merge.c 72 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;
};

Edward Thomson committed
64

Edward Thomson committed
65 66
/* Merge base computation */

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

	if (length < 2) {
		giterr_set(GITERR_INVALID, "At least two commits are required to find an ancestor. Provided 'length' was %u.", length);
		return -1;
	}

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

	if (git_revwalk_new(&walk, repo) < 0)
85
		goto on_error;
86 87

	for (i = 1; i < length; i++) {
88
		commit = git_revwalk__commit_lookup(walk, &input_array[i]);
89
		if (commit == NULL)
90
			goto on_error;
91 92 93 94

		git_vector_insert(&list, commit);
	}

95
	commit = git_revwalk__commit_lookup(walk, &input_array[0]);
96
	if (commit == NULL)
97
		goto on_error;
98 99

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

	if (!result) {
103
		giterr_set(GITERR_MERGE, "No merge base found");
104
		error = GIT_ENOTFOUND;
105
		goto on_error;
106 107
	}

108 109
	*out = result;
	*walk_out = walk;
110

111 112
	git_vector_free(&list);
	return 0;
113

114
on_error:
115
	git_vector_free(&list);
116
	git_revwalk_free(walk);
117 118 119
	return error;
}

120
int git_merge_base_many(git_oid *out, git_repository *repo, size_t length, const git_oid input_array[])
121 122
{
	git_revwalk *walk;
123 124
	git_commit_list *result = NULL;
	int error = 0;
125 126 127

	assert(out && repo && input_array);

128 129
	if ((error = merge_bases_many(&result, &walk, repo, length, input_array)) < 0)
		return error;
130

131
	git_oid_cpy(out, &result->item->oid);
132

133 134
	git_commit_list_free(&result);
	git_revwalk_free(walk);
135

136 137
	return 0;
}
138

139 140 141 142 143 144
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;
145

146
	assert(out && repo && input_array);
147

148 149
	if ((error = merge_bases_many(&result, &walk, repo, length, input_array)) < 0)
		return error;
150 151 152

	git_array_init(array);

153 154
	list = result;
	while (list) {
155
		git_oid *id = git_array_alloc(array);
156 157
		if (id == NULL) {
			error = -1;
158
			goto cleanup;
159
		}
160

161 162
		git_oid_cpy(id, &list->item->oid);
		list = list->next;
163 164 165 166 167 168 169
	}

	git_oidarray__from_array(out, &array);

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

171 172 173
	return error;
}

174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198
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) {
		giterr_set(GITERR_INVALID, "At least two commits are required to find an ancestor. Provided 'length' was %u.", length);
		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;
}

199
static int merge_bases(git_commit_list **out, git_revwalk **walk_out, git_repository *repo, const git_oid *one, const git_oid *two)
200 201 202 203 204 205 206 207 208 209
{
	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;

210
	commit = git_revwalk__commit_lookup(walk, two);
211 212 213 214 215 216 217 218 219
	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;

220
	commit = git_revwalk__commit_lookup(walk, one);
221 222 223 224 225 226 227 228
	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);
229
		giterr_set(GITERR_MERGE, "No merge base found");
230 231 232
		return GIT_ENOTFOUND;
	}

233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
	*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;

253 254 255 256 257
	git_oid_cpy(out, &result->item->oid);
	git_commit_list_free(&result);
	git_revwalk_free(walk);

	return 0;
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286
}

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;
287 288

on_error:
289
	git_commit_list_free(&result);
290 291 292 293 294 295
	git_revwalk_free(walk);
	return -1;
}

static int interesting(git_pqueue *list)
{
296 297 298 299
	size_t i;

	for (i = 0; i < git_pqueue_size(list); i++) {
		git_commit_list_node *commit = git_pqueue_get(list, i);
300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
		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;

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

321 322 323 324 325 326
	/* 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;
	}

327
	if (git_pqueue_init(&list, 0, twos->length * 2, git_commit_list_time_cmp) < 0)
328 329 330
		return -1;

	if (git_commit_list_parse(walk, one) < 0)
Edward Thomson committed
331
		return -1;
332 333 334 335 336 337

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

	git_vector_foreach(twos, i, two) {
338 339 340
		if (git_commit_list_parse(walk, two) < 0)
			return -1;

341
		two->flags |= PARENT2;
342

343 344 345 346 347 348
		if (git_pqueue_insert(&list, two) < 0)
			return -1;
	}

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

352 353
		if (commit == NULL)
			break;
354 355 356 357 358 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

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

400 401
int git_repository_mergehead_foreach(
	git_repository *repo,
402 403 404 405 406 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
	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;

433
		if ((error = cb(&oid, payload)) != 0) {
434
			giterr_set_after_callback(error);
435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452
			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
453 454 455 456 457 458 459 460 461

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 &&
462
		(value = git_oid__cmp(&a->id, &b->id)) == 0)
Edward Thomson committed
463 464 465 466 467 468 469 470 471 472 473 474
		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)
{
475
	int ours_empty, theirs_empty;
Edward Thomson committed
476 477 478 479 480 481 482 483 484 485 486
	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
487

Edward Thomson committed
488 489 490 491 492 493
	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
494

Edward Thomson committed
495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 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
	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
550

Edward Thomson committed
551 552 553 554 555 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
	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
602

Edward Thomson committed
603
	assert(resolved && diff_list && conflict);
nulltoken committed
604

Edward Thomson committed
605 606 607 608 609 610 611 612
	*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
613

Edward Thomson committed
614 615 616 617 618 619 620 621 622
	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;

623 624
	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
625

Edward Thomson committed
626 627
	/* if both are modified (and not to a common target) require a merge */
	if (ours_changed && theirs_changed &&
628
		git_oid__cmp(&conflict->our_entry.id, &conflict->their_entry.id) != 0)
Edward Thomson committed
629 630 631 632
		return 0;

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

Edward Thomson committed
634 635 636 637 638 639 640 641 642
	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
643

Edward Thomson committed
644
	*resolved = 1;
nulltoken committed
645

Edward Thomson committed
646 647
	git_vector_insert(&diff_list->staged, merged);
	git_vector_insert(&diff_list->resolved, (git_merge_diff *)conflict);
nulltoken committed
648

Edward Thomson committed
649 650 651 652 653 654 655
	return error;
}

static int merge_conflict_resolve_automerge(
	int *resolved,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict,
656
	unsigned int merge_file_favor)
Edward Thomson committed
657
{
658 659 660
	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
661 662 663 664
	git_index_entry *index_entry;
	git_odb *odb = NULL;
	git_oid automerge_oid;
	int error = 0;
nulltoken committed
665

Edward Thomson committed
666
	assert(resolved && diff_list && conflict);
nulltoken committed
667

Edward Thomson committed
668
	*resolved = 0;
nulltoken committed
669

670 671 672
	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ||
		!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry))
		return 0;
