Fix the rename detection limit checking

This adds more proper rename detection limits. Instead of just checking
the limit against the number of potential rename destinations, we verify
that the rename matrix (which is what really matters) doesn't grow
ridiculously large, and we also make sure that we don't overflow when
doing the matrix size calculation.

This also changes the default limits from unlimited, to a rename matrix
that is limited to 100 entries on a side. You can raise it with the config
entry, or by using the "-l<n>" command line flag, but at least the default
is now a sane number that avoids spending lots of time (and memory) in
situations that likely don't merit it.

The choice of default value is of course very debatable. Limiting the
rename matrix to a 100x100 size will mean that even if you have just one
obvious rename, but you also create (or delete) 10,000 files, the rename
matrix will be so big that we disable the heuristics. Sounds reasonable to
me, but let's see if people hit this (and, perhaps more importantly,
actually *care*) in real life.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/diff.c b/diff.c
index 1aca5df522d1c5249c9d1ce8d030849d59a5eb6a..0ee9ea1c1b47b82710a3850e7e9f679e4486f7bd 100644 (file)
--- a/diff.c
+++ b/diff.c
@@ -17,7 +17,7 @@
 #endif
 
 static int diff_detect_rename_default;
 #endif
 
 static int diff_detect_rename_default;

-static int diff_rename_limit_default = -1;
+static int diff_rename_limit_default = 100;

 static int diff_use_color_default;
 int diff_auto_refresh_index = 1;
 
 static int diff_use_color_default;
 int diff_auto_refresh_index = 1;
 

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 6bde4396f212833cc1d411e723d5215c086e7c2d..41b35c3a9e6935f6cd8563de732321e74e115765 100644 (file)
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -298,10 +298,25 @@ void diffcore_rename(struct diff_options *options)
                else if (detect_rename == DIFF_DETECT_COPY)
                        register_rename_src(p->one, 1, p->score);
        }
                else if (detect_rename == DIFF_DETECT_COPY)
                        register_rename_src(p->one, 1, p->score);
        }

-       if (rename_dst_nr == 0 || rename_src_nr == 0 ||
-           (0 < rename_limit && rename_limit < rename_dst_nr))
+       if (rename_dst_nr == 0 || rename_src_nr == 0)

                goto cleanup; /* nothing to do */
 
                goto cleanup; /* nothing to do */
 

+       /*
+        * This basically does a test for the rename matrix not
+        * growing larger than a "rename_limit" square matrix, ie:
+        *
+        *    rename_dst_nr * rename_src_nr > rename_limit * rename_limit
+        *
+        * but handles the potential overflow case specially (and we
+        * assume at least 32-bit integers)
+        */
+       if (rename_limit <= 0 || rename_limit > 32767)
+               rename_limit = 32767;
+       if (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)
+               goto cleanup;
+       if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)
+               goto cleanup;
+

        /* We really want to cull the candidates list early
         * with cheap tests in order to avoid doing deltas.
         * The first round matches up the up-to-date entries,
        /* We really want to cull the candidates list early
         * with cheap tests in order to avoid doing deltas.
         * The first round matches up the up-to-date entries,

diff --git a/wt-status.c b/wt-status.c
index 52054201c2a8729e036a5d97337a5f85bcafc782..10ce6eedc7e8adbcc3b12e1987d2e16b532a4e07 100644 (file)
--- a/wt-status.c
+++ b/wt-status.c
@@ -227,6 +227,7 @@ static void wt_status_print_updated(struct wt_status *s)
        rev.diffopt.format_callback = wt_status_print_updated_cb;
        rev.diffopt.format_callback_data = s;
        rev.diffopt.detect_rename = 1;
        rev.diffopt.format_callback = wt_status_print_updated_cb;
        rev.diffopt.format_callback_data = s;
        rev.diffopt.detect_rename = 1;

+       rev.diffopt.rename_limit = 100;

        wt_read_cache(s);
        run_diff_index(&rev, 1);
 }
        wt_read_cache(s);
        run_diff_index(&rev, 1);
 }