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

25
	/* lookup and reserve space if not already present */
26 27
	if ((commit = git_oidmap_get(walk->commits, oid)) != NULL)
		return commit;
28

29
	commit = git_commit_list_alloc_node(walk);
30 31
	if (commit == NULL)
		return NULL;
32

33
	git_oid_cpy(&commit->oid, oid);
34

35 36
	if ((git_oidmap_set(walk->commits, &commit->oid, commit)) < 0)
		return NULL;
37 38

	return commit;
39
}
40

41
static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int from_glob)
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 57 58 59
		/* If this comes from e.g. push_glob("tags"), ignore this */
		if (from_glob)
			return 0;

60
		git_error_set(GIT_ERROR_INVALID, "object is not a committish");
61 62
		return -1;
	}
63 64 65 66 67
	if (error < 0)
		return error;

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

77 78
	if (uninteresting) {
		walk->limited = 1;
79
		walk->did_hide = 1;
80
	} else {
81
		walk->did_push = 1;
82
	}
83

84
	commit->uninteresting = uninteresting;
85 86
	list = walk->user_input;
	if (git_commit_list_insert(commit, &list) == NULL) {
87
		git_error_set_oom();
88
		return -1;
89 90
	}

91 92
	walk->user_input = list;

93
	return 0;
94 95
}

96 97 98
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
99
	return push_commit(walk, oid, 0, false);
100
}
101

102

103 104 105
int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
106
	return push_commit(walk, oid, 1, false);
107
}
108

109
static int push_ref(git_revwalk *walk, const char *refname, int hide, int from_glob)
110
{
111
	git_oid oid;
112

113
	if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
114 115
		return -1;

116
	return push_commit(walk, &oid, hide, from_glob);
117 118
}

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

	assert(walk && glob);

	/* refs/ is implied if not given in the glob */
130 131 132
	if (git__prefixcmp(glob, GIT_REFS_DIR) != 0)
		git_buf_joinpath(&buf, GIT_REFS_DIR, glob);
	else
133
		git_buf_puts(&buf, glob);
134
	GIT_ERROR_CHECK_ALLOC_BUF(&buf);
135 136

	/* If no '?', '*' or '[' exist, we append '/ *' to the glob */
137 138 139
	wildcard = strcspn(glob, "?*[");
	if (!glob[wildcard])
		git_buf_put(&buf, "/*", 2);
140

141 142
	if ((error = git_reference_iterator_glob_new(&iter, walk->repo, buf.ptr)) < 0)
		goto out;
143

144 145 146 147 148 149 150
	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);
151

152 153 154
	if (error == GIT_ITEROVER)
		error = 0;
out:
155
	git_buf_dispose(&buf);
156
	return error;
157 158 159 160 161 162 163 164 165 166 167 168 169 170
}

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);
}

171 172 173
int git_revwalk_push_head(git_revwalk *walk)
{
	assert(walk);
174
	return push_ref(walk, GIT_HEAD_FILE, 0, false);
175 176 177 178 179
}

int git_revwalk_hide_head(git_revwalk *walk)
{
	assert(walk);
180
	return push_ref(walk, GIT_HEAD_FILE, 1, false);
181 182 183 184 185
}

int git_revwalk_push_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
186
	return push_ref(walk, refname, 0, false);
187 188
}

189 190
int git_revwalk_push_range(git_revwalk *walk, const char *range)
{
191
	git_revspec revspec;
192 193
	int error = 0;

194
	if ((error = git_revparse(&revspec, walk->repo, range)))
195
		return error;
Vicent Marti committed
196

197
	if (!revspec.to) {
198
		git_error_set(GIT_ERROR_INVALID, "invalid revspec: range not provided");
199 200 201 202
		error = GIT_EINVALIDSPEC;
		goto out;
	}

203
	if (revspec.flags & GIT_REVPARSE_MERGE_BASE) {
204
		/* TODO: support "<commit>...<commit>" */
205
		git_error_set(GIT_ERROR_INVALID, "symmetric differences not implemented in revwalk");
206 207
		error = GIT_EINVALIDSPEC;
		goto out;
208 209
	}

210
	if ((error = push_commit(walk, git_object_id(revspec.from), 1, false)))
211 212
		goto out;

213
	error = push_commit(walk, git_object_id(revspec.to), 0, false);
Vicent Marti committed
214 215

out:
216 217
	git_object_free(revspec.from);
	git_object_free(revspec.to);
218 219 220
	return error;
}

221 222 223
int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
224
	return push_ref(walk, refname, 1, false);
225 226
}

227
static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
228
{
229 230
	return git_pqueue_insert(&walk->iterator_time, commit);
}
231

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

237
static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
238
{
239
	git_commit_list_node *next;
240

241 242 243 244 245 246
	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;
		}
247
	}
248

249
	git_error_clear();
Russell Belfer committed
250
	return GIT_ITEROVER;
251 252
}

253
static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
254
{
255
	int error;
256
	git_commit_list_node *next;
257

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

266
	return error;
267
}
268

269
static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
270
{
271
	int error;
272
	git_commit_list_node *next;
273

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

282
	return error;
283 284
}

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

291
static void mark_parents_uninteresting(git_commit_list_node *commit)
292
{
293 294
	unsigned short i;
	git_commit_list *parents = NULL;
295

296 297
	for (i = 0; i < commit->out_degree; i++)
		git_commit_list_insert(commit->parents[i], &parents);
298

299 300

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

		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];
		}
	}
