usm/src/lib/Transaction.vala

using Invercargill;
using Invercargill.DataStructures;

namespace Usm {

    public class Transaction {

        public Paths paths { get; set; }
        public ResourceFinder resource_finder { get; set; }

        /**
         * Resources guaranteed present on the destination before the first
         * install lot runs: the system packages chosen during dependency
         * resolution install ahead of the USM transaction (see
         * `Install.run`). The lot scheduler treats them as locally
         * present — without this, every system-provided build dependency
         * (compilers, pkg-config files, ...) looks unmet at planning time,
         * because strategise runs before anything is installed.
         */
        public Set<ResourceRef> preinstalled_resources { get; set; default = new HashSet<ResourceRef>(); }

        public SystemState state { get; set; }
        public Set<CachedPackage> to_install { get; set; default = new HashSet<CachedPackage>(); }
        public Set<CachedPackage> to_remove { get; set; default = new HashSet<CachedPackage>(); }

        /**
         * Optional install order (package names) taken from a
         * {@link ResolutionResult}'s {@link ResolutionResult.install_order};
         * when set, packages build and install in exactly this order.
         */
        public Vector<string>? install_order { get; set; }

        /**
         * Optional removal order (package names) — the reverse of a
         * {@link ResolutionResult}'s install order; when set, removals follow
         * it exactly (dependents before their providers).
         */
        public Vector<string>? remove_order { get; set; }

        /**
         * Manifest names of the packages the user asked for by name (the
         * `usm install` arguments): each install records
         * {@link OriginInformation.explicitly_installed} true for these and
         * false for everything the resolver pulled in as a dependency.
         * Null — every command but `usm install` — marks the whole install
         * set implicit.
         */
        public Vector<string>? explicit_packages { get; set; }

        /**
         * Version downgrades executed by this transaction: each entry
         * removes {@link DowngradeEntry.current}'s installed resources —
         * keeping its state directory for a later downgrade back — and
         * installs {@link DowngradeEntry.target} in its place.
         */
        public Vector<DowngradeEntry> to_downgrade { get; set; default = new Vector<DowngradeEntry>(); }

        /**
         * The system package manager the {@link system_packages} install
         * through, as one native transaction that runs BEFORE the first
         * USM install lot — providing the toolchain and libraries the
         * builds depend on. Null (or an empty {@link system_packages})
         * makes the transaction USM-only, exactly as before.
         */
        public SystemPackageManager? system_package_manager { get; set; }

        /**
         * System (native) packages chosen during dependency resolution
         * that this transaction installs itself, each as one
         * {@link TransactionTask.INSTALLING_SYSTEM} action: they appear
         * in the plan preview, drive the shared progress display, and
         * count towards the transaction's overall progress. The lot
         * scheduler also treats their resources as present (see
         * {@link preinstalled_resources}).
         */
        public Vector<SystemPackageCandidate> system_packages { get; set; default = new Vector<SystemPackageCandidate>(); }

        /**
         * The material system install set — every native package the
         * manager would install for {@link system_packages}, chosen
         * names plus every dependency of a dependency, in the manager's
         * own transaction order (from
         * {@link SystemPackageManager.plan_install}). Each name in this
         * list is one {@link TransactionTask.INSTALLING_SYSTEM} action
         * with its own progress and completion log, so the overall
         * percentage covers the whole native transaction. Empty (helpers
         * without a plan mode) falls back to one action per chosen
         * {@link system_packages} entry.
         */
        public Vector<string> system_install_plan { get; set; default = new Vector<string>(); }

        /**
         * The names of the system-phase actions, plan first: every
         * material package when a plan exists, otherwise the chosen
         * candidates alone.
         */
        private Vector<string> effective_system_names() {
            var names = new Vector<string>();
            if(system_install_plan.length > 0) {
                foreach(var name in system_install_plan) {
                    names.add(name);
                }
                return names;
            }
            foreach(var candidate in system_packages) {
                names.add(candidate.name);
            }
            return names;
        }

        public signal void progress_updated(TransactionTask task_type, string subject, uint current_task, uint total_tasks, float task_progress);

        private uint task_count = 0;
        private uint current_task = 0;
        private string current_subject = "transaction";
        private TransactionTask current_task_type = TransactionTask.STRATEGISING;

        /**
         * Active rollback journal, non-null only for the duration of
         * {@link run} and {@link rebuild_package}: every install and
         * remove records its changes before executing them so a failure
         * can be undone in reverse (see {@link Journal}).
         */
        private Journal? journal = null;

        /**
         * Working sets computed by {@link strategise}: {@link to_install}
         * plus downgrade targets, and {@link to_remove} plus downgrade
         * currents — the whole transaction runs against these.
         */
        private Set<CachedPackage> planned_install = new HashSet<CachedPackage>();
        private Set<CachedPackage> planned_removal = new HashSet<CachedPackage>();
        /** Downgrade targets (installed with {@link InstallType.DOWNGRADE}) and currents (removed with {@link RemoveType.DOWNGRADE}). */
        private Set<CachedPackage> downgrade_targets = new HashSet<CachedPackage>();
        private Set<CachedPackage> downgrade_currents = new HashSet<CachedPackage>();
        /** Removals whose package name this transaction reinstalls — update removals ({@link RemoveType.UPGRADE}). */
        private Set<CachedPackage> upgrade_removals = new HashSet<CachedPackage>();

        /**
         * Lots computed by {@link strategise}: each lot builds, tests and
         * installs together, and lots run in dependency order. A package
         * joins a lot only when every BUILD-phase ref is already present or
         * provided by an earlier lot, so downstream builds always see the
         * upstream package's installed `pc:`/`vapi:` artifacts.
         */
        public Vector<Vector<CachedPackage>> install_lots { get; private set; }

        /** Removal order computed by {@link strategise}: dependents before their providers. */
        public Vector<CachedPackage> removal_order { get; private set; }

