revwalk.c 10.6 KB
Newer Older
1
/*
schu committed
2
 * Copyright (C) 2009-2012 the libgit2 contributors
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 14
#include "revwalk.h"
#include "merge.h"
15

16 17
#include <regex.h>

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 26 27 28
	/* 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);
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 37 38
	pos = kh_put(oid, walk->commits, &commit->oid, &ret);
	assert(ret != 0);
	kh_value(walk->commits, pos) = commit;
39 40

	return commit;
41
}
42

43
static void mark_uninteresting(git_commit_list_node *commit)
44
{
45 46
	unsigned short i;
	assert(commit);
47

48
	commit->uninteresting = 1;
49

50 51 52 53
	/* This means we've reached a merge base, so there's no need to walk any more */
	if ((commit->flags & (RESULT | STALE)) == RESULT)
		return;

54 55 56
	for (i = 0; i < commit->out_degree; ++i)
		if (!commit->parents[i]->uninteresting)
			mark_uninteresting(commit->parents[i]);
57
}
58

59
static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
60
{
61 62
	int error;

63 64 65
	if (hide)
		mark_uninteresting(commit);

66
	if (commit->seen)
67
		return 0;
68

69
	commit->seen = 1;
70

71
	if ((error = git_commit_list_parse(walk, commit)) < 0)
72
		return error;
73

74 75
	return walk->enqueue(walk, commit);
}
76

77
static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit)
78 79
{
	unsigned short i;
80
	int error = 0;
81

82 83
	for (i = 0; i < commit->out_degree && !error; ++i)
		error = process_commit(walk, commit->parents[i], commit->uninteresting);
84

85
	return error;
86 87
}

88
static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
89
{
90 91
	git_object *obj;
	git_otype type;
92
	git_commit_list_node *commit;
93

94 95 96 97 98 99 100 101 102 103 104
	if (git_object_lookup(&obj, walk->repo, oid, GIT_OBJ_ANY) < 0)
		return -1;

	type = git_object_type(obj);
	git_object_free(obj);

	if (type != GIT_OBJ_COMMIT) {
		giterr_set(GITERR_INVALID, "Object is no commit object");
		return -1;
	}

105
	commit = git_revwalk__commit_lookup(walk, oid);
106
	if (commit == NULL)
107
		return -1; /* error already reported by failed lookup */
108

109 110 111 112
	commit->uninteresting = uninteresting;
	if (walk->one == NULL && !uninteresting) {
		walk->one = commit;
	} else {
113 114
		if (git_vector_insert(&walk->twos, commit) < 0)
			return -1;
115 116
	}

117
	return 0;
118 119
}

120 121 122 123 124
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
	return push_commit(walk, oid, 0);
}
125

126

127 128 129 130 131
int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
{
	assert(walk && oid);
	return push_commit(walk, oid, 1);
}
132

133 134
static int push_ref(git_revwalk *walk, const char *refname, int hide)
{
135
	git_oid oid;
136

137
	if (git_reference_name_to_id(&oid, walk->repo, refname) < 0)
138 139
		return -1;

140
	return push_commit(walk, &oid, hide);
141 142
}

143 144 145 146 147 148 149 150 151
struct push_cb_data {
	git_revwalk *walk;
	int hide;
};

static int push_glob_cb(const char *refname, void *data_)
{
	struct push_cb_data *data = (struct push_cb_data *)data_;

152
	return push_ref(data->walk, refname, data->hide);
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
}

