merge.c 88.8 KB
Newer Older
Edward Thomson committed
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
Edward Thomson committed
3 4 5 6 7
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

8 9
#include "merge.h"

Edward Thomson committed
10
#include "posix.h"
11
#include "str.h"
Edward Thomson committed
12
#include "repository.h"
13
#include "revwalk.h"
Edward Thomson committed
14
#include "commit_list.h"
15
#include "fs_path.h"
Edward Thomson committed
16
#include "refs.h"
Edward Thomson committed
17 18 19 20
#include "object.h"
#include "iterator.h"
#include "refs.h"
#include "diff.h"
21 22
#include "diff_generate.h"
#include "diff_tform.h"
Edward Thomson committed
23 24 25
#include "checkout.h"
#include "tree.h"
#include "blob.h"
Edward Thomson committed
26
#include "oid.h"
27 28
#include "index.h"
#include "filebuf.h"
29
#include "config.h"
30
#include "oidarray.h"
31
#include "annotated_commit.h"
32
#include "commit.h"
33
#include "oidarray.h"
34
#include "merge_driver.h"
35 36
#include "oidmap.h"
#include "array.h"
Edward Thomson committed
37 38

#include "git2/types.h"
Edward Thomson committed
39
#include "git2/repository.h"
Edward Thomson committed
40 41
#include "git2/object.h"
#include "git2/commit.h"
Edward Thomson committed
42
#include "git2/merge.h"
Edward Thomson committed
43
#include "git2/refs.h"
Edward Thomson committed
44
#include "git2/reset.h"
Edward Thomson committed
45 46 47 48
#include "git2/checkout.h"
#include "git2/signature.h"
#include "git2/config.h"
#include "git2/tree.h"
49
#include "git2/oidarray.h"
50
#include "git2/annotated_commit.h"
51
#include "git2/sys/index.h"
52
#include "git2/sys/hashsig.h"
Edward Thomson committed
53 54

#define GIT_MERGE_INDEX_ENTRY_EXISTS(X)	((X).mode != 0)
Edward Thomson committed
55
#define GIT_MERGE_INDEX_ENTRY_ISFILE(X) S_ISREG((X).mode)
Edward Thomson committed
56

57

Edward Thomson committed
58 59 60 61 62 63 64 65 66 67 68 69 70
typedef enum {
	TREE_IDX_ANCESTOR = 0,
	TREE_IDX_OURS = 1,
	TREE_IDX_THEIRS = 2
} merge_tree_index_t;

/* Tracks D/F conflicts */
struct merge_diff_df_data {
	const char *df_path;
	const char *prev_path;
	git_merge_diff *prev_conflict;
};

71 72 73 74 75 76 77 78 79 80
/*
 * This acts as a negative cache entry marker. In case we've tried to calculate
 * similarity metrics for a given blob already but `git_hashsig` determined
 * that it's too small in order to have a meaningful hash signature, we will
 * insert the address of this marker instead of `NULL`. Like this, we can
 * easily check whether we have checked a gien entry already and skip doing the
 * calculation again and again.
 */
static int cache_invalid_marker;

Edward Thomson committed
81 82
/* Merge base computation */

83
static int merge_bases_many(git_commit_list **out, git_revwalk **walk_out, git_repository *repo, size_t length, const git_oid input_array[])
84
{
85
	git_revwalk *walk = NULL;
86 87
	git_vector list;
	git_commit_list *result = NULL;
88
	git_commit_list_node *commit;
89 90 91 92
	int error = -1;
	unsigned int i;

	if (length < 2) {
93
		git_error_set(GIT_ERROR_INVALID, "at least two commits are required to find an ancestor");
94 95 96 97 98 99 100
		return -1;
	}

	if (git_vector_init(&list, length - 1, NULL) < 0)
		return -1;

	if (git_revwalk_new(&walk, repo) < 0)
101
		goto on_error;
102 103

	for (i = 1; i < length; i++) {
104
		commit = git_revwalk__commit_lookup(walk, &input_array[i]);
105
		if (commit == NULL)
106
			goto on_error;
107 108 109 110

		git_vector_insert(&list, commit);
	}

111
	commit = git_revwalk__commit_lookup(walk, &input_array[0]);
112
	if (commit == NULL)
113
		goto on_error;
114

115
	if (git_merge__bases_many(&result, walk, commit, &list, 0) < 0)
116
		goto on_error;
117 118

	if (!result) {
119
		git_error_set(GIT_ERROR_MERGE, "no merge base found");
120
		error = GIT_ENOTFOUND;
121
		goto on_error;
122 123
	}

124 125
	*out = result;
	*walk_out = walk;
126

127 128
	git_vector_free(&list);
	return 0;
129

130
on_error:
131
	git_vector_free(&list);
132
	git_revwalk_free(walk);
133 134 135
	return error;
}

136
int git_merge_base_many(git_oid *out, git_repository *repo, size_t length, const git_oid input_array[])
137 138
{
	git_revwalk *walk;
139 140
	git_commit_list *result = NULL;
	int error = 0;
141

Edward Thomson committed
142 143 144
	GIT_ASSERT_ARG(out);
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(input_array);
145

146 147
	if ((error = merge_bases_many(&result, &walk, repo, length, input_array)) < 0)
		return error;
148

149
	git_oid_cpy(out, &result->item->oid);
150

151 152
	git_commit_list_free(&result);
	git_revwalk_free(walk);
153

154 155
	return 0;
}
156

157 158 159 160 161 162
int git_merge_bases_many(git_oidarray *out, git_repository *repo, size_t length, const git_oid input_array[])
{
	git_revwalk *walk;
	git_commit_list *list, *result = NULL;
	int error = 0;
	git_array_oid_t array;
163

Edward Thomson committed
164 165 166
	GIT_ASSERT_ARG(out);
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(input_array);
167

168 169
	if ((error = merge_bases_many(&result, &walk, repo, length, input_array)) < 0)
		return error;
170 171 172

	git_array_init(array);

173 174
	list = result;
	while (list) {
175
		git_oid *id = git_array_alloc(array);
176 177
		if (id == NULL) {
			error = -1;
178
			goto cleanup;
179
		}
180

181 182
		git_oid_cpy(id, &list->item->oid);
		list = list->next;
183 184 185 186 187 188 189
	}

	git_oidarray__from_array(out, &array);

cleanup:
	git_commit_list_free(&result);
	git_revwalk_free(walk);
190

191 192 193
	return error;
}

194 195 196 197 198 199
int git_merge_base_octopus(git_oid *out, git_repository *repo, size_t length, const git_oid input_array[])
{
	git_oid result;
	unsigned int i;
	int error = -1;

Edward Thomson committed
200 201 202
	GIT_ASSERT_ARG(out);
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(input_array);
203 204

	if (length < 2) {
205
		git_error_set(GIT_ERROR_INVALID, "at least two commits are required to find an ancestor");
206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
		return -1;
	}

	result = input_array[0];
	for (i = 1; i < length; i++) {
		error = git_merge_base(&result, repo, &result, &input_array[i]);
		if (error < 0)
			return error;
	}

	*out = result;

	return 0;
}

221
static int merge_bases(git_commit_list **out, git_revwalk **walk_out, git_repository *repo, const git_oid *one, const git_oid *two)
222 223 224 225 226 227 228 229 230 231
{
	git_revwalk *walk;
	git_vector list;
	git_commit_list *result = NULL;
	git_commit_list_node *commit;
	void *contents[1];

	if (git_revwalk_new(&walk, repo) < 0)
		return -1;

232
	commit = git_revwalk__commit_lookup(walk, two);
233 234 235 236 237 238 239 240 241
	if (commit == NULL)
		goto on_error;

	/* This is just one value, so we can do it on the stack */
	memset(&list, 0x0, sizeof(git_vector));
	contents[0] = commit;
	list.length = 1;
	list.contents = contents;

242
	commit = git_revwalk__commit_lookup(walk, one);
243 244 245
	if (commit == NULL)
		goto on_error;

246
	if (git_merge__bases_many(&result, walk, commit, &list, 0) < 0)
247 248 249 250
		goto on_error;

	if (!result) {
		git_revwalk_free(walk);
251
		git_error_set(GIT_ERROR_MERGE, "no merge base found");
252 253 254
		return GIT_ENOTFOUND;
	}

255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274
	*out = result;
	*walk_out = walk;

	return 0;

on_error:
	git_revwalk_free(walk);
	return -1;

}

int git_merge_base(git_oid *out, git_repository *repo, const git_oid *one, const git_oid *two)
{
	int error;
	git_revwalk *walk;
	git_commit_list *result;

	if ((error = merge_bases(&result, &walk, repo, one, two)) < 0)
		return error;

275 276 277 278 279
	git_oid_cpy(out, &result->item->oid);
	git_commit_list_free(&result);
	git_revwalk_free(walk);

	return 0;
280 281 282 283 284
}

int git_merge_bases(git_oidarray *out, git_repository *repo, const git_oid *one, const git_oid *two)
{
	int error;
285
	git_revwalk *walk;
286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308
	git_commit_list *result, *list;
	git_array_oid_t array;

	git_array_init(array);

	if ((error = merge_bases(&result, &walk, repo, one, two)) < 0)
		return error;

	list = result;
	while (list) {
		git_oid *id = git_array_alloc(array);
		if (id == NULL)
			goto on_error;

		git_oid_cpy(id, &list->item->oid);
		list = list->next;
	}

	git_oidarray__from_array(out, &array);
	git_commit_list_free(&result);
	git_revwalk_free(walk);

	return 0;
309 310

on_error:
311
	git_commit_list_free(&result);
312 313 314 315 316 317
	git_revwalk_free(walk);
	return -1;
}

static int interesting(git_pqueue *list)
{
318 319 320 321
	size_t i;

	for (i = 0; i < git_pqueue_size(list); i++) {
		git_commit_list_node *commit = git_pqueue_get(list, i);
322 323 324 325 326 327 328
		if ((commit->flags & STALE) == 0)
			return 1;
	}

	return 0;
}

329
static int clear_commit_marks_1(git_commit_list **plist,
330
		git_commit_list_node *commit, unsigned int mark)
331
{
332 333
	while (commit) {
		unsigned int i;
334

335
		if (!(mark & commit->flags))
336
			return 0;
337 338 339 340 341

		commit->flags &= ~mark;

		for (i = 1; i < commit->out_degree; i++) {
			git_commit_list_node *p = commit->parents[i];
342 343
			if (git_commit_list_insert(p, plist) == NULL)
				return -1;
344 345
		}

346
		commit = commit->out_degree ? commit->parents[0] : NULL;
347
	}
348 349

	return 0;
350
}
351

352
static int clear_commit_marks_many(git_vector *commits, unsigned int mark)
353 354 355 356 357 358
{
	git_commit_list *list = NULL;
	git_commit_list_node *c;
	unsigned int i;

	git_vector_foreach(commits, i, c) {
359 360
		if (git_commit_list_insert(c, &list) == NULL)
			return -1;
361 362
	}

363
	while (list)
364 365 366
		if (clear_commit_marks_1(&list, git_commit_list_pop(&list), mark) < 0)
			return -1;
	return 0;
367
}
368

369
static int clear_commit_marks(git_commit_list_node *commit, unsigned int mark)
370 371
{
	git_commit_list *list = NULL;
372 373
	if (git_commit_list_insert(commit, &list) == NULL)
		return -1;
374
	while (list)
375 376 377
		if (clear_commit_marks_1(&list, git_commit_list_pop(&list), mark) < 0)
			return -1;
	return 0;
378 379 380
}

static int paint_down_to_common(
381 382 383 384 385
		git_commit_list **out,
		git_revwalk *walk,
		git_commit_list_node *one,
		git_vector *twos,
		uint32_t minimum_generation)
386 387 388 389 390 391 392 393
{
	git_pqueue list;
	git_commit_list *result = NULL;
	git_commit_list_node *two;

	int error;
	unsigned int i;

394
	if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_generation_cmp) < 0)
Edward Thomson committed
395
		return -1;
396 397 398 399 400 401

	one->flags |= PARENT1;
	if (git_pqueue_insert(&list, one) < 0)
		return -1;

	git_vector_foreach(twos, i, two) {
402 403 404
		if (git_commit_list_parse(walk, two) < 0)
			return -1;

405 406 407 408 409 410 411
		two->flags |= PARENT2;
		if (git_pqueue_insert(&list, two) < 0)
			return -1;
	}

	/* as long as there are non-STALE commits */
	while (interesting(&list)) {
412
		git_commit_list_node *commit = git_pqueue_pop(&list);
413 414
		int flags;

415 416
		if (commit == NULL)
			break;
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432

		flags = commit->flags & (PARENT1 | PARENT2 | STALE);
		if (flags == (PARENT1 | PARENT2)) {
			if (!(commit->flags & RESULT)) {
				commit->flags |= RESULT;
				if (git_commit_list_insert(commit, &result) == NULL)
					return -1;
			}
			/* we mark the parents of a merge stale */
			flags |= STALE;
		}

		for (i = 0; i < commit->out_degree; i++) {
			git_commit_list_node *p = commit->parents[i];
			if ((p->flags & flags) == flags)
				continue;
433 434
			if (p->generation < minimum_generation)
				continue;
435 436 437 438 439 440 441 442 443 444 445

			if ((error = git_commit_list_parse(walk, p)) < 0)
				return error;

			p->flags |= flags;
			if (git_pqueue_insert(&list, p) < 0)
				return -1;
		}
	}

	git_pqueue_free(&list);
446 447 448 449
	*out = result;
	return 0;
}

450
static int remove_redundant(git_revwalk *walk, git_vector *commits, uint32_t minimum_generation)
451 452 453 454 455 456 457 458
{
	git_vector work = GIT_VECTOR_INIT;
	unsigned char *redundant;
	unsigned int *filled_index;
	unsigned int i, j;
	int error = 0;

	redundant = git__calloc(commits->length, 1);
459
	GIT_ERROR_CHECK_ALLOC(redundant);
460
	filled_index = git__calloc((commits->length - 1), sizeof(unsigned int));
461
	GIT_ERROR_CHECK_ALLOC(filled_index);
462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485

	for (i = 0; i < commits->length; ++i) {
		if ((error = git_commit_list_parse(walk, commits->contents[i])) < 0)
			goto done;
	}

	for (i = 0; i < commits->length; ++i) {
		git_commit_list *common = NULL;
		git_commit_list_node *commit = commits->contents[i];

		if (redundant[i])
			continue;

		git_vector_clear(&work);

		for (j = 0; j < commits->length; j++) {
			if (i == j || redundant[j])
				continue;

			filled_index[work.length] = j;
			if ((error = git_vector_insert(&work, commits->contents[j])) < 0)
				goto done;
		}

486
		error = paint_down_to_common(&common, walk, commit, &work, minimum_generation);
487 488 489 490 491 492 493 494 495 496 497 498 499
		if (error < 0)
			goto done;

		if (commit->flags & PARENT2)
			redundant[i] = 1;

		for (j = 0; j < work.length; j++) {
			git_commit_list_node *w = work.contents[j];
			if (w->flags & PARENT1)
				redundant[filled_index[j]] = 1;
		}

		git_commit_list_free(&common);
500 501 502 503

		if ((error = clear_commit_marks(commit, ALL_FLAGS)) < 0 ||
		    (error = clear_commit_marks_many(&work, ALL_FLAGS)) < 0)
				goto done;
504 505 506 507 508 509 510 511 512 513 514 515 516 517
	}

	for (i = 0; i < commits->length; ++i) {
		if (redundant[i])
			commits->contents[i] = NULL;
	}

done:
	git__free(redundant);
	git__free(filled_index);
	git_vector_free(&work);
	return error;
}

518 519 520 521 522 523
int git_merge__bases_many(
		git_commit_list **out,
		git_revwalk *walk,
		git_commit_list_node *one,
		git_vector *twos,
		uint32_t minimum_generation)
