git equivalent to hg rebase -s source -d destination?

git, rebase

Solution

This can be done in Git, but it's more complicated. To understand why, and therefore get to how, we need to review a key difference between Mercurial and Git.

[Edit, a day or two later: I hate to make this longer, but I think I can summarize the problem in two key points now. It boils down to:

Mercurial allows multiple heads—Mercurial's notion of a tip of a branch is called a head—within a branch. When this situation occurs, Mercurial just deals with it, because it can and must.

Git's design makes it impossible, by definition, to have multiple tip commits—Git's notion of the tip of a branch is called a tip—on the same branch. This means Git can't have the equivalent, does not have to deal with it, and simply doesn't try. But we can do what we might want, using Git's built-in tools; it just gets messy.

The remainder is the detailed explanation, along with a way—one that gets quite clumsy—to do the job with existing Git tools. What's really needed to do what `hg rebase` does just with one command, is a better Git tool, but as far as I know it does not exist. I wanted it for a while, and started writing it, but then the use case itself went away and I left it as a prototype that did only what I needed at the time.]

Branches vs commits

In Git, a branch (name) is merely a pointer to a single commit:

...--A--B--C--D   <-- branch1
         \
          E--F    <-- branch2

The name `branch1` is just a pointer, remembering the raw hash ID of commit `D`. The name `branch2` is also just a pointer, remembering the raw hash ID of commit `F`.

All commits have their own identity, but commits `A` and `B` are on both branches. Commits `C` and `D` are reachable only via `branch1`, commits `E` and `F` are reachable only via `branch2`, and commits `A` and `B` are reachable from both names. In Git, that's what it means for a commit to be "on a branch".

In Mercurial, things are very different. A branch (name) is a very solid entity, and we can draw this graph like this instead:

branch1: ...--A--B--C--D
                  \
branch2:           E--F

Here, commits `A` through `D` are on `branch1`. None of them are on `branch2`. They can never be on `branch2`. Commits `E` and `F` are on `branch2` and they are forever stuck on `branch2` and will never be on `branch1`. It's true that we can merge `branch2` back into `branch1`, making commits `E` and `F` reachable—but in Mercurial, reachability has no effect on the grouping of commits into branches. Commits are made on a branch, and are forevermore glued to that branch.

This, of course, means that pruning and re-grafting commits in Mercurial makes it obvious that the commits are copied. The new copies are on the other branch: they're clearly different from the originals. The meaning of the phrase "commit X is on branch Y" is permanent and unchanging. A commit's identity depends on its branch.

In Git, however, the meaning of "commit X is on branch Y" is volatile. The commit is on the branch only as long as the branch label, which is a temporary and moveable thing, makes the commit reachable. Commits can be on many branches simultaneously, or even on no branch at all. A commit has identity independent of any branch label.

This enables Mercurial to have "multiple heads" within a branch

What Git calls a tip commit, Mercurial calls a head. Let me redraw your example, but Git-ified:

A--B--C   <-- tip1
 \
  D--E    <-- tip2
   \
    F     <-- tip3

There are three tip commits here, hence three branches, named `tip1` through `tip3`. These identify commits `C`, `E`, and `F`.

Mercurial sticks commits into branches. This allows us to have a fork within a branch. I can't "do" color, but assume the first line `A--B--C` is in, say, yellow and the remaining lines are in green, denoting which commits are on which branches:

branch1:  A--B--C
           \
branch2:    D--E
  ...        \
branch2:      F

Here, `branch2` contains both commits `E` and `F`, even though they are different heads (what Git would call "tips"). This situation is impossible in Git, because two different tip commits need two different branch-names to point to them. You can't draw one single arrow, coming from the right, that points to both `E` and `F`, which are all in the "green zone" (`branch2`).

Addendum (per edit): even "intra-branch", Hg has more information than Git

Even if all the commits are on one branch, Mercurial's internals give it a direct ability that Git lacks. We can point to a commit (by hash ID, sequential number, or Mercurial bookmark) and ask for "all descendant heads that are in this branch". Those are all the head commits whose branch is the current branch (and whose sequence number is greater, although that's an optimization) for which the given commit is an ancestor. (Usually we consider a commit its own descendant and ancestor, and we would here too.) This gives us (or hg) a (fast) way to find all "interesting" heads, and hence all the commits to rebase.

Git's commits have no equivalent: it's impossible to tell, in general, which commits are descendants of some commit. Instead, we can only tell which commits are ancestors, by following internal commit IDs backwards (from commits to their parents). The closest we can get to Mercurial's ability is to say "starting from some given branch tip(s) and working backwards, see which branch-tips have this commit as their ancestor; use all those branch-tips." (Of course, `--branches` would suffice here, but that is something `git rebase` doesn't do. It's also pretty slow.)

How to get what you want in Git

