engenho-runtime 0.53.131

//! The impl census: which types implement a trait, read off the workspace's
//! shipped source (T5.11). Test-only.
//!
//! Rust cannot enumerate a trait's implementors, so the gate that every
//! `Controller` type is spawned or declared [`Dormant`](crate::Dormant)
//! takes its list of controller types from here. It lexes each crate's
//! `src/` with the read census's lexer (comments and string literals are
//! never read as code), drops every `#[cfg(test)]` item, and reads each
//! `impl … Trait for Type` it finds.
//!
//! It is a gate, not a proof:
//!
//! * `tests/`, `examples/` and `benches/` are not read: they ship nothing.
//!   A test-only module kept in its own file (`#[cfg(test)] mod x;`) IS
//!   read, so a fake controller there is reported as shipped — loudly, the
//!   safe direction.
//! * A trait path is ours when it is bare or starts at `crate`, `self`,
//!   `super` or `engenho_controllers`. `pb::controller_server::Controller`
//!   (the CSI gRPC trait) is not. A file that imports another crate's
//!   `Controller` and implements it bare is counted — loudly again.
//! * A blanket `impl<T: Bound> Trait for T` makes every implementor of
//!   `Bound` an implementor; the census follows it. One whose bound is in a
//!   `where` clause, or that has two bounds, stops the census with a
//!   message instead of guessing.
//! * An impl generated by a macro is not seen.

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

use crate::read_census::{Tok, lex, strip_test_items};

/// One Rust source file of a workspace crate.
#[derive(Clone, Debug)]
pub(crate) struct Source {
    /// Relative to the workspace root, for failure messages.
    pub(crate) path: String,
    /// The crate's name as a path segment (`engenho_controllers`).
    pub(crate) krate: String,
    pub(crate) text: String,
}

/// How an implementing type relates to its impl's generic parameters.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Shape {
    /// A type in its own right, generic or not.
    Concrete,
    /// Generic over a parameter bounded by the trait itself: an adapter that
    /// hands the work to another implementor (`Arc<C: Controller>`).
    Forwarding,
    /// `impl<T: Bound> Trait for T`: every implementor of the bound is one.
    Blanket { bounds: Vec<String> },
}

/// One implementing type, where the census found it.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(crate) struct Implementor {
    /// The crate that defines it.
    pub(crate) krate: String,
    /// Its own name: the last path segment, without generic arguments.
    pub(crate) ident: String,
    /// The file the impl is in.
    pub(crate) path: String,
}

/// The implementors of one trait across some sources.
#[derive(Clone, Debug, Default)]
pub(crate) struct Implementors {
    /// Types that implement it in their own right.
    pub(crate) concrete: BTreeSet<Implementor>,
    /// Adapters that forward it to another implementor.
    pub(crate) forwarding: BTreeSet<Implementor>,
}

impl Implementors {
    /// Every implementor of `trait_name` in `sources`, following blanket
    /// impls to the implementors of their bound.
    pub(crate) fn of(sources: &[Source], trait_name: &str) -> Self {
        let mut out = Self::default();
        let mut visited = BTreeSet::new();
        out.collect(sources, trait_name, &mut visited);
        out
    }

    fn collect(&mut self, sources: &[Source], trait_name: &str, visited: &mut BTreeSet<String>) {
        if !visited.insert(trait_name.to_owned()) {
            return;
        }
        for source in sources {
            for (ident, shape) in impls_in(&source.text, trait_name) {
                let found = Implementor {
                    krate: source.krate.clone(),
                    ident,
                    path: source.path.clone(),
                };
                match shape {
                    Shape::Concrete => {
                        self.concrete.insert(found);
                    }
                    Shape::Forwarding => {
                        self.forwarding.insert(found);
                    }
                    Shape::Blanket { bounds } => {
                        let [bound] = bounds.as_slice() else {
                            panic!(
                                "{}: a blanket impl of {trait_name} over {bounds:?} — the census \
                                 follows exactly one inline bound; teach it this one",
                                source.path
                            );
                        };
                        self.collect(sources, bound, visited);
                    }
                }
            }
        }
    }
}

/// The shipped source of every crate in the workspace at `root`: each
/// directory holding a `Cargo.toml` and a `src/`, every `.rs` file under
/// that `src/`.
pub(crate) fn workspace_sources(root: &Path) -> Vec<Source> {
    let mut sources = Vec::new();
    for dir in sorted_entries(root) {
        let name = dir
            .file_name()
            .and_then(|n| n.to_str())
            .unwrap_or_default()
            .to_owned();
        if name.starts_with('.') || name == "target" {
            continue;
        }
        let src = dir.join("src");
        if !dir.join("Cargo.toml").is_file() || !src.is_dir() {
            continue;
        }
        let krate = name.replace('-', "_");
        for file in rust_files(&src) {
            let text = std::fs::read_to_string(&file)
                .unwrap_or_else(|e| panic!("reading {}: {e}", file.display()));
            let path = file
                .strip_prefix(root)
                .unwrap_or(&file)
                .display()
                .to_string();
            sources.push(Source {
                path,
                krate: krate.clone(),
                text,
            });
        }
    }
    sources
}

