structured_pkix/

path.rs

//! Certification paths: which sequences of certificates lead from a
//! certificate to an anchor the caller trusts, and what that costs.
//!
//! One signature can have several valid paths, and a report shows them,
//! because a cross-certified provider is recognized under one scheme by one
//! path and under another by another. That is not the same as enumerating
//! every path: a certificate set somebody else controls can hold a
//! combinatorial number of them, and a browser asked for all of them stops
//! answering. So the search is bounded in every direction it can grow, and
//! when a bound is reached the answer says so. Silence about truncation
//! would be a worse answer than the truncation.
//!
//! Where the bound is on how many paths are returned, which paths are kept
//! is not the order they were found in. A second path to the same anchor
//! naming the same policies tells a reader nothing the first did not; a path
//! to another anchor, or one naming other policies, is the whole reason
//! several paths are shown at all. So a path that differs in either is kept
//! ahead of a repeat of one already held.
//!
//! An anchor is an input, never a discovery (RFC 5280 6.1): a self-signed
//! certificate that happens to sit in the same pool is a certificate like
//! any other, and a path that ends at one the caller did not name ends
//! nowhere.

mod error;
mod name_space;
mod policy;

pub use error::{BuildError, BuildResult};

use crate::algorithm::AlgorithmIdentifier;
use crate::certificate::{Certificate, Validity};
use crate::constraints::CertificateCount;
use crate::error::{Result, gate};
use crate::extension::Recognizer;
use crate::general_name::GeneralName;
use crate::key::PublicKeyInfo;
use crate::name::Name;
use name_space::{Admission, NameSpace};
use structured_asn1::memory::{Memory, OwnedMap, OwnedVec};
use structured_asn1::{BitString, Oid};

/// What the caller trusts, as the trust context named it.
///
/// A name and a key, because that is what an anchor is: the certificate it
/// was published in, where there is one, is kept for the report and is not
/// what makes it an anchor. Two anchors with the same name and different
/// keys are two anchors, and a path is built to each.
#[derive(Debug, Clone, Copy)]
pub struct Anchor<'a> {
    name: &'a Name<'a>,
    key: PublicKeyInfo<'a>,
    certificate: Option<&'a Certificate<'a>>,
}

impl<'a> Anchor<'a> {
    /// An anchor the trust context supplies as a name and a key.
    #[must_use]
    pub fn new(name: &'a Name<'a>, key: PublicKeyInfo<'a>) -> Self {
        Self {
            name,
            key,
            certificate: None,
        }
    }

    /// An anchor the trust context supplies as a certificate, whose subject
    /// and key it is. The certificate is not part of any path built to it
    /// (RFC 5280 6.1), and is kept so a report can name where the anchor
    /// came from and so that what it says about the names below it is
    /// obeyed.
    #[must_use]
    pub fn from_certificate(certificate: &'a Certificate<'a>) -> Self {
        Self {
            name: certificate.tbs().subject(),
            key: certificate.tbs().public_key(),
            certificate: Some(certificate),
        }
    }

    /// The name a certificate issued under this anchor carries as its issuer.
    #[must_use]
    pub fn name(&self) -> &'a Name<'a> {
        self.name
    }

    /// The public key information, as encoded, which is what verifies the
    /// signature of the certificate below it.
    #[must_use]
    pub fn key(&self) -> PublicKeyInfo<'a> {
        self.key
    }

    /// The certificate the anchor was published in, where the trust context
    /// had one.
    #[must_use]
    pub fn certificate(&self) -> Option<&'a Certificate<'a>> {
        self.certificate
    }

    /// Whether two anchors are the same one: the same name and the same key,
    /// which is what an anchor is.
    fn same(self, other: Self, execution: &Memory) -> Result<bool> {
        execution
            .charge_work(self.key.as_bytes().len().max(other.key.as_bytes().len()) as u64)
            .map_err(|reason| self.name.resource(reason))?;
        if self.key.as_bytes() != other.key.as_bytes() {
            return Ok(false);
        }
        self.name.matches(other.name, execution)
    }
}

/// What a verifier says about one signature.
///
/// The third answer is the one that matters: an algorithm this build cannot
/// verify is not a signature that passed. Collapsing it into a no would say
/// the certificate is broken, and into a yes would say it is good; both are
/// claims nobody made.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Verified {
    /// The signature is the issuer's over these bytes.
    Yes,
    /// The signature is not.
    No,
    /// This build cannot answer: the algorithm, the key or the parameters
    /// are outside what it verifies.
    Unsupported,
}

/// The key a certificate's signature is checked with, and the parameters
/// that are in force for it.
///
/// "If the public key algorithm parameters are absent, the working public key
/// parameters are inherited" from the certificate above (RFC 5280 6.1.2 (c)
/// and 6.1.4 (c)). A key written without them is not a key anything can be
/// checked with on its own: the curve or the group it belongs to is written
/// once, in an authority above it, and every key below stands in that same
/// one. A verifier handed the encoding alone would have to answer that it
/// cannot say, and a valid path would go unreported.
///
/// Where the key carries its own parameters, those are the ones in force and
/// nothing is inherited. This is the ordinary case: a named curve, an RSA
/// modulus, an Edwards key.
#[derive(Debug, Clone, Copy)]
pub struct WorkingKey<'a> {
    key: PublicKeyInfo<'a>,
    /// The parameters carried down, and the algorithm they belong to: they
    /// stand only for a key of that same algorithm.
    inherited: Option<(Oid<'a>, &'a [u8])>,
}

impl<'a> WorkingKey<'a> {
    /// A key that stands on its own, which is what a trust anchor's is: there
    /// is nothing above it to inherit from.
    #[must_use]
    pub fn standing(key: PublicKeyInfo<'a>) -> Self {
        Self {
            key,
            inherited: None,
        }
    }

    /// The key itself, as the certificate wrote it.
    #[must_use]
    pub fn key(self) -> PublicKeyInfo<'a> {
        self.key
    }

    /// The parameters in force: the key's own where it has them, and the ones
    /// carried down from above where it does not and belongs to the same
    /// algorithm.
    ///
    /// "If the certificate subjectPublicKey algorithm and the
    /// `working_public_key_algorithm` are different, set the
    /// `working_public_key_parameters` to null" (RFC 5280 6.1.4 (d)). Nothing
    /// is carried across a change of algorithm: a curve is not a modulus,
    /// and an authority on one algorithm certifying a key on another says
    /// nothing about how that key is written. Handing them over anyway gives
    /// a verifier a key described by parameters that are not its own, which
    /// it can only refuse.
    ///
    /// A key that writes an explicit null inherits exactly as one that omits
    /// its parameters does. The clause opens on "an algorithm field with
    /// null parameters or parameters are omitted" and gives the two one
    /// rule, so a key that writes a null and names the algorithm in force
    /// stands in what is in force, whatever a given algorithm's own encoding
    /// rules say about which of the two spellings it should have used. The
    /// same tolerance is `AlgorithmIdentifier::same_as`, and reading a null
    /// as a refusal here would refuse paths the profile builds.
    ///
    /// `None` says the algorithm takes none, which is not the same as a key
    /// whose parameters were inherited.
    #[must_use]
    pub fn parameters(self) -> Option<&'a [u8]> {
        if !self.key.algorithm().has_no_parameters() {
            return self.key.algorithm().parameters();
        }
        let (algorithm, inherited) = self.inherited?;
        (algorithm == self.key.algorithm().algorithm()).then_some(inherited)
    }

    /// The working key one certificate further down: this certificate's own
    /// key, standing in the parameters in force where it wrote none.
    ///
    /// The algorithm those parameters belong to travels with them, since a
    /// key further down inherits only from a key of its own algorithm.
    #[must_use]
    fn below(self, key: PublicKeyInfo<'a>) -> Self {
        let algorithm = self.key.algorithm().algorithm();
        Self {
            key,
            inherited: self.parameters().map(|held| (algorithm, held)),
        }
    }
}

/// Who checks a signature.
///
/// Which algorithms may verify what belongs to the algorithm registry rather
/// than to this crate, so the check is asked for rather than performed here.
/// A caller that supplies no verifier gets no path: nothing else in a path
/// binds one certificate to the next.
pub trait Verify {
    /// The original policy, provider or resource failure of this implementation.
    type Error;

    /// Whether the signature over `signed` is the one the key in `key`
    /// makes under `algorithm`.
    ///
    /// The key arrives with the parameters in force rather than as the
    /// encoding alone, since a certificate may omit them and stand in the
    /// ones an authority above it wrote.
    ///
    /// A key may also be offered before those are known: while a path is
    /// being looked for, an authority is asked about with the key exactly as
    /// its certificate wrote it, because what it stands in is above and
    /// above has not been reached. An implementation that cannot judge a key
    /// without parameters it was not given answers `Unsupported` rather than
    /// `No`. The two are not interchangeable here: `No` prunes the branch,
    /// and a key that merely could not be judged yet is asked about again
    /// from the anchor down.
    fn verify(
        &self,
        algorithm: &AlgorithmIdentifier<'_>,
        key: WorkingKey<'_>,
        signed: &[u8],
        signature: BitString<'_>,
        execution: &Memory,
    ) -> core::result::Result<Verified, Self::Error>;
}

/// Nothing is verified, which is what a caller without a registry has.
impl Verify for () {
    type Error = core::convert::Infallible;
    fn verify(
        &self,
        _algorithm: &AlgorithmIdentifier<'_>,
        _key: WorkingKey<'_>,
        _signed: &[u8],
        _signature: BitString<'_>,
        _execution: &Memory,
    ) -> core::result::Result<Verified, Self::Error> {
        Ok(Verified::Unsupported)
    }
}

/// Whether the search has run out of time.
///
/// There is no clock here: this crate builds without an operating system, so
/// wall time is something the caller watches and this asks about. The work
/// bound below is the one that always applies, and this one narrows it where
/// the caller can measure.
pub trait Watch {
    /// Whether the time the caller allowed has passed.
    fn out_of_time(&self) -> bool;
}

/// No clock, so no deadline: the work bound is what stops the search.
impl Watch for () {
    fn out_of_time(&self) -> bool {
        false
    }
}

/// What charges work and says whether there is any left.
///
/// The search holds the meter, and the planes that work out policies and
/// names are given it rather than a copy of what it counts: a plane with its
/// own budget is a second bound the caller never set, and one with none
/// spends whatever a list somebody else wrote asks for. One trait rather
/// than the search itself, so those planes do not carry the verifier, the
/// clock and the recognizer through their signatures to reach the counter.
pub(crate) trait Meter {
    /// Charges work, and says whether there is any budget left. Both the
    /// work bound and the caller's clock are answered here, since running
    /// out of either stops the same search.
    fn spend(&mut self, work: u64) -> Result<bool>;
}

