{"thread":{"id":"23404","subject":"RFD: a compressed view of branching history - struts, joins and roots","startedAt":"2010-04-10T00:00:58Z","lastAt":"2010-04-10T00:00:58Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"139095","messageId":"v2x2cfc40321004091700o9a00e3bei22f0b953839efe00@mail.gmail.com","threadId":"23404","inReplyTo":null,"subject":"RFD: a compressed view of branching history - struts, joins and roots","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2010-04-10T00:00:58Z","receivedAt":"2010-04-10T00:00:58Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"For some purposes (such as the merge linearisation algorithm I have\ndescribed previously), it would be handy to have a compressed view of\nthe branching structure of a git commit history.\n\nI'd like to discuss the idea here and solicit feedback on the design\nof rev-list options that would generate  such a compressed\nrepresentation.\n\nThe basic idea is to compress the representation of sequences of\ncommits that have exactly one parent and one child into an equivalent\n\"strut\" that names the base fork or root of the strut and the parent\nand parent-index of the tip of the strut.\n\nSo, for example, consider this graph:\n\nZ--A---B---C--D--E--F--K--L--M\n     \\           / \\           /\n     H--G--F  J-------/\n   /\nX\n\nThe struts and joins representation of this graph would be:\n\ntip M\njoin F\nstrut F..M^1\njoin C\nstrut C..F^1\nstrut C..F^2\njoin A\nstrut A..C^1\nstrut A..H^1\njoin H\nstrut H..C^2\nroot Z\nstrut Z..A^1\nroot X\nstrut X..H^2\n\nroot Z and root X define the boundary of the slice, but are not\nelements of the slice\nstrut F..M^1  contains K and  L but not F or M.\nstrut A..H^1 is zero-length\n\nAside from a use in my merge history linearisation algorithm, I can\nimagine this might be useful for driving an algorithm that exported a\nset of patch series with git format-patch for the purposes of\nreconstructing the merge history in some other place.\n\nThe list of tips, joins and roots is relatively easily obtained with a\nfew judicious uses of git rev-list, but unless I am mistaken producing\na list of struts is more involved.\n\nSo, here is a proposal for some options to git rev-list that might\nproduce the above representations:\n\n--struts\n\n    Reduces the specified set to a set of set specifications of the\nform {fork}..{merge}^{parent} where each such specification specifies\na linear history of commits which exactly one parent and exactly one\nchild\n\n--joins\n\n   Reduces the specified set to a subset of commits each of which has\nat least two parents or at least two children. [ By definition a\ncommit with exactly one parent and one child is a member of a strut ]\n\n--roots\n\n   Produces the set of commits that are not in the specified set of\ncommits but are directly reachable from the specified set of commits\n\n--tips\n\n   Produces the subset of commits in the specified set that have zero children.\n\nWould anyone care to comment on this proposal, particularly the\nsuggested option names?\n\njon.\n"}]}