RFD: best way to automatically rewrite a git DAG as a linear history?

RFD: best way to automatically rewrite a git DAG as a linear history?

[Jon Seymour]

Does the git toolset currently support rewriting a restricted git DAG
as a linear history in a completely automated way?

I understand that git rebase --root will attempt to rebase a DAG, but
as far as I can tell any conflicts that occur during the rebase
require a manual intervention to correct. My goal is a completely
automated rewrite.

I guess some might be sceptical that a sane automated rewrite is
impossible, but I am insane enough to think it might actually be
possible.

I have prototype that implements an algorithm that does this [ for a
restricted class of DAG of interest to me ], so I can't be completely
insane, but if other people have already knocked the corners of this
particular wheel, I'd be interested to learn of their efforts.

Regards.

jon

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Jeff King]

On Thu, Feb 18, 2010 at 01:35:07PM +1100, Jon Seymour wrote:

> Does the git toolset currently support rewriting a restricted git DAG
> as a linear history in a completely automated way?

Not really. It's a hard problem in the general case. Consider a history
like:

    B
   / \
  A   D
   \ /
    C

That is, two branches fork, each make a commit, and then merge. You want
something like:

  A--B--C'

If there is a merge conflict when making D, then you know that B and C
conflict. In this simple case, you can apply the same conflict
resolution used in D to the creation of C' (in other words, you use the
combined tree state given in D as the tree for C'). But what if C is a
string of commits? Some of the conflict resolution in D will be
applicable to some of the conflicts you will encounter when rebasing C,
but you don't know which.

One simple strategy would be to squash all side-branch development into
a single commit. So you would turn:

    B--C--D
   /       \
  A         H
   \       /
    E--F--G

into

  A--B--C--D--X

where X has the same tree as H, but contains all of the commit messages
of E, F, and G.

You are of course losing quite a bit of information there, but you
haven't really told us what your use case is, so I don't know whether
that's unacceptable or not.

-Peff

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Avery Pennarun]

On Thu, Feb 18, 2010 at 12:11 AM, Jeff King <peff@peff.net> wrote:
> One simple strategy would be to squash all side-branch development into
> a single commit.

Something like this (replace MY_START_BRANCH with your starting
branch, and do this in a clone of your repository so you don't destroy
anything by accident):

        parent=""
        git rev-list --first-parent --reverse  | while read commit; do
                if [ -z "$parent" ]; then
                        git checkout -f $commit
                        git clean -fdx
                else
                        git diff $parent $commit | git apply --index
                        git commit -C $commit
                fi
                parent=$commit
        done

Have fun,

Avery

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Jon Seymour]

Jeff,

The use case is extracting a patch series from a developer who has
been frequently pulling (and thus merging) with an upstream but has
not successfully delivered anything upstream.

I want to be able to unpick the upstream merge history and reconstruct
a reasonable faithful representation of the developer's edits in a
linear series of commits that can then be reviewed, edited, squashed,
re-ordered as necessary as part of integration activities. I also want
to handle the cases where a (bad) upstream rebase occurred or the
developer has (incorrectly) merged with history from a peer that has
also not been integrated upstream

This places a useful constraint on the DAG rewrite that I need to do -
I can restrict the rewrite to the reverse of linear traversal from the
developer's current head back to the first commit that has not been
integrated upstream.

Avery's script almost does what I need, except the rewritten diffs
corresponding to the merge commits introduces unnecessary noise (from
upstream deltas) in the series and potentially complicate eventual
merges of the linear history back into the upstream.

