git

1
#define USE_THE_REPOSITORY_VARIABLE
2

3
#include "git-compat-util.h"
4
#include "advice.h"
5
#include "strvec.h"
6
#include "repository.h"
7
#include "parse.h"
8
#include "dir.h"
9
#include "environment.h"
10
#include "gettext.h"
11
#include "hex.h"
12
#include "name-hash.h"
13
#include "tree.h"
14
#include "tree-walk.h"
15
#include "cache-tree.h"
16
#include "unpack-trees.h"
17
#include "progress.h"
18
#include "refs.h"
19
#include "attr.h"
20
#include "read-cache.h"
21
#include "split-index.h"
22
#include "sparse-index.h"
23
#include "submodule.h"
24
#include "submodule-config.h"
25
#include "symlinks.h"
26
#include "trace2.h"
27
#include "fsmonitor.h"
28
#include "object-store-ll.h"
29
#include "promisor-remote.h"
30
#include "entry.h"
31
#include "parallel-checkout.h"
32
#include "setup.h"
33

34
/*
35
 * Error messages expected by scripts out of plumbing commands such as
36
 * read-tree.  Non-scripted Porcelain is not required to use these messages
37
 * and in fact are encouraged to reword them to better suit their particular
38
 * situation better.  See how "git checkout" and "git merge" replaces
39
 * them using setup_unpack_trees_porcelain(), for example.
40
 */
41
static const char *unpack_plumbing_errors[NB_UNPACK_TREES_WARNING_TYPES] = {
42
	/* ERROR_WOULD_OVERWRITE */
43
	"Entry '%s' would be overwritten by merge. Cannot merge.",
44

45
	/* ERROR_NOT_UPTODATE_FILE */
46
	"Entry '%s' not uptodate. Cannot merge.",
47

48
	/* ERROR_NOT_UPTODATE_DIR */
49
	"Updating '%s' would lose untracked files in it",
50

51
	/* ERROR_CWD_IN_THE_WAY */
52
	"Refusing to remove '%s' since it is the current working directory.",
53

54
	/* ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN */
55
	"Untracked working tree file '%s' would be overwritten by merge.",
56

57
	/* ERROR_WOULD_LOSE_UNTRACKED_REMOVED */
58
	"Untracked working tree file '%s' would be removed by merge.",
59

60
	/* ERROR_BIND_OVERLAP */
61
	"Entry '%s' overlaps with '%s'.  Cannot bind.",
62

63
	/* ERROR_WOULD_LOSE_SUBMODULE */
64
	"Submodule '%s' cannot checkout new HEAD.",
65

66
	/* NB_UNPACK_TREES_ERROR_TYPES; just a meta value */
67
	"",
68

69
	/* WARNING_SPARSE_NOT_UPTODATE_FILE */
70
	"Path '%s' not uptodate; will not remove from working tree.",
71

72
	/* WARNING_SPARSE_UNMERGED_FILE */
73
	"Path '%s' unmerged; will not remove from working tree.",
74

75
	/* WARNING_SPARSE_ORPHANED_NOT_OVERWRITTEN */
76
	"Path '%s' already present; will not overwrite with sparse update.",
77
};
78

79
#define ERRORMSG(o,type) \
80
	( ((o) && (o)->internal.msgs[(type)]) \
81
	  ? ((o)->internal.msgs[(type)])      \
82
	  : (unpack_plumbing_errors[(type)]) )
83

84
static const char *super_prefixed(const char *path, const char *super_prefix)
85
{
86
	/*
87
	 * It is necessary and sufficient to have two static buffers
88
	 * here, as the return value of this function is fed to
89
	 * error() using the unpack_*_errors[] templates we see above.
90
	 */
91
	static struct strbuf buf[2] = {STRBUF_INIT, STRBUF_INIT};
92
	static int super_prefix_len = -1;
93
	static unsigned idx = ARRAY_SIZE(buf) - 1;
94

95
	if (super_prefix_len < 0) {
96
		if (!super_prefix) {
97
			super_prefix_len = 0;
98
		} else {
99
			int i;
100
			for (i = 0; i < ARRAY_SIZE(buf); i++)
101
				strbuf_addstr(&buf[i], super_prefix);
102
			super_prefix_len = buf[0].len;
103
		}
104
	}
105

106
	if (!super_prefix_len)
107
		return path;
108

109
	if (++idx >= ARRAY_SIZE(buf))
110
		idx = 0;
111

112
	strbuf_setlen(&buf[idx], super_prefix_len);
113
	strbuf_addstr(&buf[idx], path);
114

115
	return buf[idx].buf;
116
}
117

118
void setup_unpack_trees_porcelain(struct unpack_trees_options *opts,
119
				  const char *cmd)
120
{
121
	int i;
122
	const char **msgs = opts->internal.msgs;
123
	const char *msg;
124

125
	strvec_init(&opts->internal.msgs_to_free);
126

127
	if (!strcmp(cmd, "checkout"))
128
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
129
		      ? _("Your local changes to the following files would be overwritten by checkout:\n%%s"
130
			  "Please commit your changes or stash them before you switch branches.")
131
		      : _("Your local changes to the following files would be overwritten by checkout:\n%%s");
132
	else if (!strcmp(cmd, "merge"))
133
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
134
		      ? _("Your local changes to the following files would be overwritten by merge:\n%%s"
135
			  "Please commit your changes or stash them before you merge.")
136
		      : _("Your local changes to the following files would be overwritten by merge:\n%%s");
137
	else
138
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
139
		      ? _("Your local changes to the following files would be overwritten by %s:\n%%s"
140
			  "Please commit your changes or stash them before you %s.")
141
		      : _("Your local changes to the following files would be overwritten by %s:\n%%s");
142
	msgs[ERROR_WOULD_OVERWRITE] = msgs[ERROR_NOT_UPTODATE_FILE] =
143
		strvec_pushf(&opts->internal.msgs_to_free, msg, cmd, cmd);
144

145
	msgs[ERROR_NOT_UPTODATE_DIR] =
146
		_("Updating the following directories would lose untracked files in them:\n%s");
147

148
	msgs[ERROR_CWD_IN_THE_WAY] =
149
		_("Refusing to remove the current working directory:\n%s");
150

151
	if (!strcmp(cmd, "checkout"))
152
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
153
		      ? _("The following untracked working tree files would be removed by checkout:\n%%s"
154
			  "Please move or remove them before you switch branches.")
155
		      : _("The following untracked working tree files would be removed by checkout:\n%%s");
156
	else if (!strcmp(cmd, "merge"))
157
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
158
		      ? _("The following untracked working tree files would be removed by merge:\n%%s"
159
			  "Please move or remove them before you merge.")
160
		      : _("The following untracked working tree files would be removed by merge:\n%%s");
161
	else
162
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
163
		      ? _("The following untracked working tree files would be removed by %s:\n%%s"
164
			  "Please move or remove them before you %s.")
165
		      : _("The following untracked working tree files would be removed by %s:\n%%s");
166
	msgs[ERROR_WOULD_LOSE_UNTRACKED_REMOVED] =
167
		strvec_pushf(&opts->internal.msgs_to_free, msg, cmd, cmd);
168

169
	if (!strcmp(cmd, "checkout"))
170
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
171
		      ? _("The following untracked working tree files would be overwritten by checkout:\n%%s"
172
			  "Please move or remove them before you switch branches.")
173
		      : _("The following untracked working tree files would be overwritten by checkout:\n%%s");
174
	else if (!strcmp(cmd, "merge"))
175
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
176
		      ? _("The following untracked working tree files would be overwritten by merge:\n%%s"
177
			  "Please move or remove them before you merge.")
178
		      : _("The following untracked working tree files would be overwritten by merge:\n%%s");
179
	else
180
		msg = advice_enabled(ADVICE_COMMIT_BEFORE_MERGE)
181
		      ? _("The following untracked working tree files would be overwritten by %s:\n%%s"
182
			  "Please move or remove them before you %s.")
183
		      : _("The following untracked working tree files would be overwritten by %s:\n%%s");
184
	msgs[ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN] =
185
		strvec_pushf(&opts->internal.msgs_to_free, msg, cmd, cmd);
186

187
	/*
188
	 * Special case: ERROR_BIND_OVERLAP refers to a pair of paths, we
189
	 * cannot easily display it as a list.
190
	 */
191
	msgs[ERROR_BIND_OVERLAP] = _("Entry '%s' overlaps with '%s'.  Cannot bind.");
192

193
	msgs[ERROR_WOULD_LOSE_SUBMODULE] =
194
		_("Cannot update submodule:\n%s");
195

196
	msgs[WARNING_SPARSE_NOT_UPTODATE_FILE] =
197
		_("The following paths are not up to date and were left despite sparse patterns:\n%s");
198
	msgs[WARNING_SPARSE_UNMERGED_FILE] =
199
		_("The following paths are unmerged and were left despite sparse patterns:\n%s");
200
	msgs[WARNING_SPARSE_ORPHANED_NOT_OVERWRITTEN] =
201
		_("The following paths were already present and thus not updated despite sparse patterns:\n%s");
202

203
	opts->internal.show_all_errors = 1;
204
	/* rejected paths may not have a static buffer */
205
	for (i = 0; i < ARRAY_SIZE(opts->internal.unpack_rejects); i++)
206
		opts->internal.unpack_rejects[i].strdup_strings = 1;
207
}
208

209
void clear_unpack_trees_porcelain(struct unpack_trees_options *opts)
210
{
211
	strvec_clear(&opts->internal.msgs_to_free);
212
	memset(opts->internal.msgs, 0, sizeof(opts->internal.msgs));
213
	discard_index(&opts->internal.result);
214
}
215

216
static int do_add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
217
			 unsigned int set, unsigned int clear)