/// No meter, so no bound: for asking a plane what it works out rather than
/// what it spends, which is what the tests of one plane are about.
impl Meter for () {
    fn spend(&mut self, _work: u64) -> Result<bool> {
        Ok(true)
    }
}

/// How far the search may go before it stops and says so.
///
/// Every direction a search can grow has a number here, because a
/// certificate set somebody else controls grows in all of them: deeper
/// chains, wider fan-out at each step, more paths that differ in one
/// certificate, more policies in each certificate. The defaults are what a
/// browser can spend on a document somebody sent, not what a server can
/// spend on its own inventory.
#[derive(Debug, Clone, Copy)]
pub struct Bounds {
    /// How many certificates a path may hold, the anchor aside.
    pub depth: usize,
    /// How many times a certificate may be entered at some depth.
    pub visited: usize,
    /// How many candidate issuers may be considered in total.
    pub edges: usize,
    /// How much work the checks along the way may cost.
    pub work: u64,
    /// How many paths may be returned.
    pub paths: usize,
    /// How many policies one path's working out may hold at once.
    pub policies: usize,
}

impl Default for Bounds {
    fn default() -> Self {
        Self {
            depth: 12,
            visited: 4_096,
            edges: 16_384,
            work: 1_000_000,
            paths: 8,
            policies: 1_024,
        }
    }
}

/// Which bound stopped the search, where one did.
///
/// A report says which, because the answers differ: a search that ran out of
/// paths has more to show, and a search that ran out of depth was looking in
/// the wrong place.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum Truncation {
    /// A path reached the depth bound and was not followed further.
    Depth,
    /// The count of entered certificates reached its bound.
    Visited,
    /// The count of considered candidates reached its bound.
    Edges,
    /// The checks along the way cost what the caller allowed.
    Work,
    /// The caller's clock ran out.
    Time,
    /// More paths were found than the caller asked for, and one that was
    /// found is not among the ones returned.
    Paths,
    /// Working out what a path was issued under grew past what the caller
    /// allowed it to hold, so that path was not settled.
    Policies,
}

impl Truncation {
    /// Whether reaching this bound ends the whole search rather than one
    /// branch of it.
    ///
    /// The counts of work, time, entered certificates and considered
    /// candidates are spent once for the whole search, so reaching one
    /// leaves nothing further to look at. Depth, room for paths and the size
    /// of a policy tree are reached by one branch or one path, and the
    /// search goes on to the next.
    fn halts(self) -> bool {
        matches!(self, Self::Work | Self::Time | Self::Visited | Self::Edges)
    }
}

/// One certification path: the certificates from the target up, the anchor
/// they lead to, and what the authorities along it agreed the target was
/// issued under.
#[derive(Debug)]
pub struct Path<'a> {
    certificates: OwnedVec<&'a Certificate<'a>>,
    anchor: Anchor<'a>,
    policies: OwnedVec<Oid<'a>>,
}

impl<'a> Path<'a> {
    /// The certificates, the target first and the one the anchor issued
    /// last. The anchor's own certificate is not among them.
    #[must_use]
    pub fn certificates(&self) -> &[&'a Certificate<'a>] {
        &self.certificates
    }

    /// The anchor this path ends at.
    #[must_use]
    pub fn anchor(&self) -> Anchor<'a> {
        self.anchor
    }

    /// The policies every authority along the path agreed the target was
    /// issued under, narrowed to the ones the caller asked about.
    ///
    /// Empty says the path names no policy the caller asked about, which is
    /// a path only because nobody along it demanded that it name one.
    ///
    /// A set rather than a list, and returned in one order whatever order
    /// the certificates wrote it in, so that two paths naming one set are
    /// told apart by walking them once.
    #[must_use]
    pub fn policies(&self) -> &[Oid<'a>] {
        &self.policies
    }

    /// How many certificates the path holds.
    #[must_use]
    pub fn len(&self) -> usize {
        self.certificates.len()
    }

    /// Whether the path holds no certificates, which no path this builder
    /// returns does.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.certificates.is_empty()
    }

    /// Whether two paths say the same thing: the same names carrying the
    /// same keys, up to the same anchor.
    ///
    /// Serial numbers and validity are not part of it, so an authority that
    /// re-issued its own certificate is one route rather than two. What
    /// makes a second path worth showing is that it goes somewhere else or
    /// says something else, and neither of those is a new serial number.
    fn same_route(
        &self,
        chain: &[&'a Certificate<'a>],
        anchor: Anchor<'a>,
        execution: &Memory,
    ) -> Result<bool> {
        if self.certificates.len() != chain.len() || !self.anchor.same(anchor, execution)? {
            return Ok(false);
        }
        for (ours, theirs) in self.certificates.iter().zip(chain) {
            execution
                .charge_work(
                    ours.tbs()
                        .public_key()
                        .as_bytes()
                        .len()
                        .max(theirs.tbs().public_key().as_bytes().len()) as u64,
                )
                .map_err(|reason| ours.tbs().subject().resource(reason))?;
            if ours.tbs().public_key().as_bytes() != theirs.tbs().public_key().as_bytes()
                || !ours
                    .tbs()
                    .subject()
                    .matches(theirs.tbs().subject(), execution)?
            {
                return Ok(false);
            }
        }
        Ok(true)
    }

    /// Whether a path would tell a reader what this one already told them:
    /// the same anchor, and the same policies. What is worth keeping when
    /// there is room for fewer paths than were found is one of each of
    /// these, not the first ones found.
    /// Both sets arrive in one order, which is what makes this a walk down
    /// the two rather than a search of one for each member of the other:
    /// the second is the square of a count the caller's policy ceiling
    /// allows, and it is repeated against every path being held.
    fn same_meaning(
        &self,
        anchor: Anchor<'a>,
        policies: &[Oid<'a>],
        execution: &Memory,
    ) -> Result<bool> {
        if !self.anchor.same(anchor, execution)? || self.policies.len() != policies.len() {
            return Ok(false);
        }
        for (ours, theirs) in self.policies.iter().zip(policies) {
            execution
                .charge_work(ours.as_bytes().len().max(theirs.as_bytes().len()) as u64)
                .map_err(|reason| self.anchor.name.resource(reason))?;
            if ours != theirs {
                return Ok(false);
            }
        }
        Ok(true)
    }
}

/// What the search found, and what it did not get to.
#[derive(Debug)]
pub struct Outcome<'a> {
    paths: OwnedVec<Path<'a>>,
    truncated: Option<Truncation>,
}

impl<'a> Outcome<'a> {
    fn empty(execution: &Memory) -> Self {
        Self {
            paths: execution.vector(),
            truncated: None,
        }
    }

    /// The paths, shortest first, and among paths of one length in the order
    /// the caller's inputs put them in.
    #[must_use]
    pub fn paths(&self) -> &[Path<'a>] {
        &self.paths
    }

    /// Which bound stopped the search, where one did. `None` says the search
    /// finished: every path there is, is here.
    #[must_use]
    pub fn truncated(&self) -> Option<Truncation> {
        self.truncated
    }

    /// Whether the search was stopped rather than finished, which a report
    /// must say rather than claim it enumerated everything.
    #[must_use]
    pub fn is_truncated(&self) -> bool {
        self.truncated.is_some()
    }
}

/// The interval the path is built for, in seconds from the epoch.
///
/// A signature is placed in an interval rather than at an instant, because
/// what a timestamp proves is an upper bound and the lower one is usually
/// unknown. A certificate takes part in a path only where it was valid
/// across the whole of it: resolving at one end would let a signature made
/// before a certificate existed pass on the strength of a later moment.
///
/// Seconds rather than a `Time`, because a `Time` is how a certificate wrote
/// a moment, and this interval is not something a certificate wrote.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Interval {
    from: i64,
    to: i64,
}

impl Interval {
    /// The interval between two moments, whichever way round the caller
    /// hands them: an interval is a pair of bounds, not an ordering.
    #[must_use]
    pub fn between(first: i64, second: i64) -> Self {
        Self {
            from: first.min(second),
            to: first.max(second),
        }
    }

    /// The interval that is one moment, which is what a caller has when the
    /// signing time is known exactly and nothing wider has to be covered.
    #[must_use]
    pub fn at(moment: i64) -> Self {
        Self {
            from: moment,
            to: moment,
        }
    }

    /// The earlier bound.
    #[must_use]
    pub fn from(self) -> i64 {
        self.from
    }

    /// The later bound.
    #[must_use]
    pub fn to(self) -> i64 {
        self.to
    }

    /// Whether a validity interval holds the whole of this one.
    fn inside(self, validity: Validity) -> bool {
        // These endpoints are ordinary POSIX labels. Zero nanoseconds always
        // fits Instant; compare lossless labels so :60 cannot alias :59.
        let from = crate::temporal::Instant::new(self.from, 0).expect("zero nanoseconds fits");
        let to = crate::temporal::Instant::new(self.to, 0).expect("zero nanoseconds fits");
        validity.not_before().instant() <= from && to <= validity.not_after().instant()
    }
}

/// What the caller was asking about, before any certificate was read.
///
/// The defaults are a validator with no policy of its own: it asks what the
/// authorities agreed on rather than whether they agreed on one thing, and
/// reads what the certificates say rather than overriding it. A caller with
/// a policy of its own says so here, and gets paths that satisfy it or none.
#[derive(Debug, Clone, Copy)]
pub struct Policy<'a> {
    /// The policies the caller is asking about. Empty asks about all of
    /// them, and a path then carries whatever its authorities agreed on.
    pub wanted: &'a [Oid<'a>],
    /// Whether every path must name a policy, rather than only those an
    /// authority along the way demanded it of.
    pub explicit: bool,
    /// Whether a policy one authority maps to another's is honoured.
    pub mapping: bool,
    /// Whether the identifier standing for any policy is read as the
    /// certificate meant it.
    pub any: bool,
}

impl Default for Policy<'_> {
    fn default() -> Self {
        Self {
            wanted: &[],
            explicit: false,
            mapping: true,
            any: true,
        }
    }
}

/// What the search charges for the checks it runs, so that a pool somebody
/// else controls cannot buy an unbounded amount of them. The numbers are
/// relative to each other rather than to any clock: a signature check is
/// what a path spends most of its budget on, and a name comparison is a
/// walk over two names.
mod cost {
    /// Reading an extension of a certificate the search is considering.
    pub(super) const EXTENSION: u64 = 8;
    /// Reaching for two names to compare them, before what they hold.
    pub(super) const NAME: u64 = 16;
    /// How many bytes of the two names one unit of work buys where they are
    /// compared. Comparing them reads both: the parts of a name holding
    /// several attributes are ordered against each other, and values that
    /// are not byte-identical are folded through to the end. What that
    /// costs is the size of what a pool somebody else wrote put there, so
    /// it is charged by that size rather than at a flat rate.
    pub(super) const COMPARED: u64 = 16;
    /// Asking the verifier about one signature.
    pub(super) const SIGNATURE: u64 = 1_024;
    /// Holding one certificate to the constraints above it.
    pub(super) const CHECK: u64 = 32;
    /// One node of a path's working out of what it was issued under.
    pub(super) const POLICY: u64 = 4;
    /// Looking at one entry of a list a document decides the length of: a
    /// policy a certificate names, a mapping it declares, a region an
    /// authority wrote, a node of the working out being indexed.
    ///
    /// Charged per entry rather than per list, because the length is what
    /// somebody else chose. What the entry holds is charged where it is
    /// read, which for most of these is a lookup in an index and nothing
    /// more.
    pub(super) const ENTRY: u64 = 4;
    /// How many bytes of a certificate one unit of work buys where the whole
    /// of it is read, which is where its identity is taken.
    pub(super) const HASHED: u64 = 64;
}