What I am doing at the moment is doing a piece-wise replacement of
each merge with an equivalent rebase  from the other branch of the
merge, starting with the oldest merge. While doing this, there arises
the possibility of a merge conflict between a commit made by the
developer and a commit on the other branch of the merge. For my
purposes, at the point of the pick where the conflict is detected, the
conflicted blob is resolved in favour of the developer's blob. This
technically introduces an error into the history since resolving the
conflict in this way is almost certainly not correct. However, it does
mean that all subsequent picks on that segment for that blob will
apply correctly. At the end of each the rewrite of each segment, the
conflicted blob is replaced with the result of the developer's
original merge so that the introduced error is then corrected with a
perfect correction (assuming the developer did a sane merge in the
first place). In effect, each conflict introduces two deltas into the
history - one to enable the subsequent picks to apply cleanly and one
to reapply the developer's original resolution of the conflict.

This approach has several consequences:

* the rewrite is completely automated
* by construction, the tree will be consistent with developer's tree
at the commit corresponding to each merge the developer did.
* there is one commit in the rewritten history for each commit in the
original history + two commits for each auto-resolved conflict (one
that introduces the error to and one that later corrects it using the
developer's merge)

It is true that the rewritten history does contain periods where the
intervening commits are not strictly consistent (periods between the
error introducing delta and its subsequent correction), but if this is
really important, these can be resolved with an interactive rebase as
required. On the otherhand, rewritten history will be fully consistent
at well-specified points - particularly at commits corresponding to
the original merge commits and on any segment that was not affected by
a merge conflict.

Regards,

jon seymour.

On 18/02/2010, at 16:11, Jef King <peff@peff.net> wrote:

> On Thu, Feb 18, 2010 at 01:35:07PM +1100, Jon Seymour wrote:
>
>> Does the git toolset currently support rewriting a restricted git DAG
>> as a linear history in a completely automated way?
>
> Not really. It's a hard problem in the general case. Consider a
> history
> like:
>
>    B
>   / \
>  A   D
>   \ /
>    C
>
> That is, two branches fork, each make a commit, and then merge. You
> want
> something like:
>
>  A--B--C'
>
> If there is a merge conflict when making D, then you know that B and C
> conflict. In this simple case, you can apply the same conflict
> resolution used in D to the creation of C' (in other words, you use
> the
> combined tree state given in D as the tree for C'). But what if C is a
> string of commits? Some of the conflict resolution in D will be
> applicable to some of the conflicts you will encounter when rebasing
> C,
> but you don't know which.
>
> One simple strategy would be to squash all side-branch development
> into
> a single commit. So you would turn:
>
>    B--C--D
>   /       \
>  A         H
>   \       /
>    E--F--G
>
> into
>
>  A--B--C--D--X
>
> where X has the same tree as H, but contains all of the commit
> messages
> of E, F, and G.
>
> You are of course losing quite a bit of information there, but you
> haven't really told us what your use case is, so I don't know whether
> that's unacceptable or not.
>
> -Peff

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Avery Pennarun]

On Thu, Feb 18, 2010 at 8:04 PM, Jon Seymour <jon.seymour@gmail.com> wrote:
> Avery's script almost does what I need, except the rewritten diffs
> corresponding to the merge commits introduces unnecessary noise (from
> upstream deltas) in the series and potentially complicate eventual
> merges of the linear history back into the upstream.

You're never going to get the "linear" history merged back upstream
until you fix the inconsistencies.  At least, no sensible upstream
should accept the patches.

Using the linearization mechanism you propose, you end up producing a
false history: one in which, other than at certain checkpoints, the
code doesn't even work.  What's the point of such a history?  It
neither reflects the true development history (ie. pre-linearization)
nor a more useful, idealized version of history (ie. one that compiles
at every point and adds features in a rational order and is useful for
git bisect).

It doesn't even provide something useful for patch review, since half
your patches will have randomly-selected conflict resolutions (ie.
changes to unrelated code that never should have changed) thrown in.
You'd be better off reviewing patches from the original history, and
just ignoring merge commits, which is what 'git format-patch' or just
'git log -p' would do automatically.

The result is also still not suitable for submission upstream: the
sync points (where the files actually match what the developer had in
his tree) are the only places where the code is even likely to
compile, and yet they *also* include all the code brought in by prior
merges, which you already said include code that shouldn't go
upstream.

