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   EXPECT_EQ(Id(), IndexKnownModelTypeRootId(BOOKMARKS));
 162   index_.Insert(bm_folder);
 163   EXPECT_EQ(GetBookmarkRootId(), IndexKnownModelTypeRootId(BOOKMARKS));
 164 }
 165
 166 // Tests iteration over a set of siblings.
 167 TEST_F(ParentChildIndexTest, ChildInsertionAndIteration) {
 168   EntryKernel* bm_folder = MakeBookmarkRoot();
 169   index_.Insert(bm_folder);
 170
 171   // Make some folder and non-folder entries.
 172   EntryKernel* b1 = MakeBookmark(1, 1, false);
 173   EntryKernel* b2 = MakeBookmark(2, 2, false);
 174   EntryKernel* b3 = MakeBookmark(3, 3, true);
 175   EntryKernel* b4 = MakeBookmark(4, 4, false);
 176
 177   // Insert them out-of-order to test different cases.
 178   index_.Insert(b3); // Only child.
 179   index_.Insert(b4); // Right-most child.
 180   index_.Insert(b1); // Left-most child.
 181   index_.Insert(b2); // Between existing items.
 182
 183   // Double-check they've been added.
 184   EXPECT_TRUE(index_.Contains(b1));
 185   EXPECT_TRUE(index_.Contains(b2));
 186   EXPECT_TRUE(index_.Contains(b3));
 187   EXPECT_TRUE(index_.Contains(b4));
 188
 189   // Check the ordering.
 190   const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId());
 191   ASSERT_TRUE(children);
 192   ASSERT_EQ(children->size(), 4UL);
 193   OrderedChildSet::const_iterator it = children->begin();
 194   EXPECT_EQ(*it, b1);
 195   it++;
 196   EXPECT_EQ(*it, b2);
 197   it++;
 198   EXPECT_EQ(*it, b3);
 199   it++;
 200   EXPECT_EQ(*it, b4);
 201   it++;
 202   EXPECT_TRUE(it == children->end());
 203 }
 204
 205 // Tests iteration when hierarchy is involved.
 206 TEST_F(ParentChildIndexTest, ChildInsertionAndIterationWithHierarchy) {
 207   EntryKernel* bm_folder = MakeBookmarkRoot();
 208   index_.Insert(bm_folder);
 209
 210   // Just below the root, we have folders f1 and f2.
 211   EntryKernel* f1 = MakeBookmark(1, 1, false);
 212   EntryKernel* f2 = MakeBookmark(2, 2, false);
 213   EntryKernel* f3 = MakeBookmark(3, 3, false);
 214
 215   // Under folder f1, we have two bookmarks.
 216   EntryKernel* f1_b1 = MakeBookmark(101, 1, false);
 217   f1_b1->put(PARENT_ID, GetBookmarkId(1));
 218   EntryKernel* f1_b2 = MakeBookmark(102, 2, false);
 219   f1_b2->put(PARENT_ID, GetBookmarkId(1));
 220
 221   // Under folder f2, there is one bookmark.
 222   EntryKernel* f2_b1 = MakeBookmark(201, 1, false);
 223   f2_b1->put(PARENT_ID, GetBookmarkId(2));
 224
 225   // Under folder f3, there is nothing.
 226
 227   // Insert in a strange order, because we can.
 228   index_.Insert(f1_b2);
 229   index_.Insert(f2);
 230   index_.Insert(f2_b1);
 231   index_.Insert(f1);
 232   index_.Insert(f1_b1);
 233   index_.Insert(f3);
 234
 235   OrderedChildSet::const_iterator it;
 236
 237   // Iterate over children of the bookmark root.
 238   const OrderedChildSet* top_children = index_.GetChildren(GetBookmarkRootId());
 239   ASSERT_TRUE(top_children);
 240   ASSERT_EQ(top_children->size(), 3UL);
 241   it = top_children->begin();
 242   EXPECT_EQ(*it, f1);
 243   it++;
 244   EXPECT_EQ(*it, f2);
 245   it++;
 246   EXPECT_EQ(*it, f3);
 247   it++;
 248   EXPECT_TRUE(it == top_children->end());
 249
 250   // Iterate over children of the first folder.
 251   const OrderedChildSet* f1_children = index_.GetChildren(GetBookmarkId(1));
 252   ASSERT_TRUE(f1_children);
 253   ASSERT_EQ(f1_children->size(), 2UL);
 254   it = f1_children->begin();
 255   EXPECT_EQ(*it, f1_b1);
 256   it++;
 257   EXPECT_EQ(*it, f1_b2);
 258   it++;
 259   EXPECT_TRUE(it == f1_children->end());
 260
 261   // Iterate over children of the second folder.
 262   const OrderedChildSet* f2_children = index_.GetChildren(GetBookmarkId(2));
 263   ASSERT_TRUE(f2_children);
 264   ASSERT_EQ(f2_children->size(), 1UL);
 265   it = f2_children->begin();
 266   EXPECT_EQ(*it, f2_b1);
 267   it++;
 268   EXPECT_TRUE(it == f2_children->end());
 269
 270   // Check for children of the third folder.
 271   const OrderedChildSet* f3_children = index_.GetChildren(GetBookmarkId(3));
 272   EXPECT_FALSE(f3_children);
 273 }
 274
 275 // Tests removing items.
 276 TEST_F(ParentChildIndexTest, RemoveWithHierarchy) {
 277   EntryKernel* bm_folder = MakeBookmarkRoot();
 278   index_.Insert(bm_folder);
 279
 280   // Just below the root, we have folders f1 and f2.
 281   EntryKernel* f1 = MakeBookmark(1, 1, false);
 282   EntryKernel* f2 = MakeBookmark(2, 2, false);
 283   EntryKernel* f3 = MakeBookmark(3, 3, false);
 284
 285   // Under folder f1, we have two bookmarks.
 286   EntryKernel* f1_b1 = MakeBookmark(101, 1, false);
 287   f1_b1->put(PARENT_ID, GetBookmarkId(1));
 288   EntryKernel* f1_b2 = MakeBookmark(102, 2, false);
 289   f1_b2->put(PARENT_ID, GetBookmarkId(1));
 290
 291   // Under folder f2, there is one bookmark.
 292   EntryKernel* f2_b1 = MakeBookmark(201, 1, false);
 293   f2_b1->put(PARENT_ID, GetBookmarkId(2));
 294
 295   // Under folder f3, there is nothing.
 296
 297   // Insert in any order.
 298   index_.Insert(f2_b1);
 299   index_.Insert(f3);
 300   index_.Insert(f1_b2);
 301   index_.Insert(f1);
 302   index_.Insert(f2);
 303   index_.Insert(f1_b1);
 304
 305   // Check that all are in the index.
 306   EXPECT_TRUE(index_.Contains(f1));
 307   EXPECT_TRUE(index_.Contains(f2));
 308   EXPECT_TRUE(index_.Contains(f3));
 309   EXPECT_TRUE(index_.Contains(f1_b1));
 310   EXPECT_TRUE(index_.Contains(f1_b2));
 311   EXPECT_TRUE(index_.Contains(f2_b1));
 312
 313   // Remove them all in any order.
 314   index_.Remove(f3);
 315   EXPECT_FALSE(index_.Contains(f3));
 316   index_.Remove(f1_b2);
 317   EXPECT_FALSE(index_.Contains(f1_b2));
 318   index_.Remove(f2_b1);
 319   EXPECT_FALSE(index_.Contains(f2_b1));
 320   index_.Remove(f1);
 321   EXPECT_FALSE(index_.Contains(f1));
 322   index_.Remove(f2);
 323   EXPECT_FALSE(index_.Contains(f2));
 324   index_.Remove(f1_b1);
 325   EXPECT_FALSE(index_.Contains(f1_b1));
 326 }
 327
 328 // Test that involves two non-ordered items.
 329 TEST_F(ParentChildIndexTest, UnorderedChildren) {
 330   // Make two unique client tag items under the root node.
 331   EntryKernel* u1 = MakeUniqueClientItem(1, syncable::Id::GetRoot());
 332   EntryKernel* u2 = MakeUniqueClientItem(2, syncable::Id::GetRoot());
 333
 334   EXPECT_FALSE(u1->ShouldMaintainPosition());
 335   EXPECT_FALSE(u2->ShouldMaintainPosition());
 336
 337   index_.Insert(u1);
 338   index_.Insert(u2);
 339
 340   const OrderedChildSet* children = index_.GetChildren(syncable::Id::GetRoot());
 341   EXPECT_EQ(children->count(u1), 1UL);
 342   EXPECT_EQ(children->count(u2), 1UL);
 343   EXPECT_EQ(children->size(), 2UL);
 344 }
 345
 346 // Test ordered and non-ordered entries under the same parent.
 347 // TODO(rlarocque): We should not need to support this.
 348 TEST_F(ParentChildIndexTest, OrderedAndUnorderedChildren) {
 349   EntryKernel* bm_folder = MakeBookmarkRoot();
 350   index_.Insert(bm_folder);
 351
 352   EntryKernel* b1 = MakeBookmark(1, 1, false);
 353   EntryKernel* b2 = MakeBookmark(2, 2, false);
 354   EntryKernel* u1 = MakeUniqueClientItem(1, GetBookmarkRootId());
 355
 356   index_.Insert(b1);
 357   index_.Insert(u1);
 358   index_.Insert(b2);
 359
 360   const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId());
 361   ASSERT_TRUE(children);
 362   EXPECT_EQ(3UL, children->size());
 363
 364   // Ensure that the non-positionable item is moved to the far right.
 365   OrderedChildSet::const_iterator it = children->begin();
 366   EXPECT_EQ(*it, b1);
 367   it++;
 368   EXPECT_EQ(*it, b2);
 369   it++;
 370   EXPECT_EQ(*it, u1);
 371   it++;
 372   EXPECT_TRUE(it == children->end());
 373 }
 374
 375 TEST_F(ParentChildIndexTest, NodesWithImplicitParentId) {
 376   syncable::Id type_root_id = syncable::Id::CreateFromServerId("type_root");
 377   EntryKernel* type_root = MakeTypeRoot(PREFERENCES, type_root_id);
 378   index_.Insert(type_root);
 379   EXPECT_EQ(type_root_id, IndexKnownModelTypeRootId(PREFERENCES));
 380
 381   // Create entries without parent ID
 382   EntryKernel* p1 = MakeUniqueClientItem(PREFERENCES, 1);
 383   EntryKernel* p2 = MakeUniqueClientItem(PREFERENCES, 2);
 384
 385   index_.Insert(p1);
 386   index_.Insert(p2);
 387
 388   EXPECT_TRUE(index_.Contains(p1));
 389   EXPECT_TRUE(index_.Contains(p2));
 390
 391   // Items should appear under the type root
 392   const OrderedChildSet* children = index_.GetChildren(type_root);
 393   ASSERT_TRUE(children);
 394   EXPECT_EQ(2UL, children->size());
 395
 396   EXPECT_EQ(2UL, index_.GetSiblings(p1)->size());
 397   EXPECT_EQ(2UL, index_.GetSiblings(p2)->size());
 398
 399   index_.Remove(p1);
 400
 401   EXPECT_FALSE(index_.Contains(p1));
 402   EXPECT_TRUE(index_.Contains(p2));
 403   children = index_.GetChildren(type_root_id);
 404   ASSERT_TRUE(children);
 405   EXPECT_EQ(1UL, children->size());
 406
 407   index_.Remove(p2);
 408
 409   EXPECT_FALSE(index_.Contains(p2));
 410   children = index_.GetChildren(type_root);
 411   ASSERT_EQ(nullptr, children);
 412 }
 413
 414 // Test that the removal isn't sensitive to the order (PurgeEntriesWithTypeIn
 415 // removes items in arbitrary order).
 416 TEST_F(ParentChildIndexTest, RemoveOutOfOrder) {
 417   // Insert a type root and two items (with implicit parent ID).
 418   syncable::Id type_root_id = syncable::Id::CreateFromServerId("type_root");
 419   EntryKernel* type_root = MakeTypeRoot(PREFERENCES, type_root_id);
 420   index_.Insert(type_root);
 421   EntryKernel* p1 = MakeUniqueClientItem(PREFERENCES, 1);
 422   EntryKernel* p2 = MakeUniqueClientItem(PREFERENCES, 2);
 423   index_.Insert(p1);
 424   index_.Insert(p2);
 425
 426   // Two items expected under the type root.
 427   const OrderedChildSet* children = index_.GetChildren(type_root);
 428   ASSERT_TRUE(children);
 429   EXPECT_EQ(2UL, children->size());
 430
 431   // Remove all 3 items in arbitrary order.
 432   index_.Remove(p2);
 433   index_.Remove(type_root);
 434   index_.Remove(p1);
 435
 436   EXPECT_EQ(nullptr, index_.GetChildren(type_root));
 437
 438   // Add a new root and another two items again.
 439   type_root = MakeTypeRoot(PREFERENCES, type_root_id);
 440   index_.Insert(type_root);
 441
 442   index_.Insert(MakeUniqueClientItem(PREFERENCES, 3));
 443   index_.Insert(MakeUniqueClientItem(PREFERENCES, 4));
 444
 445   children = index_.GetChildren(type_root);
 446   ASSERT_TRUE(children);
 447   // Should have 2 items. If the out of order removal cleared the implicit
 448   // parent folder ID prematurely, the collection would have 3 items including
 449   // p1.
 450   EXPECT_EQ(2UL, children->size());
 451 }
 452
 453 }  // namespace syncable
 454 }  // namespace syncer
 455