Home | History | Annotate | Download | only in base
      1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "sync/internal_api/public/base/unique_position.h"
      6 
      7 #include <algorithm>
      8 #include <string>
      9 
     10 #include "base/base64.h"
     11 #include "base/basictypes.h"
     12 #include "base/logging.h"
     13 #include "base/memory/scoped_ptr.h"
     14 #include "base/sha1.h"
     15 #include "base/strings/string_number_conversions.h"
     16 #include "sync/protocol/unique_position.pb.h"
     17 #include "testing/gtest/include/gtest/gtest.h"
     18 
     19 namespace syncer {
     20 
     21 namespace {
     22 
     23 class UniquePositionTest : public ::testing::Test {
     24  protected:
     25   // Accessor to fetch the length of the position's internal representation
     26   // We try to avoid having any test expectations on it because this is an
     27   // implementation detail.
     28   //
     29   // If you run the tests with --v=1, we'll print out some of the lengths
     30   // so you can see how well the algorithm performs in various insertion
     31   // scenarios.
     32   size_t GetLength(const UniquePosition& pos) {
     33     sync_pb::UniquePosition proto;
     34     pos.ToProto(&proto);
     35     return proto.ByteSize();
     36   }
     37 };
     38 
     39 // This function exploits internal knowledge of how the protobufs are serialized
     40 // to help us build UniquePositions from strings described in this file.
     41 static UniquePosition FromBytes(const std::string& bytes) {
     42   sync_pb::UniquePosition proto;
     43   proto.set_value(bytes);
     44   return UniquePosition::FromProto(proto);
     45 }
     46 
     47 const size_t kMinLength = UniquePosition::kSuffixLength;
     48 const size_t kGenericPredecessorLength = kMinLength + 2;
     49 const size_t kGenericSuccessorLength = kMinLength + 1;
     50 const size_t kBigPositionLength = kMinLength;
     51 const size_t kSmallPositionLength = kMinLength;
     52 
     53 // Be careful when adding more prefixes to this list.
     54 // We have to manually ensure each has a unique suffix.
     55 const UniquePosition kGenericPredecessor = FromBytes(
     56     (std::string(kGenericPredecessorLength, '\x23') + '\xFF'));
     57 const UniquePosition kGenericSuccessor = FromBytes(
     58     std::string(kGenericSuccessorLength, '\xAB') + '\xFF');
     59 const UniquePosition kBigPosition = FromBytes(
     60     std::string(kBigPositionLength - 1, '\xFF') + '\xFE' + '\xFF');
     61 const UniquePosition kBigPositionLessTwo = FromBytes(
     62     std::string(kBigPositionLength - 1, '\xFF') + '\xFC' + '\xFF');
     63 const UniquePosition kBiggerPosition = FromBytes(
     64     std::string(kBigPositionLength, '\xFF') + '\xFF');
     65 const UniquePosition kSmallPosition = FromBytes(
     66     std::string(kSmallPositionLength - 1, '\x00') + '\x01' + '\xFF');
     67 const UniquePosition kSmallPositionPlusOne = FromBytes(
     68     std::string(kSmallPositionLength - 1, '\x00') + '\x02' + '\xFF');
     69 const UniquePosition kHugePosition = FromBytes(
     70     std::string(UniquePosition::kCompressBytesThreshold, '\xFF') + '\xAB');
     71 
     72 const std::string kMinSuffix =
     73     std::string(UniquePosition::kSuffixLength - 1, '\x00') + '\x01';
     74 const std::string kMaxSuffix(UniquePosition::kSuffixLength, '\xFF');
     75 const std::string kNormalSuffix(
     76     "\x68\x44\x6C\x6B\x32\x58\x78\x34\x69\x70\x46\x34\x79\x49"
     77     "\x44\x4F\x66\x4C\x58\x41\x31\x34\x68\x59\x56\x43\x6F\x3D");
     78 
     79 ::testing::AssertionResult LessThan(const char* m_expr,
     80                                     const char* n_expr,
     81                                     const UniquePosition &m,
     82                                     const UniquePosition &n) {
     83   if (m.LessThan(n))
     84     return ::testing::AssertionSuccess();
     85 
     86   return ::testing::AssertionFailure()
     87       << m_expr << " is not less than " << n_expr
     88       << " (" << m.ToDebugString() << " and " << n.ToDebugString() << ")";
     89 }
     90 
     91 ::testing::AssertionResult Equals(const char* m_expr,
     92                                   const char* n_expr,
     93                                   const UniquePosition &m,
     94                                   const UniquePosition &n) {
     95   if (m.Equals(n))
     96     return ::testing::AssertionSuccess();
     97 
     98   return ::testing::AssertionFailure()
     99       << m_expr << " is not equal to " << n_expr
    100       << " (" << m.ToDebugString() << " != " << n.ToDebugString() << ")";
    101 }
    102 
    103 // Test that the code can read the uncompressed serialization format.
    104 TEST_F(UniquePositionTest, DeserializeObsoleteUncompressedPosition) {
    105   // We no longer support the encoding data in this format.  This hard-coded
    106   // input is a serialization of kGenericPredecessor created by an older version
    107   // of this code.
    108   const char kSerializedCstr[] = {
    109     '\x0a', '\x1f', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23',
    110     '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23',
    111     '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23',
    112     '\x23', '\x23', '\x23', '\x23', '\x23', '\xff' };
    113   const std::string serialized(kSerializedCstr, sizeof(kSerializedCstr));
    114 
    115   sync_pb::UniquePosition proto;
    116   proto.ParseFromString(serialized);
    117 
    118   // Double-check that this test is testing what we think it tests.
    119   EXPECT_TRUE(proto.has_value());
    120   EXPECT_FALSE(proto.has_compressed_value());
    121   EXPECT_FALSE(proto.has_uncompressed_length());
    122 
    123   UniquePosition pos = UniquePosition::FromProto(proto);
    124   EXPECT_PRED_FORMAT2(Equals, kGenericPredecessor, pos);
    125 }
    126 
    127 // Test that the code can read the gzip serialization format.
    128 TEST_F(UniquePositionTest, DeserializeObsoleteGzippedPosition) {
    129   // We no longer support the encoding data in this format.  This hard-coded
    130   // input is a serialization of kHugePosition created by an older version of
    131   // this code.
    132   const char kSerializedCstr[] = {
    133     '\x12', '\x0d', '\x78', '\x9c', '\xfb', '\xff', '\x7f', '\x60', '\xc1',
    134     '\x6a', '\x00', '\xa2', '\x4c', '\x80', '\x2c', '\x18', '\x81', '\x01' };
    135   const std::string serialized(kSerializedCstr, sizeof(kSerializedCstr));
    136 
    137   sync_pb::UniquePosition proto;
    138   proto.ParseFromString(serialized);
    139 
    140   // Double-check that this test is testing what we think it tests.
    141   EXPECT_FALSE(proto.has_value());
    142   EXPECT_TRUE(proto.has_compressed_value());
    143   EXPECT_TRUE(proto.has_uncompressed_length());
    144 
    145   UniquePosition pos = UniquePosition::FromProto(proto);
    146   EXPECT_PRED_FORMAT2(Equals, kHugePosition, pos);
    147 }
    148 
    149 class RelativePositioningTest : public UniquePositionTest { };
    150 
    151 const UniquePosition kPositionArray[] = {
    152   kGenericPredecessor,
    153   kGenericSuccessor,
    154   kBigPosition,
    155   kBigPositionLessTwo,
    156   kBiggerPosition,
    157   kSmallPosition,
    158   kSmallPositionPlusOne,
    159 };
    160 
    161 const UniquePosition kSortedPositionArray[] = {
    162   kSmallPosition,
    163   kSmallPositionPlusOne,
    164   kGenericPredecessor,
    165   kGenericSuccessor,
    166   kBigPositionLessTwo,
    167   kBigPosition,
    168   kBiggerPosition,
    169 };
    170 
    171 static const size_t kNumPositions = arraysize(kPositionArray);
    172 static const size_t kNumSortedPositions = arraysize(kSortedPositionArray);
    173 
    174 struct PositionLessThan {
    175   bool operator()(const UniquePosition& a, const UniquePosition& b) {
    176     return a.LessThan(b);
    177   }
    178 };
    179 
    180 // Returns true iff the given position's suffix matches the input parameter.
    181 static bool IsSuffixInUse(
    182     const UniquePosition& pos, const std::string& suffix) {
    183   return pos.GetSuffixForTest() == suffix;
    184 }
    185 
    186 // Test some basic properties of comparison and equality.
    187 TEST_F(RelativePositioningTest, ComparisonSanityTest1) {
    188   const UniquePosition& a = kPositionArray[0];
    189   ASSERT_TRUE(a.IsValid());
    190 
    191   // Necessarily true for any non-invalid positions.
    192   EXPECT_TRUE(a.Equals(a));
    193   EXPECT_FALSE(a.LessThan(a));
    194 }
    195 
    196 // Test some more properties of comparison and equality.
    197 TEST_F(RelativePositioningTest, ComparisonSanityTest2) {
    198   const UniquePosition& a = kPositionArray[0];
    199   const UniquePosition& b = kPositionArray[1];
    200 
    201   // These should pass for the specific a and b we have chosen (a < b).
    202   EXPECT_FALSE(a.Equals(b));
    203   EXPECT_TRUE(a.LessThan(b));
    204   EXPECT_FALSE(b.LessThan(a));
    205 }
    206 
    207 // Exercise comparision functions by sorting and re-sorting the list.
    208 TEST_F(RelativePositioningTest, SortPositions) {
    209   ASSERT_EQ(kNumPositions, kNumSortedPositions);
    210   UniquePosition positions[arraysize(kPositionArray)];
    211   for (size_t i = 0; i < kNumPositions; ++i) {
    212     positions[i] = kPositionArray[i];
    213   }
    214 
    215   std::sort(&positions[0], &positions[kNumPositions], PositionLessThan());
    216   for (size_t i = 0; i < kNumPositions; ++i) {
    217     EXPECT_TRUE(positions[i].Equals(kSortedPositionArray[i]))
    218         << "i: " << i << ", "
    219         << positions[i].ToDebugString() << " != "
    220         << kSortedPositionArray[i].ToDebugString();
    221   }
    222 
    223 }
    224 
    225 // Some more exercise for the comparison function.
    226 TEST_F(RelativePositioningTest, ReverseSortPositions) {
    227   ASSERT_EQ(kNumPositions, kNumSortedPositions);
    228   UniquePosition positions[arraysize(kPositionArray)];
    229   for (size_t i = 0; i < kNumPositions; ++i) {
    230     positions[i] = kPositionArray[i];
    231   }
    232 
    233   std::reverse(&positions[0], &positions[kNumPositions]);
    234   std::sort(&positions[0], &positions[kNumPositions], PositionLessThan());
    235   for (size_t i = 0; i < kNumPositions; ++i) {
    236     EXPECT_TRUE(positions[i].Equals(kSortedPositionArray[i]))
    237         << "i: " << i << ", "
    238         << positions[i].ToDebugString() << " != "
    239         << kSortedPositionArray[i].ToDebugString();
    240   }
    241 }
    242 
    243 class PositionInsertTest :
    244     public RelativePositioningTest,
    245     public ::testing::WithParamInterface<std::string> { };
    246 
    247 // Exercise InsertBetween with various insertion operations.
    248 TEST_P(PositionInsertTest, InsertBetween) {
    249   const std::string suffix = GetParam();
    250   ASSERT_TRUE(UniquePosition::IsValidSuffix(suffix));
    251 
    252   for (size_t i = 0; i < kNumSortedPositions; ++i) {
    253     const UniquePosition& predecessor = kSortedPositionArray[i];
    254     // Verify our suffixes are unique before we continue.
    255     if (IsSuffixInUse(predecessor, suffix))
    256       continue;
    257 
    258     for (size_t j = i + 1; j < kNumSortedPositions; ++j) {
    259       const UniquePosition& successor = kSortedPositionArray[j];
    260 
    261       // Another guard against non-unique suffixes.
    262       if (IsSuffixInUse(successor, suffix))
    263         continue;
    264 
    265       UniquePosition midpoint =
    266           UniquePosition::Between(predecessor, successor, suffix);
    267 
    268       EXPECT_PRED_FORMAT2(LessThan, predecessor, midpoint);
    269       EXPECT_PRED_FORMAT2(LessThan, midpoint, successor);
    270     }
    271   }
    272 }
    273 
    274 TEST_P(PositionInsertTest, InsertBefore) {
    275   const std::string suffix = GetParam();
    276   for (size_t i = 0; i < kNumSortedPositions; ++i) {
    277     const UniquePosition& successor = kSortedPositionArray[i];
    278     // Verify our suffixes are unique before we continue.
    279     if (IsSuffixInUse(successor, suffix))
    280       continue;
    281 
    282     UniquePosition before = UniquePosition::Before(successor, suffix);
    283 
    284     EXPECT_PRED_FORMAT2(LessThan, before, successor);
    285   }
    286 }
    287 
    288 TEST_P(PositionInsertTest, InsertAfter) {
    289   const std::string suffix = GetParam();
    290   for (size_t i = 0; i < kNumSortedPositions; ++i) {
    291     const UniquePosition& predecessor = kSortedPositionArray[i];
    292     // Verify our suffixes are unique before we continue.
    293     if (IsSuffixInUse(predecessor, suffix))
    294       continue;
    295 
    296     UniquePosition after = UniquePosition::After(predecessor, suffix);
    297 
    298     EXPECT_PRED_FORMAT2(LessThan, predecessor, after);
    299   }
    300 }
    301 
    302 TEST_P(PositionInsertTest, StressInsertAfter) {
    303   // Use two different suffixes to not violate our suffix uniqueness guarantee.
    304   const std::string& suffix_a = GetParam();
    305   std::string suffix_b = suffix_a;
    306   suffix_b[10] = suffix_b[10] ^ 0xff;
    307 
    308   UniquePosition pos = UniquePosition::InitialPosition(suffix_a);
    309   for (int i = 0; i < 1024; i++) {
    310     const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a;
    311     UniquePosition next_pos = UniquePosition::After(pos, suffix);
    312     ASSERT_PRED_FORMAT2(LessThan, pos, next_pos);
    313     pos = next_pos;
    314   }
    315 
    316   VLOG(1) << "Length: " << GetLength(pos);
    317 }
    318 
    319 TEST_P(PositionInsertTest, StressInsertBefore) {
    320   // Use two different suffixes to not violate our suffix uniqueness guarantee.
    321   const std::string& suffix_a = GetParam();
    322   std::string suffix_b = suffix_a;
    323   suffix_b[10] = suffix_b[10] ^ 0xff;
    324 
    325   UniquePosition pos = UniquePosition::InitialPosition(suffix_a);
    326   for (int i = 0; i < 1024; i++) {
    327     const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a;
    328     UniquePosition prev_pos = UniquePosition::Before(pos, suffix);
    329     ASSERT_PRED_FORMAT2(LessThan, prev_pos, pos);
    330     pos = prev_pos;
    331   }
    332 
    333   VLOG(1) << "Length: " << GetLength(pos);
    334 }
    335 
    336 TEST_P(PositionInsertTest, StressLeftInsertBetween) {
    337   // Use different suffixes to not violate our suffix uniqueness guarantee.
    338   const std::string& suffix_a = GetParam();
    339   std::string suffix_b = suffix_a;
    340   suffix_b[10] = suffix_b[10] ^ 0xff;
    341   std::string suffix_c = suffix_a;
    342   suffix_c[10] = suffix_c[10] ^ 0xf0;
    343 
    344   UniquePosition right_pos = UniquePosition::InitialPosition(suffix_c);
    345   UniquePosition left_pos = UniquePosition::Before(right_pos, suffix_a);
    346   for (int i = 0; i < 1024; i++) {
    347     const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a;
    348     UniquePosition new_pos =
    349         UniquePosition::Between(left_pos, right_pos, suffix);
    350     ASSERT_PRED_FORMAT2(LessThan, left_pos, new_pos);
    351     ASSERT_PRED_FORMAT2(LessThan, new_pos, right_pos);
    352     left_pos = new_pos;
    353   }
    354 
    355   VLOG(1) << "Lengths: " << GetLength(left_pos) << ", " << GetLength(right_pos);
    356 }
    357 
    358 TEST_P(PositionInsertTest, StressRightInsertBetween) {
    359   // Use different suffixes to not violate our suffix uniqueness guarantee.
    360   const std::string& suffix_a = GetParam();
    361   std::string suffix_b = suffix_a;
    362   suffix_b[10] = suffix_b[10] ^ 0xff;
    363   std::string suffix_c = suffix_a;
    364   suffix_c[10] = suffix_c[10] ^ 0xf0;
    365 
    366   UniquePosition right_pos = UniquePosition::InitialPosition(suffix_a);
    367   UniquePosition left_pos = UniquePosition::Before(right_pos, suffix_c);
    368   for (int i = 0; i < 1024; i++) {
    369     const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a;
    370     UniquePosition new_pos =
    371         UniquePosition::Between(left_pos, right_pos, suffix);
    372     ASSERT_PRED_FORMAT2(LessThan, left_pos, new_pos);
    373     ASSERT_PRED_FORMAT2(LessThan, new_pos, right_pos);
    374     right_pos = new_pos;
    375   }
    376 
    377   VLOG(1) << "Lengths: " << GetLength(left_pos) << ", " << GetLength(right_pos);
    378 }
    379 
    380 // Generates suffixes similar to those generated by the directory.
    381 // This may become obsolete if the suffix generation code is modified.
    382 class SuffixGenerator {
    383  public:
    384   explicit SuffixGenerator(const std::string& cache_guid)
    385       : cache_guid_(cache_guid),
    386         next_id_(-65535) {
    387   }
    388 
    389   std::string NextSuffix() {
    390     // This is not entirely realistic, but that should be OK.  The current
    391     // suffix format is a base64'ed SHA1 hash, which should be fairly close to
    392     // random anyway.
    393     std::string input = cache_guid_ + base::Int64ToString(next_id_--);
    394     std::string output;
    395     CHECK(base::Base64Encode(base::SHA1HashString(input), &output));
    396     return output;
    397   }
    398 
    399  private:
    400   const std::string cache_guid_;
    401   int64 next_id_;
    402 };
    403 
    404 // Cache guids generated in the same style as real clients.
    405 static const char kCacheGuidStr1[] = "tuiWdG8hV+8y4RT9N5Aikg==";
    406 static const char kCacheGuidStr2[] = "yaKb7zHtY06aue9a0vlZgw==";
    407 
    408 class PositionScenariosTest : public UniquePositionTest {
    409  public:
    410   PositionScenariosTest()
    411       : generator1_(std::string(kCacheGuidStr1, arraysize(kCacheGuidStr1)-1)),
    412         generator2_(std::string(kCacheGuidStr2, arraysize(kCacheGuidStr2)-1)) {
    413   }
    414 
    415   std::string NextClient1Suffix() {
    416     return generator1_.NextSuffix();
    417   }
    418 
    419   std::string NextClient2Suffix() {
    420     return generator2_.NextSuffix();
    421   }
    422 
    423  private:
    424   SuffixGenerator generator1_;
    425   SuffixGenerator generator2_;
    426 };
    427 
    428 // One client creating new bookmarks, always inserting at the end.
    429 TEST_F(PositionScenariosTest, OneClientInsertAtEnd) {
    430   UniquePosition pos =
    431       UniquePosition::InitialPosition(NextClient1Suffix());
    432   for (int i = 0; i < 1024; i++) {
    433     const std::string suffix = NextClient1Suffix();
    434     UniquePosition new_pos = UniquePosition::After(pos, suffix);
    435     ASSERT_PRED_FORMAT2(LessThan, pos, new_pos);
    436     pos = new_pos;
    437   }
    438 
    439   VLOG(1) << "Length: " << GetLength(pos);
    440 
    441   // Normally we wouldn't want to make an assertion about the internal
    442   // representation of our data, but we make an exception for this case.
    443   // If this scenario causes lengths to explode, we have a big problem.
    444   EXPECT_LT(GetLength(pos), 500U);
    445 }
    446 
    447 // Two clients alternately inserting entries at the end, with a strong
    448 // bias towards insertions by the first client.
    449 TEST_F(PositionScenariosTest, TwoClientsInsertAtEnd_A) {
    450   UniquePosition pos =
    451       UniquePosition::InitialPosition(NextClient1Suffix());
    452   for (int i = 0; i < 1024; i++) {
    453     std::string suffix;
    454     if (i % 5 == 0) {
    455       suffix = NextClient2Suffix();
    456     } else {
    457       suffix = NextClient1Suffix();
    458     }
    459 
    460     UniquePosition new_pos = UniquePosition::After(pos, suffix);
    461     ASSERT_PRED_FORMAT2(LessThan, pos, new_pos);
    462     pos = new_pos;
    463   }
    464 
    465   VLOG(1) << "Length: " << GetLength(pos);
    466   EXPECT_LT(GetLength(pos), 500U);
    467 }
    468 
    469 // Two clients alternately inserting entries at the end.
    470 TEST_F(PositionScenariosTest, TwoClientsInsertAtEnd_B) {
    471   UniquePosition pos =
    472       UniquePosition::InitialPosition(NextClient1Suffix());
    473   for (int i = 0; i < 1024; i++) {
    474     std::string suffix;
    475     if (i % 2 == 0) {
    476       suffix = NextClient1Suffix();
    477     } else {
    478       suffix = NextClient2Suffix();
    479     }
    480 
    481     UniquePosition new_pos = UniquePosition::After(pos, suffix);
    482     ASSERT_PRED_FORMAT2(LessThan, pos, new_pos);
    483     pos = new_pos;
    484   }
    485 
    486   VLOG(1) << "Length: " << GetLength(pos);
    487   EXPECT_LT(GetLength(pos), 500U);
    488 }
    489 
    490 INSTANTIATE_TEST_CASE_P(MinSuffix, PositionInsertTest,
    491                         ::testing::Values(kMinSuffix));
    492 INSTANTIATE_TEST_CASE_P(MaxSuffix, PositionInsertTest,
    493                         ::testing::Values(kMaxSuffix));
    494 INSTANTIATE_TEST_CASE_P(NormalSuffix, PositionInsertTest,
    495                         ::testing::Values(kNormalSuffix));
    496 
    497 class PositionFromIntTest : public UniquePositionTest {
    498  public:
    499   PositionFromIntTest()
    500       : generator_(std::string(kCacheGuidStr1, arraysize(kCacheGuidStr1)-1)) {
    501   }
    502 
    503  protected:
    504   static const int64 kTestValues[];
    505   static const size_t kNumTestValues;
    506 
    507   std::string NextSuffix() {
    508     return generator_.NextSuffix();
    509   }
    510 
    511  private:
    512   SuffixGenerator generator_;
    513 };
    514 
    515 const int64 PositionFromIntTest::kTestValues[] = {
    516   0LL,
    517   1LL, -1LL,
    518   2LL, -2LL,
    519   3LL, -3LL,
    520   0x79LL, -0x79LL,
    521   0x80LL, -0x80LL,
    522   0x81LL, -0x81LL,
    523   0xFELL, -0xFELL,
    524   0xFFLL, -0xFFLL,
    525   0x100LL, -0x100LL,
    526   0x101LL, -0x101LL,
    527   0xFA1AFELL, -0xFA1AFELL,
    528   0xFFFFFFFELL, -0xFFFFFFFELL,
    529   0xFFFFFFFFLL, -0xFFFFFFFFLL,
    530   0x100000000LL, -0x100000000LL,
    531   0x100000001LL, -0x100000001LL,
    532   0xFFFFFFFFFFLL, -0xFFFFFFFFFFLL,
    533   0x112358132134LL, -0x112358132134LL,
    534   0xFEFFBEEFABC1234LL, -0xFEFFBEEFABC1234LL,
    535   kint64max,
    536   kint64min,
    537   kint64min + 1,
    538   kint64max - 1
    539 };
    540 
    541 const size_t PositionFromIntTest::kNumTestValues =
    542 arraysize(PositionFromIntTest::kTestValues);
    543 
    544 TEST_F(PositionFromIntTest, IsValid) {
    545   for (size_t i = 0; i < kNumTestValues; ++i) {
    546     const UniquePosition pos =
    547         UniquePosition::FromInt64(kTestValues[i], NextSuffix());
    548     EXPECT_TRUE(pos.IsValid()) << "i = " << i << "; " << pos.ToDebugString();
    549   }
    550 }
    551 
    552 TEST_F(PositionFromIntTest, RoundTripConversion) {
    553   for (size_t i = 0; i < kNumTestValues; ++i) {
    554     const int64 expected_value = kTestValues[i];
    555     const UniquePosition pos =
    556         UniquePosition::FromInt64(kTestValues[i], NextSuffix());
    557     const int64 value = pos.ToInt64();
    558     EXPECT_EQ(expected_value, value) << "i = " << i;
    559   }
    560 }
    561 
    562 template <typename T, typename LessThan = std::less<T> >
    563 class IndexedLessThan {
    564  public:
    565   IndexedLessThan(const T* values) : values_(values) {}
    566 
    567   bool operator()(int i1, int i2) {
    568     return less_than_(values_[i1], values_[i2]);
    569   }
    570 
    571  private:
    572   const T* values_;
    573   LessThan less_than_;
    574 };
    575 
    576 TEST_F(PositionFromIntTest, ConsistentOrdering) {
    577   UniquePosition positions[kNumTestValues];
    578   std::vector<int> original_ordering(kNumTestValues);
    579   std::vector<int> int64_ordering(kNumTestValues);
    580   std::vector<int> position_ordering(kNumTestValues);
    581   for (size_t i = 0; i < kNumTestValues; ++i) {
    582     positions[i] = UniquePosition::FromInt64(
    583         kTestValues[i], NextSuffix());
    584     original_ordering[i] = int64_ordering[i] = position_ordering[i] = i;
    585   }
    586 
    587   std::sort(int64_ordering.begin(), int64_ordering.end(),
    588             IndexedLessThan<int64>(kTestValues));
    589   std::sort(position_ordering.begin(), position_ordering.end(),
    590             IndexedLessThan<UniquePosition, PositionLessThan>(positions));
    591   EXPECT_NE(original_ordering, int64_ordering);
    592   EXPECT_EQ(int64_ordering, position_ordering);
    593 }
    594 
    595 class CompressedPositionTest : public UniquePositionTest {
    596  public:
    597   CompressedPositionTest() {
    598     positions_.push_back(
    599         MakePosition( // Prefix starts with 256 0x00s
    600             std::string("\x00\x00\x00\x00\xFF\xFF\xFE\xFF" "\x01", 9),
    601             MakeSuffix('\x04')));
    602     positions_.push_back(
    603         MakePosition( // Prefix starts with four 0x00s
    604             std::string("\x00\x00\x00\x00\xFF\xFF\xFF\xFB" "\x01", 9),
    605             MakeSuffix('\x03')));
    606     positions_.push_back(
    607         MakePosition( // Prefix starts with four 0xFFs
    608             std::string("\xFF\xFF\xFF\xFF\x00\x00\x00\x04" "\x01", 9),
    609             MakeSuffix('\x01')));
    610     positions_.push_back(
    611         MakePosition( // Prefix starts with 256 0xFFs
    612             std::string("\xFF\xFF\xFF\xFF\x00\x00\x01\x00" "\x01", 9),
    613             MakeSuffix('\x02')));
    614   }
    615 
    616  private:
    617   UniquePosition MakePosition(const std::string& compressed_prefix,
    618                               const std::string& compressed_suffix);
    619   std::string MakeSuffix(char unique_value);
    620 
    621  protected:
    622   std::vector<UniquePosition> positions_;
    623 };
    624 
    625 UniquePosition CompressedPositionTest::MakePosition(
    626       const std::string& compressed_prefix,
    627       const std::string& compressed_suffix) {
    628   sync_pb::UniquePosition proto;
    629   proto.set_custom_compressed_v1(
    630       std::string(compressed_prefix + compressed_suffix));
    631   return UniquePosition::FromProto(proto);
    632 }
    633 
    634 std::string CompressedPositionTest::MakeSuffix(char unique_value) {
    635   // We're dealing in compressed positions in this test.  That means the
    636   // suffix should be compressed, too.  To avoid complication, we use suffixes
    637   // that don't have any repeating digits, and therefore are identical in
    638   // compressed and uncompressed form.
    639   std::string suffix;
    640   for (size_t i = 0; i < UniquePosition::kSuffixLength; ++i) {
    641     suffix.push_back(static_cast<char>(i));
    642   }
    643   suffix[UniquePosition::kSuffixLength-1] = unique_value;
    644   return suffix;
    645 }
    646 
    647 // Make sure that serialization and deserialization routines are correct.
    648 TEST_F(CompressedPositionTest, SerializeAndDeserialize) {
    649   for (std::vector<UniquePosition>::const_iterator it = positions_.begin();
    650        it != positions_.end(); ++it) {
    651     SCOPED_TRACE("iteration: " + it->ToDebugString());
    652 
    653     sync_pb::UniquePosition proto;
    654     it->ToProto(&proto);
    655     UniquePosition deserialized = UniquePosition::FromProto(proto);
    656 
    657     EXPECT_PRED_FORMAT2(Equals, *it, deserialized);
    658 
    659   }
    660 }
    661 
    662 // Test that redundant serialization for legacy clients is correct, too.
    663 TEST_F(CompressedPositionTest, SerializeAndLegacyDeserialize) {
    664   for (std::vector<UniquePosition>::const_iterator it = positions_.begin();
    665        it != positions_.end(); ++it) {
    666     SCOPED_TRACE("iteration: " + it->ToDebugString());
    667     sync_pb::UniquePosition proto;
    668 
    669     it->ToProto(&proto);
    670 
    671     // Clear default encoding to force it to use legacy as fallback.
    672     proto.clear_custom_compressed_v1();
    673     UniquePosition deserialized = UniquePosition::FromProto(proto);
    674 
    675     EXPECT_PRED_FORMAT2(Equals, *it, deserialized);
    676   }
    677 }
    678 
    679 // Make sure the comparison functions are working correctly.
    680 // This requires values in the test harness to be hard-coded in ascending order.
    681 TEST_F(CompressedPositionTest, OrderingTest) {
    682   for (size_t i = 0; i < positions_.size()-1; ++i) {
    683     EXPECT_PRED_FORMAT2(LessThan, positions_[i], positions_[i+1]);
    684   }
    685 }
    686 
    687 }  // namespace
    688 
    689 }  // namespace syncer
    690