673

Edward Thomson committed
674 675 676 677
	/* Reject D/F conflicts */
	if (conflict->type == GIT_MERGE_DIFF_DIRECTORY_FILE)
		return 0;

Edward Thomson committed
678 679 680 681 682 683
	/* 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
684 685 686 687 688 689 690 691 692 693 694 695 696 697 698
	/* 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;

699 700 701 702
	/* Reject binary conflicts */
	if (conflict->binary)
		return 0;

703 704 705 706 707 708 709 710 711
	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;

Edward Thomson committed
712
	if ((error = git_repository_odb(&odb, diff_list->repo)) < 0 ||
713
		(error = git_merge_file_from_index(&result, diff_list->repo, ancestor, ours, theirs, &opts)) < 0 ||
Edward Thomson committed
714
		!result.automergeable ||
715
		(error = git_odb_write(&automerge_oid, odb, result.ptr, result.len, GIT_OBJ_BLOB)) < 0)
Edward Thomson committed
716
		goto done;
nulltoken committed
717

Edward Thomson committed
718 719 720 721 722 723 724 725
	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;
726
	git_oid_cpy(&index_entry->id, &automerge_oid);
nulltoken committed
727

Edward Thomson committed
728 729 730 731 732 733 734 735
	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
736

Edward Thomson committed
737 738 739 740 741 742 743
	return error;
}

static int merge_conflict_resolve(
	int *out,
	git_merge_diff_list *diff_list,
	const git_merge_diff *conflict,
744
	unsigned int merge_file_favor)
Edward Thomson committed
745 746 747
{
	int resolved = 0;
	int error = 0;
nulltoken committed
748

Edward Thomson committed
749
	*out = 0;
nulltoken committed
750

Edward Thomson committed
751 752 753
	if ((error = merge_conflict_resolve_trivial(&resolved, diff_list, conflict)) < 0)
		goto done;

754 755
	if (!resolved && (error = merge_conflict_resolve_one_removed(&resolved, diff_list, conflict)) < 0)
		goto done;
nulltoken committed
756

757 758
	if (!resolved && (error = merge_conflict_resolve_one_renamed(&resolved, diff_list, conflict)) < 0)
		goto done;
Edward Thomson committed
759

760 761
	if (!resolved && (error = merge_conflict_resolve_automerge(&resolved, diff_list, conflict, merge_file_favor)) < 0)
		goto done;
Edward Thomson committed
762 763

	*out = resolved;
nulltoken committed
764

Edward Thomson committed
765 766 767 768
done:
	return error;
}

