WIP: The Bookmark Position Megapatch

sync/internal_api/public/base/unique_position_unittest.cc

Index: sync/internal_api/public/base/unique_position_unittest.cc
diff --git a/sync/internal_api/public/base/unique_position_unittest.cc b/sync/internal_api/public/base/unique_position_unittest.cc
index 001a57558a0a8b75a3afb1cf17baf552fa524284..1afe29415e78a5a36cbc9a7f22237071d55fa7a7 100644
--- a/sync/internal_api/public/base/unique_position_unittest.cc
+++ b/sync/internal_api/public/base/unique_position_unittest.cc
@@ -7,8 +7,11 @@
 #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 {
@@ -17,13 +20,13 @@ 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();
   }
@@ -280,6 +283,116 @@ TEST_P(PositionInsertTest, StressRightInsertBetween) {
   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,
@@ -288,15 +401,18 @@ INSTANTIATE_TEST_CASE_P(NormalSuffix, PositionInsertTest,
                         ::testing::Values(kNormalSuffix));
 
 class PositionFromIntTest : public UniquePositionTest {
- 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);
+ public:
+  PositionFromIntTest()
+      : generator_(std::string(kCacheGuidStr1, arraysize(kCacheGuidStr1)-1)) {
+  }
 
-    return UniquePosition::GenerateBookmarkSuffix(guid, item_id);
+ protected:
+  std::string NextSuffix() {
+    return generator_.NextSuffix();
   }
+
+ private:
+  SuffixGenerator generator_;
 };
 
 const int64 kTestValues[] = {
@@ -330,7 +446,7 @@ 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();
   }
 }
@@ -339,7 +455,7 @@ 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;
   }
@@ -366,7 +482,7 @@ TEST_F(PositionFromIntTest, ConsistentOrdering) {
   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;
   }