diff options
Diffstat (limited to 'third_party/rust/dogear/src')
| -rw-r--r-- | third_party/rust/dogear/src/driver.rs | 212 | ||||
| -rw-r--r-- | third_party/rust/dogear/src/error.rs | 134 | ||||
| -rw-r--r-- | third_party/rust/dogear/src/guid.rs | 301 | ||||
| -rw-r--r-- | third_party/rust/dogear/src/lib.rs | 34 | ||||
| -rw-r--r-- | third_party/rust/dogear/src/merge.rs | 2280 | ||||
| -rw-r--r-- | third_party/rust/dogear/src/store.rs | 117 | ||||
| -rw-r--r-- | third_party/rust/dogear/src/tests.rs | 2929 | ||||
| -rw-r--r-- | third_party/rust/dogear/src/tree.rs | 2162 |
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, +} |