// Copyright 2012 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/sync/base/unique_position.h"

#include <algorithm>
#include <cstdint>
#include <functional>
#include <memory>
#include <vector>

#include "base/base64.h"
#include "base/containers/span.h"
#include "base/hash/sha1.h"
#include "base/logging.h"
#include "base/memory/raw_ptr.h"
#include "base/memory/raw_span.h"
#include "base/rand_util.h"
#include "base/strings/string_number_conversions.h"
#include "components/sync/protocol/unique_position.pb.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace syncer {

namespace {

// This function exploits internal knowledge of how the protobufs are serialized
// to help us build UniquePositions from strings described in this file.
static UniquePosition FromBytes(const std::string& bytes) {
  sync_pb::UniquePosition proto;
  proto.set_value(bytes);
  return UniquePosition::FromProto(proto);
}

class UniquePositionTest : public ::testing::Test {
 protected:
  // Accessor to fetch the length of the position's internal representation
  // We try to avoid having any test expectations on it because this is an
  // implementation detail.
  //
  // If you run the tests with --v=1, we'll print out some of the lengths
  // so you can see how well the algorithm performs in various insertion
  // scenarios.
  size_t GetLength(const UniquePosition& pos) {
    return pos.ToProto().ByteSizeLong();
  }

  const size_t kMinLength = UniquePosition::kSuffixLength;
  const size_t kGenericPredecessorLength = kMinLength + 2;
  const size_t kGenericSuccessorLength = kMinLength + 1;
  const size_t kBigPositionLength = kMinLength;
  const size_t kSmallPositionLength = kMinLength;

  // Be careful when adding more prefixes to this list.
  // We have to manually ensure each has a unique suffix.
  const UniquePosition kGenericPredecessor =
      FromBytes((std::string(kGenericPredecessorLength, '\x23') + '\xFF'));
  const UniquePosition kGenericSuccessor =
      FromBytes(std::string(kGenericSuccessorLength, '\xAB') + '\xFF');
  const UniquePosition kBigPosition =
      FromBytes(std::string(kBigPositionLength - 1, '\xFF') + '\xFE' + '\xFF');
  const UniquePosition kBigPositionLessTwo =
      FromBytes(std::string(kBigPositionLength - 1, '\xFF') + '\xFC' + '\xFF');
  const UniquePosition kBiggerPosition =
      FromBytes(std::string(kBigPositionLength, '\xFF') + '\xFF');
  const UniquePosition kSmallPosition = FromBytes(
      std::string(kSmallPositionLength - 1, '\x00') + '\x01' + '\xFF');
  const UniquePosition kSmallPositionPlusOne = FromBytes(
      std::string(kSmallPositionLength - 1, '\x00') + '\x02' + '\xFF');
  const UniquePosition kHugePosition = FromBytes(
      std::string(UniquePosition::kCompressBytesThreshold, '\xFF') + '\xAB');

  const std::array<UniquePosition, 7> kPositionArray = {
      kGenericPredecessor,  kGenericSuccessor, kBigPosition,
      kBigPositionLessTwo,  kBiggerPosition,   kSmallPosition,
      kSmallPositionPlusOne};