Edward Thomson committed
769 770 771 772 773 774 775 776 777 778 779 780 781 782
/* 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,
783
	const git_merge_options *opts)
Edward Thomson committed
784 785 786 787 788 789 790
{
	GIT_UNUSED(repo);
	GIT_UNUSED(a_idx);
	GIT_UNUSED(b_idx);
	GIT_UNUSED(cache);
	GIT_UNUSED(opts);

791
	if (git_oid__cmp(&a->id, &b->id) == 0)
Edward Thomson committed
792
		return 100;
nulltoken committed
793

Edward Thomson committed
794 795 796 797 798 799 800
	return 0;
}

static int index_entry_similarity_calc(
	void **out,
	git_repository *repo,
	git_index_entry *entry,
801
	const git_merge_options *opts)
Edward Thomson committed
802 803 804
{
	git_blob *blob;
	git_diff_file diff_file = {{{0}}};
805
	git_off_t blobsize;
Edward Thomson committed
806
	int error;
nulltoken committed
807

Edward Thomson committed
808 809
	*out = NULL;

810
	if ((error = git_blob_lookup(&blob, repo, &entry->id)) < 0)
Edward Thomson committed
811
		return error;
nulltoken committed
812

813
	git_oid_cpy(&diff_file.id, &entry->id);
Edward Thomson committed
814 815 816 817
	diff_file.path = entry->path;
	diff_file.size = entry->file_size;
	diff_file.mode = entry->mode;
	diff_file.flags = 0;
nulltoken committed
818

819 820 821 822 823
	blobsize = git_blob_rawsize(blob);

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

Edward Thomson committed
825
	error = opts->metric->buffer_signature(out, &diff_file,
826
		git_blob_rawcontent(blob), (size_t)blobsize,
Edward Thomson committed
827
		opts->metric->payload);
nulltoken committed
828

Edward Thomson committed
829 830 831 832 833 834 835 836 837 838 839 840
	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,
841
	const git_merge_options *opts)
Edward Thomson committed
842 843 844
{
	int score = 0;
	int error = 0;
nulltoken committed
845

Edward Thomson committed
846 847
	if (GIT_MODE_TYPE(a->mode) != GIT_MODE_TYPE(b->mode))
		return 0;
nulltoken committed
848

Edward Thomson committed
849 850 851 852 853
	/* 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
854

Edward Thomson committed
855 856 857 858 859 860 861 862
	/* 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
863

Edward Thomson committed
864 865 866 867 868
	/* clip score */
	if (score < 0)
		score = 0;
	else if (score > 100)
		score = 100;
nulltoken committed
869

Edward Thomson committed
870 871 872 873 874 875 876 877
	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,
878
	int (*similarity_fn)(git_repository *, git_index_entry *, size_t, git_index_entry *, size_t, void **, const git_merge_options *),
Edward Thomson committed
879
	void **cache,
880
	const git_merge_options *opts)
Edward Thomson committed
881 882 883 884
{
	size_t i, j;
	git_merge_diff *conflict_src, *conflict_tgt;
	int similarity;
nulltoken committed
885

Edward Thomson committed
886 887 888 889 890 891 892
	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
893

Edward Thomson committed
894 895 896
		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
897

Edward Thomson committed
898 899
			if (GIT_MERGE_INDEX_ENTRY_EXISTS(conflict_tgt->ancestor_entry))
				continue;
nulltoken committed
900

Edward Thomson committed
901 902 903
			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
904

Edward Thomson committed
905
				if (similarity == GIT_EBUFS)
nulltoken committed
906
					continue;
Edward Thomson committed
907 908
				else if (similarity < 0)
					return similarity;
nulltoken committed
909

Edward Thomson committed
910 911 912 913 914
				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
915

Edward Thomson committed
916 917
					if (similarity_ours[j].similarity > 0)
						similarity_ours[similarity_ours[j].other_idx].similarity = 0;
nulltoken committed
918

Edward Thomson committed
919 920
					similarity_ours[i].similarity = similarity;
					similarity_ours[i].other_idx = j;
nulltoken committed
921

Edward Thomson committed
922 923 924 925
					similarity_ours[j].similarity = similarity;
					similarity_ours[j].other_idx = i;
				}
			}
nulltoken committed
926

Edward Thomson committed
927 928 929
			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
930

Edward Thomson committed
931 932 933 934 935
				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
936

Edward Thomson committed
937 938
					if (similarity_theirs[j].similarity > 0)
						similarity_theirs[similarity_theirs[j].other_idx].similarity = 0;
nulltoken committed
939

Edward Thomson committed
940 941
					similarity_theirs[i].similarity = similarity;
					similarity_theirs[i].other_idx = j;
nulltoken committed
942

Edward Thomson committed
943 944 945 946 947 948
					similarity_theirs[j].similarity = similarity;
					similarity_theirs[j].other_idx = i;
				}
			}
		}
	}
nulltoken committed
949

Edward Thomson committed
950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980
	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,
981
	const git_merge_options *opts)