/// Everything the search asks of the caller: what is trusted, when, how far
/// to look, what is being asked about, and who answers the questions this
/// crate does not.
///
/// One value rather than a row of arguments, because these travel together:
/// a path built against other anchors, or for another interval, is another
/// question rather than the same one asked differently.
pub struct Context<'a, 'p, V: Verify, W: Watch, R: Recognizer> {
    /// The current operation's shared execution and storage domain.
    /// Retained certificate accounts never implicitly finance this search.
    pub execution: &'p Memory,
    /// The anchors a path may end at, in the order a report should prefer.
    pub anchors: &'p [Anchor<'a>],
    /// The interval the path is built for.
    pub interval: Interval,
    /// How far the search may go before it stops and says so.
    pub bounds: Bounds,
    /// What the caller is asking about the policies a path was issued under.
    pub policy: Policy<'a>,
    /// Who checks a signature.
    pub verifier: &'p V,
    /// Who says the time the caller allowed has passed.
    pub watch: &'p W,
    /// Which extensions a scheme understands beyond the ones this crate
    /// reads, since a critical extension nobody understood is a certificate
    /// no path goes through.
    pub recognizer: &'p R,
}

/// The state a search carries, so the bounds are counted in one place.
struct Search<'a, 'p, V: Verify, W: Watch, R: Recognizer> {
    execution: &'p Memory,
    /// The candidates as the caller supplied them, unread until a path
    /// needs one.
    supplied: &'p [&'a Certificate<'a>],
    /// The certificate the question is about, which is not a candidate
    /// issuer of itself.
    target: &'a Certificate<'a>,
    /// The candidates folded to one each, worked out the first time the
    /// search looks for an issuer.
    ///
    /// Not before then: a target an anchor issued is settled by the anchors
    /// alone, and reading a pool of certificates no path goes through would
    /// spend the budget that answer needs before the answer is reached. A
    /// document may carry any number of them, so that is a path a caller
    /// holds the whole of being reported as left out.
    pool: Option<OwnedVec<&'a Certificate<'a>>>,
    anchors: &'p [Anchor<'a>],
    interval: Interval,
    bounds: Bounds,
    policy: Policy<'a>,
    verifier: &'p V,
    watch: &'p W,
    recognizer: &'p R,
    visited: usize,
    edges: usize,
    spent: u64,
    /// The bound that ended the search, where one did.
    halted: Option<Truncation>,
    /// What a bound left out without ending the search.
    noted: Option<Truncation>,
    found: OwnedVec<Path<'a>>,
    /// What the verifier has already said, so that a subpath shared by many
    /// paths costs one check rather than one per path. Two certificates
    /// stand for one answer here by where their bytes are, since that is
    /// what was handed to the verifier; a second copy of one certificate is
    /// a second entry and not a wrong one.
    signatures: OwnedMap<(usize, usize, usize), Verified>,
    /// What each certificate says about itself, which does not depend on
    /// where in a path it sits. A cross-certified pool reaches the same
    /// certificate at many depths and on many chains, and reading its
    /// extensions again each time would charge a caller once per visit for
    /// an answer that cannot have changed.
    properties: OwnedMap<usize, Properties>,
}

/// What one certificate says about itself, worked out once.
#[derive(Debug, Clone, Copy)]
struct Properties {
    /// Whether it can stand in a path at all: valid across the interval, and
    /// carrying no critical extension nobody understood.
    usable: bool,
    /// What it says about issuing certificates, or `None` where it says it
    /// issues none.
    issues: Option<crate::constraints::BasicConstraints>,
    /// Whether it was issued to the name that issued it.
    self_issued: bool,
    /// Whether it is an anchor's own certificate: it carries the name and
    /// key of one, and signs itself. Both, because a certificate carrying an
    /// anchor's identity under somebody else's signature is a link to that
    /// anchor rather than the anchor.
    publishes_itself: bool,
}

impl<V: Verify, W: Watch, R: Recognizer> Meter for Search<'_, '_, V, W, R> {
    fn spend(&mut self, work: u64) -> Result<bool> {
        Self::spend(self, work)
    }
}

impl<V: Verify, W: Watch, R: Recognizer> Search<'_, '_, V, W, R> {
    /// Charges work, and says whether the search may go on.
    fn spend(&mut self, work: u64) -> Result<bool> {
        debug_assert!(self.spent <= self.bounds.work);
        if work > self.bounds.work - self.spent {
            self.stop(Truncation::Work);
            return Ok(false);
        }
        self.execution
            .charge_work(work)
            .map_err(|reason| self.target.tbs().subject().resource(reason))?;
        self.spent += work;
        if self.watch.out_of_time() {
            self.stop(Truncation::Time);
            return Ok(false);
        }
        Ok(true)
    }

    /// Charges for comparing two names, by what comparing them reads.
    ///
    /// Before the comparison rather than after it: a bound that is charged
    /// once the work is done is a bound the last comparison was never held
    /// to, and a pool of long names is a set of last comparisons.
    fn spend_names(&mut self, left: &Name<'_>, right: &Name<'_>) -> Result<bool> {
        // Admit the metadata scan before finding the widest RDN. Both counts
        // are bounded by their borrowed encodings; their sum fits u64.
        let parts = left.parts().len() as u64 + right.parts().len() as u64;
        if !self.spend(parts)? {
            return Ok(false);
        }
        let bytes = left.as_bytes().len() as u64 + right.as_bytes().len() as u64;
        let rounds = sorting_rounds(left).max(sorting_rounds(right));
        let work = rounds
            .checked_mul(bytes / cost::COMPARED)
            .and_then(|work| work.checked_add(cost::NAME))
            .ok_or_else(|| left.resource(structured_asn1::memory::MemoryError::WorkExceeded))?;
        self.spend(work)
    }

    /// Local policy-tree bounds truncate; aggregate resource failures abort.
    fn policy<T>(
        &mut self,
        result: core::result::Result<T, policy::Overflow>,
    ) -> Result<Option<T>> {
        match result {
            Ok(value) => Ok(Some(value)),
            Err(policy::Overflow::Limit) => {
                self.stop(Truncation::Policies);
                Ok(None)
            }
            Err(policy::Overflow::Resource(error)) => Err(error),
        }
    }

    /// Records which bound stopped the search, keeping the first one: it is
    /// the one that decided the answer.
    fn stop(&mut self, at: Truncation) {
        // Two kinds of bound, kept apart because they are two statements. A
        // bound that ends the whole search decides the answer and is what
        // the answer reports; one that ended a branch or left a path out is
        // worth saying only where nothing ended the search. Keeping one
        // field for both would let the first branch to run out of depth
        // swallow the count of certificates that later stopped everything,
        // and the search would carry on past a bound it had reached while
        // naming the wrong reason for what it did not do.
        let recorded = if at.halts() {
            &mut self.halted
        } else {
            &mut self.noted
        };
        if recorded.is_none() {
            *recorded = Some(at);
        }
    }

    /// Whether a bound has ended the search.
    ///
    /// Running out of room for paths is not one of them: what is worth
    /// keeping is decided when a path is settled rather than by which was
    /// found first, so a search that has filled its room keeps looking for
    /// something better to put in it, under the bounds that remain.
    fn stopped(&self) -> bool {
        self.halted.is_some()
    }

    /// What the answer says about being incomplete: the bound that ended the
    /// search where one did, and otherwise what was left out along the way.
    fn truncated(&self) -> Option<Truncation> {
        self.halted.or(self.noted)
    }

    /// Asks the verifier about one signature, or repeats what it said about
    /// the same one before. `None` says the budget ran out before it could
    /// be asked, which is not an answer about the signature.
    ///
    /// The charge is here rather than at the call sites, and only where the
    /// verifier is actually reached. Repeating what is already known costs a
    /// lookup, and charging a cryptographic check for it would undo what
    /// remembering the answer was for: a sub-path shared by many chains
    /// would spend the budget once per chain that walks it, and the search
    /// would stop before reaching paths it had already done the work for.
    fn verified(
        &mut self,
        certificate: &Certificate<'_>,
        key: WorkingKey<'_>,
    ) -> BuildResult<Option<Verified>, V::Error, R::Error> {
        // The parameters are part of what was asked, not only the key: one
        // key standing in two different sets of inherited parameters is two
        // questions, and answering the second from the first would carry an
        // answer across paths that do not share what the key stands in.
        let at = (
            certificate.signed_bytes().as_ptr() as usize,
            key.key().as_bytes().as_ptr() as usize,
            key.parameters().map_or(0, |held| held.as_ptr() as usize),
        );
        if let Some(answer) = self
            .signatures
            .get(&at, self.execution)
            .map_err(|reason| certificate.tbs().subject().resource(reason))?
        {
            return Ok(Some(*answer));
        }
        if !self.spend(cost::SIGNATURE)? {
            return Ok(None);
        }
        // Admit the cache allocation before invoking the external verifier.
        self.signatures
            .try_insert(at, Verified::Unsupported)
            .map_err(|reason| certificate.tbs().subject().resource(reason))?;
        let answer = self
            .verifier
            .verify(
                &certificate.signature_algorithm(),
                key,
                certificate.signed_bytes(),
                certificate.signature(),
                self.execution,
            )
            .map_err(BuildError::Verification)?;
        *self
            .signatures
            .get_mut(&at, self.execution)
            .map_err(|reason| certificate.tbs().subject().resource(reason))?
            .expect("the admitted signature cache entry") = answer;
        Ok(Some(answer))
    }
}

/// Admits anchor-folding work before mutation in both local and aggregate budgets.
fn spend_anchor(
    context: &Context<'_, '_, impl Verify, impl Watch, impl Recognizer>,
    spent: &mut u64,
    halted: &mut Option<Truncation>,
    origin: &Name<'_>,
    work: u64,
) -> Result<bool> {
    debug_assert!(*spent <= context.bounds.work);
    if work > context.bounds.work - *spent {
        *halted = Some(Truncation::Work);
        return Ok(false);
    }
    if context.watch.out_of_time() {
        *halted = Some(Truncation::Time);
        return Ok(false);
    }
    context
        .execution
        .charge_work(work)
        .map_err(|reason| origin.resource(reason))?;
    *spent += work;
    Ok(true)
}

