diff options
Diffstat (limited to 'xdiff')
| -rw-r--r-- | xdiff/xdiff.h | 6 | ||||
| -rw-r--r-- | xdiff/xdiffi.c | 12 | ||||
| -rw-r--r-- | xdiff/xhistogram.c | 133 | ||||
| -rw-r--r-- | xdiff/xutils.c | 21 |
4 files changed, 111 insertions, 61 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 2356da5f78..b158369020 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -86,7 +86,11 @@ typedef struct s_xpparam { typedef struct s_xdemitcb { void *priv; - int (*outf)(void *, mmbuffer_t *, int); + int (*out_hunk)(void *, + long old_begin, long old_nr, + long new_begin, long new_nr, + const char *func, long funclen); + int (*out_line)(void *, mmbuffer_t *, int); } xdemitcb_t; typedef long (*find_func_t)(const char *line, long line_len, char *buffer, long buffer_size, void *priv); diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index 3e8aff92bc..1f1f4a3c78 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -575,6 +575,11 @@ static void measure_split(const xdfile_t *xdf, long split, #define INDENT_WEIGHT 60 /* + * How far do we slide a hunk at most? + */ +#define INDENT_HEURISTIC_MAX_SLIDING 100 + +/* * Compute a badness score for the hypothetical split whose measurements are * stored in m. The weight factors were determined empirically using the tools and * corpus described in @@ -886,7 +891,12 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { long shift, best_shift = -1; struct split_score best_score; - for (shift = earliest_end; shift <= g.end; shift++) { + shift = earliest_end; + if (g.end - groupsize - 1 > shift) + shift = g.end - groupsize - 1; + if (g.end - INDENT_HEURISTIC_MAX_SLIDING > shift) + shift = g.end - INDENT_HEURISTIC_MAX_SLIDING; + for (; shift <= g.end; shift++) { struct split_measurement m; struct split_score score = {0, 0}; diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index 73210cb6f3..ec85f5992b 100644 --- a/xdiff/xhistogram.c +++ b/xdiff/xhistogram.c @@ -233,54 +233,31 @@ static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr, 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, +static int fall_back_to_classic_diff(xpparam_t const *xpp, xdfenv_t *env, int line1, int count1, int line2, int count2) { - xpparam_t xpp; - xpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; + xpparam_t xpparam; + xpparam.flags = xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; - return xdl_fall_back_diff(index->env, &xpp, + return xdl_fall_back_diff(env, &xpparam, line1, count1, line2, count2); } -static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env, - int line1, int count1, int line2, int count2) +static inline void free_index(struct histindex *index) { - 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; + xdl_free(index->records); + xdl_free(index->line_map); + xdl_free(index->next_ptrs); + xdl_cha_free(&index->rcha); +} - 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; - } +static int find_lcs(xpparam_t const *xpp, xdfenv_t *env, + struct region *lcs, + int line1, int count1, int line2, int count2) +{ + int b_ptr; + int sz, ret = -1; + struct histindex index; memset(&index, 0, sizeof(index)); @@ -318,9 +295,55 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env, index.ptr_shift = line1; index.max_chain_length = 64; + if (scanA(&index, line1, count1)) + goto cleanup; + + 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); + + if (index.has_common && index.max_chain_length < index.cnt) + ret = 1; + else + ret = 0; + +cleanup: + free_index(&index); + return ret; +} + +static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env, + int line1, int count1, int line2, int count2) +{ + struct region lcs; + int lcs_found; + int result; +redo: + 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(&lcs, 0, sizeof(lcs)); - if (find_lcs(&index, &lcs, line1, count1, line2, count2)) - result = fall_back_to_classic_diff(&index, line1, count1, line2, count2); + lcs_found = find_lcs(xpp, env, &lcs, line1, count1, line2, count2); + if (lcs_found < 0) + goto out; + else if (lcs_found) + result = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2); else { if (lcs.begin1 == 0 && lcs.begin2 == 0) { while (count1--) @@ -333,21 +356,21 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *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; + goto out; + /* + * result = histogram_diff(xpp, env, + * lcs.end1 + 1, LINE_END(1) - lcs.end1, + * lcs.end2 + 1, LINE_END(2) - lcs.end2); + * but let's optimize tail recursion ourself: + */ + count1 = LINE_END(1) - lcs.end1; + line1 = lcs.end1 + 1; + count2 = LINE_END(2) - lcs.end2; + line2 = lcs.end2 + 1; + goto redo; } } - -cleanup: - xdl_free(index.records); - xdl_free(index.line_map); - xdl_free(index.next_ptrs); - xdl_cha_free(&index.rcha); - +out: return result; } diff --git a/xdiff/xutils.c b/xdiff/xutils.c index 88e5995535..963e1c58b9 100644 --- a/xdiff/xutils.c +++ b/xdiff/xutils.c @@ -54,7 +54,7 @@ int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize, mb[2].size = strlen(mb[2].ptr); i++; } - if (ecb->outf(ecb->priv, mb, i) < 0) { + if (ecb->out_line(ecb->priv, mb, i) < 0) { return -1; } @@ -344,8 +344,9 @@ int xdl_num_out(char *out, long val) { return str - out; } -int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, - const char *func, long funclen, xdemitcb_t *ecb) { +static int xdl_format_hunk_hdr(long s1, long c1, long s2, long c2, + const char *func, long funclen, + xdemitcb_t *ecb) { int nb = 0; mmbuffer_t mb; char buf[128]; @@ -387,9 +388,21 @@ int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, mb.ptr = buf; mb.size = nb; - if (ecb->outf(ecb->priv, &mb, 1) < 0) + if (ecb->out_line(ecb->priv, &mb, 1) < 0) return -1; + return 0; +} +int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, + const char *func, long funclen, + xdemitcb_t *ecb) { + if (!ecb->out_hunk) + return xdl_format_hunk_hdr(s1, c1, s2, c2, func, funclen, ecb); + if (ecb->out_hunk(ecb->priv, + c1 ? s1 : s1 - 1, c1, + c2 ? s2 : s2 - 1, c2, + func, funclen) < 0) + return -1; return 0; } |