usm/src/lib/Resolver.vala

using Invercargill;
using Invercargill.DataStructures;

namespace Usm {

    /**
     * Errors thrown while resolving a package set.
     *
     * Every member's message is a fully itemised report safe to print
     * verbatim by a CLI.
     */
    public errordomain ResolverError {
        /** A required resource ref could not be satisfied; the message itemises every failing ref and why. */
        UNSATISFIABLE,
        /** No candidate group in a grouped dependency phase is satisfiable; the message carries a per-group itemised report. */
        NO_VIABLE_GROUP,
        /** The resolved package graph contains a dependency cycle; the message names the packages in the cycle. */
        CYCLE,
        /** The configured system package manager query failed. */
        SYSTEM_QUERY_FAILED
    }

    /**
     * Why one {@link ResourceRef} could not be satisfied during resolution:
     * it was neither present locally nor provided by any system or USM
     * package candidate.
     */
    public class RefFailure : Object {
        /** The ref that could not be satisfied. */
        public ResourceRef resource { get; set; }
        /** The name of the package whose dependency phase required it. */
        public string origin { get; set; }
        /** Whether a system package manager was consulted for this ref. */
        public bool spm_configured { get; set; }

        /**
         * One-line description used in itemised reports, e.g.
         * `bin:foo (required by "app") — not present locally; no system package provides it; no USM package provides it`.
         */
        public string describe(string reported_for) {
            var origin_note = origin != reported_for ? @" (required by \"$origin\")" : "";
            var spm_reason = spm_configured ? "no system package provides it" : "no system package manager is configured";
            return @"$(resource.to_string())$origin_note — not present locally; $spm_reason; no USM package provides it";
        }
    }

    /**
     * One candidate group that could not be satisfied during group selection,
     * carrying the failure for each unresolvable member.
     */
    public class GroupFailure : Object {
        /** The 1-based position of the group within its phase. */
        public uint group_index { get; set; }
        /** The members of the group, deterministically ordered. */
        public Vector<ResourceRef> members { get; set; }
        /** Why each unresolvable member failed. */
        public Vector<RefFailure> failures { get; set; }

        /** Indented multi-line description used in itemised reports. */
        public string describe(string reported_for) {
            var builder = new StringBuilder();
            builder.append_printf("  Group %u (%s):\n", group_index, members.to_string(r => r.to_string(), ", "));
            foreach(var failure in failures) {
                builder.append_printf("    %s\n", failure.describe(reported_for));
            }
            return builder.str;
        }
    }

    /**
     * The outcome of a successful {@link Resolver.resolve}: the resolved
     * package set, the chosen system packages and the topological
     * install/removal orders derived from the resolved package graph.
     */
    public class ResolutionResult : Object {
        /** Every chosen USM package: the roots plus their transitive provider closure. */
        public PackageSet packages { get; set; }
        /** System packages chosen to satisfy missing resources, ordered by name; install them as one transaction before any USM package. */
        public Vector<SystemPackageCandidate> system_packages { get; set; }
        /** The chosen USM packages ordered dependencies-before-dependents (Kahn's algorithm, package-name tie-break). */
        public Vector<AbstractPackage> install_order { get; set; }
        /** The exact reverse of {@link install_order}: dependents are removed before their providers. */
        public Vector<AbstractPackage> removal_order { get; set; }
    }

    /**
     * Mutable working state for one resolution run.
     *
     * Snapshots are deep (packages, processed markers, chosen system
     * packages and per-package chosen refs are all copied) so a group
     * evaluation can be rolled back by restoring a snapshot without sharing
     * any mutable collection with the state it was taken from.
     */
    internal class ResolutionState {
        public PackageSet chosen = new PackageSet();
        public HashSet<AbstractPackage> processed = new HashSet<AbstractPackage>();
        public Dictionary<string, SystemPackageCandidate> spm_chosen = new Dictionary<string, SystemPackageCandidate>();
        public Dictionary<string, Set<ResourceRef>> refs_by_package = new Dictionary<string, Set<ResourceRef>>();
        /**
         * The refs the walk satisfied through SPM candidates — the repair
         * pass ({@link Resolver.resolve}) re-selects providers for exactly
         * these when the greedy set turns out not to co-install.
         */
        public Vector<ResourceRef> spm_refs = new Vector<ResourceRef>();

