// 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::future::try_join_all;use futures::try_join;use indexmap::IndexMap;use indexmap::IndexSet;use itertools::Itertools as _;use pollster::FutureExt as _;use tracing::instrument; use crate::backend::BackendError;use crate::backend::BackendResult;use crate::backend::CommitId;use crate::backend::MergedTreeId;use crate::commit::Commit;use crate::commit::CommitIteratorExt as _;use crate::commit_builder::CommitBuilder;use crate::index::Index;use crate::index::IndexResult;use crate::iter_util::fallible_any;use crate::matchers::Matcher;use crate::matchers::Visit;use crate::merge::Merge;use crate::merged_tree::MergedTree;use crate::merged_tree::MergedTreeBuilder;use crate::merged_tree::TreeDiffEntry;use crate::repo::MutableRepo;use crate::repo::Repo;use crate::repo_path::RepoPath;use crate::revset::RevsetExpression;use crate::revset::RevsetIteratorExt 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 {        commit.tree_async().await    } else {        merge_commit_trees_no_resolve_without_repo(repo.store(), repo.index(), commits)            .await?            .resolve()            .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 = commit_id_merge        .try_map_async(async |commit_id| {            let commit = store.get_commit_async(commit_id).await?;            let tree = commit.tree_async().await?;            Ok::<_, BackendError>(tree.into_merge())        })        .await?;    Ok(MergedTree::new(tree_merge.flatten().simplify()))} /// 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,    matcher: &dyn Matcher,) -> BackendResult<MergedTreeId> {    if matcher.visit(RepoPath::root()) == Visit::AllRecursively {        // Optimization for a common case        Ok(source.id())    } else {        // TODO: We should be able to not traverse deeper in the diff if the matcher        // matches an entire subtree.        let mut tree_builder = MergedTreeBuilder::new(destination.id().clone());        // TODO: handle copy tracking        let mut diff_stream = source.diff_stream(destination, matcher);        while let Some(TreeDiffEntry {            path: repo_path,            values,        }) = diff_stream.next().await        {            let source_value = values?.before;            tree_builder.set_or_remove(repo_path, source_value);        }        tree_builder.write_tree(destination.store())    }} 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()} /// 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 fn simplify_ancestor_merge(&mut self) -> IndexResult<()> {        let head_set: HashSet<_> = self            .mut_repo            .index()            .heads(&mut self.new_parents.iter())?            .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_async();        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_id().clone())            .collect_vec();        let new_parent_trees = new_parents            .iter()            .map(|parent| parent.tree_id().clone())            .collect_vec();         let (was_empty, new_tree_id) = 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_id().clone(),            )        } 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_fut = self.old_commit.tree_async();            let (old_base_tree, new_base_tree, old_tree) =                try_join!(old_base_tree_fut, new_base_tree_fut, old_tree_fut)?;            (                old_base_tree.id() == *self.old_commit.tree_id(),                new_base_tree.merge(old_base_tree, old_tree).await?.id(),            )        };        // 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_id() == new_tree_id && !was_empty,                EmptyBehavior::AbandonAllEmpty => *parent.tree_id() == new_tree_id,            };            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_id(new_tree_id);        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)    }} pub enum RebasedCommit {    Rewritten(Commit),    Abandoned { parent_id: CommitId },} pub 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()            // 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)        .block_on()?    {        let new_commit = builder.write()?;        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.pub 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 source.tree();    }    sources.iter().try_fold(        destination.parent_tree(repo)?,        |destination_tree, source| {            let source_parent_tree = source.parent_tree(repo)?;            let source_tree = source.tree()?;            destination_tree                .merge(source_parent_tree, source_tree)                .block_on()        },    )} #[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    /// rebase.    /// Will never skip merge commits with multiple non-empty parents.    AbandonAllEmpty,} /// Controls the configuration of a rebase.// If we wanted to add a flag similar to `git rebase --ignore-date`, then this// makes it much easier by ensuring that the only changes required are to// change the RebaseOptions construction in the CLI, and changing the// rebase_commit function to actually use the flag, and ensure we don't need to// plumb it in.#[derive(Clone, Debug, Default)]pub struct RebaseOptions {    pub empty: EmptyBehavior,    pub rewrite_refs: RewriteRefsOptions,    /// If a merge commit would end up with one parent being an ancestor of the    /// other, then filter out the ancestor.    pub simplify_ancestor_merge: bool,} /// Configuration for [`MutableRepo::update_rewritten_references()`].#[derive(Clone, Debug, Default)]pub struct RewriteRefsOptions {    /// Whether or not delete bookmarks pointing to the abandoned commits.    ///    /// If false, bookmarks will be moved to the parents of the abandoned    /// commit.    pub delete_abandoned_bookmarks: bool,} pub struct MoveCommitsStats {    /// The number of commits in the target set which were rebased.    pub num_rebased_targets: u32,    /// The number of descendant commits which were rebased.    pub num_rebased_descendants: u32,    /// The number of commits for which rebase was skipped, due to the commit    /// already being in place.    pub num_skipped_rebases: u32,    /// The number of commits which were abandoned due to being empty.    pub num_abandoned_empty: u32,    /// The rebased commits    pub rebased_commits: HashMap<CommitId, RebasedCommit>,} /// Target and destination commits to be rebased by [`move_commits()`].#[derive(Clone, Debug)]pub struct MoveCommitsLocation {    pub new_parent_ids: Vec<CommitId>,    pub new_child_ids: Vec<CommitId>,    pub target: MoveCommitsTarget,} #[derive(Clone, Debug)]pub enum MoveCommitsTarget {    /// The commits to be moved. Commits should be mutable and in reverse    /// topological order.    Commits(Vec<CommitId>),    /// The root commits to be moved, along with all their descendants.    Roots(Vec<CommitId>),} #[derive(Clone, Debug)]pub struct ComputedMoveCommits {    target_commit_ids: IndexSet<CommitId>,    descendants: Vec<Commit>,    commit_new_parents_map: HashMap<CommitId, Vec<CommitId>>,    to_abandon: HashSet<CommitId>,} impl ComputedMoveCommits {    fn empty() -> Self {        Self {            target_commit_ids: IndexSet::new(),            descendants: vec![],            commit_new_parents_map: HashMap::new(),            to_abandon: HashSet::new(),        }    }     /// Records a set of commits to abandon while rebasing.    ///    /// Abandoning these commits while rebasing ensures that their descendants    /// are still rebased properly. [`MutableRepo::record_abandoned_commit`] is    /// similar, but it can lead to issues when abandoning a target commit    /// before the rebase.    pub fn record_to_abandon(&mut self, commit_ids: impl IntoIterator<Item = CommitId>) {        self.to_abandon.extend(commit_ids);    }     pub fn apply(        self,        mut_repo: &mut MutableRepo,        options: &RebaseOptions,    ) -> BackendResult<MoveCommitsStats> {        apply_move_commits(mut_repo, self, options)    }} /// Moves `loc.target` commits from their current location to a new location in/// the graph.////// Commits in `target` are rebased onto the new parents given by/// `new_parent_ids`, while the `new_child_ids` commits are rebased onto the/// heads of the commits in `targets`. This assumes that commits in `target` and

Lines 1–500 of 1342. Load more