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