Mercurial > vim

comparison src/xdiff/xpatience.c @ 32174:f84e5db372ea v9.0.1418

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
patch 9.0.1418: the included xdiff code is a bit outdated Commit: https://github.com/vim/vim/commit/5fedb8a5ab7addb584728c89e809be190de992bf Author: Yee Cheng Chin <ychin.git@gmail.com> Date: Mon Mar 20 17:30:52 2023 +0000 patch 9.0.1418: the included xdiff code is a bit outdated Problem: The included xdiff code is a bit outdated. Solution: Sync with the latest git xdiff code. (Yee Cheng Chin, closes #12181)
author Bram Moolenaar <Bram@vim.org>
date Mon, 20 Mar 2023 18:45:04 +0100
parents d5142d87f898
children
comparison
equal deleted inserted replaced
32173:1d3bf14313b6 32174:f84e5db372ea
67 */ 67 */
68 unsigned anchor : 1; 68 unsigned anchor : 1;
69 } *entries, *first, *last; 69 } *entries, *first, *last;
70 /* were common records found? */ 70 /* were common records found? */
71 unsigned long has_matches; 71 unsigned long has_matches;
72 mmfile_t *file1, *file2;
73 xdfenv_t *env; 72 xdfenv_t *env;
74 xpparam_t const *xpp; 73 xpparam_t const *xpp;
75 }; 74 };
76 75
77 static int is_anchor(xpparam_t const *xpp, const char *line) 76 static int is_anchor(xpparam_t const *xpp, const char *line)
137 * parts, as previously non-unique lines can become unique when being 136 * parts, as previously non-unique lines can become unique when being
138 * restricted to a smaller part of the files. 137 * restricted to a smaller part of the files.
139 * 138 *
140 * It is assumed that env has been prepared using xdl_prepare(). 139 * It is assumed that env has been prepared using xdl_prepare().
141 */ 140 */
142 static int fill_hashmap(mmfile_t *file1, mmfile_t *file2, 141 static int fill_hashmap(xpparam_t const *xpp, xdfenv_t *env,
143 xpparam_t const *xpp, xdfenv_t *env,
144 struct hashmap *result, 142 struct hashmap *result,
145 int line1, int count1, int line2, int count2) 143 int line1, int count1, int line2, int count2)
146 { 144 {
147 result->file1 = file1;
148 result->file2 = file2;
149 result->xpp = xpp; 145 result->xpp = xpp;
150 result->env = env; 146 result->env = env;
151 147
152 /* We know exactly how large we want the hash map */ 148 /* We know exactly how large we want the hash map */
153 result->alloc = count1 * 2; 149 result->alloc = count1 * 2;
154 result->entries = (struct entry *) 150 if (!XDL_CALLOC_ARRAY(result->entries, result->alloc))
155 xdl_malloc(result->alloc * sizeof(struct entry));
156 if (!result->entries)
157 return -1; 151 return -1;
158 memset(result->entries, 0, result->alloc * sizeof(struct entry));
159 152
160 /* First, fill with entries from the first file */ 153 /* First, fill with entries from the first file */
161 while (count1--) 154 while (count1--)
162 insert_record(xpp, line1++, result, 1); 155 insert_record(xpp, line1++, result, 1);
163 156
196 * 189 *
197 * For efficiency, the sequences are kept in a list containing exactly one 190 * For efficiency, the sequences are kept in a list containing exactly one
198 * item per sequence length: the sequence with the smallest last 191 * item per sequence length: the sequence with the smallest last
199 * element (in terms of line2). 192 * element (in terms of line2).
200 */ 193 */
201 static struct entry *find_longest_common_sequence(struct hashmap *map) 194 static int find_longest_common_sequence(struct hashmap *map, struct entry **res)
202 { 195 {
203 struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *)); 196 struct entry **sequence;
204 int longest = 0, i; 197 int longest = 0, i;
205 struct entry *entry; 198 struct entry *entry;
206 199
207 /* 200 /*
208 * If not -1, this entry in sequence must never be overridden. 201 * If not -1, this entry in sequence must never be overridden.
209 * Therefore, overriding entries before this has no effect, so 202 * Therefore, overriding entries before this has no effect, so
210 * do not do that either. 203 * do not do that either.
211 */ 204 */
212 int anchor_i = -1; 205 int anchor_i = -1;
213 206
214 // Added to silence Coverity. 207 if (!XDL_ALLOC_ARRAY(sequence, map->nr))
215 if (sequence == NULL) 208 return -1;
216 return map->first;
217 209
218 for (entry = map->first; entry; entry = entry->next) { 210 for (entry = map->first; entry; entry = entry->next) {
219 if (!entry->line2 || entry->line2 == NON_UNIQUE) 211 if (!entry->line2 || entry->line2 == NON_UNIQUE)
220 continue; 212 continue;
221 i = binary_search(sequence, longest, entry); 213 i = binary_search(sequence, longest, entry);
232 } 224 }
233 } 225 }
234 226
235 /* No common unique lines were found */ 227 /* No common unique lines were found */
236 if (!longest) { 228 if (!longest) {
229 *res = NULL;
237 xdl_free(sequence); 230 xdl_free(sequence);
238 return NULL; 231 return 0;
239 } 232 }
240 233
241 /* Iterate starting at the last element, adjusting the "next" members */ 234 /* Iterate starting at the last element, adjusting the "next" members */
242 entry = sequence[longest - 1]; 235 entry = sequence[longest - 1];
243 entry->next = NULL; 236 entry->next = NULL;
244 while (entry->previous) { 237 while (entry->previous) {
245 entry->previous->next = entry; 238 entry->previous->next = entry;
246 entry = entry->previous; 239 entry = entry->previous;
247 } 240 }
241 *res = entry;
248 xdl_free(sequence); 242 xdl_free(sequence);
249 return entry; 243 return 0;
250 } 244 }
251 245
252 static int match(struct hashmap *map, int line1, int line2) 246 static int match(struct hashmap *map, int line1, int line2)
253 { 247 {
254 xrecord_t *record1 = map->env->xdf1.recs[line1 - 1]; 248 xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];
255 xrecord_t *record2 = map->env->xdf2.recs[line2 - 1]; 249 xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];
256 return record1->ha == record2->ha; 250 return record1->ha == record2->ha;
257 } 251 }
258 252
259 static int patience_diff(mmfile_t *file1, mmfile_t *file2, 253 static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,
260 xpparam_t const *xpp, xdfenv_t *env,
261 int line1, int count1, int line2, int count2); 254 int line1, int count1, int line2, int count2);
262 255
263 static int walk_common_sequence(struct hashmap *map, struct entry *first, 256 static int walk_common_sequence(struct hashmap *map, struct entry *first,
264 int line1, int count1, int line2, int count2) 257 int line1, int count1, int line2, int count2)
265 { 258 {
286 line2++; 279 line2++;
287 } 280 }
288 281
289 /* Recurse */ 282 /* Recurse */
290 if (next1 > line1 || next2 > line2) { 283 if (next1 > line1 || next2 > line2) {
291 if (patience_diff(map->file1, map->file2, 284 if (patience_diff(map->xpp, map->env,
292 map->xpp, map->env,
293 line1, next1 - line1, 285 line1, next1 - line1,
294 line2, next2 - line2)) 286 line2, next2 - line2))
295 return -1; 287 return -1;
296 } 288 }
297 289
326 * Recursively find the longest common sequence of unique lines, 318 * Recursively find the longest common sequence of unique lines,
327 * and if none was found, ask xdl_do_diff() to do the job. 319 * and if none was found, ask xdl_do_diff() to do the job.
328 * 320 *
329 * This function assumes that env was prepared with xdl_prepare_env(). 321 * This function assumes that env was prepared with xdl_prepare_env().
330 */ 322 */
331 static int patience_diff(mmfile_t *file1, mmfile_t *file2, 323 static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,
332 xpparam_t const *xpp, xdfenv_t *env,
333 int line1, int count1, int line2, int count2) 324 int line1, int count1, int line2, int count2)
334 { 325 {
335 struct hashmap map; 326 struct hashmap map;
336 struct entry *first; 327 struct entry *first;
337 int result = 0; 328 int result = 0;
346 env->xdf1.rchg[line1++ - 1] = 1; 337 env->xdf1.rchg[line1++ - 1] = 1;
347 return 0; 338 return 0;
348 } 339 }
349 340
350 memset(&map, 0, sizeof(map)); 341 memset(&map, 0, sizeof(map));
351 if (fill_hashmap(file1, file2, xpp, env, &map, 342 if (fill_hashmap(xpp, env, &map,
352 line1, count1, line2, count2)) 343 line1, count1, line2, count2))
353 return -1; 344 return -1;
354 345
355 /* are there any matching lines at all? */ 346 /* are there any matching lines at all? */
356 if (!map.has_matches) { 347 if (!map.has_matches) {
360 env->xdf2.rchg[line2++ - 1] = 1; 351 env->xdf2.rchg[line2++ - 1] = 1;
361 xdl_free(map.entries); 352 xdl_free(map.entries);
362 return 0; 353 return 0;
363 } 354 }
364 355
365 first = find_longest_common_sequence(&map); 356 result = find_longest_common_sequence(&map, &first);
357 if (result)
358 goto out;
366 if (first) 359 if (first)
367 result = walk_common_sequence(&map, first, 360 result = walk_common_sequence(&map, first,
368 line1, count1, line2, count2); 361 line1, count1, line2, count2);
369 else 362 else
370 result = fall_back_to_classic_diff(&map, 363 result = fall_back_to_classic_diff(&map,
371 line1, count1, line2, count2); 364 line1, count1, line2, count2);
372 365 out:
373 xdl_free(map.entries); 366 xdl_free(map.entries);
374 return result; 367 return result;
375 } 368 }
376 369
377 int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2, 370 int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env)
378 xpparam_t const *xpp, xdfenv_t *env) 371 {
379 { 372 return patience_diff(xpp, env, 1, env->xdf1.nrec, 1, env->xdf2.nrec);
380 if (xdl_prepare_env(file1, file2, xpp, env) < 0) 373 }
381 return -1;
382
383 /* environment is cleaned up in xdl_diff() */
384 return patience_diff(file1, file2, xpp, env,
385 1, env->xdf1.nrec, 1, env->xdf2.nrec);
386 }