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#ifndef SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_
6#define SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_
7
8#include <string>
9
10#include "base/basictypes.h"
11#include "sync/base/sync_export.h"
12
13namespace sync_pb {
14class UniquePosition;
15}
16
17namespace syncer {
18
19// A class to represent positions.
20//
21// Valid UniquePosition objects have the following properties:
22//
23//  - a < b and b < c implies a < c (transitivity);
24//  - exactly one of a < b, b < a and a = b holds (trichotomy);
25//  - if a < b, there is a UniquePosition such that a < x < b (density);
26//  - there are UniquePositions x and y such that x < a < y (unboundedness);
27//  - if a and b were constructed with different unique suffixes, then a != b.
28//
29// As long as all UniquePositions used to sort a list were created with unique
30// suffixes, then if any item changes its position in the list, only its
31// UniquePosition value has to change to represent the new order, and all other
32// values can stay the same.
33//
34// Note that the unique suffixes must be exactly |kSuffixLength| bytes long.
35//
36// The cost for all these features is potentially unbounded space usage.  In
37// practice, however, most ordinals should be not much longer than the suffix.
38//
39// This class currently has several bookmarks-related assumptions built in,
40// though it could be adapted to be more generally useful.
41class SYNC_EXPORT_PRIVATE UniquePosition {
42 public:
43  static const size_t kSuffixLength;
44  static const size_t kCompressBytesThreshold;
45
46  static bool IsValidSuffix(const std::string& suffix);
47  static bool IsValidBytes(const std::string& bytes);
48
49  // Returns a valid, but mostly random suffix.
50  // Avoid using this; it can lead to inconsistent sort orderings if misused.
51  static std::string RandomSuffix();
52
53  // Returns an invalid position.
54  static UniquePosition CreateInvalid();
55
56  // Converts from a 'sync_pb::UniquePosition' protobuf to a UniquePosition.
57  // This may return an invalid position if the parsing fails.
58  static UniquePosition FromProto(const sync_pb::UniquePosition& proto);
59
60  // Creates a position with the given suffix.  Ordering among positions created
61  // from this function is the same as that of the integer parameters that were
62  // passed in.
63  static UniquePosition FromInt64(int64 i, const std::string& suffix);
64
65  // Returns a valid position.  Its ordering is not defined.
66  static UniquePosition InitialPosition(const std::string& suffix);
67
68  // Returns positions compare smaller than, greater than, or between the input
69  // positions.
70  static UniquePosition Before(const UniquePosition& x,
71                               const std::string& suffix);
72  static UniquePosition After(const UniquePosition& x,
73                              const std::string& suffix);
74  static UniquePosition Between(const UniquePosition& before,
75                                const UniquePosition& after,
76                                const std::string& suffix);
77
78  // This constructor creates an invalid value.
79  UniquePosition();
80
81  bool LessThan(const UniquePosition& other) const;
82  bool Equals(const UniquePosition& other) const;
83
84  // Serializes the position's internal state to a protobuf.
85  void ToProto(sync_pb::UniquePosition* proto) const;
86
87  // Serializes the protobuf representation of this object as a string.
88  void SerializeToString(std::string* blob) const;
89
90  // Returns a human-readable representation of this item's internal state.
91  std::string ToDebugString() const;
92
93  // Returns the suffix.
94  std::string GetSuffixForTest() const;
95
96  // Performs a lossy conversion to an int64 position.  Positions converted to
97  // and from int64s using this and the FromInt64 function should maintain their
98  // relative orderings unless the int64 values conflict.
99  int64 ToInt64() const;
100
101  bool IsValid() const;
102
103 private:
104  friend class UniquePositionTest;
105
106  // Returns a string X such that (X ++ |suffix|) < |str|.
107  // |str| must be a trailing substring of a valid ordinal.
108  // |suffix| must be a valid unique suffix.
109  static std::string FindSmallerWithSuffix(const std::string& str,
110                                           const std::string& suffix);
111  // Returns a string X such that (X ++ |suffix|) > |str|.
112  // |str| must be a trailing substring of a valid ordinal.
113  // |suffix| must be a valid unique suffix.
114  static std::string FindGreaterWithSuffix(const std::string& str,
115                                           const std::string& suffix);
116  // Returns a string X such that |before| < (X ++ |suffix|) < |after|.
117  // |before| and after must be a trailing substrings of valid ordinals.
118  // |suffix| must be a valid unique suffix.
119  static std::string FindBetweenWithSuffix(const std::string& before,
120                                           const std::string& after,
121                                           const std::string& suffix);
122
123  // Expects a run-length compressed string as input.  For internal use only.
124  explicit UniquePosition(const std::string& internal_rep);
125
126  // Expects an uncompressed prefix and suffix as input.  The |suffix| parameter
127  // must be a suffix of |uncompressed|.  For internal use only.
128  UniquePosition(const std::string& uncompressed, const std::string& suffix);
129
130  // Implementation of an order-preserving run-length compression scheme.
131  static std::string Compress(const std::string& input);
132  static std::string CompressImpl(const std::string& input);
133  static std::string Uncompress(const std::string& compressed);
134  static bool IsValidCompressed(const std::string& str);
135
136  // The position value after it has been run through the custom compression
137  // algorithm.  See Compress() and Uncompress() functions above.
138  std::string compressed_;
139  bool is_valid_;
140};
141
142}  // namespace syncer;
143
144#endif  // SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_
145