        /**
         * Rebuild entries planned by {@link strategise} for packages in
         * {@link to_install} flagged
         * {@link ManifestFlag.REBUILD_DEPENDANTS}: each entry rebuilds its
         * installed {@link RebuildEntry.package} — same CachedPackage,
         * same version, same state path — through the standard pipeline,
         * tagged {@link TransactionTask.REBUILDING} in progress reports.
         * Empty when nothing is flagged or {@link state} is unset.
         */
        public Vector<RebuildEntry> rebuilds { get; private set; default = new Vector<RebuildEntry>(); }

        /**
         * Emitted when a Ctrl+C lands mid-transaction: a true return
         * keeps the transaction going (the interrupted operation
         * re-runs), false rolls the journaled transaction back. No
         * handler is connected by the CLI — a Ctrl+C always rolls back
         * — leaving this as the programmatic opt-out for embedders.
         */
        public signal bool interrupt_decided(string subject, string phase_verb);

        public void run() throws TransactionError {

            // 1. Verify the transaction is valid
            strategise();

            journal = new Journal(journal_backup_root());
            TransactionInterrupt.install();
            try {
                journal.begin();

                var all_packages = planned_removal.concat(planned_install);
                var rebuild_packages = rebuilds.select<CachedPackage>(r => r.package).to_vector();

                // 2. System packages install first, as one native
                // transaction, providing the toolchain and libraries the
                // builds depend on
                install_system_packages();

                // 3. Unpack packages
                do_for(all_packages, unpack_package, TransactionTask.UNPACKING);
                do_for(rebuild_packages, unpack_package, TransactionTask.REBUILDING);

                // 4. Remove packages
                do_for(removal_order, remove_package, TransactionTask.REMOVING);

                foreach (var lot in install_lots) {
                    // 5. Build packages
                    do_for(lot, build_package, TransactionTask.BUILDING);

                    // 6. Test packages
                    do_for(lot, test_package, TransactionTask.TESTING);

                    // 7. Install packages
                    do_for(lot, install_package, TransactionTask.INSTALLING);
                }

                // Rebuilds run the same pipeline once every flagged package is
                // installed, so dependants build against the fresh artifacts
                do_for(rebuild_packages, unpack_package, TransactionTask.UNPACKING);
                do_for(rebuild_packages, build_package, TransactionTask.REBUILDING);
                do_for(rebuild_packages, test_package, TransactionTask.TESTING);
                do_for(rebuild_packages, install_package, TransactionTask.INSTALLING);

                // 8. Clean up
                do_for(all_packages, cleanup_package, TransactionTask.CLEANING_UP);
                do_for(rebuild_packages, cleanup_package, TransactionTask.CLEANING_UP);

                journal.finish();
            }
            catch(TransactionError e) {
                rollback_and_report();
                throw e;
            }
            catch(Error e) {
                rollback_and_report();
                throw new TransactionError.UNKNOWN_ERROR(@"Error running transaction: $(e.message)");
            }
            finally {
                TransactionInterrupt.restore();
                journal = null;
            }
        }

        /**
         * Rebuilds one already-installed package through the standard
         * pipeline — build-cache restore, clean-retry on failure,
         * reinstall of its resources — tagged
         * {@link TransactionTask.REBUILDING} throughout; the `usm
         * rebuild` entry point. No confirmation is needed: nothing
         * installed changes version.
         */
        public void rebuild_package(CachedPackage package) throws TransactionError {
            var packages = new Vector<CachedPackage>();
            packages.add(package);

            task_count = 5;
            current_task = 0;
            current_subject = package.package_name;
            current_task_type = TransactionTask.REBUILDING;

            journal = new Journal(journal_backup_root());
            TransactionInterrupt.install();
            try {
                journal.begin();

                do_for(packages, unpack_package, TransactionTask.UNPACKING);
                do_for(packages, build_package, TransactionTask.REBUILDING);
                do_for(packages, test_package, TransactionTask.TESTING);
                do_for(packages, install_package, TransactionTask.INSTALLING);
                do_for(packages, cleanup_package, TransactionTask.CLEANING_UP);

                journal.finish();
            }
            catch(TransactionError e) {
                rollback_and_report();
                throw e;
            }
            catch(Error e) {
                rollback_and_report();
                throw new TransactionError.UNKNOWN_ERROR(@"Error rebuilding package $(package.package_name): $(e.message)");
            }
            finally {
                TransactionInterrupt.restore();
                journal = null;
            }
        }

        /**
         * Rolls the active journal back after a failure and prints what
         * was undone; a rollback failure is reported by the journal
         * itself and never masks the original error.
         */
        private void rollback_and_report() {
            if(journal == null) {
                return;
            }
            journal.rollback();
            printerr(journal.describe_rollback() + "\n");
        }

