Which order does `git rebase` use to cherry-pick the commits from a merged branch?

Question

Suppose we have:

C1--C2--C3--C6--C7   <- topic, HEAD
 \   \     /
  \  C4--C5      
   \
    C8--C9           <- master

(We added an empty file1 and commited to C1, added an empty file2 and commited to C2, and so on).

Then we do:

$ git rebase master

The result is:

C1--C8--C9                         <- master
         \
         C4'--C2'--C5'--C3'--C7'   <- topic, HEAD

I already created an auto bash script here, you could test it if you want.

As I learned from chapter 3.6 in git-scm.com book, Git skipped the C6 which is the merged result, so the C6' isn't presented here.

My question is, which order Git use to cherry-pick from the topic branch? Why the result is ...-C4'--C2'--C5'--C3'--C7' instead of ...-C2'--C3'--C4'--C5'--C7' (which is in order of time)?

Answer 1

(By the way, thanks for the reproducer script—it was extremely helpful here.)

The order has varied in the past, but in general it is generated by running git rev-list (the sister command of git log that produces just hash IDs by default). Since hash IDs are difficult for humans, it's usually easier to use git log to see the order.

In this case the order came from:

$ git log --oneline --reverse --no-merges master..topic
5ff52aa C4
aefbb19 C2
0363c27 C5
90aaf5d C3
f953082 (topic) C7

However, if we add --topo-order, which git rebase did in various older Git versions, we get:

$ git log --oneline --reverse --topo-order --no-merges master..topic
aefbb19 C2
90aaf5d C3
5ff52aa C4
0363c27 C5
f953082 (topic) C7

The actual order is based on commit timestamps in the case where there is more than one active commit to choose from. That is, Git is doing a revision walk, from tip commit backwards. Whenever there is a merge, Git puts all the parents into the priority queue, increasing the number of commits to be visited. The default sort order for the priority queue is based on committer timestamp. Since git rebase does not set any other priority, this is the one that gets used.

(The new-ish, non-topologically-sorted order is a result of the new-ish git rebase--helper internal command, which first appeared in Git version 2.13. The merge "preserving"—really, re-creating—variant of git rebase -p still uses a topological sort. The fancy new labeled git rebase -r does not require a topo-sort.)