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 */
49struct 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
79static 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. */
90static 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 */
148static 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 */
181static 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 */
207static 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
257static 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
265static 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
269static 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
322static 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 */
338static 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
384int 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