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
  17 GIT__USE_OIDMAP
  18
  19 git_commit_list_node *git_revwalk__commit_lookup(
  20         git_revwalk *walk, const git_oid *oid)
  21 {
  22         git_commit_list_node *commit;
  23         khiter_t pos;
  24         int ret;
  25
  26         /* lookup and reserve space if not already present */
  27         pos = kh_get(oid, walk->commits, oid);
  28         if (pos != kh_end(walk->commits))
  29                 return kh_value(walk->commits, pos);
  30
  31         commit = git_commit_list_alloc_node(walk);
  32         if (commit == NULL)
  33                 return NULL;
  34
  35         git_oid_cpy(&commit->oid, oid);
  36
  37         pos = kh_put(oid, walk->commits, &commit->oid, &ret);
  38         assert(ret != 0);
  39         kh_value(walk->commits, pos) = commit;
  40
  41         return commit;
  42 }
  43
  44 typedef git_array_t(git_commit_list_node*) commit_list_node_array;
  45
  46 static bool interesting_arr(commit_list_node_array arr)
  47 {
  48         git_commit_list_node **n;
  49         size_t i = 0, size;
  50
  51         size = git_array_size(arr);
  52         for (i = 0; i < size; i++) {
  53                 n = git_array_get(arr, i);
  54                 if (!*n)
  55                         break;
  56
  57                 if (!(*n)->uninteresting)
  58                         return true;
  59         }
  60
  61         return false;
  62 }
  63
  64 static int mark_uninteresting(git_revwalk *walk, git_commit_list_node *commit)
  65 {
  66         int error;
  67         unsigned short i;
  68         commit_list_node_array pending = GIT_ARRAY_INIT;
  69         git_commit_list_node **tmp;
  70
  71         assert(commit);
  72
  73         do {
  74                 commit->uninteresting = 1;
  75
  76                 if ((error = git_commit_list_parse(walk, commit)) < 0)
  77                         return error;
  78
  79                 for (i = 0; i < commit->out_degree; ++i)
  80                         if (!commit->parents[i]->uninteresting) {
  81                                 git_commit_list_node **node = git_array_alloc(pending);
  82                                 GITERR_CHECK_ALLOC(node);
  83                                 *node = commit->parents[i];
  84                         }
  85
  86                 tmp = git_array_pop(pending);
  87                 commit = tmp ? *tmp : NULL;
  88
  89         } while (commit != NULL && !interesting_arr(pending));
  90
  91         git_array_clear(pending);
  92
  93         return 0;
  94 }
  95
  96 static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
  97 {
  98         int error;
  99
 100         if (!hide && walk->hide_cb)
 101                 hide = walk->hide_cb(&commit->oid, walk->hide_cb_payload);
 102
 103         if (hide && mark_uninteresting(walk, commit) < 0)
 104                 return -1;
 105
 106         if (commit->seen)
 107                 return 0;
 108
 109         commit->seen = 1;
 110
 111         if ((error = git_commit_list_parse(walk, commit)) < 0)
 112                 return error;
 113
 114         if (!hide)
 115                 return walk->enqueue(walk, commit);
 116
 117         return 0;
 118 }
 119
 120 static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit)
 121 {
 122         unsigned short i, max;
 123         int error = 0;
 124
 125         max = commit->out_degree;
 126         if (walk->first_parent && commit->out_degree)
 127                 max = 1;
 128
 129         for (i = 0; i < max && !error; ++i)
 130                 error = process_commit(walk, commit->parents[i], commit->uninteresting);
 131
 132         return error;
 133 }
 134
 135 static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int from_glob)
 136 {
 137         git_oid commit_id;
 138         int error;
 139         git_object *obj, *oobj;
 140         git_commit_list_node *commit;
 141         git_commit_list *list;
 142
 143         if ((error = git_object_lookup(&oobj, walk->repo, oid, GIT_OBJ_ANY)) < 0)
 144                 return error;
 145
 146         error = git_object_peel(&obj, oobj, GIT_OBJ_COMMIT);
 147         git_object_free(oobj);
 148
 149         if (error == GIT_ENOTFOUND || error == GIT_EINVALIDSPEC || error == GIT_EPEEL) {
 150                 /* If this comes from e.g. push_glob("tags"), ignore this */
 151                 if (from_glob)
 152                         return 0;
 153
 154                 giterr_set(GITERR_INVALID, "Object is not a committish");
 155                 return -1;
 156         }
 157         if (error < 0)
 158                 return error;
 159
 160         git_oid_cpy(&commit_id, git_object_id(obj));
 161         git_object_free(obj);
 162
 163         commit = git_revwalk__commit_lookup(walk, &commit_id);
 164         if (commit == NULL)
 165                 return -1; /* error already reported by failed lookup */
 166
 167         /* A previous hide already told us we don't want this commit  */
 168         if (commit->uninteresting)
 169                 return 0;
 170
 171         if (uninteresting)
 172                 walk->did_hide = 1;
 173         else
 174                 walk->did_push = 1;
 175
 176         commit->uninteresting = uninteresting;
 177         list = walk->user_input;
 178         if (git_commit_list_insert(commit, &list) == NULL) {
 179                 giterr_set_oom();
 180                 return -1;
 181         }
 182
 183         walk->user_input = list;
 184
 185         return 0;
 186 }
 187
 188 int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
 189 {
 190         assert(walk && oid);
 191         return push_commit(walk, oid, 0, false);
 192 }
 193
 194
 195 int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
 196 {
 197         assert(walk && oid);
 198         return push_commit(walk, oid, 1, false);
 199 }
 200
 201 static int push_ref(git_revwalk *walk, const char *refname, int hide, int from_glob)
 202 {
 203         git_oid oid;
 204
 205         if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
 206                 return -1;
 207
 208         return push_commit(walk, &oid, hide, from_glob);
 209 }
 210
 211 static int push_glob(git_revwalk *walk, const char *glob, int hide)
 212 {
 213         int error = 0;
 214         git_buf buf = GIT_BUF_INIT;
 215         git_reference *ref;
 216         git_reference_iterator *iter;
 217         size_t wildcard;
 218
 219         assert(walk && glob);
 220
 221         /* refs/ is implied if not given in the glob */
 222         if (git__prefixcmp(glob, GIT_REFS_DIR) != 0)
 223                 git_buf_joinpath(&buf, GIT_REFS_DIR, glob);
 224         else
 225                 git_buf_puts(&buf, glob);
 226         GITERR_CHECK_ALLOC_BUF(&buf);
 227
 228         /* If no '?', '*' or '[' exist, we append '/ *' to the glob */
 229         wildcard = strcspn(glob, "?*[");
 230         if (!glob[wildcard])
 231                 git_buf_put(&buf, "/*", 2);
 232
 233         if ((error = git_reference_iterator_glob_new(&iter, walk->repo, buf.ptr)) < 0)
 234                 goto out;
 235
 236         while ((error = git_reference_next(&ref, iter)) == 0) {
 237                 error = push_ref(walk, git_reference_name(ref), hide, true);
 238                 git_reference_free(ref);
 239                 if (error < 0)
 240                         break;
 241         }
 242         git_reference_iterator_free(iter);
 243
 244         if (error == GIT_ITEROVER)
 245                 error = 0;
 246 out:
 247         git_buf_free(&buf);
 248         return error;
 249 }
 250
 251 int git_revwalk_push_glob(git_revwalk *walk, const char *glob)
 252 {
 253         assert(walk && glob);
 254         return push_glob(walk, glob, 0);
 255 }
 256
 257 int git_revwalk_hide_glob(git_revwalk *walk, const char *glob)
 258 {
 259         assert(walk && glob);
 260         return push_glob(walk, glob, 1);
 261 }
 262
 263 int git_revwalk_push_head(git_revwalk *walk)
 264 {
 265         assert(walk);
 266         return push_ref(walk, GIT_HEAD_FILE, 0, false);
 267 }
 268
 269 int git_revwalk_hide_head(git_revwalk *walk)
 270 {
 271         assert(walk);
 272         return push_ref(walk, GIT_HEAD_FILE, 1, false);
 273 }
 274
 275 int git_revwalk_push_ref(git_revwalk *walk, const char *refname)
 276 {
 277         assert(walk && refname);
 278         return push_ref(walk, refname, 0, false);
 279 }
 280
 281 int git_revwalk_push_range(git_revwalk *walk, const char *range)
 282 {
 283         git_revspec revspec;
 284         int error = 0;
 285
 286         if ((error = git_revparse(&revspec, walk->repo, range)))
 287                 return error;
 288
 289         if (revspec.flags & GIT_REVPARSE_MERGE_BASE) {
 290                 /* TODO: support "<commit>...<commit>" */
 291                 giterr_set(GITERR_INVALID, "Symmetric differences not implemented in revwalk");
 292                 return GIT_EINVALIDSPEC;
 293         }
 294
 295         if ((error = push_commit(walk, git_object_id(revspec.from), 1, false)))
 296                 goto out;
 297
 298         error = push_commit(walk, git_object_id(revspec.to), 0, false);
 299
 300 out:
 301         git_object_free(revspec.from);
 302         git_object_free(revspec.to);
 303         return error;
 304 }
 305
 306 int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
 307 {
 308         assert(walk && refname);
 309         return push_ref(walk, refname, 1, false);
 310 }
 311
 312 static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
 313 {
 314         return git_pqueue_insert(&walk->iterator_time, commit);
 315 }
 316
 317 static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
 318 {
 319         return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
 320 }
 321
 322 static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
 323 {
 324         int error;
 325         git_commit_list_node *next;
 326
 327         while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL)
 328                 if (!next->uninteresting) {
 329                         if ((error = process_commit_parents(walk, next)) < 0)
 330                                 return error;
 331
 332                         *object_out = next;
 333                         return 0;
 334                 }
 335
 336         giterr_clear();
 337         return GIT_ITEROVER;
 338 }
 339
 340 static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
 341 {
 342         int error;
 343         git_commit_list_node *next;
 344
 345         while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL)
 346                 if (!next->uninteresting) {
 347                         if ((error = process_commit_parents(walk, next)) < 0)
 348                                 return error;
 349
 350                         *object_out = next;
 351                         return 0;
 352                 }
 353
 354         giterr_clear();
 355         return GIT_ITEROVER;
 356 }
 357
 358 static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
 359 {
 360         git_commit_list_node *next;
 361         unsigned short i, max;
 362
 363         for (;;) {
 364                 next = git_commit_list_pop(&walk->iterator_topo);
 365                 if (next == NULL) {
 366                         giterr_clear();
 367                         return GIT_ITEROVER;
 368                 }
 369
 370                 if (next->in_degree > 0) {
 371                         next->topo_delay = 1;
 372                         continue;
 373                 }
 374
 375
 376                 max = next->out_degree;
 377                 if (walk->first_parent && next->out_degree)
 378                         max = 1;
 379
 380                 for (i = 0; i < max; ++i) {
 381                         git_commit_list_node *parent = next->parents[i];
 382
 383                         if (--parent->in_degree == 0 && parent->topo_delay) {
 384                                 parent->topo_delay = 0;
 385                                 if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL)
 386                                         return -1;
 387                         }
 388                 }
 389
 390                 *object_out = next;
 391                 return 0;
 392         }
 393 }
 394
 395 static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
 396 {
 397         *object_out = git_commit_list_pop(&walk->iterator_reverse);
 398         return *object_out ? 0 : GIT_ITEROVER;
 399 }
 400
 401
 402 static int interesting(git_pqueue *list)
 403 {
 404         size_t i;
 405
 406         for (i = 0; i < git_pqueue_size(list); i++) {
 407                 git_commit_list_node *commit = git_pqueue_get(list, i);
 408                 if (!commit->uninteresting)
 409                         return 1;
 410         }
 411
 412         return 0;
 413 }
 414
 415 static int contains(git_pqueue *list, git_commit_list_node *node)
 416 {
 417         size_t i;
 418
 419         for (i = 0; i < git_pqueue_size(list); i++) {
 420                 git_commit_list_node *commit = git_pqueue_get(list, i);
 421                 if (commit == node)
 422                         return 1;
 423         }
 424
 425         return 0;
 426 }
 427
 428 static int premark_uninteresting(git_revwalk *walk)
 429 {
 430         int error = 0;
 431         unsigned short i;
 432         git_pqueue q;
 433         git_commit_list *list;
 434         git_commit_list_node *commit, *parent;
 435
 436         if ((error = git_pqueue_init(&q, 0, 8, git_commit_list_time_cmp)) < 0)
 437                 return error;
 438
 439         for (list = walk->user_input; list; list = list->next) {
 440                 if ((error = git_commit_list_parse(walk, list->item)) < 0)
 441                         goto cleanup;
 442
 443                 if ((error = git_pqueue_insert(&q, list->item)) < 0)
 444                         goto cleanup;
 445         }
 446
 447         while (interesting(&q)) {
 448                 commit = git_pqueue_pop(&q);
 449
 450                 for (i = 0; i < commit->out_degree; i++) {
 451                         parent = commit->parents[i];
 452
 453                         if ((error = git_commit_list_parse(walk, parent)) < 0)
 454                                 goto cleanup;
 455
 456                         if (commit->uninteresting)
 457                                 parent->uninteresting = 1;
 458
 459                         if (contains(&q, parent))
 460                                 continue;
 461
 462                         if ((error = git_pqueue_insert(&q, parent)) < 0)
 463                                 goto cleanup;
 464                 }
 465         }
 466
 467 cleanup:
 468         git_pqueue_free(&q);
 469         return error;
 470 }
 471
 472 static int prepare_walk(git_revwalk *walk)
 473 {
 474         int error;
 475         git_commit_list *list;
 476         git_commit_list_node *next;
 477
 478         /* If there were no pushes, we know that the walk is already over */
 479         if (!walk->did_push) {
 480                 giterr_clear();
 481                 return GIT_ITEROVER;
 482         }
 483
 484         if (walk->did_hide && (error = premark_uninteresting(walk)) < 0)
 485                 return error;
 486
 487         for (list = walk->user_input; list; list = list->next) {
 488                 if (process_commit(walk, list->item, list->item->uninteresting) < 0)
 489                         return -1;
 490         }
 491
 492
 493         if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
 494                 unsigned short i;
 495
 496                 while ((error = walk->get_next(&next, walk)) == 0) {
 497                         for (i = 0; i < next->out_degree; ++i) {
 498                                 git_commit_list_node *parent = next->parents[i];
 499                                 parent->in_degree++;
 500                         }
 501
 502                         if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
 503                                 return -1;
 504                 }
 505
 506                 if (error != GIT_ITEROVER)
 507                         return error;
 508
 509                 walk->get_next = &revwalk_next_toposort;
 510         }
 511
 512         if (walk->sorting & GIT_SORT_REVERSE) {
 513
 514                 while ((error = walk->get_next(&next, walk)) == 0)
 515                         if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
 516                                 return -1;
 517
 518                 if (error != GIT_ITEROVER)
 519                         return error;
 520
 521                 walk->get_next = &revwalk_next_reverse;
 522         }
 523
 524         walk->walking = 1;
 525         return 0;
 526 }
 527
 528
 529 int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 530 {
 531         git_revwalk *walk = git__calloc(1, sizeof(git_revwalk));
 532         GITERR_CHECK_ALLOC(walk);
 533
 534         walk->commits = git_oidmap_alloc();
 535         GITERR_CHECK_ALLOC(walk->commits);
 536
 537         if (git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0)
 538                 return -1;
 539
 540         git_pool_init(&walk->commit_pool, COMMIT_ALLOC);
 541         walk->get_next = &revwalk_next_unsorted;
 542         walk->enqueue = &revwalk_enqueue_unsorted;
 543
 544         walk->repo = repo;
 545
 546         if (git_repository_odb(&walk->odb, repo) < 0) {
 547                 git_revwalk_free(walk);
 548                 return -1;
 549         }
 550
 551         *revwalk_out = walk;
 552         return 0;
 553 }
 554
 555 void git_revwalk_free(git_revwalk *walk)
 556 {
 557         if (walk == NULL)
 558                 return;
 559
 560         git_revwalk_reset(walk);
 561         git_odb_free(walk->odb);
 562
 563         git_oidmap_free(walk->commits);
 564         git_pool_clear(&walk->commit_pool);
 565         git_pqueue_free(&walk->iterator_time);
 566         git__free(walk);
 567 }
 568
 569 git_repository *git_revwalk_repository(git_revwalk *walk)
 570 {
 571         assert(walk);
 572         return walk->repo;
 573 }
 574
 575 void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
 576 {
 577         assert(walk);
 578
 579         if (walk->walking)
 580                 git_revwalk_reset(walk);
 581
 582         walk->sorting = sort_mode;
 583
 584         if (walk->sorting & GIT_SORT_TIME) {
 585                 walk->get_next = &revwalk_next_timesort;
 586                 walk->enqueue = &revwalk_enqueue_timesort;
 587         } else {
 588                 walk->get_next = &revwalk_next_unsorted;
 589                 walk->enqueue = &revwalk_enqueue_unsorted;
 590         }
 591 }
 592
 593 void git_revwalk_simplify_first_parent(git_revwalk *walk)
 594 {
 595         walk->first_parent = 1;
 596 }
 597
 598 int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 599 {
 600         int error;
 601         git_commit_list_node *next;
 602
 603         assert(walk && oid);
 604
 605         if (!walk->walking) {
 606                 if ((error = prepare_walk(walk)) < 0)
 607                         return error;
 608         }
 609
 610         error = walk->get_next(&next, walk);
 611
 612         if (error == GIT_ITEROVER) {
 613                 git_revwalk_reset(walk);
 614                 giterr_clear();
 615                 return GIT_ITEROVER;
 616         }
 617
 618         if (!error)
 619                 git_oid_cpy(oid, &next->oid);
 620
 621         return error;
 622 }
 623
 624 void git_revwalk_reset(git_revwalk *walk)
 625 {
 626         git_commit_list_node *commit;
 627
 628         assert(walk);
 629
 630         kh_foreach_value(walk->commits, commit, {
 631                 commit->seen = 0;
 632                 commit->in_degree = 0;
 633                 commit->topo_delay = 0;
 634                 commit->uninteresting = 0;
 635                 commit->flags = 0;
 636                 });
 637
 638         git_pqueue_clear(&walk->iterator_time);
 639         git_commit_list_free(&walk->iterator_topo);
 640         git_commit_list_free(&walk->iterator_rand);
 641         git_commit_list_free(&walk->iterator_reverse);
 642         git_commit_list_free(&walk->user_input);
 643         walk->first_parent = 0;
 644         walk->walking = 0;
 645         walk->did_push = walk->did_hide = 0;
 646 }
 647
 648 int git_revwalk_add_hide_cb(
 649         git_revwalk *walk,
 650         git_revwalk_hide_cb hide_cb,
 651         void *payload)
 652 {
 653         assert(walk);
 654
 655         if (walk->walking)
 656                 git_revwalk_reset(walk);
 657
 658         if (walk->hide_cb) {
 659                 /* There is already a callback added */
 660                 giterr_set(GITERR_INVALID, "There is already a callback added to hide commits in revision walker.");
 661                 return -1;
 662         }
 663
 664         walk->hide_cb = hide_cb;
 665         walk->hide_cb_payload = payload;
 666
 667         return 0;
 668 }
 669