Merge branch 'cc/svn-fe-py-shebang'
[git/git.git] / xdiff / xpatience.c
CommitLineData
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 */
47struct 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
77static 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
88static 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 */
146static 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 */
179static 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 */
205static 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
252static 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
260static 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
264static 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
317static 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 */
333static 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
379int 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}