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,
}
#[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 });
}
}
#[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();
if has_library {
plan.push(CompilationUnitKind::RustLibraries, modules);
}
plan
}
}
#[derive(Debug, Clone)]
pub struct ScriptCompilationInput {
pub path: String,
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> {}
#[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()]));
}
}