Update HPACK implementation to draft-09

net/spdy/hpack_encoder.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/spdy/hpack_encoder.h"
 
 #include <algorithm>
 
 #include "base/logging.h"
 #include "net/spdy/hpack_header_table.h"
 #include "net/spdy/hpack_huffman_table.h"
 #include "net/spdy/hpack_output_stream.h"
 
 namespace net {
 
 using base::StringPiece;
 using std::string;
 
-namespace {
-
-const uint8 kNoState = 0;
-// Set on a referenced HpackEntry which is part of the current header set.
-const uint8 kReferencedImplicitOn = 1;
-// Set on a referenced HpackEntry which is not part of the current header set.
-const uint8 kReferencedExplicitOff = 2;
-// Set on a entries added to the reference set during this encoding.
-const uint8 kReferencedThisEncoding = 3;
-
-}  // namespace
-
 HpackEncoder::HpackEncoder(const HpackHuffmanTable& table)
     : output_stream_(),
       allow_huffman_compression_(true),
       huffman_table_(table),
       char_counts_(NULL),
       total_char_counts_(NULL) {}
 
 HpackEncoder::~HpackEncoder() {}
 
 bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set,
                                    string* output) {
-  // Walk the set of entries to encode, which are not already implied by the
-  // header table's reference set. They must be explicitly emitted.
-  Representations explicit_set(DetermineEncodingDelta(header_set));
-  for (Representations::const_iterator it = explicit_set.begin();
-       it != explicit_set.end(); ++it) {
-    // Try to find an exact match. Note that dynamic entries are preferred
-    // by the header table index.
-    HpackEntry* entry = header_table_.GetByNameAndValue(it->first, it->second);
-    if (entry != NULL && !entry->IsStatic()) {
-      // Already in the dynamic table. Simply toggle on.
-      CHECK_EQ(kNoState, entry->state());
-      EmitDynamicIndex(entry);
-      continue;
-    }
-
-    // Walk the set of entries to be evicted by this insertion.
-    HpackHeaderTable::EntryTable::iterator evict_begin, evict_end, evict_it;
-    header_table_.EvictionSet(it->first, it->second, &evict_begin, &evict_end);
-
-    for (evict_it = evict_begin; evict_it != evict_end; ++evict_it) {
-      HpackEntry* evictee = &(*evict_it);
-
-      if (evict_it->state() == kReferencedImplicitOn) {
-        // Issue twice to explicitly emit.
-        EmitDynamicIndex(evictee);
-        EmitDynamicIndex(evictee);
-      } else if (evictee->state() == kReferencedExplicitOff) {
-        // Eviction saves us from having to explicitly toggle off.
-        evictee->set_state(kNoState);
-      } else if (evictee->state() == kReferencedThisEncoding) {
-        // Already emitted. No action required.
-        evictee->set_state(kNoState);
-      }
-    }
-    if (entry != NULL) {
-      EmitStaticIndex(entry);
+  // Flatten & crumble headers into an ordered list of representations.
+  Representations full_set;
+  for (std::map<string, string>::const_iterator it = header_set.begin();
+       it != header_set.end(); ++it) {
+    if (it->first == "cookie") {
+      // |CookieToCrumbs()| produces ordered crumbs.
+      CookieToCrumbs(*it, &full_set);
     } else {
-      EmitIndexedLiteral(*it);
+      // Note std::map guarantees representations are ordered.
+      full_set.push_back(make_pair(
+          StringPiece(it->first), StringPiece(it->second)));
     }

[Johnny, 2014/08/06 15:04:50]

:pseudo-headers must appear first. I think this Just Works due to the magic of
ASCII codepoint ordering, but would be good to document the requirement (and add
tests for it).

[Bence, 2014/08/08 13:57:56]

I agree.  I'll do this on a separate CL.

   }
-  // Walk the reference set, toggling off as needed and clearing encoding state.
-  for (HpackHeaderTable::OrderedEntrySet::const_iterator it =
-           header_table_.reference_set().begin();
-       it != header_table_.reference_set().end();) {
-    HpackEntry* entry = *(it++);  // Step to prevent invalidation.
-    CHECK_NE(kNoState, entry->state());
 
-    if (entry->state() == kReferencedExplicitOff) {
-      // Explicitly toggle off.
-      EmitDynamicIndex(entry);
-    }
-    entry->set_state(kNoState);
+  // Walk this ordered list and encode entries.
+  for (Representations::const_iterator it = full_set.begin();
+       it != full_set.end(); ++it) {
+    HpackEntry* entry = header_table_.GetByNameAndValue(it->first, it->second);
+    if (entry != NULL)
+      EmitIndex(entry);
+    else
+      EmitIndexedLiteral(*it);
   }
+
   output_stream_.TakeString(output);
   return true;
 }
 
 bool HpackEncoder::EncodeHeaderSetWithoutCompression(
     const std::map<string, string>& header_set,
     string* output) {
 
   allow_huffman_compression_ = false;
   for (std::map<string, string>::const_iterator it = header_set.begin();
        it != header_set.end(); ++it) {
     // Note that cookies are not crumbled in this case.
     EmitNonIndexedLiteral(*it);
   }
   allow_huffman_compression_ = true;
   output_stream_.TakeString(output);
   return true;
 }
 
-void HpackEncoder::EmitDynamicIndex(HpackEntry* entry) {
-  DCHECK(!entry->IsStatic());
+void HpackEncoder::EmitIndex(HpackEntry* entry) {
   output_stream_.AppendPrefix(kIndexedOpcode);
   output_stream_.AppendUint32(header_table_.IndexOf(entry));
-
-  entry->set_state(kNoState);
-  if (header_table_.Toggle(entry)) {
-    // Was added to the reference set.
-    entry->set_state(kReferencedThisEncoding);
-  }
-}
-
-void HpackEncoder::EmitStaticIndex(HpackEntry* entry) {
-  DCHECK(entry->IsStatic());
-  output_stream_.AppendPrefix(kIndexedOpcode);
-  output_stream_.AppendUint32(header_table_.IndexOf(entry));
-
-  HpackEntry* new_entry = header_table_.TryAddEntry(entry->name(),
-                                                    entry->value());
-  if (new_entry) {
-    // This is a static entry: no need to pin.
-    header_table_.Toggle(new_entry);
-    new_entry->set_state(kReferencedThisEncoding);
-  }
 }
 
 void HpackEncoder::EmitIndexedLiteral(const Representation& representation) {
   output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode);
   EmitLiteral(representation);
-
-  HpackEntry* new_entry = header_table_.TryAddEntry(representation.first,
-                                                    representation.second);
-  if (new_entry) {
-    header_table_.Toggle(new_entry);
-    new_entry->set_state(kReferencedThisEncoding);
-  }
+  header_table_.TryAddEntry(representation.first, representation.second);
 }
 
 void HpackEncoder::EmitNonIndexedLiteral(
     const Representation& representation) {
   output_stream_.AppendPrefix(kLiteralNoIndexOpcode);
   output_stream_.AppendUint32(0);
   EmitString(representation.first);
   EmitString(representation.second);
 }
 
@@ skipping 16 matching lines @@
     output_stream_.AppendUint32(encoded_size);
     huffman_table_.EncodeString(str, &output_stream_);
   } else {
     output_stream_.AppendPrefix(kStringLiteralIdentityEncoded);
     output_stream_.AppendUint32(str.size());
     output_stream_.AppendBytes(str);
   }
   UpdateCharacterCounts(str);
 }
 
-// static
-HpackEncoder::Representations HpackEncoder::DetermineEncodingDelta(
-    const std::map<string, string>& header_set) {
-  // Flatten & crumble headers into an ordered list of representations.
-  Representations full_set;
-  for (std::map<string, string>::const_iterator it = header_set.begin();
-       it != header_set.end(); ++it) {
-    if (it->first == "cookie") {
-      // |CookieToCrumbs()| produces ordered crumbs.
-      CookieToCrumbs(*it, &full_set);
-    } else {
-      // Note std::map guarantees representations are ordered.
-      full_set.push_back(make_pair(
-          StringPiece(it->first), StringPiece(it->second)));
-    }
-  }
-  // Perform a linear merge of ordered representations with the (also ordered)
-  // reference set. Mark each referenced entry with current membership state,
-  // and gather representations which must be explicitly emitted.
-  Representations::const_iterator r_it = full_set.begin();
-  HpackHeaderTable::OrderedEntrySet::const_iterator s_it =
-      header_table_.reference_set().begin();
-
-  Representations explicit_set;
-  while (r_it != full_set.end() &&
-         s_it != header_table_.reference_set().end()) {
-    // Compare on name, then value.
-    int result = r_it->first.compare((*s_it)->name());
-    if (result == 0) {
-      result = r_it->second.compare((*s_it)->value());
-    }
-
-    if (result < 0) {
-      explicit_set.push_back(*r_it);
-      ++r_it;
-    } else if (result > 0) {
-      (*s_it)->set_state(kReferencedExplicitOff);
-      ++s_it;
-    } else {
-      (*s_it)->set_state(kReferencedImplicitOn);
-      ++s_it;
-      ++r_it;
-    }
-  }
-  while (r_it != full_set.end()) {
-    explicit_set.push_back(*r_it);
-    ++r_it;
-  }
-  while (s_it != header_table_.reference_set().end()) {
-    (*s_it)->set_state(kReferencedExplicitOff);
-    ++s_it;
-  }
-  return explicit_set;
-}
-
 void HpackEncoder::SetCharCountsStorage(std::vector<size_t>* char_counts,
                                         size_t* total_char_counts) {
   CHECK_LE(256u, char_counts->size());
   char_counts_ = char_counts;
   total_char_counts_ = total_char_counts;
 }
 
 void HpackEncoder::UpdateCharacterCounts(base::StringPiece str) {
   if (char_counts_ == NULL || total_char_counts_ == NULL) {
     return;
@@ skipping 31 matching lines @@
       pos++;
     }
   }
   // Sort crumbs and remove duplicates.
   std::sort(out->begin() + prior_size, out->end());
   out->erase(std::unique(out->begin() + prior_size, out->end()),
              out->end());
 }
 
 }  // namespace net