revwalk.c 13.6 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
#include "common.h"
9
#include "commit.h"
Vicent Marti committed
10
#include "odb.h"
11
#include "pool.h"
12

13
#include "revwalk.h"
14
#include "git2/revparse.h"
15
#include "merge.h"
16

17 18
git_commit_list_node *git_revwalk__commit_lookup(
	git_revwalk *walk, const git_oid *oid)
19
{
20
	git_commit_list_node *commit;
21 22
	khiter_t pos;
	int ret;
23

24 25 26 27
	/* lookup and reserve space if not already present */
	pos = kh_get(oid, walk->commits, oid);
	if (pos != kh_end(walk->commits))
		return kh_value(walk->commits, pos);
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 37
	pos = kh_put(oid, walk->commits, &commit->oid, &ret);
	assert(ret != 0);
	kh_value(walk->commits, pos) = commit;
38 39

	return commit;
40
}
41

42
static int mark_uninteresting(git_revwalk *walk, git_commit_list_node *commit)
43
{
44
	int error;
45
	unsigned short i;
46 47 48
	git_array_t(git_commit_list_node *) pending = GIT_ARRAY_INIT;
	git_commit_list_node **tmp;

49
	assert(commit);
50

51 52 53
	do {
		commit->uninteresting = 1;

54 55
		if ((error = git_commit_list_parse(walk, commit)) < 0)
			return error;
56 57 58 59 60 61 62

		for (i = 0; i < commit->out_degree; ++i)
			if (!commit->parents[i]->uninteresting) {
				git_commit_list_node **node = git_array_alloc(pending);
				GITERR_CHECK_ALLOC(node);
				*node = commit->parents[i];
			}
63

64 65
		tmp = git_array_pop(pending);
		commit = tmp ? *tmp : NULL;
66

67
	} while (commit != NULL);
68 69 70 71

	git_array_clear(pending);

	return 0;
72
}
73

74
static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
75
{
76 77
	int error;

78 79 80
	if (!hide && walk->hide_cb)
		hide = walk->hide_cb(&commit->oid, walk->hide_cb_payload);

81
	if (hide && mark_uninteresting(walk, commit) < 0)
82
		return -1;
83

84
	if (commit->seen)
85
		return 0;
86

87
	commit->seen = 1;
88

89
	if ((error = git_commit_list_parse(walk, commit)) < 0)
90
		return error;
91

92 93 94 95
	if (!hide)
		return walk->enqueue(walk, commit);

	return 0;
96
}
97

98
static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit)
99
{
100
	unsigned short i, max;
101
	int error = 0;
102

103 104 105 106 107
	max = commit->out_degree;
	if (walk->first_parent && commit->out_degree)
		max = 1;

	for (i = 0; i < max && !error; ++i)
108
		error = process_commit(walk, commit->parents[i], commit->uninteresting);
109

110
	return error;
111 112
}

113
static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int from_glob)
114
{
115
	git_oid commit_id;
116
	int error;
117
	git_object *obj, *oobj;
118
	git_commit_list_node *commit;
119
	git_commit_list *list;
120

121
	if ((error = git_object_lookup(&oobj, walk->repo, oid, GIT_OBJ_ANY)) < 0)
122
		return error;
123

124 125
	error = git_object_peel(&obj, oobj, GIT_OBJ_COMMIT);
	git_object_free(oobj);
126

127
	if (error == GIT_ENOTFOUND || error == GIT_EINVALIDSPEC || error == GIT_EPEEL) {
128 129 130 131
		/* If this comes from e.g. push_glob("tags"), ignore this */
		if (from_glob)
			return 0;

132
		giterr_set(GITERR_INVALID, "Object is not a committish");
133 134
		return -1;
	}
135 136 137 138 139
	if (error < 0)
		return error;

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

141
	commit = git_revwalk__commit_lookup(walk, &commit_id);
142
	if (commit == NULL)
143
		return -1; /* error already reported by failed lookup */
144

145 146 147 148 149
	if (uninteresting)
		walk->did_hide = 1;
	else
		walk->did_push = 1;

150
	commit->uninteresting = uninteresting;
151 152 153 154
	list = walk->user_input;
	if (git_commit_list_insert(commit, &list) == NULL) {
		giterr_set_oom();
		return -1;
155 156
	}

157 158
	walk->user_input = list;

159
	return 0;
160 161
}

