git history order strange

Hi,

I have noticed that git-rev-list can output commit IDs in the wrong order. Steps to reproduce:

	git-clone git://git.kernel.org/pub/scm/git/git.git
	git-rev-list 3bddd7d

this will output

	...lots of IDs...
	8e1454b5ad285ec5dd25758e799c589045aff9d4
	6b7d25d97bdb8a26719f90d17ff5c9720be68762
	...lots of more IDs...

but this order seems to be the wrong way around, as 8e14 is the parent of 6b7d:

	git-log --pretty=raw 6b7d25d
	commit 6b7d25d97bdb8a26719f90d17ff5c9720be68762
	tree 661dce6a7e0f319fa1c53eb94c34585ee52190e4
	parent 8e1454b5ad285ec5dd25758e799c589045aff9d4

To be noted that it only happens with `git-rev-list`, but not with `git-rev-list --date-order` or `git-rev-list --topo-order`. Is it a bug in git-rev-list w/o arguments, or do I have to expect commits in random reverse order?

thanks, Jan

On Mon, 10 Mar 2008, Jan Engelhardt wrote:

They are not in "random" order, but if you have some use that requires strict topological order, then you do need --topo-order (or --date-order, which is just a specific case of --topo-order).

By "strict" topo order I mean that _all_ commits are properly sorted with _all_ children coming before their parents.

The regular "unordered" rev-list output does mean that at least _one_ child will have been printed out before its parent, but if a commit has multiple children, it's possible that it has been reached and printed through one of those children before all the other children have been parsed and output.

Put another way: say that the tree looks like

					HEAD
				      /
	--- f --- e --- c --- b --- a
	            \       /
	              - d -

where 'a' is the most recent head commit. In this case, git-rev-list with --topo-sort would guarantee that *both* 'c' and 'd' will be printed before 'e', but without --topo-sort, it only guarantees that it will print _one_ way of reaching 'e', but not necessarily all ways.

IOW, you might see the sequence a, b, c, e, f, d (where 'd' is printed after not only its direct parent, but even after its grandparent), but if you gave 'a' as a starting point you would never see the sequence a, b, e, c, d, f (because there is no way to get to 'e' without going through either c or d).

Of course, if you give both 'a' and 'e' to git-rev-list as starting points, all bets are off (it doesn't have to go through 'c' or 'd' to get to 'e' in that case ;)

So there are _some_ ordering guarantees even without --topo-order or --date-order, but they are just much much weaker.

			Linus