WIP: The Bookmark Position Megapatch

sync/internal_api/public/base/unique_position.cc

Index: sync/internal_api/public/base/unique_position.cc
diff --git a/sync/internal_api/public/base/unique_position.cc b/sync/internal_api/public/base/unique_position.cc
index c3cfd59e3a4f0edad782b21fdcf1db68df64e410..8f3c0a70bf04c69648fab974529ed86d3fe6ab30 100644
--- a/sync/internal_api/public/base/unique_position.cc
+++ b/sync/internal_api/public/base/unique_position.cc
@@ -5,11 +5,12 @@
 #include "sync/internal_api/public/base/unique_position.h"
 
 #include "base/logging.h"
-#include "base/rand_util.h"
 #include "base/string_number_conversions.h"
 
 namespace syncer {
 
+const size_t UniquePosition::kSuffixLength = 28;
+
 // static.
 bool UniquePosition::IsValidSuffix(const std::string& suffix) {
   // The suffix must be exactly the specified length, otherwise unique suffixes
@@ -20,8 +21,13 @@ bool UniquePosition::IsValidSuffix(const std::string& suffix) {
 
 // static.
 bool UniquePosition::IsValidBytes(const std::string& bytes) {
-  return bytes.length() > kSuffixLength
-      && bytes[bytes.length()-1] == kTerminatorByte;
+  // The first condition ensures that our suffix uniqueness is sufficient to
+  // guarantee position uniqueness.  Otherwise, it's possible the end of some
+  // prefix + some short suffix == some long suffix.
+  // The second condition ensures that FindSmallerWithSuffix can always return a
+  // result.
+  return bytes.length() >= kSuffixLength
+      && bytes[bytes.length()-1] != 0;
 }
 
 // static.
@@ -35,7 +41,6 @@ UniquePosition UniquePosition::CreateInvalid() {
 UniquePosition UniquePosition::FromBytes(
     const std::string& bytes) {
   UniquePosition result(bytes);
-  DCHECK(result.IsValid());
   return result;
 }
 
@@ -93,31 +98,6 @@ UniquePosition UniquePosition::Between(
   return UniquePosition(mid, suffix);
 }
 
-// static.
-const std::string UniquePosition::GenerateUniqueSuffix() {
-  return base::RandBytesAsString(kSuffixLength);
-}
-
-// static.
-const std::string UniquePosition::GenerateBookmarkSuffix(
-    const std::string& decoded_originator_cache_guid,
-    int64 numeric_originator_item_id) {
-  std::string result(8, 0);
-
-  // The first 8 bytes come from the originator id.
-  int64 byte_iterator = numeric_originator_item_id;
-  for (int i = 7; i >= 0; --i) {
-    result[i] = static_cast<uint8>(byte_iterator);
-    byte_iterator >>= 8;
-  }
-
-  // The next 16 bytes come from the decoded cache guid.
-  DCHECK_EQ(16u, decoded_originator_cache_guid.length());
-  result.append(decoded_originator_cache_guid);
-
-  return result;
-}
-
 UniquePosition::UniquePosition() : is_valid_(false) { };
 
 bool UniquePosition::LessThan(const UniquePosition& other) const {
@@ -170,13 +150,10 @@ std::string UniquePosition::ToDebugString() const {
 std::string UniquePosition::FindSmallerWithSuffix(
     const std::string& reference,
     const std::string& suffix) {
-  // When comparing, we need to take into account the terminator that will be
-  // appended to the suffix when this is made into a UniquePosition.
-  const std::string suffixFF = suffix + kTerminatorByte;
   std::string ret;
 
   // Does our suffix alone place us where we want to be?
-  if (suffixFF < reference) {
+  if (suffix < reference) {
     return "";
   }
 
@@ -190,7 +167,7 @@ std::string UniquePosition::FindSmallerWithSuffix(
       // We failed to differentiate ourselves with this digit.  But maybe the we
       // can append the suffix at this point and get the position we're looking
       // for that way.
-      if (suffixFF < reference.substr(i+1)) {
+      if (suffix < reference.substr(i+1)) {
         return ret;
       }
     }
@@ -207,35 +184,31 @@ std::string UniquePosition::FindSmallerWithSuffix(
 std::string UniquePosition::FindGreaterWithSuffix(
     const std::string& reference,
     const std::string& suffix) {
-  // When comparing, we need to take into account the terminator that will be
-  // appended to the suffix when this is made into a UniquePosition.
-  const std::string suffixFF = suffix + kTerminatorByte;
-
   std::string ret;
 
   // Does our suffix alone place us where we want to be?
-  if (reference < suffixFF) {
+  if (reference < suffix) {
     return "";
   }
 
   for (size_t i = 0; i < reference.length(); ++i) {
     const uint8 digit = reference[i];
-    if (digit != 255) {
-      ret.push_back((digit+256U)/2U);
+    if (digit != kuint8max) {
+      ret.push_back(digit + (kuint8max - digit + 1)/2);
       return ret;
     } else {
-      ret.push_back(255);
+      ret.push_back(kuint8max);
       // We failed to differentiate ourselves with this digit.  But maybe the we
       // can append the suffix at this point and get the position we're looking
       // for that way.
-      if (reference.substr(i+1) < suffixFF) {
+      if (reference.substr(i+1) < suffix) {
         return ret;
       }
     }
   }
 
-  // Still here?  Then we must increase our length in order to exceed before.
-  ret.push_back(255);
+  // Still here?  Then we must increase our length in order to exceed reference.
+  ret.push_back(kuint8max);
 
   DCHECK_LT(reference, ret);
   return ret;
@@ -250,14 +223,10 @@ std::string UniquePosition::FindBetweenWithSuffix(
   DCHECK_NE(before, after);
   DCHECK_LT(before, after);
 
-  // When comparing, we need to take into account the terminator that will be
-  // appended when this is made into a UniquePosition.
-  const std::string suffixFF = suffix + kTerminatorByte;
-
   std::string mid;
 
   // Sometimes our suffix puts us where we want to be.
-  if (before < suffixFF && suffixFF < after) {
+  if (before < suffix && suffix < after) {
     return "";
   }
 
@@ -267,14 +236,14 @@ std::string UniquePosition::FindBetweenWithSuffix(
     uint8 b_digit = after[i];
 
     if (b_digit - a_digit >= 2) {
-      mid.push_back((b_digit + a_digit) / 2U);
+      mid.push_back(a_digit + (b_digit - a_digit)/2);
       return mid;
     } else if (a_digit == b_digit) {
       mid.push_back(a_digit);
 
       // Both strings are equal so far.  Will appending the suffix at this point
       // give us the comparison we're looking for?
-      if (suffixFF < before.substr(i, 0) && after.substr(i, 0) < suffixFF) {
+      if (before.substr(i+1) < suffix && suffix < after.substr(i+1)) {
         return mid;
       }
     } else {
@@ -328,13 +297,12 @@ std::string UniquePosition::FindBetweenWithSuffix(
 UniquePosition::UniquePosition(const std::string& internal_rep)
     : bytes_(internal_rep),
       is_valid_(IsValidBytes(bytes_)) {
-  DCHECK(IsValid());
 }
 
 UniquePosition::UniquePosition(
     const std::string& prefix,
     const std::string& suffix)
-  : bytes_(prefix + suffix + kTerminatorByte),
+  : bytes_(prefix + suffix),
     is_valid_(IsValidBytes(bytes_)) {
   DCHECK(IsValidSuffix(suffix));
   DCHECK(IsValid());