Mercurial > vim
comparison src/xdiff/xpatience.c @ 14696:195e8b1fcbbf v8.1.0360
patch 8.1.0360: using an external diff program is slow and inflexible
commit https://github.com/vim/vim/commit/e828b7621cf9065a3582be0c4dd1e0e846e335bf
Author: Bram Moolenaar <Bram@vim.org>
Date: Mon Sep 10 17:51:58 2018 +0200
patch 8.1.0360: using an external diff program is slow and inflexible
Problem: Using an external diff program is slow and inflexible.
Solution: Include the xdiff library. (Christian Brabandt, closes https://github.com/vim/vim/issues/2732)
Use it by default.
author | Christian Brabandt <cb@256bit.org> |
---|---|
date | Mon, 10 Sep 2018 18:00:06 +0200 |
parents | |
children | 193471015e1a |
comparison
equal
deleted
inserted
replaced
14695:b178e2039b2d | 14696:195e8b1fcbbf |
---|---|
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 = xdl_malloc(map->nr * sizeof(struct entry *)); | |
210 int longest = 0, i; | |
211 struct entry *entry; | |
212 | |
213 /* | |
214 * If not -1, this entry in sequence must never be overridden. | |
215 * Therefore, overriding entries before this has no effect, so | |
216 * do not do that either. | |
217 */ | |
218 int anchor_i = -1; | |
219 | |
220 for (entry = map->first; entry; entry = entry->next) { | |
221 if (!entry->line2 || entry->line2 == NON_UNIQUE) | |
222 continue; | |
223 i = binary_search(sequence, longest, entry); | |
224 entry->previous = i < 0 ? NULL : sequence[i]; | |
225 ++i; | |
226 if (i <= anchor_i) | |
227 continue; | |
228 sequence[i] = entry; | |
229 if (entry->anchor) { | |
230 anchor_i = i; | |
231 longest = anchor_i + 1; | |
232 } else if (i == longest) { | |
233 longest++; | |
234 } | |
235 } | |
236 | |
237 /* No common unique lines were found */ | |
238 if (!longest) { | |
239 xdl_free(sequence); | |
240 return NULL; | |
241 } | |
242 | |
243 /* Iterate starting at the last element, adjusting the "next" members */ | |
244 entry = sequence[longest - 1]; | |
245 entry->next = NULL; | |
246 while (entry->previous) { | |
247 entry->previous->next = entry; | |
248 entry = entry->previous; | |
249 } | |
250 xdl_free(sequence); | |
251 return entry; | |
252 } | |
253 | |
254 static int match(struct hashmap *map, int line1, int line2) | |
255 { | |
256 xrecord_t *record1 = map->env->xdf1.recs[line1 - 1]; | |
257 xrecord_t *record2 = map->env->xdf2.recs[line2 - 1]; | |
258 return xdl_recmatch(record1->ptr, record1->size, | |
259 record2->ptr, record2->size, map->xpp->flags); | |
260 } | |
261 | |
262 static int patience_diff(mmfile_t *file1, mmfile_t *file2, | |
263 xpparam_t const *xpp, xdfenv_t *env, | |
264 int line1, int count1, int line2, int count2); | |
265 | |
266 static int walk_common_sequence(struct hashmap *map, struct entry *first, | |
267 int line1, int count1, int line2, int count2) | |
268 { | |
269 int end1 = line1 + count1, end2 = line2 + count2; | |
270 int next1, next2; | |
271 | |
272 for (;;) { | |
273 /* Try to grow the line ranges of common lines */ | |
274 if (first) { | |
275 next1 = first->line1; | |
276 next2 = first->line2; | |
277 while (next1 > line1 && next2 > line2 && | |
278 match(map, next1 - 1, next2 - 1)) { | |
279 next1--; | |
280 next2--; | |
281 } | |
282 } else { | |
283 next1 = end1; | |
284 next2 = end2; | |
285 } | |
286 while (line1 < next1 && line2 < next2 && | |
287 match(map, line1, line2)) { | |
288 line1++; | |
289 line2++; | |
290 } | |
291 | |
292 /* Recurse */ | |
293 if (next1 > line1 || next2 > line2) { | |
294 struct hashmap submap; | |
295 | |
296 memset(&submap, 0, sizeof(submap)); | |
297 if (patience_diff(map->file1, map->file2, | |
298 map->xpp, map->env, | |
299 line1, next1 - line1, | |
300 line2, next2 - line2)) | |
301 return -1; | |
302 } | |
303 | |
304 if (!first) | |
305 return 0; | |
306 | |
307 while (first->next && | |
308 first->next->line1 == first->line1 + 1 && | |
309 first->next->line2 == first->line2 + 1) | |
310 first = first->next; | |
311 | |
312 line1 = first->line1 + 1; | |
313 line2 = first->line2 + 1; | |
314 | |
315 first = first->next; | |
316 } | |
317 } | |
318 | |
319 static int fall_back_to_classic_diff(struct hashmap *map, | |
320 int line1, int count1, int line2, int count2) | |
321 { | |
322 xpparam_t xpp; | |
323 xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; | |
324 | |
325 return xdl_fall_back_diff(map->env, &xpp, | |
326 line1, count1, line2, count2); | |
327 } | |
328 | |
329 /* | |
330 * Recursively find the longest common sequence of unique lines, | |
331 * and if none was found, ask xdl_do_diff() to do the job. | |
332 * | |
333 * This function assumes that env was prepared with xdl_prepare_env(). | |
334 */ | |
335 static int patience_diff(mmfile_t *file1, mmfile_t *file2, | |
336 xpparam_t const *xpp, xdfenv_t *env, | |
337 int line1, int count1, int line2, int count2) | |
338 { | |
339 struct hashmap map; | |
340 struct entry *first; | |
341 int result = 0; | |
342 | |
343 /* trivial case: one side is empty */ | |
344 if (!count1) { | |
345 while(count2--) | |
346 env->xdf2.rchg[line2++ - 1] = 1; | |
347 return 0; | |
348 } else if (!count2) { | |
349 while(count1--) | |
350 env->xdf1.rchg[line1++ - 1] = 1; | |
351 return 0; | |
352 } | |
353 | |
354 memset(&map, 0, sizeof(map)); | |
355 if (fill_hashmap(file1, file2, xpp, env, &map, | |
356 line1, count1, line2, count2)) | |
357 return -1; | |
358 | |
359 /* are there any matching lines at all? */ | |
360 if (!map.has_matches) { | |
361 while(count1--) | |
362 env->xdf1.rchg[line1++ - 1] = 1; | |
363 while(count2--) | |
364 env->xdf2.rchg[line2++ - 1] = 1; | |
365 xdl_free(map.entries); | |
366 return 0; | |
367 } | |
368 | |
369 first = find_longest_common_sequence(&map); | |
370 if (first) | |
371 result = walk_common_sequence(&map, first, | |
372 line1, count1, line2, count2); | |
373 else | |
374 result = fall_back_to_classic_diff(&map, | |
375 line1, count1, line2, count2); | |
376 | |
377 xdl_free(map.entries); | |
378 return result; | |
379 } | |
380 | |
381 int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2, | |
382 xpparam_t const *xpp, xdfenv_t *env) | |
383 { | |
384 if (xdl_prepare_env(file1, file2, xpp, env) < 0) | |
385 return -1; | |
386 | |
387 /* environment is cleaned up in xdl_diff() */ | |
388 return patience_diff(file1, file2, xpp, env, | |
389 1, env->xdf1.nrec, 1, env->xdf2.nrec); | |
390 } |