revwalk.c 16.7 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
git_commit_list_node *git_revwalk__commit_lookup(
	git_revwalk *walk, const git_oid *oid)
20
{
21
	git_commit_list_node *commit;
22 23
	khiter_t pos;
	int ret;
24

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

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

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

36
	pos = git_oidmap_put(walk->commits, &commit->oid, &ret);
37
	assert(ret != 0);
38
	git_oidmap_set_value_at(walk->commits, pos, commit);
39 40

	return commit;
41
}
42

43
static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int from_glob)
44
{
45
	git_oid commit_id;
46
	int error;
47
	git_object *obj, *oobj;
48
	git_commit_list_node *commit;
49
	git_commit_list *list;
50

51
	if ((error = git_object_lookup(&oobj, walk->repo, oid, GIT_OBJ_ANY)) < 0)
52
		return error;
53

54 55
	error = git_object_peel(&obj, oobj, GIT_OBJ_COMMIT);
	git_object_free(oobj);
56

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

62
		giterr_set(GITERR_INVALID, "object is not a committish");
63 64
		return -1;
	}
65 66 67 68 69
	if (error < 0)
		return error;

	git_oid_cpy(&commit_id, git_object_id(obj));
	git_object_free(obj);
70

71
	commit = git_revwalk__commit_lookup(walk, &commit_id);
72
	if (commit == NULL)
73
		return -1; /* error already reported by failed lookup */
74

75 76 77 78
	/* A previous hide already told us we don't want this commit  */
	if (commit->uninteresting)
		return 0;

79 80 81 82 83
	if (uninteresting)
		walk->did_hide = 1;
	else
		walk->did_push = 1;

84
	commit->uninteresting = uninteresting;
85 86 87 88
	list = walk->user_input;
	if (git_commit_list_insert(commit, &list) == NULL) {
		giterr_set_oom();
		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
	GITERR_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_free(&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.flags & GIT_REVPARSE_MERGE_BASE) {
198
		/* TODO: support "<commit>...<commit>" */
199
		giterr_set(GITERR_INVALID, "symmetric differences not implemented in revwalk");
200 201 202
		return GIT_EINVALIDSPEC;
	}

203
	if ((error = push_commit(walk, git_object_id(revspec.from), 1, false)))
204 205
		goto out;

206
	error = push_commit(walk, git_object_id(revspec.to), 0, false);
Vicent Marti committed
207 208

out:
209 210
	git_object_free(revspec.from);
	git_object_free(revspec.to);
211 212 213
	return error;
}

214 215 216
int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
217
	return push_ref(walk, refname, 1, false);
218 219
}

220
static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
221
{
222 223
	return git_pqueue_insert(&walk->iterator_time, commit);
}
224

225
static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
226
{
227
	return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
228
}
229

230
static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
231
{
232
	git_commit_list_node *next;
233

234 235 236 237 238 239
	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;
		}
240
	}
241

Russell Belfer committed
242 243
	giterr_clear();
	return GIT_ITEROVER;
244 245
}

246
static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
247
{
248
	git_commit_list_node *next;
249

250 251 252 253 254 255
	while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL) {
		/* Some commits might become uninteresting after being added to the list */
		if (!next->uninteresting) {
			*object_out = next;
			return 0;
		}
256
	}
257

Russell Belfer committed
258 259
	giterr_clear();
	return GIT_ITEROVER;
260
}
261

262
static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
263
{
264
	git_commit_list_node *next;
265

266 267 268 269 270 271
	while ((next = git_commit_list_pop(&walk->iterator_topo)) != NULL) {
		/* Some commits might become uninteresting after being added to the list */
		if (!next->uninteresting) {
			*object_out = next;
			return 0;
		}
272
	}
273 274 275

	giterr_clear();
	return GIT_ITEROVER;
276 277
}

278
static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
279
{
280
	*object_out = git_commit_list_pop(&walk->iterator_reverse);
Russell Belfer committed
281
	return *object_out ? 0 : GIT_ITEROVER;
282
}
283

284
static void mark_parents_uninteresting(git_commit_list_node *commit)
285
{
286 287
	unsigned short i;
	git_commit_list *parents = NULL;
288

289 290
	for (i = 0; i < commit->out_degree; i++)
		git_commit_list_insert(commit->parents[i], &parents);
291

292 293

	while (parents) {
294
		commit = git_commit_list_pop(&parents);
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313

		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];
		}
	}
314 315
}

316
static int add_parents_to_list(git_revwalk *walk, git_commit_list_node *commit, git_commit_list **list)
317 318
{
	unsigned short i;
319
	int error;
320

321 322
	if (commit->added)
		return 0;
323

324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
	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;
351 352
	}

