revwalk.c 14.1 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
GIT__USE_OIDMAP
18

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

26 27 28 29
	/* 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);
30

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

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

37 38 39
	pos = kh_put(oid, walk->commits, &commit->oid, &ret);
	assert(ret != 0);
	kh_value(walk->commits, pos) = commit;
40 41

	return commit;
42
}
43

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
typedef git_array_t(git_commit_list_node*) commit_list_node_array;

static bool interesting_arr(commit_list_node_array arr)
{
	git_commit_list_node **n;
	size_t i = 0, size;

	size = git_array_size(arr);
	for (i = 0; i < size; i++) {
		n = git_array_get(arr, i);
		if (!*n)
			break;

		if (!(*n)->uninteresting)
			return true;
	}

	return false;
}

64
static int mark_uninteresting(git_revwalk *walk, git_commit_list_node *commit)
65
{
66
	int error;
67
	unsigned short i;
68
	commit_list_node_array pending = GIT_ARRAY_INIT;
69 70
	git_commit_list_node **tmp;

71
	assert(commit);
72

73 74 75
	do {
		commit->uninteresting = 1;

76 77
		if ((error = git_commit_list_parse(walk, commit)) < 0)
			return error;
78 79 80 81 82 83 84

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

86 87
		tmp = git_array_pop(pending);
		commit = tmp ? *tmp : NULL;
88

89
	} while (commit != NULL && !interesting_arr(pending));
90 91 92 93

	git_array_clear(pending);

	return 0;
94
}
95

96
static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
97
{
98 99
	int error;

100 101 102
	if (!hide && walk->hide_cb)
		hide = walk->hide_cb(&commit->oid, walk->hide_cb_payload);

103
	if (hide && mark_uninteresting(walk, commit) < 0)
104
		return -1;
105

106
	if (commit->seen)
107
		return 0;
108

109
	commit->seen = 1;
110

111
	if ((error = git_commit_list_parse(walk, commit)) < 0)
112
		return error;
113

114 115 116 117
	if (!hide)
		return walk->enqueue(walk, commit);

	return 0;
118
}
119

120
static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit)
121
{
122
	unsigned short i, max;
123
	int error = 0;
124

125 126 127 128 129
	max = commit->out_degree;
	if (walk->first_parent && commit->out_degree)
		max = 1;

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

132
	return error;
133 134
}

135
static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int from_glob)
136
{
137
	git_oid commit_id;
138
	int error;
139
	git_object *obj, *oobj;
140
	git_commit_list_node *commit;
141
	git_commit_list *list;
142

143
	if ((error = git_object_lookup(&oobj, walk->repo, oid, GIT_OBJ_ANY)) < 0)
144
		return error;
145

146 147
	error = git_object_peel(&obj, oobj, GIT_OBJ_COMMIT);
	git_object_free(oobj);
148

149
	if (error == GIT_ENOTFOUND || error == GIT_EINVALIDSPEC || error == GIT_EPEEL) {
150 151 152 153
		/* If this comes from e.g. push_glob("tags"), ignore this */
		if (from_glob)
			return 0;

154
		giterr_set(GITERR_INVALID, "Object is not a committish");
155 156
		return -1;
	}
157 158 159 160 161
	if (error < 0)
		return error;

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

163
	commit = git_revwalk__commit_lookup(walk, &commit_id);
164
	if (commit == NULL)
165
		return -1; /* error already reported by failed lookup */
166

167 168 169 170
	/* A previous hide already told us we don't want this commit  */
	if (commit->uninteresting)
		return 0;

171 172 173 174 175
	if (uninteresting)
		walk->did_hide = 1;
	else
		walk->did_push = 1;

176
	commit->uninteresting = uninteresting;
177 178 179 180
	list = walk->user_input;
	if (git_commit_list_insert(commit, &list) == NULL) {
		giterr_set_oom();
		return -1;
181 182
	}

183 184
	walk->user_input = list;

185
	return 0;
186 187
}

188 189 190
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
191
	return push_commit(walk, oid, 0, false);
192
}
193

194

195 196 197
int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
198
	return push_commit(walk, oid, 1, false);
199
}
200

201
static int push_ref(git_revwalk *walk, const char *refname, int hide, int from_glob)
202
{
203
	git_oid oid;
204

205
	if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
206 207
		return -1;

208
	return push_commit(walk, &oid, hide, from_glob);
209 210
}