Edward Thomson committed
982 983
{
	git_merge_diff *ours_source = NULL, *theirs_source = NULL;
nulltoken committed
984

Edward Thomson committed
985 986
	if (ours_renamed)
		ours_source = diff_list->conflicts.contents[ours_source_idx];
nulltoken committed
987

Edward Thomson committed
988 989
	if (theirs_renamed)
		theirs_source = diff_list->conflicts.contents[theirs_source_idx];
nulltoken committed
990

Edward Thomson committed
991 992 993 994 995 996 997 998 999 1000 1001 1002 1003
	/* 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
1004

Edward Thomson committed
1005 1006 1007 1008
		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
1009

Edward Thomson committed
1010 1011
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(ours_source->their_entry))
			ours_source->type = GIT_MERGE_DIFF_RENAMED_DELETED;
nulltoken committed
1012

Edward Thomson committed
1013 1014 1015 1016 1017 1018
		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
1019

Edward Thomson committed
1020 1021 1022 1023
		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
1024

Edward Thomson committed
1025 1026
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(theirs_source->our_entry))
			theirs_source->type = GIT_MERGE_DIFF_RENAMED_DELETED;
nulltoken committed
1027

Edward Thomson committed
1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
		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
1042

Edward Thomson committed
1043 1044 1045 1046 1047 1048 1049 1050
	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,
1051
	const git_merge_options *opts)
Edward Thomson committed
1052 1053 1054 1055 1056
{
	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
1057

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

Edward Thomson committed
1061 1062
		ours_renamed = 0;
		theirs_renamed = 0;
nulltoken committed
1063

Edward Thomson committed
1064 1065 1066
		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
1067

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

Edward Thomson committed
1070 1071 1072 1073 1074
			merge_diff_coalesce_rename(
				&ours_source->our_entry,
				&ours_source->our_status,
				&target->our_entry,
				&target->our_status);
nulltoken committed
1075

Edward Thomson committed
1076 1077
			similarity_ours[ours_source_idx].similarity = 0;
			similarity_ours[i].similarity = 0;
nulltoken committed
1078

Edward Thomson committed
1079 1080
			ours_renamed = 1;
		}
nulltoken committed
1081

Edward Thomson committed
1082 1083 1084 1085
		/* 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
1086

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

Edward Thomson committed
1089 1090 1091 1092 1093
			merge_diff_coalesce_rename(
				&theirs_source->their_entry,
				&theirs_source->their_status,
				&target->their_entry,
				&target->their_status);
nulltoken committed
1094

Edward Thomson committed
1095 1096
			similarity_theirs[theirs_source_idx].similarity = 0;
			similarity_theirs[i].similarity = 0;
nulltoken committed
1097

Edward Thomson committed
1098 1099
			theirs_renamed = 1;
		}
nulltoken committed
1100

Edward Thomson committed
1101 1102 1103 1104 1105 1106 1107
		merge_diff_mark_rename_conflict(diff_list,
			similarity_ours, ours_renamed, ours_source_idx,
			similarity_theirs, theirs_renamed, theirs_source_idx,
			target, opts);
	}
}

1108
static int merge_diff_empty(const git_vector *conflicts, size_t idx, void *p)
Edward Thomson committed
1109 1110
{
	git_merge_diff *conflict = conflicts->contents[idx];
nulltoken committed
1111

1112 1113
	GIT_UNUSED(p);

Edward Thomson committed
1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128
	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
1129

Edward Thomson committed
1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142
	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)))
			src_count++;
		else if (!GIT_MERGE_INDEX_ENTRY_EXISTS(entry->ancestor_entry))
			tgt_count++;
	}
}

int git_merge_diff_list__find_renames(
	git_repository *repo,
	git_merge_diff_list *diff_list,
1143
	const git_merge_options *opts)
Edward Thomson committed
1144 1145 1146 1147 1148 1149
{
	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
1150

Edward Thomson committed
1151
	assert(diff_list && opts);
nulltoken committed
1152

Edward Thomson committed
1153 1154
	if ((opts->flags & GIT_MERGE_TREE_FIND_RENAMES) == 0)
		return 0;
nulltoken committed
1155

Edward Thomson committed
1156 1157 1158
	similarity_ours = git__calloc(diff_list->conflicts.length,
		sizeof(struct merge_diff_similarity));
	GITERR_CHECK_ALLOC(similarity_ours);
nulltoken committed
1159

Edward Thomson committed
1160 1161 1162
	similarity_theirs = git__calloc(diff_list->conflicts.length,
		sizeof(struct merge_diff_similarity));
	GITERR_CHECK_ALLOC(similarity_theirs);
nulltoken committed
1163

Edward Thomson committed
1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176
	/* 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) {
		cache_size = diff_list->conflicts.length * 3;
		cache = git__calloc(cache_size, sizeof(void *));
		GITERR_CHECK_ALLOC(cache);

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

Edward Thomson committed
1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191
		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
1192

Edward Thomson committed
1193
	/* And remove any entries that were merged and are now empty. */
1194
	git_vector_remove_matching(&diff_list->conflicts, merge_diff_empty, NULL);
Edward Thomson committed
1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211

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
1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222
/* 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
1223

Edward Thomson committed
1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234
	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
1235

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

Edward Thomson committed
1244 1245 1246
	if (child_len < parent_len ||
		strncmp(parent, child, parent_len) != 0)
		return 0;
nulltoken committed
1247

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

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

Edward Thomson committed
1269 1270 1271
		df_data->prev_conflict->type = GIT_MERGE_DIFF_DIRECTORY_FILE;
		df_data->df_path = df_data->prev_path;
	}
nulltoken committed
1272

Edward Thomson committed
1273 1274
	df_data->prev_path = cur_path;
	df_data->prev_conflict = conflict;
nulltoken committed
1275

Edward Thomson committed
1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300
	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
1301

Edward Thomson committed
1302 1303 1304
	return 0;
}

1305 1306 1307 1308 1309 1310 1311
GIT_INLINE(int) merge_diff_detect_binary(
	git_repository *repo,
	git_merge_diff *conflict)
{
	git_blob *ancestor_blob = NULL, *our_blob = NULL, *their_blob = NULL;
	int error = 0;

Edward Thomson committed
1312
	if (GIT_MERGE_INDEX_ENTRY_ISFILE(conflict->ancestor_entry)) {
1313
		if ((error = git_blob_lookup(&ancestor_blob, repo, &conflict->ancestor_entry.id)) < 0)
1314 1315 1316 1317 1318 1319
			goto done;

		conflict->binary = git_blob_is_binary(ancestor_blob);
	}

	if (!conflict->binary &&
Edward Thomson committed
1320
		GIT_MERGE_INDEX_ENTRY_ISFILE(conflict->our_entry)) {
1321
		if ((error = git_blob_lookup(&our_blob, repo, &conflict->our_entry.id)) < 0)
1322 1323 1324 1325 1326 1327
			goto done;

		conflict->binary = git_blob_is_binary(our_blob);
	}

	if (!conflict->binary &&
Edward Thomson committed
1328
		GIT_MERGE_INDEX_ENTRY_ISFILE(conflict->their_entry)) {
1329
		if ((error = git_blob_lookup(&their_blob, repo, &conflict->their_entry.id)) < 0)
1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342
			goto done;

		conflict->binary = git_blob_is_binary(their_blob);
	}

done:
	git_blob_free(ancestor_blob);
	git_blob_free(our_blob);
	git_blob_free(their_blob);

	return error;
}

1343
GIT_INLINE(int) index_entry_dup_pool(
Edward Thomson committed
1344 1345 1346 1347 1348 1349
	git_index_entry *out,
	git_pool *pool,
	const git_index_entry *src)
{
	if (src != NULL) {
		memcpy(out, src, sizeof(git_index_entry));
nulltoken committed
1350

Edward Thomson committed
1351 1352 1353
		if ((out->path = git_pool_strdup(pool, src->path)) == NULL)
			return -1;
	}
nulltoken committed
1354

Edward Thomson committed
1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371
	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;
1372
	else if (git_oid__cmp(&ancestor->id, &other->id) ||
Edward Thomson committed
1373 1374
			 ancestor->mode != other->mode)
		return GIT_DELTA_MODIFIED;
nulltoken committed
1375

Edward Thomson committed
1376 1377 1378 1379 1380 1381 1382 1383 1384
	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
1385

Edward Thomson committed
1386 1387
	if ((conflict = git_pool_malloc(pool, sizeof(git_merge_diff))) == NULL)
		return NULL;
nulltoken committed
1388

1389 1390 1391
	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
1392
		return NULL;
nulltoken committed
1393

Edward Thomson committed
1394 1395 1396 1397
	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
1398

Edward Thomson committed
1399 1400 1401 1402 1403
	return conflict;
}

/* Merge trees */

1404
static int merge_diff_list_insert_conflict(
Edward Thomson committed
1405 1406 1407 1408 1409
	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
1410

Edward Thomson committed
1411 1412 1413
	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 ||
1414
		merge_diff_detect_binary(diff_list->repo, conflict) < 0 ||
Edward Thomson committed
1415 1416
		git_vector_insert(&diff_list->conflicts, conflict) < 0)
		return -1;
nulltoken committed
1417

Edward Thomson committed
1418 1419 1420
	return 0;
}

