nornir 0.5.2

//! Binary (ELF) graph extractor — reconstruct the dependency + symbol graph
//! `G = (V, E)` from compiled artefacts when **no source is checked out**.
//!
//! This is the airgap / vendored-`.so` case (EPIC item 8, on-theme for
//! **Skidbladnir**): third-party shared objects, vendored libs, and airgap
//! bundles arrive as ELF, not as `Cargo.toml`s. We parse them **in pure Rust**
//! (the `object` crate — no `libc`, no shelling out to `readelf`/`nm`/`objdump`)
//! and emit the SAME node/edge types the source extractor uses, tagged
//! [`Provenance::Binary`] so a consumer can tell binary-derived facts from
//! source-derived ones.
//!
//! What we reconstruct, and how it maps onto `G = (V, E)`:
//!
//!  - **Library DAG** — `DT_NEEDED` dynamic entries (who links whom). Each
//!    object is a node `V`; a `DT_NEEDED` entry is an edge `object → needed`.
//!    This is the binary twin of the manifest `path`-dep graph.
//!  - **Symbol provide/need** — `.dynsym`: an object *exports* its defined
//!    global symbols and *needs* its `UND` (undefined) ones. In the
//!    [`WorkspaceGraph`] these become a node's `produces` / `consumes` sets —
//!    exactly the role crate names play for source. Resolving a `UND` symbol to
//!    the object that exports it gives the edge's concrete justification (`via`),
//!    the binary analogue of "crate B produces what crate A consumes".
//!  - **Call edges** *(stretch)* — PLT/GOT dynamic relocations
//!    (`R_*_JUMP_SLOT` / `GLOB_DAT`): each is an inter-object reference to a
//!    `UND` symbol → a call/data edge `object → symbol → provider`.
//!
//! The produced [`BinaryGraph`] converts to the very same
//! [`WorkspaceGraph`](crate::warehouse::dep_graph::WorkspaceGraph)
//! ([`to_workspace_graph`](BinaryGraph::to_workspace_graph)) so **every** graph
//! method — build order, blast radius, `dep_path`, SCC/MFAS — works unchanged on
//! a binary-only constellation, and to [`SymbolRow`] / [`CallEdgeRow`]
//! ([`to_symbol_rows`](BinaryGraph::to_symbol_rows) /
//! [`to_call_edge_rows`](BinaryGraph::to_call_edge_rows)) for the warehouse
//! symbol/call facts, mirroring [`crate::knowledge::symbols`].

use std::collections::{BTreeMap, BTreeSet};
use std::path::{Path, PathBuf};

use anyhow::{bail, Context, Result};
use object::read::elf::{ElfFile, ElfFile32, ElfFile64, FileHeader};
use object::{
    elf, Endianness, FileKind, Object, ObjectSymbol, ObjectSymbolTable, ReadRef, RelocationTarget,
    SymbolKind,
};

use super::Provenance;
use crate::knowledge::symbols::{CallEdgeRow, SymbolRow};
use crate::warehouse::dep_graph::{CrossRepoEdge, DepKind, RepoFacts, WorkspaceGraph};

/// Broad ELF object class — enough to tell an executable from a shared library
/// (the two node shapes a link graph cares about).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ObjectClass {
    /// `ET_EXEC` / `ET_DYN` with an entry point — a program.
    Executable,
    /// `ET_DYN` shared object (`.so`) — the vendored-lib case.
    SharedObject,
    /// `ET_REL` relocatable object (`.o`) — pre-link.
    Relocatable,
    /// Anything else (`ET_CORE`, unknown).
    Other,
}