        /**
         * Installs the system phase through {@link
         * system_package_manager} as the transaction's first actions:
         * one native transaction whose streaming events drive one
         * {@link TransactionTask.INSTALLING_SYSTEM} action per package
         * of {@link effective_system_names} — in the plan preview, on
         * the shared progress display and in the overall task count.
         *
         * Action slots are claimed IN COMPLETION ORDER, never by the
         * helper's own positions or the plan's ordering: downloads and
         * the rpm transaction each stream `package` events in their own
         * order, neither matching the plan, so a fixed mapping would
         * hand the display out-of-order indexes that the stale-report
         * guard (correctly) drops. Completions are strictly sequential
         * in the native transaction, so each one claims the next slot
         * and logs; a fraction event for a package that has not yet
         * completed draws on the next slot to be claimed — the running
         * package — without claiming it. Names outside the plan (a
         * differently-resolved run-time transaction) share the bound of
         * {@link effective_system_names}.length slots and fold silently
         * once the bound is reached.
         *
         * A native package cannot be rolled back by the journal; on
         * failure the thrown {@link TransactionError.INSTALL_ERROR} still
         * unwinds and rolls back every USM action (none has run yet). A
         * no-op when no manager is set or the package list is empty.
         */
        private void install_system_packages() throws TransactionError {
            var action_names = effective_system_names();
            if(system_package_manager == null || (system_packages.length == 0 && system_install_plan.length == 0)) {
                return;
            }

            var planned = new HashSet<string>();
            foreach(var name in action_names) {
                planned.add(name);
            }

            var install_names = new Vector<string>();
            foreach(var candidate in system_packages) {
                if(!install_names.any(n => n == candidate.name)) {
                    install_names.add(candidate.name);
                }
            }

            string failure = "";
            var claimed_slot = new Dictionary<string, int>();
            int next_slot = 0;
            var loop = new MainLoop();
            system_package_manager.install.begin(install_names, event => {
                switch(event.event_type) {
                    case SystemInstallEventType.BEGIN:
                        break;
                    case SystemInstallEventType.PACKAGE:
                        if(event.name != null && next_slot < action_names.length) {
                            int slot;
                            if(!claimed_slot.try_get(event.name, out slot)) {
                                // The running package targets the slot the
                                // next completion will claim
                                slot = next_slot;
                            }
                            begin_action(TransactionTask.INSTALLING_SYSTEM, event.name, 1 + slot);
                            report_progress(TransactionTask.INSTALLING_SYSTEM, (float)event.progress);
                        }
                        break;
                    case SystemInstallEventType.PACKAGE_COMPLETE:
                        if(event.name != null && next_slot < action_names.length) {
                            int slot;
                            if(!claimed_slot.try_get(event.name, out slot)) {
                                slot = next_slot++;
                                claimed_slot.set(event.name, slot);
                            }
                            begin_action(TransactionTask.INSTALLING_SYSTEM, event.name, 1 + slot);
                            report_progress(TransactionTask.INSTALLING_SYSTEM, 1.0f);
                        }
                        break;
                    case SystemInstallEventType.COMPLETE:
                        break;
                    case SystemInstallEventType.ERROR:
                        failure = event.message ?? "unknown error";
                        break;
                }
            }, (obj, res) => {
                try {
                    if(!system_package_manager.install.end(res)) {
                        failure = failure.length > 0 ? failure : "the system package manager reported a failure";
                    }
                }
                catch(Error e) {
                    failure = e.message;
                }
                loop.quit();
            });
            loop.run();

            // Whatever the helper streamed, the USM actions start right
            // after the last system action's slot
            begin_action(TransactionTask.STRATEGISING, "transaction", 1 + action_names.length);

            if(failure.length > 0) {
                throw new TransactionError.INSTALL_ERROR(@"System package installation failed: $failure");
            }
        }

        /**
         * `<destination>/<local-state>/usm/backup` — the journal's home,
         * rooted like every other destination this transaction writes
         * (`/var/usm/backup` on an unredirected system).
         */
        private string journal_backup_root() {
            return Path.build_filename(paths.destination, paths.local_state, "usm", "backup");
        }

        private string previous_key = "";
        public void print_progress(TransactionTask task_type, string subject, uint current_task, uint total_tasks, float task_progress) {
            var verb = task_type.get_verb();
            verb = verb[0].toupper().to_string() + verb.substring(1);
            var percent = (int)(task_progress * 100.0f);

            var key = @"$(task_type.get_verb())_$(subject)_$current_task";
            var prefix = previous_key == key ? "\x1b[1F\x1b[2K" : "";
            previous_key = key;

            printerr(@"$prefix[$(current_task+1)/$total_tasks] $verb $subject ($percent%)\n");
        }

        public void print_progress_simple(TransactionTask task_type, string subject, uint current_task, uint total_tasks, float task_progress) {
            var verb = task_type.get_verb();
            verb = verb[0].toupper().to_string() + verb.substring(1);
            var percent = (int)(task_progress * 100.0f);
            printerr(@"[$(current_task+1)/$total_tasks] $verb $subject ($percent%)\n");
        }

