{"thread":{"id":"22703","subject":"RFD: best way to automatically rewrite a git DAG as a linear history?","startedAt":"2010-02-18T02:35:07Z","lastAt":"2010-02-21T23:18:26Z","messageCount":11,"participants":["Jon Seymour","Jeff King","Avery Pennarun"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"134920","messageId":"2cfc40321002171835j107d2cdcr5f7667d769bf391e@mail.gmail.com","threadId":"22703","inReplyTo":null,"subject":"RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2010-02-18T02:35:07Z","receivedAt":"2010-02-18T02:35:07Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"Does the git toolset currently support rewriting a restricted git DAG\nas a linear history in a completely automated way?\n\nI understand that git rebase --root will attempt to rebase a DAG, but\nas far as I can tell any conflicts that occur during the rebase\nrequire a manual intervention to correct. My goal is a completely\nautomated rewrite.\n\nI guess some might be sceptical that a sane automated rewrite is\nimpossible, but I am insane enough to think it might actually be\npossible.\n\nI have prototype that implements an algorithm that does this [ for a\nrestricted class of DAG of interest to me ], so I can't be completely\ninsane, but if other people have already knocked the corners of this\nparticular wheel, I'd be interested to learn of their efforts.\n\nRegards.\n\njon\n"},{"id":"134927","messageId":"20100218051129.GD10970@coredump.intra.peff.net","threadId":"22703","inReplyTo":"2cfc40321002171835j107d2cdcr5f7667d769bf391e@mail.gmail.com","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-02-18T05:11:29Z","receivedAt":"2010-02-18T05:11:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 18, 2010 at 01:35:07PM +1100, Jon Seymour wrote:\n\n> Does the git toolset currently support rewriting a restricted git DAG\n> as a linear history in a completely automated way?\n\nNot really. It's a hard problem in the general case. Consider a history\nlike:\n\n B\n / \\\n A D\n \\ /\n C\n\nThat is, two branches fork, each make a commit, and then merge. You want\nsomething like:\n\n A--B--C'\n\nIf there is a merge conflict when making D, then you know that B and C\nconflict. In this simple case, you can apply the same conflict\nresolution used in D to the creation of C' (in other words, you use the\ncombined tree state given in D as the tree for C'). But what if C is a\nstring of commits? Some of the conflict resolution in D will be\napplicable to some of the conflicts you will encounter when rebasing C,\nbut you don't know which.\n\nOne simple strategy would be to squash all side-branch development into\na single commit. So you would turn:\n\n B--C--D\n / \\\n A H\n \\ /\n E--F--G\n\ninto\n\n A--B--C--D--X\n\nwhere X has the same tree as H, but contains all of the commit messages\nof E, F, and G.\n\nYou are of course losing quite a bit of information there, but you\nhaven't really told us what your use case is, so I don't know whether\nthat's unacceptable or not.\n\n-Peff\n"},{"id":"134988","messageId":"32541b131002181038x26093e3em250b46b5a6e9d97c@mail.gmail.com","threadId":"22703","inReplyTo":"20100218051129.GD10970@coredump.intra.peff.net","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2010-02-18T18:38:49Z","receivedAt":"2010-02-18T18:38:49Z","isPatch":false,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"On Thu, Feb 18, 2010 at 12:11 AM, Jeff King wrote:\n> One simple strategy would be to squash all side-branch development into\n> a single commit.\n\nSomething like this (replace MY_START_BRANCH with your starting\nbranch, and do this in a clone of your repository so you don't destroy\nanything by accident):\n\n parent=\"\"\n git rev-list --first-parent --reverse | while read commit; do\n if [ -z \"$parent\" ]; then\n git checkout -f $commit\n git clean -fdx\n else\n git diff $parent $commit | git apply --index\n git commit -C $commit\n fi\n parent=$commit\n done\n\nHave fun,\n\nAvery\n"},{"id":"135028","messageId":"2cfc40321002181704i73eb87demd03faaddf9bb108@mail.gmail.com","threadId":"22703","inReplyTo":"20100218051129.GD10970@coredump.intra.peff.net","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2010-02-19T01:04:15Z","receivedAt":"2010-02-19T01:04:15Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"Jeff,\n\nThe use case is extracting a patch series from a developer who has\nbeen frequently pulling (and thus merging) with an upstream but has\nnot successfully delivered anything upstream.\n\nI want to be able to unpick the upstream merge history and reconstruct\na reasonable faithful representation of the developer's edits in a\nlinear series of commits that can then be reviewed, edited, squashed,\nre-ordered as necessary as part of integration activities. I also want\nto handle the cases where a (bad) upstream rebase occurred or the\ndeveloper has (incorrectly) merged with history from a peer that has\nalso not been integrated upstream\n\nThis places a useful constraint on the DAG rewrite that I need to do -\nI can restrict the rewrite to the reverse of linear traversal from the\ndeveloper's current head back to the first commit that has not been\nintegrated upstream.\n\nAvery's script almost does what I need, except the rewritten diffs\ncorresponding to the merge commits introduces unnecessary noise (from\nupstream deltas) in the series and potentially complicate eventual\nmerges of the linear history back into the upstream.\n\nWhat I am doing at the moment is doing a piece-wise replacement of\neach merge with an equivalent rebase from the other branch of the\nmerge, starting with the oldest merge. While doing this, there arises\nthe possibility of a merge conflict between a commit made by the\ndeveloper and a commit on the other branch of the merge. For my\npurposes, at the point of the pick where the conflict is detected, the\nconflicted blob is resolved in favour of the developer's blob. This\ntechnically introduces an error into the history since resolving the\nconflict in this way is almost certainly not correct. However, it does\nmean that all subsequent picks on that segment for that blob will\napply correctly. At the end of each the rewrite of each segment, the\nconflicted blob is replaced with the result of the developer's\noriginal merge so that the introduced error is then corrected with a\nperfect correction (assuming the developer did a sane merge in the\nfirst place). In effect, each conflict introduces two deltas into the\nhistory - one to enable the subsequent picks to apply cleanly and one\nto reapply the developer's original resolution of the conflict.\n\nThis approach has several consequences:\n\n* the rewrite is completely automated\n* by construction, the tree will be consistent with developer's tree\nat the commit corresponding to each merge the developer did.\n* there is one commit in the rewritten history for each commit in the\noriginal history + two commits for each auto-resolved conflict (one\nthat introduces the error to and one that later corrects it using the\ndeveloper's merge)\n\nIt is true that the rewritten history does contain periods where the\nintervening commits are not strictly consistent (periods between the\nerror introducing delta and its subsequent correction), but if this is\nreally important, these can be resolved with an interactive rebase as\nrequired. On the otherhand, rewritten history will be fully consistent\nat well-specified points - particularly at commits corresponding to\nthe original merge commits and on any segment that was not affected by\na merge conflict.\n\nRegards,\n\njon seymour.\n\nOn 18/02/2010, at 16:11, Jef King wrote:\n\n> On Thu, Feb 18, 2010 at 01:35:07PM +1100, Jon Seymour wrote:\n>\n>> Does the git toolset currently support rewriting a restricted git DAG\n>> as a linear history in a completely automated way?\n>\n> Not really. It's a hard problem in the general case. Consider a\n> history\n> like:\n>\n> B\n> / \\\n> A D\n> \\ /\n> C\n>\n> That is, two branches fork, each make a commit, and then merge. You\n> want\n> something like:\n>\n> A--B--C'\n>\n> If there is a merge conflict when making D, then you know that B and C\n> conflict. In this simple case, you can apply the same conflict\n> resolution used in D to the creation of C' (in other words, you use\n> the\n> combined tree state given in D as the tree for C'). But what if C is a\n> string of commits? Some of the conflict resolution in D will be\n> applicable to some of the conflicts you will encounter when rebasing\n> C,\n> but you don't know which.\n>\n> One simple strategy would be to squash all side-branch development\n> into\n> a single commit. So you would turn:\n>\n> B--C--D\n> / \\\n> A H\n> \\ /\n> E--F--G\n>\n> into\n>\n> A--B--C--D--X\n>\n> where X has the same tree as H, but contains all of the commit\n> messages\n> of E, F, and G.\n>\n> You are of course losing quite a bit of information there, but you\n> haven't really told us what your use case is, so I don't know whether\n> that's unacceptable or not.\n>\n> -Peff\n"},{"id":"135031","messageId":"32541b131002181913t24989addr84b612787a2f8c48@mail.gmail.com","threadId":"22703","inReplyTo":"2cfc40321002181704i73eb87demd03faaddf9bb108@mail.gmail.com","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2010-02-19T03:13:45Z","receivedAt":"2010-02-19T03:13:45Z","isPatch":false,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"On Thu, Feb 18, 2010 at 8:04 PM, Jon Seymour wrote:\n> Avery's script almost does what I need, except the rewritten diffs\n> corresponding to the merge commits introduces unnecessary noise (from\n> upstream deltas) in the series and potentially complicate eventual\n> merges of the linear history back into the upstream.\n\nYou're never going to get the \"linear\" history merged back upstream\nuntil you fix the inconsistencies. At least, no sensible upstream\nshould accept the patches.\n\nUsing the linearization mechanism you propose, you end up producing a\nfalse history: one in which, other than at certain checkpoints, the\ncode doesn't even work. What's the point of such a history? It\nneither reflects the true development history (ie. pre-linearization)\nnor a more useful, idealized version of history (ie. one that compiles\nat every point and adds features in a rational order and is useful for\ngit bisect).\n\nIt doesn't even provide something useful for patch review, since half\nyour patches will have randomly-selected conflict resolutions (ie.\nchanges to unrelated code that never should have changed) thrown in.\nYou'd be better off reviewing patches from the original history, and\njust ignoring merge commits, which is what 'git format-patch' or just\n'git log -p' would do automatically.\n\nThe result is also still not suitable for submission upstream: the\nsync points (where the files actually match what the developer had in\nhis tree) are the only places where the code is even likely to\ncompile, and yet they *also* include all the code brought in by prior\nmerges, which you already said include code that shouldn't go\nupstream.\n\nThe linearization script I gave you at least has these interesting\ncharacteristics:\n\n- If the original history compiled at every point, then the linearized\nhistory does too.\n\n- It is an accurate representation of the successive states of the\ntree experienced by the original developer.\n\n- You can use 'git rebase' to incrementally rearrange and combine\npatches until they make enough sense to submit upstream.\n\n- It is easy to separate out merges (which usually don't need patch\nreview) from individual patches (which do).\n\n- If some merges added useless code, you can remove them completely\nwith rebase by just removing a single patch from the list.\n\nOf course, even with this script, it will still take work (rebasing)\nto produce code that's polished and ready to go upstream. But I'm not\nsure there's a way to automate that without producing interim versions\nthat are much, much worse.\n\nHave fun,\n\nAvery\n"},{"id":"135055","messageId":"2cfc40321002182329q7b8c5b90nbd77a4e0678cd9c8@mail.gmail.com","threadId":"22703","inReplyTo":"32541b131002181913t24989addr84b612787a2f8c48@mail.gmail.com","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2010-02-19T07:29:23Z","receivedAt":"2010-02-19T07:29:23Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On Fri, Feb 19, 2010 at 2:13 PM, Avery Pennarun wrote:\n> On Thu, Feb 18, 2010 at 8:04 PM, Jon Seymour wrote:\n>\n> Using the linearization mechanism you propose, you end up producing a\n> false history: one in which, other than at certain checkpoints, the\n> code doesn't even work.  What's the point of such a history?  It\n> neither reflects the true development history (ie. pre-linearization)\n> nor a more useful, idealized version of history (ie. one that compiles\n> at every point and adds features in a rational order and is useful for\n> git bisect).\n\nIf there are no merge conflicts in the original history, then there\nwill be no merge conflicts in the rewritten history, and therefore no\nerror deltas.\n\nThe point of creating the linearization of this kind is that if there\nare no merge conflicts, it flattens the hierarchy in a form that is\nimmediately rebaseable and will faithfully represent the work the\ndeveloper would have done if they had decided to rebase at each merge\ninstead of merging.\n\nIf there are merge conflicts, then it produces a history that\nindicates the extent the merge conflict rectification that will be\nneeded which then allows you to decide whether you want to attempt the\nrebase. If you decide to rebase, then it should just be a question of\ndeleting the delta commits and fixing the merge conflicts as they crop\nup.\n\nMy contention is that most of the text diffs in the rewritten history\n(with the exception of the error deltas) will actually represent the\nintent of the developers original changes although until the\nrectification work is done the commit sequences bounded by error\ndeltas would not be usable for git bisect, compiles or any other\npurpose that requires an intact tree.\n\nIn the no conflict case, it is not clear to me that the history\nresulting from your script is immediately rebaseable, precisely\nbecause of the presence of the merge commits [ feel free to correct me\nif I am wrong about that ] . With my approach, the merge commits\ndissolve away - there is nothing to edit.\n\n>\n> It doesn't even provide something useful for patch review, since half\n> your patches will have randomly-selected conflict resolutions (ie.\n> changes to unrelated code that never should have changed) thrown in.\n> You'd be better off reviewing patches from the original history, and\n> just ignoring merge commits, which is what 'git format-patch' or just\n> 'git log -p' would do automatically.\n\nThe conflict resolutions are far from random. They are precisely\nchosen to reconstruct the blob in such a way that all subsequent picks\nin the same path segment apply cleanly. This is a deliberate choice\nbecause we know that conflict will be resolved eventually. We are\ntemporarily deferring correctness to allow us to automatically proceed\nwith a speculative rewrite of the merge history as a rebase history.\nThe extent of incorrectness in the history is well delimited and well\nunderstood.\n\n>\n> The result is also still not suitable for submission upstream: the\n> sync points (where the files actually match what the developer had in\n> his tree) are the only places where the code is even likely to\n> compile, and yet they *also* include all the code brought in by prior\n> merges, which you already said include code that shouldn't go\n> upstream.\n\nI agree it is not suitable for many purposes. I contend that what it\nallows one to do is rewrite the merge history as a rebase history in a\nform that allows the merge conflict resolutions to be deferred. In the\nno conflict case, the linearisation is immediately usable (with no\nfurther edits) as a rebase source.\n\n>\n> The linearization script I gave you at least has these interesting\n> characteristics:\n>\n> - If the original history compiled at every point, then the linearized\n> history does too.\n>\n> - It is an accurate representation of the successive states of the\n> tree experienced by the original developer.\n>\n> - You can use 'git rebase' to incrementally rearrange and combine\n> patches until they make enough sense to submit upstream.\n>\n> - It is easy to separate out merges (which usually don't need patch\n> review) from individual patches (which do).\n>\n> - If some merges added useless code, you can remove them completely\n> with rebase by just removing a single patch from the list.\n>\n> Of course, even with this script, it will still take work (rebasing)\n> to produce code that's polished and ready to go upstream.  But I'm not\n> sure there's a way to automate that without producing interim versions\n> that are much, much worse.\n>\n> Have fun,\n>\n> Avery\n>\n"},{"id":"135108","messageId":"32541b131002191220q5a0eae6dk304173418f818ff3@mail.gmail.com","threadId":"22703","inReplyTo":"2cfc40321002182329q7b8c5b90nbd77a4e0678cd9c8@mail.gmail.com","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2010-02-19T20:20:09Z","receivedAt":"2010-02-19T20:20:09Z","isPatch":false,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"On Fri, Feb 19, 2010 at 2:29 AM, Jon Seymour wrote:\n> If there are no merge conflicts in the original history, then there\n> will be no merge conflicts in the rewritten history, and therefore no\n> error deltas.\n\nI'm just worried that this is a bit misleading. Just because there\nare no conflicts at the end doesn't mean these generated interim\nversions ever compiled or worked, does it?\n\nImagine that I have some code:\n\n f(a);\n g(x);\n\nI change it so that f takes an extra parameter\n\n f(a, b);\n g(x);\n\nThen I merge in someone else's branch that adds an extra parameter to\nfunction g, but hasn't changed f:\n\n f(a);\n g(x, y);\n\nThe merge causes a conflict, which I resolve in the obvious way:\n\n f(a, b);\n g(x, y)\n\nNow I linearize it in the way you propose, removing the \"unnecessary\"\nmerges but keeping the developer's conflict resolutions. What I end\nup with is the last code segment above - but I *don't* have the rest\nof the patch that added the extra parameter to g. So my conflict\nresolution is wrong for the code that remains. And the delta fixup\ndoesn't show that there was anything weird.\n\nUnless I've misunderstood something, you've thrown away the\n*advantage* that was autodetection of conflicts, in favour of having\nto eyeball it. I'm not sure there's an advantage there.\n\n> In the no  conflict case, it is not clear to me that the history\n> resulting from your script is immediately rebaseable, precisely\n> because of the presence of the merge commits [ feel free to correct me\n> if I am wrong about that ] . With my approach, the merge commits\n> dissolve away - there is nothing to edit.\n\nI'm pretty sure that in the absence of conflicts, you could rebase -i\nmy linearization and just remove the merge commits by hand, and things\nshould go pretty smoothly. Or in the simplest cases (ie. the merged\ncode is identical), rebase would notice that the merge patches have\nalready been applied, and simply throw them away.\n\nIn any case, I guess if what you're doing works for you, then go for\nit. But in that case I'm not sure why you asked your original\nquestion; what about your current method *doesn't* do what you want?\n\nIf it's just a question of always auto-resolving conflicts using the\nlocal merge resolution, you might be interested in -Xours and\n-Xtheirs:\nhttp://n2.nabble.com/PATCH-0-8-The-return-of-Xours-Xtheirs-Xsubtree-dir-td4069081.html\n\nIf you're looking for more general suggestions about what to do when\nuntangling a developer's horribly over-merged tree, you may want to\nconsider a simple but inelegant solution that I've used myself\nsometimes: just squash the entire diff from upstream to developer's\nversion into a single commit, then rip it apart again by hand. In my\nexperience, developers who make messes of merges also don't divide\ntheir commits into sensible fragments in the first place, so\nre-dividing them yourself afterward is actually the fastest route to\nsanity.\n\nHope this helps.\n\nHave fun,\n\nAvery\n"},{"id":"135138","messageId":"2cfc40321002191825i605e5045w6f52f9f044a5d369@mail.gmail.com","threadId":"22703","inReplyTo":"32541b131002191220q5a0eae6dk304173418f818ff3@mail.gmail.com","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2010-02-20T02:25:11Z","receivedAt":"2010-02-20T02:25:11Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On Sat, Feb 20, 2010 at 7:20 AM, Avery Pennarun wrote:\n> On Fri, Feb 19, 2010 at 2:29 AM, Jon Seymour wrote:\n>> If there are no merge conflicts in the original history, then there\n>> will be no merge conflicts in the rewritten history, and therefore no\n>> error deltas.\n>\n> I'm just worried that this is a bit misleading.  Just because there\n> are no conflicts at the end doesn't mean these generated interim\n> versions ever compiled or worked, does it?\n>\n> ... example elided\n>\n> Now I linearize it in the way you propose, removing the \"unnecessary\"\n> merges but keeping the developer's conflict resolutions.  What I end\n> up with is the last code segment above - but I *don't* have the rest\n> of the patch that added the extra parameter to g.  So my conflict\n> resolution is wrong for the code that remains.  And the delta fixup\n> doesn't show that there was anything weird.\n>\n\nThe thing is, if I linearised in the way I proposed, there would be a\nconflict during the rebase of one branch of the merge onto the other -\nso the conflict would be still be there.\n\nHowever, what happens is that rather than stopping to manually correct\nthe conflict, I compensate for the conflict by introducing a patch\nthat restores the file to state it was in when the conflicting commit\nwas originally committed. This guarantees that all future picks for\nthat file will apply correctly.\n\nYou are entirely correct that the compensated file is no longer\nconsistent with the rest of the tree at that point in the history.\nHowever, once the rewritten history passes the original merge, the\nconsistency of the tree will be restored (reason: by design the\nrewritten history always restores the state of the tree the point in\nthe rewritten history that matches a merge in the original history).\nThe inconsistencies are thus limited in scope [ and, as you will well\nsee, well delimited ]\n\n> Unless I've misunderstood something, you've thrown away the\n> *advantage* that was autodetection of conflicts, in favour of having\n> to eyeball it.  I'm not sure there's an advantage there.\n>\n\nThe conflicts are detected and clearly marked in the history. What I\nhave done is simply defer the resolution of the conflicts to a point\nof my later choosing so that I can continue with the linearisation\nprocess automatically.\n\nOne nice consequence of my linearisation is that (even in the presence\nof compensations) any diff between two points in the linearized\nhistory will only show files touched by the history - not files that\nchanged in the upstream branch. True, some of these diffs will produce\nnonsensical results (in particular diffs within a pair of compensating\ndeltas are not necessarily useful, nor are diffs that include one\ncompensation but not the other). However, diffs across histories that\ndo include both compensations will be sensible.\n\nAn example:\n\nA-B-C-D-E-F-G-H\n \\ \\ \\\n \\-M-N-P-Q-R-S-T\n\n(Merge at Q between P and E, merge at T between S and H)\n\nSuppose a change made in C conflicts with a change made in N.\n\nThis was eventually resolved in the merge commit Q. There were no\nconflicts in subsequent histories after E and Q (e.g. the merge at T\nwas clean)\n\nMy linearisation would first rebase on E.\n\n A B C D E M' e(^N) N' P' e(Q^) R' S' T'\n\ne(^N) returns the state of conflicted files to the point they were\nbefore N was applied.\nq(Q^) returns the state of conflicted files to the point the were\nafter the merge at Q.\n\nThe conflict between C and N forced me to backtrack the conflicted\nfiles to the state they were before N. This is done by the\ncompensation e(^N).\nThe commits N and P are then repicked and are guaranteed to succeed\n(by definition - the conflicted files are now in the same state as\nthey originally were).\nA reverse compensation e(Q^) is applied to ensure that R' sees the\ntree as it was at Q.\n\nThe algorithm then rebases this history onto H.\n\n A B C D E F G H M'' e(^e(^N)) N'' P'' e(e(Q^)^) R'' S''\n\nThe following is true:\n\n* the tree at e(e(Q^)^) is identical to the state of the tree at Q\n* the tree at S'' is identical to the state of the tree at T\n* the trees at M'' R'' S'' are consistent with the states that would\nhave been if rebases had been performed at Q and T with the same\nconflict resolution outcomes.\n* the trees at N'' P'' are internally inconsistent because some (but\nnot all) files have 'slipped backwards in time'\n* the diff between M'' and R'' will be the equivalent to the diff\nbetween M and R\n* diffs between any points with M'' and S'' will only show files\ntouched by edits at M, N, P, R, S or the merge Q (the intermediate\nrebasing on E and H dissolves the merge at T)\n* the series e(^e(^N)) N'' P'' e(e(Q^)^) could be squashed into a\nsingle commit that would correspond to the edits done in N and P and\nthe conflict resolution done in Q.\n* the merge history ^A T has been automatically rewritten as a rebase\nhistory ^H S''\n\nAn interesting possibility would be to squash e(^e(^N)) N'' e(e(Q^)^)\nas N''' and then edit P'' to be consistent with a new base, N'''. (In\nfact, in this case P'' would simply be the diff between N''' and Q -\nit gets more complicated if there is a series of intervening commits\nbetween N and P).\n\nIf this worked (and there is no guarantee it would), then it would\nhave the effect of folding the conflict resolution with C performed at\nQ into a re-edited commit N''' which is where it would have occurred\nhad ^A N been rebased on C in the first place.\n\n>> In the no  conflict case, it is not clear to me that the history\n>> resulting from your script is immediately rebaseable, precisely\n>> because of the presence of the merge commits [ feel free to correct me\n>> if I am wrong about that ] . With my approach, the merge commits\n>> dissolve away - there is nothing to edit.\n>\n> I'm pretty sure that in the absence of conflicts, you could rebase -i\n> my linearization and just remove the merge commits by hand, and things\n> should go pretty smoothly.  Or in the simplest cases (ie. the merged\n> code is identical), rebase would notice that the merge patches have\n> already been applied, and simply throw them away.\n>\n> In any case, I guess if what you're doing works for you, then go for\n> it.  But in that case I'm not sure why you asked your original\n> question; what about your current method *doesn't* do what you want?\n>\n\nPart of the reason I asked is that I was wondering whether someone had\nhit upon this solution already, and if they had, I'd take advantage of\nit. My discussions with you have certainly helped me think about and\narticulate the nature of the inconsistencies that are introduced, so\nthat has helped too.\n\n> If it's just a question of always auto-resolving conflicts using the\n> local merge resolution, you might be interested in -Xours and\n> -Xtheirs:\n> http://n2.nabble.com/PATCH-0-8-The-return-of-Xours-Xtheirs-Xsubtree-dir-td4069081.html\n>\n> If you're looking for more general suggestions about what to do when\n> untangling a developer's horribly over-merged tree, you may want to\n> consider a simple but inelegant solution that I've used myself\n> sometimes: just squash the entire diff from upstream to developer's\n> version into a single commit, then rip it apart again by hand.  In my\n> experience, developers who make messes of merges also don't divide\n> their commits into sensible fragments in the first place, so\n> re-dividing them yourself afterward is actually the fastest route to\n> sanity.\n\nYep, I agree that's not a bad option in many cases. It's pragmatic,\nthough rebuilding a history where the tree is internally consistent at\neach point is a somewhat tedious. Linearisation at least holds out the\npossibility of restoring consistency if you really want it for some\nreason but allows you to defer the costs of doing so if you don't\nreally need it.\n\n>\n> Hope this helps.\n>\n\nIt has.\n\n> Have fun,\n\nI will - I have created a github project called hammer where I will\nmake a realisation of these ideas available for evaluation at some\npoint.\n\ngit@github.com:jonseymour/hammer.git\n\n(A hammer is, of course, a reasonably good tool for making things flat\nalthough it does tend to break things along the way).\n\njon.\n"},{"id":"135139","messageId":"32541b131002191905u59a90866he0a38dfc661d45d2@mail.gmail.com","threadId":"22703","inReplyTo":"2cfc40321002191825i605e5045w6f52f9f044a5d369@mail.gmail.com","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2010-02-20T03:05:46Z","receivedAt":"2010-02-20T03:05:46Z","isPatch":false,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"On Fri, Feb 19, 2010 at 9:25 PM, Jon Seymour wrote:\n> (A hammer is, of course, a reasonably good tool for making things flat\n> although it does tend to break things along the way).\n\nNice analogy. Well, thanks for the clarification and best of luck in\nyour slightly crazy project :)\n\nHave fun,\n\nAvery\n"},{"id":"299161","messageId":"2cfc40321002211504o28069d16h4b9d1ef2230d03fe@mail.gmail.com","threadId":"22703","inReplyTo":"32541b131002191905u59a90866he0a38dfc661d45d2@mail.gmail.com","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2010-02-21T23:04:29Z","receivedAt":"2010-02-21T23:04:29Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On Sat, Feb 20, 2010 at 2:05 PM, Avery Pennarun wrote:\n> On Fri, Feb 19, 2010 at 9:25 PM, Jon Seymour wrote:\n>> (A hammer is, of course, a reasonably good tool for making things flat\n>> although it does tend to break things along the way).\n>\n> Nice analogy.  Well, thanks for the clarification and best of luck in\n> your slightly crazy project :)\n>\n\nThank you - FWIW, it is shaping up very well. In turns out that in\ncases where the original merge was resolved in favour of the conflict,\nthe compensation can be squashed with the compensated commit -\neffectively bring the eventual resolution forward in time.\n\nThis is so, so cool.\n\njon.\n"},{"id":"299162","messageId":"2cfc40321002211518u5eca5112wba42131341c3e286@mail.gmail.com","threadId":"22703","inReplyTo":"2cfc40321002211504o28069d16h4b9d1ef2230d03fe@mail.gmail.com","subject":"Re: RFD: best way to automatically rewrite a git DAG as a linear history?","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2010-02-21T23:18:26Z","receivedAt":"2010-02-21T23:18:26Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"Sorry, that lacked complete sense:\n\nThank you - FWIW, it is shaping up very well. In turns out that in\ncases where the original merge was resolved in favour of the _rebased branch_,\nthe compensation can be squashed with the compensated commit -\neffectively bringing the eventual resolution of the conflict forward in time.\n\njon.\n"}]}