[Sync] Add HasChildren() function and use it instead of GetFirstChildId()

This avoids some crashes when we try to traverse the list to find the
first child and encounter a dangling Id.

Remove some spurious virtual keywords.

BUG=100907
TEST=


Review URL: http://codereview.chromium.org/8396022

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

13 files changed, 144 insertions, 42 deletions

diff --git a/chrome/browser/sync/glue/autofill_model_associator.cc b/chrome/browser/sync/glue/autofill_model_associator.cc
index a9ec19f..902f00a 100644
--- a/chrome/browser/sync/glue/autofill_model_associator.cc
+++ b/chrome/browser/sync/glue/autofill_model_associator.cc
@@ -387,7 +387,7 @@ bool AutofillModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
 
   // The sync model has user created nodes if the autofill folder has any
   // children.
-  *has_nodes = sync_api::kInvalidId != autofill_node.GetFirstChildId();
+  *has_nodes = autofill_node.HasChildren();
   return true;
 }
 
diff --git a/chrome/browser/sync/glue/bookmark_change_processor.cc b/chrome/browser/sync/glue/bookmark_change_processor.cc
index 3735201..864f014 100644
--- a/chrome/browser/sync/glue/bookmark_change_processor.cc
+++ b/chrome/browser/sync/glue/bookmark_change_processor.cc
@@ -90,7 +90,7 @@ void BookmarkChangeProcessor::RemoveOneSyncNode(
     return;
   }
   // This node should have no children.
-  DCHECK(sync_node.GetFirstChildId() == sync_api::kInvalidId);
+  DCHECK(!sync_node.HasChildren());
   // Remove association and delete the sync node.
   model_associator_->Disassociate(sync_node.GetId());
   sync_node.Remove();
diff --git a/chrome/browser/sync/glue/bookmark_model_associator.cc b/chrome/browser/sync/glue/bookmark_model_associator.cc
index 720632c..0e307c1 100644
--- a/chrome/browser/sync/glue/bookmark_model_associator.cc
+++ b/chrome/browser/sync/glue/bookmark_model_associator.cc
@@ -275,10 +275,9 @@ bool BookmarkModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
 
   // Sync model has user created nodes if either one of the permanent nodes
   // has children.
-  *has_nodes = bookmark_bar_node.GetFirstChildId() != sync_api::kInvalidId ||
-      other_bookmarks_node.GetFirstChildId() != sync_api::kInvalidId ||
-      (has_synced_folder &&
-          synced_bookmarks_node.GetFirstChildId() != sync_api::kInvalidId);
+  *has_nodes = bookmark_bar_node.HasChildren() ||
+      other_bookmarks_node.HasChildren() ||
+      (has_synced_folder && synced_bookmarks_node.HasChildren());
   return true;
 }
 
diff --git a/chrome/browser/sync/glue/generic_change_processor.cc b/chrome/browser/sync/glue/generic_change_processor.cc
index 56e17e6..95274ce 100644
--- a/chrome/browser/sync/glue/generic_change_processor.cc
+++ b/chrome/browser/sync/glue/generic_change_processor.cc
@@ -241,7 +241,7 @@ bool GenericChangeProcessor::SyncModelHasUserCreatedNodes(
 
   // The sync model has user created nodes if the type's root node has any
   // children.
-  *has_nodes = sync_api::kInvalidId != type_root_node.GetFirstChildId();
+  *has_nodes = type_root_node.HasChildren();
   return true;
 }
 
diff --git a/chrome/browser/sync/glue/password_model_associator.cc b/chrome/browser/sync/glue/password_model_associator.cc
index fecea08..519b729 100644
--- a/chrome/browser/sync/glue/password_model_associator.cc
+++ b/chrome/browser/sync/glue/password_model_associator.cc
@@ -209,7 +209,7 @@ bool PasswordModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
 
   // The sync model has user created nodes if the password folder has any
   // children.
-  *has_nodes = sync_api::kInvalidId != password_node.GetFirstChildId();
+  *has_nodes = password_node.HasChildren();
   return true;
 }
 
diff --git a/chrome/browser/sync/glue/session_model_associator.cc b/chrome/browser/sync/glue/session_model_associator.cc
index edec88d..a655891 100644
--- a/chrome/browser/sync/glue/session_model_associator.cc
+++ b/chrome/browser/sync/glue/session_model_associator.cc
@@ -101,7 +101,7 @@ bool SessionModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
   }
   // The sync model has user created nodes iff the sessions folder has
   // any children.