/// One parsed ELF artefact — a node `V` in the binary graph. Its `exports`
/// (defined global `.dynsym` entries) and `imports` (`UND` entries) are the
/// binary analogue of a crate's `produces` / `consumes`.
#[derive(Debug, Clone)]
pub struct BinaryObject {
    /// The node key: the `DT_SONAME` if present, else the file name. Using the
    /// soname makes a `DT_NEEDED` edge resolve to the right node even when the
    /// on-disk file is a versioned real-name (`libz.so.1.3.1`) behind the
    /// soname (`libz.so.1`).
    pub name: String,
    /// Where the artefact was read from.
    pub path: PathBuf,
    /// `DT_SONAME`, when the object declares one.
    pub soname: Option<String>,
    /// Object class (executable / shared object / …).
    pub class: ObjectClass,
    /// `DT_NEEDED` entries in declaration order — the direct link dependencies.
    pub needed: Vec<String>,
    /// `DT_RUNPATH` / `DT_RPATH` search dirs (`:`-split), when present — the
    /// loader's resolution hints (useful to a resolver, recorded for detail).
    pub runpath: Vec<String>,
    /// Defined, globally-visible `.dynsym` function/object symbols this object
    /// **provides**. Weak defs are included (they still satisfy a `UND`).
    pub exports: BTreeSet<String>,
    /// Undefined (`UND`) `.dynsym` symbols this object **needs** from elsewhere.
    pub imports: BTreeSet<String>,
    /// Provenance marker — always [`Provenance::Binary`] here.
    pub provenance: Provenance,
    /// PLT/GOT dynamic relocations captured for call-edge reconstruction —
    /// `(symbol, reloc-kind-label)`. Folded into [`BinaryGraph::call_edges`] at
    /// graph-assembly time.
    relocs: Vec<(String, String)>,
}

/// Which kind of dependency edge — a hard `DT_NEEDED` link, or a symbol
/// resolution that crosses to a provider the loader would reach transitively.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum EdgeKind {
    /// A direct `DT_NEEDED` link (`from` names `to` in its dynamic section).
    Needed,
    /// A symbol `from` imports is satisfied by `to`, but `to` is not a direct
    /// `DT_NEEDED` of `from` (indirect / transitive resolution).
    Symbol,
}

/// A dependency edge `from → to` in the binary graph — the ELF twin of a
/// [`CrossRepoEdge`]. `via` carries the concretely-resolved symbols that justify
/// the edge (empty when the provider is outside the analysed set).
#[derive(Debug, Clone)]
pub struct BinaryEdge {
    /// The needing object (consumer) node name.
    pub from: String,
    /// The providing object (producer) node name — a soname even when that
    /// object was not itself analysed (e.g. a `DT_NEEDED` on `libc.so.6`).
    pub to: String,
    /// `Needed` (a `DT_NEEDED` link) or `Symbol` (indirect symbol resolution).
    pub kind: EdgeKind,
    /// The symbols `from` imports that `to` exports — the concrete justification
    /// ("which lib satisfies which symbol"). Empty when `to` was not analysed.
    pub via: BTreeSet<String>,
    /// Whether `to` is a node we actually parsed (its `exports` are known).
    pub resolved: bool,
    /// Provenance marker — always [`Provenance::Binary`].
    pub provenance: Provenance,
}

/// A PLT/GOT inter-object call/reference edge (the stretch goal) — an object
/// reaching an external `UND` symbol via a dynamic relocation.
#[derive(Debug, Clone)]
pub struct BinaryCallEdge {
    /// The calling object node name.
    pub from: String,
    /// The callee symbol (mangled `.dynsym` name).
    pub symbol: String,
    /// The relocation kind label (e.g. `"Elf(R_X86_64_JUMP_SLOT)"`).
    pub reloc: String,
    /// The providing object, when the symbol resolved to an analysed export.
    pub resolves_to: Option<String>,
    /// Provenance marker — always [`Provenance::Binary`].
    pub provenance: Provenance,
}