218
{
219
	clear |= CE_HASHED;
220

221
	if (set & CE_REMOVE)
222
		set |= CE_WT_REMOVE;
223

224
	ce->ce_flags = (ce->ce_flags & ~clear) | set;
225
	return add_index_entry(&o->internal.result, ce,
226
			       ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
227
}
228

229
static void add_entry(struct unpack_trees_options *o,
230
		      const struct cache_entry *ce,
231
		      unsigned int set, unsigned int clear)
232
{
233
	do_add_entry(o, dup_cache_entry(ce, &o->internal.result), set, clear);
234
}
235

236
/*
237
 * add error messages on path <path>
238
 * corresponding to the type <e> with the message <msg>
239
 * indicating if it should be display in porcelain or not
240
 */
241
static int add_rejected_path(struct unpack_trees_options *o,
242
			     enum unpack_trees_error_types e,
243
			     const char *path)
244
{
245
	if (o->quiet)
246
		return -1;
247

248
	if (!o->internal.show_all_errors)
249
		return error(ERRORMSG(o, e), super_prefixed(path,
250
							    o->super_prefix));
251

252
	/*
253
	 * Otherwise, insert in a list for future display by
254
	 * display_(error|warning)_msgs()
255
	 */
256
	string_list_append(&o->internal.unpack_rejects[e], path);
257
	return -1;
258
}
259

260
/*
261
 * display all the error messages stored in a nice way
262
 */
263
static void display_error_msgs(struct unpack_trees_options *o)
264
{
265
	int e;
266
	unsigned error_displayed = 0;
267
	for (e = 0; e < NB_UNPACK_TREES_ERROR_TYPES; e++) {
268
		struct string_list *rejects = &o->internal.unpack_rejects[e];
269

270
		if (rejects->nr > 0) {
271
			int i;
272
			struct strbuf path = STRBUF_INIT;
273

274
			error_displayed = 1;
275
			for (i = 0; i < rejects->nr; i++)
276
				strbuf_addf(&path, "\t%s\n", rejects->items[i].string);
277
			error(ERRORMSG(o, e), super_prefixed(path.buf,
278
							     o->super_prefix));
279
			strbuf_release(&path);
280
		}
281
		string_list_clear(rejects, 0);
282
	}
283
	if (error_displayed)
284
		fprintf(stderr, _("Aborting\n"));
285
}
286

287
/*
288
 * display all the warning messages stored in a nice way
289
 */
290
static void display_warning_msgs(struct unpack_trees_options *o)
291
{
292
	int e;
293
	unsigned warning_displayed = 0;
294
	for (e = NB_UNPACK_TREES_ERROR_TYPES + 1;
295
	     e < NB_UNPACK_TREES_WARNING_TYPES; e++) {
296
		struct string_list *rejects = &o->internal.unpack_rejects[e];
297

298
		if (rejects->nr > 0) {
299
			int i;
300
			struct strbuf path = STRBUF_INIT;
301

302
			warning_displayed = 1;
303
			for (i = 0; i < rejects->nr; i++)
304
				strbuf_addf(&path, "\t%s\n", rejects->items[i].string);
305
			warning(ERRORMSG(o, e), super_prefixed(path.buf,
306
							       o->super_prefix));
307
			strbuf_release(&path);
308
		}
309
		string_list_clear(rejects, 0);
310
	}
311
	if (warning_displayed)
312
		fprintf(stderr, _("After fixing the above paths, you may want to run `git sparse-checkout reapply`.\n"));
313
}
314
static int check_submodule_move_head(const struct cache_entry *ce,
315
				     const char *old_id,
316
				     const char *new_id,
317
				     struct unpack_trees_options *o)
318
{
319
	unsigned flags = SUBMODULE_MOVE_HEAD_DRY_RUN;
320
	const struct submodule *sub = submodule_from_ce(ce);
321

322
	if (!sub)
323
		return 0;
324

325
	if (o->reset)
326
		flags |= SUBMODULE_MOVE_HEAD_FORCE;
327

328
	if (submodule_move_head(ce->name, o->super_prefix, old_id, new_id,
329
				flags))
330
		return add_rejected_path(o, ERROR_WOULD_LOSE_SUBMODULE, ce->name);
331
	return 0;
332
}
333

334
/*
335
 * Perform the loading of the repository's gitmodules file.  This function is
336
 * used by 'check_update()' to perform loading of the gitmodules file in two
337
 * different situations:
338
 * (1) before removing entries from the working tree if the gitmodules file has
339
 *     been marked for removal.  This situation is specified by 'state' == NULL.
340
 * (2) before checking out entries to the working tree if the gitmodules file
341
 *     has been marked for update.  This situation is specified by 'state' != NULL.
342
 */
343
static void load_gitmodules_file(struct index_state *index,
344
				 struct checkout *state)
345
{
346
	int pos = index_name_pos(index, GITMODULES_FILE, strlen(GITMODULES_FILE));
347

348
	if (pos >= 0) {
349
		struct cache_entry *ce = index->cache[pos];
350
		if (!state && ce->ce_flags & CE_WT_REMOVE) {
351
			repo_read_gitmodules(the_repository, 0);
352
		} else if (state && (ce->ce_flags & CE_UPDATE)) {
353
			submodule_free(the_repository);
354
			checkout_entry(ce, state, NULL, NULL);
355
			repo_read_gitmodules(the_repository, 0);
356
		}
357
	}
358
}
359

360
static struct progress *get_progress(struct unpack_trees_options *o,
361
				     struct index_state *index)
362
{
363
	unsigned cnt = 0, total = 0;
364

365
	if (!o->update || !o->verbose_update)
366
		return NULL;
367

368
	for (; cnt < index->cache_nr; cnt++) {
369
		const struct cache_entry *ce = index->cache[cnt];
370
		if (ce->ce_flags & (CE_UPDATE | CE_WT_REMOVE))
371
			total++;
372
	}
373

374
	return start_delayed_progress(_("Updating files"), total);
375
}
376

377
static void setup_collided_checkout_detection(struct checkout *state,
378
					      struct index_state *index)
379
{
380
	int i;
381

382
	state->clone = 1;
383
	for (i = 0; i < index->cache_nr; i++)
384
		index->cache[i]->ce_flags &= ~CE_MATCHED;
385
}
386

387
static void report_collided_checkout(struct index_state *index)
388
{
389
	struct string_list list = STRING_LIST_INIT_NODUP;
390
	int i;
391

392
	for (i = 0; i < index->cache_nr; i++) {
393
		struct cache_entry *ce = index->cache[i];
394

395
		if (!(ce->ce_flags & CE_MATCHED))
396
			continue;
397

398
		string_list_append(&list, ce->name);
399
		ce->ce_flags &= ~CE_MATCHED;
400
	}
401

402
	list.cmp = fspathcmp;
403
	string_list_sort(&list);
404

405
	if (list.nr) {
406
		warning(_("the following paths have collided (e.g. case-sensitive paths\n"
407
			  "on a case-insensitive filesystem) and only one from the same\n"
408
			  "colliding group is in the working tree:\n"));
409

410
		for (i = 0; i < list.nr; i++)
411
			fprintf(stderr, "  '%s'\n", list.items[i].string);
412
	}
413

414
	string_list_clear(&list, 0);
415
}
416

417
static int must_checkout(const struct cache_entry *ce)
418
{
419
	return ce->ce_flags & CE_UPDATE;
420
}
421

422
static int check_updates(struct unpack_trees_options *o,
423
			 struct index_state *index)
424
{
425
	unsigned cnt = 0;
426
	int errs = 0;
427
	struct progress *progress;
428
	struct checkout state = CHECKOUT_INIT;
429
	int i, pc_workers, pc_threshold;
430

431
	trace_performance_enter();
432
	state.super_prefix = o->super_prefix;
433
	state.force = 1;
434
	state.quiet = 1;
435
	state.refresh_cache = 1;
436
	state.istate = index;
437
	clone_checkout_metadata(&state.meta, &o->meta, NULL);
438

439
	if (!o->update || o->dry_run) {
440
		remove_marked_cache_entries(index, 0);
441
		trace_performance_leave("check_updates");
442
		return 0;
443
	}
444

445
	if (o->clone)
446
		setup_collided_checkout_detection(&state, index);
447

448
	progress = get_progress(o, index);
449

450
	/* Start with clean cache to avoid using any possibly outdated info. */
451
	invalidate_lstat_cache();
452

453
	git_attr_set_direction(GIT_ATTR_CHECKOUT);
454

455
	if (should_update_submodules())
456
		load_gitmodules_file(index, NULL);
457

458
	for (i = 0; i < index->cache_nr; i++) {
459
		const struct cache_entry *ce = index->cache[i];
460

461
		if (ce->ce_flags & CE_WT_REMOVE) {
462
			display_progress(progress, ++cnt);
463
			unlink_entry(ce, o->super_prefix);
464
		}
465
	}
466

467
	remove_marked_cache_entries(index, 0);
468
	remove_scheduled_dirs();
469

470
	if (should_update_submodules())
471
		load_gitmodules_file(index, &state);
472

473
	if (repo_has_promisor_remote(the_repository))
474
		/*
475
		 * Prefetch the objects that are to be checked out in the loop
476
		 * below.
477
		 */
478
		prefetch_cache_entries(index, must_checkout);
479

480
	get_parallel_checkout_configs(&pc_workers, &pc_threshold);
481

482
	enable_delayed_checkout(&state);
483
	if (pc_workers > 1)
484
		init_parallel_checkout();
485
	for (i = 0; i < index->cache_nr; i++) {
486
		struct cache_entry *ce = index->cache[i];
487

488
		if (must_checkout(ce)) {
489
			size_t last_pc_queue_size = pc_queue_size();
490

491
			if (ce->ce_flags & CE_WT_REMOVE)
492
				BUG("both update and delete flags are set on %s",
493
				    ce->name);
494
			ce->ce_flags &= ~CE_UPDATE;
495
			errs |= checkout_entry(ce, &state, NULL, NULL);
496

497
			if (last_pc_queue_size == pc_queue_size())
498
				display_progress(progress, ++cnt);
499
		}
500
	}
501
	if (pc_workers > 1)
502
		errs |= run_parallel_checkout(&state, pc_workers, pc_threshold,
503
					      progress, &cnt);
504
	stop_progress(&progress);
505
	errs |= finish_delayed_checkout(&state, o->verbose_update);
506
	git_attr_set_direction(GIT_ATTR_CHECKIN);
507

508
	if (o->clone)
509
		report_collided_checkout(index);
510

511
	trace_performance_leave("check_updates");
512
	return errs != 0;
513
}
514

515
static int verify_uptodate_sparse(const struct cache_entry *ce,
516
				  struct unpack_trees_options *o);
517
static int verify_absent_sparse(const struct cache_entry *ce,
518
				enum unpack_trees_error_types,
519
				struct unpack_trees_options *o);
520

521
static int apply_sparse_checkout(struct index_state *istate,
522
				 struct cache_entry *ce,
523
				 struct unpack_trees_options *o)
524
{
525
	int was_skip_worktree = ce_skip_worktree(ce);
526

527
	if (ce->ce_flags & CE_NEW_SKIP_WORKTREE)
528
		ce->ce_flags |= CE_SKIP_WORKTREE;
529
	else
530
		ce->ce_flags &= ~CE_SKIP_WORKTREE;
531
	if (was_skip_worktree != ce_skip_worktree(ce)) {
532
		ce->ce_flags |= CE_UPDATE_IN_BASE;
533
		mark_fsmonitor_invalid(istate, ce);
534
		istate->cache_changed |= CE_ENTRY_CHANGED;
535
	}
536

537
	/*
538
	 * if (!was_skip_worktree && !ce_skip_worktree()) {
539
	 *	This is perfectly normal. Move on;
540
	 * }
541
	 */
542

543
	/*
544
	 * Merge strategies may set CE_UPDATE|CE_REMOVE outside checkout
545
	 * area as a result of ce_skip_worktree() shortcuts in
546
	 * verify_absent() and verify_uptodate().
547
	 * Make sure they don't modify worktree if they are already
548
	 * outside checkout area
549
	 */
550
	if (was_skip_worktree && ce_skip_worktree(ce)) {
551
		ce->ce_flags &= ~CE_UPDATE;
552

553
		/*
554
		 * By default, when CE_REMOVE is on, CE_WT_REMOVE is also
555
		 * on to get that file removed from both index and worktree.
556
		 * If that file is already outside worktree area, don't
557
		 * bother remove it.
558
		 */
559
		if (ce->ce_flags & CE_REMOVE)
560
			ce->ce_flags &= ~CE_WT_REMOVE;
561
	}
562

563
	if (!was_skip_worktree && ce_skip_worktree(ce)) {
564
		/*
565
		 * If CE_UPDATE is set, verify_uptodate() must be called already
566
		 * also stat info may have lost after merged_entry() so calling
567
		 * verify_uptodate() again may fail
568
		 */
569
		if (!(ce->ce_flags & CE_UPDATE) &&
570
		    verify_uptodate_sparse(ce, o)) {
571
			ce->ce_flags &= ~CE_SKIP_WORKTREE;
572
			return -1;
573
		}
574
		ce->ce_flags |= CE_WT_REMOVE;
575
		ce->ce_flags &= ~CE_UPDATE;
576
	}
577
	if (was_skip_worktree && !ce_skip_worktree(ce)) {
578
		if (verify_absent_sparse(ce, WARNING_SPARSE_ORPHANED_NOT_OVERWRITTEN, o))
579
			return -1;
580
		ce->ce_flags |= CE_UPDATE;
581
	}
582
	return 0;
583
}
584

585
static int warn_conflicted_path(struct index_state *istate,
586
				int i,
587
				struct unpack_trees_options *o)
588
{
589
	char *conflicting_path = istate->cache[i]->name;
590
	int count = 0;
591

592
	add_rejected_path(o, WARNING_SPARSE_UNMERGED_FILE, conflicting_path);
593

594
	/* Find out how many higher stage entries are at same path */
595
	while ((++count) + i < istate->cache_nr &&
596
	       !strcmp(conflicting_path, istate->cache[count + i]->name))
597
		; /* do nothing */
598

599
	return count;
600
}
601

602
static inline int call_unpack_fn(const struct cache_entry * const *src,
603
				 struct unpack_trees_options *o)
604
{
605
	int ret = o->fn(src, o);
606
	if (ret > 0)
607
		ret = 0;
608
	return ret;
609
}
610

611
static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)
612
{
613
	ce->ce_flags |= CE_UNPACKED;
614

615
	if (o->internal.cache_bottom < o->src_index->cache_nr &&
616
	    o->src_index->cache[o->internal.cache_bottom] == ce) {
617
		int bottom = o->internal.cache_bottom;
618

619
		while (bottom < o->src_index->cache_nr &&
620
		       o->src_index->cache[bottom]->ce_flags & CE_UNPACKED)
621
			bottom++;
622
		o->internal.cache_bottom = bottom;
623
	}
624
}
625

626
static void mark_all_ce_unused(struct index_state *index)
627
{
628
	int i;
629
	for (i = 0; i < index->cache_nr; i++)
630
		index->cache[i]->ce_flags &= ~(CE_UNPACKED | CE_ADDED | CE_NEW_SKIP_WORKTREE);
631
}
632

633
static int locate_in_src_index(const struct cache_entry *ce,
634
			       struct unpack_trees_options *o)
635
{
636
	struct index_state *index = o->src_index;
637
	int len = ce_namelen(ce);
638
	int pos = index_name_pos(index, ce->name, len);
639
	if (pos < 0)
640
		pos = -1 - pos;
641
	return pos;
642
}
643

644
/*
645
 * We call unpack_index_entry() with an unmerged cache entry
646
 * only in diff-index, and it wants a single callback.  Skip
647
 * the other unmerged entry with the same name.
648
 */
649
static void mark_ce_used_same_name(struct cache_entry *ce,
650
				   struct unpack_trees_options *o)
651
{
652
	struct index_state *index = o->src_index;
653
	int len = ce_namelen(ce);
654
	int pos;
655

656
	for (pos = locate_in_src_index(ce, o); pos < index->cache_nr; pos++) {
657
		struct cache_entry *next = index->cache[pos];
658
		if (len != ce_namelen(next) ||
659
		    memcmp(ce->name, next->name, len))
660
			break;
661
		mark_ce_used(next, o);
662
	}
663
}
664

665
static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)
666
{
667
	const struct index_state *index = o->src_index;
668
	int pos = o->internal.cache_bottom;
669

670
	while (pos < index->cache_nr) {
671
		struct cache_entry *ce = index->cache[pos];
672
		if (!(ce->ce_flags & CE_UNPACKED))
673
			return ce;
674
		pos++;
675
	}
676
	return NULL;
677
}
678

679
static void add_same_unmerged(const struct cache_entry *ce,
680
			      struct unpack_trees_options *o)
681
{
682
	struct index_state *index = o->src_index;
683
	int len = ce_namelen(ce);
684
	int pos = index_name_pos(index, ce->name, len);
685

686
	if (0 <= pos)
687
		die("programming error in a caller of mark_ce_used_same_name");
688
	for (pos = -pos - 1; pos < index->cache_nr; pos++) {
689
		struct cache_entry *next = index->cache[pos];
690
		if (len != ce_namelen(next) ||
691
		    memcmp(ce->name, next->name, len))
692
			break;
693
		add_entry(o, next, 0, 0);
694
		mark_ce_used(next, o);
695
	}
696
}
697

698
static int unpack_index_entry(struct cache_entry *ce,
699
			      struct unpack_trees_options *o)
700
{
701
	const struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
702
	int ret;
703

704
	src[0] = ce;
705

706
	mark_ce_used(ce, o);
707
	if (ce_stage(ce)) {
708
		if (o->skip_unmerged) {
709
			add_entry(o, ce, 0, 0);
710
			return 0;
711
		}
712
	}
713
	ret = call_unpack_fn(src, o);
714
	if (ce_stage(ce))
715
		mark_ce_used_same_name(ce, o);
716
	return ret;
717
}
718

719
static int find_cache_pos(struct traverse_info *, const char *p, size_t len);
720

721
static void restore_cache_bottom(struct traverse_info *info, int bottom)
722
{
723
	struct unpack_trees_options *o = info->data;
724

725
	if (o->diff_index_cached)
726
		return;
727
	o->internal.cache_bottom = bottom;
728
}
729

730
static int switch_cache_bottom(struct traverse_info *info)
731
{
732
	struct unpack_trees_options *o = info->data;
733
	int ret, pos;
734

735
	if (o->diff_index_cached)
736
		return 0;
737
	ret = o->internal.cache_bottom;
738
	pos = find_cache_pos(info->prev, info->name, info->namelen);
739

740
	if (pos < -1)
741
		o->internal.cache_bottom = -2 - pos;
742
	else if (pos < 0)
743
		o->internal.cache_bottom = o->src_index->cache_nr;
744
	return ret;
745
}
746

747
static inline int are_same_oid(struct name_entry *name_j, struct name_entry *name_k)
748
{
749
	return !is_null_oid(&name_j->oid) && !is_null_oid(&name_k->oid) && oideq(&name_j->oid, &name_k->oid);
750
}
751

752
static int all_trees_same_as_cache_tree(int n, unsigned long dirmask,
753
					struct name_entry *names,
754
					struct traverse_info *info)
755
{
756
	struct unpack_trees_options *o = info->data;
757
	int i;
758

759
	if (!o->merge || dirmask != ((1 << n) - 1))
760
		return 0;
761

762
	for (i = 1; i < n; i++)
763
		if (!are_same_oid(names, names + i))
764
			return 0;
765

766
	return cache_tree_matches_traversal(o->src_index->cache_tree, names, info);
767
}
768

