Bug 1274496 - Filter excluded bookmarks at sync time based on their root. r=markh,rnewman
authorKit Cambridge <kcambridge@mozilla.com>
Tue, 06 Sep 2016 11:39:13 -0700
changeset 355116 40663c31d2d6bd122ab90dc4b76376102b75d821
parent 355115 0154cd83212689f344562d3ae83f7c2623e72019
child 355117 2b996739ade25a2d6cf3fb5ad6f2af1aa1e2fe88
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, rnewman
bugs1274496
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 1274496 - Filter excluded bookmarks at sync time based on their root. r=markh,rnewman MozReview-Commit-ID: 6xWohLeIMha
services/sync/modules/engines.js
services/sync/modules/engines/bookmarks.js
services/sync/modules/engines/clients.js
services/sync/tests/unit/test_bookmark_tracker.js
--- a/services/sync/modules/engines.js
+++ b/services/sync/modules/engines.js
@@ -2,17 +2,18 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 this.EXPORTED_SYMBOLS = [
   "EngineManager",
   "Engine",
   "SyncEngine",
   "Tracker",
-  "Store"
+  "Store",
+  "Changeset"
 ];
 
 var {classes: Cc, interfaces: Ci, results: Cr, utils: Cu} = Components;
 
 Cu.import("resource://services-common/async.js");
 Cu.import("resource://gre/modules/Log.jsm");
 Cu.import("resource://services-common/observers.js");
 Cu.import("resource://services-sync/constants.js");
@@ -126,48 +127,53 @@ Tracker.prototype = {
   },
 
   unignoreID: function (id) {
     let index = this._ignored.indexOf(id);
     if (index != -1)
       this._ignored.splice(index, 1);
   },
 
