cabin_build/planner/

mod.rs

use crate::error::BuildError;
use crate::graph::{BuildGraph, CompileCommand, StandardViolation};
use cabin_core::{
    InterfaceStandardSource, LanguageStandard, Package, ResolvedCompilerWrapper,
    ResolvedLanguageStandards, ResolvedProfile, ResolvedProfileFlags, ResolvedToolchain,
    SourceLanguage, StandardFlagConflict, Target, TargetKind, classify_source,
    link_driver_language,
};
use cabin_driver::{
    ArchiveAction, BuildAction, CompileAction, CompileArguments, CompileMode, Dialect, LinkAction,
    compile_argv,
};
use cabin_workspace::PackageGraph;
use camino::Utf8PathBuf;
use std::collections::{BTreeSet, HashMap, HashSet};
use std::path::PathBuf;

mod lowering;
#[cfg(test)]
mod tests;

use self::lowering::{
    collect_include_dirs, collect_link_lib_names, collect_link_libs, compile_dispatch,
    depfile_path, object_path, promote_dir, resolve_target_dep_edge, topo_sort_targets,
};

/// Reference to a manifest target - one of the `[target.<name>]`
/// declarations in a package's `cabin.toml`.  May be qualified
/// `package:target` or unqualified `target`.  Resolution against a
/// [`PackageGraph`] happens in the planner.
///
/// This is the *manifest-target* selector.  It has nothing to do
/// with a platform / toolchain target (e.g. an
/// `x86_64-unknown-linux-gnu` triple); Cabin does not yet model
/// the latter.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ManifestTargetSelector {
    pub package: Option<String>,
    pub name: String,
}

impl ManifestTargetSelector {
    /// Parse a `package:target` or bare `target` string.  Unknown formats
    /// (multiple `:`s) are accepted and surfaced later by resolution
    /// errors.
    pub fn parse(s: &str) -> Self {
        match s.split_once(':') {
            Some((pkg, tgt)) => Self {
                package: Some(pkg.to_owned()),
                name: tgt.to_owned(),
            },
            None => Self {
                package: None,
                name: s.to_owned(),
            },
        }
    }
}

/// Inputs to the build planner.
#[derive(Debug)]
pub struct PlanRequest<'a> {
    pub graph: &'a PackageGraph,
    /// Resolved C/C++ toolchain.  The planner picks the compile
    /// driver per source language (`toolchain.cc.path()` for `.c`,
    /// `toolchain.cxx.path()` for `.cc` / `.cpp` / `.cxx` /
    /// `.c++` / `.C`) and the link driver per target (C++ if any
    /// linked object came from a C++ source, otherwise C).
    /// `toolchain.ar.path()` drives archive commands.
    pub toolchain: &'a ResolvedToolchain,
    /// Per-package resolved build flags.  Missing entries fall
    /// back to an empty [`ResolvedProfileFlags`]; the planner does
    /// not require every package to be present so consumers can
    /// resolve flags lazily for the selected closure only.
    pub build_flags: &'a HashMap<usize, ResolvedProfileFlags>,
    /// Per-package effective language standards.  Missing entries
    /// resolve to no package-level standards, mirroring
    /// `build_flags`; a compile of a language with no effective
    /// standard is then rejected at its compile site.
    pub language_standards: &'a HashMap<usize, ResolvedLanguageStandards>,
    /// Per-package standard-flag conflict candidates, detected by
    /// the CLI on the manifest-derived flags *before* env /
    /// pkg-config augmentation (so `CFLAGS` / `CXXFLAGS` stay
    /// exempt).  The planner records a violation for each planned
    /// compile a candidate's scope covers; candidates whose scope
    /// is never planned (an unbuilt sibling target) gate nothing.
    pub standard_flag_conflicts: &'a HashMap<usize, Vec<StandardFlagConflict>>,
    /// Absolute path under which all build outputs are placed.
    pub build_dir: PathBuf,
    /// Resolved build profile.  Drives compile flags and the per-
    /// profile output directory.
    pub profile: ResolvedProfile,
    /// Specific manifest targets to build, plus their transitive
    /// deps.  `None` means "every C/C++ target in every primary
    /// package".
    pub selected: Option<Vec<ManifestTargetSelector>>,
    /// Resolved root-package configuration.  Carried through
    /// the planner so future cache logic and any planner-level
    /// fingerprint comparisons see the same selection the build
    /// script and metadata observed.  The planner does not yet
    /// change C++ flags based on this value.
    pub configuration: Option<&'a cabin_core::BuildConfiguration>,
    /// Indices of `graph.packages` that the user picked
    /// through workspace package-selection flags.  `None` means
    /// "use the graph's primary set" (the documented default).
    /// When `Some`, default-target enumeration narrows to the
    /// supplied indices and any manifest-target selectors in
    /// `selected` are validated against them so an unrelated
    /// package never sneaks into the build.
    pub selected_packages: Option<&'a [usize]>,
    /// Optional compiler wrapper applied to every C and C++
    /// compile command.  The Ninja `command` field is prefixed with
    /// the wrapper executable; the matching `compile_commands.json`
    /// `arguments` array stays *unwrapped* so clangd / IDE tooling
    /// keeps seeing the underlying compiler.  Link and archive
    /// commands are never wrapped.
    pub compiler_wrapper: Option<&'a ResolvedCompilerWrapper>,
    /// Compiler command-line dialect for this build.  Selected from
    /// the detected C++ compiler (MSVC drives the `cl.exe` dialect).
    /// Governs artifact naming (`.o` vs `.obj`, `lib<x>.a` vs
    /// `<x>.lib`, `<x>` vs `<x>.exe`) and the spelling of every
    /// compile / archive / link command the lowering emits.
    pub dialect: Dialect,
    /// Whether the MSVC-dialect compilers accept the `/external:I`
    /// block ([`crate::msvc_external_includes_supported`]).  When
    /// `false` on an MSVC build, the planner collapses the system
    /// include bucket into the plain `/I` list instead of emitting a
    /// switch an old `cl` would reject.  Ignored by the GCC/Clang
    /// dialect, where `-isystem` is part of the base command line.
    pub msvc_external_includes: bool,
    /// Per-package enabled feature names from the cross-package
    /// feature resolver, keyed by `graph.packages` index.  Gates
    /// targets that declare `required-features`: default
    /// enumeration skips a target whose required features are not
    /// all enabled, while naming one explicitly (a selector or a
    /// `deps` entry) is a hard error.  `None` (and missing
    /// entries) mean "no features enabled" for gating purposes.
    pub enabled_features: Option<&'a HashMap<usize, BTreeSet<String>>>,
    /// Whether the post-resolution standard-compatibility check runs
    /// over the resolved target graph ([`crate::standard_compat`]).
    /// The build / check / run / test commands set it; `cabin tidy`
    /// leaves it `false`, and then the planner records no violations
    /// and its output is unchanged.
    pub standard_compat: bool,
}

