[Sync] Move //sync to //components/sync.

components/sync/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 "components/sync/base/unique_position.h"
 
 #include <stddef.h>
 #include <stdint.h>
 
 #include <algorithm>
 #include <limits>
 
 #include "base/logging.h"
 #include "base/rand_util.h"
 #include "base/stl_util.h"
 #include "base/strings/string_number_conversions.h"
-#include "sync/protocol/unique_position.pb.h"
+#include "components/sync/protocol/unique_position.pb.h"
 #include "third_party/zlib/zlib.h"
 
 namespace syncer {
 
 const size_t UniquePosition::kSuffixLength = 28;
 const size_t UniquePosition::kCompressBytesThreshold = 128;
 
 // 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
-      && suffix[kSuffixLength-1] != 0;
+  return suffix.length() == kSuffixLength && suffix[kSuffixLength - 1] != 0;
 }
 
 // static.
 bool UniquePosition::IsValidBytes(const std::string& bytes) {
   // 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;
+  return bytes.length() >= kSuffixLength && bytes[bytes.length() - 1] != 0;
 }
 
 // static.
 std::string UniquePosition::RandomSuffix() {
   // Users random data for all but the last byte.  The last byte must not be
   // zero.  We arbitrarily set it to 0x7f.
   return base::RandBytesAsString(kSuffixLength - 1) + "\x7f";
 }
 
 // static.
@@ skipping 17 matching lines @@
     int result = uncompress(
         reinterpret_cast<Bytef*>(string_as_array(&un_gzipped)),
         &uncompressed_len,
         reinterpret_cast<const Bytef*>(proto.compressed_value().data()),
         proto.compressed_value().size());
     if (result != Z_OK) {
       DLOG(ERROR) << "Unzip failed " << result;
       return UniquePosition::CreateInvalid();
     }
     if (uncompressed_len != proto.uncompressed_length()) {
-      DLOG(ERROR)
-          << "Uncompressed length " << uncompressed_len
-          << " did not match specified length " << proto.uncompressed_length();
+      DLOG(ERROR) << "Uncompressed length " << uncompressed_len
+                  << " did not match specified length "
+                  << proto.uncompressed_length();
       return UniquePosition::CreateInvalid();
     }
     return UniquePosition(Compress(un_gzipped));
   } else {
     return UniquePosition::CreateInvalid();
   }
 }
 
 // static.
 UniquePosition UniquePosition::FromInt64(int64_t x, const std::string& suffix) {
   uint64_t y = static_cast<uint64_t>(x);
   y ^= 0x8000000000000000ULL;  // Make it non-negative.
   std::string bytes(8, 0);
   for (int i = 7; i >= 0; --i) {
     bytes[i] = static_cast<uint8_t>(y);
     y >>= 8;
   }
   return UniquePosition(bytes + suffix, suffix);
 }
 
 // static.
