##// END OF EJS Templates
upstream » mercurial-mirror
RSS

Clone from https://www.mercurial-scm.org/repo/hg-all

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