summaryrefslogtreecommitdiff
path: root/xdiff
diff options
context:
space:
mode:
Diffstat (limited to 'xdiff')
-rw-r--r--xdiff/xdiff.h34
-rw-r--r--xdiff/xdiffi.c612
-rw-r--r--xdiff/xdiffi.h4
-rw-r--r--xdiff/xemit.c27
-rw-r--r--xdiff/xemit.h4
-rw-r--r--xdiff/xinclude.h4
-rw-r--r--xdiff/xmacros.h4
-rw-r--r--xdiff/xmerge.c4
-rw-r--r--xdiff/xpatience.c48
-rw-r--r--xdiff/xprepare.c4
-rw-r--r--xdiff/xprepare.h4
-rw-r--r--xdiff/xtypes.h4
-rw-r--r--xdiff/xutils.c148
-rw-r--r--xdiff/xutils.h4
14 files changed, 643 insertions, 262 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
index 7423f77fc8..c1937a2911 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,22 +27,28 @@
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)
@@ -80,6 +86,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..0de1ef463b 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>
*
@@ -400,138 +400,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) {
/*
- * 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 has the same indentation level as its predecessor.
+ * No additional adjustments needed.
*/
- ixs = ix;
- for (ix++; rchg[ix]; ix++);
- for (; rchgo[ixo]; ixo++);
+ } else {
+ /*
+ * 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:
+ */
+ 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>
*
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-29 10:12:14 +0000