Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 2280 insertions, 0 deletions

diff --git a/third_party/rust/dogear/src/merge.rs b/third_party/rust/dogear/src/merge.rs
new file mode 100644
index 0000000000..920e55c295
--- /dev/null
+++ b/third_party/rust/dogear/src/merge.rs
@@ -0,0 +1,2280 @@
+// Copyright 2018-2019 Mozilla
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use std::{
+    collections::{hash_map::Entry, HashMap, HashSet, VecDeque},
+    fmt, mem,
+};
+
+use crate::driver::{AbortSignal, DefaultAbortSignal, DefaultDriver, Driver};
+use crate::error::{ErrorKind, Result};
+use crate::guid::{Guid, IsValidGuid, TAGS_GUID};
+use crate::tree::{Content, MergeState, MergedNode, Node, Tree, Validity};
+
+/// Structure change types, used to indicate if a node on one side is moved
+/// or deleted on the other.
+#[derive(Eq, PartialEq)]
+enum StructureChange {
+    /// Node not deleted, or doesn't exist, on the other side.
+    Unchanged,
+    /// Node moved on the other side.
+    Moved,
+    /// Node deleted on the other side.
+    Deleted,
+}
+
+/// Records structure change counters for telemetry.
+#[derive(Clone, Copy, Default, Debug, Eq, Hash, PartialEq)]
+pub struct StructureCounts {
+    /// Remote non-folder change wins over local deletion.
+    pub remote_revives: usize,
+    /// Local folder deletion wins over remote change.
+    pub local_deletes: usize,
+    /// Local non-folder change wins over remote deletion.
+    pub local_revives: usize,
+    /// Remote folder deletion wins over local change.
+    pub remote_deletes: usize,
+    /// Deduped local items.
+    pub dupes: usize,
+    /// Total number of nodes in the merged tree, excluding the
+    /// root.
+    pub merged_nodes: usize,
+}
+
+/// Holds (matching remote dupes for local GUIDs, matching local dupes for
+/// remote GUIDs).
+type MatchingDupes<'t> = (HashMap<Guid, Node<'t>>, HashMap<Guid, Node<'t>>);
+
+/// Indicates which side to take in case of a merge conflict.
+#[derive(Clone, Copy, Debug)]
+enum ConflictResolution {
+    Local,
+    Remote,
+    Unchanged,
+}
+
+/// A hash key used to match dupes by content.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+enum DupeKey<'a> {
+    /// Matches a dupe by content only. Used for bookmarks, queries, folders,
+    /// and livemarks.
+    WithoutPosition(&'a Content),
+    /// Matches a dupe by content and position. Used for separators.
+    WithPosition(&'a Content, usize),
+}
+
+/// 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
+/// server tree; overlaying local onto mirror yields the complete local tree.
+///
+/// Dogear doesn't store the shared parent for changed items, so we can only
+/// do two-way merges. Our local tree is the union of iOS's mirror and local,
+/// and our remote tree is the union of iOS's mirror and buffer.
+///
+/// Unlike iOS, Dogear doesn't distinguish between structure and value changes.
+/// The `needs_merge` flag notes *that* a bookmark changed, but not *how*. This
+/// means we might detect conflicts, and revert changes on one side, for cases
+/// that iOS can merge cleanly.
+///
+/// Fortunately, most of our users don't organize their bookmarks into deeply
+/// nested hierarchies, or make conflicting changes on multiple devices
+/// simultaneously. A simpler two-way tree merge strikes a good balance between
+/// correctness and complexity.
+pub struct Merger<'t, D = DefaultDriver, A = DefaultAbortSignal> {
+    driver: &'t D,
+    signal: &'t A,
+    local_tree: &'t Tree,
+    remote_tree: &'t Tree,
+    matching_dupes_by_local_parent_guid: HashMap<Guid, MatchingDupes<'t>>,
+    merged_guids: HashSet<Guid>,
+    delete_locally: HashSet<Guid>,
+    delete_remotely: HashSet<Guid>,
+    structure_counts: StructureCounts,
+}
+
+impl<'t> Merger<'t, DefaultDriver, DefaultAbortSignal> {
+    /// Creates a merger with the default merge driver.
+    pub fn new(local_tree: &'t Tree, remote_tree: &'t Tree) -> Merger<'t> {
+        Merger {
+            driver: &DefaultDriver,
+            signal: &DefaultAbortSignal,
+            local_tree,
+            remote_tree,
+            matching_dupes_by_local_parent_guid: HashMap::new(),
+            merged_guids: HashSet::new(),
+            delete_locally: HashSet::new(),
+            delete_remotely: HashSet::new(),
+            structure_counts: StructureCounts::default(),
+        }
+    }
+}
+
+impl<'t, D: Driver, A: AbortSignal> Merger<'t, D, A> {
+    /// Creates a merger with the given merge driver and contents.
+    pub fn with_driver(
+        driver: &'t D,
+        signal: &'t A,
+        local_tree: &'t Tree,
+        remote_tree: &'t Tree,
+    ) -> Merger<'t, D, A> {
+        Merger {
+            driver,
+            signal,
+            local_tree,
+            remote_tree,
+            matching_dupes_by_local_parent_guid: HashMap::new(),
+            merged_guids: HashSet::new(),
+            delete_locally: HashSet::new(),
+            delete_remotely: HashSet::new(),
+            structure_counts: StructureCounts::default(),
+        }
+    }
+
+    /// Builds a merged tree from the local and remote trees.
+    pub fn merge(mut self) -> Result<MergedRoot<'t>> {
+        let merged_root_node = {
+            let local_root_node = self.local_tree.root();
+            let remote_root_node = self.remote_tree.root();
+            self.two_way_merge(local_root_node, remote_root_node)?
+        };
+
+        // 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 locally, or the local tree has tombstones for items that
+        // aren't on the server.
+        for guid in self.local_tree.deletions() {
+            self.signal.err_if_aborted()?;
+            if !self.mentions(guid) {
+                self.delete_remotely.insert(guid.clone());
+            }
+        }
+        for guid in self.remote_tree.deletions() {
+            self.signal.err_if_aborted()?;
+            if !self.mentions(guid) {
+                self.delete_locally.insert(guid.clone());
+            }
+        }
+
+        // The merged tree should know about all items mentioned in the local
+        // and remote trees. Otherwise, it's incomplete, and we can't apply it.
+        // This indicates a bug in the merger.
+        for guid in self.local_tree.guids() {
+            self.signal.err_if_aborted()?;
+            if !self.mentions(guid) {
+                return Err(ErrorKind::UnmergedLocalItems.into());
+            }
+        }
+        for guid in self.remote_tree.guids() {
+            self.signal.err_if_aborted()?;
+            if !self.mentions(guid) {
+                return Err(ErrorKind::UnmergedRemoteItems.into());
+            }
+        }
+
+        Ok(MergedRoot {
+            local_tree: self.local_tree,
+            remote_tree: self.remote_tree,
+            node: merged_root_node,
+            merged_guids: self.merged_guids,
+            delete_locally: self.delete_locally,
+            delete_remotely: self.delete_remotely,
+            structure_counts: self.structure_counts,
+        })
+    }
+
+    #[inline]
+    fn mentions(&self, guid: &Guid) -> bool {
+        self.merged_guids.contains(guid)
+            || self.delete_locally.contains(guid)
+            || self.delete_remotely.contains(guid)
+    }
+
+    fn merge_local_only_node(&mut self, local_node: Node<'t>) -> Result<MergedNode<'t>> {
+        trace!(self.driver, "Item {} only exists locally", local_node);
+
+        self.merged_guids.insert(local_node.guid.clone());
+
+        let merged_guid = if local_node.guid.is_valid_guid() {
+            local_node.guid.clone()
+        } else {
+            warn!(
+                self.driver,
+                "Generating new GUID for local node {}", local_node
+            );
+            self.signal.err_if_aborted()?;
+            let new_guid = self.driver.generate_new_guid(&local_node.guid)?;
+            if new_guid != local_node.guid {
+                if self.merged_guids.contains(&new_guid) {
+                    return Err(ErrorKind::DuplicateItem(new_guid).into());
+                }
+                self.merged_guids.insert(new_guid.clone());
+            }
+            new_guid
+        };
+
+        let mut merged_node = MergedNode::new(merged_guid, MergeState::LocalOnly(local_node));
+        // The local folder doesn't exist remotely, but its children might, so
+        // we still need to recursively walk and merge them. This method will
+        // change the merge state from local to new if any children were moved
+        // or deleted.
+        for local_child_node in local_node.children() {
+            self.signal.err_if_aborted()?;
+            self.merge_local_child_into_merged_node(
+                &mut merged_node,
+                local_node,
+                None,
+                local_child_node,
+            )?;
+        }
+
+        if local_node.diverged() {
+            merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+        }
+
+        Ok(merged_node)
+    }
+
+    fn merge_remote_only_node(&mut self, remote_node: Node<'t>) -> Result<MergedNode<'t>> {
+        trace!(self.driver, "Item {} only exists remotely", remote_node);
+
+        self.merged_guids.insert(remote_node.guid.clone());
+
+        let merged_guid = if remote_node.guid.is_valid_guid() {
+            remote_node.guid.clone()
+        } else {
+            warn!(
+                self.driver,
+                "Generating new GUID for remote node {}", remote_node
+            );
+            self.signal.err_if_aborted()?;
+            let new_guid = self.driver.generate_new_guid(&remote_node.guid)?;
+            if new_guid != remote_node.guid {
+                if self.merged_guids.contains(&new_guid) {
+                    return Err(ErrorKind::DuplicateItem(new_guid).into());
+                }
+                self.merged_guids.insert(new_guid.clone());
+                // Upload tombstones for changed remote GUIDs.
+                self.delete_remotely.insert(remote_node.guid.clone());
+            }
+            new_guid
+        };
+        let mut merged_node = MergedNode::new(merged_guid, MergeState::RemoteOnly(remote_node));
+        // As above, a remote folder's children might still exist locally, so we
+        // need to merge them and update the merge state from remote to new if
+        // any children were moved or deleted.
+        for remote_child_node in remote_node.children() {
+            self.signal.err_if_aborted()?;
+            self.merge_remote_child_into_merged_node(
+                &mut merged_node,
+                None,
+                remote_node,
+                remote_child_node,
+            )?;
+        }
+
+        if remote_node.diverged()
+            || merged_node.remote_guid_changed()
+            || remote_node.validity != Validity::Valid
+        {
+            // If the remote structure diverged, the merged item's GUID changed,
+            // or the item isn't valid, flag it for reupload.
+            merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+        }
+
+        Ok(merged_node)
+    }
+
+    /// Merges two nodes that exist locally and remotely.
+    fn two_way_merge(
+        &mut self,
+        local_node: Node<'t>,
+        remote_node: Node<'t>,
+    ) -> Result<MergedNode<'t>> {
+        trace!(
+            self.driver,
+            "Item exists locally as {} and remotely as {}",
+            local_node,
+            remote_node
+        );
+
+        if !local_node.has_compatible_kind(&remote_node) {
+            error!(
+                self.driver,
+                "Merging local {} and remote {} with different kinds", local_node, remote_node
+            );
+            return Err(ErrorKind::MismatchedItemKind(
+                local_node.item().clone(),
+                remote_node.item().clone(),
+            )
+            .into());
+        }
+
+        self.merged_guids.insert(local_node.guid.clone());
+        self.merged_guids.insert(remote_node.guid.clone());
+
+        let merged_guid = if remote_node.guid.is_valid_guid() {
+            remote_node.guid.clone()
+        } else {
+            warn!(
+                self.driver,
+                "Generating new valid GUID for node {}", remote_node
+            );
+            self.signal.err_if_aborted()?;
+            let new_guid = self.driver.generate_new_guid(&remote_node.guid)?;
+            if new_guid != remote_node.guid {
+                if self.merged_guids.contains(&new_guid) {
+                    return Err(ErrorKind::DuplicateItem(new_guid).into());
+                }
+                self.merged_guids.insert(new_guid.clone());
+                // Upload tombstones for changed remote GUIDs.
+                self.delete_remotely.insert(remote_node.guid.clone());
+            }
+            new_guid
+        };
+
+        let (item, children) = self.resolve_value_conflict(local_node, remote_node);
+
+        let mut merged_node = MergedNode::new(
+            merged_guid,
+            match item {
+                ConflictResolution::Local => MergeState::Local {
+                    local_node,
+                    remote_node,
+                },
+                ConflictResolution::Remote => MergeState::Remote {
+                    local_node,
+                    remote_node,
+                },
+                ConflictResolution::Unchanged => MergeState::Unchanged {
+                    local_node,
+                    remote_node,
+                },
+            },
+        );
+
+        match children {
+            ConflictResolution::Local => {
+                for local_child_node in local_node.children() {
+                    self.signal.err_if_aborted()?;
+                    self.merge_local_child_into_merged_node(
+                        &mut merged_node,
+                        local_node,
+                        Some(remote_node),
+                        local_child_node,
+                    )?;
+                }
+                for remote_child_node in remote_node.children() {
+                    self.signal.err_if_aborted()?;
+                    self.merge_remote_child_into_merged_node(
+                        &mut merged_node,
+                        Some(local_node),
+                        remote_node,
+                        remote_child_node,
+                    )?;
+                }
+            }
+
+            ConflictResolution::Remote => {
+                for remote_child_node in remote_node.children() {
+                    self.signal.err_if_aborted()?;
+                    self.merge_remote_child_into_merged_node(
+                        &mut merged_node,
+                        Some(local_node),
+                        remote_node,
+                        remote_child_node,
+                    )?;
+                }
+                for local_child_node in local_node.children() {
+                    self.signal.err_if_aborted()?;
+                    self.merge_local_child_into_merged_node(
+                        &mut merged_node,
+                        local_node,
+                        Some(remote_node),
+                        local_child_node,
+                    )?;
+                }
+            }
+
+            ConflictResolution::Unchanged => {
+                // The children are the same, so we only need to merge one side.
+                for (local_child_node, remote_child_node) in
+                    local_node.children().zip(remote_node.children())
+                {
+                    self.signal.err_if_aborted()?;
+                    self.merge_unchanged_child_into_merged_node(
+                        &mut merged_node,
+                        local_node,
+                        local_child_node,
+                        remote_node,
+                        remote_child_node,
+                    )?;
+                }
+            }
+        }
+
+        if local_node.diverged() {
+            merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+        }
+
+        if remote_node.diverged() || remote_node.validity != Validity::Valid {
+            // Flag remotely diverged and invalid items for reupload.
+            merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+        }
+
+        Ok(merged_node)
+    }
+
+    /// Merges two nodes with the same parents and positions.
+    ///
+    /// Unlike items that have been moved, or exist only on one side, unchanged
+    /// children can be merged directly.
+    fn merge_unchanged_child_into_merged_node(
+        &mut self,
+        merged_node: &mut MergedNode<'t>,
+        local_parent_node: Node<'t>,
+        local_child_node: Node<'t>,
+        remote_parent_node: Node<'t>,
+        remote_child_node: Node<'t>,
+    ) -> Result<()> {
+        assert!(
+            !self.merged_guids.contains(&local_child_node.guid),
+            "Unchanged local child shouldn't have been merged"
+        );
+        assert!(
+            !self.merged_guids.contains(&remote_child_node.guid),
+            "Unchanged remote child shouldn't have been merged"
+        );
+
+        // Even though the child exists on both sides, it might still be
+        // non-syncable or invalid, so we need to check for structure
+        // changes.
+        let local_structure_change = self.check_for_local_structure_change_of_remote_node(
+            merged_node,
+            remote_parent_node,
+            remote_child_node,
+        )?;
+        let remote_structure_change = self.check_for_remote_structure_change_of_local_node(
+            merged_node,
+            local_parent_node,
+            local_child_node,
+        )?;
+        match (local_structure_change, remote_structure_change) {
+            (StructureChange::Deleted, StructureChange::Deleted) => {
+                // The child is deleted on both sides. We'll need to reupload
+                // and apply a new structure.
+                merged_node.merge_state = merged_node
+                    .merge_state
+                    .with_new_local_structure()
+                    .with_new_remote_structure();
+            }
+            (StructureChange::Deleted, _) => {
+                // The child is deleted locally, but not remotely, so we only
+                // need to reupload a new structure.
+                merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+            }
+            (_, StructureChange::Deleted) => {
+                // The child is deleted remotely, so we only need to apply a
+                // new local structure.
+                merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+            }
+            (_, _) => {
+                // The child exists on both sides, so merge it now. If the GUID
+                // changes because it's invalid, we'll need to reapply the
+                // child, and reupload the child and its parent.
+                let mut merged_child_node =
+                    self.two_way_merge(local_child_node, remote_child_node)?;
+                if merged_child_node.local_guid_changed() {
+                    merged_child_node.merge_state =
+                        merged_child_node.merge_state.with_new_local_structure();
+                }
+                if merged_node.remote_guid_changed() {
+                    // The merged parent's GUID changed; flag the child for
+                    // reupload with a new `parentid`.
+                    merged_child_node.merge_state =
+                        merged_child_node.merge_state.with_new_remote_structure();
+                }
+                if merged_child_node.remote_guid_changed() {
+                    // The merged child's GUID changed; flag the parent for
+                    // reupload with new `children`.
+                    merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+                }
+                merged_node.merged_children.push(merged_child_node);
+                self.structure_counts.merged_nodes += 1;
+            }
+        }
+
+        Ok(())
+    }
+
+    /// Merges a remote child node into a merged folder node. This handles the
+    /// following cases:
+    ///
+    /// - The remote child is locally deleted. We recursively move all of its
+    ///   descendants that don't exist locally to the merged folder.
+    /// - The remote child doesn't exist locally, but has a content match in the
+    ///   corresponding local folder. We dedupe the local child to the remote
+    ///   child.
+    /// - The remote child exists locally, but in a different folder. We compare
+    ///   merge flags and timestamps to decide where to keep the child.
+    /// - The remote child exists locally, and in the same folder. We merge the
+    ///   local and remote children.
+    ///
+    /// This is the inverse of `merge_local_child_into_merged_node`.
+    fn merge_remote_child_into_merged_node(
+        &mut self,
+        merged_node: &mut MergedNode<'t>,
+        local_parent_node: Option<Node<'t>>,
+        remote_parent_node: Node<'t>,
+        remote_child_node: Node<'t>,
+    ) -> Result<()> {
+        if self.merged_guids.contains(&remote_child_node.guid) {
+            trace!(
+                self.driver,
+                "Remote child {} already seen in another folder and merged",
+                remote_child_node
+            );
+            // Omitting a remote child that we already merged locally means we
+            // have a new remote structure.
+            merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+            return Ok(());
+        }
+
+        trace!(
+            self.driver,
+            "Merging remote child {} of {} into {}",
+            remote_child_node,
+            remote_parent_node,
+            merged_node
+        );
+
+        // Check if the remote child is locally deleted. and move all
+        // descendants that aren't also remotely deleted to the merged node.
+        // This handles the case where a user deletes a folder on this device,
+        // and adds a bookmark to the same folder on another device. We want to
+        // keep the folder deleted, but we also don't want to lose the new
+        // bookmark, so we move the bookmark to the deleted folder's parent.
+        if self.check_for_local_structure_change_of_remote_node(
+            merged_node,
+            remote_parent_node,
+            remote_child_node,
+        )? == StructureChange::Deleted
+        {
+            // Flag the merged parent for reupload, since we deleted the
+            // remote child.
+            merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+            return Ok(());
+        }
+
+        // The remote child isn't locally deleted. Does it exist in the local tree?
+        if let Some(local_child_node) = self.local_tree.node_for_guid(&remote_child_node.guid) {
+            // The remote child exists in the local tree. Did it move?
+            let local_parent_node = local_child_node
+                .parent()
+                .expect("Can't merge existing remote child without local parent");
+
+            trace!(
+                self.driver,
+                "Remote child {} exists locally in {} and remotely in {}",
+                remote_child_node,
+                local_parent_node,
+                remote_parent_node
+            );
+
+            if self.remote_tree.is_deleted(&local_parent_node.guid) {
+                trace!(
+                    self.driver,
+                    "Unconditionally taking remote move for {} to {} because local parent {} is \
+                     deleted remotely",
+                    remote_child_node,
+                    remote_parent_node,
+                    local_parent_node
+                );
+
+                let mut merged_child_node =
+                    self.two_way_merge(local_child_node, remote_child_node)?;
+                merged_child_node.merge_state =
+                    merged_child_node.merge_state.with_new_local_structure();
+                if merged_node.remote_guid_changed() {
+                    // If the parent's GUID changed, flag the child for reupload, so that
+                    // its `parentid` is correct.
+                    merged_child_node.merge_state =
+                        merged_child_node.merge_state.with_new_remote_structure();
+                }
+                if merged_child_node.remote_guid_changed() {
+                    // If the child's GUID changed, flag the parent for reupload, so that
+                    // its `children` are correct.
+                    merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+                }
+                merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+                merged_node.merged_children.push(merged_child_node);
+                self.structure_counts.merged_nodes += 1;
+                return Ok(());
+            }
+
+            match self.resolve_structure_conflict(
+                local_parent_node,
+                local_child_node,
+                remote_parent_node,
+                remote_child_node,
+            ) {
+                ConflictResolution::Local => {
+                    // The local move is newer, so we ignore the remote move.
+                    // We'll merge the remote child later, when we walk its new
+                    // local parent.
+                    trace!(
+                        self.driver,
+                        "Remote child {} moved locally to {} and remotely to {}; \
+                         keeping child in newer local parent and position",
+                        remote_child_node,
+                        local_parent_node,
+                        remote_parent_node
+                    );
+
+                    // Flag the old parent for reupload, since we're moving
+                    // the remote child. Note that, since we only flag the
+                    // remote parent here, we don't need to handle
+                    // reparenting and repositioning separately.
+                    merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+                }
+
+                ConflictResolution::Remote | ConflictResolution::Unchanged => {
+                    // The remote move is newer, so we merge the remote
+                    // child now and ignore the local move.
+                    let mut merged_child_node = if local_parent_node.guid != remote_parent_node.guid
+                    {
+                        trace!(
+                            self.driver,
+                            "Remote child {} reparented locally to {} and remotely to {}; \
+                             keeping child in newer remote parent",
+                            remote_child_node,
+                            local_parent_node,
+                            remote_parent_node
+                        );
+                        let mut merged_child_node =
+                            self.two_way_merge(local_child_node, remote_child_node)?;
+                        merged_child_node.merge_state =
+                            merged_child_node.merge_state.with_new_local_structure();
+                        merged_child_node
+                    } else {
+                        trace!(
+                            self.driver,
+                            "Remote child {} repositioned locally in {} and remotely in {}; \
+                             keeping child in newer remote position",
+                            remote_child_node,
+                            local_parent_node,
+                            remote_parent_node
+                        );
+                        self.two_way_merge(local_child_node, remote_child_node)?
+                    };
+                    if merged_child_node.local_guid_changed() {
+                        merged_child_node.merge_state =
+                            merged_child_node.merge_state.with_new_local_structure();
+                    }
+                    if merged_node.remote_guid_changed() {
+                        // The merged parent's GUID changed; flag the child for
+                        // reupload with a new `parentid`.
+                        merged_child_node.merge_state =
+                            merged_child_node.merge_state.with_new_remote_structure();
+                    }
+                    if merged_child_node.remote_guid_changed() {
+                        // The merged child's GUID changed; flag the parent for
+                        // reupload with new `children`.
+                        merged_node.merge_state =
+                            merged_node.merge_state.with_new_remote_structure();
+                    }
+                    merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+                    merged_node.merged_children.push(merged_child_node);
+                    self.structure_counts.merged_nodes += 1;
+                }
+            }
+
+            return Ok(());
+        }
+
+        // Remote child is not a root, and doesn't exist locally. Try to find a
+        // content match in the containing folder, and dedupe the local item if
+        // we can.
+        trace!(
+            self.driver,
+            "Remote child {} doesn't exist locally; looking for local content match",
+            remote_child_node
+        );
+
+        let mut merged_child_node = if let Some(local_child_node_by_content) = self
+            .find_local_node_matching_remote_node(
+                merged_node,
+                local_parent_node,
+                remote_parent_node,
+                remote_child_node,
+            )? {
+            self.two_way_merge(local_child_node_by_content, remote_child_node)
+        } else {
+            self.merge_remote_only_node(remote_child_node)
+        }?;
+        if merged_child_node.local_guid_changed() {
+            merged_child_node.merge_state =
+                merged_child_node.merge_state.with_new_local_structure();
+        }
+        if merged_node.remote_guid_changed() {
+            merged_child_node.merge_state =
+                merged_child_node.merge_state.with_new_remote_structure();
+        }
+        if merged_child_node.remote_guid_changed() {
+            merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+        }
+        merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+        merged_node.merged_children.push(merged_child_node);
+        self.structure_counts.merged_nodes += 1;
+        Ok(())
+    }
+
+    /// Merges a local child node into a merged folder node.
+    ///
+    /// This is the inverse of `merge_remote_child_into_merged_node`.
+    fn merge_local_child_into_merged_node(
+        &mut self,
+        merged_node: &mut MergedNode<'t>,
+        local_parent_node: Node<'t>,
+        remote_parent_node: Option<Node<'t>>,
+        local_child_node: Node<'t>,
+    ) -> Result<()> {
+        if self.merged_guids.contains(&local_child_node.guid) {
+            // We already merged the child when we walked another folder. Since
+            // a tree can't have duplicate GUIDs, we must have merged the remote
+            // child, so we have a new local structure.
+            trace!(
+                self.driver,
+                "Local child {} already seen in another folder and merged",
+                local_child_node
+            );
+            merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+            return Ok(());
+        }
+
+        trace!(
+            self.driver,
+            "Merging local child {} of {} into {}",
+            local_child_node,
+            local_parent_node,
+            merged_node
+        );
+
+        // Check if the local child is remotely deleted, and move any new local
+        // descendants to the merged node if so.
+        if self.check_for_remote_structure_change_of_local_node(
+            merged_node,
+            local_parent_node,
+            local_child_node,
+        )? == StructureChange::Deleted
+        {
+            // Since we're merging local nodes, we don't need to flag the merged
+            // parent for reupload.
+            merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+            return Ok(());
+        }
+
+        // At this point, we know the local child isn't deleted. See if it
+        // exists in the remote tree.
+        if let Some(remote_child_node) = self.remote_tree.node_for_guid(&local_child_node.guid) {
+            // The local child exists remotely. It must have moved; otherwise, we
+            // would have seen it when we walked the remote children.
+            let remote_parent_node = remote_child_node
+                .parent()
+                .expect("Can't merge existing local child without remote parent");
+
+            trace!(
+                self.driver,
+                "Local child {} exists locally in {} and remotely in {}",
+                local_child_node,
+                local_parent_node,
+                remote_parent_node
+            );
+
+            if self.local_tree.is_deleted(&remote_parent_node.guid) {
+                trace!(
+                    self.driver,
+                    "Unconditionally taking local move for {} to {} because remote parent {} is \
+                     deleted locally",
+                    local_child_node,
+                    local_parent_node,
+                    remote_parent_node
+                );
+
+                // Merge and flag the new parent *and the locally moved child* for
+                // reupload. The parent references the child in its `children`; the
+                // child points back to the parent in its `parentid`.
+                //
+                // Reuploading the child isn't necessary for newer Desktops, which
+                // ignore the child's `parentid` and use the parent's `children`.
+                //
+                // However, older Desktop and Android use the child's `parentid` as
+                // canonical, while iOS is stricter and requires both to match.
+                let mut merged_child_node =
+                    self.two_way_merge(local_child_node, remote_child_node)?;
+                if merged_child_node.local_guid_changed() {
+                    merged_child_node.merge_state =
+                        merged_child_node.merge_state.with_new_local_structure();
+                }
+                merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+                merged_child_node.merge_state =
+                    merged_child_node.merge_state.with_new_remote_structure();
+                merged_node.merged_children.push(merged_child_node);
+                self.structure_counts.merged_nodes += 1;
+                return Ok(());
+            }
+
+            match self.resolve_structure_conflict(
+                local_parent_node,
+                local_child_node,
+                remote_parent_node,
+                remote_child_node,
+            ) {
+                ConflictResolution::Local => {
+                    // The local move is newer, so we merge the local child now
+                    // and ignore the remote move.
+                    if local_parent_node.guid != remote_parent_node.guid {
+                        // The child moved to a different folder.
+                        trace!(
+                            self.driver,
+                            "Local child {} reparented locally to {} and remotely to {}; \
+                             keeping child in newer local parent",
+                            local_child_node,
+                            local_parent_node,
+                            remote_parent_node
+                        );
+
+                        // Merge and flag both the new parent and child for
+                        // reupload. See above for why.
+                        let mut merged_child_node =
+                            self.two_way_merge(local_child_node, remote_child_node)?;
+                        if merged_child_node.local_guid_changed() {
+                            merged_child_node.merge_state =
+                                merged_child_node.merge_state.with_new_local_structure();
+                        }
+                        merged_node.merge_state =
+                            merged_node.merge_state.with_new_remote_structure();
+                        merged_child_node.merge_state =
+                            merged_child_node.merge_state.with_new_remote_structure();
+                        merged_node.merged_children.push(merged_child_node);
+                        self.structure_counts.merged_nodes += 1;
+                    } else {
+                        trace!(
+                            self.driver,
+                            "Local child {} repositioned locally in {} and remotely in {}; \
+                             keeping child in newer local position",
+                            local_child_node,
+                            local_parent_node,
+                            remote_parent_node
+                        );
+
+                        // For position changes in the same folder, we only need to
+                        // merge and flag the parent for reupload...
+                        let mut merged_child_node =
+                            self.two_way_merge(local_child_node, remote_child_node)?;
+                        if merged_child_node.local_guid_changed() {
+                            merged_child_node.merge_state =
+                                merged_child_node.merge_state.with_new_local_structure();
+                        }
+                        merged_node.merge_state =
+                            merged_node.merge_state.with_new_remote_structure();
+                        if merged_node.remote_guid_changed() {
+                            // ...Unless the merged parent's GUID also changed,
+                            // in which case we also need to flag the
+                            // repositioned child for reupload, so that its
+                            // `parentid` is correct.
+                            merged_child_node.merge_state =
+                                merged_child_node.merge_state.with_new_remote_structure();
+                        }
+
+                        merged_node.merged_children.push(merged_child_node);
+                        self.structure_counts.merged_nodes += 1;
+                    }
+                }
+
+                ConflictResolution::Remote | ConflictResolution::Unchanged => {
+                    // The remote move is newer, so we ignore the local
+                    // move. We'll merge the local child later, when we
+                    // walk its new remote parent.
+                    if local_parent_node.guid != remote_parent_node.guid {
+                        trace!(
+                            self.driver,
+                            "Local child {} reparented locally to {} and remotely to {}; \
+                             keeping child in newer remote parent",
+                            local_child_node,
+                            local_parent_node,
+                            remote_parent_node
+                        );
+                    } else {
+                        trace!(
+                            self.driver,
+                            "Local child {} repositioned locally in {} and remotely in {}; \
+                             keeping child in newer remote position",
+                            local_child_node,
+                            local_parent_node,
+                            remote_parent_node
+                        );
+                    }
+                    merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+                }
+            }
+
+            return Ok(());
+        }
+
+        // Local child is not a root, and doesn't exist remotely. Try to find a
+        // content match in the containing folder, and dedupe the local item if
+        // we can.
+        trace!(
+            self.driver,
+            "Local child {} doesn't exist remotely; looking for remote content match",
+            local_child_node
+        );
+
+        let merged_child_node = if let Some(remote_child_node_by_content) = self
+            .find_remote_node_matching_local_node(
+                merged_node,
+                local_parent_node,
+                remote_parent_node,
+                local_child_node,
+            )? {
+            // The local child has a remote content match, so take the remote GUID
+            // and merge.
+            let mut merged_child_node =
+                self.two_way_merge(local_child_node, remote_child_node_by_content)?;
+            if merged_child_node.local_guid_changed() {
+                merged_child_node.merge_state =
+                    merged_child_node.merge_state.with_new_local_structure();
+            }
+            if merged_node.remote_guid_changed() {
+                merged_child_node.merge_state =
+                    merged_child_node.merge_state.with_new_remote_structure();
+            }
+            if merged_child_node.remote_guid_changed() {
+                merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+            }
+            merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
+            merged_child_node
+        } else {
+            // The local child doesn't exist remotely, so flag the merged parent and
+            // new child for upload, and walk its descendants.
+            let mut merged_child_node = self.merge_local_only_node(local_child_node)?;
+            if merged_child_node.local_guid_changed() {
+                merged_child_node.merge_state =
+                    merged_child_node.merge_state.with_new_local_structure();
+            }
+            merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
+            merged_child_node.merge_state =
+                merged_child_node.merge_state.with_new_remote_structure();
+            merged_child_node
+        };
+        merged_node.merged_children.push(merged_child_node);
+        self.structure_counts.merged_nodes += 1;
+        Ok(())
+    }
+
+    /// Determines which side to prefer, and which children to merge first,
+    /// for an item that exists on both sides.
+    fn resolve_value_conflict(
+        &self,
+        local_node: Node<'t>,
+        remote_node: Node<'t>,
+    ) -> (ConflictResolution, ConflictResolution) {
+        if remote_node.is_root() {
+            // Don't touch the Places root; it's not synced, anyway.
+            return (ConflictResolution::Unchanged, ConflictResolution::Local);
+        }
+
+        match (local_node.needs_merge, remote_node.needs_merge) {
+            (true, true) => {
+                // The item changed locally and remotely.
+                let item = if local_node.is_built_in_root() {
+                    // For roots, we always prefer the local side for item
+                    // changes, like the title (bug 1432614).
+                    ConflictResolution::Local
+                } else {
+                    // For other items, we check the validity to decide
+                    // which side to take.
+                    match (local_node.validity, remote_node.validity) {
+                        // If both are invalid, it doesn't matter which side
+                        // we pick; the item will be deleted, anyway.
+                        (Validity::Replace, Validity::Replace) => ConflictResolution::Unchanged,
+                        // If only one side is invalid, pick the other side.
+                        // This loses changes from that side, but we can't
+                        // apply or upload those changes, anyway.
+                        (Validity::Replace, _) => ConflictResolution::Remote,
+                        (_, Validity::Replace) => ConflictResolution::Local,
+                        (_, _) => {
+                            // Otherwise, the item is either valid, or valid
+                            // but needs to be reuploaded or reapplied, so
+                            // compare timestamps to decide which side is newer.
+                            if local_node.age < remote_node.age {
+                                ConflictResolution::Local
+                            } else {
+                                ConflictResolution::Remote
+                            }
+                        }
+                    }
+                };
+                // For children, it's easier: we always use the newer side, even
+                // if we're taking local changes for the item.
+                let children = if local_node.has_matching_children(remote_node) {
+                    ConflictResolution::Unchanged
+                } else if local_node.age < remote_node.age {
+                    // The local change is newer, so merge local children first,
+                    // followed by remaining unmerged remote children.
+                    ConflictResolution::Local
+                } else {
+                    // The remote change is newer, so walk and merge remote
+                    // children first, then remaining local children.
+                    ConflictResolution::Remote
+                };
+                (item, children)
+            }
+
+            (true, false) => {
+                // The item changed locally, but not remotely. Prefer the local
+                // item, then merge local children first, followed by remote
+                // children.
+                let item = match local_node.validity {
+                    Validity::Valid | Validity::Reupload => ConflictResolution::Local,
+                    Validity::Replace => ConflictResolution::Remote,
+                };
+                let children = if local_node.has_matching_children(remote_node) {
+                    ConflictResolution::Unchanged
+                } else {
+                    ConflictResolution::Local
+                };
+                (item, children)
+            }
+
+            (false, true) => {
+                // The item changed remotely, but not locally.
+                let item = if local_node.is_built_in_root() {
+                    // For roots, we ignore remote item changes.
+                    ConflictResolution::Unchanged
+                } else {
+                    match remote_node.validity {
+                        Validity::Valid | Validity::Reupload => ConflictResolution::Remote,
+                        // And, for invalid remote items, we must reupload the
+                        // local side. This _loses remote changes_, but we can't
+                        // apply those changes, anyway.
+                        Validity::Replace => ConflictResolution::Local,
+                    }
+                };
+                let children = if local_node.has_matching_children(remote_node) {
+                    ConflictResolution::Unchanged
+                } else {
+                    ConflictResolution::Remote
+                };
+                // For children, we always use the remote side.
+                (item, children)
+            }
+
+            (false, false) => {
+                let item = match (local_node.validity, remote_node.validity) {
+                    (Validity::Replace, Validity::Replace) => ConflictResolution::Unchanged,
+                    (_, Validity::Replace) => ConflictResolution::Local,
+                    (Validity::Replace, _) => ConflictResolution::Remote,
+                    (_, _) => ConflictResolution::Unchanged,
+                };
+                // If the child lists are identical, the structure is unchanged.
+                // Otherwise, the children differ even though the items aren't
+                // flagged as unmerged, so we prefer the newer side.
+                let children = if local_node.has_matching_children(remote_node) {
+                    ConflictResolution::Unchanged
+                } else if local_node.age < remote_node.age {
+                    ConflictResolution::Local
+                } else {
+                    ConflictResolution::Remote
+                };
+                (item, children)
+            }
+        }
+    }
+
+    /// Determines where to keep a child of a folder that exists on both sides.
+    fn resolve_structure_conflict(
+        &self,
+        local_parent_node: Node<'t>,
+        local_child_node: Node<'t>,
+        remote_parent_node: Node<'t>,
+        remote_child_node: Node<'t>,
+    ) -> ConflictResolution {
+        if remote_child_node.is_built_in_root() {
+            // Always use the local parent and position for roots.
+            return ConflictResolution::Local;
+        }
+
+        match (
+            local_parent_node.needs_merge,
+            remote_parent_node.needs_merge,
+        ) {
+            (true, true) => {
+                // If both parents changed, compare timestamps to decide where
+                // to keep the local child.
+                let latest_local_age = local_child_node.age.min(local_parent_node.age);
+                let latest_remote_age = remote_child_node.age.min(remote_parent_node.age);
+
+                if latest_local_age < latest_remote_age {
+                    ConflictResolution::Local
+                } else {
+                    ConflictResolution::Remote
+                }
+            }
+
+            // If only the local or remote parent changed, keep the child in its
+            // new parent.
+            (true, false) => ConflictResolution::Local,
+            (false, true) => ConflictResolution::Remote,
+
+            (false, false) => ConflictResolution::Unchanged,
+        }
+    }
+
+    /// Checks if a remote node is locally moved or deleted, and reparents any
+    /// descendants that aren't also remotely deleted to the merged node.
+    ///
+    /// This is the inverse of
+    /// `check_for_remote_structure_change_of_local_node`.
+    fn check_for_local_structure_change_of_remote_node(
+        &mut self,
+        merged_node: &mut MergedNode<'t>,
+        remote_parent_node: Node<'t>,
+        remote_node: Node<'t>,
+    ) -> Result<StructureChange> {
+        if !remote_node.is_syncable() {
+            // If the remote node is known to be non-syncable, we unconditionally
+            // delete it, even if it's syncable or moved locally.
+            trace!(
+                self.driver,
+                "Deleting non-syncable remote node {}",
+                remote_node
+            );
+            return self.delete_remote_node(merged_node, remote_node);
+        }
+
+        if !self.local_tree.is_deleted(&remote_node.guid) {
+            if let Some(local_node) = self.local_tree.node_for_guid(&remote_node.guid) {
+                if !local_node.is_syncable() {
+                    // The remote node is syncable, but the local node is
+                    // non-syncable. Unconditionally delete it.
+                    trace!(
+                        self.driver,
+                        "Remote node {} is syncable, but local node {} isn't; deleting",
+                        remote_node,
+                        local_node
+                    );
+                    return self.delete_remote_node(merged_node, remote_node);
+                }
+                if local_node.validity == Validity::Replace
+                    && remote_node.validity == Validity::Replace
+                {
+                    // The nodes are invalid on both sides, so we can't apply
+                    // or reupload a valid copy. Delete it.
+                    return self.delete_remote_node(merged_node, remote_node);
+                }
+                let local_parent_node = local_node
+                    .parent()
+                    .expect("Can't check for structure changes without local parent");
+                if local_parent_node.guid != remote_parent_node.guid {
+                    return Ok(StructureChange::Moved);
+                }
+                return Ok(StructureChange::Unchanged);
+            }
+            if remote_node.validity == Validity::Replace {
+                // The remote node is invalid and doesn't exist locally, so we
+                // can't reupload a valid copy. We must delete it.
+                return self.delete_remote_node(merged_node, remote_node);
+            }
+            return Ok(StructureChange::Unchanged);
+        }
+
+        if remote_node.validity == Validity::Replace {
+            // The remote node is invalid and deleted locally, so we can't
+            // reupload a valid copy. Delete it.
+            return self.delete_remote_node(merged_node, remote_node);
+        }
+
+        if remote_node.is_built_in_root() {
+            // If the remote node is a content root, don't delete it locally.
+            return Ok(StructureChange::Unchanged);
+        }
+
+        if remote_node.needs_merge {
+            if !remote_node.is_folder() {
+                // If a non-folder child is deleted locally and changed remotely, we
+                // ignore the local deletion and take the remote child.
+                trace!(
+                    self.driver,
+                    "Remote non-folder {} deleted locally and changed remotely; \
+                     taking remote change",
+                    remote_node
+                );
+                self.structure_counts.remote_revives += 1;
+                return Ok(StructureChange::Unchanged);
+            }
+            // For folders, we always take the local deletion and relocate remotely
+            // changed grandchildren to the merged node. We could use the remote
+            // tree to revive the child folder, but it's easier to relocate orphaned
+            // grandchildren than to partially revive the child folder.
+            trace!(
+                self.driver,
+                "Remote folder {} deleted locally and changed remotely; \
+                 taking local deletion",
+                remote_node
+            );
+            self.structure_counts.local_deletes += 1;
+        } else {
+            trace!(
+                self.driver,
+                "Remote node {} deleted locally and not changed remotely; \
+                 taking local deletion",
+                remote_node
+            );
+        }
+
+        // Take the local deletion and relocate any new remote descendants to the
+        // merged node.
+        self.delete_remote_node(merged_node, remote_node)
+    }
+
+    /// 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
+    /// `check_for_local_structure_change_of_remote_node`.
+    fn check_for_remote_structure_change_of_local_node(
+        &mut self,
+        merged_node: &mut MergedNode<'t>,
+        local_parent_node: Node<'t>,
+        local_node: Node<'t>,
+    ) -> Result<StructureChange> {
+        if !local_node.is_syncable() {
+            // If the local node is known to be non-syncable, we unconditionally
+            // delete it, even if it's syncable or moved remotely.
+            trace!(
+                self.driver,
+                "Deleting non-syncable local node {}",
+                local_node
+            );
+            return self.delete_local_node(merged_node, local_node);
+        }
+
+        if !self.remote_tree.is_deleted(&local_node.guid) {
+            if let Some(remote_node) = self.remote_tree.node_for_guid(&local_node.guid) {
+                if !remote_node.is_syncable() {
+                    // The local node is syncable, but the remote node is not.
+                    // 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 it.
+                    trace!(
+                        self.driver,
+                        "Local node {} is syncable, but remote node {} isn't; deleting",
+                        local_node,
+                        remote_node
+                    );
+                    return self.delete_local_node(merged_node, local_node);
+                }
+                if remote_node.validity == Validity::Replace
+                    && local_node.validity == Validity::Replace
+                {
+                    // The nodes are invalid on both sides, so we can't replace
+                    // the local copy with a remote one. Delete it.
+                    return self.delete_local_node(merged_node, local_node);
+                }
+                // Otherwise, either both nodes are valid; or the remote node
+                // is invalid but the local node is valid, so we can reupload a
+                // valid copy.
+                let remote_parent_node = remote_node
+                    .parent()
+                    .expect("Can't check for structure changes without remote parent");
+                if remote_parent_node.guid != local_parent_node.guid {
+                    return Ok(StructureChange::Moved);
+                }
+                return Ok(StructureChange::Unchanged);
+            }
+            if local_node.validity == Validity::Replace {
+                // The local node is invalid and doesn't exist remotely, so
+                // we can't replace the local copy. Delete it.
+                return self.delete_local_node(merged_node, local_node);
+            }
+            return Ok(StructureChange::Unchanged);
+        }
+
+        if local_node.validity == Validity::Replace {
+            // The local node is invalid and deleted remotely, so we can't
+            // replace the local copy. Delete it.
+            return self.delete_local_node(merged_node, local_node);
+        }
+
+        if local_node.is_built_in_root() {
+            // If the local node is a content root, don't delete it remotely.
+            return Ok(StructureChange::Unchanged);
+        }
+
+        // See `check_for_local_structure_change_of_remote_node` for an
+        // explanation of how we decide to take or ignore a deletion.
+        if local_node.needs_merge {
+            if !local_node.is_folder() {
+                trace!(
+                    self.driver,
+                    "Local non-folder {} deleted remotely and changed locally; taking local change",
+                    local_node
+                );
+                self.structure_counts.local_revives += 1;
+                return Ok(StructureChange::Unchanged);
+            }
+            trace!(
+                self.driver,
+                "Local folder {} deleted remotely and changed locally; taking remote deletion",
+                local_node
+            );
+            self.structure_counts.remote_deletes += 1;
+        } else {
+            trace!(
+                self.driver,
+                "Local node {} deleted remotely and not changed locally; taking remote deletion",
+                local_node
+            );
+        }
+
+        // Take the remote deletion and relocate any new local descendants to the
+        // merged node.
+        self.delete_local_node(merged_node, local_node)
+    }
+
+    /// Marks a remote node as deleted, and relocates all remote descendants
+    /// that aren't also locally deleted to the merged node. This avoids data
+    /// loss if the user adds a bookmark to a folder on another device, and
+    /// deletes that folder locally.
+    ///
+    /// This is the inverse of `delete_local_node`.
+    fn delete_remote_node(
+        &mut self,
+        merged_node: &mut MergedNode<'t>,
+        remote_node: Node<'t>,
+    ) -> Result<StructureChange> {
+        self.delete_remotely.insert(remote_node.guid.clone());
+        for remote_child_node in remote_node.children() {
+            self.signal.err_if_aborted()?;
+            if self.merged_guids.contains(&remote_child_node.guid) {
+                trace!(
+                    self.driver,
+                    "Remote child {} can't be an orphan; already merged",
+                    remote_child_node
+                );
+                continue;
+            }
+            match self.check_for_local_structure_change_of_remote_node(
+                merged_node,
+                remote_node,
+                remote_child_node,
+            )? {
+                StructureChange::Moved | StructureChange::Deleted => {
+                    // The remote child is already moved or deleted locally, so we should
+                    // ignore it instead of treating it as a remote orphan.
+                    continue;
+                }
+                StructureChange::Unchanged => {
+                    trace!(
+                        self.driver,
+                        "Relocating remote orphan {} to {}",
+                        remote_child_node,
+                        merged_node
+                    );
+
+                    // Flag the new parent and moved remote orphan for reupload.
+                    let mut merged_orphan_node = if let Some(local_child_node) =
+                        self.local_tree.node_for_guid(&remote_child_node.guid)
+                    {
+                        self.two_way_merge(local_child_node, remote_child_node)
+                    } else {
+                        self.merge_remote_only_node(remote_child_node)
+                    }?;
+                    merged_node.merge_state = merged_node
+                        .merge_state
+                        .with_new_local_structure()
+                        .with_new_remote_structure();
+                    merged_orphan_node.merge_state = merged_orphan_node
+                        .merge_state
+                        .with_new_local_structure()
+                        .with_new_remote_structure();
+                    merged_node.merged_children.push(merged_orphan_node);
+                    self.structure_counts.merged_nodes += 1;
+                }
+            }
+        }
+        Ok(StructureChange::Deleted)
+    }
+
+    /// Marks a local node as deleted, and relocates all local descendants
+    /// that aren't also remotely deleted to the merged node.
+    ///
+    /// This is the inverse of `delete_remote_node`.
+    fn delete_local_node(
+        &mut self,
+        merged_node: &mut MergedNode<'t>,
+        local_node: Node<'t>,
+    ) -> Result<StructureChange> {
+        self.delete_locally.insert(local_node.guid.clone());
+        for local_child_node in local_node.children() {
+            self.signal.err_if_aborted()?;
+            if self.merged_guids.contains(&local_child_node.guid) {
+                trace!(
+                    self.driver,
+                    "Local child {} can't be an orphan; already merged",
+                    local_child_node
+                );
+                continue;
+            }
+            match self.check_for_remote_structure_change_of_local_node(
+                merged_node,
+                local_node,
+                local_child_node,
+            )? {
+                StructureChange::Moved | StructureChange::Deleted => {
+                    // The local child is already moved or deleted remotely, so we should
+                    // ignore it instead of treating it as a local orphan.
+                    continue;
+                }
+                StructureChange::Unchanged => {
+                    trace!(
+                        self.driver,
+                        "Relocating local orphan {} to {}",
+                        local_child_node,
+                        merged_node
+                    );
+
+                    // Flag the new parent and moved local orphan for reupload.
+                    let mut merged_orphan_node = if let Some(remote_child_node) =
+                        self.remote_tree.node_for_guid(&local_child_node.guid)
+                    {
+                        self.two_way_merge(local_child_node, remote_child_node)
+                    } else {
+                        self.merge_local_only_node(local_child_node)
+                    }?;
+                    merged_node.merge_state = merged_node
+                        .merge_state
+                        .with_new_local_structure()
+                        .with_new_remote_structure();
+                    merged_orphan_node.merge_state = merged_orphan_node
+                        .merge_state
+                        .with_new_local_structure()
+                        .with_new_remote_structure();
+                    merged_node.merged_children.push(merged_orphan_node);
+                    self.structure_counts.merged_nodes += 1;
+                }
+            }
+        }
+        Ok(StructureChange::Deleted)
+    }
+
+    /// 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.
+    ///
+    /// Recall that we match items by GUID as we walk down the tree. If a GUID
+    /// on one side doesn't exist on the other, we fall back to a content
+    /// match in the same folder.
+    ///
+    /// This method is called the first time that
+    /// `find_remote_node_matching_local_node` merges a local child that
+    /// doesn't exist remotely, and
+    /// the first time that `find_local_node_matching_remote_node` merges a
+    /// remote child that doesn't exist locally.
+    ///
+    /// Finding all possible dupes is O(m + n) in the worst case, where `m` is
+    /// the number of local children, and `n` is the number of remote
+    /// children. We cache matches in
+    /// `matching_dupes_by_local_parent_guid`, so deduping all
+    /// remaining children of the same folder, on both sides, only needs two
+    /// O(1) map lookups per child.
+    fn find_all_matching_dupes_in_folders(
+        &self,
+        local_parent_node: Node<'t>,
+        remote_parent_node: Node<'t>,
+    ) -> Result<MatchingDupes<'t>> {
+        let mut dupe_key_to_local_nodes: HashMap<DupeKey<'_>, VecDeque<_>> = HashMap::new();
+
+        for (local_position, local_child_node) in local_parent_node.children().enumerate() {
+            self.signal.err_if_aborted()?;
+            if local_child_node.is_built_in_root() {
+                trace!(
+                    self.driver,
+                    "Not deduping local built-in root {}",
+                    local_child_node
+                );
+                continue;
+            }
+            if self.remote_tree.mentions(&local_child_node.guid) {
+                trace!(
+                    self.driver,
+                    "Not deduping local child {}; already deleted or exists remotely",
+                    local_child_node
+                );
+                continue;
+            }
+            match local_child_node.content() {
+                Some(local_child_content) => {
+                    // Store matching local children in an array, in case multiple children
+                    // have the same dupe key (for example, a toolbar containing multiple
+                    // empty folders, as in bug 1213369).
+                    let dupe_key = match local_child_content {
+                        Content::Bookmark { .. } | Content::Folder { .. } => {
+                            DupeKey::WithoutPosition(local_child_content)
+                        }
+                        Content::Separator => {
+                            DupeKey::WithPosition(local_child_content, local_position)
+                        }
+                    };
+                    let local_nodes_for_key = dupe_key_to_local_nodes.entry(dupe_key).or_default();
+                    local_nodes_for_key.push_back(local_child_node);
+                }
+                None => {
+                    trace!(
+                        self.driver,
+                        "Not deduping local child {} without content info",
+                        local_child_node
+                    );
+                }
+            }
+        }
+
+        let mut local_to_remote = HashMap::new();
+        let mut remote_to_local = HashMap::new();
+
+        for (remote_position, remote_child_node) in remote_parent_node.children().enumerate() {
+            self.signal.err_if_aborted()?;
+            if remote_child_node.is_built_in_root() {
+                trace!(
+                    self.driver,
+                    "Not deduping remote built-in root {}",
+                    remote_child_node
+                );
+                continue;
+            }
+            if self.local_tree.mentions(&remote_child_node.guid) {
+                trace!(
+                    self.driver,
+                    "Not deduping remote child {}; already deleted or exists locally",
+                    remote_child_node
+                );
+                continue;
+            }
+            if remote_to_local.contains_key(&remote_child_node.guid) {
+                trace!(
+                    self.driver,
+                    "Not deduping remote child {}; already deduped",
+                    remote_child_node
+                );
+                continue;
+            }
+            // Note that we don't need to check if the remote node is deleted
+            // locally, because it wouldn't have local content entries if it
+            // were.
+            match remote_child_node.content() {
+                Some(remote_child_content) => {
+                    let dupe_key = match remote_child_content {
+                        Content::Bookmark { .. } | Content::Folder { .. } => {
+                            DupeKey::WithoutPosition(remote_child_content)
+                        }
+                        Content::Separator => {
+                            DupeKey::WithPosition(remote_child_content, remote_position)
+                        }
+                    };
+                    if let Some(local_nodes_for_key) = dupe_key_to_local_nodes.get_mut(&dupe_key) {
+                        if let Some(local_child_node) = local_nodes_for_key.pop_front() {
+                            trace!(
+                                self.driver,
+                                "Deduping local child {} to remote child {}",
+                                local_child_node,
+                                remote_child_node
+                            );
+                            local_to_remote
+                                .insert(local_child_node.guid.clone(), remote_child_node);
+                            remote_to_local
+                                .insert(remote_child_node.guid.clone(), local_child_node);
+                        } else {
+                            trace!(
+                                self.driver,
+                                "Not deduping remote child {}; no remaining local content matches",
+                                remote_child_node
+                            );
+                            continue;
+                        }
+                    } else {
+                        trace!(
+                            self.driver,
+                            "Not deduping remote child {}; no local content matches",
+                            remote_child_node
+                        );
+                        continue;
+                    }
+                }
+                None => {
+                    trace!(
+                        self.driver,
+                        "Not deduping remote child {} without content info",
+                        remote_child_node
+                    );
+                }
+            }
+        }
+
+        Ok((local_to_remote, remote_to_local))
+    }
+
+    /// Finds a remote node with a different GUID that matches the content of a
+    /// local node.
+    ///
+    /// This is the inverse of `find_local_node_matching_remote_node`.
+    fn find_remote_node_matching_local_node(
+        &mut self,
+        merged_node: &MergedNode<'t>,
+        local_parent_node: Node<'t>,
+        remote_parent_node: Option<Node<'t>>,
+        local_child_node: Node<'t>,
+    ) -> Result<Option<Node<'t>>> {
+        if let Some(remote_parent_node) = remote_parent_node {
+            let mut matching_dupes_by_local_parent_guid = mem::replace(
+                &mut self.matching_dupes_by_local_parent_guid,
+                HashMap::new(),
+            );
+            let new_remote_node = {
+                let (local_to_remote, _) = match matching_dupes_by_local_parent_guid
+                    .entry(local_parent_node.guid.clone())
+                {
+                    Entry::Occupied(entry) => entry.into_mut(),
+                    Entry::Vacant(entry) => {
+                        trace!(
+                            self.driver,
+                            "First local child {} doesn't exist remotely; \
+                             finding all matching dupes in local {} and remote {}",
+                            local_child_node,
+                            local_parent_node,
+                            remote_parent_node
+                        );
+                        let matching_dupes = self.find_all_matching_dupes_in_folders(
+                            local_parent_node,
+                            remote_parent_node,
+                        )?;
+                        entry.insert(matching_dupes)
+                    }
+                };
+                let new_remote_node = local_to_remote.get(&local_child_node.guid);
+                new_remote_node.map(|node| {
+                    self.structure_counts.dupes += 1;
+                    *node
+                })
+            };
+            self.matching_dupes_by_local_parent_guid = matching_dupes_by_local_parent_guid;
+            Ok(new_remote_node)
+        } else {
+            trace!(
+                self.driver,
+                "Merged node {} doesn't exist remotely; no potential dupes for local child {}",
+                merged_node,
+                local_child_node
+            );
+            Ok(None)
+        }
+    }
+
+    /// Finds a local node with a different GUID that matches the content of a
+    /// remote node.
+    ///
+    /// This is the inverse of `find_remote_node_matching_local_node`.
+    fn find_local_node_matching_remote_node(
+        &mut self,
+        merged_node: &MergedNode<'t>,
+        local_parent_node: Option<Node<'t>>,
+        remote_parent_node: Node<'t>,
+        remote_child_node: Node<'t>,
+    ) -> Result<Option<Node<'t>>> {
+        if let Some(local_parent_node) = local_parent_node {
+            let mut matching_dupes_by_local_parent_guid = mem::replace(
+                &mut self.matching_dupes_by_local_parent_guid,
+                HashMap::new(),
+            );
+            let new_local_node = {
+                let (_, remote_to_local) = match matching_dupes_by_local_parent_guid
+                    .entry(local_parent_node.guid.clone())
+                {
+                    Entry::Occupied(entry) => entry.into_mut(),
+                    Entry::Vacant(entry) => {
+                        trace!(
+                            self.driver,
+                            "First remote child {} doesn't exist locally; \
+                             finding all matching dupes in local {} and remote {}",
+                            remote_child_node,
+                            local_parent_node,
+                            remote_parent_node
+                        );
+                        let matching_dupes = self.find_all_matching_dupes_in_folders(
+                            local_parent_node,
+                            remote_parent_node,
+                        )?;
+                        entry.insert(matching_dupes)
+                    }
+                };
+                let new_local_node = remote_to_local.get(&remote_child_node.guid);
+                new_local_node.map(|node| {
+                    self.structure_counts.dupes += 1;
+                    *node
+                })
+            };
+            self.matching_dupes_by_local_parent_guid = matching_dupes_by_local_parent_guid;
+            Ok(new_local_node)
+        } else {
+            trace!(
+                self.driver,
+                "Merged node {} doesn't exist locally; no potential dupes for remote child {}",
+                merged_node,
+                remote_child_node
+            );
+            Ok(None)
+        }
+    }
+}
+
+/// The root of a merged tree, from which all merged nodes descend.
+#[derive(Debug)]
+pub struct MergedRoot<'t> {
+    local_tree: &'t Tree,
+    remote_tree: &'t Tree,
+    node: MergedNode<'t>,
+    merged_guids: HashSet<Guid>,
+    delete_locally: HashSet<Guid>,
+    delete_remotely: HashSet<Guid>,
+    structure_counts: StructureCounts,
+}
+
+impl<'t> MergedRoot<'t> {
+    /// Returns the root node.
+    #[inline]
+    pub fn node(&self) -> &MergedNode<'_> {
+        &self.node
+    }
+
+    /// Returns a sequence of completion operations, or "completion ops", to
+    /// apply to the local tree so that it matches the merged tree. The abort
+    /// signal can be used to interrupt fetching the ops.
+    pub fn completion_ops_with_signal(
+        &self,
+        signal: &impl AbortSignal,
+    ) -> Result<CompletionOps<'_>> {
+        let mut ops = CompletionOps::default();
+        accumulate(signal, &mut ops, self.node(), 1, false)?;
+
+        // Clean up tombstones for local and remote items that are revived on
+        // the other side.
+        for guid in self
+            .local_tree
+            .deletions()
+            .difference(&self.delete_remotely)
+        {
+            // For ignored local deletions, we remove the local tombstone. If
+            // the item is already deleted remotely, we also flag the remote
+            // tombstone as merged.
+            signal.err_if_aborted()?;
+            ops.delete_local_tombstones.push(DeleteLocalTombstone(guid));
+            if self.remote_tree.is_deleted(guid) {
+                ops.set_remote_merged.push(SetRemoteMerged(guid));
+            }
+        }
+        for guid in self
+            .remote_tree
+            .deletions()
+            .difference(&self.delete_locally)
+            .filter(|guid| !self.local_tree.exists(guid))
+        {
+            // Ignored remote deletions are handled a little differently. Unlike
+            // local tombstones, which are stored separately from items, remote
+            // tombstones and items are stored in the same table. This means we
+            // only need to flag the remote tombstone as merged if it's for an
+            // item that doesn't exist locally. If the local item does exist,
+            // we can avoid an extra write to flag the tombstone that we'll
+            // replace with the item, anyway. If the item is already deleted
+            // locally, we also delete the local tombstone.
+            signal.err_if_aborted()?;
+            ops.set_remote_merged.push(SetRemoteMerged(guid));
+            if self.local_tree.is_deleted(guid) {
+                ops.delete_local_tombstones.push(DeleteLocalTombstone(guid));
+            }
+        }
+
+        // Emit completion ops for deleted items.
+        for guid in self.deletions() {
+            signal.err_if_aborted()?;
+            match (
+                self.local_tree.node_for_guid(guid),
+                self.remote_tree.node_for_guid(guid),
+            ) {
+                (Some(local_node), Some(remote_node)) => {
+                    // Delete items that are non-syncable or invalid on both
+                    // sides.
+                    ops.delete_local_items.push(DeleteLocalItem(local_node));
+                    ops.insert_local_tombstones
+                        .push(InsertLocalTombstone(remote_node));
+                    ops.upload_tombstones.push(UploadTombstone(guid));
+                }
+                (Some(local_node), None) => {
+                    // Apply remote tombstones, or delete invalid local-only
+                    // items. If the item is deleted remotely, flag the remote
+                    // tombstone as merged. If not, we don't need to upload one,
+                    // since the item is only known locally.
+                    ops.delete_local_items.push(DeleteLocalItem(local_node));
+                    if self.remote_tree.is_deleted(guid) {
+                        ops.set_remote_merged.push(SetRemoteMerged(guid));
+                    }
+                }
+                (None, Some(remote_node)) => {
+                    // Take local tombstones, or delete invalid remote-only
+                    // items. If it's not already deleted locally, insert a
+                    // tombstone for the item.
+                    if !self.local_tree.is_deleted(guid) {
+                        ops.insert_local_tombstones
+                            .push(InsertLocalTombstone(remote_node));
+                    }
+                    ops.upload_tombstones.push(UploadTombstone(guid));
+                }
+                (None, None) => {
+                    // Clean up local tombstones, and flag remote tombstones as
+                    // merged, for items deleted on both sides.
+                    if self.local_tree.is_deleted(guid) {
+                        ops.delete_local_tombstones.push(DeleteLocalTombstone(guid));
+                    }
+                    if self.remote_tree.is_deleted(guid) {
+                        ops.set_remote_merged.push(SetRemoteMerged(guid));
+                    }
+                }
+            }
+        }
+
+        Ok(ops)
+    }
+
+    /// Returns a sequence of completion ops, without interruption.
+    #[inline]
+    pub fn completion_ops(&self) -> CompletionOps<'_> {
+        self.completion_ops_with_signal(&DefaultAbortSignal)
+            .unwrap()
+    }
+
+    /// Returns an iterator for all accepted local and remote deletions.
+    #[inline]
+    pub fn deletions(&self) -> impl Iterator<Item = &Guid> {
+        self.delete_locally.union(&self.delete_remotely)
+    }
+
+    /// Returns an iterator for all items that should be deleted from the
+    /// local tree.
+    #[inline]
+    pub fn local_deletions(&self) -> impl Iterator<Item = &Guid> {
+        self.delete_locally.difference(&self.delete_remotely)
+    }
+
+    /// Returns an iterator for all items that should be deleted from the
+    /// remote tree.
+    #[inline]
+    pub fn remote_deletions(&self) -> impl Iterator<Item = &Guid> {
+        self.delete_remotely.iter()
+    }
+
+    /// Returns structure change counts for this merged root.
+    #[inline]
+    pub fn counts(&self) -> &StructureCounts {
+        &self.structure_counts
+    }
+}
+
+/// Completion operations to apply to the local tree after a merge. These are
+/// represented as separate structs in `Vec`s instead of enums yielded from an
+/// iterator so that consumers can easily chunk them.
+#[derive(Clone, Debug, Default)]
+pub struct CompletionOps<'t> {
+    pub change_guids: Vec<ChangeGuid<'t>>,
+    pub apply_remote_items: Vec<ApplyRemoteItem<'t>>,
+    pub apply_new_local_structure: Vec<ApplyNewLocalStructure<'t>>,
+    pub set_local_unmerged: Vec<SetLocalUnmerged<'t>>,
+    pub set_local_merged: Vec<SetLocalMerged<'t>>,
+    pub set_remote_merged: Vec<SetRemoteMerged<'t>>,
+    pub delete_local_tombstones: Vec<DeleteLocalTombstone<'t>>,
+    pub insert_local_tombstones: Vec<InsertLocalTombstone<'t>>,
+    pub delete_local_items: Vec<DeleteLocalItem<'t>>,
+    pub upload_items: Vec<UploadItem<'t>>,
+    pub upload_tombstones: Vec<UploadTombstone<'t>>,
+}
+
+impl<'t> CompletionOps<'t> {
+    /// Returns `true` if there are no completion ops to apply.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.change_guids.is_empty()
+            && self.apply_remote_items.is_empty()
+            && self.apply_new_local_structure.is_empty()
+            && self.set_local_unmerged.is_empty()
+            && self.set_local_merged.is_empty()
+            && self.set_remote_merged.is_empty()
+            && self.delete_local_tombstones.is_empty()
+            && self.insert_local_tombstones.is_empty()
+            && self.delete_local_items.is_empty()
+            && self.upload_items.is_empty()
+            && self.upload_tombstones.is_empty()
+    }
+
+    /// Returns a printable summary of all completion ops to apply.
+    pub fn summarize(&self) -> Vec<String> {
+        std::iter::empty()
+            .chain(to_strings(&self.change_guids))
+            .chain(to_strings(&self.apply_remote_items))
+            .chain(to_strings(&self.apply_new_local_structure))
+            .chain(to_strings(&self.set_local_unmerged))
+            .chain(to_strings(&self.set_local_merged))
+            .chain(to_strings(&self.set_remote_merged))
+            .chain(to_strings(&self.delete_local_tombstones))
+            .chain(to_strings(&self.insert_local_tombstones))
+            .chain(to_strings(&self.delete_local_items))
+            .chain(to_strings(&self.upload_items))
+            .chain(to_strings(&self.upload_tombstones))
+            .collect()
+    }
+}
+
+/// A completion op to change the local GUID to the merged GUID. This is used
+/// to dedupe new local items to remote ones, as well as to fix up invalid
+/// GUIDs.
+#[derive(Clone, Copy, Debug)]
+pub struct ChangeGuid<'t> {
+    /// The merged node to update.
+    pub merged_node: &'t MergedNode<'t>,
+    /// The level of the node in the merged tree. Desktop uses this to ensure
+    /// that GUID change observers are notified in level order (parents before
+    /// children).
+    pub level: usize,
+}
+
+impl<'t> ChangeGuid<'t> {
+    /// Returns the local node for this completion op. Panics if the local node
+    /// isn't set, as we should never emit a `ChangeGuid` op in that case.
+    #[inline]
+    pub fn local_node(&self) -> &'t Node<'t> {
+        self.merged_node
+            .merge_state
+            .local_node()
+            .expect("Can't change local GUID without local node")
+    }
+}
+
+impl<'t> fmt::Display for ChangeGuid<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "Change {} to {}",
+            self.local_node().guid,
+            self.merged_node.guid
+        )
+    }
+}
+
+/// A completion op to insert a new remote item into the local tree, or apply
+/// synced changes to an existing item.
+#[derive(Clone, Copy, Debug)]
+pub struct ApplyRemoteItem<'t> {
+    pub merged_node: &'t MergedNode<'t>,
+    pub level: usize,
+}
+
+impl<'t> ApplyRemoteItem<'t> {
+    /// Returns the remote node for this completion op. Panics if the remote
+    /// node isn't set, as we should never emit an `ApplyRemoteItem` op in
+    /// that case.
+    #[inline]
+    pub fn remote_node(&self) -> &'t Node<'t> {
+        self.merged_node
+            .merge_state
+            .remote_node()
+            .expect("Can't apply remote item without remote node")
+    }
+}
+
+impl<'t> fmt::Display for ApplyRemoteItem<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if self.merged_node.remote_guid_changed() {
+            write!(
+                f,
+                "Apply remote {} as {}",
+                self.remote_node().guid,
+                self.merged_node.guid
+            )
+        } else {
+            write!(f, "Apply remote {}", self.merged_node.guid)
+        }
+    }
+}
+
+/// A completion op to update the parent and position of a local item.
+#[derive(Clone, Copy, Debug)]
+pub struct ApplyNewLocalStructure<'t> {
+    pub merged_node: &'t MergedNode<'t>,
+    pub merged_parent_node: &'t MergedNode<'t>,
+    pub position: usize,
+    pub level: usize,
+}
+
+impl<'t> fmt::Display for ApplyNewLocalStructure<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "Move {} into {} at {}",
+            self.merged_node.guid, self.merged_parent_node.guid, self.position
+        )
+    }
+}
+
+/// A completion op to flag a local item for upload.
+#[derive(Clone, Copy, Debug)]
+pub struct SetLocalUnmerged<'t> {
+    pub merged_node: &'t MergedNode<'t>,
+}
+
+impl<'t> fmt::Display for SetLocalUnmerged<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Flag local {} as unmerged", self.merged_node.guid)
+    }
+}
+
+/// A completion op to skip uploading a local item after resolving merge
+/// conflicts.
+#[derive(Clone, Copy, Debug)]
+pub struct SetLocalMerged<'t> {
+    pub merged_node: &'t MergedNode<'t>,
+}
+
+impl<'t> fmt::Display for SetLocalMerged<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Flag local {} as merged", self.merged_node.guid)
+    }
+}
+
+/// A completion op to upload or reupload a merged item.
+#[derive(Clone, Copy, Debug)]
+pub struct UploadItem<'t> {
+    pub merged_node: &'t MergedNode<'t>,
+}
+
+impl<'t> fmt::Display for UploadItem<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Upload item {}", self.merged_node.guid)
+    }
+}
+
+/// A completion op to upload a tombstone.
+#[derive(Clone, Copy, Debug)]
+pub struct UploadTombstone<'t>(&'t Guid);
+
+impl<'t> UploadTombstone<'t> {
+    /// Returns the GUID to use for the tombstone.
+    #[inline]
+    pub fn guid(self) -> &'t Guid {
+        self.0
+    }
+}
+
+impl<'t> fmt::Display for UploadTombstone<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Upload tombstone {}", self.0)
+    }
+}
+
+/// A completion op to flag a remote item as merged.
+#[derive(Clone, Copy, Debug)]
+pub struct SetRemoteMerged<'t>(&'t Guid);
+
+impl<'t> SetRemoteMerged<'t> {
+    /// Returns the remote GUID for the item to flag as merged.
+    #[inline]
+    pub fn guid(self) -> &'t Guid {
+        self.0
+    }
+}
+
+impl<'t> fmt::Display for SetRemoteMerged<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Flag remote {} as merged", self.guid())
+    }
+}
+
+/// A completion op to store a tombstone for a remote item.
+#[derive(Clone, Copy, Debug)]
+pub struct InsertLocalTombstone<'t>(Node<'t>);
+
+impl<'t> InsertLocalTombstone<'t> {
+    /// Returns the node for the item to delete remotely.
+    #[inline]
+    pub fn remote_node(&self) -> Node<'t> {
+        self.0
+    }
+}
+
+impl<'t> fmt::Display for InsertLocalTombstone<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Insert local tombstone {}", self.0.guid)
+    }
+}
+
+/// A completion op to delete a local tombstone.
+#[derive(Clone, Copy, Debug)]
+pub struct DeleteLocalTombstone<'t>(&'t Guid);
+
+impl<'t> DeleteLocalTombstone<'t> {
+    /// Returns the GUID of the tombstone.
+    #[inline]
+    pub fn guid(self) -> &'t Guid {
+        self.0
+    }
+}
+
+impl<'t> fmt::Display for DeleteLocalTombstone<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Delete local tombstone {}", self.0)
+    }
+}
+
+/// A completion op to delete an item from the local tree.
+#[derive(Clone, Copy, Debug)]
+pub struct DeleteLocalItem<'t>(Node<'t>);
+
+impl<'t> DeleteLocalItem<'t> {
+    // Returns the node for the item to delete locally.
+    #[inline]
+    pub fn local_node(&self) -> Node<'t> {
+        self.0
+    }
+}
+
+impl<'t> fmt::Display for DeleteLocalItem<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Delete local item {}", self.0.guid)
+    }
+}
+
+/// Recursively accumulates completion ops, starting at `merged_node` and
+/// drilling down into all its descendants.
+fn accumulate<'t, A: AbortSignal>(
+    signal: &A,
+    ops: &mut CompletionOps<'t>,
+    merged_node: &'t MergedNode<'t>,
+    level: usize,
+    is_tagging: bool,
+) -> Result<()> {
+    for (position, merged_child_node) in merged_node.merged_children.iter().enumerate() {
+        signal.err_if_aborted()?;
+        let is_tagging = if merged_child_node.guid == TAGS_GUID {
+            true
+        } else {
+            is_tagging
+        };
+        if merged_child_node.merge_state.should_apply_item() {
+            let apply_remote_item = ApplyRemoteItem {
+                merged_node: merged_child_node,
+                level,
+            };
+            ops.apply_remote_items.push(apply_remote_item);
+        }
+        if merged_child_node.local_guid_changed() {
+            let change_guid = ChangeGuid {
+                merged_node: merged_child_node,
+                level,
+            };
+            ops.change_guids.push(change_guid);
+        }
+        let local_child_node = merged_node
+            .merge_state
+            .local_node()
+            .and_then(|local_parent_node| local_parent_node.child(position));
+        let merged_local_child_node = merged_child_node.merge_state.local_node();
+        if local_child_node
+            .and_then(|m| merged_local_child_node.map(|n| m.guid != n.guid))
+            .unwrap_or(true)
+        {
+            // As an optimization, we only emit ops to apply a new local
+            // structure for items that actually moved. For example, if the
+            // local children are (A B C D) and the merged children are
+            // (A D C B), only (B D) need new structure.
+            let apply_new_local_structure = ApplyNewLocalStructure {
+                merged_node: merged_child_node,
+                merged_parent_node: merged_node,
+                position,
+                level,
+            };
+            ops.apply_new_local_structure
+                .push(apply_new_local_structure);
+        }
+        let local_needs_merge = merged_child_node
+            .merge_state
+            .local_node()
+            .map(|node| node.needs_merge)
+            .unwrap_or(false);
+        let should_upload = merged_child_node.merge_state.should_upload();
+        match (local_needs_merge, should_upload) {
+            (false, true) => {
+                // Local item isn't flagged for upload, but should be.
+                let set_local_unmerged = SetLocalUnmerged {
+                    merged_node: merged_child_node,
+                };
+                ops.set_local_unmerged.push(set_local_unmerged);
+            }
+            (true, false) => {
+                // Local item flagged for upload when it doesn't need to be.
+                let set_local_merged = SetLocalMerged {
+                    merged_node: merged_child_node,
+                };
+                ops.set_local_merged.push(set_local_merged);
+            }
+            _ => {}
+        }
+        if should_upload && !is_tagging {
+            // (Re)upload items. Ignore the tags root and its descendants:
+            // they're part of the local tree on Desktop (and will be removed
+            // in bug 424160), but aren't synced as part of the structure.
+            ops.upload_items.push(UploadItem {
+                merged_node: merged_child_node,
+            });
+        }
+        if let Some(remote_child_node) = merged_child_node.merge_state.remote_node() {
+            if remote_child_node.needs_merge && !should_upload {
+                // If the remote item was merged, and doesn't need to be
+                // reuploaded, flag it as merged in the remote tree. Note that
+                // we _don't_ emit this for locally revived items, or items with
+                // new remote structure.
+                let set_remote_merged = SetRemoteMerged(&remote_child_node.guid);
+                ops.set_remote_merged.push(set_remote_merged);
+            }
+        }
+        accumulate(signal, ops, merged_child_node, level + 1, is_tagging)?;
+    }
+    Ok(())
+}
+
+/// Converts all items in the list to strings.
+pub(crate) fn to_strings<'a, T: ToString>(items: &'a [T]) -> impl Iterator<Item = String> + 'a {
+    items.iter().map(ToString::to_string)
+}