-UniquePosition UniquePosition::InitialPosition(
-    const std::string& suffix) {
+UniquePosition UniquePosition::InitialPosition(const std::string& suffix) {
   DCHECK(IsValidSuffix(suffix));
   return UniquePosition(suffix, suffix);
 }
 
 // static.
-UniquePosition UniquePosition::Before(
-    const UniquePosition& x,
-    const std::string& suffix) {
+UniquePosition UniquePosition::Before(const UniquePosition& x,
+                                      const std::string& suffix) {
   DCHECK(IsValidSuffix(suffix));
   DCHECK(x.IsValid());
-  const std::string& before = FindSmallerWithSuffix(
-      Uncompress(x.compressed_), suffix);
+  const std::string& before =
+      FindSmallerWithSuffix(Uncompress(x.compressed_), suffix);
   return UniquePosition(before + suffix, suffix);
 }
 
 // static.
-UniquePosition UniquePosition::After(
-    const UniquePosition& x,
-    const std::string& suffix) {
+UniquePosition UniquePosition::After(const UniquePosition& x,
+                                     const std::string& suffix) {
   DCHECK(IsValidSuffix(suffix));
   DCHECK(x.IsValid());
-  const std::string& after = FindGreaterWithSuffix(
-      Uncompress(x.compressed_), suffix);
+  const std::string& after =
+      FindGreaterWithSuffix(Uncompress(x.compressed_), suffix);
   return UniquePosition(after + suffix, suffix);
 }
 
 // static.
-UniquePosition UniquePosition::Between(
-    const UniquePosition& before,
-    const UniquePosition& after,
-    const std::string& suffix) {
+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(
-      Uncompress(before.compressed_),
-      Uncompress(after.compressed_),
-      suffix);
+      Uncompress(before.compressed_), Uncompress(after.compressed_), suffix);
   return UniquePosition(mid + suffix, suffix);
 }
 
 UniquePosition::UniquePosition() : is_valid_(false) {}
 
 bool UniquePosition::LessThan(const UniquePosition& other) const {
   DCHECK(this->IsValid());
   DCHECK(other.IsValid());
 
   return compressed_ < other.compressed_;
@@ skipping 62 matching lines @@
   debug_string.append(", compressed: " + compressed_string);
   return debug_string;
 }
 
 std::string UniquePosition::GetSuffixForTest() const {
   const std::string bytes = Uncompress(compressed_);
   const size_t prefix_len = bytes.length() - kSuffixLength;
   return bytes.substr(prefix_len, std::string::npos);
 }
 
-std::string UniquePosition::FindSmallerWithSuffix(
-    const std::string& reference,
-    const std::string& suffix) {
+std::string UniquePosition::FindSmallerWithSuffix(const std::string& reference,
+                                                  const std::string& suffix) {
   size_t ref_zeroes = reference.find_first_not_of('\0');
   size_t suffix_zeroes = suffix.find_first_not_of('\0');
 
   // Neither of our inputs are allowed to have trailing zeroes, so the following
   // must be true.
   DCHECK_NE(ref_zeroes, std::string::npos);
   DCHECK_NE(suffix_zeroes, std::string::npos);
 
   if (suffix_zeroes > ref_zeroes) {
     // Implies suffix < ref.
@@ skipping 10 matching lines @@
     return std::string(ref_zeroes - suffix_zeroes + 1, '\0');
   } else {
     // Prepend zeroes to match those in the |reference|, then something smaller
     // than the first non-zero digit in |reference|.
     char lt_digit = static_cast<uint8_t>(reference[ref_zeroes]) / 2;
     return std::string(ref_zeroes, '\0') + lt_digit;
   }
 }
 
 // static
-std::string UniquePosition::FindGreaterWithSuffix(
-    const std::string& reference,
-    const std::string& suffix) {
+std::string UniquePosition::FindGreaterWithSuffix(const std::string& reference,
+                                                  const std::string& suffix) {
   size_t ref_FFs =
       reference.find_first_not_of(std::numeric_limits<uint8_t>::max());
   size_t suffix_FFs =
       suffix.find_first_not_of(std::numeric_limits<uint8_t>::max());
 
   if (ref_FFs == std::string::npos) {
     ref_FFs = reference.length();
   }
   if (suffix_FFs == std::string::npos) {
     suffix_FFs = suffix.length();
@@ skipping 19 matching lines @@
     // than the first non-FF digit in |reference|.
     char gt_digit = static_cast<uint8_t>(reference[ref_FFs]) +
                     (std::numeric_limits<uint8_t>::max() -
                      static_cast<uint8_t>(reference[ref_FFs]) + 1) /
                         2;
     return std::string(ref_FFs, std::numeric_limits<uint8_t>::max()) + gt_digit;
   }
 }
 
 // static
-std::string UniquePosition::FindBetweenWithSuffix(
-    const std::string& before,
-    const std::string& after,
-    const std::string& suffix) {
+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);
 
   std::string mid;
 
   // Sometimes our suffix puts us where we want to be.
   if (before < suffix && suffix < after) {
     return std::string();
   }
 
   size_t i = 0;
-  for ( ; i < std::min(before.length(), after.length()); ++i) {
+  for (; i < std::min(before.length(), after.length()); ++i) {
     uint8_t a_digit = before[i];
     uint8_t b_digit = after[i];
 
     if (b_digit - a_digit >= 2) {
-      mid.push_back(a_digit + (b_digit - a_digit)/2);
+      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 (before.substr(i+1) < suffix && suffix < after.substr(i+1)) {
+      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.
 
       // 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));
+      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) {
+      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));
+        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)
     : compressed_(internal_rep),
-      is_valid_(IsValidBytes(Uncompress(internal_rep))) {
-}
+      is_valid_(IsValidBytes(Uncompress(internal_rep))) {}
 
-UniquePosition::UniquePosition(
-    const std::string& uncompressed,
-    const std::string& suffix)
-  : compressed_(Compress(uncompressed)),
-    is_valid_(IsValidBytes(uncompressed)) {
+UniquePosition::UniquePosition(const std::string& uncompressed,
+                               const std::string& suffix)
+    : compressed_(Compress(uncompressed)),
+      is_valid_(IsValidBytes(uncompressed)) {
   DCHECK(uncompressed.rfind(suffix) + kSuffixLength == uncompressed.length());
   DCHECK(IsValidSuffix(suffix));
   DCHECK(IsValid());
 }
 
 // On custom compression:
 //
 // Let C(x) be the compression function and U(x) be the uncompression function.
 //
 // This compression scheme has a few special properties.  For one, it is
@@ skipping 110 matching lines @@
   } else {
     length = encoded_length;
   }
 
   return length;
 }
 
 // A series of four identical chars at the beginning of a block indicates
 // the beginning of a repeated character block.
 static bool IsRepeatedCharPrefix(const std::string& chars, size_t start_index) {
-  return chars[start_index] == chars[start_index+1]
-      && chars[start_index] == chars[start_index+2]
-      && chars[start_index] == chars[start_index+3];
+  return chars[start_index] == chars[start_index + 1] &&
+         chars[start_index] == chars[start_index + 2] &&
+         chars[start_index] == chars[start_index + 3];
 }
 
 }  // namespace
 
 // static
 // Wraps the CompressImpl function with a bunch of DCHECKs.
 std::string UniquePosition::Compress(const std::string& str) {
   DCHECK(IsValidBytes(str));
   std::string compressed = CompressImpl(str);
   DCHECK(IsValidCompressed(compressed));
   DCHECK_EQ(str, Uncompress(compressed));
   return compressed;
 }
 
 // static
 // Performs the order preserving run length compression of a given input string.
 std::string UniquePosition::CompressImpl(const std::string& str) {
   std::string output;
 
   // The compressed length will usually be at least as long as the suffix (28),
   // since the suffix bytes are mostly random.  Most are a few bytes longer; a
   // small few are tens of bytes longer.  Some early tests indicated that
   // roughly 99% had length 40 or smaller.  We guess that pre-sizing for 48 is a
   // good trade-off, but that has not been confirmed through profiling.
   output.reserve(48);
 
   // Each loop iteration will consume 8, or N bytes, where N >= 4 and is the
   // length of a string of identical digits starting at i.
-  for (size_t i = 0; i < str.length(); ) {
+  for (size_t i = 0; i < str.length();) {
     if (i + 4 <= str.length() && IsRepeatedCharPrefix(str, i)) {
       // Four identical bytes in a row at this position means that we must start
       // a repeated character block.  Begin by outputting those four bytes.
       output.append(str, i, 4);
 
       // Determine the size of the run.
       const char rep_digit = str[i];
-      const size_t runs_until = str.find_first_not_of(rep_digit, i+4);
+      const size_t runs_until = str.find_first_not_of(rep_digit, i + 4);
 
       // Handle the 'runs until end' special case specially.
       size_t run_length;
       bool encode_high;  // True if the next byte is greater than |rep_digit|.
       if (runs_until == std::string::npos) {
         run_length = str.length() - i;
         encode_high = false;
       } else {
         run_length = runs_until - i;
         encode_high = static_cast<uint8_t>(str[runs_until]) >
@@ skipping 40 matching lines @@
 
 bool UniquePosition::IsValidCompressed(const std::string& str) {
   for (size_t i = 0; i + 8 <= str.length(); i += 8) {
     if (IsRepeatedCharPrefix(str, i)) {
       uint32_t count = ReadEncodedRunLength(str, i + 4);
       if (count < 4) {
         // A repeated character block should at least represent the four
         // characters that started it.
         return false;
       }
-      if (str[i] == str[i+4]) {
+      if (str[i] == str[i + 4]) {
         // Does the next digit after a count match the repeated character?  Then
         // this is not the highest possible count.
         return false;
       }
     }
   }
   // We don't bother looking for the existence or checking the validity of
   // any partial blocks.  There's no way they could be invalid anyway.
   return true;
 }
 
 }  // namespace syncer