211 212
static int push_glob(git_revwalk *walk, const char *glob, int hide)
{
213
	int error = 0;
214
	git_buf buf = GIT_BUF_INIT;
215 216
	git_reference *ref;
	git_reference_iterator *iter;
217
	size_t wildcard;
218 219 220 221

	assert(walk && glob);

	/* refs/ is implied if not given in the glob */
222 223 224
	if (git__prefixcmp(glob, GIT_REFS_DIR) != 0)
		git_buf_joinpath(&buf, GIT_REFS_DIR, glob);
	else
225
		git_buf_puts(&buf, glob);
226 227
	if (git_buf_oom(&buf))
		return -1;
228 229

	/* If no '?', '*' or '[' exist, we append '/ *' to the glob */
230 231 232
	wildcard = strcspn(glob, "?*[");
	if (!glob[wildcard])
		git_buf_put(&buf, "/*", 2);
233

234 235
	if ((error = git_reference_iterator_glob_new(&iter, walk->repo, buf.ptr)) < 0)
		goto out;
236

237 238 239 240 241 242 243
	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);
244

245 246 247
	if (error == GIT_ITEROVER)
		error = 0;
out:
248
	git_buf_free(&buf);
249
	return error;
250 251 252 253 254 255 256 257 258 259 260 261 262 263
}

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

264 265 266
int git_revwalk_push_head(git_revwalk *walk)
{
	assert(walk);
267
	return push_ref(walk, GIT_HEAD_FILE, 0, false);
268 269 270 271 272
}

int git_revwalk_hide_head(git_revwalk *walk)
{
	assert(walk);
273
	return push_ref(walk, GIT_HEAD_FILE, 1, false);
274 275 276 277 278
}

int git_revwalk_push_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
279
	return push_ref(walk, refname, 0, false);
280 281
}

282 283
int git_revwalk_push_range(git_revwalk *walk, const char *range)
{
284
	git_revspec revspec;
285 286
	int error = 0;

287
	if ((error = git_revparse(&revspec, walk->repo, range)))
288
		return error;
Vicent Marti committed
289

290
	if (revspec.flags & GIT_REVPARSE_MERGE_BASE) {
291 292 293 294 295
		/* TODO: support "<commit>...<commit>" */
		giterr_set(GITERR_INVALID, "Symmetric differences not implemented in revwalk");
		return GIT_EINVALIDSPEC;
	}

296
	if ((error = push_commit(walk, git_object_id(revspec.from), 1, false)))
297 298
		goto out;

299
	error = push_commit(walk, git_object_id(revspec.to), 0, false);
Vicent Marti committed
300 301

out:
302 303
	git_object_free(revspec.from);
	git_object_free(revspec.to);
304 305 306
	return error;
}

307 308 309
int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
310
	return push_ref(walk, refname, 1, false);
311 312
}

313
static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
314
{
315 316
	return git_pqueue_insert(&walk->iterator_time, commit);
}
317

318
static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
319
{
320
	return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
321
}
322

323
static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
324 325
{
	int error;
326
	git_commit_list_node *next;
327

328
	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL)
329
		if (!next->uninteresting) {
330 331 332
			if ((error = process_commit_parents(walk, next)) < 0)
				return error;

333
			*object_out = next;
334
			return 0;
335
		}
336

Russell Belfer committed
337 338
	giterr_clear();
	return GIT_ITEROVER;
339 340
}

341
static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
342
{
343
	int error;
344
	git_commit_list_node *next;
345

346
	while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL)
347
		if (!next->uninteresting) {
348 349 350
			if ((error = process_commit_parents(walk, next)) < 0)
				return error;

351
			*object_out = next;
352
			return 0;
353
		}
354

Russell Belfer committed
355 356
	giterr_clear();
	return GIT_ITEROVER;
357
}
358

359
static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
360
{
361
	git_commit_list_node *next;
362
	unsigned short i, max;
363

364
	for (;;) {
365
		next = git_commit_list_pop(&walk->iterator_topo);
Russell Belfer committed
366 367 368 369
		if (next == NULL) {
			giterr_clear();
			return GIT_ITEROVER;
		}
370

371 372 373 374
		if (next->in_degree > 0) {
			next->topo_delay = 1;
			continue;
		}
375

376 377 378 379 380 381

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

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

384 385
			if (--parent->in_degree == 0 && parent->topo_delay) {
				parent->topo_delay = 0;
386
				if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL)
387
					return -1;
388 389
			}
		}
