diff options
Diffstat (limited to 'xdiff')
| -rw-r--r-- | xdiff/xdiff.h | 42 | ||||
| -rw-r--r-- | xdiff/xdiffi.c | 629 | ||||
| -rw-r--r-- | xdiff/xdiffi.h | 4 | ||||
| -rw-r--r-- | xdiff/xemit.c | 27 | ||||
| -rw-r--r-- | xdiff/xemit.h | 4 | ||||
| -rw-r--r-- | xdiff/xinclude.h | 4 | ||||
| -rw-r--r-- | xdiff/xmacros.h | 4 | ||||
| -rw-r--r-- | xdiff/xmerge.c | 4 | ||||
| -rw-r--r-- | xdiff/xpatience.c | 48 | ||||
| -rw-r--r-- | xdiff/xprepare.c | 4 | ||||
| -rw-r--r-- | xdiff/xprepare.h | 4 | ||||
| -rw-r--r-- | xdiff/xtypes.h | 4 | ||||
| -rw-r--r-- | xdiff/xutils.c | 148 | ||||
| -rw-r--r-- | xdiff/xutils.h | 4 |
14 files changed, 643 insertions, 287 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 7423f77fc8..2356da5f78 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * @@ -27,33 +27,31 @@ extern "C" { #endif /* #ifdef __cplusplus */ +/* xpparm_t.flags */ +#define XDF_NEED_MINIMAL (1 << 0) -#define XDF_NEED_MINIMAL (1 << 1) -#define XDF_IGNORE_WHITESPACE (1 << 2) -#define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3) -#define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4) -#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL) +#define XDF_IGNORE_WHITESPACE (1 << 1) +#define XDF_IGNORE_WHITESPACE_CHANGE (1 << 2) +#define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 3) +#define XDF_IGNORE_CR_AT_EOL (1 << 4) +#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | \ + XDF_IGNORE_WHITESPACE_CHANGE | \ + XDF_IGNORE_WHITESPACE_AT_EOL | \ + XDF_IGNORE_CR_AT_EOL) -#define XDF_PATIENCE_DIFF (1 << 5) -#define XDF_HISTOGRAM_DIFF (1 << 6) +#define XDF_IGNORE_BLANK_LINES (1 << 7) + +#define XDF_PATIENCE_DIFF (1 << 14) +#define XDF_HISTOGRAM_DIFF (1 << 15) #define XDF_DIFF_ALGORITHM_MASK (XDF_PATIENCE_DIFF | XDF_HISTOGRAM_DIFF) #define XDF_DIFF_ALG(x) ((x) & XDF_DIFF_ALGORITHM_MASK) -#define XDF_IGNORE_BLANK_LINES (1 << 7) - -#define XDF_COMPACTION_HEURISTIC (1 << 8) +#define XDF_INDENT_HEURISTIC (1 << 23) +/* xdemitconf_t.flags */ #define XDL_EMIT_FUNCNAMES (1 << 0) #define XDL_EMIT_FUNCCONTEXT (1 << 2) -#define XDL_MMB_READONLY (1 << 0) - -#define XDL_MMF_ATOMIC (1 << 0) - -#define XDL_BDOP_INS 1 -#define XDL_BDOP_CPY 2 -#define XDL_BDOP_INSB 3 - /* merge simplification levels */ #define XDL_MERGE_MINIMAL 0 #define XDL_MERGE_EAGER 1 @@ -80,6 +78,10 @@ typedef struct s_mmbuffer { typedef struct s_xpparam { unsigned long flags; + + /* See Documentation/diff-options.txt. */ + char **anchors; + size_t anchors_nr; } xpparam_t; typedef struct s_xdemitcb { diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index b3c6848875..3e8aff92bc 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * @@ -22,34 +22,17 @@ #include "xinclude.h" - - #define XDL_MAX_COST_MIN 256 #define XDL_HEUR_MIN_COST 256 #define XDL_LINE_MAX (long)((1UL << (CHAR_BIT * sizeof(long) - 1)) - 1) #define XDL_SNAKE_CNT 20 #define XDL_K_HEUR 4 - - typedef struct s_xdpsplit { long i1, i2; int min_lo, min_hi; } xdpsplit_t; - - - -static long xdl_split(unsigned long const *ha1, long off1, long lim1, - unsigned long const *ha2, long off2, long lim2, - long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl, - xdalgoenv_t *xenv); -static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2); - - - - - /* * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers. * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both @@ -400,138 +383,544 @@ static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, } -static int is_blank_line(xrecord_t **recs, long ix, long flags) +static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags) { - return xdl_blankline(recs[ix]->ptr, recs[ix]->size, flags); + return (rec1->ha == rec2->ha && + xdl_recmatch(rec1->ptr, rec1->size, + rec2->ptr, rec2->size, + flags)); } -static int recs_match(xrecord_t **recs, long ixs, long ix, long flags) +/* + * If a line is indented more than this, get_indent() just returns this value. + * This avoids having to do absurd amounts of work for data that are not + * human-readable text, and also ensures that the output of get_indent fits within + * an int. + */ +#define MAX_INDENT 200 + +/* + * Return the amount of indentation of the specified line, treating TAB as 8 + * columns. Return -1 if line is empty or contains only whitespace. Clamp the + * output value at MAX_INDENT. + */ +static int get_indent(xrecord_t *rec) { - return (recs[ixs]->ha == recs[ix]->ha && - xdl_recmatch(recs[ixs]->ptr, recs[ixs]->size, - recs[ix]->ptr, recs[ix]->size, - flags)); + long i; + int ret = 0; + + for (i = 0; i < rec->size; i++) { + char c = rec->ptr[i]; + + if (!XDL_ISSPACE(c)) + return ret; + else if (c == ' ') + ret += 1; + else if (c == '\t') + ret += 8 - ret % 8; + /* ignore other whitespace characters */ + + if (ret >= MAX_INDENT) + return MAX_INDENT; + } + + /* The line contains only whitespace. */ + return -1; } -int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { - long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec; - char *rchg = xdf->rchg, *rchgo = xdfo->rchg; - unsigned int blank_lines; - xrecord_t **recs = xdf->recs; +/* + * If more than this number of consecutive blank rows are found, just return this + * value. This avoids requiring O(N^2) work for pathological cases, and also + * ensures that the output of score_split fits in an int. + */ +#define MAX_BLANKS 20 +/* Characteristics measured about a hypothetical split position. */ +struct split_measurement { /* - * This is the same of what GNU diff does. Move back and forward - * change groups for a consistent and pretty diff output. This also - * helps in finding joinable change groups and reduce the diff size. + * Is the split at the end of the file (aside from any blank lines)? */ - for (ix = ixo = 0;;) { - /* - * Find the first changed line in the to-be-compacted file. - * We need to keep track of both indexes, so if we find a - * changed lines group on the other file, while scanning the - * to-be-compacted file, we need to skip it properly. Note - * that loops that are testing for changed lines on rchg* do - * not need index bounding since the array is prepared with - * a zero at position -1 and N. - */ - for (; ix < nrec && !rchg[ix]; ix++) - while (rchgo[ixo++]); - if (ix == nrec) + int end_of_file; + + /* + * How much is the line immediately following the split indented (or -1 if + * the line is blank): + */ + int indent; + + /* + * How many consecutive lines above the split are blank? + */ + int pre_blank; + + /* + * How much is the nearest non-blank line above the split indented (or -1 + * if there is no such line)? + */ + int pre_indent; + + /* + * How many lines after the line following the split are blank? + */ + int post_blank; + + /* + * How much is the nearest non-blank line after the line following the + * split indented (or -1 if there is no such line)? + */ + int post_indent; +}; + +struct split_score { + /* The effective indent of this split (smaller is preferred). */ + int effective_indent; + + /* Penalty for this split (smaller is preferred). */ + int penalty; +}; + +/* + * Fill m with information about a hypothetical split of xdf above line split. + */ +static void measure_split(const xdfile_t *xdf, long split, + struct split_measurement *m) +{ + long i; + + if (split >= xdf->nrec) { + m->end_of_file = 1; + m->indent = -1; + } else { + m->end_of_file = 0; + m->indent = get_indent(xdf->recs[split]); + } + + m->pre_blank = 0; + m->pre_indent = -1; + for (i = split - 1; i >= 0; i--) { + m->pre_indent = get_indent(xdf->recs[i]); + if (m->pre_indent != -1) + break; + m->pre_blank += 1; + if (m->pre_blank == MAX_BLANKS) { + m->pre_indent = 0; break; + } + } + + m->post_blank = 0; + m->post_indent = -1; + for (i = split + 1; i < xdf->nrec; i++) { + m->post_indent = get_indent(xdf->recs[i]); + if (m->post_indent != -1) + break; + m->post_blank += 1; + if (m->post_blank == MAX_BLANKS) { + m->post_indent = 0; + break; + } + } +} + +/* + * The empirically-determined weight factors used by score_split() below. + * Larger values means that the position is a less favorable place to split. + * + * Note that scores are only ever compared against each other, so multiplying + * all of these weight/penalty values by the same factor wouldn't change the + * heuristic's behavior. Still, we need to set that arbitrary scale *somehow*. + * In practice, these numbers are chosen to be large enough that they can be + * adjusted relative to each other with sufficient precision despite using + * integer math. + */ + +/* Penalty if there are no non-blank lines before the split */ +#define START_OF_FILE_PENALTY 1 + +/* Penalty if there are no non-blank lines after the split */ +#define END_OF_FILE_PENALTY 21 + +/* Multiplier for the number of blank lines around the split */ +#define TOTAL_BLANK_WEIGHT (-30) + +/* Multiplier for the number of blank lines after the split */ +#define POST_BLANK_WEIGHT 6 + +/* + * Penalties applied if the line is indented more than its predecessor + */ +#define RELATIVE_INDENT_PENALTY (-4) +#define RELATIVE_INDENT_WITH_BLANK_PENALTY 10 + +/* + * Penalties applied if the line is indented less than both its predecessor and + * its successor + */ +#define RELATIVE_OUTDENT_PENALTY 24 +#define RELATIVE_OUTDENT_WITH_BLANK_PENALTY 17 + +/* + * Penalties applied if the line is indented less than its predecessor but not + * less than its successor + */ +#define RELATIVE_DEDENT_PENALTY 23 +#define RELATIVE_DEDENT_WITH_BLANK_PENALTY 17 + +/* + * We only consider whether the sum of the effective indents for splits are + * less than (-1), equal to (0), or greater than (+1) each other. The resulting + * value is multiplied by the following weight and combined with the penalty to + * determine the better of two scores. + */ +#define INDENT_WEIGHT 60 +/* + * 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 + * + * https://github.com/mhagger/diff-slider-tools + * + * Also see that project if you want to improve the weights based on, for example, + * a larger or more diverse corpus. + */ +static void score_add_split(const struct split_measurement *m, struct split_score *s) +{ + /* + * A place to accumulate penalty factors (positive makes this index more + * favored): + */ + int post_blank, total_blank, indent, any_blanks; + + if (m->pre_indent == -1 && m->pre_blank == 0) + s->penalty += START_OF_FILE_PENALTY; + + if (m->end_of_file) + s->penalty += END_OF_FILE_PENALTY; + + /* + * Set post_blank to the number of blank lines following the split, + * including the line immediately after the split: + */ + post_blank = (m->indent == -1) ? 1 + m->post_blank : 0; + total_blank = m->pre_blank + post_blank; + + /* Penalties based on nearby blank lines: */ + s->penalty += TOTAL_BLANK_WEIGHT * total_blank; + s->penalty += POST_BLANK_WEIGHT * post_blank; + + if (m->indent != -1) + indent = m->indent; + else + indent = m->post_indent; + + any_blanks = (total_blank != 0); + + /* Note that the effective indent is -1 at the end of the file: */ + s->effective_indent += indent; + + if (indent == -1) { + /* No additional adjustments needed. */ + } else if (m->pre_indent == -1) { + /* No additional adjustments needed. */ + } else if (indent > m->pre_indent) { + /* + * The line is indented more than its predecessor. + */ + s->penalty += any_blanks ? + RELATIVE_INDENT_WITH_BLANK_PENALTY : + RELATIVE_INDENT_PENALTY; + } else if (indent == m->pre_indent) { + /* + * The line has the same indentation level as its predecessor. + * No additional adjustments needed. + */ + } else { /* - * Record the start of a changed-group in the to-be-compacted file - * and find the end of it, on both to-be-compacted and other file - * indexes (ix and ixo). + * The line is indented less than its predecessor. It could be + * the block terminator of the previous block, but it could + * also be the start of a new block (e.g., an "else" block, or + * maybe the previous block didn't have a block terminator). + * Try to distinguish those cases based on what comes next: */ - ixs = ix; - for (ix++; rchg[ix]; ix++); - for (; rchgo[ixo]; ixo++); + if (m->post_indent != -1 && m->post_indent > indent) { + /* + * The following line is indented more. So it is likely + * that this line is the start of a block. + */ + s->penalty += any_blanks ? + RELATIVE_OUTDENT_WITH_BLANK_PENALTY : + RELATIVE_OUTDENT_PENALTY; + } else { + /* + * That was probably the end of a block. + */ + s->penalty += any_blanks ? + RELATIVE_DEDENT_WITH_BLANK_PENALTY : + RELATIVE_DEDENT_PENALTY; + } + } +} + +static int score_cmp(struct split_score *s1, struct split_score *s2) +{ + /* -1 if s1.effective_indent < s2->effective_indent, etc. */ + int cmp_indents = ((s1->effective_indent > s2->effective_indent) - + (s1->effective_indent < s2->effective_indent)); + return INDENT_WEIGHT * cmp_indents + (s1->penalty - s2->penalty); +} + +/* + * Represent a group of changed lines in an xdfile_t (i.e., a contiguous group + * of lines that was inserted or deleted from the corresponding version of the + * file). We consider there to be such a group at the beginning of the file, at + * the end of the file, and between any two unchanged lines, though most such + * groups will usually be empty. + * + * If the first line in a group is equal to the line following the group, then + * the group can be slid down. Similarly, if the last line in a group is equal + * to the line preceding the group, then the group can be slid up. See + * group_slide_down() and group_slide_up(). + * + * Note that loops that are testing for changed lines in xdf->rchg do not need + * index bounding since the array is prepared with a zero at position -1 and N. + */ +struct xdlgroup { + /* + * The index of the first changed line in the group, or the index of + * the unchanged line above which the (empty) group is located. + */ + long start; + + /* + * The index of the first unchanged line after the group. For an empty + * group, end is equal to start. + */ + long end; +}; + +/* + * Initialize g to point at the first group in xdf. + */ +static void group_init(xdfile_t *xdf, struct xdlgroup *g) +{ + g->start = g->end = 0; + while (xdf->rchg[g->end]) + g->end++; +} + +/* + * Move g to describe the next (possibly empty) group in xdf and return 0. If g + * is already at the end of the file, do nothing and return -1. + */ +static inline int group_next(xdfile_t *xdf, struct xdlgroup *g) +{ + if (g->end == xdf->nrec) + return -1; + + g->start = g->end + 1; + for (g->end = g->start; xdf->rchg[g->end]; g->end++) + ; + + return 0; +} + +/* + * Move g to describe the previous (possibly empty) group in xdf and return 0. + * If g is already at the beginning of the file, do nothing and return -1. + */ +static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g) +{ + if (g->start == 0) + return -1; + + g->end = g->start - 1; + for (g->start = g->end; xdf->rchg[g->start - 1]; g->start--) + ; + + return 0; +} + +/* + * If g can be slid toward the end of the file, do so, and if it bumps into a + * 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) +{ + if (g->end < xdf->nrec && + recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) { + xdf->rchg[g->start++] = 0; + xdf->rchg[g->end++] = 1; + + while (xdf->rchg[g->end]) + g->end++; + + return 0; + } else { + return -1; + } +} + +/* + * If g can be slid toward the beginning of the file, do so, and if it bumps + * 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) +{ + if (g->start > 0 && + recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) { + xdf->rchg[--g->start] = 1; + xdf->rchg[--g->end] = 0; + + while (xdf->rchg[g->start - 1]) + g->start--; + + return 0; + } else { + return -1; + } +} + +static void xdl_bug(const char *msg) +{ + fprintf(stderr, "BUG: %s\n", msg); + exit(1); +} + +/* + * Move back and forward change groups for a consistent and pretty diff output. + * This also helps in finding joinable change groups and reducing the diff + * size. + */ +int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { + struct xdlgroup g, go; + long earliest_end, end_matching_other; + long groupsize; + + group_init(xdf, &g); + group_init(xdfo, &go); + + while (1) { + /* If the group is empty in the to-be-compacted file, skip it: */ + if (g.end == g.start) + goto next; + + /* + * Now shift the change up and then down as far as possible in + * each direction. If it bumps into any other changes, merge them. + */ do { - grpsiz = ix - ixs; - blank_lines = 0; + groupsize = g.end - g.start; /* - * If the line before the current change group, is equal to - * the last line of the current change group, shift backward - * the group. + * Keep track of the last "end" index that causes this + * group to align with a group of changed lines in the + * other file. -1 indicates that we haven't found such + * a match yet: */ - while (ixs > 0 && recs_match(recs, ixs - 1, ix - 1, flags)) { - rchg[--ixs] = 1; - rchg[--ix] = 0; - - /* - * This change might have joined two change groups, - * so we try to take this scenario in account by moving - * the start index accordingly (and so the other-file - * end-of-group index). - */ - for (; rchg[ixs - 1]; ixs--); - while (rchgo[--ixo]); - } + end_matching_other = -1; - /* - * Record the end-of-group position in case we are matched - * with a group of changes in the other file (that is, the - * change record before the end-of-group index in the other - * file is set). - */ - ixref = rchgo[ixo - 1] ? ix: nrec; + /* Shift the group backward as much as possible: */ + while (!group_slide_up(xdf, &g, flags)) + if (group_previous(xdfo, &go)) + xdl_bug("group sync broken sliding up"); /* - * If the first line of the current change group, is equal to - * the line next of the current change group, shift forward - * the group. + * This is this highest that this group can be shifted. + * Record its end index: */ - while (ix < nrec && recs_match(recs, ixs, ix, flags)) { - blank_lines += is_blank_line(recs, ix, flags); - - rchg[ixs++] = 0; - rchg[ix++] = 1; - - /* - * This change might have joined two change groups, - * so we try to take this scenario in account by moving - * the start index accordingly (and so the other-file - * end-of-group index). Keep tracking the reference - * index in case we are shifting together with a - * corresponding group of changes in the other file. - */ - for (; rchg[ix]; ix++); - while (rchgo[++ixo]) - ixref = ix; - } - } while (grpsiz != ix - ixs); + earliest_end = g.end; - /* - * Try to move back the possibly merged group of changes, to match - * the recorded position in the other file. - */ - while (ixref < ix) { - rchg[--ixs] = 1; - rchg[--ix] = 0; - while (rchgo[--ixo]); - } + if (go.end > go.start) + end_matching_other = g.end; + + /* Now shift the group forward as far as possible: */ + while (1) { + if (group_slide_down(xdf, &g, flags)) + break; + if (group_next(xdfo, &go)) + xdl_bug("group sync broken sliding down"); + + if (go.end > go.start) + end_matching_other = g.end; + } + } while (groupsize != g.end - g.start); /* - * If a group can be moved back and forth, see if there is a - * blank line in the moving space. If there is a blank line, - * make sure the last blank line is the end of the group. + * If the group can be shifted, then we can possibly use this + * freedom to produce a more intuitive diff. * - * As we already shifted the group forward as far as possible - * in the earlier loop, we need to shift it back only if at all. + * The group is currently shifted as far down as possible, so the + * heuristics below only have to handle upwards shifts. */ - if ((flags & XDF_COMPACTION_HEURISTIC) && blank_lines) { - while (ixs > 0 && - !is_blank_line(recs, ix - 1, flags) && - recs_match(recs, ixs - 1, ix - 1, flags)) { - rchg[--ixs] = 1; - rchg[--ix] = 0; + + if (g.end == earliest_end) { + /* no shifting was possible */ + } else if (end_matching_other != -1) { + /* + * Move the possibly merged group of changes back to line + * up with the last group of changes from the other file + * that it can align with. + */ + while (go.end == go.start) { + if (group_slide_up(xdf, &g, flags)) + xdl_bug("match disappeared"); + if (group_previous(xdfo, &go)) + xdl_bug("group sync broken sliding to match"); + } + } else if (flags & XDF_INDENT_HEURISTIC) { + /* + * Indent heuristic: a group of pure add/delete lines + * implies two splits, one between the end of the "before" + * context and the start of the group, and another between + * the end of the group and the beginning of the "after" + * context. Some splits are aesthetically better and some + * are worse. We compute a badness "score" for each split, + * and add the scores for the two splits to define a + * "score" for each position that the group can be shifted + * to. Then we pick the shift with the lowest score. + */ + long shift, best_shift = -1; + struct split_score best_score; + + for (shift = earliest_end; shift <= g.end; shift++) { + struct split_measurement m; + struct split_score score = {0, 0}; + + measure_split(xdf, shift, &m); + score_add_split(&m, &score); + measure_split(xdf, shift - groupsize, &m); + score_add_split(&m, &score); + if (best_shift == -1 || + score_cmp(&score, &best_score) <= 0) { + best_score.effective_indent = score.effective_indent; + best_score.penalty = score.penalty; + best_shift = shift; + } + } + + while (g.end > best_shift) { + if (group_slide_up(xdf, &g, flags)) + xdl_bug("best shift unreached"); + if (group_previous(xdfo, &go)) + xdl_bug("group sync broken sliding to blank line"); } } + + next: + /* Move past the just-processed group: */ + if (group_next(xdf, &g)) + break; + if (group_next(xdfo, &go)) + xdl_bug("group sync broken moving to next group"); } + if (!group_next(xdfo, &go)) + xdl_bug("group sync broken at end of file"); + return 0; } diff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h index 8b81206c9a..8f1c7c8b04 100644 --- a/xdiff/xdiffi.h +++ b/xdiff/xdiffi.h @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * diff --git a/xdiff/xemit.c b/xdiff/xemit.c index 7389ce4102..7778dc2b19 100644 --- a/xdiff/xemit.c +++ b/xdiff/xemit.c @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * @@ -121,6 +121,12 @@ static long match_func_rec(xdfile_t *xdf, xdemitconf_t const *xecfg, long ri, return xecfg->find_func(rec, len, buf, sz, xecfg->find_func_priv); } +static int is_func_rec(xdfile_t *xdf, xdemitconf_t const *xecfg, long ri) +{ + char dummy[1]; + return match_func_rec(xdf, xecfg, ri, dummy, sizeof(dummy)) >= 0; +} + struct func_line { long len; char buf[80]; @@ -178,21 +184,17 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, /* Appended chunk? */ if (i1 >= xe->xdf1.nrec) { - char dummy[1]; long i2 = xch->i2; /* * We don't need additional context if - * a whole function was added, possibly - * starting with empty lines. + * a whole function was added. */ - while (i2 < xe->xdf2.nrec && - is_empty_rec(&xe->xdf2, i2)) + while (i2 < xe->xdf2.nrec) { + if (is_func_rec(&xe->xdf2, xecfg, i2)) + goto post_context_calculation; i2++; - if (i2 < xe->xdf2.nrec && - match_func_rec(&xe->xdf2, xecfg, i2, - dummy, sizeof(dummy)) >= 0) - goto post_context_calculation; + } /* * Otherwise get more context from the @@ -202,6 +204,9 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, } fs1 = get_func_line(xe, xecfg, NULL, i1, -1); + while (fs1 > 0 && !is_empty_rec(&xe->xdf1, fs1 - 1) && + !is_func_rec(&xe->xdf1, xecfg, fs1 - 1)) + fs1--; if (fs1 < 0) fs1 = 0; if (fs1 < s1) { diff --git a/xdiff/xemit.h b/xdiff/xemit.h index d29710770c..1b9887e670 100644 --- a/xdiff/xemit.h +++ b/xdiff/xemit.h @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * diff --git a/xdiff/xinclude.h b/xdiff/xinclude.h index 526ccb344d..f35c4485df 100644 --- a/xdiff/xinclude.h +++ b/xdiff/xinclude.h @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h index 165a895a93..2809a28ca9 100644 --- a/xdiff/xmacros.h +++ b/xdiff/xmacros.h @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c index f338ad6c75..1659edb453 100644 --- a/xdiff/xmerge.c +++ b/xdiff/xmerge.c @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index a613efc703..f3573d9f00 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * @@ -62,6 +62,12 @@ struct hashmap { * initially, "next" reflects only the order in file1. */ struct entry *next, *previous; + + /* + * If 1, this entry can serve as an anchor. See + * Documentation/diff-options.txt for more information. + */ + unsigned anchor : 1; } *entries, *first, *last; /* were common records found? */ unsigned long has_matches; @@ -70,8 +76,19 @@ struct hashmap { xpparam_t const *xpp; }; +static int is_anchor(xpparam_t const *xpp, const char *line) +{ + int i; + for (i = 0; i < xpp->anchors_nr; i++) { + if (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i]))) + return 1; + } + return 0; +} + /* The argument "pass" is 1 for the first file, 2 for the second. */ -static void insert_record(int line, struct hashmap *map, int pass) +static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map, + int pass) { xrecord_t **records = pass == 1 ? map->env->xdf1.recs : map->env->xdf2.recs; @@ -110,6 +127,7 @@ static void insert_record(int line, struct hashmap *map, int pass) return; map->entries[index].line1 = line; map->entries[index].hash = record->ha; + map->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr); if (!map->first) map->first = map->entries + index; if (map->last) { @@ -147,11 +165,11 @@ static int fill_hashmap(mmfile_t *file1, mmfile_t *file2, /* First, fill with entries from the first file */ while (count1--) - insert_record(line1++, result, 1); + insert_record(xpp, line1++, result, 1); /* Then search for matches in the second file */ while (count2--) - insert_record(line2++, result, 2); + insert_record(xpp, line2++, result, 2); return 0; } @@ -166,7 +184,7 @@ static int binary_search(struct entry **sequence, int longest, int left = -1, right = longest; while (left + 1 < right) { - int middle = (left + right) / 2; + int middle = left + (right - left) / 2; /* by construction, no two entries can be equal */ if (sequence[middle]->line2 > entry->line2) right = middle; @@ -192,14 +210,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map) int longest = 0, i; struct entry *entry; + /* + * If not -1, this entry in sequence must never be overridden. + * Therefore, overriding entries before this has no effect, so + * do not do that either. + */ + int anchor_i = -1; + for (entry = map->first; entry; entry = entry->next) { if (!entry->line2 || entry->line2 == NON_UNIQUE) continue; i = binary_search(sequence, longest, entry); entry->previous = i < 0 ? NULL : sequence[i]; - sequence[++i] = entry; - if (i == longest) + ++i; + if (i <= anchor_i) + continue; + sequence[i] = entry; + if (entry->anchor) { + anchor_i = i; + longest = anchor_i + 1; + } else if (i == longest) { longest++; + } } /* No common unique lines were found */ diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index 13b55aba74..abeb8fb84e 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * diff --git a/xdiff/xprepare.h b/xdiff/xprepare.h index 8fb06a5374..947d9fc1bb 100644 --- a/xdiff/xprepare.h +++ b/xdiff/xprepare.h @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * diff --git a/xdiff/xtypes.h b/xdiff/xtypes.h index 2511aef8d8..8442bd436e 100644 --- a/xdiff/xtypes.h +++ b/xdiff/xtypes.h @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * diff --git a/xdiff/xutils.c b/xdiff/xutils.c index 027192a1c7..88e5995535 100644 --- a/xdiff/xutils.c +++ b/xdiff/xutils.c @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * @@ -156,6 +156,24 @@ int xdl_blankline(const char *line, long size, long flags) return (i == size); } +/* + * Have we eaten everything on the line, except for an optional + * CR at the very end? + */ +static int ends_with_optional_cr(const char *l, long s, long i) +{ + int complete = s && l[s-1] == '\n'; + + if (complete) + s--; + if (s == i) + return 1; + /* do not ignore CR at the end of an incomplete line */ + if (complete && s == i + 1 && l[i] == '\r') + return 1; + return 0; +} + int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) { int i1, i2; @@ -170,7 +188,8 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) /* * -w matches everything that matches with -b, and -b in turn - * matches everything that matches with --ignore-space-at-eol. + * matches everything that matches with --ignore-space-at-eol, + * which in turn matches everything that matches with --ignore-cr-at-eol. * * Each flavor of ignoring needs different logic to skip whitespaces * while we have both sides to compare. @@ -204,6 +223,14 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) i1++; i2++; } + } else if (flags & XDF_IGNORE_CR_AT_EOL) { + /* Find the first difference and see how the line ends */ + while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) { + i1++; + i2++; + } + return (ends_with_optional_cr(l1, s1, i1) && + ends_with_optional_cr(l2, s2, i2)); } /* @@ -230,9 +257,16 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data, char const *top, long flags) { unsigned long ha = 5381; char const *ptr = *data; + int cr_at_eol_only = (flags & XDF_WHITESPACE_FLAGS) == XDF_IGNORE_CR_AT_EOL; for (; ptr < top && *ptr != '\n'; ptr++) { - if (XDL_ISSPACE(*ptr)) { + if (cr_at_eol_only) { + /* do not ignore CR at the end of an incomplete line */ + if (*ptr == '\r' && + (ptr + 1 < top && ptr[1] == '\n')) + continue; + } + else if (XDL_ISSPACE(*ptr)) { const char *ptr2 = ptr; int at_eol; while (ptr + 1 < top && XDL_ISSPACE(ptr[1]) @@ -264,110 +298,6 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data, return ha; } -#ifdef XDL_FAST_HASH - -#define REPEAT_BYTE(x) ((~0ul / 0xff) * (x)) - -#define ONEBYTES REPEAT_BYTE(0x01) -#define NEWLINEBYTES REPEAT_BYTE(0x0a) -#define HIGHBITS REPEAT_BYTE(0x80) - -/* Return the high bit set in the first byte that is a zero */ -static inline unsigned long has_zero(unsigned long a) -{ - return ((a - ONEBYTES) & ~a) & HIGHBITS; -} - -static inline long count_masked_bytes(unsigned long mask) -{ - if (sizeof(long) == 8) { - /* - * Jan Achrenius on G+: microoptimized version of - * the simpler "(mask & ONEBYTES) * ONEBYTES >> 56" - * that works for the bytemasks without having to - * mask them first. - */ - /* - * return mask * 0x0001020304050608 >> 56; - * - * Doing it like this avoids warnings on 32-bit machines. - */ - long a = (REPEAT_BYTE(0x01) / 0xff + 1); - return mask * a >> (sizeof(long) * 7); - } else { - /* Carl Chatfield / Jan Achrenius G+ version for 32-bit */ - /* (000000 0000ff 00ffff ffffff) -> ( 1 1 2 3 ) */ - long a = (0x0ff0001 + mask) >> 23; - /* Fix the 1 for 00 case */ - return a & mask; - } -} - -unsigned long xdl_hash_record(char const **data, char const *top, long flags) -{ - unsigned long hash = 5381; - unsigned long a = 0, mask = 0; - char const *ptr = *data; - char const *end = top - sizeof(unsigned long) + 1; - - if (flags & XDF_WHITESPACE_FLAGS) - return xdl_hash_record_with_whitespace(data, top, flags); - - ptr -= sizeof(unsigned long); - do { - hash += hash << 5; - hash ^= a; - ptr += sizeof(unsigned long); - if (ptr >= end) - break; - a = *(unsigned long *)ptr; - /* Do we have any '\n' bytes in this word? */ - mask = has_zero(a ^ NEWLINEBYTES); - } while (!mask); - - if (ptr >= end) { - /* - * There is only a partial word left at the end of the - * buffer. Because we may work with a memory mapping, - * we have to grab the rest byte by byte instead of - * blindly reading it. - * - * To avoid problems with masking in a signed value, - * we use an unsigned char here. - */ - const char *p; - for (p = top - 1; p >= ptr; p--) - a = (a << 8) + *((const unsigned char *)p); - mask = has_zero(a ^ NEWLINEBYTES); - if (!mask) - /* - * No '\n' found in the partial word. Make a - * mask that matches what we read. - */ - mask = 1UL << (8 * (top - ptr) + 7); - } - - /* The mask *below* the first high bit set */ - mask = (mask - 1) & ~mask; - mask >>= 7; - hash += hash << 5; - hash ^= a & mask; - - /* Advance past the last (possibly partial) word */ - ptr += count_masked_bytes(mask); - - if (ptr < top) { - assert(*ptr == '\n'); - ptr++; - } - - *data = ptr; - - return hash; -} - -#else /* XDL_FAST_HASH */ - unsigned long xdl_hash_record(char const **data, char const *top, long flags) { unsigned long ha = 5381; char const *ptr = *data; @@ -384,8 +314,6 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) { return ha; } -#endif /* XDL_FAST_HASH */ - unsigned int xdl_hashbits(unsigned int size) { unsigned int val = 1, bits = 0; diff --git a/xdiff/xutils.h b/xdiff/xutils.h index 4646ce5752..fba7bae03c 100644 --- a/xdiff/xutils.h +++ b/xdiff/xutils.h @@ -13,8 +13,8 @@ * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * License along with this library; if not, see + * <http://www.gnu.org/licenses/>. * * Davide Libenzi <davidel@xmailserver.org> * |