WIP: The Bookmark Position Megapatch

sync/internal_api/public/base/unique_position.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 "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
   // are not sufficient to guarantee unique positions (because prefix + suffix
   // == p + refixsuffix).
   return suffix.length() == kSuffixLength;
 }
 
 // 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.
 UniquePosition UniquePosition::CreateInvalid() {
   UniquePosition pos;
   DCHECK(!pos.IsValid());
   return pos;
 }
 
 // static.
 UniquePosition UniquePosition::FromBytes(
     const std::string& bytes) {
   UniquePosition result(bytes);
-  DCHECK(result.IsValid());
   return result;
 }
 
 // static.
 UniquePosition UniquePosition::FromInt64(
     int64 x, const std::string& suffix) {
   uint64 y = static_cast<uint64>(x);
   y ^= 0x8000000000000000ULL; // Make it non-negative.
   std::string bytes(8, 0);
   for (int i = 7; i >= 0; --i) {
@@ skipping 37 matching lines @@
     const std::string& suffix) {
   DCHECK(before.IsValid());
   DCHECK(after.IsValid());
   DCHECK(before.LessThan(after));
   DCHECK(IsValidSuffix(suffix));
   const std::string& mid =
       FindBetweenWithSuffix(before.bytes_, after.bytes_, suffix);
   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 {
   DCHECK(this->IsValid());
   DCHECK(other.IsValid());
   return bytes_ < other.bytes_;
 }
 
 bool UniquePosition::Equals(const UniquePosition& other) const {
   if (!this->IsValid() && !other.IsValid())
@@ skipping 32 matching lines @@
   std::string debug_string = base::HexEncode(bytes_.data(), bytes_.length());
   if (!IsValid()) {
     debug_string = "INVALID[" + debug_string + "]";
   }
   return debug_string;;
 }
 
 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 "";
   }
 
   for (size_t i = 0; i < reference.length(); ++i) {
     const uint8 digit = reference[i];
     if (digit != 0) {
       ret.push_back(digit/2);
       return ret;
     } else {
       ret.push_back(0);
       // 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;
       }
     }
   }
 
   // Was it 0x00 all the way to the end?  Then we can't insert before it.
   // That's why we enforce that all positions should end with a max digit,
   // which should ensure we never end up here.
   NOTREACHED();
   return "";
 }
 
 // static
 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;
 }
 
 // static
 std::string UniquePosition::FindBetweenWithSuffix(
     const std::string& before,
     const std::string& after,
     const std::string& suffix) {
   DCHECK(IsValidSuffix(suffix));
   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 "";
   }
 
   size_t i = 0;
   for ( ; i < std::min(before.length(), after.length()); ++i) {
     uint8 a_digit = before[i];
     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 {
       DCHECK_EQ(b_digit - a_digit, 1);  // Implied by above if branches.
 
       // The two options are off by one digit.  The choice of whether to round
       // up or down here will have consequences on what we do with the remaining
       // digits.  Exploring both options is an optimization and is not required
       // for the correctness of this algorithm.
 
@@ skipping 33 matching lines @@
   // value, will make |before| < |mid|.  Therefore, the following will get us a
   // valid position.
 
   mid.append(FindSmallerWithSuffix(after.substr(i), suffix));
   return mid;
 }
 
 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());
 }
 
 }  // namespace syncer