/// One manifest-declared source resolved to its absolute path and the
/// per-target object path it compiles to.
struct PreparedSource {
    abs_source: Utf8PathBuf,
    object: Utf8PathBuf,
    language: SourceLanguage,
}

/// Plan a build for the requested package graph.
///
/// # Errors
/// Returns a [`BuildError`] when the request cannot be turned into
/// a valid graph: [`BuildError::NonUtf8Path`] when the build directory
/// or a package's manifest directory is not valid UTF-8 and so cannot
/// anchor the UTF-8 build model; [`BuildError::EmptySelectedPackages`]
/// when the default selection yields no C/C++ targets; selection
/// and dependency-resolution errors ([`BuildError::UnknownTargetReference`],
/// [`BuildError::AmbiguousTarget`], [`BuildError::UnknownPackageInTargetSelector`],
/// [`BuildError::UnknownTargetInPackage`],
/// [`BuildError::NoSameNameTargetInDependency`],
/// [`BuildError::DevDependencyNotActive`]); required-feature gating
/// errors ([`BuildError::TargetRequiresFeatures`],
/// [`BuildError::TargetDepRequiresFeatures`],
/// [`BuildError::AllDefaultTargetsRequireFeatures`]);
/// [`BuildError::DependencyCycle`]
/// when the target dependency graph contains a cycle; and per-target
/// source errors ([`BuildError::UnrecognizedSourceExtension`],
/// [`BuildError::InvalidSourcePath`], [`BuildError::EmptyTargetSources`],
/// [`BuildError::MissingCCompiler`]).
pub fn plan(req: &PlanRequest<'_>) -> Result<BuildGraph, BuildError> {
    let empty_features = BTreeSet::new();
    let enabled_of = |pkg_idx: usize| -> &BTreeSet<String> {
        req.enabled_features
            .and_then(|m| m.get(&pkg_idx))
            .unwrap_or(&empty_features)
    };

    let selected = if let Some(sel) = &req.selected {
        let selected = resolve_selection(sel, req.graph, req.selected_packages)?;
        // Explicitly named targets hard-error when their
        // `required-features` are not enabled - a silent skip here
        // would turn a typo'd feature selection into "built
        // nothing".
        for tid in &selected {
            let target = lookup_target(tid, req.graph)?;
            let missing = target.missing_required_features(enabled_of(tid.0));
            if !missing.is_empty() {
                return Err(BuildError::TargetRequiresFeatures {
                    target: format_target_id(tid, req.graph),
                    package: req.graph.packages[tid.0].package.name.as_str().to_owned(),
                    missing,
                });
            }
        }
        selected
    } else {
        let (chosen, gated) =
            default_selection(req.graph, req.selected_packages, req.enabled_features);
        if chosen.is_empty() {
            if gated.is_empty() {
                return Err(BuildError::EmptySelectedPackages);
            }
            return Err(BuildError::AllDefaultTargetsRequireFeatures {
                gated: gated
                    .into_iter()
                    .map(|(tid, missing)| (format_target_id(&tid, req.graph), missing))
                    .collect(),
            });
        }
        chosen
    };

    // Walk the target dep graph, resolving each raw `deps` entry to a
    // concrete (package, target) ID and recording the edges together
    // with their declared visibility.
    let mut resolved_deps: HashMap<TargetId, Vec<TargetDepEdge>> = HashMap::new();
    let mut reachable: HashSet<TargetId> = HashSet::new();
    let mut to_visit: Vec<TargetId> = selected.clone();

    while let Some(tid) = to_visit.pop() {
        if !reachable.insert(tid.clone()) {
            continue;
        }
        let target = lookup_target(&tid, req.graph)?;
        let mut resolved = Vec::with_capacity(target.deps.len());
        // Dev-only target kinds (`test` / `example`) may reference
        // the owning package's activated `[dev-dependencies]`
        // edges; every other kind resolves through Normal edges
        // only.
        let dev_deps_visible = target.kind.is_dev_only();
        for decl in &target.deps {
            let edge = resolve_target_dep_edge(decl, tid.0, dev_deps_visible, req.graph)?;
            let dep = edge.to.clone();
            // A dep edge is an explicit request: a feature-gated
            // dep target whose required features are not enabled
            // on its package is a hard error, not a skip.
            let dep_target = lookup_target(&dep, req.graph)?;
            let missing = dep_target.missing_required_features(enabled_of(dep.0));
            if !missing.is_empty() {
                // CLI feature selection applies to the selected
                // roots only, so the actionable fix depends on how
                // the gated package entered the graph.  For a
                // cross-package reference, mirror
                // `resolve_target_dep`'s edge preference: a Normal
                // edge wins, so the help only points at
                // `[dev-dependencies]` when the dep is reachable
                // through an activated dev edge alone.
                let gated_pkg_is_root = match req.selected_packages {
                    Some(s) => s.contains(&dep.0),
                    None => req.graph.primary_packages.contains(&dep.0),
                };
                let fix = if gated_pkg_is_root {
                    crate::error::FeatureGateFix::RootSelection
                } else if dep.0 == tid.0 {
                    crate::error::FeatureGateFix::UpstreamEdge
                } else if req.graph.packages[tid.0]
                    .deps_of_kind(cabin_core::DependencyKind::Normal)
                    .any(|di| di == dep.0)
                {
                    crate::error::FeatureGateFix::DependencyEdge
                } else {
                    crate::error::FeatureGateFix::DevDependencyEdge
                };
                return Err(BuildError::TargetDepRequiresFeatures {
                    consumer: format_target_id(&tid, req.graph),
                    dep_target: format_target_id(&dep, req.graph),
                    dep_package: req.graph.packages[dep.0].package.name.as_str().to_owned(),
                    missing,
                    fix,
                });
            }
            to_visit.push(dep);
            resolved.push(edge);
        }
        resolved_deps.insert(tid, resolved);
    }

    let topo = topo_sort_targets(&reachable, &resolved_deps, req.graph)?;

    // Post-resolution standard-compatibility check (spec D13 over
    // every resolved edge).  When the caller opts out (`cabin
    // tidy`), the planner's output is byte-for-byte what it was
    // before the pass existed.
    let standard_compat_violations = if req.standard_compat {
        crate::standard_compat::edge_violations(&topo, &resolved_deps, req)?
    } else {
        Vec::new()
    };

    // Promote the OS-supplied build directory to UTF-8 once: it
    // prefixes every object, archive, and executable path in the
    // semantic IR, so it must be valid UTF-8 to be embedded in build
    // commands.  A non-UTF-8 build directory is rejected here rather
    // than silently lossily converted downstream.
    let build_dir = promote_dir(&req.build_dir)?;

    let mut actions: Vec<BuildAction> = Vec::new();
    let mut compile_commands: Vec<CompileCommand> = Vec::new();
    let mut standard_violations: Vec<StandardViolation> = Vec::new();
    let mut output_for_target: HashMap<TargetId, Utf8PathBuf> = HashMap::new();
    // Per-target source-language manifest, including transitive
    // contributions through `target.deps`.  Used to pick the
    // link-driver language deterministically: a target with any
    // direct or transitive C++ object link-drives through the C++
    // compiler, every other target link-drives through the C
    // compiler.  Populated in topo order so dependents inherit
    // their dependencies' contributions.
    let mut target_languages: HashMap<TargetId, BTreeSet<SourceLanguage>> = HashMap::new();
    // Transitively reachable dependency targets per target, in
    // first-occurrence order, populated in topo order (direct deps
    // plus their reachable sets).  Drives the interface-standard
    // compatibility check.
    let mut transitive_deps: HashMap<TargetId, Vec<TargetId>> = HashMap::new();

    for tid in &topo {
        let target = lookup_target(tid, req.graph)?;
        // Vec keeps first-occurrence order; the HashSet is only a
        // seen-filter so membership checks stay O(1).
        let mut dep_closure: Vec<TargetId> = Vec::new();
        let mut seen: HashSet<TargetId> = HashSet::new();
        if let Some(deps) = resolved_deps.get(tid) {
            for edge in deps {
                let dep = &edge.to;
                if seen.insert(dep.clone()) {
                    dep_closure.push(dep.clone());
                }
                if let Some(transitive) = transitive_deps.get(dep) {
                    for transitive_dep in transitive {
                        if seen.insert(transitive_dep.clone()) {
                            dep_closure.push(transitive_dep.clone());
                        }
                    }
                }
            }
        }
        transitive_deps.insert(tid.clone(), dep_closure.clone());

        let pkg = &req.graph.packages[tid.0];
        let pkg_name = pkg.package.name.as_str();
        // Per-profile output root keeps `dev` and `release`
        // builds from overwriting each other and gives custom
        // profiles a deterministic, non-colliding output tree.
        let pkg_build_dir = build_dir
            .join(req.profile.name.as_str())
            .join("packages")
            .join(pkg_name);
        // The manifest directory is an OS-canonicalized path; promote
        // it to UTF-8 (rejecting non-UTF-8) so the source and include
        // paths it anchors enter the IR as `Utf8PathBuf`.
        let manifest_dir = promote_dir(&pkg.manifest_dir)?;

        // Header-only libraries declare include dirs but no
        // translation units.  Skip every action - `collect_link_libs`
        // and `collect_include_dirs` already walk dep targets by
        // their declared `include_dirs`, so consumers still pick up
        // the headers; no `.a` is available to link against.
        if target.kind.is_header_only() {
            target_languages.insert(tid.clone(), Default::default());
            continue;
        }

        // Build the per-source list.  Each manifest-declared source
        // resolves to an absolute path under the manifest directory
        // and a per-target object path.
        let mut prepared: Vec<PreparedSource> = Vec::with_capacity(target.sources.len());
        for source in &target.sources {
            let language =
                classify_source(source).ok_or_else(|| BuildError::UnrecognizedSourceExtension {
                    target: format_target_id(tid, req.graph),
                    path: source.clone(),
                })?;
            let object = object_path(&pkg_build_dir, target.name.as_str(), source, req.dialect)
                .map_err(|reason| BuildError::InvalidSourcePath {
                    target: format_target_id(tid, req.graph),
                    path: source.clone(),
                    reason,
                })?;
            prepared.push(PreparedSource {
                abs_source: manifest_dir.join(source),
                object,
                language,
            });
        }
        if prepared.is_empty() {
            return Err(BuildError::EmptyTargetSources(format_target_id(
                tid, req.graph,
            )));
        }

        let pkg_standards = req
            .language_standards
            .get(&tid.0)
            .copied()
            .unwrap_or_default();
        enforce_interface_standards(
            tid,
            target,
            &prepared,
            &dep_closure,
            pkg_standards,
            req,
            &mut standard_violations,
        )?;

        // Per-package resolved build flags from the manifest's
        // `[profile]`, `[target.'cfg(...)'.profile]`, and the active
        // `[profile.<name>]` table.  Layered on top of per-target
        // defines / include dirs.
        let pkg_flags = req.build_flags.get(&tid.0);

        // Compose include_dirs and defines: existing target +
        // per-package build flags, partitioned into the user (`-I`)
        // and system (`-isystem` / `/external:I`) buckets.
        let collected = collect_include_dirs(tid, target, &resolved_deps, req.graph)?;
        let mut include_dirs = collected.user;
        let mut system_include_dirs = collected.system;
        if let Some(flags) = pkg_flags {
            for inc in &flags.include_dirs {
                let absolute = if inc.is_absolute() {
                    inc.clone()
                } else {
                    manifest_dir.join(inc)
                };
                if !include_dirs.contains(&absolute) && !system_include_dirs.contains(&absolute) {
                    include_dirs.push(absolute);
                }
            }
            for inc in &flags.system_include_dirs {
                let absolute = if inc.is_absolute() {
                    inc.clone()
                } else {
                    manifest_dir.join(inc)
                };
                if !include_dirs.contains(&absolute) && !system_include_dirs.contains(&absolute) {
                    system_include_dirs.push(absolute);
                }
            }
        }
        // An MSVC toolchain that predates `/external:I` cannot spell
        // the system bucket; fall back to plain `/I` for those dirs -
        // exactly the pre-system-include command shape.
        if req.dialect == Dialect::Msvc && !req.msvc_external_includes {
            for dir in system_include_dirs.drain(..) {
                if !include_dirs.contains(&dir) {
                    include_dirs.push(dir);
                }
            }
        }
        let mut defines: Vec<String> = target.defines.clone();
        if let Some(flags) = pkg_flags {
            for def in &flags.defines {
                if !defines.contains(def) {
                    defines.push(def.clone());
                }
            }
        }
        let extra_compile_args: &[String] =
            pkg_flags.map_or(&[], |f| f.extra_compile_args.as_slice());
        let cflags: &[String] = pkg_flags.map_or(&[], |f| f.cflags.as_slice());
        let cxxflags: &[String] = pkg_flags.map_or(&[], |f| f.cxxflags.as_slice());
        let ldflags: &[String] = pkg_flags.map_or(&[], |f| f.ldflags.as_slice());

        // Strictly per-target: two targets in one build may differ in
        // both level and `gnu-extensions`.
        let gnu_extensions = cabin_core::effective_gnu_extensions(
            &req.graph.packages[tid.0].package.language,
            target,
        );
        let mut objects: Vec<Utf8PathBuf> = Vec::with_capacity(prepared.len());
        for ps in &prepared {
            let depfile = depfile_path(&ps.object);
            // Pick the language-appropriate compiler driver, the
            // language-appropriate standard / profile flags, the
            // matching escape-hatch arg list, and the human-readable
            // tag.  Naming the components here is the single point that
            // enforces "C/C++ compile lines never share argv space".
            let dispatch = compile_dispatch(ps.language, req)
                .map_err(|err| err.attach_target_path(tid, req.graph, &ps.abs_source))?;
            // Escape-hatch flags: the language-neutral list first, then
            // the language-specific one - so a per-language override
            // always appears later in argv, where the compiler treats
            // it as the final word.
            let extra_language_compile_args = match ps.language {
                SourceLanguage::C => cflags,
                SourceLanguage::Cxx => cxxflags,
            };
            let mut extra_flags =
                Vec::with_capacity(extra_compile_args.len() + extra_language_compile_args.len());
            extra_flags.extend(extra_compile_args.iter().cloned());
            extra_flags.extend(extra_language_compile_args.iter().cloned());
            // Ninja runs the wrapped command for C and C++ compiles.
            // The wrapper lives on the semantic action and is applied
            // only when lowering the *run* command;
            // `compile_commands.json` below is derived from the
            // unwrapped lowering so clangd / IDE tooling still sees
            // the underlying compiler. Link and archive commands are
            // deliberately never wrapped.
            let compiler_wrapper = req.compiler_wrapper.map(|wrapper| wrapper.path.clone());
            // Manifest loading rejects targets that compile a
            // language without an effective standard, so a `None`
            // here is a package that bypassed the parser - reject it
            // with the same actionable message.
            let missing_standard = |field: &'static str| BuildError::MissingLanguageStandard {
                target: format_target_id(tid, req.graph),
                language: ps.language.human_label(),
                field,
            };
            let standard = match ps.language {
                SourceLanguage::C => LanguageStandard::C(
                    cabin_core::effective_c(&pkg_standards, target)
                        .ok_or_else(|| missing_standard("c-standard"))?
                        .standard,
                ),
                SourceLanguage::Cxx => LanguageStandard::Cxx(
                    cabin_core::effective_cxx(&pkg_standards, target)
                        .ok_or_else(|| missing_standard("cxx-standard"))?
                        .standard,
                ),
            };
            // An MSVC-dialect compile whose standard has no stable
            // `/std:` flag cannot be lowered.  Record the violation
            // instead of failing eagerly: the `cabin check` rewrite
            // prunes dependency compiles after planning, and a
            // pruned compile must not gate the command.  The CLI
            // surfaces surviving violations through
            // `validate_planned_standards` before anything is
            // lowered or written.
            let msvc_spelling_missing =
                req.dialect == Dialect::Msvc && standard.msvc_spelling().is_none();
            if msvc_spelling_missing {
                standard_violations.push(StandardViolation::MsvcSpelling {
                    target: format_target_id(tid, req.graph),
                    language: ps.language.human_label(),
                    standard: standard.as_str(),
                    object: ps.object.clone(),
                });
            }
            // `cl.exe` has no GNU dialect mode, so `gnu-extensions`
            // cannot be honored - and must never be silently
            // ignored.  Recorded (not failed eagerly) for the same
            // check-rewrite reason as the missing-spelling case.
            let msvc_gnu_extensions = req.dialect == Dialect::Msvc && gnu_extensions;
            if msvc_gnu_extensions {
                standard_violations.push(StandardViolation::MsvcGnuExtensions {
                    target: format_target_id(tid, req.graph),
                    object: ps.object.clone(),
                });
            }
            // Escape-hatch conflicts: a candidate covers this
            // compile when its language matches and its scope is the
            // whole package or this specific target.
            if let Some(candidates) = req.standard_flag_conflicts.get(&tid.0) {
                for candidate in candidates {
                    let covers = candidate.language == ps.language
                        && candidate
                            .target
                            .as_deref()
                            .is_none_or(|t| t == tid.1.as_str());
                    if covers {
                        standard_violations.push(StandardViolation::FlagConflict {
                            conflict: candidate.clone(),
                            object: ps.object.clone(),
                        });
                    }
                }
            }
            let compile = CompileAction {
                standard,
                gnu_extensions,
                source: ps.abs_source.clone(),
                object: ps.object.clone(),
                mode: CompileMode::Object,
                implicit_inputs: Vec::new(),
                depfile: Some(depfile),
                compiler: dispatch.driver.to_path_buf(),
                compiler_wrapper,
                arguments: CompileArguments {
                    opt_level: req.profile.opt_level,
                    debug_info: req.profile.debug,
                    define_ndebug: !req.profile.assertions,
                    include_dirs: include_dirs.clone(),
                    system_include_dirs: system_include_dirs.clone(),
                    defines: defines.clone(),
                    extra_flags,
                },
                description: format!("{} {}", dispatch.description_tag, ps.object),
            };
            // `compile_commands.json` records the unwrapped, object-mode
            // argv.  Deriving it from the same lowering the Ninja writer
            // uses (minus the wrapper) keeps the two in lockstep.  A
            // violating compile has no lowerable argv, so its entry is
            // omitted - the violation above makes that loud, never
            // silent.
            if !msvc_spelling_missing && !msvc_gnu_extensions {
                compile_commands.push(CompileCommand {
                    directory: build_dir.to_path_buf(),
                    file: ps.abs_source.clone(),
                    arguments: compile_argv(req.dialect, &compile),
                    output: ps.object.clone(),
                });
            }
            objects.push(ps.object.clone());
            actions.push(BuildAction::Compile(compile));
        }

        // Per-target language manifest: own sources' languages
        // unioned with every direct target dep's manifest.  The
        // topo iteration guarantees dependencies are populated
        // before we visit the dependent.
        let mut languages_here: BTreeSet<SourceLanguage> =
            prepared.iter().map(|p| p.language).collect();
        if let Some(deps) = resolved_deps.get(tid) {
            for edge in deps {
                if let Some(dep_langs) = target_languages.get(&edge.to) {
                    languages_here.extend(dep_langs.iter().copied());
                }
            }
        }

        match target.kind {
            TargetKind::Library => {
                let lib_path =
                    pkg_build_dir.join(req.dialect.static_library_name(target.name.as_str()));
                actions.push(BuildAction::Archive(ArchiveAction {
                    archiver: req.toolchain.ar.path().to_path_buf(),
                    output: lib_path.clone(),
                    inputs: objects,
                    description: format!("AR {lib_path}"),
                }));
                output_for_target.insert(tid.clone(), lib_path);
            }
            // Every executable kind takes the same link path:
            // `executable` (production binaries), `test`
            // (run by `cabin test`), and `example`.  The build
            // planner does not distinguish between them here because
            // the link/compile semantics are identical; the kind
            // difference is only consulted when deciding *which*
            // targets to select (default-buildable vs. dev-only) and
            // which targets `cabin test` runs.  Compiler-driver
            // selection is per-source via `link_driver_language`, so
            // an `executable` that declares only `.c` sources
            // drives the link with the C compiler, while one that
            // mixes in any `.cc` / `.cpp` source - directly or
            // transitively - drives the link with the C++ compiler.
            TargetKind::Executable | TargetKind::Test | TargetKind::Example => {
                let exe_path =
                    pkg_build_dir.join(req.dialect.executable_name(target.name.as_str()));
                let lib_paths =
                    collect_link_libs(tid, &resolved_deps, req.graph, &output_for_target);

                let mut inputs = objects;
                inputs.extend(lib_paths);

                // System libraries required by this executable's
                // dependency closure (e.g. a static library port's
                // `link-libs`).  Carried as bare names on the LinkAction
                // so the dialect lowering spells them (`-l<name>` for
                // GNU, `<name>.lib` for MSVC) and places them after the
                // archives for left-to-right resolution. `arguments`
                // stays the package's own raw `ldflags`.
                let link_arguments = ldflags.to_vec();
                let link_libs = collect_link_lib_names(tid, &resolved_deps, req.build_flags);

                // Link-driver pick: C++ if any of this target's
                // own objects came from a C++ source, or if any
                // transitively reachable object did.  Otherwise
                // the C compiler drives the link, which keeps
                // pure-C executables off the C++ runtime.
                let languages_slice: Vec<SourceLanguage> = languages_here.iter().copied().collect();
                let driver_language = link_driver_language(&languages_slice);
                let driver_path = match driver_language {
                    SourceLanguage::Cxx => req.toolchain.cxx.path(),
                    SourceLanguage::C => {
                        req.toolchain
                            .cc
                            .as_ref()
                            .map(cabin_core::ResolvedTool::path)
                            .ok_or_else(|| {
                                BuildError::MissingCCompiler {
                                    target: format_target_id(tid, req.graph),
                                    // Pick a representative source for the
                                    // diagnostic; pure-C link errors
                                    // always have at least one C source on
                                    // this target.
                                    path: prepared
                                        .iter()
                                        .find(|p| p.language == SourceLanguage::C)
                                        .map_or_else(|| exe_path.clone(), |p| p.abs_source.clone()),
                                }
                            })?
                    }
                };
                actions.push(BuildAction::Link(LinkAction {
                    linker: driver_path.to_path_buf(),
                    output: exe_path.clone(),
                    inputs,
                    implicit_inputs: Vec::new(),
                    arguments: link_arguments,
                    link_libs,
                    description: format!("LINK {exe_path}"),
                }));
                output_for_target.insert(tid.clone(), exe_path);
            }
            TargetKind::HeaderOnly => {
                unreachable!("header-only targets are skipped before action generation")
            }
        }
        target_languages.insert(tid.clone(), languages_here);
    }

    let default_outputs: Vec<Utf8PathBuf> = selected
        .iter()
        .filter_map(|tid| output_for_target.get(tid).cloned())
        .collect();

    Ok(BuildGraph {
        actions,
        dialect: req.dialect,
        default_outputs,
        compile_commands,
        standard_violations,
        standard_compat_violations,
    })
}

