merge.c 72.2 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.
 */

Edward Thomson committed
8 9 10
#include "common.h"
#include "posix.h"
#include "buffer.h"
Edward Thomson committed
11
#include "repository.h"
12
#include "revwalk.h"
Edward Thomson committed
13
#include "commit_list.h"
Edward Thomson committed
14
#include "merge.h"
Edward Thomson committed
15
#include "path.h"
Edward Thomson committed
16
#include "refs.h"
Edward Thomson committed
17 18 19 20 21 22 23 24
#include "object.h"
#include "iterator.h"
#include "refs.h"
#include "diff.h"
#include "checkout.h"
#include "tree.h"
#include "merge_file.h"
#include "blob.h"
Edward Thomson committed
25
#include "oid.h"
26 27
#include "index.h"
#include "filebuf.h"
28
#include "config.h"
29
#include "oidarray.h"
30
#include "annotated_commit.h"
Edward Thomson committed
31 32

#include "git2/types.h"
Edward Thomson committed
33
#include "git2/repository.h"
Edward Thomson committed
34 35
#include "git2/object.h"
#include "git2/commit.h"
Edward Thomson committed
36
#include "git2/merge.h"
Edward Thomson committed
37
#include "git2/refs.h"
Edward Thomson committed
38
#include "git2/reset.h"
Edward Thomson committed
39 40 41 42
#include "git2/checkout.h"
#include "git2/signature.h"
#include "git2/config.h"
#include "git2/tree.h"
43
#include "git2/oidarray.h"
44
#include "git2/annotated_commit.h"
45
#include "git2/sys/index.h"
46
#include "git2/sys/hashsig.h"
Edward Thomson committed
47 48

#define GIT_MERGE_INDEX_ENTRY_EXISTS(X)	((X).mode != 0)
Edward Thomson committed
49
#define GIT_MERGE_INDEX_ENTRY_ISFILE(X) S_ISREG((X).mode)
Edward Thomson committed
50 51 52 53 54 55 56 57 58 59 60 61 62 63

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

64 65 66 67 68
GIT_INLINE(int) merge_diff_detect_binary(
	bool *binary_out,
	git_repository *repo,
	const git_merge_diff *conflict);

Edward Thomson committed
69

Edward Thomson committed
70 71
/* Merge base computation */

72
int merge_bases_many(git_commit_list **out, git_revwalk **walk_out, git_repository *repo, size_t length, const git_oid input_array[])
73
{
74
	git_revwalk *walk = NULL;
75 76
	git_vector list;
	git_commit_list *result = NULL;
77
	git_commit_list_node *commit;
78 79 80 81
	int error = -1;
	unsigned int i;

	if (length < 2) {
82
		giterr_set(GITERR_INVALID, "At least two commits are required to find an ancestor. Provided 'length' was %" PRIuZ ".", length);
83 84 85 86 87 88 89
		return -1;
	}

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

	if (git_revwalk_new(&walk, repo) < 0)
90
		goto on_error;
91 92

	for (i = 1; i < length; i++) {
93
		commit = git_revwalk__commit_lookup(walk, &input_array[i]);
94
		if (commit == NULL)
95
			goto on_error;
96 97 98 99

		git_vector_insert(&list, commit);
	}

100
	commit = git_revwalk__commit_lookup(walk, &input_array[0]);
101
	if (commit == NULL)
102
		goto on_error;
103 104

	if (git_merge__bases_many(&result, walk, commit, &list) < 0)
105
		goto on_error;
106 107

	if (!result) {
108
		giterr_set(GITERR_MERGE, "No merge base found");
109
		error = GIT_ENOTFOUND;
110
		goto on_error;
111 112
	}

113 114
	*out = result;
	*walk_out = walk;
115

116 117
	git_vector_free(&list);
	return 0;
118

119
on_error:
120
	git_vector_free(&list);
121
	git_revwalk_free(walk);
122 123 124
	return error;
}

125
int git_merge_base_many(git_oid *out, git_repository *repo, size_t length, const git_oid input_array[])
126 127
{
	git_revwalk *walk;
128 129
	git_commit_list *result = NULL;
	int error = 0;
130 131 132

	assert(out && repo && input_array);

133 134
	if ((error = merge_bases_many(&result, &walk, repo, length, input_array)) < 0)
		return error;
135

136
	git_oid_cpy(out, &result->item->oid);
137

138 139
	git_commit_list_free(&result);
	git_revwalk_free(walk);
140

141 142
	return 0;
}
143

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

151
	assert(out && repo && input_array);
152

153 154
	if ((error = merge_bases_many(&result, &walk, repo, length, input_array)) < 0)
		return error;
155 156 157

	git_array_init(array);

158 159
	list = result;
	while (list) {
160
		git_oid *id = git_array_alloc(array);
161 162
		if (id == NULL) {
			error = -1;
163
			goto cleanup;
164
		}
165

166 167
		git_oid_cpy(id, &list->item->oid);
		list = list->next;
168 169 170 171 172 173 174
	}

	git_oidarray__from_array(out, &array);

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

176 177 178
	return error;
}

179 180 181 182 183 184 185 186 187
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;

	assert(out && repo && input_array);

	if (length < 2) {
188
		giterr_set(GITERR_INVALID, "At least two commits are required to find an ancestor. Provided 'length' was %" PRIuZ ".", length);
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203
		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;
}

204
static int merge_bases(git_commit_list **out, git_revwalk **walk_out, git_repository *repo, const git_oid *one, const git_oid *two)
205 206 207 208 209 210 211 212 213 214
{
	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;

215
	commit = git_revwalk__commit_lookup(walk, two);
216 217 218 219 220 221 222 223 224
	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;

225
	commit = git_revwalk__commit_lookup(walk, one);
226 227 228 229 230 231 232 233
	if (commit == NULL)
		goto on_error;

	if (git_merge__bases_many(&result, walk, commit, &list) < 0)
		goto on_error;

	if (!result) {
		git_revwalk_free(walk);
234
		giterr_set(GITERR_MERGE, "No merge base found");
235 236 237
		return GIT_ENOTFOUND;
	}

238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257
	*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;

258 259 260 261 262
	git_oid_cpy(out, &result->item->oid);
	git_commit_list_free(&result);
	git_revwalk_free(walk);

	return 0;
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291
}

int git_merge_bases(git_oidarray *out, git_repository *repo, const git_oid *one, const git_oid *two)
{
	int error;
        git_revwalk *walk;
	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;
292 293

on_error:
294
	git_commit_list_free(&result);
295 296 297 298 299 300
	git_revwalk_free(walk);
	return -1;
}

static int interesting(git_pqueue *list)
{
301 302 303 304
	size_t i;

	for (i = 0; i < git_pqueue_size(list); i++) {
		git_commit_list_node *commit = git_pqueue_get(list, i);
305 306 307 308 309 310 311 312 313 314 315 316 317 318 319
		if ((commit->flags & STALE) == 0)
			return 1;
	}

	return 0;
}

