unpack-trees.con commit Merge branch 'nd/struct-pathspec' (240fe05)
   1#define NO_THE_INDEX_COMPATIBILITY_MACROS
   2#include "cache.h"
   3#include "dir.h"
   4#include "tree.h"
   5#include "tree-walk.h"
   6#include "cache-tree.h"
   7#include "unpack-trees.h"
   8#include "progress.h"
   9#include "refs.h"
  10#include "attr.h"
  11
  12/*
  13 * Error messages expected by scripts out of plumbing commands such as
  14 * read-tree.  Non-scripted Porcelain is not required to use these messages
  15 * and in fact are encouraged to reword them to better suit their particular
  16 * situation better.  See how "git checkout" and "git merge" replaces
  17 * them using setup_unpack_trees_porcelain(), for example.
  18 */
  19static const char *unpack_plumbing_errors[NB_UNPACK_TREES_ERROR_TYPES] = {
  20        /* ERROR_WOULD_OVERWRITE */
  21        "Entry '%s' would be overwritten by merge. Cannot merge.",
  22
  23        /* ERROR_NOT_UPTODATE_FILE */
  24        "Entry '%s' not uptodate. Cannot merge.",
  25
  26        /* ERROR_NOT_UPTODATE_DIR */
  27        "Updating '%s' would lose untracked files in it",
  28
  29        /* ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN */
  30        "Untracked working tree file '%s' would be overwritten by merge.",
  31
  32        /* ERROR_WOULD_LOSE_UNTRACKED_REMOVED */
  33        "Untracked working tree file '%s' would be removed by merge.",
  34
  35        /* ERROR_BIND_OVERLAP */
  36        "Entry '%s' overlaps with '%s'.  Cannot bind.",
  37
  38        /* ERROR_SPARSE_NOT_UPTODATE_FILE */
  39        "Entry '%s' not uptodate. Cannot update sparse checkout.",
  40
  41        /* ERROR_WOULD_LOSE_ORPHANED_OVERWRITTEN */
  42        "Working tree file '%s' would be overwritten by sparse checkout update.",
  43
  44        /* ERROR_WOULD_LOSE_ORPHANED_REMOVED */
  45        "Working tree file '%s' would be removed by sparse checkout update.",
  46};
  47
  48#define ERRORMSG(o,type) \
  49        ( ((o) && (o)->msgs[(type)]) \
  50          ? ((o)->msgs[(type)])      \
  51          : (unpack_plumbing_errors[(type)]) )
  52
  53void setup_unpack_trees_porcelain(struct unpack_trees_options *opts,
  54                                  const char *cmd)
  55{
  56        int i;
  57        const char **msgs = opts->msgs;
  58        const char *msg;
  59        char *tmp;
  60        const char *cmd2 = strcmp(cmd, "checkout") ? cmd : "switch branches";
  61        if (advice_commit_before_merge)
  62                msg = "Your local changes to the following files would be overwritten by %s:\n%%s"
  63                        "Please, commit your changes or stash them before you can %s.";
  64        else
  65                msg = "Your local changes to the following files would be overwritten by %s:\n%%s";
  66        tmp = xmalloc(strlen(msg) + strlen(cmd) + strlen(cmd2) - 2);
  67        sprintf(tmp, msg, cmd, cmd2);
  68        msgs[ERROR_WOULD_OVERWRITE] = tmp;
  69        msgs[ERROR_NOT_UPTODATE_FILE] = tmp;
  70
  71        msgs[ERROR_NOT_UPTODATE_DIR] =
  72                "Updating the following directories would lose untracked files in it:\n%s";
  73
  74        if (advice_commit_before_merge)
  75                msg = "The following untracked working tree files would be %s by %s:\n%%s"
  76                        "Please move or remove them before you can %s.";
  77        else
  78                msg = "The following untracked working tree files would be %s by %s:\n%%s";
  79        tmp = xmalloc(strlen(msg) + strlen(cmd) + strlen("removed") + strlen(cmd2) - 4);
  80        sprintf(tmp, msg, "removed", cmd, cmd2);
  81        msgs[ERROR_WOULD_LOSE_UNTRACKED_REMOVED] = tmp;
  82        tmp = xmalloc(strlen(msg) + strlen(cmd) + strlen("overwritten") + strlen(cmd2) - 4);
  83        sprintf(tmp, msg, "overwritten", cmd, cmd2);
  84        msgs[ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN] = tmp;
  85
  86        /*
  87         * Special case: ERROR_BIND_OVERLAP refers to a pair of paths, we
  88         * cannot easily display it as a list.
  89         */
  90        msgs[ERROR_BIND_OVERLAP] = "Entry '%s' overlaps with '%s'.  Cannot bind.";
  91
  92        msgs[ERROR_SPARSE_NOT_UPTODATE_FILE] =
  93                "Cannot update sparse checkout: the following entries are not up-to-date:\n%s";
  94        msgs[ERROR_WOULD_LOSE_ORPHANED_OVERWRITTEN] =
  95                "The following Working tree files would be overwritten by sparse checkout update:\n%s";
  96        msgs[ERROR_WOULD_LOSE_ORPHANED_REMOVED] =
  97                "The following Working tree files would be removed by sparse checkout update:\n%s";
  98
  99        opts->show_all_errors = 1;
 100        /* rejected paths may not have a static buffer */
 101        for (i = 0; i < ARRAY_SIZE(opts->unpack_rejects); i++)
 102                opts->unpack_rejects[i].strdup_strings = 1;
 103}
 104
 105static void add_entry(struct unpack_trees_options *o, struct cache_entry *ce,
 106        unsigned int set, unsigned int clear)
 107{
 108        unsigned int size = ce_size(ce);
 109        struct cache_entry *new = xmalloc(size);
 110
 111        clear |= CE_HASHED | CE_UNHASHED;
 112
 113        if (set & CE_REMOVE)
 114                set |= CE_WT_REMOVE;
 115
 116        memcpy(new, ce, size);
 117        new->next = NULL;
 118        new->ce_flags = (new->ce_flags & ~clear) | set;
 119        add_index_entry(&o->result, new, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE);
 120}
 121
 122/*
 123 * add error messages on path <path>
 124 * corresponding to the type <e> with the message <msg>
 125 * indicating if it should be display in porcelain or not
 126 */
 127static int add_rejected_path(struct unpack_trees_options *o,
 128                             enum unpack_trees_error_types e,
 129                             const char *path)
 130{
 131        if (!o->show_all_errors)
 132                return error(ERRORMSG(o, e), path);
 133
 134        /*
 135         * Otherwise, insert in a list for future display by
 136         * display_error_msgs()
 137         */
 138        string_list_append(&o->unpack_rejects[e], path);
 139        return -1;
 140}
 141
 142/*
 143 * display all the error messages stored in a nice way
 144 */
 145static void display_error_msgs(struct unpack_trees_options *o)
 146{
 147        int e, i;
 148        int something_displayed = 0;
 149        for (e = 0; e < NB_UNPACK_TREES_ERROR_TYPES; e++) {
 150                struct string_list *rejects = &o->unpack_rejects[e];
 151                if (rejects->nr > 0) {
 152                        struct strbuf path = STRBUF_INIT;
 153                        something_displayed = 1;
 154                        for (i = 0; i < rejects->nr; i++)
 155                                strbuf_addf(&path, "\t%s\n", rejects->items[i].string);
 156                        error(ERRORMSG(o, e), path.buf);
 157                        strbuf_release(&path);
 158                }
 159                string_list_clear(rejects, 0);
 160        }
 161        if (something_displayed)
 162                printf("Aborting\n");
 163}
 164
 165/*
 166 * Unlink the last component and schedule the leading directories for
 167 * removal, such that empty directories get removed.
 168 */
 169static void unlink_entry(struct cache_entry *ce)
 170{
 171        if (!check_leading_path(ce->name, ce_namelen(ce)))
 172                return;
 173        if (remove_or_warn(ce->ce_mode, ce->name))
 174                return;
 175        schedule_dir_for_removal(ce->name, ce_namelen(ce));
 176}
 177
 178static struct checkout state;
 179static int check_updates(struct unpack_trees_options *o)
 180{
 181        unsigned cnt = 0, total = 0;
 182        struct progress *progress = NULL;
 183        struct index_state *index = &o->result;
 184        int i;
 185        int errs = 0;
 186
 187        if (o->update && o->verbose_update) {
 188                for (total = cnt = 0; cnt < index->cache_nr; cnt++) {
 189                        struct cache_entry *ce = index->cache[cnt];
 190                        if (ce->ce_flags & (CE_UPDATE | CE_WT_REMOVE))
 191                                total++;
 192                }
 193
 194                progress = start_progress_delay("Checking out files",
 195                                                total, 50, 1);
 196                cnt = 0;
 197        }
 198
 199        if (o->update)
 200                git_attr_set_direction(GIT_ATTR_CHECKOUT, &o->result);
 201        for (i = 0; i < index->cache_nr; i++) {
 202                struct cache_entry *ce = index->cache[i];
 203
 204                if (ce->ce_flags & CE_WT_REMOVE) {
 205                        display_progress(progress, ++cnt);
 206                        if (o->update)
 207                                unlink_entry(ce);
 208                        continue;
 209                }
 210        }
 211        remove_marked_cache_entries(&o->result);
 212        remove_scheduled_dirs();
 213
 214        for (i = 0; i < index->cache_nr; i++) {
 215                struct cache_entry *ce = index->cache[i];
 216
 217                if (ce->ce_flags & CE_UPDATE) {
 218                        display_progress(progress, ++cnt);
 219                        ce->ce_flags &= ~CE_UPDATE;
 220                        if (o->update) {
 221                                errs |= checkout_entry(ce, &state, NULL);
 222                        }
 223                }
 224        }
 225        stop_progress(&progress);
 226        if (o->update)
 227                git_attr_set_direction(GIT_ATTR_CHECKIN, NULL);
 228        return errs != 0;
 229}
 230
 231static int verify_uptodate_sparse(struct cache_entry *ce, struct unpack_trees_options *o);
 232static int verify_absent_sparse(struct cache_entry *ce, enum unpack_trees_error_types, struct unpack_trees_options *o);
 233
 234static int apply_sparse_checkout(struct cache_entry *ce, struct unpack_trees_options *o)
 235{
 236        int was_skip_worktree = ce_skip_worktree(ce);
 237
 238        if (ce->ce_flags & CE_NEW_SKIP_WORKTREE)
 239                ce->ce_flags |= CE_SKIP_WORKTREE;
 240        else
 241                ce->ce_flags &= ~CE_SKIP_WORKTREE;
 242
 243        /*
 244         * if (!was_skip_worktree && !ce_skip_worktree()) {
 245         *      This is perfectly normal. Move on;
 246         * }
 247         */
 248
 249        /*
 250         * Merge strategies may set CE_UPDATE|CE_REMOVE outside checkout
 251         * area as a result of ce_skip_worktree() shortcuts in
 252         * verify_absent() and verify_uptodate().
 253         * Make sure they don't modify worktree if they are already
 254         * outside checkout area
 255         */
 256        if (was_skip_worktree && ce_skip_worktree(ce)) {
 257                ce->ce_flags &= ~CE_UPDATE;
 258
 259                /*
 260                 * By default, when CE_REMOVE is on, CE_WT_REMOVE is also
 261                 * on to get that file removed from both index and worktree.
 262                 * If that file is already outside worktree area, don't
 263                 * bother remove it.
 264                 */
 265                if (ce->ce_flags & CE_REMOVE)
 266                        ce->ce_flags &= ~CE_WT_REMOVE;
 267        }
 268
 269        if (!was_skip_worktree && ce_skip_worktree(ce)) {
 270                /*
 271                 * If CE_UPDATE is set, verify_uptodate() must be called already
 272                 * also stat info may have lost after merged_entry() so calling
 273                 * verify_uptodate() again may fail
 274                 */
 275                if (!(ce->ce_flags & CE_UPDATE) && verify_uptodate_sparse(ce, o))
 276                        return -1;
 277                ce->ce_flags |= CE_WT_REMOVE;
 278        }
 279        if (was_skip_worktree && !ce_skip_worktree(ce)) {
 280                if (verify_absent_sparse(ce, ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o))
 281                        return -1;
 282                ce->ce_flags |= CE_UPDATE;
 283        }
 284        return 0;
 285}
 286
 287static inline int call_unpack_fn(struct cache_entry **src, struct unpack_trees_options *o)
 288{
 289        int ret = o->fn(src, o);
 290        if (ret > 0)
 291                ret = 0;
 292        return ret;
 293}
 294
 295static void mark_ce_used(struct cache_entry *ce, struct unpack_trees_options *o)
 296{
 297        ce->ce_flags |= CE_UNPACKED;
 298
 299        if (o->cache_bottom < o->src_index->cache_nr &&
 300            o->src_index->cache[o->cache_bottom] == ce) {
 301                int bottom = o->cache_bottom;
 302                while (bottom < o->src_index->cache_nr &&
 303                       o->src_index->cache[bottom]->ce_flags & CE_UNPACKED)
 304                        bottom++;
 305                o->cache_bottom = bottom;
 306        }
 307}
 308
 309static void mark_all_ce_unused(struct index_state *index)
 310{
 311        int i;
 312        for (i = 0; i < index->cache_nr; i++)
 313                index->cache[i]->ce_flags &= ~(CE_UNPACKED | CE_ADDED | CE_NEW_SKIP_WORKTREE);
 314}
 315
 316static int locate_in_src_index(struct cache_entry *ce,
 317                               struct unpack_trees_options *o)
 318{
 319        struct index_state *index = o->src_index;
 320        int len = ce_namelen(ce);
 321        int pos = index_name_pos(index, ce->name, len);
 322        if (pos < 0)
 323                pos = -1 - pos;
 324        return pos;
 325}
 326
 327/*
 328 * We call unpack_index_entry() with an unmerged cache entry
 329 * only in diff-index, and it wants a single callback.  Skip
 330 * the other unmerged entry with the same name.
 331 */
 332static void mark_ce_used_same_name(struct cache_entry *ce,
 333                                   struct unpack_trees_options *o)
 334{
 335        struct index_state *index = o->src_index;
 336        int len = ce_namelen(ce);
 337        int pos;
 338
 339        for (pos = locate_in_src_index(ce, o); pos < index->cache_nr; pos++) {
 340                struct cache_entry *next = index->cache[pos];
 341                if (len != ce_namelen(next) ||
 342                    memcmp(ce->name, next->name, len))
 343                        break;
 344                mark_ce_used(next, o);
 345        }
 346}
 347
 348static struct cache_entry *next_cache_entry(struct unpack_trees_options *o)
 349{
 350        const struct index_state *index = o->src_index;
 351        int pos = o->cache_bottom;
 352
 353        while (pos < index->cache_nr) {
 354                struct cache_entry *ce = index->cache[pos];
 355                if (!(ce->ce_flags & CE_UNPACKED))
 356                        return ce;
 357                pos++;
 358        }
 359        return NULL;
 360}
 361
 362static void add_same_unmerged(struct cache_entry *ce,
 363                              struct unpack_trees_options *o)
 364{
 365        struct index_state *index = o->src_index;
 366        int len = ce_namelen(ce);
 367        int pos = index_name_pos(index, ce->name, len);
 368
 369        if (0 <= pos)
 370                die("programming error in a caller of mark_ce_used_same_name");
 371        for (pos = -pos - 1; pos < index->cache_nr; pos++) {
 372                struct cache_entry *next = index->cache[pos];
 373                if (len != ce_namelen(next) ||
 374                    memcmp(ce->name, next->name, len))
 375                        break;
 376                add_entry(o, next, 0, 0);
 377                mark_ce_used(next, o);
 378        }
 379}
 380
 381static int unpack_index_entry(struct cache_entry *ce,
 382                              struct unpack_trees_options *o)
 383{
 384        struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
 385        int ret;
 386
 387        src[0] = ce;
 388
 389        mark_ce_used(ce, o);
 390        if (ce_stage(ce)) {
 391                if (o->skip_unmerged) {
 392                        add_entry(o, ce, 0, 0);
 393                        return 0;
 394                }
 395        }
 396        ret = call_unpack_fn(src, o);
 397        if (ce_stage(ce))
 398                mark_ce_used_same_name(ce, o);
 399        return ret;
 400}
 401
 402static int find_cache_pos(struct traverse_info *, const struct name_entry *);
 403
 404static void restore_cache_bottom(struct traverse_info *info, int bottom)
 405{
 406        struct unpack_trees_options *o = info->data;
 407
 408        if (o->diff_index_cached)
 409                return;
 410        o->cache_bottom = bottom;
 411}
 412
 413static int switch_cache_bottom(struct traverse_info *info)
 414{
 415        struct unpack_trees_options *o = info->data;
 416        int ret, pos;
 417
 418        if (o->diff_index_cached)
 419                return 0;
 420        ret = o->cache_bottom;
 421        pos = find_cache_pos(info->prev, &info->name);
 422
 423        if (pos < -1)
 424                o->cache_bottom = -2 - pos;
 425        else if (pos < 0)
 426                o->cache_bottom = o->src_index->cache_nr;
 427        return ret;
 428}
 429
 430static int traverse_trees_recursive(int n, unsigned long dirmask,
 431                                    unsigned long df_conflicts,
 432                                    struct name_entry *names,
 433                                    struct traverse_info *info)
 434{
 435        int i, ret, bottom;
 436        struct tree_desc t[MAX_UNPACK_TREES];
 437        void *buf[MAX_UNPACK_TREES];
 438        struct traverse_info newinfo;
 439        struct name_entry *p;
 440
 441        p = names;
 442        while (!p->mode)
 443                p++;
 444
 445        newinfo = *info;
 446        newinfo.prev = info;
 447        newinfo.name = *p;
 448        newinfo.pathlen += tree_entry_len(p->path, p->sha1) + 1;
 449        newinfo.conflicts |= df_conflicts;
 450
 451        for (i = 0; i < n; i++, dirmask >>= 1) {
 452                const unsigned char *sha1 = NULL;
 453                if (dirmask & 1)
 454                        sha1 = names[i].sha1;
 455                buf[i] = fill_tree_descriptor(t+i, sha1);
 456        }
 457
 458        bottom = switch_cache_bottom(&newinfo);
 459        ret = traverse_trees(n, t, &newinfo);
 460        restore_cache_bottom(&newinfo, bottom);
 461
 462        for (i = 0; i < n; i++)
 463                free(buf[i]);
 464
 465        return ret;
 466}
 467
 468/*
 469 * Compare the traverse-path to the cache entry without actually
 470 * having to generate the textual representation of the traverse
 471 * path.
 472 *
 473 * NOTE! This *only* compares up to the size of the traverse path
 474 * itself - the caller needs to do the final check for the cache
 475 * entry having more data at the end!
 476 */
 477static int do_compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
 478{
 479        int len, pathlen, ce_len;
 480        const char *ce_name;
 481
 482        if (info->prev) {
 483                int cmp = do_compare_entry(ce, info->prev, &info->name);
 484                if (cmp)
 485                        return cmp;
 486        }
 487        pathlen = info->pathlen;
 488        ce_len = ce_namelen(ce);
 489
 490        /* If ce_len < pathlen then we must have previously hit "name == directory" entry */
 491        if (ce_len < pathlen)
 492                return -1;
 493
 494        ce_len -= pathlen;
 495        ce_name = ce->name + pathlen;
 496
 497        len = tree_entry_len(n->path, n->sha1);
 498        return df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
 499}
 500
 501static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
 502{
 503        int cmp = do_compare_entry(ce, info, n);
 504        if (cmp)
 505                return cmp;
 506
 507        /*
 508         * Even if the beginning compared identically, the ce should
 509         * compare as bigger than a directory leading up to it!
 510         */
 511        return ce_namelen(ce) > traverse_path_len(info, n);
 512}
 513
 514static int ce_in_traverse_path(const struct cache_entry *ce,
 515                               const struct traverse_info *info)
 516{
 517        if (!info->prev)
 518                return 1;
 519        if (do_compare_entry(ce, info->prev, &info->name))
 520                return 0;
 521        /*
 522         * If ce (blob) is the same name as the path (which is a tree
 523         * we will be descending into), it won't be inside it.
 524         */
 525        return (info->pathlen < ce_namelen(ce));
 526}
 527
 528static struct cache_entry *create_ce_entry(const struct traverse_info *info, const struct name_entry *n, int stage)
 529{
 530        int len = traverse_path_len(info, n);
 531        struct cache_entry *ce = xcalloc(1, cache_entry_size(len));
 532
 533        ce->ce_mode = create_ce_mode(n->mode);
 534        ce->ce_flags = create_ce_flags(len, stage);
 535        hashcpy(ce->sha1, n->sha1);
 536        make_traverse_path(ce->name, info, n);
 537
 538        return ce;
 539}
 540
 541static int unpack_nondirectories(int n, unsigned long mask,
 542                                 unsigned long dirmask,
 543                                 struct cache_entry **src,
 544                                 const struct name_entry *names,
 545                                 const struct traverse_info *info)
 546{
 547        int i;
 548        struct unpack_trees_options *o = info->data;
 549        unsigned long conflicts;
 550
 551        /* Do we have *only* directories? Nothing to do */
 552        if (mask == dirmask && !src[0])
 553                return 0;
 554
 555        conflicts = info->conflicts;
 556        if (o->merge)
 557                conflicts >>= 1;
 558        conflicts |= dirmask;
 559
 560        /*
 561         * Ok, we've filled in up to any potential index entry in src[0],
 562         * now do the rest.
 563         */
 564        for (i = 0; i < n; i++) {
 565                int stage;
 566                unsigned int bit = 1ul << i;
 567                if (conflicts & bit) {
 568                        src[i + o->merge] = o->df_conflict_entry;
 569                        continue;
 570                }
 571                if (!(mask & bit))
 572                        continue;
 573                if (!o->merge)
 574                        stage = 0;
 575                else if (i + 1 < o->head_idx)
 576                        stage = 1;
 577                else if (i + 1 > o->head_idx)
 578                        stage = 3;
 579                else
 580                        stage = 2;
 581                src[i + o->merge] = create_ce_entry(info, names + i, stage);
 582        }
 583
 584        if (o->merge)
 585                return call_unpack_fn(src, o);
 586
 587        for (i = 0; i < n; i++)
 588                if (src[i] && src[i] != o->df_conflict_entry)
 589                        add_entry(o, src[i], 0, 0);
 590        return 0;
 591}
 592
 593static int unpack_failed(struct unpack_trees_options *o, const char *message)
 594{
 595        discard_index(&o->result);
 596        if (!o->gently) {
 597                if (message)
 598                        return error("%s", message);
 599                return -1;
 600        }
 601        return -1;
 602}
 603
 604/* NEEDSWORK: give this a better name and share with tree-walk.c */
 605static int name_compare(const char *a, int a_len,
 606                        const char *b, int b_len)
 607{
 608        int len = (a_len < b_len) ? a_len : b_len;
 609        int cmp = memcmp(a, b, len);
 610        if (cmp)
 611                return cmp;
 612        return (a_len - b_len);
 613}
 614
 615/*
 616 * The tree traversal is looking at name p.  If we have a matching entry,
 617 * return it.  If name p is a directory in the index, do not return
 618 * anything, as we will want to match it when the traversal descends into
 619 * the directory.
 620 */
 621static int find_cache_pos(struct traverse_info *info,
 622                          const struct name_entry *p)
 623{
 624        int pos;
 625        struct unpack_trees_options *o = info->data;
 626        struct index_state *index = o->src_index;
 627        int pfxlen = info->pathlen;
 628        int p_len = tree_entry_len(p->path, p->sha1);
 629
 630        for (pos = o->cache_bottom; pos < index->cache_nr; pos++) {
 631                struct cache_entry *ce = index->cache[pos];
 632                const char *ce_name, *ce_slash;
 633                int cmp, ce_len;
 634
 635                if (ce->ce_flags & CE_UNPACKED) {
 636                        /*
 637                         * cache_bottom entry is already unpacked, so
 638                         * we can never match it; don't check it
 639                         * again.
 640                         */
 641                        if (pos == o->cache_bottom)
 642                                ++o->cache_bottom;
 643                        continue;
 644                }
 645                if (!ce_in_traverse_path(ce, info))
 646                        continue;
 647                ce_name = ce->name + pfxlen;
 648                ce_slash = strchr(ce_name, '/');
 649                if (ce_slash)
 650                        ce_len = ce_slash - ce_name;
 651                else
 652                        ce_len = ce_namelen(ce) - pfxlen;
 653                cmp = name_compare(p->path, p_len, ce_name, ce_len);
 654                /*
 655                 * Exact match; if we have a directory we need to
 656                 * delay returning it.
 657                 */
 658                if (!cmp)
 659                        return ce_slash ? -2 - pos : pos;
 660                if (0 < cmp)
 661                        continue; /* keep looking */
 662                /*
 663                 * ce_name sorts after p->path; could it be that we
 664                 * have files under p->path directory in the index?
 665                 * E.g.  ce_name == "t-i", and p->path == "t"; we may
 666                 * have "t/a" in the index.
 667                 */
 668                if (p_len < ce_len && !memcmp(ce_name, p->path, p_len) &&
 669                    ce_name[p_len] < '/')
 670                        continue; /* keep looking */
 671                break;
 672        }
 673        return -1;
 674}
 675
 676static struct cache_entry *find_cache_entry(struct traverse_info *info,
 677                                            const struct name_entry *p)
 678{
 679        int pos = find_cache_pos(info, p);
 680        struct unpack_trees_options *o = info->data;
 681
 682        if (0 <= pos)
 683                return o->src_index->cache[pos];
 684        else
 685                return NULL;
 686}
 687
 688static void debug_path(struct traverse_info *info)
 689{
 690        if (info->prev) {
 691                debug_path(info->prev);
 692                if (*info->prev->name.path)
 693                        putchar('/');
 694        }
 695        printf("%s", info->name.path);
 696}
 697
 698static void debug_name_entry(int i, struct name_entry *n)
 699{
 700        printf("ent#%d %06o %s\n", i,
 701               n->path ? n->mode : 0,
 702               n->path ? n->path : "(missing)");
 703}
 704
 705static void debug_unpack_callback(int n,
 706                                  unsigned long mask,
 707                                  unsigned long dirmask,
 708                                  struct name_entry *names,
 709                                  struct traverse_info *info)
 710{
 711        int i;
 712        printf("* unpack mask %lu, dirmask %lu, cnt %d ",
 713               mask, dirmask, n);
 714        debug_path(info);
 715        putchar('\n');
 716        for (i = 0; i < n; i++)
 717                debug_name_entry(i, names + i);
 718}
 719
 720static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)
 721{
 722        struct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };
 723        struct unpack_trees_options *o = info->data;
 724        const struct name_entry *p = names;
 725
 726        /* Find first entry with a real name (we could use "mask" too) */
 727        while (!p->mode)
 728                p++;
 729
 730        if (o->debug_unpack)
 731                debug_unpack_callback(n, mask, dirmask, names, info);
 732
 733        /* Are we supposed to look at the index too? */
 734        if (o->merge) {
 735                while (1) {
 736                        int cmp;
 737                        struct cache_entry *ce;
 738
 739                        if (o->diff_index_cached)
 740                                ce = next_cache_entry(o);
 741                        else
 742                                ce = find_cache_entry(info, p);
 743
 744                        if (!ce)
 745                                break;
 746                        cmp = compare_entry(ce, info, p);
 747                        if (cmp < 0) {
 748                                if (unpack_index_entry(ce, o) < 0)
 749                                        return unpack_failed(o, NULL);
 750                                continue;
 751                        }
 752                        if (!cmp) {
 753                                if (ce_stage(ce)) {
 754                                        /*
 755                                         * If we skip unmerged index
 756                                         * entries, we'll skip this
 757                                         * entry *and* the tree
 758                                         * entries associated with it!
 759                                         */
 760                                        if (o->skip_unmerged) {
 761                                                add_same_unmerged(ce, o);
 762                                                return mask;
 763                                        }
 764                                }
 765                                src[0] = ce;
 766                        }
 767                        break;
 768                }
 769        }
 770
 771        if (unpack_nondirectories(n, mask, dirmask, src, names, info) < 0)
 772                return -1;
 773
 774        if (src[0]) {
 775                if (ce_stage(src[0]))
 776                        mark_ce_used_same_name(src[0], o);
 777                else
 778                        mark_ce_used(src[0], o);
 779        }
 780
 781        /* Now handle any directories.. */
 782        if (dirmask) {
 783                unsigned long conflicts = mask & ~dirmask;
 784                if (o->merge) {
 785                        conflicts <<= 1;
 786                        if (src[0])
 787                                conflicts |= 1;
 788                }
 789
 790                /* special case: "diff-index --cached" looking at a tree */
 791                if (o->diff_index_cached &&
 792                    n == 1 && dirmask == 1 && S_ISDIR(names->mode)) {
 793                        int matches;
 794                        matches = cache_tree_matches_traversal(o->src_index->cache_tree,
 795                                                               names, info);
 796                        /*
 797                         * Everything under the name matches; skip the
 798                         * entire hierarchy.  diff_index_cached codepath
 799                         * special cases D/F conflicts in such a way that
 800                         * it does not do any look-ahead, so this is safe.
 801                         */
 802                        if (matches) {
 803                                o->cache_bottom += matches;
 804                                return mask;
 805                        }
 806                }
 807
 808                if (traverse_trees_recursive(n, dirmask, conflicts,
 809                                             names, info) < 0)
 810                        return -1;
 811                return mask;
 812        }
 813
 814        return mask;
 815}
 816
 817/* Whole directory matching */
 818static int clear_ce_flags_dir(struct cache_entry **cache, int nr,
 819                              char *prefix, int prefix_len,
 820                              char *basename,
 821                              int select_mask, int clear_mask,
 822                              struct exclude_list *el)
 823{
 824        struct cache_entry **cache_end = cache + nr;
 825        int dtype = DT_DIR;
 826        int ret = excluded_from_list(prefix, prefix_len, basename, &dtype, el);
 827
 828        prefix[prefix_len++] = '/';
 829
 830        /* included, no clearing for any entries under this directory */
 831        if (!ret) {
 832                for (; cache != cache_end; cache++) {
 833                        struct cache_entry *ce = *cache;
 834                        if (strncmp(ce->name, prefix, prefix_len))
 835                                break;
 836                }
 837                return nr - (cache_end - cache);
 838        }
 839
 840        /* excluded, clear all selected entries under this directory. */
 841        if (ret == 1) {
 842                for (; cache != cache_end; cache++) {
 843                        struct cache_entry *ce = *cache;
 844                        if (select_mask && !(ce->ce_flags & select_mask))
 845                                continue;
 846                        if (strncmp(ce->name, prefix, prefix_len))
 847                                break;
 848                        ce->ce_flags &= ~clear_mask;
 849                }
 850                return nr - (cache_end - cache);
 851        }
 852
 853        return 0;
 854}
 855
 856/*
 857 * Traverse the index, find every entry that matches according to
 858 * o->el. Do "ce_flags &= ~clear_mask" on those entries. Return the
 859 * number of traversed entries.
 860 *
 861 * If select_mask is non-zero, only entries whose ce_flags has on of
 862 * those bits enabled are traversed.
 863 *
 864 * cache        : pointer to an index entry
 865 * prefix_len   : an offset to its path
 866 *
 867 * The current path ("prefix") including the trailing '/' is
 868 *   cache[0]->name[0..(prefix_len-1)]
 869 * Top level path has prefix_len zero.
 870 */
 871static int clear_ce_flags_1(struct cache_entry **cache, int nr,
 872                            char *prefix, int prefix_len,
 873                            int select_mask, int clear_mask,
 874                            struct exclude_list *el)
 875{
 876        struct cache_entry **cache_end = cache + nr;
 877
 878        /*
 879         * Process all entries that have the given prefix and meet
 880         * select_mask condition
 881         */
 882        while(cache != cache_end) {
 883                struct cache_entry *ce = *cache;
 884                const char *name, *slash;
 885                int len, dtype;
 886
 887                if (select_mask && !(ce->ce_flags & select_mask)) {
 888                        cache++;
 889                        continue;
 890                }
 891
 892                if (prefix_len && strncmp(ce->name, prefix, prefix_len))
 893                        break;
 894
 895                name = ce->name + prefix_len;
 896                slash = strchr(name, '/');
 897
 898                /* If it's a directory, try whole directory match first */
 899                if (slash) {
 900                        int processed;
 901
 902                        len = slash - name;
 903                        memcpy(prefix + prefix_len, name, len);
 904
 905                        /*
 906                         * terminate the string (no trailing slash),
 907                         * clear_c_f_dir needs it
 908                         */
 909                        prefix[prefix_len + len] = '\0';
 910                        processed = clear_ce_flags_dir(cache, cache_end - cache,
 911                                                       prefix, prefix_len + len,
 912                                                       prefix + prefix_len,
 913                                                       select_mask, clear_mask,
 914                                                       el);
 915
 916                        /* clear_c_f_dir eats a whole dir already? */
 917                        if (processed) {
 918                                cache += processed;
 919                                continue;
 920                        }
 921
 922                        prefix[prefix_len + len++] = '/';
 923                        cache += clear_ce_flags_1(cache, cache_end - cache,
 924                                                  prefix, prefix_len + len,
 925                                                  select_mask, clear_mask, el);
 926                        continue;
 927                }
 928
 929                /* Non-directory */
 930                dtype = ce_to_dtype(ce);
 931                if (excluded_from_list(ce->name, ce_namelen(ce), name, &dtype, el) > 0)
 932                        ce->ce_flags &= ~clear_mask;
 933                cache++;
 934        }
 935        return nr - (cache_end - cache);
 936}
 937
 938static int clear_ce_flags(struct cache_entry **cache, int nr,
 939                            int select_mask, int clear_mask,
 940                            struct exclude_list *el)
 941{
 942        char prefix[PATH_MAX];
 943        return clear_ce_flags_1(cache, nr,
 944                                prefix, 0,
 945                                select_mask, clear_mask,
 946                                el);
 947}
 948
 949/*
 950 * Set/Clear CE_NEW_SKIP_WORKTREE according to $GIT_DIR/info/sparse-checkout
 951 */
 952static void mark_new_skip_worktree(struct exclude_list *el,
 953                                   struct index_state *the_index,
 954                                   int select_flag, int skip_wt_flag)
 955{
 956        int i;
 957
 958        /*
 959         * 1. Pretend the narrowest worktree: only unmerged entries
 960         * are checked out
 961         */
 962        for (i = 0; i < the_index->cache_nr; i++) {
 963                struct cache_entry *ce = the_index->cache[i];
 964
 965                if (select_flag && !(ce->ce_flags & select_flag))
 966                        continue;
 967
 968                if (!ce_stage(ce))
 969                        ce->ce_flags |= skip_wt_flag;
 970                else
 971                        ce->ce_flags &= ~skip_wt_flag;
 972        }
 973
 974        /*
 975         * 2. Widen worktree according to sparse-checkout file.
 976         * Matched entries will have skip_wt_flag cleared (i.e. "in")
 977         */
 978        clear_ce_flags(the_index->cache, the_index->cache_nr,
 979                       select_flag, skip_wt_flag, el);
 980}
 981
 982static int verify_absent(struct cache_entry *, enum unpack_trees_error_types, struct unpack_trees_options *);
 983/*
 984 * N-way merge "len" trees.  Returns 0 on success, -1 on failure to manipulate the
 985 * resulting index, -2 on failure to reflect the changes to the work tree.
 986 *
 987 * CE_ADDED, CE_UNPACKED and CE_NEW_SKIP_WORKTREE are used internally
 988 */
 989int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
 990{
 991        int i, ret;
 992        static struct cache_entry *dfc;
 993        struct exclude_list el;
 994
 995        if (len > MAX_UNPACK_TREES)
 996                die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES);
 997        memset(&state, 0, sizeof(state));
 998        state.base_dir = "";
 999        state.force = 1;
