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