revwalk.c 12.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
#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_commit_list_node *commit)
43
{
44
	unsigned short i;
45 46 47
	git_array_t(git_commit_list_node *) pending = GIT_ARRAY_INIT;
	git_commit_list_node **tmp;

48
	assert(commit);
49

50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
	git_array_alloc(pending);
	GITERR_CHECK_ARRAY(pending);

	do {
		commit->uninteresting = 1;

		/* This means we've reached a merge base, so there's no need to walk any more */
		if ((commit->flags & (RESULT | STALE)) == RESULT) {
			tmp = git_array_pop(pending);
			commit = tmp ? *tmp : NULL;
			continue;
		}

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

70 71
		tmp = git_array_pop(pending);
		commit = tmp ? *tmp : NULL;
72

73 74 75 76 77
	} while (git_array_size(pending) > 0);

	git_array_clear(pending);

	return 0;
78
}
79

80
static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
81
{
82 83
	int error;

84 85 86
	if (!hide && walk->hide_cb)
		hide = walk->hide_cb(&commit->oid, walk->hide_cb_payload);

87 88
	if (hide && mark_uninteresting(commit) < 0)
		return -1;
89

90
	if (commit->seen)
91
		return 0;
92

93
	commit->seen = 1;
94

95
	if ((error = git_commit_list_parse(walk, commit)) < 0)
96
		return error;
97

98 99
	return walk->enqueue(walk, commit);
}
100

101
static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit)
102
{
103
	unsigned short i, max;
104
	int error = 0;
105

106 107 108 109 110
	max = commit->out_degree;
	if (walk->first_parent && commit->out_degree)
		max = 1;

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

113
	return error;
114 115
}

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

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

126 127
	error = git_object_peel(&obj, oobj, GIT_OBJ_COMMIT);
	git_object_free(oobj);
128

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

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

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

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

147 148 149
	if (uninteresting)
		walk->did_hide = 1;

150 151 152 153
	commit->uninteresting = uninteresting;
	if (walk->one == NULL && !uninteresting) {
		walk->one = commit;
	} else {
154 155
		if (git_vector_insert(&walk->twos, commit) < 0)
			return -1;
156 157
	}

158
	return 0;
159 160
}

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

167

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

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

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

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

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

	assert(walk && glob);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

305 306
		if (!next->uninteresting) {
			*object_out = next;
307
			return 0;
308
		}
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 ((error = process_commit_parents(walk, next)) < 0)
322
			return error;
323

324 325
		if (!next->uninteresting) {
			*object_out = next;
326
			return 0;
327
		}
328 329
	}

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

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

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

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

351 352 353 354 355 356

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

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

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

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

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

377

378 379 380
static int prepare_walk(git_revwalk *walk)
{
	int error;
381
	unsigned int i;
382 383
	git_commit_list_node *next, *two;
	git_commit_list *bases = NULL;
384

385 386 387 388
	/*
	 * If walk->one is NULL, there were no positive references,
	 * so we know that the walk is already over.
	 */
Russell Belfer committed
389 390 391 392
	if (walk->one == NULL) {
		giterr_clear();
		return GIT_ITEROVER;
	}
393

394 395 396 397 398 399 400 401 402 403 404
	/*
	 * If the user asked to hide commits, we need to figure out
	 * what the merge bases are so we can know when we can stop
	 * marking parents uninteresting.
	 */
	if (walk->did_hide) {
		if (git_merge__bases_many(&bases, walk, walk->one, &walk->twos) < 0)
			return -1;

		git_commit_list_free(&bases);
	}
405

406 407
	if (process_commit(walk, walk->one, walk->one->uninteresting) < 0)
		return -1;
408 409

	git_vector_foreach(&walk->twos, i, two) {
410 411
		if (process_commit(walk, two, two->uninteresting) < 0)
			return -1;
412
	}
413

414 415
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
		unsigned short i;
416

417
		while ((error = walk->get_next(&next, walk)) == 0) {
418
			for (i = 0; i < next->out_degree; ++i) {
419
				git_commit_list_node *parent = next->parents[i];
420 421
				parent->in_degree++;
			}
422

423
			if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
424
				return -1;
425
		}
426

Russell Belfer committed
427
		if (error != GIT_ITEROVER)
428
			return error;
429

430 431
		walk->get_next = &revwalk_next_toposort;
	}
432

433
	if (walk->sorting & GIT_SORT_REVERSE) {
434

435
		while ((error = walk->get_next(&next, walk)) == 0)
436
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
437
				return -1;
438

Russell Belfer committed
439
		if (error != GIT_ITEROVER)
440
			return error;
441

442 443
		walk->get_next = &revwalk_next_reverse;
	}
444

445
	walk->walking = 1;
446
	return 0;
447
}
448 449


450 451 452 453 454
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
	git_revwalk *walk;

	walk = git__malloc(sizeof(git_revwalk));
455
	GITERR_CHECK_ALLOC(walk);
456 457 458

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

459
	walk->commits = git_oidmap_alloc();
460
	GITERR_CHECK_ALLOC(walk->commits);
461

462 463
	if (git_pqueue_init(
			&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0 ||
464
		git_vector_init(&walk->twos, 4, NULL) < 0 ||
465 466
		git_pool_init(&walk->commit_pool, 1,
			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
467
		return -1;
468 469 470 471 472 473

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

	walk->repo = repo;

474
	if (git_repository_odb(&walk->odb, repo) < 0) {
475
		git_revwalk_free(walk);
476
		return -1;
477 478
	}

479
	*revwalk_out = walk;
480
	return 0;
481 482 483 484 485 486 487 488
}

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

	git_revwalk_reset(walk);
489
	git_odb_free(walk->odb);
490

491
	git_oidmap_free(walk->commits);
492
	git_pool_clear(&walk->commit_pool);
493
	git_pqueue_free(&walk->iterator_time);
494
	git_vector_free(&walk->twos);
495
	git__free(walk);
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
}

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

522 523 524 525 526
void git_revwalk_simplify_first_parent(git_revwalk *walk)
{
	walk->first_parent = 1;
}

527 528 529
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
530
	git_commit_list_node *next;
531

532
	assert(walk && oid);
533

534
	if (!walk->walking) {
535
		if ((error = prepare_walk(walk)) < 0)
536
			return error;
537
	}
538

539
	error = walk->get_next(&next, walk);
540

Russell Belfer committed
541
	if (error == GIT_ITEROVER) {
542
		git_revwalk_reset(walk);
Russell Belfer committed
543 544
		giterr_clear();
		return GIT_ITEROVER;
545
	}
546

547 548
	if (!error)
		git_oid_cpy(oid, &next->oid);
549

550
	return error;
551 552
}

553
void git_revwalk_reset(git_revwalk *walk)
554
{
555
	git_commit_list_node *commit;
556

557
	assert(walk);
558

559
	kh_foreach_value(walk->commits, commit, {
560 561 562
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
563
		commit->uninteresting = 0;
564
		});
565

566
	git_pqueue_clear(&walk->iterator_time);
567 568 569
	git_commit_list_free(&walk->iterator_topo);
	git_commit_list_free(&walk->iterator_rand);
	git_commit_list_free(&walk->iterator_reverse);
570
	walk->walking = 0;
571 572 573

	walk->one = NULL;
	git_vector_clear(&walk->twos);
574
}
575

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

586
	if (walk->hide_cb) {
587 588 589 590 591 592 593 594 595 596 597
		/* 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;
}