        public void strategise() throws TransactionError {
            // Reset the task counters — strategise may be called twice
            // (once for the summary/confirm, once inside run())
            current_task = 0;
            task_count = 0;

            planned_install = new HashSet<CachedPackage>();
            planned_install.union_with(to_install);
            planned_removal = new HashSet<CachedPackage>();
            planned_removal.union_with(to_remove);
            downgrade_targets = new HashSet<CachedPackage>();
            downgrade_currents = new HashSet<CachedPackage>();
            foreach(var entry in to_downgrade) {
                planned_install.add(entry.target);
                downgrade_targets.add(entry.target);
                planned_removal.add(entry.current);
                downgrade_currents.add(entry.current);
            }

            // A removal whose package name this transaction reinstalls is
            // an update removal, not a final one
            upgrade_removals = new HashSet<CachedPackage>();
            try {
                var install_names = new HashSet<string>();
                foreach(var package in planned_install) {
                    install_names.add(package.get_manifest().name);
                }
                foreach(var package in planned_removal) {
                    if(install_names.contains(package.get_manifest().name)) {
                        upgrade_removals.add(package);
                    }
                }
            }
            catch(Error e) {
                throw new TransactionError.UNKNOWN_ERROR(@"Failed to read manifest while planning removals: $(e.message)");
            }

            task_count = (planned_install.count() * 5) + (planned_removal.count() * 3) + effective_system_names().length + 1;
            uint strategise_worst_case_task_count = (planned_removal.count() * planned_removal.count()) + (planned_install.count() * planned_install.count()) + effective_system_names().length;
            uint strategise_current_task = 0;

            report_progress(TransactionTask.STRATEGISING, 0.0f);

            // Installation strategy
            install_lots = new Vector<Vector<CachedPackage>>();
            var touched = new HashSet<CachedPackage>();
            var installed_by_earlier_lots = new HashSet<ResourceRef>();
            var ordered_install = ordered_by_names(planned_install, install_order);
            var round = 0;
            while(true) {
                strategise_current_task = round * planned_install.count();
                var lot = new Vector<CachedPackage>();
                var installed_by_this_lot = new HashSet<ResourceRef>();
                var remaining = ordered_install.exclude(touched);
                if(remaining.count() == 0) {
                    break;
                }

                foreach (var package in ordered_install.exclude(touched)) {
                    report_progress(TransactionTask.STRATEGISING, (float)strategise_current_task / (float)strategise_worst_case_task_count);
                    try {
                        var manifest = package.get_manifest();
                        // Resources provided by packages this transaction
                        // REMOVES are gone before the first build runs —
                        // stale on disk at planning time, they satisfy
                        // nothing (an update pair's replacement counts only
                        // from the lot that installs it, so the dependency
                        // lands in an earlier lot and the dependent builds
                        // against the fresh artifact)
                        PredicateDelegate<ResourceRef> removed_by_plan = d => planned_removal.any(p => {
                            try {
                                return p.get_manifest().satisfies(d);
                            }
                            catch(Error e) {
                                return false;
                            }
                        });
                        // Build-phase refs must be satisfied by resources
                        // that are in place when this package builds:
                        // either installed by an EARLIER lot (the
                        // replacement of an updated pair — this dominates,
                        // the removal is already undone by then) or
                        // present on the destination and NOT provided by
                        // a package this transaction removes (those go
                        // away before the first build, so the stale
                        // on-disk state satisfies nothing). A same-lot
                        // provide is not installed yet and defers the
                        // package to the next lot.
                        PredicateDelegate<ResourceRef> buildtime_satisfied = d =>
                            installed_by_earlier_lots.any(r => d.satisfied_by(r))
                            || (!removed_by_plan(d) && (
                                resource_finder.has_resource(d)
                                || preinstalled_resources.any(r => d.satisfied_by(r))));
                        // Manage-phase executables run at install time,
                        // when everything this lot has already admitted
                        // (in topological order) is installed — the same
                        // dominance and poison rules as the build phase
                        PredicateDelegate<ResourceRef> installtime_satisfied = d =>
                            installed_by_earlier_lots.any(r => d.satisfied_by(r))
                            || installed_by_this_lot.any(r => d.satisfied_by(r))
                            || (!removed_by_plan(d) && (
                                resource_finder.has_resource(d)
                                || preinstalled_resources.any(r => d.satisfied_by(r))));
                        if(manifest.dependencies.manage.is_satisfied(installtime_satisfied) &&
                                manifest.dependencies.build.is_satisfied(buildtime_satisfied)) {
                            lot.add(package);
                            touched.add(package);
                            installed_by_this_lot.union_with(manifest.effective_provides());
                        }
                        strategise_current_task++;
                    }
                    catch(Error e) {
                        throw new TransactionError.UNKNOWN_ERROR(@"Failed to read manifest for package \"$(package.package_name)\": $(e.message)");
                    }
                }

                if(lot.count() == 0) {
                    throw new TransactionError.INVALID_TRANSACTION(
                        describe_install_deadlock(ordered_install.exclude(touched), installed_by_earlier_lots, planned_install)
                    );
                }

                installed_by_earlier_lots.union_with(installed_by_this_lot);
                install_lots.add(lot);
                round++;
            }
            var current_task_baseline = (planned_install.count() * planned_install.count());
            strategise_current_task = current_task_baseline;
            report_progress(TransactionTask.STRATEGISING, (float)strategise_current_task / (float)strategise_worst_case_task_count);

            // Removal strategy
            removal_order = new Vector<CachedPackage>();
            if(remove_order != null) {
                removal_order = ordered_by_names(planned_removal, remove_order);
            }
            else {
                Set<CachedPackageManifest> remaining_to_remove;
                try {
                    remaining_to_remove = planned_removal
                        .attempt_select<CachedPackageManifest>(p => new CachedPackageManifest(p))
                        .to_set();

                }
                catch(Error e) {
                    throw new TransactionError.UNKNOWN_ERROR(@"Failed to read manifest: $(e.message)");
                }

                round = 0;
                while(true) {
                    strategise_current_task = current_task_baseline + (round * planned_removal.count());
                    if(remaining_to_remove.count() == 0) {
                        break;
                    }

                    var removed_this_round = false;
                    foreach (var package in remaining_to_remove.sort((a, b) => a.package.package_name.collate(b.package.package_name))) {
                        report_progress(TransactionTask.STRATEGISING, (float)strategise_current_task / (float)strategise_worst_case_task_count);
                        if(remaining_to_remove.no(p => p.manifest.dependencies.manage.all_refs().any(d => package.manifest.satisfies(d)))) {
                            removal_order.add(package.package);
                            remaining_to_remove.remove(package);
                            strategise_current_task++;
                            round++;
                            removed_this_round = true;
                            break;
                        }
                        strategise_current_task++;
                    }

                    if(!removed_this_round) {
                        throw new TransactionError.INVALID_TRANSACTION(describe_removal_deadlock(remaining_to_remove));
                    }
                }
            }

            plan_rebuilds();
            task_count += rebuilds.length * 5;

            report_progress(TransactionTask.STRATEGISING, 1.0f);
            current_task++;
        }

        /**
         * Whether a resource is satisfiable without the packages this
         * explainer deals with: present on the destination, provided by a
         * preinstalled (system) package, or provided by a lot scheduled
         * before the stall.
         */

