// Copyright 2020 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. #![expect(missing_docs)] use std::collections::HashMap;use std::collections::HashSet;use std::slice;use std::sync::Arc; use futures::StreamExt as _;use futures::TryStreamExt as _;use futures::future::try_join_all;use futures::try_join;use indexmap::IndexMap;use indexmap::IndexSet;use itertools::Itertools as _;use tracing::instrument; use crate::backend::BackendError;use crate::backend::BackendResult;use crate::backend::CommitId;use crate::commit::Commit;use crate::commit::CommitIteratorExt as _;use crate::commit::conflict_label_for_commits;use crate::commit_builder::CommitBuilder;use crate::conflict_labels::ConflictLabels;use crate::index::Index;use crate::index::IndexResult;use crate::index::ResolvedChangeTargets;use crate::iter_util::fallible_any;use crate::matchers::FilesMatcher;use crate::matchers::Matcher;use crate::matchers::Visit;use crate::merge::Diff;use crate::merge::Merge;use crate::merged_tree::MergedTree;use crate::merged_tree_builder::MergedTreeBuilder;use crate::repo::MutableRepo;use crate::repo::Repo;use crate::repo_path::RepoPath;use crate::revset::RevsetExpression;use crate::revset::RevsetStreamExt as _;use crate::store::Store; /// Merges `commits` and tries to resolve any conflicts recursively.#[instrument(skip(repo))]pub async fn merge_commit_trees(repo: &dyn Repo, commits: &[Commit]) -> BackendResult<MergedTree> {    if let [commit] = commits {        Ok(commit.tree())    } else {        merge_commit_trees_no_resolve(repo, commits)            .await?            .resolve()            .await    }} /// Merges `commits` without attempting to resolve file conflicts.pub async fn merge_commit_trees_no_resolve(    repo: &dyn Repo,    commits: &[Commit],) -> BackendResult<MergedTree> {    if let [commit] = commits {        Ok(commit.tree())    } else {        merge_commit_trees_no_resolve_without_repo(repo.store(), repo.index(), commits).await    }} /// Merges `commits` without attempting to resolve file conflicts.#[instrument(skip(index))]pub async fn merge_commit_trees_no_resolve_without_repo(    store: &Arc<Store>,    index: &dyn Index,    commits: &[Commit],) -> BackendResult<MergedTree> {    let commit_ids = commits        .iter()        .map(|commit| commit.id().clone())        .collect_vec();    let commit_id_merge = find_recursive_merge_commits(store, index, commit_ids)?;    let tree_merge: Merge<(MergedTree, String)> = commit_id_merge        .try_map_async(async |commit_id| {            let commit = store.get_commit_async(commit_id).await?;            Ok::<_, BackendError>((commit.tree(), commit.conflict_label()))        })        .await?;    Ok(MergedTree::merge_no_resolve(tree_merge))} /// Find the commits to use as input to the recursive merge algorithm.pub fn find_recursive_merge_commits(    store: &Arc<Store>,    index: &dyn Index,    mut commit_ids: Vec<CommitId>,) -> BackendResult<Merge<CommitId>> {    if commit_ids.is_empty() {        Ok(Merge::resolved(store.root_commit_id().clone()))    } else if commit_ids.len() == 1 {        Ok(Merge::resolved(commit_ids.pop().unwrap()))    } else {        let mut result = Merge::resolved(commit_ids[0].clone());        for (i, other_commit_id) in commit_ids.iter().enumerate().skip(1) {            let ancestor_ids = index                .common_ancestors(&commit_ids[0..i], &commit_ids[i..][..1])                // TODO: indexing error shouldn't be a "BackendError"                .map_err(|err| BackendError::Other(err.into()))?;            let ancestor_merge = find_recursive_merge_commits(store, index, ancestor_ids)?;            result = Merge::from_vec(vec![                result,                ancestor_merge,                Merge::resolved(other_commit_id.clone()),            ])            .flatten();        }        Ok(result)    }} /// Restore matching paths from the source into the destination.pub async fn restore_tree(    source: &MergedTree,    destination: &MergedTree,    source_label: String,    destination_label: String,    matcher: &dyn Matcher,) -> BackendResult<MergedTree> {    if matcher.visit(RepoPath::root()) == Visit::AllRecursively {        // Optimization for a common case        return Ok(source.clone());    }    let mut diff_stream = source.diff_stream(destination, matcher);    let mut paths = Vec::new();    while let Some(entry) = diff_stream.next().await {        // TODO: We should be able to not traverse deeper in the diff if the matcher        // matches an entire subtree.        paths.push(entry.path);    }    let matcher = FilesMatcher::new(paths);     let select_matching =        async |tree: &MergedTree, labels: ConflictLabels| -> BackendResult<MergedTree> {            let empty_tree_ids = Merge::repeated(                tree.store().empty_tree_id().clone(),                tree.tree_ids().num_sides(),            );            let labeled_empty_tree = MergedTree::new(tree.store().clone(), empty_tree_ids, labels);            let mut builder = MergedTreeBuilder::new(labeled_empty_tree);            for (path, value) in tree.entries_matching(&matcher) {                // TODO: if https://github.com/jj-vcs/jj/issues/4152 is implemented, we will need                // to expand resolved conflicts into `Merge::repeated(value, num_sides)`.                builder.set_or_remove(path, value?);            }            builder.write_tree().await        };     const RESTORE_BASE_LABEL: &str = "base files for restore";     // To avoid confusion between the destination tree and the base tree, we add a    // prefix to the conflict labels of the base tree.    let base_labels = ConflictLabels::from_merge(destination.labels().as_merge().map(|label| {        if label.is_empty() || label.starts_with(RESTORE_BASE_LABEL) {            label.clone()        } else {            format!("{RESTORE_BASE_LABEL} (from {label})")        }    }));     // Merging the trees this way ensures that when restoring a conflicted file into    // a conflicted commit, we preserve the labels of both commits even if the    // commits had different conflict labels. The labels we add here for    // non-conflicted trees will generally not be visible to users since they will    // always be removed during simplification when materializing any individual    // file. However, they could be useful in the future if we add a command which    // shows the labels for all the sides of a conflicted commit, and they are also    // useful for debugging.    // TODO: using a merge is required for retaining conflict labels when restoring    // from/into conflicted trees, but maybe we could optimize the case where both    // trees are already resolved.    MergedTree::merge(Merge::from_vec(vec![        (            destination.clone(),            format!("{destination_label} (restore destination)"),        ),        (            select_matching(destination, base_labels).await?,            format!("{RESTORE_BASE_LABEL} (from {destination_label})"),        ),        (            select_matching(source, source.labels().clone()).await?,            format!("restored files (from {source_label})"),        ),    ]))    .await} pub async fn rebase_commit(    mut_repo: &mut MutableRepo,    old_commit: Commit,    new_parents: Vec<CommitId>,) -> BackendResult<Commit> {    let rewriter = CommitRewriter::new(mut_repo, old_commit, new_parents);    let builder = rewriter.rebase().await?;    builder.write().await} /// Helps rewrite a commit.pub struct CommitRewriter<'repo> {    mut_repo: &'repo mut MutableRepo,    old_commit: Commit,    new_parents: Vec<CommitId>,} impl<'repo> CommitRewriter<'repo> {    /// Create a new instance.    pub fn new(        mut_repo: &'repo mut MutableRepo,        old_commit: Commit,        new_parents: Vec<CommitId>,    ) -> Self {        Self {            mut_repo,            old_commit,            new_parents,        }    }     /// Returns the `MutableRepo`.    pub fn repo_mut(&mut self) -> &mut MutableRepo {        self.mut_repo    }     /// The commit we're rewriting.    pub fn old_commit(&self) -> &Commit {        &self.old_commit    }     /// Get the old commit's intended new parents.    pub fn new_parents(&self) -> &[CommitId] {        &self.new_parents    }     /// Set the old commit's intended new parents.    pub fn set_new_parents(&mut self, new_parents: Vec<CommitId>) {        self.new_parents = new_parents;    }     /// Set the old commit's intended new parents to be the rewritten versions    /// of the given parents.    pub fn set_new_rewritten_parents(&mut self, unrewritten_parents: &[CommitId]) {        self.new_parents = self.mut_repo.new_parents(unrewritten_parents);    }     /// Update the intended new parents by replacing any occurrence of    /// `old_parent` by `new_parents`.    pub fn replace_parent<'a>(        &mut self,        old_parent: &CommitId,        new_parents: impl IntoIterator<Item = &'a CommitId>,    ) {        if let Some(i) = self.new_parents.iter().position(|p| p == old_parent) {            self.new_parents                .splice(i..i + 1, new_parents.into_iter().cloned());            let mut unique = HashSet::new();            self.new_parents.retain(|p| unique.insert(p.clone()));        }    }     /// Checks if the intended new parents are different from the old commit's    /// parents.    pub fn parents_changed(&self) -> bool {        self.new_parents != self.old_commit.parent_ids()    }     /// If a merge commit would end up with one parent being an ancestor of the    /// other, then filter out the ancestor.    pub async fn simplify_ancestor_merge(&mut self) -> IndexResult<()> {        let head_set: HashSet<_> = self            .mut_repo            .index()            .heads(&mut self.new_parents.iter())            .await?            .into_iter()            .collect();        self.new_parents.retain(|parent| head_set.contains(parent));        Ok(())    }     /// Records the old commit as abandoned with the new parents.    ///    /// This is equivalent to `reparent(settings).abandon()`, but is cheaper.    pub fn abandon(self) {        let old_commit_id = self.old_commit.id().clone();        let new_parents = self.new_parents;        self.mut_repo            .record_abandoned_commit_with_parents(old_commit_id, new_parents);    }     /// Rebase the old commit onto the new parents. Returns a `CommitBuilder`    /// for the new commit. Returns `None` if the commit was abandoned.    pub async fn rebase_with_empty_behavior(        self,        empty: EmptyBehavior,    ) -> BackendResult<Option<CommitBuilder<'repo>>> {        let old_parents_fut = self.old_commit.parents();        let new_parents_fut = try_join_all(            self.new_parents                .iter()                .map(|new_parent_id| self.mut_repo.store().get_commit_async(new_parent_id)),        );        let (old_parents, new_parents) = try_join!(old_parents_fut, new_parents_fut)?;        let old_parent_trees = old_parents            .iter()            .map(|parent| parent.tree_ids().clone())            .collect_vec();        let new_parent_trees = new_parents            .iter()            .map(|parent| parent.tree_ids().clone())            .collect_vec();         let (was_empty, new_tree) = if new_parent_trees == old_parent_trees {            (                // Optimization: was_empty is only used for newly empty, but when the                // parents haven't changed it can't be newly empty.                true,                // Optimization: Skip merging.                self.old_commit.tree(),            )        } else {            // We wouldn't need to resolve merge conflicts here if the            // same-change rule is "keep". See 9d4a97381f30 "rewrite: don't            // resolve intermediate parent tree when rebasing" for details.            let old_base_tree_fut = merge_commit_trees(self.mut_repo, &old_parents);            let new_base_tree_fut = merge_commit_trees(self.mut_repo, &new_parents);            let old_tree = self.old_commit.tree();            let (old_base_tree, new_base_tree) = try_join!(old_base_tree_fut, new_base_tree_fut)?;            (                old_base_tree.tree_ids() == self.old_commit.tree_ids(),                MergedTree::merge(Merge::from_vec(vec![                    (                        new_base_tree,                        format!(                            "{} (rebase destination)",                            conflict_label_for_commits(&new_parents)                        ),                    ),                    (                        old_base_tree,                        format!(                            "{} (parents of rebased revision)",                            conflict_label_for_commits(&old_parents)                        ),                    ),                    (                        old_tree,                        format!("{} (rebased revision)", self.old_commit.conflict_label()),                    ),                ]))                .await?,            )        };        // Ensure we don't abandon commits with multiple parents (merge commits), even        // if they're empty.        if let [parent] = &new_parents[..] {            let should_abandon = match empty {                EmptyBehavior::Keep => false,                EmptyBehavior::AbandonNewlyEmpty => {                    parent.tree_ids() == new_tree.tree_ids() && !was_empty                }                EmptyBehavior::AbandonAllEmpty => parent.tree_ids() == new_tree.tree_ids(),            };            if should_abandon {                self.abandon();                return Ok(None);            }        }         let builder = self            .mut_repo            .rewrite_commit(&self.old_commit)            .set_parents(self.new_parents)            .set_tree(new_tree);        Ok(Some(builder))    }     /// Rebase the old commit onto the new parents. Returns a `CommitBuilder`    /// for the new commit.    pub async fn rebase(self) -> BackendResult<CommitBuilder<'repo>> {        let builder = self.rebase_with_empty_behavior(EmptyBehavior::Keep).await?;        Ok(builder.unwrap())    }     /// Rewrite the old commit onto the new parents without changing its    /// contents. Returns a `CommitBuilder` for the new commit.    pub fn reparent(self) -> CommitBuilder<'repo> {        self.mut_repo            .rewrite_commit(&self.old_commit)            .set_parents(self.new_parents)    }} #[derive(Debug)]pub enum RebasedCommit {    Rewritten(Commit),    Abandoned { parent_id: CommitId },} pub async fn rebase_commit_with_options(    mut rewriter: CommitRewriter<'_>,    options: &RebaseOptions,) -> BackendResult<RebasedCommit> {    // If specified, don't create commit where one parent is an ancestor of another.    if options.simplify_ancestor_merge {        rewriter            .simplify_ancestor_merge()            .await            // TODO: indexing error shouldn't be a "BackendError"            .map_err(|err| BackendError::Other(err.into()))?;    }     let single_parent = match &rewriter.new_parents[..] {        [parent_id] => Some(parent_id.clone()),        _ => None,    };    let new_parents_len = rewriter.new_parents.len();    if let Some(builder) = rewriter.rebase_with_empty_behavior(options.empty).await? {        let new_commit = builder.write().await?;        Ok(RebasedCommit::Rewritten(new_commit))    } else {        assert_eq!(new_parents_len, 1);        Ok(RebasedCommit::Abandoned {            parent_id: single_parent.unwrap(),        })    }} /// Moves changes from `sources` to the `destination` parent, returns new tree.// TODO: pass conflict labels as argument to provide more specific informationpub async fn rebase_to_dest_parent(    repo: &dyn Repo,    sources: &[Commit],    destination: &Commit,) -> BackendResult<MergedTree> {    if let [source] = sources        && source.parent_ids() == destination.parent_ids()    {        return Ok(source.tree());    }     let diffs: Vec<_> = try_join_all(sources.iter().map(async |source| -> BackendResult<_> {        Ok(Diff::new(            (                source.parent_tree(repo).await?,                format!(                    "{} (original parents)",                    source.parents_conflict_label().await?                ),            ),            (                source.tree(),                format!("{} (original revision)", source.conflict_label()),            ),        ))    }))    .await?;    MergedTree::merge(Merge::from_diffs(        (            destination.parent_tree(repo).await?,            format!(                "{} (new parents)",                destination.parents_conflict_label().await?            ),        ),        diffs,    ))    .await} #[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]pub enum EmptyBehavior {    /// Always keep empty commits    #[default]    Keep,    /// Skips commits that would be empty after the rebase, but that were not    /// originally empty.    /// Will never skip merge commits with multiple non-empty parents.    AbandonNewlyEmpty,    /// Skips all empty commits, including ones that were empty before the

Lines 1–500 of 1525. Load more