769
static int index_pos_by_traverse_info(struct name_entry *names,
770
				      struct traverse_info *info)
771
{
772
	struct unpack_trees_options *o = info->data;
773
	struct strbuf name = STRBUF_INIT;
774
	int pos;
775

776
	strbuf_make_traverse_path(&name, info, names->path, names->pathlen);
777
	strbuf_addch(&name, '/');
778
	pos = index_name_pos(o->src_index, name.buf, name.len);
779
	if (pos >= 0) {
780
		if (!o->src_index->sparse_index ||
781
		    !(o->src_index->cache[pos]->ce_flags & CE_SKIP_WORKTREE))
782
			BUG("This is a directory and should not exist in index");
783
	} else {
784
		pos = -pos - 1;
785
	}
786
	if (pos >= o->src_index->cache_nr ||
787
	    !starts_with(o->src_index->cache[pos]->name, name.buf) ||
788
	    (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name.buf)))
789
		BUG("pos %d doesn't point to the first entry of %s in index",
790
		    pos, name.buf);
791
	strbuf_release(&name);
792
	return pos;
793
}
794

795
/*
796
 * Fast path if we detect that all trees are the same as cache-tree at this
797
 * path. We'll walk these trees in an iterative loop using cache-tree/index
798
 * instead of ODB since we already know what these trees contain.
799
 */
800
static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
801
				  struct traverse_info *info)
802
{
803
	struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
804
	struct unpack_trees_options *o = info->data;
805
	struct cache_entry *tree_ce = NULL;
806
	int ce_len = 0;
807
	int i, d;
808

809
	if (!o->merge)
810
		BUG("We need cache-tree to do this optimization");
811

812
	/*
813
	 * Do what unpack_callback() and unpack_single_entry() normally
814
	 * do. But we walk all paths in an iterative loop instead.
815
	 *
816
	 * D/F conflicts and higher stage entries are not a concern
817
	 * because cache-tree would be invalidated and we would never
818
	 * get here in the first place.
819
	 */
820
	for (i = 0; i < nr_entries; i++) {
821
		int new_ce_len, len, rc;
822

823
		src[0] = o->src_index->cache[pos + i];
824

825
		len = ce_namelen(src[0]);
826
		new_ce_len = cache_entry_size(len);
827

828
		if (new_ce_len > ce_len) {
829
			new_ce_len <<= 1;
830
			tree_ce = xrealloc(tree_ce, new_ce_len);
831
			memset(tree_ce, 0, new_ce_len);
832
			ce_len = new_ce_len;
833

834
			tree_ce->ce_flags = create_ce_flags(0);
835

836
			for (d = 1; d <= nr_names; d++)
837
				src[d] = tree_ce;
838
		}
839

840
		tree_ce->ce_mode = src[0]->ce_mode;
841
		tree_ce->ce_namelen = len;
842
		oidcpy(&tree_ce->oid, &src[0]->oid);
843
		memcpy(tree_ce->name, src[0]->name, len + 1);
844

845
		rc = call_unpack_fn((const struct cache_entry * const *)src, o);
846
		if (rc < 0) {
847
			free(tree_ce);
848
			return rc;
849
		}
850

851
		mark_ce_used(src[0], o);
852
	}
853
	free(tree_ce);
854
	if (o->internal.debug_unpack)
855
		printf("Unpacked %d entries from %s to %s using cache-tree\n",
856
		       nr_entries,
857
		       o->src_index->cache[pos]->name,
858
		       o->src_index->cache[pos + nr_entries - 1]->name);
859
	return 0;
860
}
861

862
static int traverse_trees_recursive(int n, unsigned long dirmask,
863
				    unsigned long df_conflicts,
864
				    struct name_entry *names,
865
				    struct traverse_info *info)
866
{
867
	struct unpack_trees_options *o = info->data;
868
	int i, ret, bottom;
869
	int nr_buf = 0;
870
	struct tree_desc *t;
871
	void **buf;
872
	struct traverse_info newinfo;
873
	struct name_entry *p;
874
	int nr_entries;
875

876
	nr_entries = all_trees_same_as_cache_tree(n, dirmask, names, info);
877
	if (nr_entries > 0) {
878
		int pos = index_pos_by_traverse_info(names, info);
879

880
		if (!o->merge || df_conflicts)
881
			BUG("Wrong condition to get here buddy");
882

883
		/*
884
		 * All entries up to 'pos' must have been processed
885
		 * (i.e. marked CE_UNPACKED) at this point. But to be safe,
886
		 * save and restore cache_bottom anyway to not miss
887
		 * unprocessed entries before 'pos'.
888
		 */
889
		bottom = o->internal.cache_bottom;
890
		ret = traverse_by_cache_tree(pos, nr_entries, n, info);
891
		o->internal.cache_bottom = bottom;
892
		return ret;
893
	}
894

895
	p = names;
896
	while (!p->mode)
897
		p++;
898

899
	newinfo = *info;
900
	newinfo.prev = info;
901
	newinfo.pathspec = info->pathspec;
902
	newinfo.name = p->path;
903
	newinfo.namelen = p->pathlen;
904
	newinfo.mode = p->mode;
905
	newinfo.pathlen = st_add3(newinfo.pathlen, tree_entry_len(p), 1);
906
	newinfo.df_conflicts |= df_conflicts;
907

908
	ALLOC_ARRAY(t, n);
909
	ALLOC_ARRAY(buf, n);
910

911
	/*
912
	 * Fetch the tree from the ODB for each peer directory in the
913
	 * n commits.
914
	 *
915
	 * For 2- and 3-way traversals, we try to avoid hitting the
916
	 * ODB twice for the same OID.  This should yield a nice speed
917
	 * up in checkouts and merges when the commits are similar.
918
	 *
919
	 * We don't bother doing the full O(n^2) search for larger n,
920
	 * because wider traversals don't happen that often and we
921
	 * avoid the search setup.
922
	 *
923
	 * When 2 peer OIDs are the same, we just copy the tree
924
	 * descriptor data.  This implicitly borrows the buffer
925
	 * data from the earlier cell.
926
	 */
927
	for (i = 0; i < n; i++, dirmask >>= 1) {
928
		if (i > 0 && are_same_oid(&names[i], &names[i - 1]))
929
			t[i] = t[i - 1];
930
		else if (i > 1 && are_same_oid(&names[i], &names[i - 2]))
931
			t[i] = t[i - 2];
932
		else {
933
			const struct object_id *oid = NULL;
934
			if (dirmask & 1)
935
				oid = &names[i].oid;
936
			buf[nr_buf++] = fill_tree_descriptor(the_repository, t + i, oid);
937
		}
938
	}
939

940
	bottom = switch_cache_bottom(&newinfo);
941
	ret = traverse_trees(o->src_index, n, t, &newinfo);
942
	restore_cache_bottom(&newinfo, bottom);
943

944
	for (i = 0; i < nr_buf; i++)
945
		free(buf[i]);
946
	free(buf);
947
	free(t);
948

949
	return ret;
950
}
951

952
/*
953
 * Compare the traverse-path to the cache entry without actually
954
 * having to generate the textual representation of the traverse
955
 * path.
956
 *
957
 * NOTE! This *only* compares up to the size of the traverse path
958
 * itself - the caller needs to do the final check for the cache
959
 * entry having more data at the end!
960
 */
961
static int do_compare_entry_piecewise(const struct cache_entry *ce,
962
				      const struct traverse_info *info,
963
				      const char *name, size_t namelen,
964
				      unsigned mode)
965
{
966
	int pathlen, ce_len;
967
	const char *ce_name;
968

969
	if (info->prev) {
970
		int cmp = do_compare_entry_piecewise(ce, info->prev,
971
						     info->name, info->namelen,
972
						     info->mode);
973
		if (cmp)
974
			return cmp;
975
	}
976
	pathlen = info->pathlen;
977
	ce_len = ce_namelen(ce);
978

979
	/* If ce_len < pathlen then we must have previously hit "name == directory" entry */
980
	if (ce_len < pathlen)
981
		return -1;
982

983
	ce_len -= pathlen;
984
	ce_name = ce->name + pathlen;
985

986
	return df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);
987
}
988

989
static int do_compare_entry(const struct cache_entry *ce,
990
			    const struct traverse_info *info,
991
			    const char *name, size_t namelen,
992
			    unsigned mode)
993
{
994
	int pathlen, ce_len;
995
	const char *ce_name;
996
	int cmp;
997
	unsigned ce_mode;
998

999
	/*
1000
	 * If we have not precomputed the traverse path, it is quicker
1001
	 * to avoid doing so.  But if we have precomputed it,
1002
	 * it is quicker to use the precomputed version.
1003
	 */
1004
	if (!info->traverse_path)
1005
		return do_compare_entry_piecewise(ce, info, name, namelen, mode);
1006

1007
	cmp = strncmp(ce->name, info->traverse_path, info->pathlen);
1008
	if (cmp)
1009
		return cmp;
1010

1011
	pathlen = info->pathlen;
1012
	ce_len = ce_namelen(ce);
1013

1014
	if (ce_len < pathlen)
1015
		return -1;
1016

1017
	ce_len -= pathlen;
1018
	ce_name = ce->name + pathlen;
1019

1020
	ce_mode = S_ISSPARSEDIR(ce->ce_mode) ? S_IFDIR : S_IFREG;
1021
	return df_name_compare(ce_name, ce_len, ce_mode, name, namelen, mode);
1022
}
1023

1024
static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
1025
{
1026
	int cmp = do_compare_entry(ce, info, n->path, n->pathlen, n->mode);
1027
	if (cmp)
1028
		return cmp;
1029

1030
	/*
1031
	 * At this point, we know that we have a prefix match. If ce
1032
	 * is a sparse directory, then allow an exact match. This only
1033
	 * works when the input name is a directory, since ce->name
1034
	 * ends in a directory separator.
1035
	 */
1036
	if (S_ISSPARSEDIR(ce->ce_mode) &&
1037
	    ce->ce_namelen == traverse_path_len(info, tree_entry_len(n)) + 1)
1038
		return 0;
1039

1040
	/*
1041
	 * Even if the beginning compared identically, the ce should
1042
	 * compare as bigger than a directory leading up to it!
1043
	 */
1044
	return ce_namelen(ce) > traverse_path_len(info, tree_entry_len(n));
1045
}
1046

1047
static int ce_in_traverse_path(const struct cache_entry *ce,
1048
			       const struct traverse_info *info)
1049
{
1050
	if (!info->prev)
1051
		return 1;
1052
	if (do_compare_entry(ce, info->prev,
1053
			     info->name, info->namelen, info->mode))
1054
		return 0;
1055
	/*
1056
	 * If ce (blob) is the same name as the path (which is a tree
1057
	 * we will be descending into), it won't be inside it.
1058
	 */
1059
	return (info->pathlen < ce_namelen(ce));
1060
}
1061

1062
static struct cache_entry *create_ce_entry(const struct traverse_info *info,
1063
	const struct name_entry *n,
1064
	int stage,
1065
	struct index_state *istate,
1066
	int is_transient,
1067
	int is_sparse_directory)
1068
{
1069
	size_t len = traverse_path_len(info, tree_entry_len(n));
1070
	size_t alloc_len = is_sparse_directory ? len + 1 : len;
1071
	struct cache_entry *ce =
1072
		is_transient ?
1073
		make_empty_transient_cache_entry(alloc_len, NULL) :
1074
		make_empty_cache_entry(istate, alloc_len);
1075

1076
	ce->ce_mode = create_ce_mode(n->mode);
1077
	ce->ce_flags = create_ce_flags(stage);
1078
	ce->ce_namelen = len;
1079
	oidcpy(&ce->oid, &n->oid);
1080
	/* len+1 because the cache_entry allocates space for NUL */
1081
	make_traverse_path(ce->name, len + 1, info, n->path, n->pathlen);
1082

1083
	if (is_sparse_directory) {
1084
		ce->name[len] = '/';
1085
		ce->name[len + 1] = '\0';
1086
		ce->ce_namelen++;
1087
		ce->ce_flags |= CE_SKIP_WORKTREE;
1088
	}
1089

1090
	return ce;
1091
}
1092

1093
/*
1094
 * Determine whether the path specified by 'p' should be unpacked as a new
1095
 * sparse directory in a sparse index. A new sparse directory 'A/':
1096
 * - must be outside the sparse cone.
1097
 * - must not already be in the index (i.e., no index entry with name 'A/'
1098
 *   exists).
1099
 * - must not have any child entries in the index (i.e., no index entry
1100
 *   'A/<something>' exists).
1101
 * If 'p' meets the above requirements, return 1; otherwise, return 0.
1102
 */
1103
static int entry_is_new_sparse_dir(const struct traverse_info *info,
1104
				   const struct name_entry *p)
1105
{
1106
	int res, pos;
1107
	struct strbuf dirpath = STRBUF_INIT;
1108
	struct unpack_trees_options *o = info->data;
1109

1110
	if (!S_ISDIR(p->mode))
1111
		return 0;
1112

1113
	/*
1114
	 * If the path is inside the sparse cone, it can't be a sparse directory.
1115
	 */
1116
	strbuf_add(&dirpath, info->traverse_path, info->pathlen);
1117
	strbuf_add(&dirpath, p->path, p->pathlen);
1118
	strbuf_addch(&dirpath, '/');
1119
	if (path_in_cone_mode_sparse_checkout(dirpath.buf, o->src_index)) {
1120
		res = 0;
1121
		goto cleanup;
1122
	}
1123

1124
	pos = index_name_pos_sparse(o->src_index, dirpath.buf, dirpath.len);
1125
	if (pos >= 0) {
1126
		/* Path is already in the index, not a new sparse dir */
1127
		res = 0;
1128
		goto cleanup;
1129
	}
1130

1131
	/* Where would this sparse dir be inserted into the index? */
1132
	pos = -pos - 1;
1133
	if (pos >= o->src_index->cache_nr) {
1134
		/*
1135
		 * Sparse dir would be inserted at the end of the index, so we
1136
		 * know it has no child entries.
1137
		 */
1138
		res = 1;
1139
		goto cleanup;
1140
	}
1141

1142
	/*
1143
	 * If the dir has child entries in the index, the first would be at the
1144
	 * position the sparse directory would be inserted. If the entry at this
1145
	 * position is inside the dir, not a new sparse dir.
1146
	 */
1147
	res = strncmp(o->src_index->cache[pos]->name, dirpath.buf, dirpath.len);
1148

1149
cleanup:
1150
	strbuf_release(&dirpath);
1151
	return res;
1152
}
1153

