Add `branch-diff`, a `tbdiff` lookalike

The incredibly useful git-tbdiff [https://github.com/trast/tbdiff] tool to compare patch series (say, to see what changed between two iterations sent to the Git mailing list) is slightly less useful for this developer due to the fact that it requires the hungarian and numpy Python packages which are for some reason really hard to build in MSYS2. So hard that I even had to give up, because it was simply easier to re-implement the whole shebang as a builtin command.

The project at https://github.com/trast/tbdiff seems to be dormant, anyway. Funny (and true) story: I looked at the open Pull Requests to see how active that project is, only to find to my surprise that I had submitted one in August 2015, and that it was still unanswered let alone merged.

While at it, I forward-ported AEvar's patch to force --decorate=no because git -p tbdiff would fail otherwise.

Side note: I work on implementing range-diff not only to make life easier for reviewers who have to suffer through v2, v3, ... of my patch series, but also to verify my changes before submitting a new iteration. And also, maybe even more importantly, I plan to use it to verify my merging-rebases of Git for Windows (for which I previously used to redirect the pre-rebase/post-rebase diffs vs upstream and then compare them using git diff --no-index). And of course any interested person can see what changes were necessary e.g. in the merging-rebase of Git for Windows onto v2.17.0 by running a command like:

        base=^{/Start.the.merging-rebase}
        tag=v2.17.0.windows.1
        pre=$tag$base^2
        git range-diff $pre$base..$pre $tag$base..$tag

The command uses what it calls the "dual color mode" (can be disabled via --no-dual-color) which helps identifying what actually changed: it prefixes lines with a - (and red background) that correspond to the first commit range, and with a + (and green background) that correspond to the second range. The rest of the lines will be colored according to the original diffs.

Changes since v4:

* Fixed a typo in the commit message of "range-diff: add tests" that was introduced in v4.
* White-space fixes.
* Fixed the length of the first header underline in the man page.
* Changed the preprocessor guard in linear-assignment.h to reflect the new name (instead of the old name, which was hungarian.h).
* Likewise, changed the preprocessor guards in range-diff.h to hide the history of the thrice-renamed command.
* Fixed indentation in the completion.
* Instead of trying to paper over white-space error handling that does not apply to "diffs of diffs", dual color mode now simply disables all white-space warnings.
* When showing the "single arg must be symmetric range" error message, git range-diff now also shows the usage.
* Adjusted the commit message of "range-diff: adjust the output of the commit pairs" to avoid the surprise of the reviewer when onelines are printed all of a sudden, too.
* "range-diff: adjust the output of the commit pairs" is now using a simpler way to print onelines.
* We are now sandwiching the diff_opt_parse() loop between two parse_options(), to make sure that we caught all options, and that the -- separator is handled.
* Adjusted the lookup_commit_reference() call to the newest master (it now takes a the_repository parameter).

Changes since v3:

* The cover letter was adjusted to reflect the new reality (the command is called range-diff now, not branch-diff, and --dual-color is the default).
* The documentation was adjusted a bit more in the patch that makes --dual-color the default.
* Clarified the calculation of the cost matrix, as per Stefan Beller's request.
* The man page now spells out that merge commits are ignored in the commit ranges (not merges per se).
* The code in linear-assignment.c was adjusted to use the SWAP() macro.
* The commit message of the patch introducing the first rudimentary implementation no longer talks about the "Hungarian" algorithm, but about the "linear assignment algorithm" instead.
* A bogus indentation change was backed out from the patch introducing the first rudimentary implementation.
* Instead of merely warning about missing .. in the 2-parameter invocation, we now exit with the error message.
* The diff_opt_parse() function is allowed to return a value larger than 1, indicating that more than just one command-line parameter was parsed. We now advance by the indicated value instead of always advancing exactly 1 (which is still correct much of the time).
* A lengthy if...else if...else if...else was simplified (from a logical point of view) by reordering it.
* The unnecessarily static variable dashes was turned into a local variable of the caller.
* The commit message talking about the new man page still referred to git branch --diff, which has been fixed.
* A forgotten t7910 reference was changed to t3206.
* An unbalanced double-tick was fixed in the man page.
* Fixed grammar both of the commit message and the description of the --no-dual-color option.
* To fix the build, a blank man page is now introduced together with the new range-diff command, even if it is populated for real only at a later patch (i.e. at the same time as before).
* The headaches Junio fears would be incurred by that simple workaround to avoid bogus white-space error reporting are fended off: a more complex patch is now in place that adds (and uses) a new white-space flag. Sadly, as is all too common when Junio "encourages" me to replace a simple workaround by something "proper", it caused all kinds of headaches to get this right, so I am rather less certain that the "proper" fix will cause us less headaches than the simple workaround would have done. But whatever.
* The dual color mode now also dims the changes that are exclusively in the first specified commit range, and uses bold face on the changes exclusively in the second one. This matches the intuition when using range-diff to compare an older iteration of a patch series to a newer
one: the changes from the previous iteration that were replaced by new ones "fade", while the changes that replace them are "shiny new".

Changes since v2:

* Right-aligned the patch numbers in the commit pairs.
* Used ALLOC_ARRAY() in hungarian.c instead of xmalloc(sizeof()*size).
* Changed compute_assignment()s return type from int to void, as it always succeeds.
* Changed the Hungarian Algorithm to use an integer cost matrix.
* Changed the --creation-weight option to --creation-factor where is an integer.
* Retitled 1/19 and 2/19 to better conform with the current conventions, as pointed out (and suggested) by Junio.
* Shut up Coverity, and at the same time avoided passing the unnecessary i and j parameters to output_pair_header().
* Removed support for the --no-patches option: we inherit diff_options' support for -s already (and much more).
* Removed the ugly _INV enum values, and introduced a beautiful GIT_COLOR_REVERSE instead. This way, whatever the user configured as color.diff.new (or .old) will be used in reverse in the dual color mode.
* Instead of overriding the fragment header color, the dual color mode will now reverse the "outer" fragment headers, too.
* Turned the stand-alone branch-diff command into the --diff option of git branch. Adjusted pretty much all commit messages to account for this. This change should no longer be visible: see below.
* Pretty much re-wrote the completion, to support the new --diff mode of git-branch. See below: it was reverted for range-diff.
* Renamed t7910 to t3206, to be closer to the git-branch tests.
* Ensured that git_diff_ui_config() gets called, and therefore color.diff.* respected.
* Avoided leaking four_spaces.
* Fixed a declaration in a for (;;) statement (which Junio had as a fixup! that I almost missed).
* Renamed branch --diff, which had been renamed from branch-diff (which was picked to avoid re-using tbdiff) to range-diff.
* Renamed hungarian.c and its header to linear-assignment.c
* Made --dual-color the default, and changed it to still auto-detect whether color should be used rather than forcing it

Johannes Schindelin (20):
linear-assignment: a function to solve least-cost assignment problems Introduce range-diff to compare iterations of a topic branch
range-diff: first rudimentary implementation
range-diff: improve the order of the shown commits
range-diff: also show the diff between patches
range-diff: right-trim commit messages
range-diff: indent the diffs just like tbdiff
range-diff: suppress the diff headers
range-diff: adjust the output of the commit pairs
range-diff: do not show "function names" in hunk headers
range-diff: use color for the commit pairs
color: add the meta color GIT_COLOR_REVERSE
diff: add an internal option to dual-color diffs of diffs
range-diff: offer to dual-color the diffs
range-diff --dual-color: skip white-space warnings
range-diff: populate the man page
completion: support git range-diff
range-diff: left-pad patch numbers
range-diff: make --dual-color the default mode
range-diff: use dim/bold cues to improve dual color mode

Thomas Rast (1):
range-diff: add tests

 .gitignore                             |   1 +
 Documentation/config.txt               |   6 +-
 Documentation/git-range-diff.txt       | 252 +++++++++++
 Makefile                               |   3 +
 builtin.h                              |   1 +
 builtin/range-diff.c                   | 114 +++++
 color.h                                |   7 +
 command-list.txt                       |   1 +
 contrib/completion/git-completion.bash |  14 +
 diff.c                                 | 105 ++++-
 diff.h                                 |  10 +-
 git.c                                  |   1 +
 linear-assignment.c                    | 201 ++++++++
 linear-assignment.h                    |  22 +
 range-diff.c                           | 435 ++++++++++++++++++
 range-diff.h                           |   9 +
 t/.gitattributes                       |   1 +
 t/t3206-range-diff.sh                  | 145 ++++++
 t/t3206/history.export                 | 604 +++++++++++++++++++++++++
 19 files changed, 1913 insertions(+), 19 deletions(-)
 create mode 100644 Documentation/git-range-diff.txt
 create mode 100644 builtin/range-diff.c
 create mode 100644 linear-assignment.c
 create mode 100644 linear-assignment.h
 create mode 100644 range-diff.c
 create mode 100644 range-diff.h
 create mode 100755 t/t3206-range-diff.sh
 create mode 100644 t/t3206/history.export

base-commit: 1d89318c48d233d52f1db230cf622935ac3c69fa
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-1%2Fdscho%2Fbranch-diff-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1/dscho/branch-diff-v5
Pull-Request: https://github.com/gitgitgadget/git/pull/1

Range-diff vs v4:

1: f7e70689e ! 1: f168da3a3 linear-assignment: a function to solve least-cost assignment problems

     @@ -239,8 +239,8 @@
      --- /dev/null
      +++ b/linear-assignment.h
      @@
     -+#ifndef HUNGARIAN_H
     -+#define HUNGARIAN_H
     ++#ifndef LINEAR_ASSIGNMENT_H
     ++#define LINEAR_ASSIGNMENT_H
      +
      +/*
      + * Compute an assignment of columns -> rows (and vice versa) such that every
  2:  88134121d !  2:  33758f361 Introduce `range-diff` to compare iterations of a topic branch
     @@ -34,7 +34,7 @@
      +++ b/Documentation/git-range-diff.txt
      @@
      +git-range-diff(1)
     -+==================
     ++=================
      +
      +NAME
      +----
  3:  4e3fb47a1 !  3:  08b8c3fc4 range-diff: first rudimentary implementation
     @@ -70,8 +70,10 @@
      +		const char *b = strstr(argv[0], "..."), *a = argv[0];
      +		int a_len;
      +
     -+		if (!b)
     -+			die(_("single arg format requires a symmetric range"));
     ++		if (!b) {
     ++			error(_("single arg format must be symmetric range"));
     ++			usage_with_options(builtin_range_diff_usage, options);
     ++		}
      +
      +		a_len = (int)(b - a);
      +		if (!a_len) {
     @@ -418,8 +420,8 @@
      --- /dev/null
      +++ b/range-diff.h
      @@
     -+#ifndef BRANCH_DIFF_H
     -+#define BRANCH_DIFF_H
     ++#ifndef RANGE_DIFF_H
     ++#define RANGE_DIFF_H
      +
      +int show_range_diff(const char *range1, const char *range2,
      +		    int creation_factor);
  4:  47bee09b0 =  4:  7b9091968 range-diff: improve the order of the shown commits
  5:  94afaeaf2 !  5:  9e1e66007 range-diff: also show the diff between patches
     @@ -10,7 +10,7 @@
          diff which is the result of first reverting the old diff and then
          applying the new diff.
      
     -    Especially when rebasing often, an interdiff is often not feasible,
     +    Especially when rebasing frequently, an interdiff is often not feasible,
          though: if the old diff cannot be applied in reverse (due to a moving
          upstream), an interdiff can simply not be inferred.
      
     @@ -25,9 +25,17 @@
          This is left for a later commit.
      
          Note also: while tbdiff accepts the `--no-patches` option to suppress
     -    these diffs between patches, we prefer the `-s` option that is
     -    automatically supported via our use of diff_opt_parse().
     +    these diffs between patches, we prefer the `-s` (or `--no-patch`) option
     +    that is automatically supported via our use of diff_opt_parse().
      
     +    And finally note: to support diff options, we have to call
     +    `parse_options()` such that it keeps unknown options, and then loop over
     +    those and let `diff_opt_parse()` handle them. After that loop, we have
     +    to call `parse_options()` again, to make sure that no unknown options
     +    are left.
     +
     +    Helped-by: Thomas Gummerer <[email protected]>
     +    Helped-by: Eric Sunshine <[email protected]>
          Signed-off-by: Johannes Schindelin <[email protected]>
      
      diff --git a/builtin/range-diff.c b/builtin/range-diff.c
     @@ -61,10 +69,10 @@
      +	diffopt.output_format = DIFF_FORMAT_PATCH;
      +
       	argc = parse_options(argc, argv, NULL, options,
     --			     builtin_range_diff_usage, 0);
     -+			     builtin_range_diff_usage, PARSE_OPT_KEEP_UNKNOWN);
     ++			     builtin_range_diff_usage, PARSE_OPT_KEEP_UNKNOWN |
     ++			     PARSE_OPT_KEEP_DASHDASH | PARSE_OPT_KEEP_ARGV0);
      +
     -+	for (i = j = 0; i < argc; ) {
     ++	for (i = j = 1; i < argc && strcmp("--", argv[i]); ) {
      +		int c = diff_opt_parse(&diffopt, argv + i, argc - i, prefix);
      +
      +		if (!c)
     @@ -74,9 +82,13 @@
      +	}
      +	argc = j;
      +	diff_setup_done(&diffopt);
     ++
     ++	/* Make sure that there are no unparsed options */
     ++	argc = parse_options(argc, argv, NULL,
     ++			     options + ARRAY_SIZE(options) - 1, /* OPT_END */
     + 			     builtin_range_diff_usage, 0);
       
       	if (argc == 2) {
     - 		if (!strstr(argv[0], ".."))
      @@
       		usage_with_options(builtin_range_diff_usage, options);
       	}
     @@ -165,8 +177,8 @@
      --- a/range-diff.h
      +++ b/range-diff.h
      @@
     - #ifndef BRANCH_DIFF_H
     - #define BRANCH_DIFF_H
     + #ifndef RANGE_DIFF_H
     + #define RANGE_DIFF_H
       
      +#include "diff.h"
      +
  6:  41ab875a3 =  6:  167ca02a3 range-diff: right-trim commit messages
  7:  a3dd99509 !  7:  ca8de8c75 range-diff: indent the diffs just like tbdiff
     @@ -39,7 +39,7 @@
      +	diffopt.output_prefix_data = &four_spaces;
       
       	argc = parse_options(argc, argv, NULL, options,
     - 			     builtin_range_diff_usage, PARSE_OPT_KEEP_UNKNOWN);
     + 			     builtin_range_diff_usage, PARSE_OPT_KEEP_UNKNOWN |
      @@
       
       	strbuf_release(&range1);
  8:  61b2ff2f7 =  8:  eb94d1982 range-diff: suppress the diff headers
  9:  9641ab5c0 !  9:  6330afad9 range-diff: adjust the output of the commit pairs
     @@ -2,6 +2,10 @@
      
          range-diff: adjust the output of the commit pairs
      
     +    This not only uses "dashed stand-ins" for "pairs" where one side is
     +    missing (i.e. unmatched commits that are present only in one of the two
     +    commit ranges), but also adds onelines for the reader's pleasure.
     +
          This change brings `git range-diff` yet another step closer to
          feature parity with tbdiff: it now shows the oneline, too, and indicates
          with `=` when the commits have identical diffs.
     @@ -61,15 +65,10 @@
      +		strbuf_addf(buf, " %d:  %s", b_util->i + 1,
      +			    find_unique_abbrev(&b_util->oid, DEFAULT_ABBREV));
      +
     -+	commit = lookup_commit_reference(oid);
     ++	commit = lookup_commit_reference(the_repository, oid);
      +	if (commit) {
     -+		const char *commit_buffer = get_commit_buffer(commit, NULL);
     -+		const char *subject;
     -+
     -+		find_commit_subject(commit_buffer, &subject);
      +		strbuf_addch(buf, ' ');
     -+		format_subject(buf, subject, " ");
     -+		unuse_commit_buffer(commit, commit_buffer);
     ++		pp_commit_easy(CMIT_FMT_ONELINE, commit, buf);
      +	}
      +	strbuf_addch(buf, '\n');
      +
 10:  0a52f8878 = 10:  c296675eb range-diff: do not show "function names" in hunk headers
 11:  2b8d09020 ! 11:  85e0ab82f range-diff: add tests

@@ -3,7 +3,7 @@
range-diff: add tests

These are essentially lifted from https://github.com/trast/tbdiff, with
- light touch-ups to account for the command now being names `git
+ light touch-ups to account for the command now being named `git
range-diff`.

Apart from renaming tbdiff to range-diff, only one test case needed
12: fb83ce71a ! 12: f48b62644 range-diff: use color for the commit pairs

     @@ -79,16 +79,14 @@
       	if (!b_util)
       		strbuf_addf(buf, " -:  %s", dashes->buf);
      @@
     - 		const char *commit_buffer = get_commit_buffer(commit, NULL);
     - 		const char *subject;
       
     + 	commit = lookup_commit_reference(the_repository, oid);
     + 	if (commit) {
      +		if (status == '!')
      +			strbuf_addf(buf, "%s%s", color_reset, color);
      +
     - 		find_commit_subject(commit_buffer, &subject);
       		strbuf_addch(buf, ' ');
     - 		format_subject(buf, subject, " ");
     - 		unuse_commit_buffer(commit, commit_buffer);
     + 		pp_commit_easy(CMIT_FMT_ONELINE, commit, buf);
       	}
      -	strbuf_addch(buf, '\n');
      +	strbuf_addf(buf, "%s\n", color_reset);
 13:  9ccb9516a = 13:  1ad74f939 color: add the meta color GIT_COLOR_REVERSE
 14:  9de5bd229 = 14:  39a0ecd28 diff: add an internal option to dual-color diffs of diffs
 15:  21b2f9e4b ! 15:  c32a24f6a range-diff: offer to dual-color the diffs
     @@ -30,8 +30,8 @@
       	};
       	int i, j, res = 0;
      @@
     - 	argc = j;
     - 	diff_setup_done(&diffopt);
     + 			     options + ARRAY_SIZE(options) - 1, /* OPT_END */
     + 			     builtin_range_diff_usage, 0);
       
      +	if (dual_color) {
      +		diffopt.use_color = 1;
 16:  f4252f2b2 <  -:  --------- range-diff --dual-color: fix bogus white-space warning
  -:  --------- > 16:  05947781f range-diff --dual-color: skip white-space warnings
 17:  9e09c6be6 = 17:  3147c4440 range-diff: populate the man page
 18:  9b3632324 ! 18:  b08e6d937 completion: support `git range-diff`
     @@ -18,16 +18,16 @@
       
      +_git_range_diff ()
      +{
     -+  case "$cur" in
     -+  --*)
     -+          __gitcomp "
     -+	  	--creation-factor= --dual-color
     -+                  $__git_diff_common_options
     -+                  "
     -+          return
     -+          ;;
     -+  esac
     -+  __git_complete_revlist
     ++	case "$cur" in
     ++	--*)
     ++		__gitcomp "
     ++			--creation-factor= --dual-color
     ++			$__git_diff_common_options
     ++		"
     ++		return
     ++		;;
     ++	esac
     ++	__git_complete_revlist
      +}
      +
       _git_rebase ()
 19:  07ec215e8 ! 19:  19406283e range-diff: left-pad patch numbers
     @@ -48,7 +48,7 @@
      +		strbuf_addf(buf, " %*d:  %s", patch_no_width, b_util->i + 1,
       			    find_unique_abbrev(&b_util->oid, DEFAULT_ABBREV));
       
     - 	commit = lookup_commit_reference(oid);
     + 	commit = lookup_commit_reference(the_repository, oid);
      @@
       		   struct diff_options *diffopt)
       {

20: b370468e7 ! 20: 6b3552386 range-diff: make --dual-color the default mode
@@ -87,8 +87,8 @@
OPT_END()
};
@@
- argc = j;
- diff_setup_done(&diffopt);
+ options + ARRAY_SIZE(options) - 1, /* OPT_END */
+ builtin_range_diff_usage, 0);

- if (dual_color) {
- diffopt.use_color = 1;
@@ -104,11 +104,11 @@
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@
- case "$cur" in
- --*)
- __gitcomp "
-- --creation-factor= --dual-color
-+ --creation-factor= --no-dual-color
- $__git_diff_common_options
- "
- return
+ case "$cur" in
+ --*)
+ __gitcomp "
+- --creation-factor= --dual-color
++ --creation-factor= --no-dual-color
+ $__git_diff_common_options
+ "
+ return
21: d8498fb32 ! 21: ccf8c1bb2 range-diff: use dim/bold cues to improve dual color mode

     @@ -144,7 +144,7 @@
      +				set = diff_get_color_opt(o, DIFF_FILE_NEW_BOLD);
      +			else
      +				set = diff_get_color_opt(o, DIFF_CONTEXT_BOLD);
     - 			flags |= WS_IGNORE_FIRST_SPACE;
     + 			flags &= ~DIFF_SYMBOL_CONTENT_WS_MASK;
       		}
       		emit_line_ws_markup(o, set, reset, line, len, set_sign, '+',
      @@

gitgitgadget

From: Johannes Schindelin <[email protected]>

The problem solved by the code introduced in this commit goes like this:
given two sets of items, and a cost matrix which says how much it "costs" to assign any given item of the first set to any given item of the second, assign all items (except when the sets have different size) in the cheapest way.

We use the Jonker-Volgenant algorithm to solve the assignment problem to answer questions such as: given two different versions of a topic branch (or iterations of a patch series), what is the best pairing of commits/patches between the different versions?

---
 Makefile            |   1 +
 linear-assignment.c | 201 ++++++++++++++++++++++++++++++++++++++++++++
 linear-assignment.h |  22 +++++
 3 files changed, 224 insertions(+)
 create mode 100644 linear-assignment.c
 create mode 100644 linear-assignment.h

index bc4fc8eea..1af719b44 100644
@@ -870,6 +870,7 @@ LIB_OBJS += gpg-interface.o
 LIB_OBJS += graph.o
 LIB_OBJS += grep.o
 LIB_OBJS += hashmap.o
+LIB_OBJS += linear-assignment.o
 LIB_OBJS += help.o
 LIB_OBJS += hex.o
 LIB_OBJS += ident.o

new file mode 100644
index 000000000..1dfea7662
@@ -0,0 +1,22 @@
+#ifndef LINEAR_ASSIGNMENT_H
+#define LINEAR_ASSIGNMENT_H
+
+/*
+ * Compute an assignment of columns -> rows (and vice versa) such that every
+ * column is assigned to at most one row (and vice versa) minimizing the
+ * overall cost.
+ *
+ * The parameter `cost` is the cost matrix: the cost to assign column j to row
+ * i is `cost[j + column_count * i].
+ *
+ * The arrays column2row and row2column will be populated with the respective
+ * assignments (-1 for unassigned, which can happen only if column_count !=
+ * row_count).
+ */
+void compute_assignment(int column_count, int row_count, int *cost,
+			int *column2row, int *row2column);
+
+/* The maximal cost in the cost matrix (to prevent integer overflows). */
+#define COST_MAX (1<<16)
+
+#endif

gitgitgadget

From: Johannes Schindelin <[email protected]>

This command does not do a whole lot so far, apart from showing a usage that is oddly similar to that of git tbdiff. And for a good reason:
the next commits will turn range-branch into a full-blown replacement for tbdiff.

At this point, we ignore tbdiff's color options, as they will all be implemented later using diff_options.

Since f318d739159 (generate-cmds.sh: export all commands to command-list.h, 2018-05-10), every new command *requires* a man page to build right away, so let's also add a blank man page, too.

---
 .gitignore                       |  1 +
 Documentation/git-range-diff.txt | 10 ++++++++++
 Makefile                         |  1 +
 builtin.h                        |  1 +
 builtin/range-diff.c             | 25 +++++++++++++++++++++++++
 command-list.txt                 |  1 +
 git.c                            |  1 +
 7 files changed, 40 insertions(+)
 create mode 100644 Documentation/git-range-diff.txt
 create mode 100644 builtin/range-diff.c

index 3284a1e9b..cc0ad74b4 100644
@@ -113,6 +113,7 @@
 /git-pull
 /git-push
 /git-quiltimport
+/git-range-diff
 /git-read-tree
 /git-rebase
 /git-rebase--am

new file mode 100644
index 000000000..49f717db8
@@ -0,0 +1,10 @@
+git-range-diff(1)
+=================
+
+NAME
+----
+git-range-diff - Compare two commit ranges (e.g. two versions of a branch)
+
+GIT
+---
+Part of the linkgit:git[1] suite

index 1af719b44..7ff7eba42 100644
@@ -1063,6 +1063,7 @@ BUILTIN_OBJS += builtin/prune-packed.o
 BUILTIN_OBJS += builtin/prune.o
 BUILTIN_OBJS += builtin/pull.o
 BUILTIN_OBJS += builtin/push.o
+BUILTIN_OBJS += builtin/range-diff.o
 BUILTIN_OBJS += builtin/read-tree.o
 BUILTIN_OBJS += builtin/rebase--helper.o
 BUILTIN_OBJS += builtin/receive-pack.o

index 0362f1ce2..99206df4b 100644
@@ -201,6 +201,7 @@ extern int cmd_prune(int argc, const char **argv, const char *prefix);
 extern int cmd_prune_packed(int argc, const char **argv, const char *prefix);
 extern int cmd_pull(int argc, const char **argv, const char *prefix);
 extern int cmd_push(int argc, const char **argv, const char *prefix);
+extern int cmd_range_diff(int argc, const char **argv, const char *prefix);
 extern int cmd_read_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_rebase__helper(int argc, const char **argv, const char *prefix);
 extern int cmd_receive_pack(int argc, const char **argv, const char *prefix);

new file mode 100644
index 000000000..36788ea4f
@@ -0,0 +1,25 @@
+#include "cache.h"
+#include "builtin.h"
+#include "parse-options.h"
+
+static const char * const builtin_range_diff_usage[] = {
+N_("git range-diff [<options>] <old-base>..<old-tip> <new-base>..<new-tip>"),
+N_("git range-diff [<options>] <old-tip>...<new-tip>"),
+N_("git range-diff [<options>] <base> <old-tip> <new-tip>"),
+NULL
+};
+
+int cmd_range_diff(int argc, const char **argv, const char *prefix)
+{
+	int creation_factor = 60;
+	struct option options[] = {
+		OPT_INTEGER(0, "creation-factor", &creation_factor,
+			    N_("Percentage by which creation is weighted")),
+		OPT_END()
+	};
+
+	argc = parse_options(argc, argv, NULL, options,
+			     builtin_range_diff_usage, 0);
+
+	return 0;
+}

index e1c26c1bb..a9dda3b8a 100644
@@ -139,6 +139,7 @@ git-prune-packed                        plumbingmanipulators
 git-pull                                mainporcelain           remote
 git-push                                mainporcelain           remote
 git-quiltimport                         foreignscminterface
+git-range-diff                          mainporcelain
 git-read-tree                           plumbingmanipulators
 git-rebase                              mainporcelain           history
 git-receive-pack                        synchelpers

index fc7d15d54..5b48cac3a 100644
@@ -520,6 +520,7 @@ static struct cmd_struct commands[] = {
 	{ "prune-packed", cmd_prune_packed, RUN_SETUP },
 	{ "pull", cmd_pull, RUN_SETUP | NEED_WORK_TREE },
 	{ "push", cmd_push, RUN_SETUP },
+	{ "range-diff", cmd_range_diff, RUN_SETUP | USE_PAGER },
 	{ "read-tree", cmd_read_tree, RUN_SETUP | SUPPORT_SUPER_PREFIX},
 	{ "rebase--helper", cmd_rebase__helper, RUN_SETUP | NEED_WORK_TREE },
 	{ "receive-pack", cmd_receive_pack },

gitgitgadget

From: Johannes Schindelin <[email protected]>

At this stage, git range-diff can determine corresponding commits of two related commit ranges. This makes use of the recently introduced implementation of the linear assignment algorithm.

The core of this patch is a straight port of the ideas of tbdiff, the apparently dormant project at https://github.com/trast/tbdiff.

The output does not at all match tbdiff's output yet, as this patch really concentrates on getting the patch matching part right.

Note: due to differences in the diff algorithm (tbdiff uses the Python module difflib, Git uses its xdiff fork), the cost matrix calculated by range-diff is different (but very similar) to the one calculated by tbdiff. Therefore, it is possible that they find different matching commits in corner cases (e.g. when a patch was split into two patches of roughly equal length).

---
 Makefile             |   1 +
 builtin/range-diff.c |  45 ++++++-
 range-diff.c         | 311 +++++++++++++++++++++++++++++++++++++++++++
 range-diff.h         |   7 +
 4 files changed, 363 insertions(+), 1 deletion(-)
 create mode 100644 range-diff.c
 create mode 100644 range-diff.h

index 7ff7eba42..72f16882e 100644
@@ -925,6 +925,7 @@ LIB_OBJS += progress.o
 LIB_OBJS += prompt.o
 LIB_OBJS += protocol.o
 LIB_OBJS += quote.o
+LIB_OBJS += range-diff.o
 LIB_OBJS += reachable.o
 LIB_OBJS += read-cache.o
 LIB_OBJS += reflog-walk.o

new file mode 100644
index 000000000..7b6eef303
@@ -0,0 +1,7 @@
+#ifndef RANGE_DIFF_H
+#define RANGE_DIFF_H
+
+int show_range_diff(const char *range1, const char *range2,
+		    int creation_factor);
+
+#endif

gitgitgadget

From: Johannes Schindelin <[email protected]>

This patch lets git range-diff use the same order as tbdiff.

The idea is simple: for left-to-right readers, it is natural to assume that the git range-diff is performed between an older vs a newer version of the branch. As such, the user is probably more interested in the question "where did this come from?" rather than "where did that one go?".

To that end, we list the commits in the order of the second commit range ("the newer version"), inserting the unmatched commits of the first commit range as soon as all their predecessors have been shown.

---
 range-diff.c | 59 +++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 40 insertions(+), 19 deletions(-)

index 15d418afa..2d94200d3 100644
@@ -12,7 +12,7 @@ struct patch_util {
 	struct hashmap_entry e;
 	const char *diff, *patch;
 
-	int i;
+	int i, shown;
 	int diffsize;
 	size_t diff_offset;
 	/* the index of the matching item in the other branch, or -1 */

@@ -260,28 +260,49 @@ static const char *short_oid(struct patch_util *util)
 
 static void output(struct string_list *a, struct string_list *b)
 {
-	int i;
-
-	for (i = 0; i < b->nr; i++) {
-		struct patch_util *util = b->items[i].util, *prev;
+	int i = 0, j = 0;
+
+	/*
+	 * We assume the user is really more interested in the second argument
+	 * ("newer" version). To that end, we print the output in the order of
+	 * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
+	 * commits that are no longer in the RHS into a good place, we place
+	 * them once we have shown all of their predecessors in the LHS.
+	 */
+
+	while (i < a->nr || j < b->nr) {
+		struct patch_util *a_util, *b_util;
+		a_util = i < a->nr ? a->items[i].util : NULL;
+		b_util = j < b->nr ? b->items[j].util : NULL;
+
+		/* Skip all the already-shown commits from the LHS. */
+		while (i < a->nr && a_util->shown)
+			a_util = ++i < a->nr ? a->items[i].util : NULL;
+
+		/* Show unmatched LHS commit whose predecessors were shown. */
+		if (i < a->nr && a_util->matching < 0) {
+			printf("%d: %s < -: --------\n",
+			       i + 1, short_oid(a_util));
+			i++;
+			continue;
+		}
 
-		if (util->matching < 0)
+		/* Show unmatched RHS commits. */
+		while (j < b->nr && b_util->matching < 0) {
 			printf("-: -------- > %d: %s\n",
-					i + 1, short_oid(util));
-		else {
-			prev = a->items[util->matching].util;
-			printf("%d: %s ! %d: %s\n",
-			       util->matching + 1, short_oid(prev),
-			       i + 1, short_oid(util));
+			       j + 1, short_oid(b_util));
+			b_util = ++j < b->nr ? b->items[j].util : NULL;
 		}
-	}
-
-	for (i = 0; i < a->nr; i++) {
-		struct patch_util *util = a->items[i].util;
 
-		if (util->matching < 0)
-			printf("%d: %s < -: --------\n",
-			       i + 1, short_oid(util));
+		/* Show matching LHS/RHS pair. */
+		if (j < b->nr) {
+			a_util = a->items[b_util->matching].util;
+			printf("%d: %s ! %d: %s\n",
+			       b_util->matching + 1, short_oid(a_util),
+			       j + 1, short_oid(b_util));
+			a_util->shown = 1;
+			j++;
+		}
 	}
 }
 

gitgitgadget

From: Johannes Schindelin <[email protected]>

Just like tbdiff, we now show the diff between matching patches. This is a "diff of two diffs", so it can be a bit daunting to read for the beginner.

An alternative would be to display an interdiff, i.e. the hypothetical diff which is the result of first reverting the old diff and then applying the new diff.

Especially when rebasing frequently, an interdiff is often not feasible,
though: if the old diff cannot be applied in reverse (due to a moving upstream), an interdiff can simply not be inferred.

This commit brings range-diff closer to feature parity with regard to tbdiff.

To make git range-diff respect e.g. color.diff.* settings, we have to adjust git_branch_config() accordingly.

Note: while we now parse diff options such as --color, the effect is not yet the same as in tbdiff, where also the commit pairs would be colored. This is left for a later commit.

Note also: while tbdiff accepts the --no-patches option to suppress these diffs between patches, we prefer the -s (or --no-patch) option that is automatically supported via our use of diff_opt_parse().

And finally note: to support diff options, we have to call parse_options() such that it keeps unknown options, and then loop over those and let diff_opt_parse() handle them. After that loop, we have to call parse_options() again, to make sure that no unknown options are left.

---
 builtin/range-diff.c | 29 +++++++++++++++++++++++++++--
 range-diff.c         | 34 +++++++++++++++++++++++++++++++---
 range-diff.h         |  4 +++-
 3 files changed, 61 insertions(+), 6 deletions(-)

index 94c1f362c..19192ab31 100644
@@ -2,6 +2,7 @@
 #include "builtin.h"
 #include "parse-options.h"
 #include "range-diff.h"
+#include "config.h"
 
 static const char * const builtin_range_diff_usage[] = {
 N_("git range-diff [<options>] <old-base>..<old-tip> <new-base>..<new-tip>"),

@@ -13,15 +14,38 @@ NULL
 int cmd_range_diff(int argc, const char **argv, const char *prefix)
 {
 	int creation_factor = 60;
+	struct diff_options diffopt = { NULL };
 	struct option options[] = {
 		OPT_INTEGER(0, "creation-factor", &creation_factor,
 			    N_("Percentage by which creation is weighted")),
 		OPT_END()
 	};
-	int res = 0;
+	int i, j, res = 0;
 	struct strbuf range1 = STRBUF_INIT, range2 = STRBUF_INIT;
 
+	git_config(git_diff_ui_config, NULL);
+
+	diff_setup(&diffopt);
+	diffopt.output_format = DIFF_FORMAT_PATCH;
+
 	argc = parse_options(argc, argv, NULL, options,
+			     builtin_range_diff_usage, PARSE_OPT_KEEP_UNKNOWN |
+			     PARSE_OPT_KEEP_DASHDASH | PARSE_OPT_KEEP_ARGV0);
+
+	for (i = j = 1; i < argc && strcmp("--", argv[i]); ) {
+		int c = diff_opt_parse(&diffopt, argv + i, argc - i, prefix);
+
+		if (!c)
+			argv[j++] = argv[i++];
+		else
+			i += c;
+	}
+	argc = j;
+	diff_setup_done(&diffopt);
+
+	/* Make sure that there are no unparsed options */
+	argc = parse_options(argc, argv, NULL,
+			     options + ARRAY_SIZE(options) - 1, /* OPT_END */
 			     builtin_range_diff_usage, 0);
 
 	if (argc == 2) {

@@ -59,7 +83,8 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 		usage_with_options(builtin_range_diff_usage, options);
 	}
 
-	res = show_range_diff(range1.buf, range2.buf, creation_factor);
+	res = show_range_diff(range1.buf, range2.buf, creation_factor,
+			      &diffopt);
 
 	strbuf_release(&range1);
 	strbuf_release(&range2);

index 2d94200d3..71883a4b7 100644
@@ -6,6 +6,7 @@
 #include "hashmap.h"
 #include "xdiff-interface.h"
 #include "linear-assignment.h"
+#include "diffcore.h"
 
 struct patch_util {
 	/* For the search for an exact match */

@@ -258,7 +259,31 @@ static const char *short_oid(struct patch_util *util)
 	return find_unique_abbrev(&util->oid, DEFAULT_ABBREV);
 }
 
-static void output(struct string_list *a, struct string_list *b)
+static struct diff_filespec *get_filespec(const char *name, const char *p)
+{
+	struct diff_filespec *spec = alloc_filespec(name);
+
+	fill_filespec(spec, &null_oid, 0, 0644);
+	spec->data = (char *)p;
+	spec->size = strlen(p);
+	spec->should_munmap = 0;
+	spec->is_stdin = 1;
+
+	return spec;
+}
+
+static void patch_diff(const char *a, const char *b,
+			      struct diff_options *diffopt)
+{
+	diff_queue(&diff_queued_diff,
+		   get_filespec("a", a), get_filespec("b", b));
+
+	diffcore_std(diffopt);
+	diff_flush(diffopt);
+}
+
+static void output(struct string_list *a, struct string_list *b,
+		   struct diff_options *diffopt)
 {
 	int i = 0, j = 0;
 

@@ -300,6 +325,9 @@ static void output(struct string_list *a, struct string_list *b)
 			printf("%d: %s ! %d: %s\n",
 			       b_util->matching + 1, short_oid(a_util),
 			       j + 1, short_oid(b_util));
+			if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
+				patch_diff(a->items[b_util->matching].string,
+					   b->items[j].string, diffopt);
 			a_util->shown = 1;
 			j++;
 		}

@@ -307,7 +335,7 @@ static void output(struct string_list *a, struct string_list *b)
 }
 
 int show_range_diff(const char *range1, const char *range2,
-		    int creation_factor)
+		    int creation_factor, struct diff_options *diffopt)
 {
 	int res = 0;
 

@@ -322,7 +350,7 @@ int show_range_diff(const char *range1, const char *range2,
 	if (!res) {
 		find_exact_matches(&branch1, &branch2);
 		get_correspondences(&branch1, &branch2, creation_factor);
-		output(&branch1, &branch2);
+		output(&branch1, &branch2, diffopt);
 	}
 
 	string_list_clear(&branch1, 1);

index 7b6eef303..2407d46a3 100644
@@ -1,7 +1,9 @@
 #ifndef RANGE_DIFF_H
 #define RANGE_DIFF_H
 
+#include "diff.h"
+
 int show_range_diff(const char *range1, const char *range2,
-		    int creation_factor);
+		    int creation_factor, struct diff_options *diffopt);
 
 #endif

gitgitgadget

Hi Dscho,

    $ ./git range-diff -- js/range-diff-v4...HEAD
    error: need two commit ranges
    usage: git range-diff [<options>] <old-base>..<old-tip> <new-base>..<new-tip>
       or: git range-diff [<options>] <old-tip>...<new-tip>
       or: git range-diff [<options>] <base> <old-tip> <new-tip>

index ef3ba22e29..132574c57a 100644
@@ -53,6 +53,11 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
                else
                        i += c;
        }
+       if (i < argc && !strcmp("--", argv[i])) {
+               i++; j++;
+               while (i < argc)
+                       argv[j++] = argv[i++];
+       }
        argc = j;
        diff_setup_done(&diffopt);
 

Hi Thomas,

Ouch, good point.

	while (i < argc)
		argv[j++] = argv[i++];

Right, that's much better, thanks!

From: Johannes Schindelin <[email protected]>

When comparing commit messages, we need to keep in mind that they are indented by four spaces. That is, empty lines are no longer empty, but have "trailing whitespace". When displaying them in color, that results in those nagging red lines.

Let's just right-trim the lines in the commit message, it's not like trailing white-space in the commit messages are important enough to care about in git range-diff.

---
 range-diff.c | 1 +
 1 file changed, 1 insertion(+)

index 71883a4b7..1ecee2c09 100644
@@ -85,6 +85,7 @@ static int read_patches(const char *range, struct string_list *list)
 				strbuf_addbuf(&buf, &line);
 				strbuf_addstr(&buf, "\n\n");
 			} else if (starts_with(line.buf, "    ")) {
+				strbuf_rtrim(&line);
 				strbuf_addbuf(&buf, &line);
 				strbuf_addch(&buf, '\n');
 			}

gitgitgadget

From: Johannes Schindelin <[email protected]>

The main information in the range-diff view comes from the list of matching and non-matching commits, the diffs are additional information. Indenting them helps with the reading flow.

---
 builtin/range-diff.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

index 19192ab31..f6df3f19a 100644
@@ -11,6 +11,11 @@ N_("git range-diff [<options>] <base> <old-tip> <new-tip>"),
 NULL
 };
 
+static struct strbuf *output_prefix_cb(struct diff_options *opt, void *data)
+{
+	return data;
+}
+
 int cmd_range_diff(int argc, const char **argv, const char *prefix)
 {
 	int creation_factor = 60;

@@ -21,12 +26,16 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 		OPT_END()
 	};
 	int i, j, res = 0;
+	struct strbuf four_spaces = STRBUF_INIT;
 	struct strbuf range1 = STRBUF_INIT, range2 = STRBUF_INIT;
 
 	git_config(git_diff_ui_config, NULL);
 
 	diff_setup(&diffopt);
 	diffopt.output_format = DIFF_FORMAT_PATCH;
+	diffopt.output_prefix = output_prefix_cb;
+	strbuf_addstr(&four_spaces, "    ");
+	diffopt.output_prefix_data = &four_spaces;
 
 	argc = parse_options(argc, argv, NULL, options,
 			     builtin_range_diff_usage, PARSE_OPT_KEEP_UNKNOWN |

@@ -88,6 +97,7 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 
 	strbuf_release(&range1);
 	strbuf_release(&range2);
+	strbuf_release(&four_spaces);
 
 	return res;
 }

gitgitgadget

From: Johannes Schindelin <[email protected]>

When showing the diff between corresponding patches of the two branch versions, we have to make up a fake filename to run the diff machinery.

That filename does not carry any meaningful information, hence tbdiff suppresses it. So we should, too.

---
 builtin/range-diff.c | 1 +
 diff.c               | 5 ++++-
 diff.h               | 1 +
 3 files changed, 6 insertions(+), 1 deletion(-)

index f6df3f19a..bc7a2fb76 100644
@@ -33,6 +33,7 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 
 	diff_setup(&diffopt);
 	diffopt.output_format = DIFF_FORMAT_PATCH;
+	diffopt.flags.suppress_diff_headers = 1;
 	diffopt.output_prefix = output_prefix_cb;
 	strbuf_addstr(&four_spaces, "    ");
 	diffopt.output_prefix_data = &four_spaces;

index 04d044bbb..9c4bd9fa1 100644
@@ -3395,13 +3395,16 @@ static void builtin_diff(const char *name_a,
 		memset(&xpp, 0, sizeof(xpp));
 		memset(&xecfg, 0, sizeof(xecfg));
 		memset(&ecbdata, 0, sizeof(ecbdata));
+		if (o->flags.suppress_diff_headers)
+			lbl[0] = NULL;
 		ecbdata.label_path = lbl;
 		ecbdata.color_diff = want_color(o->use_color);
 		ecbdata.ws_rule = whitespace_rule(name_b);
 		if (ecbdata.ws_rule & WS_BLANK_AT_EOF)
 			check_blank_at_eof(&mf1, &mf2, &ecbdata);
 		ecbdata.opt = o;
-		ecbdata.header = header.len ? &header : NULL;
+		if (header.len && !o->flags.suppress_diff_headers)
+			ecbdata.header = &header;
 		xpp.flags = o->xdl_opts;
 		xpp.anchors = o->anchors;
 		xpp.anchors_nr = o->anchors_nr;

index a14895bb8..d88ceb357 100644
@@ -94,6 +94,7 @@ struct diff_flags {
 	unsigned funccontext:1;
 	unsigned default_follow_renames:1;
 	unsigned stat_with_summary:1;
+	unsigned suppress_diff_headers:1;
 };
 
 static inline void diff_flags_or(struct diff_flags *a,

gitgitgadget

From: Johannes Schindelin <[email protected]>

This not only uses "dashed stand-ins" for "pairs" where one side is missing (i.e. unmatched commits that are present only in one of the two commit ranges), but also adds onelines for the reader's pleasure.

This change brings git range-diff yet another step closer to feature parity with tbdiff: it now shows the oneline, too, and indicates with = when the commits have identical diffs.

---
 range-diff.c | 59 ++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 50 insertions(+), 9 deletions(-)

index 1ecee2c09..23aa61af5 100644
@@ -7,6 +7,8 @@
 #include "xdiff-interface.h"
 #include "linear-assignment.h"
 #include "diffcore.h"
+#include "commit.h"
+#include "pretty.h"
 
 struct patch_util {
 	/* For the search for an exact match */

@@ -255,9 +257,49 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 	free(b2a);
 }
 
-static const char *short_oid(struct patch_util *util)
+static void output_pair_header(struct strbuf *buf,
+			       struct strbuf *dashes,
+			       struct patch_util *a_util,
+			       struct patch_util *b_util)
 {
-	return find_unique_abbrev(&util->oid, DEFAULT_ABBREV);
+	struct object_id *oid = a_util ? &a_util->oid : &b_util->oid;
+	struct commit *commit;
+
+	if (!dashes->len)
+		strbuf_addchars(dashes, '-',
+				strlen(find_unique_abbrev(oid,
+							  DEFAULT_ABBREV)));
+
+	strbuf_reset(buf);
+	if (!a_util)
+		strbuf_addf(buf, "-:  %s ", dashes->buf);
+	else
+		strbuf_addf(buf, "%d:  %s ", a_util->i + 1,
+			    find_unique_abbrev(&a_util->oid, DEFAULT_ABBREV));
+
+	if (!a_util)
+		strbuf_addch(buf, '>');
+	else if (!b_util)
+		strbuf_addch(buf, '<');
+	else if (strcmp(a_util->patch, b_util->patch))
+		strbuf_addch(buf, '!');
+	else
+		strbuf_addch(buf, '=');
+
+	if (!b_util)
+		strbuf_addf(buf, " -:  %s", dashes->buf);
+	else
+		strbuf_addf(buf, " %d:  %s", b_util->i + 1,
+			    find_unique_abbrev(&b_util->oid, DEFAULT_ABBREV));
+
+	commit = lookup_commit_reference(the_repository, oid);
+	if (commit) {
+		strbuf_addch(buf, ' ');
+		pp_commit_easy(CMIT_FMT_ONELINE, commit, buf);
+	}
+	strbuf_addch(buf, '\n');
+
+	fwrite(buf->buf, buf->len, 1, stdout);
 }
 
 static struct diff_filespec *get_filespec(const char *name, const char *p)

@@ -286,6 +328,7 @@ static void patch_diff(const char *a, const char *b,
 static void output(struct string_list *a, struct string_list *b,
 		   struct diff_options *diffopt)
 {
+	struct strbuf buf = STRBUF_INIT, dashes = STRBUF_INIT;
 	int i = 0, j = 0;
 
 	/*

@@ -307,25 +350,21 @@ static void output(struct string_list *a, struct string_list *b,
 
 		/* Show unmatched LHS commit whose predecessors were shown. */
 		if (i < a->nr && a_util->matching < 0) {
-			printf("%d: %s < -: --------\n",
-			       i + 1, short_oid(a_util));
+			output_pair_header(&buf, &dashes, a_util, NULL);
 			i++;
 			continue;
 		}
 
 		/* Show unmatched RHS commits. */
 		while (j < b->nr && b_util->matching < 0) {
-			printf("-: -------- > %d: %s\n",
-			       j + 1, short_oid(b_util));
+			output_pair_header(&buf, &dashes, NULL, b_util);
 			b_util = ++j < b->nr ? b->items[j].util : NULL;
 		}
 
 		/* Show matching LHS/RHS pair. */
 		if (j < b->nr) {
 			a_util = a->items[b_util->matching].util;
-			printf("%d: %s ! %d: %s\n",
-			       b_util->matching + 1, short_oid(a_util),
-			       j + 1, short_oid(b_util));
+			output_pair_header(&buf, &dashes, a_util, b_util);
 			if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
 				patch_diff(a->items[b_util->matching].string,
 					   b->items[j].string, diffopt);

@@ -333,6 +372,8 @@ static void output(struct string_list *a, struct string_list *b,
 			j++;
 		}
 	}
+	strbuf_release(&buf);
+	strbuf_release(&dashes);
 }
 
 int show_range_diff(const char *range1, const char *range2,

gitgitgadget

From: Johannes Schindelin <[email protected]>

We are comparing complete, formatted commit messages with patches. There are no function names here, so stop looking for them.

---
 range-diff.c | 6 ++++++
 1 file changed, 6 insertions(+)

index 23aa61af5..6d75563f4 100644
@@ -9,6 +9,7 @@
 #include "diffcore.h"
 #include "commit.h"
 #include "pretty.h"
+#include "userdiff.h"
 
 struct patch_util {
 	/* For the search for an exact match */

@@ -302,6 +303,10 @@ static void output_pair_header(struct strbuf *buf,
 	fwrite(buf->buf, buf->len, 1, stdout);
 }
 
+static struct userdiff_driver no_func_name = {
+	.funcname = { "$^", 0 }
+};
+
 static struct diff_filespec *get_filespec(const char *name, const char *p)
 {
 	struct diff_filespec *spec = alloc_filespec(name);

@@ -311,6 +316,7 @@ static struct diff_filespec *get_filespec(const char *name, const char *p)
 	spec->size = strlen(p);
 	spec->should_munmap = 0;
 	spec->is_stdin = 1;
+	spec->driver = &no_func_name;
 
 	return spec;
 }

gitgitgadget

From: Thomas Rast <[email protected]>

These are essentially lifted from https://github.com/trast/tbdiff, with light touch-ups to account for the command now being named git range-diff.

Apart from renaming tbdiff to range-diff, only one test case needed to be adjusted: 11 - 'changed message'.

The underlying reason it had to be adjusted is that diff generation is sometimes ambiguous. In this case, a comment line and an empty line are added, but it is ambiguous whether they were added after the existing empty line, or whether an empty line and the comment line are added *before* the existing empty line. And apparently xdiff picks a different option here than Python's difflib.

---
 t/.gitattributes       |   1 +
 t/t3206-range-diff.sh  | 145 ++++++++++
 t/t3206/history.export | 604 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 750 insertions(+)
 create mode 100755 t/t3206-range-diff.sh
 create mode 100644 t/t3206/history.export

index 3bd959ae5..b17bf71b8 100644
@@ -1,6 +1,7 @@
 t[0-9][0-9][0-9][0-9]/* -whitespace
 /diff-lib/* eol=lf
 /t0110/url-* binary
+/t3206/* eol=lf
 /t3900/*.txt eol=lf
 /t3901/*.txt eol=lf
 /t4034/*/* eol=lf

gitgitgadget

From: Johannes Schindelin <[email protected]>

Arguably the most important part of git range-diff's output is the list of commits in the two branches, together with their relationships.

For that reason, tbdiff introduced color-coding that is pretty intuitive, especially for unchanged patches (all dim yellow, like the first line in git show's output) vs modified patches (old commit is red, new commit is green). Let's imitate that color scheme.

---
 range-diff.c | 51 ++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 38 insertions(+), 13 deletions(-)

index 6d75563f4..b1663da7c 100644
@@ -258,34 +258,53 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 	free(b2a);
 }
 
-static void output_pair_header(struct strbuf *buf,
+static void output_pair_header(struct diff_options *diffopt,
+			       struct strbuf *buf,
 			       struct strbuf *dashes,
 			       struct patch_util *a_util,
 			       struct patch_util *b_util)
 {
 	struct object_id *oid = a_util ? &a_util->oid : &b_util->oid;
 	struct commit *commit;
+	char status;
+	const char *color_reset = diff_get_color_opt(diffopt, DIFF_RESET);
+	const char *color_old = diff_get_color_opt(diffopt, DIFF_FILE_OLD);
+	const char *color_new = diff_get_color_opt(diffopt, DIFF_FILE_NEW);
+	const char *color_commit = diff_get_color_opt(diffopt, DIFF_COMMIT);
+	const char *color;
 
 	if (!dashes->len)
 		strbuf_addchars(dashes, '-',
 				strlen(find_unique_abbrev(oid,
 							  DEFAULT_ABBREV)));
 
+	if (!b_util) {
+		color = color_old;
+		status = '<';
+	} else if (!a_util) {
+		color = color_new;
+		status = '>';
+	} else if (strcmp(a_util->patch, b_util->patch)) {
+		color = color_commit;
+		status = '!';
+	} else {
+		color = color_commit;
+		status = '=';
+	}
+
 	strbuf_reset(buf);
+	strbuf_addstr(buf, status == '!' ? color_old : color);
 	if (!a_util)
 		strbuf_addf(buf, "-:  %s ", dashes->buf);
 	else
 		strbuf_addf(buf, "%d:  %s ", a_util->i + 1,
 			    find_unique_abbrev(&a_util->oid, DEFAULT_ABBREV));
 
-	if (!a_util)
-		strbuf_addch(buf, '>');
-	else if (!b_util)
-		strbuf_addch(buf, '<');
-	else if (strcmp(a_util->patch, b_util->patch))
-		strbuf_addch(buf, '!');
-	else
-		strbuf_addch(buf, '=');
+	if (status == '!')
+		strbuf_addf(buf, "%s%s", color_reset, color);
+	strbuf_addch(buf, status);
+	if (status == '!')
+		strbuf_addf(buf, "%s%s", color_reset, color_new);
 
 	if (!b_util)
 		strbuf_addf(buf, " -:  %s", dashes->buf);

@@ -295,10 +314,13 @@ static void output_pair_header(struct strbuf *buf,
 
 	commit = lookup_commit_reference(the_repository, oid);
 	if (commit) {
+		if (status == '!')
+			strbuf_addf(buf, "%s%s", color_reset, color);
+
 		strbuf_addch(buf, ' ');
 		pp_commit_easy(CMIT_FMT_ONELINE, commit, buf);
 	}
-	strbuf_addch(buf, '\n');
+	strbuf_addf(buf, "%s\n", color_reset);
 
 	fwrite(buf->buf, buf->len, 1, stdout);
 }

@@ -356,21 +378,24 @@ static void output(struct string_list *a, struct string_list *b,
 
 		/* Show unmatched LHS commit whose predecessors were shown. */
 		if (i < a->nr && a_util->matching < 0) {
-			output_pair_header(&buf, &dashes, a_util, NULL);
+			output_pair_header(diffopt,
+					   &buf, &dashes, a_util, NULL);
 			i++;
 			continue;
 		}
 
 		/* Show unmatched RHS commits. */
 		while (j < b->nr && b_util->matching < 0) {
-			output_pair_header(&buf, &dashes, NULL, b_util);
+			output_pair_header(diffopt,
+					   &buf, &dashes, NULL, b_util);
 			b_util = ++j < b->nr ? b->items[j].util : NULL;
 		}
 
 		/* Show matching LHS/RHS pair. */
 		if (j < b->nr) {
 			a_util = a->items[b_util->matching].util;
-			output_pair_header(&buf, &dashes, a_util, b_util);
+			output_pair_header(diffopt,
+					   &buf, &dashes, a_util, b_util);
 			if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
 				patch_diff(a->items[b_util->matching].string,
 					   b->items[j].string, diffopt);

gitgitgadget

From: Johannes Schindelin <[email protected]>

This "color" simply reverts background and foreground. It will be used in the upcoming "dual color" mode of git range-diff, where we will reverse colors for the -/+ markers and the fragment headers of the "outer" diff.

---
 color.h | 1 +
 1 file changed, 1 insertion(+)

index 5b744e1bc..33e786342 100644
@@ -44,6 +44,7 @@ struct strbuf;
 #define GIT_COLOR_BG_CYAN	"\033[46m"
 #define GIT_COLOR_FAINT		"\033[2m"
 #define GIT_COLOR_FAINT_ITALIC	"\033[2;3m"
+#define GIT_COLOR_REVERSE	"\033[7m"
 
 /* A special value meaning "no color selected" */
 #define GIT_COLOR_NIL "NIL"

gitgitgadget

From: Johannes Schindelin <[email protected]>

When diffing diffs, it can be quite daunting to figure out what the heck is going on, as there are nested +/- signs.

Let's make this easier by adding a flag in diff_options that allows color-coding the outer diff sign with inverted colors, so that the preimage and postimage is colored like the diff it is.

Of course, this really only makes sense when the preimage and postimage *are* diffs. So let's not expose this flag via a command-line option for now.

This is a feature that was invented by git-tbdiff, and it will be used by git range-diff in the next commit, by offering it via a new option:
--dual-color.

---
 diff.c | 83 +++++++++++++++++++++++++++++++++++++++++++++++-----------
 diff.h |  1 +
 2 files changed, 69 insertions(+), 15 deletions(-)

index 9c4bd9fa1..e6c857abf 100644
@@ -609,14 +609,18 @@ static void check_blank_at_eof(mmfile_t *mf1, mmfile_t *mf2,
 	ecbdata->blank_at_eof_in_postimage = (at - l2) + 1;
 }
 
-static void emit_line_0(struct diff_options *o, const char *set, const char *reset,
+static void emit_line_0(struct diff_options *o,
+			const char *set, unsigned reverse, const char *reset,
 			int first, const char *line, int len)
 {
 	int has_trailing_newline, has_trailing_carriage_return;
 	int nofirst;
 	FILE *file = o->file;
 
-	fputs(diff_line_prefix(o), file);
+	if (first)
+		fputs(diff_line_prefix(o), file);
+	else if (!len)
+		return;
 
 	if (len == 0) {
 		has_trailing_newline = (first == '\n');

@@ -634,8 +638,10 @@ static void emit_line_0(struct diff_options *o, const char *set, const char *res
 	}
 
 	if (len || !nofirst) {
+		if (reverse && want_color(o->use_color))
+			fputs(GIT_COLOR_REVERSE, file);
 		fputs(set, file);
-		if (!nofirst)
+		if (first && !nofirst)
 			fputc(first, file);
 		fwrite(line, len, 1, file);
 		fputs(reset, file);

@@ -649,7 +655,7 @@ static void emit_line_0(struct diff_options *o, const char *set, const char *res
 static void emit_line(struct diff_options *o, const char *set, const char *reset,
 		      const char *line, int len)
 {
-	emit_line_0(o, set, reset, line[0], line+1, len-1);
+	emit_line_0(o, set, 0, reset, line[0], line+1, len-1);
 }
 
 enum diff_symbol {

@@ -1168,7 +1174,8 @@ static void dim_moved_lines(struct diff_options *o)
 
 static void emit_line_ws_markup(struct diff_options *o,
 				const char *set, const char *reset,
-				const char *line, int len, char sign,
+				const char *line, int len,
+				const char *set_sign, char sign,
 				unsigned ws_rule, int blank_at_eof)
 {
 	const char *ws = NULL;

@@ -1179,14 +1186,20 @@ static void emit_line_ws_markup(struct diff_options *o,
 			ws = NULL;
 	}
 
-	if (!ws)
-		emit_line_0(o, set, reset, sign, line, len);
-	else if (blank_at_eof)
+	if (!ws && !set_sign)
+		emit_line_0(o, set, 0, reset, sign, line, len);
+	else if (!ws) {
+		/* Emit just the prefix, then the rest. */
+		emit_line_0(o, set_sign ? set_sign : set, !!set_sign, reset,
+			    sign, "", 0);
+		emit_line_0(o, set, 0, reset, 0, line, len);
+	} else if (blank_at_eof)
 		/* Blank line at EOF - paint '+' as well */
-		emit_line_0(o, ws, reset, sign, line, len);
+		emit_line_0(o, ws, 0, reset, sign, line, len);
 	else {
 		/* Emit just the prefix, then the rest. */
-		emit_line_0(o, set, reset, sign, "", 0);
+		emit_line_0(o, set_sign ? set_sign : set, !!set_sign, reset,
+			    sign, "", 0);
 		ws_check_emit(line, len, ws_rule,
 			      o->file, set, reset, ws);
 	}

@@ -1196,7 +1209,7 @@ static void emit_diff_symbol_from_struct(struct diff_options *o,
 					 struct emitted_diff_symbol *eds)
 {
 	static const char *nneof = " No newline at end of file\n";
-	const char *context, *reset, *set, *meta, *fraginfo;
+	const char *context, *reset, *set, *set_sign, *meta, *fraginfo;
 	struct strbuf sb = STRBUF_INIT;
 
 	enum diff_symbol s = eds->s;

@@ -1209,7 +1222,7 @@ static void emit_diff_symbol_from_struct(struct diff_options *o,
 		context = diff_get_color_opt(o, DIFF_CONTEXT);
 		reset = diff_get_color_opt(o, DIFF_RESET);
 		putc('\n', o->file);
-		emit_line_0(o, context, reset, '\\',
+		emit_line_0(o, context, 0, reset, '\\',
 			    nneof, strlen(nneof));
 		break;
 	case DIFF_SYMBOL_SUBMODULE_HEADER:

@@ -1236,7 +1249,18 @@ static void emit_diff_symbol_from_struct(struct diff_options *o,
 	case DIFF_SYMBOL_CONTEXT:
 		set = diff_get_color_opt(o, DIFF_CONTEXT);
 		reset = diff_get_color_opt(o, DIFF_RESET);
-		emit_line_ws_markup(o, set, reset, line, len, ' ',
+		set_sign = NULL;
+		if (o->flags.dual_color_diffed_diffs) {
+			char c = !len ? 0 : line[0];
+
+			if (c == '+')
+				set = diff_get_color_opt(o, DIFF_FILE_NEW);
+			else if (c == '@')
+				set = diff_get_color_opt(o, DIFF_FRAGINFO);
+			else if (c == '-')
+				set = diff_get_color_opt(o, DIFF_FILE_OLD);
+		}
+		emit_line_ws_markup(o, set, reset, line, len, set_sign, ' ',
 				    flags & (DIFF_SYMBOL_CONTENT_WS_MASK), 0);
 		break;
 	case DIFF_SYMBOL_PLUS:

@@ -1263,7 +1287,20 @@ static void emit_diff_symbol_from_struct(struct diff_options *o,
 			set = diff_get_color_opt(o, DIFF_FILE_NEW);
 		}
 		reset = diff_get_color_opt(o, DIFF_RESET);
-		emit_line_ws_markup(o, set, reset, line, len, '+',
+		if (!o->flags.dual_color_diffed_diffs)
+			set_sign = NULL;
+		else {
+			char c = !len ? 0 : line[0];
+
+			set_sign = set;
+			if (c == '-')
+				set = diff_get_color_opt(o, DIFF_FILE_OLD);
+			else if (c == '@')
+				set = diff_get_color_opt(o, DIFF_FRAGINFO);
+			else if (c != '+')
+				set = diff_get_color_opt(o, DIFF_CONTEXT);
+		}
+		emit_line_ws_markup(o, set, reset, line, len, set_sign, '+',
 				    flags & DIFF_SYMBOL_CONTENT_WS_MASK,
 				    flags & DIFF_SYMBOL_CONTENT_BLANK_LINE_EOF);
 		break;

@@ -1291,7 +1328,20 @@ static void emit_diff_symbol_from_struct(struct diff_options *o,
 			set = diff_get_color_opt(o, DIFF_FILE_OLD);
 		}
 		reset = diff_get_color_opt(o, DIFF_RESET);
-		emit_line_ws_markup(o, set, reset, line, len, '-',
+		if (!o->flags.dual_color_diffed_diffs)
+			set_sign = NULL;
+		else {
+			char c = !len ? 0 : line[0];
+
+			set_sign = set;
+			if (c == '+')
+				set = diff_get_color_opt(o, DIFF_FILE_NEW);
+			else if (c == '@')
+				set = diff_get_color_opt(o, DIFF_FRAGINFO);
+			else if (c != '-')
+				set = diff_get_color_opt(o, DIFF_CONTEXT);
+		}
+		emit_line_ws_markup(o, set, reset, line, len, set_sign, '-',
 				    flags & DIFF_SYMBOL_CONTENT_WS_MASK, 0);
 		break;
 	case DIFF_SYMBOL_WORDS_PORCELAIN:

@@ -1482,6 +1532,7 @@ static void emit_hunk_header(struct emit_callback *ecbdata,
 	const char *frag = diff_get_color(ecbdata->color_diff, DIFF_FRAGINFO);
 	const char *func = diff_get_color(ecbdata->color_diff, DIFF_FUNCINFO);
 	const char *reset = diff_get_color(ecbdata->color_diff, DIFF_RESET);
+	const char *reverse = ecbdata->color_diff ? GIT_COLOR_REVERSE : "";
 	static const char atat[2] = { '@', '@' };
 	const char *cp, *ep;
 	struct strbuf msgbuf = STRBUF_INIT;

@@ -1502,6 +1553,8 @@ static void emit_hunk_header(struct emit_callback *ecbdata,
 	ep += 2; /* skip over @@ */
 
 	/* The hunk header in fraginfo color */
+	if (ecbdata->opt->flags.dual_color_diffed_diffs)
+		strbuf_addstr(&msgbuf, reverse);
 	strbuf_addstr(&msgbuf, frag);
 	strbuf_add(&msgbuf, line, ep - line);
 	strbuf_addstr(&msgbuf, reset);

index d88ceb357..cca4f9d6c 100644
@@ -95,6 +95,7 @@ struct diff_flags {
 	unsigned default_follow_renames:1;
 	unsigned stat_with_summary:1;
 	unsigned suppress_diff_headers:1;
+	unsigned dual_color_diffed_diffs:1;
 };
 
 static inline void diff_flags_or(struct diff_flags *a,

gitgitgadget

From: Johannes Schindelin <[email protected]>

When showing what changed between old and new commits, we show a diff of the patches. This diff is a diff between diffs, therefore there are nested +/- signs, and it can be relatively hard to understand what is going on.

With the --dual-color option, the preimage and the postimage are colored like the diffs they are, and the *outer* +/- sign is inverted for clarity.

---
 builtin/range-diff.c | 8 ++++++++
 1 file changed, 8 insertions(+)

index bc7a2fb76..da3ad3eba 100644
@@ -20,9 +20,12 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 {
 	int creation_factor = 60;
 	struct diff_options diffopt = { NULL };
+	int dual_color = 0;
 	struct option options[] = {
 		OPT_INTEGER(0, "creation-factor", &creation_factor,
 			    N_("Percentage by which creation is weighted")),
+		OPT_BOOL(0, "dual-color", &dual_color,
+			    N_("color both diff and diff-between-diffs")),
 		OPT_END()
 	};
 	int i, j, res = 0;

@@ -58,6 +61,11 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 			     options + ARRAY_SIZE(options) - 1, /* OPT_END */
 			     builtin_range_diff_usage, 0);
 
+	if (dual_color) {
+		diffopt.use_color = 1;
+		diffopt.flags.dual_color_diffed_diffs = 1;
+	}
+
 	if (argc == 2) {
 		if (!strstr(argv[0], ".."))
 			die(_("no .. in range: '%s'"), argv[0]);

gitgitgadget

From: Johannes Schindelin <[email protected]>

When displaying a diff of diffs, it is possible that there is an outer + before a context line. That happens when the context changed between old and new commit. When that context line starts with a tab (after the space that marks it as context line), our diff machinery spits out a white-space error (space before tab), but in this case, that is incorrect.

Rather than adding a specific whitespace flag that specifically ignores the first space in the output (and might miss other problems with the white-space warnings), let's just skip handling white-space errors in dual color mode to begin with.

---
 diff.c | 1 +
 1 file changed, 1 insertion(+)

index e6c857abf..ea8ecae04 100644
@@ -1299,6 +1299,7 @@ static void emit_diff_symbol_from_struct(struct diff_options *o,
 				set = diff_get_color_opt(o, DIFF_FRAGINFO);
 			else if (c != '+')
 				set = diff_get_color_opt(o, DIFF_CONTEXT);
+			flags &= ~DIFF_SYMBOL_CONTENT_WS_MASK;
 		}
 		emit_line_ws_markup(o, set, reset, line, len, set_sign, '+',
 				    flags & DIFF_SYMBOL_CONTENT_WS_MASK,

gitgitgadget

From: Johannes Schindelin <[email protected]>

The bulk of this patch consists of a heavily butchered version of tbdiff's README written by Thomas Rast and Thomas Gummerer, lifted from
https://github.com/trast/tbdiff.

---
 Documentation/git-range-diff.txt | 229 +++++++++++++++++++++++++++++++
 1 file changed, 229 insertions(+)

index 49f717db8..bebb47d42 100644
@@ -5,6 +5,235 @@ NAME
 ----
 git-range-diff - Compare two commit ranges (e.g. two versions of a branch)
 
+SYNOPSIS
+--------
+[verse]
+'git range-diff' [--color=[<when>]] [--no-color] [<diff-options>]
+	[--dual-color] [--creation-factor=<factor>]
+	( <range1> <range2> | <rev1>...<rev2> | <base> <rev1> <rev2> )
+
+DESCRIPTION
+-----------
+
+This command shows the differences between two versions of a patch
+series, or more generally, two commit ranges (ignoring merge commits).
+
+To that end, it first finds pairs of commits from both commit ranges
+that correspond with each other. Two commits are said to correspond when
+the diff between their patches (i.e. the author information, the commit
+message and the commit diff) is reasonably small compared to the
+patches' size. See ``Algorithm`` below for details.
+
+Finally, the list of matching commits is shown in the order of the
+second commit range, with unmatched commits being inserted just after
+all of their ancestors have been shown.
+
+
+OPTIONS
+-------
+--dual-color::
+	When the commit diffs differ, recreate the original diffs'
+	coloring, and add outer -/+ diff markers with the *background*
+	being red/green to make it easier to see e.g. when there was a
+	change in what exact lines were added.
+
+--creation-factor=<percent>::
+	Set the creation/deletion cost fudge factor to `<percent>`.
+	Defaults to 60. Try a larger value if `git range-diff` erroneously
+	considers a large change a total rewrite (deletion of one commit
+	and addition of another), and a smaller one in the reverse case.
+	See the ``Algorithm`` section below for an explanation why this is
+	needed.
+
+<range1> <range2>::
+	Compare the commits specified by the two ranges, where
+	`<range1>` is considered an older version of `<range2>`.
+
+<rev1>...<rev2>::
+	Equivalent to passing `<rev2>..<rev1>` and `<rev1>..<rev2>`.
+
+<base> <rev1> <rev2>::
+	Equivalent to passing `<base>..<rev1>` and `<base>..<rev2>`.
+	Note that `<base>` does not need to be the exact branch point
+	of the branches. Example: after rebasing a branch `my-topic`,
+	`git range-diff my-topic@{u} my-topic@{1} my-topic` would
+	show the differences introduced by the rebase.
+
+`git range-diff` also accepts the regular diff options (see
+linkgit:git-diff[1]), most notably the `--color=[<when>]` and
+`--no-color` options. These options are used when generating the "diff
+between patches", i.e. to compare the author, commit message and diff of
+corresponding old/new commits. There is currently no means to tweak the
+diff options passed to `git log` when generating those patches.
+
+
+CONFIGURATION
+-------------
+This command uses the `diff.color.*` and `pager.range-diff` settings
+(the latter is on by default).
+See linkgit:git-config[1].
+
+
+EXAMPLES
+--------
+
+When a rebase required merge conflicts to be resolved, compare the changes
+introduced by the rebase directly afterwards using:
+
+------------
+$ git range-diff @{u} @{1} @
+------------
+
+
+A typical output of `git range-diff` would look like this:
+
+------------
+-:  ------- > 1:  0ddba11 Prepare for the inevitable!
+1:  c0debee = 2:  cab005e Add a helpful message at the start
+2:  f00dbal ! 3:  decafe1 Describe a bug
+    @@ -1,3 +1,3 @@
+     Author: A U Thor <[email protected]>
+
+    -TODO: Describe a bug
+    +Describe a bug
+    @@ -324,5 +324,6
+      This is expected.
+
+    -+What is unexpected is that it will also crash.
+    ++Unexpectedly, it also crashes. This is a bug, and the jury is
+    ++still out there how to fix it best. See ticket #314 for details.
+
+      Contact
+3:  bedead < -:  ------- TO-UNDO
+------------
+
+In this example, there are 3 old and 3 new commits, where the developer
+removed the 3rd, added a new one before the first two, and modified the
+commit message of the 2nd commit as well its diff.
+
+When the output goes to a terminal, it is color-coded by default, just
+like regular `git diff`'s output. In addition, the first line (adding a
+commit) is green, the last line (deleting a commit) is red, the second
+line (with a perfect match) is yellow like the commit header of `git
+show`'s output, and the third line colors the old commit red, the new
+one green and the rest like `git show`'s commit header.
+
+The color-coded diff is actually a bit hard to read, though, as it
+colors the entire lines red or green. The line that added "What is
+unexpected" in the old commit, for example, is completely red, even if
+the intent of the old commit was to add something.
+
+To help with that, use the `--dual-color` mode. In this mode, the diff
+of diffs will retain the original diff colors, and prefix the lines with
+-/+ markers that have their *background* red or green, to make it more
+obvious that they describe how the diff itself changed.
+
+
+Algorithm
+---------
+
+The general idea is this: we generate a cost matrix between the commits
+in both commit ranges, then solve the least-cost assignment.
+
+The cost matrix is populated thusly: for each pair of commits, both
+diffs are generated and the "diff of diffs" is generated, with 3 context
+lines, then the number of lines in that diff is used as cost.
+
+To avoid false positives (e.g. when a patch has been removed, and an
+unrelated patch has been added between two iterations of the same patch
+series), the cost matrix is extended to allow for that, by adding
+fixed-cost entries for wholesale deletes/adds.
+
+Example: Let commits `1--2` be the first iteration of a patch series and
+`A--C` the second iteration. Let's assume that `A` is a cherry-pick of
+`2,` and `C` is a cherry-pick of `1` but with a small modification (say,
+a fixed typo). Visualize the commits as a bipartite graph:
+
+------------
+    1            A
+
+    2            B
+
+		 C
+------------
+
+We are looking for a "best" explanation of the new series in terms of
+the old one. We can represent an "explanation" as an edge in the graph:
+
+
+------------
+    1            A
+	       /
+    2 --------'  B
+
+		 C
+------------
+
+This explanation comes for "free" because there was no change. Similarly
+`C` could be explained using `1`, but that comes at some cost c>0
+because of the modification:
+
+------------
+    1 ----.      A
+	  |    /
+    2 ----+---'  B
+	  |
+	  `----- C
+	  c>0
+------------
+
+In mathematical terms, what we are looking for is some sort of a minimum
+cost bipartite matching; `1` is matched to `C` at some cost, etc. The
+underlying graph is in fact a complete bipartite graph; the cost we
+associate with every edge is the size of the diff between the two
+commits' patches. To explain also new commits, we introduce dummy nodes
+on both sides:
+
+------------
+    1 ----.      A
+	  |    /
+    2 ----+---'  B
+	  |
+    o     `----- C
+	  c>0
+    o            o
+
+    o            o
+------------
+
+The cost of an edge `o--C` is the size of `C`'s diff, modified by a
+fudge factor that should be smaller than 100%. The cost of an edge
+`o--o` is free. The fudge factor is necessary because even if `1` and
+`C` have nothing in common, they may still share a few empty lines and
+such, possibly making the assignment `1--C`, `o--o` slightly cheaper
+than `1--o`, `o--C` even if `1` and `C` have nothing in common. With the
+fudge factor we require a much larger common part to consider patches as
+corresponding.
+
+The overall time needed to compute this algorithm is the time needed to
+compute n+m commit diffs and then n*m diffs of patches, plus the time
+needed to compute the least-cost assigment between n and m diffs. Git
+uses an implementation of the Jonker-Volgenant algorithm to solve the
+assignment problem, which has cubic runtime complexity. The matching
+found in this case will look like this:
+
+------------
+    1 ----.      A
+	  |    /
+    2 ----+---'  B
+       .--+-----'
+    o -'  `----- C
+	  c>0
+    o ---------- o
+
+    o ---------- o
+------------
+
+
+SEE ALSO
+--------
+linkgit:git-log[1]
+
 GIT
 ---
 Part of the linkgit:git[1] suite

gitgitgadget

From: Johannes Schindelin <[email protected]>

Tab completion of git range-diff is very convenient, especially given that the revision arguments to specify the commit ranges to compare are typically more complex than, say, what is normally passed to git log.

---
 contrib/completion/git-completion.bash | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

index 94c95516e..3d4ec3432 100644
@@ -1976,6 +1976,20 @@ _git_push ()
 	__git_complete_remote_or_refspec
 }
 
+_git_range_diff ()
+{
+	case "$cur" in
+	--*)
+		__gitcomp "
+			--creation-factor= --dual-color
+			$__git_diff_common_options
+		"
+		return
+		;;
+	esac
+	__git_complete_revlist
+}
+
 _git_rebase ()
 {
 	__git_find_repo_path

gitgitgadget

From: Johannes Schindelin <[email protected]>

As pointed out by Elijah Newren, tbdiff has this neat little alignment trick where it outputs the commit pairs with patch numbers that are padded to the maximal patch number's width:

	  1: cafedead =   1: acefade first patch
	[...]
	314: beefeada < 314: facecab up to PI!

Let's do the same in range-diff, too.

---
 range-diff.c | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)

index b1663da7c..b6b9abac2 100644
@@ -259,6 +259,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 }
 
 static void output_pair_header(struct diff_options *diffopt,
+			       int patch_no_width,
 			       struct strbuf *buf,
 			       struct strbuf *dashes,
 			       struct patch_util *a_util,

@@ -295,9 +296,9 @@ static void output_pair_header(struct diff_options *diffopt,
 	strbuf_reset(buf);
 	strbuf_addstr(buf, status == '!' ? color_old : color);
 	if (!a_util)
-		strbuf_addf(buf, "-:  %s ", dashes->buf);
+		strbuf_addf(buf, "%*s:  %s ", patch_no_width, "-", dashes->buf);
 	else
-		strbuf_addf(buf, "%d:  %s ", a_util->i + 1,
+		strbuf_addf(buf, "%*d:  %s ", patch_no_width, a_util->i + 1,
 			    find_unique_abbrev(&a_util->oid, DEFAULT_ABBREV));
 
 	if (status == '!')

@@ -307,9 +308,9 @@ static void output_pair_header(struct diff_options *diffopt,
 		strbuf_addf(buf, "%s%s", color_reset, color_new);
 
 	if (!b_util)
-		strbuf_addf(buf, " -:  %s", dashes->buf);
+		strbuf_addf(buf, " %*s:  %s", patch_no_width, "-", dashes->buf);
 	else
-		strbuf_addf(buf, " %d:  %s", b_util->i + 1,
+		strbuf_addf(buf, " %*d:  %s", patch_no_width, b_util->i + 1,
 			    find_unique_abbrev(&b_util->oid, DEFAULT_ABBREV));
 
 	commit = lookup_commit_reference(the_repository, oid);

@@ -357,6 +358,7 @@ static void output(struct string_list *a, struct string_list *b,
 		   struct diff_options *diffopt)
 {
 	struct strbuf buf = STRBUF_INIT, dashes = STRBUF_INIT;
+	int patch_no_width = decimal_width(1 + (a->nr > b->nr ? a->nr : b->nr));
 	int i = 0, j = 0;
 
 	/*

@@ -378,7 +380,7 @@ static void output(struct string_list *a, struct string_list *b,
 
 		/* Show unmatched LHS commit whose predecessors were shown. */
 		if (i < a->nr && a_util->matching < 0) {
-			output_pair_header(diffopt,
+			output_pair_header(diffopt, patch_no_width,
 					   &buf, &dashes, a_util, NULL);
 			i++;
 			continue;

@@ -386,7 +388,7 @@ static void output(struct string_list *a, struct string_list *b,
 
 		/* Show unmatched RHS commits. */
 		while (j < b->nr && b_util->matching < 0) {
-			output_pair_header(diffopt,
+			output_pair_header(diffopt, patch_no_width,
 					   &buf, &dashes, NULL, b_util);
 			b_util = ++j < b->nr ? b->items[j].util : NULL;
 		}

@@ -394,7 +396,7 @@ static void output(struct string_list *a, struct string_list *b,
 		/* Show matching LHS/RHS pair. */
 		if (j < b->nr) {
 			a_util = a->items[b_util->matching].util;
-			output_pair_header(diffopt,
+			output_pair_header(diffopt, patch_no_width,
 					   &buf, &dashes, a_util, b_util);
 			if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
 				patch_diff(a->items[b_util->matching].string,

gitgitgadget

From: Johannes Schindelin <[email protected]>

After using this command extensively for the last two months, this developer came to the conclusion that even if the dual color mode still leaves a lot of room for confusion about what was actually changed, the non-dual color mode is substantially worse in that regard.

Therefore, we really want to make the dual color mode the default.

---
 Documentation/git-range-diff.txt       | 32 +++++++++++++++-----------
 builtin/range-diff.c                   | 10 ++++----
 contrib/completion/git-completion.bash |  2 +-
 3 files changed, 25 insertions(+), 19 deletions(-)

index bebb47d42..82c71c682 100644
@@ -9,7 +9,7 @@ SYNOPSIS
 --------
 [verse]
 'git range-diff' [--color=[<when>]] [--no-color] [<diff-options>]
-	[--dual-color] [--creation-factor=<factor>]
+	[--no-dual-color] [--creation-factor=<factor>]
 	( <range1> <range2> | <rev1>...<rev2> | <base> <rev1> <rev2> )
 
 DESCRIPTION

@@ -31,11 +31,14 @@ all of their ancestors have been shown.
 
 OPTIONS
 -------
---dual-color::
-	When the commit diffs differ, recreate the original diffs'
-	coloring, and add outer -/+ diff markers with the *background*
-	being red/green to make it easier to see e.g. when there was a
-	change in what exact lines were added.
+--no-dual-color::
+	When the commit diffs differ, `git range-diff` recreates the
+	original diffs' coloring, and adds outer -/+ diff markers with
+	the *background* being red/green to make it easier to see e.g.
+	when there was a change in what exact lines were added. This is
+	known to `range-diff` as "dual coloring". Use `--no-dual-color`
+	to revert to color all lines according to the outer diff markers
+	(and completely ignore the inner diff when it comes to color).
 
 --creation-factor=<percent>::
 	Set the creation/deletion cost fudge factor to `<percent>`.

@@ -118,15 +121,16 @@ line (with a perfect match) is yellow like the commit header of `git
 show`'s output, and the third line colors the old commit red, the new
 one green and the rest like `git show`'s commit header.
 
-The color-coded diff is actually a bit hard to read, though, as it
-colors the entire lines red or green. The line that added "What is
-unexpected" in the old commit, for example, is completely red, even if
-the intent of the old commit was to add something.
+A naive color-coded diff of diffs is actually a bit hard to read,
+though, as it colors the entire lines red or green. The line that added
+"What is unexpected" in the old commit, for example, is completely red,
+even if the intent of the old commit was to add something.
 
-To help with that, use the `--dual-color` mode. In this mode, the diff
-of diffs will retain the original diff colors, and prefix the lines with
--/+ markers that have their *background* red or green, to make it more
-obvious that they describe how the diff itself changed.
+To help with that, `range` uses the `--dual-color` mode by default. In
+this mode, the diff of diffs will retain the original diff colors, and
+prefix the lines with -/+ markers that have their *background* red or
+green, to make it more obvious that they describe how the diff itself
+changed.
 
 
 Algorithm

index da3ad3eba..ef3ba22e2 100644
@@ -20,11 +20,11 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 {
 	int creation_factor = 60;
 	struct diff_options diffopt = { NULL };
-	int dual_color = 0;
+	int simple_color = -1;
 	struct option options[] = {
 		OPT_INTEGER(0, "creation-factor", &creation_factor,
 			    N_("Percentage by which creation is weighted")),
-		OPT_BOOL(0, "dual-color", &dual_color,
+		OPT_BOOL(0, "no-dual-color", &simple_color,
 			    N_("color both diff and diff-between-diffs")),
 		OPT_END()
 	};

@@ -61,8 +61,10 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 			     options + ARRAY_SIZE(options) - 1, /* OPT_END */
 			     builtin_range_diff_usage, 0);
 
-	if (dual_color) {
-		diffopt.use_color = 1;
+	if (simple_color < 1) {
+		if (!simple_color)
+			/* force color when --dual-color was used */
+			diffopt.use_color = 1;
 		diffopt.flags.dual_color_diffed_diffs = 1;
 	}
 

index 3d4ec3432..d63d2dffd 100644
@@ -1981,7 +1981,7 @@ _git_range_diff ()
 	case "$cur" in
 	--*)
 		__gitcomp "
-			--creation-factor= --dual-color
+			--creation-factor= --no-dual-color
 			$__git_diff_common_options
 		"
 		return

gitgitgadget

From: Johannes Schindelin <[email protected]>

It *is* a confusing thing to look at a diff of diffs. All too easy is it to mix up whether the -/+ markers refer to the "inner" or the "outer" diff, i.e. whether a + indicates that a line was added by either the old or the new diff (or both), or whether the new diff does something different than the old diff.

To make things easier to process for normal developers, we introduced the dual color mode which colors the lines according to the commit diff, i.e. lines that are added by a commit (whether old, new, or both) are colored in green. In non-dual color mode, the lines would be colored according to the outer diff: if the old commit added a line, it would be colored red (because that line addition is only present in the first commit range that was specified on the command-line, i.e. the "old" commit, but not in the second commit range, i.e. the "new" commit).

However, this dual color mode is still not making things clear enough, as we are looking at two levels of diffs, and we still only pick a color according to *one* of them (the outer diff marker is colored differently, of course, but in particular with deep indentation, it is easy to lose track of that outer diff marker's background color).

Therefore, let's add another dimension to the mix. Still use green/red/normal according to the commit diffs, but now also dim the lines that were only in the old commit, and use bold face for the lines that are only in the new commit.

That way, it is much easier not to lose track of, say, when we are looking at a line that was added in the previous iteration of a patch series but the new iteration adds a slightly different version: the obsolete change will be dimmed, the current version of the patch will be bold.

At least this developer has a much easier time reading the range-diffs that way.

---
 Documentation/config.txt         |  6 ++++--
 Documentation/git-range-diff.txt | 17 +++++++++++++----
 color.h                          |  6 ++++++
 diff.c                           | 28 ++++++++++++++++++++++------
 diff.h                           |  8 +++++++-
 5 files changed, 52 insertions(+), 13 deletions(-)

index 63365dcf3..90241ed77 100644
@@ -1193,8 +1193,10 @@ color.diff.<slot>::
 	(highlighting whitespace errors), `oldMoved` (deleted lines),
 	`newMoved` (added lines), `oldMovedDimmed`, `oldMovedAlternative`,
 	`oldMovedAlternativeDimmed`, `newMovedDimmed`, `newMovedAlternative`
-	and `newMovedAlternativeDimmed` (See the '<mode>'
-	setting of '--color-moved' in linkgit:git-diff[1] for details).
+	`newMovedAlternativeDimmed` (See the '<mode>'
+	setting of '--color-moved' in linkgit:git-diff[1] for details),
+	`contextDimmed`, `oldDimmed`, `newDimmed`, `contextBold`,
+	`oldBold`, and `newBold` (see linkgit:git-range-diff[1] for details).
 
 color.decorate.<slot>::
 	Use customized color for 'git log --decorate' output.  `<slot>` is one

index 82c71c682..f693930fd 100644
@@ -35,10 +35,19 @@ OPTIONS
 	When the commit diffs differ, `git range-diff` recreates the
 	original diffs' coloring, and adds outer -/+ diff markers with
 	the *background* being red/green to make it easier to see e.g.
-	when there was a change in what exact lines were added. This is
-	known to `range-diff` as "dual coloring". Use `--no-dual-color`
-	to revert to color all lines according to the outer diff markers
-	(and completely ignore the inner diff when it comes to color).
+	when there was a change in what exact lines were added.
++
+Additionally, the commit diff lines that are only present in the first commit
+range are shown "dimmed" (this can be overridden using the `color.diff.<slot>`
+config setting where `<slot>` is one of `contextDimmed`, `oldDimmed` and
+`newDimmed`), and the commit diff lines that are only present in the second
+commit range are shown in bold (which can be overridden using the config
+settings `color.diff.<slot>` with `<slot>` being one of `contextBold`,
+`oldBold` or `newBold`).
++
+This is known to `range-diff` as "dual coloring". Use `--no-dual-color`
+to revert to color all lines according to the outer diff markers
+(and completely ignore the inner diff when it comes to color).
 
 --creation-factor=<percent>::
 	Set the creation/deletion cost fudge factor to `<percent>`.

index 33e786342..98894d6a1 100644
@@ -36,6 +36,12 @@ struct strbuf;
 #define GIT_COLOR_BOLD_BLUE	"\033[1;34m"
 #define GIT_COLOR_BOLD_MAGENTA	"\033[1;35m"
 #define GIT_COLOR_BOLD_CYAN	"\033[1;36m"
+#define GIT_COLOR_FAINT_RED	"\033[2;31m"
+#define GIT_COLOR_FAINT_GREEN	"\033[2;32m"
+#define GIT_COLOR_FAINT_YELLOW	"\033[2;33m"
+#define GIT_COLOR_FAINT_BLUE	"\033[2;34m"
+#define GIT_COLOR_FAINT_MAGENTA	"\033[2;35m"
+#define GIT_COLOR_FAINT_CYAN	"\033[2;36m"
 #define GIT_COLOR_BG_RED	"\033[41m"
 #define GIT_COLOR_BG_GREEN	"\033[42m"
 #define GIT_COLOR_BG_YELLOW	"\033[43m"

index ea8ecae04..ae1314952 100644
@@ -70,6 +70,12 @@ static char diff_colors[][COLOR_MAXLEN] = {
 	GIT_COLOR_BOLD_YELLOW,	/* NEW_MOVED ALTERNATIVE */
 	GIT_COLOR_FAINT,	/* NEW_MOVED_DIM */
 	GIT_COLOR_FAINT_ITALIC,	/* NEW_MOVED_ALTERNATIVE_DIM */
+	GIT_COLOR_FAINT,	/* CONTEXT_DIM */
+	GIT_COLOR_FAINT_RED,	/* OLD_DIM */
+	GIT_COLOR_FAINT_GREEN,	/* NEW_DIM */
+	GIT_COLOR_BOLD,		/* CONTEXT_BOLD */
+	GIT_COLOR_BOLD_RED,	/* OLD_BOLD */
+	GIT_COLOR_BOLD_GREEN,	/* NEW_BOLD */
 };
 
 static const char *color_diff_slots[] = {

@@ -89,6 +95,12 @@ static const char *color_diff_slots[] = {
 	[DIFF_FILE_NEW_MOVED_ALT]     = "newMovedAlternative",
 	[DIFF_FILE_NEW_MOVED_DIM]     = "newMovedDimmed",
 	[DIFF_FILE_NEW_MOVED_ALT_DIM] = "newMovedAlternativeDimmed",
+	[DIFF_CONTEXT_DIM]	      = "contextDimmed",
+	[DIFF_FILE_OLD_DIM]	      = "oldDimmed",
+	[DIFF_FILE_NEW_DIM]	      = "newDimmed",
+	[DIFF_CONTEXT_BOLD]	      = "contextBold",
+	[DIFF_FILE_OLD_BOLD]	      = "oldBold",
+	[DIFF_FILE_NEW_BOLD]	      = "newBold",
 };
 
 static NORETURN void die_want_option(const char *option_name)

@@ -1294,11 +1306,13 @@ static void emit_diff_symbol_from_struct(struct diff_options *o,
 
 			set_sign = set;
 			if (c == '-')
-				set = diff_get_color_opt(o, DIFF_FILE_OLD);
+				set = diff_get_color_opt(o, DIFF_FILE_OLD_BOLD);
 			else if (c == '@')
 				set = diff_get_color_opt(o, DIFF_FRAGINFO);
-			else if (c != '+')
-				set = diff_get_color_opt(o, DIFF_CONTEXT);
+			else if (c == '+')
+				set = diff_get_color_opt(o, DIFF_FILE_NEW_BOLD);
+			else
+				set = diff_get_color_opt(o, DIFF_CONTEXT_BOLD);
 			flags &= ~DIFF_SYMBOL_CONTENT_WS_MASK;
 		}
 		emit_line_ws_markup(o, set, reset, line, len, set_sign, '+',

@@ -1336,11 +1350,13 @@ static void emit_diff_symbol_from_struct(struct diff_options *o,
 
 			set_sign = set;
 			if (c == '+')
-				set = diff_get_color_opt(o, DIFF_FILE_NEW);
+				set = diff_get_color_opt(o, DIFF_FILE_NEW_DIM);
 			else if (c == '@')
 				set = diff_get_color_opt(o, DIFF_FRAGINFO);
-			else if (c != '-')
-				set = diff_get_color_opt(o, DIFF_CONTEXT);
+			else if (c == '-')
+				set = diff_get_color_opt(o, DIFF_FILE_OLD_DIM);
+			else
+				set = diff_get_color_opt(o, DIFF_CONTEXT_DIM);
 		}
 		emit_line_ws_markup(o, set, reset, line, len, set_sign, '-',
 				    flags & DIFF_SYMBOL_CONTENT_WS_MASK, 0);

index cca4f9d6c..e1e54256c 100644
@@ -248,7 +248,13 @@ enum color_diff {
 	DIFF_FILE_NEW_MOVED = 13,
 	DIFF_FILE_NEW_MOVED_ALT = 14,
 	DIFF_FILE_NEW_MOVED_DIM = 15,
-	DIFF_FILE_NEW_MOVED_ALT_DIM = 16
+	DIFF_FILE_NEW_MOVED_ALT_DIM = 16,
+	DIFF_CONTEXT_DIM = 17,
+	DIFF_FILE_OLD_DIM = 18,
+	DIFF_FILE_NEW_DIM = 19,
+	DIFF_CONTEXT_BOLD = 20,
+	DIFF_FILE_OLD_BOLD = 21,
+	DIFF_FILE_NEW_BOLD = 22,
 };
 const char *diff_get_color(int diff_use_color, enum color_diff ix);
 #define diff_get_color_opt(o, ix) \

gitgitgadget

The incredibly useful git-tbdiff [https://github.com/trast/tbdiff] tool to compare patch series (say, to see what changed between two iterations sent to the Git mailing list) is slightly less useful for this developer due to the fact that it requires the hungarian and numpy Python packages which are for some reason really hard to build in MSYS2. So hard that I even had to give up, because it was simply easier to re-implement the whole shebang as a builtin command.

The project at https://github.com/trast/tbdiff seems to be dormant, anyway. Funny (and true) story: I looked at the open Pull Requests to see how active that project is, only to find to my surprise that I had submitted one in August 2015, and that it was still unanswered let alone merged.

While at it, I forward-ported AEvar's patch to force --decorate=no because git -p tbdiff would fail otherwise.

Side note: I work on implementing range-diff not only to make life easier for reviewers who have to suffer through v2, v3, ... of my patch series, but also to verify my changes before submitting a new iteration. And also, maybe even more importantly, I plan to use it to verify my merging-rebases of Git for Windows (for which I previously used to redirect the pre-rebase/post-rebase diffs vs upstream and then compare them using git diff --no-index). And of course any interested person can see what changes were necessary e.g. in the merging-rebase of Git for Windows onto v2.17.0 by running a command like:

        base=^{/Start.the.merging-rebase}
        tag=v2.17.0.windows.1
        pre=$tag$base^2
        git range-diff $pre$base..$pre $tag$base..$tag

The command uses what it calls the "dual color mode" (can be disabled via --no-dual-color) which helps identifying what actually changed: it prefixes lines with a - (and red background) that correspond to the first commit range, and with a + (and green background) that correspond to the second range. The rest of the lines will be colored according to the original diffs.

Changes since v4:

* Fixed a typo in the commit message of "range-diff: add tests" that was introduced in v4.
* White-space fixes.
* Fixed the length of the first header underline in the man page.
* Changed the preprocessor guard in linear-assignment.h to reflect the new name (instead of the old name, which was hungarian.h).
* Likewise, changed the preprocessor guards in range-diff.h to hide the history of the thrice-renamed command.
* Fixed indentation in the completion.
* Instead of trying to paper over white-space error handling that does not apply to "diffs of diffs", dual color mode now simply disables all white-space warnings.
* When showing the "single arg must be symmetric range" error message, git range-diff now also shows the usage.
* Adjusted the commit message of "range-diff: adjust the output of the commit pairs" to avoid the surprise of the reviewer when onelines are printed all of a sudden, too.
* "range-diff: adjust the output of the commit pairs" is now using a simpler way to print onelines.
* We are now sandwiching the diff_opt_parse() loop between two parse_options(), to make sure that we caught all options, and that the -- separator is handled.
* Adjusted the lookup_commit_reference() call to the newest master (it now takes a the_repository parameter).

Changes since v3:

* The cover letter was adjusted to reflect the new reality (the command is called range-diff now, not branch-diff, and --dual-color is the default).
* The documentation was adjusted a bit more in the patch that makes --dual-color the default.
* Clarified the calculation of the cost matrix, as per Stefan Beller's request.
* The man page now spells out that merge commits are ignored in the commit ranges (not merges per se).
* The code in linear-assignment.c was adjusted to use the SWAP() macro.
* The commit message of the patch introducing the first rudimentary implementation no longer talks about the "Hungarian" algorithm, but about the "linear assignment algorithm" instead.
* A bogus indentation change was backed out from the patch introducing the first rudimentary implementation.
* Instead of merely warning about missing .. in the 2-parameter invocation, we now exit with the error message.
* The diff_opt_parse() function is allowed to return a value larger than 1, indicating that more than just one command-line parameter was parsed. We now advance by the indicated value instead of always advancing exactly 1 (which is still correct much of the time).
* A lengthy if...else if...else if...else was simplified (from a logical point of view) by reordering it.
* The unnecessarily static variable dashes was turned into a local variable of the caller.
* The commit message talking about the new man page still referred to git branch --diff, which has been fixed.
* A forgotten t7910 reference was changed to t3206.
* An unbalanced double-tick was fixed in the man page.
* Fixed grammar both of the commit message and the description of the --no-dual-color option.
* To fix the build, a blank man page is now introduced together with the new range-diff command, even if it is populated for real only at a later patch (i.e. at the same time as before).
* The headaches Junio fears would be incurred by that simple workaround to avoid bogus white-space error reporting are fended off: a more complex patch is now in place that adds (and uses) a new white-space flag. Sadly, as is all too common when Junio "encourages" me to replace a simple workaround by something "proper", it caused all kinds of headaches to get this right, so I am rather less certain that the "proper" fix will cause us less headaches than the simple workaround would have done. But whatever.
* The dual color mode now also dims the changes that are exclusively in the first specified commit range, and uses bold face on the changes exclusively in the second one. This matches the intuition when using range-diff to compare an older iteration of a patch series to a newer
one: the changes from the previous iteration that were replaced by new ones "fade", while the changes that replace them are "shiny new".

Changes since v2:

* Right-aligned the patch numbers in the commit pairs.
* Used ALLOC_ARRAY() in hungarian.c instead of xmalloc(sizeof()*size).
* Changed compute_assignment()s return type from int to void, as it always succeeds.
* Changed the Hungarian Algorithm to use an integer cost matrix.
* Changed the --creation-weight option to --creation-factor where is an integer.
* Retitled 1/19 and 2/19 to better conform with the current conventions, as pointed out (and suggested) by Junio.
* Shut up Coverity, and at the same time avoided passing the unnecessary i and j parameters to output_pair_header().
* Removed support for the --no-patches option: we inherit diff_options' support for -s already (and much more).
* Removed the ugly _INV enum values, and introduced a beautiful GIT_COLOR_REVERSE instead. This way, whatever the user configured as color.diff.new (or .old) will be used in reverse in the dual color mode.
* Instead of overriding the fragment header color, the dual color mode will now reverse the "outer" fragment headers, too.
* Turned the stand-alone branch-diff command into the --diff option of git branch. Adjusted pretty much all commit messages to account for this. This change should no longer be visible: see below.
* Pretty much re-wrote the completion, to support the new --diff mode of git-branch. See below: it was reverted for range-diff.
* Renamed t7910 to t3206, to be closer to the git-branch tests.
* Ensured that git_diff_ui_config() gets called, and therefore color.diff.* respected.
* Avoided leaking four_spaces.
* Fixed a declaration in a for (;;) statement (which Junio had as a fixup! that I almost missed).
* Renamed branch --diff, which had been renamed from branch-diff (which was picked to avoid re-using tbdiff) to range-diff.
* Renamed hungarian.c and its header to linear-assignment.c
* Made --dual-color the default, and changed it to still auto-detect whether color should be used rather than forcing it

Johannes Schindelin (20):
linear-assignment: a function to solve least-cost assignment problems Introduce range-diff to compare iterations of a topic branch
range-diff: first rudimentary implementation
range-diff: improve the order of the shown commits
range-diff: also show the diff between patches
range-diff: right-trim commit messages
range-diff: indent the diffs just like tbdiff
range-diff: suppress the diff headers
range-diff: adjust the output of the commit pairs
range-diff: do not show "function names" in hunk headers
range-diff: use color for the commit pairs
color: add the meta color GIT_COLOR_REVERSE
diff: add an internal option to dual-color diffs of diffs
range-diff: offer to dual-color the diffs
range-diff --dual-color: skip white-space warnings
range-diff: populate the man page
completion: support git range-diff
range-diff: left-pad patch numbers
range-diff: make --dual-color the default mode
range-diff: use dim/bold cues to improve dual color mode

Thomas Rast (1):
range-diff: add tests

 .gitignore                             |   1 +
 Documentation/config.txt               |   6 +-
 Documentation/git-range-diff.txt       | 252 +++++++++++
 Makefile                               |   3 +
 builtin.h                              |   1 +
 builtin/range-diff.c                   | 116 +++++
 color.h                                |   7 +
 command-list.txt                       |   1 +
 contrib/completion/git-completion.bash |  14 +
 diff.c                                 | 105 ++++-
 diff.h                                 |  10 +-
 git.c                                  |   1 +
 linear-assignment.c                    | 201 ++++++++
 linear-assignment.h                    |  22 +
 range-diff.c                           | 435 ++++++++++++++++++
 range-diff.h                           |   9 +
 t/.gitattributes                       |   1 +
 t/t3206-range-diff.sh                  | 145 ++++++
 t/t3206/history.export                 | 604 +++++++++++++++++++++++++
 19 files changed, 1915 insertions(+), 19 deletions(-)
 create mode 100644 Documentation/git-range-diff.txt
 create mode 100644 builtin/range-diff.c
 create mode 100644 linear-assignment.c
 create mode 100644 linear-assignment.h
 create mode 100644 range-diff.c
 create mode 100644 range-diff.h
 create mode 100755 t/t3206-range-diff.sh
 create mode 100644 t/t3206/history.export

base-commit: 1d89318c48d233d52f1db230cf622935ac3c69fa
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-1%2Fdscho%2Fbranch-diff-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1/dscho/branch-diff-v6
Pull-Request: https://github.com/gitgitgadget/git/pull/1

Range-diff vs v5:

  1:  f168da3a3 =  1:  f168da3a3 linear-assignment: a function to solve least-cost assignment problems
  2:  33758f361 =  2:  33758f361 Introduce `range-diff` to compare iterations of a topic branch
  3:  08b8c3fc4 =  3:  08b8c3fc4 range-diff: first rudimentary implementation
  4:  7b9091968 =  4:  7b9091968 range-diff: improve the order of the shown commits
  5:  9e1e66007 !  5:  8515d2f75 range-diff: also show the diff between patches
     @@ -80,6 +80,8 @@
      +		else
      +			i += c;
      +	}
     ++	while (i < argc)
     ++		argv[j++] = argv[i++];
      +	argc = j;
      +	diff_setup_done(&diffopt);
      +
  6:  167ca02a3 =  6:  a10ca0163 range-diff: right-trim commit messages
  7:  ca8de8c75 =  7:  f81cbef2c range-diff: indent the diffs just like tbdiff
  8:  eb94d1982 =  8:  458090ffd range-diff: suppress the diff headers
  9:  6330afad9 =  9:  d3be03a44 range-diff: adjust the output of the commit pairs
 10:  c296675eb = 10:  94b44dfe6 range-diff: do not show "function names" in hunk headers
 11:  85e0ab82f = 11:  1477c58e4 range-diff: add tests
 12:  f48b62644 = 12:  32492c159 range-diff: use color for the commit pairs
 13:  1ad74f939 = 13:  969a196f4 color: add the meta color GIT_COLOR_REVERSE
 14:  39a0ecd28 = 14:  f1c86f606 diff: add an internal option to dual-color diffs of diffs
 15:  c32a24f6a = 15:  3c7b9f339 range-diff: offer to dual-color the diffs
 16:  05947781f = 16:  c56c51c8b range-diff --dual-color: skip white-space warnings
 17:  3147c4440 = 17:  8c5543a06 range-diff: populate the man page
 18:  b08e6d937 = 18:  16e3cf27b completion: support `git range-diff`
 19:  19406283e = 19:  d9b09abcf range-diff: left-pad patch numbers
 20:  6b3552386 = 20:  f6fd3955e range-diff: make --dual-color the default mode
 21:  ccf8c1bb2 = 21:  699cd712e range-diff: use dim/bold cues to improve dual color mode

gitgitgadget

From: Johannes Schindelin <[email protected]>

The problem solved by the code introduced in this commit goes like this:
given two sets of items, and a cost matrix which says how much it "costs" to assign any given item of the first set to any given item of the second, assign all items (except when the sets have different size) in the cheapest way.

We use the Jonker-Volgenant algorithm to solve the assignment problem to answer questions such as: given two different versions of a topic branch (or iterations of a patch series), what is the best pairing of commits/patches between the different versions?

---
 Makefile            |   1 +
 linear-assignment.c | 201 ++++++++++++++++++++++++++++++++++++++++++++
 linear-assignment.h |  22 +++++
 3 files changed, 224 insertions(+)
 create mode 100644 linear-assignment.c
 create mode 100644 linear-assignment.h

index bc4fc8eea..1af719b44 100644
@@ -870,6 +870,7 @@ LIB_OBJS += gpg-interface.o
 LIB_OBJS += graph.o
 LIB_OBJS += grep.o
 LIB_OBJS += hashmap.o
+LIB_OBJS += linear-assignment.o
 LIB_OBJS += help.o
 LIB_OBJS += hex.o
 LIB_OBJS += ident.o

new file mode 100644
index 000000000..1dfea7662
@@ -0,0 +1,22 @@
+#ifndef LINEAR_ASSIGNMENT_H
+#define LINEAR_ASSIGNMENT_H
+
+/*
+ * Compute an assignment of columns -> rows (and vice versa) such that every
+ * column is assigned to at most one row (and vice versa) minimizing the
+ * overall cost.
+ *
+ * The parameter `cost` is the cost matrix: the cost to assign column j to row
+ * i is `cost[j + column_count * i].
+ *
+ * The arrays column2row and row2column will be populated with the respective
+ * assignments (-1 for unassigned, which can happen only if column_count !=
+ * row_count).
+ */
+void compute_assignment(int column_count, int row_count, int *cost,
+			int *column2row, int *row2column);
+
+/* The maximal cost in the cost matrix (to prevent integer overflows). */
+#define COST_MAX (1<<16)
+
+#endif

gitgitgadget

From: Johannes Schindelin <[email protected]>

This command does not do a whole lot so far, apart from showing a usage that is oddly similar to that of git tbdiff. And for a good reason:
the next commits will turn range-branch into a full-blown replacement for tbdiff.

At this point, we ignore tbdiff's color options, as they will all be implemented later using diff_options.

Since f318d739159 (generate-cmds.sh: export all commands to command-list.h, 2018-05-10), every new command *requires* a man page to build right away, so let's also add a blank man page, too.

---
 .gitignore                       |  1 +
 Documentation/git-range-diff.txt | 10 ++++++++++
 Makefile                         |  1 +
 builtin.h                        |  1 +
 builtin/range-diff.c             | 25 +++++++++++++++++++++++++
 command-list.txt                 |  1 +
 git.c                            |  1 +
 7 files changed, 40 insertions(+)
 create mode 100644 Documentation/git-range-diff.txt
 create mode 100644 builtin/range-diff.c

index 3284a1e9b..cc0ad74b4 100644
@@ -113,6 +113,7 @@
 /git-pull
 /git-push
 /git-quiltimport
+/git-range-diff
 /git-read-tree
 /git-rebase
 /git-rebase--am

new file mode 100644
index 000000000..49f717db8
@@ -0,0 +1,10 @@
+git-range-diff(1)
+=================
+
+NAME
+----
+git-range-diff - Compare two commit ranges (e.g. two versions of a branch)
+
+GIT
+---
+Part of the linkgit:git[1] suite

index 1af719b44..7ff7eba42 100644
@@ -1063,6 +1063,7 @@ BUILTIN_OBJS += builtin/prune-packed.o
 BUILTIN_OBJS += builtin/prune.o
 BUILTIN_OBJS += builtin/pull.o
 BUILTIN_OBJS += builtin/push.o
+BUILTIN_OBJS += builtin/range-diff.o
 BUILTIN_OBJS += builtin/read-tree.o
 BUILTIN_OBJS += builtin/rebase--helper.o
 BUILTIN_OBJS += builtin/receive-pack.o

index 0362f1ce2..99206df4b 100644
@@ -201,6 +201,7 @@ extern int cmd_prune(int argc, const char **argv, const char *prefix);
 extern int cmd_prune_packed(int argc, const char **argv, const char *prefix);
 extern int cmd_pull(int argc, const char **argv, const char *prefix);
 extern int cmd_push(int argc, const char **argv, const char *prefix);
+extern int cmd_range_diff(int argc, const char **argv, const char *prefix);
 extern int cmd_read_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_rebase__helper(int argc, const char **argv, const char *prefix);
 extern int cmd_receive_pack(int argc, const char **argv, const char *prefix);

new file mode 100644
index 000000000..36788ea4f
@@ -0,0 +1,25 @@
+#include "cache.h"
+#include "builtin.h"
+#include "parse-options.h"
+
+static const char * const builtin_range_diff_usage[] = {
+N_("git range-diff [<options>] <old-base>..<old-tip> <new-base>..<new-tip>"),
+N_("git range-diff [<options>] <old-tip>...<new-tip>"),
+N_("git range-diff [<options>] <base> <old-tip> <new-tip>"),
+NULL
+};
+
+int cmd_range_diff(int argc, const char **argv, const char *prefix)
+{
+	int creation_factor = 60;
+	struct option options[] = {
+		OPT_INTEGER(0, "creation-factor", &creation_factor,
+			    N_("Percentage by which creation is weighted")),
+		OPT_END()
+	};
+
+	argc = parse_options(argc, argv, NULL, options,
+			     builtin_range_diff_usage, 0);
+
+	return 0;
+}

index e1c26c1bb..a9dda3b8a 100644
@@ -139,6 +139,7 @@ git-prune-packed                        plumbingmanipulators
 git-pull                                mainporcelain           remote
 git-push                                mainporcelain           remote
 git-quiltimport                         foreignscminterface
+git-range-diff                          mainporcelain
 git-read-tree                           plumbingmanipulators
 git-rebase                              mainporcelain           history
 git-receive-pack                        synchelpers

index fc7d15d54..5b48cac3a 100644
@@ -520,6 +520,7 @@ static struct cmd_struct commands[] = {
 	{ "prune-packed", cmd_prune_packed, RUN_SETUP },
 	{ "pull", cmd_pull, RUN_SETUP | NEED_WORK_TREE },
 	{ "push", cmd_push, RUN_SETUP },
+	{ "range-diff", cmd_range_diff, RUN_SETUP | USE_PAGER },
 	{ "read-tree", cmd_read_tree, RUN_SETUP | SUPPORT_SUPER_PREFIX},
 	{ "rebase--helper", cmd_rebase__helper, RUN_SETUP | NEED_WORK_TREE },
 	{ "receive-pack", cmd_receive_pack },

gitgitgadget

From: Johannes Schindelin <[email protected]>

At this stage, git range-diff can determine corresponding commits of two related commit ranges. This makes use of the recently introduced implementation of the linear assignment algorithm.

The core of this patch is a straight port of the ideas of tbdiff, the apparently dormant project at https://github.com/trast/tbdiff.

The output does not at all match tbdiff's output yet, as this patch really concentrates on getting the patch matching part right.

Note: due to differences in the diff algorithm (tbdiff uses the Python module difflib, Git uses its xdiff fork), the cost matrix calculated by range-diff is different (but very similar) to the one calculated by tbdiff. Therefore, it is possible that they find different matching commits in corner cases (e.g. when a patch was split into two patches of roughly equal length).

---
 Makefile             |   1 +
 builtin/range-diff.c |  45 ++++++-
 range-diff.c         | 311 +++++++++++++++++++++++++++++++++++++++++++
 range-diff.h         |   7 +
 4 files changed, 363 insertions(+), 1 deletion(-)
 create mode 100644 range-diff.c
 create mode 100644 range-diff.h

index 7ff7eba42..72f16882e 100644
@@ -925,6 +925,7 @@ LIB_OBJS += progress.o
 LIB_OBJS += prompt.o
 LIB_OBJS += protocol.o
 LIB_OBJS += quote.o
+LIB_OBJS += range-diff.o
 LIB_OBJS += reachable.o
 LIB_OBJS += read-cache.o
 LIB_OBJS += reflog-walk.o

new file mode 100644
index 000000000..7b6eef303
@@ -0,0 +1,7 @@
+#ifndef RANGE_DIFF_H
+#define RANGE_DIFF_H
+
+int show_range_diff(const char *range1, const char *range2,
+		    int creation_factor);
+
+#endif

gitgitgadget

"Johannes Schindelin via GitGitGadget" <[email protected]>

From: Johannes Schindelin <[email protected]>

This patch lets git range-diff use the same order as tbdiff.

The idea is simple: for left-to-right readers, it is natural to assume that the git range-diff is performed between an older vs a newer version of the branch. As such, the user is probably more interested in the question "where did this come from?" rather than "where did that one go?".

To that end, we list the commits in the order of the second commit range ("the newer version"), inserting the unmatched commits of the first commit range as soon as all their predecessors have been shown.

---
 range-diff.c | 59 +++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 40 insertions(+), 19 deletions(-)

index 15d418afa..2d94200d3 100644
@@ -12,7 +12,7 @@ struct patch_util {
 	struct hashmap_entry e;
 	const char *diff, *patch;
 
-	int i;
+	int i, shown;
 	int diffsize;
 	size_t diff_offset;
 	/* the index of the matching item in the other branch, or -1 */

@@ -260,28 +260,49 @@ static const char *short_oid(struct patch_util *util)
 
 static void output(struct string_list *a, struct string_list *b)
 {
-	int i;
-
-	for (i = 0; i < b->nr; i++) {
-		struct patch_util *util = b->items[i].util, *prev;
+	int i = 0, j = 0;
+
+	/*
+	 * We assume the user is really more interested in the second argument
+	 * ("newer" version). To that end, we print the output in the order of
+	 * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
+	 * commits that are no longer in the RHS into a good place, we place
+	 * them once we have shown all of their predecessors in the LHS.
+	 */
+
+	while (i < a->nr || j < b->nr) {
+		struct patch_util *a_util, *b_util;
+		a_util = i < a->nr ? a->items[i].util : NULL;
+		b_util = j < b->nr ? b->items[j].util : NULL;
+
+		/* Skip all the already-shown commits from the LHS. */
+		while (i < a->nr && a_util->shown)
+			a_util = ++i < a->nr ? a->items[i].util : NULL;
+
+		/* Show unmatched LHS commit whose predecessors were shown. */
+		if (i < a->nr && a_util->matching < 0) {
+			printf("%d: %s < -: --------\n",
+			       i + 1, short_oid(a_util));
+			i++;
+			continue;
+		}
 
-		if (util->matching < 0)
+		/* Show unmatched RHS commits. */
+		while (j < b->nr && b_util->matching < 0) {
 			printf("-: -------- > %d: %s\n",
-					i + 1, short_oid(util));
-		else {
-			prev = a->items[util->matching].util;
-			printf("%d: %s ! %d: %s\n",
-			       util->matching + 1, short_oid(prev),
-			       i + 1, short_oid(util));
+			       j + 1, short_oid(b_util));
+			b_util = ++j < b->nr ? b->items[j].util : NULL;
 		}
-	}
-
-	for (i = 0; i < a->nr; i++) {
-		struct patch_util *util = a->items[i].util;
 
-		if (util->matching < 0)
-			printf("%d: %s < -: --------\n",
-			       i + 1, short_oid(util));
+		/* Show matching LHS/RHS pair. */
+		if (j < b->nr) {
+			a_util = a->items[b_util->matching].util;
+			printf("%d: %s ! %d: %s\n",
+			       b_util->matching + 1, short_oid(a_util),
+			       j + 1, short_oid(b_util));
+			a_util->shown = 1;
+			j++;
+		}
 	}
 }
 

gitgitgadget

From: Johannes Schindelin <[email protected]>

Just like tbdiff, we now show the diff between matching patches. This is a "diff of two diffs", so it can be a bit daunting to read for the beginner.

An alternative would be to display an interdiff, i.e. the hypothetical diff which is the result of first reverting the old diff and then applying the new diff.

Especially when rebasing frequently, an interdiff is often not feasible,
though: if the old diff cannot be applied in reverse (due to a moving upstream), an interdiff can simply not be inferred.

This commit brings range-diff closer to feature parity with regard to tbdiff.

To make git range-diff respect e.g. color.diff.* settings, we have to adjust git_branch_config() accordingly.

Note: while we now parse diff options such as --color, the effect is not yet the same as in tbdiff, where also the commit pairs would be colored. This is left for a later commit.

Note also: while tbdiff accepts the --no-patches option to suppress these diffs between patches, we prefer the -s (or --no-patch) option that is automatically supported via our use of diff_opt_parse().

And finally note: to support diff options, we have to call parse_options() such that it keeps unknown options, and then loop over those and let diff_opt_parse() handle them. After that loop, we have to call parse_options() again, to make sure that no unknown options are left.

---
 builtin/range-diff.c | 31 +++++++++++++++++++++++++++++--
 range-diff.c         | 34 +++++++++++++++++++++++++++++++---
 range-diff.h         |  4 +++-
 3 files changed, 63 insertions(+), 6 deletions(-)

index 94c1f362c..3b06ed944 100644
@@ -2,6 +2,7 @@
 #include "builtin.h"
 #include "parse-options.h"
 #include "range-diff.h"
+#include "config.h"
 
 static const char * const builtin_range_diff_usage[] = {
 N_("git range-diff [<options>] <old-base>..<old-tip> <new-base>..<new-tip>"),

@@ -13,15 +14,40 @@ NULL
 int cmd_range_diff(int argc, const char **argv, const char *prefix)
 {
 	int creation_factor = 60;
+	struct diff_options diffopt = { NULL };
 	struct option options[] = {
 		OPT_INTEGER(0, "creation-factor", &creation_factor,
 			    N_("Percentage by which creation is weighted")),
 		OPT_END()
 	};
-	int res = 0;
+	int i, j, res = 0;
 	struct strbuf range1 = STRBUF_INIT, range2 = STRBUF_INIT;
 
+	git_config(git_diff_ui_config, NULL);
+
+	diff_setup(&diffopt);
+	diffopt.output_format = DIFF_FORMAT_PATCH;
+
 	argc = parse_options(argc, argv, NULL, options,
+			     builtin_range_diff_usage, PARSE_OPT_KEEP_UNKNOWN |
+			     PARSE_OPT_KEEP_DASHDASH | PARSE_OPT_KEEP_ARGV0);
+
+	for (i = j = 1; i < argc && strcmp("--", argv[i]); ) {
+		int c = diff_opt_parse(&diffopt, argv + i, argc - i, prefix);
+
+		if (!c)
+			argv[j++] = argv[i++];
+		else
+			i += c;
+	}
+	while (i < argc)
+		argv[j++] = argv[i++];
+	argc = j;
+	diff_setup_done(&diffopt);
+
+	/* Make sure that there are no unparsed options */
+	argc = parse_options(argc, argv, NULL,
+			     options + ARRAY_SIZE(options) - 1, /* OPT_END */
 			     builtin_range_diff_usage, 0);
 
 	if (argc == 2) {

@@ -59,7 +85,8 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 		usage_with_options(builtin_range_diff_usage, options);
 	}
 
-	res = show_range_diff(range1.buf, range2.buf, creation_factor);
+	res = show_range_diff(range1.buf, range2.buf, creation_factor,
+			      &diffopt);
 
 	strbuf_release(&range1);
 	strbuf_release(&range2);

index 2d94200d3..71883a4b7 100644
@@ -6,6 +6,7 @@
 #include "hashmap.h"
 #include "xdiff-interface.h"
 #include "linear-assignment.h"
+#include "diffcore.h"
 
 struct patch_util {
 	/* For the search for an exact match */

@@ -258,7 +259,31 @@ static const char *short_oid(struct patch_util *util)
 	return find_unique_abbrev(&util->oid, DEFAULT_ABBREV);
 }
 
-static void output(struct string_list *a, struct string_list *b)
+static struct diff_filespec *get_filespec(const char *name, const char *p)
+{
+	struct diff_filespec *spec = alloc_filespec(name);
+
+	fill_filespec(spec, &null_oid, 0, 0644);
+	spec->data = (char *)p;
+	spec->size = strlen(p);
+	spec->should_munmap = 0;
+	spec->is_stdin = 1;
+
+	return spec;
+}
+
+static void patch_diff(const char *a, const char *b,
+			      struct diff_options *diffopt)
+{
+	diff_queue(&diff_queued_diff,
+		   get_filespec("a", a), get_filespec("b", b));
+
+	diffcore_std(diffopt);
+	diff_flush(diffopt);
+}
+
+static void output(struct string_list *a, struct string_list *b,
+		   struct diff_options *diffopt)
 {
 	int i = 0, j = 0;
 

@@ -300,6 +325,9 @@ static void output(struct string_list *a, struct string_list *b)
 			printf("%d: %s ! %d: %s\n",
 			       b_util->matching + 1, short_oid(a_util),
 			       j + 1, short_oid(b_util));
+			if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
+				patch_diff(a->items[b_util->matching].string,
+					   b->items[j].string, diffopt);
 			a_util->shown = 1;
 			j++;
 		}

@@ -307,7 +335,7 @@ static void output(struct string_list *a, struct string_list *b)
 }
 
 int show_range_diff(const char *range1, const char *range2,
-		    int creation_factor)
+		    int creation_factor, struct diff_options *diffopt)
 {
 	int res = 0;
 

@@ -322,7 +350,7 @@ int show_range_diff(const char *range1, const char *range2,
 	if (!res) {
 		find_exact_matches(&branch1, &branch2);
 		get_correspondences(&branch1, &branch2, creation_factor);
-		output(&branch1, &branch2);
+		output(&branch1, &branch2, diffopt);
 	}
 
 	string_list_clear(&branch1, 1);

index 7b6eef303..2407d46a3 100644
@@ -1,7 +1,9 @@
 #ifndef RANGE_DIFF_H
 #define RANGE_DIFF_H
 
+#include "diff.h"
+
 int show_range_diff(const char *range1, const char *range2,
-		    int creation_factor);
+		    int creation_factor, struct diff_options *diffopt);
 
 #endif

gitgitgadget

From: Johannes Schindelin <[email protected]>

When comparing commit messages, we need to keep in mind that they are indented by four spaces. That is, empty lines are no longer empty, but have "trailing whitespace". When displaying them in color, that results in those nagging red lines.

Let's just right-trim the lines in the commit message, it's not like trailing white-space in the commit messages are important enough to care about in git range-diff.

---
 range-diff.c | 1 +
 1 file changed, 1 insertion(+)

index 71883a4b7..1ecee2c09 100644
@@ -85,6 +85,7 @@ static int read_patches(const char *range, struct string_list *list)
 				strbuf_addbuf(&buf, &line);
 				strbuf_addstr(&buf, "\n\n");
 			} else if (starts_with(line.buf, "    ")) {
+				strbuf_rtrim(&line);
 				strbuf_addbuf(&buf, &line);
 				strbuf_addch(&buf, '\n');
 			}

gitgitgadget

From: Johannes Schindelin <[email protected]>

The main information in the range-diff view comes from the list of matching and non-matching commits, the diffs are additional information. Indenting them helps with the reading flow.

---
 builtin/range-diff.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

index 3b06ed944..f0598005a 100644
@@ -11,6 +11,11 @@ N_("git range-diff [<options>] <base> <old-tip> <new-tip>"),
 NULL
 };
 
+static struct strbuf *output_prefix_cb(struct diff_options *opt, void *data)
+{
+	return data;
+}
+
 int cmd_range_diff(int argc, const char **argv, const char *prefix)
 {
 	int creation_factor = 60;

@@ -21,12 +26,16 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 		OPT_END()
 	};
 	int i, j, res = 0;
+	struct strbuf four_spaces = STRBUF_INIT;
 	struct strbuf range1 = STRBUF_INIT, range2 = STRBUF_INIT;
 
 	git_config(git_diff_ui_config, NULL);
 
 	diff_setup(&diffopt);
 	diffopt.output_format = DIFF_FORMAT_PATCH;
+	diffopt.output_prefix = output_prefix_cb;
+	strbuf_addstr(&four_spaces, "    ");
+	diffopt.output_prefix_data = &four_spaces;
 
 	argc = parse_options(argc, argv, NULL, options,
 			     builtin_range_diff_usage, PARSE_OPT_KEEP_UNKNOWN |

@@ -90,6 +99,7 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 
 	strbuf_release(&range1);
 	strbuf_release(&range2);
+	strbuf_release(&four_spaces);
 
 	return res;
 }

gitgitgadget

From: Johannes Schindelin <[email protected]>

When showing the diff between corresponding patches of the two branch versions, we have to make up a fake filename to run the diff machinery.

That filename does not carry any meaningful information, hence tbdiff suppresses it. So we should, too.

---
 builtin/range-diff.c | 1 +
 diff.c               | 5 ++++-
 diff.h               | 1 +
 3 files changed, 6 insertions(+), 1 deletion(-)

index f0598005a..76659d0b3 100644
@@ -33,6 +33,7 @@ int cmd_range_diff(int argc, const char **argv, const char *prefix)
 
 	diff_setup(&diffopt);
 	diffopt.output_format = DIFF_FORMAT_PATCH;
+	diffopt.flags.suppress_diff_headers = 1;
 	diffopt.output_prefix = output_prefix_cb;
 	strbuf_addstr(&four_spaces, "    ");
 	diffopt.output_prefix_data = &four_spaces;

index 04d044bbb..9c4bd9fa1 100644
@@ -3395,13 +3395,16 @@ static void builtin_diff(const char *name_a,
 		memset(&xpp, 0, sizeof(xpp));
 		memset(&xecfg, 0, sizeof(xecfg));
 		memset(&ecbdata, 0, sizeof(ecbdata));
+		if (o->flags.suppress_diff_headers)
+			lbl[0] = NULL;
 		ecbdata.label_path = lbl;
 		ecbdata.color_diff = want_color(o->use_color);
 		ecbdata.ws_rule = whitespace_rule(name_b);
 		if (ecbdata.ws_rule & WS_BLANK_AT_EOF)
 			check_blank_at_eof(&mf1, &mf2, &ecbdata);
 		ecbdata.opt = o;
-		ecbdata.header = header.len ? &header : NULL;
+		if (header.len && !o->flags.suppress_diff_headers)
+			ecbdata.header = &header;
 		xpp.flags = o->xdl_opts;
 		xpp.anchors = o->anchors;
 		xpp.anchors_nr = o->anchors_nr;

index a14895bb8..d88ceb357 100644
@@ -94,6 +94,7 @@ struct diff_flags {
 	unsigned funccontext:1;
 	unsigned default_follow_renames:1;
 	unsigned stat_with_summary:1;
+	unsigned suppress_diff_headers:1;
 };
 
 static inline void diff_flags_or(struct diff_flags *a,

gitgitgadget

From: Johannes Schindelin <[email protected]>

This not only uses "dashed stand-ins" for "pairs" where one side is missing (i.e. unmatched commits that are present only in one of the two commit ranges), but also adds onelines for the reader's pleasure.

This change brings git range-diff yet another step closer to feature parity with tbdiff: it now shows the oneline, too, and indicates with = when the commits have identical diffs.

---
 range-diff.c | 59 ++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 50 insertions(+), 9 deletions(-)

index 1ecee2c09..23aa61af5 100644
@@ -7,6 +7,8 @@
 #include "xdiff-interface.h"
 #include "linear-assignment.h"
 #include "diffcore.h"
+#include "commit.h"
+#include "pretty.h"
 
 struct patch_util {
 	/* For the search for an exact match */

@@ -255,9 +257,49 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 	free(b2a);
 }
 
-static const char *short_oid(struct patch_util *util)
+static void output_pair_header(struct strbuf *buf,
+			       struct strbuf *dashes,
+			       struct patch_util *a_util,
+			       struct patch_util *b_util)
 {
-	return find_unique_abbrev(&util->oid, DEFAULT_ABBREV);
+	struct object_id *oid = a_util ? &a_util->oid : &b_util->oid;
+	struct commit *commit;
+
+	if (!dashes->len)
+		strbuf_addchars(dashes, '-',
+				strlen(find_unique_abbrev(oid,
+							  DEFAULT_ABBREV)));
+
+	strbuf_reset(buf);
+	if (!a_util)
+		strbuf_addf(buf, "-:  %s ", dashes->buf);
+	else
+		strbuf_addf(buf, "%d:  %s ", a_util->i + 1,
+			    find_unique_abbrev(&a_util->oid, DEFAULT_ABBREV));
+
+	if (!a_util)
+		strbuf_addch(buf, '>');
+	else if (!b_util)
+		strbuf_addch(buf, '<');
+	else if (strcmp(a_util->patch, b_util->patch))
+		strbuf_addch(buf, '!');
+	else
+		strbuf_addch(buf, '=');
+
+	if (!b_util)
+		strbuf_addf(buf, " -:  %s", dashes->buf);
+	else
+		strbuf_addf(buf, " %d:  %s", b_util->i + 1,
+			    find_unique_abbrev(&b_util->oid, DEFAULT_ABBREV));
+
+	commit = lookup_commit_reference(the_repository, oid);
+	if (commit) {
+		strbuf_addch(buf, ' ');
+		pp_commit_easy(CMIT_FMT_ONELINE, commit, buf);
+	}
+	strbuf_addch(buf, '\n');
+
+	fwrite(buf->buf, buf->len, 1, stdout);
 }
 
 static struct diff_filespec *get_filespec(const char *name, const char *p)

@@ -286,6 +328,7 @@ static void patch_diff(const char *a, const char *b,
 static void output(struct string_list *a, struct string_list *b,
 		   struct diff_options *diffopt)
 {
+	struct strbuf buf = STRBUF_INIT, dashes = STRBUF_INIT;
 	int i = 0, j = 0;
 
 	/*

@@ -307,25 +350,21 @@ static void output(struct string_list *a, struct string_list *b,
 
 		/* Show unmatched LHS commit whose predecessors were shown. */
 		if (i < a->nr && a_util->matching < 0) {
-			printf("%d: %s < -: --------\n",
-			       i + 1, short_oid(a_util));
+			output_pair_header(&buf, &dashes, a_util, NULL);
 			i++;
 			continue;
 		}
 
 		/* Show unmatched RHS commits. */
 		while (j < b->nr && b_util->matching < 0) {
-			printf("-: -------- > %d: %s\n",
-			       j + 1, short_oid(b_util));
+			output_pair_header(&buf, &dashes, NULL, b_util);
 			b_util = ++j < b->nr ? b->items[j].util : NULL;
 		}
 
 		/* Show matching LHS/RHS pair. */
 		if (j < b->nr) {
 			a_util = a->items[b_util->matching].util;
-			printf("%d: %s ! %d: %s\n",
-			       b_util->matching + 1, short_oid(a_util),
-			       j + 1, short_oid(b_util));
+			output_pair_header(&buf, &dashes, a_util, b_util);
 			if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
 				patch_diff(a->items[b_util->matching].string,
 					   b->items[j].string, diffopt);

@@ -333,6 +372,8 @@ static void output(struct string_list *a, struct string_list *b,
 			j++;
 		}
 	}
+	strbuf_release(&buf);
+	strbuf_release(&dashes);
 }
 
 int show_range_diff(const char *range1, const char *range2,

gitgitgadget

From: Johannes Schindelin <[email protected]>

We are comparing complete, formatted commit messages with patches. There are no function names here, so stop looking for them.

---
 range-diff.c | 6 ++++++
 1 file changed, 6 insertions(+)

index 23aa61af5..6d75563f4 100644
@@ -9,6 +9,7 @@
 #include "diffcore.h"
 #include "commit.h"
 #include "pretty.h"
+#include "userdiff.h"
 
 struct patch_util {
 	/* For the search for an exact match */

@@ -302,6 +303,10 @@ static void output_pair_header(struct strbuf *buf,
 	fwrite(buf->buf, buf->len, 1, stdout);
 }
 
+static struct userdiff_driver no_func_name = {
+	.funcname = { "$^", 0 }
+};
+
 static struct diff_filespec *get_filespec(const char *name, const char *p)
 {
 	struct diff_filespec *spec = alloc_filespec(name);

@@ -311,6 +316,7 @@ static struct diff_filespec *get_filespec(const char *name, const char *p)
 	spec->size = strlen(p);
 	spec->should_munmap = 0;
 	spec->is_stdin = 1;
+	spec->driver = &no_func_name;
 
 	return spec;
 }

gitgitgadget

From: Thomas Rast <[email protected]>

These are essentially lifted from https://github.com/trast/tbdiff, with light touch-ups to account for the command now being named git range-diff.

Apart from renaming tbdiff to range-diff, only one test case needed to be adjusted: 11 - 'changed message'.

The underlying reason it had to be adjusted is that diff generation is sometimes ambiguous. In this case, a comment line and an empty line are added, but it is ambiguous whether they were added after the existing empty line, or whether an empty line and the comment line are added *before* the existing empty line. And apparently xdiff picks a different option here than Python's difflib.

---
 t/.gitattributes       |   1 +
 t/t3206-range-diff.sh  | 145 ++++++++++
 t/t3206/history.export | 604 +++++++++++++++++++++++++++++++++++++++++
 3 files changed, 750 insertions(+)
 create mode 100755 t/t3206-range-diff.sh
 create mode 100644 t/t3206/history.export

index 3bd959ae5..b17bf71b8 100644
@@ -1,6 +1,7 @@
 t[0-9][0-9][0-9][0-9]/* -whitespace
 /diff-lib/* eol=lf
 /t0110/url-* binary
+/t3206/* eol=lf
 /t3900/*.txt eol=lf
 /t3901/*.txt eol=lf
 /t4034/*/* eol=lf

gitgitgadget

Just noticed while reading the whole series again (hopefully for the last time :)), do we need Thomas Rast's Sign-off here, as he is credited as the author here?