524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544
{
	int error;
	unsigned int i;
	git_commit_list_node *two;
	git_commit_list *result = NULL, *tmp = NULL;

	/* If there's only the one commit, there can be no merge bases */
	if (twos->length == 0) {
		*out = NULL;
		return 0;
	}

	/* if the commit is repeated, we have a our merge base already */
	git_vector_foreach(twos, i, two) {
		if (one == two)
			return git_commit_list_insert(one, out) ? 0 : -1;
	}

	if (git_commit_list_parse(walk, one) < 0)
		return -1;

545
	error = paint_down_to_common(&result, walk, one, twos, minimum_generation);
546 547
	if (error < 0)
		return error;
548 549 550 551 552 553

	/* filter out any stale commits in the results */
	tmp = result;
	result = NULL;

	while (tmp) {
554 555 556
		git_commit_list_node *c = git_commit_list_pop(&tmp);
		if (!(c->flags & STALE))
			if (git_commit_list_insert_by_date(c, &result) == NULL)
557
				return -1;
558 559
	}

Vicent Marti committed
560 561 562 563
	/*
	 * more than one merge base -- see if there are redundant merge
	 * bases and remove them
	 */
564 565 566 567 568 569
	if (result && result->next) {
		git_vector redundant = GIT_VECTOR_INIT;

		while (result)
			git_vector_insert(&redundant, git_commit_list_pop(&result));

570 571
		if ((error = clear_commit_marks(one, ALL_FLAGS)) < 0 ||
		    (error = clear_commit_marks_many(twos, ALL_FLAGS)) < 0 ||
572
		    (error = remove_redundant(walk, &redundant, minimum_generation)) < 0) {
573 574 575 576 577 578 579 580
			git_vector_free(&redundant);
			return error;
		}

		git_vector_foreach(&redundant, i, two) {
			if (two != NULL)
				git_commit_list_insert_by_date(two, &result);
		}
581

582
		git_vector_free(&redundant);
583 584 585 586 587
	}

	*out = result;
	return 0;
}
588

589 590
int git_repository_mergehead_foreach(
	git_repository *repo,
591 592 593
	git_repository_mergehead_foreach_cb cb,
	void *payload)
{
594
	git_str merge_head_path = GIT_STR_INIT, merge_head_file = GIT_STR_INIT;
595 596 597 598 599
	char *buffer, *line;
	size_t line_num = 1;
	git_oid oid;
	int error = 0;

Edward Thomson committed
600 601
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(cb);
602

603
	if ((error = git_str_joinpath(&merge_head_path, repo->gitdir,
604 605 606 607
		GIT_MERGE_HEAD_FILE)) < 0)
		return error;

	if ((error = git_futils_readbuffer(&merge_head_file,
608
		git_str_cstr(&merge_head_path))) < 0)
609 610 611 612 613 614
		goto cleanup;

	buffer = merge_head_file.ptr;

	while ((line = git__strsep(&buffer, "\n")) != NULL) {
		if (strlen(line) != GIT_OID_HEXSZ) {
615
			git_error_set(GIT_ERROR_INVALID, "unable to parse OID - invalid length");
616 617 618 619 620 621 622
			error = -1;
			goto cleanup;
		}

		if ((error = git_oid_fromstr(&oid, line)) < 0)
			goto cleanup;

623
		if ((error = cb(&oid, payload)) != 0) {
624
			git_error_set_after_callback(error);
625 626 627 628 629 630 631
			goto cleanup;
		}

		++line_num;
	}

	if (*buffer) {
632
		git_error_set(GIT_ERROR_MERGE, "no EOL at line %"PRIuZ, line_num);
633 634 635 636 637
		error = -1;
		goto cleanup;
	}

cleanup:
638 639
	git_str_dispose(&merge_head_path);
	git_str_dispose(&merge_head_file);
640 641 642

	return error;
}
Edward Thomson committed
643 644 645 646 647 648 649 650 651

GIT_INLINE(int) index_entry_cmp(const git_index_entry *a, const git_index_entry *b)
{
	int value = 0;

	if (a->path == NULL)
		return (b->path == NULL) ? 0 : 1;

	if ((value = a->mode - b->mode) == 0 &&
652
		(value = git_oid__cmp(&a->id, &b->id)) == 0)
Edward Thomson committed
653 654 655 656 657 658 659 660 661 662 663 664
		value = strcmp(a->path, b->path);

	return value;
}

/* Conflict resolution */

static int merge_conflict_resolve_trivial(
	int *resolved,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict)
{
665
	int ours_empty, theirs_empty;
Edward Thomson committed
666 667 668 669
	int ours_changed, theirs_changed, ours_theirs_differ;
	git_index_entry const *result = NULL;
	int error = 0;

Edward Thomson committed
670 671 672
	GIT_ASSERT_ARG(resolved);
	GIT_ASSERT_ARG(diff_list);
	GIT_ASSERT_ARG(conflict);
Edward Thomson committed
673 674 675 676 677 678

	*resolved = 0;

	if (conflict->type == GIT_MERGE_DIFF_DIRECTORY_FILE ||
		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
		return 0;
nulltoken committed
679

Edward Thomson committed
680 681 682 683 684 685
	if (conflict->our_status == GIT_DELTA_RENAMED ||
		conflict->their_status == GIT_DELTA_RENAMED)
		return 0;

	ours_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry);
	theirs_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry);
nulltoken committed
686

Edward Thomson committed
687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741
	ours_changed = (conflict->our_status != GIT_DELTA_UNMODIFIED);
	theirs_changed = (conflict->their_status != GIT_DELTA_UNMODIFIED);
	ours_theirs_differ = ours_changed && theirs_changed &&
		index_entry_cmp(&conflict->our_entry, &conflict->their_entry);

	/*
	 * Note: with only one ancestor, some cases are not distinct:
	 *
	 * 16: ancest:anc1/anc2, head:anc1, remote:anc2 = result:no merge
	 * 3: ancest:(empty)^, head:head, remote:(empty) = result:no merge
	 * 2: ancest:(empty)^, head:(empty), remote:remote = result:no merge
	 *
	 * Note that the two cases that take D/F conflicts into account
	 * specifically do not need to be explicitly tested, as D/F conflicts
	 * would fail the *empty* test:
	 *
	 * 3ALT: ancest:(empty)+, head:head, remote:*empty* = result:head
	 * 2ALT: ancest:(empty)+, head:*empty*, remote:remote = result:remote
	 *
	 * Note that many of these cases need not be explicitly tested, as
	 * they simply degrade to "all different" cases (eg, 11):
	 *
	 * 4: ancest:(empty)^, head:head, remote:remote = result:no merge
	 * 7: ancest:ancest+, head:(empty), remote:remote = result:no merge
	 * 9: ancest:ancest+, head:head, remote:(empty) = result:no merge
	 * 11: ancest:ancest+, head:head, remote:remote = result:no merge
	 */

	/* 5ALT: ancest:*, head:head, remote:head = result:head */
	if (ours_changed && !ours_empty && !ours_theirs_differ)
		result = &conflict->our_entry;
	/* 6: ancest:ancest+, head:(empty), remote:(empty) = result:no merge */
	else if (ours_changed && ours_empty && theirs_empty)
		*resolved = 0;
	/* 8: ancest:ancest^, head:(empty), remote:ancest = result:no merge */
	else if (ours_empty && !theirs_changed)
		*resolved = 0;
	/* 10: ancest:ancest^, head:ancest, remote:(empty) = result:no merge */
	else if (!ours_changed && theirs_empty)
		*resolved = 0;
	/* 13: ancest:ancest+, head:head, remote:ancest = result:head */
	else if (ours_changed && !theirs_changed)
		result = &conflict->our_entry;
	/* 14: ancest:ancest+, head:ancest, remote:remote = result:remote */
	else if (!ours_changed && theirs_changed)
		result = &conflict->their_entry;
	else
		*resolved = 0;

	if (result != NULL &&
		GIT_MERGE_INDEX_ENTRY_EXISTS(*result) &&
		(error = git_vector_insert(&diff_list->staged, (void *)result)) >= 0)
		*resolved = 1;

	/* Note: trivial resolution does not update the REUC. */
nulltoken committed
742

Edward Thomson committed
743 744 745 746 747 748 749 750 751 752 753 754
	return error;
}

static int merge_conflict_resolve_one_removed(
	int *resolved,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict)
{
	int ours_empty, theirs_empty;
	int ours_changed, theirs_changed;
	int error = 0;

Edward Thomson committed
755 756 757
	GIT_ASSERT_ARG(resolved);
	GIT_ASSERT_ARG(diff_list);
	GIT_ASSERT_ARG(conflict);
Edward Thomson committed
758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795

	*resolved = 0;

	if (conflict->type == GIT_MERGE_DIFF_DIRECTORY_FILE ||
		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
		return 0;

	ours_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry);
	theirs_empty = !GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry);

	ours_changed = (conflict->our_status != GIT_DELTA_UNMODIFIED);
	theirs_changed = (conflict->their_status != GIT_DELTA_UNMODIFIED);

	/* Removed in both */
	if (ours_changed && ours_empty && theirs_empty)
		*resolved = 1;
	/* Removed in ours */
	else if (ours_empty && !theirs_changed)
		*resolved = 1;
	/* Removed in theirs */
	else if (!ours_changed && theirs_empty)
		*resolved = 1;

	if (*resolved)
		git_vector_insert(&diff_list->resolved, (git_merge_diff *)conflict);

	return error;
}

static int merge_conflict_resolve_one_renamed(
	int *resolved,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict)
{
	int ours_renamed, theirs_renamed;
	int ours_changed, theirs_changed;
	git_index_entry *merged;
	int error = 0;
nulltoken committed
796

Edward Thomson committed
797 798 799
	GIT_ASSERT_ARG(resolved);
	GIT_ASSERT_ARG(diff_list);
	GIT_ASSERT_ARG(conflict);
nulltoken committed
800

Edward Thomson committed
801 802 803 804 805 806 807 808
	*resolved = 0;

	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ||
		!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry))
		return 0;

	ours_renamed = (conflict->our_status == GIT_DELTA_RENAMED);
	theirs_renamed = (conflict->their_status == GIT_DELTA_RENAMED);
nulltoken committed
809

Edward Thomson committed
810 811 812 813 814 815 816 817 818
	if (!ours_renamed && !theirs_renamed)
		return 0;

	/* Reject one file in a 2->1 conflict */
	if (conflict->type == GIT_MERGE_DIFF_BOTH_RENAMED_2_TO_1 ||
		conflict->type == GIT_MERGE_DIFF_BOTH_RENAMED_1_TO_2 ||
		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
		return 0;

819 820 821 822 823
	ours_changed = (git_oid__cmp(&conflict->ancestor_entry.id, &conflict->our_entry.id) != 0) ||
		(conflict->ancestor_entry.mode != conflict->our_entry.mode);

	theirs_changed = (git_oid__cmp(&conflict->ancestor_entry.id, &conflict->their_entry.id) != 0) ||
		(conflict->ancestor_entry.mode != conflict->their_entry.mode);
nulltoken committed
824

Edward Thomson committed
825 826
	/* if both are modified (and not to a common target) require a merge */
	if (ours_changed && theirs_changed &&
827
		git_oid__cmp(&conflict->our_entry.id, &conflict->their_entry.id) != 0)
Edward Thomson committed
828 829
		return 0;

830
	if ((merged = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry))) == NULL)
Edward Thomson committed
831
		return -1;
nulltoken committed
832

Edward Thomson committed
833 834 835 836 837 838 839 840 841
	if (ours_changed)
		memcpy(merged, &conflict->our_entry, sizeof(git_index_entry));
	else
		memcpy(merged, &conflict->their_entry, sizeof(git_index_entry));

	if (ours_renamed)
		merged->path = conflict->our_entry.path;
	else
		merged->path = conflict->their_entry.path;
nulltoken committed
842

Edward Thomson committed
843
	*resolved = 1;
nulltoken committed
844

Edward Thomson committed
845 846
	git_vector_insert(&diff_list->staged, merged);
	git_vector_insert(&diff_list->resolved, (git_merge_diff *)conflict);
nulltoken committed
847

Edward Thomson committed
848 849 850
	return error;
}

851 852
static bool merge_conflict_can_resolve_contents(
	const git_merge_diff *conflict)
Edward Thomson committed
853
{
854 855
	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ||
		!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry))
856
		return false;
857

Edward Thomson committed
858 859
	/* Reject D/F conflicts */
	if (conflict->type == GIT_MERGE_DIFF_DIRECTORY_FILE)
860
		return false;
Edward Thomson committed
861

Edward Thomson committed
862 863 864 865
	/* Reject submodules. */
	if (S_ISGITLINK(conflict->ancestor_entry.mode) ||
		S_ISGITLINK(conflict->our_entry.mode) ||
		S_ISGITLINK(conflict->their_entry.mode))
866
		return false;
Edward Thomson committed
867

Edward Thomson committed
868
	/* Reject link/file conflicts. */
869 870 871 872 873
	if ((S_ISLNK(conflict->ancestor_entry.mode) ^
			S_ISLNK(conflict->our_entry.mode)) ||
		(S_ISLNK(conflict->ancestor_entry.mode) ^
			S_ISLNK(conflict->their_entry.mode)))
		return false;
Edward Thomson committed
874 875 876 877

	/* Reject name conflicts */
	if (conflict->type == GIT_MERGE_DIFF_BOTH_RENAMED_2_TO_1 ||
		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
878
		return false;
Edward Thomson committed
879 880 881 882

	if ((conflict->our_status & GIT_DELTA_RENAMED) == GIT_DELTA_RENAMED &&
		(conflict->their_status & GIT_DELTA_RENAMED) == GIT_DELTA_RENAMED &&
		strcmp(conflict->ancestor_entry.path, conflict->their_entry.path) != 0)
883 884 885 886 887 888 889
		return false;

	return true;
}

static int merge_conflict_invoke_driver(
	git_index_entry **out,
890
	const char *name,
891 892
	git_merge_driver *driver,
	git_merge_diff_list *diff_list,
893
	git_merge_driver_source *src)
894 895
{
	git_index_entry *result;
896
	git_buf buf = {0};
897 898 899 900 901 902 903 904
	const char *path;
	uint32_t mode;
	git_odb *odb = NULL;
	git_oid oid;
	int error;

	*out = NULL;

905 906
	if ((error = driver->apply(driver, &path, &mode, &buf, name, src)) < 0 ||
		(error = git_repository_odb(&odb, src->repo)) < 0 ||
907
		(error = git_odb_write(&oid, odb, buf.ptr, buf.size, GIT_OBJECT_BLOB)) < 0)
908 909 910
		goto done;

	result = git_pool_mallocz(&diff_list->pool, sizeof(git_index_entry));
911
	GIT_ERROR_CHECK_ALLOC(result);
912 913 914

	git_oid_cpy(&result->id, &oid);
	result->mode = mode;
915
	result->file_size = (uint32_t)buf.size;
916 917

	result->path = git_pool_strdup(&diff_list->pool, path);
918
	GIT_ERROR_CHECK_ALLOC(result->path);
919 920 921 922

	*out = result;

done:
923
	git_buf_dispose(&buf);
924 925 926 927 928 929 930 931 932
	git_odb_free(odb);

	return error;
}

static int merge_conflict_resolve_contents(
	int *resolved,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict,
933
	const git_merge_options *merge_opts,
934 935 936 937 938
	const git_merge_file_options *file_opts)
{
	git_merge_driver_source source = {0};
	git_merge_file_result result = {0};
	git_merge_driver *driver;
939
	git_merge_driver__builtin builtin = {{0}};
940 941
	git_index_entry *merge_result;
	git_odb *odb = NULL;
942
	const char *name;
943 944
	bool fallback = false;
	int error;
945

Edward Thomson committed
946 947 948
	GIT_ASSERT_ARG(resolved);
	GIT_ASSERT_ARG(diff_list);
	GIT_ASSERT_ARG(conflict);
949 950 951 952

	*resolved = 0;

	if (!merge_conflict_can_resolve_contents(conflict))
Edward Thomson committed
953 954
		return 0;

955
	source.repo = diff_list->repo;
956
	source.default_driver = merge_opts->default_driver;
957 958
	source.file_opts = file_opts;
	source.ancestor = GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry) ?
959
		&conflict->ancestor_entry : NULL;
960
	source.ours = GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
961
		&conflict->our_entry : NULL;
962
	source.theirs = GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
963 964
		&conflict->their_entry : NULL;

965 966
	if (file_opts->favor != GIT_MERGE_FILE_FAVOR_NORMAL) {
		/* if the user requested a particular type of resolution (via the
967 968
		 * favor flag) then let that override the gitattributes and use
		 * the builtin driver.
969
		 */
970 971 972 973 974
		name = "text";
		builtin.base.apply = git_merge_driver__builtin_apply;
		builtin.favor = file_opts->favor;

		driver = &builtin.base;
975 976
	} else {
		/* find the merge driver for this file */
977
		if ((error = git_merge_driver_for_source(&name, &driver, &source)) < 0)
978
			goto done;
979 980 981

		if (driver == NULL)
			fallback = true;
982 983
	}

