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 class ParentChildIndexTest : public testing::Test {
  23  public:
  24   virtual void TearDown() {
  25     // To make memory management easier, we take ownership of all EntryKernels
  26     // returned by our factory methods and delete them here.
  27     STLDeleteElements(&owned_entry_kernels_);
  28   }
  29
  30   // Unfortunately, we can't use the regular Entry factory methods, because the
  31   // ParentChildIndex deals in EntryKernels.
  32
  33   static syncable::Id GetBookmarkRootId() {
  34     return syncable::Id::CreateFromServerId("bookmark_folder");
  35   }
  36
  37   static syncable::Id GetBookmarkId(int n) {
  38     return syncable::Id::CreateFromServerId("b" + base::IntToString(n));
  39   }
  40
  41   static syncable::Id GetClientUniqueId(int n) {
  42     return syncable::Id::CreateFromServerId("c" + base::IntToString(n));
  43   }
  44
  45   EntryKernel* MakeRoot() {
  46     // Mimics the root node.
  47     EntryKernel* root = new EntryKernel();
  48     root->put(META_HANDLE, 1);
  49     root->put(BASE_VERSION, -1);
  50     root->put(SERVER_VERSION, 0);
  51     root->put(IS_DIR, true);
  52     root->put(ID, syncable::Id());
  53     root->put(PARENT_ID, syncable::Id());
  54     root->put(SERVER_PARENT_ID, syncable::Id());
  55
  56     owned_entry_kernels_.push_back(root);
  57     return root;
  58   }
  59
  60   EntryKernel* MakeBookmarkRoot() {
  61     // Mimics a server-created bookmark folder.
  62     EntryKernel* folder = new EntryKernel;
  63     folder->put(META_HANDLE, 1);
  64     folder->put(BASE_VERSION, 9);
  65     folder->put(SERVER_VERSION, 9);
  66     folder->put(IS_DIR, true);
  67     folder->put(ID, GetBookmarkRootId());
  68     folder->put(SERVER_PARENT_ID, syncable::Id());
  69     folder->put(PARENT_ID, syncable::Id());
  70     folder->put(UNIQUE_SERVER_TAG, "google_chrome_bookmarks");
  71
  72     owned_entry_kernels_.push_back(folder);
  73     return folder;
  74   }
  75
  76   EntryKernel* MakeBookmark(int n, int pos, bool is_dir) {
  77     // Mimics a regular bookmark or folder.
  78     EntryKernel* bm = new EntryKernel();
  79     bm->put(META_HANDLE, n);
  80     bm->put(BASE_VERSION, 10);
  81     bm->put(SERVER_VERSION, 10);
  82     bm->put(IS_DIR, is_dir);
  83     bm->put(ID, GetBookmarkId(n));
  84     bm->put(PARENT_ID, GetBookmarkRootId());
  85     bm->put(SERVER_PARENT_ID, GetBookmarkRootId());
  86
  87     bm->put(UNIQUE_BOOKMARK_TAG,
  88             syncable::GenerateSyncableBookmarkHash(kCacheGuid,
  89                                                    bm->ref(ID).GetServerId()));
  90
  91     UniquePosition unique_pos =
  92         UniquePosition::FromInt64(pos, bm->ref(UNIQUE_BOOKMARK_TAG));
  93     bm->put(UNIQUE_POSITION, unique_pos);
  94     bm->put(SERVER_UNIQUE_POSITION, unique_pos);
  95
  96     owned_entry_kernels_.push_back(bm);
  97     return bm;
  98   }
  99
 100   EntryKernel* MakeUniqueClientItem(int n) {
 101     EntryKernel* item = new EntryKernel();
 102     item->put(META_HANDLE, n);
 103     item->put(BASE_VERSION, 10);
 104     item->put(SERVER_VERSION, 10);
 105     item->put(IS_DIR, false);
 106     item->put(ID, GetClientUniqueId(n));
 107     item->put(PARENT_ID, syncable::Id());
 108     item->put(SERVER_PARENT_ID, syncable::Id());
 109     item->put(UNIQUE_CLIENT_TAG, base::IntToString(n));
 110
 111     owned_entry_kernels_.push_back(item);
 112     return item;
 113   }
 114
 115   ParentChildIndex index_;
 116
 117  private:
 118   std::list<EntryKernel*> owned_entry_kernels_;
 119 };
 120
 121 TEST_F(ParentChildIndexTest, TestRootNode) {
 122   EntryKernel* root = MakeRoot();
 123   EXPECT_FALSE(ParentChildIndex::ShouldInclude(root));
 124 }
 125
 126 TEST_F(ParentChildIndexTest, TestBookmarkRootFolder) {
 127   EntryKernel* bm_folder = MakeBookmarkRoot();
 128   EXPECT_TRUE(ParentChildIndex::ShouldInclude(bm_folder));
 129 }
 130
 131 // Tests iteration over a set of siblings.
 132 TEST_F(ParentChildIndexTest, ChildInsertionAndIteration) {
 133   EntryKernel* bm_folder = MakeBookmarkRoot();
 134   index_.Insert(bm_folder);
 135
 136   // Make some folder and non-folder entries.
 137   EntryKernel* b1 = MakeBookmark(1, 1, false);
 138   EntryKernel* b2 = MakeBookmark(2, 2, false);
 139   EntryKernel* b3 = MakeBookmark(3, 3, true);
 140   EntryKernel* b4 = MakeBookmark(4, 4, false);
 141
 142   // Insert them out-of-order to test different cases.
 143   index_.Insert(b3); // Only child.
 144   index_.Insert(b4); // Right-most child.
 145   index_.Insert(b1); // Left-most child.
 146   index_.Insert(b2); // Between existing items.
 147
 148   // Double-check they've been added.
 149   EXPECT_TRUE(index_.Contains(b1));
 150   EXPECT_TRUE(index_.Contains(b2));
 151   EXPECT_TRUE(index_.Contains(b3));
 152   EXPECT_TRUE(index_.Contains(b4));
 153
 154   // Check the ordering.
 155   const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId());
 156   ASSERT_TRUE(children);
 157   ASSERT_EQ(children->size(), 4UL);
 158   OrderedChildSet::const_iterator it = children->begin();
 159   EXPECT_EQ(*it, b1);
 160   it++;
 161   EXPECT_EQ(*it, b2);
 162   it++;
 163   EXPECT_EQ(*it, b3);
 164   it++;
 165   EXPECT_EQ(*it, b4);
 166   it++;
 167   EXPECT_TRUE(it == children->end());
 168 }
 169
 170 // Tests iteration when hierarchy is involved.
 171 TEST_F(ParentChildIndexTest, ChildInsertionAndIterationWithHierarchy) {
 172   EntryKernel* bm_folder = MakeBookmarkRoot();
 173   index_.Insert(bm_folder);
 174
 175   // Just below the root, we have folders f1 and f2.
 176   EntryKernel* f1 = MakeBookmark(1, 1, false);
 177   EntryKernel* f2 = MakeBookmark(2, 2, false);
 178   EntryKernel* f3 = MakeBookmark(3, 3, false);
 179
 180   // Under folder f1, we have two bookmarks.
 181   EntryKernel* f1_b1 = MakeBookmark(101, 1, false);
 182   f1_b1->put(PARENT_ID, GetBookmarkId(1));
 183   EntryKernel* f1_b2 = MakeBookmark(102, 2, false);
 184   f1_b2->put(PARENT_ID, GetBookmarkId(1));
 185
 186   // Under folder f2, there is one bookmark.
 187   EntryKernel* f2_b1 = MakeBookmark(201, 1, false);
 188   f2_b1->put(PARENT_ID, GetBookmarkId(2));
 189
 190   // Under folder f3, there is nothing.
 191
 192   // Insert in a strange order, because we can.
 193   index_.Insert(f1_b2);
 194   index_.Insert(f2);
 195   index_.Insert(f2_b1);
 196   index_.Insert(f1);
 197   index_.Insert(f1_b1);
 198   index_.Insert(f3);
 199
 200   OrderedChildSet::const_iterator it;
 201
 202   // Iterate over children of the bookmark root.
 203   const OrderedChildSet* top_children = index_.GetChildren(GetBookmarkRootId());
 204   ASSERT_TRUE(top_children);
 205   ASSERT_EQ(top_children->size(), 3UL);
 206   it = top_children->begin();
 207   EXPECT_EQ(*it, f1);
 208   it++;
 209   EXPECT_EQ(*it, f2);
 210   it++;
 211   EXPECT_EQ(*it, f3);
 212   it++;
 213   EXPECT_TRUE(it == top_children->end());
 214
 215   // Iterate over children of the first folder.
 216   const OrderedChildSet* f1_children = index_.GetChildren(GetBookmarkId(1));
 217   ASSERT_TRUE(f1_children);
 218   ASSERT_EQ(f1_children->size(), 2UL);
 219   it = f1_children->begin();
 220   EXPECT_EQ(*it, f1_b1);
 221   it++;
 222   EXPECT_EQ(*it, f1_b2);
 223   it++;
 224   EXPECT_TRUE(it == f1_children->end());
 225
 226   // Iterate over children of the second folder.
 227   const OrderedChildSet* f2_children = index_.GetChildren(GetBookmarkId(2));
 228   ASSERT_TRUE(f2_children);
 229   ASSERT_EQ(f2_children->size(), 1UL);
 230   it = f2_children->begin();
 231   EXPECT_EQ(*it, f2_b1);
 232   it++;
 233   EXPECT_TRUE(it == f2_children->end());
 234
 235   // Check for children of the third folder.
 236   const OrderedChildSet* f3_children = index_.GetChildren(GetBookmarkId(3));
 237   EXPECT_FALSE(f3_children);
 238 }
 239
 240 // Tests removing items.
 241 TEST_F(ParentChildIndexTest, RemoveWithHierarchy) {
 242   EntryKernel* bm_folder = MakeBookmarkRoot();
 243   index_.Insert(bm_folder);
 244
 245   // Just below the root, we have folders f1 and f2.
 246   EntryKernel* f1 = MakeBookmark(1, 1, false);
 247   EntryKernel* f2 = MakeBookmark(2, 2, false);
 248   EntryKernel* f3 = MakeBookmark(3, 3, false);
 249
 250   // Under folder f1, we have two bookmarks.
 251   EntryKernel* f1_b1 = MakeBookmark(101, 1, false);
 252   f1_b1->put(PARENT_ID, GetBookmarkId(1));
 253   EntryKernel* f1_b2 = MakeBookmark(102, 2, false);
 254   f1_b2->put(PARENT_ID, GetBookmarkId(1));
 255
 256   // Under folder f2, there is one bookmark.
 257   EntryKernel* f2_b1 = MakeBookmark(201, 1, false);
 258   f2_b1->put(PARENT_ID, GetBookmarkId(2));
 259
 260   // Under folder f3, there is nothing.
 261
 262   // Insert in any order.
 263   index_.Insert(f2_b1);
 264   index_.Insert(f3);
 265   index_.Insert(f1_b2);
 266   index_.Insert(f1);
 267   index_.Insert(f2);
 268   index_.Insert(f1_b1);
 269
 270   // Check that all are in the index.
 271   EXPECT_TRUE(index_.Contains(f1));
 272   EXPECT_TRUE(index_.Contains(f2));
 273   EXPECT_TRUE(index_.Contains(f3));
 274   EXPECT_TRUE(index_.Contains(f1_b1));
 275   EXPECT_TRUE(index_.Contains(f1_b2));
 276   EXPECT_TRUE(index_.Contains(f2_b1));
 277
 278   // Remove them all in any order.
 279   index_.Remove(f3);
 280   EXPECT_FALSE(index_.Contains(f3));
 281   index_.Remove(f1_b2);
 282   EXPECT_FALSE(index_.Contains(f1_b2));
 283   index_.Remove(f2_b1);
 284   EXPECT_FALSE(index_.Contains(f2_b1));
 285   index_.Remove(f1);
 286   EXPECT_FALSE(index_.Contains(f1));
 287   index_.Remove(f2);
 288   EXPECT_FALSE(index_.Contains(f2));
 289   index_.Remove(f1_b1);
 290   EXPECT_FALSE(index_.Contains(f1_b1));
 291 }
 292
 293 // Test that involves two non-ordered items.
 294 TEST_F(ParentChildIndexTest, UnorderedChildren) {
 295   // Make two unique client tag items under the root node.
 296   EntryKernel* u1 = MakeUniqueClientItem(1);
 297   EntryKernel* u2 = MakeUniqueClientItem(2);
 298
 299   EXPECT_FALSE(u1->ShouldMaintainPosition());
 300   EXPECT_FALSE(u2->ShouldMaintainPosition());
 301
 302   index_.Insert(u1);
 303   index_.Insert(u2);
 304
 305   const OrderedChildSet* children = index_.GetChildren(syncable::Id());
 306   EXPECT_EQ(children->count(u1), 1UL);
 307   EXPECT_EQ(children->count(u2), 1UL);
 308   EXPECT_EQ(children->size(), 2UL);
 309 }
 310
 311 // Test ordered and non-ordered entries under the same parent.
 312 // TODO(rlarocque): We should not need to support this.
 313 TEST_F(ParentChildIndexTest, OrderedAndUnorderedChildren) {
 314   EntryKernel* bm_folder = MakeBookmarkRoot();
 315   index_.Insert(bm_folder);
 316
 317   EntryKernel* b1 = MakeBookmark(1, 1, false);
 318   EntryKernel* b2 = MakeBookmark(2, 2, false);
 319   EntryKernel* u1 = MakeUniqueClientItem(1);
 320   u1->put(PARENT_ID, GetBookmarkRootId());
 321
 322   index_.Insert(b1);
 323   index_.Insert(u1);
 324   index_.Insert(b2);
 325
 326   const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId());
 327   ASSERT_TRUE(children);
 328   EXPECT_EQ(children->size(), 3UL);
 329
 330   // Ensure that the non-positionable item is moved to the far right.
 331   OrderedChildSet::const_iterator it = children->begin();
 332   EXPECT_EQ(*it, b1);
 333   it++;
 334   EXPECT_EQ(*it, b2);
 335   it++;
 336   EXPECT_EQ(*it, u1);
 337   it++;
 338   EXPECT_TRUE(it == children->end());
 339 }
 340
 341 }  // namespace
 342 }  // namespace syncable
 343 }  // namespace syncer
 344