The linearization script I gave you at least has these interesting
characteristics:

- If the original history compiled at every point, then the linearized
history does too.

- It is an accurate representation of the successive states of the
tree experienced by the original developer.

- You can use 'git rebase' to incrementally rearrange and combine
patches until they make enough sense to submit upstream.

- It is easy to separate out merges (which usually don't need patch
review) from individual patches (which do).

- If some merges added useless code, you can remove them completely
with rebase by just removing a single patch from the list.

Of course, even with this script, it will still take work (rebasing)
to produce code that's polished and ready to go upstream.  But I'm not
sure there's a way to automate that without producing interim versions
that are much, much worse.

Have fun,

Avery

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Jon Seymour]

On Fri, Feb 19, 2010 at 2:13 PM, Avery Pennarun <apenwarr@gmail.com> wrote:
> On Thu, Feb 18, 2010 at 8:04 PM, Jon Seymour <jon.seymour@gmail.com> wrote:
>
> Using the linearization mechanism you propose, you end up producing a
> false history: one in which, other than at certain checkpoints, the
> code doesn't even work.  What's the point of such a history?  It
> neither reflects the true development history (ie. pre-linearization)
> nor a more useful, idealized version of history (ie. one that compiles
> at every point and adds features in a rational order and is useful for
> git bisect).

If there are no merge conflicts in the original history, then there
will be no merge conflicts in the rewritten history, and therefore no
error deltas.

The point of creating the linearization of this kind is that if there
are no merge conflicts, it flattens the hierarchy in a form that is
immediately rebaseable and will faithfully represent the work the
developer would have done if they had decided to rebase at each merge
instead of merging.

If there are merge conflicts, then it produces a history that
indicates the extent the merge conflict rectification that will be
needed which then allows you to decide whether you want to attempt the
rebase.  If you decide to rebase, then it should just be a question of
deleting the delta commits and fixing the merge conflicts as they crop
up.

My contention is that most of the text diffs in the rewritten history
(with the exception of the error deltas) will actually represent the
intent of the developers original changes although until the
rectification work is done the commit sequences bounded by error
deltas would not be usable for git bisect, compiles or any other
purpose that requires an intact tree.

In the no  conflict case, it is not clear to me that the history
resulting from your script is immediately rebaseable, precisely
because of the presence of the merge commits [ feel free to correct me
if I am wrong about that ] . With my approach, the merge commits
dissolve away - there is nothing to edit.

>
> It doesn't even provide something useful for patch review, since half
> your patches will have randomly-selected conflict resolutions (ie.
> changes to unrelated code that never should have changed) thrown in.
> You'd be better off reviewing patches from the original history, and
> just ignoring merge commits, which is what 'git format-patch' or just
> 'git log -p' would do automatically.

The conflict resolutions are far from random. They are precisely
chosen to reconstruct the blob in such a way that all subsequent picks
in the same path segment apply cleanly.  This is  a deliberate choice
because we know that conflict will be resolved eventually. We are
temporarily deferring correctness to allow us to automatically proceed
with a speculative rewrite of the merge history as a rebase history.
The extent of incorrectness in the history is well delimited and well
understood.

>
> The result is also still not suitable for submission upstream: the
> sync points (where the files actually match what the developer had in
> his tree) are the only places where the code is even likely to
> compile, and yet they *also* include all the code brought in by prior
> merges, which you already said include code that shouldn't go
> upstream.

I agree it is not suitable for many purposes. I contend that what it
allows one to do is rewrite the merge history as a rebase history in a
form that allows the merge conflict resolutions to be deferred. In the
no conflict case, the linearisation is immediately usable (with no
further edits) as a rebase source.