984 985 986 987 988 989 990
	if (driver) {
		error = merge_conflict_invoke_driver(&merge_result, name, driver,
			diff_list, &source);

		if (error == GIT_PASSTHROUGH)
			fallback = true;
	}
nulltoken committed
991

992
	if (fallback) {
993 994
		error = merge_conflict_invoke_driver(&merge_result, "text",
			&git_merge_driver__text.base, diff_list, &source);
995
	}
Edward Thomson committed
996

997 998 999
	if (error < 0) {
		if (error == GIT_EMERGECONFLICT)
			error = 0;
Edward Thomson committed
1000

1001 1002
		goto done;
	}
nulltoken committed
1003

1004
	git_vector_insert(&diff_list->staged, merge_result);
Edward Thomson committed
1005 1006 1007 1008 1009 1010 1011
	git_vector_insert(&diff_list->resolved, (git_merge_diff *)conflict);

	*resolved = 1;

done:
	git_merge_file_result_free(&result);
	git_odb_free(odb);
nulltoken committed
1012

Edward Thomson committed
1013 1014 1015 1016 1017 1018 1019
	return error;
}

static int merge_conflict_resolve(
	int *out,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict,
1020
	const git_merge_options *merge_opts,
1021
	const git_merge_file_options *file_opts)
Edward Thomson committed
1022 1023 1024
{
	int resolved = 0;
	int error = 0;
nulltoken committed
1025

Edward Thomson committed
1026
	*out = 0;
nulltoken committed
1027

1028 1029
	if ((error = merge_conflict_resolve_trivial(
			&resolved, diff_list, conflict)) < 0)
Edward Thomson committed
1030 1031
		goto done;

1032 1033
	if (!resolved && (error = merge_conflict_resolve_one_removed(
			&resolved, diff_list, conflict)) < 0)
1034
		goto done;
nulltoken committed
1035

1036 1037
	if (!resolved && (error = merge_conflict_resolve_one_renamed(
			&resolved, diff_list, conflict)) < 0)
1038
		goto done;
Edward Thomson committed
1039

1040 1041
	if (!resolved && (error = merge_conflict_resolve_contents(
			&resolved, diff_list, conflict, merge_opts, file_opts)) < 0)
1042
		goto done;
Edward Thomson committed
1043 1044

	*out = resolved;
nulltoken committed
1045

Edward Thomson committed
1046 1047 1048 1049
done:
	return error;
}

Edward Thomson committed
1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060
/* Rename detection and coalescing */

struct merge_diff_similarity {
	unsigned char similarity;
	size_t other_idx;
};

static int index_entry_similarity_calc(
	void **out,
	git_repository *repo,
	git_index_entry *entry,
1061
	const git_merge_options *opts)
Edward Thomson committed
1062 1063 1064
{
	git_blob *blob;
	git_diff_file diff_file = {{{0}}};
1065
	git_object_size_t blobsize;
Edward Thomson committed
1066
	int error;
nulltoken committed
1067

1068 1069 1070
	if (*out || *out == &cache_invalid_marker)
		return 0;

Edward Thomson committed
1071 1072
	*out = NULL;

1073
	if ((error = git_blob_lookup(&blob, repo, &entry->id)) < 0)
Edward Thomson committed
1074
		return error;
nulltoken committed
1075

1076
	git_oid_cpy(&diff_file.id, &entry->id);
Edward Thomson committed
1077 1078 1079 1080
	diff_file.path = entry->path;
	diff_file.size = entry->file_size;
	diff_file.mode = entry->mode;
	diff_file.flags = 0;
nulltoken committed
1081

1082 1083 1084 1085 1086
	blobsize = git_blob_rawsize(blob);

	/* file too big for rename processing */
	if (!git__is_sizet(blobsize))
		return 0;
nulltoken committed
1087

Edward Thomson committed
1088
	error = opts->metric->buffer_signature(out, &diff_file,
1089
		git_blob_rawcontent(blob), (size_t)blobsize,
Edward Thomson committed
1090
		opts->metric->payload);
1091 1092
	if (error == GIT_EBUFS)
		*out = &cache_invalid_marker;
nulltoken committed
1093

Edward Thomson committed
1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105
	git_blob_free(blob);

	return error;
}

static int index_entry_similarity_inexact(
	git_repository *repo,
	git_index_entry *a,
	size_t a_idx,
	git_index_entry *b,
	size_t b_idx,
	void **cache,
1106
	const git_merge_options *opts)
Edward Thomson committed
1107 1108 1109
{
	int score = 0;
	int error = 0;
nulltoken committed
1110

1111
	if (!GIT_MODE_ISBLOB(a->mode) || !GIT_MODE_ISBLOB(b->mode))
Edward Thomson committed
1112
		return 0;
nulltoken committed
1113

Edward Thomson committed
1114
	/* update signature cache if needed */
1115 1116
	if ((error = index_entry_similarity_calc(&cache[a_idx], repo, a, opts)) < 0 ||
	    (error = index_entry_similarity_calc(&cache[b_idx], repo, b, opts)) < 0)
Edward Thomson committed
1117
		return error;
nulltoken committed
1118

Edward Thomson committed
1119
	/* some metrics may not wish to process this file (too big / too small) */
1120
	if (cache[a_idx] == &cache_invalid_marker || cache[b_idx] == &cache_invalid_marker)
Edward Thomson committed
1121 1122 1123
		return 0;

	/* compare signatures */
1124
	if (opts->metric->similarity(&score, cache[a_idx], cache[b_idx], opts->metric->payload) < 0)
Edward Thomson committed
1125
		return -1;
nulltoken committed
1126

Edward Thomson committed
1127 1128 1129 1130 1131
	/* clip score */
	if (score < 0)
		score = 0;
	else if (score > 100)
		score = 100;
nulltoken committed
1132

Edward Thomson committed
1133 1134 1135
	return score;
}

1136
/* Tracks deletes by oid for merge_diff_mark_similarity_exact().  This is a
1137
* non-shrinking queue where next_pos is the next position to dequeue.
1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156
*/
typedef struct {
	git_array_t(size_t) arr;
	size_t next_pos;
	size_t first_entry;
} deletes_by_oid_queue;

static void deletes_by_oid_free(git_oidmap *map) {
	deletes_by_oid_queue *queue;

	if (!map)
		return;

	git_oidmap_foreach_value(map, queue, {
		git_array_clear(queue->arr);
	});
	git_oidmap_free(map);
}

1157
static int deletes_by_oid_enqueue(git_oidmap *map, git_pool *pool, const git_oid *id, size_t idx)
1158
{
1159 1160 1161
	deletes_by_oid_queue *queue;
	size_t *array_entry;

1162
	if ((queue = git_oidmap_get(map, id)) == NULL) {
1163
		queue = git_pool_malloc(pool, sizeof(deletes_by_oid_queue));
1164
		GIT_ERROR_CHECK_ALLOC(queue);
1165 1166 1167 1168 1169

		git_array_init(queue->arr);
		queue->next_pos = 0;
		queue->first_entry = idx;

1170
		if (git_oidmap_set(map, id, queue) < 0)
1171 1172 1173
			return -1;
	} else {
		array_entry = git_array_alloc(queue->arr);
1174
		GIT_ERROR_CHECK_ALLOC(array_entry);
1175 1176 1177 1178 1179 1180
		*array_entry = idx;
	}

	return 0;
}

1181 1182
static int deletes_by_oid_dequeue(size_t *idx, git_oidmap *map, const git_oid *id)
{
1183 1184 1185
	deletes_by_oid_queue *queue;
	size_t *array_entry;

1186
	if ((queue = git_oidmap_get(map, id)) == NULL)
1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209
		return GIT_ENOTFOUND;

	if (queue->next_pos == 0) {
		*idx = queue->first_entry;
	} else {
		array_entry = git_array_get(queue->arr, queue->next_pos - 1);
		if (array_entry == NULL)
			return GIT_ENOTFOUND;

		*idx = *array_entry;
	}

	queue->next_pos++;
	return 0;
}

static int merge_diff_mark_similarity_exact(
	git_merge_diff_list *diff_list,
	struct merge_diff_similarity *similarity_ours,
	struct merge_diff_similarity *similarity_theirs)
{
	size_t i, j;
	git_merge_diff *conflict_src, *conflict_tgt;
1210
	git_oidmap *ours_deletes_by_oid = NULL, *theirs_deletes_by_oid = NULL;
1211 1212
	int error = 0;

1213 1214
	if (git_oidmap_new(&ours_deletes_by_oid) < 0 ||
	    git_oidmap_new(&theirs_deletes_by_oid) < 0) {
1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271
		error = -1;
		goto done;
	}

	/* Build a map of object ids to conflicts */
	git_vector_foreach(&diff_list->conflicts, i, conflict_src) {
		/* Items can be the source of a rename iff they have an item in the
		* ancestor slot and lack an item in the ours or theirs slot. */
		if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->ancestor_entry))
			continue;

		if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->our_entry)) {
			error = deletes_by_oid_enqueue(ours_deletes_by_oid, &diff_list->pool, &conflict_src->ancestor_entry.id, i);
			if (error < 0)
				goto done;
		}

		if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->their_entry)) {
			error = deletes_by_oid_enqueue(theirs_deletes_by_oid, &diff_list->pool, &conflict_src->ancestor_entry.id, i);
			if (error < 0)
				goto done;
		}
	}

	git_vector_foreach(&diff_list->conflicts, j, conflict_tgt) {
		if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->ancestor_entry))
			continue;

		if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->our_entry)) {
			if (deletes_by_oid_dequeue(&i, ours_deletes_by_oid, &conflict_tgt->our_entry.id) == 0) {
				similarity_ours[i].similarity = 100;
				similarity_ours[i].other_idx = j;

				similarity_ours[j].similarity = 100;
				similarity_ours[j].other_idx = i;
			}
		}

		if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->their_entry)) {
			if (deletes_by_oid_dequeue(&i, theirs_deletes_by_oid, &conflict_tgt->their_entry.id) == 0) {
				similarity_theirs[i].similarity = 100;
				similarity_theirs[i].other_idx = j;

				similarity_theirs[j].similarity = 100;
				similarity_theirs[j].other_idx = i;
			}
		}
	}

done:
	deletes_by_oid_free(ours_deletes_by_oid);
	deletes_by_oid_free(theirs_deletes_by_oid);

	return error;
}

static int merge_diff_mark_similarity_inexact(
Edward Thomson committed
1272 1273 1274 1275 1276
	git_repository *repo,
	git_merge_diff_list *diff_list,
	struct merge_diff_similarity *similarity_ours,
	struct merge_diff_similarity *similarity_theirs,
	void **cache,
1277
	const git_merge_options *opts)
Edward Thomson committed
1278 1279 1280 1281
{
	size_t i, j;
	git_merge_diff *conflict_src, *conflict_tgt;
	int similarity;
nulltoken committed
1282

Edward Thomson committed
1283 1284 1285 1286 1287 1288 1289
	git_vector_foreach(&diff_list->conflicts, i, conflict_src) {
		/* Items can be the source of a rename iff they have an item in the
		 * ancestor slot and lack an item in the ours or theirs slot. */
		if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->ancestor_entry) ||
			(GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->our_entry) &&
			 GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->their_entry)))
			continue;
nulltoken committed
1290

Edward Thomson committed
1291 1292 1293
		git_vector_foreach(&diff_list->conflicts, j, conflict_tgt) {
			size_t our_idx = diff_list->conflicts.length + j;
			size_t their_idx = (diff_list->conflicts.length * 2) + j;
nulltoken committed
1294

Edward Thomson committed
1295 1296
			if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->ancestor_entry))
				continue;
nulltoken committed
1297

Edward Thomson committed
1298 1299
			if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->our_entry) &&
				!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->our_entry)) {
1300
				similarity = index_entry_similarity_inexact(repo, &conflict_src->ancestor_entry, i, &conflict_tgt->our_entry, our_idx, cache, opts);
nulltoken committed
1301

Edward Thomson committed
1302
				if (similarity == GIT_EBUFS)
nulltoken committed
1303
					continue;
Edward Thomson committed
1304 1305
				else if (similarity < 0)
					return similarity;
nulltoken committed
1306

Edward Thomson committed
1307 1308 1309 1310 1311
				if (similarity > similarity_ours[i].similarity &&
					similarity > similarity_ours[j].similarity) {
					/* Clear previous best similarity */
					if (similarity_ours[i].similarity > 0)
						similarity_ours[similarity_ours[i].other_idx].similarity = 0;
nulltoken committed
1312

Edward Thomson committed
1313 1314
					if (similarity_ours[j].similarity > 0)
						similarity_ours[similarity_ours[j].other_idx].similarity = 0;
nulltoken committed
1315

Edward Thomson committed
1316 1317
					similarity_ours[i].similarity = similarity;
					similarity_ours[i].other_idx = j;
nulltoken committed
1318

Edward Thomson committed
1319 1320 1321 1322
					similarity_ours[j].similarity = similarity;
					similarity_ours[j].other_idx = i;
				}
			}
nulltoken committed
1323

Edward Thomson committed
1324 1325
			if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->their_entry) &&
				!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->their_entry)) {
1326
				similarity = index_entry_similarity_inexact(repo, &conflict_src->ancestor_entry, i, &conflict_tgt->their_entry, their_idx, cache, opts);
nulltoken committed
1327

Edward Thomson committed
1328 1329 1330 1331 1332
				if (similarity > similarity_theirs[i].similarity &&
					similarity > similarity_theirs[j].similarity) {
					/* Clear previous best similarity */
					if (similarity_theirs[i].similarity > 0)
						similarity_theirs[similarity_theirs[i].other_idx].similarity = 0;
nulltoken committed
1333

Edward Thomson committed
1334 1335
					if (similarity_theirs[j].similarity > 0)
						similarity_theirs[similarity_theirs[j].other_idx].similarity = 0;
nulltoken committed
1336

Edward Thomson committed
1337 1338
					similarity_theirs[i].similarity = similarity;
					similarity_theirs[i].other_idx = j;
nulltoken committed
1339

Edward Thomson committed
1340 1341 1342 1343 1344 1345
					similarity_theirs[j].similarity = similarity;
					similarity_theirs[j].other_idx = i;
				}
			}
		}
	}
nulltoken committed
1346

Edward Thomson committed
1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377
	return 0;
}

/*
 * Rename conflicts:
 *
 *      Ancestor   Ours   Theirs
 *
 * 0a   A          A      A        No rename
 *  b   A          A*     A        No rename (ours was rewritten)
 *  c   A          A      A*       No rename (theirs rewritten)
 * 1a   A          A      B[A]     Rename or rename/edit
 *  b   A          B[A]   A        (automergeable)
 * 2    A          B[A]   B[A]     Both renamed (automergeable)
 * 3a   A          B[A]            Rename/delete
 *  b   A                 B[A]      (same)
 * 4a   A          B[A]   B        Rename/add [B~ours B~theirs]
 *  b   A          B      B[A]      (same)
 * 5    A          B[A]   C[A]     Both renamed ("1 -> 2")
 * 6    A          C[A]            Both renamed ("2 -> 1")
 *      B                 C[B]     [C~ours C~theirs]    (automergeable)
 */
static void merge_diff_mark_rename_conflict(
	git_merge_diff_list *diff_list,
	struct merge_diff_similarity *similarity_ours,
	bool ours_renamed,
	size_t ours_source_idx,
	struct merge_diff_similarity *similarity_theirs,
	bool theirs_renamed,
	size_t theirs_source_idx,
	git_merge_diff *target,
1378
	const git_merge_options *opts)
