// Copyright 2023 The Jujutsu Authors//// Licensed under the Apache License, Version 2.0 (the "License");// you may not use this file except in compliance with the License.// You may obtain a copy of the License at//// https://www.apache.org/licenses/LICENSE-2.0//// Unless required by applicable law or agreed to in writing, software// distributed under the License is distributed on an "AS IS" BASIS,// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.// See the License for the specific language governing permissions and// limitations under the License. //! A lazily merged view of a set of trees. use std::cmp::{max, Ordering};use std::collections::{BTreeMap, VecDeque};use std::iter::zip;use std::pin::Pin;use std::sync::Arc;use std::task::{Context, Poll};use std::{iter, vec}; use futures::stream::StreamExt;use futures::{Future, Stream, TryStreamExt};use itertools::Itertools; use crate::backend::{BackendError, BackendResult, ConflictId, MergedTreeId, TreeId, TreeValue};use crate::matchers::{EverythingMatcher, Matcher};use crate::merge::{Merge, MergeBuilder, MergedTreeValue};use crate::repo_path::{RepoPath, RepoPathBuf, RepoPathComponent, RepoPathComponentsIter};use crate::store::Store;use crate::tree::{try_resolve_file_conflict, Tree, TreeMergeError};use crate::tree_builder::TreeBuilder;use crate::{backend, tree}; /// Presents a view of a merged set of trees.#[derive(PartialEq, Eq, Clone, Debug)]pub enum MergedTree { /// A single tree, possibly with path-level conflicts. Legacy(Tree), /// A merge of multiple trees, or just a single tree. The individual trees /// have no path-level conflicts. Merge(Merge<Tree>),} /// The value at a given path in a `MergedTree`.#[derive(PartialEq, Eq, Hash, Clone, Debug)]pub enum MergedTreeVal<'a> { /// A single non-conflicted value. Resolved(Option<&'a TreeValue>), /// TODO: Make this a `Merge<Option<&'a TreeValue>>` (reference to the /// value) once we have removed the `MergedTree::Legacy` variant. Conflict(MergedTreeValue),} impl MergedTreeVal<'_> { fn to_merge(&self) -> MergedTreeValue { match self { MergedTreeVal::Resolved(value) => Merge::resolved(value.cloned()), MergedTreeVal::Conflict(merge) => merge.clone(), } }} /// Summary of the changes between two trees.#[derive(Debug, PartialEq, Eq, Clone)]pub struct DiffSummary { /// Modified files pub modified: Vec<RepoPathBuf>, /// Added files pub added: Vec<RepoPathBuf>, /// Removed files pub removed: Vec<RepoPathBuf>,} impl MergedTree { /// Creates a new `MergedTree` representing a single tree without conflicts. pub fn resolved(tree: Tree) -> Self { MergedTree::new(Merge::resolved(tree)) } /// Creates a new `MergedTree` representing a merge of a set of trees. The /// individual trees must not have any conflicts. pub fn new(trees: Merge<Tree>) -> Self { debug_assert!(!trees.iter().any(|t| t.has_conflict())); debug_assert!(trees.iter().map(|tree| tree.dir()).all_equal()); debug_assert!(trees .iter() .map(|tree| Arc::as_ptr(tree.store())) .all_equal()); MergedTree::Merge(trees) } /// Creates a new `MergedTree` backed by a tree with path-level conflicts. pub fn legacy(tree: Tree) -> Self { MergedTree::Legacy(tree) } /// Takes a tree in the legacy format (with path-level conflicts in the /// tree) and returns a `MergedTree` with any conflicts converted to /// tree-level conflicts. pub fn from_legacy_tree(tree: Tree) -> BackendResult<Self> { let conflict_ids = tree.conflicts(); if conflict_ids.is_empty() { return Ok(MergedTree::resolved(tree)); } // Find the number of removes and adds in the most complex conflict. let mut max_tree_count = 1; let store = tree.store(); let mut conflicts: Vec<(&RepoPath, MergedTreeValue)> = vec![]; for (path, conflict_id) in &conflict_ids { let conflict = store.read_conflict(path, conflict_id)?; max_tree_count = max(max_tree_count, conflict.iter().len()); conflicts.push((path, conflict)); } let mut tree_builders = Vec::new(); tree_builders.resize_with(max_tree_count, || store.tree_builder(tree.id().clone())); for (path, conflict) in conflicts { // If there are fewer terms in this conflict than in some other conflict, we can // add canceling removes and adds of any value. The simplest value is an absent // value, so we use that. let terms_padded = conflict.into_iter().chain(iter::repeat(None)); for (builder, term) in zip(&mut tree_builders, terms_padded) { builder.set_or_remove(path.to_owned(), term); } } let new_trees: Vec<_> = tree_builders .into_iter() .map(|builder| { let tree_id = builder.write_tree(); store.get_tree(RepoPath::root(), &tree_id) }) .try_collect()?; Ok(MergedTree::Merge(Merge::from_vec(new_trees))) } /// This tree's directory pub fn dir(&self) -> &RepoPath { match self { MergedTree::Legacy(tree) => tree.dir(), MergedTree::Merge(conflict) => conflict.first().dir(), } } /// The `Store` associated with this tree. pub fn store(&self) -> &Arc<Store> { match self { MergedTree::Legacy(tree) => tree.store(), MergedTree::Merge(trees) => trees.first().store(), } } /// Base names of entries in this directory. pub fn names<'a>(&'a self) -> Box<dyn Iterator<Item = &'a RepoPathComponent> + 'a> { match self { MergedTree::Legacy(tree) => Box::new(tree.data().names()), MergedTree::Merge(conflict) => Box::new(all_tree_basenames(conflict)), } } /// The value at the given basename. The value can be `Resolved` even if /// `self` is a `Merge`, which happens if the value at the path can be /// trivially merged. Does not recurse, so if `basename` refers to a Tree, /// then a `TreeValue::Tree` will be returned. pub fn value(&self, basename: &RepoPathComponent) -> MergedTreeVal { match self { MergedTree::Legacy(tree) => match tree.value(basename) { Some(TreeValue::Conflict(conflict_id)) => { let path = tree.dir().join(basename); let conflict = tree.store().read_conflict(&path, conflict_id).unwrap(); MergedTreeVal::Conflict(conflict) } other => MergedTreeVal::Resolved(other), }, MergedTree::Merge(trees) => trees_value(trees, basename), } } /// Tries to resolve any conflicts, resolving any conflicts that can be /// automatically resolved and leaving the rest unresolved. The returned /// conflict will either be resolved or have the same number of sides as /// the input. pub fn resolve(&self) -> Result<Merge<Tree>, TreeMergeError> { match self { MergedTree::Legacy(tree) => Ok(Merge::resolved(tree.clone())), MergedTree::Merge(trees) => merge_trees(trees), } } /// An iterator over the conflicts in this tree, including subtrees. /// Recurses into subtrees and yields conflicts in those, but only if /// all sides are trees, so tree/file conflicts will be reported as a single /// conflict, not one for each path in the tree. // TODO: Restrict this by a matcher (or add a separate method for that). pub fn conflicts(&self) -> impl Iterator<Item = (RepoPathBuf, MergedTreeValue)> { ConflictIterator::new(self) } /// Whether this tree has conflicts. pub fn has_conflict(&self) -> bool { match self { MergedTree::Legacy(tree) => tree.has_conflict(), MergedTree::Merge(trees) => !trees.is_resolved(), } } /// Gets the `MergeTree` in a subdirectory of the current tree. If the path /// doesn't correspond to a tree in any of the inputs to the merge, then /// that entry will be replace by an empty tree in the result. pub fn sub_tree(&self, name: &RepoPathComponent) -> Option<MergedTree> { if let MergedTree::Legacy(tree) = self { tree.sub_tree(name).map(MergedTree::Legacy) } else { match self.value(name) { MergedTreeVal::Resolved(Some(TreeValue::Tree(sub_tree_id))) => { let subdir = self.dir().join(name); Some(MergedTree::resolved( self.store().get_tree(&subdir, sub_tree_id).unwrap(), )) } MergedTreeVal::Resolved(_) => None, MergedTreeVal::Conflict(merge) => { let merged_trees = merge.map(|value| match value { Some(TreeValue::Tree(sub_tree_id)) => { let subdir = self.dir().join(name); self.store().get_tree(&subdir, sub_tree_id).unwrap() } _ => { let subdir = self.dir().join(name); Tree::null(self.store().clone(), subdir.clone()) } }); Some(MergedTree::Merge(merged_trees)) } } } } /// The value at the given path. The value can be `Resolved` even if /// `self` is a `Conflict`, which happens if the value at the path can be /// trivially merged. pub fn path_value(&self, path: &RepoPath) -> MergedTreeValue { assert_eq!(self.dir(), RepoPath::root()); match path.split() { Some((dir, basename)) => match self.sub_tree_recursive(dir.components()) { None => Merge::absent(), Some(tree) => tree.value(basename).to_merge(), }, None => match self { MergedTree::Legacy(tree) => Merge::normal(TreeValue::Tree(tree.id().clone())), MergedTree::Merge(trees) => { trees.map(|tree| Some(TreeValue::Tree(tree.id().clone()))) } }, } } /// The tree's id pub fn id(&self) -> MergedTreeId { match self { MergedTree::Legacy(tree) => MergedTreeId::Legacy(tree.id().clone()), MergedTree::Merge(merge) => MergedTreeId::Merge(merge.map(|tree| tree.id().clone())), } } fn sub_tree_recursive(&self, mut components: RepoPathComponentsIter) -> Option<MergedTree> { if let Some(first) = components.next() { components.try_fold(self.sub_tree(first)?, |tree, name| tree.sub_tree(name)) } else { Some(self.clone()) } } /// Iterator over the entries matching the given matcher. Subtrees are /// visited recursively. Subtrees that differ between the current /// `MergedTree`'s terms are merged on the fly. Missing terms are treated as /// empty directories. Subtrees that conflict with non-trees are not /// visited. For example, if current tree is a merge of 3 trees, and the /// entry for 'foo' is a conflict between a change subtree and a symlink /// (i.e. the subdirectory was replaced by symlink in one side of the /// conflict), then the entry for `foo` itself will be emitted, but no /// entries from inside `foo/` from either of the trees will be. pub fn entries(&self) -> TreeEntriesIterator<'static> { TreeEntriesIterator::new(self.clone(), &EverythingMatcher) } /// Like `entries()` but restricted by a matcher. pub fn entries_matching<'matcher>( &self, matcher: &'matcher dyn Matcher, ) -> TreeEntriesIterator<'matcher> { TreeEntriesIterator::new(self.clone(), matcher) } /// Iterate over the differences between this tree and another tree. /// /// The files in a removed tree will be returned before a file that replaces /// it. pub fn diff<'matcher>( &self, other: &MergedTree, matcher: &'matcher dyn Matcher, ) -> TreeDiffIterator<'matcher> { TreeDiffIterator::new(self.clone(), other.clone(), matcher) } /// Stream of the differences between this tree and another tree. pub fn diff_stream<'matcher>( &self, other: &MergedTree, matcher: &'matcher dyn Matcher, ) -> TreeDiffStream<'matcher> { let concurrency = self.store().concurrency(); if concurrency <= 1 { Box::pin(futures::stream::iter(TreeDiffIterator::new( self.clone(), other.clone(), matcher, ))) } else { Box::pin(TreeDiffStreamImpl::new( self.clone(), other.clone(), matcher, concurrency, )) } } /// Collects lists of modified, added, and removed files between this tree /// and another tree. pub fn diff_summary( &self, other: &MergedTree, matcher: &dyn Matcher, ) -> BackendResult<DiffSummary> { let mut modified = vec![]; let mut added = vec![]; let mut removed = vec![]; for (file, diff) in self.diff(other, matcher) { let (before, after) = diff?; if before.is_absent() { added.push(file); } else if after.is_absent() { removed.push(file); } else { modified.push(file); } } modified.sort(); added.sort(); removed.sort(); Ok(DiffSummary { modified, added, removed, }) } /// Merges this tree with `other`, using `base` as base. pub fn merge( &self, base: &MergedTree, other: &MergedTree, ) -> Result<MergedTree, TreeMergeError> { if let (MergedTree::Legacy(this), MergedTree::Legacy(base), MergedTree::Legacy(other)) = (self, base, other) { let merged_tree = tree::merge_trees(this, base, other)?; Ok(MergedTree::legacy(merged_tree)) } else { // Convert legacy trees to merged trees and unwrap to `Merge<Tree>` let to_merge = |tree: &MergedTree| -> Result<Merge<Tree>, TreeMergeError> { match tree { MergedTree::Legacy(tree) => { let MergedTree::Merge(tree) = MergedTree::from_legacy_tree(tree.clone())? else { unreachable!(); }; Ok(tree) } MergedTree::Merge(conflict) => Ok(conflict.clone()), } }; let nested = Merge::from_vec(vec![to_merge(self)?, to_merge(base)?, to_merge(other)?]); let tree = merge_trees(&nested.flatten().simplify())?; // If the result can be resolved, then `merge_trees()` above would have returned // a resolved merge. However, that function will always preserve the arity of // conflicts it cannot resolve. So we simplify the conflict again // here to possibly reduce a complex conflict to a simpler one. let tree = tree.simplify(); // If debug assertions are enabled, check that the merge was idempotent. In // particular, that this last simplification doesn't enable further automatic // resolutions if cfg!(debug_assertions) { let re_merged = merge_trees(&tree).unwrap(); debug_assert_eq!(re_merged, tree); } Ok(MergedTree::Merge(tree)) } }} /// Type alias for the result from `MergedTree::diff_stream()`. We use a/// `Stream` instead of an `Iterator` so high-latency backends (e.g. cloud-based/// ones) can fetch trees asynchronously.pub type TreeDiffStream<'matcher> = Pin< Box< dyn Stream< Item = ( RepoPathBuf, BackendResult<(MergedTreeValue, MergedTreeValue)>, ), > + 'matcher, >,>; fn all_tree_basenames(trees: &Merge<Tree>) -> impl Iterator<Item = &RepoPathComponent> { trees .iter() .map(|tree| tree.data().names()) .kmerge() .dedup()} fn merged_tree_basenames<'a>( tree1: &'a MergedTree, tree2: &'a MergedTree,) -> Box<dyn Iterator<Item = &'a RepoPathComponent> + 'a> { fn merge_iters<'a>( iter1: impl Iterator<Item = &'a RepoPathComponent> + 'a, iter2: impl Iterator<Item = &'a RepoPathComponent> + 'a, ) -> Box<dyn Iterator<Item = &'a RepoPathComponent> + 'a> { Box::new(iter1.merge(iter2).dedup()) } match (&tree1, &tree2) { (MergedTree::Legacy(before), MergedTree::Legacy(after)) => { merge_iters(before.data().names(), after.data().names()) } (MergedTree::Merge(before), MergedTree::Legacy(after)) => { merge_iters(all_tree_basenames(before), after.data().names()) } (MergedTree::Legacy(before), MergedTree::Merge(after)) => { merge_iters(before.data().names(), all_tree_basenames(after)) } (MergedTree::Merge(before), MergedTree::Merge(after)) => { merge_iters(all_tree_basenames(before), all_tree_basenames(after)) } }} fn merged_tree_entry_diff<'a>( before: &'a MergedTree, after: &'a MergedTree,) -> impl Iterator<Item = (&'a RepoPathComponent, MergedTreeVal<'a>, MergedTreeVal<'a>)> { merged_tree_basenames(before, after).filter_map(|basename| { let value_before = before.value(basename); let value_after = after.value(basename); (value_after != value_before).then_some((basename, value_before, value_after)) })} fn trees_value<'a>(trees: &'a Merge<Tree>, basename: &RepoPathComponent) -> MergedTreeVal<'a> { if let Some(tree) = trees.as_resolved() { return MergedTreeVal::Resolved(tree.value(basename)); } let value = trees.map(|tree| tree.value(basename)); if let Some(resolved) = value.resolve_trivial() { return MergedTreeVal::Resolved(*resolved); } MergedTreeVal::Conflict(value.map(|x| x.cloned()))} fn merge_trees(merge: &Merge<Tree>) -> Result<Merge<Tree>, TreeMergeError> { if let Some(tree) = merge.resolve_trivial() { return Ok(Merge::resolved(tree.clone())); } let base_tree = merge.first(); let store = base_tree.store(); let dir = base_tree.dir(); // Keep resolved entries in `new_tree` and conflicted entries in `conflicts` to // start with. Then we'll create the full trees later, and only if there are // any conflicts. let mut new_tree = backend::Tree::default(); let mut conflicts = vec![]; for basename in all_tree_basenames(merge) { let path_merge = merge.map(|tree| tree.value(basename).cloned()); let path = dir.join(basename); let path_merge = merge_tree_values(store, &path, path_merge)?; match path_merge.into_resolved() { Ok(value) => { new_tree.set_or_remove(basename, value); } Err(path_merge) => { conflicts.push((basename, path_merge.into_iter()));Lines 1–500 of 1272. Load more
// Copyright 2023 The Jujutsu Authors // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // https://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. //! A lazily merged view of a set of trees. use std::cmp::{max, Ordering}; use std::collections::{BTreeMap, VecDeque}; use std::iter::zip; use std::pin::Pin; use std::sync::Arc; use std::task::{Context, Poll}; use std::{iter, vec}; use futures::stream::StreamExt; use futures::{Future, Stream, TryStreamExt}; use itertools::Itertools; use crate::backend::{BackendError, BackendResult, ConflictId, MergedTreeId, TreeId, TreeValue}; use crate::matchers::{EverythingMatcher, Matcher}; use crate::merge::{Merge, MergeBuilder, MergedTreeValue}; use crate::repo_path::{RepoPath, RepoPathBuf, RepoPathComponent, RepoPathComponentsIter}; use crate::store::Store; use crate::tree::{try_resolve_file_conflict, Tree, TreeMergeError}; use crate::tree_builder::TreeBuilder; use crate::{backend, tree}; /// Presents a view of a merged set of trees. #[derive(PartialEq, Eq, Clone, Debug)] pub enum MergedTree { /// A single tree, possibly with path-level conflicts. Legacy(Tree), /// A merge of multiple trees, or just a single tree. The individual trees /// have no path-level conflicts. Merge(Merge<Tree>), } /// The value at a given path in a `MergedTree`. #[derive(PartialEq, Eq, Hash, Clone, Debug)] pub enum MergedTreeVal<'a> { /// A single non-conflicted value. Resolved(Option<&'a TreeValue>), /// TODO: Make this a `Merge<Option<&'a TreeValue>>` (reference to the /// value) once we have removed the `MergedTree::Legacy` variant. Conflict(MergedTreeValue), } impl MergedTreeVal<'_> { fn to_merge(&self) -> MergedTreeValue { match self { MergedTreeVal::Resolved(value) => Merge::resolved(value.cloned()), MergedTreeVal::Conflict(merge) => merge.clone(), } } } /// Summary of the changes between two trees. #[derive(Debug, PartialEq, Eq, Clone)] pub struct DiffSummary { /// Modified files pub modified: Vec<RepoPathBuf>, /// Added files pub added: Vec<RepoPathBuf>, /// Removed files pub removed: Vec<RepoPathBuf>, } impl MergedTree { /// Creates a new `MergedTree` representing a single tree without conflicts. pub fn resolved(tree: Tree) -> Self { MergedTree::new(Merge::resolved(tree)) } /// Creates a new `MergedTree` representing a merge of a set of trees. The /// individual trees must not have any conflicts. pub fn new(trees: Merge<Tree>) -> Self { debug_assert!(!trees.iter().any(|t| t.has_conflict())); debug_assert!(trees.iter().map(|tree| tree.dir()).all_equal()); debug_assert!(trees .iter() .map(|tree| Arc::as_ptr(tree.store())) .all_equal()); MergedTree::Merge(trees) } /// Creates a new `MergedTree` backed by a tree with path-level conflicts. pub fn legacy(tree: Tree) -> Self { MergedTree::Legacy(tree) } /// Takes a tree in the legacy format (with path-level conflicts in the /// tree) and returns a `MergedTree` with any conflicts converted to /// tree-level conflicts. pub fn from_legacy_tree(tree: Tree) -> BackendResult<Self> { let conflict_ids = tree.conflicts(); if conflict_ids.is_empty() { return Ok(MergedTree::resolved(tree)); } // Find the number of removes and adds in the most complex conflict. let mut max_tree_count = 1; let store = tree.store(); let mut conflicts: Vec<(&RepoPath, MergedTreeValue)> = vec![]; for (path, conflict_id) in &conflict_ids { let conflict = store.read_conflict(path, conflict_id)?; max_tree_count = max(max_tree_count, conflict.iter().len()); conflicts.push((path, conflict)); } let mut tree_builders = Vec::new(); tree_builders.resize_with(max_tree_count, || store.tree_builder(tree.id().clone())); for (path, conflict) in conflicts { // If there are fewer terms in this conflict than in some other conflict, we can // add canceling removes and adds of any value. The simplest value is an absent // value, so we use that. let terms_padded = conflict.into_iter().chain(iter::repeat(None)); for (builder, term) in zip(&mut tree_builders, terms_padded) { builder.set_or_remove(path.to_owned(), term); } } let new_trees: Vec<_> = tree_builders .into_iter() .map(|builder| { let tree_id = builder.write_tree(); store.get_tree(RepoPath::root(), &tree_id) }) .try_collect()?; Ok(MergedTree::Merge(Merge::from_vec(new_trees))) } /// This tree's directory pub fn dir(&self) -> &RepoPath { match self { MergedTree::Legacy(tree) => tree.dir(), MergedTree::Merge(conflict) => conflict.first().dir(), } } /// The `Store` associated with this tree. pub fn store(&self) -> &Arc<Store> { match self { MergedTree::Legacy(tree) => tree.store(), MergedTree::Merge(trees) => trees.first().store(), } } /// Base names of entries in this directory. pub fn names<'a>(&'a self) -> Box<dyn Iterator<Item = &'a RepoPathComponent> + 'a> { match self { MergedTree::Legacy(tree) => Box::new(tree.data().names()), MergedTree::Merge(conflict) => Box::new(all_tree_basenames(conflict)), } } /// The value at the given basename. The value can be `Resolved` even if /// `self` is a `Merge`, which happens if the value at the path can be /// trivially merged. Does not recurse, so if `basename` refers to a Tree, /// then a `TreeValue::Tree` will be returned. pub fn value(&self, basename: &RepoPathComponent) -> MergedTreeVal { match self { MergedTree::Legacy(tree) => match tree.value(basename) { Some(TreeValue::Conflict(conflict_id)) => { let path = tree.dir().join(basename); let conflict = tree.store().read_conflict(&path, conflict_id).unwrap(); MergedTreeVal::Conflict(conflict) } other => MergedTreeVal::Resolved(other), }, MergedTree::Merge(trees) => trees_value(trees, basename), } } /// Tries to resolve any conflicts, resolving any conflicts that can be /// automatically resolved and leaving the rest unresolved. The returned /// conflict will either be resolved or have the same number of sides as /// the input. pub fn resolve(&self) -> Result<Merge<Tree>, TreeMergeError> { match self { MergedTree::Legacy(tree) => Ok(Merge::resolved(tree.clone())), MergedTree::Merge(trees) => merge_trees(trees), } } /// An iterator over the conflicts in this tree, including subtrees. /// Recurses into subtrees and yields conflicts in those, but only if /// all sides are trees, so tree/file conflicts will be reported as a single /// conflict, not one for each path in the tree. // TODO: Restrict this by a matcher (or add a separate method for that). pub fn conflicts(&self) -> impl Iterator<Item = (RepoPathBuf, MergedTreeValue)> { ConflictIterator::new(self) } /// Whether this tree has conflicts. pub fn has_conflict(&self) -> bool { match self { MergedTree::Legacy(tree) => tree.has_conflict(), MergedTree::Merge(trees) => !trees.is_resolved(), } } /// Gets the `MergeTree` in a subdirectory of the current tree. If the path /// doesn't correspond to a tree in any of the inputs to the merge, then /// that entry will be replace by an empty tree in the result. pub fn sub_tree(&self, name: &RepoPathComponent) -> Option<MergedTree> { if let MergedTree::Legacy(tree) = self { tree.sub_tree(name).map(MergedTree::Legacy) } else { match self.value(name) { MergedTreeVal::Resolved(Some(TreeValue::Tree(sub_tree_id))) => { let subdir = self.dir().join(name); Some(MergedTree::resolved( self.store().get_tree(&subdir, sub_tree_id).unwrap(), )) } MergedTreeVal::Resolved(_) => None, MergedTreeVal::Conflict(merge) => { let merged_trees = merge.map(|value| match value { Some(TreeValue::Tree(sub_tree_id)) => { let subdir = self.dir().join(name); self.store().get_tree(&subdir, sub_tree_id).unwrap() } _ => { let subdir = self.dir().join(name); Tree::null(self.store().clone(), subdir.clone()) } }); Some(MergedTree::Merge(merged_trees)) } } } } /// The value at the given path. The value can be `Resolved` even if /// `self` is a `Conflict`, which happens if the value at the path can be /// trivially merged. pub fn path_value(&self, path: &RepoPath) -> MergedTreeValue { assert_eq!(self.dir(), RepoPath::root()); match path.split() { Some((dir, basename)) => match self.sub_tree_recursive(dir.components()) { None => Merge::absent(), Some(tree) => tree.value(basename).to_merge(), }, None => match self { MergedTree::Legacy(tree) => Merge::normal(TreeValue::Tree(tree.id().clone())), MergedTree::Merge(trees) => { trees.map(|tree| Some(TreeValue::Tree(tree.id().clone()))) } }, } } /// The tree's id pub fn id(&self) -> MergedTreeId { match self { MergedTree::Legacy(tree) => MergedTreeId::Legacy(tree.id().clone()), MergedTree::Merge(merge) => MergedTreeId::Merge(merge.map(|tree| tree.id().clone())), } } fn sub_tree_recursive(&self, mut components: RepoPathComponentsIter) -> Option<MergedTree> { if let Some(first) = components.next() { components.try_fold(self.sub_tree(first)?, |tree, name| tree.sub_tree(name)) } else { Some(self.clone()) } } /// Iterator over the entries matching the given matcher. Subtrees are /// visited recursively. Subtrees that differ between the current /// `MergedTree`'s terms are merged on the fly. Missing terms are treated as /// empty directories. Subtrees that conflict with non-trees are not /// visited. For example, if current tree is a merge of 3 trees, and the /// entry for 'foo' is a conflict between a change subtree and a symlink /// (i.e. the subdirectory was replaced by symlink in one side of the /// conflict), then the entry for `foo` itself will be emitted, but no /// entries from inside `foo/` from either of the trees will be. pub fn entries(&self) -> TreeEntriesIterator<'static> { TreeEntriesIterator::new(self.clone(), &EverythingMatcher) } /// Like `entries()` but restricted by a matcher. pub fn entries_matching<'matcher>( &self, matcher: &'matcher dyn Matcher, ) -> TreeEntriesIterator<'matcher> { TreeEntriesIterator::new(self.clone(), matcher) } /// Iterate over the differences between this tree and another tree. /// /// The files in a removed tree will be returned before a file that replaces /// it. pub fn diff<'matcher>( &self, other: &MergedTree, matcher: &'matcher dyn Matcher, ) -> TreeDiffIterator<'matcher> { TreeDiffIterator::new(self.clone(), other.clone(), matcher) } /// Stream of the differences between this tree and another tree. pub fn diff_stream<'matcher>( &self, other: &MergedTree, matcher: &'matcher dyn Matcher, ) -> TreeDiffStream<'matcher> { let concurrency = self.store().concurrency(); if concurrency <= 1 { Box::pin(futures::stream::iter(TreeDiffIterator::new( self.clone(), other.clone(), matcher, ))) } else { Box::pin(TreeDiffStreamImpl::new( self.clone(), other.clone(), matcher, concurrency, )) } } /// Collects lists of modified, added, and removed files between this tree /// and another tree. pub fn diff_summary( &self, other: &MergedTree, matcher: &dyn Matcher, ) -> BackendResult<DiffSummary> { let mut modified = vec![]; let mut added = vec![]; let mut removed = vec![]; for (file, diff) in self.diff(other, matcher) { let (before, after) = diff?; if before.is_absent() { added.push(file); } else if after.is_absent() { removed.push(file); } else { modified.push(file); } } modified.sort(); added.sort(); removed.sort(); Ok(DiffSummary { modified, added, removed, }) } /// Merges this tree with `other`, using `base` as base. pub fn merge( &self, base: &MergedTree, other: &MergedTree, ) -> Result<MergedTree, TreeMergeError> { if let (MergedTree::Legacy(this), MergedTree::Legacy(base), MergedTree::Legacy(other)) = (self, base, other) { let merged_tree = tree::merge_trees(this, base, other)?; Ok(MergedTree::legacy(merged_tree)) } else { // Convert legacy trees to merged trees and unwrap to `Merge<Tree>` let to_merge = |tree: &MergedTree| -> Result<Merge<Tree>, TreeMergeError> { match tree { MergedTree::Legacy(tree) => { let MergedTree::Merge(tree) = MergedTree::from_legacy_tree(tree.clone())? else { unreachable!(); }; Ok(tree) } MergedTree::Merge(conflict) => Ok(conflict.clone()), } }; let nested = Merge::from_vec(vec![to_merge(self)?, to_merge(base)?, to_merge(other)?]); let tree = merge_trees(&nested.flatten().simplify())?; // If the result can be resolved, then `merge_trees()` above would have returned // a resolved merge. However, that function will always preserve the arity of // conflicts it cannot resolve. So we simplify the conflict again // here to possibly reduce a complex conflict to a simpler one. let tree = tree.simplify(); // If debug assertions are enabled, check that the merge was idempotent. In // particular, that this last simplification doesn't enable further automatic // resolutions if cfg!(debug_assertions) { let re_merged = merge_trees(&tree).unwrap(); debug_assert_eq!(re_merged, tree); } Ok(MergedTree::Merge(tree)) } } } /// Type alias for the result from `MergedTree::diff_stream()`. We use a /// `Stream` instead of an `Iterator` so high-latency backends (e.g. cloud-based /// ones) can fetch trees asynchronously. pub type TreeDiffStream<'matcher> = Pin< Box< dyn Stream< Item = ( RepoPathBuf, BackendResult<(MergedTreeValue, MergedTreeValue)>, ), > + 'matcher, >, >; fn all_tree_basenames(trees: &Merge<Tree>) -> impl Iterator<Item = &RepoPathComponent> { trees .iter() .map(|tree| tree.data().names()) .kmerge() .dedup() } fn merged_tree_basenames<'a>( tree1: &'a MergedTree, tree2: &'a MergedTree, ) -> Box<dyn Iterator<Item = &'a RepoPathComponent> + 'a> { fn merge_iters<'a>( iter1: impl Iterator<Item = &'a RepoPathComponent> + 'a, iter2: impl Iterator<Item = &'a RepoPathComponent> + 'a, ) -> Box<dyn Iterator<Item = &'a RepoPathComponent> + 'a> { Box::new(iter1.merge(iter2).dedup()) } match (&tree1, &tree2) { (MergedTree::Legacy(before), MergedTree::Legacy(after)) => { merge_iters(before.data().names(), after.data().names()) } (MergedTree::Merge(before), MergedTree::Legacy(after)) => { merge_iters(all_tree_basenames(before), after.data().names()) } (MergedTree::Legacy(before), MergedTree::Merge(after)) => { merge_iters(before.data().names(), all_tree_basenames(after)) } (MergedTree::Merge(before), MergedTree::Merge(after)) => { merge_iters(all_tree_basenames(before), all_tree_basenames(after)) } } } fn merged_tree_entry_diff<'a>( before: &'a MergedTree, after: &'a MergedTree, ) -> impl Iterator<Item = (&'a RepoPathComponent, MergedTreeVal<'a>, MergedTreeVal<'a>)> { merged_tree_basenames(before, after).filter_map(|basename| { let value_before = before.value(basename); let value_after = after.value(basename); (value_after != value_before).then_some((basename, value_before, value_after)) }) } fn trees_value<'a>(trees: &'a Merge<Tree>, basename: &RepoPathComponent) -> MergedTreeVal<'a> { if let Some(tree) = trees.as_resolved() { return MergedTreeVal::Resolved(tree.value(basename)); } let value = trees.map(|tree| tree.value(basename)); if let Some(resolved) = value.resolve_trivial() { return MergedTreeVal::Resolved(*resolved); } MergedTreeVal::Conflict(value.map(|x| x.cloned())) } fn merge_trees(merge: &Merge<Tree>) -> Result<Merge<Tree>, TreeMergeError> { if let Some(tree) = merge.resolve_trivial() { return Ok(Merge::resolved(tree.clone())); } let base_tree = merge.first(); let store = base_tree.store(); let dir = base_tree.dir(); // Keep resolved entries in `new_tree` and conflicted entries in `conflicts` to // start with. Then we'll create the full trees later, and only if there are // any conflicts. let mut new_tree = backend::Tree::default(); let mut conflicts = vec![]; for basename in all_tree_basenames(merge) { let path_merge = merge.map(|tree| tree.value(basename).cloned()); let path = dir.join(basename); let path_merge = merge_tree_values(store, &path, path_merge)?; match path_merge.into_resolved() { Ok(value) => { new_tree.set_or_remove(basename, value); } Err(path_merge) => { conflicts.push((basename, path_merge.into_iter()));