revwalk.c 17.2 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3
 *
Vicent Marti committed
4 5
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
6 7
 */

8 9
#include "revwalk.h"

10
#include "commit.h"
Vicent Marti committed
11
#include "odb.h"
12
#include "pool.h"
13

14
#include "git2/revparse.h"
15
#include "merge.h"
16
#include "vector.h"
17

18 19
static int get_revision(git_commit_list_node **out, git_revwalk *walk, git_commit_list **list);

20 21
git_commit_list_node *git_revwalk__commit_lookup(
	git_revwalk *walk, const git_oid *oid)
22
{
23
	git_commit_list_node *commit;
24
	size_t pos;
25
	int ret;
26

27
	/* lookup and reserve space if not already present */
28
	pos = git_oidmap_lookup_index(walk->commits, oid);
29
	if (git_oidmap_valid_index(walk->commits, pos))
30
		return git_oidmap_value_at(walk->commits, pos);
31

32
	commit = git_commit_list_alloc_node(walk);
33 34
	if (commit == NULL)
		return NULL;
35

36
	git_oid_cpy(&commit->oid, oid);
37

38
	pos = git_oidmap_put(walk->commits, &commit->oid, &ret);
39
	assert(ret != 0);
40
	git_oidmap_set_value_at(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_OBJECT_ANY)) < 0)
54
		return error;
55

56
	error = git_object_peel(&obj, oobj, GIT_OBJECT_COMMIT);
57
	git_object_free(oobj);
58

59
	if (error == GIT_ENOTFOUND || error == GIT_EINVALIDSPEC || error == GIT_EPEEL) {
60 61 62 63
		/* If this comes from e.g. push_glob("tags"), ignore this */
		if (from_glob)
			return 0;

64
		git_error_set(GIT_ERROR_INVALID, "object is not a committish");
65 66
		return -1;
	}
67 68 69 70 71
	if (error < 0)
		return error;

	git_oid_cpy(&commit_id, git_object_id(obj));
	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 78 79 80
	/* A previous hide already told us we don't want this commit  */
	if (commit->uninteresting)
		return 0;

81 82
	if (uninteresting) {
		walk->limited = 1;
83
		walk->did_hide = 1;
84
	} else {
85
		walk->did_push = 1;
86
	}
87

88
	commit->uninteresting = uninteresting;
89 90
	list = walk->user_input;
	if (git_commit_list_insert(commit, &list) == NULL) {
91
		git_error_set_oom();
92
		return -1;
93 94
	}

95 96
	walk->user_input = list;

97
	return 0;
98 99
}

100 101 102
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
103
	return push_commit(walk, oid, 0, false);
104
}
105

106

107 108 109
int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
110
	return push_commit(walk, oid, 1, false);
111
}
112

113
static int push_ref(git_revwalk *walk, const char *refname, int hide, int from_glob)
114
{
115
	git_oid oid;
116

117
	if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
118 119
		return -1;

120
	return push_commit(walk, &oid, hide, from_glob);
121 122
}

123 124
static int push_glob(git_revwalk *walk, const char *glob, int hide)
{
125
	int error = 0;
126
	git_buf buf = GIT_BUF_INIT;
127 128
	git_reference *ref;
	git_reference_iterator *iter;
129
	size_t wildcard;
130 131 132 133

	assert(walk && glob);

	/* refs/ is implied if not given in the glob */
134 135 136
	if (git__prefixcmp(glob, GIT_REFS_DIR) != 0)
		git_buf_joinpath(&buf, GIT_REFS_DIR, glob);
	else
137
		git_buf_puts(&buf, glob);
138
	GIT_ERROR_CHECK_ALLOC_BUF(&buf);
139 140

	/* If no '?', '*' or '[' exist, we append '/ *' to the glob */
141 142 143
	wildcard = strcspn(glob, "?*[");
	if (!glob[wildcard])
		git_buf_put(&buf, "/*", 2);
144

145 146
	if ((error = git_reference_iterator_glob_new(&iter, walk->repo, buf.ptr)) < 0)
		goto out;
147

148 149 150 151 152 153 154
	while ((error = git_reference_next(&ref, iter)) == 0) {
		error = push_ref(walk, git_reference_name(ref), hide, true);
		git_reference_free(ref);
		if (error < 0)
			break;
	}
	git_reference_iterator_free(iter);
155

156 157 158
	if (error == GIT_ITEROVER)
		error = 0;
out:
159
	git_buf_dispose(&buf);
160
	return error;
161 162 163 164 165 166 167 168 169 170 171 172 173 174
}

