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_commit_list_node *git_revwalk__commit_lookup(
  18         git_revwalk *walk, const git_oid *oid)
  19 {
  20         git_commit_list_node *commit;
  21         khiter_t pos;
  22         int ret;
  23
  24         /* lookup and reserve space if not already present */
  25         pos = kh_get(oid, walk->commits, oid);
  26         if (pos != kh_end(walk->commits))
  27                 return kh_value(walk->commits, pos);
  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         pos = kh_put(oid, walk->commits, &commit->oid, &ret);
  36         assert(ret != 0);
  37         kh_value(walk->commits, pos) = commit;
  38
  39         return commit;
  40 }
  41
  42 static int mark_uninteresting(git_commit_list_node *commit)
  43 {
  44         unsigned short i;
  45         git_array_t(git_commit_list_node *) pending = GIT_ARRAY_INIT;
  46         git_commit_list_node **tmp;
  47
  48         assert(commit);
  49
  50         git_array_alloc(pending);
  51         GITERR_CHECK_ARRAY(pending);
  52
  53         do {
  54                 commit->uninteresting = 1;
  55
  56                 /* This means we've reached a merge base, so there's no need to walk any more */
  57                 if ((commit->flags & (RESULT | STALE)) == RESULT) {
  58                         tmp = git_array_pop(pending);
  59                         commit = tmp ? *tmp : NULL;
  60                         continue;
  61                 }
  62
  63                 for (i = 0; i < commit->out_degree; ++i)
  64                         if (!commit->parents[i]->uninteresting) {
  65                                 git_commit_list_node **node = git_array_alloc(pending);
  66                                 GITERR_CHECK_ALLOC(node);
  67                                 *node = commit->parents[i];
  68                         }
  69
  70                 tmp = git_array_pop(pending);
  71                 commit = tmp ? *tmp : NULL;
  72
  73         } while (git_array_size(pending) > 0);
  74
  75         git_array_clear(pending);
  76
  77         return 0;
  78 }
  79
  80 static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
  81 {
  82         int error;
  83
  84         if (hide && mark_uninteresting(commit) < 0)
  85                 return -1;
  86
  87         if (commit->seen)
  88                 return 0;
  89
  90         commit->seen = 1;
  91
  92         if ((error = git_commit_list_parse(walk, commit)) < 0)
  93                 return error;
  94
  95         return walk->enqueue(walk, commit);
  96 }
  97
  98 static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit)
  99 {
 100         unsigned short i, max;
 101         int error = 0;
 102
 103         max = commit->out_degree;
 104         if (walk->first_parent && commit->out_degree)
 105                 max = 1;
 106
 107         for (i = 0; i < max && !error; ++i)
 108                 error = process_commit(walk, commit->parents[i], commit->uninteresting);
 109
 110         return error;
 111 }
 112
 113 static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
 114 {
 115         git_object *obj;
 116         git_otype type;
 117         git_commit_list_node *commit;
 118
 119         if (git_object_lookup(&obj, walk->repo, oid, GIT_OBJ_ANY) < 0)
 120                 return -1;
 121
 122         type = git_object_type(obj);
 123         git_object_free(obj);
 124
 125         if (type != GIT_OBJ_COMMIT) {
 126                 giterr_set(GITERR_INVALID, "Object is no commit object");
 127                 return -1;
 128         }
 129
 130         commit = git_revwalk__commit_lookup(walk, oid);
 131         if (commit == NULL)
 132                 return -1; /* error already reported by failed lookup */
 133
 134         commit->uninteresting = uninteresting;
 135         if (walk->one == NULL && !uninteresting) {
 136                 walk->one = commit;
 137         } else {
 138                 if (git_vector_insert(&walk->twos, commit) < 0)
 139                         return -1;
 140         }
 141
 142         return 0;
 143 }
 144
 145 int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
 146 {
 147         assert(walk && oid);
 148         return push_commit(walk, oid, 0);
 149 }
 150
 151
 152 int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
 153 {
 154         assert(walk && oid);
 155         return push_commit(walk, oid, 1);
 156 }
 157
 158 static int push_ref(git_revwalk *walk, const char *refname, int hide)
 159 {
 160         git_oid oid;
 161
 162         if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
 163                 return -1;
 164
 165         return push_commit(walk, &oid, hide);
 166 }
 167
 168 struct push_cb_data {
 169         git_revwalk *walk;
 170         int hide;
 171 };
 172
 173 static int push_glob_cb(const char *refname, void *data_)
 174 {
 175         struct push_cb_data *data = (struct push_cb_data *)data_;
 176
 177         return push_ref(data->walk, refname, data->hide);
 178 }
 179
 180 static int push_glob(git_revwalk *walk, const char *glob, int hide)
 181 {
 182         int error = 0;
 183         git_buf buf = GIT_BUF_INIT;
 184         struct push_cb_data data;
 185         size_t wildcard;
 186
 187         assert(walk && glob);
 188
 189         /* refs/ is implied if not given in the glob */
 190         if (git__prefixcmp(glob, GIT_REFS_DIR) != 0)
 191                 git_buf_joinpath(&buf, GIT_REFS_DIR, glob);
 192         else
 193                 git_buf_puts(&buf, glob);
 194
 195         /* If no '?', '*' or '[' exist, we append '/ *' to the glob */
 196         wildcard = strcspn(glob, "?*[");
 197         if (!glob[wildcard])
 198                 git_buf_put(&buf, "/*", 2);
 199
 200         data.walk = walk;
 201         data.hide = hide;
 202
 203         if (git_buf_oom(&buf))
 204                 error = -1;
 205         else
 206                 error = git_reference_foreach_glob(
 207                         walk->repo, git_buf_cstr(&buf), push_glob_cb, &data);
 208
 209         git_buf_free(&buf);
 210         return error;
 211 }
 212
 213 int git_revwalk_push_glob(git_revwalk *walk, const char *glob)
 214 {
 215         assert(walk && glob);
 216         return push_glob(walk, glob, 0);
 217 }
 218
 219 int git_revwalk_hide_glob(git_revwalk *walk, const char *glob)
 220 {
 221         assert(walk && glob);
 222         return push_glob(walk, glob, 1);
 223 }
 224
 225 int git_revwalk_push_head(git_revwalk *walk)
 226 {
 227         assert(walk);
 228         return push_ref(walk, GIT_HEAD_FILE, 0);
 229 }
 230
 231 int git_revwalk_hide_head(git_revwalk *walk)
 232 {
 233         assert(walk);
 234         return push_ref(walk, GIT_HEAD_FILE, 1);
 235 }
 236
 237 int git_revwalk_push_ref(git_revwalk *walk, const char *refname)
 238 {
 239         assert(walk && refname);
 240         return push_ref(walk, refname, 0);
 241 }
 242
 243 int git_revwalk_push_range(git_revwalk *walk, const char *range)
 244 {
 245         git_revspec revspec;
 246         int error = 0;
 247
 248         if ((error = git_revparse(&revspec, walk->repo, range)))
 249                 return error;
 250
 251         if (revspec.flags & GIT_REVPARSE_MERGE_BASE) {
 252                 /* TODO: support "<commit>...<commit>" */
 253                 giterr_set(GITERR_INVALID, "Symmetric differences not implemented in revwalk");
 254                 return GIT_EINVALIDSPEC;
 255         }
 256
 257         if ((error = push_commit(walk, git_object_id(revspec.from), 1)))
 258                 goto out;
 259
 260         error = push_commit(walk, git_object_id(revspec.to), 0);
 261
 262 out:
 263         git_object_free(revspec.from);
 264         git_object_free(revspec.to);
 265         return error;
 266 }
 267
 268 int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
 269 {
 270         assert(walk && refname);
 271         return push_ref(walk, refname, 1);
 272 }
 273
 274 static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
 275 {
 276         return git_pqueue_insert(&walk->iterator_time, commit);
 277 }
 278
 279 static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
 280 {
 281         return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
 282 }
 283
 284 static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
 285 {
 286         int error;
 287         git_commit_list_node *next;
 288
 289         while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
 290                 if ((error = process_commit_parents(walk, next)) < 0)
 291                         return error;
 292
 293                 if (!next->uninteresting) {
 294                         *object_out = next;
 295                         return 0;
 296                 }
 297         }
 298
 299         giterr_clear();
 300         return GIT_ITEROVER;
 301 }
 302
 303 static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
 304 {
 305         int error;
 306         git_commit_list_node *next;
 307
 308         while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL) {
 309                 if ((error = process_commit_parents(walk, next)) < 0)
 310                         return error;
 311
 312                 if (!next->uninteresting) {
 313                         *object_out = next;
 314                         return 0;
 315                 }
 316         }
 317
 318         giterr_clear();
 319         return GIT_ITEROVER;
 320 }
 321
 322 static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
 323 {
 324         git_commit_list_node *next;
 325         unsigned short i, max;
 326
 327         for (;;) {
 328                 next = git_commit_list_pop(&walk->iterator_topo);
 329                 if (next == NULL) {
 330                         giterr_clear();
 331                         return GIT_ITEROVER;
 332                 }
 333
 334                 if (next->in_degree > 0) {
 335                         next->topo_delay = 1;
 336                         continue;
 337                 }
 338
 339
 340                 max = next->out_degree;
 341                 if (walk->first_parent && next->out_degree)
 342                         max = 1;
 343
 344                 for (i = 0; i < max; ++i) {
 345                         git_commit_list_node *parent = next->parents[i];
 346
 347                         if (--parent->in_degree == 0 && parent->topo_delay) {
 348                                 parent->topo_delay = 0;
 349                                 if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL)
 350                                         return -1;
 351                         }
 352                 }
 353
 354                 *object_out = next;
 355                 return 0;
 356         }
 357 }
 358
 359 static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
 360 {
 361         *object_out = git_commit_list_pop(&walk->iterator_reverse);
 362         return *object_out ? 0 : GIT_ITEROVER;
 363 }
 364
 365
 366 static int prepare_walk(git_revwalk *walk)
 367 {
 368         int error;
 369         unsigned int i;
 370         git_commit_list_node *next, *two;
 371         git_commit_list *bases = NULL;
 372
 373         /*
 374          * If walk->one is NULL, there were no positive references,
 375          * so we know that the walk is already over.
 376          */
 377         if (walk->one == NULL) {
 378                 giterr_clear();
 379                 return GIT_ITEROVER;
 380         }
 381
 382         /* first figure out what the merge bases are */
 383         if (git_merge__bases_many(&bases, walk, walk->one, &walk->twos) < 0)
 384                 return -1;
 385
 386         git_commit_list_free(&bases);
 387         if (process_commit(walk, walk->one, walk->one->uninteresting) < 0)
 388                 return -1;
 389
 390         git_vector_foreach(&walk->twos, i, two) {
 391                 if (process_commit(walk, two, two->uninteresting) < 0)
 392                         return -1;
 393         }
 394
 395         if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
 396                 unsigned short i;
 397
 398                 while ((error = walk->get_next(&next, walk)) == 0) {
 399                         for (i = 0; i < next->out_degree; ++i) {
 400                                 git_commit_list_node *parent = next->parents[i];
 401                                 parent->in_degree++;
 402                         }
 403
 404                         if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
 405                                 return -1;
 406                 }
 407
 408                 if (error != GIT_ITEROVER)
 409                         return error;
 410
 411                 walk->get_next = &revwalk_next_toposort;
 412         }
 413
 414         if (walk->sorting & GIT_SORT_REVERSE) {
 415
 416                 while ((error = walk->get_next(&next, walk)) == 0)
 417                         if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
 418                                 return -1;
 419
 420                 if (error != GIT_ITEROVER)
 421                         return error;
 422
 423                 walk->get_next = &revwalk_next_reverse;
 424         }
 425
 426         walk->walking = 1;
 427         return 0;
 428 }
 429
 430
 431 int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 432 {
 433         git_revwalk *walk;
 434
 435         walk = git__malloc(sizeof(git_revwalk));
 436         GITERR_CHECK_ALLOC(walk);
 437
 438         memset(walk, 0x0, sizeof(git_revwalk));
 439
 440         walk->commits = git_oidmap_alloc();
 441         GITERR_CHECK_ALLOC(walk->commits);
 442
 443         if (git_pqueue_init(&walk->iterator_time, 8, git_commit_list_time_cmp) < 0 ||
 444                 git_vector_init(&walk->twos, 4, NULL) < 0 ||
 445                 git_pool_init(&walk->commit_pool, 1,
 446                         git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
 447                 return -1;
 448
 449         walk->get_next = &revwalk_next_unsorted;
 450         walk->enqueue = &revwalk_enqueue_unsorted;
 451
 452         walk->repo = repo;
 453
 454         if (git_repository_odb(&walk->odb, repo) < 0) {
 455                 git_revwalk_free(walk);
 456                 return -1;
 457         }
 458
 459         *revwalk_out = walk;
 460         return 0;
 461 }
 462
 463 void git_revwalk_free(git_revwalk *walk)
 464 {
 465         if (walk == NULL)
 466                 return;
 467
 468         git_revwalk_reset(walk);
 469         git_odb_free(walk->odb);
 470
 471         git_oidmap_free(walk->commits);
 472         git_pool_clear(&walk->commit_pool);
 473         git_pqueue_free(&walk->iterator_time);
 474         git_vector_free(&walk->twos);
 475         git__free(walk);
 476 }
 477
 478 git_repository *git_revwalk_repository(git_revwalk *walk)
 479 {
 480         assert(walk);
 481         return walk->repo;
 482 }
 483
 484 void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
 485 {
 486         assert(walk);
 487
 488         if (walk->walking)
 489                 git_revwalk_reset(walk);
 490
 491         walk->sorting = sort_mode;
 492
 493         if (walk->sorting & GIT_SORT_TIME) {
 494                 walk->get_next = &revwalk_next_timesort;
 495                 walk->enqueue = &revwalk_enqueue_timesort;
 496         } else {
 497                 walk->get_next = &revwalk_next_unsorted;
 498                 walk->enqueue = &revwalk_enqueue_unsorted;
 499         }
 500 }
 501
 502 void git_revwalk_simplify_first_parent(git_revwalk *walk)
 503 {
 504         walk->first_parent = 1;
 505 }
 506
 507 int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 508 {
 509         int error;
 510         git_commit_list_node *next;
 511
 512         assert(walk && oid);
 513
 514         if (!walk->walking) {
 515                 if ((error = prepare_walk(walk)) < 0)
 516                         return error;
 517         }
 518
 519         error = walk->get_next(&next, walk);
 520
 521         if (error == GIT_ITEROVER) {
 522                 git_revwalk_reset(walk);
 523                 giterr_clear();
 524                 return GIT_ITEROVER;
 525         }
 526
 527         if (!error)
 528                 git_oid_cpy(oid, &next->oid);
 529
 530         return error;
 531 }
 532
 533 void git_revwalk_reset(git_revwalk *walk)
 534 {
 535         git_commit_list_node *commit;
 536
 537         assert(walk);
 538
 539         kh_foreach_value(walk->commits, commit, {
 540                 commit->seen = 0;
 541                 commit->in_degree = 0;
 542                 commit->topo_delay = 0;
 543                 commit->uninteresting = 0;
 544                 });
 545
 546         git_pqueue_clear(&walk->iterator_time);
 547         git_commit_list_free(&walk->iterator_topo);
 548         git_commit_list_free(&walk->iterator_rand);
 549         git_commit_list_free(&walk->iterator_reverse);
 550         walk->walking = 0;
 551
 552         walk->one = NULL;
 553         git_vector_clear(&walk->twos);
 554 }
 555