path: root/icing/index/main/posting-list-hit-serializer_test.cc

// Copyright (C) 2022 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "icing/index/main/posting-list-hit-serializer.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <deque>
#include <iterator>
#include <limits>
#include <vector>

#include "icing/text_classifier/lib3/utils/base/status.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "icing/file/posting_list/posting-list-used.h"
#include "icing/index/hit/hit.h"
#include "icing/legacy/index/icing-bit-util.h"
#include "icing/schema/section.h"
#include "icing/store/document-id.h"
#include "icing/testing/common-matchers.h"
#include "icing/testing/hit-test-utils.h"

using testing::ElementsAre;
using testing::ElementsAreArray;
using testing::Eq;
using testing::Gt;
using testing::IsEmpty;
using testing::IsFalse;
using testing::IsTrue;
using testing::Le;
using testing::Lt;

namespace icing {
namespace lib {

namespace {

struct HitElt {
  HitElt() = default;
  explicit HitElt(const Hit &hit_in) : hit(hit_in) {}

  static Hit get_hit(const HitElt &hit_elt) { return hit_elt.hit; }

  Hit hit;
};

TEST(PostingListHitSerializerTest, PostingListUsedPrependHitNotFull) {
  PostingListHitSerializer serializer;

  static const int kNumHits = 2551;
  static const size_t kHitsSize = kNumHits * sizeof(Hit);

  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, kHitsSize));

  // Make used.
  Hit hit0(/*section_id=*/0, /*document_id=*/0, /*term_frequency=*/56,
           /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit0));
  // Size = sizeof(uncompressed hit0::Value)
  //        + sizeof(hit0::Flags)
  //        + sizeof(hit0::TermFrequency)
  int expected_size =
      sizeof(Hit::Value) + sizeof(Hit::Flags) + sizeof(Hit::TermFrequency);
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used), IsOkAndHolds(ElementsAre(hit0)));

  Hit hit1(/*section_id=*/0, /*document_id=*/1, Hit::kDefaultTermFrequency,
           /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  uint8_t delta_buf[VarInt::kMaxEncodedLen64];
  size_t delta_len = PostingListHitSerializer::EncodeNextHitValue(
      /*next_hit_value=*/hit1.value(),
      /*curr_hit_value=*/hit0.value(), delta_buf);
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit1));
  // Size = sizeof(uncompressed hit1::Value)
  //        + sizeof(hit0-hit1)
  //        + sizeof(hit0::Flags)
  //        + sizeof(hit0::TermFrequency)
  expected_size += delta_len;
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit1, hit0)));

  Hit hit2(/*section_id=*/0, /*document_id=*/2, /*term_frequency=*/56,
           /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  delta_len = PostingListHitSerializer::EncodeNextHitValue(
      /*next_hit_value=*/hit2.value(),
      /*curr_hit_value=*/hit1.value(), delta_buf);
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit2));
  // Size = sizeof(uncompressed hit2::Value) + sizeof(hit2::Flags)
  //        + sizeof(hit2::TermFrequency)
  //        + sizeof(hit1-hit2)
  //        + sizeof(hit0-hit1)
  //        + sizeof(hit0::flags)
  //        + sizeof(hit0::term_frequency)
  expected_size += delta_len + sizeof(Hit::Flags) + sizeof(Hit::TermFrequency);
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit2, hit1, hit0)));

  Hit hit3(/*section_id=*/0, /*document_id=*/3, Hit::kDefaultTermFrequency,
           /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  delta_len = PostingListHitSerializer::EncodeNextHitValue(
      /*next_hit_value=*/hit3.value(),
      /*curr_hit_value=*/hit2.value(), delta_buf);
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit3));
  // Size = sizeof(uncompressed hit3::Value)
  //        + sizeof(hit2-hit3) + sizeof(hit2::Flags)
  //        + sizeof(hit2::TermFrequency)
  //        + sizeof(hit1-hit2)
  //        + sizeof(hit0-hit1)
  //        + sizeof(hit0::flags)
  //        + sizeof(hit0::term_frequency)
  expected_size += delta_len;
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit3, hit2, hit1, hit0)));
}

