// Copyright (c) 2018 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 "quiche/quic/core/qpack/qpack_encoder.h"

#include <limits>
#include <string>

#include "absl/strings/escaping.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/string_view.h"
#include "quiche/quic/platform/api/quic_flags.h"
#include "quiche/quic/platform/api/quic_test.h"
#include "quiche/quic/test_tools/qpack/qpack_encoder_peer.h"
#include "quiche/quic/test_tools/qpack/qpack_test_utils.h"

using ::testing::_;
using ::testing::Eq;
using ::testing::Return;
using ::testing::StrictMock;

namespace quic {
namespace test {
namespace {

// A number larger than kMaxBytesBufferedByStream in
// qpack_encoder_stream_sender.cc.  Returning this value from NumBytesBuffered()
// will instruct QpackEncoder not to generate any instructions for the encoder
// stream.
constexpr uint64_t kTooManyBytesBuffered = 1024 * 1024;

// Mock QpackEncoder::DecoderStreamErrorDelegate implementation.
class MockDecoderStreamErrorDelegate
    : public QpackEncoder::DecoderStreamErrorDelegate {
 public:
  ~MockDecoderStreamErrorDelegate() override = default;

  MOCK_METHOD(void, OnDecoderStreamError,
              (QuicErrorCode error_code, absl::string_view error_message),
              (override));
};

class QpackEncoderTest : public QuicTestWithParam<bool> {
 protected:
  QpackEncoderTest()
      : encoder_(&decoder_stream_error_delegate_, HuffmanEncoding()),
        encoder_stream_sent_byte_count_(0) {
    encoder_.set_qpack_stream_sender_delegate(&encoder_stream_sender_delegate_);
    encoder_.SetMaximumBlockedStreams(1);
  }

  ~QpackEncoderTest() override = default;

  bool DisableHuffmanEncoding() { return GetParam(); }
  HuffmanEncoding HuffmanEncoding() {
    return DisableHuffmanEncoding() ? HuffmanEncoding::kDisabled
                                    : HuffmanEncoding::kEnabled;
  }

  std::string Encode(const spdy::Http2HeaderBlock& header_list) {
    return encoder_.EncodeHeaderList(/* stream_id = */ 1, header_list,
                                     &encoder_stream_sent_byte_count_);
  }

  StrictMock<MockDecoderStreamErrorDelegate> decoder_stream_error_delegate_;
  StrictMock<MockQpackStreamSenderDelegate> encoder_stream_sender_delegate_;
  QpackEncoder encoder_;
  QuicByteCount encoder_stream_sent_byte_count_;
};

INSTANTIATE_TEST_SUITE_P(DisableHuffmanEncoding, QpackEncoderTest,
                         testing::Values(false, true));

TEST_P(QpackEncoderTest, Empty) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  spdy::Http2HeaderBlock header_list;
  std::string output = Encode(header_list);

  EXPECT_EQ(absl::HexStringToBytes("0000"), output);
}

TEST_P(QpackEncoderTest, EmptyName) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  spdy::Http2HeaderBlock header_list;
  header_list[""] = "foo";
  std::string output = Encode(header_list);

  if (DisableHuffmanEncoding()) {
    EXPECT_EQ(absl::HexStringToBytes("00002003666f6f"), output);
  } else {
    EXPECT_EQ(absl::HexStringToBytes("0000208294e7"), output);
  }
}

TEST_P(QpackEncoderTest, EmptyValue) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  spdy::Http2HeaderBlock header_list;
  header_list["foo"] = "";
  std::string output = Encode(header_list);

  if (DisableHuffmanEncoding()) {
    EXPECT_EQ(absl::HexStringToBytes("000023666f6f00"), output);
  } else {
    EXPECT_EQ(absl::HexStringToBytes("00002a94e700"), output);
  }
}

TEST_P(QpackEncoderTest, EmptyNameAndValue) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  spdy::Http2HeaderBlock header_list;
  header_list[""] = "";
  std::string output = Encode(header_list);

  EXPECT_EQ(absl::HexStringToBytes("00002000"), output);
}