Edward Thomson committed
1379 1380
{
	git_merge_diff *ours_source = NULL, *theirs_source = NULL;
nulltoken committed
1381

Edward Thomson committed
1382 1383
	if (ours_renamed)
		ours_source = diff_list->conflicts.contents[ours_source_idx];
nulltoken committed
1384

Edward Thomson committed
1385 1386
	if (theirs_renamed)
		theirs_source = diff_list->conflicts.contents[theirs_source_idx];
nulltoken committed
1387

Edward Thomson committed
1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400
	/* Detect 2->1 conflicts */
	if (ours_renamed && theirs_renamed) {
		/* Both renamed to the same target name. */
		if (ours_source_idx == theirs_source_idx)
			ours_source->type = GIT_MERGE_DIFF_BOTH_RENAMED;
		else {
			ours_source->type = GIT_MERGE_DIFF_BOTH_RENAMED_2_TO_1;
			theirs_source->type = GIT_MERGE_DIFF_BOTH_RENAMED_2_TO_1;
		}
	} else if (ours_renamed) {
		/* If our source was also renamed in theirs, this is a 1->2 */
		if (similarity_theirs[ours_source_idx].similarity >= opts->rename_threshold)
			ours_source->type = GIT_MERGE_DIFF_BOTH_RENAMED_1_TO_2;
nulltoken committed
1401

Edward Thomson committed
1402 1403 1404 1405
		else if (GIT_MERGE_INDEX_ENTRY_EXISTS(target->their_entry)) {
			ours_source->type = GIT_MERGE_DIFF_RENAMED_ADDED;
			target->type = GIT_MERGE_DIFF_RENAMED_ADDED;
		}
nulltoken committed
1406

Edward Thomson committed
1407 1408
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(ours_source->their_entry))
			ours_source->type = GIT_MERGE_DIFF_RENAMED_DELETED;
nulltoken committed
1409

Edward Thomson committed
1410 1411 1412 1413 1414 1415
		else if (ours_source->type == GIT_MERGE_DIFF_MODIFIED_DELETED)
			ours_source->type = GIT_MERGE_DIFF_RENAMED_MODIFIED;
	} else if (theirs_renamed) {
		/* If their source was also renamed in ours, this is a 1->2 */
		if (similarity_ours[theirs_source_idx].similarity >= opts->rename_threshold)
			theirs_source->type = GIT_MERGE_DIFF_BOTH_RENAMED_1_TO_2;
nulltoken committed
1416

Edward Thomson committed
1417 1418 1419 1420
		else if (GIT_MERGE_INDEX_ENTRY_EXISTS(target->our_entry)) {
			theirs_source->type = GIT_MERGE_DIFF_RENAMED_ADDED;
			target->type = GIT_MERGE_DIFF_RENAMED_ADDED;
		}
nulltoken committed
1421

Edward Thomson committed
1422 1423
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(theirs_source->our_entry))
			theirs_source->type = GIT_MERGE_DIFF_RENAMED_DELETED;
nulltoken committed
1424

Edward Thomson committed
1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438
		else if (theirs_source->type == GIT_MERGE_DIFF_MODIFIED_DELETED)
			theirs_source->type = GIT_MERGE_DIFF_RENAMED_MODIFIED;
	}
}

GIT_INLINE(void) merge_diff_coalesce_rename(
	git_index_entry *source_entry,
	git_delta_t *source_status,
	git_index_entry *target_entry,
	git_delta_t *target_status)
{
	/* Coalesce the rename target into the rename source. */
	memcpy(source_entry, target_entry, sizeof(git_index_entry));
	*source_status = GIT_DELTA_RENAMED;
nulltoken committed
1439

Edward Thomson committed
1440 1441 1442 1443 1444 1445 1446 1447
	memset(target_entry, 0x0, sizeof(git_index_entry));
	*target_status = GIT_DELTA_UNMODIFIED;
}

static void merge_diff_list_coalesce_renames(
	git_merge_diff_list *diff_list,
	struct merge_diff_similarity *similarity_ours,
	struct merge_diff_similarity *similarity_theirs,
1448
	const git_merge_options *opts)
Edward Thomson committed
1449 1450 1451 1452 1453
{
	size_t i;
	bool ours_renamed = 0, theirs_renamed = 0;
	size_t ours_source_idx = 0, theirs_source_idx = 0;
	git_merge_diff *ours_source, *theirs_source, *target;
nulltoken committed
1454

Edward Thomson committed
1455 1456
	for (i = 0; i < diff_list->conflicts.length; i++) {
		target = diff_list->conflicts.contents[i];
nulltoken committed
1457

Edward Thomson committed
1458 1459
		ours_renamed = 0;
		theirs_renamed = 0;
nulltoken committed
1460

Edward Thomson committed
1461 1462 1463
		if (GIT_MERGE_INDEX_ENTRY_EXISTS(target->our_entry) &&
			similarity_ours[i].similarity >= opts->rename_threshold) {
			ours_source_idx = similarity_ours[i].other_idx;
nulltoken committed
1464

Edward Thomson committed
1465
			ours_source = diff_list->conflicts.contents[ours_source_idx];
nulltoken committed
1466

Edward Thomson committed
1467 1468 1469 1470 1471
			merge_diff_coalesce_rename(
				&ours_source->our_entry,
				&ours_source->our_status,
				&target->our_entry,
				&target->our_status);
nulltoken committed
1472

Edward Thomson committed
1473 1474
			similarity_ours[ours_source_idx].similarity = 0;
			similarity_ours[i].similarity = 0;
nulltoken committed
1475

Edward Thomson committed
1476 1477
			ours_renamed = 1;
		}
nulltoken committed
1478

Edward Thomson committed
1479 1480 1481 1482
		/* insufficient to determine direction */
		if (GIT_MERGE_INDEX_ENTRY_EXISTS(target->their_entry) &&
			similarity_theirs[i].similarity >= opts->rename_threshold) {
			theirs_source_idx = similarity_theirs[i].other_idx;
nulltoken committed
1483

Edward Thomson committed
1484
			theirs_source = diff_list->conflicts.contents[theirs_source_idx];
nulltoken committed
1485

Edward Thomson committed
1486 1487 1488 1489 1490
			merge_diff_coalesce_rename(
				&theirs_source->their_entry,
				&theirs_source->their_status,
				&target->their_entry,
				&target->their_status);
nulltoken committed
1491

Edward Thomson committed
1492 1493
			similarity_theirs[theirs_source_idx].similarity = 0;
			similarity_theirs[i].similarity = 0;
nulltoken committed
1494

Edward Thomson committed
1495 1496
			theirs_renamed = 1;
		}
nulltoken committed
1497

Edward Thomson committed
1498 1499 1500 1501 1502 1503 1504
		merge_diff_mark_rename_conflict(diff_list,
			similarity_ours, ours_renamed, ours_source_idx,
			similarity_theirs, theirs_renamed, theirs_source_idx,
			target, opts);
	}
}

1505
static int merge_diff_empty(const git_vector *conflicts, size_t idx, void *p)
Edward Thomson committed
1506 1507
{
	git_merge_diff *conflict = conflicts->contents[idx];
nulltoken committed
1508

1509 1510
	GIT_UNUSED(p);

Edward Thomson committed
1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525
	return (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry) &&
		!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) &&
		!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry));
}

static void merge_diff_list_count_candidates(
	git_merge_diff_list *diff_list,
	size_t *src_count,
	size_t *tgt_count)
{
	git_merge_diff *entry;
	size_t i;

	*src_count = 0;
	*tgt_count = 0;
nulltoken committed
1526

Edward Thomson committed
1527 1528 1529 1530
	git_vector_foreach(&diff_list->conflicts, i, entry) {
		if (GIT_MERGE_INDEX_ENTRY_EXISTS(entry->ancestor_entry) &&
			(!GIT_MERGE_INDEX_ENTRY_EXISTS(entry->our_entry) ||
			!GIT_MERGE_INDEX_ENTRY_EXISTS(entry->their_entry)))
1531
			(*src_count)++;
Edward Thomson committed
1532
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(entry->ancestor_entry))
1533
			(*tgt_count)++;
Edward Thomson committed
1534 1535 1536 1537 1538 1539
	}
}

int git_merge_diff_list__find_renames(
	git_repository *repo,
	git_merge_diff_list *diff_list,
1540
	const git_merge_options *opts)
Edward Thomson committed
1541 1542 1543 1544 1545 1546
{
	struct merge_diff_similarity *similarity_ours, *similarity_theirs;
	void **cache = NULL;
	size_t cache_size = 0;
	size_t src_count, tgt_count, i;
	int error = 0;
nulltoken committed
1547

Edward Thomson committed
1548 1549
	GIT_ASSERT_ARG(diff_list);
	GIT_ASSERT_ARG(opts);
nulltoken committed
1550

1551 1552
	if ((opts->flags & GIT_MERGE_FIND_RENAMES) == 0 ||
	    !diff_list->conflicts.length)
Edward Thomson committed
1553
		return 0;
nulltoken committed
1554

Edward Thomson committed
1555 1556
	similarity_ours = git__calloc(diff_list->conflicts.length,
		sizeof(struct merge_diff_similarity));
1557
	GIT_ERROR_CHECK_ALLOC(similarity_ours);
nulltoken committed
1558

Edward Thomson committed
1559 1560
	similarity_theirs = git__calloc(diff_list->conflicts.length,
		sizeof(struct merge_diff_similarity));
1561
	GIT_ERROR_CHECK_ALLOC(similarity_theirs);
nulltoken committed
1562

Edward Thomson committed
1563 1564 1565
	/* Calculate similarity between items that were deleted from the ancestor
	 * and added in the other branch.
	 */
1566
	if ((error = merge_diff_mark_similarity_exact(diff_list, similarity_ours, similarity_theirs)) < 0)
Edward Thomson committed
1567 1568
		goto done;

1569
	if (opts->rename_threshold < 100 && diff_list->conflicts.length <= opts->target_limit) {
1570
		GIT_ERROR_CHECK_ALLOC_MULTIPLY(&cache_size, diff_list->conflicts.length, 3);
Edward Thomson committed
1571
		cache = git__calloc(cache_size, sizeof(void *));
1572
		GIT_ERROR_CHECK_ALLOC(cache);
Edward Thomson committed
1573 1574

		merge_diff_list_count_candidates(diff_list, &src_count, &tgt_count);
nulltoken committed
1575

Edward Thomson committed
1576 1577 1578
		if (src_count > opts->target_limit || tgt_count > opts->target_limit) {
			/* TODO: report! */
		} else {
1579 1580
			if ((error = merge_diff_mark_similarity_inexact(
				repo, diff_list, similarity_ours, similarity_theirs, cache, opts)) < 0)
Edward Thomson committed
1581 1582 1583 1584 1585 1586 1587 1588
				goto done;
		}
	}

	/* For entries that are appropriately similar, merge the new name's entry
	 * into the old name.
	 */
	merge_diff_list_coalesce_renames(diff_list, similarity_ours, similarity_theirs, opts);
nulltoken committed
1589

Edward Thomson committed
1590
	/* And remove any entries that were merged and are now empty. */
1591
	git_vector_remove_matching(&diff_list->conflicts, merge_diff_empty, NULL);
Edward Thomson committed
1592 1593 1594 1595

done:
	if (cache != NULL) {
		for (i = 0; i < cache_size; ++i) {
1596
			if (cache[i] != NULL && cache[i] != &cache_invalid_marker)
Edward Thomson committed
1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608
				opts->metric->free_signature(cache[i], opts->metric->payload);
		}

		git__free(cache);
	}

	git__free(similarity_ours);
	git__free(similarity_theirs);

	return error;
}

Edward Thomson committed
1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619
/* Directory/file conflict handling */

GIT_INLINE(const char *) merge_diff_path(
	const git_merge_diff *conflict)
{
	if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry))
		return conflict->ancestor_entry.path;
	else if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry))
		return conflict->our_entry.path;
	else if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry))
		return conflict->their_entry.path;
nulltoken committed
1620

Edward Thomson committed
1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631
	return NULL;
}

GIT_INLINE(bool) merge_diff_any_side_added_or_modified(
	const git_merge_diff *conflict)
{
	if (conflict->our_status == GIT_DELTA_ADDED ||
		conflict->our_status == GIT_DELTA_MODIFIED ||
		conflict->their_status == GIT_DELTA_ADDED ||
		conflict->their_status == GIT_DELTA_MODIFIED)
		return true;
nulltoken committed
1632

Edward Thomson committed
1633 1634 1635 1636 1637 1638 1639
	return false;
}

GIT_INLINE(bool) path_is_prefixed(const char *parent, const char *child)
{
	size_t child_len = strlen(child);
	size_t parent_len = strlen(parent);
nulltoken committed
1640

Edward Thomson committed
1641 1642 1643
	if (child_len < parent_len ||
		strncmp(parent, child, parent_len) != 0)
		return 0;
nulltoken committed
1644

Edward Thomson committed
1645 1646 1647 1648 1649 1650 1651 1652
	return (child[parent_len] == '/');
}

GIT_INLINE(int) merge_diff_detect_df_conflict(
	struct merge_diff_df_data *df_data,
	git_merge_diff *conflict)
{
	const char *cur_path = merge_diff_path(conflict);
nulltoken committed
1653

Edward Thomson committed
1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664
	/* Determine if this is a D/F conflict or the child of one */
	if (df_data->df_path &&
		path_is_prefixed(df_data->df_path, cur_path))
		conflict->type = GIT_MERGE_DIFF_DF_CHILD;
	else if(df_data->df_path)
		df_data->df_path = NULL;
	else if (df_data->prev_path &&
		merge_diff_any_side_added_or_modified(df_data->prev_conflict) &&
		merge_diff_any_side_added_or_modified(conflict) &&
		path_is_prefixed(df_data->prev_path, cur_path)) {
		conflict->type = GIT_MERGE_DIFF_DF_CHILD;
nulltoken committed
1665

Edward Thomson committed
1666 1667 1668
		df_data->prev_conflict->type = GIT_MERGE_DIFF_DIRECTORY_FILE;
		df_data->df_path = df_data->prev_path;
	}
nulltoken committed
1669

Edward Thomson committed
1670 1671
	df_data->prev_path = cur_path;
	df_data->prev_conflict = conflict;
nulltoken committed
1672

Edward Thomson committed
1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697
	return 0;
}

/* Conflict handling */

GIT_INLINE(int) merge_diff_detect_type(
	git_merge_diff *conflict)
{
	if (conflict->our_status == GIT_DELTA_ADDED &&
		conflict->their_status == GIT_DELTA_ADDED)
		conflict->type = GIT_MERGE_DIFF_BOTH_ADDED;
	else if (conflict->our_status == GIT_DELTA_MODIFIED &&
			 conflict->their_status == GIT_DELTA_MODIFIED)
		conflict->type = GIT_MERGE_DIFF_BOTH_MODIFIED;
	else if (conflict->our_status == GIT_DELTA_DELETED &&
			 conflict->their_status == GIT_DELTA_DELETED)
		conflict->type = GIT_MERGE_DIFF_BOTH_DELETED;
	else if (conflict->our_status == GIT_DELTA_MODIFIED &&
			 conflict->their_status == GIT_DELTA_DELETED)
		conflict->type = GIT_MERGE_DIFF_MODIFIED_DELETED;
	else if (conflict->our_status == GIT_DELTA_DELETED &&
			 conflict->their_status == GIT_DELTA_MODIFIED)
		conflict->type = GIT_MERGE_DIFF_MODIFIED_DELETED;
	else
		conflict->type = GIT_MERGE_DIFF_NONE;
nulltoken committed
1698

Edward Thomson committed
1699 1700 1701
	return 0;
}

1702
GIT_INLINE(int) index_entry_dup_pool(
Edward Thomson committed
1703 1704 1705 1706 1707 1708 1709 1710 1711
	git_index_entry *out,
	git_pool *pool,
	const git_index_entry *src)
{
	if (src != NULL) {
		memcpy(out, src, sizeof(git_index_entry));
		if ((out->path = git_pool_strdup(pool, src->path)) == NULL)
			return -1;
	}
nulltoken committed
1712

Edward Thomson committed
1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729
	return 0;
}

GIT_INLINE(int) merge_delta_type_from_index_entries(
	const git_index_entry *ancestor,
	const git_index_entry *other)
{
	if (ancestor == NULL && other == NULL)
		return GIT_DELTA_UNMODIFIED;
	else if (ancestor == NULL && other != NULL)
		return GIT_DELTA_ADDED;
	else if (ancestor != NULL && other == NULL)
		return GIT_DELTA_DELETED;
	else if (S_ISDIR(ancestor->mode) ^ S_ISDIR(other->mode))
		return GIT_DELTA_TYPECHANGE;
	else if(S_ISLNK(ancestor->mode) ^ S_ISLNK(other->mode))
		return GIT_DELTA_TYPECHANGE;
1730
	else if (git_oid__cmp(&ancestor->id, &other->id) ||
Edward Thomson committed
1731 1732
			 ancestor->mode != other->mode)
		return GIT_DELTA_MODIFIED;
nulltoken committed
1733

Edward Thomson committed
1734 1735 1736 1737 1738 1739 1740 1741 1742
	return GIT_DELTA_UNMODIFIED;
}