/// The anchors a search will look at, with the repeats among the caller's
/// folded away, and what folding them spent.
///
/// Two anchors of one name and one key are one anchor, and the paths to them
/// are one path. A trust context assembled from several stores hands the same
/// root over more than once, and every copy would buy an edge and a name
/// comparison to settle a path that was already settled, so a bound would
/// report the answer as truncated over nothing that was left out.
///
/// Folded by what makes two anchors one, which is the same name and the same
/// key however the name was written, and the same certificate or none behind
/// both. Folding by the bytes of the name instead would leave one key under
/// two spellings as two anchors, and placed in front of a key that does
/// verify they can spend a tight bound before it is reached: the path that
/// exists is then not returned, which is a lost answer rather than a charge.
///
/// The keys are grouped first, because they are compared as bytes and a trust
/// store's are all different: an anchor is looked at once, and the comparison
/// that reads two names runs only where a key was supplied twice, which is
/// the case being folded. Comparing every pair would be the square of a count
/// for the sake of the pairs that cannot match.
fn fold_anchors<'a>(
    context: &Context<'a, '_, impl Verify, impl Watch, impl Recognizer>,
    spent: &mut u64,
    halted: &mut Option<Truncation>,
) -> Result<OwnedVec<Anchor<'a>>> {
    let mut keyed: OwnedMap<&[u8], OwnedVec<usize>> = context.execution.map();
    let mut anchors: OwnedVec<Anchor<'a>> = context.execution.vector();
    'anchors: for anchor in context.anchors {
        let key = anchor.key().as_bytes();
        if !spend_anchor(
            context,
            spent,
            halted,
            anchor.name(),
            cost::CHECK + key.len() as u64 / cost::HASHED,
        )? {
            break;
        }

        let fail = |reason| anchor.name().resource(reason);
        if keyed.get(&key, context.execution).map_err(fail)?.is_none() {
            keyed
                .try_insert(key, context.execution.vector())
                .map_err(fail)?;
        }
        let group = keyed
            .get_mut(&key, context.execution)
            .map_err(fail)?
            .expect("the group was inserted before lookup");
        for at in group.iter() {
            let theirs: &Name<'_> = anchors[*at].name();
            let bytes = (theirs.as_bytes().len() as u64)
                .checked_add(anchor.name().as_bytes().len() as u64)
                .ok_or_else(|| {
                    anchor
                        .name()
                        .resource(structured_asn1::memory::MemoryError::WorkExceeded)
                })?;
            if !spend_anchor(
                context,
                spent,
                halted,
                anchor.name(),
                cost::NAME + bytes / cost::COMPARED,
            )? {
                break 'anchors;
            }
            if !theirs.matches(anchor.name(), context.execution)? {
                continue;
            }

            // The names and the key agree, and one thing is left that tells
            // two such anchors apart: what each was published in. A trust
            // context that supplied the anchor as a constrained certificate
            // bound the names below it, and the same name and key supplied
            // without one bound nothing. They are two statements about one
            // key, and folding them would let the order of the caller's list
            // decide which constraint holds and so whether a path exists at
            // all.
            let held = anchors[*at].certificate();
            let bytes = published_bytes(held)
                .checked_add(published_bytes(anchor.certificate()))
                .ok_or_else(|| {
                    anchor
                        .name()
                        .resource(structured_asn1::memory::MemoryError::WorkExceeded)
                })?;
            if !spend_anchor(
                context,
                spent,
                halted,
                anchor.name(),
                cost::CHECK + bytes / cost::HASHED,
            )? {
                break 'anchors;
            }
            if published_alike(held, anchor.certificate(), context.execution)? {
                continue 'anchors;
            }
        }
        group.try_push(anchors.len()).map_err(fail)?;
        anchors.try_push(*anchor).map_err(fail)?;
    }
    Ok(anchors)
}

/// The candidates of a pool, each of them once and the target not among
/// them.
///
/// A pool that holds one certificate twice holds one certificate, and folding
/// the copies before the search rather than at each step is what makes that
/// true of what the search spends as well as of what it finds. A pool
/// somebody else wrote may repeat a certificate leading nowhere as often as
/// it likes, and charging every copy would let the copies spend the search
/// before the issuer that does lead somewhere is reached.
///
/// The folding is itself charged, because it is itself work somebody else
/// decides the size of: the identity of a certificate is its bytes, and there
/// may be any number of certificates of any length.
fn fold_pool<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    pool: &[&'a Certificate<'a>],
    target: &'a Certificate<'a>,
) -> BuildResult<OwnedVec<&'a Certificate<'a>>, V::Error, R::Error> {
    let mut named: OwnedMap<usize, ()> = search.execution.map();
    let mut seen: OwnedMap<&[u8], ()> = search.execution.map();
    let mut unique = search.execution.vector();
    for candidate in pool {
        let bytes = candidate.as_bytes();

        // Looking at a candidate at all, which every one of them costs.
        if !search.spend(cost::CHECK)? {
            break;
        }

        // A pool that names one certificate over and over names it once,
        // and recognising that costs a pointer. Reading the whole encoding
        // is what telling a separately written copy from it costs, and
        // charging that for every repeat lets the repeats spend the search
        // before the issuer that does lead somewhere is reached.
        if named
            .try_insert(bytes.as_ptr() as usize, ())
            .map_err(|reason| candidate.tbs().subject().resource(reason))?
            .is_some()
        {
            continue;
        }
        if !search.spend(bytes.len() as u64 / cost::HASHED)? {
            break;
        }

        // The target is not a candidate issuer of itself, and a caller who
        // put it here was told that changes nothing. Leaving it among the
        // candidates makes that false of what the search spends: the cycle
        // check refuses it, but only after an edge and a name comparison
        // have been charged for it, so a bound tight enough to notice
        // reports the answer as truncated over a certificate that could
        // never have been followed.
        search
            .execution
            .charge_work(bytes.len().max(target.as_bytes().len()) as u64)
            .map_err(|reason| candidate.tbs().subject().resource(reason))?;
        if bytes != target.as_bytes()
            && seen
                .try_insert(bytes, ())
                .map_err(|reason| candidate.tbs().subject().resource(reason))?
                .is_none()
        {
            unique
                .try_push(*candidate)
                .map_err(|reason| candidate.tbs().subject().resource(reason))?;
        }
    }
    Ok(unique)
}

/// Builds the paths from one certificate to the anchors the caller trusts.
///
/// The pool is where issuers are looked for, and holding the target itself
/// changes nothing: a certificate never appears twice in one path
/// (RFC 5280 6.1), so it cannot be its own issuer.
///
/// # Errors
///
/// A spent budget, which says this run gave up rather than that the
/// certificates are wrong.
pub fn build<'a, V: Verify, W: Watch, R: Recognizer>(
    target: &'a Certificate<'a>,
    pool: &[&'a Certificate<'a>],
    context: &Context<'a, '_, V, W, R>,
) -> BuildResult<Outcome<'a>, V::Error, R::Error> {
    // A path ends at an anchor, so a caller who named none has asked a
    // question whose complete answer is no paths. Reading the pool to find
    // that out spends a budget on work that cannot change the answer, and a
    // bound reached while doing it would report the one conclusive answer
    // there is as though something had been left out, which reads to a
    // caller as worth asking again.
    if context.anchors.is_empty() {
        return Ok(Outcome::empty(context.execution));
    }

    // And a path is built for a moment. A target the caller's interval does
    // not hold is not one any path can end at, whatever the anchors and the
    // pool say, so folding them to find that out is the same spending on an
    // answer that cannot change. The question is asked again where every
    // certificate of a path is held to it, and asking it here first is what
    // keeps a bound from calling this conclusive answer a partial one.
    if !context.interval.inside(target.tbs().validity()) {
        return Ok(Outcome::empty(context.execution));
    }

    let mut spent = 0u64;
    let mut halted = None;
    let anchors = fold_anchors(context, &mut spent, &mut halted)?;
    if halted.is_some() {
        return Ok(Outcome {
            paths: context.execution.vector(),
            truncated: halted,
        });
    }

    let mut search = Search {
        execution: context.execution,
        supplied: pool,
        target,
        pool: None,
        anchors: &anchors,
        interval: context.interval,
        bounds: context.bounds,
        policy: context.policy,
        verifier: context.verifier,
        watch: context.watch,
        recognizer: context.recognizer,
        visited: 0,
        edges: 0,
        spent,
        halted,
        noted: None,
        found: context.execution.vector(),
        signatures: context.execution.map(),
        properties: context.execution.map(),
    };

    // The certificate an anchor was published in is not a step on a path to
    // that anchor: "when the trust anchor is provided in the form of a
    // self-signed certificate, this self-signed certificate is not included
    // as part of the prospective certification path" (RFC 5280 6.1). That
    // holds of the first position as much as of the rest, and the rest
    // already keep it. Settling such a target reports the anchor as issued
    // by itself, which is the anchor named twice rather than a chain of
    // authority, and it is what a caller asking about a root would read as
    // the root having been certified by somebody.
    //
    // A self-signed certificate can chain nowhere else, since the only name
    // that issued it is its own, so there is nothing further to look for
    // and the empty answer is the whole of it.
    let known = properties(&mut search, target)?;
    let mut chain = context.execution.vector();
    if known.usable && !known.publishes_itself {
        walk(&mut search, target, &mut chain)?;
    }

    // Shortest first: a longer path to the same place says the same thing
    // through more parties, and a reader reads the first one. Among paths
    // of one length the order is the one the caller's inputs put them in,
    // which is what makes the same inputs give the same answer twice.
    // Include the discovery position in the comparison so the allocation-free
    // heap sort preserves the documented order among equal-length paths.
    let mut ordered = context.execution.vector();
    let found = core::mem::replace(&mut search.found, context.execution.vector());
    for (position, path) in found.into_iter().enumerate() {
        ordered
            .try_push((position, path))
            .map_err(|reason| target.tbs().subject().resource(reason))?;
    }
    ordered
        .try_sort_unstable_by(|left, right| {
            Ok::<_, structured_asn1::memory::MemoryError>(
                (left.1.len(), left.0).cmp(&(right.1.len(), right.0)),
            )
        })
        .map_err(|error| target.tbs().subject().resource(error.into()))?;
    for (_, path) in ordered {
        search
            .found
            .try_push(path)
            .map_err(|reason| target.tbs().subject().resource(reason))?;
    }
    let truncated = search.truncated();
    Ok(Outcome {
        paths: search.found,
        truncated,
    })
}

