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