162 163 164
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
165
	return push_commit(walk, oid, 0, false);
166
}
167

168

169 170 171
int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
172
	return push_commit(walk, oid, 1, false);
173
}
174

175
static int push_ref(git_revwalk *walk, const char *refname, int hide, int from_glob)
176
{
177
	git_oid oid;
178

179
	if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
180 181
		return -1;

182
	return push_commit(walk, &oid, hide, from_glob);
183 184
}

185 186
static int push_glob(git_revwalk *walk, const char *glob, int hide)
{
187
	int error = 0;
188
	git_buf buf = GIT_BUF_INIT;
189 190
	git_reference *ref;
	git_reference_iterator *iter;
191
	size_t wildcard;
192 193 194 195

	assert(walk && glob);

	/* refs/ is implied if not given in the glob */
196 197 198
	if (git__prefixcmp(glob, GIT_REFS_DIR) != 0)
		git_buf_joinpath(&buf, GIT_REFS_DIR, glob);
	else
199
		git_buf_puts(&buf, glob);
200 201
	if (git_buf_oom(&buf))
		return -1;
202 203

	/* If no '?', '*' or '[' exist, we append '/ *' to the glob */
204 205 206
	wildcard = strcspn(glob, "?*[");
	if (!glob[wildcard])
		git_buf_put(&buf, "/*", 2);
207

208 209
	if ((error = git_reference_iterator_glob_new(&iter, walk->repo, buf.ptr)) < 0)
		goto out;
210

211 212 213 214 215 216 217
	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);
218

219 220 221
	if (error == GIT_ITEROVER)
		error = 0;
out:
222
	git_buf_free(&buf);
223
	return error;
224 225 226 227 228 229 230 231 232 233 234 235 236 237
}

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

238 239 240
int git_revwalk_push_head(git_revwalk *walk)
{
	assert(walk);
241
	return push_ref(walk, GIT_HEAD_FILE, 0, false);
242 243 244 245 246
}

int git_revwalk_hide_head(git_revwalk *walk)
{
	assert(walk);
247
	return push_ref(walk, GIT_HEAD_FILE, 1, false);
248 249 250 251 252
}

int git_revwalk_push_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
253
	return push_ref(walk, refname, 0, false);
254 255
}

256 257
int git_revwalk_push_range(git_revwalk *walk, const char *range)
{
258
	git_revspec revspec;
259 260
	int error = 0;

261
	if ((error = git_revparse(&revspec, walk->repo, range)))
262
		return error;
Vicent Marti committed
263

264
	if (revspec.flags & GIT_REVPARSE_MERGE_BASE) {
265 266 267 268 269
		/* TODO: support "<commit>...<commit>" */
		giterr_set(GITERR_INVALID, "Symmetric differences not implemented in revwalk");
		return GIT_EINVALIDSPEC;
	}

270
	if ((error = push_commit(walk, git_object_id(revspec.from), 1, false)))
271 272
		goto out;

273
	error = push_commit(walk, git_object_id(revspec.to), 0, false);
Vicent Marti committed
274 275

out:
276 277
	git_object_free(revspec.from);
	git_object_free(revspec.to);
278 279 280
	return error;
}

281 282 283
int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
284
	return push_ref(walk, refname, 1, false);
285 286
}

287
static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
288
{
289 290
	return git_pqueue_insert(&walk->iterator_time, commit);
}
291

292
static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
293
{
294
	return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
295
}
296

297
static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
298 299
{
	int error;
300
	git_commit_list_node *next;
301

302
	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL)
303
		if (!next->uninteresting) {
304 305 306
			if ((error = process_commit_parents(walk, next)) < 0)
				return error;

307
			*object_out = next;
308
			return 0;
309
		}
310

