ilyagr.bsky.social
just playing with tangled
1// Copyright 2020 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![allow(missing_docs)]
16
17use std::collections::HashMap;
18use std::collections::HashSet;
19use std::sync::Arc;
20
21use futures::StreamExt as _;
22use indexmap::IndexMap;
23use indexmap::IndexSet;
24use itertools::Itertools as _;
25use pollster::FutureExt as _;
26use tracing::instrument;
27
28use crate::backend::BackendError;
29use crate::backend::BackendResult;
30use crate::backend::CommitId;
31use crate::backend::MergedTreeId;
32use crate::commit::Commit;
33use crate::commit::CommitIteratorExt as _;
34use crate::commit_builder::CommitBuilder;
35use crate::dag_walk;
36use crate::index::Index;
37use crate::index::IndexError;
38use crate::matchers::Matcher;
39use crate::matchers::Visit;
40use crate::merged_tree::MergedTree;
41use crate::merged_tree::MergedTreeBuilder;
42use crate::merged_tree::TreeDiffEntry;
43use crate::repo::MutableRepo;
44use crate::repo::Repo;
45use crate::repo_path::RepoPath;
46use crate::revset::RevsetExpression;
47use crate::revset::RevsetIteratorExt as _;
48use crate::store::Store;
49
50/// Merges `commits` and tries to resolve any conflicts recursively.
51#[instrument(skip(repo))]
52pub fn merge_commit_trees(repo: &dyn Repo, commits: &[Commit]) -> BackendResult<MergedTree> {
53 if let [commit] = commits {
54 commit.tree()
55 } else {
56 merge_commit_trees_no_resolve_without_repo(repo.store(), repo.index(), commits)?.resolve()
57 }
58}
59
60/// Merges `commits` without attempting to resolve file conflicts.
61#[instrument(skip(index))]
62pub fn merge_commit_trees_no_resolve_without_repo(
63 store: &Arc<Store>,
64 index: &dyn Index,
65 commits: &[Commit],
66) -> BackendResult<MergedTree> {
67 if commits.is_empty() {
68 Ok(store.get_root_tree(&store.empty_merged_tree_id())?)
69 } else {
70 let mut new_tree = commits[0].tree()?;
71 let commit_ids = commits
72 .iter()
73 .map(|commit| commit.id().clone())
74 .collect_vec();
75 for (i, other_commit) in commits.iter().enumerate().skip(1) {
76 let ancestor_ids = index.common_ancestors(&commit_ids[0..i], &commit_ids[i..][..1]);
77 let ancestors: Vec<_> = ancestor_ids
78 .iter()
79 .map(|id| store.get_commit(id))
80 .try_collect()?;
81 let ancestor_tree =
82 merge_commit_trees_no_resolve_without_repo(store, index, &ancestors)?;
83 let other_tree = other_commit.tree()?;
84 new_tree = new_tree.merge_no_resolve(&ancestor_tree, &other_tree);
85 }
86 Ok(new_tree)
87 }
88}
89
90/// Restore matching paths from the source into the destination.
91pub fn restore_tree(
92 source: &MergedTree,
93 destination: &MergedTree,
94 matcher: &dyn Matcher,
95) -> BackendResult<MergedTreeId> {
96 if matcher.visit(RepoPath::root()) == Visit::AllRecursively {
97 // Optimization for a common case
98 Ok(source.id())
99 } else {
100 // TODO: We should be able to not traverse deeper in the diff if the matcher
101 // matches an entire subtree.
102 let mut tree_builder = MergedTreeBuilder::new(destination.id().clone());
103 async {
104 // TODO: handle copy tracking
105 let mut diff_stream = source.diff_stream(destination, matcher);
106 while let Some(TreeDiffEntry {
107 path: repo_path,
108 values,
109 }) = diff_stream.next().await
110 {
111 let (source_value, _destination_value) = values?;
112 tree_builder.set_or_remove(repo_path, source_value);
113 }
114 Ok::<(), BackendError>(())
115 }
116 .block_on()?;
117 tree_builder.write_tree(destination.store())
118 }
119}
120
121pub fn rebase_commit(
122 mut_repo: &mut MutableRepo,
123 old_commit: Commit,
124 new_parents: Vec<CommitId>,
125) -> BackendResult<Commit> {
126 let rewriter = CommitRewriter::new(mut_repo, old_commit, new_parents);
127 let builder = rewriter.rebase()?;
128 builder.write()
129}
130
131/// Helps rewrite a commit.
132pub struct CommitRewriter<'repo> {
133 mut_repo: &'repo mut MutableRepo,
134 old_commit: Commit,
135 new_parents: Vec<CommitId>,
136}
137
138impl<'repo> CommitRewriter<'repo> {
139 /// Create a new instance.
140 pub fn new(
141 mut_repo: &'repo mut MutableRepo,
142 old_commit: Commit,
143 new_parents: Vec<CommitId>,
144 ) -> Self {
145 Self {
146 mut_repo,
147 old_commit,
148 new_parents,
149 }
150 }
151
152 /// Returns the `MutableRepo`.
153 pub fn mut_repo(&mut self) -> &mut MutableRepo {
154 self.mut_repo
155 }
156
157 /// The commit we're rewriting.
158 pub fn old_commit(&self) -> &Commit {
159 &self.old_commit
160 }
161
162 /// Get the old commit's intended new parents.
163 pub fn new_parents(&self) -> &[CommitId] {
164 &self.new_parents
165 }
166
167 /// Set the old commit's intended new parents.
168 pub fn set_new_parents(&mut self, new_parents: Vec<CommitId>) {
169 self.new_parents = new_parents;
170 }
171
172 /// Set the old commit's intended new parents to be the rewritten versions
173 /// of the given parents.
174 pub fn set_new_rewritten_parents(&mut self, unrewritten_parents: &[CommitId]) {
175 self.new_parents = self.mut_repo.new_parents(unrewritten_parents);
176 }
177
178 /// Update the intended new parents by replacing any occurrence of
179 /// `old_parent` by `new_parents`.
180 pub fn replace_parent<'a>(
181 &mut self,
182 old_parent: &CommitId,
183 new_parents: impl IntoIterator<Item = &'a CommitId>,
184 ) {
185 if let Some(i) = self.new_parents.iter().position(|p| p == old_parent) {
186 self.new_parents
187 .splice(i..i + 1, new_parents.into_iter().cloned());
188 let mut unique = HashSet::new();
189 self.new_parents.retain(|p| unique.insert(p.clone()));
190 }
191 }
192
193 /// Checks if the intended new parents are different from the old commit's
194 /// parents.
195 pub fn parents_changed(&self) -> bool {
196 self.new_parents != self.old_commit.parent_ids()
197 }
198
199 /// If a merge commit would end up with one parent being an ancestor of the
200 /// other, then filter out the ancestor.
201 pub fn simplify_ancestor_merge(&mut self) -> Result<(), IndexError> {
202 let head_set: HashSet<_> = self
203 .mut_repo
204 .index()
205 .heads(&mut self.new_parents.iter())?
206 .into_iter()
207 .collect();
208 self.new_parents.retain(|parent| head_set.contains(parent));
209 Ok(())
210 }
211
212 /// Records the old commit as abandoned with the new parents.
213 ///
214 /// This is equivalent to `reparent(settings).abandon()`, but is cheaper.
215 pub fn abandon(self) {
216 let old_commit_id = self.old_commit.id().clone();
217 let new_parents = self.new_parents;
218 self.mut_repo
219 .record_abandoned_commit_with_parents(old_commit_id, new_parents);
220 }
221
222 /// Rebase the old commit onto the new parents. Returns a `CommitBuilder`
223 /// for the new commit. Returns `None` if the commit was abandoned.
224 pub fn rebase_with_empty_behavior(
225 self,
226 empty: EmptyBehaviour,
227 ) -> BackendResult<Option<CommitBuilder<'repo>>> {
228 let old_parents: Vec<_> = self.old_commit.parents().try_collect()?;
229 let old_parent_trees = old_parents
230 .iter()
231 .map(|parent| parent.tree_id().clone())
232 .collect_vec();
233 let new_parents: Vec<_> = self
234 .new_parents
235 .iter()
236 .map(|new_parent_id| self.mut_repo.store().get_commit(new_parent_id))
237 .try_collect()?;
238 let new_parent_trees = new_parents
239 .iter()
240 .map(|parent| parent.tree_id().clone())
241 .collect_vec();
242
243 let (was_empty, new_tree_id) = if new_parent_trees == old_parent_trees {
244 (
245 // Optimization: was_empty is only used for newly empty, but when the
246 // parents haven't changed it can't be newly empty.
247 true,
248 // Optimization: Skip merging.
249 self.old_commit.tree_id().clone(),
250 )
251 } else {
252 let old_base_tree = merge_commit_trees(self.mut_repo, &old_parents)?;
253 let new_base_tree = merge_commit_trees(self.mut_repo, &new_parents)?;
254 let old_tree = self.old_commit.tree()?;
255 (
256 old_base_tree.id() == *self.old_commit.tree_id(),
257 new_base_tree.merge(&old_base_tree, &old_tree)?.id(),
258 )
259 };
260 // Ensure we don't abandon commits with multiple parents (merge commits), even
261 // if they're empty.
262 if let [parent] = &new_parents[..] {
263 let should_abandon = match empty {
264 EmptyBehaviour::Keep => false,
265 EmptyBehaviour::AbandonNewlyEmpty => *parent.tree_id() == new_tree_id && !was_empty,
266 EmptyBehaviour::AbandonAllEmpty => *parent.tree_id() == new_tree_id,
267 };
268 if should_abandon {
269 self.abandon();
270 return Ok(None);
271 }
272 }
273
274 let builder = self
275 .mut_repo
276 .rewrite_commit(&self.old_commit)
277 .set_parents(self.new_parents)
278 .set_tree_id(new_tree_id);
279 Ok(Some(builder))
280 }
281
282 /// Rebase the old commit onto the new parents. Returns a `CommitBuilder`
283 /// for the new commit.
284 pub fn rebase(self) -> BackendResult<CommitBuilder<'repo>> {
285 let builder = self.rebase_with_empty_behavior(EmptyBehaviour::Keep)?;
286 Ok(builder.unwrap())
287 }
288
289 /// Rewrite the old commit onto the new parents without changing its
290 /// contents. Returns a `CommitBuilder` for the new commit.
291 pub fn reparent(self) -> CommitBuilder<'repo> {
292 self.mut_repo
293 .rewrite_commit(&self.old_commit)
294 .set_parents(self.new_parents)
295 }
296}
297
298pub enum RebasedCommit {
299 Rewritten(Commit),
300 Abandoned { parent_id: CommitId },
301}
302
303pub fn rebase_commit_with_options(
304 mut rewriter: CommitRewriter<'_>,
305 options: &RebaseOptions,
306) -> BackendResult<RebasedCommit> {
307 // If specified, don't create commit where one parent is an ancestor of another.
308 if options.simplify_ancestor_merge {
309 // TODO: BackendError is not the right error here because
310 // the error does not come from `Backend`, but `Index`.
311 rewriter
312 .simplify_ancestor_merge()
313 .map_err(|err| BackendError::Other(err.into()))?;
314 }
315
316 let single_parent = match &rewriter.new_parents[..] {
317 [parent_id] => Some(parent_id.clone()),
318 _ => None,
319 };
320 let new_parents_len = rewriter.new_parents.len();
321 if let Some(builder) = rewriter.rebase_with_empty_behavior(options.empty)? {
322 let new_commit = builder.write()?;
323 Ok(RebasedCommit::Rewritten(new_commit))
324 } else {
325 assert_eq!(new_parents_len, 1);
326 Ok(RebasedCommit::Abandoned {
327 parent_id: single_parent.unwrap(),
328 })
329 }
330}
331
332/// Moves changes from `sources` to the `destination` parent, returns new tree.
333pub fn rebase_to_dest_parent(
334 repo: &dyn Repo,
335 sources: &[Commit],
336 destination: &Commit,
337) -> BackendResult<MergedTree> {
338 if let [source] = sources {
339 if source.parent_ids() == destination.parent_ids() {
340 return source.tree();
341 }
342 }
343 sources.iter().try_fold(
344 destination.parent_tree(repo)?,
345 |destination_tree, source| {
346 let source_parent_tree = source.parent_tree(repo)?;
347 let source_tree = source.tree()?;
348 destination_tree.merge(&source_parent_tree, &source_tree)
349 },
350 )
351}
352
353#[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]
354pub enum EmptyBehaviour {
355 /// Always keep empty commits
356 #[default]
357 Keep,
358 /// Skips commits that would be empty after the rebase, but that were not
359 /// originally empty.
360 /// Will never skip merge commits with multiple non-empty parents.
361 AbandonNewlyEmpty,
362 /// Skips all empty commits, including ones that were empty before the
363 /// rebase.
364 /// Will never skip merge commits with multiple non-empty parents.
365 AbandonAllEmpty,
366}
367
368/// Controls the configuration of a rebase.
369// If we wanted to add a flag similar to `git rebase --ignore-date`, then this
370// makes it much easier by ensuring that the only changes required are to
371// change the RebaseOptions construction in the CLI, and changing the
372// rebase_commit function to actually use the flag, and ensure we don't need to
373// plumb it in.
374#[derive(Clone, Debug, Default)]
375pub struct RebaseOptions {
376 pub empty: EmptyBehaviour,
377 pub rewrite_refs: RewriteRefsOptions,
378 /// If a merge commit would end up with one parent being an ancestor of the
379 /// other, then filter out the ancestor.
380 pub simplify_ancestor_merge: bool,
381}
382
383/// Configuration for [`MutableRepo::update_rewritten_references()`].
384#[derive(Clone, Debug, Default)]
385pub struct RewriteRefsOptions {
386 /// Whether or not delete bookmarks pointing to the abandoned commits.
387 ///
388 /// If false, bookmarks will be moved to the parents of the abandoned
389 /// commit.
390 pub delete_abandoned_bookmarks: bool,
391}
392
393#[derive(Default)]
394pub struct MoveCommitsStats {
395 /// The number of commits in the target set which were rebased.
396 pub num_rebased_targets: u32,
397 /// The number of descendant commits which were rebased.
398 pub num_rebased_descendants: u32,
399 /// The number of commits for which rebase was skipped, due to the commit
400 /// already being in place.
401 pub num_skipped_rebases: u32,
402 /// The number of commits which were abandoned.
403 pub num_abandoned: u32,
404}
405
406pub enum MoveCommitsTarget {
407 /// The commits to be moved. Commits should be mutable and in reverse
408 /// topological order.
409 Commits(Vec<Commit>),
410 /// The root commits to be moved, along with all their descendants.
411 Roots(Vec<Commit>),
412}
413
414/// Moves `target_commits` from their current location to a new location in the
415/// graph.
416///
417/// Commits in `target` are rebased onto the new parents given by
418/// `new_parent_ids`, while the `new_children` commits are rebased onto the
419/// heads of the commits in `targets`. This assumes that commits in `target` and
420/// `new_children` can be rewritten, and there will be no cycles in the
421/// resulting graph. Commits in `target` should be in reverse topological order.
422pub fn move_commits(
423 mut_repo: &mut MutableRepo,
424 new_parent_ids: &[CommitId],
425 new_children: &[Commit],
426 target: &MoveCommitsTarget,
427 options: &RebaseOptions,
428) -> BackendResult<MoveCommitsStats> {
429 let target_commits: Vec<Commit>;
430 let target_commit_ids: HashSet<_>;
431 let connected_target_commits: Vec<Commit>;
432 let connected_target_commits_internal_parents: HashMap<CommitId, Vec<CommitId>>;
433 let target_roots: HashSet<CommitId>;
434
435 match target {
436 MoveCommitsTarget::Commits(commits) => {
437 if commits.is_empty() {
438 return Ok(MoveCommitsStats::default());
439 }
440
441 target_commits = commits.clone();
442 target_commit_ids = target_commits.iter().ids().cloned().collect();
443
444 connected_target_commits =
445 RevsetExpression::commits(target_commits.iter().ids().cloned().collect_vec())
446 .connected()
447 .evaluate(mut_repo)
448 .map_err(|err| err.expect_backend_error())?
449 .iter()
450 .commits(mut_repo.store())
451 .try_collect()
452 // TODO: Return evaluation error to caller
453 .map_err(|err| err.expect_backend_error())?;
454 connected_target_commits_internal_parents =
455 compute_internal_parents_within(&target_commit_ids, &connected_target_commits);
456
457 target_roots = connected_target_commits_internal_parents
458 .iter()
459 .filter(|(commit_id, parents)| {
460 target_commit_ids.contains(commit_id) && parents.is_empty()
461 })
462 .map(|(commit_id, _)| commit_id.clone())
463 .collect();
464 }
465 MoveCommitsTarget::Roots(roots) => {
466 if roots.is_empty() {
467 return Ok(MoveCommitsStats::default());
468 }
469
470 target_commits = RevsetExpression::commits(roots.iter().ids().cloned().collect_vec())
471 .descendants()
472 .evaluate(mut_repo)
473 .map_err(|err| err.expect_backend_error())?
474 .iter()
475 .commits(mut_repo.store())
476 .try_collect()
477 // TODO: Return evaluation error to caller
478 .map_err(|err| err.expect_backend_error())?;
479 target_commit_ids = target_commits.iter().ids().cloned().collect();
480
481 connected_target_commits = target_commits.iter().cloned().collect_vec();
482 // We don't have to compute the internal parents for the connected target set,
483 // since the connected target set is the same as the target set.
484 connected_target_commits_internal_parents = HashMap::new();
485 target_roots = roots.iter().ids().cloned().collect();
486 }
487 }
488
489 // If a commit outside the target set has a commit in the target set as a
490 // parent, then - after the transformation - it should have that commit's
491 // ancestors which are not in the target set as parents.
492 let mut target_commits_external_parents: HashMap<CommitId, IndexSet<CommitId>> = HashMap::new();
493 for commit in target_commits.iter().rev() {
494 let mut new_parents = IndexSet::new();
495 for old_parent in commit.parent_ids() {
496 if let Some(parents) = target_commits_external_parents.get(old_parent) {
497 new_parents.extend(parents.iter().cloned());
498 } else {
499 new_parents.insert(old_parent.clone());
500 }
501 }
502 target_commits_external_parents.insert(commit.id().clone(), new_parents);
503 }
504
505 // If the new parents include a commit in the target set, replace it with the
506 // commit's ancestors which are outside the set.
507 // e.g. `jj rebase -r A --before A`
508 let new_parent_ids: Vec<_> = new_parent_ids
509 .iter()
510 .flat_map(|parent_id| {
511 if let Some(parent_ids) = target_commits_external_parents.get(parent_id) {
512 parent_ids.iter().cloned().collect_vec()
513 } else {
514 vec![parent_id.clone()]
515 }
516 })
517 .collect();
518
519 // If the new children include a commit in the target set, replace it with the
520 // commit's descendants which are outside the set.
521 // e.g. `jj rebase -r A --after A`
522 let new_children: Vec<_> = if new_children
523 .iter()
524 .any(|child| target_commit_ids.contains(child.id()))
525 {
526 let target_commits_descendants: Vec<_> =
527 RevsetExpression::commits(target_commit_ids.iter().cloned().collect_vec())
528 .union(
529 &RevsetExpression::commits(target_commit_ids.iter().cloned().collect_vec())
530 .children(),
531 )
532 .evaluate(mut_repo)
533 .map_err(|err| err.expect_backend_error())?
534 .iter()
535 .commits(mut_repo.store())
536 .try_collect()
537 // TODO: Return evaluation error to caller
538 .map_err(|err| err.expect_backend_error())?;
539
540 // For all commits in the target set, compute its transitive descendant commits
541 // which are outside of the target set by up to 1 generation.
542 let mut target_commit_external_descendants: HashMap<CommitId, IndexSet<Commit>> =
543 HashMap::new();
544 // Iterate through all descendants of the target set, going through children
545 // before parents.
546 for commit in &target_commits_descendants {
547 if !target_commit_external_descendants.contains_key(commit.id()) {
548 let children = if target_commit_ids.contains(commit.id()) {
549 IndexSet::new()
550 } else {
551 IndexSet::from([commit.clone()])
552 };
553 target_commit_external_descendants.insert(commit.id().clone(), children);
554 }
555
556 let children = target_commit_external_descendants
557 .get(commit.id())
558 .unwrap()
559 .iter()
560 .cloned()
561 .collect_vec();
562 for parent_id in commit.parent_ids() {
563 if target_commit_ids.contains(parent_id) {
564 if let Some(target_children) =
565 target_commit_external_descendants.get_mut(parent_id)
566 {
567 target_children.extend(children.iter().cloned());
568 } else {
569 target_commit_external_descendants
570 .insert(parent_id.clone(), children.iter().cloned().collect());
571 }
572 };
573 }
574 }
575
576 new_children
577 .iter()
578 .flat_map(|child| {
579 if let Some(children) = target_commit_external_descendants.get(child.id()) {
580 children.iter().cloned().collect_vec()
581 } else {
582 vec![child.clone()]
583 }
584 })
585 .collect()
586 } else {
587 new_children.to_vec()
588 };
589
590 // Compute the parents of the new children, which will include the heads of the
591 // target set.
592 let new_children_parents: HashMap<_, _> = if !new_children.is_empty() {
593 // Compute the heads of the target set, which will be used as the parents of
594 // `new_children`.
595 let target_heads = compute_commits_heads(&target_commit_ids, &connected_target_commits);
596
597 new_children
598 .iter()
599 .map(|child_commit| {
600 let mut new_child_parent_ids = IndexSet::new();
601 for old_child_parent_id in child_commit.parent_ids() {
602 // Replace target commits with their parents outside the target set.
603 let old_child_parent_ids = if let Some(parents) =
604 target_commits_external_parents.get(old_child_parent_id)
605 {
606 parents.iter().collect_vec()
607 } else {
608 vec![old_child_parent_id]
609 };
610
611 // If the original parents of the new children are the new parents of the
612 // `target_heads`, replace them with the target heads since we are "inserting"
613 // the target commits in between the new parents and the new children.
614 for id in old_child_parent_ids {
615 if new_parent_ids.contains(id) {
616 new_child_parent_ids.extend(target_heads.clone());
617 } else {
618 new_child_parent_ids.insert(id.clone());
619 };
620 }
621 }
622
623 // If not already present, add `target_heads` as parents of the new child
624 // commit.
625 new_child_parent_ids.extend(target_heads.clone());
626
627 (
628 child_commit.id().clone(),
629 new_child_parent_ids.into_iter().collect_vec(),
630 )
631 })
632 .collect()
633 } else {
634 HashMap::new()
635 };
636
637 // Compute the set of commits to visit, which includes the target commits, the
638 // new children commits (if any), and their descendants.
639 let mut roots = target_roots.iter().cloned().collect_vec();
640 roots.extend(new_children.iter().ids().cloned());
641 let to_visit_expression = RevsetExpression::commits(roots).descendants();
642 let to_visit: Vec<_> = to_visit_expression
643 .evaluate(mut_repo)
644 .map_err(|err| err.expect_backend_error())?
645 .iter()
646 .commits(mut_repo.store())
647 .try_collect()
648 // TODO: Return evaluation error to caller
649 .map_err(|err| err.expect_backend_error())?;
650 let to_visit_commits: IndexMap<_, _> = to_visit
651 .into_iter()
652 .map(|commit| (commit.id().clone(), commit))
653 .collect();
654
655 let to_visit_commits_new_parents: HashMap<_, _> = to_visit_commits
656 .iter()
657 .map(|(commit_id, commit)| {
658 let new_parents =
659 // New child of the rebased target commits.
660 if let Some(new_child_parents) = new_children_parents.get(commit_id) {
661 new_child_parents.clone()
662 }
663 // Commit is in the target set.
664 else if target_commit_ids.contains(commit_id) {
665 // If the commit is a root of the target set, it should be rebased onto the new destination.
666 if target_roots.contains(commit_id) {
667 new_parent_ids.clone()
668 }
669 // Otherwise:
670 // 1. Keep parents which are within the target set.
671 // 2. Replace parents which are outside the target set but are part of the
672 // connected target set with their ancestor commits which are in the target
673 // set.
674 // 3. Keep other parents outside the target set if they are not descendants of the
675 // new children of the target set.
676 else {
677 let mut new_parents = vec![];
678 for parent_id in commit.parent_ids() {
679 if target_commit_ids.contains(parent_id) {
680 new_parents.push(parent_id.clone());
681 } else if let Some(parents) =
682 connected_target_commits_internal_parents.get(parent_id) {
683 new_parents.extend(parents.iter().cloned());
684 } else if !new_children.iter().any(|new_child| {
685 mut_repo.index().is_ancestor(new_child.id(), parent_id) }) {
686 new_parents.push(parent_id.clone());
687 }
688 }
689 new_parents
690 }
691 }
692 // Commits outside the target set should have references to commits inside the set
693 // replaced.
694 else if commit
695 .parent_ids()
696 .iter()
697 .any(|id| target_commits_external_parents.contains_key(id))
698 {
699 let mut new_parents = vec![];
700 for parent in commit.parent_ids() {
701 if let Some(parents) = target_commits_external_parents.get(parent) {
702 new_parents.extend(parents.iter().cloned());
703 } else {
704 new_parents.push(parent.clone());
705 }
706 }
707 new_parents
708 } else {
709 commit.parent_ids().iter().cloned().collect_vec()
710 };
711
712 (commit_id.clone(), new_parents)
713 })
714 .collect();
715
716 // Re-compute the order of commits to visit, such that each commit's new parents
717 // must be visited first.
718 let mut visited: HashSet<CommitId> = HashSet::new();
719 let mut to_visit = dag_walk::topo_order_reverse(
720 to_visit_commits.keys().cloned().collect_vec(),
721 |commit_id| commit_id.clone(),
722 |commit_id| -> Vec<CommitId> {
723 visited.insert(commit_id.clone());
724 to_visit_commits_new_parents
725 .get(commit_id)
726 .cloned()
727 .unwrap()
728 .iter()
729 // Only add parents which are in the set to be visited and have not already been
730 // visited.
731 .filter(|&id| to_visit_commits.contains_key(id) && !visited.contains(id))
732 .cloned()
733 .collect()
734 },
735 );
736
737 let mut num_rebased_targets = 0;
738 let mut num_rebased_descendants = 0;
739 let mut num_skipped_rebases = 0;
740 let mut num_abandoned = 0;
741
742 // Always keep empty commits when rebasing descendants.
743 let rebase_descendant_options = &RebaseOptions {
744 empty: EmptyBehaviour::Keep,
745 rewrite_refs: options.rewrite_refs.clone(),
746 simplify_ancestor_merge: options.simplify_ancestor_merge,
747 };
748
749 // Rebase each commit onto its new parents in the reverse topological order
750 // computed above.
751 while let Some(old_commit_id) = to_visit.pop() {
752 let old_commit = to_visit_commits.get(&old_commit_id).unwrap();
753 let parent_ids = to_visit_commits_new_parents.get(&old_commit_id).unwrap();
754 let new_parent_ids = mut_repo.new_parents(parent_ids);
755 let rewriter = CommitRewriter::new(mut_repo, old_commit.clone(), new_parent_ids);
756 if rewriter.parents_changed() {
757 let is_target_commit = target_commit_ids.contains(&old_commit_id);
758 let rebased_commit = rebase_commit_with_options(
759 rewriter,
760 if is_target_commit {
761 options
762 } else {
763 rebase_descendant_options
764 },
765 )?;
766 if let RebasedCommit::Abandoned { .. } = rebased_commit {
767 num_abandoned += 1;
768 } else if is_target_commit {
769 num_rebased_targets += 1;
770 } else {
771 num_rebased_descendants += 1;
772 }
773 } else {
774 num_skipped_rebases += 1;
775 }
776 }
777 mut_repo.update_rewritten_references(&options.rewrite_refs)?;
778
779 Ok(MoveCommitsStats {
780 num_rebased_targets,
781 num_rebased_descendants,
782 num_skipped_rebases,
783 num_abandoned,
784 })
785}
786
787#[derive(Default)]
788pub struct DuplicateCommitsStats {
789 /// Map of original commit ID to newly duplicated commit.
790 pub duplicated_commits: IndexMap<CommitId, Commit>,
791 /// The number of descendant commits which were rebased onto the duplicated
792 /// commits.
793 pub num_rebased: u32,
794}
795
796/// Duplicates the given `target_commits` onto a new location in the graph.
797///
798/// The roots of `target_commits` are duplicated on top of the new
799/// `parent_commit_ids`, whilst other commits in `target_commits` are duplicated
800/// on top of the newly duplicated commits in the target set. If
801/// `children_commit_ids` is not empty, the `children_commit_ids` will be
802/// rebased onto the heads of the duplicated target commits.
803///
804/// This assumes that commits in `children_commit_ids` can be rewritten. There
805/// should also be no cycles in the resulting graph, i.e. `children_commit_ids`
806/// should not be ancestors of `parent_commit_ids`. Commits in `target_commits`
807/// should be in reverse topological order (children before parents).
808pub fn duplicate_commits(
809 mut_repo: &mut MutableRepo,
810 target_commits: &[CommitId],
811 parent_commit_ids: &[CommitId],
812 children_commit_ids: &[CommitId],
813) -> BackendResult<DuplicateCommitsStats> {
814 if target_commits.is_empty() {
815 return Ok(DuplicateCommitsStats::default());
816 }
817
818 let mut duplicated_old_to_new: IndexMap<CommitId, Commit> = IndexMap::new();
819 let mut num_rebased = 0;
820
821 let target_commit_ids: HashSet<_> = target_commits.iter().cloned().collect();
822
823 let connected_target_commits: Vec<_> =
824 RevsetExpression::commits(target_commit_ids.iter().cloned().collect_vec())
825 .connected()
826 .evaluate(mut_repo)
827 .map_err(|err| err.expect_backend_error())?
828 .iter()
829 .commits(mut_repo.store())
830 .try_collect()
831 // TODO: Return evaluation error to caller
832 .map_err(|err| err.expect_backend_error())?;
833
834 // Commits in the target set should only have other commits in the set as
835 // parents, except the roots of the set, which persist their original
836 // parents.
837 // If a commit in the target set has a parent which is not in the set, but has
838 // an ancestor which is in the set, then the commit will have that ancestor
839 // as a parent instead.
840 let target_commits_internal_parents = {
841 let mut target_commits_internal_parents =
842 compute_internal_parents_within(&target_commit_ids, &connected_target_commits);
843 target_commits_internal_parents.retain(|id, _| target_commit_ids.contains(id));
844 target_commits_internal_parents
845 };
846
847 // Compute the roots of `target_commits`.
848 let target_root_ids: HashSet<_> = target_commits_internal_parents
849 .iter()
850 .filter(|(_, parents)| parents.is_empty())
851 .map(|(commit_id, _)| commit_id.clone())
852 .collect();
853
854 // Compute the heads of the target set, which will be used as the parents of
855 // the children commits.
856 let target_head_ids = if !children_commit_ids.is_empty() {
857 compute_commits_heads(&target_commit_ids, &connected_target_commits)
858 } else {
859 vec![]
860 };
861
862 // Topological order ensures that any parents of the original commit are
863 // either not in `target_commits` or were already duplicated.
864 for original_commit_id in target_commits.iter().rev() {
865 let original_commit = mut_repo.store().get_commit(original_commit_id)?;
866 let new_parent_ids = if target_root_ids.contains(original_commit_id) {
867 parent_commit_ids.to_vec()
868 } else {
869 target_commits_internal_parents
870 .get(original_commit_id)
871 .unwrap()
872 .iter()
873 // Replace parent IDs with their new IDs if they were duplicated.
874 .map(|id| {
875 duplicated_old_to_new
876 .get(id)
877 .map_or(id, |commit| commit.id())
878 .clone()
879 })
880 .collect()
881 };
882 let new_commit = CommitRewriter::new(mut_repo, original_commit, new_parent_ids)
883 .rebase()?
884 .generate_new_change_id()
885 .write()?;
886 duplicated_old_to_new.insert(original_commit_id.clone(), new_commit);
887 }
888
889 // Replace the original commit IDs in `target_head_ids` with the duplicated
890 // commit IDs.
891 let target_head_ids = target_head_ids
892 .into_iter()
893 .map(|commit_id| {
894 duplicated_old_to_new
895 .get(&commit_id)
896 .map_or(commit_id, |commit| commit.id().clone())
897 })
898 .collect_vec();
899
900 // Rebase new children onto the target heads.
901 let children_commit_ids_set: HashSet<CommitId> = children_commit_ids.iter().cloned().collect();
902 mut_repo.transform_descendants(children_commit_ids.to_vec(), |mut rewriter| {
903 if children_commit_ids_set.contains(rewriter.old_commit().id()) {
904 let mut child_new_parent_ids = IndexSet::new();
905 for old_parent_id in rewriter.old_commit().parent_ids() {
906 // If the original parents of the new children are the new parents of
907 // `target_head_ids`, replace them with `target_head_ids` since we are
908 // "inserting" the target commits in between the new parents and the new
909 // children.
910 if parent_commit_ids.contains(old_parent_id) {
911 child_new_parent_ids.extend(target_head_ids.clone());
912 } else {
913 child_new_parent_ids.insert(old_parent_id.clone());
914 }
915 }
916 // If not already present, add `target_head_ids` as parents of the new child
917 // commit.
918 child_new_parent_ids.extend(target_head_ids.clone());
919 rewriter.set_new_parents(child_new_parent_ids.into_iter().collect());
920 }
921 num_rebased += 1;
922 rewriter.rebase()?.write()?;
923 Ok(())
924 })?;
925
926 Ok(DuplicateCommitsStats {
927 duplicated_commits: duplicated_old_to_new,
928 num_rebased,
929 })
930}
931
932/// Duplicates the given `target_commits` onto their original parents or other
933/// duplicated commits.
934///
935/// Commits in `target_commits` should be in reverse topological order (children
936/// before parents).
937pub fn duplicate_commits_onto_parents(
938 mut_repo: &mut MutableRepo,
939 target_commits: &[CommitId],
940) -> BackendResult<DuplicateCommitsStats> {
941 if target_commits.is_empty() {
942 return Ok(DuplicateCommitsStats::default());
943 }
944
945 let mut duplicated_old_to_new: IndexMap<CommitId, Commit> = IndexMap::new();
946
947 // Topological order ensures that any parents of the original commit are
948 // either not in `target_commits` or were already duplicated.
949 for original_commit_id in target_commits.iter().rev() {
950 let original_commit = mut_repo.store().get_commit(original_commit_id)?;
951 let new_parent_ids = original_commit
952 .parent_ids()
953 .iter()
954 .map(|id| {
955 duplicated_old_to_new
956 .get(id)
957 .map_or(id, |commit| commit.id())
958 .clone()
959 })
960 .collect();
961 let new_commit = mut_repo
962 .rewrite_commit(&original_commit)
963 .generate_new_change_id()
964 .set_parents(new_parent_ids)
965 .write()?;
966 duplicated_old_to_new.insert(original_commit_id.clone(), new_commit);
967 }
968
969 Ok(DuplicateCommitsStats {
970 duplicated_commits: duplicated_old_to_new,
971 num_rebased: 0,
972 })
973}
974
975/// Computes the internal parents of all commits in a connected commit graph,
976/// allowing only commits in the target set as parents.
977///
978/// The parents of each commit are identical to the ones found using a preorder
979/// DFS of the node's ancestors, starting from the node itself, and avoiding
980/// traversing an edge if the parent is in the target set. `graph_commits`
981/// should be in reverse topological order.
982fn compute_internal_parents_within(
983 target_commit_ids: &HashSet<CommitId>,
984 graph_commits: &[Commit],
985) -> HashMap<CommitId, Vec<CommitId>> {
986 let mut internal_parents: HashMap<CommitId, Vec<CommitId>> = HashMap::new();
987 for commit in graph_commits.iter().rev() {
988 // The roots of the set will not have any parents found in `internal_parents`,
989 // and will be stored as an empty vector.
990 let mut new_parents = vec![];
991 for old_parent in commit.parent_ids() {
992 if target_commit_ids.contains(old_parent) {
993 new_parents.push(old_parent.clone());
994 } else if let Some(parents) = internal_parents.get(old_parent) {
995 new_parents.extend(parents.iter().cloned());
996 }
997 }
998 internal_parents.insert(commit.id().clone(), new_parents);
999 }
1000 internal_parents
1001}
1002
1003/// Computes the heads of commits in the target set, given the list of
1004/// `target_commit_ids` and a connected graph of commits.
1005///
1006/// `connected_target_commits` should be in reverse topological order (children
1007/// before parents).
1008fn compute_commits_heads(
1009 target_commit_ids: &HashSet<CommitId>,
1010 connected_target_commits: &[Commit],
1011) -> Vec<CommitId> {
1012 let mut target_head_ids: HashSet<CommitId> = HashSet::new();
1013 for commit in connected_target_commits.iter().rev() {
1014 target_head_ids.insert(commit.id().clone());
1015 for old_parent in commit.parent_ids() {
1016 target_head_ids.remove(old_parent);
1017 }
1018 }
1019 connected_target_commits
1020 .iter()
1021 .rev()
1022 .filter(|commit| {
1023 target_head_ids.contains(commit.id()) && target_commit_ids.contains(commit.id())
1024 })
1025 .map(|commit| commit.id().clone())
1026 .collect_vec()
1027}
1028
1029pub struct CommitWithSelection {
1030 pub commit: Commit,
1031 pub selected_tree: MergedTree,
1032 pub parent_tree: MergedTree,
1033}
1034
1035impl CommitWithSelection {
1036 /// Returns true if the selection contains all changes in the commit.
1037 pub fn is_full_selection(&self) -> bool {
1038 &self.selected_tree.id() == self.commit.tree_id()
1039 }
1040
1041 /// Returns true if the selection matches the parent tree (contains no
1042 /// changes from the commit).
1043 ///
1044 /// Both `is_full_selection()` and `is_empty_selection()`
1045 /// can be true if the commit is itself empty.
1046 pub fn is_empty_selection(&self) -> bool {
1047 self.selected_tree.id() == self.parent_tree.id()
1048 }
1049}
1050
1051/// Resulting commit builder and stats to be returned by [`squash_commits()`].
1052#[must_use]
1053pub struct SquashedCommit<'repo> {
1054 /// New destination commit will be created by this builder.
1055 pub commit_builder: CommitBuilder<'repo>,
1056 /// List of abandoned source commits.
1057 pub abandoned_commits: Vec<Commit>,
1058}
1059
1060/// Squash `sources` into `destination` and return a [`SquashedCommit`] for the
1061/// resulting commit. Caller is responsible for setting the description and
1062/// finishing the commit.
1063pub fn squash_commits<'repo>(
1064 repo: &'repo mut MutableRepo,
1065 sources: &[CommitWithSelection],
1066 destination: &Commit,
1067 keep_emptied: bool,
1068) -> BackendResult<Option<SquashedCommit<'repo>>> {
1069 struct SourceCommit<'a> {
1070 commit: &'a CommitWithSelection,
1071 abandon: bool,
1072 }
1073 let mut source_commits = vec![];
1074 for source in sources {
1075 let abandon = !keep_emptied && source.is_full_selection();
1076 if !abandon && source.is_empty_selection() {
1077 // Nothing selected from this commit. If it's abandoned (i.e. already empty), we
1078 // still include it so `jj squash` can be used for abandoning an empty commit in
1079 // the middle of a stack.
1080 continue;
1081 }
1082
1083 // TODO: Do we want to optimize the case of moving to the parent commit (`jj
1084 // squash -r`)? The source tree will be unchanged in that case.
1085 source_commits.push(SourceCommit {
1086 commit: source,
1087 abandon,
1088 });
1089 }
1090
1091 if source_commits.is_empty() {
1092 return Ok(None);
1093 }
1094
1095 let mut abandoned_commits = vec![];
1096 for source in &source_commits {
1097 if source.abandon {
1098 repo.record_abandoned_commit(&source.commit.commit);
1099 abandoned_commits.push(source.commit.commit.clone());
1100 } else {
1101 let source_tree = source.commit.commit.tree()?;
1102 // Apply the reverse of the selected changes onto the source
1103 let new_source_tree =
1104 source_tree.merge(&source.commit.selected_tree, &source.commit.parent_tree)?;
1105 repo.rewrite_commit(&source.commit.commit)
1106 .set_tree_id(new_source_tree.id().clone())
1107 .write()?;
1108 }
1109 }
1110
1111 let mut rewritten_destination = destination.clone();
1112 if sources.iter().any(|source| {
1113 repo.index()
1114 .is_ancestor(source.commit.id(), destination.id())
1115 }) {
1116 // If we're moving changes to a descendant, first rebase descendants onto the
1117 // rewritten sources. Otherwise it will likely already have the content
1118 // changes we're moving, so applying them will have no effect and the
1119 // changes will disappear.
1120 let options = RebaseOptions::default();
1121 repo.rebase_descendants_with_options(&options, |old_commit, rebased_commit| {
1122 if old_commit.id() != destination.id() {
1123 return;
1124 }
1125 rewritten_destination = match rebased_commit {
1126 RebasedCommit::Rewritten(commit) => commit,
1127 RebasedCommit::Abandoned { .. } => panic!("all commits should be kept"),
1128 };
1129 })?;
1130 }
1131 // Apply the selected changes onto the destination
1132 let mut destination_tree = rewritten_destination.tree()?;
1133 for source in &source_commits {
1134 destination_tree =
1135 destination_tree.merge(&source.commit.parent_tree, &source.commit.selected_tree)?;
1136 }
1137 let mut predecessors = vec![destination.id().clone()];
1138 predecessors.extend(
1139 source_commits
1140 .iter()
1141 .map(|source| source.commit.commit.id().clone()),
1142 );
1143
1144 let commit_builder = repo
1145 .rewrite_commit(&rewritten_destination)
1146 .set_tree_id(destination_tree.id().clone())
1147 .set_predecessors(predecessors);
1148 Ok(Some(SquashedCommit {
1149 commit_builder,
1150 abandoned_commits,
1151 }))
1152}