static git_merge_diff *merge_diff_from_index_entries(
	git_merge_diff_list *diff_list,
	const git_index_entry **entries)
{
	git_merge_diff *conflict;
	git_pool *pool = &diff_list->pool;
nulltoken committed
1743

1744
	if ((conflict = git_pool_mallocz(pool, sizeof(git_merge_diff))) == NULL)
Edward Thomson committed
1745
		return NULL;
nulltoken committed
1746

1747 1748 1749
	if (index_entry_dup_pool(&conflict->ancestor_entry, pool, entries[TREE_IDX_ANCESTOR]) < 0 ||
		index_entry_dup_pool(&conflict->our_entry, pool, entries[TREE_IDX_OURS]) < 0 ||
		index_entry_dup_pool(&conflict->their_entry, pool, entries[TREE_IDX_THEIRS]) < 0)
Edward Thomson committed
1750
		return NULL;
nulltoken committed
1751

Edward Thomson committed
1752 1753 1754 1755
	conflict->our_status = merge_delta_type_from_index_entries(
		entries[TREE_IDX_ANCESTOR], entries[TREE_IDX_OURS]);
	conflict->their_status = merge_delta_type_from_index_entries(
		entries[TREE_IDX_ANCESTOR], entries[TREE_IDX_THEIRS]);
nulltoken committed
1756

Edward Thomson committed
1757 1758 1759 1760 1761
	return conflict;
}

/* Merge trees */

1762
static int merge_diff_list_insert_conflict(
Edward Thomson committed
1763 1764 1765 1766 1767
	git_merge_diff_list *diff_list,
	struct merge_diff_df_data *merge_df_data,
	const git_index_entry *tree_items[3])
{
	git_merge_diff *conflict;
nulltoken committed
1768

Edward Thomson committed
1769 1770 1771 1772 1773
	if ((conflict = merge_diff_from_index_entries(diff_list, tree_items)) == NULL ||
		merge_diff_detect_type(conflict) < 0 ||
		merge_diff_detect_df_conflict(merge_df_data, conflict) < 0 ||
		git_vector_insert(&diff_list->conflicts, conflict) < 0)
		return -1;
nulltoken committed
1774

Edward Thomson committed
1775 1776 1777
	return 0;
}

1778
static int merge_diff_list_insert_unmodified(
Edward Thomson committed
1779 1780 1781 1782 1783
	git_merge_diff_list *diff_list,
	const git_index_entry *tree_items[3])
{
	int error = 0;
	git_index_entry *entry;
nulltoken committed
1784

1785
	entry = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry));
1786
	GIT_ERROR_CHECK_ALLOC(entry);
nulltoken committed
1787

1788
	if ((error = index_entry_dup_pool(entry, &diff_list->pool, tree_items[0])) >= 0)
Edward Thomson committed
1789
		error = git_vector_insert(&diff_list->staged, entry);
nulltoken committed
1790

Edward Thomson committed
1791 1792 1793
	return error;
}

1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821
struct merge_diff_find_data {
	git_merge_diff_list *diff_list;
	struct merge_diff_df_data df_data;
};

static int queue_difference(const git_index_entry **entries, void *data)
{
	struct merge_diff_find_data *find_data = data;
	bool item_modified = false;
	size_t i;

	if (!entries[0] || !entries[1] || !entries[2]) {
		item_modified = true;
	} else {
		for (i = 1; i < 3; i++) {
			if (index_entry_cmp(entries[0], entries[i]) != 0) {
				item_modified = true;
				break;
			}
		}
	}

	return item_modified ?
		merge_diff_list_insert_conflict(
			find_data->diff_list, &find_data->df_data, entries) :
		merge_diff_list_insert_unmodified(find_data->diff_list, entries);
}

Edward Thomson committed
1822 1823
int git_merge_diff_list__find_differences(
	git_merge_diff_list *diff_list,
1824 1825 1826
	git_iterator *ancestor_iter,
	git_iterator *our_iter,
	git_iterator *their_iter)
Edward Thomson committed
1827
{
1828
	git_iterator *iterators[3] = { ancestor_iter, our_iter, their_iter };
1829
	struct merge_diff_find_data find_data = { diff_list };
nulltoken committed
1830

1831
	return git_iterator_walk(iterators, 3, queue_difference, &find_data);
Edward Thomson committed
1832 1833 1834 1835 1836
}

git_merge_diff_list *git_merge_diff_list__alloc(git_repository *repo)
{
	git_merge_diff_list *diff_list = git__calloc(1, sizeof(git_merge_diff_list));
nulltoken committed
1837

Edward Thomson committed
1838 1839
	if (diff_list == NULL)
		return NULL;
nulltoken committed
1840

Edward Thomson committed
1841
	diff_list->repo = repo;
nulltoken committed
1842

1843

1844 1845 1846 1847 1848
	if (git_pool_init(&diff_list->pool, 1) < 0 ||
	    git_vector_init(&diff_list->staged, 0, NULL) < 0 ||
	    git_vector_init(&diff_list->conflicts, 0, NULL) < 0 ||
	    git_vector_init(&diff_list->resolved, 0, NULL) < 0) {
	    git_merge_diff_list__free(diff_list);
Edward Thomson committed
1849
		return NULL;
Jacques Germishuys committed
1850
	}
nulltoken committed
1851

Edward Thomson committed
1852 1853 1854
	return diff_list;
}

Edward Thomson committed
1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866
void git_merge_diff_list__free(git_merge_diff_list *diff_list)
{
	if (!diff_list)
		return;

	git_vector_free(&diff_list->staged);
	git_vector_free(&diff_list->conflicts);
	git_vector_free(&diff_list->resolved);
	git_pool_clear(&diff_list->pool);
	git__free(diff_list);
}

1867
static int merge_normalize_opts(
Edward Thomson committed
1868
	git_repository *repo,
1869 1870
	git_merge_options *opts,
	const git_merge_options *given)
Edward Thomson committed
1871 1872
{
	git_config *cfg = NULL;
1873
	git_config_entry *entry = NULL;
Edward Thomson committed
1874
	int error = 0;
nulltoken committed
1875

Edward Thomson committed
1876 1877
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(opts);
nulltoken committed
1878

Edward Thomson committed
1879 1880
	if ((error = git_repository_config__weakptr(&cfg, repo)) < 0)
		return error;
nulltoken committed
1881

1882
	if (given != NULL) {
1883
		memcpy(opts, given, sizeof(git_merge_options));
1884
	} else {
1885
		git_merge_options init = GIT_MERGE_OPTIONS_INIT;
Edward Thomson committed
1886
		memcpy(opts, &init, sizeof(init));
1887
	}
nulltoken committed
1888

1889
	if ((opts->flags & GIT_MERGE_FIND_RENAMES) && !opts->rename_threshold)
1890
		opts->rename_threshold = GIT_MERGE_DEFAULT_RENAME_THRESHOLD;
nulltoken committed
1891

1892 1893
	if (given && given->default_driver) {
		opts->default_driver = git__strdup(given->default_driver);
1894
		GIT_ERROR_CHECK_ALLOC(opts->default_driver);
1895 1896 1897 1898 1899
	} else {
		error = git_config_get_entry(&entry, cfg, "merge.default");

		if (error == 0) {
			opts->default_driver = git__strdup(entry->value);
1900
			GIT_ERROR_CHECK_ALLOC(opts->default_driver);
1901 1902 1903 1904 1905 1906 1907
		} else if (error == GIT_ENOTFOUND) {
			error = 0;
		} else {
			goto done;
		}
	}

Edward Thomson committed
1908
	if (!opts->target_limit) {
1909
		int limit = git_config__get_int_force(cfg, "merge.renamelimit", 0);
nulltoken committed
1910

1911 1912
		if (!limit)
			limit = git_config__get_int_force(cfg, "diff.renamelimit", 0);
nulltoken committed
1913

1914
		opts->target_limit = (limit <= 0) ?
1915
			GIT_MERGE_DEFAULT_TARGET_LIMIT : (unsigned int)limit;
Edward Thomson committed
1916
	}
nulltoken committed
1917

Edward Thomson committed
1918 1919 1920
	/* assign the internal metric with whitespace flag as payload */
	if (!opts->metric) {
		opts->metric = git__malloc(sizeof(git_diff_similarity_metric));
1921
		GIT_ERROR_CHECK_ALLOC(opts->metric);
nulltoken committed
1922

Edward Thomson committed
1923 1924 1925 1926
		opts->metric->file_signature = git_diff_find_similar__hashsig_for_file;
		opts->metric->buffer_signature = git_diff_find_similar__hashsig_for_buf;
		opts->metric->free_signature = git_diff_find_similar__hashsig_free;
		opts->metric->similarity = git_diff_find_similar__calc_similarity;
1927
		opts->metric->payload = (void *)GIT_HASHSIG_SMART_WHITESPACE;
Edward Thomson committed
1928
	}
nulltoken committed
1929

1930 1931 1932
done:
	git_config_entry_free(entry);
	return error;
Edward Thomson committed
1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944
}


static int merge_index_insert_reuc(
	git_index *index,
	size_t idx,
	const git_index_entry *entry)
{
	const git_index_reuc_entry *reuc;
	int mode[3] = { 0, 0, 0 };
	git_oid const *oid[3] = { NULL, NULL, NULL };
	size_t i;
nulltoken committed
1945

Edward Thomson committed
1946 1947
	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(*entry))
		return 0;
nulltoken committed
1948

Edward Thomson committed
1949 1950 1951 1952 1953 1954
	if ((reuc = git_index_reuc_get_bypath(index, entry->path)) != NULL) {
		for (i = 0; i < 3; i++) {
			mode[i] = reuc->mode[i];
			oid[i] = &reuc->oid[i];
		}
	}
nulltoken committed
1955

Edward Thomson committed
1956
	mode[idx] = entry->mode;
1957
	oid[idx] = &entry->id;
nulltoken committed
1958

Edward Thomson committed
1959 1960 1961 1962
	return git_index_reuc_add(index, entry->path,
		mode[0], oid[0], mode[1], oid[1], mode[2], oid[2]);
}

1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001
static int index_update_reuc(git_index *index, git_merge_diff_list *diff_list)
{
	int error;
	size_t i;
	git_merge_diff *conflict;

	/* Add each entry in the resolved conflict to the REUC independently, since
	 * the paths may differ due to renames. */
	git_vector_foreach(&diff_list->resolved, i, conflict) {
		const git_index_entry *ancestor =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry) ?
			&conflict->ancestor_entry : NULL;

		const git_index_entry *ours =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
			&conflict->our_entry : NULL;

		const git_index_entry *theirs =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
			&conflict->their_entry : NULL;

		if (ancestor != NULL &&
			(error = merge_index_insert_reuc(index, TREE_IDX_ANCESTOR, ancestor)) < 0)
			return error;

		if (ours != NULL &&
			(error = merge_index_insert_reuc(index, TREE_IDX_OURS, ours)) < 0)
			return error;

		if (theirs != NULL &&
			(error = merge_index_insert_reuc(index, TREE_IDX_THEIRS, theirs)) < 0)
			return error;
	}

	return 0;
}

static int index_from_diff_list(git_index **out,
	git_merge_diff_list *diff_list, bool skip_reuc)
Edward Thomson committed
2002 2003 2004 2005 2006
{
	git_index *index;
	size_t i;
	git_merge_diff *conflict;
	int error = 0;
nulltoken committed
2007

Edward Thomson committed
2008
	*out = NULL;
nulltoken committed
2009

Edward Thomson committed
2010 2011
	if ((error = git_index_new(&index)) < 0)
		return error;
nulltoken committed
2012

2013 2014
	if ((error = git_index__fill(index, &diff_list->staged)) < 0)
		goto on_error;
nulltoken committed
2015

Edward Thomson committed
2016 2017 2018 2019
	git_vector_foreach(&diff_list->conflicts, i, conflict) {
		const git_index_entry *ancestor =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry) ?
			&conflict->ancestor_entry : NULL;
nulltoken committed
2020

Edward Thomson committed
2021 2022 2023
		const git_index_entry *ours =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
			&conflict->our_entry : NULL;
nulltoken committed
2024

Edward Thomson committed
2025 2026 2027
		const git_index_entry *theirs =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
			&conflict->their_entry : NULL;
nulltoken committed
2028

Edward Thomson committed
2029 2030 2031
		if ((error = git_index_conflict_add(index, ancestor, ours, theirs)) < 0)
			goto on_error;
	}
nulltoken committed
2032

Edward Thomson committed
2033 2034 2035
	/* Add each rename entry to the rename portion of the index. */
	git_vector_foreach(&diff_list->conflicts, i, conflict) {
		const char *ancestor_path, *our_path, *their_path;
nulltoken committed
2036

Edward Thomson committed
2037 2038
		if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry))
			continue;
nulltoken committed
2039

Edward Thomson committed
2040
		ancestor_path = conflict->ancestor_entry.path;
nulltoken committed
2041

Edward Thomson committed
2042 2043 2044
		our_path =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
			conflict->our_entry.path : NULL;
nulltoken committed
2045

Edward Thomson committed
2046 2047 2048
		their_path =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
			conflict->their_entry.path : NULL;
nulltoken committed
2049

Edward Thomson committed
2050 2051 2052 2053 2054
		if ((our_path && strcmp(ancestor_path, our_path) != 0) ||
			(their_path && strcmp(ancestor_path, their_path) != 0)) {
			if ((error = git_index_name_add(index, ancestor_path, our_path, their_path)) < 0)
				goto on_error;
		}
Edward Thomson committed
2055
	}
nulltoken committed
2056

2057 2058
	if (!skip_reuc) {
		if ((error = index_update_reuc(index, diff_list)) < 0)
Edward Thomson committed
2059 2060
			goto on_error;
	}
nulltoken committed
2061

Edward Thomson committed
2062 2063
	*out = index;
	return 0;
nulltoken committed
2064

Edward Thomson committed
2065 2066 2067 2068 2069
on_error:
	git_index_free(index);
	return error;
}

2070 2071
static git_iterator *iterator_given_or_empty(git_iterator **empty, git_iterator *given)
{
2072 2073
	git_iterator_options opts = GIT_ITERATOR_OPTIONS_INIT;

2074 2075 2076
	if (given)
		return given;

2077 2078 2079
	opts.flags = GIT_ITERATOR_DONT_IGNORE_CASE;

	if (git_iterator_for_nothing(empty, &opts) < 0)
2080 2081 2082 2083 2084 2085
		return NULL;

	return *empty;
}

int git_merge__iterators(
Edward Thomson committed
2086 2087
	git_index **out,
	git_repository *repo,
2088 2089 2090
	git_iterator *ancestor_iter,
	git_iterator *our_iter,
	git_iterator *theirs_iter,
2091
	const git_merge_options *given_opts)