>
> The linearization script I gave you at least has these interesting
> characteristics:
>
> - If the original history compiled at every point, then the linearized
> history does too.
>
> - It is an accurate representation of the successive states of the
> tree experienced by the original developer.
>
> - You can use 'git rebase' to incrementally rearrange and combine
> patches until they make enough sense to submit upstream.
>
> - It is easy to separate out merges (which usually don't need patch
> review) from individual patches (which do).
>
> - If some merges added useless code, you can remove them completely
> with rebase by just removing a single patch from the list.
>
> Of course, even with this script, it will still take work (rebasing)
> to produce code that's polished and ready to go upstream.  But I'm not
> sure there's a way to automate that without producing interim versions
> that are much, much worse.
>
> Have fun,
>
> Avery
>

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Avery Pennarun]

On Fri, Feb 19, 2010 at 2:29 AM, Jon Seymour <jon.seymour@gmail.com> wrote:
> If there are no merge conflicts in the original history, then there
> will be no merge conflicts in the rewritten history, and therefore no
> error deltas.

I'm just worried that this is a bit misleading.  Just because there
are no conflicts at the end doesn't mean these generated interim
versions ever compiled or worked, does it?

Imagine that I have some code:

        f(a);
        g(x);

I change it so that f takes an extra parameter

        f(a, b);
        g(x);

Then I merge in someone else's branch that adds an extra parameter to
function g, but hasn't changed f:

        f(a);
        g(x, y);

The merge causes a conflict, which I resolve in the obvious way:

        f(a, b);
        g(x, y)

Now I linearize it in the way you propose, removing the "unnecessary"
merges but keeping the developer's conflict resolutions.  What I end
up with is the last code segment above - but I *don't* have the rest
of the patch that added the extra parameter to g.  So my conflict
resolution is wrong for the code that remains.  And the delta fixup
doesn't show that there was anything weird.

Unless I've misunderstood something, you've thrown away the
*advantage* that was autodetection of conflicts, in favour of having
to eyeball it.  I'm not sure there's an advantage there.

> In the no  conflict case, it is not clear to me that the history
> resulting from your script is immediately rebaseable, precisely
> because of the presence of the merge commits [ feel free to correct me
> if I am wrong about that ] . With my approach, the merge commits
> dissolve away - there is nothing to edit.

I'm pretty sure that in the absence of conflicts, you could rebase -i
my linearization and just remove the merge commits by hand, and things
should go pretty smoothly.  Or in the simplest cases (ie. the merged
code is identical), rebase would notice that the merge patches have
already been applied, and simply throw them away.

In any case, I guess if what you're doing works for you, then go for
it.  But in that case I'm not sure why you asked your original
question; what about your current method *doesn't* do what you want?

If it's just a question of always auto-resolving conflicts using the
local merge resolution, you might be interested in -Xours and
-Xtheirs:
http://n2.nabble.com/PATCH-0-8-The-return-of-Xours-Xtheirs-Xsubtree-dir-td4069081.html

If you're looking for more general suggestions about what to do when
untangling a developer's horribly over-merged tree, you may want to
consider a simple but inelegant solution that I've used myself
sometimes: just squash the entire diff from upstream to developer's
version into a single commit, then rip it apart again by hand.  In my
experience, developers who make messes of merges also don't divide
their commits into sensible fragments in the first place, so
re-dividing them yourself afterward is actually the fastest route to
sanity.

Hope this helps.

Have fun,

Avery

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Jon Seymour]

On Sat, Feb 20, 2010 at 7:20 AM, Avery Pennarun <apenwarr@gmail.com> wrote:
> On Fri, Feb 19, 2010 at 2:29 AM, Jon Seymour <jon.seymour@gmail.com> wrote:
>> If there are no merge conflicts in the original history, then there
>> will be no merge conflicts in the rewritten history, and therefore no
>> error deltas.
>
> I'm just worried that this is a bit misleading.  Just because there
> are no conflicts at the end doesn't mean these generated interim
> versions ever compiled or worked, does it?
>
> ... example elided
>
> Now I linearize it in the way you propose, removing the "unnecessary"
> merges but keeping the developer's conflict resolutions.  What I end
> up with is the last code segment above - but I *don't* have the rest
> of the patch that added the extra parameter to g.  So my conflict
> resolution is wrong for the code that remains.  And the delta fixup
> doesn't show that there was anything weird.
>