int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_list_node *one, git_vector *twos)
{
	int error;
	unsigned int i;
	git_commit_list_node *two;
	git_commit_list *result = NULL, *tmp = NULL;
	git_pqueue list;

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

326 327 328 329 330 331
	/* 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;
	}

332
	if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_time_cmp) < 0)
333 334 335
		return -1;

	if (git_commit_list_parse(walk, one) < 0)
Edward Thomson committed
336
		return -1;
337 338 339 340 341 342

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

	git_vector_foreach(twos, i, two) {
343 344 345
		if (git_commit_list_parse(walk, two) < 0)
			return -1;

346
		two->flags |= PARENT2;
347

348 349 350 351 352 353
		if (git_pqueue_insert(&list, two) < 0)
			return -1;
	}

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

357 358
		if (commit == NULL)
			break;
359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403

		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;

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

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

	while (tmp) {
		struct git_commit_list *next = tmp->next;
		if (!(tmp->item->flags & STALE))
			if (git_commit_list_insert_by_date(tmp->item, &result) == NULL)
				return -1;

		git__free(tmp);
		tmp = next;
	}

	*out = result;
	return 0;
}
404

405 406
int git_repository_mergehead_foreach(
	git_repository *repo,
407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437
	git_repository_mergehead_foreach_cb cb,
	void *payload)
{
	git_buf merge_head_path = GIT_BUF_INIT, merge_head_file = GIT_BUF_INIT;
	char *buffer, *line;
	size_t line_num = 1;
	git_oid oid;
	int error = 0;

	assert(repo && cb);

	if ((error = git_buf_joinpath(&merge_head_path, repo->path_repository,
		GIT_MERGE_HEAD_FILE)) < 0)
		return error;

	if ((error = git_futils_readbuffer(&merge_head_file,
		git_buf_cstr(&merge_head_path))) < 0)
		goto cleanup;

	buffer = merge_head_file.ptr;

	while ((line = git__strsep(&buffer, "\n")) != NULL) {
		if (strlen(line) != GIT_OID_HEXSZ) {
			giterr_set(GITERR_INVALID, "Unable to parse OID - invalid length");
			error = -1;
			goto cleanup;
		}

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

438
		if ((error = cb(&oid, payload)) != 0) {
439
			giterr_set_after_callback(error);
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457
			goto cleanup;
		}

		++line_num;
	}

	if (*buffer) {
		giterr_set(GITERR_MERGE, "No EOL at line %d", line_num);
		error = -1;
		goto cleanup;
	}

cleanup:
	git_buf_free(&merge_head_path);
	git_buf_free(&merge_head_file);

	return error;
}
Edward Thomson committed
458 459 460 461 462 463 464 465 466

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 &&
467
		(value = git_oid__cmp(&a->id, &b->id)) == 0)
Edward Thomson committed
468 469 470 471 472 473 474 475 476 477 478 479
		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)
{
480
	int ours_empty, theirs_empty;
Edward Thomson committed
481 482 483 484 485 486 487 488 489 490 491
	int ours_changed, theirs_changed, ours_theirs_differ;
	git_index_entry const *result = NULL;
	int error = 0;

	assert(resolved && diff_list && conflict);

	*resolved = 0;

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

Edward Thomson committed
493 494 495 496 497 498
	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
499

Edward Thomson committed
500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554
	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
555

Edward Thomson committed
556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606
	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;

	assert(resolved && diff_list && conflict);

	*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
607

Edward Thomson committed
608
	assert(resolved && diff_list && conflict);
nulltoken committed
609

Edward Thomson committed
610 611 612 613 614 615 616 617
	*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
618

Edward Thomson committed
619 620 621 622 623 624 625 626 627
	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;

628 629
	ours_changed = (git_oid__cmp(&conflict->ancestor_entry.id, &conflict->our_entry.id) != 0);
	theirs_changed = (git_oid__cmp(&conflict->ancestor_entry.id, &conflict->their_entry.id) != 0);
nulltoken committed
630

Edward Thomson committed
631 632
	/* if both are modified (and not to a common target) require a merge */
	if (ours_changed && theirs_changed &&
633
		git_oid__cmp(&conflict->our_entry.id, &conflict->their_entry.id) != 0)
Edward Thomson committed
634 635 636 637
		return 0;

	if ((merged = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry))) == NULL)
		return -1;
nulltoken committed
638

Edward Thomson committed
639 640 641 642 643 644 645 646 647
	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
648

Edward Thomson committed
649
	*resolved = 1;
nulltoken committed
650

Edward Thomson committed
651 652
	git_vector_insert(&diff_list->staged, merged);
	git_vector_insert(&diff_list->resolved, (git_merge_diff *)conflict);
nulltoken committed
653

Edward Thomson committed
654 655 656 657 658 659 660
	return error;
}

static int merge_conflict_resolve_automerge(
	int *resolved,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict,
661
	unsigned int merge_file_favor,
662
	unsigned int file_flags)
Edward Thomson committed
663
{
664 665 666
	const git_index_entry *ancestor = NULL, *ours = NULL, *theirs = NULL;
	git_merge_file_options opts = GIT_MERGE_FILE_OPTIONS_INIT;
	git_merge_file_result result = {0};
Edward Thomson committed
667 668 669 670
	git_index_entry *index_entry;
	git_odb *odb = NULL;
	git_oid automerge_oid;
	int error = 0;
671
	bool binary = false;
nulltoken committed
672

Edward Thomson committed
673
	assert(resolved && diff_list && conflict);
nulltoken committed
674

Edward Thomson committed
675
	*resolved = 0;
nulltoken committed
676

677 678 679
	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ||
		!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry))
		return 0;
680

Edward Thomson committed
681 682 683 684
	/* Reject D/F conflicts */
	if (conflict->type == GIT_MERGE_DIFF_DIRECTORY_FILE)
		return 0;

Edward Thomson committed
685 686 687 688 689 690
	/* Reject submodules. */
	if (S_ISGITLINK(conflict->ancestor_entry.mode) ||
		S_ISGITLINK(conflict->our_entry.mode) ||
		S_ISGITLINK(conflict->their_entry.mode))
		return 0;

Edward Thomson committed
691 692 693 694 695 696 697 698 699 700 701 702 703 704 705
	/* Reject link/file conflicts. */
	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 0;

	/* Reject name conflicts */
	if (conflict->type == GIT_MERGE_DIFF_BOTH_RENAMED_2_TO_1 ||
		conflict->type == GIT_MERGE_DIFF_RENAMED_ADDED)
		return 0;

	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)
		return 0;

706
	/* Reject binary conflicts */
707 708 709
	if ((error = merge_diff_detect_binary(&binary, diff_list->repo, conflict)) < 0)
		return error;
	if (binary)
710 711
		return 0;

712 713 714 715 716 717 718 719
	ancestor = GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry) ?
		&conflict->ancestor_entry : NULL;
	ours = GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
		&conflict->our_entry : NULL;
	theirs = GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
		&conflict->their_entry : NULL;

	opts.favor = merge_file_favor;
720
	opts.flags = file_flags;
721

Edward Thomson committed
722
	if ((error = git_repository_odb(&odb, diff_list->repo)) < 0 ||
723
		(error = git_merge_file_from_index(&result, diff_list->repo, ancestor, ours, theirs, &opts)) < 0 ||
Edward Thomson committed
724
		!result.automergeable ||
725
		(error = git_odb_write(&automerge_oid, odb, result.ptr, result.len, GIT_OBJ_BLOB)) < 0)
Edward Thomson committed
726
		goto done;
nulltoken committed
727

Edward Thomson committed
728 729 730 731 732 733 734 735
	if ((index_entry = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry))) == NULL)
	GITERR_CHECK_ALLOC(index_entry);

	index_entry->path = git_pool_strdup(&diff_list->pool, result.path);
	GITERR_CHECK_ALLOC(index_entry->path);

	index_entry->file_size = result.len;
	index_entry->mode = result.mode;
736
	git_oid_cpy(&index_entry->id, &automerge_oid);
nulltoken committed
737

Edward Thomson committed
738 739 740 741 742 743 744 745
	git_vector_insert(&diff_list->staged, index_entry);
	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
746

Edward Thomson committed
747 748 749 750 751 752 753
	return error;
}

static int merge_conflict_resolve(
	int *out,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict,
754
	unsigned int merge_file_favor,
755
	unsigned int file_flags)
Edward Thomson committed
756 757 758
{
	int resolved = 0;
	int error = 0;
nulltoken committed
759

Edward Thomson committed
760
	*out = 0;
nulltoken committed
761

Edward Thomson committed
762 763 764
	if ((error = merge_conflict_resolve_trivial(&resolved, diff_list, conflict)) < 0)
		goto done;

765 766
	if (!resolved && (error = merge_conflict_resolve_one_removed(&resolved, diff_list, conflict)) < 0)
		goto done;
nulltoken committed
767

768 769
	if (!resolved && (error = merge_conflict_resolve_one_renamed(&resolved, diff_list, conflict)) < 0)
		goto done;
Edward Thomson committed
770

771
	if (!resolved && (error = merge_conflict_resolve_automerge(&resolved, diff_list, conflict,
772
		merge_file_favor, file_flags)) < 0)
773
		goto done;
Edward Thomson committed
774 775

	*out = resolved;
nulltoken committed
776

Edward Thomson committed
777 778 779 780
done:
	return error;
}

Edward Thomson committed
781 782 783 784 785 786 787 788 789 790 791 792 793 794
/* Rename detection and coalescing */

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