/// The reconstructed binary graph: nodes ([`BinaryObject`]s), dependency edges
/// ([`BinaryEdge`]s), and PLT/GOT call edges ([`BinaryCallEdge`]s). Convert to
/// the shared model with [`to_workspace_graph`](Self::to_workspace_graph) /
/// [`to_symbol_rows`](Self::to_symbol_rows) /
/// [`to_call_edge_rows`](Self::to_call_edge_rows).
#[derive(Debug, Clone, Default)]
pub struct BinaryGraph {
    /// Nodes `V` — the parsed ELF artefacts.
    pub objects: Vec<BinaryObject>,
    /// Dependency edges `E` — `DT_NEEDED` links + resolved symbol edges.
    pub edges: Vec<BinaryEdge>,
    /// PLT/GOT inter-object call edges (stretch).
    pub call_edges: Vec<BinaryCallEdge>,
}

/// Demangle a Rust/`itanium` symbol for display; falls back to the raw name.
/// Used only for the human-facing `SymbolRow.signature` — the graph keys stay
/// the mangled `.dynsym` names so resolution is exact.
fn demangle(name: &str) -> String {
    rustc_demangle::try_demangle(name)
        .map(|d| d.to_string())
        .unwrap_or_else(|_| name.to_string())
}

/// Parse a single ELF artefact into a [`BinaryObject`] node (no cross-object
/// edges — use [`extract_graph`] for those). Pure Rust; never shells out.
pub fn extract_object(path: &Path) -> Result<BinaryObject> {
    let data =
        std::fs::read(path).with_context(|| format!("reading ELF artefact {}", path.display()))?;
    parse_object(path, &data)
}

/// Parse a set of ELF artefacts and resolve the dependency + symbol + call
/// graph across them.
///
/// Edges come in two flavours (see [`EdgeKind`]): every `DT_NEEDED` yields a
/// `Needed` edge (its `via` filled in with the symbols the provider actually
/// exports, when the provider is in the set); any remaining unresolved import
/// satisfied by *another* analysed object yields a `Symbol` edge. A
/// `DT_NEEDED` on a library outside the set (e.g. `libc.so.6` when only
/// `libz.so` was handed in) still produces an (unresolved) edge — the link is
/// known even if the provider's symbols are not.
///
/// An unreadable / non-ELF input is **skipped** (logged to stderr), never fatal
/// to the whole graph — one bad vendored blob must not sink the bundle.
pub fn extract_graph(paths: &[PathBuf]) -> Result<BinaryGraph> {
    let mut objects: Vec<BinaryObject> = Vec::new();
    for p in paths {
        match extract_object(p) {
            Ok(obj) => objects.push(obj),
            Err(e) => eprintln!(
                "nornir: binary-graph: skipping {} — not a parseable ELF: {e:#}",
                p.display()
            ),
        }
    }
    Ok(assemble(objects))
}