TEST_P(QpackEncoderTest, Simple) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  spdy::Http2HeaderBlock header_list;
  header_list["foo"] = "bar";
  std::string output = Encode(header_list);

  if (DisableHuffmanEncoding()) {
    EXPECT_EQ(absl::HexStringToBytes("000023666f6f03626172"), output);
  } else {
    EXPECT_EQ(absl::HexStringToBytes("00002a94e703626172"), output);
  }
}

TEST_P(QpackEncoderTest, Multiple) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  spdy::Http2HeaderBlock header_list;
  header_list["foo"] = "bar";
  // 'Z' would be Huffman encoded to 8 bits, so no Huffman encoding is used.
  header_list["ZZZZZZZ"] = std::string(127, 'Z');
  std::string output = Encode(header_list);

  std::string expected;
  if (DisableHuffmanEncoding()) {
    expected = absl::HexStringToBytes(
        "0000"                // prefix
        "23666f6f03626172");  // foo: bar
  } else {
    expected = absl::HexStringToBytes(
        "0000"              // prefix
        "2a94e703626172");  // foo: bar
  }
  expected += absl::HexStringToBytes(
      "27005a5a5a5a5a5a5a"  // 7 octet long header name, the smallest number
                            // that does not fit on a 3-bit prefix.
      "7f005a5a5a5a5a5a5a"  // 127 octet long header value, the smallest
      "5a5a5a5a5a5a5a5a5a"  // number that does not fit on a 7-bit prefix.
      "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a"
      "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a"
      "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a"
      "5a5a5a5a5a5a5a5a5a");
  EXPECT_EQ(expected, output);
}

TEST_P(QpackEncoderTest, StaticTable) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  {
    spdy::Http2HeaderBlock header_list;
    header_list[":method"] = "GET";
    header_list["accept-encoding"] = "gzip, deflate, br";
    header_list["location"] = "";

    std::string output = Encode(header_list);
    EXPECT_EQ(absl::HexStringToBytes("0000d1dfcc"), output);
  }
  {
    spdy::Http2HeaderBlock header_list;
    header_list[":method"] = "POST";
    header_list["accept-encoding"] = "compress";
    header_list["location"] = "foo";

    std::string output = Encode(header_list);
    if (DisableHuffmanEncoding()) {
      EXPECT_EQ(
          absl::HexStringToBytes("0000d45f1008636f6d70726573735c03666f6f"),
          output);
    } else {
      EXPECT_EQ(absl::HexStringToBytes("0000d45f108621e9aec2a11f5c8294e7"),
                output);
    }
  }
  {
    spdy::Http2HeaderBlock header_list;
    header_list[":method"] = "TRACE";
    header_list["accept-encoding"] = "";

    std::string output = Encode(header_list);
    EXPECT_EQ(absl::HexStringToBytes("00005f000554524143455f1000"), output);
  }
}

TEST_P(QpackEncoderTest, DecoderStreamError) {
  EXPECT_CALL(decoder_stream_error_delegate_,
              OnDecoderStreamError(QUIC_QPACK_DECODER_STREAM_INTEGER_TOO_LARGE,
                                   Eq("Encoded integer too large.")));

  QpackEncoder encoder(&decoder_stream_error_delegate_, HuffmanEncoding());
  encoder.set_qpack_stream_sender_delegate(&encoder_stream_sender_delegate_);
  encoder.decoder_stream_receiver()->Decode(
      absl::HexStringToBytes("ffffffffffffffffffffff"));
}

TEST_P(QpackEncoderTest, SplitAlongNullCharacter) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  spdy::Http2HeaderBlock header_list;
  header_list["foo"] = absl::string_view("bar\0bar\0baz", 11);
  std::string output = Encode(header_list);

  if (DisableHuffmanEncoding()) {
    EXPECT_EQ(absl::HexStringToBytes("0000"              // prefix
                                     "23666f6f03626172"  // foo: bar
                                     "23666f6f03626172"  // foo: bar
                                     "23666f6f0362617a"  // foo: bar
                                     ),
              output);
  } else {
    EXPECT_EQ(absl::HexStringToBytes("0000"            // prefix
                                     "2a94e703626172"  // foo: bar
                                     "2a94e703626172"  // foo: bar
                                     "2a94e70362617a"  // foo: baz
                                     ),
              output);
  }
}