321 322
}

323
static int add_parents_to_list(git_revwalk *walk, git_commit_list_node *commit, git_commit_list **list)
324 325
{
	unsigned short i;
326
	int error;
327

328 329
	if (commit->added)
		return 0;
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 355 356 357
	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;
358 359
	}

360 361 362 363 364 365 366
	/*
	 * 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];
367

368 369
		if ((error = git_commit_list_parse(walk, p)) < 0)
			return error;
370

371
		if (walk->hide_cb && walk->hide_cb(&p->oid, walk->hide_cb_payload))
372
			continue;
373

374 375 376 377 378 379 380 381 382 383
		if (!p->seen) {
			p->seen = 1;
			git_commit_list_insert_by_date(p, list);
		}

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

385 386 387 388 389 390 391 392 393
/* 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;

394 395 396 397 398 399 400
	/*
	 * 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;

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

	/* 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;
417
	int64_t time = INT64_MAX;
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432
	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)
433 434
				continue;

435
			break;
436
		}
437

438 439
		if (walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload))
			continue;
440 441 442

		time = commit->time;
		p = &git_commit_list_insert(commit, p)->next;
443 444
	}

445
	git_commit_list_free(&list);
446 447
	*out = newlist;
	return 0;
448 449
}

450 451 452 453 454
static int get_revision(git_commit_list_node **out, git_revwalk *walk, git_commit_list **list)
{
	int error;
	git_commit_list_node *commit;

455 456
	commit = git_commit_list_pop(list);
	if (!commit) {
457
		git_error_clear();
458 459 460 461 462 463 464 465 466
		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)
467
			return error;
468 469 470 471
	}

	*out = commit;
	return 0;
472 473
}

474
static int sort_in_topological_order(git_commit_list **out, git_revwalk *walk, git_commit_list *list)
475
{
476
	git_commit_list *ll = NULL, *newlist, **pptr;
477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494
	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.
	 */
495 496
	for (ll = list; ll; ll = ll->next) {
		ll->item->in_degree = 1;
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 557 558 559
	}

	/*
	 * 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;
}

560 561
static int prepare_walk(git_revwalk *walk)
{
562
	int error = 0;
563
	git_commit_list *list, *commits = NULL;
564 565
	git_commit_list_node *next;

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

572 573 574 575 576 577 578 579 580 581 582 583 584 585
	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);
		}
	}

586
	if (walk->limited && (error = limit_list(&commits, walk, commits)) < 0)
587
		return error;
588

589
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
590 591 592 593
		error = sort_in_topological_order(&walk->iterator_topo, walk, commits);
		git_commit_list_free(&commits);

		if (error < 0)
594
			return error;
595

596
		walk->get_next = &revwalk_next_toposort;
597 598 599 600 601 602 603 604 605 606 607
	} 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;
608
	}
609

610
	if (walk->sorting & GIT_SORT_REVERSE) {
611

612
		while ((error = walk->get_next(&next, walk)) == 0)
613
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
614
				return -1;
615

Russell Belfer committed
616
		if (error != GIT_ITEROVER)
617
			return error;
618

619 620
		walk->get_next = &revwalk_next_reverse;
	}
621

622
	walk->walking = 1;
623
	return 0;
624
}
625 626


627 628
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
629
	git_revwalk *walk = git__calloc(1, sizeof(git_revwalk));
630
	GIT_ERROR_CHECK_ALLOC(walk);
631

632 633
	if (git_oidmap_new(&walk->commits) < 0)
		return -1;
634

635
	if (git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0)
636
		return -1;
637

638
	git_pool_init(&walk->commit_pool, COMMIT_ALLOC);
639 640 641 642 643
	walk->get_next = &revwalk_next_unsorted;
	walk->enqueue = &revwalk_enqueue_unsorted;

	walk->repo = repo;

644
	if (git_repository_odb(&walk->odb, repo) < 0) {
645
		git_revwalk_free(walk);
646
		return -1;
647 648
	}

649
	*revwalk_out = walk;
650
	return 0;
651 652 653 654 655 656 657 658
}

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

	git_revwalk_reset(walk);
659
	git_odb_free(walk->odb);
660

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

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;
	}
689

690
	if (walk->sorting != GIT_SORT_NONE)
691
		walk->limited = 1;
692 693
}

694 695 696 697 698
void git_revwalk_simplify_first_parent(git_revwalk *walk)
{
	walk->first_parent = 1;
}

699 700 701
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
702
	git_commit_list_node *next;
703

704
	assert(walk && oid);
705

706
	if (!walk->walking) {
707
		if ((error = prepare_walk(walk)) < 0)
708
			return error;
709
	}
710

711
	error = walk->get_next(&next, walk);
712

Russell Belfer committed
713
	if (error == GIT_ITEROVER) {
714
		git_revwalk_reset(walk);
715
		git_error_clear();
Russell Belfer committed
716
		return GIT_ITEROVER;
717
	}
718

719 720
	if (!error)
		git_oid_cpy(oid, &next->oid);
721

722
	return error;
723 724
}

725
void git_revwalk_reset(git_revwalk *walk)
726
{
727
	git_commit_list_node *commit;
728

729
	assert(walk);
730

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

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

752 753 754 755 756 757 758 759 760 761 762 763
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;
764 765 766

	if (hide_cb)
		walk->limited = 1;
767 768 769 770

	return 0;
}