How to do a difficult rebase in O(n) rather than O(n^2)?

Question

There's this difficult rebase that keeps stumbling on conflicts every other commit. In order to be able to resolve some confusing conflicts, I must sometimes --abort and check out the master branch to see what exactly is there (unconfounded by conflict markup, stuff rebased so far, or git's "ours" vs. "theirs" hell). Whenever I do this, I must subsequently re-resolve all conflicts up to that point. This makes the rebase effectively O(n^2).

Is there a better way?

(Note: it absolutely must be a rebase, this requirement is a given. Merging is out of the question).

[There's always the comically oversized hammer of git-rerere.](https://git-scm.com/docs/git-rerere) Never tried it, don't know if it is helpful in your case. The less silly way would be to have the master branch checked out in a different directory and being able to examine it without aborting. — , Apr 01 '21 at 08:06

score 1 · Accepted Answer · answered Apr 01 '21 at 08:15

1

First, the new (Git 2.30) new merge strategy: ORT ("Ostensibly Recursive's Twin") will be slightly faster.
But the all process would still be not O(n).

Second, do use the git worktree command in order to checkout master in a separate folder (without making a separate clone).
That way, you don't have to abort the merge in progress, and can compare with a copy of your working tree, on master branch.

answered Apr 01 '21 at 08:15

VonC

1,262,500
529
4,410
5,250

Thanks! I meant O(n) in the number of "stumbles". If I never redo a "stumble", then it's linear. – Szczepan Hołyszewski Apr 01 '21 at 08:38

How to do a difficult rebase in O(n) rather than O(n^2)?

1 Answers1