diff options
Diffstat (limited to 'xdiff')
| -rw-r--r-- | xdiff/xdiff.h | 3 | ||||
| -rw-r--r-- | xdiff/xdiffi.c | 3 | ||||
| -rw-r--r-- | xdiff/xdiffi.h | 2 | ||||
| -rw-r--r-- | xdiff/xemit.c | 85 | ||||
| -rw-r--r-- | xdiff/xhistogram.c | 363 | ||||
| -rw-r--r-- | xdiff/xpatience.c | 27 | ||||
| -rw-r--r-- | xdiff/xprepare.c | 219 | ||||
| -rw-r--r-- | xdiff/xutils.c | 51 | ||||
| -rw-r--r-- | xdiff/xutils.h | 4 |
9 files changed, 588 insertions, 169 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 711048ea36..00d36c3ac7 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 '-' @@ -42,6 +43,7 @@ extern "C" { #define XDL_EMIT_FUNCNAMES (1 << 0) #define XDL_EMIT_COMMON (1 << 1) +#define XDL_EMIT_FUNCCONTEXT (1 << 2) #define XDL_MMB_READONLY (1 << 0) @@ -105,7 +107,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/xemit.c b/xdiff/xemit.c index 1f188dc1f1..d11dbf9f13 100644 --- a/xdiff/xemit.c +++ b/xdiff/xemit.c @@ -100,14 +100,40 @@ static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, return 0; } +struct func_line { + long len; + char buf[80]; +}; + +static long get_func_line(xdfenv_t *xe, xdemitconf_t const *xecfg, + struct func_line *func_line, long start, long limit) +{ + find_func_t ff = xecfg->find_func ? xecfg->find_func : def_ff; + long l, size, step = (start > limit) ? -1 : 1; + char *buf, dummy[1]; + + buf = func_line ? func_line->buf : dummy; + size = func_line ? sizeof(func_line->buf) : sizeof(dummy); + + for (l = start; l != limit && 0 <= l && l < xe->xdf1.nrec; l += step) { + const char *rec; + long reclen = xdl_get_rec(&xe->xdf1, l, &rec); + long len = ff(rec, reclen, buf, size, xecfg->find_func_priv); + if (len >= 0) { + if (func_line) + func_line->len = len; + return l; + } + } + return -1; +} + int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, xdemitconf_t const *xecfg) { long s1, s2, e1, e2, lctx; xdchange_t *xch, *xche; - char funcbuf[80]; - long funclen = 0; long funclineprev = -1; - find_func_t ff = xecfg->find_func ? xecfg->find_func : def_ff; + struct func_line func_line = { 0 }; if (xecfg->flags & XDL_EMIT_COMMON) return xdl_emit_common(xe, xscr, ecb, xecfg); @@ -118,6 +144,17 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, s1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0); s2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0); + if (xecfg->flags & XDL_EMIT_FUNCCONTEXT) { + long fs1 = get_func_line(xe, xecfg, NULL, xch->i1, -1); + if (fs1 < 0) + fs1 = 0; + if (fs1 < s1) { + s2 -= s1 - fs1; + s1 = fs1; + } + } + + again: lctx = xecfg->ctxlen; lctx = XDL_MIN(lctx, xe->xdf1.nrec - (xche->i1 + xche->chg1)); lctx = XDL_MIN(lctx, xe->xdf2.nrec - (xche->i2 + xche->chg2)); @@ -125,27 +162,43 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, e1 = xche->i1 + xche->chg1 + lctx; e2 = xche->i2 + xche->chg2 + lctx; + if (xecfg->flags & XDL_EMIT_FUNCCONTEXT) { + long fe1 = get_func_line(xe, xecfg, NULL, + xche->i1 + xche->chg1, + xe->xdf1.nrec); + if (fe1 < 0) + fe1 = xe->xdf1.nrec; + if (fe1 > e1) { + e2 += fe1 - e1; + e1 = fe1; + } + + /* + * Overlap with next change? Then include it + * in the current hunk and start over to find + * its new end. + */ + if (xche->next) { + long l = xche->next->i1; + if (l <= e1 || + get_func_line(xe, xecfg, NULL, l, e1) < 0) { + xche = xche->next; + goto again; + } + } + } + /* * Emit current hunk header. */ if (xecfg->flags & XDL_EMIT_FUNCNAMES) { - long l; - for (l = s1 - 1; l >= 0 && l > funclineprev; l--) { - const char *rec; - long reclen = xdl_get_rec(&xe->xdf1, l, &rec); - long newfunclen = ff(rec, reclen, funcbuf, - sizeof(funcbuf), - xecfg->find_func_priv); - if (newfunclen >= 0) { - funclen = newfunclen; - break; - } - } + get_func_line(xe, xecfg, &func_line, + s1 - 1, funclineprev); funclineprev = s1 - 1; } if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2, - funcbuf, funclen, ecb) < 0) + func_line.buf, func_line.len, ecb) < 0) return -1; /* 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 1689085235..e419f4f726 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 { @@ -34,6 +36,7 @@ typedef struct s_xdlclass { char const *line; long size; long idx; + long len1, len2; } xdlclass_t; typedef struct s_xdlclassifier { @@ -41,6 +44,8 @@ typedef struct s_xdlclassifier { long hsize; xdlclass_t **rchash; chastore_t ncha; + xdlclass_t **rcrecs; + long alloc; long count; long flags; } xdlclassifier_t; @@ -50,22 +55,20 @@ typedef struct s_xdlclassifier { static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags); static void xdl_free_classifier(xdlclassifier_t *cf); -static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits, - xrecord_t *rec); -static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp, +static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash, + unsigned int hbits, xrecord_t *rec); +static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp, xdlclassifier_t *cf, xdfile_t *xdf); static void xdl_free_ctx(xdfile_t *xdf); static int xdl_clean_mmatch(char const *dis, long i, long s, long e); -static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2); +static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2); static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2); -static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2); +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); @@ -80,8 +83,15 @@ 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 *)))) { + + xdl_free(cf->rchash); + xdl_cha_free(&cf->ncha); + return -1; + } cf->count = 0; @@ -91,16 +101,18 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) { static void xdl_free_classifier(xdlclassifier_t *cf) { + xdl_free(cf->rcrecs); xdl_free(cf->rchash); xdl_cha_free(&cf->ncha); } -static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits, - xrecord_t *rec) { +static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash, + unsigned int hbits, xrecord_t *rec) { long hi; char const *line; xdlclass_t *rcrec; + xdlclass_t **rcrecs; line = rec->ptr; hi = (long) XDL_HASHLONG(rec->ha, cf->hbits); @@ -116,13 +128,25 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned return -1; } rcrec->idx = cf->count++; + if (cf->count > cf->alloc) { + cf->alloc *= 2; + if (!(rcrecs = (xdlclass_t **) xdl_realloc(cf->rcrecs, cf->alloc * sizeof(xdlclass_t *)))) { + + return -1; + } + cf->rcrecs = rcrecs; + } + cf->rcrecs[rcrec->idx] = rcrec; rcrec->line = line; rcrec->size = rec->size; rcrec->ha = rec->ha; + rcrec->len1 = rcrec->len2 = 0; rcrec->next = cf->rchash[hi]; cf->rchash[hi] = rcrec; } + (pass == 1) ? rcrec->len1++ : rcrec->len2++; + rec->ha = (unsigned long) rcrec->idx; hi = (long) XDL_HASHLONG(rec->ha, hbits); @@ -133,10 +157,10 @@ static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned } -static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp, +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; @@ -146,96 +170,59 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp, char *rchg; long *rindex; - if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) { - - return -1; - } - 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; + 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 *)); } - 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(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; @@ -249,6 +236,15 @@ static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp, 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; } @@ -265,39 +261,53 @@ 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; + memset(&cf, 0, sizeof(cf)); + + /* + * 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; + + enl1 = xdl_guess_lines(mf1, sample) + 1; + enl2 = xdl_guess_lines(mf2, sample) + 1; - if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) { + if (!(xpp->flags & XDF_HISTOGRAM_DIFF) && + xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) { return -1; } - if (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) { + if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) { xdl_free_classifier(&cf); return -1; } - if (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) { + if (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) { xdl_free_ctx(&xe->xdf1); xdl_free_classifier(&cf); return -1; } - xdl_free_classifier(&cf); - if (!(xpp->flags & XDF_PATIENCE_DIFF) && - xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) { + !(xpp->flags & XDF_HISTOGRAM_DIFF) && + xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf1); return -1; } + if (!(xpp->flags & XDF_HISTOGRAM_DIFF)) + xdl_free_classifier(&cf); + return 0; } @@ -372,11 +382,10 @@ static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { * matches on the other file. Also, lines that have multiple matches * might be potentially discarded if they happear in a run of discardable. */ -static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) { - long i, nm, rhi, nreff, mlim; - unsigned long hav; +static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { + long i, nm, nreff, mlim; xrecord_t **recs; - xrecord_t *rec; + xdlclass_t *rcrec; char *dis, *dis1, *dis2; if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) { @@ -390,22 +399,16 @@ static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) { if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT) mlim = XDL_MAX_EQLIMIT; for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) { - hav = (*recs)->ha; - rhi = (long) XDL_HASHLONG(hav, xdf2->hbits); - for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next) - if (rec->ha == hav && ++nm == mlim) - break; + rcrec = cf->rcrecs[(*recs)->ha]; + nm = rcrec ? rcrec->len2 : 0; dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1; } if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT) mlim = XDL_MAX_EQLIMIT; for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) { - hav = (*recs)->ha; - rhi = (long) XDL_HASHLONG(hav, xdf1->hbits); - for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next) - if (rec->ha == hav && ++nm == mlim) - break; + rcrec = cf->rcrecs[(*recs)->ha]; + nm = rcrec ? rcrec->len1 : 0; dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1; } @@ -468,10 +471,10 @@ static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) { } -static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) { +static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { if (xdl_trim_ends(xdf1, xdf2) < 0 || - xdl_cleanup_records(xdf1, xdf2) < 0) { + xdl_cleanup_records(cf, xdf1, xdf2) < 0) { return -1; } 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); |