#include "internal.h"

#define hash(k) ((int32)k.ino ^ (int32)k.dev)
#define equal(k1, k2) (k1.ino == k2.ino && k1.dev == k2.dev)

static int
morehistory(fs·History *h, int n)
{
    SET_GROW(h, struct Key, n, hash, base·Memory, nil);
}

static int
addentry(fs·History *h, struct Key key, int *err)
{
    SET_PUT(h, key, hash, equal, morehistory, err);
}

static void
forget(fs·History *h)
{
    if (!h)
        return;

    SET_RESET(h);
}

void
fs·walk(fs·Walker *fs)
{
    char *e, *b;
    sys·Info cwd;
    fs·History *h;
    fs·DirEntry *f;
    fs·Directory dir;
    int new, fd, ofd, flags;

    flags = 0;
    if(fs->flags & fs·nolinks)
        flags |= sys·AtNoFollowLink;

    /* get info for base relative to current fd */
    if(sys·infoat(fs->fd, fs->base, flags, 0, &cwd)){
        if(fs->flags & fs·verbose)
            errorf("stat: %s", fs->path);
        return;
    }

    /* if we hit a file, finish! */
    if(!sys·InfoIsFile(cwd.mode)) {
        fs->func(fs->data, fs->base, fs->path, &cwd);
        return;
    }

    /* have we been here before? (cycle detection) */
    /* if not, add to our path history */
    if(!(fs->flags & fs·nolinks)){
        addentry(fs->hist,
            (struct Key){
                .dev = ((uint64)cwd.device.major<<32)|((uint64)cwd.device.minor),
                .ino = cwd.inode
            }, &new
        );
        if (!new)
            return;
    }
    /*
     * operate on directory first if preorder traversal 
     * truncate recursion if callback returns an error code
     */
    if(fs->flags & fs·preorder){
        if(fs->func(fs->data, fs->base, fs->path, &cwd))
            return;
    }

    /* open directory */
    if(!fs->max || fs->lev + 1 < fs->max){
        if(sys·openat(fs->fd, fs->base, sys·ORead|sys·OCloseExec|sys·ODirectory, 0, &fd))
            errorf("open %s:", fs->path);

        if(fs·openfd(fd, &dir)){
            if(fs->flags & fs·verbose)
                errorf("fdopendir: %s", fs->path);
            return;
        }

        ofd = fs->fd, fs->fd = fd;

        /* traverse children */
        e = fs->end, b = fs->base;
        if (fs->end[-1] != '/')
            *fs->end++ = '/';

        fs->base = fs->end;
        while(!fs·read(&dir,&f)){
            if(f->name[0] == '.')
                if(f->name[1] == 0 ||                       /* . */
                   (f->name[1] == '.' && f->name[2] == 0)) /* .. */
                    continue;

            fs->end = str·ncopy(fs->base, arrend(fs->path) - fs->base, f->name);

            fs->lev++;
            fs·walk(fs);
            fs->lev--;
        }
        *e      = 0;
        fs->fd  = ofd;
        fs->end = e, fs->base = b;
        fs·close(&dir);
    }

    /* operate on directory if postorder (default) traversal */
    if(!(fs->flags & fs·preorder))
        fs->func(fs->data, fs->base, fs->path, &cwd);

    if(!fs->lev)
        forget(fs->hist);
}