1 // Copyright 2018-2019 Mozilla
2
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 use std::{
16 borrow::Cow,
17 cmp::Ordering,
18 collections::{HashMap, HashSet},
19 convert::{TryFrom, TryInto},
20 fmt, mem,
21 ops::Deref,
22 ptr,
23 };
24
25 use smallbitvec::SmallBitVec;
26
27 use crate::error::{Error, ErrorKind, Result};
28 use crate::guid::Guid;
29
30 /// The type for entry indices in the tree.
31 type Index = usize;
32
33 /// A complete, rooted bookmark tree with tombstones.
34 ///
35 /// The tree stores bookmark items in a vector, and uses indices in the vector
36 /// to identify parents and children. This makes traversal and lookup very
37 /// efficient. Retrieving a node's parent takes one indexing operation,
38 /// retrieving children takes one indexing operation per child, and retrieving
39 /// a node by random GUID takes one hash map lookup and one indexing operation.
40 #[derive(Debug)]
41 pub struct Tree {
42 entry_index_by_guid: HashMap<Guid, Index>,
43 entries: Vec<TreeEntry>,
44 deleted_guids: HashSet<Guid>,
45 problems: Problems,
46 }
47
48 impl Tree {
49 /// Returns a builder for a rooted tree.
with_root(root: Item) -> Builder50 pub fn with_root(root: Item) -> Builder {
51 let mut entry_index_by_guid = HashMap::new();
52 entry_index_by_guid.insert(root.guid.clone(), 0);
53
54 Builder {
55 entries: vec![BuilderEntry {
56 item: root,
57 content: None,
58 parent: BuilderEntryParent::Root,
59 children: Vec::new(),
60 }],
61 deleted_guids: HashSet::new(),
62 entry_index_by_guid,
63 reparent_orphans_to: None,
64 }
65 }
66
67 /// Returns the number of nodes in the tree.
68 #[inline]
size(&self) -> usize69 pub fn size(&self) -> usize {
70 self.entries.len()
71 }
72
73 /// Returns the root node.
74 #[inline]
root(&self) -> Node<'_>75 pub fn root(&self) -> Node<'_> {
76 Node(self, &self.entries[0])
77 }
78
79 /// Returns the set of all tombstoned GUIDs.
80 #[inline]
deletions(&self) -> &HashSet<Guid>81 pub fn deletions(&self) -> &HashSet<Guid> {
82 &self.deleted_guids
83 }
84
85 /// Indicates if the GUID exists in the tree.
86 #[inline]
exists(&self, guid: &Guid) -> bool87 pub fn exists(&self, guid: &Guid) -> bool {
88 self.entry_index_by_guid.contains_key(guid)
89 }
90
91 /// Indicates if the GUID is known to be deleted. If `Tree::node_for_guid`
92 /// returns `None` and `Tree::is_deleted` returns `false`, the item doesn't
93 /// exist in the tree at all.
94 #[inline]
is_deleted(&self, guid: &Guid) -> bool95 pub fn is_deleted(&self, guid: &Guid) -> bool {
96 self.deleted_guids.contains(guid)
97 }
98
99 /// Indicates if the GUID is mentioned in the tree, either as a node or
100 /// a deletion.
101 #[inline]
mentions(&self, guid: &Guid) -> bool102 pub fn mentions(&self, guid: &Guid) -> bool {
103 self.entry_index_by_guid.contains_key(guid) || self.deleted_guids.contains(guid)
104 }
105
106 /// Returns an iterator for all node and tombstone GUIDs.
guids(&self) -> impl Iterator<Item = &Guid>107 pub fn guids(&self) -> impl Iterator<Item = &Guid> {
108 self.entries
109 .iter()
110 .map(|entry| &entry.item.guid)
111 .chain(self.deleted_guids.iter())
112 }
113
114 /// Returns the node for a given `guid`, or `None` if a node with the `guid`
115 /// doesn't exist in the tree, or was deleted.
node_for_guid(&self, guid: &Guid) -> Option<Node<'_>>116 pub fn node_for_guid(&self, guid: &Guid) -> Option<Node<'_>> {
117 self.entry_index_by_guid
118 .get(guid)
119 .map(|&index| Node(self, &self.entries[index]))
120 }
121
122 /// Returns the structure divergences found when building the tree.
123 #[inline]
problems(&self) -> &Problems124 pub fn problems(&self) -> &Problems {
125 &self.problems
126 }
127 }
128
129 impl fmt::Display for Tree {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result130 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
131 let root = self.root();
132 f.write_str(&root.to_ascii_string())?;
133 if !self.deleted_guids.is_empty() {
134 f.write_str("\nDeleted: [")?;
135 for (i, guid) in self.deleted_guids.iter().enumerate() {
136 if i != 0 {
137 f.write_str(", ")?;
138 }
139 f.write_str(guid.as_ref())?;
140 }
141 }
142 if !self.problems.is_empty() {
143 f.write_str("\nProblems:\n")?;
144 for (i, summary) in self.problems.summarize().enumerate() {
145 if i != 0 {
146 f.write_str("\n")?;
147 }
148 write!(f, "❗️ {}", summary)?;
149 }
150 }
151 Ok(())
152 }
153 }
154
155 /// A tree builder builds a bookmark tree structure from a flat list of items
156 /// and parent-child associations.
157 ///
158 /// # Tree structure
159 ///
160 /// In a well-formed tree:
161 ///
162 /// - Each item exists in exactly one folder. Two different folder's
163 /// `children` should never reference the same item.
164 /// - Each folder contains existing children. A folder's `children` should
165 /// never reference tombstones, or items that don't exist in the tree at all.
166 /// - Each item has a `parentid` that agrees with its parent's `children`. In
167 /// other words, if item B's `parentid` is A, then A's `children` should
168 /// contain B.
169 ///
170 /// Because of Reasons, things are (a lot) messier in practice.
171 ///
172 /// # Structure inconsistencies
173 ///
174 /// Sync stores structure in two places: a `parentid` property on each item,
175 /// which points to its parent's GUID, and a list of ordered `children` on the
176 /// item's parent. They're duplicated because, historically, Sync clients didn't
177 /// stage incoming records. Instead, they applied records one at a time,
178 /// directly to the live local tree. This meant that, if a client saw a child
179 /// before its parent, it would first use the `parentid` to decide where to keep
180 /// the child, then fix up parents and positions using the parent's `children`.
181 ///
182 /// This is also why moving an item into a different folder uploads records for
183 /// the item, old folder, and new folder. The item has a new `parentid`, and the
184 /// folders have new `children`. Similarly, deleting an item uploads a tombstone
185 /// for the item, and a record for the item's old parent.
186 ///
187 /// Unfortunately, bugs (bug 1258127) and missing features (bug 1253051) in
188 /// older clients sometimes caused them to upload invalid or incomplete changes.
189 /// For example, a client might have:
190 ///
191 /// - Uploaded a moved child, but not its parents. This means the child now
192 /// appears in multiple parents. In the most extreme case, an item might be
193 /// referenced in two different sets of `children`, _and_ have a third,
194 /// completely unrelated `parentid`.
195 /// - Deleted a child, and tracked the deletion, but didn't flag the parent for
196 /// reupload. The parent folder now has a tombstone child.
197 /// - Tracked and uploaded items that shouldn't exist on the server at all,
198 /// like the left pane or reading list roots (bug 1309255).
199 /// - Missed new folders created during a sync, creating holes in the tree.
200 ///
201 /// Newer clients shouldn't do this, but we might still have inconsistent
202 /// records on the server that will confuse older clients. Additionally, Firefox
203 /// for iOS includes a much stricter bookmarks engine that refuses to sync if
204 /// it detects inconsistencies.
205 ///
206 /// # Divergences
207 ///
208 /// To work around this, the builder lets the structure _diverge_. This allows:
209 ///
210 /// - Items with multiple parents.
211 /// - Items with missing `parentid`s.
212 /// - Folders with `children` whose `parentid`s don't match the folder.
213 /// - Items whose `parentid`s don't mention the item in their `children`.
214 /// - Items with `parentid`s that point to nonexistent or deleted folders.
215 /// - Folders with nonexistent `children`.
216 /// - Non-syncable items, like custom roots.
217 /// - Any combination of these.
218 ///
219 /// # Resolving divergences
220 ///
221 /// Building a tree using `std::convert::TryInto<Tree>::try_into` resolves
222 /// divergences using these rules:
223 ///
224 /// 1. User content roots should always be children of the Places root. If
225 /// they appear in other parents, we move them.
226 /// 2. Items that appear in multiple `children`, and items with mismatched
227 /// `parentid`s, use the chronologically newer parent, based on the parent's
228 /// last modified time. We always prefer parents by `children` over
229 /// `parentid,` because `children` also gives us the item's position.
230 /// 3. Items that aren't mentioned in any parent's `children`, but have a
231 /// `parentid` that references an existing folder in the tree, are reparented
232 /// to the end of that folder, after the folder's `children`.
233 /// 4. Items that reference a nonexistent or non-folder `parentid`, or don't
234 /// have a `parentid` at all, are reparented to the default folder.
235 /// 5. If the default folder isn't set, or doesn't exist, items from rule 4 are
236 /// reparented to the root instead.
237 ///
238 /// The result is a well-formed tree structure that can be merged. The merger
239 /// detects if the structure diverged, and flags affected items for reupload.
240 #[derive(Debug)]
241 pub struct Builder {
242 entry_index_by_guid: HashMap<Guid, Index>,
243 entries: Vec<BuilderEntry>,
244 deleted_guids: HashSet<Guid>,
245 reparent_orphans_to: Option<Guid>,
246 }
247
248 impl Builder {
249 /// Sets the default folder for reparented orphans. If not set, doesn't
250 /// exist, or not a folder, orphans will be reparented to the root.
251 #[inline]
reparent_orphans_to(&mut self, guid: &Guid) -> &mut Builder252 pub fn reparent_orphans_to(&mut self, guid: &Guid) -> &mut Builder {
253 self.reparent_orphans_to = Some(guid.clone());
254 self
255 }
256
257 /// Inserts an `item` into the tree. Returns an error if the item already
258 /// exists.
item(&mut self, item: Item) -> Result<ItemBuilder<'_>>259 pub fn item(&mut self, item: Item) -> Result<ItemBuilder<'_>> {
260 assert_eq!(self.entries.len(), self.entry_index_by_guid.len());
261 if self.entry_index_by_guid.contains_key(&item.guid) {
262 return Err(ErrorKind::DuplicateItem(item.guid.clone()).into());
263 }
264 let entry_index = self.entries.len();
265 self.entry_index_by_guid
266 .insert(item.guid.clone(), entry_index);
267 self.entries.push(BuilderEntry {
268 item,
269 content: None,
270 parent: BuilderEntryParent::None,
271 children: Vec::new(),
272 });
273 Ok(ItemBuilder(self, entry_index))
274 }
275
276 /// Sets parents for a `child_guid`. Depending on where the parent comes
277 /// from, `child_guid` may not need to exist in the tree.
parent_for(&mut self, child_guid: &Guid) -> ParentBuilder<'_>278 pub fn parent_for(&mut self, child_guid: &Guid) -> ParentBuilder<'_> {
279 assert_eq!(self.entries.len(), self.entry_index_by_guid.len());
280 let entry_child = match self.entry_index_by_guid.get(child_guid) {
281 Some(&child_index) => BuilderEntryChild::Exists(child_index),
282 None => BuilderEntryChild::Missing(child_guid.clone()),
283 };
284 ParentBuilder(self, entry_child)
285 }
286
287 /// Notes a tombstone for a deleted item, marking it as deleted in the
288 /// tree.
289 #[inline]
deletion(&mut self, guid: Guid) -> &mut Builder290 pub fn deletion(&mut self, guid: Guid) -> &mut Builder {
291 self.deleted_guids.insert(guid);
292 self
293 }
294
295 /// Equivalent to using our implementation of`TryInto<Tree>::try_into`, but
296 /// provided both for convenience when updating from previous versions of
297 /// `dogear`, and for cases where a type hint would otherwise be needed to
298 /// clarify the target type of the conversion.
into_tree(self) -> Result<Tree>299 pub fn into_tree(self) -> Result<Tree> {
300 self.try_into()
301 }
302
303 /// Mutates content and structure for an existing item. This is only
304 /// exposed to tests.
305 #[cfg(test)]
mutate(&mut self, child_guid: &Guid) -> ItemBuilder<'_>306 pub fn mutate(&mut self, child_guid: &Guid) -> ItemBuilder<'_> {
307 assert_eq!(self.entries.len(), self.entry_index_by_guid.len());
308 match self.entry_index_by_guid.get(child_guid) {
309 Some(&child_index) => ItemBuilder(self, child_index),
310 None => panic!("Can't mutate nonexistent item {}", child_guid),
311 }
312 }
313 }
314
315 impl TryFrom<Builder> for Tree {
316 type Error = Error;
317 /// Builds a tree from all stored items and parent-child associations,
318 /// resolving inconsistencies like orphans, multiple parents, and
319 /// parent-child disagreements.
try_from(mut builder: Builder) -> Result<Tree>320 fn try_from(mut builder: Builder) -> Result<Tree> {
321 let mut problems = Problems::default();
322
323 // The indices in this bit vector point to zombie entries, which exist
324 // in the tree, but are also flagged as deleted. We'll remove these
325 // zombies from the set of deleted GUIDs, and mark them as diverged for
326 // reupload.
327 let mut zombies = SmallBitVec::from_elem(builder.entries.len(), false);
328
329 // First, resolve parents for all entries, and build a lookup table for
330 // items without a position.
331 let mut parents = Vec::with_capacity(builder.entries.len());
332 let mut reparented_child_indices_by_parent: HashMap<Index, Vec<Index>> = HashMap::new();
333 for (entry_index, entry) in builder.entries.iter().enumerate() {
334 let r = ResolveParent::new(&builder, entry, &mut problems);
335 let resolved_parent = r.resolve();
336 if let ResolvedParent::ByParentGuid(parent_index) = resolved_parent {
337 // Reparented items are special: since they aren't mentioned in
338 // that parent's `children`, we don't know their positions. Note
339 // them for when we resolve children. We also clone the GUID,
340 // since we use it for sorting, but can't access it by
341 // reference once we call `builder.entries.into_iter()` below.
342 let reparented_child_indices = reparented_child_indices_by_parent
343 .entry(parent_index)
344 .or_default();
345 reparented_child_indices.push(entry_index);
346 }
347 if builder.deleted_guids.remove(&entry.item.guid) {
348 zombies.set(entry_index, true);
349 }
350 parents.push(resolved_parent);
351 }
352
353 // If any parents form cycles, abort. We haven't seen cyclic trees in
354 // the wild, and breaking cycles would add complexity.
355 if let Some(index) = detect_cycles(&parents) {
356 return Err(ErrorKind::Cycle(builder.entries[index].item.guid.clone()).into());
357 }
358
359 // Then, resolve children, and build a slab of entries for the tree.
360 let mut entries = Vec::with_capacity(builder.entries.len());
361 for (entry_index, entry) in builder.entries.into_iter().enumerate() {
362 // Each entry is consistent, until proven otherwise!
363 let mut divergence = Divergence::Consistent;
364
365 let parent_index = match &parents[entry_index] {
366 ResolvedParent::Root => {
367 // The Places root doesn't have a parent, and should always
368 // be the first entry.
369 assert_eq!(entry_index, 0);
370 None
371 }
372 ResolvedParent::ByStructure(index) => {
373 // The entry has a valid parent by structure, yay!
374 Some(*index)
375 }
376 ResolvedParent::ByChildren(index) | ResolvedParent::ByParentGuid(index) => {
377 // The entry has multiple parents, and we resolved one,
378 // so it's diverged.
379 divergence = Divergence::Diverged;
380 Some(*index)
381 }
382 };
383
384 // If the entry is a zombie, mark it as diverged, so that the merger
385 // can remove the tombstone and reupload the item.
386 if zombies[entry_index] {
387 divergence = Divergence::Diverged;
388 }
389
390 // Check if the entry's children exist and agree that this entry is
391 // their parent.
392 let mut child_indices = Vec::with_capacity(entry.children.len());
393 for child in entry.children {
394 match child {
395 BuilderEntryChild::Exists(child_index) => {
396 if zombies[entry_index] {
397 // If the entry has a zombie child, mark it as
398 // diverged.
399 divergence = Divergence::Diverged;
400 }
401 match &parents[child_index] {
402 ResolvedParent::Root => {
403 // The Places root can't be a child of another entry.
404 unreachable!("A child can't be a top-level root");
405 }
406 ResolvedParent::ByStructure(parent_index) => {
407 // If the child has a valid parent by structure, it
408 // must be the entry. If it's not, there's a bug
409 // in `ResolveParent` or `BuilderEntry`.
410 assert_eq!(*parent_index, entry_index);
411 child_indices.push(child_index);
412 }
413 ResolvedParent::ByChildren(parent_index) => {
414 // If the child has multiple parents, we may have
415 // resolved a different one, so check if we decided
416 // to keep the child in this entry.
417 divergence = Divergence::Diverged;
418 if *parent_index == entry_index {
419 child_indices.push(child_index);
420 }
421 }
422 ResolvedParent::ByParentGuid(parent_index) => {
423 // We should only ever prefer parents
424 // `by_parent_guid` over parents `by_children` for
425 // misparented user content roots. Otherwise,
426 // there's a bug in `ResolveParent`.
427 assert_eq!(*parent_index, 0);
428 divergence = Divergence::Diverged;
429 }
430 }
431 }
432 BuilderEntryChild::Missing(child_guid) => {
433 // If the entry's `children` mention a deleted or
434 // nonexistent GUID, note it as a problem, and ignore
435 // the child.
436 divergence = Divergence::Diverged;
437 let problem = if builder.deleted_guids.remove(&child_guid) {
438 Problem::DeletedChild {
439 child_guid: child_guid.clone(),
440 }
441 } else {
442 Problem::MissingChild {
443 child_guid: child_guid.clone(),
444 }
445 };
446 problems.note(&entry.item.guid, problem);
447 }
448 }
449 }
450
451 // Reparented items don't appear in our `children`, so we move them
452 // to the end, after existing children (rules 3-4).
453 if let Some(reparented_child_indices) =
454 reparented_child_indices_by_parent.get(&entry_index)
455 {
456 divergence = Divergence::Diverged;
457 child_indices.extend_from_slice(reparented_child_indices);
458 }
459
460 entries.push(TreeEntry {
461 item: entry.item,
462 content: entry.content,
463 parent_index,
464 child_indices,
465 divergence,
466 });
467 }
468
469 // Now we have a consistent tree.
470 Ok(Tree {
471 entry_index_by_guid: builder.entry_index_by_guid,
472 entries,
473 deleted_guids: builder.deleted_guids,
474 problems,
475 })
476 }
477 }
478
479 /// Adds an item with content and structure to a tree builder.
480 pub struct ItemBuilder<'b>(&'b mut Builder, Index);
481
482 impl<'b> ItemBuilder<'b> {
483 /// Sets content info for an item that hasn't been uploaded or merged yet.
484 /// We'll try to dedupe local items with content info to remotely changed
485 /// items with similar contents and different GUIDs.
486 #[inline]
content<'c>(&'c mut self, content: Content) -> &'c mut ItemBuilder<'b>487 pub fn content<'c>(&'c mut self, content: Content) -> &'c mut ItemBuilder<'b> {
488 mem::replace(&mut self.0.entries[self.1].content, Some(content));
489 self
490 }
491
492 /// Records a `parent_guid` from the item's parent's `children`. See
493 /// `ParentBuilder::by_children`.
494 #[inline]
by_children(self, parent_guid: &Guid) -> Result<&'b mut Builder>495 pub fn by_children(self, parent_guid: &Guid) -> Result<&'b mut Builder> {
496 let b = ParentBuilder(self.0, BuilderEntryChild::Exists(self.1));
497 b.by_children(parent_guid)
498 }
499
500 /// Records a `parent_guid` from the item's `parentid`. See
501 /// `ParentBuilder::by_parent_guid`.
502 #[inline]
by_parent_guid(self, parent_guid: Guid) -> Result<&'b mut Builder>503 pub fn by_parent_guid(self, parent_guid: Guid) -> Result<&'b mut Builder> {
504 let b = ParentBuilder(self.0, BuilderEntryChild::Exists(self.1));
505 b.by_parent_guid(parent_guid)
506 }
507
508 #[inline]
by_structure(self, parent_guid: &Guid) -> Result<&'b mut Builder>509 pub fn by_structure(self, parent_guid: &Guid) -> Result<&'b mut Builder> {
510 let b = ParentBuilder(self.0, BuilderEntryChild::Exists(self.1));
511 b.by_structure(parent_guid)
512 }
513 }
514
515 /// Adds structure for an existing item to a tree builder.
516 pub struct ParentBuilder<'b>(&'b mut Builder, BuilderEntryChild);
517
518 impl<'b> ParentBuilder<'b> {
519 /// Records a `parent_guid` from the item's parent's `children`. The
520 /// `parent_guid` must refer to an existing folder in the tree, but
521 /// the item itself doesn't need to exist. This handles folders with
522 /// missing children.
by_children(self, parent_guid: &Guid) -> Result<&'b mut Builder>523 pub fn by_children(self, parent_guid: &Guid) -> Result<&'b mut Builder> {
524 let parent_index = match self.0.entry_index_by_guid.get(parent_guid) {
525 Some(&parent_index) if self.0.entries[parent_index].item.is_folder() => parent_index,
526 _ => {
527 let child_guid = match &self.1 {
528 BuilderEntryChild::Exists(index) => &self.0.entries[*index].item.guid,
529 BuilderEntryChild::Missing(guid) => guid,
530 };
531 return Err(
532 ErrorKind::InvalidParent(child_guid.clone(), parent_guid.clone()).into(),
533 );
534 }
535 };
536 if let BuilderEntryChild::Exists(child_index) = &self.1 {
537 self.0.entries[*child_index].parents_by(&[BuilderParentBy::Children(parent_index)])?;
538 }
539 self.0.entries[parent_index].children.push(self.1);
540 Ok(self.0)
541 }
542
543 /// Records a `parent_guid` from the item's `parentid`. The item must
544 /// exist in the tree, but the `parent_guid` doesn't need to exist,
545 /// or even refer to a folder. The builder will reparent items with
546 /// missing and non-folder `parentid`s to the default folder when it
547 /// builds the tree.
by_parent_guid(self, parent_guid: Guid) -> Result<&'b mut Builder>548 pub fn by_parent_guid(self, parent_guid: Guid) -> Result<&'b mut Builder> {
549 match &self.1 {
550 BuilderEntryChild::Exists(child_index) => {
551 self.0.entries[*child_index]
552 .parents_by(&[BuilderParentBy::UnknownItem(parent_guid)])?;
553 }
554 BuilderEntryChild::Missing(child_guid) => {
555 return Err(ErrorKind::MissingItem(child_guid.clone()).into());
556 }
557 }
558 Ok(self.0)
559 }
560
561 /// Records a `parent_guid` from a valid tree structure. This is for
562 /// callers who already know their structure is consistent, like
563 /// `Store::fetch_local_tree()` on Desktop, and
564 /// `std::convert::TryInto<Tree>` in the tests.
565 ///
566 /// Both the item and `parent_guid` must exist, and the `parent_guid` must
567 /// refer to a folder.
568 ///
569 /// `by_structure(parent_guid)` is logically the same as:
570 ///
571 /// ```no_run
572 /// # use dogear::{Item, Kind, Result, ROOT_GUID, Tree};
573 /// # fn main() -> Result<()> {
574 /// # let mut builder = Tree::with_root(Item::new(ROOT_GUID, Kind::Folder));
575 /// # let child_guid = "bookmarkAAAA".into();
576 /// # let parent_guid = "folderAAAAAA".into();
577 /// builder.parent_for(&child_guid)
578 /// .by_children(&parent_guid)?
579 /// .parent_for(&child_guid)
580 /// .by_parent_guid(parent_guid)?;
581 /// # Ok(())
582 /// # }
583 /// ```
584 ///
585 /// ...But more convenient. It's also more efficient, because it avoids
586 /// multiple lookups for the item and parent, as well as an extra heap
587 /// allocation to store the parents.
by_structure(self, parent_guid: &Guid) -> Result<&'b mut Builder>588 pub fn by_structure(self, parent_guid: &Guid) -> Result<&'b mut Builder> {
589 let parent_index = match self.0.entry_index_by_guid.get(parent_guid) {
590 Some(&parent_index) if self.0.entries[parent_index].item.is_folder() => parent_index,
591 _ => {
592 let child_guid = match &self.1 {
593 BuilderEntryChild::Exists(index) => &self.0.entries[*index].item.guid,
594 BuilderEntryChild::Missing(guid) => guid,
595 };
596 return Err(
597 ErrorKind::InvalidParent(child_guid.clone(), parent_guid.clone()).into(),
598 );
599 }
600 };
601 if let BuilderEntryChild::Exists(child_index) = &self.1 {
602 self.0.entries[*child_index].parents_by(&[
603 BuilderParentBy::Children(parent_index),
604 BuilderParentBy::KnownItem(parent_index),
605 ])?;
606 }
607 self.0.entries[parent_index].children.push(self.1);
608 Ok(self.0)
609 }
610 }
611
612 /// An entry wraps a tree item with references to its parents and children,
613 /// which index into the tree's `entries` vector. This indirection exists
614 /// because Rust is more strict about ownership of parents and children.
615 ///
616 /// For example, we can't have entries own their children without sacrificing
617 /// fast random lookup: we'd need to store references to the entries in the
618 /// lookup map, but a struct can't hold references into itself.
619 ///
620 /// Similarly, we can't have entries hold `Weak` pointers to `Rc` entries for
621 /// the parent and children, because we need to update the parent when we insert
622 /// a new node, but `Rc` won't hand us a mutable reference to the entry as long
623 /// as it has outstanding `Weak` pointers.
624 ///
625 /// We *could* use GUIDs instead of indices, and store the entries in a
626 /// `HashMap<String, Entry>`, but that's inefficient: we'd need to store N
627 /// copies of the GUID for parent and child lookups, and retrieving children
628 /// would take one hash map lookup *per child*.
629 ///
630 /// Note that we always compare references to entries, instead of deriving
631 /// `PartialEq`, because two entries with the same fields but in different
632 /// trees should never compare equal.
633 #[derive(Debug)]
634 struct TreeEntry {
635 item: Item,
636 content: Option<Content>,
637 divergence: Divergence,
638 parent_index: Option<Index>,
639 child_indices: Vec<Index>,
640 }
641
642 /// A builder entry holds an item and its structure. It's the builder's analog
643 /// of a `TreeEntry`.
644 #[derive(Debug)]
645 struct BuilderEntry {
646 item: Item,
647 content: Option<Content>,
648 parent: BuilderEntryParent,
649 children: Vec<BuilderEntryChild>,
650 }
651
652 impl BuilderEntry {
653 /// Adds `new_parents` for the entry.
parents_by(&mut self, new_parents: &[BuilderParentBy]) -> Result<()>654 fn parents_by(&mut self, new_parents: &[BuilderParentBy]) -> Result<()> {
655 let old_parent = mem::replace(&mut self.parent, BuilderEntryParent::None);
656 let new_parent = match old_parent {
657 BuilderEntryParent::Root => {
658 mem::replace(&mut self.parent, BuilderEntryParent::Root);
659 return Err(ErrorKind::DuplicateItem(self.item.guid.clone()).into());
660 }
661 BuilderEntryParent::None => match new_parents {
662 [BuilderParentBy::Children(from_children), BuilderParentBy::KnownItem(from_item)]
663 | [BuilderParentBy::KnownItem(from_item), BuilderParentBy::Children(from_children)]
664 if from_children == from_item =>
665 {
666 // If the parent's `children` and item's `parentid` match,
667 // we have a complete structure, so we can avoid an extra
668 // allocation for the partial structure.
669 BuilderEntryParent::Complete(*from_children)
670 }
671 new_parents => BuilderEntryParent::Partial(new_parents.to_vec()),
672 },
673 BuilderEntryParent::Complete(index) => {
674 let mut parents = vec![
675 BuilderParentBy::Children(index),
676 BuilderParentBy::KnownItem(index),
677 ];
678 parents.extend_from_slice(new_parents);
679 BuilderEntryParent::Partial(parents)
680 }
681 BuilderEntryParent::Partial(mut parents) => {
682 parents.extend_from_slice(new_parents);
683 BuilderEntryParent::Partial(parents)
684 }
685 };
686 mem::replace(&mut self.parent, new_parent);
687 Ok(())
688 }
689 }
690
691 /// Holds an existing child index, or missing child GUID, for a builder entry.
692 #[derive(Debug)]
693 enum BuilderEntryChild {
694 Exists(Index),
695 Missing(Guid),
696 }
697
698 /// Holds one or more parents for a builder entry.
699 #[derive(Clone, Debug)]
700 enum BuilderEntryParent {
701 /// The entry is an orphan.
702 None,
703
704 /// The entry is a top-level root, from which all other entries descend.
705 /// A tree can only have one root.
706 Root,
707
708 /// The entry has two matching parents from its structure. This is the fast
709 /// path for local trees, which are always valid.
710 Complete(Index),
711
712 /// The entry has an incomplete or divergent structure. This is the path for
713 /// all remote trees, valid and invalid, since we add structure from
714 /// `parentid`s and `children` separately. This is also the path for
715 /// mismatched and multiple parents.
716 Partial(Vec<BuilderParentBy>),
717 }
718
719 /// Describes where a builder entry's parent comes from.
720 #[derive(Clone, Debug)]
721 enum BuilderParentBy {
722 /// The entry's parent references the entry in its `children`.
723 Children(Index),
724
725 /// The entry's parent comes from its `parentid`, and will be resolved
726 /// when we build the tree.
727 UnknownItem(Guid),
728
729 /// The entry's parent comes from its `parentid` and has been
730 /// resolved.
731 KnownItem(Index),
732 }
733
734 /// Resolves the parent for a builder entry.
735 struct ResolveParent<'a> {
736 builder: &'a Builder,
737 entry: &'a BuilderEntry,
738 problems: &'a mut Problems,
739 }
740
741 impl<'a> ResolveParent<'a> {
new( builder: &'a Builder, entry: &'a BuilderEntry, problems: &'a mut Problems, ) -> ResolveParent<'a>742 fn new(
743 builder: &'a Builder,
744 entry: &'a BuilderEntry,
745 problems: &'a mut Problems,
746 ) -> ResolveParent<'a> {
747 ResolveParent {
748 builder,
749 entry,
750 problems,
751 }
752 }
753
resolve(self) -> ResolvedParent754 fn resolve(self) -> ResolvedParent {
755 if self.entry.item.guid.is_built_in_root() {
756 self.user_content_root()
757 } else {
758 self.item()
759 }
760 }
761
762 /// Returns the parent for this builder entry. This unifies parents
763 /// `by_structure`, which are known to be consistent, and parents
764 /// `by_children` and `by_parent_guid`, which are consistent if they match.
parent(&self) -> Cow<'a, BuilderEntryParent>765 fn parent(&self) -> Cow<'a, BuilderEntryParent> {
766 let parents = match &self.entry.parent {
767 // Roots and orphans pass through as-is.
768 BuilderEntryParent::Root => return Cow::Owned(BuilderEntryParent::Root),
769 BuilderEntryParent::None => return Cow::Owned(BuilderEntryParent::None),
770 BuilderEntryParent::Complete(index) => {
771 // The entry is known to have a valid parent by structure. This
772 // is the fast path, used for local trees in Desktop.
773 return Cow::Owned(BuilderEntryParent::Complete(*index));
774 }
775 BuilderEntryParent::Partial(parents) => parents,
776 };
777 // The entry has zero, one, or many parents, recorded separately. Check
778 // if it has exactly two: one `by_parent_guid`, and one `by_children`.
779 let (index_by_guid, index_by_children) = match parents.as_slice() {
780 [BuilderParentBy::UnknownItem(guid), BuilderParentBy::Children(index_by_children)]
781 | [BuilderParentBy::Children(index_by_children), BuilderParentBy::UnknownItem(guid)] => {
782 match self.builder.entry_index_by_guid.get(guid) {
783 Some(&index_by_guid) => (index_by_guid, *index_by_children),
784 None => return Cow::Borrowed(&self.entry.parent),
785 }
786 }
787 [BuilderParentBy::KnownItem(index_by_guid), BuilderParentBy::Children(index_by_children)]
788 | [BuilderParentBy::Children(index_by_children), BuilderParentBy::KnownItem(index_by_guid)] => {
789 (*index_by_guid, *index_by_children)
790 }
791 // In all other cases (missing `parentid`, missing from `children`,
792 // multiple parents), return all possible parents. We'll pick one
793 // when we resolve the parent.
794 _ => return Cow::Borrowed(&self.entry.parent),
795 };
796 // If the entry has matching parents `by_children` and `by_parent_guid`,
797 // it has a valid parent by structure. This is the "fast slow path",
798 // used for remote trees in Desktop, because their structure is built in
799 // two passes. In all other cases, we have a parent-child disagreement,
800 // so return all possible parents.
801 if index_by_guid == index_by_children {
802 Cow::Owned(BuilderEntryParent::Complete(index_by_children))
803 } else {
804 Cow::Borrowed(&self.entry.parent)
805 }
806 }
807
808 /// Resolves the parent for a user content root: menu, mobile, toolbar, and
809 /// unfiled. These are simpler to resolve than non-roots because they must
810 /// be children of the Places root (rule 1), which is always the first
811 /// entry.
user_content_root(self) -> ResolvedParent812 fn user_content_root(self) -> ResolvedParent {
813 match self.parent().as_ref() {
814 BuilderEntryParent::None => {
815 // Orphaned content root. This should only happen if the content
816 // root doesn't have a parent `by_parent_guid`.
817 self.problems.note(&self.entry.item.guid, Problem::Orphan);
818 ResolvedParent::ByParentGuid(0)
819 }
820 BuilderEntryParent::Root => {
821 unreachable!("A user content root can't be a top-level root")
822 }
823 BuilderEntryParent::Complete(index) => {
824 if *index == 0 {
825 ResolvedParent::ByStructure(*index)
826 } else {
827 // Move misparented content roots to the Places root.
828 let parent_guid = self.builder.entries[*index].item.guid.clone();
829 self.problems.note(
830 &self.entry.item.guid,
831 Problem::MisparentedRoot(vec![
832 DivergedParent::ByChildren(parent_guid.clone()),
833 DivergedParentGuid::Folder(parent_guid).into(),
834 ]),
835 );
836 ResolvedParent::ByParentGuid(0)
837 }
838 }
839 BuilderEntryParent::Partial(parents_by) => {
840 // Ditto for content roots with multiple parents or parent-child
841 // disagreements.
842 self.problems.note(
843 &self.entry.item.guid,
844 Problem::MisparentedRoot(
845 parents_by
846 .iter()
847 .map(|parent_by| {
848 PossibleParent::new(self.builder, parent_by).summarize()
849 })
850 .collect(),
851 ),
852 );
853 ResolvedParent::ByParentGuid(0)
854 }
855 }
856 }
857
858 /// Resolves the parent for a top-level Places root or other item, using
859 /// rules 2-5.
item(self) -> ResolvedParent860 fn item(self) -> ResolvedParent {
861 match self.parent().as_ref() {
862 BuilderEntryParent::Root => ResolvedParent::Root,
863 BuilderEntryParent::None => {
864 // The item doesn't have a `parentid`, and isn't mentioned in
865 // any `children`. Reparent to the default folder (rule 4) or
866 // Places root (rule 5).
867 let parent_index = self.reparent_orphans_to_default_index();
868 self.problems.note(&self.entry.item.guid, Problem::Orphan);
869 ResolvedParent::ByParentGuid(parent_index)
870 }
871 BuilderEntryParent::Complete(index) => {
872 // The item's `parentid` and parent's `children` match, so keep
873 // it in its current parent.
874 ResolvedParent::ByStructure(*index)
875 }
876 BuilderEntryParent::Partial(parents) => {
877 // For items with one or more than two parents, pick the
878 // youngest (minimum age).
879 let possible_parents = parents
880 .iter()
881 .map(|parent_by| PossibleParent::new(self.builder, parent_by))
882 .collect::<Vec<_>>();
883 self.problems.note(
884 &self.entry.item.guid,
885 Problem::DivergedParents(
886 possible_parents
887 .iter()
888 .map(PossibleParent::summarize)
889 .collect(),
890 ),
891 );
892 possible_parents
893 .into_iter()
894 .min()
895 .and_then(|p| match p.parent_by {
896 BuilderParentBy::Children(index) => {
897 Some(ResolvedParent::ByChildren(*index))
898 }
899 BuilderParentBy::KnownItem(index) => {
900 Some(ResolvedParent::ByParentGuid(*index))
901 }
902 BuilderParentBy::UnknownItem(guid) => self
903 .builder
904 .entry_index_by_guid
905 .get(guid)
906 .filter(|&&index| self.builder.entries[index].item.is_folder())
907 .map(|&index| ResolvedParent::ByParentGuid(index)),
908 })
909 .unwrap_or_else(|| {
910 // Fall back to the default folder (rule 4) or root
911 // (rule 5) if we didn't find a parent.
912 let parent_index = self.reparent_orphans_to_default_index();
913 ResolvedParent::ByParentGuid(parent_index)
914 })
915 }
916 }
917 }
918
919 /// Returns the index of the default parent entry for reparented orphans.
920 /// This is either the default folder (rule 4), or the root, if the
921 /// default folder isn't set, doesn't exist, or isn't a folder (rule 5).
reparent_orphans_to_default_index(&self) -> Index922 fn reparent_orphans_to_default_index(&self) -> Index {
923 self.builder
924 .reparent_orphans_to
925 .as_ref()
926 .and_then(|guid| self.builder.entry_index_by_guid.get(guid))
927 .cloned()
928 .filter(|&parent_index| {
929 let parent_entry = &self.builder.entries[parent_index];
930 parent_entry.item.is_folder()
931 })
932 .unwrap_or(0)
933 }
934 }
935
936 // A possible parent for an item with conflicting parents. We use this wrapper's
937 // `Ord` implementation to decide which parent is youngest.
938 #[derive(Clone, Copy, Debug)]
939 struct PossibleParent<'a> {
940 builder: &'a Builder,
941 parent_by: &'a BuilderParentBy,
942 }
943
944 impl<'a> PossibleParent<'a> {
new(builder: &'a Builder, parent_by: &'a BuilderParentBy) -> PossibleParent<'a>945 fn new(builder: &'a Builder, parent_by: &'a BuilderParentBy) -> PossibleParent<'a> {
946 PossibleParent { builder, parent_by }
947 }
948
949 /// Returns the problem with this conflicting parent.
summarize(&self) -> DivergedParent950 fn summarize(&self) -> DivergedParent {
951 let entry = match self.parent_by {
952 BuilderParentBy::Children(index) => {
953 return DivergedParent::ByChildren(self.builder.entries[*index].item.guid.clone());
954 }
955 BuilderParentBy::KnownItem(index) => &self.builder.entries[*index],
956 BuilderParentBy::UnknownItem(guid) => {
957 match self.builder.entry_index_by_guid.get(guid) {
958 Some(index) => &self.builder.entries[*index],
959 None => {
960 if self.builder.deleted_guids.contains(guid) {
961 return DivergedParentGuid::Deleted(guid.clone()).into();
962 }
963 return DivergedParentGuid::Missing(guid.clone()).into();
964 }
965 }
966 }
967 };
968 if entry.item.is_folder() {
969 DivergedParentGuid::Folder(entry.item.guid.clone()).into()
970 } else {
971 DivergedParentGuid::NonFolder(entry.item.guid.clone()).into()
972 }
973 }
974 }
975
976 impl<'a> Ord for PossibleParent<'a> {
977 /// Compares two possible parents to determine which is younger
978 /// (`Ordering::Less`). Prefers parents from `children` over `parentid`
979 /// (rule 2), and `parentid`s that reference folders over non-folders
980 /// (rule 4).
cmp(&self, other: &PossibleParent<'_>) -> Ordering981 fn cmp(&self, other: &PossibleParent<'_>) -> Ordering {
982 let (index, other_index) = match (&self.parent_by, &other.parent_by) {
983 (BuilderParentBy::Children(index), BuilderParentBy::Children(other_index)) => {
984 // Both `self` and `other` mention the item in their `children`.
985 (*index, *other_index)
986 }
987 (BuilderParentBy::Children(_), BuilderParentBy::KnownItem(_)) => {
988 // `self` mentions the item in its `children`, and the item's
989 // `parentid` is `other`, so prefer `self`.
990 return Ordering::Less;
991 }
992 (BuilderParentBy::Children(_), BuilderParentBy::UnknownItem(_)) => {
993 // As above, except we don't know if `other` exists. We don't
994 // need to look it up, though, because we can unconditionally
995 // prefer `self`.
996 return Ordering::Less;
997 }
998 (BuilderParentBy::KnownItem(_), BuilderParentBy::Children(_)) => {
999 // The item's `parentid` is `self`, and `other` mentions the
1000 // item in its `children`, so prefer `other`.
1001 return Ordering::Greater;
1002 }
1003 (BuilderParentBy::UnknownItem(_), BuilderParentBy::Children(_)) => {
1004 // As above. We don't know if `self` exists, but we
1005 // unconditionally prefer `other`.
1006 return Ordering::Greater;
1007 }
1008 // Cases where `self` and `other` are `parentid`s, existing or not,
1009 // are academic, since it doesn't make sense for an item to have
1010 // multiple `parentid`s.
1011 _ => return Ordering::Equal,
1012 };
1013 // If both `self` and `other` are folders, compare timestamps. If one is
1014 // a folder, but the other isn't, we prefer the folder. If neither is a
1015 // folder, it doesn't matter.
1016 let entry = &self.builder.entries[index];
1017 let other_entry = &self.builder.entries[other_index];
1018 match (entry.item.is_folder(), other_entry.item.is_folder()) {
1019 (true, true) => entry.item.age.cmp(&other_entry.item.age),
1020 (false, true) => Ordering::Greater,
1021 (true, false) => Ordering::Less,
1022 (false, false) => Ordering::Equal,
1023 }
1024 }
1025 }
1026
1027 impl<'a> PartialOrd for PossibleParent<'a> {
partial_cmp(&self, other: &PossibleParent<'_>) -> Option<Ordering>1028 fn partial_cmp(&self, other: &PossibleParent<'_>) -> Option<Ordering> {
1029 Some(self.cmp(other))
1030 }
1031 }
1032
1033 impl<'a> PartialEq for PossibleParent<'a> {
eq(&self, other: &PossibleParent<'_>) -> bool1034 fn eq(&self, other: &PossibleParent<'_>) -> bool {
1035 self.cmp(other) == Ordering::Equal
1036 }
1037 }
1038
1039 impl<'a> Eq for PossibleParent<'a> {}
1040
1041 /// Describes a resolved parent for an item.
1042 #[derive(Debug)]
1043 enum ResolvedParent {
1044 /// The item is a top-level root, and has no parent.
1045 Root,
1046
1047 /// The item has a valid, consistent structure.
1048 ByStructure(Index),
1049
1050 /// The item has multiple parents; this is the one we picked.
1051 ByChildren(Index),
1052
1053 /// The item has a parent-child disagreement: the folder referenced by the
1054 /// item's `parentid` doesn't mention the item in its `children`, the
1055 /// `parentid` doesn't exist at all, or the item is a misparented content
1056 /// root.
1057 ByParentGuid(Index),
1058 }
1059
1060 impl ResolvedParent {
index(&self) -> Option<Index>1061 fn index(&self) -> Option<Index> {
1062 match self {
1063 ResolvedParent::Root => None,
1064 ResolvedParent::ByStructure(index)
1065 | ResolvedParent::ByChildren(index)
1066 | ResolvedParent::ByParentGuid(index) => Some(*index),
1067 }
1068 }
1069 }
1070
1071 /// Detects cycles in resolved parents, using Floyd's tortoise and the hare
1072 /// algorithm. Returns the index of the entry where the cycle was detected,
1073 /// or `None` if there aren't any cycles.
detect_cycles(parents: &[ResolvedParent]) -> Option<Index>1074 fn detect_cycles(parents: &[ResolvedParent]) -> Option<Index> {
1075 let mut seen = SmallBitVec::from_elem(parents.len(), false);
1076 for (entry_index, parent) in parents.iter().enumerate() {
1077 if seen[entry_index] {
1078 continue;
1079 }
1080 let mut parent_index = parent.index();
1081 let mut grandparent_index = parent.index().and_then(|index| parents[index].index());
1082 while let (Some(i), Some(j)) = (parent_index, grandparent_index) {
1083 if i == j {
1084 return Some(i);
1085 }
1086 if seen[i] || seen[j] {
1087 break;
1088 }
1089 parent_index = parent_index.and_then(|index| parents[index].index());
1090 grandparent_index = grandparent_index
1091 .and_then(|index| parents[index].index())
1092 .and_then(|index| parents[index].index());
1093 }
1094 seen.set(entry_index, true);
1095 }
1096 None
1097 }
1098
1099 /// Indicates if a tree entry's structure diverged.
1100 #[derive(Debug)]
1101 enum Divergence {
1102 /// The structure is already correct, and doesn't need to be reuploaded.
1103 Consistent,
1104
1105 /// The node has structure problems, and should be flagged for reupload
1106 /// when merging.
1107 Diverged,
1108 }
1109
1110 /// Describes a structure divergence for an item in a bookmark tree. These are
1111 /// used for logging and validation telemetry.
1112 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
1113 pub enum Problem {
1114 /// The item doesn't have a `parentid`, and isn't mentioned in any folders.
1115 Orphan,
1116
1117 /// The item is a user content root (menu, mobile, toolbar, or unfiled),
1118 /// but `parent_guid` isn't the Places root.
1119 MisparentedRoot(Vec<DivergedParent>),
1120
1121 /// The item has diverging parents. If the vector contains more than one
1122 /// `DivergedParent::ByChildren`, the item has multiple parents. If the
1123 /// vector contains a `DivergedParent::ByParentGuid`, with or without a
1124 /// `DivergedParent::ByChildren`, the item has a parent-child disagreement.
1125 DivergedParents(Vec<DivergedParent>),
1126
1127 /// The item is mentioned in a folder's `children`, but doesn't exist.
1128 MissingChild { child_guid: Guid },
1129
1130 /// The item is mentioned in a folder's `children`, but is deleted.
1131 DeletedChild { child_guid: Guid },
1132 }
1133
1134 impl Problem {
1135 /// Returns count deltas for this problem.
counts(&self) -> ProblemCounts1136 fn counts(&self) -> ProblemCounts {
1137 let (parents, deltas) = match self {
1138 Problem::Orphan => {
1139 return ProblemCounts {
1140 orphans: 1,
1141 ..ProblemCounts::default()
1142 }
1143 }
1144 Problem::DeletedChild { .. } => {
1145 return ProblemCounts {
1146 deleted_children: 1,
1147 ..ProblemCounts::default()
1148 }
1149 }
1150 Problem::MissingChild { .. } => {
1151 return ProblemCounts {
1152 missing_children: 1,
1153 ..ProblemCounts::default()
1154 }
1155 }
1156 // For misparented roots, or items with diverged parents, we need to
1157 // do a bit more work to determine all the problems. For example, a
1158 // toolbar root with a `parentid` pointing to a nonexistent folder,
1159 // and mentioned in the `children` of unfiled and menu has three
1160 // problems: it's a misparented root, with multiple parents, and a
1161 // missing `parentid`.
1162 Problem::MisparentedRoot(parents) => (
1163 parents,
1164 ProblemCounts {
1165 misparented_roots: 1,
1166 ..ProblemCounts::default()
1167 },
1168 ),
1169 Problem::DivergedParents(parents) => (parents, ProblemCounts::default()),
1170 };
1171 let deltas = match parents.as_slice() {
1172 // For items with different parents `by_parent_guid` and
1173 // `by_children`, report a parent-child disagreement.
1174 [DivergedParent::ByChildren(_)]
1175 | [DivergedParent::ByParentGuid(_)]
1176 | [DivergedParent::ByChildren(_), DivergedParent::ByParentGuid(_)]
1177 | [DivergedParent::ByParentGuid(_), DivergedParent::ByChildren(_)] => ProblemCounts {
1178 parent_child_disagreements: 1,
1179 ..deltas
1180 },
1181 // For items with multiple parents `by_children`, and possibly by
1182 // `by_parent_guid`, report a disagreement _and_ multiple parents.
1183 _ => ProblemCounts {
1184 multiple_parents_by_children: 1,
1185 parent_child_disagreements: 1,
1186 ..deltas
1187 },
1188 };
1189 // Count invalid or missing parents, but only once, since we're counting
1190 // the number of _items with the problem_, not the _occurrences of the
1191 // problem_. This is specifically for roots; it doesn't make sense for
1192 // other items to have multiple `parentid`s.
1193 parents.iter().fold(deltas, |deltas, parent| match parent {
1194 DivergedParent::ByChildren(_) => deltas,
1195 DivergedParent::ByParentGuid(p) => match p {
1196 DivergedParentGuid::Folder(_) => deltas,
1197 DivergedParentGuid::NonFolder(_) => {
1198 if deltas.non_folder_parent_guids > 0 {
1199 deltas
1200 } else {
1201 ProblemCounts {
1202 non_folder_parent_guids: 1,
1203 ..deltas
1204 }
1205 }
1206 }
1207 DivergedParentGuid::Deleted(_) => {
1208 if deltas.deleted_parent_guids > 0 {
1209 deltas
1210 } else {
1211 ProblemCounts {
1212 deleted_parent_guids: 1,
1213 ..deltas
1214 }
1215 }
1216 }
1217 DivergedParentGuid::Missing(_) => {
1218 if deltas.missing_parent_guids > 0 {
1219 deltas
1220 } else {
1221 ProblemCounts {
1222 missing_parent_guids: 1,
1223 ..deltas
1224 }
1225 }
1226 }
1227 },
1228 })
1229 }
1230 }
1231
1232 /// Describes where an invalid parent comes from.
1233 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
1234 pub enum DivergedParent {
1235 /// The item appears in this folder's `children`.
1236 ByChildren(Guid),
1237 /// The `parentid` references this folder.
1238 ByParentGuid(DivergedParentGuid),
1239 }
1240
1241 impl From<DivergedParentGuid> for DivergedParent {
from(d: DivergedParentGuid) -> DivergedParent1242 fn from(d: DivergedParentGuid) -> DivergedParent {
1243 DivergedParent::ByParentGuid(d)
1244 }
1245 }
1246
1247 impl fmt::Display for DivergedParent {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1248 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1249 match self {
1250 DivergedParent::ByChildren(parent_guid) => {
1251 write!(f, "is in children of {}", parent_guid)
1252 }
1253 DivergedParent::ByParentGuid(p) => match p {
1254 DivergedParentGuid::Folder(parent_guid) => write!(f, "has parent {}", parent_guid),
1255 DivergedParentGuid::NonFolder(parent_guid) => {
1256 write!(f, "has non-folder parent {}", parent_guid)
1257 }
1258 DivergedParentGuid::Deleted(parent_guid) => {
1259 write!(f, "has deleted parent {}", parent_guid)
1260 }
1261 DivergedParentGuid::Missing(parent_guid) => {
1262 write!(f, "has nonexistent parent {}", parent_guid)
1263 }
1264 },
1265 }
1266 }
1267 }
1268
1269 /// Describes an invalid `parentid`.
1270 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
1271 pub enum DivergedParentGuid {
1272 /// Exists and is a folder.
1273 Folder(Guid),
1274 /// Exists, but isn't a folder.
1275 NonFolder(Guid),
1276 /// Is explicitly deleted.
1277 Deleted(Guid),
1278 /// Doesn't exist at all.
1279 Missing(Guid),
1280 }
1281
1282 /// Records problems for all items in a tree.
1283 #[derive(Debug, Default)]
1284 pub struct Problems(HashMap<Guid, Vec<Problem>>);
1285
1286 impl Problems {
1287 /// Notes a problem for an item.
1288 #[inline]
note(&mut self, guid: &Guid, problem: Problem) -> &mut Problems1289 pub fn note(&mut self, guid: &Guid, problem: Problem) -> &mut Problems {
1290 self.0.entry(guid.clone()).or_default().push(problem);
1291 self
1292 }
1293
1294 /// Returns `true` if there are no problems.
1295 #[inline]
is_empty(&self) -> bool1296 pub fn is_empty(&self) -> bool {
1297 self.0.is_empty()
1298 }
1299
1300 /// Returns an iterator for all problems.
summarize(&self) -> impl Iterator<Item = ProblemSummary<'_>>1301 pub fn summarize(&self) -> impl Iterator<Item = ProblemSummary<'_>> {
1302 self.0.iter().flat_map(|(guid, problems)| {
1303 problems
1304 .iter()
1305 .map(move |problem| ProblemSummary(guid, problem))
1306 })
1307 }
1308
1309 /// Returns total counts for each problem. If any counts are not 0, the
1310 /// tree structure diverged.
counts(&self) -> ProblemCounts1311 pub fn counts(&self) -> ProblemCounts {
1312 self.0
1313 .values()
1314 .flatten()
1315 .fold(ProblemCounts::default(), |totals, problem| {
1316 totals.add(problem.counts())
1317 })
1318 }
1319 }
1320
1321 /// A printable summary of a problem for an item.
1322 #[derive(Clone, Copy, Debug)]
1323 pub struct ProblemSummary<'a>(&'a Guid, &'a Problem);
1324
1325 impl<'a> ProblemSummary<'a> {
1326 #[inline]
guid(&self) -> &Guid1327 pub fn guid(&self) -> &Guid {
1328 &self.0
1329 }
1330
1331 #[inline]
problem(&self) -> &Problem1332 pub fn problem(&self) -> &Problem {
1333 &self.1
1334 }
1335 }
1336
1337 impl<'a> fmt::Display for ProblemSummary<'a> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1338 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1339 let parents = match self.problem() {
1340 Problem::Orphan => return write!(f, "{} is an orphan", self.guid()),
1341 Problem::MisparentedRoot(parents) => {
1342 write!(f, "{} is a user content root", self.guid())?;
1343 if parents.is_empty() {
1344 return Ok(());
1345 }
1346 f.write_str(", but ")?;
1347 parents
1348 }
1349 Problem::DivergedParents(parents) => {
1350 if parents.is_empty() {
1351 return write!(f, "{} has diverged parents", self.guid());
1352 }
1353 write!(f, "{} ", self.guid())?;
1354 parents
1355 }
1356 Problem::MissingChild { child_guid } => {
1357 return write!(f, "{} has nonexistent child {}", self.guid(), child_guid);
1358 }
1359 Problem::DeletedChild { child_guid } => {
1360 return write!(f, "{} has deleted child {}", self.guid(), child_guid);
1361 }
1362 };
1363 match parents.as_slice() {
1364 [a] => write!(f, "{}", a)?,
1365 [a, b] => write!(f, "{} and {}", a, b)?,
1366 _ => {
1367 for (i, parent) in parents.iter().enumerate() {
1368 if i != 0 {
1369 f.write_str(", ")?;
1370 }
1371 if i == parents.len() - 1 {
1372 f.write_str("and ")?;
1373 }
1374 write!(f, "{}", parent)?;
1375 }
1376 }
1377 }
1378 Ok(())
1379 }
1380 }
1381
1382 /// Records total problem counts for telemetry. An item can have multiple
1383 /// problems, but each problem is only counted once per item.
1384 #[derive(Clone, Copy, Default, Debug, Eq, Hash, PartialEq)]
1385 pub struct ProblemCounts {
1386 /// Number of items that aren't mentioned in any parent's `children` and
1387 /// don't have a `parentid`. These are very rare; it's likely that a
1388 /// problem child has at least a `parentid`.
1389 pub orphans: usize,
1390 /// Number of roots that aren't children of the Places root.
1391 pub misparented_roots: usize,
1392 /// Number of items with multiple, conflicting parents `by_children`.
1393 pub multiple_parents_by_children: usize,
1394 /// Number of items whose `parentid` is deleted.
1395 pub deleted_parent_guids: usize,
1396 /// Number of items whose `parentid` doesn't exist.
1397 pub missing_parent_guids: usize,
1398 /// Number of items whose `parentid` isn't a folder.
1399 pub non_folder_parent_guids: usize,
1400 /// Number of items whose `parentid`s disagree with their parents'
1401 /// `children`.
1402 pub parent_child_disagreements: usize,
1403 /// Number of deleted items mentioned in all parents' `children`.
1404 pub deleted_children: usize,
1405 /// Number of nonexistent items mentioned in all parents' `children`.
1406 pub missing_children: usize,
1407 }
1408
1409 impl ProblemCounts {
1410 /// Adds two sets of counts together.
add(&self, other: ProblemCounts) -> ProblemCounts1411 pub fn add(&self, other: ProblemCounts) -> ProblemCounts {
1412 ProblemCounts {
1413 orphans: self.orphans + other.orphans,
1414 misparented_roots: self.misparented_roots + other.misparented_roots,
1415 multiple_parents_by_children: self.multiple_parents_by_children
1416 + other.multiple_parents_by_children,
1417 deleted_parent_guids: self.deleted_parent_guids + other.deleted_parent_guids,
1418 missing_parent_guids: self.missing_parent_guids + other.missing_parent_guids,
1419 non_folder_parent_guids: self.non_folder_parent_guids + other.non_folder_parent_guids,
1420 parent_child_disagreements: self.parent_child_disagreements
1421 + other.parent_child_disagreements,
1422 deleted_children: self.deleted_children + other.deleted_children,
1423 missing_children: self.missing_children + other.missing_children,
1424 }
1425 }
1426 }
1427
1428 /// A node in a bookmark tree that knows its parent and children, and
1429 /// dereferences to its item.
1430 #[derive(Clone, Copy, Debug)]
1431 pub struct Node<'t>(&'t Tree, &'t TreeEntry);
1432
1433 impl<'t> Node<'t> {
1434 /// Returns the item for this node.
1435 #[inline]
item(&self) -> &'t Item1436 pub fn item(&self) -> &'t Item {
1437 &self.1.item
1438 }
1439
1440 /// Returns content info for deduping this item, if available.
1441 #[inline]
content(&self) -> Option<&'t Content>1442 pub fn content(&self) -> Option<&'t Content> {
1443 self.1.content.as_ref()
1444 }
1445
1446 /// Returns an iterator for all children of this node.
children<'n>(&'n self) -> impl Iterator<Item = Node<'t>> + 'n1447 pub fn children<'n>(&'n self) -> impl Iterator<Item = Node<'t>> + 'n {
1448 self.1
1449 .child_indices
1450 .iter()
1451 .map(move |&child_index| Node(self.0, &self.0.entries[child_index]))
1452 }
1453
1454 /// Returns the child at the given index, or `None` if the index is out of
1455 /// bounds.
child(&self, index: usize) -> Option<Node<'_>>1456 pub fn child(&self, index: usize) -> Option<Node<'_>> {
1457 self.1
1458 .child_indices
1459 .get(index)
1460 .map(|&child_index| Node(self.0, &self.0.entries[child_index]))
1461 }
1462
1463 /// Returns `true` if this and `other` have the same child GUIDs.
has_matching_children<'u>(&self, other: Node<'u>) -> bool1464 pub fn has_matching_children<'u>(&self, other: Node<'u>) -> bool {
1465 if self.1.child_indices.len() != other.1.child_indices.len() {
1466 return false;
1467 }
1468 for (index, &child_index) in self.1.child_indices.iter().enumerate() {
1469 let guid = &self.0.entries[child_index].item.guid;
1470 let other_guid = &other.0.entries[other.1.child_indices[index]].item.guid;
1471 if guid != other_guid {
1472 return false;
1473 }
1474 }
1475 true
1476 }
1477
1478 /// Returns the resolved parent of this node, or `None` if this is the
1479 /// root node.
parent(&self) -> Option<Node<'_>>1480 pub fn parent(&self) -> Option<Node<'_>> {
1481 self.1
1482 .parent_index
1483 .as_ref()
1484 .map(|&parent_index| Node(self.0, &self.0.entries[parent_index]))
1485 }
1486
1487 /// Returns the level of this node in the tree.
level(&self) -> i641488 pub fn level(&self) -> i64 {
1489 if self.is_root() {
1490 return 0;
1491 }
1492 self.parent().map_or(-1, |parent| parent.level() + 1)
1493 }
1494
1495 /// Indicates if this node is for a syncable item.
1496 ///
1497 /// Syncable items descend from the four user content roots. For historical
1498 /// reasons, the Desktop tags root and its descendants are also marked as
1499 /// syncable, even though they are not part of the synced tree structure.
1500 /// Any other roots and their descendants, like the left pane root,
1501 /// left pane queries, and custom roots, are non-syncable.
1502 ///
1503 /// Newer Desktops should never reupload non-syncable items
1504 /// (bug 1274496), and should have removed them in Places
1505 /// migrations (bug 1310295). However, these items may be
1506 /// reparented locally to unfiled, in which case they're seen as
1507 /// syncable. If the remote tree has the missing parents
1508 /// and roots, we'll determine that the items are non-syncable
1509 /// when merging, remove them locally, and mark them for deletion
1510 /// remotely.
is_syncable(&self) -> bool1511 pub fn is_syncable(&self) -> bool {
1512 if self.is_root() {
1513 return false;
1514 }
1515 if self.is_built_in_root() {
1516 return true;
1517 }
1518 match self.kind {
1519 // Exclude livemarks (bug 1477671).
1520 Kind::Livemark => false,
1521 // Exclude orphaned Places queries (bug 1433182).
1522 Kind::Query if self.diverged() => false,
1523 _ => self.parent().map_or(false, |parent| parent.is_syncable()),
1524 }
1525 }
1526
1527 /// Indicates if this node's structure diverged because it
1528 /// existed in multiple parents, or was reparented.
1529 #[inline]
diverged(&self) -> bool1530 pub fn diverged(&self) -> bool {
1531 match &self.1.divergence {
1532 Divergence::Diverged => true,
1533 Divergence::Consistent => false,
1534 }
1535 }
1536
1537 /// Returns an ASCII art (with emoji!) representation of this node and all
1538 /// its descendants. Handy for logging.
to_ascii_string(&self) -> String1539 pub fn to_ascii_string(&self) -> String {
1540 self.to_ascii_fragment("")
1541 }
1542
to_ascii_fragment(&self, prefix: &str) -> String1543 fn to_ascii_fragment(&self, prefix: &str) -> String {
1544 match self.item().kind {
1545 Kind::Folder => {
1546 let children_prefix = format!("{}| ", prefix);
1547 let children = self
1548 .children()
1549 .map(|n| n.to_ascii_fragment(&children_prefix))
1550 .collect::<Vec<String>>();
1551 let kind = if self.diverged() {
1552 "❗️"
1553 } else {
1554 ""
1555 };
1556 if children.is_empty() {
1557 format!("{}{} {}", prefix, kind, self.item())
1558 } else {
1559 format!(
1560 "{}{} {}\n{}",
1561 prefix,
1562 kind,
1563 self.item(),
1564 children.join("\n")
1565 )
1566 }
1567 }
1568 _ => {
1569 let kind = if self.diverged() {
1570 "❗️"
1571 } else {
1572 ""
1573 };
1574 format!("{}{} {}", prefix, kind, self.item())
1575 }
1576 }
1577 }
1578
1579 /// Indicates if this node is the root node.
1580 #[inline]
is_root(&self) -> bool1581 pub fn is_root(&self) -> bool {
1582 ptr::eq(self.1, &self.0.entries[0])
1583 }
1584
1585 /// Indicates if this node is a Places built-in root. Any other roots except
1586 /// these are non-syncable.
1587 #[inline]
is_built_in_root(&self) -> bool1588 pub fn is_built_in_root(&self) -> bool {
1589 self.item().guid.is_built_in_root()
1590 }
1591 }
1592
1593 impl<'t> Deref for Node<'t> {
1594 type Target = Item;
1595
1596 #[inline]
deref(&self) -> &Item1597 fn deref(&self) -> &Item {
1598 self.item()
1599 }
1600 }
1601
1602 impl<'t> fmt::Display for Node<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1603 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1604 self.item().fmt(f)
1605 }
1606 }
1607
1608 /// An item in a local or remote bookmark tree.
1609 #[derive(Debug, Eq, PartialEq)]
1610 pub struct Item {
1611 pub guid: Guid,
1612 pub kind: Kind,
1613 pub age: i64,
1614 pub needs_merge: bool,
1615 pub validity: Validity,
1616 }
1617
1618 impl Item {
1619 /// Creates an item with the given kind.
1620 #[inline]
new(guid: Guid, kind: Kind) -> Item1621 pub fn new(guid: Guid, kind: Kind) -> Item {
1622 Item {
1623 guid,
1624 kind,
1625 age: 0,
1626 needs_merge: false,
1627 validity: Validity::Valid,
1628 }
1629 }
1630
1631 /// Indicates if the item is a folder. Only folders are allowed to have
1632 /// children.
1633 #[inline]
is_folder(&self) -> bool1634 pub fn is_folder(&self) -> bool {
1635 self.kind == Kind::Folder
1636 }
1637
1638 /// Indicates if the item can be merged with another item. Only items with
1639 /// compatible kinds can be merged.
1640 #[inline]
has_compatible_kind(&self, remote_node: &Item) -> bool1641 pub fn has_compatible_kind(&self, remote_node: &Item) -> bool {
1642 match (&self.kind, &remote_node.kind) {
1643 // Bookmarks and queries are interchangeable, as simply changing the URL
1644 // can cause it to flip kinds.
1645 (Kind::Bookmark, Kind::Query) => true,
1646 (Kind::Query, Kind::Bookmark) => true,
1647 (local_kind, remote_kind) => local_kind == remote_kind,
1648 }
1649 }
1650 }
1651
1652 impl fmt::Display for Item {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1653 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1654 let kind = match self.validity {
1655 Validity::Valid => format!("{}", self.kind),
1656 Validity::Reupload | Validity::Replace => format!("{} ({})", self.kind, self.validity),
1657 };
1658 let info = if self.needs_merge {
1659 format!("{}; Age = {}ms; Unmerged", kind, self.age)
1660 } else {
1661 format!("{}; Age = {}ms", kind, self.age)
1662 };
1663 write!(f, "{} ({})", self.guid, info)
1664 }
1665 }
1666
1667 /// Synced item kinds. Each corresponds to a Sync record type.
1668 #[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1669 pub enum Kind {
1670 Bookmark,
1671 Query,
1672 Folder,
1673 Livemark,
1674 Separator,
1675 }
1676
1677 impl fmt::Display for Kind {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1678 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1679 fmt::Debug::fmt(self, f)
1680 }
1681 }
1682
1683 /// Synced item validity.
1684 #[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
1685 pub enum Validity {
1686 /// The item is valid, and can be applied as-is.
1687 Valid,
1688
1689 /// The item can be applied, but should also be flagged for reupload. Places
1690 /// uses this to rewrite legacy tag queries.
1691 Reupload,
1692
1693 /// The item isn't valid at all, and should either be replaced with a valid
1694 /// local copy, or deleted if a valid local copy doesn't exist. Places uses
1695 /// this to flag bookmarks and queries without valid URLs.
1696 Replace,
1697 }
1698
1699 impl fmt::Display for Validity {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1700 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1701 fmt::Debug::fmt(self, f)
1702 }
1703 }
1704
1705 /// A merged bookmark node that indicates which side to prefer, and holds merged
1706 /// child nodes.
1707 #[derive(Debug)]
1708 pub struct MergedNode<'t> {
1709 pub guid: Guid,
1710 pub merge_state: MergeState<'t>,
1711 pub merged_children: Vec<MergedNode<'t>>,
1712 }
1713
1714 impl<'t> MergedNode<'t> {
1715 /// Creates a merged node from the given merge state.
new(guid: Guid, merge_state: MergeState<'t>) -> MergedNode<'t>1716 pub fn new(guid: Guid, merge_state: MergeState<'t>) -> MergedNode<'t> {
1717 MergedNode {
1718 guid,
1719 merge_state,
1720 merged_children: Vec::new(),
1721 }
1722 }
1723
1724 /// Indicates if the merged node exists locally and has a new GUID.
1725 /// The merger uses this to flag deduped items and items with invalid
1726 /// GUIDs with new local structure.
local_guid_changed(&self) -> bool1727 pub fn local_guid_changed(&self) -> bool {
1728 self.merge_state
1729 .local_node()
1730 .map_or(false, |local_node| local_node.guid != self.guid)
1731 }
1732
1733 /// Indicates if the merged node exists remotely and has a new GUID. The
1734 /// merger uses this to flag parents and children of remote nodes with
1735 /// invalid GUIDs for reupload.
remote_guid_changed(&self) -> bool1736 pub fn remote_guid_changed(&self) -> bool {
1737 self.merge_state
1738 .remote_node()
1739 .map_or(false, |remote_node| remote_node.guid != self.guid)
1740 }
1741
1742 /// Returns an ASCII art representation of the root and its descendants,
1743 /// similar to `Node::to_ascii_string`.
1744 #[inline]
to_ascii_string(&self) -> String1745 pub fn to_ascii_string(&self) -> String {
1746 self.to_ascii_fragment("")
1747 }
1748
to_ascii_fragment(&self, prefix: &str) -> String1749 fn to_ascii_fragment(&self, prefix: &str) -> String {
1750 match self.merge_state.node().kind {
1751 Kind::Folder => {
1752 let children_prefix = format!("{}| ", prefix);
1753 let children = self
1754 .merged_children
1755 .iter()
1756 .map(|n| n.to_ascii_fragment(&children_prefix))
1757 .collect::<Vec<String>>();
1758 if children.is_empty() {
1759 format!("{} {}", prefix, &self)
1760 } else {
1761 format!("{} {}\n{}", prefix, &self, children.join("\n"))
1762 }
1763 }
1764 _ => format!("{} {}", prefix, &self),
1765 }
1766 }
1767 }
1768
1769 impl<'t> fmt::Display for MergedNode<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1770 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1771 write!(f, "{} {}", self.guid, self.merge_state)
1772 }
1773 }
1774
1775 /// The merge state indicates which side we should prefer, local or remote, when
1776 /// resolving conflicts.
1777 #[derive(Clone, Copy, Debug)]
1778 pub enum MergeState<'t> {
1779 /// A local-only merge state means the item only exists locally, and should
1780 /// be uploaded.
1781 LocalOnly(Node<'t>),
1782
1783 /// Local-only with a new local structure means the item should be uploaded,
1784 /// _and_ has new children (reparented or repositioned) locally.
1785 LocalOnlyWithNewLocalStructure(Node<'t>),
1786
1787 /// A remote-only merge state means the item only exists remotely, and
1788 /// should be applied.
1789 RemoteOnly(Node<'t>),
1790
1791 /// Remote-only with a new remote structure means the item should be
1792 /// applied, _and_ has a new child list that should be uploaded.
1793 RemoteOnlyWithNewRemoteStructure(Node<'t>),
1794
1795 /// A local merge state means the item exists on both sides, and has newer
1796 /// local changes that should be uploaded.
1797 Local {
1798 local_node: Node<'t>,
1799 remote_node: Node<'t>,
1800 },
1801
1802 /// Local with a new local structure means the item has newer local changes
1803 /// that should be uploaded, and new children locally.
1804 LocalWithNewLocalStructure {
1805 local_node: Node<'t>,
1806 remote_node: Node<'t>,
1807 },
1808
1809 /// A remote merge state means the item exists on both sides, and has newer
1810 /// remote changes that should be applied.
1811 Remote {
1812 local_node: Node<'t>,
1813 remote_node: Node<'t>,
1814 },
1815
1816 /// Remote with a new remote structure means the item has newer remote
1817 /// changes that should be applied, and a new child list that should be
1818 /// uploaded.
1819 RemoteWithNewRemoteStructure {
1820 local_node: Node<'t>,
1821 remote_node: Node<'t>,
1822 },
1823
1824 /// An unchanged merge state means the item and its children are the
1825 /// same on both sides, and don't need to be uploaded or applied.
1826 Unchanged {
1827 local_node: Node<'t>,
1828 remote_node: Node<'t>,
1829 },
1830
1831 /// Unchanged with a new local structure means the item hasn't changed, but
1832 /// its children have. The new children should be applied locally, but not
1833 /// uploaded.
1834 UnchangedWithNewLocalStructure {
1835 local_node: Node<'t>,
1836 remote_node: Node<'t>,
1837 },
1838 }
1839
1840 impl<'t> MergeState<'t> {
1841 /// Returns the local node for the item, or `None` if the item only exists
1842 /// remotely. The inverse of `remote_node()`.
local_node(&self) -> Option<&Node<'t>>1843 pub fn local_node(&self) -> Option<&Node<'t>> {
1844 match self {
1845 MergeState::LocalOnly(local_node)
1846 | MergeState::LocalOnlyWithNewLocalStructure(local_node)
1847 | MergeState::Local { local_node, .. }
1848 | MergeState::LocalWithNewLocalStructure { local_node, .. }
1849 | MergeState::Remote { local_node, .. }
1850 | MergeState::RemoteWithNewRemoteStructure { local_node, .. }
1851 | MergeState::Unchanged { local_node, .. }
1852 | MergeState::UnchangedWithNewLocalStructure { local_node, .. } => Some(local_node),
1853 MergeState::RemoteOnly(_) | MergeState::RemoteOnlyWithNewRemoteStructure(_) => None,
1854 }
1855 }
1856
1857 /// Returns the remote node for the item, or `None` if the node only exists
1858 /// locally. The inverse of `local_node()`.
remote_node(&self) -> Option<&Node<'t>>1859 pub fn remote_node(&self) -> Option<&Node<'t>> {
1860 match self {
1861 MergeState::Local { remote_node, .. }
1862 | MergeState::LocalWithNewLocalStructure { remote_node, .. }
1863 | MergeState::RemoteOnly(remote_node)
1864 | MergeState::RemoteOnlyWithNewRemoteStructure(remote_node)
1865 | MergeState::Remote { remote_node, .. }
1866 | MergeState::RemoteWithNewRemoteStructure { remote_node, .. }
1867 | MergeState::Unchanged { remote_node, .. }
1868 | MergeState::UnchangedWithNewLocalStructure { remote_node, .. } => Some(remote_node),
1869 MergeState::LocalOnly(_) | MergeState::LocalOnlyWithNewLocalStructure(_) => None,
1870 }
1871 }
1872
1873 /// Returns `true` if the remote item should be inserted into or updated
1874 /// in the local tree. This is not necessarily the inverse of
1875 /// `should_upload()`, as remote items with new structure should be both
1876 /// applied and reuploaded, and unchanged items should be neither.
should_apply_item(&self) -> bool1877 pub fn should_apply_item(&self) -> bool {
1878 match self {
1879 MergeState::RemoteOnly(_)
1880 | MergeState::RemoteOnlyWithNewRemoteStructure(_)
1881 | MergeState::Remote { .. }
1882 | MergeState::RemoteWithNewRemoteStructure { .. } => true,
1883 MergeState::LocalOnly(_)
1884 | MergeState::LocalOnlyWithNewLocalStructure(_)
1885 | MergeState::Local { .. }
1886 | MergeState::LocalWithNewLocalStructure { .. }
1887 | MergeState::Unchanged { .. }
1888 | MergeState::UnchangedWithNewLocalStructure { .. } => false,
1889 }
1890 }
1891
1892 /// Returns `true` if the item has a new structure (parent or children)
1893 /// that should be updated in the local tree.
should_apply_structure(&self) -> bool1894 pub fn should_apply_structure(&self) -> bool {
1895 match self {
1896 MergeState::LocalOnlyWithNewLocalStructure(_)
1897 | MergeState::LocalWithNewLocalStructure { .. }
1898 | MergeState::RemoteOnly(_)
1899 | MergeState::RemoteOnlyWithNewRemoteStructure(_)
1900 | MergeState::Remote { .. }
1901 | MergeState::RemoteWithNewRemoteStructure { .. }
1902 | MergeState::UnchangedWithNewLocalStructure { .. } => true,
1903 MergeState::LocalOnly(_) | MergeState::Local { .. } | MergeState::Unchanged { .. } => {
1904 false
1905 }
1906 }
1907 }
1908
1909 /// Returns `true` if the item should be flagged for (re)upload.
should_upload(&self) -> bool1910 pub fn should_upload(&self) -> bool {
1911 match self {
1912 MergeState::LocalOnly(_)
1913 | MergeState::LocalOnlyWithNewLocalStructure(_)
1914 | MergeState::Local { .. }
1915 | MergeState::LocalWithNewLocalStructure { .. }
1916 | MergeState::RemoteOnlyWithNewRemoteStructure(_)
1917 | MergeState::RemoteWithNewRemoteStructure { .. } => true,
1918 MergeState::RemoteOnly(_)
1919 | MergeState::Remote { .. }
1920 | MergeState::Unchanged { .. }
1921 | MergeState::UnchangedWithNewLocalStructure { .. } => false,
1922 }
1923 }
1924
1925 /// Returns a new merge state, indicating that the item has a new merged
1926 /// structure that should be applied locally.
with_new_local_structure(self) -> MergeState<'t>1927 pub fn with_new_local_structure(self) -> MergeState<'t> {
1928 match self {
1929 MergeState::LocalOnly(local_node) => {
1930 MergeState::LocalOnlyWithNewLocalStructure(local_node)
1931 }
1932 MergeState::LocalOnlyWithNewLocalStructure(local_node) => {
1933 MergeState::LocalOnlyWithNewLocalStructure(local_node)
1934 }
1935 MergeState::Local {
1936 local_node,
1937 remote_node,
1938 } => MergeState::LocalWithNewLocalStructure {
1939 local_node,
1940 remote_node,
1941 },
1942 MergeState::LocalWithNewLocalStructure {
1943 local_node,
1944 remote_node,
1945 } => MergeState::LocalWithNewLocalStructure {
1946 local_node,
1947 remote_node,
1948 },
1949 MergeState::RemoteOnly(remote_node) => MergeState::RemoteOnly(remote_node),
1950 MergeState::RemoteOnlyWithNewRemoteStructure(local_node) => {
1951 MergeState::RemoteOnlyWithNewRemoteStructure(local_node)
1952 }
1953 MergeState::Remote {
1954 local_node,
1955 remote_node,
1956 } => MergeState::Remote {
1957 local_node,
1958 remote_node,
1959 },
1960 MergeState::RemoteWithNewRemoteStructure {
1961 local_node,
1962 remote_node,
1963 } => MergeState::RemoteWithNewRemoteStructure {
1964 local_node,
1965 remote_node,
1966 },
1967 MergeState::Unchanged {
1968 local_node,
1969 remote_node,
1970 } => {
1971 // Once the structure changes, it doesn't matter which side we
1972 // pick; we'll need to reupload the item to the server, anyway.
1973 MergeState::UnchangedWithNewLocalStructure {
1974 local_node,
1975 remote_node,
1976 }
1977 }
1978 MergeState::UnchangedWithNewLocalStructure {
1979 local_node,
1980 remote_node,
1981 } => MergeState::UnchangedWithNewLocalStructure {
1982 local_node,
1983 remote_node,
1984 },
1985 }
1986 }
1987
1988 /// Returns a new merge state, indicating that the item has a new merged
1989 /// structure that should be reuploaded to the server.
with_new_remote_structure(self) -> MergeState<'t>1990 pub fn with_new_remote_structure(self) -> MergeState<'t> {
1991 match self {
1992 MergeState::LocalOnly(local_node) => MergeState::LocalOnly(local_node),
1993 MergeState::LocalOnlyWithNewLocalStructure(local_node) => {
1994 MergeState::LocalOnlyWithNewLocalStructure(local_node)
1995 }
1996 MergeState::Local {
1997 local_node,
1998 remote_node,
1999 } => MergeState::Local {
2000 local_node,
2001 remote_node,
2002 },
2003 MergeState::LocalWithNewLocalStructure {
2004 local_node,
2005 remote_node,
2006 } => MergeState::LocalWithNewLocalStructure {
2007 local_node,
2008 remote_node,
2009 },
2010 MergeState::RemoteOnly(remote_node) => {
2011 MergeState::RemoteOnlyWithNewRemoteStructure(remote_node)
2012 }
2013 MergeState::RemoteOnlyWithNewRemoteStructure(remote_node) => {
2014 MergeState::RemoteOnlyWithNewRemoteStructure(remote_node)
2015 }
2016 MergeState::Remote {
2017 local_node,
2018 remote_node,
2019 } => MergeState::RemoteWithNewRemoteStructure {
2020 local_node,
2021 remote_node,
2022 },
2023 MergeState::RemoteWithNewRemoteStructure {
2024 local_node,
2025 remote_node,
2026 } => MergeState::RemoteWithNewRemoteStructure {
2027 local_node,
2028 remote_node,
2029 },
2030 MergeState::Unchanged {
2031 local_node,
2032 remote_node,
2033 } => {
2034 // Once the structure changes, it doesn't matter which side we
2035 // pick; we'll need to reupload the item to the server, anyway.
2036 MergeState::Local {
2037 local_node,
2038 remote_node,
2039 }
2040 }
2041 MergeState::UnchangedWithNewLocalStructure {
2042 local_node,
2043 remote_node,
2044 } => MergeState::LocalWithNewLocalStructure {
2045 local_node,
2046 remote_node,
2047 },
2048 }
2049 }
2050
2051 /// Returns the node from the preferred side. Unlike `local_node()` and
2052 /// `remote_node()`, this doesn't indicate which side, so it's only used
2053 /// for logging and `try_from()`.
node(&self) -> &Node<'t>2054 fn node(&self) -> &Node<'t> {
2055 match self {
2056 MergeState::LocalOnly(local_node)
2057 | MergeState::LocalOnlyWithNewLocalStructure(local_node)
2058 | MergeState::Local { local_node, .. }
2059 | MergeState::LocalWithNewLocalStructure { local_node, .. }
2060 | MergeState::Unchanged { local_node, .. }
2061 | MergeState::UnchangedWithNewLocalStructure { local_node, .. } => local_node,
2062 MergeState::RemoteOnly(remote_node)
2063 | MergeState::RemoteOnlyWithNewRemoteStructure(remote_node)
2064 | MergeState::Remote { remote_node, .. }
2065 | MergeState::RemoteWithNewRemoteStructure { remote_node, .. } => remote_node,
2066 }
2067 }
2068 }
2069
2070 impl<'t> fmt::Display for MergeState<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2071 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2072 f.write_str(match self {
2073 MergeState::LocalOnly(_) | MergeState::Local { .. } => "(Local, Local)",
2074 MergeState::LocalOnlyWithNewLocalStructure(_)
2075 | MergeState::LocalWithNewLocalStructure { .. } => "(Local, New)",
2076
2077 MergeState::RemoteOnly(_) | MergeState::Remote { .. } => "(Remote, Remote)",
2078 MergeState::RemoteOnlyWithNewRemoteStructure(_)
2079 | MergeState::RemoteWithNewRemoteStructure { .. } => "(Remote, New)",
2080
2081 MergeState::Unchanged { .. } => "(Unchanged, Unchanged)",
2082 MergeState::UnchangedWithNewLocalStructure { .. } => "(Unchanged, New)",
2083 })
2084 }
2085 }
2086
2087 /// Content info for an item in the local or remote tree. This is used to dedupe
2088 /// new local items to remote items that don't exist locally, with different
2089 /// GUIDs and similar content.
2090 ///
2091 /// - Bookmarks must have the same title and URL.
2092 /// - Queries must have the same title and query URL.
2093 /// - Folders and livemarks must have the same title.
2094 /// - Separators must have the same position within their parents.
2095 #[derive(Debug, Eq, Hash, PartialEq)]
2096 pub enum Content {
2097 Bookmark { title: String, url_href: String },
2098 Folder { title: String },
2099 Separator,
2100 }
2101