Russell Belfer committed
311 312
	giterr_clear();
	return GIT_ITEROVER;
313 314
}

315
static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
316
{
317
	int error;
318
	git_commit_list_node *next;
319

320
	while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL)
321
		if (!next->uninteresting) {
322 323 324
			if ((error = process_commit_parents(walk, next)) < 0)
				return error;

325
			*object_out = next;
326
			return 0;
327
		}
328

Russell Belfer committed
329 330
	giterr_clear();
	return GIT_ITEROVER;
331
}
332

333
static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
334
{
335
	git_commit_list_node *next;
336
	unsigned short i, max;
337

338
	for (;;) {
339
		next = git_commit_list_pop(&walk->iterator_topo);
Russell Belfer committed
340 341 342 343
		if (next == NULL) {
			giterr_clear();
			return GIT_ITEROVER;
		}
344

345 346 347 348
		if (next->in_degree > 0) {
			next->topo_delay = 1;
			continue;
		}
349

350 351 352 353 354 355

		max = next->out_degree;
		if (walk->first_parent && next->out_degree)
			max = 1;

		for (i = 0; i < max; ++i) {
356
			git_commit_list_node *parent = next->parents[i];
357

358 359
			if (--parent->in_degree == 0 && parent->topo_delay) {
				parent->topo_delay = 0;
360
				if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL)
361
					return -1;
362 363
			}
		}
364

365
		*object_out = next;
366
		return 0;
367
	}
368 369
}

370
static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
371
{
372
	*object_out = git_commit_list_pop(&walk->iterator_reverse);
Russell Belfer committed
373
	return *object_out ? 0 : GIT_ITEROVER;
374
}
375

376

377 378 379 380 381 382 383 384 385 386 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 435 436 437 438 439 440 441 442 443 444 445 446
static int interesting(git_pqueue *list)
{
	size_t i;

	for (i = 0; i < git_pqueue_size(list); i++) {
		git_commit_list_node *commit = git_pqueue_get(list, i);
		if (!commit->uninteresting)
			return 1;
	}

	return 0;
}

static int contains(git_pqueue *list, git_commit_list_node *node)
{
	size_t i;

	for (i = 0; i < git_pqueue_size(list); i++) {
		git_commit_list_node *commit = git_pqueue_get(list, i);
		if (commit == node)
			return 1;
	}

	return 0;
}

static int premark_uninteresting(git_revwalk *walk)
{
	int error = 0;
	unsigned short i;
	git_pqueue q;
	git_commit_list *list;
	git_commit_list_node *commit, *parent;

	if ((error = git_pqueue_init(&q, 0, 8, git_commit_list_time_cmp)) < 0)
		return error;

	for (list = walk->user_input; list; list = list->next) {
		if ((error = git_commit_list_parse(walk, list->item)) < 0)
			goto cleanup;

		if ((error = git_pqueue_insert(&q, list->item)) < 0)
			goto cleanup;
	}

	while (interesting(&q)) {
		commit = git_pqueue_pop(&q);

		for (i = 0; i < commit->out_degree; i++) {
			parent = commit->parents[i];

			if ((error = git_commit_list_parse(walk, parent)) < 0)
				goto cleanup;

			if (commit->uninteresting)
				parent->uninteresting = 1;

			if (contains(&q, parent))
				continue;

			if ((error = git_pqueue_insert(&q, parent)) < 0)
				goto cleanup;
		}
	}

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

447 448
static int prepare_walk(git_revwalk *walk)
{
449
	int error;
450 451 452
	git_commit_list *list;
	git_commit_list_node *next;

453 454 455 456 457 458 459
	/* If there were no pushes, we know that the walk is already over */
	if (!walk->did_push) {
		giterr_clear();
		return GIT_ITEROVER;
	}

	if (walk->did_hide && (error = premark_uninteresting(walk)) < 0)
460 461
		return error;

462 463 464 465 466
	for (list = walk->user_input; list; list = list->next) {
		if (process_commit(walk, list->item, list->item->uninteresting) < 0)
			return -1;
	}

467

468 469
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
		unsigned short i;
470

471
		while ((error = walk->get_next(&next, walk)) == 0) {
472
			for (i = 0; i < next->out_degree; ++i) {
473
				git_commit_list_node *parent = next->parents[i];
474 475
				parent->in_degree++;
			}
476

477
			if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
478
				return -1;
479
		}
480

Russell Belfer committed
481
		if (error != GIT_ITEROVER)
482
			return error;
483

484 485
		walk->get_next = &revwalk_next_toposort;
	}
486

487
	if (walk->sorting & GIT_SORT_REVERSE) {
488

489
		while ((error = walk->get_next(&next, walk)) == 0)
490
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
491
				return -1;
492

Russell Belfer committed
493
		if (error != GIT_ITEROVER)
494
			return error;
495

496 497
		walk->get_next = &revwalk_next_reverse;
	}
498

499
	walk->walking = 1;
500
	return 0;
501
}
502 503