        public ResolutionState snapshot() {
            var copy = new ResolutionState();
            copy.chosen.union_with(chosen);
            copy.processed.union_with(processed);
            foreach(var pair in spm_chosen) {
                copy.spm_chosen.set(pair.key, pair.value);
            }
            foreach(var pair in refs_by_package) {
                var refs = new HashSet<ResourceRef>();
                refs.union_with(pair.value);
                copy.refs_by_package.set(pair.key, refs);
            }
            copy.spm_refs = new Vector<ResourceRef>();
            copy.spm_refs.add_all(spm_refs);
            return copy;
        }
    }

    public class Resolver {

        private Dictionary<Repository, RepositoryListing> listings = new Dictionary<Repository, RepositoryListing>();
        private Set<AbstractPackage> supplied = new HashSet<AbstractPackage>();
        private ResourceFinder resource_finder;
        private Vector<AbstractPackage>? catalog_cache = null;

        // Per-resolution state, reset at the start of every {@link resolve} call
        private ResolutionState state = new ResolutionState();
        private Dictionary<string, Vector<SystemPackageCandidate>> spm_index = new Dictionary<string, Vector<SystemPackageCandidate>>();
        private Dictionary<string, bool> local_presence = new Dictionary<string, bool>();
        private bool spm_configured = false;
        /**
         * The last batched SPM query result — kept so the post-walk
         * repair pass can re-select providers from the full candidate
         * pool without a second helper spawn.
         */
        private SystemQueryResult? spm_query_result = null;

        /**
         * Optional progress callback fired once per resolved package as
         * `resolved_count / estimated_total`, where the estimate is the
         * number of roots times two (a rough dependency multiplier) and
         * the final report is clamped to 1.0 when resolution completes.
         * Null (the default) disables reporting.
         */
        public owned ProgressDelegate? resolution_progress { get; set; }

        /** Estimated package count for {@link resolution_progress}: roots x 2, at least 1. */
        private uint resolution_estimated_total = 1;

        /** The lifecycle phases resolution considers, in processing order. */
        private const string[] PHASES = { "manage", "build", "runtime" };

        public Resolver(ResourceFinder local_resource_finder) {
            this.resource_finder = local_resource_finder;
        }

        public void load_listing(Repository repo, RepositoryListing listing) {
            listings.set(repo, listing);
            catalog_cache = null;
        }

        public void supply_package(string path) throws Error {
            supplied.add(new AbstractPackage.from_package(path));
            catalog_cache = null;
        }

        /**
         * Adds every readable cached package as a supplied package so the
         * cache can satisfy resources during resolution. Unreadable cache
         * entries (for example a half-finished download) are skipped with a
         * warning.
         */
        public void load_cache(Paths paths) throws Error {
            var cache_state = new SystemState(paths);
            foreach (var package in cache_state.get_cached_packages()) {
                if(!File.new_for_path(package.package_path).query_exists()) {
                    continue;
                }
                try {
                    supply_package(package.package_path);
                }
                catch(Error e) {
                    warning(@"[Usm] Skipping unreadable cached package \"$(package.package_name)\": $(e.message)");
                }
            }
        }

        /**
         * Finds a package by exact name, preferring repository packages over
         * supplied (cached) ones so installs pull a fresh copy. Deterministic:
         * repository packages are preferred, then the highest version, then
         * repository name.
         */
        public AbstractPackage? find_package(string search) {
            AbstractPackage? match = null;
            foreach(var package in catalog()) {
                if(package.manifest.name != search) {
                    continue;
                }
                if(package.repository != null) {
                    match = package;
                }
                else if(match == null) {
                    match = package;
                }
            }
            return match;
        }

        /**
         * Finds a package providing the given resource, deterministically
         * choosing the best provider: alphabetically-first package name,
         * then the HIGHEST version (a stale cached copy of an older
         * release must never win over a newer one), then a repository
         * package over a supplied/cached one so installs pull a fresh
         * copy, then repository name and package path.
         */
        public AbstractPackage? find_resource(ResourceRef resource) {
            AbstractPackage? match = null;
            foreach(var package in catalog()) {
                if(!package.manifest.satisfies(resource)) {
                    continue;
                }
                if(match == null) {
                    match = package;
                    continue;
                }
                if(better_provider(package, match)) {
                    match = package;
                }
            }
            return match;
        }