1421
static int merge_diff_list_insert_unmodified(
Edward Thomson committed
1422 1423 1424 1425 1426
	git_merge_diff_list *diff_list,
	const git_index_entry *tree_items[3])
{
	int error = 0;
	git_index_entry *entry;
nulltoken committed
1427

Edward Thomson committed
1428 1429
	entry = git_pool_malloc(&diff_list->pool, sizeof(git_index_entry));
	GITERR_CHECK_ALLOC(entry);
nulltoken committed
1430

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

Edward Thomson committed
1434 1435 1436 1437 1438 1439 1440 1441 1442 1443
	return error;
}

int git_merge_diff_list__find_differences(
	git_merge_diff_list *diff_list,
	const git_tree *ancestor_tree,
	const git_tree *our_tree,
	const git_tree *their_tree)
{
	git_iterator *iterators[3] = {0};
Vicent Marti committed
1444
	const git_index_entry *items[3] = {0}, *best_cur_item, *cur_items[3];
1445
	git_vector_cmp entry_compare = git_index_entry_cmp;
Edward Thomson committed
1446 1447
	struct merge_diff_df_data df_data = {0};
	int cur_item_modified;
1448
	size_t i, j;
Edward Thomson committed
1449
	int error = 0;
nulltoken committed
1450

1451
	assert(diff_list && (our_tree || their_tree));
Edward Thomson committed
1452 1453 1454 1455 1456

	if ((error = git_iterator_for_tree(&iterators[TREE_IDX_ANCESTOR], (git_tree *)ancestor_tree, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
		(error = git_iterator_for_tree(&iterators[TREE_IDX_OURS], (git_tree *)our_tree, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0 ||
		(error = git_iterator_for_tree(&iterators[TREE_IDX_THEIRS], (git_tree *)their_tree, GIT_ITERATOR_DONT_IGNORE_CASE, NULL, NULL)) < 0)
		goto done;
nulltoken committed
1457

Edward Thomson committed
1458 1459
	/* Set up the iterators */
	for (i = 0; i < 3; i++) {
1460
		error = git_iterator_current(&items[i], iterators[i]);
1461

1462
		if (error < 0 && error != GIT_ITEROVER)
Edward Thomson committed
1463 1464
			goto done;
	}
nulltoken committed
1465

Edward Thomson committed
1466
	while (true) {
1467 1468 1469
		for (i = 0; i < 3; i++)
			cur_items[i] = NULL;

Edward Thomson committed
1470 1471
		best_cur_item = NULL;
		cur_item_modified = 0;
nulltoken committed
1472

Edward Thomson committed
1473 1474 1475 1476 1477 1478
		/* Find the next path(s) to consume from each iterator */
		for (i = 0; i < 3; i++) {
			if (items[i] == NULL) {
				cur_item_modified = 1;
				continue;
			}
nulltoken committed
1479

Edward Thomson committed
1480 1481 1482 1483 1484
			if (best_cur_item == NULL) {
				best_cur_item = items[i];
				cur_items[i] = items[i];
			} else {
				int path_diff = entry_compare(items[i], best_cur_item);
nulltoken committed
1485

Edward Thomson committed
1486 1487 1488 1489 1490
				if (path_diff < 0) {
					/*
					 * Found an item that sorts before our current item, make
					 * our current item this one.
					 */
1491 1492 1493
					for (j = 0; j < i; j++)
						cur_items[j] = NULL;

Edward Thomson committed
1494 1495 1496 1497 1498 1499 1500 1501
					cur_item_modified = 1;
					best_cur_item = items[i];
					cur_items[i] = items[i];
				} else if (path_diff > 0) {
					/* No entry for the current item, this is modified */
					cur_item_modified = 1;
				} else if (path_diff == 0) {
					cur_items[i] = items[i];
nulltoken committed
1502

Edward Thomson committed
1503 1504 1505 1506 1507
					if (!cur_item_modified)
						cur_item_modified = index_entry_cmp(best_cur_item, items[i]);
				}
			}
		}
nulltoken committed
1508

Edward Thomson committed
1509 1510
		if (best_cur_item == NULL)
			break;
nulltoken committed
1511

Edward Thomson committed
1512
		if (cur_item_modified)
1513
			error = merge_diff_list_insert_conflict(diff_list, &df_data, cur_items);
Edward Thomson committed
1514
		else
1515
			error = merge_diff_list_insert_unmodified(diff_list, cur_items);
1516 1517
		if (error < 0)
			goto done;
nulltoken committed
1518

Edward Thomson committed
1519 1520
		/* Advance each iterator that participated */
		for (i = 0; i < 3; i++) {
1521 1522 1523 1524
			if (cur_items[i] == NULL)
				continue;

			error = git_iterator_advance(&items[i], iterators[i]);
1525

1526
			if (error < 0 && error != GIT_ITEROVER)
Edward Thomson committed
1527 1528 1529
				goto done;
		}
	}
nulltoken committed
1530

Edward Thomson committed
1531 1532 1533
done:
	for (i = 0; i < 3; i++)
		git_iterator_free(iterators[i]);
nulltoken committed
1534

1535 1536 1537
	if (error == GIT_ITEROVER)
		error = 0;

Edward Thomson committed
1538 1539 1540 1541 1542 1543
	return error;
}

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
1544

Edward Thomson committed
1545 1546
	if (diff_list == NULL)
		return NULL;
nulltoken committed
1547

Edward Thomson committed
1548
	diff_list->repo = repo;
nulltoken committed
1549

Edward Thomson committed
1550 1551 1552
	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
1553 1554
		git_pool_init(&diff_list->pool, 1, 0) < 0) {
		git_merge_diff_list__free(diff_list);
Edward Thomson committed
1555
		return NULL;
Jacques Germishuys committed
1556
	}
nulltoken committed
1557

Edward Thomson committed
1558 1559 1560
	return diff_list;
}

Edward Thomson committed
1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572
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);
}

