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 345
