Friday, December 28, 2012

Real-world conflict diagrams

In earlier articles, I described a way to diagram a conflicting merge, and presented an algorithm for efficiently mapping the conflict frontier which is implemented in an experimental program, git-mergemate.  In this article, I would like to present a few examples of real-world merge diagrams.

To generate these diagrams, I first used the following command to search for merge commits in "master" that had manually-resolved conflicts:

git rev-list --merges --grep='Conflicts:' master

Assuming that the SHA1 of the merge is stored in $s, the two parents of such a commit can be written as $s^1 and $s^2.  So I then ran git-mergemate like so:

git-mergemate diagram $s^1...$s^2

and converted the output from PPM format to PNG using the pnm2png utility [1].

Show me the pixels!

Each pixel in these diagrams represents one pairwise merge.  Thus the images are quite compact; the width (in pixels) is the number of commits on "master" after the branch point, and the height is the number of commits on the branch.  I am leaving the images at 1:1 scaling so that their relative sizes can easily be seen (hopefully you can zoom them using your browser if you want to see more detail).

A pixel is green if the corresponding merge was successful and red if the merge resulted in a conflict.  The merges that were explicitly tested are shown as bright green/red; the other merges were inferred using the assumptions described in the algorithm article.  As you can see, it takes very few test merges to compute a whole merge diagram.

Ho-hum

Most of the merge diagrams (about 80% of them) were quite boring.

A typical short branch with a conflict:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgOy0xGXDmTDeDpq0BdRLzEoA1W3R39seX7_RD0u4FD01ViLwV_q_lNlEBQjZbgPMvxN2zKN3T8oxMo3nUFybe1qwAFpmFLmu3IBpuz42gAnOL412AbKqR5r3wuQqxem_81I8wstU3Xvqk/s1600/diagram-43c456bdfa3127a2f73b3c99fb1a3e21674613ea.png

A short branch with an early conflict:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjjybk4IykVYxAiJ9u2U5-nXqiXJfO7kbjSQODQai7tQT5u65aBikUGzkjwBC_2u5hAEWjo39xYv1r7KRqyCFUEciKgpWxb2g0IOuHCUARq5_RoXlErTcWAA9ujCOpRq6FadEvhEsgmEjs/s1600/diagram-3e8ebc18283a23305179aa2055619985163fbd93.png

A very short branch merged long after it was created:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjosveq9_j9xYlko1NKeCqW_fmu94dE8In_Gv_uqECQYIp4Ur-3KzQ7gHWzO2apKIfTaL54hIqw8Eb374f2_GydTMr1KBwjB33nR2YNJmCjthCAXacL4z5yU_m2VXA4q5zqQWc6oceBa0k/s320/diagram-6cc13d7703e8dc0edccd134f44676ca9ad73dd6a.png

A longer branch merged soon after it was created, with a conflict with one of its later commits:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiczEd_xAHdY972whFdL8cbi0JUeUc8EpdevWTmV1FI9RxOwbUb48C6UVXiVqY8Su8Bc95mZP3neWoSovHL4hyupeb6LiaBhKKgxlAIYyBBzwlYN0U4c2qK94gqq_KXRQLkwjz_kiVXJeE/s1600/diagram-7f28917bfa6aef7c38a216d0e30fae40f216e8f4.png
Single conflicts

However, about 20% of the merge diagrams were more interesting.  The interesting diagrams tend to be bigger because they represent long-lived branches merged a considerable time after they were created.

Several diagrams show merges that might be blocked by a single pairwise conflict:

The conflict at the upper-left corner of the red rectangle might be all that is blocking this merge:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpchBoy8mhuo9U140LM8T_CwhBGztnsYQWWfMjgimbxe02FwhVdOZBHQ_FETMYYHMjnzHscLbFZBL08FJpApAC1Ds-hYeLal2QL_NFwmBBBmDvPsKNKyaJGTWGulB3R-6aj6vcFAzVQko/s1600/diagram-737dae7c79f05d06fada3246d2269fa4f33dd90a.png

