builtin-read-tree.c

   1 /*
   2  * GIT - The information manager from hell
   3  *
   4  * Copyright (C) Linus Torvalds, 2005
   5  */
   6 #define DBRT_DEBUG 1
   7
   8 #include "cache.h"
   9
  10 #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"
  16
  17 static struct object_list *trees = NULL;
  18
  19 static void reject_merge(struct cache_entry *ce)
  20 {
  21         die("Entry '%s' would be overwritten by merge. Cannot merge.",
  22             ce->name);
  23 }
  24
  25 static 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 }
  33
  34 static 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
  44
  45 /*
  46  * When a CE gets turned into an unmerged entry, we
  47  * want it to be up-to-date
  48  */
  49 static void verify_uptodate(struct cache_entry *ce,
  50                 struct unpack_trees_options *o)
  51 {
  52         struct stat st;
  53
  54         if (o->index_only || o->reset)
  55                 return;
  56
  57         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 }
  71
  72 static void invalidate_ce_path(struct cache_entry *ce)
  73 {
  74         if (ce)
  75                 cache_tree_invalidate_path(active_cache_tree, ce->name);
  76 }
  77
  78 /*
  79  * We do not want to remove or overwrite a working tree file that
  80  * is not tracked.
  81  */
  82 static void verify_absent(const char *path, const char *action,
  83                 struct unpack_trees_options *o)
  84 {
  85         struct stat st;
  86
  87         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 }
  93
  94 static 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
 118         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 }
 122
 123 static 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 }
 135
 136 static int keep_entry(struct cache_entry *ce)
 137 {
 138         add_cache_entry(ce, ADD_CACHE_OK_TO_ADD);
 139         return 1;
 140 }
 141
 142 #if DBRT_DEBUG
 143 static 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
 157
 158 static 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
 169         int df_conflict_head = 0;
 170         int df_conflict_remote = 0;
 171
 172         int any_anc_missing = 0;
 173         int no_anc_exists = 1;
 174         int i;
 175
 176         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
 186         index = stages[0];
 187         head = stages[o->head_idx];
 188
 189         if (head == &o->df_conflict_entry) {
 190                 df_conflict_head = 1;
 191                 head = NULL;
 192         }
 193
 194         if (remote == &o->df_conflict_entry) {
 195                 df_conflict_remote = 1;
 196                 remote = NULL;
 197         }
 198
 199         if (!path && index)
 200                 path = index->name;
 201         if (!path && head)
 202                 path = head->name;
 203         if (!path && remote)
 204                 path = remote->name;
 205
 206         /* 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
 220         /* 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
 238         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
 247         /* #1 */
 248         if (!head && !remote && any_anc_missing)
 249                 return 0;
 250
 251         /* 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
 276         }
 277
 278         /* 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
 288         o->nontrivial_merge = 1;
 289
 290         /* #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
 313 /*
 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  */
 322 static 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
 328         if (o->merge_size != 2)
 329                 return error("Cannot do a twoway merge of %d trees",
 330                              o->merge_size);
 331
 332         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
 369 /*
 370  * Bind merge.
 371  *
 372  * Keep the index entries at stage0, collapse stage1 but make sure
 373  * stage0 does not have anything there.
 374  */
 375 static 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
 381         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
 392 /*
 393  * One-way merge.
 394  *
 395  * The rule is:
 396  * - take the stat information from stage0, take the data from stage1
 397  */
 398 static 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
 404         if (o->merge_size != 1)
 405                 return error("Cannot do a oneway merge of %d trees",
 406                              o->merge_size);
 407
 408         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 }
 421
 422 static int read_cache_unmerged(void)
 423 {
 424         int i;
 425         struct cache_entry **dst;
 426         struct cache_entry *last = NULL;
 427
 428         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 }
 445
 446 static 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
 452         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 }
 472
 473 static 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
 481 }
 482
 483 static const char read_tree_usage[] = "git-read-tree (<sha> | [[-m [--aggressive] | --reset | --prefix=<prefix>] [-u | -i]] <sha1> [<sha2> [<sha3>]])";
 484
 485 static struct lock_file lock_file;
 486
 487 int 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
 493         memset(&opts, 0, sizeof(opts));
 494         opts.head_idx = -1;
 495
 496         setup_git_directory();
 497         git_config(git_default_config);
 498
 499         newfd = hold_lock_file_for_update(&lock_file, get_index_file());
 500         if (newfd < 0)
 501                 die("unable to create new index file");
 502
 503         git_config(git_default_config);
 504
 505         for (i = 1; i < argc; i++) {
 506                 const char *arg = argv[i];
 507
 508                 /* "-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
 516                 if (!strcmp(arg, "-v")) {
 517                         opts.verbose_update = 1;
 518                         continue;
 519                 }
 520
 521                 /* "-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
 529                 /* "--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
 544                 /* 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
 558                 if (!strcmp(arg, "--trivial")) {
 559                         opts.trivial_merges_only = 1;
 560                         continue;
 561                 }
 562
 563                 if (!strcmp(arg, "--aggressive")) {
 564                         opts.aggressive = 1;
 565                         continue;
 566                 }
 567
 568                 /* "-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
 579                 /* 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
 583                 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
 592         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
 612         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
 629                 if (stage - 1 >= 3)
 630                         opts.head_idx = stage - 2;
 631                 else
 632                         opts.head_idx = 1;
 633         }
 634
 635         unpack_trees(trees, &opts);
 636
 637         /*
 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
 648         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 }