TEST(PostingListHitSerializerTest,
     PostingListUsedPrependHitAlmostFull_withFlags) {
  PostingListHitSerializer serializer;

  // Size = 24
  int pl_size = 2 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  // Fill up the compressed region.
  // Transitions:
  // Adding hit0: EMPTY -> NOT_FULL
  // Adding hit1: NOT_FULL -> NOT_FULL
  // Adding hit2: NOT_FULL -> NOT_FULL
  Hit hit0(/*section_id=*/0, /*document_id=*/0, Hit::kDefaultTermFrequency,
           /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  Hit hit1 = CreateHit(hit0, /*desired_byte_length=*/3);
  Hit hit2 = CreateHit(hit1, /*desired_byte_length=*/2, /*term_frequency=*/57,
                       /*is_in_prefix_section=*/true,
                       /*is_prefix_hit=*/true);
  EXPECT_THAT(hit2.has_flags(), IsTrue());
  EXPECT_THAT(hit2.has_term_frequency(), IsTrue());
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit0));
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit1));
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit2));
  // Size used will be 4 (hit2::Value) + 1 (hit2::Flags) + 1
  // (hit2::TermFrequency) + 2 (hit1-hit2) + 3 (hit0-hit1) = 11 bytes
  int expected_size = sizeof(Hit::Value) + sizeof(Hit::Flags) +
                      sizeof(Hit::TermFrequency) + 2 + 3;
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit2, hit1, hit0)));

  // Add one more hit to transition NOT_FULL -> ALMOST_FULL
  Hit hit3 =
      CreateHit(hit2, /*desired_byte_length=*/3, Hit::kDefaultTermFrequency,
                /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  EXPECT_THAT(hit3.has_flags(), IsFalse());
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit3));
  // Storing them in the compressed region requires 4 (hit3::Value) + 3
  // (hit2-hit3) + 1 (hit2::Flags) + 1 (hit2::TermFrequency) + 2 (hit1-hit2) + 3
  // (hit0-hit1) = 14 bytes, but there are only 12 bytes in the compressed
  // region. So instead, the posting list will transition to ALMOST_FULL.
  // The in-use compressed region will actually shrink from 11 bytes to 10 bytes
  // because the uncompressed version of hit2 will be overwritten with the
  // compressed delta of hit2. hit3 will be written to one of the special hits.
  // Because we're in ALMOST_FULL, the expected size is the size of the pl minus
  // the one hit used to mark the posting list as ALMOST_FULL.
  expected_size = pl_size - sizeof(Hit);
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit3, hit2, hit1, hit0)));

  // Add one more hit to transition ALMOST_FULL -> ALMOST_FULL
  Hit hit4 = CreateHit(hit3, /*desired_byte_length=*/2);
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit4));
  // There are currently 10 bytes in use in the compressed region. hit3 will
  // have a 2-byte delta, which fits in the compressed region. Hit3 will be
  // moved from the special hit to the compressed region (which will have 12
  // bytes in use after adding hit3). Hit4 will be placed in one of the special
  // hits and the posting list will remain in ALMOST_FULL.
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit4, hit3, hit2, hit1, hit0)));

  // Add one more hit to transition ALMOST_FULL -> FULL
  Hit hit5 = CreateHit(hit4, /*desired_byte_length=*/2);
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit5));
  // There are currently 12 bytes in use in the compressed region. hit4 will
  // have a 2-byte delta which will not fit in the compressed region. So hit4
  // will remain in one of the special hits and hit5 will occupy the other,
  // making the posting list FULL.
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(pl_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit5, hit4, hit3, hit2, hit1, hit0)));

  // The posting list is FULL. Adding another hit should fail.
  Hit hit6 = CreateHit(hit5, /*desired_byte_length=*/1);
  EXPECT_THAT(serializer.PrependHit(&pl_used, hit6),
              StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));
}

TEST(PostingListHitSerializerTest, PostingListUsedPrependHitAlmostFull) {
  PostingListHitSerializer serializer;

  // Size = 24
  int pl_size = 2 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  // Fill up the compressed region.
  // Transitions:
  // Adding hit0: EMPTY -> NOT_FULL
  // Adding hit1: NOT_FULL -> NOT_FULL
  // Adding hit2: NOT_FULL -> NOT_FULL
  Hit hit0(/*section_id=*/0, /*document_id=*/0, Hit::kDefaultTermFrequency,
           /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  Hit hit1 = CreateHit(hit0, /*desired_byte_length=*/3);
  Hit hit2 = CreateHit(hit1, /*desired_byte_length=*/3);
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit0));
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit1));
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit2));
  // Size used will be 4 (hit2::Value) + 3 (hit1-hit2) + 3 (hit0-hit1)
  // = 10 bytes
  int expected_size = sizeof(Hit::Value) + 3 + 3;
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit2, hit1, hit0)));

  // Add one more hit to transition NOT_FULL -> ALMOST_FULL
  Hit hit3 = CreateHit(hit2, /*desired_byte_length=*/3);
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit3));
  // Storing them in the compressed region requires 4 (hit3::Value) + 3
  // (hit2-hit3) + 3 (hit1-hit2) + 3 (hit0-hit1) = 13 bytes, but there are only
  // 12 bytes in the compressed region. So instead, the posting list will
  // transition to ALMOST_FULL.
  // The in-use compressed region will actually shrink from 10 bytes to 9 bytes
  // because the uncompressed version of hit2 will be overwritten with the
  // compressed delta of hit2. hit3 will be written to one of the special hits.
  // Because we're in ALMOST_FULL, the expected size is the size of the pl minus
  // the one hit used to mark the posting list as ALMOST_FULL.
  expected_size = pl_size - sizeof(Hit);
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit3, hit2, hit1, hit0)));

  // Add one more hit to transition ALMOST_FULL -> ALMOST_FULL
  Hit hit4 = CreateHit(hit3, /*desired_byte_length=*/2);
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit4));
  // There are currently 9 bytes in use in the compressed region. Hit3 will
  // have a 2-byte delta, which fits in the compressed region. Hit3 will be
  // moved from the special hit to the compressed region (which will have 11
  // bytes in use after adding hit3). Hit4 will be placed in one of the special
  // hits and the posting list will remain in ALMOST_FULL.
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit4, hit3, hit2, hit1, hit0)));

  // Add one more hit to transition ALMOST_FULL -> FULL
  Hit hit5 = CreateHit(hit4, /*desired_byte_length=*/2);
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit5));
  // There are currently 11 bytes in use in the compressed region. Hit4 will
  // have a 2-byte delta which will not fit in the compressed region. So hit4
  // will remain in one of the special hits and hit5 will occupy the other,
  // making the posting list FULL.
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(pl_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit5, hit4, hit3, hit2, hit1, hit0)));

  // The posting list is FULL. Adding another hit should fail.
  Hit hit6 = CreateHit(hit5, /*desired_byte_length=*/1);
  EXPECT_THAT(serializer.PrependHit(&pl_used, hit6),
              StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));
}

