Initial UniquePositions implementation

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
new file mode 100644
index 0000000000000000000000000000000000000000..c3cfd59e3a4f0edad782b21fdcf1db68df64e410
--- /dev/null
+++ b/sync/internal_api/public/base/unique_position.cc
@@ -0,0 +1,343 @@
+// 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 {
+
+// 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;
+}
+
+// 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) {
+    bytes[i] = static_cast<uint8>(y);
+    y >>= 8;
+  }
+  return UniquePosition(bytes, suffix);
+}
+
+// static.
+UniquePosition UniquePosition::InitialPosition(
+    const std::string& suffix) {
+  DCHECK(IsValidSuffix(suffix));
+  return UniquePosition("", suffix);
+}
+
+// static.
+UniquePosition UniquePosition::Before(
+    const UniquePosition& x,
+    const std::string& suffix) {
+  DCHECK(IsValidSuffix(suffix));
+  DCHECK(x.IsValid());
+  const std::string& before = FindSmallerWithSuffix(x.bytes_, suffix);
+  return UniquePosition(before, suffix);
+}
+
+// static.
+UniquePosition UniquePosition::After(
+    const UniquePosition& x,
+    const std::string& suffix) {
+  DCHECK(IsValidSuffix(suffix));
+  DCHECK(x.IsValid());
+  const std::string& after = FindGreaterWithSuffix(x.bytes_, suffix);
+  return UniquePosition(after, suffix);
+}
+
+// static.
+UniquePosition UniquePosition::Between(
+    const UniquePosition& before,
+    const UniquePosition& after,
+    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())
+    return true;
+
+  return bytes_ == other.bytes_;
+}
+
+const std::string& UniquePosition::ToInternalValue() const {
+  return bytes_;
+}
+
+int64 UniquePosition::ToInt64() const {
+  uint64 y = 0;
+  const std::string& s = ToInternalValue();
+  size_t l = sizeof(int64);
+  if (s.length() < l) {
+    NOTREACHED();
+    l = s.length();
+  }
+  for (size_t i = 0; i < l; ++i) {
+    const uint8 byte = s[l - i - 1];
+    y |= static_cast<uint64>(byte) << (i * 8);
+  }
+  y ^= 0x8000000000000000ULL;
+  // This is technically implementation-defined if y > INT64_MAX, so
+  // we're assuming that we're on a twos-complement machine.
+  return static_cast<int64>(y);
+}
+
+bool UniquePosition::IsValid() const {
+  return is_valid_;
+}
+
+std::string UniquePosition::ToDebugString() const {
+  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) {
+    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)) {
+        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) {
+    return "";
+  }
+
+  for (size_t i = 0; i < reference.length(); ++i) {
+    const uint8 digit = reference[i];
+    if (digit != 255) {

[akalin, 2012/12/18 22:38:20]

use kuint8max

[rlarocque, 2012/12/18 23:51:09]

Done.

+      ret.push_back((digit+256U)/2U);

[akalin, 2012/12/18 22:38:20]

prefer "digit + (kuint8max - digit + 1) / 2" as it's easier to see that that
expression is > digit

[rlarocque, 2012/12/18 23:51:09]

Done.

+      return ret;
+    } else {
+      ret.push_back(255);

[akalin, 2012/12/18 22:38:20]

kuint8max

[rlarocque, 2012/12/18 23:51:09]

Done.

+      // 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) {
+        return ret;
+      }
+    }
+  }
+
+  // Still here?  Then we must increase our length in order to exceed before.
+  ret.push_back(255);

[akalin, 2012/12/18 22:38:20]

here too

also before -> reference

[rlarocque, 2012/12/18 23:51:09]

Done.

+
+  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) {
+    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);

[akalin, 2012/12/17 18:47:45]

can overflow?  perhaps a_digit + (b_digit - a_digit) / 2?

[rlarocque, 2012/12/18 23:51:09]

Done.

+      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) {

[akalin, 2012/12/18 22:38:20]

hey how does this work?  you want the substring of before from i to the end,
right?  I don't think 0 is the right value to use (it just returns the empty
string)

also, don't you want i + 1?  and "before.substr(...) < suffixFF && suffixFF <
after.substr(...)"?  I'm confused...

[rlarocque, 2012/12/18 23:51:09]

Yep, that's very wrong.

We can get away with it because suffixFF < "" always returns false, so we never
enter this if branch.  This makes the algorithm less effective at finding the
shortest possible string, but the strings it eventually does return will be
between |before| and |after|.

For some reason, fixing this leads to slightly longer positions being generated
in the stress tests.  

+        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.
+
+      // Option A: Round down the current digit.  This makes our |mid| <
+      // |after|, no matter what we append afterwards.  We then focus on
+      // appending digits until |mid| > |before|.
+      std::string mid_a = mid;
+      mid_a.push_back(a_digit);
+      mid_a.append(FindGreaterWithSuffix(before.substr(i+1), suffix));
+
+      // Option B: Round up the current digit.  This makes our |mid| > |before|,
+      // no matter what we append afterwards.  We then focus on appending digits
+      // until |mid| < |after|.  Note that this option may not be viable if the
+      // current digit is the last one in |after|, so we skip the option in that
+      // case.
+      if (after.length() > i+1) {
+        std::string mid_b = mid;
+        mid_b.push_back(b_digit);
+        mid_b.append(FindSmallerWithSuffix(after.substr(i+1), suffix));
+
+        // Does this give us a shorter position value?  If so, use it.
+        if (mid_b.length() < mid_a.length()) {
+          return mid_b;
+        }
+      }
+      return mid_a;
+    }
+  }
+
+  // If we haven't found a midpoint yet, the following must be true:
+  DCHECK_EQ(before.substr(0, i), after.substr(0, i));
+  DCHECK_EQ(before, mid);
+  DCHECK_LT(before.length(), after.length());
+
+  // We know that we'll need to append at least one more byte to |mid| in the
+  // process of making it < |after|.  Appending any digit, regardless of the
+  // 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),
+    is_valid_(IsValidBytes(bytes_)) {
+  DCHECK(IsValidSuffix(suffix));
+  DCHECK(IsValid());
+}
+
+}  // namespace syncer