/// Follows one certificate up: to every anchor that could have issued it,
/// and to every certificate in the pool that could have.
fn walk<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    certificate: &'a Certificate<'a>,
    chain: &mut OwnedVec<&'a Certificate<'a>>,
) -> BuildResult<(), V::Error, R::Error> {
    // One candidate cursor per active certificate replaces recursive DFS.
    // Both stacks are admitted by the request domain before their growth.
    let mut cursors = search.execution.vector();
    let mut entering = certificate;
    'enter: loop {
        if search.stopped() {
            break;
        }
        if search.visited >= search.bounds.visited {
            search.stop(Truncation::Visited);
            break;
        }
        search.visited += 1;
        if !search.spend(cost::CHECK)? {
            break;
        }
        if chain.len() >= search.bounds.depth {
            search.stop(Truncation::Depth);
            break;
        }
        chain
            .try_push(entering)
            .map_err(|reason| entering.tbs().subject().resource(reason))?;
        cursors
            .try_push(0usize)
            .map_err(|reason| entering.tbs().subject().resource(reason))?;
        settle(search, entering, chain)?;

        loop {
            if search.stopped() {
                break 'enter;
            }
            let current = *chain.last().expect("the active DFS certificate");
            let cursor = cursors.last_mut().expect("its candidate cursor");
            if let Some(candidate) = next_issuer(
                search,
                current,
                chain,
                chain.len() >= search.bounds.depth,
                cursor,
            )? {
                entering = candidate;
                continue 'enter;
            }
            chain.pop();
            cursors.pop();
            if chain.is_empty() {
                break 'enter;
            }
        }
    }
    chain.clear();
    Ok(())
}

/// Ends the chain at every anchor that issued the certificate on top of it,
/// which is where a path becomes one.
fn settle<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    certificate: &'a Certificate<'a>,
    chain: &[&'a Certificate<'a>],
) -> BuildResult<(), V::Error, R::Error> {
    for at in 0..search.anchors.len() {
        let anchor = search.anchors[at];
        if search.stopped() {
            break;
        }
        if search.edges >= search.bounds.edges {
            search.stop(Truncation::Edges);
            break;
        }
        search.edges += 1;
        if !search.spend_names(certificate.tbs().issuer(), anchor.name())? {
            break;
        }
        if !certificate
            .tbs()
            .issuer()
            .matches(anchor.name(), search.execution)?
        {
            continue;
        }
        // The signature is checked where the path is walked from the anchor
        // down, since that is where the parameters a key may stand in are
        // known. Nothing is lost by not asking here: this is the last edge
        // of the path, so the check is one step away either way.
        let Some(policies) = validate(search, chain, anchor)? else {
            continue;
        };
        keep(search, chain, anchor, policies)?;
    }
    Ok(())
}

/// Puts a settled path among the ones that will be returned, where there is
/// room for it or where what it says is not already there.
///
/// A repeat of a route already held is dropped and is not truncation: it is
/// the same path spelled through a re-issued certificate, and nothing was
/// lost by not showing it twice. Dropping a path that does say something
/// else is truncation, and so is making room for one by putting out a
/// repeat of something already shown.
/// The chain is held rather than copied until there is somewhere to put it:
/// a cross-certified pool settles the same route many times over, and a copy
/// made before the question is asked is a copy made for every one of them.
fn keep<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    chain: &[&'a Certificate<'a>],
    anchor: Anchor<'a>,
    policies: OwnedVec<Oid<'a>>,
) -> BuildResult<(), V::Error, R::Error> {
    // Telling this path from the ones already held reads their names, the
    // keys under them and their policies again, once per path held, and how
    // long a name or a key encoding is is the pool's to decide. Both are
    // read from the front, so two of one length that part near the end are
    // read almost to the end. The charge is taken for the whole scan before
    // it runs.
    //
    // Obeyed where there is anything to compare against: a charge that the
    // budget cannot meet is the answer that this scan is not going to
    // happen, and running it anyway is the reading the charge exists to
    // stop. What is then not known is whether this route says what a held
    // one already says, so it is not shown, and the answer is marked
    // truncated by the charge that failed.
    //
    // Where nothing is held there is nothing to compare and no scan to
    // refuse. The first path a search settles is kept whatever the budget
    // says, since dropping it would lose an answer for work nobody was
    // going to do.
    let held = search.found.len() as u64;
    if held > 0 {
        if !search.spend(chain.len() as u64)? {
            return Ok(());
        }
        let overflow = || {
            anchor
                .name
                .resource(structured_asn1::memory::MemoryError::WorkExceeded)
        };
        let mut read = 0u64;
        for certificate in chain {
            let tbs = certificate.tbs();
            let bytes =
                tbs.subject().as_bytes().len() as u64 + tbs.public_key().as_bytes().len() as u64;
            read = read.checked_add(bytes).ok_or_else(overflow)?;
        }
        let each = (read / cost::COMPARED)
            .checked_add(cost::NAME)
            .and_then(|work| work.checked_add(policies.len() as u64))
            .ok_or_else(overflow)?;
        let work = each.checked_mul(held).ok_or_else(overflow)?;
        if !search.spend(work)? {
            return Ok(());
        }
    }

    // The same route saying the same thing. A re-issued certificate is one
    // route spelled twice, but an authority that re-issued under another
    // policy said something else through it, and that is precisely the
    // distinct outcome several paths exist to preserve: dropping it as a
    // repeat would throw away the answer while reporting nothing missing.
    for held in &search.found {
        if held.same_route(chain, anchor, search.execution)?
            && held.same_meaning(anchor, &policies, search.execution)?
        {
            return Ok(());
        }
    }
    if search.found.len() < search.bounds.paths {
        let mut certificates = search.execution.vector();
        certificates
            .try_extend_from_slice(chain)
            .map_err(|reason| anchor.name.resource(reason))?;
        search
            .found
            .try_push(Path {
                certificates,
                anchor,
                policies,
            })
            .map_err(|reason| anchor.name.resource(reason))?;
        return Ok(());
    }

    // No room. A path saying something none of the held ones say is worth
    // more than a second path saying what one of them already said, so it
    // takes the place of the last such repeat. Either way a path that was
    // found is not being returned, which the answer has to say.
    search.stop(Truncation::Paths);
    for held in &search.found {
        if held.same_meaning(anchor, &policies, search.execution)? {
            return Ok(());
        }
    }
    let mut repeat = None;
    for at in (0..search.found.len()).rev() {
        let candidate = &search.found[at];
        let mut count = 0;
        for held in &search.found {
            if held.same_meaning(candidate.anchor, &candidate.policies, search.execution)? {
                count += 1;
                if count > 1 {
                    break;
                }
            }
        }
        if count > 1 {
            repeat = Some(at);
            break;
        }
    }
    if let Some(at) = repeat {
        // The repeat is taken out and the new path put on the end, rather
        // than dropped into the slot the repeat held. Paths of one length
        // come back in the order the caller's inputs put them in, and the
        // sort that arranges them is by length alone: a path written into
        // an earlier slot would sit in front of paths found before it, and
        // nothing afterwards would move it back.
        let moves = core::mem::size_of_val(&search.found[at..]);
        search
            .execution
            .charge_work(moves as u64)
            .map_err(|reason| anchor.name.resource(reason))?;
        search.found[at..].rotate_left(1);
        search.found.pop();
        let mut certificates = search.execution.vector();
        certificates
            .try_extend_from_slice(chain)
            .map_err(|reason| anchor.name.resource(reason))?;
        search
            .found
            .try_push(Path {
                certificates,
                anchor,
                policies,
            })
            .map_err(|reason| anchor.name.resource(reason))?;
    }
    Ok(())
}

/// Follows the chain further up: to every certificate in the pool that could
/// have issued the one on top of it.
///
/// `deepest` says the chain has reached the length the caller allowed, so
/// that a candidate found here is one the depth bound refuses to step into
/// rather than one to walk. It is what turns the bound into a report: the
/// answer says it was reached where a candidate was there to be refused,
/// and says nothing where the chain had nowhere to go regardless.
fn next_issuer<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    certificate: &'a Certificate<'a>,
    chain: &[&'a Certificate<'a>],
    deepest: bool,
    at: &mut usize,
) -> BuildResult<Option<&'a Certificate<'a>>, V::Error, R::Error> {
    // The candidates, folded the first time one is looked for. Every later
    // position reads the same folded list.
    if search.pool.is_none() {
        let supplied = search.supplied;
        let target = search.target;
        search.pool = Some(fold_pool(search, supplied, target)?);
    }
    // By position rather than by iterator: what follows this borrows the
    // search to walk further up, and a candidate is one shared reference,
    // so reading it out ends the borrow the loop would otherwise hold.
    while let Some(candidate) = search.pool.as_ref().and_then(|pool| pool.get(*at)).copied() {
        *at += 1;
        if search.stopped() {
            break;
        }
        if search.edges >= search.bounds.edges {
            search.stop(Truncation::Edges);
            break;
        }
        search.edges += 1;
        if !search.spend_names(certificate.tbs().issuer(), candidate.tbs().subject())? {
            break;
        }
        // A certificate appears once in a path (RFC 5280 6.1), which is
        // also what keeps a cycle from being followed round.
        //
        // Asked of where the certificate is rather than of what it holds.
        // The pool was folded before the search so that no two candidates
        // carry the same bytes, and the target was taken out of it, so two
        // certificates of one chain hold the same bytes exactly when they
        // are the same one. Comparing the encodings would read both from
        // end to end for an answer their addresses already give, and a pool
        // of long re-issued certificates that part only near the end makes
        // that a full scan per candidate per position of the chain, where
        // the charge just taken covers two names. It is the identity the
        // rest of the search already works by: what a certificate says
        // about itself is remembered under the same address.
        let mut repeated = false;
        for held in chain {
            search
                .execution
                .charge_work(1)
                .map_err(|reason| certificate.tbs().subject().resource(reason))?;
            if core::ptr::eq(held.as_bytes(), candidate.as_bytes()) {
                repeated = true;
                break;
            }
        }
        if repeated {
            continue;
        }
        if !certificate
            .tbs()
            .issuer()
            .matches(candidate.tbs().subject(), search.execution)?
        {
            continue;
        }
        // Everything cheap first, and the signature last: a candidate that
        // could not have issued anything, or was not valid when it would
        // have had to be, is refused for what it says rather than for what
        // its key does, and the check that costs the most is the one a
        // hostile pool would most like to buy in quantity.
        //
        // The certificate an anchor was published in is not a link in a path
        // to that anchor: "when the trust anchor is provided in the form of
        // a self-signed certificate, this self-signed certificate is not
        // included as part of the prospective certification path"
        // (RFC 5280 6.1). Walking into it would produce the path that was
        // already found, spelled one certificate longer.
        //
        // Self-signed is the whole of that rule, and names are not enough to
        // establish it. A provider recognized under two schemes has its
        // identity certified by both, and an authority rolling its key over
        // certifies the new key with the old one: the first carries the
        // anchor's name and key under somebody else's signature, the second
        // carries one name on both sides under the old key's. Both are
        // ordinary links, and skipping either would lose a whole route while
        // saying nothing about having lost it.
        let known = properties(search, candidate)?;
        if known.publishes_itself || !known.usable || known.issues.is_none() {
            continue;
        }
        if deepest {
            // A candidate that names itself the issuer and can issue is a
            // branch the depth bound is refusing, and refusing it is what
            // the answer has to say. Whether its signature would have held
            // is exactly what the search does not get to find out, so the
            // check is not spent on a candidate it will not follow. Once
            // one is refused the rest say the same thing, and the search
            // has other branches to spend its budget on.
            search.stop(Truncation::Depth);
            break;
        }
        // The key is asked about here, where the answer prunes the branch: a
        // candidate that did not sign this certificate is not walked into,
        // and a pool of such candidates costs one check each rather than a
        // subtree each.
        //
        // It is asked as the certificate wrote it, since what a key standing
        // in parameters written above stands in is exactly what this search
        // has not found yet. So only a definite no prunes. A registry that
        // cannot judge a key on those terms says that it cannot rather than
        // saying no, and the branch is walked so the question can be put
        // again from the anchor down, where the parameters in force are
        // known. Refusing on anything short of a no would lose whole routes.
        //
        // Asking only where the key carries its own parameters would prune
        // almost nothing: an algorithm that takes none writes a null, which
        // is written the same way as omitting them, so a pool of ordinary
        // wrong-key authorities would be walked in full and could spend the
        // whole budget before the one that signed this certificate is
        // reached. What tells the two apart is the registry's answer, and
        // the registry is who this asks.
        let key = WorkingKey::standing(candidate.tbs().public_key());
        let Some(answer) = search.verified(certificate, key)? else {
            break;
        };
        if answer == Verified::No {
            continue;
        }
        return Ok(Some(candidate));
    }
    Ok(None)
}