/// Assemble edges + call edges from already-parsed objects (the resolution core,
/// split out so tests can feed synthetic objects).
fn assemble(objects: Vec<BinaryObject>) -> BinaryGraph {
    // Export index: symbol → every node that exports it. Lets us resolve a
    // `UND` import to its provider(s) concretely.
    let mut export_index: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
    // Node set (soname AND file name both resolve to the node) so a `DT_NEEDED`
    // on a soname matches an object read from its versioned real-name file.
    let mut node_by_key: BTreeMap<&str, &BinaryObject> = BTreeMap::new();
    for obj in &objects {
        node_by_key.insert(obj.name.as_str(), obj);
        if let Some(so) = &obj.soname {
            node_by_key.insert(so.as_str(), obj);
        }
        for e in &obj.exports {
            export_index.entry(e.as_str()).or_default().push(obj.name.as_str());
        }
    }

    let mut edges: Vec<BinaryEdge> = Vec::new();
    let mut call_edges: Vec<BinaryCallEdge> = Vec::new();

    for obj in &objects {
        // Which providers we've already linked to via DT_NEEDED — so the
        // Symbol-edge pass only adds the *indirect* resolutions.
        let mut direct_providers: BTreeSet<String> = BTreeSet::new();

        // ── Library DAG: one edge per DT_NEEDED entry ──
        for need in &obj.needed {
            let provider = node_by_key.get(need.as_str());
            let (to_name, resolved, via) = match provider {
                Some(p) => {
                    direct_providers.insert(p.name.clone());
                    // Concrete justification: the symbols obj imports that this
                    // provider exports.
                    let via: BTreeSet<String> =
                        obj.imports.intersection(&p.exports).cloned().collect();
                    (p.name.clone(), true, via)
                }
                // DT_NEEDED on a lib outside the analysed set — link known,
                // symbols not. Keep the edge (the DAG is still recoverable).
                None => (need.clone(), false, BTreeSet::new()),
            };
            edges.push(BinaryEdge {
                from: obj.name.clone(),
                to: to_name,
                kind: EdgeKind::Needed,
                via,
                resolved,
                provenance: Provenance::Binary,
            });
        }

        // ── Symbol resolution: imports satisfied by a NON-DT_NEEDED provider ──
        // (transitive/indirect — the loader would still reach these). Group the
        // extra resolutions per provider so we emit one Symbol edge each.
        let mut indirect: BTreeMap<&str, BTreeSet<String>> = BTreeMap::new();
        for imp in &obj.imports {
            if let Some(providers) = export_index.get(imp.as_str()) {
                for &prov in providers {
                    if prov == obj.name || direct_providers.contains(prov) {
                        continue;
                    }
                    indirect.entry(prov).or_default().insert(imp.clone());
                }
            }
        }
        for (prov, via) in indirect {
            edges.push(BinaryEdge {
                from: obj.name.clone(),
                to: prov.to_string(),
                kind: EdgeKind::Symbol,
                via,
                resolved: true,
                provenance: Provenance::Binary,
            });
        }

        // ── Call edges (stretch): PLT/GOT relocations → external symbols ──
        for (symbol, reloc) in &obj.relocs {
            let resolves_to =
                export_index.get(symbol.as_str()).and_then(|ps| ps.first().map(|s| s.to_string()));
            call_edges.push(BinaryCallEdge {
                from: obj.name.clone(),
                symbol: symbol.clone(),
                reloc: reloc.clone(),
                resolves_to,
                provenance: Provenance::Binary,
            });
        }
    }

    BinaryGraph { objects, edges, call_edges }
}

impl BinaryGraph {
    /// Project onto the shared [`WorkspaceGraph`] so every existing graph
    /// method (build order, blast radius, `dep_path`, SCC/MFAS, …) works on a
    /// binary-only constellation.
    ///
    /// Node `V` → [`RepoFacts`]: `name` = object node name, `produces` =
    /// exported symbols, `consumes` = imported symbols (the direct binary
    /// analogue of a crate's produces/consumes). Edge `E` → [`CrossRepoEdge`]
    /// (`Normal` kind — a link/symbol dependency is always order-gating). The
    /// [`WorkspaceGraph`] itself carries no provenance field; every node/edge's
    /// [`Provenance::Binary`] tag lives on the [`BinaryObject`] / [`BinaryEdge`]
    /// this was built from (and on the [`SymbolRow`]s via
    /// [`to_symbol_rows`](Self::to_symbol_rows)).
    pub fn to_workspace_graph(&self) -> WorkspaceGraph {
        let mut facts: BTreeMap<String, RepoFacts> = BTreeMap::new();
        for obj in &self.objects {
            facts.insert(
                obj.name.clone(),
                RepoFacts {
                    name: obj.name.clone(),
                    root: obj.path.clone(),
                    produces: obj.exports.clone(),
                    consumes: obj.imports.clone(),
                    dev_only_consumes: BTreeSet::new(),
                },
            );
        }
        // Merge multi-symbol edges between the same (from,to) into one edge so
        // the CrossRepoEdge set is one-per-pair (matches the source builder).
        let mut merged: BTreeMap<(String, String), BTreeSet<String>> = BTreeMap::new();
        for e in &self.edges {
            merged.entry((e.from.clone(), e.to.clone())).or_default().extend(e.via.iter().cloned());
        }
        let edges = merged
            .into_iter()
            .map(|((from, to), via)| CrossRepoEdge { from, to, via, kind: DepKind::Normal })
            .collect();
        WorkspaceGraph::from_query_parts(facts, edges)
    }

