Adding upstream version 124.0.1.upstream/124.0.1

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

8 files changed, 8169 insertions, 0 deletions

diff --git a/third_party/rust/dogear/src/driver.rs b/third_party/rust/dogear/src/driver.rs
new file mode 100644
index 0000000000..1c98ebdfb1
--- /dev/null
+++ b/third_party/rust/dogear/src/driver.rs
@@ -0,0 +1,212 @@
+// 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::{fmt::Arguments, time::Duration};
+
+use log::{Level, LevelFilter, Log};
+
+use crate::error::{ErrorKind, Result};
+use crate::guid::Guid;
+use crate::merge::StructureCounts;
+use crate::tree::ProblemCounts;
+
+/// An abort signal is used to abort merging. Implementations of `AbortSignal`
+/// can store an aborted flag, usually as an atomic integer or Boolean, set
+/// the flag on abort, and have `AbortSignal::aborted` return the flag's value.
+///
+/// Since merging is synchronous, it's not possible to interrupt a merge from
+/// the same thread that started it. In practice, this means a signal will
+/// implement `Send` and `Sync`, too, so that another thread can set the
+/// aborted flag.
+///
+/// The name comes from the `AbortSignal` DOM API.
+pub trait AbortSignal {
+    /// Indicates if the caller signaled to abort.
+    fn aborted(&self) -> bool;
+
+    /// Returns an error if the caller signaled to abort. This helper makes it
+    /// easier to use the signal with the `?` operator.
+    fn err_if_aborted(&self) -> Result<()> {
+        if self.aborted() {
+            Err(ErrorKind::Abort.into())
+        } else {
+            Ok(())
+        }
+    }
+}
+
+/// A default signal that can't be aborted.
+pub struct DefaultAbortSignal;
+
+impl AbortSignal for DefaultAbortSignal {
+    fn aborted(&self) -> bool {
+        false
+    }
+}
+
+/// A merge telemetry event.
+pub enum TelemetryEvent {
+    FetchLocalTree(TreeStats),
+    FetchRemoteTree(TreeStats),
+    Merge(Duration, StructureCounts),
+    Apply(Duration),
+}
+
+/// Records the time taken to build a local or remote tree, number of items
+/// in the tree, and structure problem counts.
+pub struct TreeStats {
+    pub time: Duration,
+    pub items: usize,
+    pub deletions: usize,
+    pub problems: ProblemCounts,
+}
+
+/// A merge driver provides methods to customize merging behavior.
+pub trait Driver {
+    /// Generates a new GUID for the given invalid GUID. This is used to fix up
+    /// items with GUIDs that Places can't store (bug 1380606, bug 1313026).
+    ///
+    /// The default implementation returns an error, forbidding invalid GUIDs.
+    ///
+    /// Implementations of `Driver` can either use the `rand` and `base64`
+    /// crates to generate a new, random GUID (9 bytes, Base64url-encoded
+    /// without padding), or use an existing method like Desktop's
+    /// `nsINavHistoryService::MakeGuid`. Dogear doesn't generate new GUIDs
+    /// automatically to avoid depending on those crates.
+    ///
+    /// Implementations can also return `Ok(invalid_guid.clone())` to pass
+    /// through all invalid GUIDs, as the tests do.
+    fn generate_new_guid(&self, invalid_guid: &Guid) -> Result<Guid> {
+        Err(ErrorKind::InvalidGuid(invalid_guid.clone()).into())
+    }
+
+    /// Returns the maximum log level for merge messages. The default
+    /// implementation returns the `log` crate's global maximum level.
+    fn max_log_level(&self) -> LevelFilter {
+        log::max_level()
+    }
+
+    /// Returns a logger for merge messages.
+    ///
+    /// The default implementation returns the `log` crate's global logger.
+    ///
+    /// Implementations can override this method to return a custom logger,
+    /// where using the global logger won't work. For example, Firefox Desktop
+    /// has an existing Sync logging setup outside of the `log` crate.
+    fn logger(&self) -> &dyn Log {
+        log::logger()
+    }
+
+    /// Records a merge telemetry event.
+    ///
+    /// The default implementation is a no-op that discards the event.
+    /// Implementations can override this method to capture event and bookmark
+    /// validation telemetry.
+    fn record_telemetry_event(&self, _: TelemetryEvent) {}
+}
+
+/// A default implementation of the merge driver.
+pub struct DefaultDriver;
+
+impl Driver for DefaultDriver {}
+
+/// Logs a merge message.
+pub fn log<D: Driver>(
+    driver: &D,
+    level: Level,
+    args: Arguments<'_>,
+    module_path: &'static str,
+    file: &'static str,
+    line: u32,
+) {
+    let meta = log::Metadata::builder()
+        .level(level)
+        .target(module_path)
+        .build();
+    if driver.logger().enabled(&meta) {
+        driver.logger().log(
+            &log::Record::builder()
+                .args(args)
+                .metadata(meta)
+                .module_path(Some(module_path))
+                .file(Some(file))
+                .line(Some(line))
+                .build(),
+        );
+    }
+}
+
+#[macro_export]
+macro_rules! error {
+    ($driver:expr, $($args:tt)+) => {
+        if log::Level::Error <= $crate::Driver::max_log_level($driver) {
+            $crate::log(
+                $driver,
+                log::Level::Error,
+                format_args!($($args)+),
+                module_path!(),
+                file!(),
+                line!(),
+            );
+        }
+    }
+}
+
+#[macro_export]
+macro_rules! warn {
+    ($driver:expr, $($args:tt)+) => {
+        if log::Level::Warn <= $crate::Driver::max_log_level($driver) {
+            $crate::log(
+                $driver,
+                log::Level::Warn,
+                format_args!($($args)+),
+                module_path!(),
+                file!(),
+                line!(),
+            );
+        }
+    }
+}
+
+#[macro_export]
+macro_rules! debug {
+    ($driver:expr, $($args:tt)+) => {
+        if log::Level::Debug <= $crate::Driver::max_log_level($driver) {
+            $crate::log(
+                $driver,
+                log::Level::Debug,
+                format_args!($($args)+),
+                module_path!(),
+                file!(),
+                line!(),
+            );
+        }
+    }
+}
+
+#[macro_export]
+macro_rules! trace {
+    ($driver:expr, $($args:tt)+) => {
+        if log::Level::Trace <= $crate::Driver::max_log_level($driver) {
+            $crate::log(
+                $driver,
+                log::Level::Trace,
+                format_args!($($args)+),
+                module_path!(),
+                file!(),
+                line!(),
+            );
+        }
+    }
+}
diff --git a/third_party/rust/dogear/src/error.rs b/third_party/rust/dogear/src/error.rs
new file mode 100644
index 0000000000..b950062a38
--- /dev/null
+++ b/third_party/rust/dogear/src/error.rs
@@ -0,0 +1,134 @@
+// 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::{error, fmt, result, str::Utf8Error, string::FromUtf16Error};
+
+use crate::guid::Guid;
+use crate::Item;
+
+pub type Result<T> = result::Result<T, Error>;
+
+#[derive(Debug)]
+pub struct Error(ErrorKind);
+
+impl Error {
+    pub fn kind(&self) -> &ErrorKind {
+        &self.0
+    }
+}
+
+impl error::Error for Error {
+    fn source(&self) -> Option<&(dyn error::Error + 'static)> {
+        match self.kind() {
+            ErrorKind::MalformedString(err) => Some(err.as_ref()),
+            _ => None,
+        }
+    }
+}
+
+impl From<ErrorKind> for Error {
+    fn from(kind: ErrorKind) -> Error {
+        Error(kind)
+    }
+}
+
+impl From<FromUtf16Error> for Error {
+    fn from(error: FromUtf16Error) -> Error {
+        Error(ErrorKind::MalformedString(error.into()))
+    }
+}
+
+impl From<Utf8Error> for Error {
+    fn from(error: Utf8Error) -> Error {
+        Error(ErrorKind::MalformedString(error.into()))
+    }
+}
+
+impl fmt::Display for Error {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        // We format the guid-specific params with <guid: {}> to make it easier on the
+        // telemetry side to parse out the user-specific guid and normalize the errors
+        // to better aggregate the data
+        match self.kind() {
+            ErrorKind::MismatchedItemKind(local_item, remote_item) => write!(
+                f,
+                "Can't merge local {} <guid: {}> and remote {} <guid: {}>",
+                local_item.kind, local_item.guid, remote_item.kind, remote_item.guid,
+            ),
+            ErrorKind::DuplicateItem(guid) => {
+                write!(f, "Item <guid: {}> already exists in tree", guid)
+            }
+            ErrorKind::MissingItem(guid) => {
+                write!(f, "Item <guid: {}> doesn't exist in tree", guid)
+            }
+            ErrorKind::InvalidParent(child, parent) => write!(
+                f,
+                "Can't insert {} <guid: {}> into {} <guid: {}>",
+                child.kind, child.guid, parent.kind, parent.guid,
+            ),
+            ErrorKind::InvalidParentForUnknownChild(child_guid, parent) => write!(
+                f,
+                "Can't insert unknown child <guid: {}> into {} <guid: {}>",
+                child_guid, parent.kind, parent.guid,
+            ),
+            ErrorKind::MissingParent(child, parent_guid) => write!(
+                f,
+                "Can't insert {} <guid: {}> into nonexistent parent <guid: {}>",
+                child.kind, child.guid, parent_guid,
+            ),
+            ErrorKind::MissingParentForUnknownChild(child_guid, parent_guid) => write!(
+                f,
+                "Can't insert unknown child <guid: {}> into nonexistent parent <guid: {}>",
+                child_guid, parent_guid,
+            ),
+            ErrorKind::Cycle(guid) => write!(f, "Item <guid: {}> can't contain itself", guid),
+            ErrorKind::MergeConflict => write!(f, "Local tree changed during merge"),
+            ErrorKind::UnmergedLocalItems => {
+                write!(f, "Merged tree doesn't mention all items from local tree")
+            }
+            ErrorKind::UnmergedRemoteItems => {
+                write!(f, "Merged tree doesn't mention all items from remote tree")
+            }
+            ErrorKind::InvalidGuid(invalid_guid) => {
+                write!(
+                    f,
+                    "Merged tree contains invalid GUID <guid: {}>",
+                    invalid_guid
+                )
+            }
+            ErrorKind::InvalidByte(b) => write!(f, "Invalid byte <byte: {}> in UTF-16 encoding", b),
+            ErrorKind::MalformedString(err) => err.fmt(f),
+            ErrorKind::Abort => write!(f, "Operation aborted"),
+        }
+    }
+}
+
+#[derive(Debug)]
+pub enum ErrorKind {
+    MismatchedItemKind(Item, Item),
+    DuplicateItem(Guid),
+    InvalidParent(Item, Item),
+    InvalidParentForUnknownChild(Guid, Item),
+    MissingParent(Item, Guid),
+    MissingParentForUnknownChild(Guid, Guid),
+    MissingItem(Guid),
+    Cycle(Guid),
+    MergeConflict,
+    UnmergedLocalItems,
+    UnmergedRemoteItems,
+    InvalidGuid(Guid),
+    InvalidByte(u16),
+    MalformedString(Box<dyn error::Error + Send + Sync + 'static>),
+    Abort,
+}
diff --git a/third_party/rust/dogear/src/guid.rs b/third_party/rust/dogear/src/guid.rs
new file mode 100644
index 0000000000..661ee53c63
--- /dev/null
+++ b/third_party/rust/dogear/src/guid.rs
@@ -0,0 +1,301 @@
+// 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::{
+    cmp::Ordering,
+    fmt,
+    hash::{Hash, Hasher},
+    ops, str,
+};
+
+use crate::error::{ErrorKind, Result};
+
+/// A GUID for an item in a bookmark tree.
+#[derive(Clone)]
+pub struct Guid(Repr);
+
+/// Indicates if the GUID is valid. Implemented for byte slices and GUIDs.
+pub trait IsValidGuid {
+    fn is_valid_guid(&self) -> bool;
+}
+
+/// The internal representation of a GUID. Valid GUIDs are 12 bytes, and contain
+/// only Base64url characters; we can store them on the stack without a heap
+/// allocation. However, both local and remote items might have invalid GUIDs,
+/// in which case we fall back to a heap-allocated string.
+#[derive(Clone)]
+enum Repr {
+    Valid([u8; 12]),
+    Invalid(Box<str>),
+}
+
+/// The Places root GUID, used to root all items in a bookmark tree.
+pub const ROOT_GUID: Guid = Guid(Repr::Valid(*b"root________"));
+
+/// The bookmarks toolbar GUID.
+pub const TOOLBAR_GUID: Guid = Guid(Repr::Valid(*b"toolbar_____"));
+
+/// The bookmarks menu GUID.
+pub const MENU_GUID: Guid = Guid(Repr::Valid(*b"menu________"));
+
+/// The "Other Bookmarks" GUID, used to hold items without a parent.
+pub const UNFILED_GUID: Guid = Guid(Repr::Valid(*b"unfiled_____"));
+
+/// The mobile bookmarks GUID.
+pub const MOBILE_GUID: Guid = Guid(Repr::Valid(*b"mobile______"));
+
+/// The tags root GUID.
+pub const TAGS_GUID: Guid = Guid(Repr::Valid(*b"tags________"));
+
+const VALID_GUID_BYTES: [u8; 255] = [
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
+    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,
+    0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+];
+
+impl Guid {
+    /// Converts a UTF-8 byte slice to a GUID.
+    pub fn from_utf8(b: &[u8]) -> Result<Guid> {
+        let repr = if b.is_valid_guid() {
+            let mut bytes = [0u8; 12];
+            bytes.copy_from_slice(b);
+            Repr::Valid(bytes)
+        } else {
+            match str::from_utf8(b) {
+                Ok(s) => Repr::Invalid(s.into()),
+                Err(err) => return Err(err.into()),
+            }
+        };
+        Ok(Guid(repr))
+    }
+
+    /// Converts a UTF-16 byte slice to a GUID.
+    pub fn from_utf16(b: &[u16]) -> Result<Guid> {
+        let repr = if b.is_valid_guid() {
+            let mut bytes = [0u8; 12];
+            for (index, &byte) in b.iter().enumerate() {
+                if byte > u16::from(u8::max_value()) {
+                    return Err(ErrorKind::InvalidByte(byte).into());
+                }
+                bytes[index] = byte as u8;
+            }
+            Repr::Valid(bytes)
+        } else {
+            match String::from_utf16(b) {
+                Ok(s) => Repr::Invalid(s.into()),
+                Err(err) => return Err(err.into()),
+            }
+        };
+        Ok(Guid(repr))
+    }
+
+    /// Returns the GUID as a byte slice.
+    #[inline]
+    pub fn as_bytes(&self) -> &[u8] {
+        match self.0 {
+            Repr::Valid(ref bytes) => bytes,
+            Repr::Invalid(ref s) => s.as_bytes(),
+        }
+    }
+
+    /// Returns the GUID as a string slice.
+    #[inline]
+    pub fn as_str(&self) -> &str {
+        // We actually could use from_utf8_unchecked here, and depending on how
+        // often we end up doing this, it's arguable that we should. We know
+        // already this is valid utf8, since we know that we only ever create
+        // these while respecting is_valid (and moreover, we assert that
+        // `s.is_char_boundary(12)` in `Guid::from`).
+        match self.0 {
+            Repr::Valid(ref bytes) => str::from_utf8(bytes).unwrap(),
+            Repr::Invalid(ref s) => s,
+        }
+    }
+
+    /// Indicates if the GUID is one of the five Places built-in roots,
+    /// including the user content roots and the tags root.
+    #[inline]
+    pub fn is_built_in_root(&self) -> bool {
+        self == TOOLBAR_GUID
+            || self == MENU_GUID
+            || self == UNFILED_GUID
+            || self == MOBILE_GUID
+            || self == TAGS_GUID
+    }
+}
+
+impl IsValidGuid for Guid {
+    #[inline]
+    fn is_valid_guid(&self) -> bool {
+        match self.0 {
+            Repr::Valid(_) => true,
+            Repr::Invalid(_) => false,
+        }
+    }
+}
+
+impl<T: Copy + Into<usize>> IsValidGuid for [T] {
+    /// Equivalent to `PlacesUtils.isValidGuid`.
+    #[inline]
+    fn is_valid_guid(&self) -> bool {
+        self.len() == 12
+            && self
+                .iter()
+                .all(|&byte| VALID_GUID_BYTES.get(byte.into()).map_or(false, |&b| b == 1))
+    }
+}
+
+impl From<String> for Guid {
+    #[inline]
+    fn from(s: String) -> Guid {
+        Guid::from(s.as_str())
+    }
+}
+
+impl<'a> From<&'a str> for Guid {
+    #[inline]
+    fn from(s: &'a str) -> Guid {
+        let repr = if s.as_bytes().is_valid_guid() {
+            assert!(s.is_char_boundary(12));
+            let mut bytes = [0u8; 12];
+            bytes.copy_from_slice(s.as_bytes());
+            Repr::Valid(bytes)
+        } else {
+            Repr::Invalid(s.into())
+        };
+        Guid(repr)
+    }
+}
+
+impl AsRef<str> for Guid {
+    #[inline]
+    fn as_ref(&self) -> &str {
+        self.as_str()
+    }
+}
+
+impl AsRef<[u8]> for Guid {
+    #[inline]
+    fn as_ref(&self) -> &[u8] {
+        self.as_bytes()
+    }
+}
+
+impl ops::Deref for Guid {
+    type Target = str;
+
+    #[inline]
+    fn deref(&self) -> &str {
+        self.as_str()
+    }
+}
+
+impl Ord for Guid {
+    fn cmp(&self, other: &Guid) -> Ordering {
+        self.as_bytes().cmp(other.as_bytes())
+    }
+}
+
+impl PartialOrd for Guid {
+    fn partial_cmp(&self, other: &Guid) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+// Allow direct comparison with str
+impl PartialEq<str> for Guid {
+    #[inline]
+    fn eq(&self, other: &str) -> bool {
+        self.as_bytes() == other.as_bytes()
+    }
+}
+
+impl<'a> PartialEq<&'a str> for Guid {
+    #[inline]
+    fn eq(&self, other: &&'a str) -> bool {
+        self == *other
+    }
+}
+
+impl PartialEq for Guid {
+    #[inline]
+    fn eq(&self, other: &Guid) -> bool {
+        self.as_bytes() == other.as_bytes()
+    }
+}
+
+impl<'a> PartialEq<Guid> for &'a Guid {
+    #[inline]
+    fn eq(&self, other: &Guid) -> bool {
+        *self == other
+    }
+}
+
+impl Eq for Guid {}
+
+impl Hash for Guid {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.as_bytes().hash(state);
+    }
+}
+
+// The default Debug impl is pretty unhelpful here.
+impl fmt::Debug for Guid {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Guid({:?})", self.as_str())
+    }
+}
+
+impl fmt::Display for Guid {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str(self.as_str())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn is_valid() {
+        let valid_guids = &[
+            "bookmarkAAAA",
+            "menu________",
+            "__folderBB__",
+            "queryAAAAAAA",
+        ];
+        for s in valid_guids {
+            assert!(s.as_bytes().is_valid_guid(), "{:?} should validate", s);
+            assert!(Guid::from(*s).is_valid_guid());
+        }
+
+        let invalid_guids = &["bookmarkAAA", "folder!", "b@dgu1d!"];
+        for s in invalid_guids {
+            assert!(!s.as_bytes().is_valid_guid(), "{:?} should not validate", s);
+            assert!(!Guid::from(*s).is_valid_guid());
+        }
+
+        let invalid_guid_bytes: &[[u8; 12]] =
+            &[[113, 117, 101, 114, 121, 65, 225, 193, 65, 65, 65, 65]];
+        for bytes in invalid_guid_bytes {
+            assert!(!bytes.is_valid_guid(), "{:?} should not validate", bytes);
+            Guid::from_utf8(bytes).expect_err("Should not make GUID from invalid UTF-8");
+        }
+    }
+}
diff --git a/third_party/rust/dogear/src/lib.rs b/third_party/rust/dogear/src/lib.rs
new file mode 100644
index 0000000000..b3793e5417
--- /dev/null
+++ b/third_party/rust/dogear/src/lib.rs
@@ -0,0 +1,34 @@
+// 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.
+
+#![allow(unknown_lints)]
+#![warn(rust_2018_idioms)]
+
+#[macro_use]
+mod driver;
+mod error;
+mod guid;
+mod merge;
+mod store;
+mod tree;
+
+#[cfg(test)]
+mod tests;
+
+pub use crate::driver::*;
+pub use crate::error::*;
+pub use crate::guid::*;
+pub use crate::merge::*;
+pub use crate::store::*;
+pub use crate::tree::*;
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)
+}
diff --git a/third_party/rust/dogear/src/store.rs b/third_party/rust/dogear/src/store.rs
new file mode 100644
index 0000000000..7ada8407fc
--- /dev/null
+++ b/third_party/rust/dogear/src/store.rs
@@ -0,0 +1,117 @@
+// 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::{time::Duration, time::Instant};
+
+use crate::driver::{
+    AbortSignal, DefaultAbortSignal, DefaultDriver, Driver, TelemetryEvent, TreeStats,
+};
+use crate::error::Error;
+use crate::guid::Guid;
+use crate::merge::{MergedRoot, Merger};
+use crate::tree::Tree;
+
+/// A store is the main interface to Dogear. It implements methods for building
+/// local and remote trees from a storage backend, fetching content info for
+/// matching items with similar contents, and persisting the merged tree.
+pub trait Store {
+    /// The type returned from a successful merge.
+    type Ok;
+
+    /// The type returned in the event of a store error.
+    type Error: From<Error>;
+
+    /// Builds a fully rooted, consistent tree from the items and tombstones in
+    /// the local store.
+    fn fetch_local_tree(&self) -> Result<Tree, Self::Error>;
+
+    /// Builds a fully rooted, consistent tree from the items and tombstones in
+    /// the mirror.
+    fn fetch_remote_tree(&self) -> Result<Tree, Self::Error>;
+
+    /// Applies the merged root to the local store, and stages items for
+    /// upload. On Desktop, this method inserts the merged tree into a temp
+    /// table, updates Places, and inserts outgoing items into another
+    /// temp table.
+    fn apply<'t>(&mut self, root: MergedRoot<'t>) -> Result<Self::Ok, Self::Error>;
+
+    /// Builds and applies a merged tree using the default merge driver.
+    fn merge(&mut self) -> Result<Self::Ok, Self::Error> {
+        self.merge_with_driver(&DefaultDriver, &DefaultAbortSignal)
+    }
+
+    /// Builds a complete merged tree from the local and remote trees, resolves
+    /// conflicts, dedupes local items, and applies the merged tree using the
+    /// given driver.
+    fn merge_with_driver(
+        &mut self,
+        driver: &impl Driver,
+        signal: &impl AbortSignal,
+    ) -> Result<Self::Ok, Self::Error> {
+        signal.err_if_aborted()?;
+        debug!(driver, "Building local tree");
+        let (local_tree, time) = with_timing(|| self.fetch_local_tree())?;
+        driver.record_telemetry_event(TelemetryEvent::FetchLocalTree(TreeStats {
+            items: local_tree.size(),
+            deletions: local_tree.deletions().len(),
+            problems: local_tree.problems().counts(),
+            time,
+        }));
+        trace!(driver, "Built local tree from mirror\n{}", local_tree);
+
+        signal.err_if_aborted()?;
+        debug!(driver, "Building remote tree");
+        let (remote_tree, time) = with_timing(|| self.fetch_remote_tree())?;
+        driver.record_telemetry_event(TelemetryEvent::FetchRemoteTree(TreeStats {
+            items: remote_tree.size(),
+            deletions: local_tree.deletions().len(),
+            problems: remote_tree.problems().counts(),
+            time,
+        }));
+        trace!(driver, "Built remote tree from mirror\n{}", remote_tree);
+
+        signal.err_if_aborted()?;
+        debug!(driver, "Building merged tree");
+        let merger = Merger::with_driver(driver, signal, &local_tree, &remote_tree);
+        let (merged_root, time) = with_timing(|| merger.merge())?;
+        driver.record_telemetry_event(TelemetryEvent::Merge(time, *merged_root.counts()));
+        trace!(
+            driver,
+            "Built new merged tree\n{}\nDelete Locally: [{}]\nDelete Remotely: [{}]",
+            merged_root.node().to_ascii_string(),
+            merged_root
+                .local_deletions()
+                .map(Guid::as_str)
+                .collect::<Vec<_>>()
+                .join(", "),
+            merged_root
+                .remote_deletions()
+                .map(Guid::as_str)
+                .collect::<Vec<_>>()
+                .join(", ")
+        );
+
+        signal.err_if_aborted()?;
+        debug!(driver, "Applying merged tree");
+        let (result, time) = with_timing(|| self.apply(merged_root))?;
+        driver.record_telemetry_event(TelemetryEvent::Apply(time));
+
+        Ok(result)
+    }
+}
+
+fn with_timing<T, E>(run: impl FnOnce() -> Result<T, E>) -> Result<(T, Duration), E> {
+    let now = Instant::now();
+    run().map(|value| (value, now.elapsed()))
+}
diff --git a/third_party/rust/dogear/src/tests.rs b/third_party/rust/dogear/src/tests.rs
new file mode 100644
index 0000000000..33645c35a2
--- /dev/null
+++ b/third_party/rust/dogear/src/tests.rs
@@ -0,0 +1,2929 @@
+// 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::{
+    cell::Cell,
+    convert::{TryFrom, TryInto},
+    sync::Once,
+};
+
+use env_logger;
+
+use crate::driver::{DefaultAbortSignal, Driver};
+use crate::error::{Error, ErrorKind, Result};
+use crate::guid::{Guid, ROOT_GUID, UNFILED_GUID};
+use crate::merge::{to_strings, Merger, StructureCounts};
+use crate::tree::{
+    self, Builder, Content, DivergedParent, DivergedParentGuid, Item, Kind, MergeState, Problem,
+    ProblemCounts, Problems, Tree, Validity,
+};
+
+#[derive(Debug)]
+struct Node {
+    item: Item,
+    children: Vec<Node>,
+}
+
+impl Node {
+    fn new(item: Item) -> Node {
+        Node {
+            item,
+            children: Vec::new(),
+        }
+    }
+    /// For convenience.
+    fn into_tree(self) -> Result<Tree> {
+        self.try_into()
+    }
+}
+
+impl TryFrom<Node> for Builder {
+    type Error = Error;
+
+    fn try_from(node: Node) -> Result<Builder> {
+        fn inflate(b: &mut Builder, parent_guid: &Guid, node: Node) -> Result<()> {
+            let guid = node.item.guid.clone();
+            if let Err(err) = b.item(node.item) {
+                match err.kind() {
+                    ErrorKind::DuplicateItem(_) => {}
+                    _ => return Err(err),
+                }
+            }
+            b.parent_for(&guid).by_structure(&parent_guid)?;
+            for child in node.children {
+                inflate(b, &guid, child)?;
+            }
+            Ok(())
+        }
+
+        let guid = node.item.guid.clone();
+        let mut builder = Tree::with_root(node.item);
+        builder.reparent_orphans_to(&UNFILED_GUID);
+        for child in node.children {
+            inflate(&mut builder, &guid, child)?;
+        }
+        Ok(builder)
+    }
+}
+
+impl TryFrom<Node> for Tree {
+    type Error = Error;
+    fn try_from(node: Node) -> Result<Tree> {
+        Builder::try_from(node)?.try_into()
+    }
+}
+
+macro_rules! nodes {
+    ($children:tt) => { nodes!(ROOT_GUID, Folder[needs_merge = true], $children) };
+    ($guid:expr, $kind:ident) => { nodes!(Guid::from($guid), $kind[]) };
+    ($guid:expr, $kind:ident [ $( $name:ident = $value:expr ),* ]) => {{
+        #[allow(unused_mut)]
+        let mut item = Item::new(Guid::from($guid), Kind::$kind);
+        $({ item.$name = $value; })*
+        Node::new(item)
+    }};
+    ($guid:expr, $kind:ident, $children:tt) => { nodes!($guid, $kind[], $children) };
+    ($guid:expr, $kind:ident [ $( $name:ident = $value:expr ),* ], { $(( $($children:tt)+ )),* }) => {{
+        #[allow(unused_mut)]
+        let mut node = nodes!($guid, $kind [ $( $name = $value ),* ]);
+        $({
+            let child = nodes!($($children)*);
+            node.children.push(child.into());
+        })*
+        node
+    }};
+}
+
+/// The name of a merge state. These match `tree::MergeState`, but without the
+/// associated nodes to simplify comparisons. We also don't distinguish between
+/// `{Local, Remote}Only` and `{Local, Remote}`, since that doesn't matter for
+/// tests.
+#[derive(Debug)]
+enum MergeStateName {
+    Local,
+    LocalWithNewLocalStructure,
+    Remote,
+    RemoteWithNewRemoteStructure,
+    Unchanged,
+    UnchangedWithNewLocalStructure,
+}
+
+/// A merged node produced by the `merged_nodes!` macro. Can be compared to
+/// a `tree::MergedNode` using `assert_eq!`.
+#[derive(Debug)]
+struct MergedNode {
+    guid: Guid,
+    merge_state_name: MergeStateName,
+    children: Vec<MergedNode>,
+}
+
+impl MergedNode {
+    fn new(guid: Guid, merge_state_name: MergeStateName) -> MergedNode {
+        MergedNode {
+            guid,
+            merge_state_name,
+            children: Vec::new(),
+        }
+    }
+}
+
+impl<'t> PartialEq<tree::MergedNode<'t>> for MergedNode {
+    fn eq(&self, other: &tree::MergedNode<'t>) -> bool {
+        if self.guid != other.guid {
+            return false;
+        }
+        let merge_state_matches = match (&self.merge_state_name, other.merge_state) {
+            (MergeStateName::Local, MergeState::LocalOnly(_)) => true,
+            (
+                MergeStateName::LocalWithNewLocalStructure,
+                MergeState::LocalOnlyWithNewLocalStructure(_),
+            ) => true,
+            (MergeStateName::Remote, MergeState::RemoteOnly(_)) => true,
+            (
+                MergeStateName::RemoteWithNewRemoteStructure,
+                MergeState::RemoteOnlyWithNewRemoteStructure(_),
+            ) => true,
+            (MergeStateName::Local, MergeState::Local { .. }) => true,
+            (
+                MergeStateName::LocalWithNewLocalStructure,
+                MergeState::LocalWithNewLocalStructure { .. },
+            ) => true,
+            (MergeStateName::Remote, MergeState::Remote { .. }) => true,
+            (
+                MergeStateName::RemoteWithNewRemoteStructure,
+                MergeState::RemoteWithNewRemoteStructure { .. },
+            ) => true,
+            (MergeStateName::Unchanged, MergeState::Unchanged { .. }) => true,
+            (
+                MergeStateName::UnchangedWithNewLocalStructure,
+                MergeState::UnchangedWithNewLocalStructure { .. },
+            ) => true,
+            _ => false,
+        };
+        if !merge_state_matches {
+            return false;
+        }
+        self.children == other.merged_children
+    }
+}
+
+macro_rules! merged_nodes {
+    ($children:tt) => { merged_nodes!(ROOT_GUID, Local, $children) };
+    ($guid:expr, $state:ident) => {
+        MergedNode::new(Guid::from($guid), MergeStateName::$state)
+    };
+    ($guid:expr, $state:ident, { $(( $($children:tt)+ )),* }) => {{
+        #[allow(unused_mut)]
+        let mut node = merged_nodes!($guid, $state);
+        $({
+            let child = merged_nodes!($($children)*);
+            node.children.push(child);
+        })*
+        node
+    }};
+}
+
+fn before_each() {
+    static ONCE: Once = Once::new();
+    ONCE.call_once(|| {
+        env_logger::init();
+    });
+}
+
+#[test]
+fn reparent_and_reposition() {
+    before_each();
+
+    let local_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderAAAAAA", Folder[needs_merge = true], {
+                ("bookmarkAAAA", Bookmark[needs_merge = true]),
+                ("folderBBBBBB", Folder[needs_merge = true], {
+                    ("bookmarkCCCC", Bookmark[needs_merge = true]),
+                    ("bookmarkDDDD", Bookmark[needs_merge = true])
+                }),
+                ("bookmarkEEEE", Bookmark[needs_merge = true])
+            }),
+            ("bookmarkFFFF", Bookmark[needs_merge = true])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("folderBBBBBB", Folder[needs_merge = true], {
+                ("bookmarkDDDD", Bookmark[needs_merge = true]),
+                ("bookmarkAAAA", Bookmark[needs_merge = true]),
+                ("bookmarkCCCC", Bookmark[needs_merge = true])
+            })
+        }),
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("folderAAAAAA", Folder, {
+                ("bookmarkFFFF", Bookmark[needs_merge = true]),
+                ("bookmarkEEEE", Bookmark[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, LocalWithNewLocalStructure, {
+        ("menu________", LocalWithNewLocalStructure, {
+            ("bookmarkFFFF", RemoteWithNewRemoteStructure)
+        }),
+        ("unfiled_____", Remote, {
+            ("folderBBBBBB", Remote, {
+                ("bookmarkDDDD", Remote),
+                ("bookmarkAAAA", Remote),
+                ("bookmarkCCCC", Remote)
+            })
+        }),
+        ("toolbar_____", Remote, {
+            ("folderAAAAAA", LocalWithNewLocalStructure, {
+                ("bookmarkEEEE", Remote)
+            })
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 10,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+// This test moves a bookmark that exists locally into a new folder that only
+// exists remotely, and is a later sibling of the local parent.
+#[test]
+fn move_into_parent_sibling() {
+    before_each();
+
+    let local_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderAAAAAA", Folder[needs_merge = true], {
+                ("bookmarkBBBB", Bookmark[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderAAAAAA", Folder[needs_merge = true]),
+            ("folderCCCCCC", Folder[needs_merge = true], {
+                ("bookmarkBBBB", Bookmark[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            ("folderAAAAAA", Remote),
+            ("folderCCCCCC", Remote, {
+                ("bookmarkBBBB", Remote)
+            })
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 4,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn reorder_and_insert() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder, {
+            ("bookmarkAAAA", Bookmark),
+            ("bookmarkBBBB", Bookmark),
+            ("bookmarkCCCC", Bookmark)
+        }),
+        ("toolbar_____", Folder, {
+            ("bookmarkDDDD", Bookmark),
+            ("bookmarkEEEE", Bookmark),
+            ("bookmarkFFFF", Bookmark)
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let local_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkCCCC", Bookmark),
+            ("bookmarkAAAA", Bookmark),
+            ("bookmarkBBBB", Bookmark)
+        }),
+        ("toolbar_____", Folder[needs_merge = true, age = 5], {
+            ("bookmarkDDDD", Bookmark),
+            ("bookmarkEEEE", Bookmark),
+            ("bookmarkFFFF", Bookmark),
+            ("bookmarkGGGG", Bookmark[needs_merge = true]),
+            ("bookmarkHHHH", Bookmark[needs_merge = true])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("menu________", Folder[needs_merge = true, age = 5], {
+            ("bookmarkAAAA", Bookmark[age = 5]),
+            ("bookmarkBBBB", Bookmark[age = 5]),
+            ("bookmarkCCCC", Bookmark[age = 5]),
+            ("bookmarkIIII", Bookmark[needs_merge = true]),
+            ("bookmarkJJJJ", Bookmark[needs_merge = true])
+        }),
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("bookmarkFFFF", Bookmark),
+            ("bookmarkDDDD", Bookmark),
+            ("bookmarkEEEE", Bookmark)
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            // The server has an older menu, so we should use the local order (C A B)
+            // as the base, then append (I J).
+            ("bookmarkCCCC", Unchanged),
+            ("bookmarkAAAA", Unchanged),
+            ("bookmarkBBBB", Unchanged),
+            ("bookmarkIIII", Remote),
+            ("bookmarkJJJJ", Remote)
+        }),
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            // The server has a newer toolbar, so we should use the remote order (F D E)
+            // as the base, then append (G H). However, we always prefer the local state
+            // for roots, to avoid clobbering titles, so this is
+            // `LocalWithNewLocalStructure` instead of `RemoteWithNewRemoteStructure`.
+            ("bookmarkFFFF", Unchanged),
+            ("bookmarkDDDD", Unchanged),
+            ("bookmarkEEEE", Unchanged),
+            ("bookmarkGGGG", Local),
+            ("bookmarkHHHH", Local)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 12,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn unchanged_newer_changed_older() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder[age = 5], {
+            ("folderAAAAAA", Folder[age = 5]),
+            ("bookmarkBBBB", Bookmark[age = 5])
+        }),
+        ("toolbar_____", Folder[age = 5], {
+            ("folderCCCCCC", Folder[age = 5]),
+            ("bookmarkDDDD", Bookmark[age = 5])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        // Even though the local menu is newer (local = 5s, remote = 9s;
+        // adding E updated the modified times of A and the menu), it's
+        // not *changed* locally, so we should merge remote children first.
+        ("menu________", Folder, {
+            ("folderAAAAAA", Folder[needs_merge = true], {
+                ("bookmarkEEEE", Bookmark[needs_merge = true])
+            }),
+            ("bookmarkBBBB", Bookmark[age = 5])
+        }),
+        ("toolbar_____", Folder[needs_merge = true, age = 5], {
+            ("bookmarkDDDD", Bookmark[age = 5])
+        })
+    }))
+    .unwrap();
+    local_tree_builder.deletion("folderCCCCCC".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true, age = 5], {
+            ("bookmarkBBBB", Bookmark[age = 5])
+        }),
+        // Even though the remote toolbar is newer (local = 15s, remote = 10s), it's
+        // not changed remotely, so we should merge local children first.
+        ("toolbar_____", Folder[age = 5], {
+            ("folderCCCCCC", Folder[needs_merge = true], {
+                ("bookmarkFFFF", Bookmark[needs_merge = true])
+            }),
+            ("bookmarkDDDD", Bookmark[age = 5])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder.deletion("folderAAAAAA".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            ("bookmarkBBBB", Unchanged),
+            ("bookmarkEEEE", LocalWithNewLocalStructure)
+        }),
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            ("bookmarkDDDD", Unchanged),
+            ("bookmarkFFFF", RemoteWithNewRemoteStructure)
+        })
+    });
+    let expected_deletions = &["folderAAAAAA", "folderCCCCCC"];
+    let expected_telem = StructureCounts {
+        local_deletes: 1,
+        remote_deletes: 1,
+        merged_nodes: 6,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn newer_local_moves() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder[age = 10], {
+            ("bookmarkAAAA", Bookmark[age = 10]),
+            ("folderBBBBBB", Folder[age = 10], {
+                ("bookmarkCCCC", Bookmark[age = 10])
+            }),
+            ("folderDDDDDD", Folder[age = 10])
+        }),
+        ("toolbar_____", Folder[age = 10], {
+            ("bookmarkEEEE", Bookmark[age = 10]),
+            ("folderFFFFFF", Folder[age = 10], {
+                ("bookmarkGGGG", Bookmark[age = 10])
+            }),
+            ("folderHHHHHH", Folder[age = 10])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let local_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderDDDDDD", Folder[needs_merge = true], {
+                ("bookmarkCCCC", Bookmark[needs_merge = true])
+            })
+        }),
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("folderHHHHHH", Folder[needs_merge = true], {
+                ("bookmarkGGGG", Bookmark[needs_merge = true])
+            }),
+            ("folderFFFFFF", Folder[needs_merge = true]),
+            ("bookmarkEEEE", Bookmark[age = 10])
+        }),
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true])
+        }),
+        ("mobile______", Folder[needs_merge = true], {
+            ("folderBBBBBB", Folder[needs_merge = true])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("mobile______", Folder[needs_merge = true, age = 5], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true, age = 5])
+        }),
+        ("unfiled_____", Folder[needs_merge = true, age = 5], {
+            ("folderBBBBBB", Folder[needs_merge = true, age = 5])
+        }),
+        ("menu________", Folder[needs_merge = true, age = 5], {
+            ("folderDDDDDD", Folder[needs_merge = true, age = 5], {
+                ("bookmarkGGGG", Bookmark[needs_merge = true, age = 5])
+            })
+        }),
+        ("toolbar_____", Folder[needs_merge = true, age = 5], {
+            ("folderFFFFFF", Folder[needs_merge = true, age = 5]),
+            ("bookmarkEEEE", Bookmark[age = 10]),
+            ("folderHHHHHH", Folder[needs_merge = true, age = 5], {
+                ("bookmarkCCCC", Bookmark[needs_merge = true, age = 5])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", Local, {
+            ("folderDDDDDD", Local, {
+                ("bookmarkCCCC", Local)
+            })
+        }),
+        ("toolbar_____", Local, {
+            ("folderHHHHHH", Local, {
+                ("bookmarkGGGG", Local)
+            }),
+            ("folderFFFFFF", Local),
+            ("bookmarkEEEE", Unchanged)
+        }),
+        ("unfiled_____", Local, {
+            ("bookmarkAAAA", Local)
+        }),
+        ("mobile______", Local, {
+            ("folderBBBBBB", Local)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 12,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn newer_remote_moves() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder[age = 10], {
+            ("bookmarkAAAA", Bookmark[age = 10]),
+            ("folderBBBBBB", Folder[age = 10], {
+                ("bookmarkCCCC", Bookmark[age = 10])
+            }),
+            ("folderDDDDDD", Folder[age = 10])
+        }),
+        ("toolbar_____", Folder[age = 10], {
+            ("bookmarkEEEE", Bookmark[age = 10]),
+            ("folderFFFFFF", Folder[age = 10], {
+                ("bookmarkGGGG", Bookmark[age = 10])
+            }),
+            ("folderHHHHHH", Folder[age = 10])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let local_tree = nodes!({
+        ("menu________", Folder[needs_merge = true, age = 5], {
+            ("folderDDDDDD", Folder[needs_merge = true, age = 5], {
+                ("bookmarkCCCC", Bookmark[needs_merge = true, age = 5])
+            })
+        }),
+        ("toolbar_____", Folder[needs_merge = true, age = 5], {
+            ("folderHHHHHH", Folder[needs_merge = true, age = 5], {
+                ("bookmarkGGGG", Bookmark[needs_merge = true, age = 5])
+            }),
+            ("folderFFFFFF", Folder[needs_merge = true, age = 5]),
+            ("bookmarkEEEE", Bookmark[age = 10])
+        }),
+        ("unfiled_____", Folder[needs_merge = true, age = 5], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true, age = 5])
+        }),
+        ("mobile______", Folder[needs_merge = true, age = 5], {
+            ("folderBBBBBB", Folder[needs_merge = true, age = 5])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("mobile______", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true])
+        }),
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("folderBBBBBB", Folder[needs_merge = true])
+        }),
+        ("menu________", Folder[needs_merge = true], {
+            ("folderDDDDDD", Folder[needs_merge = true], {
+                ("bookmarkGGGG", Bookmark[needs_merge = true])
+            })
+        }),
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("folderFFFFFF", Folder[needs_merge = true]),
+            ("bookmarkEEEE", Bookmark[age = 10]),
+            ("folderHHHHHH", Folder[needs_merge = true], {
+                ("bookmarkCCCC", Bookmark[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", Local, {
+            ("folderDDDDDD", Remote, {
+                ("bookmarkGGGG", Remote)
+            })
+        }),
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            ("folderFFFFFF", Remote),
+            ("bookmarkEEEE", Unchanged),
+            ("folderHHHHHH", Remote, {
+                ("bookmarkCCCC", Remote)
+            })
+        }),
+        ("unfiled_____", LocalWithNewLocalStructure, {
+            ("folderBBBBBB", Remote)
+        }),
+        ("mobile______", LocalWithNewLocalStructure, {
+            ("bookmarkAAAA", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 12,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn value_structure_conflict() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder, {
+            ("folderAAAAAA", Folder, {
+                ("bookmarkBBBB", Bookmark),
+                ("bookmarkCCCC", Bookmark)
+            }),
+            ("folderDDDDDD", Folder, {
+                ("bookmarkEEEE", Bookmark)
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let local_tree = nodes!({
+        ("menu________", Folder, {
+            ("folderAAAAAA", Folder[needs_merge = true, age = 10], {
+                ("bookmarkCCCC", Bookmark)
+            }),
+            ("folderDDDDDD", Folder[needs_merge = true, age = 10], {
+                ("bookmarkBBBB", Bookmark),
+                ("bookmarkEEEE", Bookmark[age = 10])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("menu________", Folder, {
+            ("folderAAAAAA", Folder, {
+                ("bookmarkBBBB", Bookmark),
+                ("bookmarkCCCC", Bookmark)
+            }),
+            ("folderDDDDDD", Folder[needs_merge = true, age = 5], {
+                ("bookmarkEEEE", Bookmark[needs_merge = true, age = 5])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", Unchanged, {
+            ("folderAAAAAA", Local, {
+                ("bookmarkCCCC", Unchanged)
+            }),
+            ("folderDDDDDD", RemoteWithNewRemoteStructure, {
+                ("bookmarkEEEE", Remote),
+                ("bookmarkBBBB", Local)
+            })
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 6,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn complex_move_with_additions() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder, {
+            ("folderAAAAAA", Folder, {
+                ("bookmarkBBBB", Bookmark),
+                ("bookmarkCCCC", Bookmark)
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let local_tree = nodes!({
+        ("menu________", Folder, {
+            ("folderAAAAAA", Folder[needs_merge = true], {
+                ("bookmarkBBBB", Bookmark),
+                ("bookmarkCCCC", Bookmark),
+                ("bookmarkDDDD", Bookmark[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkCCCC", Bookmark[needs_merge = true])
+        }),
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("folderAAAAAA", Folder[needs_merge = true], {
+                ("bookmarkBBBB", Bookmark),
+                ("bookmarkEEEE", Bookmark[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, LocalWithNewLocalStructure, {
+        ("menu________", UnchangedWithNewLocalStructure, {
+            ("bookmarkCCCC", Remote)
+        }),
+        ("toolbar_____", Remote, {
+            ("folderAAAAAA", RemoteWithNewRemoteStructure, {
+                // We can guarantee child order (B E D), since we always walk remote
+                // children first, and the remote folder A record is newer than the
+                // local folder. If the local folder were newer, the order would be
+                // (D B E).
+                ("bookmarkBBBB", Unchanged),
+                ("bookmarkEEEE", Remote),
+                ("bookmarkDDDD", Local)
+            })
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 7,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn complex_orphaning() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("toolbar_____", Folder, {
+            ("folderAAAAAA", Folder, {
+                ("folderBBBBBB", Folder)
+            })
+        }),
+        ("menu________", Folder, {
+            ("folderCCCCCC", Folder, {
+                ("folderDDDDDD", Folder, {
+                    ("folderEEEEEE", Folder)
+                })
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    // Locally: delete E, add B > F.
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("toolbar_____", Folder[needs_merge = false], {
+            ("folderAAAAAA", Folder, {
+                ("folderBBBBBB", Folder[needs_merge = true], {
+                    ("bookmarkFFFF", Bookmark[needs_merge = true])
+                })
+            })
+        }),
+        ("menu________", Folder, {
+            ("folderCCCCCC", Folder, {
+                ("folderDDDDDD", Folder[needs_merge = true])
+            })
+        })
+    }))
+    .unwrap();
+    local_tree_builder.deletion("folderEEEEEE".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    // Remotely: delete B, add E > G.
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("toolbar_____", Folder, {
+            ("folderAAAAAA", Folder[needs_merge = true])
+        }),
+        ("menu________", Folder, {
+            ("folderCCCCCC", Folder, {
+                ("folderDDDDDD", Folder, {
+                    ("folderEEEEEE", Folder[needs_merge = true], {
+                        ("bookmarkGGGG", Bookmark[needs_merge = true])
+                    })
+                })
+            })
+        })
+    }))
+    .unwrap();
+    remote_tree_builder.deletion("folderBBBBBB".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("toolbar_____", Unchanged, {
+            ("folderAAAAAA", RemoteWithNewRemoteStructure, {
+                // B was deleted remotely, so F moved to A, the closest
+                // surviving parent.
+                ("bookmarkFFFF", LocalWithNewLocalStructure)
+            })
+        }),
+        ("menu________", Unchanged, {
+            ("folderCCCCCC", Unchanged, {
+                ("folderDDDDDD", LocalWithNewLocalStructure, {
+                    // E was deleted locally, so G moved to D.
+                    ("bookmarkGGGG", RemoteWithNewRemoteStructure)
+                })
+            })
+        })
+    });
+    let expected_deletions = &["folderBBBBBB", "folderEEEEEE"];
+    let expected_telem = StructureCounts {
+        local_deletes: 1,
+        remote_deletes: 1,
+        merged_nodes: 7,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn locally_modified_remotely_deleted() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("toolbar_____", Folder, {
+            ("folderAAAAAA", Folder, {
+                ("folderBBBBBB", Folder)
+            })
+        }),
+        ("menu________", Folder, {
+            ("folderCCCCCC", Folder, {
+                ("folderDDDDDD", Folder, {
+                    ("folderEEEEEE", Folder)
+                })
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("toolbar_____", Folder, {
+            ("folderAAAAAA", Folder, {
+                ("folderBBBBBB", Folder[needs_merge = true], {
+                    ("bookmarkFFFF", Bookmark[needs_merge = true])
+                })
+            })
+        }),
+        ("menu________", Folder, {
+            ("folderCCCCCC", Folder, {
+                ("folderDDDDDD", Folder[needs_merge = true])
+            })
+        })
+    }))
+    .unwrap();
+    local_tree_builder.deletion("folderEEEEEE".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("toolbar_____", Folder, {
+            ("folderAAAAAA", Folder[needs_merge = true])
+        }),
+        ("menu________", Folder, {
+            ("folderCCCCCC", Folder, {
+                ("folderDDDDDD", Folder, {
+                    ("folderEEEEEE", Folder[needs_merge = true], {
+                        ("bookmarkGGGG", Bookmark[needs_merge = true])
+                    })
+                })
+            })
+        })
+    }))
+    .unwrap();
+    remote_tree_builder.deletion("folderBBBBBB".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("toolbar_____", Unchanged, {
+            ("folderAAAAAA", RemoteWithNewRemoteStructure, {
+                ("bookmarkFFFF", LocalWithNewLocalStructure)
+            })
+        }),
+        ("menu________", Unchanged, {
+            ("folderCCCCCC", Unchanged, {
+                ("folderDDDDDD", LocalWithNewLocalStructure, {
+                    ("bookmarkGGGG", RemoteWithNewRemoteStructure)
+                })
+            })
+        })
+    });
+    let expected_deletions = &["folderBBBBBB", "folderEEEEEE"];
+    let expected_telem = StructureCounts {
+        local_deletes: 1,
+        remote_deletes: 1,
+        merged_nodes: 7,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn locally_deleted_remotely_modified() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder, {
+            ("bookmarkAAAA", Bookmark),
+            ("folderBBBBBB", Folder, {
+                ("bookmarkCCCC", Bookmark),
+                ("folderDDDDDD", Folder, {
+                    ("bookmarkEEEE", Bookmark)
+                })
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let mut local_tree_builder =
+        Builder::try_from(nodes!({ ("menu________", Folder[needs_merge = true]) })).unwrap();
+    local_tree_builder
+        .deletion("bookmarkAAAA".into())
+        .deletion("folderBBBBBB".into())
+        .deletion("bookmarkCCCC".into())
+        .deletion("folderDDDDDD".into())
+        .deletion("bookmarkEEEE".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let remote_tree = nodes!({
+        ("menu________", Folder, {
+            ("bookmarkAAAA", Bookmark[needs_merge = true]),
+            ("folderBBBBBB", Folder[needs_merge = true], {
+                ("bookmarkCCCC", Bookmark),
+                ("folderDDDDDD", Folder[needs_merge = true], {
+                    ("bookmarkEEEE", Bookmark),
+                    ("bookmarkFFFF", Bookmark[needs_merge = true])
+                }),
+                ("bookmarkGGGG", Bookmark[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            ("bookmarkAAAA", Remote),
+            ("bookmarkFFFF", RemoteWithNewRemoteStructure),
+            ("bookmarkGGGG", RemoteWithNewRemoteStructure)
+        })
+    });
+    let expected_deletions = &[
+        "bookmarkCCCC",
+        "bookmarkEEEE",
+        "folderBBBBBB",
+        "folderDDDDDD",
+    ];
+    let expected_telem = StructureCounts {
+        remote_revives: 1,
+        local_deletes: 2,
+        merged_nodes: 4,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn nonexistent_on_one_side() {
+    before_each();
+
+    // A doesn't exist remotely.
+    let mut local_tree_builder = Tree::with_root(Item::new(ROOT_GUID, Kind::Folder));
+    local_tree_builder.deletion("bookmarkAAAA".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    // B doesn't exist locally.
+    let mut remote_tree_builder = Tree::with_root(Item::new(ROOT_GUID, Kind::Folder));
+    remote_tree_builder.deletion("bookmarkBBBB".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let mut expected_root = Item::new(ROOT_GUID, Kind::Folder);
+    expected_root.needs_merge = true;
+    let expected_tree = merged_nodes!(ROOT_GUID, Unchanged, {});
+    let expected_deletions = &["bookmarkAAAA", "bookmarkBBBB"];
+    let expected_telem = StructureCounts {
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    let ops = merged_root.completion_ops();
+    assert_eq!(
+        ops.summarize(),
+        &[
+            "Flag remote bookmarkBBBB as merged",
+            "Delete local tombstone bookmarkAAAA",
+        ]
+    );
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn clear_folder_then_delete() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder, {
+            ("folderAAAAAA", Folder, {
+                ("bookmarkBBBB", Bookmark),
+                ("bookmarkCCCC", Bookmark)
+            }),
+            ("folderDDDDDD", Folder, {
+                ("bookmarkEEEE", Bookmark),
+                ("bookmarkFFFF", Bookmark)
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderAAAAAA", Folder, {
+                ("bookmarkBBBB", Bookmark),
+                ("bookmarkCCCC", Bookmark)
+            }),
+            ("bookmarkEEEE", Bookmark[needs_merge = true])
+        }),
+        ("mobile______", Folder[needs_merge = true], {
+            ("bookmarkFFFF", Bookmark[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    local_tree_builder.deletion("folderDDDDDD".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkBBBB", Bookmark[needs_merge = true]),
+            ("folderDDDDDD", Folder, {
+                ("bookmarkEEEE", Bookmark),
+                ("bookmarkFFFF", Bookmark)
+            })
+        }),
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("bookmarkCCCC", Bookmark[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder.deletion("folderAAAAAA".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, LocalWithNewLocalStructure, {
+        ("menu________", LocalWithNewLocalStructure, {
+            ("bookmarkBBBB", Remote),
+            ("bookmarkEEEE", Local)
+        }),
+        ("mobile______", Local, {
+            ("bookmarkFFFF", Local)
+        }),
+        ("unfiled_____", Remote, {
+            ("bookmarkCCCC", Remote)
+        })
+    });
+    let expected_deletions = &["folderAAAAAA", "folderDDDDDD"];
+    let expected_telem = StructureCounts {
+        merged_nodes: 7,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn newer_move_to_deleted() {
+    before_each();
+
+    let _shared_tree = nodes!({
+        ("menu________", Folder, {
+            ("folderAAAAAA", Folder, {
+                ("bookmarkBBBB", Bookmark)
+            }),
+            ("folderCCCCCC", Folder, {
+                ("bookmarkDDDD", Bookmark)
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            // A is younger locally. However, we should *not* revert
+            // remotely moving B to the toolbar. (Locally, B exists in A,
+            // but we deleted the now-empty A remotely).
+            ("folderAAAAAA", Folder[needs_merge = true], {
+                ("bookmarkBBBB", Bookmark[age = 5]),
+                ("bookmarkEEEE", Bookmark[needs_merge = true])
+            })
+        }),
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("bookmarkDDDD", Bookmark[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    local_tree_builder.deletion("folderCCCCCC".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true, age = 5], {
+            // C is younger remotely. However, we should *not* revert
+            // locally moving D to the toolbar. (Locally, D exists in C,
+            // but we deleted the now-empty C locally).
+            ("folderCCCCCC", Folder[needs_merge = true], {
+                ("bookmarkDDDD", Bookmark[age = 5]),
+                ("bookmarkFFFF", Bookmark[needs_merge = true])
+            })
+        }),
+        ("toolbar_____", Folder[needs_merge = true, age = 5], {
+            ("bookmarkBBBB", Bookmark[needs_merge = true, age = 5])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder.deletion("folderAAAAAA".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            ("bookmarkEEEE", LocalWithNewLocalStructure),
+            ("bookmarkFFFF", RemoteWithNewRemoteStructure)
+        }),
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            ("bookmarkDDDD", Local),
+            ("bookmarkBBBB", Remote)
+        })
+    });
+    let expected_deletions = &["folderAAAAAA", "folderCCCCCC"];
+    let expected_telem = StructureCounts {
+        local_deletes: 1,
+        remote_deletes: 1,
+        merged_nodes: 6,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn deduping_multiple_candidates() {
+    before_each();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true, age = 5], {
+            ("folderAAAAA1", Folder[needs_merge = true, age = 5]),
+            ("folderAAAAA2", Folder[needs_merge = true, age = 5])
+        }),
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("folderBBBBB1", Folder[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    local_tree_builder
+        .mutate(&"folderAAAAA1".into())
+        .content(Content::Folder { title: "A".into() });
+    local_tree_builder
+        .mutate(&"folderAAAAA2".into())
+        .content(Content::Folder { title: "A".into() });
+    local_tree_builder
+        .mutate(&"folderBBBBB1".into())
+        .content(Content::Folder { title: "B".into() });
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderAAAAA1", Folder[needs_merge = true])
+        }),
+        ("toolbar_____", Folder[needs_merge = true, age = 5], {
+            ("folderBBBBB1", Folder[needs_merge = true, age = 5]),
+            ("folderBBBBB2", Folder[needs_merge = true, age = 5])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder
+        .mutate(&"folderAAAAA1".into())
+        .content(Content::Folder { title: "A".into() });
+    remote_tree_builder
+        .mutate(&"folderBBBBB1".into())
+        .content(Content::Folder { title: "B".into() });
+    remote_tree_builder
+        .mutate(&"folderBBBBB2".into())
+        .content(Content::Folder { title: "B".into() });
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            ("folderAAAAA1", Remote),
+            ("folderAAAAA2", Local)
+        }),
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            ("folderBBBBB1", Local),
+            ("folderBBBBB2", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 6,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn deduping_local_newer() {
+    before_each();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkAAA1", Bookmark[needs_merge = true]),
+            ("bookmarkAAA2", Bookmark[needs_merge = true]),
+            ("bookmarkAAA3", Bookmark[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    local_tree_builder
+        .mutate(&"bookmarkAAA1".into())
+        .content(Content::Bookmark {
+            title: "A".into(),
+            url_href: "http://example.com/a".into(),
+        });
+    local_tree_builder
+        .mutate(&"bookmarkAAA2".into())
+        .content(Content::Bookmark {
+            title: "A".into(),
+            url_href: "http://example.com/a".into(),
+        });
+    local_tree_builder
+        .mutate(&"bookmarkAAA3".into())
+        .content(Content::Bookmark {
+            title: "A".into(),
+            url_href: "http://example.com/a".into(),
+        });
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true, age = 5], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true, age = 5]),
+            ("bookmarkAAA4", Bookmark[needs_merge = true, age = 5]),
+            ("bookmarkAAA5", Bookmark)
+        })
+    }))
+    .unwrap();
+    remote_tree_builder
+        .mutate(&"bookmarkAAAA".into())
+        .content(Content::Bookmark {
+            title: "A".into(),
+            url_href: "http://example.com/a".into(),
+        });
+    remote_tree_builder
+        .mutate(&"bookmarkAAA4".into())
+        .content(Content::Bookmark {
+            title: "A".into(),
+            url_href: "http://example.com/a".into(),
+        });
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            ("bookmarkAAAA", LocalWithNewLocalStructure),
+            ("bookmarkAAA4", LocalWithNewLocalStructure),
+            ("bookmarkAAA3", Local),
+            ("bookmarkAAA5", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        dupes: 2,
+        merged_nodes: 5,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn deduping_remote_newer() {
+    before_each();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true, age = 5], {
+            // Shouldn't dedupe to `folderAAAAA1` because it's not in
+            // `new_local_contents`.
+            ("folderAAAAAA", Folder[needs_merge = true, age = 5], {
+                // Shouldn't dedupe to `bookmarkBBB1`. (bookmarkG111)
+                ("bookmarkBBBB", Bookmark[age = 10]),
+                // Not a candidate for `bookmarkCCC1` because the URLs are
+                // different. (bookmarkH111)
+                ("bookmarkCCCC", Bookmark[needs_merge = true, age = 5])
+            }),
+            // Should dedupe to `folderDDDDD1`. (folderB11111)
+            ("folderDDDDDD", Folder[needs_merge = true, age = 5], {
+                // Should dedupe to `bookmarkEEE1`. (bookmarkC222)
+                ("bookmarkEEEE", Bookmark[needs_merge = true, age = 5]),
+                // Should dedupe to `separatorFF1` because the positions are
+                // the same. (separatorF11)
+                ("separatorFFF", Separator[needs_merge = true, age = 5])
+            }),
+            // Shouldn't dedupe to `separatorGG1`, because the positions are
+            // different. (separatorE11)
+            ("separatorGGG", Separator[needs_merge = true, age = 5]),
+            // Shouldn't dedupe to `bookmarkHHH1` because the parents are
+            // different. (bookmarkC222)
+            ("bookmarkHHHH", Bookmark[needs_merge = true, age = 5]),
+            // Should dedupe to `queryIIIIII1`.
+            ("queryIIIIIII", Query[needs_merge = true, age = 5])
+        })
+    }))
+    .unwrap();
+    local_tree_builder
+        .mutate(&"bookmarkCCCC".into())
+        .content(Content::Bookmark {
+            title: "C".into(),
+            url_href: "http://example.com/c".into(),
+        });
+    local_tree_builder
+        .mutate(&"folderDDDDDD".into())
+        .content(Content::Folder { title: "D".into() });
+    local_tree_builder
+        .mutate(&"bookmarkEEEE".into())
+        .content(Content::Bookmark {
+            title: "E".into(),
+            url_href: "http://example.com/e".into(),
+        });
+    local_tree_builder
+        .mutate(&"separatorFFF".into())
+        .content(Content::Separator);
+    local_tree_builder
+        .mutate(&"separatorGGG".into())
+        .content(Content::Separator);
+    local_tree_builder
+        .mutate(&"bookmarkHHHH".into())
+        .content(Content::Bookmark {
+            title: "H".into(),
+            url_href: "http://example.com/h".into(),
+        });
+    local_tree_builder
+        .mutate(&"queryIIIIIII".into())
+        .content(Content::Bookmark {
+            title: "I".into(),
+            url_href: "place:maxResults=10&sort=8".into(),
+        });
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderAAAAAA", Folder[needs_merge = true], {
+                ("bookmarkBBBB", Bookmark[age = 10]),
+                ("bookmarkCCC1", Bookmark[needs_merge = true])
+            }),
+            ("folderDDDDD1", Folder[needs_merge = true], {
+                ("bookmarkEEE1", Bookmark[needs_merge = true]),
+                ("separatorFF1", Separator[needs_merge = true])
+            }),
+            ("separatorGG1", Separator[needs_merge = true]),
+            ("bookmarkHHH1", Bookmark[needs_merge = true]),
+            ("queryIIIIII1", Query[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder
+        .mutate(&"bookmarkCCC1".into())
+        .content(Content::Bookmark {
+            title: "C".into(),
+            url_href: "http://example.com/c1".into(),
+        });
+    remote_tree_builder
+        .mutate(&"folderDDDDD1".into())
+        .content(Content::Folder { title: "D".into() });
+    remote_tree_builder
+        .mutate(&"bookmarkEEE1".into())
+        .content(Content::Bookmark {
+            title: "E".into(),
+            url_href: "http://example.com/e".into(),
+        });
+    remote_tree_builder
+        .mutate(&"separatorFF1".into())
+        .content(Content::Separator);
+    remote_tree_builder
+        .mutate(&"separatorGG1".into())
+        .content(Content::Separator);
+    remote_tree_builder
+        .mutate(&"bookmarkHHH1".into())
+        .content(Content::Bookmark {
+            title: "H".into(),
+            url_href: "http://example.com/h".into(),
+        });
+    remote_tree_builder
+        .mutate(&"queryIIIIII1".into())
+        .content(Content::Bookmark {
+            title: "I".into(),
+            url_href: "place:maxResults=10&sort=8".into(),
+        });
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            ("folderAAAAAA", RemoteWithNewRemoteStructure, {
+                ("bookmarkBBBB", Unchanged),
+                ("bookmarkCCC1", Remote),
+                ("bookmarkCCCC", Local)
+            }),
+            ("folderDDDDD1", Remote, {
+                ("bookmarkEEE1", Remote),
+                ("separatorFF1", Remote)
+            }),
+            ("separatorGG1", Remote),
+            ("bookmarkHHH1", Remote),
+            ("queryIIIIII1", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        dupes: 6,
+        merged_nodes: 11,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn complex_deduping() {
+    before_each();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderAAAAAA", Folder[needs_merge = true, age = 10], {
+                ("bookmarkBBBB", Bookmark[needs_merge = true, age = 10]),
+                ("bookmarkCCCC", Bookmark[needs_merge = true, age = 10])
+            }),
+            ("folderDDDDDD", Folder[needs_merge = true], {
+                ("bookmarkEEEE", Bookmark[needs_merge = true, age = 5])
+            }),
+            ("folderFFFFFF", Folder[needs_merge = true, age = 5], {
+                ("bookmarkGGGG", Bookmark[needs_merge = true, age = 5])
+            })
+        })
+    }))
+    .unwrap();
+    local_tree_builder
+        .mutate(&"folderAAAAAA".into())
+        .content(Content::Folder { title: "A".into() });
+    local_tree_builder
+        .mutate(&"bookmarkBBBB".into())
+        .content(Content::Bookmark {
+            title: "B".into(),
+            url_href: "http://example.com/b".into(),
+        });
+    local_tree_builder
+        .mutate(&"bookmarkCCCC".into())
+        .content(Content::Bookmark {
+            title: "C".into(),
+            url_href: "http://example.com/c".into(),
+        });
+    local_tree_builder
+        .mutate(&"folderDDDDDD".into())
+        .content(Content::Folder { title: "D".into() });
+    local_tree_builder
+        .mutate(&"bookmarkEEEE".into())
+        .content(Content::Bookmark {
+            title: "E".into(),
+            url_href: "http://example.com/e".into(),
+        });
+    local_tree_builder
+        .mutate(&"folderFFFFFF".into())
+        .content(Content::Folder { title: "F".into() });
+    local_tree_builder
+        .mutate(&"bookmarkGGGG".into())
+        .content(Content::Bookmark {
+            title: "G".into(),
+            url_href: "http://example.com/g".into(),
+        });
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("folderAAAAA1", Folder[needs_merge = true], {
+                ("bookmarkBBB1", Bookmark[needs_merge = true])
+            }),
+            ("folderDDDDD1", Folder[needs_merge = true, age = 5], {
+                ("bookmarkEEE1", Bookmark[needs_merge = true])
+            }),
+            ("folderFFFFF1", Folder[needs_merge = true], {
+                ("bookmarkGGG1", Bookmark[needs_merge = true, age = 5]),
+                ("bookmarkHHH1", Bookmark[needs_merge = true])
+            })
+        })
+    }))
+    .unwrap();
+    remote_tree_builder
+        .mutate(&"folderAAAAA1".into())
+        .content(Content::Folder { title: "A".into() });
+    remote_tree_builder
+        .mutate(&"bookmarkBBB1".into())
+        .content(Content::Bookmark {
+            title: "B".into(),
+            url_href: "http://example.com/b".into(),
+        });
+    remote_tree_builder
+        .mutate(&"folderDDDDD1".into())
+        .content(Content::Folder { title: "D".into() });
+    remote_tree_builder
+        .mutate(&"bookmarkEEE1".into())
+        .content(Content::Bookmark {
+            title: "E".into(),
+            url_href: "http://example.com/e".into(),
+        });
+    remote_tree_builder
+        .mutate(&"folderFFFFF1".into())
+        .content(Content::Folder { title: "F".into() });
+    remote_tree_builder
+        .mutate(&"bookmarkGGG1".into())
+        .content(Content::Bookmark {
+            title: "G".into(),
+            url_href: "http://example.com/g".into(),
+        });
+    remote_tree_builder
+        .mutate(&"bookmarkHHH1".into())
+        .content(Content::Bookmark {
+            title: "H".into(),
+            url_href: "http://example.com/h".into(),
+        });
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", LocalWithNewLocalStructure, {
+            ("folderAAAAA1", RemoteWithNewRemoteStructure, {
+                ("bookmarkBBB1", Remote),
+                ("bookmarkCCCC", Local)
+            }),
+            ("folderDDDDD1", LocalWithNewLocalStructure, {
+                ("bookmarkEEE1", Remote)
+            }),
+            ("folderFFFFF1", Remote, {
+                ("bookmarkGGG1", Remote),
+                ("bookmarkHHH1", Remote)
+            })
+        })
+    });
+    let expected_telem = StructureCounts {
+        dupes: 6,
+        merged_nodes: 9,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn left_pane_root() {
+    before_each();
+
+    let local_tree = Tree::with_root(Item::new(ROOT_GUID, Kind::Folder))
+        .into_tree()
+        .unwrap();
+
+    let remote_tree = nodes!({
+        ("folderLEFTPR", Folder[needs_merge = true], {
+            ("folderLEFTPQ", Query[needs_merge = true]),
+            ("folderLEFTPF", Folder[needs_merge = true], {
+                ("folderLEFTPC", Query[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, Local);
+    let expected_deletions = &[
+        "folderLEFTPC",
+        "folderLEFTPF",
+        "folderLEFTPQ",
+        "folderLEFTPR",
+    ];
+    let expected_telem = StructureCounts {
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn livemarks() {
+    before_each();
+
+    let local_tree = nodes!({
+        ("menu________", Folder, {
+            ("livemarkAAAA", Livemark),
+            ("livemarkBBBB", Folder),
+            ("livemarkCCCC", Livemark)
+        }),
+        ("toolbar_____", Folder, {
+            ("livemarkDDDD", Livemark)
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("menu________", Folder, {
+            ("livemarkAAAA", Livemark),
+            ("livemarkBBBB", Livemark),
+            ("livemarkCCCC", Folder)
+        }),
+        ("unfiled_____", Folder, {
+            ("livemarkEEEE", Livemark)
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, LocalWithNewLocalStructure, {
+        ("menu________", LocalWithNewLocalStructure),
+        ("toolbar_____", LocalWithNewLocalStructure),
+        ("unfiled_____", RemoteWithNewRemoteStructure)
+    });
+    let expected_deletions = &[
+        "livemarkAAAA",
+        "livemarkBBBB",
+        "livemarkCCCC",
+        "livemarkDDDD",
+        "livemarkEEEE",
+    ];
+    let expected_telem = StructureCounts {
+        merged_nodes: 3,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn non_syncable_items() {
+    before_each();
+
+    let local_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            // A is non-syncable remotely, but B doesn't exist remotely, so
+            // we'll remove A from the merged structure, and move B to the
+            // menu.
+            ("folderAAAAAA", Folder[needs_merge = true], {
+                ("bookmarkBBBB", Bookmark[needs_merge = true])
+            })
+        }),
+        ("unfiled_____", Folder, {
+            // Orphaned left pane queries.
+            ("folderLEFTPQ", Query),
+            ("folderLEFTPC", Query)
+        }),
+        ("rootCCCCCCCC", Folder, {
+            // Non-syncable local root and children.
+            ("folderDDDDDD", Folder, {
+                ("bookmarkEEEE", Bookmark)
+            }),
+            ("bookmarkFFFF", Bookmark)
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("unfiled_____", Folder[needs_merge = true], {
+            // D, J, and G are syncable remotely, but D is non-syncable
+            // locally. Since J and G don't exist locally, and are syncable
+            // remotely, we'll remove D, and move J and G to unfiled.
+            ("folderDDDDDD", Folder[needs_merge = true], {
+                ("bookmarkJJJJ", Bookmark[needs_merge = true])
+            }),
+            ("bookmarkGGGG", Bookmark)
+        }),
+        ("rootHHHHHHHH", Folder[needs_merge = true], {
+            // H is a non-syncable root that only exists remotely. A is
+            // non-syncable remotely, and syncable locally. We should
+            // remove A and its descendants locally, since its parent
+            // H is known to be non-syncable remotely.
+            ("folderAAAAAA", Folder, {
+                // F exists in two different non-syncable folders: C
+                // locally, and A remotely.
+                ("bookmarkFFFF", Bookmark),
+                ("bookmarkIIII", Bookmark)
+            })
+        }),
+        ("folderLEFTPR", Folder[needs_merge = true], {
+            // The complete left pane root. We should remove all left pane
+            // queries locally, even though they're syncable, since the left
+            // pane root is known to be non-syncable.
+            ("folderLEFTPQ", Query[needs_merge = true]),
+            ("folderLEFTPF", Folder[needs_merge = true], {
+                ("folderLEFTPC", Query[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, LocalWithNewLocalStructure, {
+        ("menu________", LocalWithNewLocalStructure, {
+            ("bookmarkBBBB", LocalWithNewLocalStructure)
+        }),
+        ("unfiled_____", LocalWithNewLocalStructure, {
+            ("bookmarkJJJJ", RemoteWithNewRemoteStructure),
+            ("bookmarkGGGG", Remote)
+        })
+    });
+    let expected_deletions = &[
+        "bookmarkEEEE", // Non-syncable locally.
+        "bookmarkFFFF", // Non-syncable locally.
+        "bookmarkIIII", // Non-syncable remotely.
+        "folderAAAAAA", // Non-syncable remotely.
+        "folderDDDDDD", // Non-syncable locally.
+        "folderLEFTPC", // Non-syncable remotely.
+        "folderLEFTPF", // Non-syncable remotely.
+        "folderLEFTPQ", // Non-syncable remotely.
+        "folderLEFTPR", // Non-syncable remotely.
+        "rootCCCCCCCC", // Non-syncable locally.
+        "rootHHHHHHHH", // Non-syncable remotely.
+    ];
+    let expected_telem = StructureCounts {
+        merged_nodes: 5,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn applying_two_empty_folders_doesnt_smush() {
+    before_each();
+
+    let local_tree = Tree::with_root(Item::new(ROOT_GUID, Kind::Folder))
+        .into_tree()
+        .unwrap();
+
+    let remote_tree = nodes!({
+        ("mobile______", Folder[needs_merge = true], {
+            ("emptyempty01", Folder[needs_merge = true]),
+            ("emptyempty02", Folder[needs_merge = true])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, UnchangedWithNewLocalStructure, {
+        ("mobile______", Remote, {
+            ("emptyempty01", Remote),
+            ("emptyempty02", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 3,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn applying_two_empty_folders_matches_only_one() {
+    before_each();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("mobile______", Folder[needs_merge = true], {
+            ("emptyempty02", Folder[needs_merge = true]),
+            ("emptyemptyL0", Folder[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    local_tree_builder
+        .mutate(&"emptyempty02".into())
+        .content(Content::Folder {
+            title: "Empty".into(),
+        });
+    local_tree_builder
+        .mutate(&"emptyemptyL0".into())
+        .content(Content::Folder {
+            title: "Empty".into(),
+        });
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("mobile______", Folder[needs_merge = true], {
+            ("emptyempty01", Folder[needs_merge = true]),
+            ("emptyempty02", Folder[needs_merge = true]),
+            ("emptyempty03", Folder[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder
+        .mutate(&"emptyempty01".into())
+        .content(Content::Folder {
+            title: "Empty".into(),
+        });
+    remote_tree_builder
+        .mutate(&"emptyempty02".into())
+        .content(Content::Folder {
+            title: "Empty".into(),
+        });
+    remote_tree_builder
+        .mutate(&"emptyempty03".into())
+        .content(Content::Folder {
+            title: "Empty".into(),
+        });
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("mobile______", LocalWithNewLocalStructure, {
+            ("emptyempty01", Remote),
+            ("emptyempty02", Remote),
+            ("emptyempty03", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        dupes: 1,
+        merged_nodes: 4,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+// Bug 747699: we should follow the hierarchy when merging, instead of
+// deduping by parent title.
+#[test]
+fn deduping_ignores_parent_title() {
+    before_each();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("mobile______", Folder[needs_merge = true], {
+            ("bookmarkAAA1", Bookmark[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    local_tree_builder
+        .mutate(&"mobile______".into())
+        .content(Content::Folder {
+            title: "Favoritos do celular".into(),
+        });
+    local_tree_builder
+        .mutate(&"bookmarkAAA1".into())
+        .content(Content::Bookmark {
+            title: "A".into(),
+            url_href: "http://example.com/a".into(),
+        });
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("mobile______", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder
+        .mutate(&"mobile______".into())
+        .content(Content::Folder {
+            title: "Mobile Bookmarks".into(),
+        });
+    remote_tree_builder
+        .mutate(&"bookmarkAAAA".into())
+        .content(Content::Bookmark {
+            title: "A".into(),
+            url_href: "http://example.com/a".into(),
+        });
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("mobile______", LocalWithNewLocalStructure, {
+            ("bookmarkAAAA", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        dupes: 1,
+        merged_nodes: 2,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn mismatched_compatible_bookmark_kinds() {
+    before_each();
+
+    let local_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("queryAAAAAAA", Query[needs_merge = true]),
+            ("bookmarkBBBB", Bookmark[needs_merge = true, age = 5])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("queryAAAAAAA", Bookmark[needs_merge = true, age = 5]),
+            ("bookmarkBBBB", Query[needs_merge = true])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", Local, {
+            ("queryAAAAAAA", Local),
+            ("bookmarkBBBB", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 3,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn mismatched_incompatible_bookmark_kinds() {
+    before_each();
+
+    let local_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Folder[needs_merge = true, age = 5])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    match merger.merge() {
+        Ok(_) => panic!("Should not merge trees with mismatched kinds"),
+        Err(err) => {
+            match err.kind() {
+                ErrorKind::MismatchedItemKind { .. } => {}
+                kind => panic!("Got {:?} merging trees with mismatched kinds", kind),
+            };
+        }
+    };
+}
+
+#[test]
+fn invalid_guids() {
+    before_each();
+
+    #[derive(Default)]
+    struct GenerateNewGuid(Cell<usize>);
+
+    impl Driver for GenerateNewGuid {
+        fn generate_new_guid(&self, old_guid: &Guid) -> Result<Guid> {
+            let count = self.0.get();
+            self.0.set(count + 1);
+            assert!(
+                &[")(*&", "shortGUID", "loooooongGUID", "!@#$%^", ""].contains(&old_guid.as_str()),
+                "Didn't expect to generate new GUID for {}",
+                old_guid
+            );
+            Ok(format!("item{:0>8}", count).into())
+        }
+    }
+
+    let local_tree = nodes!({
+        ("toolbar_____", Folder[needs_merge = true, age = 5], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true, age = 5]),
+            ("bookmarkBBBB", Bookmark[needs_merge = true, age = 5]),
+            (")(*&", Bookmark[needs_merge = true, age = 5])
+        }),
+        ("menu________", Folder[needs_merge = true], {
+            ("shortGUID", Bookmark[needs_merge = true]),
+            ("loooooongGUID", Bookmark[needs_merge = true])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("toolbar_____", Folder[needs_merge = true, age = 5], {
+            ("!@#$%^", Bookmark[needs_merge = true, age = 5]),
+            ("shortGUID", Bookmark[needs_merge = true, age = 5]),
+            ("", Bookmark[needs_merge = true, age = 5]),
+            ("loooooongGUID", Bookmark[needs_merge = true, age = 5])
+        }),
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true]),
+            ("bookmarkBBBB", Bookmark[needs_merge = true])
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let driver = GenerateNewGuid::default();
+    let merger = Merger::with_driver(&driver, &DefaultAbortSignal, &local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            ("item00000000", RemoteWithNewRemoteStructure),
+            ("item00000001", RemoteWithNewRemoteStructure),
+            ("item00000002", LocalWithNewLocalStructure)
+        }),
+        ("menu________", LocalWithNewLocalStructure, {
+            ("bookmarkAAAA", Remote),
+            ("bookmarkBBBB", Remote),
+            ("item00000003", LocalWithNewLocalStructure),
+            ("item00000004", LocalWithNewLocalStructure)
+        })
+    });
+    let expected_deletions = &["", "!@#$%^", "loooooongGUID", "shortGUID"];
+    let expected_telem = StructureCounts {
+        merged_nodes: 9,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn multiple_parents() {
+    before_each();
+
+    let local_tree = Tree::with_root(Item::new(ROOT_GUID, Kind::Folder))
+        .into_tree()
+        .unwrap();
+
+    let remote_tree = nodes!({
+        ("toolbar_____", Folder[age = 5], {
+            ("bookmarkAAAA", Bookmark),
+            ("bookmarkBBBB", Bookmark),
+            ("folderCCCCCC", Folder, {
+                ("bookmarkDDDD", Bookmark),
+                ("bookmarkEEEE", Bookmark),
+                ("bookmarkFFFF", Bookmark)
+            })
+        }),
+        ("menu________", Folder, {
+            ("bookmarkGGGG", Bookmark),
+            ("bookmarkAAAA", Bookmark),
+            ("folderCCCCCC", Folder, {
+                ("bookmarkHHHH", Bookmark),
+                ("bookmarkDDDD", Bookmark)
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, UnchangedWithNewLocalStructure, {
+        ("toolbar_____", RemoteWithNewRemoteStructure, {
+            ("bookmarkBBBB", Remote)
+        }),
+        ("menu________", RemoteWithNewRemoteStructure, {
+            ("bookmarkGGGG", Remote),
+            ("bookmarkAAAA", RemoteWithNewRemoteStructure),
+            ("folderCCCCCC", RemoteWithNewRemoteStructure, {
+                ("bookmarkDDDD", RemoteWithNewRemoteStructure),
+                ("bookmarkEEEE", Remote),
+                ("bookmarkFFFF", Remote),
+                ("bookmarkHHHH", Remote)
+            })
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 10,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn reparent_orphans() {
+    before_each();
+
+    let local_tree = nodes!({
+        ("toolbar_____", Folder, {
+            ("bookmarkAAAA", Bookmark),
+            ("bookmarkBBBB", Bookmark)
+        }),
+        ("unfiled_____", Folder, {
+            ("bookmarkCCCC", Bookmark)
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let mut remote_tree_builder: Builder = nodes!({
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("bookmarkBBBB", Bookmark),
+            ("bookmarkAAAA", Bookmark)
+        }),
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("bookmarkDDDD", Bookmark[needs_merge = true]),
+            ("bookmarkCCCC", Bookmark)
+        })
+    })
+    .try_into()
+    .unwrap();
+    remote_tree_builder
+        .item(Item {
+            guid: "bookmarkEEEE".into(),
+            kind: Kind::Bookmark,
+            age: 0,
+            needs_merge: true,
+            validity: Validity::Valid,
+        })
+        .and_then(|p| p.by_parent_guid("toolbar_____".into()))
+        .expect("Should insert orphan E");
+    remote_tree_builder
+        .item(Item {
+            guid: "bookmarkFFFF".into(),
+            kind: Kind::Bookmark,
+            age: 0,
+            needs_merge: true,
+            validity: Validity::Valid,
+        })
+        .and_then(|p| p.by_parent_guid("nonexistent".into()))
+        .expect("Should insert orphan F");
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            ("bookmarkBBBB", Unchanged),
+            ("bookmarkAAAA", Unchanged),
+            ("bookmarkEEEE", RemoteWithNewRemoteStructure)
+        }),
+        ("unfiled_____", LocalWithNewLocalStructure, {
+            ("bookmarkDDDD", Remote),
+            ("bookmarkCCCC", Unchanged),
+            ("bookmarkFFFF", RemoteWithNewRemoteStructure)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 8,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn deleted_user_content_roots() {
+    before_each();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    local_tree_builder
+        .deletion("mobile______".into())
+        .deletion("toolbar_____".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("mobile______", Folder[needs_merge = true], {
+            ("bookmarkBBBB", Bookmark[needs_merge = true])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder
+        .deletion("unfiled_____".into())
+        .deletion("toolbar_____".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, LocalWithNewLocalStructure, {
+        ("unfiled_____", Local, {
+            ("bookmarkAAAA", Local)
+        }),
+        ("mobile______", Remote, {
+            ("bookmarkBBBB", Remote)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 4,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 1);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn moved_user_content_roots() {
+    before_each();
+
+    let local_tree = nodes!({
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Bookmark[needs_merge = true]),
+            ("menu________", Folder[needs_merge = true], {
+                ("bookmarkBBBB", Bookmark[needs_merge = true]),
+                ("folderCCCCCC", Folder, {
+                    ("bookmarkDDDD", Bookmark),
+                    ("toolbar_____", Folder, {
+                        ("bookmarkEEEE", Bookmark)
+                    })
+                })
+            })
+        }),
+        ("mobile______", Folder, {
+            ("bookmarkFFFF", Bookmark)
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let remote_tree = nodes!({
+        ("mobile______", Folder[needs_merge = true], {
+            ("toolbar_____", Folder[needs_merge = true], {
+                ("bookmarkGGGG", Bookmark[needs_merge = true]),
+                ("bookmarkEEEE", Bookmark)
+            })
+        }),
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkHHHH", Bookmark[needs_merge = true]),
+            ("unfiled_____", Folder[needs_merge = true], {
+                ("bookmarkIIII", Bookmark[needs_merge = true])
+            })
+        })
+    })
+    .into_tree()
+    .unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!(ROOT_GUID, LocalWithNewLocalStructure, {
+        ("unfiled_____", LocalWithNewLocalStructure, {
+            ("bookmarkIIII", Remote),
+            ("bookmarkAAAA", Local)
+        }),
+        ("mobile______", Local, {
+            ("bookmarkFFFF", Local)
+        }),
+        ("menu________", LocalWithNewLocalStructure, {
+           ("bookmarkHHHH", Remote),
+           ("bookmarkBBBB", Local),
+           ("folderCCCCCC", LocalWithNewLocalStructure, {
+               ("bookmarkDDDD", Local)
+           })
+        }),
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            ("bookmarkGGGG", Remote),
+            ("bookmarkEEEE", Unchanged)
+        })
+    });
+    let expected_telem = StructureCounts {
+        merged_nodes: 13,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    assert_eq!(merged_root.deletions().count(), 0);
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn cycle() {
+    before_each();
+
+    // Try to create a cycle: move A into B, and B into the menu, but keep
+    // B's parent by children as A.
+    let mut b: Builder = nodes!({ ("menu________", Folder) }).try_into().unwrap();
+
+    b.item(Item::new("folderAAAAAA".into(), Kind::Folder))
+        .and_then(|p| p.by_parent_guid("folderBBBBBB".into()))
+        .expect("Should insert A");
+
+    b.item(Item::new("folderBBBBBB".into(), Kind::Folder))
+        .and_then(|p| p.by_parent_guid("menu________".into()))
+        .and_then(|b| {
+            b.parent_for(&"folderBBBBBB".into())
+                .by_children(&"folderAAAAAA".into())
+        })
+        .expect("Should insert B");
+
+    match b
+        .into_tree()
+        .expect_err("Should not build tree with cycles")
+        .kind()
+    {
+        ErrorKind::Cycle(guid) => assert_eq!(guid, &Guid::from("folderAAAAAA")),
+        err => panic!("Wrong error kind for cycle: {:?}", err),
+    }
+}
+
+#[test]
+fn reupload_replace() {
+    before_each();
+
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder, {
+            ("bookmarkAAAA", Bookmark)
+        }),
+        ("toolbar_____", Folder, {
+            ("folderBBBBBB", Folder, {
+                ("bookmarkCCCC", Bookmark[validity = Validity::Replace])
+            }),
+            ("folderDDDDDD", Folder, {
+                ("bookmarkEEEE", Bookmark[validity = Validity::Replace])
+            })
+        }),
+        ("unfiled_____", Folder),
+        ("mobile______", Folder, {
+            ("bookmarkFFFF", Bookmark[validity = Validity::Replace]),
+            ("folderGGGGGG", Folder),
+            ("bookmarkHHHH", Bookmark[validity = Validity::Replace])
+        })
+    }))
+    .unwrap();
+    local_tree_builder.deletion("bookmarkIIII".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder, {
+            ("bookmarkAAAA", Bookmark[validity = Validity::Replace])
+        }),
+        ("toolbar_____", Folder, {
+            ("bookmarkJJJJ", Bookmark[validity = Validity::Replace]),
+            ("folderBBBBBB", Folder, {
+                ("bookmarkCCCC", Bookmark[validity = Validity::Replace])
+            }),
+            ("folderDDDDDD", Folder)
+        }),
+        ("unfiled_____", Folder, {
+            ("bookmarkKKKK", Bookmark[validity = Validity::Reupload])
+        }),
+        ("mobile______", Folder, {
+            ("bookmarkFFFF", Bookmark),
+            ("folderGGGGGG", Folder, {
+                ("bookmarkIIII", Bookmark[validity = Validity::Replace])
+            })
+        })
+    }))
+    .unwrap();
+    remote_tree_builder.deletion("bookmarkEEEE".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", Unchanged, {
+            // A is invalid remotely and valid locally, so replace.
+            ("bookmarkAAAA", Local)
+        }),
+        // Toolbar has new children.
+        ("toolbar_____", LocalWithNewLocalStructure, {
+            // B has new children.
+            ("folderBBBBBB", LocalWithNewLocalStructure),
+            ("folderDDDDDD", UnchangedWithNewLocalStructure)
+        }),
+        ("unfiled_____", UnchangedWithNewLocalStructure, {
+            // K was flagged for reupload.
+           ("bookmarkKKKK", RemoteWithNewRemoteStructure)
+        }),
+        ("mobile______", UnchangedWithNewLocalStructure, {
+            // F is invalid locally, so replace with remote. This isn't
+            // possible in Firefox Desktop or Rust Places, where the local
+            // tree is always valid, but we handle it for symmetry.
+            ("bookmarkFFFF", Remote),
+            ("folderGGGGGG", Local)
+        })
+    });
+    let expected_deletions = &[
+        // C is invalid on both sides, so we need to upload a tombstone.
+        "bookmarkCCCC",
+        // E is invalid locally and deleted remotely, so doesn't need a
+        // tombstone.
+        "bookmarkEEEE",
+        // H is invalid locally and doesn't exist remotely, so doesn't need a
+        // tombstone.
+        "bookmarkHHHH",
+        // I is deleted locally and invalid remotely, so needs a tombstone.
+        "bookmarkIIII",
+        // J doesn't exist locally and invalid remotely, so needs a tombstone.
+        "bookmarkJJJJ",
+    ];
+    let expected_telem = StructureCounts {
+        merged_nodes: 10,
+        ..StructureCounts::default()
+    };
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let mut deletions = merged_root.deletions().collect::<Vec<_>>();
+    deletions.sort();
+    assert_eq!(deletions, expected_deletions);
+
+    let ops = merged_root.completion_ops();
+    let mut summary = ops.summarize();
+    summary.sort();
+    assert_eq!(
+        summary,
+        &[
+            "Apply remote bookmarkFFFF",
+            "Apply remote bookmarkKKKK",
+            "Delete local item bookmarkCCCC",
+            "Delete local item bookmarkEEEE",
+            "Delete local item bookmarkHHHH",
+            "Flag local bookmarkAAAA as unmerged",
+            "Flag local bookmarkKKKK as unmerged",
+            "Flag local folderBBBBBB as unmerged",
+            "Flag local folderGGGGGG as unmerged",
+            "Flag local toolbar_____ as unmerged",
+            "Flag remote bookmarkEEEE as merged",
+            "Insert local tombstone bookmarkCCCC",
+            "Insert local tombstone bookmarkJJJJ",
+            "Move bookmarkKKKK into unfiled_____ at 0",
+            "Upload item bookmarkAAAA",
+            "Upload item bookmarkKKKK",
+            "Upload item folderBBBBBB",
+            "Upload item folderGGGGGG",
+            "Upload item toolbar_____",
+            "Upload tombstone bookmarkCCCC",
+            "Upload tombstone bookmarkIIII",
+            "Upload tombstone bookmarkJJJJ",
+        ]
+    );
+
+    assert_eq!(merged_root.counts(), &expected_telem);
+}
+
+#[test]
+fn completion_ops() {
+    let mut local_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder, {
+            ("bookmarkAAAA", Bookmark),
+            ("bookmarkBBBB", Bookmark),
+            ("bookmarkCCCC", Bookmark),
+            ("bookmarkDDDD", Bookmark)
+        }),
+        ("toolbar_____", Folder, {
+            ("bookmarkEEEE", Bookmark)
+        }),
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("bookmarkIIII", Bookmark)
+        }),
+        ("mobile______", Folder, {
+            ("bookmarkFFFF", Bookmark[needs_merge = true, age = 10])
+        })
+    }))
+    .unwrap();
+    local_tree_builder.deletion("bookmarkJJJJ".into());
+    let local_tree = local_tree_builder.into_tree().unwrap();
+
+    let mut remote_tree_builder = Builder::try_from(nodes!({
+        ("menu________", Folder[needs_merge = true], {
+            ("bookmarkAAAA", Bookmark),
+            ("bookmarkDDDD", Bookmark),
+            ("bookmarkCCCC", Bookmark),
+            ("bookmarkBBBB", Bookmark),
+            ("bookmarkEEEE", Bookmark[needs_merge = true])
+        }),
+        ("toolbar_____", Folder[needs_merge = true], {
+            ("bookmarkGGGG", Bookmark[needs_merge = true])
+        }),
+        ("unfiled_____", Folder[needs_merge = true], {
+            ("bookmarkHHHH", Bookmark[needs_merge = true]),
+            ("bookmarkJJJJ", Bookmark)
+        }),
+        ("mobile______", Folder, {
+            ("bookmarkFFFF", Bookmark[needs_merge = true, age = 5])
+        })
+    }))
+    .unwrap();
+    remote_tree_builder.deletion("bookmarkIIII".into());
+    let remote_tree = remote_tree_builder.into_tree().unwrap();
+
+    let merger = Merger::new(&local_tree, &remote_tree);
+    let merged_root = merger.merge().unwrap();
+
+    let expected_tree = merged_nodes!({
+        ("menu________", UnchangedWithNewLocalStructure, {
+            ("bookmarkAAAA", Unchanged),
+            ("bookmarkDDDD", Unchanged),
+            ("bookmarkCCCC", Unchanged),
+            ("bookmarkBBBB", Unchanged),
+            ("bookmarkEEEE", Remote)
+        }),
+        ("toolbar_____", UnchangedWithNewLocalStructure, {
+            ("bookmarkGGGG", Remote)
+        }),
+        ("unfiled_____", LocalWithNewLocalStructure, {
+           ("bookmarkHHHH", Remote)
+        }),
+        ("mobile______", Unchanged, {
+            ("bookmarkFFFF", Remote)
+        })
+    });
+
+    assert_eq!(&expected_tree, merged_root.node());
+
+    let ops = merged_root.completion_ops();
+    assert!(ops.change_guids.is_empty());
+    assert_eq!(
+        to_strings(&ops.apply_remote_items).collect::<Vec<_>>(),
+        &[
+            "Apply remote bookmarkEEEE",
+            "Apply remote bookmarkGGGG",
+            "Apply remote bookmarkHHHH",
+            "Apply remote bookmarkFFFF",
+        ]
+    );
+    assert_eq!(
+        to_strings(&ops.apply_new_local_structure).collect::<Vec<_>>(),
+        &[
+            "Move bookmarkDDDD into menu________ at 1",
+            "Move bookmarkBBBB into menu________ at 3",
+            "Move bookmarkEEEE into menu________ at 4",
+            "Move bookmarkGGGG into toolbar_____ at 0",
+            "Move bookmarkHHHH into unfiled_____ at 0",
+        ]
+    );
+    assert!(ops.set_local_unmerged.is_empty());
+    assert_eq!(
+        to_strings(&ops.set_local_merged).collect::<Vec<_>>(),
+        &["Flag local bookmarkFFFF as merged"]
+    );
+    assert_eq!(
+        to_strings(&ops.set_remote_merged).collect::<Vec<_>>(),
+        &[
+            "Flag remote menu________ as merged",
+            "Flag remote bookmarkEEEE as merged",
+            "Flag remote toolbar_____ as merged",
+            "Flag remote bookmarkGGGG as merged",
+            "Flag remote bookmarkHHHH as merged",
+            "Flag remote bookmarkFFFF as merged",
+            "Flag remote bookmarkIIII as merged",
+        ]
+    );
+    let mut delete_local_items = to_strings(&ops.delete_local_items).collect::<Vec<_>>();
+    delete_local_items.sort();
+    assert_eq!(delete_local_items, &["Delete local item bookmarkIIII"]);
+    assert!(ops.insert_local_tombstones.is_empty());
+    assert_eq!(
+        to_strings(&ops.upload_items).collect::<Vec<_>>(),
+        &["Upload item unfiled_____"]
+    );
+    let mut upload_tombstones = to_strings(&ops.upload_tombstones).collect::<Vec<_>>();
+    upload_tombstones.sort();
+    assert_eq!(upload_tombstones, &["Upload tombstone bookmarkJJJJ"]);
+}
+
+#[test]
+fn problems() {
+    let mut problems = Problems::default();
+
+    problems
+        .note(&"bookmarkAAAA".into(), Problem::Orphan)
+        .note(
+            &"menu________".into(),
+            Problem::MisparentedRoot(vec![DivergedParent::ByChildren("unfiled_____".into())]),
+        )
+        .note(&"toolbar_____".into(), Problem::MisparentedRoot(Vec::new()))
+        .note(
+            &"bookmarkBBBB".into(),
+            Problem::DivergedParents(vec![
+                DivergedParent::ByChildren("folderCCCCCC".into()),
+                DivergedParentGuid::Folder("folderDDDDDD".into()).into(),
+            ]),
+        )
+        .note(
+            &"bookmarkEEEE".into(),
+            Problem::DivergedParents(vec![
+                DivergedParent::ByChildren("folderFFFFFF".into()),
+                DivergedParentGuid::NonFolder("bookmarkGGGG".into()).into(),
+            ]),
+        )
+        .note(&"bookmarkRRRR".into(), Problem::InvalidItem)
+        .note(
+            &"bookmarkHHHH".into(),
+            Problem::DivergedParents(vec![
+                DivergedParent::ByChildren("folderIIIIII".into()),
+                DivergedParent::ByChildren("folderJJJJJJ".into()),
+                DivergedParentGuid::Missing("folderKKKKKK".into()).into(),
+            ]),
+        )
+        .note(&"bookmarkLLLL".into(), Problem::DivergedParents(Vec::new()))
+        .note(
+            &"folderMMMMMM".into(),
+            Problem::MissingChild {
+                child_guid: "bookmarkNNNN".into(),
+            },
+        )
+        .note(
+            &"folderMMMMMM".into(),
+            Problem::MissingChild {
+                child_guid: "bookmarkOOOO".into(),
+            },
+        )
+        .note(
+            &"bookmarkPPPP".into(),
+            Problem::DivergedParents(vec![
+                DivergedParentGuid::Deleted("folderQQQQQQ".into()).into()
+            ]),
+        )
+        .note(&"bookmarkQQQQ".into(), Problem::InvalidItem);
+
+    let mut summary = problems.summarize().collect::<Vec<_>>();
+    summary.sort_by(|a, b| a.guid().cmp(b.guid()));
+    assert_eq!(
+        to_strings(&summary).collect::<Vec<_>>(),
+        &[
+            "bookmarkAAAA is an orphan",
+            "bookmarkBBBB is in children of folderCCCCCC and has parent folderDDDDDD",
+            "bookmarkEEEE is in children of folderFFFFFF and has non-folder parent bookmarkGGGG",
+            "bookmarkHHHH is in children of folderIIIIII, is in children of folderJJJJJJ, and has \
+             nonexistent parent folderKKKKKK",
+            "bookmarkLLLL has diverged parents",
+            "bookmarkPPPP has deleted parent folderQQQQQQ",
+            "bookmarkQQQQ is invalid",
+            "bookmarkRRRR is invalid",
+            "folderMMMMMM has nonexistent child bookmarkNNNN",
+            "folderMMMMMM has nonexistent child bookmarkOOOO",
+            "menu________ is a user content root, but is in children of unfiled_____",
+            "toolbar_____ is a user content root",
+        ]
+    );
+
+    assert_eq!(
+        problems.counts(),
+        ProblemCounts {
+            orphans: 1,
+            misparented_roots: 2,
+            multiple_parents_by_children: 3,
+            deleted_parent_guids: 1,
+            missing_parent_guids: 1,
+            non_folder_parent_guids: 1,
+            parent_child_disagreements: 7,
+            deleted_children: 0,
+            missing_children: 2,
+            invalid_items: 2,
+        }
+    );
+}
diff --git a/third_party/rust/dogear/src/tree.rs b/third_party/rust/dogear/src/tree.rs
new file mode 100644
index 0000000000..fe791f6c06
--- /dev/null
+++ b/third_party/rust/dogear/src/tree.rs
@@ -0,0 +1,2162 @@
+// 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::{
+    borrow::Cow,
+    cmp::Ordering,
+    collections::{HashMap, HashSet},
+    convert::{TryFrom, TryInto},
+    fmt, mem,
+    ops::Deref,
+    ptr,
+};
+
+use smallbitvec::SmallBitVec;
+
+use crate::error::{Error, ErrorKind, Result};
+use crate::guid::Guid;
+
+/// The type for entry indices in the tree.
+type Index = usize;
+
+/// A complete, rooted bookmark tree with tombstones.
+///
+/// The tree stores bookmark items in a vector, and uses indices in the vector
+/// to identify parents and children. This makes traversal and lookup very
+/// efficient. Retrieving a node's parent takes one indexing operation,
+/// retrieving children takes one indexing operation per child, and retrieving
+/// a node by random GUID takes one hash map lookup and one indexing operation.
+#[derive(Debug)]
+pub struct Tree {
+    entry_index_by_guid: HashMap<Guid, Index>,
+    entries: Vec<TreeEntry>,
+    deleted_guids: HashSet<Guid>,
+    problems: Problems,
+}
+
+impl Tree {
+    /// Returns a builder for a rooted tree.
+    pub fn with_root(root: Item) -> Builder {
+        let mut entry_index_by_guid = HashMap::new();
+        entry_index_by_guid.insert(root.guid.clone(), 0);
+
+        Builder {
+            entries: vec![BuilderEntry {
+                item: root,
+                content: None,
+                parent: BuilderEntryParent::Root,
+                children: Vec::new(),
+            }],
+            deleted_guids: HashSet::new(),
+            entry_index_by_guid,
+            reparent_orphans_to: None,
+        }
+    }
+
+    /// Returns the number of nodes in the tree.
+    #[inline]
+    pub fn size(&self) -> usize {
+        self.entries.len()
+    }
+
+    /// Returns the root node.
+    #[inline]
+    pub fn root(&self) -> Node<'_> {
+        Node(self, &self.entries[0])
+    }
+
+    /// Returns the set of all tombstoned GUIDs.
+    #[inline]
+    pub fn deletions(&self) -> &HashSet<Guid> {
+        &self.deleted_guids
+    }
+
+    /// Indicates if the GUID exists in the tree.
+    #[inline]
+    pub fn exists(&self, guid: &Guid) -> bool {
+        self.entry_index_by_guid.contains_key(guid)
+    }
+
+    /// Indicates if the GUID is known to be deleted. If `Tree::node_for_guid`
+    /// returns `None` and `Tree::is_deleted` returns `false`, the item doesn't
+    /// exist in the tree at all.
+    #[inline]
+    pub fn is_deleted(&self, guid: &Guid) -> bool {
+        self.deleted_guids.contains(guid)
+    }
+
+    /// Indicates if the GUID is mentioned in the tree, either as a node or
+    /// a deletion.
+    #[inline]
+    pub fn mentions(&self, guid: &Guid) -> bool {
+        self.entry_index_by_guid.contains_key(guid) || self.deleted_guids.contains(guid)
+    }
+
+    /// Returns an iterator for all node and tombstone GUIDs.
+    pub fn guids(&self) -> impl Iterator<Item = &Guid> {
+        self.entries
+            .iter()
+            .map(|entry| &entry.item.guid)
+            .chain(self.deleted_guids.iter())
+    }
+
+    /// Returns the node for a given `guid`, or `None` if a node with the `guid`
+    /// doesn't exist in the tree, or was deleted.
+    pub fn node_for_guid(&self, guid: &Guid) -> Option<Node<'_>> {
+        self.entry_index_by_guid
+            .get(guid)
+            .map(|&index| Node(self, &self.entries[index]))
+    }
+
+    /// Returns the structure divergences found when building the tree.
+    #[inline]
+    pub fn problems(&self) -> &Problems {
+        &self.problems
+    }
+}
+
+impl fmt::Display for Tree {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let root = self.root();
+        f.write_str(&root.to_ascii_string())?;
+        if !self.deleted_guids.is_empty() {
+            f.write_str("\nDeleted: [")?;
+            for (i, guid) in self.deleted_guids.iter().enumerate() {
+                if i != 0 {
+                    f.write_str(", ")?;
+                }
+                f.write_str(guid.as_ref())?;
+            }
+        }
+        if !self.problems.is_empty() {
+            f.write_str("\nProblems:\n")?;
+            for (i, summary) in self.problems.summarize().enumerate() {
+                if i != 0 {
+                    f.write_str("\n")?;
+                }
+                write!(f, "❗️ {}", summary)?;
+            }
+        }
+        Ok(())
+    }
+}
+
+/// A tree builder builds a bookmark tree structure from a flat list of items
+/// and parent-child associations.
+///
+/// # Tree structure
+///
+/// In a well-formed tree:
+///
+/// - Each item exists in exactly one folder. Two different folder's
+///   `children` should never reference the same item.
+/// - Each folder contains existing children. A folder's `children` should
+///   never reference tombstones, or items that don't exist in the tree at all.
+/// - Each item has a `parentid` that agrees with its parent's `children`. In
+///   other words, if item B's `parentid` is A, then A's `children` should
+///   contain B.
+///
+/// Because of Reasons, things are (a lot) messier in practice.
+///
+/// # Structure inconsistencies
+///
+/// Sync stores structure in two places: a `parentid` property on each item,
+/// which points to its parent's GUID, and a list of ordered `children` on the
+/// item's parent. They're duplicated because, historically, Sync clients didn't
+/// stage incoming records. Instead, they applied records one at a time,
+/// directly to the live local tree. This meant that, if a client saw a child
+/// before its parent, it would first use the `parentid` to decide where to keep
+/// the child, then fix up parents and positions using the parent's `children`.
+///
+/// This is also why moving an item into a different folder uploads records for
+/// the item, old folder, and new folder. The item has a new `parentid`, and the
+/// folders have new `children`. Similarly, deleting an item uploads a tombstone
+/// for the item, and a record for the item's old parent.
+///
+/// Unfortunately, bugs (bug 1258127) and missing features (bug 1253051) in
+/// older clients sometimes caused them to upload invalid or incomplete changes.
+/// For example, a client might have:
+///
+/// - Uploaded a moved child, but not its parents. This means the child now
+///   appears in multiple parents. In the most extreme case, an item might be
+///   referenced in two different sets of `children`, _and_ have a third,
+///   completely unrelated `parentid`.
+/// - Deleted a child, and tracked the deletion, but didn't flag the parent for
+///   reupload. The parent folder now has a tombstone child.
+/// - Tracked and uploaded items that shouldn't exist on the server at all,
+///   like the left pane or reading list roots (bug 1309255).
+/// - Missed new folders created during a sync, creating holes in the tree.
+///
+/// Newer clients shouldn't do this, but we might still have inconsistent
+/// records on the server that will confuse older clients. Additionally, Firefox
+/// for iOS includes a much stricter bookmarks engine that refuses to sync if
+/// it detects inconsistencies.
+///
+/// # Divergences
+///
+/// To work around this, the builder lets the structure _diverge_. This allows:
+///
+/// - Items with multiple parents.
+/// - Items with missing `parentid`s.
+/// - Folders with `children` whose `parentid`s don't match the folder.
+/// - Items whose `parentid`s don't mention the item in their `children`.
+/// - Items with `parentid`s that point to nonexistent or deleted folders.
+/// - Folders with nonexistent `children`.
+/// - Non-syncable items, like custom roots.
+/// - Any combination of these.
+///
+/// # Resolving divergences
+///
+/// Building a tree using `std::convert::TryInto<Tree>::try_into` resolves
+/// divergences using these rules:
+///
+/// 1. User content roots should always be children of the Places root. If
+///    they appear in other parents, we move them.
+/// 2. Items that appear in multiple `children`, and items with mismatched
+///    `parentid`s, use the chronologically newer parent, based on the parent's
+///    last modified time. We always prefer parents by `children` over
+///    `parentid,` because `children` also gives us the item's position.
+/// 3. Items that aren't mentioned in any parent's `children`, but have a
+///    `parentid` that references an existing folder in the tree, are reparented
+///    to the end of that folder, after the folder's `children`.
+/// 4. Items that reference a nonexistent or non-folder `parentid`, or don't
+///    have a `parentid` at all, are reparented to the default folder.
+/// 5. If the default folder isn't set, or doesn't exist, items from rule 4 are
+///    reparented to the root instead.
+///
+/// The result is a well-formed tree structure that can be merged. The merger
+/// detects if the structure diverged, and flags affected items for reupload.
+#[derive(Debug)]
+pub struct Builder {
+    entry_index_by_guid: HashMap<Guid, Index>,
+    entries: Vec<BuilderEntry>,
+    deleted_guids: HashSet<Guid>,
+    reparent_orphans_to: Option<Guid>,
+}
+
+impl Builder {
+    /// Sets the default folder for reparented orphans. If not set, doesn't
+    /// exist, or not a folder, orphans will be reparented to the root.
+    #[inline]
+    pub fn reparent_orphans_to(&mut self, guid: &Guid) -> &mut Builder {
+        self.reparent_orphans_to = Some(guid.clone());
+        self
+    }
+
+    /// Inserts an `item` into the tree. Returns an error if the item already
+    /// exists.
+    pub fn item(&mut self, item: Item) -> Result<ItemBuilder<'_>> {
+        assert_eq!(self.entries.len(), self.entry_index_by_guid.len());
+        if self.entry_index_by_guid.contains_key(&item.guid) {
+            return Err(ErrorKind::DuplicateItem(item.guid.clone()).into());
+        }
+        let entry_index = self.entries.len();
+        self.entry_index_by_guid
+            .insert(item.guid.clone(), entry_index);
+        self.entries.push(BuilderEntry {
+            item,
+            content: None,
+            parent: BuilderEntryParent::None,
+            children: Vec::new(),
+        });
+        Ok(ItemBuilder(self, entry_index))
+    }
+
+    /// Sets parents for a `child_guid`. Depending on where the parent comes
+    /// from, `child_guid` may not need to exist in the tree.
+    pub fn parent_for(&mut self, child_guid: &Guid) -> ParentBuilder<'_> {
+        assert_eq!(self.entries.len(), self.entry_index_by_guid.len());
+        let entry_child = match self.entry_index_by_guid.get(child_guid) {
+            Some(&child_index) => BuilderEntryChild::Exists(child_index),
+            None => BuilderEntryChild::Missing(child_guid.clone()),
+        };
+        ParentBuilder(self, entry_child)
+    }
+
+    /// Notes a tombstone for a deleted item, marking it as deleted in the
+    /// tree.
+    #[inline]
+    pub fn deletion(&mut self, guid: Guid) -> &mut Builder {
+        self.deleted_guids.insert(guid);
+        self
+    }
+
+    /// Equivalent to using our implementation of`TryInto<Tree>::try_into`, but
+    /// provided both for convenience when updating from previous versions of
+    /// `dogear`, and for cases where a type hint would otherwise be needed to
+    /// clarify the target type of the conversion.
+    pub fn into_tree(self) -> Result<Tree> {
+        self.try_into()
+    }
+
+    /// Mutates content and structure for an existing item. This is only
+    /// exposed to tests.
+    #[cfg(test)]
+    pub fn mutate(&mut self, child_guid: &Guid) -> ItemBuilder<'_> {
+        assert_eq!(self.entries.len(), self.entry_index_by_guid.len());
+        match self.entry_index_by_guid.get(child_guid) {
+            Some(&child_index) => ItemBuilder(self, child_index),
+            None => panic!("Can't mutate nonexistent item {}", child_guid),
+        }
+    }
+}
+
+impl TryFrom<Builder> for Tree {
+    type Error = Error;
+    /// Builds a tree from all stored items and parent-child associations,
+    /// resolving inconsistencies like orphans, multiple parents, and
+    /// parent-child disagreements.
+    fn try_from(mut builder: Builder) -> Result<Tree> {
+        let mut problems = Problems::default();
+
+        // The indices in this bit vector point to zombie entries, which exist
+        // in the tree, but are also flagged as deleted. We'll remove these
+        // zombies from the set of deleted GUIDs, and mark them as diverged for
+        // reupload.
+        let mut zombies = SmallBitVec::from_elem(builder.entries.len(), false);
+
+        // First, resolve parents for all entries, and build a lookup table for
+        // items without a position.
+        let mut parents = Vec::with_capacity(builder.entries.len());
+        let mut reparented_child_indices_by_parent: HashMap<Index, Vec<Index>> = HashMap::new();
+        for (entry_index, entry) in builder.entries.iter().enumerate() {
+            if entry.item.validity == Validity::Replace {
+                problems.note(&entry.item.guid, Problem::InvalidItem);
+            }
+            let r = ResolveParent::new(&builder, entry, &mut problems);
+            let resolved_parent = r.resolve();
+            if let ResolvedParent::ByParentGuid(parent_index) = resolved_parent {
+                // Reparented items are special: since they aren't mentioned in
+                // that parent's `children`, we don't know their positions. Note
+                // them for when we resolve children. We also clone the GUID,
+                // since we use it for sorting, but can't access it by
+                // reference once we call `builder.entries.into_iter()` below.
+                let reparented_child_indices = reparented_child_indices_by_parent
+                    .entry(parent_index)
+                    .or_default();
+                reparented_child_indices.push(entry_index);
+            }
+            if builder.deleted_guids.remove(&entry.item.guid) {
+                zombies.set(entry_index, true);
+            }
+            parents.push(resolved_parent);
+        }
+
+        // If any parents form cycles, abort. We haven't seen cyclic trees in
+        // the wild, and breaking cycles would add complexity.
+        if let Some(index) = detect_cycles(&parents) {
+            return Err(ErrorKind::Cycle(builder.entries[index].item.guid.clone()).into());
+        }
+
+        // Then, resolve children, and build a slab of entries for the tree.
+        let mut entries = Vec::with_capacity(builder.entries.len());
+        for (entry_index, entry) in builder.entries.into_iter().enumerate() {
+            // Each entry is consistent, until proven otherwise!
+            let mut divergence = Divergence::Consistent;
+
+            let parent_index = match &parents[entry_index] {
+                ResolvedParent::Root => {
+                    // The Places root doesn't have a parent, and should always
+                    // be the first entry.
+                    assert_eq!(entry_index, 0);
+                    None
+                }
+                ResolvedParent::ByStructure(index) => {
+                    // The entry has a valid parent by structure, yay!
+                    Some(*index)
+                }
+                ResolvedParent::ByChildren(index) | ResolvedParent::ByParentGuid(index) => {
+                    // The entry has multiple parents, and we resolved one,
+                    // so it's diverged.
+                    divergence = Divergence::Diverged;
+                    Some(*index)
+                }
+            };
+
+            // If the entry is a zombie, mark it as diverged, so that the merger
+            // can remove the tombstone and reupload the item.
+            if zombies[entry_index] {
+                divergence = Divergence::Diverged;
+            }
+
+            // Check if the entry's children exist and agree that this entry is
+            // their parent.
+            let mut child_indices = Vec::with_capacity(entry.children.len());
+            for child in entry.children {
+                match child {
+                    BuilderEntryChild::Exists(child_index) => {
+                        if zombies[entry_index] {
+                            // If the entry has a zombie child, mark it as
+                            // diverged.
+                            divergence = Divergence::Diverged;
+                        }
+                        match &parents[child_index] {
+                            ResolvedParent::Root => {
+                                // The Places root can't be a child of another entry.
+                                unreachable!("A child can't be a top-level root");
+                            }
+                            ResolvedParent::ByStructure(parent_index) => {
+                                // If the child has a valid parent by structure, it
+                                // must be the entry. If it's not, there's a bug
+                                // in `ResolveParent` or `BuilderEntry`.
+                                assert_eq!(*parent_index, entry_index);
+                                child_indices.push(child_index);
+                            }
+                            ResolvedParent::ByChildren(parent_index) => {
+                                // If the child has multiple parents, we may have
+                                // resolved a different one, so check if we decided
+                                // to keep the child in this entry.
+                                divergence = Divergence::Diverged;
+                                if *parent_index == entry_index {
+                                    child_indices.push(child_index);
+                                }
+                            }
+                            ResolvedParent::ByParentGuid(parent_index) => {
+                                // We should only ever prefer parents
+                                // `by_parent_guid` over parents `by_children` for
+                                // misparented user content roots. Otherwise,
+                                // there's a bug in `ResolveParent`.
+                                assert_eq!(*parent_index, 0);
+                                divergence = Divergence::Diverged;
+                            }
+                        }
+                    }
+                    BuilderEntryChild::Missing(child_guid) => {
+                        // If the entry's `children` mention a deleted or
+                        // nonexistent GUID, note it as a problem, and ignore
+                        // the child.
+                        divergence = Divergence::Diverged;
+                        let problem = if builder.deleted_guids.remove(&child_guid) {
+                            Problem::DeletedChild {
+                                child_guid: child_guid.clone(),
+                            }
+                        } else {
+                            Problem::MissingChild {
+                                child_guid: child_guid.clone(),
+                            }
+                        };
+                        problems.note(&entry.item.guid, problem);
+                    }
+                }
+            }
+
+            // Reparented items don't appear in our `children`, so we move them
+            // to the end, after existing children (rules 3-4).
+            if let Some(reparented_child_indices) =
+                reparented_child_indices_by_parent.get(&entry_index)
+            {
+                divergence = Divergence::Diverged;
+                child_indices.extend_from_slice(reparented_child_indices);
+            }
+
+            entries.push(TreeEntry {
+                item: entry.item,
+                content: entry.content,
+                parent_index,
+                child_indices,
+                divergence,
+            });
+        }
+
+        // Now we have a consistent tree.
+        Ok(Tree {
+            entry_index_by_guid: builder.entry_index_by_guid,
+            entries,
+            deleted_guids: builder.deleted_guids,
+            problems,
+        })
+    }
+}
+
+/// Adds an item with content and structure to a tree builder.
+pub struct ItemBuilder<'b>(&'b mut Builder, Index);
+
+impl<'b> ItemBuilder<'b> {
+    /// Sets content info for an item that hasn't been uploaded or merged yet.
+    /// We'll try to dedupe local items with content info to remotely changed
+    /// items with similar contents and different GUIDs.
+    #[inline]
+    pub fn content<'c>(&'c mut self, content: Content) -> &'c mut ItemBuilder<'b> {
+        self.0.entries[self.1].content = Some(content);
+        self
+    }
+
+    /// Records a `parent_guid` from the item's parent's `children`. See
+    /// `ParentBuilder::by_children`.
+    #[inline]
+    pub fn by_children(self, parent_guid: &Guid) -> Result<&'b mut Builder> {
+        let b = ParentBuilder(self.0, BuilderEntryChild::Exists(self.1));
+        b.by_children(parent_guid)
+    }
+
+    /// Records a `parent_guid` from the item's `parentid`. See
+    /// `ParentBuilder::by_parent_guid`.
+    #[inline]
+    pub fn by_parent_guid(self, parent_guid: Guid) -> Result<&'b mut Builder> {
+        let b = ParentBuilder(self.0, BuilderEntryChild::Exists(self.1));
+        b.by_parent_guid(parent_guid)
+    }
+
+    #[inline]
+    pub fn by_structure(self, parent_guid: &Guid) -> Result<&'b mut Builder> {
+        let b = ParentBuilder(self.0, BuilderEntryChild::Exists(self.1));
+        b.by_structure(parent_guid)
+    }
+}
+
+/// Adds structure for an existing item to a tree builder.
+pub struct ParentBuilder<'b>(&'b mut Builder, BuilderEntryChild);
+
+impl<'b> ParentBuilder<'b> {
+    /// Records a `parent_guid` from the item's parent's `children`. The
+    /// `parent_guid` must refer to an existing folder in the tree, but
+    /// the item itself doesn't need to exist. This handles folders with
+    /// missing children.
+    pub fn by_children(self, parent_guid: &Guid) -> Result<&'b mut Builder> {
+        let parent_index = match self.0.entry_index_by_guid.get(parent_guid) {
+            Some(&parent_index) if self.0.entries[parent_index].item.is_folder() => parent_index,
+            Some(&parent_index) => {
+                let parent = &self.0.entries[parent_index].item;
+
+                let child = match &self.1 {
+                    BuilderEntryChild::Exists(index) => &self.0.entries[*index].item,
+                    BuilderEntryChild::Missing(child_guid) => {
+                        return Err(ErrorKind::InvalidParentForUnknownChild(
+                            child_guid.clone(),
+                            parent.clone(),
+                        )
+                        .into())
+                    }
+                };
+
+                return Err(ErrorKind::InvalidParent(child.clone(), parent.clone()).into());
+            }
+            _ => {
+                let child = match &self.1 {
+                    BuilderEntryChild::Exists(index) => &self.0.entries[*index].item,
+                    BuilderEntryChild::Missing(child_guid) => {
+                        return Err(ErrorKind::MissingParentForUnknownChild(
+                            child_guid.clone(),
+                            parent_guid.clone(),
+                        )
+                        .into())
+                    }
+                };
+
+                return Err(ErrorKind::MissingParent(child.clone(), parent_guid.clone()).into());
+            }
+        };
+        if let BuilderEntryChild::Exists(child_index) = &self.1 {
+            self.0.entries[*child_index].parents_by(&[BuilderParentBy::Children(parent_index)])?;
+        }
+        self.0.entries[parent_index].children.push(self.1);
+        Ok(self.0)
+    }
+
+    /// Records a `parent_guid` from the item's `parentid`. The item must
+    /// exist in the tree, but the `parent_guid` doesn't need to exist,
+    /// or even refer to a folder. The builder will reparent items with
+    /// missing and non-folder `parentid`s to the default folder when it
+    /// builds the tree.
+    pub fn by_parent_guid(self, parent_guid: Guid) -> Result<&'b mut Builder> {
+        match &self.1 {
+            BuilderEntryChild::Exists(child_index) => {
+                self.0.entries[*child_index]
+                    .parents_by(&[BuilderParentBy::UnknownItem(parent_guid)])?;
+            }
+            BuilderEntryChild::Missing(child_guid) => {
+                return Err(ErrorKind::MissingItem(child_guid.clone()).into());
+            }
+        }
+        Ok(self.0)
+    }
+
+    /// Records a `parent_guid` from a valid tree structure. This is for
+    /// callers who already know their structure is consistent, like
+    /// `Store::fetch_local_tree()` on Desktop, and
+    /// `std::convert::TryInto<Tree>` in the tests.
+    ///
+    /// Both the item and `parent_guid` must exist, and the `parent_guid` must
+    /// refer to a folder.
+    ///
+    /// `by_structure(parent_guid)` is logically the same as:
+    ///
+    /// ```no_run
+    /// # use dogear::{Item, Kind, Result, ROOT_GUID, Tree};
+    /// # fn main() -> Result<()> {
+    /// # let mut builder = Tree::with_root(Item::new(ROOT_GUID, Kind::Folder));
+    /// # let child_guid = "bookmarkAAAA".into();
+    /// # let parent_guid = "folderAAAAAA".into();
+    /// builder.parent_for(&child_guid)
+    ///     .by_children(&parent_guid)?
+    /// .parent_for(&child_guid)
+    ///     .by_parent_guid(parent_guid)?;
+    /// # Ok(())
+    /// # }
+    /// ```
+    ///
+    /// ...But more convenient. It's also more efficient, because it avoids
+    /// multiple lookups for the item and parent, as well as an extra heap
+    /// allocation to store the parents.
+    pub fn by_structure(self, parent_guid: &Guid) -> Result<&'b mut Builder> {
+        let parent_index = match self.0.entry_index_by_guid.get(parent_guid) {
+            Some(&parent_index) if self.0.entries[parent_index].item.is_folder() => parent_index,
+            Some(&parent_index) => {
+                let parent = &self.0.entries[parent_index].item;
+
+                let child = match &self.1 {
+                    BuilderEntryChild::Exists(index) => &self.0.entries[*index].item,
+                    BuilderEntryChild::Missing(child_guid) => {
+                        return Err(ErrorKind::InvalidParentForUnknownChild(
+                            child_guid.clone(),
+                            parent.clone(),
+                        )
+                        .into())
+                    }
+                };
+
+                return Err(ErrorKind::InvalidParent(child.clone(), parent.clone()).into());
+            }
+            _ => {
+                let child = match &self.1 {
+                    BuilderEntryChild::Exists(index) => &self.0.entries[*index].item,
+                    BuilderEntryChild::Missing(child_guid) => {
+                        return Err(ErrorKind::MissingParentForUnknownChild(
+                            child_guid.clone(),
+                            parent_guid.clone(),
+                        )
+                        .into())
+                    }
+                };
+
+                return Err(ErrorKind::MissingParent(child.clone(), parent_guid.clone()).into());
+            }
+        };
+        if let BuilderEntryChild::Exists(child_index) = &self.1 {
+            self.0.entries[*child_index].parents_by(&[
+                BuilderParentBy::Children(parent_index),
+                BuilderParentBy::KnownItem(parent_index),
+            ])?;
+        }
+        self.0.entries[parent_index].children.push(self.1);
+        Ok(self.0)
+    }
+}
+
+/// An entry wraps a tree item with references to its parents and children,
+/// which index into the tree's `entries` vector. This indirection exists
+/// because Rust is more strict about ownership of parents and children.
+///
+/// For example, we can't have entries own their children without sacrificing
+/// fast random lookup: we'd need to store references to the entries in the
+/// lookup map, but a struct can't hold references into itself.
+///
+/// Similarly, we can't have entries hold `Weak` pointers to `Rc` entries for
+/// the parent and children, because we need to update the parent when we insert
+/// a new node, but `Rc` won't hand us a mutable reference to the entry as long
+/// as it has outstanding `Weak` pointers.
+///
+/// We *could* use GUIDs instead of indices, and store the entries in a
+/// `HashMap<String, Entry>`, but that's inefficient: we'd need to store N
+/// copies of the GUID for parent and child lookups, and retrieving children
+/// would take one hash map lookup *per child*.
+///
+/// Note that we always compare references to entries, instead of deriving
+/// `PartialEq`, because two entries with the same fields but in different
+/// trees should never compare equal.
+#[derive(Debug)]
+struct TreeEntry {
+    item: Item,
+    content: Option<Content>,
+    divergence: Divergence,
+    parent_index: Option<Index>,
+    child_indices: Vec<Index>,
+}
+
+/// A builder entry holds an item and its structure. It's the builder's analog
+/// of a `TreeEntry`.
+#[derive(Debug)]
+struct BuilderEntry {
+    item: Item,
+    content: Option<Content>,
+    parent: BuilderEntryParent,
+    children: Vec<BuilderEntryChild>,
+}
+
+impl BuilderEntry {
+    /// Adds `new_parents` for the entry.
+    fn parents_by(&mut self, new_parents: &[BuilderParentBy]) -> Result<()> {
+        let old_parent = mem::replace(&mut self.parent, BuilderEntryParent::None);
+        let new_parent = match old_parent {
+            BuilderEntryParent::Root => {
+                self.parent = BuilderEntryParent::Root;
+                return Err(ErrorKind::DuplicateItem(self.item.guid.clone()).into());
+            }
+            BuilderEntryParent::None => match new_parents {
+                [BuilderParentBy::Children(from_children), BuilderParentBy::KnownItem(from_item)]
+                | [BuilderParentBy::KnownItem(from_item), BuilderParentBy::Children(from_children)]
+                    if from_children == from_item =>
+                {
+                    // If the parent's `children` and item's `parentid` match,
+                    // we have a complete structure, so we can avoid an extra
+                    // allocation for the partial structure.
+                    BuilderEntryParent::Complete(*from_children)
+                }
+                new_parents => BuilderEntryParent::Partial(new_parents.to_vec()),
+            },
+            BuilderEntryParent::Complete(index) => {
+                let mut parents = vec![
+                    BuilderParentBy::Children(index),
+                    BuilderParentBy::KnownItem(index),
+                ];
+                parents.extend_from_slice(new_parents);
+                BuilderEntryParent::Partial(parents)
+            }
+            BuilderEntryParent::Partial(mut parents) => {
+                parents.extend_from_slice(new_parents);
+                BuilderEntryParent::Partial(parents)
+            }
+        };
+        self.parent = new_parent;
+        Ok(())
+    }
+}
+
+/// Holds an existing child index, or missing child GUID, for a builder entry.
+#[derive(Debug)]
+enum BuilderEntryChild {
+    Exists(Index),
+    Missing(Guid),
+}
+
+/// Holds one or more parents for a builder entry.
+#[derive(Clone, Debug)]
+enum BuilderEntryParent {
+    /// The entry is an orphan.
+    None,
+
+    /// The entry is a top-level root, from which all other entries descend.
+    /// A tree can only have one root.
+    Root,
+
+    /// The entry has two matching parents from its structure. This is the fast
+    /// path for local trees, which are always valid.
+    Complete(Index),
+
+    /// The entry has an incomplete or divergent structure. This is the path for
+    /// all remote trees, valid and invalid, since we add structure from
+    /// `parentid`s and `children` separately. This is also the path for
+    /// mismatched and multiple parents.
+    Partial(Vec<BuilderParentBy>),
+}
+
+/// Describes where a builder entry's parent comes from.
+#[derive(Clone, Debug)]
+enum BuilderParentBy {
+    /// The entry's parent references the entry in its `children`.
+    Children(Index),
+
+    /// The entry's parent comes from its `parentid`, and will be resolved
+    /// when we build the tree.
+    UnknownItem(Guid),
+
+    /// The entry's parent comes from its `parentid` and has been
+    /// resolved.
+    KnownItem(Index),
+}
+
+/// Resolves the parent for a builder entry.
+struct ResolveParent<'a> {
+    builder: &'a Builder,
+    entry: &'a BuilderEntry,
+    problems: &'a mut Problems,
+}
+
+impl<'a> ResolveParent<'a> {
+    fn new(
+        builder: &'a Builder,
+        entry: &'a BuilderEntry,
+        problems: &'a mut Problems,
+    ) -> ResolveParent<'a> {
+        ResolveParent {
+            builder,
+            entry,
+            problems,
+        }
+    }
+
+    fn resolve(self) -> ResolvedParent {
+        if self.entry.item.guid.is_built_in_root() {
+            self.user_content_root()
+        } else {
+            self.item()
+        }
+    }
+
+    /// Returns the parent for this builder entry. This unifies parents
+    /// `by_structure`, which are known to be consistent, and parents
+    /// `by_children` and `by_parent_guid`, which are consistent if they match.
+    fn parent(&self) -> Cow<'a, BuilderEntryParent> {
+        let parents = match &self.entry.parent {
+            // Roots and orphans pass through as-is.
+            BuilderEntryParent::Root => return Cow::Owned(BuilderEntryParent::Root),
+            BuilderEntryParent::None => return Cow::Owned(BuilderEntryParent::None),
+            BuilderEntryParent::Complete(index) => {
+                // The entry is known to have a valid parent by structure. This
+                // is the fast path, used for local trees in Desktop.
+                return Cow::Owned(BuilderEntryParent::Complete(*index));
+            }
+            BuilderEntryParent::Partial(parents) => parents,
+        };
+        // The entry has zero, one, or many parents, recorded separately. Check
+        // if it has exactly two: one `by_parent_guid`, and one `by_children`.
+        let (index_by_guid, index_by_children) = match parents.as_slice() {
+            [BuilderParentBy::UnknownItem(guid), BuilderParentBy::Children(index_by_children)]
+            | [BuilderParentBy::Children(index_by_children), BuilderParentBy::UnknownItem(guid)] => {
+                match self.builder.entry_index_by_guid.get(guid) {
+                    Some(&index_by_guid) => (index_by_guid, *index_by_children),
+                    None => return Cow::Borrowed(&self.entry.parent),
+                }
+            }
+            [BuilderParentBy::KnownItem(index_by_guid), BuilderParentBy::Children(index_by_children)]
+            | [BuilderParentBy::Children(index_by_children), BuilderParentBy::KnownItem(index_by_guid)] => {
+                (*index_by_guid, *index_by_children)
+            }
+            // In all other cases (missing `parentid`, missing from `children`,
+            // multiple parents), return all possible parents. We'll pick one
+            // when we resolve the parent.
+            _ => return Cow::Borrowed(&self.entry.parent),
+        };
+        // If the entry has matching parents `by_children` and `by_parent_guid`,
+        // it has a valid parent by structure. This is the "fast slow path",
+        // used for remote trees in Desktop, because their structure is built in
+        // two passes. In all other cases, we have a parent-child disagreement,
+        // so return all possible parents.
+        if index_by_guid == index_by_children {
+            Cow::Owned(BuilderEntryParent::Complete(index_by_children))
+        } else {
+            Cow::Borrowed(&self.entry.parent)
+        }
+    }
+
+    /// Resolves the parent for a user content root: menu, mobile, toolbar, and
+    /// unfiled. These are simpler to resolve than non-roots because they must
+    /// be children of the Places root (rule 1), which is always the first
+    /// entry.
+    fn user_content_root(self) -> ResolvedParent {
+        match self.parent().as_ref() {
+            BuilderEntryParent::None => {
+                // Orphaned content root. This should only happen if the content
+                // root doesn't have a parent `by_parent_guid`.
+                self.problems.note(&self.entry.item.guid, Problem::Orphan);
+                ResolvedParent::ByParentGuid(0)
+            }
+            BuilderEntryParent::Root => {
+                unreachable!("A user content root can't be a top-level root")
+            }
+            BuilderEntryParent::Complete(index) => {
+                if *index == 0 {
+                    ResolvedParent::ByStructure(*index)
+                } else {
+                    // Move misparented content roots to the Places root.
+                    let parent_guid = self.builder.entries[*index].item.guid.clone();
+                    self.problems.note(
+                        &self.entry.item.guid,
+                        Problem::MisparentedRoot(vec![
+                            DivergedParent::ByChildren(parent_guid.clone()),
+                            DivergedParentGuid::Folder(parent_guid).into(),
+                        ]),
+                    );
+                    ResolvedParent::ByParentGuid(0)
+                }
+            }
+            BuilderEntryParent::Partial(parents_by) => {
+                // Ditto for content roots with multiple parents or parent-child
+                // disagreements.
+                self.problems.note(
+                    &self.entry.item.guid,
+                    Problem::MisparentedRoot(
+                        parents_by
+                            .iter()
+                            .map(|parent_by| {
+                                PossibleParent::new(self.builder, parent_by).summarize()
+                            })
+                            .collect(),
+                    ),
+                );
+                ResolvedParent::ByParentGuid(0)
+            }
+        }
+    }
+
+    /// Resolves the parent for a top-level Places root or other item, using
+    /// rules 2-5.
+    fn item(self) -> ResolvedParent {
+        match self.parent().as_ref() {
+            BuilderEntryParent::Root => ResolvedParent::Root,
+            BuilderEntryParent::None => {
+                // The item doesn't have a `parentid`, and isn't mentioned in
+                // any `children`. Reparent to the default folder (rule 4) or
+                // Places root (rule 5).
+                let parent_index = self.reparent_orphans_to_default_index();
+                self.problems.note(&self.entry.item.guid, Problem::Orphan);
+                ResolvedParent::ByParentGuid(parent_index)
+            }
+            BuilderEntryParent::Complete(index) => {
+                // The item's `parentid` and parent's `children` match, so keep
+                // it in its current parent.
+                ResolvedParent::ByStructure(*index)
+            }
+            BuilderEntryParent::Partial(parents) => {
+                // For items with one or more than two parents, pick the
+                // youngest (minimum age).
+                let possible_parents = parents
+                    .iter()
+                    .map(|parent_by| PossibleParent::new(self.builder, parent_by))
+                    .collect::<Vec<_>>();
+                self.problems.note(
+                    &self.entry.item.guid,
+                    Problem::DivergedParents(
+                        possible_parents
+                            .iter()
+                            .map(PossibleParent::summarize)
+                            .collect(),
+                    ),
+                );
+                possible_parents
+                    .into_iter()
+                    .min()
+                    .and_then(|p| match p.parent_by {
+                        BuilderParentBy::Children(index) => {
+                            Some(ResolvedParent::ByChildren(*index))
+                        }
+                        BuilderParentBy::KnownItem(index) => {
+                            Some(ResolvedParent::ByParentGuid(*index))
+                        }
+                        BuilderParentBy::UnknownItem(guid) => self
+                            .builder
+                            .entry_index_by_guid
+                            .get(guid)
+                            .filter(|&&index| self.builder.entries[index].item.is_folder())
+                            .map(|&index| ResolvedParent::ByParentGuid(index)),
+                    })
+                    .unwrap_or_else(|| {
+                        // Fall back to the default folder (rule 4) or root
+                        // (rule 5) if we didn't find a parent.
+                        let parent_index = self.reparent_orphans_to_default_index();
+                        ResolvedParent::ByParentGuid(parent_index)
+                    })
+            }
+        }
+    }
+
+    /// Returns the index of the default parent entry for reparented orphans.
+    /// This is either the default folder (rule 4), or the root, if the
+    /// default folder isn't set, doesn't exist, or isn't a folder (rule 5).
+    fn reparent_orphans_to_default_index(&self) -> Index {
+        self.builder
+            .reparent_orphans_to
+            .as_ref()
+            .and_then(|guid| self.builder.entry_index_by_guid.get(guid))
+            .cloned()
+            .filter(|&parent_index| {
+                let parent_entry = &self.builder.entries[parent_index];
+                parent_entry.item.is_folder()
+            })
+            .unwrap_or(0)
+    }
+}
+
+// A possible parent for an item with conflicting parents. We use this wrapper's
+// `Ord` implementation to decide which parent is youngest.
+#[derive(Clone, Copy, Debug)]
+struct PossibleParent<'a> {
+    builder: &'a Builder,
+    parent_by: &'a BuilderParentBy,
+}
+
+impl<'a> PossibleParent<'a> {
+    fn new(builder: &'a Builder, parent_by: &'a BuilderParentBy) -> PossibleParent<'a> {
+        PossibleParent { builder, parent_by }
+    }
+
+    /// Returns the problem with this conflicting parent.
+    fn summarize(&self) -> DivergedParent {
+        let entry = match self.parent_by {
+            BuilderParentBy::Children(index) => {
+                return DivergedParent::ByChildren(self.builder.entries[*index].item.guid.clone());
+            }
+            BuilderParentBy::KnownItem(index) => &self.builder.entries[*index],
+            BuilderParentBy::UnknownItem(guid) => {
+                match self.builder.entry_index_by_guid.get(guid) {
+                    Some(index) => &self.builder.entries[*index],
+                    None => {
+                        if self.builder.deleted_guids.contains(guid) {
+                            return DivergedParentGuid::Deleted(guid.clone()).into();
+                        }
+                        return DivergedParentGuid::Missing(guid.clone()).into();
+                    }
+                }
+            }
+        };
+        if entry.item.is_folder() {
+            DivergedParentGuid::Folder(entry.item.guid.clone()).into()
+        } else {
+            DivergedParentGuid::NonFolder(entry.item.guid.clone()).into()
+        }
+    }
+}
+
+impl<'a> Ord for PossibleParent<'a> {
+    /// Compares two possible parents to determine which is younger
+    /// (`Ordering::Less`). Prefers parents from `children` over `parentid`
+    /// (rule 2), and `parentid`s that reference folders over non-folders
+    /// (rule 4).
+    fn cmp(&self, other: &PossibleParent<'_>) -> Ordering {
+        let (index, other_index) = match (&self.parent_by, &other.parent_by) {
+            (BuilderParentBy::Children(index), BuilderParentBy::Children(other_index)) => {
+                // Both `self` and `other` mention the item in their `children`.
+                (*index, *other_index)
+            }
+            (BuilderParentBy::Children(_), BuilderParentBy::KnownItem(_)) => {
+                // `self` mentions the item in its `children`, and the item's
+                // `parentid` is `other`, so prefer `self`.
+                return Ordering::Less;
+            }
+            (BuilderParentBy::Children(_), BuilderParentBy::UnknownItem(_)) => {
+                // As above, except we don't know if `other` exists. We don't
+                // need to look it up, though, because we can unconditionally
+                // prefer `self`.
+                return Ordering::Less;
+            }
+            (BuilderParentBy::KnownItem(_), BuilderParentBy::Children(_)) => {
+                // The item's `parentid` is `self`, and `other` mentions the
+                // item in its `children`, so prefer `other`.
+                return Ordering::Greater;
+            }
+            (BuilderParentBy::UnknownItem(_), BuilderParentBy::Children(_)) => {
+                // As above. We don't know if `self` exists, but we
+                // unconditionally prefer `other`.
+                return Ordering::Greater;
+            }
+            // Cases where `self` and `other` are `parentid`s, existing or not,
+            // are academic, since it doesn't make sense for an item to have
+            // multiple `parentid`s.
+            _ => return Ordering::Equal,
+        };
+        // If both `self` and `other` are folders, compare timestamps. If one is
+        // a folder, but the other isn't, we prefer the folder. If neither is a
+        // folder, it doesn't matter.
+        let entry = &self.builder.entries[index];
+        let other_entry = &self.builder.entries[other_index];
+        match (entry.item.is_folder(), other_entry.item.is_folder()) {
+            (true, true) => entry.item.age.cmp(&other_entry.item.age),
+            (false, true) => Ordering::Greater,
+            (true, false) => Ordering::Less,
+            (false, false) => Ordering::Equal,
+        }
+    }
+}
+
+impl<'a> PartialOrd for PossibleParent<'a> {
+    fn partial_cmp(&self, other: &PossibleParent<'_>) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl<'a> PartialEq for PossibleParent<'a> {
+    fn eq(&self, other: &PossibleParent<'_>) -> bool {
+        self.cmp(other) == Ordering::Equal
+    }
+}
+
+impl<'a> Eq for PossibleParent<'a> {}
+
+/// Describes a resolved parent for an item.
+#[derive(Debug)]
+enum ResolvedParent {
+    /// The item is a top-level root, and has no parent.
+    Root,
+
+    /// The item has a valid, consistent structure.
+    ByStructure(Index),
+
+    /// The item has multiple parents; this is the one we picked.
+    ByChildren(Index),
+
+    /// The item has a parent-child disagreement: the folder referenced by the
+    /// item's `parentid` doesn't mention the item in its `children`, the
+    /// `parentid` doesn't exist at all, or the item is a misparented content
+    /// root.
+    ByParentGuid(Index),
+}
+
+impl ResolvedParent {
+    fn index(&self) -> Option<Index> {
+        match self {
+            ResolvedParent::Root => None,
+            ResolvedParent::ByStructure(index)
+            | ResolvedParent::ByChildren(index)
+            | ResolvedParent::ByParentGuid(index) => Some(*index),
+        }
+    }
+}
+
+/// Detects cycles in resolved parents, using Floyd's tortoise and the hare
+/// algorithm. Returns the index of the entry where the cycle was detected,
+/// or `None` if there aren't any cycles.
+fn detect_cycles(parents: &[ResolvedParent]) -> Option<Index> {
+    let mut seen = SmallBitVec::from_elem(parents.len(), false);
+    for (entry_index, parent) in parents.iter().enumerate() {
+        if seen[entry_index] {
+            continue;
+        }
+        let mut parent_index = parent.index();
+        let mut grandparent_index = parent.index().and_then(|index| parents[index].index());
+        while let (Some(i), Some(j)) = (parent_index, grandparent_index) {
+            if i == j {
+                return Some(i);
+            }
+            if seen[i] || seen[j] {
+                break;
+            }
+            parent_index = parent_index.and_then(|index| parents[index].index());
+            grandparent_index = grandparent_index
+                .and_then(|index| parents[index].index())
+                .and_then(|index| parents[index].index());
+        }
+        seen.set(entry_index, true);
+    }
+    None
+}
+
+/// Indicates if a tree entry's structure diverged.
+#[derive(Debug)]
+enum Divergence {
+    /// The structure is already correct, and doesn't need to be reuploaded.
+    Consistent,
+
+    /// The node has structure problems, and should be flagged for reupload
+    /// when merging.
+    Diverged,
+}
+
+/// Describes a structure divergence for an item in a bookmark tree. These are
+/// used for logging and validation telemetry.
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub enum Problem {
+    /// The item doesn't have a `parentid`, and isn't mentioned in any folders.
+    Orphan,
+
+    /// The item is a user content root (menu, mobile, toolbar, or unfiled),
+    /// but `parent_guid` isn't the Places root.
+    MisparentedRoot(Vec<DivergedParent>),
+
+    /// The item has diverging parents. If the vector contains more than one
+    /// `DivergedParent::ByChildren`, the item has multiple parents. If the
+    /// vector contains a `DivergedParent::ByParentGuid`, with or without a
+    /// `DivergedParent::ByChildren`, the item has a parent-child disagreement.
+    DivergedParents(Vec<DivergedParent>),
+
+    /// The item is mentioned in a folder's `children`, but doesn't exist.
+    MissingChild {
+        child_guid: Guid,
+    },
+
+    /// The item is mentioned in a folder's `children`, but is deleted.
+    DeletedChild {
+        child_guid: Guid,
+    },
+
+    // This item is invalid e.g the URL is malformed
+    InvalidItem,
+}
+
+impl Problem {
+    /// Returns count deltas for this problem.
+    fn counts(&self) -> ProblemCounts {
+        let (parents, deltas) = match self {
+            Problem::Orphan => {
+                return ProblemCounts {
+                    orphans: 1,
+                    ..ProblemCounts::default()
+                }
+            }
+            Problem::DeletedChild { .. } => {
+                return ProblemCounts {
+                    deleted_children: 1,
+                    ..ProblemCounts::default()
+                }
+            }
+            Problem::MissingChild { .. } => {
+                return ProblemCounts {
+                    missing_children: 1,
+                    ..ProblemCounts::default()
+                }
+            }
+            // For misparented roots, or items with diverged parents, we need to
+            // do a bit more work to determine all the problems. For example, a
+            // toolbar root with a `parentid` pointing to a nonexistent folder,
+            // and mentioned in the `children` of unfiled and menu has three
+            // problems: it's a misparented root, with multiple parents, and a
+            // missing `parentid`.
+            Problem::MisparentedRoot(parents) => (
+                parents,
+                ProblemCounts {
+                    misparented_roots: 1,
+                    ..ProblemCounts::default()
+                },
+            ),
+            Problem::DivergedParents(parents) => (parents, ProblemCounts::default()),
+            Problem::InvalidItem => {
+                return ProblemCounts {
+                    invalid_items: 1,
+                    ..ProblemCounts::default()
+                }
+            }
+        };
+        let deltas = match parents.as_slice() {
+            // For items with different parents `by_parent_guid` and
+            // `by_children`, report a parent-child disagreement.
+            [DivergedParent::ByChildren(_)]
+            | [DivergedParent::ByParentGuid(_)]
+            | [DivergedParent::ByChildren(_), DivergedParent::ByParentGuid(_)]
+            | [DivergedParent::ByParentGuid(_), DivergedParent::ByChildren(_)] => ProblemCounts {
+                parent_child_disagreements: 1,
+                ..deltas
+            },
+            // For items with multiple parents `by_children`, and possibly by
+            // `by_parent_guid`, report a disagreement _and_ multiple parents.
+            _ => ProblemCounts {
+                multiple_parents_by_children: 1,
+                parent_child_disagreements: 1,
+                ..deltas
+            },
+        };
+        // Count invalid or missing parents, but only once, since we're counting
+        // the number of _items with the problem_, not the _occurrences of the
+        // problem_. This is specifically for roots; it doesn't make sense for
+        // other items to have multiple `parentid`s.
+        parents.iter().fold(deltas, |deltas, parent| match parent {
+            DivergedParent::ByChildren(_) => deltas,
+            DivergedParent::ByParentGuid(p) => match p {
+                DivergedParentGuid::Folder(_) => deltas,
+                DivergedParentGuid::NonFolder(_) => {
+                    if deltas.non_folder_parent_guids > 0 {
+                        deltas
+                    } else {
+                        ProblemCounts {
+                            non_folder_parent_guids: 1,
+                            ..deltas
+                        }
+                    }
+                }
+                DivergedParentGuid::Deleted(_) => {
+                    if deltas.deleted_parent_guids > 0 {
+                        deltas
+                    } else {
+                        ProblemCounts {
+                            deleted_parent_guids: 1,
+                            ..deltas
+                        }
+                    }
+                }
+                DivergedParentGuid::Missing(_) => {
+                    if deltas.missing_parent_guids > 0 {
+                        deltas
+                    } else {
+                        ProblemCounts {
+                            missing_parent_guids: 1,
+                            ..deltas
+                        }
+                    }
+                }
+            },
+        })
+    }
+}
+
+/// Describes where an invalid parent comes from.
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub enum DivergedParent {
+    /// The item appears in this folder's `children`.
+    ByChildren(Guid),
+    /// The `parentid` references this folder.
+    ByParentGuid(DivergedParentGuid),
+}
+
+impl From<DivergedParentGuid> for DivergedParent {
+    fn from(d: DivergedParentGuid) -> DivergedParent {
+        DivergedParent::ByParentGuid(d)
+    }
+}
+
+impl fmt::Display for DivergedParent {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            DivergedParent::ByChildren(parent_guid) => {
+                write!(f, "is in children of {}", parent_guid)
+            }
+            DivergedParent::ByParentGuid(p) => match p {
+                DivergedParentGuid::Folder(parent_guid) => write!(f, "has parent {}", parent_guid),
+                DivergedParentGuid::NonFolder(parent_guid) => {
+                    write!(f, "has non-folder parent {}", parent_guid)
+                }
+                DivergedParentGuid::Deleted(parent_guid) => {
+                    write!(f, "has deleted parent {}", parent_guid)
+                }
+                DivergedParentGuid::Missing(parent_guid) => {
+                    write!(f, "has nonexistent parent {}", parent_guid)
+                }
+            },
+        }
+    }
+}
+
+/// Describes an invalid `parentid`.
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub enum DivergedParentGuid {
+    /// Exists and is a folder.
+    Folder(Guid),
+    /// Exists, but isn't a folder.
+    NonFolder(Guid),
+    /// Is explicitly deleted.
+    Deleted(Guid),
+    /// Doesn't exist at all.
+    Missing(Guid),
+}
+
+/// Records problems for all items in a tree.
+#[derive(Debug, Default)]
+pub struct Problems(HashMap<Guid, Vec<Problem>>);
+
+impl Problems {
+    /// Notes a problem for an item.
+    #[inline]
+    pub fn note(&mut self, guid: &Guid, problem: Problem) -> &mut Problems {
+        self.0.entry(guid.clone()).or_default().push(problem);
+        self
+    }
+
+    /// Returns `true` if there are no problems.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+
+    /// Returns an iterator for all problems.
+    pub fn summarize(&self) -> impl Iterator<Item = ProblemSummary<'_>> {
+        self.0.iter().flat_map(|(guid, problems)| {
+            problems
+                .iter()
+                .map(move |problem| ProblemSummary(guid, problem))
+        })
+    }
+
+    /// Returns total counts for each problem. If any counts are not 0, the
+    /// tree structure diverged.
+    pub fn counts(&self) -> ProblemCounts {
+        self.0
+            .values()
+            .flatten()
+            .fold(ProblemCounts::default(), |totals, problem| {
+                totals.add(problem.counts())
+            })
+    }
+}
+
+/// A printable summary of a problem for an item.
+#[derive(Clone, Copy, Debug)]
+pub struct ProblemSummary<'a>(&'a Guid, &'a Problem);
+
+impl<'a> ProblemSummary<'a> {
+    #[inline]
+    pub fn guid(&self) -> &Guid {
+        &self.0
+    }
+
+    #[inline]
+    pub fn problem(&self) -> &Problem {
+        &self.1
+    }
+}
+
+impl<'a> fmt::Display for ProblemSummary<'a> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let parents = match self.problem() {
+            Problem::Orphan => return write!(f, "{} is an orphan", self.guid()),
+            Problem::MisparentedRoot(parents) => {
+                write!(f, "{} is a user content root", self.guid())?;
+                if parents.is_empty() {
+                    return Ok(());
+                }
+                f.write_str(", but ")?;
+                parents
+            }
+            Problem::DivergedParents(parents) => {
+                if parents.is_empty() {
+                    return write!(f, "{} has diverged parents", self.guid());
+                }
+                write!(f, "{} ", self.guid())?;
+                parents
+            }
+            Problem::MissingChild { child_guid } => {
+                return write!(f, "{} has nonexistent child {}", self.guid(), child_guid);
+            }
+            Problem::DeletedChild { child_guid } => {
+                return write!(f, "{} has deleted child {}", self.guid(), child_guid);
+            }
+            Problem::InvalidItem => return write!(f, "{} is invalid", self.guid()),
+        };
+        match parents.as_slice() {
+            [a] => write!(f, "{}", a)?,
+            [a, b] => write!(f, "{} and {}", a, b)?,
+            _ => {
+                for (i, parent) in parents.iter().enumerate() {
+                    if i != 0 {
+                        f.write_str(", ")?;
+                    }
+                    if i == parents.len() - 1 {
+                        f.write_str("and ")?;
+                    }
+                    write!(f, "{}", parent)?;
+                }
+            }
+        }
+        Ok(())
+    }
+}
+
+/// Records total problem counts for telemetry. An item can have multiple
+/// problems, but each problem is only counted once per item.
+#[derive(Clone, Copy, Default, Debug, Eq, Hash, PartialEq)]
+pub struct ProblemCounts {
+    /// Number of items that aren't mentioned in any parent's `children` and
+    /// don't have a `parentid`. These are very rare; it's likely that a
+    /// problem child has at least a `parentid`.
+    pub orphans: usize,
+    /// Number of roots that aren't children of the Places root.
+    pub misparented_roots: usize,
+    /// Number of items with multiple, conflicting parents `by_children`.
+    pub multiple_parents_by_children: usize,
+    /// Number of items whose `parentid` is deleted.
+    pub deleted_parent_guids: usize,
+    /// Number of items whose `parentid` doesn't exist.
+    pub missing_parent_guids: usize,
+    /// Number of items whose `parentid` isn't a folder.
+    pub non_folder_parent_guids: usize,
+    /// Number of items whose `parentid`s disagree with their parents'
+    /// `children`.
+    pub parent_child_disagreements: usize,
+    /// Number of deleted items mentioned in all parents' `children`.
+    pub deleted_children: usize,
+    /// Number of nonexistent items mentioned in all parents' `children`.
+    pub missing_children: usize,
+    // Number of items with malformed URLs
+    pub invalid_items: usize,
+}
+
+impl ProblemCounts {
+    /// Adds two sets of counts together.
+    pub fn add(&self, other: ProblemCounts) -> ProblemCounts {
+        ProblemCounts {
+            orphans: self.orphans + other.orphans,
+            misparented_roots: self.misparented_roots + other.misparented_roots,
+            multiple_parents_by_children: self.multiple_parents_by_children
+                + other.multiple_parents_by_children,
+            deleted_parent_guids: self.deleted_parent_guids + other.deleted_parent_guids,
+            missing_parent_guids: self.missing_parent_guids + other.missing_parent_guids,
+            non_folder_parent_guids: self.non_folder_parent_guids + other.non_folder_parent_guids,
+            parent_child_disagreements: self.parent_child_disagreements
+                + other.parent_child_disagreements,
+            deleted_children: self.deleted_children + other.deleted_children,
+            missing_children: self.missing_children + other.missing_children,
+            invalid_items: self.invalid_items + other.invalid_items,
+        }
+    }
+}
+
+/// A node in a bookmark tree that knows its parent and children, and
+/// dereferences to its item.
+#[derive(Clone, Copy, Debug)]
+pub struct Node<'t>(&'t Tree, &'t TreeEntry);
+
+impl<'t> Node<'t> {
+    /// Returns the item for this node.
+    #[inline]
+    pub fn item(&self) -> &'t Item {
+        &self.1.item
+    }
+
+    /// Returns content info for deduping this item, if available.
+    #[inline]
+    pub fn content(&self) -> Option<&'t Content> {
+        self.1.content.as_ref()
+    }
+
+    /// Returns an iterator for all children of this node.
+    pub fn children<'n>(&'n self) -> impl Iterator<Item = Node<'t>> + 'n {
+        self.1
+            .child_indices
+            .iter()
+            .map(move |&child_index| Node(self.0, &self.0.entries[child_index]))
+    }
+
+    /// Returns the child at the given index, or `None` if the index is out of
+    /// bounds.
+    pub fn child(&self, index: usize) -> Option<Node<'_>> {
+        self.1
+            .child_indices
+            .get(index)
+            .map(|&child_index| Node(self.0, &self.0.entries[child_index]))
+    }
+
+    /// Returns `true` if this and `other` have the same child GUIDs.
+    pub fn has_matching_children<'u>(&self, other: Node<'u>) -> bool {
+        if self.1.child_indices.len() != other.1.child_indices.len() {
+            return false;
+        }
+        for (index, &child_index) in self.1.child_indices.iter().enumerate() {
+            let guid = &self.0.entries[child_index].item.guid;
+            let other_guid = &other.0.entries[other.1.child_indices[index]].item.guid;
+            if guid != other_guid {
+                return false;
+            }
+        }
+        true
+    }
+
+    /// Returns the resolved parent of this node, or `None` if this is the
+    /// root node.
+    pub fn parent(&self) -> Option<Node<'_>> {
+        self.1
+            .parent_index
+            .as_ref()
+            .map(|&parent_index| Node(self.0, &self.0.entries[parent_index]))
+    }
+
+    /// Returns the level of this node in the tree.
+    pub fn level(&self) -> i64 {
+        if self.is_root() {
+            return 0;
+        }
+        self.parent().map_or(-1, |parent| parent.level() + 1)
+    }
+
+    /// Indicates if this node is for a syncable item.
+    ///
+    /// Syncable items descend from the four user content roots. For historical
+    /// reasons, the Desktop tags root and its descendants are also marked as
+    /// syncable, even though they are not part of the synced tree structure.
+    /// Any other roots and their descendants, like the left pane root,
+    /// left pane queries, and custom roots, are non-syncable.
+    ///
+    /// Newer Desktops should never reupload non-syncable items
+    /// (bug 1274496), and should have removed them in Places
+    /// migrations (bug 1310295). However, these items may be
+    /// reparented locally to unfiled, in which case they're seen as
+    /// syncable. If the remote tree has the missing parents
+    /// and roots, we'll determine that the items are non-syncable
+    /// when merging, remove them locally, and mark them for deletion
+    /// remotely.
+    pub fn is_syncable(&self) -> bool {
+        if self.is_root() {
+            return false;
+        }
+        if self.is_built_in_root() {
+            return true;
+        }
+        match self.kind {
+            // Exclude livemarks (bug 1477671).
+            Kind::Livemark => false,
+            // Exclude orphaned Places queries (bug 1433182).
+            Kind::Query if self.diverged() => false,
+            _ => self.parent().map_or(false, |parent| parent.is_syncable()),
+        }
+    }
+
+    /// Indicates if this node's structure diverged because it
+    /// existed in multiple parents, or was reparented.
+    #[inline]
+    pub fn diverged(&self) -> bool {
+        match &self.1.divergence {
+            Divergence::Diverged => true,
+            Divergence::Consistent => false,
+        }
+    }
+
+    /// Returns an ASCII art (with emoji!) representation of this node and all
+    /// its descendants. Handy for logging.
+    pub fn to_ascii_string(&self) -> String {
+        self.to_ascii_fragment("")
+    }
+
+    fn to_ascii_fragment(&self, prefix: &str) -> String {
+        match self.item().kind {
+            Kind::Folder => {
+                let children_prefix = format!("{}| ", prefix);
+                let children = self
+                    .children()
+                    .map(|n| n.to_ascii_fragment(&children_prefix))
+                    .collect::<Vec<String>>();
+                let kind = if self.diverged() {
+                    "❗️📂"
+                } else {
+                    "📂"
+                };
+                if children.is_empty() {
+                    format!("{}{} {}", prefix, kind, self.item())
+                } else {
+                    format!(
+                        "{}{} {}\n{}",
+                        prefix,
+                        kind,
+                        self.item(),
+                        children.join("\n")
+                    )
+                }
+            }
+            _ => {
+                let kind = if self.diverged() {
+                    "❗️🔖"
+                } else {
+                    "🔖"
+                };
+                format!("{}{} {}", prefix, kind, self.item())
+            }
+        }
+    }
+
+    /// Indicates if this node is the root node.
+    #[inline]
+    pub fn is_root(&self) -> bool {
+        ptr::eq(self.1, &self.0.entries[0])
+    }
+
+    /// Indicates if this node is a Places built-in root. Any other roots except
+    /// these are non-syncable.
+    #[inline]
+    pub fn is_built_in_root(&self) -> bool {
+        self.item().guid.is_built_in_root()
+    }
+}
+
+impl<'t> Deref for Node<'t> {
+    type Target = Item;
+
+    #[inline]
+    fn deref(&self) -> &Item {
+        self.item()
+    }
+}
+
+impl<'t> fmt::Display for Node<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.item().fmt(f)
+    }
+}
+
+/// An item in a local or remote bookmark tree.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Item {
+    pub guid: Guid,
+    pub kind: Kind,
+    pub age: i64,
+    pub needs_merge: bool,
+    pub validity: Validity,
+}
+
+impl Item {
+    /// Creates an item with the given kind.
+    #[inline]
+    pub fn new(guid: Guid, kind: Kind) -> Item {
+        Item {
+            guid,
+            kind,
+            age: 0,
+            needs_merge: false,
+            validity: Validity::Valid,
+        }
+    }
+
+    /// Indicates if the item is a folder. Only folders are allowed to have
+    /// children.
+    #[inline]
+    pub fn is_folder(&self) -> bool {
+        self.kind == Kind::Folder
+    }
+
+    /// Indicates if the item can be merged with another item. Only items with
+    /// compatible kinds can be merged.
+    #[inline]
+    pub fn has_compatible_kind(&self, remote_node: &Item) -> bool {
+        match (&self.kind, &remote_node.kind) {
+            // Bookmarks and queries are interchangeable, as simply changing the URL
+            // can cause it to flip kinds.
+            (Kind::Bookmark, Kind::Query) => true,
+            (Kind::Query, Kind::Bookmark) => true,
+            (local_kind, remote_kind) => local_kind == remote_kind,
+        }
+    }
+}
+
+impl fmt::Display for Item {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let kind = match self.validity {
+            Validity::Valid => format!("{}", self.kind),
+            Validity::Reupload | Validity::Replace => format!("{} ({})", self.kind, self.validity),
+        };
+        let info = if self.needs_merge {
+            format!("{}; Age = {}ms; Unmerged", kind, self.age)
+        } else {
+            format!("{}; Age = {}ms", kind, self.age)
+        };
+        write!(f, "{} ({})", self.guid, info)
+    }
+}
+
+/// Synced item kinds. Each corresponds to a Sync record type.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+pub enum Kind {
+    Bookmark,
+    Query,
+    Folder,
+    Livemark,
+    Separator,
+}
+
+impl fmt::Display for Kind {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Debug::fmt(self, f)
+    }
+}
+
+/// Synced item validity.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+pub enum Validity {
+    /// The item is valid, and can be applied as-is.
+    Valid,
+
+    /// The item can be applied, but should also be flagged for reupload. Places
+    /// uses this to rewrite legacy tag queries.
+    Reupload,
+
+    /// The item isn't valid at all, and should either be replaced with a valid
+    /// local copy, or deleted if a valid local copy doesn't exist. Places uses
+    /// this to flag bookmarks and queries without valid URLs.
+    Replace,
+}
+
+impl fmt::Display for Validity {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        fmt::Debug::fmt(self, f)
+    }
+}
+
+/// A merged bookmark node that indicates which side to prefer, and holds merged
+/// child nodes.
+#[derive(Debug)]
+pub struct MergedNode<'t> {
+    pub guid: Guid,
+    pub merge_state: MergeState<'t>,
+    pub merged_children: Vec<MergedNode<'t>>,
+}
+
+impl<'t> MergedNode<'t> {
+    /// Creates a merged node from the given merge state.
+    pub fn new(guid: Guid, merge_state: MergeState<'t>) -> MergedNode<'t> {
+        MergedNode {
+            guid,
+            merge_state,
+            merged_children: Vec::new(),
+        }
+    }
+
+    /// Indicates if the merged node exists locally and has a new GUID.
+    /// The merger uses this to flag deduped items and items with invalid
+    /// GUIDs with new local structure.
+    pub fn local_guid_changed(&self) -> bool {
+        self.merge_state
+            .local_node()
+            .map_or(false, |local_node| local_node.guid != self.guid)
+    }
+
+    /// Indicates if the merged node exists remotely and has a new GUID. The
+    /// merger uses this to flag parents and children of remote nodes with
+    /// invalid GUIDs for reupload.
+    pub fn remote_guid_changed(&self) -> bool {
+        self.merge_state
+            .remote_node()
+            .map_or(false, |remote_node| remote_node.guid != self.guid)
+    }
+
+    /// Returns an ASCII art representation of the root and its descendants,
+    /// similar to `Node::to_ascii_string`.
+    #[inline]
+    pub fn to_ascii_string(&self) -> String {
+        self.to_ascii_fragment("")
+    }
+
+    fn to_ascii_fragment(&self, prefix: &str) -> String {
+        match self.merge_state.node().kind {
+            Kind::Folder => {
+                let children_prefix = format!("{}| ", prefix);
+                let children = self
+                    .merged_children
+                    .iter()
+                    .map(|n| n.to_ascii_fragment(&children_prefix))
+                    .collect::<Vec<String>>();
+                if children.is_empty() {
+                    format!("{}📂 {}", prefix, &self)
+                } else {
+                    format!("{}📂 {}\n{}", prefix, &self, children.join("\n"))
+                }
+            }
+            _ => format!("{}🔖 {}", prefix, &self),
+        }
+    }
+}
+
+impl<'t> fmt::Display for MergedNode<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{} {}", self.guid, self.merge_state)
+    }
+}
+
+/// The merge state indicates which side we should prefer, local or remote, when
+/// resolving conflicts.
+#[derive(Clone, Copy, Debug)]
+pub enum MergeState<'t> {
+    /// A local-only merge state means the item only exists locally, and should
+    /// be uploaded.
+    LocalOnly(Node<'t>),
+
+    /// Local-only with a new local structure means the item should be uploaded,
+    /// _and_ has new children (reparented or repositioned) locally.
+    LocalOnlyWithNewLocalStructure(Node<'t>),
+
+    /// A remote-only merge state means the item only exists remotely, and
+    /// should be applied.
+    RemoteOnly(Node<'t>),
+
+    /// Remote-only with a new remote structure means the item should be
+    /// applied, _and_ has a new child list that should be uploaded.
+    RemoteOnlyWithNewRemoteStructure(Node<'t>),
+
+    /// A local merge state means the item exists on both sides, and has newer
+    /// local changes that should be uploaded.
+    Local {
+        local_node: Node<'t>,
+        remote_node: Node<'t>,
+    },
+
+    /// Local with a new local structure means the item has newer local changes
+    /// that should be uploaded, and new children locally.
+    LocalWithNewLocalStructure {
+        local_node: Node<'t>,
+        remote_node: Node<'t>,
+    },
+
+    /// A remote merge state means the item exists on both sides, and has newer
+    /// remote changes that should be applied.
+    Remote {
+        local_node: Node<'t>,
+        remote_node: Node<'t>,
+    },
+
+    /// Remote with a new remote structure means the item has newer remote
+    /// changes that should be applied, and a new child list that should be
+    /// uploaded.
+    RemoteWithNewRemoteStructure {
+        local_node: Node<'t>,
+        remote_node: Node<'t>,
+    },
+
+    /// An unchanged merge state means the item and its children are the
+    /// same on both sides, and don't need to be uploaded or applied.
+    Unchanged {
+        local_node: Node<'t>,
+        remote_node: Node<'t>,
+    },
+
+    /// Unchanged with a new local structure means the item hasn't changed, but
+    /// its children have. The new children should be applied locally, but not
+    /// uploaded.
+    UnchangedWithNewLocalStructure {
+        local_node: Node<'t>,
+        remote_node: Node<'t>,
+    },
+}
+
+impl<'t> MergeState<'t> {
+    /// Returns the local node for the item, or `None` if the item only exists
+    /// remotely. The inverse of `remote_node()`.
+    pub fn local_node(&self) -> Option<&Node<'t>> {
+        match self {
+            MergeState::LocalOnly(local_node)
+            | MergeState::LocalOnlyWithNewLocalStructure(local_node)
+            | MergeState::Local { local_node, .. }
+            | MergeState::LocalWithNewLocalStructure { local_node, .. }
+            | MergeState::Remote { local_node, .. }
+            | MergeState::RemoteWithNewRemoteStructure { local_node, .. }
+            | MergeState::Unchanged { local_node, .. }
+            | MergeState::UnchangedWithNewLocalStructure { local_node, .. } => Some(local_node),
+            MergeState::RemoteOnly(_) | MergeState::RemoteOnlyWithNewRemoteStructure(_) => None,
+        }
+    }
+
+    /// Returns the remote node for the item, or `None` if the node only exists
+    /// locally. The inverse of `local_node()`.
+    pub fn remote_node(&self) -> Option<&Node<'t>> {
+        match self {
+            MergeState::Local { remote_node, .. }
+            | MergeState::LocalWithNewLocalStructure { remote_node, .. }
+            | MergeState::RemoteOnly(remote_node)
+            | MergeState::RemoteOnlyWithNewRemoteStructure(remote_node)
+            | MergeState::Remote { remote_node, .. }
+            | MergeState::RemoteWithNewRemoteStructure { remote_node, .. }
+            | MergeState::Unchanged { remote_node, .. }
+            | MergeState::UnchangedWithNewLocalStructure { remote_node, .. } => Some(remote_node),
+            MergeState::LocalOnly(_) | MergeState::LocalOnlyWithNewLocalStructure(_) => None,
+        }
+    }
+
+    /// Returns `true` if the remote item should be inserted into or updated
+    /// in the local tree. This is not necessarily the inverse of
+    /// `should_upload()`, as remote items with new structure should be both
+    /// applied and reuploaded, and unchanged items should be neither.
+    pub fn should_apply_item(&self) -> bool {
+        match self {
+            MergeState::RemoteOnly(_)
+            | MergeState::RemoteOnlyWithNewRemoteStructure(_)
+            | MergeState::Remote { .. }
+            | MergeState::RemoteWithNewRemoteStructure { .. } => true,
+            MergeState::LocalOnly(_)
+            | MergeState::LocalOnlyWithNewLocalStructure(_)
+            | MergeState::Local { .. }
+            | MergeState::LocalWithNewLocalStructure { .. }
+            | MergeState::Unchanged { .. }
+            | MergeState::UnchangedWithNewLocalStructure { .. } => false,
+        }
+    }
+
+    /// Returns `true` if the item has a new structure (parent or children)
+    /// that should be updated in the local tree.
+    pub fn should_apply_structure(&self) -> bool {
+        match self {
+            MergeState::LocalOnlyWithNewLocalStructure(_)
+            | MergeState::LocalWithNewLocalStructure { .. }
+            | MergeState::RemoteOnly(_)
+            | MergeState::RemoteOnlyWithNewRemoteStructure(_)
+            | MergeState::Remote { .. }
+            | MergeState::RemoteWithNewRemoteStructure { .. }
+            | MergeState::UnchangedWithNewLocalStructure { .. } => true,
+            MergeState::LocalOnly(_) | MergeState::Local { .. } | MergeState::Unchanged { .. } => {
+                false
+            }
+        }
+    }
+
+    /// Returns `true` if the item should be flagged for (re)upload.
+    pub fn should_upload(&self) -> bool {
+        match self {
+            MergeState::LocalOnly(_)
+            | MergeState::LocalOnlyWithNewLocalStructure(_)
+            | MergeState::Local { .. }
+            | MergeState::LocalWithNewLocalStructure { .. }
+            | MergeState::RemoteOnlyWithNewRemoteStructure(_)
+            | MergeState::RemoteWithNewRemoteStructure { .. } => true,
+            MergeState::RemoteOnly(_)
+            | MergeState::Remote { .. }
+            | MergeState::Unchanged { .. }
+            | MergeState::UnchangedWithNewLocalStructure { .. } => false,
+        }
+    }
+
+    /// Returns a new merge state, indicating that the item has a new merged
+    /// structure that should be applied locally.
+    pub fn with_new_local_structure(self) -> MergeState<'t> {
+        match self {
+            MergeState::LocalOnly(local_node) => {
+                MergeState::LocalOnlyWithNewLocalStructure(local_node)
+            }
+            MergeState::LocalOnlyWithNewLocalStructure(local_node) => {
+                MergeState::LocalOnlyWithNewLocalStructure(local_node)
+            }
+            MergeState::Local {
+                local_node,
+                remote_node,
+            } => MergeState::LocalWithNewLocalStructure {
+                local_node,
+                remote_node,
+            },
+            MergeState::LocalWithNewLocalStructure {
+                local_node,
+                remote_node,
+            } => MergeState::LocalWithNewLocalStructure {
+                local_node,
+                remote_node,
+            },
+            MergeState::RemoteOnly(remote_node) => MergeState::RemoteOnly(remote_node),
+            MergeState::RemoteOnlyWithNewRemoteStructure(local_node) => {
+                MergeState::RemoteOnlyWithNewRemoteStructure(local_node)
+            }
+            MergeState::Remote {
+                local_node,
+                remote_node,
+            } => MergeState::Remote {
+                local_node,
+                remote_node,
+            },
+            MergeState::RemoteWithNewRemoteStructure {
+                local_node,
+                remote_node,
+            } => MergeState::RemoteWithNewRemoteStructure {
+                local_node,
+                remote_node,
+            },
+            MergeState::Unchanged {
+                local_node,
+                remote_node,
+            } => {
+                // Once the structure changes, it doesn't matter which side we
+                // pick; we'll need to reupload the item to the server, anyway.
+                MergeState::UnchangedWithNewLocalStructure {
+                    local_node,
+                    remote_node,
+                }
+            }
+            MergeState::UnchangedWithNewLocalStructure {
+                local_node,
+                remote_node,
+            } => MergeState::UnchangedWithNewLocalStructure {
+                local_node,
+                remote_node,
+            },
+        }
+    }
+
+    /// Returns a new merge state, indicating that the item has a new merged
+    /// structure that should be reuploaded to the server.
+    pub fn with_new_remote_structure(self) -> MergeState<'t> {
+        match self {
+            MergeState::LocalOnly(local_node) => MergeState::LocalOnly(local_node),
+            MergeState::LocalOnlyWithNewLocalStructure(local_node) => {
+                MergeState::LocalOnlyWithNewLocalStructure(local_node)
+            }
+            MergeState::Local {
+                local_node,
+                remote_node,
+            } => MergeState::Local {
+                local_node,
+                remote_node,
+            },
+            MergeState::LocalWithNewLocalStructure {
+                local_node,
+                remote_node,
+            } => MergeState::LocalWithNewLocalStructure {
+                local_node,
+                remote_node,
+            },
+            MergeState::RemoteOnly(remote_node) => {
+                MergeState::RemoteOnlyWithNewRemoteStructure(remote_node)
+            }
+            MergeState::RemoteOnlyWithNewRemoteStructure(remote_node) => {
+                MergeState::RemoteOnlyWithNewRemoteStructure(remote_node)
+            }
+            MergeState::Remote {
+                local_node,
+                remote_node,
+            } => MergeState::RemoteWithNewRemoteStructure {
+                local_node,
+                remote_node,
+            },
+            MergeState::RemoteWithNewRemoteStructure {
+                local_node,
+                remote_node,
+            } => MergeState::RemoteWithNewRemoteStructure {
+                local_node,
+                remote_node,
+            },
+            MergeState::Unchanged {
+                local_node,
+                remote_node,
+            } => {
+                // Once the structure changes, it doesn't matter which side we
+                // pick; we'll need to reupload the item to the server, anyway.
+                MergeState::Local {
+                    local_node,
+                    remote_node,
+                }
+            }
+            MergeState::UnchangedWithNewLocalStructure {
+                local_node,
+                remote_node,
+            } => MergeState::LocalWithNewLocalStructure {
+                local_node,
+                remote_node,
+            },
+        }
+    }
+
+    /// Returns the node from the preferred side. Unlike `local_node()` and
+    /// `remote_node()`, this doesn't indicate which side, so it's only used
+    /// for logging and `try_from()`.
+    fn node(&self) -> &Node<'t> {
+        match self {
+            MergeState::LocalOnly(local_node)
+            | MergeState::LocalOnlyWithNewLocalStructure(local_node)
+            | MergeState::Local { local_node, .. }
+            | MergeState::LocalWithNewLocalStructure { local_node, .. }
+            | MergeState::Unchanged { local_node, .. }
+            | MergeState::UnchangedWithNewLocalStructure { local_node, .. } => local_node,
+            MergeState::RemoteOnly(remote_node)
+            | MergeState::RemoteOnlyWithNewRemoteStructure(remote_node)
+            | MergeState::Remote { remote_node, .. }
+            | MergeState::RemoteWithNewRemoteStructure { remote_node, .. } => remote_node,
+        }
+    }
+}
+
+impl<'t> fmt::Display for MergeState<'t> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str(match self {
+            MergeState::LocalOnly(_) | MergeState::Local { .. } => "(Local, Local)",
+            MergeState::LocalOnlyWithNewLocalStructure(_)
+            | MergeState::LocalWithNewLocalStructure { .. } => "(Local, New)",
+
+            MergeState::RemoteOnly(_) | MergeState::Remote { .. } => "(Remote, Remote)",
+            MergeState::RemoteOnlyWithNewRemoteStructure(_)
+            | MergeState::RemoteWithNewRemoteStructure { .. } => "(Remote, New)",
+
+            MergeState::Unchanged { .. } => "(Unchanged, Unchanged)",
+            MergeState::UnchangedWithNewLocalStructure { .. } => "(Unchanged, New)",
+        })
+    }
+}
+
+/// Content info for an item in the local or remote tree. This is used to dedupe
+/// new local items to remote items that don't exist locally, with different
+/// GUIDs and similar content.
+///
+/// - Bookmarks must have the same title and URL.
+/// - Queries must have the same title and query URL.
+/// - Folders and livemarks must have the same title.
+/// - Separators must have the same position within their parents.
+#[derive(Debug, Eq, Hash, PartialEq)]
+pub enum Content {
+    Bookmark { title: String, url_href: String },
+    Folder { title: String },
+    Separator,
+}