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