1573
static int merge_normalize_opts(
Edward Thomson committed
1574
	git_repository *repo,
1575 1576
	git_merge_options *opts,
	const git_merge_options *given)
Edward Thomson committed
1577 1578 1579
{
	git_config *cfg = NULL;
	int error = 0;
nulltoken committed
1580

Edward Thomson committed
1581
	assert(repo && opts);
nulltoken committed
1582

Edward Thomson committed
1583 1584
	if ((error = git_repository_config__weakptr(&cfg, repo)) < 0)
		return error;
nulltoken committed
1585

Edward Thomson committed
1586
	if (given != NULL)
1587
		memcpy(opts, given, sizeof(git_merge_options));
Edward Thomson committed
1588
	else {
1589
		git_merge_options init = GIT_MERGE_OPTIONS_INIT;
Edward Thomson committed
1590
		memcpy(opts, &init, sizeof(init));
nulltoken committed
1591

Edward Thomson committed
1592 1593 1594
		opts->flags = GIT_MERGE_TREE_FIND_RENAMES;
		opts->rename_threshold = GIT_MERGE_TREE_RENAME_THRESHOLD;
	}
nulltoken committed
1595

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

1599 1600
		if (!limit)
			limit = git_config__get_int_force(cfg, "diff.renamelimit", 0);
nulltoken committed
1601

1602 1603
		opts->target_limit = (limit <= 0) ?
			GIT_MERGE_TREE_TARGET_LIMIT : (unsigned int)limit;
Edward Thomson committed
1604
	}
nulltoken committed
1605

