cache-tree.con commit Merge branch 'jl/nor-or-nand-and' (d59c12d)
   1#include "cache.h"
   2#include "tree.h"
   3#include "tree-walk.h"
   4#include "cache-tree.h"
   5
   6#ifndef DEBUG
   7#define DEBUG 0
   8#endif
   9
  10struct cache_tree *cache_tree(void)
  11{
  12        struct cache_tree *it = xcalloc(1, sizeof(struct cache_tree));
  13        it->entry_count = -1;
  14        return it;
  15}
  16
  17void cache_tree_free(struct cache_tree **it_p)
  18{
  19        int i;
  20        struct cache_tree *it = *it_p;
  21
  22        if (!it)
  23                return;
  24        for (i = 0; i < it->subtree_nr; i++)
  25                if (it->down[i]) {
  26                        cache_tree_free(&it->down[i]->cache_tree);
  27                        free(it->down[i]);
  28                }
  29        free(it->down);
  30        free(it);
  31        *it_p = NULL;
  32}
  33
  34static int subtree_name_cmp(const char *one, int onelen,
  35                            const char *two, int twolen)
  36{
  37        if (onelen < twolen)
  38                return -1;
  39        if (twolen < onelen)
  40                return 1;
  41        return memcmp(one, two, onelen);
  42}
  43
  44static int subtree_pos(struct cache_tree *it, const char *path, int pathlen)
  45{
  46        struct cache_tree_sub **down = it->down;
  47        int lo, hi;
  48        lo = 0;
  49        hi = it->subtree_nr;
  50        while (lo < hi) {
  51                int mi = (lo + hi) / 2;
  52                struct cache_tree_sub *mdl = down[mi];
  53                int cmp = subtree_name_cmp(path, pathlen,
  54                                           mdl->name, mdl->namelen);
  55                if (!cmp)
  56                        return mi;
  57                if (cmp < 0)
  58                        hi = mi;
  59                else
  60                        lo = mi + 1;
  61        }
  62        return -lo-1;
  63}
  64
  65static struct cache_tree_sub *find_subtree(struct cache_tree *it,
  66                                           const char *path,
  67                                           int pathlen,
  68                                           int create)
  69{
  70        struct cache_tree_sub *down;
  71        int pos = subtree_pos(it, path, pathlen);
  72        if (0 <= pos)
  73                return it->down[pos];
  74        if (!create)
  75                return NULL;
  76
  77        pos = -pos-1;
  78        ALLOC_GROW(it->down, it->subtree_nr + 1, it->subtree_alloc);
  79        it->subtree_nr++;
  80
  81        down = xmalloc(sizeof(*down) + pathlen + 1);
  82        down->cache_tree = NULL;
  83        down->namelen = pathlen;
  84        memcpy(down->name, path, pathlen);
  85        down->name[pathlen] = 0;
  86
  87        if (pos < it->subtree_nr)
  88                memmove(it->down + pos + 1,
  89                        it->down + pos,
  90                        sizeof(down) * (it->subtree_nr - pos - 1));
  91        it->down[pos] = down;
  92        return down;
  93}
  94
  95struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const char *path)
  96{
  97        int pathlen = strlen(path);
  98        return find_subtree(it, path, pathlen, 1);
  99}
 100
 101void cache_tree_invalidate_path(struct cache_tree *it, const char *path)
 102{
 103        /* a/b/c
 104         * ==> invalidate self
 105         * ==> find "a", have it invalidate "b/c"
 106         * a
 107         * ==> invalidate self
 108         * ==> if "a" exists as a subtree, remove it.
 109         */
 110        const char *slash;
 111        int namelen;
 112        struct cache_tree_sub *down;
 113
 114#if DEBUG
 115        fprintf(stderr, "cache-tree invalidate <%s>\n", path);
 116#endif
 117
 118        if (!it)
 119                return;
 120        slash = strchrnul(path, '/');
 121        namelen = slash - path;
 122        it->entry_count = -1;
 123        if (!*slash) {
 124                int pos;
 125                pos = subtree_pos(it, path, namelen);
 126                if (0 <= pos) {
 127                        cache_tree_free(&it->down[pos]->cache_tree);
 128                        free(it->down[pos]);
 129                        /* 0 1 2 3 4 5
 130                         *       ^     ^subtree_nr = 6
 131                         *       pos
 132                         * move 4 and 5 up one place (2 entries)
 133                         * 2 = 6 - 3 - 1 = subtree_nr - pos - 1
 134                         */
 135                        memmove(it->down+pos, it->down+pos+1,
 136                                sizeof(struct cache_tree_sub *) *
 137                                (it->subtree_nr - pos - 1));
 138                        it->subtree_nr--;
 139                }
 140                return;
 141        }
 142        down = find_subtree(it, path, namelen, 0);
 143        if (down)
 144                cache_tree_invalidate_path(down->cache_tree, slash + 1);
 145}
 146
 147static int verify_cache(const struct cache_entry * const *cache,
 148                        int entries, int flags)
 149{
 150        int i, funny;
 151        int silent = flags & WRITE_TREE_SILENT;
 152
 153        /* Verify that the tree is merged */
 154        funny = 0;
 155        for (i = 0; i < entries; i++) {
 156                const struct cache_entry *ce = cache[i];
 157                if (ce_stage(ce)) {
 158                        if (silent)
 159                                return -1;
 160                        if (10 < ++funny) {
 161                                fprintf(stderr, "...\n");
 162                                break;
 163                        }
 164                        fprintf(stderr, "%s: unmerged (%s)\n",
 165                                ce->name, sha1_to_hex(ce->sha1));
 166                }
 167        }
 168        if (funny)
 169                return -1;
 170
 171        /* Also verify that the cache does not have path and path/file
 172         * at the same time.  At this point we know the cache has only
 173         * stage 0 entries.
 174         */
 175        funny = 0;
 176        for (i = 0; i < entries - 1; i++) {
 177                /* path/file always comes after path because of the way
 178                 * the cache is sorted.  Also path can appear only once,
 179                 * which means conflicting one would immediately follow.
 180                 */
 181                const char *this_name = cache[i]->name;
 182                const char *next_name = cache[i+1]->name;
 183                int this_len = strlen(this_name);
 184                if (this_len < strlen(next_name) &&
 185                    strncmp(this_name, next_name, this_len) == 0 &&
 186                    next_name[this_len] == '/') {
 187                        if (10 < ++funny) {
 188                                fprintf(stderr, "...\n");
 189                                break;
 190                        }
 191                        fprintf(stderr, "You have both %s and %s\n",
 192                                this_name, next_name);
 193                }
 194        }
 195        if (funny)
 196                return -1;
 197        return 0;
 198}
 199
 200static void discard_unused_subtrees(struct cache_tree *it)
 201{
 202        struct cache_tree_sub **down = it->down;
 203        int nr = it->subtree_nr;
 204        int dst, src;
 205        for (dst = src = 0; src < nr; src++) {
 206                struct cache_tree_sub *s = down[src];
 207                if (s->used)
 208                        down[dst++] = s;
 209                else {
 210                        cache_tree_free(&s->cache_tree);
 211                        free(s);
 212                        it->subtree_nr--;
 213                }
 214        }
 215}
 216
 217int cache_tree_fully_valid(struct cache_tree *it)
 218{
 219        int i;
 220        if (!it)
 221                return 0;
 222        if (it->entry_count < 0 || !has_sha1_file(it->sha1))
 223                return 0;
 224        for (i = 0; i < it->subtree_nr; i++) {
 225                if (!cache_tree_fully_valid(it->down[i]->cache_tree))
 226                        return 0;
 227        }
 228        return 1;
 229}
 230
 231static int update_one(struct cache_tree *it,
 232                      const struct cache_entry * const *cache,
 233                      int entries,
 234                      const char *base,
 235                      int baselen,
 236                      int *skip_count,
 237                      int flags)
 238{
 239        struct strbuf buffer;
 240        int missing_ok = flags & WRITE_TREE_MISSING_OK;
 241        int dryrun = flags & WRITE_TREE_DRY_RUN;
 242        int to_invalidate = 0;
 243        int i;
 244
 245        *skip_count = 0;
 246
 247        if (0 <= it->entry_count && has_sha1_file(it->sha1))
 248                return it->entry_count;
 249
 250        /*
 251         * We first scan for subtrees and update them; we start by
 252         * marking existing subtrees -- the ones that are unmarked
 253         * should not be in the result.
 254         */
 255        for (i = 0; i < it->subtree_nr; i++)
 256                it->down[i]->used = 0;
 257
 258        /*
 259         * Find the subtrees and update them.
 260         */
 261        i = 0;
 262        while (i < entries) {
 263                const struct cache_entry *ce = cache[i];
 264                struct cache_tree_sub *sub;
 265                const char *path, *slash;
 266                int pathlen, sublen, subcnt, subskip;
 267
 268                path = ce->name;
 269                pathlen = ce_namelen(ce);
 270                if (pathlen <= baselen || memcmp(base, path, baselen))
 271                        break; /* at the end of this level */
 272
 273                slash = strchr(path + baselen, '/');
 274                if (!slash) {
 275                        i++;
 276                        continue;
 277                }
 278                /*
 279                 * a/bbb/c (base = a/, slash = /c)
 280                 * ==>
 281                 * path+baselen = bbb/c, sublen = 3
 282                 */
 283                sublen = slash - (path + baselen);
 284                sub = find_subtree(it, path + baselen, sublen, 1);
 285                if (!sub->cache_tree)
 286                        sub->cache_tree = cache_tree();
 287                subcnt = update_one(sub->cache_tree,
 288                                    cache + i, entries - i,
 289                                    path,
 290                                    baselen + sublen + 1,
 291                                    &subskip,
 292                                    flags);
 293                if (subcnt < 0)
 294                        return subcnt;
 295                i += subcnt;
 296                sub->count = subcnt; /* to be used in the next loop */
 297                *skip_count += subskip;
 298                sub->used = 1;
 299        }
 300
 301        discard_unused_subtrees(it);
 302
 303        /*
 304         * Then write out the tree object for this level.
 305         */
 306        strbuf_init(&buffer, 8192);
 307
 308        i = 0;
 309        while (i < entries) {
 310                const struct cache_entry *ce = cache[i];
 311                struct cache_tree_sub *sub;
 312                const char *path, *slash;
 313                int pathlen, entlen;
 314                const unsigned char *sha1;
 315                unsigned mode;
 316
 317                path = ce->name;
 318                pathlen = ce_namelen(ce);
 319                if (pathlen <= baselen || memcmp(base, path, baselen))
 320                        break; /* at the end of this level */
 321
 322                slash = strchr(path + baselen, '/');
 323                if (slash) {
 324                        entlen = slash - (path + baselen);
 325                        sub = find_subtree(it, path + baselen, entlen, 0);
 326                        if (!sub)
 327                                die("cache-tree.c: '%.*s' in '%s' not found",
 328                                    entlen, path + baselen, path);
 329                        i += sub->count;
 330                        sha1 = sub->cache_tree->sha1;
 331                        mode = S_IFDIR;
 332                        if (sub->cache_tree->entry_count < 0)
 333                                to_invalidate = 1;
 334                }
 335                else {
 336                        sha1 = ce->sha1;
 337                        mode = ce->ce_mode;
 338                        entlen = pathlen - baselen;
 339                        i++;
 340                }
 341                if (mode != S_IFGITLINK && !missing_ok && !has_sha1_file(sha1)) {
 342                        strbuf_release(&buffer);
 343                        return error("invalid object %06o %s for '%.*s'",
 344                                mode, sha1_to_hex(sha1), entlen+baselen, path);
 345                }
 346
 347                /*
 348                 * CE_REMOVE entries are removed before the index is
 349                 * written to disk. Skip them to remain consistent
 350                 * with the future on-disk index.
 351                 */
 352                if (ce->ce_flags & CE_REMOVE) {
 353                        *skip_count = *skip_count + 1;
 354                        continue;
 355                }
 356
 357                /*
 358                 * CE_INTENT_TO_ADD entries exist on on-disk index but
 359                 * they are not part of generated trees. Invalidate up
 360                 * to root to force cache-tree users to read elsewhere.
 361                 */
 362                if (ce->ce_flags & CE_INTENT_TO_ADD) {
 363                        to_invalidate = 1;
 364                        continue;
 365                }
 366
 367                strbuf_grow(&buffer, entlen + 100);
 368                strbuf_addf(&buffer, "%o %.*s%c", mode, entlen, path + baselen, '\0');
 369                strbuf_add(&buffer, sha1, 20);
 370
 371#if DEBUG
 372                fprintf(stderr, "cache-tree update-one %o %.*s\n",
 373                        mode, entlen, path + baselen);
 374#endif
 375        }
 376
 377        if (dryrun)
 378                hash_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1);
 379        else if (write_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1)) {
 380                strbuf_release(&buffer);
 381                return -1;
 382        }
 383
 384        strbuf_release(&buffer);
 385        it->entry_count = to_invalidate ? -1 : i - *skip_count;
 386#if DEBUG
 387        fprintf(stderr, "cache-tree update-one (%d ent, %d subtree) %s\n",
 388                it->entry_count, it->subtree_nr,
 389                sha1_to_hex(it->sha1));
 390#endif
 391        return i;
 392}
 393
 394int cache_tree_update(struct cache_tree *it,
 395                      const struct cache_entry * const *cache,
 396                      int entries,
 397                      int flags)
 398{
 399        int i, skip;
 400        i = verify_cache(cache, entries, flags);
 401        if (i)
 402                return i;
 403        i = update_one(it, cache, entries, "", 0, &skip, flags);
 404        if (i < 0)
 405                return i;
 406        return 0;
 407}
 408
 409static void write_one(struct strbuf *buffer, struct cache_tree *it,
 410                      const char *path, int pathlen)
 411{
 412        int i;
 413
 414        /* One "cache-tree" entry consists of the following:
 415         * path (NUL terminated)
 416         * entry_count, subtree_nr ("%d %d\n")
 417         * tree-sha1 (missing if invalid)
 418         * subtree_nr "cache-tree" entries for subtrees.
 419         */
 420        strbuf_grow(buffer, pathlen + 100);
 421        strbuf_add(buffer, path, pathlen);
 422        strbuf_addf(buffer, "%c%d %d\n", 0, it->entry_count, it->subtree_nr);
 423
 424#if DEBUG
 425        if (0 <= it->entry_count)
 426                fprintf(stderr, "cache-tree <%.*s> (%d ent, %d subtree) %s\n",
 427                        pathlen, path, it->entry_count, it->subtree_nr,
 428                        sha1_to_hex(it->sha1));
 429        else
 430                fprintf(stderr, "cache-tree <%.*s> (%d subtree) invalid\n",
 431                        pathlen, path, it->subtree_nr);
 432#endif
 433
 434        if (0 <= it->entry_count) {
 435                strbuf_add(buffer, it->sha1, 20);
 436        }
 437        for (i = 0; i < it->subtree_nr; i++) {
 438                struct cache_tree_sub *down = it->down[i];
 439                if (i) {
 440                        struct cache_tree_sub *prev = it->down[i-1];
 441                        if (subtree_name_cmp(down->name, down->namelen,
 442                                             prev->name, prev->namelen) <= 0)
 443                                die("fatal - unsorted cache subtree");
 444                }
 445                write_one(buffer, down->cache_tree, down->name, down->namelen);
 446        }
 447}
 448
 449void cache_tree_write(struct strbuf *sb, struct cache_tree *root)
 450{
 451        write_one(sb, root, "", 0);
 452}
 453
 454static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
 455{
 456        const char *buf = *buffer;
 457        unsigned long size = *size_p;
 458        const char *cp;
 459        char *ep;
 460        struct cache_tree *it;
 461        int i, subtree_nr;
 462
 463        it = NULL;
 464        /* skip name, but make sure name exists */
 465        while (size && *buf) {
 466                size--;
 467                buf++;
 468        }
 469        if (!size)
 470                goto free_return;
 471        buf++; size--;
 472        it = cache_tree();
 473
 474        cp = buf;
 475        it->entry_count = strtol(cp, &ep, 10);
 476        if (cp == ep)
 477                goto free_return;
 478        cp = ep;
 479        subtree_nr = strtol(cp, &ep, 10);
 480        if (cp == ep)
 481                goto free_return;
 482        while (size && *buf && *buf != '\n') {
 483                size--;
 484                buf++;
 485        }
 486        if (!size)
 487                goto free_return;
 488        buf++; size--;
 489        if (0 <= it->entry_count) {
 490                if (size < 20)
 491                        goto free_return;
 492                hashcpy(it->sha1, (const unsigned char*)buf);
 493                buf += 20;
 494                size -= 20;
 495        }
 496
 497#if DEBUG
 498        if (0 <= it->entry_count)
 499                fprintf(stderr, "cache-tree <%s> (%d ent, %d subtree) %s\n",
 500                        *buffer, it->entry_count, subtree_nr,
 501                        sha1_to_hex(it->sha1));
 502        else
 503                fprintf(stderr, "cache-tree <%s> (%d subtrees) invalid\n",
 504                        *buffer, subtree_nr);
 505#endif
 506
 507        /*
 508         * Just a heuristic -- we do not add directories that often but
 509         * we do not want to have to extend it immediately when we do,
 510         * hence +2.
 511         */
 512        it->subtree_alloc = subtree_nr + 2;
 513        it->down = xcalloc(it->subtree_alloc, sizeof(struct cache_tree_sub *));
 514        for (i = 0; i < subtree_nr; i++) {
 515                /* read each subtree */
 516                struct cache_tree *sub;
 517                struct cache_tree_sub *subtree;
 518                const char *name = buf;
 519
 520                sub = read_one(&buf, &size);
 521                if (!sub)
 522                        goto free_return;
 523                subtree = cache_tree_sub(it, name);
 524                subtree->cache_tree = sub;
 525        }
 526        if (subtree_nr != it->subtree_nr)
 527                die("cache-tree: internal error");
 528        *buffer = buf;
 529        *size_p = size;
 530        return it;
 531
 532 free_return:
 533        cache_tree_free(&it);
 534        return NULL;
 535}
 536
 537struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
 538{
 539        if (buffer[0])
 540                return NULL; /* not the whole tree */
 541        return read_one(&buffer, &size);
 542}
 543
 544static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)
 545{
 546        if (!it)
 547                return NULL;
 548        while (*path) {
 549                const char *slash;
 550                struct cache_tree_sub *sub;
 551
 552                slash = strchrnul(path, '/');
 553                /*
 554                 * Between path and slash is the name of the subtree
 555                 * to look for.
 556                 */
 557                sub = find_subtree(it, path, slash - path, 0);
 558                if (!sub)
 559                        return NULL;
 560                it = sub->cache_tree;
 561
 562                path = slash;
 563                while (*path == '/')
 564                        path++;
 565        }
 566        return it;
 567}
 568
 569int write_cache_as_tree(unsigned char *sha1, int flags, const char *prefix)
 570{
 571        int entries, was_valid, newfd;
 572        struct lock_file *lock_file;
 573
 574        /*
 575         * We can't free this memory, it becomes part of a linked list
 576         * parsed atexit()
 577         */
 578        lock_file = xcalloc(1, sizeof(struct lock_file));
 579
 580        newfd = hold_locked_index(lock_file, 1);
 581
 582        entries = read_cache();
 583        if (entries < 0)
 584                return WRITE_TREE_UNREADABLE_INDEX;
 585        if (flags & WRITE_TREE_IGNORE_CACHE_TREE)
 586                cache_tree_free(&(active_cache_tree));
 587
 588        if (!active_cache_tree)
 589                active_cache_tree = cache_tree();
 590
 591        was_valid = cache_tree_fully_valid(active_cache_tree);
 592        if (!was_valid) {
 593                if (cache_tree_update(active_cache_tree,
 594                                      (const struct cache_entry * const *)active_cache,
 595                                      active_nr, flags) < 0)
 596                        return WRITE_TREE_UNMERGED_INDEX;
 597                if (0 <= newfd) {
 598                        if (!write_cache(newfd, active_cache, active_nr) &&
 599                            !commit_lock_file(lock_file))
 600                                newfd = -1;
 601                }
 602                /* Not being able to write is fine -- we are only interested
 603                 * in updating the cache-tree part, and if the next caller
 604                 * ends up using the old index with unupdated cache-tree part
 605                 * it misses the work we did here, but that is just a
 606                 * performance penalty and not a big deal.
 607                 */
 608        }
 609
 610        if (prefix) {
 611                struct cache_tree *subtree =
 612                        cache_tree_find(active_cache_tree, prefix);
 613                if (!subtree)
 614                        return WRITE_TREE_PREFIX_ERROR;
 615                hashcpy(sha1, subtree->sha1);
 616        }
 617        else
 618                hashcpy(sha1, active_cache_tree->sha1);
 619
 620        if (0 <= newfd)
 621                rollback_lock_file(lock_file);
 622
 623        return 0;
 624}
 625
 626static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
 627{
 628        struct tree_desc desc;
 629        struct name_entry entry;
 630        int cnt;
 631
 632        hashcpy(it->sha1, tree->object.sha1);
 633        init_tree_desc(&desc, tree->buffer, tree->size);
 634        cnt = 0;
 635        while (tree_entry(&desc, &entry)) {
 636                if (!S_ISDIR(entry.mode))
 637                        cnt++;
 638                else {
 639                        struct cache_tree_sub *sub;
 640                        struct tree *subtree = lookup_tree(entry.sha1);
 641                        if (!subtree->object.parsed)
 642                                parse_tree(subtree);
 643                        sub = cache_tree_sub(it, entry.path);
 644                        sub->cache_tree = cache_tree();
 645                        prime_cache_tree_rec(sub->cache_tree, subtree);
 646                        cnt += sub->cache_tree->entry_count;
 647                }
 648        }
 649        it->entry_count = cnt;
 650}
 651
 652void prime_cache_tree(struct cache_tree **it, struct tree *tree)
 653{
 654        cache_tree_free(it);
 655        *it = cache_tree();
 656        prime_cache_tree_rec(*it, tree);
 657}
 658
 659/*
 660 * find the cache_tree that corresponds to the current level without
 661 * exploding the full path into textual form.  The root of the
 662 * cache tree is given as "root", and our current level is "info".
 663 * (1) When at root level, info->prev is NULL, so it is "root" itself.
 664 * (2) Otherwise, find the cache_tree that corresponds to one level
 665 *     above us, and find ourselves in there.
 666 */
 667static struct cache_tree *find_cache_tree_from_traversal(struct cache_tree *root,
 668                                                         struct traverse_info *info)
 669{
 670        struct cache_tree *our_parent;
 671
 672        if (!info->prev)
 673                return root;
 674        our_parent = find_cache_tree_from_traversal(root, info->prev);
 675        return cache_tree_find(our_parent, info->name.path);
 676}
 677
 678int cache_tree_matches_traversal(struct cache_tree *root,
 679                                 struct name_entry *ent,
 680                                 struct traverse_info *info)
 681{
 682        struct cache_tree *it;
 683
 684        it = find_cache_tree_from_traversal(root, info);
 685        it = cache_tree_find(it, ent->path);
 686        if (it && it->entry_count > 0 && !hashcmp(ent->sha1, it->sha1))
 687                return it->entry_count;
 688        return 0;
 689}
 690
 691int update_main_cache_tree(int flags)
 692{
 693        if (!the_index.cache_tree)
 694                the_index.cache_tree = cache_tree();
 695        return cache_tree_update(the_index.cache_tree,
 696                                 (const struct cache_entry * const *)the_index.cache,
 697                                 the_index.cache_nr, flags);
 698}