Subject: [PATCH v3 0/4] Rename/copy limits -- docs, warnings, and new defaults

From: "Elijah Newren via GitGitGadget" <[email-masked]>
Date: Thu, 15 Jul 2021 00:45:20 +0000

Fix a few small issues with documentation and warnings around the limits for
the quadratic portion of rename (&copy) detection, and bump the default
limits.

Discussion on bumping the limits can be found at [1]. Although it appears we
generally agree we could switch to an unlimited setting for
merge.renameLimit, that would require some changes to progress bars to
notify users how to take action once things start taking a while. So, for
now, just bump the limits.

[1]
https://lore.kernel.org/git/CABPp-BFzp3TCWiF1QAVSfywDLYrz=[email-masked]/T/#u

Changes since v2:

 * Change the meaning of "0" to actually mean unlimited, and modify the
   documentation to mention that.
 * Added 'currently' to descriptions to make it clear the defaults are
   likely to change (again).
 * Added a brief explanation of the exhaustive portion of rename detection,
   as requested by Ævar (though, honestly, I think the thing that actually
   helps people pick values for the limit is the warning that tells people
   that rename detection was skipped and how high they need to set the limit
   if they want to redo the operation and get renames).

Changes since v1:

 * Shuffled patch order since the explanation of why "inexact rename
   detection" is incorrect was in the third patch
 * Use the term "exhaustive rename detection" for the quadratic portion
 * Simplify -l description by just stating that it defaults to
   diff.renameLimit (since it in turn has the right default value)
 * Fix asciidoc formating
 * Include bump of the limits in a new patch

Elijah Newren (4):
  diff: correct warning message when renameLimit exceeded
  doc: clarify documentation for rename/copy limits
  diffcore-rename: treat a rename_limit of 0 as unlimited
  Bump rename limit defaults (yet again)

 Documentation/config/diff.txt  |  7 ++++---
 Documentation/config/merge.txt | 10 ++++++----
 Documentation/diff-options.txt | 16 +++++++++++-----
 diff.c                         |  4 ++--
 diffcore-rename.c              |  2 +-
 merge-ort.c                    |  2 +-
 merge-recursive.c              |  2 +-
 7 files changed, 26 insertions(+), 17 deletions(-)

base-commit: d486ca60a51c9cb1fe068803c3f540724e95e83a
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1044%2Fnewren%2Frename-limit-documentation-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1044/newren/rename-limit-documentation-v3
Pull-Request: https://github.com/git/git/pull/1044