    /// The provide/need symbol facts as [`SymbolRow`]s (mirrors the source syn
    /// symbol pass) — `item_kind` = `"exported_symbol"` / `"imported_symbol"`,
    /// `visibility` = `"pub"` (export) / `"und"` (import), `crate_name` = the
    /// object node, `file` = the artefact path, `signature` = the demangled
    /// name. The `binary_graph` provenance rides in `module_path`.
    pub fn to_symbol_rows(&self) -> Vec<SymbolRow> {
        let mut rows = Vec::new();
        for obj in &self.objects {
            let file = obj.path.display().to_string();
            for sym in &obj.exports {
                rows.push(SymbolRow {
                    crate_name: obj.name.clone(),
                    module_path: Provenance::Binary.as_str().to_string(),
                    item_kind: "exported_symbol".to_string(),
                    item_name: sym.clone(),
                    visibility: "pub".to_string(),
                    file: file.clone(),
                    line: 0,
                    doc_lines: 0,
                    signature: Some(demangle(sym)),
                });
            }
            for sym in &obj.imports {
                rows.push(SymbolRow {
                    crate_name: obj.name.clone(),
                    module_path: Provenance::Binary.as_str().to_string(),
                    item_kind: "imported_symbol".to_string(),
                    item_name: sym.clone(),
                    visibility: "und".to_string(),
                    file: file.clone(),
                    line: 0,
                    doc_lines: 0,
                    signature: Some(demangle(sym)),
                });
            }
        }
        rows
    }

    /// The PLT/GOT call edges as [`CallEdgeRow`]s (mirrors the source call
    /// graph) — `caller_path` = the calling object, `callee_ident` = the callee
    /// symbol, `call_kind` = the relocation label. The `binary_graph`
    /// provenance rides in `crate_name` suffix via the object node name only, so
    /// `crate_name` stays the object; the marker is implicit in `call_kind`.
    pub fn to_call_edge_rows(&self) -> Vec<CallEdgeRow> {
        self.call_edges
            .iter()
            .map(|c| CallEdgeRow {
                crate_name: c.from.clone(),
                caller_path: c.from.clone(),
                callee_ident: c.symbol.clone(),
                call_kind: format!("plt:{}", c.reloc),
                file: c.resolves_to.clone().unwrap_or_default(),
                line: 0,
            })
            .collect()
    }

    /// Imports that no analysed object exports — the graph's dangling needs
    /// (their providers live outside the handed-in set, e.g. `libc` symbols
    /// when only `libz` was analysed). Keyed by object node name.
    pub fn unresolved_imports(&self) -> BTreeMap<String, BTreeSet<String>> {
        let mut exported: BTreeSet<&str> = BTreeSet::new();
        for obj in &self.objects {
            exported.extend(obj.exports.iter().map(String::as_str));
        }
        let mut out = BTreeMap::new();
        for obj in &self.objects {
            let missing: BTreeSet<String> =
                obj.imports.iter().filter(|i| !exported.contains(i.as_str())).cloned().collect();
            if !missing.is_empty() {
                out.insert(obj.name.clone(), missing);
            }
        }
        out
    }
}

// ─── ELF parsing (pure Rust, `object`) ────────────────────────────────────

