Bug 1295582 - Fix sync bookmark validator bugs around missing parents and orphans r=markh
authorThom Chiovoloni <tchiovoloni@mozilla.com>
Thu, 25 Aug 2016 15:39:56 -0400
changeset 354731 924be2624797eb7a3db7ad3532e389a0a6964cb8
parent 354730 142fd07295b031014a9a221c08d34dbd4809a446
child 354732 c5c0de78a445cdd0875b723ed8849b9d087c3407
push id6570
push userraliiev@mozilla.com
push dateMon, 14 Nov 2016 12:26:13 +0000
treeherdermozilla-beta@f455459b2ae5 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmarkh
bugs1295582
milestone51.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1295582 - Fix sync bookmark validator bugs around missing parents and orphans r=markh MozReview-Commit-ID: LXZuK7ny7Ei
services/sync/modules/bookmark_validator.js
services/sync/tests/unit/test_bookmark_validator.js
--- a/services/sync/modules/bookmark_validator.js
+++ b/services/sync/modules/bookmark_validator.js
@@ -21,16 +21,19 @@ this.EXPORTED_SYMBOLS = ["BookmarkValida
  * - parentChildMismatches (array of {parent: parentid, child: childid}):
  *   instances where the child's parentid and the parent's children array
  *   do not match
  * - cycles (array of array of ids). List of cycles found in the "tree".
  * - orphans (array of {id: string, parent: string}): List of nodes with
  *   either no parentid, or where the parent could not be found.
  * - missingChildren (array of {parent: id, child: id}):
  *   List of parent/children where the child id couldn't be found
+ * - deletedChildren (array of { parent: id, child: id }):
+ *   List of parent/children where child id was a deleted item (but still showed up
+ *   in the children array)
  * - multipleParents (array of {child: id, parents: array of ids}):
  *   List of children that were part of multiple parent arrays
  * - deletedParents (array of ids) : List of records that aren't deleted but
  *   had deleted parents
  * - childrenOnNonFolder (array of ids): list of non-folders that still have
  *   children arrays
  * - duplicateChildren (array of ids): list of records who have the same
  *   child listed multiple times in their children array
@@ -55,16 +58,17 @@ class BookmarkProblemData {
     this.rootOnServer = false;
     this.missingIDs = 0;
 
     this.duplicates = [];
     this.parentChildMismatches = [];
     this.cycles = [];
     this.orphans = [];
     this.missingChildren = [];
+    this.deletedChildren = [];
     this.multipleParents = [];
     this.deletedParents = [];
     this.childrenOnNonFolder = [];
     this.duplicateChildren = [];
     this.parentNotFolder = [];
     this.wrongParentName = [];
 
     this.clientMissing = [];
@@ -95,16 +99,17 @@ class BookmarkProblemData {
       { name: "missingIDs", count: this.missingIDs },
       { name: "rootOnServer", count: this.rootOnServer ? 1 : 0 },
 
       { name: "duplicates", count: this.duplicates.length },
       { name: "parentChildMismatches", count: this.parentChildMismatches.length },
       { name: "cycles", count: this.cycles.length },
       { name: "orphans", count: this.orphans.length },
       { name: "missingChildren", count: this.missingChildren.length },
+      { name: "deletedChildren", count: this.deletedChildren.length },
       { name: "multipleParents", count: this.multipleParents.length },
       { name: "deletedParents", count: this.deletedParents.length },
       { name: "childrenOnNonFolder", count: this.childrenOnNonFolder.length },
       { name: "duplicateChildren", count: this.duplicateChildren.length },
       { name: "parentNotFolder", count: this.parentNotFolder.length },
       { name: "wrongParentName", count: this.wrongParentName.length },
     ];
   }
@@ -226,20 +231,28 @@ class BookmarkValidator {
       }
       if (record.deleted) {
         deletedItemIds.add(record.id);
       } else {
         if (idToRecord.has(record.id)) {
           problemData.duplicates.push(record.id);
           continue;
         }
-        idToRecord.set(record.id, record);
       }
-      if (record.children && record.type !== "livemark") {
-        if (record.type !== 'folder') {
+      idToRecord.set(record.id, record);
+
+      if (record.children) {
+        if (record.type !== "folder") {
+          // Due to implementation details in engines/bookmarks.js, (Livemark
+          // subclassing BookmarkFolder) Livemarks will have a children array,
+          // but it should still be empty.
+          if (!record.children.length) {
+            continue;
+          }
+          // Otherwise we mark it as an error and still try to resolve the children
           problemData.childrenOnNonFolder.push(record.id);
         }
         folders.push(record);
 
         if (new Set(record.children).size !== record.children.length) {
           problemData.duplicateChildren.push(record.id)
         }
 
@@ -295,30 +308,40 @@ class BookmarkValidator {
 
     // Build the tree, find orphans, and record most problems having to do with
     // the tree structure.
     for (let [id, record] of idToRecord) {
       if (record === root) {
         continue;
       }
 
+      if (record.isDeleted) {
+        continue;
+      }
+
       let parentID = record.parentid;
       if (!parentID) {
         problemData.orphans.push({id: record.id, parent: parentID});
         continue;
       }
 
       let parent = idToRecord.get(parentID);
       if (!parent) {
         problemData.orphans.push({id: record.id, parent: parentID});
         continue;
       }
 
       if (parent.type !== 'folder') {
         problemData.parentNotFolder.push(record.id);
+        if (!parent.children) {
+          parent.children = [];
+        }
+        if (!parent.childGUIDs) {
+          parent.childGUIDs = [];
+        }
       }
 
       if (!record.isDeleted) {
         resultRecords.push(record);
       }
 
       record.parent = parent;
       if (parent !== root || problemData.rootOnServer) {
@@ -338,44 +361,96 @@ class BookmarkValidator {
 
       if (record.parentName !== parent.title && parent.id !== 'unfiled') {
         problemData.wrongParentName.push(record.id);
       }
     }
 
     // Check that we aren't missing any children.
     for (let folder of folders) {
-      for (let ci = 0; ci < folder.children.length; ++ci) {
-        let child = folder.children[ci];
-        if (typeof child === 'string') {
-          let childObject = idToRecord.get(child);
+      folder.unfilteredChildren = folder.children;
+      folder.children = [];
+      for (let ci = 0; ci < folder.unfilteredChildren.length; ++ci) {
+        let child = folder.unfilteredChildren[ci];
+        let childObject;
+        if (typeof child == "string") {
+          // This can happen the parent refers to a child that has a different
+          // parentid, or if it refers to a missing or deleted child. It shouldn't
+          // be possible with totally valid bookmarks.
+          childObject = idToRecord.get(child);
           if (!childObject) {
             problemData.missingChildren.push({parent: folder.id, child});
           } else {
-            if (childObject.parentid === folder.id) {
-              // Probably impossible, would have been caught in the loop above.
-              continue;
-            }
-
-            // The child is in multiple `children` arrays.
-            let currentProblemRecord = problemData.multipleParents.find(pr =>
-              pr.child === child);
-
-            if (currentProblemRecord) {
-              currentProblemRecord.parents.push(folder.id);
-            } else {
-              problemData.multipleParents.push({ child, parents: [childObject.parentid, folder.id] });
+            folder.unfilteredChildren[ci] = childObject;
+            if (childObject.isDeleted) {
+              problemData.deletedChildren.push({ parent: folder.id, child });
             }
           }
-          // Remove it from the array to avoid needing to special case this later.
-          folder.children.splice(ci, 1);
-          --ci;
+        } else {
+          childObject = child;
+        }
+
+        if (!childObject) {
+          continue;
+        }
+
+        if (childObject.parentid === folder.id) {
+          folder.children.push(childObject);
+          continue;
+        }
+
+        // The child is very probably in multiple `children` arrays --
+        // see if we already have a problem record about it.
+        let currentProblemRecord = problemData.multipleParents.find(pr =>
+          pr.child === child);
+
+        if (currentProblemRecord) {
+          currentProblemRecord.parents.push(folder.id);
+          continue;
         }
+
+        let otherParent = idToRecord.get(childObject.parentid);
+        // it's really an ... orphan ... sort of.
+        if (!otherParent) {
+          // if we never end up adding to this parent's list, we filter it out after this loop.
+          problemData.multipleParents.push({
+            child,
+            parents: [folder.id]
+          });
+          if (!problemData.orphans.some(r => r.id === child)) {
+            problemData.orphans.push({
+              id: child,
+              parent: childObject.parentid
+            });
+          }
+          continue;
+        }
+
+        if (otherParent.isDeleted) {
+          if (!problemData.deletedParents.includes(child)) {
+            problemData.deletedParents.push(child);
+          }
+          continue;
+        }
+
+        if (otherParent.childGUIDs && !otherParent.childGUIDs.includes(child)) {
+          if (!problemData.parentChildMismatches.some(r => r.child === child)) {
+            // Might not be possible to get here.
+            problemData.parentChildMismatches.push({ child, parent: folder.id });
+          }
+        }
+
+        problemData.multipleParents.push({
+          child,
+          parents: [childObject.parentid, folder.id]
+        });
       }
     }
+    problemData.multipleParents = problemData.multipleParents.filter(record =>
+      record.parents.length >= 2);
 
     problemData.cycles = this._detectCycles(resultRecords);
 
     return {
       deletedRecords,
       records: resultRecords,
       problemData,
       root,
--- a/services/sync/tests/unit/test_bookmark_validator.js
+++ b/services/sync/tests/unit/test_bookmark_validator.js
@@ -37,23 +37,33 @@ add_test(function test_isr_cycles() {
   run_next_test();
 });
 
 add_test(function test_isr_orphansMultiParents() {
   let c = inspectServerRecords([
     { id: 'A', type: 'bookmark', parentid: 'D' },
     { id: 'B', type: 'folder', parentid: 'places', children: ['A']},
     { id: 'C', type: 'folder', parentid: 'places', children: ['A']},
+
+  ]).problemData;
+  deepEqual(c.orphans, [{ id: "A", parent: "D" }]);
+  equal(c.multipleParents.length, 1)
+  ok(c.multipleParents[0].parents.indexOf('B') >= 0);
+  ok(c.multipleParents[0].parents.indexOf('C') >= 0);
+  run_next_test();
+});
+
+add_test(function test_isr_orphansMultiParents2() {
+  let c = inspectServerRecords([
+    { id: 'A', type: 'bookmark', parentid: 'D' },
+    { id: 'B', type: 'folder', parentid: 'places', children: ['A']},
   ]).problemData;
   equal(c.orphans.length, 1);
   equal(c.orphans[0].id, 'A');
-  equal(c.multipleParents.length, 1);
-  equal(c.multipleParents[0].child, 'A');
-  ok(c.multipleParents[0].parents.indexOf('B') >= 0);
-  ok(c.multipleParents[0].parents.indexOf('C') >= 0);
+  equal(c.multipleParents.length, 0);
   run_next_test();
 });
 
 add_test(function test_isr_deletedParents() {
   let c = inspectServerRecords([
     { id: 'A', type: 'bookmark', parentid: 'B' },
     { id: 'B', type: 'folder', parentid: 'places', children: ['A']},
     { id: 'B', type: 'item', deleted: true},