about summary refs log tree commit diff
path: root/third_party/git/Documentation/technical/rerere.txt
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/git/Documentation/technical/rerere.txt')
-rw-r--r--third_party/git/Documentation/technical/rerere.txt186
1 files changed, 0 insertions, 186 deletions
diff --git a/third_party/git/Documentation/technical/rerere.txt b/third_party/git/Documentation/technical/rerere.txt
deleted file mode 100644
index af5f9fc24f93..000000000000
--- a/third_party/git/Documentation/technical/rerere.txt
+++ /dev/null
@@ -1,186 +0,0 @@
-Rerere
-======
-
-This document describes the rerere logic.
-
-Conflict normalization
-----------------------
-
-To ensure recorded conflict resolutions can be looked up in the rerere
-database, even when branches are merged in a different order,
-different branches are merged that result in the same conflict, or
-when different conflict style settings are used, rerere normalizes the
-conflicts before writing them to the rerere database.
-
-Different conflict styles and branch names are normalized by stripping
-the labels from the conflict markers, and removing the common ancestor
-version from the `diff3` conflict style. Branches that are merged
-in different order are normalized by sorting the conflict hunks.  More
-on each of those steps in the following sections.
-
-Once these two normalization operations are applied, a conflict ID is
-calculated based on the normalized conflict, which is later used by
-rerere to look up the conflict in the rerere database.
-
-Removing the common ancestor version
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-
-Say we have three branches AB, AC and AC2.  The common ancestor of
-these branches has a file with a line containing the string "A" (for
-brevity this is called "line A" in the rest of the document).  In
-branch AB this line is changed to "B", in AC, this line is changed to
-"C", and branch AC2 is forked off of AC, after the line was changed to
-"C".
-
-Forking a branch ABAC off of branch AB and then merging AC into it, we
-get a conflict like the following:
-
-    <<<<<<< HEAD
-    B
-    =======
-    C
-    >>>>>>> AC
-
-Doing the analogous with AC2 (forking a branch ABAC2 off of branch AB
-and then merging branch AC2 into it), using the diff3 conflict style,
-we get a conflict like the following:
-
-    <<<<<<< HEAD
-    B
-    ||||||| merged common ancestors
-    A
-    =======
-    C
-    >>>>>>> AC2
-
-By resolving this conflict, to leave line D, the user declares:
-
-    After examining what branches AB and AC did, I believe that making
-    line A into line D is the best thing to do that is compatible with
-    what AB and AC wanted to do.
-
-As branch AC2 refers to the same commit as AC, the above implies that
-this is also compatible what AB and AC2 wanted to do.
-
-By extension, this means that rerere should recognize that the above
-conflicts are the same.  To do this, the labels on the conflict
-markers are stripped, and the common ancestor version is removed.  The above
-examples would both result in the following normalized conflict:
-
-    <<<<<<<
-    B
-    =======
-    C
-    >>>>>>>
-
-Sorting hunks
-~~~~~~~~~~~~~
-
-As before, lets imagine that a common ancestor had a file with line A
-its early part, and line X in its late part.  And then four branches
-are forked that do these things:
-
-    - AB: changes A to B
-    - AC: changes A to C
-    - XY: changes X to Y
-    - XZ: changes X to Z
-
-Now, forking a branch ABAC off of branch AB and then merging AC into
-it, and forking a branch ACAB off of branch AC and then merging AB
-into it, would yield the conflict in a different order.  The former
-would say "A became B or C, what now?" while the latter would say "A
-became C or B, what now?"
-
-As a reminder, the act of merging AC into ABAC and resolving the
-conflict to leave line D means that the user declares:
-
-    After examining what branches AB and AC did, I believe that
-    making line A into line D is the best thing to do that is
-    compatible with what AB and AC wanted to do.
-
-So the conflict we would see when merging AB into ACAB should be
-resolved the same way---it is the resolution that is in line with that
-declaration.
-
-Imagine that similarly previously a branch XYXZ was forked from XY,
-and XZ was merged into it, and resolved "X became Y or Z" into "X
-became W".
-
-Now, if a branch ABXY was forked from AB and then merged XY, then ABXY
-would have line B in its early part and line Y in its later part.
-Such a merge would be quite clean.  We can construct 4 combinations
-using these four branches ((AB, AC) x (XY, XZ)).
-
-Merging ABXY and ACXZ would make "an early A became B or C, a late X
-became Y or Z" conflict, while merging ACXY and ABXZ would make "an
-early A became C or B, a late X became Y or Z".  We can see there are
-4 combinations of ("B or C", "C or B") x ("X or Y", "Y or X").
-
-By sorting, the conflict is given its canonical name, namely, "an
-early part became B or C, a late part became X or Y", and whenever
-any of these four patterns appear, and we can get to the same conflict
-and resolution that we saw earlier.
-
-Without the sorting, we'd have to somehow find a previous resolution
-from combinatorial explosion.
-
-Conflict ID calculation
-~~~~~~~~~~~~~~~~~~~~~~~
-
-Once the conflict normalization is done, the conflict ID is calculated
-as the sha1 hash of the conflict hunks appended to each other,
-separated by <NUL> characters.  The conflict markers are stripped out
-before the sha1 is calculated.  So in the example above, where we
-merge branch AC which changes line A to line C, into branch AB, which
-changes line A to line C, the conflict ID would be
-SHA1('B<NUL>C<NUL>').
-
-If there are multiple conflicts in one file, the sha1 is calculated
-the same way with all hunks appended to each other, in the order in
-which they appear in the file, separated by a <NUL> character.
-
-Nested conflicts
-~~~~~~~~~~~~~~~~
-
-Nested conflicts are handled very similarly to "simple" conflicts.
-Similar to simple conflicts, the conflict is first normalized by
-stripping the labels from conflict markers, stripping the common ancestor
-version, and the sorting the conflict hunks, both for the outer and the
-inner conflict.  This is done recursively, so any number of nested
-conflicts can be handled.
-
-Note that this only works for conflict markers that "cleanly nest".  If
-there are any unmatched conflict markers, rerere will fail to handle
-the conflict and record a conflict resolution.
-
-The only difference is in how the conflict ID is calculated.  For the
-inner conflict, the conflict markers themselves are not stripped out
-before calculating the sha1.
-
-Say we have the following conflict for example:
-
-    <<<<<<< HEAD
-    1
-    =======
-    <<<<<<< HEAD
-    3
-    =======
-    2
-    >>>>>>> branch-2
-    >>>>>>> branch-3~
-
-After stripping out the labels of the conflict markers, and sorting
-the hunks, the conflict would look as follows:
-
-    <<<<<<<
-    1
-    =======
-    <<<<<<<
-    2
-    =======
-    3
-    >>>>>>>
-    >>>>>>>
-
-and finally the conflict ID would be calculated as:
-`sha1('1<NUL><<<<<<<\n3\n=======\n2\n>>>>>>><NUL>')`