TEST(PostingListHitSerializerTest, PrependHitsWithSameValue) {
  PostingListHitSerializer serializer;

  // Size = 24
  int pl_size = 2 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  // Fill up the compressed region.
  Hit hit0(/*section_id=*/0, /*document_id=*/0, Hit::kDefaultTermFrequency,
           /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  Hit hit1 = CreateHit(hit0, /*desired_byte_length=*/3);
  Hit hit2 = CreateHit(hit1, /*desired_byte_length=*/2, /*term_frequency=*/57,
                       /*is_in_prefix_section=*/true,
                       /*is_prefix_hit=*/true);
  // Create hit3 with the same value but different flags as hit2 (hit3_flags
  // is set to have all currently-defined flags enabled)
  Hit::Flags hit3_flags = 0;
  for (int i = 0; i < Hit::kNumFlagsInFlagsField; ++i) {
    hit3_flags |= (1 << i);
  }
  Hit hit3(hit2.value(), /*term_frequency=*/hit2.term_frequency(),
           /*flags=*/hit3_flags);

  // hit3 is larger than hit2 (its flag value is larger), and so needs to be
  // prepended first
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit0));
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit1));
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit3));
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit2));
  // Posting list is now ALMOST_FULL
  // ----------------------
  // 23-21     delta(Hit #0)
  // 20-19     delta(Hit #1)
  // 18        term-frequency(Hit #2)
  // 17        flags(Hit #2)
  // 16        delta(Hit #2) = 0
  // 15-12     <unused padding = 0>
  // 11-6      Hit #3
  // 5-0       kSpecialHit
  // ----------------------
  int bytes_used = pl_size - sizeof(Hit);

  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(bytes_used));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit2, hit3, hit1, hit0)));
}

TEST(PostingListHitSerializerTest, PostingListUsedMinSize) {
  PostingListHitSerializer serializer;

  // Min size = 12
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(
          &serializer, serializer.GetMinPostingListSize()));
  // PL State: EMPTY
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(0));
  EXPECT_THAT(serializer.GetHits(&pl_used), IsOkAndHolds(IsEmpty()));

  // Add a hit, PL should shift to ALMOST_FULL state
  Hit hit0(/*section_id=*/1, /*document_id=*/0, /*term_frequency=*/0,
           /*is_in_prefix_section=*/false,
           /*is_prefix_hit=*/true);
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit0));
  // Size = sizeof(uncompressed hit0)
  int expected_size = sizeof(Hit);
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Le(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used), IsOkAndHolds(ElementsAre(hit0)));

  // Add the smallest hit possible - no term_frequency, non-prefix hit and a
  // delta of 0b10. PL should shift to FULL state.
  Hit hit1(/*section_id=*/0, /*document_id=*/0, /*term_frequency=*/0,
           /*is_in_prefix_section=*/false,
           /*is_prefix_hit=*/false);
  ICING_EXPECT_OK(serializer.PrependHit(&pl_used, hit1));
  // Size = sizeof(uncompressed hit1) + sizeof(uncompressed hit0)
  expected_size += sizeof(Hit);
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Le(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit1, hit0)));

  // Try to add the smallest hit possible. Should fail
  Hit hit2(/*section_id=*/0, /*document_id=*/0, /*term_frequency=*/0,
           /*is_in_prefix_section=*/false,
           /*is_prefix_hit=*/false);
  EXPECT_THAT(serializer.PrependHit(&pl_used, hit2),
              StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Le(expected_size));
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAre(hit1, hit0)));
}

TEST(PostingListHitSerializerTest,
     PostingListPrependHitArrayMinSizePostingList) {
  PostingListHitSerializer serializer;

  // Min Size = 12
  int pl_size = serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  std::vector<HitElt> hits_in;
  hits_in.emplace_back(Hit(/*section_id=*/1, /*document_id=*/0,
                           Hit::kDefaultTermFrequency,
                           /*is_in_prefix_section=*/false,
                           /*is_prefix_hit=*/false));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  std::reverse(hits_in.begin(), hits_in.end());

  // Add five hits. The PL is in the empty state and an empty min size PL can
  // only fit two hits. So PrependHitArray should fail.
  ICING_ASSERT_OK_AND_ASSIGN(
      uint32_t num_can_prepend,
      (serializer.PrependHitArray<HitElt, HitElt::get_hit>(
          &pl_used, &hits_in[0], hits_in.size(), /*keep_prepended=*/false)));
  EXPECT_THAT(num_can_prepend, Eq(2));

  int can_fit_hits = num_can_prepend;
  // The PL has room for 2 hits. We should be able to add them without any
  // problem, transitioning the PL from EMPTY -> ALMOST_FULL -> FULL
  const HitElt *hits_in_ptr = hits_in.data() + (hits_in.size() - 2);
  ICING_ASSERT_OK_AND_ASSIGN(
      num_can_prepend,
      (serializer.PrependHitArray<HitElt, HitElt::get_hit>(
          &pl_used, hits_in_ptr, can_fit_hits, /*keep_prepended=*/false)));
  EXPECT_THAT(num_can_prepend, Eq(can_fit_hits));
  EXPECT_THAT(pl_size, Eq(serializer.GetBytesUsed(&pl_used)));
  std::deque<Hit> hits_pushed;
  std::transform(hits_in.rbegin(),
                 hits_in.rend() - hits_in.size() + can_fit_hits,
                 std::front_inserter(hits_pushed), HitElt::get_hit);
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));
}