TEST_P(QpackEncoderTest, ZeroInsertCountIncrement) {
  // Encoder receives insert count increment with forbidden value 0.
  EXPECT_CALL(
      decoder_stream_error_delegate_,
      OnDecoderStreamError(QUIC_QPACK_DECODER_STREAM_INVALID_ZERO_INCREMENT,
                           Eq("Invalid increment value 0.")));
  encoder_.OnInsertCountIncrement(0);
}

TEST_P(QpackEncoderTest, TooLargeInsertCountIncrement) {
  // Encoder receives insert count increment with value that increases Known
  // Received Count to a value (one) which is larger than the number of dynamic
  // table insertions sent (zero).
  EXPECT_CALL(
      decoder_stream_error_delegate_,
      OnDecoderStreamError(QUIC_QPACK_DECODER_STREAM_IMPOSSIBLE_INSERT_COUNT,
                           Eq("Increment value 1 raises known received count "
                              "to 1 exceeding inserted entry count 0")));
  encoder_.OnInsertCountIncrement(1);
}

// Regression test for https://crbug.com/1014372.
TEST_P(QpackEncoderTest, InsertCountIncrementOverflow) {
  QpackEncoderHeaderTable* header_table =
      QpackEncoderPeer::header_table(&encoder_);

  // Set dynamic table capacity large enough to hold one entry.
  header_table->SetMaximumDynamicTableCapacity(4096);
  header_table->SetDynamicTableCapacity(4096);
  // Insert one entry into the header table.
  header_table->InsertEntry("foo", "bar");

  // Receive Insert Count Increment instruction with increment value 1.
  encoder_.OnInsertCountIncrement(1);

  // Receive Insert Count Increment instruction that overflows the known
  // received count.  This must result in an error instead of a crash.
  EXPECT_CALL(decoder_stream_error_delegate_,
              OnDecoderStreamError(
                  QUIC_QPACK_DECODER_STREAM_INCREMENT_OVERFLOW,
                  Eq("Insert Count Increment instruction causes overflow.")));
  encoder_.OnInsertCountIncrement(std::numeric_limits<uint64_t>::max());
}

TEST_P(QpackEncoderTest, InvalidHeaderAcknowledgement) {
  // Encoder receives header acknowledgement for a stream on which no header
  // block with dynamic table entries was ever sent.
  EXPECT_CALL(
      decoder_stream_error_delegate_,
      OnDecoderStreamError(QUIC_QPACK_DECODER_STREAM_INCORRECT_ACKNOWLEDGEMENT,
                           Eq("Header Acknowledgement received for stream 0 "
                              "with no outstanding header blocks.")));
  encoder_.OnHeaderAcknowledgement(/* stream_id = */ 0);
}

TEST_P(QpackEncoderTest, DynamicTable) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  encoder_.SetMaximumBlockedStreams(1);
  encoder_.SetMaximumDynamicTableCapacity(4096);
  encoder_.SetDynamicTableCapacity(4096);

  spdy::Http2HeaderBlock header_list;
  header_list["foo"] = "bar";
  header_list.AppendValueOrAddHeader("foo",
                                     "baz");  // name matches dynamic entry
  header_list["cookie"] = "baz";              // name matches static entry

  // Set Dynamic Table Capacity instruction.
  std::string set_dyanamic_table_capacity = absl::HexStringToBytes("3fe11f");
  // Insert three entries into the dynamic table.
  std::string insert_entries;
  if (DisableHuffmanEncoding()) {
    insert_entries = absl::HexStringToBytes(
        "43"        // insert without name reference
        "666f6f");  // Huffman-encoded name "foo"
  } else {
    insert_entries = absl::HexStringToBytes(
        "62"      // insert without name reference
        "94e7");  // Huffman-encoded name "foo"
  }
  insert_entries += absl::HexStringToBytes(
      "03626172"    // value "bar"
      "80"          // insert with name reference, dynamic index 0
      "0362617a"    // value "baz"
      "c5"          // insert with name reference, static index 5
      "0362617a");  // value "baz"
  EXPECT_CALL(encoder_stream_sender_delegate_,
              WriteStreamData(Eq(
                  absl::StrCat(set_dyanamic_table_capacity, insert_entries))));

  EXPECT_EQ(absl::HexStringToBytes(
                "0400"      // prefix
                "828180"),  // dynamic entries with relative index 0, 1, and 2
            Encode(header_list));

  EXPECT_EQ(insert_entries.size(), encoder_stream_sent_byte_count_);
}

