revwalk.c 11.2 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
#include <regex.h>

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
static void mark_uninteresting(git_commit_list_node *commit)
45
{
46 47
	unsigned short i;
	assert(commit);
48

49
	commit->uninteresting = 1;
50

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

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

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

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

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

70
	commit->seen = 1;
71

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

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

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

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

86
	return error;
87 88
}

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

95 96 97 98 99 100 101 102 103 104 105
	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;
	}

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

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

118
	return 0;
119 120
}

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

127

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

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

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

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

144 145 146 147 148 149 150 151 152
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_;

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

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)) {
174 175 176
		giterr_set(GITERR_OS, "Regex failed to compile");
		git_buf_free(&buf);
		return -1;
177 178 179 180 181
	}

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

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

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

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

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

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

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

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

int git_revwalk_hide_head(git_revwalk *walk)
{
	assert(walk);
223 224 225 226 227 228 229 230 231
	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);
}

232 233
int git_revwalk_push_range(git_revwalk *walk, const char *range)
{
234
	git_revspec revspec;
235 236
	int error = 0;

237
	if ((error = git_revparse(&revspec, walk->repo, range)))
238
		return error;
Vicent Marti committed
239

240
	if (revspec.flags & GIT_REVPARSE_MERGE_BASE) {
241 242 243 244 245
		/* TODO: support "<commit>...<commit>" */
		giterr_set(GITERR_INVALID, "Symmetric differences not implemented in revwalk");
		return GIT_EINVALIDSPEC;
	}

246
	if ((error = push_commit(walk, git_object_id(revspec.from), 1)))
247 248
		goto out;

249
	error = push_commit(walk, git_object_id(revspec.to), 0);
Vicent Marti committed
250 251

out:
252 253
	git_object_free(revspec.from);
	git_object_free(revspec.to);
254 255 256
	return error;
}

257 258 259 260
int git_revwalk_hide_ref(git_revwalk *walk, const char *refname)
{
	assert(walk && refname);
	return push_ref(walk, refname, 1);
261 262
}

263
static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit)
264
{
265 266
	return git_pqueue_insert(&walk->iterator_time, commit);
}
267

268
static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit)
269
{
270
	return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1;
271
}
272

273
static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
274 275
{
	int error;
276
	git_commit_list_node *next;
277

278
	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
279
		if ((error = process_commit_parents(walk, next)) < 0)
280
			return error;
281

282 283
		if (!next->uninteresting) {
			*object_out = next;
284
			return 0;
285
		}
286
	}
287

Russell Belfer committed
288 289
	giterr_clear();
	return GIT_ITEROVER;
290 291
}

292
static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
293
{
294
	int error;
295
	git_commit_list_node *next;
296

297
	while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL) {
298
		if ((error = process_commit_parents(walk, next)) < 0)
299
			return error;
300

301 302
		if (!next->uninteresting) {
			*object_out = next;
303
			return 0;
304
		}
305 306
	}

Russell Belfer committed
307 308
	giterr_clear();
	return GIT_ITEROVER;
309
}
310

311
static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
312
{
313
	git_commit_list_node *next;
314
	unsigned short i;
315

316
	for (;;) {
317
		next = git_commit_list_pop(&walk->iterator_topo);
Russell Belfer committed
318 319 320 321
		if (next == NULL) {
			giterr_clear();
			return GIT_ITEROVER;
		}
322

323 324 325 326
		if (next->in_degree > 0) {
			next->topo_delay = 1;
			continue;
		}
327

328
		for (i = 0; i < next->out_degree; ++i) {
329
			git_commit_list_node *parent = next->parents[i];
330

331 332
			if (--parent->in_degree == 0 && parent->topo_delay) {
				parent->topo_delay = 0;
333
				if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL)
334
					return -1;
335 336
			}
		}
337

338
		*object_out = next;
339
		return 0;
340
	}
341 342
}

343
static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
344
{
345
	*object_out = git_commit_list_pop(&walk->iterator_reverse);
Russell Belfer committed
346
	return *object_out ? 0 : GIT_ITEROVER;
347
}
348

349