static int index_entry_similarity_exact(
	git_repository *repo,
	git_index_entry *a,
	size_t a_idx,
	git_index_entry *b,
	size_t b_idx,
	void **cache,
795
	const git_merge_options *opts)
Edward Thomson committed
796 797 798 799 800 801 802
{
	GIT_UNUSED(repo);
	GIT_UNUSED(a_idx);
	GIT_UNUSED(b_idx);
	GIT_UNUSED(cache);
	GIT_UNUSED(opts);

803
	if (git_oid__cmp(&a->id, &b->id) == 0)
Edward Thomson committed
804
		return 100;
nulltoken committed
805

Edward Thomson committed
806 807 808 809 810 811 812
	return 0;
}

static int index_entry_similarity_calc(
	void **out,
	git_repository *repo,
	git_index_entry *entry,
813
	const git_merge_options *opts)
Edward Thomson committed
814 815 816
{
	git_blob *blob;
	git_diff_file diff_file = {{{0}}};
817
	git_off_t blobsize;
Edward Thomson committed
818
	int error;
nulltoken committed
819

Edward Thomson committed
820 821
	*out = NULL;

822
	if ((error = git_blob_lookup(&blob, repo, &entry->id)) < 0)
Edward Thomson committed
823
		return error;
nulltoken committed
824

825
	git_oid_cpy(&diff_file.id, &entry->id);
Edward Thomson committed
826 827 828 829
	diff_file.path = entry->path;
	diff_file.size = entry->file_size;
	diff_file.mode = entry->mode;
	diff_file.flags = 0;
nulltoken committed
830

831 832 833 834 835
	blobsize = git_blob_rawsize(blob);

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

Edward Thomson committed
837
	error = opts->metric->buffer_signature(out, &diff_file,
838
		git_blob_rawcontent(blob), (size_t)blobsize,
Edward Thomson committed
839
		opts->metric->payload);
nulltoken committed
840

Edward Thomson committed
841 842 843 844 845 846 847 848 849 850 851 852
	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,
853
	const git_merge_options *opts)
Edward Thomson committed
854 855 856
{
	int score = 0;
	int error = 0;
nulltoken committed
857

Edward Thomson committed
858 859
	if (GIT_MODE_TYPE(a->mode) != GIT_MODE_TYPE(b->mode))
		return 0;
nulltoken committed
860

Edward Thomson committed
861 862 863 864 865
	/* update signature cache if needed */
	if (!cache[a_idx] && (error = index_entry_similarity_calc(&cache[a_idx], repo, a, opts)) < 0)
		return error;
	if (!cache[b_idx] && (error = index_entry_similarity_calc(&cache[b_idx], repo, b, opts)) < 0)
		return error;
nulltoken committed
866

Edward Thomson committed
867 868 869 870 871 872 873 874
	/* some metrics may not wish to process this file (too big / too small) */
	if (!cache[a_idx] || !cache[b_idx])
		return 0;

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

Edward Thomson committed
876 877 878 879 880
	/* clip score */
	if (score < 0)
		score = 0;
	else if (score > 100)
		score = 100;
nulltoken committed
881

Edward Thomson committed
882 883 884 885 886 887 888 889
	return score;
}

static int merge_diff_mark_similarity(
	git_repository *repo,
	git_merge_diff_list *diff_list,
	struct merge_diff_similarity *similarity_ours,
	struct merge_diff_similarity *similarity_theirs,
890
	int (*similarity_fn)(git_repository *, git_index_entry *, size_t, git_index_entry *, size_t, void **, const git_merge_options *),
Edward Thomson committed
891
	void **cache,
892
	const git_merge_options *opts)
Edward Thomson committed
893 894 895 896
{
	size_t i, j;
	git_merge_diff *conflict_src, *conflict_tgt;
	int similarity;
nulltoken committed
897

Edward Thomson committed
898 899 900 901 902 903 904
	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
905

Edward Thomson committed
906 907 908
		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
909

Edward Thomson committed
910 911
			if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->ancestor_entry))
				continue;
nulltoken committed
912

Edward Thomson committed
913 914 915
			if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->our_entry) &&
				!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->our_entry)) {
				similarity = similarity_fn(repo, &conflict_src->ancestor_entry, i, &conflict_tgt->our_entry, our_idx, cache, opts);
nulltoken committed
916

Edward Thomson committed
917
				if (similarity == GIT_EBUFS)
nulltoken committed
918
					continue;
Edward Thomson committed
919 920
				else if (similarity < 0)
					return similarity;
nulltoken committed
921

Edward Thomson committed
922 923 924 925 926
				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
927

Edward Thomson committed
928 929
					if (similarity_ours[j].similarity > 0)
						similarity_ours[similarity_ours[j].other_idx].similarity = 0;
nulltoken committed
930

Edward Thomson committed
931 932
					similarity_ours[i].similarity = similarity;
					similarity_ours[i].other_idx = j;
nulltoken committed
933

Edward Thomson committed
934 935 936 937
					similarity_ours[j].similarity = similarity;
					similarity_ours[j].other_idx = i;
				}
			}
nulltoken committed
938

Edward Thomson committed
939 940 941
			if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->their_entry) &&
				!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_src->their_entry)) {
				similarity = similarity_fn(repo, &conflict_src->ancestor_entry, i, &conflict_tgt->their_entry, their_idx, cache, opts);
nulltoken committed
942

Edward Thomson committed
943 944 945 946 947
				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
948

Edward Thomson committed
949 950
					if (similarity_theirs[j].similarity > 0)
						similarity_theirs[similarity_theirs[j].other_idx].similarity = 0;
nulltoken committed
951

Edward Thomson committed
952 953
					similarity_theirs[i].similarity = similarity;
					similarity_theirs[i].other_idx = j;
nulltoken committed
954

Edward Thomson committed
955 956 957 958 959 960
					similarity_theirs[j].similarity = similarity;
					similarity_theirs[j].other_idx = i;
				}
			}
		}
	}
nulltoken committed
961

Edward Thomson committed
962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992
	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,
993
	const git_merge_options *opts)