// There is no room in the dynamic table after inserting the first entry.
TEST_P(QpackEncoderTest, SmallDynamicTable) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  encoder_.SetMaximumBlockedStreams(1);
  encoder_.SetMaximumDynamicTableCapacity(QpackEntry::Size("foo", "bar"));
  encoder_.SetDynamicTableCapacity(QpackEntry::Size("foo", "bar"));

  spdy::Http2HeaderBlock header_list;
  header_list["foo"] = "bar";
  header_list.AppendValueOrAddHeader("foo",
                                     "baz");  // name matches dynamic entry
  header_list["cookie"] = "baz";              // name matches static entry
  header_list["bar"] = "baz";                 // no match

  // Set Dynamic Table Capacity instruction.
  std::string set_dyanamic_table_capacity = absl::HexStringToBytes("3f07");
  // Insert one entry into the dynamic table.
  std::string insert_entry;
  if (DisableHuffmanEncoding()) {
    insert_entry = absl::HexStringToBytes(
        "43"          // insert without name reference
        "666f6f"      // Huffman-encoded name "foo"
        "03626172");  // value "bar"
  } else {
    insert_entry = absl::HexStringToBytes(
        "62"          // insert without name reference
        "94e7"        // Huffman-encoded name "foo"
        "03626172");  // value "bar"
  }
  EXPECT_CALL(encoder_stream_sender_delegate_,
              WriteStreamData(
                  Eq(absl::StrCat(set_dyanamic_table_capacity, insert_entry))));

  EXPECT_EQ(absl::HexStringToBytes("0200"  // prefix
                                   "80"    // dynamic entry 0
                                   "40"    // reference to dynamic entry 0 name
                                   "0362617a"  // with literal value "baz"
                                   "55"  // reference to static entry 5 name
                                   "0362617a"    // with literal value "baz"
                                   "23626172"    // literal name "bar"
                                   "0362617a"),  // with literal value "baz"
            Encode(header_list));

  EXPECT_EQ(insert_entry.size(), encoder_stream_sent_byte_count_);
}

