| 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/unique_position.h" | |
| 6 | |
| 7 #include <stddef.h> | |
| 8 #include <stdint.h> | |
| 9 | |
| 10 #include <algorithm> | |
| 11 #include <functional> | |
| 12 #include <memory> | |
| 13 #include <string> | |
| 14 #include <vector> | |
| 15 | |
| 16 #include "base/base64.h" | |
| 17 #include "base/logging.h" | |
| 18 #include "base/macros.h" | |
| 19 #include "base/sha1.h" | |
| 20 #include "base/strings/string_number_conversions.h" | |
| 21 #include "sync/protocol/unique_position.pb.h" | |
| 22 #include "testing/gtest/include/gtest/gtest.h" | |
| 23 | |
| 24 namespace syncer { | |
| 25 | |
| 26 namespace { | |
| 27 | |
| 28 class UniquePositionTest : public ::testing::Test { | |
| 29 protected: | |
| 30 // Accessor to fetch the length of the position's internal representation | |
| 31 // We try to avoid having any test expectations on it because this is an | |
| 32 // implementation detail. | |
| 33 // | |
| 34 // If you run the tests with --v=1, we'll print out some of the lengths | |
| 35 // so you can see how well the algorithm performs in various insertion | |
| 36 // scenarios. | |
| 37 size_t GetLength(const UniquePosition& pos) { | |
| 38 sync_pb::UniquePosition proto; | |
| 39 pos.ToProto(&proto); | |
| 40 return proto.ByteSize(); | |
| 41 } | |
| 42 }; | |
| 43 | |
| 44 // This function exploits internal knowledge of how the protobufs are serialized | |
| 45 // to help us build UniquePositions from strings described in this file. | |
| 46 static UniquePosition FromBytes(const std::string& bytes) { | |
| 47 sync_pb::UniquePosition proto; | |
| 48 proto.set_value(bytes); | |
| 49 return UniquePosition::FromProto(proto); | |
| 50 } | |
| 51 | |
| 52 const size_t kMinLength = UniquePosition::kSuffixLength; | |
| 53 const size_t kGenericPredecessorLength = kMinLength + 2; | |
| 54 const size_t kGenericSuccessorLength = kMinLength + 1; | |
| 55 const size_t kBigPositionLength = kMinLength; | |
| 56 const size_t kSmallPositionLength = kMinLength; | |
| 57 | |
| 58 // Be careful when adding more prefixes to this list. | |
| 59 // We have to manually ensure each has a unique suffix. | |
| 60 const UniquePosition kGenericPredecessor = FromBytes( | |
| 61 (std::string(kGenericPredecessorLength, '\x23') + '\xFF')); | |
| 62 const UniquePosition kGenericSuccessor = FromBytes( | |
| 63 std::string(kGenericSuccessorLength, '\xAB') + '\xFF'); | |
| 64 const UniquePosition kBigPosition = FromBytes( | |
| 65 std::string(kBigPositionLength - 1, '\xFF') + '\xFE' + '\xFF'); | |
| 66 const UniquePosition kBigPositionLessTwo = FromBytes( | |
| 67 std::string(kBigPositionLength - 1, '\xFF') + '\xFC' + '\xFF'); | |
| 68 const UniquePosition kBiggerPosition = FromBytes( | |
| 69 std::string(kBigPositionLength, '\xFF') + '\xFF'); | |
| 70 const UniquePosition kSmallPosition = FromBytes( | |
| 71 std::string(kSmallPositionLength - 1, '\x00') + '\x01' + '\xFF'); | |
| 72 const UniquePosition kSmallPositionPlusOne = FromBytes( | |
| 73 std::string(kSmallPositionLength - 1, '\x00') + '\x02' + '\xFF'); | |
| 74 const UniquePosition kHugePosition = FromBytes( | |
| 75 std::string(UniquePosition::kCompressBytesThreshold, '\xFF') + '\xAB'); | |
| 76 | |
| 77 const std::string kMinSuffix = | |
| 78 std::string(UniquePosition::kSuffixLength - 1, '\x00') + '\x01'; | |
| 79 const std::string kMaxSuffix(UniquePosition::kSuffixLength, '\xFF'); | |
| 80 const std::string kNormalSuffix( | |
| 81 "\x68\x44\x6C\x6B\x32\x58\x78\x34\x69\x70\x46\x34\x79\x49" | |
| 82 "\x44\x4F\x66\x4C\x58\x41\x31\x34\x68\x59\x56\x43\x6F\x3D"); | |
| 83 | |
| 84 ::testing::AssertionResult LessThan(const char* m_expr, | |
| 85 const char* n_expr, | |
| 86 const UniquePosition &m, | |
| 87 const UniquePosition &n) { | |
| 88 if (m.LessThan(n)) | |
| 89 return ::testing::AssertionSuccess(); | |
| 90 | |
| 91 return ::testing::AssertionFailure() | |
| 92 << m_expr << " is not less than " << n_expr | |
| 93 << " (" << m.ToDebugString() << " and " << n.ToDebugString() << ")"; | |
| 94 } | |
| 95 | |
| 96 ::testing::AssertionResult Equals(const char* m_expr, | |
| 97 const char* n_expr, | |
| 98 const UniquePosition &m, | |
| 99 const UniquePosition &n) { | |
| 100 if (m.Equals(n)) | |
| 101 return ::testing::AssertionSuccess(); | |
| 102 | |
| 103 return ::testing::AssertionFailure() | |
| 104 << m_expr << " is not equal to " << n_expr | |
| 105 << " (" << m.ToDebugString() << " != " << n.ToDebugString() << ")"; | |
| 106 } | |
| 107 | |
| 108 // Test that the code can read the uncompressed serialization format. | |
| 109 TEST_F(UniquePositionTest, DeserializeObsoleteUncompressedPosition) { | |
| 110 // We no longer support the encoding data in this format. This hard-coded | |
| 111 // input is a serialization of kGenericPredecessor created by an older version | |
| 112 // of this code. | |
| 113 const char kSerializedCstr[] = { | |
| 114 '\x0a', '\x1f', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', | |
| 115 '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', | |
| 116 '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', '\x23', | |
| 117 '\x23', '\x23', '\x23', '\x23', '\x23', '\xff' }; | |
| 118 const std::string serialized(kSerializedCstr, sizeof(kSerializedCstr)); | |
| 119 | |
| 120 sync_pb::UniquePosition proto; | |
| 121 proto.ParseFromString(serialized); | |
| 122 | |
| 123 // Double-check that this test is testing what we think it tests. | |
| 124 EXPECT_TRUE(proto.has_value()); | |
| 125 EXPECT_FALSE(proto.has_compressed_value()); | |
| 126 EXPECT_FALSE(proto.has_uncompressed_length()); | |
| 127 | |
| 128 UniquePosition pos = UniquePosition::FromProto(proto); | |
| 129 EXPECT_PRED_FORMAT2(Equals, kGenericPredecessor, pos); | |
| 130 } | |
| 131 | |
| 132 // Test that the code can read the gzip serialization format. | |
| 133 TEST_F(UniquePositionTest, DeserializeObsoleteGzippedPosition) { | |
| 134 // We no longer support the encoding data in this format. This hard-coded | |
| 135 // input is a serialization of kHugePosition created by an older version of | |
| 136 // this code. | |
| 137 const char kSerializedCstr[] = { | |
| 138 '\x12', '\x0d', '\x78', '\x9c', '\xfb', '\xff', '\x7f', '\x60', '\xc1', | |
| 139 '\x6a', '\x00', '\xa2', '\x4c', '\x80', '\x2c', '\x18', '\x81', '\x01' }; | |
| 140 const std::string serialized(kSerializedCstr, sizeof(kSerializedCstr)); | |
| 141 | |
| 142 sync_pb::UniquePosition proto; | |
| 143 proto.ParseFromString(serialized); | |
| 144 | |
| 145 // Double-check that this test is testing what we think it tests. | |
| 146 EXPECT_FALSE(proto.has_value()); | |
| 147 EXPECT_TRUE(proto.has_compressed_value()); | |
| 148 EXPECT_TRUE(proto.has_uncompressed_length()); | |
| 149 | |
| 150 UniquePosition pos = UniquePosition::FromProto(proto); | |
| 151 EXPECT_PRED_FORMAT2(Equals, kHugePosition, pos); | |
| 152 } | |
| 153 | |
| 154 class RelativePositioningTest : public UniquePositionTest { }; | |
| 155 | |
| 156 const UniquePosition kPositionArray[] = { | |
| 157 kGenericPredecessor, | |
| 158 kGenericSuccessor, | |
| 159 kBigPosition, | |
| 160 kBigPositionLessTwo, | |
| 161 kBiggerPosition, | |
| 162 kSmallPosition, | |
| 163 kSmallPositionPlusOne, | |
| 164 }; | |
| 165 | |
| 166 const UniquePosition kSortedPositionArray[] = { | |
| 167 kSmallPosition, | |
| 168 kSmallPositionPlusOne, | |
| 169 kGenericPredecessor, | |
| 170 kGenericSuccessor, | |
| 171 kBigPositionLessTwo, | |
| 172 kBigPosition, | |
| 173 kBiggerPosition, | |
| 174 }; | |
| 175 | |
| 176 static const size_t kNumPositions = arraysize(kPositionArray); | |
| 177 static const size_t kNumSortedPositions = arraysize(kSortedPositionArray); | |
| 178 | |
| 179 struct PositionLessThan { | |
| 180 bool operator()(const UniquePosition& a, const UniquePosition& b) { | |
| 181 return a.LessThan(b); | |
| 182 } | |
| 183 }; | |
| 184 | |
| 185 // Returns true iff the given position's suffix matches the input parameter. | |
| 186 static bool IsSuffixInUse( | |
| 187 const UniquePosition& pos, const std::string& suffix) { | |
| 188 return pos.GetSuffixForTest() == suffix; | |
| 189 } | |
| 190 | |
| 191 // Test some basic properties of comparison and equality. | |
| 192 TEST_F(RelativePositioningTest, ComparisonSanityTest1) { | |
| 193 const UniquePosition& a = kPositionArray[0]; | |
| 194 ASSERT_TRUE(a.IsValid()); | |
| 195 | |
| 196 // Necessarily true for any non-invalid positions. | |
| 197 EXPECT_TRUE(a.Equals(a)); | |
| 198 EXPECT_FALSE(a.LessThan(a)); | |
| 199 } | |
| 200 | |
| 201 // Test some more properties of comparison and equality. | |
| 202 TEST_F(RelativePositioningTest, ComparisonSanityTest2) { | |
| 203 const UniquePosition& a = kPositionArray[0]; | |
| 204 const UniquePosition& b = kPositionArray[1]; | |
| 205 | |
| 206 // These should pass for the specific a and b we have chosen (a < b). | |
| 207 EXPECT_FALSE(a.Equals(b)); | |
| 208 EXPECT_TRUE(a.LessThan(b)); | |
| 209 EXPECT_FALSE(b.LessThan(a)); | |
| 210 } | |
| 211 | |
| 212 // Exercise comparision functions by sorting and re-sorting the list. | |
| 213 TEST_F(RelativePositioningTest, SortPositions) { | |
| 214 ASSERT_EQ(kNumPositions, kNumSortedPositions); | |
| 215 UniquePosition positions[arraysize(kPositionArray)]; | |
| 216 for (size_t i = 0; i < kNumPositions; ++i) { | |
| 217 positions[i] = kPositionArray[i]; | |
| 218 } | |
| 219 | |
| 220 std::sort(&positions[0], &positions[kNumPositions], PositionLessThan()); | |
| 221 for (size_t i = 0; i < kNumPositions; ++i) { | |
| 222 EXPECT_TRUE(positions[i].Equals(kSortedPositionArray[i])) | |
| 223 << "i: " << i << ", " | |
| 224 << positions[i].ToDebugString() << " != " | |
| 225 << kSortedPositionArray[i].ToDebugString(); | |
| 226 } | |
| 227 } | |
| 228 | |
| 229 // Some more exercise for the comparison function. | |
| 230 TEST_F(RelativePositioningTest, ReverseSortPositions) { | |
| 231 ASSERT_EQ(kNumPositions, kNumSortedPositions); | |
| 232 UniquePosition positions[arraysize(kPositionArray)]; | |
| 233 for (size_t i = 0; i < kNumPositions; ++i) { | |
| 234 positions[i] = kPositionArray[i]; | |
| 235 } | |
| 236 | |
| 237 std::reverse(&positions[0], &positions[kNumPositions]); | |
| 238 std::sort(&positions[0], &positions[kNumPositions], PositionLessThan()); | |
| 239 for (size_t i = 0; i < kNumPositions; ++i) { | |
| 240 EXPECT_TRUE(positions[i].Equals(kSortedPositionArray[i])) | |
| 241 << "i: " << i << ", " | |
| 242 << positions[i].ToDebugString() << " != " | |
| 243 << kSortedPositionArray[i].ToDebugString(); | |
| 244 } | |
| 245 } | |
| 246 | |
| 247 class PositionInsertTest : | |
| 248 public RelativePositioningTest, | |
| 249 public ::testing::WithParamInterface<std::string> { }; | |
| 250 | |
| 251 // Exercise InsertBetween with various insertion operations. | |
| 252 TEST_P(PositionInsertTest, InsertBetween) { | |
| 253 const std::string suffix = GetParam(); | |
| 254 ASSERT_TRUE(UniquePosition::IsValidSuffix(suffix)); | |
| 255 | |
| 256 for (size_t i = 0; i < kNumSortedPositions; ++i) { | |
| 257 const UniquePosition& predecessor = kSortedPositionArray[i]; | |
| 258 // Verify our suffixes are unique before we continue. | |
| 259 if (IsSuffixInUse(predecessor, suffix)) | |
| 260 continue; | |
| 261 | |
| 262 for (size_t j = i + 1; j < kNumSortedPositions; ++j) { | |
| 263 const UniquePosition& successor = kSortedPositionArray[j]; | |
| 264 | |
| 265 // Another guard against non-unique suffixes. | |
| 266 if (IsSuffixInUse(successor, suffix)) | |
| 267 continue; | |
| 268 | |
| 269 UniquePosition midpoint = | |
| 270 UniquePosition::Between(predecessor, successor, suffix); | |
| 271 | |
| 272 EXPECT_PRED_FORMAT2(LessThan, predecessor, midpoint); | |
| 273 EXPECT_PRED_FORMAT2(LessThan, midpoint, successor); | |
| 274 } | |
| 275 } | |
| 276 } | |
| 277 | |
| 278 TEST_P(PositionInsertTest, InsertBefore) { | |
| 279 const std::string suffix = GetParam(); | |
| 280 for (size_t i = 0; i < kNumSortedPositions; ++i) { | |
| 281 const UniquePosition& successor = kSortedPositionArray[i]; | |
| 282 // Verify our suffixes are unique before we continue. | |
| 283 if (IsSuffixInUse(successor, suffix)) | |
| 284 continue; | |
| 285 | |
| 286 UniquePosition before = UniquePosition::Before(successor, suffix); | |
| 287 | |
| 288 EXPECT_PRED_FORMAT2(LessThan, before, successor); | |
| 289 } | |
| 290 } | |
| 291 | |
| 292 TEST_P(PositionInsertTest, InsertAfter) { | |
| 293 const std::string suffix = GetParam(); | |
| 294 for (size_t i = 0; i < kNumSortedPositions; ++i) { | |
| 295 const UniquePosition& predecessor = kSortedPositionArray[i]; | |
| 296 // Verify our suffixes are unique before we continue. | |
| 297 if (IsSuffixInUse(predecessor, suffix)) | |
| 298 continue; | |
| 299 | |
| 300 UniquePosition after = UniquePosition::After(predecessor, suffix); | |
| 301 | |
| 302 EXPECT_PRED_FORMAT2(LessThan, predecessor, after); | |
| 303 } | |
| 304 } | |
| 305 | |
| 306 TEST_P(PositionInsertTest, StressInsertAfter) { | |
| 307 // Use two different suffixes to not violate our suffix uniqueness guarantee. | |
| 308 const std::string& suffix_a = GetParam(); | |
| 309 std::string suffix_b = suffix_a; | |
| 310 suffix_b[10] = suffix_b[10] ^ 0xff; | |
| 311 | |
| 312 UniquePosition pos = UniquePosition::InitialPosition(suffix_a); | |
| 313 for (int i = 0; i < 1024; i++) { | |
| 314 const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a; | |
| 315 UniquePosition next_pos = UniquePosition::After(pos, suffix); | |
| 316 ASSERT_PRED_FORMAT2(LessThan, pos, next_pos); | |
| 317 pos = next_pos; | |
| 318 } | |
| 319 | |
| 320 VLOG(1) << "Length: " << GetLength(pos); | |
| 321 } | |
| 322 | |
| 323 TEST_P(PositionInsertTest, StressInsertBefore) { | |
| 324 // Use two different suffixes to not violate our suffix uniqueness guarantee. | |
| 325 const std::string& suffix_a = GetParam(); | |
| 326 std::string suffix_b = suffix_a; | |
| 327 suffix_b[10] = suffix_b[10] ^ 0xff; | |
| 328 | |
| 329 UniquePosition pos = UniquePosition::InitialPosition(suffix_a); | |
| 330 for (int i = 0; i < 1024; i++) { | |
| 331 const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a; | |
| 332 UniquePosition prev_pos = UniquePosition::Before(pos, suffix); | |
| 333 ASSERT_PRED_FORMAT2(LessThan, prev_pos, pos); | |
| 334 pos = prev_pos; | |
| 335 } | |
| 336 | |
| 337 VLOG(1) << "Length: " << GetLength(pos); | |
| 338 } | |
| 339 | |
| 340 TEST_P(PositionInsertTest, StressLeftInsertBetween) { | |
| 341 // Use different suffixes to not violate our suffix uniqueness guarantee. | |
| 342 const std::string& suffix_a = GetParam(); | |
| 343 std::string suffix_b = suffix_a; | |
| 344 suffix_b[10] = suffix_b[10] ^ 0xff; | |
| 345 std::string suffix_c = suffix_a; | |
| 346 suffix_c[10] = suffix_c[10] ^ 0xf0; | |
| 347 | |
| 348 UniquePosition right_pos = UniquePosition::InitialPosition(suffix_c); | |
| 349 UniquePosition left_pos = UniquePosition::Before(right_pos, suffix_a); | |
| 350 for (int i = 0; i < 1024; i++) { | |
| 351 const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a; | |
| 352 UniquePosition new_pos = | |
| 353 UniquePosition::Between(left_pos, right_pos, suffix); | |
| 354 ASSERT_PRED_FORMAT2(LessThan, left_pos, new_pos); | |
| 355 ASSERT_PRED_FORMAT2(LessThan, new_pos, right_pos); | |
| 356 left_pos = new_pos; | |
| 357 } | |
| 358 | |
| 359 VLOG(1) << "Lengths: " << GetLength(left_pos) << ", " << GetLength(right_pos); | |
| 360 } | |
| 361 | |
| 362 TEST_P(PositionInsertTest, StressRightInsertBetween) { | |
| 363 // Use different suffixes to not violate our suffix uniqueness guarantee. | |
| 364 const std::string& suffix_a = GetParam(); | |
| 365 std::string suffix_b = suffix_a; | |
| 366 suffix_b[10] = suffix_b[10] ^ 0xff; | |
| 367 std::string suffix_c = suffix_a; | |
| 368 suffix_c[10] = suffix_c[10] ^ 0xf0; | |
| 369 | |
| 370 UniquePosition right_pos = UniquePosition::InitialPosition(suffix_a); | |
| 371 UniquePosition left_pos = UniquePosition::Before(right_pos, suffix_c); | |
| 372 for (int i = 0; i < 1024; i++) { | |
| 373 const std::string& suffix = (i % 2 == 0) ? suffix_b : suffix_a; | |
| 374 UniquePosition new_pos = | |
| 375 UniquePosition::Between(left_pos, right_pos, suffix); | |
| 376 ASSERT_PRED_FORMAT2(LessThan, left_pos, new_pos); | |
| 377 ASSERT_PRED_FORMAT2(LessThan, new_pos, right_pos); | |
| 378 right_pos = new_pos; | |
| 379 } | |
| 380 | |
| 381 VLOG(1) << "Lengths: " << GetLength(left_pos) << ", " << GetLength(right_pos); | |
| 382 } | |
| 383 | |
| 384 // Generates suffixes similar to those generated by the directory. | |
| 385 // This may become obsolete if the suffix generation code is modified. | |
| 386 class SuffixGenerator { | |
| 387 public: | |
| 388 explicit SuffixGenerator(const std::string& cache_guid) | |
| 389 : cache_guid_(cache_guid), | |
| 390 next_id_(-65535) { | |
| 391 } | |
| 392 | |
| 393 std::string NextSuffix() { | |
| 394 // This is not entirely realistic, but that should be OK. The current | |
| 395 // suffix format is a base64'ed SHA1 hash, which should be fairly close to | |
| 396 // random anyway. | |
| 397 std::string input = cache_guid_ + base::Int64ToString(next_id_--); | |
| 398 std::string output; | |
| 399 base::Base64Encode(base::SHA1HashString(input), &output); | |
| 400 return output; | |
| 401 } | |
| 402 | |
| 403 private: | |
| 404 const std::string cache_guid_; | |
| 405 int64_t next_id_; | |
| 406 }; | |
| 407 | |
| 408 // Cache guids generated in the same style as real clients. | |
| 409 static const char kCacheGuidStr1[] = "tuiWdG8hV+8y4RT9N5Aikg=="; | |
| 410 static const char kCacheGuidStr2[] = "yaKb7zHtY06aue9a0vlZgw=="; | |
| 411 | |
| 412 class PositionScenariosTest : public UniquePositionTest { | |
| 413 public: | |
| 414 PositionScenariosTest() | |
| 415 : generator1_(std::string(kCacheGuidStr1, arraysize(kCacheGuidStr1)-1)), | |
| 416 generator2_(std::string(kCacheGuidStr2, arraysize(kCacheGuidStr2)-1)) { | |
| 417 } | |
| 418 | |
| 419 std::string NextClient1Suffix() { | |
| 420 return generator1_.NextSuffix(); | |
| 421 } | |
| 422 | |
| 423 std::string NextClient2Suffix() { | |
| 424 return generator2_.NextSuffix(); | |
| 425 } | |
| 426 | |
| 427 private: | |
| 428 SuffixGenerator generator1_; | |
| 429 SuffixGenerator generator2_; | |
| 430 }; | |
| 431 | |
| 432 // One client creating new bookmarks, always inserting at the end. | |
| 433 TEST_F(PositionScenariosTest, OneClientInsertAtEnd) { | |
| 434 UniquePosition pos = | |
| 435 UniquePosition::InitialPosition(NextClient1Suffix()); | |
| 436 for (int i = 0; i < 1024; i++) { | |
| 437 const std::string suffix = NextClient1Suffix(); | |
| 438 UniquePosition new_pos = UniquePosition::After(pos, suffix); | |
| 439 ASSERT_PRED_FORMAT2(LessThan, pos, new_pos); | |
| 440 pos = new_pos; | |
| 441 } | |
| 442 | |
| 443 VLOG(1) << "Length: " << GetLength(pos); | |
| 444 | |
| 445 // Normally we wouldn't want to make an assertion about the internal | |
| 446 // representation of our data, but we make an exception for this case. | |
| 447 // If this scenario causes lengths to explode, we have a big problem. | |
| 448 EXPECT_LT(GetLength(pos), 500U); | |
| 449 } | |
| 450 | |
| 451 // Two clients alternately inserting entries at the end, with a strong | |
| 452 // bias towards insertions by the first client. | |
| 453 TEST_F(PositionScenariosTest, TwoClientsInsertAtEnd_A) { | |
| 454 UniquePosition pos = | |
| 455 UniquePosition::InitialPosition(NextClient1Suffix()); | |
| 456 for (int i = 0; i < 1024; i++) { | |
| 457 std::string suffix; | |
| 458 if (i % 5 == 0) { | |
| 459 suffix = NextClient2Suffix(); | |
| 460 } else { | |
| 461 suffix = NextClient1Suffix(); | |
| 462 } | |
| 463 | |
| 464 UniquePosition new_pos = UniquePosition::After(pos, suffix); | |
| 465 ASSERT_PRED_FORMAT2(LessThan, pos, new_pos); | |
| 466 pos = new_pos; | |
| 467 } | |
| 468 | |
| 469 VLOG(1) << "Length: " << GetLength(pos); | |
| 470 EXPECT_LT(GetLength(pos), 500U); | |
| 471 } | |
| 472 | |
| 473 // Two clients alternately inserting entries at the end. | |
| 474 TEST_F(PositionScenariosTest, TwoClientsInsertAtEnd_B) { | |
| 475 UniquePosition pos = | |
| 476 UniquePosition::InitialPosition(NextClient1Suffix()); | |
| 477 for (int i = 0; i < 1024; i++) { | |
| 478 std::string suffix; | |
| 479 if (i % 2 == 0) { | |
| 480 suffix = NextClient1Suffix(); | |
| 481 } else { | |
| 482 suffix = NextClient2Suffix(); | |
| 483 } | |
| 484 | |
| 485 UniquePosition new_pos = UniquePosition::After(pos, suffix); | |
| 486 ASSERT_PRED_FORMAT2(LessThan, pos, new_pos); | |
| 487 pos = new_pos; | |
| 488 } | |
| 489 | |
| 490 VLOG(1) << "Length: " << GetLength(pos); | |
| 491 EXPECT_LT(GetLength(pos), 500U); | |
| 492 } | |
| 493 | |
| 494 INSTANTIATE_TEST_CASE_P(MinSuffix, PositionInsertTest, | |
| 495 ::testing::Values(kMinSuffix)); | |
| 496 INSTANTIATE_TEST_CASE_P(MaxSuffix, PositionInsertTest, | |
| 497 ::testing::Values(kMaxSuffix)); | |
| 498 INSTANTIATE_TEST_CASE_P(NormalSuffix, PositionInsertTest, | |
| 499 ::testing::Values(kNormalSuffix)); | |
| 500 | |
| 501 class PositionFromIntTest : public UniquePositionTest { | |
| 502 public: | |
| 503 PositionFromIntTest() | |
| 504 : generator_(std::string(kCacheGuidStr1, arraysize(kCacheGuidStr1)-1)) { | |
| 505 } | |
| 506 | |
| 507 protected: | |
| 508 static const int64_t kTestValues[]; | |
| 509 static const size_t kNumTestValues; | |
| 510 | |
| 511 std::string NextSuffix() { | |
| 512 return generator_.NextSuffix(); | |
| 513 } | |
| 514 | |
| 515 private: | |
| 516 SuffixGenerator generator_; | |
| 517 }; | |
| 518 | |
| 519 const int64_t PositionFromIntTest::kTestValues[] = {0LL, | |
| 520 1LL, | |
| 521 -1LL, | |
| 522 2LL, | |
| 523 -2LL, | |
| 524 3LL, | |
| 525 -3LL, | |
| 526 0x79LL, | |
| 527 -0x79LL, | |
| 528 0x80LL, | |
| 529 -0x80LL, | |
| 530 0x81LL, | |
| 531 -0x81LL, | |
| 532 0xFELL, | |
| 533 -0xFELL, | |
| 534 0xFFLL, | |
| 535 -0xFFLL, | |
| 536 0x100LL, | |
| 537 -0x100LL, | |
| 538 0x101LL, | |
| 539 -0x101LL, | |
| 540 0xFA1AFELL, | |
| 541 -0xFA1AFELL, | |
| 542 0xFFFFFFFELL, | |
| 543 -0xFFFFFFFELL, | |
| 544 0xFFFFFFFFLL, | |
| 545 -0xFFFFFFFFLL, | |
| 546 0x100000000LL, | |
| 547 -0x100000000LL, | |
| 548 0x100000001LL, | |
| 549 -0x100000001LL, | |
| 550 0xFFFFFFFFFFLL, | |
| 551 -0xFFFFFFFFFFLL, | |
| 552 0x112358132134LL, | |
| 553 -0x112358132134LL, | |
| 554 0xFEFFBEEFABC1234LL, | |
| 555 -0xFEFFBEEFABC1234LL, | |
| 556 INT64_MAX, | |
| 557 INT64_MIN, | |
| 558 INT64_MIN + 1, | |
| 559 INT64_MAX - 1}; | |
| 560 | |
| 561 const size_t PositionFromIntTest::kNumTestValues = | |
| 562 arraysize(PositionFromIntTest::kTestValues); | |
| 563 | |
| 564 TEST_F(PositionFromIntTest, IsValid) { | |
| 565 for (size_t i = 0; i < kNumTestValues; ++i) { | |
| 566 const UniquePosition pos = | |
| 567 UniquePosition::FromInt64(kTestValues[i], NextSuffix()); | |
| 568 EXPECT_TRUE(pos.IsValid()) << "i = " << i << "; " << pos.ToDebugString(); | |
| 569 } | |
| 570 } | |
| 571 | |
| 572 TEST_F(PositionFromIntTest, RoundTripConversion) { | |
| 573 for (size_t i = 0; i < kNumTestValues; ++i) { | |
| 574 const int64_t expected_value = kTestValues[i]; | |
| 575 const UniquePosition pos = | |
| 576 UniquePosition::FromInt64(kTestValues[i], NextSuffix()); | |
| 577 const int64_t value = pos.ToInt64(); | |
| 578 EXPECT_EQ(expected_value, value) << "i = " << i; | |
| 579 } | |
| 580 } | |
| 581 | |
| 582 template <typename T, typename LessThan = std::less<T> > | |
| 583 class IndexedLessThan { | |
| 584 public: | |
| 585 explicit IndexedLessThan(const T* values) : values_(values) {} | |
| 586 | |
| 587 bool operator()(int i1, int i2) { | |
| 588 return less_than_(values_[i1], values_[i2]); | |
| 589 } | |
| 590 | |
| 591 private: | |
| 592 const T* values_; | |
| 593 LessThan less_than_; | |
| 594 }; | |
| 595 | |
| 596 TEST_F(PositionFromIntTest, ConsistentOrdering) { | |
| 597 UniquePosition positions[kNumTestValues]; | |
| 598 std::vector<int> original_ordering(kNumTestValues); | |
| 599 std::vector<int> int64_ordering(kNumTestValues); | |
| 600 std::vector<int> position_ordering(kNumTestValues); | |
| 601 for (size_t i = 0; i < kNumTestValues; ++i) { | |
| 602 positions[i] = UniquePosition::FromInt64( | |
| 603 kTestValues[i], NextSuffix()); | |
| 604 original_ordering[i] = int64_ordering[i] = position_ordering[i] = i; | |
| 605 } | |
| 606 | |
| 607 std::sort(int64_ordering.begin(), int64_ordering.end(), | |
| 608 IndexedLessThan<int64_t>(kTestValues)); | |
| 609 std::sort(position_ordering.begin(), position_ordering.end(), | |
| 610 IndexedLessThan<UniquePosition, PositionLessThan>(positions)); | |
| 611 EXPECT_NE(original_ordering, int64_ordering); | |
| 612 EXPECT_EQ(int64_ordering, position_ordering); | |
| 613 } | |
| 614 | |
| 615 class CompressedPositionTest : public UniquePositionTest { | |
| 616 public: | |
| 617 CompressedPositionTest() { | |
| 618 positions_.push_back(MakePosition( // Prefix starts with 256 0x00s | |
| 619 std::string("\x00\x00\x00\x00\xFF\xFF\xFE\xFF" | |
| 620 "\x01", | |
| 621 9), | |
| 622 MakeSuffix('\x04'))); | |
| 623 positions_.push_back(MakePosition( // Prefix starts with four 0x00s | |
| 624 std::string("\x00\x00\x00\x00\xFF\xFF\xFF\xFB" | |
| 625 "\x01", | |
| 626 9), | |
| 627 MakeSuffix('\x03'))); | |
| 628 positions_.push_back(MakePosition( // Prefix starts with four 0xFFs | |
| 629 std::string("\xFF\xFF\xFF\xFF\x00\x00\x00\x04" | |
| 630 "\x01", | |
| 631 9), | |
| 632 MakeSuffix('\x01'))); | |
| 633 positions_.push_back(MakePosition( // Prefix starts with 256 0xFFs | |
| 634 std::string("\xFF\xFF\xFF\xFF\x00\x00\x01\x00" | |
| 635 "\x01", | |
| 636 9), | |
| 637 MakeSuffix('\x02'))); | |
| 638 } | |
| 639 | |
| 640 private: | |
| 641 UniquePosition MakePosition(const std::string& compressed_prefix, | |
| 642 const std::string& compressed_suffix); | |
| 643 std::string MakeSuffix(char unique_value); | |
| 644 | |
| 645 protected: | |
| 646 std::vector<UniquePosition> positions_; | |
| 647 }; | |
| 648 | |
| 649 UniquePosition CompressedPositionTest::MakePosition( | |
| 650 const std::string& compressed_prefix, | |
| 651 const std::string& compressed_suffix) { | |
| 652 sync_pb::UniquePosition proto; | |
| 653 proto.set_custom_compressed_v1( | |
| 654 std::string(compressed_prefix + compressed_suffix)); | |
| 655 return UniquePosition::FromProto(proto); | |
| 656 } | |
| 657 | |
| 658 std::string CompressedPositionTest::MakeSuffix(char unique_value) { | |
| 659 // We're dealing in compressed positions in this test. That means the | |
| 660 // suffix should be compressed, too. To avoid complication, we use suffixes | |
| 661 // that don't have any repeating digits, and therefore are identical in | |
| 662 // compressed and uncompressed form. | |
| 663 std::string suffix; | |
| 664 for (size_t i = 0; i < UniquePosition::kSuffixLength; ++i) { | |
| 665 suffix.push_back(static_cast<char>(i)); | |
| 666 } | |
| 667 suffix[UniquePosition::kSuffixLength-1] = unique_value; | |
| 668 return suffix; | |
| 669 } | |
| 670 | |
| 671 // Make sure that serialization and deserialization routines are correct. | |
| 672 TEST_F(CompressedPositionTest, SerializeAndDeserialize) { | |
| 673 for (std::vector<UniquePosition>::const_iterator it = positions_.begin(); | |
| 674 it != positions_.end(); ++it) { | |
| 675 SCOPED_TRACE("iteration: " + it->ToDebugString()); | |
| 676 | |
| 677 sync_pb::UniquePosition proto; | |
| 678 it->ToProto(&proto); | |
| 679 UniquePosition deserialized = UniquePosition::FromProto(proto); | |
| 680 | |
| 681 EXPECT_PRED_FORMAT2(Equals, *it, deserialized); | |
| 682 } | |
| 683 } | |
| 684 | |
| 685 // Test that deserialization failures of protobufs where we know none of its | |
| 686 // fields is not catastrophic. This may happen if all the fields currently | |
| 687 // known to this client become deprecated in the future. | |
| 688 TEST_F(CompressedPositionTest, DeserializeProtobufFromTheFuture) { | |
| 689 sync_pb::UniquePosition proto; | |
| 690 UniquePosition deserialized = UniquePosition::FromProto(proto); | |
| 691 EXPECT_FALSE(deserialized.IsValid()); | |
| 692 } | |
| 693 | |
| 694 // Make sure the comparison functions are working correctly. | |
| 695 // This requires values in the test harness to be hard-coded in ascending order. | |
| 696 TEST_F(CompressedPositionTest, OrderingTest) { | |
| 697 for (size_t i = 0; i < positions_.size()-1; ++i) { | |
| 698 EXPECT_PRED_FORMAT2(LessThan, positions_[i], positions_[i+1]); | |
| 699 } | |
| 700 } | |
| 701 | |
| 702 } // namespace | |
| 703 | |
| 704 } // 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