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