        /**
         * Explains why the install lot scheduler stalled: for every
         * unscheduled package, each blocking dependency is reported with
         * its exact cause — unmet (nothing present or planned provides it)
         * or cyclical (only packages that are themselves unscheduled
         * provide it) — naming the providers, the phase carrying the ref,
         * and the lot rule that applies (build-phase refs must come from
         * an EARLIER lot; manage-phase refs may share the lot).
         */
        private string describe_install_deadlock(Enumerable<CachedPackage> stuck, Set<ResourceRef> installed_by_earlier_lots, Set<CachedPackage> planned_install) {
            var stuck_sorted = stuck.sort((a, b) => a.package_name.collate(b.package_name)).to_vector();

            // The same satisfier the scheduler used, poison included: a
            // resource provided by a package this transaction removes is
            // going away before the first build, so explaining a stall
            // against the stale on-disk state would clear every blocker
            // and produce a dead diagnosis
            PredicateDelegate<ResourceRef> removed_by_plan = r => planned_removal.any(p => {
                try {
                    return p.get_manifest().satisfies(r);
                }
                catch(Error e) {
                    return false;
                }
            });
            PredicateDelegate<ResourceRef> satisfier = r =>
                installed_by_earlier_lots.any(p => r.satisfied_by(p))
                || (!removed_by_plan(r) && (
                    resource_finder.has_resource(r)
                    || preinstalled_resources.any(p => r.satisfied_by(p))));

            var builder = new StringBuilder();
            builder.append_printf("Could not build a transaction strategy: %u package(s) could not be scheduled for installation", stuck_sorted.length);
            if(preinstalled_resources.any()) {
                builder.append_printf(" (%u resource(s) already planned via system packages are counted as present)", preinstalled_resources.count());
            }
            builder.append(":\n");
            foreach(var package in stuck_sorted) {
                builder.append_printf("  %s:\n", package.package_name);
                Manifest manifest;
                try {
                    manifest = package.get_manifest();
                }
                catch(Error e) {
                    builder.append_printf("    (manifest could not be read: %s)\n", e.message);
                    continue;
                }
                append_blocking_refs(builder, manifest.dependencies.manage, "manage", satisfier, removed_by_plan, planned_install, package);
                append_blocking_refs(builder, manifest.dependencies.build, "build", satisfier, removed_by_plan, planned_install, package);
            }
            return builder.str.chomp();
        }

        /**
         * Appends the refs of one dependency phase that nothing schedulable
         * provides. Flat phases list their refs directly; grouped phases
         * report every candidate group that is not viable.
         */
        private void append_blocking_refs(StringBuilder builder, DependencyPhase phase, string phase_name, PredicateDelegate<ResourceRef> satisfier, PredicateDelegate<ResourceRef> removed_by_plan, Set<CachedPackage> planned_install, CachedPackage package) {
            if(phase == null) {
                return;
            }
            if(!phase.is_grouped) {
                foreach(var resource in phase.ordered_required()) {
                    if(!satisfier(resource)) {
                        append_blocking_ref(builder, phase_name, resource, removed_by_plan, planned_install, package);
                    }
                }
                return;
            }
            var groups = phase.ordered_groups();
            for(uint index = 0; index < groups.length; index++) {
                var blocking = groups[index].where(r => !satisfier(r)).to_vector();
                if(blocking.length == 0) {
                    return;
                }
                builder.append_printf("    [%s phase, candidate group %u of %u:]\n", phase_name, index + 1, groups.length);
                foreach(var resource in blocking) {
                    append_blocking_ref(builder, phase_name, resource, removed_by_plan, planned_install, package);
                }
            }
        }

        /**
         * Appends one blocking ref with its exact cause and, when other
         * transaction members provide it, their names — distinguishing
         * unmet dependencies from dependency cycles.
         */
        private void append_blocking_ref(StringBuilder builder, string phase_name, ResourceRef resource, PredicateDelegate<ResourceRef> removed_by_plan, Set<CachedPackage> planned_install, CachedPackage package) {
            var providers = new Vector<string>();
            foreach(var candidate in planned_install) {
                if(candidate == package) {
                    continue;
                }
                try {
                    if(candidate.get_manifest().satisfies(resource)) {
                        providers.add(candidate.package_name);
                    }
                }
                catch(Error e) {
                    builder.append_printf("    %s (%s phase): provider check failed for \"%s\": %s\n", resource.to_string(), phase_name, candidate.package_name, e.message);
                }
            }
            if(providers.length == 0) {
                if(removed_by_plan(resource)) {
                    builder.append_printf(
                        "    %s (%s phase) is going away: a package this transaction removes currently provides it, and nothing in this transaction replaces it\n",
                        resource.to_string(), phase_name
                    );
                    return;
                }
                builder.append_printf("    %s (%s phase) is unmet: it is not present on this system, no planned system package provides it, and no package in this transaction provides it\n", resource.to_string(), phase_name);
                return;
            }
            var self_cycle = false;
            try {
                self_cycle = package.get_manifest().satisfies(resource);
            }
            catch(Error e) {
            }
            if(self_cycle) {
                providers.add(@"$(package.package_name) (itself)");
            }
            builder.append_printf(
                "    %s (%s phase) is part of a dependency cycle: only %s provide%s it, and none of them can be scheduled before \"%s\"\n",
                resource.to_string(), phase_name, providers.to_string(p => p, ", "), providers.length == 1 ? "s" : "", package.package_name
            );
        }

        /**
         * Explains why no remaining package can be removed: a package is
         * stuck when another still-to-be-removed package's manage-phase
         * dependencies are satisfied by its provides, so each blocking
         * (remover, blocked-by, ref) pair is reported — a pure cycle when
         * every remaining package is blocked.
         */
        private string describe_removal_deadlock(Set<CachedPackageManifest> remaining) {
            var builder = new StringBuilder();
            builder.append_printf("Could not build a transaction strategy: %u package(s) could not be scheduled for removal:\n", remaining.count());
            foreach(var entry in remaining.sort((a, b) => a.package.package_name.collate(b.package.package_name))) {
                var blockers = new Vector<string>();
                foreach(var other in remaining) {
                    if(other == entry) {
                        continue;
                    }
                    foreach(var dependency in other.manifest.dependencies.manage.all_refs()) {
                        if(entry.manifest.satisfies(dependency)) {
                            blockers.add(@"\"$(other.package.package_name)\" still needs $(dependency.to_string()) (manage phase)");
                            break;
                        }
                    }
                }
                if(blockers.length == 0) {
                    builder.append_printf("  %s: no remaining package depends on it, but nothing else could be scheduled either\n", entry.package.package_name);
                }
                else {
                    builder.append_printf("  %s: %s\n", entry.package.package_name, blockers.to_string(b => b, "; "));
                }
            }
            return builder.str.chomp();
        }