TEST(PostingListHitSerializerTest, PostingListPrependHitArrayPostingList) {
  PostingListHitSerializer serializer;

  // Size = 36
  int pl_size = 3 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  std::vector<HitElt> hits_in;
  hits_in.emplace_back(Hit(/*section_id=*/1, /*document_id=*/0,
                           Hit::kDefaultTermFrequency,
                           /*is_in_prefix_section=*/false,
                           /*is_prefix_hit=*/false));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  std::reverse(hits_in.begin(), hits_in.end());
  // The last hit is uncompressed and the four before it should only take one
  // byte. Total use = 8 bytes.
  // ----------------------
  // 35     delta(Hit #0)
  // 34     delta(Hit #1)
  // 33     delta(Hit #2)
  // 32     delta(Hit #3)
  // 31-28  Hit #4
  // 27-12  <unused>
  // 11-6   kSpecialHit
  // 5-0    Offset=28
  // ----------------------
  int byte_size = sizeof(Hit::Value) + hits_in.size() - 1;

  // Add five hits. The PL is in the empty state and should be able to fit all
  // five hits without issue, transitioning the PL from EMPTY -> NOT_FULL.
  ICING_ASSERT_OK_AND_ASSIGN(
      uint32_t num_could_fit,
      (serializer.PrependHitArray<HitElt, HitElt::get_hit>(
          &pl_used, &hits_in[0], hits_in.size(), /*keep_prepended=*/false)));
  EXPECT_THAT(num_could_fit, Eq(hits_in.size()));
  EXPECT_THAT(byte_size, Eq(serializer.GetBytesUsed(&pl_used)));
  std::deque<Hit> hits_pushed;
  std::transform(hits_in.rbegin(), hits_in.rend(),
                 std::front_inserter(hits_pushed), HitElt::get_hit);
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));

  Hit first_hit = CreateHit(hits_in.begin()->hit, /*desired_byte_length=*/1);
  hits_in.clear();
  hits_in.emplace_back(first_hit);
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/2));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/1));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/2));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/3));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/2));
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/3));
  std::reverse(hits_in.begin(), hits_in.end());
  // Size increased by the deltas of these hits (1+2+1+2+3+2+3) = 14 bytes
  // ----------------------
  // 35     delta(Hit #0)
  // 34     delta(Hit #1)
  // 33     delta(Hit #2)
  // 32     delta(Hit #3)
  // 31     delta(Hit #4)
  // 30-29  delta(Hit #5)
  // 28     delta(Hit #6)
  // 27-26  delta(Hit #7)
  // 25-23  delta(Hit #8)
  // 22-21  delta(Hit #9)
  // 20-18  delta(Hit #10)
  // 17-14  Hit #11
  // 13-12  <unused>
  // 11-6   kSpecialHit
  // 5-0    Offset=14
  // ----------------------
  byte_size += 14;

  // Add these 7 hits. The PL is currently in the NOT_FULL state and should
  // remain in the NOT_FULL state.
  ICING_ASSERT_OK_AND_ASSIGN(
      num_could_fit,
      (serializer.PrependHitArray<HitElt, HitElt::get_hit>(
          &pl_used, &hits_in[0], hits_in.size(), /*keep_prepended=*/false)));
  EXPECT_THAT(num_could_fit, Eq(hits_in.size()));
  EXPECT_THAT(byte_size, Eq(serializer.GetBytesUsed(&pl_used)));
  // All hits from hits_in were added.
  std::transform(hits_in.rbegin(), hits_in.rend(),
                 std::front_inserter(hits_pushed), HitElt::get_hit);
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));

  first_hit = CreateHit(hits_in.begin()->hit, /*desired_byte_length=*/3);
  hits_in.clear();
  hits_in.emplace_back(first_hit);
  // ----------------------
  // 35     delta(Hit #0)
  // 34     delta(Hit #1)
  // 33     delta(Hit #2)
  // 32     delta(Hit #3)
  // 31     delta(Hit #4)
  // 30-29  delta(Hit #5)
  // 28     delta(Hit #6)
  // 27-26  delta(Hit #7)
  // 25-23  delta(Hit #8)
  // 22-21  delta(Hit #9)
  // 20-18  delta(Hit #10)
  // 17-15  delta(Hit #11)
  // 14-12  <unused>
  // 11-6   Hit #12
  // 5-0    kSpecialHit
  // ----------------------
  byte_size = 30;  // 36 - 6

  // Add this 1 hit. The PL is currently in the NOT_FULL state and should
  // transition to the ALMOST_FULL state - even though there is still some
  // unused space. This is because the unused space (3 bytes) is less than
  // the size of a uncompressed Hit.
  ICING_ASSERT_OK_AND_ASSIGN(
      num_could_fit,
      (serializer.PrependHitArray<HitElt, HitElt::get_hit>(
          &pl_used, &hits_in[0], hits_in.size(), /*keep_prepended=*/false)));
  EXPECT_THAT(num_could_fit, Eq(hits_in.size()));
  EXPECT_THAT(byte_size, Eq(serializer.GetBytesUsed(&pl_used)));
  // All hits from hits_in were added.
  std::transform(hits_in.rbegin(), hits_in.rend(),
                 std::front_inserter(hits_pushed), HitElt::get_hit);
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));

  first_hit = CreateHit(hits_in.begin()->hit, /*desired_byte_length=*/1);
  hits_in.clear();
  hits_in.emplace_back(first_hit);
  hits_in.emplace_back(
      CreateHit(hits_in.rbegin()->hit, /*desired_byte_length=*/3));
  std::reverse(hits_in.begin(), hits_in.end());
  // ----------------------
  // 35     delta(Hit #0)
  // 34     delta(Hit #1)
  // 33     delta(Hit #2)
  // 32     delta(Hit #3)
  // 31     delta(Hit #4)
  // 30-29  delta(Hit #5)
  // 28     delta(Hit #6)
  // 27-26  delta(Hit #7)
  // 25-23  delta(Hit #8)
  // 22-21  delta(Hit #9)
  // 20-18  delta(Hit #10)
  // 17-15  delta(Hit #11)
  // 14     delta(Hit #12)
  // 13-12  <unused>
  // 11-6   Hit #13
  // 5-0    Hit #14
  // ----------------------

  // Add these 2 hits.
  // - The PL is currently in the ALMOST_FULL state. Adding the first hit should
  //   keep the PL in ALMOST_FULL because the delta between
  //   Hit #13 and Hit #14 (1 byte) can fit in the unused area (3 bytes).
  // - Adding the second hit should transition to the FULL state because the
  //   delta between Hit #14 and Hit #15 (3 bytes) is larger than the remaining
  //   unused area (2 byte).
  ICING_ASSERT_OK_AND_ASSIGN(
      num_could_fit,
      (serializer.PrependHitArray<HitElt, HitElt::get_hit>(
          &pl_used, &hits_in[0], hits_in.size(), /*keep_prepended=*/false)));
  EXPECT_THAT(num_could_fit, Eq(hits_in.size()));
  EXPECT_THAT(pl_size, Eq(serializer.GetBytesUsed(&pl_used)));
  // All hits from hits_in were added.
  std::transform(hits_in.rbegin(), hits_in.rend(),
                 std::front_inserter(hits_pushed), HitElt::get_hit);
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));
}