Edward Thomson committed
994 995
{
	git_merge_diff *ours_source = NULL, *theirs_source = NULL;
nulltoken committed
996

Edward Thomson committed
997 998
	if (ours_renamed)
		ours_source = diff_list->conflicts.contents[ours_source_idx];
nulltoken committed
999

Edward Thomson committed
1000 1001
	if (theirs_renamed)
		theirs_source = diff_list->conflicts.contents[theirs_source_idx];
nulltoken committed
1002

Edward Thomson committed
1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015
	/* 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
1016

Edward Thomson committed
1017 1018 1019 1020
		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
1021

Edward Thomson committed
1022 1023
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(ours_source->their_entry))
			ours_source->type = GIT_MERGE_DIFF_RENAMED_DELETED;
nulltoken committed
1024

Edward Thomson committed
1025 1026 1027 1028 1029 1030
		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
1031

Edward Thomson committed
1032 1033 1034 1035
		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
1036

Edward Thomson committed
1037 1038
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(theirs_source->our_entry))
			theirs_source->type = GIT_MERGE_DIFF_RENAMED_DELETED;
nulltoken committed
1039

Edward Thomson committed
1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053
		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
1054

Edward Thomson committed
1055 1056 1057 1058 1059 1060 1061 1062
	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,
1063
	const git_merge_options *opts)
Edward Thomson committed
1064 1065 1066 1067 1068
{
	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
1069

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

Edward Thomson committed
1073 1074
		ours_renamed = 0;
		theirs_renamed = 0;
nulltoken committed
1075

Edward Thomson committed
1076 1077 1078
		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
1079

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

Edward Thomson committed
1082 1083 1084 1085 1086
			merge_diff_coalesce_rename(
				&ours_source->our_entry,
				&ours_source->our_status,
				&target->our_entry,
				&target->our_status);
nulltoken committed
1087

Edward Thomson committed
1088 1089
			similarity_ours[ours_source_idx].similarity = 0;
			similarity_ours[i].similarity = 0;
nulltoken committed
1090

Edward Thomson committed
1091 1092
			ours_renamed = 1;
		}
nulltoken committed
1093

Edward Thomson committed
1094 1095 1096 1097
		/* 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
1098

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

Edward Thomson committed
1101 1102 1103 1104 1105
			merge_diff_coalesce_rename(
				&theirs_source->their_entry,
				&theirs_source->their_status,
				&target->their_entry,
				&target->their_status);
nulltoken committed
1106

Edward Thomson committed
1107 1108
			similarity_theirs[theirs_source_idx].similarity = 0;
			similarity_theirs[i].similarity = 0;
nulltoken committed
1109

Edward Thomson committed
1110 1111
			theirs_renamed = 1;
		}
nulltoken committed
1112

Edward Thomson committed
1113 1114 1115 1116 1117 1118 1119
		merge_diff_mark_rename_conflict(diff_list,
			similarity_ours, ours_renamed, ours_source_idx,
			similarity_theirs, theirs_renamed, theirs_source_idx,
			target, opts);
	}
}

1120
static int merge_diff_empty(const git_vector *conflicts, size_t idx, void *p)
Edward Thomson committed
1121 1122
{
	git_merge_diff *conflict = conflicts->contents[idx];
nulltoken committed
1123

1124 1125
	GIT_UNUSED(p);

Edward Thomson committed
1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140
	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
1141

Edward Thomson committed
1142 1143 1144 1145
	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)))
1146
			(*src_count)++;
Edward Thomson committed
1147
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(entry->ancestor_entry))
1148
			(*tgt_count)++;
Edward Thomson committed
1149 1150 1151 1152 1153 1154
	}
}

int git_merge_diff_list__find_renames(
	git_repository *repo,
	git_merge_diff_list *diff_list,
1155
	const git_merge_options *opts)
Edward Thomson committed
1156 1157 1158 1159 1160 1161
{
	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
1162

Edward Thomson committed
1163
	assert(diff_list && opts);
nulltoken committed
1164

1165
	if ((opts->tree_flags & GIT_MERGE_TREE_FIND_RENAMES) == 0)
Edward Thomson committed
1166
		return 0;
nulltoken committed
1167

Edward Thomson committed
1168 1169 1170
	similarity_ours = git__calloc(diff_list->conflicts.length,
		sizeof(struct merge_diff_similarity));
	GITERR_CHECK_ALLOC(similarity_ours);
nulltoken committed
1171

Edward Thomson committed
1172 1173 1174
	similarity_theirs = git__calloc(diff_list->conflicts.length,
		sizeof(struct merge_diff_similarity));
	GITERR_CHECK_ALLOC(similarity_theirs);
nulltoken committed
1175

Edward Thomson committed
1176 1177 1178 1179 1180 1181 1182 1183
	/* Calculate similarity between items that were deleted from the ancestor
	 * and added in the other branch.
	 */
	if ((error = merge_diff_mark_similarity(repo, diff_list, similarity_ours,
		similarity_theirs, index_entry_similarity_exact, NULL, opts)) < 0)
		goto done;

	if (diff_list->conflicts.length <= opts->target_limit) {
1184
		GITERR_CHECK_ALLOC_MULTIPLY(&cache_size, diff_list->conflicts.length, 3);
Edward Thomson committed
1185 1186 1187 1188
		cache = git__calloc(cache_size, sizeof(void *));
		GITERR_CHECK_ALLOC(cache);

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

Edward Thomson committed
1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203
		if (src_count > opts->target_limit || tgt_count > opts->target_limit) {
			/* TODO: report! */
		} else {
			if ((error = merge_diff_mark_similarity(
				repo, diff_list, similarity_ours, similarity_theirs,
				index_entry_similarity_inexact, cache, opts)) < 0)
				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
1204

Edward Thomson committed
1205
	/* And remove any entries that were merged and are now empty. */
1206
	git_vector_remove_matching(&diff_list->conflicts, merge_diff_empty, NULL);
Edward Thomson committed
1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223

done:
	if (cache != NULL) {
		for (i = 0; i < cache_size; ++i) {
			if (cache[i] != NULL)
				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
1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234
/* 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
1235

Edward Thomson committed
1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246
	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
1247

Edward Thomson committed
1248 1249 1250 1251 1252 1253 1254
	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
1255

Edward Thomson committed
1256 1257 1258
	if (child_len < parent_len ||
		strncmp(parent, child, parent_len) != 0)
		return 0;
nulltoken committed
1259

Edward Thomson committed
1260 1261 1262 1263 1264 1265 1266 1267
	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
1268

Edward Thomson committed
1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279
	/* 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
1280

Edward Thomson committed
1281 1282 1283
		df_data->prev_conflict->type = GIT_MERGE_DIFF_DIRECTORY_FILE;
		df_data->df_path = df_data->prev_path;
	}
nulltoken committed
1284

Edward Thomson committed
1285 1286
	df_data->prev_path = cur_path;
	df_data->prev_conflict = conflict;
nulltoken committed
1287

Edward Thomson committed
1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312
	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
1313

Edward Thomson committed
1314 1315 1316
	return 0;
}

1317
GIT_INLINE(int) merge_diff_detect_binary(
1318
	bool *binary_out,
1319
	git_repository *repo,
1320
	const git_merge_diff *conflict)
1321 1322 1323
{
	git_blob *ancestor_blob = NULL, *our_blob = NULL, *their_blob = NULL;
	int error = 0;
1324
	bool binary = false;
1325

Edward Thomson committed
1326
	if (GIT_MERGE_INDEX_ENTRY_ISFILE(conflict->ancestor_entry)) {
1327
		if ((error = git_blob_lookup(&ancestor_blob, repo, &conflict->ancestor_entry.id)) < 0)
1328 1329
			goto done;

1330
		binary = git_blob_is_binary(ancestor_blob);
1331 1332
	}

1333
	if (!binary &&
Edward Thomson committed
1334
		GIT_MERGE_INDEX_ENTRY_ISFILE(conflict->our_entry)) {
1335
		if ((error = git_blob_lookup(&our_blob, repo, &conflict->our_entry.id)) < 0)
1336 1337
			goto done;

1338
		binary = git_blob_is_binary(our_blob);
1339 1340
	}

1341
	if (!binary &&
Edward Thomson committed
1342
		GIT_MERGE_INDEX_ENTRY_ISFILE(conflict->their_entry)) {
1343
		if ((error = git_blob_lookup(&their_blob, repo, &conflict->their_entry.id)) < 0)
1344 1345
			goto done;

1346
		binary = git_blob_is_binary(their_blob);
1347 1348
	}

1349 1350
	*binary_out = binary;

1351 1352 1353 1354 1355 1356 1357 1358
done:
	git_blob_free(ancestor_blob);
	git_blob_free(our_blob);
	git_blob_free(their_blob);

	return error;
}

1359
GIT_INLINE(int) index_entry_dup_pool(
Edward Thomson committed
1360 1361 1362 1363 1364 1365
	git_index_entry *out,
	git_pool *pool,
	const git_index_entry *src)
{
	if (src != NULL) {
		memcpy(out, src, sizeof(git_index_entry));
nulltoken committed
1366

Edward Thomson committed
1367 1368 1369
		if ((out->path = git_pool_strdup(pool, src->path)) == NULL)
			return -1;
	}
nulltoken committed
1370

Edward Thomson committed
1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387
	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;
1388
	else if (git_oid__cmp(&ancestor->id, &other->id) ||
Edward Thomson committed
1389 1390
			 ancestor->mode != other->mode)
		return GIT_DELTA_MODIFIED;
nulltoken committed
1391

Edward Thomson committed
1392 1393 1394 1395 1396 1397 1398 1399 1400
	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
1401

Edward Thomson committed
1402 1403
	if ((conflict = git_pool_malloc(pool, sizeof(git_merge_diff))) == NULL)
		return NULL;
nulltoken committed
1404

1405 1406 1407
	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
1408
		return NULL;
nulltoken committed
1409

Edward Thomson committed
1410 1411 1412 1413
	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
1414

Edward Thomson committed
1415 1416 1417 1418 1419
	return conflict;
}

/* Merge trees */

1420
static int merge_diff_list_insert_conflict(
Edward Thomson committed
1421 1422 1423 1424 1425
	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
1426

Edward Thomson committed
1427 1428 1429 1430 1431
	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
1432

Edward Thomson committed
1433 1434 1435
	return 0;
}

1436
static int merge_diff_list_insert_unmodified(
Edward Thomson committed
1437 1438 1439 1440 1441
	git_merge_diff_list *diff_list,
	const git_index_entry *tree_items[3])
{
	int error = 0;
	git_index_entry *entry;
nulltoken committed
1442

Edward Thomson committed
1443 1444
	entry = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry));
	GITERR_CHECK_ALLOC(entry);
nulltoken committed
1445

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

Edward Thomson committed
1449 1450 1451
	return error;
}

1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479
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
1480 1481
int git_merge_diff_list__find_differences(
	git_merge_diff_list *diff_list,
1482 1483 1484
	git_iterator *ancestor_iter,
	git_iterator *our_iter,
	git_iterator *their_iter)
Edward Thomson committed
1485
{
1486
	git_iterator *iterators[3] = { ancestor_iter, our_iter, their_iter };
1487
	struct merge_diff_find_data find_data = { diff_list };
nulltoken committed
1488

1489
	return git_iterator_walk(iterators, 3, queue_difference, &find_data);
Edward Thomson committed
1490 1491 1492 1493 1494
}

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
1495

Edward Thomson committed
1496 1497
	if (diff_list == NULL)
		return NULL;
nulltoken committed
1498

Edward Thomson committed
1499
	diff_list->repo = repo;
nulltoken committed
1500

Edward Thomson committed
1501 1502 1503
	if (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 ||
Jacques Germishuys committed
1504 1505
		git_pool_init(&diff_list->pool, 1, 0) < 0) {
		git_merge_diff_list__free(diff_list);
Edward Thomson committed
1506
		return NULL;
Jacques Germishuys committed
1507
	}
nulltoken committed
1508

Edward Thomson committed
1509 1510 1511
	return diff_list;
}

Edward Thomson committed
1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523
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);
}

