##// END OF EJS Templates
xdiff: remove whitespace related feature...
Jun Wu -
r36779:09f32006 default
parent child Browse files
Show More
@@ -1,150 +1,139
1 /*
1 /*
2 * LibXDiff by Davide Libenzi ( File Differential Library )
2 * LibXDiff by Davide Libenzi ( File Differential Library )
3 * Copyright (C) 2003 Davide Libenzi
3 * Copyright (C) 2003 Davide Libenzi
4 *
4 *
5 * This library is free software; you can redistribute it and/or
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
8 * version 2.1 of the License, or (at your option) any later version.
9 *
9 *
10 * This library is distributed in the hope that it will be useful,
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
13 * Lesser General Public License for more details.
14 *
14 *
15 * You should have received a copy of the GNU Lesser General Public
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, see
16 * License along with this library; if not, see
17 * <http://www.gnu.org/licenses/>.
17 * <http://www.gnu.org/licenses/>.
18 *
18 *
19 * Davide Libenzi <davidel@xmailserver.org>
19 * Davide Libenzi <davidel@xmailserver.org>
20 *
20 *
21 */
21 */
22
22
23 #if !defined(XDIFF_H)
23 #if !defined(XDIFF_H)
24 #define XDIFF_H
24 #define XDIFF_H
25
25
26 #ifdef __cplusplus
26 #ifdef __cplusplus
27 extern "C" {
27 extern "C" {
28 #endif /* #ifdef __cplusplus */
28 #endif /* #ifdef __cplusplus */
29
29
30 #include <stddef.h> /* size_t */
30 #include <stddef.h> /* size_t */
31
31
32 /* xpparm_t.flags */
32 /* xpparm_t.flags */
33 #define XDF_NEED_MINIMAL (1 << 0)
33 #define XDF_NEED_MINIMAL (1 << 0)
34
34
35 #define XDF_IGNORE_WHITESPACE (1 << 1)
36 #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 2)
37 #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 3)
38 #define XDF_IGNORE_CR_AT_EOL (1 << 4)
39 #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | \
40 XDF_IGNORE_WHITESPACE_CHANGE | \
41 XDF_IGNORE_WHITESPACE_AT_EOL | \
42 XDF_IGNORE_CR_AT_EOL)
43
44 #define XDF_IGNORE_BLANK_LINES (1 << 7)
45
46 #define XDF_INDENT_HEURISTIC (1 << 23)
35 #define XDF_INDENT_HEURISTIC (1 << 23)
47
36
48 /* xdemitconf_t.flags */
37 /* xdemitconf_t.flags */
49 #define XDL_EMIT_FUNCNAMES (1 << 0)
38 #define XDL_EMIT_FUNCNAMES (1 << 0)
50 #define XDL_EMIT_FUNCCONTEXT (1 << 2)
39 #define XDL_EMIT_FUNCCONTEXT (1 << 2)
51 /* emit bdiff-style "matched" (a1, a2, b1, b2) hunks instead of "different"
40 /* emit bdiff-style "matched" (a1, a2, b1, b2) hunks instead of "different"
52 * (a1, a2 - a1, b1, b2 - b1) hunks */
41 * (a1, a2 - a1, b1, b2 - b1) hunks */
53 #define XDL_EMIT_BDIFFHUNK (1 << 4)
42 #define XDL_EMIT_BDIFFHUNK (1 << 4)
54
43
55 #define XDL_MMB_READONLY (1 << 0)
44 #define XDL_MMB_READONLY (1 << 0)
56
45
57 #define XDL_MMF_ATOMIC (1 << 0)
46 #define XDL_MMF_ATOMIC (1 << 0)
58
47
59 #define XDL_BDOP_INS 1
48 #define XDL_BDOP_INS 1
60 #define XDL_BDOP_CPY 2
49 #define XDL_BDOP_CPY 2
61 #define XDL_BDOP_INSB 3
50 #define XDL_BDOP_INSB 3
62
51
63 /* merge simplification levels */
52 /* merge simplification levels */
64 #define XDL_MERGE_MINIMAL 0
53 #define XDL_MERGE_MINIMAL 0
65 #define XDL_MERGE_EAGER 1
54 #define XDL_MERGE_EAGER 1
66 #define XDL_MERGE_ZEALOUS 2
55 #define XDL_MERGE_ZEALOUS 2
67 #define XDL_MERGE_ZEALOUS_ALNUM 3
56 #define XDL_MERGE_ZEALOUS_ALNUM 3
68
57
69 /* merge favor modes */
58 /* merge favor modes */
70 #define XDL_MERGE_FAVOR_OURS 1
59 #define XDL_MERGE_FAVOR_OURS 1
71 #define XDL_MERGE_FAVOR_THEIRS 2
60 #define XDL_MERGE_FAVOR_THEIRS 2
72 #define XDL_MERGE_FAVOR_UNION 3
61 #define XDL_MERGE_FAVOR_UNION 3
73
62
74 /* merge output styles */
63 /* merge output styles */
75 #define XDL_MERGE_DIFF3 1
64 #define XDL_MERGE_DIFF3 1
76
65
77 typedef struct s_mmfile {
66 typedef struct s_mmfile {
78 char *ptr;
67 char *ptr;
79 long size;
68 long size;
80 } mmfile_t;
69 } mmfile_t;
81
70
82 typedef struct s_mmbuffer {
71 typedef struct s_mmbuffer {
83 char *ptr;
72 char *ptr;
84 long size;
73 long size;
85 } mmbuffer_t;
74 } mmbuffer_t;
86
75
87 typedef struct s_xpparam {
76 typedef struct s_xpparam {
88 unsigned long flags;
77 unsigned long flags;
89
78
90 /* See Documentation/diff-options.txt. */
79 /* See Documentation/diff-options.txt. */
91 char **anchors;
80 char **anchors;
92 size_t anchors_nr;
81 size_t anchors_nr;
93 } xpparam_t;
82 } xpparam_t;
94
83
95 typedef struct s_xdemitcb {
84 typedef struct s_xdemitcb {
96 void *priv;
85 void *priv;
97 int (*outf)(void *, mmbuffer_t *, int);
86 int (*outf)(void *, mmbuffer_t *, int);
98 } xdemitcb_t;
87 } xdemitcb_t;
99
88
100 typedef long (*find_func_t)(const char *line, long line_len, char *buffer, long buffer_size, void *priv);
89 typedef long (*find_func_t)(const char *line, long line_len, char *buffer, long buffer_size, void *priv);
101
90
102 typedef int (*xdl_emit_hunk_consume_func_t)(long start_a, long count_a,
91 typedef int (*xdl_emit_hunk_consume_func_t)(long start_a, long count_a,
103 long start_b, long count_b,
92 long start_b, long count_b,
104 void *cb_data);
93 void *cb_data);
105
94
106 typedef struct s_xdemitconf {
95 typedef struct s_xdemitconf {
107 long ctxlen;
96 long ctxlen;
108 long interhunkctxlen;
97 long interhunkctxlen;
109 unsigned long flags;
98 unsigned long flags;
110 find_func_t find_func;
99 find_func_t find_func;
111 void *find_func_priv;
100 void *find_func_priv;
112 xdl_emit_hunk_consume_func_t hunk_func;
101 xdl_emit_hunk_consume_func_t hunk_func;
113 } xdemitconf_t;
102 } xdemitconf_t;
114
103
115 typedef struct s_bdiffparam {
104 typedef struct s_bdiffparam {
116 long bsize;
105 long bsize;
117 } bdiffparam_t;
106 } bdiffparam_t;
118
107
119
108
120 #define xdl_malloc(x) malloc(x)
109 #define xdl_malloc(x) malloc(x)
121 #define xdl_free(ptr) free(ptr)
110 #define xdl_free(ptr) free(ptr)
122 #define xdl_realloc(ptr,x) realloc(ptr,x)
111 #define xdl_realloc(ptr,x) realloc(ptr,x)
123
112
124 void *xdl_mmfile_first(mmfile_t *mmf, long *size);
113 void *xdl_mmfile_first(mmfile_t *mmf, long *size);
125 long xdl_mmfile_size(mmfile_t *mmf);
114 long xdl_mmfile_size(mmfile_t *mmf);
126
115
127 int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
116 int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
128 xdemitconf_t const *xecfg, xdemitcb_t *ecb);
117 xdemitconf_t const *xecfg, xdemitcb_t *ecb);
129
118
130 typedef struct s_xmparam {
119 typedef struct s_xmparam {
131 xpparam_t xpp;
120 xpparam_t xpp;
132 int marker_size;
121 int marker_size;
133 int level;
122 int level;
134 int favor;
123 int favor;
135 int style;
124 int style;
136 const char *ancestor; /* label for orig */
125 const char *ancestor; /* label for orig */
137 const char *file1; /* label for mf1 */
126 const char *file1; /* label for mf1 */
138 const char *file2; /* label for mf2 */
127 const char *file2; /* label for mf2 */
139 } xmparam_t;
128 } xmparam_t;
140
129
141 #define DEFAULT_CONFLICT_MARKER_SIZE 7
130 #define DEFAULT_CONFLICT_MARKER_SIZE 7
142
131
143 int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
132 int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
144 xmparam_t const *xmp, mmbuffer_t *result);
133 xmparam_t const *xmp, mmbuffer_t *result);
145
134
146 #ifdef __cplusplus
135 #ifdef __cplusplus
147 }
136 }
148 #endif /* #ifdef __cplusplus */
137 #endif /* #ifdef __cplusplus */
149
138
150 #endif /* #if !defined(XDIFF_H) */
139 #endif /* #if !defined(XDIFF_H) */
@@ -1,1094 +1,1071
1 /*
1 /*
2 * LibXDiff by Davide Libenzi ( File Differential Library )
2 * LibXDiff by Davide Libenzi ( File Differential Library )
3 * Copyright (C) 2003 Davide Libenzi
3 * Copyright (C) 2003 Davide Libenzi
4 *
4 *
5 * This library is free software; you can redistribute it and/or
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
8 * version 2.1 of the License, or (at your option) any later version.
9 *
9 *
10 * This library is distributed in the hope that it will be useful,
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
13 * Lesser General Public License for more details.
14 *
14 *
15 * You should have received a copy of the GNU Lesser General Public
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, see
16 * License along with this library; if not, see
17 * <http://www.gnu.org/licenses/>.
17 * <http://www.gnu.org/licenses/>.
18 *
18 *
19 * Davide Libenzi <davidel@xmailserver.org>
19 * Davide Libenzi <davidel@xmailserver.org>
20 *
20 *
21 */
21 */
22
22
23 #include "xinclude.h"
23 #include "xinclude.h"
24
24
25
25
26
26
27 #define XDL_MAX_COST_MIN 256
27 #define XDL_MAX_COST_MIN 256
28 #define XDL_HEUR_MIN_COST 256
28 #define XDL_HEUR_MIN_COST 256
29 #define XDL_LINE_MAX (long)((1UL << (CHAR_BIT * sizeof(long) - 1)) - 1)
29 #define XDL_LINE_MAX (long)((1UL << (CHAR_BIT * sizeof(long) - 1)) - 1)
30 #define XDL_SNAKE_CNT 20
30 #define XDL_SNAKE_CNT 20
31 #define XDL_K_HEUR 4
31 #define XDL_K_HEUR 4
32
32
33 /* VC 2008 doesn't know about the inline keyword. */
33 /* VC 2008 doesn't know about the inline keyword. */
34 #if defined(_MSC_VER)
34 #if defined(_MSC_VER)
35 #define inline __forceinline
35 #define inline __forceinline
36 #endif
36 #endif
37
37
38
38
39 typedef struct s_xdpsplit {
39 typedef struct s_xdpsplit {
40 long i1, i2;
40 long i1, i2;
41 int min_lo, min_hi;
41 int min_lo, min_hi;
42 } xdpsplit_t;
42 } xdpsplit_t;
43
43
44
44
45
45
46
46
47 static long xdl_split(unsigned long const *ha1, long off1, long lim1,
47 static long xdl_split(unsigned long const *ha1, long off1, long lim1,
48 unsigned long const *ha2, long off2, long lim2,
48 unsigned long const *ha2, long off2, long lim2,
49 long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,
49 long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,
50 xdalgoenv_t *xenv);
50 xdalgoenv_t *xenv);
51 static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2);
51 static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2);
52
52
53
53
54
54
55
55
56
56
57 /*
57 /*
58 * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
58 * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
59 * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
59 * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
60 * the forward diagonal starting from (off1, off2) and the backward diagonal
60 * the forward diagonal starting from (off1, off2) and the backward diagonal
61 * starting from (lim1, lim2). If the K values on the same diagonal crosses
61 * starting from (lim1, lim2). If the K values on the same diagonal crosses
62 * returns the furthest point of reach. We might end up having to expensive
62 * returns the furthest point of reach. We might end up having to expensive
63 * cases using this algorithm is full, so a little bit of heuristic is needed
63 * cases using this algorithm is full, so a little bit of heuristic is needed
64 * to cut the search and to return a suboptimal point.
64 * to cut the search and to return a suboptimal point.
65 */
65 */
66 static long xdl_split(unsigned long const *ha1, long off1, long lim1,
66 static long xdl_split(unsigned long const *ha1, long off1, long lim1,
67 unsigned long const *ha2, long off2, long lim2,
67 unsigned long const *ha2, long off2, long lim2,
68 long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,
68 long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,
69 xdalgoenv_t *xenv) {
69 xdalgoenv_t *xenv) {
70 long dmin = off1 - lim2, dmax = lim1 - off2;
70 long dmin = off1 - lim2, dmax = lim1 - off2;
71 long fmid = off1 - off2, bmid = lim1 - lim2;
71 long fmid = off1 - off2, bmid = lim1 - lim2;
72 long odd = (fmid - bmid) & 1;
72 long odd = (fmid - bmid) & 1;
73 long fmin = fmid, fmax = fmid;
73 long fmin = fmid, fmax = fmid;
74 long bmin = bmid, bmax = bmid;
74 long bmin = bmid, bmax = bmid;
75 long ec, d, i1, i2, prev1, best, dd, v, k;
75 long ec, d, i1, i2, prev1, best, dd, v, k;
76
76
77 /*
77 /*
78 * Set initial diagonal values for both forward and backward path.
78 * Set initial diagonal values for both forward and backward path.
79 */
79 */
80 kvdf[fmid] = off1;
80 kvdf[fmid] = off1;
81 kvdb[bmid] = lim1;
81 kvdb[bmid] = lim1;
82
82
83 for (ec = 1;; ec++) {
83 for (ec = 1;; ec++) {
84 int got_snake = 0;
84 int got_snake = 0;
85
85
86 /*
86 /*
87 * We need to extent the diagonal "domain" by one. If the next
87 * We need to extent the diagonal "domain" by one. If the next
88 * values exits the box boundaries we need to change it in the
88 * values exits the box boundaries we need to change it in the
89 * opposite direction because (max - min) must be a power of two.
89 * opposite direction because (max - min) must be a power of two.
90 * Also we initialize the external K value to -1 so that we can
90 * Also we initialize the external K value to -1 so that we can
91 * avoid extra conditions check inside the core loop.
91 * avoid extra conditions check inside the core loop.
92 */
92 */
93 if (fmin > dmin)
93 if (fmin > dmin)
94 kvdf[--fmin - 1] = -1;
94 kvdf[--fmin - 1] = -1;
95 else
95 else
96 ++fmin;
96 ++fmin;
97 if (fmax < dmax)
97 if (fmax < dmax)
98 kvdf[++fmax + 1] = -1;
98 kvdf[++fmax + 1] = -1;
99 else
99 else
100 --fmax;
100 --fmax;
101
101
102 for (d = fmax; d >= fmin; d -= 2) {
102 for (d = fmax; d >= fmin; d -= 2) {
103 if (kvdf[d - 1] >= kvdf[d + 1])
103 if (kvdf[d - 1] >= kvdf[d + 1])
104 i1 = kvdf[d - 1] + 1;
104 i1 = kvdf[d - 1] + 1;
105 else
105 else
106 i1 = kvdf[d + 1];
106 i1 = kvdf[d + 1];
107 prev1 = i1;
107 prev1 = i1;
108 i2 = i1 - d;
108 i2 = i1 - d;
109 for (; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++, i2++);
109 for (; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++, i2++);
110 if (i1 - prev1 > xenv->snake_cnt)
110 if (i1 - prev1 > xenv->snake_cnt)
111 got_snake = 1;
111 got_snake = 1;
112 kvdf[d] = i1;
112 kvdf[d] = i1;
113 if (odd && bmin <= d && d <= bmax && kvdb[d] <= i1) {
113 if (odd && bmin <= d && d <= bmax && kvdb[d] <= i1) {
114 spl->i1 = i1;
114 spl->i1 = i1;
115 spl->i2 = i2;
115 spl->i2 = i2;
116 spl->min_lo = spl->min_hi = 1;
116 spl->min_lo = spl->min_hi = 1;
117 return ec;
117 return ec;
118 }
118 }
119 }
119 }
120
120
121 /*
121 /*
122 * We need to extent the diagonal "domain" by one. If the next
122 * We need to extent the diagonal "domain" by one. If the next
123 * values exits the box boundaries we need to change it in the
123 * values exits the box boundaries we need to change it in the
124 * opposite direction because (max - min) must be a power of two.
124 * opposite direction because (max - min) must be a power of two.
125 * Also we initialize the external K value to -1 so that we can
125 * Also we initialize the external K value to -1 so that we can
126 * avoid extra conditions check inside the core loop.
126 * avoid extra conditions check inside the core loop.
127 */
127 */
128 if (bmin > dmin)
128 if (bmin > dmin)
129 kvdb[--bmin - 1] = XDL_LINE_MAX;
129 kvdb[--bmin - 1] = XDL_LINE_MAX;
130 else
130 else
131 ++bmin;
131 ++bmin;
132 if (bmax < dmax)
132 if (bmax < dmax)
133 kvdb[++bmax + 1] = XDL_LINE_MAX;
133 kvdb[++bmax + 1] = XDL_LINE_MAX;
134 else
134 else
135 --bmax;
135 --bmax;
136
136
137 for (d = bmax; d >= bmin; d -= 2) {
137 for (d = bmax; d >= bmin; d -= 2) {
138 if (kvdb[d - 1] < kvdb[d + 1])
138 if (kvdb[d - 1] < kvdb[d + 1])
139 i1 = kvdb[d - 1];
139 i1 = kvdb[d - 1];
140 else
140 else
141 i1 = kvdb[d + 1] - 1;
141 i1 = kvdb[d + 1] - 1;
142 prev1 = i1;
142 prev1 = i1;
143 i2 = i1 - d;
143 i2 = i1 - d;
144 for (; i1 > off1 && i2 > off2 && ha1[i1 - 1] == ha2[i2 - 1]; i1--, i2--);
144 for (; i1 > off1 && i2 > off2 && ha1[i1 - 1] == ha2[i2 - 1]; i1--, i2--);
145 if (prev1 - i1 > xenv->snake_cnt)
145 if (prev1 - i1 > xenv->snake_cnt)
146 got_snake = 1;
146 got_snake = 1;
147 kvdb[d] = i1;
147 kvdb[d] = i1;
148 if (!odd && fmin <= d && d <= fmax && i1 <= kvdf[d]) {
148 if (!odd && fmin <= d && d <= fmax && i1 <= kvdf[d]) {
149 spl->i1 = i1;
149 spl->i1 = i1;
150 spl->i2 = i2;
150 spl->i2 = i2;
151 spl->min_lo = spl->min_hi = 1;
151 spl->min_lo = spl->min_hi = 1;
152 return ec;
152 return ec;
153 }
153 }
154 }
154 }
155
155
156 if (need_min)
156 if (need_min)
157 continue;
157 continue;
158
158
159 /*
159 /*
160 * If the edit cost is above the heuristic trigger and if
160 * If the edit cost is above the heuristic trigger and if
161 * we got a good snake, we sample current diagonals to see
161 * we got a good snake, we sample current diagonals to see
162 * if some of the, have reached an "interesting" path. Our
162 * if some of the, have reached an "interesting" path. Our
163 * measure is a function of the distance from the diagonal
163 * measure is a function of the distance from the diagonal
164 * corner (i1 + i2) penalized with the distance from the
164 * corner (i1 + i2) penalized with the distance from the
165 * mid diagonal itself. If this value is above the current
165 * mid diagonal itself. If this value is above the current
166 * edit cost times a magic factor (XDL_K_HEUR) we consider
166 * edit cost times a magic factor (XDL_K_HEUR) we consider
167 * it interesting.
167 * it interesting.
168 */
168 */
169 if (got_snake && ec > xenv->heur_min) {
169 if (got_snake && ec > xenv->heur_min) {
170 for (best = 0, d = fmax; d >= fmin; d -= 2) {
170 for (best = 0, d = fmax; d >= fmin; d -= 2) {
171 dd = d > fmid ? d - fmid: fmid - d;
171 dd = d > fmid ? d - fmid: fmid - d;
172 i1 = kvdf[d];
172 i1 = kvdf[d];
173 i2 = i1 - d;
173 i2 = i1 - d;
174 v = (i1 - off1) + (i2 - off2) - dd;
174 v = (i1 - off1) + (i2 - off2) - dd;
175
175
176 if (v > XDL_K_HEUR * ec && v > best &&
176 if (v > XDL_K_HEUR * ec && v > best &&
177 off1 + xenv->snake_cnt <= i1 && i1 < lim1 &&
177 off1 + xenv->snake_cnt <= i1 && i1 < lim1 &&
178 off2 + xenv->snake_cnt <= i2 && i2 < lim2) {
178 off2 + xenv->snake_cnt <= i2 && i2 < lim2) {
179 for (k = 1; ha1[i1 - k] == ha2[i2 - k]; k++)
179 for (k = 1; ha1[i1 - k] == ha2[i2 - k]; k++)
180 if (k == xenv->snake_cnt) {
180 if (k == xenv->snake_cnt) {
181 best = v;
181 best = v;
182 spl->i1 = i1;
182 spl->i1 = i1;
183 spl->i2 = i2;
183 spl->i2 = i2;
184 break;
184 break;
185 }
185 }
186 }
186 }
187 }
187 }
188 if (best > 0) {
188 if (best > 0) {
189 spl->min_lo = 1;
189 spl->min_lo = 1;
190 spl->min_hi = 0;
190 spl->min_hi = 0;
191 return ec;
191 return ec;
192 }
192 }
193
193
194 for (best = 0, d = bmax; d >= bmin; d -= 2) {
194 for (best = 0, d = bmax; d >= bmin; d -= 2) {
195 dd = d > bmid ? d - bmid: bmid - d;
195 dd = d > bmid ? d - bmid: bmid - d;
196 i1 = kvdb[d];
196 i1 = kvdb[d];
197 i2 = i1 - d;
197 i2 = i1 - d;
198 v = (lim1 - i1) + (lim2 - i2) - dd;
198 v = (lim1 - i1) + (lim2 - i2) - dd;
199
199
200 if (v > XDL_K_HEUR * ec && v > best &&
200 if (v > XDL_K_HEUR * ec && v > best &&
201 off1 < i1 && i1 <= lim1 - xenv->snake_cnt &&
201 off1 < i1 && i1 <= lim1 - xenv->snake_cnt &&
202 off2 < i2 && i2 <= lim2 - xenv->snake_cnt) {
202 off2 < i2 && i2 <= lim2 - xenv->snake_cnt) {
203 for (k = 0; ha1[i1 + k] == ha2[i2 + k]; k++)
203 for (k = 0; ha1[i1 + k] == ha2[i2 + k]; k++)
204 if (k == xenv->snake_cnt - 1) {
204 if (k == xenv->snake_cnt - 1) {
205 best = v;
205 best = v;
206 spl->i1 = i1;
206 spl->i1 = i1;
207 spl->i2 = i2;
207 spl->i2 = i2;
208 break;
208 break;
209 }
209 }
210 }
210 }
211 }
211 }
212 if (best > 0) {
212 if (best > 0) {
213 spl->min_lo = 0;
213 spl->min_lo = 0;
214 spl->min_hi = 1;
214 spl->min_hi = 1;
215 return ec;
215 return ec;
216 }
216 }
217 }
217 }
218
218
219 /*
219 /*
220 * Enough is enough. We spent too much time here and now we collect
220 * Enough is enough. We spent too much time here and now we collect
221 * the furthest reaching path using the (i1 + i2) measure.
221 * the furthest reaching path using the (i1 + i2) measure.
222 */
222 */
223 if (ec >= xenv->mxcost) {
223 if (ec >= xenv->mxcost) {
224 long fbest, fbest1, bbest, bbest1;
224 long fbest, fbest1, bbest, bbest1;
225
225
226 fbest = fbest1 = -1;
226 fbest = fbest1 = -1;
227 for (d = fmax; d >= fmin; d -= 2) {
227 for (d = fmax; d >= fmin; d -= 2) {
228 i1 = XDL_MIN(kvdf[d], lim1);
228 i1 = XDL_MIN(kvdf[d], lim1);
229 i2 = i1 - d;
229 i2 = i1 - d;
230 if (lim2 < i2)
230 if (lim2 < i2)
231 i1 = lim2 + d, i2 = lim2;
231 i1 = lim2 + d, i2 = lim2;
232 if (fbest < i1 + i2) {
232 if (fbest < i1 + i2) {
233 fbest = i1 + i2;
233 fbest = i1 + i2;
234 fbest1 = i1;
234 fbest1 = i1;
235 }
235 }
236 }
236 }
237
237
238 bbest = bbest1 = XDL_LINE_MAX;
238 bbest = bbest1 = XDL_LINE_MAX;
239 for (d = bmax; d >= bmin; d -= 2) {
239 for (d = bmax; d >= bmin; d -= 2) {
240 i1 = XDL_MAX(off1, kvdb[d]);
240 i1 = XDL_MAX(off1, kvdb[d]);
241 i2 = i1 - d;
241 i2 = i1 - d;
242 if (i2 < off2)
242 if (i2 < off2)
243 i1 = off2 + d, i2 = off2;
243 i1 = off2 + d, i2 = off2;
244 if (i1 + i2 < bbest) {
244 if (i1 + i2 < bbest) {
245 bbest = i1 + i2;
245 bbest = i1 + i2;
246 bbest1 = i1;
246 bbest1 = i1;
247 }
247 }
248 }
248 }
249
249
250 if ((lim1 + lim2) - bbest < fbest - (off1 + off2)) {
250 if ((lim1 + lim2) - bbest < fbest - (off1 + off2)) {
251 spl->i1 = fbest1;
251 spl->i1 = fbest1;
252 spl->i2 = fbest - fbest1;
252 spl->i2 = fbest - fbest1;
253 spl->min_lo = 1;
253 spl->min_lo = 1;
254 spl->min_hi = 0;
254 spl->min_hi = 0;
255 } else {
255 } else {
256 spl->i1 = bbest1;
256 spl->i1 = bbest1;
257 spl->i2 = bbest - bbest1;
257 spl->i2 = bbest - bbest1;
258 spl->min_lo = 0;
258 spl->min_lo = 0;
259 spl->min_hi = 1;
259 spl->min_hi = 1;
260 }
260 }
261 return ec;
261 return ec;
262 }
262 }
263 }
263 }
264 }
264 }
265
265
266
266
267 /*
267 /*
268 * Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling
268 * Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling
269 * the box splitting function. Note that the real job (marking changed lines)
269 * the box splitting function. Note that the real job (marking changed lines)
270 * is done in the two boundary reaching checks.
270 * is done in the two boundary reaching checks.
271 */
271 */
272 int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,
272 int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,
273 diffdata_t *dd2, long off2, long lim2,
273 diffdata_t *dd2, long off2, long lim2,
274 long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) {
274 long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) {
275 unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha;
275 unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha;
276
276
277 /*
277 /*
278 * Shrink the box by walking through each diagonal snake (SW and NE).
278 * Shrink the box by walking through each diagonal snake (SW and NE).
279 */
279 */
280 for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++);
280 for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++);
281 for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--);
281 for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--);
282
282
283 /*
283 /*
284 * If one dimension is empty, then all records on the other one must
284 * If one dimension is empty, then all records on the other one must
285 * be obviously changed.
285 * be obviously changed.
286 */
286 */
287 if (off1 == lim1) {
287 if (off1 == lim1) {
288 char *rchg2 = dd2->rchg;
288 char *rchg2 = dd2->rchg;
289 long *rindex2 = dd2->rindex;
289 long *rindex2 = dd2->rindex;
290
290
291 for (; off2 < lim2; off2++)
291 for (; off2 < lim2; off2++)
292 rchg2[rindex2[off2]] = 1;
292 rchg2[rindex2[off2]] = 1;
293 } else if (off2 == lim2) {
293 } else if (off2 == lim2) {
294 char *rchg1 = dd1->rchg;
294 char *rchg1 = dd1->rchg;
295 long *rindex1 = dd1->rindex;
295 long *rindex1 = dd1->rindex;
296
296
297 for (; off1 < lim1; off1++)
297 for (; off1 < lim1; off1++)
298 rchg1[rindex1[off1]] = 1;
298 rchg1[rindex1[off1]] = 1;
299 } else {
299 } else {
300 xdpsplit_t spl;
300 xdpsplit_t spl;
301 spl.i1 = spl.i2 = 0;
301 spl.i1 = spl.i2 = 0;
302
302
303 /*
303 /*
304 * Divide ...
304 * Divide ...
305 */
305 */
306 if (xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,
306 if (xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,
307 need_min, &spl, xenv) < 0) {
307 need_min, &spl, xenv) < 0) {
308
308
309 return -1;
309 return -1;
310 }
310 }
311
311
312 /*
312 /*
313 * ... et Impera.
313 * ... et Impera.
314 */
314 */
315 if (xdl_recs_cmp(dd1, off1, spl.i1, dd2, off2, spl.i2,
315 if (xdl_recs_cmp(dd1, off1, spl.i1, dd2, off2, spl.i2,
316 kvdf, kvdb, spl.min_lo, xenv) < 0 ||
316 kvdf, kvdb, spl.min_lo, xenv) < 0 ||
317 xdl_recs_cmp(dd1, spl.i1, lim1, dd2, spl.i2, lim2,
317 xdl_recs_cmp(dd1, spl.i1, lim1, dd2, spl.i2, lim2,
318 kvdf, kvdb, spl.min_hi, xenv) < 0) {
318 kvdf, kvdb, spl.min_hi, xenv) < 0) {
319
319
320 return -1;
320 return -1;
321 }
321 }
322 }
322 }
323
323
324 return 0;
324 return 0;
325 }
325 }
326
326
327
327
328 int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
328 int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
329 xdfenv_t *xe) {
329 xdfenv_t *xe) {
330 long ndiags;
330 long ndiags;
331 long *kvd, *kvdf, *kvdb;
331 long *kvd, *kvdf, *kvdb;
332 xdalgoenv_t xenv;
332 xdalgoenv_t xenv;
333 diffdata_t dd1, dd2;
333 diffdata_t dd1, dd2;
334
334
335 if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
335 if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
336
336
337 return -1;
337 return -1;
338 }
338 }
339
339
340 /*
340 /*
341 * Allocate and setup K vectors to be used by the differential algorithm.
341 * Allocate and setup K vectors to be used by the differential algorithm.
342 * One is to store the forward path and one to store the backward path.
342 * One is to store the forward path and one to store the backward path.
343 */
343 */
344 ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
344 ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
345 if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {
345 if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {
346
346
347 xdl_free_env(xe);
347 xdl_free_env(xe);
348 return -1;
348 return -1;
349 }
349 }
350 kvdf = kvd;
350 kvdf = kvd;
351 kvdb = kvdf + ndiags;
351 kvdb = kvdf + ndiags;
352 kvdf += xe->xdf2.nreff + 1;
352 kvdf += xe->xdf2.nreff + 1;
353 kvdb += xe->xdf2.nreff + 1;
353 kvdb += xe->xdf2.nreff + 1;
354
354
355 xenv.mxcost = xdl_bogosqrt(ndiags);
355 xenv.mxcost = xdl_bogosqrt(ndiags);
356 if (xenv.mxcost < XDL_MAX_COST_MIN)
356 if (xenv.mxcost < XDL_MAX_COST_MIN)
357 xenv.mxcost = XDL_MAX_COST_MIN;
357 xenv.mxcost = XDL_MAX_COST_MIN;
358 xenv.snake_cnt = XDL_SNAKE_CNT;
358 xenv.snake_cnt = XDL_SNAKE_CNT;
359 xenv.heur_min = XDL_HEUR_MIN_COST;
359 xenv.heur_min = XDL_HEUR_MIN_COST;
360
360
361 dd1.nrec = xe->xdf1.nreff;
361 dd1.nrec = xe->xdf1.nreff;
362 dd1.ha = xe->xdf1.ha;
362 dd1.ha = xe->xdf1.ha;
363 dd1.rchg = xe->xdf1.rchg;
363 dd1.rchg = xe->xdf1.rchg;
364 dd1.rindex = xe->xdf1.rindex;
364 dd1.rindex = xe->xdf1.rindex;
365 dd2.nrec = xe->xdf2.nreff;
365 dd2.nrec = xe->xdf2.nreff;
366 dd2.ha = xe->xdf2.ha;
366 dd2.ha = xe->xdf2.ha;
367 dd2.rchg = xe->xdf2.rchg;
367 dd2.rchg = xe->xdf2.rchg;
368 dd2.rindex = xe->xdf2.rindex;
368 dd2.rindex = xe->xdf2.rindex;
369
369
370 if (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
370 if (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
371 kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) {
371 kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) {
372
372
373 xdl_free(kvd);
373 xdl_free(kvd);
374 xdl_free_env(xe);
374 xdl_free_env(xe);
375 return -1;
375 return -1;
376 }
376 }
377
377
378 xdl_free(kvd);
378 xdl_free(kvd);
379
379
380 return 0;
380 return 0;
381 }
381 }
382
382
383
383
384 static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) {
384 static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) {
385 xdchange_t *xch;
385 xdchange_t *xch;
386
386
387 if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t))))
387 if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t))))
388 return NULL;
388 return NULL;
389
389
390 xch->next = xscr;
390 xch->next = xscr;
391 xch->i1 = i1;
391 xch->i1 = i1;
392 xch->i2 = i2;
392 xch->i2 = i2;
393 xch->chg1 = chg1;
393 xch->chg1 = chg1;
394 xch->chg2 = chg2;
394 xch->chg2 = chg2;
395 xch->ignore = 0;
395 xch->ignore = 0;
396
396
397 return xch;
397 return xch;
398 }
398 }
399
399
400
400
401 static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)
401 static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags)
402 {
402 {
403 return (rec1->ha == rec2->ha &&
403 return (rec1->ha == rec2->ha &&
404 xdl_recmatch(rec1->ptr, rec1->size,
404 xdl_recmatch(rec1->ptr, rec1->size,
405 rec2->ptr, rec2->size,
405 rec2->ptr, rec2->size,
406 flags));
406 flags));
407 }
407 }
408
408
409 /*
409 /*
410 * If a line is indented more than this, get_indent() just returns this value.
410 * If a line is indented more than this, get_indent() just returns this value.
411 * This avoids having to do absurd amounts of work for data that are not
411 * This avoids having to do absurd amounts of work for data that are not
412 * human-readable text, and also ensures that the output of get_indent fits within
412 * human-readable text, and also ensures that the output of get_indent fits within
413 * an int.
413 * an int.
414 */
414 */
415 #define MAX_INDENT 200
415 #define MAX_INDENT 200
416
416
417 /*
417 /*
418 * Return the amount of indentation of the specified line, treating TAB as 8
418 * Return the amount of indentation of the specified line, treating TAB as 8
419 * columns. Return -1 if line is empty or contains only whitespace. Clamp the
419 * columns. Return -1 if line is empty or contains only whitespace. Clamp the
420 * output value at MAX_INDENT.
420 * output value at MAX_INDENT.
421 */
421 */
422 static int get_indent(xrecord_t *rec)
422 static int get_indent(xrecord_t *rec)
423 {
423 {
424 long i;
424 long i;
425 int ret = 0;
425 int ret = 0;
426
426
427 for (i = 0; i < rec->size; i++) {
427 for (i = 0; i < rec->size; i++) {
428 char c = rec->ptr[i];
428 char c = rec->ptr[i];
429
429
430 if (!XDL_ISSPACE(c))
430 if (!XDL_ISSPACE(c))
431 return ret;
431 return ret;
432 else if (c == ' ')
432 else if (c == ' ')
433 ret += 1;
433 ret += 1;
434 else if (c == '\t')
434 else if (c == '\t')
435 ret += 8 - ret % 8;
435 ret += 8 - ret % 8;
436 /* ignore other whitespace characters */
436 /* ignore other whitespace characters */
437
437
438 if (ret >= MAX_INDENT)
438 if (ret >= MAX_INDENT)
439 return MAX_INDENT;
439 return MAX_INDENT;
440 }
440 }
441
441
442 /* The line contains only whitespace. */
442 /* The line contains only whitespace. */
443 return -1;
443 return -1;
444 }
444 }
445
445
446 /*
446 /*
447 * If more than this number of consecutive blank rows are found, just return this
447 * If more than this number of consecutive blank rows are found, just return this
448 * value. This avoids requiring O(N^2) work for pathological cases, and also
448 * value. This avoids requiring O(N^2) work for pathological cases, and also
449 * ensures that the output of score_split fits in an int.
449 * ensures that the output of score_split fits in an int.
450 */
450 */
451 #define MAX_BLANKS 20
451 #define MAX_BLANKS 20
452
452
453 /* Characteristics measured about a hypothetical split position. */
453 /* Characteristics measured about a hypothetical split position. */
454 struct split_measurement {
454 struct split_measurement {
455 /*
455 /*
456 * Is the split at the end of the file (aside from any blank lines)?
456 * Is the split at the end of the file (aside from any blank lines)?
457 */
457 */
458 int end_of_file;
458 int end_of_file;
459
459
460 /*
460 /*
461 * How much is the line immediately following the split indented (or -1 if
461 * How much is the line immediately following the split indented (or -1 if
462 * the line is blank):
462 * the line is blank):
463 */
463 */
464 int indent;
464 int indent;
465
465
466 /*
466 /*
467 * How many consecutive lines above the split are blank?
467 * How many consecutive lines above the split are blank?
468 */
468 */
469 int pre_blank;
469 int pre_blank;
470
470
471 /*
471 /*
472 * How much is the nearest non-blank line above the split indented (or -1
472 * How much is the nearest non-blank line above the split indented (or -1
473 * if there is no such line)?
473 * if there is no such line)?
474 */
474 */
475 int pre_indent;
475 int pre_indent;
476
476
477 /*
477 /*
478 * How many lines after the line following the split are blank?
478 * How many lines after the line following the split are blank?
479 */
479 */
480 int post_blank;
480 int post_blank;
481
481
482 /*
482 /*
483 * How much is the nearest non-blank line after the line following the
483 * How much is the nearest non-blank line after the line following the
484 * split indented (or -1 if there is no such line)?
484 * split indented (or -1 if there is no such line)?
485 */
485 */
486 int post_indent;
486 int post_indent;
487 };
487 };
488
488
489 struct split_score {
489 struct split_score {
490 /* The effective indent of this split (smaller is preferred). */
490 /* The effective indent of this split (smaller is preferred). */
491 int effective_indent;
491 int effective_indent;
492
492
493 /* Penalty for this split (smaller is preferred). */
493 /* Penalty for this split (smaller is preferred). */
494 int penalty;
494 int penalty;
495 };
495 };
496
496
497 /*
497 /*
498 * Fill m with information about a hypothetical split of xdf above line split.
498 * Fill m with information about a hypothetical split of xdf above line split.
499 */
499 */
500 static void measure_split(const xdfile_t *xdf, long split,
500 static void measure_split(const xdfile_t *xdf, long split,
501 struct split_measurement *m)
501 struct split_measurement *m)
502 {
502 {
503 long i;
503 long i;
504
504
505 if (split >= xdf->nrec) {
505 if (split >= xdf->nrec) {
506 m->end_of_file = 1;
506 m->end_of_file = 1;
507 m->indent = -1;
507 m->indent = -1;
508 } else {
508 } else {
509 m->end_of_file = 0;
509 m->end_of_file = 0;
510 m->indent = get_indent(xdf->recs[split]);
510 m->indent = get_indent(xdf->recs[split]);
511 }
511 }
512
512
513 m->pre_blank = 0;
513 m->pre_blank = 0;
514 m->pre_indent = -1;
514 m->pre_indent = -1;
515 for (i = split - 1; i >= 0; i--) {
515 for (i = split - 1; i >= 0; i--) {
516 m->pre_indent = get_indent(xdf->recs[i]);
516 m->pre_indent = get_indent(xdf->recs[i]);
517 if (m->pre_indent != -1)
517 if (m->pre_indent != -1)
518 break;
518 break;
519 m->pre_blank += 1;
519 m->pre_blank += 1;
520 if (m->pre_blank == MAX_BLANKS) {
520 if (m->pre_blank == MAX_BLANKS) {
521 m->pre_indent = 0;
521 m->pre_indent = 0;
522 break;
522 break;
523 }
523 }
524 }
524 }
525
525
526 m->post_blank = 0;
526 m->post_blank = 0;
527 m->post_indent = -1;
527 m->post_indent = -1;
528 for (i = split + 1; i < xdf->nrec; i++) {
528 for (i = split + 1; i < xdf->nrec; i++) {
529 m->post_indent = get_indent(xdf->recs[i]);
529 m->post_indent = get_indent(xdf->recs[i]);
530 if (m->post_indent != -1)
530 if (m->post_indent != -1)
531 break;
531 break;
532 m->post_blank += 1;
532 m->post_blank += 1;
533 if (m->post_blank == MAX_BLANKS) {
533 if (m->post_blank == MAX_BLANKS) {
534 m->post_indent = 0;
534 m->post_indent = 0;
535 break;
535 break;
536 }
536 }
537 }
537 }
538 }
538 }
539
539
540 /*
540 /*
541 * The empirically-determined weight factors used by score_split() below.
541 * The empirically-determined weight factors used by score_split() below.
542 * Larger values means that the position is a less favorable place to split.
542 * Larger values means that the position is a less favorable place to split.
543 *
543 *
544 * Note that scores are only ever compared against each other, so multiplying
544 * Note that scores are only ever compared against each other, so multiplying
545 * all of these weight/penalty values by the same factor wouldn't change the
545 * all of these weight/penalty values by the same factor wouldn't change the
546 * heuristic's behavior. Still, we need to set that arbitrary scale *somehow*.
546 * heuristic's behavior. Still, we need to set that arbitrary scale *somehow*.
547 * In practice, these numbers are chosen to be large enough that they can be
547 * In practice, these numbers are chosen to be large enough that they can be
548 * adjusted relative to each other with sufficient precision despite using
548 * adjusted relative to each other with sufficient precision despite using
549 * integer math.
549 * integer math.
550 */
550 */
551
551
552 /* Penalty if there are no non-blank lines before the split */
552 /* Penalty if there are no non-blank lines before the split */
553 #define START_OF_FILE_PENALTY 1
553 #define START_OF_FILE_PENALTY 1
554
554
555 /* Penalty if there are no non-blank lines after the split */
555 /* Penalty if there are no non-blank lines after the split */
556 #define END_OF_FILE_PENALTY 21
556 #define END_OF_FILE_PENALTY 21
557
557
558 /* Multiplier for the number of blank lines around the split */
558 /* Multiplier for the number of blank lines around the split */
559 #define TOTAL_BLANK_WEIGHT (-30)
559 #define TOTAL_BLANK_WEIGHT (-30)
560
560
561 /* Multiplier for the number of blank lines after the split */
561 /* Multiplier for the number of blank lines after the split */
562 #define POST_BLANK_WEIGHT 6
562 #define POST_BLANK_WEIGHT 6
563
563
564 /*
564 /*
565 * Penalties applied if the line is indented more than its predecessor
565 * Penalties applied if the line is indented more than its predecessor
566 */
566 */
567 #define RELATIVE_INDENT_PENALTY (-4)
567 #define RELATIVE_INDENT_PENALTY (-4)
568 #define RELATIVE_INDENT_WITH_BLANK_PENALTY 10
568 #define RELATIVE_INDENT_WITH_BLANK_PENALTY 10
569
569
570 /*
570 /*
571 * Penalties applied if the line is indented less than both its predecessor and
571 * Penalties applied if the line is indented less than both its predecessor and
572 * its successor
572 * its successor
573 */
573 */
574 #define RELATIVE_OUTDENT_PENALTY 24
574 #define RELATIVE_OUTDENT_PENALTY 24
575 #define RELATIVE_OUTDENT_WITH_BLANK_PENALTY 17
575 #define RELATIVE_OUTDENT_WITH_BLANK_PENALTY 17
576
576
577 /*
577 /*
578 * Penalties applied if the line is indented less than its predecessor but not
578 * Penalties applied if the line is indented less than its predecessor but not
579 * less than its successor
579 * less than its successor
580 */
580 */
581 #define RELATIVE_DEDENT_PENALTY 23
581 #define RELATIVE_DEDENT_PENALTY 23
582 #define RELATIVE_DEDENT_WITH_BLANK_PENALTY 17
582 #define RELATIVE_DEDENT_WITH_BLANK_PENALTY 17
583
583
584 /*
584 /*
585 * We only consider whether the sum of the effective indents for splits are
585 * We only consider whether the sum of the effective indents for splits are
586 * less than (-1), equal to (0), or greater than (+1) each other. The resulting
586 * less than (-1), equal to (0), or greater than (+1) each other. The resulting
587 * value is multiplied by the following weight and combined with the penalty to
587 * value is multiplied by the following weight and combined with the penalty to
588 * determine the better of two scores.
588 * determine the better of two scores.
589 */
589 */
590 #define INDENT_WEIGHT 60
590 #define INDENT_WEIGHT 60
591
591
592 /*
592 /*
593 * Compute a badness score for the hypothetical split whose measurements are
593 * Compute a badness score for the hypothetical split whose measurements are
594 * stored in m. The weight factors were determined empirically using the tools and
594 * stored in m. The weight factors were determined empirically using the tools and
595 * corpus described in
595 * corpus described in
596 *
596 *
597 * https://github.com/mhagger/diff-slider-tools
597 * https://github.com/mhagger/diff-slider-tools
598 *
598 *
599 * Also see that project if you want to improve the weights based on, for example,
599 * Also see that project if you want to improve the weights based on, for example,
600 * a larger or more diverse corpus.
600 * a larger or more diverse corpus.
601 */
601 */
602 static void score_add_split(const struct split_measurement *m, struct split_score *s)
602 static void score_add_split(const struct split_measurement *m, struct split_score *s)
603 {
603 {
604 /*
604 /*
605 * A place to accumulate penalty factors (positive makes this index more
605 * A place to accumulate penalty factors (positive makes this index more
606 * favored):
606 * favored):
607 */
607 */
608 int post_blank, total_blank, indent, any_blanks;
608 int post_blank, total_blank, indent, any_blanks;
609
609
610 if (m->pre_indent == -1 && m->pre_blank == 0)
610 if (m->pre_indent == -1 && m->pre_blank == 0)
611 s->penalty += START_OF_FILE_PENALTY;
611 s->penalty += START_OF_FILE_PENALTY;
612
612
613 if (m->end_of_file)
613 if (m->end_of_file)
614 s->penalty += END_OF_FILE_PENALTY;
614 s->penalty += END_OF_FILE_PENALTY;
615
615
616 /*
616 /*
617 * Set post_blank to the number of blank lines following the split,
617 * Set post_blank to the number of blank lines following the split,
618 * including the line immediately after the split:
618 * including the line immediately after the split:
619 */
619 */
620 post_blank = (m->indent == -1) ? 1 + m->post_blank : 0;
620 post_blank = (m->indent == -1) ? 1 + m->post_blank : 0;
621 total_blank = m->pre_blank + post_blank;
621 total_blank = m->pre_blank + post_blank;
622
622
623 /* Penalties based on nearby blank lines: */
623 /* Penalties based on nearby blank lines: */
624 s->penalty += TOTAL_BLANK_WEIGHT * total_blank;
624 s->penalty += TOTAL_BLANK_WEIGHT * total_blank;
625 s->penalty += POST_BLANK_WEIGHT * post_blank;
625 s->penalty += POST_BLANK_WEIGHT * post_blank;
626
626
627 if (m->indent != -1)
627 if (m->indent != -1)
628 indent = m->indent;
628 indent = m->indent;
629 else
629 else
630 indent = m->post_indent;
630 indent = m->post_indent;
631
631
632 any_blanks = (total_blank != 0);
632 any_blanks = (total_blank != 0);
633
633
634 /* Note that the effective indent is -1 at the end of the file: */
634 /* Note that the effective indent is -1 at the end of the file: */
635 s->effective_indent += indent;
635 s->effective_indent += indent;
636
636
637 if (indent == -1) {
637 if (indent == -1) {
638 /* No additional adjustments needed. */
638 /* No additional adjustments needed. */
639 } else if (m->pre_indent == -1) {
639 } else if (m->pre_indent == -1) {
640 /* No additional adjustments needed. */
640 /* No additional adjustments needed. */
641 } else if (indent > m->pre_indent) {
641 } else if (indent > m->pre_indent) {
642 /*
642 /*
643 * The line is indented more than its predecessor.
643 * The line is indented more than its predecessor.
644 */
644 */
645 s->penalty += any_blanks ?
645 s->penalty += any_blanks ?
646 RELATIVE_INDENT_WITH_BLANK_PENALTY :
646 RELATIVE_INDENT_WITH_BLANK_PENALTY :
647 RELATIVE_INDENT_PENALTY;
647 RELATIVE_INDENT_PENALTY;
648 } else if (indent == m->pre_indent) {
648 } else if (indent == m->pre_indent) {
649 /*
649 /*
650 * The line has the same indentation level as its predecessor.
650 * The line has the same indentation level as its predecessor.
651 * No additional adjustments needed.
651 * No additional adjustments needed.
652 */
652 */
653 } else {
653 } else {
654 /*
654 /*
655 * The line is indented less than its predecessor. It could be
655 * The line is indented less than its predecessor. It could be
656 * the block terminator of the previous block, but it could
656 * the block terminator of the previous block, but it could
657 * also be the start of a new block (e.g., an "else" block, or
657 * also be the start of a new block (e.g., an "else" block, or
658 * maybe the previous block didn't have a block terminator).
658 * maybe the previous block didn't have a block terminator).
659 * Try to distinguish those cases based on what comes next:
659 * Try to distinguish those cases based on what comes next:
660 */
660 */
661 if (m->post_indent != -1 && m->post_indent > indent) {
661 if (m->post_indent != -1 && m->post_indent > indent) {
662 /*
662 /*
663 * The following line is indented more. So it is likely
663 * The following line is indented more. So it is likely
664 * that this line is the start of a block.
664 * that this line is the start of a block.
665 */
665 */
666 s->penalty += any_blanks ?
666 s->penalty += any_blanks ?
667 RELATIVE_OUTDENT_WITH_BLANK_PENALTY :
667 RELATIVE_OUTDENT_WITH_BLANK_PENALTY :
668 RELATIVE_OUTDENT_PENALTY;
668 RELATIVE_OUTDENT_PENALTY;
669 } else {
669 } else {
670 /*
670 /*
671 * That was probably the end of a block.
671 * That was probably the end of a block.
672 */
672 */
673 s->penalty += any_blanks ?
673 s->penalty += any_blanks ?
674 RELATIVE_DEDENT_WITH_BLANK_PENALTY :
674 RELATIVE_DEDENT_WITH_BLANK_PENALTY :
675 RELATIVE_DEDENT_PENALTY;
675 RELATIVE_DEDENT_PENALTY;
676 }
676 }
677 }
677 }
678 }
678 }
679
679
680 static int score_cmp(struct split_score *s1, struct split_score *s2)
680 static int score_cmp(struct split_score *s1, struct split_score *s2)
681 {
681 {
682 /* -1 if s1.effective_indent < s2->effective_indent, etc. */
682 /* -1 if s1.effective_indent < s2->effective_indent, etc. */
683 int cmp_indents = ((s1->effective_indent > s2->effective_indent) -
683 int cmp_indents = ((s1->effective_indent > s2->effective_indent) -
684 (s1->effective_indent < s2->effective_indent));
684 (s1->effective_indent < s2->effective_indent));
685
685
686 return INDENT_WEIGHT * cmp_indents + (s1->penalty - s2->penalty);
686 return INDENT_WEIGHT * cmp_indents + (s1->penalty - s2->penalty);
687 }
687 }
688
688
689 /*
689 /*
690 * Represent a group of changed lines in an xdfile_t (i.e., a contiguous group
690 * Represent a group of changed lines in an xdfile_t (i.e., a contiguous group
691 * of lines that was inserted or deleted from the corresponding version of the
691 * of lines that was inserted or deleted from the corresponding version of the
692 * file). We consider there to be such a group at the beginning of the file, at
692 * file). We consider there to be such a group at the beginning of the file, at
693 * the end of the file, and between any two unchanged lines, though most such
693 * the end of the file, and between any two unchanged lines, though most such
694 * groups will usually be empty.
694 * groups will usually be empty.
695 *
695 *
696 * If the first line in a group is equal to the line following the group, then
696 * If the first line in a group is equal to the line following the group, then
697 * the group can be slid down. Similarly, if the last line in a group is equal
697 * the group can be slid down. Similarly, if the last line in a group is equal
698 * to the line preceding the group, then the group can be slid up. See
698 * to the line preceding the group, then the group can be slid up. See
699 * group_slide_down() and group_slide_up().
699 * group_slide_down() and group_slide_up().
700 *
700 *
701 * Note that loops that are testing for changed lines in xdf->rchg do not need
701 * Note that loops that are testing for changed lines in xdf->rchg do not need
702 * index bounding since the array is prepared with a zero at position -1 and N.
702 * index bounding since the array is prepared with a zero at position -1 and N.
703 */
703 */
704 struct xdlgroup {
704 struct xdlgroup {
705 /*
705 /*
706 * The index of the first changed line in the group, or the index of
706 * The index of the first changed line in the group, or the index of
707 * the unchanged line above which the (empty) group is located.
707 * the unchanged line above which the (empty) group is located.
708 */
708 */
709 long start;
709 long start;
710
710
711 /*
711 /*
712 * The index of the first unchanged line after the group. For an empty
712 * The index of the first unchanged line after the group. For an empty
713 * group, end is equal to start.
713 * group, end is equal to start.
714 */
714 */
715 long end;
715 long end;
716 };
716 };
717
717
718 /*
718 /*
719 * Initialize g to point at the first group in xdf.
719 * Initialize g to point at the first group in xdf.
720 */
720 */
721 static void group_init(xdfile_t *xdf, struct xdlgroup *g)
721 static void group_init(xdfile_t *xdf, struct xdlgroup *g)
722 {
722 {
723 g->start = g->end = 0;
723 g->start = g->end = 0;
724 while (xdf->rchg[g->end])
724 while (xdf->rchg[g->end])
725 g->end++;
725 g->end++;
726 }
726 }
727
727
728 /*
728 /*
729 * Move g to describe the next (possibly empty) group in xdf and return 0. If g
729 * Move g to describe the next (possibly empty) group in xdf and return 0. If g
730 * is already at the end of the file, do nothing and return -1.
730 * is already at the end of the file, do nothing and return -1.
731 */
731 */
732 static inline int group_next(xdfile_t *xdf, struct xdlgroup *g)
732 static inline int group_next(xdfile_t *xdf, struct xdlgroup *g)
733 {
733 {
734 if (g->end == xdf->nrec)
734 if (g->end == xdf->nrec)
735 return -1;
735 return -1;
736
736
737 g->start = g->end + 1;
737 g->start = g->end + 1;
738 for (g->end = g->start; xdf->rchg[g->end]; g->end++)
738 for (g->end = g->start; xdf->rchg[g->end]; g->end++)
739 ;
739 ;
740
740
741 return 0;
741 return 0;
742 }
742 }
743
743
744 /*
744 /*
745 * Move g to describe the previous (possibly empty) group in xdf and return 0.
745 * Move g to describe the previous (possibly empty) group in xdf and return 0.
746 * If g is already at the beginning of the file, do nothing and return -1.
746 * If g is already at the beginning of the file, do nothing and return -1.
747 */
747 */
748 static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)
748 static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g)
749 {
749 {
750 if (g->start == 0)
750 if (g->start == 0)
751 return -1;
751 return -1;
752
752
753 g->end = g->start - 1;
753 g->end = g->start - 1;
754 for (g->start = g->end; xdf->rchg[g->start - 1]; g->start--)
754 for (g->start = g->end; xdf->rchg[g->start - 1]; g->start--)
755 ;
755 ;
756
756
757 return 0;
757 return 0;
758 }
758 }
759
759
760 /*
760 /*
761 * If g can be slid toward the end of the file, do so, and if it bumps into a
761 * If g can be slid toward the end of the file, do so, and if it bumps into a
762 * following group, expand this group to include it. Return 0 on success or -1
762 * following group, expand this group to include it. Return 0 on success or -1
763 * if g cannot be slid down.
763 * if g cannot be slid down.
764 */
764 */
765 static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags)
765 static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags)
766 {
766 {
767 if (g->end < xdf->nrec &&
767 if (g->end < xdf->nrec &&
768 recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) {
768 recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) {
769 xdf->rchg[g->start++] = 0;
769 xdf->rchg[g->start++] = 0;
770 xdf->rchg[g->end++] = 1;
770 xdf->rchg[g->end++] = 1;
771
771
772 while (xdf->rchg[g->end])
772 while (xdf->rchg[g->end])
773 g->end++;
773 g->end++;
774
774
775 return 0;
775 return 0;
776 } else {
776 } else {
777 return -1;
777 return -1;
778 }
778 }
779 }
779 }
780
780
781 /*
781 /*
782 * If g can be slid toward the beginning of the file, do so, and if it bumps
782 * If g can be slid toward the beginning of the file, do so, and if it bumps
783 * into a previous group, expand this group to include it. Return 0 on success
783 * into a previous group, expand this group to include it. Return 0 on success
784 * or -1 if g cannot be slid up.
784 * or -1 if g cannot be slid up.
785 */
785 */
786 static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g, long flags)
786 static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g, long flags)
787 {
787 {
788 if (g->start > 0 &&
788 if (g->start > 0 &&
789 recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) {
789 recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) {
790 xdf->rchg[--g->start] = 1;
790 xdf->rchg[--g->start] = 1;
791 xdf->rchg[--g->end] = 0;
791 xdf->rchg[--g->end] = 0;
792
792
793 while (xdf->rchg[g->start - 1])
793 while (xdf->rchg[g->start - 1])
794 g->start--;
794 g->start--;
795
795
796 return 0;
796 return 0;
797 } else {
797 } else {
798 return -1;
798 return -1;
799 }
799 }
800 }
800 }
801
801
802 static void xdl_bug(const char *msg)
802 static void xdl_bug(const char *msg)
803 {
803 {
804 fprintf(stderr, "BUG: %s\n", msg);
804 fprintf(stderr, "BUG: %s\n", msg);
805 exit(1);
805 exit(1);
806 }
806 }
807
807
808 /*
808 /*
809 * For indentation heuristic, skip searching for better slide position after
809 * For indentation heuristic, skip searching for better slide position after
810 * checking MAX_BORING lines without finding an improvement. This defends the
810 * checking MAX_BORING lines without finding an improvement. This defends the
811 * indentation heuristic logic against pathological cases. The value is not
811 * indentation heuristic logic against pathological cases. The value is not
812 * picked scientifically but should be good enough.
812 * picked scientifically but should be good enough.
813 */
813 */
814 #define MAX_BORING 100
814 #define MAX_BORING 100
815
815
816 /*
816 /*
817 * Move back and forward change groups for a consistent and pretty diff output.
817 * Move back and forward change groups for a consistent and pretty diff output.
818 * This also helps in finding joinable change groups and reducing the diff
818 * This also helps in finding joinable change groups and reducing the diff
819 * size.
819 * size.
820 */
820 */
821 int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
821 int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
822 struct xdlgroup g, go;
822 struct xdlgroup g, go;
823 long earliest_end, end_matching_other;
823 long earliest_end, end_matching_other;
824 long groupsize;
824 long groupsize;
825
825
826 group_init(xdf, &g);
826 group_init(xdf, &g);
827 group_init(xdfo, &go);
827 group_init(xdfo, &go);
828
828
829 while (1) {
829 while (1) {
830 /* If the group is empty in the to-be-compacted file, skip it: */
830 /* If the group is empty in the to-be-compacted file, skip it: */
831 if (g.end == g.start)
831 if (g.end == g.start)
832 goto next;
832 goto next;
833
833
834 /*
834 /*
835 * Now shift the change up and then down as far as possible in
835 * Now shift the change up and then down as far as possible in
836 * each direction. If it bumps into any other changes, merge them.
836 * each direction. If it bumps into any other changes, merge them.
837 */
837 */
838 do {
838 do {
839 groupsize = g.end - g.start;
839 groupsize = g.end - g.start;
840
840
841 /*
841 /*
842 * Keep track of the last "end" index that causes this
842 * Keep track of the last "end" index that causes this
843 * group to align with a group of changed lines in the
843 * group to align with a group of changed lines in the
844 * other file. -1 indicates that we haven't found such
844 * other file. -1 indicates that we haven't found such
845 * a match yet:
845 * a match yet:
846 */
846 */
847 end_matching_other = -1;
847 end_matching_other = -1;
848
848
849 /* Shift the group backward as much as possible: */
849 /* Shift the group backward as much as possible: */
850 while (!group_slide_up(xdf, &g, flags))
850 while (!group_slide_up(xdf, &g, flags))
851 if (group_previous(xdfo, &go))
851 if (group_previous(xdfo, &go))
852 xdl_bug("group sync broken sliding up");
852 xdl_bug("group sync broken sliding up");
853
853
854 /*
854 /*
855 * This is this highest that this group can be shifted.
855 * This is this highest that this group can be shifted.
856 * Record its end index:
856 * Record its end index:
857 */
857 */
858 earliest_end = g.end;
858 earliest_end = g.end;
859
859
860 if (go.end > go.start)
860 if (go.end > go.start)
861 end_matching_other = g.end;
861 end_matching_other = g.end;
862
862
863 /* Now shift the group forward as far as possible: */
863 /* Now shift the group forward as far as possible: */
864 while (1) {
864 while (1) {
865 if (group_slide_down(xdf, &g, flags))
865 if (group_slide_down(xdf, &g, flags))
866 break;
866 break;
867 if (group_next(xdfo, &go))
867 if (group_next(xdfo, &go))
868 xdl_bug("group sync broken sliding down");
868 xdl_bug("group sync broken sliding down");
869
869
870 if (go.end > go.start)
870 if (go.end > go.start)
871 end_matching_other = g.end;
871 end_matching_other = g.end;
872 }
872 }
873 } while (groupsize != g.end - g.start);
873 } while (groupsize != g.end - g.start);
874
874
875 /*
875 /*
876 * If the group can be shifted, then we can possibly use this
876 * If the group can be shifted, then we can possibly use this
877 * freedom to produce a more intuitive diff.
877 * freedom to produce a more intuitive diff.
878 *
878 *
879 * The group is currently shifted as far down as possible, so the
879 * The group is currently shifted as far down as possible, so the
880 * heuristics below only have to handle upwards shifts.
880 * heuristics below only have to handle upwards shifts.
881 */
881 */
882
882
883 if (g.end == earliest_end) {
883 if (g.end == earliest_end) {
884 /* no shifting was possible */
884 /* no shifting was possible */
885 } else if (end_matching_other != -1) {
885 } else if (end_matching_other != -1) {
886 /*
886 /*
887 * Move the possibly merged group of changes back to line
887 * Move the possibly merged group of changes back to line
888 * up with the last group of changes from the other file
888 * up with the last group of changes from the other file
889 * that it can align with.
889 * that it can align with.
890 */
890 */
891 while (go.end == go.start) {
891 while (go.end == go.start) {
892 if (group_slide_up(xdf, &g, flags))
892 if (group_slide_up(xdf, &g, flags))
893 xdl_bug("match disappeared");
893 xdl_bug("match disappeared");
894 if (group_previous(xdfo, &go))
894 if (group_previous(xdfo, &go))
895 xdl_bug("group sync broken sliding to match");
895 xdl_bug("group sync broken sliding to match");
896 }
896 }
897 } else if (flags & XDF_INDENT_HEURISTIC) {
897 } else if (flags & XDF_INDENT_HEURISTIC) {
898 /*
898 /*
899 * Indent heuristic: a group of pure add/delete lines
899 * Indent heuristic: a group of pure add/delete lines
900 * implies two splits, one between the end of the "before"
900 * implies two splits, one between the end of the "before"
901 * context and the start of the group, and another between
901 * context and the start of the group, and another between
902 * the end of the group and the beginning of the "after"
902 * the end of the group and the beginning of the "after"
903 * context. Some splits are aesthetically better and some
903 * context. Some splits are aesthetically better and some
904 * are worse. We compute a badness "score" for each split,
904 * are worse. We compute a badness "score" for each split,
905 * and add the scores for the two splits to define a
905 * and add the scores for the two splits to define a
906 * "score" for each position that the group can be shifted
906 * "score" for each position that the group can be shifted
907 * to. Then we pick the shift with the lowest score.
907 * to. Then we pick the shift with the lowest score.
908 */
908 */
909 long shift, best_shift = -1;
909 long shift, best_shift = -1;
910 struct split_score best_score;
910 struct split_score best_score;
911
911
912 /*
912 /*
913 * This is O(N * MAX_BLANKS) (N = shift-able lines).
913 * This is O(N * MAX_BLANKS) (N = shift-able lines).
914 * Even with MAX_BLANKS bounded to a small value, a
914 * Even with MAX_BLANKS bounded to a small value, a
915 * large N could still make this loop take several
915 * large N could still make this loop take several
916 * times longer than the main diff algorithm. The
916 * times longer than the main diff algorithm. The
917 * "boring" value is to help cut down N to something
917 * "boring" value is to help cut down N to something
918 * like (MAX_BORING + groupsize).
918 * like (MAX_BORING + groupsize).
919 *
919 *
920 * Scan from bottom to top. So we can exit the loop
920 * Scan from bottom to top. So we can exit the loop
921 * without compromising the assumption "for a same best
921 * without compromising the assumption "for a same best
922 * score, pick the bottommost shift".
922 * score, pick the bottommost shift".
923 */
923 */
924 int boring = 0;
924 int boring = 0;
925 for (shift = g.end; shift >= earliest_end; shift--) {
925 for (shift = g.end; shift >= earliest_end; shift--) {
926 struct split_measurement m;
926 struct split_measurement m;
927 struct split_score score = {0, 0};
927 struct split_score score = {0, 0};
928 int cmp;
928 int cmp;
929
929
930 measure_split(xdf, shift, &m);
930 measure_split(xdf, shift, &m);
931 score_add_split(&m, &score);
931 score_add_split(&m, &score);
932 measure_split(xdf, shift - groupsize, &m);
932 measure_split(xdf, shift - groupsize, &m);
933 score_add_split(&m, &score);
933 score_add_split(&m, &score);
934
934
935 if (best_shift == -1) {
935 if (best_shift == -1) {
936 cmp = -1;
936 cmp = -1;
937 } else {
937 } else {
938 cmp = score_cmp(&score, &best_score);
938 cmp = score_cmp(&score, &best_score);
939 }
939 }
940 if (cmp < 0) {
940 if (cmp < 0) {
941 boring = 0;
941 boring = 0;
942 best_score.effective_indent = score.effective_indent;
942 best_score.effective_indent = score.effective_indent;
943 best_score.penalty = score.penalty;
943 best_score.penalty = score.penalty;
944 best_shift = shift;
944 best_shift = shift;
945 } else {
945 } else {
946 boring += 1;
946 boring += 1;
947 if (boring >= MAX_BORING)
947 if (boring >= MAX_BORING)
948 break;
948 break;
949 }
949 }
950 }
950 }
951
951
952 while (g.end > best_shift) {
952 while (g.end > best_shift) {
953 if (group_slide_up(xdf, &g, flags))
953 if (group_slide_up(xdf, &g, flags))
954 xdl_bug("best shift unreached");
954 xdl_bug("best shift unreached");
955 if (group_previous(xdfo, &go))
955 if (group_previous(xdfo, &go))
956 xdl_bug("group sync broken sliding to blank line");
956 xdl_bug("group sync broken sliding to blank line");
957 }
957 }
958 }
958 }
959
959
960 next:
960 next:
961 /* Move past the just-processed group: */
961 /* Move past the just-processed group: */
962 if (group_next(xdf, &g))
962 if (group_next(xdf, &g))
963 break;
963 break;
964 if (group_next(xdfo, &go))
964 if (group_next(xdfo, &go))
965 xdl_bug("group sync broken moving to next group");
965 xdl_bug("group sync broken moving to next group");
966 }
966 }
967
967
968 if (!group_next(xdfo, &go))
968 if (!group_next(xdfo, &go))
969 xdl_bug("group sync broken at end of file");
969 xdl_bug("group sync broken at end of file");
970
970
971 return 0;
971 return 0;
972 }
972 }
973
973
974
974
975 int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
975 int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
976 xdchange_t *cscr = NULL, *xch;
976 xdchange_t *cscr = NULL, *xch;
977 char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;
977 char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;
978 long i1, i2, l1, l2;
978 long i1, i2, l1, l2;
979
979
980 /*
980 /*
981 * Trivial. Collects "groups" of changes and creates an edit script.
981 * Trivial. Collects "groups" of changes and creates an edit script.
982 */
982 */
983 for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
983 for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
984 if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
984 if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
985 for (l1 = i1; rchg1[i1 - 1]; i1--);
985 for (l1 = i1; rchg1[i1 - 1]; i1--);
986 for (l2 = i2; rchg2[i2 - 1]; i2--);
986 for (l2 = i2; rchg2[i2 - 1]; i2--);
987
987
988 if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
988 if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
989 xdl_free_script(cscr);
989 xdl_free_script(cscr);
990 return -1;
990 return -1;
991 }
991 }
992 cscr = xch;
992 cscr = xch;
993 }
993 }
994
994
995 *xscr = cscr;
995 *xscr = cscr;
996
996
997 return 0;
997 return 0;
998 }
998 }
999
999
1000
1000
1001 void xdl_free_script(xdchange_t *xscr) {
1001 void xdl_free_script(xdchange_t *xscr) {
1002 xdchange_t *xch;
1002 xdchange_t *xch;
1003
1003
1004 while ((xch = xscr) != NULL) {
1004 while ((xch = xscr) != NULL) {
1005 xscr = xscr->next;
1005 xscr = xscr->next;
1006 xdl_free(xch);
1006 xdl_free(xch);
1007 }
1007 }
1008 }
1008 }
1009
1009
1010 static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
1010 static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
1011 xdemitconf_t const *xecfg)
1011 xdemitconf_t const *xecfg)
1012 {
1012 {
1013 xdchange_t *xch, *xche;
1013 xdchange_t *xch, *xche;
1014 if ((xecfg->flags & XDL_EMIT_BDIFFHUNK) != 0) {
1014 if ((xecfg->flags & XDL_EMIT_BDIFFHUNK) != 0) {
1015 long i1 = 0, i2 = 0, n1 = xe->xdf1.nrec, n2 = xe->xdf2.nrec;
1015 long i1 = 0, i2 = 0, n1 = xe->xdf1.nrec, n2 = xe->xdf2.nrec;
1016 for (xch = xscr; xch; xch = xche->next) {
1016 for (xch = xscr; xch; xch = xche->next) {
1017 xche = xdl_get_hunk(&xch, xecfg);
1017 xche = xdl_get_hunk(&xch, xecfg);
1018 if (!xch)
1018 if (!xch)
1019 break;
1019 break;
1020 if (xch->i1 > i1 || xch->i2 > i2) {
1020 if (xch->i1 > i1 || xch->i2 > i2) {
1021 if (xecfg->hunk_func(i1, xch->i1, i2, xch->i2, ecb->priv) < 0)
1021 if (xecfg->hunk_func(i1, xch->i1, i2, xch->i2, ecb->priv) < 0)
1022 return -1;
1022 return -1;
1023 }
1023 }
1024 i1 = xche->i1 + xche->chg1;
1024 i1 = xche->i1 + xche->chg1;
1025 i2 = xche->i2 + xche->chg2;
1025 i2 = xche->i2 + xche->chg2;
1026 }
1026 }
1027 if (xecfg->hunk_func(i1, n1, i2, n2, ecb->priv) < 0)
1027 if (xecfg->hunk_func(i1, n1, i2, n2, ecb->priv) < 0)
1028 return -1;
1028 return -1;
1029 } else {
1029 } else {
1030 for (xch = xscr; xch; xch = xche->next) {
1030 for (xch = xscr; xch; xch = xche->next) {
1031 xche = xdl_get_hunk(&xch, xecfg);
1031 xche = xdl_get_hunk(&xch, xecfg);
1032 if (!xch)
1032 if (!xch)
1033 break;
1033 break;
1034 if (xecfg->hunk_func(
1034 if (xecfg->hunk_func(
1035 xch->i1, xche->i1 + xche->chg1 - xch->i1,
1035 xch->i1, xche->i1 + xche->chg1 - xch->i1,
1036 xch->i2, xche->i2 + xche->chg2 - xch->i2,
1036 xch->i2, xche->i2 + xche->chg2 - xch->i2,
1037 ecb->priv) < 0)
1037 ecb->priv) < 0)
1038 return -1;
1038 return -1;
1039 }
1039 }
1040 }
1040 }
1041 return 0;
1041 return 0;
1042 }
1042 }
1043
1043
1044 static void xdl_mark_ignorable(xdchange_t *xscr, xdfenv_t *xe, long flags)
1045 {
1046 xdchange_t *xch;
1047
1048 for (xch = xscr; xch; xch = xch->next) {
1049 int ignore = 1;
1050 xrecord_t **rec;
1051 long i;
1052
1053 rec = &xe->xdf1.recs[xch->i1];
1054 for (i = 0; i < xch->chg1 && ignore; i++)
1055 ignore = xdl_blankline(rec[i]->ptr, rec[i]->size, flags);
1056
1057 rec = &xe->xdf2.recs[xch->i2];
1058 for (i = 0; i < xch->chg2 && ignore; i++)
1059 ignore = xdl_blankline(rec[i]->ptr, rec[i]->size, flags);
1060
1061 xch->ignore = ignore;
1062 }
1063 }
1064
1065 int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
1044 int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
1066 xdemitconf_t const *xecfg, xdemitcb_t *ecb) {
1045 xdemitconf_t const *xecfg, xdemitcb_t *ecb) {
1067 xdchange_t *xscr;
1046 xdchange_t *xscr;
1068 xdfenv_t xe;
1047 xdfenv_t xe;
1069 emit_func_t ef = xecfg->hunk_func ? xdl_call_hunk_func : xdl_emit_diff;
1048 emit_func_t ef = xecfg->hunk_func ? xdl_call_hunk_func : xdl_emit_diff;
1070
1049
1071 if (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) {
1050 if (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) {
1072
1051
1073 return -1;
1052 return -1;
1074 }
1053 }
1075 if (xdl_change_compact(&xe.xdf1, &xe.xdf2, xpp->flags) < 0 ||
1054 if (xdl_change_compact(&xe.xdf1, &xe.xdf2, xpp->flags) < 0 ||
1076 xdl_change_compact(&xe.xdf2, &xe.xdf1, xpp->flags) < 0 ||
1055 xdl_change_compact(&xe.xdf2, &xe.xdf1, xpp->flags) < 0 ||
1077 xdl_build_script(&xe, &xscr) < 0) {
1056 xdl_build_script(&xe, &xscr) < 0) {
1078
1057
1079 xdl_free_env(&xe);
1058 xdl_free_env(&xe);
1080 return -1;
1059 return -1;
1081 }
1060 }
1082
1061
1083 if (xpp->flags & XDF_IGNORE_BLANK_LINES)
1084 xdl_mark_ignorable(xscr, &xe, xpp->flags);
1085 if (ef(&xe, xscr, ecb, xecfg) < 0) {
1062 if (ef(&xe, xscr, ecb, xecfg) < 0) {
1086 xdl_free_script(xscr);
1063 xdl_free_script(xscr);
1087 xdl_free_env(&xe);
1064 xdl_free_env(&xe);
1088 return -1;
1065 return -1;
1089 }
1066 }
1090 xdl_free_script(xscr);
1067 xdl_free_script(xscr);
1091 xdl_free_env(&xe);
1068 xdl_free_env(&xe);
1092
1069
1093 return 0;
1070 return 0;
1094 }
1071 }
@@ -1,425 +1,274
1 /*
1 /*
2 * LibXDiff by Davide Libenzi ( File Differential Library )
2 * LibXDiff by Davide Libenzi ( File Differential Library )
3 * Copyright (C) 2003 Davide Libenzi
3 * Copyright (C) 2003 Davide Libenzi
4 *
4 *
5 * This library is free software; you can redistribute it and/or
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
8 * version 2.1 of the License, or (at your option) any later version.
9 *
9 *
10 * This library is distributed in the hope that it will be useful,
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
13 * Lesser General Public License for more details.
14 *
14 *
15 * You should have received a copy of the GNU Lesser General Public
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, see
16 * License along with this library; if not, see
17 * <http://www.gnu.org/licenses/>.
17 * <http://www.gnu.org/licenses/>.
18 *
18 *
19 * Davide Libenzi <davidel@xmailserver.org>
19 * Davide Libenzi <davidel@xmailserver.org>
20 *
20 *
21 */
21 */
22
22
23 #include <limits.h>
23 #include <limits.h>
24 #include <assert.h>
24 #include <assert.h>
25 #include "xinclude.h"
25 #include "xinclude.h"
26
26
27
27
28
28
29
29
30 long xdl_bogosqrt(long n) {
30 long xdl_bogosqrt(long n) {
31 long i;
31 long i;
32
32
33 /*
33 /*
34 * Classical integer square root approximation using shifts.
34 * Classical integer square root approximation using shifts.
35 */
35 */
36 for (i = 1; n > 0; n >>= 2)
36 for (i = 1; n > 0; n >>= 2)
37 i <<= 1;
37 i <<= 1;
38
38
39 return i;
39 return i;
40 }
40 }
41
41
42
42
43 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
43 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
44 xdemitcb_t *ecb) {
44 xdemitcb_t *ecb) {
45 int i = 2;
45 int i = 2;
46 mmbuffer_t mb[3];
46 mmbuffer_t mb[3];
47
47
48 mb[0].ptr = (char *) pre;
48 mb[0].ptr = (char *) pre;
49 mb[0].size = psize;
49 mb[0].size = psize;
50 mb[1].ptr = (char *) rec;
50 mb[1].ptr = (char *) rec;
51 mb[1].size = size;
51 mb[1].size = size;
52 if (size > 0 && rec[size - 1] != '\n') {
52 if (size > 0 && rec[size - 1] != '\n') {
53 mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
53 mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
54 mb[2].size = strlen(mb[2].ptr);
54 mb[2].size = strlen(mb[2].ptr);
55 i++;
55 i++;
56 }
56 }
57 if (ecb->outf(ecb->priv, mb, i) < 0) {
57 if (ecb->outf(ecb->priv, mb, i) < 0) {
58
58
59 return -1;
59 return -1;
60 }
60 }
61
61
62 return 0;
62 return 0;
63 }
63 }
64
64
65 void *xdl_mmfile_first(mmfile_t *mmf, long *size)
65 void *xdl_mmfile_first(mmfile_t *mmf, long *size)
66 {
66 {
67 *size = mmf->size;
67 *size = mmf->size;
68 return mmf->ptr;
68 return mmf->ptr;
69 }
69 }
70
70
71
71
72 long xdl_mmfile_size(mmfile_t *mmf)
72 long xdl_mmfile_size(mmfile_t *mmf)
73 {
73 {
74 return mmf->size;
74 return mmf->size;
75 }
75 }
76
76
77
77
78 int xdl_cha_init(chastore_t *cha, long isize, long icount) {
78 int xdl_cha_init(chastore_t *cha, long isize, long icount) {
79
79
80 cha->head = cha->tail = NULL;
80 cha->head = cha->tail = NULL;
81 cha->isize = isize;
81 cha->isize = isize;
82 cha->nsize = icount * isize;
82 cha->nsize = icount * isize;
83 cha->ancur = cha->sncur = NULL;
83 cha->ancur = cha->sncur = NULL;
84 cha->scurr = 0;
84 cha->scurr = 0;
85
85
86 return 0;
86 return 0;
87 }
87 }
88
88
89
89
90 void xdl_cha_free(chastore_t *cha) {
90 void xdl_cha_free(chastore_t *cha) {
91 chanode_t *cur, *tmp;
91 chanode_t *cur, *tmp;
92
92
93 for (cur = cha->head; (tmp = cur) != NULL;) {
93 for (cur = cha->head; (tmp = cur) != NULL;) {
94 cur = cur->next;
94 cur = cur->next;
95 xdl_free(tmp);
95 xdl_free(tmp);
96 }
96 }
97 }
97 }
98
98
99
99
100 void *xdl_cha_alloc(chastore_t *cha) {
100 void *xdl_cha_alloc(chastore_t *cha) {
101 chanode_t *ancur;
101 chanode_t *ancur;
102 void *data;
102 void *data;
103
103
104 if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
104 if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
105 if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
105 if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
106
106
107 return NULL;
107 return NULL;
108 }
108 }
109 ancur->icurr = 0;
109 ancur->icurr = 0;
110 ancur->next = NULL;
110 ancur->next = NULL;
111 if (cha->tail)
111 if (cha->tail)
112 cha->tail->next = ancur;
112 cha->tail->next = ancur;
113 if (!cha->head)
113 if (!cha->head)
114 cha->head = ancur;
114 cha->head = ancur;
115 cha->tail = ancur;
115 cha->tail = ancur;
116 cha->ancur = ancur;
116 cha->ancur = ancur;
117 }
117 }
118
118
119 data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
119 data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
120 ancur->icurr += cha->isize;
120 ancur->icurr += cha->isize;
121
121
122 return data;
122 return data;
123 }
123 }
124
124
125 long xdl_guess_lines(mmfile_t *mf, long sample) {
125 long xdl_guess_lines(mmfile_t *mf, long sample) {
126 long nl = 0, size, tsize = 0;
126 long nl = 0, size, tsize = 0;
127 char const *data, *cur, *top;
127 char const *data, *cur, *top;
128
128
129 if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
129 if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
130 for (top = data + size; nl < sample && cur < top; ) {
130 for (top = data + size; nl < sample && cur < top; ) {
131 nl++;
131 nl++;
132 if (!(cur = memchr(cur, '\n', top - cur)))
132 if (!(cur = memchr(cur, '\n', top - cur)))
133 cur = top;
133 cur = top;
134 else
134 else
135 cur++;
135 cur++;
136 }
136 }
137 tsize += (long) (cur - data);
137 tsize += (long) (cur - data);
138 }
138 }
139
139
140 if (nl && tsize)
140 if (nl && tsize)
141 nl = xdl_mmfile_size(mf) / (tsize / nl);
141 nl = xdl_mmfile_size(mf) / (tsize / nl);
142
142
143 return nl + 1;
143 return nl + 1;
144 }
144 }
145
145
146 int xdl_blankline(const char *line, long size, long flags)
147 {
148 long i;
149
150 if (!(flags & XDF_WHITESPACE_FLAGS))
151 return (size <= 1);
152
153 for (i = 0; i < size && XDL_ISSPACE(line[i]); i++)
154 ;
155
156 return (i == size);
157 }
158
159 /*
160 * Have we eaten everything on the line, except for an optional
161 * CR at the very end?
162 */
163 static int ends_with_optional_cr(const char *l, long s, long i)
164 {
165 int complete = s && l[s-1] == '\n';
166
167 if (complete)
168 s--;
169 if (s == i)
170 return 1;
171 /* do not ignore CR at the end of an incomplete line */
172 if (complete && s == i + 1 && l[i] == '\r')
173 return 1;
174 return 0;
175 }
176
177 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
146 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
178 {
147 {
179 int i1, i2;
180
181 if (s1 == s2 && !memcmp(l1, l2, s1))
148 if (s1 == s2 && !memcmp(l1, l2, s1))
182 return 1;
149 return 1;
183 if (!(flags & XDF_WHITESPACE_FLAGS))
150 return 0;
184 return 0;
185
186 i1 = 0;
187 i2 = 0;
188
189 /*
190 * -w matches everything that matches with -b, and -b in turn
191 * matches everything that matches with --ignore-space-at-eol,
192 * which in turn matches everything that matches with --ignore-cr-at-eol.
193 *
194 * Each flavor of ignoring needs different logic to skip whitespaces
195 * while we have both sides to compare.
196 */
197 if (flags & XDF_IGNORE_WHITESPACE) {
198 goto skip_ws;
199 while (i1 < s1 && i2 < s2) {
200 if (l1[i1++] != l2[i2++])
201 return 0;
202 skip_ws:
203 while (i1 < s1 && XDL_ISSPACE(l1[i1]))
204 i1++;
205 while (i2 < s2 && XDL_ISSPACE(l2[i2]))
206 i2++;
207 }
208 } else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
209 while (i1 < s1 && i2 < s2) {
210 if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) {
211 /* Skip matching spaces and try again */
212 while (i1 < s1 && XDL_ISSPACE(l1[i1]))
213 i1++;
214 while (i2 < s2 && XDL_ISSPACE(l2[i2]))
215 i2++;
216 continue;
217 }
218 if (l1[i1++] != l2[i2++])
219 return 0;
220 }
221 } else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) {
222 while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) {
223 i1++;
224 i2++;
225 }
226 } else if (flags & XDF_IGNORE_CR_AT_EOL) {
227 /* Find the first difference and see how the line ends */
228 while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) {
229 i1++;
230 i2++;
231 }
232 return (ends_with_optional_cr(l1, s1, i1) &&
233 ends_with_optional_cr(l2, s2, i2));
234 }
235
236 /*
237 * After running out of one side, the remaining side must have
238 * nothing but whitespace for the lines to match. Note that
239 * ignore-whitespace-at-eol case may break out of the loop
240 * while there still are characters remaining on both lines.
241 */
242 if (i1 < s1) {
243 while (i1 < s1 && XDL_ISSPACE(l1[i1]))
244 i1++;
245 if (s1 != i1)
246 return 0;
247 }
248 if (i2 < s2) {
249 while (i2 < s2 && XDL_ISSPACE(l2[i2]))
250 i2++;
251 return (s2 == i2);
252 }
253 return 1;
254 }
255
256 static unsigned long xdl_hash_record_with_whitespace(char const **data,
257 char const *top, long flags) {
258 unsigned long ha = 5381;
259 char const *ptr = *data;
260 int cr_at_eol_only = (flags & XDF_WHITESPACE_FLAGS) == XDF_IGNORE_CR_AT_EOL;
261
262 for (; ptr < top && *ptr != '\n'; ptr++) {
263 if (cr_at_eol_only) {
264 /* do not ignore CR at the end of an incomplete line */
265 if (*ptr == '\r' &&
266 (ptr + 1 < top && ptr[1] == '\n'))
267 continue;
268 }
269 else if (XDL_ISSPACE(*ptr)) {
270 const char *ptr2 = ptr;
271 int at_eol;
272 while (ptr + 1 < top && XDL_ISSPACE(ptr[1])
273 && ptr[1] != '\n')
274 ptr++;
275 at_eol = (top <= ptr + 1 || ptr[1] == '\n');
276 if (flags & XDF_IGNORE_WHITESPACE)
277 ; /* already handled */
278 else if (flags & XDF_IGNORE_WHITESPACE_CHANGE
279 && !at_eol) {
280 ha += (ha << 5);
281 ha ^= (unsigned long) ' ';
282 }
283 else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL
284 && !at_eol) {
285 while (ptr2 != ptr + 1) {
286 ha += (ha << 5);
287 ha ^= (unsigned long) *ptr2;
288 ptr2++;
289 }
290 }
291 continue;
292 }
293 ha += (ha << 5);
294 ha ^= (unsigned long) *ptr;
295 }
296 *data = ptr < top ? ptr + 1: ptr;
297
298 return ha;
299 }
151 }
300
152
301 unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
153 unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
302 unsigned long ha = 5381;
154 unsigned long ha = 5381;
303 char const *ptr = *data;
155 char const *ptr = *data;
304
156
305 if (flags & XDF_WHITESPACE_FLAGS)
306 return xdl_hash_record_with_whitespace(data, top, flags);
307
308 for (; ptr < top && *ptr != '\n'; ptr++) {
157 for (; ptr < top && *ptr != '\n'; ptr++) {
309 ha += (ha << 5);
158 ha += (ha << 5);
310 ha ^= (unsigned long) *ptr;
159 ha ^= (unsigned long) *ptr;
311 }
160 }
312 *data = ptr < top ? ptr + 1: ptr;
161 *data = ptr < top ? ptr + 1: ptr;
313
162
314 return ha;
163 return ha;
315 }
164 }
316
165
317 unsigned int xdl_hashbits(unsigned int size) {
166 unsigned int xdl_hashbits(unsigned int size) {
318 unsigned int val = 1, bits = 0;
167 unsigned int val = 1, bits = 0;
319
168
320 for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
169 for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
321 return bits ? bits: 1;
170 return bits ? bits: 1;
322 }
171 }
323
172
324
173
325 int xdl_num_out(char *out, long val) {
174 int xdl_num_out(char *out, long val) {
326 char *ptr, *str = out;
175 char *ptr, *str = out;
327 char buf[32];
176 char buf[32];
328
177
329 ptr = buf + sizeof(buf) - 1;
178 ptr = buf + sizeof(buf) - 1;
330 *ptr = '\0';
179 *ptr = '\0';
331 if (val < 0) {
180 if (val < 0) {
332 *--ptr = '-';
181 *--ptr = '-';
333 val = -val;
182 val = -val;
334 }
183 }
335 for (; val && ptr > buf; val /= 10)
184 for (; val && ptr > buf; val /= 10)
336 *--ptr = "0123456789"[val % 10];
185 *--ptr = "0123456789"[val % 10];
337 if (*ptr)
186 if (*ptr)
338 for (; *ptr; ptr++, str++)
187 for (; *ptr; ptr++, str++)
339 *str = *ptr;
188 *str = *ptr;
340 else
189 else
341 *str++ = '0';
190 *str++ = '0';
342 *str = '\0';
191 *str = '\0';
343
192
344 return str - out;
193 return str - out;
345 }
194 }
346
195
347 int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
196 int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
348 const char *func, long funclen, xdemitcb_t *ecb) {
197 const char *func, long funclen, xdemitcb_t *ecb) {
349 int nb = 0;
198 int nb = 0;
350 mmbuffer_t mb;
199 mmbuffer_t mb;
351 char buf[128];
200 char buf[128];
352
201
353 memcpy(buf, "@@ -", 4);
202 memcpy(buf, "@@ -", 4);
354 nb += 4;
203 nb += 4;
355
204
356 nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);
205 nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);
357
206
358 if (c1 != 1) {
207 if (c1 != 1) {
359 memcpy(buf + nb, ",", 1);
208 memcpy(buf + nb, ",", 1);
360 nb += 1;
209 nb += 1;
361
210
362 nb += xdl_num_out(buf + nb, c1);
211 nb += xdl_num_out(buf + nb, c1);
363 }
212 }
364
213
365 memcpy(buf + nb, " +", 2);
214 memcpy(buf + nb, " +", 2);
366 nb += 2;
215 nb += 2;
367
216
368 nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);
217 nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);
369
218
370 if (c2 != 1) {
219 if (c2 != 1) {
371 memcpy(buf + nb, ",", 1);
220 memcpy(buf + nb, ",", 1);
372 nb += 1;
221 nb += 1;
373
222
374 nb += xdl_num_out(buf + nb, c2);
223 nb += xdl_num_out(buf + nb, c2);
375 }
224 }
376
225
377 memcpy(buf + nb, " @@", 3);
226 memcpy(buf + nb, " @@", 3);
378 nb += 3;
227 nb += 3;
379 if (func && funclen) {
228 if (func && funclen) {
380 buf[nb++] = ' ';
229 buf[nb++] = ' ';
381 if (funclen > sizeof(buf) - nb - 1)
230 if (funclen > sizeof(buf) - nb - 1)
382 funclen = sizeof(buf) - nb - 1;
231 funclen = sizeof(buf) - nb - 1;
383 memcpy(buf + nb, func, funclen);
232 memcpy(buf + nb, func, funclen);
384 nb += funclen;
233 nb += funclen;
385 }
234 }
386 buf[nb++] = '\n';
235 buf[nb++] = '\n';
387
236
388 mb.ptr = buf;
237 mb.ptr = buf;
389 mb.size = nb;
238 mb.size = nb;
390 if (ecb->outf(ecb->priv, &mb, 1) < 0)
239 if (ecb->outf(ecb->priv, &mb, 1) < 0)
391 return -1;
240 return -1;
392
241
393 return 0;
242 return 0;
394 }
243 }
395
244
396 int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
245 int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
397 int line1, int count1, int line2, int count2)
246 int line1, int count1, int line2, int count2)
398 {
247 {
399 /*
248 /*
400 * This probably does not work outside Git, since
249 * This probably does not work outside Git, since
401 * we have a very simple mmfile structure.
250 * we have a very simple mmfile structure.
402 *
251 *
403 * Note: ideally, we would reuse the prepared environment, but
252 * Note: ideally, we would reuse the prepared environment, but
404 * the libxdiff interface does not (yet) allow for diffing only
253 * the libxdiff interface does not (yet) allow for diffing only
405 * ranges of lines instead of the whole files.
254 * ranges of lines instead of the whole files.
406 */
255 */
407 mmfile_t subfile1, subfile2;
256 mmfile_t subfile1, subfile2;
408 xdfenv_t env;
257 xdfenv_t env;
409
258
410 subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr;
259 subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr;
411 subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr +
260 subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr +
412 diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;
261 diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;
413 subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr;
262 subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr;
414 subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr +
263 subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr +
415 diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;
264 diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;
416 if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0)
265 if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0)
417 return -1;
266 return -1;
418
267
419 memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);
268 memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);
420 memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);
269 memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);
421
270
422 xdl_free_env(&env);
271 xdl_free_env(&env);
423
272
424 return 0;
273 return 0;
425 }
274 }
@@ -1,47 +1,46
1 /*
1 /*
2 * LibXDiff by Davide Libenzi ( File Differential Library )
2 * LibXDiff by Davide Libenzi ( File Differential Library )
3 * Copyright (C) 2003 Davide Libenzi
3 * Copyright (C) 2003 Davide Libenzi
4 *
4 *
5 * This library is free software; you can redistribute it and/or
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
8 * version 2.1 of the License, or (at your option) any later version.
9 *
9 *
10 * This library is distributed in the hope that it will be useful,
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
13 * Lesser General Public License for more details.
14 *
14 *
15 * You should have received a copy of the GNU Lesser General Public
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, see
16 * License along with this library; if not, see
17 * <http://www.gnu.org/licenses/>.
17 * <http://www.gnu.org/licenses/>.
18 *
18 *
19 * Davide Libenzi <davidel@xmailserver.org>
19 * Davide Libenzi <davidel@xmailserver.org>
20 *
20 *
21 */
21 */
22
22
23 #if !defined(XUTILS_H)
23 #if !defined(XUTILS_H)
24 #define XUTILS_H
24 #define XUTILS_H
25
25
26
26
27
27
28 long xdl_bogosqrt(long n);
28 long xdl_bogosqrt(long n);
29 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
29 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
30 xdemitcb_t *ecb);
30 xdemitcb_t *ecb);
31 int xdl_cha_init(chastore_t *cha, long isize, long icount);
31 int xdl_cha_init(chastore_t *cha, long isize, long icount);
32 void xdl_cha_free(chastore_t *cha);
32 void xdl_cha_free(chastore_t *cha);
33 void *xdl_cha_alloc(chastore_t *cha);
33 void *xdl_cha_alloc(chastore_t *cha);
34 long xdl_guess_lines(mmfile_t *mf, long sample);
34 long xdl_guess_lines(mmfile_t *mf, long sample);
35 int xdl_blankline(const char *line, long size, long flags);
36 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);
35 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);
37 unsigned long xdl_hash_record(char const **data, char const *top, long flags);
36 unsigned long xdl_hash_record(char const **data, char const *top, long flags);
38 unsigned int xdl_hashbits(unsigned int size);
37 unsigned int xdl_hashbits(unsigned int size);
39 int xdl_num_out(char *out, long val);
38 int xdl_num_out(char *out, long val);
40 int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
39 int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
41 const char *func, long funclen, xdemitcb_t *ecb);
40 const char *func, long funclen, xdemitcb_t *ecb);
42 int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
41 int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
43 int line1, int count1, int line2, int count2);
42 int line1, int count1, int line2, int count2);
44
43
45
44
46
45
47 #endif /* #if !defined(XUTILS_H) */
46 #endif /* #if !defined(XUTILS_H) */
General Comments 0
You need to be logged in to leave comments. Login now