Edward Thomson committed
2092
{
2093 2094 2095
	git_iterator *empty_ancestor = NULL,
		*empty_ours = NULL,
		*empty_theirs = NULL;
Edward Thomson committed
2096
	git_merge_diff_list *diff_list;
2097
	git_merge_options opts;
2098
	git_merge_file_options file_opts = GIT_MERGE_FILE_OPTIONS_INIT;
Edward Thomson committed
2099 2100 2101 2102 2103
	git_merge_diff *conflict;
	git_vector changes;
	size_t i;
	int error = 0;

Edward Thomson committed
2104 2105
	GIT_ASSERT_ARG(out);
	GIT_ASSERT_ARG(repo);
Edward Thomson committed
2106 2107

	*out = NULL;
nulltoken committed
2108

2109
	GIT_ERROR_CHECK_VERSION(
2110
		given_opts, GIT_MERGE_OPTIONS_VERSION, "git_merge_options");
2111

2112
	if ((error = merge_normalize_opts(repo, &opts, given_opts)) < 0)
Edward Thomson committed
2113 2114
		return error;

2115 2116 2117 2118
	file_opts.favor = opts.file_favor;
	file_opts.flags = opts.file_flags;

	/* use the git-inspired labels when virtual base building */
2119
	if (opts.flags & GIT_MERGE_VIRTUAL_BASE) {
2120 2121 2122
		file_opts.ancestor_label = "merged common ancestors";
		file_opts.our_label = "Temporary merge branch 1";
		file_opts.their_label = "Temporary merge branch 2";
2123
		file_opts.flags |= GIT_MERGE_FILE_ACCEPT_CONFLICTS;
2124
		file_opts.marker_size = GIT_MERGE_CONFLICT_MARKER_SIZE + 2;
2125 2126
	}

Edward Thomson committed
2127
	diff_list = git_merge_diff_list__alloc(repo);
2128
	GIT_ERROR_CHECK_ALLOC(diff_list);
nulltoken committed
2129

2130 2131 2132 2133 2134 2135
	ancestor_iter = iterator_given_or_empty(&empty_ancestor, ancestor_iter);
	our_iter = iterator_given_or_empty(&empty_ours, our_iter);
	theirs_iter = iterator_given_or_empty(&empty_theirs, theirs_iter);

	if ((error = git_merge_diff_list__find_differences(
			diff_list, ancestor_iter, our_iter, theirs_iter)) < 0 ||
Edward Thomson committed
2136
		(error = git_merge_diff_list__find_renames(repo, diff_list, &opts)) < 0)
Edward Thomson committed
2137
		goto done;
nulltoken committed
2138

Edward Thomson committed
2139 2140
	memcpy(&changes, &diff_list->conflicts, sizeof(git_vector));
	git_vector_clear(&diff_list->conflicts);
nulltoken committed
2141

Edward Thomson committed
2142 2143
	git_vector_foreach(&changes, i, conflict) {
		int resolved = 0;
nulltoken committed
2144

2145
		if ((error = merge_conflict_resolve(
2146
			&resolved, diff_list, conflict, &opts, &file_opts)) < 0)
Edward Thomson committed
2147
			goto done;
nulltoken committed
2148

2149
		if (!resolved) {
2150
			if ((opts.flags & GIT_MERGE_FAIL_ON_CONFLICT)) {
2151
				git_error_set(GIT_ERROR_MERGE, "merge conflicts exist");
2152 2153 2154 2155
				error = GIT_EMERGECONFLICT;
				goto done;
			}

Edward Thomson committed
2156
			git_vector_insert(&diff_list->conflicts, conflict);
2157
		}
Edward Thomson committed
2158
	}
nulltoken committed
2159

2160
	error = index_from_diff_list(out, diff_list,
2161
		(opts.flags & GIT_MERGE_SKIP_REUC));
Edward Thomson committed
2162 2163

done:
Vicent Marti committed
2164 2165 2166
	if (!given_opts || !given_opts->metric)
		git__free(opts.metric);

2167 2168
	git__free((char *)opts.default_driver);

Edward Thomson committed
2169
	git_merge_diff_list__free(diff_list);
2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185
	git_iterator_free(empty_ancestor);
	git_iterator_free(empty_ours);
	git_iterator_free(empty_theirs);

	return error;
}

int git_merge_trees(
	git_index **out,
	git_repository *repo,
	const git_tree *ancestor_tree,
	const git_tree *our_tree,
	const git_tree *their_tree,
	const git_merge_options *merge_opts)
{
	git_iterator *ancestor_iter = NULL, *our_iter = NULL, *their_iter = NULL;
2186
	git_iterator_options iter_opts = GIT_ITERATOR_OPTIONS_INIT;
2187 2188
	int error;

Edward Thomson committed
2189 2190
	GIT_ASSERT_ARG(out);
	GIT_ASSERT_ARG(repo);
2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203

	/* if one side is treesame to the ancestor, take the other side */
	if (ancestor_tree && merge_opts && (merge_opts->flags & GIT_MERGE_SKIP_REUC)) {
		const git_tree *result = NULL;
		const git_oid *ancestor_tree_id = git_tree_id(ancestor_tree);

		if (our_tree && !git_oid_cmp(ancestor_tree_id, git_tree_id(our_tree)))
			result = their_tree;
		else if (their_tree && !git_oid_cmp(ancestor_tree_id, git_tree_id(their_tree)))
			result = our_tree;

		if (result) {
			if ((error = git_index_new(out)) == 0)
2204
    			error = git_index_read_tree(*out, result);
2205 2206 2207 2208 2209

			return error;
		}
	}

2210 2211 2212 2213 2214 2215 2216 2217
	iter_opts.flags = GIT_ITERATOR_DONT_IGNORE_CASE;

	if ((error = git_iterator_for_tree(
			&ancestor_iter, (git_tree *)ancestor_tree, &iter_opts)) < 0 ||
		(error = git_iterator_for_tree(
			&our_iter, (git_tree *)our_tree, &iter_opts)) < 0 ||
		(error = git_iterator_for_tree(
			&their_iter, (git_tree *)their_tree, &iter_opts)) < 0)
2218 2219 2220 2221 2222 2223 2224 2225 2226
		goto done;

	error = git_merge__iterators(
		out, repo, ancestor_iter, our_iter, their_iter, merge_opts);

done:
	git_iterator_free(ancestor_iter);
	git_iterator_free(our_iter);
	git_iterator_free(their_iter);
Edward Thomson committed
2227 2228 2229 2230

	return error;
}

2231 2232 2233
static int merge_annotated_commits(
	git_index **index_out,
	git_annotated_commit **base_out,
2234
	git_repository *repo,
2235 2236
	git_annotated_commit *our_commit,
	git_annotated_commit *their_commit,
2237
	size_t recursion_level,
2238 2239
	const git_merge_options *opts);

2240 2241 2242 2243 2244 2245 2246 2247 2248
GIT_INLINE(int) insert_head_ids(
	git_array_oid_t *ids,
	const git_annotated_commit *annotated_commit)
{
	git_oid *id;
	size_t i;

	if (annotated_commit->type == GIT_ANNOTATED_COMMIT_REAL) {
		id = git_array_alloc(*ids);
2249
		GIT_ERROR_CHECK_ALLOC(id);
2250 2251 2252 2253 2254

		git_oid_cpy(id, git_commit_id(annotated_commit->commit));
	} else {
		for (i = 0; i < annotated_commit->parents.size; i++) {
			id = git_array_alloc(*ids);
2255
			GIT_ERROR_CHECK_ALLOC(id);
2256 2257 2258 2259 2260 2261 2262 2263

			git_oid_cpy(id, &annotated_commit->parents.ptr[i]);
		}
	}

	return 0;
}

2264
static int create_virtual_base(
2265
	git_annotated_commit **out,
2266
	git_repository *repo,
2267 2268
	git_annotated_commit *one,
	git_annotated_commit *two,
2269
	const git_merge_options *opts,
2270
	size_t recursion_level)
2271
{
2272
	git_annotated_commit *result = NULL;
2273
	git_index *index = NULL;
2274
	git_merge_options virtual_opts = GIT_MERGE_OPTIONS_INIT;
2275

2276 2277 2278 2279 2280 2281 2282
	/* Conflicts in the merge base creation do not propagate to conflicts
	 * in the result; the conflicted base will act as the common ancestor.
	 */
	if (opts)
		memcpy(&virtual_opts, opts, sizeof(git_merge_options));

	virtual_opts.flags &= ~GIT_MERGE_FAIL_ON_CONFLICT;
2283
	virtual_opts.flags |= GIT_MERGE_VIRTUAL_BASE;
2284

2285
	if ((merge_annotated_commits(&index, NULL, repo, one, two,
2286
			recursion_level + 1, &virtual_opts)) < 0)
2287
		return -1;
2288

2289
	result = git__calloc(1, sizeof(git_annotated_commit));
2290
	GIT_ERROR_CHECK_ALLOC(result);
2291 2292
	result->type = GIT_ANNOTATED_COMMIT_VIRTUAL;
	result->index = index;
2293

2294 2295 2296 2297 2298
	if (insert_head_ids(&result->parents, one) < 0 ||
		insert_head_ids(&result->parents, two) < 0) {
		git_annotated_commit_free(result);
		return -1;
	}
2299

2300
	*out = result;
2301 2302
	return 0;
}
2303

2304 2305 2306 2307 2308
static int compute_base(
	git_annotated_commit **out,
	git_repository *repo,
	const git_annotated_commit *one,
	const git_annotated_commit *two,
2309
	const git_merge_options *given_opts,
2310 2311 2312 2313 2314
	size_t recursion_level)
{
	git_array_oid_t head_ids = GIT_ARRAY_INIT;
	git_oidarray bases = {0};
	git_annotated_commit *base = NULL, *other = NULL, *new_base = NULL;
2315
	git_merge_options opts = GIT_MERGE_OPTIONS_INIT;
2316
	size_t i, base_count;
2317
	int error;
2318

2319
	*out = NULL;
2320

2321 2322 2323
	if (given_opts)
		memcpy(&opts, given_opts, sizeof(git_merge_options));

2324 2325 2326 2327 2328 2329 2330 2331
	/* With more than two commits, merge_bases_many finds the base of
	 * the first commit and a hypothetical merge of the others. Since
	 * "one" may itself be a virtual commit, which insert_head_ids
	 * substitutes multiple ancestors for, it needs to be added
	 * after "two" which is always a single real commit.
	 */
	if ((error = insert_head_ids(&head_ids, two)) < 0 ||
		(error = insert_head_ids(&head_ids, one)) < 0 ||
2332 2333
		(error = git_merge_bases_many(&bases, repo,
			head_ids.size, head_ids.ptr)) < 0)
2334 2335
		goto done;

2336 2337 2338 2339 2340 2341
	base_count = (opts.flags & GIT_MERGE_NO_RECURSIVE) ? 0 : bases.count;

	if (base_count)
		git_oidarray__reverse(&bases);

	if ((error = git_annotated_commit_lookup(&base, repo, &bases.ids[0])) < 0)
2342
		goto done;
2343

2344
	for (i = 1; i < base_count; i++) {
2345
		recursion_level++;
2346

2347 2348 2349
		if (opts.recursion_limit && recursion_level > opts.recursion_limit)
			break;

2350 2351
		if ((error = git_annotated_commit_lookup(&other, repo,
				&bases.ids[i])) < 0 ||
2352
			(error = create_virtual_base(&new_base, repo, base, other, &opts,
2353
				recursion_level)) < 0)
2354 2355
			goto done;

2356 2357
		git_annotated_commit_free(base);
		git_annotated_commit_free(other);
2358

2359 2360 2361
		base = new_base;
		new_base = NULL;
		other = NULL;
2362 2363 2364
	}

done:
2365 2366 2367 2368
	if (error == 0)
		*out = base;
	else
		git_annotated_commit_free(base);
2369

2370 2371
	git_annotated_commit_free(other);
	git_annotated_commit_free(new_base);
2372
	git_oidarray_dispose(&bases);
2373
	git_array_clear(head_ids);
2374 2375
	return error;
}
2376

2377 2378 2379 2380 2381 2382 2383 2384 2385 2386
static int iterator_for_annotated_commit(
	git_iterator **out,
	git_annotated_commit *commit)
{
	git_iterator_options opts = GIT_ITERATOR_OPTIONS_INIT;
	int error;

	opts.flags = GIT_ITERATOR_DONT_IGNORE_CASE;

	if (commit == NULL) {
2387
		error = git_iterator_for_nothing(out, &opts);
2388
	} else if (commit->type == GIT_ANNOTATED_COMMIT_VIRTUAL) {
2389
		error = git_iterator_for_index(out, git_index_owner(commit->index), commit->index, &opts);
2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401
	} else {
		if (!commit->tree &&
			(error = git_commit_tree(&commit->tree, commit->commit)) < 0)
			goto done;

		error = git_iterator_for_tree(out, commit->tree, &opts);
	}

done:
	return error;
}

2402 2403 2404
static int merge_annotated_commits(
	git_index **index_out,
	git_annotated_commit **base_out,
2405
	git_repository *repo,
2406 2407
	git_annotated_commit *ours,
	git_annotated_commit *theirs,
2408
	size_t recursion_level,
2409
	const git_merge_options *opts)
2410
{
2411
	git_annotated_commit *base = NULL;
2412
	git_iterator *base_iter = NULL, *our_iter = NULL, *their_iter = NULL;
2413
	int error;
2414

2415
	if ((error = compute_base(&base, repo, ours, theirs, opts,
2416
		recursion_level)) < 0) {
2417

2418 2419
		if (error != GIT_ENOTFOUND)
			goto done;
2420

2421
		git_error_clear();
2422
	}
2423

2424 2425 2426 2427 2428
	if ((error = iterator_for_annotated_commit(&base_iter, base)) < 0 ||
		(error = iterator_for_annotated_commit(&our_iter, ours)) < 0 ||
		(error = iterator_for_annotated_commit(&their_iter, theirs)) < 0 ||
		(error = git_merge__iterators(index_out, repo, base_iter, our_iter,
			their_iter, opts)) < 0)
2429 2430
		goto done;

2431 2432 2433 2434
	if (base_out) {
		*base_out = base;
		base = NULL;
	}
2435 2436

done:
2437
	git_annotated_commit_free(base);
2438 2439 2440
	git_iterator_free(base_iter);
	git_iterator_free(our_iter);
	git_iterator_free(their_iter);
2441 2442 2443
	return error;
}

2444

2445 2446 2447 2448 2449 2450 2451
int git_merge_commits(
	git_index **out,
	git_repository *repo,
	const git_commit *our_commit,
	const git_commit *their_commit,
	const git_merge_options *opts)
{
2452 2453 2454 2455 2456 2457
	git_annotated_commit *ours = NULL, *theirs = NULL, *base = NULL;
	int error = 0;

	if ((error = git_annotated_commit_from_commit(&ours, (git_commit *)our_commit)) < 0 ||
		(error = git_annotated_commit_from_commit(&theirs, (git_commit *)their_commit)) < 0)
		goto done;
2458

2459
	error = merge_annotated_commits(out, &base, repo, ours, theirs, 0, opts);
2460

2461 2462 2463 2464
done:
	git_annotated_commit_free(ours);
	git_annotated_commit_free(theirs);
	git_annotated_commit_free(base);
2465 2466 2467
	return error;
}

Edward Thomson committed
2468 2469 2470 2471
/* Merge setup / cleanup */

static int write_merge_head(
	git_repository *repo,
2472
	const git_annotated_commit *heads[],
Edward Thomson committed
2473 2474 2475
	size_t heads_len)
{
	git_filebuf file = GIT_FILEBUF_INIT;
2476
	git_str file_path = GIT_STR_INIT;
Edward Thomson committed
2477 2478 2479
	size_t i;
	int error = 0;

Edward Thomson committed
2480 2481
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(heads);
Edward Thomson committed
2482

2483
	if ((error = git_str_joinpath(&file_path, repo->gitdir, GIT_MERGE_HEAD_FILE)) < 0 ||
2484
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_CREATE_LEADING_DIRS, GIT_MERGE_FILE_MODE)) < 0)
Edward Thomson committed
2485 2486 2487
		goto cleanup;

	for (i = 0; i < heads_len; i++) {
2488
		if ((error = git_filebuf_printf(&file, "%s\n", heads[i]->id_str)) < 0)
Edward Thomson committed
2489 2490 2491
			goto cleanup;
	}

2492
	error = git_filebuf_commit(&file);
Edward Thomson committed
2493 2494 2495 2496 2497

cleanup:
	if (error < 0)
		git_filebuf_cleanup(&file);

2498
	git_str_dispose(&file_path);
Edward Thomson committed
2499 2500 2501 2502

	return error;
}

2503
static int write_merge_mode(git_repository *repo)
Edward Thomson committed
2504 2505
{
	git_filebuf file = GIT_FILEBUF_INIT;
2506
	git_str file_path = GIT_STR_INIT;
Edward Thomson committed
2507 2508
	int error = 0;

Edward Thomson committed
2509
	GIT_ASSERT_ARG(repo);
Edward Thomson committed
2510

2511
	if ((error = git_str_joinpath(&file_path, repo->gitdir, GIT_MERGE_MODE_FILE)) < 0 ||
2512
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_CREATE_LEADING_DIRS, GIT_MERGE_FILE_MODE)) < 0)
Edward Thomson committed
2513 2514
		goto cleanup;

2515 2516
	if ((error = git_filebuf_write(&file, "no-ff", 5)) < 0)
		goto cleanup;
2517

2518
	error = git_filebuf_commit(&file);
Edward Thomson committed
2519 2520 2521 2522 2523

cleanup:
	if (error < 0)
		git_filebuf_cleanup(&file);

2524
	git_str_dispose(&file_path);
Edward Thomson committed
2525 2526 2527 2528 2529

	return error;
}

struct merge_msg_entry {
2530
	const git_annotated_commit *merge_head;
Edward Thomson committed
2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717
	bool written;
};

static int msg_entry_is_branch(
	const struct merge_msg_entry *entry,
	git_vector *entries)
{
	GIT_UNUSED(entries);

	return (entry->written == 0 &&
		entry->merge_head->remote_url == NULL &&
		entry->merge_head->ref_name != NULL &&
		git__strncmp(GIT_REFS_HEADS_DIR, entry->merge_head->ref_name, strlen(GIT_REFS_HEADS_DIR)) == 0);
}

