How does git-rev-list order the commits that it returns?
I am mostly referring to commits that come in on a concurrent branch of development and then is merged into the main branch. It doesn't seem that the commits are ordered with respect to date, which makes sense because commits can be cherry-picked from various times in the past or future.
For instance, here is some history from git-log...
* Sat, 25 Aug 2012 11:37:23 -0700 8238401
|\
| * Thu, 23 Aug 2012 12:29:09 -0700 c9de861
* | Fri, 24 Aug 2012 16:29:01 -0700 b7e8827
|\ \
| * | Mon, 14 May 2012 20:46:30 +0200 0a1db74
| * | Mon, 14 May 2012 17:54:25 +0200 e03e71d
| * | Fri, 13 Jul 2012 12:01:11 +0200 bffa852
* | | Fri, 24 Aug 2012 15:45:13 -0700 09fad50
|\ \ \
| * | | Fri, 24 Aug 2012 12:19:22 -0700 97a17e4
| * | | Thu, 9 Aug 2012 19:43:25 -0700 5f4a61a
| * | | Fri, 3 Aug 2012 14:28:07 -0700 0c8858d
| * | | Thu, 2 Aug 2012 13:00:58 -0700 aa13bf0
| * | | Wed, 18 Jul 2012 14:30:15 -0700 decff7b
* | | | Fri, 24 Aug 2012 15:43:19 -0700 091c742
Here is the output of the same history via rev-list.
$ git rev-list HEAD --max-count=13
8238401ccb9f7018c927866896bea583d351ad2a # 1 root
c9de8611d6a3e77757a714cdf6acf46178b1d622 # 2 descends into the second parent
b7e8827b8bbca0c69d85be34cc4a88888c1152f2 # 3 first parent of root
09fad5069636fb2e8cacf15817834e3d32ff6b8e # 4 descends into the first parent
091c742af985cc78711727ca06a24ae42b376fae
7fbca880aa5c011257ef734d0b5bfd5545dbaf6b
07c06f7a83640e11d6be13a87f02e986ecc6e4b3
1168410426293aef8ce33becb277ff225595e183
97a17e4e9fa5cafa531ff79cb88a9ee5c224a613
0a1db746fbcaf09681e446250f75581cc8f8fd05
e03e71da56608f60770eb80767dcd94e698cdcae
5f4a61aea834fe25ce1596bc9c0e0b5e563aa98b
0c8858de8c82bae3fd88513724689a07d231da7e
How does the rev-list command decide whether to list a first-parent or descend into a n-th-parent's commit graph? For instance, above after looking at (1), the rev-list descends into the second parent (2). However, after looking at (3) it descends into the first parent (4). Is this behavior well-defined?
By default, the commits are ordered in reverse chronological order. You can get output in a different ordering depending on the options you pass. See the Commit Ordering section in the git-rev-list man page for the other options.
git log orders in reverse chronological order by default, too. However, when you run it with --graph it implies --topo-order.
Lastly, the commit ordering by date is done by commit date, but the default output of git log displays author date. With patches, cherry-picks, and rebases, those two can get out of sync.
Those last two points should explain why your two outputs are ordered differently, and why on the surface git rev-list isn't ordering by date.