diff options
Diffstat (limited to 'xdiff')
| -rw-r--r-- | xdiff/xdiff.h | 1 | ||||
| -rw-r--r-- | xdiff/xdiffi.c | 56 | ||||
| -rw-r--r-- | xdiff/xhistogram.c | 16 | ||||
| -rw-r--r-- | xdiff/xmerge.c | 105 | ||||
| -rw-r--r-- | xdiff/xpatience.c | 21 | ||||
| -rw-r--r-- | xdiff/xprepare.c | 35 |
6 files changed, 138 insertions, 96 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index b29deca5de..72e25a9ffa 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -66,6 +66,7 @@ extern "C" { /* merge output styles */ #define XDL_MERGE_DIFF3 1 +#define XDL_MERGE_ZEALOUS_DIFF3 2 typedef struct s_mmfile { char *ptr; diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index a4542c05b6..758410c11a 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -315,16 +315,19 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, long *kvd, *kvdf, *kvdb; xdalgoenv_t xenv; diffdata_t dd1, dd2; + int res; - if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) - return xdl_do_patience_diff(mf1, mf2, xpp, xe); - - if (XDF_DIFF_ALG(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; - if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) { + if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) { + res = xdl_do_patience_diff(mf1, mf2, xpp, xe); + goto out; + } - return -1; + if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) { + res = xdl_do_histogram_diff(mf1, mf2, xpp, xe); + goto out; } /* @@ -359,17 +362,15 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, dd2.rchg = xe->xdf2.rchg; dd2.rindex = xe->xdf2.rindex; - if (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec, - kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) { - - xdl_free(kvd); - xdl_free_env(xe); - return -1; - } - + res = xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec, + kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, + &xenv); xdl_free(kvd); + out: + if (res < 0) + xdl_free_env(xe); - return 0; + return res; } @@ -390,12 +391,9 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, } -static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags) +static int recs_match(xrecord_t *rec1, xrecord_t *rec2) { - return (rec1->ha == rec2->ha && - xdl_recmatch(rec1->ptr, rec1->size, - rec2->ptr, rec2->size, - flags)); + return (rec1->ha == rec2->ha); } /* @@ -759,10 +757,10 @@ static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g) * following group, expand this group to include it. Return 0 on success or -1 * if g cannot be slid down. */ -static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags) +static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g) { if (g->end < xdf->nrec && - recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) { + recs_match(xdf->recs[g->start], xdf->recs[g->end])) { xdf->rchg[g->start++] = 0; xdf->rchg[g->end++] = 1; @@ -780,10 +778,10 @@ static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags) * into a previous group, expand this group to include it. Return 0 on success * or -1 if g cannot be slid up. */ -static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g, long flags) +static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g) { if (g->start > 0 && - recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) { + recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1])) { xdf->rchg[--g->start] = 1; xdf->rchg[--g->end] = 0; @@ -833,7 +831,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { end_matching_other = -1; /* Shift the group backward as much as possible: */ - while (!group_slide_up(xdf, &g, flags)) + while (!group_slide_up(xdf, &g)) if (group_previous(xdfo, &go)) BUG("group sync broken sliding up"); @@ -848,7 +846,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { /* Now shift the group forward as far as possible: */ while (1) { - if (group_slide_down(xdf, &g, flags)) + if (group_slide_down(xdf, &g)) break; if (group_next(xdfo, &go)) BUG("group sync broken sliding down"); @@ -875,7 +873,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { * other file that it can align with. */ while (go.end == go.start) { - if (group_slide_up(xdf, &g, flags)) + if (group_slide_up(xdf, &g)) BUG("match disappeared"); if (group_previous(xdfo, &go)) BUG("group sync broken sliding to match"); @@ -918,7 +916,7 @@ int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { } while (g.end > best_shift) { - if (group_slide_up(xdf, &g, flags)) + if (group_slide_up(xdf, &g)) BUG("best shift unreached"); if (group_previous(xdfo, &go)) BUG("group sync broken sliding to blank line"); diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index e694bfd9e3..01decffc33 100644 --- a/xdiff/xhistogram.c +++ b/xdiff/xhistogram.c @@ -88,19 +88,14 @@ struct region { #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) +static int cmp_recs(xrecord_t *r1, xrecord_t *r2) { - return r1->ha == r2->ha && - xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size, - xpp->flags); -} + return r1->ha == r2->ha; -#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))) + (cmp_recs(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) @@ -377,9 +372,6 @@ out: 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/xmerge.c b/xdiff/xmerge.c index 1659edb453..af40c88a5b 100644 --- a/xdiff/xmerge.c +++ b/xdiff/xmerge.c @@ -230,7 +230,7 @@ static int fill_conflict_hunk(xdfenv_t *xe1, const char *name1, size += xdl_recs_copy(xe1, m->i1, m->chg1, needs_cr, 1, dest ? dest + size : NULL); - if (style == XDL_MERGE_DIFF3) { + if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) { /* Shared preimage */ if (!dest) { size += marker_size + 1 + needs_cr + marker3_size; @@ -322,6 +322,40 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1, return size; } +static int recmatch(xrecord_t *rec1, xrecord_t *rec2, unsigned long flags) +{ + return xdl_recmatch(rec1->ptr, rec1->size, + rec2->ptr, rec2->size, flags); +} + +/* + * Remove any common lines from the beginning and end of the conflicted region. + */ +static void xdl_refine_zdiff3_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m, + xpparam_t const *xpp) +{ + xrecord_t **rec1 = xe1->xdf2.recs, **rec2 = xe2->xdf2.recs; + for (; m; m = m->next) { + /* let's handle just the conflicts */ + if (m->mode) + continue; + + while(m->chg1 && m->chg2 && + recmatch(rec1[m->i1], rec2[m->i2], xpp->flags)) { + m->chg1--; + m->chg2--; + m->i1++; + m->i2++; + } + while (m->chg1 && m->chg2 && + recmatch(rec1[m->i1 + m->chg1 - 1], + rec2[m->i2 + m->chg2 - 1], xpp->flags)) { + m->chg1--; + m->chg2--; + } + } +} + /* * Sometimes, changes are not quite identical, but differ in only a few * lines. Try hard to show only these few lines as conflicting. @@ -482,7 +516,22 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, int style = xmp->style; int favor = xmp->favor; - if (style == XDL_MERGE_DIFF3) { + /* + * XDL_MERGE_DIFF3 does not attempt to refine conflicts by looking + * at common areas of sides 1 & 2, because the base (side 0) does + * not match and is being shown. Similarly, simplification of + * non-conflicts is also skipped due to the skipping of conflict + * refinement. + * + * XDL_MERGE_ZEALOUS_DIFF3, on the other hand, will attempt to + * refine conflicts looking for common areas of sides 1 & 2. + * However, since the base is being shown and does not match, + * it will only look for common areas at the beginning or end + * of the conflict block. Since XDL_MERGE_ZEALOUS_DIFF3's + * conflict refinement is much more limited in this fashion, the + * conflict simplification will be skipped. + */ + if (style == XDL_MERGE_DIFF3 || style == XDL_MERGE_ZEALOUS_DIFF3) { /* * "diff3 -m" output does not make sense for anything * more aggressive than XDL_MERGE_EAGER. @@ -603,10 +652,12 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, if (!changes) changes = c; /* refine conflicts */ - if (XDL_MERGE_ZEALOUS <= level && - (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 || - xdl_simplify_non_conflicts(xe1, changes, - XDL_MERGE_ZEALOUS < level) < 0)) { + if (style == XDL_MERGE_ZEALOUS_DIFF3) { + xdl_refine_zdiff3_conflicts(xe1, xe2, changes, xpp); + } else if (XDL_MERGE_ZEALOUS <= level && + (xdl_refine_conflicts(xe1, xe2, changes, xpp) < 0 || + xdl_simplify_non_conflicts(xe1, changes, + XDL_MERGE_ZEALOUS < level) < 0)) { xdl_cleanup_merge(changes); return -1; } @@ -633,42 +684,42 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2, xmparam_t const *xmp, mmbuffer_t *result) { - xdchange_t *xscr1, *xscr2; + xdchange_t *xscr1 = NULL, *xscr2 = NULL; xdfenv_t xe1, xe2; - int status; + int status = -1; xpparam_t const *xpp = &xmp->xpp; result->ptr = NULL; result->size = 0; - if (xdl_do_diff(orig, mf1, xpp, &xe1) < 0) { - return -1; - } - if (xdl_do_diff(orig, mf2, xpp, &xe2) < 0) { - xdl_free_env(&xe1); + if (xdl_do_diff(orig, mf1, xpp, &xe1) < 0) return -1; - } + + if (xdl_do_diff(orig, mf2, xpp, &xe2) < 0) + goto free_xe1; /* avoid double free of xe2 */ + if (xdl_change_compact(&xe1.xdf1, &xe1.xdf2, xpp->flags) < 0 || xdl_change_compact(&xe1.xdf2, &xe1.xdf1, xpp->flags) < 0 || - xdl_build_script(&xe1, &xscr1) < 0) { - xdl_free_env(&xe1); - return -1; - } + xdl_build_script(&xe1, &xscr1) < 0) + goto out; + if (xdl_change_compact(&xe2.xdf1, &xe2.xdf2, xpp->flags) < 0 || xdl_change_compact(&xe2.xdf2, &xe2.xdf1, xpp->flags) < 0 || - xdl_build_script(&xe2, &xscr2) < 0) { - xdl_free_script(xscr1); - xdl_free_env(&xe1); - xdl_free_env(&xe2); - return -1; - } - status = 0; + xdl_build_script(&xe2, &xscr2) < 0) + goto out; + if (!xscr1) { result->ptr = xdl_malloc(mf2->size); + if (!result->ptr) + goto out; + status = 0; memcpy(result->ptr, mf2->ptr, mf2->size); result->size = mf2->size; } else if (!xscr2) { result->ptr = xdl_malloc(mf1->size); + if (!result->ptr) + goto out; + status = 0; memcpy(result->ptr, mf1->ptr, mf1->size); result->size = mf1->size; } else { @@ -676,11 +727,13 @@ int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2, &xe2, xscr2, xmp, result); } + out: xdl_free_script(xscr1); xdl_free_script(xscr2); - xdl_free_env(&xe1); xdl_free_env(&xe2); + free_xe1: + xdl_free_env(&xe1); return status; } diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index c5d48e80ae..1a21c6a74b 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -198,7 +198,7 @@ static int binary_search(struct entry **sequence, int longest, * item per sequence length: the sequence with the smallest last * element (in terms of line2). */ -static struct entry *find_longest_common_sequence(struct hashmap *map) +static int find_longest_common_sequence(struct hashmap *map, struct entry **res) { struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *)); int longest = 0, i; @@ -211,6 +211,9 @@ static struct entry *find_longest_common_sequence(struct hashmap *map) */ int anchor_i = -1; + if (!sequence) + return -1; + for (entry = map->first; entry; entry = entry->next) { if (!entry->line2 || entry->line2 == NON_UNIQUE) continue; @@ -230,8 +233,9 @@ static struct entry *find_longest_common_sequence(struct hashmap *map) /* No common unique lines were found */ if (!longest) { + *res = NULL; xdl_free(sequence); - return NULL; + return 0; } /* Iterate starting at the last element, adjusting the "next" members */ @@ -241,8 +245,9 @@ static struct entry *find_longest_common_sequence(struct hashmap *map) entry->previous->next = entry; entry = entry->previous; } + *res = entry; xdl_free(sequence); - return entry; + return 0; } static int match(struct hashmap *map, int line1, int line2) @@ -358,14 +363,16 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2, return 0; } - first = find_longest_common_sequence(&map); + result = find_longest_common_sequence(&map, &first); + if (result) + goto out; if (first) result = walk_common_sequence(&map, first, line1, count1, line2, count2); else result = fall_back_to_classic_diff(&map, line1, count1, line2, count2); - + out: xdl_free(map.entries); return result; } @@ -373,10 +380,6 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2, int xdl_do_patience_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; - - /* environment is cleaned up in xdl_diff() */ return patience_diff(file1, file2, xpp, env, 1, env->xdf1.nrec, 1, env->xdf2.nrec); } diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index abeb8fb84e..4527a4a07c 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -181,15 +181,11 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) goto abort; - if (XDF_DIFF_ALG(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 *)); - } + 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 *)); nrec = 0; if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) { @@ -208,9 +204,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ crec->size = (long) (cur - prev); crec->ha = hav; recs[nrec++] = crec; - - if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && - xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) + if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) goto abort; } } @@ -219,10 +213,13 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ goto abort; memset(rchg, 0, (nrec + 2) * sizeof(char)); - if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long)))) - goto abort; - if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long)))) - goto abort; + if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && + (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) { + if (!(rindex = xdl_malloc((nrec + 1) * sizeof(*rindex)))) + goto abort; + if (!(ha = xdl_malloc((nrec + 1) * sizeof(*ha)))) + goto abort; + } xdf->nrec = nrec; xdf->recs = recs; @@ -279,8 +276,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, enl1 = xdl_guess_lines(mf1, sample) + 1; enl2 = xdl_guess_lines(mf2, sample) + 1; - if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF && - xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) + if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) return -1; if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) { @@ -305,8 +301,7 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, return -1; } - if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) - xdl_free_classifier(&cf); + xdl_free_classifier(&cf); return 0; } |