Edward Thomson committed
1606 1607 1608 1609
	/* 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
1610

Edward Thomson committed
1611 1612 1613 1614
		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;
nulltoken committed
1615

Edward Thomson committed
1616 1617 1618 1619 1620 1621
		if (opts->flags & GIT_DIFF_FIND_IGNORE_WHITESPACE)
			opts->metric->payload = (void *)GIT_HASHSIG_IGNORE_WHITESPACE;
		else if (opts->flags & GIT_DIFF_FIND_DONT_IGNORE_WHITESPACE)
			opts->metric->payload = (void *)GIT_HASHSIG_NORMAL;
		else
			opts->metric->payload = (void *)GIT_HASHSIG_SMART_WHITESPACE;
Edward Thomson committed
1622
	}
nulltoken committed
1623

Edward Thomson committed
1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636
	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
1637

Edward Thomson committed
1638 1639
	if (!GIT_MERGE_INDEX_ENTRY_EXISTS(*entry))
		return 0;
nulltoken committed
1640

Edward Thomson committed
1641 1642 1643 1644 1645 1646
	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
1647

Edward Thomson committed
1648
	mode[idx] = entry->mode;
1649
	oid[idx] = &entry->id;
nulltoken committed
1650

Edward Thomson committed
1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661
	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
1662

Edward Thomson committed
1663
	*out = NULL;
nulltoken committed
1664

Edward Thomson committed
1665 1666
	if ((error = git_index_new(&index)) < 0)
		return error;
nulltoken committed
1667

Edward Thomson committed
1668 1669 1670 1671
	git_vector_foreach(&diff_list->staged, i, entry) {
		if ((error = git_index_add(index, entry)) < 0)
			goto on_error;
	}
nulltoken committed
1672

Edward Thomson committed
1673 1674 1675 1676
	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
1677

Edward Thomson committed
1678 1679 1680
		const git_index_entry *ours =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
			&conflict->our_entry : NULL;
nulltoken committed
1681

Edward Thomson committed
1682 1683 1684
		const git_index_entry *theirs =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
			&conflict->their_entry : NULL;
nulltoken committed
1685

Edward Thomson committed
1686 1687 1688
		if ((error = git_index_conflict_add(index, ancestor, ours, theirs)) < 0)
			goto on_error;
	}
nulltoken committed
1689

Edward Thomson committed
1690 1691 1692
	/* 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
1693

Edward Thomson committed
1694 1695
		if (!GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->ancestor_entry))
			continue;
nulltoken committed
1696

Edward Thomson committed
1697
		ancestor_path = conflict->ancestor_entry.path;
nulltoken committed
1698

Edward Thomson committed
1699 1700 1701
		our_path =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->our_entry) ?
			conflict->our_entry.path : NULL;
nulltoken committed
1702

Edward Thomson committed
1703 1704 1705
		their_path =
			GIT_MERGE_INDEX_ENTRY_EXISTS(conflict->their_entry) ?
			conflict->their_entry.path : NULL;
nulltoken committed
1706

Edward Thomson committed
1707 1708 1709 1710 1711
		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
1712
	}
nulltoken committed
1713

Edward Thomson committed
1714 1715 1716 1717 1718 1719 1720 1721 1722 1723
	/* 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
1724

Edward Thomson committed
1725 1726 1727 1728 1729 1730 1731
		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
1732

Edward Thomson committed
1733 1734 1735
		if (ours != NULL &&
			(error = merge_index_insert_reuc(index, TREE_IDX_OURS, ours)) < 0)
			goto on_error;
nulltoken committed
1736

Edward Thomson committed
1737 1738 1739 1740
		if (theirs != NULL &&
			(error = merge_index_insert_reuc(index, TREE_IDX_THEIRS, theirs)) < 0)
			goto on_error;
	}
nulltoken committed
1741

Edward Thomson committed
1742 1743
	*out = index;
	return 0;
nulltoken committed
1744

Edward Thomson committed
1745 1746
on_error:
	git_index_free(index);
nulltoken committed
1747

Edward Thomson committed
1748 1749 1750 1751 1752 1753 1754 1755 1756
	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,
1757
	const git_merge_options *given_opts)
Edward Thomson committed
1758 1759
{
	git_merge_diff_list *diff_list;
1760
	git_merge_options opts;
Edward Thomson committed
1761 1762 1763 1764 1765
	git_merge_diff *conflict;
	git_vector changes;
	size_t i;
	int error = 0;

1766
	assert(out && repo && (our_tree || their_tree));
Edward Thomson committed
1767 1768

	*out = NULL;
nulltoken committed
1769

1770
	GITERR_CHECK_VERSION(given_opts, GIT_MERGE_OPTIONS_VERSION, "git_merge_options");
1771

1772
	if ((error = merge_normalize_opts(repo, &opts, given_opts)) < 0)
Edward Thomson committed
1773 1774 1775 1776
		return error;

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

Edward Thomson committed
1778 1779
	if ((error = git_merge_diff_list__find_differences(diff_list, ancestor_tree, our_tree, their_tree)) < 0 ||
		(error = git_merge_diff_list__find_renames(repo, diff_list, &opts)) < 0)
Edward Thomson committed
1780
		goto done;
nulltoken committed
1781

Edward Thomson committed
1782 1783
	memcpy(&changes, &diff_list->conflicts, sizeof(git_vector));
	git_vector_clear(&diff_list->conflicts);
nulltoken committed
1784

Edward Thomson committed
1785 1786
	git_vector_foreach(&changes, i, conflict) {
		int resolved = 0;
nulltoken committed
1787

1788
		if ((error = merge_conflict_resolve(&resolved, diff_list, conflict, opts.file_favor)) < 0)
Edward Thomson committed
1789
			goto done;
nulltoken committed
1790

Edward Thomson committed
1791 1792 1793
		if (!resolved)
			git_vector_insert(&diff_list->conflicts, conflict);
	}
nulltoken committed
1794

Edward Thomson committed
1795 1796
	if (!given_opts || !given_opts->metric)
		git__free(opts.metric);
nulltoken committed
1797

Edward Thomson committed
1798 1799 1800 1801 1802 1803 1804 1805
	error = index_from_diff_list(out, diff_list);

done:
	git_merge_diff_list__free(diff_list);

	return error;
}

1806 1807 1808 1809 1810
int git_merge_commits(
	git_index **out,
	git_repository *repo,
	const git_commit *our_commit,
	const git_commit *their_commit,
1811
	const git_merge_options *opts)
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 1839
{
	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
1840 1841 1842 1843
/* Merge setup / cleanup */