int git_revwalk_push_glob(git_revwalk *walk, const char *glob)
{
	assert(walk && glob);
	return push_glob(walk, glob, 0);
}

int git_revwalk_hide_glob(git_revwalk *walk, const char *glob)
{
	assert(walk && glob);
	return push_glob(walk, glob, 1);
}

175 176 177
int git_revwalk_push_head(git_revwalk *walk)
{
	assert(walk);
178
	return push_ref(walk, GIT_HEAD_FILE, 0, false);
179 180 181 182 183
}

int git_revwalk_hide_head(git_revwalk *walk)
{
	assert(walk);
184
	return push_ref(walk, GIT_HEAD_FILE, 1, false);
185 186 187 188 189
}

int git_revwalk_push_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
190
	return push_ref(walk, refname, 0, false);
191 192
}

193 194
int git_revwalk_push_range(git_revwalk *walk, const char *range)
{
195
	git_revspec revspec;
196 197
	int error = 0;

198
	if ((error = git_revparse(&revspec, walk->repo, range)))
199
		return error;
Vicent Marti committed
200

201
	if (revspec.flags & GIT_REVPARSE_MERGE_BASE) {
202
		/* TODO: support "<commit>...<commit>" */
203
		git_error_set(GIT_ERROR_INVALID, "symmetric differences not implemented in revwalk");
204 205 206
		return GIT_EINVALIDSPEC;
	}

207
	if ((error = push_commit(walk, git_object_id(revspec.from), 1, false)))
208 209
		goto out;

210
	error = push_commit(walk, git_object_id(revspec.to), 0, false);
Vicent Marti committed
211 212

out:
213 214
	git_object_free(revspec.from);
	git_object_free(revspec.to);
215 216 217
	return error;
}

218 219 220
int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
221
	return push_ref(walk, refname, 1, false);
222 223
}

224
static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
225
{
226 227
	return git_pqueue_insert(&walk->iterator_time, commit);
}
228

229
static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
230
{
231
	return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
232
}
233

234
static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
235
{
236
	git_commit_list_node *next;
237

238 239 240 241 242 243
	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
		/* Some commits might become uninteresting after being added to the list */
		if (!next->uninteresting) {
			*object_out = next;
			return 0;
		}
244
	}
245

246
	git_error_clear();
Russell Belfer committed
247
	return GIT_ITEROVER;
248 249
}

250
static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
251
{
252
	int error;
253
	git_commit_list_node *next;
254

255
	while (!(error = get_revision(&next, walk, &walk->iterator_rand))) {
256 257 258 259 260
		/* Some commits might become uninteresting after being added to the list */
		if (!next->uninteresting) {
			*object_out = next;
			return 0;
		}
261
	}
262

263
	return error;
264
}
265

266
static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
267
{
268
	int error;
269
	git_commit_list_node *next;
270

271
	while (!(error = get_revision(&next, walk, &walk->iterator_topo))) {
272 273 274 275 276
		/* Some commits might become uninteresting after being added to the list */
		if (!next->uninteresting) {
			*object_out = next;
			return 0;
		}
277
	}
278

279
	return error;
280 281
}

282
static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
283
{
284
	*object_out = git_commit_list_pop(&walk->iterator_reverse);
Russell Belfer committed
285
	return *object_out ? 0 : GIT_ITEROVER;
286
}
287

288
static void mark_parents_uninteresting(git_commit_list_node *commit)
289
{
290 291
	unsigned short i;
	git_commit_list *parents = NULL;
292

293 294
	for (i = 0; i < commit->out_degree; i++)
		git_commit_list_insert(commit->parents[i], &parents);
295

296 297

	while (parents) {
298
		commit = git_commit_list_pop(&parents);
299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317

		while (commit) {
			if (commit->uninteresting)
				break;

			commit->uninteresting = 1;
			/*
			 * If we've reached this commit some other way
			 * already, we need to mark its parents uninteresting
			 * as well.
			 */
			if (!commit->parents)
				break;

			for (i = 0; i < commit->out_degree; i++)
				git_commit_list_insert(commit->parents[i], &parents);
			commit = commit->parents[0];
		}
	}
318 319
}

