tree-walk.con commit Merge branch 'jn/merge-renormalize' (8aed4a5)
   1#include "cache.h"
   2#include "tree-walk.h"
   3#include "unpack-trees.h"
   4#include "tree.h"
   5
   6static const char *get_mode(const char *str, unsigned int *modep)
   7{
   8        unsigned char c;
   9        unsigned int mode = 0;
  10
  11        if (*str == ' ')
  12                return NULL;
  13
  14        while ((c = *str++) != ' ') {
  15                if (c < '0' || c > '7')
  16                        return NULL;
  17                mode = (mode << 3) + (c - '0');
  18        }
  19        *modep = mode;
  20        return str;
  21}
  22
  23static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
  24{
  25        const char *path;
  26        unsigned int mode, len;
  27
  28        if (size < 24 || buf[size - 21])
  29                die("corrupt tree file");
  30
  31        path = get_mode(buf, &mode);
  32        if (!path || !*path)
  33                die("corrupt tree file");
  34        len = strlen(path) + 1;
  35
  36        /* Initialize the descriptor entry */
  37        desc->entry.path = path;
  38        desc->entry.mode = mode;
  39        desc->entry.sha1 = (const unsigned char *)(path + len);
  40}
  41
  42void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
  43{
  44        desc->buffer = buffer;
  45        desc->size = size;
  46        if (size)
  47                decode_tree_entry(desc, buffer, size);
  48}
  49
  50void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
  51{
  52        unsigned long size = 0;
  53        void *buf = NULL;
  54
  55        if (sha1) {
  56                buf = read_object_with_reference(sha1, tree_type, &size, NULL);
  57                if (!buf)
  58                        die("unable to read tree %s", sha1_to_hex(sha1));
  59        }
  60        init_tree_desc(desc, buf, size);
  61        return buf;
  62}
  63
  64static void entry_clear(struct name_entry *a)
  65{
  66        memset(a, 0, sizeof(*a));
  67}
  68
  69static void entry_extract(struct tree_desc *t, struct name_entry *a)
  70{
  71        *a = t->entry;
  72}
  73
  74void update_tree_entry(struct tree_desc *desc)
  75{
  76        const void *buf = desc->buffer;
  77        const unsigned char *end = desc->entry.sha1 + 20;
  78        unsigned long size = desc->size;
  79        unsigned long len = end - (const unsigned char *)buf;
  80
  81        if (size < len)
  82                die("corrupt tree file");
  83        buf = end;
  84        size -= len;
  85        desc->buffer = buf;
  86        desc->size = size;
  87        if (size)
  88                decode_tree_entry(desc, buf, size);
  89}
  90
  91int tree_entry(struct tree_desc *desc, struct name_entry *entry)
  92{
  93        if (!desc->size)
  94                return 0;
  95
  96        *entry = desc->entry;
  97        update_tree_entry(desc);
  98        return 1;
  99}
 100
 101void setup_traverse_info(struct traverse_info *info, const char *base)
 102{
 103        int pathlen = strlen(base);
 104        static struct traverse_info dummy;
 105
 106        memset(info, 0, sizeof(*info));
 107        if (pathlen && base[pathlen-1] == '/')
 108                pathlen--;
 109        info->pathlen = pathlen ? pathlen + 1 : 0;
 110        info->name.path = base;
 111        info->name.sha1 = (void *)(base + pathlen + 1);
 112        if (pathlen)
 113                info->prev = &dummy;
 114}
 115
 116char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
 117{
 118        int len = tree_entry_len(n->path, n->sha1);
 119        int pathlen = info->pathlen;
 120
 121        path[pathlen + len] = 0;
 122        for (;;) {
 123                memcpy(path + pathlen, n->path, len);
 124                if (!pathlen)
 125                        break;
 126                path[--pathlen] = '/';
 127                n = &info->name;
 128                len = tree_entry_len(n->path, n->sha1);
 129                info = info->prev;
 130                pathlen -= len;
 131        }
 132        return path;
 133}
 134
 135struct tree_desc_skip {
 136        struct tree_desc_skip *prev;
 137        const void *ptr;
 138};
 139
 140struct tree_desc_x {
 141        struct tree_desc d;
 142        struct tree_desc_skip *skip;
 143};
 144
 145static int name_compare(const char *a, int a_len,
 146                        const char *b, int b_len)
 147{
 148        int len = (a_len < b_len) ? a_len : b_len;
 149        int cmp = memcmp(a, b, len);
 150        if (cmp)
 151                return cmp;
 152        return (a_len - b_len);
 153}
 154
 155static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
 156{
 157        /*
 158         * The caller wants to pick *a* from a tree or nothing.
 159         * We are looking at *b* in a tree.
 160         *
 161         * (0) If a and b are the same name, we are trivially happy.
 162         *
 163         * There are three possibilities where *a* could be hiding
 164         * behind *b*.
 165         *
 166         * (1) *a* == "t",   *b* == "ab"  i.e. *b* sorts earlier than *a* no
 167         *                                matter what.
 168         * (2) *a* == "t",   *b* == "t-2" and "t" is a subtree in the tree;
 169         * (3) *a* == "t-2", *b* == "t"   and "t-2" is a blob in the tree.
 170         *
 171         * Otherwise we know *a* won't appear in the tree without
 172         * scanning further.
 173         */
 174
 175        int cmp = name_compare(a, a_len, b, b_len);
 176
 177        /* Most common case first -- reading sync'd trees */
 178        if (!cmp)
 179                return cmp;
 180
 181        if (0 < cmp) {
 182                /* a comes after b; it does not matter if it is case (3)
 183                if (b_len < a_len && !memcmp(a, b, b_len) && a[b_len] < '/')
 184                        return 1;
 185                */
 186                return 1; /* keep looking */
 187        }
 188
 189        /* b comes after a; are we looking at case (2)? */
 190        if (a_len < b_len && !memcmp(a, b, a_len) && b[a_len] < '/')
 191                return 1; /* keep looking */
 192
 193        return -1; /* a cannot appear in the tree */
 194}
 195
 196/*
 197 * From the extended tree_desc, extract the first name entry, while
 198 * paying attention to the candidate "first" name.  Most importantly,
 199 * when looking for an entry, if there are entries that sorts earlier
 200 * in the tree object representation than that name, skip them and
 201 * process the named entry first.  We will remember that we haven't
 202 * processed the first entry yet, and in the later call skip the
 203 * entry we processed early when update_extended_entry() is called.
 204 *
 205 * E.g. if the underlying tree object has these entries:
 206 *
 207 *    blob    "t-1"
 208 *    blob    "t-2"
 209 *    tree    "t"
 210 *    blob    "t=1"
 211 *
 212 * and the "first" asks for "t", remember that we still need to
 213 * process "t-1" and "t-2" but extract "t".  After processing the
 214 * entry "t" from this call, the caller will let us know by calling
 215 * update_extended_entry() that we can remember "t" has been processed
 216 * already.
 217 */
 218
 219static void extended_entry_extract(struct tree_desc_x *t,
 220                                   struct name_entry *a,
 221                                   const char *first,
 222                                   int first_len)
 223{
 224        const char *path;
 225        int len;
 226        struct tree_desc probe;
 227        struct tree_desc_skip *skip;
 228
 229        /*
 230         * Extract the first entry from the tree_desc, but skip the
 231         * ones that we already returned in earlier rounds.
 232         */
 233        while (1) {
 234                if (!t->d.size) {
 235                        entry_clear(a);
 236                        break; /* not found */
 237                }
 238                entry_extract(&t->d, a);
 239                for (skip = t->skip; skip; skip = skip->prev)
 240                        if (a->path == skip->ptr)
 241                                break; /* found */
 242                if (!skip)
 243                        break;
 244                /* We have processed this entry already. */
 245                update_tree_entry(&t->d);
 246        }
 247
 248        if (!first || !a->path)
 249                return;
 250
 251        /*
 252         * The caller wants "first" from this tree, or nothing.
 253         */
 254        path = a->path;
 255        len = tree_entry_len(a->path, a->sha1);
 256        switch (check_entry_match(first, first_len, path, len)) {
 257        case -1:
 258                entry_clear(a);
 259        case 0:
 260                return;
 261        default:
 262                break;
 263        }
 264
 265        /*
 266         * We need to look-ahead -- we suspect that a subtree whose
 267         * name is "first" may be hiding behind the current entry "path".
 268         */
 269        probe = t->d;
 270        while (probe.size) {
 271                entry_extract(&probe, a);
 272                path = a->path;
 273                len = tree_entry_len(a->path, a->sha1);
 274                switch (check_entry_match(first, first_len, path, len)) {
 275                case -1:
 276                        entry_clear(a);
 277                case 0:
 278                        return;
 279                default:
 280                        update_tree_entry(&probe);
 281                        break;
 282                }
 283                /* keep looking */
 284        }
 285        entry_clear(a);
 286}
 287
 288static void update_extended_entry(struct tree_desc_x *t, struct name_entry *a)
 289{
 290        if (t->d.entry.path == a->path) {
 291                update_tree_entry(&t->d);
 292        } else {
 293                /* we have returned this entry early */
 294                struct tree_desc_skip *skip = xmalloc(sizeof(*skip));
 295                skip->ptr = a->path;
 296                skip->prev = t->skip;
 297                t->skip = skip;
 298        }
 299}
 300
 301static void free_extended_entry(struct tree_desc_x *t)
 302{
 303        struct tree_desc_skip *p, *s;
 304
 305        for (s = t->skip; s; s = p) {
 306                p = s->prev;
 307                free(s);
 308        }
 309}
 310
 311int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 312{
 313        int ret = 0;
 314        int error = 0;
 315        struct name_entry *entry = xmalloc(n*sizeof(*entry));
 316        int i;
 317        struct tree_desc_x *tx = xcalloc(n, sizeof(*tx));
 318
 319        for (i = 0; i < n; i++)
 320                tx[i].d = t[i];
 321
 322        for (;;) {
 323                unsigned long mask, dirmask;
 324                const char *first = NULL;
 325                int first_len = 0;
 326                struct name_entry *e;
 327                int len;
 328
 329                for (i = 0; i < n; i++) {
 330                        e = entry + i;
 331                        extended_entry_extract(tx + i, e, NULL, 0);
 332                }
 333
 334                /*
 335                 * A tree may have "t-2" at the current location even
 336                 * though it may have "t" that is a subtree behind it,
 337                 * and another tree may return "t".  We want to grab
 338                 * all "t" from all trees to match in such a case.
 339                 */
 340                for (i = 0; i < n; i++) {
 341                        e = entry + i;
 342                        if (!e->path)
 343                                continue;
 344                        len = tree_entry_len(e->path, e->sha1);
 345                        if (!first) {
 346                                first = e->path;
 347                                first_len = len;
 348                                continue;
 349                        }
 350                        if (name_compare(e->path, len, first, first_len) < 0) {
 351                                first = e->path;
 352                                first_len = len;
 353                        }
 354                }
 355
 356                if (first) {
 357                        for (i = 0; i < n; i++) {
 358                                e = entry + i;
 359                                extended_entry_extract(tx + i, e, first, first_len);
 360                                /* Cull the ones that are not the earliest */
 361                                if (!e->path)
 362                                        continue;
 363                                len = tree_entry_len(e->path, e->sha1);
 364                                if (name_compare(e->path, len, first, first_len))
 365                                        entry_clear(e);
 366                        }
 367                }
 368
 369                /* Now we have in entry[i] the earliest name from the trees */
 370                mask = 0;
 371                dirmask = 0;
 372                for (i = 0; i < n; i++) {
 373                        if (!entry[i].path)
 374                                continue;
 375                        mask |= 1ul << i;
 376                        if (S_ISDIR(entry[i].mode))
 377                                dirmask |= 1ul << i;
 378                }
 379                if (!mask)
 380                        break;
 381                ret = info->fn(n, mask, dirmask, entry, info);
 382                if (ret < 0) {
 383                        error = ret;
 384                        if (!info->show_all_errors)
 385                                break;
 386                }
 387                mask &= ret;
 388                ret = 0;
 389                for (i = 0; i < n; i++)
 390                        if (mask & (1ul << i))
 391                                update_extended_entry(tx + i, entry + i);
 392        }
 393        free(entry);
 394        for (i = 0; i < n; i++)
 395                free_extended_entry(tx + i);
 396        free(tx);
 397        return error;
 398}
 399
 400static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
 401{
 402        int namelen = strlen(name);
 403        while (t->size) {
 404                const char *entry;
 405                const unsigned char *sha1;
 406                int entrylen, cmp;
 407
 408                sha1 = tree_entry_extract(t, &entry, mode);
 409                update_tree_entry(t);
 410                entrylen = tree_entry_len(entry, sha1);
 411                if (entrylen > namelen)
 412                        continue;
 413                cmp = memcmp(name, entry, entrylen);
 414                if (cmp > 0)
 415                        continue;
 416                if (cmp < 0)
 417                        break;
 418                if (entrylen == namelen) {
 419                        hashcpy(result, sha1);
 420                        return 0;
 421                }
 422                if (name[entrylen] != '/')
 423                        continue;
 424                if (!S_ISDIR(*mode))
 425                        break;
 426                if (++entrylen == namelen) {
 427                        hashcpy(result, sha1);
 428                        return 0;
 429                }
 430                return get_tree_entry(sha1, name + entrylen, result, mode);
 431        }
 432        return -1;
 433}
 434
 435int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
 436{
 437        int retval;
 438        void *tree;
 439        unsigned long size;
 440        struct tree_desc t;
 441        unsigned char root[20];
 442
 443        tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
 444        if (!tree)
 445                return -1;
 446
 447        if (name[0] == '\0') {
 448                hashcpy(sha1, root);
 449                free(tree);
 450                return 0;
 451        }
 452
 453        init_tree_desc(&t, tree, size);
 454        retval = find_tree_entry(&t, name, sha1, mode);
 455        free(tree);
 456        return retval;
 457}