        /**
         * Whether {@link candidate} beats {@link incumbent} as a provider:
         * alphabetically-first name, then highest version, then repository
         * over supplied/cache, then repository name and package path.
         */
        private static bool better_provider(AbstractPackage candidate, AbstractPackage incumbent) {
            var by_name = candidate.manifest.name.collate(incumbent.manifest.name);
            if(by_name != 0) {
                return by_name < 0;
            }
            var by_version = candidate.manifest.version.compare(incumbent.manifest.version);
            if(by_version != 0) {
                return by_version > 0;
            }
            if((candidate.repository == null) != (incumbent.repository == null)) {
                return candidate.repository != null;
            }
            var by_repository = (candidate.repository?.name ?? "").collate(incumbent.repository?.name ?? "");
            if(by_repository != 0) {
                return by_repository < 0;
            }
            return (candidate.package_path ?? "").collate(incumbent.package_path ?? "") < 0;
        }

        /**
         * Resolves the full dependency closure for the given root packages.
         *
         * A missing resource resolves in order: (a) already present locally,
         * (b) system packages — via ONE batched query covering every ref any
         * candidate group could need, choosing per ref the candidate
         * minimising new installs (dependency-count − installed-dependency-count),
         * deduplicating packages chosen for multiple resources — then (c) USM
         * packages from repositories, the cache or supplied packages. Without
         * a configured manager (b) is skipped. Grouped phases select, in
         * manifest order, the viable group minimising total new installs
         * (USM packages count with their transitive closure; resources
         * already satisfied cost 0); ties keep manifest order.
         *
         * Throws {@link ResolverError} with an itemised report when a flat
         * ref is unsatisfiable, when no group is viable, or when the resolved
         * graph contains a cycle.
         */
        public ResolutionResult resolve(Lot<AbstractPackage> roots, SystemPackageManager? spm = null) throws Error {
            state = new ResolutionState();
            spm_index = new Dictionary<string, Vector<SystemPackageCandidate>>();
            local_presence = new Dictionary<string, bool>();
            spm_configured = spm != null && spm.enabled;
            spm_query_result = null;
            resolution_estimated_total = roots.length * 2;
            if(resolution_estimated_total < 1) {
                resolution_estimated_total = 1;
            }

            var ordered_roots = roots.sort(compare_packages).to_vector();
            foreach(var root in ordered_roots) {
                state.chosen.add(root);
            }

            if(spm_configured) {
                batch_query(roots, (!)spm);
            }

            foreach(var root in ordered_roots) {
                process_package(root);
            }

            var install_order = topological_order(state.chosen, state.refs_by_package);
            var removal_order = new Vector<AbstractPackage>();
            for(uint index = install_order.length; index > 0; index--) {
                removal_order.add(install_order[index - 1]);
            }

            var system_packages = new Vector<SystemPackageCandidate>();
            foreach(var pair in state.spm_chosen) {
                system_packages.add(pair.value);
            }
            system_packages = system_packages.sort((a, b) => a.name.collate(b.name)).to_vector();

            // The walk chose SPM candidates greedily with conflict
            // METADATA only. The SPM's own solver is the final arbiter:
            // when the finished set does not co-install, re-select the
            // whole SPM-assigned ref set through the shared
            // provider-selection pass (planner-verified, minimal
            // cumulative closure). Zero extra helper spawns in the
            // common case — one plan call.
            if(spm != null && ((SystemPackageManager)spm).enabled && system_packages.length > 0
                    && spm_query_result != null && state.spm_refs.length > 0) {
                var chosen_names = new Vector<string>();
                foreach(var system_package in system_packages) {
                    chosen_names.add(system_package.name);
                }
                if(((SystemPackageManager)spm).try_plan_install(chosen_names) == null) {
                    SystemProviderPlan plan = names => ((SystemPackageManager)spm).try_plan_install(names);
                    var selection = ProviderSelection.select(state.spm_refs, (!)spm_query_result, plan);
                    if(selection.planner_succeeded && selection.unresolved.length > 0) {
                        var listing = new StringBuilder();
                        foreach(var reference in selection.unresolved) {
                            if(listing.len > 0) {
                                listing.append(", ");
                            }
                            listing.append(reference.to_string());
                        }
                        throw new ResolverError.UNSATISFIABLE(
                            "The system package manager cannot co-install a provider set for: %s — the covering providers conflict with each other"
                            .printf(listing.str));
                    }
                    var by_name = new Dictionary<string, SystemPackageCandidate>();
                    foreach(var candidate in ((!)spm_query_result).packages) {
                        if(!by_name.has(candidate.name)) {
                            by_name.set(candidate.name, candidate);
                        }
                    }
                    var repaired = new Vector<SystemPackageCandidate>();
                    foreach(var name in selection.chosen) {
                        SystemPackageCandidate candidate;
                        if(by_name.try_get(name, out candidate)) {
                            repaired.add(candidate);
                        }
                    }
                    // A planner that never succeeded is a helper without
                    // a working plan mode, not a conflict verdict: keep
                    // the walk's greedy set rather than discarding it on
                    // unusable evidence.
                    if(repaired.length > 0 && (selection.planner_succeeded || repaired.length < system_packages.length)) {
                        system_packages = repaired.sort((a, b) => a.name.collate(b.name)).to_vector();
                    }
                }
            }

            var packages = new PackageSet();
            packages.union_with(state.chosen);

            if(resolution_progress != null) {
                resolution_progress(1.0f);
            }

            return new ResolutionResult() {
                packages = packages,
                system_packages = system_packages,
                install_order = install_order,
                removal_order = removal_order
            };
        }