static int push_glob(git_revwalk *walk, const char *glob, int hide)
{
	git_buf buf = GIT_BUF_INIT;
	struct push_cb_data data;
	regex_t preg;

	assert(walk && glob);

	/* refs/ is implied if not given in the glob */
	if (strncmp(glob, GIT_REFS_DIR, strlen(GIT_REFS_DIR))) {
		git_buf_printf(&buf, GIT_REFS_DIR "%s", glob);
	} else {
		git_buf_puts(&buf, glob);
	}

	/* If no '?', '*' or '[' exist, we append '/ *' to the glob */
	memset(&preg, 0x0, sizeof(regex_t));
	if (regcomp(&preg, "[?*[]", REG_EXTENDED)) {
173 174 175
		giterr_set(GITERR_OS, "Regex failed to compile");
		git_buf_free(&buf);
		return -1;
176 177 178 179 180
	}

	if (regexec(&preg, glob, 0, NULL, 0))
		git_buf_puts(&buf, "/*");

181 182
	if (git_buf_oom(&buf))
		goto on_error;
183 184 185 186

	data.walk = walk;
	data.hide = hide;

187 188
	if (git_reference_foreach_glob(
		walk->repo, git_buf_cstr(&buf), GIT_REF_LISTALL, push_glob_cb, &data) < 0)
189
		goto on_error;
190 191 192

	regfree(&preg);
	git_buf_free(&buf);
193 194 195 196 197 198
	return 0;

on_error:
	regfree(&preg);
	git_buf_free(&buf);
	return -1;
199 200 201 202 203 204 205 206 207 208 209 210 211 212
}

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

213 214 215
int git_revwalk_push_head(git_revwalk *walk)
{
	assert(walk);
216
	return push_ref(walk, GIT_HEAD_FILE, 0);
217 218 219 220 221
}

int git_revwalk_hide_head(git_revwalk *walk)
{
	assert(walk);
222 223 224 225 226 227 228 229 230 231 232 233 234
	return push_ref(walk, GIT_HEAD_FILE, 1);
}

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

int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
	return push_ref(walk, refname, 1);
235 236
}

237
static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
238
{
239 240
	return git_pqueue_insert(&walk->iterator_time, commit);
}
241

242
static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
243
{
244
	return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
245
}
246

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

252
	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
253
		if ((error = process_commit_parents(walk, next)) < 0)
254
			return error;
255

256 257
		if (!next->uninteresting) {
			*object_out = next;
258
			return 0;
259
		}
260
	}
261

Russell Belfer committed
262 263
	giterr_clear();
	return GIT_ITEROVER;
264 265
}

266
static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
267
{
268
	int error;
269
	git_commit_list_node *next;
270

271
	while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL) {
272
		if ((error = process_commit_parents(walk, next)) < 0)
273
			return error;
274

275 276
		if (!next->uninteresting) {
			*object_out = next;
277
			return 0;
278
		}
279 280
	}

Russell Belfer committed
281 282
	giterr_clear();
	return GIT_ITEROVER;
283
}
284

285
static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
286
{
287
	git_commit_list_node *next;
288
	unsigned short i;
289

290
	for (;;) {
291
		next = git_commit_list_pop(&walk->iterator_topo);
Russell Belfer committed
292 293 294 295
		if (next == NULL) {
			giterr_clear();
			return GIT_ITEROVER;
		}
296

297 298 299 300
		if (next->in_degree > 0) {
			next->topo_delay = 1;
			continue;
		}
301

302
		for (i = 0; i < next->out_degree; ++i) {
303
			git_commit_list_node *parent = next->parents[i];
304

305 306
			if (--parent->in_degree == 0 && parent->topo_delay) {
				parent->topo_delay = 0;
307
				if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL)
308
					return -1;
309 310
			}
		}
311

312
		*object_out = next;
313
		return 0;
314
	}
315 316
}

317
static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
318
{
319
	*object_out = git_commit_list_pop(&walk->iterator_reverse);
Russell Belfer committed
320
	return *object_out ? 0 : GIT_ITEROVER;
321
}
322

323