320
static int add_parents_to_list(git_revwalk *walk, git_commit_list_node *commit, git_commit_list **list)
321 322
{
	unsigned short i;
323
	int error;
324

325 326
	if (commit->added)
		return 0;
327

328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354
	commit->added = 1;

	/*
	 * Go full on in the uninteresting case as we want to include
	 * as many of these as we can.
	 *
	 * Usually we haven't parsed the parent of a parent, but if we
	 * have it we reached it via other means so we want to mark
	 * its parents recursively too.
	 */
	if (commit->uninteresting) {
		for (i = 0; i < commit->out_degree; i++) {
			git_commit_list_node *p = commit->parents[i];
			p->uninteresting = 1;

			/* git does it gently here, but we don't like missing objects */
			if ((error = git_commit_list_parse(walk, p)) < 0)
				return error;

			if (p->parents)
				mark_parents_uninteresting(p);

			p->seen = 1;
			git_commit_list_insert_by_date(p, list);
		}

		return 0;
355 356
	}

357 358 359 360 361 362 363
	/*
	 * Now on to what we do if the commit is indeed
	 * interesting. Here we do want things like first-parent take
	 * effect as this is what we'll be showing.
	 */
	for (i = 0; i < commit->out_degree; i++) {
		git_commit_list_node *p = commit->parents[i];
364

365 366
		if ((error = git_commit_list_parse(walk, p)) < 0)
			return error;
367

368
		if (walk->hide_cb && walk->hide_cb(&p->oid, walk->hide_cb_payload))
369
			continue;
370

371 372 373 374 375 376 377 378 379 380
		if (!p->seen) {
			p->seen = 1;
			git_commit_list_insert_by_date(p, list);
		}

		if (walk->first_parent)
			break;
	}
	return 0;
}
381

382 383 384 385 386 387 388 389 390
/* How many unintersting commits we want to look at after we run out of interesting ones */
#define SLOP 5

static int still_interesting(git_commit_list *list, int64_t time, int slop)
{
	/* The empty list is pretty boring */
	if (!list)
		return 0;

391 392 393 394 395 396 397
	/*
	 * If the destination list has commits with an earlier date than our
	 * source, we want to reset the slop counter as we're not done.
	 */
	if (time <= list->item->time)
		return SLOP;

398 399
	for (; list; list = list->next) {
		/*
400
		 * If the destination list still contains interesting commits we
401 402 403 404 405
		 * want to continue looking.
		 */
		if (!list->item->uninteresting || list->item->time > time)
			return SLOP;
	}
406 407 408 409 410 411 412 413

	/* Everything's uninteresting, reduce the count */
	return slop - 1;
}

static int limit_list(git_commit_list **out, git_revwalk *walk, git_commit_list *commits)
{
	int error, slop = SLOP;
414
	int64_t time = INT64_MAX;
415 416 417 418 419 420 421 422 423 424 425 426 427 428 429
	git_commit_list *list = commits;
	git_commit_list *newlist = NULL;
	git_commit_list **p = &newlist;

	while (list) {
		git_commit_list_node *commit = git_commit_list_pop(&list);

		if ((error = add_parents_to_list(walk, commit, &list)) < 0)
			return error;

		if (commit->uninteresting) {
			mark_parents_uninteresting(commit);

			slop = still_interesting(list, time, slop);
			if (slop)
430 431
				continue;

432
			break;
433
		}
434

435 436
		if (walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload))
			continue;
437 438 439

		time = commit->time;
		p = &git_commit_list_insert(commit, p)->next;
440 441
	}

442
	git_commit_list_free(&list);
443 444
	*out = newlist;
	return 0;
445 446
}

447 448 449 450 451
static int get_revision(git_commit_list_node **out, git_revwalk *walk, git_commit_list **list)
{
	int error;
	git_commit_list_node *commit;

452 453
	commit = git_commit_list_pop(list);
	if (!commit) {
454
		git_error_clear();
455 456 457 458 459 460 461 462 463
		return GIT_ITEROVER;
	}

	/*
	 * If we did not run limit_list and we must add parents to the
	 * list ourselves.
	 */
	if (!walk->limited) {
		if ((error = add_parents_to_list(walk, commit, list)) < 0)
464
			return error;
465 466 467 468
	}

	*out = commit;
	return 0;
469 470
}