static int msg_entry_is_tracking(
	const struct merge_msg_entry *entry,
	git_vector *entries)
{
	GIT_UNUSED(entries);

	return (entry->written == 0 &&
		entry->merge_head->remote_url == NULL &&
		entry->merge_head->ref_name != NULL &&
		git__strncmp(GIT_REFS_REMOTES_DIR, entry->merge_head->ref_name, strlen(GIT_REFS_REMOTES_DIR)) == 0);
}

static int msg_entry_is_tag(
	const struct merge_msg_entry *entry,
	git_vector *entries)
{
	GIT_UNUSED(entries);

	return (entry->written == 0 &&
		entry->merge_head->remote_url == NULL &&
		entry->merge_head->ref_name != NULL &&
		git__strncmp(GIT_REFS_TAGS_DIR, entry->merge_head->ref_name, strlen(GIT_REFS_TAGS_DIR)) == 0);
}

static int msg_entry_is_remote(
	const struct merge_msg_entry *entry,
	git_vector *entries)
{
	if (entry->written == 0 &&
		entry->merge_head->remote_url != NULL &&
		entry->merge_head->ref_name != NULL &&
		git__strncmp(GIT_REFS_HEADS_DIR, entry->merge_head->ref_name, strlen(GIT_REFS_HEADS_DIR)) == 0)
	{
		struct merge_msg_entry *existing;

		/* Match only branches from the same remote */
		if (entries->length == 0)
			return 1;

		existing = git_vector_get(entries, 0);

		return (git__strcmp(existing->merge_head->remote_url,
			entry->merge_head->remote_url) == 0);
	}

	return 0;
}

static int msg_entry_is_oid(
	const struct merge_msg_entry *merge_msg_entry)
{
	return (merge_msg_entry->written == 0 &&
		merge_msg_entry->merge_head->ref_name == NULL &&
		merge_msg_entry->merge_head->remote_url == NULL);
}

static int merge_msg_entry_written(
	const struct merge_msg_entry *merge_msg_entry)
{
	return (merge_msg_entry->written == 1);
}

static int merge_msg_entries(
	git_vector *v,
	const struct merge_msg_entry *entries,
	size_t len,
	int (*match)(const struct merge_msg_entry *entry, git_vector *entries))
{
	size_t i;
	int matches, total = 0;

	git_vector_clear(v);

	for (i = 0; i < len; i++) {
		if ((matches = match(&entries[i], v)) < 0)
			return matches;
		else if (!matches)
			continue;

		git_vector_insert(v, (struct merge_msg_entry *)&entries[i]);
		total++;
	}

	return total;
}

static int merge_msg_write_entries(
	git_filebuf *file,
	git_vector *entries,
	const char *item_name,
	const char *item_plural_name,
	size_t ref_name_skip,
	const char *source,
	char sep)
{
	struct merge_msg_entry *entry;
	size_t i;
	int error = 0;

	if (entries->length == 0)
		return 0;

	if (sep && (error = git_filebuf_printf(file, "%c ", sep)) < 0)
		goto done;

	if ((error = git_filebuf_printf(file, "%s ",
		(entries->length == 1) ? item_name : item_plural_name)) < 0)
		goto done;

	git_vector_foreach(entries, i, entry) {
		if (i > 0 &&
			(error = git_filebuf_printf(file, "%s", (i == entries->length - 1) ? " and " : ", ")) < 0)
			goto done;

		if ((error = git_filebuf_printf(file, "'%s'", entry->merge_head->ref_name + ref_name_skip)) < 0)
			goto done;

		entry->written = 1;
	}

	if (source)
		error = git_filebuf_printf(file, " of %s", source);

done:
	return error;
}

static int merge_msg_write_branches(
	git_filebuf *file,
	git_vector *entries,
	char sep)
{
	return merge_msg_write_entries(file, entries,
		"branch", "branches", strlen(GIT_REFS_HEADS_DIR), NULL, sep);
}

static int merge_msg_write_tracking(
	git_filebuf *file,
	git_vector *entries,
	char sep)
{
	return merge_msg_write_entries(file, entries,
		"remote-tracking branch", "remote-tracking branches", 0, NULL, sep);
}

static int merge_msg_write_tags(
	git_filebuf *file,
	git_vector *entries,
	char sep)
{
	return merge_msg_write_entries(file, entries,
		"tag", "tags", strlen(GIT_REFS_TAGS_DIR), NULL, sep);
}

static int merge_msg_write_remotes(
	git_filebuf *file,
	git_vector *entries,
	char sep)
{
	const char *source;

	if (entries->length == 0)
		return 0;

	source = ((struct merge_msg_entry *)entries->contents[0])->merge_head->remote_url;

	return merge_msg_write_entries(file, entries,
		"branch", "branches", strlen(GIT_REFS_HEADS_DIR), source, sep);
}

static int write_merge_msg(
	git_repository *repo,
2718
	const git_annotated_commit *heads[],
Edward Thomson committed
2719 2720 2721
	size_t heads_len)
{
	git_filebuf file = GIT_FILEBUF_INIT;
2722
	git_str file_path = GIT_STR_INIT;
Edward Thomson committed
2723 2724 2725 2726 2727 2728
	struct merge_msg_entry *entries;
	git_vector matching = GIT_VECTOR_INIT;
	size_t i;
	char sep = 0;
	int error = 0;

Edward Thomson committed
2729 2730
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(heads);
Edward Thomson committed
2731 2732

	entries = git__calloc(heads_len, sizeof(struct merge_msg_entry));
2733
	GIT_ERROR_CHECK_ALLOC(entries);
Edward Thomson committed
2734

2735 2736
	if (git_vector_init(&matching, heads_len, NULL) < 0) {
		git__free(entries);
Edward Thomson committed
2737
		return -1;
2738
	}
Edward Thomson committed
2739 2740 2741 2742

	for (i = 0; i < heads_len; i++)
		entries[i].merge_head = heads[i];

2743
	if ((error = git_str_joinpath(&file_path, repo->gitdir, GIT_MERGE_MSG_FILE)) < 0 ||
2744
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_CREATE_LEADING_DIRS, GIT_MERGE_FILE_MODE)) < 0 ||
Edward Thomson committed
2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762
		(error = git_filebuf_write(&file, "Merge ", 6)) < 0)
		goto cleanup;

	/*
	 * This is to emulate the format of MERGE_MSG by core git.
	 *
	 * Core git will write all the commits specified by OID, in the order
	 * provided, until the first named branch or tag is reached, at which
	 * point all branches will be written in the order provided, then all
	 * tags, then all remote tracking branches and finally all commits that
	 * were specified by OID that were not already written.
	 *
	 * Yes.  Really.
	 */
	for (i = 0; i < heads_len; i++) {
		if (!msg_entry_is_oid(&entries[i]))
			break;

2763 2764
		if ((error = git_filebuf_printf(&file,
			"%scommit '%s'", (i > 0) ? "; " : "",
2765
			entries[i].merge_head->id_str)) < 0)
Edward Thomson committed
2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786
			goto cleanup;

		entries[i].written = 1;
	}

	if (i)
		sep = ';';

	if ((error = merge_msg_entries(&matching, entries, heads_len, msg_entry_is_branch)) < 0 ||
		(error = merge_msg_write_branches(&file, &matching, sep)) < 0)
		goto cleanup;

	if (matching.length)
		sep =',';

	if ((error = merge_msg_entries(&matching, entries, heads_len, msg_entry_is_tracking)) < 0 ||
		(error = merge_msg_write_tracking(&file, &matching, sep)) < 0)
		goto cleanup;

	if (matching.length)
		sep =',';
2787

Edward Thomson committed
2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811
	if ((error = merge_msg_entries(&matching, entries, heads_len, msg_entry_is_tag)) < 0 ||
		(error = merge_msg_write_tags(&file, &matching, sep)) < 0)
		goto cleanup;

	if (matching.length)
		sep =',';

	/* We should never be called with multiple remote branches, but handle
	 * it in case we are... */
	while ((error = merge_msg_entries(&matching, entries, heads_len, msg_entry_is_remote)) > 0) {
		if ((error = merge_msg_write_remotes(&file, &matching, sep)) < 0)
			goto cleanup;

		if (matching.length)
			sep =',';
	}

	if (error < 0)
		goto cleanup;

	for (i = 0; i < heads_len; i++) {
		if (merge_msg_entry_written(&entries[i]))
			continue;

2812
		if ((error = git_filebuf_printf(&file, "; commit '%s'",
2813
			entries[i].merge_head->id_str)) < 0)
Edward Thomson committed
2814 2815 2816 2817
			goto cleanup;
	}

	if ((error = git_filebuf_printf(&file, "\n")) < 0 ||
2818
		(error = git_filebuf_commit(&file)) < 0)
Edward Thomson committed
2819 2820 2821 2822 2823 2824
		goto cleanup;

cleanup:
	if (error < 0)
		git_filebuf_cleanup(&file);

2825
	git_str_dispose(&file_path);
Edward Thomson committed
2826 2827 2828 2829 2830 2831 2832

	git_vector_free(&matching);
	git__free(entries);

	return error;
}

2833 2834
int git_merge__setup(
	git_repository *repo,
2835 2836
	const git_annotated_commit *our_head,
	const git_annotated_commit *heads[],
2837 2838 2839 2840
	size_t heads_len)
{
	int error = 0;

Edward Thomson committed
2841 2842 2843
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(our_head);
	GIT_ASSERT_ARG(heads);
2844

2845
	if ((error = git_repository__set_orig_head(repo, git_annotated_commit_id(our_head))) == 0 &&
2846 2847 2848 2849 2850 2851 2852 2853
		(error = write_merge_head(repo, heads, heads_len)) == 0 &&
		(error = write_merge_mode(repo)) == 0) {
		error = write_merge_msg(repo, heads, heads_len);
	}

	return error;
}

2854 2855 2856
/* Merge branches */

static int merge_ancestor_head(
2857
	git_annotated_commit **ancestor_head,
2858
	git_repository *repo,
2859 2860
	const git_annotated_commit *our_head,
	const git_annotated_commit **their_heads,
2861 2862 2863
	size_t their_heads_len)
{
	git_oid *oids, ancestor_oid;
2864
	size_t i, alloc_len;
2865 2866
	int error = 0;

Edward Thomson committed
2867 2868 2869
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(our_head);
	GIT_ASSERT_ARG(their_heads);
2870

2871
	GIT_ERROR_CHECK_ALLOC_ADD(&alloc_len, their_heads_len, 1);
2872
	oids = git__calloc(alloc_len, sizeof(git_oid));
2873
	GIT_ERROR_CHECK_ALLOC(oids);
2874 2875 2876 2877

	git_oid_cpy(&oids[0], git_commit_id(our_head->commit));

	for (i = 0; i < their_heads_len; i++)
2878
		git_oid_cpy(&oids[i + 1], git_annotated_commit_id(their_heads[i]));
2879 2880 2881 2882

	if ((error = git_merge_base_many(&ancestor_oid, repo, their_heads_len + 1, oids)) < 0)
		goto on_error;

2883
	error = git_annotated_commit_lookup(ancestor_head, repo, &ancestor_oid);
2884 2885 2886 2887 2888 2889

on_error:
	git__free(oids);
	return error;
}

2890
static const char *merge_their_label(const char *branchname)
2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902
{
	const char *slash;

	if ((slash = strrchr(branchname, '/')) == NULL)
		return branchname;

	if (*(slash+1) == '\0')
		return "theirs";

	return slash+1;
}

2903
static int merge_normalize_checkout_opts(
2904
	git_checkout_options *out,
2905
	git_repository *repo,
2906
	const git_checkout_options *given_checkout_opts,
2907
	unsigned int checkout_strategy,
2908
	git_annotated_commit *ancestor,
2909
	const git_annotated_commit *our_head,
2910 2911
	const git_annotated_commit **their_heads,
	size_t their_heads_len)
2912
{
2913
	git_checkout_options default_checkout_opts = GIT_CHECKOUT_OPTIONS_INIT;
2914 2915 2916 2917
	int error = 0;

	GIT_UNUSED(repo);

2918
	if (given_checkout_opts != NULL)
2919 2920 2921
		memcpy(out, given_checkout_opts, sizeof(git_checkout_options));
	else
		memcpy(out, &default_checkout_opts, sizeof(git_checkout_options));
2922

2923
	out->checkout_strategy = checkout_strategy;
2924

2925
	if (!out->ancestor_label) {
2926
		if (ancestor && ancestor->type == GIT_ANNOTATED_COMMIT_REAL)
2927
			out->ancestor_label = git_commit_summary(ancestor->commit);
2928
		else if (ancestor)
2929
			out->ancestor_label = "merged common ancestors";
2930 2931
		else
			out->ancestor_label = "empty base";
2932 2933
	}

2934
	if (!out->our_label) {
2935
		if (our_head && our_head->ref_name)
2936
			out->our_label = our_head->ref_name;
2937
		else
2938
			out->our_label = "ours";
2939
	}
2940

2941
	if (!out->their_label) {
2942
		if (their_heads_len == 1 && their_heads[0]->ref_name)
2943
			out->their_label = merge_their_label(their_heads[0]->ref_name);
2944
		else if (their_heads_len == 1)
2945
			out->their_label = their_heads[0]->id_str;
2946
		else
2947
			out->their_label = "theirs";
2948 2949 2950 2951 2952 2953 2954 2955 2956 2957
	}

	return error;
}

static int merge_check_index(size_t *conflicts, git_repository *repo, git_index *index_new, git_vector *merged_paths)
{
	git_tree *head_tree = NULL;
	git_index *index_repo = NULL;
	git_iterator *iter_repo = NULL, *iter_new = NULL;
2958
	git_iterator_options iter_opts = GIT_ITERATOR_OPTIONS_INIT;
2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987
	git_diff *staged_diff_list = NULL, *index_diff_list = NULL;
	git_diff_delta *delta;
	git_diff_options opts = GIT_DIFF_OPTIONS_INIT;
	git_vector staged_paths = GIT_VECTOR_INIT;
	size_t i;
	int error = 0;

	GIT_UNUSED(merged_paths);

	*conflicts = 0;

	/* No staged changes may exist unless the change staged is identical to
	 * the result of the merge.  This allows one to apply to merge manually,
	 * then run merge.  Any other staged change would be overwritten by
	 * a reset merge.
	 */
	if ((error = git_repository_head_tree(&head_tree, repo)) < 0 ||
		(error = git_repository_index(&index_repo, repo)) < 0 ||
		(error = git_diff_tree_to_index(&staged_diff_list, repo, head_tree, index_repo, &opts)) < 0)
		goto done;

	if (staged_diff_list->deltas.length == 0)
		goto done;

	git_vector_foreach(&staged_diff_list->deltas, i, delta) {
		if ((error = git_vector_insert(&staged_paths, (char *)delta->new_file.path)) < 0)
			goto done;
	}

2988
	iter_opts.flags = GIT_ITERATOR_DONT_IGNORE_CASE;
2989 2990
	iter_opts.pathlist.strings = (char **)staged_paths.contents;
	iter_opts.pathlist.count = staged_paths.length;
2991

2992 2993
	if ((error = git_iterator_for_index(&iter_repo, repo, index_repo, &iter_opts)) < 0 ||
		(error = git_iterator_for_index(&iter_new, repo, index_new, &iter_opts)) < 0 ||
2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016
		(error = git_diff__from_iterators(&index_diff_list, repo, iter_repo, iter_new, &opts)) < 0)
		goto done;

	*conflicts = index_diff_list->deltas.length;

done:
	git_tree_free(head_tree);
	git_index_free(index_repo);
	git_iterator_free(iter_repo);
	git_iterator_free(iter_new);
	git_diff_free(staged_diff_list);
	git_diff_free(index_diff_list);
	git_vector_free(&staged_paths);

	return error;
}