static int write_merge_head(
	git_repository *repo,
1844
	const git_annotated_commit *heads[],
Edward Thomson committed
1845 1846 1847 1848 1849 1850 1851 1852 1853 1854
	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 ||
1855
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_FORCE, GIT_MERGE_FILE_MODE)) < 0)
Edward Thomson committed
1856 1857 1858
		goto cleanup;

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

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

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

	git_buf_free(&file_path);

	return error;
}

1874
static int write_merge_mode(git_repository *repo)
Edward Thomson committed
1875 1876 1877 1878 1879 1880 1881 1882
{
	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 ||
1883
		(error = git_filebuf_open(&file, file_path.ptr, GIT_FILEBUF_FORCE, GIT_MERGE_FILE_MODE)) < 0)
Edward Thomson committed
1884 1885
		goto cleanup;

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

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

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

	git_buf_free(&file_path);

	return error;
}

struct merge_msg_entry {
1901
	const git_annotated_commit *merge_head;
Edward Thomson committed
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 2088
	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,
2089
	const git_annotated_commit *heads[],
Edward Thomson committed
2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104
	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); 

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

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

2133 2134
		if ((error = git_filebuf_printf(&file,
			"%scommit '%s'", (i > 0) ? "; " : "",
2135
			entries[i].merge_head->id_str)) < 0)
Edward Thomson committed
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 2181
			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;

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

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

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

	git_buf_free(&file_path);

	git_vector_free(&matching);
	git__free(entries);

	return error;
}

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

	assert (repo && our_head && heads);

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

2222 2223 2224
/* Merge branches */

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

	assert(repo && our_head && their_heads);

	oids = git__calloc(their_heads_len + 1, sizeof(git_oid));
	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 2439
	}

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

		if (git_index_entry_stage(e) != 0 &&
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 2454 2455 2456
	if ((conflicts = index_conflicts + wd_conflicts) > 0) {
		giterr_set(GITERR_MERGE, "%d uncommitted change%s would be overwritten by merge",
			conflicts, (conflicts != 1) ? "s" : "");
		error = GIT_EMERGECONFLICT;
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 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510

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

		if (git_index_entry_stage(e) == 0)
			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_new = NULL;
2661 2662
	size_t i;
	int error = 0;
2663

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

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

2674
	if ((error = merge_heads(&ancestor_head, &our_head, repo, their_heads, their_heads_len)) < 0)
2675 2676
		goto on_error;

2677 2678
	if ((error = merge_normalize_checkout_opts(repo, &checkout_opts, given_checkout_opts,
		ancestor_head, our_head, their_heads_len, their_heads)) < 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
	if ((error = git_merge_trees(&index_new, repo, ancestor_tree, our_tree, their_trees[0], merge_opts)) < 0 ||
2700 2701 2702
		(error = git_merge__check_result(repo, index_new)) < 0 ||
		(error = git_merge__append_conflicts_to_merge_msg(repo, index_new)) < 0 ||
		(error = git_checkout_index(repo, index_new, &checkout_opts)) < 0)
2703 2704 2705 2706 2707
		goto on_error;

	goto done;

on_error:
2708
	merge_state_cleanup(repo);
2709 2710

done:
2711
	git_index_free(index_new);
2712 2713 2714 2715 2716 2717 2718 2719 2720

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

2721 2722
	git_annotated_commit_free(our_head);
	git_annotated_commit_free(ancestor_head);
2723 2724 2725 2726 2727 2728

	git_reference_free(our_ref);

	return error;
}

2729
int git_merge_init_options(git_merge_options *opts, unsigned int version)
2730
{
2731 2732 2733
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		opts, version, git_merge_options, GIT_MERGE_OPTIONS_INIT);
	return 0;
2734
}
2735

2736
int git_merge_file_init_input(git_merge_file_input *input, unsigned int version)
2737
{
2738 2739 2740
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		input, version, git_merge_file_input, GIT_MERGE_FILE_INPUT_INIT);
	return 0;
2741 2742
}

2743 2744
int git_merge_file_init_options(
	git_merge_file_options *opts, unsigned int version)
2745
{
2746 2747 2748
	GIT_INIT_STRUCTURE_FROM_TEMPLATE(
		opts, version, git_merge_file_options, GIT_MERGE_FILE_OPTIONS_INIT);
	return 0;
2749
}