1154
/*
1155
 * Note that traverse_by_cache_tree() duplicates some logic in this function
1156
 * without actually calling it. If you change the logic here you may need to
1157
 * check and change there as well.
1158
 */
1159
static int unpack_single_entry(int n, unsigned long mask,
1160
			       unsigned long dirmask,
1161
			       struct cache_entry **src,
1162
			       const struct name_entry *names,
1163
			       const struct traverse_info *info,
1164
			       int *is_new_sparse_dir)
1165
{
1166
	int i;
1167
	struct unpack_trees_options *o = info->data;
1168
	unsigned long conflicts = info->df_conflicts | dirmask;
1169
	const struct name_entry *p = names;
1170

1171
	*is_new_sparse_dir = 0;
1172
	if (mask == dirmask && !src[0]) {
1173
		/*
1174
		 * If we're not in a sparse index, we can't unpack a directory
1175
		 * without recursing into it, so we return.
1176
		 */
1177
		if (!o->src_index->sparse_index)
1178
			return 0;
1179

1180
		/* Find first entry with a real name (we could use "mask" too) */
1181
		while (!p->mode)
1182
			p++;
1183

1184
		/*
1185
		 * If the directory is completely missing from the index but
1186
		 * would otherwise be a sparse directory, we should unpack it.
1187
		 * If not, we'll return and continue recursively traversing the
1188
		 * tree.
1189
		 */
1190
		*is_new_sparse_dir = entry_is_new_sparse_dir(info, p);
1191
		if (!*is_new_sparse_dir)
1192
			return 0;
1193
	}
1194

1195
	/*
1196
	 * When we are unpacking a sparse directory, then this isn't necessarily
1197
	 * a directory-file conflict.
1198
	 */
1199
	if (mask == dirmask &&
1200
	    (*is_new_sparse_dir || (src[0] && S_ISSPARSEDIR(src[0]->ce_mode))))
1201
		conflicts = 0;
1202

1203
	/*
1204
	 * Ok, we've filled in up to any potential index entry in src[0],
1205
	 * now do the rest.
1206
	 */
1207
	for (i = 0; i < n; i++) {
1208
		int stage;
1209
		unsigned int bit = 1ul << i;
1210
		if (conflicts & bit) {
1211
			src[i + o->merge] = o->df_conflict_entry;
1212
			continue;
1213
		}
1214
		if (!(mask & bit))
1215
			continue;
1216
		if (!o->merge)
1217
			stage = 0;
1218
		else if (i + 1 < o->head_idx)
1219
			stage = 1;
1220
		else if (i + 1 > o->head_idx)
1221
			stage = 3;
1222
		else
1223
			stage = 2;
1224

1225
		/*
1226
		 * If the merge bit is set, then the cache entries are
1227
		 * discarded in the following block.  In this case,
1228
		 * construct "transient" cache_entries, as they are
1229
		 * not stored in the index.  otherwise construct the
1230
		 * cache entry from the index aware logic.
1231
		 */
1232
		src[i + o->merge] = create_ce_entry(info, names + i, stage,
1233
						    &o->internal.result,
1234
						    o->merge, bit & dirmask);
1235
	}
1236

1237
	if (o->merge) {
1238
		int rc = call_unpack_fn((const struct cache_entry * const *)src,
1239
					o);
1240
		for (i = 0; i < n; i++) {
1241
			struct cache_entry *ce = src[i + o->merge];
1242
			if (ce != o->df_conflict_entry)
1243
				discard_cache_entry(ce);
1244
		}
1245
		return rc;
1246
	}
1247

1248
	for (i = 0; i < n; i++)
1249
		if (src[i] && src[i] != o->df_conflict_entry)
1250
			if (do_add_entry(o, src[i], 0, 0))
1251
				return -1;
1252

1253
	return 0;
1254
}
1255

1256
static int unpack_failed(struct unpack_trees_options *o, const char *message)
1257
{
1258
	discard_index(&o->internal.result);
1259
	if (!o->quiet && !o->exiting_early) {
1260
		if (message)
1261
			return error("%s", message);
1262
		return -1;
1263
	}
1264
	return -1;
1265
}
1266

1267
/*
1268
 * The tree traversal is looking at name p.  If we have a matching entry,
1269
 * return it.  If name p is a directory in the index, do not return
1270
 * anything, as we will want to match it when the traversal descends into
1271
 * the directory.
1272
 */
1273
static int find_cache_pos(struct traverse_info *info,
1274
			  const char *p, size_t p_len)
1275
{
1276
	int pos;
1277
	struct unpack_trees_options *o = info->data;
1278
	struct index_state *index = o->src_index;
1279
	int pfxlen = info->pathlen;
1280

1281
	for (pos = o->internal.cache_bottom; pos < index->cache_nr; pos++) {
1282
		const struct cache_entry *ce = index->cache[pos];
1283
		const char *ce_name, *ce_slash;
1284
		int cmp, ce_len;
1285

1286
		if (ce->ce_flags & CE_UNPACKED) {
1287
			/*
1288
			 * cache_bottom entry is already unpacked, so
1289
			 * we can never match it; don't check it
1290
			 * again.
1291
			 */
1292
			if (pos == o->internal.cache_bottom)
1293
				++o->internal.cache_bottom;
1294
			continue;
1295
		}
1296
		if (!ce_in_traverse_path(ce, info)) {
1297
			/*
1298
			 * Check if we can skip future cache checks
1299
			 * (because we're already past all possible
1300
			 * entries in the traverse path).
1301
			 */
1302
			if (info->traverse_path) {
1303
				if (strncmp(ce->name, info->traverse_path,
1304
					    info->pathlen) > 0)
1305
					break;
1306
			}
1307
			continue;
1308
		}
1309
		ce_name = ce->name + pfxlen;
1310
		ce_slash = strchr(ce_name, '/');
1311
		if (ce_slash)
1312
			ce_len = ce_slash - ce_name;
1313
		else
1314
			ce_len = ce_namelen(ce) - pfxlen;
1315
		cmp = name_compare(p, p_len, ce_name, ce_len);
1316
		/*
1317
		 * Exact match; if we have a directory we need to
1318
		 * delay returning it.
1319
		 */
1320
		if (!cmp)
1321
			return ce_slash ? -2 - pos : pos;
1322
		if (0 < cmp)
1323
			continue; /* keep looking */
1324
		/*
1325
		 * ce_name sorts after p->path; could it be that we
1326
		 * have files under p->path directory in the index?
1327
		 * E.g.  ce_name == "t-i", and p->path == "t"; we may
1328
		 * have "t/a" in the index.
1329
		 */
1330
		if (p_len < ce_len && !memcmp(ce_name, p, p_len) &&
1331
		    ce_name[p_len] < '/')
1332
			continue; /* keep looking */
1333
		break;
1334
	}
1335
	return -1;
1336
}
1337

1338
/*
1339
 * Given a sparse directory entry 'ce', compare ce->name to
1340
 * info->traverse_path + p->path + '/' if info->traverse_path
1341
 * is non-empty.
1342
 *
1343
 * Compare ce->name to p->path + '/' otherwise. Note that
1344
 * ce->name must end in a trailing '/' because it is a sparse
1345
 * directory entry.
1346
 */
1347
static int sparse_dir_matches_path(const struct cache_entry *ce,
1348
				   struct traverse_info *info,
1349
				   const struct name_entry *p)
1350
{
1351
	assert(S_ISSPARSEDIR(ce->ce_mode));
1352
	assert(ce->name[ce->ce_namelen - 1] == '/');
1353

1354
	if (info->pathlen)
1355
		return ce->ce_namelen == info->pathlen + p->pathlen + 1 &&
1356
		       ce->name[info->pathlen - 1] == '/' &&
1357
		       !strncmp(ce->name, info->traverse_path, info->pathlen) &&
1358
		       !strncmp(ce->name + info->pathlen, p->path, p->pathlen);
1359
	return ce->ce_namelen == p->pathlen + 1 &&
1360
	       !strncmp(ce->name, p->path, p->pathlen);
1361
}
1362

1363
static struct cache_entry *find_cache_entry(struct traverse_info *info,
1364
					    const struct name_entry *p)
1365
{
1366
	const char *path;
1367
	int pos = find_cache_pos(info, p->path, p->pathlen);
1368
	struct unpack_trees_options *o = info->data;
1369

1370
	if (0 <= pos)
1371
		return o->src_index->cache[pos];
1372

1373
	/*
1374
	 * Check for a sparse-directory entry named "path/".
1375
	 * Due to the input p->path not having a trailing
1376
	 * slash, the negative 'pos' value overshoots the
1377
	 * expected position, hence "-2" instead of "-1".
1378
	 */
1379
	pos = -pos - 2;
1380

1381
	if (pos < 0 || pos >= o->src_index->cache_nr)
1382
		return NULL;
1383

1384
	/*
1385
	 * Due to lexicographic sorting and sparse directory
1386
	 * entries ending with a trailing slash, our path as a
1387
	 * sparse directory (e.g "subdir/") and	our path as a
1388
	 * file (e.g. "subdir") might be separated by other
1389
	 * paths (e.g. "subdir-").
1390
	 */
1391
	while (pos >= 0) {
1392
		struct cache_entry *ce = o->src_index->cache[pos];
1393

1394
		if (!skip_prefix(ce->name, info->traverse_path, &path) ||
1395
		    strncmp(path, p->path, p->pathlen) ||
1396
		    path[p->pathlen] != '/')
1397
			return NULL;
1398

1399
		if (S_ISSPARSEDIR(ce->ce_mode) &&
1400
		    sparse_dir_matches_path(ce, info, p))
1401
			return ce;
1402

1403
		pos--;
1404
	}
1405

1406
	return NULL;
1407
}
1408

1409
static void debug_path(struct traverse_info *info)
1410
{
1411
	if (info->prev) {
1412
		debug_path(info->prev);
1413
		if (*info->prev->name)
1414
			putchar('/');
1415
	}
1416
	printf("%s", info->name);
1417
}
1418

1419
static void debug_name_entry(int i, struct name_entry *n)
1420
{
1421
	printf("ent#%d %06o %s\n", i,
1422
	       n->path ? n->mode : 0,
1423
	       n->path ? n->path : "(missing)");
1424
}
1425

1426
static void debug_unpack_callback(int n,
1427
				  unsigned long mask,
1428
				  unsigned long dirmask,
1429
				  struct name_entry *names,
1430
				  struct traverse_info *info)
1431
{
1432
	int i;
1433
	printf("* unpack mask %lu, dirmask %lu, cnt %d ",
1434
	       mask, dirmask, n);
1435
	debug_path(info);
1436
	putchar('\n');
1437
	for (i = 0; i < n; i++)
1438
		debug_name_entry(i, names + i);
1439
}
1440

1441
/*
1442
 * Returns true if and only if the given cache_entry is a
1443
 * sparse-directory entry that matches the given name_entry
1444
 * from the tree walk at the given traverse_info.
1445
 */
1446
static int is_sparse_directory_entry(struct cache_entry *ce,
1447
				     const struct name_entry *name,
1448
				     struct traverse_info *info)
1449
{
1450
	if (!ce || !name || !S_ISSPARSEDIR(ce->ce_mode))
1451
		return 0;
1452

1453
	return sparse_dir_matches_path(ce, info, name);
1454
}
1455

