Re: Shortest path between commits

[Linus Torvalds <torvalds@osdl.org>]

On Wed, 8 Feb 2006, Ralf Baechle wrote:
>
> I wonder if there some way to find the shortest path between two commits?
> That is if there is a merge between the two commits I only want the merge
> commit itself, not the potencially large list of commits that were merged.

The problem is that it's entirely possible that no such path even 
exists.

Two commits are not necessarily directly related, and asking for the 
shortest path may involve having to go both backwards _and_ forwards in 
history to get from one to the other. The most trivial case is

	    a  <- head of tree
	   / \
	  /   \
	 b     c
	  \   /
	   \ /
	    d  <- root

where the shortest path between "b" and "c" is not really a well-defined 
notion.

Now, _if_ you know that one of the commits is a direct descendant of the 
other, a sensible path can be decided on, but even then the notion of 
"shortest" is not obvious. Look at "a" vs "d" above - which path is the 
shortest one? The one through "b" or the one through "c"? There's really 
no way to tell them apart (you could select "first parent", but in more 
complex graphs that might not be unambiguous either).

That said, and to finally answer your question: selecing _one_ short path 
between two commits (if they are directly related) is certainly possible, 
but no, we don't have anything like that available right now. It wouldn't 
be hugely difficult to do an addition to git-rev-list to do so, though.

Can you describe your usage case? The operation really _isn't_ sensible in 
general, so while I could add a flag to git-rev-list to only print out as 
direct a chain as possible, I'd like to know that there is at least _one_ 
entirely sane usage for such a thing.

		Linus