WIP: The Bookmark Position Megapatch

sync/internal_api/public/base/unique_position_unittest.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "sync/internal_api/public/base/unique_position.h"
 
 #include <algorithm>
 #include <string>
 
+#include "base/base64.h"
 #include "base/basictypes.h"
 #include "base/logging.h"
+#include "base/sha1.h"
+#include "base/string_number_conversions.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace syncer {
 
 namespace {
 
 class UniquePositionTest : public ::testing::Test {
  protected:
-  // Accessor to fetch the length of the position's internal representation.  We
-  // don't have any test expectations on it because this is an implementation
-  // detail.
+  // 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.
   //
-  // We use it to see just how big our ordinals are getting in some of the
-  // worst-case scenarios that occur in our tests.  This can be useful when
-  // testing and comparing alternative implementations.  Enable with --v=1.
+  // 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(UniquePosition &pos) {
     return pos.ToInternalValue().length();
   }
 };
 
 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;
@@ skipping 236 matching lines @@
     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 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),
+        next_id_(-65535) {
+  }
+
+  std::string 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::Int64ToString(next_id_--);
+    std::string output;
+    CHECK(base::Base64Encode(base::SHA1HashString(input), &output));
+    return output;
+  }
+
+ private:
+  const std::string cache_guid_;
+  int64 next_id_;
+};
+
+// 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, arraysize(kCacheGuidStr1)-1)),
+        generator2_(std::string(kCacheGuidStr2, arraysize(kCacheGuidStr2)-1)) {
+  }
+
+  std::string NextClient1Suffix() {
+    return generator1_.NextSuffix();
+  }
+
+  std::string 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 std::string 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++) {
+    std::string 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++) {
+    std::string 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_CASE_P(MinSuffix, PositionInsertTest,
                         ::testing::Values(kMinSuffix));
 INSTANTIATE_TEST_CASE_P(MaxSuffix, PositionInsertTest,
                         ::testing::Values(kMaxSuffix));
 INSTANTIATE_TEST_CASE_P(NormalSuffix, PositionInsertTest,
                         ::testing::Values(kNormalSuffix));
 
 class PositionFromIntTest : public UniquePositionTest {
+ public:
+  PositionFromIntTest()
+      : generator_(std::string(kCacheGuidStr1, arraysize(kCacheGuidStr1)-1)) {
+  }
+
  protected:
-  static std::string SuffixFromInt(int64 item_id) {
-    // Represents a cache_guid-like value.
-    const std::string guid(
-        "\xFF\xFE\xFE\xFF\x00\x01\x01\x00"
-        "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF", 16);
+  std::string NextSuffix() {
+    return generator_.NextSuffix();
+  }
 
-    return UniquePosition::GenerateBookmarkSuffix(guid, item_id);
-  }
+ private:
+  SuffixGenerator generator_;
 };
 
 const int64 kTestValues[] = {
   0LL,
   1LL, -1LL,
   2LL, -2LL,
   3LL, -3LL,
   0x79LL, -0x79LL,
   0x80LL, -0x80LL,
   0x81LL, -0x81LL,
@@ skipping 13 matching lines @@
   kint64min,
   kint64min + 1,
   kint64max - 1
 };
 
 const size_t kNumTestValues = arraysize(kTestValues);
 
 TEST_F(PositionFromIntTest, IsValid) {
   for (size_t i = 0; i < kNumTestValues; ++i) {
     const UniquePosition pos =
-        UniquePosition::FromInt64(kTestValues[i], SuffixFromInt(i));
+        UniquePosition::FromInt64(kTestValues[i], NextSuffix());
     EXPECT_TRUE(pos.IsValid()) << "i = " << i << "; " << pos.ToDebugString();
   }
 }
 
 TEST_F(PositionFromIntTest, RoundTripConversion) {
   for (size_t i = 0; i < kNumTestValues; ++i) {
     const int64 expected_value = kTestValues[i];
     const UniquePosition pos =
-        UniquePosition::FromInt64(kTestValues[i], SuffixFromInt(i));
+        UniquePosition::FromInt64(kTestValues[i], NextSuffix());
     const int64 value = pos.ToInt64();
     EXPECT_EQ(expected_value, value) << "i = " << i;
   }
 }
 
 template <typename T, typename LessThan = std::less<T> >
 class IndexedLessThan {
  public:
   IndexedLessThan(const T* values) : values_(values) {}
 
   bool operator()(int i1, int i2) {
     return less_than_(values_[i1], values_[i2]);
   }
 
  private:
   const T* values_;
   LessThan less_than_;
 };
 
 TEST_F(PositionFromIntTest, ConsistentOrdering) {
   UniquePosition positions[kNumTestValues];
   std::vector<int> original_ordering(kNumTestValues);
   std::vector<int> int64_ordering(kNumTestValues);
   std::vector<int> position_ordering(kNumTestValues);
   for (size_t i = 0; i < kNumTestValues; ++i) {
     positions[i] = UniquePosition::FromInt64(
-        kTestValues[i], SuffixFromInt(i));
+        kTestValues[i], NextSuffix());
     original_ordering[i] = int64_ordering[i] = position_ordering[i] = i;
   }
 
   std::sort(int64_ordering.begin(), int64_ordering.end(),
             IndexedLessThan<int64>(kTestValues));
   std::sort(position_ordering.begin(), position_ordering.end(),
             IndexedLessThan<UniquePosition, PositionLessThan>(positions));
   EXPECT_NE(original_ordering, int64_ordering);
   EXPECT_EQ(int64_ordering, position_ordering);
 }
 
 }  // namespace
 
 }  // namespace syncer