Because Git does not have multiple heads, and Git's branches are so ephemeral, we must start with our Git-specific drawing with three branches named `tip1` through `tip3`. We can then rebase either `tip2` or `tip3`: the choice is arbitrary.

Just as in Mercurial, rebasing means copying. Let's rebase `tip2` to get `D'` and `E'`. We start with this, which I've redrawn a bit to leave some more room:

A--B--C    <-- tip1
 \
  \
   \
    D--E   <-- tip2
     \
      F    <-- tip3

Now we run:

$ git checkout tip2 && git rebase tip1

This first gets us `on branch tip2`, as `git status` would say, so that our rebase will affect branch-pointer `tip2`. Then, it instructs Git to find commits that are reachable from the current branch (`tip2`) but not reachable from the given branch `tip1`. These are commits `D` and `E`. Then, Git should copy these two commits, with the copies placed after the `--onto` argument.

We didn't give an `--onto` argument but it defaults to the argument we did give, which is `tip1`; and `tip1` points to commit `C`. So the copies are placed after `C`. The last step of the rebase is to abandon the original chain of commits (though `ORIG_HEAD` and the reflog for `tip2` will remember them for a while) and make the current branch, i.e., `tip2`, point to the final copied commit, i.e., `E'`:

A--B--C        <-- tip1
 \     \
  \     D'-E'  <-- tip2
   \
    D--E       [ORIG_HEAD]
     \
      F        <-- tip3

We're halfway done. Now we hit the hard part: we need to rebase `tip3` as well. We want our new copy of `F'` to come after commit `D'`. This means we must find the ID of `D'`.

Finding this ID is a bit tricky. In this case, it's easy enough: it's the parent commit of the new `E'`, and `tip2` points to `E'`, so we just need to name the parent of `tip2`, for which any of these syntaxes work:

tip2^     # equivalent to tip2^1
tip2^1    # the first (and only) parent of the commit found via tip2
tip2~     # equivalent to tip2~1
tip2~1    # the commit found by moving one first-parent step back

(The difference between the `^` and `~` syntax is useful when you are crossing merge commits, which have more than one parent. If we wanted to move more commits back in a longer chain, we could repeat `^` many times, e.g., `foo^^^^^`, or use the `~` syntax: `foo~5`. For cases like this, use whichever one you find easier to type.)

The naïve attempt here—which usually works—is simply to run:

$ git checkout tip3 && git rebase tip2^   # I find ^ easier to type

This finds commits reachable from `tip3` but not from `tip2^`. Those are, of course, commit `F` itself, and—uh oh—commit `D`. Note that when we start from `tip2^` and work backwards, we go from `D'` to `C` to `B`. So this rebase will copy both `D` and `F`, rather than just copying commit `F`. The copies will go after `D'`, which is the commit we identified by writing `tip2^`.

This seems like a disaster: Won't we get a new copy `D''`? And sometimes we will, and that is a (small) disaster. But when `git rebase` is doing its copies, it first checks to see if the commit it's copying—which, remember, is `D`—has a copy in the list of commits it should skip.

The list of commits it should skip is `D'` (`tip2^`) and `C` (`tip2^^` or `tip2~2`). And, what do you know, `D'` is a copy of `D`. As long as `git rebase` can figure this out, it skips copying `D` after all. The result is:

A--B--C        <-- tip1
 \     \
  \     D'-E'  <-- tip2
   \     \
    D     F'   <-- tip3
     \
      F        [ORIG_HEAD]

(What happened to `E` here? The answer is: I'm not drawing in any of the reflog entries. Normally `git log` skips them, so I am skipping them too. I am only including `ORIG_HEAD`, the special name that `git rebase` leaves behind. The old `ORIG_HEAD` pointed to `E`, but the new rebase over-wrote it, so now we only see commit `F`—and even then, only if we use `git log --all`.)

Now, there are cases when `git rebase` can't figure out that `D` got copied to `D'`. Specifically, these occur if the first rebase—the one that made `tip2` point to `E'`—had a conflict that you had to manually resolve while copying `D`.

In this case, you need a smarter `git rebase` command, instead of the naïve version. This is when you need the `--onto` argument:

$ git checkout tip3 && git rebase --onto tip2^ tip3^

This `git rebase` takes two parameters:

- A set of commits to exclude: that's `tip3^`, i.e., commit `D` and everything earlier.

- A place to start copying after: that's `tip2^`, i.e., commit `D'`.

This tells `git rebase` to copy commit `F`, but not `D` or anything before `D`, and place the copies after `D'`.

It would be nice if we could tell `git rebase` to do multiple branch-tips, but we can't. It would be nice if we could tell Git to figure out where `D` and `D'` are automatically, and here we have a bit more luck, but it's still tricky. A few years ago, I started to write some code along these lines, but I abandoned the effort when I was getting too little gain for too much pain. The cases I really cared about were already being handled by the copy-detection during a naïve-style `git rebase`.

Problem

Original source

Related problems

• Setting git parent pointer to a different parent