324 325 326
static int prepare_walk(git_revwalk *walk)
{
	int error;
327
	unsigned int i;
328 329
	git_commit_list_node *next, *two;
	git_commit_list *bases = NULL;
330

331 332 333 334
	/*
	 * If walk->one is NULL, there were no positive references,
	 * so we know that the walk is already over.
	 */
Russell Belfer committed
335 336 337 338
	if (walk->one == NULL) {
		giterr_clear();
		return GIT_ITEROVER;
	}
339

340
	/* first figure out what the merge bases are */
341
	if (git_merge__bases_many(&bases, walk, walk->one, &walk->twos) < 0)
342
		return -1;
343

344
	git_commit_list_free(&bases);
345 346
	if (process_commit(walk, walk->one, walk->one->uninteresting) < 0)
		return -1;
347 348

	git_vector_foreach(&walk->twos, i, two) {
349 350
		if (process_commit(walk, two, two->uninteresting) < 0)
			return -1;
351
	}
352

353 354
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
		unsigned short i;
355

356
		while ((error = walk->get_next(&next, walk)) == 0) {
357
			for (i = 0; i < next->out_degree; ++i) {
358
				git_commit_list_node *parent = next->parents[i];
359 360
				parent->in_degree++;
			}
361

362
			if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
363
				return -1;
364
		}
365

Russell Belfer committed
366
		if (error != GIT_ITEROVER)
367
			return error;
368

369 370
		walk->get_next = &revwalk_next_toposort;
	}
371

372
	if (walk->sorting & GIT_SORT_REVERSE) {
373

374
		while ((error = walk->get_next(&next, walk)) == 0)
375
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
376
				return -1;
377

Russell Belfer committed
378
		if (error != GIT_ITEROVER)
379
			return error;
380

381 382
		walk->get_next = &revwalk_next_reverse;
	}
383

384
	walk->walking = 1;
385
	return 0;
386
}
387 388


389 390 391 392 393
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
	git_revwalk *walk;

	walk = git__malloc(sizeof(git_revwalk));
394
	GITERR_CHECK_ALLOC(walk);
395 396 397

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

398
	walk->commits = git_oidmap_alloc();
399
	GITERR_CHECK_ALLOC(walk->commits);
400

401
	if (git_pqueue_init(&walk->iterator_time, 8, git_commit_list_time_cmp) < 0 ||
402
		git_vector_init(&walk->twos, 4, NULL) < 0 ||
403 404
		git_pool_init(&walk->commit_pool, 1,
			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
405
		return -1;
406 407 408 409 410 411

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

	walk->repo = repo;

412
	if (git_repository_odb(&walk->odb, repo) < 0) {
413
		git_revwalk_free(walk);
414
		return -1;
415 416
	}

417
	*revwalk_out = walk;
418
	return 0;
419 420 421 422 423 424 425 426
}

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

	git_revwalk_reset(walk);
427
	git_odb_free(walk->odb);
428

429
	git_oidmap_free(walk->commits);
430
	git_pool_clear(&walk->commit_pool);
431
	git_pqueue_free(&walk->iterator_time);
432
	git_vector_free(&walk->twos);
433
	git__free(walk);
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
}

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

460 461 462
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
463
	git_commit_list_node *next;
464

465
	assert(walk && oid);
466

467
	if (!walk->walking) {
468
		if ((error = prepare_walk(walk)) < 0)
469
			return error;
470
	}
471

472
	error = walk->get_next(&next, walk);
473

Russell Belfer committed
474
	if (error == GIT_ITEROVER) {
475
		git_revwalk_reset(walk);
Russell Belfer committed
476 477
		giterr_clear();
		return GIT_ITEROVER;
478
	}
479

480 481
	if (!error)
		git_oid_cpy(oid, &next->oid);
482

483
	return error;
484 485
}

486
void git_revwalk_reset(git_revwalk *walk)
487
{
488
	git_commit_list_node *commit;
489

490
	assert(walk);
491

492
	kh_foreach_value(walk->commits, commit, {
493 494 495
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
496
		commit->uninteresting = 0;
497
		});
498

499
	git_pqueue_clear(&walk->iterator_time);
500 501 502
	git_commit_list_free(&walk->iterator_topo);
	git_commit_list_free(&walk->iterator_rand);
	git_commit_list_free(&walk->iterator_reverse);
503
	walk->walking = 0;
504 505 506

	walk->one = NULL;
	git_vector_clear(&walk->twos);
507
}
508