Skip to main content

graphrt_core/
validate.rs

1//! Whole-document validation that collects every finding.
2//!
3//! [`Graph::build`] stops at the first problem, which suits programs. People
4//! editing a document want all of them at once, each pointing at the text
5//! that caused it. [`validate_text`] parses a JSON or YAML document, checks
6//! it against the node catalog and returns every [`Diagnostic`] with its
7//! document path (`graph.nodes[1].template`), source position, and a
8//! "did you mean" suggestion where one is close enough. When nothing is
9//! wrong it also returns the compiled graph.
10//!
11//! Checks, in addition to everything [`Graph::build`] enforces:
12//!
13//! - unknown fields, for the document, graph, nodes, edges, policies and node
14//!   configs whose catalog schema is closed (`additionalProperties: false`;
15//!   every built-in kind). Plugin configs with open schemas take any key;
16//! - required config fields from the catalog schema;
17//! - unknown node types, node ids in edges, parents and selectors, and edge
18//!   handles the source node never selects;
19//! - deprecated spellings (warnings).
20//!
21//! Documents in the import layout (a top-level `workflow` or `app` key, or
22//! nodes wrapped in `data`) are checked leniently: unknown fields are not
23//! reported for them.
24
25use std::collections::{HashMap, HashSet};
26use std::fmt;
27use std::sync::Arc;
28
29use serde::Serialize;
30
31use crate::catalog::{Handles, NodeDescriptor};
32use crate::dsl::{ErrorStrategy, NodeDoc};
33use crate::graph::{FAIL_BRANCH, Graph, GraphError, SOURCE_HANDLE};
34use crate::node::{ConfigError, Node, NodeRole, Registry};
35pub use crate::source_map::{DocPath, PathSegment, SourceMap, SourceSpan};
36
37/// How serious a finding is.
38#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
39#[serde(rename_all = "lowercase")]
40pub enum Severity {
41    /// The document is rejected.
42    Error,
43    /// The document runs, but probably not as intended, or uses a deprecated spelling.
44    Warning,
45}
46
47/// One validation finding.
48#[derive(Clone, Debug, PartialEq, Serialize)]
49#[non_exhaustive]
50pub struct Diagnostic {
51    pub severity: Severity,
52    /// Stable machine-readable category, e.g. `unknown-field`, `unknown-node`.
53    pub code: &'static str,
54    pub message: String,
55    /// Where in the document, e.g. `graph.nodes[1].template`.
56    pub path: DocPath,
57    /// Source position (`line`, `column`, `length`), when known.
58    #[serde(flatten)]
59    pub span: Option<SourceSpan>,
60    /// Id of the node the finding is about.
61    #[serde(skip_serializing_if = "Option::is_none")]
62    pub node: Option<String>,
63    /// Likely intended spelling ("did you mean `template`?").
64    #[serde(skip_serializing_if = "Option::is_none")]
65    pub suggestion: Option<String>,
66    /// Extra guidance.
67    #[serde(skip_serializing_if = "Option::is_none")]
68    pub help: Option<String>,
69    /// Point at the key of `path` rather than its value.
70    #[serde(skip)]
71    pub at_key: bool,
72}
73
74impl Diagnostic {
75    pub fn error(code: &'static str, path: DocPath, message: impl Into<String>) -> Self {
76        Self::new(Severity::Error, code, path, message.into())
77    }
78
79    pub fn warning(code: &'static str, path: DocPath, message: impl Into<String>) -> Self {
80        Self::new(Severity::Warning, code, path, message.into())
81    }
82
83    fn new(severity: Severity, code: &'static str, path: DocPath, message: String) -> Self {
84        Self { severity, code, message, path, span: None, node: None, suggestion: None, help: None, at_key: false }
85    }
86
87    /// Point at the key of the path (for unknown or misspelled fields).
88    #[must_use]
89    pub fn at_key(mut self) -> Self {
90        self.at_key = true;
91        self
92    }
93
94    #[must_use]
95    pub fn with_suggestion(mut self, suggestion: Option<String>) -> Self {
96        self.suggestion = suggestion;
97        self
98    }
99
100    #[must_use]
101    pub fn with_help(mut self, help: impl Into<String>) -> Self {
102        self.help = Some(help.into());
103        self
104    }
105
106    #[must_use]
107    pub fn with_node(mut self, id: &str) -> Self {
108        self.node = Some(id.to_owned());
109        self
110    }
111
112    pub fn is_error(&self) -> bool {
113        self.severity == Severity::Error
114    }
115}
116
117impl fmt::Display for Diagnostic {
118    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
119        write!(f, "{}: {}", self.path, self.message)?;
120        if let Some(s) = &self.suggestion {
121            write!(f, " (did you mean `{s}`?)")?;
122        }
123        Ok(())
124    }
125}
126
127/// Result of [`validate_text`].
128#[derive(Debug)]
129pub struct Validation {
130    /// Every finding, in document order.
131    pub diagnostics: Vec<Diagnostic>,
132    /// The compiled graph, when there are no errors.
133    pub graph: Option<Graph>,
134}
135
136impl Validation {
137    pub fn has_errors(&self) -> bool {
138        self.diagnostics.iter().any(Diagnostic::is_error)
139    }
140
141    pub fn errors(&self) -> impl Iterator<Item = &Diagnostic> {
142        self.diagnostics.iter().filter(|d| d.is_error())
143    }
144
145    pub fn warnings(&self) -> impl Iterator<Item = &Diagnostic> {
146        self.diagnostics.iter().filter(|d| !d.is_error())
147    }
148}
149
150/// The closest candidate to `word` by edit distance, if it is close enough to
151/// be a likely typo (at most one edit per three characters, minimum one).
152/// A case-insensitive exact match always wins.
153pub fn suggest<'a, I>(word: &str, candidates: I) -> Option<String>
154where
155    I: IntoIterator<Item = &'a str>,
156{
157    let limit = (word.chars().count().max(3) / 3).max(1);
158    let lower = word.to_lowercase();
159    let mut best: Option<(usize, &str)> = None;
160    for candidate in candidates {
161        if candidate == word {
162            continue;
163        }
164        let distance =
165            if candidate.to_lowercase() == lower { 0 } else { edit_distance(&lower, &candidate.to_lowercase()) };
166        if distance <= limit && best.is_none_or(|(d, _)| distance < d) {
167            best = Some((distance, candidate));
168        }
169    }
170    best.map(|(_, c)| c.to_owned())
171}
172
173/// Optimal string alignment distance (Levenshtein plus adjacent transpositions).
174fn edit_distance(a: &str, b: &str) -> usize {
175    let a: Vec<char> = a.chars().collect();
176    let b: Vec<char> = b.chars().collect();
177    let width = b.len() + 1;
178    let mut table = vec![0usize; (a.len() + 1) * width];
179    let at = |i: usize, j: usize| i * width + j;
180    for i in 0..=a.len() {
181        if let Some(cell) = table.get_mut(at(i, 0)) {
182            *cell = i;
183        }
184    }
185    for j in 0..=b.len() {
186        if let Some(cell) = table.get_mut(at(0, j)) {
187            *cell = j;
188        }
189    }
190    for i in 1..=a.len() {
191        for j in 1..=b.len() {
192            let get = |i: usize, j: usize| table.get(at(i, j)).copied().unwrap_or(usize::MAX - 1);
193            let same = a.get(i - 1) == b.get(j - 1);
194            let mut value = (get(i - 1, j) + 1).min(get(i, j - 1) + 1).min(get(i - 1, j - 1) + usize::from(!same));
195            if i > 1 && j > 1 && a.get(i - 1) == b.get(j - 2) && a.get(i - 2) == b.get(j - 1) {
196                value = value.min(get(i - 2, j - 2) + 1);
197            }
198            if let Some(cell) = table.get_mut(at(i, j)) {
199                *cell = value;
200            }
201        }
202    }
203    table.last().copied().unwrap_or(0)
204}
205
206/// Rendered " (did you mean `x`?)" suffix, or nothing.
207pub(crate) fn did_you_mean(suggestion: &Option<String>) -> String {
208    suggestion.as_ref().map(|s| format!("; did you mean `{s}`?")).unwrap_or_default()
209}
210
211/// Parse, check and compile a JSON or YAML document, collecting every finding.
212pub fn validate_text(text: &str, registry: &Registry) -> Validation {
213    let raw = match parse_raw(text) {
214        Ok(raw) => raw,
215        Err(diagnostic) => return Validation { diagnostics: vec![*diagnostic], graph: None },
216    };
217    let map = SourceMap::from_text(text);
218    let mut validation = validate_value(raw, registry);
219    for d in &mut validation.diagnostics {
220        if d.span.is_none() {
221            d.span = map.locate(&d.path, d.at_key);
222        }
223    }
224    // Document order; findings without a position keep their relative order at the end.
225    validation.diagnostics.sort_by_key(|d| d.span.map_or((u32::MAX, u32::MAX), |s| (s.line, s.column)));
226    validation
227}
228
229/// Check and compile an already-decoded document (no source positions).
230pub fn validate_value(raw: serde_json::Value, registry: &Registry) -> Validation {
231    let decoded = crate::dsl::decode(raw);
232    let mut diagnostics = decoded.diagnostics;
233    let paths = Paths { nodes: decoded.node_paths, edges: decoded.edge_paths };
234    check_graph(&decoded.workflow, &paths, registry, &mut diagnostics);
235    if diagnostics.iter().any(Diagnostic::is_error) {
236        return Validation { diagnostics, graph: None };
237    }
238    let ids: Vec<String> = decoded.workflow.graph.nodes.iter().map(|n| n.id.clone()).collect();
239    match Graph::build(decoded.workflow, registry) {
240        Ok(graph) => {
241            for warning in graph.warnings() {
242                let path = backticked(warning)
243                    .and_then(|id| ids.iter().position(|n| n == id))
244                    .and_then(|ix| paths.nodes.get(ix).cloned())
245                    .unwrap_or_default();
246                diagnostics.push(Diagnostic::warning("graph", path, warning.clone()));
247            }
248            Validation { diagnostics, graph: Some(graph) }
249        }
250        Err(error) => {
251            let path = backticked(&error.to_string())
252                .and_then(|id| ids.iter().position(|n| n == id))
253                .and_then(|ix| paths.nodes.get(ix).cloned())
254                .unwrap_or_else(|| DocPath::root().key("graph"));
255            diagnostics.push(Diagnostic::error("graph", path, error.to_string()));
256            Validation { diagnostics, graph: None }
257        }
258    }
259}
260
261/// The first `` `quoted` `` word of a message.
262fn backticked(message: &str) -> Option<&str> {
263    let start = message.find('`')? + 1;
264    let len = message.get(start..)?.find('`')?;
265    message.get(start..start + len)
266}
267
268/// Parse JSON (text starting with `{`) or YAML into a JSON value.
269fn parse_raw(text: &str) -> Result<serde_json::Value, Box<Diagnostic>> {
270    let syntax = |message: String, line: usize, column: usize| {
271        let mut d = Diagnostic::error("syntax", DocPath::root(), message);
272        if let (Ok(line), Ok(column)) = (u32::try_from(line), u32::try_from(column)) {
273            if line > 0 {
274                d.span = Some(SourceSpan { line, column: column.max(1), len: 1 });
275            }
276        }
277        Box::new(d)
278    };
279    if text.trim_start().starts_with('{') {
280        return serde_json::from_str(text)
281            .map_err(|e| syntax(format!("invalid JSON: {}", strip_position(&e.to_string())), e.line(), e.column()));
282    }
283    #[cfg(feature = "yaml")]
284    {
285        let options = serde_saphyr::options! { strict_booleans: true };
286        serde_saphyr::from_str_with_options(text, options).map_err(|e| {
287            let (line, column) = e
288                .location()
289                .map(|l| (usize::try_from(l.line()).unwrap_or(0), usize::try_from(l.column()).unwrap_or(0)))
290                .unwrap_or((0, 0));
291            let message = e.to_string();
292            let first = message.lines().next().unwrap_or("invalid YAML").trim().to_owned();
293            syntax(format!("invalid YAML: {}", strip_position(&first)), line, column)
294        })
295    }
296    #[cfg(not(feature = "yaml"))]
297    {
298        serde_json::from_str(text).map_err(|e| {
299            syntax(
300                format!("invalid JSON (YAML support is not compiled in): {}", strip_position(&e.to_string())),
301                e.line(),
302                e.column(),
303            )
304        })
305    }
306}
307
308/// Drop a trailing " at line X column Y" that the position already carries.
309fn strip_position(message: &str) -> String {
310    match message.rfind(" at line ") {
311        Some(ix) => message.get(..ix).unwrap_or(message).to_owned(),
312        None => message.to_owned(),
313    }
314}
315
316struct Paths {
317    nodes: Vec<DocPath>,
318    edges: Vec<DocPath>,
319}
320
321impl Paths {
322    fn node(&self, ix: usize) -> DocPath {
323        self.nodes.get(ix).cloned().unwrap_or_default()
324    }
325    fn edge(&self, ix: usize) -> DocPath {
326        self.edges.get(ix).cloned().unwrap_or_default()
327    }
328}
329
330/// Graph-level checks over every decoded node and edge.
331fn check_graph(workflow: &crate::Workflow, paths: &Paths, registry: &Registry, out: &mut Vec<Diagnostic>) {
332    let nodes = &workflow.graph.nodes;
333    let ids: Vec<&str> = nodes.iter().map(|n| n.id.as_str()).collect();
334    let mut index: HashMap<&str, usize> = HashMap::with_capacity(nodes.len());
335    for (ix, node) in nodes.iter().enumerate() {
336        let path = paths.node(ix).key("id");
337        if let Err(GraphError::InvalidNodeId { reason, .. }) = crate::graph::validate_node_id(&node.id) {
338            out.push(
339                Diagnostic::error("invalid-node-id", path.clone(), format!("node id `{}` {reason}", node.id))
340                    .with_node(&node.id),
341            );
342        }
343        if let Some(first) = index.insert(&node.id, ix) {
344            index.insert(&node.id, first);
345            out.push(
346                Diagnostic::error("duplicate-node", path, format!("duplicate node id `{}`", node.id))
347                    .with_node(&node.id)
348                    .with_help(format!("first defined at {}", paths.node(first))),
349            );
350        }
351    }
352
353    let mut built: Vec<Option<Arc<dyn Node>>> = Vec::with_capacity(nodes.len());
354    for (ix, doc) in nodes.iter().enumerate() {
355        built.push(check_node(doc, &paths.node(ix), registry, out));
356    }
357
358    check_parents(nodes, &index, &built, paths, out);
359    check_edges(workflow, &index, &ids, &built, paths, registry, out);
360    check_references(nodes, &index, &ids, &built, paths, out);
361}
362
363/// Type, fields and configuration of one node. Returns the built node.
364fn check_node(doc: &NodeDoc, path: &DocPath, registry: &Registry, out: &mut Vec<Diagnostic>) -> Option<Arc<dyn Node>> {
365    if !registry.contains(&doc.kind) {
366        let mut kinds: Vec<&str> = registry.kinds().collect();
367        kinds.sort_unstable();
368        out.push(
369            Diagnostic::error("unknown-node-type", path.key("type"), format!("unknown node type `{}`", doc.kind))
370                .with_node(&doc.id)
371                .with_suggestion(suggest(&doc.kind, kinds))
372                .with_help("node types come from built-in features and plugins"),
373        );
374        return None;
375    }
376    if doc.strict {
377        if let Some(descriptor) = registry.descriptor_ref(&doc.kind) {
378            out.extend(config_diagnostics(doc, descriptor, path));
379        }
380    }
381    match registry.build(doc) {
382        Ok(node) => Some(node),
383        Err(error) => {
384            out.push(config_error(&error, path));
385            None
386        }
387    }
388}
389
390fn config_error(error: &ConfigError, base: &DocPath) -> Diagnostic {
391    let path = error.field.as_deref().map(|field| join_dotted(base, field)).unwrap_or_else(|| base.clone());
392    Diagnostic::error(
393        "invalid-config",
394        path,
395        format!("invalid `{}` node `{}`: {}", error.kind, error.node_id, error.message),
396    )
397    .with_node(&error.node_id)
398}
399
400/// `base` extended by a serde-style path such as `variables[0].value_selector`.
401fn join_dotted(base: &DocPath, field: &str) -> DocPath {
402    let mut path = base.clone();
403    for part in field.split('.') {
404        let (key, indices) = match part.find('[') {
405            Some(ix) => (part.get(..ix).unwrap_or(part), part.get(ix..).unwrap_or("")),
406            None => (part, ""),
407        };
408        if !key.is_empty() && key != "?" {
409            path = path.key(key);
410        }
411        for index in indices.split(['[', ']']).filter(|s| !s.is_empty()) {
412            if let Ok(ix) = index.parse() {
413                path = path.index(ix);
414            }
415        }
416    }
417    path
418}
419
420/// Unknown, missing and deprecated config fields of a strict node, judged by its catalog schema.
421pub(crate) fn config_diagnostics(doc: &NodeDoc, descriptor: &NodeDescriptor, base: &DocPath) -> Vec<Diagnostic> {
422    let mut issues = Vec::new();
423    let config = serde_json::Value::Object(doc.config.clone());
424    let scope = Scope { kind: &doc.kind, depth: base.segments().len() };
425    walk_schema(&descriptor.config_schema, &config, base, &scope, &mut issues);
426    for issue in &mut issues {
427        issue.node = Some(doc.id.clone());
428    }
429    issues
430}
431
432/// Report unknown keys (closed object schemas only), missing required keys and
433/// deprecated keys. Composition keywords (`oneOf`, `anyOf`, ...) are not followed.
434fn walk_schema(
435    schema: &serde_json::Value,
436    value: &serde_json::Value,
437    path: &DocPath,
438    scope: &Scope<'_>,
439    out: &mut Vec<Diagnostic>,
440) {
441    let Some(schema) = schema.as_object() else { return };
442    match value {
443        serde_json::Value::Object(map) => {
444            let properties = schema.get("properties").and_then(serde_json::Value::as_object);
445            let closed = schema.get("additionalProperties") == Some(&serde_json::Value::Bool(false))
446                && !schema.contains_key("patternProperties");
447            let extra = schema.get("additionalProperties").filter(|s| s.is_object());
448            let known: Vec<&str> = properties
449                .map(|p| {
450                    p.iter()
451                        .filter(|(_, s)| s.get("deprecated") != Some(&serde_json::Value::Bool(true)))
452                        .map(|(k, _)| k.as_str())
453                        .collect()
454                })
455                .unwrap_or_default();
456            let mut suggested = HashSet::new();
457            for (key, child) in map {
458                let child_path = path.key(key);
459                match properties.and_then(|p| p.get(key)) {
460                    Some(sub) => {
461                        if sub.get("deprecated") == Some(&serde_json::Value::Bool(true)) {
462                            let note = sub.get("description").and_then(serde_json::Value::as_str).unwrap_or("");
463                            let replacement = backticked(note).map(str::to_owned);
464                            out.push(
465                                Diagnostic::warning("deprecated", child_path.clone(), format!("`{key}` is deprecated"))
466                                    .at_key()
467                                    .with_suggestion(replacement),
468                            );
469                        }
470                        walk_schema(sub, child, &child_path, scope, out);
471                    }
472                    None => match extra {
473                        Some(sub) => walk_schema(sub, child, &child_path, scope, out),
474                        None if closed => {
475                            let suggestion = suggest(key, known.iter().copied());
476                            if let Some(s) = &suggestion {
477                                suggested.insert(s.clone());
478                            }
479                            let message = format!("unknown field `{key}` {}", scope.describe(path));
480                            let mut d = Diagnostic::error("unknown-field", child_path, message)
481                                .at_key()
482                                .with_suggestion(suggestion);
483                            if d.suggestion.is_none() && !known.is_empty() {
484                                d = d.with_help(format!("expected one of: {}", known.join(", ")));
485                            }
486                            out.push(d);
487                        }
488                        None => {}
489                    },
490                }
491            }
492            for required in schema.get("required").and_then(serde_json::Value::as_array).into_iter().flatten() {
493                let Some(required) = required.as_str() else { continue };
494                if !map.contains_key(required) && !suggested.contains(required) {
495                    out.push(Diagnostic::error(
496                        "missing-field",
497                        path.clone(),
498                        format!("missing required field `{required}` {}", scope.describe(path)),
499                    ));
500                }
501            }
502        }
503        serde_json::Value::Array(items) => {
504            if let Some(sub) = schema.get("items").filter(|s| s.is_object()) {
505                for (ix, item) in items.iter().enumerate() {
506                    walk_schema(sub, item, &path.index(ix), scope, out);
507                }
508            }
509        }
510        _ => {}
511    }
512}
513
514/// Where a config finding is, for messages.
515struct Scope<'a> {
516    kind: &'a str,
517    /// Path length of the node config root.
518    depth: usize,
519}
520
521impl Scope<'_> {
522    fn describe(&self, path: &DocPath) -> String {
523        let inner = path.segments().get(self.depth..).unwrap_or_default();
524        if inner.is_empty() {
525            return format!("for node type `{}`", self.kind);
526        }
527        format!("in `{}` of a `{}` node", join_segments(&DocPath::root(), inner), self.kind)
528    }
529}
530
531fn check_parents(
532    nodes: &[NodeDoc],
533    index: &HashMap<&str, usize>,
534    built: &[Option<Arc<dyn Node>>],
535    paths: &Paths,
536    out: &mut Vec<Diagnostic>,
537) {
538    let containers: Vec<&str> = nodes
539        .iter()
540        .zip(built)
541        .filter(|(_, n)| n.as_ref().is_some_and(|n| n.role() == NodeRole::Container))
542        .map(|(d, _)| d.id.as_str())
543        .collect();
544    for (ix, doc) in nodes.iter().enumerate() {
545        let Some(parent) = &doc.parent else { continue };
546        let path = paths.node(ix).key("parent");
547        match index.get(parent.as_str()) {
548            None => out.push(
549                Diagnostic::error(
550                    "unknown-node",
551                    path,
552                    format!("parent `{parent}` of node `{}` is not a node id", doc.id),
553                )
554                .with_node(&doc.id)
555                .with_suggestion(suggest(parent, containers.iter().copied())),
556            ),
557            Some(&p) => {
558                let role = built.get(p).and_then(|n| n.as_ref()).map(|n| n.role());
559                if role.is_some_and(|r| r != NodeRole::Container) {
560                    out.push(
561                        Diagnostic::error(
562                            "invalid-parent",
563                            path,
564                            format!("parent `{parent}` of node `{}` is not a container (iteration or loop)", doc.id),
565                        )
566                        .with_node(&doc.id),
567                    );
568                }
569            }
570        }
571    }
572}
573
574fn check_edges(
575    workflow: &crate::Workflow,
576    index: &HashMap<&str, usize>,
577    ids: &[&str],
578    built: &[Option<Arc<dyn Node>>],
579    paths: &Paths,
580    registry: &Registry,
581    out: &mut Vec<Diagnostic>,
582) {
583    let nodes = &workflow.graph.nodes;
584    let mut edge_ids = HashSet::new();
585    for (k, edge) in workflow.graph.edges.iter().enumerate() {
586        let path = paths.edge(k);
587        if let Some(id) = &edge.id {
588            if !edge_ids.insert(id.as_str()) {
589                out.push(Diagnostic::error("duplicate-edge", path.key("id"), format!("duplicate edge id `{id}`")));
590            }
591        }
592        let mut lookup = |end: &str, id: &str| match index.get(id) {
593            Some(&ix) => Some(ix),
594            None => {
595                out.push(
596                    Diagnostic::error("unknown-node", path.key(end), format!("edge {end} `{id}` is not a node id"))
597                        .with_suggestion(suggest(id, ids.iter().copied())),
598                );
599                None
600            }
601        };
602        let (Some(source), Some(target)) = (lookup("source", &edge.source), lookup("target", &edge.target)) else {
603            continue;
604        };
605        let (Some(source_doc), Some(target_doc)) = (nodes.get(source), nodes.get(target)) else { continue };
606        if source_doc.parent != target_doc.parent {
607            let scope = |p: &Option<String>| p.as_deref().map_or("the root graph".to_owned(), |p| format!("`{p}`"));
608            out.push(Diagnostic::error(
609                "cross-scope-edge",
610                path.clone(),
611                format!(
612                    "edge `{}` -> `{}` crosses scopes: `{}` is in {} but `{}` is in {}",
613                    edge.source,
614                    edge.target,
615                    edge.source,
616                    scope(&source_doc.parent),
617                    edge.target,
618                    scope(&target_doc.parent)
619                ),
620            ));
621        }
622        let Some(node) = built.get(source).and_then(|n| n.as_ref()) else { continue };
623        let Some(allowed) = allowed_handles(node.as_ref(), registry.descriptor_ref(&source_doc.kind)) else {
624            continue;
625        };
626        let handle = edge.handle.as_deref().filter(|h| !h.is_empty()).unwrap_or(SOURCE_HANDLE);
627        if let Some(message) = dead_fail_branch(source_doc, handle) {
628            out.push(Diagnostic::warning("dead-edge", path.key("handle"), message).with_node(&source_doc.id));
629        }
630        if !allowed.iter().any(|h| h == handle) {
631            let at = if edge.handle.is_some() { path.key("handle") } else { path.clone() };
632            out.push(
633                Diagnostic::error("unknown-handle", at, handle_message(source_doc, handle, &allowed))
634                    .with_node(&source_doc.id)
635                    .with_suggestion(suggest(handle, allowed.iter().map(String::as_str))),
636            );
637        }
638    }
639}
640
641pub(crate) fn handle_message(source: &NodeDoc, handle: &str, allowed: &[String]) -> String {
642    format!(
643        "node `{}` ({}) has no handle `{handle}`; its handles are: {}",
644        source.id,
645        source.kind,
646        allowed.iter().map(|h| format!("`{h}`")).collect::<Vec<_>>().join(", ")
647    )
648}
649
650/// The handles a node can select, or `None` when they cannot be known statically.
651pub(crate) fn allowed_handles(node: &dyn Node, descriptor: Option<&NodeDescriptor>) -> Option<Vec<String>> {
652    let mut handles = match node.branch_handles() {
653        Some(handles) => handles,
654        None => match descriptor.map(|d| &d.handles) {
655            Some(Handles::Fixed { handles }) => handles.clone(),
656            Some(Handles::Dynamic { .. }) => return None,
657            _ if node.role() == NodeRole::Branch => return None,
658            _ => vec![SOURCE_HANDLE.to_owned()],
659        },
660    };
661    // Always allowed: without `on_error: {strategy: fail-branch}` such an edge is
662    // never taken, which is reported as a warning (see `dead_fail_branch`).
663    handles.push(FAIL_BRANCH.to_owned());
664    Some(handles)
665}
666
667/// Warning text for a `fail-branch` edge whose source does not use that strategy.
668pub(crate) fn dead_fail_branch(source: &NodeDoc, handle: &str) -> Option<String> {
669    (handle == FAIL_BRANCH && source.policy.on_error != ErrorStrategy::FailBranch).then(|| {
670        format!(
671            "edge from `{}` uses handle `fail-branch`, but the node does not set \
672             `on_error: {{strategy: fail-branch}}`; the edge is never taken",
673            source.id
674        )
675    })
676}
677
678fn check_references(
679    nodes: &[NodeDoc],
680    index: &HashMap<&str, usize>,
681    ids: &[&str],
682    built: &[Option<Arc<dyn Node>>],
683    paths: &Paths,
684    out: &mut Vec<Diagnostic>,
685) {
686    let mut candidates: Vec<&str> = ids.to_vec();
687    candidates.extend_from_slice(crate::graph::RESERVED_NAMESPACES);
688    for (ix, (doc, node)) in nodes.iter().zip(built).enumerate() {
689        let Some(node) = node else { continue };
690        let mut seen = HashSet::new();
691        for selector in node.inputs() {
692            let namespace = selector.namespace();
693            if crate::graph::RESERVED_NAMESPACES.contains(&namespace) || index.contains_key(namespace) {
694                continue;
695            }
696            if !seen.insert(selector.to_string()) {
697                continue;
698            }
699            let path = locate_reference(&doc.config, namespace)
700                .map(|rel| join_segments(&paths.node(ix), &rel))
701                .unwrap_or_else(|| paths.node(ix));
702            out.push(
703                Diagnostic::error(
704                    "unknown-reference",
705                    path,
706                    format!("node `{}` references `{selector}`, but there is no node `{namespace}`", doc.id),
707                )
708                .with_node(&doc.id)
709                .with_suggestion(suggest(namespace, candidates.iter().copied()))
710                .with_help("selectors start with a node id or `sys`, `env`, `conversation`"),
711            );
712        }
713    }
714}
715
716fn join_segments(base: &DocPath, rel: &[PathSegment]) -> DocPath {
717    rel.iter().fold(base.clone(), |path, segment| match segment {
718        PathSegment::Key(k) => path.key(k),
719        PathSegment::Index(i) => path.index(*i),
720    })
721}
722
723/// Find where in a config a selector with `namespace` appears: an array whose
724/// first item is the namespace, a dotted string `namespace.x`, or a template
725/// placeholder `{{#namespace.x#}}`.
726fn locate_reference(config: &serde_json::Map<String, serde_json::Value>, namespace: &str) -> Option<Vec<PathSegment>> {
727    fn search(value: &serde_json::Value, namespace: &str, path: &mut Vec<PathSegment>) -> bool {
728        match value {
729            serde_json::Value::String(s) => {
730                s.contains(&format!("{{{{#{namespace}.")) || s.starts_with(&format!("{namespace}."))
731            }
732            serde_json::Value::Array(items) => {
733                let is_selector = items.first().and_then(serde_json::Value::as_str) == Some(namespace)
734                    && items.iter().all(serde_json::Value::is_string)
735                    && items.len() >= 2;
736                if is_selector {
737                    // Point at the namespace part, the one that is wrong.
738                    path.push(PathSegment::Index(0));
739                    return true;
740                }
741                for (ix, item) in items.iter().enumerate() {
742                    path.push(PathSegment::Index(ix));
743                    if search(item, namespace, path) {
744                        return true;
745                    }
746                    path.pop();
747                }
748                false
749            }
750            serde_json::Value::Object(map) => {
751                for (key, item) in map {
752                    path.push(PathSegment::Key(key.clone()));
753                    if search(item, namespace, path) {
754                        return true;
755                    }
756                    path.pop();
757                }
758                false
759            }
760            _ => false,
761        }
762    }
763    let mut path = Vec::new();
764    search(&serde_json::Value::Object(config.clone()), namespace, &mut path).then_some(path)
765}
766
767#[cfg(test)]
768mod tests {
769    use super::*;
770
771    #[test]
772    fn suggestions() {
773        assert_eq!(suggest("templat", ["template", "variables"]), Some("template".into()));
774        assert_eq!(suggest("varaibles", ["template", "variables"]), Some("variables".into()));
775        assert_eq!(suggest("Template", ["template"]), Some("template".into()));
776        assert_eq!(suggest("zzz", ["template", "variables"]), None);
777        assert_eq!(suggest("a", ["b"]), Some("b".into()));
778        assert_eq!(suggest("x", ["x"]), None, "an exact match is not a suggestion");
779        assert_eq!(edit_distance("abc", "acb"), 1);
780        assert_eq!(edit_distance("", "abc"), 3);
781    }
782
783    #[test]
784    fn dotted_paths_join() {
785        let base = DocPath::root().key("graph").key("nodes").index(2);
786        assert_eq!(
787            join_dotted(&base, "variables[0].value_selector").to_string(),
788            "graph.nodes[2].variables[0].value_selector"
789        );
790        assert_eq!(join_dotted(&base, "a[1][2]").to_string(), "graph.nodes[2].a[1][2]");
791    }
792
793    #[test]
794    fn finds_references() {
795        let config = serde_json::json!({"variables": [{"variable": "x", "value_selector": ["strat", "x"]}], "t": "{{#llm.text#}}"});
796        let config = config.as_object().cloned().unwrap_or_default();
797        let path = locate_reference(&config, "strat").unwrap_or_default();
798        assert_eq!(join_segments(&DocPath::root(), &path).to_string(), "variables[0].value_selector[0]");
799        let path = locate_reference(&config, "llm").unwrap_or_default();
800        assert_eq!(join_segments(&DocPath::root(), &path).to_string(), "t");
801    }
802}