/// Whether two anchors were published the same way: in the same certificate,
/// or in none. It is the last thing that tells apart two anchors of one name
/// and one key, because the certificate an anchor was published in is what
/// says how the names below it are constrained.
fn published_alike(
    left: Option<&Certificate<'_>>,
    right: Option<&Certificate<'_>>,
    execution: &Memory,
) -> Result<bool> {
    match (left, right) {
        (None, None) => Ok(true),
        (Some(ours), Some(theirs)) => binds_alike(ours, theirs, execution),
        _ => Ok(false),
    }
}

/// Whether two certificates of one name and one key say the same thing about
/// the names below them.
///
/// By what is read rather than by every byte. An anchor's certificate is not
/// a link in any path: the one thing the search takes from it is what it
/// says about the space below, which is the regions it names, and nothing
/// else about it is consulted anywhere. A trust store holding a root
/// re-issued with a new serial, a new validity or a new signature holds one
/// statement of trust written twice, and keeping both makes the search try
/// each of them at every position where an anchor could end a path: a tight
/// bound on edges is then spent on copies, and a path through the one that
/// matches is lost.
///
/// The one extension compared is therefore the one enforced. Basic
/// constraints were compared here while an anchor's regions were honoured
/// only under an asserted authority bit; they are not read of an anchor any
/// more, and comparing them would split anchors that behave identically.
fn binds_alike(
    ours: &Certificate<'_>,
    theirs: &Certificate<'_>,
    execution: &Memory,
) -> Result<bool> {
    if same(ours, theirs) {
        return Ok(true);
    }
    let ours = ours
        .tbs()
        .extensions()
        .get(crate::oid::NAME_CONSTRAINTS, execution)?;
    let theirs = theirs
        .tbs()
        .extensions()
        .get(crate::oid::NAME_CONSTRAINTS, execution)?;
    Ok(match (ours, theirs) {
        (None, None) => true,
        (Some(ours), Some(theirs)) => {
            ours.is_critical() == theirs.is_critical() && ours.value() == theirs.value()
        }
        _ => false,
    })
}

/// How many times comparing a name may read it.
///
/// Once, where every part holds one attribute: the parts line up in the
/// order they were written and each pair is compared where it stands. A part
/// holding several is a set, whose order carries no meaning, so both sides
/// are put in order before they are lined up, and a sort of `n` reads its
/// input about `log2(n)` times over. The widest part decides it, since one
/// wide part is enough to pay for.
///
/// A document decides how many attributes a part holds, so this factor is
/// theirs to choose too: without it a name of one very wide part is charged
/// as though it were read straight through, and the sort runs to the end
/// with nothing left to stop it.
fn sorting_rounds(name: &Name<'_>) -> u64 {
    let widest = name
        .parts()
        .iter()
        .map(|part| part.attributes().len())
        .max()
        .unwrap_or(1)
        .max(1);
    u64::from(widest.ilog2()) + 1
}

/// How many bytes comparing an anchor's published certificate reads on its
/// side, which is none where it was published as a name and a key.
fn published_bytes(certificate: Option<&Certificate<'_>>) -> u64 {
    certificate.map_or(0, |certificate| certificate.as_bytes().len() as u64)
}

/// Whether two certificates are the same one: the bytes they arrived as. A
/// pool that holds one certificate twice holds one certificate.
fn same(left: &Certificate<'_>, right: &Certificate<'_>) -> bool {
    core::ptr::eq(left.as_bytes(), right.as_bytes()) || left.as_bytes() == right.as_bytes()
}

/// Whether a certificate is one an anchor was published in: the same name
/// and the same key, however the trust context supplied the anchor itself.
fn publishes_anchor<V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'_, '_, V, W, R>,
    certificate: &Certificate<'_>,
) -> BuildResult<bool, V::Error, R::Error> {
    let anchors = search.anchors;
    for anchor in anchors {
        if !search.spend_names(certificate.tbs().subject(), anchor.name())? {
            break;
        }
        if !certificate
            .tbs()
            .subject()
            .matches(anchor.name(), search.execution)?
        {
            continue;
        }

        // The keys are compared byte for byte, and how long a key encoding
        // is is decided by whoever wrote the certificate. Two encodings of
        // one length that differ near the end are read to the end, and a
        // pool can hold a candidate for every anchor: charged at a flat
        // rate, one certificate and a handful of anchors buy the reading of
        // their product while the bound barely moves. The name comparison
        // above is charged by what it reads for the same reason, and this
        // is the other side of the same question.
        let key = certificate.tbs().public_key().as_bytes();
        let against = anchor.key().as_bytes();
        let read = (key.len() as u64 + against.len() as u64) / cost::COMPARED;
        if !search.spend(read)? {
            break;
        }
        if key == against {
            return Ok(true);
        }
    }
    Ok(false)
}

/// What one certificate says about itself, read the first time it is seen
/// and repeated afterwards.
///
/// Every answer here is a property of the certificate and of the question
/// the caller asked, neither of which changes while a search runs, so the
/// second visit costs a lookup rather than the extensions again.
fn properties<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    certificate: &'a Certificate<'a>,
) -> BuildResult<Properties, V::Error, R::Error> {
    let at = certificate.as_bytes().as_ptr() as usize;
    if let Some(known) = search
        .properties
        .get(&at, search.execution)
        .map_err(|reason| certificate.tbs().subject().resource(reason))?
    {
        return Ok(*known);
    }
    // Whether it names itself as its own issuer, which is two names of the
    // certificate compared, and comparing them reads both: a document
    // decides how long they are, so the charge is the size of what is read
    // and it is taken before the reading. Where there is nothing left to
    // spend the answer is no, which is safe for the same reason it is below:
    // a certificate not known to be self-issued is an ordinary link, and the
    // search that could not afford the question is one nothing will now be
    // built through.
    let self_issued = search
        .spend_names(certificate.tbs().subject(), certificate.tbs().issuer())?
        && self_issued(certificate, search.execution)?;
    let publishes_anchor = publishes_anchor(search, certificate)?;
    let issuing = issues(search, certificate)?;
    // "If the subject is a CA ... then the subject field MUST be populated
    // with a non-empty distinguished name matching the contents of the
    // issuer field ... in all certificates issued by the subject CA"
    // (RFC 5280 4.1.2.6). A certificate may carry its identity in the
    // alternative names and leave the subject empty, but not while claiming
    // to be an authority: there is then no name for anything below it to be
    // issued under, and nothing for a report to say a path leads to.
    //
    // On the asserted bit rather than on whether it may issue. Those are two
    // questions, and a certificate that asserts being an authority while
    // naming a key that may not sign certificates has still asserted it:
    // reading one from the other would let that spelling name nobody.
    //
    // Asked here rather than where a path holds each certificate to what it
    // says about issuing, because that is asked only of the certificates a
    // path is built through. The one the question is about is not among
    // them, since it need not be an authority at all, and this is a
    // certificate that says it is one.
    //
    // A certificate whose basic constraints did not read has not answered
    // whether it is one, so there is no answer for this to be held to and
    // the certificate stands nowhere.
    let named =
        issuing.is_some_and(|issuing| !issuing.asserted || !certificate.tbs().subject().is_empty());
    let usable = named && usable(search, certificate)?;

    // Whether it signs itself, which is asked only of the certificates that
    // could be an anchor's own: it is the one question here that costs a
    // signature check, and the answer matters for nothing else.
    //
    // Asked last, and only of a certificate that could stand in a path at
    // all. A pool can put any number of expired copies of an anchor's own
    // certificate in front of the issuer that leads somewhere, and what
    // rules each of them out is what it says about itself, which costs
    // nothing to read. Asking the expensive question first would spend the
    // search on candidates already refused.
    //
    // Naming itself as its issuer is not the same as signing itself. An
    // authority rolling its key over certifies the new key with the old one,
    // and that certificate carries one name on both sides while being signed
    // by somebody else. It is the only route from the new key to the old
    // anchor, so reading the names alone would lose it.
    //
    // Charged like every other signature, because it is one: a pool can hold
    // any number of certificates that copy an anchor's name and key, and
    // asking the verifier about each of them for free would run the most
    // expensive check here as often as somebody else likes while the meter
    // recorded only the name comparisons. Where there is nothing left to
    // spend the answer is no, which is safe: the search has halted, and a
    // certificate not known to sign itself is treated as an ordinary link
    // that nothing will now be built through.
    let publishes_itself = usable
        && publishes_anchor
        && self_issued
        && search.verified(
            certificate,
            // Its own key and nothing above it: a certificate that signs
            // itself stands in whatever it wrote, and a key that omits its
            // parameters has nowhere to inherit them from here.
            WorkingKey::standing(certificate.tbs().public_key()),
        )? == Some(Verified::Yes);

    let known = Properties {
        usable,
        issues: issuing.and_then(|issuing| issuing.constraints),
        self_issued,
        publishes_itself,
    };
    search
        .properties
        .try_insert(at, known)
        .map_err(|reason| certificate.tbs().subject().resource(reason))?;
    Ok(known)
}

