src/revwalk.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "common.h"
   9 #include "commit.h"
  10 #include "odb.h"
  11 #include "pool.h"
  12
  13 #include "revwalk.h"
  14 #include "git2/revparse.h"
  15 #include "merge.h"
  16 #include "vector.h"
  17
  18 GIT__USE_OIDMAP
  19
  20 git_commit_list_node *git_revwalk__commit_lookup(
  21         git_revwalk *walk, const git_oid *oid)
  22 {
  23         git_commit_list_node *commit;
  24         khiter_t pos;
  25         int ret;
  26
  27         /* lookup and reserve space if not already present */
  28         pos = kh_get(oid, walk->commits, oid);
  29         if (pos != kh_end(walk->commits))
  30                 return kh_value(walk->commits, pos);
  31
  32         commit = git_commit_list_alloc_node(walk);
  33         if (commit == NULL)
  34                 return NULL;
  35
  36         git_oid_cpy(&commit->oid, oid);
  37
  38         pos = kh_put(oid, walk->commits, &commit->oid, &ret);
  39         assert(ret != 0);
  40         kh_value(walk->commits, pos) = commit;
  41
  42         return commit;
  43 }
  44
  45 static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int from_glob)
  46 {
  47         git_oid commit_id;
  48         int error;
  49         git_object *obj, *oobj;
  50         git_commit_list_node *commit;
  51         git_commit_list *list;
  52
  53         if ((error = git_object_lookup(&oobj, walk->repo, oid, GIT_OBJ_ANY)) < 0)
  54                 return error;
  55
  56         error = git_object_peel(&obj, oobj, GIT_OBJ_COMMIT);
  57         git_object_free(oobj);
  58
  59         if (error == GIT_ENOTFOUND || error == GIT_EINVALIDSPEC || error == GIT_EPEEL) {
  60                 /* If this comes from e.g. push_glob("tags"), ignore this */
  61                 if (from_glob)
  62                         return 0;
  63
  64                 giterr_set(GITERR_INVALID, "Object is not a committish");
  65                 return -1;
  66         }
  67         if (error < 0)
  68                 return error;
  69
  70         git_oid_cpy(&commit_id, git_object_id(obj));
  71         git_object_free(obj);
  72
  73         commit = git_revwalk__commit_lookup(walk, &commit_id);
  74         if (commit == NULL)
  75                 return -1; /* error already reported by failed lookup */
  76
  77         /* A previous hide already told us we don't want this commit  */
  78         if (commit->uninteresting)
  79                 return 0;
  80
  81         if (uninteresting)
  82                 walk->did_hide = 1;
  83         else
  84                 walk->did_push = 1;
  85
  86         commit->uninteresting = uninteresting;
  87         list = walk->user_input;
  88         if (git_commit_list_insert(commit, &list) == NULL) {
  89                 giterr_set_oom();
  90                 return -1;
  91         }
  92
  93         walk->user_input = list;
  94
  95         return 0;
  96 }
  97
  98 int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
  99 {
 100         assert(walk && oid);
 101         return push_commit(walk, oid, 0, false);
 102 }
 103
 104
 105 int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
 106 {
 107         assert(walk && oid);
 108         return push_commit(walk, oid, 1, false);
 109 }
 110
 111 static int push_ref(git_revwalk *walk, const char *refname, int hide, int from_glob)
 112 {
 113         git_oid oid;
 114
 115         if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
 116                 return -1;
 117
 118         return push_commit(walk, &oid, hide, from_glob);
 119 }
 120
 121 static int push_glob(git_revwalk *walk, const char *glob, int hide)
 122 {
 123         int error = 0;
 124         git_buf buf = GIT_BUF_INIT;
 125         git_reference *ref;
 126         git_reference_iterator *iter;
 127         size_t wildcard;
 128
 129         assert(walk && glob);
 130
 131         /* refs/ is implied if not given in the glob */
 132         if (git__prefixcmp(glob, GIT_REFS_DIR) != 0)
 133                 git_buf_joinpath(&buf, GIT_REFS_DIR, glob);
 134         else
 135                 git_buf_puts(&buf, glob);
 136         GITERR_CHECK_ALLOC_BUF(&buf);
 137
 138         /* If no '?', '*' or '[' exist, we append '/ *' to the glob */
 139         wildcard = strcspn(glob, "?*[");
 140         if (!glob[wildcard])
 141                 git_buf_put(&buf, "/*", 2);
 142
 143         if ((error = git_reference_iterator_glob_new(&iter, walk->repo, buf.ptr)) < 0)
 144                 goto out;
 145
 146         while ((error = git_reference_next(&ref, iter)) == 0) {
 147                 error = push_ref(walk, git_reference_name(ref), hide, true);
 148                 git_reference_free(ref);
 149                 if (error < 0)
 150                         break;
 151         }
 152         git_reference_iterator_free(iter);
 153
 154         if (error == GIT_ITEROVER)
 155                 error = 0;
 156 out:
 157         git_buf_free(&buf);
 158         return error;
 159 }
 160
 161 int git_revwalk_push_glob(git_revwalk *walk, const char *glob)
 162 {
 163         assert(walk && glob);
 164         return push_glob(walk, glob, 0);
 165 }
 166
 167 int git_revwalk_hide_glob(git_revwalk *walk, const char *glob)
 168 {
 169         assert(walk && glob);
 170         return push_glob(walk, glob, 1);
 171 }
 172
 173 int git_revwalk_push_head(git_revwalk *walk)
 174 {
 175         assert(walk);
 176         return push_ref(walk, GIT_HEAD_FILE, 0, false);
 177 }
 178
 179 int git_revwalk_hide_head(git_revwalk *walk)
 180 {
 181         assert(walk);
 182         return push_ref(walk, GIT_HEAD_FILE, 1, false);
 183 }
 184
 185 int git_revwalk_push_ref(git_revwalk *walk, const char *refname)
 186 {
 187         assert(walk && refname);
 188         return push_ref(walk, refname, 0, false);
 189 }
 190
 191 int git_revwalk_push_range(git_revwalk *walk, const char *range)
 192 {
 193         git_revspec revspec;
 194         int error = 0;
 195
 196         if ((error = git_revparse(&revspec, walk->repo, range)))
 197                 return error;
 198
 199         if (revspec.flags & GIT_REVPARSE_MERGE_BASE) {
 200                 /* TODO: support "<commit>...<commit>" */
 201                 giterr_set(GITERR_INVALID, "Symmetric differences not implemented in revwalk");
 202                 return GIT_EINVALIDSPEC;
 203         }
 204
 205         if ((error = push_commit(walk, git_object_id(revspec.from), 1, false)))
 206                 goto out;
 207
 208         error = push_commit(walk, git_object_id(revspec.to), 0, false);
 209
 210 out:
 211         git_object_free(revspec.from);
 212         git_object_free(revspec.to);
 213         return error;
 214 }
 215
 216 int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
 217 {
 218         assert(walk && refname);
 219         return push_ref(walk, refname, 1, false);
 220 }
 221
 222 static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
 223 {
 224         return git_pqueue_insert(&walk->iterator_time, commit);
 225 }
 226
 227 static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
 228 {
 229         return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
 230 }
 231
 232 static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
 233 {
 234         git_commit_list_node *next;
 235
 236         if ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
 237                 *object_out = next;
 238                 return 0;
 239         }
 240
 241         giterr_clear();
 242         return GIT_ITEROVER;
 243 }
 244
 245 static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
 246 {
 247         git_commit_list_node *next;
 248
 249         if ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL) {
 250                 *object_out = next;
 251                 return 0;
 252         }
 253
 254         giterr_clear();
 255         return GIT_ITEROVER;
 256 }
 257
 258 static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
 259 {
 260         git_commit_list_node *node;
 261
 262         node = git_commit_list_pop(&walk->iterator_topo);
 263         if (node) {
 264                 *object_out = node;
 265                 return 0;
 266         }
 267
 268         giterr_clear();
 269         return GIT_ITEROVER;
 270 }
 271
 272 static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
 273 {
 274         *object_out = git_commit_list_pop(&walk->iterator_reverse);
 275         return *object_out ? 0 : GIT_ITEROVER;
 276 }
 277
 278 static void mark_parents_uninteresting(git_commit_list_node *commit)
 279 {
 280         unsigned short i;
 281         git_commit_list *parents = NULL;
 282
 283         for (i = 0; i < commit->out_degree; i++)
 284                 git_commit_list_insert(commit->parents[i], &parents);
 285
 286
 287         while (parents) {
 288                 git_commit_list_node *commit = git_commit_list_pop(&parents);
 289
 290                 while (commit) {
 291                         if (commit->uninteresting)
 292                                 break;
 293
 294                         commit->uninteresting = 1;
 295                         /*
 296                          * If we've reached this commit some other way
 297                          * already, we need to mark its parents uninteresting
 298                          * as well.
 299                          */
 300                         if (!commit->parents)
 301                                 break;
 302
 303                         for (i = 0; i < commit->out_degree; i++)
 304                                 git_commit_list_insert(commit->parents[i], &parents);
 305                         commit = commit->parents[0];
 306                 }
 307         }
 308 }
 309
 310 static int add_parents_to_list(git_revwalk *walk, git_commit_list_node *commit, git_commit_list **list)
 311 {
 312         unsigned short i;
 313         int error;
 314
 315         if (commit->added)
 316                 return 0;
 317
 318         commit->added = 1;
 319
 320         /*
 321          * Go full on in the uninteresting case as we want to include
 322          * as many of these as we can.
 323          *
 324          * Usually we haven't parsed the parent of a parent, but if we
 325          * have it we reached it via other means so we want to mark
 326          * its parents recursively too.
 327          */
 328         if (commit->uninteresting) {
 329                 for (i = 0; i < commit->out_degree; i++) {
 330                         git_commit_list_node *p = commit->parents[i];
 331                         p->uninteresting = 1;
 332
 333                         /* git does it gently here, but we don't like missing objects */
 334                         if ((error = git_commit_list_parse(walk, p)) < 0)
 335                                 return error;
 336
 337                         if (p->parents)
 338                                 mark_parents_uninteresting(p);
 339
 340                         p->seen = 1;
 341                         git_commit_list_insert_by_date(p, list);
 342                 }
 343
 344                 return 0;
 345         }
 346
 347         /*
 348          * Now on to what we do if the commit is indeed
 349          * interesting. Here we do want things like first-parent take
 350          * effect as this is what we'll be showing.
 351          */
 352         for (i = 0; i < commit->out_degree; i++) {
 353                 git_commit_list_node *p = commit->parents[i];
 354
 355                 if ((error = git_commit_list_parse(walk, p)) < 0)
 356                         return error;
 357
 358                 if (walk->hide_cb && walk->hide_cb(&p->oid, walk->hide_cb_payload))
 359                         continue;
 360
 361                 if (!p->seen) {
 362                         p->seen = 1;
 363                         git_commit_list_insert_by_date(p, list);
 364                 }
 365
 366                 if (walk->first_parent)
 367                         break;
 368         }
 369         return 0;
 370 }
 371
 372 static int everybody_uninteresting(git_commit_list *orig)
 373 {
 374         git_commit_list *list = orig;
 375
 376         while (list) {
 377                 git_commit_list_node *commit = list->item;
 378                 list = list->next;
 379                 if (!commit->uninteresting)
 380                         return 0;
 381         }
 382
 383         return 1;
 384 }
 385
 386 /* How many unintersting commits we want to look at after we run out of interesting ones */
 387 #define SLOP 5
 388
 389 static int still_interesting(git_commit_list *list, int64_t time, int slop)
 390 {
 391         /* The empty list is pretty boring */
 392         if (!list)
 393                 return 0;
 394
 395         /*
 396          * If the destination list has commits with an earlier date
 397          * than our source we want to continue looking.
 398          */
 399         if (time <= list->item->time)
 400                 return SLOP;
 401
 402         /* If we find interesting commits, we reset the slop count */
 403         if (!everybody_uninteresting(list))
 404                 return SLOP;
 405
 406         /* Everything's uninteresting, reduce the count */
 407         return slop - 1;
 408 }
 409
 410 static int limit_list(git_commit_list **out, git_revwalk *walk, git_commit_list *commits)
 411 {
 412         int error, slop = SLOP;
 413         int64_t time = ~0ll;
 414         git_commit_list *list = commits;
 415         git_commit_list *newlist = NULL;
 416         git_commit_list **p = &newlist;
 417
 418         while (list) {
 419                 git_commit_list_node *commit = git_commit_list_pop(&list);
 420
 421                 if ((error = add_parents_to_list(walk, commit, &list)) < 0)
 422                         return error;
 423
 424                 if (commit->uninteresting) {
 425                         mark_parents_uninteresting(commit);
 426
 427                         slop = still_interesting(list, time, slop);
 428                         if (slop)
 429                                 continue;
 430
 431                         break;
 432                 }
 433
 434                 if (!commit->uninteresting && walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload))
 435                                 continue;
 436
 437                 time = commit->time;
 438                 p = &git_commit_list_insert(commit, p)->next;
 439         }
 440
 441         git_commit_list_free(&list);
 442         *out = newlist;
 443         return 0;
 444 }
 445
 446 static int sort_in_topological_order(git_commit_list **out, git_revwalk *walk)
 447 {
 448         git_commit_list *list = NULL, *ll = NULL, *newlist, **pptr;
 449         git_commit_list_node *next;
 450         git_pqueue queue;
 451         git_vector_cmp queue_cmp = NULL;
 452         unsigned short i;
 453         int error;
 454
 455         if (walk->sorting & GIT_SORT_TIME)
 456                 queue_cmp = git_commit_list_time_cmp;
 457
 458         if ((error = git_pqueue_init(&queue, 0, 8, queue_cmp)))
 459                 return error;
 460
 461         /*
 462          * Start by resetting the in-degree to 1 for the commits in
 463          * our list. We want to go through this list again, so we
 464          * store it in the commit list as we extract it from the lower
 465          * machinery.
 466          */
 467         while ((error = walk->get_next(&next, walk)) == 0) {
 468                 next->in_degree = 1;
 469                 git_commit_list_insert(next, &list);
 470         }
 471
 472         if (error != GIT_ITEROVER)
 473                 goto cleanup;
 474
 475         error = 0;
 476
 477         /*
 478          * Count up how many children each commit has. We limit
 479          * ourselves to those commits in the original list (in-degree
 480          * of 1) avoiding setting it for any parent that was hidden.
 481          */
 482         for(ll = list; ll; ll = ll->next) {
 483                 for (i = 0; i < ll->item->out_degree; ++i) {
 484                         git_commit_list_node *parent = ll->item->parents[i];
 485                         if (parent->in_degree)
 486                                 parent->in_degree++;
 487                 }
 488         }
 489
 490         /*
 491          * Now we find the tips i.e. those not reachable from any other node
 492          * i.e. those which still have an in-degree of 1.
 493          */
 494         for(ll = list; ll; ll = ll->next) {
 495                 if (ll->item->in_degree == 1) {
 496                         if ((error = git_pqueue_insert(&queue, ll->item)))
 497                                 goto cleanup;
 498                 }
 499         }
 500
 501         /*
 502          * We need to output the tips in the order that they came out of the
 503          * traversal, so if we're not doing time-sorting, we need to reverse the
 504          * pqueue in order to get them to come out as we inserted them.
 505          */
 506         if ((walk->sorting & GIT_SORT_TIME) == 0)
 507                 git_pqueue_reverse(&queue);
 508
 509
 510         pptr = &newlist;
 511         newlist = NULL;
 512         while ((next = git_pqueue_pop(&queue)) != NULL) {
 513                 for (i = 0; i < next->out_degree; ++i) {
 514                         git_commit_list_node *parent = next->parents[i];
 515                         if (parent->in_degree == 0)
 516                                 continue;
 517
 518                         if (--parent->in_degree == 1) {
 519                                 if ((error = git_pqueue_insert(&queue, parent)))
 520                                         goto cleanup;
 521                         }
 522                 }
 523
 524                 /* All the children of 'item' have been emitted (since we got to it via the priority queue) */
 525                 next->in_degree = 0;
 526
 527                 pptr = &git_commit_list_insert(next, pptr)->next;
 528         }
 529
 530         *out = newlist;
 531         error = 0;
 532
 533 cleanup:
 534         git_commit_list_free(&list);
 535         git_pqueue_free(&queue);
 536         return error;
 537 }
 538
 539 static int prepare_walk(git_revwalk *walk)
 540 {
 541         int error;
 542         git_commit_list *list, *commits = NULL;
 543         git_commit_list_node *next;
 544
 545         /* If there were no pushes, we know that the walk is already over */
 546         if (!walk->did_push) {
 547                 giterr_clear();
 548                 return GIT_ITEROVER;
 549         }
 550
 551         for (list = walk->user_input; list; list = list->next) {
 552                 git_commit_list_node *commit = list->item;
 553                 if ((error = git_commit_list_parse(walk, commit)) < 0)
 554                         return error;
 555
 556                 if (commit->uninteresting)
 557                         mark_parents_uninteresting(commit);
 558
 559                 if (!commit->seen) {
 560                         commit->seen = 1;
 561                         git_commit_list_insert(commit, &commits);
 562                 }
 563         }
 564
 565         if ((error = limit_list(&commits, walk, commits)) < 0)
 566                 return error;
 567
 568         for (list = commits; list; list = list->next) {
 569                 if (list->item->uninteresting)
 570                         continue;
 571
 572                 if ((error = walk->enqueue(walk, list->item)) < 0) {
 573                         git_commit_list_free(&commits);
 574                         return error;
 575                 }
 576         }
 577
 578         git_commit_list_free(&commits);
 579
 580         if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
 581                 if ((error = sort_in_topological_order(&walk->iterator_topo, walk)))
 582                         return error;
 583
 584                 walk->get_next = &revwalk_next_toposort;
 585         }
 586
 587         if (walk->sorting & GIT_SORT_REVERSE) {
 588
 589                 while ((error = walk->get_next(&next, walk)) == 0)
 590                         if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
 591                                 return -1;
 592
 593                 if (error != GIT_ITEROVER)
 594                         return error;
 595
 596                 walk->get_next = &revwalk_next_reverse;
 597         }
 598
 599         walk->walking = 1;
 600         return 0;
 601 }
 602
 603
 604 int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 605 {
 606         git_revwalk *walk = git__calloc(1, sizeof(git_revwalk));
 607         GITERR_CHECK_ALLOC(walk);
 608
 609         walk->commits = git_oidmap_alloc();
 610         GITERR_CHECK_ALLOC(walk->commits);
 611
 612         if (git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0)
 613                 return -1;
 614
 615         git_pool_init(&walk->commit_pool, COMMIT_ALLOC);
 616         walk->get_next = &revwalk_next_unsorted;
 617         walk->enqueue = &revwalk_enqueue_unsorted;
 618
 619         walk->repo = repo;
 620
 621         if (git_repository_odb(&walk->odb, repo) < 0) {
 622                 git_revwalk_free(walk);
 623                 return -1;
 624         }
 625
 626         *revwalk_out = walk;
 627         return 0;
 628 }
 629
 630 void git_revwalk_free(git_revwalk *walk)
 631 {
 632         if (walk == NULL)
 633                 return;
 634
 635         git_revwalk_reset(walk);
 636         git_odb_free(walk->odb);
 637
 638         git_oidmap_free(walk->commits);
 639         git_pool_clear(&walk->commit_pool);
 640         git_pqueue_free(&walk->iterator_time);
 641         git__free(walk);
 642 }
 643
 644 git_repository *git_revwalk_repository(git_revwalk *walk)
 645 {
 646         assert(walk);
 647         return walk->repo;
 648 }
 649
 650 void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
 651 {
 652         assert(walk);
 653
 654         if (walk->walking)
 655                 git_revwalk_reset(walk);
 656
 657         walk->sorting = sort_mode;
 658
 659         if (walk->sorting & GIT_SORT_TIME) {
 660                 walk->get_next = &revwalk_next_timesort;
 661                 walk->enqueue = &revwalk_enqueue_timesort;
 662         } else {
 663                 walk->get_next = &revwalk_next_unsorted;
 664                 walk->enqueue = &revwalk_enqueue_unsorted;
 665         }
 666 }
 667
 668 void git_revwalk_simplify_first_parent(git_revwalk *walk)
 669 {
 670         walk->first_parent = 1;
 671 }
 672
 673 int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 674 {
 675         int error;
 676         git_commit_list_node *next;
 677
 678         assert(walk && oid);
 679
 680         if (!walk->walking) {
 681                 if ((error = prepare_walk(walk)) < 0)
 682                         return error;
 683         }
 684
 685         error = walk->get_next(&next, walk);
 686
 687         if (error == GIT_ITEROVER) {
 688                 git_revwalk_reset(walk);
 689                 giterr_clear();
 690                 return GIT_ITEROVER;
 691         }
 692
 693         if (!error)
 694                 git_oid_cpy(oid, &next->oid);
 695
 696         return error;
 697 }
 698
 699 void git_revwalk_reset(git_revwalk *walk)
 700 {
 701         git_commit_list_node *commit;
 702
 703         assert(walk);
 704
 705         kh_foreach_value(walk->commits, commit, {
 706                 commit->seen = 0;
 707                 commit->in_degree = 0;
 708                 commit->topo_delay = 0;
 709                 commit->uninteresting = 0;
 710                 commit->added = 0;
 711                 commit->flags = 0;
 712                 });
 713
 714         git_pqueue_clear(&walk->iterator_time);
 715         git_commit_list_free(&walk->iterator_topo);
 716         git_commit_list_free(&walk->iterator_rand);
 717         git_commit_list_free(&walk->iterator_reverse);
 718         git_commit_list_free(&walk->user_input);
 719         walk->first_parent = 0;
 720         walk->walking = 0;
 721         walk->did_push = walk->did_hide = 0;
 722 }
 723
 724 int git_revwalk_add_hide_cb(
 725         git_revwalk *walk,
 726         git_revwalk_hide_cb hide_cb,
 727         void *payload)
 728 {
 729         assert(walk);
 730
 731         if (walk->walking)
 732                 git_revwalk_reset(walk);
 733
 734         if (walk->hide_cb) {
 735                 /* There is already a callback added */
 736                 giterr_set(GITERR_INVALID, "There is already a callback added to hide commits in revision walker.");
 737                 return -1;
 738         }
 739
 740         walk->hide_cb = hide_cb;
 741         walk->hide_cb_payload = payload;
 742
 743         return 0;
 744 }
 745