/// Detect ELF class (32/64) and dispatch to the generic parser. `Endianness` is
/// a runtime enum in `object`, so one 64-bit and one 32-bit instantiation cover
/// both byte orders. Non-ELF input is a hard error (the caller downgrades it to
/// a skip).
fn parse_object(path: &Path, data: &[u8]) -> Result<BinaryObject> {
    match FileKind::parse(data).context("detecting file kind")? {
        FileKind::Elf64 => {
            let elf = ElfFile64::<Endianness>::parse(data).context("parsing ELF64")?;
            from_elf(path, &elf)
        }
        FileKind::Elf32 => {
            let elf = ElfFile32::<Endianness>::parse(data).context("parsing ELF32")?;
            from_elf(path, &elf)
        }
        other => bail!("{} is not an ELF file (kind {:?})", path.display(), other),
    }
}

/// The generic (class/endian-agnostic) parse: pull `DT_SONAME` / `DT_NEEDED` /
/// `DT_RUNPATH` from the dynamic table, exports/imports from `.dynsym`, and
/// PLT/GOT relocations for call edges — all via the `object` reader.
fn from_elf<'data, Elf, R>(path: &Path, elf: &ElfFile<'data, Elf, R>) -> Result<BinaryObject>
where
    Elf: FileHeader<Endian = Endianness>,
    R: ReadRef<'data>,
{
    let endian = elf.endian();

    // ── Dynamic table: DT_SONAME / DT_NEEDED / DT_RUNPATH (+ DT_RPATH) ──
    let mut soname: Option<String> = None;
    let mut needed: Vec<String> = Vec::new();
    let mut runpath: Vec<String> = Vec::new();
    let dyn_table = elf.elf_dynamic_table().context("reading ELF dynamic table")?;
    for d in dyn_table.iter() {
        // `string()` reads the value as an offset into the dynamic string table
        // (`.dynstr`) — valid for the string-typed tags below.
        let read = |d| dyn_table.string(d).ok().map(|b| String::from_utf8_lossy(b).into_owned());
        match d.tag {
            elf::DT_SONAME => soname = read(d),
            elf::DT_NEEDED => {
                if let Some(s) = read(d) {
                    needed.push(s);
                }
            }
            elf::DT_RUNPATH | elf::DT_RPATH => {
                if let Some(s) = read(d) {
                    runpath.extend(s.split(':').filter(|p| !p.is_empty()).map(str::to_string));
                }
            }
            _ => {}
        }
    }

    // ── Exports / imports from .dynsym ──
    let mut exports: BTreeSet<String> = BTreeSet::new();
    let mut imports: BTreeSet<String> = BTreeSet::new();
    for sym in elf.dynamic_symbols() {
        let name = match sym.name() {
            Ok(n) if !n.is_empty() => n,
            _ => continue,
        };
        // Only FUNC/OBJECT symbols matter for provide/need resolution; skip
        // SECTION/FILE/versioning pseudo-symbols.
        if !matches!(sym.kind(), SymbolKind::Text | SymbolKind::Data | SymbolKind::Unknown) {
            continue;
        }
        if sym.is_undefined() {
            imports.insert(name.to_string());
        } else if sym.is_global() {
            // Defined + global (or weak-global) → an export. Weak defs still
            // satisfy a UND import, so `is_global()` (true for weak) is right.
            exports.insert(name.to_string());
        }
    }

    // ── Call edges (stretch): PLT/GOT dynamic relocations → UND symbols ──
    let mut relocs: Vec<(String, String)> = Vec::new();
    if let (Some(reloc_iter), Some(dynsyms)) =
        (elf.dynamic_relocations(), elf.dynamic_symbol_table())
    {
        for (_addr, reloc) in reloc_iter {
            if let RelocationTarget::Symbol(idx) = reloc.target() {
                if let Ok(sym) = dynsyms.symbol_by_index(idx) {
                    if let Ok(name) = sym.name() {
                        if !name.is_empty() {
                            relocs.push((name.to_string(), format!("{:?}", reloc.kind())));
                        }
                    }
                }
            }
        }
    }

    let class = match elf.elf_header().e_type(endian) {
        elf::ET_EXEC => ObjectClass::Executable,
        // A PIE executable is ET_DYN with an entry point; a plain .so is ET_DYN
        // with entry 0. Distinguish so an executable isn't mislabelled a lib.
        elf::ET_DYN if elf.entry() != 0 => ObjectClass::Executable,
        elf::ET_DYN => ObjectClass::SharedObject,
        elf::ET_REL => ObjectClass::Relocatable,
        _ => ObjectClass::Other,
    };

    // Node key: prefer the soname (stable across versioned real-names), else the
    // file name.
    let name = soname.clone().unwrap_or_else(|| {
        path.file_name().map(|n| n.to_string_lossy().into_owned()).unwrap_or_else(|| {
            path.display().to_string()
        })
    });

    Ok(BinaryObject {
        name,
        path: path.to_path_buf(),
        soname,
        class,
        needed,
        runpath,
        exports,
        imports,
        provenance: Provenance::Binary,
        relocs,
    })
}