  const std::array<UniquePosition, 7> kSortedPositionArray = {
      kSmallPosition,    kSmallPositionPlusOne, kGenericPredecessor,
      kGenericSuccessor, kBigPositionLessTwo,   kBigPosition,
      kBiggerPosition};
};

static constexpr uint8_t kMinSuffix[] = {
    '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
    '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
    '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
    '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x01'};
static_assert(std::size(kMinSuffix) == UniquePosition::kSuffixLength,
              "Wrong size of kMinSuffix.");

static constexpr uint8_t kMaxSuffix[] = {
    u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF',
    u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF',
    u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF',
    u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF', u'\xFF'};
static_assert(std::size(kMaxSuffix) == UniquePosition::kSuffixLength,
              "Wrong size of kMaxSuffix.");

static constexpr uint8_t kNormalSuffix[] = {
    '\x68', '\x44', '\x6C', '\x6B', '\x32', '\x58', '\x78',
    '\x34', '\x69', '\x70', '\x46', '\x34', '\x79', '\x49',
    '\x44', '\x4F', '\x66', '\x4C', '\x58', '\x41', '\x31',
    '\x34', '\x68', '\x59', '\x56', '\x43', '\x6F', '\x3D'};
static_assert(std::size(kNormalSuffix) == UniquePosition::kSuffixLength,
              "Wrong size of kNormalSuffix.");

::testing::AssertionResult LessThan(const char* m_expr,
                                    const char* n_expr,
                                    const UniquePosition& m,
                                    const UniquePosition& n) {
  if (m.LessThan(n)) {
    return ::testing::AssertionSuccess();
  }

  return ::testing::AssertionFailure()
         << m_expr << " is not less than " << n_expr << " ("
         << m.ToDebugString() << " and " << n.ToDebugString() << ")";
}

::testing::AssertionResult Equals(const char* m_expr,
                                  const char* n_expr,
                                  const UniquePosition& m,
                                  const UniquePosition& n) {
  if (m.Equals(n)) {
    return ::testing::AssertionSuccess();
  }

  return ::testing::AssertionFailure()
         << m_expr << " is not equal to " << n_expr << " (" << m.ToDebugString()
         << " != " << n.ToDebugString() << ")";
}

// Test that the code can read the uncompressed serialization format.
TEST_F(UniquePositionTest, DeserializeObsoleteUncompressedPosition) {
  // We no longer support the encoding data in this format.  This hard-coded
  // input is a serialization of kGenericPredecessor created by an older version
  // of this code.
  const char kSerializedCstr[] = {
      '\x0a', '\x1f', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23',
      '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23',
      '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23',
      '\x23', '\x23', '\x23', '\x23', '\x23', '\xff'};
  const std::string serialized(kSerializedCstr, sizeof(kSerializedCstr));

  sync_pb::UniquePosition proto;
  proto.ParseFromString(serialized);

  // Double-check that this test is testing what we think it tests.
  EXPECT_TRUE(proto.has_value());
  EXPECT_FALSE(proto.has_compressed_value());
  EXPECT_FALSE(proto.has_uncompressed_length());

  UniquePosition pos = UniquePosition::FromProto(proto);
  EXPECT_PRED_FORMAT2(Equals, kGenericPredecessor, pos);
}

// Test that the code can read the gzip serialization format.
TEST_F(UniquePositionTest, DeserializeObsoleteGzippedPosition) {
  // We no longer support the encoding data in this format.  This hard-coded
  // input is a serialization of kHugePosition created by an older version of
  // this code.
  const char kSerializedCstr[] = {
      '\x12', '\x0d', '\x78', '\x9c', '\xfb', '\xff', '\x7f', '\x60', '\xc1',
      '\x6a', '\x00', '\xa2', '\x4c', '\x80', '\x2c', '\x18', '\x81', '\x01'};
  const std::string serialized(kSerializedCstr, sizeof(kSerializedCstr));

  sync_pb::UniquePosition proto;
  proto.ParseFromString(serialized);

  // Double-check that this test is testing what we think it tests.
  EXPECT_FALSE(proto.has_value());
  EXPECT_TRUE(proto.has_compressed_value());
  EXPECT_TRUE(proto.has_uncompressed_length());

  UniquePosition pos = UniquePosition::FromProto(proto);
  EXPECT_PRED_FORMAT2(Equals, kHugePosition, pos);
}

TEST_F(UniquePositionTest, UncompressTooLongRepeatingDigit) {
  // First 4 bytes represent the digit to expand, and the next 4 bytes is the
  // number of bytes.
  constexpr char kSerializedCstr[] = {'\x12', '\x12', '\x12', '\x12',
                                      '\x88', '\x88', '\x88', '\x88'};

  sync_pb::UniquePosition proto;
  proto.set_custom_compressed_v1(kSerializedCstr, sizeof(kSerializedCstr));
  proto.mutable_custom_compressed_v1()->append(
      base::RandBytesAsString(UniquePosition::kSuffixLength));
  UniquePosition unique_position = UniquePosition::FromProto(proto);
  EXPECT_FALSE(unique_position.IsValid());
}

class RelativePositioningTest : public UniquePositionTest {};

struct PositionLessThan {
  bool operator()(const UniquePosition& a, const UniquePosition& b) {
    return a.LessThan(b);
  }
};

// Returns true iff the given position's suffix matches the input parameter.
static bool IsSuffixInUse(const UniquePosition& pos,
                          const UniquePosition::Suffix& suffix) {
  return pos.GetSuffixForTest() == suffix;
}

// Test some basic properties of comparison and equality.
TEST_F(RelativePositioningTest, ComparisonSanityTest1) {
  const UniquePosition& a = kPositionArray[0];
  ASSERT_TRUE(a.IsValid());

  // Necessarily true for any non-invalid positions.
  EXPECT_TRUE(a.Equals(a));
  EXPECT_FALSE(a.LessThan(a));
}

// Test some more properties of comparison and equality.
TEST_F(RelativePositioningTest, ComparisonSanityTest2) {
  const UniquePosition& a = kPositionArray[0];
  const UniquePosition& b = kPositionArray[1];

  // These should pass for the specific a and b we have chosen (a < b).
  EXPECT_FALSE(a.Equals(b));
  EXPECT_TRUE(a.LessThan(b));
  EXPECT_FALSE(b.LessThan(a));
}

// Exercise comparision functions by sorting and re-sorting the list.
TEST_F(RelativePositioningTest, SortPositions) {
  std::array<UniquePosition, 7> positions;
  ASSERT_EQ(kPositionArray.size(), kSortedPositionArray.size());
  base::span(positions).copy_from(kPositionArray);

  std::ranges::sort(positions, PositionLessThan());
  for (size_t i = 0; i < kPositionArray.size(); ++i) {
    EXPECT_TRUE(positions[i].Equals(kSortedPositionArray[i]))
        << "i: " << i << ", " << positions[i].ToDebugString()
        << " != " << kSortedPositionArray[i].ToDebugString();
  }
}

// Some more exercise for the comparison function.
TEST_F(RelativePositioningTest, ReverseSortPositions) {
  std::array<UniquePosition, 7> positions;
  ASSERT_EQ(kPositionArray.size(), kSortedPositionArray.size());
  ASSERT_EQ(kPositionArray.size(), positions.size());
  base::span(positions).copy_from(kPositionArray);

  std::ranges::reverse(positions);
  std::ranges::sort(positions, PositionLessThan());
  for (size_t i = 0; i < kPositionArray.size(); ++i) {
    EXPECT_TRUE(positions[i].Equals(kSortedPositionArray[i]))
        << "i: " << i << ", " << positions[i].ToDebugString()
        << " != " << kSortedPositionArray[i].ToDebugString();
  }
}

class PositionInsertTest
    : public RelativePositioningTest,
      public ::testing::WithParamInterface<UniquePosition::Suffix> {};

// Exercise InsertBetween with various insertion operations.
TEST_P(PositionInsertTest, InsertBetween) {
  const UniquePosition::Suffix suffix = GetParam();
  ASSERT_TRUE(UniquePosition::IsValidSuffix(suffix));

  for (size_t i = 0; i < kSortedPositionArray.size(); ++i) {
    const UniquePosition& predecessor = kSortedPositionArray[i];
    // Verify our suffixes are unique before we continue.
    if (IsSuffixInUse(predecessor, suffix)) {
      continue;
    }

    for (size_t j = i + 1; j < kSortedPositionArray.size(); ++j) {
      const UniquePosition& successor = kSortedPositionArray[j];

      // Another guard against non-unique suffixes.
      if (IsSuffixInUse(successor, suffix)) {
        continue;
      }

      UniquePosition midpoint =
          UniquePosition::Between(predecessor, successor, suffix);

      EXPECT_PRED_FORMAT2(LessThan, predecessor, midpoint);
      EXPECT_PRED_FORMAT2(LessThan, midpoint, successor);
    }
  }
}

TEST_P(PositionInsertTest, InsertBefore) {
  const UniquePosition::Suffix suffix = GetParam();
  for (size_t i = 0; i < kSortedPositionArray.size(); ++i) {
    const UniquePosition& successor = kSortedPositionArray[i];
    // Verify our suffixes are unique before we continue.
    if (IsSuffixInUse(successor, suffix)) {
      continue;
    }

    UniquePosition before = UniquePosition::Before(successor, suffix);

    EXPECT_PRED_FORMAT2(LessThan, before, successor);
  }
}

TEST_P(PositionInsertTest, InsertAfter) {
  const UniquePosition::Suffix suffix = GetParam();
  for (size_t i = 0; i < kSortedPositionArray.size(); ++i) {
    const UniquePosition& predecessor = kSortedPositionArray[i];
    // Verify our suffixes are unique before we continue.
    if (IsSuffixInUse(predecessor, suffix)) {
      continue;
    }

    UniquePosition after = UniquePosition::After(predecessor, suffix);

    EXPECT_PRED_FORMAT2(LessThan, predecessor, after);
  }
}

TEST_P(PositionInsertTest, StressInsertAfter) {
  // Use two different suffixes to not violate our suffix uniqueness guarantee.
  const UniquePosition::Suffix suffix_a = GetParam();
  UniquePosition::Suffix suffix_b = suffix_a;
  suffix_b[10] = suffix_b[10] ^ 0xff;

  UniquePosition pos = UniquePosition::InitialPosition(suffix_a);
  for (int i = 0; i < 1024; i++) {
    const UniquePosition::Suffix& suffix = (i % 2 == 0) ? suffix_b : suffix_a;
    UniquePosition next_pos = UniquePosition::After(pos, suffix);
    ASSERT_PRED_FORMAT2(LessThan, pos, next_pos);
    pos = next_pos;
  }

  VLOG(1) << "Length: " << GetLength(pos);
}

TEST_P(PositionInsertTest, StressInsertBefore) {
  // Use two different suffixes to not violate our suffix uniqueness guarantee.
  const UniquePosition::Suffix& suffix_a = GetParam();
  UniquePosition::Suffix suffix_b = suffix_a;
  suffix_b[10] = suffix_b[10] ^ 0xff;

  UniquePosition pos = UniquePosition::InitialPosition(suffix_a);
  for (int i = 0; i < 1024; i++) {
    const UniquePosition::Suffix& suffix = (i % 2 == 0) ? suffix_b : suffix_a;
    UniquePosition prev_pos = UniquePosition::Before(pos, suffix);
    ASSERT_PRED_FORMAT2(LessThan, prev_pos, pos);
    pos = prev_pos;
  }

  VLOG(1) << "Length: " << GetLength(pos);
}

TEST_P(PositionInsertTest, StressLeftInsertBetween) {
  // Use different suffixes to not violate our suffix uniqueness guarantee.
  const UniquePosition::Suffix& suffix_a = GetParam();
  UniquePosition::Suffix suffix_b = suffix_a;
  suffix_b[10] = suffix_b[10] ^ 0xff;
  UniquePosition::Suffix suffix_c = suffix_a;
  suffix_c[10] = suffix_c[10] ^ 0xf0;

  UniquePosition right_pos = UniquePosition::InitialPosition(suffix_c);
  UniquePosition left_pos = UniquePosition::Before(right_pos, suffix_a);
  for (int i = 0; i < 1024; i++) {
    const UniquePosition::Suffix& suffix = (i % 2 == 0) ? suffix_b : suffix_a;
    UniquePosition new_pos =
        UniquePosition::Between(left_pos, right_pos, suffix);
    ASSERT_PRED_FORMAT2(LessThan, left_pos, new_pos);
    ASSERT_PRED_FORMAT2(LessThan, new_pos, right_pos);
    left_pos = new_pos;
  }

  VLOG(1) << "Lengths: " << GetLength(left_pos) << ", " << GetLength(right_pos);
}

TEST_P(PositionInsertTest, StressRightInsertBetween) {
  // Use different suffixes to not violate our suffix uniqueness guarantee.
  const UniquePosition::Suffix& suffix_a = GetParam();
  UniquePosition::Suffix suffix_b = suffix_a;
  suffix_b[10] = suffix_b[10] ^ 0xff;
  UniquePosition::Suffix suffix_c = suffix_a;
  suffix_c[10] = suffix_c[10] ^ 0xf0;

  UniquePosition right_pos = UniquePosition::InitialPosition(suffix_a);
  UniquePosition left_pos = UniquePosition::Before(right_pos, suffix_c);
  for (int i = 0; i < 1024; i++) {
    const UniquePosition::Suffix& suffix = (i % 2 == 0) ? suffix_b : suffix_a;
    UniquePosition new_pos =
        UniquePosition::Between(left_pos, right_pos, suffix);
    ASSERT_PRED_FORMAT2(LessThan, left_pos, new_pos);
    ASSERT_PRED_FORMAT2(LessThan, new_pos, right_pos);
    right_pos = new_pos;
  }

  VLOG(1) << "Lengths: " << GetLength(left_pos) << ", " << GetLength(right_pos);
}

// Generates suffixes similar to those generated by the legacy Directory.
// This may become obsolete if the suffix generation code is modified.
class SuffixGenerator {
 public:
  explicit SuffixGenerator(const std::string& cache_guid)
      : cache_guid_(cache_guid) {}

  UniquePosition::Suffix NextSuffix() {
    // This is not entirely realistic, but that should be OK.  The current
    // suffix format is a base64'ed SHA1 hash, which should be fairly close to
    // random anyway.
    std::string input = cache_guid_ + base::NumberToString(next_id_--);
    std::string suffix_str =
        base::Base64Encode(base::SHA1Hash(base::as_byte_span(input)));
    UniquePosition::Suffix suffix;
    std::ranges::copy(suffix_str, suffix.begin());
    return suffix;
  }

 private:
  const std::string cache_guid_;
  int64_t next_id_ = -65535;
};

// Cache guids generated in the same style as real clients.
static const char kCacheGuidStr1[] = "tuiWdG8hV+8y4RT9N5Aikg==";
static const char kCacheGuidStr2[] = "yaKb7zHtY06aue9a0vlZgw==";

class PositionScenariosTest : public UniquePositionTest {
 public:
  PositionScenariosTest()
      : generator1_(std::string(kCacheGuidStr1, std::size(kCacheGuidStr1) - 1)),
        generator2_(
            std::string(kCacheGuidStr2, std::size(kCacheGuidStr2) - 1)) {}

  UniquePosition::Suffix NextClient1Suffix() {
    return generator1_.NextSuffix();
  }

  UniquePosition::Suffix NextClient2Suffix() {
    return generator2_.NextSuffix();
  }

 private:
  SuffixGenerator generator1_;
  SuffixGenerator generator2_;
};

// One client creating new bookmarks, always inserting at the end.
TEST_F(PositionScenariosTest, OneClientInsertAtEnd) {
  UniquePosition pos = UniquePosition::InitialPosition(NextClient1Suffix());
  for (int i = 0; i < 1024; i++) {
    const UniquePosition::Suffix suffix = NextClient1Suffix();
    UniquePosition new_pos = UniquePosition::After(pos, suffix);
    ASSERT_PRED_FORMAT2(LessThan, pos, new_pos);
    pos = new_pos;
  }

  VLOG(1) << "Length: " << GetLength(pos);

  // Normally we wouldn't want to make an assertion about the internal
  // representation of our data, but we make an exception for this case.
  // If this scenario causes lengths to explode, we have a big problem.
  EXPECT_LT(GetLength(pos), 500U);
}

// Two clients alternately inserting entries at the end, with a strong
// bias towards insertions by the first client.
TEST_F(PositionScenariosTest, TwoClientsInsertAtEnd_A) {
  UniquePosition pos = UniquePosition::InitialPosition(NextClient1Suffix());
  for (int i = 0; i < 1024; i++) {
    UniquePosition::Suffix suffix;
    if (i % 5 == 0) {
      suffix = NextClient2Suffix();
    } else {
      suffix = NextClient1Suffix();
    }

    UniquePosition new_pos = UniquePosition::After(pos, suffix);
    ASSERT_PRED_FORMAT2(LessThan, pos, new_pos);
    pos = new_pos;
  }

  VLOG(1) << "Length: " << GetLength(pos);
  EXPECT_LT(GetLength(pos), 500U);
}

// Two clients alternately inserting entries at the end.
TEST_F(PositionScenariosTest, TwoClientsInsertAtEnd_B) {
  UniquePosition pos = UniquePosition::InitialPosition(NextClient1Suffix());
  for (int i = 0; i < 1024; i++) {
    UniquePosition::Suffix suffix;
    if (i % 2 == 0) {
      suffix = NextClient1Suffix();
    } else {
      suffix = NextClient2Suffix();
    }

    UniquePosition new_pos = UniquePosition::After(pos, suffix);
    ASSERT_PRED_FORMAT2(LessThan, pos, new_pos);
    pos = new_pos;
  }

  VLOG(1) << "Length: " << GetLength(pos);
  EXPECT_LT(GetLength(pos), 500U);
}

INSTANTIATE_TEST_SUITE_P(MinSuffix,
                         PositionInsertTest,
                         ::testing::Values(std::to_array(kMinSuffix)));
INSTANTIATE_TEST_SUITE_P(MaxSuffix,
                         PositionInsertTest,
                         ::testing::Values(std::to_array(kMaxSuffix)));
INSTANTIATE_TEST_SUITE_P(NormalSuffix,
                         PositionInsertTest,
                         ::testing::Values(std::to_array(kNormalSuffix)));

class PositionFromIntTest : public UniquePositionTest {
 public:
  PositionFromIntTest()
      : generator_(std::string(kCacheGuidStr1, std::size(kCacheGuidStr1) - 1)) {
  }

 protected:
  static constexpr auto kTestValues =
      std::to_array<int64_t>({0LL,
                              1LL,
                              -1LL,
                              2LL,
                              -2LL,
                              3LL,
                              -3LL,
                              0x79LL,
                              -0x79LL,
                              0x80LL,
                              -0x80LL,
                              0x81LL,
                              -0x81LL,
                              0xFELL,
                              -0xFELL,
                              0xFFLL,
                              -0xFFLL,
                              0x100LL,
                              -0x100LL,
                              0x101LL,
                              -0x101LL,
                              0xFA1AFELL,
                              -0xFA1AFELL,
                              0xFFFFFFFELL,
                              -0xFFFFFFFELL,
                              0xFFFFFFFFLL,
                              -0xFFFFFFFFLL,
                              0x100000000LL,
                              -0x100000000LL,
                              0x100000001LL,
                              -0x100000001LL,
                              0xFFFFFFFFFFLL,
                              -0xFFFFFFFFFFLL,
                              0x112358132134LL,
                              -0x112358132134LL,
                              0xFEFFBEEFABC1234LL,
                              -0xFEFFBEEFABC1234LL,
                              INT64_MAX,
                              INT64_MIN,
                              INT64_MIN + 1,
                              INT64_MAX - 1});
  UniquePosition::Suffix NextSuffix() { return generator_.NextSuffix(); }

 private:
  SuffixGenerator generator_;
};

TEST_F(PositionFromIntTest, IsValid) {
  for (size_t i = 0; i < kTestValues.size(); ++i) {
    const UniquePosition pos =
        UniquePosition::FromInt64(kTestValues[i], NextSuffix());
    EXPECT_TRUE(pos.IsValid()) << "i = " << i << "; " << pos.ToDebugString();
  }
}

template <typename T, typename LessThan = std::less<T>>
class IndexedLessThan {
 public:
  explicit IndexedLessThan(base::span<const T> values) : values_(values) {}

  bool operator()(size_t i1, size_t i2) {
    return less_than_(values_[i1], values_[i2]);
  }

 private:
  base::raw_span<const T> values_;
  LessThan less_than_;
};

TEST_F(PositionFromIntTest, ConsistentOrdering) {
  std::array<UniquePosition, kTestValues.size()> positions;
  std::vector<size_t> original_ordering(kTestValues.size());
  std::vector<size_t> int64_ordering(kTestValues.size());
  std::vector<size_t> position_ordering(kTestValues.size());
  for (size_t i = 0; i < kTestValues.size(); ++i) {
    positions[i] = UniquePosition::FromInt64(kTestValues[i], NextSuffix());
    original_ordering[i] = int64_ordering[i] = position_ordering[i] = i;
  }

  std::ranges::sort(int64_ordering, IndexedLessThan<int64_t>(kTestValues));
  std::ranges::sort(
      position_ordering,
      IndexedLessThan<UniquePosition, PositionLessThan>(positions));
  EXPECT_NE(original_ordering, int64_ordering);
  EXPECT_EQ(int64_ordering, position_ordering);
}

class CompressedPositionTest : public UniquePositionTest {
 public:
  CompressedPositionTest() {
    positions_.push_back(MakePosition(  // Prefix starts with 256 0x00s
        std::string("\x00\x00\x00\x00\xFF\xFF\xFE\xFF"
                    "\x01",
                    9),
        MakeSuffix('\x04')));
    positions_.push_back(MakePosition(  // Prefix starts with four 0x00s
        std::string("\x00\x00\x00\x00\xFF\xFF\xFF\xFB"
                    "\x01",
                    9),
        MakeSuffix('\x03')));
    positions_.push_back(MakePosition(  // Prefix starts with four 0xFFs
        std::string("\xFF\xFF\xFF\xFF\x00\x00\x00\x04"
                    "\x01",
                    9),
        MakeSuffix('\x01')));
    positions_.push_back(MakePosition(  // Prefix starts with 256 0xFFs
        std::string("\xFF\xFF\xFF\xFF\x00\x00\x01\x00"
                    "\x01",
                    9),
        MakeSuffix('\x02')));
  }

 private:
  UniquePosition MakePosition(const std::string& compressed_prefix,
                              const std::string& compressed_suffix);
  std::string MakeSuffix(char unique_value);

 protected:
  std::vector<UniquePosition> positions_;
};

UniquePosition CompressedPositionTest::MakePosition(
    const std::string& compressed_prefix,
    const std::string& compressed_suffix) {
  sync_pb::UniquePosition proto;
  proto.set_custom_compressed_v1(
      std::string(compressed_prefix + compressed_suffix));
  return UniquePosition::FromProto(proto);
}

std::string CompressedPositionTest::MakeSuffix(char unique_value) {
  // We're dealing in compressed positions in this test.  That means the
  // suffix should be compressed, too.  To avoid complication, we use suffixes
  // that don't have any repeating digits, and therefore are identical in
  // compressed and uncompressed form.
  std::string suffix;
  for (size_t i = 0; i < UniquePosition::kSuffixLength; ++i) {
    suffix.push_back(static_cast<char>(i));
  }
  suffix[UniquePosition::kSuffixLength - 1] = unique_value;
  return suffix;
}

// Make sure that serialization and deserialization routines are correct.
TEST_F(CompressedPositionTest, SerializeAndDeserialize) {
  for (std::vector<UniquePosition>::const_iterator it = positions_.begin();
       it != positions_.end(); ++it) {
    SCOPED_TRACE("iteration: " + it->ToDebugString());

    UniquePosition deserialized = UniquePosition::FromProto(it->ToProto());

    EXPECT_PRED_FORMAT2(Equals, *it, deserialized);
  }
}

// Test that deserialization failures of protobufs where we know none of its
// fields is not catastrophic.  This may happen if all the fields currently
// known to this client become deprecated in the future.
TEST_F(CompressedPositionTest, DeserializeProtobufFromTheFuture) {
  sync_pb::UniquePosition proto;
  UniquePosition deserialized = UniquePosition::FromProto(proto);
  EXPECT_FALSE(deserialized.IsValid());
}

// Make sure the comparison functions are working correctly.
// This requires values in the test harness to be hard-coded in ascending order.
TEST_F(CompressedPositionTest, OrderingTest) {
  for (size_t i = 0; i < positions_.size() - 1; ++i) {
    EXPECT_PRED_FORMAT2(LessThan, positions_[i], positions_[i + 1]);
  }
}

}  // namespace

}  // namespace syncer