Skip to main content

instruction_md/
workflow.rs

1//! The checks a `:::workflow{dialect="instruction/workflow"}` body is held to (§9.1, the specification's
2//! reference/workflows.md): its steps against the specification's workflow registry (`workflow-registry.json`,
3//! vendored unchanged as `src/workflow-registry.json`) and its graph. A host must refuse each of these before
4//! activation, so each is an error: `invalid-workflow` (§18: dialect schema, dependency graph or routing invalid),
5//! `limit-exceeded` for the registry's published limits, `extension-unavailable` for a namespaced node whose alias the
6//! document doesn't declare.
7//!
8//! - the definition: a name, a nonempty mapping of steps, no unknown field (`x-*` is extension data), a key when
9//!   concurrency is key-scoped;
10//! - each step: a valid name, a kind the registry has (or a declared `alias:node`), the kind's required fields, no
11//!   field that is neither the kind's nor a common one, `depends_on` naming siblings, `retry.max` within the limit,
12//!   `on_error` as fail, continue or `goto:<step>`, a scoping kind's body of `{steps}` or branches of them, a schedule
13//!   with one of cron/every/at, a correlate with a window;
14//! - each scope: no more steps than the limit, no deeper than the body limit, no dependency cycle, routes (switch cases
15//!   and default, `goto:`, `on_timeout`) to a sibling that isn't a trigger; triggers and finish only at the top, a
16//!   trigger depending on nothing;
17//! - the top level: a step that depends on nothing starts the run, so it is a trigger; there is a trigger and a
18//!   finish; every step is reached from a trigger.
19//!
20//! The same checks, codes and messages as the TypeScript reference's (`packages/spec/src/workflow.ts`), which models
21//! the specification's own checker (its `tools/workflow_support.py`). What a host decides — which events it emits,
22//! its node providers, expressions, credentials — is not checked: the specification lists no host events, so an
23//! `event` trigger's `on` is any value. [`crate::check_reading`] (and [`crate::check()`], [`crate::deliver`]) runs these
24//! checks on every such body ([`crate::workflows_diagnostics`]); [`workflow_diagnostics`] checks a definition on its
25//! own. Diagnostics come sorted by line, code and message.
26
27use std::collections::{BTreeMap, HashMap, HashSet};
28use std::sync::LazyLock;
29
30use serde::Deserialize;
31use serde_json::Value;
32
33use crate::js::{js_number, js_space, js_trim, truthy, utf16_cmp};
34use crate::types::{Diagnostic, Object, Severity};
35
36/// The native workflow dialect a `:::workflow` names to be checked here.
37pub const WORKFLOW_DIALECT: &str = "instruction/workflow";
38
39/// The workflow registry as vendored: the specification's `workflow-registry.json`.
40pub const WORKFLOW_REGISTRY_JSON: &str = include_str!("workflow-registry.json");
41
42/// A workflow step kind's registry entry.
43#[derive(Clone, Debug, Default, Deserialize)]
44pub struct WorkflowKind {
45    /// The kind's own fields (the common fields are the registry's `common_fields`).
46    #[serde(default)]
47    pub fields: Vec<String>,
48    #[serde(default)]
49    pub required: Vec<String>,
50    /// A trigger: it can start a run.
51    #[serde(default)]
52    pub start: bool,
53    #[serde(default)]
54    pub summary: String,
55}
56
57/// The registry's published limits.
58#[derive(Clone, Copy, Debug, Default, Deserialize)]
59pub struct WorkflowLimits {
60    /// Steps in one scope.
61    pub steps: usize,
62    /// Nested body levels.
63    pub body_depth: usize,
64    /// `retry.max`.
65    pub retry_max: f64,
66}
67
68/// The workflow registry, typed.
69#[derive(Clone, Debug, Default, Deserialize)]
70pub struct WorkflowRegistry {
71    /// instruction-workflow-registry/1
72    pub format: String,
73    /// instruction/workflow
74    pub dialect: String,
75    pub revision: String,
76    pub kinds: BTreeMap<String, WorkflowKind>,
77    /// The fields every step takes.
78    pub common_fields: Vec<String>,
79    pub limits: WorkflowLimits,
80}
81
82static REGISTRY: LazyLock<WorkflowRegistry> = LazyLock::new(|| serde_json::from_str(WORKFLOW_REGISTRY_JSON).unwrap_or_default());
83
84/// The workflow registry.
85pub fn workflow_registry() -> &'static WorkflowRegistry {
86    &REGISTRY
87}
88
89/// The definition's fields (reference/workflows.md, Definition fields), and `$schema`, which its schema allows.
90const DEFINITION_FIELDS: &[&str] = &[
91    "name",
92    "steps",
93    "description",
94    "armed",
95    "inputs",
96    "outputs",
97    "concurrency",
98    "key",
99    "limits",
100    "priority",
101    "durable",
102    "state",
103    "unload",
104    "tool",
105    "act_for",
106    "$schema",
107];
108const P: &str = ":::workflow";
109
110/// The kinds whose field holds a nested scope of steps, and that field (reference/workflows.md, Graphs, scopes and
111/// validation: `foreach`, `batch`, `iterate` and `subgraph` contain `body: {steps: …}`; `parallel` and `race` contain
112/// named `branches`, each with its own `steps`). The registry lists each kind's fields but not which hold steps, so
113/// this is the specification's text; a field of the same name on another kind (an `http` request's `body`) is that
114/// kind's data, never a scope.
115pub const WORKFLOW_SCOPES: &[(&str, &str)] =
116    &[("batch", "body"), ("foreach", "body"), ("iterate", "body"), ("parallel", "branches"), ("race", "branches"), ("subgraph", "body")];
117
118/// The field of `kind` that holds a nested scope of steps, if it is a scoping kind.
119pub fn workflow_scope(kind: &str) -> Option<&'static str> {
120    WORKFLOW_SCOPES.iter().find(|(k, _)| *k == kind).map(|(_, f)| *f)
121}
122
123/// `^[A-Za-z_][A-Za-z0-9_-]{0,63}$`
124fn is_name(s: &str) -> bool {
125    let b = s.as_bytes();
126    !b.is_empty()
127        && b.len() <= 64
128        && (b[0].is_ascii_alphabetic() || b[0] == b'_')
129        && b[1..].iter().all(|c| c.is_ascii_alphanumeric() || *c == b'_' || *c == b'-')
130}
131
132/// `^x-[a-z0-9_.-]+$`
133fn is_extension_field(s: &str) -> bool {
134    s.strip_prefix("x-")
135        .is_some_and(|r| !r.is_empty() && r.bytes().all(|c| c.is_ascii_lowercase() || c.is_ascii_digit() || b"_.-".contains(&c)))
136}
137
138/// `^[a-z][a-z0-9-]*:[a-z][a-z0-9-]*$`
139fn is_custom_kind(s: &str) -> bool {
140    let part = |p: &str| {
141        let b = p.as_bytes();
142        !b.is_empty() && b[0].is_ascii_lowercase() && b.iter().all(|c| c.is_ascii_lowercase() || c.is_ascii_digit() || *c == b'-')
143    };
144    s.split_once(':').is_some_and(|(a, k)| part(a) && part(k))
145}
146
147/// `^(?:fail|continue|goto:[A-Za-z_][A-Za-z0-9_-]{0,63})$`
148fn is_on_error(s: &str) -> bool {
149    s == "fail" || s == "continue" || s.strip_prefix("goto:").is_some_and(is_name)
150}
151
152/// `Number.isInteger`.
153fn integer(v: &Value) -> Option<f64> {
154    v.as_f64().filter(|f| f.is_finite() && f.fract() == 0.0)
155}
156
157fn quote(s: &str) -> String {
158    format!("\"{s}\"")
159}
160
161/// A mapping's keys, sorted as ECMAScript sorts strings.
162fn keys(o: &Object) -> Vec<&str> {
163    let mut k: Vec<&str> = o.keys().map(String::as_str).collect();
164    k.sort_by(|a, b| utf16_cmp(a, b));
165    k
166}
167
168fn join<'a>(a: &[&'a str], b: &[&'a str]) -> Vec<&'a str> {
169    a.iter().chain(b).copied().collect()
170}
171
172fn steps_of(v: Option<&Value>) -> Option<&Object> {
173    v.and_then(|b| b.get("steps")).and_then(Value::as_object)
174}
175
176/// A body: `{steps: {…}}` and nothing else.
177fn is_body(v: Option<&Value>) -> bool {
178    v.and_then(Value::as_object).is_some_and(|o| o.len() == 1 && o.get("steps").is_some_and(Value::is_object))
179}
180
181/// A workflow definition's diagnostics, without lines: what [`crate::check_reading`] reports for an
182/// `instruction/workflow` body (it places each on the line of the key it is about). `extensions` is the document's front matter
183/// `extensions`, which a namespaced `alias:node` kind needs its alias in.
184pub fn workflow_diagnostics(definition: &Value, extensions: Option<&Object>) -> Vec<Diagnostic> {
185    check(definition, &[], 0, extensions)
186}
187
188/// The checks, each diagnostic on the line of the deepest key of its path found in the body's lines (else `at`).
189pub(crate) fn check(definition: &Value, lines: &[(u32, &str)], at: u32, extensions: Option<&Object>) -> Vec<Diagnostic> {
190    let mut c = Checker { out: Vec::new(), lines, at, extensions, reg: workflow_registry() };
191    let Some(def) = definition.as_object() else { return c.out }; // (the reader reports a body that isn't a mapping)
192    if !def.get("name").and_then(Value::as_str).is_some_and(is_name) {
193        c.diag(
194            "invalid-workflow",
195            format!("{P}: its name is required: 1 to 64 letters, digits, \"_\" and \"-\", starting with a letter or \"_\""),
196            &["name"],
197        );
198    }
199    for k in keys(def) {
200        if !DEFINITION_FIELDS.contains(&k) && !is_extension_field(k) {
201            c.diag("invalid-workflow", format!("{P}: \"{k}\" is not a field of a workflow definition"), &[k]);
202        }
203    }
204    if let Some(concurrency) = def.get("concurrency").and_then(Value::as_object)
205        && concurrency.get("scope").and_then(Value::as_str) == Some("key")
206        && !def.contains_key("key")
207    {
208        c.diag("invalid-workflow", format!("{P}: key-scoped concurrency needs the workflow's key"), &["concurrency"]);
209    }
210    match def.get("steps").and_then(Value::as_object) {
211        Some(steps) if !steps.is_empty() => c.scope(steps, &[], &["steps"], 0),
212        _ => c.diag("invalid-workflow", format!("{P}: its steps are a nonempty mapping of step names to steps"), &["steps"]),
213    }
214    let line = |d: &Diagnostic| d.range.map_or(0, |r| r.start);
215    c.out.sort_by(|a, b| line(a).cmp(&line(b)).then_with(|| a.code.cmp(b.code)).then_with(|| utf16_cmp(&a.message, &b.message)));
216    c.out
217}
218
219struct Checker<'a> {
220    out: Vec<Diagnostic>,
221    lines: &'a [(u32, &'a str)],
222    at: u32,
223    extensions: Option<&'a Object>,
224    reg: &'static WorkflowRegistry,
225}
226
227impl Checker<'_> {
228    fn diag(&mut self, code: &'static str, message: String, path: &[&str]) {
229        let line = if self.lines.is_empty() { 0 } else { locate(self.lines, path).unwrap_or(self.at) };
230        self.out.push(Diagnostic::new(code, Severity::Error, message, line));
231    }
232
233    fn kind(&self, k: &str) -> Option<&'static WorkflowKind> {
234        self.reg.kinds.get(k)
235    }
236
237    /// One scope's steps: the top level (depth 0), or a body's or a branch's.
238    fn scope<'a>(&mut self, steps: &'a Object, prefix: &[&'a str], at: &[&'a str], depth: usize) {
239        let names = keys(steps);
240        let limits = self.reg.limits;
241        if names.len() > limits.steps {
242            self.diag("limit-exceeded", format!("{P}: {} steps in one scope; the limit is {}", names.len(), limits.steps), at);
243        }
244        let path = |id: &'a str| join(at, &[id]);
245        let label = |id: &str| quote(&prefix.iter().copied().chain([id]).collect::<Vec<_>>().join("."));
246        let kind_of =
247            |id: &str| -> Option<&str> { steps.get(id).and_then(Value::as_object).and_then(|s| s.get("kind")).and_then(Value::as_str) };
248        let reg = self.reg;
249        let is_trigger = |id: &str| kind_of(id).and_then(|k| reg.kinds.get(k)).is_some_and(|k| k.start);
250        let deps_of = |id: &str| -> Vec<&str> {
251            match steps.get(id).and_then(Value::as_object).and_then(|s| s.get("depends_on")) {
252                Some(Value::Array(d)) => d.iter().filter_map(Value::as_str).collect(),
253                _ => Vec::new(),
254            }
255        };
256        let mut routes: HashMap<&str, Vec<&str>> = HashMap::new();
257        let mut missing_dep: Vec<&str> = Vec::new();
258        for &id in &names {
259            let where_ = label(id);
260            let here = path(id);
261            let with = |k: &'a str| join(&here, &[k]);
262            if !is_name(id) {
263                self.diag(
264                    "invalid-workflow",
265                    format!(
266                        "{P}: {where_} is not a valid step name: 1 to 64 letters, digits, \"_\" and \"-\", starting with a letter or \"_\""
267                    ),
268                    &here,
269                );
270            }
271            let Some(s) = steps.get(id).and_then(Value::as_object) else {
272                self.diag("invalid-workflow", format!("{P}: step {where_} is a mapping with a kind"), &here);
273                continue;
274            };
275            let Some(kind) = s.get("kind").and_then(Value::as_str) else {
276                self.diag("invalid-workflow", format!("{P}: step {where_} has no kind"), &here);
277                continue;
278            };
279            let spec = self.kind(kind);
280            match spec {
281                None => {
282                    if is_custom_kind(kind) {
283                        let alias = kind.split(':').next().unwrap_or("");
284                        if !truthy(self.extensions.and_then(|e| e.get(alias))) {
285                            self.diag(
286                                "extension-unavailable",
287                                format!(
288                                    "{P}: step {where_}: the extension alias \"{alias}\" is not declared in the front matter's extensions"
289                                ),
290                                &with("kind"),
291                            );
292                        }
293                    } else {
294                        self.diag("invalid-workflow", format!("{P}: step {where_}: \"{kind}\" is not a workflow step kind"), &with("kind"));
295                    }
296                }
297                Some(spec) => {
298                    for f in &spec.required {
299                        if !s.contains_key(f) {
300                            self.diag("invalid-workflow", format!("{P}: step {where_} ({kind}) needs {f}"), &here);
301                        }
302                    }
303                    for f in keys(s) {
304                        if !spec.fields.iter().any(|x| x == f) && !self.reg.common_fields.iter().any(|x| x == f) && !is_extension_field(f) {
305                            self.diag(
306                                "invalid-workflow",
307                                format!("{P}: step {where_} ({kind}): \"{f}\" is not a field of {kind} or a common step field"),
308                                &with(f),
309                            );
310                        }
311                    }
312                    if spec.start && depth > 0 {
313                        self.diag(
314                            "invalid-workflow",
315                            format!("{P}: step {where_} ({kind}) is a trigger, which only the top-level steps can hold"),
316                            &here,
317                        );
318                    }
319                    if spec.start && !deps_of(id).is_empty() {
320                        self.diag(
321                            "invalid-workflow",
322                            format!("{P}: step {where_} ({kind}) is a trigger, which depends on nothing"),
323                            &with("depends_on"),
324                        );
325                    }
326                    if kind == "finish" && depth > 0 {
327                        self.diag(
328                            "invalid-workflow",
329                            format!("{P}: step {where_} is a finish, which only the top-level steps can hold"),
330                            &here,
331                        );
332                    }
333                    if kind == "schedule" && ["cron", "every", "at"].iter().filter(|f| s.contains_key(**f)).count() != 1 {
334                        self.diag(
335                            "invalid-workflow",
336                            format!("{P}: step {where_} (schedule) sets exactly one of cron, every and at"),
337                            &here,
338                        );
339                    }
340                    if kind == "correlate" && !s.contains_key("window") {
341                        self.diag("invalid-workflow", format!("{P}: step {where_} (correlate) needs a window"), &here);
342                    }
343                }
344            }
345            if let Some(d) = s.get("depends_on") {
346                let distinct = |list: &[Value]| {
347                    let mut seen = HashSet::new();
348                    list.iter().all(|x| x.as_str().is_some_and(|x| seen.insert(x)))
349                };
350                if !d.as_array().is_some_and(|list| distinct(list)) {
351                    self.diag(
352                        "invalid-workflow",
353                        format!("{P}: step {where_}: depends_on is a list of distinct step names"),
354                        &with("depends_on"),
355                    );
356                }
357                for dep in deps_of(id) {
358                    if !steps.contains_key(dep) {
359                        if !missing_dep.contains(&id) {
360                            missing_dep.push(id);
361                        }
362                        self.diag(
363                            "invalid-workflow",
364                            format!("{P}: step {where_} depends on \"{dep}\", which is not a step in its scope"),
365                            &with("depends_on"),
366                        );
367                    }
368                }
369            }
370            if let Some(max) = s.get("retry").and_then(Value::as_object).and_then(|r| r.get("max")) {
371                match integer(max) {
372                    Some(n) if n > limits.retry_max => self.diag(
373                        "limit-exceeded",
374                        format!("{P}: step {where_} retries {} times; the limit is {}", js_number(n), js_number(limits.retry_max)),
375                        &with("retry"),
376                    ),
377                    Some(n) if n >= 0.0 => {}
378                    _ => self.diag(
379                        "invalid-workflow",
380                        format!("{P}: step {where_}: retry.max is a whole number of retries, at most {}", js_number(limits.retry_max)),
381                        &with("retry"),
382                    ),
383                }
384            }
385            let mut targets: Vec<&str> = Vec::new();
386            if let Some(on_error) = s.get("on_error") {
387                match on_error.as_str() {
388                    Some(e) if is_on_error(e) => {
389                        if let Some(t) = e.strip_prefix("goto:") {
390                            targets.push(t);
391                        }
392                    }
393                    _ => self.diag(
394                        "invalid-workflow",
395                        format!("{P}: step {where_}: on_error is fail, continue or goto:<step>"),
396                        &with("on_error"),
397                    ),
398                }
399            }
400            if kind == "switch" {
401                if let Some(cases) = s.get("cases").and_then(Value::as_object) {
402                    for case in keys(cases) {
403                        match cases.get(case) {
404                            Some(Value::String(t)) => targets.push(t),
405                            _ => self.diag(
406                                "invalid-workflow",
407                                format!("{P}: step {where_} (switch): case \"{case}\" names one step, as a string"),
408                                &with("cases"),
409                            ),
410                        }
411                    }
412                }
413                if let Some(Value::String(t)) = s.get("default") {
414                    targets.push(t);
415                }
416            }
417            if let Some(Value::String(t)) = s.get("on_timeout") {
418                targets.push(t);
419            }
420            for &t in &targets {
421                if !steps.contains_key(t) {
422                    self.diag("invalid-workflow", format!("{P}: step {where_} routes to \"{t}\", which is not a step in its scope"), &here);
423                } else if is_trigger(t) {
424                    self.diag(
425                        "invalid-workflow",
426                        format!("{P}: step {where_} routes to \"{t}\", a trigger: a route can't start a run"),
427                        &here,
428                    );
429                }
430            }
431            routes.insert(id, targets.into_iter().filter(|t| steps.contains_key(*t)).collect());
432            // the nested scopes: (prefix, path, steps)
433            let mut nested: Vec<(Vec<&'a str>, Vec<&'a str>, &'a Object)> = Vec::new();
434            let takes = |f: &str| spec.is_some() && workflow_scope(kind) == Some(f);
435            let inner = steps_of;
436            if takes("body") && s.contains_key("body") {
437                match inner(s.get("body")).filter(|_| is_body(s.get("body"))) {
438                    Some(st) => nested.push((prefix.iter().copied().chain([id]).collect(), [with("body"), vec!["steps"]].concat(), st)),
439                    None => self.diag(
440                        "invalid-workflow",
441                        format!("{P}: step {where_}: its body is {{steps: …}}, a mapping of steps"),
442                        &with("body"),
443                    ),
444                }
445            }
446            if takes("branches") && s.contains_key("branches") {
447                match s.get("branches").and_then(Value::as_object) {
448                    Some(b) if !b.is_empty() && b.values().all(|v| is_body(Some(v))) => {
449                        for n in keys(b) {
450                            if let Some(st) = inner(b.get(n)) {
451                                nested.push((
452                                    prefix.iter().copied().chain([id, n]).collect(),
453                                    [with("branches"), vec![n, "steps"]].concat(),
454                                    st,
455                                ));
456                            }
457                        }
458                    }
459                    _ => self.diag(
460                        "invalid-workflow",
461                        format!("{P}: step {where_}: its branches are a mapping of names to {{steps: …}}"),
462                        &with("branches"),
463                    ),
464                }
465            }
466            for (p, a, st) in nested {
467                if depth + 1 > limits.body_depth {
468                    self.diag("limit-exceeded", format!("{P}: step {where_} nests bodies deeper than {} levels", limits.body_depth), &here);
469                    break;
470                }
471                self.scope(st, &p, &a, depth + 1);
472            }
473        }
474
475        // dependency cycles, each found once: a depth-first walk in name order, dependencies in their written order
476        // (iterative: a scope may hold any number of steps)
477        let mut cyclic: Vec<&str> = Vec::new();
478        let mut state: HashMap<&str, bool> = HashMap::new(); // false: visiting, true: done
479        for &root in &names {
480            if state.contains_key(root) {
481                continue;
482            }
483            let mut stack: Vec<(&str, Vec<&str>, usize)> = vec![(root, deps_of(root), 0)];
484            state.insert(root, false);
485            while let Some(top) = stack.last_mut() {
486                let Some(&dep) = top.1.get(top.2) else {
487                    let (id, _, _) = stack.pop().unwrap_or((root, Vec::new(), 0));
488                    state.insert(id, true);
489                    continue;
490                };
491                top.2 += 1;
492                if !steps.contains_key(dep) {
493                    continue;
494                }
495                match state.get(dep) {
496                    Some(false) => {
497                        let from = stack.iter().position(|f| f.0 == dep).unwrap_or(0);
498                        let cycle: Vec<&str> = stack[from..].iter().map(|f| f.0).collect();
499                        for &c in &cycle {
500                            if !cyclic.contains(&c) {
501                                cyclic.push(c);
502                            }
503                        }
504                        let shown: Vec<String> = cycle.iter().copied().chain([dep]).map(label).collect();
505                        self.diag(
506                            "invalid-workflow",
507                            format!("{P}: the steps {} depend on each other in a cycle", shown.join(" → ")),
508                            &path(dep),
509                        );
510                    }
511                    Some(true) => {}
512                    None => {
513                        state.insert(dep, false);
514                        stack.push((dep, deps_of(dep), 0));
515                    }
516                }
517            }
518        }
519
520        if depth > 0 {
521            return;
522        }
523        let routed: HashSet<&str> = routes.values().flatten().copied().collect();
524        let triggers: Vec<&str> = names.iter().copied().filter(|id| is_trigger(id)).collect();
525        // a namespaced node's role (trigger or step) is its extension's to say, and an unknown kind is already reported
526        let unknown: Vec<&str> =
527            names.iter().copied().filter(|id| kind_of(id).is_some_and(|k| !reg.kinds.contains_key(k)) && deps_of(id).is_empty()).collect();
528        let roots: Vec<&str> = names
529            .iter()
530            .copied()
531            .filter(|id| {
532                kind_of(id).and_then(|k| reg.kinds.get(k)).is_some_and(|k| !k.start) && deps_of(id).is_empty() && !routed.contains(id)
533            })
534            .collect();
535        let mut all_triggers: Vec<&str> = reg.kinds.iter().filter(|(_, k)| k.start).map(|(n, _)| n.as_str()).collect();
536        all_triggers.sort_by(|a, b| utf16_cmp(a, b));
537        let all_triggers = all_triggers.join(", ");
538        for &id in &roots {
539            self.diag(
540                "invalid-workflow",
541                format!(
542                    "{P}: step {} depends on nothing, so it starts the workflow, but {} is not a trigger: start with one of {all_triggers} and depend on it",
543                    label(id),
544                    kind_of(id).unwrap_or("")
545                ),
546                &path(id),
547            );
548        }
549        if triggers.is_empty() && roots.is_empty() && unknown.is_empty() {
550            self.diag("invalid-workflow", format!("{P}: the workflow has no trigger: one of {all_triggers} starts it"), &["steps"]);
551        }
552        if !names.iter().any(|id| kind_of(id) == Some("finish")) {
553            self.diag("invalid-workflow", format!("{P}: the workflow has no finish step, which ends a run"), &["steps"]);
554        }
555        // reached from a trigger (or from where the checks above already stopped) through dependencies and routes
556        let mut next: HashMap<&str, Vec<&str>> = names.iter().map(|&id| (id, routes.get(id).cloned().unwrap_or_default())).collect();
557        for &id in &names {
558            for dep in deps_of(id) {
559                if let Some(n) = next.get_mut(dep) {
560                    n.push(id);
561                }
562            }
563        }
564        let mut reached: HashSet<&str> = HashSet::new();
565        let mut pending: Vec<&str> = [triggers, roots, unknown, missing_dep, cyclic].concat();
566        while let Some(id) = pending.pop() {
567            if !reached.insert(id) {
568                continue;
569            }
570            if let Some(n) = next.get(id) {
571                pending.extend(n.iter().copied().filter(|x| !reached.contains(x)));
572            }
573        }
574        for &id in &names {
575            if !reached.contains(id) && kind_of(id).is_some() {
576                self.diag("invalid-workflow", format!("{P}: step {} can't be reached from a trigger", label(id)), &path(id));
577            }
578        }
579    }
580}
581
582/// The line of the deepest key of `path` found in block-style YAML: each key at its parent's child indentation.
583fn locate(lines: &[(u32, &str)], path: &[&str]) -> Option<u32> {
584    let mut start = 0;
585    let mut parent: isize = -1;
586    let mut found = None;
587    for key in path {
588        let mut child: isize = -1;
589        let mut hit = None;
590        for (i, &(_, text)) in lines.iter().enumerate().skip(start) {
591            if js_trim(text).is_empty() || text.trim_start_matches(js_space).starts_with('#') {
592                continue;
593            }
594            let rest = text.trim_start_matches(js_space);
595            let indent = text[..text.len() - rest.len()].chars().count() as isize;
596            if indent <= parent {
597                break;
598            }
599            if child < 0 {
600                child = indent;
601            }
602            if indent != child {
603                continue;
604            }
605            if key_at(rest, key) {
606                hit = Some(i);
607                break;
608            }
609        }
610        let Some(i) = hit else { return found };
611        found = Some(lines[i].0);
612        start = i + 1;
613        parent = child;
614    }
615    found
616}
617
618fn key_at(s: &str, key: &str) -> bool {
619    ["", "\"", "'"].iter().any(|q| {
620        let p = format!("{q}{key}{q}:");
621        s.strip_prefix(p.as_str()).is_some_and(|after| after.is_empty() || after.starts_with([' ', '\t']))
622    })
623}