// ---------------------------------------------------------------------------
// internal: target IDs and lookups
// ---------------------------------------------------------------------------

/// Stable identifier for a target within a [`PackageGraph`]: the index of
/// its package in `graph.packages` and its target name.
pub(crate) type TargetId = (usize, String);

/// One resolved edge of the target dependency graph.  Alias
/// resolution has already happened - `to` is a concrete
/// (package, target), never a pre-alias bare name - and the edge
/// carries the visibility declared on the manifest entry.  The
/// `public` classification feeds the standard-compatibility
/// pass, which propagates interface requirements along public edges
/// (`docs/design/standard-compatibility/spec.md`, D5).
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct TargetDepEdge {
    pub(crate) to: TargetId,
    pub(crate) public: bool,
}

/// Find a target by name within a package's manifest.  Target
/// names are unique within a package, so this returns the sole
/// match (or `None`).
pub(crate) fn find_target<'a>(pkg: &'a Package, name: &str) -> Option<&'a Target> {
    pkg.targets.iter().find(|t| t.name.as_str() == name)
}

pub(crate) fn lookup_target<'a>(
    tid: &TargetId,
    graph: &'a PackageGraph,
) -> Result<&'a Target, BuildError> {
    let pkg = &graph.packages[tid.0];
    find_target(&pkg.package, &tid.1).ok_or_else(|| BuildError::UnknownTargetInPackage {
        package: pkg.package.name.as_str().to_owned(),
        target: tid.1.clone(),
    })
}

