lib/diff_output_unidiff.c

   1 /* Produce a unidiff output from a diff_result. */
   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 #include <errno.h>
  19 #include <stdbool.h>
  20 #include <stdint.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <assert.h>
  25
  26 #include <arraylist.h>
  27 #include <diff_main.h>
  28 #include <diff_output.h>
  29
  30 #include "diff_internal.h"
  31 #include "diff_debug.h"
  32
  33 bool
  34 diff_chunk_context_empty(const struct diff_chunk_context *cc)
  35 {
  36         return diff_range_empty(&cc->chunk);
  37 }
  38
  39 int
  40 diff_chunk_get_left_start(const struct diff_chunk *c,
  41     const struct diff_result *r, int context_lines)
  42 {
  43         int left_start = diff_atom_root_idx(r->left, c->left_start);
  44         return MAX(0, left_start - context_lines);
  45 }
  46
  47 int
  48 diff_chunk_get_left_end(const struct diff_chunk *c,
  49     const struct diff_result *r, int context_lines)
  50 {
  51         int left_start = diff_chunk_get_left_start(c, r, 0);
  52         return MIN(r->left->atoms.len,
  53             left_start + c->left_count + context_lines);
  54 }
  55
  56 int
  57 diff_chunk_get_right_start(const struct diff_chunk *c,
  58     const struct diff_result *r, int context_lines)
  59 {
  60         int right_start = diff_atom_root_idx(r->right, c->right_start);
  61         return MAX(0, right_start - context_lines);
  62 }
  63
  64 int
  65 diff_chunk_get_right_end(const struct diff_chunk *c,
  66     const struct diff_result *r, int context_lines)
  67 {
  68         int right_start = diff_chunk_get_right_start(c, r, 0);
  69         return MIN(r->right->atoms.len,
  70             right_start + c->right_count + context_lines);
  71 }
  72
  73 struct diff_chunk *
  74 diff_chunk_get(const struct diff_result *r, int chunk_idx)
  75 {
  76         return &r->chunks.head[chunk_idx];
  77 }
  78
  79 int
  80 diff_chunk_get_left_count(struct diff_chunk *c)
  81 {
  82         return c->left_count;
  83 }
  84
  85 int
  86 diff_chunk_get_right_count(struct diff_chunk *c)
  87 {
  88         return c->right_count;
  89 }
  90
  91 void
  92 diff_chunk_context_get(struct diff_chunk_context *cc, const struct diff_result *r,
  93                   int chunk_idx, int context_lines)
  94 {
  95         const struct diff_chunk *c = &r->chunks.head[chunk_idx];
  96         int left_start = diff_chunk_get_left_start(c, r, context_lines);
  97         int left_end = diff_chunk_get_left_end(c, r, context_lines);
  98         int right_start = diff_chunk_get_right_start(c, r, context_lines);
  99         int right_end = diff_chunk_get_right_end(c, r,  context_lines);
 100
 101         *cc = (struct diff_chunk_context){
 102                 .chunk = {
 103                         .start = chunk_idx,
 104                         .end = chunk_idx + 1,
 105                 },
 106                 .left = {
 107                         .start = left_start,
 108                         .end = left_end,
 109                 },
 110                 .right = {
 111                         .start = right_start,
 112                         .end = right_end,
 113                 },
 114         };
 115 }
 116
 117 bool
 118 diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
 119                           const struct diff_chunk_context *other)
 120 {
 121         return diff_ranges_touch(&cc->chunk, &other->chunk)
 122                 || diff_ranges_touch(&cc->left, &other->left)
 123                 || diff_ranges_touch(&cc->right, &other->right);
 124 }
 125
 126 void
 127 diff_chunk_contexts_merge(struct diff_chunk_context *cc,
 128                           const struct diff_chunk_context *other)
 129 {
 130         diff_ranges_merge(&cc->chunk, &other->chunk);
 131         diff_ranges_merge(&cc->left, &other->left);
 132         diff_ranges_merge(&cc->right, &other->right);
 133 }
 134
 135 void
 136 diff_chunk_context_load_change(struct diff_chunk_context *cc,
 137                                int *nchunks_used,
 138                                struct diff_result *result,
 139                                int start_chunk_idx,
 140                                int context_lines)
 141 {
 142         int i;
 143         int seen_minus = 0, seen_plus = 0;
 144
 145         if (nchunks_used)
 146                 *nchunks_used = 0;
 147
 148         for (i = start_chunk_idx; i < result->chunks.len; i++) {
 149                 struct diff_chunk *chunk = &result->chunks.head[i];
 150                 enum diff_chunk_type t = diff_chunk_type(chunk);
 151                 struct diff_chunk_context next;
 152
 153                 if (t != CHUNK_MINUS && t != CHUNK_PLUS) {
 154                         if (nchunks_used)
 155                                 (*nchunks_used)++;
 156                         if (seen_minus || seen_plus)
 157                                 break;
 158                         else
 159                                 continue;
 160                 } else if (t == CHUNK_MINUS)
 161                         seen_minus = 1;
 162                 else if (t == CHUNK_PLUS)
 163                         seen_plus = 1;
 164
 165                 if (diff_chunk_context_empty(cc)) {
 166                         /* Note down the start point, any number of subsequent
 167                          * chunks may be joined up to this chunk by being
 168                          * directly adjacent. */
 169                         diff_chunk_context_get(cc, result, i, context_lines);
 170                         if (nchunks_used)
 171                                 (*nchunks_used)++;
 172                         continue;
 173                 }
 174
 175                 /* There already is a previous chunk noted down for being
 176                  * printed. Does it join up with this one? */
 177                 diff_chunk_context_get(&next, result, i, context_lines);
 178
 179                 if (diff_chunk_contexts_touch(cc, &next)) {
 180                         /* This next context touches or overlaps the previous
 181                          * one, join. */
 182                         diff_chunk_contexts_merge(cc, &next);
 183                         if (nchunks_used)
 184                                 (*nchunks_used)++;
 185                         continue;
 186                 } else
 187                         break;
 188         }
 189 }
 190
 191 struct diff_output_unidiff_state {
 192         bool header_printed;
 193         char prototype[DIFF_FUNCTION_CONTEXT_SIZE];
 194         int last_prototype_idx;
 195 };
 196
 197 struct diff_output_unidiff_state *
 198 diff_output_unidiff_state_alloc(void)
 199 {
 200         struct diff_output_unidiff_state *state;
 201
 202         state = calloc(1, sizeof(struct diff_output_unidiff_state));
 203         if (state != NULL)
 204                 diff_output_unidiff_state_reset(state);
 205         return state;
 206 }
 207
 208 void
 209 diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state)
 210 {
 211         state->header_printed = false;
 212         memset(state->prototype, 0, sizeof(state->prototype));
 213         state->last_prototype_idx = 0;
 214 }
 215
 216 void
 217 diff_output_unidiff_state_free(struct diff_output_unidiff_state *state)
 218 {
 219         free(state);
 220 }
 221
 222 static int
 223 output_unidiff_chunk(struct diff_output_info *outinfo, FILE *dest,
 224                      struct diff_output_unidiff_state *state,
 225                      const struct diff_input_info *info,
 226                      const struct diff_result *result,
 227                      bool print_header, bool show_function_prototypes,
 228                      const struct diff_chunk_context *cc)
 229 {
 230         int rc, left_start, left_len, right_start, right_len;
 231         off_t outoff = 0, *offp;
 232
 233         if (diff_range_empty(&cc->left) && diff_range_empty(&cc->right))
 234                 return DIFF_RC_OK;
 235
 236         if (outinfo && outinfo->line_offsets.len > 0) {
 237                 unsigned int idx = outinfo->line_offsets.len - 1;
 238                 outoff = outinfo->line_offsets.head[idx];
 239         }
 240
 241         if (print_header && !(state->header_printed)) {
 242                 rc = fprintf(dest, "--- %s\n",
 243                     diff_output_get_label_left(info));
 244                 if (rc < 0)
 245                         return errno;
 246                 if (outinfo) {
 247                         ARRAYLIST_ADD(offp, outinfo->line_offsets);
 248                         if (offp == NULL)
 249                                 return ENOMEM;
 250                         outoff += rc;
 251                         *offp = outoff;
 252
 253                 }
 254                 rc = fprintf(dest, "+++ %s\n",
 255                     diff_output_get_label_right(info));
 256                 if (rc < 0)
 257                         return errno;
 258                 if (outinfo) {
 259                         ARRAYLIST_ADD(offp, outinfo->line_offsets);
 260                         if (offp == NULL)
 261                                 return ENOMEM;
 262                         outoff += rc;
 263                         *offp = outoff;
 264
 265                 }
 266                 state->header_printed = true;
 267         }
 268
 269         left_len = cc->left.end - cc->left.start;
 270         if (result->left->atoms.len == 0)
 271                 left_start = 0;
 272         else if (left_len == 0 && cc->left.start > 0)
 273                 left_start = cc->left.start;
 274         else
 275                 left_start = cc->left.start + 1;
 276
 277         right_len = cc->right.end - cc->right.start;
 278         if (result->right->atoms.len == 0)
 279                 right_start = 0;
 280         else if (right_len == 0 && cc->right.start > 0)
 281                 right_start = cc->right.start;
 282         else
 283                 right_start = cc->right.start + 1;
 284
 285         if (show_function_prototypes) {
 286                 rc = diff_output_match_function_prototype(state->prototype,
 287                     sizeof(state->prototype), &state->last_prototype_idx,
 288                     result, cc);
 289                 if (rc)
 290                         return rc;
 291         }
 292
 293         if (left_len == 1 && right_len == 1) {
 294                 rc = fprintf(dest, "@@ -%d +%d @@%s%s\n",
 295                         left_start, right_start,
 296                         state->prototype[0] ? " " : "",
 297                         state->prototype[0] ? state->prototype : "");
 298         } else if (left_len == 1 && right_len != 1) {
 299                 rc = fprintf(dest, "@@ -%d +%d,%d @@%s%s\n",
 300                         left_start, right_start, right_len,
 301                         state->prototype[0] ? " " : "",
 302                         state->prototype[0] ? state->prototype : "");
 303         } else if (left_len != 1 && right_len == 1) {
 304                 rc = fprintf(dest, "@@ -%d,%d +%d @@%s%s\n",
 305                         left_start, left_len, right_start,
 306                         state->prototype[0] ? " " : "",
 307                         state->prototype[0] ? state->prototype : "");
 308         } else {
 309                 rc = fprintf(dest, "@@ -%d,%d +%d,%d @@%s%s\n",
 310                         left_start, left_len, right_start, right_len,
 311                         state->prototype[0] ? " " : "",
 312                         state->prototype[0] ? state->prototype : "");
 313         }
 314         if (rc < 0)
 315                 return errno;
 316         if (outinfo) {
 317                 ARRAYLIST_ADD(offp, outinfo->line_offsets);
 318                 if (offp == NULL)
 319                         return ENOMEM;
 320                 outoff += rc;
 321                 *offp = outoff;
 322
 323         }
 324
 325         /* Got the absolute line numbers where to start printing, and the index
 326          * of the interesting (non-context) chunk.
 327          * To print context lines above the interesting chunk, nipping on the
 328          * previous chunk index may be necessary.
 329          * It is guaranteed to be only context lines where left == right, so it
 330          * suffices to look on the left. */
 331         const struct diff_chunk *first_chunk;
 332         int chunk_start_line;
 333         first_chunk = &result->chunks.head[cc->chunk.start];
 334         chunk_start_line = diff_atom_root_idx(result->left,
 335                                               first_chunk->left_start);
 336         if (cc->left.start < chunk_start_line) {
 337                 rc = diff_output_lines(outinfo, dest, " ",
 338                                   &result->left->atoms.head[cc->left.start],
 339                                   chunk_start_line - cc->left.start);
 340                 if (rc)
 341                         return rc;
 342         }
 343
 344         /* Now write out all the joined chunks and contexts between them */
 345         int c_idx;
 346         for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
 347                 const struct diff_chunk *c = &result->chunks.head[c_idx];
 348
 349                 if (c->left_count && c->right_count)
 350                         rc = diff_output_lines(outinfo, dest,
 351                                           c->solved ? " " : "?",
 352                                           c->left_start, c->left_count);
 353                 else if (c->left_count && !c->right_count)
 354                         rc = diff_output_lines(outinfo, dest,
 355                                           c->solved ? "-" : "?",
 356                                           c->left_start, c->left_count);
 357                 else if (c->right_count && !c->left_count)
 358                         rc = diff_output_lines(outinfo, dest,
 359                                           c->solved ? "+" : "?",
 360                                           c->right_start, c->right_count);
 361                 if (rc)
 362                         return rc;
 363
 364                 if (cc->chunk.end == result->chunks.len) {
 365                         rc = diff_output_trailing_newline_msg(outinfo, dest, c);
 366                         if (rc != DIFF_RC_OK)
 367                                 return rc;
 368                 }
 369         }
 370
 371         /* Trailing context? */
 372         const struct diff_chunk *last_chunk;
 373         int chunk_end_line;
 374         last_chunk = &result->chunks.head[cc->chunk.end - 1];
 375         chunk_end_line = diff_atom_root_idx(result->left,
 376                                             last_chunk->left_start
 377                                             + last_chunk->left_count);
 378         if (cc->left.end > chunk_end_line) {
 379                 rc = diff_output_lines(outinfo, dest, " ",
 380                                   &result->left->atoms.head[chunk_end_line],
 381                                   cc->left.end - chunk_end_line);
 382                 if (rc)
 383                         return rc;
 384         }
 385
 386         return DIFF_RC_OK;
 387 }
 388
 389 int
 390 diff_output_unidiff_chunk(struct diff_output_info **output_info, FILE *dest,
 391                           struct diff_output_unidiff_state *state,
 392                           const struct diff_input_info *info,
 393                           const struct diff_result *result,
 394                           const struct diff_chunk_context *cc)
 395 {
 396         struct diff_output_info *outinfo = NULL;
 397         int flags = (result->left->root->diff_flags |
 398             result->right->root->diff_flags);
 399         bool show_function_prototypes = (flags & DIFF_FLAG_SHOW_PROTOTYPES);
 400
 401         if (output_info) {
 402                 *output_info = diff_output_info_alloc();
 403                 if (*output_info == NULL)
 404                         return ENOMEM;
 405                 outinfo = *output_info;
 406         }
 407
 408         return output_unidiff_chunk(outinfo, dest, state, info,
 409             result, false, show_function_prototypes, cc);
 410 }
 411
 412 int
 413 diff_output_unidiff(struct diff_output_info **output_info,
 414                     FILE *dest, const struct diff_input_info *info,
 415                     const struct diff_result *result,
 416                     unsigned int context_lines)
 417 {
 418         struct diff_output_unidiff_state *state;
 419         struct diff_chunk_context cc = {};
 420         struct diff_output_info *outinfo = NULL;
 421         int atomizer_flags = (result->left->atomizer_flags|
 422             result->right->atomizer_flags);
 423         int flags = (result->left->root->diff_flags |
 424             result->right->root->diff_flags);
 425         bool show_function_prototypes = (flags & DIFF_FLAG_SHOW_PROTOTYPES);
 426         bool force_text = (flags & DIFF_FLAG_FORCE_TEXT_DATA);
 427         bool have_binary = (atomizer_flags & DIFF_ATOMIZER_FOUND_BINARY_DATA);
 428         int i;
 429
 430         if (!result)
 431                 return EINVAL;
 432         if (result->rc != DIFF_RC_OK)
 433                 return result->rc;
 434
 435         if (output_info) {
 436                 *output_info = diff_output_info_alloc();
 437                 if (*output_info == NULL)
 438                         return ENOMEM;
 439                 outinfo = *output_info;
 440         }
 441
 442         if (have_binary && !force_text) {
 443                 for (i = 0; i < result->chunks.len; i++) {
 444                         struct diff_chunk *c = &result->chunks.head[i];
 445                         enum diff_chunk_type t = diff_chunk_type(c);
 446
 447                         if (t != CHUNK_MINUS && t != CHUNK_PLUS)
 448                                 continue;
 449
 450                         fprintf(dest, "Binary files %s and %s differ\n",
 451                             diff_output_get_label_left(info),
 452                             diff_output_get_label_right(info));
 453                         break;
 454                 }
 455
 456                 return DIFF_RC_OK;
 457         }
 458
 459         state = diff_output_unidiff_state_alloc();
 460         if (state == NULL) {
 461                 if (output_info) {
 462                         diff_output_info_free(*output_info);
 463                         *output_info = NULL;
 464                 }
 465                 return ENOMEM;
 466         }
 467
 468 #if DEBUG
 469         unsigned int check_left_pos, check_right_pos;
 470         check_left_pos = 0;
 471         check_right_pos = 0;
 472         for (i = 0; i < result->chunks.len; i++) {
 473                 struct diff_chunk *c = &result->chunks.head[i];
 474                 enum diff_chunk_type t = diff_chunk_type(c);
 475
 476                 debug("[%d] %s lines L%d R%d @L %d @R %d\n",
 477                       i, (t == CHUNK_MINUS ? "minus" :
 478                           (t == CHUNK_PLUS ? "plus" :
 479                            (t == CHUNK_SAME ? "same" : "?"))),
 480                       c->left_count,
 481                       c->right_count,
 482                       c->left_start ? diff_atom_root_idx(result->left, c->left_start) : -1,
 483                       c->right_start ? diff_atom_root_idx(result->right, c->right_start) : -1);
 484                 assert(check_left_pos == diff_atom_root_idx(result->left, c->left_start));
 485                 assert(check_right_pos == diff_atom_root_idx(result->right, c->right_start));
 486                 check_left_pos += c->left_count;
 487                 check_right_pos += c->right_count;
 488
 489         }
 490         assert(check_left_pos == result->left->atoms.len);
 491         assert(check_right_pos == result->right->atoms.len);
 492 #endif
 493
 494         for (i = 0; i < result->chunks.len; i++) {
 495                 struct diff_chunk *c = &result->chunks.head[i];
 496                 enum diff_chunk_type t = diff_chunk_type(c);
 497                 struct diff_chunk_context next;
 498
 499                 if (t != CHUNK_MINUS && t != CHUNK_PLUS)
 500                         continue;
 501
 502                 if (diff_chunk_context_empty(&cc)) {
 503                         /* These are the first lines being printed.
 504                          * Note down the start point, any number of subsequent
 505                          * chunks may be joined up to this unidiff chunk by
 506                          * context lines or by being directly adjacent. */
 507                         diff_chunk_context_get(&cc, result, i, context_lines);
 508                         debug("new chunk to be printed:"
 509                               " chunk %d-%d left %d-%d right %d-%d\n",
 510                               cc.chunk.start, cc.chunk.end,
 511                               cc.left.start, cc.left.end,
 512                               cc.right.start, cc.right.end);
 513                         continue;
 514                 }
 515
 516                 /* There already is a previous chunk noted down for being
 517                  * printed. Does it join up with this one? */
 518                 diff_chunk_context_get(&next, result, i, context_lines);
 519                 debug("new chunk to be printed:"
 520                       " chunk %d-%d left %d-%d right %d-%d\n",
 521                       next.chunk.start, next.chunk.end,
 522                       next.left.start, next.left.end,
 523                       next.right.start, next.right.end);
 524
 525                 if (diff_chunk_contexts_touch(&cc, &next)) {
 526                         /* This next context touches or overlaps the previous
 527                          * one, join. */
 528                         diff_chunk_contexts_merge(&cc, &next);
 529                         debug("new chunk to be printed touches previous chunk,"
 530                               " now: left %d-%d right %d-%d\n",
 531                               cc.left.start, cc.left.end,
 532                               cc.right.start, cc.right.end);
 533                         continue;
 534                 }
 535
 536                 /* No touching, so the previous context is complete with a gap
 537                  * between it and this next one. Print the previous one and
 538                  * start fresh here. */
 539                 debug("new chunk to be printed does not touch previous chunk;"
 540                       " print left %d-%d right %d-%d\n",
 541                       cc.left.start, cc.left.end, cc.right.start, cc.right.end);
 542                 output_unidiff_chunk(outinfo, dest, state, info, result,
 543                     true, show_function_prototypes, &cc);
 544                 cc = next;
 545                 debug("new unprinted chunk is left %d-%d right %d-%d\n",
 546                       cc.left.start, cc.left.end, cc.right.start, cc.right.end);
 547         }
 548
 549         if (!diff_chunk_context_empty(&cc))
 550                 output_unidiff_chunk(outinfo, dest, state, info, result,
 551                     true, show_function_prototypes, &cc);
 552         diff_output_unidiff_state_free(state);
 553         return DIFF_RC_OK;
 554 }