350 351 352
static int prepare_walk(git_revwalk *walk)
{
	int error;
353
	unsigned int i;
354 355
	git_commit_list_node *next, *two;
	git_commit_list *bases = NULL;
356

357 358 359 360
	/*
	 * If walk->one is NULL, there were no positive references,
	 * so we know that the walk is already over.
	 */
Russell Belfer committed
361 362 363 364
	if (walk->one == NULL) {
		giterr_clear();
		return GIT_ITEROVER;
	}
365

366
	/* first figure out what the merge bases are */
367
	if (git_merge__bases_many(&bases, walk, walk->one, &walk->twos) < 0)
368
		return -1;
369

370
	git_commit_list_free(&bases);
371 372
	if (process_commit(walk, walk->one, walk->one->uninteresting) < 0)
		return -1;
373 374

	git_vector_foreach(&walk->twos, i, two) {
375 376
		if (process_commit(walk, two, two->uninteresting) < 0)
			return -1;
377
	}
378

379 380
	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
		unsigned short i;
381

382
		while ((error = walk->get_next(&next, walk)) == 0) {
383
			for (i = 0; i < next->out_degree; ++i) {
384
				git_commit_list_node *parent = next->parents[i];
385 386
				parent->in_degree++;
			}
387

388
			if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
389
				return -1;
390
		}
391

Russell Belfer committed
392
		if (error != GIT_ITEROVER)
393
			return error;
394

395 396
		walk->get_next = &revwalk_next_toposort;
	}
397

398
	if (walk->sorting & GIT_SORT_REVERSE) {
399

400
		while ((error = walk->get_next(&next, walk)) == 0)
401
			if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL)
402
				return -1;
403

Russell Belfer committed
404
		if (error != GIT_ITEROVER)
405
			return error;
406

407 408
		walk->get_next = &revwalk_next_reverse;
	}
409

410
	walk->walking = 1;
411
	return 0;
412
}
413 414


415 416 417 418 419
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
	git_revwalk *walk;

	walk = git__malloc(sizeof(git_revwalk));
420
	GITERR_CHECK_ALLOC(walk);
421 422 423

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

424
	walk->commits = git_oidmap_alloc();
425
	GITERR_CHECK_ALLOC(walk->commits);
426

427
	if (git_pqueue_init(&walk->iterator_time, 8, git_commit_list_time_cmp) < 0 ||
428
		git_vector_init(&walk->twos, 4, NULL) < 0 ||
429 430
		git_pool_init(&walk->commit_pool, 1,
			git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0)
431
		return -1;
432 433 434 435 436 437

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

	walk->repo = repo;

438
	if (git_repository_odb(&walk->odb, repo) < 0) {
439
		git_revwalk_free(walk);
440
		return -1;
441 442
	}

443
	*revwalk_out = walk;
444
	return 0;
445 446 447 448 449 450 451 452
}

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

	git_revwalk_reset(walk);
453
	git_odb_free(walk->odb);
454

455
	git_oidmap_free(walk->commits);
456
	git_pool_clear(&walk->commit_pool);
457
	git_pqueue_free(&walk->iterator_time);
458
	git_vector_free(&walk->twos);
459
	git__free(walk);
460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485
}

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

486 487 488
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
	int error;
489
	git_commit_list_node *next;
490

491
	assert(walk && oid);
492

493
	if (!walk->walking) {
494
		if ((error = prepare_walk(walk)) < 0)
495
			return error;
496
	}
497

498
	error = walk->get_next(&next, walk);
499

Russell Belfer committed
500
	if (error == GIT_ITEROVER) {
501
		git_revwalk_reset(walk);
Russell Belfer committed
502 503
		giterr_clear();
		return GIT_ITEROVER;
504
	}
505

506 507
	if (!error)
		git_oid_cpy(oid, &next->oid);
508

509
	return error;
510 511
}

512
void git_revwalk_reset(git_revwalk *walk)
513
{
514
	git_commit_list_node *commit;
515

516
	assert(walk);
517

518
	kh_foreach_value(walk->commits, commit, {
519 520 521
		commit->seen = 0;
		commit->in_degree = 0;
		commit->topo_delay = 0;
522
		commit->uninteresting = 0;
523
		});
524

525
	git_pqueue_clear(&walk->iterator_time);
526 527 528
	git_commit_list_free(&walk->iterator_topo);
	git_commit_list_free(&walk->iterator_rand);
	git_commit_list_free(&walk->iterator_reverse);
529
	walk->walking = 0;
530 531 532

	walk->one = NULL;
	git_vector_clear(&walk->twos);
533
}
534