Merge branch 'fl/cvsserver'
[git] / unpack-trees.c
1 #include "cache.h"
2 #include "dir.h"
3 #include "tree.h"
4 #include "tree-walk.h"
5 #include "cache-tree.h"
6 #include "unpack-trees.h"
7
8 #define DBRT_DEBUG 1
9
10 struct tree_entry_list {
11         struct tree_entry_list *next;
12         unsigned directory : 1;
13         unsigned executable : 1;
14         unsigned symlink : 1;
15         unsigned int mode;
16         const char *name;
17         const unsigned char *sha1;
18 };
19
20 static struct tree_entry_list *create_tree_entry_list(struct tree *tree)
21 {
22         struct tree_desc desc;
23         struct name_entry one;
24         struct tree_entry_list *ret = NULL;
25         struct tree_entry_list **list_p = &ret;
26
27         if (!tree->object.parsed)
28                 parse_tree(tree);
29
30         init_tree_desc(&desc, tree->buffer, tree->size);
31
32         while (tree_entry(&desc, &one)) {
33                 struct tree_entry_list *entry;
34
35                 entry = xmalloc(sizeof(struct tree_entry_list));
36                 entry->name = one.path;
37                 entry->sha1 = one.sha1;
38                 entry->mode = one.mode;
39                 entry->directory = S_ISDIR(one.mode) != 0;
40                 entry->executable = (one.mode & S_IXUSR) != 0;
41                 entry->symlink = S_ISLNK(one.mode) != 0;
42                 entry->next = NULL;
43
44                 *list_p = entry;
45                 list_p = &entry->next;
46         }
47         return ret;
48 }
49
50 static int entcmp(const char *name1, int dir1, const char *name2, int dir2)
51 {
52         int len1 = strlen(name1);
53         int len2 = strlen(name2);
54         int len = len1 < len2 ? len1 : len2;
55         int ret = memcmp(name1, name2, len);
56         unsigned char c1, c2;
57         if (ret)
58                 return ret;
59         c1 = name1[len];
60         c2 = name2[len];
61         if (!c1 && dir1)
62                 c1 = '/';
63         if (!c2 && dir2)
64                 c2 = '/';
65         ret = (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;
66         if (c1 && c2 && !ret)
67                 ret = len1 - len2;
68         return ret;
69 }
70
71 static int unpack_trees_rec(struct tree_entry_list **posns, int len,
72                             const char *base, struct unpack_trees_options *o,
73                             struct tree_entry_list *df_conflict_list)
74 {
75         int baselen = strlen(base);
76         int src_size = len + 1;
77         int i_stk = i_stk;
78         int retval = 0;
79
80         if (o->dir)
81                 i_stk = push_exclude_per_directory(o->dir, base, strlen(base));
82
83         do {
84                 int i;
85                 const char *first;
86                 int firstdir = 0;
87                 int pathlen;
88                 unsigned ce_size;
89                 struct tree_entry_list **subposns;
90                 struct cache_entry **src;
91                 int any_files = 0;
92                 int any_dirs = 0;
93                 char *cache_name;
94                 int ce_stage;
95
96                 /* Find the first name in the input. */
97
98                 first = NULL;
99                 cache_name = NULL;
100
101                 /* Check the cache */
102                 if (o->merge && o->pos < active_nr) {
103                         /* This is a bit tricky: */
104                         /* If the index has a subdirectory (with
105                          * contents) as the first name, it'll get a
106                          * filename like "foo/bar". But that's after
107                          * "foo", so the entry in trees will get
108                          * handled first, at which point we'll go into
109                          * "foo", and deal with "bar" from the index,
110                          * because the base will be "foo/". The only
111                          * way we can actually have "foo/bar" first of
112                          * all the things is if the trees don't
113                          * contain "foo" at all, in which case we'll
114                          * handle "foo/bar" without going into the
115                          * directory, but that's fine (and will return
116                          * an error anyway, with the added unknown
117                          * file case.
118                          */
119
120                         cache_name = active_cache[o->pos]->name;
121                         if (strlen(cache_name) > baselen &&
122                             !memcmp(cache_name, base, baselen)) {
123                                 cache_name += baselen;
124                                 first = cache_name;
125                         } else {
126                                 cache_name = NULL;
127                         }
128                 }
129
130 #if DBRT_DEBUG > 1
131                 if (first)
132                         printf("index %s\n", first);
133 #endif
134                 for (i = 0; i < len; i++) {
135                         if (!posns[i] || posns[i] == df_conflict_list)
136                                 continue;
137 #if DBRT_DEBUG > 1
138                         printf("%d %s\n", i + 1, posns[i]->name);
139 #endif
140                         if (!first || entcmp(first, firstdir,
141                                              posns[i]->name,
142                                              posns[i]->directory) > 0) {
143                                 first = posns[i]->name;
144                                 firstdir = posns[i]->directory;
145                         }
146                 }
147                 /* No name means we're done */
148                 if (!first)
149                         goto leave_directory;
150
151                 pathlen = strlen(first);
152                 ce_size = cache_entry_size(baselen + pathlen);
153
154                 src = xcalloc(src_size, sizeof(struct cache_entry *));
155
156                 subposns = xcalloc(len, sizeof(struct tree_list_entry *));
157
158                 if (cache_name && !strcmp(cache_name, first)) {
159                         any_files = 1;
160                         src[0] = active_cache[o->pos];
161                         remove_cache_entry_at(o->pos);
162                 }
163
164                 for (i = 0; i < len; i++) {
165                         struct cache_entry *ce;
166
167                         if (!posns[i] ||
168                             (posns[i] != df_conflict_list &&
169                              strcmp(first, posns[i]->name))) {
170                                 continue;
171                         }
172
173                         if (posns[i] == df_conflict_list) {
174                                 src[i + o->merge] = o->df_conflict_entry;
175                                 continue;
176                         }
177
178                         if (posns[i]->directory) {
179                                 struct tree *tree = lookup_tree(posns[i]->sha1);
180                                 any_dirs = 1;
181                                 parse_tree(tree);
182                                 subposns[i] = create_tree_entry_list(tree);
183                                 posns[i] = posns[i]->next;
184                                 src[i + o->merge] = o->df_conflict_entry;
185                                 continue;
186                         }
187
188                         if (!o->merge)
189                                 ce_stage = 0;
190                         else if (i + 1 < o->head_idx)
191                                 ce_stage = 1;
192                         else if (i + 1 > o->head_idx)
193                                 ce_stage = 3;
194                         else
195                                 ce_stage = 2;
196
197                         ce = xcalloc(1, ce_size);
198                         ce->ce_mode = create_ce_mode(posns[i]->mode);
199                         ce->ce_flags = create_ce_flags(baselen + pathlen,
200                                                        ce_stage);
201                         memcpy(ce->name, base, baselen);
202                         memcpy(ce->name + baselen, first, pathlen + 1);
203
204                         any_files = 1;
205
206                         hashcpy(ce->sha1, posns[i]->sha1);
207                         src[i + o->merge] = ce;
208                         subposns[i] = df_conflict_list;
209                         posns[i] = posns[i]->next;
210                 }
211                 if (any_files) {
212                         if (o->merge) {
213                                 int ret;
214
215 #if DBRT_DEBUG > 1
216                                 printf("%s:\n", first);
217                                 for (i = 0; i < src_size; i++) {
218                                         printf(" %d ", i);
219                                         if (src[i])
220                                                 printf("%s\n", sha1_to_hex(src[i]->sha1));
221                                         else
222                                                 printf("\n");
223                                 }
224 #endif
225                                 ret = o->fn(src, o);
226
227 #if DBRT_DEBUG > 1
228                                 printf("Added %d entries\n", ret);
229 #endif
230                                 o->pos += ret;
231                         } else {
232                                 for (i = 0; i < src_size; i++) {
233                                         if (src[i]) {
234                                                 add_cache_entry(src[i], ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);
235                                         }
236                                 }
237                         }
238                 }
239                 if (any_dirs) {
240                         char *newbase = xmalloc(baselen + 2 + pathlen);
241                         memcpy(newbase, base, baselen);
242                         memcpy(newbase + baselen, first, pathlen);
243                         newbase[baselen + pathlen] = '/';
244                         newbase[baselen + pathlen + 1] = '\0';
245                         if (unpack_trees_rec(subposns, len, newbase, o,
246                                              df_conflict_list)) {
247                                 retval = -1;
248                                 goto leave_directory;
249                         }
250                         free(newbase);
251                 }
252                 free(subposns);
253                 free(src);
254         } while (1);
255
256  leave_directory:
257         if (o->dir)
258                 pop_exclude_per_directory(o->dir, i_stk);
259         return retval;
260 }
261
262 /* Unlink the last component and attempt to remove leading
263  * directories, in case this unlink is the removal of the
264  * last entry in the directory -- empty directories are removed.
265  */
266 static void unlink_entry(char *name)
267 {
268         char *cp, *prev;
269
270         if (unlink(name))
271                 return;
272         prev = NULL;
273         while (1) {
274                 int status;
275                 cp = strrchr(name, '/');
276                 if (prev)
277                         *prev = '/';
278                 if (!cp)
279                         break;
280
281                 *cp = 0;
282                 status = rmdir(name);
283                 if (status) {
284                         *cp = '/';
285                         break;
286                 }
287                 prev = cp;
288         }
289 }
290
291 static volatile sig_atomic_t progress_update;
292
293 static void progress_interval(int signum)
294 {
295         progress_update = 1;
296 }
297
298 static void setup_progress_signal(void)
299 {
300         struct sigaction sa;
301         struct itimerval v;
302
303         memset(&sa, 0, sizeof(sa));
304         sa.sa_handler = progress_interval;
305         sigemptyset(&sa.sa_mask);
306         sa.sa_flags = SA_RESTART;
307         sigaction(SIGALRM, &sa, NULL);
308
309         v.it_interval.tv_sec = 1;
310         v.it_interval.tv_usec = 0;
311         v.it_value = v.it_interval;
312         setitimer(ITIMER_REAL, &v, NULL);
313 }
314
315 static struct checkout state;
316 static void check_updates(struct cache_entry **src, int nr,
317                 struct unpack_trees_options *o)
318 {
319         unsigned short mask = htons(CE_UPDATE);
320         unsigned last_percent = 200, cnt = 0, total = 0;
321
322         if (o->update && o->verbose_update) {
323                 for (total = cnt = 0; cnt < nr; cnt++) {
324                         struct cache_entry *ce = src[cnt];
325                         if (!ce->ce_mode || ce->ce_flags & mask)
326                                 total++;
327                 }
328
329                 /* Don't bother doing this for very small updates */
330                 if (total < 250)
331                         total = 0;
332
333                 if (total) {
334                         fprintf(stderr, "Checking files out...\n");
335                         setup_progress_signal();
336                         progress_update = 1;
337                 }
338                 cnt = 0;
339         }
340
341         while (nr--) {
342                 struct cache_entry *ce = *src++;
343
344                 if (total) {
345                         if (!ce->ce_mode || ce->ce_flags & mask) {
346                                 unsigned percent;
347                                 cnt++;
348                                 percent = (cnt * 100) / total;
349                                 if (percent != last_percent ||
350                                     progress_update) {
351                                         fprintf(stderr, "%4u%% (%u/%u) done\r",
352                                                 percent, cnt, total);
353                                         last_percent = percent;
354                                         progress_update = 0;
355                                 }
356                         }
357                 }
358                 if (!ce->ce_mode) {
359                         if (o->update)
360                                 unlink_entry(ce->name);
361                         continue;
362                 }
363                 if (ce->ce_flags & mask) {
364                         ce->ce_flags &= ~mask;
365                         if (o->update)
366                                 checkout_entry(ce, &state, NULL);
367                 }
368         }
369         if (total) {
370                 signal(SIGALRM, SIG_IGN);
371                 fputc('\n', stderr);
372         }
373 }
374
375 int unpack_trees(struct object_list *trees, struct unpack_trees_options *o)
376 {
377         unsigned len = object_list_length(trees);
378         struct tree_entry_list **posns;
379         int i;
380         struct object_list *posn = trees;
381         struct tree_entry_list df_conflict_list;
382         static struct cache_entry *dfc;
383
384         memset(&df_conflict_list, 0, sizeof(df_conflict_list));
385         df_conflict_list.next = &df_conflict_list;
386         memset(&state, 0, sizeof(state));
387         state.base_dir = "";
388         state.force = 1;
389         state.quiet = 1;
390         state.refresh_cache = 1;
391
392         o->merge_size = len;
393
394         if (!dfc)
395                 dfc = xcalloc(1, sizeof(struct cache_entry) + 1);
396         o->df_conflict_entry = dfc;
397
398         if (len) {
399                 posns = xmalloc(len * sizeof(struct tree_entry_list *));
400                 for (i = 0; i < len; i++) {
401                         posns[i] = create_tree_entry_list((struct tree *) posn->item);
402                         posn = posn->next;
403                 }
404                 if (unpack_trees_rec(posns, len, o->prefix ? o->prefix : "",
405                                      o, &df_conflict_list))
406                         return -1;
407         }
408
409         if (o->trivial_merges_only && o->nontrivial_merge)
410                 die("Merge requires file-level merging");
411
412         check_updates(active_cache, active_nr, o);
413         return 0;
414 }
415
416 /* Here come the merge functions */
417
418 static void reject_merge(struct cache_entry *ce)
419 {
420         die("Entry '%s' would be overwritten by merge. Cannot merge.",
421             ce->name);
422 }
423
424 static int same(struct cache_entry *a, struct cache_entry *b)
425 {
426         if (!!a != !!b)
427                 return 0;
428         if (!a && !b)
429                 return 1;
430         return a->ce_mode == b->ce_mode &&
431                !hashcmp(a->sha1, b->sha1);
432 }
433
434
435 /*
436  * When a CE gets turned into an unmerged entry, we
437  * want it to be up-to-date
438  */
439 static void verify_uptodate(struct cache_entry *ce,
440                 struct unpack_trees_options *o)
441 {
442         struct stat st;
443
444         if (o->index_only || o->reset)
445                 return;
446
447         if (!lstat(ce->name, &st)) {
448                 unsigned changed = ce_match_stat(ce, &st, 1);
449                 if (!changed)
450                         return;
451                 errno = 0;
452         }
453         if (o->reset) {
454                 ce->ce_flags |= htons(CE_UPDATE);
455                 return;
456         }
457         if (errno == ENOENT)
458                 return;
459         die("Entry '%s' not uptodate. Cannot merge.", ce->name);
460 }
461
462 static void invalidate_ce_path(struct cache_entry *ce)
463 {
464         if (ce)
465                 cache_tree_invalidate_path(active_cache_tree, ce->name);
466 }
467
468 static int verify_clean_subdirectory(const char *path, const char *action,
469                                       struct unpack_trees_options *o)
470 {
471         /*
472          * we are about to extract "path"; we would not want to lose
473          * anything in the existing directory there.
474          */
475         int namelen;
476         int pos, i;
477         struct dir_struct d;
478         char *pathbuf;
479         int cnt = 0;
480
481         /*
482          * First let's make sure we do not have a local modification
483          * in that directory.
484          */
485         namelen = strlen(path);
486         pos = cache_name_pos(path, namelen);
487         if (0 <= pos)
488                 return cnt; /* we have it as nondirectory */
489         pos = -pos - 1;
490         for (i = pos; i < active_nr; i++) {
491                 struct cache_entry *ce = active_cache[i];
492                 int len = ce_namelen(ce);
493                 if (len < namelen ||
494                     strncmp(path, ce->name, namelen) ||
495                     ce->name[namelen] != '/')
496                         break;
497                 /*
498                  * ce->name is an entry in the subdirectory.
499                  */
500                 if (!ce_stage(ce)) {
501                         verify_uptodate(ce, o);
502                         ce->ce_mode = 0;
503                 }
504                 cnt++;
505         }
506
507         /*
508          * Then we need to make sure that we do not lose a locally
509          * present file that is not ignored.
510          */
511         pathbuf = xmalloc(namelen + 2);
512         memcpy(pathbuf, path, namelen);
513         strcpy(pathbuf+namelen, "/");
514
515         memset(&d, 0, sizeof(d));
516         if (o->dir)
517                 d.exclude_per_dir = o->dir->exclude_per_dir;
518         i = read_directory(&d, path, pathbuf, namelen+1, NULL);
519         if (i)
520                 die("Updating '%s' would lose untracked files in it",
521                     path);
522         free(pathbuf);
523         return cnt;
524 }
525
526 /*
527  * We do not want to remove or overwrite a working tree file that
528  * is not tracked, unless it is ignored.
529  */
530 static void verify_absent(const char *path, const char *action,
531                 struct unpack_trees_options *o)
532 {
533         struct stat st;
534
535         if (o->index_only || o->reset || !o->update)
536                 return;
537
538         if (!lstat(path, &st)) {
539                 int cnt;
540
541                 if (o->dir && excluded(o->dir, path))
542                         /*
543                          * path is explicitly excluded, so it is Ok to
544                          * overwrite it.
545                          */
546                         return;
547                 if (S_ISDIR(st.st_mode)) {
548                         /*
549                          * We are checking out path "foo" and
550                          * found "foo/." in the working tree.
551                          * This is tricky -- if we have modified
552                          * files that are in "foo/" we would lose
553                          * it.
554                          */
555                         cnt = verify_clean_subdirectory(path, action, o);
556
557                         /*
558                          * If this removed entries from the index,
559                          * what that means is:
560                          *
561                          * (1) the caller unpack_trees_rec() saw path/foo
562                          * in the index, and it has not removed it because
563                          * it thinks it is handling 'path' as blob with
564                          * D/F conflict;
565                          * (2) we will return "ok, we placed a merged entry
566                          * in the index" which would cause o->pos to be
567                          * incremented by one;
568                          * (3) however, original o->pos now has 'path/foo'
569                          * marked with "to be removed".
570                          *
571                          * We need to increment it by the number of
572                          * deleted entries here.
573                          */
574                         o->pos += cnt;
575                         return;
576                 }
577
578                 /*
579                  * The previous round may already have decided to
580                  * delete this path, which is in a subdirectory that
581                  * is being replaced with a blob.
582                  */
583                 cnt = cache_name_pos(path, strlen(path));
584                 if (0 <= cnt) {
585                         struct cache_entry *ce = active_cache[cnt];
586                         if (!ce_stage(ce) && !ce->ce_mode)
587                                 return;
588                 }
589
590                 die("Untracked working tree file '%s' "
591                     "would be %s by merge.", path, action);
592         }
593 }
594
595 static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
596                 struct unpack_trees_options *o)
597 {
598         merge->ce_flags |= htons(CE_UPDATE);
599         if (old) {
600                 /*
601                  * See if we can re-use the old CE directly?
602                  * That way we get the uptodate stat info.
603                  *
604                  * This also removes the UPDATE flag on
605                  * a match.
606                  */
607                 if (same(old, merge)) {
608                         *merge = *old;
609                 } else {
610                         verify_uptodate(old, o);
611                         invalidate_ce_path(old);
612                 }
613         }
614         else {
615                 verify_absent(merge->name, "overwritten", o);
616                 invalidate_ce_path(merge);
617         }
618
619         merge->ce_flags &= ~htons(CE_STAGEMASK);
620         add_cache_entry(merge, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
621         return 1;
622 }
623
624 static int deleted_entry(struct cache_entry *ce, struct cache_entry *old,
625                 struct unpack_trees_options *o)
626 {
627         if (old)
628                 verify_uptodate(old, o);
629         else
630                 verify_absent(ce->name, "removed", o);
631         ce->ce_mode = 0;
632         add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
633         invalidate_ce_path(ce);
634         return 1;
635 }
636
637 static int keep_entry(struct cache_entry *ce, struct unpack_trees_options *o)
638 {
639         add_cache_entry(ce, ADD_CACHE_OK_TO_ADD);
640         return 1;
641 }
642
643 #if DBRT_DEBUG
644 static void show_stage_entry(FILE *o,
645                              const char *label, const struct cache_entry *ce)
646 {
647         if (!ce)
648                 fprintf(o, "%s (missing)\n", label);
649         else
650                 fprintf(o, "%s%06o %s %d\t%s\n",
651                         label,
652                         ntohl(ce->ce_mode),
653                         sha1_to_hex(ce->sha1),
654                         ce_stage(ce),
655                         ce->name);
656 }
657 #endif
658
659 int threeway_merge(struct cache_entry **stages,
660                 struct unpack_trees_options *o)
661 {
662         struct cache_entry *index;
663         struct cache_entry *head;
664         struct cache_entry *remote = stages[o->head_idx + 1];
665         int count;
666         int head_match = 0;
667         int remote_match = 0;
668
669         int df_conflict_head = 0;
670         int df_conflict_remote = 0;
671
672         int any_anc_missing = 0;
673         int no_anc_exists = 1;
674         int i;
675
676         for (i = 1; i < o->head_idx; i++) {
677                 if (!stages[i] || stages[i] == o->df_conflict_entry)
678                         any_anc_missing = 1;
679                 else
680                         no_anc_exists = 0;
681         }
682
683         index = stages[0];
684         head = stages[o->head_idx];
685
686         if (head == o->df_conflict_entry) {
687                 df_conflict_head = 1;
688                 head = NULL;
689         }
690
691         if (remote == o->df_conflict_entry) {
692                 df_conflict_remote = 1;
693                 remote = NULL;
694         }
695
696         /* First, if there's a #16 situation, note that to prevent #13
697          * and #14.
698          */
699         if (!same(remote, head)) {
700                 for (i = 1; i < o->head_idx; i++) {
701                         if (same(stages[i], head)) {
702                                 head_match = i;
703                         }
704                         if (same(stages[i], remote)) {
705                                 remote_match = i;
706                         }
707                 }
708         }
709
710         /* We start with cases where the index is allowed to match
711          * something other than the head: #14(ALT) and #2ALT, where it
712          * is permitted to match the result instead.
713          */
714         /* #14, #14ALT, #2ALT */
715         if (remote && !df_conflict_head && head_match && !remote_match) {
716                 if (index && !same(index, remote) && !same(index, head))
717                         reject_merge(index);
718                 return merged_entry(remote, index, o);
719         }
720         /*
721          * If we have an entry in the index cache, then we want to
722          * make sure that it matches head.
723          */
724         if (index && !same(index, head)) {
725                 reject_merge(index);
726         }
727
728         if (head) {
729                 /* #5ALT, #15 */
730                 if (same(head, remote))
731                         return merged_entry(head, index, o);
732                 /* #13, #3ALT */
733                 if (!df_conflict_remote && remote_match && !head_match)
734                         return merged_entry(head, index, o);
735         }
736
737         /* #1 */
738         if (!head && !remote && any_anc_missing)
739                 return 0;
740
741         /* Under the new "aggressive" rule, we resolve mostly trivial
742          * cases that we historically had git-merge-one-file resolve.
743          */
744         if (o->aggressive) {
745                 int head_deleted = !head && !df_conflict_head;
746                 int remote_deleted = !remote && !df_conflict_remote;
747                 const char *path = NULL;
748
749                 if (index)
750                         path = index->name;
751                 else if (head)
752                         path = head->name;
753                 else if (remote)
754                         path = remote->name;
755                 else {
756                         for (i = 1; i < o->head_idx; i++) {
757                                 if (stages[i] && stages[i] != o->df_conflict_entry) {
758                                         path = stages[i]->name;
759                                         break;
760                                 }
761                         }
762                 }
763
764                 /*
765                  * Deleted in both.
766                  * Deleted in one and unchanged in the other.
767                  */
768                 if ((head_deleted && remote_deleted) ||
769                     (head_deleted && remote && remote_match) ||
770                     (remote_deleted && head && head_match)) {
771                         if (index)
772                                 return deleted_entry(index, index, o);
773                         else if (path && !head_deleted)
774                                 verify_absent(path, "removed", o);
775                         return 0;
776                 }
777                 /*
778                  * Added in both, identically.
779                  */
780                 if (no_anc_exists && head && remote && same(head, remote))
781                         return merged_entry(head, index, o);
782
783         }
784
785         /* Below are "no merge" cases, which require that the index be
786          * up-to-date to avoid the files getting overwritten with
787          * conflict resolution files.
788          */
789         if (index) {
790                 verify_uptodate(index, o);
791         }
792
793         o->nontrivial_merge = 1;
794
795         /* #2, #3, #4, #6, #7, #9, #10, #11. */
796         count = 0;
797         if (!head_match || !remote_match) {
798                 for (i = 1; i < o->head_idx; i++) {
799                         if (stages[i] && stages[i] != o->df_conflict_entry) {
800                                 keep_entry(stages[i], o);
801                                 count++;
802                                 break;
803                         }
804                 }
805         }
806 #if DBRT_DEBUG
807         else {
808                 fprintf(stderr, "read-tree: warning #16 detected\n");
809                 show_stage_entry(stderr, "head   ", stages[head_match]);
810                 show_stage_entry(stderr, "remote ", stages[remote_match]);
811         }
812 #endif
813         if (head) { count += keep_entry(head, o); }
814         if (remote) { count += keep_entry(remote, o); }
815         return count;
816 }
817
818 /*
819  * Two-way merge.
820  *
821  * The rule is to "carry forward" what is in the index without losing
822  * information across a "fast forward", favoring a successful merge
823  * over a merge failure when it makes sense.  For details of the
824  * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
825  *
826  */
827 int twoway_merge(struct cache_entry **src,
828                 struct unpack_trees_options *o)
829 {
830         struct cache_entry *current = src[0];
831         struct cache_entry *oldtree = src[1];
832         struct cache_entry *newtree = src[2];
833
834         if (o->merge_size != 2)
835                 return error("Cannot do a twoway merge of %d trees",
836                              o->merge_size);
837
838         if (oldtree == o->df_conflict_entry)
839                 oldtree = NULL;
840         if (newtree == o->df_conflict_entry)
841                 newtree = NULL;
842
843         if (current) {
844                 if ((!oldtree && !newtree) || /* 4 and 5 */
845                     (!oldtree && newtree &&
846                      same(current, newtree)) || /* 6 and 7 */
847                     (oldtree && newtree &&
848                      same(oldtree, newtree)) || /* 14 and 15 */
849                     (oldtree && newtree &&
850                      !same(oldtree, newtree) && /* 18 and 19 */
851                      same(current, newtree))) {
852                         return keep_entry(current, o);
853                 }
854                 else if (oldtree && !newtree && same(current, oldtree)) {
855                         /* 10 or 11 */
856                         return deleted_entry(oldtree, current, o);
857                 }
858                 else if (oldtree && newtree &&
859                          same(current, oldtree) && !same(current, newtree)) {
860                         /* 20 or 21 */
861                         return merged_entry(newtree, current, o);
862                 }
863                 else {
864                         /* all other failures */
865                         if (oldtree)
866                                 reject_merge(oldtree);
867                         if (current)
868                                 reject_merge(current);
869                         if (newtree)
870                                 reject_merge(newtree);
871                         return -1;
872                 }
873         }
874         else if (newtree)
875                 return merged_entry(newtree, current, o);
876         else
877                 return deleted_entry(oldtree, current, o);
878 }
879
880 /*
881  * Bind merge.
882  *
883  * Keep the index entries at stage0, collapse stage1 but make sure
884  * stage0 does not have anything there.
885  */
886 int bind_merge(struct cache_entry **src,
887                 struct unpack_trees_options *o)
888 {
889         struct cache_entry *old = src[0];
890         struct cache_entry *a = src[1];
891
892         if (o->merge_size != 1)
893                 return error("Cannot do a bind merge of %d trees\n",
894                              o->merge_size);
895         if (a && old)
896                 die("Entry '%s' overlaps.  Cannot bind.", a->name);
897         if (!a)
898                 return keep_entry(old, o);
899         else
900                 return merged_entry(a, NULL, o);
901 }
902
903 /*
904  * One-way merge.
905  *
906  * The rule is:
907  * - take the stat information from stage0, take the data from stage1
908  */
909 int oneway_merge(struct cache_entry **src,
910                 struct unpack_trees_options *o)
911 {
912         struct cache_entry *old = src[0];
913         struct cache_entry *a = src[1];
914
915         if (o->merge_size != 1)
916                 return error("Cannot do a oneway merge of %d trees",
917                              o->merge_size);
918
919         if (!a)
920                 return deleted_entry(old, old, o);
921         if (old && same(old, a)) {
922                 if (o->reset) {
923                         struct stat st;
924                         if (lstat(old->name, &st) ||
925                             ce_match_stat(old, &st, 1))
926                                 old->ce_flags |= htons(CE_UPDATE);
927                 }
928                 return keep_entry(old, o);
929         }
930         return merged_entry(a, old, o);
931 }