1524
static int merge_normalize_opts(
Edward Thomson committed
1525
	git_repository *repo,
1526 1527
	git_merge_options *opts,
	const git_merge_options *given)
Edward Thomson committed
1528 1529 1530
{
	git_config *cfg = NULL;
	int error = 0;
nulltoken committed
1531

Edward Thomson committed
1532
	assert(repo && opts);
nulltoken committed
1533

Edward Thomson committed
1534 1535
	if ((error = git_repository_config__weakptr(&cfg, repo)) < 0)
		return error;
nulltoken committed
1536

Edward Thomson committed
1537
	if (given != NULL)
1538
		memcpy(opts, given, sizeof(git_merge_options));
Edward Thomson committed
1539
	else {
1540
		git_merge_options init = GIT_MERGE_OPTIONS_INIT;
Edward Thomson committed
1541
		memcpy(opts, &init, sizeof(init));
nulltoken committed
1542

1543
		opts->tree_flags = GIT_MERGE_TREE_FIND_RENAMES;
Edward Thomson committed
1544 1545
		opts->rename_threshold = GIT_MERGE_TREE_RENAME_THRESHOLD;
	}
nulltoken committed
1546

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

1550 1551
		if (!limit)
			limit = git_config__get_int_force(cfg, "diff.renamelimit", 0);
nulltoken committed
1552

1553 1554
		opts->target_limit = (limit <= 0) ?
			GIT_MERGE_TREE_TARGET_LIMIT : (unsigned int)limit;
Edward Thomson committed
1555
	}
nulltoken committed
1556

Edward Thomson committed
1557 1558 1559 1560
	/* assign the internal metric with whitespace flag as payload */
	if (!opts->metric) {
		opts->metric = git__malloc(sizeof(git_diff_similarity_metric));
		GITERR_CHECK_ALLOC(opts->metric);
nulltoken committed
1561

Edward Thomson committed
1562 1563 1564 1565
		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;
1566
		opts->metric->payload = (void *)GIT_HASHSIG_SMART_WHITESPACE;
Edward Thomson committed
1567
	}
nulltoken committed
1568

Edward Thomson committed
1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581
	return 0;
}


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
1582

Edward Thomson committed
1583 1584
	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(*entry))
		return 0;
nulltoken committed
1585

Edward Thomson committed
1586 1587 1588 1589 1590 1591
	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
1592

Edward Thomson committed
1593
	mode[idx] = entry->mode;
1594
	oid[idx] = &entry->id;
nulltoken committed
1595

Edward Thomson committed
1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606
	return git_index_reuc_add(index, entry->path,
		mode[0], oid[0], mode[1], oid[1], mode[2], oid[2]);
}

int index_from_diff_list(git_index **out, git_merge_diff_list *diff_list)
{
	git_index *index;
	size_t i;
	git_index_entry *entry;
	git_merge_diff *conflict;
	int error = 0;
nulltoken committed
1607

Edward Thomson committed
1608
	*out = NULL;
nulltoken committed
1609

Edward Thomson committed
1610 1611
	if ((error = git_index_new(&index)) < 0)
		return error;
nulltoken committed
1612

Edward Thomson committed
1613 1614 1615 1616
	git_vector_foreach(&diff_list->staged, i, entry) {
		if ((error = git_index_add(index, entry)) < 0)
			goto on_error;
	}
nulltoken committed
1617

Edward Thomson committed
1618 1619 1620 1621
	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
1622

Edward Thomson committed
1623 1624 1625
		const git_index_entry *ours =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
			&conflict->our_entry : NULL;
nulltoken committed
1626

Edward Thomson committed
1627 1628 1629
		const git_index_entry *theirs =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
			&conflict->their_entry : NULL;
nulltoken committed
1630

Edward Thomson committed
1631 1632 1633
		if ((error = git_index_conflict_add(index, ancestor, ours, theirs)) < 0)
			goto on_error;
	}
nulltoken committed
1634

