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