1/*
2 * GIT - The information manager from hell
3 *
4 * Copyright (C) Linus Torvalds, 2005
5 */
6#define DBRT_DEBUG 1
7#include "cache.h"
9#include "object.h"
11#include "tree.h"
12#include "tree-walk.h"
13#include "cache-tree.h"
14#include "unpack-trees.h"
15#include "builtin.h"
16static struct object_list *trees = NULL;
18static void reject_merge(struct cache_entry *ce)
20{
21 die("Entry '%s' would be overwritten by merge. Cannot merge.",
22 ce->name);
23}
24static int list_tree(unsigned char *sha1)
26{
27 struct tree *tree = parse_tree_indirect(sha1);
28 if (!tree)
29 return -1;
30 object_list_append(&tree->object, &trees);
31 return 0;
32}
33static int same(struct cache_entry *a, struct cache_entry *b)
35{
36 if (!!a != !!b)
37 return 0;
38 if (!a && !b)
39 return 1;
40 return a->ce_mode == b->ce_mode &&
41 !memcmp(a->sha1, b->sha1, 20);
42}
43/*
46 * When a CE gets turned into an unmerged entry, we
47 * want it to be up-to-date
48 */
49static void verify_uptodate(struct cache_entry *ce,
50 struct unpack_trees_options *o)
51{
52 struct stat st;
53 if (o->index_only || o->reset)
55 return;
56 if (!lstat(ce->name, &st)) {
58 unsigned changed = ce_match_stat(ce, &st, 1);
59 if (!changed)
60 return;
61 errno = 0;
62 }
63 if (o->reset) {
64 ce->ce_flags |= htons(CE_UPDATE);
65 return;
66 }
67 if (errno == ENOENT)
68 return;
69 die("Entry '%s' not uptodate. Cannot merge.", ce->name);
70}
71static void invalidate_ce_path(struct cache_entry *ce)
73{
74 if (ce)
75 cache_tree_invalidate_path(active_cache_tree, ce->name);
76}
77/*
79 * We do not want to remove or overwrite a working tree file that
80 * is not tracked.
81 */
82static void verify_absent(const char *path, const char *action,
83 struct unpack_trees_options *o)
84{
85 struct stat st;
86 if (o->index_only || o->reset || !o->update)
88 return;
89 if (!lstat(path, &st))
90 die("Untracked working tree file '%s' "
91 "would be %s by merge.", path, action);
92}
93static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
95 struct unpack_trees_options *o)
96{
97 merge->ce_flags |= htons(CE_UPDATE);
98 if (old) {
99 /*
100 * See if we can re-use the old CE directly?
101 * That way we get the uptodate stat info.
102 *
103 * This also removes the UPDATE flag on
104 * a match.
105 */
106 if (same(old, merge)) {
107 *merge = *old;
108 } else {
109 verify_uptodate(old, o);
110 invalidate_ce_path(old);
111 }
112 }
113 else {
114 verify_absent(merge->name, "overwritten", o);
115 invalidate_ce_path(merge);
116 }
117 merge->ce_flags &= ~htons(CE_STAGEMASK);
119 add_cache_entry(merge, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
120 return 1;
121}
122static int deleted_entry(struct cache_entry *ce, struct cache_entry *old,
124 struct unpack_trees_options *o)
125{
126 if (old)
127 verify_uptodate(old, o);
128 else
129 verify_absent(ce->name, "removed", o);
130 ce->ce_mode = 0;
131 add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
132 invalidate_ce_path(ce);
133 return 1;
134}
135static int keep_entry(struct cache_entry *ce)
137{
138 add_cache_entry(ce, ADD_CACHE_OK_TO_ADD);
139 return 1;
140}
141#if DBRT_DEBUG
143static void show_stage_entry(FILE *o,
144 const char *label, const struct cache_entry *ce)
145{
146 if (!ce)
147 fprintf(o, "%s (missing)\n", label);
148 else
149 fprintf(o, "%s%06o %s %d\t%s\n",
150 label,
151 ntohl(ce->ce_mode),
152 sha1_to_hex(ce->sha1),
153 ce_stage(ce),
154 ce->name);
155}
156#endif
157static int threeway_merge(struct cache_entry **stages,
159 struct unpack_trees_options *o)
160{
161 struct cache_entry *index;
162 struct cache_entry *head;
163 struct cache_entry *remote = stages[o->head_idx + 1];
164 int count;
165 int head_match = 0;
166 int remote_match = 0;
167 const char *path = NULL;
168 int df_conflict_head = 0;
170 int df_conflict_remote = 0;
171 int any_anc_missing = 0;
173 int no_anc_exists = 1;
174 int i;
175 for (i = 1; i < o->head_idx; i++) {
177 if (!stages[i])
178 any_anc_missing = 1;
179 else {
180 if (!path)
181 path = stages[i]->name;
182 no_anc_exists = 0;
183 }
184 }
185 index = stages[0];
187 head = stages[o->head_idx];
188 if (head == &o->df_conflict_entry) {
190 df_conflict_head = 1;
191 head = NULL;
192 }
193 if (remote == &o->df_conflict_entry) {
195 df_conflict_remote = 1;
196 remote = NULL;
197 }
198 if (!path && index)
200 path = index->name;
201 if (!path && head)
202 path = head->name;
203 if (!path && remote)
204 path = remote->name;
205 /* First, if there's a #16 situation, note that to prevent #13
207 * and #14.
208 */
209 if (!same(remote, head)) {
210 for (i = 1; i < o->head_idx; i++) {
211 if (same(stages[i], head)) {
212 head_match = i;
213 }
214 if (same(stages[i], remote)) {
215 remote_match = i;
216 }
217 }
218 }
219 /* We start with cases where the index is allowed to match
221 * something other than the head: #14(ALT) and #2ALT, where it
222 * is permitted to match the result instead.
223 */
224 /* #14, #14ALT, #2ALT */
225 if (remote && !df_conflict_head && head_match && !remote_match) {
226 if (index && !same(index, remote) && !same(index, head))
227 reject_merge(index);
228 return merged_entry(remote, index, o);
229 }
230 /*
231 * If we have an entry in the index cache, then we want to
232 * make sure that it matches head.
233 */
234 if (index && !same(index, head)) {
235 reject_merge(index);
236 }
237 if (head) {
239 /* #5ALT, #15 */
240 if (same(head, remote))
241 return merged_entry(head, index, o);
242 /* #13, #3ALT */
243 if (!df_conflict_remote && remote_match && !head_match)
244 return merged_entry(head, index, o);
245 }
246 /* #1 */
248 if (!head && !remote && any_anc_missing)
249 return 0;
250 /* Under the new "aggressive" rule, we resolve mostly trivial
252 * cases that we historically had git-merge-one-file resolve.
253 */
254 if (o->aggressive) {
255 int head_deleted = !head && !df_conflict_head;
256 int remote_deleted = !remote && !df_conflict_remote;
257 /*
258 * Deleted in both.
259 * Deleted in one and unchanged in the other.
260 */
261 if ((head_deleted && remote_deleted) ||
262 (head_deleted && remote && remote_match) ||
263 (remote_deleted && head && head_match)) {
264 if (index)
265 return deleted_entry(index, index, o);
266 else if (path)
267 verify_absent(path, "removed", o);
268 return 0;
269 }
270 /*
271 * Added in both, identically.
272 */
273 if (no_anc_exists && head && remote && same(head, remote))
274 return merged_entry(head, index, o);
275 }
277 /* Below are "no merge" cases, which require that the index be
279 * up-to-date to avoid the files getting overwritten with
280 * conflict resolution files.
281 */
282 if (index) {
283 verify_uptodate(index, o);
284 }
285 else if (path)
286 verify_absent(path, "overwritten", o);
287 o->nontrivial_merge = 1;
289 /* #2, #3, #4, #6, #7, #9, #11. */
291 count = 0;
292 if (!head_match || !remote_match) {
293 for (i = 1; i < o->head_idx; i++) {
294 if (stages[i]) {
295 keep_entry(stages[i]);
296 count++;
297 break;
298 }
299 }
300 }
301#if DBRT_DEBUG
302 else {
303 fprintf(stderr, "read-tree: warning #16 detected\n");
304 show_stage_entry(stderr, "head ", stages[head_match]);
305 show_stage_entry(stderr, "remote ", stages[remote_match]);
306 }
307#endif
308 if (head) { count += keep_entry(head); }
309 if (remote) { count += keep_entry(remote); }
310 return count;
311}
312/*
314 * Two-way merge.
315 *
316 * The rule is to "carry forward" what is in the index without losing
317 * information across a "fast forward", favoring a successful merge
318 * over a merge failure when it makes sense. For details of the
319 * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
320 *
321 */
322static int twoway_merge(struct cache_entry **src,
323 struct unpack_trees_options *o)
324{
325 struct cache_entry *current = src[0];
326 struct cache_entry *oldtree = src[1], *newtree = src[2];
327 if (o->merge_size != 2)
329 return error("Cannot do a twoway merge of %d trees",
330 o->merge_size);
331 if (current) {
333 if ((!oldtree && !newtree) || /* 4 and 5 */
334 (!oldtree && newtree &&
335 same(current, newtree)) || /* 6 and 7 */
336 (oldtree && newtree &&
337 same(oldtree, newtree)) || /* 14 and 15 */
338 (oldtree && newtree &&
339 !same(oldtree, newtree) && /* 18 and 19*/
340 same(current, newtree))) {
341 return keep_entry(current);
342 }
343 else if (oldtree && !newtree && same(current, oldtree)) {
344 /* 10 or 11 */
345 return deleted_entry(oldtree, current, o);
346 }
347 else if (oldtree && newtree &&
348 same(current, oldtree) && !same(current, newtree)) {
349 /* 20 or 21 */
350 return merged_entry(newtree, current, o);
351 }
352 else {
353 /* all other failures */
354 if (oldtree)
355 reject_merge(oldtree);
356 if (current)
357 reject_merge(current);
358 if (newtree)
359 reject_merge(newtree);
360 return -1;
361 }
362 }
363 else if (newtree)
364 return merged_entry(newtree, current, o);
365 else
366 return deleted_entry(oldtree, current, o);
367}
368/*
370 * Bind merge.
371 *
372 * Keep the index entries at stage0, collapse stage1 but make sure
373 * stage0 does not have anything there.
374 */
375static int bind_merge(struct cache_entry **src,
376 struct unpack_trees_options *o)
377{
378 struct cache_entry *old = src[0];
379 struct cache_entry *a = src[1];
380 if (o->merge_size != 1)
382 return error("Cannot do a bind merge of %d trees\n",
383 o->merge_size);
384 if (a && old)
385 die("Entry '%s' overlaps. Cannot bind.", a->name);
386 if (!a)
387 return keep_entry(old);
388 else
389 return merged_entry(a, NULL, o);
390}
391/*
393 * One-way merge.
394 *
395 * The rule is:
396 * - take the stat information from stage0, take the data from stage1
397 */
398static int oneway_merge(struct cache_entry **src,
399 struct unpack_trees_options *o)
400{
401 struct cache_entry *old = src[0];
402 struct cache_entry *a = src[1];
403 if (o->merge_size != 1)
405 return error("Cannot do a oneway merge of %d trees",
406 o->merge_size);
407 if (!a)
409 return deleted_entry(old, old, o);
410 if (old && same(old, a)) {
411 if (o->reset) {
412 struct stat st;
413 if (lstat(old->name, &st) ||
414 ce_match_stat(old, &st, 1))
415 old->ce_flags |= htons(CE_UPDATE);
416 }
417 return keep_entry(old);
418 }
419 return merged_entry(a, old, o);
420}
421static int read_cache_unmerged(void)
423{
424 int i;
425 struct cache_entry **dst;
426 struct cache_entry *last = NULL;
427 read_cache();
429 dst = active_cache;
430 for (i = 0; i < active_nr; i++) {
431 struct cache_entry *ce = active_cache[i];
432 if (ce_stage(ce)) {
433 if (last && !strcmp(ce->name, last->name))
434 continue;
435 invalidate_ce_path(ce);
436 last = ce;
437 ce->ce_mode = 0;
438 ce->ce_flags &= ~htons(CE_STAGEMASK);
439 }
440 *dst++ = ce;
441 }
442 active_nr = dst - active_cache;
443 return !!last;
444}
445static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
447{
448 struct tree_desc desc;
449 struct name_entry entry;
450 int cnt;
451 memcpy(it->sha1, tree->object.sha1, 20);
453 desc.buf = tree->buffer;
454 desc.size = tree->size;
455 cnt = 0;
456 while (tree_entry(&desc, &entry)) {
457 if (!S_ISDIR(entry.mode))
458 cnt++;
459 else {
460 struct cache_tree_sub *sub;
461 struct tree *subtree = lookup_tree(entry.sha1);
462 if (!subtree->object.parsed)
463 parse_tree(subtree);
464 sub = cache_tree_sub(it, entry.path);
465 sub->cache_tree = cache_tree();
466 prime_cache_tree_rec(sub->cache_tree, subtree);
467 cnt += sub->cache_tree->entry_count;
468 }
469 }
470 it->entry_count = cnt;
471}
472static void prime_cache_tree(void)
474{
475 struct tree *tree = (struct tree *)trees->item;
476 if (!tree)
477 return;
478 active_cache_tree = cache_tree();
479 prime_cache_tree_rec(active_cache_tree, tree);
480}
482static const char read_tree_usage[] = "git-read-tree (<sha> | [[-m [--aggressive] | --reset | --prefix=<prefix>] [-u | -i]] <sha1> [<sha2> [<sha3>]])";
484static struct lock_file lock_file;
486int cmd_read_tree(int argc, const char **argv, const char *prefix)
488{
489 int i, newfd, stage = 0;
490 unsigned char sha1[20];
491 struct unpack_trees_options opts;
492 memset(&opts, 0, sizeof(opts));
494 opts.head_idx = -1;
495 setup_git_directory();
497 git_config(git_default_config);
498 newfd = hold_lock_file_for_update(&lock_file, get_index_file());
500 if (newfd < 0)
501 die("unable to create new index file");
502 git_config(git_default_config);
504 for (i = 1; i < argc; i++) {
506 const char *arg = argv[i];
507 /* "-u" means "update", meaning that a merge will update
509 * the working tree.
510 */
511 if (!strcmp(arg, "-u")) {
512 opts.update = 1;
513 continue;
514 }
515 if (!strcmp(arg, "-v")) {
517 opts.verbose_update = 1;
518 continue;
519 }
520 /* "-i" means "index only", meaning that a merge will
522 * not even look at the working tree.
523 */
524 if (!strcmp(arg, "-i")) {
525 opts.index_only = 1;
526 continue;
527 }
528 /* "--prefix=<subdirectory>/" means keep the current index
530 * entries and put the entries from the tree under the
531 * given subdirectory.
532 */
533 if (!strncmp(arg, "--prefix=", 9)) {
534 if (stage || opts.merge || opts.prefix)
535 usage(read_tree_usage);
536 opts.prefix = arg + 9;
537 opts.merge = 1;
538 stage = 1;
539 if (read_cache_unmerged())
540 die("you need to resolve your current index first");
541 continue;
542 }
543 /* This differs from "-m" in that we'll silently ignore
545 * unmerged entries and overwrite working tree files that
546 * correspond to them.
547 */
548 if (!strcmp(arg, "--reset")) {
549 if (stage || opts.merge || opts.prefix)
550 usage(read_tree_usage);
551 opts.reset = 1;
552 opts.merge = 1;
553 stage = 1;
554 read_cache_unmerged();
555 continue;
556 }
557 if (!strcmp(arg, "--trivial")) {
559 opts.trivial_merges_only = 1;
560 continue;
561 }
562 if (!strcmp(arg, "--aggressive")) {
564 opts.aggressive = 1;
565 continue;
566 }
567 /* "-m" stands for "merge", meaning we start in stage 1 */
569 if (!strcmp(arg, "-m")) {
570 if (stage || opts.merge || opts.prefix)
571 usage(read_tree_usage);
572 if (read_cache_unmerged())
573 die("you need to resolve your current index first");
574 stage = 1;
575 opts.merge = 1;
576 continue;
577 }
578 /* using -u and -i at the same time makes no sense */
580 if (1 < opts.index_only + opts.update)
581 usage(read_tree_usage);
582 if (get_sha1(arg, sha1))
584 die("Not a valid object name %s", arg);
585 if (list_tree(sha1) < 0)
586 die("failed to unpack tree object %s", arg);
587 stage++;
588 }
589 if ((opts.update||opts.index_only) && !opts.merge)
590 usage(read_tree_usage);
591 if (opts.prefix) {
593 int pfxlen = strlen(opts.prefix);
594 int pos;
595 if (opts.prefix[pfxlen-1] != '/')
596 die("prefix must end with /");
597 if (stage != 2)
598 die("binding merge takes only one tree");
599 pos = cache_name_pos(opts.prefix, pfxlen);
600 if (0 <= pos)
601 die("corrupt index file");
602 pos = -pos-1;
603 if (pos < active_nr &&
604 !strncmp(active_cache[pos]->name, opts.prefix, pfxlen))
605 die("subdirectory '%s' already exists.", opts.prefix);
606 pos = cache_name_pos(opts.prefix, pfxlen-1);
607 if (0 <= pos)
608 die("file '%.*s' already exists.",
609 pfxlen-1, opts.prefix);
610 }
611 if (opts.merge) {
613 if (stage < 2)
614 die("just how do you expect me to merge %d trees?", stage-1);
615 switch (stage - 1) {
616 case 1:
617 opts.fn = opts.prefix ? bind_merge : oneway_merge;
618 break;
619 case 2:
620 opts.fn = twoway_merge;
621 break;
622 case 3:
623 default:
624 opts.fn = threeway_merge;
625 cache_tree_free(&active_cache_tree);
626 break;
627 }
628 if (stage - 1 >= 3)
630 opts.head_idx = stage - 2;
631 else
632 opts.head_idx = 1;
633 }
634 unpack_trees(trees, &opts);
636 /*
638 * When reading only one tree (either the most basic form,
639 * "-m ent" or "--reset ent" form), we can obtain a fully
640 * valid cache-tree because the index must match exactly
641 * what came from the tree.
642 */
643 if (trees && trees->item && !opts.prefix && (!opts.merge || (stage == 2))) {
644 cache_tree_free(&active_cache_tree);
645 prime_cache_tree();
646 }
647 if (write_cache(newfd, active_cache, active_nr) ||
649 close(newfd) || commit_lock_file(&lock_file))
650 die("unable to write new index file");
651 return 0;
652}