353 354 355 356 357 358 359
	/*
	 * 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];
360

361 362
		if ((error = git_commit_list_parse(walk, p)) < 0)
			return error;
363

364
		if (walk->hide_cb && walk->hide_cb(&p->oid, walk->hide_cb_payload))
365
			continue;
366

367 368 369 370 371 372 373 374 375 376
		if (!p->seen) {
			p->seen = 1;
			git_commit_list_insert_by_date(p, list);
		}

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

378 379 380 381 382 383 384
static int everybody_uninteresting(git_commit_list *orig)
{
	git_commit_list *list = orig;

	while (list) {
		git_commit_list_node *commit = list->item;
		list = list->next;
385 386
		if (!commit->uninteresting)
			return 0;
387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434
	}

	return 1;
}

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

	/*
	 * If the destination list has commits with an earlier date
	 * than our source we want to continue looking.
	 */
	if (time <= list->item->time)
		return SLOP;

	/* If we find interesting commits, we reset the slop count */
	if (!everybody_uninteresting(list))
		return SLOP;

	/* 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;
	int64_t time = ~0ll;
	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)
435 436
				continue;

437
			break;
438
		}
439 440 441 442 443 444

		if (!commit->uninteresting && walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload))
				continue;

		time = commit->time;
		p = &git_commit_list_insert(commit, p)->next;
445 446
	}

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

452
static int sort_in_topological_order(git_commit_list **out, git_revwalk *walk, git_commit_list *list)
453
{
454
	git_commit_list *ll = NULL, *newlist, **pptr;
455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472
	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.
	 */
473 474
	for (ll = list; ll; ll = ll->next) {
		ll->item->in_degree = 1;
475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 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
	}

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

538 539
static int prepare_walk(git_revwalk *walk)
{
540
	int error;
541
	git_commit_list *list, *commits = NULL;
542 543
	git_commit_list_node *next;

544 545 546 547 548 549
	/* If there were no pushes, we know that the walk is already over */
	if (!walk->did_push) {
		giterr_clear();
		return GIT_ITEROVER;
	}

550 551 552 553 554 555 556 557 558 559 560 561 562 563
	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);
		}
	}

564 565
	if ((error = limit_list(&commits, walk, commits)) < 0)
		return error;
566

567
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
568 569 570 571
		error = sort_in_topological_order(&walk->iterator_topo, walk, commits);
		git_commit_list_free(&commits);

		if (error < 0)
572
			return error;
573

574
		walk->get_next = &revwalk_next_toposort;
575 576 577 578 579 580 581 582 583 584 585
	} 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;
586
	}
587

588
	if (walk->sorting & GIT_SORT_REVERSE) {
589

590
		while ((error = walk->get_next(&next, walk)) == 0)
591
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
592
				return -1;
593

Russell Belfer committed
594
		if (error != GIT_ITEROVER)
595
			return error;
596

597 598
		walk->get_next = &revwalk_next_reverse;
	}
599

600
	walk->walking = 1;
601
	return 0;
602
}
603 604


605 606
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
607
	git_revwalk *walk = git__calloc(1, sizeof(git_revwalk));
608
	GITERR_CHECK_ALLOC(walk);
609

610
	walk->commits = git_oidmap_alloc();
611
	GITERR_CHECK_ALLOC(walk->commits);
612

613
	if (git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0)
614
		return -1;
615

616
	git_pool_init(&walk->commit_pool, COMMIT_ALLOC);
617 618 619 620 621
	walk->get_next = &revwalk_next_unsorted;
	walk->enqueue = &revwalk_enqueue_unsorted;

	walk->repo = repo;

622
	if (git_repository_odb(&walk->odb, repo) < 0) {
623
		git_revwalk_free(walk);
624
		return -1;
625 626
	}

627
	*revwalk_out = walk;
628
	return 0;
629 630 631 632 633 634 635 636
}

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

	git_revwalk_reset(walk);
637
	git_odb_free(walk->odb);
638

639
	git_oidmap_free(walk->commits);
640
	git_pool_clear(&walk->commit_pool);
641
	git_pqueue_free(&walk->iterator_time);
642
	git__free(walk);
643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668
}

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

669 670 671 672 673
void git_revwalk_simplify_first_parent(git_revwalk *walk)
{
	walk->first_parent = 1;
}

674 675 676
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
677
	git_commit_list_node *next;
678

679
	assert(walk && oid);
680

681
	if (!walk->walking) {
682
		if ((error = prepare_walk(walk)) < 0)
683
			return error;
684
	}
685

686
	error = walk->get_next(&next, walk);
687

Russell Belfer committed
688
	if (error == GIT_ITEROVER) {
689
		git_revwalk_reset(walk);
Russell Belfer committed
690 691
		giterr_clear();
		return GIT_ITEROVER;
692
	}
693

694 695
	if (!error)
		git_oid_cpy(oid, &next->oid);
696

697
	return error;
698 699
}

700
void git_revwalk_reset(git_revwalk *walk)
701
{
702
	git_commit_list_node *commit;
703

704
	assert(walk);
705

706
	git_oidmap_foreach_value(walk->commits, commit, {
707 708 709
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
710
		commit->uninteresting = 0;
711
		commit->added = 0;
712
		commit->flags = 0;
713
		});
714

715
	git_pqueue_clear(&walk->iterator_time);
716 717 718
	git_commit_list_free(&walk->iterator_topo);
	git_commit_list_free(&walk->iterator_rand);
	git_commit_list_free(&walk->iterator_reverse);
719
	git_commit_list_free(&walk->user_input);
720
	walk->first_parent = 0;
721
	walk->walking = 0;
722
	walk->did_push = walk->did_hide = 0;
723
}
724

725 726 727 728 729 730 731 732 733 734
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);

735
	if (walk->hide_cb) {
736
		/* There is already a callback added */
737
		giterr_set(GITERR_INVALID, "there is already a callback added to hide commits in revwalk");
738 739 740 741 742 743 744 745 746
		return -1;
	}

	walk->hide_cb = hide_cb;
	walk->hide_cb_payload = payload;

	return 0;
}