sync/internal_api/public/base/unique_position_unittest.cc

   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     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 // Test that deserialization failures of protobufs where we know none of its
 662 // fields is not catastrophic.  This may happen if all the fields currently
 663 // known to this client become deprecated in the future.
 664 TEST_F(CompressedPositionTest, DeserializeProtobufFromTheFuture) {
 665   sync_pb::UniquePosition proto;
 666   UniquePosition deserialized = UniquePosition::FromProto(proto);
 667   EXPECT_FALSE(deserialized.IsValid());
 668 }
 669
 670 // Make sure the comparison functions are working correctly.
 671 // This requires values in the test harness to be hard-coded in ascending order.
 672 TEST_F(CompressedPositionTest, OrderingTest) {
 673   for (size_t i = 0; i < positions_.size()-1; ++i) {
 674     EXPECT_PRED_FORMAT2(LessThan, positions_[i], positions_[i+1]);
 675   }
 676 }
 677
 678 }  // namespace
 679
 680 }  // namespace syncer