471
static int sort_in_topological_order(git_commit_list **out, git_revwalk *walk, git_commit_list *list)
472
{
473
	git_commit_list *ll = NULL, *newlist, **pptr;
474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491
	git_commit_list_node *next;
	git_pqueue queue;
	git_vector_cmp queue_cmp = NULL;
	unsigned short i;
	int error;

	if (walk->sorting & GIT_SORT_TIME)
		queue_cmp = git_commit_list_time_cmp;

	if ((error = git_pqueue_init(&queue, 0, 8, queue_cmp)))
		return error;

	/*
	 * Start by resetting the in-degree to 1 for the commits in
	 * our list. We want to go through this list again, so we
	 * store it in the commit list as we extract it from the lower
	 * machinery.
	 */
492 493
	for (ll = list; ll; ll = ll->next) {
		ll->item->in_degree = 1;
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556
	}

	/*
	 * Count up how many children each commit has. We limit
	 * ourselves to those commits in the original list (in-degree
	 * of 1) avoiding setting it for any parent that was hidden.
	 */
	for(ll = list; ll; ll = ll->next) {
		for (i = 0; i < ll->item->out_degree; ++i) {
			git_commit_list_node *parent = ll->item->parents[i];
			if (parent->in_degree)
				parent->in_degree++;
		}
	}

	/*
	 * Now we find the tips i.e. those not reachable from any other node
	 * i.e. those which still have an in-degree of 1.
	 */
	for(ll = list; ll; ll = ll->next) {
		if (ll->item->in_degree == 1) {
			if ((error = git_pqueue_insert(&queue, ll->item)))
				goto cleanup;
		}
	}

	/*
	 * We need to output the tips in the order that they came out of the
	 * traversal, so if we're not doing time-sorting, we need to reverse the
	 * pqueue in order to get them to come out as we inserted them.
	 */
	if ((walk->sorting & GIT_SORT_TIME) == 0)
		git_pqueue_reverse(&queue);


	pptr = &newlist;
	newlist = NULL;
	while ((next = git_pqueue_pop(&queue)) != NULL) {
		for (i = 0; i < next->out_degree; ++i) {
			git_commit_list_node *parent = next->parents[i];
			if (parent->in_degree == 0)
				continue;

			if (--parent->in_degree == 1) {
				if ((error = git_pqueue_insert(&queue, parent)))
					goto cleanup;
			}
		}

		/* All the children of 'item' have been emitted (since we got to it via the priority queue) */
		next->in_degree = 0;

		pptr = &git_commit_list_insert(next, pptr)->next;
	}

	*out = newlist;
	error = 0;

cleanup:
	git_pqueue_free(&queue);
	return error;
}

557 558
static int prepare_walk(git_revwalk *walk)
{
559
	int error = 0;
560
	git_commit_list *list, *commits = NULL;
561 562
	git_commit_list_node *next;

563 564
	/* If there were no pushes, we know that the walk is already over */
	if (!walk->did_push) {
565
		git_error_clear();
566 567 568
		return GIT_ITEROVER;
	}

569 570 571 572 573 574 575 576 577 578 579 580 581 582
	for (list = walk->user_input; list; list = list->next) {
		git_commit_list_node *commit = list->item;
		if ((error = git_commit_list_parse(walk, commit)) < 0)
			return error;

		if (commit->uninteresting)
			mark_parents_uninteresting(commit);

		if (!commit->seen) {
			commit->seen = 1;
			git_commit_list_insert(commit, &commits);
		}
	}

583
	if (walk->limited && (error = limit_list(&commits, walk, commits)) < 0)
584
		return error;
585

586
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
587 588 589 590
		error = sort_in_topological_order(&walk->iterator_topo, walk, commits);
		git_commit_list_free(&commits);

		if (error < 0)
591
			return error;
592

593
		walk->get_next = &revwalk_next_toposort;
594 595 596 597 598 599 600 601 602 603 604
	} else if (walk->sorting & GIT_SORT_TIME) {
		for (list = commits; list && !error; list = list->next)
			error = walk->enqueue(walk, list->item);

		git_commit_list_free(&commits);

		if (error < 0)
			return error;
	} else {
		walk->iterator_rand = commits;
		walk->get_next = revwalk_next_unsorted;
605
	}
606

