// 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::borrow::Borrow;use std::cmp::max;use std::cmp::Ordering;use std::collections::BTreeMap;use std::collections::VecDeque;use std::iter;use std::iter::zip;use std::pin::Pin;use std::sync::Arc;use std::task::Context;use std::task::Poll;use std::vec; use either::Either;use futures::future::BoxFuture;use futures::stream::BoxStream;use futures::stream::StreamExt as _;use futures::Stream;use futures::TryStreamExt as _;use itertools::EitherOrBoth;use itertools::Itertools as _;use pollster::FutureExt as _; use crate::backend;use crate::backend::BackendResult;use crate::backend::MergedTreeId;use crate::backend::TreeId;use crate::backend::TreeValue;use crate::copies::CopiesTreeDiffEntry;use crate::copies::CopiesTreeDiffStream;use crate::copies::CopyRecords;use crate::matchers::EverythingMatcher;use crate::matchers::Matcher;use crate::merge::Merge;use crate::merge::MergeBuilder;use crate::merge::MergedTreeVal;use crate::merge::MergedTreeValue;use crate::repo_path::RepoPath;use crate::repo_path::RepoPathBuf;use crate::repo_path::RepoPathComponent;use crate::store::Store;use crate::tree::try_resolve_file_conflict;use crate::tree::Tree;use crate::tree_builder::TreeBuilder; /// Presents a view of a merged set of trees.#[derive(PartialEq, Eq, Clone, Debug)]pub struct MergedTree {    trees: Merge<Tree>,} 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 { trees }    }     /// 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(RepoPathBuf::root(), &tree_id)            })            .try_collect()?;        Ok(MergedTree {            trees: Merge::from_vec(new_trees),        })    }     /// Returns the underlying `Merge<Tree>`.    pub fn as_merge(&self) -> &Merge<Tree> {        &self.trees    }     /// Extracts the underlying `Merge<Tree>`.    pub fn take(self) -> Merge<Tree> {        self.trees    }     /// This tree's directory    pub fn dir(&self) -> &RepoPath {        self.trees.first().dir()    }     /// The `Store` associated with this tree.    pub fn store(&self) -> &Arc<Store> {        self.trees.first().store()    }     /// Base names of entries in this directory.    pub fn names<'a>(&'a self) -> Box<dyn Iterator<Item = &'a RepoPathComponent> + 'a> {        Box::new(all_tree_basenames(&self.trees))    }     /// 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 {        trees_value(&self.trees, basename)    }     /// Tries to resolve any conflicts, resolving any conflicts that can be    /// automatically resolved and leaving the rest unresolved.    pub fn resolve(&self) -> BackendResult<MergedTree> {        let merged = merge_trees(&self.trees)?;        // 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 simplified = merged.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(&simplified).unwrap();            debug_assert_eq!(re_merged, simplified);        }        Ok(MergedTree { trees: simplified })    }     /// 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, BackendResult<MergedTreeValue>)> + use<> {        ConflictIterator::new(self)    }     /// Whether this tree has conflicts.    pub fn has_conflict(&self) -> bool {        !self.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) -> BackendResult<Option<MergedTree>> {        match self.value(name).into_resolved() {            Ok(Some(TreeValue::Tree(sub_tree_id))) => {                let subdir = self.dir().join(name);                Ok(Some(MergedTree::resolved(                    self.store().get_tree(subdir, sub_tree_id)?,                )))            }            Ok(_) => Ok(None),            Err(merge) => {                let trees = merge.try_map(|value| match value {                    Some(TreeValue::Tree(sub_tree_id)) => {                        let subdir = self.dir().join(name);                        self.store().get_tree(subdir, sub_tree_id)                    }                    _ => {                        let subdir = self.dir().join(name);                        Ok(Tree::empty(self.store().clone(), subdir))                    }                })?;                Ok(Some(MergedTree { 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) -> BackendResult<MergedTreeValue> {        assert_eq!(self.dir(), RepoPath::root());        match path.split() {            Some((dir, basename)) => match self.sub_tree_recursive(dir)? {                None => Ok(Merge::absent()),                Some(tree) => Ok(tree.value(basename).cloned()),            },            None => Ok(self                .trees                .map(|tree| Some(TreeValue::Tree(tree.id().clone())))),        }    }     /// The tree's id    pub fn id(&self) -> MergedTreeId {        MergedTreeId::Merge(self.trees.map(|tree| tree.id().clone()))    }     /// Look up the tree at the given path.    pub fn sub_tree_recursive(&self, path: &RepoPath) -> BackendResult<Option<MergedTree>> {        let mut current_tree = self.clone();        for name in path.components() {            match current_tree.sub_tree(name)? {                None => {                    return Ok(None);                }                Some(sub_tree) => {                    current_tree = sub_tree;                }            }        }        Ok(Some(current_tree))    }     /// 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> {        self.entries_matching(&EverythingMatcher)    }     /// Like `entries()` but restricted by a matcher.    pub fn entries_matching<'matcher>(        &self,        matcher: &'matcher dyn Matcher,    ) -> TreeEntriesIterator<'matcher> {        TreeEntriesIterator::new(&self.trees, matcher)    }     /// Stream of 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_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.trees,                &other.trees,                matcher,            )))        } else {            Box::pin(TreeDiffStreamImpl::new(                &self.trees,                &other.trees,                matcher,                concurrency,            ))        }    }     /// Like `diff_stream()` but takes the given copy records into account.    pub fn diff_stream_with_copies<'a>(        &self,        other: &MergedTree,        matcher: &'a dyn Matcher,        copy_records: &'a CopyRecords,    ) -> BoxStream<'a, CopiesTreeDiffEntry> {        let stream = self.diff_stream(other, matcher);        Box::pin(CopiesTreeDiffStream::new(            stream,            self.clone(),            other.clone(),            copy_records,        ))    }     /// Merges this tree with `other`, using `base` as base. Any conflicts will    /// be resolved recursively if possible.    pub fn merge(&self, base: &MergedTree, other: &MergedTree) -> BackendResult<MergedTree> {        self.merge_no_resolve(base, other).resolve()    }     /// Merges this tree with `other`, using `base` as base, without attempting    /// to resolve file conflicts.    pub fn merge_no_resolve(&self, base: &MergedTree, other: &MergedTree) -> MergedTree {        let nested = Merge::from_vec(vec![            self.trees.clone(),            base.trees.clone(),            other.trees.clone(),        ]);        MergedTree {            trees: nested.flatten().simplify(),        }    }} /// A single entry in a tree diff.pub struct TreeDiffEntry {    /// The path.    pub path: RepoPathBuf,    /// The resolved tree values if available.    pub values: BackendResult<(MergedTreeValue, MergedTreeValue)>,} /// 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> = BoxStream<'matcher, TreeDiffEntry>; fn all_tree_basenames(trees: &Merge<Tree>) -> impl Iterator<Item = &RepoPathComponent> {    trees        .iter()        .map(|tree| tree.data().names())        .kmerge()        .dedup()} fn all_tree_entries(    trees: &Merge<Tree>,) -> impl Iterator<Item = (&RepoPathComponent, MergedTreeVal<'_>)> {    if let Some(tree) = trees.as_resolved() {        let iter = tree            .entries_non_recursive()            .map(|entry| (entry.name(), Merge::normal(entry.value())));        Either::Left(iter)    } else {        let iter = all_merged_tree_entries(trees).map(|(name, values)| {            // TODO: move resolve_trivial() to caller?            let values = match values.resolve_trivial() {                Some(resolved) => Merge::resolved(*resolved),                None => values,            };            (name, values)        });        Either::Right(iter)    }} /// Suppose the given `trees` aren't resolved, iterates `(name, values)` pairs/// non-recursively. This also works if `trees` are resolved, but is more costly/// than `tree.entries_non_recursive()`.fn all_merged_tree_entries(    trees: &Merge<Tree>,) -> impl Iterator<Item = (&RepoPathComponent, MergedTreeVal<'_>)> {    let mut entries_iters = trees        .iter()        .map(|tree| tree.entries_non_recursive().peekable())        .collect_vec();    iter::from_fn(move || {        let next_name = entries_iters            .iter_mut()            .filter_map(|iter| iter.peek())            .map(|entry| entry.name())            .min()?;        let values: MergeBuilder<_> = entries_iters            .iter_mut()            .map(|iter| {                let entry = iter.next_if(|entry| entry.name() == next_name)?;                Some(entry.value())            })            .collect();        Some((next_name, values.build()))    })} fn merged_tree_entry_diff<'a>(    trees1: &'a Merge<Tree>,    trees2: &'a Merge<Tree>,) -> impl Iterator<Item = (&'a RepoPathComponent, MergedTreeVal<'a>, MergedTreeVal<'a>)> {    itertools::merge_join_by(        all_tree_entries(trees1),        all_tree_entries(trees2),        |(name1, _), (name2, _)| name1.cmp(name2),    )    .map(|entry| match entry {        EitherOrBoth::Both((name, value1), (_, value2)) => (name, value1, value2),        EitherOrBoth::Left((name, value1)) => (name, value1, Merge::absent()),        EitherOrBoth::Right((name, value2)) => (name, Merge::absent(), value2),    })    .filter(|(_, value1, value2)| value1 != value2)} fn trees_value<'a>(trees: &'a Merge<Tree>, basename: &RepoPathComponent) -> MergedTreeVal<'a> {    if let Some(tree) = trees.as_resolved() {        return Merge::resolved(tree.value(basename));    }    let value = trees.map(|tree| tree.value(basename));    if let Some(resolved) = value.resolve_trivial() {        return Merge::resolved(*resolved);    }    value} /// The returned conflict will either be resolved or have the same number of/// sides as the input.fn merge_trees(merge: &Merge<Tree>) -> BackendResult<Merge<Tree>> {    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![];    // TODO: Merge values concurrently    for (basename, path_merge) in all_merged_tree_entries(merge) {        let path = dir.join(basename);        let path_merge = merge_tree_values(store, &path, &path_merge).block_on()?;        match path_merge.into_resolved() {            Ok(value) => {                new_tree.set_or_remove(basename, value);            }            Err(path_merge) => {                conflicts.push((basename, path_merge.into_iter()));            }        };    }    if conflicts.is_empty() {        let new_tree_id = store.write_tree(dir, new_tree).block_on()?;        Ok(Merge::resolved(new_tree_id))    } else {        // For each side of the conflict, overwrite the entries in `new_tree` with the        // values from  `conflicts`. Entries that are not in `conflicts` will remain        // unchanged and will be reused for each side.        let tree_count = merge.iter().len();        let mut new_trees = Vec::with_capacity(tree_count);        for _ in 0..tree_count {            for (basename, path_conflict) in &mut conflicts {                new_tree.set_or_remove(basename, path_conflict.next().unwrap());            }            let tree = store.write_tree(dir, new_tree.clone()).block_on()?;            new_trees.push(tree);        }        Ok(Merge::from_vec(new_trees))    }} /// Tries to resolve a conflict between tree values. Returns/// Ok(Merge::normal(value)) if the conflict was resolved, and/// Ok(Merge::absent()) if the path should be removed. Returns the/// conflict unmodified if it cannot be resolved automatically.async fn merge_tree_values(    store: &Arc<Store>,    path: &RepoPath,    values: &MergedTreeVal<'_>,) -> BackendResult<MergedTreeValue> {    if let Some(resolved) = values.resolve_trivial() {        return Ok(Merge::resolved(resolved.cloned()));    }

Lines 1–500 of 1209. Load more