        /**
         * Plans rebuildDependants rebuilds: every package in
         * {@link to_install} flagged
         * {@link ManifestFlag.REBUILD_DEPENDANTS} names its installed
         * dependants via {@link SystemState.find_dependant_names}, and each
         * one neither installed nor removed by this transaction rebuilds
         * exactly once — dependants the transaction already handles are
         * skipped, and two flagged packages sharing a dependant rebuild it
         * once only. Without a {@link state} there is nothing to scan.
         */
        private void plan_rebuilds() throws TransactionError {
            rebuilds = new Vector<RebuildEntry>();
            if(state == null) {
                return;
            }

            try {
                var installed_by_name = new Dictionary<string, CachedPackage>();
                foreach(var installed in state.get_installed_packages()) {
                    // Resolve through the installed symlink so a rebuild
                    // carries the cache path: reinstalling through the
                    // installed path itself would make mark_installed
                    // relink the symlink onto itself
                    var info = File.new_for_path(installed.state_path).query_info(FileAttribute.STANDARD_SYMLINK_TARGET, FileQueryInfoFlags.NOFOLLOW_SYMLINKS);
                    var target = info.get_symlink_target();
                    installed_by_name.set(installed.package_name, target != null ? new CachedPackage(target) : installed);
                }

                var planned = new HashSet<string>();
                foreach(var package in planned_install) {
                    planned.add(package.get_manifest().name);
                }
                foreach(var package in planned_removal) {
                    planned.add(package.get_manifest().name);
                }

                foreach(var package in planned_install) {
                    var manifest = package.get_manifest();
                    if(manifest.flags == null || !manifest.flags.has(ManifestFlag.REBUILD_DEPENDANTS)) {
                        continue;
                    }
                    foreach(var name in state.find_dependant_names(package)) {
                        CachedPackage dependant;
                        if(!installed_by_name.try_get(name, out dependant)) {
                            continue;
                        }
                        var dependant_name = dependant.get_manifest().name;
                        if(planned.has(dependant_name)) {
                            continue;
                        }
                        planned.add(dependant_name);
                        rebuilds.add(new RebuildEntry() {
                            package = dependant,
                            trigger = package
                        });
                    }
                }
            }
            catch(Error e) {
                throw new TransactionError.UNKNOWN_ERROR(@"Failed to plan dependant rebuilds: $(e.message)");
            }
        }

        /**
         * Orders a transaction package set by the given manifest-name order
         * (from a {@link ResolutionResult}); names with no package in the set
         * are skipped (for example supplied cache packages filtered out by
         * the caller). Without an order the set is sorted by name for
         * determinism. Throws when an order covers none of a package's set
         * entries — every package must be covered.
         */
        private Vector<CachedPackage> ordered_by_names(Set<CachedPackage> packages, Vector<string>? names) throws TransactionError {
            if(names == null) {
                return packages.sort((a, b) => a.package_name.collate(b.package_name)).to_vector();
            }

            var by_name = new Dictionary<string, CachedPackage>();
            foreach(var package in packages) {
                try {
                    by_name.set(package.get_manifest().name, package);
                }
                catch(Error e) {
                    throw new TransactionError.UNKNOWN_ERROR(@"Failed to read manifest for package \"$(package.package_name)\": $(e.message)");
                }
            }

            var ordered = new Vector<CachedPackage>();
            var covered = new HashSet<CachedPackage>();
            foreach(var name in names) {
                CachedPackage package;
                if(by_name.try_get(name, out package)) {
                    ordered.add(package);
                    covered.add(package);
                }
            }

            var uncovered_names = packages.exclude(covered).to_string(p => p.package_name, ", ");
            if(uncovered_names.length > 0) {
                throw new TransactionError.INVALID_TRANSACTION(@"The supplied package order does not cover: $(uncovered_names)");
            }
            return ordered;
        }

        private delegate void PackageDelegate(CachedPackage package) throws Error;

        /**
         * Serialises progress reporting: the ninja progress reader
         * thread of a `ninjaStyleProgress` build emits fractions
         * concurrently with the main thread advancing between actions,
         * so the reporting fields and the {@link progress_updated}
         * emissions (and the display behind them) must never interleave.
         */
        private Object progress_lock = new Object();

        /**
         * Moves the action cursor under {@link progress_lock}: the next
         * {@link report_progress} carries this task, subject and index.
         */
        private void begin_action(TransactionTask task, string subject, uint index) {
            lock(progress_lock) {
                current_task_type = task;
                current_subject = subject;
                current_task = index;
            }
        }

        private void do_for(Enumerable<CachedPackage> packages, PackageDelegate func, TransactionTask task_type) throws TransactionError {
            foreach (var package in packages) {
                // A Ctrl+C that arrived between operations resolves before
                // this one starts: keep going (clearing the flag) or roll
                // the transaction back
                if(TransactionInterrupt.requested && !resolve_interrupt(package.package_name, task_type)) {
                    throw new TransactionError.INTERRUPTED(@"Interrupted before $(task_type.get_verb()) $(package.package_name)");
                }
                while(true) {
                    try {
                        begin_action(task_type, package.package_name, current_task);
                        report_progress(task_type, 0.0f);
                        func(package);
                        lock(progress_lock) {
                            current_task++;
                        }
                        break;
                    }
                    catch (TransactionError e) {
                        // The operation failed with a Ctrl+C pending — the
                        // terminal signalled the child too. Ask: roll back,
                        // or clear the flag and re-run this operation
                        if(TransactionInterrupt.requested && resolve_interrupt(package.package_name, task_type)) {
                            continue;
                        }
                        throw e;
                    }
                    catch(Error e) {
                        if(TransactionInterrupt.requested && resolve_interrupt(package.package_name, task_type)) {
                            continue;
                        }
                        throw new TransactionError.UNKNOWN_ERROR(@"Error $(task_type.get_verb()) package $(package.package_name): $(e.message)");
                    }
                }
            }
        }

        /**
         * Resolves a pending interrupt for {@link subject} in the phase
         * {@link verb}: emits {@link interrupt_decided}. A "keep going"
         * answer clears the flag so the retried operation runs
         * uninterrupted; a rollback answer (or no handler — the signal's
         * default) leaves it set and the caller unwinds to the journaled
         * rollback.
         */
        private bool resolve_interrupt(string subject, TransactionTask task_type) {
            bool keep_going = interrupt_decided(subject, task_type.get_verb());
            if(keep_going) {
                TransactionInterrupt.requested = false;
            }
            return keep_going;
        }

        private void report_progress(TransactionTask task, float progress) {
            lock(progress_lock) {
                progress_updated(task, current_subject, current_task, task_count, progress);
            }
        }

        /**
         * Reports one progress fraction for an action whose identity was
         * captured when it started — used by the ninja progress reader
         * thread, whose emissions may lag behind the main thread
         * advancing the cursor; carrying the captured identity (instead
         * of reading the live fields) keeps a late emission from
         * masquerading as whatever action happens to be current.
         */
        private void report_action_progress(TransactionTask task, string subject, uint index, float progress) {
            lock(progress_lock) {
                progress_updated(task, subject, index, task_count, progress);
            }
        }

        public void unpack_package(CachedPackage package) throws Error {
            // A clean copy of the sources is all any phase needs — builds,
            // tests, installs and remove scripts all run from the source
            // directory — so removals must not require a build artifact
            // to exist (see {@link cleanup_package})
            package.clean_source();
            report_progress(current_task_type, 0.5f);
            package.get_source_directory((fraction) => {
                report_progress(current_task_type, 0.5f + (fraction * 0.5f));
            });
            report_progress(current_task_type, 1.0f);
        }

        /**
         * Builds a package through the unified build-cache path: an
         * existing build directory or a build archive (restored by
         * {@link CachedPackage.get_build_directory}) makes the build
         * incremental, and a failure atop either is retried once from
         * extracted sources — a stale cache is the likeliest culprit, and
         * the clean-retry error propagates when that also fails. A failure
         * on an already-clean build propagates directly.
         */
        private void build_package(CachedPackage package) throws Error {
            var reused = package.has_build_directory() || package.has_build_archive();
            try {
                attempt_build(package);
            }
            catch(Error e) {
                if(!reused) {
                    throw e;
                }
                package.clean_build_directory();
                package.clean_source();
                package.get_source_directory();
                package.create_build_directory();
                attempt_build(package);
            }
            report_progress(current_task_type, 1.0f);
        }

        /**
         * Runs the package's build script against the unified
         * build-directory path: an existing build tree is reused and a
         * build archive is restored in place (both incremental), and only
         * with neither does a fresh build directory appear — a missing
         * cache is fine, the user may have cleaned it up. The caller owns
         * the clean-retry decision (see {@link build_package}).
         */
        private void attempt_build(CachedPackage package) throws Error {
            // Get source directory, and reuse, restore or create the build directory
            string build_dir;
            if(package.has_build_directory() || package.has_build_archive()) {
                build_dir = package.get_build_directory();
            }
            else {
                build_dir = package.create_build_directory();
            }
            var source_dir = package.get_source_directory();

            // Change directory to sources
            Environment.set_current_dir(source_dir);
            var manifest = new Usm.Manifest.from_file("MANIFEST.usm");

            // The ninja progress reader thread outlives the build process
            // by a moment; snapshot the action's identity so its late
            // emissions carry what they meant when written, never
            // whatever action the cursor has since moved to (see
            // {@link report_action_progress})
            TransactionTask action_task = current_task_type;
            string action_subject = current_subject;
            uint action_index = current_task;
            var build_proc = manifest.run_build(build_dir, paths, SubprocessFlags.STDOUT_SILENCE, (progress) => {
                report_action_progress(action_task, action_subject, action_index, progress);
            });
            build_proc.wait_check();
        }

        private void test_package(CachedPackage package) throws Error {
            var source_dir = package.get_source_directory();
            var build_dir = package.get_build_directory();

            // "cd" into the source directory and read the manifest
            Environment.set_current_dir(source_dir);
            var manifest = new Usm.Manifest.from_file("MANIFEST.usm");

            // Run test process if present
            var test_proc = manifest.run_test(build_dir, SubprocessFlags.STDOUT_SILENCE);
            if(test_proc != null) {
                test_proc.wait_check();
            }
            // A package with no test executable still transitions through
            // the testing task, so completion is reported either way
            report_progress(current_task_type, 1.0f);
        }

        private void remove_package(CachedPackage package) throws Error {
            // Get source and build directories
            var source_dir = package.get_source_directory();

            // "cd" into the source directory and read the manifest
            Environment.set_current_dir(source_dir);
            var manifest = new Usm.Manifest.from_file("MANIFEST.usm");

            // A downgrade removal keeps the state directory for the way
            // back; an update removal is followed by a reinstall; anything
            // else is final
            var removal_type = downgrade_currents.has(package)
                ? RemoveType.DOWNGRADE
                : upgrade_removals.has(package) ? RemoveType.UPGRADE : RemoveType.FINAL;

            // Journal before anything is deleted: every existing resource
            // file is backed up and the installed mark's target recorded,
            // so a later failure puts the package back exactly as it was
            var files_removed = manifest.report_remove_resources(paths);
            journal.entry_remove(package, files_removed.to_array(), state.installed_mark_path(package), state.read_installed_target(package));
            foreach(var path in files_removed) {
                journal.backup_file(path, package.package_name);
            }

            // Run remove process if present
            var build_proc = manifest.run_remove(removal_type, SubprocessFlags.STDOUT_SILENCE);
            if(build_proc != null)
                build_proc.wait_check();

            manifest.remove_resources( paths, (r, cr, tr, f) => report_progress(current_task_type, ((float)cr + (float)f) / (float)tr));

            state.unmark_installed(package);
            journal.complete(package.package_name);
        }