The thing is, if I linearised in the way I proposed, there would be a
conflict during the rebase of one branch of the merge onto the other -
so the conflict would be still be there.

However, what happens is that rather than stopping to manually correct
the conflict, I compensate for the conflict by introducing a patch
that restores the file to state it was in when the conflicting commit
was originally committed. This guarantees that all future picks for
that file will apply correctly.

You are entirely correct that the compensated file is no longer
consistent with the rest of the tree at that point in the history.
However, once the rewritten history passes the original merge, the
consistency of the tree will be restored (reason: by design the
rewritten history always restores the state of the tree the point in
the rewritten history that matches a merge in the original history).
The inconsistencies are thus limited in scope [ and, as you will well
see, well delimited ]

> Unless I've misunderstood something, you've thrown away the
> *advantage* that was autodetection of conflicts, in favour of having
> to eyeball it.  I'm not sure there's an advantage there.
>

The conflicts are detected and clearly marked in the history. What I
have done is simply defer the resolution of the conflicts to a point
of my later choosing so that I can continue with the linearisation
process automatically.

One nice consequence of my linearisation is that (even in the presence
of compensations) any diff between two points in the linearized
history will only show files touched by the history - not files that
changed in the upstream branch. True, some of these diffs will produce
nonsensical results (in particular diffs within a pair of compensating
deltas are not necessarily useful, nor are diffs that include one
compensation but not the other). However, diffs across histories that
do include both compensations will be sensible.

An example:

A-B-C-D-E-F-G-H
 \       \      \
  \-M-N-P-Q-R-S-T

(Merge at Q between P and E, merge at T between S and H)

Suppose a change made in C conflicts with a change made in N.

This was eventually resolved in the merge commit Q. There were no
conflicts in subsequent histories after E and Q (e.g. the merge at T
was clean)

My linearisation would first rebase on E.

    A B C D E M' e(^N) N' P' e(Q^) R' S' T'

e(^N) returns the state of conflicted files to the point they were
before N was applied.
q(Q^) returns the state of conflicted files to the point the were
after the merge at Q.

The conflict between C and N forced me to backtrack the conflicted
files to the state they were before N. This is done by the
compensation e(^N).
The commits N and P are then repicked and are guaranteed to succeed
(by definition - the conflicted files are now in the same state as
they originally were).
A reverse compensation e(Q^) is applied to ensure that R' sees the
tree as it was at Q.

The algorithm then rebases this history onto H.

    A B C D E F G H M'' e(^e(^N)) N'' P'' e(e(Q^)^) R'' S''

The following is true:

* the tree at e(e(Q^)^) is identical to the state of the tree at Q
* the tree at S'' is identical to the state of the tree at T
* the trees at M'' R'' S'' are consistent with the states that would
have been if rebases had been performed at Q and T with the same
conflict resolution outcomes.
* the trees at N'' P'' are internally inconsistent because some (but
not all) files have 'slipped backwards in time'
* the diff between M'' and R'' will be the equivalent to the diff
between M and R
* diffs between any points with M'' and S'' will only show files
touched by edits at M, N, P, R, S or the merge Q (the intermediate
rebasing on E and H dissolves the merge at T)
* the series e(^e(^N)) N'' P'' e(e(Q^)^) could be squashed into a
single commit that would correspond to the edits done in N and P and
the conflict resolution done in Q.
* the merge history ^A T  has been automatically rewritten as a rebase
history ^H S''

