Bug 1454864 - Simplify bookmark trees, merge states, and orphan relocation. r=tcsc
authorKit Cambridge <kit@yakshaving.ninja>
Fri, 27 Apr 2018 09:33:46 -0700
changeset 472919 c470f035fe635060d93fd483d553eee462fed99b
parent 472918 baf0ff2fb10ea14a68e12b9a1f8f73cb4ea7fa1f
child 472920 6cc5d9e64f7b733e47771753ffbbb405b18a1e46
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)
reviewerstcsc
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 - Simplify bookmark trees, merge states, and orphan relocation. r=tcsc * Remove `infosByNode` from `BookmarkTree`. The tree only needs to look up parents by children. The level, and, in the next commit, syncable flag, can be stored directly on the node. * Remove `MergedBookmarkNode#{toBookmarkNode, decidedValue}()`. These are from before we used triggers to apply the merged tree; we don't actually use the new merge state's synthesized node for anything. * Flatten `process{Local, Remote}OrphansForNode` into `relocate{Local, Remote}OrphansToNode`. The next commit uses these methods to flag non-syncable nodes for deletion. MozReview-Commit-ID: 6yqJMC1c7rP
toolkit/components/places/SyncedBookmarksMirror.jsm
--- a/toolkit/components/places/SyncedBookmarksMirror.jsm
+++ b/toolkit/components/places/SyncedBookmarksMirror.jsm
@@ -308,17 +308,17 @@ class SyncedBookmarksMirror {
    * Stores incoming or uploaded Sync records in the mirror. Rejects if any
    * records are invalid.
    *
    * @param {PlacesItem[]} records
    *        Sync records to store in the mirror.
    * @param {Boolean} [options.needsMerge]
    *        Indicates if the records were changed remotely since the last sync,
    *        and should be merged into the local tree. This option is set to
-   *       `true` for incoming records, and `false` for successfully uploaded
+   *        `true` for incoming records, and `false` for successfully uploaded
    *        records. Tests can also pass `false` to set up an existing mirror.
    */
   async store(records, { needsMerge = true } = {}) {
     let options = { needsMerge };
     let ignoreCounts = {
       bookmark: { id: 0, url: 0 },
       query: { id: 0, url: 0 },
       folder: { id: 0, root: 0 },
@@ -539,19 +539,20 @@ class SyncedBookmarksMirror {
           "Merged tree doesn't mention all items from local tree");
       }
       if (!await merger.subsumes(remoteTree)) {
         throw new SyncedBookmarksMirror.ConsistencyError(
           "Merged tree doesn't mention all items from remote tree");
       }
 
       MirrorLog.debug("Applying merged tree");
-      let localDeletions = Array.from(merger.deleteLocally).map(guid =>
-        ({ guid, level: localTree.levelForGuid(guid) })
-      );
+      let localDeletions = Array.from(merger.deleteLocally).map(guid => {
+        let localNode = localTree.nodeForGuid(guid);
+        return { guid, level: localNode ? localNode.level : -1 };
+      });
       let remoteDeletions = Array.from(merger.deleteRemotely);
       let { time: updateTiming } = await withTiming(
         "Apply merged tree",
         () => this.updateLocalItemsInPlaces(mergedRoot, localDeletions,
                                             remoteDeletions)
       );
       applyStats.update = { time: updateTiming };
 
@@ -1091,17 +1092,17 @@ class SyncedBookmarksMirror {
     }
 
     // Second, build a complete tree from the pseudo-tree. We could do these
     // two steps in SQL, but it's extremely inefficient. An equivalent
     // recursive query, with joins in the base and recursive clauses, takes
     // 10 seconds for a mirror with 5k items. Building the pseudo-tree and
     // the pseudo-tree and recursing in JS takes 30ms for 5k items.
     // (Note: Timing was done before adding maybeYield calls)
-    await inflateTree(remoteTree, pseudoTree, PlacesUtils.bookmarks.rootGuid);
+    await inflateTree(remoteTree, pseudoTree, remoteTree.root);
 
     // Note tombstones for remotely deleted items.
     let tombstoneRows = await this.db.execute(`
       SELECT guid FROM items
       WHERE isDeleted AND
             needsMerge`);
 
     for await (let row of yieldingIterator(tombstoneRows)) {
@@ -1185,17 +1186,18 @@ class SyncedBookmarksMirror {
                     /* 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
                           n.name = :feedURLAnno
                   ) THEN :livemarkKind
                   ELSE :folderKind END)
                 ELSE :separatorKind END) AS kind,
-             b.lastModified / 1000 AS localModified, b.syncChangeCounter
+             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`,
       { bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK,
         queryKind: SyncedBookmarksMirror.KIND.QUERY,
         bookmarkKind: SyncedBookmarksMirror.KIND.BOOKMARK,
         folderType: PlacesUtils.bookmarks.TYPE_FOLDER,
@@ -2779,23 +2781,24 @@ function validateTag(rawTag) {
     // Drop empty and oversized tags.
     return null;
   }
   return tag;
 }
 
 // Recursively inflates a bookmark tree from a pseudo-tree that maps
 // parents to children.
-async function inflateTree(tree, pseudoTree, parentGuid) {
-  let nodes = pseudoTree.get(parentGuid);
+async function inflateTree(tree, pseudoTree, parentNode) {
+  let nodes = pseudoTree.get(parentNode.guid);
   if (nodes) {
     for (let node of nodes) {
       await maybeYield();
-      tree.insert(parentGuid, node);
-      await inflateTree(tree, pseudoTree, node.guid);
+      node.level = parentNode.level + 1;
+      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
 // function.
 async function withTiming(name, func) {
@@ -2869,82 +2872,67 @@ function makeDupeKey(node, content) {
 }
 
 /**
  * The merge state indicates which node we should prefer when reconciling
  * with Places. Recall that a merged node may point to a local node, remote
  * node, or both.
  */
 class BookmarkMergeState {
-  constructor(type, newStructureNode = null) {
-    this.type = type;
-    this.newStructureNode = newStructureNode;
+  constructor(value, structure = value) {
+    this.value = value;
+    this.structure = structure;
   }
 
   /**
-   * Takes an existing value state, and a new node for the structure state. We
-   * use the new merge state to resolve conflicts caused by moving local items
-   * out of a remotely deleted folder, or remote items out of a locally deleted
-   * folder.
+   * Takes an existing value state, and a new structure state. We use the new
+   * merge state to resolve conflicts caused by moving local items out of a
+   * remotely deleted folder, or remote items out of a locally deleted folder.
    *
    * Applying a new merged node bumps its local change counter, so that the
    * merged structure is reuploaded to the server.
    *
    * @param  {BookmarkMergeState} oldState
-   *         The existing value state.
-   * @param  {BookmarkNode} newStructureNode
-   *         A node to use for the new structure state.
+   *         The existing merge state.
    * @return {BookmarkMergeState}
    *         The new merge state.
    */
-  static new(oldState, newStructureNode) {
-    return new BookmarkMergeState(oldState.type, newStructureNode);
-  }
-
-  // Returns the structure state type: `LOCAL`, `REMOTE`, or `NEW`.
-  structure() {
-    return this.newStructureNode ? BookmarkMergeState.TYPE.NEW : this.type;
-  }
-
-  // Returns the value state type: `LOCAL` or `REMOTE`.
-  value() {
-    return this.type;
+  static new(oldState) {
+    return new BookmarkMergeState(oldState.value, BookmarkMergeState.TYPE.NEW);
   }
 
   /**
    * Returns a representation of the value ("V") and structure ("S") state
    * for logging. "L" is "local", "R" is "remote", and "+" is "new". We use
    * compact notation here to reduce noise in trace logs, which log the
    * merge state of every node in the tree.
    *
    * @return {String}
    */
   toString() {
     return `(${this.valueToString()}; ${this.structureToString()})`;
   }
 
   valueToString() {
-    switch (this.value()) {
+    switch (this.value) {
       case BookmarkMergeState.TYPE.LOCAL:
         return "Value: Local";
       case BookmarkMergeState.TYPE.REMOTE:
         return "Value: Remote";
     }
     return "Value: ?";
   }
 
   structureToString() {
-    switch (this.structure()) {
+    switch (this.structure) {
       case BookmarkMergeState.TYPE.LOCAL:
         return "Structure: Local";
       case BookmarkMergeState.TYPE.REMOTE:
         return "Structure: Remote";
       case BookmarkMergeState.TYPE.NEW:
-        // We intentionally don't log the new structure node here, since
-        // the merger already does that.
         return "Structure: New";
     }
     return "Structure: ?";
   }
 
   toJSON() {
     return this.toString();
   }
@@ -2979,28 +2967,29 @@ 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, age, kind, needsMerge = false) {
+  constructor(guid, kind, { age = 0, needsMerge = false, level = 0 } = {}) {
     this.guid = guid;
     this.kind = kind;
     this.age = age;
     this.needsMerge = needsMerge;
+    this.level = level;
     this.children = [];
   }
 
   // Creates a virtual folder node for the Places root.
   static root() {
     let guid = PlacesUtils.bookmarks.rootGuid;
-    return new BookmarkNode(guid, 0, SyncedBookmarksMirror.KIND.FOLDER);
+    return new BookmarkNode(guid, SyncedBookmarksMirror.KIND.FOLDER);
   }
 
   /**
    * Creates a bookmark node from a Places row.
    *
    * @param  {mozIStorageRow} row
    *         The Places row containing the node info.
    * @param  {Number} localTimeSeconds
@@ -3013,21 +3002,22 @@ class BookmarkNode {
     let guid = row.getResultByName("guid");
 
     // 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 syncChangeCounter = row.getResultByName("syncChangeCounter");
     let needsMerge = syncChangeCounter > 0;
 
-    return new BookmarkNode(guid, age, kind, needsMerge);
+    return new BookmarkNode(guid, kind, { age, needsMerge, level });
   }
 
   /**
    * Creates a bookmark node from a mirror row.
    *
    * @param  {mozIStorageRow} row
    *         The mirror row containing the node info.
    * @param  {Number} remoteTimeSeconds
@@ -3041,17 +3031,17 @@ class BookmarkNode {
 
     // `serverModified` is in milliseconds.
     let serverModified = row.getResultByName("serverModified");
     let age = Math.max(remoteTimeSeconds - serverModified / 1000, 0) || 0;
 
     let kind = row.getResultByName("kind");
     let needsMerge = !!row.getResultByName("needsMerge");
 
-    return new BookmarkNode(guid, age, kind, needsMerge);
+    return new BookmarkNode(guid, kind, { age, needsMerge });
   }
 
   isFolder() {
     return this.kind == SyncedBookmarksMirror.KIND.FOLDER;
   }
 
   newerThan(otherNode) {
     return this.age < otherNode.age;
@@ -3153,48 +3143,36 @@ class BookmarkNode {
   }
 }
 
 /**
  * A complete, rooted tree with tombstones.
  */
 class BookmarkTree {
   constructor(root) {
-    this.byGuid = new Map();
-    this.infosByNode = new WeakMap();
+    this.root = root;
+    this.byGuid = new Map([[this.root.guid, this.root]]);
+    this.parentNodeByChildNode = new Map([[this.root, null]]);
     this.deletedGuids = new Set();
-
-    this.root = root;
-    this.byGuid.set(this.root.guid, this.root);
   }
 
   get guidCount() {
     return this.byGuid.size + this.deletedGuids.size;
   }
 
   isDeleted(guid) {
     return this.deletedGuids.has(guid);
   }
 
   nodeForGuid(guid) {
     return this.byGuid.get(guid);
   }
 
   parentNodeFor(childNode) {
-    let info = this.infosByNode.get(childNode);
-    return info ? info.parentNode : null;
-  }
-
-  levelForGuid(guid) {
-    let node = this.byGuid.get(guid);
-    if (!node) {
-      return -1;
-    }
-    let info = this.infosByNode.get(node);
-    return info ? info.level : -1;
+    return this.parentNodeByChildNode.get(childNode);
   }
 
   /**
    * Inserts a node into the tree. The node must not already exist in the tree,
    * and the node's parent must be a folder.
    */
   insert(parentGuid, node) {
     if (this.byGuid.has(node.guid)) {
@@ -3212,20 +3190,17 @@ class BookmarkTree {
     if (!parentNode.isFolder()) {
       MirrorLog.error("Non-folder parent ${parentNode} for node ${node}",
                       { parentNode, node });
       throw new TypeError("Can't insert node into non-folder");
     }
 
     parentNode.children.push(node);
     this.byGuid.set(node.guid, node);
-
-    let parentInfo = this.infosByNode.get(parentNode);
-    let level = parentInfo ? parentInfo.level + 1 : 0;
-    this.infosByNode.set(node, { parentNode, level });
+    this.parentNodeByChildNode.set(node, parentNode);
   }
 
   noteDeleted(guid) {
     this.deletedGuids.add(guid);
   }
 
   * syncableGuids() {
     let nodesToWalk = PlacesUtils.bookmarks.userContentRoots.map(guid => {
@@ -3279,91 +3254,25 @@ class MergedBookmarkNode {
       let mergeStateParam = {
         localGuid: mergedChild.localNode ? mergedChild.localNode.guid : null,
         // The merged GUID is different than the local GUID if we deduped a
         // NEW local item to a remote item.
         mergedGuid: mergedChild.guid,
         parentGuid: this.guid,
         level,
         position,
-        valueState: mergedChild.mergeState.value(),
-        structureState: mergedChild.mergeState.structure(),
+        valueState: mergedChild.mergeState.value,
+        structureState: mergedChild.mergeState.structure,
       };
       yield mergeStateParam;
       yield* mergedChild.mergeStatesParams(level + 1);
     }
   }
 
   /**
-   * Creates a bookmark node from this merged node.
-   *
-   * @return {BookmarkNode}
-   *         A node containing the decided value and structure state.
-   */
-  async toBookmarkNode() {
-    if (MergedBookmarkNode.cachedBookmarkNodes.has(this)) {
-      return MergedBookmarkNode.cachedBookmarkNodes.get(this);
-    }
-
-    let decidedValueNode = this.decidedValue();
-    let decidedStructureState = this.mergeState.structure();
-    let needsMerge = decidedStructureState == BookmarkMergeState.TYPE.NEW ||
-                     (decidedStructureState == BookmarkMergeState.TYPE.LOCAL &&
-                      decidedValueNode.needsMerge);
-
-    let newNode = new BookmarkNode(this.guid, decidedValueNode.age,
-                                   decidedValueNode.kind, needsMerge);
-    MergedBookmarkNode.cachedBookmarkNodes.set(this, newNode);
-
-    if (newNode.isFolder()) {
-      for await (let mergedChildNode of yieldingIterator(this.mergedChildren)) {
-        newNode.children.push(await mergedChildNode.toBookmarkNode());
-      }
-    }
-
-    return newNode;
-  }
-
-  /**
-   * Decides the value state for the merged node. Note that you can't walk the
-   * decided node's children: since the value node doesn't include structure
-   * changes from the other side, you'll depart from the merged tree. You'll
-   * want to use `toBookmarkNode` instead, which returns a node with the
-   * decided value *and* structure.
-   *
-   * @return {BookmarkNode}
-   *         The local or remote node containing the decided value state.
-   */
-  decidedValue() {
-    let valueState = this.mergeState.value();
-    switch (valueState) {
-      case BookmarkMergeState.TYPE.LOCAL:
-        if (!this.localNode) {
-          MirrorLog.error("Merged node ${guid} has local value state, but " +
-                          "no local node", this);
-          throw new TypeError(
-            "Can't take local value state without local node");
-        }
-        return this.localNode;
-
-      case BookmarkMergeState.TYPE.REMOTE:
-        if (!this.remoteNode) {
-          MirrorLog.error("Merged node ${guid} has remote value state, but " +
-                          "no remote node", this);
-          throw new TypeError(
-            "Can't take remote value state without remote node");
-        }
-        return this.remoteNode;
-    }
-    MirrorLog.error("Merged node ${guid} has unknown value state ${valueState}",
-                    { guid: this.guid, valueState });
-    throw new TypeError("Can't take unknown value state");
-  }
-
-  /**
    * Generates an ASCII art representation of the merged node and its
    * descendants. This is similar to the format generated by
    * `BookmarkNode#toASCIITreeString`, but logs value and structure states for
    * merged children.
    *
    * @return {String}
    */
   toASCIITreeString(prefix = "") {
@@ -3386,19 +3295,16 @@ class MergedBookmarkNode {
     return `${this.guid} ${this.mergeState.toString()}`;
   }
 
   toJSON() {
     return this.toString();
   }
 }
 
-// Caches bookmark nodes containing the decided value and structure.
-MergedBookmarkNode.cachedBookmarkNodes = new WeakMap();
-
 /**
  * A two-way merger that produces a complete merged tree from a complete local
  * tree and a complete remote tree with changes since the last sync.
  *
  * This is ported almost directly from iOS. On iOS, the `ThreeWayMerger` takes a
  * complete "mirror" tree with the server state after the last sync, and two
  * incomplete trees with local and remote changes to the mirror: "local" and
  * "mirror", respectively. Overlaying buffer onto mirror yields the current
@@ -4022,19 +3928,17 @@ class BookmarkMerger {
     }
 
     // Update the merge state if we moved children orphaned on one side by a
     // deletion on the other side, if we kept newer locally moved children,
     // or if the child order changed. We already updated the merge state of the
     // orphans, but we also need to flag the containing folder so that it's
     // reuploaded to the server along with the new children.
     if (mergeStateChanged) {
-      let newStructureNode = await mergedNode.toBookmarkNode();
-      let newMergeState = BookmarkMergeState.new(mergedNode.mergeState,
-                                                 newStructureNode);
+      let newMergeState = BookmarkMergeState.new(mergedNode.mergeState);
       MirrorLog.trace("Merge state for ${mergedNode} has new structure " +
                       "${newMergeState}", { mergedNode, newMergeState });
       this.structureCounts.new++;
       mergedNode.mergeState = newMergeState;
     }
   }
 
   /**
@@ -4143,28 +4047,26 @@ class BookmarkMerger {
       // revive the child folder, but it's easier to relocate orphaned
       // grandchildren than to partially revive the child folder.
       MirrorLog.trace("Remote folder ${remoteNode} deleted locally " +
                       "and changed remotely; taking local deletion",
                       { remoteNode });
       this.structureCounts.localDeletes++;
     } else {
       MirrorLog.trace("Remote node ${remoteNode} deleted locally and not " +
-                       "changed remotely; taking local deletion",
-                       { remoteNode });
+                      "changed remotely; taking local deletion",
+                      { remoteNode });
     }
 
+    // Take the local deletion and relocate any new remote descendants to the
+    // merged node.
     this.deleteRemotely.add(remoteNode.guid);
-
-    let mergedOrphanNodes = await this.processRemoteOrphansForNode(mergedNode,
-                                                                   remoteNode);
-    await this.relocateOrphansTo(mergedNode, mergedOrphanNodes);
-    MirrorLog.trace("Relocating remote orphans ${mergedOrphanNodes} to " +
-                    "${mergedNode}", { mergedOrphanNodes, mergedNode });
-
+    if (remoteNode.isFolder()) {
+      await this.relocateRemoteOrphansToMergedNode(mergedNode, remoteNode);
+    }
     return BookmarkMerger.STRUCTURE.DELETED;
   }
 
   /**
    * Checks if a local node is remotely moved or deleted, and reparents any
    * descendants that aren't also locally deleted to the merged node.
    *
    * This is the inverse of `checkForLocalStructureChangeOfRemoteNode`.
@@ -4210,39 +4112,41 @@ class BookmarkMerger {
       MirrorLog.trace("Local folder ${localNode} deleted remotely and " +
                       "changed locally; taking remote deletion", { localNode });
       this.structureCounts.remoteDeletes++;
     } else {
       MirrorLog.trace("Local node ${localNode} deleted remotely and not " +
                       "changed locally; taking remote deletion", { localNode });
     }
 
-    MirrorLog.trace("Local node ${localNode} deleted remotely; taking remote " +
-                    "deletion", { localNode });
-
+    // Take the remote deletion and relocate any new local descendants to the
+    // merged node.
     this.deleteLocally.add(localNode.guid);
-
-    let mergedOrphanNodes = await this.processLocalOrphansForNode(mergedNode,
-                                                                  localNode);
-    await this.relocateOrphansTo(mergedNode, mergedOrphanNodes);
-    MirrorLog.trace("Relocating local orphans ${mergedOrphanNodes} to " +
-                    "${mergedNode}", { mergedOrphanNodes, mergedNode });
-
+    if (localNode.isFolder()) {
+      await this.relocateLocalOrphansToMergedNode(mergedNode, localNode);
+    }
     return BookmarkMerger.STRUCTURE.DELETED;
   }
 
   /**
-   * Recursively merges all remote children of a locally deleted folder that
-   * haven't also been deleted remotely. This can happen if the user adds a
-   * bookmark to a folder on another device, and deletes that folder locally.
-   * This is the inverse of `processLocalOrphansForNode`.
+   * Takes a local deletion for a remote node by marking the node as deleted,
+   * and relocating all remote descendants that aren't also locally deleted to
+   * the closest surviving ancestor. We do this to avoid data loss if the
+   * user adds a bookmark to a folder on another device, and deletes that
+   * folder locally.
+   *
+   * This is the inverse of `relocateLocalOrphansToMergedNode`.
+   *
+   * @param {MergedBookmarkNode} mergedNode
+   *        The closest surviving ancestor, to hold relocated remote orphans.
+   * @param {BookmarkNode} remoteNode
+   *        The locally deleted remote node.
    */
-  async processRemoteOrphansForNode(mergedNode, remoteNode) {
+  async relocateRemoteOrphansToMergedNode(mergedNode, remoteNode) {
     let remoteOrphanNodes = [];
-
     for await (let remoteChildNode of yieldingIterator(remoteNode.children)) {
       let structureChange = await this.checkForLocalStructureChangeOfRemoteNode(
         mergedNode, remoteNode, remoteChildNode);
       if (structureChange == BookmarkMerger.STRUCTURE.MOVED ||
           structureChange == BookmarkMerger.STRUCTURE.DELETED) {
         // The remote child is already moved or deleted locally, so we should
         // ignore it instead of treating it as a remote orphan.
         continue;
@@ -4253,30 +4157,39 @@ class BookmarkMerger {
     let mergedOrphanNodes = [];
     for await (let remoteOrphanNode of yieldingIterator(remoteOrphanNodes)) {
       let localOrphanNode = this.localTree.nodeForGuid(remoteOrphanNode.guid);
       let mergedOrphanNode = await this.mergeNode(remoteOrphanNode.guid,
                                                   localOrphanNode, remoteOrphanNode);
       mergedOrphanNodes.push(mergedOrphanNode);
     }
 
-    return mergedOrphanNodes;
+    MirrorLog.trace("Relocating remote orphans ${mergedOrphanNodes} to " +
+                    "${mergedNode}", { mergedOrphanNodes, mergedNode });
+    for await (let mergedOrphanNode of yieldingIterator(mergedOrphanNodes)) {
+      // Flag the moved orphans for reupload.
+      let mergeState = BookmarkMergeState.new(mergedOrphanNode.mergeState);
+      mergedOrphanNode.mergeState = mergeState;
+      mergedNode.mergedChildren.push(mergedOrphanNode);
+    }
   }
 
   /**
-   * Recursively merges all local children of a remotely deleted folder that
-   * haven't also been deleted locally. This is the inverse of
-   * `processRemoteOrphansForNode`.
+   * Takes a remote deletion for a local node by marking the node as deleted,
+   * and relocating all local descendants that aren't also remotely deleted to
+   * the closest surviving ancestor.
+   *
+   * This is the inverse of `relocateRemoteOrphansToMergedNode`.
+   *
+   * @param {MergedBookmarkNode} mergedNode
+   *        The closest surviving ancestor, to hold relocated local orphans.
+   * @param {BookmarkNode} localNode
+   *        The remotely deleted local node.
    */
-  async processLocalOrphansForNode(mergedNode, localNode) {
-    if (!localNode.isFolder()) {
-      // The local node isn't a folder, so it won't have orphans.
-      return [];
-    }
-
+  async relocateLocalOrphansToMergedNode(mergedNode, localNode) {
     let localOrphanNodes = [];
     for await (let localChildNode of yieldingIterator(localNode.children)) {
       let structureChange = await this.checkForRemoteStructureChangeOfLocalNode(
         mergedNode, localNode, localChildNode);
       if (structureChange == BookmarkMerger.STRUCTURE.MOVED ||
           structureChange == BookmarkMerger.STRUCTURE.DELETED) {
         // The local child is already moved or deleted remotely, so we should
         // ignore it instead of treating it as a local orphan.
@@ -4288,35 +4201,22 @@ class BookmarkMerger {
     let mergedOrphanNodes = [];
     for await (let localOrphanNode of yieldingIterator(localOrphanNodes)) {
       let remoteOrphanNode = this.remoteTree.nodeForGuid(localOrphanNode.guid);
       let mergedNode = await this.mergeNode(localOrphanNode.guid,
                                             localOrphanNode, remoteOrphanNode);
       mergedOrphanNodes.push(mergedNode);
     }
 
-    return mergedOrphanNodes;
-  }
-
-  /**
-   * Moves a list of merged orphan nodes to the closest surviving ancestor.
-   * Changes the merge state of the moved orphans to new, so that we reupload
-   * them along with their new parent on the next sync.
-   *
-   * @param {MergedBookmarkNode} mergedNode
-   *        The closest surviving ancestor.
-   * @param {MergedBookmarkNode[]} mergedOrphanNodes
-   *        Merged orphans to relocate to the surviving ancestor.
-   */
-  async relocateOrphansTo(mergedNode, mergedOrphanNodes) {
-    for (let mergedOrphanNode of mergedOrphanNodes) {
-      let newStructureNode = await mergedOrphanNode.toBookmarkNode();
-      let newMergeState = BookmarkMergeState.new(mergedOrphanNode.mergeState,
-                                                 newStructureNode);
-      mergedOrphanNode.mergeState = newMergeState;
+    MirrorLog.trace("Relocating local orphans ${mergedOrphanNodes} to " +
+                    "${mergedNode}", { mergedOrphanNodes, mergedNode });
+
+    for await (let mergedOrphanNode of yieldingIterator(mergedOrphanNodes)) {
+      let mergeState = BookmarkMergeState.new(mergedOrphanNode.mergeState);
+      mergedOrphanNode.mergeState = mergeState;
       mergedNode.mergedChildren.push(mergedOrphanNode);
     }
   }
 
   /**
    * Finds all children of a local folder with similar content as children of
    * the corresponding remote folder. This is used to dedupe local items that
    * haven't been uploaded yet, to remote items that don't exist locally.