use super::Compiler;
use crate::common::diagnostic::Diagnostic;
use crate::common::error::{names_listed, twice, TICK_DECLARED};
use crate::flow::{Node, NodeId, Outcome};
use crate::syntax::ast::TICK;
use indexmap::IndexSet;
use smol_str::SmolStr;
use std::collections::{HashMap, HashSet};
use temple_dsl::{ExprUnit, InputRead, Span};
impl Compiler<'_> {
pub(super) fn check_entries(&mut self, node_ids: &HashMap<SmolStr, NodeId>) -> Vec<NodeId> {
let ast = self.ast;
if ast.entry_names().next().is_none() {
let span = ast.name.as_ref().map_or(Span::new(0, 0), |name| name.span);
self.push(
Diagnostic::error(span, "this flow has no `entry`")
.with_help("add `entry <node>` to say where a new run starts"),
);
}
let mut entries = Vec::new();
let mut seen = HashSet::new();
for entry in ast.entry_names() {
let Some(&id) = node_ids.get(&entry.name) else {
self.unknown_node(entry, node_ids);
continue;
};
if !seen.insert(id) {
self.error(entry.span, twice("entry", &entry.name));
continue;
}
if !ast.nodes[id.index()].params.is_empty() {
self.push(
Diagnostic::error(entry.span, format!("entry node `{}` takes parameters", entry.name))
.with_help("a run that starts here has nothing to fill them with; read `input.data` instead"),
);
}
entries.push(id);
}
entries
}
pub(super) fn check_events(&mut self) -> IndexSet<SmolStr> {
let mut events = IndexSet::new();
for event in self.ast.event_names() {
if event.name == TICK {
self.push(Diagnostic::warning(event.span, TICK_DECLARED));
} else if !events.insert(event.name.clone()) {
self.error(event.span, twice("event", &event.name));
}
}
events
}
pub(super) fn check_asks<'u>(
&mut self,
nodes: &mut [Node],
shared: impl Iterator<Item = &'u ExprUnit>,
) {
let mut continued_at = vec![false; nodes.len()];
let mut jumped_to = vec![false; nodes.len()];
for branch in nodes.iter().flat_map(|node| &node.branches) {
match &branch.outcome {
Outcome::Ask { node: target, .. } => continued_at[target.index()] = true,
Outcome::Jump { node: target, .. } => jumped_to[target.index()] = true,
_ => {}
}
}
for (index, node) in nodes.iter_mut().enumerate() {
node.resumes_ask = continued_at[index];
if !node.resumes_ask {
for read in node.reads().into_iter().filter(reads_answer) {
self.push(
Diagnostic::error(read.span, "`input.result` and `input.failure` only exist in the node an ask continues at")
.with_help(format!("node `{}` isn't the target of any `ask ... ->`", node.name)),
);
}
continue;
}
if node.is_entry {
self.push(
Diagnostic::error(
node.span,
format!(
"node `{}` continues an ask, so it can't be an entry",
node.name
),
)
.with_help("it only runs when the host resumes the ask with an answer"),
);
}
if jumped_to[index] {
self.push(
Diagnostic::error(
node.span,
format!(
"node `{}` continues an ask, so nothing can jump to it",
node.name
),
)
.with_help("a jump has no answer to give it; jump to a node that asks instead"),
);
}
for branch in &node.branches {
if !matches!(branch.outcome, Outcome::Jump { .. } | Outcome::Ask { .. }) {
self.push(
Diagnostic::error(branch.span, format!("node `{}` continues an ask, so every branch must jump or ask again", node.name))
.with_help("the answer is gone on the next run; jump to a node that returns the value"),
);
}
}
}
for read in shared.flat_map(ExprUnit::reads).filter(reads_answer) {
self.error(read.span, "flow-level lets and helpers can't read `input.result` or `input.failure`; read them in the node an ask continues at");
}
}
pub(super) fn check_jump_loops(&mut self, nodes: &[Node]) {
let mut jumps = vec![Vec::new(); nodes.len()];
for (index, node) in nodes.iter().enumerate() {
for branch in &node.branches {
if let Outcome::Jump { node: target, .. } = &branch.outcome {
if !branch.needs_event {
jumps[index].push(Jump {
to: target.index(),
span: branch.span,
});
}
}
}
}
let components = strongly_connected(&jumps);
let mut component_of = vec![0; nodes.len()];
for (number, component) in components.iter().enumerate() {
for &index in component {
component_of[index] = number;
}
}
for (number, mut component) in components.into_iter().enumerate() {
let loops = component.len() > 1
|| jumps[component[0]]
.iter()
.any(|jump| jump.to == component[0]);
if !loops {
continue;
}
component.sort_by(|&a, &b| nodes[a].name.cmp(&nodes[b].name));
let names: Vec<&str> = component
.iter()
.map(|&index| nodes[index].name.as_str())
.collect();
let listed = names_listed(&names);
let first = component[0];
let span = jumps[first]
.iter()
.find(|jump| component_of[jump.to] == number)
.map_or(nodes[first].span, |jump| jump.span);
self.push(
Diagnostic::error(span, format!("these nodes can jump in a loop forever within one run: {listed}"))
.with_help("make one of the jumps depend on an event (`input.event == '...'`), or end the run with a value"),
);
}
}
pub(super) fn check_reachability(&mut self, nodes: &[Node], entries: &[NodeId]) {
let mut seen = vec![false; nodes.len()];
let mut pending: Vec<usize> = entries.iter().map(|entry| entry.index()).collect();
while let Some(index) = pending.pop() {
if std::mem::replace(&mut seen[index], true) {
continue;
}
for branch in &nodes[index].branches {
match &branch.outcome {
Outcome::Jump { node: target, .. } | Outcome::Ask { node: target, .. } => {
pending.push(target.index())
}
_ => {}
}
}
}
for (index, node) in nodes.iter().enumerate() {
if !seen[index] {
self.push(Diagnostic::warning(
node.span,
format!("node `{}` can never be reached", node.name),
));
}
}
}
}
fn reads_answer(read: &InputRead) -> bool {
read.path
.first()
.is_some_and(|first| first == "result" || first == "failure")
}
#[derive(Clone)]
struct Jump {
to: usize,
span: Span,
}
fn strongly_connected(edges: &[Vec<Jump>]) -> Vec<Vec<usize>> {
const UNVISITED: usize = usize::MAX;
struct Walk {
next_index: usize,
index: Vec<usize>,
lowest: Vec<usize>,
on_stack: Vec<bool>,
stack: Vec<usize>,
}
impl Walk {
fn visit(&mut self, node: usize) {
self.index[node] = self.next_index;
self.lowest[node] = self.next_index;
self.next_index += 1;
self.stack.push(node);
self.on_stack[node] = true;
}
}
struct Frame {
node: usize,
edges_followed: usize,
}
let count = edges.len();
let mut walk = Walk {
next_index: 0,
index: vec![UNVISITED; count],
lowest: vec![0; count],
on_stack: vec![false; count],
stack: Vec::new(),
};
let mut components = Vec::new();
let mut frames = Vec::new();
for root in 0..count {
if walk.index[root] != UNVISITED {
continue;
}
walk.visit(root);
frames.push(Frame {
node: root,
edges_followed: 0,
});
while let Some(frame) = frames.last_mut() {
let node = frame.node;
if let Some(jump) = edges[node].get(frame.edges_followed) {
frame.edges_followed += 1;
if walk.index[jump.to] == UNVISITED {
walk.visit(jump.to);
frames.push(Frame {
node: jump.to,
edges_followed: 0,
});
} else if walk.on_stack[jump.to] {
walk.lowest[node] = walk.lowest[node].min(walk.index[jump.to]);
}
continue;
}
frames.pop();
if let Some(parent) = frames.last() {
walk.lowest[parent.node] = walk.lowest[parent.node].min(walk.lowest[node]);
}
if walk.lowest[node] == walk.index[node] {
let mut component = Vec::new();
while let Some(member) = walk.stack.pop() {
walk.on_stack[member] = false;
component.push(member);
if member == node {
break;
}
}
components.push(component);
}
}
}
components
}