vim: src/xdiff/xpatience.c annotate

annotate src/xdiff/xpatience.c @ 30731:2295ee9c025d v9.0.0700

patch 9.0.0700: there is no real need for a "big" build Commit: https://github.com/vim/vim/commit/25f3a146a0e4c731b8608f4cfbbfdf7a71b2d05e Author: Martin Tournoij <martin@arp242.net> Date: Sat Oct 8 19:26:41 2022 +0100 patch 9.0.0700: there is no real need for a "big" build Problem: There is no real need for a "big" build. Solution: Move common features to "normal" build, less often used features to the "huge" build. (Martin Tournoij, closes #11283)

author	Bram Moolenaar <Bram@vim.org>
date	Sat, 08 Oct 2022 20:30:05 +0200
parents	d5142d87f898
children	f84e5db372ea

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 }

Mercurial > vim

annotate src/xdiff/xpatience.c @ 30731:2295ee9c025d v9.0.0700