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.
5 #include "base/basictypes.h"
6 #include "sync/internal_api/public/base/ordinal.h"
7 #include "testing/gtest/include/gtest/gtest.h"
19 struct TestOrdinalTraits
{
20 static const uint8 kZeroDigit
= '0';
21 static const uint8 kMaxDigit
= '3';
22 static const size_t kMinLength
= 1;
25 struct LongOrdinalTraits
{
26 static const uint8 kZeroDigit
= '0';
27 static const uint8 kMaxDigit
= '9';
28 static const size_t kMinLength
= 5;
31 struct LargeOrdinalTraits
{
32 static const uint8 kZeroDigit
= 0;
33 static const uint8 kMaxDigit
= kuint8max
;
34 static const size_t kMinLength
= 1;
37 typedef Ordinal
<TestOrdinalTraits
> TestOrdinal
;
38 typedef Ordinal
<LongOrdinalTraits
> LongOrdinal
;
39 typedef Ordinal
<LargeOrdinalTraits
> LargeOrdinal
;
41 static_assert(TestOrdinal::kZeroDigit
== '0',
42 "incorrect TestOrdinal zero digit");
43 static_assert(TestOrdinal::kOneDigit
== '1',
44 "incorrect TestOrdinal one digit");
45 static_assert(TestOrdinal::kMidDigit
== '2',
46 "incorrect TestOrdinal min digit");
47 static_assert(TestOrdinal::kMaxDigit
== '3',
48 "incorrect TestOrdinal max digit");
49 static_assert(TestOrdinal::kMidDigitValue
== 2,
50 "incorrect TestOrdinal mid digit value");
51 static_assert(TestOrdinal::kMaxDigitValue
== 3,
52 "incorrect TestOrdinal max digit value");
53 static_assert(TestOrdinal::kRadix
== 4,
54 "incorrect TestOrdinal radix");
56 static_assert(LongOrdinal::kZeroDigit
== '0',
57 "incorrect LongOrdinal zero digit");
58 static_assert(LongOrdinal::kOneDigit
== '1',
59 "incorrect LongOrdinal one digit");
60 static_assert(LongOrdinal::kMidDigit
== '5',
61 "incorrect LongOrdinal mid digit");
62 static_assert(LongOrdinal::kMaxDigit
== '9',
63 "incorrect LongOrdinal max digit");
64 static_assert(LongOrdinal::kMidDigitValue
== 5,
65 "incorrect LongOrdinal mid digit value");
66 static_assert(LongOrdinal::kMaxDigitValue
== 9,
67 "incorrect LongOrdinal max digit value");
68 static_assert(LongOrdinal::kRadix
== 10,
69 "incorrect LongOrdinal radix");
71 static_assert(static_cast<char>(LargeOrdinal::kZeroDigit
) == '\x00',
72 "incorrect LargeOrdinal zero digit");
73 static_assert(static_cast<char>(LargeOrdinal::kOneDigit
) == '\x01',
74 "incorrect LargeOrdinal one digit");
75 static_assert(static_cast<char>(LargeOrdinal::kMidDigit
) == '\x80',
76 "incorrect LargeOrdinal mid digit");
77 static_assert(static_cast<char>(LargeOrdinal::kMaxDigit
) == '\xff',
78 "incorrect LargeOrdinal max digit");
79 static_assert(LargeOrdinal::kMidDigitValue
== 128,
80 "incorrect LargeOrdinal mid digit value");
81 static_assert(LargeOrdinal::kMaxDigitValue
== 255,
82 "incorrect LargeOrdinal max digit value");
83 static_assert(LargeOrdinal::kRadix
== 256,
84 "incorrect LargeOrdinal radix");
86 // Create Ordinals that satisfy all but one criterion for validity.
87 // IsValid() should return false for all of them.
88 TEST(Ordinal
, Invalid
) {
90 EXPECT_FALSE(TestOrdinal(std::string()).IsValid());
91 EXPECT_FALSE(LongOrdinal("0001").IsValid());
93 const char kBeforeZero
[] = { '0' - 1, '\0' };
94 const char kAfterNine
[] = { '9' + 1, '\0' };
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());
103 EXPECT_FALSE(TestOrdinal("0").IsValid());
104 EXPECT_FALSE(TestOrdinal("00000").IsValid());
106 // Trailing zero criterion.
107 EXPECT_FALSE(TestOrdinal("10").IsValid());
108 EXPECT_FALSE(TestOrdinal("111110").IsValid());
111 // Create Ordinals that satisfy all criteria for validity.
112 // IsValid() should return true for all of them.
113 TEST(Ordinal
, Valid
) {
115 EXPECT_TRUE(TestOrdinal("1").IsValid());
116 EXPECT_TRUE(LongOrdinal("10000").IsValid());
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")));
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
;
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
));
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");
149 EXPECT_FALSE(small_ordinal
.LessThan(small_ordinal
));
150 EXPECT_TRUE(small_ordinal
.LessThan(middle_ordinal
));
151 EXPECT_TRUE(small_ordinal
.LessThan(big_ordinal
));
153 EXPECT_FALSE(middle_ordinal
.LessThan(small_ordinal
));
154 EXPECT_FALSE(middle_ordinal
.LessThan(middle_ordinal
));
155 EXPECT_TRUE(middle_ordinal
.LessThan(big_ordinal
));
157 EXPECT_FALSE(big_ordinal
.LessThan(small_ordinal
));
158 EXPECT_FALSE(big_ordinal
.LessThan(middle_ordinal
));
159 EXPECT_FALSE(big_ordinal
.LessThan(big_ordinal
));
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");
169 EXPECT_TRUE(small_ordinal
.LessThan(big_ordinal
));
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");
179 EXPECT_FALSE(small_ordinal
.GreaterThan(small_ordinal
));
180 EXPECT_FALSE(small_ordinal
.GreaterThan(middle_ordinal
));
181 EXPECT_FALSE(small_ordinal
.GreaterThan(big_ordinal
));
183 EXPECT_TRUE(middle_ordinal
.GreaterThan(small_ordinal
));
184 EXPECT_FALSE(middle_ordinal
.GreaterThan(middle_ordinal
));
185 EXPECT_FALSE(middle_ordinal
.GreaterThan(big_ordinal
));
187 EXPECT_TRUE(big_ordinal
.GreaterThan(small_ordinal
));
188 EXPECT_TRUE(big_ordinal
.GreaterThan(middle_ordinal
));
189 EXPECT_FALSE(big_ordinal
.GreaterThan(big_ordinal
));
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");
198 EXPECT_TRUE(ordinal1
.Equals(ordinal1
));
199 EXPECT_FALSE(ordinal1
.Equals(ordinal2
));
201 EXPECT_FALSE(ordinal2
.Equals(ordinal1
));
202 EXPECT_TRUE(ordinal2
.Equals(ordinal2
));
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());
213 bool IsNonEmptyPrintableString(const std::string
& str
) {
216 for (size_t i
= 0; i
< str
.length(); ++i
) {
217 if (!isprint(str
[i
]))
223 // Create some invalid/valid ordinals. ToDebugString() should always
224 // return a non-empty printable string.
225 TEST(OrdinalTest
, ToDebugString
) {
227 IsNonEmptyPrintableString(TestOrdinal().ToDebugString()));
229 IsNonEmptyPrintableString(TestOrdinal("invalid string").ToDebugString()));
231 IsNonEmptyPrintableString(TestOrdinal("2").ToDebugString()));
233 IsNonEmptyPrintableString(LongOrdinal("12345").ToDebugString()));
235 IsNonEmptyPrintableString(LargeOrdinal("\1\2\3\4\5").ToDebugString()));
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");
245 const TestOrdinal::LessThanFn less_than
;
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
));
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
));
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
));
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();
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"));
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"));
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
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"));
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
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"));
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());
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());
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");
344 const TestOrdinal::EqualsFn equals
;
346 EXPECT_TRUE(equals(ordinal1
, ordinal1
));
347 EXPECT_FALSE(equals(ordinal1
, ordinal2
));
349 EXPECT_FALSE(equals(ordinal2
, ordinal1
));
350 EXPECT_TRUE(equals(ordinal2
,ordinal2
));
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");
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
);
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()));
376 } // namespace syncer