1// Copyright 2014 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "net/spdy/hpack_encoder.h"
6
7#include <map>
8#include <string>
9
10#include "testing/gmock/include/gmock/gmock.h"
11#include "testing/gtest/include/gtest/gtest.h"
12
13namespace net {
14
15using base::StringPiece;
16using std::string;
17using testing::ElementsAre;
18
19namespace test {
20
21class HpackHeaderTablePeer {
22 public:
23  explicit HpackHeaderTablePeer(HpackHeaderTable* table)
24      : table_(table) {}
25
26  HpackHeaderTable::EntryTable* dynamic_entries() {
27    return &table_->dynamic_entries_;
28  }
29
30 private:
31  HpackHeaderTable* table_;
32};
33
34class HpackEncoderPeer {
35 public:
36  typedef HpackEncoder::Representation Representation;
37  typedef HpackEncoder::Representations Representations;
38
39  explicit HpackEncoderPeer(HpackEncoder* encoder)
40    : encoder_(encoder) {}
41
42  HpackHeaderTable* table() {
43    return &encoder_->header_table_;
44  }
45  HpackHeaderTablePeer table_peer() {
46    return HpackHeaderTablePeer(table());
47  }
48  bool allow_huffman_compression() {
49    return encoder_->allow_huffman_compression_;
50  }
51  void set_allow_huffman_compression(bool allow) {
52    encoder_->allow_huffman_compression_ = allow;
53  }
54  void EmitString(StringPiece str) {
55    encoder_->EmitString(str);
56  }
57  void TakeString(string* out) {
58    encoder_->output_stream_.TakeString(out);
59  }
60  void UpdateCharacterCounts(StringPiece str) {
61    encoder_->UpdateCharacterCounts(str);
62  }
63  static void CookieToCrumbs(StringPiece cookie,
64                             std::vector<StringPiece>* out) {
65    Representations tmp;
66    HpackEncoder::CookieToCrumbs(make_pair("", cookie), &tmp);
67
68    out->clear();
69    for (size_t i = 0; i != tmp.size(); ++i) {
70      out->push_back(tmp[i].second);
71    }
72  }
73  static void DecomposeRepresentation(StringPiece value,
74                                      std::vector<StringPiece>* out) {
75    Representations tmp;
76    HpackEncoder::DecomposeRepresentation(make_pair("foobar", value), &tmp);
77
78    out->clear();
79    for (size_t i = 0; i != tmp.size(); ++i) {
80      out->push_back(tmp[i].second);
81    }
82  }
83
84 private:
85  HpackEncoder* encoder_;
86};
87
88}  // namespace test
89
90namespace {
91
92using std::map;
93using testing::ElementsAre;
94
95class HpackEncoderTest : public ::testing::Test {
96 protected:
97  typedef test::HpackEncoderPeer::Representations Representations;
98
99  HpackEncoderTest()
100      : encoder_(ObtainHpackHuffmanTable()),
101        peer_(&encoder_),
102        static_(peer_.table()->GetByIndex(1)) {}
103
104  virtual void SetUp() {
105    // Populate dynamic entries into the table fixture. For simplicity each
106    // entry has name.size() + value.size() == 10.
107    key_1_ = peer_.table()->TryAddEntry("key1", "value1");
108    key_2_ = peer_.table()->TryAddEntry("key2", "value2");
109    cookie_a_ = peer_.table()->TryAddEntry("cookie", "a=bb");
110    cookie_c_ = peer_.table()->TryAddEntry("cookie", "c=dd");
111
112    // No further insertions may occur without evictions.
113    peer_.table()->SetMaxSize(peer_.table()->size());
114
115    // Disable Huffman coding by default. Most tests don't care about it.
116    peer_.set_allow_huffman_compression(false);
117  }
118
119  void ExpectIndex(size_t index) {
120    expected_.AppendPrefix(kIndexedOpcode);
121    expected_.AppendUint32(index);
122  }
123  void ExpectIndexedLiteral(const HpackEntry* key_entry, StringPiece value) {
124    expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
125    expected_.AppendUint32(IndexOf(key_entry));
126    expected_.AppendPrefix(kStringLiteralIdentityEncoded);
127    expected_.AppendUint32(value.size());
128    expected_.AppendBytes(value);
129  }
130  void ExpectIndexedLiteral(StringPiece name, StringPiece value) {
131    expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
132    expected_.AppendUint32(0);
133    expected_.AppendPrefix(kStringLiteralIdentityEncoded);
134    expected_.AppendUint32(name.size());
135    expected_.AppendBytes(name);
136    expected_.AppendPrefix(kStringLiteralIdentityEncoded);
137    expected_.AppendUint32(value.size());
138    expected_.AppendBytes(value);
139  }
140  void ExpectNonIndexedLiteral(StringPiece name, StringPiece value) {
141    expected_.AppendPrefix(kLiteralNoIndexOpcode);
142    expected_.AppendUint32(0);
143    expected_.AppendPrefix(kStringLiteralIdentityEncoded);
144    expected_.AppendUint32(name.size());
145    expected_.AppendBytes(name);
146    expected_.AppendPrefix(kStringLiteralIdentityEncoded);
147    expected_.AppendUint32(value.size());
148    expected_.AppendBytes(value);
149  }
150  void CompareWithExpectedEncoding(const map<string, string>& header_set) {
151    string expected_out, actual_out;
152    expected_.TakeString(&expected_out);
153    EXPECT_TRUE(encoder_.EncodeHeaderSet(header_set, &actual_out));
154    EXPECT_EQ(expected_out, actual_out);
155  }
156  size_t IndexOf(HpackEntry* entry) {
157    return peer_.table()->IndexOf(entry);
158  }
159  size_t IndexOf(const HpackEntry* entry) {
160    return peer_.table()->IndexOf(entry);
161  }
162
163  HpackEncoder encoder_;
164  test::HpackEncoderPeer peer_;
165
166  const HpackEntry* static_;
167  const HpackEntry* key_1_;
168  const HpackEntry* key_2_;
169  const HpackEntry* cookie_a_;
170  const HpackEntry* cookie_c_;
171
172  HpackOutputStream expected_;
173};
174
175TEST_F(HpackEncoderTest, SingleDynamicIndex) {
176  ExpectIndex(IndexOf(key_2_));
177
178  map<string, string> headers;
179  headers[key_2_->name()] = key_2_->value();
180  CompareWithExpectedEncoding(headers);
181}
182
183TEST_F(HpackEncoderTest, SingleStaticIndex) {
184  ExpectIndex(IndexOf(static_));
185
186  map<string, string> headers;
187  headers[static_->name()] = static_->value();
188  CompareWithExpectedEncoding(headers);
189}
190
191TEST_F(HpackEncoderTest, SingleStaticIndexTooLarge) {
192  peer_.table()->SetMaxSize(1);  // Also evicts all fixtures.
193  ExpectIndex(IndexOf(static_));
194
195  map<string, string> headers;
196  headers[static_->name()] = static_->value();
197  CompareWithExpectedEncoding(headers);
198
199  EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
200}
201
202TEST_F(HpackEncoderTest, SingleLiteralWithIndexName) {
203  ExpectIndexedLiteral(key_2_, "value3");
204
205  map<string, string> headers;
206  headers[key_2_->name()] = "value3";
207  CompareWithExpectedEncoding(headers);
208
209  // A new entry was inserted and added to the reference set.
210  HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
211  EXPECT_EQ(new_entry->name(), key_2_->name());
212  EXPECT_EQ(new_entry->value(), "value3");
213}
214
215TEST_F(HpackEncoderTest, SingleLiteralWithLiteralName) {
216  ExpectIndexedLiteral("key3", "value3");
217
218  map<string, string> headers;
219  headers["key3"] = "value3";
220  CompareWithExpectedEncoding(headers);
221
222  HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
223  EXPECT_EQ(new_entry->name(), "key3");
224  EXPECT_EQ(new_entry->value(), "value3");
225}
226
227TEST_F(HpackEncoderTest, SingleLiteralTooLarge) {
228  peer_.table()->SetMaxSize(1);  // Also evicts all fixtures.
229
230  ExpectIndexedLiteral("key3", "value3");
231
232  // A header overflowing the header table is still emitted.
233  // The header table is empty.
234  map<string, string> headers;
235  headers["key3"] = "value3";
236  CompareWithExpectedEncoding(headers);
237
238  EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
239}
240
241TEST_F(HpackEncoderTest, EmitThanEvict) {
242  // |key_1_| is toggled and placed into the reference set,
243  // and then immediately evicted by "key3".
244  ExpectIndex(IndexOf(key_1_));
245  ExpectIndexedLiteral("key3", "value3");
246
247  map<string, string> headers;
248  headers[key_1_->name()] = key_1_->value();
249  headers["key3"] = "value3";
250  CompareWithExpectedEncoding(headers);
251}
252
253TEST_F(HpackEncoderTest, CookieHeaderIsCrumbled) {
254  ExpectIndex(IndexOf(cookie_a_));
255  ExpectIndex(IndexOf(cookie_c_));
256  ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
257
258  map<string, string> headers;
259  headers["cookie"] = "e=ff; a=bb; c=dd";
260  CompareWithExpectedEncoding(headers);
261}
262
263TEST_F(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) {
264  peer_.set_allow_huffman_compression(true);
265
266  // Compactable string. Uses Huffman coding.
267  peer_.EmitString("feedbeef");
268  expected_.AppendPrefix(kStringLiteralHuffmanEncoded);
269  expected_.AppendUint32(6);
270  expected_.AppendBytes("\x94\xA5\x92""2\x96_");
271
272  // Non-compactable. Uses identity coding.
273  peer_.EmitString("@@@@@@");
274  expected_.AppendPrefix(kStringLiteralIdentityEncoded);
275  expected_.AppendUint32(6);
276  expected_.AppendBytes("@@@@@@");
277
278  string expected_out, actual_out;
279  expected_.TakeString(&expected_out);
280  peer_.TakeString(&actual_out);
281  EXPECT_EQ(expected_out, actual_out);
282}
283
284TEST_F(HpackEncoderTest, EncodingWithoutCompression) {
285  // Implementation should internally disable.
286  peer_.set_allow_huffman_compression(true);
287
288  ExpectNonIndexedLiteral(":path", "/index.html");
289  ExpectNonIndexedLiteral("cookie", "foo=bar; baz=bing");
290  ExpectNonIndexedLiteral("hello", "goodbye");
291
292  map<string, string> headers;
293  headers[":path"] = "/index.html";
294  headers["cookie"] = "foo=bar; baz=bing";
295  headers["hello"] = "goodbye";
296
297  string expected_out, actual_out;
298  expected_.TakeString(&expected_out);
299  encoder_.EncodeHeaderSetWithoutCompression(headers, &actual_out);
300  EXPECT_EQ(expected_out, actual_out);
301}
302
303TEST_F(HpackEncoderTest, MultipleEncodingPasses) {
304  // Pass 1.
305  {
306    map<string, string> headers;
307    headers["key1"] = "value1";
308    headers["cookie"] = "a=bb";
309
310    ExpectIndex(IndexOf(cookie_a_));
311    ExpectIndex(IndexOf(key_1_));
312    CompareWithExpectedEncoding(headers);
313  }
314  // Header table is:
315  // 65: key1: value1
316  // 64: key2: value2
317  // 63: cookie: a=bb
318  // 62: cookie: c=dd
319  // Pass 2.
320  {
321    map<string, string> headers;
322    headers["key1"] = "value1";
323    headers["key2"] = "value2";
324    headers["cookie"] = "c=dd; e=ff";
325
326    ExpectIndex(IndexOf(cookie_c_));
327    // key1 by index.
328    ExpectIndex(65);
329    // key2 by index.
330    ExpectIndex(64);
331    // This cookie evicts |key1| from the header table.
332    ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
333
334    CompareWithExpectedEncoding(headers);
335  }
336  // Header table is:
337  // 65: key2: value2
338  // 64: cookie: a=bb
339  // 63: cookie: c=dd
340  // 62: cookie: e=ff
341  // Pass 3.
342  {
343    map<string, string> headers;
344    headers["key1"] = "value1";
345    headers["key3"] = "value3";
346    headers["cookie"] = "e=ff";
347
348    // cookie: e=ff by index.
349    ExpectIndex(62);
350    ExpectIndexedLiteral("key1", "value1");
351    ExpectIndexedLiteral("key3", "value3");
352
353    CompareWithExpectedEncoding(headers);
354  }
355}
356
357TEST_F(HpackEncoderTest, PseudoHeadersFirst) {
358  map<string, string> headers;
359  // A pseudo-header to be indexed.
360  headers[":authority"] = "www.example.com";
361  // A pseudo-header that should not be indexed.
362  headers[":path"] = "/spam/eggs.html";
363  // A regular header which precedes ":" alphabetically, should still be encoded
364  // after pseudo-headers.
365  headers["-foo"] = "bar";
366  headers["foo"] = "bar";
367  headers["cookie"] = "c=dd";
368
369  // Pseudo-headers are encoded in alphabetical order.
370  ExpectIndexedLiteral(peer_.table()->GetByName(":authority"),
371                       "www.example.com");
372  ExpectNonIndexedLiteral(":path", "/spam/eggs.html");
373  // Regular headers in the header table are encoded first.
374  ExpectIndex(IndexOf(cookie_a_));
375  // Regular headers not in the header table are encoded, in alphabetical order.
376  ExpectIndexedLiteral("-foo", "bar");
377  ExpectIndexedLiteral("foo", "bar");
378  CompareWithExpectedEncoding(headers);
379}
380
381TEST_F(HpackEncoderTest, CookieToCrumbs) {
382  test::HpackEncoderPeer peer(NULL);
383  std::vector<StringPiece> out;
384
385  // A space after ';' is consumed. All other spaces remain. ';' at beginning
386  // and end of string produce empty crumbs. Duplicate crumbs are removed.
387  // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2
388  // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11
389  peer.CookieToCrumbs(" foo=1;bar=2 ; bar=3;  bing=4; ", &out);
390  EXPECT_THAT(out, ElementsAre("", " bing=4", " foo=1", "bar=2 ", "bar=3"));
391
392  peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out);
393  EXPECT_THAT(out, ElementsAre("", "baz =bing", "foo = bar "));
394
395  peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out);
396  EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar"));
397
398  peer.CookieToCrumbs("baz=bing", &out);
399  EXPECT_THAT(out, ElementsAre("baz=bing"));
400
401  peer.CookieToCrumbs("", &out);
402  EXPECT_THAT(out, ElementsAre(""));
403
404  peer.CookieToCrumbs("foo;bar; baz;baz;bing;", &out);
405  EXPECT_THAT(out, ElementsAre("", "bar", "baz", "bing", "foo"));
406}
407
408TEST_F(HpackEncoderTest, UpdateCharacterCounts) {
409  std::vector<size_t> counts(256, 0);
410  size_t total_counts = 0;
411  encoder_.SetCharCountsStorage(&counts, &total_counts);
412
413  char kTestString[] = "foo\0\1\xff""boo";
414  peer_.UpdateCharacterCounts(
415      StringPiece(kTestString, arraysize(kTestString) - 1));
416
417  std::vector<size_t> expect(256, 0);
418  expect[static_cast<uint8>('f')] = 1;
419  expect[static_cast<uint8>('o')] = 4;
420  expect[static_cast<uint8>('\0')] = 1;
421  expect[static_cast<uint8>('\1')] = 1;
422  expect[static_cast<uint8>('\xff')] = 1;
423  expect[static_cast<uint8>('b')] = 1;
424
425  EXPECT_EQ(expect, counts);
426  EXPECT_EQ(9u, total_counts);
427}
428
429TEST_F(HpackEncoderTest, DecomposeRepresentation) {
430  test::HpackEncoderPeer peer(NULL);
431  std::vector<StringPiece> out;
432
433  peer.DecomposeRepresentation("", &out);
434  EXPECT_THAT(out, ElementsAre(""));
435
436  peer.DecomposeRepresentation("foobar", &out);
437  EXPECT_THAT(out, ElementsAre("foobar"));
438
439  peer.DecomposeRepresentation(StringPiece("foo\0bar", 7), &out);
440  EXPECT_THAT(out, ElementsAre("foo", "bar"));
441
442  peer.DecomposeRepresentation(StringPiece("\0foo\0bar", 8), &out);
443  EXPECT_THAT(out, ElementsAre("", "foo", "bar"));
444
445  peer.DecomposeRepresentation(StringPiece("foo\0bar\0", 8), &out);
446  EXPECT_THAT(out, ElementsAre("foo", "bar", ""));
447
448  peer.DecomposeRepresentation(StringPiece("\0foo\0bar\0", 9), &out);
449  EXPECT_THAT(out, ElementsAre("", "foo", "bar", ""));
450}
451
452// Test that encoded headers do not have \0-delimited multiple values, as this
453// became disallowed in HTTP/2 draft-14.
454TEST_F(HpackEncoderTest, CrumbleNullByteDelimitedValue) {
455  map<string, string> headers;
456  // A header field to be crumbled: "spam: foo\0bar".
457  headers["spam"] = string("foo\0bar", 7);
458
459  ExpectIndexedLiteral("spam", "foo");
460  expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
461  expected_.AppendUint32(62);
462  expected_.AppendPrefix(kStringLiteralIdentityEncoded);
463  expected_.AppendUint32(3);
464  expected_.AppendBytes("bar");
465  CompareWithExpectedEncoding(headers);
466}
467
468}  // namespace
469
470}  // namespace net
471