Sync: ChangeReorderBuffer::Traversal should handle nodes with unset Parent ID

sync/internal_api/change_reorder_buffer.cc

 // Copyright 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/internal_api/change_reorder_buffer.h"
 
 #include <limits>
 #include <queue>
 #include <set>
 #include <utility>  // for pair<>
@@ skipping 41 matching lines @@
       CHECK(node.good());
       if (node.GetId().IsRoot()) {
         // If we've hit the root, and the root isn't already in the tree
         // (it would have to be |top_| if it were), start a new expansion
         // upwards from |top_| to unite the original traversal with the
         // path we just added that goes from |child_handle| to the root.
         node_to_include = top_;
         top_ = node.GetMetahandle();
       } else {
         // Otherwise, get the parent ID so that we can add a ParentChildLink.
-        syncable::Entry parent(trans, syncable::GET_BY_ID,
-                               node.GetParentId());
+
+        // Treat nodes with unset parent ID as if they were linked to the root.
+        // That is a valid way to traverse the tree because all hierarchical
+        // datatypes must have a valid parent ID and the ones with unset parent
+        // ID have flat hierarchy where the order doesn't matter.
+        const syncable::Id& parent_id = !node.GetParentId().IsNull()
+                                            ? node.GetParentId()
+                                            : syncable::Id::GetRoot();
+        syncable::Entry parent(trans, syncable::GET_BY_ID, parent_id);
         CHECK(parent.good());
         node_parent = parent.GetMetahandle();
 
         ParentChildLink link(node_parent, node_to_include);
 
         // If the link exists in the LinkSet |links_|, we don't need to search
         // any higher; we are done.
         if (links_.find(link) != links_.end())
           return;
 
@@ skipping 134 matching lines @@
       CHECK(j->first == next);
       to_visit.push(j->second);
     }
   }
 
   *changes = ImmutableChangeRecordList(&changelist);
   return true;
 }
 
 }  // namespace syncer