Re: git-bisect failed me again

On Fri, 12 May 2006, Linus Torvalds wrote:

Note that totally independently of sort order (whether "topo-order" or the normal cheaper "order by date, but at least one chain of parenthood always first"), you _will_ get the situation that a commit that was shown "last" in a linear list is actually merged long before.

The simplest case is this:

		merge
		 |  \
		 A   \
		 |    \
		 B     \
		 |      X
		 C      |
		 |	Y
		 D	|
		 |      Z
		..	..

where the "main branch" is the A-B-C-D.. line of history, and the merge brings in another "X-Y-Z" line of history.

Now, the A-B-C branch may have gotten a lot more recent love and attention, and when you linearize it, since the normal ordering tends to show it in a date-like order, you may get a list of commits like

		merge
		A
		B
		C
		D
		..
		X
		Y
		Z
		..

which makes you think that "A" is much more recent than "X". That may be actually be _true_, but:

 - 'X' actually _showed_up_ in the mainline much later than A. So, if you 
   track another persons tree like this, X as a commit may be 2 weeks old, 
   but it might not have been in the tree you tracked yesterday, because 
   it hadn't been _merged_ until today.

   So in a very real sense, from your standpoint, 'X' may be the 'recent' 
   one, because you hadn't seen it before, but you _had_ seen 'A' 
   yesterday.

 - Equally importantly, 'A' very much is _not_ a descendant of 'X' (ie, 
   'X' is _not_ reachable from 'A'). So even though 'A' is in a time-sense 
   much more recent than 'X', you can't say "it's the most recent commit, 
   so if there's a bug in any of the series, the bug must have been 
   visible at point 'A'".

This is why it's wrong to look at _any_ linearized list of commits and imply any ordering what-so-ever. There simply is no list ordering that guarantees anything at all, because even with "topo-sort", the only thing we guarantee is that commits that are directly related to each other will always sort the child before its parents. So even there, you can't actually say that one commit "dominates" another commit unless you end up looking at the parenthood chain (and merges are really important).

[ Strictly speaking, there is exactly _one_ thing you can say from just 
  seeing a list of commits: _if_ that list includes all types of commits 
  (ie notably merges and empty changes) _and_ if that list was generated 
  with just one "top" commit, then the first commit on the list will 
  dominate all other commits. But that's literally the only real ordering 
  you can ever know from just a list.

  So looking at the first commit in a list is actually valid, but only if 
  you included all the merges and only if the list was generated by a git 
  command, and not sorted by any other criteria ]

			Linus