Merge branch 'sg/test-stress-jobs'
[git] / unpack-trees.c
1 #include "cache.h"
2 #include "strvec.h"
3 #include "repository.h"
4 #include "config.h"
5 #include "dir.h"
6 #include "tree.h"
7 #include "tree-walk.h"
8 #include "cache-tree.h"
9 #include "unpack-trees.h"
10 #include "progress.h"
11 #include "refs.h"
12 #include "attr.h"
13 #include "split-index.h"
14 #include "submodule.h"
15 #include "submodule-config.h"
16 #include "fsmonitor.h"
17 #include "object-store.h"
18 #include "promisor-remote.h"
19
20 /*
21  * Error messages expected by scripts out of plumbing commands such as
22  * read-tree.  Non-scripted Porcelain is not required to use these messages
23  * and in fact are encouraged to reword them to better suit their particular
24  * situation better.  See how "git checkout" and "git merge" replaces
25  * them using setup_unpack_trees_porcelain(), for example.
26  */
27 static const char *unpack_plumbing_errors[NB_UNPACK_TREES_WARNING_TYPES] = {
28         /* ERROR_WOULD_OVERWRITE */
29         "Entry '%s' would be overwritten by merge. Cannot merge.",
30
31         /* ERROR_NOT_UPTODATE_FILE */
32         "Entry '%s' not uptodate. Cannot merge.",
33
34         /* ERROR_NOT_UPTODATE_DIR */
35         "Updating '%s' would lose untracked files in it",
36
37         /* ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN */
38         "Untracked working tree file '%s' would be overwritten by merge.",
39
40         /* ERROR_WOULD_LOSE_UNTRACKED_REMOVED */
41         "Untracked working tree file '%s' would be removed by merge.",
42
43         /* ERROR_BIND_OVERLAP */
44         "Entry '%s' overlaps with '%s'.  Cannot bind.",
45
46         /* ERROR_WOULD_LOSE_SUBMODULE */
47         "Submodule '%s' cannot checkout new HEAD.",
48
49         /* NB_UNPACK_TREES_ERROR_TYPES; just a meta value */
50         "",
51
52         /* WARNING_SPARSE_NOT_UPTODATE_FILE */
53         "Path '%s' not uptodate; will not remove from working tree.",
54
55         /* WARNING_SPARSE_UNMERGED_FILE */
56         "Path '%s' unmerged; will not remove from working tree.",
57
58         /* WARNING_SPARSE_ORPHANED_NOT_OVERWRITTEN */
59         "Path '%s' already present; will not overwrite with sparse update.",
60 };
61
62 #define ERRORMSG(o,type) \
63         ( ((o) && (o)->msgs[(type)]) \
64           ? ((o)->msgs[(type)])      \
65           : (unpack_plumbing_errors[(type)]) )
66
67 static const char *super_prefixed(const char *path)
68 {
69         /*
70          * It is necessary and sufficient to have two static buffers
71          * here, as the return value of this function is fed to
72          * error() using the unpack_*_errors[] templates we see above.
73          */
74         static struct strbuf buf[2] = {STRBUF_INIT, STRBUF_INIT};
75         static int super_prefix_len = -1;
76         static unsigned idx = ARRAY_SIZE(buf) - 1;
77
78         if (super_prefix_len < 0) {
79                 const char *super_prefix = get_super_prefix();
80                 if (!super_prefix) {
81                         super_prefix_len = 0;
82                 } else {
83                         int i;
84                         for (i = 0; i < ARRAY_SIZE(buf); i++)
85                                 strbuf_addstr(&buf[i], super_prefix);
86                         super_prefix_len = buf[0].len;
87                 }
88         }
89
90         if (!super_prefix_len)
91                 return path;
92
93         if (++idx >= ARRAY_SIZE(buf))
94                 idx = 0;
95
96         strbuf_setlen(&buf[idx], super_prefix_len);
97         strbuf_addstr(&buf[idx], path);
98
99         return buf[idx].buf;
100 }
101
102 void setup_unpack_trees_porcelain(struct unpack_trees_options *opts,
103                                   const char *cmd)
104 {
105         int i;
106         const char **msgs = opts->msgs;
107         const char *msg;
108
109         strvec_init(&opts->msgs_to_free);
110
111         if (!strcmp(cmd, "checkout"))
112                 msg = advice_commit_before_merge
113                       ? _("Your local changes to the following files would be overwritten by checkout:\n%%s"
114                           "Please commit your changes or stash them before you switch branches.")
115                       : _("Your local changes to the following files would be overwritten by checkout:\n%%s");
116         else if (!strcmp(cmd, "merge"))
117                 msg = advice_commit_before_merge
118                       ? _("Your local changes to the following files would be overwritten by merge:\n%%s"
119                           "Please commit your changes or stash them before you merge.")
120                       : _("Your local changes to the following files would be overwritten by merge:\n%%s");
121         else
122                 msg = advice_commit_before_merge
123                       ? _("Your local changes to the following files would be overwritten by %s:\n%%s"
124                           "Please commit your changes or stash them before you %s.")
125                       : _("Your local changes to the following files would be overwritten by %s:\n%%s");
126         msgs[ERROR_WOULD_OVERWRITE] = msgs[ERROR_NOT_UPTODATE_FILE] =
127                 strvec_pushf(&opts->msgs_to_free, msg, cmd, cmd);
128
129         msgs[ERROR_NOT_UPTODATE_DIR] =
130                 _("Updating the following directories would lose untracked files in them:\n%s");
131
132         if (!strcmp(cmd, "checkout"))
133                 msg = advice_commit_before_merge
134                       ? _("The following untracked working tree files would be removed by checkout:\n%%s"
135                           "Please move or remove them before you switch branches.")
136                       : _("The following untracked working tree files would be removed by checkout:\n%%s");
137         else if (!strcmp(cmd, "merge"))
138                 msg = advice_commit_before_merge
139                       ? _("The following untracked working tree files would be removed by merge:\n%%s"
140                           "Please move or remove them before you merge.")
141                       : _("The following untracked working tree files would be removed by merge:\n%%s");
142         else
143                 msg = advice_commit_before_merge
144                       ? _("The following untracked working tree files would be removed by %s:\n%%s"
145                           "Please move or remove them before you %s.")
146                       : _("The following untracked working tree files would be removed by %s:\n%%s");
147         msgs[ERROR_WOULD_LOSE_UNTRACKED_REMOVED] =
148                 strvec_pushf(&opts->msgs_to_free, msg, cmd, cmd);
149
150         if (!strcmp(cmd, "checkout"))
151                 msg = advice_commit_before_merge
152                       ? _("The following untracked working tree files would be overwritten by checkout:\n%%s"
153                           "Please move or remove them before you switch branches.")
154                       : _("The following untracked working tree files would be overwritten by checkout:\n%%s");
155         else if (!strcmp(cmd, "merge"))
156                 msg = advice_commit_before_merge
157                       ? _("The following untracked working tree files would be overwritten by merge:\n%%s"
158                           "Please move or remove them before you merge.")
159                       : _("The following untracked working tree files would be overwritten by merge:\n%%s");
160         else
161                 msg = advice_commit_before_merge
162                       ? _("The following untracked working tree files would be overwritten by %s:\n%%s"
163                           "Please move or remove them before you %s.")
164                       : _("The following untracked working tree files would be overwritten by %s:\n%%s");
165         msgs[ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN] =
166                 strvec_pushf(&opts->msgs_to_free, msg, cmd, cmd);
167
168         /*
169          * Special case: ERROR_BIND_OVERLAP refers to a pair of paths, we
170          * cannot easily display it as a list.
171          */
172         msgs[ERROR_BIND_OVERLAP] = _("Entry '%s' overlaps with '%s'.  Cannot bind.");
173
174         msgs[ERROR_WOULD_LOSE_SUBMODULE] =
175                 _("Cannot update submodule:\n%s");
176
177         msgs[WARNING_SPARSE_NOT_UPTODATE_FILE] =
178                 _("The following paths are not up to date and were left despite sparse patterns:\n%s");
179         msgs[WARNING_SPARSE_UNMERGED_FILE] =
180                 _("The following paths are unmerged and were left despite sparse patterns:\n%s");
181         msgs[WARNING_SPARSE_ORPHANED_NOT_OVERWRITTEN] =
182                 _("The following paths were already present and thus not updated despite sparse patterns:\n%s");
183
184         opts->show_all_errors = 1;
185         /* rejected paths may not have a static buffer */
186         for (i = 0; i < ARRAY_SIZE(opts->unpack_rejects); i++)
187                 opts->unpack_rejects[i].strdup_strings = 1;
188 }
189
190 void clear_unpack_trees_porcelain(struct unpack_trees_options *opts)
191 {
192         strvec_clear(&opts->msgs_to_free);
193         memset(opts->msgs, 0, sizeof(opts->msgs));
194 }
195
196 static int do_add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
197                          unsigned int set, unsigned int clear)
198 {
199         clear |= CE_HASHED;
200
201         if (set & CE_REMOVE)
202                 set |= CE_WT_REMOVE;
203
204         ce->ce_flags = (ce->ce_flags & ~clear) | set;
205         return add_index_entry(&o->result, ce,
206                                ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
207 }
208
209 static void add_entry(struct unpack_trees_options *o,
210                       const struct cache_entry *ce,
211                       unsigned int set, unsigned int clear)
212 {
213         do_add_entry(o, dup_cache_entry(ce, &o->result), set, clear);
214 }
215
216 /*
217  * add error messages on path <path>
218  * corresponding to the type <e> with the message <msg>
219  * indicating if it should be display in porcelain or not
220  */
221 static int add_rejected_path(struct unpack_trees_options *o,
222                              enum unpack_trees_error_types e,
223                              const char *path)
224 {
225         if (o->quiet)
226                 return -1;
227
228         if (!o->show_all_errors)
229                 return error(ERRORMSG(o, e), super_prefixed(path));
230
231         /*
232          * Otherwise, insert in a list for future display by
233          * display_(error|warning)_msgs()
234          */
235         string_list_append(&o->unpack_rejects[e], path);
236         return -1;
237 }
238
239 /*
240  * display all the error messages stored in a nice way
241  */
242 static void display_error_msgs(struct unpack_trees_options *o)
243 {
244         int e;
245         unsigned error_displayed = 0;
246         for (e = 0; e < NB_UNPACK_TREES_ERROR_TYPES; e++) {
247                 struct string_list *rejects = &o->unpack_rejects[e];
248
249                 if (rejects->nr > 0) {
250                         int i;
251                         struct strbuf path = STRBUF_INIT;
252
253                         error_displayed = 1;
254                         for (i = 0; i < rejects->nr; i++)
255                                 strbuf_addf(&path, "\t%s\n", rejects->items[i].string);
256                         error(ERRORMSG(o, e), super_prefixed(path.buf));
257                         strbuf_release(&path);
258                 }
259                 string_list_clear(rejects, 0);
260         }
261         if (error_displayed)
262                 fprintf(stderr, _("Aborting\n"));
263 }
264
265 /*
266  * display all the warning messages stored in a nice way
267  */
268 static void display_warning_msgs(struct unpack_trees_options *o)
269 {
270         int e;
271         unsigned warning_displayed = 0;
272         for (e = NB_UNPACK_TREES_ERROR_TYPES + 1;
273              e < NB_UNPACK_TREES_WARNING_TYPES; e++) {
274                 struct string_list *rejects = &o->unpack_rejects[e];
275
276                 if (rejects->nr > 0) {
277                         int i;
278                         struct strbuf path = STRBUF_INIT;
279
280                         warning_displayed = 1;
281                         for (i = 0; i < rejects->nr; i++)
282                                 strbuf_addf(&path, "\t%s\n", rejects->items[i].string);
283                         warning(ERRORMSG(o, e), super_prefixed(path.buf));
284                         strbuf_release(&path);
285                 }
286                 string_list_clear(rejects, 0);
287         }
288         if (warning_displayed)
289                 fprintf(stderr, _("After fixing the above paths, you may want to run `git sparse-checkout reapply`.\n"));
290 }
291 static int check_submodule_move_head(const struct cache_entry *ce,
292                                      const char *old_id,
293                                      const char *new_id,
294                                      struct unpack_trees_options *o)
295 {
296         unsigned flags = SUBMODULE_MOVE_HEAD_DRY_RUN;
297         const struct submodule *sub = submodule_from_ce(ce);
298
299         if (!sub)
300                 return 0;
301
302         if (o->reset)
303                 flags |= SUBMODULE_MOVE_HEAD_FORCE;
304
305         if (submodule_move_head(ce->name, old_id, new_id, flags))
306                 return add_rejected_path(o, ERROR_WOULD_LOSE_SUBMODULE, ce->name);
307         return 0;
308 }
309
310 /*
311  * Perform the loading of the repository's gitmodules file.  This function is
312  * used by 'check_update()' to perform loading of the gitmodules file in two
313  * different situations:
314  * (1) before removing entries from the working tree if the gitmodules file has
315  *     been marked for removal.  This situation is specified by 'state' == NULL.
316  * (2) before checking out entries to the working tree if the gitmodules file
317  *     has been marked for update.  This situation is specified by 'state' != NULL.
318  */
319 static void load_gitmodules_file(struct index_state *index,
320                                  struct checkout *state)
321 {
322         int pos = index_name_pos(index, GITMODULES_FILE, strlen(GITMODULES_FILE));
323
324         if (pos >= 0) {
325                 struct cache_entry *ce = index->cache[pos];
326                 if (!state && ce->ce_flags & CE_WT_REMOVE) {
327                         repo_read_gitmodules(the_repository, 0);
328                 } else if (state && (ce->ce_flags & CE_UPDATE)) {
329                         submodule_free(the_repository);
330                         checkout_entry(ce, state, NULL, NULL);
331                         repo_read_gitmodules(the_repository, 0);
332                 }
333         }
334 }
335
336 static struct progress *get_progress(struct unpack_trees_options *o,
337                                      struct index_state *index)
338 {
339         unsigned cnt = 0, total = 0;
340
341         if (!o->update || !o->verbose_update)
342                 return NULL;
343
344         for (; cnt < index->cache_nr; cnt++) {
345                 const struct cache_entry *ce = index->cache[cnt];
346                 if (ce->ce_flags & (CE_UPDATE | CE_WT_REMOVE))
347                         total++;
348         }
349
350         return start_delayed_progress(_("Updating files"), total);
351 }
352
353 static void setup_collided_checkout_detection(struct checkout *state,
354                                               struct index_state *index)
355 {
356         int i;
357
358         state->clone = 1;
359         for (i = 0; i < index->cache_nr; i++)
360                 index->cache[i]->ce_flags &= ~CE_MATCHED;
361 }
362
363 static void report_collided_checkout(struct index_state *index)
364 {
365         struct string_list list = STRING_LIST_INIT_NODUP;
366         int i;
367
368         for (i = 0; i < index->cache_nr; i++) {
369                 struct cache_entry *ce = index->cache[i];
370
371                 if (!(ce->ce_flags & CE_MATCHED))
372                         continue;
373
374                 string_list_append(&list, ce->name);
375                 ce->ce_flags &= ~CE_MATCHED;
376         }
377
378         list.cmp = fspathcmp;
379         string_list_sort(&list);
380
381         if (list.nr) {
382                 warning(_("the following paths have collided (e.g. case-sensitive paths\n"
383                           "on a case-insensitive filesystem) and only one from the same\n"
384                           "colliding group is in the working tree:\n"));
385
386                 for (i = 0; i < list.nr; i++)
387                         fprintf(stderr, "  '%s'\n", list.items[i].string);
388         }
389
390         string_list_clear(&list, 0);
391 }
392
393 static int check_updates(struct unpack_trees_options *o,
394                          struct index_state *index)
395 {
396         unsigned cnt = 0;
397         int errs = 0;
398         struct progress *progress;
399         struct checkout state = CHECKOUT_INIT;
400         int i;
401
402         trace_performance_enter();
403         state.force = 1;
404         state.quiet = 1;
405         state.refresh_cache = 1;
406         state.istate = index;
407         clone_checkout_metadata(&state.meta, &o->meta, NULL);
408
409         if (!o->update || o->dry_run) {
410                 remove_marked_cache_entries(index, 0);
411                 trace_performance_leave("check_updates");
412                 return 0;
413         }
414
415         if (o->clone)
416                 setup_collided_checkout_detection(&state, index);
417
418         progress = get_progress(o, index);
419
420         git_attr_set_direction(GIT_ATTR_CHECKOUT);
421
422         if (should_update_submodules())
423                 load_gitmodules_file(index, NULL);
424
425         for (i = 0; i < index->cache_nr; i++) {
426                 const struct cache_entry *ce = index->cache[i];
427
428                 if (ce->ce_flags & CE_WT_REMOVE) {
429                         display_progress(progress, ++cnt);
430                         unlink_entry(ce);
431                 }
432         }
433
434         remove_marked_cache_entries(index, 0);
435         remove_scheduled_dirs();
436
437         if (should_update_submodules())
438                 load_gitmodules_file(index, &state);
439
440         enable_delayed_checkout(&state);
441         if (has_promisor_remote()) {
442                 /*
443                  * Prefetch the objects that are to be checked out in the loop
444                  * below.
445                  */
446                 struct oid_array to_fetch = OID_ARRAY_INIT;
447                 for (i = 0; i < index->cache_nr; i++) {
448                         struct cache_entry *ce = index->cache[i];
449
450                         if (!(ce->ce_flags & CE_UPDATE) ||
451                             S_ISGITLINK(ce->ce_mode))
452                                 continue;
453                         if (!oid_object_info_extended(the_repository, &ce->oid,
454                                                       NULL,
455                                                       OBJECT_INFO_FOR_PREFETCH))
456                                 continue;
457                         oid_array_append(&to_fetch, &ce->oid);
458                 }
459                 promisor_remote_get_direct(the_repository,
460                                            to_fetch.oid, to_fetch.nr);
461                 oid_array_clear(&to_fetch);
462         }
463         for (i = 0; i < index->cache_nr; i++) {
464                 struct cache_entry *ce = index->cache[i];
465
466                 if (ce->ce_flags & CE_UPDATE) {
467                         if (ce->ce_flags & CE_WT_REMOVE)
468                                 BUG("both update and delete flags are set on %s",
469                                     ce->name);
470                         display_progress(progress, ++cnt);
471                         ce->ce_flags &= ~CE_UPDATE;
472                         errs |= checkout_entry(ce, &state, NULL, NULL);
473                 }
474         }
475         stop_progress(&progress);
476         errs |= finish_delayed_checkout(&state, NULL);
477         git_attr_set_direction(GIT_ATTR_CHECKIN);
478
479         if (o->clone)
480                 report_collided_checkout(index);
481
482         trace_performance_leave("check_updates");
483         return errs != 0;
484 }
485
486 static int verify_uptodate_sparse(const struct cache_entry *ce,
487                                   struct unpack_trees_options *o);
488 static int verify_absent_sparse(const struct cache_entry *ce,
489                                 enum unpack_trees_error_types,
490                                 struct unpack_trees_options *o);
491
492 static int apply_sparse_checkout(struct index_state *istate,
493                                  struct cache_entry *ce,
494                                  struct unpack_trees_options *o)
495 {
496         int was_skip_worktree = ce_skip_worktree(ce);
497
498         if (ce->ce_flags & CE_NEW_SKIP_WORKTREE)
499                 ce->ce_flags |= CE_SKIP_WORKTREE;
500         else
501                 ce->ce_flags &= ~CE_SKIP_WORKTREE;
502         if (was_skip_worktree != ce_skip_worktree(ce)) {
503                 ce->ce_flags |= CE_UPDATE_IN_BASE;
504                 mark_fsmonitor_invalid(istate, ce);
505                 istate->cache_changed |= CE_ENTRY_CHANGED;
506         }
507
508         /*
509          * if (!was_skip_worktree && !ce_skip_worktree()) {
510          *      This is perfectly normal. Move on;
511          * }
512          */
513
514         /*
515          * Merge strategies may set CE_UPDATE|CE_REMOVE outside checkout
516          * area as a result of ce_skip_worktree() shortcuts in
517          * verify_absent() and verify_uptodate().
518          * Make sure they don't modify worktree if they are already
519          * outside checkout area
520          */
521         if (was_skip_worktree && ce_skip_worktree(ce)) {
522                 ce->ce_flags &= ~CE_UPDATE;
523
524                 /*
525                  * By default, when CE_REMOVE is on, CE_WT_REMOVE is also
526                  * on to get that file removed from both index and worktree.
527                  * If that file is already outside worktree area, don't
528                  * bother remove it.
529                  */
530                 if (ce->ce_flags & CE_REMOVE)
531                         ce->ce_flags &= ~CE_WT_REMOVE;
532         }
533
534         if (!was_skip_worktree && ce_skip_worktree(ce)) {
535                 /*
536                  * If CE_UPDATE is set, verify_uptodate() must be called already
537                  * also stat info may have lost after merged_entry() so calling
538                  * verify_uptodate() again may fail
539                  */
540                 if (!(ce->ce_flags & CE_UPDATE) &&
541                     verify_uptodate_sparse(ce, o)) {
542                         ce->ce_flags &= ~CE_SKIP_WORKTREE;
543                         return -1;
544                 }
545                 ce->ce_flags |= CE_WT_REMOVE;
546                 ce->ce_flags &= ~CE_UPDATE;
547         }
548         if (was_skip_worktree && !ce_skip_worktree(ce)) {
549                 if (verify_absent_sparse(ce, WARNING_SPARSE_ORPHANED_NOT_OVERWRITTEN, o))
550                         return -1;
551                 ce->ce_flags |= CE_UPDATE;
552         }
553         return 0;
554 }
555
556 static int warn_conflicted_path(struct index_state *istate,
557                                 int i,
558                                 struct unpack_trees_options *o)
559 {
560         char *conflicting_path = istate->cache[i]->name;
561         int count = 0;
562
563         add_rejected_path(o, WARNING_SPARSE_UNMERGED_FILE, conflicting_path);
564
565         /* Find out how many higher stage entries are at same path */
566         while ((++count) + i < istate->cache_nr &&
567                !strcmp(conflicting_path, istate->cache[count + i]->name))
568                 ; /* do nothing */
569
570         return count;
571 }
572
573 static inline int call_unpack_fn(const struct cache_entry * const *src,
574                                  struct unpack_trees_options *o)
575 {
576         int ret = o->fn(src, o);
577         if (ret > 0)
578                 ret = 0;
579         return ret;
580 }
581
582 static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)
583 {
584         ce->ce_flags |= CE_UNPACKED;
585
586         if (o->cache_bottom < o->src_index->cache_nr &&
587             o->src_index->cache[o->cache_bottom] == ce) {
588                 int bottom = o->cache_bottom;
589                 while (bottom < o->src_index->cache_nr &&
590                        o->src_index->cache[bottom]->ce_flags & CE_UNPACKED)
591                         bottom++;
592                 o->cache_bottom = bottom;
593         }
594 }
595
596 static void mark_all_ce_unused(struct index_state *index)
597 {
598         int i;
599         for (i = 0; i < index->cache_nr; i++)
600                 index->cache[i]->ce_flags &= ~(CE_UNPACKED | CE_ADDED | CE_NEW_SKIP_WORKTREE);
601 }
602
603 static int locate_in_src_index(const struct cache_entry *ce,
604                                struct unpack_trees_options *o)
605 {
606         struct index_state *index = o->src_index;
607         int len = ce_namelen(ce);
608         int pos = index_name_pos(index, ce->name, len);
609         if (pos < 0)
610                 pos = -1 - pos;
611         return pos;
612 }
613
614 /*
615  * We call unpack_index_entry() with an unmerged cache entry
616  * only in diff-index, and it wants a single callback.  Skip
617  * the other unmerged entry with the same name.
618  */
619 static void mark_ce_used_same_name(struct cache_entry *ce,
620                                    struct unpack_trees_options *o)
621 {
622         struct index_state *index = o->src_index;
623         int len = ce_namelen(ce);
624         int pos;
625
626         for (pos = locate_in_src_index(ce, o); pos < index->cache_nr; pos++) {
627                 struct cache_entry *next = index->cache[pos];
628                 if (len != ce_namelen(next) ||
629                     memcmp(ce->name, next->name, len))
630                         break;
631                 mark_ce_used(next, o);
632         }
633 }
634
635 static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)
636 {
637         const struct index_state *index = o->src_index;
638         int pos = o->cache_bottom;
639
640         while (pos < index->cache_nr) {
641                 struct cache_entry *ce = index->cache[pos];
642                 if (!(ce->ce_flags & CE_UNPACKED))
643                         return ce;
644                 pos++;
645         }
646         return NULL;
647 }
648
649 static void add_same_unmerged(const 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 = index_name_pos(index, ce->name, len);
655
656         if (0 <= pos)
657                 die("programming error in a caller of mark_ce_used_same_name");
658         for (pos = -pos - 1; pos < index->cache_nr; pos++) {
659                 struct cache_entry *next = index->cache[pos];
660                 if (len != ce_namelen(next) ||
661                     memcmp(ce->name, next->name, len))
662                         break;
663                 add_entry(o, next, 0, 0);
664                 mark_ce_used(next, o);
665         }
666 }
667
668 static int unpack_index_entry(struct cache_entry *ce,
669                               struct unpack_trees_options *o)
670 {
671         const struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
672         int ret;
673
674         src[0] = ce;
675
676         mark_ce_used(ce, o);
677         if (ce_stage(ce)) {
678                 if (o->skip_unmerged) {
679                         add_entry(o, ce, 0, 0);
680                         return 0;
681                 }
682         }
683         ret = call_unpack_fn(src, o);
684         if (ce_stage(ce))
685                 mark_ce_used_same_name(ce, o);
686         return ret;
687 }
688
689 static int find_cache_pos(struct traverse_info *, const char *p, size_t len);
690
691 static void restore_cache_bottom(struct traverse_info *info, int bottom)
692 {
693         struct unpack_trees_options *o = info->data;
694
695         if (o->diff_index_cached)
696                 return;
697         o->cache_bottom = bottom;
698 }
699
700 static int switch_cache_bottom(struct traverse_info *info)
701 {
702         struct unpack_trees_options *o = info->data;
703         int ret, pos;
704
705         if (o->diff_index_cached)
706                 return 0;
707         ret = o->cache_bottom;
708         pos = find_cache_pos(info->prev, info->name, info->namelen);
709
710         if (pos < -1)
711                 o->cache_bottom = -2 - pos;
712         else if (pos < 0)
713                 o->cache_bottom = o->src_index->cache_nr;
714         return ret;
715 }
716
717 static inline int are_same_oid(struct name_entry *name_j, struct name_entry *name_k)
718 {
719         return !is_null_oid(&name_j->oid) && !is_null_oid(&name_k->oid) && oideq(&name_j->oid, &name_k->oid);
720 }
721
722 static int all_trees_same_as_cache_tree(int n, unsigned long dirmask,
723                                         struct name_entry *names,
724                                         struct traverse_info *info)
725 {
726         struct unpack_trees_options *o = info->data;
727         int i;
728
729         if (!o->merge || dirmask != ((1 << n) - 1))
730                 return 0;
731
732         for (i = 1; i < n; i++)
733                 if (!are_same_oid(names, names + i))
734                         return 0;
735
736         return cache_tree_matches_traversal(o->src_index->cache_tree, names, info);
737 }
738
739 static int index_pos_by_traverse_info(struct name_entry *names,
740                                       struct traverse_info *info)
741 {
742         struct unpack_trees_options *o = info->data;
743         struct strbuf name = STRBUF_INIT;
744         int pos;
745
746         strbuf_make_traverse_path(&name, info, names->path, names->pathlen);
747         strbuf_addch(&name, '/');
748         pos = index_name_pos(o->src_index, name.buf, name.len);
749         if (pos >= 0)
750                 BUG("This is a directory and should not exist in index");
751         pos = -pos - 1;
752         if (pos >= o->src_index->cache_nr ||
753             !starts_with(o->src_index->cache[pos]->name, name.buf) ||
754             (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name.buf)))
755                 BUG("pos %d doesn't point to the first entry of %s in index",
756                     pos, name.buf);
757         strbuf_release(&name);
758         return pos;
759 }
760
761 /*
762  * Fast path if we detect that all trees are the same as cache-tree at this
763  * path. We'll walk these trees in an iterative loop using cache-tree/index
764  * instead of ODB since we already know what these trees contain.
765  */
766 static int traverse_by_cache_tree(int pos, int nr_entries, int nr_names,
767                                   struct traverse_info *info)
768 {
769         struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
770         struct unpack_trees_options *o = info->data;
771         struct cache_entry *tree_ce = NULL;
772         int ce_len = 0;
773         int i, d;
774
775         if (!o->merge)
776                 BUG("We need cache-tree to do this optimization");
777
778         /*
779          * Do what unpack_callback() and unpack_nondirectories() normally
780          * do. But we walk all paths in an iterative loop instead.
781          *
782          * D/F conflicts and higher stage entries are not a concern
783          * because cache-tree would be invalidated and we would never
784          * get here in the first place.
785          */
786         for (i = 0; i < nr_entries; i++) {
787                 int new_ce_len, len, rc;
788
789                 src[0] = o->src_index->cache[pos + i];
790
791                 len = ce_namelen(src[0]);
792                 new_ce_len = cache_entry_size(len);
793
794                 if (new_ce_len > ce_len) {
795                         new_ce_len <<= 1;
796                         tree_ce = xrealloc(tree_ce, new_ce_len);
797                         memset(tree_ce, 0, new_ce_len);
798                         ce_len = new_ce_len;
799
800                         tree_ce->ce_flags = create_ce_flags(0);
801
802                         for (d = 1; d <= nr_names; d++)
803                                 src[d] = tree_ce;
804                 }
805
806                 tree_ce->ce_mode = src[0]->ce_mode;
807                 tree_ce->ce_namelen = len;
808                 oidcpy(&tree_ce->oid, &src[0]->oid);
809                 memcpy(tree_ce->name, src[0]->name, len + 1);
810
811                 rc = call_unpack_fn((const struct cache_entry * const *)src, o);
812                 if (rc < 0) {
813                         free(tree_ce);
814                         return rc;
815                 }
816
817                 mark_ce_used(src[0], o);
818         }
819         free(tree_ce);
820         if (o->debug_unpack)
821                 printf("Unpacked %d entries from %s to %s using cache-tree\n",
822                        nr_entries,
823                        o->src_index->cache[pos]->name,
824                        o->src_index->cache[pos + nr_entries - 1]->name);
825         return 0;
826 }
827
828 static int traverse_trees_recursive(int n, unsigned long dirmask,
829                                     unsigned long df_conflicts,
830                                     struct name_entry *names,
831                                     struct traverse_info *info)
832 {
833         struct unpack_trees_options *o = info->data;
834         int i, ret, bottom;
835         int nr_buf = 0;
836         struct tree_desc t[MAX_UNPACK_TREES];
837         void *buf[MAX_UNPACK_TREES];
838         struct traverse_info newinfo;
839         struct name_entry *p;
840         int nr_entries;
841
842         nr_entries = all_trees_same_as_cache_tree(n, dirmask, names, info);
843         if (nr_entries > 0) {
844                 int pos = index_pos_by_traverse_info(names, info);
845
846                 if (!o->merge || df_conflicts)
847                         BUG("Wrong condition to get here buddy");
848
849                 /*
850                  * All entries up to 'pos' must have been processed
851                  * (i.e. marked CE_UNPACKED) at this point. But to be safe,
852                  * save and restore cache_bottom anyway to not miss
853                  * unprocessed entries before 'pos'.
854                  */
855                 bottom = o->cache_bottom;
856                 ret = traverse_by_cache_tree(pos, nr_entries, n, info);
857                 o->cache_bottom = bottom;
858                 return ret;
859         }
860
861         p = names;
862         while (!p->mode)
863                 p++;
864
865         newinfo = *info;
866         newinfo.prev = info;
867         newinfo.pathspec = info->pathspec;
868         newinfo.name = p->path;
869         newinfo.namelen = p->pathlen;
870         newinfo.mode = p->mode;
871         newinfo.pathlen = st_add3(newinfo.pathlen, tree_entry_len(p), 1);
872         newinfo.df_conflicts |= df_conflicts;
873
874         /*
875          * Fetch the tree from the ODB for each peer directory in the
876          * n commits.
877          *
878          * For 2- and 3-way traversals, we try to avoid hitting the
879          * ODB twice for the same OID.  This should yield a nice speed
880          * up in checkouts and merges when the commits are similar.
881          *
882          * We don't bother doing the full O(n^2) search for larger n,
883          * because wider traversals don't happen that often and we
884          * avoid the search setup.
885          *
886          * When 2 peer OIDs are the same, we just copy the tree
887          * descriptor data.  This implicitly borrows the buffer
888          * data from the earlier cell.
889          */
890         for (i = 0; i < n; i++, dirmask >>= 1) {
891                 if (i > 0 && are_same_oid(&names[i], &names[i - 1]))
892                         t[i] = t[i - 1];
893                 else if (i > 1 && are_same_oid(&names[i], &names[i - 2]))
894                         t[i] = t[i - 2];
895                 else {
896                         const struct object_id *oid = NULL;
897                         if (dirmask & 1)
898                                 oid = &names[i].oid;
899                         buf[nr_buf++] = fill_tree_descriptor(the_repository, t + i, oid);
900                 }
901         }
902
903         bottom = switch_cache_bottom(&newinfo);
904         ret = traverse_trees(o->src_index, n, t, &newinfo);
905         restore_cache_bottom(&newinfo, bottom);
906
907         for (i = 0; i < nr_buf; i++)
908                 free(buf[i]);
909
910         return ret;
911 }
912
913 /*
914  * Compare the traverse-path to the cache entry without actually
915  * having to generate the textual representation of the traverse
916  * path.
917  *
918  * NOTE! This *only* compares up to the size of the traverse path
919  * itself - the caller needs to do the final check for the cache
920  * entry having more data at the end!
921  */
922 static int do_compare_entry_piecewise(const struct cache_entry *ce,
923                                       const struct traverse_info *info,
924                                       const char *name, size_t namelen,
925                                       unsigned mode)
926 {
927         int pathlen, ce_len;
928         const char *ce_name;
929
930         if (info->prev) {
931                 int cmp = do_compare_entry_piecewise(ce, info->prev,
932                                                      info->name, info->namelen,
933                                                      info->mode);
934                 if (cmp)
935                         return cmp;
936         }
937         pathlen = info->pathlen;
938         ce_len = ce_namelen(ce);
939
940         /* If ce_len < pathlen then we must have previously hit "name == directory" entry */
941         if (ce_len < pathlen)
942                 return -1;
943
944         ce_len -= pathlen;
945         ce_name = ce->name + pathlen;
946
947         return df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);
948 }
949
950 static int do_compare_entry(const struct cache_entry *ce,
951                             const struct traverse_info *info,
952                             const char *name, size_t namelen,
953                             unsigned mode)
954 {
955         int pathlen, ce_len;
956         const char *ce_name;
957         int cmp;
958
959         /*
960          * If we have not precomputed the traverse path, it is quicker
961          * to avoid doing so.  But if we have precomputed it,
962          * it is quicker to use the precomputed version.
963          */
964         if (!info->traverse_path)
965                 return do_compare_entry_piecewise(ce, info, name, namelen, mode);
966
967         cmp = strncmp(ce->name, info->traverse_path, info->pathlen);
968         if (cmp)
969                 return cmp;
970
971         pathlen = info->pathlen;
972         ce_len = ce_namelen(ce);
973
974         if (ce_len < pathlen)
975                 return -1;
976
977         ce_len -= pathlen;
978         ce_name = ce->name + pathlen;
979
980         return df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);
981 }
982
983 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
984 {
985         int cmp = do_compare_entry(ce, info, n->path, n->pathlen, n->mode);
986         if (cmp)
987                 return cmp;
988
989         /*
990          * Even if the beginning compared identically, the ce should
991          * compare as bigger than a directory leading up to it!
992          */
993         return ce_namelen(ce) > traverse_path_len(info, tree_entry_len(n));
994 }
995
996 static int ce_in_traverse_path(const struct cache_entry *ce,
997                                const struct traverse_info *info)
998 {
999         if (!info->prev)
1000                 return 1;
1001         if (do_compare_entry(ce, info->prev,
1002                              info->name, info->namelen, info->mode))
1003                 return 0;
1004         /*
1005          * If ce (blob) is the same name as the path (which is a tree
1006          * we will be descending into), it won't be inside it.
1007          */
1008         return (info->pathlen < ce_namelen(ce));
1009 }
1010
1011 static struct cache_entry *create_ce_entry(const struct traverse_info *info,
1012         const struct name_entry *n,
1013         int stage,
1014         struct index_state *istate,
1015         int is_transient)
1016 {
1017         size_t len = traverse_path_len(info, tree_entry_len(n));
1018         struct cache_entry *ce =
1019                 is_transient ?
1020                 make_empty_transient_cache_entry(len) :
1021                 make_empty_cache_entry(istate, len);
1022
1023         ce->ce_mode = create_ce_mode(n->mode);
1024         ce->ce_flags = create_ce_flags(stage);
1025         ce->ce_namelen = len;
1026         oidcpy(&ce->oid, &n->oid);
1027         /* len+1 because the cache_entry allocates space for NUL */
1028         make_traverse_path(ce->name, len + 1, info, n->path, n->pathlen);
1029
1030         return ce;
1031 }
1032
1033 /*
1034  * Note that traverse_by_cache_tree() duplicates some logic in this function
1035  * without actually calling it. If you change the logic here you may need to
1036  * check and change there as well.
1037  */
1038 static int unpack_nondirectories(int n, unsigned long mask,
1039                                  unsigned long dirmask,
1040                                  struct cache_entry **src,
1041                                  const struct name_entry *names,
1042                                  const struct traverse_info *info)
1043 {
1044         int i;
1045         struct unpack_trees_options *o = info->data;
1046         unsigned long conflicts = info->df_conflicts | dirmask;
1047
1048         /* Do we have *only* directories? Nothing to do */
1049         if (mask == dirmask && !src[0])
1050                 return 0;
1051
1052         /*
1053          * Ok, we've filled in up to any potential index entry in src[0],
1054          * now do the rest.
1055          */
1056         for (i = 0; i < n; i++) {
1057                 int stage;
1058                 unsigned int bit = 1ul << i;
1059                 if (conflicts & bit) {
1060                         src[i + o->merge] = o->df_conflict_entry;
1061                         continue;
1062                 }
1063                 if (!(mask & bit))
1064                         continue;
1065                 if (!o->merge)
1066                         stage = 0;
1067                 else if (i + 1 < o->head_idx)
1068                         stage = 1;
1069                 else if (i + 1 > o->head_idx)
1070                         stage = 3;
1071                 else
1072                         stage = 2;
1073
1074                 /*
1075                  * If the merge bit is set, then the cache entries are
1076                  * discarded in the following block.  In this case,
1077                  * construct "transient" cache_entries, as they are
1078                  * not stored in the index.  otherwise construct the
1079                  * cache entry from the index aware logic.
1080                  */
1081                 src[i + o->merge] = create_ce_entry(info, names + i, stage, &o->result, o->merge);
1082         }
1083
1084         if (o->merge) {
1085                 int rc = call_unpack_fn((const struct cache_entry * const *)src,
1086                                         o);
1087                 for (i = 0; i < n; i++) {
1088                         struct cache_entry *ce = src[i + o->merge];
1089                         if (ce != o->df_conflict_entry)
1090                                 discard_cache_entry(ce);
1091                 }
1092                 return rc;
1093         }
1094
1095         for (i = 0; i < n; i++)
1096                 if (src[i] && src[i] != o->df_conflict_entry)
1097                         if (do_add_entry(o, src[i], 0, 0))
1098                                 return -1;
1099
1100         return 0;
1101 }
1102
1103 static int unpack_failed(struct unpack_trees_options *o, const char *message)
1104 {
1105         discard_index(&o->result);
1106         if (!o->quiet && !o->exiting_early) {
1107                 if (message)
1108                         return error("%s", message);
1109                 return -1;
1110         }
1111         return -1;
1112 }
1113
1114 /*
1115  * The tree traversal is looking at name p.  If we have a matching entry,
1116  * return it.  If name p is a directory in the index, do not return
1117  * anything, as we will want to match it when the traversal descends into
1118  * the directory.
1119  */
1120 static int find_cache_pos(struct traverse_info *info,
1121                           const char *p, size_t p_len)
1122 {
1123         int pos;
1124         struct unpack_trees_options *o = info->data;
1125         struct index_state *index = o->src_index;
1126         int pfxlen = info->pathlen;
1127
1128         for (pos = o->cache_bottom; pos < index->cache_nr; pos++) {
1129                 const struct cache_entry *ce = index->cache[pos];
1130                 const char *ce_name, *ce_slash;
1131                 int cmp, ce_len;
1132
1133                 if (ce->ce_flags & CE_UNPACKED) {
1134                         /*
1135                          * cache_bottom entry is already unpacked, so
1136                          * we can never match it; don't check it
1137                          * again.
1138                          */
1139                         if (pos == o->cache_bottom)
1140                                 ++o->cache_bottom;
1141                         continue;
1142                 }
1143                 if (!ce_in_traverse_path(ce, info)) {
1144                         /*
1145                          * Check if we can skip future cache checks
1146                          * (because we're already past all possible
1147                          * entries in the traverse path).
1148                          */
1149                         if (info->traverse_path) {
1150                                 if (strncmp(ce->name, info->traverse_path,
1151                                             info->pathlen) > 0)
1152                                         break;
1153                         }
1154                         continue;
1155                 }
1156                 ce_name = ce->name + pfxlen;
1157                 ce_slash = strchr(ce_name, '/');
1158                 if (ce_slash)
1159                         ce_len = ce_slash - ce_name;
1160                 else
1161                         ce_len = ce_namelen(ce) - pfxlen;
1162                 cmp = name_compare(p, p_len, ce_name, ce_len);
1163                 /*
1164                  * Exact match; if we have a directory we need to
1165                  * delay returning it.
1166                  */
1167                 if (!cmp)
1168                         return ce_slash ? -2 - pos : pos;
1169                 if (0 < cmp)
1170                         continue; /* keep looking */
1171                 /*
1172                  * ce_name sorts after p->path; could it be that we
1173                  * have files under p->path directory in the index?
1174                  * E.g.  ce_name == "t-i", and p->path == "t"; we may
1175                  * have "t/a" in the index.
1176                  */
1177                 if (p_len < ce_len && !memcmp(ce_name, p, p_len) &&
1178                     ce_name[p_len] < '/')
1179                         continue; /* keep looking */
1180                 break;
1181         }
1182         return -1;
1183 }
1184
1185 static struct cache_entry *find_cache_entry(struct traverse_info *info,
1186                                             const struct name_entry *p)
1187 {
1188         int pos = find_cache_pos(info, p->path, p->pathlen);
1189         struct unpack_trees_options *o = info->data;
1190
1191         if (0 <= pos)
1192                 return o->src_index->cache[pos];
1193         else
1194                 return NULL;
1195 }
1196
1197 static void debug_path(struct traverse_info *info)
1198 {
1199         if (info->prev) {
1200                 debug_path(info->prev);
1201                 if (*info->prev->name)
1202                         putchar('/');
1203         }
1204         printf("%s", info->name);
1205 }
1206
1207 static void debug_name_entry(int i, struct name_entry *n)
1208 {
1209         printf("ent#%d %06o %s\n", i,
1210                n->path ? n->mode : 0,
1211                n->path ? n->path : "(missing)");
1212 }
1213
1214 static void debug_unpack_callback(int n,
1215                                   unsigned long mask,
1216                                   unsigned long dirmask,
1217                                   struct name_entry *names,
1218                                   struct traverse_info *info)
1219 {
1220         int i;
1221         printf("* unpack mask %lu, dirmask %lu, cnt %d ",
1222                mask, dirmask, n);
1223         debug_path(info);
1224         putchar('\n');
1225         for (i = 0; i < n; i++)
1226                 debug_name_entry(i, names + i);
1227 }
1228
1229 /*
1230  * Note that traverse_by_cache_tree() duplicates some logic in this function
1231  * without actually calling it. If you change the logic here you may need to
1232  * check and change there as well.
1233  */
1234 static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
1235 {
1236         struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
1237         struct unpack_trees_options *o = info->data;
1238         const struct name_entry *p = names;
1239
1240         /* Find first entry with a real name (we could use "mask" too) */
1241         while (!p->mode)
1242                 p++;
1243
1244         if (o->debug_unpack)
1245                 debug_unpack_callback(n, mask, dirmask, names, info);
1246
1247         /* Are we supposed to look at the index too? */
1248         if (o->merge) {
1249                 while (1) {
1250                         int cmp;
1251                         struct cache_entry *ce;
1252
1253                         if (o->diff_index_cached)
1254                                 ce = next_cache_entry(o);
1255                         else
1256                                 ce = find_cache_entry(info, p);
1257
1258                         if (!ce)
1259                                 break;
1260                         cmp = compare_entry(ce, info, p);
1261                         if (cmp < 0) {
1262                                 if (unpack_index_entry(ce, o) < 0)
1263                                         return unpack_failed(o, NULL);
1264                                 continue;
1265                         }
1266                         if (!cmp) {
1267                                 if (ce_stage(ce)) {
1268                                         /*
1269                                          * If we skip unmerged index
1270                                          * entries, we'll skip this
1271                                          * entry *and* the tree
1272                                          * entries associated with it!
1273                                          */
1274                                         if (o->skip_unmerged) {
1275                                                 add_same_unmerged(ce, o);
1276                                                 return mask;
1277                                         }
1278                                 }
1279                                 src[0] = ce;
1280                         }
1281                         break;
1282                 }
1283         }
1284
1285         if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
1286                 return -1;
1287
1288         if (o->merge && src[0]) {
1289                 if (ce_stage(src[0]))
1290                         mark_ce_used_same_name(src[0], o);
1291                 else
1292                         mark_ce_used(src[0], o);
1293         }
1294
1295         /* Now handle any directories.. */
1296         if (dirmask) {
1297                 /* special case: "diff-index --cached" looking at a tree */
1298                 if (o->diff_index_cached &&
1299                     n == 1 && dirmask == 1 && S_ISDIR(names->mode)) {
1300                         int matches;
1301                         matches = cache_tree_matches_traversal(o->src_index->cache_tree,
1302                                                                names, info);
1303                         /*
1304                          * Everything under the name matches; skip the
1305                          * entire hierarchy.  diff_index_cached codepath
1306                          * special cases D/F conflicts in such a way that
1307                          * it does not do any look-ahead, so this is safe.
1308                          */
1309                         if (matches) {
1310                                 o->cache_bottom += matches;
1311                                 return mask;
1312                         }
1313                 }
1314
1315                 if (traverse_trees_recursive(n, dirmask, mask & ~dirmask,
1316                                              names, info) < 0)
1317                         return -1;
1318                 return mask;
1319         }
1320
1321         return mask;
1322 }
1323
1324 static int clear_ce_flags_1(struct index_state *istate,
1325                             struct cache_entry **cache, int nr,
1326                             struct strbuf *prefix,
1327                             int select_mask, int clear_mask,
1328                             struct pattern_list *pl,
1329                             enum pattern_match_result default_match,
1330                             int progress_nr);
1331
1332 /* Whole directory matching */
1333 static int clear_ce_flags_dir(struct index_state *istate,
1334                               struct cache_entry **cache, int nr,
1335                               struct strbuf *prefix,
1336                               char *basename,
1337                               int select_mask, int clear_mask,
1338                               struct pattern_list *pl,
1339                               enum pattern_match_result default_match,
1340                               int progress_nr)
1341 {
1342         struct cache_entry **cache_end;
1343         int dtype = DT_DIR;
1344         int rc;
1345         enum pattern_match_result ret, orig_ret;
1346         orig_ret = path_matches_pattern_list(prefix->buf, prefix->len,
1347                                              basename, &dtype, pl, istate);
1348
1349         strbuf_addch(prefix, '/');
1350
1351         /* If undecided, use matching result of parent dir in defval */
1352         if (orig_ret == UNDECIDED)
1353                 ret = default_match;
1354         else
1355                 ret = orig_ret;
1356
1357         for (cache_end = cache; cache_end != cache + nr; cache_end++) {
1358                 struct cache_entry *ce = *cache_end;
1359                 if (strncmp(ce->name, prefix->buf, prefix->len))
1360                         break;
1361         }
1362
1363         if (pl->use_cone_patterns && orig_ret == MATCHED_RECURSIVE) {
1364                 struct cache_entry **ce = cache;
1365                 rc = cache_end - cache;
1366
1367                 while (ce < cache_end) {
1368                         (*ce)->ce_flags &= ~clear_mask;
1369                         ce++;
1370                 }
1371         } else if (pl->use_cone_patterns && orig_ret == NOT_MATCHED) {
1372                 rc = cache_end - cache;
1373         } else {
1374                 rc = clear_ce_flags_1(istate, cache, cache_end - cache,
1375                                       prefix,
1376                                       select_mask, clear_mask,
1377                                       pl, ret,
1378                                       progress_nr);
1379         }
1380
1381         strbuf_setlen(prefix, prefix->len - 1);
1382         return rc;
1383 }
1384
1385 /*
1386  * Traverse the index, find every entry that matches according to
1387  * o->pl. Do "ce_flags &= ~clear_mask" on those entries. Return the
1388  * number of traversed entries.
1389  *
1390  * If select_mask is non-zero, only entries whose ce_flags has on of
1391  * those bits enabled are traversed.
1392  *
1393  * cache        : pointer to an index entry
1394  * prefix_len   : an offset to its path
1395  *
1396  * The current path ("prefix") including the trailing '/' is
1397  *   cache[0]->name[0..(prefix_len-1)]
1398  * Top level path has prefix_len zero.
1399  */
1400 static int clear_ce_flags_1(struct index_state *istate,
1401                             struct cache_entry **cache, int nr,
1402                             struct strbuf *prefix,
1403                             int select_mask, int clear_mask,
1404                             struct pattern_list *pl,
1405                             enum pattern_match_result default_match,
1406                             int progress_nr)
1407 {
1408         struct cache_entry **cache_end = nr ? cache + nr : cache;
1409
1410         /*
1411          * Process all entries that have the given prefix and meet
1412          * select_mask condition
1413          */
1414         while(cache != cache_end) {
1415                 struct cache_entry *ce = *cache;
1416                 const char *name, *slash;
1417                 int len, dtype;
1418                 enum pattern_match_result ret;
1419
1420                 display_progress(istate->progress, progress_nr);
1421
1422                 if (select_mask && !(ce->ce_flags & select_mask)) {
1423                         cache++;
1424                         progress_nr++;
1425                         continue;
1426                 }
1427
1428                 if (prefix->len && strncmp(ce->name, prefix->buf, prefix->len))
1429                         break;
1430
1431                 name = ce->name + prefix->len;
1432                 slash = strchr(name, '/');
1433
1434                 /* If it's a directory, try whole directory match first */
1435                 if (slash) {
1436                         int processed;
1437
1438                         len = slash - name;
1439                         strbuf_add(prefix, name, len);
1440
1441                         processed = clear_ce_flags_dir(istate, cache, cache_end - cache,
1442                                                        prefix,
1443                                                        prefix->buf + prefix->len - len,
1444                                                        select_mask, clear_mask,
1445                                                        pl, default_match,
1446                                                        progress_nr);
1447
1448                         /* clear_c_f_dir eats a whole dir already? */
1449                         if (processed) {
1450                                 cache += processed;
1451                                 progress_nr += processed;
1452                                 strbuf_setlen(prefix, prefix->len - len);
1453                                 continue;
1454                         }
1455
1456                         strbuf_addch(prefix, '/');
1457                         processed = clear_ce_flags_1(istate, cache, cache_end - cache,
1458                                                      prefix,
1459                                                      select_mask, clear_mask, pl,
1460                                                      default_match, progress_nr);
1461
1462                         cache += processed;
1463                         progress_nr += processed;
1464
1465                         strbuf_setlen(prefix, prefix->len - len - 1);
1466                         continue;
1467                 }
1468
1469                 /* Non-directory */
1470                 dtype = ce_to_dtype(ce);
1471                 ret = path_matches_pattern_list(ce->name,
1472                                                 ce_namelen(ce),
1473                                                 name, &dtype, pl, istate);
1474                 if (ret == UNDECIDED)
1475                         ret = default_match;
1476                 if (ret == MATCHED || ret == MATCHED_RECURSIVE)
1477                         ce->ce_flags &= ~clear_mask;
1478                 cache++;
1479                 progress_nr++;
1480         }
1481
1482         display_progress(istate->progress, progress_nr);
1483         return nr - (cache_end - cache);
1484 }
1485
1486 static int clear_ce_flags(struct index_state *istate,
1487                           int select_mask, int clear_mask,
1488                           struct pattern_list *pl,
1489                           int show_progress)
1490 {
1491         static struct strbuf prefix = STRBUF_INIT;
1492         char label[100];
1493         int rval;
1494
1495         strbuf_reset(&prefix);
1496         if (show_progress)
1497                 istate->progress = start_delayed_progress(
1498                                         _("Updating index flags"),
1499                                         istate->cache_nr);
1500
1501         xsnprintf(label, sizeof(label), "clear_ce_flags(0x%08lx,0x%08lx)",
1502                   (unsigned long)select_mask, (unsigned long)clear_mask);
1503         trace2_region_enter("unpack_trees", label, the_repository);
1504         rval = clear_ce_flags_1(istate,
1505                                 istate->cache,
1506                                 istate->cache_nr,
1507                                 &prefix,
1508                                 select_mask, clear_mask,
1509                                 pl, 0, 0);
1510         trace2_region_leave("unpack_trees", label, the_repository);
1511
1512         stop_progress(&istate->progress);
1513         return rval;
1514 }
1515
1516 /*
1517  * Set/Clear CE_NEW_SKIP_WORKTREE according to $GIT_DIR/info/sparse-checkout
1518  */
1519 static void mark_new_skip_worktree(struct pattern_list *pl,
1520                                    struct index_state *istate,
1521                                    int select_flag, int skip_wt_flag,
1522                                    int show_progress)
1523 {
1524         int i;
1525
1526         /*
1527          * 1. Pretend the narrowest worktree: only unmerged entries
1528          * are checked out
1529          */
1530         for (i = 0; i < istate->cache_nr; i++) {
1531                 struct cache_entry *ce = istate->cache[i];
1532
1533                 if (select_flag && !(ce->ce_flags & select_flag))
1534                         continue;
1535
1536                 if (!ce_stage(ce) && !(ce->ce_flags & CE_CONFLICTED))
1537                         ce->ce_flags |= skip_wt_flag;
1538                 else
1539                         ce->ce_flags &= ~skip_wt_flag;
1540         }
1541
1542         /*
1543          * 2. Widen worktree according to sparse-checkout file.
1544          * Matched entries will have skip_wt_flag cleared (i.e. "in")
1545          */
1546         clear_ce_flags(istate, select_flag, skip_wt_flag, pl, show_progress);
1547 }
1548
1549 static void populate_from_existing_patterns(struct unpack_trees_options *o,
1550                                             struct pattern_list *pl)
1551 {
1552         char *sparse = git_pathdup("info/sparse-checkout");
1553
1554         pl->use_cone_patterns = core_sparse_checkout_cone;
1555         if (add_patterns_from_file_to_list(sparse, "", 0, pl, NULL) < 0)
1556                 o->skip_sparse_checkout = 1;
1557         else
1558                 o->pl = pl;
1559         free(sparse);
1560 }
1561
1562
1563 static int verify_absent(const struct cache_entry *,
1564                          enum unpack_trees_error_types,
1565                          struct unpack_trees_options *);
1566 /*
1567  * N-way merge "len" trees.  Returns 0 on success, -1 on failure to manipulate the
1568  * resulting index, -2 on failure to reflect the changes to the work tree.
1569  *
1570  * CE_ADDED, CE_UNPACKED and CE_NEW_SKIP_WORKTREE are used internally
1571  */
1572 int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
1573 {
1574         int i, ret;
1575         static struct cache_entry *dfc;
1576         struct pattern_list pl;
1577         int free_pattern_list = 0;
1578
1579         if (len > MAX_UNPACK_TREES)
1580                 die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES);
1581
1582         trace_performance_enter();
1583         trace2_region_enter("unpack_trees", "unpack_trees", the_repository);
1584
1585         if (!core_apply_sparse_checkout || !o->update)
1586                 o->skip_sparse_checkout = 1;
1587         if (!o->skip_sparse_checkout && !o->pl) {
1588                 memset(&pl, 0, sizeof(pl));
1589                 free_pattern_list = 1;
1590                 populate_from_existing_patterns(o, &pl);
1591         }
1592
1593         memset(&o->result, 0, sizeof(o->result));
1594         o->result.initialized = 1;
1595         o->result.timestamp.sec = o->src_index->timestamp.sec;
1596         o->result.timestamp.nsec = o->src_index->timestamp.nsec;
1597         o->result.version = o->src_index->version;
1598         if (!o->src_index->split_index) {
1599                 o->result.split_index = NULL;
1600         } else if (o->src_index == o->dst_index) {
1601                 /*
1602                  * o->dst_index (and thus o->src_index) will be discarded
1603                  * and overwritten with o->result at the end of this function,
1604                  * so just use src_index's split_index to avoid having to
1605                  * create a new one.
1606                  */
1607                 o->result.split_index = o->src_index->split_index;
1608                 o->result.split_index->refcount++;
1609         } else {
1610                 o->result.split_index = init_split_index(&o->result);
1611         }
1612         oidcpy(&o->result.oid, &o->src_index->oid);
1613         o->merge_size = len;
1614         mark_all_ce_unused(o->src_index);
1615
1616         if (o->src_index->fsmonitor_last_update)
1617                 o->result.fsmonitor_last_update = o->src_index->fsmonitor_last_update;
1618
1619         /*
1620          * Sparse checkout loop #1: set NEW_SKIP_WORKTREE on existing entries
1621          */
1622         if (!o->skip_sparse_checkout)
1623                 mark_new_skip_worktree(o->pl, o->src_index, 0,
1624                                        CE_NEW_SKIP_WORKTREE, o->verbose_update);
1625
1626         if (!dfc)
1627                 dfc = xcalloc(1, cache_entry_size(0));
1628         o->df_conflict_entry = dfc;
1629
1630         if (len) {
1631                 const char *prefix = o->prefix ? o->prefix : "";
1632                 struct traverse_info info;
1633
1634                 setup_traverse_info(&info, prefix);
1635                 info.fn = unpack_callback;
1636                 info.data = o;
1637                 info.show_all_errors = o->show_all_errors;
1638                 info.pathspec = o->pathspec;
1639
1640                 if (o->prefix) {
1641                         /*
1642                          * Unpack existing index entries that sort before the
1643                          * prefix the tree is spliced into.  Note that o->merge
1644                          * is always true in this case.
1645                          */
1646                         while (1) {
1647                                 struct cache_entry *ce = next_cache_entry(o);
1648                                 if (!ce)
1649                                         break;
1650                                 if (ce_in_traverse_path(ce, &info))
1651                                         break;
1652                                 if (unpack_index_entry(ce, o) < 0)
1653                                         goto return_failed;
1654                         }
1655                 }
1656
1657                 trace_performance_enter();
1658                 trace2_region_enter("unpack_trees", "traverse_trees", the_repository);
1659                 ret = traverse_trees(o->src_index, len, t, &info);
1660                 trace2_region_leave("unpack_trees", "traverse_trees", the_repository);
1661                 trace_performance_leave("traverse_trees");
1662                 if (ret < 0)
1663                         goto return_failed;
1664         }
1665
1666         /* Any left-over entries in the index? */
1667         if (o->merge) {
1668                 while (1) {
1669                         struct cache_entry *ce = next_cache_entry(o);
1670                         if (!ce)
1671                                 break;
1672                         if (unpack_index_entry(ce, o) < 0)
1673                                 goto return_failed;
1674                 }
1675         }
1676         mark_all_ce_unused(o->src_index);
1677
1678         if (o->trivial_merges_only && o->nontrivial_merge) {
1679                 ret = unpack_failed(o, "Merge requires file-level merging");
1680                 goto done;
1681         }
1682
1683         if (!o->skip_sparse_checkout) {
1684                 /*
1685                  * Sparse checkout loop #2: set NEW_SKIP_WORKTREE on entries not in loop #1
1686                  * If they will have NEW_SKIP_WORKTREE, also set CE_SKIP_WORKTREE
1687                  * so apply_sparse_checkout() won't attempt to remove it from worktree
1688                  */
1689                 mark_new_skip_worktree(o->pl, &o->result,
1690                                        CE_ADDED, CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE,
1691                                        o->verbose_update);
1692
1693                 ret = 0;
1694                 for (i = 0; i < o->result.cache_nr; i++) {
1695                         struct cache_entry *ce = o->result.cache[i];
1696
1697                         /*
1698                          * Entries marked with CE_ADDED in merged_entry() do not have
1699                          * verify_absent() check (the check is effectively disabled
1700                          * because CE_NEW_SKIP_WORKTREE is set unconditionally).
1701                          *
1702                          * Do the real check now because we have had
1703                          * correct CE_NEW_SKIP_WORKTREE
1704                          */
1705                         if (ce->ce_flags & CE_ADDED &&
1706                             verify_absent(ce, WARNING_SPARSE_ORPHANED_NOT_OVERWRITTEN, o))
1707                                 ret = 1;
1708
1709                         if (apply_sparse_checkout(&o->result, ce, o))
1710                                 ret = 1;
1711                 }
1712                 if (ret == 1) {
1713                         /*
1714                          * Inability to sparsify or de-sparsify individual
1715                          * paths is not an error, but just a warning.
1716                          */
1717                         if (o->show_all_errors)
1718                                 display_warning_msgs(o);
1719                         ret = 0;
1720                 }
1721         }
1722
1723         ret = check_updates(o, &o->result) ? (-2) : 0;
1724         if (o->dst_index) {
1725                 move_index_extensions(&o->result, o->src_index);
1726                 if (!ret) {
1727                         if (git_env_bool("GIT_TEST_CHECK_CACHE_TREE", 0))
1728                                 cache_tree_verify(the_repository, &o->result);
1729                         if (!o->result.cache_tree)
1730                                 o->result.cache_tree = cache_tree();
1731                         if (!cache_tree_fully_valid(o->result.cache_tree))
1732                                 cache_tree_update(&o->result,
1733                                                   WRITE_TREE_SILENT |
1734                                                   WRITE_TREE_REPAIR);
1735                 }
1736
1737                 o->result.updated_workdir = 1;
1738                 discard_index(o->dst_index);
1739                 *o->dst_index = o->result;
1740         } else {
1741                 discard_index(&o->result);
1742         }
1743         o->src_index = NULL;
1744
1745 done:
1746         if (free_pattern_list)
1747                 clear_pattern_list(&pl);
1748         trace2_region_leave("unpack_trees", "unpack_trees", the_repository);
1749         trace_performance_leave("unpack_trees");
1750         return ret;
1751
1752 return_failed:
1753         if (o->show_all_errors)
1754                 display_error_msgs(o);
1755         mark_all_ce_unused(o->src_index);
1756         ret = unpack_failed(o, NULL);
1757         if (o->exiting_early)
1758                 ret = 0;
1759         goto done;
1760 }
1761
1762 /*
1763  * Update SKIP_WORKTREE bits according to sparsity patterns, and update
1764  * working directory to match.
1765  *
1766  * CE_NEW_SKIP_WORKTREE is used internally.
1767  */
1768 enum update_sparsity_result update_sparsity(struct unpack_trees_options *o)
1769 {
1770         enum update_sparsity_result ret = UPDATE_SPARSITY_SUCCESS;
1771         struct pattern_list pl;
1772         int i;
1773         unsigned old_show_all_errors;
1774         int free_pattern_list = 0;
1775
1776         old_show_all_errors = o->show_all_errors;
1777         o->show_all_errors = 1;
1778
1779         /* Sanity checks */
1780         if (!o->update || o->index_only || o->skip_sparse_checkout)
1781                 BUG("update_sparsity() is for reflecting sparsity patterns in working directory");
1782         if (o->src_index != o->dst_index || o->fn)
1783                 BUG("update_sparsity() called wrong");
1784
1785         trace_performance_enter();
1786
1787         /* If we weren't given patterns, use the recorded ones */
1788         if (!o->pl) {
1789                 memset(&pl, 0, sizeof(pl));
1790                 free_pattern_list = 1;
1791                 populate_from_existing_patterns(o, &pl);
1792                 if (o->skip_sparse_checkout)
1793                         goto skip_sparse_checkout;
1794         }
1795
1796         /* Set NEW_SKIP_WORKTREE on existing entries. */
1797         mark_all_ce_unused(o->src_index);
1798         mark_new_skip_worktree(o->pl, o->src_index, 0,
1799                                CE_NEW_SKIP_WORKTREE, o->verbose_update);
1800
1801         /* Then loop over entries and update/remove as needed */
1802         ret = UPDATE_SPARSITY_SUCCESS;
1803         for (i = 0; i < o->src_index->cache_nr; i++) {
1804                 struct cache_entry *ce = o->src_index->cache[i];
1805
1806
1807                 if (ce_stage(ce)) {
1808                         /* -1 because for loop will increment by 1 */
1809                         i += warn_conflicted_path(o->src_index, i, o) - 1;
1810                         ret = UPDATE_SPARSITY_WARNINGS;
1811                         continue;
1812                 }
1813
1814                 if (apply_sparse_checkout(o->src_index, ce, o))
1815                         ret = UPDATE_SPARSITY_WARNINGS;
1816         }
1817
1818 skip_sparse_checkout:
1819         if (check_updates(o, o->src_index))
1820                 ret = UPDATE_SPARSITY_WORKTREE_UPDATE_FAILURES;
1821
1822         display_warning_msgs(o);
1823         o->show_all_errors = old_show_all_errors;
1824         if (free_pattern_list)
1825                 clear_pattern_list(&pl);
1826         trace_performance_leave("update_sparsity");
1827         return ret;
1828 }
1829
1830 /* Here come the merge functions */
1831
1832 static int reject_merge(const struct cache_entry *ce,
1833                         struct unpack_trees_options *o)
1834 {
1835         return add_rejected_path(o, ERROR_WOULD_OVERWRITE, ce->name);
1836 }
1837
1838 static int same(const struct cache_entry *a, const struct cache_entry *b)
1839 {
1840         if (!!a != !!b)
1841                 return 0;
1842         if (!a && !b)
1843                 return 1;
1844         if ((a->ce_flags | b->ce_flags) & CE_CONFLICTED)
1845                 return 0;
1846         return a->ce_mode == b->ce_mode &&
1847                oideq(&a->oid, &b->oid);
1848 }
1849
1850
1851 /*
1852  * When a CE gets turned into an unmerged entry, we
1853  * want it to be up-to-date
1854  */
1855 static int verify_uptodate_1(const struct cache_entry *ce,
1856                              struct unpack_trees_options *o,
1857                              enum unpack_trees_error_types error_type)
1858 {
1859         struct stat st;
1860
1861         if (o->index_only)
1862                 return 0;
1863
1864         /*
1865          * CE_VALID and CE_SKIP_WORKTREE cheat, we better check again
1866          * if this entry is truly up-to-date because this file may be
1867          * overwritten.
1868          */
1869         if ((ce->ce_flags & CE_VALID) || ce_skip_worktree(ce))
1870                 ; /* keep checking */
1871         else if (o->reset || ce_uptodate(ce))
1872                 return 0;
1873
1874         if (!lstat(ce->name, &st)) {
1875                 int flags = CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE;
1876                 unsigned changed = ie_match_stat(o->src_index, ce, &st, flags);
1877
1878                 if (submodule_from_ce(ce)) {
1879                         int r = check_submodule_move_head(ce,
1880                                 "HEAD", oid_to_hex(&ce->oid), o);
1881                         if (r)
1882                                 return add_rejected_path(o, error_type, ce->name);
1883                         return 0;
1884                 }
1885
1886                 if (!changed)
1887                         return 0;
1888                 /*
1889                  * Historic default policy was to allow submodule to be out
1890                  * of sync wrt the superproject index. If the submodule was
1891                  * not considered interesting above, we don't care here.
1892                  */
1893                 if (S_ISGITLINK(ce->ce_mode))
1894                         return 0;
1895
1896                 errno = 0;
1897         }
1898         if (errno == ENOENT)
1899                 return 0;
1900         return add_rejected_path(o, error_type, ce->name);
1901 }
1902
1903 int verify_uptodate(const struct cache_entry *ce,
1904                     struct unpack_trees_options *o)
1905 {
1906         if (!o->skip_sparse_checkout && (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
1907                 return 0;
1908         return verify_uptodate_1(ce, o, ERROR_NOT_UPTODATE_FILE);
1909 }
1910
1911 static int verify_uptodate_sparse(const struct cache_entry *ce,
1912                                   struct unpack_trees_options *o)
1913 {
1914         return verify_uptodate_1(ce, o, WARNING_SPARSE_NOT_UPTODATE_FILE);
1915 }
1916
1917 /*
1918  * TODO: We should actually invalidate o->result, not src_index [1].
1919  * But since cache tree and untracked cache both are not copied to
1920  * o->result until unpacking is complete, we invalidate them on
1921  * src_index instead with the assumption that they will be copied to
1922  * dst_index at the end.
1923  *
1924  * [1] src_index->cache_tree is also used in unpack_callback() so if
1925  * we invalidate o->result, we need to update it to use
1926  * o->result.cache_tree as well.
1927  */
1928 static void invalidate_ce_path(const struct cache_entry *ce,
1929                                struct unpack_trees_options *o)
1930 {
1931         if (!ce)
1932                 return;
1933         cache_tree_invalidate_path(o->src_index, ce->name);
1934         untracked_cache_invalidate_path(o->src_index, ce->name, 1);
1935 }
1936
1937 /*
1938  * Check that checking out ce->sha1 in subdir ce->name is not
1939  * going to overwrite any working files.
1940  */
1941 static int verify_clean_submodule(const char *old_sha1,
1942                                   const struct cache_entry *ce,
1943                                   struct unpack_trees_options *o)
1944 {
1945         if (!submodule_from_ce(ce))
1946                 return 0;
1947
1948         return check_submodule_move_head(ce, old_sha1,
1949                                          oid_to_hex(&ce->oid), o);
1950 }
1951
1952 static int verify_clean_subdirectory(const struct cache_entry *ce,
1953                                      struct unpack_trees_options *o)
1954 {
1955         /*
1956          * we are about to extract "ce->name"; we would not want to lose
1957          * anything in the existing directory there.
1958          */
1959         int namelen;
1960         int i;
1961         struct dir_struct d;
1962         char *pathbuf;
1963         int cnt = 0;
1964
1965         if (S_ISGITLINK(ce->ce_mode)) {
1966                 struct object_id oid;
1967                 int sub_head = resolve_gitlink_ref(ce->name, "HEAD", &oid);
1968                 /*
1969                  * If we are not going to update the submodule, then
1970                  * we don't care.
1971                  */
1972                 if (!sub_head && oideq(&oid, &ce->oid))
1973                         return 0;
1974                 return verify_clean_submodule(sub_head ? NULL : oid_to_hex(&oid),
1975                                               ce, o);
1976         }
1977
1978         /*
1979          * First let's make sure we do not have a local modification
1980          * in that directory.
1981          */
1982         namelen = ce_namelen(ce);
1983         for (i = locate_in_src_index(ce, o);
1984              i < o->src_index->cache_nr;
1985              i++) {
1986                 struct cache_entry *ce2 = o->src_index->cache[i];
1987                 int len = ce_namelen(ce2);
1988                 if (len < namelen ||
1989                     strncmp(ce->name, ce2->name, namelen) ||
1990                     ce2->name[namelen] != '/')
1991                         break;
1992                 /*
1993                  * ce2->name is an entry in the subdirectory to be
1994                  * removed.
1995                  */
1996                 if (!ce_stage(ce2)) {
1997                         if (verify_uptodate(ce2, o))
1998                                 return -1;
1999                         add_entry(o, ce2, CE_REMOVE, 0);
2000                         invalidate_ce_path(ce, o);
2001                         mark_ce_used(ce2, o);
2002                 }
2003                 cnt++;
2004         }
2005
2006         /*
2007          * Then we need to make sure that we do not lose a locally
2008          * present file that is not ignored.
2009          */
2010         pathbuf = xstrfmt("%.*s/", namelen, ce->name);
2011
2012         memset(&d, 0, sizeof(d));
2013         if (o->dir)
2014                 d.exclude_per_dir = o->dir->exclude_per_dir;
2015         i = read_directory(&d, o->src_index, pathbuf, namelen+1, NULL);
2016         if (i)
2017                 return add_rejected_path(o, ERROR_NOT_UPTODATE_DIR, ce->name);
2018         free(pathbuf);
2019         return cnt;
2020 }
2021
2022 /*
2023  * This gets called when there was no index entry for the tree entry 'dst',
2024  * but we found a file in the working tree that 'lstat()' said was fine,
2025  * and we're on a case-insensitive filesystem.
2026  *
2027  * See if we can find a case-insensitive match in the index that also
2028  * matches the stat information, and assume it's that other file!
2029  */
2030 static int icase_exists(struct unpack_trees_options *o, const char *name, int len, struct stat *st)
2031 {
2032         const struct cache_entry *src;
2033
2034         src = index_file_exists(o->src_index, name, len, 1);
2035         return src && !ie_match_stat(o->src_index, src, st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
2036 }
2037
2038 static int check_ok_to_remove(const char *name, int len, int dtype,
2039                               const struct cache_entry *ce, struct stat *st,
2040                               enum unpack_trees_error_types error_type,
2041                               struct unpack_trees_options *o)
2042 {
2043         const struct cache_entry *result;
2044
2045         /*
2046          * It may be that the 'lstat()' succeeded even though
2047          * target 'ce' was absent, because there is an old
2048          * entry that is different only in case..
2049          *
2050          * Ignore that lstat() if it matches.
2051          */
2052         if (ignore_case && icase_exists(o, name, len, st))
2053                 return 0;
2054
2055         if (o->dir &&
2056             is_excluded(o->dir, o->src_index, name, &dtype))
2057                 /*
2058                  * ce->name is explicitly excluded, so it is Ok to
2059                  * overwrite it.
2060                  */
2061                 return 0;
2062         if (S_ISDIR(st->st_mode)) {
2063                 /*
2064                  * We are checking out path "foo" and
2065                  * found "foo/." in the working tree.
2066                  * This is tricky -- if we have modified
2067                  * files that are in "foo/" we would lose
2068                  * them.
2069                  */
2070                 if (verify_clean_subdirectory(ce, o) < 0)
2071                         return -1;
2072                 return 0;
2073         }
2074
2075         /*
2076          * The previous round may already have decided to
2077          * delete this path, which is in a subdirectory that
2078          * is being replaced with a blob.
2079          */
2080         result = index_file_exists(&o->result, name, len, 0);
2081         if (result) {
2082                 if (result->ce_flags & CE_REMOVE)
2083                         return 0;
2084         }
2085
2086         return add_rejected_path(o, error_type, name);
2087 }
2088
2089 /*
2090  * We do not want to remove or overwrite a working tree file that
2091  * is not tracked, unless it is ignored.
2092  */
2093 static int verify_absent_1(const struct cache_entry *ce,
2094                            enum unpack_trees_error_types error_type,
2095                            struct unpack_trees_options *o)
2096 {
2097         int len;
2098         struct stat st;
2099
2100         if (o->index_only || o->reset || !o->update)
2101                 return 0;
2102
2103         len = check_leading_path(ce->name, ce_namelen(ce));
2104         if (!len)
2105                 return 0;
2106         else if (len > 0) {
2107                 char *path;
2108                 int ret;
2109
2110                 path = xmemdupz(ce->name, len);
2111                 if (lstat(path, &st))
2112                         ret = error_errno("cannot stat '%s'", path);
2113                 else {
2114                         if (submodule_from_ce(ce))
2115                                 ret = check_submodule_move_head(ce,
2116                                                                 oid_to_hex(&ce->oid),
2117                                                                 NULL, o);
2118                         else
2119                                 ret = check_ok_to_remove(path, len, DT_UNKNOWN, NULL,
2120                                                          &st, error_type, o);
2121                 }
2122                 free(path);
2123                 return ret;
2124         } else if (lstat(ce->name, &st)) {
2125                 if (errno != ENOENT)
2126                         return error_errno("cannot stat '%s'", ce->name);
2127                 return 0;
2128         } else {
2129                 if (submodule_from_ce(ce))
2130                         return check_submodule_move_head(ce, oid_to_hex(&ce->oid),
2131                                                          NULL, o);
2132
2133                 return check_ok_to_remove(ce->name, ce_namelen(ce),
2134                                           ce_to_dtype(ce), ce, &st,
2135                                           error_type, o);
2136         }
2137 }
2138
2139 static int verify_absent(const struct cache_entry *ce,
2140                          enum unpack_trees_error_types error_type,
2141                          struct unpack_trees_options *o)
2142 {
2143         if (!o->skip_sparse_checkout && (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
2144                 return 0;
2145         return verify_absent_1(ce, error_type, o);
2146 }
2147
2148 static int verify_absent_sparse(const struct cache_entry *ce,
2149                                 enum unpack_trees_error_types error_type,
2150                                 struct unpack_trees_options *o)
2151 {
2152         return verify_absent_1(ce, error_type, o);
2153 }
2154
2155 static int merged_entry(const struct cache_entry *ce,
2156                         const struct cache_entry *old,
2157                         struct unpack_trees_options *o)
2158 {
2159         int update = CE_UPDATE;
2160         struct cache_entry *merge = dup_cache_entry(ce, &o->result);
2161
2162         if (!old) {
2163                 /*
2164                  * New index entries. In sparse checkout, the following
2165                  * verify_absent() will be delayed until after
2166                  * traverse_trees() finishes in unpack_trees(), then:
2167                  *
2168                  *  - CE_NEW_SKIP_WORKTREE will be computed correctly
2169                  *  - verify_absent() be called again, this time with
2170                  *    correct CE_NEW_SKIP_WORKTREE
2171                  *
2172                  * verify_absent() call here does nothing in sparse
2173                  * checkout (i.e. o->skip_sparse_checkout == 0)
2174                  */
2175                 update |= CE_ADDED;
2176                 merge->ce_flags |= CE_NEW_SKIP_WORKTREE;
2177
2178                 if (verify_absent(merge,
2179                                   ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o)) {
2180                         discard_cache_entry(merge);
2181                         return -1;
2182                 }
2183                 invalidate_ce_path(merge, o);
2184
2185                 if (submodule_from_ce(ce) && file_exists(ce->name)) {
2186                         int ret = check_submodule_move_head(ce, NULL,
2187                                                             oid_to_hex(&ce->oid),
2188                                                             o);
2189                         if (ret)
2190                                 return ret;
2191                 }
2192
2193         } else if (!(old->ce_flags & CE_CONFLICTED)) {
2194                 /*
2195                  * See if we can re-use the old CE directly?
2196                  * That way we get the uptodate stat info.
2197                  *
2198                  * This also removes the UPDATE flag on a match; otherwise
2199                  * we will end up overwriting local changes in the work tree.
2200                  */
2201                 if (same(old, merge)) {
2202                         copy_cache_entry(merge, old);
2203                         update = 0;
2204                 } else {
2205                         if (verify_uptodate(old, o)) {
2206                                 discard_cache_entry(merge);
2207                                 return -1;
2208                         }
2209                         /* Migrate old flags over */
2210                         update |= old->ce_flags & (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
2211                         invalidate_ce_path(old, o);
2212                 }
2213
2214                 if (submodule_from_ce(ce) && file_exists(ce->name)) {
2215                         int ret = check_submodule_move_head(ce, oid_to_hex(&old->oid),
2216                                                             oid_to_hex(&ce->oid),
2217                                                             o);
2218                         if (ret)
2219                                 return ret;
2220                 }
2221         } else {
2222                 /*
2223                  * Previously unmerged entry left as an existence
2224                  * marker by read_index_unmerged();
2225                  */
2226                 invalidate_ce_path(old, o);
2227         }
2228
2229         if (do_add_entry(o, merge, update, CE_STAGEMASK) < 0)
2230                 return -1;
2231         return 1;
2232 }
2233
2234 static int deleted_entry(const struct cache_entry *ce,
2235                          const struct cache_entry *old,
2236                          struct unpack_trees_options *o)
2237 {
2238         /* Did it exist in the index? */
2239         if (!old) {
2240                 if (verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_REMOVED, o))
2241                         return -1;
2242                 return 0;
2243         }
2244         if (!(old->ce_flags & CE_CONFLICTED) && verify_uptodate(old, o))
2245                 return -1;
2246         add_entry(o, ce, CE_REMOVE, 0);
2247         invalidate_ce_path(ce, o);
2248         return 1;
2249 }
2250
2251 static int keep_entry(const struct cache_entry *ce,
2252                       struct unpack_trees_options *o)
2253 {
2254         add_entry(o, ce, 0, 0);
2255         if (ce_stage(ce))
2256                 invalidate_ce_path(ce, o);
2257         return 1;
2258 }
2259
2260 #if DBRT_DEBUG
2261 static void show_stage_entry(FILE *o,
2262                              const char *label, const struct cache_entry *ce)
2263 {
2264         if (!ce)
2265                 fprintf(o, "%s (missing)\n", label);
2266         else
2267                 fprintf(o, "%s%06o %s %d\t%s\n",
2268                         label,
2269                         ce->ce_mode,
2270                         oid_to_hex(&ce->oid),
2271                         ce_stage(ce),
2272                         ce->name);
2273 }
2274 #endif
2275
2276 int threeway_merge(const struct cache_entry * const *stages,
2277                    struct unpack_trees_options *o)
2278 {
2279         const struct cache_entry *index;
2280         const struct cache_entry *head;
2281         const struct cache_entry *remote = stages[o->head_idx + 1];
2282         int count;
2283         int head_match = 0;
2284         int remote_match = 0;
2285
2286         int df_conflict_head = 0;
2287         int df_conflict_remote = 0;
2288
2289         int any_anc_missing = 0;
2290         int no_anc_exists = 1;
2291         int i;
2292
2293         for (i = 1; i < o->head_idx; i++) {
2294                 if (!stages[i] || stages[i] == o->df_conflict_entry)
2295                         any_anc_missing = 1;
2296                 else
2297                         no_anc_exists = 0;
2298         }
2299
2300         index = stages[0];
2301         head = stages[o->head_idx];
2302
2303         if (head == o->df_conflict_entry) {
2304                 df_conflict_head = 1;
2305                 head = NULL;
2306         }
2307
2308         if (remote == o->df_conflict_entry) {
2309                 df_conflict_remote = 1;
2310                 remote = NULL;
2311         }
2312
2313         /*
2314          * First, if there's a #16 situation, note that to prevent #13
2315          * and #14.
2316          */
2317         if (!same(remote, head)) {
2318                 for (i = 1; i < o->head_idx; i++) {
2319                         if (same(stages[i], head)) {
2320                                 head_match = i;
2321                         }
2322                         if (same(stages[i], remote)) {
2323                                 remote_match = i;
2324                         }
2325                 }
2326         }
2327
2328         /*
2329          * We start with cases where the index is allowed to match
2330          * something other than the head: #14(ALT) and #2ALT, where it
2331          * is permitted to match the result instead.
2332          */
2333         /* #14, #14ALT, #2ALT */
2334         if (remote && !df_conflict_head && head_match && !remote_match) {
2335                 if (index && !same(index, remote) && !same(index, head))
2336                         return reject_merge(index, o);
2337                 return merged_entry(remote, index, o);
2338         }
2339         /*
2340          * If we have an entry in the index cache, then we want to
2341          * make sure that it matches head.
2342          */
2343         if (index && !same(index, head))
2344                 return reject_merge(index, o);
2345
2346         if (head) {
2347                 /* #5ALT, #15 */
2348                 if (same(head, remote))
2349                         return merged_entry(head, index, o);
2350                 /* #13, #3ALT */
2351                 if (!df_conflict_remote && remote_match && !head_match)
2352                         return merged_entry(head, index, o);
2353         }
2354
2355         /* #1 */
2356         if (!head && !remote && any_anc_missing)
2357                 return 0;
2358
2359         /*
2360          * Under the "aggressive" rule, we resolve mostly trivial
2361          * cases that we historically had git-merge-one-file resolve.
2362          */
2363         if (o->aggressive) {
2364                 int head_deleted = !head;
2365                 int remote_deleted = !remote;
2366                 const struct cache_entry *ce = NULL;
2367
2368                 if (index)
2369                         ce = index;
2370                 else if (head)
2371                         ce = head;
2372                 else if (remote)
2373                         ce = remote;
2374                 else {
2375                         for (i = 1; i < o->head_idx; i++) {
2376                                 if (stages[i] && stages[i] != o->df_conflict_entry) {
2377                                         ce = stages[i];
2378                                         break;
2379                                 }
2380                         }
2381                 }
2382
2383                 /*
2384                  * Deleted in both.
2385                  * Deleted in one and unchanged in the other.
2386                  */
2387                 if ((head_deleted && remote_deleted) ||
2388                     (head_deleted && remote && remote_match) ||
2389                     (remote_deleted && head && head_match)) {
2390                         if (index)
2391                                 return deleted_entry(index, index, o);
2392                         if (ce && !head_deleted) {
2393                                 if (verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_REMOVED, o))
2394                                         return -1;
2395                         }
2396                         return 0;
2397                 }
2398                 /*
2399                  * Added in both, identically.
2400                  */
2401                 if (no_anc_exists && head && remote && same(head, remote))
2402                         return merged_entry(head, index, o);
2403
2404         }
2405
2406         /* Below are "no merge" cases, which require that the index be
2407          * up-to-date to avoid the files getting overwritten with
2408          * conflict resolution files.
2409          */
2410         if (index) {
2411                 if (verify_uptodate(index, o))
2412                         return -1;
2413         }
2414
2415         o->nontrivial_merge = 1;
2416
2417         /* #2, #3, #4, #6, #7, #9, #10, #11. */
2418         count = 0;
2419         if (!head_match || !remote_match) {
2420                 for (i = 1; i < o->head_idx; i++) {
2421                         if (stages[i] && stages[i] != o->df_conflict_entry) {
2422                                 keep_entry(stages[i], o);
2423                                 count++;
2424                                 break;
2425                         }
2426                 }
2427         }
2428 #if DBRT_DEBUG
2429         else {
2430                 fprintf(stderr, "read-tree: warning #16 detected\n");
2431                 show_stage_entry(stderr, "head   ", stages[head_match]);
2432                 show_stage_entry(stderr, "remote ", stages[remote_match]);
2433         }
2434 #endif
2435         if (head) { count += keep_entry(head, o); }
2436         if (remote) { count += keep_entry(remote, o); }
2437         return count;
2438 }
2439
2440 /*
2441  * Two-way merge.
2442  *
2443  * The rule is to "carry forward" what is in the index without losing
2444  * information across a "fast-forward", favoring a successful merge
2445  * over a merge failure when it makes sense.  For details of the
2446  * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
2447  *
2448  */
2449 int twoway_merge(const struct cache_entry * const *src,
2450                  struct unpack_trees_options *o)
2451 {
2452         const struct cache_entry *current = src[0];
2453         const struct cache_entry *oldtree = src[1];
2454         const struct cache_entry *newtree = src[2];
2455
2456         if (o->merge_size != 2)
2457                 return error("Cannot do a twoway merge of %d trees",
2458                              o->merge_size);
2459
2460         if (oldtree == o->df_conflict_entry)
2461                 oldtree = NULL;
2462         if (newtree == o->df_conflict_entry)
2463                 newtree = NULL;
2464
2465         if (current) {
2466                 if (current->ce_flags & CE_CONFLICTED) {
2467                         if (same(oldtree, newtree) || o->reset) {
2468                                 if (!newtree)
2469                                         return deleted_entry(current, current, o);
2470                                 else
2471                                         return merged_entry(newtree, current, o);
2472                         }
2473                         return reject_merge(current, o);
2474                 } else if ((!oldtree && !newtree) || /* 4 and 5 */
2475                          (!oldtree && newtree &&
2476                           same(current, newtree)) || /* 6 and 7 */
2477                          (oldtree && newtree &&
2478                           same(oldtree, newtree)) || /* 14 and 15 */
2479                          (oldtree && newtree &&
2480                           !same(oldtree, newtree) && /* 18 and 19 */
2481                           same(current, newtree))) {
2482                         return keep_entry(current, o);
2483                 } else if (oldtree && !newtree && same(current, oldtree)) {
2484                         /* 10 or 11 */
2485                         return deleted_entry(oldtree, current, o);
2486                 } else if (oldtree && newtree &&
2487                          same(current, oldtree) && !same(current, newtree)) {
2488                         /* 20 or 21 */
2489                         return merged_entry(newtree, current, o);
2490                 } else
2491                         return reject_merge(current, o);
2492         }
2493         else if (newtree) {
2494                 if (oldtree && !o->initial_checkout) {
2495                         /*
2496                          * deletion of the path was staged;
2497                          */
2498                         if (same(oldtree, newtree))
2499                                 return 1;
2500                         return reject_merge(oldtree, o);
2501                 }
2502                 return merged_entry(newtree, current, o);
2503         }
2504         return deleted_entry(oldtree, current, o);
2505 }
2506
2507 /*
2508  * Bind merge.
2509  *
2510  * Keep the index entries at stage0, collapse stage1 but make sure
2511  * stage0 does not have anything there.
2512  */
2513 int bind_merge(const struct cache_entry * const *src,
2514                struct unpack_trees_options *o)
2515 {
2516         const struct cache_entry *old = src[0];
2517         const struct cache_entry *a = src[1];
2518
2519         if (o->merge_size != 1)
2520                 return error("Cannot do a bind merge of %d trees",
2521                              o->merge_size);
2522         if (a && old)
2523                 return o->quiet ? -1 :
2524                         error(ERRORMSG(o, ERROR_BIND_OVERLAP),
2525                               super_prefixed(a->name),
2526                               super_prefixed(old->name));
2527         if (!a)
2528                 return keep_entry(old, o);
2529         else
2530                 return merged_entry(a, NULL, o);
2531 }
2532
2533 /*
2534  * One-way merge.
2535  *
2536  * The rule is:
2537  * - take the stat information from stage0, take the data from stage1
2538  */
2539 int oneway_merge(const struct cache_entry * const *src,
2540                  struct unpack_trees_options *o)
2541 {
2542         const struct cache_entry *old = src[0];
2543         const struct cache_entry *a = src[1];
2544
2545         if (o->merge_size != 1)
2546                 return error("Cannot do a oneway merge of %d trees",
2547                              o->merge_size);
2548
2549         if (!a || a == o->df_conflict_entry)
2550                 return deleted_entry(old, old, o);
2551
2552         if (old && same(old, a)) {
2553                 int update = 0;
2554                 if (o->reset && o->update && !ce_uptodate(old) && !ce_skip_worktree(old) &&
2555                         !(old->ce_flags & CE_FSMONITOR_VALID)) {
2556                         struct stat st;
2557                         if (lstat(old->name, &st) ||
2558                             ie_match_stat(o->src_index, old, &st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE))
2559                                 update |= CE_UPDATE;
2560                 }
2561                 if (o->update && S_ISGITLINK(old->ce_mode) &&
2562                     should_update_submodules() && !verify_uptodate(old, o))
2563                         update |= CE_UPDATE;
2564                 add_entry(o, old, update, CE_STAGEMASK);
2565                 return 0;
2566         }
2567         return merged_entry(a, old, o);
2568 }