]>
Commit | Line | Data |
---|---|---|
92b7de93 JS |
1 | /* |
2 | * LibXDiff by Davide Libenzi ( File Differential Library ) | |
044fb190 | 3 | * Copyright (C) 2003-2016 Davide Libenzi, Johannes E. Schindelin |
92b7de93 JS |
4 | * |
5 | * This library is free software; you can redistribute it and/or | |
6 | * modify it under the terms of the GNU Lesser General Public | |
7 | * License as published by the Free Software Foundation; either | |
8 | * version 2.1 of the License, or (at your option) any later version. | |
9 | * | |
10 | * This library is distributed in the hope that it will be useful, | |
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | * Lesser General Public License for more details. | |
14 | * | |
15 | * You should have received a copy of the GNU Lesser General Public | |
48425792 TZ |
16 | * License along with this library; if not, see |
17 | * <http://www.gnu.org/licenses/>. | |
92b7de93 JS |
18 | * |
19 | * Davide Libenzi <davidel@xmailserver.org> | |
20 | * | |
21 | */ | |
22 | #include "xinclude.h" | |
92b7de93 JS |
23 | |
24 | /* | |
25 | * The basic idea of patience diff is to find lines that are unique in | |
26 | * both files. These are intuitively the ones that we want to see as | |
27 | * common lines. | |
28 | * | |
29 | * The maximal ordered sequence of such line pairs (where ordered means | |
30 | * that the order in the sequence agrees with the order of the lines in | |
31 | * both files) naturally defines an initial set of common lines. | |
32 | * | |
33 | * Now, the algorithm tries to extend the set of common lines by growing | |
34 | * the line ranges where the files have identical lines. | |
35 | * | |
36 | * Between those common lines, the patience diff algorithm is applied | |
37 | * recursively, until no unique line pairs can be found; these line ranges | |
38 | * are handled by the well-known Myers algorithm. | |
39 | */ | |
40 | ||
41 | #define NON_UNIQUE ULONG_MAX | |
42 | ||
43 | /* | |
44 | * This is a hash mapping from line hash to line numbers in the first and | |
45 | * second file. | |
46 | */ | |
47 | struct hashmap { | |
48 | int nr, alloc; | |
49 | struct entry { | |
50 | unsigned long hash; | |
51 | /* | |
52 | * 0 = unused entry, 1 = first line, 2 = second, etc. | |
53 | * line2 is NON_UNIQUE if the line is not unique | |
54 | * in either the first or the second file. | |
55 | */ | |
56 | unsigned long line1, line2; | |
57 | /* | |
58 | * "next" & "previous" are used for the longest common | |
59 | * sequence; | |
60 | * initially, "next" reflects only the order in file1. | |
61 | */ | |
62 | struct entry *next, *previous; | |
2477ab2e JT |
63 | |
64 | /* | |
65 | * If 1, this entry can serve as an anchor. See | |
66 | * Documentation/diff-options.txt for more information. | |
67 | */ | |
68 | unsigned anchor : 1; | |
92b7de93 JS |
69 | } *entries, *first, *last; |
70 | /* were common records found? */ | |
71 | unsigned long has_matches; | |
72 | mmfile_t *file1, *file2; | |
73 | xdfenv_t *env; | |
74 | xpparam_t const *xpp; | |
75 | }; | |
76 | ||
2477ab2e JT |
77 | static int is_anchor(xpparam_t const *xpp, const char *line) |
78 | { | |
79 | int i; | |
80 | for (i = 0; i < xpp->anchors_nr; i++) { | |
81 | if (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i]))) | |
82 | return 1; | |
83 | } | |
84 | return 0; | |
85 | } | |
86 | ||
92b7de93 | 87 | /* The argument "pass" is 1 for the first file, 2 for the second. */ |
2477ab2e JT |
88 | static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map, |
89 | int pass) | |
92b7de93 JS |
90 | { |
91 | xrecord_t **records = pass == 1 ? | |
92 | map->env->xdf1.recs : map->env->xdf2.recs; | |
93 | xrecord_t *record = records[line - 1], *other; | |
94 | /* | |
95 | * After xdl_prepare_env() (or more precisely, due to | |
96 | * xdl_classify_record()), the "ha" member of the records (AKA lines) | |
97 | * is _not_ the hash anymore, but a linearized version of it. In | |
98 | * other words, the "ha" member is guaranteed to start with 0 and | |
99 | * the second record's ha can only be 0 or 1, etc. | |
100 | * | |
101 | * So we multiply ha by 2 in the hope that the hashing was | |
102 | * "unique enough". | |
103 | */ | |
104 | int index = (int)((record->ha << 1) % map->alloc); | |
105 | ||
106 | while (map->entries[index].line1) { | |
107 | other = map->env->xdf1.recs[map->entries[index].line1 - 1]; | |
108 | if (map->entries[index].hash != record->ha || | |
109 | !xdl_recmatch(record->ptr, record->size, | |
110 | other->ptr, other->size, | |
111 | map->xpp->flags)) { | |
112 | if (++index >= map->alloc) | |
113 | index = 0; | |
114 | continue; | |
115 | } | |
116 | if (pass == 2) | |
117 | map->has_matches = 1; | |
118 | if (pass == 1 || map->entries[index].line2) | |
119 | map->entries[index].line2 = NON_UNIQUE; | |
120 | else | |
121 | map->entries[index].line2 = line; | |
122 | return; | |
123 | } | |
124 | if (pass == 2) | |
125 | return; | |
126 | map->entries[index].line1 = line; | |
127 | map->entries[index].hash = record->ha; | |
2477ab2e | 128 | map->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr); |
92b7de93 JS |
129 | if (!map->first) |
130 | map->first = map->entries + index; | |
131 | if (map->last) { | |
132 | map->last->next = map->entries + index; | |
133 | map->entries[index].previous = map->last; | |
134 | } | |
135 | map->last = map->entries + index; | |
136 | map->nr++; | |
137 | } | |
138 | ||
139 | /* | |
140 | * This function has to be called for each recursion into the inter-hunk | |
141 | * parts, as previously non-unique lines can become unique when being | |
142 | * restricted to a smaller part of the files. | |
143 | * | |
144 | * It is assumed that env has been prepared using xdl_prepare(). | |
145 | */ | |
146 | static int fill_hashmap(mmfile_t *file1, mmfile_t *file2, | |
147 | xpparam_t const *xpp, xdfenv_t *env, | |
148 | struct hashmap *result, | |
149 | int line1, int count1, int line2, int count2) | |
150 | { | |
151 | result->file1 = file1; | |
152 | result->file2 = file2; | |
153 | result->xpp = xpp; | |
154 | result->env = env; | |
155 | ||
156 | /* We know exactly how large we want the hash map */ | |
157 | result->alloc = count1 * 2; | |
158 | result->entries = (struct entry *) | |
159 | xdl_malloc(result->alloc * sizeof(struct entry)); | |
160 | if (!result->entries) | |
161 | return -1; | |
162 | memset(result->entries, 0, result->alloc * sizeof(struct entry)); | |
163 | ||
164 | /* First, fill with entries from the first file */ | |
165 | while (count1--) | |
2477ab2e | 166 | insert_record(xpp, line1++, result, 1); |
92b7de93 JS |
167 | |
168 | /* Then search for matches in the second file */ | |
169 | while (count2--) | |
2477ab2e | 170 | insert_record(xpp, line2++, result, 2); |
92b7de93 JS |
171 | |
172 | return 0; | |
173 | } | |
174 | ||
175 | /* | |
176 | * Find the longest sequence with a smaller last element (meaning a smaller | |
177 | * line2, as we construct the sequence with entries ordered by line1). | |
178 | */ | |
179 | static int binary_search(struct entry **sequence, int longest, | |
180 | struct entry *entry) | |
181 | { | |
182 | int left = -1, right = longest; | |
183 | ||
184 | while (left + 1 < right) { | |
19716b21 | 185 | int middle = left + (right - left) / 2; |
92b7de93 JS |
186 | /* by construction, no two entries can be equal */ |
187 | if (sequence[middle]->line2 > entry->line2) | |
188 | right = middle; | |
189 | else | |
190 | left = middle; | |
191 | } | |
192 | /* return the index in "sequence", _not_ the sequence length */ | |
193 | return left; | |
194 | } | |
195 | ||
196 | /* | |
197 | * The idea is to start with the list of common unique lines sorted by | |
198 | * the order in file1. For each of these pairs, the longest (partial) | |
199 | * sequence whose last element's line2 is smaller is determined. | |
200 | * | |
201 | * For efficiency, the sequences are kept in a list containing exactly one | |
202 | * item per sequence length: the sequence with the smallest last | |
203 | * element (in terms of line2). | |
204 | */ | |
205 | static struct entry *find_longest_common_sequence(struct hashmap *map) | |
206 | { | |
207 | struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *)); | |
208 | int longest = 0, i; | |
209 | struct entry *entry; | |
210 | ||
2477ab2e JT |
211 | /* |
212 | * If not -1, this entry in sequence must never be overridden. | |
213 | * Therefore, overriding entries before this has no effect, so | |
214 | * do not do that either. | |
215 | */ | |
216 | int anchor_i = -1; | |
217 | ||
92b7de93 JS |
218 | for (entry = map->first; entry; entry = entry->next) { |
219 | if (!entry->line2 || entry->line2 == NON_UNIQUE) | |
220 | continue; | |
221 | i = binary_search(sequence, longest, entry); | |
222 | entry->previous = i < 0 ? NULL : sequence[i]; | |
2477ab2e JT |
223 | ++i; |
224 | if (i <= anchor_i) | |
225 | continue; | |
226 | sequence[i] = entry; | |
227 | if (entry->anchor) { | |
228 | anchor_i = i; | |
229 | longest = anchor_i + 1; | |
230 | } else if (i == longest) { | |
92b7de93 | 231 | longest++; |
2477ab2e | 232 | } |
92b7de93 JS |
233 | } |
234 | ||
235 | /* No common unique lines were found */ | |
236 | if (!longest) { | |
237 | xdl_free(sequence); | |
238 | return NULL; | |
239 | } | |
240 | ||
241 | /* Iterate starting at the last element, adjusting the "next" members */ | |
242 | entry = sequence[longest - 1]; | |
243 | entry->next = NULL; | |
244 | while (entry->previous) { | |
245 | entry->previous->next = entry; | |
246 | entry = entry->previous; | |
247 | } | |
248 | xdl_free(sequence); | |
249 | return entry; | |
250 | } | |
251 | ||
252 | static int match(struct hashmap *map, int line1, int line2) | |
253 | { | |
254 | xrecord_t *record1 = map->env->xdf1.recs[line1 - 1]; | |
255 | xrecord_t *record2 = map->env->xdf2.recs[line2 - 1]; | |
256 | return xdl_recmatch(record1->ptr, record1->size, | |
257 | record2->ptr, record2->size, map->xpp->flags); | |
258 | } | |
259 | ||
260 | static int patience_diff(mmfile_t *file1, mmfile_t *file2, | |
261 | xpparam_t const *xpp, xdfenv_t *env, | |
262 | int line1, int count1, int line2, int count2); | |
263 | ||
264 | static int walk_common_sequence(struct hashmap *map, struct entry *first, | |
265 | int line1, int count1, int line2, int count2) | |
266 | { | |
267 | int end1 = line1 + count1, end2 = line2 + count2; | |
268 | int next1, next2; | |
269 | ||
270 | for (;;) { | |
271 | /* Try to grow the line ranges of common lines */ | |
272 | if (first) { | |
273 | next1 = first->line1; | |
274 | next2 = first->line2; | |
275 | while (next1 > line1 && next2 > line2 && | |
276 | match(map, next1 - 1, next2 - 1)) { | |
277 | next1--; | |
278 | next2--; | |
279 | } | |
280 | } else { | |
281 | next1 = end1; | |
282 | next2 = end2; | |
283 | } | |
284 | while (line1 < next1 && line2 < next2 && | |
285 | match(map, line1, line2)) { | |
286 | line1++; | |
287 | line2++; | |
288 | } | |
289 | ||
290 | /* Recurse */ | |
291 | if (next1 > line1 || next2 > line2) { | |
292 | struct hashmap submap; | |
293 | ||
294 | memset(&submap, 0, sizeof(submap)); | |
295 | if (patience_diff(map->file1, map->file2, | |
296 | map->xpp, map->env, | |
297 | line1, next1 - line1, | |
298 | line2, next2 - line2)) | |
299 | return -1; | |
300 | } | |
301 | ||
302 | if (!first) | |
303 | return 0; | |
304 | ||
305 | while (first->next && | |
306 | first->next->line1 == first->line1 + 1 && | |
307 | first->next->line2 == first->line2 + 1) | |
308 | first = first->next; | |
309 | ||
310 | line1 = first->line1 + 1; | |
311 | line2 = first->line2 + 1; | |
312 | ||
313 | first = first->next; | |
314 | } | |
315 | } | |
316 | ||
317 | static int fall_back_to_classic_diff(struct hashmap *map, | |
318 | int line1, int count1, int line2, int count2) | |
319 | { | |
92b7de93 | 320 | xpparam_t xpp; |
307ab20b | 321 | xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; |
92b7de93 | 322 | |
1d26b252 TRC |
323 | return xdl_fall_back_diff(map->env, &xpp, |
324 | line1, count1, line2, count2); | |
92b7de93 JS |
325 | } |
326 | ||
327 | /* | |
328 | * Recursively find the longest common sequence of unique lines, | |
329 | * and if none was found, ask xdl_do_diff() to do the job. | |
330 | * | |
331 | * This function assumes that env was prepared with xdl_prepare_env(). | |
332 | */ | |
333 | static int patience_diff(mmfile_t *file1, mmfile_t *file2, | |
334 | xpparam_t const *xpp, xdfenv_t *env, | |
335 | int line1, int count1, int line2, int count2) | |
336 | { | |
337 | struct hashmap map; | |
338 | struct entry *first; | |
339 | int result = 0; | |
340 | ||
341 | /* trivial case: one side is empty */ | |
342 | if (!count1) { | |
343 | while(count2--) | |
344 | env->xdf2.rchg[line2++ - 1] = 1; | |
345 | return 0; | |
346 | } else if (!count2) { | |
347 | while(count1--) | |
348 | env->xdf1.rchg[line1++ - 1] = 1; | |
349 | return 0; | |
350 | } | |
351 | ||
352 | memset(&map, 0, sizeof(map)); | |
353 | if (fill_hashmap(file1, file2, xpp, env, &map, | |
354 | line1, count1, line2, count2)) | |
355 | return -1; | |
356 | ||
357 | /* are there any matching lines at all? */ | |
358 | if (!map.has_matches) { | |
359 | while(count1--) | |
360 | env->xdf1.rchg[line1++ - 1] = 1; | |
361 | while(count2--) | |
362 | env->xdf2.rchg[line2++ - 1] = 1; | |
363 | xdl_free(map.entries); | |
364 | return 0; | |
365 | } | |
366 | ||
367 | first = find_longest_common_sequence(&map); | |
368 | if (first) | |
369 | result = walk_common_sequence(&map, first, | |
370 | line1, count1, line2, count2); | |
371 | else | |
372 | result = fall_back_to_classic_diff(&map, | |
373 | line1, count1, line2, count2); | |
374 | ||
375 | xdl_free(map.entries); | |
376 | return result; | |
377 | } | |
378 | ||
379 | int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2, | |
380 | xpparam_t const *xpp, xdfenv_t *env) | |
381 | { | |
382 | if (xdl_prepare_env(file1, file2, xpp, env) < 0) | |
383 | return -1; | |
384 | ||
385 | /* environment is cleaned up in xdl_diff() */ | |
386 | return patience_diff(file1, file2, xpp, env, | |
387 | 1, env->xdf1.nrec, 1, env->xdf2.nrec); | |
388 | } |