        /**
         * Resolves the dependency closure of a LOCAL manifest — a git
         * checkout or build directory — rather than a repository package:
         * the entry point `usm manifest install`/`usm manifest build`
         * and usmrad's ensure-deps share, so provider selection (SPM
         * conflict awareness, minimal closures, planner verification)
         * behaves identically everywhere. The root contributes its
         * dependency phases; its own provides are NOT installed (it is
         * the thing being built, not a dependency).
         */
        public ResolutionResult resolve_manifest(Manifest manifest, SystemPackageManager? spm = null) throws Error {
            var roots = new Vector<AbstractPackage>();
            roots.add(new AbstractPackage.from_manifest(manifest));
            return resolve(roots, spm);
        }

        /**
         * Orders packages dependencies-before-dependents with Kahn's
         * algorithm and a deterministic package-name tie-break; a cycle is a
         * hard error naming the packages in it.
         *
         * {@link chosen_refs} maps a package name to the refs chosen for it
         * during resolution (flat refs plus the chosen group's members); when
         * null the requirements are derived from each manifest's flat
         * phases plus every candidate group's refs. Only refs provided by
         * another package in the set create ordering edges.
         */
        public static Vector<AbstractPackage> topological_order(Enumerable<AbstractPackage> packages, ReadOnlyAssociative<string, Set<ResourceRef>>? chosen_refs = null) throws ResolverError {
            var nodes = packages.sort(compare_packages).to_vector();

            var by_name = new Dictionary<string, Vector<AbstractPackage>>();
            foreach(var node in nodes) {
                var name = node.manifest.name;
                Vector<AbstractPackage> named;
                if(!by_name.try_get(name, out named)) {
                    named = new Vector<AbstractPackage>();
                    by_name.set(name, named);
                }
                named.add(node);
            }

            var required = new Dictionary<string, Vector<ResourceRef>>();
            foreach(var node in nodes) {
                var refs = new Vector<ResourceRef>();
                Set<ResourceRef>? chosen = null;
                if(chosen_refs != null && chosen_refs.try_get(node.manifest.name, out chosen)) {
                    foreach(var resource in chosen) {
                        refs.add(resource);
                    }
                }
                else {
                    foreach(var phase in resolution_phases(node.manifest)) {
                        foreach(var resource in phase.ordered_all_refs()) {
                            refs.add(resource);
                        }
                    }
                }
                required.set(node.manifest.name, refs.sort((a, b) => a.to_string().collate(b.to_string())).to_vector());
            }

            // Edges provider → dependent; one edge per (provider, dependent) pair
            var dependents = new Dictionary<string, Vector<string>>();
            var indegree = new Dictionary<string, uint>();
            foreach(var node in nodes) {
                indegree.set(node.manifest.name, 0);
            }
            foreach(var dependent in nodes) {
                var dependent_name = dependent.manifest.name;
                var linked_providers = new HashSet<string>();
                Vector<ResourceRef> dependent_refs;
                if(!required.try_get(dependent_name, out dependent_refs)) {
                    continue;
                }
                foreach(var resource in dependent_refs) {
                    foreach(var provider in nodes) {
                        var provider_name = provider.manifest.name;
                        if(provider_name == dependent_name || linked_providers.has(provider_name)) {
                            continue;
                        }
                        if(provider.manifest.satisfies(resource)) {
                            linked_providers.add(provider_name);
                            Vector<string> follower_names;
                            if(!dependents.try_get(provider_name, out follower_names)) {
                                follower_names = new Vector<string>();
                                dependents.set(provider_name, follower_names);
                            }
                            follower_names.add(dependent_name);
                            uint degree;
                            indegree.try_get(dependent_name, out degree);
                            indegree.set(dependent_name, degree + 1);
                        }
                    }
                }
            }

            var order = new Vector<AbstractPackage>();
            var remaining = new HashSet<string>();
            foreach(var node in nodes) {
                remaining.add(node.manifest.name);
            }
            while(remaining.any()) {
                string? next = null;
                foreach(var name in remaining) {
                    uint degree;
                    if(indegree.try_get(name, out degree) && degree == 0) {
                        if(next == null || name.collate(next) < 0) {
                            next = name;
                        }
                    }
                }
                if(next == null) {
                    throw new ResolverError.CYCLE(
                        @"The resolved package graph contains a dependency cycle: $(describe_cycle(remaining, required, nodes))"
                    );
                }
                remaining.remove(next);
                Vector<AbstractPackage> named;
                if(by_name.try_get(next, out named)) {
                    foreach(var package in named) {
                        order.add(package);
                    }
                }
                Vector<string> follower_names;
                if(dependents.try_get(next, out follower_names)) {
                    foreach(var follower in follower_names) {
                        if(remaining.has(follower)) {
                            uint degree;
                            indegree.try_get(follower, out degree);
                            indegree.set(follower, degree - 1);
                        }
                    }
                }
            }

            return order;
        }