TEST(PostingListHitSerializerTest, PostingListPrependHitArrayTooManyHits) {
  PostingListHitSerializer serializer;

  static constexpr int kNumHits = 128;
  static constexpr int kDeltaSize = 1;
  static constexpr size_t kHitsSize =
      ((kNumHits - 2) * kDeltaSize + (2 * sizeof(Hit))) / sizeof(Hit) *
      sizeof(Hit);

  // Create an array with one too many hits
  std::vector<Hit> hits_in_too_many =
      CreateHits(kNumHits + 1, /*desired_byte_length=*/1);
  std::vector<HitElt> hit_elts_in_too_many;
  for (const Hit &hit : hits_in_too_many) {
    hit_elts_in_too_many.emplace_back(hit);
  }
  // Reverse so that hits are inserted in descending order
  std::reverse(hit_elts_in_too_many.begin(), hit_elts_in_too_many.end());

  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(
          &serializer, serializer.GetMinPostingListSize()));
  // PrependHitArray should fail because hit_elts_in_too_many is far too large
  // for the minimum size pl.
  ICING_ASSERT_OK_AND_ASSIGN(
      uint32_t num_could_fit,
      (serializer.PrependHitArray<HitElt, HitElt::get_hit>(
          &pl_used, &hit_elts_in_too_many[0], hit_elts_in_too_many.size(),
          /*keep_prepended=*/false)));
  ASSERT_THAT(num_could_fit, Eq(2));
  ASSERT_THAT(num_could_fit, Lt(hit_elts_in_too_many.size()));
  ASSERT_THAT(serializer.GetBytesUsed(&pl_used), Eq(0));
  ASSERT_THAT(serializer.GetHits(&pl_used), IsOkAndHolds(IsEmpty()));

  ICING_ASSERT_OK_AND_ASSIGN(
      pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, kHitsSize));
  // PrependHitArray should fail because hit_elts_in_too_many is one hit too
  // large for this pl.
  ICING_ASSERT_OK_AND_ASSIGN(
      num_could_fit,
      (serializer.PrependHitArray<HitElt, HitElt::get_hit>(
          &pl_used, &hit_elts_in_too_many[0], hit_elts_in_too_many.size(),
          /*keep_prepended=*/false)));
  ASSERT_THAT(num_could_fit, Eq(hit_elts_in_too_many.size() - 1));
  ASSERT_THAT(serializer.GetBytesUsed(&pl_used), Eq(0));
  ASSERT_THAT(serializer.GetHits(&pl_used), IsOkAndHolds(IsEmpty()));
}

TEST(PostingListHitSerializerTest,
     PostingListStatusJumpFromNotFullToFullAndBack) {
  PostingListHitSerializer serializer;

  // Size = 18
  const uint32_t pl_size = 3 * sizeof(Hit);
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  Hit max_valued_hit(kMaxSectionId, kMinDocumentId, Hit::kMaxTermFrequency,
                     /*is_in_prefix_section=*/true, /*is_prefix_hit=*/true);
  ICING_ASSERT_OK(serializer.PrependHit(&pl, max_valued_hit));
  uint32_t bytes_used = serializer.GetBytesUsed(&pl);
  ASSERT_THAT(bytes_used, sizeof(Hit::Value) + sizeof(Hit::Flags) +
                              sizeof(Hit::TermFrequency));
  // Status not full.
  ASSERT_THAT(bytes_used,
              Le(pl_size - PostingListHitSerializer::kSpecialHitsSize));

  Hit min_valued_hit(kMinSectionId, kMaxDocumentId, Hit::kMaxTermFrequency,
                     /*is_in_prefix_section=*/true, /*is_prefix_hit=*/true);
  uint8_t delta_buf[VarInt::kMaxEncodedLen64];
  size_t delta_len = PostingListHitSerializer::EncodeNextHitValue(
      /*next_hit_value=*/min_valued_hit.value(),
      /*curr_hit_value=*/max_valued_hit.value(), delta_buf);
  // The compressed region available is pl_size - 2 * sizeof(specialHits) = 6
  // We need to also fit max_valued_hit's flags and term-frequency fields, which
  // each take 1 byte
  // So we'll jump directly to FULL if the varint-encoded delta of the 2 hits >
  // 6 - sizeof(Hit::Flags) - sizeof(Hit::TermFrequency) = 4
  ASSERT_THAT(delta_len, Gt(4));
  ICING_ASSERT_OK(serializer.PrependHit(
      &pl, Hit(kMinSectionId, kMaxDocumentId, Hit::kMaxTermFrequency,
               /*is_in_prefix_section=*/true, /*is_prefix_hit=*/true)));
  // Status should jump to full directly.
  ASSERT_THAT(serializer.GetBytesUsed(&pl), Eq(pl_size));
  ICING_ASSERT_OK(serializer.PopFrontHits(&pl, 1));
  // Status should return to not full as before.
  ASSERT_THAT(serializer.GetBytesUsed(&pl), Eq(bytes_used));
}