1000        state.quiet = 1;
1001        state.refresh_cache = 1;
1002
1003        memset(&el, 0, sizeof(el));
1004        if (!core_apply_sparse_checkout || !o->update)
1005                o->skip_sparse_checkout = 1;
1006        if (!o->skip_sparse_checkout) {
1007                if (add_excludes_from_file_to_list(git_path("info/sparse-checkout"), "", 0, NULL, &el, 0) < 0)
1008                        o->skip_sparse_checkout = 1;
1009                else
1010                        o->el = &el;
1011        }
1012
1013        memset(&o->result, 0, sizeof(o->result));
1014        o->result.initialized = 1;
1015        o->result.timestamp.sec = o->src_index->timestamp.sec;
1016        o->result.timestamp.nsec = o->src_index->timestamp.nsec;
1017        o->merge_size = len;
1018        mark_all_ce_unused(o->src_index);
1019
1020        /*
1021         * Sparse checkout loop #1: set NEW_SKIP_WORKTREE on existing entries
1022         */
1023        if (!o->skip_sparse_checkout)
1024                mark_new_skip_worktree(o->el, o->src_index, 0, CE_NEW_SKIP_WORKTREE);
1025
1026        if (!dfc)
1027                dfc = xcalloc(1, cache_entry_size(0));
1028        o->df_conflict_entry = dfc;
1029
1030        if (len) {
1031                const char *prefix = o->prefix ? o->prefix : "";
1032                struct traverse_info info;
1033
1034                setup_traverse_info(&info, prefix);
1035                info.fn = unpack_callback;
1036                info.data = o;
1037                info.show_all_errors = o->show_all_errors;
1038
1039                if (o->prefix) {
1040                        /*
1041                         * Unpack existing index entries that sort before the
1042                         * prefix the tree is spliced into.  Note that o->merge
1043                         * is always true in this case.
1044                         */
1045                        while (1) {
1046                                struct cache_entry *ce = next_cache_entry(o);
1047                                if (!ce)
1048                                        break;
1049                                if (ce_in_traverse_path(ce, &info))
1050                                        break;
1051                                if (unpack_index_entry(ce, o) < 0)
1052                                        goto return_failed;
1053                        }
1054                }
1055
1056                if (traverse_trees(len, t, &info) < 0)
1057                        goto return_failed;
1058        }
1059
1060        /* Any left-over entries in the index? */
1061        if (o->merge) {
1062                while (1) {
1063                        struct cache_entry *ce = next_cache_entry(o);
1064                        if (!ce)
1065                                break;
1066                        if (unpack_index_entry(ce, o) < 0)
1067                                goto return_failed;
1068                }
1069        }
1070        mark_all_ce_unused(o->src_index);
1071
1072        if (o->trivial_merges_only && o->nontrivial_merge) {
1073                ret = unpack_failed(o, "Merge requires file-level merging");
1074                goto done;
1075        }
1076
1077        if (!o->skip_sparse_checkout) {
1078                int empty_worktree = 1;
1079
1080                /*
1081                 * Sparse checkout loop #2: set NEW_SKIP_WORKTREE on entries not in loop #1
1082                 * If the will have NEW_SKIP_WORKTREE, also set CE_SKIP_WORKTREE
1083                 * so apply_sparse_checkout() won't attempt to remove it from worktree
1084                 */
1085                mark_new_skip_worktree(o->el, &o->result, CE_ADDED, CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
1086
1087                for (i = 0; i < o->result.cache_nr; i++) {
1088                        struct cache_entry *ce = o->result.cache[i];
1089
1090                        /*
1091                         * Entries marked with CE_ADDED in merged_entry() do not have
1092                         * verify_absent() check (the check is effectively disabled
1093                         * because CE_NEW_SKIP_WORKTREE is set unconditionally).
1094                         *
1095                         * Do the real check now because we have had
1096                         * correct CE_NEW_SKIP_WORKTREE
1097                         */
1098                        if (ce->ce_flags & CE_ADDED &&
1099                            verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o))
1100                                        return -1;
1101
1102                        if (apply_sparse_checkout(ce, o)) {
1103                                ret = -1;
1104                                goto done;
1105                        }
1106                        if (!ce_skip_worktree(ce))
1107                                empty_worktree = 0;
1108
1109                }
1110                if (o->result.cache_nr && empty_worktree) {
1111                        /* dubious---why should this fail??? */
1112                        ret = unpack_failed(o, "Sparse checkout leaves no entry on working directory");
1113                        goto done;
1114                }
1115        }
1116
1117        o->src_index = NULL;
1118        ret = check_updates(o) ? (-2) : 0;
1119        if (o->dst_index)
1120                *o->dst_index = o->result;
1121
1122done:
1123        free_excludes(&el);
1124        return ret;
1125
1126return_failed:
1127        if (o->show_all_errors)
1128                display_error_msgs(o);
1129        mark_all_ce_unused(o->src_index);
1130        ret = unpack_failed(o, NULL);
1131        goto done;
1132}
1133
1134/* Here come the merge functions */
1135
1136static int reject_merge(struct cache_entry *ce, struct unpack_trees_options *o)
1137{
1138        return add_rejected_path(o, ERROR_WOULD_OVERWRITE, ce->name);
1139}
1140
1141static int same(struct cache_entry *a, struct cache_entry *b)
1142{
1143        if (!!a != !!b)
1144                return 0;
1145        if (!a && !b)
1146                return 1;
1147        if ((a->ce_flags | b->ce_flags) & CE_CONFLICTED)
1148                return 0;
1149        return a->ce_mode == b->ce_mode &&
1150               !hashcmp(a->sha1, b->sha1);
1151}
1152
1153
1154/*
1155 * When a CE gets turned into an unmerged entry, we
1156 * want it to be up-to-date
1157 */
1158static int verify_uptodate_1(struct cache_entry *ce,
1159                                   struct unpack_trees_options *o,
1160                                   enum unpack_trees_error_types error_type)
1161{
1162        struct stat st;
1163
1164        if (o->index_only || (!((ce->ce_flags & CE_VALID) || ce_skip_worktree(ce)) && (o->reset || ce_uptodate(ce))))
1165                return 0;
1166
1167        if (!lstat(ce->name, &st)) {
1168                unsigned changed = ie_match_stat(o->src_index, ce, &st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
1169                if (!changed)
1170                        return 0;
1171                /*
1172                 * NEEDSWORK: the current default policy is to allow
1173                 * submodule to be out of sync wrt the supermodule
1174                 * index.  This needs to be tightened later for
1175                 * submodules that are marked to be automatically
1176                 * checked out.
1177                 */
1178                if (S_ISGITLINK(ce->ce_mode))
1179                        return 0;
1180                errno = 0;
1181        }
1182        if (errno == ENOENT)
1183                return 0;
1184        return o->gently ? -1 :
1185                add_rejected_path(o, error_type, ce->name);
1186}
1187
1188static int verify_uptodate(struct cache_entry *ce,
1189                           struct unpack_trees_options *o)
1190{
1191        if (!o->skip_sparse_checkout && (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
1192                return 0;
1193        return verify_uptodate_1(ce, o, ERROR_NOT_UPTODATE_FILE);
1194}
1195
1196static int verify_uptodate_sparse(struct cache_entry *ce,
1197                                  struct unpack_trees_options *o)
1198{
1199        return verify_uptodate_1(ce, o, ERROR_SPARSE_NOT_UPTODATE_FILE);
1200}
1201
1202static void invalidate_ce_path(struct cache_entry *ce, struct unpack_trees_options *o)
1203{
1204        if (ce)
1205                cache_tree_invalidate_path(o->src_index->cache_tree, ce->name);
1206}
1207
1208/*
1209 * Check that checking out ce->sha1 in subdir ce->name is not
1210 * going to overwrite any working files.
1211 *
1212 * Currently, git does not checkout subprojects during a superproject
1213 * checkout, so it is not going to overwrite anything.
1214 */
1215static int verify_clean_submodule(struct cache_entry *ce,
1216                                      enum unpack_trees_error_types error_type,
1217                                      struct unpack_trees_options *o)
1218{
1219        return 0;
1220}
1221
1222static int verify_clean_subdirectory(struct cache_entry *ce,
1223                                      enum unpack_trees_error_types error_type,
1224                                      struct unpack_trees_options *o)
1225{
1226        /*
1227         * we are about to extract "ce->name"; we would not want to lose
1228         * anything in the existing directory there.
1229         */
1230        int namelen;
1231        int i;
1232        struct dir_struct d;
1233        char *pathbuf;
1234        int cnt = 0;
1235        unsigned char sha1[20];
1236
1237        if (S_ISGITLINK(ce->ce_mode) &&
1238            resolve_gitlink_ref(ce->name, "HEAD", sha1) == 0) {
1239                /* If we are not going to update the submodule, then
1240                 * we don't care.
1241                 */
1242                if (!hashcmp(sha1, ce->sha1))
1243                        return 0;
1244                return verify_clean_submodule(ce, error_type, o);
1245        }
1246
1247        /*
1248         * First let's make sure we do not have a local modification
1249         * in that directory.
1250         */
1251        namelen = strlen(ce->name);
1252        for (i = locate_in_src_index(ce, o);
1253             i < o->src_index->cache_nr;
1254             i++) {
1255                struct cache_entry *ce2 = o->src_index->cache[i];
1256                int len = ce_namelen(ce2);
1257                if (len < namelen ||
1258                    strncmp(ce->name, ce2->name, namelen) ||
1259                    ce2->name[namelen] != '/')
1260                        break;
1261                /*
1262                 * ce2->name is an entry in the subdirectory to be
1263                 * removed.
1264                 */
1265                if (!ce_stage(ce2)) {
1266                        if (verify_uptodate(ce2, o))
1267                                return -1;
1268                        add_entry(o, ce2, CE_REMOVE, 0);
1269                        mark_ce_used(ce2, o);
1270                }
1271                cnt++;
1272        }
1273
1274        /*
1275         * Then we need to make sure that we do not lose a locally
1276         * present file that is not ignored.
1277         */
1278        pathbuf = xmalloc(namelen + 2);
1279        memcpy(pathbuf, ce->name, namelen);
1280        strcpy(pathbuf+namelen, "/");
1281
1282        memset(&d, 0, sizeof(d));
1283        if (o->dir)
1284                d.exclude_per_dir = o->dir->exclude_per_dir;
1285        i = read_directory(&d, pathbuf, namelen+1, NULL);
1286        if (i)
1287                return o->gently ? -1 :
1288                        add_rejected_path(o, ERROR_NOT_UPTODATE_DIR, ce->name);
1289        free(pathbuf);
1290        return cnt;
1291}
1292
1293/*
1294 * This gets called when there was no index entry for the tree entry 'dst',
1295 * but we found a file in the working tree that 'lstat()' said was fine,
1296 * and we're on a case-insensitive filesystem.
1297 *
1298 * See if we can find a case-insensitive match in the index that also
1299 * matches the stat information, and assume it's that other file!
1300 */
1301static int icase_exists(struct unpack_trees_options *o, const char *name, int len, struct stat *st)
1302{
1303        struct cache_entry *src;
1304
1305        src = index_name_exists(o->src_index, name, len, 1);
1306        return src && !ie_match_stat(o->src_index, src, st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
1307}
1308
1309static int check_ok_to_remove(const char *name, int len, int dtype,
1310                              struct cache_entry *ce, struct stat *st,
1311                              enum unpack_trees_error_types error_type,
1312                              struct unpack_trees_options *o)
1313{
1314        struct cache_entry *result;
1315
1316        /*
1317         * It may be that the 'lstat()' succeeded even though
1318         * target 'ce' was absent, because there is an old
1319         * entry that is different only in case..
1320         *
1321         * Ignore that lstat() if it matches.
1322         */
1323        if (ignore_case && icase_exists(o, name, len, st))
1324                return 0;
1325
1326        if (o->dir && excluded(o->dir, name, &dtype))
1327                /*
1328                 * ce->name is explicitly excluded, so it is Ok to
1329                 * overwrite it.
1330                 */
1331                return 0;
1332        if (S_ISDIR(st->st_mode)) {
1333                /*
1334                 * We are checking out path "foo" and
1335                 * found "foo/." in the working tree.
1336                 * This is tricky -- if we have modified
1337                 * files that are in "foo/" we would lose
1338                 * them.
1339                 */
1340                if (verify_clean_subdirectory(ce, error_type, o) < 0)
1341                        return -1;
1342                return 0;
1343        }
1344
1345        /*
1346         * The previous round may already have decided to
1347         * delete this path, which is in a subdirectory that
1348         * is being replaced with a blob.
1349         */
1350        result = index_name_exists(&o->result, name, len, 0);
1351        if (result) {
1352                if (result->ce_flags & CE_REMOVE)
1353                        return 0;
1354        }
1355
1356        return o->gently ? -1 :
1357                add_rejected_path(o, error_type, name);
1358}
1359
1360/*
1361 * We do not want to remove or overwrite a working tree file that
1362 * is not tracked, unless it is ignored.
1363 */
1364static int verify_absent_1(struct cache_entry *ce,
1365                                 enum unpack_trees_error_types error_type,
1366                                 struct unpack_trees_options *o)
1367{
1368        int len;
1369        struct stat st;
1370
1371        if (o->index_only || o->reset || !o->update)
1372                return 0;
1373
1374        len = check_leading_path(ce->name, ce_namelen(ce));
1375        if (!len)
1376                return 0;
1377        else if (len > 0) {
1378                char path[PATH_MAX + 1];
1379                memcpy(path, ce->name, len);
1380                path[len] = 0;
1381                if (lstat(path, &st))
1382                        return error("cannot stat '%s': %s", path,
1383                                        strerror(errno));
1384
1385                return check_ok_to_remove(path, len, DT_UNKNOWN, NULL, &st,
1386                                error_type, o);
1387        } else if (lstat(ce->name, &st)) {
1388                if (errno != ENOENT)
1389                        return error("cannot stat '%s': %s", ce->name,
1390                                     strerror(errno));
1391                return 0;
1392        } else {
1393                return check_ok_to_remove(ce->name, ce_namelen(ce),
1394                                          ce_to_dtype(ce), ce, &st,
1395                                          error_type, o);
1396        }
1397}
1398
1399static int verify_absent(struct cache_entry *ce,
1400                         enum unpack_trees_error_types error_type,
1401                         struct unpack_trees_options *o)
1402{
1403        if (!o->skip_sparse_checkout && (ce->ce_flags & CE_NEW_SKIP_WORKTREE))
1404                return 0;
1405        return verify_absent_1(ce, error_type, o);
1406}
1407
1408static int verify_absent_sparse(struct cache_entry *ce,
1409                         enum unpack_trees_error_types error_type,
1410                         struct unpack_trees_options *o)
1411{
1412        enum unpack_trees_error_types orphaned_error = error_type;
1413        if (orphaned_error == ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN)
1414                orphaned_error = ERROR_WOULD_LOSE_ORPHANED_OVERWRITTEN;
1415
1416        return verify_absent_1(ce, orphaned_error, o);
1417}
1418
1419static int merged_entry(struct cache_entry *merge, struct cache_entry *old,
1420                struct unpack_trees_options *o)
1421{
1422        int update = CE_UPDATE;
1423
1424        if (!old) {
1425                /*
1426                 * New index entries. In sparse checkout, the following
1427                 * verify_absent() will be delayed until after
1428                 * traverse_trees() finishes in unpack_trees(), then:
1429                 *
1430                 *  - CE_NEW_SKIP_WORKTREE will be computed correctly
1431                 *  - verify_absent() be called again, this time with
1432                 *    correct CE_NEW_SKIP_WORKTREE
1433                 *
1434                 * verify_absent() call here does nothing in sparse
1435                 * checkout (i.e. o->skip_sparse_checkout == 0)
1436                 */
1437                update |= CE_ADDED;
1438                merge->ce_flags |= CE_NEW_SKIP_WORKTREE;
1439
1440                if (verify_absent(merge, ERROR_WOULD_LOSE_UNTRACKED_OVERWRITTEN, o))
1441                        return -1;
1442                invalidate_ce_path(merge, o);
1443        } else if (!(old->ce_flags & CE_CONFLICTED)) {
1444                /*
1445                 * See if we can re-use the old CE directly?
1446                 * That way we get the uptodate stat info.
1447                 *
1448                 * This also removes the UPDATE flag on a match; otherwise
1449                 * we will end up overwriting local changes in the work tree.
1450                 */
1451                if (same(old, merge)) {
1452                        copy_cache_entry(merge, old);
1453                        update = 0;
1454                } else {
1455                        if (verify_uptodate(old, o))
1456                                return -1;
1457                        /* Migrate old flags over */
1458                        update |= old->ce_flags & (CE_SKIP_WORKTREE | CE_NEW_SKIP_WORKTREE);
1459                        invalidate_ce_path(old, o);
1460                }
1461        } else {
1462                /*
1463                 * Previously unmerged entry left as an existence
1464                 * marker by read_index_unmerged();
1465                 */
1466                invalidate_ce_path(old, o);
1467        }
1468
1469        add_entry(o, merge, update, CE_STAGEMASK);
1470        return 1;
1471}
1472
1473static int deleted_entry(struct cache_entry *ce, struct cache_entry *old,
1474                struct unpack_trees_options *o)
1475{
1476        /* Did it exist in the index? */
1477        if (!old) {
1478                if (verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_REMOVED, o))
1479                        return -1;
1480                return 0;
1481        }
1482        if (!(old->ce_flags & CE_CONFLICTED) && verify_uptodate(old, o))
1483                return -1;
1484        add_entry(o, ce, CE_REMOVE, 0);
1485        invalidate_ce_path(ce, o);
1486        return 1;
1487}
1488
1489static int keep_entry(struct cache_entry *ce, struct unpack_trees_options *o)
1490{
1491        add_entry(o, ce, 0, 0);
1492        return 1;
1493}
1494
1495#if DBRT_DEBUG
1496static void show_stage_entry(FILE *o,
1497                             const char *label, const struct cache_entry *ce)
1498{
1499        if (!ce)
1500                fprintf(o, "%s (missing)\n", label);
1501        else
1502                fprintf(o, "%s%06o %s %d\t%s\n",
1503                        label,
1504                        ce->ce_mode,
1505                        sha1_to_hex(ce->sha1),
1506                        ce_stage(ce),
1507                        ce->name);
1508}
1509#endif
1510
1511int threeway_merge(struct cache_entry **stages, struct unpack_trees_options *o)
1512{
1513        struct cache_entry *index;
1514        struct cache_entry *head;
1515        struct cache_entry *remote = stages[o->head_idx + 1];
1516        int count;
1517        int head_match = 0;
1518        int remote_match = 0;
1519
1520        int df_conflict_head = 0;
1521        int df_conflict_remote = 0;
1522
1523        int any_anc_missing = 0;
1524        int no_anc_exists = 1;
1525        int i;
1526
1527        for (i = 1; i < o->head_idx; i++) {
1528                if (!stages[i] || stages[i] == o->df_conflict_entry)
1529                        any_anc_missing = 1;
1530                else
1531                        no_anc_exists = 0;
1532        }
1533
1534        index = stages[0];
1535        head = stages[o->head_idx];
1536
1537        if (head == o->df_conflict_entry) {
1538                df_conflict_head = 1;
1539                head = NULL;
1540        }
1541
1542        if (remote == o->df_conflict_entry) {
1543                df_conflict_remote = 1;
1544                remote = NULL;
1545        }
1546
1547        /*
1548         * First, if there's a #16 situation, note that to prevent #13
1549         * and #14.
1550         */
1551        if (!same(remote, head)) {
1552                for (i = 1; i < o->head_idx; i++) {
1553                        if (same(stages[i], head)) {
1554                                head_match = i;
1555                        }
1556                        if (same(stages[i], remote)) {
1557                                remote_match = i;
1558                        }
1559                }
1560        }
1561
1562        /*
1563         * We start with cases where the index is allowed to match
1564         * something other than the head: #14(ALT) and #2ALT, where it
1565         * is permitted to match the result instead.
1566         */
1567        /* #14, #14ALT, #2ALT */
1568        if (remote && !df_conflict_head && head_match && !remote_match) {
1569                if (index && !same(index, remote) && !same(index, head))
1570                        return o->gently ? -1 : reject_merge(index, o);
1571                return merged_entry(remote, index, o);
1572        }
1573        /*
1574         * If we have an entry in the index cache, then we want to
1575         * make sure that it matches head.
1576         */
1577        if (index && !same(index, head))
1578                return o->gently ? -1 : reject_merge(index, o);
1579
1580        if (head) {
1581                /* #5ALT, #15 */
1582                if (same(head, remote))
1583                        return merged_entry(head, index, o);
1584                /* #13, #3ALT */
1585                if (!df_conflict_remote && remote_match && !head_match)
1586                        return merged_entry(head, index, o);
1587        }
1588
1589        /* #1 */
1590        if (!head && !remote && any_anc_missing)
1591                return 0;
1592
1593        /*
1594         * Under the "aggressive" rule, we resolve mostly trivial
1595         * cases that we historically had git-merge-one-file resolve.
1596         */
1597        if (o->aggressive) {
1598                int head_deleted = !head;
1599                int remote_deleted = !remote;
1600                struct cache_entry *ce = NULL;
1601
1602                if (index)
1603                        ce = index;
1604                else if (head)
1605                        ce = head;
1606                else if (remote)
1607                        ce = remote;
1608                else {
1609                        for (i = 1; i < o->head_idx; i++) {
1610                                if (stages[i] && stages[i] != o->df_conflict_entry) {
1611                                        ce = stages[i];
1612                                        break;
1613                                }
1614                        }
1615                }
1616
1617                /*
1618                 * Deleted in both.
1619                 * Deleted in one and unchanged in the other.
1620                 */
1621                if ((head_deleted && remote_deleted) ||
1622                    (head_deleted && remote && remote_match) ||
1623                    (remote_deleted && head && head_match)) {
1624                        if (index)
1625                                return deleted_entry(index, index, o);
1626                        if (ce && !head_deleted) {
1627                                if (verify_absent(ce, ERROR_WOULD_LOSE_UNTRACKED_REMOVED, o))
1628                                        return -1;
1629                        }
1630                        return 0;
1631                }
1632                /*
1633                 * Added in both, identically.
1634                 */
1635                if (no_anc_exists && head && remote && same(head, remote))
1636                        return merged_entry(head, index, o);
1637
1638        }
1639
1640        /* Below are "no merge" cases, which require that the index be
1641         * up-to-date to avoid the files getting overwritten with
1642         * conflict resolution files.
1643         */
1644        if (index) {
1645                if (verify_uptodate(index, o))
1646                        return -1;
1647        }
1648
1649        o->nontrivial_merge = 1;
1650
1651        /* #2, #3, #4, #6, #7, #9, #10, #11. */
1652        count = 0;
1653        if (!head_match || !remote_match) {
1654                for (i = 1; i < o->head_idx; i++) {
1655                        if (stages[i] && stages[i] != o->df_conflict_entry) {
1656                                keep_entry(stages[i], o);
1657                                count++;
1658                                break;
1659                        }
1660                }
1661        }
1662#if DBRT_DEBUG
1663        else {
1664                fprintf(stderr, "read-tree: warning #16 detected\n");
1665                show_stage_entry(stderr, "head   ", stages[head_match]);
1666                show_stage_entry(stderr, "remote ", stages[remote_match]);
1667        }
1668#endif
1669        if (head) { count += keep_entry(head, o); }
1670        if (remote) { count += keep_entry(remote, o); }
1671        return count;
1672}
1673
1674/*
1675 * Two-way merge.
1676 *
1677 * The rule is to "carry forward" what is in the index without losing
1678 * information across a "fast-forward", favoring a successful merge
1679 * over a merge failure when it makes sense.  For details of the
1680 * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
1681 *
1682 */
1683int twoway_merge(struct cache_entry **src, struct unpack_trees_options *o)
1684{
1685        struct cache_entry *current = src[0];
1686        struct cache_entry *oldtree = src[1];
1687        struct cache_entry *newtree = src[2];
1688
1689        if (o->merge_size != 2)
1690                return error("Cannot do a twoway merge of %d trees",
1691                             o->merge_size);
1692
1693        if (oldtree == o->df_conflict_entry)
1694                oldtree = NULL;
1695        if (newtree == o->df_conflict_entry)
1696                newtree = NULL;
1697
1698        if (current) {
1699                if ((!oldtree && !newtree) || /* 4 and 5 */
1700                    (!oldtree && newtree &&
1701                     same(current, newtree)) || /* 6 and 7 */
1702                    (oldtree && newtree &&
1703                     same(oldtree, newtree)) || /* 14 and 15 */
1704                    (oldtree && newtree &&
1705                     !same(oldtree, newtree) && /* 18 and 19 */
1706                     same(current, newtree))) {
1707                        return keep_entry(current, o);
1708                }
1709                else if (oldtree && !newtree && same(current, oldtree)) {
1710                        /* 10 or 11 */
1711                        return deleted_entry(oldtree, current, o);
1712                }
1713                else if (oldtree && newtree &&
1714                         same(current, oldtree) && !same(current, newtree)) {
1715                        /* 20 or 21 */
1716                        return merged_entry(newtree, current, o);
1717                }
1718                else {
1719                        /* all other failures */
1720                        if (oldtree)
1721                                return o->gently ? -1 : reject_merge(oldtree, o);
1722                        if (current)
1723                                return o->gently ? -1 : reject_merge(current, o);
1724                        if (newtree)
1725                                return o->gently ? -1 : reject_merge(newtree, o);
1726                        return -1;
1727                }
1728        }
1729        else if (newtree) {
1730                if (oldtree && !o->initial_checkout) {
1731                        /*
1732                         * deletion of the path was staged;
1733                         */
1734                        if (same(oldtree, newtree))
1735                                return 1;
1736                        return reject_merge(oldtree, o);
1737                }
1738                return merged_entry(newtree, current, o);
1739        }
1740        return deleted_entry(oldtree, current, o);
1741}
1742
1743/*
1744 * Bind merge.
1745 *
1746 * Keep the index entries at stage0, collapse stage1 but make sure
1747 * stage0 does not have anything there.
1748 */
1749int bind_merge(struct cache_entry **src,
1750                struct unpack_trees_options *o)
1751{
1752        struct cache_entry *old = src[0];
1753        struct cache_entry *a = src[1];
1754
1755        if (o->merge_size != 1)
1756                return error("Cannot do a bind merge of %d trees\n",
1757                             o->merge_size);
1758        if (a && old)
1759                return o->gently ? -1 :
1760                        error(ERRORMSG(o, ERROR_BIND_OVERLAP), a->name, old->name);
1761        if (!a)
1762                return keep_entry(old, o);
1763        else
1764                return merged_entry(a, NULL, o);
1765}
1766
1767/*
1768 * One-way merge.
1769 *
1770 * The rule is:
1771 * - take the stat information from stage0, take the data from stage1
1772 */
1773int oneway_merge(struct cache_entry **src, struct unpack_trees_options *o)
1774{
1775        struct cache_entry *old = src[0];
1776        struct cache_entry *a = src[1];
1777
1778        if (o->merge_size != 1)
1779                return error("Cannot do a oneway merge of %d trees",
1780                             o->merge_size);
1781
1782        if (!a || a == o->df_conflict_entry)
1783                return deleted_entry(old, old, o);
1784
1785        if (old && same(old, a)) {
1786                int update = 0;
1787                if (o->reset && !ce_uptodate(old) && !ce_skip_worktree(old)) {
1788                        struct stat st;
1789                        if (lstat(old->name, &st) ||
1790                            ie_match_stat(o->src_index, old, &st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE))
1791                                update |= CE_UPDATE;
1792                }
1793                add_entry(o, old, update, 0);
1794                return 0;
1795        }
1796        return merged_entry(a, old, o);
1797}