Implement decoding of indexed headers for HPACK

Also update the handling of indexed headers to match the -05 spec
(i.e., handle the special-cased 0 index).

This lands server change 60576720 by akalin.

BUG=339578
R=rch@chromium.org

Review URL: https://codereview.chromium.org/142083006

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@248278 0039d316-1c4b-4281-b951-d872f2087c98

9 files changed, 168 insertions, 7 deletions

diff --git a/net/spdy/hpack_constants.h b/net/spdy/hpack_constants.h
index dd1f2c6..e3da0f1 100644
--- a/net/spdy/hpack_constants.h
+++ b/net/spdy/hpack_constants.h
@@ -24,6 +24,9 @@ struct HpackPrefix {
 // without Huffman encoding) (from 4.1.2).
 const HpackPrefix kStringLiteralIdentityEncoded = { 0x0, 1 };
 
+// The opcode for an indexed header field (from 4.2).
+const HpackPrefix kIndexedOpcode = { 0x1, 1 };
+
 // The opcode for a literal header field without indexing (from
 // 4.3.1).
 const HpackPrefix kLiteralNoIndexOpcode = { 0x01, 2 };
diff --git a/net/spdy/hpack_decoder.cc b/net/spdy/hpack_decoder.cc
index 060a88c..e85e6ff 100644
--- a/net/spdy/hpack_decoder.cc
+++ b/net/spdy/hpack_decoder.cc
@@ -43,6 +43,40 @@ bool HpackDecoder::DecodeHeaderSet(StringPiece input,
 
 bool HpackDecoder::ProcessNextHeaderRepresentation(
     HpackInputStream* input_stream, HpackHeaderPairVector* header_list) {
+  // Touches are used below to track which headers have been emitted.
+
+  // Implements 4.2. Indexed Header Field Representation.
+  if (input_stream->MatchPrefixAndConsume(kIndexedOpcode)) {
+    uint32 index_or_zero = 0;
+    if (!input_stream->DecodeNextUint32(&index_or_zero))
+      return false;
+
+    if (index_or_zero > context_.GetEntryCount())
+      return false;
+
+    bool emitted = false;
+    if (index_or_zero > 0) {
+      uint32 index = index_or_zero;
+      // The index will be put into the reference set.
+      if (!context_.IsReferencedAt(index)) {
+        header_list->push_back(
+            HpackHeaderPair(context_.GetNameAt(index).as_string(),
+                            context_.GetValueAt(index).as_string()));
+        emitted = true;
+      }
+    }
+
+    uint32 new_index = 0;
+    std::vector<uint32> removed_referenced_indices;
+    context_.ProcessIndexedHeader(
+        index_or_zero, &new_index, &removed_referenced_indices);
+
+    if (emitted && new_index > 0)
+      context_.AddTouchesAt(new_index, 0);
+
+    return true;
+  }
+
   // Implements 4.3.1. Literal Header Field without Indexing.
   if (input_stream->MatchPrefixAndConsume(kLiteralNoIndexOpcode)) {
     StringPiece name;
diff --git a/net/spdy/hpack_decoder_test.cc b/net/spdy/hpack_decoder_test.cc
index dcc5ad8..a444bed 100644
--- a/net/spdy/hpack_decoder_test.cc
+++ b/net/spdy/hpack_decoder_test.cc
@@ -8,6 +8,7 @@
 #include <string>
 
 #include "base/basictypes.h"
+#include "base/strings/string_piece.h"
 #include "net/spdy/hpack_encoder.h"
 #include "net/spdy/hpack_input_stream.h"
 #include "testing/gtest/include/gtest/gtest.h"
@@ -51,6 +52,64 @@ TEST(HpackDecoderTest, DecodeNextNameInvalidIndex) {
   EXPECT_FALSE(decoder.DecodeNextNameForTest(&input_stream, &string_piece));
 }
 
+// Utility function to decode a string into a header set, assuming
+// that the emitted headers have unique names.
+std::map<string, string> DecodeUniqueHeaderSet(
+    HpackDecoder* decoder, StringPiece str) {
+  HpackHeaderPairVector header_list;
+  EXPECT_TRUE(decoder->DecodeHeaderSet(str, &header_list));
+  std::map<string, string> header_set(
+      header_list.begin(), header_list.end());
+  // Make sure |header_list| has no duplicates.
+  EXPECT_EQ(header_set.size(), header_list.size());
+  return header_set;
+}
+
+// Decoding an indexed header should toggle the index's presence in
+// the reference set, making a copy of static table entries if
+// necessary. It should also emit the header if toggled on (and only
+// as many times as it was toggled on).
+TEST(HpackDecoderTest, IndexedHeaderBasic) {
+  HpackDecoder decoder(kuint32max);
+
+  // Toggle on static table entry #2 (and make a copy at index #1),
+  // then toggle on static table entry #5 (which is now #6 because of
+  // the copy of #2).
+  std::map<string, string> header_set1 =
+      DecodeUniqueHeaderSet(&decoder, "\x82\x86");
+  std::map<string, string> expected_header_set1;
+  expected_header_set1[":method"] = "GET";
+  expected_header_set1[":path"] = "/index.html";
+  EXPECT_EQ(expected_header_set1, header_set1);
+
+  std::map<string, string> expected_header_set2;
+  expected_header_set2[":path"] = "/index.html";
+  // Toggle off the copy of static table entry #5.
+  std::map<string, string> header_set2 =
+      DecodeUniqueHeaderSet(&decoder, "\x82");
+  EXPECT_EQ(expected_header_set2, header_set2);
+}
+
+// Decoding an indexed header with index 0 should clear the reference
+// set.
+TEST(HpackDecoderTest, IndexedHeaderZero) {
+  HpackDecoder decoder(kuint32max);
+
+  // Toggle on a couple of headers.
+  std::map<string, string> header_set1 =
+      DecodeUniqueHeaderSet(&decoder, "\x82\x86");
+  std::map<string, string> expected_header_set1;
+  expected_header_set1[":method"] = "GET";
+  expected_header_set1[":path"] = "/index.html";
+  EXPECT_EQ(expected_header_set1, header_set1);
+
+  // Toggle index 0 to clear the reference set.
+  std::map<string, string> header_set2 =
+      DecodeUniqueHeaderSet(&decoder, "\x80");
+  std::map<string, string> expected_header_set2;
+  EXPECT_EQ(expected_header_set2, header_set2);
+}
+
 // Decoding two valid encoded literal headers with no indexing should
 // work.
 TEST(HpackDecoderTest, LiteralHeaderNoIndexing) {
diff --git a/net/spdy/hpack_encoding_context.cc b/net/spdy/hpack_encoding_context.cc
index c395064..28d090e 100644
--- a/net/spdy/hpack_encoding_context.cc
+++ b/net/spdy/hpack_encoding_context.cc
@@ -169,12 +169,28 @@ void HpackEncodingContext::SetMaxSize(uint32 max_size) {
 }
 
 bool HpackEncodingContext::ProcessIndexedHeader(
-    uint32 index,
+    uint32 index_or_zero,
     uint32* new_index,
     std::vector<uint32>* removed_referenced_indices) {
-  if (index < 1 || index > GetEntryCount())
+  if (index_or_zero > GetEntryCount())
     return false;
 
+  if (index_or_zero == 0) {
+    *new_index = 0;
+    removed_referenced_indices->clear();
+    // Empty the reference set.
+    for (size_t i = 1; i <= header_table_.GetEntryCount(); ++i) {
+      HpackEntry* entry = header_table_.GetMutableEntry(i);
+      if (entry->IsReferenced()) {
+        removed_referenced_indices->push_back(i);
+        entry->SetReferenced(false);
+      }
+    }
+    return true;
+  }
+
+  uint32 index = index_or_zero;
+
   if (index <= header_table_.GetEntryCount()) {
     *new_index = index;
     removed_referenced_indices->clear();
diff --git a/net/spdy/hpack_encoding_context.h b/net/spdy/hpack_encoding_context.h
index 870e004..9a4a2e8 100644
--- a/net/spdy/hpack_encoding_context.h
+++ b/net/spdy/hpack_encoding_context.h
@@ -77,11 +77,12 @@ class NET_EXPORT_PRIVATE HpackEncodingContext {
   // if an error was encountered.
 
   // Tries to update the encoding context given an indexed header
-  // opcode for the given index as described in 3.2.1. new_index is
-  // filled in with the index of a mutable entry, or 0 if one was not
-  // able to be created. removed_referenced_indices is filled in with
-  // the indices of all entries removed from the reference set.
-  bool ProcessIndexedHeader(uint32 index,
+  // opcode for the given index (or zero) as described in
+  // 3.2.1. new_index is filled in with the index of a mutable entry,
+  // or 0 if one was not created. removed_referenced_indices is filled
+  // in with the indices of all entries removed from the reference
+  // set.
+  bool ProcessIndexedHeader(uint32 index_or_zero,
                             uint32* new_index,
                             std::vector<uint32>* removed_referenced_indices);
 
diff --git a/net/spdy/hpack_encoding_context_test.cc b/net/spdy/hpack_encoding_context_test.cc
index e202eae..2a2c6d3 100644
--- a/net/spdy/hpack_encoding_context_test.cc
+++ b/net/spdy/hpack_encoding_context_test.cc
@@ -88,6 +88,36 @@ TEST(HpackEncodingContextTest, IndexedHeaderStaticCopyDoesNotFit) {
   EXPECT_EQ(0u, encoding_context.GetMutableEntryCount());
 }
 
+// Add a bunch of new headers and then try to process an indexed
+// header with index 0. That should clear the reference set.
+TEST(HpackEncodingContextTest, IndexedHeaderZero) {
+  HpackEncodingContext encoding_context;
+
+  uint32 kEntryCount = 50;
+  std::vector<uint32> expected_removed_referenced_indices;
+
+  for (uint32 i = 1; i <= kEntryCount; ++i) {
+    uint32 new_index = 0;
+    std::vector<uint32> removed_referenced_indices;
+    EXPECT_TRUE(
+        encoding_context.ProcessIndexedHeader(i,
+                                              &new_index,
+                                              &removed_referenced_indices));
+    EXPECT_EQ(1u, new_index);
+    EXPECT_TRUE(removed_referenced_indices.empty());
+    EXPECT_EQ(i, encoding_context.GetMutableEntryCount());
+    expected_removed_referenced_indices.push_back(i);
+  }
+
+  uint32 new_index = 0;
+  std::vector<uint32> removed_referenced_indices;
+  EXPECT_TRUE(
+      encoding_context.ProcessIndexedHeader(0, &new_index,
+                                            &removed_referenced_indices));
+  EXPECT_EQ(0u, new_index);
+  EXPECT_EQ(expected_removed_referenced_indices, removed_referenced_indices);
+}
+
 // NOTE: It's too onerous to try to test invalid input to
 // ProcessLiteralHeaderWithIncrementalIndexing(); that would require
 // making a really large (>4GB of memory) string.
diff --git a/net/spdy/hpack_output_stream.cc b/net/spdy/hpack_output_stream.cc
index e499fbf..5290892 100644
--- a/net/spdy/hpack_output_stream.cc
+++ b/net/spdy/hpack_output_stream.cc
@@ -18,6 +18,11 @@ HpackOutputStream::HpackOutputStream(uint32 max_string_literal_size)
 
 HpackOutputStream::~HpackOutputStream() {}
 
+void HpackOutputStream::AppendIndexedHeader(uint32 index_or_zero) {
+  AppendPrefix(kIndexedOpcode);
+  AppendUint32(index_or_zero);
+}
+
 bool HpackOutputStream::AppendLiteralHeaderNoIndexingWithName(
     StringPiece name, StringPiece value) {
   AppendPrefix(kLiteralNoIndexOpcode);
diff --git a/net/spdy/hpack_output_stream.h b/net/spdy/hpack_output_stream.h
index f82ec92..7ad13e6 100644
--- a/net/spdy/hpack_output_stream.h
+++ b/net/spdy/hpack_output_stream.h
@@ -30,6 +30,9 @@ class NET_EXPORT_PRIVATE HpackOutputStream {
   explicit HpackOutputStream(uint32 max_string_literal_size);
   ~HpackOutputStream();
 
+  // Corresponds to 4.2.
+  void AppendIndexedHeader(uint32 index_or_zero);
+
   // Corresponds to 4.3.1 (second form). Returns whether or not the
   // append was successful; if the append was unsuccessful, no other
   // member function may be called.
diff --git a/net/spdy/hpack_output_stream_test.cc b/net/spdy/hpack_output_stream_test.cc
index 0a81341..0321e3d 100644
--- a/net/spdy/hpack_output_stream_test.cc
+++ b/net/spdy/hpack_output_stream_test.cc
@@ -266,6 +266,16 @@ TEST(HpackOutputStreamTest, AppendStringLiteralTooLong) {
       base::StringPiece(NULL, kuint32max)));
 }
 
+// Test that encoding an indexed header simply encodes the index.
+TEST(HpackOutputStreamTest, AppendIndexedHeader) {
+  HpackOutputStream output_stream(kuint32max);
+  output_stream.AppendIndexedHeader(0xffffffff);
+
+  string str;
+  output_stream.TakeString(&str);
+  EXPECT_EQ("\xff\x80\xff\xff\xff\x0f", str);
+}
+
 // Test that encoding a literal header without indexing with a name
 // encodes both the name and value as string literals.
 TEST(HpackOutputStreamTest, AppendLiteralHeaderNoIndexingWithName) {