TEST(PostingListHitSerializerTest, DeltaOverflow) {
  PostingListHitSerializer serializer;

  const uint32_t pl_size = 4 * sizeof(Hit);
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  static const Hit::Value kMaxHitValue = std::numeric_limits<Hit::Value>::max();
  static const Hit::Value kOverflow[4] = {
      kMaxHitValue >> 2,
      (kMaxHitValue >> 2) * 2,
      (kMaxHitValue >> 2) * 3,
      kMaxHitValue - 1,
  };

  // Fit at least 4 ordinary values.
  for (Hit::Value v = 0; v < 4; v++) {
    ICING_EXPECT_OK(serializer.PrependHit(&pl, Hit(4 - v)));
  }

  // Cannot fit 4 overflow values.
  ICING_ASSERT_OK_AND_ASSIGN(
      pl, PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  Hit::Flags has_term_frequency_flags = 0b1;
  ICING_EXPECT_OK(serializer.PrependHit(
      &pl, Hit(/*value=*/kOverflow[3], has_term_frequency_flags,
               /*term_frequency=*/8)));
  ICING_EXPECT_OK(serializer.PrependHit(
      &pl, Hit(/*value=*/kOverflow[2], has_term_frequency_flags,
               /*term_frequency=*/8)));

  // Can fit only one more.
  ICING_EXPECT_OK(serializer.PrependHit(
      &pl, Hit(/*value=*/kOverflow[1], has_term_frequency_flags,
               /*term_frequency=*/8)));
  EXPECT_THAT(serializer.PrependHit(
                  &pl, Hit(/*value=*/kOverflow[0], has_term_frequency_flags,
                           /*term_frequency=*/8)),
              StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));
}

TEST(PostingListHitSerializerTest, GetMinPostingListToFitForNotFullPL) {
  PostingListHitSerializer serializer;

  // Size = 24
  int pl_size = 2 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  // Create and add some hits to make pl_used NOT_FULL
  std::vector<Hit> hits_in =
      CreateHits(/*num_hits=*/7, /*desired_byte_length=*/1);
  for (const Hit &hit : hits_in) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit));
  }
  // ----------------------
  // 23     delta(Hit #0)
  // 22     delta(Hit #1)
  // 21     delta(Hit #2)
  // 20     delta(Hit #3)
  // 19     delta(Hit #4)
  // 18     delta(Hit #5)
  // 17-14  Hit #6
  // 13-12  <unused>
  // 11-6   kSpecialHit
  // 5-0    Offset=14
  // ----------------------
  int bytes_used = 10;

  // Check that all hits have been inserted
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(bytes_used));
  std::deque<Hit> hits_pushed(hits_in.rbegin(), hits_in.rend());
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));

  // Get the min size to fit for the hits in pl_used. Moving the hits in pl_used
  // into a posting list with this min size should make it ALMOST_FULL, which we
  // can see should have size = 18.
  // ----------------------
  // 17     delta(Hit #0)
  // 16     delta(Hit #1)
  // 15     delta(Hit #2)
  // 14     delta(Hit #3)
  // 13     delta(Hit #4)
  // 12     delta(Hit #5)
  // 11-6   Hit #6
  // 5-0    kSpecialHit
  // ----------------------
  int expected_min_size = 18;
  uint32_t min_size_to_fit = serializer.GetMinPostingListSizeToFit(&pl_used);
  EXPECT_THAT(min_size_to_fit, Eq(expected_min_size));

  // Also check that this min size to fit posting list actually does fit all the
  // hits and can only hit one more hit in the ALMOST_FULL state.
  ICING_ASSERT_OK_AND_ASSIGN(PostingListUsed min_size_to_fit_pl,
                             PostingListUsed::CreateFromUnitializedRegion(
                                 &serializer, min_size_to_fit));
  for (const Hit &hit : hits_in) {
    ICING_ASSERT_OK(serializer.PrependHit(&min_size_to_fit_pl, hit));
  }

  // Adding another hit to the min-size-to-fit posting list should succeed
  Hit hit = CreateHit(hits_in.back(), /*desired_byte_length=*/1);
  ICING_ASSERT_OK(serializer.PrependHit(&min_size_to_fit_pl, hit));
  // Adding any other hits should fail with RESOURCE_EXHAUSTED error.
  EXPECT_THAT(serializer.PrependHit(&min_size_to_fit_pl,
                                    CreateHit(hit, /*desired_byte_length=*/1)),
              StatusIs(libtextclassifier3::StatusCode::RESOURCE_EXHAUSTED));

  // Check that all hits have been inserted and the min-fit posting list is now
  // FULL.
  EXPECT_THAT(serializer.GetBytesUsed(&min_size_to_fit_pl),
              Eq(min_size_to_fit));
  hits_pushed.emplace_front(hit);
  EXPECT_THAT(serializer.GetHits(&min_size_to_fit_pl),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));
}

TEST(PostingListHitSerializerTest, GetMinPostingListToFitForTwoHits) {
  PostingListHitSerializer serializer;

  // Size = 36
  int pl_size = 3 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  // Create and add 2 hits
  Hit first_hit(/*section_id=*/1, /*document_id=*/0, /*term_frequency=*/5,
                /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  std::vector<Hit> hits_in =
      CreateHits(first_hit, /*num_hits=*/2, /*desired_byte_length=*/4);
  for (const Hit &hit : hits_in) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit));
  }
  // ----------------------
  // 35     term-frequency(Hit #0)
  // 34     flags(Hit #0)
  // 33-30  delta(Hit #0)
  // 29     term-frequency(Hit #1)
  // 28     flags(Hit #1)
  // 27-24  Hit #1
  // 23-12  <unused>
  // 11-6   kSpecialHit
  // 5-0    Offset=24
  // ----------------------
  int bytes_used = 12;

  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(bytes_used));
  std::deque<Hit> hits_pushed(hits_in.rbegin(), hits_in.rend());
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));

  // GetMinPostingListSizeToFit should return min posting list size.
  EXPECT_THAT(serializer.GetMinPostingListSizeToFit(&pl_used),
              Eq(serializer.GetMinPostingListSize()));
}

