sync: Bookmark unique position end-to-end support

This change rewrites the bookmark positioning system to use absolute,
arbitrary-precision, unique positions from end-to-end.

First, it introduces the concept of a UNIQUE_BOOKMARK_TAG. This has a
similar format to the UNIQUE_CLIENT_TAG, though bookmarks have never
supported unique tags previously. For new items, it is initialized
based on the bookmark's originator client item ID (ie. the "c-" style
ID) and the originator's cache_guid. These values should be globally
unique.

Many previously created items that exist in the database do not have
this information available.  Non-committed items will still have this
information, and will have their tags set correctly.  Previously
committed items will have server style IDs and no hint as to what the
originator_cache_guid is.  In that common case, we will initialize the
tag with a "fake" one based solely on the server ID.  This has the
advantage of being something that all existing clients will agree on,
even it if new clients and updated items/the server will disagree with
them.

To bring everyone back into sync, whenever they receive an update
clients will access the included originator_cache_guid and
originator_client_item_id fields and reset the UNIQUE_BOOKMARK_TAG field
according to the values they find there.  Over time, clients should
converge towards the same tag values.

Next, this change adds the UNIQUE_POSITION and SERVER_UNIQUE_POSITION
fields to each entry. See the UniquePosition class documentation for
more information on their behaviour. New items should have their local
position updated when they are first inserted into the list, which
should happen shortly after they are initialized. Existing items will
have these fields populated from the SERVER_ORDINAL_IN_PARENT field and
the genrated UNIQUE_BOOKMARK_TAG. Unfortunately, all outstanding local
changes will be lost during the migration.

With the addition of UNIQUE_POSITION fields comes the removal of the
PREV_ID and NEXT_ID fields. This required significant refactoring of
the Directory so it could continue to support the PutPredecessor(),
GetPredecessorId(), GetSuccessorId() and GetFirstChildId() functions. A
new class, ParentChildIndex, has been introduced to contain some of the
complexity introduced by the new system. See that class' documentation
for more information.

Communication with the server has also been affected by this change.
The client will now set the unique_position field on every update. It
will also set the legacy server_position_in_parent field with a value
derrived from a truncation of its local UNIQUE_POSITION. This replaces
the existing server position in parent calculation through
interpolation.

The receipt of updates has been changed as well. If the client receives
an update with a unique_position, it will apply it. If the update was
written by an older client, it will contain only the
server_position_in_parent. In that case, the client will use that
position and the unique tag derrived from the update to construct a
unique position that approximates the server_position_in_parent value.
This will work well if the clients have not exceeded the available
precision in an int64. Otherwise, some spurious re-positioning may
occur.

Finally, all these changes required some updates to the tests. Some
arbitrary position assertions had to be updated, since the arbitrary
ordering has changed. Some test helpers have been updated to no longer
automatically place bookmarks at the end of the list; that logic has
been moved to the tests themselves.

BUG=145412, 126505, 147715, 101852, 107744, 112203, 123429, 177521, 20011


Review URL: https://chromiumcodereview.appspot.com/11885024

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@191767 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 4 insertions, 5 deletions

diff --git a/sync/internal_api/sync_manager_impl.h b/sync/internal_api/sync_manager_impl.h
index c0373cf..acc0175 100644
--- a/sync/internal_api/sync_manager_impl.h
+++ b/sync/internal_api/sync_manager_impl.h
@@ -220,11 +220,10 @@ class SYNC_EXPORT_PRIVATE SyncManagerImpl :
   typedef std::map<std::string, JsMessageHandler> JsMessageHandlerMap;
 
   // Determine if the parents or predecessors differ between the old and new
-  // versions of an entry stored in |a| and |b|.  Note that a node's index may
-  // change without its NEXT_ID changing if the node at NEXT_ID also moved (but
-  // the relative order is unchanged).  To handle such cases, we rely on the
-  // caller to treat a position update on any sibling as updating the positions
-  // of all siblings.
+  // versions of an entry.  Note that a node's index may change without its
+  // UNIQUE_POSITION changing if its sibling nodes were changed.  To handle such
+  // cases, we rely on the caller to treat a position update on any sibling as
+  // updating the positions of all siblings.
   bool VisiblePositionsDiffer(
       const syncable::EntryKernelMutation& mutation) const;