path: root/resolve.c

/*
 * pkg - Dependency resolver
 * Uses Kahn's algorithm for topological sort
 * https://rawnix.org
 *
 * Copyright (c) 2025 zorz@gmx.com
 * SPDX-License-Identifier: BSD-2-Clause
 */

#include "resolve.h"
#include "repo.h"
#include "builder.h"

/* ---- Graph data structures ---- */

typedef struct {
    char *name;
    strarray_t *deps;
    int in_degree;
    bool visited;
    bool done;          /* emitted by topo_sort */
} node_t;

typedef struct {
    node_t **nodes;
    size_t count;
    size_t capacity;
} graph_t;

/* ---- Resolution lifecycle ---- */

resolution_t *resolution_new(void)
{
    resolution_t *r = xmalloc(sizeof(resolution_t));

    r->order = xmalloc(sizeof(strarray_t));
    r->missing = xmalloc(sizeof(strarray_t));
    r->cycle = xmalloc(sizeof(strarray_t));
    strarray_init(r->order);
    strarray_init(r->missing);
    strarray_init(r->cycle);
    r->has_cycle = false;
    r->has_missing = false;

    return r;
}

void resolution_free(resolution_t *r)
{
    if (!r)
        return;
    if (r->order) {
        strarray_free(r->order);
        free(r->order);
    }
    if (r->missing) {
        strarray_free(r->missing);
        free(r->missing);
    }
    if (r->cycle) {
        strarray_free(r->cycle);
        free(r->cycle);
    }
    free(r);
}

/* ---- Node / graph helpers ---- */

static node_t *node_new(const char *name)
{
    node_t *n = xmalloc(sizeof(node_t));

    n->name = xstrdup(name);
    n->deps = xmalloc(sizeof(strarray_t));
    strarray_init(n->deps);
    n->in_degree = 0;
    n->visited = false;
    n->done = false;
    return n;
}

static void node_free(node_t *n)
{
    if (!n)
        return;
    free(n->name);
    if (n->deps) {
        strarray_free(n->deps);
        free(n->deps);
    }
    free(n);
}

static graph_t *graph_new(void)
{
    graph_t *g = xmalloc(sizeof(graph_t));

    g->nodes = NULL;
    g->count = 0;
    g->capacity = 0;
    return g;
}

static void graph_free(graph_t *g)
{
    size_t i;

    if (!g)
        return;
    for (i = 0; i < g->count; i++)
        node_free(g->nodes[i]);
    free(g->nodes);
    free(g);
}

static node_t *graph_find(graph_t *g, const char *name)
{
    size_t i;

    for (i = 0; i < g->count; i++)
        if (strcmp(g->nodes[i]->name, name) == 0)
            return g->nodes[i];
    return NULL;
}

static node_t *graph_add(graph_t *g, const char *name)
{
    node_t *n;

    n = graph_find(g, name);
    if (n)
        return n;

    n = node_new(name);

    if (g->count >= g->capacity) {
        g->capacity = g->capacity == 0 ? 16 : g->capacity * 2;
        g->nodes = xrealloc(g->nodes, g->capacity * sizeof(node_t *));
    }

    g->nodes[g->count++] = n;
    return n;
}

/* ---- Resolve provider for virtual packages ---- */

static port_t *find_provider(repo_t *repo, const char *name)
{
    strarray_t *prov = repo_providers(repo, name);

    if (!prov || prov->size == 0)
        return NULL;

    /* dep_pending has already established that no installed
     * provider exists, so any provider works — take the first */
    return repo_find(repo, prov->data[0]);
}

/*
 * Compare installed version against port version.
 * Returns true if they differ (i.e. an update is available).
 */
bool version_differs(installed_pkg_t *ip, port_t *p)
{
    char repo_ver[256];

    if (!ip || !p || !p->pkg || !p->pkg->version)
        return false;

    version_build(repo_ver, sizeof(repo_ver),
                  p->pkg->version, p->pkg->release);
    return strcmp(ip->version, repo_ver) != 0;
}

/*
 * An installed package is current when it matches its port, is
 * frozen (locked with no MAKEPKG.lock behind it — a version-only
 * pin), or has no port to compare against.  The last case is
 * load-bearing: kernels are built from /usr/src, which is not in
 * any portdir, and must never be treated as outdated here.
 *
 * A lock WITH a recipe is compared like any port: port_load() reads
 * MAKEPKG.lock, so upstream is invisible and a difference can only
 * mean the operator edited the pinned recipe.
 */
static bool installed_current(repo_t *repo, pkgdb_t *pkgdb,
                              locker_t *locker, const char *name)
{
    port_t *p = repo_find(repo, name);

    if (locker && locker_is_locked(locker, name) && !port_recipe_locked(p))
        return true;

    if (!p || port_load(p) != 0)
        return true;

    return !version_differs(pkgdb_find(pkgdb, name), p);
}