pub(crate) fn format_target_id(tid: &TargetId, graph: &PackageGraph) -> String {
    format!("{}:{}", graph.packages[tid.0].package.name.as_str(), tid.1)
}

// ---------------------------------------------------------------------------
// internal: interface-standard compatibility
// ---------------------------------------------------------------------------

/// Pre-build interface-standard compatibility: a consuming target's
/// effective implementation standard must be at least every reachable
/// library-like dependency's interface requirement, per language the
/// consumer compiles.  The chronological `>=` comparison is a
/// compatibility policy, not a proof of header validity - see
/// `docs/language-standards.md`.
///
/// Incompatibilities are *recorded* on the consumer's first compile
/// of the offending language rather than failing the plan: the
/// `cabin check` rewrite prunes dependency compiles after planning,
/// and an incompatibility between two dependencies whose compiles
/// are all pruned must not gate the command.
/// `validate_planned_standards` surfaces the survivors.
fn enforce_interface_standards(
    tid: &TargetId,
    target: &Target,
    prepared: &[PreparedSource],
    dep_closure: &[TargetId],
    pkg_standards: ResolvedLanguageStandards,
    req: &PlanRequest<'_>,
    violations: &mut Vec<StandardViolation>,
) -> Result<(), BuildError> {
    let object_of = |language: SourceLanguage| {
        prepared
            .iter()
            .find(|p| p.language == language)
            .map(|p| p.object.clone())
    };
    for dep_tid in dep_closure {
        let dep_target = lookup_target(dep_tid, req.graph)?;
        if !dep_target.kind.is_library_like() {
            continue;
        }
        let dep_pkg = &req.graph.packages[dep_tid.0].package;
        let dep_standards = req
            .language_standards
            .get(&dep_tid.0)
            .copied()
            .unwrap_or_default();
        // A `None` requirement or consumer standard cannot happen
        // for manifest-derived packages: `imposes_requirement` is
        // true only when some declaration (or a source file, whose
        // standard manifest loading guarantees) backs the language,
        // and the consumer compiles the language, so its own
        // standard was already demanded at its compile site.
        // An explicit `none` requirement carries no minimum to
        // compare against; rejecting consumers of not-consumable
        // headers is deferred alongside the rest of the range work.
        if let Some(object) = object_of(SourceLanguage::C)
            && cabin_core::imposes_requirement(dep_target, &dep_pkg.language, SourceLanguage::C)
            && let Some(required) =
                cabin_core::interface_c(&dep_standards, &dep_pkg.language, dep_target)
            && let Some(required_min) = required.requirement.min()
            && let Some(consumer) = cabin_core::effective_c(&pkg_standards, target)
            && consumer.standard < required_min
        {
            violations.push(interface_violation(
                format_target_id(tid, req.graph),
                format_target_id(dep_tid, req.graph),
                SourceLanguage::C,
                consumer.standard.as_str(),
                required_min.as_str(),
                required.source,
                object,
            ));
        }
        if let Some(object) = object_of(SourceLanguage::Cxx)
            && cabin_core::imposes_requirement(dep_target, &dep_pkg.language, SourceLanguage::Cxx)
            && let Some(required) =
                cabin_core::interface_cxx(&dep_standards, &dep_pkg.language, dep_target)
            && let Some(required_min) = required.requirement.min()
            && let Some(consumer) = cabin_core::effective_cxx(&pkg_standards, target)
            && consumer.standard < required_min
        {
            violations.push(interface_violation(
                format_target_id(tid, req.graph),
                format_target_id(dep_tid, req.graph),
                SourceLanguage::Cxx,
                consumer.standard.as_str(),
                required_min.as_str(),
                required.source,
                object,
            ));
        }
    }
    Ok(())
}