#[cfg(test)]
mod tests {
    use super::*;

    /// A synthetic two-node graph exercising the resolution core without any
    /// real ELF: `app` needs `libfoo.so` and imports `foo_hello`, which
    /// `libfoo.so` exports → a resolved `Needed` edge whose `via` names the
    /// concrete symbol.
    fn synth(name: &str, needed: &[&str], exports: &[&str], imports: &[&str]) -> BinaryObject {
        BinaryObject {
            name: name.to_string(),
            path: PathBuf::from(format!("/synthetic/{name}")),
            soname: Some(name.to_string()),
            class: ObjectClass::SharedObject,
            needed: needed.iter().map(|s| s.to_string()).collect(),
            runpath: Vec::new(),
            exports: exports.iter().map(|s| s.to_string()).collect(),
            imports: imports.iter().map(|s| s.to_string()).collect(),
            provenance: Provenance::Binary,
            relocs: Vec::new(),
        }
    }

    #[test]
    fn resolves_needed_edge_to_the_exporting_object() {
        let g = assemble(vec![
            synth("app", &["libfoo.so"], &[], &["foo_hello"]),
            synth("libfoo.so", &[], &["foo_hello"], &[]),
        ]);
        let e = g
            .edges
            .iter()
            .find(|e| e.from == "app" && e.to == "libfoo.so")
            .expect("app → libfoo.so edge");
        assert_eq!(e.kind, EdgeKind::Needed);
        assert!(e.resolved, "provider is in the set");
        assert!(e.via.contains("foo_hello"), "edge justified by the concrete symbol");
    }

    #[test]
    fn dt_needed_outside_the_set_is_an_unresolved_edge() {
        let g = assemble(vec![synth("app", &["libc.so.6"], &[], &["malloc"])]);
        let e = g.edges.iter().find(|e| e.to == "libc.so.6").expect("edge to libc kept");
        assert!(!e.resolved, "provider not analysed");
        assert!(e.via.is_empty());
        // malloc has no analysed exporter → dangling need.
        assert!(g.unresolved_imports().get("app").unwrap().contains("malloc"));
    }

    #[test]
    fn workspace_graph_projection_reuses_blast_radius() {
        // libbar → libfoo (bar imports a foo symbol); a change to libfoo's
        // blast radius must include libbar via the shared graph engine.
        let g = assemble(vec![
            synth("libbar.so", &["libfoo.so"], &["bar_do"], &["foo_hello"]),
            synth("libfoo.so", &[], &["foo_hello"], &[]),
        ]);
        let wg = g.to_workspace_graph();
        assert_eq!(
            wg.dependents_transitive("libfoo.so"),
            ["libbar.so"].iter().map(|s| s.to_string()).collect()
        );
        // produces/consumes carried the exports/imports through.
        assert!(wg.facts.get("libfoo.so").unwrap().produces.contains("foo_hello"));
        assert!(wg.facts.get("libbar.so").unwrap().consumes.contains("foo_hello"));
    }