/*
 * Decide whether a dependency needs work.  Returns NULL when it is
 * satisfied by a current installed package, otherwise the name to
 * queue:
 *
 *   - installed under its own name but outdated   -> dep
 *   - only an installed provider, and it's outdated -> provider's
 *     real name.  Queueing the virtual name instead would let
 *     find_provider() pick a different, uninstalled provider
 *     (llvm vs llvm-toolchain).
 *   - nothing installed                            -> dep
 *
 * Presence alone used to count as satisfied, so `pkg prepare`
 * happily built hipblas against a rocm-device-libs two releases
 * behind the tree.
 *
 * All providers are checked, not just the first, because
 * hash-table iteration order is non-deterministic.
 */
static const char *dep_pending(repo_t *repo, pkgdb_t *pkgdb,
                               locker_t *locker, const char *dep)
{
    strarray_t *prov;
    const char *stale = NULL;
    size_t i;

    if (pkgdb_installed(pkgdb, dep))
        return installed_current(repo, pkgdb, locker, dep) ? NULL : dep;

    prov = repo_providers(repo, dep);
    if (prov) {
        for (i = 0; i < prov->size; i++) {
            if (!pkgdb_installed(pkgdb, prov->data[i]))
                continue;
            if (installed_current(repo, pkgdb, locker, prov->data[i]))
                return NULL;
            if (!stale)
                stale = prov->data[i];
        }
    }

    return stale ? stale : dep;
}

/* ---- Graph construction ---- */

/*
 * Build the dependency graph.  When makedeps is true, we include
 * build-time dependencies ONLY for packages that haven't been built
 * yet (pkg_is_built == false).  Pre-built packages only pull in
 * their runtime depends.
 */
static graph_t *build_graph(repo_t *repo, const char *root, pkgdb_t *pkgdb,
                            locker_t *locker, bool makedeps,
                            resolution_t *res)
{
    graph_t *g;
    strlist_t *queue = NULL, *cur;
    node_t *n;
    port_t *p;
    size_t i;
    bool needs_build;

    g = graph_new();
    strlist_add(&queue, root);

    while (queue) {
        cur = queue;
        queue = queue->next;
        cur->next = NULL;

        /*
         * Fast path for repeat real-name visits.  Virtual names will
         * never be found here because we only ever add nodes under
         * the real (resolved) name — see the post-resolution check
         * further down.
         */
        n = graph_find(g, cur->data);
        if (n && n->visited) {
            strlist_free(cur);
            continue;
        }

        /*
         * Resolve the queued name to a port BEFORE touching the
         * graph.  This way:
         *   - missing packages don't leave dangling nodes in the
         *     graph (they used to land in res->order via topo sort);
         *   - virtual names like "ninja" never enter the graph at
         *     all — we go straight to the real provider, so two
         *     ports both depending on "ninja" can't produce two
         *     provider nodes.
         */
        p = repo_find(repo, cur->data);
        if (!p) {
            port_t *provider = find_provider(repo, cur->data);
            if (provider) {
                /*
                 * Virtual name → real provider.  Rewrite any edges
                 * already pointing at the virtual name so the graph
                 * stays internally consistent.
                 */
                size_t gi, di;
                p = provider;

                for (gi = 0; gi < g->count; gi++) {
                    node_t *other = g->nodes[gi];
                    for (di = 0; di < other->deps->size; di++) {
                        if (strcmp(other->deps->data[di],
                                   cur->data) == 0) {
                            free(other->deps->data[di]);
                            other->deps->data[di] =
                                xstrdup(p->name);
                        }
                    }
                }

                /*
                 * Provider already installed?  Dep is satisfied —
                 * skip without adding a node.  (dep_pending should
                 * have caught this earlier; this is the defensive
                 * second line for the case where the root target
                 * itself is a virtual name.)
                 */
                if (pkgdb_installed(pkgdb, p->name)) {
                    strlist_free(cur);
                    continue;
                }

                /*
                 * Provider may have been visited already through
                 * a different virtual alias or a direct reference.
                 * Look it up by REAL name now that we've resolved.
                 */
                n = graph_find(g, p->name);
                if (n && n->visited) {
                    strlist_free(cur);
                    continue;
                }
            } else if (!pkgdb_installed(pkgdb, cur->data)) {
                res->has_missing = true;
                strarray_add(res->missing, cur->data);
                strlist_free(cur);
                continue;
            } else {
                /* already installed, not in repo — skip */
                strlist_free(cur);
                continue;
            }
        }

        /* Now add the node under the real package name. */
        if (!n)
            n = graph_add(g, p->name);
        n->visited = true;

        if (port_load(p) != 0) {
            strlist_free(cur);
            continue;
        }

        /*
         * Skip makedeps for pre-built packages.  If the package
         * tarball already exists we only need its runtime deps
         * installed — no compiler, no headers, no build tooling.
         * This avoids pulling in dozens of -dev packages when
         * installing from a binary cache.
         *
         * Exception: the root package always needs its makedeps
         * checked.  'pkg prepare' must detect missing build deps
         * even when a previous tarball exists — the user is about
         * to rebuild.
         */
        needs_build = makedeps &&
                      (strcmp(n->name, root) == 0 || !pkg_is_built(p));

        /*
         * A recipe-locked port with no tarball for its lock version is
         * a source build no matter what — even under -b, where bulk
         * refuses it — so it always needs its makedeps.
         */
        if (!needs_build && port_recipe_locked(p) && !pkg_is_built(p))
            needs_build = true;

        if (needs_build && p->pkg && p->pkg->makedeps) {
            for (i = 0; i < p->pkg->makedeps->size; i++) {
                const char *dep = p->pkg->makedeps->data[i];
                const char *want = dep_pending(repo, pkgdb, locker, dep);
                if (!want) {
                    if (strcmp(dep, root) != 0)
                        continue;
                    want = dep;
                }
                if (!strarray_contains(n->deps, want)) {
                    strarray_add(n->deps, want);
                    strlist_add(&queue, want);
                }
            }
        }

        /* runtime deps are always included */
        if (p->pkg && p->pkg->depends) {
            for (i = 0; i < p->pkg->depends->size; i++) {
                const char *dep = p->pkg->depends->data[i];
                const char *want = dep_pending(repo, pkgdb, locker, dep);
                if (!want) {
                    if (strcmp(dep, root) != 0)
                        continue;
                    want = dep;
                }
                if (!strarray_contains(n->deps, want)) {
                    strarray_add(n->deps, want);
                    strlist_add(&queue, want);
                }
            }
        }

        strlist_free(cur);
    }

    /* calculate in-degrees */
    for (i = 0; i < g->count; i++)
        g->nodes[i]->in_degree = g->nodes[i]->deps->size;

    return g;
}

