Documentation/diff-options: explain different diff algorithms
PATCH 1/1 Documentation/diff-options: explain different diff algorithms
As a user I wondered what the diff algorithms are about. Offer at least a basic explanation on the differences of the diff algorithms.
--- Documentation/diff-options.txt | 32 +++++++++++++++++++++++++------- 1 file changed, 25 insertions(+), 7 deletions(-)
Documentation/diff-options.txt +25 -7
@@ -94,16 +94,34 @@ diff" algorithm internally. Choose a diff algorithm. The variants are as follows: + -- -`default`, `myers`;; - The basic greedy diff algorithm. Currently, this is the default. `minimal`;; - Spend extra time to make sure the smallest possible diff is - produced. + A diff as produced by the basic greedy algorithm described in + link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations] +`default`, `myers`;; + The same algorithm as `minimal`, extended with a heuristic to + reduce extensive searches. Currently, this is the default. `patience`;; - Use "patience diff" algorithm when generating patches. + Use "patience diff" algorithm when generating patches. This + matches the longest common subsequence of unique lines on + both sides, recursively. It obtained its name by the way the + longest subsequence is found, as that is a byproduct of the + patience sorting algorithm. If there are no unique lines left + it falls back to `myers`. Empirically this algorithm produces + a more readable output for code, but it does not garantuee + the shortest output. `histogram`;; - This algorithm extends the patience algorithm to "support - low-occurrence common elements". + This algorithm re-implements the `patience` algorithm with + "support of low-occurrence common elements" and only picks + one element of the LCS for the recursion. It is often the + fastest, but in cornercases (when there are many longest + common subsequences of the same length) it produces bad + results as seen in: + + seq 1 100 >one + echo 99 > two + seq 1 2 98 >>two + git diff --no-index --histogram one two + -- + For instance, if you configured diff.algorithm variable to a
Signature · 1 line
2.18.0.345.g5c9ce644c3-goog
Hi,
Quoted 2 lines · Stefan Beller
As a user I wondered what the diff algorithms are about. Offer at least a basic explanation on the differences of the diff algorithms.
Interesting. Let's see.
[...]
Documentation/diff-options.txt diff" algorithm internally. · line 98
Quoted 10 lines
Documentation/diff-options.txt +1
-2@@ -94,16 +94,34 @@ diff" algorithm internally. Choose a diff algorithm. The variants are as follows: + -- -`default`, `myers`;; - The basic greedy diff algorithm. Currently, this is the default. `minimal`;; + A diff as produced by the basic greedy algorithm described in
Why this reordering?
Documentation/diff-options.txt diff" algorithm internally. · line 99
Quoted 1 line
Documentation/diff-options.txt +1
-0+ link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations]
This URL doesn't seem likely to stay stable. Are appearances deceiving? (Maybe so, since that's the same host as libxdiff's homepage <http://www.xmailserver.org/xdiff-lib.html>.) It might be worth mentioning the author and date just in case.
Documentation/diff-options.txt diff" algorithm internally. · line 102
Quoted 5 lines
Documentation/diff-options.txt +3
-2- Spend extra time to make sure the smallest possible diff is - produced. +`default`, `myers`;; + The same algorithm as `minimal`, extended with a heuristic to + reduce extensive searches. Currently, this is the default.
Amusing --- this means that the Myers diff is spelled as "minimal" instead of "myers".
Documentation/diff-options.txt diff" algorithm internally. · line 111
Quoted 10 lines
Documentation/diff-options.txt +8
-1`patience`;; - Use "patience diff" algorithm when generating patches. + Use "patience diff" algorithm when generating patches. This + matches the longest common subsequence of unique lines on + both sides, recursively. It obtained its name by the way the + longest subsequence is found, as that is a byproduct of the + patience sorting algorithm. If there are no unique lines left + it falls back to `myers`. Empirically this algorithm produces + a more readable output for code, but it does not garantuee + the shortest output.
Probably also worth mentioning that this was invented by Bram Cohen for the bazaar vcs.
Documentation/diff-options.txt diff" algorithm internally. · line 113
Quoted 4 lines
Documentation/diff-options.txt +1
-2`histogram`;; - This algorithm extends the patience algorithm to "support - low-occurrence common elements". + This algorithm re-implements the `patience` algorithm with
What does reimplements mean here? Do you mean that it is a variation on patience?
Documentation/diff-options.txt diff" algorithm internally. · line 115
Quoted 2 lines
Documentation/diff-options.txt +2
-0+ "support of low-occurrence common elements" and only picks + one element of the LCS for the recursion. It is often the
Does LCS mean longest common subsequence or longest common substring here? Probably best to spell it out to avoid confusion.
Documentation/diff-options.txt diff" algorithm internally. · line 116
Quoted 1 line
Documentation/diff-options.txt +1
-0+ fastest, but in cornercases (when there are many longest
s/cornercases/corner cases/
Documentation/diff-options.txt diff" algorithm internally. · line 123
Quoted 7 lines
Documentation/diff-options.txt +7
-0+ common subsequences of the same length) it produces bad + results as seen in: + + seq 1 100 >one + echo 99 > two + seq 1 2 98 >>two + git diff --no-index --histogram one two
I wonder if these details (about all the algorithms) should go in a separate Diff Algorithms section and this section could focus on what use cases warrant using each, referring to that section for details. What do you think?
Thanks and hope that helps,
Jonathan
Quoted 11 lines · Jonathan Nieder
Hi,
Quoted 2 lines · Stefan Beller
As a user I wondered what the diff algorithms are about. Offer at least a basic explanation on the differences of the diff algorithms.
Interesting. Let's see.
[...]
Quoted 12 lines
Documentation/diff-options.txt diff" algorithm internally. · line 98
Quoted 10 lines
Documentation/diff-options.txt +1
-2@@ -94,16 +94,34 @@ diff" algorithm internally. Choose a diff algorithm. The variants are as follows: + -- -`default`, `myers`;; - The basic greedy diff algorithm. Currently, this is the default. `minimal`;; + A diff as produced by the basic greedy algorithm described inWhy this reordering?
because Myers (below) is constructed from minimal + heuristic. Before this patch we say Myers is myers and minimal "spends extra cycles", which is true if you read the code, as it just is
for (...) {
test_path
if (need_min)
continue;
if (heuristic_good_enough())
break;
}https://github.com/git/git/blob/master/xdiff/xdiffi.c#L152
So the "minimal" algorithm is the basic myers algorithm, and the "myers" algorithm is the extended version (extended with a heuristic to be fast in corner cases, still producing good enough diffs).
Quoted 7 lines
Documentation/diff-options.txt diff" algorithm internally. · line 99
Quoted 2 lines
Documentation/diff-options.txt +1
-0+ link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations]This URL doesn't seem likely to stay stable. Are appearances deceiving? (Maybe so, since that's the same host as libxdiff's homepage <http://www.xmailserver.org/xdiff-lib.html>.) It might be worth mentioning the author and date just in case.
I though about it and did not mention it, as the name "An O(ND) Difference Algorithm and its Variations" is already enough to find that paper quickly.
Quoted 20 lines
Documentation/diff-options.txt diff" algorithm internally. · line 102
Quoted 5 lines
Documentation/diff-options.txt +3
-2- Spend extra time to make sure the smallest possible diff is - produced. +`default`, `myers`;; + The same algorithm as `minimal`, extended with a heuristic to + reduce extensive searches. Currently, this is the default.Amusing --- this means that the Myers diff is spelled as "minimal" instead of "myers".
Documentation/diff-options.txt diff" algorithm internally. · line 111
Quoted 10 lines
Documentation/diff-options.txt +8
-1`patience`;; - Use "patience diff" algorithm when generating patches. + Use "patience diff" algorithm when generating patches. This + matches the longest common subsequence of unique lines on + both sides, recursively. It obtained its name by the way the + longest subsequence is found, as that is a byproduct of the + patience sorting algorithm. If there are no unique lines left + it falls back to `myers`. Empirically this algorithm produces + a more readable output for code, but it does not garantuee + the shortest output.
Quoted 2 lines
Probably also worth mentioning that this was invented by Bram Cohen for the bazaar vcs.
I tried to balance the part that reads like a history lesson and the immediately useful part (why is this better, when should I use it?)
Mentioning bazaar probably makes sense. Not sure about the author, but I'll include him in a reroll of this patch.
Quoted 7 lines
Documentation/diff-options.txt diff" algorithm internally. · line 113
Quoted 4 lines
Documentation/diff-options.txt +1
-2`histogram`;; - This algorithm extends the patience algorithm to "support - low-occurrence common elements". + This algorithm re-implements the `patience` algorithm withWhat does reimplements mean here? Do you mean that it is a variation on patience?
It is supposed to be a variation of patience, but as it comes with its own implementation which I would not fully trust (as it was ported from JGit, and reading the comments over there, a misunderstanding of LCS made it possible to have only one midpoint before recursing)
So it is not just taking the patience algorithm and adding support for "low-occurrence common elements" (what does that even mean? patience already distinguishes uniques and non-uniques), but its own implementation, hence it is not bug-for-bug compatible.
Quoted 5 lines
Documentation/diff-options.txt diff" algorithm internally. · line 115
Quoted 2 lines
Documentation/diff-options.txt +2
-0+ "support of low-occurrence common elements" and only picks + one element of the LCS for the recursion. It is often theDoes LCS mean longest common subsequence or longest common substring here? Probably best to spell it out to avoid confusion.
When writing the patch I meant to refer to longest common subsequence from above, but by picking just one element, this algorithm understands it as longest common string.
Quoted 13 lines
Documentation/diff-options.txt diff" algorithm internally. · line 116
Quoted 2 lines
Documentation/diff-options.txt +1
-0+ fastest, but in cornercases (when there are many longests/cornercases/corner cases/
Documentation/diff-options.txt diff" algorithm internally. · line 123
Quoted 7 lines
Documentation/diff-options.txt +7
-0+ common subsequences of the same length) it produces bad + results as seen in: + + seq 1 100 >one + echo 99 > two + seq 1 2 98 >>two + git diff --no-index --histogram one two
Quoted 4 lines
I wonder if these details (about all the algorithms) should go in a separate Diff Algorithms section and this section could focus on what use cases warrant using each, referring to that section for details. What do you think?
Yeah I thought about putting together a Documentation/technical/diffs.txt that talk about all kinds of diffing (basic diff algorithms, options, how to diff trees), but considered rolling this as a band aid until that document fully materializes.
Thanks,
Stefan
Quoted 25 lines · Stefan Beller
Quoted 11 lines · Jonathan Nieder
Hi,
Quoted 2 lines · Stefan Beller
As a user I wondered what the diff algorithms are about. Offer at least a basic explanation on the differences of the diff algorithms.
Interesting. Let's see.
[...]
Quoted 12 lines
Documentation/diff-options.txt diff" algorithm internally. · line 98
Quoted 10 lines
Documentation/diff-options.txt +1
-2@@ -94,16 +94,34 @@ diff" algorithm internally. Choose a diff algorithm. The variants are as follows: + -- -`default`, `myers`;; - The basic greedy diff algorithm. Currently, this is the default. `minimal`;; + A diff as produced by the basic greedy algorithm described inWhy this reordering?
Quoted 6 lines
because Myers (below) is constructed from minimal + heuristic.
...
So the "minimal" algorithm is the basic myers algorithm, and the "myers" algorithm is the extended version (extended with a heuristic to be fast in corner cases, still producing good enough diffs).
I am not sure that is a good reason for the target readers of this document to move the default from the beginning to somewhere in the middle. For a textbook that explains different algorithms and gives overview of how they work, that order may be appropriate, though.
Quoted 8 lines
Quoted 8 lines
Documentation/diff-options.txt diff" algorithm internally. · line 102
Quoted 5 lines
Documentation/diff-options.txt +3
-2- Spend extra time to make sure the smallest possible diff is - produced. +`default`, `myers`;; + The same algorithm as `minimal`, extended with a heuristic to + reduce extensive searches. Currently, this is the default.Amusing --- this means that the Myers diff is spelled as "minimal" instead of "myers".
Yeah, I had the same thought---for an end-user documentation update, this change and the reordering does not feel like an improvement.
Quoted 4 lines
Quoted 4 lines
I wonder if these details (about all the algorithms) should go in a separate Diff Algorithms section and this section could focus on what use cases warrant using each, referring to that section for details. What do you think?
Good suggestion.
PATCH 1/1 Documentation/diff-options: explain different diff algorithms
In reply to Jonathan NiederAs a user I wondered what the diff algorithms are about. Offer at least a basic explanation on the differences of the diff algorithms.
--- Documentation/diff-options.txt | 10 +++++++--- Documentation/git-diff.txt | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 41 insertions(+), 3 deletions(-)
Documentation/diff-options.txt +7 -3
@@ -91,14 +91,18 @@ appearing as a deletion or addition in the output. It uses the "patience diff" algorithm internally. --diff-algorithm={patience|minimal|histogram|myers}:: - Choose a diff algorithm. The variants are as follows: + Choose a diff algorithm. See the discussion of DIFF ALGORITHMS +ifndef::git-diff[] + in linkgit:git-diff[1] +endif::git-diff[] + . The variants are as follows: + -- `default`, `myers`;; The basic greedy diff algorithm. Currently, this is the default. `minimal`;; - Spend extra time to make sure the smallest possible diff is - produced. + The same algorithm as `myers`, but spend extra time to make + sure the smallest possible diff is produced. `patience`;; Use "patience diff" algorithm when generating patches. `histogram`;;
Documentation/git-diff.txt +34 -0
@@ -119,6 +119,40 @@ include::diff-options.txt[] include::diff-format.txt[] +DIFF ALGORITHMS +--------------- +`Myers` + +A diff as produced by the basic greedy algorithm described in +link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations]. +with a run time of O(M + N + D^2). It employs a heuristic to allow for +a faster diff at the small cost of diff size. +The `minimal` algorithm has that heuristic turned off. + +`Patience` + +This algorithm by Bram Cohen matches the longest common subsequence +of unique lines on both sides, recursively. It obtained its name by +the way the longest subsequence is found, as that is a byproduct of +the patience sorting algorithm. If there are no unique lines left +it falls back to `myers`. Empirically this algorithm produces +a more readable output for code, but it does not garantuee +the shortest output. + +`Histogram` + +This algorithm finds the longest common substring and recursively +diffs the content before and after the longest common substring. +If there are no common substrings left, fallback to `myers`. +This is often the fastest, but in corner cases (when there are +many common substrings of the same length) it produces bad +results as seen in: + + seq 1 100 >one + echo 99 > two + seq 1 2 98 >>two + git diff --no-index --histogram one two + EXAMPLES --------
Signature · 1 line
2.18.0.597.ga71716f1ad-goog
Hi,
Documentation/diff-options.txt appearing as a deletion or addition in the output. It uses the "patience · line 98
Quoted 12 lines · Stefan Beller
Documentation/diff-options.txt +5
-1@@ -91,14 +91,18 @@ appearing as a deletion or addition in the output. It uses the "patience diff" algorithm internally. --diff-algorithm={patience|minimal|histogram|myers}:: - Choose a diff algorithm. The variants are as follows: + Choose a diff algorithm. See the discussion of DIFF ALGORITHMS +ifndef::git-diff[] + in linkgit:git-diff[1] +endif::git-diff[] + . The variants are as follows:
This means outside of git-diff(1), I'd see
See the discussion of DIFF ALGORITHMS in git-diff(1) .
And in git-diff(1), I'd see
See the discussion of DIFF ALGORITHMS .
Both don't seem quite right, since they have an extra space before the period. The git-diff(1) seems especially not quite right --- does it intend to say something like "See the DIFF ALGORITHMS section for more discussion"?
[...]
Documentation/git-diff.txt include::diff-options.txt[] · line 123
Quoted 8 lines
Documentation/git-diff.txt +2
-0@@ -119,6 +119,40 @@ include::diff-options.txt[] include::diff-format.txt[] +DIFF ALGORITHMS +---------------
Please add some introductory words about what the headings refer to.
Quoted 6 lines
Documentation/git-diff.txt +6
-0+`Myers` + +A diff as produced by the basic greedy algorithm described in +link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations]. +with a run time of O(M + N + D^2). It employs a heuristic to allow for +a faster diff at the small cost of diff size.
Documentation/git-diff.txt include::diff-options.txt[] · line 139
Quoted 10 lines
Documentation/git-diff.txt +10
-0+The `minimal` algorithm has that heuristic turned off. + +`Patience` + +This algorithm by Bram Cohen matches the longest common subsequence +of unique lines on both sides, recursively. It obtained its name by +the way the longest subsequence is found, as that is a byproduct of +the patience sorting algorithm. If there are no unique lines left +it falls back to `myers`. Empirically this algorithm produces +a more readable output for code, but it does not garantuee
nit: s/garantuee/guarantee/
Documentation/git-diff.txt include::diff-options.txt[] · line 140
Quoted 1 line
Documentation/git-diff.txt +1
-0+the shortest output.
Trivia: the minimal variant of Myers doesn't guarantee shortest output, either: what it minimizes is the number of lines marked as added or removed. If you want to minimize context lines too, then that would be a new variant. ;-)
[...]
Documentation/git-diff.txt include::diff-options.txt[] · line 145
Quoted 4 lines
Documentation/git-diff.txt +4
-0+`Histogram` + +This algorithm finds the longest common substring and recursively +diffs the content before and after the longest common substring.
optional: may be worth a short aside in the text about the distinction between LCS and LCS. ;-)
It would be especially useful here, since the alphabet used in these strings is *lines* instead of characters, so the first-time reader could probably use some help in building their intuition.
Documentation/git-diff.txt include::diff-options.txt[] · line 146
Quoted 1 line
Documentation/git-diff.txt +1
-0+If there are no common substrings left, fallback to `myers`.
nit: fallback is the noun, fall back is the verb.
Documentation/git-diff.txt include::diff-options.txt[] · line 148
Quoted 2 lines
Documentation/git-diff.txt +2
-0+This is often the fastest, but in corner cases (when there are +many common substrings of the same length) it produces bad
Can you clarify what "bad" means? E.g. would "unexpected", or "poorly aligned", match what you mean?
Documentation/git-diff.txt include::diff-options.txt[] · line 157
Quoted 9 lines
Documentation/git-diff.txt +7
-0+results as seen in: + + seq 1 100 >one + echo 99 > two + seq 1 2 98 >>two + git diff --no-index --histogram one two + EXAMPLES --------
Thanks,
Jonathan
Quoted 4 lines · Jonathan Nieder
Both don't seem quite right, since they have an extra space before the period. The git-diff(1) seems especially not quite right --- does it intend to say something like "See the DIFF ALGORITHMS section for more discussion"?
Good suggestion and doing so would nicely allow side-stepping the space before the dot issue, i.e. "See the DIFF ALGO section (in
git-diff(1)) for more discussion". I like it.
Quoted 23 lines
[...]
Documentation/git-diff.txt include::diff-options.txt[] · line 123
Quoted 8 lines
Documentation/git-diff.txt +2
-0@@ -119,6 +119,40 @@ include::diff-options.txt[] include::diff-format.txt[] +DIFF ALGORITHMS +---------------Please add some introductory words about what the headings refer to.
Quoted 10 lines
Documentation/git-diff.txt +10
-0+`Myers` + +A diff as produced by the basic greedy algorithm described in +link:http://www.xmailserver.org/diff2.pdf[An O(ND) Difference Algorithm and its Variations]. +... + +`Patience` + +This algorithm by Bram Cohen matches the longest common subsequence +...[...]
Quoted 4 lines
Documentation/git-diff.txt include::diff-options.txt[] · line 145
Quoted 4 lines
+
HistogramDocumentation/git-diff.txt +3
-0+ +This algorithm finds the longest common substring and recursively +diffs the content before and after the longest common substring.
As a first-time reader, I felt that it is a bit uneven that there is no attribution for only this item, unlike the description for Myers and Patience.
Quoted 11 lines · Junio C Hamano
Quoted 4 lines · Jonathan Nieder
Both don't seem quite right, since they have an extra space before the period. The git-diff(1) seems especially not quite right --- does it intend to say something like "See the DIFF ALGORITHMS section for more discussion"?
Good suggestion and doing so would nicely allow side-stepping the space before the dot issue, i.e. "See the DIFF ALGO section (in
git-diff(1)) for more discussion". I like it.
Me, too.
Quoted 8 lines
Quoted 4 lines
Documentation/git-diff.txt include::diff-options.txt[] · line 145
Quoted 4 lines
+
HistogramDocumentation/git-diff.txt +3
-0+ +This algorithm finds the longest common substring and recursively +diffs the content before and after the longest common substring.As a first-time reader, I felt that it is a bit uneven that there is no attribution for only this item, unlike the description for Myers and Patience.
Yeah. That is because I spent too much time thinking how this algo is flawed (in its design as the comments in the initial commit in JGit indicate that design error when reading closely) when I was trying to understand it deeply.
Maybe I should emphasize the trade off for performance gain more as Shawn really cared about performance. After all it offers the best performance in *many* common cases, but has a "long tail" of really unfortunate results, too.
PATCH 1/1 Documentation/diff-options: explain different diff algorithms
As a user I wondered what the diff algorithms are about. Offer at least a basic explanation on the differences of the diff algorithms.
---
Not sure if this is finished, I just want to put out the state that I have sitting on my disk.
Documentation/diff-options.txt | 10 +++-- Documentation/git-diff.txt | 72 ++++++++++++++++++++++++++++++++++ 2 files changed, 79 insertions(+), 3 deletions(-)
Documentation/diff-options.txt +7 -3
@@ -91,14 +91,18 @@ appearing as a deletion or addition in the output. It uses the "patience diff" algorithm internally. --diff-algorithm={patience|minimal|histogram|myers}:: - Choose a diff algorithm. The variants are as follows: + Choose a diff algorithm. See the DIFF ALGORITHMS section +ifndef::git-diff[] + in linkgit:git-diff[1] +endif::git-diff[] + for more discussion. The variants are as follows: + -- `default`, `myers`;; The basic greedy diff algorithm. Currently, this is the default. `minimal`;; - Spend extra time to make sure the smallest possible diff is - produced. + The same algorithm as `myers`, but spend extra time to make + sure the smallest possible diff is produced. `patience`;; Use "patience diff" algorithm when generating patches. `histogram`;;
Documentation/git-diff.txt +72 -0
78 lines not on this page · raw message
Signature · 1 line
2.18.0.865.gffc8e1a3cd6-goog
Quoted 4 lines · Jonathan Nieder
Quoted 2 lines
+DIFF ALGORITHMS
+---------------Please add some introductory words about what the headings refer to.
ok.
Quoted 7 lines
Quoted 2 lines
+the shortest output.
Trivia: the
minimalvariant of Myers doesn't guarantee shortest output, either: what it minimizes is the number of lines marked as added or removed. If you want to minimize context lines too, then that would be a new variant. ;-)
... and take line length into account. ;-)
It minimizes the edit distance in terms of lines, i.e. in a context-less diff we get the lowest number of lines possible.
Quoted 9 lines
Documentation/git-diff.txt include::diff-options.txt[] · line 145
Quoted 2 lines
Documentation/git-diff.txt +2
-0+This algorithm finds the longest common substring and recursively +diffs the content before and after the longest common substring.optional: may be worth a short aside in the text about the distinction between LCS and LCS. ;-)
It would be especially useful here, since the alphabet used in these strings is *lines* instead of characters, so the first-time reader could probably use some help in building their intuition.
That makes sense.
Quoted 6 lines
Documentation/git-diff.txt include::diff-options.txt[] · line 148
Quoted 3 lines
Documentation/git-diff.txt +2
-0+This is often the fastest, but in corner cases (when there are +many common substrings of the same length) it produces badCan you clarify what "bad" means? E.g. would "unexpected", or "poorly aligned", match what you mean?
I'll just go with unexpected.
Quoted 6 lines
Quoted 6 lines
Documentation/git-diff.txt +6
-0+results as seen in: + + seq 1 100 >one + echo 99 > two + seq 1 2 98 >>two + git diff --no-index --histogram one two
cover Getting data on different diff algorithms WAS: Documentation/diff-options: explain different diff algorithms
In reply to Stefan BellerI instrumented range-diff to use different diff algorithms for the patches, (I chose default-myers and patience) and then run on the same range, via ./git-range-diff v2.10.0..HEAD v2.10.0..HEAD
and I found 5245 same, 304 slightly different and 4 completely different patches in that range.
Looking at the interdiff is not very pleasing even when reading it with coloring and move detection.
Manually looking at them, I found the patience diff easier to review.
Comparing the 'default' diff algorithm to 'minimal', I'll see
5491 same, 58 slightly different and 0 completely different patches.
Comparing 'default' to 'histogram', I'll see
5255 same, 294 slightly different and 8 completely different patches.
Comparing 'histogram' to 'patience', I'll see
5337 same, 212 slightly different and 10 completely different patches.
This is all to just put data out there, on how much difference to expect from the diff algorithms. I have not yet dug into the quality of the diffs.
Stefan
Stefan Beller (2):
WIP: range-diff: take extra arguments for different diffs. WIP range-diff: print some statistics about the range
range-diff.c | 29 +++++++++++++++++++++++++---- 1 file changed, 25 insertions(+), 4 deletions(-)
Signature · 1 line
2.18.0.597.ga71716f1ad-goog
PATCH 1/2 WIP: range-diff: take extra arguments for different diffs.
We can use the range-diff on the same range to examine differences in the diff algorithm.
--- range-diff.c | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-)
range-diff.c +16 -4
@@ -28,7 +28,8 @@ struct patch_util {* Reads the patches into a string list, with the `util` field being populated * as struct object_id (will need to be free()d). */ -static int read_patches (const char *range,struct string_list *list) +static int read_patches (const char *range,struct string_list *list, +struct argv_array *extra_log_args) {struct child_process cp =CHILD_PROCESS_INIT ;FILE *in;
@@ -36,7 +37,12 @@ static int read_patches(const char *range, struct string_list *list)struct patch_util *util =NULL ;int in_header =1 ; -argv_array_pushl (&cp.args,"log" ,"--no-color" ,"-p" ,"--no-merges" , +argv_array_pushl (&cp.args,"log" ,"--no-color" ,"-p" ,"--no-merges" ,NULL ); + +if (extra_log_args) +argv_array_pushv (&cp.args, extra_log_args->argv); + +argv_array_pushl (&cp.args,"--reverse" ,"--date-order" ,"--decorate=no" ,"--no-abbrev-commit" , range,NULL );
@@ -419,14 +425,20 @@ int show_range_diff(const char *range1, const char *range2, {int res =0 ; +struct argv_array extra =ARGV_ARRAY_INIT ; +struct string_list branch1 =STRING_LIST_INIT_DUP ;struct string_list branch2 =STRING_LIST_INIT_DUP ; -if (read_patches (range1, &branch1)) +argv_array_push (&extra,"--diff-algorithm=patience" ); +argv_array_push (&extra,"--indent-heuristic" ); + +if (read_patches (range1, &branch1,NULL )) res =error (_ ("could not parse log for '%s'" ), range1); -if (!res &&read_patches (range2, &branch2)) +if (!res &&read_patches (range2, &branch2, &extra)) res =error (_ ("could not parse log for '%s'" ), range2); + diffopt->color_moved =COLOR_MOVED_DEFAULT ;if (!res) {find_exact_matches (&branch1, &branch2);get_correspondences (&branch1, &branch2, creation_factor);
Signature · 1 line
2.18.0.597.ga71716f1ad-goog
PATCH 2/2 WIP range-diff: print some statistics about the range
In reply to Stefan Beller--- range-diff.c | 9 +++++++++ 1 file changed, 9 insertions(+)
range-diff.c +9 -0
@@ -264,6 +264,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b,free (b2a); } +int completely_different, slightly_different, same; + static void output_pair_header(struct diff_options *diffopt, int patch_no_width, struct strbuf *buf,
@@ -288,15 +290,19 @@ static void output_pair_header(struct diff_options *diffopt,if (!b_util) { color = color_old; status ='<' ; + slightly_different++; }else if (!a_util) { color = color_new; status ='>' ; + completely_different++; }else if (strcmp (a_util->patch, b_util->patch)) { color = color_commit; status ='!' ; + slightly_different++; }else { color = color_commit; status ='=' ; + same++; }strbuf_reset (buf);
@@ -439,12 +445,15 @@ int show_range_diff(const char *range1, const char *range2, res =error (_ ("could not parse log for '%s'" ), range2); diffopt->color_moved =COLOR_MOVED_DEFAULT ; +if (!res) {find_exact_matches (&branch1, &branch2);get_correspondences (&branch1, &branch2, creation_factor);output (&branch1, &branch2, diffopt); } +printf ("patch ranges are %d same, %d slightly different and %d completely different\n" , same, slightly_different, completely_different); +string_list_clear (&branch1,1 );string_list_clear (&branch2,1 );
Signature · 1 line
2.18.0.597.ga71716f1ad-goog