390

391
		*object_out = next;
392
		return 0;
393
	}
394 395
}

396
static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
397
{
398
	*object_out = git_commit_list_pop(&walk->iterator_reverse);
Russell Belfer committed
399
	return *object_out ? 0 : GIT_ITEROVER;
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 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472
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;
}

473 474
static int prepare_walk(git_revwalk *walk)
{
475
	int error;
476 477 478
	git_commit_list *list;
	git_commit_list_node *next;

479 480 481 482 483 484 485
	/* 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)
486 487
		return error;

488 489 490 491 492
	for (list = walk->user_input; list; list = list->next) {
		if (process_commit(walk, list->item, list->item->uninteresting) < 0)
			return -1;
	}

493

494 495
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
		unsigned short i;
496

497
		while ((error = walk->get_next(&next, walk)) == 0) {
498
			for (i = 0; i < next->out_degree; ++i) {
499
				git_commit_list_node *parent = next->parents[i];
500 501
				parent->in_degree++;
			}
502

503
			if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
504
				return -1;
505
		}
506

Russell Belfer committed
507
		if (error != GIT_ITEROVER)
508
			return error;
509

510 511
		walk->get_next = &revwalk_next_toposort;
	}
512

513
	if (walk->sorting & GIT_SORT_REVERSE) {
514

515
		while ((error = walk->get_next(&next, walk)) == 0)
516
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
517
				return -1;
518

Russell Belfer committed
519
		if (error != GIT_ITEROVER)
520
			return error;
521

522 523
		walk->get_next = &revwalk_next_reverse;
	}
524

525
	walk->walking = 1;
526
	return 0;
527
}
528 529


530 531
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
532
	git_revwalk *walk = git__calloc(1, sizeof(git_revwalk));
533
	GITERR_CHECK_ALLOC(walk);
534

535
	walk->commits = git_oidmap_alloc();
536
	GITERR_CHECK_ALLOC(walk->commits);
537

538 539
	if (git_pqueue_init(
			&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0 ||
540 541
		git_pool_init(&walk->commit_pool, 1,
			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
542
		return -1;
543 544 545 546 547 548

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

	walk->repo = repo;

549
	if (git_repository_odb(&walk->odb, repo) < 0) {
550
		git_revwalk_free(walk);
551
		return -1;
552 553
	}

554
	*revwalk_out = walk;
555
	return 0;
556 557 558 559 560 561 562 563
}

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

	git_revwalk_reset(walk);
564
	git_odb_free(walk->odb);
565

566
	git_oidmap_free(walk->commits);
567
	git_pool_clear(&walk->commit_pool);
568
	git_pqueue_free(&walk->iterator_time);
569
	git__free(walk);
570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595
}

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

596 597 598 599 600
void git_revwalk_simplify_first_parent(git_revwalk *walk)
{
	walk->first_parent = 1;
}

601 602 603
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
604
	git_commit_list_node *next;
605

606
	assert(walk && oid);
607

608
	if (!walk->walking) {
609
		if ((error = prepare_walk(walk)) < 0)
610
			return error;
611
	}
612

613
	error = walk->get_next(&next, walk);
614

Russell Belfer committed
615
	if (error == GIT_ITEROVER) {
616
		git_revwalk_reset(walk);
Russell Belfer committed
617 618
		giterr_clear();
		return GIT_ITEROVER;
619
	}
620

621 622
	if (!error)
		git_oid_cpy(oid, &next->oid);
623

624
	return error;
625 626
}

627
void git_revwalk_reset(git_revwalk *walk)
628
{
629
	git_commit_list_node *commit;
630

631
	assert(walk);
632

633
	kh_foreach_value(walk->commits, commit, {
634 635 636
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
637
		commit->uninteresting = 0;
638
		commit->flags = 0;
639
		});
640

641
	git_pqueue_clear(&walk->iterator_time);
642 643 644
	git_commit_list_free(&walk->iterator_topo);
	git_commit_list_free(&walk->iterator_rand);
	git_commit_list_free(&walk->iterator_reverse);
645
	git_commit_list_free(&walk->user_input);
646
	walk->first_parent = 0;
647
	walk->walking = 0;
648
	walk->did_push = walk->did_hide = 0;
649
}
650

651 652 653 654 655 656 657 658 659 660
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);

661
	if (walk->hide_cb) {
662 663 664 665 666 667 668 669 670 671 672
		/* 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;
}