sync/syncable/parent_child_index_unittest.cc

   1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "sync/syncable/parent_child_index.h"
   6
   7 #include <list>
   8
   9 #include "base/stl_util.h"
  10 #include "base/strings/string_number_conversions.h"
  11 #include "sync/syncable/entry_kernel.h"
  12 #include "sync/syncable/syncable_util.h"
  13 #include "testing/gtest/include/gtest/gtest.h"
  14
  15 namespace syncer {
  16 namespace syncable {
  17
  18 namespace {
  19
  20 static const std::string kCacheGuid = "8HhNIHlEOCGQbIAALr9QEg==";
  21
  22 }  // namespace
  23
  24 class ParentChildIndexTest : public testing::Test {
  25  public:
  26   void TearDown() override {
  27     // To make memory management easier, we take ownership of all EntryKernels
  28     // returned by our factory methods and delete them here.
  29     STLDeleteElements(&owned_entry_kernels_);
  30   }
  31
  32   // Unfortunately, we can't use the regular Entry factory methods, because the
  33   // ParentChildIndex deals in EntryKernels.
  34
  35   static syncable::Id GetBookmarkRootId() {
  36     return syncable::Id::CreateFromServerId("bookmark_folder");
  37   }
  38
  39   static syncable::Id GetBookmarkId(int n) {
  40     return syncable::Id::CreateFromServerId("b" + base::IntToString(n));
  41   }
  42
  43   static syncable::Id GetClientUniqueId(int n) {
  44     return syncable::Id::CreateFromServerId("c" + base::IntToString(n));
  45   }
  46
  47   EntryKernel* MakeRoot() {
  48     // Mimics the root node.
  49     EntryKernel* root = new EntryKernel();
  50     root->put(META_HANDLE, 1);
  51     root->put(BASE_VERSION, -1);
  52     root->put(SERVER_VERSION, 0);
  53     root->put(IS_DIR, true);
  54     root->put(ID, syncable::Id::GetRoot());
  55     root->put(PARENT_ID, syncable::Id::GetRoot());
  56
  57     owned_entry_kernels_.push_back(root);
  58     return root;
  59   }
  60
  61   EntryKernel* MakeTypeRoot(ModelType model_type, const syncable::Id& id) {
  62     // Mimics a server-created bookmark folder.
  63     EntryKernel* folder = new EntryKernel;
  64     folder->put(META_HANDLE, 1);
  65     folder->put(BASE_VERSION, 9);
  66     folder->put(SERVER_VERSION, 9);
  67     folder->put(IS_DIR, true);
  68     folder->put(ID, id);
  69     folder->put(PARENT_ID, syncable::Id::GetRoot());
  70     folder->put(UNIQUE_SERVER_TAG, ModelTypeToRootTag(model_type));
  71
  72     // Ensure that GetModelType() returns a correct value.
  73     sync_pb::EntitySpecifics specifics;
  74     AddDefaultFieldValue(model_type, &specifics);
  75     folder->put(SPECIFICS, specifics);
  76
  77     owned_entry_kernels_.push_back(folder);
  78     return folder;
  79   }
  80
  81   EntryKernel* MakeBookmarkRoot() {
  82     return MakeTypeRoot(BOOKMARKS, GetBookmarkRootId());
  83   }
  84
  85   EntryKernel* MakeBookmark(int n, int pos, bool is_dir) {
  86     // Mimics a regular bookmark or folder.
  87     EntryKernel* bm = new EntryKernel();
  88     bm->put(META_HANDLE, n);
  89     bm->put(BASE_VERSION, 10);
  90     bm->put(SERVER_VERSION, 10);
  91     bm->put(IS_DIR, is_dir);
  92     bm->put(ID, GetBookmarkId(n));
  93     bm->put(PARENT_ID, GetBookmarkRootId());
  94
  95     bm->put(UNIQUE_BOOKMARK_TAG,
  96             syncable::GenerateSyncableBookmarkHash(kCacheGuid,
  97                                                    bm->ref(ID).GetServerId()));
  98
  99     UniquePosition unique_pos =
 100         UniquePosition::FromInt64(pos, bm->ref(UNIQUE_BOOKMARK_TAG));
 101     bm->put(UNIQUE_POSITION, unique_pos);
 102     bm->put(SERVER_UNIQUE_POSITION, unique_pos);
 103
 104     owned_entry_kernels_.push_back(bm);
 105     return bm;
 106   }
 107
 108   EntryKernel* MakeUniqueClientItem(ModelType model_type,
 109                                     int n,
 110                                     const syncable::Id& parent_id) {
 111     EntryKernel* item = new EntryKernel();
 112     item->put(META_HANDLE, n);
 113     item->put(BASE_VERSION, 10);
 114     item->put(SERVER_VERSION, 10);
 115     item->put(IS_DIR, false);
 116     item->put(ID, GetClientUniqueId(n));
 117     item->put(UNIQUE_CLIENT_TAG, base::IntToString(n));
 118
 119     if (!parent_id.IsNull()) {
 120       item->put(PARENT_ID, parent_id);
 121     }
 122
 123     if (model_type != UNSPECIFIED) {
 124       // Ensure that GetModelType() returns a correct value.
 125       sync_pb::EntitySpecifics specifics;
 126       AddDefaultFieldValue(model_type, &specifics);
 127       item->put(SPECIFICS, specifics);
 128     }
 129
 130     owned_entry_kernels_.push_back(item);
 131     return item;
 132   }
 133
 134   EntryKernel* MakeUniqueClientItem(int n, const syncable::Id& parent_id) {
 135     return MakeUniqueClientItem(UNSPECIFIED, n, parent_id);
 136   }
 137
 138   EntryKernel* MakeUniqueClientItem(ModelType model_type, int n) {
 139     return MakeUniqueClientItem(model_type, n, Id());
 140   }
 141
 142   const syncable::Id& IndexKnownModelTypeRootId(ModelType model_type) const {
 143     return index_.GetModelTypeRootId(model_type);
 144   }
 145
 146   ParentChildIndex index_;
 147
 148  private:
 149   std::list<EntryKernel*> owned_entry_kernels_;
 150 };
 151
 152 TEST_F(ParentChildIndexTest, TestRootNode) {
 153   EntryKernel* root = MakeRoot();
 154   EXPECT_FALSE(ParentChildIndex::ShouldInclude(root));
 155 }
 156
 157 TEST_F(ParentChildIndexTest, TestBookmarkRootFolder) {
 158   EntryKernel* bm_folder = MakeBookmarkRoot();
 159   EXPECT_TRUE(ParentChildIndex::ShouldInclude(bm_folder));
 160
 161   index_.Insert(bm_folder);
 162   // Since BOOKMARKS is a hierarchical type, its type root folder shouldn't be
 163   // tracked by ParentChildIndex.
 164   EXPECT_EQ(Id(), IndexKnownModelTypeRootId(BOOKMARKS));
 165 }
 166
 167 // Tests iteration over a set of siblings.
 168 TEST_F(ParentChildIndexTest, ChildInsertionAndIteration) {
 169   EntryKernel* bm_folder = MakeBookmarkRoot();
 170   index_.Insert(bm_folder);
 171
 172   // Make some folder and non-folder entries.
 173   EntryKernel* b1 = MakeBookmark(1, 1, false);
 174   EntryKernel* b2 = MakeBookmark(2, 2, false);
 175   EntryKernel* b3 = MakeBookmark(3, 3, true);
 176   EntryKernel* b4 = MakeBookmark(4, 4, false);
 177
 178   // Insert them out-of-order to test different cases.
 179   index_.Insert(b3); // Only child.
 180   index_.Insert(b4); // Right-most child.
 181   index_.Insert(b1); // Left-most child.
 182   index_.Insert(b2); // Between existing items.
 183
 184   // Double-check they've been added.
 185   EXPECT_TRUE(index_.Contains(b1));
 186   EXPECT_TRUE(index_.Contains(b2));
 187   EXPECT_TRUE(index_.Contains(b3));
 188   EXPECT_TRUE(index_.Contains(b4));
 189
 190   // Check the ordering.
 191   const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId());
 192   ASSERT_TRUE(children);
 193   ASSERT_EQ(children->size(), 4UL);
 194   OrderedChildSet::const_iterator it = children->begin();
 195   EXPECT_EQ(*it, b1);
 196   it++;
 197   EXPECT_EQ(*it, b2);
 198   it++;
 199   EXPECT_EQ(*it, b3);
 200   it++;
 201   EXPECT_EQ(*it, b4);
 202   it++;
 203   EXPECT_TRUE(it == children->end());
 204 }
 205
 206 // Tests iteration when hierarchy is involved.
 207 TEST_F(ParentChildIndexTest, ChildInsertionAndIterationWithHierarchy) {
 208   EntryKernel* bm_folder = MakeBookmarkRoot();
 209   index_.Insert(bm_folder);
 210
 211   // Just below the root, we have folders f1 and f2.
 212   EntryKernel* f1 = MakeBookmark(1, 1, false);
 213   EntryKernel* f2 = MakeBookmark(2, 2, false);
 214   EntryKernel* f3 = MakeBookmark(3, 3, false);
 215
 216   // Under folder f1, we have two bookmarks.
 217   EntryKernel* f1_b1 = MakeBookmark(101, 1, false);
 218   f1_b1->put(PARENT_ID, GetBookmarkId(1));
 219   EntryKernel* f1_b2 = MakeBookmark(102, 2, false);
 220   f1_b2->put(PARENT_ID, GetBookmarkId(1));
 221
 222   // Under folder f2, there is one bookmark.
 223   EntryKernel* f2_b1 = MakeBookmark(201, 1, false);
 224   f2_b1->put(PARENT_ID, GetBookmarkId(2));
 225
 226   // Under folder f3, there is nothing.
 227
 228   // Insert in a strange order, because we can.
 229   index_.Insert(f1_b2);
 230   index_.Insert(f2);
 231   index_.Insert(f2_b1);
 232   index_.Insert(f1);
 233   index_.Insert(f1_b1);
 234   index_.Insert(f3);
 235
 236   OrderedChildSet::const_iterator it;
 237
 238   // Iterate over children of the bookmark root.
 239   const OrderedChildSet* top_children = index_.GetChildren(GetBookmarkRootId());
 240   ASSERT_TRUE(top_children);
 241   ASSERT_EQ(top_children->size(), 3UL);
 242   it = top_children->begin();
 243   EXPECT_EQ(*it, f1);
 244   it++;
 245   EXPECT_EQ(*it, f2);
 246   it++;
 247   EXPECT_EQ(*it, f3);
 248   it++;
 249   EXPECT_TRUE(it == top_children->end());
 250
 251   // Iterate over children of the first folder.
 252   const OrderedChildSet* f1_children = index_.GetChildren(GetBookmarkId(1));
 253   ASSERT_TRUE(f1_children);
 254   ASSERT_EQ(f1_children->size(), 2UL);
 255   it = f1_children->begin();
 256   EXPECT_EQ(*it, f1_b1);
 257   it++;
 258   EXPECT_EQ(*it, f1_b2);
 259   it++;
 260   EXPECT_TRUE(it == f1_children->end());
 261
 262   // Iterate over children of the second folder.
 263   const OrderedChildSet* f2_children = index_.GetChildren(GetBookmarkId(2));
 264   ASSERT_TRUE(f2_children);
 265   ASSERT_EQ(f2_children->size(), 1UL);
 266   it = f2_children->begin();
 267   EXPECT_EQ(*it, f2_b1);
 268   it++;
 269   EXPECT_TRUE(it == f2_children->end());
 270
 271   // Check for children of the third folder.
 272   const OrderedChildSet* f3_children = index_.GetChildren(GetBookmarkId(3));
 273   EXPECT_FALSE(f3_children);
 274 }
 275
 276 // Tests removing items.
 277 TEST_F(ParentChildIndexTest, RemoveWithHierarchy) {
 278   EntryKernel* bm_folder = MakeBookmarkRoot();
 279   index_.Insert(bm_folder);
 280
 281   // Just below the root, we have folders f1 and f2.
 282   EntryKernel* f1 = MakeBookmark(1, 1, false);
 283   EntryKernel* f2 = MakeBookmark(2, 2, false);
 284   EntryKernel* f3 = MakeBookmark(3, 3, false);
 285
 286   // Under folder f1, we have two bookmarks.
 287   EntryKernel* f1_b1 = MakeBookmark(101, 1, false);
 288   f1_b1->put(PARENT_ID, GetBookmarkId(1));
 289   EntryKernel* f1_b2 = MakeBookmark(102, 2, false);
 290   f1_b2->put(PARENT_ID, GetBookmarkId(1));
 291
 292   // Under folder f2, there is one bookmark.
 293   EntryKernel* f2_b1 = MakeBookmark(201, 1, false);
 294   f2_b1->put(PARENT_ID, GetBookmarkId(2));
 295
 296   // Under folder f3, there is nothing.
 297
 298   // Insert in any order.
 299   index_.Insert(f2_b1);
 300   index_.Insert(f3);
 301   index_.Insert(f1_b2);
 302   index_.Insert(f1);
 303   index_.Insert(f2);
 304   index_.Insert(f1_b1);
 305
 306   // Check that all are in the index.
 307   EXPECT_TRUE(index_.Contains(f1));
 308   EXPECT_TRUE(index_.Contains(f2));
 309   EXPECT_TRUE(index_.Contains(f3));
 310   EXPECT_TRUE(index_.Contains(f1_b1));
 311   EXPECT_TRUE(index_.Contains(f1_b2));
 312   EXPECT_TRUE(index_.Contains(f2_b1));
 313
 314   // Remove them all in any order.
 315   index_.Remove(f3);
 316   EXPECT_FALSE(index_.Contains(f3));
 317   index_.Remove(f1_b2);
 318   EXPECT_FALSE(index_.Contains(f1_b2));
 319   index_.Remove(f2_b1);
 320   EXPECT_FALSE(index_.Contains(f2_b1));
 321   index_.Remove(f1);
 322   EXPECT_FALSE(index_.Contains(f1));
 323   index_.Remove(f2);
 324   EXPECT_FALSE(index_.Contains(f2));
 325   index_.Remove(f1_b1);
 326   EXPECT_FALSE(index_.Contains(f1_b1));
 327 }
 328
 329 // Test that involves two non-ordered items.
 330 TEST_F(ParentChildIndexTest, UnorderedChildren) {
 331   // Make two unique client tag items under the root node.
 332   EntryKernel* u1 = MakeUniqueClientItem(1, syncable::Id::GetRoot());
 333   EntryKernel* u2 = MakeUniqueClientItem(2, syncable::Id::GetRoot());
 334
 335   EXPECT_FALSE(u1->ShouldMaintainPosition());
 336   EXPECT_FALSE(u2->ShouldMaintainPosition());
 337
 338   index_.Insert(u1);
 339   index_.Insert(u2);
 340
 341   const OrderedChildSet* children = index_.GetChildren(syncable::Id::GetRoot());
 342   EXPECT_EQ(children->count(u1), 1UL);
 343   EXPECT_EQ(children->count(u2), 1UL);
 344   EXPECT_EQ(children->size(), 2UL);
 345 }
 346
 347 // Test ordered and non-ordered entries under the same parent.
 348 // TODO(rlarocque): We should not need to support this.
 349 TEST_F(ParentChildIndexTest, OrderedAndUnorderedChildren) {
 350   EntryKernel* bm_folder = MakeBookmarkRoot();
 351   index_.Insert(bm_folder);
 352
 353   EntryKernel* b1 = MakeBookmark(1, 1, false);
 354   EntryKernel* b2 = MakeBookmark(2, 2, false);
 355   EntryKernel* u1 = MakeUniqueClientItem(1, GetBookmarkRootId());
 356
 357   index_.Insert(b1);
 358   index_.Insert(u1);
 359   index_.Insert(b2);
 360
 361   const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId());
 362   ASSERT_TRUE(children);
 363   EXPECT_EQ(3UL, children->size());
 364
 365   // Ensure that the non-positionable item is moved to the far right.
 366   OrderedChildSet::const_iterator it = children->begin();
 367   EXPECT_EQ(*it, b1);
 368   it++;
 369   EXPECT_EQ(*it, b2);
 370   it++;
 371   EXPECT_EQ(*it, u1);
 372   it++;
 373   EXPECT_TRUE(it == children->end());
 374 }
 375
 376 TEST_F(ParentChildIndexTest, NodesWithImplicitParentId) {
 377   syncable::Id type_root_id = syncable::Id::CreateFromServerId("type_root");
 378   EntryKernel* type_root = MakeTypeRoot(PREFERENCES, type_root_id);
 379   index_.Insert(type_root);
 380   EXPECT_EQ(type_root_id, IndexKnownModelTypeRootId(PREFERENCES));
 381
 382   // Create entries without parent ID
 383   EntryKernel* p1 = MakeUniqueClientItem(PREFERENCES, 1);
 384   EntryKernel* p2 = MakeUniqueClientItem(PREFERENCES, 2);
 385
 386   index_.Insert(p1);
 387   index_.Insert(p2);
 388
 389   EXPECT_TRUE(index_.Contains(p1));
 390   EXPECT_TRUE(index_.Contains(p2));
 391
 392   // Items should appear under the type root
 393   const OrderedChildSet* children = index_.GetChildren(type_root);
 394   ASSERT_TRUE(children);
 395   EXPECT_EQ(2UL, children->size());
 396
 397   EXPECT_EQ(2UL, index_.GetSiblings(p1)->size());
 398   EXPECT_EQ(2UL, index_.GetSiblings(p2)->size());
 399
 400   index_.Remove(p1);
 401
 402   EXPECT_FALSE(index_.Contains(p1));
 403   EXPECT_TRUE(index_.Contains(p2));
 404   children = index_.GetChildren(type_root_id);
 405   ASSERT_TRUE(children);
 406   EXPECT_EQ(1UL, children->size());
 407
 408   index_.Remove(p2);
 409
 410   EXPECT_FALSE(index_.Contains(p2));
 411   children = index_.GetChildren(type_root);
 412   ASSERT_EQ(nullptr, children);
 413 }
 414
 415 // Test that the removal isn't sensitive to the order (PurgeEntriesWithTypeIn
 416 // removes items in arbitrary order).
 417 TEST_F(ParentChildIndexTest, RemoveOutOfOrder) {
 418   // Insert a type root and two items (with implicit parent ID).
 419   syncable::Id type_root_id = syncable::Id::CreateFromServerId("type_root");
 420   EntryKernel* type_root = MakeTypeRoot(PREFERENCES, type_root_id);
 421   index_.Insert(type_root);
 422   EntryKernel* p1 = MakeUniqueClientItem(PREFERENCES, 1);
 423   EntryKernel* p2 = MakeUniqueClientItem(PREFERENCES, 2);
 424   index_.Insert(p1);
 425   index_.Insert(p2);
 426
 427   // Two items expected under the type root.
 428   const OrderedChildSet* children = index_.GetChildren(type_root);
 429   ASSERT_TRUE(children);
 430   EXPECT_EQ(2UL, children->size());
 431
 432   // Remove all 3 items in arbitrary order.
 433   index_.Remove(p2);
 434   index_.Remove(type_root);
 435   index_.Remove(p1);
 436
 437   EXPECT_EQ(nullptr, index_.GetChildren(type_root));
 438
 439   // Add a new root and another two items again.
 440   type_root = MakeTypeRoot(PREFERENCES, type_root_id);
 441   index_.Insert(type_root);
 442
 443   index_.Insert(MakeUniqueClientItem(PREFERENCES, 3));
 444   index_.Insert(MakeUniqueClientItem(PREFERENCES, 4));
 445
 446   children = index_.GetChildren(type_root);
 447   ASSERT_TRUE(children);
 448   // Should have 2 items. If the out of order removal cleared the implicit
 449   // parent folder ID prematurely, the collection would have 3 items including
 450   // p1.
 451   EXPECT_EQ(2UL, children->size());
 452 }
 453
 454 // Test that the insert isn't sensitive to the order (Loading entries from
 455 // Sync DB is done in arbitrary order).
 456 TEST_F(ParentChildIndexTest, InsertOutOfOrder) {
 457   // Insert two Preferences entries with implicit parent first
 458   index_.Insert(MakeUniqueClientItem(PREFERENCES, 1));
 459   index_.Insert(MakeUniqueClientItem(PREFERENCES, 2));
 460
 461   // Then insert the Preferences type root
 462   syncable::Id type_root_id = syncable::Id::CreateFromServerId("type_root");
 463   index_.Insert(MakeTypeRoot(PREFERENCES, type_root_id));
 464
 465   // The index should still be able to associate Preferences entries
 466   // with the root.
 467   const OrderedChildSet* children = index_.GetChildren(type_root_id);
 468   ASSERT_TRUE(children);
 469   EXPECT_EQ(2UL, children->size());
 470 }
 471
 472 }  // namespace syncable
 473 }  // namespace syncer
 474