Mercurial > vim

annotate src/xdiff/xpatience.c @ 28942:6cdf55afaae9 v8.2.4993

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