TEST_P(QpackEncoderTest, BlockedStream) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  encoder_.SetMaximumBlockedStreams(1);
  encoder_.SetMaximumDynamicTableCapacity(4096);
  encoder_.SetDynamicTableCapacity(4096);

  spdy::Http2HeaderBlock header_list1;
  header_list1["foo"] = "bar";

  // Set Dynamic Table Capacity instruction.
  std::string set_dyanamic_table_capacity = absl::HexStringToBytes("3fe11f");
  // Insert one entry into the dynamic table.
  std::string insert_entry1;
  if (DisableHuffmanEncoding()) {
    insert_entry1 = absl::HexStringToBytes(
        "43"          // insert without name reference
        "666f6f"      // Huffman-encoded name "foo"
        "03626172");  // value "bar"
  } else {
    insert_entry1 = absl::HexStringToBytes(
        "62"          // insert without name reference
        "94e7"        // Huffman-encoded name "foo"
        "03626172");  // value "bar"
  }
  EXPECT_CALL(encoder_stream_sender_delegate_,
              WriteStreamData(Eq(
                  absl::StrCat(set_dyanamic_table_capacity, insert_entry1))));

  EXPECT_EQ(absl::HexStringToBytes("0200"  // prefix
                                   "80"),  // dynamic entry 0
            encoder_.EncodeHeaderList(/* stream_id = */ 1, header_list1,
                                      &encoder_stream_sent_byte_count_));
  EXPECT_EQ(insert_entry1.size(), encoder_stream_sent_byte_count_);

  // Stream 1 is blocked.  Stream 2 is not allowed to block.
  spdy::Http2HeaderBlock header_list2;
  header_list2["foo"] = "bar";  // name and value match dynamic entry
  header_list2.AppendValueOrAddHeader("foo",
                                      "baz");  // name matches dynamic entry
  header_list2["cookie"] = "baz";              // name matches static entry
  header_list2["bar"] = "baz";                 // no match

  std::string entries;
  if (DisableHuffmanEncoding()) {
    entries = absl::HexStringToBytes(
        "0000"        // prefix
        "23666f6f"    // literal name "foo"
        "03626172"    // with literal value "bar"
        "23666f6f"    // literal name "foo"
        "0362617a"    // with literal value "baz"
        "55"          // name of static entry 5
        "0362617a"    // with literal value "baz"
        "23626172"    // literal name "bar"
        "0362617a");  // with literal value "baz"
  } else {
    entries = absl::HexStringToBytes(
        "0000"        // prefix
        "2a94e7"      // literal name "foo"
        "03626172"    // with literal value "bar"
        "2a94e7"      // literal name "foo"
        "0362617a"    // with literal value "baz"
        "55"          // name of static entry 5
        "0362617a"    // with literal value "baz"
        "23626172"    // literal name "bar"
        "0362617a");  // with literal value "baz"
  }
  EXPECT_EQ(entries,
            encoder_.EncodeHeaderList(/* stream_id = */ 2, header_list2,
                                      &encoder_stream_sent_byte_count_));
  EXPECT_EQ(0u, encoder_stream_sent_byte_count_);

  // Peer acknowledges receipt of one dynamic table entry.
  // Stream 1 is no longer blocked.
  encoder_.OnInsertCountIncrement(1);

  // Insert three entries into the dynamic table.
  std::string insert_entries = absl::HexStringToBytes(
      "80"          // insert with name reference, dynamic index 0
      "0362617a"    // value "baz"
      "c5"          // insert with name reference, static index 5
      "0362617a"    // value "baz"
      "43"          // insert without name reference
      "626172"      // name "bar"
      "0362617a");  // value "baz"
  EXPECT_CALL(encoder_stream_sender_delegate_,
              WriteStreamData(Eq(insert_entries)));

  EXPECT_EQ(absl::HexStringToBytes("0500"        // prefix
                                   "83828180"),  // dynamic entries
            encoder_.EncodeHeaderList(/* stream_id = */ 3, header_list2,
                                      &encoder_stream_sent_byte_count_));
  EXPECT_EQ(insert_entries.size(), encoder_stream_sent_byte_count_);

  // Stream 3 is blocked.  Stream 4 is not allowed to block, but it can
  // reference already acknowledged dynamic entry 0.
  std::string expected2;
  if (DisableHuffmanEncoding()) {
    expected2 = absl::HexStringToBytes(
        "0200"            // prefix
        "80"              // dynamic entry 0
        "23666f6f"        // literal name "foo"
        "0362617a"        // with literal value "baz"
        "26636f6f6b6965"  // literal name "cookie"
        "0362617a"        // with literal value "baz"
        "23626172"        // literal name "bar"
        "0362617a");      // with literal value "baz"
  } else {
    expected2 = absl::HexStringToBytes(
        "0200"        // prefix
        "80"          // dynamic entry 0
        "2a94e7"      // literal name "foo"
        "0362617a"    // with literal value "baz"
        "2c21cfd4c5"  // literal name "cookie"
        "0362617a"    // with literal value "baz"
        "23626172"    // literal name "bar"
        "0362617a");  // with literal value "baz"
  }
  EXPECT_EQ(expected2,
            encoder_.EncodeHeaderList(/* stream_id = */ 4, header_list2,
                                      &encoder_stream_sent_byte_count_));
  EXPECT_EQ(0u, encoder_stream_sent_byte_count_);

  // Peer acknowledges receipt of two more dynamic table entries.
  // Stream 3 is still blocked.
  encoder_.OnInsertCountIncrement(2);

  // Stream 5 is not allowed to block, but it can reference already acknowledged
  // dynamic entries 0, 1, and 2.
  EXPECT_EQ(absl::HexStringToBytes("0400"        // prefix
                                   "828180"      // dynamic entries
                                   "23626172"    // literal name "bar"
                                   "0362617a"),  // with literal value "baz"
            encoder_.EncodeHeaderList(/* stream_id = */ 5, header_list2,
                                      &encoder_stream_sent_byte_count_));
  EXPECT_EQ(0u, encoder_stream_sent_byte_count_);

  // Peer acknowledges decoding header block on stream 3.
  // Stream 3 is not blocked any longer.
  encoder_.OnHeaderAcknowledgement(3);

  EXPECT_EQ(absl::HexStringToBytes("0500"        // prefix
                                   "83828180"),  // dynamic entries
            encoder_.EncodeHeaderList(/* stream_id = */ 6, header_list2,
                                      &encoder_stream_sent_byte_count_));
  EXPECT_EQ(0u, encoder_stream_sent_byte_count_);
}

