revwalk.c 17 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.flags & GIT_REVPARSE_MERGE_BASE) {
198
		/* TODO: support "<commit>...<commit>" */
199
		git_error_set(GIT_ERROR_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

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

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

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

259
	return error;
260
}
261

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

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

275
	return error;
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 385 386
/* 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;

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

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

	/* 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;
410
	int64_t time = INT64_MAX;
411 412 413 414 415 416 417 418 419 420 421 422 423 424 425
	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)
426 427
				continue;

428
			break;
429
		}
430

431 432
		if (walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload))
			continue;
433 434 435

		time = commit->time;
		p = &git_commit_list_insert(commit, p)->next;
436 437
	}

438
	git_commit_list_free(&list);
439 440
	*out = newlist;
	return 0;
441 442
}

443 444 445 446 447
static int get_revision(git_commit_list_node **out, git_revwalk *walk, git_commit_list **list)
{
	int error;
	git_commit_list_node *commit;

448 449
	commit = git_commit_list_pop(list);
	if (!commit) {
450
		git_error_clear();
451 452 453 454 455 456 457 458 459
		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)
460
			return error;
461 462 463 464
	}

	*out = commit;
	return 0;
465 466
}

467
static int sort_in_topological_order(git_commit_list **out, git_revwalk *walk, git_commit_list *list)
468
{
469
	git_commit_list *ll = NULL, *newlist, **pptr;
470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487
	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.
	 */
488 489
	for (ll = list; ll; ll = ll->next) {
		ll->item->in_degree = 1;
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 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552
	}

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

553 554
static int prepare_walk(git_revwalk *walk)
{
555
	int error = 0;
556
	git_commit_list *list, *commits = NULL;
557 558
	git_commit_list_node *next;

559 560
	/* If there were no pushes, we know that the walk is already over */
	if (!walk->did_push) {
561
		git_error_clear();
562 563 564
		return GIT_ITEROVER;
	}

565 566 567 568 569 570 571 572 573 574 575 576 577 578
	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);
		}
	}

579
	if (walk->limited && (error = limit_list(&commits, walk, commits)) < 0)
580
		return error;
581

582
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
583 584 585 586
		error = sort_in_topological_order(&walk->iterator_topo, walk, commits);
		git_commit_list_free(&commits);

		if (error < 0)
587
			return error;
588

589
		walk->get_next = &revwalk_next_toposort;
590 591 592 593 594 595 596 597 598 599 600
	} 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;
601
	}
602

603
	if (walk->sorting & GIT_SORT_REVERSE) {
604

605
		while ((error = walk->get_next(&next, walk)) == 0)
606
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
607
				return -1;
608

Russell Belfer committed
609
		if (error != GIT_ITEROVER)
610
			return error;
611

612 613
		walk->get_next = &revwalk_next_reverse;
	}
614

615
	walk->walking = 1;
616
	return 0;
617
}
618 619


620 621
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
622
	git_revwalk *walk = git__calloc(1, sizeof(git_revwalk));
623
	GIT_ERROR_CHECK_ALLOC(walk);
624

625 626
	if (git_oidmap_new(&walk->commits) < 0)
		return -1;
627

628
	if (git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0)
629
		return -1;
630

631
	git_pool_init(&walk->commit_pool, COMMIT_ALLOC);
632 633 634 635 636
	walk->get_next = &revwalk_next_unsorted;
	walk->enqueue = &revwalk_enqueue_unsorted;

	walk->repo = repo;

637
	if (git_repository_odb(&walk->odb, repo) < 0) {
638
		git_revwalk_free(walk);
639
		return -1;
640 641
	}

642
	*revwalk_out = walk;
643
	return 0;
644 645 646 647 648 649 650 651
}

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

	git_revwalk_reset(walk);
652
	git_odb_free(walk->odb);
653

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

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

683
	if (walk->sorting != GIT_SORT_NONE)
684
		walk->limited = 1;
685 686
}

687 688 689 690 691
void git_revwalk_simplify_first_parent(git_revwalk *walk)
{
	walk->first_parent = 1;
}

692 693 694
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
695
	git_commit_list_node *next;
696

697
	assert(walk && oid);
698

699
	if (!walk->walking) {
700
		if ((error = prepare_walk(walk)) < 0)
701
			return error;
702
	}
703

704
	error = walk->get_next(&next, walk);
705

Russell Belfer committed
706
	if (error == GIT_ITEROVER) {
707
		git_revwalk_reset(walk);
708
		git_error_clear();
Russell Belfer committed
709
		return GIT_ITEROVER;
710
	}
711

712 713
	if (!error)
		git_oid_cpy(oid, &next->oid);
714

715
	return error;
716 717
}

718
void git_revwalk_reset(git_revwalk *walk)
719
{
720
	git_commit_list_node *commit;
721

722
	assert(walk);
723

724
	git_oidmap_foreach_value(walk->commits, commit, {
725 726 727
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
728
		commit->uninteresting = 0;
729
		commit->added = 0;
730
		commit->flags = 0;
731
		});
732

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

745 746 747 748 749 750 751 752 753 754 755 756
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;
757 758 759

	if (hide_cb)
		walk->limited = 1;
760 761 762 763

	return 0;
}