        /** Deterministic catalog order: (name, version, repository name, package path). */
        private static int compare_packages(AbstractPackage a, AbstractPackage b) {
            var by_name = a.manifest.name.collate(b.manifest.name);
            if(by_name != 0) {
                return by_name;
            }
            var by_version = a.manifest.version.compare(b.manifest.version);
            if(by_version != 0) {
                return by_version;
            }
            var by_repository = (a.repository?.name ?? "").collate(b.repository?.name ?? "");
            if(by_repository != 0) {
                return by_repository;
            }
            return (a.package_path ?? "").collate(b.package_path ?? "");
        }

        /** The lifecycle phases resolution considers, in processing order. */
        private static Vector<DependencyPhase> resolution_phases(Manifest manifest) {
            var phases = new Vector<DependencyPhase>();
            phases.add(manifest.dependencies.manage);
            phases.add(manifest.dependencies.build);
            phases.add(manifest.dependencies.runtime);
            return phases;
        }

        private static Vector<AbstractPackage> catalog_of(Set<AbstractPackage> supplied, Dictionary<Repository, RepositoryListing> listings) {
            return supplied.concat(
                    listings.select_many<Pair<Repository, RepositoryListingEntry>>(l => l.value.entries.select_pairs<Repository, RepositoryListingEntry>(e => l.key, e => e))
                    .select<AbstractPackage>(p => new AbstractPackage.from_repository(p.value1, p.value2)))
                .sort(compare_packages)
                .to_vector();
        }

        private Vector<AbstractPackage> catalog() {
            if(catalog_cache == null) {
                catalog_cache = catalog_of(supplied, listings);
            }
            return catalog_cache;
        }

        /**
         * Collects every ref resolution could possibly consult — all refs of
         * all candidate groups of every package reachable through USM
         * providers — then asks the system package manager about the locally
         * missing ones in ONE batched query.
         */
        private void batch_query(Lot<AbstractPackage> roots, SystemPackageManager spm) throws Error {
            var refs = new HashSet<ResourceRef>();
            var visited = new HashSet<AbstractPackage>();
            var pending = new Series<AbstractPackage>();
            foreach(var root in roots) {
                pending.add(root);
            }
            while(pending.length > 0) {
                var package = pending.pop_start();
                if(visited.has(package)) {
                    continue;
                }
                visited.add(package);
                foreach(var phase in resolution_phases(package.manifest)) {
                    foreach(var resource in phase.ordered_all_refs()) {
                        refs.add(resource);
                        if(!has_local(resource)) {
                            var provider = find_resource(resource);
                            if(provider != null) {
                                pending.add(provider);
                            }
                        }
                    }
                }
            }

            var missing = new Vector<ResourceRef>();
            foreach(var resource in refs.sort((a, b) => a.to_string().collate(b.to_string()))) {
                // Version-constrained refs have no SPM translation yet:
                // shims match names exactly, so querying them would only
                // yield misleading not-founds. They resolve from local
                // presence or USM packages.
                if(resource.constraint != null) {
                    continue;
                }
                if(!has_local(resource)) {
                    missing.add(resource);
                }
            }
            if(missing.length == 0) {
                return;
            }

            SystemQueryResult? result = null;
            try {
                result = spm.query_sync(missing);
                spm_query_result = result;
            }
            catch(Error e) {
                throw new ResolverError.SYSTEM_QUERY_FAILED(@"$(e.message)");
            }
            if(result == null) {
                spm_configured = false;
                return;
            }

            foreach(var candidate in result.packages) {
                foreach(var resource in candidate.resources) {
                    var key = resource.to_string();
                    Vector<SystemPackageCandidate> candidates;
                    if(!spm_index.try_get(key, out candidates)) {
                        candidates = new Vector<SystemPackageCandidate>();
                        spm_index.set(key, candidates);
                    }
                    candidates.add(candidate);
                }
            }
        }

