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