| /* |
| * LibXDiff by Davide Libenzi ( File Differential Library ) |
| * Copyright (C) 2003-2016 Davide Libenzi, Johannes E. Schindelin |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Lesser General Public |
| * License as published by the Free Software Foundation; either |
| * version 2.1 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Lesser General Public License for more details. |
| * |
| * You should have received a copy of the GNU Lesser General Public |
| * License along with this library; if not, see |
| * <http://www.gnu.org/licenses/>. |
| * |
| * Davide Libenzi <davidel@xmailserver.org> |
| * |
| */ |
| #include "xinclude.h" |
| |
| /* |
| * The basic idea of patience diff is to find lines that are unique in |
| * both files. These are intuitively the ones that we want to see as |
| * common lines. |
| * |
| * The maximal ordered sequence of such line pairs (where ordered means |
| * that the order in the sequence agrees with the order of the lines in |
| * both files) naturally defines an initial set of common lines. |
| * |
| * Now, the algorithm tries to extend the set of common lines by growing |
| * the line ranges where the files have identical lines. |
| * |
| * Between those common lines, the patience diff algorithm is applied |
| * recursively, until no unique line pairs can be found; these line ranges |
| * are handled by the well-known Myers algorithm. |
| */ |
| |
| #define NON_UNIQUE ULONG_MAX |
| |
| /* |
| * This is a hash mapping from line hash to line numbers in the first and |
| * second file. |
| */ |
| struct hashmap { |
| int nr, alloc; |
| struct entry { |
| unsigned long hash; |
| /* |
| * 0 = unused entry, 1 = first line, 2 = second, etc. |
| * line2 is NON_UNIQUE if the line is not unique |
| * in either the first or the second file. |
| */ |
| unsigned long line1, line2; |
| /* |
| * "next" & "previous" are used for the longest common |
| * sequence; |
| * initially, "next" reflects only the order in file1. |
| */ |
| struct entry *next, *previous; |
| |
| /* |
| * If 1, this entry can serve as an anchor. See |
| * Documentation/diff-options.txt for more information. |
| */ |
| unsigned anchor : 1; |
| } *entries, *first, *last; |
| /* were common records found? */ |
| unsigned long has_matches; |
| xdfenv_t *env; |
| xpparam_t const *xpp; |
| }; |
| |
| static int is_anchor(xpparam_t const *xpp, const char *line) |
| { |
| int i; |
| for (i = 0; i < xpp->anchors_nr; i++) { |
| if (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i]))) |
| return 1; |
| } |
| return 0; |
| } |
| |
| /* The argument "pass" is 1 for the first file, 2 for the second. */ |
| static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map, |
| int pass) |
| { |
| xrecord_t **records = pass == 1 ? |
| map->env->xdf1.recs : map->env->xdf2.recs; |
| xrecord_t *record = records[line - 1]; |
| /* |
| * After xdl_prepare_env() (or more precisely, due to |
| * xdl_classify_record()), the "ha" member of the records (AKA lines) |
| * is _not_ the hash anymore, but a linearized version of it. In |
| * other words, the "ha" member is guaranteed to start with 0 and |
| * the second record's ha can only be 0 or 1, etc. |
| * |
| * So we multiply ha by 2 in the hope that the hashing was |
| * "unique enough". |
| */ |
| int index = (int)((record->ha << 1) % map->alloc); |
| |
| while (map->entries[index].line1) { |
| if (map->entries[index].hash != record->ha) { |
| if (++index >= map->alloc) |
| index = 0; |
| continue; |
| } |
| if (pass == 2) |
| map->has_matches = 1; |
| if (pass == 1 || map->entries[index].line2) |
| map->entries[index].line2 = NON_UNIQUE; |
| else |
| map->entries[index].line2 = line; |
| return; |
| } |
| if (pass == 2) |
| return; |
| map->entries[index].line1 = line; |
| map->entries[index].hash = record->ha; |
| map->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr); |
| if (!map->first) |
| map->first = map->entries + index; |
| if (map->last) { |
| map->last->next = map->entries + index; |
| map->entries[index].previous = map->last; |
| } |
| map->last = map->entries + index; |
| map->nr++; |
| } |
| |
| /* |
| * This function has to be called for each recursion into the inter-hunk |
| * parts, as previously non-unique lines can become unique when being |
| * restricted to a smaller part of the files. |
| * |
| * It is assumed that env has been prepared using xdl_prepare(). |
| */ |
| static int fill_hashmap(xpparam_t const *xpp, xdfenv_t *env, |
| struct hashmap *result, |
| int line1, int count1, int line2, int count2) |
| { |
| result->xpp = xpp; |
| result->env = env; |
| |
| /* We know exactly how large we want the hash map */ |
| result->alloc = count1 * 2; |
| if (!XDL_CALLOC_ARRAY(result->entries, result->alloc)) |
| return -1; |
| |
| /* First, fill with entries from the first file */ |
| while (count1--) |
| insert_record(xpp, line1++, result, 1); |
| |
| /* Then search for matches in the second file */ |
| while (count2--) |
| insert_record(xpp, line2++, result, 2); |
| |
| return 0; |
| } |
| |
| /* |
| * Find the longest sequence with a smaller last element (meaning a smaller |
| * line2, as we construct the sequence with entries ordered by line1). |
| */ |
| static int binary_search(struct entry **sequence, int longest, |
| struct entry *entry) |
| { |
| int left = -1, right = longest; |
| |
| while (left + 1 < right) { |
| int middle = left + (right - left) / 2; |
| /* by construction, no two entries can be equal */ |
| if (sequence[middle]->line2 > entry->line2) |
| right = middle; |
| else |
| left = middle; |
| } |
| /* return the index in "sequence", _not_ the sequence length */ |
| return left; |
| } |
| |
| /* |
| * The idea is to start with the list of common unique lines sorted by |
| * the order in file1. For each of these pairs, the longest (partial) |
| * sequence whose last element's line2 is smaller is determined. |
| * |
| * For efficiency, the sequences are kept in a list containing exactly one |
| * item per sequence length: the sequence with the smallest last |
| * element (in terms of line2). |
| */ |
| static int find_longest_common_sequence(struct hashmap *map, struct entry **res) |
| { |
| struct entry **sequence; |
| int longest = 0, i; |
| struct entry *entry; |
| |
| /* |
| * If not -1, this entry in sequence must never be overridden. |
| * Therefore, overriding entries before this has no effect, so |
| * do not do that either. |
| */ |
| int anchor_i = -1; |
| |
| if (!XDL_ALLOC_ARRAY(sequence, map->nr)) |
| return -1; |
| |
| for (entry = map->first; entry; entry = entry->next) { |
| if (!entry->line2 || entry->line2 == NON_UNIQUE) |
| continue; |
| i = binary_search(sequence, longest, entry); |
| entry->previous = i < 0 ? NULL : sequence[i]; |
| ++i; |
| if (i <= anchor_i) |
| continue; |
| sequence[i] = entry; |
| if (entry->anchor) { |
| anchor_i = i; |
| longest = anchor_i + 1; |
| } else if (i == longest) { |
| longest++; |
| } |
| } |
| |
| /* No common unique lines were found */ |
| if (!longest) { |
| *res = NULL; |
| xdl_free(sequence); |
| return 0; |
| } |
| |
| /* Iterate starting at the last element, adjusting the "next" members */ |
| entry = sequence[longest - 1]; |
| entry->next = NULL; |
| while (entry->previous) { |
| entry->previous->next = entry; |
| entry = entry->previous; |
| } |
| *res = entry; |
| xdl_free(sequence); |
| return 0; |
| } |
| |
| static int match(struct hashmap *map, int line1, int line2) |
| { |
| xrecord_t *record1 = map->env->xdf1.recs[line1 - 1]; |
| xrecord_t *record2 = map->env->xdf2.recs[line2 - 1]; |
| return record1->ha == record2->ha; |
| } |
| |
| static int patience_diff(xpparam_t const *xpp, xdfenv_t *env, |
| int line1, int count1, int line2, int count2); |
| |
| static int walk_common_sequence(struct hashmap *map, struct entry *first, |
| int line1, int count1, int line2, int count2) |
| { |
| int end1 = line1 + count1, end2 = line2 + count2; |
| int next1, next2; |
| |
| for (;;) { |
| /* Try to grow the line ranges of common lines */ |
| if (first) { |
| next1 = first->line1; |
| next2 = first->line2; |
| while (next1 > line1 && next2 > line2 && |
| match(map, next1 - 1, next2 - 1)) { |
| next1--; |
| next2--; |
| } |
| } else { |
| next1 = end1; |
| next2 = end2; |
| } |
| while (line1 < next1 && line2 < next2 && |
| match(map, line1, line2)) { |
| line1++; |
| line2++; |
| } |
| |
| /* Recurse */ |
| if (next1 > line1 || next2 > line2) { |
| if (patience_diff(map->xpp, map->env, |
| line1, next1 - line1, |
| line2, next2 - line2)) |
| return -1; |
| } |
| |
| if (!first) |
| return 0; |
| |
| while (first->next && |
| first->next->line1 == first->line1 + 1 && |
| first->next->line2 == first->line2 + 1) |
| first = first->next; |
| |
| line1 = first->line1 + 1; |
| line2 = first->line2 + 1; |
| |
| first = first->next; |
| } |
| } |
| |
| static int fall_back_to_classic_diff(struct hashmap *map, |
| int line1, int count1, int line2, int count2) |
| { |
| xpparam_t xpp; |
| |
| memset(&xpp, 0, sizeof(xpp)); |
| xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; |
| |
| return xdl_fall_back_diff(map->env, &xpp, |
| line1, count1, line2, count2); |
| } |
| |
| /* |
| * Recursively find the longest common sequence of unique lines, |
| * and if none was found, ask xdl_do_diff() to do the job. |
| * |
| * This function assumes that env was prepared with xdl_prepare_env(). |
| */ |
| static int patience_diff(xpparam_t const *xpp, xdfenv_t *env, |
| int line1, int count1, int line2, int count2) |
| { |
| struct hashmap map; |
| struct entry *first; |
| int result = 0; |
| |
| /* trivial case: one side is empty */ |
| if (!count1) { |
| while(count2--) |
| env->xdf2.rchg[line2++ - 1] = 1; |
| return 0; |
| } else if (!count2) { |
| while(count1--) |
| env->xdf1.rchg[line1++ - 1] = 1; |
| return 0; |
| } |
| |
| memset(&map, 0, sizeof(map)); |
| if (fill_hashmap(xpp, env, &map, |
| line1, count1, line2, count2)) |
| return -1; |
| |
| /* are there any matching lines at all? */ |
| if (!map.has_matches) { |
| while(count1--) |
| env->xdf1.rchg[line1++ - 1] = 1; |
| while(count2--) |
| env->xdf2.rchg[line2++ - 1] = 1; |
| xdl_free(map.entries); |
| return 0; |
| } |
| |
| result = find_longest_common_sequence(&map, &first); |
| if (result) |
| goto out; |
| if (first) |
| result = walk_common_sequence(&map, first, |
| line1, count1, line2, count2); |
| else |
| result = fall_back_to_classic_diff(&map, |
| line1, count1, line2, count2); |
| out: |
| xdl_free(map.entries); |
| return result; |
| } |
| |
| int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env) |
| { |
| return patience_diff(xpp, env, 1, env->xdf1.nrec, 1, env->xdf2.nrec); |
| } |