1456
static int unpack_sparse_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
1457
{
1458
	struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
1459
	struct unpack_trees_options *o = info->data;
1460
	int ret, is_new_sparse_dir;
1461

1462
	assert(o->merge);
1463

1464
	/*
1465
	 * Unlike in 'unpack_callback', where src[0] is derived from the index when
1466
	 * merging, src[0] is a transient cache entry derived from the first tree
1467
	 * provided. Create the temporary entry as if it came from a non-sparse index.
1468
	 */
1469
	if (!is_null_oid(&names[0].oid)) {
1470
		src[0] = create_ce_entry(info, &names[0], 0,
1471
					&o->internal.result, 1,
1472
					dirmask & (1ul << 0));
1473
		src[0]->ce_flags |= (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
1474
	}
1475

1476
	/*
1477
	 * 'unpack_single_entry' assumes that src[0] is derived directly from
1478
	 * the index, rather than from an entry in 'names'. This is *not* true when
1479
	 * merging a sparse directory, in which case names[0] is the "index" source
1480
	 * entry. To match the expectations of 'unpack_single_entry', shift past the
1481
	 * "index" tree (i.e., names[0]) and adjust 'names', 'n', 'mask', and
1482
	 * 'dirmask' accordingly.
1483
	 */
1484
	ret = unpack_single_entry(n - 1, mask >> 1, dirmask >> 1, src, names + 1, info, &is_new_sparse_dir);
1485

1486
	if (src[0])
1487
		discard_cache_entry(src[0]);
1488

1489
	return ret >= 0 ? mask : -1;
1490
}
1491

1492
/*
1493
 * Note that traverse_by_cache_tree() duplicates some logic in this function
1494
 * without actually calling it. If you change the logic here you may need to
1495
 * check and change there as well.
1496
 */
1497
static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
1498
{
1499
	struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
1500
	struct unpack_trees_options *o = info->data;
1501
	const struct name_entry *p = names;
1502
	int is_new_sparse_dir;
1503

1504
	/* Find first entry with a real name (we could use "mask" too) */
1505
	while (!p->mode)
1506
		p++;
1507

1508
	if (o->internal.debug_unpack)
1509
		debug_unpack_callback(n, mask, dirmask, names, info);
1510

1511
	/* Are we supposed to look at the index too? */
1512
	if (o->merge) {
1513
		while (1) {
1514
			int cmp;
1515
			struct cache_entry *ce;
1516

1517
			if (o->diff_index_cached)
1518
				ce = next_cache_entry(o);
1519
			else
1520
				ce = find_cache_entry(info, p);
1521

1522
			if (!ce)
1523
				break;
1524
			cmp = compare_entry(ce, info, p);
1525
			if (cmp < 0) {
1526
				if (unpack_index_entry(ce, o) < 0)
1527
					return unpack_failed(o, NULL);
1528
				continue;
1529
			}
1530
			if (!cmp) {
1531
				if (ce_stage(ce)) {
1532
					/*
1533
					 * If we skip unmerged index
1534
					 * entries, we'll skip this
1535
					 * entry *and* the tree
1536
					 * entries associated with it!
1537
					 */
1538
					if (o->skip_unmerged) {
1539
						add_same_unmerged(ce, o);
1540
						return mask;
1541
					}
1542
				}
1543
				src[0] = ce;
1544
			}
1545
			break;
1546
		}
1547
	}
1548

1549
	if (unpack_single_entry(n, mask, dirmask, src, names, info, &is_new_sparse_dir))
1550
		return -1;
1551

1552
	if (o->merge && src[0]) {
1553
		if (ce_stage(src[0]))
1554
			mark_ce_used_same_name(src[0], o);
1555
		else
1556
			mark_ce_used(src[0], o);
1557
	}
1558

1559
	/* Now handle any directories.. */
1560
	if (dirmask) {
1561
		/* special case: "diff-index --cached" looking at a tree */
1562
		if (o->diff_index_cached &&
1563
		    n == 1 && dirmask == 1 && S_ISDIR(names->mode)) {
1564
			int matches;
1565
			matches = cache_tree_matches_traversal(o->src_index->cache_tree,
1566
							       names, info);
1567
			/*
1568
			 * Everything under the name matches; skip the
1569
			 * entire hierarchy.  diff_index_cached codepath
1570
			 * special cases D/F conflicts in such a way that
1571
			 * it does not do any look-ahead, so this is safe.
1572
			 */
1573
			if (matches) {
1574
				/*
1575
				 * Only increment the cache_bottom if the
1576
				 * directory isn't a sparse directory index
1577
				 * entry (if it is, it was already incremented)
1578
				 * in 'mark_ce_used()'
1579
				 */
1580
				if (!src[0] || !S_ISSPARSEDIR(src[0]->ce_mode))
1581
					o->internal.cache_bottom += matches;
1582
				return mask;
1583
			}
1584
		}
1585

1586
		if (!is_sparse_directory_entry(src[0], p, info) &&
1587
		    !is_new_sparse_dir &&
1588
		    traverse_trees_recursive(n, dirmask, mask & ~dirmask,
1589
						    names, info) < 0) {
1590
			return -1;
1591
		}
1592

1593
		return mask;
1594
	}
1595

1596
	return mask;
1597
}
1598

1599
static int clear_ce_flags_1(struct index_state *istate,
1600
			    struct cache_entry **cache, int nr,
1601
			    struct strbuf *prefix,
1602
			    int select_mask, int clear_mask,
1603
			    struct pattern_list *pl,
1604
			    enum pattern_match_result default_match,
1605
			    int progress_nr);
1606

1607
/* Whole directory matching */
1608
static int clear_ce_flags_dir(struct index_state *istate,
1609
			      struct cache_entry **cache, int nr,
1610
			      struct strbuf *prefix,
1611
			      char *basename,
1612
			      int select_mask, int clear_mask,
1613
			      struct pattern_list *pl,
1614
			      enum pattern_match_result default_match,
1615
			      int progress_nr)
1616
{
1617
	struct cache_entry **cache_end;
1618
	int dtype = DT_DIR;
1619
	int rc;
1620
	enum pattern_match_result ret, orig_ret;
1621
	orig_ret = path_matches_pattern_list(prefix->buf, prefix->len,
1622
					     basename, &dtype, pl, istate);
1623

1624
	strbuf_addch(prefix, '/');
1625

1626
	/* If undecided, use matching result of parent dir in defval */
1627
	if (orig_ret == UNDECIDED)
1628
		ret = default_match;
1629
	else
1630
		ret = orig_ret;
1631

1632
	for (cache_end = cache; cache_end != cache + nr; cache_end++) {
1633
		struct cache_entry *ce = *cache_end;
1634
		if (strncmp(ce->name, prefix->buf, prefix->len))
1635
			break;
1636
	}
1637

1638
	if (pl->use_cone_patterns && orig_ret == MATCHED_RECURSIVE) {
1639
		struct cache_entry **ce = cache;
1640
		rc = cache_end - cache;
1641

1642
		while (ce < cache_end) {
1643
			(*ce)->ce_flags &= ~clear_mask;
1644
			ce++;
1645
		}
1646
	} else if (pl->use_cone_patterns && orig_ret == NOT_MATCHED) {
1647
		rc = cache_end - cache;
1648
	} else {
1649
		rc = clear_ce_flags_1(istate, cache, cache_end - cache,
1650
				      prefix,
1651
				      select_mask, clear_mask,
1652
				      pl, ret,
1653
				      progress_nr);
1654
	}
1655

1656
	strbuf_setlen(prefix, prefix->len - 1);
1657
	return rc;
1658
}
1659

1660
/*
1661
 * Traverse the index, find every entry that matches according to
1662
 * o->pl. Do "ce_flags &= ~clear_mask" on those entries. Return the
1663
 * number of traversed entries.
1664
 *
1665
 * If select_mask is non-zero, only entries whose ce_flags has on of
1666
 * those bits enabled are traversed.
1667
 *
1668
 * cache	: pointer to an index entry
1669
 * prefix_len	: an offset to its path
1670
 *
1671
 * The current path ("prefix") including the trailing '/' is
1672
 *   cache[0]->name[0..(prefix_len-1)]
1673
 * Top level path has prefix_len zero.
1674
 */
1675
static int clear_ce_flags_1(struct index_state *istate,
1676
			    struct cache_entry **cache, int nr,
1677
			    struct strbuf *prefix,
1678
			    int select_mask, int clear_mask,
1679
			    struct pattern_list *pl,
1680
			    enum pattern_match_result default_match,
1681
			    int progress_nr)
1682
{
1683
	struct cache_entry **cache_end = nr ? cache + nr : cache;
1684

1685
	/*
1686
	 * Process all entries that have the given prefix and meet
1687
	 * select_mask condition
1688
	 */
1689
	while(cache != cache_end) {
1690
		struct cache_entry *ce = *cache;
1691
		const char *name, *slash;
1692
		int len, dtype;
1693
		enum pattern_match_result ret;
1694

1695
		display_progress(istate->progress, progress_nr);
1696

1697
		if (select_mask && !(ce->ce_flags & select_mask)) {
1698
			cache++;
1699
			progress_nr++;
1700
			continue;
1701
		}
1702

1703
		if (prefix->len && strncmp(ce->name, prefix->buf, prefix->len))
1704
			break;
1705

1706
		name = ce->name + prefix->len;
1707
		slash = strchr(name, '/');
1708

1709
		/* If it's a directory, try whole directory match first */
1710
		if (slash) {
1711
			int processed;
1712

1713
			len = slash - name;
1714
			strbuf_add(prefix, name, len);
1715

1716
			processed = clear_ce_flags_dir(istate, cache, cache_end - cache,
1717
						       prefix,
1718
						       prefix->buf + prefix->len - len,
1719
						       select_mask, clear_mask,
1720
						       pl, default_match,
1721
						       progress_nr);
1722

1723
			/* clear_c_f_dir eats a whole dir already? */
1724
			if (processed) {
1725
				cache += processed;
1726
				progress_nr += processed;
1727
				strbuf_setlen(prefix, prefix->len - len);
1728
				continue;
1729
			}
1730

1731
			strbuf_addch(prefix, '/');
1732
			processed = clear_ce_flags_1(istate, cache, cache_end - cache,
1733
						     prefix,
1734
						     select_mask, clear_mask, pl,
1735
						     default_match, progress_nr);
1736

1737
			cache += processed;
1738
			progress_nr += processed;
1739

1740
			strbuf_setlen(prefix, prefix->len - len - 1);
1741
			continue;
1742
		}
1743

1744
		/* Non-directory */
1745
		dtype = ce_to_dtype(ce);
1746
		ret = path_matches_pattern_list(ce->name,
1747
						ce_namelen(ce),
1748
						name, &dtype, pl, istate);
1749
		if (ret == UNDECIDED)
1750
			ret = default_match;
1751
		if (ret == MATCHED || ret == MATCHED_RECURSIVE)
1752
			ce->ce_flags &= ~clear_mask;
1753
		cache++;
1754
		progress_nr++;
1755
	}
1756

1757
	display_progress(istate->progress, progress_nr);
1758
	return nr - (cache_end - cache);
1759
}
1760

1761
static int clear_ce_flags(struct index_state *istate,
1762
			  int select_mask, int clear_mask,
1763
			  struct pattern_list *pl,
1764
			  int show_progress)
1765
{
1766
	static struct strbuf prefix = STRBUF_INIT;
1767
	char label[100];
1768
	int rval;
1769

1770
	strbuf_reset(&prefix);
1771
	if (show_progress)
1772
		istate->progress = start_delayed_progress(
1773
					_("Updating index flags"),
1774
					istate->cache_nr);
1775

1776
	xsnprintf(label, sizeof(label), "clear_ce_flags(0x%08lx,0x%08lx)",
1777
		  (unsigned long)select_mask, (unsigned long)clear_mask);
1778
	trace2_region_enter("unpack_trees", label, the_repository);
1779
	rval = clear_ce_flags_1(istate,
1780
				istate->cache,
1781
				istate->cache_nr,
1782
				&prefix,
1783
				select_mask, clear_mask,
1784
				pl, 0, 0);
1785
	trace2_region_leave("unpack_trees", label, the_repository);
1786

1787
	stop_progress(&istate->progress);
1788
	return rval;
1789
}
1790

1791
/*
1792
 * Set/Clear CE_NEW_SKIP_WORKTREE according to $GIT_DIR/info/sparse-checkout
1793
 */
1794
static void mark_new_skip_worktree(struct pattern_list *pl,
1795
				   struct index_state *istate,
1796
				   int select_flag, int skip_wt_flag,
1797
				   int show_progress)
1798
{
1799
	int i;
1800

1801
	/*
1802
	 * 1. Pretend the narrowest worktree: only unmerged entries
1803
	 * are checked out
1804
	 */
1805
	for (i = 0; i < istate->cache_nr; i++) {
1806
		struct cache_entry *ce = istate->cache[i];
1807

1808
		if (select_flag && !(ce->ce_flags & select_flag))
1809
			continue;
1810

1811
		if (!ce_stage(ce) && !(ce->ce_flags & CE_CONFLICTED))
1812
			ce->ce_flags |= skip_wt_flag;
1813
		else
1814
			ce->ce_flags &= ~skip_wt_flag;
1815
	}
1816

1817
	/*
1818
	 * 2. Widen worktree according to sparse-checkout file.
1819
	 * Matched entries will have skip_wt_flag cleared (i.e. "in")
1820
	 */
1821
	clear_ce_flags(istate, select_flag, skip_wt_flag, pl, show_progress);
1822
}
1823

1824
static void populate_from_existing_patterns(struct unpack_trees_options *o,
1825
					    struct pattern_list *pl)
1826
{
1827
	if (get_sparse_checkout_patterns(pl) < 0)
1828
		o->skip_sparse_checkout = 1;
1829
	else
1830
		o->internal.pl = pl;
1831
}
1832

1833
static void update_sparsity_for_prefix(const char *prefix,
1834
				       struct index_state *istate)
1835
{
1836
	int prefix_len = strlen(prefix);
1837
	struct strbuf ce_prefix = STRBUF_INIT;
1838

1839
	if (!istate->sparse_index)
1840
		return;
1841

1842
	while (prefix_len > 0 && prefix[prefix_len - 1] == '/')
1843
		prefix_len--;
1844

1845
	if (prefix_len <= 0)
1846
		BUG("Invalid prefix passed to update_sparsity_for_prefix");
1847

1848
	strbuf_grow(&ce_prefix, prefix_len + 1);
1849
	strbuf_add(&ce_prefix, prefix, prefix_len);
1850
	strbuf_addch(&ce_prefix, '/');
1851

1852
	/*
1853
	 * If the prefix points to a sparse directory or a path inside a sparse
1854
	 * directory, the index should be expanded. This is accomplished in one
1855
	 * of two ways:
1856
	 * - if the prefix is inside a sparse directory, it will be expanded by
1857
	 *   the 'ensure_full_index(...)' call in 'index_name_pos(...)'.
1858
	 * - if the prefix matches an existing sparse directory entry,
1859
	 *   'index_name_pos(...)' will return its index position, triggering
1860
	 *   the 'ensure_full_index(...)' below.
1861
	 */
1862
	if (!path_in_cone_mode_sparse_checkout(ce_prefix.buf, istate) &&
1863
	    index_name_pos(istate, ce_prefix.buf, ce_prefix.len) >= 0)
1864
		ensure_full_index(istate);
1865

1866
	strbuf_release(&ce_prefix);
1867
}
1868

1869
static int verify_absent(const struct cache_entry *,
1870
			 enum unpack_trees_error_types,
1871
			 struct unpack_trees_options *);
1872
/*
1873
 * N-way merge "len" trees.  Returns 0 on success, -1 on failure to manipulate the
1874
 * resulting index, -2 on failure to reflect the changes to the work tree.
1875
 *
1876
 * CE_ADDED, CE_UNPACKED and CE_NEW_SKIP_WORKTREE are used internally
1877
 */
1878
int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
1879
{
1880
	struct repository *repo = the_repository;
1881
	int i, ret;
1882
	static struct cache_entry *dfc;
1883
	struct pattern_list pl;
1884
	int free_pattern_list = 0;
1885
	struct dir_struct dir = DIR_INIT;
1886

1887
	if (o->reset == UNPACK_RESET_INVALID)
1888
		BUG("o->reset had a value of 1; should be UNPACK_TREES_*_UNTRACKED");
1889

1890
	if (len > MAX_UNPACK_TREES)
1891
		die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES);
1892
	if (o->internal.dir)
1893
		BUG("o->internal.dir is for internal use only");
1894
	if (o->internal.pl)
1895
		BUG("o->internal.pl is for internal use only");
1896
	if (o->df_conflict_entry)
1897
		BUG("o->df_conflict_entry is an output only field");
1898

1899
	trace_performance_enter();
1900
	trace2_region_enter("unpack_trees", "unpack_trees", the_repository);
1901

1902
	prepare_repo_settings(repo);
1903
	if (repo->settings.command_requires_full_index) {
1904
		ensure_full_index(o->src_index);
1905
		if (o->dst_index)
1906
			ensure_full_index(o->dst_index);
1907
	}
1908

1909
	if (o->reset == UNPACK_RESET_OVERWRITE_UNTRACKED &&
1910
	    o->preserve_ignored)
1911
		BUG("UNPACK_RESET_OVERWRITE_UNTRACKED incompatible with preserved ignored files");
1912

1913
	if (!o->preserve_ignored) {
1914
		o->internal.dir = &dir;
1915
		o->internal.dir->flags |= DIR_SHOW_IGNORED;
1916
		setup_standard_excludes(o->internal.dir);
1917
	}
1918

1919
	if (o->prefix)
1920
		update_sparsity_for_prefix(o->prefix, o->src_index);
1921

1922
	if (!core_apply_sparse_checkout || !o->update)
1923
		o->skip_sparse_checkout = 1;
1924
	if (!o->skip_sparse_checkout) {
1925
		memset(&pl, 0, sizeof(pl));
1926
		free_pattern_list = 1;
1927
		populate_from_existing_patterns(o, &pl);
1928
	}
1929

1930
	index_state_init(&o->internal.result, o->src_index->repo);
1931
	o->internal.result.initialized = 1;
1932
	o->internal.result.timestamp.sec = o->src_index->timestamp.sec;
1933
	o->internal.result.timestamp.nsec = o->src_index->timestamp.nsec;
1934
	o->internal.result.version = o->src_index->version;
1935
	if (!o->src_index->split_index) {
1936
		o->internal.result.split_index = NULL;
1937
	} else if (o->src_index == o->dst_index) {
1938
		/*
1939
		 * o->dst_index (and thus o->src_index) will be discarded
1940
		 * and overwritten with o->internal.result at the end of
1941
		 * this function, so just use src_index's split_index to
1942
		 * avoid having to create a new one.
1943
		 */
1944
		o->internal.result.split_index = o->src_index->split_index;
1945
		if (o->src_index->cache_changed & SPLIT_INDEX_ORDERED)
1946
			o->internal.result.cache_changed |= SPLIT_INDEX_ORDERED;
1947
		o->internal.result.split_index->refcount++;
1948
	} else {
1949
		o->internal.result.split_index =
1950
			init_split_index(&o->internal.result);
1951
	}
1952
	oidcpy(&o->internal.result.oid, &o->src_index->oid);
1953
	o->internal.merge_size = len;
1954
	mark_all_ce_unused(o->src_index);
1955

1956
	o->internal.result.fsmonitor_last_update =
1957
		xstrdup_or_null(o->src_index->fsmonitor_last_update);
1958
	o->internal.result.fsmonitor_has_run_once = o->src_index->fsmonitor_has_run_once;
1959

1960
	if (!o->src_index->initialized &&
1961
	    !repo->settings.command_requires_full_index &&
1962
	    is_sparse_index_allowed(&o->internal.result, 0))
1963
		o->internal.result.sparse_index = 1;
1964

1965
	/*
1966
	 * Sparse checkout loop #1: set NEW_SKIP_WORKTREE on existing entries
1967
	 */
1968
	if (!o->skip_sparse_checkout)
1969
		mark_new_skip_worktree(o->internal.pl, o->src_index, 0,
1970
				       CE_NEW_SKIP_WORKTREE, o->verbose_update);
1971

1972
	if (!dfc)
1973
		dfc = xcalloc(1, cache_entry_size(0));
1974
	o->df_conflict_entry = dfc;
1975

1976
	if (len) {
1977
		const char *prefix = o->prefix ? o->prefix : "";
1978
		struct traverse_info info;
1979

1980
		setup_traverse_info(&info, prefix);
1981
		info.fn = unpack_callback;
1982
		info.data = o;
1983
		info.show_all_errors = o->internal.show_all_errors;
1984
		info.pathspec = o->pathspec;
1985

1986
		if (o->prefix) {
1987
			/*
1988
			 * Unpack existing index entries that sort before the
1989
			 * prefix the tree is spliced into.  Note that o->merge
1990
			 * is always true in this case.
1991
			 */
1992
			while (1) {
1993
				struct cache_entry *ce = next_cache_entry(o);
1994
				if (!ce)
1995
					break;
1996
				if (ce_in_traverse_path(ce, &info))
1997
					break;
1998
				if (unpack_index_entry(ce, o) < 0)
1999
					goto return_failed;
2000
			}
2001
		}
2002

2003
		trace_performance_enter();
2004
		trace2_region_enter("unpack_trees", "traverse_trees", the_repository);
2005
		ret = traverse_trees(o->src_index, len, t, &info);
2006
		trace2_region_leave("unpack_trees", "traverse_trees", the_repository);
2007
		trace_performance_leave("traverse_trees");
2008
		if (ret < 0)
2009
			goto return_failed;
2010
	}
2011

2012
	/* Any left-over entries in the index? */
2013
	if (o->merge) {
2014
		while (1) {
2015
			struct cache_entry *ce = next_cache_entry(o);
2016
			if (!ce)
2017
				break;
2018
			if (unpack_index_entry(ce, o) < 0)
2019
				goto return_failed;
2020
		}
2021
	}
2022
	mark_all_ce_unused(o->src_index);
2023

2024
	if (o->trivial_merges_only && o->internal.nontrivial_merge) {
2025
		ret = unpack_failed(o, "Merge requires file-level merging");
2026
		goto done;
2027
	}
2028

2029
	if (!o->skip_sparse_checkout) {
2030
		/*
2031
		 * Sparse checkout loop #2: set NEW_SKIP_WORKTREE on entries not in loop #1
2032
		 * If they will have NEW_SKIP_WORKTREE, also set CE_SKIP_WORKTREE
2033
		 * so apply_sparse_checkout() won't attempt to remove it from worktree
2034
		 */
2035
		mark_new_skip_worktree(o->internal.pl, &o->internal.result,
2036
				       CE_ADDED, CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE,
2037
				       o->verbose_update);
2038

2039
		ret = 0;
2040
		for (i = 0; i < o->internal.result.cache_nr; i++) {
2041
			struct cache_entry *ce = o->internal.result.cache[i];
2042

2043
			/*
2044
			 * Entries marked with CE_ADDED in merged_entry() do not have
2045
			 * verify_absent() check (the check is effectively disabled
2046
			 * because CE_NEW_SKIP_WORKTREE is set unconditionally).
2047
			 *
2048
			 * Do the real check now because we have had
2049
			 * correct CE_NEW_SKIP_WORKTREE
2050
			 */
2051
			if (ce->ce_flags & CE_ADDED &&
2052
			    verify_absent(ce, WARNING_SPARSE_ORPHANED_NOT_OVERWRITTEN, o))
2053
				ret = 1;
2054

2055
			if (apply_sparse_checkout(&o->internal.result, ce, o))
2056
				ret = 1;
2057
		}
2058
		if (ret == 1) {
2059
			/*
2060
			 * Inability to sparsify or de-sparsify individual
2061
			 * paths is not an error, but just a warning.
2062
			 */
2063
			if (o->internal.show_all_errors)
2064
				display_warning_msgs(o);
2065
			ret = 0;
2066
		}
2067
	}
2068

2069
	ret = check_updates(o, &o->internal.result) ? (-2) : 0;
2070
	if (o->dst_index) {
2071
		move_index_extensions(&o->internal.result, o->src_index);
2072
		if (!ret) {
2073
			if (git_env_bool("GIT_TEST_CHECK_CACHE_TREE", 0))
2074
				cache_tree_verify(the_repository,
2075
						  &o->internal.result);
2076
			if (!o->skip_cache_tree_update &&
2077
			    !cache_tree_fully_valid(o->internal.result.cache_tree))
2078
				cache_tree_update(&o->internal.result,
2079
						  WRITE_TREE_SILENT |
2080
						  WRITE_TREE_REPAIR);
2081
		}
2082

2083
		o->internal.result.updated_workdir = 1;
2084
		discard_index(o->dst_index);
2085
		*o->dst_index = o->internal.result;
2086
		memset(&o->internal.result, 0, sizeof(o->internal.result));
2087
	} else {
2088
		discard_index(&o->internal.result);
2089
	}
2090
	o->src_index = NULL;
2091

2092
done:
2093
	if (free_pattern_list)
2094
		clear_pattern_list(&pl);
2095
	if (o->internal.dir) {
2096
		dir_clear(o->internal.dir);
2097
		o->internal.dir = NULL;
2098
	}
2099
	trace2_region_leave("unpack_trees", "unpack_trees", the_repository);
2100
	trace_performance_leave("unpack_trees");
2101
	return ret;
2102

2103
return_failed:
2104
	if (o->internal.show_all_errors)
2105
		display_error_msgs(o);
2106
	mark_all_ce_unused(o->src_index);
2107
	ret = unpack_failed(o, NULL);
2108
	if (o->exiting_early)
2109
		ret = 0;
2110
	goto done;
2111
}
2112

