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

sync/syncable/parent_child_index.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "sync/syncable/parent_child_index.h"
 
 #include "base/stl_util.h"
 
 #include "sync/syncable/entry_kernel.h"
 #include "sync/syncable/syncable_id.h"
@@ skipping 22 matching lines @@
   } else {
     // Position doesn't matter.
     DCHECK(!a->ref(UNIQUE_POSITION).IsValid());
     DCHECK(!b->ref(UNIQUE_POSITION).IsValid());
     // Sort by META_HANDLE to ensure consistent order for testing.
     return a->ref(META_HANDLE) < b->ref(META_HANDLE);
   }
 }
 
 ParentChildIndex::ParentChildIndex() {
+  // Pre-allocate these two vectors to the number of model types.
+  model_type_root_ids_.resize(MODEL_TYPE_COUNT);
+  type_root_child_sets_.resize(MODEL_TYPE_COUNT);
 }
 
 ParentChildIndex::~ParentChildIndex() {
-  STLDeleteContainerPairSecondPointers(
-      parent_children_map_.begin(), parent_children_map_.end());
+  for (int i = 0; i < MODEL_TYPE_COUNT; i++) {
+    // Normally all OrderedChildSet instances in |type_root_child_sets_|
+    // are shared with |parent_children_map_| and will be destroyed
+    // below. The only ones that haven't been shared are those that
+    // correspond to unset IDs in |model_type_root_ids_|.
+    if (type_root_child_sets_[i]) {
+      if (model_type_root_ids_[i].IsNull()) {
+        delete type_root_child_sets_[i];

[Nicolas Zea, 2015/07/10 00:12:57]

Would a scoped_vector work?

[stanisc, 2015/07/10 04:58:51]

Done.

+      } else {
+        DCHECK(parent_children_map_.find(model_type_root_ids_[i]) !=
+               parent_children_map_.end());
+      }
+    }
+  }
+
+  STLDeleteContainerPairSecondPointers(parent_children_map_.begin(),
+                                       parent_children_map_.end());
 }
 
 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 until
+  // they're applied.
+  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* siblings = nullptr;
+  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()) {
+      siblings = it->second;
+    } else {
+      siblings = new OrderedChildSet();
+      parent_children_map_.insert(std::make_pair(parent_id, siblings));
     }
+  } else {
+    // Non-hierarchical type, return a pre-defined collection by type.
+    siblings = GetOrCreateModelTypeChildSet(model_type);
   }
 
-  OrderedChildSet* children = NULL;
-  ParentChildrenMap::iterator i = parent_children_map_.find(parent_id);
-  if (i != parent_children_map_.end()) {
-    children = i->second;
-  } else {
-    children = new OrderedChildSet();
-    parent_children_map_.insert(std::make_pair(parent_id, children));
+  // 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.
+  // TODO(stanisc): crbug/438313: Just TypeSupportsHierarchy condition should
+  // theoretically be sufficient but in practice many tests don't properly
+  // initialize entries so TypeSupportsHierarchy ends up failing. Consider
+  // tweaking TypeSupportsHierarchy and fixing all related test code.
+  if (parent_id.IsRoot() && entry->ref(IS_DIR) &&
+      syncer::IsRealDataType(model_type) &&
+      !TypeSupportsHierarchy(model_type)) {
+    const Id& type_root_id = entry->ref(ID);
+    // Disassociate the type root child set with the previous ID if any.

[Nicolas Zea, 2015/07/10 00:12:57]

When would this happen?

[stanisc, 2015/07/10 04:58:51]

This happens when the type root folder ID is changed. With the current version
of the server the client first creates type root folders with local IDs (as soon
as progress marker for each type is received), then the server sends type root
folders with server IDs. Once the server is switched to implicit permanent
folders this should stop happening.
This condition is also exercised in one or two tests.

+    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. This child set will be re-inserted
+        // in the map under the new ID below so it is safe to simply erase
+        // the entry here.
+        DCHECK_EQ(it->second, GetModelTypeChildSet(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;
+    parent_children_map_.insert(
+        std::make_pair(type_root_id, GetOrCreateModelTypeChildSet(model_type)));
   }
 
-  return children->insert(entry).second;
+  // Finally, insert the entry in the child set.
+  return siblings->insert(entry).second;
 }
 
 // Like the other containers used to help support the syncable::Directory, this
 // 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);
+  OrderedChildSet* siblings = nullptr;
+  ModelType model_type = e->GetModelType();
+  const Id& parent_id = e->ref(PARENT_ID);
+  bool should_erase = false;
+  ParentChildrenMap::iterator it;
 
-  ParentChildrenMap::iterator parent = parent_children_map_.find(parent_id);
-  DCHECK(parent != parent_children_map_.end());
+  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());
+    siblings = it->second;
+    should_erase = true;
+  } else {
+    // Non-hierarchical type, return a pre-defined child set by type.
+    siblings = type_root_child_sets_[model_type];
+  }
 
-  OrderedChildSet* children = parent->second;
-  OrderedChildSet::iterator j = children->find(e);
-  DCHECK(j != children->end());
+  OrderedChildSet::iterator j = siblings->find(e);
+  DCHECK(j != siblings->end());
 
-  children->erase(j);
-  if (children->empty()) {
-    delete children;
-    parent_children_map_.erase(parent);
+  // Erase the entry from the child set.
+  siblings->erase(j);
+  // If the set is now empty and isn't shareable with |type_root_child_sets_|,
+  // erase it from the map.
+  if (siblings->empty() && should_erase) {
+    delete siblings;
+    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* siblings = GetChildSet(e);
+  return siblings && siblings->count(e) > 0;
 }
 
 const OrderedChildSet* ParentChildIndex::GetChildren(const Id& id) const {
   DCHECK(!id.IsNull());
 
   ParentChildrenMap::const_iterator parent = parent_children_map_.find(id);
   if (parent == parent_children_map_.end()) {
     return nullptr;
   }
 
-  // A successful lookup implies at least some children exist.
-  DCHECK(!parent->second->empty());
-  return parent->second;
+  OrderedChildSet* children = parent->second;
+  // 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 {
   return GetChildren(e->ref(ID));
 }
 
 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.

[Nicolas Zea, 2015/07/10 00:12:57]

I'm not sure I understand this comment? Returns true?

[stanisc, 2015/07/10 04:58:50]

Didn't finish the comment. Updated.

+  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;
+    }
+  } else {
+    // Non-hierarchical type, return a collection indexed by type.
+    return GetModelTypeChildSet(model_type);
   }
-  return model_type;
+
+  return nullptr;

[Nicolas Zea, 2015/07/10 00:12:57]

nit: how about rewriting this as:

if (ShouldUseParentId(...)) {
  ...
  if (it == parent_children_map_.end())
    return nullptr
  return it->second;;
}

return GetModelTypeChildSet(..);

[stanisc, 2015/07/10 04:58:50]

Done.

+}
+
+const OrderedChildSet* ParentChildIndex::GetModelTypeChildSet(
+    ModelType model_type) const {
+  return type_root_child_sets_[model_type];
+}
+
+OrderedChildSet* ParentChildIndex::GetOrCreateModelTypeChildSet(
+    ModelType model_type) {
+  if (!type_root_child_sets_[model_type])
+    type_root_child_sets_[model_type] = new OrderedChildSet();
+  return type_root_child_sets_[model_type];
 }
 
 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];
 }
 
 }  // namespace syncable
 }  // namespace syncer