Merge branch 'jc/post-simplify' into tr/rev-list-docs
[git] / unpack-trees.c
1 #define NO_THE_INDEX_COMPATIBILITY_MACROS
2 #include "cache.h"
3 #include "dir.h"
4 #include "tree.h"
5 #include "tree-walk.h"
6 #include "cache-tree.h"
7 #include "unpack-trees.h"
8 #include "progress.h"
9 #include "refs.h"
10
11 /*
12  * Error messages expected by scripts out of plumbing commands such as
13  * read-tree.  Non-scripted Porcelain is not required to use these messages
14  * and in fact are encouraged to reword them to better suit their particular
15  * situation better.  See how "git checkout" replaces not_uptodate_file to
16  * explain why it does not allow switching between branches when you have
17  * local changes, for example.
18  */
19 static struct unpack_trees_error_msgs unpack_plumbing_errors = {
20         /* would_overwrite */
21         "Entry '%s' would be overwritten by merge. Cannot merge.",
22
23         /* not_uptodate_file */
24         "Entry '%s' not uptodate. Cannot merge.",
25
26         /* not_uptodate_dir */
27         "Updating '%s' would lose untracked files in it",
28
29         /* would_lose_untracked */
30         "Untracked working tree file '%s' would be %s by merge.",
31
32         /* bind_overlap */
33         "Entry '%s' overlaps with '%s'.  Cannot bind.",
34 };
35
36 #define ERRORMSG(o,fld) \
37         ( ((o) && (o)->msgs.fld) \
38         ? ((o)->msgs.fld) \
39         : (unpack_plumbing_errors.fld) )
40
41 static void add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
42         unsigned int set, unsigned int clear)
43 {
44         unsigned int size = ce_size(ce);
45         struct cache_entry *new = xmalloc(size);
46
47         clear |= CE_HASHED | CE_UNHASHED;
48
49         memcpy(new, ce, size);
50         new->next = NULL;
51         new->ce_flags = (new->ce_flags & ~clear) | set;
52         add_index_entry(&o->result, new, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE|ADD_CACHE_SKIP_DFCHECK);
53 }
54
55 /* Unlink the last component and attempt to remove leading
56  * directories, in case this unlink is the removal of the
57  * last entry in the directory -- empty directories are removed.
58  */
59 static void unlink_entry(struct cache_entry *ce)
60 {
61         char *cp, *prev;
62         char *name = ce->name;
63
64         if (has_symlink_leading_path(ce_namelen(ce), ce->name))
65                 return;
66         if (unlink(name))
67                 return;
68         prev = NULL;
69         while (1) {
70                 int status;
71                 cp = strrchr(name, '/');
72                 if (prev)
73                         *prev = '/';
74                 if (!cp)
75                         break;
76
77                 *cp = 0;
78                 status = rmdir(name);
79                 if (status) {
80                         *cp = '/';
81                         break;
82                 }
83                 prev = cp;
84         }
85 }
86
87 static struct checkout state;
88 static int check_updates(struct unpack_trees_options *o)
89 {
90         unsigned cnt = 0, total = 0;
91         struct progress *progress = NULL;
92         struct index_state *index = &o->result;
93         int i;
94         int errs = 0;
95
96         if (o->update && o->verbose_update) {
97                 for (total = cnt = 0; cnt < index->cache_nr; cnt++) {
98                         struct cache_entry *ce = index->cache[cnt];
99                         if (ce->ce_flags & (CE_UPDATE | CE_REMOVE))
100                                 total++;
101                 }
102
103                 progress = start_progress_delay("Checking out files",
104                                                 total, 50, 1);
105                 cnt = 0;
106         }
107
108         for (i = 0; i < index->cache_nr; i++) {
109                 struct cache_entry *ce = index->cache[i];
110
111                 if (ce->ce_flags & CE_REMOVE) {
112                         display_progress(progress, ++cnt);
113                         if (o->update)
114                                 unlink_entry(ce);
115                         remove_index_entry_at(&o->result, i);
116                         i--;
117                         continue;
118                 }
119         }
120
121         for (i = 0; i < index->cache_nr; i++) {
122                 struct cache_entry *ce = index->cache[i];
123
124                 if (ce->ce_flags & CE_UPDATE) {
125                         display_progress(progress, ++cnt);
126                         ce->ce_flags &= ~CE_UPDATE;
127                         if (o->update) {
128                                 errs |= checkout_entry(ce, &state, NULL);
129                         }
130                 }
131         }
132         stop_progress(&progress);
133         return errs != 0;
134 }
135
136 static inline int call_unpack_fn(struct cache_entry **src, struct unpack_trees_options *o)
137 {
138         int ret = o->fn(src, o);
139         if (ret > 0)
140                 ret = 0;
141         return ret;
142 }
143
144 static int unpack_index_entry(struct cache_entry *ce, struct unpack_trees_options *o)
145 {
146         struct cache_entry *src[5] = { ce, };
147
148         o->pos++;
149         if (ce_stage(ce)) {
150                 if (o->skip_unmerged) {
151                         add_entry(o, ce, 0, 0);
152                         return 0;
153                 }
154         }
155         return call_unpack_fn(src, o);
156 }
157
158 int traverse_trees_recursive(int n, unsigned long dirmask, unsigned long df_conflicts, struct name_entry *names, struct traverse_info *info)
159 {
160         int i;
161         struct tree_desc t[MAX_UNPACK_TREES];
162         struct traverse_info newinfo;
163         struct name_entry *p;
164
165         p = names;
166         while (!p->mode)
167                 p++;
168
169         newinfo = *info;
170         newinfo.prev = info;
171         newinfo.name = *p;
172         newinfo.pathlen += tree_entry_len(p->path, p->sha1) + 1;
173         newinfo.conflicts |= df_conflicts;
174
175         for (i = 0; i < n; i++, dirmask >>= 1) {
176                 const unsigned char *sha1 = NULL;
177                 if (dirmask & 1)
178                         sha1 = names[i].sha1;
179                 fill_tree_descriptor(t+i, sha1);
180         }
181         return traverse_trees(n, t, &newinfo);
182 }
183
184 /*
185  * Compare the traverse-path to the cache entry without actually
186  * having to generate the textual representation of the traverse
187  * path.
188  *
189  * NOTE! This *only* compares up to the size of the traverse path
190  * itself - the caller needs to do the final check for the cache
191  * entry having more data at the end!
192  */
193 static int do_compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
194 {
195         int len, pathlen, ce_len;
196         const char *ce_name;
197
198         if (info->prev) {
199                 int cmp = do_compare_entry(ce, info->prev, &info->name);
200                 if (cmp)
201                         return cmp;
202         }
203         pathlen = info->pathlen;
204         ce_len = ce_namelen(ce);
205
206         /* If ce_len < pathlen then we must have previously hit "name == directory" entry */
207         if (ce_len < pathlen)
208                 return -1;
209
210         ce_len -= pathlen;
211         ce_name = ce->name + pathlen;
212
213         len = tree_entry_len(n->path, n->sha1);
214         return df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
215 }
216
217 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
218 {
219         int cmp = do_compare_entry(ce, info, n);
220         if (cmp)
221                 return cmp;
222
223         /*
224          * Even if the beginning compared identically, the ce should
225          * compare as bigger than a directory leading up to it!
226          */
227         return ce_namelen(ce) > traverse_path_len(info, n);
228 }
229
230 static struct cache_entry *create_ce_entry(const struct traverse_info *info, const struct name_entry *n, int stage)
231 {
232         int len = traverse_path_len(info, n);
233         struct cache_entry *ce = xcalloc(1, cache_entry_size(len));
234
235         ce->ce_mode = create_ce_mode(n->mode);
236         ce->ce_flags = create_ce_flags(len, stage);
237         hashcpy(ce->sha1, n->sha1);
238         make_traverse_path(ce->name, info, n);
239
240         return ce;
241 }
242
243 static int unpack_nondirectories(int n, unsigned long mask, unsigned long dirmask, struct cache_entry *src[5],
244         const struct name_entry *names, const struct traverse_info *info)
245 {
246         int i;
247         struct unpack_trees_options *o = info->data;
248         unsigned long conflicts;
249
250         /* Do we have *only* directories? Nothing to do */
251         if (mask == dirmask && !src[0])
252                 return 0;
253
254         conflicts = info->conflicts;
255         if (o->merge)
256                 conflicts >>= 1;
257         conflicts |= dirmask;
258
259         /*
260          * Ok, we've filled in up to any potential index entry in src[0],
261          * now do the rest.
262          */
263         for (i = 0; i < n; i++) {
264                 int stage;
265                 unsigned int bit = 1ul << i;
266                 if (conflicts & bit) {
267                         src[i + o->merge] = o->df_conflict_entry;
268                         continue;
269                 }
270                 if (!(mask & bit))
271                         continue;
272                 if (!o->merge)
273                         stage = 0;
274                 else if (i + 1 < o->head_idx)
275                         stage = 1;
276                 else if (i + 1 > o->head_idx)
277                         stage = 3;
278                 else
279                         stage = 2;
280                 src[i + o->merge] = create_ce_entry(info, names + i, stage);
281         }
282
283         if (o->merge)
284                 return call_unpack_fn(src, o);
285
286         n += o->merge;
287         for (i = 0; i < n; i++)
288                 add_entry(o, src[i], 0, 0);
289         return 0;
290 }
291
292 static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
293 {
294         struct cache_entry *src[5] = { NULL, };
295         struct unpack_trees_options *o = info->data;
296         const struct name_entry *p = names;
297
298         /* Find first entry with a real name (we could use "mask" too) */
299         while (!p->mode)
300                 p++;
301
302         /* Are we supposed to look at the index too? */
303         if (o->merge) {
304                 while (o->pos < o->src_index->cache_nr) {
305                         struct cache_entry *ce = o->src_index->cache[o->pos];
306                         int cmp = compare_entry(ce, info, p);
307                         if (cmp < 0) {
308                                 if (unpack_index_entry(ce, o) < 0)
309                                         return -1;
310                                 continue;
311                         }
312                         if (!cmp) {
313                                 o->pos++;
314                                 if (ce_stage(ce)) {
315                                         /*
316                                          * If we skip unmerged index entries, we'll skip this
317                                          * entry *and* the tree entries associated with it!
318                                          */
319                                         if (o->skip_unmerged) {
320                                                 add_entry(o, ce, 0, 0);
321                                                 return mask;
322                                         }
323                                 }
324                                 src[0] = ce;
325                         }
326                         break;
327                 }
328         }
329
330         if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
331                 return -1;
332
333         /* Now handle any directories.. */
334         if (dirmask) {
335                 unsigned long conflicts = mask & ~dirmask;
336                 if (o->merge) {
337                         conflicts <<= 1;
338                         if (src[0])
339                                 conflicts |= 1;
340                 }
341                 if (traverse_trees_recursive(n, dirmask, conflicts,
342                                              names, info) < 0)
343                         return -1;
344                 return mask;
345         }
346
347         return mask;
348 }
349
350 static int unpack_failed(struct unpack_trees_options *o, const char *message)
351 {
352         discard_index(&o->result);
353         if (!o->gently) {
354                 if (message)
355                         return error(message);
356                 return -1;
357         }
358         return -1;
359 }
360
361 /*
362  * N-way merge "len" trees.  Returns 0 on success, -1 on failure to manipulate the
363  * resulting index, -2 on failure to reflect the changes to the work tree.
364  */
365 int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
366 {
367         int ret;
368         static struct cache_entry *dfc;
369
370         if (len > MAX_UNPACK_TREES)
371                 die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES);
372         memset(&state, 0, sizeof(state));
373         state.base_dir = "";
374         state.force = 1;
375         state.quiet = 1;
376         state.refresh_cache = 1;
377
378         memset(&o->result, 0, sizeof(o->result));
379         if (o->src_index)
380                 o->result.timestamp = o->src_index->timestamp;
381         o->merge_size = len;
382
383         if (!dfc)
384                 dfc = xcalloc(1, sizeof(struct cache_entry) + 1);
385         o->df_conflict_entry = dfc;
386
387         if (len) {
388                 const char *prefix = o->prefix ? o->prefix : "";
389                 struct traverse_info info;
390
391                 setup_traverse_info(&info, prefix);
392                 info.fn = unpack_callback;
393                 info.data = o;
394
395                 if (traverse_trees(len, t, &info) < 0)
396                         return unpack_failed(o, NULL);
397         }
398
399         /* Any left-over entries in the index? */
400         if (o->merge) {
401                 while (o->pos < o->src_index->cache_nr) {
402                         struct cache_entry *ce = o->src_index->cache[o->pos];
403                         if (unpack_index_entry(ce, o) < 0)
404                                 return unpack_failed(o, NULL);
405                 }
406         }
407
408         if (o->trivial_merges_only && o->nontrivial_merge)
409                 return unpack_failed(o, "Merge requires file-level merging");
410
411         o->src_index = NULL;
412         ret = check_updates(o) ? (-2) : 0;
413         if (o->dst_index)
414                 *o->dst_index = o->result;
415         return ret;
416 }
417
418 /* Here come the merge functions */
419
420 static int reject_merge(struct cache_entry *ce, struct unpack_trees_options *o)
421 {
422         return error(ERRORMSG(o, would_overwrite), ce->name);
423 }
424
425 static int same(struct cache_entry *a, struct cache_entry *b)
426 {
427         if (!!a != !!b)
428                 return 0;
429         if (!a && !b)
430                 return 1;
431         return a->ce_mode == b->ce_mode &&
432                !hashcmp(a->sha1, b->sha1);
433 }
434
435
436 /*
437  * When a CE gets turned into an unmerged entry, we
438  * want it to be up-to-date
439  */
440 static int verify_uptodate(struct cache_entry *ce,
441                 struct unpack_trees_options *o)
442 {
443         struct stat st;
444
445         if (o->index_only || o->reset)
446                 return 0;
447
448         if (!lstat(ce->name, &st)) {
449                 unsigned changed = ie_match_stat(o->src_index, ce, &st, CE_MATCH_IGNORE_VALID);
450                 if (!changed)
451                         return 0;
452                 /*
453                  * NEEDSWORK: the current default policy is to allow
454                  * submodule to be out of sync wrt the supermodule
455                  * index.  This needs to be tightened later for
456                  * submodules that are marked to be automatically
457                  * checked out.
458                  */
459                 if (S_ISGITLINK(ce->ce_mode))
460                         return 0;
461                 errno = 0;
462         }
463         if (errno == ENOENT)
464                 return 0;
465         return o->gently ? -1 :
466                 error(ERRORMSG(o, not_uptodate_file), ce->name);
467 }
468
469 static void invalidate_ce_path(struct cache_entry *ce, struct unpack_trees_options *o)
470 {
471         if (ce)
472                 cache_tree_invalidate_path(o->src_index->cache_tree, ce->name);
473 }
474
475 /*
476  * Check that checking out ce->sha1 in subdir ce->name is not
477  * going to overwrite any working files.
478  *
479  * Currently, git does not checkout subprojects during a superproject
480  * checkout, so it is not going to overwrite anything.
481  */
482 static int verify_clean_submodule(struct cache_entry *ce, const char *action,
483                                       struct unpack_trees_options *o)
484 {
485         return 0;
486 }
487
488 static int verify_clean_subdirectory(struct cache_entry *ce, const char *action,
489                                       struct unpack_trees_options *o)
490 {
491         /*
492          * we are about to extract "ce->name"; we would not want to lose
493          * anything in the existing directory there.
494          */
495         int namelen;
496         int pos, i;
497         struct dir_struct d;
498         char *pathbuf;
499         int cnt = 0;
500         unsigned char sha1[20];
501
502         if (S_ISGITLINK(ce->ce_mode) &&
503             resolve_gitlink_ref(ce->name, "HEAD", sha1) == 0) {
504                 /* If we are not going to update the submodule, then
505                  * we don't care.
506                  */
507                 if (!hashcmp(sha1, ce->sha1))
508                         return 0;
509                 return verify_clean_submodule(ce, action, o);
510         }
511
512         /*
513          * First let's make sure we do not have a local modification
514          * in that directory.
515          */
516         namelen = strlen(ce->name);
517         pos = index_name_pos(o->src_index, ce->name, namelen);
518         if (0 <= pos)
519                 return cnt; /* we have it as nondirectory */
520         pos = -pos - 1;
521         for (i = pos; i < o->src_index->cache_nr; i++) {
522                 struct cache_entry *ce = o->src_index->cache[i];
523                 int len = ce_namelen(ce);
524                 if (len < namelen ||
525                     strncmp(ce->name, ce->name, namelen) ||
526                     ce->name[namelen] != '/')
527                         break;
528                 /*
529                  * ce->name is an entry in the subdirectory.
530                  */
531                 if (!ce_stage(ce)) {
532                         if (verify_uptodate(ce, o))
533                                 return -1;
534                         add_entry(o, ce, CE_REMOVE, 0);
535                 }
536                 cnt++;
537         }
538
539         /*
540          * Then we need to make sure that we do not lose a locally
541          * present file that is not ignored.
542          */
543         pathbuf = xmalloc(namelen + 2);
544         memcpy(pathbuf, ce->name, namelen);
545         strcpy(pathbuf+namelen, "/");
546
547         memset(&d, 0, sizeof(d));
548         if (o->dir)
549                 d.exclude_per_dir = o->dir->exclude_per_dir;
550         i = read_directory(&d, ce->name, pathbuf, namelen+1, NULL);
551         if (i)
552                 return o->gently ? -1 :
553                         error(ERRORMSG(o, not_uptodate_dir), ce->name);
554         free(pathbuf);
555         return cnt;
556 }
557
558 /*
559  * This gets called when there was no index entry for the tree entry 'dst',
560  * but we found a file in the working tree that 'lstat()' said was fine,
561  * and we're on a case-insensitive filesystem.
562  *
563  * See if we can find a case-insensitive match in the index that also
564  * matches the stat information, and assume it's that other file!
565  */
566 static int icase_exists(struct unpack_trees_options *o, struct cache_entry *dst, struct stat *st)
567 {
568         struct cache_entry *src;
569
570         src = index_name_exists(o->src_index, dst->name, ce_namelen(dst), 1);
571         return src && !ie_match_stat(o->src_index, src, st, CE_MATCH_IGNORE_VALID);
572 }
573
574 /*
575  * We do not want to remove or overwrite a working tree file that
576  * is not tracked, unless it is ignored.
577  */
578 static int verify_absent(struct cache_entry *ce, const char *action,
579                          struct unpack_trees_options *o)
580 {
581         struct stat st;
582
583         if (o->index_only || o->reset || !o->update)
584                 return 0;
585
586         if (has_symlink_leading_path(ce_namelen(ce), ce->name))
587                 return 0;
588
589         if (!lstat(ce->name, &st)) {
590                 int cnt;
591                 int dtype = ce_to_dtype(ce);
592                 struct cache_entry *result;
593
594                 /*
595                  * It may be that the 'lstat()' succeeded even though
596                  * target 'ce' was absent, because there is an old
597                  * entry that is different only in case..
598                  *
599                  * Ignore that lstat() if it matches.
600                  */
601                 if (ignore_case && icase_exists(o, ce, &st))
602                         return 0;
603
604                 if (o->dir && excluded(o->dir, ce->name, &dtype))
605                         /*
606                          * ce->name is explicitly excluded, so it is Ok to
607                          * overwrite it.
608                          */
609                         return 0;
610                 if (S_ISDIR(st.st_mode)) {
611                         /*
612                          * We are checking out path "foo" and
613                          * found "foo/." in the working tree.
614                          * This is tricky -- if we have modified
615                          * files that are in "foo/" we would lose
616                          * it.
617                          */
618                         cnt = verify_clean_subdirectory(ce, action, o);
619
620                         /*
621                          * If this removed entries from the index,
622                          * what that means is:
623                          *
624                          * (1) the caller unpack_trees_rec() saw path/foo
625                          * in the index, and it has not removed it because
626                          * it thinks it is handling 'path' as blob with
627                          * D/F conflict;
628                          * (2) we will return "ok, we placed a merged entry
629                          * in the index" which would cause o->pos to be
630                          * incremented by one;
631                          * (3) however, original o->pos now has 'path/foo'
632                          * marked with "to be removed".
633                          *
634                          * We need to increment it by the number of
635                          * deleted entries here.
636                          */
637                         o->pos += cnt;
638                         return 0;
639                 }
640
641                 /*
642                  * The previous round may already have decided to
643                  * delete this path, which is in a subdirectory that
644                  * is being replaced with a blob.
645                  */
646                 result = index_name_exists(&o->result, ce->name, ce_namelen(ce), 0);
647                 if (result) {
648                         if (result->ce_flags & CE_REMOVE)
649                                 return 0;
650                 }
651
652                 return o->gently ? -1 :
653                         error(ERRORMSG(o, would_lose_untracked), ce->name, action);
654         }
655         return 0;
656 }
657
658 static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
659                 struct unpack_trees_options *o)
660 {
661         int update = CE_UPDATE;
662
663         if (old) {
664                 /*
665                  * See if we can re-use the old CE directly?
666                  * That way we get the uptodate stat info.
667                  *
668                  * This also removes the UPDATE flag on a match; otherwise
669                  * we will end up overwriting local changes in the work tree.
670                  */
671                 if (same(old, merge)) {
672                         copy_cache_entry(merge, old);
673                         update = 0;
674                 } else {
675                         if (verify_uptodate(old, o))
676                                 return -1;
677                         invalidate_ce_path(old, o);
678                 }
679         }
680         else {
681                 if (verify_absent(merge, "overwritten", o))
682                         return -1;
683                 invalidate_ce_path(merge, o);
684         }
685
686         add_entry(o, merge, update, CE_STAGEMASK);
687         return 1;
688 }
689
690 static int deleted_entry(struct cache_entry *ce, struct cache_entry *old,
691                 struct unpack_trees_options *o)
692 {
693         /* Did it exist in the index? */
694         if (!old) {
695                 if (verify_absent(ce, "removed", o))
696                         return -1;
697                 return 0;
698         }
699         if (verify_uptodate(old, o))
700                 return -1;
701         add_entry(o, ce, CE_REMOVE, 0);
702         invalidate_ce_path(ce, o);
703         return 1;
704 }
705
706 static int keep_entry(struct cache_entry *ce, struct unpack_trees_options *o)
707 {
708         add_entry(o, ce, 0, 0);
709         return 1;
710 }
711
712 #if DBRT_DEBUG
713 static void show_stage_entry(FILE *o,
714                              const char *label, const struct cache_entry *ce)
715 {
716         if (!ce)
717                 fprintf(o, "%s (missing)\n", label);
718         else
719                 fprintf(o, "%s%06o %s %d\t%s\n",
720                         label,
721                         ce->ce_mode,
722                         sha1_to_hex(ce->sha1),
723                         ce_stage(ce),
724                         ce->name);
725 }
726 #endif
727
728 int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o)
729 {
730         struct cache_entry *index;
731         struct cache_entry *head;
732         struct cache_entry *remote = stages[o->head_idx + 1];
733         int count;
734         int head_match = 0;
735         int remote_match = 0;
736
737         int df_conflict_head = 0;
738         int df_conflict_remote = 0;
739
740         int any_anc_missing = 0;
741         int no_anc_exists = 1;
742         int i;
743
744         for (i = 1; i < o->head_idx; i++) {
745                 if (!stages[i] || stages[i] == o->df_conflict_entry)
746                         any_anc_missing = 1;
747                 else
748                         no_anc_exists = 0;
749         }
750
751         index = stages[0];
752         head = stages[o->head_idx];
753
754         if (head == o->df_conflict_entry) {
755                 df_conflict_head = 1;
756                 head = NULL;
757         }
758
759         if (remote == o->df_conflict_entry) {
760                 df_conflict_remote = 1;
761                 remote = NULL;
762         }
763
764         /* First, if there's a #16 situation, note that to prevent #13
765          * and #14.
766          */
767         if (!same(remote, head)) {
768                 for (i = 1; i < o->head_idx; i++) {
769                         if (same(stages[i], head)) {
770                                 head_match = i;
771                         }
772                         if (same(stages[i], remote)) {
773                                 remote_match = i;
774                         }
775                 }
776         }
777
778         /* We start with cases where the index is allowed to match
779          * something other than the head: #14(ALT) and #2ALT, where it
780          * is permitted to match the result instead.
781          */
782         /* #14, #14ALT, #2ALT */
783         if (remote && !df_conflict_head && head_match && !remote_match) {
784                 if (index && !same(index, remote) && !same(index, head))
785                         return o->gently ? -1 : reject_merge(index, o);
786                 return merged_entry(remote, index, o);
787         }
788         /*
789          * If we have an entry in the index cache, then we want to
790          * make sure that it matches head.
791          */
792         if (index && !same(index, head))
793                 return o->gently ? -1 : reject_merge(index, o);
794
795         if (head) {
796                 /* #5ALT, #15 */
797                 if (same(head, remote))
798                         return merged_entry(head, index, o);
799                 /* #13, #3ALT */
800                 if (!df_conflict_remote && remote_match && !head_match)
801                         return merged_entry(head, index, o);
802         }
803
804         /* #1 */
805         if (!head && !remote && any_anc_missing)
806                 return 0;
807
808         /* Under the new "aggressive" rule, we resolve mostly trivial
809          * cases that we historically had git-merge-one-file resolve.
810          */
811         if (o->aggressive) {
812                 int head_deleted = !head && !df_conflict_head;
813                 int remote_deleted = !remote && !df_conflict_remote;
814                 struct cache_entry *ce = NULL;
815
816                 if (index)
817                         ce = index;
818                 else if (head)
819                         ce = head;
820                 else if (remote)
821                         ce = remote;
822                 else {
823                         for (i = 1; i < o->head_idx; i++) {
824                                 if (stages[i] && stages[i] != o->df_conflict_entry) {
825                                         ce = stages[i];
826                                         break;
827                                 }
828                         }
829                 }
830
831                 /*
832                  * Deleted in both.
833                  * Deleted in one and unchanged in the other.
834                  */
835                 if ((head_deleted && remote_deleted) ||
836                     (head_deleted && remote && remote_match) ||
837                     (remote_deleted && head && head_match)) {
838                         if (index)
839                                 return deleted_entry(index, index, o);
840                         if (ce && !head_deleted) {
841                                 if (verify_absent(ce, "removed", o))
842                                         return -1;
843                         }
844                         return 0;
845                 }
846                 /*
847                  * Added in both, identically.
848                  */
849                 if (no_anc_exists && head && remote && same(head, remote))
850                         return merged_entry(head, index, o);
851
852         }
853
854         /* Below are "no merge" cases, which require that the index be
855          * up-to-date to avoid the files getting overwritten with
856          * conflict resolution files.
857          */
858         if (index) {
859                 if (verify_uptodate(index, o))
860                         return -1;
861         }
862
863         o->nontrivial_merge = 1;
864
865         /* #2, #3, #4, #6, #7, #9, #10, #11. */
866         count = 0;
867         if (!head_match || !remote_match) {
868                 for (i = 1; i < o->head_idx; i++) {
869                         if (stages[i] && stages[i] != o->df_conflict_entry) {
870                                 keep_entry(stages[i], o);
871                                 count++;
872                                 break;
873                         }
874                 }
875         }
876 #if DBRT_DEBUG
877         else {
878                 fprintf(stderr, "read-tree: warning #16 detected\n");
879                 show_stage_entry(stderr, "head   ", stages[head_match]);
880                 show_stage_entry(stderr, "remote ", stages[remote_match]);
881         }
882 #endif
883         if (head) { count += keep_entry(head, o); }
884         if (remote) { count += keep_entry(remote, o); }
885         return count;
886 }
887
888 /*
889  * Two-way merge.
890  *
891  * The rule is to "carry forward" what is in the index without losing
892  * information across a "fast forward", favoring a successful merge
893  * over a merge failure when it makes sense.  For details of the
894  * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
895  *
896  */
897 int twoway_merge(struct cache_entry **src, struct unpack_trees_options *o)
898 {
899         struct cache_entry *current = src[0];
900         struct cache_entry *oldtree = src[1];
901         struct cache_entry *newtree = src[2];
902
903         if (o->merge_size != 2)
904                 return error("Cannot do a twoway merge of %d trees",
905                              o->merge_size);
906
907         if (oldtree == o->df_conflict_entry)
908                 oldtree = NULL;
909         if (newtree == o->df_conflict_entry)
910                 newtree = NULL;
911
912         if (current) {
913                 if ((!oldtree && !newtree) || /* 4 and 5 */
914                     (!oldtree && newtree &&
915                      same(current, newtree)) || /* 6 and 7 */
916                     (oldtree && newtree &&
917                      same(oldtree, newtree)) || /* 14 and 15 */
918                     (oldtree && newtree &&
919                      !same(oldtree, newtree) && /* 18 and 19 */
920                      same(current, newtree))) {
921                         return keep_entry(current, o);
922                 }
923                 else if (oldtree && !newtree && same(current, oldtree)) {
924                         /* 10 or 11 */
925                         return deleted_entry(oldtree, current, o);
926                 }
927                 else if (oldtree && newtree &&
928                          same(current, oldtree) && !same(current, newtree)) {
929                         /* 20 or 21 */
930                         return merged_entry(newtree, current, o);
931                 }
932                 else {
933                         /* all other failures */
934                         if (oldtree)
935                                 return o->gently ? -1 : reject_merge(oldtree, o);
936                         if (current)
937                                 return o->gently ? -1 : reject_merge(current, o);
938                         if (newtree)
939                                 return o->gently ? -1 : reject_merge(newtree, o);
940                         return -1;
941                 }
942         }
943         else if (newtree)
944                 return merged_entry(newtree, current, o);
945         return deleted_entry(oldtree, current, o);
946 }
947
948 /*
949  * Bind merge.
950  *
951  * Keep the index entries at stage0, collapse stage1 but make sure
952  * stage0 does not have anything there.
953  */
954 int bind_merge(struct cache_entry **src,
955                 struct unpack_trees_options *o)
956 {
957         struct cache_entry *old = src[0];
958         struct cache_entry *a = src[1];
959
960         if (o->merge_size != 1)
961                 return error("Cannot do a bind merge of %d trees\n",
962                              o->merge_size);
963         if (a && old)
964                 return o->gently ? -1 :
965                         error(ERRORMSG(o, bind_overlap), a->name, old->name);
966         if (!a)
967                 return keep_entry(old, o);
968         else
969                 return merged_entry(a, NULL, o);
970 }
971
972 /*
973  * One-way merge.
974  *
975  * The rule is:
976  * - take the stat information from stage0, take the data from stage1
977  */
978 int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o)
979 {
980         struct cache_entry *old = src[0];
981         struct cache_entry *a = src[1];
982
983         if (o->merge_size != 1)
984                 return error("Cannot do a oneway merge of %d trees",
985                              o->merge_size);
986
987         if (!a)
988                 return deleted_entry(old, old, o);
989
990         if (old && same(old, a)) {
991                 int update = 0;
992                 if (o->reset) {
993                         struct stat st;
994                         if (lstat(old->name, &st) ||
995                             ie_match_stat(o->src_index, old, &st, CE_MATCH_IGNORE_VALID))
996                                 update |= CE_UPDATE;
997                 }
998                 add_entry(o, old, update, 0);
999                 return 0;
1000         }
1001         return merged_entry(a, old, o);
1002 }