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 collections::{hash_map::Entry, HashMap, HashSet, VecDeque},
17 fmt, mem,
18 };
19
20 use crate::driver::{AbortSignal, DefaultAbortSignal, DefaultDriver, Driver};
21 use crate::error::{ErrorKind, Result};
22 use crate::guid::{Guid, IsValidGuid, TAGS_GUID};
23 use crate::tree::{Content, MergeState, MergedNode, Node, Tree, Validity};
24
25 /// Structure change types, used to indicate if a node on one side is moved
26 /// or deleted on the other.
27 #[derive(Eq, PartialEq)]
28 enum StructureChange {
29 /// Node not deleted, or doesn't exist, on the other side.
30 Unchanged,
31 /// Node moved on the other side.
32 Moved,
33 /// Node deleted on the other side.
34 Deleted,
35 }
36
37 /// Records structure change counters for telemetry.
38 #[derive(Clone, Copy, Default, Debug, Eq, Hash, PartialEq)]
39 pub struct StructureCounts {
40 /// Remote non-folder change wins over local deletion.
41 pub remote_revives: usize,
42 /// Local folder deletion wins over remote change.
43 pub local_deletes: usize,
44 /// Local non-folder change wins over remote deletion.
45 pub local_revives: usize,
46 /// Remote folder deletion wins over local change.
47 pub remote_deletes: usize,
48 /// Deduped local items.
49 pub dupes: usize,
50 /// Total number of nodes in the merged tree, excluding the
51 /// root.
52 pub merged_nodes: usize,
53 }
54
55 /// Holds (matching remote dupes for local GUIDs, matching local dupes for
56 /// remote GUIDs).
57 type MatchingDupes<'t> = (HashMap<Guid, Node<'t>>, HashMap<Guid, Node<'t>>);
58
59 /// Indicates which side to take in case of a merge conflict.
60 #[derive(Clone, Copy, Debug)]
61 enum ConflictResolution {
62 Local,
63 Remote,
64 Unchanged,
65 }
66
67 /// A hash key used to match dupes by content.
68 #[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
69 enum DupeKey<'a> {
70 /// Matches a dupe by content only. Used for bookmarks, queries, folders,
71 /// and livemarks.
72 WithoutPosition(&'a Content),
73 /// Matches a dupe by content and position. Used for separators.
74 WithPosition(&'a Content, usize),
75 }
76
77 /// A two-way merger that produces a complete merged tree from a complete local
78 /// tree and a complete remote tree with changes since the last sync.
79 ///
80 /// This is ported almost directly from iOS. On iOS, the `ThreeWayMerger` takes
81 /// a complete "mirror" tree with the server state after the last sync, and two
82 /// incomplete trees with local and remote changes to the mirror: "local" and
83 /// "mirror", respectively. Overlaying buffer onto mirror yields the current
84 /// server tree; overlaying local onto mirror yields the complete local tree.
85 ///
86 /// Dogear doesn't store the shared parent for changed items, so we can only
87 /// do two-way merges. Our local tree is the union of iOS's mirror and local,
88 /// and our remote tree is the union of iOS's mirror and buffer.
89 ///
90 /// Unlike iOS, Dogear doesn't distinguish between structure and value changes.
91 /// The `needs_merge` flag notes *that* a bookmark changed, but not *how*. This
92 /// means we might detect conflicts, and revert changes on one side, for cases
93 /// that iOS can merge cleanly.
94 ///
95 /// Fortunately, most of our users don't organize their bookmarks into deeply
96 /// nested hierarchies, or make conflicting changes on multiple devices
97 /// simultaneously. A simpler two-way tree merge strikes a good balance between
98 /// correctness and complexity.
99 pub struct Merger<'t, D = DefaultDriver, A = DefaultAbortSignal> {
100 driver: &'t D,
101 signal: &'t A,
102 local_tree: &'t Tree,
103 remote_tree: &'t Tree,
104 matching_dupes_by_local_parent_guid: HashMap<Guid, MatchingDupes<'t>>,
105 merged_guids: HashSet<Guid>,
106 delete_locally: HashSet<Guid>,
107 delete_remotely: HashSet<Guid>,
108 structure_counts: StructureCounts,
109 }
110
111 impl<'t> Merger<'t, DefaultDriver, DefaultAbortSignal> {
112 /// Creates a merger with the default merge driver.
new(local_tree: &'t Tree, remote_tree: &'t Tree) -> Merger<'t>113 pub fn new(local_tree: &'t Tree, remote_tree: &'t Tree) -> Merger<'t> {
114 Merger {
115 driver: &DefaultDriver,
116 signal: &DefaultAbortSignal,
117 local_tree,
118 remote_tree,
119 matching_dupes_by_local_parent_guid: HashMap::new(),
120 merged_guids: HashSet::new(),
121 delete_locally: HashSet::new(),
122 delete_remotely: HashSet::new(),
123 structure_counts: StructureCounts::default(),
124 }
125 }
126 }
127
128 impl<'t, D: Driver, A: AbortSignal> Merger<'t, D, A> {
129 /// Creates a merger with the given merge driver and contents.
with_driver( driver: &'t D, signal: &'t A, local_tree: &'t Tree, remote_tree: &'t Tree, ) -> Merger<'t, D, A>130 pub fn with_driver(
131 driver: &'t D,
132 signal: &'t A,
133 local_tree: &'t Tree,
134 remote_tree: &'t Tree,
135 ) -> Merger<'t, D, A> {
136 Merger {
137 driver,
138 signal,
139 local_tree,
140 remote_tree,
141 matching_dupes_by_local_parent_guid: HashMap::new(),
142 merged_guids: HashSet::new(),
143 delete_locally: HashSet::new(),
144 delete_remotely: HashSet::new(),
145 structure_counts: StructureCounts::default(),
146 }
147 }
148
149 /// Builds a merged tree from the local and remote trees.
merge(mut self) -> Result<MergedRoot<'t>>150 pub fn merge(mut self) -> Result<MergedRoot<'t>> {
151 let merged_root_node = {
152 let local_root_node = self.local_tree.root();
153 let remote_root_node = self.remote_tree.root();
154 self.two_way_merge(local_root_node, remote_root_node)?
155 };
156
157 // Any remaining deletions on one side should be deleted on the other side.
158 // This happens when the remote tree has tombstones for items that don't
159 // exist locally, or the local tree has tombstones for items that
160 // aren't on the server.
161 for guid in self.local_tree.deletions() {
162 self.signal.err_if_aborted()?;
163 if !self.mentions(guid) {
164 self.delete_remotely.insert(guid.clone());
165 }
166 }
167 for guid in self.remote_tree.deletions() {
168 self.signal.err_if_aborted()?;
169 if !self.mentions(guid) {
170 self.delete_locally.insert(guid.clone());
171 }
172 }
173
174 // The merged tree should know about all items mentioned in the local
175 // and remote trees. Otherwise, it's incomplete, and we can't apply it.
176 // This indicates a bug in the merger.
177 for guid in self.local_tree.guids() {
178 self.signal.err_if_aborted()?;
179 if !self.mentions(guid) {
180 return Err(ErrorKind::UnmergedLocalItems.into());
181 }
182 }
183 for guid in self.remote_tree.guids() {
184 self.signal.err_if_aborted()?;
185 if !self.mentions(guid) {
186 return Err(ErrorKind::UnmergedRemoteItems.into());
187 }
188 }
189
190 Ok(MergedRoot {
191 local_tree: self.local_tree,
192 remote_tree: self.remote_tree,
193 node: merged_root_node,
194 merged_guids: self.merged_guids,
195 delete_locally: self.delete_locally,
196 delete_remotely: self.delete_remotely,
197 structure_counts: self.structure_counts,
198 })
199 }
200
201 #[inline]
mentions(&self, guid: &Guid) -> bool202 fn mentions(&self, guid: &Guid) -> bool {
203 self.merged_guids.contains(guid)
204 || self.delete_locally.contains(guid)
205 || self.delete_remotely.contains(guid)
206 }
207
merge_local_only_node(&mut self, local_node: Node<'t>) -> Result<MergedNode<'t>>208 fn merge_local_only_node(&mut self, local_node: Node<'t>) -> Result<MergedNode<'t>> {
209 trace!(self.driver, "Item {} only exists locally", local_node);
210
211 self.merged_guids.insert(local_node.guid.clone());
212
213 let merged_guid = if local_node.guid.is_valid_guid() {
214 local_node.guid.clone()
215 } else {
216 warn!(
217 self.driver,
218 "Generating new GUID for local node {}", local_node
219 );
220 self.signal.err_if_aborted()?;
221 let new_guid = self.driver.generate_new_guid(&local_node.guid)?;
222 if new_guid != local_node.guid {
223 if self.merged_guids.contains(&new_guid) {
224 return Err(ErrorKind::DuplicateItem(new_guid).into());
225 }
226 self.merged_guids.insert(new_guid.clone());
227 }
228 new_guid
229 };
230
231 let mut merged_node = MergedNode::new(merged_guid, MergeState::LocalOnly(local_node));
232 // The local folder doesn't exist remotely, but its children might, so
233 // we still need to recursively walk and merge them. This method will
234 // change the merge state from local to new if any children were moved
235 // or deleted.
236 for local_child_node in local_node.children() {
237 self.signal.err_if_aborted()?;
238 self.merge_local_child_into_merged_node(
239 &mut merged_node,
240 local_node,
241 None,
242 local_child_node,
243 )?;
244 }
245
246 if local_node.diverged() {
247 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
248 }
249
250 Ok(merged_node)
251 }
252
merge_remote_only_node(&mut self, remote_node: Node<'t>) -> Result<MergedNode<'t>>253 fn merge_remote_only_node(&mut self, remote_node: Node<'t>) -> Result<MergedNode<'t>> {
254 trace!(self.driver, "Item {} only exists remotely", remote_node);
255
256 self.merged_guids.insert(remote_node.guid.clone());
257
258 let merged_guid = if remote_node.guid.is_valid_guid() {
259 remote_node.guid.clone()
260 } else {
261 warn!(
262 self.driver,
263 "Generating new GUID for remote node {}", remote_node
264 );
265 self.signal.err_if_aborted()?;
266 let new_guid = self.driver.generate_new_guid(&remote_node.guid)?;
267 if new_guid != remote_node.guid {
268 if self.merged_guids.contains(&new_guid) {
269 return Err(ErrorKind::DuplicateItem(new_guid).into());
270 }
271 self.merged_guids.insert(new_guid.clone());
272 // Upload tombstones for changed remote GUIDs.
273 self.delete_remotely.insert(remote_node.guid.clone());
274 }
275 new_guid
276 };
277 let mut merged_node = MergedNode::new(merged_guid, MergeState::RemoteOnly(remote_node));
278 // As above, a remote folder's children might still exist locally, so we
279 // need to merge them and update the merge state from remote to new if
280 // any children were moved or deleted.
281 for remote_child_node in remote_node.children() {
282 self.signal.err_if_aborted()?;
283 self.merge_remote_child_into_merged_node(
284 &mut merged_node,
285 None,
286 remote_node,
287 remote_child_node,
288 )?;
289 }
290
291 if remote_node.diverged()
292 || merged_node.remote_guid_changed()
293 || remote_node.validity != Validity::Valid
294 {
295 // If the remote structure diverged, the merged item's GUID changed,
296 // or the item isn't valid, flag it for reupload.
297 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
298 }
299
300 Ok(merged_node)
301 }
302
303 /// Merges two nodes that exist locally and remotely.
two_way_merge( &mut self, local_node: Node<'t>, remote_node: Node<'t>, ) -> Result<MergedNode<'t>>304 fn two_way_merge(
305 &mut self,
306 local_node: Node<'t>,
307 remote_node: Node<'t>,
308 ) -> Result<MergedNode<'t>> {
309 trace!(
310 self.driver,
311 "Item exists locally as {} and remotely as {}",
312 local_node,
313 remote_node
314 );
315
316 if !local_node.has_compatible_kind(&remote_node) {
317 error!(
318 self.driver,
319 "Merging local {} and remote {} with different kinds", local_node, remote_node
320 );
321 return Err(ErrorKind::MismatchedItemKind(local_node.kind, remote_node.kind).into());
322 }
323
324 self.merged_guids.insert(local_node.guid.clone());
325 self.merged_guids.insert(remote_node.guid.clone());
326
327 let merged_guid = if remote_node.guid.is_valid_guid() {
328 remote_node.guid.clone()
329 } else {
330 warn!(
331 self.driver,
332 "Generating new valid GUID for node {}", remote_node
333 );
334 self.signal.err_if_aborted()?;
335 let new_guid = self.driver.generate_new_guid(&remote_node.guid)?;
336 if new_guid != remote_node.guid {
337 if self.merged_guids.contains(&new_guid) {
338 return Err(ErrorKind::DuplicateItem(new_guid).into());
339 }
340 self.merged_guids.insert(new_guid.clone());
341 // Upload tombstones for changed remote GUIDs.
342 self.delete_remotely.insert(remote_node.guid.clone());
343 }
344 new_guid
345 };
346
347 let (item, children) = self.resolve_value_conflict(local_node, remote_node);
348
349 let mut merged_node = MergedNode::new(
350 merged_guid,
351 match item {
352 ConflictResolution::Local => MergeState::Local {
353 local_node,
354 remote_node,
355 },
356 ConflictResolution::Remote => MergeState::Remote {
357 local_node,
358 remote_node,
359 },
360 ConflictResolution::Unchanged => MergeState::Unchanged {
361 local_node,
362 remote_node,
363 },
364 },
365 );
366
367 match children {
368 ConflictResolution::Local => {
369 for local_child_node in local_node.children() {
370 self.signal.err_if_aborted()?;
371 self.merge_local_child_into_merged_node(
372 &mut merged_node,
373 local_node,
374 Some(remote_node),
375 local_child_node,
376 )?;
377 }
378 for remote_child_node in remote_node.children() {
379 self.signal.err_if_aborted()?;
380 self.merge_remote_child_into_merged_node(
381 &mut merged_node,
382 Some(local_node),
383 remote_node,
384 remote_child_node,
385 )?;
386 }
387 }
388
389 ConflictResolution::Remote => {
390 for remote_child_node in remote_node.children() {
391 self.signal.err_if_aborted()?;
392 self.merge_remote_child_into_merged_node(
393 &mut merged_node,
394 Some(local_node),
395 remote_node,
396 remote_child_node,
397 )?;
398 }
399 for local_child_node in local_node.children() {
400 self.signal.err_if_aborted()?;
401 self.merge_local_child_into_merged_node(
402 &mut merged_node,
403 local_node,
404 Some(remote_node),
405 local_child_node,
406 )?;
407 }
408 }
409
410 ConflictResolution::Unchanged => {
411 // The children are the same, so we only need to merge one side.
412 for (local_child_node, remote_child_node) in
413 local_node.children().zip(remote_node.children())
414 {
415 self.signal.err_if_aborted()?;
416 self.merge_unchanged_child_into_merged_node(
417 &mut merged_node,
418 local_node,
419 local_child_node,
420 remote_node,
421 remote_child_node,
422 )?;
423 }
424 }
425 }
426
427 if local_node.diverged() {
428 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
429 }
430
431 if remote_node.diverged() || remote_node.validity != Validity::Valid {
432 // Flag remotely diverged and invalid items for reupload.
433 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
434 }
435
436 Ok(merged_node)
437 }
438
439 /// Merges two nodes with the same parents and positions.
440 ///
441 /// Unlike items that have been moved, or exist only on one side, unchanged
442 /// children can be merged directly.
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<()>443 fn merge_unchanged_child_into_merged_node(
444 &mut self,
445 merged_node: &mut MergedNode<'t>,
446 local_parent_node: Node<'t>,
447 local_child_node: Node<'t>,
448 remote_parent_node: Node<'t>,
449 remote_child_node: Node<'t>,
450 ) -> Result<()> {
451 assert!(
452 !self.merged_guids.contains(&local_child_node.guid),
453 "Unchanged local child shouldn't have been merged"
454 );
455 assert!(
456 !self.merged_guids.contains(&remote_child_node.guid),
457 "Unchanged remote child shouldn't have been merged"
458 );
459
460 // Even though the child exists on both sides, it might still be
461 // non-syncable or invalid, so we need to check for structure
462 // changes.
463 let local_structure_change = self.check_for_local_structure_change_of_remote_node(
464 merged_node,
465 remote_parent_node,
466 remote_child_node,
467 )?;
468 let remote_structure_change = self.check_for_remote_structure_change_of_local_node(
469 merged_node,
470 local_parent_node,
471 local_child_node,
472 )?;
473 match (local_structure_change, remote_structure_change) {
474 (StructureChange::Deleted, StructureChange::Deleted) => {
475 // The child is deleted on both sides. We'll need to reupload
476 // and apply a new structure.
477 merged_node.merge_state = merged_node
478 .merge_state
479 .with_new_local_structure()
480 .with_new_remote_structure();
481 }
482 (StructureChange::Deleted, _) => {
483 // The child is deleted locally, but not remotely, so we only
484 // need to reupload a new structure.
485 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
486 }
487 (_, StructureChange::Deleted) => {
488 // The child is deleted remotely, so we only need to apply a
489 // new local structure.
490 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
491 }
492 (_, _) => {
493 // The child exists on both sides, so merge it now. If the GUID
494 // changes because it's invalid, we'll need to reapply the
495 // child, and reupload the child and its parent.
496 let mut merged_child_node =
497 self.two_way_merge(local_child_node, remote_child_node)?;
498 if merged_child_node.local_guid_changed() {
499 merged_child_node.merge_state =
500 merged_child_node.merge_state.with_new_local_structure();
501 }
502 if merged_node.remote_guid_changed() {
503 // The merged parent's GUID changed; flag the child for
504 // reupload with a new `parentid`.
505 merged_child_node.merge_state =
506 merged_child_node.merge_state.with_new_remote_structure();
507 }
508 if merged_child_node.remote_guid_changed() {
509 // The merged child's GUID changed; flag the parent for
510 // reupload with new `children`.
511 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
512 }
513 merged_node.merged_children.push(merged_child_node);
514 self.structure_counts.merged_nodes += 1;
515 }
516 }
517
518 Ok(())
519 }
520
521 /// Merges a remote child node into a merged folder node. This handles the
522 /// following cases:
523 ///
524 /// - The remote child is locally deleted. We recursively move all of its
525 /// descendants that don't exist locally to the merged folder.
526 /// - The remote child doesn't exist locally, but has a content match in the
527 /// corresponding local folder. We dedupe the local child to the remote
528 /// child.
529 /// - The remote child exists locally, but in a different folder. We compare
530 /// merge flags and timestamps to decide where to keep the child.
531 /// - The remote child exists locally, and in the same folder. We merge the
532 /// local and remote children.
533 ///
534 /// This is the inverse of `merge_local_child_into_merged_node`.
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<()>535 fn merge_remote_child_into_merged_node(
536 &mut self,
537 merged_node: &mut MergedNode<'t>,
538 local_parent_node: Option<Node<'t>>,
539 remote_parent_node: Node<'t>,
540 remote_child_node: Node<'t>,
541 ) -> Result<()> {
542 if self.merged_guids.contains(&remote_child_node.guid) {
543 trace!(
544 self.driver,
545 "Remote child {} already seen in another folder and merged",
546 remote_child_node
547 );
548 // Omitting a remote child that we already merged locally means we
549 // have a new remote structure.
550 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
551 return Ok(());
552 }
553
554 trace!(
555 self.driver,
556 "Merging remote child {} of {} into {}",
557 remote_child_node,
558 remote_parent_node,
559 merged_node
560 );
561
562 // Check if the remote child is locally deleted. and move all
563 // descendants that aren't also remotely deleted to the merged node.
564 // This handles the case where a user deletes a folder on this device,
565 // and adds a bookmark to the same folder on another device. We want to
566 // keep the folder deleted, but we also don't want to lose the new
567 // bookmark, so we move the bookmark to the deleted folder's parent.
568 if self.check_for_local_structure_change_of_remote_node(
569 merged_node,
570 remote_parent_node,
571 remote_child_node,
572 )? == StructureChange::Deleted
573 {
574 // Flag the merged parent for reupload, since we deleted the
575 // remote child.
576 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
577 return Ok(());
578 }
579
580 // The remote child isn't locally deleted. Does it exist in the local tree?
581 if let Some(local_child_node) = self.local_tree.node_for_guid(&remote_child_node.guid) {
582 // The remote child exists in the local tree. Did it move?
583 let local_parent_node = local_child_node
584 .parent()
585 .expect("Can't merge existing remote child without local parent");
586
587 trace!(
588 self.driver,
589 "Remote child {} exists locally in {} and remotely in {}",
590 remote_child_node,
591 local_parent_node,
592 remote_parent_node
593 );
594
595 if self.remote_tree.is_deleted(&local_parent_node.guid) {
596 trace!(
597 self.driver,
598 "Unconditionally taking remote move for {} to {} because local parent {} is \
599 deleted remotely",
600 remote_child_node,
601 remote_parent_node,
602 local_parent_node
603 );
604
605 let mut merged_child_node =
606 self.two_way_merge(local_child_node, remote_child_node)?;
607 merged_child_node.merge_state =
608 merged_child_node.merge_state.with_new_local_structure();
609 if merged_node.remote_guid_changed() {
610 // If the parent's GUID changed, flag the child for reupload, so that
611 // its `parentid` is correct.
612 merged_child_node.merge_state =
613 merged_child_node.merge_state.with_new_remote_structure();
614 }
615 if merged_child_node.remote_guid_changed() {
616 // If the child's GUID changed, flag the parent for reupload, so that
617 // its `children` are correct.
618 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
619 }
620 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
621 merged_node.merged_children.push(merged_child_node);
622 self.structure_counts.merged_nodes += 1;
623 return Ok(());
624 }
625
626 match self.resolve_structure_conflict(
627 local_parent_node,
628 local_child_node,
629 remote_parent_node,
630 remote_child_node,
631 ) {
632 ConflictResolution::Local => {
633 // The local move is newer, so we ignore the remote move.
634 // We'll merge the remote child later, when we walk its new
635 // local parent.
636 trace!(
637 self.driver,
638 "Remote child {} moved locally to {} and remotely to {}; \
639 keeping child in newer local parent and position",
640 remote_child_node,
641 local_parent_node,
642 remote_parent_node
643 );
644
645 // Flag the old parent for reupload, since we're moving
646 // the remote child. Note that, since we only flag the
647 // remote parent here, we don't need to handle
648 // reparenting and repositioning separately.
649 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
650 }
651
652 ConflictResolution::Remote | ConflictResolution::Unchanged => {
653 // The remote move is newer, so we merge the remote
654 // child now and ignore the local move.
655 let mut merged_child_node = if local_parent_node.guid != remote_parent_node.guid
656 {
657 trace!(
658 self.driver,
659 "Remote child {} reparented locally to {} and remotely to {}; \
660 keeping child in newer remote parent",
661 remote_child_node,
662 local_parent_node,
663 remote_parent_node
664 );
665 let mut merged_child_node =
666 self.two_way_merge(local_child_node, remote_child_node)?;
667 merged_child_node.merge_state =
668 merged_child_node.merge_state.with_new_local_structure();
669 merged_child_node
670 } else {
671 trace!(
672 self.driver,
673 "Remote child {} repositioned locally in {} and remotely in {}; \
674 keeping child in newer remote position",
675 remote_child_node,
676 local_parent_node,
677 remote_parent_node
678 );
679 self.two_way_merge(local_child_node, remote_child_node)?
680 };
681 if merged_child_node.local_guid_changed() {
682 merged_child_node.merge_state =
683 merged_child_node.merge_state.with_new_local_structure();
684 }
685 if merged_node.remote_guid_changed() {
686 // The merged parent's GUID changed; flag the child for
687 // reupload with a new `parentid`.
688 merged_child_node.merge_state =
689 merged_child_node.merge_state.with_new_remote_structure();
690 }
691 if merged_child_node.remote_guid_changed() {
692 // The merged child's GUID changed; flag the parent for
693 // reupload with new `children`.
694 merged_node.merge_state =
695 merged_node.merge_state.with_new_remote_structure();
696 }
697 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
698 merged_node.merged_children.push(merged_child_node);
699 self.structure_counts.merged_nodes += 1;
700 }
701 }
702
703 return Ok(());
704 }
705
706 // Remote child is not a root, and doesn't exist locally. Try to find a
707 // content match in the containing folder, and dedupe the local item if
708 // we can.
709 trace!(
710 self.driver,
711 "Remote child {} doesn't exist locally; looking for local content match",
712 remote_child_node
713 );
714
715 let mut merged_child_node = if let Some(local_child_node_by_content) = self
716 .find_local_node_matching_remote_node(
717 merged_node,
718 local_parent_node,
719 remote_parent_node,
720 remote_child_node,
721 )? {
722 self.two_way_merge(local_child_node_by_content, remote_child_node)
723 } else {
724 self.merge_remote_only_node(remote_child_node)
725 }?;
726 if merged_child_node.local_guid_changed() {
727 merged_child_node.merge_state =
728 merged_child_node.merge_state.with_new_local_structure();
729 }
730 if merged_node.remote_guid_changed() {
731 merged_child_node.merge_state =
732 merged_child_node.merge_state.with_new_remote_structure();
733 }
734 if merged_child_node.remote_guid_changed() {
735 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
736 }
737 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
738 merged_node.merged_children.push(merged_child_node);
739 self.structure_counts.merged_nodes += 1;
740 Ok(())
741 }
742
743 /// Merges a local child node into a merged folder node.
744 ///
745 /// This is the inverse of `merge_remote_child_into_merged_node`.
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<()>746 fn merge_local_child_into_merged_node(
747 &mut self,
748 merged_node: &mut MergedNode<'t>,
749 local_parent_node: Node<'t>,
750 remote_parent_node: Option<Node<'t>>,
751 local_child_node: Node<'t>,
752 ) -> Result<()> {
753 if self.merged_guids.contains(&local_child_node.guid) {
754 // We already merged the child when we walked another folder. Since
755 // a tree can't have duplicate GUIDs, we must have merged the remote
756 // child, so we have a new local structure.
757 trace!(
758 self.driver,
759 "Local child {} already seen in another folder and merged",
760 local_child_node
761 );
762 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
763 return Ok(());
764 }
765
766 trace!(
767 self.driver,
768 "Merging local child {} of {} into {}",
769 local_child_node,
770 local_parent_node,
771 merged_node
772 );
773
774 // Check if the local child is remotely deleted, and move any new local
775 // descendants to the merged node if so.
776 if self.check_for_remote_structure_change_of_local_node(
777 merged_node,
778 local_parent_node,
779 local_child_node,
780 )? == StructureChange::Deleted
781 {
782 // Since we're merging local nodes, we don't need to flag the merged
783 // parent for reupload.
784 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
785 return Ok(());
786 }
787
788 // At this point, we know the local child isn't deleted. See if it
789 // exists in the remote tree.
790 if let Some(remote_child_node) = self.remote_tree.node_for_guid(&local_child_node.guid) {
791 // The local child exists remotely. It must have moved; otherwise, we
792 // would have seen it when we walked the remote children.
793 let remote_parent_node = remote_child_node
794 .parent()
795 .expect("Can't merge existing local child without remote parent");
796
797 trace!(
798 self.driver,
799 "Local child {} exists locally in {} and remotely in {}",
800 local_child_node,
801 local_parent_node,
802 remote_parent_node
803 );
804
805 if self.local_tree.is_deleted(&remote_parent_node.guid) {
806 trace!(
807 self.driver,
808 "Unconditionally taking local move for {} to {} because remote parent {} is \
809 deleted locally",
810 local_child_node,
811 local_parent_node,
812 remote_parent_node
813 );
814
815 // Merge and flag the new parent *and the locally moved child* for
816 // reupload. The parent references the child in its `children`; the
817 // child points back to the parent in its `parentid`.
818 //
819 // Reuploading the child isn't necessary for newer Desktops, which
820 // ignore the child's `parentid` and use the parent's `children`.
821 //
822 // However, older Desktop and Android use the child's `parentid` as
823 // canonical, while iOS is stricter and requires both to match.
824 let mut merged_child_node =
825 self.two_way_merge(local_child_node, remote_child_node)?;
826 if merged_child_node.local_guid_changed() {
827 merged_child_node.merge_state =
828 merged_child_node.merge_state.with_new_local_structure();
829 }
830 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
831 merged_child_node.merge_state =
832 merged_child_node.merge_state.with_new_remote_structure();
833 merged_node.merged_children.push(merged_child_node);
834 self.structure_counts.merged_nodes += 1;
835 return Ok(());
836 }
837
838 match self.resolve_structure_conflict(
839 local_parent_node,
840 local_child_node,
841 remote_parent_node,
842 remote_child_node,
843 ) {
844 ConflictResolution::Local => {
845 // The local move is newer, so we merge the local child now
846 // and ignore the remote move.
847 if local_parent_node.guid != remote_parent_node.guid {
848 // The child moved to a different folder.
849 trace!(
850 self.driver,
851 "Local child {} reparented locally to {} and remotely to {}; \
852 keeping child in newer local parent",
853 local_child_node,
854 local_parent_node,
855 remote_parent_node
856 );
857
858 // Merge and flag both the new parent and child for
859 // reupload. See above for why.
860 let mut merged_child_node =
861 self.two_way_merge(local_child_node, remote_child_node)?;
862 if merged_child_node.local_guid_changed() {
863 merged_child_node.merge_state =
864 merged_child_node.merge_state.with_new_local_structure();
865 }
866 merged_node.merge_state =
867 merged_node.merge_state.with_new_remote_structure();
868 merged_child_node.merge_state =
869 merged_child_node.merge_state.with_new_remote_structure();
870 merged_node.merged_children.push(merged_child_node);
871 self.structure_counts.merged_nodes += 1;
872 } else {
873 trace!(
874 self.driver,
875 "Local child {} repositioned locally in {} and remotely in {}; \
876 keeping child in newer local position",
877 local_child_node,
878 local_parent_node,
879 remote_parent_node
880 );
881
882 // For position changes in the same folder, we only need to
883 // merge and flag the parent for reupload...
884 let mut merged_child_node =
885 self.two_way_merge(local_child_node, remote_child_node)?;
886 if merged_child_node.local_guid_changed() {
887 merged_child_node.merge_state =
888 merged_child_node.merge_state.with_new_local_structure();
889 }
890 merged_node.merge_state =
891 merged_node.merge_state.with_new_remote_structure();
892 if merged_node.remote_guid_changed() {
893 // ...Unless the merged parent's GUID also changed,
894 // in which case we also need to flag the
895 // repositioned child for reupload, so that its
896 // `parentid` is correct.
897 merged_child_node.merge_state =
898 merged_child_node.merge_state.with_new_remote_structure();
899 }
900
901 merged_node.merged_children.push(merged_child_node);
902 self.structure_counts.merged_nodes += 1;
903 }
904 }
905
906 ConflictResolution::Remote | ConflictResolution::Unchanged => {
907 // The remote move is newer, so we ignore the local
908 // move. We'll merge the local child later, when we
909 // walk its new remote parent.
910 if local_parent_node.guid != remote_parent_node.guid {
911 trace!(
912 self.driver,
913 "Local child {} reparented locally to {} and remotely to {}; \
914 keeping child in newer remote parent",
915 local_child_node,
916 local_parent_node,
917 remote_parent_node
918 );
919 } else {
920 trace!(
921 self.driver,
922 "Local child {} repositioned locally in {} and remotely in {}; \
923 keeping child in newer remote position",
924 local_child_node,
925 local_parent_node,
926 remote_parent_node
927 );
928 }
929 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
930 }
931 }
932
933 return Ok(());
934 }
935
936 // Local child is not a root, and doesn't exist remotely. Try to find a
937 // content match in the containing folder, and dedupe the local item if
938 // we can.
939 trace!(
940 self.driver,
941 "Local child {} doesn't exist remotely; looking for remote content match",
942 local_child_node
943 );
944
945 let merged_child_node = if let Some(remote_child_node_by_content) = self
946 .find_remote_node_matching_local_node(
947 merged_node,
948 local_parent_node,
949 remote_parent_node,
950 local_child_node,
951 )? {
952 // The local child has a remote content match, so take the remote GUID
953 // and merge.
954 let mut merged_child_node =
955 self.two_way_merge(local_child_node, remote_child_node_by_content)?;
956 if merged_child_node.local_guid_changed() {
957 merged_child_node.merge_state =
958 merged_child_node.merge_state.with_new_local_structure();
959 }
960 if merged_node.remote_guid_changed() {
961 merged_child_node.merge_state =
962 merged_child_node.merge_state.with_new_remote_structure();
963 }
964 if merged_child_node.remote_guid_changed() {
965 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
966 }
967 merged_node.merge_state = merged_node.merge_state.with_new_local_structure();
968 merged_child_node
969 } else {
970 // The local child doesn't exist remotely, so flag the merged parent and
971 // new child for upload, and walk its descendants.
972 let mut merged_child_node = self.merge_local_only_node(local_child_node)?;
973 if merged_child_node.local_guid_changed() {
974 merged_child_node.merge_state =
975 merged_child_node.merge_state.with_new_local_structure();
976 }
977 merged_node.merge_state = merged_node.merge_state.with_new_remote_structure();
978 merged_child_node.merge_state =
979 merged_child_node.merge_state.with_new_remote_structure();
980 merged_child_node
981 };
982 merged_node.merged_children.push(merged_child_node);
983 self.structure_counts.merged_nodes += 1;
984 Ok(())
985 }
986
987 /// Determines which side to prefer, and which children to merge first,
988 /// for an item that exists on both sides.
resolve_value_conflict( &self, local_node: Node<'t>, remote_node: Node<'t>, ) -> (ConflictResolution, ConflictResolution)989 fn resolve_value_conflict(
990 &self,
991 local_node: Node<'t>,
992 remote_node: Node<'t>,
993 ) -> (ConflictResolution, ConflictResolution) {
994 if remote_node.is_root() {
995 // Don't touch the Places root; it's not synced, anyway.
996 return (ConflictResolution::Unchanged, ConflictResolution::Local);
997 }
998
999 match (local_node.needs_merge, remote_node.needs_merge) {
1000 (true, true) => {
1001 // The item changed locally and remotely.
1002 let item = if local_node.is_built_in_root() {
1003 // For roots, we always prefer the local side for item
1004 // changes, like the title (bug 1432614).
1005 ConflictResolution::Local
1006 } else {
1007 // For other items, we check the validity to decide
1008 // which side to take.
1009 match (local_node.validity, remote_node.validity) {
1010 // If both are invalid, it doesn't matter which side
1011 // we pick; the item will be deleted, anyway.
1012 (Validity::Replace, Validity::Replace) => ConflictResolution::Unchanged,
1013 // If only one side is invalid, pick the other side.
1014 // This loses changes from that side, but we can't
1015 // apply or upload those changes, anyway.
1016 (Validity::Replace, _) => ConflictResolution::Remote,
1017 (_, Validity::Replace) => ConflictResolution::Local,
1018 (_, _) => {
1019 // Otherwise, the item is either valid, or valid
1020 // but needs to be reuploaded or reapplied, so
1021 // compare timestamps to decide which side is newer.
1022 if local_node.age < remote_node.age {
1023 ConflictResolution::Local
1024 } else {
1025 ConflictResolution::Remote
1026 }
1027 }
1028 }
1029 };
1030 // For children, it's easier: we always use the newer side, even
1031 // if we're taking local changes for the item.
1032 let children = if local_node.has_matching_children(remote_node) {
1033 ConflictResolution::Unchanged
1034 } else if local_node.age < remote_node.age {
1035 // The local change is newer, so merge local children first,
1036 // followed by remaining unmerged remote children.
1037 ConflictResolution::Local
1038 } else {
1039 // The remote change is newer, so walk and merge remote
1040 // children first, then remaining local children.
1041 ConflictResolution::Remote
1042 };
1043 (item, children)
1044 }
1045
1046 (true, false) => {
1047 // The item changed locally, but not remotely. Prefer the local
1048 // item, then merge local children first, followed by remote
1049 // children.
1050 let item = match local_node.validity {
1051 Validity::Valid | Validity::Reupload => ConflictResolution::Local,
1052 Validity::Replace => ConflictResolution::Remote,
1053 };
1054 let children = if local_node.has_matching_children(remote_node) {
1055 ConflictResolution::Unchanged
1056 } else {
1057 ConflictResolution::Local
1058 };
1059 (item, children)
1060 }
1061
1062 (false, true) => {
1063 // The item changed remotely, but not locally.
1064 let item = if local_node.is_built_in_root() {
1065 // For roots, we ignore remote item changes.
1066 ConflictResolution::Unchanged
1067 } else {
1068 match remote_node.validity {
1069 Validity::Valid | Validity::Reupload => ConflictResolution::Remote,
1070 // And, for invalid remote items, we must reupload the
1071 // local side. This _loses remote changes_, but we can't
1072 // apply those changes, anyway.
1073 Validity::Replace => ConflictResolution::Local,
1074 }
1075 };
1076 let children = if local_node.has_matching_children(remote_node) {
1077 ConflictResolution::Unchanged
1078 } else {
1079 ConflictResolution::Remote
1080 };
1081 // For children, we always use the remote side.
1082 (item, children)
1083 }
1084
1085 (false, false) => {
1086 let item = match (local_node.validity, remote_node.validity) {
1087 (Validity::Replace, Validity::Replace) => ConflictResolution::Unchanged,
1088 (_, Validity::Replace) => ConflictResolution::Local,
1089 (Validity::Replace, _) => ConflictResolution::Remote,
1090 (_, _) => ConflictResolution::Unchanged,
1091 };
1092 // If the child lists are identical, the structure is unchanged.
1093 // Otherwise, the children differ even though the items aren't
1094 // flagged as unmerged, so we prefer the newer side.
1095 let children = if local_node.has_matching_children(remote_node) {
1096 ConflictResolution::Unchanged
1097 } else if local_node.age < remote_node.age {
1098 ConflictResolution::Local
1099 } else {
1100 ConflictResolution::Remote
1101 };
1102 (item, children)
1103 }
1104 }
1105 }
1106
1107 /// Determines where to keep a child of a folder that exists on both sides.
resolve_structure_conflict( &self, local_parent_node: Node<'t>, local_child_node: Node<'t>, remote_parent_node: Node<'t>, remote_child_node: Node<'t>, ) -> ConflictResolution1108 fn resolve_structure_conflict(
1109 &self,
1110 local_parent_node: Node<'t>,
1111 local_child_node: Node<'t>,
1112 remote_parent_node: Node<'t>,
1113 remote_child_node: Node<'t>,
1114 ) -> ConflictResolution {
1115 if remote_child_node.is_built_in_root() {
1116 // Always use the local parent and position for roots.
1117 return ConflictResolution::Local;
1118 }
1119
1120 match (
1121 local_parent_node.needs_merge,
1122 remote_parent_node.needs_merge,
1123 ) {
1124 (true, true) => {
1125 // If both parents changed, compare timestamps to decide where
1126 // to keep the local child.
1127 let latest_local_age = local_child_node.age.min(local_parent_node.age);
1128 let latest_remote_age = remote_child_node.age.min(remote_parent_node.age);
1129
1130 if latest_local_age < latest_remote_age {
1131 ConflictResolution::Local
1132 } else {
1133 ConflictResolution::Remote
1134 }
1135 }
1136
1137 // If only the local or remote parent changed, keep the child in its
1138 // new parent.
1139 (true, false) => ConflictResolution::Local,
1140 (false, true) => ConflictResolution::Remote,
1141
1142 (false, false) => ConflictResolution::Unchanged,
1143 }
1144 }
1145
1146 /// Checks if a remote node is locally moved or deleted, and reparents any
1147 /// descendants that aren't also remotely deleted to the merged node.
1148 ///
1149 /// This is the inverse of
1150 /// `check_for_remote_structure_change_of_local_node`.
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>1151 fn check_for_local_structure_change_of_remote_node(
1152 &mut self,
1153 merged_node: &mut MergedNode<'t>,
1154 remote_parent_node: Node<'t>,
1155 remote_node: Node<'t>,
1156 ) -> Result<StructureChange> {
1157 if !remote_node.is_syncable() {
1158 // If the remote node is known to be non-syncable, we unconditionally
1159 // delete it, even if it's syncable or moved locally.
1160 trace!(
1161 self.driver,
1162 "Deleting non-syncable remote node {}",
1163 remote_node
1164 );
1165 return self.delete_remote_node(merged_node, remote_node);
1166 }
1167
1168 if !self.local_tree.is_deleted(&remote_node.guid) {
1169 if let Some(local_node) = self.local_tree.node_for_guid(&remote_node.guid) {
1170 if !local_node.is_syncable() {
1171 // The remote node is syncable, but the local node is
1172 // non-syncable. Unconditionally delete it.
1173 trace!(
1174 self.driver,
1175 "Remote node {} is syncable, but local node {} isn't; deleting",
1176 remote_node,
1177 local_node
1178 );
1179 return self.delete_remote_node(merged_node, remote_node);
1180 }
1181 if local_node.validity == Validity::Replace
1182 && remote_node.validity == Validity::Replace
1183 {
1184 // The nodes are invalid on both sides, so we can't apply
1185 // or reupload a valid copy. Delete it.
1186 return self.delete_remote_node(merged_node, remote_node);
1187 }
1188 let local_parent_node = local_node
1189 .parent()
1190 .expect("Can't check for structure changes without local parent");
1191 if local_parent_node.guid != remote_parent_node.guid {
1192 return Ok(StructureChange::Moved);
1193 }
1194 return Ok(StructureChange::Unchanged);
1195 }
1196 if remote_node.validity == Validity::Replace {
1197 // The remote node is invalid and doesn't exist locally, so we
1198 // can't reupload a valid copy. We must delete it.
1199 return self.delete_remote_node(merged_node, remote_node);
1200 }
1201 return Ok(StructureChange::Unchanged);
1202 }
1203
1204 if remote_node.validity == Validity::Replace {
1205 // The remote node is invalid and deleted locally, so we can't
1206 // reupload a valid copy. Delete it.
1207 return self.delete_remote_node(merged_node, remote_node);
1208 }
1209
1210 if remote_node.is_built_in_root() {
1211 // If the remote node is a content root, don't delete it locally.
1212 return Ok(StructureChange::Unchanged);
1213 }
1214
1215 if remote_node.needs_merge {
1216 if !remote_node.is_folder() {
1217 // If a non-folder child is deleted locally and changed remotely, we
1218 // ignore the local deletion and take the remote child.
1219 trace!(
1220 self.driver,
1221 "Remote non-folder {} deleted locally and changed remotely; \
1222 taking remote change",
1223 remote_node
1224 );
1225 self.structure_counts.remote_revives += 1;
1226 return Ok(StructureChange::Unchanged);
1227 }
1228 // For folders, we always take the local deletion and relocate remotely
1229 // changed grandchildren to the merged node. We could use the remote
1230 // tree to revive the child folder, but it's easier to relocate orphaned
1231 // grandchildren than to partially revive the child folder.
1232 trace!(
1233 self.driver,
1234 "Remote folder {} deleted locally and changed remotely; \
1235 taking local deletion",
1236 remote_node
1237 );
1238 self.structure_counts.local_deletes += 1;
1239 } else {
1240 trace!(
1241 self.driver,
1242 "Remote node {} deleted locally and not changed remotely; \
1243 taking local deletion",
1244 remote_node
1245 );
1246 }
1247
1248 // Take the local deletion and relocate any new remote descendants to the
1249 // merged node.
1250 self.delete_remote_node(merged_node, remote_node)
1251 }
1252
1253 /// Checks if a local node is remotely moved or deleted, and reparents any
1254 /// descendants that aren't also locally deleted to the merged node.
1255 ///
1256 /// This is the inverse of
1257 /// `check_for_local_structure_change_of_remote_node`.
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>1258 fn check_for_remote_structure_change_of_local_node(
1259 &mut self,
1260 merged_node: &mut MergedNode<'t>,
1261 local_parent_node: Node<'t>,
1262 local_node: Node<'t>,
1263 ) -> Result<StructureChange> {
1264 if !local_node.is_syncable() {
1265 // If the local node is known to be non-syncable, we unconditionally
1266 // delete it, even if it's syncable or moved remotely.
1267 trace!(
1268 self.driver,
1269 "Deleting non-syncable local node {}",
1270 local_node
1271 );
1272 return self.delete_local_node(merged_node, local_node);
1273 }
1274
1275 if !self.remote_tree.is_deleted(&local_node.guid) {
1276 if let Some(remote_node) = self.remote_tree.node_for_guid(&local_node.guid) {
1277 if !remote_node.is_syncable() {
1278 // The local node is syncable, but the remote node is not.
1279 // This can happen if we applied an orphaned left pane
1280 // query in a previous sync, and later saw the left pane
1281 // root on the server. Since we now have the complete
1282 // subtree, we can remove it.
1283 trace!(
1284 self.driver,
1285 "Local node {} is syncable, but remote node {} isn't; deleting",
1286 local_node,
1287 remote_node
1288 );
1289 return self.delete_local_node(merged_node, local_node);
1290 }
1291 if remote_node.validity == Validity::Replace
1292 && local_node.validity == Validity::Replace
1293 {
1294 // The nodes are invalid on both sides, so we can't replace
1295 // the local copy with a remote one. Delete it.
1296 return self.delete_local_node(merged_node, local_node);
1297 }
1298 // Otherwise, either both nodes are valid; or the remote node
1299 // is invalid but the local node is valid, so we can reupload a
1300 // valid copy.
1301 let remote_parent_node = remote_node
1302 .parent()
1303 .expect("Can't check for structure changes without remote parent");
1304 if remote_parent_node.guid != local_parent_node.guid {
1305 return Ok(StructureChange::Moved);
1306 }
1307 return Ok(StructureChange::Unchanged);
1308 }
1309 if local_node.validity == Validity::Replace {
1310 // The local node is invalid and doesn't exist remotely, so
1311 // we can't replace the local copy. Delete it.
1312 return self.delete_local_node(merged_node, local_node);
1313 }
1314 return Ok(StructureChange::Unchanged);
1315 }
1316
1317 if local_node.validity == Validity::Replace {
1318 // The local node is invalid and deleted remotely, so we can't
1319 // replace the local copy. Delete it.
1320 return self.delete_local_node(merged_node, local_node);
1321 }
1322
1323 if local_node.is_built_in_root() {
1324 // If the local node is a content root, don't delete it remotely.
1325 return Ok(StructureChange::Unchanged);
1326 }
1327
1328 // See `check_for_local_structure_change_of_remote_node` for an
1329 // explanation of how we decide to take or ignore a deletion.
1330 if local_node.needs_merge {
1331 if !local_node.is_folder() {
1332 trace!(
1333 self.driver,
1334 "Local non-folder {} deleted remotely and changed locally; taking local change",
1335 local_node
1336 );
1337 self.structure_counts.local_revives += 1;
1338 return Ok(StructureChange::Unchanged);
1339 }
1340 trace!(
1341 self.driver,
1342 "Local folder {} deleted remotely and changed locally; taking remote deletion",
1343 local_node
1344 );
1345 self.structure_counts.remote_deletes += 1;
1346 } else {
1347 trace!(
1348 self.driver,
1349 "Local node {} deleted remotely and not changed locally; taking remote deletion",
1350 local_node
1351 );
1352 }
1353
1354 // Take the remote deletion and relocate any new local descendants to the
1355 // merged node.
1356 self.delete_local_node(merged_node, local_node)
1357 }
1358
1359 /// Marks a remote node as deleted, and relocates all remote descendants
1360 /// that aren't also locally deleted to the merged node. This avoids data
1361 /// loss if the user adds a bookmark to a folder on another device, and
1362 /// deletes that folder locally.
1363 ///
1364 /// This is the inverse of `delete_local_node`.
delete_remote_node( &mut self, merged_node: &mut MergedNode<'t>, remote_node: Node<'t>, ) -> Result<StructureChange>1365 fn delete_remote_node(
1366 &mut self,
1367 merged_node: &mut MergedNode<'t>,
1368 remote_node: Node<'t>,
1369 ) -> Result<StructureChange> {
1370 self.delete_remotely.insert(remote_node.guid.clone());
1371 for remote_child_node in remote_node.children() {
1372 self.signal.err_if_aborted()?;
1373 if self.merged_guids.contains(&remote_child_node.guid) {
1374 trace!(
1375 self.driver,
1376 "Remote child {} can't be an orphan; already merged",
1377 remote_child_node
1378 );
1379 continue;
1380 }
1381 match self.check_for_local_structure_change_of_remote_node(
1382 merged_node,
1383 remote_node,
1384 remote_child_node,
1385 )? {
1386 StructureChange::Moved | StructureChange::Deleted => {
1387 // The remote child is already moved or deleted locally, so we should
1388 // ignore it instead of treating it as a remote orphan.
1389 continue;
1390 }
1391 StructureChange::Unchanged => {
1392 trace!(
1393 self.driver,
1394 "Relocating remote orphan {} to {}",
1395 remote_child_node,
1396 merged_node
1397 );
1398
1399 // Flag the new parent and moved remote orphan for reupload.
1400 let mut merged_orphan_node = if let Some(local_child_node) =
1401 self.local_tree.node_for_guid(&remote_child_node.guid)
1402 {
1403 self.two_way_merge(local_child_node, remote_child_node)
1404 } else {
1405 self.merge_remote_only_node(remote_child_node)
1406 }?;
1407 merged_node.merge_state = merged_node
1408 .merge_state
1409 .with_new_local_structure()
1410 .with_new_remote_structure();
1411 merged_orphan_node.merge_state = merged_orphan_node
1412 .merge_state
1413 .with_new_local_structure()
1414 .with_new_remote_structure();
1415 merged_node.merged_children.push(merged_orphan_node);
1416 self.structure_counts.merged_nodes += 1;
1417 }
1418 }
1419 }
1420 Ok(StructureChange::Deleted)
1421 }
1422
1423 /// Marks a local node as deleted, and relocates all local descendants
1424 /// that aren't also remotely deleted to the merged node.
1425 ///
1426 /// This is the inverse of `delete_remote_node`.
delete_local_node( &mut self, merged_node: &mut MergedNode<'t>, local_node: Node<'t>, ) -> Result<StructureChange>1427 fn delete_local_node(
1428 &mut self,
1429 merged_node: &mut MergedNode<'t>,
1430 local_node: Node<'t>,
1431 ) -> Result<StructureChange> {
1432 self.delete_locally.insert(local_node.guid.clone());
1433 for local_child_node in local_node.children() {
1434 self.signal.err_if_aborted()?;
1435 if self.merged_guids.contains(&local_child_node.guid) {
1436 trace!(
1437 self.driver,
1438 "Local child {} can't be an orphan; already merged",
1439 local_child_node
1440 );
1441 continue;
1442 }
1443 match self.check_for_remote_structure_change_of_local_node(
1444 merged_node,
1445 local_node,
1446 local_child_node,
1447 )? {
1448 StructureChange::Moved | StructureChange::Deleted => {
1449 // The local child is already moved or deleted remotely, so we should
1450 // ignore it instead of treating it as a local orphan.
1451 continue;
1452 }
1453 StructureChange::Unchanged => {
1454 trace!(
1455 self.driver,
1456 "Relocating local orphan {} to {}",
1457 local_child_node,
1458 merged_node
1459 );
1460
1461 // Flag the new parent and moved local orphan for reupload.
1462 let mut merged_orphan_node = if let Some(remote_child_node) =
1463 self.remote_tree.node_for_guid(&local_child_node.guid)
1464 {
1465 self.two_way_merge(local_child_node, remote_child_node)
1466 } else {
1467 self.merge_local_only_node(local_child_node)
1468 }?;
1469 merged_node.merge_state = merged_node
1470 .merge_state
1471 .with_new_local_structure()
1472 .with_new_remote_structure();
1473 merged_orphan_node.merge_state = merged_orphan_node
1474 .merge_state
1475 .with_new_local_structure()
1476 .with_new_remote_structure();
1477 merged_node.merged_children.push(merged_orphan_node);
1478 self.structure_counts.merged_nodes += 1;
1479 }
1480 }
1481 }
1482 Ok(StructureChange::Deleted)
1483 }
1484
1485 /// Finds all children of a local folder with similar content as children of
1486 /// the corresponding remote folder. This is used to dedupe local items that
1487 /// haven't been uploaded yet, to remote items that don't exist locally.
1488 ///
1489 /// Recall that we match items by GUID as we walk down the tree. If a GUID
1490 /// on one side doesn't exist on the other, we fall back to a content
1491 /// match in the same folder.
1492 ///
1493 /// This method is called the first time that
1494 /// `find_remote_node_matching_local_node` merges a local child that
1495 /// doesn't exist remotely, and
1496 /// the first time that `find_local_node_matching_remote_node` merges a
1497 /// remote child that doesn't exist locally.
1498 ///
1499 /// Finding all possible dupes is O(m + n) in the worst case, where `m` is
1500 /// the number of local children, and `n` is the number of remote
1501 /// children. We cache matches in
1502 /// `matching_dupes_by_local_parent_guid`, so deduping all
1503 /// remaining children of the same folder, on both sides, only needs two
1504 /// O(1) map lookups per child.
find_all_matching_dupes_in_folders( &self, local_parent_node: Node<'t>, remote_parent_node: Node<'t>, ) -> Result<MatchingDupes<'t>>1505 fn find_all_matching_dupes_in_folders(
1506 &self,
1507 local_parent_node: Node<'t>,
1508 remote_parent_node: Node<'t>,
1509 ) -> Result<MatchingDupes<'t>> {
1510 let mut dupe_key_to_local_nodes: HashMap<DupeKey<'_>, VecDeque<_>> = HashMap::new();
1511
1512 for (local_position, local_child_node) in local_parent_node.children().enumerate() {
1513 self.signal.err_if_aborted()?;
1514 if local_child_node.is_built_in_root() {
1515 trace!(
1516 self.driver,
1517 "Not deduping local built-in root {}",
1518 local_child_node
1519 );
1520 continue;
1521 }
1522 if self.remote_tree.mentions(&local_child_node.guid) {
1523 trace!(
1524 self.driver,
1525 "Not deduping local child {}; already deleted or exists remotely",
1526 local_child_node
1527 );
1528 continue;
1529 }
1530 match local_child_node.content() {
1531 Some(local_child_content) => {
1532 // Store matching local children in an array, in case multiple children
1533 // have the same dupe key (for example, a toolbar containing multiple
1534 // empty folders, as in bug 1213369).
1535 let dupe_key = match local_child_content {
1536 Content::Bookmark { .. } | Content::Folder { .. } => {
1537 DupeKey::WithoutPosition(local_child_content)
1538 }
1539 Content::Separator => {
1540 DupeKey::WithPosition(local_child_content, local_position)
1541 }
1542 };
1543 let local_nodes_for_key = dupe_key_to_local_nodes.entry(dupe_key).or_default();
1544 local_nodes_for_key.push_back(local_child_node);
1545 }
1546 None => {
1547 trace!(
1548 self.driver,
1549 "Not deduping local child {} without content info",
1550 local_child_node
1551 );
1552 }
1553 }
1554 }
1555
1556 let mut local_to_remote = HashMap::new();
1557 let mut remote_to_local = HashMap::new();
1558
1559 for (remote_position, remote_child_node) in remote_parent_node.children().enumerate() {
1560 self.signal.err_if_aborted()?;
1561 if remote_child_node.is_built_in_root() {
1562 trace!(
1563 self.driver,
1564 "Not deduping remote built-in root {}",
1565 remote_child_node
1566 );
1567 continue;
1568 }
1569 if self.local_tree.mentions(&remote_child_node.guid) {
1570 trace!(
1571 self.driver,
1572 "Not deduping remote child {}; already deleted or exists locally",
1573 remote_child_node
1574 );
1575 continue;
1576 }
1577 if remote_to_local.contains_key(&remote_child_node.guid) {
1578 trace!(
1579 self.driver,
1580 "Not deduping remote child {}; already deduped",
1581 remote_child_node
1582 );
1583 continue;
1584 }
1585 // Note that we don't need to check if the remote node is deleted
1586 // locally, because it wouldn't have local content entries if it
1587 // were.
1588 match remote_child_node.content() {
1589 Some(remote_child_content) => {
1590 let dupe_key = match remote_child_content {
1591 Content::Bookmark { .. } | Content::Folder { .. } => {
1592 DupeKey::WithoutPosition(remote_child_content)
1593 }
1594 Content::Separator => {
1595 DupeKey::WithPosition(remote_child_content, remote_position)
1596 }
1597 };
1598 if let Some(local_nodes_for_key) = dupe_key_to_local_nodes.get_mut(&dupe_key) {
1599 if let Some(local_child_node) = local_nodes_for_key.pop_front() {
1600 trace!(
1601 self.driver,
1602 "Deduping local child {} to remote child {}",
1603 local_child_node,
1604 remote_child_node
1605 );
1606 local_to_remote
1607 .insert(local_child_node.guid.clone(), remote_child_node);
1608 remote_to_local
1609 .insert(remote_child_node.guid.clone(), local_child_node);
1610 } else {
1611 trace!(
1612 self.driver,
1613 "Not deduping remote child {}; no remaining local content matches",
1614 remote_child_node
1615 );
1616 continue;
1617 }
1618 } else {
1619 trace!(
1620 self.driver,
1621 "Not deduping remote child {}; no local content matches",
1622 remote_child_node
1623 );
1624 continue;
1625 }
1626 }
1627 None => {
1628 trace!(
1629 self.driver,
1630 "Not deduping remote child {} without content info",
1631 remote_child_node
1632 );
1633 }
1634 }
1635 }
1636
1637 Ok((local_to_remote, remote_to_local))
1638 }
1639
1640 /// Finds a remote node with a different GUID that matches the content of a
1641 /// local node.
1642 ///
1643 /// This is the inverse of `find_local_node_matching_remote_node`.
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>>>1644 fn find_remote_node_matching_local_node(
1645 &mut self,
1646 merged_node: &MergedNode<'t>,
1647 local_parent_node: Node<'t>,
1648 remote_parent_node: Option<Node<'t>>,
1649 local_child_node: Node<'t>,
1650 ) -> Result<Option<Node<'t>>> {
1651 if let Some(remote_parent_node) = remote_parent_node {
1652 let mut matching_dupes_by_local_parent_guid = mem::replace(
1653 &mut self.matching_dupes_by_local_parent_guid,
1654 HashMap::new(),
1655 );
1656 let new_remote_node = {
1657 let (local_to_remote, _) = match matching_dupes_by_local_parent_guid
1658 .entry(local_parent_node.guid.clone())
1659 {
1660 Entry::Occupied(entry) => entry.into_mut(),
1661 Entry::Vacant(entry) => {
1662 trace!(
1663 self.driver,
1664 "First local child {} doesn't exist remotely; \
1665 finding all matching dupes in local {} and remote {}",
1666 local_child_node,
1667 local_parent_node,
1668 remote_parent_node
1669 );
1670 let matching_dupes = self.find_all_matching_dupes_in_folders(
1671 local_parent_node,
1672 remote_parent_node,
1673 )?;
1674 entry.insert(matching_dupes)
1675 }
1676 };
1677 let new_remote_node = local_to_remote.get(&local_child_node.guid);
1678 new_remote_node.map(|node| {
1679 self.structure_counts.dupes += 1;
1680 *node
1681 })
1682 };
1683 mem::replace(
1684 &mut self.matching_dupes_by_local_parent_guid,
1685 matching_dupes_by_local_parent_guid,
1686 );
1687 Ok(new_remote_node)
1688 } else {
1689 trace!(
1690 self.driver,
1691 "Merged node {} doesn't exist remotely; no potential dupes for local child {}",
1692 merged_node,
1693 local_child_node
1694 );
1695 Ok(None)
1696 }
1697 }
1698
1699 /// Finds a local node with a different GUID that matches the content of a
1700 /// remote node.
1701 ///
1702 /// This is the inverse of `find_remote_node_matching_local_node`.
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>>>1703 fn find_local_node_matching_remote_node(
1704 &mut self,
1705 merged_node: &MergedNode<'t>,
1706 local_parent_node: Option<Node<'t>>,
1707 remote_parent_node: Node<'t>,
1708 remote_child_node: Node<'t>,
1709 ) -> Result<Option<Node<'t>>> {
1710 if let Some(local_parent_node) = local_parent_node {
1711 let mut matching_dupes_by_local_parent_guid = mem::replace(
1712 &mut self.matching_dupes_by_local_parent_guid,
1713 HashMap::new(),
1714 );
1715 let new_local_node = {
1716 let (_, remote_to_local) = match matching_dupes_by_local_parent_guid
1717 .entry(local_parent_node.guid.clone())
1718 {
1719 Entry::Occupied(entry) => entry.into_mut(),
1720 Entry::Vacant(entry) => {
1721 trace!(
1722 self.driver,
1723 "First remote child {} doesn't exist locally; \
1724 finding all matching dupes in local {} and remote {}",
1725 remote_child_node,
1726 local_parent_node,
1727 remote_parent_node
1728 );
1729 let matching_dupes = self.find_all_matching_dupes_in_folders(
1730 local_parent_node,
1731 remote_parent_node,
1732 )?;
1733 entry.insert(matching_dupes)
1734 }
1735 };
1736 let new_local_node = remote_to_local.get(&remote_child_node.guid);
1737 new_local_node.map(|node| {
1738 self.structure_counts.dupes += 1;
1739 *node
1740 })
1741 };
1742 mem::replace(
1743 &mut self.matching_dupes_by_local_parent_guid,
1744 matching_dupes_by_local_parent_guid,
1745 );
1746 Ok(new_local_node)
1747 } else {
1748 trace!(
1749 self.driver,
1750 "Merged node {} doesn't exist locally; no potential dupes for remote child {}",
1751 merged_node,
1752 remote_child_node
1753 );
1754 Ok(None)
1755 }
1756 }
1757 }
1758
1759 /// The root of a merged tree, from which all merged nodes descend.
1760 #[derive(Debug)]
1761 pub struct MergedRoot<'t> {
1762 local_tree: &'t Tree,
1763 remote_tree: &'t Tree,
1764 node: MergedNode<'t>,
1765 merged_guids: HashSet<Guid>,
1766 delete_locally: HashSet<Guid>,
1767 delete_remotely: HashSet<Guid>,
1768 structure_counts: StructureCounts,
1769 }
1770
1771 impl<'t> MergedRoot<'t> {
1772 /// Returns the root node.
1773 #[inline]
node(&self) -> &MergedNode<'_>1774 pub fn node(&self) -> &MergedNode<'_> {
1775 &self.node
1776 }
1777
1778 /// Returns a sequence of completion operations, or "completion ops", to
1779 /// apply to the local tree so that it matches the merged tree. The abort
1780 /// signal can be used to interrupt fetching the ops.
completion_ops_with_signal( &self, signal: &impl AbortSignal, ) -> Result<CompletionOps<'_>>1781 pub fn completion_ops_with_signal(
1782 &self,
1783 signal: &impl AbortSignal,
1784 ) -> Result<CompletionOps<'_>> {
1785 let mut ops = CompletionOps::default();
1786 accumulate(signal, &mut ops, self.node(), 1, false)?;
1787
1788 // Clean up tombstones for local and remote items that are revived on
1789 // the other side.
1790 for guid in self
1791 .local_tree
1792 .deletions()
1793 .difference(&self.delete_remotely)
1794 {
1795 // For ignored local deletions, we remove the local tombstone. If
1796 // the item is already deleted remotely, we also flag the remote
1797 // tombstone as merged.
1798 signal.err_if_aborted()?;
1799 ops.delete_local_tombstones.push(DeleteLocalTombstone(guid));
1800 if self.remote_tree.is_deleted(guid) {
1801 ops.set_remote_merged.push(SetRemoteMerged(guid));
1802 }
1803 }
1804 for guid in self
1805 .remote_tree
1806 .deletions()
1807 .difference(&self.delete_locally)
1808 .filter(|guid| !self.local_tree.exists(guid))
1809 {
1810 // Ignored remote deletions are handled a little differently. Unlike
1811 // local tombstones, which are stored separately from items, remote
1812 // tombstones and items are stored in the same table. This means we
1813 // only need to flag the remote tombstone as merged if it's for an
1814 // item that doesn't exist locally. If the local item does exist,
1815 // we can avoid an extra write to flag the tombstone that we'll
1816 // replace with the item, anyway. If the item is already deleted
1817 // locally, we also delete the local tombstone.
1818 signal.err_if_aborted()?;
1819 ops.set_remote_merged.push(SetRemoteMerged(guid));
1820 if self.local_tree.is_deleted(guid) {
1821 ops.delete_local_tombstones.push(DeleteLocalTombstone(guid));
1822 }
1823 }
1824
1825 // Emit completion ops for deleted items.
1826 for guid in self.deletions() {
1827 signal.err_if_aborted()?;
1828 match (
1829 self.local_tree.node_for_guid(guid),
1830 self.remote_tree.node_for_guid(guid),
1831 ) {
1832 (Some(local_node), Some(remote_node)) => {
1833 // Delete items that are non-syncable or invalid on both
1834 // sides.
1835 ops.delete_local_items.push(DeleteLocalItem(local_node));
1836 ops.insert_local_tombstones
1837 .push(InsertLocalTombstone(remote_node));
1838 ops.upload_tombstones.push(UploadTombstone(guid));
1839 }
1840 (Some(local_node), None) => {
1841 // Apply remote tombstones, or delete invalid local-only
1842 // items. If the item is deleted remotely, flag the remote
1843 // tombstone as merged. If not, we don't need to upload one,
1844 // since the item is only known locally.
1845 ops.delete_local_items.push(DeleteLocalItem(local_node));
1846 if self.remote_tree.is_deleted(guid) {
1847 ops.set_remote_merged.push(SetRemoteMerged(guid));
1848 }
1849 }
1850 (None, Some(remote_node)) => {
1851 // Take local tombstones, or delete invalid remote-only
1852 // items. If it's not already deleted locally, insert a
1853 // tombstone for the item.
1854 if !self.local_tree.is_deleted(guid) {
1855 ops.insert_local_tombstones
1856 .push(InsertLocalTombstone(remote_node));
1857 }
1858 ops.upload_tombstones.push(UploadTombstone(guid));
1859 }
1860 (None, None) => {
1861 // Clean up local tombstones, and flag remote tombstones as
1862 // merged, for items deleted on both sides.
1863 if self.local_tree.is_deleted(guid) {
1864 ops.delete_local_tombstones.push(DeleteLocalTombstone(guid));
1865 }
1866 if self.remote_tree.is_deleted(guid) {
1867 ops.set_remote_merged.push(SetRemoteMerged(guid));
1868 }
1869 }
1870 }
1871 }
1872
1873 Ok(ops)
1874 }
1875
1876 /// Returns a sequence of completion ops, without interruption.
1877 #[inline]
completion_ops(&self) -> CompletionOps<'_>1878 pub fn completion_ops(&self) -> CompletionOps<'_> {
1879 self.completion_ops_with_signal(&DefaultAbortSignal)
1880 .unwrap()
1881 }
1882
1883 /// Returns an iterator for all accepted local and remote deletions.
1884 #[inline]
deletions(&self) -> impl Iterator<Item = &Guid>1885 pub fn deletions(&self) -> impl Iterator<Item = &Guid> {
1886 self.delete_locally.union(&self.delete_remotely)
1887 }
1888
1889 /// Returns an iterator for all items that should be deleted from the
1890 /// local tree.
1891 #[inline]
local_deletions(&self) -> impl Iterator<Item = &Guid>1892 pub fn local_deletions(&self) -> impl Iterator<Item = &Guid> {
1893 self.delete_locally.difference(&self.delete_remotely)
1894 }
1895
1896 /// Returns an iterator for all items that should be deleted from the
1897 /// remote tree.
1898 #[inline]
remote_deletions(&self) -> impl Iterator<Item = &Guid>1899 pub fn remote_deletions(&self) -> impl Iterator<Item = &Guid> {
1900 self.delete_remotely.iter()
1901 }
1902
1903 /// Returns structure change counts for this merged root.
1904 #[inline]
counts(&self) -> &StructureCounts1905 pub fn counts(&self) -> &StructureCounts {
1906 &self.structure_counts
1907 }
1908 }
1909
1910 /// Completion operations to apply to the local tree after a merge. These are
1911 /// represented as separate structs in `Vec`s instead of enums yielded from an
1912 /// iterator so that consumers can easily chunk them.
1913 #[derive(Clone, Debug, Default)]
1914 pub struct CompletionOps<'t> {
1915 pub change_guids: Vec<ChangeGuid<'t>>,
1916 pub apply_remote_items: Vec<ApplyRemoteItem<'t>>,
1917 pub apply_new_local_structure: Vec<ApplyNewLocalStructure<'t>>,
1918 pub set_local_unmerged: Vec<SetLocalUnmerged<'t>>,
1919 pub set_local_merged: Vec<SetLocalMerged<'t>>,
1920 pub set_remote_merged: Vec<SetRemoteMerged<'t>>,
1921 pub delete_local_tombstones: Vec<DeleteLocalTombstone<'t>>,
1922 pub insert_local_tombstones: Vec<InsertLocalTombstone<'t>>,
1923 pub delete_local_items: Vec<DeleteLocalItem<'t>>,
1924 pub upload_items: Vec<UploadItem<'t>>,
1925 pub upload_tombstones: Vec<UploadTombstone<'t>>,
1926 }
1927
1928 impl<'t> CompletionOps<'t> {
1929 /// Returns `true` if there are no completion ops to apply.
1930 #[inline]
is_empty(&self) -> bool1931 pub fn is_empty(&self) -> bool {
1932 self.change_guids.is_empty()
1933 && self.apply_remote_items.is_empty()
1934 && self.apply_new_local_structure.is_empty()
1935 && self.set_local_unmerged.is_empty()
1936 && self.set_local_merged.is_empty()
1937 && self.set_remote_merged.is_empty()
1938 && self.delete_local_tombstones.is_empty()
1939 && self.insert_local_tombstones.is_empty()
1940 && self.delete_local_items.is_empty()
1941 && self.upload_items.is_empty()
1942 && self.upload_tombstones.is_empty()
1943 }
1944
1945 /// Returns a printable summary of all completion ops to apply.
summarize(&self) -> Vec<String>1946 pub fn summarize(&self) -> Vec<String> {
1947 std::iter::empty()
1948 .chain(to_strings(&self.change_guids))
1949 .chain(to_strings(&self.apply_remote_items))
1950 .chain(to_strings(&self.apply_new_local_structure))
1951 .chain(to_strings(&self.set_local_unmerged))
1952 .chain(to_strings(&self.set_local_merged))
1953 .chain(to_strings(&self.set_remote_merged))
1954 .chain(to_strings(&self.delete_local_tombstones))
1955 .chain(to_strings(&self.insert_local_tombstones))
1956 .chain(to_strings(&self.delete_local_items))
1957 .chain(to_strings(&self.upload_items))
1958 .chain(to_strings(&self.upload_tombstones))
1959 .collect()
1960 }
1961 }
1962
1963 /// A completion op to change the local GUID to the merged GUID. This is used
1964 /// to dedupe new local items to remote ones, as well as to fix up invalid
1965 /// GUIDs.
1966 #[derive(Clone, Copy, Debug)]
1967 pub struct ChangeGuid<'t> {
1968 /// The merged node to update.
1969 pub merged_node: &'t MergedNode<'t>,
1970 /// The level of the node in the merged tree. Desktop uses this to ensure
1971 /// that GUID change observers are notified in level order (parents before
1972 /// children).
1973 pub level: usize,
1974 }
1975
1976 impl<'t> ChangeGuid<'t> {
1977 /// Returns the local node for this completion op. Panics if the local node
1978 /// isn't set, as we should never emit a `ChangeGuid` op in that case.
1979 #[inline]
local_node(&self) -> &'t Node<'t>1980 pub fn local_node(&self) -> &'t Node<'t> {
1981 self.merged_node
1982 .merge_state
1983 .local_node()
1984 .expect("Can't change local GUID without local node")
1985 }
1986 }
1987
1988 impl<'t> fmt::Display for ChangeGuid<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result1989 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1990 write!(
1991 f,
1992 "Change {} to {}",
1993 self.local_node().guid,
1994 self.merged_node.guid
1995 )
1996 }
1997 }
1998
1999 /// A completion op to insert a new remote item into the local tree, or apply
2000 /// synced changes to an existing item.
2001 #[derive(Clone, Copy, Debug)]
2002 pub struct ApplyRemoteItem<'t> {
2003 pub merged_node: &'t MergedNode<'t>,
2004 pub level: usize,
2005 }
2006
2007 impl<'t> ApplyRemoteItem<'t> {
2008 /// Returns the remote node for this completion op. Panics if the remote
2009 /// node isn't set, as we should never emit an `ApplyRemoteItem` op in
2010 /// that case.
2011 #[inline]
remote_node(&self) -> &'t Node<'t>2012 pub fn remote_node(&self) -> &'t Node<'t> {
2013 self.merged_node
2014 .merge_state
2015 .remote_node()
2016 .expect("Can't apply remote item without remote node")
2017 }
2018 }
2019
2020 impl<'t> fmt::Display for ApplyRemoteItem<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2021 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2022 if self.merged_node.remote_guid_changed() {
2023 write!(
2024 f,
2025 "Apply remote {} as {}",
2026 self.remote_node().guid,
2027 self.merged_node.guid
2028 )
2029 } else {
2030 write!(f, "Apply remote {}", self.merged_node.guid)
2031 }
2032 }
2033 }
2034
2035 /// A completion op to update the parent and position of a local item.
2036 #[derive(Clone, Copy, Debug)]
2037 pub struct ApplyNewLocalStructure<'t> {
2038 pub merged_node: &'t MergedNode<'t>,
2039 pub merged_parent_node: &'t MergedNode<'t>,
2040 pub position: usize,
2041 pub level: usize,
2042 }
2043
2044 impl<'t> fmt::Display for ApplyNewLocalStructure<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2045 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2046 write!(
2047 f,
2048 "Move {} into {} at {}",
2049 self.merged_node.guid, self.merged_parent_node.guid, self.position
2050 )
2051 }
2052 }
2053
2054 /// A completion op to flag a local item for upload.
2055 #[derive(Clone, Copy, Debug)]
2056 pub struct SetLocalUnmerged<'t> {
2057 pub merged_node: &'t MergedNode<'t>,
2058 }
2059
2060 impl<'t> fmt::Display for SetLocalUnmerged<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2061 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2062 write!(f, "Flag local {} as unmerged", self.merged_node.guid)
2063 }
2064 }
2065
2066 /// A completion op to skip uploading a local item after resolving merge
2067 /// conflicts.
2068 #[derive(Clone, Copy, Debug)]
2069 pub struct SetLocalMerged<'t> {
2070 pub merged_node: &'t MergedNode<'t>,
2071 }
2072
2073 impl<'t> fmt::Display for SetLocalMerged<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2074 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2075 write!(f, "Flag local {} as merged", self.merged_node.guid)
2076 }
2077 }
2078
2079 /// A completion op to upload or reupload a merged item.
2080 #[derive(Clone, Copy, Debug)]
2081 pub struct UploadItem<'t> {
2082 pub merged_node: &'t MergedNode<'t>,
2083 }
2084
2085 impl<'t> fmt::Display for UploadItem<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2086 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2087 write!(f, "Upload item {}", self.merged_node.guid)
2088 }
2089 }
2090
2091 /// A completion op to upload a tombstone.
2092 #[derive(Clone, Copy, Debug)]
2093 pub struct UploadTombstone<'t>(&'t Guid);
2094
2095 impl<'t> UploadTombstone<'t> {
2096 /// Returns the GUID to use for the tombstone.
2097 #[inline]
guid(self) -> &'t Guid2098 pub fn guid(self) -> &'t Guid {
2099 self.0
2100 }
2101 }
2102
2103 impl<'t> fmt::Display for UploadTombstone<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2104 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2105 write!(f, "Upload tombstone {}", self.0)
2106 }
2107 }
2108
2109 /// A completion op to flag a remote item as merged.
2110 #[derive(Clone, Copy, Debug)]
2111 pub struct SetRemoteMerged<'t>(&'t Guid);
2112
2113 impl<'t> SetRemoteMerged<'t> {
2114 /// Returns the remote GUID for the item to flag as merged.
2115 #[inline]
guid(self) -> &'t Guid2116 pub fn guid(self) -> &'t Guid {
2117 self.0
2118 }
2119 }
2120
2121 impl<'t> fmt::Display for SetRemoteMerged<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2122 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2123 write!(f, "Flag remote {} as merged", self.guid())
2124 }
2125 }
2126
2127 /// A completion op to store a tombstone for a remote item.
2128 #[derive(Clone, Copy, Debug)]
2129 pub struct InsertLocalTombstone<'t>(Node<'t>);
2130
2131 impl<'t> InsertLocalTombstone<'t> {
2132 /// Returns the node for the item to delete remotely.
2133 #[inline]
remote_node(&self) -> Node<'t>2134 pub fn remote_node(&self) -> Node<'t> {
2135 self.0
2136 }
2137 }
2138
2139 impl<'t> fmt::Display for InsertLocalTombstone<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2140 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2141 write!(f, "Insert local tombstone {}", self.0.guid)
2142 }
2143 }
2144
2145 /// A completion op to delete a local tombstone.
2146 #[derive(Clone, Copy, Debug)]
2147 pub struct DeleteLocalTombstone<'t>(&'t Guid);
2148
2149 impl<'t> DeleteLocalTombstone<'t> {
2150 /// Returns the GUID of the tombstone.
2151 #[inline]
guid(self) -> &'t Guid2152 pub fn guid(self) -> &'t Guid {
2153 self.0
2154 }
2155 }
2156
2157 impl<'t> fmt::Display for DeleteLocalTombstone<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2158 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2159 write!(f, "Delete local tombstone {}", self.0)
2160 }
2161 }
2162
2163 /// A completion op to delete an item from the local tree.
2164 #[derive(Clone, Copy, Debug)]
2165 pub struct DeleteLocalItem<'t>(Node<'t>);
2166
2167 impl<'t> DeleteLocalItem<'t> {
2168 // Returns the node for the item to delete locally.
2169 #[inline]
local_node(&self) -> Node<'t>2170 pub fn local_node(&self) -> Node<'t> {
2171 self.0
2172 }
2173 }
2174
2175 impl<'t> fmt::Display for DeleteLocalItem<'t> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result2176 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2177 write!(f, "Delete local item {}", self.0.guid)
2178 }
2179 }
2180
2181 /// Recursively accumulates completion ops, starting at `merged_node` and
2182 /// drilling down into all its descendants.
accumulate<'t, A: AbortSignal>( signal: &A, ops: &mut CompletionOps<'t>, merged_node: &'t MergedNode<'t>, level: usize, is_tagging: bool, ) -> Result<()>2183 fn accumulate<'t, A: AbortSignal>(
2184 signal: &A,
2185 ops: &mut CompletionOps<'t>,
2186 merged_node: &'t MergedNode<'t>,
2187 level: usize,
2188 is_tagging: bool,
2189 ) -> Result<()> {
2190 for (position, merged_child_node) in merged_node.merged_children.iter().enumerate() {
2191 signal.err_if_aborted()?;
2192 let is_tagging = if merged_child_node.guid == TAGS_GUID {
2193 true
2194 } else {
2195 is_tagging
2196 };
2197 if merged_child_node.merge_state.should_apply_item() {
2198 let apply_remote_item = ApplyRemoteItem {
2199 merged_node: merged_child_node,
2200 level,
2201 };
2202 ops.apply_remote_items.push(apply_remote_item);
2203 }
2204 if merged_child_node.local_guid_changed() {
2205 let change_guid = ChangeGuid {
2206 merged_node: merged_child_node,
2207 level,
2208 };
2209 ops.change_guids.push(change_guid);
2210 }
2211 let local_child_node = merged_node
2212 .merge_state
2213 .local_node()
2214 .and_then(|local_parent_node| local_parent_node.child(position));
2215 let merged_local_child_node = merged_child_node.merge_state.local_node();
2216 if local_child_node
2217 .and_then(|m| merged_local_child_node.map(|n| m.guid != n.guid))
2218 .unwrap_or(true)
2219 {
2220 // As an optimization, we only emit ops to apply a new local
2221 // structure for items that actually moved. For example, if the
2222 // local children are (A B C D) and the merged children are
2223 // (A D C B), only (B D) need new structure.
2224 let apply_new_local_structure = ApplyNewLocalStructure {
2225 merged_node: merged_child_node,
2226 merged_parent_node: merged_node,
2227 position,
2228 level,
2229 };
2230 ops.apply_new_local_structure
2231 .push(apply_new_local_structure);
2232 }
2233 let local_needs_merge = merged_child_node
2234 .merge_state
2235 .local_node()
2236 .map(|node| node.needs_merge)
2237 .unwrap_or(false);
2238 let should_upload = merged_child_node.merge_state.should_upload();
2239 match (local_needs_merge, should_upload) {
2240 (false, true) => {
2241 // Local item isn't flagged for upload, but should be.
2242 let set_local_unmerged = SetLocalUnmerged {
2243 merged_node: merged_child_node,
2244 };
2245 ops.set_local_unmerged.push(set_local_unmerged);
2246 }
2247 (true, false) => {
2248 // Local item flagged for upload when it doesn't need to be.
2249 let set_local_merged = SetLocalMerged {
2250 merged_node: merged_child_node,
2251 };
2252 ops.set_local_merged.push(set_local_merged);
2253 }
2254 _ => {}
2255 }
2256 if should_upload && !is_tagging {
2257 // (Re)upload items. Ignore the tags root and its descendants:
2258 // they're part of the local tree on Desktop (and will be removed
2259 // in bug 424160), but aren't synced as part of the structure.
2260 ops.upload_items.push(UploadItem {
2261 merged_node: merged_child_node,
2262 });
2263 }
2264 if let Some(remote_child_node) = merged_child_node.merge_state.remote_node() {
2265 if remote_child_node.needs_merge && !should_upload {
2266 // If the remote item was merged, and doesn't need to be
2267 // reuploaded, flag it as merged in the remote tree. Note that
2268 // we _don't_ emit this for locally revived items, or items with
2269 // new remote structure.
2270 let set_remote_merged = SetRemoteMerged(&remote_child_node.guid);
2271 ops.set_remote_merged.push(set_remote_merged);
2272 }
2273 }
2274 accumulate(signal, ops, merged_child_node, level + 1, is_tagging)?;
2275 }
2276 Ok(())
2277 }
2278
2279 /// Converts all items in the list to strings.
to_strings<'a, T: ToString>(items: &'a [T]) -> impl Iterator<Item = String> + 'a2280 pub(crate) fn to_strings<'a, T: ToString>(items: &'a [T]) -> impl Iterator<Item = String> + 'a {
2281 items.iter().map(ToString::to_string)
2282 }
2283