1 <?xml version=
"1.0" encoding=
"UTF-8"?>
2 <!DOCTYPE html PUBLIC
"-//W3C//DTD XHTML 1.1//EN"
3 "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
4 <html xmlns=
"http://www.w3.org/1999/xhtml" xml:
lang=
"en">
6 <meta http-equiv=
"Content-Type" content=
"application/xhtml+xml; charset=UTF-8" />
7 <meta name=
"generator" content=
"AsciiDoc 10.2.0" />
8 <title>git-range-diff(
1)
</title>
9 <style type=
"text/css">
10 /* Shared CSS for AsciiDoc xhtml11 and html5 backends */
14 font-family: Georgia,serif;
18 h1, h2, h3, h4, h5, h6,
19 div.title, caption.title,
20 thead, p.table.header,
22 #author, #revnumber, #revdate, #revremark,
24 font-family: Arial,Helvetica,sans-serif;
28 margin:
1em
5%
1em
5%;
33 text-decoration: underline;
49 h1, h2, h3, h4, h5, h6 {
57 border-bottom:
2px solid silver;
77 border:
1px solid silver;
88 ul
> li { color: #aaa; }
89 ul
> li
> * { color: black; }
91 .monospaced, code, pre {
92 font-family:
"Courier New", Courier, monospace;
99 white-space: pre-wrap;
109 #revnumber, #revdate, #revremark {
114 border-top:
2px solid silver;
120 padding-bottom:
0.5em;
124 padding-bottom:
0.5em;
129 margin-bottom:
1.5em;
131 div.imageblock, div.exampleblock, div.verseblock,
132 div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
133 div.admonitionblock {
135 margin-bottom:
1.5em;
137 div.admonitionblock {
139 margin-bottom:
2.0em;
144 div.content { /* Block element content. */
148 /* Block element titles. */
149 div.title, caption.title {
154 margin-bottom:
0.5em;
160 td div.title:first-child {
163 div.content div.title:first-child {
166 div.content + div.title {
170 div.sidebarblock
> div.content {
172 border:
1px solid #dddddd;
173 border-left:
4px solid #f0f0f0;
177 div.listingblock
> div.content {
178 border:
1px solid #dddddd;
179 border-left:
5px solid #f0f0f0;
184 div.quoteblock, div.verseblock {
188 border-left:
5px solid #f0f0f0;
192 div.quoteblock
> div.attribution {
197 div.verseblock
> pre.content {
198 font-family: inherit;
201 div.verseblock
> div.attribution {
205 /* DEPRECATED: Pre version
8.2.7 verse style literal block. */
206 div.verseblock + div.attribution {
210 div.admonitionblock .icon {
214 text-decoration: underline;
216 padding-right:
0.5em;
218 div.admonitionblock td.content {
220 border-left:
3px solid #dddddd;
223 div.exampleblock
> div.content {
224 border-left:
3px solid #dddddd;
228 div.imageblock div.content { padding-left:
0; }
229 span.image img { border-style: none; vertical-align: text-bottom; }
230 a.image:visited { color: white; }
234 margin-bottom:
0.8em;
247 list-style-position: outside;
250 list-style-type: decimal;
253 list-style-type: lower-alpha;
256 list-style-type: upper-alpha;
259 list-style-type: lower-roman;
262 list-style-type: upper-roman;
265 div.compact ul, div.compact ol,
266 div.compact p, div.compact p,
267 div.compact div, div.compact div {
269 margin-bottom:
0.1em;
281 margin-bottom:
0.8em;
284 padding-bottom:
15px;
286 dt.hdlist1.strong, td.hdlist1.strong {
292 padding-right:
0.8em;
298 div.hdlist.compact tr {
307 .footnote, .footnoteref {
311 span.footnote, span.footnoteref {
312 vertical-align: super;
316 margin:
20px
0 20px
0;
320 #footnotes div.footnote {
326 border-top:
1px solid silver;
335 padding-right:
0.5em;
336 padding-bottom:
0.3em;
344 #footer-badges { display: none; }
348 margin-bottom:
2.5em;
356 margin-bottom:
0.1em;
359 div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
376 span.aqua { color: aqua; }
377 span.black { color: black; }
378 span.blue { color: blue; }
379 span.fuchsia { color: fuchsia; }
380 span.gray { color: gray; }
381 span.green { color: green; }
382 span.lime { color: lime; }
383 span.maroon { color: maroon; }
384 span.navy { color: navy; }
385 span.olive { color: olive; }
386 span.purple { color: purple; }
387 span.red { color: red; }
388 span.silver { color: silver; }
389 span.teal { color: teal; }
390 span.white { color: white; }
391 span.yellow { color: yellow; }
393 span.aqua-background { background: aqua; }
394 span.black-background { background: black; }
395 span.blue-background { background: blue; }
396 span.fuchsia-background { background: fuchsia; }
397 span.gray-background { background: gray; }
398 span.green-background { background: green; }
399 span.lime-background { background: lime; }
400 span.maroon-background { background: maroon; }
401 span.navy-background { background: navy; }
402 span.olive-background { background: olive; }
403 span.purple-background { background: purple; }
404 span.red-background { background: red; }
405 span.silver-background { background: silver; }
406 span.teal-background { background: teal; }
407 span.white-background { background: white; }
408 span.yellow-background { background: yellow; }
410 span.big { font-size:
2em; }
411 span.small { font-size:
0.6em; }
413 span.underline { text-decoration: underline; }
414 span.overline { text-decoration: overline; }
415 span.line-through { text-decoration: line-through; }
417 div.unbreakable { page-break-inside: avoid; }
427 margin-bottom:
1.5em;
429 div.tableblock
> table {
430 border:
3px solid #
527bbd;
432 thead, p.table.header {
439 /* Because the table frame attribute is overridden by CSS in most browsers. */
440 div.tableblock
> table[
frame=
"void"] {
443 div.tableblock
> table[
frame=
"hsides"] {
444 border-left-style: none;
445 border-right-style: none;
447 div.tableblock
> table[
frame=
"vsides"] {
448 border-top-style: none;
449 border-bottom-style: none;
460 margin-bottom:
1.5em;
462 thead, p.tableblock.header {
473 border-color: #
527bbd;
474 border-collapse: collapse;
476 th.tableblock, td.tableblock {
480 border-color: #
527bbd;
483 table.tableblock.frame-topbot {
484 border-left-style: hidden;
485 border-right-style: hidden;
487 table.tableblock.frame-sides {
488 border-top-style: hidden;
489 border-bottom-style: hidden;
491 table.tableblock.frame-none {
492 border-style: hidden;
495 th.tableblock.halign-left, td.tableblock.halign-left {
498 th.tableblock.halign-center, td.tableblock.halign-center {
501 th.tableblock.halign-right, td.tableblock.halign-right {
505 th.tableblock.valign-top, td.tableblock.valign-top {
508 th.tableblock.valign-middle, td.tableblock.valign-middle {
509 vertical-align: middle;
511 th.tableblock.valign-bottom, td.tableblock.valign-bottom {
512 vertical-align: bottom;
523 padding-bottom:
0.5em;
524 border-top:
2px solid silver;
525 border-bottom:
2px solid silver;
530 body.manpage div.sectionbody {
535 body.manpage div#toc { display: none; }
540 <script type=
"text/javascript">
542 var asciidoc = { // Namespace.
544 /////////////////////////////////////////////////////////////////////
545 // Table Of Contents generator
546 /////////////////////////////////////////////////////////////////////
548 /* Author: Mihai Bazon, September
2002
549 * http://students.infoiasi.ro/~mishoo
551 * Table Of Content generator
554 * Feel free to use this script under the terms of the GNU General Public
555 * License, as long as you do not remove or alter this notice.
558 /* modified by Troy D. Hanson, September
2006. License: GPL */
559 /* modified by Stuart Rackham,
2006,
2009. License: GPL */
562 toc: function (toclevels) {
564 function getText(el) {
566 for (var i = el.firstChild; i != null; i = i.nextSibling) {
567 if (i.nodeType ==
3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
569 else if (i.firstChild != null)
575 function TocEntry(el, text, toclevel) {
578 this.toclevel = toclevel;
581 function tocEntries(el, toclevels) {
582 var result = new Array;
583 var re = new RegExp('[hH]([
1-'+(toclevels+
1)+'])');
584 // Function that scans the DOM tree for header elements (the DOM2
585 // nodeIterator API would be a better technique but not supported by all
587 var iterate = function (el) {
588 for (var i = el.firstChild; i != null; i = i.nextSibling) {
589 if (i.nodeType ==
1 /* Node.ELEMENT_NODE */) {
590 var mo = re.exec(i.tagName);
591 if (mo && (i.getAttribute(
"class") || i.getAttribute(
"className")) !=
"float") {
592 result[result.length] = new TocEntry(i, getText(i), mo[
1]-
1);
602 var toc = document.getElementById(
"toc");
607 // Delete existing TOC entries in case we're reloading the TOC.
608 var tocEntriesToRemove = [];
610 for (i =
0; i < toc.childNodes.length; i++) {
611 var entry = toc.childNodes[i];
612 if (entry.nodeName.toLowerCase() == 'div'
613 && entry.getAttribute(
"class")
614 && entry.getAttribute(
"class").match(/^toclevel/))
615 tocEntriesToRemove.push(entry);
617 for (i =
0; i < tocEntriesToRemove.length; i++) {
618 toc.removeChild(tocEntriesToRemove[i]);
621 // Rebuild TOC entries.
622 var entries = tocEntries(document.getElementById(
"content"), toclevels);
623 for (var i =
0; i < entries.length; ++i) {
624 var entry = entries[i];
625 if (entry.element.id ==
"")
626 entry.element.id =
"_toc_" + i;
627 var a = document.createElement(
"a");
628 a.href =
"#" + entry.element.id;
629 a.appendChild(document.createTextNode(entry.text));
630 var div = document.createElement(
"div");
632 div.className =
"toclevel" + entry.toclevel;
633 toc.appendChild(div);
635 if (entries.length ==
0)
636 toc.parentNode.removeChild(toc);
640 /////////////////////////////////////////////////////////////////////
641 // Footnotes generator
642 /////////////////////////////////////////////////////////////////////
644 /* Based on footnote generation code from:
645 * http://www.brandspankingnew.net/archive/
2005/
07/format_footnote.html
648 footnotes: function () {
649 // Delete existing footnote entries in case we're reloading the footnodes.
651 var noteholder = document.getElementById(
"footnotes");
655 var entriesToRemove = [];
656 for (i =
0; i < noteholder.childNodes.length; i++) {
657 var entry = noteholder.childNodes[i];
658 if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute(
"class") ==
"footnote")
659 entriesToRemove.push(entry);
661 for (i =
0; i < entriesToRemove.length; i++) {
662 noteholder.removeChild(entriesToRemove[i]);
665 // Rebuild footnote entries.
666 var cont = document.getElementById(
"content");
667 var spans = cont.getElementsByTagName(
"span");
670 for (i=
0; i
<spans.length; i++) {
671 if (spans[i].className ==
"footnote") {
673 var note = spans[i].getAttribute(
"data-note");
675 // Use [\s\S] in place of . so multi-line matches work.
676 // Because JavaScript has no s (dotall) regex flag.
677 note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[
1];
679 "[<a id='_footnoteref_" + n +
"' href='#_footnote_" + n +
680 "' title='View footnote' class='footnote'>" + n +
"</a>]";
681 spans[i].setAttribute(
"data-note", note);
683 noteholder.innerHTML +=
684 "<div class='footnote' id='_footnote_" + n +
"'>" +
685 "<a href='#_footnoteref_" + n +
"' title='Return to text'>" +
686 n +
"</a>. " + note +
"</div>";
687 var id =spans[i].getAttribute(
"id");
688 if (id != null) refs[
"#"+id] = n;
692 noteholder.parentNode.removeChild(noteholder);
694 // Process footnoterefs.
695 for (i=
0; i
<spans.length; i++) {
696 if (spans[i].className ==
"footnoteref") {
697 var href = spans[i].getElementsByTagName(
"a")[
0].getAttribute(
"href");
698 href = href.match(/#.*/)[
0]; // Because IE return full URL.
701 "[<a href='#_footnote_" + n +
702 "' title='View footnote' class='footnote'>" + n +
"</a>]";
708 install: function(toclevels) {
711 function reinstall() {
712 asciidoc.footnotes();
714 asciidoc.toc(toclevels);
718 function reinstallAndRemoveTimer() {
719 clearInterval(timerId);
723 timerId = setInterval(reinstall,
500);
724 if (document.addEventListener)
725 document.addEventListener(
"DOMContentLoaded", reinstallAndRemoveTimer, false);
727 window.onload = reinstallAndRemoveTimer;
735 <body class=
"manpage">
738 git-range-diff(
1) Manual Page
741 <div class=
"sectionbody">
743 Compare two commit ranges (e.g. two versions of a branch)
749 <h2 id=
"_synopsis">SYNOPSIS
</h2>
750 <div class=
"sectionbody">
751 <div class=
"verseblock">
752 <pre class=
"content"><em>git range-diff
</em> [--color=[
<when
>]] [--no-color] [
<diff-options
>]
753 [--no-dual-color] [--creation-factor=
<factor
>]
754 [--left-only | --right-only]
755 (
<range1
> <range2
> |
<rev1
>…<rev2
> |
<base
> <rev1
> <rev2
> )
756 [[--]
<path
>…]
</pre>
757 <div class=
"attribution">
762 <h2 id=
"_description">DESCRIPTION
</h2>
763 <div class=
"sectionbody">
764 <div class=
"paragraph"><p>This command shows the differences between two versions of a patch
765 series, or more generally, two commit ranges (ignoring merge commits).
</p></div>
766 <div class=
"paragraph"><p>In the presence of
<code><path
></code> arguments, these commit ranges are limited
767 accordingly.
</p></div>
768 <div class=
"paragraph"><p>To that end, it first finds pairs of commits from both commit ranges
769 that correspond with each other. Two commits are said to correspond when
770 the diff between their patches (i.e. the author information, the commit
771 message and the commit diff) is reasonably small compared to the
772 patches' size. See ``Algorithm`` below for details.
</p></div>
773 <div class=
"paragraph"><p>Finally, the list of matching commits is shown in the order of the
774 second commit range, with unmatched commits being inserted just after
775 all of their ancestors have been shown.
</p></div>
776 <div class=
"paragraph"><p>There are three ways to specify the commit ranges:
</p></div>
777 <div class=
"ulist"><ul>
780 <code><range1
> <range2
></code>: Either commit range can be of the form
781 <code><base
>..
<rev
></code>,
<code><rev
>^!
</code> or
<code><rev
>^-
<n
></code>. See
<code>SPECIFYING RANGES
</code>
782 in
<a href=
"gitrevisions.html">gitrevisions(
7)
</a> for more details.
787 <code><rev1
>...
<rev2
></code>. This is equivalent to
788 <code><rev2
>..
<rev1
> <rev1
>..
<rev2
></code>.
793 <code><base
> <rev1
> <rev2
></code>: This is equivalent to
<code><base
>..
<rev1
>
794 <base
>..
<rev2
></code>.
801 <h2 id=
"_options">OPTIONS
</h2>
802 <div class=
"sectionbody">
803 <div class=
"dlist"><dl>
809 When the commit diffs differ,
‘git range-diff` recreates the
810 original diffs
’ coloring, and adds outer -/+ diff markers with
811 the
<strong>background
</strong> being red/green to make it easier to see e.g.
812 when there was a change in what exact lines were added.
814 <div class=
"paragraph"><p>Additionally, the commit diff lines that are only present in the first commit
815 range are shown
"dimmed" (this can be overridden using the
<code>color.diff.
<slot
></code>
816 config setting where
<code><slot
></code> is one of
<code>contextDimmed
</code>,
<code>oldDimmed
</code> and
817 <code>newDimmed
</code>), and the commit diff lines that are only present in the second
818 commit range are shown in bold (which can be overridden using the config
819 settings
<code>color.diff.
<slot
></code> with
<code><slot
></code> being one of
<code>contextBold
</code>,
820 <code>oldBold
</code> or
<code>newBold
</code>).
</p></div>
821 <div class=
"paragraph"><p>This is known to
<code>range-diff
</code> as
"dual coloring". Use
<code>--no-dual-color
</code>
822 to revert to color all lines according to the outer diff markers
823 (and completely ignore the inner diff when it comes to color).
</p></div>
826 --creation-factor=
<percent
>
830 Set the creation/deletion cost fudge factor to
<code><percent
></code>.
831 Defaults to
60. Try a larger value if
<code>git range-diff
</code> erroneously
832 considers a large change a total rewrite (deletion of one commit
833 and addition of another), and a smaller one in the reverse case.
834 See the ``Algorithm`` section below for an explanation of why this is
843 Suppress commits that are missing from the first specified range
844 (or the
"left range" when using the
<code><rev1
>...
<rev2
></code> format).
852 Suppress commits that are missing from the second specified range
853 (or the
"right range" when using the
<code><rev1
>...
<rev2
></code> format).
857 --[no-]notes[=
<ref
>]
861 This flag is passed to the
<code>git log
</code> program
862 (see
<a href=
"git-log.html">git-log(
1)
</a>) that generates the patches.
866 <range1
> <range2
>
870 Compare the commits specified by the two ranges, where
871 <code><range1
></code> is considered an older version of
<code><range2
></code>.
875 <rev1
>…<rev2
>
879 Equivalent to passing
<code><rev2
>..
<rev1
></code> and
<code><rev1
>..
<rev2
></code>.
883 <base
> <rev1
> <rev2
>
887 Equivalent to passing
<code><base
>..
<rev1
></code> and
<code><base
>..
<rev2
></code>.
888 Note that
<code><base
></code> does not need to be the exact branch point
889 of the branches. Example: after rebasing a branch
<code>my-topic
</code>,
890 <code>git range-diff my-topic@{u} my-topic@{
1} my-topic
</code> would
891 show the differences introduced by the rebase.
895 <div class=
"paragraph"><p><code>git range-diff
</code> also accepts the regular diff options (see
896 <a href=
"git-diff.html">git-diff(
1)
</a>), most notably the
<code>--color=[
<when
>]
</code> and
897 <code>--no-color
</code> options. These options are used when generating the
"diff
898 between patches", i.e. to compare the author, commit message and diff of
899 corresponding old/new commits. There is currently no means to tweak most of the
900 diff options passed to
<code>git log
</code> when generating those patches.
</p></div>
904 <h2 id=
"_output_stability">OUTPUT STABILITY
</h2>
905 <div class=
"sectionbody">
906 <div class=
"paragraph"><p>The output of the
<code>range-diff
</code> command is subject to change. It is
907 intended to be human-readable porcelain output, not something that can
908 be used across versions of Git to get a textually stable
<code>range-diff
</code>
909 (as opposed to something like the
<code>--stable
</code> option to
910 <a href=
"git-patch-id.html">git-patch-id(
1)
</a>). There
’s also no equivalent of
911 <a href=
"git-apply.html">git-apply(
1)
</a> for
<code>range-diff
</code>, the output is not intended to
912 be machine-readable.
</p></div>
913 <div class=
"paragraph"><p>This is particularly true when passing in diff options. Currently some
914 options like
<code>--stat
</code> can, as an emergent effect, produce output
915 that
’s quite useless in the context of
<code>range-diff
</code>. Future versions
916 of
<code>range-diff
</code> may learn to interpret such options in a manner
917 specific to
<code>range-diff
</code> (e.g. for
<code>--stat
</code> producing human-readable
918 output which summarizes how the diffstat changed).
</p></div>
922 <h2 id=
"_configuration">CONFIGURATION
</h2>
923 <div class=
"sectionbody">
924 <div class=
"paragraph"><p>This command uses the
<code>diff.color.*
</code> and
<code>pager.range-diff
</code> settings
925 (the latter is on by default).
926 See
<a href=
"git-config.html">git-config(
1)
</a>.
</p></div>
930 <h2 id=
"_examples">EXAMPLES
</h2>
931 <div class=
"sectionbody">
932 <div class=
"paragraph"><p>When a rebase required merge conflicts to be resolved, compare the changes
933 introduced by the rebase directly afterwards using:
</p></div>
934 <div class=
"listingblock">
935 <div class=
"content">
936 <pre><code>$ git range-diff @{u} @{
1} @
</code></pre>
938 <div class=
"paragraph"><p>A typical output of
<code>git range-diff
</code> would look like this:
</p></div>
939 <div class=
"listingblock">
940 <div class=
"content">
941 <pre><code>-: -------
> 1:
0ddba11 Prepare for the inevitable!
942 1: c0debee =
2: cab005e Add a helpful message at the start
943 2: f00dbal !
3: decafe1 Describe a bug
945 Author: A U Thor
<author@example.com
>
947 -TODO: Describe a bug
952 -+What is unexpected is that it will also crash.
953 ++Unexpectedly, it also crashes. This is a bug, and the jury is
954 ++still out there how to fix it best. See ticket #
314 for details.
957 3: bedead
< -: ------- TO-UNDO
</code></pre>
959 <div class=
"paragraph"><p>In this example, there are
3 old and
3 new commits, where the developer
960 removed the
3rd, added a new one before the first two, and modified the
961 commit message of the
2nd commit as well as its diff.
</p></div>
962 <div class=
"paragraph"><p>When the output goes to a terminal, it is color-coded by default, just
963 like regular
<code>git diff
</code>'s output. In addition, the first line (adding a
964 commit) is green, the last line (deleting a commit) is red, the second
965 line (with a perfect match) is yellow like the commit header of
<code>git
966 show
</code>'s output, and the third line colors the old commit red, the new
967 one green and the rest like
<code>git show
</code>'s commit header.
</p></div>
968 <div class=
"paragraph"><p>A naive color-coded diff of diffs is actually a bit hard to read,
969 though, as it colors the entire lines red or green. The line that added
970 "What is unexpected" in the old commit, for example, is completely red,
971 even if the intent of the old commit was to add something.
</p></div>
972 <div class=
"paragraph"><p>To help with that,
<code>range
</code> uses the
<code>--dual-color
</code> mode by default. In
973 this mode, the diff of diffs will retain the original diff colors, and
974 prefix the lines with -/+ markers that have their
<strong>background
</strong> red or
975 green, to make it more obvious that they describe how the diff itself
980 <h2 id=
"_algorithm">Algorithm
</h2>
981 <div class=
"sectionbody">
982 <div class=
"paragraph"><p>The general idea is this: we generate a cost matrix between the commits
983 in both commit ranges, then solve the least-cost assignment.
</p></div>
984 <div class=
"paragraph"><p>The cost matrix is populated thusly: for each pair of commits, both
985 diffs are generated and the
"diff of diffs" is generated, with
3 context
986 lines, then the number of lines in that diff is used as cost.
</p></div>
987 <div class=
"paragraph"><p>To avoid false positives (e.g. when a patch has been removed, and an
988 unrelated patch has been added between two iterations of the same patch
989 series), the cost matrix is extended to allow for that, by adding
990 fixed-cost entries for wholesale deletes/adds.
</p></div>
991 <div class=
"paragraph"><p>Example: Let commits
<code>1--
2</code> be the first iteration of a patch series and
992 <code>A--C
</code> the second iteration. Let
’s assume that
<code>A
</code> is a cherry-pick of
993 <code>2,
</code> and
<code>C
</code> is a cherry-pick of
<code>1</code> but with a small modification (say,
994 a fixed typo). Visualize the commits as a bipartite graph:
</p></div>
995 <div class=
"listingblock">
996 <div class=
"content">
1003 <div class=
"paragraph"><p>We are looking for a
"best" explanation of the new series in terms of
1004 the old one. We can represent an
"explanation" as an edge in the graph:
</p></div>
1005 <div class=
"listingblock">
1006 <div class=
"content">
1013 <div class=
"paragraph"><p>This explanation comes for
"free" because there was no change. Similarly
1014 <code>C
</code> could be explained using
<code>1</code>, but that comes at some cost c
>0
1015 because of the modification:
</p></div>
1016 <div class=
"listingblock">
1017 <div class=
"content">
1018 <pre><code> 1 ----. A
1025 <div class=
"paragraph"><p>In mathematical terms, what we are looking for is some sort of a minimum
1026 cost bipartite matching;
‘1` is matched to
<code>C
</code> at some cost, etc. The
1027 underlying graph is in fact a complete bipartite graph; the cost we
1028 associate with every edge is the size of the diff between the two
1029 commits
’ patches. To explain also new commits, we introduce dummy nodes
1030 on both sides:
</p></div>
1031 <div class=
"listingblock">
1032 <div class=
"content">
1033 <pre><code> 1 ----. A
1043 <div class=
"paragraph"><p>The cost of an edge
<code>o--C
</code> is the size of
<code>C
</code>'s diff, modified by a
1044 fudge factor that should be smaller than
100%. The cost of an edge
1045 <code>o--o
</code> is free. The fudge factor is necessary because even if
<code>1</code> and
1046 <code>C
</code> have nothing in common, they may still share a few empty lines and
1047 such, possibly making the assignment
<code>1--C
</code>,
<code>o--o
</code> slightly cheaper
1048 than
<code>1--o
</code>,
<code>o--C
</code> even if
<code>1</code> and
<code>C
</code> have nothing in common. With the
1049 fudge factor we require a much larger common part to consider patches as
1050 corresponding.
</p></div>
1051 <div class=
"paragraph"><p>The overall time needed to compute this algorithm is the time needed to
1052 compute n+m commit diffs and then n*m diffs of patches, plus the time
1053 needed to compute the least-cost assignment between n and m diffs. Git
1054 uses an implementation of the Jonker-Volgenant algorithm to solve the
1055 assignment problem, which has cubic runtime complexity. The matching
1056 found in this case will look like this:
</p></div>
1057 <div class=
"listingblock">
1058 <div class=
"content">
1059 <pre><code> 1 ----. A
1067 o ---------- o
</code></pre>
1072 <h2 id=
"_see_also">SEE ALSO
</h2>
1073 <div class=
"sectionbody">
1074 <div class=
"paragraph"><p><a href=
"git-log.html">git-log(
1)
</a></p></div>
1078 <h2 id=
"_git">GIT
</h2>
1079 <div class=
"sectionbody">
1080 <div class=
"paragraph"><p>Part of the
<a href=
"git.html">git(
1)
</a> suite
</p></div>
1084 <div id=
"footnotes"><hr /></div>
1086 <div id=
"footer-text">
1088 2023-
10-
29 16:
42:
00 PDT