fn sorted_entries(dir: &Path) -> Vec<PathBuf> {
    let mut entries: Vec<PathBuf> = std::fs::read_dir(dir)
        .unwrap_or_else(|e| panic!("listing {}: {e}", dir.display()))
        .map(|entry| {
            entry
                .unwrap_or_else(|e| panic!("listing {}: {e}", dir.display()))
                .path()
        })
        .collect();
    entries.sort();
    entries
}

fn rust_files(dir: &Path) -> Vec<PathBuf> {
    let mut files = Vec::new();
    for entry in sorted_entries(dir) {
        if entry.is_dir() {
            files.extend(rust_files(&entry));
        } else if entry.extension().is_some_and(|e| e == "rs") {
            files.push(entry);
        }
    }
    files
}

/// Path prefixes under which a trait named like ours is ours.
const OURS: &[&str] = &["crate", "self", "super", "engenho_controllers"];

/// Every `impl … <trait_name> for Type` in `src` outside `#[cfg(test)]`
/// items: the type's own name and its [`Shape`].
pub(crate) fn impls_in(src: &str, trait_name: &str) -> Vec<(String, Shape)> {
    let tokens = strip_test_items(&lex(src));
    let mut found = Vec::new();
    for (i, tok) in tokens.iter().enumerate() {
        if *tok == Tok::Ident("impl".into())
            && let Some(item) = trait_impl_at(&tokens, i + 1)
        {
            let ours = item.trait_path.split_last().is_some_and(|(last, prefix)| {
                last == trait_name
                    && prefix
                        .first()
                        .is_none_or(|first| OURS.contains(&first.as_str()))
            });
            if ours {
                found.push((item.self_ident.clone(), item.shape(trait_name)));
            }
        }
    }
    found
}

/// A generic parameter of an impl and the traits bounding it inline.
#[derive(Debug)]
struct Param {
    name: String,
    bounds: Vec<String>,
}

/// The parts of `impl<…> Trait for Type` the census reads.
#[derive(Debug)]
struct TraitImpl {
    params: Vec<Param>,
    /// The trait's path segments, generic arguments dropped.
    trait_path: Vec<String>,
    /// The implementing type's path segments, generic arguments dropped.
    self_path: Vec<String>,
    self_ident: String,
    /// Every identifier inside the implementing type's generic arguments.
    self_args: Vec<String>,
}

impl TraitImpl {
    fn shape(&self, trait_name: &str) -> Shape {
        let param = |name: &str| self.params.iter().find(|p| p.name == name);
        if let [only] = self.self_path.as_slice()
            && let Some(p) = param(only)
        {
            return Shape::Blanket {
                bounds: p
                    .bounds
                    .iter()
                    .filter(|b| !AUTO.contains(&b.as_str()))
                    .cloned()
                    .collect(),
            };
        }
        let forwards = self
            .self_args
            .iter()
            .filter_map(|a| param(a))
            .any(|p| p.bounds.iter().any(|b| b == trait_name));
        if forwards {
            Shape::Forwarding
        } else {
            Shape::Concrete
        }
    }
}

/// Bounds that say nothing about which implementors a blanket impl covers.
const AUTO: &[&str] = &["Send", "Sync", "Sized", "Unpin"];

/// Read `<…> Trait for Type` starting just after an `impl` keyword; `None`
/// when this `impl` is not a trait impl item (an inherent impl, or `impl
/// Trait` in a signature).
fn trait_impl_at(tokens: &[Tok], mut i: usize) -> Option<TraitImpl> {
    let mut params = Vec::new();
    if tokens.get(i) == Some(&Tok::Punct('<')) {
        let close = angle_close(tokens, i)?;
        params = generic_params(&tokens[i + 1..close]);
        i = close + 1;
    }
    // The trait path runs to `for`; a `{`, `;`, `where` or an unbalanced
    // bracket first means this is not `impl Trait for Type`.
    let for_at = scan_depth0(tokens, i, |t| *t == Tok::Ident("for".into()))?;
    let trait_path = path_segments(&tokens[i..for_at]);
    // The implementing type runs to the header's end: its `where` or `{`.
    let body = scan_depth0(tokens, for_at + 1, |t| {
        *t == Tok::Punct('{') || *t == Tok::Ident("where".into())
    })?;
    let self_tokens = &tokens[for_at + 1..body];
    let self_path = path_segments(self_tokens);
    let self_ident = self_path.last()?.clone();
    let self_args = self_tokens
        .iter()
        .skip_while(|t| **t != Tok::Punct('<'))
        .filter_map(|t| match t {
            Tok::Ident(name) => Some(name.clone()),
            Tok::Str(_) | Tok::Punct(_) | Tok::Other => None,
        })
        .collect();
    Some(TraitImpl {
        params,
        trait_path,
        self_path,
        self_ident,
        self_args,
    })
}

