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, 28 insertions, 81 deletions

diff --git a/sync/syncable/directory.h b/sync/syncable/directory.h
index 51ceaf8..61c5522 100644
--- a/sync/syncable/directory.h
+++ b/sync/syncable/directory.h
@@ -17,6 +17,7 @@
 #include "sync/syncable/dir_open_result.h"
 #include "sync/syncable/entry_kernel.h"
 #include "sync/syncable/metahandle_set.h"
+#include "sync/syncable/parent_child_index.h"
 #include "sync/syncable/scoped_kernel_lock.h"
 #include "sync/syncable/syncable_delete_journal.h"
 
@@ -86,21 +87,6 @@ struct ClientTagIndexer {
   static bool ShouldInclude(const EntryKernel* a);
 };
 
-// This index contains EntryKernels ordered by parent ID and metahandle.
-// It allows efficient lookup of the children of a given parent.
-struct ParentIdAndHandleIndexer {
-  // This index is of the parent ID and metahandle.  We use a custom
-  // comparator.
-  class Comparator {
-   public:
-    bool operator() (const syncable::EntryKernel* a,
-                     const syncable::EntryKernel* b) const;
-  };
-
-  // This index does not include deleted items.
-  static bool ShouldInclude(const EntryKernel* a);
-};
-
 // Given an Indexer providing the semantics of an index, defines the
 // set type used to actually contain the index.
 template <typename Indexer>
@@ -108,13 +94,6 @@ struct Index {
   typedef std::set<EntryKernel*, typename Indexer::Comparator> Set;
 };
 