TEST_P(QpackEncoderTest, Draining) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  spdy::Http2HeaderBlock header_list1;
  header_list1["one"] = "foo";
  header_list1["two"] = "foo";
  header_list1["three"] = "foo";
  header_list1["four"] = "foo";
  header_list1["five"] = "foo";
  header_list1["six"] = "foo";
  header_list1["seven"] = "foo";
  header_list1["eight"] = "foo";
  header_list1["nine"] = "foo";
  header_list1["ten"] = "foo";

  // Make just enough room in the dynamic table for the header list plus the
  // first entry duplicated.  This will ensure that the oldest entries are
  // draining.
  uint64_t maximum_dynamic_table_capacity = 0;
  for (const auto& header_field : header_list1) {
    maximum_dynamic_table_capacity +=
        QpackEntry::Size(header_field.first, header_field.second);
  }
  maximum_dynamic_table_capacity += QpackEntry::Size("one", "foo");
  encoder_.SetMaximumDynamicTableCapacity(maximum_dynamic_table_capacity);
  encoder_.SetDynamicTableCapacity(maximum_dynamic_table_capacity);

  // Set Dynamic Table Capacity instruction and insert ten entries into the
  // dynamic table.
  EXPECT_CALL(encoder_stream_sender_delegate_, WriteStreamData(_));

  EXPECT_EQ(absl::HexStringToBytes("0b00"                    // prefix
                                   "89888786858483828180"),  // dynamic entries
            Encode(header_list1));

  // Entry is identical to oldest one, which is draining.  It will be
  // duplicated and referenced.
  spdy::Http2HeaderBlock header_list2;
  header_list2["one"] = "foo";

  // Duplicate oldest entry.
  EXPECT_CALL(encoder_stream_sender_delegate_,
              WriteStreamData(Eq(absl::HexStringToBytes("09"))));

  EXPECT_EQ(absl::HexStringToBytes("0c00"  // prefix
                                   "80"),  // most recent dynamic table entry
            Encode(header_list2));

  spdy::Http2HeaderBlock header_list3;
  // Entry is identical to second oldest one, which is draining.  There is no
  // room to duplicate, it will be encoded with string literals.
  header_list3.AppendValueOrAddHeader("two", "foo");
  // Entry has name identical to second oldest one, which is draining.  There is
  // no room to insert new entry, it will be encoded with string literals.
  header_list3.AppendValueOrAddHeader("two", "bar");

  std::string entries =
      "0000"       // prefix
      "2374776f";  // literal name "two"
  if (DisableHuffmanEncoding()) {
    entries += "03666f6f";  // literal name "foo"
  } else {
    entries += "8294e7";  // literal value "foo"
  }
  entries +=
      "2374776f"   // literal name "two"
      "03626172";  // literal value "bar"
  EXPECT_EQ(absl::HexStringToBytes(entries), Encode(header_list3));
}

TEST_P(QpackEncoderTest, DynamicTableCapacityLessThanMaximum) {
  encoder_.SetMaximumDynamicTableCapacity(1024);
  encoder_.SetDynamicTableCapacity(30);

  QpackEncoderHeaderTable* header_table =
      QpackEncoderPeer::header_table(&encoder_);

  EXPECT_EQ(1024u, header_table->maximum_dynamic_table_capacity());
  EXPECT_EQ(30u, header_table->dynamic_table_capacity());
}

