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