TEST(PostingListHitSerializerTest, GetMinPostingListToFitForThreeSmallHits) {
  PostingListHitSerializer serializer;

  // Size = 24
  int pl_size = 2 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  // Create and add 3 small hits that fit in the size range where we should be
  // checking for whether the PL has only 2 hits
  std::vector<Hit> hits_in =
      CreateHits(/*num_hits=*/3, /*desired_byte_length=*/1);
  for (const Hit &hit : hits_in) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit));
  }
  // ----------------------
  // 23     delta(Hit #0)
  // 22     delta(Hit #1)
  // 21-18  Hit #2
  // 17-12  <unused>
  // 11-6   kSpecialHit
  // 5-0    Offset=18
  // ----------------------
  int bytes_used = 6;

  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(bytes_used));
  std::deque<Hit> hits_pushed(hits_in.rbegin(), hits_in.rend());
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));

  // Get the min size to fit for the hits in pl_used. Moving the hits in pl_used
  // into a posting list with this min size should make it ALMOST_FULL, which we
  // can see should have size = 14. This should not return the min posting list
  // size.
  // ----------------------
  // 13     delta(Hit #0)
  // 12     delta(Hit #1)
  // 11-6   Hit #2
  // 5-0    kSpecialHit
  // ----------------------
  int expected_min_size = 14;

  EXPECT_THAT(serializer.GetMinPostingListSizeToFit(&pl_used),
              Gt(serializer.GetMinPostingListSize()));
  EXPECT_THAT(serializer.GetMinPostingListSizeToFit(&pl_used),
              Eq(expected_min_size));
}

TEST(PostingListHitSerializerTest,
     GetMinPostingListToFitForAlmostFullAndFullPLReturnsSameSize) {
  PostingListHitSerializer serializer;

  // Size = 24
  int pl_size = 2 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  // Create and add some hits to make pl_used ALMOST_FULL
  std::vector<Hit> hits_in =
      CreateHits(/*num_hits=*/7, /*desired_byte_length=*/2);
  for (const Hit &hit : hits_in) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit));
  }
  // ----------------------
  // 23-22     delta(Hit #0)
  // 21-20     delta(Hit #1)
  // 19-18     delta(Hit #2)
  // 17-16     delta(Hit #3)
  // 15-14     delta(Hit #4)
  // 13-12     delta(Hit #5)
  // 11-6      Hit #6
  // 5-0       kSpecialHit
  // ----------------------
  int bytes_used = 18;

  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(bytes_used));
  std::deque<Hit> hits_pushed(hits_in.rbegin(), hits_in.rend());
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));

  // GetMinPostingListSizeToFit should return the same size as pl_used.
  uint32_t min_size_to_fit = serializer.GetMinPostingListSizeToFit(&pl_used);
  EXPECT_THAT(min_size_to_fit, Eq(pl_size));

  // Add another hit to make the posting list FULL
  Hit hit = CreateHit(hits_in.back(), /*desired_byte_length=*/1);
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit));
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(pl_size));
  hits_pushed.emplace_front(hit);
  EXPECT_THAT(serializer.GetHits(&pl_used),
              IsOkAndHolds(ElementsAreArray(hits_pushed)));

  // GetMinPostingListSizeToFit should still be the same size as pl_used.
  min_size_to_fit = serializer.GetMinPostingListSizeToFit(&pl_used);
  EXPECT_THAT(min_size_to_fit, Eq(pl_size));
}

TEST(PostingListHitSerializerTest, MoveFrom) {
  PostingListHitSerializer serializer;

  int pl_size = 3 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used1,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  std::vector<Hit> hits1 =
      CreateHits(/*num_hits=*/5, /*desired_byte_length=*/1);
  for (const Hit &hit : hits1) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used1, hit));
  }

  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used2,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  std::vector<Hit> hits2 =
      CreateHits(/*num_hits=*/5, /*desired_byte_length=*/2);
  for (const Hit &hit : hits2) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used2, hit));
  }

  ICING_ASSERT_OK(serializer.MoveFrom(/*dst=*/&pl_used2, /*src=*/&pl_used1));
  EXPECT_THAT(serializer.GetHits(&pl_used2),
              IsOkAndHolds(ElementsAreArray(hits1.rbegin(), hits1.rend())));
  EXPECT_THAT(serializer.GetHits(&pl_used1), IsOkAndHolds(IsEmpty()));
}

TEST(PostingListHitSerializerTest, MoveFromNullArgumentReturnsInvalidArgument) {
  PostingListHitSerializer serializer;

  int pl_size = 3 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used1,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  std::vector<Hit> hits = CreateHits(/*num_hits=*/5, /*desired_byte_length=*/1);
  for (const Hit &hit : hits) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used1, hit));
  }

  EXPECT_THAT(serializer.MoveFrom(/*dst=*/&pl_used1, /*src=*/nullptr),
              StatusIs(libtextclassifier3::StatusCode::FAILED_PRECONDITION));
  EXPECT_THAT(serializer.GetHits(&pl_used1),
              IsOkAndHolds(ElementsAreArray(hits.rbegin(), hits.rend())));
}

TEST(PostingListHitSerializerTest,
     MoveFromInvalidPostingListReturnsInvalidArgument) {
  PostingListHitSerializer serializer;

  int pl_size = 3 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used1,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  std::vector<Hit> hits1 =
      CreateHits(/*num_hits=*/5, /*desired_byte_length=*/1);
  for (const Hit &hit : hits1) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used1, hit));
  }

  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used2,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  std::vector<Hit> hits2 =
      CreateHits(/*num_hits=*/5, /*desired_byte_length=*/2);
  for (const Hit &hit : hits2) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used2, hit));
  }

  // Write invalid hits to the beginning of pl_used1 to make it invalid.
  Hit invalid_hit(Hit::kInvalidValue);
  Hit *first_hit = reinterpret_cast<Hit *>(pl_used1.posting_list_buffer());
  *first_hit = invalid_hit;
  ++first_hit;
  *first_hit = invalid_hit;
  EXPECT_THAT(serializer.MoveFrom(/*dst=*/&pl_used2, /*src=*/&pl_used1),
              StatusIs(libtextclassifier3::StatusCode::INVALID_ARGUMENT));
  EXPECT_THAT(serializer.GetHits(&pl_used2),
              IsOkAndHolds(ElementsAreArray(hits2.rbegin(), hits2.rend())));
}

