// 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. #![allow(missing_docs)] use std::collections::HashMap;use std::collections::HashSet;use std::sync::Arc; use futures::StreamExt as _;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::dag_walk;use crate::index::Index;use crate::index::IndexError;use crate::matchers::Matcher;use crate::matchers::Visit;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 fn merge_commit_trees(repo: &dyn Repo, commits: &[Commit]) -> BackendResult<MergedTree> {    if let [commit] = commits {        commit.tree()    } else {        merge_commit_trees_no_resolve_without_repo(repo.store(), repo.index(), commits)?.resolve()    }} /// Merges `commits` without attempting to resolve file conflicts.#[instrument(skip(index))]pub fn merge_commit_trees_no_resolve_without_repo(    store: &Arc<Store>,    index: &dyn Index,    commits: &[Commit],) -> BackendResult<MergedTree> {    if commits.is_empty() {        Ok(store.get_root_tree(&store.empty_merged_tree_id())?)    } else {        let mut new_tree = commits[0].tree()?;        let commit_ids = commits            .iter()            .map(|commit| commit.id().clone())            .collect_vec();        for (i, other_commit) in commits.iter().enumerate().skip(1) {            let ancestor_ids = index.common_ancestors(&commit_ids[0..i], &commit_ids[i..][..1]);            let ancestors: Vec<_> = ancestor_ids                .iter()                .map(|id| store.get_commit(id))                .try_collect()?;            let ancestor_tree =                merge_commit_trees_no_resolve_without_repo(store, index, &ancestors)?;            let other_tree = other_commit.tree()?;            new_tree = new_tree.merge_no_resolve(&ancestor_tree, &other_tree);        }        Ok(new_tree)    }} /// Restore matching paths from the source into the destination.pub 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());        async {            // 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, _destination_value) = values?;                tree_builder.set_or_remove(repo_path, source_value);            }            Ok::<(), BackendError>(())        }        .block_on()?;        tree_builder.write_tree(destination.store())    }} pub 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()?;    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 mut_repo(&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) -> Result<(), IndexError> {        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 fn rebase_with_empty_behavior(        self,        empty: EmptyBehaviour,    ) -> BackendResult<Option<CommitBuilder<'repo>>> {        let old_parents: Vec<_> = self.old_commit.parents().try_collect()?;        let old_parent_trees = old_parents            .iter()            .map(|parent| parent.tree_id().clone())            .collect_vec();        let new_parents: Vec<_> = self            .new_parents            .iter()            .map(|new_parent_id| self.mut_repo.store().get_commit(new_parent_id))            .try_collect()?;        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 {            let old_base_tree = merge_commit_trees(self.mut_repo, &old_parents)?;            let new_base_tree = merge_commit_trees(self.mut_repo, &new_parents)?;            let old_tree = self.old_commit.tree()?;            (                old_base_tree.id() == *self.old_commit.tree_id(),                new_base_tree.merge(&old_base_tree, &old_tree)?.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 {                EmptyBehaviour::Keep => false,                EmptyBehaviour::AbandonNewlyEmpty => *parent.tree_id() == new_tree_id && !was_empty,                EmptyBehaviour::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 fn rebase(self) -> BackendResult<CommitBuilder<'repo>> {        let builder = self.rebase_with_empty_behavior(EmptyBehaviour::Keep)?;        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 {        // TODO: BackendError is not the right error here because        // the error does not come from `Backend`, but `Index`.        rewriter            .simplify_ancestor_merge()            .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)? {        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 {        if 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)        },    )} #[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]pub enum EmptyBehaviour {    /// 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: EmptyBehaviour,    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,} #[derive(Default)]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.    pub num_abandoned: u32,} pub enum MoveCommitsTarget {    /// The commits to be moved. Commits should be mutable and in reverse    /// topological order.    Commits(Vec<Commit>),    /// The root commits to be moved, along with all their descendants.    Roots(Vec<Commit>),} /// Moves `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_children` commits are rebased onto the/// heads of the commits in `targets`. This assumes that commits in `target` and/// `new_children` can be rewritten, and there will be no cycles in the/// resulting graph. Commits in `target` should be in reverse topological order.pub fn move_commits(    mut_repo: &mut MutableRepo,    new_parent_ids: &[CommitId],    new_children: &[Commit],    target: &MoveCommitsTarget,    options: &RebaseOptions,) -> BackendResult<MoveCommitsStats> {    let target_commits: Vec<Commit>;    let target_commit_ids: HashSet<_>;    let connected_target_commits: Vec<Commit>;    let connected_target_commits_internal_parents: HashMap<CommitId, Vec<CommitId>>;    let target_roots: HashSet<CommitId>;     match target {        MoveCommitsTarget::Commits(commits) => {            if commits.is_empty() {                return Ok(MoveCommitsStats::default());            }             target_commits = commits.clone();            target_commit_ids = target_commits.iter().ids().cloned().collect();             connected_target_commits =                RevsetExpression::commits(target_commits.iter().ids().cloned().collect_vec())                    .connected()                    .evaluate(mut_repo)                    .map_err(|err| err.expect_backend_error())?                    .iter()                    .commits(mut_repo.store())                    .try_collect()                    // TODO: Return evaluation error to caller                    .map_err(|err| err.expect_backend_error())?;            connected_target_commits_internal_parents =                compute_internal_parents_within(&target_commit_ids, &connected_target_commits);             target_roots = connected_target_commits_internal_parents                .iter()                .filter(|(commit_id, parents)| {                    target_commit_ids.contains(commit_id) && parents.is_empty()                })                .map(|(commit_id, _)| commit_id.clone())                .collect();        }        MoveCommitsTarget::Roots(roots) => {            if roots.is_empty() {                return Ok(MoveCommitsStats::default());            }             target_commits = RevsetExpression::commits(roots.iter().ids().cloned().collect_vec())                .descendants()                .evaluate(mut_repo)                .map_err(|err| err.expect_backend_error())?                .iter()                .commits(mut_repo.store())                .try_collect()                // TODO: Return evaluation error to caller                .map_err(|err| err.expect_backend_error())?;            target_commit_ids = target_commits.iter().ids().cloned().collect();             connected_target_commits = target_commits.iter().cloned().collect_vec();            // We don't have to compute the internal parents for the connected target set,            // since the connected target set is the same as the target set.            connected_target_commits_internal_parents = HashMap::new();            target_roots = roots.iter().ids().cloned().collect();        }    }     // If a commit outside the target set has a commit in the target set as a    // parent, then - after the transformation - it should have that commit's    // ancestors which are not in the target set as parents.    let mut target_commits_external_parents: HashMap<CommitId, IndexSet<CommitId>> = HashMap::new();    for commit in target_commits.iter().rev() {        let mut new_parents = IndexSet::new();        for old_parent in commit.parent_ids() {            if let Some(parents) = target_commits_external_parents.get(old_parent) {                new_parents.extend(parents.iter().cloned());            } else {                new_parents.insert(old_parent.clone());            }

Lines 1–500 of 1152. Load more