lib/diff_main.c

   1 /* Generic infrastructure to implement various diff algorithms (implementation). */
   2 /*
   3  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18
  19 #include <sys/queue.h>
  20 #include <ctype.h>
  21 #include <errno.h>
  22 #include <stdint.h>
  23 #include <stdlib.h>
  24 #include <stdbool.h>
  25 #include <stdio.h>
  26 #include <string.h>
  27 #include <limits.h>
  28 #include <unistd.h>
  29
  30 #include <assert.h>
  31
  32 #include <arraylist.h>
  33 #include <diff_main.h>
  34
  35 #include "got_compat.h"
  36
  37 #include "diff_internal.h"
  38 #include "diff_debug.h"
  39
  40 inline enum diff_chunk_type
  41 diff_chunk_type(const struct diff_chunk *chunk)
  42 {
  43         if (!chunk->left_count && !chunk->right_count)
  44                 return CHUNK_EMPTY;
  45         if (!chunk->solved)
  46                 return CHUNK_ERROR;
  47         if (!chunk->right_count)
  48                 return CHUNK_MINUS;
  49         if (!chunk->left_count)
  50                 return CHUNK_PLUS;
  51         if (chunk->left_count != chunk->right_count)
  52                 return CHUNK_ERROR;
  53         return CHUNK_SAME;
  54 }
  55
  56 static int
  57 read_at(FILE *f, off_t at_pos, unsigned char *buf, size_t len)
  58 {
  59         int r;
  60         if (fseeko(f, at_pos, SEEK_SET) == -1)
  61                 return errno;
  62         r = fread(buf, sizeof(char), len, f);
  63         if ((r == 0 || r < len) && ferror(f))
  64                 return EIO;
  65         if (r != len)
  66                 return EIO;
  67         return 0;
  68 }
  69
  70 static int
  71 buf_cmp(const unsigned char *left, size_t left_len,
  72         const unsigned char *right, size_t right_len,
  73         bool ignore_whitespace)
  74 {
  75         int cmp;
  76
  77         if (ignore_whitespace) {
  78                 int il = 0, ir = 0;
  79                 while (il < left_len && ir < right_len) {
  80                         unsigned char cl = left[il];
  81                         unsigned char cr = right[ir];
  82
  83                         if (isspace((unsigned char)cl) && il < left_len) {
  84                                 il++;
  85                                 continue;
  86                         }
  87                         if (isspace((unsigned char)cr) && ir < right_len) {
  88                                 ir++;
  89                                 continue;
  90                         }
  91
  92                         if (cl > cr)
  93                                 return 1;
  94                         if (cr > cl)
  95                                 return -1;
  96                         il++;
  97                         ir++;
  98                 }
  99                 while (il < left_len) {
 100                         unsigned char cl = left[il++];
 101                         if (!isspace((unsigned char)cl))
 102                                 return 1;
 103                 }
 104                 while (ir < right_len) {
 105                         unsigned char cr = right[ir++];
 106                         if (!isspace((unsigned char)cr))
 107                                 return -1;
 108                 }
 109
 110                 return 0;
 111         }
 112
 113         cmp = memcmp(left, right, MIN(left_len, right_len));
 114         if (cmp)
 115                 return cmp;
 116         if (left_len == right_len)
 117                 return 0;
 118         return (left_len > right_len) ? 1 : -1;
 119 }
 120
 121 int
 122 diff_atom_cmp(int *cmp,
 123               const struct diff_atom *left,
 124               const struct diff_atom *right)
 125 {
 126         off_t remain_left, remain_right;
 127         int flags = (left->root->diff_flags | right->root->diff_flags);
 128         bool ignore_whitespace = (flags & DIFF_FLAG_IGNORE_WHITESPACE);
 129
 130         if (!left->len && !right->len) {
 131                 *cmp = 0;
 132                 return 0;
 133         }
 134         if (!ignore_whitespace) {
 135                 if (!right->len) {
 136                         *cmp = 1;
 137                         return 0;
 138                 }
 139                 if (!left->len) {
 140                         *cmp = -1;
 141                         return 0;
 142                 }
 143         }
 144
 145         if (left->at != NULL && right->at != NULL) {
 146                 *cmp = buf_cmp(left->at, left->len, right->at, right->len,
 147                     ignore_whitespace);
 148                 return 0;
 149         }
 150
 151         remain_left = left->len;
 152         remain_right = right->len;
 153         while (remain_left > 0 || remain_right > 0) {
 154                 const size_t chunksz = 8192;
 155                 unsigned char buf_left[chunksz], buf_right[chunksz];
 156                 const uint8_t *p_left, *p_right;
 157                 off_t n_left, n_right;
 158                 ssize_t r;
 159
 160                 if (!remain_right) {
 161                         *cmp = 1;
 162                         return 0;
 163                 }
 164                 if (!remain_left) {
 165                         *cmp = -1;
 166                         return 0;
 167                 }
 168
 169                 n_left = MIN(chunksz, remain_left);
 170                 n_right = MIN(chunksz, remain_right);
 171
 172                 if (left->at == NULL) {
 173                         r = read_at(left->root->f,
 174                                     left->pos + (left->len - remain_left),
 175                                     buf_left, n_left);
 176                         if (r) {
 177                                 *cmp = 0;
 178                                 return r;
 179                         }
 180                         p_left = buf_left;
 181                 } else {
 182                         p_left = left->at + (left->len - remain_left);
 183                 }
 184
 185                 if (right->at == NULL) {
 186                         r = read_at(right->root->f,
 187                                     right->pos + (right->len - remain_right),
 188                                     buf_right, n_right);
 189                         if (r) {
 190                                 *cmp = 0;
 191                                 return r;
 192                         }
 193                         p_right = buf_right;
 194                 } else {
 195                         p_right = right->at + (right->len - remain_right);
 196                 }
 197
 198                 r = buf_cmp(p_left, n_left, p_right, n_right,
 199                     ignore_whitespace);
 200                 if (r) {
 201                         *cmp = r;
 202                         return 0;
 203                 }
 204
 205                 remain_left -= n_left;
 206                 remain_right -= n_right;
 207         }
 208
 209         *cmp = 0;
 210         return 0;
 211 }
 212
 213 int
 214 diff_atom_same(bool *same,
 215                const struct diff_atom *left,
 216                const struct diff_atom *right)
 217 {
 218         int cmp;
 219         int r;
 220         if (left->hash != right->hash) {
 221                 *same = false;
 222                 return 0;
 223         }
 224         r = diff_atom_cmp(&cmp, left, right);
 225         if (r) {
 226                 *same = true;
 227                 return r;
 228         }
 229         *same = (cmp == 0);
 230         return 0;
 231 }
 232
 233 static struct diff_chunk *
 234 diff_state_add_solved_chunk(struct diff_state *state,
 235                             const struct diff_chunk *chunk)
 236 {
 237         diff_chunk_arraylist_t *result;
 238         struct diff_chunk *new_chunk;
 239         enum diff_chunk_type last_t;
 240         enum diff_chunk_type new_t;
 241         struct diff_chunk *last;
 242
 243         /* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
 244          * never directly follows a plus chunk. */
 245         result = &state->result->chunks;
 246
 247         last_t = result->len ? diff_chunk_type(&result->head[result->len - 1])
 248                 : CHUNK_EMPTY;
 249         new_t = diff_chunk_type(chunk);
 250
 251         debug("ADD %s chunk #%u:\n", chunk->solved ? "solved" : "UNSOLVED",
 252               result->len);
 253         debug("L\n");
 254         debug_dump_atoms(&state->left, chunk->left_start, chunk->left_count);
 255         debug("R\n");
 256         debug_dump_atoms(&state->right, chunk->right_start, chunk->right_count);
 257
 258         if (result->len) {
 259                 last = &result->head[result->len - 1];
 260                 assert(chunk->left_start
 261                        == last->left_start + last->left_count);
 262                 assert(chunk->right_start
 263                        == last->right_start + last->right_count);
 264         }
 265
 266         if (new_t == last_t) {
 267                 new_chunk = &result->head[result->len - 1];
 268                 new_chunk->left_count += chunk->left_count;
 269                 new_chunk->right_count += chunk->right_count;
 270                 debug("  - added chunk touches previous one of same type, joined:\n");
 271                 debug("L\n");
 272                 debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
 273                 debug("R\n");
 274                 debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
 275         } else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
 276                 enum diff_chunk_type prev_last_t =
 277                         result->len > 1 ?
 278                                 diff_chunk_type(&result->head[result->len - 2])
 279                                 : CHUNK_EMPTY;
 280                 /* If a minus-chunk follows a plus-chunk, place it above the plus-chunk->
 281                  * Is the one before that also a minus? combine. */
 282                 if (prev_last_t == CHUNK_MINUS) {
 283                         new_chunk = &result->head[result->len - 2];
 284                         new_chunk->left_count += chunk->left_count;
 285                         new_chunk->right_count += chunk->right_count;
 286
 287                         debug("  - added minus-chunk follows plus-chunk,"
 288                               " put before that plus-chunk and joined"
 289                               " with preceding minus-chunk:\n");
 290                         debug("L\n");
 291                         debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
 292                         debug("R\n");
 293                         debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
 294                 } else {
 295                         ARRAYLIST_INSERT(new_chunk, *result, result->len - 1);
 296                         if (!new_chunk)
 297                                 return NULL;
 298                         *new_chunk = *chunk;
 299
 300                         /* The new minus chunk indicates to which position on
 301                          * the right it corresponds, even though it doesn't add
 302                          * any lines on the right. By moving above a plus chunk,
 303                          * that position on the right has shifted. */
 304                         last = &result->head[result->len - 1];
 305                         new_chunk->right_start = last->right_start;
 306
 307                         debug("  - added minus-chunk follows plus-chunk,"
 308                               " put before that plus-chunk\n");
 309                 }
 310
 311                 /* That last_t == CHUNK_PLUS indicates to which position on the
 312                  * left it corresponds, even though it doesn't add any lines on
 313                  * the left. By inserting/extending the prev_last_t ==
 314                  * CHUNK_MINUS, that position on the left has shifted. */
 315                 last = &result->head[result->len - 1];
 316                 last->left_start = new_chunk->left_start
 317                         + new_chunk->left_count;
 318
 319         } else {
 320                 ARRAYLIST_ADD(new_chunk, *result);
 321                 if (!new_chunk)
 322                         return NULL;
 323                 *new_chunk = *chunk;
 324         }
 325         return new_chunk;
 326 }
 327
 328 /* Even if a left or right side is empty, diff output may need to know the
 329  * position in that file.
 330  * So left_start or right_start must never be NULL -- pass left_count or
 331  * right_count as zero to indicate staying at that position without consuming
 332  * any lines. */
 333 struct diff_chunk *
 334 diff_state_add_chunk(struct diff_state *state, bool solved,
 335                      struct diff_atom *left_start, unsigned int left_count,
 336                      struct diff_atom *right_start, unsigned int right_count)
 337 {
 338         struct diff_chunk *new_chunk;
 339         struct diff_chunk chunk = {
 340                 .solved = solved,
 341                 .left_start = left_start,
 342                 .left_count = left_count,
 343                 .right_start = right_start,
 344                 .right_count = right_count,
 345         };
 346
 347         /* An unsolved chunk means store as intermediate result for later
 348          * re-iteration.
 349          * If there already are intermediate results, that means even a
 350          * following solved chunk needs to go to intermediate results, so that
 351          * it is later put in the final correct position in solved chunks.
 352          */
 353         if (!solved || state->temp_result.len) {
 354                 /* Append to temp_result */
 355                 debug("ADD %s chunk to temp result:\n",
 356                       chunk.solved ? "solved" : "UNSOLVED");
 357                 debug("L\n");
 358                 debug_dump_atoms(&state->left, left_start, left_count);
 359                 debug("R\n");
 360                 debug_dump_atoms(&state->right, right_start, right_count);
 361                 ARRAYLIST_ADD(new_chunk, state->temp_result);
 362                 if (!new_chunk)
 363                         return NULL;
 364                 *new_chunk = chunk;
 365                 return new_chunk;
 366         }
 367
 368         return diff_state_add_solved_chunk(state, &chunk);
 369 }
 370
 371 static void
 372 diff_data_init_root(struct diff_data *d, FILE *f, const uint8_t *data,
 373     unsigned long long len, int diff_flags)
 374 {
 375         *d = (struct diff_data){
 376                 .f = f,
 377                 .pos = 0,
 378                 .data = data,
 379                 .len = len,
 380                 .root = d,
 381                 .diff_flags = diff_flags,
 382         };
 383 }
 384
 385 void
 386 diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
 387                           struct diff_atom *from_atom, unsigned int atoms_count)
 388 {
 389         struct diff_atom *last_atom;
 390
 391         debug("diff_data %p  parent %p  from_atom %p  atoms_count %u\n",
 392               d, parent, from_atom, atoms_count);
 393         debug("  from_atom ");
 394         debug_dump_atom(parent, NULL, from_atom);
 395
 396         if (atoms_count == 0) {
 397                 *d = (struct diff_data){
 398                         .f = NULL,
 399                         .pos = 0,
 400                         .data = NULL,
 401                         .len = 0,
 402                         .root = parent->root,
 403                         .atoms.head = NULL,
 404                         .atoms.len = atoms_count,
 405                 };
 406
 407                 return;
 408         }
 409
 410         last_atom = from_atom + atoms_count - 1;
 411         *d = (struct diff_data){
 412                 .f = NULL,
 413                 .pos = from_atom->pos,
 414                 .data = from_atom->at,
 415                 .len = (last_atom->pos + last_atom->len) - from_atom->pos,
 416                 .root = parent->root,
 417                 .atoms.head = from_atom,
 418                 .atoms.len = atoms_count,
 419         };
 420
 421         debug("subsection:\n");
 422         debug_dump(d);
 423 }
 424
 425 void
 426 diff_data_free(struct diff_data *diff_data)
 427 {
 428         if (!diff_data)
 429                 return;
 430         if (diff_data->atoms.allocated)
 431                 ARRAYLIST_FREE(diff_data->atoms);
 432 }
 433
 434 int
 435 diff_algo_none(const struct diff_algo_config *algo_config,
 436                struct diff_state *state)
 437 {
 438         debug("\n** %s\n", __func__);
 439         debug("left:\n");
 440         debug_dump(&state->left);
 441         debug("right:\n");
 442         debug_dump(&state->right);
 443         debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
 444                                0);
 445
 446         /* Add a chunk of equal lines, if any */
 447         struct diff_atom *l = state->left.atoms.head;
 448         unsigned int l_len = state->left.atoms.len;
 449         struct diff_atom *r = state->right.atoms.head;
 450         unsigned int r_len = state->right.atoms.len;
 451         unsigned int equal_atoms_start = 0;
 452         unsigned int equal_atoms_end = 0;
 453         unsigned int l_idx = 0;
 454         unsigned int r_idx = 0;
 455
 456         while (equal_atoms_start < l_len
 457                && equal_atoms_start < r_len) {
 458                 int err;
 459                 bool same;
 460                 err = diff_atom_same(&same, &l[equal_atoms_start],
 461                                      &r[equal_atoms_start]);
 462                 if (err)
 463                         return err;
 464                 if (!same)
 465                         break;
 466                 equal_atoms_start++;
 467         }
 468         while (equal_atoms_end < (l_len - equal_atoms_start)
 469                && equal_atoms_end < (r_len - equal_atoms_start)) {
 470                 int err;
 471                 bool same;
 472                 err = diff_atom_same(&same, &l[l_len - 1 - equal_atoms_end],
 473                                    &r[r_len - 1 - equal_atoms_end]);
 474                 if (err)
 475                         return err;
 476                 if (!same)
 477                         break;
 478                 equal_atoms_end++;
 479         }
 480
 481         /* Add a chunk of equal lines at the start */
 482         if (equal_atoms_start) {
 483                 if (!diff_state_add_chunk(state, true,
 484                                           l, equal_atoms_start,
 485                                           r, equal_atoms_start))
 486                         return ENOMEM;
 487                 l_idx += equal_atoms_start;
 488                 r_idx += equal_atoms_start;
 489         }
 490
 491         /* Add a "minus" chunk with all lines from the left. */
 492         if (equal_atoms_start + equal_atoms_end < l_len) {
 493                 unsigned int add_len = l_len - equal_atoms_start - equal_atoms_end;
 494                 if (!diff_state_add_chunk(state, true,
 495                                           &l[l_idx], add_len,
 496                                           &r[r_idx], 0))
 497                         return ENOMEM;
 498                 l_idx += add_len;
 499         }
 500
 501         /* Add a "plus" chunk with all lines from the right. */
 502         if (equal_atoms_start + equal_atoms_end < r_len) {
 503                 unsigned int add_len = r_len - equal_atoms_start - equal_atoms_end;
 504                 if (!diff_state_add_chunk(state, true,
 505                                           &l[l_idx], 0,
 506                                           &r[r_idx], add_len))
 507                         return ENOMEM;
 508                 r_idx += add_len;
 509         }
 510
 511         /* Add a chunk of equal lines at the end */
 512         if (equal_atoms_end) {
 513                 if (!diff_state_add_chunk(state, true,
 514                                           &l[l_idx], equal_atoms_end,
 515                                           &r[r_idx], equal_atoms_end))
 516                         return ENOMEM;
 517         }
 518
 519         return DIFF_RC_OK;
 520 }
 521
 522 static int
 523 diff_run_algo(const struct diff_algo_config *algo_config,
 524               struct diff_state *state)
 525 {
 526         int rc;
 527
 528         if (!algo_config || !algo_config->impl
 529             || !state->recursion_depth_left
 530             || !state->left.atoms.len || !state->right.atoms.len) {
 531                 debug("Fall back to diff_algo_none():%s%s%s\n",
 532                       (!algo_config || !algo_config->impl) ? " no-cfg" : "",
 533                       (!state->recursion_depth_left) ? " max-depth" : "",
 534                       (!state->left.atoms.len || !state->right.atoms.len)?
 535                               " trivial" : "");
 536                 return diff_algo_none(algo_config, state);
 537         }
 538
 539         ARRAYLIST_FREE(state->temp_result);
 540         ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
 541         rc = algo_config->impl(algo_config, state);
 542         switch (rc) {
 543         case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
 544                 debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
 545                       algo_config->fallback_algo);
 546                 rc = diff_run_algo(algo_config->fallback_algo, state);
 547                 goto return_rc;
 548
 549         case DIFF_RC_OK:
 550                 /* continue below */
 551                 break;
 552
 553         default:
 554                 /* some error happened */
 555                 goto return_rc;
 556         }
 557
 558         /* Pick up any diff chunks that are still unsolved and feed to
 559          * inner_algo.  inner_algo will solve unsolved chunks and append to
 560          * result, and subsequent solved chunks on this level are then appended
 561          * to result afterwards. */
 562         int i;
 563         for (i = 0; i < state->temp_result.len; i++) {
 564                 struct diff_chunk *c = &state->temp_result.head[i];
 565                 if (c->solved) {
 566                         diff_state_add_solved_chunk(state, c);
 567                         continue;
 568                 }
 569
 570                 /* c is an unsolved chunk, feed to inner_algo */
 571                 struct diff_state inner_state = {
 572                         .result = state->result,
 573                         .recursion_depth_left = state->recursion_depth_left - 1,
 574                         .kd_buf = state->kd_buf,
 575                         .kd_buf_size = state->kd_buf_size,
 576                 };
 577                 diff_data_init_subsection(&inner_state.left, &state->left,
 578                                           c->left_start, c->left_count);
 579                 diff_data_init_subsection(&inner_state.right, &state->right,
 580                                           c->right_start, c->right_count);
 581
 582                 rc = diff_run_algo(algo_config->inner_algo, &inner_state);
 583                 state->kd_buf = inner_state.kd_buf;
 584                 state->kd_buf_size = inner_state.kd_buf_size;
 585                 if (rc != DIFF_RC_OK)
 586                         goto return_rc;
 587         }
 588
 589         rc = DIFF_RC_OK;
 590 return_rc:
 591         ARRAYLIST_FREE(state->temp_result);
 592         return rc;
 593 }
 594
 595 int
 596 diff_atomize_file(struct diff_data *d,
 597                   const struct diff_config *config,
 598                   FILE *f, const uint8_t *data, off_t len, int diff_flags)
 599 {
 600         if (!config->atomize_func)
 601                 return EINVAL;
 602
 603         diff_data_init_root(d, f, data, len, diff_flags);
 604
 605         return config->atomize_func(config->atomize_func_data, d);
 606
 607 }
 608
 609 struct diff_result *
 610 diff_main(const struct diff_config *config, struct diff_data *left,
 611           struct diff_data *right)
 612 {
 613         struct diff_result *result = malloc(sizeof(struct diff_result));
 614         if (!result)
 615                 return NULL;
 616
 617         *result = (struct diff_result){};
 618         result->left = left;
 619         result->right = right;
 620
 621         struct diff_state state = {
 622                 .result = result,
 623                 .recursion_depth_left = config->max_recursion_depth ?
 624                     config->max_recursion_depth : UINT_MAX,
 625                 .kd_buf = NULL,
 626                 .kd_buf_size = 0,
 627         };
 628         diff_data_init_subsection(&state.left, left,
 629                                   left->atoms.head,
 630                                   left->atoms.len);
 631         diff_data_init_subsection(&state.right, right,
 632                                   right->atoms.head,
 633                                   right->atoms.len);
 634
 635         result->rc = diff_run_algo(config->algo, &state);
 636         free(state.kd_buf);
 637
 638         return result;
 639 }
 640
 641 void
 642 diff_result_free(struct diff_result *result)
 643 {
 644         if (!result)
 645                 return;
 646         ARRAYLIST_FREE(result->chunks);
 647         free(result);
 648 }
 649
 650 int
 651 diff_result_contains_printable_chunks(struct diff_result *result)
 652 {
 653         struct diff_chunk *c;
 654         enum diff_chunk_type t;
 655         int i;
 656
 657         for (i = 0; i < result->chunks.len; i++) {
 658                 c = &result->chunks.head[i];
 659                 t = diff_chunk_type(c);
 660                 if (t == CHUNK_MINUS || t == CHUNK_PLUS)
 661                         return 1;
 662         }
 663
 664         return 0;
 665 }