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
15namespace syncer {
16
17namespace {
18
19struct TestOrdinalTraits {
20  static const uint8 kZeroDigit = '0';
21  static const uint8 kMaxDigit = '3';
22  static const size_t kMinLength = 1;
23};
24
25struct LongOrdinalTraits {
26  static const uint8 kZeroDigit = '0';
27  static const uint8 kMaxDigit = '9';
28  static const size_t kMinLength = 5;
29};
30
31struct LargeOrdinalTraits {
32  static const uint8 kZeroDigit = 0;
33  static const uint8 kMaxDigit = kuint8max;
34  static const size_t kMinLength = 1;
35};
36
37typedef Ordinal<TestOrdinalTraits> TestOrdinal;
38typedef Ordinal<LongOrdinalTraits> LongOrdinal;
39typedef Ordinal<LargeOrdinalTraits> LargeOrdinal;
40
41COMPILE_ASSERT(TestOrdinal::kZeroDigit == '0',
42               TestOrdinalHasCorrectZeroDigit);
43COMPILE_ASSERT(TestOrdinal::kOneDigit == '1',
44               TestOrdinalHasCorrectOneDigit);
45COMPILE_ASSERT(TestOrdinal::kMidDigit == '2',
46               TestOrdinalHasCorrectMidDigit);
47COMPILE_ASSERT(TestOrdinal::kMaxDigit == '3',
48               TestOrdinalHasCorrectMaxDigit);
49COMPILE_ASSERT(TestOrdinal::kMidDigitValue == 2,
50               TestOrdinalHasCorrectMidDigitValue);
51COMPILE_ASSERT(TestOrdinal::kMaxDigitValue == 3,
52               TestOrdinalHasCorrectMaxDigitValue);
53COMPILE_ASSERT(TestOrdinal::kRadix == 4,
54               TestOrdinalHasCorrectRadix);
55
56COMPILE_ASSERT(LongOrdinal::kZeroDigit == '0',
57               LongOrdinalkZeroDigit_incorrect);
58COMPILE_ASSERT(LongOrdinal::kOneDigit == '1',
59               LongOrdinalkOneDigit_incorrect);
60COMPILE_ASSERT(LongOrdinal::kMidDigit == '5',
61               LongOrdinalkMidDigit_incorrect);
62COMPILE_ASSERT(LongOrdinal::kMaxDigit == '9',
63               LongOrdinalkMaxDigit_incorrect);
64COMPILE_ASSERT(LongOrdinal::kMidDigitValue == 5,
65               LongOrdinalkMidDigitValue_incorrect);
66COMPILE_ASSERT(LongOrdinal::kMaxDigitValue == 9,
67               LongOrdinalkMaxDigitValue_incorrect);
68COMPILE_ASSERT(LongOrdinal::kRadix == 10,
69               LongOrdinalkRadix_incorrect);
70
71COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kZeroDigit) == '\x00',
72               LargeOrdinalkZeroDigit_incorrect);
73COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kOneDigit) == '\x01',
74               LargeOrdinalkOneDigit_incorrect);
75COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kMidDigit) == '\x80',
76               LargeOrdinalkMidDigit_incorrect);
77COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kMaxDigit) == '\xff',
78               LargeOrdinalkMaxDigit_incorrect);
79COMPILE_ASSERT(LargeOrdinal::kMidDigitValue == 128,
80               LargeOrdinalkMidDigitValue_incorrect);
81COMPILE_ASSERT(LargeOrdinal::kMaxDigitValue == 255,
82               LargeOrdinalkMaxDigitValue_incorrect);
83COMPILE_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.
88TEST(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.
113TEST(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.
121TEST(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.
132TEST(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.
144TEST(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.
165TEST(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.
174TEST(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.
194TEST(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.
207TEST(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
213bool 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.
225TEST(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.
240TEST(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
260template <typename Traits>
261std::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.
274TEST(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.
283TEST(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.
299TEST(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.
314TEST(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.
321TEST(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.
330TEST(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.
340TEST(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.
355TEST(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