static int merge_check_workdir(size_t *conflicts, git_repository *repo, git_index *index_new, git_vector *merged_paths)
{
	git_diff *wd_diff_list = NULL;
	git_diff_options opts = GIT_DIFF_OPTIONS_INIT;
	int error = 0;

Russell Belfer committed
3017 3018
	GIT_UNUSED(index_new);

3019 3020
	*conflicts = 0;

3021
	/* We need to have merged at least 1 file for the possibility to exist to
Dimitris Apostolou committed
3022
	 * have conflicts with the workdir. Passing 0 as the pathspec count parameter
3023 3024
	 * will consider all files in the working directory, that is, we may detect
	 * a conflict if there were untracked files in the workdir prior to starting
Dimitris Apostolou committed
3025
	 * the merge. This typically happens when cherry-picking a commit whose
3026 3027 3028 3029 3030
	 * changes have already been applied.
	 */
	if (merged_paths->length == 0)
		return 0;

3031 3032 3033 3034 3035 3036
	opts.flags |= GIT_DIFF_INCLUDE_UNTRACKED;

	/* Workdir changes may exist iff they do not conflict with changes that
	 * will be applied by the merge (including conflicts).  Ensure that there
	 * are no changes in the workdir to these paths.
	 */
3037
	opts.flags |= GIT_DIFF_DISABLE_PATHSPEC_MATCH;
3038 3039
	opts.pathspec.count = merged_paths->length;
	opts.pathspec.strings = (char **)merged_paths->contents;
3040
	opts.ignore_submodules = GIT_SUBMODULE_IGNORE_ALL;
3041

3042
	if ((error = git_diff_index_to_workdir(&wd_diff_list, repo, NULL, &opts)) < 0)
3043 3044 3045 3046 3047 3048 3049 3050 3051 3052
		goto done;

	*conflicts = wd_diff_list->deltas.length;

done:
	git_diff_free(wd_diff_list);

	return error;
}

3053
int git_merge__check_result(git_repository *repo, git_index *index_new)
3054
{
3055 3056
	git_tree *head_tree = NULL;
	git_iterator *iter_head = NULL, *iter_new = NULL;
3057
	git_iterator_options iter_opts = GIT_ITERATOR_OPTIONS_INIT;
3058 3059 3060
	git_diff *merged_list = NULL;
	git_diff_options opts = GIT_DIFF_OPTIONS_INIT;
	git_diff_delta *delta;
3061
	git_vector paths = GIT_VECTOR_INIT;
3062
	size_t i, index_conflicts = 0, wd_conflicts = 0, conflicts;
3063 3064 3065
	const git_index_entry *e;
	int error = 0;

3066 3067
	iter_opts.flags = GIT_ITERATOR_DONT_IGNORE_CASE;

3068
	if ((error = git_repository_head_tree(&head_tree, repo)) < 0 ||
3069
		(error = git_iterator_for_tree(&iter_head, head_tree, &iter_opts)) < 0 ||
3070
		(error = git_iterator_for_index(&iter_new, repo, index_new, &iter_opts)) < 0 ||
3071
		(error = git_diff__from_iterators(&merged_list, repo, iter_head, iter_new, &opts)) < 0)
3072 3073
		goto done;

3074 3075 3076
	git_vector_foreach(&merged_list->deltas, i, delta) {
		if ((error = git_vector_insert(&paths, (char *)delta->new_file.path)) < 0)
			goto done;
3077 3078 3079 3080 3081
	}

	for (i = 0; i < git_index_entrycount(index_new); i++) {
		e = git_index_get_byindex(index_new, i);

3082
		if (git_index_entry_is_conflict(e) &&
3083 3084
			(git_vector_last(&paths) == NULL ||
			strcmp(git_vector_last(&paths), e->path) != 0)) {
3085

3086 3087 3088
			if ((error = git_vector_insert(&paths, (char *)e->path)) < 0)
				goto done;
		}
3089 3090
	}

3091 3092 3093 3094
	/* Make sure the index and workdir state do not prevent merging */
	if ((error = merge_check_index(&index_conflicts, repo, index_new, &paths)) < 0 ||
		(error = merge_check_workdir(&wd_conflicts, repo, index_new, &paths)) < 0)
		goto done;
3095

3096
	if ((conflicts = index_conflicts + wd_conflicts) > 0) {
3097
		git_error_set(GIT_ERROR_MERGE, "%" PRIuZ " uncommitted change%s would be overwritten by merge",
3098
			conflicts, (conflicts != 1) ? "s" : "");
3099
		error = GIT_ECONFLICT;
3100 3101 3102
	}

done:
3103 3104 3105 3106 3107
	git_vector_free(&paths);
	git_tree_free(head_tree);
	git_iterator_free(iter_head);
	git_iterator_free(iter_new);
	git_diff_free(merged_list);
3108 3109 3110 3111

	return error;
}

3112 3113 3114 3115 3116
int git_merge__append_conflicts_to_merge_msg(
	git_repository *repo,
	git_index *index)
{
	git_filebuf file = GIT_FILEBUF_INIT;
3117
	git_str file_path = GIT_STR_INIT;
3118 3119 3120 3121
	const char *last = NULL;
	size_t i;
	int error;

3122 3123 3124
	if (!git_index_has_conflicts(index))
		return 0;

3125
	if ((error = git_str_joinpath(&file_path, repo->gitdir, GIT_MERGE_MSG_FILE)) < 0 ||
3126 3127 3128
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_APPEND, GIT_MERGE_FILE_MODE)) < 0)
		goto cleanup;

3129
	git_filebuf_printf(&file, "\n#Conflicts:\n");
3130 3131 3132 3133

	for (i = 0; i < git_index_entrycount(index); i++) {
		const git_index_entry *e = git_index_get_byindex(index, i);

3134
		if (!git_index_entry_is_conflict(e))
3135 3136 3137
			continue;

		if (last == NULL || strcmp(e->path, last) != 0)
3138
			git_filebuf_printf(&file, "#\t%s\n", e->path);
3139 3140 3141 3142 3143 3144 3145 3146 3147 3148

		last = e->path;
	}

	error = git_filebuf_commit(&file);

cleanup:
	if (error < 0)
		git_filebuf_cleanup(&file);

3149
	git_str_dispose(&file_path);
3150 3151 3152 3153

	return error;
}

3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164
static int merge_state_cleanup(git_repository *repo)
{
	const char *state_files[] = {
		GIT_MERGE_HEAD_FILE,
		GIT_MERGE_MODE_FILE,
		GIT_MERGE_MSG_FILE,
	};

	return git_repository__cleanup_files(repo, state_files, ARRAY_SIZE(state_files));
}

3165
static int merge_heads(
3166 3167
	git_annotated_commit **ancestor_head_out,
	git_annotated_commit **our_head_out,
3168
	git_repository *repo,
3169
	git_reference *our_ref,
3170
	const git_annotated_commit **their_heads,
3171
	size_t their_heads_len)
3172
{
3173
	git_annotated_commit *ancestor_head = NULL, *our_head = NULL;
3174 3175 3176 3177 3178
	int error = 0;

	*ancestor_head_out = NULL;
	*our_head_out = NULL;

3179
	if ((error = git_annotated_commit_from_ref(&our_head, repo, our_ref)) < 0)
3180 3181 3182 3183 3184 3185
		goto done;

	if ((error = merge_ancestor_head(&ancestor_head, repo, our_head, their_heads, their_heads_len)) < 0) {
		if (error != GIT_ENOTFOUND)
			goto done;

3186
		git_error_clear();
3187 3188 3189 3190 3191 3192 3193 3194
		error = 0;
	}

	*ancestor_head_out = ancestor_head;
	*our_head_out = our_head;

done:
	if (error < 0) {
3195 3196
		git_annotated_commit_free(ancestor_head);
		git_annotated_commit_free(our_head);
3197 3198 3199 3200 3201
	}

	return error;
}

3202
static int merge_preference(git_merge_preference_t *out, git_repository *repo)
3203 3204 3205 3206 3207
{
	git_config *config;
	const char *value;
	int bool_value, error = 0;

3208
	*out = GIT_MERGE_PREFERENCE_NONE;
3209

Edward Thomson committed
3210
	if ((error = git_repository_config_snapshot(&config, repo)) < 0)
3211 3212 3213 3214
		goto done;

	if ((error = git_config_get_string(&value, config, "merge.ff")) < 0) {
		if (error == GIT_ENOTFOUND) {
3215
			git_error_clear();
3216 3217 3218 3219 3220 3221 3222 3223
			error = 0;
		}

		goto done;
	}

	if (git_config_parse_bool(&bool_value, value) == 0) {
		if (!bool_value)
3224
			*out |= GIT_MERGE_PREFERENCE_NO_FASTFORWARD;
3225 3226
	} else {
		if (strcasecmp(value, "only") == 0)
3227
			*out |= GIT_MERGE_PREFERENCE_FASTFORWARD_ONLY;
3228 3229 3230 3231 3232 3233 3234
	}

done:
	git_config_free(config);
	return error;
}

3235
int git_merge_analysis_for_ref(
3236
	git_merge_analysis_t *analysis_out,
3237
	git_merge_preference_t *preference_out,
3238
	git_repository *repo,
3239
	git_reference *our_ref,
3240
	const git_annotated_commit **their_heads,
3241 3242
	size_t their_heads_len)
{
3243
	git_annotated_commit *ancestor_head = NULL, *our_head = NULL;
3244
	int error = 0;
3245
	bool unborn;
3246

Edward Thomson committed
3247 3248 3249 3250
	GIT_ASSERT_ARG(analysis_out);
	GIT_ASSERT_ARG(preference_out);
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(their_heads && their_heads_len > 0);
3251

3252
	if (their_heads_len != 1) {
3253
		git_error_set(GIT_ERROR_MERGE, "can only merge a single branch");
3254 3255 3256 3257
		error = -1;
		goto done;
	}

3258
	*analysis_out = GIT_MERGE_ANALYSIS_NONE;
3259

3260
	if ((error = merge_preference(preference_out, repo)) < 0)
3261
		goto done;
3262

3263 3264 3265 3266
	if ((error = git_reference__is_unborn_head(&unborn, our_ref, repo)) < 0)
		goto done;

	if (unborn) {
3267
		*analysis_out |= GIT_MERGE_ANALYSIS_FASTFORWARD | GIT_MERGE_ANALYSIS_UNBORN;
3268
		error = 0;
3269
		goto done;
3270 3271
	}

3272
	if ((error = merge_heads(&ancestor_head, &our_head, repo, our_ref, their_heads, their_heads_len)) < 0)
3273
		goto done;
3274

3275
	/* We're up-to-date if we're trying to merge our own common ancestor. */
3276 3277
	if (ancestor_head && git_oid_equal(
		git_annotated_commit_id(ancestor_head), git_annotated_commit_id(their_heads[0])))
3278
		*analysis_out |= GIT_MERGE_ANALYSIS_UP_TO_DATE;
3279

3280
	/* We're fastforwardable if we're our own common ancestor. */
3281 3282
	else if (ancestor_head && git_oid_equal(
		git_annotated_commit_id(ancestor_head), git_annotated_commit_id(our_head)))
3283
		*analysis_out |= GIT_MERGE_ANALYSIS_FASTFORWARD | GIT_MERGE_ANALYSIS_NORMAL;
3284

3285 3286
	/* Otherwise, just a normal merge is possible. */
	else
3287
		*analysis_out |= GIT_MERGE_ANALYSIS_NORMAL;
3288

3289
done:
3290 3291
	git_annotated_commit_free(ancestor_head);
	git_annotated_commit_free(our_head);
3292 3293
	return error;
}
3294

3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305
int git_merge_analysis(
	git_merge_analysis_t *analysis_out,
	git_merge_preference_t *preference_out,
	git_repository *repo,
	const git_annotated_commit **their_heads,
	size_t their_heads_len)
{
	git_reference *head_ref = NULL;
	int error = 0;

	if ((error = git_reference_lookup(&head_ref, repo, GIT_HEAD_FILE)) < 0) {
3306
		git_error_set(GIT_ERROR_MERGE, "failed to lookup HEAD reference");
3307 3308 3309 3310 3311 3312 3313 3314 3315 3316
		return error;
	}

	error = git_merge_analysis_for_ref(analysis_out, preference_out, repo, head_ref, their_heads, their_heads_len);

	git_reference_free(head_ref);

	return error;
}

3317 3318
int git_merge(
	git_repository *repo,
3319
	const git_annotated_commit **their_heads,
3320
	size_t their_heads_len,
3321
	const git_merge_options *merge_opts,
3322
	const git_checkout_options *given_checkout_opts)
3323 3324
{
	git_reference *our_ref = NULL;
3325
	git_checkout_options checkout_opts;
3326
	git_annotated_commit *our_head = NULL, *base = NULL;
3327
	git_index *repo_index = NULL, *index = NULL;
3328
	git_indexwriter indexwriter = GIT_INDEXWRITER_INIT;
3329
	unsigned int checkout_strategy;
3330
	int error = 0;
3331

Edward Thomson committed
3332 3333
	GIT_ASSERT_ARG(repo);
	GIT_ASSERT_ARG(their_heads && their_heads_len > 0);
3334 3335

	if (their_heads_len != 1) {
3336
		git_error_set(GIT_ERROR_MERGE, "can only merge a single branch");
3337 3338 3339
		return -1;
	}

3340 3341
	if ((error = git_repository__ensure_not_bare(repo, "merge")) < 0)
		goto done;
3342

3343 3344 3345
	checkout_strategy = given_checkout_opts ?
		given_checkout_opts->checkout_strategy :
		GIT_CHECKOUT_SAFE;
3346

3347 3348 3349
	if ((error = git_indexwriter_init_for_operation(&indexwriter, repo,
		&checkout_strategy)) < 0)
		goto done;
3350

3351 3352
	if ((error = git_repository_index(&repo_index, repo) < 0) ||
	    (error = git_index_read(repo_index, 0) < 0))
3353 3354
		goto done;

3355 3356 3357 3358 3359
	/* Write the merge setup files to the repository. */
	if ((error = git_annotated_commit_from_head(&our_head, repo)) < 0 ||
		(error = git_merge__setup(repo, our_head, their_heads,
			their_heads_len)) < 0)
		goto done;
3360

3361
	/* TODO: octopus */
3362

3363
	if ((error = merge_annotated_commits(&index, &base, repo, our_head,
3364
			(git_annotated_commit *)their_heads[0], 0, merge_opts)) < 0 ||
3365
		(error = git_merge__check_result(repo, index)) < 0 ||
3366 3367
		(error = git_merge__append_conflicts_to_merge_msg(repo, index)) < 0)
		goto done;
3368

3369
	/* check out the merge results */
3370

3371 3372
	if ((error = merge_normalize_checkout_opts(&checkout_opts, repo,
			given_checkout_opts, checkout_strategy,
3373
			base, our_head, their_heads, their_heads_len)) < 0 ||
3374 3375 3376 3377
		(error = git_checkout_index(repo, index, &checkout_opts)) < 0)
		goto done;

	error = git_indexwriter_commit(&indexwriter);
3378 3379

done:
3380 3381
	if (error < 0)
		merge_state_cleanup(repo);
3382

3383
	git_indexwriter_cleanup(&indexwriter);
3384
	git_index_free(index);
3385
	git_annotated_commit_free(our_head);
3386
	git_annotated_commit_free(base);
3387
	git_reference_free(our_ref);
3388
	git_index_free(repo_index);
3389 3390 3391 3392

	return error;
}

3393
int git_merge_options_init(git_merge_options *opts, unsigned int version)
3394
{
3395 3396 3397
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		opts, version, git_merge_options, GIT_MERGE_OPTIONS_INIT);
	return 0;
3398
}
3399

3400
#ifndef GIT_DEPRECATE_HARD
3401 3402 3403 3404
int git_merge_init_options(git_merge_options *opts, unsigned int version)
{
	return git_merge_options_init(opts, version);
}
3405
#endif
3406 3407

int git_merge_file_input_init(git_merge_file_input *input, unsigned int version)
3408
{
3409 3410 3411
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		input, version, git_merge_file_input, GIT_MERGE_FILE_INPUT_INIT);
	return 0;
3412 3413
}

3414
#ifndef GIT_DEPRECATE_HARD
3415 3416 3417 3418
int git_merge_file_init_input(git_merge_file_input *input, unsigned int version)
{
	return git_merge_file_input_init(input, version);
}
3419
#endif
3420 3421

int git_merge_file_options_init(
3422
	git_merge_file_options *opts, unsigned int version)
3423
{
3424 3425 3426
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		opts, version, git_merge_file_options, GIT_MERGE_FILE_OPTIONS_INIT);
	return 0;
3427
}
3428

3429
#ifndef GIT_DEPRECATE_HARD
3430 3431 3432 3433 3434
int git_merge_file_init_options(
	git_merge_file_options *opts, unsigned int version)
{
	return git_merge_file_options_init(opts, version);
}
3435
#endif