/// Whether a certificate can stand in a path at all: valid across the
/// interval, and carrying no critical extension nobody understood.
///
/// A malformed extension is not an error of this run, so the answer is no
/// rather than a refusal: another path may not go through this certificate.
fn usable<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    certificate: &'a Certificate<'a>,
) -> BuildResult<bool, V::Error, R::Error> {
    if !search.spend(cost::CHECK)? {
        return Ok(false);
    }
    if !search.interval.inside(certificate.tbs().validity()) {
        return Ok(false);
    }
    // The critical extensions one at a time, charged before each is read
    // and stopping at the first demand nobody understood. Working out one
    // entry decodes its value, and how many entries there are and how much
    // each holds is a certificate's to decide: gathering them all first
    // reads the whole list at a fixed charge, and goes on reading it after
    // the answer is already no.
    //
    // The charge comes before the question, and the list is walked without
    // asking it, so that a budget already spent refuses the reading rather
    // than being told about it afterwards.
    let extensions = certificate.tbs().extensions();
    for demand in extensions.criticals(search.execution) {
        let demand = demand?;
        if !search.spend(cost::EXTENSION)? {
            return Ok(false);
        }
        if extensions.understands(demand, search.recognizer, search.execution)? {
            continue;
        }
        // One of those demands is this function's own subject. A critical
        // name-constraints extension counts as not understood where it
        // constrains a form nothing here matches names against, and that
        // reading is right for a reader that will not look at the names:
        // for one that will, the profile asks for the certificate to be
        // refused only where "an instance of that name form appears"
        // below it (RFC 5280 4.2.1.10), which is a question the search
        // answers per certificate rather than here. What it cannot do is
        // go on when the value did not parse at all, since then there is
        // no constraint to hold anything to.
        if demand.kind() == crate::oid::NAME_CONSTRAINTS {
            if !search.spend(cost::EXTENSION)? {
                return Ok(false);
            }
            if gate(crate::constraints::NameConstraints::read(
                demand,
                search.execution,
            ))?
            .is_some()
            {
                continue;
            }
        }
        return Ok(false);
    }
    Ok(true)
}

/// What a certificate says about issuing certificates, both facts read from
/// the one extension.
///
/// The answer carries the constraints rather than a yes, because the same
/// extension holds how far below the authority a path may go and reading it
/// twice would charge a caller twice for one value.
#[derive(Debug, Clone, Copy, Default)]
struct Issuing {
    /// Whether the certificate asserts being an authority: the basic
    /// constraints are there and say so, whatever its key may be used for.
    ///
    /// Kept apart from the constraints below because the profile hangs a
    /// different rule on it. The requirement that an authority name
    /// somebody is tied to this bit (RFC 5280 4.1.2.6), and a certificate
    /// that asserts it while naming a key that may not sign certificates
    /// has still asserted it.
    asserted: bool,
    /// The constraints where the certificate may issue, and `None` where it
    /// says it does not, does not say, or names a key that is not for
    /// signing certificates (RFC 5280 6.1.4 (k) and (n)).
    constraints: Option<crate::constraints::BasicConstraints>,
}

/// Reads both, charging the extensions once.
///
/// `None` where the certificate carries basic constraints this run could not
/// read: whether the subject is an authority is then unanswered, and the
/// requirement that an authority name somebody (RFC 5280 4.1.2.6) is hung on
/// that answer. Reading it as though the extension were absent answers no,
/// so a certificate with an empty subject passes a requirement its own
/// extension may have been asserting. The extension need not be critical for
/// this to matter, and a critical one is refused elsewhere, so this is where
/// the difference is kept.
fn issues<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    certificate: &'a Certificate<'a>,
) -> BuildResult<Option<Issuing>, V::Error, R::Error> {
    let extensions = certificate.tbs().extensions();
    let Ok(carried) = read(search, |execution| extensions.basic_constraints(execution))?.enforced()
    else {
        return Ok(None);
    };
    let Some(basic) = carried else {
        return Ok(Some(Issuing::default()));
    };
    if !basic.is_authority() {
        return Ok(Some(Issuing::default()));
    }
    let asserted = Issuing {
        asserted: true,
        constraints: None,
    };
    if extensions
        .get(crate::oid::KEY_USAGE, search.execution)?
        .is_some()
    {
        let Some(usage) = read(search, |execution| extensions.key_usage(execution))?.value() else {
            return Ok(Some(asserted));
        };
        if !usage.key_cert_sign() {
            return Ok(Some(asserted));
        }
    }
    Ok(Some(Issuing {
        constraints: Some(basic),
        ..asserted
    }))
}

/// Whether the chain, read down from the anchor, is a path: every
/// certificate within the names the ones above it allowed, under a policy
/// they agreed on, and inside the depth they permitted (RFC 5280 6.1.3 and
/// 6.1.4).
///
/// The answer carries what the path was issued under, because that is not a
/// property of any one certificate: it is what is left after every authority
/// along the path has narrowed it.
///
/// The chain is held with the target first, so it is read backwards: the
/// certificate the anchor issued is where the path starts.
fn validate<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    chain: &[&'a Certificate<'a>],
    anchor: Anchor<'a>,
) -> BuildResult<Option<OwnedVec<Oid<'a>>>, V::Error, R::Error> {
    let length = chain.len();
    let mut space = NameSpace::new(search.execution);
    let Some(mut policies) = initial_policies(search, length)? else {
        // A caller who allowed the working out nothing at all has not asked
        // for a path settled without it.
        return Ok(None);
    };

    // What the anchor says about the names below it. The anchor itself is
    // not a certificate of the path, but a trust context that published a
    // constrained root published the constraint with it, and a path that
    // ignored it would be a path the trust context did not allow.
    if let Some(certificate) = anchor.certificate()
        && !narrow_published(search, &mut space, certificate.tbs().extensions())?
    {
        return Ok(None);
    }

    // "n", the number of certificates in the path (6.1.2 (k)): a path can
    // never spend more than it holds.
    let mut allowed = u32::try_from(length).unwrap_or(u32::MAX);
    let mut last_constraints = None;

    // The key each certificate is checked with, carried down from the anchor
    // (RFC 5280 6.1.2 (c)). The anchor's own key stands on its own: there is
    // nothing above a trust anchor to inherit from.
    let mut working = WorkingKey::standing(anchor.key());

    for (position, certificate) in chain.iter().rev().enumerate() {
        if !search.spend(cost::CHECK)? {
            return Ok(None);
        }
        let last = position + 1 == length;

        // (6.1.3 (a) (1)) The certificate is the one the key above signed.
        // Asked here rather than where the edge was found, because a key
        // that omits its parameters is only usable once the path above it
        // is known, and here it is. A key that stands on its own was asked
        // about at the edge and the answer is remembered, so this costs a
        // lookup for it.
        let Some(answer) = search.verified(certificate, working)? else {
            return Ok(None);
        };
        if answer != Verified::Yes {
            return Ok(None);
        }
        working = working.below(certificate.tbs().public_key());
        let known = properties(search, certificate)?;
        let self_issued = known.self_issued;
        let extensions = certificate.tbs().extensions();

        // (6.1.3 (b) and (c)) The names have to be where the authorities
        // above allowed them. A self-issued certificate that is not the one
        // at the end is a key rollover rather than a name being certified,
        // and is not held to the space it is itself narrowing.
        if !space.is_open() && (last || !self_issued) && !within(search, &space, certificate)? {
            return Ok(None);
        }

        // (6.1.3 (d) to (f)) What this certificate says about policies. A
        // list that is present and does not read is not a certificate that
        // named no policy: that reading would carry the agreement past a
        // certificate whose part in it nobody could see.
        let Ok(named) = read(search, |execution| {
            extensions.certificate_policies(execution)
        })?
        .enforced() else {
            return Ok(None);
        };
        let presented = policies.present(named.as_ref(), self_issued, last, search);
        let Some(satisfied) = search.policy(presented)? else {
            return Ok(None);
        };
        if !satisfied {
            return Ok(None);
        }

        // (6.1.4 (g)) What this certificate says about the names below it,
        // which is read before the path ends because the profile allows the
        // extension only in a certificate that issues others: one at the end
        // of a path carries it only where the path is to an authority.
        if !narrow(search, &mut space, extensions)? {
            return Ok(None);
        }

        if last {
            // Nothing reads the mappings of the certificate at the end of a
            // path, and nothing should. The mapping step is 6.1.4, which
            // runs for certificates 1 to n-1; 6.1.5 defines no processing of
            // mappings for certificate n, because there is no certificate
            // below for a mapped policy to be named in.
            //
            // Nor is carrying them a reason to refuse it. The profile says
            // the extension "is used in CA certificates" (RFC 5280 4.2.1.5),
            // which is a description of where it belongs, not a prohibition:
            // where it does mean to forbid an extension outside a
            // certification authority it says so, as it does for the name
            // constraints that "MUST be used only in a CA certificate"
            // (4.2.1.10), and that one is enforced above. Reading the weaker
            // sentence as the stronger one would refuse a certificate over a
            // rule the profile does not state.
            let Ok(constraints) =
                read(search, |execution| extensions.policy_constraints(execution))?.enforced()
            else {
                return Ok(None);
            };
            last_constraints = constraints;
            break;
        }

        // (6.1.4 (b) and (h) to (j)) What it says about the ones below it.
        let Some(restrictions) = restrictions(search, extensions)? else {
            return Ok(None);
        };
        let carried = policies.carry(
            restrictions.mappings.as_ref(),
            restrictions.constraints,
            restrictions.inhibit,
            self_issued,
            search,
        );
        if search.policy(carried)?.is_none() {
            return Ok(None);
        }

        // (6.1.4 (k)) A certificate that issues certificates says so, and
        // (n) where it says what its key is for, signing certificates is
        // among it. Both were asked of this certificate before the search
        // walked into it, and both are asked again here because a path is
        // read on what it holds rather than on how it was found.
        let Some(basic) = known.issues else {
            return Ok(None);
        };

        // (6.1.4 (l)) A certificate issued to somebody else spends one of
        // the certificates the path is allowed. One issued to the same name
        // spends nothing: a key rollover is not a longer chain of authority.
        if !self_issued {
            if allowed == 0 {
                return Ok(None);
            }
            allowed -= 1;
        }

        // (6.1.4 (m)) And an authority may allow fewer than it was given. A
        // limit wider than the counter holds is no limit: the path this
        // browser will ever walk is shorter than that by every other bound.
        if let Some(limit) = basic.path_length().and_then(CertificateCount::certificates) {
            allowed = allowed.min(limit);
        }
    }

    // (6.1.5) What is left is what the authorities agreed the target was
    // issued under.
    if !spend_policies(search, policies.nodes())? {
        return Ok(None);
    }
    let settled = policies.settle(last_constraints, search.policy.wanted, search);
    let Some(settled) = search.policy(settled)? else {
        return Ok(None);
    };
    if !settled.is_satisfied() {
        return Ok(None);
    }
    Ok(Some(settled.into_policies()))
}