-// Reason for unlinking.
-enum UnlinkReason {
-  NODE_MANIPULATION, // To be used by any operation manipulating the linked
-                     // list.
-  DATA_TYPE_PURGE    // To be used when purging a dataype.
-};
-
 enum InvariantCheckLevel {
   OFF = 0,            // No checking.
   VERIFY_CHANGES = 1, // Checks only mutated entries.  Does not check hierarchy.
@@ -126,9 +105,7 @@ class SYNC_EXPORT Directory {
   friend class Entry;
   friend class MutableEntry;
   friend class ReadTransaction;
-  friend class ReadTransactionWithoutDB;
   friend class ScopedKernelLock;
-  friend class ScopedKernelUnlock;
   friend class WriteTransaction;
   friend class SyncableDirectoryTest;
   friend class syncer::TestUserShare;
@@ -233,9 +210,8 @@ class SYNC_EXPORT Directory {
   void Close();
 
   int64 NextMetahandle();
-  // Always returns a negative id.  Positive client ids are generated
-  // by the server only.
-  Id NextId();
+  // Returns a negative integer unique to this client.
+  syncable::Id NextId();
 
   bool good() const { return NULL != kernel_; }
 
@@ -320,13 +296,6 @@ class SYNC_EXPORT Directory {
                        const Id& new_parent_id);
   void ClearDirtyMetahandles();
 
-  // These don't do semantic checking.
-  // The semantic checking is implemented higher up.
-  bool UnlinkEntryFromOrder(EntryKernel* entry,
-                            WriteTransaction* trans,
-                            ScopedKernelLock* lock,
-                            UnlinkReason unlink_reason);
-
   DirOpenResult OpenImpl(
       const std::string& name,
       DirectoryChangeDelegate* delegate,
@@ -337,8 +306,6 @@ class SYNC_EXPORT Directory {
   // before calling.
   EntryKernel* GetEntryById(const Id& id, ScopedKernelLock* const lock);
 
-  template <class T> void TestAndSet(T* kernel_data, const T* data_to_set);
-
  public:
   typedef std::vector<int64> ChildHandles;
 
@@ -361,23 +328,27 @@ class SYNC_EXPORT Directory {
   // and fill in |*first_child_id| with its id.  Fills in a root Id if
   // parent has no children.  Returns true if the first child was
   // successfully found, or false if an error was encountered.
-  bool GetFirstChildId(BaseTransaction* trans, const Id& parent_id,
-                       Id* first_child_id) WARN_UNUSED_RESULT;
+  Id GetFirstChildId(BaseTransaction* trans, const EntryKernel* parent);
 
-  // Find the last child in the positional ordering under a parent,
-  // and fill in |*first_child_id| with its id.  Fills in a root Id if
-  // parent has no children.  Returns true if the first child was
-  // successfully found, or false if an error was encountered.
-  bool GetLastChildIdForTest(BaseTransaction* trans, const Id& parent_id,
-                             Id* last_child_id) WARN_UNUSED_RESULT;
+  // These functions allow one to fetch the next or previous item under
+  // the same folder.  Returns the "root" ID if there is no predecessor
+  // or successor.
+  //
+  // TODO(rlarocque): These functions are used mainly for tree traversal.  We
+  // should replace these with an iterator API.  See crbug.com/178275.
+  syncable::Id GetPredecessorId(EntryKernel*);
+  syncable::Id GetSuccessorId(EntryKernel*);
 
-  // Compute a local predecessor position for |update_item|.  The position
-  // is determined by the SERVER_POSITION_IN_PARENT value of |update_item|,
-  // as well as the SERVER_POSITION_IN_PARENT values of any up-to-date
-  // children of |parent_id|.
-  Id ComputePrevIdFromServerPosition(
-      const EntryKernel* update_item,
-      const syncable::Id& parent_id);
+  // Places |e| as a successor to |predecessor|.  If |predecessor| is NULL,
+  // |e| will be placed as the left-most item in its folder.
+  //
+  // Both |e| and |predecessor| must be valid entries under the same parent.
+  //
+  // TODO(rlarocque): This function includes limited support for placing items
+  // with valid positions (ie. Bookmarks) as siblings of items that have no set
+  // ordering (ie. Autofill items).  This support is required only for tests,
+  // and should be removed.  See crbug.com/178282.
+  void PutPredecessor(EntryKernel* e, EntryKernel* predecessor);
 
   // SaveChanges works by taking a consistent snapshot of the current Directory
   // state and indices (by deep copy) under a ReadTransaction, passing this
@@ -486,12 +457,9 @@ class SYNC_EXPORT Directory {
   Directory& operator = (const Directory&);
 
  public:
+  // These contain all items, including IS_DEL items.
   typedef Index<MetahandleIndexer>::Set MetahandlesIndex;
   typedef Index<IdIndexer>::Set IdsIndex;
-  // All entries in memory must be in both the MetahandlesIndex and
-  // the IdsIndex, but only non-deleted entries will be the
-  // ParentIdChildIndex.
-  typedef Index<ParentIdAndHandleIndexer>::Set ParentIdChildIndex;
 
   // Contains both deleted and existing entries with tags.
   // We can't store only existing tags because the client would create
@@ -538,7 +506,11 @@ class SYNC_EXPORT Directory {
     MetahandlesIndex* metahandles_index;
     // Entries indexed by id
     IdsIndex* ids_index;
-    ParentIdChildIndex* parent_id_child_index;
+
+    // Contains non-deleted items, indexed according to parent and position
+    // within parent.  Protected by the ScopedKernelLock.
+    ParentChildIndex* parent_child_index;
+
     ClientTagIndex* client_tag_index;
     // So we don't have to create an EntryKernel every time we want to
     // look something up in an index.  Needle in haystack metaphor.
@@ -583,36 +555,11 @@ class SYNC_EXPORT Directory {
     const WeakHandle<TransactionObserver> transaction_observer;
   };
 
-  // Helper method used to do searches on |parent_id_child_index|.
-  ParentIdChildIndex::iterator LocateInParentChildIndex(
-      const ScopedKernelLock& lock,
-      const Id& parent_id,
-      int64 position_in_parent,
-      const Id& item_id_for_tiebreaking);
-
-  // Return an iterator to the beginning of the range of the children of
-  // |parent_id| in the kernel's parent_id_child_index.
-  ParentIdChildIndex::iterator GetParentChildIndexLowerBound(
-      const ScopedKernelLock& lock,
-      const Id& parent_id);
-
-  // Return an iterator to just past the end of the range of the
-  // children of |parent_id| in the kernel's parent_id_child_index.
-  ParentIdChildIndex::iterator GetParentChildIndexUpperBound(
-      const ScopedKernelLock& lock,
-      const Id& parent_id);
-
   // Append the handles of the children of |parent_id| to |result|.
   void AppendChildHandles(
       const ScopedKernelLock& lock,
       const Id& parent_id, Directory::ChildHandles* result);
 
-  // Return a pointer to what is probably (but not certainly) the
-  // first child of |parent_id|, or NULL if |parent_id| definitely has
-  // no children.
-  EntryKernel* GetPossibleFirstChild(
-      const ScopedKernelLock& lock, const Id& parent_id);
-
   Kernel* kernel_;
 
   scoped_ptr<DirectoryBackingStore> store_;