TEST_P(QpackEncoderTest, EncoderStreamWritesDisallowedThenAllowed) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(kTooManyBytesBuffered));
  encoder_.SetMaximumBlockedStreams(1);
  encoder_.SetMaximumDynamicTableCapacity(4096);
  encoder_.SetDynamicTableCapacity(4096);

  spdy::Http2HeaderBlock header_list1;
  header_list1["foo"] = "bar";
  header_list1.AppendValueOrAddHeader("foo", "baz");
  header_list1["cookie"] = "baz";  // name matches static entry

  // Encoder is not allowed to write on the encoder stream.
  // No Set Dynamic Table Capacity or Insert instructions are sent.
  // Headers are encoded as string literals.
  std::string entries;
  if (DisableHuffmanEncoding()) {
    entries = absl::HexStringToBytes(
        "0000"        // prefix
        "23666f6f"    // literal name "foo"
        "03626172"    // with literal value "bar"
        "23666f6f"    // literal name "foo"
        "0362617a"    // with literal value "baz"
        "55"          // name of static entry 5
        "0362617a");  // with literal value "baz"
  } else {
    entries = absl::HexStringToBytes(
        "0000"        // prefix
        "2a94e7"      // literal name "foo"
        "03626172"    // with literal value "bar"
        "2a94e7"      // literal name "foo"
        "0362617a"    // with literal value "baz"
        "55"          // name of static entry 5
        "0362617a");  // with literal value "baz"
  }
  EXPECT_EQ(entries, Encode(header_list1));

  EXPECT_EQ(0u, encoder_stream_sent_byte_count_);

  // If number of bytes buffered by encoder stream goes under the threshold,
  // then QpackEncoder will resume emitting encoder stream instructions.
  ::testing::Mock::VerifyAndClearExpectations(&encoder_stream_sender_delegate_);
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));

  spdy::Http2HeaderBlock header_list2;
  header_list2["foo"] = "bar";
  header_list2.AppendValueOrAddHeader("foo",
                                      "baz");  // name matches dynamic entry
  header_list2["cookie"] = "baz";              // name matches static entry

  // Set Dynamic Table Capacity instruction.
  std::string set_dyanamic_table_capacity = absl::HexStringToBytes("3fe11f");
  // Insert three entries into the dynamic table.
  std::string insert_entries;
  if (DisableHuffmanEncoding()) {
    insert_entries = absl::HexStringToBytes(
        "43"        // insert without name reference
        "666f6f");  // name "foo"
  } else {
    insert_entries = absl::HexStringToBytes(
        "62"      // insert without name reference
        "94e7");  // Huffman-encoded name "foo"
  }
  insert_entries += absl::HexStringToBytes(
      "03626172"    // value "bar"
      "80"          // insert with name reference, dynamic index 0
      "0362617a"    // value "baz"
      "c5"          // insert with name reference, static index 5
      "0362617a");  // value "baz"
  EXPECT_CALL(encoder_stream_sender_delegate_,
              WriteStreamData(Eq(
                  absl::StrCat(set_dyanamic_table_capacity, insert_entries))));

  EXPECT_EQ(absl::HexStringToBytes(
                "0400"      // prefix
                "828180"),  // dynamic entries with relative index 0, 1, and 2
            Encode(header_list2));

  EXPECT_EQ(insert_entries.size(), encoder_stream_sent_byte_count_);
}

TEST_P(QpackEncoderTest, EncoderStreamWritesAllowedThenDisallowed) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  encoder_.SetMaximumBlockedStreams(1);
  encoder_.SetMaximumDynamicTableCapacity(4096);
  encoder_.SetDynamicTableCapacity(4096);

  spdy::Http2HeaderBlock header_list1;
  header_list1["foo"] = "bar";
  header_list1.AppendValueOrAddHeader("foo",
                                      "baz");  // name matches dynamic entry
  header_list1["cookie"] = "baz";              // name matches static entry

  // Set Dynamic Table Capacity instruction.
  std::string set_dyanamic_table_capacity = absl::HexStringToBytes("3fe11f");
  // Insert three entries into the dynamic table.
  std::string insert_entries;
  if (DisableHuffmanEncoding()) {
    insert_entries = absl::HexStringToBytes(
        "43"        // insert without name reference
        "666f6f");  // name "foo"
  } else {
    insert_entries = absl::HexStringToBytes(
        "62"      // insert without name reference
        "94e7");  // Huffman-encoded name "foo"
  }
  insert_entries += absl::HexStringToBytes(
      "03626172"    // value "bar"
      "80"          // insert with name reference, dynamic index 0
      "0362617a"    // value "baz"
      "c5"          // insert with name reference, static index 5
      "0362617a");  // value "baz"
  EXPECT_CALL(encoder_stream_sender_delegate_,
              WriteStreamData(Eq(
                  absl::StrCat(set_dyanamic_table_capacity, insert_entries))));

  EXPECT_EQ(absl::HexStringToBytes(
                "0400"      // prefix
                "828180"),  // dynamic entries with relative index 0, 1, and 2
            Encode(header_list1));

  EXPECT_EQ(insert_entries.size(), encoder_stream_sent_byte_count_);

  // If number of bytes buffered by encoder stream goes over the threshold,
  // then QpackEncoder will stop emitting encoder stream instructions.
  ::testing::Mock::VerifyAndClearExpectations(&encoder_stream_sender_delegate_);
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(kTooManyBytesBuffered));

  spdy::Http2HeaderBlock header_list2;
  header_list2["foo"] = "bar";  // matches previously inserted dynamic entry
  header_list2["bar"] = "baz";
  header_list2["cookie"] = "baz";  // name matches static entry

  // Encoder is not allowed to write on the encoder stream.
  // No Set Dynamic Table Capacity or Insert instructions are sent.
  // Headers are encoded as string literals.
  EXPECT_EQ(
      absl::HexStringToBytes("0400"      // prefix
                             "82"        // dynamic entry with relative index 0
                             "23626172"  // literal name "bar"
                             "0362617a"  // with literal value "baz"
                             "80"),      // dynamic entry with relative index 2
      Encode(header_list2));

  EXPECT_EQ(0u, encoder_stream_sent_byte_count_);
}