/// The index of the first token from `start` at bracket depth zero that
/// `hit` accepts (checked first, so `hit` may accept `{` or `where`);
/// `None` if a `{`, `;` or `where` at depth zero, or a bracket closing past
/// depth zero, comes first. A `<…>` is skipped whole.
fn scan_depth0(tokens: &[Tok], start: usize, hit: impl Fn(&Tok) -> bool) -> Option<usize> {
    let mut depth = 0usize;
    let mut i = start;
    while i < tokens.len() {
        let tok = &tokens[i];
        if depth == 0 && hit(tok) {
            return Some(i);
        }
        match tok {
            Tok::Punct('(' | '[') => depth += 1,
            Tok::Punct(')' | ']') => depth = depth.checked_sub(1)?,
            Tok::Punct('<') => i = angle_close(tokens, i)?,
            Tok::Punct('{' | ';') if depth == 0 => return None,
            Tok::Ident(word) if depth == 0 && word == "where" => return None,
            Tok::Ident(_) | Tok::Str(_) | Tok::Punct(_) | Tok::Other => {}
        }
        i += 1;
    }
    None
}

/// The index of the `>` closing the `<` at `open`. A `>` straight after a
/// `-` is an arrow (`Fn() -> T`), not a close.
fn angle_close(tokens: &[Tok], open: usize) -> Option<usize> {
    let mut depth = 0usize;
    for i in open..tokens.len() {
        match &tokens[i] {
            Tok::Punct('<') => depth += 1,
            Tok::Punct('>') if i > 0 && tokens[i - 1] == Tok::Punct('-') => {}
            Tok::Punct('>') => {
                depth = depth.checked_sub(1)?;
                if depth == 0 {
                    return Some(i);
                }
            }
            Tok::Ident(_) | Tok::Str(_) | Tok::Punct(_) | Tok::Other => {}
        }
    }
    None
}

/// The identifiers of a path at angle depth zero: `std::sync::Arc<C>` is
/// `[std, sync, Arc]`.
fn path_segments(tokens: &[Tok]) -> Vec<String> {
    let mut segments = Vec::new();
    let mut depth = 0usize;
    for (i, tok) in tokens.iter().enumerate() {
        match tok {
            Tok::Punct('<') => depth += 1,
            Tok::Punct('>') if i > 0 && tokens[i - 1] == Tok::Punct('-') => {}
            Tok::Punct('>') => depth = depth.saturating_sub(1),
            Tok::Ident(name) if depth == 0 && name != "dyn" => segments.push(name.clone()),
            Tok::Ident(_) | Tok::Str(_) | Tok::Punct(_) | Tok::Other => {}
        }
    }
    segments
}

/// The parameters inside an impl's `<…>` (brackets excluded), each with the
/// identifiers of its inline bounds. Lifetimes are skipped; `const N: T`
/// is a parameter whose "bound" is its type.
fn generic_params(tokens: &[Tok]) -> Vec<Param> {
    let mut params = Vec::new();
    for part in split_top_level_commas(tokens) {
        let mut idents = part.iter().filter_map(|t| match t {
            Tok::Ident(name) => Some(name.clone()),
            Tok::Str(_) | Tok::Punct(_) | Tok::Other => None,
        });
        let Some(mut name) = idents.next() else {
            continue; // a lifetime
        };
        if name == "const" {
            let Some(real) = idents.next() else { continue };
            name = real;
        }
        let bounds = part
            .iter()
            .position(|t| *t == Tok::Punct(':'))
            .map(|colon| path_segments_per_bound(&part[colon + 1..]))
            .unwrap_or_default();
        params.push(Param { name, bounds });
    }
    params
}

/// The last path segment of each `+`-separated bound: `crate::Controller +
/// ?Sized + 'static` is `[Controller, Sized]`.
fn path_segments_per_bound(tokens: &[Tok]) -> Vec<String> {
    tokens
        .split(|t| *t == Tok::Punct('+'))
        .filter_map(|bound| path_segments(bound).last().cloned())
        .collect()
}