fn interface_violation(
    consumer: String,
    dependency: String,
    language: SourceLanguage,
    consumer_standard: &'static str,
    required: &'static str,
    source: InterfaceStandardSource,
    object: Utf8PathBuf,
) -> StandardViolation {
    let requirement_source = match source {
        InterfaceStandardSource::Target => "its target-level interface standard",
        InterfaceStandardSource::Package => "its package-level interface standard",
        InterfaceStandardSource::Workspace => "its workspace-inherited interface standard",
        InterfaceStandardSource::CompileStandard => {
            "its effective implementation standard (no interface standard declared)"
        }
    };
    StandardViolation::InterfaceIncompatibility {
        consumer,
        dependency,
        language: language.human_label(),
        consumer_standard,
        required,
        requirement_source,
        object,
    }
}

// ---------------------------------------------------------------------------
// internal: manifest-target selector resolution
// ---------------------------------------------------------------------------

fn resolve_selection(
    selectors: &[ManifestTargetSelector],
    graph: &PackageGraph,
    selected_packages: Option<&[usize]>,
) -> Result<Vec<TargetId>, BuildError> {
    let mut out: Vec<TargetId> = Vec::with_capacity(selectors.len());
    for sel in selectors {
        out.push(resolve_top_level_selector(sel, graph, selected_packages)?);
    }
    Ok(out)
}

