builtin/merge-tree.c

   1 #define USE_THE_INDEX_COMPATIBILITY_MACROS
   2 #include "builtin.h"
   3 #include "tree-walk.h"
   4 #include "xdiff-interface.h"
   5 #include "help.h"
   6 #include "commit-reach.h"
   7 #include "merge-ort.h"
   8 #include "object-store.h"
   9 #include "parse-options.h"
  10 #include "repository.h"
  11 #include "blob.h"
  12 #include "exec-cmd.h"
  13 #include "merge-blobs.h"
  14 #include "quote.h"
  15
  16 static int line_termination = '\n';
  17
  18 struct merge_list {
  19         struct merge_list *next;
  20         struct merge_list *link;        /* other stages for this object */
  21
  22         unsigned int stage : 2;
  23         unsigned int mode;
  24         const char *path;
  25         struct blob *blob;
  26 };
  27
  28 static struct merge_list *merge_result, **merge_result_end = &merge_result;
  29
  30 static void add_merge_entry(struct merge_list *entry)
  31 {
  32         *merge_result_end = entry;
  33         merge_result_end = &entry->next;
  34 }
  35
  36 static void trivial_merge_trees(struct tree_desc t[3], const char *base);
  37
  38 static const char *explanation(struct merge_list *entry)
  39 {
  40         switch (entry->stage) {
  41         case 0:
  42                 return "merged";
  43         case 3:
  44                 return "added in remote";
  45         case 2:
  46                 if (entry->link)
  47                         return "added in both";
  48                 return "added in local";
  49         }
  50
  51         /* Existed in base */
  52         entry = entry->link;
  53         if (!entry)
  54                 return "removed in both";
  55
  56         if (entry->link)
  57                 return "changed in both";
  58
  59         if (entry->stage == 3)
  60                 return "removed in local";
  61         return "removed in remote";
  62 }
  63
  64 static void *result(struct merge_list *entry, unsigned long *size)
  65 {
  66         enum object_type type;
  67         struct blob *base, *our, *their;
  68         const char *path = entry->path;
  69
  70         if (!entry->stage)
  71                 return read_object_file(&entry->blob->object.oid, &type, size);
  72         base = NULL;
  73         if (entry->stage == 1) {
  74                 base = entry->blob;
  75                 entry = entry->link;
  76         }
  77         our = NULL;
  78         if (entry && entry->stage == 2) {
  79                 our = entry->blob;
  80                 entry = entry->link;
  81         }
  82         their = NULL;
  83         if (entry)
  84                 their = entry->blob;
  85         return merge_blobs(the_repository->index, path,
  86                            base, our, their, size);
  87 }
  88
  89 static void *origin(struct merge_list *entry, unsigned long *size)
  90 {
  91         enum object_type type;
  92         while (entry) {
  93                 if (entry->stage == 2)
  94                         return read_object_file(&entry->blob->object.oid,
  95                                                 &type, size);
  96                 entry = entry->link;
  97         }
  98         return NULL;
  99 }
 100
 101 static int show_outf(void *priv_, mmbuffer_t *mb, int nbuf)
 102 {
 103         int i;
 104         for (i = 0; i < nbuf; i++)
 105                 printf("%.*s", (int) mb[i].size, mb[i].ptr);
 106         return 0;
 107 }
 108
 109 static void show_diff(struct merge_list *entry)
 110 {
 111         unsigned long size;
 112         mmfile_t src, dst;
 113         xpparam_t xpp;
 114         xdemitconf_t xecfg;
 115         xdemitcb_t ecb = { .out_line = show_outf };
 116
 117         memset(&xpp, 0, sizeof(xpp));
 118         xpp.flags = 0;
 119         memset(&xecfg, 0, sizeof(xecfg));
 120         xecfg.ctxlen = 3;
 121
 122         src.ptr = origin(entry, &size);
 123         if (!src.ptr)
 124                 size = 0;
 125         src.size = size;
 126         dst.ptr = result(entry, &size);
 127         if (!dst.ptr)
 128                 size = 0;
 129         dst.size = size;
 130         if (xdi_diff(&src, &dst, &xpp, &xecfg, &ecb))
 131                 die("unable to generate diff");
 132         free(src.ptr);
 133         free(dst.ptr);
 134 }
 135
 136 static void show_result_list(struct merge_list *entry)
 137 {
 138         printf("%s\n", explanation(entry));
 139         do {
 140                 struct merge_list *link = entry->link;
 141                 static const char *desc[4] = { "result", "base", "our", "their" };
 142                 printf("  %-6s %o %s %s\n", desc[entry->stage], entry->mode, oid_to_hex(&entry->blob->object.oid), entry->path);
 143                 entry = link;
 144         } while (entry);
 145 }
 146
 147 static void show_result(void)
 148 {
 149         struct merge_list *walk;
 150
 151         walk = merge_result;
 152         while (walk) {
 153                 show_result_list(walk);
 154                 show_diff(walk);
 155                 walk = walk->next;
 156         }
 157 }
 158
 159 /* An empty entry never compares same, not even to another empty entry */
 160 static int same_entry(struct name_entry *a, struct name_entry *b)
 161 {
 162         return  !is_null_oid(&a->oid) &&
 163                 !is_null_oid(&b->oid) &&
 164                 oideq(&a->oid, &b->oid) &&
 165                 a->mode == b->mode;
 166 }
 167
 168 static int both_empty(struct name_entry *a, struct name_entry *b)
 169 {
 170         return is_null_oid(&a->oid) && is_null_oid(&b->oid);
 171 }
 172
 173 static struct merge_list *create_entry(unsigned stage, unsigned mode, const struct object_id *oid, const char *path)
 174 {
 175         struct merge_list *res = xcalloc(1, sizeof(*res));
 176
 177         res->stage = stage;
 178         res->path = path;
 179         res->mode = mode;
 180         res->blob = lookup_blob(the_repository, oid);
 181         return res;
 182 }
 183
 184 static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)
 185 {
 186         struct strbuf buf = STRBUF_INIT;
 187         strbuf_make_traverse_path(&buf, info, n->path, n->pathlen);
 188         return strbuf_detach(&buf, NULL);
 189 }
 190
 191 static void resolve(const struct traverse_info *info, struct name_entry *ours, struct name_entry *result)
 192 {
 193         struct merge_list *orig, *final;
 194         const char *path;
 195
 196         /* If it's already ours, don't bother showing it */
 197         if (!ours)
 198                 return;
 199
 200         path = traverse_path(info, result);
 201         orig = create_entry(2, ours->mode, &ours->oid, path);
 202         final = create_entry(0, result->mode, &result->oid, path);
 203
 204         final->link = orig;
 205
 206         add_merge_entry(final);
 207 }
 208
 209 static void unresolved_directory(const struct traverse_info *info,
 210                                  struct name_entry n[3])
 211 {
 212         struct repository *r = the_repository;
 213         char *newbase;
 214         struct name_entry *p;
 215         struct tree_desc t[3];
 216         void *buf0, *buf1, *buf2;
 217
 218         for (p = n; p < n + 3; p++) {
 219                 if (p->mode && S_ISDIR(p->mode))
 220                         break;
 221         }
 222         if (n + 3 <= p)
 223                 return; /* there is no tree here */
 224
 225         newbase = traverse_path(info, p);
 226
 227 #define ENTRY_OID(e) (((e)->mode && S_ISDIR((e)->mode)) ? &(e)->oid : NULL)
 228         buf0 = fill_tree_descriptor(r, t + 0, ENTRY_OID(n + 0));
 229         buf1 = fill_tree_descriptor(r, t + 1, ENTRY_OID(n + 1));
 230         buf2 = fill_tree_descriptor(r, t + 2, ENTRY_OID(n + 2));
 231 #undef ENTRY_OID
 232
 233         trivial_merge_trees(t, newbase);
 234
 235         free(buf0);
 236         free(buf1);
 237         free(buf2);
 238         free(newbase);
 239 }
 240
 241
 242 static struct merge_list *link_entry(unsigned stage, const struct traverse_info *info, struct name_entry *n, struct merge_list *entry)
 243 {
 244         const char *path;
 245         struct merge_list *link;
 246
 247         if (!n->mode)
 248                 return entry;
 249         if (entry)
 250                 path = entry->path;
 251         else
 252                 path = traverse_path(info, n);
 253         link = create_entry(stage, n->mode, &n->oid, path);
 254         link->link = entry;
 255         return link;
 256 }
 257
 258 static void unresolved(const struct traverse_info *info, struct name_entry n[3])
 259 {
 260         struct merge_list *entry = NULL;
 261         int i;
 262         unsigned dirmask = 0, mask = 0;
 263
 264         for (i = 0; i < 3; i++) {
 265                 mask |= (1 << i);
 266                 /*
 267                  * Treat missing entries as directories so that we return
 268                  * after unresolved_directory has handled this.
 269                  */
 270                 if (!n[i].mode || S_ISDIR(n[i].mode))
 271                         dirmask |= (1 << i);
 272         }
 273
 274         unresolved_directory(info, n);
 275
 276         if (dirmask == mask)
 277                 return;
 278
 279         if (n[2].mode && !S_ISDIR(n[2].mode))
 280                 entry = link_entry(3, info, n + 2, entry);
 281         if (n[1].mode && !S_ISDIR(n[1].mode))
 282                 entry = link_entry(2, info, n + 1, entry);
 283         if (n[0].mode && !S_ISDIR(n[0].mode))
 284                 entry = link_entry(1, info, n + 0, entry);
 285
 286         add_merge_entry(entry);
 287 }
 288
 289 /*
 290  * Merge two trees together (t[1] and t[2]), using a common base (t[0])
 291  * as the origin.
 292  *
 293  * This walks the (sorted) trees in lock-step, checking every possible
 294  * name. Note that directories automatically sort differently from other
 295  * files (see "base_name_compare"), so you'll never see file/directory
 296  * conflicts, because they won't ever compare the same.
 297  *
 298  * IOW, if a directory changes to a filename, it will automatically be
 299  * seen as the directory going away, and the filename being created.
 300  *
 301  * Think of this as a three-way diff.
 302  *
 303  * The output will be either:
 304  *  - successful merge
 305  *       "0 mode sha1 filename"
 306  *    NOTE NOTE NOTE! FIXME! We really really need to walk the index
 307  *    in parallel with this too!
 308  *
 309  *  - conflict:
 310  *      "1 mode sha1 filename"
 311  *      "2 mode sha1 filename"
 312  *      "3 mode sha1 filename"
 313  *    where not all of the 1/2/3 lines may exist, of course.
 314  *
 315  * The successful merge rules are the same as for the three-way merge
 316  * in git-read-tree.
 317  */
 318 static int threeway_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *info)
 319 {
 320         /* Same in both? */
 321         if (same_entry(entry+1, entry+2) || both_empty(entry+1, entry+2)) {
 322                 /* Modified, added or removed identically */
 323                 resolve(info, NULL, entry+1);
 324                 return mask;
 325         }
 326
 327         if (same_entry(entry+0, entry+1)) {
 328                 if (!is_null_oid(&entry[2].oid) && !S_ISDIR(entry[2].mode)) {
 329                         /* We did not touch, they modified -- take theirs */
 330                         resolve(info, entry+1, entry+2);
 331                         return mask;
 332                 }
 333                 /*
 334                  * If we did not touch a directory but they made it
 335                  * into a file, we fall through and unresolved()
 336                  * recurses down.  Likewise for the opposite case.
 337                  */
 338         }
 339
 340         if (same_entry(entry+0, entry+2) || both_empty(entry+0, entry+2)) {
 341                 /* We added, modified or removed, they did not touch -- take ours */
 342                 resolve(info, NULL, entry+1);
 343                 return mask;
 344         }
 345
 346         unresolved(info, entry);
 347         return mask;
 348 }
 349
 350 static void trivial_merge_trees(struct tree_desc t[3], const char *base)
 351 {
 352         struct traverse_info info;
 353
 354         setup_traverse_info(&info, base);
 355         info.fn = threeway_callback;
 356         traverse_trees(&the_index, 3, t, &info);
 357 }
 358
 359 static void *get_tree_descriptor(struct repository *r,
 360                                  struct tree_desc *desc,
 361                                  const char *rev)
 362 {
 363         struct object_id oid;
 364         void *buf;
 365
 366         if (repo_get_oid(r, rev, &oid))
 367                 die("unknown rev %s", rev);
 368         buf = fill_tree_descriptor(r, desc, &oid);
 369         if (!buf)
 370                 die("%s is not a tree", rev);
 371         return buf;
 372 }
 373
 374 static int trivial_merge(const char *base,
 375                          const char *branch1,
 376                          const char *branch2)
 377 {
 378         struct repository *r = the_repository;
 379         struct tree_desc t[3];
 380         void *buf1, *buf2, *buf3;
 381
 382         buf1 = get_tree_descriptor(r, t+0, base);
 383         buf2 = get_tree_descriptor(r, t+1, branch1);
 384         buf3 = get_tree_descriptor(r, t+2, branch2);
 385         trivial_merge_trees(t, "");
 386         free(buf1);
 387         free(buf2);
 388         free(buf3);
 389
 390         show_result();
 391         return 0;
 392 }
 393
 394 enum mode {
 395         MODE_UNKNOWN,
 396         MODE_TRIVIAL,
 397         MODE_REAL,
 398 };
 399
 400 struct merge_tree_options {
 401         int mode;
 402         int allow_unrelated_histories;
 403         int show_messages;
 404         int name_only;
 405 };
 406
 407 static int real_merge(struct merge_tree_options *o,
 408                       const char *branch1, const char *branch2,
 409                       const char *prefix)
 410 {
 411         struct commit *parent1, *parent2;
 412         struct commit_list *merge_bases = NULL;
 413         struct merge_options opt;
 414         struct merge_result result = { 0 };
 415
 416         parent1 = get_merge_parent(branch1);
 417         if (!parent1)
 418                 help_unknown_ref(branch1, "merge-tree",
 419                                  _("not something we can merge"));
 420
 421         parent2 = get_merge_parent(branch2);
 422         if (!parent2)
 423                 help_unknown_ref(branch2, "merge-tree",
 424                                  _("not something we can merge"));
 425
 426         init_merge_options(&opt, the_repository);
 427
 428         opt.show_rename_progress = 0;
 429
 430         opt.branch1 = branch1;
 431         opt.branch2 = branch2;
 432
 433         /*
 434          * Get the merge bases, in reverse order; see comment above
 435          * merge_incore_recursive in merge-ort.h
 436          */
 437         merge_bases = get_merge_bases(parent1, parent2);
 438         if (!merge_bases && !o->allow_unrelated_histories)
 439                 die(_("refusing to merge unrelated histories"));
 440         merge_bases = reverse_commit_list(merge_bases);
 441
 442         merge_incore_recursive(&opt, merge_bases, parent1, parent2, &result);
 443         if (result.clean < 0)
 444                 die(_("failure to merge"));
 445
 446         if (o->show_messages == -1)
 447                 o->show_messages = !result.clean;
 448
 449         printf("%s%c", oid_to_hex(&result.tree->object.oid), line_termination);
 450         if (!result.clean) {
 451                 struct string_list conflicted_files = STRING_LIST_INIT_NODUP;
 452                 const char *last = NULL;
 453                 int i;
 454
 455                 merge_get_conflicted_files(&result, &conflicted_files);
 456                 for (i = 0; i < conflicted_files.nr; i++) {
 457                         const char *name = conflicted_files.items[i].string;
 458                         struct stage_info *c = conflicted_files.items[i].util;
 459                         if (!o->name_only)
 460                                 printf("%06o %s %d\t",
 461                                        c->mode, oid_to_hex(&c->oid), c->stage);
 462                         else if (last && !strcmp(last, name))
 463                                 continue;
 464                         write_name_quoted_relative(
 465                                 name, prefix, stdout, line_termination);
 466                         last = name;
 467                 }
 468                 string_list_clear(&conflicted_files, 1);
 469         }
 470         if (o->show_messages) {
 471                 putchar(line_termination);
 472                 merge_display_update_messages(&opt, line_termination == '\0',
 473                                               &result);
 474         }
 475         merge_finalize(&opt, &result);
 476         return !result.clean; /* result.clean < 0 handled above */
 477 }
 478
 479 int cmd_merge_tree(int argc, const char **argv, const char *prefix)
 480 {
 481         struct merge_tree_options o = { .show_messages = -1 };
 482         int expected_remaining_argc;
 483         int original_argc;
 484
 485         const char * const merge_tree_usage[] = {
 486                 N_("git merge-tree [--write-tree] [<options>] <branch1> <branch2>"),
 487                 N_("git merge-tree [--trivial-merge] <base-tree> <branch1> <branch2>"),
 488                 NULL
 489         };
 490         struct option mt_options[] = {
 491                 OPT_CMDMODE(0, "write-tree", &o.mode,
 492                             N_("do a real merge instead of a trivial merge"),
 493                             MODE_REAL),
 494                 OPT_CMDMODE(0, "trivial-merge", &o.mode,
 495                             N_("do a trivial merge only"), MODE_TRIVIAL),
 496                 OPT_BOOL(0, "messages", &o.show_messages,
 497                          N_("also show informational/conflict messages")),
 498                 OPT_SET_INT('z', NULL, &line_termination,
 499                             N_("separate paths with the NUL character"), '\0'),
 500                 OPT_BOOL_F(0, "name-only",
 501                            &o.name_only,
 502                            N_("list filenames without modes/oids/stages"),
 503                            PARSE_OPT_NONEG),
 504                 OPT_BOOL_F(0, "allow-unrelated-histories",
 505                            &o.allow_unrelated_histories,
 506                            N_("allow merging unrelated histories"),
 507                            PARSE_OPT_NONEG),
 508                 OPT_END()
 509         };
 510
 511         /* Parse arguments */
 512         original_argc = argc - 1; /* ignoring argv[0] */
 513         argc = parse_options(argc, argv, prefix, mt_options,
 514                              merge_tree_usage, PARSE_OPT_STOP_AT_NON_OPTION);
 515         switch (o.mode) {
 516         default:
 517                 BUG("unexpected command mode %d", o.mode);
 518         case MODE_UNKNOWN:
 519                 switch (argc) {
 520                 default:
 521                         usage_with_options(merge_tree_usage, mt_options);
 522                 case 2:
 523                         o.mode = MODE_REAL;
 524                         break;
 525                 case 3:
 526                         o.mode = MODE_TRIVIAL;
 527                         break;
 528                 }
 529                 expected_remaining_argc = argc;
 530                 break;
 531         case MODE_REAL:
 532                 expected_remaining_argc = 2;
 533                 break;
 534         case MODE_TRIVIAL:
 535                 expected_remaining_argc = 3;
 536                 /* Removal of `--trivial-merge` is expected */
 537                 original_argc--;
 538                 break;
 539         }
 540         if (o.mode == MODE_TRIVIAL && argc < original_argc)
 541                 die(_("--trivial-merge is incompatible with all other options"));
 542
 543         if (argc != expected_remaining_argc)
 544                 usage_with_options(merge_tree_usage, mt_options);
 545
 546         /* Do the relevant type of merge */
 547         if (o.mode == MODE_REAL)
 548                 return real_merge(&o, argv[0], argv[1], prefix);
 549         else
 550                 return trivial_merge(argv[0], argv[1], argv[2]);
 551 }