        private bool has_local(ResourceRef resource) {
            var key = resource.to_string();
            bool present;
            if(local_presence.try_get(key, out present)) {
                return present;
            }
            present = resource_finder.has_resource(resource);
            local_presence.set(key, present);
            return present;
        }

        /** Cost ordering for system package candidates: new installs first, then name. */
        private static int compare_spm_candidates(SystemPackageCandidate a, SystemPackageCandidate b) {
            var by_cost = (a.dependency_count - a.installed_dependency_count) - (b.dependency_count - b.installed_dependency_count);
            if(by_cost != 0) {
                return by_cost;
            }
            return a.name.collate(b.name);
        }

        /**
         * The best candidate providing the resource: one already chosen for
         * another resource (cost 0, smallest name) when possible, otherwise
         * the cheapest by (new installs, name). Candidates whose conflicts
         * metadata names a chosen package — in EITHER direction, since
         * blockers are declared asymmetrically (dropbear declares
         * `!openssh-client`; the openssh packages declare nothing) — are
         * skipped: alternative providers of one ref routinely cannot
         * coexist, and the walk must never pick such a mix. The post-walk
         * repair pass in {@link resolve} re-checks the finished set with
         * the SPM's own solver, catching pairs the metadata missed.
         */
        private SystemPackageCandidate? best_spm_candidate(ResourceRef resource) {
            Vector<SystemPackageCandidate> candidates;
            if(!spm_index.try_get(resource.to_string(), out candidates)) {
                return null;
            }
            SystemPackageCandidate? already_chosen = null;
            SystemPackageCandidate? best = null;
            foreach(var candidate in candidates) {
                if(conflicts_with_chosen(candidate)) {
                    continue;
                }
                if(state.spm_chosen.has(candidate.name)) {
                    if(already_chosen == null || candidate.name.collate(already_chosen.name) < 0) {
                        already_chosen = candidate;
                    }
                }
                else if(best == null || compare_spm_candidates(candidate, best) < 0) {
                    best = candidate;
                }
            }
            return already_chosen ?? best;
        }

        /**
         * Symmetric conflict test against the walk's chosen SPM set: the
         * candidate's own metadata naming a chosen package, or a chosen
         * package's metadata naming the candidate.
         */
        private bool conflicts_with_chosen(SystemPackageCandidate candidate) {
            foreach(var name in candidate.conflicts) {
                if(state.spm_chosen.has(name)) {
                    return true;
                }
            }
            foreach(var pair in state.spm_chosen) {
                foreach(var name in pair.value.conflicts) {
                    if(name == candidate.name) {
                        return true;
                    }
                }
            }
            return false;
        }

        /**
         * Resolves one resource ref for {@link origin} under the
         * local → system-package → USM-package precedence, mutating the
         * current {@link state}; returns the failure when unsatisfiable.
         */
        private RefFailure? resolve_ref(AbstractPackage origin, ResourceRef resource) throws Error {
            if(state.chosen.provides(resource) || has_local(resource)) {
                return null;
            }
            if(spm_configured) {
                var candidate = best_spm_candidate(resource);
                if(candidate != null) {
                    state.spm_chosen.set(candidate.name, candidate);
                    if(!state.spm_refs.any(r => r.to_string() == resource.to_string())) {
                        state.spm_refs.add(resource);
                    }
                    return null;
                }
            }
            var provider = find_resource(resource);
            if(provider != null) {
                if(!state.chosen.has(provider)) {
                    state.chosen.add(provider);
                }
                process_package(provider);
                return null;
            }
            return new RefFailure() {
                resource = resource,
                origin = origin.manifest.name,
                spm_configured = spm_configured
            };
        }