+  _saveChangedID(id, when) {
+    this._log.trace(`Adding changed ID: ${id}, ${JSON.stringify(when)}`);
+    this.changedIDs[id] = when;
+    this.saveChangedIDs(this.onSavedChangedIDs);
+  },
+
   addChangedID: function (id, when) {
     if (!id) {
       this._log.warn("Attempted to add undefined ID to tracker");
       return false;
     }
 
-    if (this.ignoreAll || (id in this._ignored)) {
+    if (this.ignoreAll || this._ignored.includes(id)) {
       return false;
     }
 
     // Default to the current time in seconds if no time is provided.
     if (when == null) {
-      when = Math.floor(Date.now() / 1000);
+      when = Date.now() / 1000;
     }
 
     // Add/update the entry if we have a newer time.
     if ((this.changedIDs[id] || -Infinity) < when) {
-      this._log.trace("Adding changed ID: " + id + ", " + when);
-      this.changedIDs[id] = when;
-      this.saveChangedIDs(this.onSavedChangedIDs);
+      this._saveChangedID(id, when);
     }
 
     return true;
   },
 
   removeChangedID: function (id) {
     if (!id) {
       this._log.warn("Attempted to remove undefined ID to tracker");
       return false;
     }
-    if (this.ignoreAll || (id in this._ignored))
+    if (this.ignoreAll || this._ignored.includes(id)) {
       return false;
+    }
     if (this.changedIDs[id] != null) {
       this._log.trace("Removing changed ID " + id);
       delete this.changedIDs[id];
       this.saveChangedIDs();
     }
     return true;
   },
 
@@ -857,19 +863,18 @@ SyncEngine.prototype = {
     return parseInt(Svc.Prefs.get(this.name + ".lastSyncLocal", "0"), 10);
   },
   set lastSyncLocal(value) {
     // Store as a string because pref can only store C longs as numbers.
     Svc.Prefs.set(this.name + ".lastSyncLocal", value.toString());
   },
 
   /*
-   * Returns a mapping of IDs -> changed timestamp. Engine implementations
-   * can override this method to bypass the tracker for certain or all
-   * changed items.
+   * Returns a changeset for this sync. Engine implementations can override this
+   * method to bypass the tracker for certain or all changed items.
    */
   getChangedIDs: function () {
     return this._tracker.changedIDs;
   },
 
   // Create a new record using the store and add in crypto fields.
   _createRecord: function (id) {
     let record = this._store.createRecord(id, this.name);
@@ -927,30 +932,26 @@ SyncEngine.prototype = {
     // Save objects that need to be uploaded in this._modified. We also save
     // the timestamp of this fetch in this.lastSyncLocal. As we successfully
     // upload objects we remove them from this._modified. If an error occurs
     // or any objects fail to upload, they will remain in this._modified. At
     // the end of a sync, or after an error, we add all objects remaining in
     // this._modified to the tracker.
     this.lastSyncLocal = Date.now();
     if (this.lastSync) {
-      this._modified = this.getChangedIDs();
+      this._modified = this.pullNewChanges();
     } else {
-      // Mark all items to be uploaded, but treat them as changed from long ago
       this._log.debug("First sync, uploading all items");
-      this._modified = {};
-      for (let id in this._store.getAllIDs()) {
-        this._modified[id] = 0;
-      }
+      this._modified = this.pullAllChanges();
     }
     // Clear the tracker now. If the sync fails we'll add the ones we failed
     // to upload back.
     this._tracker.clearChangedIDs();
 
-    this._log.info(Object.keys(this._modified).length +
+    this._log.info(this._modified.count() +
                    " outgoing items pre-reconciliation");
 
     // Keep track of what to delete at the end of sync
     this._delete = {};
   },
 
   /**
    * A tiny abstraction to make it easier to test incoming record
@@ -1288,22 +1289,22 @@ SyncEngine.prototype = {
     if (this._log.level <= Log.Level.Trace) {
       this._log.trace("Incoming: " + item);
     }
 
     // We start reconciling by collecting a bunch of state. We do this here
     // because some state may change during the course of this function and we
     // need to operate on the original values.
     let existsLocally   = this._store.itemExists(item.id);
-    let locallyModified = item.id in this._modified;
+    let locallyModified = this._modified.has(item.id);
 
     // TODO Handle clock drift better. Tracked in bug 721181.
     let remoteAge = AsyncResource.serverTime - item.modified;
     let localAge  = locallyModified ?
-      (Date.now() / 1000 - this._modified[item.id]) : null;
+      (Date.now() / 1000 - this._modified.getModifiedTimestamp(item.id)) : null;
     let remoteIsNewer = remoteAge < localAge;
 
     this._log.trace("Reconciling " + item.id + ". exists=" +
                     existsLocally + "; modified=" + locallyModified +
                     "; local age=" + localAge + "; incoming age=" +
                     remoteAge);
 
     // We handle deletions first so subsequent logic doesn't have to check
@@ -1364,23 +1365,23 @@ SyncEngine.prototype = {
         // an item but doesn't expose it through itemExists. If the API
         // contract were stronger, this could be changed.
         this._log.debug("Switching local ID to incoming: " + dupeID + " -> " +
                         item.id);
         this._store.changeItemID(dupeID, item.id);
 
         // If the local item was modified, we carry its metadata forward so
         // appropriate reconciling can be performed.
-        if (dupeID in this._modified) {
+        if (this._modified.has(dupeID)) {
           locallyModified = true;
-          localAge = Date.now() / 1000 - this._modified[dupeID];
+          localAge = Date.now() / 1000 -
+            this._modified.getModifiedTimestamp(dupeID);
           remoteIsNewer = remoteAge < localAge;
 
-          this._modified[item.id] = this._modified[dupeID];
-          delete this._modified[dupeID];
+          this._modified.swap(dupeID, item.id);
         } else {
           locallyModified = false;
           localAge = null;
         }
 
         this._log.debug("Local item after duplication: age=" + localAge +
                         "; modified=" + locallyModified + "; exists=" +
                         existsLocally);
@@ -1404,17 +1405,17 @@ SyncEngine.prototype = {
       }
 
       // If the item was modified locally but isn't present, it must have
       // been deleted. If the incoming record is younger, we restore from
       // that record.
       if (remoteIsNewer) {
         this._log.trace("Applying incoming because local item was deleted " +
                         "before the incoming item was changed.");
-        delete this._modified[item.id];
+        this._modified.delete(item.id);
         return true;
       }
 
       this._log.trace("Ignoring incoming item because the local item's " +
                       "deletion is newer.");
       return false;
     }
 
@@ -1430,17 +1431,17 @@ SyncEngine.prototype = {
 
     // If the records are the same, we don't need to do anything. This does
     // potentially throw away a local modification time. But, if the records
     // are the same, does it matter?
     if (recordsEqual) {
       this._log.trace("Ignoring incoming item because the local item is " +
                       "identical.");
 
-      delete this._modified[item.id];
+      this._modified.delete(item.id);
       return false;
     }
 
     // At this point the records are different.
 
     // If we have no local modifications, always take the server record.
     if (!locallyModified) {
       this._log.trace("Applying incoming record because no local conflicts.");
@@ -1455,17 +1456,17 @@ SyncEngine.prototype = {
                    item.id);
     return remoteIsNewer;
   },
 
   // Upload outgoing records.
   _uploadOutgoing: function () {
     this._log.trace("Uploading local changes to server.");
 
-    let modifiedIDs = Object.keys(this._modified);
+    let modifiedIDs = this._modified.ids();
     if (modifiedIDs.length) {
       this._log.trace("Preparing " + modifiedIDs.length +
                       " outgoing records");
 
       let counts = { sent: modifiedIDs.length, failed: 0 };
 
       // collection we'll upload
       let up = new Collection(this.engineURL, null, this.service);
@@ -1499,17 +1500,17 @@ SyncEngine.prototype = {
           this._log.debug("Records that will be uploaded again because "
                           + "the server couldn't store them: "
                           + failed.join(", "));
         }
 
         counts.failed += failed.length;
 
         for (let id of successful) {
-          delete this._modified[id];
+          this._modified.delete(id);
         }
 
         this._onRecordsWritten(successful, failed);
 
         // clear for next batch
         failed.length = 0;
         successful.length = 0;
       };
@@ -1583,20 +1584,18 @@ SyncEngine.prototype = {
   },
 
   _syncCleanup: function () {
     if (!this._modified) {
       return;
     }
 
     // Mark failed WBOs as changed again so they are reuploaded next time.
-    for (let [id, when] of Object.entries(this._modified)) {
-      this._tracker.addChangedID(id, when);
-    }
-    this._modified = {};
+    this.trackRemainingChanges();
+    this._modified.clear();
   },
 
   _sync: function () {
     try {
       this._syncStartup();
       Observers.notify("weave:engine:sync:status", "process-incoming");
       this._processIncoming();
       Observers.notify("weave:engine:sync:status", "upload-outgoing");
@@ -1672,10 +1671,113 @@ SyncEngine.prototype = {
    *
    * All return values will be part of the kRecoveryStrategy enumeration.
    */
   handleHMACMismatch: function (item, mayRetry) {
     // By default we either try again, or bail out noisily.
     return (this.service.handleHMACEvent() && mayRetry) ?
            SyncEngine.kRecoveryStrategy.retry :
            SyncEngine.kRecoveryStrategy.error;
+  },
+
+  /**
+   * Returns a changeset containing all items in the store. The default
+   * implementation returns a changeset with timestamps from long ago, to
+   * ensure we always use the remote version if one exists.
+   *
+   * This function is only called for the first sync. Subsequent syncs call
+   * `pullNewChanges`.
+   *
+   * @return A `Changeset` object.
+   */
+  pullAllChanges() {
+    let changeset = new Changeset();
+    for (let id in this._store.getAllIDs()) {
+      changeset.set(id, 0);
+    }
+    return changeset;
+  },
+
+  /*
+   * Returns a changeset containing entries for all currently tracked items.
+   * The default implementation returns a changeset with timestamps indicating
+   * when the item was added to the tracker.
+   *
+   * @return A `Changeset` object.
+   */
+  pullNewChanges() {
+    return new Changeset(this.getChangedIDs());
+  },
+
+  /**
+   * Adds all remaining changeset entries back to the tracker, typically for
+   * items that failed to upload. This method is called at the end of each sync.
+   *
+   */
+  trackRemainingChanges() {
+    for (let [id, change] of this._modified.entries()) {
+      this._tracker.addChangedID(id, change);
+    }
+  },
+};
+
+/**
+ * A changeset is created for each sync in `Engine::get{Changed, All}IDs`,
+ * and stores opaque change data for tracked IDs. The default implementation
+ * only records timestamps, though engines can extend this to store additional
+ * data for each entry.
+ */
+class Changeset {
+  // Creates a changeset with an initial set of tracked entries.
+  constructor(changes = {}) {
+    this.changes = changes;
   }
-};
+
+  // Returns the last modified time, in seconds, for an entry in the changeset.
+  // `id` is guaranteed to be in the set.
+  getModifiedTimestamp(id) {
+    return this.changes[id];
+  }
+
+  // Adds a change for a tracked ID to the changeset.
+  set(id, change) {
+    this.changes[id] = change;
+  }
+
+  // Indicates whether an entry is in the changeset.
+  has(id) {
+    return id in this.changes;
+  }
+
+  // Deletes an entry from the changeset. Used to clean up entries for
+  // reconciled and successfully uploaded records.
+  delete(id) {
+    delete this.changes[id];
+  }
+
+  // Swaps two entries in the changeset. Used when reconciling duplicates that
+  // have local changes.
+  swap(oldID, newID) {
+    this.changes[newID] = this.changes[oldID];
+    delete this.changes[oldID];
+  }
+
+  // Returns an array of all tracked IDs in this changeset.
+  ids() {
+    return Object.keys(this.changes);
+  }
+
+  // Returns an array of `[id, change]` tuples. Used to repopulate the tracker
+  // with entries for failed uploads at the end of a sync.
+  entries() {
+    return Object.entries(this.changes);
+  }
+
+  // Returns the number of entries in this changeset.
+  count() {
+    return this.ids().length;
+  }
+
+  // Clears the changeset.
+  clear() {
+    this.changes = {};
+  }
+}
--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -28,16 +28,18 @@ const ANNOS_TO_TRACK = [BookmarkAnnos.DE
 const SERVICE_NOT_SUPPORTED = "Service not supported on this platform";
 const FOLDER_SORTINDEX = 1000000;
 const {
   SOURCE_SYNC,
   SOURCE_IMPORT,
   SOURCE_IMPORT_REPLACE,
 } = Ci.nsINavBookmarksService;
 
+const SQLITE_MAX_VARIABLE_NUMBER = 999;
+
 // Maps Sync record property names to `PlacesSyncUtils` bookmark properties.
 const RECORD_PROPS_TO_BOOKMARK_PROPS = {
   title: "title",
   bmkUri: "url",
   tags: "tags",
   keyword: "keyword",
   description: "description",
   loadInSidebar: "loadInSidebar",
@@ -421,17 +423,103 @@ BookmarksEngine.prototype = {
       this._log.trace(item.id + " already a dupe: not finding one.");
       return;
     }
     let mapped = this._mapDupe(item);
     this._log.debug(item.id + " mapped to " + mapped);
     // We must return a string, not an object, and the entries in the GUIDMap
     // are created via "new String()" making them an object.
     return mapped ? mapped.toString() : mapped;
-  }
+  },
+
+  pullAllChanges() {
+    let changeset = new BookmarksChangeset();
+    for (let id in this._store.getAllIDs()) {
+      changeset.set(id, { modified: 0, deleted: false });
+    }
+    return changeset;
+  },
+
+  pullNewChanges() {
+    let modifiedGUIDs = this._getModifiedGUIDs();
+    if (!modifiedGUIDs.length) {
+      return new BookmarksChangeset(this._tracker.changedIDs);
+    }
+
+    // We don't use `PlacesUtils.promiseDBConnection` here because
+    // `getChangedIDs` might be called while we're in a batch, meaning we
+    // won't see any changes until the batch finishes and the transaction
+    // commits.
+    let db = PlacesUtils.history.QueryInterface(Ci.nsPIPlacesDatabase)
+                        .DBConnection;
+
+    // Filter out tags, organizer queries, and other descendants that we're
+    // not tracking. We chunk `modifiedGUIDs` because SQLite limits the number
+    // of bound parameters per query.
+    for (let startIndex = 0;
+         startIndex < modifiedGUIDs.length;
+         startIndex += SQLITE_MAX_VARIABLE_NUMBER) {
+
+      let chunkLength = Math.min(startIndex + SQLITE_MAX_VARIABLE_NUMBER,
+                                 modifiedGUIDs.length);
+
+      let query = `
+        WITH RECURSIVE
+        modifiedGuids(guid) AS (
+          VALUES ${new Array(chunkLength).fill("(?)").join(", ")}
+        ),
+        syncedItems(id) AS (
+          SELECT b.id
+          FROM moz_bookmarks b
+          WHERE b.id IN (${getChangeRootIds().join(", ")})
+          UNION ALL
+          SELECT b.id
+          FROM moz_bookmarks b
+          JOIN syncedItems s ON b.parent = s.id
+        )
+        SELECT b.guid, b.id
+        FROM modifiedGuids m
+        JOIN moz_bookmarks b ON b.guid = m.guid
+        LEFT JOIN syncedItems s ON b.id = s.id
+        WHERE s.id IS NULL
+      `;
+
+      let statement = db.createAsyncStatement(query);
+      try {
+        for (let i = 0; i < chunkLength; i++) {
+          statement.bindByIndex(i, modifiedGUIDs[startIndex + i]);
+        }
+        let results = Async.querySpinningly(statement, ["id", "guid"]);
+        for (let { id, guid } of results) {
+          let syncID = BookmarkSpecialIds.specialGUIDForId(id) || guid;
+          this._tracker.removeChangedID(syncID);
+        }
+      } finally {
+        statement.finalize();
+      }
+    }
+
+    return new BookmarksChangeset(this._tracker.changedIDs);
+  },
+
+  // Returns an array of Places GUIDs for all changed items. Ignores deletions,
+  // which won't exist in the DB and shouldn't be removed from the tracker.
+  _getModifiedGUIDs() {
+    let guids = [];
+    for (let syncID in this._tracker.changedIDs) {
+      if (this._tracker.changedIDs[syncID].deleted === true) {
+        // The `===` check also filters out old persisted timestamps,
+        // which won't have a `deleted` property.
+        continue;
+      }
+      let guid = BookmarkSpecialIds.syncIDToPlacesGUID(syncID);
+      guids.push(guid);
+    }
+    return guids;
+  },
 };
 
 function BookmarksStore(name, engine) {
   Store.call(this, name, engine);
 
   // Explicitly nullify our references to our cached services so we don't leak
   Svc.Obs.add("places-shutdown", function() {
     for (let query in this._stmts) {
@@ -959,107 +1047,130 @@ BookmarksTracker.prototype = {
   },
 
   QueryInterface: XPCOMUtils.generateQI([
     Ci.nsINavBookmarkObserver,
     Ci.nsINavBookmarkObserver_MOZILLA_1_9_1_ADDITIONS,
     Ci.nsISupportsWeakReference
   ]),
 
+  addChangedID(id, change) {
+    if (!id) {
+      this._log.warn("Attempted to add undefined ID to tracker");
+      return false;
+    }
+    if (this._ignored.includes(id)) {
+      return false;
+    }
+    let shouldSaveChange = false;
+    let currentChange = this.changedIDs[id];
+    if (currentChange) {
+      if (typeof currentChange == "number") {
+        // Allow raw timestamps for backward-compatibility with persisted
+        // changed IDs. The new format uses tuples to track deleted items.
+        shouldSaveChange = currentChange < change.modified;
+      } else {
+        shouldSaveChange = currentChange.modified < change.modified ||
+                           currentChange.deleted != change.deleted;
+      }
+    } else {
+      shouldSaveChange = true;
+    }
+    if (shouldSaveChange) {
+      this._saveChangedID(id, change);
+    }
+    return true;
+  },
+
   /**
    * Add a bookmark GUID to be uploaded and bump up the sync score.
    *
-   * @param itemGuid
-   *        GUID of the bookmark to upload.
+   * @param itemId
+   *        The Places item ID of the bookmark to upload.
+   * @param guid
+   *        The Places GUID of the bookmark to upload.
+   * @param isTombstone
+   *        Whether we're uploading a tombstone for a removed bookmark.
    */
-  _add: function BMT__add(itemId, guid) {
+  _add: function BMT__add(itemId, guid, isTombstone = false) {
     guid = BookmarkSpecialIds.specialGUIDForId(itemId) || guid;
-    if (this.addChangedID(guid))
+    let info = { modified: Date.now() / 1000, deleted: isTombstone };
+    if (this.addChangedID(guid, info)) {
       this._upScore();
+    }
   },
 
   /* Every add/remove/change will trigger a sync for MULTI_DEVICE (except in
      a batch operation, where we do it at the end of the batch) */
   _upScore: function BMT__upScore() {
     if (this._batchDepth == 0) {
       this.score += SCORE_INCREMENT_XLARGE;
     } else {
       this._batchSawScoreIncrement = true;
     }
   },
 
-  /**
-   * Determine if a change should be ignored.
-   *
-   * @param itemId
-   *        Item under consideration to ignore
-   * @param folder (optional)
-   *        Folder of the item being changed
-   * @param guid
-   *        Places GUID of the item being changed
-   * @param source
-   *        A change source constant from `nsINavBookmarksService::SOURCE_*`.
-   */
-  _ignore: function BMT__ignore(itemId, folder, guid, source) {
-    if (IGNORED_SOURCES.includes(source)) {
-      return true;
-    }
-
-    // Get the folder id if we weren't given one.
-    if (folder == null) {
-      try {
-        folder = PlacesUtils.bookmarks.getFolderIdForItem(itemId);
-      } catch (ex) {
-        this._log.debug("getFolderIdForItem(" + itemId +
-                        ") threw; calling _ensureMobileQuery.");
-        // I'm guessing that gFIFI can throw, and perhaps that's why
-        // _ensureMobileQuery is here at all. Try not to call it.
-        this._ensureMobileQuery();
-        folder = PlacesUtils.bookmarks.getFolderIdForItem(itemId);
-      }
-    }
-
-    // Ignore changes to tags (folders under the tags folder).
-    let tags = BookmarkSpecialIds.tags;
-    if (folder == tags)
-      return true;
-
-    // Ignore tag items (the actual instance of a tag for a bookmark).
-    if (PlacesUtils.bookmarks.getFolderIdForItem(folder) == tags)
-      return true;
-
-    // Make sure to remove items that have the exclude annotation.
-    if (PlacesUtils.annotations.itemHasAnnotation(itemId, BookmarkAnnos.EXCLUDEBACKUP_ANNO)) {
-      this.removeChangedID(guid);
-      return true;
-    }
-
-    return false;
-  },
-
   onItemAdded: function BMT_onItemAdded(itemId, folder, index,
                                         itemType, uri, title, dateAdded,
                                         guid, parentGuid, source) {
-    if (this._ignore(itemId, folder, guid, source)) {
+    if (IGNORED_SOURCES.includes(source)) {
       return;
     }
 
     this._log.trace("onItemAdded: " + itemId);
     this._add(itemId, guid);
     this._add(folder, parentGuid);
   },
 
   onItemRemoved: function (itemId, parentId, index, type, uri,
                            guid, parentGuid, source) {
-    if (this._ignore(itemId, parentId, guid, source)) {
+    if (IGNORED_SOURCES.includes(source)) {
+      return;
+    }
+
+    // Ignore changes to tags (folders under the tags folder).
+    if (parentId == PlacesUtils.tagsFolderId) {
+      return;
+    }
+
+    let grandParentId = -1;
+    try {
+      grandParentId = PlacesUtils.bookmarks.getFolderIdForItem(parentId);
+    } catch (ex) {
+      // `getFolderIdForItem` can throw if the item no longer exists, such as
+      // when we've removed a subtree using `removeFolderChildren`.
       return;
     }
 
+    // Ignore tag items (the actual instance of a tag for a bookmark).
+    if (grandParentId == PlacesUtils.tagsFolderId) {
+      return;
+    }
+
+    /**
+     * The above checks are incomplete: we can still write tombstones for
+     * items that we don't track, and upload extraneous roots.
+     *
+     * Consider the left pane root: it's a child of the Places root, and has
+     * children and grandchildren. `PlacesUIUtils` can create, delete, and
+     * recreate it as needed. We can't determine ancestors when the root or its
+     * children are deleted, because they've already been removed from the
+     * database when `onItemRemoved` is called. Likewise, we can't check their
+     * "exclude from backup" annos, because they've *also* been removed.
+     *
+     * So, we end up writing tombstones for the left pane queries and left
+     * pane root. For good measure, we'll also upload the Places root, because
+     * it's the parent of the left pane root.
+     *
+     * As a workaround, we can track the parent GUID and reconstruct the item's
+     * ancestry at sync time. This is complicated, and the previous behavior was
+     * already wrong, so we'll wait for bug 1258127 to fix this generally.
+     */
     this._log.trace("onItemRemoved: " + itemId);
-    this._add(itemId, guid);
+    this._add(itemId, guid, /* isTombstone */ true);
     this._add(parentId, parentGuid);
   },
 
   _ensureMobileQuery: function _ensureMobileQuery() {
     let find = val =>
       PlacesUtils.annotations.getItemsWithAnnotation(BookmarkAnnos.ORGANIZERQUERY_ANNO, {}).filter(
         id => PlacesUtils.annotations.getItemAnnotation(id, BookmarkAnnos.ORGANIZERQUERY_ANNO) == val
       );
@@ -1093,39 +1204,39 @@ BookmarksTracker.prototype = {
   },
 
   // This method is oddly structured, but the idea is to return as quickly as
   // possible -- this handler gets called *every time* a bookmark changes, for
   // *each change*.
   onItemChanged: function BMT_onItemChanged(itemId, property, isAnno, value,
                                             lastModified, itemType, parentId,
                                             guid, parentGuid, source) {
+    if (IGNORED_SOURCES.includes(source)) {
+      return;
+    }
+
     if (isAnno && (ANNOS_TO_TRACK.indexOf(property) == -1))
       // Ignore annotations except for the ones that we sync.
       return;
 
     // Ignore favicon changes to avoid unnecessary churn.
     if (property == "favicon")
       return;
 
-    if (this._ignore(itemId, parentId, guid, source)) {
-      return;
-    }
-
     this._log.trace("onItemChanged: " + itemId +
                     (", " + property + (isAnno? " (anno)" : "")) +
                     (value ? (" = \"" + value + "\"") : ""));
     this._add(itemId, guid);
   },
 
   onItemMoved: function BMT_onItemMoved(itemId, oldParent, oldIndex,
                                         newParent, newIndex, itemType,
                                         guid, oldParentGuid, newParentGuid,
                                         source) {
-    if (this._ignore(itemId, newParent, guid, source)) {
+    if (IGNORED_SOURCES.includes(source)) {
       return;
     }
 
     this._log.trace("onItemMoved: " + itemId);
     this._add(oldParent, oldParentGuid);
     if (oldParent != newParent) {
       this._add(itemId, guid);
       this._add(newParent, newParentGuid);
@@ -1141,8 +1252,31 @@ BookmarksTracker.prototype = {
   onEndUpdateBatch: function () {
     if (--this._batchDepth === 0 && this._batchSawScoreIncrement) {
       this.score += SCORE_INCREMENT_XLARGE;
       this._batchSawScoreIncrement = false;
     }
   },
   onItemVisited: function () {}
 };
+
+// Returns an array of root IDs to recursively query for synced bookmarks.
+// Items in other roots, including tags and organizer queries, will be
+// ignored.
+function getChangeRootIds() {
+  let rootIds = [
+    PlacesUtils.bookmarksMenuFolderId,
+    PlacesUtils.toolbarFolderId,
+    PlacesUtils.unfiledBookmarksFolderId,
+  ];
+  let mobileRootId = BookmarkSpecialIds.findMobileRoot(false);
+  if (mobileRootId) {
+    rootIds.push(mobileRootId);
+  }
+  return rootIds;
+}
+
+class BookmarksChangeset extends Changeset {
+  getModifiedTimestamp(id) {
+    let change = this.changes[id];
+    return change ? change.modified : Number.NaN;
+  }
+}
--- a/services/sync/modules/engines/clients.js
+++ b/services/sync/modules/engines/clients.js
@@ -306,17 +306,17 @@ ClientEngine.prototype = {
     }
   },
 
   _uploadOutgoing() {
     this._currentlySyncingCommands = this._prepareCommandsForUpload();
     const clientWithPendingCommands = Object.keys(this._currentlySyncingCommands);
     for (let clientId of clientWithPendingCommands) {
       if (this._store._remoteClients[clientId] || this.localID == clientId) {
-        this._modified[clientId] = 0;
+        this._modified.set(clientId, 0);
       }
     }
     SyncEngine.prototype._uploadOutgoing.call(this);
   },
 
   _onRecordsWritten(succeeded, failed) {
     // Reconcile the status of the local records with what we just wrote on the
     // server
--- a/services/sync/tests/unit/test_bookmark_tracker.js
+++ b/services/sync/tests/unit/test_bookmark_tracker.js
@@ -17,18 +17,19 @@ var tracker = engine._tracker;
 
 store.wipe();
 tracker.persistChangedIDs = false;
 
 const DAY_IN_MS = 24 * 60 * 60 * 1000;
 
 // Test helpers.
 function* verifyTrackerEmpty() {
-  do_check_empty(tracker.changedIDs);
-  do_check_eq(tracker.score, 0);
+  let changes = engine.pullNewChanges();
+  equal(changes.count(), 0);
+  equal(tracker.score, 0);
 }
 
 function* resetTracker() {
   tracker.clearChangedIDs();
   tracker.resetScore();
 }
 
 function* cleanup() {
@@ -43,27 +44,31 @@ function* startTracking() {
   Svc.Obs.notify("weave:engine:start-tracking");
 }
 
 function* stopTracking() {
   Svc.Obs.notify("weave:engine:stop-tracking");
 }
 
 function* verifyTrackedItems(tracked) {
-  let trackedIDs = new Set(Object.keys(tracker.changedIDs));
+  let changes = engine.pullNewChanges();
+  let trackedIDs = new Set(changes.ids());
   for (let guid of tracked) {
-    ok(tracker.changedIDs[guid] > 0, `${guid} should be tracked`);
+    ok(changes.has(guid), `${guid} should be tracked`);
+    ok(changes.getModifiedTimestamp(guid) > 0,
+      `${guid} should have a modified time`);
     trackedIDs.delete(guid);
   }
   equal(trackedIDs.size, 0, `Unhandled tracked IDs: ${
     JSON.stringify(Array.from(trackedIDs))}`);
 }
 
 function* verifyTrackedCount(expected) {
-  do_check_attribute_count(tracker.changedIDs, expected);
+  let changes = engine.pullNewChanges();
+  equal(changes.count(), expected);
 }
 
 add_task(function* test_tracking() {
   _("Test starting and stopping the tracker");
 
   let folder = PlacesUtils.bookmarks.createFolder(
     PlacesUtils.bookmarks.bookmarksMenuFolder,
     "Test Folder", PlacesUtils.bookmarks.DEFAULT_INDEX);
@@ -384,17 +389,17 @@ add_task(function* test_onItemTagged() {
 
     yield startTracking();
 
     _("Tag the item");
     PlacesUtils.tagging.tagURI(uri, ["foo"]);
 
     // bookmark should be tracked, folder should not be.
     yield verifyTrackedItems([bGUID]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 5);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onItemUntagged() {
   _("Items untagged using the synchronous API should be tracked");
@@ -517,17 +522,17 @@ add_task(function* test_async_onItemTagg
     _("Tag an item using the async bookmarks API");
     yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
       parentGuid: tag.guid,
       url: "http://getfirefox.com",
     });
 
     yield verifyTrackedItems([fxBmk1.guid, fxBmk2.guid]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 2);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onItemKeywordChanged() {
   _("Keyword changes via the synchronous API should be tracked");
@@ -695,41 +700,83 @@ add_task(function* test_onItemAnnoChange
     yield verifyTrackedItems([bGUID]);
     do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
-add_task(function* test_onItemExcluded() {
-  _("Items excluded from backups should not be tracked");
+add_task(function* test_onItemAdded_filtered_root() {
+  _("Items outside the change roots should not be tracked");
+
+  try {
+    yield startTracking();
+
+    _("Create a new root");
+    let rootID = PlacesUtils.bookmarks.createFolder(
+      PlacesUtils.bookmarks.placesRoot,
+      "New root",
+      PlacesUtils.bookmarks.DEFAULT_INDEX);
+    let rootGUID = engine._store.GUIDForId(rootID);
+    _(`New root GUID: ${rootGUID}`);
+
+    _("Insert a bookmark underneath the new root");
+    let untrackedBmkID = PlacesUtils.bookmarks.insertBookmark(
+      rootID,
+      Utils.makeURI("http://getthunderbird.com"),
+      PlacesUtils.bookmarks.DEFAULT_INDEX,
+      "Get Thunderbird!");
+    let untrackedBmkGUID = engine._store.GUIDForId(untrackedBmkID);
+    _(`New untracked bookmark GUID: ${untrackedBmkGUID}`);
+
+    _("Insert a bookmark underneath the Places root");
+    let rootBmkID = PlacesUtils.bookmarks.insertBookmark(
+      PlacesUtils.bookmarks.placesRoot,
+      Utils.makeURI("http://getfirefox.com"),
+      PlacesUtils.bookmarks.DEFAULT_INDEX, "Get Firefox!");
+    let rootBmkGUID = engine._store.GUIDForId(rootBmkID);
+    _(`New Places root bookmark GUID: ${rootBmkGUID}`);
+
+    _("New root and bookmark should be ignored");
+    yield verifyTrackedItems([]);
+    // ...But we'll still increment the score and filter out the changes at
+    // sync time.
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
+  } finally {
+    _("Clean up.");
+    yield cleanup();
+  }
+});
+
+add_task(function* test_onItemDeleted_filtered_root() {
+  _("Deleted items outside the change roots should be tracked");
 
   try {
     yield stopTracking();
 
-    _("Create a bookmark");
-    let b = PlacesUtils.bookmarks.insertBookmark(
-      PlacesUtils.bookmarks.bookmarksMenuFolder,
+    _("Insert a bookmark underneath the Places root");
+    let rootBmkID = PlacesUtils.bookmarks.insertBookmark(
+      PlacesUtils.bookmarks.placesRoot,
       Utils.makeURI("http://getfirefox.com"),
       PlacesUtils.bookmarks.DEFAULT_INDEX, "Get Firefox!");
-    let bGUID = engine._store.GUIDForId(b);
+    let rootBmkGUID = engine._store.GUIDForId(rootBmkID);
+    _(`New Places root bookmark GUID: ${rootBmkGUID}`);
 
     yield startTracking();
 
-    _("Exclude the bookmark from backups");
-    PlacesUtils.annotations.setItemAnnotation(
-      b, BookmarkAnnos.EXCLUDEBACKUP_ANNO, "Don't back this up", 0,
-      PlacesUtils.annotations.EXPIRE_NEVER);
+    PlacesUtils.bookmarks.removeItem(rootBmkID);
 
-    _("Modify the bookmark");
-    PlacesUtils.bookmarks.setItemTitle(b, "Download Firefox");
-
-    _("Excluded items should be ignored");
-    yield verifyTrackerEmpty();
+    // We shouldn't upload tombstones for items in filtered roots, but the
+    // `onItemRemoved` observer doesn't have enough context to determine
+    // the root, so we'll end up uploading it.
+    yield verifyTrackedItems([rootBmkGUID]);
+    // We'll increment the counter twice (once for the removed item, and once
+    // for the Places root), then filter out the root.
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 2);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onPageAnnoChanged() {
   _("Page annotations should not be tracked");
@@ -1249,32 +1296,53 @@ add_task(function* test_async_onItemDele
     });
     _(`Mozilla GUID: ${mozBmk.guid}`);
     let mdnBmk = yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
       parentGuid: PlacesUtils.bookmarks.menuGuid,
       url: "https://developer.mozilla.org",
       title: "MDN",
     });
+    _(`MDN GUID: ${mdnBmk.guid}`);
     let bugsFolder = yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_FOLDER,
       parentGuid: PlacesUtils.bookmarks.toolbarGuid,
       title: "Bugs",
     });
+    _(`Bugs folder GUID: ${bugsFolder.guid}`);
     let bzBmk = yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
       parentGuid: bugsFolder.guid,
       url: "https://bugzilla.mozilla.org",
       title: "Bugzilla",
     });
+    _(`Bugzilla GUID: ${bzBmk.guid}`);
+    let bugsChildFolder = yield PlacesUtils.bookmarks.insert({
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      parentGuid: bugsFolder.guid,
+      title: "Bugs child",
+    });
+    _(`Bugs child GUID: ${bugsChildFolder.guid}`);
+    let bugsGrandChildBmk = yield PlacesUtils.bookmarks.insert({
+      type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+      parentGuid: bugsChildFolder.guid,
+      url: "https://example.com",
+      title: "Bugs grandchild",
+    });
+    _(`Bugs grandchild GUID: ${bugsGrandChildBmk.guid}`);
 
     yield startTracking();
 
     yield PlacesUtils.bookmarks.eraseEverything();
 
+    // `eraseEverything` removes all items from the database before notifying
+    // observers. Because of this, grandchild lookup in the tracker's
+    // `onItemRemoved` observer will fail. That means we won't track
+    // (bzBmk.guid, bugsGrandChildBmk.guid, bugsChildFolder.guid), even
+    // though we should.
     yield verifyTrackedItems(["menu", mozBmk.guid, mdnBmk.guid, "toolbar",
                               bugsFolder.guid]);
     do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });