Bug 1454864 - Improve merging of non-syncable items in the bookmarks mirror. r=markh,tcsc
authorKit Cambridge <kit@yakshaving.ninja>
Fri, 27 Apr 2018 09:38:31 -0700
changeset 472920 6cc5d9e64f7b733e47771753ffbbb405b18a1e46
parent 472919 c470f035fe635060d93fd483d553eee462fed99b
child 472921 56e5751b3a4d46fc37a03cd3c18daf354f5d57b1
push id1728
push userjlund@mozilla.com
push dateMon, 18 Jun 2018 21:12:27 +0000
treeherdermozilla-release@c296fde26f5f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmarkh, tcsc
bugs1454864
milestone61.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 1454864 - Improve merging of non-syncable items in the bookmarks mirror. r=markh,tcsc This commit changes `fetchLocalTree` to include all items in Places, syncable and non-syncable. The four user content roots, and all nodes that descend from them, are syncable. Everything else is not. When we check for structure changes of a local or remote node on the other side, we also check if the node is syncable on both sides. If the node is not syncable, on either side, we flag it for deletion. If the non-syncable item is a child of a syncable parent (for example, an orphaned left pane query), we set the parent's merge state to "new", just like for local deletions, which flags the parent for reupload on the next sync. Uploading tombstones for non-syncable items is handled in the next commit. MozReview-Commit-ID: B9HzycuneND
toolkit/components/places/SyncedBookmarksMirror.jsm
toolkit/components/places/tests/sync/head_sync.js
toolkit/components/places/tests/sync/test_bookmark_corruption.js
--- a/toolkit/components/places/SyncedBookmarksMirror.jsm
+++ b/toolkit/components/places/SyncedBookmarksMirror.jsm
@@ -66,19 +66,53 @@ XPCOMUtils.defineLazyModuleGetters(this,
   PlacesUtils: "resource://gre/modules/PlacesUtils.jsm",
   Sqlite: "resource://gre/modules/Sqlite.jsm",
 });
 
 XPCOMUtils.defineLazyGetter(this, "MirrorLog", () =>
   Log.repository.getLogger("Sync.Engine.Bookmarks.Mirror")
 );
 
-XPCOMUtils.defineLazyGetter(this, "UserContentRootsAsSqlList", () =>
-  PlacesUtils.bookmarks.userContentRoots.map(v => `'${v}'`).join(",")
-);
+/**
+ * A common table expression for all local items in Places, to be included in a
+ * `WITH RECURSIVE` clause. We start at the roots, excluding tags (bug 424160),
+ * and work our way down.
+ *
+ * Note that syncable items (`isSyncable`) descend from the four syncable roots.
+ * Any other roots and their descendants, like the left pane root, left pane
+ * queries, and custom roots, are non-syncable.
+ *
+ * Newer Desktops should never reupload non-syncable items (bug 1274496), and
+ * should have removed them in Places migrations (bug 1310295). However, these
+ * items might be orphaned in "unfiled", in which case they're seen as syncable
+ * locally. If the server has the missing parents and roots, we'll determine
+ * that the items are non-syncable when merging, remove them from Places, and
+ * upload tombstones to the server.
+ */
+XPCOMUtils.defineLazyGetter(this, "LocalItemsSQLFragment", () => `
+  localItems(id, guid, parentId, parentGuid, position, type, title,
+             parentTitle, placeId, dateAdded, lastModified, syncChangeCounter,
+             isSyncable, level) AS (
+    SELECT b.id, b.guid, p.id, p.guid, b.position, b.type, b.title, p.title,
+           b.fk, b.dateAdded, b.lastModified, b.syncChangeCounter,
+           b.guid IN (${PlacesUtils.bookmarks.userContentRoots.map(v =>
+             `'${v}'`
+           ).join(",")}), 0
+    FROM moz_bookmarks b
+    JOIN moz_bookmarks p ON p.id = b.parent
+    WHERE b.guid <> '${PlacesUtils.bookmarks.tagsGuid}' AND
+          p.guid = '${PlacesUtils.bookmarks.rootGuid}'
+    UNION ALL
+    SELECT b.id, b.guid, s.id, s.guid, b.position, b.type, b.title, s.title,
+           b.fk, b.dateAdded, b.lastModified, b.syncChangeCounter,
+           s.isSyncable, s.level + 1
+    FROM moz_bookmarks b
+    JOIN localItems s ON s.id = b.parent
+  )
+`);
 
 // These can be removed once they're exposed in a central location (bug
 // 1375896).
 const DB_URL_LENGTH_MAX = 65536;
 const DB_TITLE_LENGTH_MAX = 4096;
 const DB_DESCRIPTION_LENGTH_MAX = 256;
 
 const SQLITE_MAX_VARIABLE_NUMBER = 999;
