lehit 0.2.0

Embeddable Lehit language frontend and Cranelift JIT runtime
Documentation
//! Dependency planning and strongly connected compilation-unit grouping.
//!
//! Mutually recursive script modules are installed atomically; acyclic
//! dependencies are ordered before their dependants.

use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::error::Error;
use std::fmt;

use crate::rust_lib::RustLib;

pub type CompilationUnitId = u32;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CompilationUnitKind {
    RustLibraries,
    Scripts,
}

/// A set of modules which must be installed and removed atomically.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CompilationUnit {
    pub id: CompilationUnitId,
    pub kind: CompilationUnitKind,
    pub modules: BTreeSet<String>,
}

#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct CompilationPlan {
    pub units: Vec<CompilationUnit>,
    module_units: HashMap<String, CompilationUnitId>,
}

impl CompilationPlan {
    pub fn unit_for(&self, module: &str) -> Option<CompilationUnitId> {
        self.module_units.get(module).copied()
    }

    fn push(&mut self, kind: CompilationUnitKind, modules: BTreeSet<String>) {
        let id = self.units.len() as CompilationUnitId;
        for module in &modules {
            self.module_units.insert(module.clone(), id);
        }
        self.units.push(CompilationUnit { id, kind, modules });
    }
}

/// Rust libraries share one backend/JIT namespace and therefore one unit.
#[derive(Debug, Default)]
pub struct RustLibCompilationSystem;

impl RustLibCompilationSystem {
    pub fn plan<'a>(&self, libraries: impl IntoIterator<Item = &'a RustLib>) -> CompilationPlan {
        let mut modules = BTreeSet::new();
        let mut has_library = false;
        for library in libraries {
            has_library = true;
            modules.extend(library.scripts.keys().cloned());
        }

        let mut plan = CompilationPlan::default();
        // Keep a unit for native-only/empty libraries as well.
        if has_library {
            plan.push(CompilationUnitKind::RustLibraries, modules);
        }
        plan
    }
}

#[derive(Debug, Clone)]
pub struct ScriptCompilationInput {
    pub path: String,
    /// Direct script-module dependencies discovered during semantic analysis.
    pub dependencies: Vec<String>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ScriptCompilationError<E> {
    Provider(E),
    MissingScript { requested_by: String, path: String },
    ConflictingDependencies { path: String },
}

impl<E: fmt::Display> fmt::Display for ScriptCompilationError<E> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Provider(error) => write!(f, "script provider failed: {error}"),
            Self::MissingScript { requested_by, path } => {
                write!(
                    f,
                    "script `{requested_by}` requires missing script `{path}`"
                )
            }
            Self::ConflictingDependencies { path } => {
                write!(
                    f,
                    "script `{path}` was provided with different dependencies"
                )
            }
        }
    }
}

impl<E: Error + 'static> Error for ScriptCompilationError<E> {}

/// Loads dependencies on demand, then groups only mutually dependent scripts.
#[derive(Debug, Default)]
pub struct ScriptCompilationSystem;

impl ScriptCompilationSystem {
    pub fn plan<E, F>(
        &self,
        roots: impl IntoIterator<Item = ScriptCompilationInput>,
        mut request_script: F,
    ) -> Result<CompilationPlan, ScriptCompilationError<E>>
    where
        F: FnMut(&str) -> Result<Option<ScriptCompilationInput>, E>,
    {
        let mut scripts = BTreeMap::<String, Vec<String>>::new();
        let mut pending = VecDeque::<(String, Option<String>)>::new();

        for root in roots {
            pending.push_back((root.path.clone(), None));
            insert_script(&mut scripts, root)?;
        }

        let mut expanded = HashSet::new();
        while let Some((path, requested_by)) = pending.pop_front() {
            if !scripts.contains_key(&path) {
                let input = request_script(&path)
                    .map_err(ScriptCompilationError::Provider)?
                    .ok_or_else(|| ScriptCompilationError::MissingScript {
                        requested_by: requested_by.clone().unwrap_or_else(|| "<root>".into()),
                        path: path.clone(),
                    })?;
                if input.path != path {
                    return Err(ScriptCompilationError::MissingScript {
                        requested_by: requested_by.unwrap_or_else(|| "<root>".into()),
                        path,
                    });
                }
                insert_script(&mut scripts, input)?;
            }

            if !expanded.insert(path.clone()) {
                continue;
            }
            for dependency in scripts[&path].clone() {
                pending.push_back((dependency, Some(path.clone())));
            }
        }

        let components = dependency_first_components(&scripts);
        let mut plan = CompilationPlan::default();
        for modules in components {
            plan.push(CompilationUnitKind::Scripts, modules);
        }
        Ok(plan)
    }
}

fn insert_script<E>(
    scripts: &mut BTreeMap<String, Vec<String>>,
    mut input: ScriptCompilationInput,
) -> Result<(), ScriptCompilationError<E>> {
    input.dependencies.sort();
    input.dependencies.dedup();
    match scripts.get(&input.path) {
        Some(dependencies) if dependencies != &input.dependencies => {
            Err(ScriptCompilationError::ConflictingDependencies { path: input.path })
        }
        Some(_) => Ok(()),
        None => {
            scripts.insert(input.path, input.dependencies);
            Ok(())
        }
    }
}

