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 377