@@ -579,17 +613,17 @@ class SyncedBookmarksMirror {
 
       await this.db.execute(`DELETE FROM mergeStates`);
       await this.db.execute(`DELETE FROM itemsAdded`);
       await this.db.execute(`DELETE FROM guidsChanged`);
       await this.db.execute(`DELETE FROM itemsChanged`);
       await this.db.execute(`DELETE FROM itemsRemoved`);
       await this.db.execute(`DELETE FROM itemsMoved`);
       await this.db.execute(`DELETE FROM annosChanged`);
-      await this.db.execute(`DELETE FROM itemsToWeaklyReupload`);
+      await this.db.execute(`DELETE FROM idsToWeaklyUpload`);
       await this.db.execute(`DELETE FROM itemsToUpload`);
 
       return changeRecords;
     });
 
     MirrorLog.debug("Replaying recorded observer notifications");
     try {
       await observersToNotify.notifyAll();
@@ -1018,25 +1052,19 @@ class SyncedBookmarksMirror {
       EXISTS (
        SELECT 1
        FROM items v
        LEFT JOIN moz_bookmarks b ON v.guid = b.guid
        WHERE v.needsMerge AND
        (NOT v.isDeleted OR b.guid NOT NULL)
       ) OR EXISTS (
        WITH RECURSIVE
-       syncedItems(id, syncChangeCounter) AS (
-         SELECT b.id, b.syncChangeCounter FROM moz_bookmarks b
-         WHERE b.guid IN (${UserContentRootsAsSqlList})
-         UNION ALL
-         SELECT b.id, b.syncChangeCounter FROM moz_bookmarks b
-         JOIN syncedItems s ON b.parent = s.id
-       )
+       ${LocalItemsSQLFragment}
        SELECT 1
-       FROM syncedItems
+       FROM localItems
        WHERE syncChangeCounter > 0
       ) OR EXISTS (
        SELECT 1
        FROM moz_bookmarks_deleted
       )
       AS hasChanges
     `);
     return !!rows[0].getResultByName("hasChanges");
@@ -1154,54 +1182,42 @@ class SyncedBookmarksMirror {
    * @param  {Number} localTimeSeconds
    *         The current local time, in seconds.
    * @return {BookmarkTree}
    *         The local bookmark tree.
    */
   async fetchLocalTree(localTimeSeconds) {
     let localTree = new BookmarkTree(BookmarkNode.root());
 
-    // This unsightly query collects all descendants and maps their Places types
-    // to the Sync record kinds. We start with the roots, and work our way down.
-    // The list of roots in `syncedItems` should be updated if we add new
-    // syncable roots to Places.
     let itemRows = await this.db.execute(`
       WITH RECURSIVE
-      syncedItems(id, level) AS (
-        SELECT b.id, 0 AS level FROM moz_bookmarks b
-        WHERE b.guid IN (${UserContentRootsAsSqlList})
-        UNION ALL
-        SELECT b.id, s.level + 1 AS level FROM moz_bookmarks b
-        JOIN syncedItems s ON s.id = b.parent
-      )
-      SELECT b.id, b.guid, p.guid AS parentGuid,
+      ${LocalItemsSQLFragment}
+      SELECT s.id, s.guid, s.parentGuid,
              /* Map Places item types to Sync record kinds. */
-             (CASE b.type
+             (CASE s.type
                 WHEN :bookmarkType THEN (
                   CASE SUBSTR((SELECT h.url FROM moz_places h
-                               WHERE h.id = b.fk), 1, 6)
+                               WHERE h.id = s.placeId), 1, 6)
                   /* Queries are bookmarks with a "place:" URL scheme. */
                   WHEN 'place:' THEN :queryKind
                   ELSE :bookmarkKind END)
                 WHEN :folderType THEN (
                   CASE WHEN EXISTS(
                     /* Livemarks are folders with a feed URL annotation. */
                     SELECT 1 FROM moz_items_annos a
                     JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
-                    WHERE a.item_id = b.id AND
+                    WHERE a.item_id = s.id AND
                           n.name = :feedURLAnno
                   ) THEN :livemarkKind
                   ELSE :folderKind END)
                 ELSE :separatorKind END) AS kind,
-             b.lastModified / 1000 AS localModified, b.syncChangeCounter,
-             s.level
-      FROM moz_bookmarks b
-      JOIN moz_bookmarks p ON p.id = b.parent
-      JOIN syncedItems s ON s.id = b.id
-      ORDER BY s.level, b.parent, b.position`,
+             s.lastModified / 1000 AS localModified, s.syncChangeCounter,
+             s.level, s.isSyncable
+      FROM localItems s
+      ORDER BY s.level, s.parentId, s.position`,
       { bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK,
         queryKind: SyncedBookmarksMirror.KIND.QUERY,
         bookmarkKind: SyncedBookmarksMirror.KIND.BOOKMARK,
         folderType: PlacesUtils.bookmarks.TYPE_FOLDER,
         feedURLAnno: PlacesUtils.LMANNO_FEEDURI,
         livemarkKind: SyncedBookmarksMirror.KIND.LIVEMARK,
         folderKind: SyncedBookmarksMirror.KIND.FOLDER,
         separatorKind: SyncedBookmarksMirror.KIND.SEPARATOR });
