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.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html