fn resolve_top_level_selector(
    sel: &ManifestTargetSelector,
    graph: &PackageGraph,
    selected_packages: Option<&[usize]>,
) -> Result<TargetId, BuildError> {
    if let Some(pkg_name) = &sel.package {
        let pkg_idx =
            graph
                .index_of(pkg_name)
                .ok_or_else(|| BuildError::UnknownPackageInTargetSelector {
                    package: pkg_name.clone(),
                    selector: format!("{}:{}", pkg_name, sel.name),
                })?;
        let pkg = &graph.packages[pkg_idx];
        if find_target(&pkg.package, &sel.name).is_none() {
            return Err(BuildError::UnknownTargetInPackage {
                package: pkg_name.clone(),
                target: sel.name.clone(),
            });
        }
        return Ok((pkg_idx, sel.name.clone()));
    }

    // unqualified selectors search the selected
    // package set (or the primary set when no selection is
    // active).  We no longer fall back to the root package when it
    // is outside the selected set - that would silently build
    // something the user did not ask for.
    let candidates: Vec<usize> = if let Some(s) = selected_packages {
        s.to_vec()
    } else {
        // Unqualified selector with no workspace selection
        // active: walk the root first, then every primary.
        let mut root_match: Option<TargetId> = None;
        if let Some(root_idx) = graph.root_package {
            let root = &graph.packages[root_idx];
            if find_target(&root.package, &sel.name).is_some() {
                root_match = Some((root_idx, sel.name.clone()));
            }
        }
        if let Some(tid) = root_match {
            return Ok(tid);
        }
        graph.primary_packages.clone()
    };

    let mut matches: Vec<TargetId> = Vec::new();
    for idx in candidates {
        let pkg = &graph.packages[idx];
        if find_target(&pkg.package, &sel.name).is_some() {
            matches.push((idx, sel.name.clone()));
        }
    }
    match matches.len() {
        0 => Err(BuildError::UnknownTargetReference(sel.name.clone())),
        1 => Ok(matches.into_iter().next().unwrap()),
        _ => Err(BuildError::AmbiguousTarget(
            sel.name.clone(),
            matches
                .iter()
                .map(|(i, t)| format!("{}:{}", graph.packages[*i].package.name.as_str(), t))
                .collect(),
        )),
    }
}

