Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync r?kitcambridge,mak draft
authorThom Chiovoloni <tchiovoloni@mozilla.com>
Thu, 26 Jan 2017 16:16:17 -0500
changeset 479462 2f0300aa8f2374a03be60dc9c4fd811270b190ab
parent 469157 e9b9944b527ce101d421f9374891f85beb5274b8
child 544694 7f3d367ce4ec1a0151851d3ef1f4d6b98f28fabe
push id44265
push userbmo:tchiovoloni@mozilla.com
push dateMon, 06 Feb 2017 19:34:51 +0000
reviewerskitcambridge, mak
bugs1324503
milestone54.0a1
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync r?kitcambridge,mak This makes two changes: 1. when possible, we avoid reordering all-together. 2. when we must reorder, we fall back to the current order for items that we don't have a specified order for (previously this was unspecified). MozReview-Commit-ID: JgbajK7NDb9
toolkit/components/places/Bookmarks.jsm
toolkit/components/places/tests/bookmarks/test_bookmarks_reorder.js
toolkit/components/places/tests/unit/test_sync_utils.js
--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -689,17 +689,20 @@ var Bookmarks = Object.freeze({
    * Reorders contents of a folder based on a provided array of GUIDs.
    *
    * @param parentGuid
    *        The globally unique identifier of the folder whose contents should
    *        be reordered.
    * @param orderedChildrenGuids
    *        Ordered array of the children's GUIDs.  If this list contains
    *        non-existing entries they will be ignored.  If the list is
-   *        incomplete, missing entries will be appended.
+   *        incomplete, and the current child list is already in order with
+   *        respect to orderedChildrenGuids, no change is made. Otherwise, the
+   *        new items are appended but maintain their current order relative to
+   *        eachother.
    * @param {Object} [options={}]
    *        Additional options. Currently supports the following properties:
    *         - source: The change source, forwarded to all bookmark observers.
    *           Defaults to nsINavBookmarksService::SOURCE_DEFAULT.
    *
    * @return {Promise} resolved when reordering is complete.
    * @rejects if an error happens while reordering.
    * @throws if the arguments are invalid.
@@ -1277,96 +1280,125 @@ function reorderChildren(parent, ordered
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: updateBookmark",
     db => db.executeTransaction(function* () {
       // Select all of the direct children for the given parent.
       let children = yield fetchBookmarksByParent({ parentGuid: parent.guid });
       if (!children.length) {
         return [];
       }
 
-      // Build a map of GUIDs to indices for fast lookups in the comparator
-      // function.
+      // Maps of GUIDs to indices for fast lookups in the comparator function.
       let guidIndices = new Map();
+      let currentIndices = new Map();
       for (let i = 0; i < orderedChildrenGuids.length; ++i) {
         let guid = orderedChildrenGuids[i];
         guidIndices.set(guid, i);
       }
 
-      // Reorder the children array according to the specified order, provided
-      // GUIDs come first, others are appended in somehow random order.
-      children.sort((a, b) => {
-        // This works provided fetchBookmarksByParent returns sorted children.
-        if (!guidIndices.has(a.guid) && !guidIndices.has(b.guid)) {
-          return 0;
-        }
-        if (!guidIndices.has(a.guid)) {
-          return 1;
-        }
-        if (!guidIndices.has(b.guid)) {
-          return -1;
-        }
-        return guidIndices.get(a.guid) < guidIndices.get(b.guid) ? -1 : 1;
-       });
+      // If we got an incomplete list but everything we have is in the right
+      // order, we do nothing.
+      let needReorder = true;
+      let requestedChildIndices = [];
+      for (let i = 0; i < children.length; ++i) {
+        // Take the opportunity to build currentIndices here, since we already
+        // are iterating over the children array.
+        currentIndices.set(children[i].guid, i);
 
-      // Update the bookmarks position now.  If any unknown guid have been
-      // inserted meanwhile, its position will be set to -position, and we'll
-      // handle it later.
-      // To do the update in a single step, we build a VALUES (guid, position)
-      // table.  We then use count() in the sorting table to avoid skipping values
-      // when no more existing GUIDs have been provided.
-      let valuesTable = children.map((child, i) => `("${child.guid}", ${i})`)
-                                .join();
-      yield db.execute(
-        `WITH sorting(g, p) AS (
-           VALUES ${valuesTable}
-         )
-         UPDATE moz_bookmarks SET position = (
-           SELECT CASE count(*) WHEN 0 THEN -position
-                                       ELSE count(*) - 1
-                  END
-           FROM sorting a
-           JOIN sorting b ON b.p <= a.p
-           WHERE a.g = guid
-         )
-         WHERE parent = :parentId
-        `, { parentId: parent._id});
+        if (guidIndices.has(children[i].guid)) {
+          let index = guidIndices.get(children[i].guid);
+          requestedChildIndices.push(index);
+        }
+      }
 
-      let syncChangeDelta =
-        PlacesSyncUtils.bookmarks.determineSyncChangeDelta(options.source);
-      if (syncChangeDelta) {
-        // Flag the parent as having a change.
-        yield db.executeCached(`
-          UPDATE moz_bookmarks SET
-            syncChangeCounter = syncChangeCounter + :syncChangeDelta
-          WHERE id = :parentId`,
-          { parentId: parent._id, syncChangeDelta });
+      if (requestedChildIndices.length) {
+        needReorder = false;
+        for (let i = 1; i < requestedChildIndices.length; ++i) {
+          if (requestedChildIndices[i - 1] > requestedChildIndices[i]) {
+            needReorder = true;
+            break;
+          }
+        }
       }
 
-      // Update position of items that could have been inserted in the meanwhile.
-      // Since this can happen rarely and it's only done for schema coherence
-      // resonds, we won't notify about these changes.
-      yield db.executeCached(
-        `CREATE TEMP TRIGGER moz_bookmarks_reorder_trigger
-           AFTER UPDATE OF position ON moz_bookmarks
-           WHEN NEW.position = -1
-         BEGIN
-           UPDATE moz_bookmarks
-           SET position = (SELECT MAX(position) FROM moz_bookmarks
-                           WHERE parent = NEW.parent) +
-                          (SELECT count(*) FROM moz_bookmarks
-                           WHERE parent = NEW.parent
-                             AND position BETWEEN OLD.position AND -1)
-           WHERE guid = NEW.guid;
-         END
-        `);
+      if (needReorder) {
+
+
+        // Reorder the children array according to the specified order, provided
+        // GUIDs come first, others are appended in somehow random order.
+        children.sort((a, b) => {
+          // This works provided fetchBookmarksByParent returns sorted children.
+          if (!guidIndices.has(a.guid) && !guidIndices.has(b.guid)) {
+            return currentIndices.get(a.guid) < currentIndices.get(b.guid) ? -1 : 1;
+          }
+          if (!guidIndices.has(a.guid)) {
+            return 1;
+          }
+          if (!guidIndices.has(b.guid)) {
+            return -1;
+          }
+          return guidIndices.get(a.guid) < guidIndices.get(b.guid) ? -1 : 1;
+        });
 
-      yield db.executeCached(
-        `UPDATE moz_bookmarks SET position = -1 WHERE position < 0`);
+        // Update the bookmarks position now.  If any unknown guid have been
+        // inserted meanwhile, its position will be set to -position, and we'll
+        // handle it later.
+        // To do the update in a single step, we build a VALUES (guid, position)
+        // table.  We then use count() in the sorting table to avoid skipping values
+        // when no more existing GUIDs have been provided.
+        let valuesTable = children.map((child, i) => `("${child.guid}", ${i})`)
+                                  .join();
+        yield db.execute(
+          `WITH sorting(g, p) AS (
+             VALUES ${valuesTable}
+           )
+           UPDATE moz_bookmarks SET position = (
+             SELECT CASE count(*) WHEN 0 THEN -position
+                                         ELSE count(*) - 1
+                    END
+             FROM sorting a
+             JOIN sorting b ON b.p <= a.p
+             WHERE a.g = guid
+           )
+           WHERE parent = :parentId
+          `, { parentId: parent._id});
 
-      yield db.executeCached(`DROP TRIGGER moz_bookmarks_reorder_trigger`);
+        let syncChangeDelta =
+          PlacesSyncUtils.bookmarks.determineSyncChangeDelta(options.source);
+        if (syncChangeDelta) {
+          // Flag the parent as having a change.
+          yield db.executeCached(`
+            UPDATE moz_bookmarks SET
+              syncChangeCounter = syncChangeCounter + :syncChangeDelta
+            WHERE id = :parentId`,
+            { parentId: parent._id, syncChangeDelta });
+        }
+
+        // Update position of items that could have been inserted in the meanwhile.
+        // Since this can happen rarely and it's only done for schema coherence
+        // resonds, we won't notify about these changes.
+        yield db.executeCached(
+          `CREATE TEMP TRIGGER moz_bookmarks_reorder_trigger
+             AFTER UPDATE OF position ON moz_bookmarks
+             WHEN NEW.position = -1
+           BEGIN
+             UPDATE moz_bookmarks
+             SET position = (SELECT MAX(position) FROM moz_bookmarks
+                             WHERE parent = NEW.parent) +
+                            (SELECT count(*) FROM moz_bookmarks
+                             WHERE parent = NEW.parent
+                               AND position BETWEEN OLD.position AND -1)
+             WHERE guid = NEW.guid;
+           END
+          `);
+
+        yield db.executeCached(
+          `UPDATE moz_bookmarks SET position = -1 WHERE position < 0`);
+
+        yield db.executeCached(`DROP TRIGGER moz_bookmarks_reorder_trigger`);
+      }
 
       // Remove the Sync orphan annotation from the reordered children, so that
       // Sync doesn't try to reparent them once it sees the original parents. We
       // only do this for explicitly ordered children, to avoid removing orphan
       // annos set by Sync.
       let possibleOrphanIds = [];
       for (let child of children) {
         if (guidIndices.has(child.guid)) {
--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_reorder.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_reorder.js
@@ -78,29 +78,44 @@ add_task(function* reorder() {
     yield PlacesUtils.bookmarks.reorder(PlacesUtils.bookmarks.unfiledGuid,
                                         sortedGuids);
     for (let i = 0; i < sorted.length; ++i) {
       let item = yield PlacesUtils.bookmarks.fetch(sorted[i].guid);
       Assert.equal(item.index, i);
     }
   }
 
+
   do_print("Test partial sorting");
-  // Try a partial sorting by passing only 2 entries.
-  // The unspecified entries should retain the original order.
-  sorted = [ sorted[1], sorted[0] ].concat(sorted.slice(2));
-  let sortedGuids = [ sorted[0].guid, sorted[1].guid ];
-  dump("Expected order: " + sorted.map(b => b.guid).join() + "\n");
-  yield PlacesUtils.bookmarks.reorder(PlacesUtils.bookmarks.unfiledGuid,
-                                      sortedGuids);
-  for (let i = 0; i < sorted.length; ++i) {
-    let item = yield PlacesUtils.bookmarks.fetch(sorted[i].guid);
-    Assert.equal(item.index, i);
+  {
+    // Try a partial sorting by passing 2 entries in same order as they
+    // currently have. No entries should change order.
+    let sortedGuids = [ sorted[0].guid, sorted[3].guid ];
+    dump("Expected order: " + sorted.map(b => b.guid).join() + "\n");
+    yield PlacesUtils.bookmarks.reorder(PlacesUtils.bookmarks.unfiledGuid,
+                                        sortedGuids);
+    for (let i = 0; i < sorted.length; ++i) {
+      let item = yield PlacesUtils.bookmarks.fetch(sorted[i].guid);
+      Assert.equal(item.index, i);
+    }
   }
 
+  {
+    // Try a partial sorting by passing 2 entries out of order
+    // The unspecified entries should be appended and retain the original order
+    sorted = [ sorted[1], sorted[0] ].concat(sorted.slice(2));
+    let sortedGuids = [ sorted[0].guid, sorted[1].guid ];
+    dump("Expected order: " + sorted.map(b => b.guid).join() + "\n");
+    yield PlacesUtils.bookmarks.reorder(PlacesUtils.bookmarks.unfiledGuid,
+                                        sortedGuids);
+    for (let i = 0; i < sorted.length; ++i) {
+      let item = yield PlacesUtils.bookmarks.fetch(sorted[i].guid);
+      Assert.equal(item.index, i);
+    }
+  }
   // Use triangular numbers to detect skipped position.
   let db = yield PlacesUtils.promiseDBConnection();
   let rows = yield db.execute(
     `SELECT parent
      FROM moz_bookmarks
      GROUP BY parent
      HAVING (SUM(DISTINCT position + 1) - (count(*) * (count(*) + 1) / 2)) <> 0`);
   Assert.equal(rows.length, 0, "All the bookmarks should have consistent positions");
--- a/toolkit/components/places/tests/unit/test_sync_utils.js
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -193,26 +193,38 @@ add_task(function* test_order() {
   {
     let order = [guids.siblingFolder, guids.siblingSep, guids.childBmk,
       guids.siblingBmk];
     yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.menuGuid, order);
     let childSyncIds = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(PlacesUtils.bookmarks.menuGuid);
     deepEqual(childSyncIds, order, "New bookmarks should be reordered according to array");
   }
 
-  do_print("Reorder with unspecified children");
+  do_print("Same order with unspecified children");
   {
     yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.menuGuid, [
       guids.siblingSep, guids.siblingBmk,
     ]);
     let childSyncIds = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(
       PlacesUtils.bookmarks.menuGuid);
-    deepEqual(childSyncIds, [guids.siblingSep, guids.siblingBmk,
+    deepEqual(childSyncIds, [guids.siblingFolder, guids.siblingSep,
+      guids.childBmk, guids.siblingBmk],
+      "Current order should be respected if possible");
+  }
+
+  do_print("New order with unspecified children");
+  {
+    yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.menuGuid, [
+      guids.siblingBmk, guids.siblingSep,
+    ]);
+    let childSyncIds = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(
+      PlacesUtils.bookmarks.menuGuid);
+    deepEqual(childSyncIds, [guids.siblingBmk, guids.siblingSep,
       guids.siblingFolder, guids.childBmk],
-      "Unordered children should be moved to end");
+      "Unordered children should be moved to end if current order can't be respected");
   }
 
   do_print("Reorder with nonexistent children");
   {
     yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.menuGuid, [
       guids.childBmk, makeGuid(), guids.siblingBmk, guids.siblingSep,
       makeGuid(), guids.siblingFolder, makeGuid()]);
     let childSyncIds = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(