607
	if (walk->sorting & GIT_SORT_REVERSE) {
608

609
		while ((error = walk->get_next(&next, walk)) == 0)
610
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
611
				return -1;
612

Russell Belfer committed
613
		if (error != GIT_ITEROVER)
614
			return error;
615

616 617
		walk->get_next = &revwalk_next_reverse;
	}
618

619
	walk->walking = 1;
620
	return 0;
621
}
622 623


624 625
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
626
	git_revwalk *walk = git__calloc(1, sizeof(git_revwalk));
627
	GIT_ERROR_CHECK_ALLOC(walk);
628

629
	walk->commits = git_oidmap_alloc();
630
	GIT_ERROR_CHECK_ALLOC(walk->commits);
631

632
	if (git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0)
633
		return -1;
634

635
	git_pool_init(&walk->commit_pool, COMMIT_ALLOC);
636 637 638 639 640
	walk->get_next = &revwalk_next_unsorted;
	walk->enqueue = &revwalk_enqueue_unsorted;

	walk->repo = repo;

641
	if (git_repository_odb(&walk->odb, repo) < 0) {
642
		git_revwalk_free(walk);
643
		return -1;
644 645
	}

646
	*revwalk_out = walk;
647
	return 0;
648 649 650 651 652 653 654 655
}

void git_revwalk_free(git_revwalk *walk)
{
	if (walk == NULL)
		return;

	git_revwalk_reset(walk);
656
	git_odb_free(walk->odb);
657

658
	git_oidmap_free(walk->commits);
659
	git_pool_clear(&walk->commit_pool);
660
	git_pqueue_free(&walk->iterator_time);
661
	git__free(walk);
662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685
}

git_repository *git_revwalk_repository(git_revwalk *walk)
{
	assert(walk);
	return walk->repo;
}

void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
{
	assert(walk);

	if (walk->walking)
		git_revwalk_reset(walk);

	walk->sorting = sort_mode;

	if (walk->sorting & GIT_SORT_TIME) {
		walk->get_next = &revwalk_next_timesort;
		walk->enqueue = &revwalk_enqueue_timesort;
	} else {
		walk->get_next = &revwalk_next_unsorted;
		walk->enqueue = &revwalk_enqueue_unsorted;
	}
686

687
	if (walk->sorting != GIT_SORT_NONE)
688
		walk->limited = 1;
689 690
}

691 692 693 694 695
void git_revwalk_simplify_first_parent(git_revwalk *walk)
{
	walk->first_parent = 1;
}

696 697 698
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
699
	git_commit_list_node *next;
700

701
	assert(walk && oid);
702

703
	if (!walk->walking) {
704
		if ((error = prepare_walk(walk)) < 0)
705
			return error;
706
	}
707

708
	error = walk->get_next(&next, walk);
709

Russell Belfer committed
710
	if (error == GIT_ITEROVER) {
711
		git_revwalk_reset(walk);
712
		git_error_clear();
Russell Belfer committed
713
		return GIT_ITEROVER;
714
	}
715

716 717
	if (!error)
		git_oid_cpy(oid, &next->oid);
718

719
	return error;
720 721
}

722
void git_revwalk_reset(git_revwalk *walk)
723
{
724
	git_commit_list_node *commit;
725

726
	assert(walk);
727

728
	git_oidmap_foreach_value(walk->commits, commit, {
729 730 731
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
732
		commit->uninteresting = 0;
733
		commit->added = 0;
734
		commit->flags = 0;
735
		});
736

737
	git_pqueue_clear(&walk->iterator_time);
738 739 740
	git_commit_list_free(&walk->iterator_topo);
	git_commit_list_free(&walk->iterator_rand);
	git_commit_list_free(&walk->iterator_reverse);
741
	git_commit_list_free(&walk->user_input);
742
	walk->first_parent = 0;
743
	walk->walking = 0;
744
	walk->limited = 0;
745
	walk->did_push = walk->did_hide = 0;
746
	walk->sorting = GIT_SORT_NONE;
747
}
748

749 750 751 752 753 754 755 756 757 758 759 760
int git_revwalk_add_hide_cb(
	git_revwalk *walk,
	git_revwalk_hide_cb hide_cb,
	void *payload)
{
	assert(walk);

	if (walk->walking)
		git_revwalk_reset(walk);

	walk->hide_cb = hide_cb;
	walk->hide_cb_payload = payload;
761 762 763

	if (hide_cb)
		walk->limited = 1;
764 765 766 767

	return 0;
}