/* ---- Topological sort (Kahn's algorithm) ---- */

/*
 * Kahn's is stuck: every remaining node waits on another.  If some
 * remaining node waits only on packages that are already INSTALLED,
 * it can be built against those installed versions.  1.3.0 did this
 * implicitly by never letting installed deps into the graph; now
 * that outdated ones enter it, two installed packages that depend on
 * each other and both bump (freetype <-> harfbuzz) would otherwise be
 * refused as a cycle — on exactly the sysup after a ports update.
 *
 * Takes the deepest candidate (last in BFS order) so dependencies are
 * rebuilt before the target that pulled them in.  Returns NULL when
 * the cycle involves something not installed: a genuine cycle.
 */
static node_t *cycle_break(graph_t *g, pkgdb_t *pkgdb)
{
    node_t *pick = NULL;
    size_t i, j;

    for (i = 0; i < g->count; i++) {
        node_t *n = g->nodes[i];
        bool ok = true;

        if (n->done)
            continue;
        for (j = 0; j < n->deps->size && ok; j++) {
            node_t *d = graph_find(g, n->deps->data[j]);
            if (d && !d->done && !pkgdb_installed(pkgdb, d->name))
                ok = false;
        }
        if (ok)
            pick = n;
    }
    return pick;
}

/* Emit n and release the nodes waiting on it. */
static void topo_emit(graph_t *g, node_t *n, resolution_t *res,
                      strlist_t **queue)
{
    size_t i, j;

    n->done = true;
    strarray_add(res->order, n->name);

    for (i = 0; i < g->count; i++) {
        node_t *other = g->nodes[i];
        if (other->done)
            continue;
        for (j = 0; j < other->deps->size; j++) {
            if (strcmp(other->deps->data[j], n->name) == 0) {
                other->in_degree--;
                if (other->in_degree == 0)
                    strlist_add(queue, other->name);
                break;
            }
        }
    }
}

static bool topo_sort(graph_t *g, pkgdb_t *pkgdb, resolution_t *res)
{
    strlist_t *queue = NULL, *cur;
    node_t *n;
    size_t i, processed = 0;

    /* seed with in_degree == 0 */
    for (i = 0; i < g->count; i++)
        if (g->nodes[i]->in_degree == 0)
            strlist_add(&queue, g->nodes[i]->name);

    for (;;) {
        while (queue) {
            cur = queue;
            queue = queue->next;
            cur->next = NULL;

            n = graph_find(g, cur->data);
            if (n && !n->done) {
                topo_emit(g, n, res, &queue);
                processed++;
            }
            strlist_free(cur);
        }

        if (processed == g->count)
            break;

        n = cycle_break(g, pkgdb);
        if (!n)
            break;
        topo_emit(g, n, res, &queue);
        processed++;
    }

    /* cycle detection */
    if (processed < g->count) {
        res->has_cycle = true;
        for (i = 0; i < g->count; i++)
            if (!g->nodes[i]->done)
                strarray_add(res->cycle, g->nodes[i]->name);
        return false;
    }

    return true;
}

/* ---- Public API ---- */

resolution_t *resolve(repo_t *repo, const char *pkg, pkgdb_t *pkgdb,
                      locker_t *locker, bool makedeps)
{
    resolution_t *res;
    graph_t *g;

    if (!repo || !pkg || !pkgdb)
        return NULL;

    res = resolution_new();
    g = build_graph(repo, pkg, pkgdb, locker, makedeps, res);

    if (!g) {
        resolution_free(res);
        return NULL;
    }

    topo_sort(g, pkgdb, res);
    graph_free(g);

    return res;
}