merge-ort.c

   1 /*
   2  * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
   3  * as a drop-in replacement for the "recursive" merge strategy, allowing one
   4  * to replace
   5  *
   6  *   git merge [-s recursive]
   7  *
   8  * with
   9  *
  10  *   git merge -s ort
  11  *
  12  * Note: git's parser allows the space between '-s' and its argument to be
  13  * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
  14  * "cale", "peedy", or "ins" instead of "ort"?)
  15  */
  16
  17 #include "cache.h"
  18 #include "merge-ort.h"
  19
  20 #include "diff.h"
  21 #include "diffcore.h"
  22 #include "object-store.h"
  23 #include "strmap.h"
  24 #include "tree.h"
  25 #include "xdiff-interface.h"
  26
  27 /*
  28  * We have many arrays of size 3.  Whenever we have such an array, the
  29  * indices refer to one of the sides of the three-way merge.  This is so
  30  * pervasive that the constants 0, 1, and 2 are used in many places in the
  31  * code (especially in arithmetic operations to find the other side's index
  32  * or to compute a relevant mask), but sometimes these enum names are used
  33  * to aid code clarity.
  34  *
  35  * See also 'filemask' and 'dirmask' in struct conflict_info; the "ith side"
  36  * referred to there is one of these three sides.
  37  */
  38 enum merge_side {
  39         MERGE_BASE = 0,
  40         MERGE_SIDE1 = 1,
  41         MERGE_SIDE2 = 2
  42 };
  43
  44 struct merge_options_internal {
  45         /*
  46          * paths: primary data structure in all of merge ort.
  47          *
  48          * The keys of paths:
  49          *   * are full relative paths from the toplevel of the repository
  50          *     (e.g. "drivers/firmware/raspberrypi.c").
  51          *   * store all relevant paths in the repo, both directories and
  52          *     files (e.g. drivers, drivers/firmware would also be included)
  53          *   * these keys serve to intern all the path strings, which allows
  54          *     us to do pointer comparison on directory names instead of
  55          *     strcmp; we just have to be careful to use the interned strings.
  56          *
  57          * The values of paths:
  58          *   * either a pointer to a merged_info, or a conflict_info struct
  59          *   * merged_info contains all relevant information for a
  60          *     non-conflicted entry.
  61          *   * conflict_info contains a merged_info, plus any additional
  62          *     information about a conflict such as the higher orders stages
  63          *     involved and the names of the paths those came from (handy
  64          *     once renames get involved).
  65          *   * a path may start "conflicted" (i.e. point to a conflict_info)
  66          *     and then a later step (e.g. three-way content merge) determines
  67          *     it can be cleanly merged, at which point it'll be marked clean
  68          *     and the algorithm will ignore any data outside the contained
  69          *     merged_info for that entry
  70          *   * If an entry remains conflicted, the merged_info portion of a
  71          *     conflict_info will later be filled with whatever version of
  72          *     the file should be placed in the working directory (e.g. an
  73          *     as-merged-as-possible variation that contains conflict markers).
  74          */
  75         struct strmap paths;
  76
  77         /*
  78          * conflicted: a subset of keys->values from "paths"
  79          *
  80          * conflicted is basically an optimization between process_entries()
  81          * and record_conflicted_index_entries(); the latter could loop over
  82          * ALL the entries in paths AGAIN and look for the ones that are
  83          * still conflicted, but since process_entries() has to loop over
  84          * all of them, it saves the ones it couldn't resolve in this strmap
  85          * so that record_conflicted_index_entries() can iterate just the
  86          * relevant entries.
  87          */
  88         struct strmap conflicted;
  89
  90         /*
  91          * current_dir_name: temporary var used in collect_merge_info_callback()
  92          *
  93          * Used to set merged_info.directory_name; see documentation for that
  94          * variable and the requirements placed on that field.
  95          */
  96         const char *current_dir_name;
  97
  98         /* call_depth: recursion level counter for merging merge bases */
  99         int call_depth;
 100 };
 101
 102 struct version_info {
 103         struct object_id oid;
 104         unsigned short mode;
 105 };
 106
 107 struct merged_info {
 108         /* if is_null, ignore result.  otherwise result has oid & mode */
 109         struct version_info result;
 110         unsigned is_null:1;
 111
 112         /*
 113          * clean: whether the path in question is cleanly merged.
 114          *
 115          * see conflict_info.merged for more details.
 116          */
 117         unsigned clean:1;
 118
 119         /*
 120          * basename_offset: offset of basename of path.
 121          *
 122          * perf optimization to avoid recomputing offset of final '/'
 123          * character in pathname (0 if no '/' in pathname).
 124          */
 125         size_t basename_offset;
 126
 127          /*
 128           * directory_name: containing directory name.
 129           *
 130           * Note that we assume directory_name is constructed such that
 131           *    strcmp(dir1_name, dir2_name) == 0 iff dir1_name == dir2_name,
 132           * i.e. string equality is equivalent to pointer equality.  For this
 133           * to hold, we have to be careful setting directory_name.
 134           */
 135         const char *directory_name;
 136 };
 137
 138 struct conflict_info {
 139         /*
 140          * merged: the version of the path that will be written to working tree
 141          *
 142          * WARNING: It is critical to check merged.clean and ensure it is 0
 143          * before reading any conflict_info fields outside of merged.
 144          * Allocated merge_info structs will always have clean set to 1.
 145          * Allocated conflict_info structs will have merged.clean set to 0
 146          * initially.  The merged.clean field is how we know if it is safe
 147          * to access other parts of conflict_info besides merged; if a
 148          * conflict_info's merged.clean is changed to 1, the rest of the
 149          * algorithm is not allowed to look at anything outside of the
 150          * merged member anymore.
 151          */
 152         struct merged_info merged;
 153
 154         /* oids & modes from each of the three trees for this path */
 155         struct version_info stages[3];
 156
 157         /* pathnames for each stage; may differ due to rename detection */
 158         const char *pathnames[3];
 159
 160         /* Whether this path is/was involved in a directory/file conflict */
 161         unsigned df_conflict:1;
 162
 163         /*
 164          * For filemask and dirmask, the ith bit corresponds to whether the
 165          * ith entry is a file (filemask) or a directory (dirmask).  Thus,
 166          * filemask & dirmask is always zero, and filemask | dirmask is at
 167          * most 7 but can be less when a path does not appear as either a
 168          * file or a directory on at least one side of history.
 169          *
 170          * Note that these masks are related to enum merge_side, as the ith
 171          * entry corresponds to side i.
 172          *
 173          * These values come from a traverse_trees() call; more info may be
 174          * found looking at tree-walk.h's struct traverse_info,
 175          * particularly the documentation above the "fn" member (note that
 176          * filemask = mask & ~dirmask from that documentation).
 177          */
 178         unsigned filemask:3;
 179         unsigned dirmask:3;
 180
 181         /*
 182          * Optimization to track which stages match, to avoid the need to
 183          * recompute it in multiple steps. Either 0 or at least 2 bits are
 184          * set; if at least 2 bits are set, their corresponding stages match.
 185          */
 186         unsigned match_mask:3;
 187 };
 188
 189 /*
 190  * For the next three macros, see warning for conflict_info.merged.
 191  *
 192  * In each of the below, mi is a struct merged_info*, and ci was defined
 193  * as a struct conflict_info* (but we need to verify ci isn't actually
 194  * pointed at a struct merged_info*).
 195  *
 196  * INITIALIZE_CI: Assign ci to mi but only if it's safe; set to NULL otherwise.
 197  * VERIFY_CI: Ensure that something we assigned to a conflict_info* is one.
 198  * ASSIGN_AND_VERIFY_CI: Similar to VERIFY_CI but do assignment first.
 199  */
 200 #define INITIALIZE_CI(ci, mi) do {                                           \
 201         (ci) = (!(mi) || (mi)->clean) ? NULL : (struct conflict_info *)(mi); \
 202 } while (0)
 203 #define VERIFY_CI(ci) assert(ci && !ci->merged.clean);
 204 #define ASSIGN_AND_VERIFY_CI(ci, mi) do {    \
 205         (ci) = (struct conflict_info *)(mi);  \
 206         assert((ci) && !(mi)->clean);        \
 207 } while (0)
 208
 209 static int err(struct merge_options *opt, const char *err, ...)
 210 {
 211         va_list params;
 212         struct strbuf sb = STRBUF_INIT;
 213
 214         strbuf_addstr(&sb, "error: ");
 215         va_start(params, err);
 216         strbuf_vaddf(&sb, err, params);
 217         va_end(params);
 218
 219         error("%s", sb.buf);
 220         strbuf_release(&sb);
 221
 222         return -1;
 223 }
 224
 225 static void setup_path_info(struct merge_options *opt,
 226                             struct string_list_item *result,
 227                             const char *current_dir_name,
 228                             int current_dir_name_len,
 229                             char *fullpath, /* we'll take over ownership */
 230                             struct name_entry *names,
 231                             struct name_entry *merged_version,
 232                             unsigned is_null,     /* boolean */
 233                             unsigned df_conflict, /* boolean */
 234                             unsigned filemask,
 235                             unsigned dirmask,
 236                             int resolved          /* boolean */)
 237 {
 238         /* result->util is void*, so mi is a convenience typed variable */
 239         struct merged_info *mi;
 240
 241         assert(!is_null || resolved);
 242         assert(!df_conflict || !resolved); /* df_conflict implies !resolved */
 243         assert(resolved == (merged_version != NULL));
 244
 245         mi = xcalloc(1, resolved ? sizeof(struct merged_info) :
 246                                    sizeof(struct conflict_info));
 247         mi->directory_name = current_dir_name;
 248         mi->basename_offset = current_dir_name_len;
 249         mi->clean = !!resolved;
 250         if (resolved) {
 251                 mi->result.mode = merged_version->mode;
 252                 oidcpy(&mi->result.oid, &merged_version->oid);
 253                 mi->is_null = !!is_null;
 254         } else {
 255                 int i;
 256                 struct conflict_info *ci;
 257
 258                 ASSIGN_AND_VERIFY_CI(ci, mi);
 259                 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
 260                         ci->pathnames[i] = fullpath;
 261                         ci->stages[i].mode = names[i].mode;
 262                         oidcpy(&ci->stages[i].oid, &names[i].oid);
 263                 }
 264                 ci->filemask = filemask;
 265                 ci->dirmask = dirmask;
 266                 ci->df_conflict = !!df_conflict;
 267                 if (dirmask)
 268                         /*
 269                          * Assume is_null for now, but if we have entries
 270                          * under the directory then when it is complete in
 271                          * write_completed_directory() it'll update this.
 272                          * Also, for D/F conflicts, we have to handle the
 273                          * directory first, then clear this bit and process
 274                          * the file to see how it is handled -- that occurs
 275                          * near the top of process_entry().
 276                          */
 277                         mi->is_null = 1;
 278         }
 279         strmap_put(&opt->priv->paths, fullpath, mi);
 280         result->string = fullpath;
 281         result->util = mi;
 282 }
 283
 284 static int collect_merge_info_callback(int n,
 285                                        unsigned long mask,
 286                                        unsigned long dirmask,
 287                                        struct name_entry *names,
 288                                        struct traverse_info *info)
 289 {
 290         /*
 291          * n is 3.  Always.
 292          * common ancestor (mbase) has mask 1, and stored in index 0 of names
 293          * head of side 1  (side1) has mask 2, and stored in index 1 of names
 294          * head of side 2  (side2) has mask 4, and stored in index 2 of names
 295          */
 296         struct merge_options *opt = info->data;
 297         struct merge_options_internal *opti = opt->priv;
 298         struct string_list_item pi;  /* Path Info */
 299         struct conflict_info *ci; /* typed alias to pi.util (which is void*) */
 300         struct name_entry *p;
 301         size_t len;
 302         char *fullpath;
 303         const char *dirname = opti->current_dir_name;
 304         unsigned filemask = mask & ~dirmask;
 305         unsigned match_mask = 0; /* will be updated below */
 306         unsigned mbase_null = !(mask & 1);
 307         unsigned side1_null = !(mask & 2);
 308         unsigned side2_null = !(mask & 4);
 309         unsigned side1_matches_mbase = (!side1_null && !mbase_null &&
 310                                         names[0].mode == names[1].mode &&
 311                                         oideq(&names[0].oid, &names[1].oid));
 312         unsigned side2_matches_mbase = (!side2_null && !mbase_null &&
 313                                         names[0].mode == names[2].mode &&
 314                                         oideq(&names[0].oid, &names[2].oid));
 315         unsigned sides_match = (!side1_null && !side2_null &&
 316                                 names[1].mode == names[2].mode &&
 317                                 oideq(&names[1].oid, &names[2].oid));
 318
 319         /*
 320          * Note: When a path is a file on one side of history and a directory
 321          * in another, we have a directory/file conflict.  In such cases, if
 322          * the conflict doesn't resolve from renames and deletions, then we
 323          * always leave directories where they are and move files out of the
 324          * way.  Thus, while struct conflict_info has a df_conflict field to
 325          * track such conflicts, we ignore that field for any directories at
 326          * a path and only pay attention to it for files at the given path.
 327          * The fact that we leave directories were they are also means that
 328          * we do not need to worry about getting additional df_conflict
 329          * information propagated from parent directories down to children
 330          * (unlike, say traverse_trees_recursive() in unpack-trees.c, which
 331          * sets a newinfo.df_conflicts field specifically to propagate it).
 332          */
 333         unsigned df_conflict = (filemask != 0) && (dirmask != 0);
 334
 335         /* n = 3 is a fundamental assumption. */
 336         if (n != 3)
 337                 BUG("Called collect_merge_info_callback wrong");
 338
 339         /*
 340          * A bunch of sanity checks verifying that traverse_trees() calls
 341          * us the way I expect.  Could just remove these at some point,
 342          * though maybe they are helpful to future code readers.
 343          */
 344         assert(mbase_null == is_null_oid(&names[0].oid));
 345         assert(side1_null == is_null_oid(&names[1].oid));
 346         assert(side2_null == is_null_oid(&names[2].oid));
 347         assert(!mbase_null || !side1_null || !side2_null);
 348         assert(mask > 0 && mask < 8);
 349
 350         /* Determine match_mask */
 351         if (side1_matches_mbase)
 352                 match_mask = (side2_matches_mbase ? 7 : 3);
 353         else if (side2_matches_mbase)
 354                 match_mask = 5;
 355         else if (sides_match)
 356                 match_mask = 6;
 357
 358         /*
 359          * Get the name of the relevant filepath, which we'll pass to
 360          * setup_path_info() for tracking.
 361          */
 362         p = names;
 363         while (!p->mode)
 364                 p++;
 365         len = traverse_path_len(info, p->pathlen);
 366
 367         /* +1 in both of the following lines to include the NUL byte */
 368         fullpath = xmalloc(len + 1);
 369         make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen);
 370
 371         /*
 372          * If mbase, side1, and side2 all match, we can resolve early.  Even
 373          * if these are trees, there will be no renames or anything
 374          * underneath.
 375          */
 376         if (side1_matches_mbase && side2_matches_mbase) {
 377                 /* mbase, side1, & side2 all match; use mbase as resolution */
 378                 setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
 379                                 names, names+0, mbase_null, 0,
 380                                 filemask, dirmask, 1);
 381                 return mask;
 382         }
 383
 384         /*
 385          * Record information about the path so we can resolve later in
 386          * process_entries.
 387          */
 388         setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
 389                         names, NULL, 0, df_conflict, filemask, dirmask, 0);
 390
 391         ci = pi.util;
 392         VERIFY_CI(ci);
 393         ci->match_mask = match_mask;
 394
 395         /* If dirmask, recurse into subdirectories */
 396         if (dirmask) {
 397                 struct traverse_info newinfo;
 398                 struct tree_desc t[3];
 399                 void *buf[3] = {NULL, NULL, NULL};
 400                 const char *original_dir_name;
 401                 int i, ret;
 402
 403                 ci->match_mask &= filemask;
 404                 newinfo = *info;
 405                 newinfo.prev = info;
 406                 newinfo.name = p->path;
 407                 newinfo.namelen = p->pathlen;
 408                 newinfo.pathlen = st_add3(newinfo.pathlen, p->pathlen, 1);
 409                 /*
 410                  * If this directory we are about to recurse into cared about
 411                  * its parent directory (the current directory) having a D/F
 412                  * conflict, then we'd propagate the masks in this way:
 413                  *    newinfo.df_conflicts |= (mask & ~dirmask);
 414                  * But we don't worry about propagating D/F conflicts.  (See
 415                  * comment near setting of local df_conflict variable near
 416                  * the beginning of this function).
 417                  */
 418
 419                 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++) {
 420                         if (i == 1 && side1_matches_mbase)
 421                                 t[1] = t[0];
 422                         else if (i == 2 && side2_matches_mbase)
 423                                 t[2] = t[0];
 424                         else if (i == 2 && sides_match)
 425                                 t[2] = t[1];
 426                         else {
 427                                 const struct object_id *oid = NULL;
 428                                 if (dirmask & 1)
 429                                         oid = &names[i].oid;
 430                                 buf[i] = fill_tree_descriptor(opt->repo,
 431                                                               t + i, oid);
 432                         }
 433                         dirmask >>= 1;
 434                 }
 435
 436                 original_dir_name = opti->current_dir_name;
 437                 opti->current_dir_name = pi.string;
 438                 ret = traverse_trees(NULL, 3, t, &newinfo);
 439                 opti->current_dir_name = original_dir_name;
 440
 441                 for (i = MERGE_BASE; i <= MERGE_SIDE2; i++)
 442                         free(buf[i]);
 443
 444                 if (ret < 0)
 445                         return -1;
 446         }
 447
 448         return mask;
 449 }
 450
 451 static int collect_merge_info(struct merge_options *opt,
 452                               struct tree *merge_base,
 453                               struct tree *side1,
 454                               struct tree *side2)
 455 {
 456         int ret;
 457         struct tree_desc t[3];
 458         struct traverse_info info;
 459         const char *toplevel_dir_placeholder = "";
 460
 461         opt->priv->current_dir_name = toplevel_dir_placeholder;
 462         setup_traverse_info(&info, toplevel_dir_placeholder);
 463         info.fn = collect_merge_info_callback;
 464         info.data = opt;
 465         info.show_all_errors = 1;
 466
 467         parse_tree(merge_base);
 468         parse_tree(side1);
 469         parse_tree(side2);
 470         init_tree_desc(t + 0, merge_base->buffer, merge_base->size);
 471         init_tree_desc(t + 1, side1->buffer, side1->size);
 472         init_tree_desc(t + 2, side2->buffer, side2->size);
 473
 474         ret = traverse_trees(NULL, 3, t, &info);
 475
 476         return ret;
 477 }
 478
 479 static int detect_and_process_renames(struct merge_options *opt,
 480                                       struct tree *merge_base,
 481                                       struct tree *side1,
 482                                       struct tree *side2)
 483 {
 484         int clean = 1;
 485
 486         /*
 487          * Rename detection works by detecting file similarity.  Here we use
 488          * a really easy-to-implement scheme: files are similar IFF they have
 489          * the same filename.  Therefore, by this scheme, there are no renames.
 490          *
 491          * TODO: Actually implement a real rename detection scheme.
 492          */
 493         return clean;
 494 }
 495
 496 static int string_list_df_name_compare(const char *one, const char *two)
 497 {
 498         int onelen = strlen(one);
 499         int twolen = strlen(two);
 500         /*
 501          * Here we only care that entries for D/F conflicts are
 502          * adjacent, in particular with the file of the D/F conflict
 503          * appearing before files below the corresponding directory.
 504          * The order of the rest of the list is irrelevant for us.
 505          *
 506          * To achieve this, we sort with df_name_compare and provide
 507          * the mode S_IFDIR so that D/F conflicts will sort correctly.
 508          * We use the mode S_IFDIR for everything else for simplicity,
 509          * since in other cases any changes in their order due to
 510          * sorting cause no problems for us.
 511          */
 512         int cmp = df_name_compare(one, onelen, S_IFDIR,
 513                                   two, twolen, S_IFDIR);
 514         /*
 515          * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
 516          * that 'foo' comes before 'foo/bar'.
 517          */
 518         if (cmp)
 519                 return cmp;
 520         return onelen - twolen;
 521 }
 522
 523 struct directory_versions {
 524         struct string_list versions;
 525 };
 526
 527 static int tree_entry_order(const void *a_, const void *b_)
 528 {
 529         const struct string_list_item *a = a_;
 530         const struct string_list_item *b = b_;
 531
 532         const struct merged_info *ami = a->util;
 533         const struct merged_info *bmi = b->util;
 534         return base_name_compare(a->string, strlen(a->string), ami->result.mode,
 535                                  b->string, strlen(b->string), bmi->result.mode);
 536 }
 537
 538 static void write_tree(struct object_id *result_oid,
 539                        struct string_list *versions,
 540                        unsigned int offset,
 541                        size_t hash_size)
 542 {
 543         size_t maxlen = 0, extra;
 544         unsigned int nr = versions->nr - offset;
 545         struct strbuf buf = STRBUF_INIT;
 546         struct string_list relevant_entries = STRING_LIST_INIT_NODUP;
 547         int i;
 548
 549         /*
 550          * We want to sort the last (versions->nr-offset) entries in versions.
 551          * Do so by abusing the string_list API a bit: make another string_list
 552          * that contains just those entries and then sort them.
 553          *
 554          * We won't use relevant_entries again and will let it just pop off the
 555          * stack, so there won't be allocation worries or anything.
 556          */
 557         relevant_entries.items = versions->items + offset;
 558         relevant_entries.nr = versions->nr - offset;
 559         QSORT(relevant_entries.items, relevant_entries.nr, tree_entry_order);
 560
 561         /* Pre-allocate some space in buf */
 562         extra = hash_size + 8; /* 8: 6 for mode, 1 for space, 1 for NUL char */
 563         for (i = 0; i < nr; i++) {
 564                 maxlen += strlen(versions->items[offset+i].string) + extra;
 565         }
 566         strbuf_grow(&buf, maxlen);
 567
 568         /* Write each entry out to buf */
 569         for (i = 0; i < nr; i++) {
 570                 struct merged_info *mi = versions->items[offset+i].util;
 571                 struct version_info *ri = &mi->result;
 572                 strbuf_addf(&buf, "%o %s%c",
 573                             ri->mode,
 574                             versions->items[offset+i].string, '\0');
 575                 strbuf_add(&buf, ri->oid.hash, hash_size);
 576         }
 577
 578         /* Write this object file out, and record in result_oid */
 579         write_object_file(buf.buf, buf.len, tree_type, result_oid);
 580         strbuf_release(&buf);
 581 }
 582
 583 static void record_entry_for_tree(struct directory_versions *dir_metadata,
 584                                   const char *path,
 585                                   struct merged_info *mi)
 586 {
 587         const char *basename;
 588
 589         if (mi->is_null)
 590                 /* nothing to record */
 591                 return;
 592
 593         basename = path + mi->basename_offset;
 594         assert(strchr(basename, '/') == NULL);
 595         string_list_append(&dir_metadata->versions,
 596                            basename)->util = &mi->result;
 597 }
 598
 599 /* Per entry merge function */
 600 static void process_entry(struct merge_options *opt,
 601                           const char *path,
 602                           struct conflict_info *ci,
 603                           struct directory_versions *dir_metadata)
 604 {
 605         VERIFY_CI(ci);
 606         assert(ci->filemask >= 0 && ci->filemask <= 7);
 607         /* ci->match_mask == 7 was handled in collect_merge_info_callback() */
 608         assert(ci->match_mask == 0 || ci->match_mask == 3 ||
 609                ci->match_mask == 5 || ci->match_mask == 6);
 610
 611         if (ci->dirmask) {
 612                 record_entry_for_tree(dir_metadata, path, &ci->merged);
 613                 if (ci->filemask == 0)
 614                         /* nothing else to handle */
 615                         return;
 616                 assert(ci->df_conflict);
 617         }
 618
 619         if (ci->df_conflict) {
 620                 die("Not yet implemented.");
 621         }
 622
 623         /*
 624          * NOTE: Below there is a long switch-like if-elseif-elseif... block
 625          *       which the code goes through even for the df_conflict cases
 626          *       above.  Well, it will once we don't die-not-implemented above.
 627          */
 628         if (ci->match_mask) {
 629                 ci->merged.clean = 1;
 630                 if (ci->match_mask == 6) {
 631                         /* stages[1] == stages[2] */
 632                         ci->merged.result.mode = ci->stages[1].mode;
 633                         oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
 634                 } else {
 635                         /* determine the mask of the side that didn't match */
 636                         unsigned int othermask = 7 & ~ci->match_mask;
 637                         int side = (othermask == 4) ? 2 : 1;
 638
 639                         ci->merged.result.mode = ci->stages[side].mode;
 640                         ci->merged.is_null = !ci->merged.result.mode;
 641                         oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
 642
 643                         assert(othermask == 2 || othermask == 4);
 644                         assert(ci->merged.is_null ==
 645                                (ci->filemask == ci->match_mask));
 646                 }
 647         } else if (ci->filemask >= 6 &&
 648                    (S_IFMT & ci->stages[1].mode) !=
 649                    (S_IFMT & ci->stages[2].mode)) {
 650                 /*
 651                  * Two different items from (file/submodule/symlink)
 652                  */
 653                 die("Not yet implemented.");
 654         } else if (ci->filemask >= 6) {
 655                 /*
 656                  * TODO: Needs a two-way or three-way content merge, but we're
 657                  * just being lazy and copying the version from HEAD and
 658                  * leaving it as conflicted.
 659                  */
 660                 ci->merged.clean = 0;
 661                 ci->merged.result.mode = ci->stages[1].mode;
 662                 oidcpy(&ci->merged.result.oid, &ci->stages[1].oid);
 663         } else if (ci->filemask == 3 || ci->filemask == 5) {
 664                 /* Modify/delete */
 665                 die("Not yet implemented.");
 666         } else if (ci->filemask == 2 || ci->filemask == 4) {
 667                 /* Added on one side */
 668                 int side = (ci->filemask == 4) ? 2 : 1;
 669                 ci->merged.result.mode = ci->stages[side].mode;
 670                 oidcpy(&ci->merged.result.oid, &ci->stages[side].oid);
 671                 ci->merged.clean = !ci->df_conflict;
 672         } else if (ci->filemask == 1) {
 673                 /* Deleted on both sides */
 674                 ci->merged.is_null = 1;
 675                 ci->merged.result.mode = 0;
 676                 oidcpy(&ci->merged.result.oid, &null_oid);
 677                 ci->merged.clean = 1;
 678         }
 679
 680         /*
 681          * If still conflicted, record it separately.  This allows us to later
 682          * iterate over just conflicted entries when updating the index instead
 683          * of iterating over all entries.
 684          */
 685         if (!ci->merged.clean)
 686                 strmap_put(&opt->priv->conflicted, path, ci);
 687         record_entry_for_tree(dir_metadata, path, &ci->merged);
 688 }
 689
 690 static void process_entries(struct merge_options *opt,
 691                             struct object_id *result_oid)
 692 {
 693         struct hashmap_iter iter;
 694         struct strmap_entry *e;
 695         struct string_list plist = STRING_LIST_INIT_NODUP;
 696         struct string_list_item *entry;
 697         struct directory_versions dir_metadata = { STRING_LIST_INIT_NODUP };
 698
 699         if (strmap_empty(&opt->priv->paths)) {
 700                 oidcpy(result_oid, opt->repo->hash_algo->empty_tree);
 701                 return;
 702         }
 703
 704         /* Hack to pre-allocate plist to the desired size */
 705         ALLOC_GROW(plist.items, strmap_get_size(&opt->priv->paths), plist.alloc);
 706
 707         /* Put every entry from paths into plist, then sort */
 708         strmap_for_each_entry(&opt->priv->paths, &iter, e) {
 709                 string_list_append(&plist, e->key)->util = e->value;
 710         }
 711         plist.cmp = string_list_df_name_compare;
 712         string_list_sort(&plist);
 713
 714         /*
 715          * Iterate over the items in reverse order, so we can handle paths
 716          * below a directory before needing to handle the directory itself.
 717          */
 718         for (entry = &plist.items[plist.nr-1]; entry >= plist.items; --entry) {
 719                 char *path = entry->string;
 720                 /*
 721                  * NOTE: mi may actually be a pointer to a conflict_info, but
 722                  * we have to check mi->clean first to see if it's safe to
 723                  * reassign to such a pointer type.
 724                  */
 725                 struct merged_info *mi = entry->util;
 726
 727                 if (mi->clean)
 728                         record_entry_for_tree(&dir_metadata, path, mi);
 729                 else {
 730                         struct conflict_info *ci = (struct conflict_info *)mi;
 731                         process_entry(opt, path, ci, &dir_metadata);
 732                 }
 733         }
 734
 735         /*
 736          * TODO: We can't actually write a tree yet, because dir_metadata just
 737          * contains all basenames of all files throughout the tree with their
 738          * mode and hash.  Not only is that a nonsensical tree, it will have
 739          * lots of duplicates for paths such as "Makefile" or ".gitignore".
 740          */
 741         die("Not yet implemented; need to process subtrees separately");
 742         write_tree(result_oid, &dir_metadata.versions, 0,
 743                    opt->repo->hash_algo->rawsz);
 744         string_list_clear(&plist, 0);
 745         string_list_clear(&dir_metadata.versions, 0);
 746 }
 747
 748 void merge_switch_to_result(struct merge_options *opt,
 749                             struct tree *head,
 750                             struct merge_result *result,
 751                             int update_worktree_and_index,
 752                             int display_update_msgs)
 753 {
 754         die("Not yet implemented");
 755         merge_finalize(opt, result);
 756 }
 757
 758 void merge_finalize(struct merge_options *opt,
 759                     struct merge_result *result)
 760 {
 761         die("Not yet implemented");
 762 }
 763
 764 static void merge_start(struct merge_options *opt, struct merge_result *result)
 765 {
 766         /* Sanity checks on opt */
 767         assert(opt->repo);
 768
 769         assert(opt->branch1 && opt->branch2);
 770
 771         assert(opt->detect_directory_renames >= MERGE_DIRECTORY_RENAMES_NONE &&
 772                opt->detect_directory_renames <= MERGE_DIRECTORY_RENAMES_TRUE);
 773         assert(opt->rename_limit >= -1);
 774         assert(opt->rename_score >= 0 && opt->rename_score <= MAX_SCORE);
 775         assert(opt->show_rename_progress >= 0 && opt->show_rename_progress <= 1);
 776
 777         assert(opt->xdl_opts >= 0);
 778         assert(opt->recursive_variant >= MERGE_VARIANT_NORMAL &&
 779                opt->recursive_variant <= MERGE_VARIANT_THEIRS);
 780
 781         /*
 782          * detect_renames, verbosity, buffer_output, and obuf are ignored
 783          * fields that were used by "recursive" rather than "ort" -- but
 784          * sanity check them anyway.
 785          */
 786         assert(opt->detect_renames >= -1 &&
 787                opt->detect_renames <= DIFF_DETECT_COPY);
 788         assert(opt->verbosity >= 0 && opt->verbosity <= 5);
 789         assert(opt->buffer_output <= 2);
 790         assert(opt->obuf.len == 0);
 791
 792         assert(opt->priv == NULL);
 793
 794         /* Default to histogram diff.  Actually, just hardcode it...for now. */
 795         opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
 796
 797         /* Initialization of opt->priv, our internal merge data */
 798         opt->priv = xcalloc(1, sizeof(*opt->priv));
 799
 800         /*
 801          * Although we initialize opt->priv->paths with strdup_strings=0,
 802          * that's just to avoid making yet another copy of an allocated
 803          * string.  Putting the entry into paths means we are taking
 804          * ownership, so we will later free it.
 805          *
 806          * In contrast, conflicted just has a subset of keys from paths, so
 807          * we don't want to free those (it'd be a duplicate free).
 808          */
 809         strmap_init_with_options(&opt->priv->paths, NULL, 0);
 810         strmap_init_with_options(&opt->priv->conflicted, NULL, 0);
 811 }
 812
 813 /*
 814  * Originally from merge_trees_internal(); heavily adapted, though.
 815  */
 816 static void merge_ort_nonrecursive_internal(struct merge_options *opt,
 817                                             struct tree *merge_base,
 818                                             struct tree *side1,
 819                                             struct tree *side2,
 820                                             struct merge_result *result)
 821 {
 822         struct object_id working_tree_oid;
 823
 824         if (collect_merge_info(opt, merge_base, side1, side2) != 0) {
 825                 /*
 826                  * TRANSLATORS: The %s arguments are: 1) tree hash of a merge
 827                  * base, and 2-3) the trees for the two trees we're merging.
 828                  */
 829                 err(opt, _("collecting merge info failed for trees %s, %s, %s"),
 830                     oid_to_hex(&merge_base->object.oid),
 831                     oid_to_hex(&side1->object.oid),
 832                     oid_to_hex(&side2->object.oid));
 833                 result->clean = -1;
 834                 return;
 835         }
 836
 837         result->clean = detect_and_process_renames(opt, merge_base,
 838                                                    side1, side2);
 839         process_entries(opt, &working_tree_oid);
 840
 841         /* Set return values */
 842         result->tree = parse_tree_indirect(&working_tree_oid);
 843         /* existence of conflicted entries implies unclean */
 844         result->clean &= strmap_empty(&opt->priv->conflicted);
 845         if (!opt->priv->call_depth) {
 846                 result->priv = opt->priv;
 847                 opt->priv = NULL;
 848         }
 849 }
 850
 851 void merge_incore_nonrecursive(struct merge_options *opt,
 852                                struct tree *merge_base,
 853                                struct tree *side1,
 854                                struct tree *side2,
 855                                struct merge_result *result)
 856 {
 857         assert(opt->ancestor != NULL);
 858         merge_start(opt, result);
 859         merge_ort_nonrecursive_internal(opt, merge_base, side1, side2, result);
 860 }
 861
 862 void merge_incore_recursive(struct merge_options *opt,
 863                             struct commit_list *merge_bases,
 864                             struct commit *side1,
 865                             struct commit *side2,
 866                             struct merge_result *result)
 867 {
 868         die("Not yet implemented");
 869 }