diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | diff.c | 2 | ||||
| -rw-r--r-- | merge-recursive.c | 2 | ||||
| -rw-r--r-- | t/lib-diff-alternative.sh | 165 | ||||
| -rwxr-xr-x | t/t4033-diff-patience.sh | 162 | ||||
| -rwxr-xr-x | t/t4050-diff-histogram.sh | 12 | ||||
| -rw-r--r-- | xdiff/xdiff.h | 2 | ||||
| -rw-r--r-- | xdiff/xdiffi.c | 3 | ||||
| -rw-r--r-- | xdiff/xdiffi.h | 2 | ||||
| -rw-r--r-- | xdiff/xhistogram.c | 363 | ||||
| -rw-r--r-- | xdiff/xpatience.c | 27 | ||||
| -rw-r--r-- | xdiff/xprepare.c | 143 | ||||
| -rw-r--r-- | xdiff/xutils.c | 51 | ||||
| -rw-r--r-- | xdiff/xutils.h | 4 |
14 files changed, 655 insertions, 285 deletions
@@ -1876,7 +1876,7 @@ ifndef NO_CURL GIT_OBJS += http.o http-walker.o remote-curl.o endif XDIFF_OBJS = xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o \ - xdiff/xmerge.o xdiff/xpatience.o + xdiff/xmerge.o xdiff/xpatience.o xdiff/xhistogram.o VCSSVN_OBJS = vcs-svn/string_pool.o vcs-svn/line_buffer.o \ vcs-svn/repo_tree.o vcs-svn/fast_export.o vcs-svn/svndump.o VCSSVN_TEST_OBJS = test-obj-pool.o test-string-pool.o \ @@ -3393,6 +3393,8 @@ int diff_opt_parse(struct diff_options *options, const char **av, int ac) DIFF_XDL_SET(options, IGNORE_WHITESPACE_AT_EOL); else if (!strcmp(arg, "--patience")) DIFF_XDL_SET(options, PATIENCE_DIFF); + else if (!strcmp(arg, "--histogram")) + DIFF_XDL_SET(options, HISTOGRAM_DIFF); /* flags options */ else if (!strcmp(arg, "--binary")) { diff --git a/merge-recursive.c b/merge-recursive.c index db9ba19ddf..0cc1e6fc14 100644 --- a/merge-recursive.c +++ b/merge-recursive.c @@ -1759,6 +1759,8 @@ int parse_merge_opt(struct merge_options *o, const char *s) o->subtree_shift = s + strlen("subtree="); else if (!strcmp(s, "patience")) o->xdl_opts |= XDF_PATIENCE_DIFF; + else if (!strcmp(s, "histogram")) + o->xdl_opts |= XDF_HISTOGRAM_DIFF; else if (!strcmp(s, "ignore-space-change")) o->xdl_opts |= XDF_IGNORE_WHITESPACE_CHANGE; else if (!strcmp(s, "ignore-all-space")) diff --git a/t/lib-diff-alternative.sh b/t/lib-diff-alternative.sh new file mode 100644 index 0000000000..75ffd9174f --- /dev/null +++ b/t/lib-diff-alternative.sh @@ -0,0 +1,165 @@ +#!/bin/sh + +test_diff_frobnitz() { + cat >file1 <<\EOF +#include <stdio.h> + +// Frobs foo heartily +int frobnitz(int foo) +{ + int i; + for(i = 0; i < 10; i++) + { + printf("Your answer is: "); + printf("%d\n", foo); + } +} + +int fact(int n) +{ + if(n > 1) + { + return fact(n-1) * n; + } + return 1; +} + +int main(int argc, char **argv) +{ + frobnitz(fact(10)); +} +EOF + + cat >file2 <<\EOF +#include <stdio.h> + +int fib(int n) +{ + if(n > 2) + { + return fib(n-1) + fib(n-2); + } + return 1; +} + +// Frobs foo heartily +int frobnitz(int foo) +{ + int i; + for(i = 0; i < 10; i++) + { + printf("%d\n", foo); + } +} + +int main(int argc, char **argv) +{ + frobnitz(fib(10)); +} +EOF + + cat >expect <<\EOF +diff --git a/file1 b/file2 +index 6faa5a3..e3af329 100644 +--- a/file1 ++++ b/file2 +@@ -1,26 +1,25 @@ + #include <stdio.h> + ++int fib(int n) ++{ ++ if(n > 2) ++ { ++ return fib(n-1) + fib(n-2); ++ } ++ return 1; ++} ++ + // Frobs foo heartily + int frobnitz(int foo) + { + int i; + for(i = 0; i < 10; i++) + { +- printf("Your answer is: "); + printf("%d\n", foo); + } + } + +-int fact(int n) +-{ +- if(n > 1) +- { +- return fact(n-1) * n; +- } +- return 1; +-} +- + int main(int argc, char **argv) + { +- frobnitz(fact(10)); ++ frobnitz(fib(10)); + } +EOF + + STRATEGY=$1 + + test_expect_success "$STRATEGY diff" ' + test_must_fail git diff --no-index "--$STRATEGY" file1 file2 > output && + test_cmp expect output + ' + + test_expect_success "$STRATEGY diff output is valid" ' + mv file2 expect && + git apply < output && + test_cmp expect file2 + ' +} + +test_diff_unique() { + cat >uniq1 <<\EOF +1 +2 +3 +4 +5 +6 +EOF + + cat >uniq2 <<\EOF +a +b +c +d +e +f +EOF + + cat >expect <<\EOF +diff --git a/uniq1 b/uniq2 +index b414108..0fdf397 100644 +--- a/uniq1 ++++ b/uniq2 +@@ -1,6 +1,6 @@ +-1 +-2 +-3 +-4 +-5 +-6 ++a ++b ++c ++d ++e ++f +EOF + + STRATEGY=$1 + + test_expect_success 'completely different files' ' + test_must_fail git diff --no-index "--$STRATEGY" uniq1 uniq2 > output && + test_cmp expect output + ' +} + diff --git a/t/t4033-diff-patience.sh b/t/t4033-diff-patience.sh index 1eb14989df..3c9932edf3 100755 --- a/t/t4033-diff-patience.sh +++ b/t/t4033-diff-patience.sh @@ -3,166 +3,10 @@ test_description='patience diff algorithm' . ./test-lib.sh +. "$TEST_DIRECTORY"/lib-diff-alternative.sh -cat >file1 <<\EOF -#include <stdio.h> +test_diff_frobnitz "patience" -// Frobs foo heartily -int frobnitz(int foo) -{ - int i; - for(i = 0; i < 10; i++) - { - printf("Your answer is: "); - printf("%d\n", foo); - } -} - -int fact(int n) -{ - if(n > 1) - { - return fact(n-1) * n; - } - return 1; -} - -int main(int argc, char **argv) -{ - frobnitz(fact(10)); -} -EOF - -cat >file2 <<\EOF -#include <stdio.h> - -int fib(int n) -{ - if(n > 2) - { - return fib(n-1) + fib(n-2); - } - return 1; -} - -// Frobs foo heartily -int frobnitz(int foo) -{ - int i; - for(i = 0; i < 10; i++) - { - printf("%d\n", foo); - } -} - -int main(int argc, char **argv) -{ - frobnitz(fib(10)); -} -EOF - -cat >expect <<\EOF -diff --git a/file1 b/file2 -index 6faa5a3..e3af329 100644 ---- a/file1 -+++ b/file2 -@@ -1,26 +1,25 @@ - #include <stdio.h> - -+int fib(int n) -+{ -+ if(n > 2) -+ { -+ return fib(n-1) + fib(n-2); -+ } -+ return 1; -+} -+ - // Frobs foo heartily - int frobnitz(int foo) - { - int i; - for(i = 0; i < 10; i++) - { -- printf("Your answer is: "); - printf("%d\n", foo); - } - } - --int fact(int n) --{ -- if(n > 1) -- { -- return fact(n-1) * n; -- } -- return 1; --} -- - int main(int argc, char **argv) - { -- frobnitz(fact(10)); -+ frobnitz(fib(10)); - } -EOF - -test_expect_success 'patience diff' ' - - test_must_fail git diff --no-index --patience file1 file2 > output && - test_cmp expect output - -' - -test_expect_success 'patience diff output is valid' ' - - mv file2 expect && - git apply < output && - test_cmp expect file2 - -' - -cat >uniq1 <<\EOF -1 -2 -3 -4 -5 -6 -EOF - -cat >uniq2 <<\EOF -a -b -c -d -e -f -EOF - -cat >expect <<\EOF -diff --git a/uniq1 b/uniq2 -index b414108..0fdf397 100644 ---- a/uniq1 -+++ b/uniq2 -@@ -1,6 +1,6 @@ --1 --2 --3 --4 --5 --6 -+a -+b -+c -+d -+e -+f -EOF - -test_expect_success 'completely different files' ' - - test_must_fail git diff --no-index --patience uniq1 uniq2 > output && - test_cmp expect output - -' +test_diff_unique "patience" test_done diff --git a/t/t4050-diff-histogram.sh b/t/t4050-diff-histogram.sh new file mode 100755 index 0000000000..fd3e86a74f --- /dev/null +++ b/t/t4050-diff-histogram.sh @@ -0,0 +1,12 @@ +#!/bin/sh + +test_description='histogram diff algorithm' + +. ./test-lib.sh +. "$TEST_DIRECTORY"/lib-diff-alternative.sh + +test_diff_frobnitz "histogram" + +test_diff_unique "histogram" + +test_done diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 711048ea36..4beb10c678 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -33,6 +33,7 @@ extern "C" { #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3) #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4) #define XDF_PATIENCE_DIFF (1 << 5) +#define XDF_HISTOGRAM_DIFF (1 << 6) #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL) #define XDL_PATCH_NORMAL '-' @@ -105,7 +106,6 @@ typedef struct s_bdiffparam { #define xdl_realloc(ptr,x) realloc(ptr,x) void *xdl_mmfile_first(mmfile_t *mmf, long *size); -void *xdl_mmfile_next(mmfile_t *mmf, long *size); long xdl_mmfile_size(mmfile_t *mmf); int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index da67c04357..75a3922750 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -331,6 +331,9 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, if (xpp->flags & XDF_PATIENCE_DIFF) return xdl_do_patience_diff(mf1, mf2, xpp, xe); + if (xpp->flags & XDF_HISTOGRAM_DIFF) + return xdl_do_histogram_diff(mf1, mf2, xpp, xe); + if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) { return -1; diff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h index ad033a8e6a..7a92ea9c4d 100644 --- a/xdiff/xdiffi.h +++ b/xdiff/xdiffi.h @@ -57,5 +57,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, xdemitconf_t const *xecfg); int xdl_do_patience_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdfenv_t *env); +int xdl_do_histogram_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, + xdfenv_t *env); #endif /* #if !defined(XDIFFI_H) */ diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c new file mode 100644 index 0000000000..18f6f997c3 --- /dev/null +++ b/xdiff/xhistogram.c @@ -0,0 +1,363 @@ +/* + * Copyright (C) 2010, Google Inc. + * and other copyright owners as documented in JGit's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "xinclude.h" +#include "xtypes.h" +#include "xdiff.h" + +#define MAX_PTR UINT_MAX +#define MAX_CNT UINT_MAX + +#define LINE_END(n) (line##n + count##n - 1) +#define LINE_END_PTR(n) (*line##n + *count##n - 1) + +struct histindex { + struct record { + unsigned int ptr, cnt; + struct record *next; + } **records, /* an ocurrence */ + **line_map; /* map of line to record chain */ + chastore_t rcha; + unsigned int *next_ptrs; + unsigned int table_bits, + records_size, + line_map_size; + + unsigned int max_chain_length, + key_shift, + ptr_shift; + + unsigned int cnt, + has_common; + + xdfenv_t *env; + xpparam_t const *xpp; +}; + +struct region { + unsigned int begin1, end1; + unsigned int begin2, end2; +}; + +#define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift]) + +#define NEXT_PTR(index, ptr) \ + (index->next_ptrs[(ptr) - index->ptr_shift]) + +#define CNT(index, ptr) \ + ((LINE_MAP(index, ptr))->cnt) + +#define REC(env, s, l) \ + (env->xdf##s.recs[l - 1]) + +static int cmp_recs(xpparam_t const *xpp, + xrecord_t *r1, xrecord_t *r2) +{ + return r1->ha == r2->ha && + xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size, + xpp->flags); +} + +#define CMP_ENV(xpp, env, s1, l1, s2, l2) \ + (cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2))) + +#define CMP(i, s1, l1, s2, l2) \ + (cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2))) + +#define TABLE_HASH(index, side, line) \ + XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits) + +static int scanA(struct histindex *index, int line1, int count1) +{ + unsigned int ptr, tbl_idx; + unsigned int chain_len; + struct record **rec_chain, *rec; + + for (ptr = LINE_END(1); line1 <= ptr; ptr--) { + tbl_idx = TABLE_HASH(index, 1, ptr); + rec_chain = index->records + tbl_idx; + rec = *rec_chain; + + chain_len = 0; + while (rec) { + if (CMP(index, 1, rec->ptr, 1, ptr)) { + /* + * ptr is identical to another element. Insert + * it onto the front of the existing element + * chain. + */ + NEXT_PTR(index, ptr) = rec->ptr; + rec->ptr = ptr; + /* cap rec->cnt at MAX_CNT */ + rec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1); + LINE_MAP(index, ptr) = rec; + goto continue_scan; + } + + rec = rec->next; + chain_len++; + } + + if (chain_len == index->max_chain_length) + return -1; + + /* + * This is the first time we have ever seen this particular + * element in the sequence. Construct a new chain for it. + */ + if (!(rec = xdl_cha_alloc(&index->rcha))) + return -1; + rec->ptr = ptr; + rec->cnt = 1; + rec->next = *rec_chain; + *rec_chain = rec; + LINE_MAP(index, ptr) = rec; + +continue_scan: + ; /* no op */ + } + + return 0; +} + +static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr, + int line1, int count1, int line2, int count2) +{ + unsigned int b_next = b_ptr + 1; + struct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)]; + unsigned int as, ae, bs, be, np, rc; + int should_break; + + for (; rec; rec = rec->next) { + if (rec->cnt > index->cnt) { + if (!index->has_common) + index->has_common = CMP(index, 1, rec->ptr, 2, b_ptr); + continue; + } + + as = rec->ptr; + if (!CMP(index, 1, as, 2, b_ptr)) + continue; + + index->has_common = 1; + for (;;) { + should_break = 0; + np = NEXT_PTR(index, as); + bs = b_ptr; + ae = as; + be = bs; + rc = rec->cnt; + + while (line1 < as && line2 < bs + && CMP(index, 1, as - 1, 2, bs - 1)) { + as--; + bs--; + if (1 < rc) + rc = XDL_MIN(rc, CNT(index, as)); + } + while (ae < LINE_END(1) && be < LINE_END(2) + && CMP(index, 1, ae + 1, 2, be + 1)) { + ae++; + be++; + if (1 < rc) + rc = XDL_MIN(rc, CNT(index, ae)); + } + + if (b_next <= be) + b_next = be + 1; + if (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) { + lcs->begin1 = as; + lcs->begin2 = bs; + lcs->end1 = ae; + lcs->end2 = be; + index->cnt = rc; + } + + if (np == 0) + break; + + while (np <= ae) { + np = NEXT_PTR(index, np); + if (np == 0) { + should_break = 1; + break; + } + } + + if (should_break) + break; + + as = np; + } + } + return b_next; +} + +static int find_lcs(struct histindex *index, struct region *lcs, + int line1, int count1, int line2, int count2) { + int b_ptr; + + if (scanA(index, line1, count1)) + return -1; + + index->cnt = index->max_chain_length + 1; + + for (b_ptr = line2; b_ptr <= LINE_END(2); ) + b_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2); + + return index->has_common && index->max_chain_length < index->cnt; +} + +static int fall_back_to_classic_diff(struct histindex *index, + int line1, int count1, int line2, int count2) +{ + xpparam_t xpp; + xpp.flags = index->xpp->flags & ~XDF_HISTOGRAM_DIFF; + + return xdl_fall_back_diff(index->env, &xpp, + line1, count1, line2, count2); +} + +static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env, + int line1, int count1, int line2, int count2) +{ + struct histindex index; + struct region lcs; + int sz; + int result = -1; + + if (count1 <= 0 && count2 <= 0) + return 0; + + if (LINE_END(1) >= MAX_PTR) + return -1; + + if (!count1) { + while(count2--) + env->xdf2.rchg[line2++ - 1] = 1; + return 0; + } else if (!count2) { + while(count1--) + env->xdf1.rchg[line1++ - 1] = 1; + return 0; + } + + memset(&index, 0, sizeof(index)); + + index.env = env; + index.xpp = xpp; + + index.records = NULL; + index.line_map = NULL; + /* in case of early xdl_cha_free() */ + index.rcha.head = NULL; + + index.table_bits = xdl_hashbits(count1); + sz = index.records_size = 1 << index.table_bits; + sz *= sizeof(struct record *); + if (!(index.records = (struct record **) xdl_malloc(sz))) + goto cleanup; + memset(index.records, 0, sz); + + sz = index.line_map_size = count1; + sz *= sizeof(struct record *); + if (!(index.line_map = (struct record **) xdl_malloc(sz))) + goto cleanup; + memset(index.line_map, 0, sz); + + sz = index.line_map_size; + sz *= sizeof(unsigned int); + if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz))) + goto cleanup; + memset(index.next_ptrs, 0, sz); + + /* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */ + if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0) + goto cleanup; + + index.ptr_shift = line1; + index.max_chain_length = 64; + + memset(&lcs, 0, sizeof(lcs)); + if (find_lcs(&index, &lcs, line1, count1, line2, count2)) + result = fall_back_to_classic_diff(&index, line1, count1, line2, count2); + else { + if (lcs.begin1 == 0 && lcs.begin2 == 0) { + while (count1--) + env->xdf1.rchg[line1++ - 1] = 1; + while (count2--) + env->xdf2.rchg[line2++ - 1] = 1; + result = 0; + } else { + result = histogram_diff(xpp, env, + line1, lcs.begin1 - line1, + line2, lcs.begin2 - line2); + if (result) + goto cleanup; + result = histogram_diff(xpp, env, + lcs.end1 + 1, LINE_END(1) - lcs.end1, + lcs.end2 + 1, LINE_END(2) - lcs.end2); + if (result) + goto cleanup; + } + } + +cleanup: + xdl_free(index.records); + xdl_free(index.line_map); + xdl_free(index.next_ptrs); + xdl_cha_free(&index.rcha); + + return result; +} + +int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2, + xpparam_t const *xpp, xdfenv_t *env) +{ + if (xdl_prepare_env(file1, file2, xpp, env) < 0) + return -1; + + return histogram_diff(xpp, env, + env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1, + env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1); +} diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index e42c16a807..fdd7d0263f 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -287,34 +287,11 @@ static int walk_common_sequence(struct hashmap *map, struct entry *first, static int fall_back_to_classic_diff(struct hashmap *map, int line1, int count1, int line2, int count2) { - /* - * This probably does not work outside Git, since - * we have a very simple mmfile structure. - * - * Note: ideally, we would reuse the prepared environment, but - * the libxdiff interface does not (yet) allow for diffing only - * ranges of lines instead of the whole files. - */ - mmfile_t subfile1, subfile2; xpparam_t xpp; - xdfenv_t env; - - subfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr; - subfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr + - map->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr; - subfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr; - subfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr + - map->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr; xpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF; - if (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0) - return -1; - memcpy(map->env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1); - memcpy(map->env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2); - - xdl_free_env(&env); - - return 0; + return xdl_fall_back_diff(map->env, &xpp, + line1, count1, line2, count2); } /* diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index 05a8f01f38..eba31ffaee 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -26,6 +26,8 @@ #define XDL_KPDIS_RUN 4 #define XDL_MAX_EQLIMIT 1024 #define XDL_SIMSCAN_WINDOW 100 +#define XDL_GUESS_NLINES1 256 +#define XDL_GUESS_NLINES2 20 typedef struct s_xdlclass { @@ -67,8 +69,6 @@ static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2 static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) { - long i; - cf->flags = flags; cf->hbits = xdl_hashbits((unsigned int) size); @@ -83,8 +83,7 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) { xdl_cha_free(&cf->ncha); return -1; } - for (i = 0; i < cf->hsize; i++) - cf->rchash[i] = NULL; + memset(cf->rchash, 0, cf->hsize * sizeof(xdlclass_t *)); cf->alloc = size; if (!(cf->rcrecs = (xdlclass_t **) xdl_malloc(cf->alloc * sizeof(xdlclass_t *)))) { @@ -161,7 +160,7 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp, xdlclassifier_t *cf, xdfile_t *xdf) { unsigned int hbits; - long i, nrec, hsize, bsize; + long nrec, hsize, bsize; unsigned long hav; char const *blk, *cur, *top, *prev; xrecord_t *crec; @@ -171,96 +170,59 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ char *rchg; long *rindex; - if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) { - - return -1; + ha = NULL; + rindex = NULL; + rchg = NULL; + rhash = NULL; + recs = NULL; + + if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) + goto abort; + if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) + goto abort; + + if (xpp->flags & XDF_HISTOGRAM_DIFF) + hbits = hsize = 0; + else { + hbits = xdl_hashbits((unsigned int) narec); + hsize = 1 << hbits; + if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) + goto abort; + memset(rhash, 0, hsize * sizeof(xrecord_t *)); } - if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) { - - xdl_cha_free(&xdf->rcha); - return -1; - } - - hbits = xdl_hashbits((unsigned int) narec); - hsize = 1 << hbits; - if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) { - - xdl_free(recs); - xdl_cha_free(&xdf->rcha); - return -1; - } - for (i = 0; i < hsize; i++) - rhash[i] = NULL; nrec = 0; if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) { - for (top = blk + bsize;;) { - if (cur >= top) { - if (!(cur = blk = xdl_mmfile_next(mf, &bsize))) - break; - top = blk + bsize; - } + for (top = blk + bsize; cur < top; ) { prev = cur; hav = xdl_hash_record(&cur, top, xpp->flags); if (nrec >= narec) { narec *= 2; - if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) { - - xdl_free(rhash); - xdl_free(recs); - xdl_cha_free(&xdf->rcha); - return -1; - } + if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) + goto abort; recs = rrecs; } - if (!(crec = xdl_cha_alloc(&xdf->rcha))) { - - xdl_free(rhash); - xdl_free(recs); - xdl_cha_free(&xdf->rcha); - return -1; - } + if (!(crec = xdl_cha_alloc(&xdf->rcha))) + goto abort; crec->ptr = prev; crec->size = (long) (cur - prev); crec->ha = hav; recs[nrec++] = crec; - if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) { - - xdl_free(rhash); - xdl_free(recs); - xdl_cha_free(&xdf->rcha); - return -1; - } + if (!(xpp->flags & XDF_HISTOGRAM_DIFF) && + xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) + goto abort; } } - if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) { - - xdl_free(rhash); - xdl_free(recs); - xdl_cha_free(&xdf->rcha); - return -1; - } + if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) + goto abort; memset(rchg, 0, (nrec + 2) * sizeof(char)); - if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long)))) { - - xdl_free(rchg); - xdl_free(rhash); - xdl_free(recs); - xdl_cha_free(&xdf->rcha); - return -1; - } - if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long)))) { - - xdl_free(rindex); - xdl_free(rchg); - xdl_free(rhash); - xdl_free(recs); - xdl_cha_free(&xdf->rcha); - return -1; - } + if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long)))) + goto abort; + if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long)))) + goto abort; xdf->nrec = nrec; xdf->recs = recs; @@ -274,6 +236,15 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ xdf->dend = nrec - 1; return 0; + +abort: + xdl_free(ha); + xdl_free(rindex); + xdl_free(rchg); + xdl_free(rhash); + xdl_free(recs); + xdl_cha_free(&xdf->rcha); + return -1; } @@ -290,13 +261,23 @@ static void xdl_free_ctx(xdfile_t *xdf) { int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdfenv_t *xe) { - long enl1, enl2; + long enl1, enl2, sample; xdlclassifier_t cf; - enl1 = xdl_guess_lines(mf1) + 1; - enl2 = xdl_guess_lines(mf2) + 1; + /* + * For histogram diff, we can afford a smaller sample size and + * thus a poorer estimate of the number of lines, as the hash + * table (rhash) won't be filled up/grown. The number of lines + * (nrecs) will be updated correctly anyway by + * xdl_prepare_ctx(). + */ + sample = xpp->flags & XDF_HISTOGRAM_DIFF ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1; - if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) { + enl1 = xdl_guess_lines(mf1, sample) + 1; + enl2 = xdl_guess_lines(mf2, sample) + 1; + + if (!(xpp->flags & XDF_HISTOGRAM_DIFF) && + xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) { return -1; } @@ -314,6 +295,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, } if (!(xpp->flags & XDF_PATIENCE_DIFF) && + !(xpp->flags & XDF_HISTOGRAM_DIFF) && xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { xdl_free_ctx(&xe->xdf2); @@ -321,7 +303,8 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, return -1; } - xdl_free_classifier(&cf); + if (!(xpp->flags & XDF_HISTOGRAM_DIFF)) + xdl_free_classifier(&cf); return 0; } diff --git a/xdiff/xutils.c b/xdiff/xutils.c index ab6503460f..0de084e53f 100644 --- a/xdiff/xutils.c +++ b/xdiff/xutils.c @@ -24,10 +24,6 @@ -#define XDL_GUESS_NLINES 256 - - - long xdl_bogosqrt(long n) { long i; @@ -71,12 +67,6 @@ void *xdl_mmfile_first(mmfile_t *mmf, long *size) } -void *xdl_mmfile_next(mmfile_t *mmf, long *size) -{ - return NULL; -} - - long xdl_mmfile_size(mmfile_t *mmf) { return mmf->size; @@ -159,18 +149,12 @@ void *xdl_cha_next(chastore_t *cha) { } -long xdl_guess_lines(mmfile_t *mf) { +long xdl_guess_lines(mmfile_t *mf, long sample) { long nl = 0, size, tsize = 0; char const *data, *cur, *top; if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) { - for (top = data + size; nl < XDL_GUESS_NLINES;) { - if (cur >= top) { - tsize += (long) (cur - data); - if (!(cur = data = xdl_mmfile_next(mf, &size))) - break; - top = data + size; - } + for (top = data + size; nl < sample && cur < top; ) { nl++; if (!(cur = memchr(cur, '\n', top - cur))) cur = top; @@ -402,3 +386,34 @@ int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, return 0; } + +int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, + int line1, int count1, int line2, int count2) +{ + /* + * This probably does not work outside Git, since + * we have a very simple mmfile structure. + * + * Note: ideally, we would reuse the prepared environment, but + * the libxdiff interface does not (yet) allow for diffing only + * ranges of lines instead of the whole files. + */ + mmfile_t subfile1, subfile2; + xdfenv_t env; + + subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr; + subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr + + diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr; + subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr; + subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr + + diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr; + if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0) + return -1; + + memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1); + memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2); + + xdl_free_env(&env); + + return 0; +} diff --git a/xdiff/xutils.h b/xdiff/xutils.h index d5de8292e0..714719a89c 100644 --- a/xdiff/xutils.h +++ b/xdiff/xutils.h @@ -33,7 +33,7 @@ void xdl_cha_free(chastore_t *cha); void *xdl_cha_alloc(chastore_t *cha); void *xdl_cha_first(chastore_t *cha); void *xdl_cha_next(chastore_t *cha); -long xdl_guess_lines(mmfile_t *mf); +long xdl_guess_lines(mmfile_t *mf, long sample); int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags); unsigned long xdl_hash_record(char const **data, char const *top, long flags); unsigned int xdl_hashbits(unsigned int size); @@ -41,6 +41,8 @@ int xdl_num_out(char *out, long val); long xdl_atol(char const *str, char const **next); int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, const char *func, long funclen, xdemitcb_t *ecb); +int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, + int line1, int count1, int line2, int count2); |