Edward Thomson committed
1635 1636 1637
	/* 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
1638

Edward Thomson committed
1639 1640
		if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry))
			continue;
nulltoken committed
1641

Edward Thomson committed
1642
		ancestor_path = conflict->ancestor_entry.path;
nulltoken committed
1643

Edward Thomson committed
1644 1645 1646
		our_path =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
			conflict->our_entry.path : NULL;
nulltoken committed
1647

Edward Thomson committed
1648 1649 1650
		their_path =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
			conflict->their_entry.path : NULL;
nulltoken committed
1651

Edward Thomson committed
1652 1653 1654 1655 1656
		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
1657
	}
nulltoken committed
1658

Edward Thomson committed
1659 1660 1661 1662 1663 1664 1665 1666 1667 1668
	/* 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;
nulltoken committed
1669

Edward Thomson committed
1670 1671 1672 1673 1674 1675 1676
		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)
			goto on_error;
nulltoken committed
1677

Edward Thomson committed
1678 1679 1680
		if (ours != NULL &&
			(error = merge_index_insert_reuc(index, TREE_IDX_OURS, ours)) < 0)
			goto on_error;
nulltoken committed
1681

Edward Thomson committed
1682 1683 1684 1685
		if (theirs != NULL &&
			(error = merge_index_insert_reuc(index, TREE_IDX_THEIRS, theirs)) < 0)
			goto on_error;
	}
nulltoken committed
1686

Edward Thomson committed
1687 1688
	*out = index;
	return 0;
nulltoken committed
1689

Edward Thomson committed
1690 1691
on_error:
	git_index_free(index);
nulltoken committed
1692

Edward Thomson committed
1693 1694 1695
	return error;
}

1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707
static git_iterator *iterator_given_or_empty(git_iterator **empty, git_iterator *given)
{
	if (given)
		return given;

	if (git_iterator_for_nothing(empty, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL) < 0)
		return NULL;

	return *empty;
}

int git_merge__iterators(
Edward Thomson committed
1708 1709
	git_index **out,
	git_repository *repo,
1710 1711 1712
	git_iterator *ancestor_iter,
	git_iterator *our_iter,
	git_iterator *theirs_iter,
1713
	const git_merge_options *given_opts)
Edward Thomson committed
1714
{
1715 1716 1717
	git_iterator *empty_ancestor = NULL,
		*empty_ours = NULL,
		*empty_theirs = NULL;
Edward Thomson committed
1718
	git_merge_diff_list *diff_list;
1719
	git_merge_options opts;
Edward Thomson committed
1720 1721 1722 1723 1724
	git_merge_diff *conflict;
	git_vector changes;
	size_t i;
	int error = 0;

1725
	assert(out && repo);
Edward Thomson committed
1726 1727

	*out = NULL;
nulltoken committed
1728

1729 1730
	GITERR_CHECK_VERSION(
		given_opts, GIT_MERGE_OPTIONS_VERSION, "git_merge_options");
1731

1732
	if ((error = merge_normalize_opts(repo, &opts, given_opts)) < 0)
Edward Thomson committed
1733 1734 1735 1736
		return error;

	diff_list = git_merge_diff_list__alloc(repo);
	GITERR_CHECK_ALLOC(diff_list);
nulltoken committed
1737

1738 1739 1740 1741 1742 1743
	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
1744
		(error = git_merge_diff_list__find_renames(repo, diff_list, &opts)) < 0)
Edward Thomson committed
1745
		goto done;
nulltoken committed
1746

Edward Thomson committed
1747 1748
	memcpy(&changes, &diff_list->conflicts, sizeof(git_vector));
	git_vector_clear(&diff_list->conflicts);
nulltoken committed
1749

Edward Thomson committed
1750 1751
	git_vector_foreach(&changes, i, conflict) {
		int resolved = 0;
nulltoken committed
1752

1753
		if ((error = merge_conflict_resolve(&resolved, diff_list, conflict, opts.file_favor, opts.file_flags)) < 0)
Edward Thomson committed
1754
			goto done;
nulltoken committed
1755

Edward Thomson committed
1756 1757 1758
		if (!resolved)
			git_vector_insert(&diff_list->conflicts, conflict);
	}
nulltoken committed
1759

Edward Thomson committed
1760 1761
	if (!given_opts || !given_opts->metric)
		git__free(opts.metric);
nulltoken committed
1762

Edward Thomson committed
1763 1764 1765 1766
	error = index_from_diff_list(out, diff_list);

done:
	git_merge_diff_list__free(diff_list);
1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799
	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;
	int error;

	if ((error = git_iterator_for_tree(&ancestor_iter, (git_tree *)ancestor_tree,
			GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
		(error = git_iterator_for_tree(&our_iter, (git_tree *)our_tree,
			GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
		(error = git_iterator_for_tree(&their_iter, (git_tree *)their_tree,
			GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0)
		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
1800 1801 1802 1803

	return error;
}

1804

1805 1806 1807 1808 1809
int git_merge_commits(
	git_index **out,
	git_repository *repo,
	const git_commit *our_commit,
	const git_commit *their_commit,
1810
	const git_merge_options *opts)
1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838
{
	git_oid ancestor_oid;
	git_commit *ancestor_commit = NULL;
	git_tree *our_tree = NULL, *their_tree = NULL, *ancestor_tree = NULL;
	int error = 0;

	if ((error = git_merge_base(&ancestor_oid, repo, git_commit_id(our_commit), git_commit_id(their_commit))) < 0 &&
		error == GIT_ENOTFOUND)
		giterr_clear();
	else if (error < 0 ||
		(error = git_commit_lookup(&ancestor_commit, repo, &ancestor_oid)) < 0 ||
		(error = git_commit_tree(&ancestor_tree, ancestor_commit)) < 0)
		goto done;

	if ((error = git_commit_tree(&our_tree, our_commit)) < 0 ||
		(error = git_commit_tree(&their_tree, their_commit)) < 0 ||
		(error = git_merge_trees(out, repo, ancestor_tree, our_tree, their_tree, opts)) < 0)
		goto done;

done:
	git_commit_free(ancestor_commit);
	git_tree_free(our_tree);
	git_tree_free(their_tree);
	git_tree_free(ancestor_tree);

	return error;
}

Edward Thomson committed
1839 1840 1841 1842
/* Merge setup / cleanup */

static int write_merge_head(
	git_repository *repo,
1843
	const git_annotated_commit *heads[],
Edward Thomson committed
1844 1845 1846 1847 1848 1849 1850 1851 1852 1853
	size_t heads_len)
{
	git_filebuf file = GIT_FILEBUF_INIT;
	git_buf file_path = GIT_BUF_INIT;
	size_t i;
	int error = 0;

	assert(repo && heads);

	if ((error = git_buf_joinpath(&file_path, repo->path_repository, GIT_MERGE_HEAD_FILE)) < 0 ||
1854
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_FORCE, GIT_MERGE_FILE_MODE)) < 0)
Edward Thomson committed
1855 1856 1857
		goto cleanup;

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

1862
	error = git_filebuf_commit(&file);
Edward Thomson committed
1863 1864 1865 1866 1867 1868 1869 1870 1871 1872

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

	git_buf_free(&file_path);

	return error;
}

1873
static int write_merge_mode(git_repository *repo)
Edward Thomson committed
1874 1875 1876 1877 1878 1879 1880 1881
{
	git_filebuf file = GIT_FILEBUF_INIT;
	git_buf file_path = GIT_BUF_INIT;
	int error = 0;

	assert(repo);

	if ((error = git_buf_joinpath(&file_path, repo->path_repository, GIT_MERGE_MODE_FILE)) < 0 ||
1882
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_FORCE, GIT_MERGE_FILE_MODE)) < 0)
Edward Thomson committed
1883 1884
		goto cleanup;

1885 1886
	if ((error = git_filebuf_write(&file, "no-ff", 5)) < 0)
		goto cleanup;
1887

1888
	error = git_filebuf_commit(&file);
Edward Thomson committed
1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899

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

	git_buf_free(&file_path);

	return error;
}

struct merge_msg_entry {
1900
	const git_annotated_commit *merge_head;
Edward Thomson committed
1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 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 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087
	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,
2088
	const git_annotated_commit *heads[],
Edward Thomson committed
2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103
	size_t heads_len)
{
	git_filebuf file = GIT_FILEBUF_INIT;
	git_buf file_path = GIT_BUF_INIT;
	struct merge_msg_entry *entries;
	git_vector matching = GIT_VECTOR_INIT;
	size_t i;
	char sep = 0;
	int error = 0;

	assert(repo && heads);

	entries = git__calloc(heads_len, sizeof(struct merge_msg_entry));
	GITERR_CHECK_ALLOC(entries); 

2104 2105
	if (git_vector_init(&matching, heads_len, NULL) < 0) {
		git__free(entries);
Edward Thomson committed
2106
		return -1;
2107
	}
Edward Thomson committed
2108 2109 2110 2111 2112

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

	if ((error = git_buf_joinpath(&file_path, repo->path_repository, GIT_MERGE_MSG_FILE)) < 0 ||
2113
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_FORCE, GIT_MERGE_FILE_MODE)) < 0 ||
Edward Thomson committed
2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131
		(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;

2132 2133
		if ((error = git_filebuf_printf(&file,
			"%scommit '%s'", (i > 0) ? "; " : "",
2134
			entries[i].merge_head->id_str)) < 0)
Edward Thomson committed
2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180
			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 =',';
	
	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;

2181
		if ((error = git_filebuf_printf(&file, "; commit '%s'",
2182
			entries[i].merge_head->id_str)) < 0)
Edward Thomson committed
2183 2184 2185 2186
			goto cleanup;
	}

	if ((error = git_filebuf_printf(&file, "\n")) < 0 ||
2187
		(error = git_filebuf_commit(&file)) < 0)
Edward Thomson committed
2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201
		goto cleanup;

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

	git_buf_free(&file_path);

	git_vector_free(&matching);
	git__free(entries);

	return error;
}