// Regression test for https://crbug.com/1441880.
TEST_P(QpackEncoderTest, UnackedEntryCannotBeEvicted) {
  EXPECT_CALL(encoder_stream_sender_delegate_, NumBytesBuffered())
      .WillRepeatedly(Return(0));
  encoder_.SetMaximumBlockedStreams(2);
  // With 32 byte overhead per entry, only one entry fits in the dynamic table.
  encoder_.SetMaximumDynamicTableCapacity(40);
  encoder_.SetDynamicTableCapacity(40);

  QpackEncoderHeaderTable* header_table =
      QpackEncoderPeer::header_table(&encoder_);
  EXPECT_EQ(0u, header_table->inserted_entry_count());
  EXPECT_EQ(0u, header_table->dropped_entry_count());

  spdy::Http2HeaderBlock header_list1;
  header_list1["foo"] = "bar";

  // Set Dynamic Table Capacity instruction.
  std::string set_dyanamic_table_capacity = absl::HexStringToBytes("3f09");
  // Insert one entry into the dynamic table.
  std::string insert_entries1;
  if (DisableHuffmanEncoding()) {
    insert_entries1 = absl::HexStringToBytes(
        "43"          // insert without name reference
        "666f6f"      // Huffman-encoded name "foo"
        "03626172");  // value "bar"
  } else {
    insert_entries1 = absl::HexStringToBytes(
        "62"          // insert without name reference
        "94e7"        // Huffman-encoded name "foo"
        "03626172");  // value "bar"
  }
  EXPECT_CALL(encoder_stream_sender_delegate_,
              WriteStreamData(Eq(
                  absl::StrCat(set_dyanamic_table_capacity, insert_entries1))));

  EXPECT_EQ(
      absl::HexStringToBytes("0200"  // prefix
                             "80"),  // dynamic entry with relative index 0
      encoder_.EncodeHeaderList(/* stream_id = */ 1, header_list1,
                                &encoder_stream_sent_byte_count_));

  EXPECT_EQ(1u, header_table->inserted_entry_count());
  EXPECT_EQ(0u, header_table->dropped_entry_count());

  encoder_.OnStreamCancellation(/* stream_id = */ 1);

  // At this point, entry 0 has no references to it, because stream 1 is
  // cancelled.  However, this entry is unacknowledged, therefore it must not be
  // evicted according to RFC 9204 Section 2.1.1.

  spdy::Http2HeaderBlock header_list2;
  header_list2["bar"] = "baz";

  EXPECT_EQ(absl::HexStringToBytes("0000"        // prefix
                                   "23626172"    // literal name "bar"
                                   "0362617a"),  // literal value "baz"
            encoder_.EncodeHeaderList(/* stream_id = */ 2, header_list2,
                                      &encoder_stream_sent_byte_count_));

  EXPECT_EQ(1u, header_table->inserted_entry_count());
  EXPECT_EQ(0u, header_table->dropped_entry_count());
}

}  // namespace
}  // namespace test
}  // namespace quic