4 files changed, 533 insertions, 0 deletions
diff --git a/net/net.gyp b/net/net.gyp
index 0bd0915..03a4fe6 100644
--- a/net/net.gyp
+++ b/net/net.gyp
@@ -1034,6 +1034,8 @@
         'spdy/spdy_framer.h',
         'spdy/spdy_header_block.cc',
         'spdy/spdy_header_block.h',
+        'spdy/spdy_headers_block_parser.cc',
+        'spdy/spdy_headers_block_parser.h',
         'spdy/spdy_http_stream.cc',
         'spdy/spdy_http_stream.h',
         'spdy/spdy_http_utils.cc',
@@ -1972,6 +1974,7 @@
         'spdy/spdy_frame_reader_test.cc',
         'spdy/spdy_framer_test.cc',
         'spdy/spdy_header_block_unittest.cc',
+        'spdy/spdy_headers_block_parser_test.cc',
         'spdy/spdy_http_stream_unittest.cc',
         'spdy/spdy_http_utils_unittest.cc',
         'spdy/spdy_network_transaction_unittest.cc',
diff --git a/net/spdy/spdy_headers_block_parser.cc b/net/spdy/spdy_headers_block_parser.cc
new file mode 100644
index 0000000..30bc00c
--- /dev/null
+++ b/net/spdy/spdy_headers_block_parser.cc
@@ -0,0 +1,181 @@
+// 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/spdy_headers_block_parser.h"
+
+#include <memory>
+
+#include "base/sys_byteorder.h"
+
+namespace net {
+
+SpdyHeadersBlockParserReader::SpdyHeadersBlockParserReader(
+    base::StringPiece prefix,
+    base::StringPiece suffix)
+      : prefix_(prefix),
+        suffix_(suffix),
+        in_suffix_(false),
+        offset_(0) {}
+
+size_t SpdyHeadersBlockParserReader::Available() {
+  if (in_suffix_) {
+    return suffix_.length() - offset_;
+  } else {
+    return prefix_.length() + suffix_.length() - offset_;
+  }
+}
+
+bool SpdyHeadersBlockParserReader::ReadN(size_t count, char* out) {
+  if (Available() < count)
+    return false;
+
+  if (!in_suffix_ && count > (prefix_.length() - offset_)) {
+    count -= prefix_.length() - offset_;
+    out = std::copy(prefix_.begin() + offset_, prefix_.end(), out);
+    in_suffix_ = true;
+    offset_ = 0;
+    // Fallthrough to suffix read.
+  } else if (!in_suffix_) {
+    // Read is satisfied by the prefix.
+    DCHECK_GE(prefix_.length() - offset_, count);
+    std::copy(prefix_.begin() + offset_,
+              prefix_.begin() + offset_ + count,
+              out);
+    offset_ += count;
+    return true;
+  }
+  // Read is satisfied by the suffix.
+  DCHECK(in_suffix_);
+  DCHECK_GE(suffix_.length() - offset_, count);
+  std::copy(suffix_.begin() + offset_,
+            suffix_.begin() + offset_ + count,
+            out);
+  offset_ += count;
+  return true;
+}
+
+std::vector<char> SpdyHeadersBlockParserReader::Remainder() {
+  std::vector<char> remainder(Available(), '\0');
+  if (remainder.size()) {
+    ReadN(remainder.size(), &remainder[0]);
+  }
+  DCHECK_EQ(0u, Available());
+  return remainder;
+}
+
+SpdyHeadersBlockParser::SpdyHeadersBlockParser(KeyValueHandler* handler) :
+    state_(READING_HEADER_BLOCK_LEN),
+    remaining_key_value_pairs_for_frame_(0),
+    next_field_len_(0),
+    handler_(handler) {
+}
+
+SpdyHeadersBlockParser::~SpdyHeadersBlockParser() {}
+
+bool SpdyHeadersBlockParser::ParseUInt32(Reader* reader,
+                                         uint32_t* parsed_value) {
+  // Are there enough bytes available?
+  if (reader->Available() < sizeof(uint32_t)) {
+    return false;
+  }
+
+  // Read the required bytes, convert from network to host
+  // order and return the parsed out integer.
+  char buf[sizeof(uint32_t)];
+  reader->ReadN(sizeof(uint32_t), buf);
+  *parsed_value = base::NetToHost32(*reinterpret_cast<const uint32_t *>(buf));
+  return true;
+}
+
+void SpdyHeadersBlockParser::Reset() {
+  // Clear any saved state about the last headers block.
+  headers_block_prefix_.clear();
+  state_ = READING_HEADER_BLOCK_LEN;
+}
+
+void SpdyHeadersBlockParser::HandleControlFrameHeadersData(
+    const char* headers_data, size_t len) {
+  // Only do something if we received anything new.
+  if (len == 0) {
+    return;
+  }
+
+  // Reader avoids copying data.
+  base::StringPiece prefix;
+  if (headers_block_prefix_.size()) {
+    prefix.set(&headers_block_prefix_[0], headers_block_prefix_.size());
+  }
+  Reader reader(prefix, base::StringPiece(headers_data, len));
+
+  // If we didn't parse out yet the number of key-value pairs in this
+  // headers block, try to do it now (succeeds if we received enough bytes).
+  if (state_ == READING_HEADER_BLOCK_LEN) {
+    if (ParseUInt32(&reader, &remaining_key_value_pairs_for_frame_)) {
+      state_ = READING_KEY_LEN;
+    } else {
+      headers_block_prefix_ = reader.Remainder();
+      return;
+    }
+  }
+
+  // Parse out and handle the key-value pairs.
+  while (remaining_key_value_pairs_for_frame_ > 0) {
+    // Parse the key-value length, in case we don't already have it.
+    if ((state_ == READING_KEY_LEN) || (state_ == READING_VALUE_LEN)) {
+      if (ParseUInt32(&reader, &next_field_len_)) {
+        state_ == READING_KEY_LEN ? state_ = READING_KEY :
+                                    state_ = READING_VALUE;
+      } else {
+        // Did not receive enough bytes.
+        break;
+      }
+    }
+
+    // Parse the next field if we received enough bytes.
+    if (reader.Available() >= next_field_len_) {
+      // Copy the field from the cord.
+      char* key_value_buf(new char[next_field_len_]);
+      reader.ReadN(next_field_len_, key_value_buf);
+
+      // Is this field a key?
+      if (state_ == READING_KEY) {
+        current_key.reset(key_value_buf);
+        key_len_ = next_field_len_;
+        state_ = READING_VALUE_LEN;
+
+      } else if (state_ == READING_VALUE) {
+        // We already had the key, now we got its value.
+        current_value.reset(key_value_buf);
+
+        // Call the handler for the key-value pair that we received.
+        handler_->OnKeyValuePair(
+            base::StringPiece(current_key.get(), key_len_),
+            base::StringPiece(current_value.get(), next_field_len_));
+
+        // Free allocated key and value strings.
+        current_key.reset();
+        current_value.reset();
+
+        // Finished handling a key-value pair.
+        remaining_key_value_pairs_for_frame_--;
+
+        // Finished handling a header, prepare for the next one.
+        state_ = READING_KEY_LEN;
+      }
+    } else {
+      // Did not receive enough bytes.
+      break;
+    }
+  }
+
+  // Unread suffix becomes the prefix upon next invocation.
+  headers_block_prefix_ = reader.Remainder();
+
+  // Did we finish handling the current block?
+  if (remaining_key_value_pairs_for_frame_ == 0) {
+    Reset();
+  }
+}
+
+}  // namespace net
diff --git a/net/spdy/spdy_headers_block_parser.h b/net/spdy/spdy_headers_block_parser.h
new file mode 100644
index 0000000..9b8ec8c
--- /dev/null
+++ b/net/spdy/spdy_headers_block_parser.h
@@ -0,0 +1,116 @@
+// 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.
+
+#ifndef NET_SPDY_SPDY_HEADERS_BLOCK_PARSER_H_
+#define NET_SPDY_SPDY_HEADERS_BLOCK_PARSER_H_
+
+#include <memory>
+#include <vector>
+
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/strings/string_piece.h"
+#include "net/base/net_export.h"
+
+namespace net {
+
+// A handler class for SPDY headers block key/value pairs.
+// TODO(ygi) Modify this stub handler to pass the key-value pair
+// through the spdy logic.
+class KeyValueHandler {
+ public:
+  virtual ~KeyValueHandler() {}
+  virtual void OnKeyValuePair(const base::StringPiece& key,
+                              const base::StringPiece& value) = 0;
+};
+
+// Helper class which simplifies reading contiguously
+// from a disjoint buffer prefix & suffix.
+class NET_EXPORT_PRIVATE SpdyHeadersBlockParserReader {
+ public:
+  // StringPieces are treated as raw buffers.
+  SpdyHeadersBlockParserReader(base::StringPiece prefix,
+                               base::StringPiece suffix);
+  // Number of bytes available to be read.
+  size_t Available();
+
+  // Reads |count| bytes, copying into |*out|. Returns true on success,
+  // false if not enough bytes were available.
+  bool ReadN(size_t count, char* out);
+
+  // Returns a new string contiguously holding
+  // the remaining unread prefix and suffix.
+  std::vector<char> Remainder();
+
+ private:
+  base::StringPiece prefix_;
+  base::StringPiece suffix_;
+  bool in_suffix_;
+  size_t offset_;
+};
+
+// This class handles SPDY headers block bytes and parses out key-value pairs
+// as they arrive. This class is not thread-safe, and assumes that all headers
+// block bytes are processed in a single thread.
+class NET_EXPORT_PRIVATE SpdyHeadersBlockParser {
+ public:
+  // Costructor. The handler's OnKeyValuePair will be called for every key
+  // value pair that we parsed from the headers block.
+  explicit SpdyHeadersBlockParser(KeyValueHandler* handler);
+
+  virtual ~SpdyHeadersBlockParser();
+
+  // Handles headers block data as it arrives.
+  void HandleControlFrameHeadersData(const char* headers_data, size_t len);
+
+ private:
+  // The state of the parser.
+  enum ParserState {
+    READING_HEADER_BLOCK_LEN,
+    READING_KEY_LEN,
+    READING_KEY,
+    READING_VALUE_LEN,
+    READING_VALUE
+  };
+
+  ParserState state_;
+
+  typedef SpdyHeadersBlockParserReader Reader;
+
+  // Parses an unsigned 32 bit integer from the reader. This method assumes that
+  // the integer is in network order and converts to host order. Returns true on
+  // success and false on failure (if there were not enough bytes available).
+  static bool ParseUInt32(Reader* reader, uint32_t* parsed_value);
+
+  // Resets the state of the parser to prepare it for a headers block of a
+  // new frame.
+  void Reset();
+
+  // Number of key-value pairs until we complete handling the current
+  // headers block.
+  uint32_t remaining_key_value_pairs_for_frame_;
+
+  // The length of the next field in the headers block (either a key or
+  // a value).
+  uint32_t next_field_len_;
+
+  // The length of the key of the current header.
+  uint32_t key_len_;
+
+  // Holds unprocessed bytes of the headers block.
+  std::vector<char> headers_block_prefix_;
+
+  // Handles key-value pairs as we parse them.
+  KeyValueHandler* handler_;
+
+  // Points to the current key.
+  scoped_ptr<char[]> current_key;
+
+  // Points to the current value.
+  scoped_ptr<char[]> current_value;
+};
+
+}  // namespace net
+
+#endif  // NET_SPDY_SPDY_HEADERS_BLOCK_PARSER_H_
diff --git a/net/spdy/spdy_headers_block_parser_test.cc b/net/spdy/spdy_headers_block_parser_test.cc
new file mode 100644
index 0000000..326cb05
--- /dev/null
+++ b/net/spdy/spdy_headers_block_parser_test.cc
@@ -0,0 +1,233 @@
+// 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/spdy_headers_block_parser.h"
+
+#include <string>
+
+#include "base/strings/string_number_conversions.h"
+#include "base/sys_byteorder.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+
+using base::IntToString;
+using base::StringPiece;
+using std::string;
+using testing::ElementsAre;
+using testing::ElementsAreArray;
+
+class MockKeyValueHandler : public KeyValueHandler {
+ public:
+  // A mock the handler method to make sure we parse out (and call it with)
+  // the correct parameters.
+  MOCK_METHOD2(OnKeyValuePair, void(const StringPiece&, const StringPiece&));
+};
+
+class SpdyHeadersBlockParserTest : public testing::Test {
+ public:
+  virtual ~SpdyHeadersBlockParserTest() {}
+
+ protected:
+  virtual void SetUp() {
+    // Create a parser using the mock handler.
+    parser_.reset(new SpdyHeadersBlockParser(&handler_));
+  }
+
+  MockKeyValueHandler handler_;
+  scoped_ptr<SpdyHeadersBlockParser> parser_;
+
+  // Create a header block with a specified number of headers.
+  static string CreateHeaders(uint32_t num_headers, bool insert_nulls) {
+    string headers;
+    char length_field[sizeof(uint32_t)];
+
+    // First, write the number of headers in the header block.
+    StoreInt(num_headers, length_field);
+    headers += string(length_field, sizeof(length_field));
+
+    // Second, write the key-value pairs.
+    for (uint32_t i = 0; i < num_headers; i++) {
+      // Build the key.
+      string key;
+      if (insert_nulls) {
+        key = string(base_key) + string("\0", 1) + IntToString(i);
+      } else {
+        key = string(base_key) + IntToString(i);
+      }
+      // Encode the key as SPDY header.
+      StoreInt(key.length(), length_field);
+      headers += string(length_field, sizeof(length_field));
+      headers += key;
+
+      // Build the value.
+      string value;
+      if (insert_nulls) {
+        value = string(base_value) + string("\0", 1) + IntToString(i);
+      } else {
+        value = string(base_value) + IntToString(i);
+      }
+      // Encode the value as SPDY header.
+      StoreInt(value.length(), length_field);
+      headers += string(length_field, sizeof(length_field));
+      headers += value;
+    }
+
+    return headers;
+  }
+
+  static const char* base_key;
+  static const char* base_value;
+
+  // Number of headers and header blocks used in the tests.
+  static const int kNumHeadersInBlock = 10;
+  static const int kNumHeaderBlocks = 10;
+
+ private:
+  static void StoreInt(uint32_t num, char* buf) {
+    uint32_t net_order_len = base::HostToNet32(num);
+    memcpy(buf, &net_order_len, sizeof(num));
+  }
+};
+
+const char* SpdyHeadersBlockParserTest::base_key = "test_key";
+const char* SpdyHeadersBlockParserTest::base_value = "test_value";
+
+TEST_F(SpdyHeadersBlockParserTest, Basic) {
+  // Sanity test, verify that we parse out correctly a block with
+  // a single key-value pair.
+  std::string expect_key = base_key + IntToString(0);
+  std::string expect_value = base_value + IntToString(0);
+  EXPECT_CALL(handler_, OnKeyValuePair(StringPiece(expect_key),
+                                       StringPiece(expect_value))).Times(1);
+  string headers(CreateHeaders(1, false));
+  parser_->HandleControlFrameHeadersData(headers.c_str(), headers.length());
+}
+
+TEST_F(SpdyHeadersBlockParserTest, NullsSupported) {
+  // Sanity test, verify that we parse out correctly a block with
+  // a single key-value pair when the key and value contain null charecters.
+  std::string expect_key = base_key + string("\0", 1) + IntToString(0);
+  std::string expect_value = base_value + string("\0", 1) + IntToString(0);
+  EXPECT_CALL(handler_, OnKeyValuePair(StringPiece(expect_key),
+                                       StringPiece(expect_value))).Times(1);
+  string headers(CreateHeaders(1, true));
+  parser_->HandleControlFrameHeadersData(headers.c_str(), headers.length());
+}
+
+TEST_F(SpdyHeadersBlockParserTest, MultipleBlocksMultipleHeadersPerBlock) {
+  testing::InSequence s;
+
+  // The mock doesn't retain storage of arguments, so keep them in scope.
+  std::vector<string> retained_arguments;
+  for (int i = 0; i < kNumHeadersInBlock; i++) {
+    retained_arguments.push_back(base_key + IntToString(i));
+    retained_arguments.push_back(base_value + IntToString(i));
+  }
+  // For each block we expect to parse out the headers in order.
+  for (int i = 0; i < kNumHeaderBlocks; i++) {
+    for (int j = 0; j < kNumHeadersInBlock; j++) {
+      EXPECT_CALL(handler_, OnKeyValuePair(
+          StringPiece(retained_arguments[2 * j]),
+          StringPiece(retained_arguments[2 * j + 1]))).Times(1);
+    }
+  }
+  // Parse the blocks, breaking them into multiple reads at various points.
+  for (int i = 0; i < kNumHeaderBlocks; i++) {
+    unsigned break_index = 4 * i;
+    string headers(CreateHeaders(kNumHeadersInBlock, false));
+    parser_->HandleControlFrameHeadersData(
+        headers.c_str(), headers.length() - break_index);
+    parser_->HandleControlFrameHeadersData(
+        headers.c_str() + headers.length() - break_index, break_index);
+  }
+}
+
+TEST(SpdyHeadersBlockParserReader, EmptyPrefix) {
+  std::string prefix = "";
+  std::string suffix = "foobar";
+  char buffer[] = "12345";
+
+  SpdyHeadersBlockParserReader reader(prefix, suffix);
+  EXPECT_EQ(6u, reader.Available());
+  EXPECT_FALSE(reader.ReadN(10, buffer));  // Not enough buffer.
+  EXPECT_TRUE(reader.ReadN(5, buffer));
+  EXPECT_THAT(buffer, ElementsAreArray("fooba"));
+  EXPECT_EQ(1u, reader.Available());
+  EXPECT_THAT(reader.Remainder(), ElementsAre('r'));
+}
+
+TEST(SpdyHeadersBlockParserReader, EmptySuffix) {
+  std::string prefix = "foobar";
+  std::string suffix = "";
+  char buffer[] = "12345";
+
+  SpdyHeadersBlockParserReader reader(prefix, suffix);
+  EXPECT_EQ(6u, reader.Available());
+  EXPECT_FALSE(reader.ReadN(10, buffer));  // Not enough buffer.
+  EXPECT_TRUE(reader.ReadN(5, buffer));
+  EXPECT_THAT(buffer, ElementsAreArray("fooba"));
+  EXPECT_EQ(1u, reader.Available());
+  EXPECT_THAT(reader.Remainder(), ElementsAre('r'));
+}
+
+TEST(SpdyHeadersBlockParserReader, ReadInPrefix) {
+  std::string prefix = "abcdef";
+  std::string suffix = "ghijk";
+  char buffer[] = "1234";
+
+  SpdyHeadersBlockParserReader reader(prefix, suffix);
+  EXPECT_EQ(11u, reader.Available());
+  EXPECT_TRUE(reader.ReadN(4, buffer));
+  EXPECT_THAT(buffer, ElementsAreArray("abcd"));
+  EXPECT_EQ(7u, reader.Available());
+  EXPECT_THAT(reader.Remainder(),
+            ElementsAre('e', 'f', 'g', 'h', 'i', 'j', 'k'));
+}
+
+TEST(SpdyHeadersBlockParserReader, ReadPastPrefix) {
+  std::string prefix = "abcdef";
+  std::string suffix = "ghijk";
+  char buffer[] = "12345";
+
+  SpdyHeadersBlockParserReader reader(prefix, suffix);
+  EXPECT_EQ(11u, reader.Available());
+  EXPECT_TRUE(reader.ReadN(5, buffer));
+  EXPECT_THAT(buffer, ElementsAreArray("abcde"));
+
+  // One byte of prefix left: read it.
+  EXPECT_EQ(6u, reader.Available());
+  EXPECT_TRUE(reader.ReadN(1, buffer));
+  EXPECT_THAT(buffer, ElementsAreArray("fbcde"));
+
+  // Read one byte of suffix.
+  EXPECT_EQ(5u, reader.Available());
+  EXPECT_TRUE(reader.ReadN(1, buffer));
+  EXPECT_THAT(buffer, ElementsAreArray("gbcde"));
+
+  EXPECT_THAT(reader.Remainder(),
+            ElementsAre('h', 'i', 'j', 'k'));
+}
+
+TEST(SpdyHeadersBlockParserReader, ReadAcrossSuffix) {
+  std::string prefix = "abcdef";
+  std::string suffix = "ghijk";
+  char buffer[] = "12345678";
+
+  SpdyHeadersBlockParserReader reader(prefix, suffix);
+  EXPECT_EQ(11u, reader.Available());
+  EXPECT_TRUE(reader.ReadN(8, buffer));
+  EXPECT_THAT(buffer, ElementsAreArray("abcdefgh"));
+
+  EXPECT_EQ(3u, reader.Available());
+  EXPECT_FALSE(reader.ReadN(4, buffer));
+  EXPECT_TRUE(reader.ReadN(3, buffer));
+  EXPECT_THAT(buffer, ElementsAreArray("ijkdefgh"));
+
+  EXPECT_EQ(0u, reader.Available());
+  EXPECT_THAT(reader.Remainder(), ElementsAre());
+}
+
+}  // namespace net