TEST(PostingListHitSerializerTest,
     MoveToInvalidPostingListReturnsFailedPrecondition) {
  PostingListHitSerializer serializer;

  int pl_size = 3 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used1,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  std::vector<Hit> hits1 =
      CreateHits(/*num_hits=*/5, /*desired_byte_length=*/1);
  for (const Hit &hit : hits1) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used1, hit));
  }

  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used2,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  std::vector<Hit> hits2 =
      CreateHits(/*num_hits=*/5, /*desired_byte_length=*/2);
  for (const Hit &hit : hits2) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used2, hit));
  }

  // Write invalid hits to the beginning of pl_used2 to make it invalid.
  Hit invalid_hit(Hit::kInvalidValue);
  Hit *first_hit = reinterpret_cast<Hit *>(pl_used2.posting_list_buffer());
  *first_hit = invalid_hit;
  ++first_hit;
  *first_hit = invalid_hit;
  EXPECT_THAT(serializer.MoveFrom(/*dst=*/&pl_used2, /*src=*/&pl_used1),
              StatusIs(libtextclassifier3::StatusCode::FAILED_PRECONDITION));
  EXPECT_THAT(serializer.GetHits(&pl_used1),
              IsOkAndHolds(ElementsAreArray(hits1.rbegin(), hits1.rend())));
}

TEST(PostingListHitSerializerTest, MoveToPostingListTooSmall) {
  PostingListHitSerializer serializer;

  int pl_size = 3 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used1,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));
  std::vector<Hit> hits1 =
      CreateHits(/*num_hits=*/5, /*desired_byte_length=*/1);
  for (const Hit &hit : hits1) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used1, hit));
  }

  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used2,
      PostingListUsed::CreateFromUnitializedRegion(
          &serializer, serializer.GetMinPostingListSize()));
  std::vector<Hit> hits2 =
      CreateHits(/*num_hits=*/1, /*desired_byte_length=*/2);
  for (const Hit &hit : hits2) {
    ICING_ASSERT_OK(serializer.PrependHit(&pl_used2, hit));
  }

  EXPECT_THAT(serializer.MoveFrom(/*dst=*/&pl_used2, /*src=*/&pl_used1),
              StatusIs(libtextclassifier3::StatusCode::INVALID_ARGUMENT));
  EXPECT_THAT(serializer.GetHits(&pl_used1),
              IsOkAndHolds(ElementsAreArray(hits1.rbegin(), hits1.rend())));
  EXPECT_THAT(serializer.GetHits(&pl_used2),
              IsOkAndHolds(ElementsAreArray(hits2.rbegin(), hits2.rend())));
}

TEST(PostingListHitSerializerTest, PopHitsWithTermFrequenciesAndFlags) {
  PostingListHitSerializer serializer;

  // Size = 24
  int pl_size = 2 * serializer.GetMinPostingListSize();
  ICING_ASSERT_OK_AND_ASSIGN(
      PostingListUsed pl_used,
      PostingListUsed::CreateFromUnitializedRegion(&serializer, pl_size));

  // This posting list is 24-bytes. Create four hits that will have deltas of
  // two bytes each and all of whom will have a non-default term-frequency. This
  // posting list will be almost_full.
  //
  // ----------------------
  // 23     term-frequency(Hit #0)
  // 22     flags(Hit #0)
  // 21-20  delta(Hit #0)
  // 19     term-frequency(Hit #1)
  // 18     flags(Hit #1)
  // 17-16  delta(Hit #1)
  // 15     term-frequency(Hit #2)
  // 14     flags(Hit #2)
  // 13-12  delta(Hit #2)
  // 11-6   Hit #3
  // 5-0    kInvalidHit
  // ----------------------
  int bytes_used = 18;

  Hit hit0(/*section_id=*/0, /*document_id=*/0, /*term_frequency=*/5,
           /*is_in_prefix_section=*/false, /*is_prefix_hit=*/false);
  Hit hit1 = CreateHit(hit0, /*desired_byte_length=*/2);
  Hit hit2 = CreateHit(hit1, /*desired_byte_length=*/2);
  Hit hit3 = CreateHit(hit2, /*desired_byte_length=*/2);
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit0));
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit1));
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit2));
  ICING_ASSERT_OK(serializer.PrependHit(&pl_used, hit3));

  ICING_ASSERT_OK_AND_ASSIGN(std::vector<Hit> hits_out,
                             serializer.GetHits(&pl_used));
  EXPECT_THAT(hits_out, ElementsAre(hit3, hit2, hit1, hit0));
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(bytes_used));

  // Now, pop the last hit. The posting list should contain the first three
  // hits.
  //
  // ----------------------
  // 23     term-frequency(Hit #0)
  // 22     flags(Hit #0)
  // 21-20  delta(Hit #0)
  // 19     term-frequency(Hit #1)
  // 18     flags(Hit #1)
  // 17-16  delta(Hit #1)
  // 15-12  <unused>
  // 11-6   Hit #2
  // 5-0    kInvalidHit
  // ----------------------
  ICING_ASSERT_OK(serializer.PopFrontHits(&pl_used, 1));
  ICING_ASSERT_OK_AND_ASSIGN(hits_out, serializer.GetHits(&pl_used));
  EXPECT_THAT(hits_out, ElementsAre(hit2, hit1, hit0));
  EXPECT_THAT(serializer.GetBytesUsed(&pl_used), Eq(bytes_used));
}

}  // namespace

}  // namespace lib
}  // namespace icing