    #[test]
    fn symbol_rows_tag_binary_provenance() {
        let g = assemble(vec![synth("libfoo.so", &[], &["foo_hello"], &["malloc"])]);
        let rows = g.to_symbol_rows();
        let exp = rows.iter().find(|r| r.item_name == "foo_hello").unwrap();
        assert_eq!(exp.item_kind, "exported_symbol");
        assert_eq!(exp.module_path, super::super::BINARY_GRAPH_PROVENANCE);
        let imp = rows.iter().find(|r| r.item_name == "malloc").unwrap();
        assert_eq!(imp.item_kind, "imported_symbol");
        assert_eq!(imp.visibility, "und");
    }

    /// An import satisfied by a provider that is NOT a direct `DT_NEEDED` yields a
    /// `Symbol` (indirect) edge — the loader would still reach it transitively — and
    /// the direct link stays a `Needed` edge, so the two edge kinds don't collide.
    #[test]
    fn indirect_import_becomes_a_symbol_edge() {
        let g = assemble(vec![
            // app DT_NEEDED only libfoo, but ALSO imports bar_sym (from libbar).
            synth("app", &["libfoo.so"], &[], &["foo_sym", "bar_sym"]),
            synth("libfoo.so", &[], &["foo_sym"], &[]),
            synth("libbar.so", &[], &["bar_sym"], &[]),
        ]);
        let needed = g.edges.iter().find(|e| e.to == "libfoo.so").expect("direct link");
        assert_eq!(needed.kind, EdgeKind::Needed);
        assert!(needed.via.contains("foo_sym"));
        let sym = g.edges.iter().find(|e| e.to == "libbar.so").expect("indirect link");
        assert_eq!(sym.kind, EdgeKind::Symbol, "no DT_NEEDED on libbar ⇒ Symbol edge");
        assert!(sym.resolved && sym.via.contains("bar_sym"));
        // Everything resolved → no dangling imports.
        assert!(g.unresolved_imports().is_empty());
    }

    /// A symbol an object both imports and exports must NOT create a self-edge (the
    /// `prov == obj.name` guard) — a node never depends on itself.
    #[test]
    fn self_provided_symbol_makes_no_edge() {
        let g = assemble(vec![synth("solo.so", &[], &["s"], &["s"])]);
        assert!(g.edges.is_empty(), "an object that provides its own import has no dependency edge");
    }

    /// PLT/GOT relocations become call edges that resolve to the exporting object,
    /// and project to `CallEdgeRow`s with a `plt:` call-kind marker.
    #[test]
    fn plt_relocations_resolve_and_project_to_call_edge_rows() {
        let mut app = synth("app", &["libc.so.6"], &[], &["malloc"]);
        app.relocs = vec![("malloc".to_string(), "Elf(R_X86_64_JUMP_SLOT)".to_string())];
        let g = assemble(vec![app, synth("libc.so.6", &[], &["malloc"], &[])]);
        assert_eq!(g.call_edges.len(), 1);
        let ce = &g.call_edges[0];
        assert_eq!(ce.from, "app");
        assert_eq!(ce.symbol, "malloc");
        assert_eq!(ce.resolves_to.as_deref(), Some("libc.so.6"), "malloc resolves to its exporter");
        assert_eq!(ce.provenance, Provenance::Binary);
        let rows = g.to_call_edge_rows();
        assert_eq!(rows.len(), 1);
        assert_eq!(rows[0].caller_path, "app");
        assert_eq!(rows[0].callee_ident, "malloc");
        assert!(rows[0].call_kind.starts_with("plt:"), "call_kind carries the reloc label");
        assert_eq!(rows[0].file, "libc.so.6", "resolved provider recorded in the row");
    }
}