2202 2203
int git_merge__setup(
	git_repository *repo,
2204 2205
	const git_annotated_commit *our_head,
	const git_annotated_commit *heads[],
2206 2207 2208 2209 2210 2211
	size_t heads_len)
{
	int error = 0;

	assert (repo && our_head && heads);

2212
	if ((error = git_repository__set_orig_head(repo, git_annotated_commit_id(our_head))) == 0 &&
2213 2214 2215 2216 2217 2218 2219 2220
		(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;
}

2221 2222 2223
/* Merge branches */

static int merge_ancestor_head(
2224
	git_annotated_commit **ancestor_head,
2225
	git_repository *repo,
2226 2227
	const git_annotated_commit *our_head,
	const git_annotated_commit **their_heads,
2228 2229 2230
	size_t their_heads_len)
{
	git_oid *oids, ancestor_oid;
2231
	size_t i, alloc_len;
2232 2233 2234 2235
	int error = 0;

	assert(repo && our_head && their_heads);

2236 2237
	GITERR_CHECK_ALLOC_ADD(&alloc_len, their_heads_len, 1);
	oids = git__calloc(alloc_len, sizeof(git_oid));
2238 2239 2240 2241 2242
	GITERR_CHECK_ALLOC(oids);

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

	for (i = 0; i < their_heads_len; i++)
2243
		git_oid_cpy(&oids[i + 1], git_annotated_commit_id(their_heads[i]));
2244 2245 2246 2247

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

2248
	error = git_annotated_commit_lookup(ancestor_head, repo, &ancestor_oid);
2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267

on_error:
	git__free(oids);
	return error;
}

const char *merge_their_label(const char *branchname)
{
	const char *slash;

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

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

	return slash+1;
}

2268
static int merge_normalize_checkout_opts(
2269
	git_repository *repo,
2270 2271
	git_checkout_options *checkout_opts,
	const git_checkout_options *given_checkout_opts,
2272 2273
	const git_annotated_commit *ancestor_head,
	const git_annotated_commit *our_head,
2274
	size_t their_heads_len,
2275
	const git_annotated_commit **their_heads)
2276 2277 2278 2279 2280
{
	int error = 0;

	GIT_UNUSED(repo);

2281 2282
	if (given_checkout_opts != NULL)
		memcpy(checkout_opts, given_checkout_opts, sizeof(git_checkout_options));
2283
	else {
2284
		git_checkout_options default_checkout_opts = GIT_CHECKOUT_OPTIONS_INIT;
2285
		default_checkout_opts.checkout_strategy =  GIT_CHECKOUT_SAFE;
2286

2287
		memcpy(checkout_opts, &default_checkout_opts, sizeof(git_checkout_options));
2288 2289
	}

2290
	/* TODO: for multiple ancestors in merge-recursive, this is "merged common ancestors" */
2291
	if (!checkout_opts->ancestor_label) {
2292
		if (ancestor_head && ancestor_head->commit)
2293
			checkout_opts->ancestor_label = git_commit_summary(ancestor_head->commit);
2294
		else
2295
			checkout_opts->ancestor_label = "ancestor";
2296 2297
	}

2298
	if (!checkout_opts->our_label) {
2299
		if (our_head && our_head->ref_name)
2300
			checkout_opts->our_label = our_head->ref_name;
2301
		else
2302
			checkout_opts->our_label = "ours";
2303
	}
2304

2305
	if (!checkout_opts->their_label) {
2306
		if (their_heads_len == 1 && their_heads[0]->ref_name)
2307
			checkout_opts->their_label = merge_their_label(their_heads[0]->ref_name);
2308
		else if (their_heads_len == 1)
2309
			checkout_opts->their_label = their_heads[0]->id_str;
2310
		else
2311
			checkout_opts->their_label = "theirs";
2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378
	}

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

	opts.pathspec.count = staged_paths.length;
	opts.pathspec.strings = (char **)staged_paths.contents;

	if ((error = git_iterator_for_index(&iter_repo, index_repo, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
		(error = git_iterator_for_index(&iter_new, index_new, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
		(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
2379 2380
	GIT_UNUSED(index_new);

2381 2382
	*conflicts = 0;

2383 2384 2385 2386 2387 2388 2389 2390 2391 2392
	/* We need to have merged at least 1 file for the possibility to exist to
	 * have conflicts with the workdir. Passing 0 as the pathspec count paramter
	 * 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
	 * the merge. This typically happens when cherry-picking a commmit whose
	 * changes have already been applied.
	 */
	if (merged_paths->length == 0)
		return 0;

2393 2394 2395 2396 2397 2398 2399 2400 2401
	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.
	 */
	opts.pathspec.count = merged_paths->length;
	opts.pathspec.strings = (char **)merged_paths->contents;

2402
	if ((error = git_diff_index_to_workdir(&wd_diff_list, repo, NULL, &opts)) < 0)
2403 2404 2405 2406 2407 2408 2409 2410 2411 2412
		goto done;

	*conflicts = wd_diff_list->deltas.length;

done:
	git_diff_free(wd_diff_list);

	return error;
}

2413
int git_merge__check_result(git_repository *repo, git_index *index_new)
2414
{
2415 2416 2417 2418 2419
	git_tree *head_tree = NULL;
	git_iterator *iter_head = NULL, *iter_new = NULL;
	git_diff *merged_list = NULL;
	git_diff_options opts = GIT_DIFF_OPTIONS_INIT;
	git_diff_delta *delta;
2420
	git_vector paths = GIT_VECTOR_INIT;
2421
	size_t i, index_conflicts = 0, wd_conflicts = 0, conflicts;
2422 2423 2424
	const git_index_entry *e;
	int error = 0;

2425 2426 2427 2428
	if ((error = git_repository_head_tree(&head_tree, repo)) < 0 ||
		(error = git_iterator_for_tree(&iter_head, head_tree, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
		(error = git_iterator_for_index(&iter_new, index_new, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
		(error = git_diff__from_iterators(&merged_list, repo, iter_head, iter_new, &opts)) < 0)
2429 2430
		goto done;

2431 2432 2433
	git_vector_foreach(&merged_list->deltas, i, delta) {
		if ((error = git_vector_insert(&paths, (char *)delta->new_file.path)) < 0)
			goto done;
2434 2435 2436 2437 2438
	}

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

2439
		if (git_index_entry_is_conflict(e) &&
2440 2441
			(git_vector_last(&paths) == NULL ||
			strcmp(git_vector_last(&paths), e->path) != 0)) {
2442

2443 2444 2445
			if ((error = git_vector_insert(&paths, (char *)e->path)) < 0)
				goto done;
		}
2446 2447
	}

2448 2449 2450 2451
	/* 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;
2452

2453
	if ((conflicts = index_conflicts + wd_conflicts) > 0) {
2454
		giterr_set(GITERR_MERGE, "%" PRIuZ " uncommitted change%s would be overwritten by merge",
2455
			conflicts, (conflicts != 1) ? "s" : "");
2456
		error = GIT_ECONFLICT;
2457 2458 2459
	}

done:
2460 2461 2462 2463 2464
	git_vector_free(&paths);
	git_tree_free(head_tree);
	git_iterator_free(iter_head);
	git_iterator_free(iter_new);
	git_diff_free(merged_list);
2465 2466 2467 2468

	return error;
}

2469 2470 2471 2472 2473 2474 2475 2476 2477 2478
int git_merge__append_conflicts_to_merge_msg(
	git_repository *repo,
	git_index *index)
{
	git_filebuf file = GIT_FILEBUF_INIT;
	git_buf file_path = GIT_BUF_INIT;
	const char *last = NULL;
	size_t i;
	int error;

2479 2480 2481
	if (!git_index_has_conflicts(index))
		return 0;

2482 2483 2484 2485
	if ((error = git_buf_joinpath(&file_path, repo->path_repository, GIT_MERGE_MSG_FILE)) < 0 ||
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_APPEND, GIT_MERGE_FILE_MODE)) < 0)
		goto cleanup;

2486
	git_filebuf_printf(&file, "\nConflicts:\n");
2487 2488 2489 2490

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

2491
		if (!git_index_entry_is_conflict(e))
2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510
			continue;

		if (last == NULL || strcmp(e->path, last) != 0)
			git_filebuf_printf(&file, "\t%s\n", e->path);

		last = e->path;
	}

	error = git_filebuf_commit(&file);

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

	git_buf_free(&file_path);

	return error;
}

2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521
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));
}

2522
static int merge_heads(
2523 2524
	git_annotated_commit **ancestor_head_out,
	git_annotated_commit **our_head_out,
2525
	git_repository *repo,
2526
	const git_annotated_commit **their_heads,
2527
	size_t their_heads_len)
2528
{
2529
	git_annotated_commit *ancestor_head = NULL, *our_head = NULL;
2530
	git_reference *our_ref = NULL;
2531 2532 2533 2534 2535 2536 2537 2538 2539
	int error = 0;

	*ancestor_head_out = NULL;
	*our_head_out = NULL;

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

	if ((error = git_reference_lookup(&our_ref, repo, GIT_HEAD_FILE)) < 0 ||
2540
		(error = git_annotated_commit_from_ref(&our_head, repo, our_ref)) < 0)
2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555
		goto done;

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

		giterr_clear();
		error = 0;
	}

	*ancestor_head_out = ancestor_head;
	*our_head_out = our_head;

done:
	if (error < 0) {
2556 2557
		git_annotated_commit_free(ancestor_head);
		git_annotated_commit_free(our_head);
2558 2559 2560 2561 2562 2563 2564
	}

	git_reference_free(our_ref);

	return error;
}

2565
static int merge_preference(git_merge_preference_t *out, git_repository *repo)
2566 2567 2568 2569 2570
{
	git_config *config;
	const char *value;
	int bool_value, error = 0;

2571
	*out = GIT_MERGE_PREFERENCE_NONE;
2572

Edward Thomson committed
2573
	if ((error = git_repository_config_snapshot(&config, repo)) < 0)
2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586
		goto done;

	if ((error = git_config_get_string(&value, config, "merge.ff")) < 0) {
		if (error == GIT_ENOTFOUND) {
			giterr_clear();
			error = 0;
		}

		goto done;
	}

	if (git_config_parse_bool(&bool_value, value) == 0) {
		if (!bool_value)
2587
			*out |= GIT_MERGE_PREFERENCE_NO_FASTFORWARD;
2588 2589
	} else {
		if (strcasecmp(value, "only") == 0)
2590
			*out |= GIT_MERGE_PREFERENCE_FASTFORWARD_ONLY;
2591 2592 2593 2594 2595 2596 2597
	}

done:
	git_config_free(config);
	return error;
}

2598
int git_merge_analysis(
2599
	git_merge_analysis_t *analysis_out,
2600
	git_merge_preference_t *preference_out,
2601
	git_repository *repo,
2602
	const git_annotated_commit **their_heads,
2603 2604
	size_t their_heads_len)
{
2605
	git_annotated_commit *ancestor_head = NULL, *our_head = NULL;
2606 2607
	int error = 0;

2608
	assert(analysis_out && preference_out && repo && their_heads);
2609

2610 2611 2612 2613 2614 2615
	if (their_heads_len != 1) {
		giterr_set(GITERR_MERGE, "Can only merge a single branch");
		error = -1;
		goto done;
	}

2616
	*analysis_out = GIT_MERGE_ANALYSIS_NONE;
2617

2618
	if ((error = merge_preference(preference_out, repo)) < 0)
2619
		goto done;
2620

2621
	if (git_repository_head_unborn(repo)) {
2622
		*analysis_out |= GIT_MERGE_ANALYSIS_FASTFORWARD | GIT_MERGE_ANALYSIS_UNBORN;
2623
		goto done;
2624 2625
	}

2626 2627
	if ((error = merge_heads(&ancestor_head, &our_head, repo, their_heads, their_heads_len)) < 0)
		goto done;
2628

2629
	/* We're up-to-date if we're trying to merge our own common ancestor. */
2630 2631
	if (ancestor_head && git_oid_equal(
		git_annotated_commit_id(ancestor_head), git_annotated_commit_id(their_heads[0])))
2632
		*analysis_out |= GIT_MERGE_ANALYSIS_UP_TO_DATE;
2633

2634
	/* We're fastforwardable if we're our own common ancestor. */
2635 2636
	else if (ancestor_head && git_oid_equal(
		git_annotated_commit_id(ancestor_head), git_annotated_commit_id(our_head)))
2637
		*analysis_out |= GIT_MERGE_ANALYSIS_FASTFORWARD | GIT_MERGE_ANALYSIS_NORMAL;
2638

2639 2640
	/* Otherwise, just a normal merge is possible. */
	else
2641
		*analysis_out |= GIT_MERGE_ANALYSIS_NORMAL;
2642

2643
done:
2644 2645
	git_annotated_commit_free(ancestor_head);
	git_annotated_commit_free(our_head);
2646 2647
	return error;
}
2648 2649 2650

int git_merge(
	git_repository *repo,
2651
	const git_annotated_commit **their_heads,
2652
	size_t their_heads_len,
2653
	const git_merge_options *merge_opts,
2654
	const git_checkout_options *given_checkout_opts)
2655 2656
{
	git_reference *our_ref = NULL;
2657
	git_checkout_options checkout_opts;
2658
	git_annotated_commit *ancestor_head = NULL, *our_head = NULL;
2659
	git_tree *ancestor_tree = NULL, *our_tree = NULL, **their_trees = NULL;
2660
	git_index *index = NULL;
2661
	git_indexwriter indexwriter = GIT_INDEXWRITER_INIT;
2662 2663
	size_t i;
	int error = 0;
2664

2665
	assert(repo && their_heads);
2666 2667 2668 2669 2670 2671 2672 2673 2674

	if (their_heads_len != 1) {
		giterr_set(GITERR_MERGE, "Can only merge a single branch");
		return -1;
	}

	their_trees = git__calloc(their_heads_len, sizeof(git_tree *));
	GITERR_CHECK_ALLOC(their_trees);

2675 2676 2677 2678
	if ((error = merge_heads(&ancestor_head, &our_head, repo, their_heads, their_heads_len)) < 0 ||
		(error = merge_normalize_checkout_opts(repo, &checkout_opts, given_checkout_opts,
			ancestor_head, our_head, their_heads_len, their_heads)) < 0 ||
		(error = git_indexwriter_init_for_operation(&indexwriter, repo, &checkout_opts.checkout_strategy)) < 0)
2679 2680 2681
		goto on_error;

	/* Write the merge files to the repository. */
2682
	if ((error = git_merge__setup(repo, our_head, their_heads, their_heads_len)) < 0)
2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698
		goto on_error;

	if (ancestor_head != NULL &&
		(error = git_commit_tree(&ancestor_tree, ancestor_head->commit)) < 0)
			goto on_error;

	if ((error = git_commit_tree(&our_tree, our_head->commit)) < 0)
		goto on_error;

	for (i = 0; i < their_heads_len; i++) {
		if ((error = git_commit_tree(&their_trees[i], their_heads[i]->commit)) < 0)
			goto on_error;
	}

	/* TODO: recursive, octopus, etc... */

2699 2700 2701 2702 2703
	if ((error = git_merge_trees(&index, repo, ancestor_tree, our_tree, their_trees[0], merge_opts)) < 0 ||
		(error = git_merge__check_result(repo, index)) < 0 ||
		(error = git_merge__append_conflicts_to_merge_msg(repo, index)) < 0 ||
		(error = git_checkout_index(repo, index, &checkout_opts)) < 0 ||
		(error = git_indexwriter_commit(&indexwriter)) < 0)
2704 2705 2706 2707 2708
		goto on_error;

	goto done;

on_error:
2709
	merge_state_cleanup(repo);
2710 2711

done:
2712 2713 2714
	git_indexwriter_cleanup(&indexwriter);

	git_index_free(index);
2715 2716 2717 2718 2719 2720 2721 2722 2723

	git_tree_free(ancestor_tree);
	git_tree_free(our_tree);

	for (i = 0; i < their_heads_len; i++)
		git_tree_free(their_trees[i]);

	git__free(their_trees);

2724 2725
	git_annotated_commit_free(our_head);
	git_annotated_commit_free(ancestor_head);
2726 2727 2728 2729 2730 2731

	git_reference_free(our_ref);

	return error;
}

2732
int git_merge_init_options(git_merge_options *opts, unsigned int version)
2733
{
2734 2735 2736
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		opts, version, git_merge_options, GIT_MERGE_OPTIONS_INIT);
	return 0;
2737
}
2738

2739
int git_merge_file_init_input(git_merge_file_input *input, unsigned int version)
2740
{
2741 2742 2743
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		input, version, git_merge_file_input, GIT_MERGE_FILE_INPUT_INIT);
	return 0;
2744 2745
}

2746 2747
int git_merge_file_init_options(
	git_merge_file_options *opts, unsigned int version)
2748
{
2749 2750 2751
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		opts, version, git_merge_file_options, GIT_MERGE_FILE_OPTIONS_INIT);
	return 0;
2752
}