/// `tokens` split at commas outside any bracket.
fn split_top_level_commas(tokens: &[Tok]) -> Vec<&[Tok]> {
    let mut parts = Vec::new();
    let mut depth = 0usize;
    let mut start = 0;
    for (i, tok) in tokens.iter().enumerate() {
        match tok {
            Tok::Punct('(' | '[' | '{' | '<') => depth += 1,
            Tok::Punct('>') if i > 0 && tokens[i - 1] == Tok::Punct('-') => {}
            Tok::Punct(')' | ']' | '}' | '>') => depth = depth.saturating_sub(1),
            Tok::Punct(',') if depth == 0 => {
                parts.push(&tokens[start..i]);
                start = i + 1;
            }
            Tok::Ident(_) | Tok::Str(_) | Tok::Punct(_) | Tok::Other => {}
        }
    }
    parts.push(&tokens[start..]);
    parts
}

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

    fn impls(src: &str) -> Vec<(String, Shape)> {
        impls_in(src, "Controller")
    }

    fn concrete(names: &[&str]) -> Vec<(String, Shape)> {
        names
            .iter()
            .map(|n| ((*n).to_owned(), Shape::Concrete))
            .collect()
    }

    /// The positive control: every impl shape the census claims to read,
    /// read. A census gone blind would pass the gate vacuously.
    #[test]
    fn it_sees_every_impl_shape_it_claims() {
        let found = impls(
            r"
            #[async_trait]
            impl Controller for Plain {
                fn name(&self) -> &'static str { 'x'; }
            }
            impl engenho_controllers::Controller for Qualified {}
            impl crate::controller::Controller for InCrate {}
            impl<E: Clone + Send + Sync + 'static> Controller for Generic<E> {}
            impl<F: Fn() -> u8> Controller for WithArrow<F> {}
            impl<C: Controller + ?Sized> Controller for std::sync::Arc<C> {}
            impl<C: crate::Controller> Controller for Wrap<C> where C: Send {}
            impl<T: OwnedChildrenReconciler + Send> Controller for T {}
            ",
        );
        let mut want = concrete(&["Plain", "Qualified", "InCrate", "Generic", "WithArrow"]);
        want.push(("Arc".into(), Shape::Forwarding));
        want.push(("Wrap".into(), Shape::Forwarding));
        want.push((
            "T".into(),
            Shape::Blanket {
                bounds: vec!["OwnedChildrenReconciler".into()],
            },
        ));
        assert_eq!(found, want);
    }

    /// Text that only looks like an implementor: comments, strings, other
    /// crates' traits of the same name, other traits, inherent impls,
    /// `impl Trait` in signatures, and test code.
    #[test]
    fn it_does_not_see_what_is_not_an_implementor() {
        let found = impls(
            r##"
            // impl Controller for InAComment {}
            /* impl Controller for InABlock {} */
            const DOC: &str = "impl Controller for InAString {}";
            const RAW: &str = r#"impl Controller for InARawString {}"#;
            impl pb::controller_server::Controller for Grpc {}
            impl TargetController for Other {}
            impl ControllerExt for Ext {}
            impl Inherent { fn f() {} }
            impl<T> Inherent2<T> { fn g(&self) { for x in y {} } }
            fn all() -> impl Iterator<Item = u8> { for c in cs {} }
            fn arg(x: impl Fn(), y: u8) where for<'a> X: Y { for z in w {} }
            #[cfg(test)]
            mod tests {
                impl Controller for InATest {}
            }
            #[cfg(test)]
            impl Controller for InATestImpl {}
            impl Controller for AfterTheTests {}
            "##,
        );
        assert_eq!(found, concrete(&["AfterTheTests"]));
    }

    /// A blanket impl is followed to the implementors of its bound: those
    /// are the controller types, and `T` is not one.
    #[test]
    fn a_blanket_impl_is_followed_to_its_bounds_implementors() {
        let source = |path: &str, text: &str| Source {
            path: path.to_owned(),
            krate: "fixture".to_owned(),
            text: text.to_owned(),
        };
        let sources = [
            source(
                "owned.rs",
                "impl<T: OwnedChildrenReconciler> Controller for T {}\n\
                 impl<C: Controller> Controller for Adapter<C> {}",
            ),
            source(
                "deployment.rs",
                "impl OwnedChildrenReconciler for DeploymentController {}",
            ),
            source("gc.rs", "impl Controller for GcController {}"),
        ];
        let found = Implementors::of(&sources, "Controller");
        let idents =
            |set: &BTreeSet<Implementor>| set.iter().map(|i| i.ident.clone()).collect::<Vec<_>>();
        assert_eq!(
            idents(&found.concrete),
            ["DeploymentController", "GcController"]
        );
        assert_eq!(idents(&found.forwarding), ["Adapter"]);
    }

    #[test]
    #[should_panic(expected = "teach it this one")]
    fn a_blanket_impl_it_cannot_follow_stops_the_census() {
        let sources = [Source {
            path: "where.rs".to_owned(),
            krate: "fixture".to_owned(),
            text: "impl<T> Controller for T where T: Other {}".to_owned(),
        }];
        let _ = Implementors::of(&sources, "Controller");
    }
}