        private void process_package(AbstractPackage package) throws Error {
            if(state.processed.has(package)) {
                return;
            }
            state.processed.add(package);
            report_resolution_progress();

            var manifest = package.manifest;
            for(int phase_index = 0; phase_index < PHASES.length; phase_index++) {
                var phase_name = PHASES[phase_index];
                var phase = manifest_phase(manifest, phase_name);
                if(phase.is_grouped) {
                    select_group(package, phase_name, phase);
                }
                else {
                    var failures = new Vector<RefFailure>();
                    foreach(var resource in phase.ordered_required()) {
                        var failure = resolve_ref(package, resource);
                        if(failure != null) {
                            failures.add(failure);
                        }
                    }
                    if(failures.any()) {
                        var builder = new StringBuilder();
                        builder.append_printf(
                            "Could not resolve package \"%s\" (phase \"%s\"): %u unresolvable dependenc%s:\n",
                            manifest.name, phase_name, failures.length, failures.length == 1 ? "y" : "ies"
                        );
                        foreach(var failure in failures) {
                            builder.append_printf("  %s\n", failure.describe(manifest.name));
                        }
                        throw new ResolverError.UNSATISFIABLE(builder.str);
                    }
                    record_refs(package, phase.ordered_required());
                }
            }
        }

        /**
         * Fires {@link resolution_progress} for the packages processed
         * so far, clamped to 1.0; the estimate deliberately
         * over-counts shallow closures so the bar never sits full
         * before resolution is done.
         */
        private void report_resolution_progress() {
            if(resolution_progress == null) {
                return;
            }
            var fraction = (float)state.processed.count() / (float)resolution_estimated_total;
            resolution_progress(fraction > 1.0f ? 1.0f : fraction);
        }

        private static DependencyPhase manifest_phase(Manifest manifest, string phase_name) {
            switch(phase_name) {
                case "manage":
                    return manifest.dependencies.manage;
                case "build":
                    return manifest.dependencies.build;
                case "runtime":
                    return manifest.dependencies.runtime;
                default:
                    assert_not_reached();
            }
        }

        /**
         * Evaluates the phase's candidate groups in manifest order on a
         * snapshot of the choices already made: a group is viable when every
         * member resolves. The viable group minimising total new installs
         * (USM packages with their transitive closure plus system packages by
         * their cost fields) is committed; ties keep manifest order. When no
         * group is viable an itemised per-group report is thrown.
         */
        private void select_group(AbstractPackage package, string phase_name, DependencyPhase phase) throws Error {
            var base_state = state.snapshot();
            var groups = phase.ordered_groups();
            var group_failures = new Vector<GroupFailure>();

            ResolutionState? best_state = null;
            uint best_index = 0;
            int best_cost = 0;

            for(uint index = 0; index < groups.length; index++) {
                // A fresh copy per evaluation: state must never alias
                // base_state, or every group's additions would look
                // pre-existing and cost nothing
                state = base_state.snapshot();
                var failures = new Vector<RefFailure>();
                foreach(var resource in groups[index]) {
                    var failure = resolve_ref(package, resource);
                    if(failure != null) {
                        failures.add(failure);
                    }
                }
                if(failures.any()) {
                    group_failures.add(new GroupFailure() {
                        group_index = index + 1,
                        members = groups[index],
                        failures = failures
                    });
                    continue;
                }
                var cost = new_install_cost(base_state);
                if(best_state == null || cost < best_cost) {
                    best_cost = cost;
                    best_index = index;
                    best_state = state.snapshot();
                }
            }
            if(best_state == null) {
                var builder = new StringBuilder();
                builder.append_printf(
                    "Could not resolve package \"%s\" (phase \"%s\"): no candidate dependency group is satisfiable.\n",
                    package.manifest.name, phase_name
                );
                foreach(var failure in group_failures) {
                    builder.append(failure.describe(package.manifest.name));
                }
                throw new ResolverError.NO_VIABLE_GROUP(builder.str);
            }

            state = best_state;
            record_refs(package, groups[best_index]);
        }

        /** Total new installs the current state adds over {@link base_state}: new USM packages plus system-package new-install costs. */
        private int new_install_cost(ResolutionState base_state) {
            var cost = (int)(state.chosen.count() - base_state.chosen.count());
            foreach(var pair in state.spm_chosen) {
                if(!base_state.spm_chosen.has(pair.key)) {
                    cost += pair.value.dependency_count - pair.value.installed_dependency_count;
                }
            }
            return cost;
        }

