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