@@ -1581,94 +1597,86 @@ class SyncedBookmarksMirror {
    * @param  {String[]} weakUpload
    *         GUIDs of bookmarks to weakly upload.
    */
   async stageItemsToUpload(weakUpload) {
     // Stage explicit weak uploads such as repair responses.
     for (let chunk of PlacesSyncUtils.chunkArray(weakUpload,
       SQLITE_MAX_VARIABLE_NUMBER)) {
       await this.db.execute(`
-        INSERT INTO itemsToWeaklyReupload(id)
+        INSERT INTO idsToWeaklyUpload(id)
         SELECT b.id FROM moz_bookmarks b
         WHERE b.guid IN (${new Array(chunk.length).fill("?").join(",")})`,
         chunk);
     }
 
     // Stage remotely changed items with older local creation dates. These are
     // tracked "weakly": if the upload is interrupted or fails, we won't
     // reupload the record on the next sync.
     await this.db.execute(`
-      INSERT OR IGNORE INTO itemsToWeaklyReupload(id)
+      INSERT OR IGNORE INTO idsToWeaklyUpload(id)
       SELECT b.id FROM moz_bookmarks b
       JOIN mergeStates r ON r.mergedGuid = b.guid
       JOIN items v ON v.guid = r.mergedGuid
       WHERE r.valueState = :valueState AND
             /* "b.dateAdded" is in microseconds; "v.dateAdded" is in
                milliseconds. */
             b.dateAdded / 1000 < v.dateAdded`,
       { valueState: BookmarkMergeState.TYPE.REMOTE });
 
     // Stage remaining locally changed items for upload.
     await this.db.execute(`
       WITH RECURSIVE
-      syncedItems(id, level) AS (
-        SELECT b.id, 0 AS level FROM moz_bookmarks b
-        WHERE b.guid IN (${UserContentRootsAsSqlList})
-        UNION ALL
-        SELECT b.id, s.level + 1 AS level FROM moz_bookmarks b
-        JOIN syncedItems s ON s.id = b.parent
-      )
+      ${LocalItemsSQLFragment}
       INSERT INTO itemsToUpload(id, guid, syncChangeCounter, parentGuid,
                                 parentTitle, dateAdded, type, title, isQuery,
                                 url, tags, description, loadInSidebar,
                                 smartBookmarkName, keyword, feedURL, siteURL,
                                 position, tagFolderName)
-      SELECT b.id, b.guid, b.syncChangeCounter, p.guid, p.title,
-             b.dateAdded / 1000, b.type, b.title,
+      SELECT s.id, s.guid, s.syncChangeCounter, s.parentGuid, s.parentTitle,
+             s.dateAdded / 1000, s.type, s.title,
              IFNULL(SUBSTR(h.url, 1, 6) = 'place:', 0) AS isQuery,
              h.url,
              (SELECT GROUP_CONCAT(t.title, ',') FROM moz_bookmarks e
               JOIN moz_bookmarks t ON t.id = e.parent
               JOIN moz_bookmarks r ON r.id = t.parent
-              WHERE b.type = :bookmarkType AND
+              WHERE s.type = :bookmarkType AND
                     r.guid = :tagsGuid AND
                     e.fk = h.id),
              (SELECT a.content FROM moz_items_annos a
               JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
-              WHERE b.type IN (:bookmarkType, :folderType) AND
-                    a.item_id = b.id AND
+              WHERE s.type IN (:bookmarkType, :folderType) AND
+                    a.item_id = s.id AND
                     n.name = :descriptionAnno),
              IFNULL((SELECT a.content FROM moz_items_annos a
                      JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
-                     WHERE a.item_id = b.id AND
+                     WHERE a.item_id = s.id AND
                            n.name = :sidebarAnno), 0),
              (SELECT a.content FROM moz_items_annos a
               JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
-              WHERE a.item_id = b.id AND
+              WHERE a.item_id = s.id AND
                     n.name = :smartBookmarkAnno),
              (SELECT keyword FROM moz_keywords WHERE place_id = h.id),
              (SELECT a.content FROM moz_items_annos a
               JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
-              WHERE b.type = :folderType AND
-                    a.item_id = b.id AND
+              WHERE s.type = :folderType AND
+                    a.item_id = s.id AND
                     n.name = :feedURLAnno),
              (SELECT a.content FROM moz_items_annos a
               JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
-              WHERE b.type = :folderType AND
-                    a.item_id = b.id AND
+              WHERE s.type = :folderType AND
+                    a.item_id = s.id AND
                     n.name = :siteURLAnno),
-             b.position,
+             s.position,
              (SELECT get_query_param(substr(url, 7), 'tag')
               WHERE substr(h.url, 1, 6) = 'place:')
-      FROM moz_bookmarks b
-      JOIN moz_bookmarks p ON p.id = b.parent
-      JOIN syncedItems s ON s.id = b.id
-      LEFT JOIN moz_places h ON h.id = b.fk
-      LEFT JOIN itemsToWeaklyReupload w ON w.id = b.id
-      WHERE b.syncChangeCounter >= 1 OR
+      FROM localItems s
+      LEFT JOIN moz_places h ON h.id = s.placeId
+      LEFT JOIN idsToWeaklyUpload w ON w.id = s.id
+      WHERE s.syncChangeCounter >= 1 OR
             w.id NOT NULL`,
       { bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK,
         tagsGuid: PlacesUtils.bookmarks.tagsGuid,
         descriptionAnno: PlacesSyncUtils.bookmarks.DESCRIPTION_ANNO,
         sidebarAnno: PlacesSyncUtils.bookmarks.SIDEBAR_ANNO,
         smartBookmarkAnno: PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO,
         folderType: PlacesUtils.bookmarks.TYPE_FOLDER,
         feedURLAnno: PlacesUtils.LMANNO_FEEDURI,
@@ -2666,17 +2674,20 @@ async function initializeTempMirrorEntit
   // observers.
   await db.execute(`CREATE TEMP TABLE annosChanged(
     itemId INTEGER NOT NULL,
     annoName TEXT NOT NULL,
     wasRemoved BOOLEAN NOT NULL,
     PRIMARY KEY(itemId, annoName, wasRemoved)
   ) WITHOUT ROWID`);
 
-  await db.execute(`CREATE TEMP TABLE itemsToWeaklyReupload(
+  // Stores local IDs for items to upload even if they're not flagged as changed
+  // in Places. These are "weak" because we won't try to reupload the item on
+  // the next sync if the upload is interrupted or fails.
+  await db.execute(`CREATE TEMP TABLE idsToWeaklyUpload(
     id INTEGER PRIMARY KEY
   )`);
 
   // Stores locally changed items staged for upload. See `stageItemsToUpload`
   // for an explanation of why these tables exists.
   await db.execute(`CREATE TEMP TABLE itemsToUpload(
     id INTEGER PRIMARY KEY,
     guid TEXT UNIQUE NOT NULL,
@@ -2787,16 +2798,23 @@ function validateTag(rawTag) {
 // Recursively inflates a bookmark tree from a pseudo-tree that maps
 // parents to children.
 async function inflateTree(tree, pseudoTree, parentNode) {
   let nodes = pseudoTree.get(parentNode.guid);
   if (nodes) {
     for (let node of nodes) {
       await maybeYield();
       node.level = parentNode.level + 1;
+      // See `LocalItemsSQLFragment` for a more detailed explanation about
+      // syncable and non-syncable items. Non-syncable items might be
+      // reuploaded by Android after a node reassignment, or orphaned on the
+      // server.
+      node.isSyncable = parentNode == tree.root ?
+        PlacesUtils.bookmarks.userContentRoots.includes(node.guid) :
+        parentNode.isSyncable;
       tree.insert(parentNode.guid, node);
       await inflateTree(tree, pseudoTree, node);
     }
   }
 }
 
 // Executes a function and returns a `{ result, time }` tuple, where `result` is
 // the function's return value, and `time` is the time taken to execute the
@@ -2967,22 +2985,24 @@ BookmarkMergeState.remote = new Bookmark
   BookmarkMergeState.TYPE.REMOTE);
 
 /**
  * A node in a local or remote bookmark tree. Nodes are lightweight: they carry
  * enough information for the merger to resolve trivial conflicts without
  * querying the mirror or Places for the complete value state.
  */
 class BookmarkNode {
-  constructor(guid, kind, { age = 0, needsMerge = false, level = 0 } = {}) {
+  constructor(guid, kind, { age = 0, needsMerge = false, level = 0,
+                            isSyncable = true } = {}) {
     this.guid = guid;
     this.kind = kind;
     this.age = age;
     this.needsMerge = needsMerge;
     this.level = level;
+    this.isSyncable = isSyncable;
     this.children = [];
   }
 
   // Creates a virtual folder node for the Places root.
   static root() {
     let guid = PlacesUtils.bookmarks.rootGuid;
     return new BookmarkNode(guid, SyncedBookmarksMirror.KIND.FOLDER);
   }
@@ -3003,21 +3023,22 @@ class BookmarkNode {
 
     // Note that this doesn't account for local clock skew. `localModified`
     // is in milliseconds.
     let localModified = row.getResultByName("localModified");
     let age = Math.max(localTimeSeconds - localModified / 1000, 0) || 0;
 
     let kind = row.getResultByName("kind");
     let level = row.getResultByName("level");
+    let isSyncable = !!row.getResultByName("isSyncable");
 
     let syncChangeCounter = row.getResultByName("syncChangeCounter");
     let needsMerge = syncChangeCounter > 0;
 
-    return new BookmarkNode(guid, kind, { age, needsMerge, level });
+    return new BookmarkNode(guid, kind, { age, needsMerge, level, isSyncable });
   }
 
   /**
    * Creates a bookmark node from a mirror row.
    *
    * @param  {mozIStorageRow} row
    *         The mirror row containing the node info.
    * @param  {Number} remoteTimeSeconds
@@ -3197,27 +3218,19 @@ class BookmarkTree {
     this.byGuid.set(node.guid, node);
     this.parentNodeByChildNode.set(node, parentNode);
   }
 
   noteDeleted(guid) {
     this.deletedGuids.add(guid);
   }
 
-  * syncableGuids() {
-    let nodesToWalk = PlacesUtils.bookmarks.userContentRoots.map(guid => {
-      let node = this.byGuid.get(guid);
-      return node ? node.children : [];
-    });
-    while (nodesToWalk.length) {
-      let childNodes = nodesToWalk.pop();
-      for (let node of childNodes) {
-        yield node.guid;
-        nodesToWalk.push(node.children);
-      }
+  * guids() {
+    for (let [guid] of this.byGuid) {
+      yield guid;
     }
     for (let guid of this.deletedGuids) {
       yield guid;
     }
   }
 
   /**
    * Generates an ASCII art representation of the complete tree.
@@ -3364,25 +3377,20 @@ class BookmarkMerger {
     let structureExtra = normalizeExtraTelemetryFields(this.structureCounts);
     if (structureExtra) {
       events.push({ value: "structure", extra: structureExtra });
     }
     return events;
   }
 
   async merge() {
-    let mergedRoot = new MergedBookmarkNode(PlacesUtils.bookmarks.rootGuid,
-      BookmarkNode.root(), null, BookmarkMergeState.local);
-    for (let guid of PlacesUtils.bookmarks.userContentRoots) {
-      let localSyncableRoot = this.localTree.nodeForGuid(guid);
-      let remoteSyncableRoot = this.remoteTree.nodeForGuid(guid);
-      let mergedSyncableRoot = await this.mergeNode(guid, localSyncableRoot,
-                                                    remoteSyncableRoot);
-      mergedRoot.mergedChildren.push(mergedSyncableRoot);
-    }
+    let localRoot = this.localTree.nodeForGuid(PlacesUtils.bookmarks.rootGuid);
+    let remoteRoot = this.remoteTree.nodeForGuid(PlacesUtils.bookmarks.rootGuid);
+    let mergedRoot = await this.mergeNode(PlacesUtils.bookmarks.rootGuid, localRoot,
+                                          remoteRoot);
 
     // Any remaining deletions on one side should be deleted on the other side.
     // This happens when the remote tree has tombstones for items that don't
     // exist in Places, or Places has tombstones for items that aren't on the
     // server.
     for await (let guid of yieldingIterator(this.localTree.deletedGuids)) {
       if (!this.mentions(guid)) {
         this.deleteRemotely.add(guid);
@@ -3392,17 +3400,17 @@ class BookmarkMerger {
       if (!this.mentions(guid)) {
         this.deleteLocally.add(guid);
       }
     }
     return mergedRoot;
   }
 
   async subsumes(tree) {
-    for await (let guid of yieldingIterator(tree.syncableGuids())) {
+    for await (let guid of yieldingIterator(tree.guids())) {
       if (!this.mentions(guid)) {
         return false;
       }
     }
     return true;
   }
 
   mentions(guid) {
@@ -4009,21 +4017,45 @@ class BookmarkMerger {
    *         The remote potentially deleted child node.
    * @return {BookmarkMerger.STRUCTURE}
    *         A structure change type: `UNCHANGED` if the remote node is not
    *         deleted or doesn't exist locally, `MOVED` if the node is moved
    *         locally, or `DELETED` if the node is deleted locally.
    */
   async checkForLocalStructureChangeOfRemoteNode(mergedNode, remoteParentNode,
                                                  remoteNode) {
+    if (!remoteNode.isSyncable) {
+      // If the remote node is known to be non-syncable, we unconditionally
+      // delete it from the server, even if it's syncable locally.
+      this.deleteRemotely.add(remoteNode.guid);
+      if (remoteNode.isFolder()) {
+        // If the remote node is a folder, we also need to walk its descendants
+        // and reparent any syncable descendants, and descendants that only
+        // exist remotely, to the merged node.
+        await this.relocateRemoteOrphansToMergedNode(mergedNode, remoteNode);
+      }
+      return BookmarkMerger.STRUCTURE.DELETED;
+    }
+
     if (!this.localTree.isDeleted(remoteNode.guid)) {
       let localNode = this.localTree.nodeForGuid(remoteNode.guid);
       if (!localNode) {
         return BookmarkMerger.STRUCTURE.UNCHANGED;
       }
+      if (!localNode.isSyncable) {
+        // The remote node is syncable, but the local node is non-syncable.
+        // This is unlikely now that Places no longer supports custom roots,
+        // but, for consistency, we unconditionally delete the node from the
+        // server.
+        this.deleteRemotely.add(remoteNode.guid);
+        if (remoteNode.isFolder()) {
+          await this.relocateRemoteOrphansToMergedNode(mergedNode, remoteNode);
+        }
+        return BookmarkMerger.STRUCTURE.DELETED;
+      }
       let localParentNode = this.localTree.parentNodeFor(localNode);
       if (!localParentNode) {
         // Should never happen. If a node in the local tree doesn't have a
         // parent, we built the tree incorrectly.
         throw new TypeError(
           "Can't check for structure changes without local parent");
       }
       if (localParentNode.guid != remoteParentNode.guid) {
@@ -4079,21 +4111,44 @@ class BookmarkMerger {
    *         The local potentially deleted child node.
    * @return {BookmarkMerger.STRUCTURE}
    *         A structure change type: `UNCHANGED` if the local node is not
    *         deleted or doesn't exist remotely, `MOVED` if the node is moved
    *         remotely, or `DELETED` if the node is deleted remotely.
    */
   async checkForRemoteStructureChangeOfLocalNode(mergedNode, localParentNode,
                                                  localNode) {
+    if (!localNode.isSyncable) {
+      // If the local node is known to be non-syncable, we unconditionally
+      // delete it from Places, even if it's syncable remotely. This is
+      // unlikely now that Places no longer supports custom roots.
+      this.deleteLocally.add(localNode.guid);
+      if (localNode.isFolder()) {
+        await this.relocateLocalOrphansToMergedNode(mergedNode, localNode);
+      }
+      return BookmarkMerger.STRUCTURE.DELETED;
+    }
+
     if (!this.remoteTree.isDeleted(localNode.guid)) {
       let remoteNode = this.remoteTree.nodeForGuid(localNode.guid);
       if (!remoteNode) {
         return BookmarkMerger.STRUCTURE.UNCHANGED;
       }
+      if (!remoteNode.isSyncable) {
+        // The local node is syncable, but the remote node is non-syncable.
+        // This can happen if we applied an orphaned left pane query in a
+        // previous sync, and later saw the left pane root on the server.
+        // Since we now have the complete subtree, we can remove the item from
+        // Places.
+        this.deleteLocally.add(localNode.guid);
+        if (remoteNode.isFolder()) {
+          await this.relocateLocalOrphansToMergedNode(mergedNode, localNode);
+        }
+        return BookmarkMerger.STRUCTURE.DELETED;
+      }
       let remoteParentNode = this.remoteTree.parentNodeFor(remoteNode);
       if (!remoteParentNode) {
         // Should never happen. If a node in the remote tree doesn't have a
         // parent, we built the tree incorrectly.
         throw new TypeError(
           "Can't check for structure changes without remote parent");
       }
       if (remoteParentNode.guid != localParentNode.guid) {
--- a/toolkit/components/places/tests/sync/head_sync.js
+++ b/toolkit/components/places/tests/sync/head_sync.js
@@ -41,16 +41,36 @@ function run_test() {
   for (let log of [bufLog, sqliteLog]) {
     log.addAppender(appender);
   }
 
   do_get_profile();
   run_next_test();
 }
 
+// A test helper to insert local roots directly into Places, since the public
+// bookmarks APIs no longer support custom roots.
+async function insertLocalRoot({ guid, title }) {
+  await PlacesUtils.withConnectionWrapper("insertLocalRoot",
+    async function(db) {
+      let dateAdded = PlacesUtils.toPRTime(new Date());
+      await db.execute(`
+        INSERT INTO moz_bookmarks(guid, type, parent, position, title,
+                                  dateAdded, lastModified)
+        VALUES(:guid, :type, (SELECT id FROM moz_bookmarks
+                              WHERE guid = :parentGuid),
+               (SELECT COUNT(*) FROM moz_bookmarks
+                WHERE parent = (SELECT id FROM moz_bookmarks
+                                WHERE guid = :parentGuid)),
+               :title, :dateAdded, :dateAdded)`,
+        { guid, type: PlacesUtils.bookmarks.TYPE_FOLDER,
+          parentGuid: PlacesUtils.bookmarks.rootGuid, title, dateAdded });
+  });
+}
+
 // Returns a `CryptoWrapper`-like object that wraps the Sync record cleartext.
 // This exists to avoid importing `record.js` from Sync.
 function makeRecord(cleartext) {
   return new Proxy({ cleartext }, {
     get(target, property, receiver) {
       if (property == "cleartext") {
         return target.cleartext;
       }
@@ -85,16 +105,35 @@ function inspectChangeRecords(changeReco
   for (let [id, record] of Object.entries(changeRecords)) {
     (record.tombstone ? results.deleted : results.updated).push(id);
   }
   results.updated.sort();
   results.deleted.sort();
   return results;
 }
 
+async function promiseManyDatesAdded(guids) {
+  let datesAdded = new Map();
+  let db = await PlacesUtils.promiseDBConnection();
+  for (let chunk of PlacesSyncUtils.chunkArray(guids, 100)) {
+    let rows = await db.executeCached(`
+      SELECT guid, dateAdded FROM moz_bookmarks
+      WHERE guid IN (${new Array(chunk.length).fill("?").join(",")})`,
+      chunk);
+    if (rows.length != chunk.length) {
+      throw new TypeError("Can't fetch date added for nonexistent items");
+    }
+    for (let row of rows) {
+      let dateAdded = row.getResultByName("dateAdded") / 1000;
+      datesAdded.set(row.getResultByName("guid"), dateAdded);
+    }
+  }
+  return datesAdded;
+}
+
 async function fetchLocalTree(rootGuid) {
   function bookmarkNodeToInfo(node) {
     let { guid, index, title, typeCode: type } = node;
     let itemInfo = { guid, index, title, type };
     if (node.annos) {
       let syncableAnnos = node.annos.filter(anno => [
         PlacesSyncUtils.bookmarks.DESCRIPTION_ANNO,
         PlacesSyncUtils.bookmarks.SIDEBAR_ANNO,
--- a/toolkit/components/places/tests/sync/test_bookmark_corruption.js
+++ b/toolkit/components/places/tests/sync/test_bookmark_corruption.js
@@ -982,16 +982,271 @@ add_task(async function test_tombstone_a
       title: MobileBookmarksTitle,
     }],
   }, "Should have ignored tombstone record");
   await buf.finalize();
   await PlacesUtils.bookmarks.eraseEverything();
   await PlacesSyncUtils.bookmarks.reset();
 });
 
+add_task(async function test_non_syncable_items() {
+  let buf = await openMirror("non_syncable_items");
+
+  info("Insert local orphaned left pane queries");
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.unfiledGuid,
+    children: [{
+      guid: "folderLEFTPQ",
+      url: "place:folder=SOMETHING",
+      title: "Some query",
+    }, {
+      guid: "folderLEFTPC",
+      url: "place:folder=SOMETHING_ELSE",
+      title: "A query under 'All Bookmarks'",
+    }],
+  });
+
+  info("Insert syncable local items (A > B) that exist in non-syncable remote root H");
+  await PlacesUtils.bookmarks.insertTree({
+    guid: PlacesUtils.bookmarks.menuGuid,
+    children: [{
+      // A is non-syncable remotely, but B doesn't exist remotely, so we'll
+      // remove A from the merged structure, and move B to the menu.
+      guid: "folderAAAAAA",
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      title: "A",
+      children: [{
+        guid: "bookmarkBBBB",
+        title: "B",
+        url: "http://example.com/b",
+      }],
+    }],
+  });
+
+  info("Insert non-syncable local root C and items (C > (D > E) F)");
+  await insertLocalRoot({
+    guid: "rootCCCCCCCC",
+    title: "C",
+  });
+  await PlacesUtils.bookmarks.insertTree({
+    guid: "rootCCCCCCCC",
+    children: [{
+      guid: "folderDDDDDD",
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      title: "D",
+      children: [{
+        guid: "bookmarkEEEE",
+        url: "http://example.com/e",
+        title: "E",
+      }],
+    }, {
+      guid: "bookmarkFFFF",
+      url: "http://example.com/f",
+      title: "F",
+    }],
+  });
+  await PlacesTestUtils.markBookmarksAsSynced();
+
+  info("Make remote changes");
+  await storeRecords(buf, [{
+    // H is a non-syncable root that only exists remotely.
+    id: "rootHHHHHHHH",
+    type: "folder",
+    parentid: "places",
+    title: "H",
+    children: ["folderAAAAAA"],
+  }, {
+    // A is a folder with children that's non-syncable remotely, and syncable
+    // locally. We should remove A and its descendants locally, since its parent
+    // H is known to be non-syncable remotely.
+    id: "folderAAAAAA",
+    type: "folder",
+    title: "A",
+    children: ["bookmarkFFFF", "bookmarkIIII"],
+  }, {
+    // F exists in two different non-syncable folders: C locally, and A
+    // remotely.
+    id: "bookmarkFFFF",
+    type: "bookmark",
+    title: "F",
+    bmkUri: "http://example.com/f",
+  }, {
+    id: "bookmarkIIII",
+    type: "query",
+    title: "I",
+    bmkUri: "http://example.com/i",
+  }, {
+    // The complete left pane root. We should remove all left pane queries
+    // locally, even though they're syncable, since the left pane root is
+    // known to be non-syncable.
+    id: "folderLEFTPR",
+    type: "folder",
+    parentid: "places",
+    title: "",
+    children: ["folderLEFTPQ", "folderLEFTPF"],
+  }, {
+    id: "folderLEFTPQ",
+    type: "query",
+    title: "Some query",
+    bmkUri: "place:folder=SOMETHING",
+  }, {
+    id: "folderLEFTPF",
+    type: "folder",
+    title: "All Bookmarks",
+    children: ["folderLEFTPC"],
+  }, {
+    id: "folderLEFTPC",
+    type: "query",
+    title: "A query under 'All Bookmarks'",
+    bmkUri: "place:folder=SOMETHING_ELSE",
+  }, {
+    // D, J, and G are syncable remotely, but D is non-syncable locally. Since
+    // J and G don't exist locally, and are syncable remotely, we'll remove D
+    // from the merged structure, and move J and G to unfiled.
+    id: "unfiled",
+    type: "folder",
+    children: ["folderDDDDDD", "bookmarkGGGG"],
+  }, {
+    id: "folderDDDDDD",
+    type: "folder",
+    title: "D",
+    children: ["bookmarkJJJJ"],
+  }, {
+    id: "bookmarkJJJJ",
+    type: "bookmark",
+    title: "J",
+    bmkUri: "http://example.com/j",
+  }, {
+    id: "bookmarkGGGG",
+    type: "bookmark",
+    title: "G",
+    bmkUri: "http://example.com/g",
+  }]);
+
+  let changesToUpload = await buf.apply();
+  deepEqual(await buf.fetchUnmergedGuids(), [], "Should merge all items");
+
+  let datesAdded = await promiseManyDatesAdded([PlacesUtils.bookmarks.menuGuid,
+    PlacesUtils.bookmarks.unfiledGuid, "bookmarkBBBB", "bookmarkJJJJ"]);
+  deepEqual(changesToUpload, {
+    bookmarkBBBB: {
+      tombstone: false,
+      counter: 1,
+      synced: false,
+      cleartext: {
+        id: "bookmarkBBBB",
+        type: "bookmark",
+        parentid: "menu",
+        hasDupe: true,
+        parentName: BookmarksMenuTitle,
+        dateAdded: datesAdded.get("bookmarkBBBB"),
+        bmkUri: "http://example.com/b",
+        title: "B",
+      },
+    },
+    bookmarkJJJJ: {
+      tombstone: false,
+      counter: 1,
+      synced: false,
+      cleartext: {
+        id: "bookmarkJJJJ",
+        type: "bookmark",
+        parentid: "unfiled",
+        hasDupe: true,
+        parentName: UnfiledBookmarksTitle,
+        dateAdded: undefined,
+        bmkUri: "http://example.com/j",
+        title: "J",
+      },
+    },
+    menu: {
+      tombstone: false,
+      counter: 1,
+      synced: false,
+      cleartext: {
+        id: "menu",
+        type: "folder",
+        parentid: "places",
+        hasDupe: true,
+        parentName: "",
+        dateAdded: datesAdded.get(PlacesUtils.bookmarks.menuGuid),
+        title: BookmarksMenuTitle,
+        children: ["bookmarkBBBB"],
+      },
+    },
+    unfiled: {
+      tombstone: false,
+      counter: 1,
+      synced: false,
+      cleartext: {
+        id: "unfiled",
+        type: "folder",
+        parentid: "places",
+        hasDupe: true,
+        parentName: "",
+        dateAdded: datesAdded.get(PlacesUtils.bookmarks.unfiledGuid),
+        title: UnfiledBookmarksTitle,
+        children: ["bookmarkJJJJ", "bookmarkGGGG"],
+      },
+    },
+  }, "Should upload new structure and tombstones for non-syncable items");
+
+  await assertLocalTree(PlacesUtils.bookmarks.rootGuid, {
+    guid: PlacesUtils.bookmarks.rootGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    index: 0,
+    title: "",
+    children: [{
+      guid: PlacesUtils.bookmarks.menuGuid,
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      index: 0,
+      title: BookmarksMenuTitle,
+      children: [{
+        guid: "bookmarkBBBB",
+        type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+        index: 0,
+        title: "B",
+        url: "http://example.com/b",
+      }]
+    }, {
+      guid: PlacesUtils.bookmarks.toolbarGuid,
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      index: 1,
+      title: BookmarksToolbarTitle,
+    }, {
+      guid: PlacesUtils.bookmarks.unfiledGuid,
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      index: 3,
+      title: UnfiledBookmarksTitle,
+      children: [{
+        guid: "bookmarkJJJJ",
+        type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+        index: 0,
+        title: "J",
+        url: "http://example.com/j",
+      }, {
+        guid: "bookmarkGGGG",
+        type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+        index: 1,
+        title: "G",
+        url: "http://example.com/g",
+      }],
+    }, {
+      guid: PlacesUtils.bookmarks.mobileGuid,
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      index: 4,
+      title: MobileBookmarksTitle,
+    }],
+  }, "Should upload new structure excluding non-syncable items");
+
+  await buf.finalize();
+  await PlacesUtils.bookmarks.eraseEverything();
+  await PlacesSyncUtils.bookmarks.reset();
+});
+
 // See what happens when a left-pane root and a left-pane query are on the server
 add_task(async function test_left_pane_root() {
   let buf = await openMirror("lpr");
 
   let initialTree = await fetchLocalTree(PlacesUtils.bookmarks.rootGuid);
 
   // This test is expected to not touch bookmarks at all, and if it did
   // happen to create a new item that's not under our syncable roots, then