/// Admits the terminal tree pass before settlement performs it.
fn spend_policies(
    search: &mut Search<'_, '_, impl Verify, impl Watch, impl Recognizer>,
    nodes: usize,
) -> Result<bool> {
    let work = cost::POLICY.checked_mul(nodes as u64).ok_or_else(|| {
        search
            .target
            .tbs()
            .subject()
            .resource(structured_asn1::memory::MemoryError::WorkExceeded)
    })?;
    search.spend(work)
}

/// Creates the accounted policy root at the original target's location.
fn initial_policies<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    length: usize,
) -> Result<Option<policy::Processing<'a>>> {
    let origin = search
        .target
        .tbs()
        .subject()
        .resource(structured_asn1::memory::MemoryError::CapacityOverflow);
    let length = u32::try_from(length).map_err(|_| origin.clone())?;
    let initial = policy::Processing::new(
        length,
        policy::Initial {
            explicit_policy: search.policy.explicit,
            policy_mapping: search.policy.mapping,
            any_policy: search.policy.any,
        },
        search.bounds.policies,
        search.execution,
        origin.offset(),
    );
    search.policy(initial)
}

/// Keeps the settled identifiers in the returned path's resource domain.
/// Narrows the name space by what one certificate says, answering whether
/// the certificate may be in a path at all.
///
/// Two ways it may not. A constraint this run could not read is one nothing
/// below can be shown to obey, and treating an unreadable one as absent
/// would let a certificate through the space its authority narrowed by
/// writing a value nobody can parse. And "the name constraints extension
/// ... MUST be used only in a CA certificate" (RFC 5280 4.2.1.10): carried
/// by a certificate that issues nothing, it constrains a space that does not
/// exist, and the profile says such a certificate is not one to build a path
/// through.
fn narrow<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    space: &mut NameSpace<'a>,
    extensions: &'a crate::extension::Extensions<'a>,
) -> BuildResult<bool, V::Error, R::Error> {
    if extensions
        .get(crate::oid::NAME_CONSTRAINTS, search.execution)?
        .is_none()
    {
        return Ok(true);
    }
    let authority = read(search, |execution| extensions.basic_constraints(execution))?
        .value()
        .is_some_and(crate::constraints::BasicConstraints::is_authority);
    if !authority {
        return Ok(false);
    }
    narrowed(search, space, extensions)
}

/// The same, for the certificate a trust context published an anchor in.
///
/// Without the question about issuing. That question is asked of a
/// certificate of the path, where the profile allows the extension "only
/// within a CA certificate" and one carrying it while claiming to be
/// anything else is refused. An anchor is not a certificate of the path
/// (RFC 5280 6.1), it is the statement of trust the caller made, and this
/// crate's way of making that statement carry regions is to hand over a
/// certificate holding them. Reading them only where it also asserts being
/// an authority would throw away a path the caller trusts, to a target
/// inside the very subtree the caller allowed, and report it as no path at
/// all.
///
/// What is not waived is reading them: regions that do not read are regions
/// nothing was held to, and that refuses here as everywhere.
fn narrow_published<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    space: &mut NameSpace<'a>,
    extensions: &'a crate::extension::Extensions<'a>,
) -> BuildResult<bool, V::Error, R::Error> {
    if extensions
        .get(crate::oid::NAME_CONSTRAINTS, search.execution)?
        .is_none()
    {
        return Ok(true);
    }
    narrowed(search, space, extensions)
}

/// Reads the regions and narrows the space by them, which is what both of
/// the above do once they have decided the extension is theirs to honour.
fn narrowed<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    space: &mut NameSpace<'a>,
    extensions: &'a crate::extension::Extensions<'a>,
) -> BuildResult<bool, V::Error, R::Error> {
    let Some(constraints) =
        read(search, |execution| extensions.name_constraints(execution))?.value()
    else {
        return Ok(false);
    };
    let origin = extensions
        .get(crate::oid::NAME_CONSTRAINTS, search.execution)?
        .expect("the decoded name constraints extension")
        .span()
        .start;
    space
        .narrow(constraints)
        .map_err(|reason| crate::Error::resource(reason, "nameConstraints", origin))?;
    Ok(true)
}

/// Whether the names one certificate carries are where the authorities above
/// it allowed them to be (RFC 5280 6.1.3 (b) and (c)).
///
/// Names this run could not read are names it cannot show to be where they
/// were allowed. A certificate carrying an alternative name extension that
/// does not parse is not a certificate with no alternative names: reading it
/// as one would hold a shorter list to the space than the certificate
/// carries.
fn within<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    space: &NameSpace<'a>,
    certificate: &'a Certificate<'a>,
) -> BuildResult<bool, V::Error, R::Error> {
    // Through the same gate as every other extension, so that reading the
    // list happens after the charge. Reaching for it here rather than
    // handing it over is what keeps that true: an argument is worked out
    // before the call it is passed to, and how many names this holds is a
    // certificate's to decide.
    let subject = certificate.tbs().subject();
    let Ok(carried) = read(search, |execution| {
        certificate.tbs().extensions().subject_alt_name(execution)
    })?
    .enforced() else {
        return Ok(false);
    };
    // Absent subjectAltName has no names; borrow the optional collection rather
    // than fabricate a new account or an uncharged growable container.
    let alternatives = carried.as_deref().unwrap_or(&[]);
    if !charge_names(search, space, subject, alternatives)? {
        return Ok(false);
    }
    Ok(
        space.admits(subject, alternatives, search.recognizer, search.execution)?
            == Admission::Admitted,
    )
}

/// Charges for holding one certificate's names to the space above it, before
/// the comparison runs: both the number of names and the number of regions
/// come from certificates somebody else wrote.
///
/// Every name that will be compared is counted, the legacy mailboxes among
/// them. A subject may carry as many of those as the parse budget allowed,
/// and each is held against every region: charging for one would let a
/// certificate buy the comparisons of thousands without the meter that
/// stops them ever moving.
fn charge_names<V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'_, '_, V, W, R>,
    space: &NameSpace<'_>,
    subject: &Name<'_>,
    alternatives: &[GeneralName<'_>],
) -> Result<bool> {
    // What the space says it will compare, which is the pairs of a name and
    // a region of one form rather than every name against every region. A
    // comparison that does not part early reads the whole of the name: two
    // distinguished names are ordered and compared attribute by attribute,
    // a domain and a mailbox are folded to the end. How long the names are
    // and how many regions there are is decided by a certificate and an
    // extension somebody else wrote, so the charge is their product rather
    // than a fixed amount, which one long name and a handful of regions
    // would otherwise buy while the bound barely moved.
    //
    // Charged where it is counted rather than counted here and charged
    // afterwards: forming a name reads it, and a list priced in full before
    // the meter is consulted has been read in full whatever the budget
    // said.
    space.charge(subject, alternatives, search, search.execution)
}

/// Whether a certificate was issued to the name that issued it, which is how
/// an authority rolls its key over without lengthening the chain of
/// authority under it (RFC 5280 6.1).
fn self_issued(certificate: &Certificate<'_>, execution: &Memory) -> Result<bool> {
    certificate
        .tbs()
        .subject()
        .matches(certificate.tbs().issuer(), execution)
}

/// What one extension of a certificate turned out to be.
///
/// Absent and unreadable are kept apart, because they are different facts
/// and the difference decides a path. A certificate that does not carry a
/// restriction is not restricted; one that carries a restriction nothing
/// here could read is a certificate whose restriction was not enforced, and
/// reading the second as the first lets it into a path on the strength of a
/// value nobody understood. Only the extensions marked critical are refused
/// when they are read, so this is the whole of what protects the rest.
enum Read<T> {
    /// The certificate does not carry it.
    Absent,
    /// It carries it, and this is what it says.
    Value(T),
    /// It carries it, and this run could not read it.
    Unreadable,
}

impl<T> Read<T> {
    /// What the extension says, where it says anything, with unreadable and
    /// absent alike answering nothing. For the extensions whose absence and
    /// whose unreadability lead to the same refusal anyway.
    fn value(self) -> Option<T> {
        match self {
            Self::Value(value) => Some(value),
            Self::Absent | Self::Unreadable => None,
        }
    }

    /// What the extension says, for a restriction where absent and
    /// unreadable are different answers: a certificate that carries no
    /// restriction restricts nothing, and one carrying a restriction this
    /// run could not read is a certificate whose restriction was never
    /// enforced.
    fn enforced(self) -> core::result::Result<Option<T>, Unreadable> {
        match self {
            Self::Absent => Ok(None),
            Self::Value(value) => Ok(Some(value)),
            Self::Unreadable => Err(Unreadable),
        }
    }
}

/// A restriction that is there and could not be read, which is not the same
/// as a restriction that is not there.
struct Unreadable;

/// What one certificate says about how policies are processed below it.
struct Restrictions<'a> {
    mappings: Option<crate::policy::PolicyMappings<'a>>,
    constraints: Option<crate::constraints::PolicyConstraints>,
    inhibit: Option<crate::constraints::InhibitAnyPolicy>,
}

/// Reads all three, or refuses where any of them is present and does not
/// read: each restricts what may be agreed below, and reading an unreadable
/// one as absent carries the agreement past a restriction nobody saw.
fn restrictions<'a, V: Verify, W: Watch, R: Recognizer>(
    search: &mut Search<'a, '_, V, W, R>,
    extensions: &'a crate::extension::Extensions<'a>,
) -> BuildResult<Option<Restrictions<'a>>, V::Error, R::Error> {
    let mappings = read(search, |execution| extensions.policy_mappings(execution))?.enforced();
    let constraints =
        read(search, |execution| extensions.policy_constraints(execution))?.enforced();
    let inhibit = read(search, |execution| extensions.inhibit_any_policy(execution))?.enforced();
    let (Ok(mappings), Ok(constraints), Ok(inhibit)) = (mappings, constraints, inhibit) else {
        return Ok(None);
    };
    Ok(Some(Restrictions {
        mappings,
        constraints,
        inhibit,
    }))
}

/// One extension of a certificate the search is holding to its constraints,
/// with a spent budget kept as the error it is: that says this run gave up
/// rather than anything about the document.
///
/// The extension is reached for rather than handed over, so that reading its
/// value happens after the charge and not before it. An argument is worked
/// out before the call it is passed to, and reading an extension decodes
/// everything it holds, which is a document's to decide: handed over, the
/// whole of it is read even where the budget was already spent.
fn read<T>(
    search: &mut Search<'_, '_, impl Verify, impl Watch, impl Recognizer>,
    outcome: impl FnOnce(&Memory) -> Result<Option<T>>,
) -> Result<Read<T>> {
    if !search.spend(cost::EXTENSION)? {
        return Ok(Read::Unreadable);
    }
    match gate(outcome(search.execution))? {
        Some(Some(value)) => Ok(Read::Value(value)),
        Some(None) => Ok(Read::Absent),
        None => Ok(Read::Unreadable),
    }
}

#[cfg(test)]
mod tests;