Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
11569045:
Initial UniquePositions implementation (Closed)
|
Created:
8 years ago by rlarocque Modified:
7 years, 11 months ago Reviewers:
akalin CC:
chromium-reviews, Raghu Simha, haitaol1, tim (not reviewing) Base URL:
svn://svn.chromium.org/chrome/trunk/src Visibility:
Public. |
DescriptionInitial UniquePositions implementation
Introduces a new class that represents an item's position within an
arbitrarily ordered list. It's currently biased towards bookmarks, but
it could be made more generic if there was a need for it.
This class supports inserting before, after, or between other
UniquePosition items. It never runs out of position values, though it
can use up unbounded space in the worst case.
In addition to the basics mentioned above, it also has support for other
functions that are particularly useful for bookmark sync. The positions
are serializable and de-serializable, for storage and transimission.
They also support conversion to and from int64 values, allowing them to
operate with old-style positions.
The class is not currently used anywhere. This commit includes only its
implementation and some tests.
BUG=145412
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=175462
Patch Set 1 #
Total comments: 12
Patch Set 2 : Address comments #
Total comments: 3
Patch Set 3 : More tests + cache_guid style suffixes #Patch Set 4 : Update algorithm #
Total comments: 24
Patch Set 5 : Review fixes #Patch Set 6 : Update class comments #
Messages
Total messages: 20 (0 generated)
Here's an attempt at implementing the UniquePosition class. At first I had tried to reuse as much of NodeOrdinal's code as possible, but I kept running into corner cases with no obvious solution. This became particularly problematic when trying to optimize for length. Whereas NodeOrdinals midpoint algorithm would looking for any string X that fits between two given input strings, the UniquePosition class must find a string X such that X ++ suffix ++ terminator is between those two inputs. The append can have a significant impact on the comparison, so I started to doubt that it was possible for a suffix-unaware algorithm to produce correct result without producing unnecessarily large result strings. I eventually gave up on amending the ordinals code and decided to try something based on lexicographic comparison, rather than the more integer-math oriented ordinals. The resulting algorithm is somewhere in the ballpark of O(n^2), because it performs a strcmp() for every digit it prepends to the result ordinal. Please review, and let me know if you can find a better approach.
https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... File sync/internal_api/public/base/unique_position.cc (right): https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:270: mid.push_back((b_digit + a_digit) / 2U); can overflow? perhaps a_digit + (b_digit - a_digit) / 2?
Following our talk at lunch, I've been rethinking the suffix system. If we want to make bookmarks a 'unique_client_tag' type like all the others, then it would make sense for the current 'bookmark_unique_tag' to resemble a 'unique_client_tag' as much as possible. That would make it a 20 byte hash which is then base64 encoded, for a total of 28 bytes. Changing the suffix length later on would be very difficult, so it's important to get this right. The impacts to the code presented here should be minor. The suffix length will be increased to 28 and the 0xFF terminator removed (since we now have a guarantee that the suffix does not end in trailing NULLs).
initial comments, just looked at the main algorithms I'm still trying to think of a way to avoid the O(n^2) behavior https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... File sync/internal_api/public/base/unique_position.cc (right): https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:223: if (digit != 255) { use kuint8max https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:224: ret.push_back((digit+256U)/2U); prefer "digit + (kuint8max - digit + 1) / 2" as it's easier to see that that expression is > digit https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:227: ret.push_back(255); kuint8max https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:238: ret.push_back(255); here too also before -> reference https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:277: if (suffixFF < before.substr(i, 0) && after.substr(i, 0) < suffixFF) { hey how does this work? you want the substring of before from i to the end, right? I don't think 0 is the right value to use (it just returns the empty string) also, don't you want i + 1? and "before.substr(...) < suffixFF && suffixFF < after.substr(...)"? I'm confused...
Addressed comments. I was a bit concerned with some of your suggested digit calculation expressions, particularly with regard to sign-extension in the division operation. However, if the expressions are getting converted to 'int' size that shouldn't be a problem. Maybe I was being overly paranoid when I put a 'U' next to all my constants. https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... File sync/internal_api/public/base/unique_position.cc (right): https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:223: if (digit != 255) { On 2012/12/18 22:38:20, akalin wrote: > use kuint8max Done. https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:224: ret.push_back((digit+256U)/2U); On 2012/12/18 22:38:20, akalin wrote: > prefer "digit + (kuint8max - digit + 1) / 2" as it's easier to see that that > expression is > digit Done. https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:227: ret.push_back(255); On 2012/12/18 22:38:20, akalin wrote: > kuint8max Done. https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:238: ret.push_back(255); On 2012/12/18 22:38:20, akalin wrote: > here too > > also before -> reference Done. https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:270: mid.push_back((b_digit + a_digit) / 2U); On 2012/12/17 18:47:45, akalin wrote: > can overflow? perhaps a_digit + (b_digit - a_digit) / 2? Done. https://codereview.chromium.org/11569045/diff/1/sync/internal_api/public/base... sync/internal_api/public/base/unique_position.cc:277: if (suffixFF < before.substr(i, 0) && after.substr(i, 0) < suffixFF) { On 2012/12/18 22:38:20, akalin wrote: > hey how does this work? you want the substring of before from i to the end, > right? I don't think 0 is the right value to use (it just returns the empty > string) > > also, don't you want i + 1? and "before.substr(...) < suffixFF && suffixFF < > after.substr(...)"? I'm confused... Yep, that's very wrong. We can get away with it because suffixFF < "" always returns false, so we never enter this if branch. This makes the algorithm less effective at finding the shortest possible string, but the strings it eventually does return will be between |before| and |after|. For some reason, fixing this leads to slightly longer positions being generated in the stress tests.
On 2012/12/18 23:51:08, rlarocque wrote: > I was a bit concerned with some of your suggested digit calculation expressions, > particularly with regard to sign-extension in the division operation. However, > if the expressions are getting converted to 'int' size that shouldn't be a > problem. Maybe I was being overly paranoid when I put a 'U' next to all my > constants. Can you elaborate? The divisors should all be positive, so there's no sign-extension going on, right?
On 2012/12/18 22:38:20, akalin wrote: > I'm still trying to think of a way to avoid the O(n^2) behavior Okay, I think I came up with a faster algorithm, but I don't think it's practical. Basically, it involves suffix trees/arrays ( http://en.wikipedia.org/wiki/Suffix_tree ) which are O(n) to construct. For example, CreateBefore can be done as follows: def CreateBefore(ref, suffix): a = MakeSuffixArray(ref) find the smallest index i of a such that suffix < ref.substr(a[i]) using binary search return ref.substr(0, a[i]) + suffix Let m = len(ref) and n = len(suffix) <= m. Then this is O(m) + O(n * lg m) + O(m + n) = O(m lg m). You can make it O(m * k) where k is the size of the alphabet (256 for chars) if you convert the suffix array into a suffix 'trie', so that you can just index into the trie immediately instead of doing a binary search, so that's linear time depending on your definition of linear time. Anyway, this isn't practical because our suffix length is already fixed small anyway, so O(n^2) is also fixed. And this doesn't return the smallest string that's smaller than ref. Maybe it's worth putting a comment like: // The algorithms below are O(suffix-length^2), but that's okay since the suffix length is fixed and asymptotically faster algorithms (with e.g., suffix trees/arrays) aren't worth it for our suffix size.
On 2012/12/19 00:02:48, akalin wrote: > On 2012/12/18 23:51:08, rlarocque wrote: > > I was a bit concerned with some of your suggested digit calculation > expressions, > > particularly with regard to sign-extension in the division operation. > However, > > if the expressions are getting converted to 'int' size that shouldn't be a > > problem. Maybe I was being overly paranoid when I put a 'U' next to all my > > constants. > > Can you elaborate? The divisors should all be positive, so there's no > sign-extension going on, right? This was one issue I ran into when I was still using 'char' for some of these calculations. When (signed char)0xFE gets converted to an int, it would become 0xFFFF...FE. Perform a signed division by two and we get 0xFFFF...FF, not 0xFFFF...7f. Cast it back to a char, and the result is 0xFF (255), not 0x7F (127). That experience led me to pre-emptively place a U after all my integer constants. That was probably redundant because, IIRC, an expression involving a signed and an unsigned operand usually ends up with an unsigned result. So, because digit is a uint8, (digit + 1) should have an unsigned result even though the 1 is signed, which is what we need for the division to work properly. As for the comment above, I was a bit confused. I think we're hoping the expression gets converted to 'int', not unsigned int.
> > As for the comment above, I was a bit confused. I think we're hoping the > expression gets converted to 'int', not unsigned int. Let me rephrase again: We want it to be converted to 'unsigned int', not 'int'.
Spent some time thinking about this https://codereview.chromium.org/11569045/diff/7001/sync/internal_api/public/b... File sync/internal_api/public/base/unique_position.cc (right): https://codereview.chromium.org/11569045/diff/7001/sync/internal_api/public/b... sync/internal_api/public/base/unique_position.cc:178: // Does our suffix alone place us where we want to be? I think this is a faster and linear algorithm: int i = ref.find_first_not_of('\0'); int j = suffixFF.find_first_not_of('\0'); if (j > i) // j > i implies suffixFF < ref return suffixFF; if (suffixFF.substr(j) < ref.substr(i)) // pad suffixFF to have i '\0's return string(i - j, '\0') + suffixFF // pad suffixFF to have i + 1 ''\0's return string(i -j + 1, '\0') + suffixFF I think the other functions can be transformed similarly. What do you think? https://codereview.chromium.org/11569045/diff/7001/sync/internal_api/public/b... sync/internal_api/public/base/unique_position.cc:193: if (suffixFF < reference.substr(i+1)) { so assuming that each digit of suffix is uniform over 0-255, the number of times this branch is taken follows a (truncated) geometric distribution ( http://en.wikipedia.org/wiki/Geometric_distribution , with Y) with 'success' meaning finding a non-'\0' character and p = 255/256. The expected value of Y is therefore 1/255, which means the number of times we compare suffixFF to (a suffix of reference) is 1 + 1/255 (including the first time), so that's expected-time O(n).
TL;DR: Added tests and changed the suffixes to look more like unique_client_tags (base64 encoding of a SHA1 hash). The code for generating the suffix is now shared with unique_client_tag code, so it is not included in this patch. What follows is an explanation for why I made this change. =============== I added a test that tries to simulate what is probably the most common scenario: one client inserting bookmarks at the end of a list. It turns out that this was a very bad scenario for the code as it was written in patch set #2. Because the suffixes start with negative numbers (ie. lots of 0xFF digits), it took a lot of digits to insert after them. After 1024 insertions, the positions were over 1K long. Reversing the sign of the next_ids helped a lot. That made the suffixes of more recent items greater than the suffixes of less recent items, so the insert at end scenario required no additional digits. Everything was sorted without any effort. However, when the scenario was expanded to include more than one client, the positions started growing again (up to 127 bytes). I tried a few other systems. Putting the cache_guids in front of the suffix helped take the edge off some of the worse cases. Eventually I settled on using a unique_cache_guid-style suffix. The suffix is the result of a hash, making it effectively random and therefore eliminating the possibility of certain insertion patterns triggering worst-case scenarios. It turns out that the base64 encoding works fairly well in practice. It increases the length, though this is mitigated slightly because we no longer need the "terminator" digit. More important, though, is that it prevents suffixes from containing 0xFF or 0x00 digits, which gives us more room to insert before or after them. With this system, the length after 1024 insertions at the end of the list was ~150 bytes. That's not great, but at least we can expect that no insertion scenario will perform much better or worse than this. The same can't be said for the un-hashed suffixes.
https://codereview.chromium.org/11569045/diff/7001/sync/internal_api/public/b... File sync/internal_api/public/base/unique_position.cc (right): https://codereview.chromium.org/11569045/diff/7001/sync/internal_api/public/b... sync/internal_api/public/base/unique_position.cc:178: // Does our suffix alone place us where we want to be? On 2012/12/20 19:19:20, akalin wrote: > I think this is a faster and linear algorithm: > > int i = ref.find_first_not_of('\0'); > int j = suffixFF.find_first_not_of('\0'); > if (j > i) > // j > i implies suffixFF < ref > return suffixFF; > if (suffixFF.substr(j) < ref.substr(i)) > // pad suffixFF to have i '\0's > return string(i - j, '\0') + suffixFF > // pad suffixFF to have i + 1 ''\0's > return string(i -j + 1, '\0') + suffixFF > > I think the other functions can be transformed similarly. What do you think? Interesting. I'm still thinking about it, but my initial thought is that this could bloat the lengths of the positions. If I understand it correctly, assuming the suffixes are randomly distributed, then after a few insertions the common case will be j = 0, and the returned prefix will consist of either i or i+1 zeros. The size of that zero prefix could grow very quickly. I like the strategy of skipping over initial zeroes of both strings with a find, though. That's likely to be a useful optimization.
On 2012/12/20 20:09:50, rlarocque wrote: > Interesting. I'm still thinking about it, but my initial thought is that this > could bloat the lengths of the positions. If I understand it correctly, > assuming the suffixes are randomly distributed, then after a few insertions the > common case will be j = 0, and the returned prefix will consist of either i or > i+1 zeros. The size of that zero prefix could grow very quickly. Hmm, this algorithm should give the same results as yours, i.e. a returned value of minimum length, since it only zero-pads to the left as many characters as needed. The common case is i = j = 0, in which case either 0 or 1 character is prepended.
Sorry I realize what you mean now. Yeah, the last zero should be replaced by the appropriate digit / 2 to be the same as your algorithm. On Thursday, December 20, 2012, wrote: > On 2012/12/20 20:09:50, rlarocque wrote: > > Interesting. I'm still thinking about it, but my initial thought is that >> this >> could bloat the lengths of the positions. If I understand it correctly, >> assuming the suffixes are randomly distributed, then after a few >> insertions >> > the > >> common case will be j = 0, and the returned prefix will consist of either >> i or >> i+1 zeros. The size of that zero prefix could grow very quickly. >> > > Hmm, this algorithm should give the same results as yours, i.e. a returned > value > of minimum length, since it only zero-pads to the left as many characters > as > needed. The common case is i = j = 0, in which case either 0 or 1 > character is > prepended. > > > https://codereview.chromium.**org/11569045/<https://codereview.chromium.org/1... >
For completeness, the revised version:
int i = ref.find_first_not_of('\0');
int j = suffixFF.find_first_not_of('\0');
if (j > i)
// j > i implies suffixFF < ref
return suffixFF;
if (suffixFF.substr(j) < ref.substr(i))
// pad suffixFF to have i '\0's
return string(i - j, '\0') + suffixFF
// pad suffixFF to have i '\0's and a digit less than ref[i]
return string(i -j, '\0') + (ref[i]/2) + suffixFF
I think this gives exactly the same results as your version.
On 2012/12/20 21:56:56, akalin wrote:
> Sorry I realize what you mean now. Yeah, the last zero should be replaced
> by the appropriate digit / 2 to be the same as your algorithm.
On 2012/12/21 18:24:18, akalin wrote:
> For completeness, the revised version:
>
> int i = ref.find_first_not_of('\0');
> int j = suffixFF.find_first_not_of('\0');
> if (j > i)
> // j > i implies suffixFF < ref
> return suffixFF;
> if (suffixFF.substr(j) < ref.substr(i))
> // pad suffixFF to have i '\0's
> return string(i - j, '\0') + suffixFF
> // pad suffixFF to have i '\0's and a digit less than ref[i]
> return string(i -j, '\0') + (ref[i]/2) + suffixFF
>
> I think this gives exactly the same results as your version.
>
> On 2012/12/20 21:56:56, akalin wrote:
> > Sorry I realize what you mean now. Yeah, the last zero should be replaced
> > by the appropriate digit / 2 to be the same as your algorithm.
That's still not quite right, though I didn't realize that until the tests
forced me to think about it very carefully.
- The last return should be "string(i, '\0') + ..." because we can't take
advantage of the suffix's zeroes prefix (j) if we insert a non-zero digit
(ref[i]/2) before it.
- Sometimes the condition (suffixFF.substr(j) < ref.substr(i)) is false, but we
still do want to take advantage of the suffix's zeroes. We know that prepending
(i - j + 1) zeroes will give us a valid prefix. That valid prefix has length
less than the other option (string(i, '\0') + ref[i]/2) when j > 1.
I've uploaded a new patch that includes these amendments. PTAL.
PS: I ran some primitive tests and found that the new algorithm is 10x-150x
times faster than the original in release mode, while returning the exact same
results as the original. Thanks for the optimization!
lgtm i'm okay with landing this and iterating. otherwise, this review can take ages https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... File sync/internal_api/public/base/unique_position.cc (right): https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:42: const std::string& bytes) { fits on previous line? https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:101: UniquePosition::UniquePosition() : is_valid_(false) { }; "{ };" -> "{}" https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:158: DCHECK(ref_zeroes != std::string::npos); DCHECK_NE? https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:162: // Implies ref < suffix. backwards -- suffix < ref https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:177: char lt_digit = (uint8)reference[ref_zeroes]/2; static_cast<uint8>? https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:197: // Implies suffix > reference append . https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:212: char gt_digit = (uint8)reference[ref_FFs] + static_cast<uint8> https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:247: if (before.substr(i+1) < suffix && suffix < after.substr(i+1)) { pretty sure you can rewrite this one to something similar to FindLessThanWithSuffix, etc. Or something like before (+) FindLessThanWithSuffix(after (-) before, suffix (-) before) (where (+) and (-) treat the strings like binary numbers), right?) But I'm fine with leaving this as a TODO or something https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... File sync/internal_api/public/base/unique_position.h (right): https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.h:16: // By relying on the existence of unique suffixes, this class can ensure that it would like to have a blurb about the algebraic properties of UniquePosition, similar to the class comment for Ordinal. You can say mention transitivity, trichotomy, density, and unboundedness, but probably would have to modify them to take the suffixes into account. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.h:60: UniquePosition(); comment that this creates an invalid value https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... File sync/internal_api/public/base/unique_position_unittest.cc (right): https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position_unittest.cc:30: size_t GetLength(UniquePosition &pos) { const ref, space after & and not before https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position_unittest.cc:121: std::sort(&positions[0], &positions[kNumPositions], PositionLessThan()); sorting is undefined if the comparator is inconsistent, so may want to have some basic tests for PositionLessThan first
Comments addressed and new patch uploaded. I'll try to land this as is. Thanks for the thorough review. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... File sync/internal_api/public/base/unique_position.cc (right): https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:42: const std::string& bytes) { On 2012/12/29 10:17:13, akalin wrote: > fits on previous line? Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:101: UniquePosition::UniquePosition() : is_valid_(false) { }; On 2012/12/29 10:17:13, akalin wrote: > "{ };" -> "{}" Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:158: DCHECK(ref_zeroes != std::string::npos); On 2012/12/29 10:17:13, akalin wrote: > DCHECK_NE? Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:162: // Implies ref < suffix. On 2012/12/29 10:17:13, akalin wrote: > backwards -- suffix < ref Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:177: char lt_digit = (uint8)reference[ref_zeroes]/2; On 2012/12/29 10:17:13, akalin wrote: > static_cast<uint8>? Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:197: // Implies suffix > reference On 2012/12/29 10:17:13, akalin wrote: > append . Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:212: char gt_digit = (uint8)reference[ref_FFs] + On 2012/12/29 10:17:13, akalin wrote: > static_cast<uint8> Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.cc:247: if (before.substr(i+1) < suffix && suffix < after.substr(i+1)) { On 2012/12/29 10:17:13, akalin wrote: > pretty sure you can rewrite this one to something similar to > FindLessThanWithSuffix, etc. Or something like before (+) > FindLessThanWithSuffix(after (-) before, suffix (-) before) (where (+) and (-) > treat the strings like binary numbers), right?) > > But I'm fine with leaving this as a TODO or something I'm not sure I follow you. How would the binary subtraction "suffix (-) before" work if before > suffix? I'm not sure how relevant this is, since I don't understand what you're proposing. However, here's the corner case that haunts all my attempts to optimize this function: a == "ABCDE..." b == "ABCDG..." suffix == "CDF..." The ideal result would be "AB" + "CDF..." (ie. return with mid == "AB"), because "ABCDE..." < "AB" + "CDF..." < "ABCDG...". Any attempt to skip past the matching common prefix of 'a' and 'b' would skip past this result, because the common prefix is "ABCD". That's why I think any common prefix approach in the style of FindLessThanWithSuffix() won't work. There's probably some fast algorithm out there that handles this case properly. I don't think it's possible to do it with a single pass, though. I've added a comment suggesting we should take another look at this function at some point. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... File sync/internal_api/public/base/unique_position.h (right): https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.h:16: // By relying on the existence of unique suffixes, this class can ensure that it On 2012/12/29 10:17:13, akalin wrote: > would like to have a blurb about the algebraic properties of UniquePosition, > similar to the class comment for Ordinal. You can say mention transitivity, > trichotomy, density, and unboundedness, but probably would have to modify them > to take the suffixes into account. Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position.h:60: UniquePosition(); On 2012/12/29 10:17:13, akalin wrote: > comment that this creates an invalid value Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... File sync/internal_api/public/base/unique_position_unittest.cc (right): https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position_unittest.cc:30: size_t GetLength(UniquePosition &pos) { On 2012/12/29 10:17:13, akalin wrote: > const ref, space after & and not before Done. https://codereview.chromium.org/11569045/diff/20001/sync/internal_api/public/... sync/internal_api/public/base/unique_position_unittest.cc:121: std::sort(&positions[0], &positions[kNumPositions], PositionLessThan()); On 2012/12/29 10:17:13, akalin wrote: > sorting is undefined if the comparator is inconsistent, so may want to have some > basic tests for PositionLessThan first I've added some very basic sanity tests in some test cases above this one.
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/rlarocque@chromium.org/11569045/26002
Message was sent while issue was closed.
Change committed as 175462 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
