#include "resolve.h"

#include <stdint.h>
#include <stdalign.h>
#include <string.h>

#include "store.h"

typedef enum : uint8_t {
    UNVISITED = 0,
    VISITING,
    VISITED,
} visit_state;

typedef struct closure_node closure_node;
struct closure_node {
    const pkg    *p;
    closure_node *next;
};

static bool closure_contains(const closure_node *head, const pkg *p) {
    for (const closure_node *n = head; n != nullptr; n = n->next) {
        if (n->p == p) return true;
    }
    return false;
}

static bool closure_collect(
        arena         *a,
        const pkg     *p,
        closure_node **head,
        size_t        *count
    ) {
    if (closure_contains(*head, p)) return true;

    closure_node *node = arena_alloc(a, sizeof(closure_node), alignof(closure_node));
    if (node == nullptr) return false;
    node->p    = p;
    node->next = *head;
    *head      = node;
    (*count)++;

    for (size_t i = 0; i < p->deps.len; i++) {
        if (!closure_collect(a, p->deps.data[i], head, count)) return false;
    }
    return true;
}

static size_t closure_index(
    const pkg *const *closure,
    size_t            n,
    const pkg        *target)
{
    for (size_t i = 0; i < n; i++) {
        if (closure[i] == target) return i;
    }
    return SIZE_MAX;
}

static resolve_error visit(
    arena             *a,
    const pkg *const  *closure,
    size_t             n_closure,
    size_t             idx,
    visit_state       *state,
    resolved          *out,
    size_t            *out_len)
{
    switch (state[idx]) {
        case VISITED:  return RESOLVE_OK_VAL;
        case VISITING: return (resolve_error){
            .kind = RESOLVE_E_CYCLE,
            .pkg_name = closure[idx]->name,
        };
        case UNVISITED: break;
    }

    state[idx] = VISITING;
    const pkg *p = closure[idx];

    for (size_t i = 0; i < p->deps.len; i++) {
        size_t dep_idx = closure_index(closure, n_closure, p->deps.data[i]);
        resolve_error err = visit(a, closure, n_closure, dep_idx, state, out, out_len);
        if (err.kind != RESOLVE_OK) return err;
    }

    out[*out_len].def        = p;
    out[*out_len].store_path = store_path_compute(a, p, out, *out_len);
    (*out_len)++;
    state[idx] = VISITED;
    return RESOLVE_OK_VAL;
}

/**
 * resolve() - Compute the build closure and topologically sort it.
 * @a: Arena holding the resulting closure, visit-state, and resolved arrays.
 * @cfg: System configuration providing the package roots.
 * @out: Filled with topologically-sorted &resolved entries on success.
 *
 * Roots are everything the config references directly: @cfg->pkgs entries,
 * @cfg->boot.kernel, and each @cfg->users[i].shell. Transitive deps are
 * auto-discovered into the closure. The output is in post-order so
 * &realize can iterate it directly.
 *
 * Return: RESOLVE_OK_VAL on success, a tagged error otherwise.
 */
resolve_error resolve(
    arena              *a,
    const system_cfg   *cfg,
    resolved_list      *out)
{
    for (size_t i = 0; i < cfg->pkgs.len; i++) {
        for (size_t j = i + 1; j < cfg->pkgs.len; j++) {
            if (strcmp(cfg->pkgs.data[i]->name, cfg->pkgs.data[j]->name) == 0) {
                return (resolve_error){
                    .kind = RESOLVE_E_DUPLICATE_NAME,
                    .pkg_name = cfg->pkgs.data[i]->name,
                };
            }
        }
    }

    closure_node *head = nullptr;
    size_t n_closure = 0;
    for (size_t i = 0; i < cfg->pkgs.len; i++) {
        if (!closure_collect(a, cfg->pkgs.data[i], &head, &n_closure)) {
            return (resolve_error){ .kind = RESOLVE_E_OOM };
        }
    }
    if (cfg->boot.kernel != nullptr) {
        if (!closure_collect(a, cfg->boot.kernel, &head, &n_closure)) {
            return (resolve_error){ .kind = RESOLVE_E_OOM };
        }
    }
    for (size_t i = 0; i < cfg->users.len; i++) {
        const pkg *shell = cfg->users.data[i].shell;
        if (shell != nullptr) {
            if (!closure_collect(a, shell, &head, &n_closure)) {
                return (resolve_error){ .kind = RESOLVE_E_OOM };
            }
        }
    }

    const pkg **closure = arena_alloc(a, n_closure * sizeof(const pkg *),
                                       alignof(const pkg *));
    visit_state *state  = arena_alloc(a, n_closure * sizeof(visit_state),
                                       alignof(visit_state));
    resolved    *res    = arena_alloc(a, n_closure * sizeof(resolved),
                                       alignof(resolved));
    if (closure == nullptr || state == nullptr || res == nullptr) {
        return (resolve_error){ .kind = RESOLVE_E_OOM };
    }

    {
        size_t i = 0;
        for (closure_node *n = head; n != nullptr; n = n->next) {
            closure[i++] = n->p;
        }
    }

    size_t res_len = 0;
    for (size_t i = 0; i < n_closure; i++) {
        resolve_error err = visit(a, closure, n_closure, i, state, res, &res_len);
        if (err.kind != RESOLVE_OK) return err;
    }

    out->data = res;
    out->len  = res_len;
    return RESOLVE_OK_VAL;
}