lib/blame.c

   1 /*
   2  * Copyright (c) 2018, 2019, 2020 Stefan Sperling <stsp@openbsd.org>
   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 <sys/mman.h>
  19 #include <sys/stat.h>
  20
  21 #include <errno.h>
  22 #include <string.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <time.h>
  26 #include <limits.h>
  27 #include <zlib.h>
  28
  29 #include "got_compat.h"
  30
  31 #include "got_error.h"
  32 #include "got_object.h"
  33 #include "got_cancel.h"
  34 #include "got_commit_graph.h"
  35 #include "got_opentemp.h"
  36 #include "got_diff.h"
  37 #include "got_blame.h"
  38
  39 #include "got_lib_inflate.h"
  40 #include "got_lib_delta.h"
  41 #include "got_lib_object.h"
  42 #include "got_lib_diff.h"
  43
  44 #ifndef MAX
  45 #define MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b))
  46 #endif
  47
  48 struct got_blame_line {
  49         int annotated;
  50         struct got_object_id id;
  51 };
  52
  53 struct got_blame {
  54         struct diff_config *cfg;
  55         int nlines;     /* number of lines in file being blamed */
  56         int nannotated; /* number of lines already annotated */
  57         struct got_blame_line *lines; /* one per line */
  58         int ncommits;
  59
  60         /*
  61          * These change with every traversed commit. After diffing
  62          * commits N:N-1, in preparation for diffing commits N-1:N-2,
  63          * data for commit N is retained and flipped into data for N-1.
  64          *
  65          */
  66         FILE *f1; /* older version from commit N-1. */
  67         FILE *f2; /* newer version from commit N. */
  68         int fd;
  69         unsigned char *map1;
  70         unsigned char *map2;
  71         off_t size1;
  72         off_t size2;
  73         int nlines1;
  74         int nlines2;
  75         off_t *line_offsets1;
  76         off_t *line_offsets2;
  77
  78         /*
  79          * Map line numbers of an older version of the file to valid line
  80          * numbers in the version of the file being blamed. This map is
  81          * updated with each commit we traverse throughout the file's history.
  82          * Lines mapped to -1 do not correspond to any line in the version
  83          * being blamed.
  84          */
  85         int *linemap1;
  86         int *linemap2;
  87
  88         struct diff_data *data1;
  89         struct diff_data *data2;
  90 };
  91
  92 static const struct got_error *
  93 annotate_line(struct got_blame *blame, int lineno,
  94     struct got_commit_object *commit, struct got_object_id *id,
  95     got_blame_cb cb, void *arg)
  96 {
  97         const struct got_error *err = NULL;
  98         struct got_blame_line *line;
  99
 100         if (lineno < 0 || lineno >= blame->nlines)
 101                 return NULL;
 102
 103         line = &blame->lines[lineno];
 104         if (line->annotated)
 105                 return NULL;
 106
 107         memcpy(&line->id, id, sizeof(line->id));
 108         line->annotated = 1;
 109         blame->nannotated++;
 110         if (cb)
 111                 err = cb(arg, blame->nlines, lineno + 1, commit, id);
 112         return err;
 113 }
 114
 115 static const struct got_error *
 116 blame_changes(struct got_blame *blame, struct diff_result *diff_result,
 117     struct got_commit_object *commit, struct got_object_id *commit_id,
 118     got_blame_cb cb, void *arg)
 119 {
 120         const struct got_error *err = NULL;
 121         int i;
 122         int idx1 = 0, idx2 = 0;
 123
 124         for (i = 0; i < diff_result->chunks.len &&
 125             blame->nannotated < blame->nlines; i++) {
 126                 struct diff_chunk *c = diff_chunk_get(diff_result, i);
 127                 unsigned int left_count, right_count;
 128                 int j;
 129
 130                 /*
 131                  * We do not need to worry about idx1/idx2 growing out
 132                  * of bounds because the diff implementation ensures
 133                  * that chunk ranges never exceed the number of lines
 134                  * in the left/right input files.
 135                  */
 136                 left_count = diff_chunk_get_left_count(c);
 137                 right_count = diff_chunk_get_right_count(c);
 138
 139                 if (left_count == right_count) {
 140                         for (j = 0; j < left_count; j++) {
 141                                 blame->linemap1[idx1++] =
 142                                     blame->linemap2[idx2++];
 143                         }
 144                         continue;
 145                 }
 146
 147                 if (right_count == 0) {
 148                         for (j = 0; j < left_count; j++) {
 149                                 blame->linemap1[idx1++] = -1;
 150                         }
 151                         continue;
 152                 }
 153
 154                 for (j = 0; j < right_count; j++) {
 155                         int ln = blame->linemap2[idx2++];
 156                         err = annotate_line(blame, ln, commit, commit_id,
 157                             cb, arg);
 158                         if (err)
 159                                 return err;
 160                         if (blame->nlines == blame->nannotated)
 161                                 break;
 162                 }
 163         }
 164
 165         return NULL;
 166 }
 167
 168 static const struct got_error *
 169 blame_prepare_file(FILE *f, unsigned char **p, off_t *size,
 170     int *nlines, off_t **line_offsets, struct diff_data *diff_data,
 171     const struct diff_config *cfg, struct got_blob_object *blob)
 172 {
 173         const struct got_error *err = NULL;
 174         int diff_flags = 0, rc;
 175
 176         err = got_object_blob_dump_to_file(size, nlines, line_offsets,
 177             f, blob);
 178         if (err)
 179                 return err;
 180
 181 #ifndef GOT_DIFF_NO_MMAP
 182         *p = mmap(NULL, *size, PROT_READ, MAP_PRIVATE, fileno(f), 0);
 183         if (*p == MAP_FAILED)
 184 #endif
 185                 *p = NULL; /* fall back on file I/O */
 186
 187         /* Allow blaming lines in binary files even though it's useless. */
 188         diff_flags |= DIFF_FLAG_FORCE_TEXT_DATA;
 189
 190         rc = diff_atomize_file(diff_data, cfg, f, *p, *size, diff_flags);
 191         if (rc)
 192                 return got_error_set_errno(rc, "diff_atomize_file");
 193
 194         return NULL;
 195 }
 196
 197 static const struct got_error *
 198 blame_commit(struct got_blame *blame, struct got_object_id *id,
 199     const char *path, struct got_repository *repo,
 200     got_blame_cb cb, void *arg)
 201 {
 202         const struct got_error *err = NULL;
 203         struct got_commit_object *commit = NULL, *pcommit = NULL;
 204         struct got_object_qid *pid = NULL;
 205         struct got_object_id *pblob_id = NULL;
 206         struct got_blob_object *pblob = NULL;
 207         struct diff_result *diff_result = NULL;
 208
 209         err = got_object_open_as_commit(&commit, repo, id);
 210         if (err)
 211                 return err;
 212
 213         pid = STAILQ_FIRST(got_object_commit_get_parent_ids(commit));
 214         if (pid == NULL) {
 215                 got_object_commit_close(commit);
 216                 return NULL;
 217         }
 218
 219         err = got_object_open_as_commit(&pcommit, repo, &pid->id);
 220         if (err)
 221                 goto done;
 222
 223         err = got_object_id_by_path(&pblob_id, repo, pcommit, path);
 224         if (err) {
 225                 if (err->code == GOT_ERR_NO_TREE_ENTRY)
 226                         err = NULL;
 227                 goto done;
 228         }
 229
 230         err = got_object_open_as_blob(&pblob, repo, pblob_id, 8192, blame->fd);
 231         if (err)
 232                 goto done;
 233
 234         err = blame_prepare_file(blame->f1, &blame->map1, &blame->size1,
 235             &blame->nlines1, &blame->line_offsets1, blame->data1,
 236             blame->cfg, pblob);
 237         if (err)
 238                 goto done;
 239
 240         diff_result = diff_main(blame->cfg, blame->data1, blame->data2);
 241         if (diff_result == NULL) {
 242                 err = got_error_set_errno(ENOMEM, "malloc");
 243                 goto done;
 244         }
 245         if (diff_result->rc != DIFF_RC_OK) {
 246                 err = got_error_set_errno(diff_result->rc, "diff");
 247                 goto done;
 248         }
 249         if (diff_result->chunks.len > 0) {
 250                 if (blame->nlines1 > 0) {
 251                         blame->linemap1 = calloc(blame->nlines1,
 252                             sizeof(*blame->linemap1));
 253                         if (blame->linemap1 == NULL) {
 254                                 err = got_error_from_errno("malloc");
 255                                 goto done;
 256                         }
 257                 }
 258                 err = blame_changes(blame, diff_result, commit, id, cb, arg);
 259                 if (err)
 260                         goto done;
 261         } else if (cb)
 262                 err = cb(arg, blame->nlines, -1, commit, id);
 263 done:
 264         if (diff_result)
 265                 diff_result_free(diff_result);
 266         if (commit)
 267                 got_object_commit_close(commit);
 268         if (pcommit)
 269                 got_object_commit_close(pcommit);
 270         free(pblob_id);
 271         if (pblob)
 272                 got_object_blob_close(pblob);
 273         return err;
 274 }
 275
 276 static const struct got_error *
 277 blame_close(struct got_blame *blame)
 278 {
 279         const struct got_error *err = NULL;
 280
 281         diff_data_free(blame->data1);
 282         free(blame->data1);
 283         diff_data_free(blame->data2);
 284         free(blame->data2);
 285         if (blame->map1) {
 286                 if (munmap(blame->map1, blame->size1) == -1 && err == NULL)
 287                         err = got_error_from_errno("munmap");
 288         }
 289         if (blame->map2) {
 290                 if (munmap(blame->map2, blame->size2) == -1 && err == NULL)
 291                         err = got_error_from_errno("munmap");
 292         }
 293         free(blame->lines);
 294         free(blame->line_offsets1);
 295         free(blame->line_offsets2);
 296         free(blame->linemap1);
 297         free(blame->linemap2);
 298         free(blame->cfg);
 299         free(blame);
 300         return err;
 301 }
 302
 303 static int
 304 atomize_file(struct diff_data *d, FILE *f, off_t filesize, int nlines,
 305     off_t *line_offsets)
 306 {
 307         int i, rc = DIFF_RC_OK;
 308         int embedded_nul = 0;
 309
 310         ARRAYLIST_INIT(d->atoms, nlines);
 311
 312         for (i = 0; i < nlines; i++) {
 313                 struct diff_atom *atom;
 314                 off_t len, pos = line_offsets[i];
 315                 unsigned int hash = 0;
 316                 int j;
 317
 318                 ARRAYLIST_ADD(atom, d->atoms);
 319                 if (atom == NULL) {
 320                         rc = errno;
 321                         break;
 322                 }
 323
 324                 if (i < nlines - 1)
 325                         len = line_offsets[i + 1] - pos;
 326                 else
 327                         len = filesize - pos;
 328
 329                 if (fseeko(f, pos, SEEK_SET) == -1) {
 330                         rc = errno;
 331                         break;
 332                 }
 333                 for (j = 0; j < len; j++) {
 334                         int c = fgetc(f);
 335                         if (c == EOF) {
 336                                 if (feof(f))
 337                                         rc = EIO; /* unexpected EOF */
 338                                 else
 339                                         rc = errno;
 340                                 goto done;
 341                         }
 342
 343                         hash = diff_atom_hash_update(hash, (unsigned char)c);
 344
 345                         if (c == '\0')
 346                                 embedded_nul = 1;
 347
 348                 }
 349                 *atom = (struct diff_atom){
 350                         .root = d,
 351                         .pos = pos,
 352                         .at = NULL,     /* atom data is not memory-mapped */
 353                         .len = len,
 354                         .hash = hash,
 355                 };
 356         }
 357
 358         /* File are considered binary if they contain embedded '\0' bytes. */
 359         if (embedded_nul)
 360                 d->atomizer_flags |= DIFF_ATOMIZER_FOUND_BINARY_DATA;
 361 done:
 362         if (rc)
 363                 ARRAYLIST_FREE(d->atoms);
 364
 365         return rc;
 366 }
 367
 368 static int
 369 atomize_file_mmap(struct diff_data *d, unsigned char *p,
 370     off_t filesize, int nlines, off_t *line_offsets)
 371 {
 372         int i, rc = DIFF_RC_OK;
 373         int embedded_nul = 0;
 374
 375         ARRAYLIST_INIT(d->atoms, nlines);
 376
 377         for (i = 0; i < nlines; i++) {
 378                 struct diff_atom *atom;
 379                 off_t len, pos = line_offsets[i];
 380                 unsigned int hash = 0;
 381                 int j;
 382
 383                 ARRAYLIST_ADD(atom, d->atoms);
 384                 if (atom == NULL) {
 385                         rc = errno;
 386                         break;
 387                 }
 388
 389                 if (i < nlines - 1)
 390                         len = line_offsets[i + 1] - pos;
 391                 else
 392                         len = filesize - pos;
 393
 394                 for (j = 0; j < len; j++)
 395                         hash = diff_atom_hash_update(hash, p[pos + j]);
 396
 397                 if (!embedded_nul && memchr(&p[pos], '\0', len) != NULL)
 398                         embedded_nul = 1;
 399
 400                 *atom = (struct diff_atom){
 401                         .root = d,
 402                         .pos = pos,
 403                         .at = &p[pos],
 404                         .len = len,
 405                         .hash = hash,
 406                 };
 407         }
 408
 409         /* File are considered binary if they contain embedded '\0' bytes. */
 410         if (embedded_nul)
 411                 d->atomizer_flags |= DIFF_ATOMIZER_FOUND_BINARY_DATA;
 412
 413         if (rc)
 414                 ARRAYLIST_FREE(d->atoms);
 415
 416         return rc;
 417 }
 418
 419 /* Implements diff_atomize_func_t */
 420 static int
 421 blame_atomize_file(void *arg, struct diff_data *d)
 422 {
 423         struct got_blame *blame = arg;
 424
 425         if (d->f == blame->f1) {
 426                 if (blame->map1)
 427                         return atomize_file_mmap(d, blame->map1,
 428                             blame->size1, blame->nlines1,
 429                             blame->line_offsets1);
 430                 else
 431                         return atomize_file(d, blame->f1, blame->size1,
 432                             blame->nlines1, blame->line_offsets1);
 433         } else if (d->f == blame->f2) {
 434                 if (d->atoms.len > 0) {
 435                         /* Re-use data from previous commit. */
 436                         return DIFF_RC_OK;
 437                 }
 438                 if (blame->map2)
 439                         return atomize_file_mmap(d, blame->map2,
 440                             blame->size2, blame->nlines2,
 441                             blame->line_offsets2);
 442                 else
 443                         return atomize_file(d, blame->f2, blame->size2,
 444                             blame->nlines2, blame->line_offsets2);
 445         }
 446
 447         return DIFF_RC_OK;
 448 }
 449
 450 static const struct got_error *
 451 flip_files(struct got_blame *blame)
 452 {
 453         const struct got_error *err = NULL;
 454         struct diff_data *d;
 455         FILE *tmp;
 456
 457         free(blame->line_offsets2);
 458         blame->line_offsets2 = blame->line_offsets1;
 459         blame->line_offsets1 = NULL;
 460
 461         free(blame->linemap2);
 462         blame->linemap2 = blame->linemap1;
 463         blame->linemap1 = NULL;
 464
 465         if (blame->map2) {
 466                 if (munmap(blame->map2, blame->size2) == -1)
 467                         return got_error_from_errno("munmap");
 468                 blame->map2 = blame->map1;
 469                 blame->map1 = NULL;
 470         }
 471         blame->size2 = blame->size1;
 472
 473         err = got_opentemp_truncate(blame->f2);
 474         if (err)
 475                 return err;
 476         tmp = blame->f2;
 477         blame->f2 = blame->f1;
 478         blame->f1 = tmp;
 479         blame->size1 = 0;
 480
 481         blame->nlines2 = blame->nlines1;
 482         blame->nlines1 = 0;
 483
 484         diff_data_free(blame->data2); /* does not free pointer itself */
 485         memset(blame->data2, 0, sizeof(*blame->data2));
 486         d = blame->data2;
 487         blame->data2 = blame->data1;
 488         blame->data1 = d;
 489
 490         return NULL;
 491 }
 492
 493 static const struct got_error *
 494 blame_open(struct got_blame **blamep, const char *path,
 495     struct got_object_id *start_commit_id, struct got_repository *repo,
 496     enum got_diff_algorithm diff_algo, got_blame_cb cb, void *arg,
 497     got_cancel_cb cancel_cb, void *cancel_arg,
 498     int fd1, int fd2, FILE *f1, FILE *f2)
 499 {
 500         const struct got_error *err = NULL;
 501         struct got_commit_object *start_commit = NULL, *last_commit = NULL;
 502         struct got_object_id *obj_id = NULL;
 503         struct got_blob_object *blob = NULL;
 504         struct got_blame *blame = NULL;
 505         struct got_object_id *id = NULL;
 506         int lineno;
 507         struct got_commit_graph *graph = NULL;
 508
 509         *blamep = NULL;
 510
 511         err = got_object_open_as_commit(&start_commit, repo, start_commit_id);
 512         if (err)
 513                 goto done;
 514
 515         err = got_object_id_by_path(&obj_id, repo, start_commit, path);
 516         if (err)
 517                 goto done;
 518
 519         err = got_object_open_as_blob(&blob, repo, obj_id, 8192, fd1);
 520         if (err)
 521                 goto done;
 522
 523         blame = calloc(1, sizeof(*blame));
 524         if (blame == NULL) {
 525                 err = got_error_from_errno("calloc");
 526                 goto done;
 527         }
 528
 529         blame->data1 = calloc(1, sizeof(*blame->data1));
 530         if (blame->data1 == NULL) {
 531                 err = got_error_from_errno("calloc");
 532                 goto done;
 533         }
 534         blame->data2 = calloc(1, sizeof(*blame->data2));
 535         if (blame->data2 == NULL) {
 536                 err = got_error_from_errno("calloc");
 537                 goto done;
 538         }
 539
 540         blame->f1 = f1;
 541         blame->f2 = f2;
 542         blame->fd = fd2;
 543
 544         err = got_diff_get_config(&blame->cfg, diff_algo, blame_atomize_file,
 545             blame);
 546         if (err)
 547                 goto done;
 548
 549         err = blame_prepare_file(blame->f2, &blame->map2, &blame->size2,
 550             &blame->nlines2, &blame->line_offsets2, blame->data2,
 551             blame->cfg, blob);
 552         blame->nlines = blame->nlines2;
 553         if (err || blame->nlines == 0)
 554                 goto done;
 555
 556         got_object_blob_close(blob);
 557         blob = NULL;
 558
 559         /* Don't include \n at EOF in the blame line count. */
 560         if (blame->line_offsets2[blame->nlines - 1] == blame->size2)
 561                 blame->nlines--;
 562
 563         blame->lines = calloc(blame->nlines, sizeof(*blame->lines));
 564         if (blame->lines == NULL) {
 565                 err = got_error_from_errno("calloc");
 566                 goto done;
 567         }
 568
 569         blame->linemap2 = calloc(blame->nlines2, sizeof(*blame->linemap2));
 570         if (blame->linemap2 == NULL) {
 571                 err = got_error_from_errno("calloc");
 572                 goto done;
 573         }
 574         for (lineno = 0; lineno < blame->nlines2; lineno++)
 575                 blame->linemap2[lineno] = lineno;
 576
 577         err = got_commit_graph_open(&graph, path, 1);
 578         if (err)
 579                 goto done;
 580
 581         err = got_commit_graph_iter_start(graph, start_commit_id, repo,
 582             cancel_cb, cancel_arg);
 583         if (err)
 584                 goto done;
 585         for (;;) {
 586                 struct got_object_id *next_id;
 587                 err = got_commit_graph_iter_next(&next_id, graph, repo,
 588                     cancel_cb, cancel_arg);
 589                 if (err) {
 590                         if (err->code == GOT_ERR_ITER_COMPLETED) {
 591                                 err = NULL;
 592                                 break;
 593                         }
 594                         goto done;
 595                 }
 596                 if (next_id) {
 597                         id = next_id;
 598                         err = blame_commit(blame, id, path, repo, cb, arg);
 599                         if (err) {
 600                                 if (err->code == GOT_ERR_ITER_COMPLETED)
 601                                         err = NULL;
 602                                 goto done;
 603                         }
 604                         if (blame->nannotated == blame->nlines)
 605                                 break;
 606
 607                         err = flip_files(blame);
 608                         if (err)
 609                                 goto done;
 610                 }
 611         }
 612
 613         if (id && blame->nannotated < blame->nlines) {
 614                 /* Annotate remaining non-annotated lines with last commit. */
 615                 err = got_object_open_as_commit(&last_commit, repo, id);
 616                 if (err)
 617                         goto done;
 618                 for (lineno = 0; lineno < blame->nlines; lineno++) {
 619                         err = annotate_line(blame, lineno, last_commit, id,
 620                             cb, arg);
 621                         if (err)
 622                                 goto done;
 623                 }
 624         }
 625
 626 done:
 627         if (graph)
 628                 got_commit_graph_close(graph);
 629         free(obj_id);
 630         if (blob)
 631                 got_object_blob_close(blob);
 632         if (start_commit)
 633                 got_object_commit_close(start_commit);
 634         if (last_commit)
 635                 got_object_commit_close(last_commit);
 636         if (err) {
 637                 if (blame)
 638                         blame_close(blame);
 639         } else
 640                 *blamep = blame;
 641
 642         return err;
 643 }
 644
 645 const struct got_error *
 646 got_blame(const char *path, struct got_object_id *commit_id,
 647     struct got_repository *repo, enum got_diff_algorithm diff_algo,
 648     got_blame_cb cb, void *arg, got_cancel_cb cancel_cb, void* cancel_arg,
 649     int fd1, int fd2, FILE *f1, FILE *f2)
 650 {
 651         const struct got_error *err = NULL, *close_err = NULL;
 652         struct got_blame *blame;
 653         char *abspath;
 654
 655         if (asprintf(&abspath, "%s%s", path[0] == '/' ? "" : "/", path) == -1)
 656                 return got_error_from_errno2("asprintf", path);
 657
 658         err = blame_open(&blame, abspath, commit_id, repo, diff_algo,
 659             cb, arg, cancel_cb, cancel_arg, fd1, fd2, f1, f2);
 660         free(abspath);
 661         if (blame)
 662                 close_err = blame_close(blame);
 663         return err ? err : close_err;
 664 }