-  *has_nodes = root.GetFirstChildId() != sync_api::kInvalidId;
+  *has_nodes = root.HasChildren();
   return true;
 }
 
diff --git a/chrome/browser/sync/glue/theme_model_associator.cc b/chrome/browser/sync/glue/theme_model_associator.cc
index b854cbf..e410041 100644
--- a/chrome/browser/sync/glue/theme_model_associator.cc
+++ b/chrome/browser/sync/glue/theme_model_associator.cc
@@ -96,7 +96,7 @@ bool ThemeModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
   }
   // The sync model has user created nodes iff the themes folder has
   // any children.
-  *has_nodes = root.GetFirstChildId() != sync_api::kInvalidId;
+  *has_nodes = root.HasChildren();
   return true;
 }
 
diff --git a/chrome/browser/sync/glue/typed_url_model_associator.cc b/chrome/browser/sync/glue/typed_url_model_associator.cc
index 92fec6d..9ec26cf 100644
--- a/chrome/browser/sync/glue/typed_url_model_associator.cc
+++ b/chrome/browser/sync/glue/typed_url_model_associator.cc
@@ -429,7 +429,7 @@ bool TypedUrlModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) {
 
   // The sync model has user created nodes if the typed_url folder has any
   // children.
-  *has_nodes = sync_api::kInvalidId != typed_url_node.GetFirstChildId();
+  *has_nodes = typed_url_node.HasChildren();
   return true;
 }
 
diff --git a/chrome/browser/sync/internal_api/base_node.cc b/chrome/browser/sync/internal_api/base_node.cc
index c409b8a..2aa212c 100644
--- a/chrome/browser/sync/internal_api/base_node.cc
+++ b/chrome/browser/sync/internal_api/base_node.cc
@@ -201,6 +201,12 @@ GURL BaseNode::GetURL() const {
   return GURL(GetBookmarkSpecifics().url());
 }
 
