RFD: a compressed view of branching history - struts, joins and roots

RFD: a compressed view of branching history - struts, joins and roots

[Jon Seymour]

For some purposes (such as the merge linearisation algorithm I have
described previously), it would be handy to have a compressed view of
the branching structure of a git commit history.

I'd like to discuss the idea here and solicit feedback on the design
of rev-list options that would generate  such a compressed
representation.

The basic idea is to compress the representation of sequences of
commits that have exactly one parent and one child into an equivalent
"strut" that names the base fork or root of the strut and the parent
and parent-index of the tip of the strut.

So, for example, consider this graph:

Z--A---B---C--D--E--F--K--L--M
     \           / \           /
     H--G--F  J-------/
   /
X

The struts and joins representation of this graph would be:

tip M
join F
strut F..M^1
join C
strut C..F^1
strut C..F^2
join A
strut A..C^1
strut A..H^1
join H
strut H..C^2
root Z
strut Z..A^1
root X
strut X..H^2

root Z and root X define the boundary of the slice, but are not
elements of the slice
strut F..M^1  contains K and  L but not F or M.
strut A..H^1 is zero-length

Aside from a use in my merge history linearisation algorithm, I can
imagine this might be useful for driving an algorithm that exported a
set of patch series with git format-patch for the purposes of
reconstructing the merge history in some other place.

The list of tips, joins and roots is relatively easily obtained with a
few judicious uses of git rev-list, but unless I am mistaken producing
a list of struts is more involved.

So, here is a proposal for some options to git rev-list that might
produce the above representations:

--struts

    Reduces the specified set to a set of set specifications of the
form {fork}..{merge}^{parent} where each such specification specifies
a linear history of commits which exactly one parent and exactly one
child

--joins

   Reduces the specified set to a subset of commits each of which has
at least two parents or at least two children. [ By definition a
commit with exactly one parent and one child is a member of a strut ]

--roots

   Produces the set of commits that are not in the specified set of
commits but are directly reachable from the specified set of commits

--tips

   Produces the subset of commits in the specified set that have zero children.

Would anyone care to comment on this proposal, particularly the
suggested option names?

jon.