#include "cache.h"
#include "tree-walk.h"
#include "tree.h"

static const char *get_mode(const char *str, unsigned int *modep)
{
        unsigned char c;
        unsigned int mode = 0;

        if (*str == ' ')
                return NULL;

        while ((c = *str++) != ' ') {
                if (c < '0' || c > '7')
                        return NULL;
                mode = (mode << 3) + (c - '0');
        }
        *modep = mode;
        return str;
}

static void decode_tree_entry(struct tree_desc *desc, const char *buf, unsigned long size)
{
        const char *path;
        unsigned int mode, len;

        if (size < 24 || buf[size - 21])
                die("corrupt tree file");

        path = get_mode(buf, &mode);
        if (!path || !*path)
                die("corrupt tree file");
        len = strlen(path) + 1;

        /* Initialize the descriptor entry */
        desc->entry.path = path;
        desc->entry.mode = mode;
        desc->entry.sha1 = (const unsigned char *)(path + len);
}

void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)
{
        desc->buffer = buffer;
        desc->size = size;
        if (size)
                decode_tree_entry(desc, buffer, size);
}

void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
{
        unsigned long size = 0;
        void *buf = NULL;

        if (sha1) {
                buf = read_object_with_reference(sha1, tree_type, &size, NULL);
                if (!buf)
                        die("unable to read tree %s", sha1_to_hex(sha1));
        }
        init_tree_desc(desc, buf, size);
        return buf;
}

static int entry_compare(struct name_entry *a, struct name_entry *b)
{
        return base_name_compare(
                        a->path, tree_entry_len(a->path, a->sha1), a->mode,
                        b->path, tree_entry_len(b->path, b->sha1), b->mode);
}

static void entry_clear(struct name_entry *a)
{
        memset(a, 0, sizeof(*a));
}

static void entry_extract(struct tree_desc *t, struct name_entry *a)
{
        *a = t->entry;
}

void update_tree_entry(struct tree_desc *desc)
{
        const void *buf = desc->buffer;
        const unsigned char *end = desc->entry.sha1 + 20;
        unsigned long size = desc->size;
        unsigned long len = end - (const unsigned char *)buf;

        if (size < len)
                die("corrupt tree file");
        buf = end;
        size -= len;
        desc->buffer = buf;
        desc->size = size;
        if (size)
                decode_tree_entry(desc, buf, size);
}

int tree_entry(struct tree_desc *desc, struct name_entry *entry)
{
        if (!desc->size)
                return 0;

        *entry = desc->entry;
        update_tree_entry(desc);
        return 1;
}

void setup_traverse_info(struct traverse_info *info, const char *base)
{
        int pathlen = strlen(base);

        memset(info, 0, sizeof(*info));
        if (pathlen && base[pathlen-1] == '/')
                pathlen--;
        info->pathlen = pathlen ? pathlen + 1 : 0;
        info->name.path = base;
        info->name.sha1 = (void *)(base + pathlen + 1);
}

char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
{
        int len = tree_entry_len(n->path, n->sha1);
        int pathlen = info->pathlen;

        path[pathlen + len] = 0;
        for (;;) {
                memcpy(path + pathlen, n->path, len);
                if (!pathlen)
                        break;
                path[--pathlen] = '/';
                n = &info->name;
                len = tree_entry_len(n->path, n->sha1);
                info = info->prev;
                pathlen -= len;
        }
        return path;
}

int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
{
        int ret = 0;
        struct name_entry *entry = xmalloc(n*sizeof(*entry));

        for (;;) {
                unsigned long mask = 0;
                int i, last;

                last = -1;
                for (i = 0; i < n; i++) {
                        if (!t[i].size)
                                continue;
                        entry_extract(t+i, entry+i);
                        if (last >= 0) {
                                int cmp = entry_compare(entry+i, entry+last);

                                /*
                                 * Is the new name bigger than the old one?
                                 * Ignore it
                                 */
                                if (cmp > 0)
                                        continue;
                                /*
                                 * Is the new name smaller than the old one?
                                 * Ignore all old ones
                                 */
                                if (cmp < 0)
                                        mask = 0;
                        }
                        mask |= 1ul << i;
                        last = i;
                }
                if (!mask)
                        break;

                /*
                 * Clear all the unused name-entries.
                 */
                for (i = 0; i < n; i++) {
                        if (mask & (1ul << i))
                                continue;
                        entry_clear(entry + i);
                }
                ret = info->fn(n, mask, entry, info);
                if (ret < 0)
                        break;
                if (ret)
                        mask &= ret;
                ret = 0;
                for (i = 0; i < n; i++) {
                        if (mask & (1ul << i))
                                update_tree_entry(t + i);
                }
        }
        free(entry);
        return ret;
}

static int find_tree_entry(struct tree_desc *t, const char *name, unsigned char *result, unsigned *mode)
{
        int namelen = strlen(name);
        while (t->size) {
                const char *entry;
                const unsigned char *sha1;
                int entrylen, cmp;

                sha1 = tree_entry_extract(t, &entry, mode);
                update_tree_entry(t);
                entrylen = tree_entry_len(entry, sha1);
                if (entrylen > namelen)
                        continue;
                cmp = memcmp(name, entry, entrylen);
                if (cmp > 0)
                        continue;
                if (cmp < 0)
                        break;
                if (entrylen == namelen) {
                        hashcpy(result, sha1);
                        return 0;
                }
                if (name[entrylen] != '/')
                        continue;
                if (!S_ISDIR(*mode))
                        break;
                if (++entrylen == namelen) {
                        hashcpy(result, sha1);
                        return 0;
                }
                return get_tree_entry(sha1, name + entrylen, result, mode);
        }
        return -1;
}

int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned char *sha1, unsigned *mode)
{
        int retval;
        void *tree;
        unsigned long size;
        struct tree_desc t;
        unsigned char root[20];

        tree = read_object_with_reference(tree_sha1, tree_type, &size, root);
        if (!tree)
                return -1;

        if (name[0] == '\0') {
                hashcpy(sha1, root);
                return 0;
        }

        init_tree_desc(&t, tree, size);
        retval = find_tree_entry(&t, name, sha1, mode);
        free(tree);
        return retval;
}