/// Default-buildable targets of the selected packages, split into
/// the buildable set and the targets skipped because their
/// `required-features` are not enabled (with the missing names, for
/// the all-gated diagnostic).
fn default_selection(
    graph: &PackageGraph,
    selected_packages: Option<&[usize]>,
    enabled_features: Option<&HashMap<usize, BTreeSet<String>>>,
) -> (Vec<TargetId>, Vec<(TargetId, Vec<String>)>) {
    let empty = BTreeSet::new();
    let mut out = Vec::new();
    let mut gated = Vec::new();
    let pkg_indices: &[usize] = match selected_packages {
        Some(s) => s,
        None => graph.primary_packages.as_slice(),
    };
    for &pkg_idx in pkg_indices {
        let pkg = &graph.packages[pkg_idx];
        let enabled = enabled_features
            .and_then(|m| m.get(&pkg_idx))
            .unwrap_or(&empty);
        for target in &pkg.package.targets {
            if !target.kind.is_default_buildable() {
                continue;
            }
            let tid = (pkg_idx, target.name.as_str().to_owned());
            let missing = target.missing_required_features(enabled);
            if missing.is_empty() {
                out.push(tid);
            } else {
                gated.push((tid, missing));
            }
        }
    }
    (out, gated)
}

/// Whether the selector's target has all of its
/// `required-features` enabled under `enabled_features`.  Used by
/// enumeration-style callers (`cabin test` without `--test`,
/// `cabin tidy`) to *skip* feature-gated targets; explicitly named
/// targets go through [`plan`], which hard-errors instead.
/// Selectors that do not resolve to a target return `true` so
/// resolution diagnostics stay owned by [`plan`].
// The map is always the std-hasher one the CLI builds from the
// feature resolver; a `BuildHasher` parameter would be dead
// flexibility.
#[allow(clippy::implicit_hasher)]
pub fn selector_required_features_met(
    sel: &ManifestTargetSelector,
    graph: &PackageGraph,
    enabled_features: &HashMap<usize, BTreeSet<String>>,
) -> bool {
    let empty = BTreeSet::new();
    let Some(pkg_name) = &sel.package else {
        return true;
    };
    let Some(pkg_idx) = graph.index_of(pkg_name) else {
        return true;
    };
    let Some(target) = graph.packages[pkg_idx]
        .package
        .targets
        .iter()
        .find(|t| t.name.as_str() == sel.name)
    else {
        return true;
    };
    let enabled = enabled_features.get(&pkg_idx).unwrap_or(&empty);
    target.missing_required_features(enabled).is_empty()
}

/// Build-time selector for `cabin test`: expand a package
/// selection into the set of targets of a specific
/// development-only kind (`test` today).  Returns
/// deterministic `(package_index, target_name)` tuples in the same
/// order as the planner consumes selectors.  Useful for callers that
/// want every dev-only target of a given kind without naming each
/// one explicitly.
pub fn select_targets_of_kind(
    graph: &PackageGraph,
    selected_packages: Option<&[usize]>,
    kind: TargetKind,
) -> Vec<ManifestTargetSelector> {
    let pkg_indices: &[usize] = match selected_packages {
        Some(s) => s,
        None => graph.primary_packages.as_slice(),
    };
    let mut out = Vec::new();
    for &pkg_idx in pkg_indices {
        let pkg = &graph.packages[pkg_idx];
        for target in &pkg.package.targets {
            if target.kind == kind {
                out.push(ManifestTargetSelector {
                    package: Some(pkg.package.name.as_str().to_owned()),
                    name: target.name.as_str().to_owned(),
                });
            }
        }
    }
    out
}