+bool BaseNode::HasChildren() const {
+  syncable::Directory* dir = GetTransaction()->GetLookup();
+  syncable::BaseTransaction* trans = GetTransaction()->GetWrappedTrans();
+  return dir->HasChildren(trans, GetEntry()->Get(syncable::ID));
+}
+
 int64 BaseNode::GetPredecessorId() const {
   syncable::Id id_string = GetEntry()->Get(syncable::PREV_ID);
   if (id_string.IsRoot())
diff --git a/chrome/browser/sync/internal_api/base_node.h b/chrome/browser/sync/internal_api/base_node.h
index a2286c3..362fdc3 100644
--- a/chrome/browser/sync/internal_api/base_node.h
+++ b/chrome/browser/sync/internal_api/base_node.h
@@ -156,17 +156,20 @@ class BaseNode {
   // Returns the local external ID associated with the node.
   int64 GetExternalId() const;
 
+  // Returns true iff this node has children.
+  bool HasChildren() const;
+
   // Return the ID of the node immediately before this in the sibling order.
   // For the first node in the ordering, return 0.
   int64 GetPredecessorId() const;
 
   // Return the ID of the node immediately after this in the sibling order.
   // For the last node in the ordering, return 0.
-  virtual int64 GetSuccessorId() const;
+  int64 GetSuccessorId() const;
 
   // Return the ID of the first child of this node.  If this node has no
   // children, return 0.
-  virtual int64 GetFirstChildId() const;
+  int64 GetFirstChildId() const;
 
   // These virtual accessors provide access to data members of derived classes.
   virtual const syncable::Entry* GetEntry() const = 0;
diff --git a/chrome/browser/sync/syncable/syncable.cc b/chrome/browser/sync/syncable/syncable.cc
index 9038240..73ee43b 100644
--- a/chrome/browser/sync/syncable/syncable.cc
+++ b/chrome/browser/sync/syncable/syncable.cc
@@ -1765,33 +1765,27 @@ Id Directory::NextId() {
   return Id::CreateFromClientString(base::Int64ToString(result));
 }
 
+bool Directory::HasChildren(BaseTransaction* trans, const Id& id) {
+  ScopedKernelLock lock(this);
+  return (GetPossibleFirstChild(lock, id) != NULL);
+}
+
 Id Directory::GetFirstChildId(BaseTransaction* trans,
                               const Id& parent_id) {
   ScopedKernelLock lock(this);
-  // We can use the server positional ordering as a hint because it's generally
-  // in sync with the local (linked-list) positional ordering, and we have an
-  // index on it.
-  ParentIdChildIndex::iterator candidate =
-      GetParentChildIndexLowerBound(lock, parent_id);
-  ParentIdChildIndex::iterator end_range =
-      GetParentChildIndexUpperBound(lock, parent_id);
-  for (; candidate != end_range; ++candidate) {
-    EntryKernel* entry = *candidate;
-    // Filter out self-looped items, which are temporarily not in the child
-    // ordering.
-    if (entry->ref(PREV_ID).IsRoot() ||
-        entry->ref(PREV_ID) != entry->ref(NEXT_ID)) {
-      // Walk to the front of the list; the server position ordering
-      // is commonly identical to the linked-list ordering, but pending
-      // unsynced or unapplied items may diverge.
-      while (!entry->ref(PREV_ID).IsRoot()) {
-        entry = GetEntryById(entry->ref(PREV_ID), &lock);
-      }
-      return entry->ref(ID);
-    }
+  EntryKernel* entry = GetPossibleFirstChild(lock, parent_id);
+  if (!entry)
+    return Id();
+
+  // Walk to the front of the list; the server position ordering
+  // is commonly identical to the linked-list ordering, but pending
+  // unsynced or unapplied items may diverge.
+  while (!entry->ref(PREV_ID).IsRoot()) {
+    // TODO(akalin): Gracefully handle GetEntryById returning NULL
+    // (http://crbug.com/100907).
+    entry = GetEntryById(entry->ref(PREV_ID), &lock);
   }
-  // There were no children in the linked list.
-  return Id();
+  return entry->ref(ID);
 }
 
 Id Directory::GetLastChildId(BaseTransaction* trans,
@@ -1817,6 +1811,8 @@ Id Directory::GetLastChildId(BaseTransaction* trans,
       // is commonly identical to the linked-list ordering, but pending
       // unsynced or unapplied items may diverge.
       while (!entry->ref(NEXT_ID).IsRoot())
+        // TODO(akalin): Gracefully handle GetEntryById returning NULL
+        // (http://crbug.com/100907).
         entry = GetEntryById(entry->ref(NEXT_ID), &lock);
       return entry->ref(ID);
     }
@@ -1961,7 +1957,6 @@ Directory::GetParentChildIndexLowerBound(const ScopedKernelLock& lock,
       Id::GetLeastIdForLexicographicComparison());
 }
 
-
 Directory::ParentIdChildIndex::iterator
 Directory::GetParentChildIndexUpperBound(const ScopedKernelLock& lock,
                                          const Id& parent_id) {
@@ -1984,4 +1979,26 @@ void Directory::AppendChildHandles(const ScopedKernelLock& lock,
   }
 }
 
+EntryKernel* Directory::GetPossibleFirstChild(
+    const ScopedKernelLock& lock, const Id& parent_id) {
+  // We can use the server positional ordering as a hint because it's generally
+  // in sync with the local (linked-list) positional ordering, and we have an
+  // index on it.
+  ParentIdChildIndex::iterator candidate =
+      GetParentChildIndexLowerBound(lock, parent_id);
+  ParentIdChildIndex::iterator end_range =
+      GetParentChildIndexUpperBound(lock, parent_id);
+  for (; candidate != end_range; ++candidate) {
+    EntryKernel* entry = *candidate;
+    // Filter out self-looped items, which are temporarily not in the child
+    // ordering.
+    if (entry->ref(PREV_ID).IsRoot() ||
+        entry->ref(PREV_ID) != entry->ref(NEXT_ID)) {
+      return entry;
+    }
+  }
+  // There were no children in the linked list.
+  return NULL;
+}
+
 }  // namespace syncable
diff --git a/chrome/browser/sync/syncable/syncable.h b/chrome/browser/sync/syncable/syncable.h
index 4f8875f..73409a4 100644
--- a/chrome/browser/sync/syncable/syncable.h
+++ b/chrome/browser/sync/syncable/syncable.h
@@ -910,19 +910,24 @@ class Directory {
  public:
   typedef std::vector<int64> ChildHandles;
 
-  // Returns the child meta handles for given parent id.  Clears
-  // |result| if there are no children.
+  // Returns the child meta handles (even those for deleted/unlinked
+  // nodes) for given parent id.  Clears |result| if there are no
+  // children.
   void GetChildHandlesById(BaseTransaction*, const Id& parent_id,
       ChildHandles* result);
 
-  // Returns the child meta handles for given meta handle.  Clears
-  // |result| if there are no children.
+  // Returns the child meta handles (even those for deleted/unlinked
+  // nodes) for given meta handle.  Clears |result| if there are no
+  // children.
   void GetChildHandlesByHandle(BaseTransaction*, int64 handle,
       ChildHandles* result);
 
+  // Returns true iff |id| has children.
+  bool HasChildren(BaseTransaction* trans, const Id& id);
+
   // Find the first or last child in the positional ordering under a parent,
   // and return its id.  Returns a root Id if parent has no children.
-  virtual Id GetFirstChildId(BaseTransaction* trans, const Id& parent_id);
+  Id GetFirstChildId(BaseTransaction* trans, const Id& parent_id);
   Id GetLastChildId(BaseTransaction* trans, const Id& parent_id);
 
   // Compute a local predecessor position for |update_item|.  The position
@@ -1149,6 +1154,12 @@ class Directory {
       const ScopedKernelLock& lock,
       const Id& parent_id, Directory::ChildHandles* result);
 
+  // Returns 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_;
 
   DirectoryBackingStore* store_;
diff --git a/chrome/browser/sync/syncable/syncable_unittest.cc b/chrome/browser/sync/syncable/syncable_unittest.cc
index c0ce9bd..0950ada 100644
--- a/chrome/browser/sync/syncable/syncable_unittest.cc
+++ b/chrome/browser/sync/syncable/syncable_unittest.cc
@@ -207,6 +207,72 @@ TEST_F(SyncableGeneralTest, General) {
   dir.SaveChanges();
 }
 
+TEST_F(SyncableGeneralTest, ChildrenOps) {
+  Directory dir;
+  dir.Open(db_path_, "SimpleTest", &delegate_);
+
+  int64 root_metahandle;
+  {
+    ReadTransaction rtrans(FROM_HERE, &dir);
+    Entry e(&rtrans, GET_BY_ID, rtrans.root_id());
+    ASSERT_TRUE(e.good());
+    root_metahandle = e.Get(META_HANDLE);
+  }
+
+  int64 written_metahandle;
+  const Id id = TestIdFactory::FromNumber(99);
+  std::string name = "Jeff";
+  {
+    ReadTransaction rtrans(FROM_HERE, &dir);
+    Entry e(&rtrans, GET_BY_ID, id);
+    ASSERT_FALSE(e.good());  // Hasn't been written yet.
+
+    EXPECT_FALSE(dir.HasChildren(&rtrans, rtrans.root_id()));
+    EXPECT_TRUE(dir.GetFirstChildId(&rtrans, rtrans.root_id()).IsRoot());
+  }
+
+  {
+    WriteTransaction wtrans(FROM_HERE, UNITTEST, &dir);
+    MutableEntry me(&wtrans, CREATE, wtrans.root_id(), name);
+    ASSERT_TRUE(me.good());
+    me.Put(ID, id);
+    me.Put(BASE_VERSION, 1);
+    written_metahandle = me.Get(META_HANDLE);
+  }
+
+  // Test children ops after something is now in the DB.
+  {
+    ReadTransaction rtrans(FROM_HERE, &dir);
+    Entry e(&rtrans, GET_BY_ID, id);
+    ASSERT_TRUE(e.good());
+
+    Entry child(&rtrans, GET_BY_HANDLE, written_metahandle);
+    ASSERT_TRUE(child.good());
+
+    EXPECT_TRUE(dir.HasChildren(&rtrans, rtrans.root_id()));
+    EXPECT_EQ(e.Get(ID), dir.GetFirstChildId(&rtrans, rtrans.root_id()));
+  }
+
+  {
+    WriteTransaction wtrans(FROM_HERE, UNITTEST, &dir);
+    MutableEntry me(&wtrans, GET_BY_HANDLE, written_metahandle);
+    ASSERT_TRUE(me.good());
+    me.Put(IS_DEL, true);
+  }
+
+  // Test children ops after the children have been deleted.
+  {
+    ReadTransaction rtrans(FROM_HERE, &dir);
+    Entry e(&rtrans, GET_BY_ID, id);
+    ASSERT_TRUE(e.good());
+
+    EXPECT_FALSE(dir.HasChildren(&rtrans, rtrans.root_id()));
+    EXPECT_TRUE(dir.GetFirstChildId(&rtrans, rtrans.root_id()).IsRoot());
+  }
+
+  dir.SaveChanges();
+}
+
 TEST_F(SyncableGeneralTest, ClientIndexRebuildsProperly) {
   int64 written_metahandle;
   TestIdFactory factory;