Range-diff vs v2:

 1:  0d1d0f180a3 = 1:  0d1d0f180a3 diff: correct warning message when renameLimit exceeded
 2:  4046993a9a2 ! 2:  193385d7ca1 doc: clarify documentation for rename/copy limits
     @@ Documentation/config/diff.txt: diff.orderFile::
      -	has no effect if rename detection is turned off.
      +	The number of files to consider in the exhaustive portion of
      +	copy/rename detection; equivalent to the 'git diff' option
     -+	`-l`.  If not set, the default value is 400.  This setting has
     -+	no effect if rename detection is turned off.
     ++	`-l`.  If not set, the default value is currently 400.  This
     ++	setting has no effect if rename detection is turned off.
       
       diff.renames::
       	Whether and how Git detects renames.  If set to "false",
     @@ Documentation/config/merge.txt: merge.verifySignatures::
      +	The number of files to consider in the exhaustive portion of
      +	rename detection during a merge.  If not specified, defaults
      +	to the value of diff.renameLimit.  If neither
     -+	merge.renameLimit nor diff.renameLimit are specified, defaults
     -+	to 1000.  This setting has no effect if rename detection is
     -+	turned off.
     ++	merge.renameLimit nor diff.renameLimit are specified,
     ++	currently defaults to 1000.  This setting has no effect if
     ++	rename detection is turned off.
       
       merge.renames::
       	Whether Git detects renames.  If set to "false", rename detection
     @@ Documentation/diff-options.txt: When used together with `-B`, omit also the prei
      -	The `-M` and `-C` options require O(n^2) processing time where n
      -	is the number of potential rename/copy targets.  This
      -	option prevents rename/copy detection from running if
     -+	The `-M` and `-C` options have an exhaustive portion that
     -+	requires O(n^2) processing time where n is the number of
     -+	potential rename/copy targets.  This option prevents the
     -+	exhaustive portion of rename/copy detection from running if
     - 	the number of rename/copy targets exceeds the specified
     +-	the number of rename/copy targets exceeds the specified
      -	number.
     -+	number.  Defaults to diff.renameLimit.
     ++	The `-M` and `-C` options involve some preliminary steps that
     ++	can detect subsets of renames/copies cheaply, followed by an
     ++	exhaustive fallback portion that compares all remaining
     ++	unpaired destinations to all relevant sources.  (For renames,
     ++	only remaining unpaired sources are relevant; for copies, all
     ++	original sources are relevant.)  For N sources and
     ++	destinations, this exhaustive check is O(N^2).  This option
     ++	prevents the exhaustive portion of rename/copy detection from
     ++	running if the number of source/destination files involved
     ++	exceeds the specified number.  Defaults to diff.renameLimit.
       
       ifndef::git-format-patch[]
       --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::
 3:  6f5767607cd ! 3:  00a2072baea doc: document the special handling of -l0
     @@ Metadata
      Author: Elijah Newren <[email-masked]>
      
       ## Commit message ##
     -    doc: document the special handling of -l0
     +    diffcore-rename: treat a rename_limit of 0 as unlimited
      
     -    As noted in commit 89973554b52c (diffcore-rename: make diff-tree -l0
     -    mean -l<large>, 2017-11-29), -l0 has had a magical special "large"
     -    historical value associated with it.  Document this value, particularly
     -    since it is not large enough for some uses -- see commit 9f7e4bfa3b6d
     -    (diff: remove silent clamp of renameLimit, 2017-11-13).
     +    In commit 89973554b52c (diffcore-rename: make diff-tree -l0 mean
     +    -l<large>, 2017-11-29), -l0 was given a special magical "large" value,
     +    but one which was not large enough for some uses (as can be seen from
     +    commit 9f7e4bfa3b6d (diff: remove silent clamp of renameLimit,
     +    2017-11-13).  Make 0 (or a negative value) be treated as unlimited
     +    instead and update the documentation to mention this.
      
          Signed-off-by: Elijah Newren <[email-masked]>
      
       ## Documentation/diff-options.txt ##
      @@ Documentation/diff-options.txt: of a delete/create pair.
     - 	exhaustive portion of rename/copy detection from running if
     - 	the number of rename/copy targets exceeds the specified
     - 	number.  Defaults to diff.renameLimit.
     -++
     -+Note that for backward compatibility reasons, a value of 0 is treated
     -+the same as if a large value was passed (currently, 32767).
     + 	prevents the exhaustive portion of rename/copy detection from
     + 	running if the number of source/destination files involved
     + 	exceeds the specified number.  Defaults to diff.renameLimit.
     ++	Note that a value of 0 is treated as unlimited.
       
       ifndef::git-format-patch[]
       --diff-filter=[(A|C|D|M|R|T|U|X|B)...[*]]::
     +
     + ## diffcore-rename.c ##
     +@@ diffcore-rename.c: static int too_many_rename_candidates(int num_destinations, int num_sources,
     + 	 * memory for the matrix anyway.
     + 	 */
     + 	if (rename_limit <= 0)
     +-		rename_limit = 32767;
     ++		return 0; /* treat as unlimited */
     + 	if (st_mult(num_destinations, num_sources)
     + 	    <= st_mult(rename_limit, rename_limit))
     + 		return 0;
 4:  8f1deb6dd16 ! 4:  b41278b6680 Bump rename limit defaults (yet again)
     @@ Documentation/config/diff.txt: diff.orderFile::
       diff.renameLimit::
       	The number of files to consider in the exhaustive portion of
       	copy/rename detection; equivalent to the 'git diff' option
     --	`-l`.  If not set, the default value is 400.  This setting has
     -+	`-l`.  If not set, the default value is 1000.  This setting has
     - 	no effect if rename detection is turned off.
     +-	`-l`.  If not set, the default value is currently 400.  This
     ++	`-l`.  If not set, the default value is currently 1000.  This
     + 	setting has no effect if rename detection is turned off.
       
       diff.renames::
      
     @@ Documentation/config/merge.txt
      @@ Documentation/config/merge.txt: merge.renameLimit::
       	rename detection during a merge.  If not specified, defaults
       	to the value of diff.renameLimit.  If neither
     - 	merge.renameLimit nor diff.renameLimit are specified, defaults
     --	to 1000.  This setting has no effect if rename detection is
     -+	to 7000.  This setting has no effect if rename detection is
     - 	turned off.
     + 	merge.renameLimit nor diff.renameLimit are specified,
     +-	currently defaults to 1000.  This setting has no effect if
     ++	currently defaults to 7000.  This setting has no effect if
     + 	rename detection is turned off.
       
       merge.renames::

-- 
gitgitgadget