An interesting possibility would be to squash  e(^e(^N)) N'' e(e(Q^)^)
as N''' and then edit P'' to be consistent with a new base, N'''.  (In
fact, in this case P'' would simply be the diff between N''' and Q -
it gets more complicated if there is a series of intervening commits
between N and P).

If this worked (and there is no guarantee it would), then it would
have the effect of folding the conflict resolution with C performed at
Q into a re-edited commit N''' which is where it would have occurred
had ^A N been rebased on C in the first place.

>> In the no  conflict case, it is not clear to me that the history
>> resulting from your script is immediately rebaseable, precisely
>> because of the presence of the merge commits [ feel free to correct me
>> if I am wrong about that ] . With my approach, the merge commits
>> dissolve away - there is nothing to edit.
>
> I'm pretty sure that in the absence of conflicts, you could rebase -i
> my linearization and just remove the merge commits by hand, and things
> should go pretty smoothly.  Or in the simplest cases (ie. the merged
> code is identical), rebase would notice that the merge patches have
> already been applied, and simply throw them away.
>
> In any case, I guess if what you're doing works for you, then go for
> it.  But in that case I'm not sure why you asked your original
> question; what about your current method *doesn't* do what you want?
>

Part of the reason I asked is that I was wondering whether someone had
hit upon this solution already, and if they had, I'd take advantage of
it. My discussions with you have certainly helped me think about and
articulate the nature of the inconsistencies that are introduced, so
that has helped too.

> If it's just a question of always auto-resolving conflicts using the
> local merge resolution, you might be interested in -Xours and
> -Xtheirs:
> http://n2.nabble.com/PATCH-0-8-The-return-of-Xours-Xtheirs-Xsubtree-dir-td4069081.html
>
> If you're looking for more general suggestions about what to do when
> untangling a developer's horribly over-merged tree, you may want to
> consider a simple but inelegant solution that I've used myself
> sometimes: just squash the entire diff from upstream to developer's
> version into a single commit, then rip it apart again by hand.  In my
> experience, developers who make messes of merges also don't divide
> their commits into sensible fragments in the first place, so
> re-dividing them yourself afterward is actually the fastest route to
> sanity.

Yep, I agree that's not a bad option in many cases. It's pragmatic,
though rebuilding a history where the tree is internally consistent at
each point is a somewhat tedious. Linearisation at least holds out the
possibility of restoring consistency if you really want it for some
reason but allows you to defer the costs of doing so if you don't
really need it.

>
> Hope this helps.
>

It has.

> Have fun,

I will - I have created a github project called hammer where I will
make a realisation of these ideas available for evaluation at some
point.

git@github.com:jonseymour/hammer.git

(A hammer is, of course, a reasonably good tool for making things flat
although it does tend to break things along the way).

jon.

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Avery Pennarun]

On Fri, Feb 19, 2010 at 9:25 PM, Jon Seymour <jon.seymour@gmail.com> wrote:
> (A hammer is, of course, a reasonably good tool for making things flat
> although it does tend to break things along the way).

Nice analogy.  Well, thanks for the clarification and best of luck in
your slightly crazy project :)

Have fun,

Avery

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Jon Seymour]

On Sat, Feb 20, 2010 at 2:05 PM, Avery Pennarun <apenwarr@gmail.com> wrote:
> On Fri, Feb 19, 2010 at 9:25 PM, Jon Seymour <jon.seymour@gmail.com> wrote:
>> (A hammer is, of course, a reasonably good tool for making things flat
>> although it does tend to break things along the way).
>
> Nice analogy.  Well, thanks for the clarification and best of luck in
> your slightly crazy project :)
>

Thank you - FWIW, it is shaping up very well. In turns out that in
cases where the original merge was resolved in favour of the conflict,
the compensation can be squashed with the compensated commit -
effectively bring the eventual resolution forward in time.

This is so, so cool.

jon.

Re: RFD: best way to automatically rewrite a git DAG as a linear history?

[Jon Seymour]

Sorry, that lacked complete sense:

Thank you - FWIW, it is shaping up very well. In turns out that in
cases where the original merge was resolved in favour of the _rebased branch_,
the compensation can be squashed with the compensated commit -
effectively bringing the eventual resolution of the conflict forward in time.

jon.