2113
/*
2114
 * Update SKIP_WORKTREE bits according to sparsity patterns, and update
2115
 * working directory to match.
2116
 *
2117
 * CE_NEW_SKIP_WORKTREE is used internally.
2118
 */
2119
enum update_sparsity_result update_sparsity(struct unpack_trees_options *o,
2120
					    struct pattern_list *pl)
2121
{
2122
	enum update_sparsity_result ret = UPDATE_SPARSITY_SUCCESS;
2123
	int i;
2124
	unsigned old_show_all_errors;
2125
	int free_pattern_list = 0;
2126

2127
	old_show_all_errors = o->internal.show_all_errors;
2128
	o->internal.show_all_errors = 1;
2129
	index_state_init(&o->internal.result, o->src_index->repo);
2130

2131
	/* Sanity checks */
2132
	if (!o->update || o->index_only || o->skip_sparse_checkout)
2133
		BUG("update_sparsity() is for reflecting sparsity patterns in working directory");
2134
	if (o->src_index != o->dst_index || o->fn)
2135
		BUG("update_sparsity() called wrong");
2136

2137
	trace_performance_enter();
2138

2139
	/* If we weren't given patterns, use the recorded ones */
2140
	if (!pl) {
2141
		free_pattern_list = 1;
2142
		pl = xcalloc(1, sizeof(*pl));
2143
		populate_from_existing_patterns(o, pl);
2144
	}
2145
	o->internal.pl = pl;
2146

2147
	/* Expand sparse directories as needed */
2148
	expand_index(o->src_index, o->internal.pl);
2149

2150
	/* Set NEW_SKIP_WORKTREE on existing entries. */
2151
	mark_all_ce_unused(o->src_index);
2152
	mark_new_skip_worktree(o->internal.pl, o->src_index, 0,
2153
			       CE_NEW_SKIP_WORKTREE, o->verbose_update);
2154

2155
	/* Then loop over entries and update/remove as needed */
2156
	ret = UPDATE_SPARSITY_SUCCESS;
2157
	for (i = 0; i < o->src_index->cache_nr; i++) {
2158
		struct cache_entry *ce = o->src_index->cache[i];
2159

2160

2161
		if (ce_stage(ce)) {
2162
			/* -1 because for loop will increment by 1 */
2163
			i += warn_conflicted_path(o->src_index, i, o) - 1;
2164
			ret = UPDATE_SPARSITY_WARNINGS;
2165
			continue;
2166
		}
2167

2168
		if (apply_sparse_checkout(o->src_index, ce, o))
2169
			ret = UPDATE_SPARSITY_WARNINGS;
2170
	}
2171

2172
	if (check_updates(o, o->src_index))
2173
		ret = UPDATE_SPARSITY_WORKTREE_UPDATE_FAILURES;
2174

2175
	display_warning_msgs(o);
2176
	o->internal.show_all_errors = old_show_all_errors;
2177
	if (free_pattern_list) {
2178
		clear_pattern_list(pl);
2179
		free(pl);
2180
		o->internal.pl = NULL;
2181
	}
2182
	trace_performance_leave("update_sparsity");
2183
	return ret;
2184
}
2185

2186
/* Here come the merge functions */
2187

2188
static int reject_merge(const struct cache_entry *ce,
2189
			struct unpack_trees_options *o)
2190
{
2191
	return add_rejected_path(o, ERROR_WOULD_OVERWRITE, ce->name);
2192
}
2193

2194
static int same(const struct cache_entry *a, const struct cache_entry *b)
2195
{
2196
	if (!!a != !!b)
2197
		return 0;
2198
	if (!a && !b)
2199
		return 1;
2200
	if ((a->ce_flags | b->ce_flags) & CE_CONFLICTED)
2201
		return 0;
2202
	return a->ce_mode == b->ce_mode &&
2203
	       oideq(&a->oid, &b->oid);
2204
}
2205

2206

2207
/*
2208
 * When a CE gets turned into an unmerged entry, we
2209
 * want it to be up-to-date
2210
 */
2211
static int verify_uptodate_1(const struct cache_entry *ce,
2212
			     struct unpack_trees_options *o,
2213
			     enum unpack_trees_error_types error_type)
2214
{
2215
	struct stat st;
2216

2217
	if (o->index_only)
2218
		return 0;
2219

2220
	/*
2221
	 * CE_VALID and CE_SKIP_WORKTREE cheat, we better check again
2222
	 * if this entry is truly up-to-date because this file may be
2223
	 * overwritten.
2224
	 */
2225
	if ((ce->ce_flags & CE_VALID) || ce_skip_worktree(ce))
2226
		; /* keep checking */
2227
	else if (o->reset || ce_uptodate(ce))
2228
		return 0;
2229

2230
	if (!lstat(ce->name, &st)) {
2231
		int flags = CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE;
2232
		unsigned changed = ie_match_stat(o->src_index, ce, &st, flags);
2233

2234
		if (submodule_from_ce(ce)) {
2235
			int r = check_submodule_move_head(ce,
2236
				"HEAD", oid_to_hex(&ce->oid), o);
2237
			if (r)
2238
				return add_rejected_path(o, error_type, ce->name);
2239
			return 0;
2240
		}
2241

2242
		if (!changed)
2243
			return 0;
2244
		/*
2245
		 * Historic default policy was to allow submodule to be out
2246
		 * of sync wrt the superproject index. If the submodule was
2247
		 * not considered interesting above, we don't care here.
2248
		 */
2249
		if (S_ISGITLINK(ce->ce_mode))
2250
			return 0;
2251

2252
		errno = 0;
2253
	}
2254
	if (errno == ENOENT)
2255
		return 0;
2256
	return add_rejected_path(o, error_type, ce->name);
2257
}
2258

2259
int verify_uptodate(const struct cache_entry *ce,
2260
		    struct unpack_trees_options *o)
