Sync: Support nodes with implicit permanent folders: Node Browser and out-of-order loading from DB

sync/syncable/parent_child_index.cc

Index: sync/syncable/parent_child_index.cc
diff --git a/sync/syncable/parent_child_index.cc b/sync/syncable/parent_child_index.cc
index 0cab1d3942eb47b0bc1d1ebb8215633deef4492b..274461a02f4445f8a98be9efe5b4a918b07b7da8 100644
--- a/sync/syncable/parent_child_index.cc
+++ b/sync/syncable/parent_child_index.cc
@@ -43,40 +43,79 @@ ParentChildIndex::ParentChildIndex() {
 }
 
 ParentChildIndex::~ParentChildIndex() {
-  STLDeleteContainerPairSecondPointers(
-      parent_children_map_.begin(), parent_children_map_.end());
+  for (ParentChildrenMap::iterator it = parent_children_map_.begin();
+       it != parent_children_map_.end(); ++it) {
+    if (it->second.owned()) {
+      delete it->second.child_set();
+    }
+  }
 }
 
 bool ParentChildIndex::ShouldInclude(const EntryKernel* entry) {
   // This index excludes deleted items and the root item.  The root
   // item is excluded so that it doesn't show up as a child of itself.
-  return !entry->ref(IS_DEL) && !entry->ref(ID).IsRoot();
+  // The index also excludes items without client data e.g. the items
+  // that don't have client SPECIFICS or PARENT_ID. There is no need to
+  // include server-only entries because they shouldn't show up on the client

[Nicolas Zea, 2015/07/09 20:36:34]

nit: "on the client until they're applied."

[stanisc, 2015/07/09 23:59:27]

Done.

+  return !entry->ref(IS_DEL) && !entry->ref(ID).IsRoot() &&
+         (entry->GetModelType() != UNSPECIFIED ||
+          !entry->ref(PARENT_ID).IsNull());
 }
 
 bool ParentChildIndex::Insert(EntryKernel* entry) {
   DCHECK(ShouldInclude(entry));
 
-  const Id& parent_id = GetParentId(entry);
-  // Store type root ID when inserting a type root entry.
-  if (parent_id.IsRoot()) {
-    ModelType model_type = GetModelType(entry);
-    // TODO(stanisc): there are some unit tests that create entries
-    // at the root and don't bother initializing specifics which
-    // produces TOP_LEVEL_FOLDER type here.
-    if (syncer::IsRealDataType(model_type)) {
-      model_type_root_ids_[model_type] = entry->ref(ID);
+  OrderedChildSet* children = nullptr;

[Nicolas Zea, 2015/07/09 20:36:34]

nit: children here implies to me that they're children of the entry itself. In
fact they're the siblings right? Perhaps consider renaming?

[stanisc, 2015/07/09 23:59:27]

Done.

+  const Id& parent_id = entry->ref(PARENT_ID);
+  ModelType model_type = entry->GetModelType();
+
+  if (ShouldUseParentId(parent_id, model_type)) {
+    // Hierarchical type, lookup child set in the map.
+    DCHECK(!parent_id.IsNull());
+    ParentChildrenMap::iterator it = parent_children_map_.find(parent_id);
+    if (it != parent_children_map_.end()) {
+      children = it->second.child_set();
     }
+  } else {
+    // Non-hierarchical type, return a pre-defined collection by type.
+    children = &type_root_child_sets_[model_type];
   }
 
-  OrderedChildSet* children = NULL;
-  ParentChildrenMap::iterator i = parent_children_map_.find(parent_id);
-  if (i != parent_children_map_.end()) {
-    children = i->second;
-  } else {
+  if (!children) {
+    DCHECK(!parent_id.IsNull());
     children = new OrderedChildSet();
-    parent_children_map_.insert(std::make_pair(parent_id, children));
+    InsertChildSet(parent_id, ChildSetEntry(children, true));
   }
 
+  // If this is one of type root folder for a non-hierarchical type, associate
+  // its ID with the model type and the type's pre-defined child set with the
+  // type root ID.
+  if (parent_id.IsRoot() && entry->ref(IS_DIR) &&
+      syncer::IsRealDataType(model_type) &&
+      !TypeSupportsHierarchy(model_type)) {

[Nicolas Zea, 2015/07/09 20:36:34]

Isn't TypeSupportsHierarchy a sufficient condition here?

[stanisc, 2015/07/09 21:45:17]

Since the condition is "not TypeSupportsHierarchy" it included top folders and
other legacy cases that I wanted to be handled by the PARENT_ID based approach.
Perhaps TypeSupportsHierarchy condition isn't accurate enough. I'll review this
one more time.

[stanisc, 2015/07/09 23:59:27]

Discussed. Added TODO.

+    const Id& type_root_id = entry->ref(ID);
+    // Disassociate the type root child set with the previous ID if any.
+    const Id& prev_type_root_id = model_type_root_ids_[model_type];
+    if (!prev_type_root_id.IsNull()) {
+      ParentChildrenMap::iterator it =
+          parent_children_map_.find(prev_type_root_id);
+      if (it != parent_children_map_.end()) {
+        // If the entry exists in the map it must already have the same
+        // model type specific child set and now own it. In this case

[stanisc, 2015/07/09 20:33:48]

"now own" -> "not own"

[stanisc, 2015/07/09 23:59:27]

Done.

+        // it should be safe to simply remove the entry.
+        DCHECK(!it->second.owned());
+        DCHECK_EQ(it->second.child_set(), &type_root_child_sets_[model_type]);
+        parent_children_map_.erase(it);
+      }
+    }
+    // Store the new type root ID and associate the child set.
+    // Note that the child set isn't owned by the map in this case.
+    model_type_root_ids_[model_type] = type_root_id;
+    InsertChildSet(type_root_id,
+                   ChildSetEntry(&type_root_child_sets_[model_type], false));
+  }
+
+  // Finally, insert the entry in the child set.
   return children->insert(entry).second;
 }
 
@@ -84,32 +123,39 @@ bool ParentChildIndex::Insert(EntryKernel* entry) {
 // one does not own any EntryKernels.  This function removes references to the
 // given EntryKernel but does not delete it.
 void ParentChildIndex::Remove(EntryKernel* e) {
-  const Id& parent_id = GetParentId(e);
-
-  ParentChildrenMap::iterator parent = parent_children_map_.find(parent_id);
-  DCHECK(parent != parent_children_map_.end());
+  OrderedChildSet* children = nullptr;
+  ModelType model_type = e->GetModelType();
+  const Id& parent_id = e->ref(PARENT_ID);
+  bool is_owned = false;
+  ParentChildrenMap::iterator it;
+
+  if (ShouldUseParentId(parent_id, model_type)) {
+    // Hierarchical type, lookup child set in the map.
+    DCHECK(!parent_id.IsNull());
+    it = parent_children_map_.find(parent_id);
+    DCHECK(it != parent_children_map_.end());
+    children = it->second.child_set();
+    is_owned = it->second.owned();
+  } else {
+    // Non-hierarchical type, return a pre-defined child set by type.
+    children = &type_root_child_sets_[model_type];
+  }
 
-  OrderedChildSet* children = parent->second;
   OrderedChildSet::iterator j = children->find(e);
   DCHECK(j != children->end());
 
+  // Erase the entry from the child set.
   children->erase(j);
-  if (children->empty()) {
+  // If the set is now empty and is owned by the map, erase it from the map.
+  if (children->empty() && is_owned) {
     delete children;
-    parent_children_map_.erase(parent);
+    parent_children_map_.erase(it);
   }
 }
 
 bool ParentChildIndex::Contains(EntryKernel *e) const {
-  const Id& parent_id = GetParentId(e);
-  ParentChildrenMap::const_iterator parent =
-      parent_children_map_.find(parent_id);
-  if (parent == parent_children_map_.end()) {
-    return false;
-  }
-  const OrderedChildSet* children = parent->second;
-  DCHECK(children && !children->empty());
-  return children->count(e) > 0;
+  const OrderedChildSet* children = GetChildSet(e);
+  return children && children->count(e) > 0;
 }
 
 const OrderedChildSet* ParentChildIndex::GetChildren(const Id& id) const {
@@ -120,9 +166,12 @@ const OrderedChildSet* ParentChildIndex::GetChildren(const Id& id) const {
     return nullptr;
   }
 
-  // A successful lookup implies at least some children exist.
-  DCHECK(!parent->second->empty());
-  return parent->second;
+  OrderedChildSet* children = parent->second.child_set();
+  // The expectation is that the function returns nullptr instead of an empty
+  // child set
+  if (children && children->empty())
+    children = nullptr;
+  return children;
 }
 
 const OrderedChildSet* ParentChildIndex::GetChildren(EntryKernel* e) const {
@@ -130,32 +179,45 @@ const OrderedChildSet* ParentChildIndex::GetChildren(EntryKernel* e) const {
 }
 
 const OrderedChildSet* ParentChildIndex::GetSiblings(EntryKernel* e) const {
+  // This implies the entry is in the index.
   DCHECK(Contains(e));
-  const OrderedChildSet* siblings = GetChildren(GetParentId(e));
+  const OrderedChildSet* siblings = GetChildSet(e);
   DCHECK(siblings && !siblings->empty());
   return siblings;
 }
 
-const Id& ParentChildIndex::GetParentId(EntryKernel* e) const {
-  const Id& parent_id = e->ref(PARENT_ID);
-  if (!parent_id.IsNull()) {
-    return parent_id;
-  }
-  return GetModelTypeRootId(GetModelType(e));
+/* static */
+bool ParentChildIndex::ShouldUseParentId(const Id& parent_id,
+                                         ModelType model_type) {
+  // Returns true for compatibility with legacy unit tests.
+  return parent_id.IsRoot() || TypeSupportsHierarchy(model_type) ||
+         !syncer::IsRealDataType(model_type);
 }
 
-ModelType ParentChildIndex::GetModelType(EntryKernel* e) {
-  // TODO(stanisc): is there a more effective way to find out model type?
+const OrderedChildSet* ParentChildIndex::GetChildSet(EntryKernel* e) const {
   ModelType model_type = e->GetModelType();
-  if (!syncer::IsRealDataType(model_type)) {
-    model_type = e->GetServerModelType();
+
+  const Id& parent_id = e->ref(PARENT_ID);
+  if (ShouldUseParentId(parent_id, model_type)) {
+    // Hierarchical type, lookup child set in the map.
+    ParentChildrenMap::const_iterator it = parent_children_map_.find(parent_id);
+    if (it != parent_children_map_.end()) {
+      return it->second.child_set();
+    }
+  } else {
+    // Non-hierarchical type, return a pre-defined collection by type.
+    return &type_root_child_sets_[model_type];
   }
-  return model_type;
+
+  return nullptr;
+}
+
+void ParentChildIndex::InsertChildSet(const Id& id,
+                                      const ChildSetEntry& entry) {
+  parent_children_map_.insert(std::make_pair(id, entry));
 }
 
 const Id& ParentChildIndex::GetModelTypeRootId(ModelType model_type) const {
-  // TODO(stanisc): Review whether this approach is reliable enough.
-  // Should this method simply enumerate children of root node ("r") instead?
   return model_type_root_ids_[model_type];
 }