fn dependency_first_components(graph: &BTreeMap<String, Vec<String>>) -> Vec<BTreeSet<String>> {
    let components = strongly_connected_components(graph);
    let mut component_for = HashMap::new();
    for (index, component) in components.iter().enumerate() {
        for module in component {
            component_for.insert(module.as_str(), index);
        }
    }
    let mut ordered = Vec::with_capacity(components.len());
    let mut visited = HashSet::new();
    fn visit(
        index: usize,
        graph: &BTreeMap<String, Vec<String>>,
        components: &[BTreeSet<String>],
        component_for: &HashMap<&str, usize>,
        visited: &mut HashSet<usize>,
        ordered: &mut Vec<BTreeSet<String>>,
    ) {
        if !visited.insert(index) {
            return;
        }
        for module in &components[index] {
            for dependency in &graph[module] {
                let dependency_index = component_for[dependency.as_str()];
                if dependency_index != index {
                    visit(
                        dependency_index,
                        graph,
                        components,
                        component_for,
                        visited,
                        ordered,
                    );
                }
            }
        }
        ordered.push(components[index].clone());
    }
    for index in 0..components.len() {
        visit(
            index,
            graph,
            &components,
            &component_for,
            &mut visited,
            &mut ordered,
        );
    }
    ordered
}

fn strongly_connected_components(graph: &BTreeMap<String, Vec<String>>) -> Vec<BTreeSet<String>> {
    struct Tarjan<'a> {
        graph: &'a BTreeMap<String, Vec<String>>,
        next_index: usize,
        indices: HashMap<String, usize>,
        lowlinks: HashMap<String, usize>,
        stack: Vec<String>,
        on_stack: HashSet<String>,
        components: Vec<BTreeSet<String>>,
    }

    fn visit(node: &str, state: &mut Tarjan<'_>) {
        let index = state.next_index;
        state.next_index += 1;
        state.indices.insert(node.to_owned(), index);
        state.lowlinks.insert(node.to_owned(), index);
        state.stack.push(node.to_owned());
        state.on_stack.insert(node.to_owned());

        for dependency in &state.graph[node] {
            if !state.indices.contains_key(dependency) {
                visit(dependency, state);
                let low = state.lowlinks[node].min(state.lowlinks[dependency]);
                state.lowlinks.insert(node.to_owned(), low);
            } else if state.on_stack.contains(dependency) {
                let low = state.lowlinks[node].min(state.indices[dependency]);
                state.lowlinks.insert(node.to_owned(), low);
            }
        }

        if state.lowlinks[node] == state.indices[node] {
            let mut component = BTreeSet::new();
            loop {
                let member = state.stack.pop().expect("current node is on Tarjan stack");
                state.on_stack.remove(&member);
                component.insert(member.clone());
                if member == node {
                    break;
                }
            }
            state.components.push(component);
        }
    }

    let mut state = Tarjan {
        graph,
        next_index: 0,
        indices: HashMap::new(),
        lowlinks: HashMap::new(),
        stack: Vec::new(),
        on_stack: HashSet::new(),
        components: Vec::new(),
    };
    for node in graph.keys() {
        if !state.indices.contains_key(node) {
            visit(node, &mut state);
        }
    }
    state
        .components
        .sort_by(|left, right| left.iter().next().cmp(&right.iter().next()));
    state.components
}

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

    #[test]
    fn requests_dependencies_and_groups_only_cycles() {
        let root = ScriptCompilationInput {
            path: "a".into(),
            dependencies: vec!["b".into()],
        };
        let mut requested = Vec::new();
        let plan = ScriptCompilationSystem
            .plan([root], |path| {
                requested.push(path.to_owned());
                Ok::<_, ()>(Some(ScriptCompilationInput {
                    path: path.into(),
                    dependencies: vec!["a".into()],
                }))
            })
            .unwrap();

        assert_eq!(requested, ["b"]);
        assert_eq!(plan.units.len(), 1);
        assert_eq!(
            plan.units[0].modules,
            BTreeSet::from(["a".into(), "b".into()])
        );
    }

    #[test]
    fn one_way_dependency_stays_removable() {
        let plan = ScriptCompilationSystem
            .plan(
                [ScriptCompilationInput {
                    path: "a".into(),
                    dependencies: vec!["b".into()],
                }],
                |path| {
                    Ok::<_, ()>(Some(ScriptCompilationInput {
                        path: path.into(),
                        dependencies: vec![],
                    }))
                },
            )
            .unwrap();

        assert_eq!(plan.units.len(), 2);
        assert_ne!(plan.unit_for("a"), plan.unit_for("b"));
        assert_eq!(plan.units[0].modules, BTreeSet::from(["b".into()]));
        assert_eq!(plan.units[1].modules, BTreeSet::from(["a".into()]));
    }
}