src/sync/internal_api/public/base/ordinal_unittest.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "base/basictypes.h"
   6 #include "sync/internal_api/public/base/ordinal.h"
   7 #include "testing/gtest/include/gtest/gtest.h"
   8
   9 #include <algorithm>
  10 #include <cctype>
  11 #include <cstddef>
  12 #include <string>
  13 #include <vector>
  14
  15 namespace syncer {
  16
  17 namespace {
  18
  19 struct TestOrdinalTraits {
  20   static const uint8 kZeroDigit = '0';
  21   static const uint8 kMaxDigit = '3';
  22   static const size_t kMinLength = 1;
  23 };
  24
  25 struct LongOrdinalTraits {
  26   static const uint8 kZeroDigit = '0';
  27   static const uint8 kMaxDigit = '9';
  28   static const size_t kMinLength = 5;
  29 };
  30
  31 struct LargeOrdinalTraits {
  32   static const uint8 kZeroDigit = 0;
  33   static const uint8 kMaxDigit = kuint8max;
  34   static const size_t kMinLength = 1;
  35 };
  36
  37 typedef Ordinal<TestOrdinalTraits> TestOrdinal;
  38 typedef Ordinal<LongOrdinalTraits> LongOrdinal;
  39 typedef Ordinal<LargeOrdinalTraits> LargeOrdinal;
  40
  41 COMPILE_ASSERT(TestOrdinal::kZeroDigit == '0',
  42                TestOrdinalHasCorrectZeroDigit);
  43 COMPILE_ASSERT(TestOrdinal::kOneDigit == '1',
  44                TestOrdinalHasCorrectOneDigit);
  45 COMPILE_ASSERT(TestOrdinal::kMidDigit == '2',
  46                TestOrdinalHasCorrectMidDigit);
  47 COMPILE_ASSERT(TestOrdinal::kMaxDigit == '3',
  48                TestOrdinalHasCorrectMaxDigit);
  49 COMPILE_ASSERT(TestOrdinal::kMidDigitValue == 2,
  50                TestOrdinalHasCorrectMidDigitValue);
  51 COMPILE_ASSERT(TestOrdinal::kMaxDigitValue == 3,
  52                TestOrdinalHasCorrectMaxDigitValue);
  53 COMPILE_ASSERT(TestOrdinal::kRadix == 4,
  54                TestOrdinalHasCorrectRadix);
  55
  56 COMPILE_ASSERT(LongOrdinal::kZeroDigit == '0',
  57                LongOrdinalkZeroDigit_incorrect);
  58 COMPILE_ASSERT(LongOrdinal::kOneDigit == '1',
  59                LongOrdinalkOneDigit_incorrect);
  60 COMPILE_ASSERT(LongOrdinal::kMidDigit == '5',
  61                LongOrdinalkMidDigit_incorrect);
  62 COMPILE_ASSERT(LongOrdinal::kMaxDigit == '9',
  63                LongOrdinalkMaxDigit_incorrect);
  64 COMPILE_ASSERT(LongOrdinal::kMidDigitValue == 5,
  65                LongOrdinalkMidDigitValue_incorrect);
  66 COMPILE_ASSERT(LongOrdinal::kMaxDigitValue == 9,
  67                LongOrdinalkMaxDigitValue_incorrect);
  68 COMPILE_ASSERT(LongOrdinal::kRadix == 10,
  69                LongOrdinalkRadix_incorrect);
  70
  71 COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kZeroDigit) == '\x00',
  72                LargeOrdinalkZeroDigit_incorrect);
  73 COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kOneDigit) == '\x01',
  74                LargeOrdinalkOneDigit_incorrect);
  75 COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kMidDigit) == '\x80',
  76                LargeOrdinalkMidDigit_incorrect);
  77 COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kMaxDigit) == '\xff',
  78                LargeOrdinalkMaxDigit_incorrect);
  79 COMPILE_ASSERT(LargeOrdinal::kMidDigitValue == 128,
  80                LargeOrdinalkMidDigitValue_incorrect);
  81 COMPILE_ASSERT(LargeOrdinal::kMaxDigitValue == 255,
  82                LargeOrdinalkMaxDigitValue_incorrect);
  83 COMPILE_ASSERT(LargeOrdinal::kRadix == 256,
  84                LargeOrdinalkRadix_incorrect);
  85
  86 // Create Ordinals that satisfy all but one criterion for validity.
  87 // IsValid() should return false for all of them.
  88 TEST(Ordinal, Invalid) {
  89   // Length criterion.
  90   EXPECT_FALSE(TestOrdinal(std::string()).IsValid());
  91   EXPECT_FALSE(LongOrdinal("0001").IsValid());
  92
  93   const char kBeforeZero[] = { '0' - 1, '\0' };
  94   const char kAfterNine[] = { '9' + 1, '\0' };
  95
  96   // Character criterion.
  97   EXPECT_FALSE(TestOrdinal(kBeforeZero).IsValid());
  98   EXPECT_FALSE(TestOrdinal("4").IsValid());
  99   EXPECT_FALSE(LongOrdinal(std::string("0000") + kBeforeZero).IsValid());
 100   EXPECT_FALSE(LongOrdinal(std::string("0000") + kAfterNine).IsValid());
 101
 102   // Zero criterion.
 103   EXPECT_FALSE(TestOrdinal("0").IsValid());
 104   EXPECT_FALSE(TestOrdinal("00000").IsValid());
 105
 106   // Trailing zero criterion.
 107   EXPECT_FALSE(TestOrdinal("10").IsValid());
 108   EXPECT_FALSE(TestOrdinal("111110").IsValid());
 109 }
 110
 111 // Create Ordinals that satisfy all criteria for validity.
 112 // IsValid() should return true for all of them.
 113 TEST(Ordinal, Valid) {
 114   // Length criterion.
 115   EXPECT_TRUE(TestOrdinal("1").IsValid());
 116   EXPECT_TRUE(LongOrdinal("10000").IsValid());
 117 }
 118
 119 // Create Ordinals from CreateInitialOrdinal.  They should be valid
 120 // and close to the middle of the range.
 121 TEST(Ordinal, CreateInitialOrdinal) {
 122   const TestOrdinal& ordinal1 = TestOrdinal::CreateInitialOrdinal();
 123   const LongOrdinal& ordinal2 = LongOrdinal::CreateInitialOrdinal();
 124   ASSERT_TRUE(ordinal1.IsValid());
 125   ASSERT_TRUE(ordinal2.IsValid());
 126   EXPECT_TRUE(ordinal1.Equals(TestOrdinal("2")));
 127   EXPECT_TRUE(ordinal2.Equals(LongOrdinal("50000")));
 128 }
 129
 130 // Create an invalid and a valid Ordinal.  EqualsOrBothInvalid should
 131 // return true if called reflexively and false otherwise.
 132 TEST(Ordinal, EqualsOrBothInvalid) {
 133   const TestOrdinal& valid_ordinal = TestOrdinal::CreateInitialOrdinal();
 134   const TestOrdinal invalid_ordinal;
 135
 136   EXPECT_TRUE(valid_ordinal.EqualsOrBothInvalid(valid_ordinal));
 137   EXPECT_TRUE(invalid_ordinal.EqualsOrBothInvalid(invalid_ordinal));
 138   EXPECT_FALSE(invalid_ordinal.EqualsOrBothInvalid(valid_ordinal));
 139   EXPECT_FALSE(valid_ordinal.EqualsOrBothInvalid(invalid_ordinal));
 140 }
 141
 142 // Create three Ordinals in order.  LessThan should return values
 143 // consistent with that order.
 144 TEST(Ordinal, LessThan) {
 145   const TestOrdinal small_ordinal("1");
 146   const TestOrdinal middle_ordinal("2");
 147   const TestOrdinal big_ordinal("3");
 148
 149   EXPECT_FALSE(small_ordinal.LessThan(small_ordinal));
 150   EXPECT_TRUE(small_ordinal.LessThan(middle_ordinal));
 151   EXPECT_TRUE(small_ordinal.LessThan(big_ordinal));
 152
 153   EXPECT_FALSE(middle_ordinal.LessThan(small_ordinal));
 154   EXPECT_FALSE(middle_ordinal.LessThan(middle_ordinal));
 155   EXPECT_TRUE(middle_ordinal.LessThan(big_ordinal));
 156
 157   EXPECT_FALSE(big_ordinal.LessThan(small_ordinal));
 158   EXPECT_FALSE(big_ordinal.LessThan(middle_ordinal));
 159   EXPECT_FALSE(big_ordinal.LessThan(big_ordinal));
 160 }
 161
 162 // Create two single-digit ordinals with byte values 0 and 255.  The
 163 // former should compare as less than the latter, even though the
 164 // native char type may be signed.
 165 TEST(Ordinal, LessThanLarge) {
 166   const LargeOrdinal small_ordinal("\x01");
 167   const LargeOrdinal big_ordinal("\xff");
 168
 169   EXPECT_TRUE(small_ordinal.LessThan(big_ordinal));
 170 }
 171
 172 // Create three Ordinals in order.  GreaterThan should return values
 173 // consistent with that order.
 174 TEST(Ordinal, GreaterThan) {
 175   const LongOrdinal small_ordinal("10000");
 176   const LongOrdinal middle_ordinal("55555");
 177   const LongOrdinal big_ordinal("99999");
 178
 179   EXPECT_FALSE(small_ordinal.GreaterThan(small_ordinal));
 180   EXPECT_FALSE(small_ordinal.GreaterThan(middle_ordinal));
 181   EXPECT_FALSE(small_ordinal.GreaterThan(big_ordinal));
 182
 183   EXPECT_TRUE(middle_ordinal.GreaterThan(small_ordinal));
 184   EXPECT_FALSE(middle_ordinal.GreaterThan(middle_ordinal));
 185   EXPECT_FALSE(middle_ordinal.GreaterThan(big_ordinal));
 186
 187   EXPECT_TRUE(big_ordinal.GreaterThan(small_ordinal));
 188   EXPECT_TRUE(big_ordinal.GreaterThan(middle_ordinal));
 189   EXPECT_FALSE(big_ordinal.GreaterThan(big_ordinal));
 190 }
 191
 192 // Create two valid Ordinals.  Equals should return true only when
 193 // called reflexively.
 194 TEST(Ordinal, Equals) {
 195   const TestOrdinal ordinal1("1");
 196   const TestOrdinal ordinal2("2");
 197
 198   EXPECT_TRUE(ordinal1.Equals(ordinal1));
 199   EXPECT_FALSE(ordinal1.Equals(ordinal2));
 200
 201   EXPECT_FALSE(ordinal2.Equals(ordinal1));
 202   EXPECT_TRUE(ordinal2.Equals(ordinal2));
 203 }
 204
 205 // Create some valid ordinals from some byte strings.
 206 // ToInternalValue() should return the original byte string.
 207 TEST(OrdinalTest, ToInternalValue) {
 208   EXPECT_EQ("2", TestOrdinal("2").ToInternalValue());
 209   EXPECT_EQ("12345", LongOrdinal("12345").ToInternalValue());
 210   EXPECT_EQ("\1\2\3\4\5", LargeOrdinal("\1\2\3\4\5").ToInternalValue());
 211 }
 212
 213 bool IsNonEmptyPrintableString(const std::string& str) {
 214   if (str.empty())
 215     return false;
 216   for (size_t i = 0; i < str.length(); ++i) {
 217     if (!isprint(str[i]))
 218       return false;
 219   }
 220   return true;
 221 }
 222
 223 // Create some invalid/valid ordinals.  ToDebugString() should always
 224 // return a non-empty printable string.
 225 TEST(OrdinalTest, ToDebugString) {
 226   EXPECT_TRUE(
 227       IsNonEmptyPrintableString(TestOrdinal().ToDebugString()));
 228   EXPECT_TRUE(
 229       IsNonEmptyPrintableString(TestOrdinal("invalid string").ToDebugString()));
 230   EXPECT_TRUE(
 231       IsNonEmptyPrintableString(TestOrdinal("2").ToDebugString()));
 232   EXPECT_TRUE(
 233       IsNonEmptyPrintableString(LongOrdinal("12345").ToDebugString()));
 234   EXPECT_TRUE(
 235       IsNonEmptyPrintableString(LargeOrdinal("\1\2\3\4\5").ToDebugString()));
 236 }
 237
 238 // Create three Ordinals in order.  LessThanFn should return values
 239 // consistent with that order.
 240 TEST(Ordinal, LessThanFn) {
 241   const TestOrdinal small_ordinal("1");
 242   const TestOrdinal middle_ordinal("2");
 243   const TestOrdinal big_ordinal("3");
 244
 245   const TestOrdinal::LessThanFn less_than;
 246
 247   EXPECT_FALSE(less_than(small_ordinal, small_ordinal));
 248   EXPECT_TRUE(less_than(small_ordinal, middle_ordinal));
 249   EXPECT_TRUE(less_than(small_ordinal, big_ordinal));
 250
 251   EXPECT_FALSE(less_than(middle_ordinal, small_ordinal));
 252   EXPECT_FALSE(less_than(middle_ordinal, middle_ordinal));
 253   EXPECT_TRUE(less_than(middle_ordinal, big_ordinal));
 254
 255   EXPECT_FALSE(less_than(big_ordinal, small_ordinal));
 256   EXPECT_FALSE(less_than(big_ordinal, middle_ordinal));
 257   EXPECT_FALSE(less_than(big_ordinal, big_ordinal));
 258 }
 259
 260 template <typename Traits>
 261 std::string GetBetween(const std::string& ordinal_string1,
 262                        const std::string& ordinal_string2) {
 263   const Ordinal<Traits> ordinal1(ordinal_string1);
 264   const Ordinal<Traits> ordinal2(ordinal_string2);
 265   const Ordinal<Traits> between1 = ordinal1.CreateBetween(ordinal2);
 266   const Ordinal<Traits> between2 = ordinal2.CreateBetween(ordinal1);
 267   EXPECT_TRUE(between1.Equals(between2));
 268   return between1.ToInternalValue();
 269 }
 270
 271 // Create some Ordinals from single-digit strings.  Given two strings
 272 // from this set, CreateBetween should return an Ordinal roughly between
 273 // them that are also single-digit when possible.
 274 TEST(Ordinal, CreateBetweenSingleDigit) {
 275   EXPECT_EQ("2", GetBetween<TestOrdinal>("1", "3"));
 276   EXPECT_EQ("12", GetBetween<TestOrdinal>("1", "2"));
 277   EXPECT_EQ("22", GetBetween<TestOrdinal>("2", "3"));
 278 }
 279
 280 // Create some Ordinals from strings of various lengths.  Given two
 281 // strings from this set, CreateBetween should return an Ordinal roughly
 282 // between them that have as few digits as possible.
 283 TEST(Ordinal, CreateBetweenDifferentLengths) {
 284   EXPECT_EQ("102", GetBetween<TestOrdinal>("1", "11"));
 285   EXPECT_EQ("2", GetBetween<TestOrdinal>("1", "31"));
 286   EXPECT_EQ("132", GetBetween<TestOrdinal>("13", "2"));
 287   EXPECT_EQ("2", GetBetween<TestOrdinal>("10001", "3"));
 288   EXPECT_EQ("20000", GetBetween<LongOrdinal>("10001", "30000"));
 289   EXPECT_EQ("2", GetBetween<TestOrdinal>("10002", "3"));
 290   EXPECT_EQ("20001", GetBetween<LongOrdinal>("10002", "30000"));
 291   EXPECT_EQ("2", GetBetween<TestOrdinal>("1", "30002"));
 292   EXPECT_EQ("20001", GetBetween<LongOrdinal>("10000", "30002"));
 293 }
 294
 295 // Create some Ordinals specifically designed to trigger overflow
 296 // cases.  Given two strings from this set, CreateBetween should
 297 // return an Ordinal roughly between them that have as few digits as
 298 // possible.
 299 TEST(Ordinal, CreateBetweenOverflow) {
 300   EXPECT_EQ("03", GetBetween<TestOrdinal>("01", "11"));
 301   EXPECT_EQ("13", GetBetween<TestOrdinal>("11", "21"));
 302   EXPECT_EQ("113", GetBetween<TestOrdinal>("111", "121"));
 303   EXPECT_EQ("2", GetBetween<TestOrdinal>("001", "333"));
 304   EXPECT_EQ("31", GetBetween<TestOrdinal>("222", "333"));
 305   EXPECT_EQ("3", GetBetween<TestOrdinal>("201", "333"));
 306   EXPECT_EQ("2", GetBetween<TestOrdinal>("003", "333"));
 307   EXPECT_EQ("2", GetBetween<TestOrdinal>("2223", "1113"));
 308 }
 309
 310 // Create some Ordinals specifically designed to trigger digit
 311 // overflow cases.  Given two strings from this set, CreateBetween
 312 // should return an Ordinal roughly between them that have as few digits
 313 // as possible.
 314 TEST(Ordinal, CreateBetweenOverflowLarge) {
 315   EXPECT_EQ("\x80", GetBetween<LargeOrdinal>("\x01\xff", "\xff\xff"));
 316   EXPECT_EQ("\xff\xfe\x80", GetBetween<LargeOrdinal>("\xff\xfe", "\xff\xff"));
 317 }
 318
 319 // Create some Ordinals.  CreateBefore should return an Ordinal
 320 // roughly halfway towards 0.
 321 TEST(Ordinal, CreateBefore) {
 322   EXPECT_EQ("02", TestOrdinal("1").CreateBefore().ToInternalValue());
 323   EXPECT_EQ("03", TestOrdinal("11").CreateBefore().ToInternalValue());
 324   EXPECT_EQ("03", TestOrdinal("12").CreateBefore().ToInternalValue());
 325   EXPECT_EQ("1", TestOrdinal("13").CreateBefore().ToInternalValue());
 326 }
 327
 328 // Create some Ordinals.  CreateAfter should return an Ordinal
 329 // roughly halfway towards 0.
 330 TEST(Ordinal, CreateAfter) {
 331   EXPECT_EQ("31", TestOrdinal("3").CreateAfter().ToInternalValue());
 332   EXPECT_EQ("322", TestOrdinal("32").CreateAfter().ToInternalValue());
 333   EXPECT_EQ("33322", TestOrdinal("3332").CreateAfter().ToInternalValue());
 334   EXPECT_EQ("3", TestOrdinal("22").CreateAfter().ToInternalValue());
 335   EXPECT_EQ("3", TestOrdinal("23").CreateAfter().ToInternalValue());
 336 }
 337
 338 // Create two valid Ordinals.  EqualsFn should return true only when
 339 // called reflexively.
 340 TEST(Ordinal, EqualsFn) {
 341   const TestOrdinal ordinal1("1");
 342   const TestOrdinal ordinal2("2");
 343
 344   const TestOrdinal::EqualsFn equals;
 345
 346   EXPECT_TRUE(equals(ordinal1, ordinal1));
 347   EXPECT_FALSE(equals(ordinal1, ordinal2));
 348
 349   EXPECT_FALSE(equals(ordinal2, ordinal1));
 350   EXPECT_TRUE(equals(ordinal2,ordinal2));
 351 }
 352
 353 // Create some Ordinals and shuffle them.  Sorting them using
 354 // LessThanFn should produce the correct order.
 355 TEST(Ordinal, Sort) {
 356   const LongOrdinal ordinal1("12345");
 357   const LongOrdinal ordinal2("54321");
 358   const LongOrdinal ordinal3("87654");
 359   const LongOrdinal ordinal4("98765");
 360
 361   std::vector<LongOrdinal> sorted_ordinals;
 362   sorted_ordinals.push_back(ordinal1);
 363   sorted_ordinals.push_back(ordinal2);
 364   sorted_ordinals.push_back(ordinal3);
 365   sorted_ordinals.push_back(ordinal4);
 366
 367   std::vector<LongOrdinal> ordinals = sorted_ordinals;
 368   std::random_shuffle(ordinals.begin(), ordinals.end());
 369   std::sort(ordinals.begin(), ordinals.end(), LongOrdinal::LessThanFn());
 370   EXPECT_TRUE(std::equal(ordinals.begin(), ordinals.end(),
 371                          sorted_ordinals.begin(), LongOrdinal::EqualsFn()));
 372 }
 373
 374 }  // namespace
 375
 376 }  // namespace syncer