2261
{
2262
	if (!o->skip_sparse_checkout &&
2263
	    (ce->ce_flags & CE_SKIP_WORKTREE) &&
2264
	    (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
2265
		return 0;
2266
	return verify_uptodate_1(ce, o, ERROR_NOT_UPTODATE_FILE);
2267
}
2268

2269
static int verify_uptodate_sparse(const struct cache_entry *ce,
2270
				  struct unpack_trees_options *o)
2271
{
2272
	return verify_uptodate_1(ce, o, WARNING_SPARSE_NOT_UPTODATE_FILE);
2273
}
2274

2275
/*
2276
 * TODO: We should actually invalidate o->internal.result, not src_index [1].
2277
 * But since cache tree and untracked cache both are not copied to
2278
 * o->internal.result until unpacking is complete, we invalidate them on
2279
 * src_index instead with the assumption that they will be copied to
2280
 * dst_index at the end.
2281
 *
2282
 * [1] src_index->cache_tree is also used in unpack_callback() so if
2283
 * we invalidate o->internal.result, we need to update it to use
2284
 * o->internal.result.cache_tree as well.
2285
 */
2286
static void invalidate_ce_path(const struct cache_entry *ce,
2287
			       struct unpack_trees_options *o)
2288
{
2289
	if (!ce)
2290
		return;
2291
	cache_tree_invalidate_path(o->src_index, ce->name);
2292
	untracked_cache_invalidate_path(o->src_index, ce->name, 1);
2293
}
2294

2295
/*
2296
 * Check that checking out ce->sha1 in subdir ce->name is not
2297
 * going to overwrite any working files.
2298
 */
2299
static int verify_clean_submodule(const char *old_sha1,
2300
				  const struct cache_entry *ce,
2301
				  struct unpack_trees_options *o)
2302
{
2303
	if (!submodule_from_ce(ce))
2304
		return 0;
2305

2306
	return check_submodule_move_head(ce, old_sha1,
2307
					 oid_to_hex(&ce->oid), o);
2308
}
2309

2310
static int verify_clean_subdirectory(const struct cache_entry *ce,
2311
				     struct unpack_trees_options *o)
2312
{
2313
	/*
2314
	 * we are about to extract "ce->name"; we would not want to lose
2315
	 * anything in the existing directory there.
2316
	 */
2317
	int namelen;
2318
	int i;
2319
	struct dir_struct d;
2320
	char *pathbuf;
2321
	int cnt = 0;
2322

2323
	if (S_ISGITLINK(ce->ce_mode)) {
2324
		struct object_id oid;
2325
		int sub_head = repo_resolve_gitlink_ref(the_repository, ce->name,
2326
							"HEAD", &oid);
2327
		/*
2328
		 * If we are not going to update the submodule, then
2329
		 * we don't care.
2330
		 */
2331
		if (!sub_head && oideq(&oid, &ce->oid))
2332
			return 0;
2333
		return verify_clean_submodule(sub_head ? NULL : oid_to_hex(&oid),
2334
					      ce, o);
2335
	}
2336

2337
	/*
2338
	 * First let's make sure we do not have a local modification
2339
	 * in that directory.
2340
	 */
2341
	namelen = ce_namelen(ce);
2342
	for (i = locate_in_src_index(ce, o);
2343
	     i < o->src_index->cache_nr;
2344
	     i++) {
2345
		struct cache_entry *ce2 = o->src_index->cache[i];
2346
		int len = ce_namelen(ce2);
2347
		if (len < namelen ||
2348
		    strncmp(ce->name, ce2->name, namelen) ||
2349
		    ce2->name[namelen] != '/')
2350
			break;
2351
		/*
2352
		 * ce2->name is an entry in the subdirectory to be
2353
		 * removed.
2354
		 */
2355
		if (!ce_stage(ce2)) {
2356
			if (verify_uptodate(ce2, o))
2357
				return -1;
2358
			add_entry(o, ce2, CE_REMOVE, 0);
2359
			invalidate_ce_path(ce, o);
2360
			mark_ce_used(ce2, o);
2361
		}
2362
		cnt++;
2363
	}
2364

2365
	/* Do not lose a locally present file that is not ignored. */
2366
	pathbuf = xstrfmt("%.*s/", namelen, ce->name);
2367

2368
	memset(&d, 0, sizeof(d));
2369
	if (o->internal.dir)
2370
		setup_standard_excludes(&d);
2371
	i = read_directory(&d, o->src_index, pathbuf, namelen+1, NULL);
2372
	dir_clear(&d);
2373
	free(pathbuf);
2374
	if (i)
2375
		return add_rejected_path(o, ERROR_NOT_UPTODATE_DIR, ce->name);
2376

2377
	/* Do not lose startup_info->original_cwd */
2378
	if (startup_info->original_cwd &&
2379
	    !strcmp(startup_info->original_cwd, ce->name))
2380
		return add_rejected_path(o, ERROR_CWD_IN_THE_WAY, ce->name);
2381

2382
	return cnt;
2383
}
2384

2385
/*
2386
 * This gets called when there was no index entry for the tree entry 'dst',
2387
 * but we found a file in the working tree that 'lstat()' said was fine,
2388
 * and we're on a case-insensitive filesystem.
2389
 *
2390
 * See if we can find a case-insensitive match in the index that also
2391
 * matches the stat information, and assume it's that other file!
2392
 */
2393
static int icase_exists(struct unpack_trees_options *o, const char *name, int len, struct stat *st)
2394
{
2395
	const struct cache_entry *src;
2396

2397
	src = index_file_exists(o->src_index, name, len, 1);
2398
	return src && !ie_match_stat(o->src_index, src, st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
2399
}
2400

2401
enum absent_checking_type {
2402
	COMPLETELY_ABSENT,
2403
	ABSENT_ANY_DIRECTORY
2404
};
2405

2406
static int check_ok_to_remove(const char *name, int len, int dtype,
2407
			      const struct cache_entry *ce, struct stat *st,
2408
			      enum unpack_trees_error_types error_type,
2409
			      enum absent_checking_type absent_type,
2410
			      struct unpack_trees_options *o)
2411
{
2412
	const struct cache_entry *result;
2413

2414
	/*
2415
	 * It may be that the 'lstat()' succeeded even though
2416
	 * target 'ce' was absent, because there is an old
2417
	 * entry that is different only in case..
2418
	 *
2419
	 * Ignore that lstat() if it matches.
2420
	 */
2421
	if (ignore_case && icase_exists(o, name, len, st))
2422
		return 0;
2423

2424
	if (o->internal.dir &&
2425
	    is_excluded(o->internal.dir, o->src_index, name, &dtype))
2426
		/*
2427
		 * ce->name is explicitly excluded, so it is Ok to
2428
		 * overwrite it.
2429
		 */
2430
		return 0;
2431
	if (S_ISDIR(st->st_mode)) {
2432
		/*
2433
		 * We are checking out path "foo" and
2434
		 * found "foo/." in the working tree.
2435
		 * This is tricky -- if we have modified
2436
		 * files that are in "foo/" we would lose
2437
		 * them.
2438
		 */
2439
		if (verify_clean_subdirectory(ce, o) < 0)
2440
			return -1;
2441
		return 0;
2442
	}
2443

2444
	/* If we only care about directories, then we can remove */
2445
	if (absent_type == ABSENT_ANY_DIRECTORY)
2446
		return 0;
2447

2448
	/*
2449
	 * The previous round may already have decided to
2450
	 * delete this path, which is in a subdirectory that
2451
	 * is being replaced with a blob.
2452
	 */
2453
	result = index_file_exists(&o->internal.result, name, len, 0);
2454
	if (result) {
2455
		if (result->ce_flags & CE_REMOVE)
2456
			return 0;
2457
	}
2458

2459
	return add_rejected_path(o, error_type, name);
2460
}
2461

2462
/*
2463
 * We do not want to remove or overwrite a working tree file that
2464
 * is not tracked, unless it is ignored.
2465
 */
2466
static int verify_absent_1(const struct cache_entry *ce,
2467
			   enum unpack_trees_error_types error_type,
2468
			   enum absent_checking_type absent_type,
2469
			   struct unpack_trees_options *o)
2470
{
2471
	int len;
2472
	struct stat st;
2473

2474
	if (o->index_only || !o->update)
2475
		return 0;
2476

2477
	if (o->reset == UNPACK_RESET_OVERWRITE_UNTRACKED) {
2478
		/* Avoid nuking startup_info->original_cwd... */
2479
		if (startup_info->original_cwd &&
2480
		    !strcmp(startup_info->original_cwd, ce->name))
2481
			return add_rejected_path(o, ERROR_CWD_IN_THE_WAY,
2482
						 ce->name);
2483
		/* ...but nuke anything else. */
2484
		return 0;
2485
	}
2486

2487
	len = check_leading_path(ce->name, ce_namelen(ce), 0);
2488
	if (!len)
2489
		return 0;
2490
	else if (len > 0) {
2491
		char *path;
2492
		int ret;
2493

2494
		path = xmemdupz(ce->name, len);
2495
		if (lstat(path, &st))
2496
			ret = error_errno("cannot stat '%s'", path);
2497
		else {
2498
			if (submodule_from_ce(ce))
2499
				ret = check_submodule_move_head(ce,
2500
								oid_to_hex(&ce->oid),
2501
								NULL, o);
2502
			else
2503
				ret = check_ok_to_remove(path, len, DT_UNKNOWN, NULL,
2504
							 &st, error_type,
2505
							 absent_type, o);
2506
		}
2507
		free(path);
2508
		return ret;
2509
	} else if (lstat(ce->name, &st)) {
2510
		if (errno != ENOENT)
2511
			return error_errno("cannot stat '%s'", ce->name);
2512
		return 0;
2513
	} else {
2514
		if (submodule_from_ce(ce))
2515
			return check_submodule_move_head(ce, oid_to_hex(&ce->oid),
2516
							 NULL, o);
2517

2518
		return check_ok_to_remove(ce->name, ce_namelen(ce),
2519
					  ce_to_dtype(ce), ce, &st,
2520
					  error_type, absent_type, o);
2521
	}
2522
}
2523

2524
static int verify_absent(const struct cache_entry *ce,
2525
			 enum unpack_trees_error_types error_type,
2526
			 struct unpack_trees_options *o)
2527
{
2528
	if (!o->skip_sparse_checkout && (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
2529
		return 0;
2530
	return verify_absent_1(ce, error_type, COMPLETELY_ABSENT, o);
2531
}
2532

2533
static int verify_absent_if_directory(const struct cache_entry *ce,
2534
				      enum unpack_trees_error_types error_type,
2535
				      struct unpack_trees_options *o)
2536
{
2537
	if (!o->skip_sparse_checkout && (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
2538
		return 0;
2539
	return verify_absent_1(ce, error_type, ABSENT_ANY_DIRECTORY, o);
2540
}
2541

2542
static int verify_absent_sparse(const struct cache_entry *ce,
2543
				enum unpack_trees_error_types error_type,
2544
				struct unpack_trees_options *o)
2545
{
2546
	return verify_absent_1(ce, error_type, COMPLETELY_ABSENT, o);
2547
}
2548

2549
static int merged_entry(const struct cache_entry *ce,
2550
			const struct cache_entry *old,
2551
			struct unpack_trees_options *o)
2552
{
2553
	int update = CE_UPDATE;
2554
	struct cache_entry *merge = dup_cache_entry(ce, &o->internal.result);
2555

2556
	if (!old) {
2557
		/*
2558
		 * New index entries. In sparse checkout, the following
2559
		 * verify_absent() will be delayed until after
2560
		 * traverse_trees() finishes in unpack_trees(), then:
2561
		 *
2562
		 *  - CE_NEW_SKIP_WORKTREE will be computed correctly
2563
		 *  - verify_absent() be called again, this time with
2564
		 *    correct CE_NEW_SKIP_WORKTREE
2565
		 *
2566
		 * verify_absent() call here does nothing in sparse
2567
		 * checkout (i.e. o->skip_sparse_checkout == 0)
2568
		 */
2569
		update |= CE_ADDED;
2570
		merge->ce_flags |= CE_NEW_SKIP_WORKTREE;
2571

2572
		if (verify_absent(merge,
2573
				  ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o)) {
2574
			discard_cache_entry(merge);
2575
			return -1;
2576
		}
2577
		invalidate_ce_path(merge, o);
2578

2579
		if (submodule_from_ce(ce) && file_exists(ce->name)) {
2580
			int ret = check_submodule_move_head(ce, NULL,
2581
							    oid_to_hex(&ce->oid),
2582
							    o);
2583
			if (ret)
2584
				return ret;
2585
		}
2586

2587
	} else if (!(old->ce_flags & CE_CONFLICTED)) {
2588
		/*
2589
		 * See if we can re-use the old CE directly?
2590
		 * That way we get the uptodate stat info.
2591
		 *
2592
		 * This also removes the UPDATE flag on a match; otherwise
2593
		 * we will end up overwriting local changes in the work tree.
2594
		 */
2595
		if (same(old, merge)) {
2596
			copy_cache_entry(merge, old);
2597
			update = 0;
2598
		} else {
2599
			if (verify_uptodate(old, o)) {
2600
				discard_cache_entry(merge);
2601
				return -1;
2602
			}
2603
			/* Migrate old flags over */
2604
			update |= old->ce_flags & (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
2605
			invalidate_ce_path(old, o);
2606
		}
2607

2608
		if (submodule_from_ce(ce) && file_exists(ce->name)) {
2609
			int ret = check_submodule_move_head(ce, oid_to_hex(&old->oid),
2610
							    oid_to_hex(&ce->oid),
2611
							    o);
2612
			if (ret)
2613
				return ret;
2614
		}
2615
	} else {
2616
		/*
2617
		 * Previously unmerged entry left as an existence
2618
		 * marker by read_index_unmerged();
2619
		 */
2620
		if (verify_absent_if_directory(merge,
2621
				  ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o)) {
2622
			discard_cache_entry(merge);
2623
			return -1;
2624
		}
2625

2626
		invalidate_ce_path(old, o);
2627
	}
2628

2629
	if (do_add_entry(o, merge, update, CE_STAGEMASK) < 0)
2630
		return -1;
2631
	return 1;
2632
}
2633

2634
static int merged_sparse_dir(const struct cache_entry * const *src, int n,
2635
			     struct unpack_trees_options *o)
2636
{
2637
	struct tree_desc t[MAX_UNPACK_TREES + 1];
2638
	void * tree_bufs[MAX_UNPACK_TREES + 1];
2639
	struct traverse_info info;
2640
	int i, ret;
2641

2642
	/*
2643
	 * Create the tree traversal information for traversing into *only* the
2644
	 * sparse directory.
2645
	 */
2646
	setup_traverse_info(&info, src[0]->name);
2647
	info.fn = unpack_sparse_callback;
2648
	info.data = o;
2649
	info.show_all_errors = o->internal.show_all_errors;
2650
	info.pathspec = o->pathspec;
2651

2652
	/* Get the tree descriptors of the sparse directory in each of the merging trees */
2653
	for (i = 0; i < n; i++)
2654
		tree_bufs[i] = fill_tree_descriptor(o->src_index->repo, &t[i],
2655
						    src[i] && !is_null_oid(&src[i]->oid) ? &src[i]->oid : NULL);
2656

2657
	ret = traverse_trees(o->src_index, n, t, &info);
2658

2659
	for (i = 0; i < n; i++)
2660
		free(tree_bufs[i]);
2661

2662
	return ret;
2663
}
2664

2665
static int deleted_entry(const struct cache_entry *ce,
2666
			 const struct cache_entry *old,
2667
			 struct unpack_trees_options *o)
2668
{
2669
	/* Did it exist in the index? */
2670
	if (!old) {
2671
		if (verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_REMOVED, o))
2672
			return -1;
2673
		return 0;
2674
	} else if (verify_absent_if_directory(ce, ERROR_WOULD_LOSE_UNTRACKED_REMOVED, o)) {
2675
		return -1;
2676
	}
2677

2678
	if (!(old->ce_flags & CE_CONFLICTED) && verify_uptodate(old, o))
2679
		return -1;
2680
	add_entry(o, ce, CE_REMOVE, 0);
2681
	invalidate_ce_path(ce, o);
2682
	return 1;
2683
}
2684

2685
static int keep_entry(const struct cache_entry *ce,
2686
		      struct unpack_trees_options *o)
2687
{
2688
	add_entry(o, ce, 0, 0);
2689
	if (ce_stage(ce))
2690
		invalidate_ce_path(ce, o);
2691
	return 1;
2692
}
2693

2694
#if DBRT_DEBUG
2695
static void show_stage_entry(FILE *o,
2696
			     const char *label, const struct cache_entry *ce)
2697
{
2698
	if (!ce)
2699
		fprintf(o, "%s (missing)\n", label);
2700
	else
2701
		fprintf(o, "%s%06o %s %d\t%s\n",
2702
			label,
2703
			ce->ce_mode,
2704
			oid_to_hex(&ce->oid),
2705
			ce_stage(ce),
2706
			ce->name);
2707
}
2708
#endif
2709

2710
int threeway_merge(const struct cache_entry * const *stages,
2711
		   struct unpack_trees_options *o)
2712
{
2713
	const struct cache_entry *index;
2714
	const struct cache_entry *head;
2715
	const struct cache_entry *remote = stages[o->head_idx + 1];
2716
	int count;
2717
	int head_match = 0;
2718
	int remote_match = 0;
2719

2720
	int df_conflict_head = 0;
2721
	int df_conflict_remote = 0;
2722

2723
	int any_anc_missing = 0;
2724
	int no_anc_exists = 1;
2725
	int i;
2726

2727
	for (i = 1; i < o->head_idx; i++) {
2728
		if (!stages[i] || stages[i] == o->df_conflict_entry)
2729
			any_anc_missing = 1;
2730
		else
2731
			no_anc_exists = 0;
2732
	}
2733

2734
	index = stages[0];
2735
	head = stages[o->head_idx];
2736

2737
	if (head == o->df_conflict_entry) {
2738
		df_conflict_head = 1;
2739
		head = NULL;
2740
	}
2741

2742
	if (remote == o->df_conflict_entry) {
2743
		df_conflict_remote = 1;
2744
		remote = NULL;
2745
	}
2746

2747
	/*
2748
	 * First, if there's a #16 situation, note that to prevent #13
2749
	 * and #14.
2750
	 */
2751
	if (!same(remote, head)) {
2752
		for (i = 1; i < o->head_idx; i++) {
2753
			if (same(stages[i], head)) {
2754
				head_match = i;
2755
			}
2756
			if (same(stages[i], remote)) {
2757
				remote_match = i;
2758
			}
2759
		}
2760
	}
2761

2762
	/*
2763
	 * We start with cases where the index is allowed to match
2764
	 * something other than the head: #14(ALT) and #2ALT, where it
2765
	 * is permitted to match the result instead.
2766
	 */
2767
	/* #14, #14ALT, #2ALT */
2768
	if (remote && !df_conflict_head && head_match && !remote_match) {
2769
		if (index && !same(index, remote) && !same(index, head)) {
2770
			if (S_ISSPARSEDIR(index->ce_mode))
2771
				return merged_sparse_dir(stages, 4, o);
2772
			else
2773
				return reject_merge(index, o);
2774
		}
2775
		return merged_entry(remote, index, o);
2776
	}
2777
	/*
2778
	 * If we have an entry in the index cache, then we want to
2779
	 * make sure that it matches head.
2780
	 */
2781
	if (index && !same(index, head)) {
2782
		if (S_ISSPARSEDIR(index->ce_mode))
2783
			return merged_sparse_dir(stages, 4, o);
2784
		else
2785
			return reject_merge(index, o);
2786
	}
2787

2788
	if (head) {
2789
		/* #5ALT, #15 */
2790
		if (same(head, remote))
2791
			return merged_entry(head, index, o);
2792
		/* #13, #3ALT */
2793
		if (!df_conflict_remote && remote_match && !head_match)
2794
			return merged_entry(head, index, o);
2795
	}
2796

2797
	/* #1 */
2798
	if (!head && !remote && any_anc_missing)
2799
		return 0;
2800

2801
	/*
2802
	 * Under the "aggressive" rule, we resolve mostly trivial
2803
	 * cases that we historically had git-merge-one-file resolve.
2804
	 */
2805
	if (o->aggressive) {
2806
		int head_deleted = !head;
2807
		int remote_deleted = !remote;
2808
		const struct cache_entry *ce = NULL;
2809

2810
		if (index)
2811
			ce = index;
2812
		else if (head)
2813
			ce = head;
2814
		else if (remote)
2815
			ce = remote;
2816
		else {
2817
			for (i = 1; i < o->head_idx; i++) {
2818
				if (stages[i] && stages[i] != o->df_conflict_entry) {
2819
					ce = stages[i];
2820
					break;
2821
				}
2822
			}
2823
		}
2824

2825
		/*
2826
		 * Deleted in both.
2827
		 * Deleted in one and unchanged in the other.
2828
		 */
2829
		if ((head_deleted && remote_deleted) ||
2830
		    (head_deleted && remote && remote_match) ||
2831
		    (remote_deleted && head && head_match)) {
2832
			if (index)
2833
				return deleted_entry(index, index, o);
2834
			if (ce && !head_deleted) {
2835
				if (verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_REMOVED, o))
2836
					return -1;
2837
			}
2838
			return 0;
2839
		}
2840
		/*
2841
		 * Added in both, identically.
2842
		 */
2843
		if (no_anc_exists && head && remote && same(head, remote))
2844
			return merged_entry(head, index, o);
2845

2846
	}
2847

2848
	/* Handle "no merge" cases (see t/t1000-read-tree-m-3way.sh) */
2849
	if (index) {
2850
		/*
2851
		 * If we've reached the "no merge" cases and we're merging
2852
		 * a sparse directory, we may have an "edit/edit" conflict that
2853
		 * can be resolved by individually merging directory contents.
2854
		 */
2855
		if (S_ISSPARSEDIR(index->ce_mode))
2856
			return merged_sparse_dir(stages, 4, o);
2857

2858
		/*
2859
		 * If we're not merging a sparse directory, ensure the index is
2860
		 * up-to-date to avoid files getting overwritten with conflict
2861
		 * resolution files
2862
		 */
2863
		if (verify_uptodate(index, o))
2864
			return -1;
2865
	}
2866

2867
	o->internal.nontrivial_merge = 1;
2868

2869
	/* #2, #3, #4, #6, #7, #9, #10, #11. */
2870
	count = 0;
2871
	if (!head_match || !remote_match) {
2872
		for (i = 1; i < o->head_idx; i++) {
2873
			if (stages[i] && stages[i] != o->df_conflict_entry) {
2874
				keep_entry(stages[i], o);
2875
				count++;
2876
				break;
2877
			}
2878
		}
2879
	}
2880
#if DBRT_DEBUG
2881
	else {
2882
		fprintf(stderr, "read-tree: warning #16 detected\n");
2883
		show_stage_entry(stderr, "head   ", stages[head_match]);
2884
		show_stage_entry(stderr, "remote ", stages[remote_match]);
2885
	}
2886
#endif
2887
	if (head) { count += keep_entry(head, o); }
2888
	if (remote) { count += keep_entry(remote, o); }
2889
	return count;
2890
}
2891

2892
/*
2893
 * Two-way merge.
2894
 *
2895
 * The rule is to "carry forward" what is in the index without losing
2896
 * information across a "fast-forward", favoring a successful merge
2897
 * over a merge failure when it makes sense.  For details of the
2898
 * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
2899
 *
2900
 */
2901
int twoway_merge(const struct cache_entry * const *src,
2902
		 struct unpack_trees_options *o)
2903
{
2904
	const struct cache_entry *current = src[0];
2905
	const struct cache_entry *oldtree = src[1];
2906
	const struct cache_entry *newtree = src[2];
2907

2908
	if (o->internal.merge_size != 2)
2909
		return error("Cannot do a twoway merge of %d trees",
2910
			     o->internal.merge_size);
2911

2912
	if (oldtree == o->df_conflict_entry)
2913
		oldtree = NULL;
2914
	if (newtree == o->df_conflict_entry)
2915
		newtree = NULL;
2916

2917
	if (current) {
2918
		if (current->ce_flags & CE_CONFLICTED) {
2919
			if (same(oldtree, newtree) || o->reset) {
2920
				if (!newtree)
2921
					return deleted_entry(current, current, o);
2922
				else
2923
					return merged_entry(newtree, current, o);
2924
			}
2925
			return reject_merge(current, o);
2926
		} else if ((!oldtree && !newtree) || /* 4 and 5 */
2927
			 (!oldtree && newtree &&
2928
			  same(current, newtree)) || /* 6 and 7 */
2929
			 (oldtree && newtree &&
2930
			  same(oldtree, newtree)) || /* 14 and 15 */
2931
			 (oldtree && newtree &&
2932
			  !same(oldtree, newtree) && /* 18 and 19 */
2933
			  same(current, newtree))) {
2934
			return keep_entry(current, o);
2935
		} else if (oldtree && !newtree && same(current, oldtree)) {
2936
			/* 10 or 11 */
2937
			return deleted_entry(oldtree, current, o);
2938
		} else if (oldtree && newtree &&
2939
			 same(current, oldtree) && !same(current, newtree)) {
2940
			/* 20 or 21 */
2941
			return merged_entry(newtree, current, o);
2942
		} else if (current && !oldtree && newtree &&
2943
			   S_ISSPARSEDIR(current->ce_mode) != S_ISSPARSEDIR(newtree->ce_mode) &&
2944
			   ce_stage(current) == 0) {
2945
			/*
2946
			 * This case is a directory/file conflict across the sparse-index
2947
			 * boundary. When we are changing from one path to another via
2948
			 * 'git checkout', then we want to replace one entry with another
2949
			 * via merged_entry(). If there are staged changes, then we should
2950
			 * reject the merge instead.
2951
			 */
2952
			return merged_entry(newtree, current, o);
2953
		} else if (S_ISSPARSEDIR(current->ce_mode)) {
2954
			/*
2955
			 * The sparse directories differ, but we don't know whether that's
2956
			 * because of two different files in the directory being modified
2957
			 * (can be trivially merged) or if there is a real file conflict.
2958
			 * Merge the sparse directory by OID to compare file-by-file.
2959
			 */
2960
			return merged_sparse_dir(src, 3, o);
2961
		} else
2962
			return reject_merge(current, o);
2963
	}
2964
	else if (newtree) {
2965
		if (oldtree && !o->initial_checkout) {
2966
			/*
2967
			 * deletion of the path was staged;
2968
			 */
2969
			if (same(oldtree, newtree))
2970
				return 1;
2971
			return reject_merge(oldtree, o);
2972
		}
2973
		return merged_entry(newtree, current, o);
2974
	}
2975
	return deleted_entry(oldtree, current, o);
2976
}
2977

2978
/*
2979
 * Bind merge.
2980
 *
2981
 * Keep the index entries at stage0, collapse stage1 but make sure
2982
 * stage0 does not have anything there.
2983
 */
2984
int bind_merge(const struct cache_entry * const *src,
2985
	       struct unpack_trees_options *o)
2986
{
2987
	const struct cache_entry *old = src[0];
2988
	const struct cache_entry *a = src[1];
2989

2990
	if (o->internal.merge_size != 1)
2991
		return error("Cannot do a bind merge of %d trees",
2992
			     o->internal.merge_size);
2993
	if (a && old)
2994
		return o->quiet ? -1 :
2995
			error(ERRORMSG(o, ERROR_BIND_OVERLAP),
2996
			      super_prefixed(a->name, o->super_prefix),
2997
			      super_prefixed(old->name, o->super_prefix));
2998
	if (!a)
2999
		return keep_entry(old, o);
3000
	else
3001
		return merged_entry(a, NULL, o);
3002
}
3003

3004
/*
3005
 * One-way merge.
3006
 *
3007
 * The rule is:
3008
 * - take the stat information from stage0, take the data from stage1
3009
 */
3010
int oneway_merge(const struct cache_entry * const *src,
3011
		 struct unpack_trees_options *o)
3012
{
3013
	const struct cache_entry *old = src[0];
3014
	const struct cache_entry *a = src[1];
3015

3016
	if (o->internal.merge_size != 1)
3017
		return error("Cannot do a oneway merge of %d trees",
3018
			     o->internal.merge_size);
3019

3020
	if (!a || a == o->df_conflict_entry)
3021
		return deleted_entry(old, old, o);
3022

3023
	if (old && same(old, a)) {
3024
		int update = 0;
3025
		if (o->reset && o->update && !ce_uptodate(old) && !ce_skip_worktree(old) &&
3026
			!(old->ce_flags & CE_FSMONITOR_VALID)) {
3027
			struct stat st;
3028
			if (lstat(old->name, &st) ||
3029
			    ie_match_stat(o->src_index, old, &st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE))
3030
				update |= CE_UPDATE;
3031
		}
3032
		if (o->update && S_ISGITLINK(old->ce_mode) &&
3033
		    should_update_submodules() && !verify_uptodate(old, o))
3034
			update |= CE_UPDATE;
3035
		add_entry(o, old, update, CE_STAGEMASK);
3036
		return 0;
3037
	}
3038
	return merged_entry(a, old, o);
3039
}
3040

3041
/*
3042
 * Merge worktree and untracked entries in a stash entry.
3043
 *
3044
 * Ignore all index entries. Collapse remaining trees but make sure that they
3045
 * don't have any conflicting files.
3046
 */
3047
int stash_worktree_untracked_merge(const struct cache_entry * const *src,
3048
				   struct unpack_trees_options *o)
3049
{
3050
	const struct cache_entry *worktree = src[1];
3051
	const struct cache_entry *untracked = src[2];
3052

3053
	if (o->internal.merge_size != 2)
3054
		BUG("invalid merge_size: %d", o->internal.merge_size);
3055

3056
	if (worktree && untracked)
3057
		return error(_("worktree and untracked commit have duplicate entries: %s"),
3058
			     super_prefixed(worktree->name, o->super_prefix));
3059

3060
	return merged_entry(worktree ? worktree : untracked, NULL, o);
3061
}
3062