use crate::{code, fed};
use std::path::{Path, PathBuf};
mod cycle;
mod shell;
pub use cycle::cycles;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Unresolved {
pub node: String,
pub script: String,
pub call: String,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CodeDep {
pub node: String,
pub needs: Vec<String>,
pub seam: Vec<String>,
}
#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub struct Schedule {
pub rounds: Vec<Vec<String>>,
pub blocked: Vec<String>,
pub edges: usize,
pub blocking: usize,
}
impl Schedule {
#[must_use]
pub fn depth(&self) -> usize {
self.rounds.len()
}
#[must_use]
pub fn width(&self) -> usize {
self.rounds.iter().map(Vec::len).max().unwrap_or(0)
}
}
#[must_use]
pub fn code_deps(root: &Path) -> Vec<CodeDep> {
let nodes = fed::discover(root);
let scripts = fed::script_files(root);
nodes
.iter()
.map(|n| {
let (mut needs, mut seam) = edges_of(root, n, &nodes);
needs.extend(script_edges(root, n, &nodes, &scripts));
dedup(&mut needs);
seam.retain(|l| !needs.contains(l));
CodeDep {
node: fed::node_label(root, n),
needs,
seam,
}
})
.collect()
}
fn edges_of(
root: &Path,
node: &Path,
nodes: &[PathBuf],
) -> (Vec<String>, Vec<String>) {
let sibs = siblings_of(root, node, nodes);
let mut needs: Vec<String> = Vec::new();
let mut seam: Vec<String> = Vec::new();
for src in owned_sources(node, nodes) {
for import in code::crate_imports(&src) {
let Some(label) = sibling_label(&sibs, &import.module) else {
continue;
};
let target = node_path(root, &label);
if type_only(&import, &declared_types(&target, nodes)) {
seam.push(label);
} else {
needs.push(label);
}
}
}
dedup(&mut needs);
dedup(&mut seam);
seam.retain(|l| !needs.contains(l));
(needs, seam)
}
fn script_edges(
root: &Path,
node: &Path,
nodes: &[PathBuf],
all: &[PathBuf],
) -> Vec<String> {
let sibs: Vec<PathBuf> = nodes
.iter()
.filter(|n| n.as_path() != node && n.parent() == node.parent())
.cloned()
.collect();
let mut out = Vec::new();
for (_, target) in script_calls(root, node, nodes, all) {
if let shell::Target::Script(p) | shell::Target::Inferred(p) = target
&& let Some(s) = sibs.iter().find(|s| p.starts_with(s))
{
out.push(fed::node_label(root, s));
}
}
out
}
fn script_calls(
root: &Path,
node: &Path,
nodes: &[PathBuf],
all: &[PathBuf],
) -> Vec<(PathBuf, shell::Target)> {
let mut out = Vec::new();
for script in fed::owned_script_files(node, nodes) {
let Ok(text) = std::fs::read_to_string(&script) else {
continue;
};
let cx = shell::Context {
script: &script,
root,
all,
};
for t in shell::calls(&text, &cx) {
out.push((script.clone(), t));
}
}
out
}
#[must_use]
pub fn unresolved_calls(root: &Path, dir: &Path) -> Vec<Unresolved> {
let nodes = fed::discover(root);
let all = fed::script_files(root);
let mut out: Vec<Unresolved> = Vec::new();
for node in nodes.iter().filter(|n| n.starts_with(dir)) {
for (script, target) in script_calls(root, node, &nodes, &all) {
if let shell::Target::Unresolved(call) = target {
out.push(Unresolved {
node: fed::node_label(root, node),
script: fed::node_label(root, &script),
call,
});
}
}
}
out.sort_by(|a, b| {
a.script.cmp(&b.script).then_with(|| a.call.cmp(&b.call))
});
out.dedup();
out
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum EdgeKind {
Blocking,
TypeOnly,
}
impl EdgeKind {
#[must_use]
pub fn as_str(self) -> &'static str {
match self {
Self::Blocking => "blocking",
Self::TypeOnly => "type-only",
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Edge {
pub from: String,
pub to: String,
pub kind: EdgeKind,
pub sibling: bool,
pub inferred: bool,
}
#[must_use]
pub fn edges(root: &Path, dir: &Path) -> Vec<Edge> {
let nodes = fed::discover(root);
let all = fed::script_files(root);
let mut out: Vec<Edge> = Vec::new();
for node in nodes.iter().filter(|n| n.starts_with(dir)) {
for e in rust_edges(root, node, &nodes)
.into_iter()
.chain(shell_edges(root, dir, node, &nodes, &all))
{
merge(&mut out, e);
}
}
let scope: Vec<String> = nodes
.iter()
.filter(|n| n.starts_with(dir))
.map(|n| fed::node_label(root, n))
.collect();
out.retain(|e| scope.contains(&e.to));
out.sort();
out
}
fn rust_edges(root: &Path, node: &Path, nodes: &[PathBuf]) -> Vec<Edge> {
let from = fed::node_label(root, node);
let (needs, seam) = edges_of(root, node, nodes);
let edge = |to: String, kind| Edge {
from: from.clone(),
to,
kind,
sibling: true,
inferred: false,
};
needs
.into_iter()
.map(|t| edge(t, EdgeKind::Blocking))
.chain(seam.into_iter().map(|t| edge(t, EdgeKind::TypeOnly)))
.collect()
}
fn shell_edges(
root: &Path,
dir: &Path,
node: &Path,
nodes: &[PathBuf],
all: &[PathBuf],
) -> Vec<Edge> {
let from = fed::node_label(root, node);
let mut out = Vec::new();
for (_, target) in script_calls(root, node, nodes, all) {
let (p, inferred) = match target {
shell::Target::Script(p) => (p, false),
shell::Target::Inferred(p) => (p, true),
shell::Target::Unresolved(_) => continue,
};
let Some(owner) = owner_of(&p, nodes) else {
continue;
};
if owner == node || !owner.starts_with(dir) {
continue;
}
out.push(Edge {
from: from.clone(),
to: fed::node_label(root, owner),
kind: EdgeKind::Blocking,
sibling: under_sibling(node, owner, nodes),
inferred,
});
}
out
}
fn under_sibling(node: &Path, owner: &Path, nodes: &[PathBuf]) -> bool {
nodes.iter().any(|s| {
s.as_path() != node
&& s.parent() == node.parent()
&& owner.starts_with(s)
})
}
fn merge(out: &mut Vec<Edge>, e: Edge) {
if let Some(have) =
out.iter_mut().find(|h| h.from == e.from && h.to == e.to)
{
have.kind = have.kind.min(e.kind);
have.inferred &= e.inferred;
return;
}
out.push(e);
}
fn owner_of<'a>(p: &Path, nodes: &'a [PathBuf]) -> Option<&'a Path> {
nodes
.iter()
.filter(|n| p.starts_with(n))
.max_by_key(|n| n.components().count())
.map(PathBuf::as_path)
}
#[must_use]
pub fn wave_with_cycles(
root: &Path,
dir: &Path,
) -> (Schedule, Vec<Vec<String>>) {
let deps = scoped_deps(root, dir);
let s = schedule(&deps);
let c = cycles(&deps, &s.blocked);
(s, c)
}
fn type_only(import: &code::Import, types: &[String]) -> bool {
!import.items.is_empty() && import.items.iter().all(|i| types.contains(i))
}
fn declared_types(node: &Path, nodes: &[PathBuf]) -> Vec<String> {
code::types_in(&owned_sources(node, nodes))
.into_iter()
.map(|t| t.name)
.collect()
}
fn dedup(v: &mut Vec<String>) {
v.sort();
v.dedup();
}
fn sibling_label(sibs: &[(String, String)], name: &str) -> Option<String> {
sibs.iter()
.find(|(n, _)| n == name)
.map(|(_, label)| label.clone())
}
fn siblings_of(
root: &Path,
node: &Path,
nodes: &[PathBuf],
) -> Vec<(String, String)> {
let parent = node.parent();
nodes
.iter()
.filter(|n| n.as_path() != node && n.parent() == parent)
.filter_map(|n| {
let name = n.file_name()?.to_string_lossy().to_string();
Some((name, fed::node_label(root, n)))
})
.collect()
}
fn owned_sources(node: &Path, nodes: &[PathBuf]) -> Vec<String> {
fed::owned_rust_files(node, nodes)
.iter()
.filter_map(|f| std::fs::read_to_string(f).ok())
.collect()
}
#[must_use]
pub fn schedule(deps: &[CodeDep]) -> Schedule {
let mut out = Schedule {
blocking: deps.iter().map(|d| d.needs.len()).sum(),
edges: deps
.iter()
.map(|d| d.needs.len().saturating_add(d.seam.len()))
.sum(),
..Schedule::default()
};
let mut built: Vec<String> = Vec::new();
let mut rest: Vec<&CodeDep> = deps.iter().collect();
while !rest.is_empty() {
let (ready, waiting) = split_ready(rest, &built);
if ready.is_empty() {
out.blocked = labels(&waiting);
break;
}
built.extend(labels(&ready));
out.rounds.push(labels(&ready));
rest = waiting;
}
out
}
fn split_ready<'a>(
rest: Vec<&'a CodeDep>,
built: &[String],
) -> (Vec<&'a CodeDep>, Vec<&'a CodeDep>) {
rest.into_iter()
.partition(|d| d.needs.iter().all(|n| built.contains(n)))
}
fn labels(ds: &[&CodeDep]) -> Vec<String> {
let mut out: Vec<String> = ds.iter().map(|d| d.node.clone()).collect();
out.sort();
out
}
#[must_use]
pub fn wave(root: &Path, dir: &Path) -> Schedule {
schedule(&scoped_deps(root, dir))
}
fn scoped_deps(root: &Path, dir: &Path) -> Vec<CodeDep> {
let deps = code_deps(root);
let keep: Vec<String> = deps
.iter()
.map(|d| d.node.clone())
.filter(|l| node_path(root, l).starts_with(dir))
.collect();
scoped(&deps, &keep)
}
fn node_path(root: &Path, label: &str) -> PathBuf {
if label == "." {
root.to_path_buf()
} else {
root.join(label)
}
}
fn within(labels: &[String], keep: &[String]) -> Vec<String> {
labels
.iter()
.filter(|l| keep.contains(l))
.cloned()
.collect()
}
fn scoped(deps: &[CodeDep], keep: &[String]) -> Vec<CodeDep> {
deps.iter()
.filter(|d| keep.contains(&d.node))
.map(|d| CodeDep {
node: d.node.clone(),
needs: within(&d.needs, keep),
seam: within(&d.seam, keep),
})
.collect()
}
#[cfg(test)]
#[path = "tests/wave.rs"]
mod wave_tests;
#[cfg(test)]
#[path = "tests/shell.rs"]
mod shell_tests;
#[cfg(test)]
#[path = "tests/shell_var.rs"]
mod shell_var_tests;
#[cfg(test)]
#[path = "tests/edges.rs"]
mod edges_tests;