A long branch, merged before much was changed on "master":

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjs07m54MVuWlZnxiumaXGenldz_R8VgksvnXBsykEwnCyhqdo_gyOyedz201Wm33fV27xwjfsiKx6xxCgpnif5ulcOLjlnxNhwlO_0JSP3MFh4wxlnv3e2ZRAhTVjbDgkyAeDshRa__eI/s1600/diagram-8922c2d3f89fc35636d5e41ca17dfa36b15fbd2d.png

A short branch, merged quite a while after it was created:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBrfpWjOEowIiYg2mY7FLkpVzQtpHK0zJDimeqUGGfLnDadUmYJBL49zB0I6YwDB4RHMqX89h1SD9a2pgH3bhrFiIYebgUM5MQPAIGQNZZNCqAI41T__bb8hdyH4HZS_Jzp-jjBL5OcZs/s1600/diagram-9747028e60b994b5df12cf0805c0a3b3f04d9edd.png

A branch that has diverged widely from "master", but might have only one pairwise conflict:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnxejhfQN-YDPK0rAV6VoJ79i1vmGj9LbZg17n-VCQrVHiX5Byo5RmlK1afHGgmisVh2w4HIZpq1hMf34zjQz_Muq9YgY7JnvtVMNXx-XoPWSx7ezVmLsqgqMmZTZY2IGs2Gyi_-SBFjc/s1600/diagram-e51c4480518a4b30e241e35218385ef357f0f71b.png
Multiple conflicts

Other diagrams are yet more complicated, with merge frontiers shaped by two pairwise conflicts:

A smallish diagram with two early conflict blocks:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_dm1u1ovnnbnJLnoE6-_afuQBoVI4L8bmlR51cZgV_m1GygZDqwEjmafWCDiD7kv6UCEdvqvd2LohoitGAqbCQFWzVYLUydCtvk9q_jC4VokM8IemQykrfFUZyp81IAX8BLrkUKkdmcY/s1600/diagram-fd1165fbe2aca4400e46904ac29f269e42d8da50.png

Note that the top line in this diagram is green, meaning that the first branch commit doesn't conflict with any of the commits on master:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEggWXPtiga7NwSjwjvx0kIJTxpwgWMG2aw5k7c1HshAnLnPAsluUyWIOa8z0EpPAvOS7xMm1_LPNwjF7QwrFE5vbLny90PhKu8kWQ_eiLa0mz37QbnjgIOUgYwK28QSUXXSpqNzIpk2c9E/s1600/diagram-b6508be06fde5b869f6119f883bb7d838425d4fe.png

A larger merge with two early conflict blocks:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgvGZe0U1b_pbvLyfS1ewJoj_vfaEwfDuWbmwnJKUt3NAV2TMIdzahZGAHaDou9edllwMtoHjkLxGIm32ESWEMoGiBhQFuACBx_r7Z-7XMyomLNXd0gq0Jcug_RPQ_47gHoayMH1_IcS0/s1600/diagram-04d07c8da4eec76f1d4c32cd438ddfbf9e2ccb3d.png

The biggest merge of all (281 commits on master, 235 commits on branch).  Please note that even though the branch and master have diverged significantly, conflicts did not arise until quite some time after the branch was created:

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg7WtlSrOU8vWlNKOBc8_lEs74QBu6StpDeryMqazS70Lx29SNww6JEa2Zfeqpd0MXe2T4INEdIAV3InstY81oUkkBJYJDvPXbBbyLZIdPY8aDcKoCrKy2r3PB1HitRqxZFiScYhSRFzis/s1600/diagram-698240f65bd4eb19f122ac2a725818b965445155.png

Conclusion

A merge diagram provides a quick, intuitive overview of a conflicting merge, and highlights the individual commits on each branch that conflict with each other.

Most merge diagrams are simple (in fact I didn't observe any with more than two blocking pairwise merges).  Thus there is hope that, by focusing our attention on these critical pairwise merges, we can resolve a nightmare merge with an acceptable level of pain and (more importantly) some confidence in the result.

In upcoming articles I will explore how to use incremental merging to resolve a nightmare merge.

Notes:
[1]

Putting this all together, we have

for s in $(git rev-list --grep='Conflicts:' --merges master)
do
    git-mergemate diagram $s^1...$s^2 | pnmtopng >../diagram-$s.png
done

If you want to try this with your own git repository, please make a backup first, as the script is only lightly tested!

No comments: