src/mplib/resolve.pm

use v5.16;
package mplib::resolve;
use strict;
use warnings FATAL => 'all';
use Exporter 'import';
use mplib::config qw($CFG load load_overlay read_conf set_pkgconf);
use mplib::util qw(note fail ok try_soft bare_name slot_key split_slot_key backend pconf_lookup pconf_section order_manifest delta_or_literal spin_start spin_tick spin_stop);
use mplib::version qw(vercmp ver_satisfies parse_dep_token);
use mplib::portformat qw(resolve_port write_phase_scripts parse_pkg_use enabled_use apply_use_patches resolve_slot USE_NONE);
use mplib::db qw(read_lines read_db write_db write_manifest read_snapshot diff_snapshot find_file_conflict
    write_linkdeps_for linkdeps_users read_subslot_deps write_subslot_deps_for db_lock db_unlock
    canon_lock canon_unlock);
use mplib::hooks qw(port_env_args run_hook);
 
our @EXPORT_OK = qw(
	all_ports find_portdir try_pkgconf pkgconf
	expand_meta expand_set
	effective_deps tag_providers tag_satisfied portpin
	check_static_conflicts soft_conflict_targets reachable_needed_set effective_conflicts held_reason version_held_mismatch masked_reason keyword_reason pconf_lookup
	use_requirement_mismatches apply_use_requirement
	resolve_dep_name resolve_dep pick_provider interactive_pick resolved_db_key
	resolved_slotted_deps dep_slot_prefixes with_sysroot_scope apply_patch_manifest
	record_subslot_dep subslot_changed_targets
	install_pkg remove_pkg reinstall_pkg clean_pkg sync_ports init
	plan_resolution
);
 
# every mutating command needs the working dir/prefix skeleton/ports tree
# to exist first; read-only queries (list/search/info/...) call this too
# so they work identically on a freshly-bootstrapped system.
sub init {
	unless(-d $CFG->{WD})
	{
		system('mkdir', '-p', $CFG->{WD}) == 0 or fail("failed making $CFG->{WD}");
	}
	for my $sub (qw(bin sbin lib libexec include share))
	{
		my $d = "$CFG->{INSTPREFIX}/$sub";
		unless(-d $d)
		{
			system('mkdir', '-p', $d) == 0 or fail("failed making $d");
		}
	}
	# same reasoning as sync_ports' own spinner just below in this file:
	# a tick per repo about to be cloned, not a live animation during
	# any one clone -- git's own clone output takes over the moment it
	# actually starts, same as a pull's.
	spin_start("syncing ports tree...");
	for my $r (@{$CFG->{REPOS}})
	{
		next if -d $r->{dir};
		spin_tick();
		note("repo '$r->{name}' uninitialized, cloning");
		my @cmd = ('git', 'clone');
		push @cmd, '-b', $r->{branch} if defined $r->{branch} && $r->{branch} ne '';
		push @cmd, $r->{url}, $r->{dir};
		system(@cmd) == 0
			or fail("failed cloning $r->{url} to $r->{dir}");
	}
	spin_stop();
	unless(-f $CFG->{DBFILE})
	{
		my $fh;
		open($fh, '>', $CFG->{DBFILE}) or fail("failed making $CFG->{DBFILE}");
		close($fh);
	}
	return;
}
 
my $TAGMAP;
my $ALLPORTS;
 
sub all_ports {
	my @out;
	my %seen;
 
	return @$ALLPORTS if $ALLPORTS;
	for my $root ($CFG->{CUSTOM_PORTS}, map { $_->{ports} } @{$CFG->{REPOS}})
	{
		my $dh;
 
		next unless -d $root && opendir($dh, $root);
		my @cats = sort grep { !/^\./ && -d "$root/$_" } readdir($dh);
		closedir($dh);
		for my $cat (@cats)
		{
			my $cdh;
			next unless opendir($cdh, "$root/$cat");
			my @names = sort grep { !/^\./ && -d "$root/$cat/$_" } readdir($cdh);
			closedir($cdh);
			for my $name (@names)
			{
				next if $seen{"$cat/$name"};
				$seen{"$cat/$name"} = 1;
				push @out, { cat => $cat, name => $name, dir => "$root/$cat/$name" };
			}
		}
	}
	$ALLPORTS = \@out;
	return @out;
}
 
# same category/name double-readdir scan all_ports() itself does, but
# rooted at exactly ONE directory instead of CUSTOM_PORTS plus every
# configured repo -- and deliberately NOT cached the way all_ports()'s
# own $ALLPORTS is: a repo-qualified lookup (find_portdir's own third
# arg, below) is rare/deliberate, not a hot path worth the cache
# invalidation complexity a second, root-keyed cache would add.
sub _ports_in_root {
	my ($root) = @_;
	my @out;
 
	return @out unless -d $root && opendir(my $dh, $root);
	my @cats = sort grep { !/^\./ && -d "$root/$_" } readdir($dh);
	closedir($dh);
	for my $cat (@cats)
	{
		next unless opendir(my $cdh, "$root/$cat");
		my @names = sort grep { !/^\./ && -d "$root/$cat/$_" } readdir($cdh);
		closedir($cdh);
		push @out, { cat => $cat, name => $_, dir => "$root/$cat/$_" } for @names;
	}
	return @out;
}
 
# the shared "resolve $name (+ optional $wantslot) against this list of
# port entries" logic find_portdir itself needs twice: once against the
# default, cross-repo, deduped all_ports() list, and once (for a
# repo-qualified lookup) against a single repo's own _ports_in_root(),
# fresh and undeduped. identical resolution order either way: an exact
# directory-name match first (skipped entirely when a slot was
# requested, same reasoning as before this was split out -- a directory
# literally named $name has no slot of its own to check against), else
# fall back to scanning declared pkg_name/pkg_slot across every entry
# in the list.
sub _resolve_in_list {
	my ($entries, $name, $wantslot) = @_;
 
	unless(defined $wantslot && $wantslot ne '')
	{
		for my $p (@$entries)
		{
			return $p->{dir} if $p->{name} eq $name;
		}
	}
	my @matches;
	for my $p (@$entries)
	{
		my $pc = try_pkgconf($p->{dir});
		next unless $pc && $pc->{pkg_name} eq $name;
		# a pkg_slot_use port's effective slot depends on which USE flags
		# are enabled for its bare name, not just its static pkg_slot (see
		# mplib::portformat::resolve_slot) -- composing it here lets a
		# dep reference like "curl:nossl" find curl's one port directory
		# even though "nossl" never appears literally in its pkg.conf.
		push @matches, { dir => $p->{dir}, slot => (resolve_slot($pc, $pc->{pkg_name}) || '0'), pref => ($pc->{pkg_pref} || 50) };
	}
	return undef unless @matches;
	if(defined $wantslot && $wantslot ne '')
	{
		for my $m (@matches) { return $m->{dir} if $m->{slot} eq $wantslot; }
		return undef;
	}
	my @sorted = sort { $a->{pref} <=> $b->{pref} } @matches;
	return $sorted[0]{dir};
}
 
# $wantrepo (optional, third arg -- parse_dep_token's own "::repo"
# suffix, see mplib::version): restricts the search to exactly the
# named configured repo instead of the normal cross-repo priority
# search, for a dependency atom (or CLI token) that deliberately wants
# one specific repo's copy rather than whichever wins the usual
# priority order. CUSTOM_PORTS_DIR still applies unconditionally either
# way -- it's documented as "highest priority of all, for every port
# lookup" (mp.conf.example), an entirely separate axis (the user's own
# local override) from which of several CONFIGURED repos a name should
# resolve against, so a repo qualifier narrowing the latter has no
# business overriding the former.
#
# the "cat/name" branch just below DOES honor $wantrepo when called
# directly (and is exercised that way, deliberately, by this function's
# own test coverage) -- but parse_dep_token itself has no "/" in ANY of
# its character classes (a cat/name-shaped token is treated as one
# opaque, entirely unparsed literal name -- see its own deptok_
# unparsable_slash test), so "cat/name::repo" typed on the command line
# or in a pkg_deps= entry never actually reaches here with $wantrepo
# populated at all. only the bare-name form (the overwhelmingly common
# case for a real dependency atom) is reachable with a repo qualifier
# today; closing the cat/name gap too would mean teaching
# parse_dep_token to parse "/" specifically for this one shape, without
# disturbing find_portdir's own existing, separate "cat/name" splitting
# -- left as a followup, not attempted here.
sub find_portdir {
	my ($name, $wantslot, $wantrepo) = @_;
 
	if($name =~ m{^([^/]+)/([^/]+)$})
	{
		my $custom = "$CFG->{CUSTOM_PORTS}/$1/$2";
		return $custom if -d $custom;
		if(defined $wantrepo && $wantrepo ne '')
		{
			my ($r) = grep { $_->{name} eq $wantrepo } @{$CFG->{REPOS}};
			return undef unless $r;
			my $cand = "$r->{ports}/$1/$2";
			return -d $cand ? $cand : undef;
		}
		for my $r (@{$CFG->{REPOS}})
		{
			my $cand = "$r->{ports}/$1/$2";
			return $cand if -d $cand;
		}
		return undef;
	}
	if(defined $wantrepo && $wantrepo ne '')
	{
		my ($r) = grep { $_->{name} eq $wantrepo } @{$CFG->{REPOS}};
		return undef unless $r;
		return _resolve_in_list([ _ports_in_root($r->{ports}) ], $name, $wantslot);
	}
	# no directory is literally named $name (or a specific slot was asked
	# for): a slotted port's directory need not match its pkg_name (e.g.
	# compilers/gcc-12, compilers/gcc-13 both declaring pkg_name="gcc"),
	# so fall back to scanning declared pkg_name/pkg_slot across the tree.
	return _resolve_in_list([ all_ports() ], $name, $wantslot);
}
 
sub try_pkgconf {
	my ($portdir) = @_;
	return resolve_port($portdir);
}
 
sub pkgconf {
	my ($portdir) = @_;
	my $out = try_pkgconf($portdir);
 
	fail("failed reading pkg.conf for $portdir") unless $out;
	return $out;
}
 
sub expand_meta {
	my ($name, $db, $seen) = @_;
	my $bare = bare_name($name);
 
	if($bare eq 'world')
	{
		return sort keys %$db;
	}
	if($bare eq 'all')
	{
		return map { $_->{name} } all_ports();
	}
	if($bare =~ /^@(.+)$/)
	{
		return expand_set($1, $db, $seen || {});
	}
	return ($name);
}
 
# a user-makable package set: plain text, one name/@nested-set/world/all
# per line, at $WD/sets/<setname>.set -- no dedicated command needed to
# make one, just write the file, matching how per-package config sections
# already work.
sub expand_set {
	my ($setname, $db, $seen) = @_;
 
	if($seen->{$setname}++)
	{
		fail("set \@$setname is self-referential");
	}
	my @lines = read_lines("$CFG->{WD}/sets/$setname.set");
	fail("set \@$setname not found ($CFG->{WD}/sets/$setname.set)") unless @lines;
	my @out;
	for my $line (@lines)
	{
		next unless $line =~ /\S/;
		next if $line =~ /^\s*#/;
		push @out, expand_meta($line, $db, $seen);
	}
	# clear this set's mark once its own expansion is done, not just on a
	# true cycle: $seen only needs to track sets currently on the path
	# from the top-level call down to here, so a second, non-cyclic
	# reference to the same set from a sibling branch (a diamond, e.g.
	# two sets both including @common) is legitimate and shouldn't be
	# mistaken for self-reference just because $common was already fully
	# expanded and returned from earlier.
	delete $seen->{$setname};
	return @out;
}
 
# a pkg_conflicts entry is written against a port's bare name (slots
# don't exist yet at port-authoring time -- the same reason pconf_lookup
# falls back from a slotted canon to its bare name), so it must match a
# db key regardless of which slot suffix that key carries; an entry that
# DOES carry an explicit ":slot" of its own (a deliberate pin to one
# specific slot, not the common case) is the one exception, matched
# exactly rather than falling back. without this, a conflict declared
# the natural bare way is silently never detected against any slotted
# install of the target.
sub _conflict_matches {
	my ($token, $key) = @_;
	return 1 if $token eq $key;
	return 0 if $token =~ /:/;
	my ($base) = split_slot_key($key);
	return $token eq $base;
}
 
# CONFLICTS= (mp.conf, per-package only -- bare_name('.conflicts) fallback
# like every other per-package key): an OPTIONAL user override on top of
# a port's own declared pkg_conflicts, same +/- delta convention as
# USE=/"mp use" -- a bare list REPLACES the declared conflicts outright,
# a +token/-token delta is applied atop them instead ("+!!other-libc"
# adds a hard blocker the port itself never declared, "-!somepkg" lifts
# a soft one it did -- the token after +/- is matched verbatim against a
# declared entry, '!'/'!!' markers included, so removing a soft entry
# needs the same leading '!' the declaration itself used). no global
# variant: a conflict is inherently a relationship between two SPECIFIC
# packages, not a system-wide toggle like a USE flag -- a global
# CONFLICTS= would silently blocker-ize every OTHER port's coexistence
# with whatever it names, a far larger blast radius than intended. no
# dedicated command persists this today -- hand-edit mp.conf.
sub effective_conflicts {
	my ($canon, $pc) = @_;
	my $declared = $pc->{pkg_conflicts} || '';
	my $raw = $canon ? pconf_lookup($canon, 'CONFLICTS') : undef;
	return $declared unless defined $raw;
	return '' if $raw eq USE_NONE;
	return delta_or_literal($raw, $declared, "CONFLICTS for '$canon'");
}
 
# a pkg_conflicts entry may be "pkg" or "!pkg" (soft blocker: warns but
# does not block -- %tag resolution already tries a conflict-free
# provider automatically, see pick_provider) or "!!pkg" (hard blocker:
# always blocks, e.g. two libc slots that genuinely cannot coexist).
sub check_static_conflicts {
	my ($name, $pc, $db) = @_;
 
	for my $c (split ' ', effective_conflicts($name, $pc))
	{
		my $hard = 1;
		if($c =~ /^!!(.+)$/)   { $hard = 1; $c = $1; }
		elsif($c =~ /^!(.+)$/) { $hard = 0; $c = $1; }
		my ($match) = grep { _conflict_matches($c, $_) } keys %$db;
		next unless defined $match;
		if($hard) { return $match; }
		note("$name softly conflicts with installed $match");
	}
	for my $installed (sort keys %$db)
	{
		# the slot must be threaded through to find_portdir too, not just
		# the bare name -- a statically multi-directory slotted port
		# (e.g. compilers/gcc-12 and compilers/gcc-13, both declaring
		# pkg_name="gcc") would otherwise resolve to whichever directory
		# has the lowest pkg_pref (find_portdir's own tie-break for "no
		# slot requested"), not the specific slot actually installed --
		# silently checking the WRONG variant's pkg_conflicts against
		# $name, either missing a real conflict the installed slot
		# declares or attributing one from a different, not-installed
		# slot.
		my ($ibase, $islot) = split_slot_key($installed);
		my $idir = find_portdir($ibase, $islot);
		next unless $idir;
		my $ipc = try_pkgconf($idir);
		next unless $ipc;
		for my $c (split ' ', effective_conflicts($installed, $ipc))
		{
			my $hard = 1;
			if($c =~ /^!!(.+)$/)   { $hard = 1; $c = $1; }
			elsif($c =~ /^!(.+)$/) { $hard = 0; $c = $1; }
			next unless _conflict_matches($c, $name);
			if($hard) { return $installed; }
			note("installed $installed softly conflicts with $name");
		}
	}
	return undef;
}
 
# every currently-installed package a soft ("!", not "!!") conflict
# actually matches, in both directions -- the exact same pairs
# check_static_conflicts itself discovers above but only ever note()s,
# never returns (a hard conflict there aborts/backtracks instead, so
# nothing else needed the list until now). kept as its own separate
# function rather than reshaping check_static_conflicts' own return
# value -- that one has a second caller (pick_provider, backtracking
# among %tag candidates) relying on its existing plain truthy/falsy
# scalar return, not worth the regression risk of changing its shape
# for this one new use. install_pkg_body is the caller: a soft conflict
# with something genuinely unneeded (mplib::resolve::reachable_needed_
# set says nothing reaches it) gets auto-removed as part of the same
# install, same spirit as a real transactional weak-blocker resolution;
# one still needed escalates to a hard failure instead of silently
# letting both coexist -- see install_pkg_body's own comment for why
# that split, not "always remove" or "always just warn", is the
# actual improvement here.
sub soft_conflict_targets {
	my ($name, $pc, $db) = @_;
	my @out;
 
	for my $c (split ' ', effective_conflicts($name, $pc))
	{
		next if $c =~ /^!!/;
		next unless $c =~ s/^!//;
		my ($match) = grep { _conflict_matches($c, $_) } keys %$db;
		push @out, $match if defined $match;
	}
	for my $installed (sort keys %$db)
	{
		# see check_static_conflicts' own identical comment just above --
		# the slot must be threaded through find_portdir here too, for
		# the identical reason.
		my ($ibase, $islot) = split_slot_key($installed);
		my $idir = find_portdir($ibase, $islot);
		next unless $idir;
		my $ipc = try_pkgconf($idir);
		next unless $ipc;
		for my $c (split ' ', effective_conflicts($installed, $ipc))
		{
			next if $c =~ /^!!/;
			next unless $c =~ s/^!//;
			next unless _conflict_matches($c, $name);
			push @out, $installed;
		}
	}
	my %seen;
	return grep { !$seen{$_}++ } @out;
}
 
# the transitive RUNTIME-dependency closure over every explicitly
# requested package -- "still needed" in the exact sense mp prune
# itself uses to decide what's safe to remove. shared between prune.pl
# (which used to duplicate this exact loop inline) and
# soft_conflict_targets' own caller, install_pkg_body -- one algorithm,
# not two copies quietly drifting apart over time.
#
# $tick (optional, second arg): called once per queue item visited --
# prune.pl's own whole-installed-db walk can be slow enough to want its
# existing "resolving dependencies..." spinner (mplib::util::spin_tick)
# ticking here same as before this was split out; install_pkg_body's
# own use (checking a soft conflict, typically a handful of packages)
# has no such need and simply omits it.
sub reachable_needed_set {
	my ($db, $tick) = @_;
	my %need;
	my @queue;
 
	for my $name (keys %$db)
	{
		if($db->{$name}{requested})
		{
			$need{$name} = 1;
			push @queue, $name;
		}
	}
	while(my $name = shift @queue)
	{
		$tick->() if $tick;
		my ($base, $slot) = split_slot_key($name);
		my $dir = find_portdir($base, $slot);
		next unless $dir;
		my $pc = try_pkgconf($dir);
		next unless $pc;
		for my $d (effective_deps($pc, $name, 'runtime'))
		{
			my $target = resolve_dep_name($d, $name, $db);
			next unless defined $target;
			my $t = resolved_db_key($target, $db);
			next unless defined $t;
			next if $need{$t};
			$need{$t} = 1;
			push @queue, $t;
		}
	}
	return \%need;
}
 
# every flag in $use ({flag=>1|0,...}, mplib::version::parse_dep_token's
# own atom-bracket parse -- 1 means required enabled, 0 required
# disabled) that $enabled ({flag=>1,...}, mplib::portformat::
# enabled_use's own return -- present+truthy means enabled, ABSENT
# means disabled, there is no explicit "0" entry) does NOT currently
# satisfy. empty if every requirement already holds.
sub use_requirement_mismatches {
	my ($enabled, $use) = @_;
	return grep { ($use->{$_} ? 1 : 0) != ($enabled->{$_} ? 1 : 0) } keys %$use;
}
 
# tracks, for the lifetime of this ONE mp process, every USE-conditional
# atom requirement actually applied so far ("$canon\0$flag" => 0|1) --
# lets a SECOND dependency atom (from a different consumer, or the same
# one twice) requiring the OPPOSITE state on the same not-yet-installed
# package's same flag fail with a clear, immediate error naming exactly
# what disagrees, instead of the second requirement silently winning (or
# losing) with no indication anything was ever contested. resets
# implicitly every run (mp is a fresh process per invocation) -- nothing
# here needs to survive beyond one command.
my %USE_REQUIRED_THIS_RUN;
 
# applies a USE-conditional atom's requirement ($use, mplib::version::
# parse_dep_token's own bracket parse, e.g. from "somelib[ssl,-static]")
# to $canon (the BARE name -- USE= is always persisted/read under the
# bare name regardless of slot, the same convention every other
# per-package USE mechanism already follows; see use.pl's own identical
# reasoning) before it gets installed or rebuilt: a flag already in the
# required state is left alone; a genuine change gets persisted via
# set_pkgconf so the upcoming build actually picks it up, preserving
# every OTHER currently-enabled flag exactly as it was (never a blanket
# "just these flags, drop everything else").
#
# a SECOND, contradictory requirement on the same canon+flag within
# this same run is a hard failure, immediately, naming the flag and
# both values -- silently picking one (first-wins, or worse, last-wins)
# would build $canon in a way that quietly breaks whichever consumer
# didn't get its way, with no indication anything was ever contested.
# deliberately NOT PMS's own fuller autounmask-style resolution
# (computing and prompting a config change across the whole graph) --
# a clear, immediate error naming exactly what disagrees is simpler,
# fully deterministic, and arguably better UX for a conflict a human
# still has to resolve either way, for a project this size.
#
# %USE_REQUIRED_THIS_RUN's OWN practical reach is narrower than "any
# two consumers disagreeing," worth being honest about: mp resolves
# pkg_deps= sequentially, one token at a time, and install_pkg_body
# only returns (writing $canon into $db) once a real build has fully
# finished -- so two consumers naming the SAME not-yet-installed target
# almost always have the first one complete, and $db populated, before
# the second is ever looked at, which resolve_dep's own separate
# "already installed, wrong USE state" check (see its own comment)
# catches instead, with a different message. this tracking hash
# specifically guards the narrower remaining window: a requirement
# recorded here by an attempt that itself never reached $db at all (a
# soft dependency that failed and was skipped after already calling
# this, most plausibly) followed by a later, different, non-soft
# consumer wanting the opposite state on that same still-not-installed
# target. verified directly (unit-level, not via a full mp install) for
# exactly this reason -- see test/suites/resolution.sh's own comment on
# its "sequential conflicting requirements" test for the reachable,
# end-to-end case instead.
sub apply_use_requirement {
	my ($canon, $use, $pc) = @_;
 
	for my $flag (keys %$use)
	{
		my $key = "$canon\x00$flag";
		if(exists $USE_REQUIRED_THIS_RUN{$key} && $USE_REQUIRED_THIS_RUN{$key} != $use->{$flag})
		{
			fail("conflicting USE requirements on '$canon': flag '$flag' required "
			    . ($use->{$flag} ? 'enabled' : 'disabled') . " by one dependency atom, "
			    . ($USE_REQUIRED_THIS_RUN{$key} ? 'enabled' : 'disabled') . " by another this same run");
		}
		$USE_REQUIRED_THIS_RUN{$key} = $use->{$flag};
	}
	my $declared = parse_pkg_use($pc->{pkg_use});
	my $enabled = enabled_use($canon, $declared);
	my @mismatch = use_requirement_mismatches($enabled, $use);
	return unless @mismatch;
	my %want = %$enabled;
	$want{$_} = $use->{$_} for keys %$use;
	my $result = join(' ', sort grep { $want{$_} } keys %want);
	note("setting USE for '$canon' to satisfy a dependency atom's own requirement: "
	    . join(',', map { ($use->{$_} ? '' : '-') . $_ } @mismatch));
	set_pkgconf($canon, 'USE', $result eq '' ? USE_NONE : $result);
	return;
}
 
sub tag_providers {
	my %providers;
 
	return $TAGMAP if $TAGMAP;
	for my $p (all_ports())
	{
		my $pc = try_pkgconf($p->{dir});
		next unless $pc;
		for my $tag (split ' ', $pc->{pkg_tags} || '')
		{
			push @{$providers{$tag}}, { name => $p->{name}, pref => ($pc->{pkg_pref} || 50) };
		}
	}
	$TAGMAP = \%providers;
	return $TAGMAP;
}
 
# which installed db key (if any) currently declares $tag -- $name is a
# raw db key ("gcc:12", "curl:nossl", or a bare "openssl"), and
# find_portdir needs the slot split off and passed separately (it matches
# by declared pkg_name/pkg_slot, not by the compound canon string), or it
# never finds a slotted installed package's directory at all, silently
# reporting the tag as unsatisfied even though it genuinely is.
sub installed_tag_provider {
	my ($tag, $db) = @_;
 
	for my $name (sort keys %$db)
	{
		my ($base, $slot) = split_slot_key($name);
		my $dir = find_portdir($base, $slot);
		next unless $dir;
		my $pc = try_pkgconf($dir);
		next unless $pc;
		return $name if grep { $_ eq $tag } split ' ', $pc->{pkg_tags} || '';
	}
	return undef;
}
 
sub tag_satisfied {
	my ($tag, $db) = @_;
	return defined(installed_tag_provider($tag, $db)) ? 1 : 0;
}
 
sub portpin {
	my ($cur, $tag) = @_;
 
	if($cur)
	{
		for my $key ("TARGET_$tag", "TAG_$tag")
		{
			# pconf_lookup (not a bare $CFG->{pconf}{$cur} exact-canon
			# check): a pkg_slot_use-composed canon (e.g.
			# "pinvariant:variant") doesn't exist yet at the moment a
			# per-package TARGET_/TAG_ pin is written, so a pin declared
			# under the bare name was silently invisible to a slotted
			# package's own %tag resolution, falling through to
			# pkg_pref auto-pick instead of honoring the pin.
			my $val = pconf_lookup($cur, $key);
			return $val if defined $val && $val ne '';
		}
	}
	for my $key ("TARGET_$tag", "TAG_$tag")
	{
		if(defined $CFG->{conf}{$key} && $CFG->{conf}{$key} ne '')
		{
			return $CFG->{conf}{$key};
		}
	}
	return undef;
}
 
# effective dependency list for a package after config modification.
sub effective_deps {
	my ($pc, $canon, $mode) = @_;
	$mode ||= 'all';
	# pkg_deps is legacy shorthand for "needed both to build and at
	# runtime"; pkg_bdepend/pkg_rdepend split the two. 'all' (install
	# time, needs everything) includes both; 'runtime' (mp.prune's "is
	# this still needed" closure) drops bdepend-only deps.
	my @deps = split ' ', ($pc->{pkg_deps} || '');
	push @deps, split ' ', ($pc->{pkg_rdepend} || '');
	push @deps, split ' ', ($pc->{pkg_bdepend} || '') if $mode eq 'all';
	# enabled USE flags add their declared deps (optional features); a
	# flag marked "b:" (build-only) is skipped in runtime mode. collected
	# before the DEPS/DEPS+/DEPS- override block below (not after), so a
	# use-flag-contributed dep is just as overridable as a plain pkg_deps
	# one -- appending it afterward let it silently bypass DEPS- entirely
	# (DEPS-=<tag> could never remove it) and made DEPS= (meant as a full
	# override of the dependency list) not actually override it either.
	my $use = parse_pkg_use($pc->{pkg_use});
	my $en = $canon ? enabled_use($canon, $use) : {};
	for my $f (sort keys %$en)
	{
		next unless $use->{$f};
		next if $mode ne 'all' && $use->{$f}{build};
		push @deps, @{$use->{$f}{deps}};
	}
 
	my %removed;
	my @added;
	# pconf_section (not a bare $CFG->{pconf}{$canon} exact-canon check):
	# same fallback pconf_lookup/portpin already need, since a
	# pkg_slot_use-composed canon doesn't exist yet at the moment a
	# DEPS/DEPS+/DEPS- override is written under a port's bare name.
	my $s = pconf_section($canon);
 
	if(%$s)
	{
		if(defined $s->{DEPS})
		{
			@deps = split ' ', $s->{DEPS};
		}
		if(defined $s->{'DEPS+'})
		{
			push @added, split ' ', $s->{'DEPS+'};
		}
		if(defined $s->{'DEPS-'})
		{
			$removed{$_} = 1 for split ' ', $s->{'DEPS-'};
		}
	}
	@deps = grep { !$removed{$_} } @deps;
	push @deps, @added;
	# soft deps participate in resolution/ordering but never block: if
	# they'd create a cycle or aren't satisfiable, the caller (resolve_dep)
	# just leaves them unresolved rather than dying. generalizes the old
	# hardcoded %libc/%shell/%coreutils bootstrap-triangle exemption below.
	push @deps, map { "?$_" } split ' ', ($pc->{pkg_deps_soft} || '');
	# global deps are appended everywhere except two cases. the no-op
	# logical metas (null/world/all) must stay trivial (they expand to
	# whole sets and can't have deps resolved). and a port providing any
	# of the global %tags is a bootstrap provider: it is exempt from the
	# whole GLOBAL_DEPS line, not just its own tag, so libc/shell/coreutils
	# providers never depend on each other (which would cycle: a shell
	# needs %coreutils to build, coreutils needs %shell). real meta
	# packages (e.g. meta/mp) still get GLOBAL_DEPS like any other port.
	my %noop = map { $_ => 1 } qw(null world all);
	if($CFG->{GLOBAL_DEPS} && !(defined $canon && $noop{bare_name($canon)}))
	{
		my %self = map { $_ => 1 } split ' ', ($pc->{pkg_tags} || '');
		my $bootstrap = 0;
		for my $gd (split ' ', $CFG->{GLOBAL_DEPS})
		{
			my ($tagname) = $gd =~ /^%(.+)$/;
			$bootstrap = 1 if defined $tagname && $self{$tagname};
		}
		unless($bootstrap)
		{
			my %have = map { $_ => 1 } @deps;
			for my $gd (split ' ', $CFG->{GLOBAL_DEPS})
			{
				next if $have{$gd};
				push @deps, $gd;
				$have{$gd} = 1;
			}
		}
	}
	return @deps;
}
 
# hold / version constraint.
sub held_reason {
	my ($name) = @_;
	my $hold = pconf_lookup($name, 'HOLD');
	return (defined $hold && $hold =~ /^(y|yes|1|true)$/i) ? "held by config (HOLD=yes)" : undef;
}
 
sub version_held_mismatch {
	my ($name, $ver) = @_;
	my $hv = pconf_lookup($name, 'HOLD_VERSION');
	return (defined $hv && $hv ne $ver) ? 1 : 0;
}
 
# general masking: MASK=yes in a "<name>:" config section hides a
# candidate from auto-pick and blocks an explicit install, without
# deleting the port -- "mp.install --unmask name" overrides it.
sub masked_reason {
	my ($name) = @_;
	return undef if $CFG->{UNMASK};
	my $mask = pconf_lookup($name, 'MASK');
	return undef unless defined $mask && $mask ne '';
	return undef if $mask =~ /^(n|no|0|false)$/i;
	return "masked by config (MASK=$mask)";
}
 
# keywords gate: pkg_keywords="amd64 arm64 ~riscv" (bare = stable, ~arch =
# testing, absent from the list = unsupported there). ACCEPT_KEYWORDS
# unset (the default) turns the whole check off, so ports that declare no
# pkg_keywords (nearly all of them, today) are never affected.
sub keyword_reason {
	my ($pc) = @_;
	return undef if $CFG->{UNMASK};
	my $accept = $CFG->{conf}{ACCEPT_KEYWORDS};
	return undef unless defined $accept && $accept ne '';
	return undef unless $pc->{pkg_keywords} && $pc->{pkg_keywords} ne '';
	my %kw = map { $_ => 1 } split ' ', $pc->{pkg_keywords};
	for my $a (split ' ', $accept)
	{
		if($a =~ /^~(.+)$/) { return undef if $kw{$a} || $kw{$1}; }
		else                { return undef if $kw{$a}; }
	}
	return "keywords ($pc->{pkg_keywords}) do not satisfy ACCEPT_KEYWORDS ($accept)";
}
 
# try each %tag provider in preference order: prefer one already
# installed outright, else the first whose static conflicts probe clean
# (via try_soft, so a conflicting candidate is skipped rather than
# aborting the whole resolution). this is a real but deliberately simple
# backtracking search over just this one choice point -- not a full SAT
# solver reconsidering earlier choices too.
sub pick_provider {
	my ($sorted, $db) = @_;
	my @cand;
 
	for my $p (@$sorted)
	{
		my $portdir = find_portdir($p->{name});
		next unless $portdir;
		my $pc = try_pkgconf($portdir);
		next unless $pc;
		# resolve_slot (not the raw static pkg_slot) so this canon matches
		# what install_pkg actually computes/installs under for a
		# pkg_slot_use-composed provider -- using the raw pkg_slot here
		# left both the already-installed check below and
		# check_static_conflicts looking under the wrong db key.
		push @cand, { name => $p->{name}, pc => $pc, canon => slot_key($pc->{pkg_name}, resolve_slot($pc, $pc->{pkg_name})) };
	}
	for my $c (@cand)
	{
		return $c->{name} if $db->{$c->{canon}};
	}
	@cand = grep { !masked_reason($_->{canon}) && !keyword_reason($_->{pc}) } @cand;
	for my $c (@cand)
	{
		my $conflict;
		try_soft(sub { $conflict = check_static_conflicts($c->{canon}, $c->{pc}, $db); });
		return $c->{name} unless $conflict;
	}
	return undef;
}
 
# interactive fallback once automatic backtracking exhausts every
# provider without finding a conflict-free one; undef (abort) if there's
# no terminal to prompt on.
sub interactive_pick {
	my ($sorted, $tag, $cur) = @_;
 
	return undef unless -t STDIN;
	print STDERR "no conflict-free provider of %$tag found automatically"
	    . (defined $cur ? " (needed by $cur)" : '') . ":\n";
	for my $i (0 .. $#$sorted)
	{
		print STDERR "  " . ($i + 1) . ") $sorted->[$i]{name} (pref $sorted->[$i]{pref})\n";
	}
	print STDERR "  0) abort\n";
	print STDERR "choice: ";
	my $ans = <STDIN>;
	return undef unless defined $ans;
	chomp $ans;
	return undef if $ans eq '' || $ans eq '0';
	return undef unless $ans =~ /^[0-9]+$/ && $ans >= 1 && $ans <= @$sorted;
	return $sorted->[$ans - 1]{name};
}
 
# resolve a dep token to a concrete port name without installing.
sub resolve_dep_name {
	my ($dep, $cur, $db) = @_;
	# both the "?" soft marker and the "@" subslot-tracking marker (see
	# record_subslot_dep's own comment) are stripped here -- this
	# function's whole job is turning a raw pkg_deps= token into the
	# real dependency NAME it points at, for every caller that needs to
	# recognize the edge at all (update.pl's own rebuild ordering, why.pl/
	# tree.pl/prune.pl, resolved_slotted_deps' buildlink wiring) -- a
	# leading "@" left unstripped would make parse_dep_token (called
	# below, indirectly, for the "%tag" check, and directly by every
	# caller afterward) treat the whole token as one opaque unparsed
	# name instead of recognizing the real dependency at all, silently
	# breaking every one of those uses for a subslot-tracked dependency
	# specifically.
	$dep =~ s/^[?@]+//;
 
	if($dep =~ /^%(.+)$/)
	{
		my $tag = $1;
		my $pin = portpin($cur, $tag);
		return $pin if $pin;
		# already satisfied: return WHAT satisfies it (the actual
		# installed db key), not undef -- every caller (why.pl/tree.pl/
		# update.pl/prune.pl, plus resolved_slotted_deps' buildlink/
		# revdep wiring) needs to know the concrete provider to record a
		# real dependency edge; treating "already satisfied" the same as
		# "unresolvable" silently dropped that edge everywhere, which for
		# prune.pl specifically meant a still-needed slotted %tag
		# provider could look prunable.
		my $installed = installed_tag_provider($tag, $db);
		return $installed if defined $installed;
		# not yet satisfied by anything installed: predict what
		# resolve_dep would actually pick if asked to install this
		# dependency now, which sorts by pkg_pref first (mirroring
		# resolve_dep exactly, not just tag_providers()' raw directory-
		# scan order, which pick_provider itself never uses either).
		my $providers = tag_providers()->{$tag};
		return undef unless $providers && @$providers;
		my @sorted = sort { $a->{pref} <=> $b->{pref} } @$providers;
		return $sorted[0]{name};
	}
	return $dep;
}
 
# find the $db key an already-resolved dep reference actually installed
# under -- a slot-qualified reference (e.g. "curl:nossl") maps directly;
# a bare one falls back to whichever slot of that bare name is actually
# installed (ambiguous if several coexist, same as any other bare dep
# reference -- an explicit name:slot is how a port disambiguates, exactly
# as for a static gcc-style slot).
sub resolved_db_key {
	my ($ref, $db) = @_;
	# a TAG_/TARGET_ pin (see portpin) is conventionally written
	# "category/name" (e.g. "meta/null"), a form parse_dep_token's name
	# grammar doesn't accept at all ('/' isn't in its character class),
	# so strip any such prefix first -- bare_name's plain "up to the last
	# /" strip, same as find_portdir's own "category/name" handling,
	# rather than silently failing to resolve every pinned dependency.
	my $tok = parse_dep_token(bare_name($ref));
	my $key = slot_key($tok->{name}, $tok->{slot});
	return $key if $db->{$key};
	for my $k (sort keys %$db)
	{
		my ($base) = split_slot_key($k);
		return $k if $base eq $tok->{name};
	}
	return undef;
}
 
# every one of $pc's resolved dependencies that is itself slotted (any
# axis -- gcc version, libc, microarch, optimization, or a
# pkg_slot_use-composed USE-flag variant), as canon db keys, deduped. the
# shared source of truth behind both dep_slot_prefixes (buildlink env
# wiring) and the linkdeps revdep-safety tracking (mplib::db) -- a
# dependency living at the default (unslotted) prefix needs no entry in
# either, since it's already covered by the plain MP_PREFIX-based flags
# and can't be removed out from under a specific slot reference anyway.
sub resolved_slotted_deps {
	my ($pc, $canon, $db) = @_;
	my %seen;
	my @keys;
	for my $dep (effective_deps($pc, $canon))
	{
		# both markers stripped (not just "?"): a "@"-prefixed token is
		# just as real a buildlink edge as any other -- see
		# resolve_dep_name's own comment for why both need stripping
		# wherever a raw pkg_deps= token is interpreted as a reference.
		(my $bare = $dep) =~ s/^[?@]+//;
		my $ref = ($bare =~ /^%(.+)$/) ? resolve_dep_name($bare, $canon, $db) : $bare;
		next unless defined $ref;
		my $key = resolved_db_key($ref, $db);
		next unless defined $key;
		my (undef, $slot) = split_slot_key($key);
		next unless $slot && $slot ne '0';
		push @keys, $key unless $seen{$key}++;
	}
	return @keys;
}
 
# buildlink-style wiring: the private install prefix for each of
# resolved_slotted_deps() above. mpx.c's cmd_runsh turns these into
# -I/-L/rpath/PKG_CONFIG_PATH so a build actually links against the exact
# dependency variant it declared, not whatever else happens to be on the
# default search path.
sub dep_slot_prefixes {
	my ($pc, $canon, $db) = @_;
	return map {
		my ($base, $slot) = split_slot_key($_);
		"$CFG->{INSTPREFIX}/$base-$slot";
	} resolved_slotted_deps($pc, $canon, $db);
}
 
# "@dep" in pkg_deps= (mplib::resolve::resolve_dep's own leading-sigil
# strip, same convention as the existing "?" soft marker): records,
# after $consumer successfully resolves against $target_ref, exactly
# what pkg_subslot value the ACTUAL resolved target currently declares
# -- Portage's own ":=" slot operator, in spirit, without needing a
# second, separate slot-like grammar element in the atom itself (mp's
# existing slot syntax already means something different -- an exact
# SLOT pin, not "track and rebuild on ABI change" -- and the two aren't
# mutually exclusive, so layering this onto a sigil instead of the slot
# position keeps them independent). a target with no pkg_subslot
# declared at all is simply never tracked -- "opt-in per port", not a
# blanket requirement every port must declare one to be depended on
# this way.
#
# $target_ref is resolved via resolved_db_key (not assumed to already
# be the exact db key) since the caller may only have the RAW
# reference (a bare name, a %tag's own pin, or the concrete port a %tag
# backtracked to) -- by the time this runs, $db already reflects
# whatever install_pkg just did, so resolved_db_key's own "fall back to
# whichever slot is actually installed" resolution finds the real
# target correctly either way.
sub record_subslot_dep {
	my ($consumer, $target_ref, $db) = @_;
	my $target = resolved_db_key($target_ref, $db);
	return unless defined $target;
	my ($base, $slot) = split_slot_key($target);
	my $dir = find_portdir($base, $slot);
	return unless $dir;
	my $pc = try_pkgconf($dir);
	return unless $pc;
	my $subslot = $pc->{pkg_subslot};
	return unless defined $subslot && $subslot ne '';
	my $edges = read_subslot_deps();
	my %deps = %{$edges->{$consumer} || {}};
	$deps{$target} = $subslot;
	write_subslot_deps_for($consumer, \%deps);
	return;
}
 
# mp update's own rebuild-cascade check: every currently-installed
# package (regardless of whether it's in the caller's own requested
# update set already) whose subslots.db record for at least one tracked
# dependency no longer matches that dependency's CURRENT pkg_subslot --
# i.e. every consumer that built against an ABI which has since moved
# out from under it, and needs rebuilding to catch up. a dependency
# that no longer resolves at all (removed from the tree, or the
# consumer itself no longer installed) is silently skipped, not an
# error -- this is an ADDITIVE discovery pass (more packages to rebuild
# that the caller didn't explicitly name), never itself a source of
# failures.
sub subslot_changed_targets {
	my ($db) = @_;
	my @out;
	my $edges = read_subslot_deps();
 
	for my $consumer (sort keys %$edges)
	{
		next unless $db->{$consumer};
		for my $dep (sort keys %{$edges->{$consumer}})
		{
			next unless $db->{$dep};
			my ($base, $slot) = split_slot_key($dep);
			my $dir = find_portdir($base, $slot);
			next unless $dir;
			my $pc = try_pkgconf($dir);
			next unless $pc;
			my $current = $pc->{pkg_subslot};
			next unless defined $current && $current ne '';
			next if $current eq $edges->{$consumer}{$dep};
			push @out, $consumer;
			last;
		}
	}
	return @out;
}
 
sub resolve_dep {
	my ($dep, $db, $seen, $cur, $req) = @_;
	# "?" (soft) and "@" (subslot-tracked, see record_subslot_dep's own
	# comment) are independent, orthogonal markers -- either order,
	# either alone, or both together, all valid. only ever applied on a
	# genuinely successful, non-soft resolution below (a soft dep that
	# got skipped has nothing real to record against; deliberately not
	# handled for the soft case at all, an esoteric combination this
	# doesn't need to support for the primary use case -- a real ABI
	# dependency being declared soft in the first place would be
	# unusual).
	my ($soft, $tracked) = (0, 0);
	while(1)
	{
		if($dep =~ s/^\?//) { $soft = 1; next; }
		if($dep =~ s/^@//)  { $tracked = 1; next; }
		last;
	}
 
	if($dep =~ /^%(.+)$/)
	{
		my $tag = $1;
		my $pin = portpin($cur, $tag);
		if(defined $pin && $pin ne '')
		{
			note("%$tag pinned to $pin (for $cur)");
			# no short-circuit here beyond what install_pkg already does
			# itself: a bare $db->{bare_name($pin)} lookup never matches
			# a slotted canon, and worse, would wrongly treat a
			# version-pinned "name=X" the same as an unconstrained pin,
			# silently accepting an already-installed version that
			# doesn't actually satisfy "=X". install_pkg's own idempotent
			# skip (quiet if already installed and satisfying) and hard
			# version-mismatch fail() already cover exactly this.
			if($soft)
			{
				note("soft dep %$tag ($pin) failed, skipping") unless try_soft(sub { install_pkg($pin, $db, $seen, 0); });
				return;
			}
			install_pkg($pin, $db, $seen, 0);
			record_subslot_dep($cur, $pin, $db) if $tracked;
			return;
		}
		return if tag_satisfied($tag, $db);
		my $providers = tag_providers()->{$tag};
		unless($providers && @$providers)
		{
			if($soft) { note("soft dep %$tag has no provider, skipping"); return; }
			fail("no port provides tag %$tag");
		}
		my @sorted = sort { $a->{pref} <=> $b->{pref} } @$providers;
		my $picked = pick_provider(\@sorted, $db);
		unless(defined $picked)
		{
			if($soft) { note("soft dep %$tag has no conflict-free provider, skipping"); return; }
			$picked = interactive_pick(\@sorted, $tag, $cur);
			fail("no provider of %$tag could be installed without conflicting") unless defined $picked;
		}
		note("%$tag resolved to $picked");
		if($soft)
		{
			note("soft dep %$tag ($picked) failed, skipping") unless try_soft(sub { install_pkg($picked, $db, $seen, $req); });
			return;
		}
		install_pkg($picked, $db, $seen, $req);
		record_subslot_dep($cur, $picked, $db) if $tracked;
		return;
	}
	my $tok = parse_dep_token($dep);
	my $key = slot_key($tok->{name}, $tok->{slot});
	if($db->{$key})
	{
		if(defined $tok->{op} && !ver_satisfies($db->{$key}{ver}, $tok->{op}, $tok->{val}))
		{
			if($soft) { note("soft dep $dep unsatisfied by installed $key ($db->{$key}{ver}), skipping"); return; }
			fail("$key is installed at $db->{$key}{ver}, which does not satisfy "
			    . "$dep required by $cur (remove/reinstall $key at a satisfying version first)");
		}
		# a USE-conditional atom ("somelib[ssl]") against an ALREADY-
		# installed $key: unlike the not-yet-installed case
		# (install_pkg's own apply_use_requirement, which can still
		# persist an override before the very first build), $key is
		# already built -- there is no way to retroactively change what
		# flags its existing binary was actually compiled with, so a
		# mismatch here can only ever be a hard failure (or a soft-dep
		# skip), never something to silently patch up.
		if(defined $tok->{use})
		{
			my ($base, $slot) = split_slot_key($key);
			my $dir = find_portdir($base, $slot);
			my $pc = $dir ? try_pkgconf($dir) : undef;
			if($pc)
			{
				my $enabled = enabled_use($key, parse_pkg_use($pc->{pkg_use}));
				my @mismatch = use_requirement_mismatches($enabled, $tok->{use});
				if(@mismatch)
				{
					my $desc = join(',', map { ($tok->{use}{$_} ? '' : '-') . $_ } @mismatch);
					if($soft) { note("soft dep $dep unsatisfied by installed ${key}'s own USE state ($desc), skipping"); return; }
					fail("$key is installed without satisfying USE state ($desc) required by "
					    . "$dep required by $cur (remove/reinstall $key with the right USE flags first)");
				}
			}
		}
		record_subslot_dep($cur, $key, $db) if $tracked;
		return;
	}
	if($soft)
	{
		note("soft dep $dep failed, skipping") unless try_soft(sub { install_pkg($dep, $db, $seen, $req); });
		return;
	}
	install_pkg($dep, $db, $seen, $req);
	record_subslot_dep($cur, $key, $db) if $tracked;
	return;
}
 
# mpx.conf's SANDBOX (global or per-package) governs sandboxing by
# default, but mpx itself can't tell a legacy port's combined
# fetch+build+install "install.sh" from a new-format one where fetch
# already ran as its own separate phase -- only the perl side knows that,
# from $legacy. so this forces sandboxing off for the two cases where it
# would break a legitimate network need: the fetch phase itself, and any
# phase at all of a legacy port (whose one script may embed its own
# fetch). anywhere else, no override is passed and mpx.conf decides.
sub sandbox_arg {
	my ($legacy, $ph) = @_;
	return ($legacy || $ph eq 'fetch') ? ('MP_SANDBOX=no') : ();
}
 
# an optional patches/patches.conf gives individual patches -- named by
# their path relative to patches/, e.g. "003-fix.patch" or the
# use-<flag>/nouse-<flag> subdirectory form "use-ssl/002-extra.patch" --
# the same declarative section grammar as mp.conf itself:
#   003-fix.patch:
#       IF_DEP=%zlib !experimental-thing
#       IF_VER=>=2.0
#       IF_USE=ssl
#       AFTER=001-base.patch
# IF_DEP: every listed token must be among $pc's effective_deps (a
# leading '!' requires its ABSENCE instead); IF_VER: pkg_ver must satisfy
# every listed constraint (same op grammar as any dep token); IF_USE: same
# flag/!flag grammar as HOOKS_DIR/<phase>/hooks.conf's IF_USE, letting a
# flat patches/*.patch be USE-gated too, not just one already inside a
# use-<flag>/nouse-<flag> subdirectory; AFTER: ordering prerequisite(s)
# among the patches actually being applied, topologically sorted --
# filename order (today's only ordering) is still the tiebreak/default
# for anything with no AFTER. lives in
# mplib::resolve (not portformat, where the rest of patch synthesis
# happens) because IF_DEP needs effective_deps, and portformat is
# imported BY resolve -- pulling effective_deps in the other direction
# would be circular. a complete no-op (existing phase text from
# resolve_port/apply_use_patches untouched) when there's no
# patches.conf, or nothing was synthesized to filter/reorder (an
# explicit hand-written patch: phase in pkg.conf itself, same as
# apply_use_patches already leaves alone).
sub apply_patch_manifest {
	my ($pc, $canon) = @_;
	return if $pc->{_legacy};
	my $portdir = $pc->{_portdir};
	return unless defined $portdir;
	my $list = $pc->{_patchlist};
	return unless $list && @$list;
	my $mpath = "$portdir/patches/patches.conf";
	return unless -f $mpath;
 
	# normalized (leading '?' soft-marker and '%' tag sigil both stripped)
	# so "IF_DEP=zlib" matches a dep declared as "%zlib" -- an author
	# writing the tag name alone (the intuitive reading of "depends on
	# zlib") shouldn't have to also know/write the exact '%'-prefixed
	# token shape effective_deps happens to store tag dependencies as.
	my @deps = effective_deps($pc, $canon);
	my %havedep;
	for my $d (@deps)
	{
		(my $norm = $d) =~ s/^[?%]+//;
		$havedep{$d} = 1;
		$havedep{$norm} = 1;
	}
	my $enabled = enabled_use($canon, parse_pkg_use($pc->{pkg_use}));
	my $want = sub {
		my ($sec) = @_;
		return 1 unless $sec;
		for my $tok (split ' ', $sec->{IF_DEP} || '')
		{
			my $wantit = ($tok =~ s/^!//) ? 0 : 1;
			(my $ntok = $tok) =~ s/^%//;
			return 0 if (($havedep{$tok} || $havedep{$ntok} ? 1 : 0) != $wantit);
		}
		for my $constraint (split ' ', $sec->{IF_VER} || '')
		{
			next unless $constraint =~ /^(>=|<=|>|<|=|~)(.+)$/;
			return 0 unless ver_satisfies($pc->{pkg_ver}, $1, $2);
		}
		# same IF_USE=flag/!flag grammar as HOOKS_DIR/<phase>/hooks.conf --
		# a supplement to (not a replacement for) the use-<flag>/nouse-
		# <flag> directory convention: it lets a flat patches/*.patch also
		# be USE-gated without moving it into a subdirectory.
		for my $tok (split ' ', $sec->{IF_USE} || '')
		{
			my $wantit = ($tok =~ s/^!//) ? 0 : 1;
			return 0 if (($enabled->{$tok} ? 1 : 0) != $wantit);
		}
		return 1;
	};
	my @ordered = order_manifest($list, $mpath, $want);
 
	# a patch's own condition (IF_DEP/IF_VER/IF_USE) can also pull in an
	# extra dependency the patch itself needs -- DEPS+=<dep> <dep> in
	# that patch's own section, merged into pkg_deps for every patch
	# actually applied (in @ordered). this is what makes "USE flag on ->
	# patch applies -> patch needs xlib" a single declaration instead of
	# writing the same IF_USE=x condition twice (once via pkg_use's own
	# "x:xlib" gating, once via the patch's own IF_USE=x) to keep them in
	# sync by hand -- and it works for any patch condition, not just
	# IF_USE (e.g. an IF_VER=<2.0 compat patch needing an old-abi dep).
	# read a second time (order_manifest already read $mpath once, but
	# doesn't hand its parsed sections back to the caller) rather than
	# changing order_manifest's shared return contract, which hooks.pm's
	# run_hook also relies on -- patches.conf is small and this runs
	# once per port resolve, not per file.
	my (undef, $patchconf) = read_conf($mpath);
	my @extra;
	for my $p (@ordered)
	{
		push @extra, split ' ', ($patchconf->{$p}{'DEPS+'} || '');
	}
	if(@extra)
	{
		# deliberately evaluated against the @deps snapshot $want closed
		# over above (the port's OWN pkg_deps/pkg_use/DEPS-override
		# state), never against anything a patch itself adds here --
		# letting one patch's DEPS+= feed another's IF_DEP would make
		# the outcome depend on evaluation order, or cycle outright, for
		# no real benefit.
		$pc->{pkg_deps} = join(' ', grep { length } (($pc->{pkg_deps} || ''), @extra));
	}
 
	$pc->{_phases}{patch} = join('', map { "patch -p1 < ../patches/$_\n" } @ordered);
	return;
}
 
# --- pre-install dependency planning ------------------------------------
#
# resolve_dep/pick_provider's own %tag backtracking (above) only ever
# looks at $db as it stands at the moment ONE specific %tag is being
# decided -- correct when a conflict already pre-exists (from an earlier,
# separate "mp install"), but blind in both directions to a conflict that
# only exists because of ANOTHER package in the SAME batch: a %tag
# decided early can turn out to conflict with something the batch hasn't
# installed yet, and a package further down the batch can conflict with
# an early %tag pick that is already real and irreversible on disk by
# the time that is discovered. resolve_dep has no way to undo a real
# install to go back and try a different earlier choice, so today that
# second case aborts the whole batch instead of trying an alternative --
# even when one exists.
#
# plan_resolution runs once, BEFORE any of that: a pure, side-effect-free
# search over port METADATA and the current $db snapshot (never builds,
# installs, removes, or mutates $db) that looks for ONE globally
# consistent assignment -- every %tag anywhere in the transitive closure
# of the requested packages resolved to a specific provider such that
# nothing in the resulting whole set (chosen providers, plain pkg_deps
# targets, and whatever is already in $db) hard-conflicts with anything
# else in it, and no hard (non-soft) dependency edge closes a cycle.
# every genuinely ambiguous %tag (more than one still-viable candidate)
# is a real backtracking decision point, tried lowest-pkg_pref-first
# (same order pick_provider always has), backtracking to the next
# candidate -- and, from there, potentially re-trying every OTHER
# decision point too -- on conflict, cycle, or an unsatisfiable subtree.
# worst case is genuinely combinatorial: as bad as the product of every
# decision point's candidate count, i.e. as steep as O(N!) laid out as a
# chain of increasingly constrained choices. that is accepted on purpose
# -- a real ports tree has few genuinely ambiguous tags per invocation
# (most cost no search at all, see _plan_named's $db/$chosen fast paths
# below), and correctness matters more here than protecting against a
# pathological tree nobody actually has: never silently install a
# conflicting combination, and never abort mid-batch with partial state
# on disk when some other combination would have worked.
#
# deliberately conservative about what it claims to fully model: a
# per-package SYSROOT= override swaps $CFG/$db entirely for its own
# subtree (with_sysroot_scope, above), which this planner does not
# attempt to replay -- hitting one aborts planning outright (the
# PLAN_PUNT exception below), and the caller falls back to resolve_dep's
# own always-correct-if-shallower backtracking for the whole invocation,
# exactly as if plan_resolution had never run. planning is therefore
# always safe to attempt: it either fully validates the batch before
# touching anything, or gets out of the way and changes nothing.
# undef if $canon is installable; otherwise the exact message
# install_pkg_body's own real checks would fail with, so a rejection
# surfaced by the planner reads identically to one surfaced by actually
# attempting the install.
sub _plan_reject_reason {
	my ($canon, $pc, $db) = @_;
	if(!$db->{$canon})
	{
		if(my $why = held_reason($canon)) { return "$canon cannot be (re)installed: $why"; }
		if(my $why = masked_reason($canon)) { return "$canon cannot be installed: $why (--unmask to override)"; }
		if(my $why = keyword_reason($pc)) { return "$canon cannot be installed: $why (--unmask to override)"; }
	}
	if(!$db->{$canon} && version_held_mismatch($canon, $pc->{pkg_ver}))
	{
		return "$canon version $pc->{pkg_ver} does not match HOLD_VERSION $CFG->{pconf}{$canon}{HOLD_VERSION}";
	}
	return undef;
}
 
# pc for an arbitrary db/chosen key, loading it from the ports tree for a
# $db-only entry (mirroring check_static_conflicts' own installed-side
# loop) -- undef if its port directory is gone (an installed package
# whose port vanished from the tree entirely; check_static_conflicts
# itself just skips that case too, via its own "next unless $idir").
sub _plan_pc_for_key {
	my ($key, $db, $chosen) = @_;
	return $chosen->{$key} if $chosen->{$key};
	return undef unless $db->{$key};
	my ($base, $slot) = split_slot_key($key);
	my $dir = find_portdir($base, $slot);
	return undef unless $dir;
	return try_pkgconf($dir);
}
 
# both directions of check_static_conflicts' own hard-blocker check
# (candidate's declared conflicts against the universe, and the
# universe's declared conflicts against the candidate), but against the
# PLANNED set ($chosen, which already includes $canon itself by the time
# this is called) union $db, instead of the live install db alone --
# $chosen is what makes this planner see a conflict between two packages
# that are BOTH still just proposed, not yet real, which check_static_
# conflicts alone never could.
sub _plan_conflict {
	my ($canon, $pc, $db, $chosen) = @_;
	# --force: install_pkg_body's own real conflict check is skipped
	# entirely under FORCE (masked/keyword/held are NOT -- those stay
	# unconditional there, so this planner leaves them unconditional
	# here too, see _plan_candidate_viable), so a plan that would
	# otherwise fail only on a conflict must not reject it either, or
	# --force would stop meaning "install anyway" the moment planning
	# runs before it gets the chance to.
	return undef if $CFG->{FORCE};
	my %universe;
	$universe{$_} = 1 for keys %$chosen;
	$universe{$_} = 1 for keys %$db;
 
	for my $c (split ' ', effective_conflicts($canon, $pc))
	{
		my $hard = 1;
		if($c =~ /^!!(.+)$/)   { $hard = 1; $c = $1; }
		elsif($c =~ /^!(.+)$/) { $hard = 0; $c = $1; }
		next unless $hard;
		for my $k (keys %universe)
		{
			next if $k eq $canon;
			return $k if _conflict_matches($c, $k);
		}
	}
	for my $k (keys %universe)
	{
		next if $k eq $canon;
		my $opc = _plan_pc_for_key($k, $db, $chosen);
		next unless $opc;
		for my $c (split ' ', effective_conflicts($k, $opc))
		{
			my $hard = 1;
			if($c =~ /^!!(.+)$/)   { $hard = 1; $c = $1; }
			elsif($c =~ /^!(.+)$/) { $hard = 0; $c = $1; }
			next unless $hard;
			return $k if _conflict_matches($c, $canon);
		}
	}
	return undef;
}
 
# resolves ONE dependency token (a %tag, a "?"-prefixed soft dep, or a
# plain "name[:slot][op val]") against the in-progress plan. every
# success path returns (1, $decided, $chosen, $canon) -- possibly the
# very same $decided/$chosen hashrefs passed in, when nothing about the
# plan needed to change (the common case: already installed, or already
# resolved earlier in this same plan) -- and every failure path returns
# (0, "why"), EXCEPT a failed SOFT dep, which is not a failure of the
# plan at all (that is the whole point of a soft dep) and returns
# success with the plan unchanged (and no meaningful $canon), same as
# resolve_dep silently dropping one today.
# --- soft-dep resolution: self-contained, never backtracks anything
# outside itself -------------------------------------------------------
#
# a soft dep (pkg_deps_soft, or a "?"-prefixed edge already inside one)
# participates in ITS OWN resolution/ordering (including %tag candidate
# preference) but never blocks the plan and is never worth retrying
# because of something that fails LATER, elsewhere -- that would turn an
# intentionally-optional edge into a second, needless axis of the search
# (try the plan WITH it, then WITHOUT it, for every later failure), and
# "a soft dep never blocks" already has fixed, simple, well-tested
# meaning: resolve it in isolation, keep the result if it fully
# succeeds on its own merits, drop it silently otherwise. so this half
# has no continuation at all -- it is the plan's original, pre-CPS
# shape, kept exactly because that shape is exactly right for something
# self-contained.
sub _plan_soft_dep {
	my ($dep, $cur, $db, $decided, $chosen, $onstack) = @_;
	# same "@" strip as _plan_dep's own entry, and for the same reason:
	# no satisfiability meaning here, but left un-stripped it would
	# otherwise reach _plan_soft_named's parse_dep_token as an opaque,
	# unmatched literal name (or hide a real "%tag" one line below, since
	# a leading "@" means the "^%(.+)$" check here never even matches).
	# a single strip suffices -- by the time a token reaches here, any
	# "?" has already been consumed by whichever caller decided this was
	# the soft path, so at most one sigil is ever still in front.
	$dep =~ s/^@//;
	if($dep =~ /^%(.+)$/)
	{
		my $tag = $1;
		my $pin = portpin($cur, $tag);
		my $target = (defined $pin && $pin ne '') ? $pin : $decided->{$tag};
		if(defined $target)
		{
			my ($ok, $r1, $r2, $canon) = _plan_soft_named($target, $cur, $db, $decided, $chosen, $onstack);
			return (0) unless $ok;
			return (1, $r1, $r2) unless defined $canon;
			my %d2 = (%$r1, $tag => $canon);
			return (1, \%d2, $r2);
		}
		if(tag_satisfied($tag, $db))
		{
			my %d2 = (%$decided, $tag => installed_tag_provider($tag, $db));
			return (1, \%d2, $chosen);
		}
		my $providers = tag_providers()->{$tag};
		return (0) unless $providers && @$providers;
		for my $cand (sort { $a->{pref} <=> $b->{pref} } @$providers)
		{
			my ($ok, $r1, $r2, $canon) = _plan_soft_named($cand->{name}, $cur, $db, $decided, $chosen, $onstack);
			next unless $ok;
			my %d2 = (%$r1, $tag => $canon);
			return (1, \%d2, $r2);
		}
		return (0);
	}
	return _plan_soft_named($dep, $cur, $db, $decided, $chosen, $onstack);
}
 
sub _plan_soft_named {
	my ($tok_str, $cur, $db, $decided, $chosen, $onstack) = @_;
	my $tok = parse_dep_token($tok_str);
	my $key = slot_key($tok->{name}, $tok->{slot});
	if($db->{$key})
	{
		return (0) if defined $tok->{op} && !ver_satisfies($db->{$key}{ver}, $tok->{op}, $tok->{val});
		return (1, $decided, $chosen, $key);
	}
	my $portdir = find_portdir($tok->{name}, $tok->{slot});
	return (0) unless $portdir;
	my $pc = try_pkgconf($portdir);
	return (0) unless $pc;
	return (0) if defined $tok->{op} && $tok->{op} ne '=' && !ver_satisfies($pc->{pkg_ver}, $tok->{op}, $tok->{val});
	my $canon = slot_key($pc->{pkg_name}, resolve_slot($pc, $pc->{pkg_name}));
	die "PLAN_PUNT\n" if pconf_lookup($canon, 'SYSROOT');
	if($db->{$canon})
	{
		return (0) if defined $tok->{op} && !ver_satisfies($db->{$canon}{ver}, $tok->{op}, $tok->{val});
		return (1, $decided, $chosen, $canon);
	}
	return (0) if $onstack->{$canon};
	return (1, $decided, $chosen, $canon) if $chosen->{$canon};
	return (0) if _plan_reject_reason($canon, $pc, $db);
	my %c2 = (%$chosen, $canon => $pc);
	return (0) if _plan_conflict($canon, $pc, $db, \%c2);
	my %stack2 = (%$onstack, $canon => 1);
	my ($d, $c) = ($decided, \%c2);
	for my $sub (effective_deps($pc, $canon))
	{
		if($sub =~ s/^\?//)
		{
			my ($ok, $r1, $r2) = _plan_soft_dep($sub, $canon, $db, $d, $c, \%stack2);
			($d, $c) = ($r1, $r2) if $ok;
			next;
		}
		my ($ok, $r1, $r2) = _plan_soft_dep($sub, $canon, $db, $d, $c, \%stack2);
		return (0) unless $ok;
		($d, $c) = ($r1, $r2);
	}
	return (1, $d, $c, $canon);
}
 
# --- hard-dep resolution: continuation-passing, backtracks across the
# WHOLE remaining plan, not just the one tag being decided -------------
#
# every function below takes a final argument $k, "the rest of the
# entire search" -- everything that still needs to succeed AFTER this
# one dependency, all the way out to plan_resolution's own top-level
# request list. success means calling $k->($decided, $chosen) and
# returning WHATEVER it returns, unexamined; a %tag's candidate loop
# tries the next candidate not just when ITS OWN subtree fails, but
# whenever $k itself (the entire rest of the plan, tried under this
# candidate) ultimately fails too. this is what makes a conflict
# discovered arbitrarily far downstream -- a different top-level
# request, a sibling dependency three levels away, anything -- able to
# reach back and un-pick an EARLIER %tag choice that seemed perfectly
# fine when it was made, then re-try the rest of the plan under the
# alternative. a plain, non-tag edge has no alternative to retry, so it
# still just fails outright on conflict/cycle -- there is nothing here
# TO backtrack.
sub _plan_dep {
	my ($dep, $cur, $db, $decided, $chosen, $onstack, $k) = @_;
	spin_tick();
	# "@" (subslot-tracked, see record_subslot_dep's own comment) carries
	# no satisfiability meaning at all here -- only resolve_dep's own
	# REAL execution pass records a subslot edge, this planner only
	# checks whether a request CAN be satisfied -- so it is simply
	# stripped and ignored, same as resolve_dep's own while(1) loop
	# strips it before ever looking at the rest of the token (either
	# order, either alone, or combined with "?" below).
	my $soft = 0;
	while(1)
	{
		if($dep =~ s/^@//) { next; }
		if($dep =~ s/^\?//) { $soft = 1; next; }
		last;
	}
	if($soft)
	{
		my ($ok, $d2, $c2) = _plan_soft_dep($dep, $cur, $db, $decided, $chosen, $onstack);
		return $k->($ok ? $d2 : $decided, $ok ? $c2 : $chosen);
	}
	if($dep =~ /^%(.+)$/)
	{
		my $tag = $1;
		my $fold = sub {
			my ($tagk) = @_;
			return sub { my ($d2, $c2, $canon) = @_; my %d3 = (%$d2, $tag => $canon); return $tagk->(\%d3, $c2); };
		};
		# an explicit TARGET_$tag/TAG_$tag pin (global or under $cur's own
		# section) always wins, exactly like resolve_dep/portpin -- checked
		# BEFORE $decided, so a per-package pin can still legitimately
		# diverge from what every OTHER package sharing this tag agreed on.
		# neither has an ALTERNATIVE to try, so either just resolves once.
		my $pin = portpin($cur, $tag);
		if(defined $pin && $pin ne '')
		{
			return _plan_named($pin, $cur, $db, $decided, $chosen, $onstack, $fold->($k));
		}
		if(defined $decided->{$tag})
		{
			return _plan_named($decided->{$tag}, $cur, $db, $decided, $chosen, $onstack, $fold->($k));
		}
		if(tag_satisfied($tag, $db))
		{
			my $prov = installed_tag_provider($tag, $db);
			my %d2 = (%$decided, $tag => $prov);
			return $k->(\%d2, $chosen);
		}
		my $providers = tag_providers()->{$tag};
		unless($providers && @$providers)
		{
			return (0, "no port provides tag %$tag" . (defined $cur ? " (needed by $cur)" : ''));
		}
		my @sorted = sort { $a->{pref} <=> $b->{pref} } @$providers;
		my $lastfail;
		my $all_conflicts = 1;
		for my $cand (@sorted)
		{
			my ($ok, $r) = _plan_named($cand->{name}, $cur, $db, $decided, $chosen, $onstack, $fold->($k));
			return (1, $r) if $ok;
			$lastfail = $r;
			$all_conflicts = 0 unless $r =~ / conflicts with /;
		}
		# every candidate specifically conflicting (and nothing downstream
		# ever getting far enough to fail any OTHER way) is exactly the
		# case resolve_dep's own interactive_pick fallback already has
		# fixed wording for -- match it, rather than surfacing just the
		# LAST candidate's specific conflict (arbitrary, and silent about
		# every other candidate having failed the identical way).
		return (0, "no provider of %$tag could be installed without conflicting" . (defined $cur ? " (needed by $cur)" : ''))
		    if $all_conflicts && @sorted > 1;
		return (0, $lastfail);
	}
	return _plan_named($dep, $cur, $db, $decided, $chosen, $onstack, sub { my ($d2, $c2) = @_; return $k->($d2, $c2); });
}
 
# resolves a plain (tag-free) token to a concrete port, walking its own
# deps (via _plan_seq, below) if it is genuinely new to this plan, then
# invoking $k->($decided, $chosen, $canon) -- $canon is the fully
# resolved db-key form (pkg_name-based, slot included) even when
# $tok_str itself named a port by its directory instead (the static-
# multi-slot case). mirrors resolve_dep's own literal-key fast path (an
# exact installed match needs no portdir/pc at all) and install_pkg's
# canon computation (pkg_slot_use composition can only be known once pc
# is loaded, so a bare token that turns out