504 505 506 507 508
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
	git_revwalk *walk;

	walk = git__malloc(sizeof(git_revwalk));
509
	GITERR_CHECK_ALLOC(walk);
510 511 512

	memset(walk, 0x0, sizeof(git_revwalk));

513
	walk->commits = git_oidmap_alloc();
514
	GITERR_CHECK_ALLOC(walk->commits);
515

516 517
	if (git_pqueue_init(
			&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0 ||
518 519
		git_pool_init(&walk->commit_pool, 1,
			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
520
		return -1;
521 522 523 524 525 526

	walk->get_next = &revwalk_next_unsorted;
	walk->enqueue = &revwalk_enqueue_unsorted;

	walk->repo = repo;

527
	if (git_repository_odb(&walk->odb, repo) < 0) {
528
		git_revwalk_free(walk);
529
		return -1;
530 531
	}

532
	*revwalk_out = walk;
533
	return 0;
534 535 536 537 538 539 540 541
}

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

	git_revwalk_reset(walk);
542
	git_odb_free(walk->odb);
543

544
	git_oidmap_free(walk->commits);
545
	git_pool_clear(&walk->commit_pool);
546
	git_pqueue_free(&walk->iterator_time);
547
	git__free(walk);
548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573
}

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

574 575 576 577 578
void git_revwalk_simplify_first_parent(git_revwalk *walk)
{
	walk->first_parent = 1;
}

579 580 581
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
582
	git_commit_list_node *next;
583

584
	assert(walk && oid);
585

586
	if (!walk->walking) {
587
		if ((error = prepare_walk(walk)) < 0)
588
			return error;
589
	}
590

591
	error = walk->get_next(&next, walk);
592

Russell Belfer committed
593
	if (error == GIT_ITEROVER) {
594
		git_revwalk_reset(walk);
Russell Belfer committed
595 596
		giterr_clear();
		return GIT_ITEROVER;
597
	}
598

599 600
	if (!error)
		git_oid_cpy(oid, &next->oid);
601

602
	return error;
603 604
}

605
void git_revwalk_reset(git_revwalk *walk)
606
{
607
	git_commit_list_node *commit;
608

609
	assert(walk);
610

611
	kh_foreach_value(walk->commits, commit, {
612 613 614
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
615
		commit->uninteresting = 0;
616
		commit->flags = 0;
617
		});
618

619
	git_pqueue_clear(&walk->iterator_time);
620 621 622
	git_commit_list_free(&walk->iterator_topo);
	git_commit_list_free(&walk->iterator_rand);
	git_commit_list_free(&walk->iterator_reverse);
623
	git_commit_list_free(&walk->user_input);
624
	walk->first_parent = 0;
625
	walk->walking = 0;
626
	walk->did_push = walk->did_hide = 0;
627
}
628

629 630 631 632 633 634 635 636 637 638
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);

639
	if (walk->hide_cb) {
640 641 642 643 644 645 646 647 648 649 650
		/* There is already a callback added */
		giterr_set(GITERR_INVALID, "There is already a callback added to hide commits in revision walker.");
		return -1;
	}

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

	return 0;
}