        private void install_package(CachedPackage package) throws Error {
            var source_dir = package.get_source_directory();
            var build_dir = package.get_build_directory();

            // "cd" into the source directory and read the manifest
            Environment.set_current_dir(source_dir);
            var manifest = new Usm.Manifest.from_file("MANIFEST.usm");
            report_progress(current_task_type, 0.0f);

            string? install_dir = null;
            // Downgrade targets install over their current version rather
            // than fresh
            var install_type = downgrade_targets.has(package) ? InstallType.DOWNGRADE : InstallType.FRESH;

            // Journal before anything changes on disk: the destination
            // set comes from the manifest's provides, every file about to
            // be overwritten is backed up, and the installed mark's
            // previous target is recorded so the rollback restores it
            Vector<string> files_created;
            Vector<string> files_overwritten;
            manifest.report_install_resources(paths, out files_created, out files_overwritten);
            journal.entry_install(package, files_created.to_array(), files_overwritten.to_array(),
                state.installed_mark_path(package), state.read_installed_target(package));
            foreach(var path in files_overwritten) {
                journal.backup_file(path, package.package_name);
            }

            // Run install process if present
            if(manifest.executables.install != null) {
                install_dir = package.create_install_directory();
                // Only a ninjaStyleProgress install script streams
                // parseable Installing lines; everything else stays
                // silenced (see {@link Manifest.run_install})
                ProgressDelegate? install_progress = null;
                if(manifest.flags != null && manifest.flags.has(ManifestFlag.NINJA_STYLE_PROGRESS)) {
                    install_progress = (fraction) => {
                        report_progress(current_task_type, fraction);
                    };
                }
                var install_proc = manifest.run_install(build_dir, install_dir, paths, install_type, SubprocessFlags.STDOUT_SILENCE, install_progress);
                install_proc.wait_check();
            }

            // Install the package's resources
            manifest.install_resources(source_dir, build_dir, install_dir, paths, (r, cr, tr, f) => report_progress(current_task_type, ((float)cr + (float)f) / (float)tr));

            // Run post install process if present
            report_progress(current_task_type, 1.0f);
            var post_install_proc = manifest.run_post_install(build_dir, install_type, SubprocessFlags.STDOUT_SILENCE);
            if(post_install_proc != null)
            post_install_proc.wait_check();

            // Update the system state, and cleanup
            state.mark_installed(package);
            record_origin(package, manifest);
            journal.complete(package.package_name);
        }

        /**
         * Writes the package's origin record after install: a record
         * already in this cache directory (a rebuild reinstalls the same
         * one) keeps its provenance and its explicit mark — a rebuild
         * must not demote an explicitly installed package to
         * orphan-removable — while a fresh directory starts a record
         * whose only known field is the mark, set from whether the user
         * named the package in this transaction.
         */
        private void record_origin(CachedPackage package, Manifest manifest) throws Error {
            OriginInformation origin;
            try {
                origin = package.get_origin_information();
            }
            catch(Error e) {
                origin = new OriginInformation();
            }
            var named = explicit_packages != null && explicit_packages.contains(manifest.name);
            origin.explicitly_installed = named || origin.explicitly_installed;
            package.update_origin_information(origin);
        }

        private void cleanup_package(CachedPackage package) throws Error {
            // A package with no build artifact (for example after `usm
            // clean builds`) has nothing to archive; its cache stays as-is
            if(package.has_build_directory() || package.has_build_archive()) {
                package.archive_build((compression) => {
                    report_progress(TransactionTask.CLEANING_UP, compression * 0.25f);
                });
            }
            report_progress(TransactionTask.CLEANING_UP, 0.25f);
            package.clean_source();
            report_progress(TransactionTask.CLEANING_UP, 0.5f);
            package.clean_install();
            report_progress(TransactionTask.CLEANING_UP, 0.75f);
            report_progress(TransactionTask.CLEANING_UP, 1.0f);
        }
    }

    /**
     * One planned rebuildDependants rebuild: {@link package} is the
     * installed {@link CachedPackage} — same version, same state path —
     * that rebuilds through the standard pipeline tagged
     * {@link TransactionTask.REBUILDING}, and {@link trigger} is the
     * flagged package whose install/update pulled it in.
     */
    public class RebuildEntry {
        public CachedPackage package { get; set; }
        public CachedPackage trigger { get; set; }
    }

    /**
     * One planned version downgrade: {@link current} is the installed
     * {@link CachedPackage} whose resources are removed — its state
     * directory is kept, enabling the downgrade back — and {@link target}
     * is the older version installed in its place.
     */
    public class DowngradeEntry {
        public CachedPackage target { get; set; }
        public CachedPackage current { get; set; }
    }

    public enum TransactionTask {
        STRATEGISING,
        UNPACKING,
        BUILDING,
        TESTING,
        REMOVING,
        INSTALLING,
        CLEANING_UP,
        /** Installing one chosen system (native) package; runs ahead of the first USM lot. */
        INSTALLING_SYSTEM,
        /** The rebuildDependants pipeline for an already-installed package (see {@link RebuildEntry}). */
        REBUILDING;

    public string get_verb() {
        switch (this) {
            case STRATEGISING:
                return "preparing a strategy for";
            case UNPACKING:
                return "unpacking";
            case BUILDING:
                return "building";
            case TESTING:
                return "testing";
            case REMOVING:
                return "removing";
            case INSTALLING:
                return "installing";
            case INSTALLING_SYSTEM:
                return "installing system package";
            case CLEANING_UP:
                return "cleaning up";
            case REBUILDING:
                return "rebuilding";
            default:
                assert_not_reached();
        }
    }
    }

    public errordomain TransactionError {

        INVALID_TRANSACTION,
        UNKNOWN_ERROR,
        BUILD_ERROR,
        INSTALL_ERROR,
        /** A Ctrl+C the interrupt decision answered with "roll back". */
        INTERRUPTED
    }


}