        private void record_refs(AbstractPackage package, Vector<ResourceRef> refs) {
            Set<ResourceRef> recorded;
            if(!state.refs_by_package.try_get(package.manifest.name, out recorded)) {
                recorded = new HashSet<ResourceRef>();
                state.refs_by_package.set(package.manifest.name, recorded);
            }
            foreach(var resource in refs) {
                recorded.add(resource);
            }
        }

        /** Walks provider edges among {@link remaining} from its smallest name until a node repeats, naming the cycle found. */
        private static string describe_cycle(HashSet<string> remaining, Dictionary<string, Vector<ResourceRef>> required, Vector<AbstractPackage> nodes) {
            var providers_of = new Dictionary<string, Vector<string>>();
            foreach(var dependent in nodes) {
                var dependent_name = dependent.manifest.name;
                foreach(var provider in nodes) {
                    var provider_name = provider.manifest.name;
                    if(provider_name == dependent_name || !remaining.has(provider_name)) {
                        continue;
                    }
                    Vector<ResourceRef> refs;
                    if(!required.try_get(dependent_name, out refs)) {
                        continue;
                    }
                    var provided = false;
                    foreach(var resource in refs) {
                        if(provider.manifest.satisfies(resource)) {
                            provided = true;
                            break;
                        }
                    }
                    if(provided) {
                        Vector<string> providers;
                        if(!providers_of.try_get(dependent_name, out providers)) {
                            providers = new Vector<string>();
                            providers_of.set(dependent_name, providers);
                        }
                        providers.add(provider_name);
                    }
                }
            }

            string? smallest = null;
            foreach(var name in remaining) {
                if(smallest == null || name.collate(smallest) < 0) {
                    smallest = name;
                }
            }

            var path = new Series<string>();
            var seen = new HashSet<string>();
            var current = smallest;
            while(current != null && !seen.has(current)) {
                seen.add(current);
                path.add(current);
                string? next = null;
                Vector<string> providers;
                if(providers_of.try_get(current, out providers)) {
                    foreach(var provider in providers) {
                        if(next == null || provider.collate(next) < 0) {
                            next = provider;
                        }
                    }
                }
                current = next;
            }

            if(current == null) {
                return remaining.to_string(n => n, " -> ");
            }

            var cycle = new Series<string>();
            var started = false;
            foreach(var name in path) {
                if(name == current) {
                    started = true;
                }
                if(started) {
                    cycle.add(name);
                }
            }
            cycle.add(current);
            return cycle.to_string(n => n, " -> ");
        }
    }

    public class PackageSet : HashSet<AbstractPackage> {

        public void add_from_file(string path) throws Error {
            add(new AbstractPackage.from_package(path));
        }

        public void add_from_repo(Repository repository, RepositoryListingEntry entry) throws Error {
            add(new AbstractPackage.from_repository(repository, entry));
        }

        /**
         * Whether every package's required phases hold: flat phases need all
         * refs present (provided by the set or locally), grouped phases need
         * one fully-satisfied group.
         */
        public bool is_satisfied(ResourceFinder local_resource_finder) {
            return all(package => {
                foreach(var phase_name in new string[] { "manage", "build", "runtime" }) {
                    var phase = manifest_phase_of(package.manifest, phase_name);
                    if(!phase.is_satisfied(d => provides(d) || local_resource_finder.has_resource(d))) {
                        return false;
                    }
                }
                return true;
            });
        }

        public bool provides(ResourceRef resource) {
            return any(p => p.manifest.satisfies(resource));
        }

        private static DependencyPhase manifest_phase_of(Manifest manifest, string phase_name) {
            switch(phase_name) {
                case "manage":
                    return manifest.dependencies.manage;
                case "build":
                    return manifest.dependencies.build;
                case "runtime":
                    return manifest.dependencies.runtime;
                default:
                    assert_not_reached();
            }
        }

    }

    public class AbstractPackage {

        public Manifest manifest { get; set; }
        public Repository? repository { get; set; }
        public RepositoryListingEntry? repository_entry { get; set; }
        public string? package_path { get; set; }
        public CachedPackage? cached_package { get; set; }

        public AbstractPackage.from_package(string path) throws Error {
            package_path = path;
            manifest = new Manifest.from_package(path);
        }

        public AbstractPackage.from_repository(Repository repository, RepositoryListingEntry entry) {
            this.repository = repository;
            this.repository_entry = entry;
            this.manifest = entry.manifest;
        }

        /** Wraps an already-parsed {@link Manifest} with no repository or package source behind it; used by tooling and tests. */
        public AbstractPackage.from_manifest(Manifest manifest) {
            this.manifest = manifest;
        }

    }

}