// 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,
        }
    );
}