Sync: Support directory entries with unset (implicit) parent ID

This is a part of a larger workitem on supporting datatypes that have implicit
permanent folders. This change prepares Sync directory to handle entries with
unset parent ID. That includes:
1) ParentChildIndex gets ability to resolve an entry without Parent ID to a
datatype root folder based on the entry type.
2) MutableEntity accepts a null Id and gets a constructor overload without
parent ID.
3) Similarly WriteNode accepts initialization with a null parent ID.
4) Added a few extra conditions and checks in the directory validation
routines to handle entries with unset parent ID.
5) Added a few new unit tests.

For now directory entries with implicit parent ID can be created only in test
code. All existing datatypes continue creating entries the old way, with parent ID.

BUG=438313

Review URL: https://codereview.chromium.org/843613002

Cr-Commit-Position: refs/heads/master@{#311090}

13 files changed, 390 insertions, 100 deletions

diff --git a/sync/internal_api/base_node.cc b/sync/internal_api/base_node.cc
index b43c6ca..4d6d56f 100644
--- a/sync/internal_api/base_node.cc
+++ b/sync/internal_api/base_node.cc
@@ -34,6 +34,8 @@ using syncable::SPECIFICS;
 // string.
 static int64 IdToMetahandle(syncable::BaseTransaction* trans,
                             const syncable::Id& id) {
+  if (id.IsNull())
+    return kInvalidId;
   syncable::Entry entry(trans, syncable::GET_BY_ID, id);
   if (!entry.good())
     return kInvalidId;
diff --git a/sync/internal_api/public/write_node.h b/sync/internal_api/public/write_node.h
index 2682d017..2d84aae 100644
--- a/sync/internal_api/public/write_node.h
+++ b/sync/internal_api/public/write_node.h
@@ -34,6 +34,7 @@ class Cryptographer;
 class WriteTransaction;
 
 namespace syncable {
+class Id;
 class Entry;
 class MutableEntry;
 }
@@ -84,6 +85,12 @@ class SYNC_EXPORT WriteNode : public BaseNode {
       const BaseNode& parent,
       const std::string& client_tag);
 
+  // InitUniqueByCreation overload for model types without hierarchy.
+  // The parent node isn't stored but is assumed to be the type root folder.
+  InitUniqueByCreationResult InitUniqueByCreation(
+      ModelType model_type,
+      const std::string& client_tag);
+
   // Looks up the type's root folder.  This is usually created by the sync
   // server during initial sync, though we do eventually wish to remove it from
   // the protocol and have the client "fake it" instead.
@@ -188,6 +195,11 @@ class SYNC_EXPORT WriteNode : public BaseNode {
 
   void* operator new(size_t size);  // Node is meant for stack use only.
 
+  InitUniqueByCreationResult InitUniqueByCreationImpl(
+      ModelType model_type,
+      const syncable::Id& parent_id,
+      const std::string& client_tag);
+
   // Helper to set the previous node.
   bool PutPredecessor(const BaseNode* predecessor) WARN_UNUSED_RESULT;
 
diff --git a/sync/internal_api/sync_backup_manager.cc b/sync/internal_api/sync_backup_manager.cc
index d626229..00615a8 100644
--- a/sync/internal_api/sync_backup_manager.cc
+++ b/sync/internal_api/sync_backup_manager.cc
@@ -83,7 +83,7 @@ void SyncBackupManager::NormalizeEntries() {
 
     if (!entry.GetId().ServerKnows())
       entry.PutId(syncable::Id::CreateFromServerId(entry.GetId().value()));
-    if (!entry.GetParentId().ServerKnows()) {
+    if (!entry.GetParentId().IsNull() && !entry.GetParentId().ServerKnows()) {
       entry.PutParentIdPropertyOnly(syncable::Id::CreateFromServerId(
           entry.GetParentId().value()));
     }
diff --git a/sync/internal_api/sync_manager_impl_unittest.cc b/sync/internal_api/sync_manager_impl_unittest.cc
index e6a1fa9..8e77e70 100644
--- a/sync/internal_api/sync_manager_impl_unittest.cc
+++ b/sync/internal_api/sync_manager_impl_unittest.cc
@@ -95,12 +95,26 @@ using syncable::kEncryptedString;
 
 namespace {
 
-// Makes a non-folder child of the root node.  Returns the id of the
+// Makes a child node under the type root folder.  Returns the id of the
 // newly-created node.
 int64 MakeNode(UserShare* share,
                ModelType model_type,
                const std::string& client_tag) {
   WriteTransaction trans(FROM_HERE, share);
+  WriteNode node(&trans);
+  WriteNode::InitUniqueByCreationResult result =
+      node.InitUniqueByCreation(model_type, client_tag);
+  EXPECT_EQ(WriteNode::INIT_SUCCESS, result);
+  node.SetIsFolder(false);
+  return node.GetId();
+}
+
+// Makes a non-folder child of the root node.  Returns the id of the
+// newly-created node.
+int64 MakeNodeWithRoot(UserShare* share,
+                       ModelType model_type,
+                       const std::string& client_tag) {
+  WriteTransaction trans(FROM_HERE, share);
   ReadNode root_node(&trans);
   root_node.InitByRootLookup();
   WriteNode node(&trans);
@@ -140,8 +154,7 @@ int64 MakeBookmarkWithParent(UserShare* share,
 // Creates the "synced" root node for a particular datatype. We use the syncable
 // methods here so that the syncer treats these nodes as if they were already
 // received from the server.
-int64 MakeServerNodeForType(UserShare* share,
-                            ModelType model_type) {
+int64 MakeTypeRoot(UserShare* share, ModelType model_type) {
   sync_pb::EntitySpecifics specifics;
   AddDefaultFieldValue(model_type, &specifics);
   syncable::WriteTransaction trans(
@@ -155,8 +168,6 @@ int64 MakeServerNodeForType(UserShare* share,
   entry.PutBaseVersion(1);
   entry.PutServerVersion(1);
   entry.PutIsUnappliedUpdate(false);
-  // TODO(stanisc): setting parent ID might be unnecessary once
-  // empty parent ID is supported.
   entry.PutParentId(syncable::Id::GetRoot());
   entry.PutServerParentId(syncable::Id::GetRoot());
   entry.PutServerIsDir(true);
@@ -306,24 +317,49 @@ TEST_F(SyncApiTest, BasicTagWrite) {
     ReadTransaction trans(FROM_HERE, user_share());
     ReadNode root_node(&trans);
     root_node.InitByRootLookup();
-    EXPECT_EQ(root_node.GetFirstChildId(), 0);
+    EXPECT_EQ(kInvalidId, root_node.GetFirstChildId());
   }
 
-  ignore_result(MakeNode(user_share(), BOOKMARKS, "testtag"));
+  ignore_result(MakeNodeWithRoot(user_share(), BOOKMARKS, "testtag"));
 
   {
     ReadTransaction trans(FROM_HERE, user_share());
     ReadNode node(&trans);
     EXPECT_EQ(BaseNode::INIT_OK,
               node.InitByClientTagLookup(BOOKMARKS, "testtag"));
+    EXPECT_NE(0, node.GetId());
 
     ReadNode root_node(&trans);
     root_node.InitByRootLookup();
-    EXPECT_NE(node.GetId(), 0);
     EXPECT_EQ(node.GetId(), root_node.GetFirstChildId());
   }
 }
 
+TEST_F(SyncApiTest, BasicTagWriteWithImplicitParent) {
+  int64 type_root = MakeTypeRoot(user_share(), PREFERENCES);
+
+  {
+    ReadTransaction trans(FROM_HERE, user_share());
+    ReadNode type_root_node(&trans);
+    EXPECT_EQ(BaseNode::INIT_OK, type_root_node.InitByIdLookup(type_root));
+    EXPECT_EQ(kInvalidId, type_root_node.GetFirstChildId());
+  }
+
+  ignore_result(MakeNode(user_share(), PREFERENCES, "testtag"));
+
+  {
+    ReadTransaction trans(FROM_HERE, user_share());
+    ReadNode node(&trans);
+    EXPECT_EQ(BaseNode::INIT_OK,
+              node.InitByClientTagLookup(PREFERENCES, "testtag"));
+    EXPECT_EQ(kInvalidId, node.GetParentId());
+
+    ReadNode type_root_node(&trans);
+    EXPECT_EQ(BaseNode::INIT_OK, type_root_node.InitByIdLookup(type_root));
+    EXPECT_EQ(node.GetId(), type_root_node.GetFirstChildId());
+  }
+}
+
 TEST_F(SyncApiTest, ModelTypesSiloed) {
   {
     WriteTransaction trans(FROM_HERE, user_share());
@@ -332,9 +368,9 @@ TEST_F(SyncApiTest, ModelTypesSiloed) {
     EXPECT_EQ(root_node.GetFirstChildId(), 0);
   }
 
-  ignore_result(MakeNode(user_share(), BOOKMARKS, "collideme"));
-  ignore_result(MakeNode(user_share(), PREFERENCES, "collideme"));
-  ignore_result(MakeNode(user_share(), AUTOFILL, "collideme"));
+  ignore_result(MakeNodeWithRoot(user_share(), BOOKMARKS, "collideme"));
+  ignore_result(MakeNodeWithRoot(user_share(), PREFERENCES, "collideme"));
+  ignore_result(MakeNodeWithRoot(user_share(), AUTOFILL, "collideme"));
 
   {
     ReadTransaction trans(FROM_HERE, user_share());
@@ -537,7 +573,7 @@ TEST_F(SyncApiTest, WriteEncryptedTitle) {
 }
 
 TEST_F(SyncApiTest, BaseNodeSetSpecifics) {
-  int64 child_id = MakeNode(user_share(), BOOKMARKS, "testtag");
+  int64 child_id = MakeNodeWithRoot(user_share(), BOOKMARKS, "testtag");
   WriteTransaction trans(FROM_HERE, user_share());
   WriteNode node(&trans);
   EXPECT_EQ(BaseNode::INIT_OK, node.InitByIdLookup(child_id));
@@ -553,7 +589,7 @@ TEST_F(SyncApiTest, BaseNodeSetSpecifics) {
 }
 
 TEST_F(SyncApiTest, BaseNodeSetSpecificsPreservesUnknownFields) {
-  int64 child_id = MakeNode(user_share(), BOOKMARKS, "testtag");
+  int64 child_id = MakeNodeWithRoot(user_share(), BOOKMARKS, "testtag");
   WriteTransaction trans(FROM_HERE, user_share());
   WriteNode node(&trans);
   EXPECT_EQ(BaseNode::INIT_OK, node.InitByIdLookup(child_id));
@@ -585,7 +621,7 @@ TEST_F(SyncApiTest, EmptyTags) {
 
 // Test counting nodes when the type's root node has no children.
 TEST_F(SyncApiTest, GetTotalNodeCountEmpty) {
-  int64 type_root = MakeServerNodeForType(user_share(), BOOKMARKS);
+  int64 type_root = MakeTypeRoot(user_share(), BOOKMARKS);
   {
     ReadTransaction trans(FROM_HERE, user_share());
     ReadNode type_root_node(&trans);
@@ -597,7 +633,7 @@ TEST_F(SyncApiTest, GetTotalNodeCountEmpty) {
 
 // Test counting nodes when there is one child beneath the type's root.
 TEST_F(SyncApiTest, GetTotalNodeCountOneChild) {
-  int64 type_root = MakeServerNodeForType(user_share(), BOOKMARKS);
+  int64 type_root = MakeTypeRoot(user_share(), BOOKMARKS);
   int64 parent = MakeFolderWithParent(user_share(), BOOKMARKS, type_root, NULL);
   {
     ReadTransaction trans(FROM_HERE, user_share());
@@ -615,7 +651,7 @@ TEST_F(SyncApiTest, GetTotalNodeCountOneChild) {
 // Test counting nodes when there are multiple children beneath the type root,
 // and one of those children has children of its own.
 TEST_F(SyncApiTest, GetTotalNodeCountMultipleChildren) {
-  int64 type_root = MakeServerNodeForType(user_share(), BOOKMARKS);
+  int64 type_root = MakeTypeRoot(user_share(), BOOKMARKS);
   int64 parent = MakeFolderWithParent(user_share(), BOOKMARKS, type_root, NULL);
   ignore_result(MakeFolderWithParent(user_share(), BOOKMARKS, type_root, NULL));
   int64 child1 = MakeFolderWithParent(user_share(), BOOKMARKS, parent, NULL);
@@ -834,8 +870,8 @@ class SyncManagerTest : public testing::Test,
     if (initialization_succeeded_) {
       for (ModelSafeRoutingInfo::iterator i = routing_info.begin();
            i != routing_info.end(); ++i) {
-        type_roots_[i->first] = MakeServerNodeForType(
-            sync_manager_.GetUserShare(), i->first);
+        type_roots_[i->first] =
+            MakeTypeRoot(sync_manager_.GetUserShare(), i->first);
       }
     }
 
@@ -1126,13 +1162,13 @@ TEST_F(SyncManagerTest, EncryptDataTypesWithData) {
   }
   // Next batch_size nodes are a different type and on their own.
   for (; i < 2*batch_size; ++i) {
-    MakeNode(sync_manager_.GetUserShare(), SESSIONS,
-             base::StringPrintf("%" PRIuS "", i));
+    MakeNodeWithRoot(sync_manager_.GetUserShare(), SESSIONS,
+                     base::StringPrintf("%" PRIuS "", i));
   }
   // Last batch_size nodes are a third type that will not need encryption.
   for (; i < 3*batch_size; ++i) {
-    MakeNode(sync_manager_.GetUserShare(), THEMES,
-             base::StringPrintf("%" PRIuS "", i));
+    MakeNodeWithRoot(sync_manager_.GetUserShare(), THEMES,
+                     base::StringPrintf("%" PRIuS "", i));
   }
 
   {
@@ -1615,12 +1651,10 @@ TEST_F(SyncManagerTest, EncryptBookmarksWithLegacyData) {
   std::string url2 = "http://www.bla.com";
 
   // Create a bookmark using the legacy format.
-  int64 node_id1 = MakeNode(sync_manager_.GetUserShare(),
-      BOOKMARKS,
-      "testtag");
-  int64 node_id2 = MakeNode(sync_manager_.GetUserShare(),
-      BOOKMARKS,
-      "testtag2");
+  int64 node_id1 =
+      MakeNodeWithRoot(sync_manager_.GetUserShare(), BOOKMARKS, "testtag");
+  int64 node_id2 =
+      MakeNodeWithRoot(sync_manager_.GetUserShare(), BOOKMARKS, "testtag2");
   {
     WriteTransaction trans(FROM_HERE, sync_manager_.GetUserShare());
     WriteNode node(&trans);
@@ -2690,7 +2724,7 @@ TEST_F(SyncManagerTest, PurgeUnappliedTypes) {
   AddDefaultFieldValue(BOOKMARKS, &bm_specifics);
   int pref1_meta = MakeServerNode(
       share, PREFERENCES, "pref1", "hash1", pref_specifics);
-  int64 pref2_meta = MakeNode(share, PREFERENCES, "pref2");
+  int64 pref2_meta = MakeNodeWithRoot(share, PREFERENCES, "pref2");
   int pref3_meta = MakeServerNode(
       share, PREFERENCES, "pref3", "hash3", pref_specifics);
   int pref4_meta = MakeServerNode(
diff --git a/sync/internal_api/write_node.cc b/sync/internal_api/write_node.cc
index 4aab598..cc445e4 100644
--- a/sync/internal_api/write_node.cc
+++ b/sync/internal_api/write_node.cc
@@ -337,6 +337,7 @@ bool WriteNode::InitBookmarkByCreation(const BaseNode& parent,
   }
 
   syncable::Id parent_id = parent.GetEntry()->GetId();
+  DCHECK(!parent_id.IsNull());
 
   // Start out with a dummy name.  We expect
   // the caller to set a meaningful name after creation.
@@ -352,8 +353,26 @@ bool WriteNode::InitBookmarkByCreation(const BaseNode& parent,
   // Entries are untitled folders by default.
   entry_->PutIsDir(true);
 
-  // Now set the predecessor, which sets IS_UNSYNCED as necessary.
-  return PutPredecessor(predecessor);
+  if (!PutPredecessor(predecessor)) {
+    return false;
+  }
+
+  // Mark this entry as unsynced, to wake up the syncer.
+  MarkForSyncing();
+  return true;
+}
+
+WriteNode::InitUniqueByCreationResult WriteNode::InitUniqueByCreation(
+    ModelType model_type,
+    const BaseNode& parent,
+    const std::string& tag) {
+  return InitUniqueByCreationImpl(model_type, parent.GetEntry()->GetId(), tag);
+}
+
+WriteNode::InitUniqueByCreationResult WriteNode::InitUniqueByCreation(
+    ModelType model_type,
+    const std::string& tag) {
+  return InitUniqueByCreationImpl(model_type, syncable::Id(), tag);
 }
 
 // Create a new node with default properties and a client defined unique tag,
@@ -362,9 +381,9 @@ bool WriteNode::InitBookmarkByCreation(const BaseNode& parent,
 // we will attempt to undelete the node.
 // TODO(chron): Code datatype into hash tag.
 // TODO(chron): Is model type ever lost?
-WriteNode::InitUniqueByCreationResult WriteNode::InitUniqueByCreation(
+WriteNode::InitUniqueByCreationResult WriteNode::InitUniqueByCreationImpl(
     ModelType model_type,
-    const BaseNode& parent,
+    const syncable::Id& parent_id,
     const std::string& tag) {
   // This DCHECK will only fail if init is called twice.
   DCHECK(!entry_);
@@ -375,8 +394,6 @@ WriteNode::InitUniqueByCreationResult WriteNode::InitUniqueByCreation(
 
   const std::string hash = syncable::GenerateSyncableHash(model_type, tag);
 
-  syncable::Id parent_id = parent.GetEntry()->GetId();
-
   // Start out with a dummy name.  We expect
   // the caller to set a meaningful name after creation.
   string dummy(kDefaultNameForNewNodes);
@@ -440,10 +457,13 @@ WriteNode::InitUniqueByCreationResult WriteNode::InitUniqueByCreation(
   // We don't support directory and tag combinations.
   entry_->PutIsDir(false);
 
-  // Now set the predecessor, which sets IS_UNSYNCED as necessary.
-  bool success = PutPredecessor(NULL);
-  if (!success)
-    return INIT_FAILED_SET_PREDECESSOR;
+  if (!parent_id.IsNull()) {
+    if (!PutPredecessor(NULL))
+      return INIT_FAILED_SET_PREDECESSOR;
+  }
+
+  // Mark this entry as unsynced, to wake up the syncer.
+  MarkForSyncing();
 
   return INIT_SUCCESS;
 }
@@ -457,6 +477,7 @@ bool WriteNode::SetPosition(const BaseNode& new_parent,
   }
 
   syncable::Id new_parent_id = new_parent.GetEntry()->GetId();
+  DCHECK(!new_parent_id.IsNull());
 
   // Filter out redundant changes if both the parent and the predecessor match.
   if (new_parent_id == entry_->GetParentId()) {
@@ -469,8 +490,13 @@ bool WriteNode::SetPosition(const BaseNode& new_parent,
 
   entry_->PutParentId(new_parent_id);
 
-  // Now set the predecessor, which sets IS_UNSYNCED as necessary.
-  return PutPredecessor(predecessor);
+  if (!PutPredecessor(predecessor)) {
+    return false;
+  }
+
+  // Mark this entry as unsynced, to wake up the syncer.
+  MarkForSyncing();
+  return true;
 }
 
 void WriteNode::SetAttachmentMetadata(
@@ -505,14 +531,10 @@ void WriteNode::Drop() {
 }
 
 bool WriteNode::PutPredecessor(const BaseNode* predecessor) {
+  DCHECK(!entry_->GetParentId().IsNull());
   syncable::Id predecessor_id = predecessor ?
       predecessor->GetEntry()->GetId() : syncable::Id();
-  if (!entry_->PutPredecessor(predecessor_id))
-    return false;
-  // Mark this entry as unsynced, to wake up the syncer.
-  MarkForSyncing();
-
-  return true;
+  return entry_->PutPredecessor(predecessor_id);
 }
 
 void WriteNode::MarkForSyncing() {
diff --git a/sync/syncable/directory.cc b/sync/syncable/directory.cc
index 22c3f46..68774df 100644
--- a/sync/syncable/directory.cc
+++ b/sync/syncable/directory.cc
@@ -1191,34 +1191,32 @@ bool Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
                       "Non unique name should not be empty.",
                       trans))
         return false;
-      int safety_count = handles.size() + 1;
-      // TODO(stanisc): handle items with Null parentid
-      while (!parentid.IsRoot()) {
-        Entry parent(trans, GET_BY_ID, parentid);
-        if (!SyncAssert(parent.good(), FROM_HERE,
-                        "Parent entry is not valid.",
-                        trans))
-          return false;
-        if (handles.end() == handles.find(parent.GetMetahandle()))
-            break; // Skip further checking if parent was unmodified.
-        if (!SyncAssert(parent.GetIsDir(), FROM_HERE,
-                        "Parent should be a directory",
-                        trans))
-          return false;
-        if (!SyncAssert(!parent.GetIsDel(), FROM_HERE,
-                        "Parent should not have been marked for deletion.",
-                        trans))
-          return false;
-        if (!SyncAssert(handles.end() != handles.find(parent.GetMetahandle()),
-                        FROM_HERE,
-                        "Parent should be in the index.",
-                        trans))
-          return false;
-        parentid = parent.GetParentId();
-        if (!SyncAssert(--safety_count > 0, FROM_HERE,
-                        "Count should be greater than zero.",
-                        trans))
-          return false;
+
+      if (!parentid.IsNull()) {
+        int safety_count = handles.size() + 1;
+        // TODO(stanisc): handle items with Null parentid
+        while (!parentid.IsRoot()) {
+          Entry parent(trans, GET_BY_ID, parentid);
+          if (!SyncAssert(parent.good(), FROM_HERE,
+                          "Parent entry is not valid.", trans))
+            return false;
+          if (handles.end() == handles.find(parent.GetMetahandle()))
+            break;  // Skip further checking if parent was unmodified.
+          if (!SyncAssert(parent.GetIsDir(), FROM_HERE,
+                          "Parent should be a directory", trans))
+            return false;
+          if (!SyncAssert(!parent.GetIsDel(), FROM_HERE,
+                          "Parent should not have been marked for deletion.",
+                          trans))
+            return false;
+          if (!SyncAssert(handles.end() != handles.find(parent.GetMetahandle()),
+                          FROM_HERE, "Parent should be in the index.", trans))
+            return false;
+          parentid = parent.GetParentId();
+          if (!SyncAssert(--safety_count > 0, FROM_HERE,
+                          "Count should be greater than zero.", trans))
+            return false;
+        }
       }
     }
     int64 base_version = e.GetBaseVersion();
diff --git a/sync/syncable/directory_unittest.cc b/sync/syncable/directory_unittest.cc
index b891dd7..162b93e 100644
--- a/sync/syncable/directory_unittest.cc
+++ b/sync/syncable/directory_unittest.cc
@@ -1766,6 +1766,70 @@ TEST_F(SyncableDirectoryTest, Directory_GetAttachmentIdsToUpload) {
   ASSERT_TRUE(id_set.empty());
 }
 
+// Verify that the directory accepts entries with unset parent ID.
+TEST_F(SyncableDirectoryTest, MutableEntry_ImplicitParentId) {
+  TestIdFactory id_factory;
+  const Id root_id = TestIdFactory::root();
+  const Id p_root_id = id_factory.NewServerId();
+  const Id a_root_id = id_factory.NewServerId();
+  const Id item1_id = id_factory.NewServerId();
+  const Id item2_id = id_factory.NewServerId();
+  const Id item3_id = id_factory.NewServerId();
+  // Create two type root folders that are necessary (for now)
+  // for creating items without explicitly set Parent ID
+  {
+    WriteTransaction trans(FROM_HERE, UNITTEST, dir().get());
+    MutableEntry p_root(&trans, CREATE, PREFERENCES, root_id, "P");
+    ASSERT_TRUE(p_root.good());
+    p_root.PutIsDir(true);
+    p_root.PutId(p_root_id);
+    p_root.PutBaseVersion(1);
+
+    MutableEntry a_root(&trans, CREATE, AUTOFILL, root_id, "A");
+    ASSERT_TRUE(a_root.good());
+    a_root.PutIsDir(true);
+    a_root.PutId(a_root_id);
+    a_root.PutBaseVersion(1);
+  }
+
+  // Create two entries with implicit parent nodes and one entry with explicit
+  // parent node.
+  {
+    WriteTransaction trans(FROM_HERE, UNITTEST, dir().get());
+    MutableEntry item1(&trans, CREATE, PREFERENCES, "P1");
+    item1.PutBaseVersion(1);
+    item1.PutId(item1_id);
+    MutableEntry item2(&trans, CREATE, AUTOFILL, "A1");
+    item2.PutBaseVersion(1);
+    item2.PutId(item2_id);
+    // Placing an AUTOFILL item under the root isn't expected,
+    // but let's test it to verify that explicit root overrides the implicit
+    // one and this entry doesn't end up under the "A" root.
+    MutableEntry item3(&trans, CREATE, AUTOFILL, root_id, "A2");
+    item3.PutBaseVersion(1);
+    item3.PutId(item3_id);
+  }
+
+  {
+    ReadTransaction trans(FROM_HERE, dir().get());
+    // Verify that item1 and item2 are good and have no ParentId.
+    Entry item1(&trans, GET_BY_ID, item1_id);
+    ASSERT_TRUE(item1.good());
+    ASSERT_TRUE(item1.GetParentId().IsNull());
+    Entry item2(&trans, GET_BY_ID, item2_id);
+    ASSERT_TRUE(item2.good());
+    ASSERT_TRUE(item2.GetParentId().IsNull());
+    // Verify that p_root and a_root have exactly one child each
+    // (subtract one to exclude roots themselves).
+    Entry p_root(&trans, GET_BY_ID, p_root_id);
+    ASSERT_EQ(item1_id, p_root.GetFirstChildId());
+    ASSERT_EQ(1, p_root.GetTotalNodeCount() - 1);
+    Entry a_root(&trans, GET_BY_ID, a_root_id);
+    ASSERT_EQ(item2_id, a_root.GetFirstChildId());
+    ASSERT_EQ(1, a_root.GetTotalNodeCount() - 1);
+  }
+}
+
 }  // namespace syncable
 
 }  // namespace syncer
diff --git a/sync/syncable/mutable_entry.cc b/sync/syncable/mutable_entry.cc
index 0cc06f9..89c8b05 100644
--- a/sync/syncable/mutable_entry.cc
+++ b/sync/syncable/mutable_entry.cc
@@ -29,7 +29,6 @@ void MutableEntry::Init(WriteTransaction* trans,
   kernel->put(ID, trans->directory_->NextId());
   kernel->put(META_HANDLE, trans->directory_->NextMetahandle());
   kernel->mark_dirty(&trans->directory_->kernel_->dirty_metahandles);
-  kernel->put(PARENT_ID, parent_id);
   kernel->put(NON_UNIQUE_NAME, name);
   const base::Time& now = base::Time::Now();
   kernel->put(CTIME, now);
@@ -37,6 +36,10 @@ void MutableEntry::Init(WriteTransaction* trans,
   // We match the database defaults here
   kernel->put(BASE_VERSION, CHANGES_VERSION);
 
+  if (!parent_id.IsNull()) {
+    kernel->put(PARENT_ID, parent_id);
+  }
+
   // Normally the SPECIFICS setting code is wrapped in logic to deal with
   // unknown fields and encryption.  Since all we want to do here is ensure that
   // GetModelType() returns a correct value from the very beginning, these
@@ -57,6 +60,20 @@ void MutableEntry::Init(WriteTransaction* trans,
 MutableEntry::MutableEntry(WriteTransaction* trans,
                            Create,
                            ModelType model_type,
+                           const string& name)
+    : ModelNeutralMutableEntry(trans), write_transaction_(trans) {
+  Init(trans, model_type, Id(), name);
+  // We need to have a valid position ready before we can index the item.
+  DCHECK_NE(BOOKMARKS, model_type);
+  DCHECK(!ShouldMaintainPosition());
+
+  bool result = trans->directory()->InsertEntry(trans, kernel_);
+  DCHECK(result);
+}
+
+MutableEntry::MutableEntry(WriteTransaction* trans,
+                           Create,
+                           ModelType model_type,
                            const Id& parent_id,
                            const string& name)
     : ModelNeutralMutableEntry(trans), write_transaction_(trans) {
diff --git a/sync/syncable/mutable_entry.h b/sync/syncable/mutable_entry.h
index 615fe80..6f010e6 100644
--- a/sync/syncable/mutable_entry.h
+++ b/sync/syncable/mutable_entry.h
@@ -30,8 +30,15 @@ class SYNC_EXPORT_PRIVATE MutableEntry : public ModelNeutralMutableEntry {
 
  public:
   MutableEntry(WriteTransaction* trans, CreateNewUpdateItem, const Id& id);
-  MutableEntry(WriteTransaction* trans, Create, ModelType model_type,
-               const Id& parent_id, const std::string& name);
+  MutableEntry(WriteTransaction* trans,
+               Create,
+               ModelType model_type,
+               const std::string& name);
+  MutableEntry(WriteTransaction* trans,
+               Create,
+               ModelType model_type,
+               const Id& parent_id,
+               const std::string& name);
   MutableEntry(WriteTransaction* trans, GetByHandle, int64);
   MutableEntry(WriteTransaction* trans, GetById, const Id&);
   MutableEntry(WriteTransaction* trans, GetByClientTag, const std::string& tag);
diff --git a/sync/syncable/parent_child_index.cc b/sync/syncable/parent_child_index.cc
index 71fb92e..f45bcfe 100644
--- a/sync/syncable/parent_child_index.cc
+++ b/sync/syncable/parent_child_index.cc
@@ -12,9 +12,8 @@
 namespace syncer {
 namespace syncable {
 
-bool ChildComparator::operator()(
-    const syncable::EntryKernel* a,
-    const syncable::EntryKernel* b) const {
+bool ChildComparator::operator()(const EntryKernel* a,
+                                 const EntryKernel* b) const {
   const UniquePosition& a_pos = a->ref(UNIQUE_POSITION);
   const UniquePosition& b_pos = b->ref(UNIQUE_POSITION);
 
@@ -56,7 +55,18 @@ bool ParentChildIndex::ShouldInclude(const EntryKernel* entry) {
 bool ParentChildIndex::Insert(EntryKernel* entry) {
   DCHECK(ShouldInclude(entry));
 
-  const syncable::Id& parent_id = entry->ref(PARENT_ID);
+  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 = NULL;
   ParentChildrenMap::iterator i = parent_children_map_.find(parent_id);
   if (i != parent_children_map_.end()) {
@@ -73,8 +83,18 @@ 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) {
-  ParentChildrenMap::iterator parent =
-      parent_children_map_.find(e->ref(PARENT_ID));
+  const Id& parent_id = GetParentId(e);
+  // Clear type root ID when removing a type root entry.
+  if (parent_id.IsRoot()) {
+    ModelType model_type = GetModelType(e);
+    // TODO(stanisc): the check is needed to work around some tests.
+    // See TODO above.
+    if (model_type_root_ids_[model_type] == e->ref(ID)) {
+      model_type_root_ids_[model_type] = Id();
+    }
+  }
+
+  ParentChildrenMap::iterator parent = parent_children_map_.find(parent_id);
   DCHECK(parent != parent_children_map_.end());
 
   OrderedChildSet* children = parent->second;
@@ -89,7 +109,7 @@ void ParentChildIndex::Remove(EntryKernel* e) {
 }
 
 bool ParentChildIndex::Contains(EntryKernel *e) const {
-  const syncable::Id& parent_id = e->ref(PARENT_ID);
+  const Id& parent_id = GetParentId(e);
   ParentChildrenMap::const_iterator parent =
       parent_children_map_.find(parent_id);
   if (parent == parent_children_map_.end()) {
@@ -111,5 +131,28 @@ const OrderedChildSet* ParentChildIndex::GetChildren(const syncable::Id& id) {
   return parent->second;
 }
 
+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));
+}
+
+ModelType ParentChildIndex::GetModelType(EntryKernel* e) {
+  // TODO(stanisc): is there a more effective way to find out model type?
+  ModelType model_type = e->GetModelType();
+  if (!syncer::IsRealDataType(model_type)) {
+    model_type = e->GetServerModelType();
+  }
+  return 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
diff --git a/sync/syncable/parent_child_index.h b/sync/syncable/parent_child_index.h
index fd0f2e8..5b51597 100644
--- a/sync/syncable/parent_child_index.h
+++ b/sync/syncable/parent_child_index.h
@@ -10,12 +10,13 @@
 
 #include "base/basictypes.h"
 #include "sync/base/sync_export.h"
+#include "sync/internal_api/public/base/model_type.h"
+#include "sync/syncable/syncable_id.h"
 
 namespace syncer {
 namespace syncable {
 
 struct EntryKernel;
-class Id;
 class ParentChildIndex;
 
 // A node ordering function.
@@ -51,12 +52,26 @@ class SYNC_EXPORT_PRIVATE ParentChildIndex {
   const OrderedChildSet* GetChildren(const Id& id);
 
  private:
-  typedef std::map<syncable::Id, OrderedChildSet*> ParentChildrenMap;
+  friend class ParentChildIndexTest;
+  typedef std::map<Id, OrderedChildSet*> ParentChildrenMap;
+
+  // Determines entry's model type.
+  static ModelType GetModelType(EntryKernel* e);
+
+  // Returns parent ID for the entry which is either its PARENT_ID value
+  // or derived from its model type.
+  const Id& GetParentId(EntryKernel* e) const;
+
+  // Returns previously cached model type root ID for the given |model_type|.
+  const Id& GetModelTypeRootId(ModelType model_type) const;
 
   // A map of parent IDs to children.
   // Parents with no children are not included in this map.
   ParentChildrenMap parent_children_map_;
 
+  // This array tracks model type roots IDs.
+  Id model_type_root_ids_[MODEL_TYPE_COUNT];
+
   DISALLOW_COPY_AND_ASSIGN(ParentChildIndex);
 };
 
diff --git a/sync/syncable/parent_child_index_unittest.cc b/sync/syncable/parent_child_index_unittest.cc
index 256e2dc..2519aab 100644
--- a/sync/syncable/parent_child_index_unittest.cc
+++ b/sync/syncable/parent_child_index_unittest.cc
@@ -19,6 +19,8 @@ namespace {
 
 static const std::string kCacheGuid = "8HhNIHlEOCGQbIAALr9QEg==";
 
+}  // namespace
+
 class ParentChildIndexTest : public testing::Test {
  public:
   void TearDown() override {
@@ -56,21 +58,30 @@ class ParentChildIndexTest : public testing::Test {
     return root;
   }
 
-  EntryKernel* MakeBookmarkRoot() {
+  EntryKernel* MakeTypeRoot(ModelType model_type, const syncable::Id& id) {
     // Mimics a server-created bookmark folder.
     EntryKernel* folder = new EntryKernel;
     folder->put(META_HANDLE, 1);
     folder->put(BASE_VERSION, 9);
     folder->put(SERVER_VERSION, 9);
     folder->put(IS_DIR, true);
-    folder->put(ID, GetBookmarkRootId());
+    folder->put(ID, id);
     folder->put(PARENT_ID, syncable::Id::GetRoot());
-    folder->put(UNIQUE_SERVER_TAG, "google_chrome_bookmarks");
+    folder->put(UNIQUE_SERVER_TAG, ModelTypeToRootTag(model_type));
+
+    // Ensure that GetModelType() returns a correct value.
+    sync_pb::EntitySpecifics specifics;
+    AddDefaultFieldValue(model_type, &specifics);
+    folder->put(SPECIFICS, specifics);
 
     owned_entry_kernels_.push_back(folder);
     return folder;
   }
 
+  EntryKernel* MakeBookmarkRoot() {
+    return MakeTypeRoot(BOOKMARKS, GetBookmarkRootId());
+  }
+
   EntryKernel* MakeBookmark(int n, int pos, bool is_dir) {
     // Mimics a regular bookmark or folder.
     EntryKernel* bm = new EntryKernel();
@@ -94,20 +105,44 @@ class ParentChildIndexTest : public testing::Test {
     return bm;
   }
 
-  EntryKernel* MakeUniqueClientItem(int n) {
+  EntryKernel* MakeUniqueClientItem(ModelType model_type,
+                                    int n,
+                                    const syncable::Id& parent_id) {
     EntryKernel* item = new EntryKernel();
     item->put(META_HANDLE, n);
     item->put(BASE_VERSION, 10);
     item->put(SERVER_VERSION, 10);
     item->put(IS_DIR, false);
     item->put(ID, GetClientUniqueId(n));
-    item->put(PARENT_ID, syncable::Id::GetRoot());
     item->put(UNIQUE_CLIENT_TAG, base::IntToString(n));
 
+    if (!parent_id.IsNull()) {
+      item->put(PARENT_ID, parent_id);
+    }
+
+    if (model_type != UNSPECIFIED) {
+      // Ensure that GetModelType() returns a correct value.
+      sync_pb::EntitySpecifics specifics;
+      AddDefaultFieldValue(model_type, &specifics);
+      item->put(SPECIFICS, specifics);
+    }
+
     owned_entry_kernels_.push_back(item);
     return item;
   }
 
+  EntryKernel* MakeUniqueClientItem(int n, const syncable::Id& parent_id) {
+    return MakeUniqueClientItem(UNSPECIFIED, n, parent_id);
+  }
+
+  EntryKernel* MakeUniqueClientItem(ModelType model_type, int n) {
+    return MakeUniqueClientItem(model_type, n, Id());
+  }
+
+  const syncable::Id& IndexKnownModelTypeRootId(ModelType model_type) const {
+    return index_.GetModelTypeRootId(model_type);
+  }
+
   ParentChildIndex index_;
 
  private:
@@ -122,6 +157,10 @@ TEST_F(ParentChildIndexTest, TestRootNode) {
 TEST_F(ParentChildIndexTest, TestBookmarkRootFolder) {
   EntryKernel* bm_folder = MakeBookmarkRoot();
   EXPECT_TRUE(ParentChildIndex::ShouldInclude(bm_folder));
+
+  EXPECT_EQ(Id(), IndexKnownModelTypeRootId(BOOKMARKS));
+  index_.Insert(bm_folder);
+  EXPECT_EQ(GetBookmarkRootId(), IndexKnownModelTypeRootId(BOOKMARKS));
 }
 
 // Tests iteration over a set of siblings.
@@ -289,8 +328,8 @@ TEST_F(ParentChildIndexTest, RemoveWithHierarchy) {
 // Test that involves two non-ordered items.
 TEST_F(ParentChildIndexTest, UnorderedChildren) {
   // Make two unique client tag items under the root node.
-  EntryKernel* u1 = MakeUniqueClientItem(1);
-  EntryKernel* u2 = MakeUniqueClientItem(2);
+  EntryKernel* u1 = MakeUniqueClientItem(1, syncable::Id::GetRoot());
+  EntryKernel* u2 = MakeUniqueClientItem(2, syncable::Id::GetRoot());
 
   EXPECT_FALSE(u1->ShouldMaintainPosition());
   EXPECT_FALSE(u2->ShouldMaintainPosition());
@@ -312,8 +351,7 @@ TEST_F(ParentChildIndexTest, OrderedAndUnorderedChildren) {
 
   EntryKernel* b1 = MakeBookmark(1, 1, false);
   EntryKernel* b2 = MakeBookmark(2, 2, false);
-  EntryKernel* u1 = MakeUniqueClientItem(1);
-  u1->put(PARENT_ID, GetBookmarkRootId());
+  EntryKernel* u1 = MakeUniqueClientItem(1, GetBookmarkRootId());
 
   index_.Insert(b1);
   index_.Insert(u1);
@@ -321,7 +359,7 @@ TEST_F(ParentChildIndexTest, OrderedAndUnorderedChildren) {
 
   const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId());
   ASSERT_TRUE(children);
-  EXPECT_EQ(children->size(), 3UL);
+  EXPECT_EQ(3UL, children->size());
 
   // Ensure that the non-positionable item is moved to the far right.
   OrderedChildSet::const_iterator it = children->begin();
@@ -334,7 +372,45 @@ TEST_F(ParentChildIndexTest, OrderedAndUnorderedChildren) {
   EXPECT_TRUE(it == children->end());
 }
 
-}  // namespace
+TEST_F(ParentChildIndexTest, NodesWithImplicitParentId) {
+  syncable::Id type_root_id = syncable::Id::CreateFromServerId("type_root");
+  EntryKernel* type_root = MakeTypeRoot(PREFERENCES, type_root_id);
+  index_.Insert(type_root);
+  EXPECT_EQ(type_root_id, IndexKnownModelTypeRootId(PREFERENCES));
+
+  // Create entries without parent ID
+  EntryKernel* p1 = MakeUniqueClientItem(PREFERENCES, 1);
+  EntryKernel* p2 = MakeUniqueClientItem(PREFERENCES, 2);
+
+  index_.Insert(p1);
+  index_.Insert(p2);
+
+  EXPECT_TRUE(index_.Contains(p1));
+  EXPECT_TRUE(index_.Contains(p2));
+
+  // Items should appear under the type root
+  const OrderedChildSet* children = index_.GetChildren(type_root_id);
+  ASSERT_TRUE(children);
+  EXPECT_EQ(2UL, children->size());
+
+  index_.Remove(p1);
+
+  EXPECT_FALSE(index_.Contains(p1));
+  EXPECT_TRUE(index_.Contains(p2));
+  children = index_.GetChildren(type_root_id);
+  ASSERT_TRUE(children);
+  EXPECT_EQ(1UL, children->size());
+
+  index_.Remove(p2);
+
+  EXPECT_FALSE(index_.Contains(p2));
+  children = index_.GetChildren(type_root_id);
+  ASSERT_EQ(nullptr, children);
+
+  index_.Remove(type_root);
+  EXPECT_EQ(Id(), IndexKnownModelTypeRootId(PREFERENCES));
+}
+
 }  // namespace syncable
 }  // namespace syncer
 
diff --git a/sync/syncable/syncable_id.h b/sync/syncable/syncable_id.h
index 5b40114..3691d77b 100644
--- a/sync/syncable/syncable_id.h
+++ b/sync/syncable/syncable_id.h
@@ -58,7 +58,7 @@ class SYNC_EXPORT Id {
     return "r" == s_;
   }
   inline bool ServerKnows() const {
-    return s_[0] == 's' || s_ == "r";
+    return !IsNull() && (s_[0] == 's' || s_ == "r");
   }
 
   inline bool IsNull() const { return s_.empty(); }