src/revwalk.c

   1 /*
   2  * Copyright (C) 2009-2012 the libgit2 contributors
   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 "hashtable.h"
  12 #include "pqueue.h"
  13
  14 #include "git2/revwalk.h"
  15
  16 typedef struct commit_object {
  17         git_oid oid;
  18         uint32_t time;
  19         unsigned int seen:1,
  20                          uninteresting:1,
  21                          topo_delay:1,
  22                          parsed:1;
  23
  24         unsigned short in_degree;
  25         unsigned short out_degree;
  26
  27         struct commit_object **parents;
  28 } commit_object;
  29
  30 typedef struct commit_list {
  31         commit_object *item;
  32         struct commit_list *next;
  33 } commit_list;
  34
  35 struct git_revwalk {
  36         git_repository *repo;
  37         git_odb *odb;
  38
  39         git_hashtable *commits;
  40
  41         commit_list *iterator_topo;
  42         commit_list *iterator_rand;
  43         commit_list *iterator_reverse;
  44         git_pqueue iterator_time;
  45
  46         int (*get_next)(commit_object **, git_revwalk *);
  47         int (*enqueue)(git_revwalk *, commit_object *);
  48
  49         git_vector memory_alloc;
  50         size_t chunk_size;
  51
  52         unsigned walking:1;
  53         unsigned int sorting;
  54 };
  55
  56 static commit_list *commit_list_insert(commit_object *item, commit_list **list_p)
  57 {
  58         commit_list *new_list = git__malloc(sizeof(commit_list));
  59         new_list->item = item;
  60         new_list->next = *list_p;
  61         *list_p = new_list;
  62         return new_list;
  63 }
  64
  65 static void commit_list_free(commit_list **list_p)
  66 {
  67         commit_list *list = *list_p;
  68
  69         while (list) {
  70                 commit_list *temp = list;
  71                 list = temp->next;
  72                 git__free(temp);
  73         }
  74
  75         *list_p = NULL;
  76 }
  77
  78 static commit_object *commit_list_pop(commit_list **stack)
  79 {
  80         commit_list *top = *stack;
  81         commit_object *item = top ? top->item : NULL;
  82
  83         if (top) {
  84                 *stack = top->next;
  85                 git__free(top);
  86         }
  87         return item;
  88 }
  89
  90 static int commit_time_cmp(void *a, void *b)
  91 {
  92         commit_object *commit_a = (commit_object *)a;
  93         commit_object *commit_b = (commit_object *)b;
  94
  95         return (commit_a->time < commit_b->time);
  96 }
  97
  98 static uint32_t object_table_hash(const void *key, int hash_id)
  99 {
 100         uint32_t r;
 101         const git_oid *id = key;
 102
 103         memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));
 104         return r;
 105 }
 106
 107 #define COMMITS_PER_CHUNK 128
 108 #define CHUNK_STEP 64
 109 #define PARENTS_PER_COMMIT ((CHUNK_STEP - sizeof(commit_object)) / sizeof(commit_object *))
 110
 111 static int alloc_chunk(git_revwalk *walk)
 112 {
 113         void *chunk;
 114
 115         chunk = git__calloc(COMMITS_PER_CHUNK, CHUNK_STEP);
 116         if (chunk == NULL)
 117                 return GIT_ENOMEM;
 118
 119         walk->chunk_size = 0;
 120         return git_vector_insert(&walk->memory_alloc, chunk);
 121 }
 122
 123 static commit_object *alloc_commit(git_revwalk *walk)
 124 {
 125         unsigned char *chunk;
 126
 127         if (walk->chunk_size == COMMITS_PER_CHUNK)
 128                 alloc_chunk(walk);
 129
 130         chunk = git_vector_get(&walk->memory_alloc, walk->memory_alloc.length - 1);
 131         chunk += (walk->chunk_size * CHUNK_STEP);
 132         walk->chunk_size++;
 133
 134         return (commit_object *)chunk;
 135 }
 136
 137 static commit_object **alloc_parents(commit_object *commit, size_t n_parents)
 138 {
 139         if (n_parents <= PARENTS_PER_COMMIT)
 140                 return (commit_object **)((unsigned char *)commit + sizeof(commit_object));
 141
 142         return git__malloc(n_parents * sizeof(commit_object *));
 143 }
 144
 145
 146 static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
 147 {
 148         commit_object *commit;
 149
 150         if ((commit = git_hashtable_lookup(walk->commits, oid)) != NULL)
 151                 return commit;
 152
 153         commit = alloc_commit(walk);
 154         if (commit == NULL)
 155                 return NULL;
 156
 157         git_oid_cpy(&commit->oid, oid);
 158
 159         if (git_hashtable_insert(walk->commits, &commit->oid, commit) < GIT_SUCCESS) {
 160                 git__free(commit);
 161                 return NULL;
 162         }
 163
 164         return commit;
 165 }
 166
 167 static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawobj *raw)
 168 {
 169         const int parent_len = strlen("parent ") + GIT_OID_HEXSZ + 1;
 170
 171         unsigned char *buffer = raw->data;
 172         unsigned char *buffer_end = buffer + raw->len;
 173         unsigned char *parents_start;
 174
 175         int i, parents = 0;
 176         int commit_time;
 177
 178         buffer += strlen("tree ") + GIT_OID_HEXSZ + 1;
 179
 180         parents_start = buffer;
 181         while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", strlen("parent ")) == 0) {
 182                 parents++;
 183                 buffer += parent_len;
 184         }
 185
 186         commit->parents = alloc_parents(commit, parents);
 187         if (commit->parents == NULL)
 188                 return GIT_ENOMEM;
 189
 190         buffer = parents_start;
 191         for (i = 0; i < parents; ++i) {
 192                 git_oid oid;
 193
 194                 if (git_oid_fromstr(&oid, (char *)buffer + strlen("parent ")) < GIT_SUCCESS)
 195                         return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Parent object is corrupted");
 196
 197                 commit->parents[i] = commit_lookup(walk, &oid);
 198                 if (commit->parents[i] == NULL)
 199                         return GIT_ENOMEM;
 200
 201                 buffer += parent_len;
 202         }
 203
 204         commit->out_degree = (unsigned short)parents;
 205
 206         if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
 207                 return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Object is corrupted");
 208
 209         buffer = memchr(buffer, '>', buffer_end - buffer);
 210         if (buffer == NULL)
 211                 return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Can't find author");
 212
 213         if (git__strtol32(&commit_time, (char *)buffer + 2, NULL, 10) < GIT_SUCCESS)
 214                 return git__throw(GIT_EOBJCORRUPTED, "Failed to parse commit. Can't parse commit time");
 215
 216         commit->time = (time_t)commit_time;
 217         commit->parsed = 1;
 218         return GIT_SUCCESS;
 219 }
 220
 221 static int commit_parse(git_revwalk *walk, commit_object *commit)
 222 {
 223         git_odb_object *obj;
 224         int error;
 225
 226         if (commit->parsed)
 227                 return GIT_SUCCESS;
 228
 229         if ((error = git_odb_read(&obj, walk->odb, &commit->oid)) < GIT_SUCCESS)
 230                 return git__rethrow(error, "Failed to parse commit. Can't read object");
 231
 232         if (obj->raw.type != GIT_OBJ_COMMIT) {
 233                 git_odb_object_free(obj);
 234                 return git__throw(GIT_EOBJTYPE, "Failed to parse commit. Object is no commit object");
 235         }
 236
 237         error = commit_quick_parse(walk, commit, &obj->raw);
 238         git_odb_object_free(obj);
 239         return error == GIT_SUCCESS ? GIT_SUCCESS : git__rethrow(error, "Failed to parse commit");
 240 }
 241
 242 static void mark_uninteresting(commit_object *commit)
 243 {
 244         unsigned short i;
 245         assert(commit);
 246
 247         commit->uninteresting = 1;
 248
 249         for (i = 0; i < commit->out_degree; ++i)
 250                 if (!commit->parents[i]->uninteresting)
 251                         mark_uninteresting(commit->parents[i]);
 252 }
 253
 254 static int process_commit(git_revwalk *walk, commit_object *commit, int hide)
 255 {
 256         int error;
 257
 258         if (hide)
 259                 mark_uninteresting(commit);
 260
 261         if (commit->seen)
 262                 return GIT_SUCCESS;
 263
 264         commit->seen = 1;
 265
 266         if ((error = commit_parse(walk, commit)) < GIT_SUCCESS)
 267                         return git__rethrow(error, "Failed to process commit");
 268
 269         return walk->enqueue(walk, commit);
 270 }
 271
 272 static int process_commit_parents(git_revwalk *walk, commit_object *commit)
 273 {
 274         unsigned short i;
 275         int error = GIT_SUCCESS;
 276
 277         for (i = 0; i < commit->out_degree && error == GIT_SUCCESS; ++i) {
 278                 error = process_commit(walk, commit->parents[i], commit->uninteresting);
 279         }
 280
 281         return error == GIT_SUCCESS ? GIT_SUCCESS : git__rethrow(error, "Failed to process commit parents");
 282 }
 283
 284 static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
 285 {
 286         commit_object *commit;
 287
 288         commit = commit_lookup(walk, oid);
 289         if (commit == NULL)
 290                 return git__throw(GIT_ENOTFOUND, "Failed to push commit. Object not found");
 291
 292         return process_commit(walk, commit, uninteresting);
 293 }
 294
 295 int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
 296 {
 297         assert(walk && oid);
 298         return push_commit(walk, oid, 0);
 299 }
 300
 301 int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
 302 {
 303         assert(walk && oid);
 304         return push_commit(walk, oid, 1);
 305 }
 306
 307 static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit)
 308 {
 309         return git_pqueue_insert(&walk->iterator_time, commit);
 310 }
 311
 312 static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit)
 313 {
 314         return commit_list_insert(commit, &walk->iterator_rand) ? GIT_SUCCESS : GIT_ENOMEM;
 315 }
 316
 317 static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)
 318 {
 319         int error;
 320         commit_object *next;
 321
 322         while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
 323                 if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)
 324                         return git__rethrow(error, "Failed to load next revision");
 325
 326                 if (!next->uninteresting) {
 327                         *object_out = next;
 328                         return GIT_SUCCESS;
 329                 }
 330         }
 331
 332         return git__throw(GIT_EREVWALKOVER, "Failed to load next revision");
 333 }
 334
 335 static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)
 336 {
 337         int error;
 338         commit_object *next;
 339
 340         while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) {
 341                 if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)
 342                         return git__rethrow(error, "Failed to load next revision");
 343
 344                 if (!next->uninteresting) {
 345                         *object_out = next;
 346                         return GIT_SUCCESS;
 347                 }
 348         }
 349
 350         return git__throw(GIT_EREVWALKOVER, "Failed to load next revision");
 351 }
 352
 353 static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
 354 {
 355         commit_object *next;
 356         unsigned short i;
 357
 358         for (;;) {
 359                 next = commit_list_pop(&walk->iterator_topo);
 360                 if (next == NULL)
 361                         return git__throw(GIT_EREVWALKOVER, "Failed to load next revision");
 362
 363                 if (next->in_degree > 0) {
 364                         next->topo_delay = 1;
 365                         continue;
 366                 }
 367
 368                 for (i = 0; i < next->out_degree; ++i) {
 369                         commit_object *parent = next->parents[i];
 370
 371                         if (--parent->in_degree == 0 && parent->topo_delay) {
 372                                 parent->topo_delay = 0;
 373                                 commit_list_insert(parent, &walk->iterator_topo);
 374                         }
 375                 }
 376
 377                 *object_out = next;
 378                 return GIT_SUCCESS;
 379         }
 380 }
 381
 382 static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
 383 {
 384         *object_out = commit_list_pop(&walk->iterator_reverse);
 385         return *object_out ? GIT_SUCCESS : GIT_EREVWALKOVER;
 386 }
 387
 388
 389 static int prepare_walk(git_revwalk *walk)
 390 {
 391         int error;
 392         commit_object *next;
 393
 394         if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
 395                 unsigned short i;
 396
 397                 while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS) {
 398                         for (i = 0; i < next->out_degree; ++i) {
 399                                 commit_object *parent = next->parents[i];
 400                                 parent->in_degree++;
 401                         }
 402
 403                         commit_list_insert(next, &walk->iterator_topo);
 404                 }
 405
 406                 if (error != GIT_EREVWALKOVER)
 407                         return git__rethrow(error, "Failed to prepare revision walk");
 408
 409                 walk->get_next = &revwalk_next_toposort;
 410         }
 411
 412         if (walk->sorting & GIT_SORT_REVERSE) {
 413
 414                 while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS)
 415                         commit_list_insert(next, &walk->iterator_reverse);
 416
 417                 if (error != GIT_EREVWALKOVER)
 418                         return git__rethrow(error, "Failed to prepare revision walk");
 419
 420                 walk->get_next = &revwalk_next_reverse;
 421         }
 422
 423         walk->walking = 1;
 424         return GIT_SUCCESS;
 425 }
 426
 427
 428
 429
 430
 431 int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
 432 {
 433         int error;
 434         git_revwalk *walk;
 435
 436         walk = git__malloc(sizeof(git_revwalk));
 437         if (walk == NULL)
 438                 return GIT_ENOMEM;
 439
 440         memset(walk, 0x0, sizeof(git_revwalk));
 441
 442         walk->commits = git_hashtable_alloc(64,
 443                         object_table_hash,
 444                         (git_hash_keyeq_ptr)git_oid_cmp);
 445
 446         if (walk->commits == NULL) {
 447                 git__free(walk);
 448                 return GIT_ENOMEM;
 449         }
 450
 451         git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp);
 452         git_vector_init(&walk->memory_alloc, 8, NULL);
 453         alloc_chunk(walk);
 454
 455         walk->get_next = &revwalk_next_unsorted;
 456         walk->enqueue = &revwalk_enqueue_unsorted;
 457
 458         walk->repo = repo;
 459
 460         error = git_repository_odb(&walk->odb, repo);
 461         if (error < GIT_SUCCESS) {
 462                 git_revwalk_free(walk);
 463                 return error;
 464         }
 465
 466         *revwalk_out = walk;
 467         return GIT_SUCCESS;
 468 }
 469
 470 void git_revwalk_free(git_revwalk *walk)
 471 {
 472         unsigned int i;
 473         const void *GIT_UNUSED(_unused);
 474         commit_object *commit;
 475
 476         if (walk == NULL)
 477                 return;
 478
 479         git_revwalk_reset(walk);
 480         git_odb_free(walk->odb);
 481
 482         /* if the parent has more than PARENTS_PER_COMMIT parents,
 483          * we had to allocate a separate array for those parents.
 484          * make sure it's being free'd */
 485         GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit, {
 486                 if (commit->out_degree > PARENTS_PER_COMMIT)
 487                         git__free(commit->parents);
 488         });
 489
 490         git_hashtable_free(walk->commits);
 491         git_pqueue_free(&walk->iterator_time);
 492
 493         for (i = 0; i < walk->memory_alloc.length; ++i)
 494                 git__free(git_vector_get(&walk->memory_alloc, i));
 495
 496         git_vector_free(&walk->memory_alloc);
 497         git__free(walk);
 498 }
 499
 500 git_repository *git_revwalk_repository(git_revwalk *walk)
 501 {
 502         assert(walk);
 503         return walk->repo;
 504 }
 505
 506 void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
 507 {
 508         assert(walk);
 509
 510         if (walk->walking)
 511                 git_revwalk_reset(walk);
 512
 513         walk->sorting = sort_mode;
 514
 515         if (walk->sorting & GIT_SORT_TIME) {
 516                 walk->get_next = &revwalk_next_timesort;
 517                 walk->enqueue = &revwalk_enqueue_timesort;
 518         } else {
 519                 walk->get_next = &revwalk_next_unsorted;
 520                 walk->enqueue = &revwalk_enqueue_unsorted;
 521         }
 522 }
 523
 524 int git_revwalk_next(git_oid *oid, git_revwalk *walk)
 525 {
 526         int error;
 527         commit_object *next;
 528
 529         assert(walk && oid);
 530
 531         if (!walk->walking) {
 532                 if ((error = prepare_walk(walk)) < GIT_SUCCESS)
 533                         return git__rethrow(error, "Failed to load next revision");
 534         }
 535
 536         error = walk->get_next(&next, walk);
 537
 538         if (error == GIT_EREVWALKOVER) {
 539                 git_revwalk_reset(walk);
 540                 return GIT_EREVWALKOVER;
 541         }
 542
 543         if (error < GIT_SUCCESS)
 544                 return git__rethrow(error, "Failed to load next revision");
 545
 546         git_oid_cpy(oid, &next->oid);
 547         return GIT_SUCCESS;
 548 }
 549
 550 void git_revwalk_reset(git_revwalk *walk)
 551 {
 552         const void *GIT_UNUSED(_unused);
 553         commit_object *commit;
 554
 555         assert(walk);
 556
 557         GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit,
 558                 commit->seen = 0;
 559                 commit->in_degree = 0;
 560                 commit->topo_delay = 0;
 561                 commit->uninteresting = 0;
 562         );
 563
 564         git_pqueue_clear(&walk->iterator_time);
 565         commit_list_free(&walk->iterator_topo);
 566         commit_list_free(&walk->iterator_rand);
 567         commit_list_free(&walk->iterator_reverse);
 568         walk->walking = 0;
 569 }
 570