instruction-md 0.4.0

Read, check, resolve and verify instruction.md documents (the specification's first edition, instruction/1): the reader, the agent text, composition and signature verification
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
//! The checks a `:::workflow{dialect="instruction/workflow"}` body is held to (§9.1, the specification's
//! reference/workflows.md): its steps against the specification's workflow registry (`workflow-registry.json`,
//! vendored unchanged as `src/workflow-registry.json`) and its graph. A host must refuse each of these before
//! activation, so each is an error: `invalid-workflow` (§18: dialect schema, dependency graph or routing invalid),
//! `limit-exceeded` for the registry's published limits, `extension-unavailable` for a namespaced node whose alias the
//! document doesn't declare.
//!
//! - the definition: a name, a nonempty mapping of steps, no unknown field (`x-*` is extension data), a key when
//!   concurrency is key-scoped;
//! - each step: a valid name, a kind the registry has (or a declared `alias:node`), the kind's required fields, no
//!   field that is neither the kind's nor a common one, `depends_on` naming siblings, `retry.max` within the limit,
//!   `on_error` as fail, continue or `goto:<step>`, a scoping kind's body of `{steps}` or branches of them, a schedule
//!   with one of cron/every/at, a correlate with a window;
//! - each scope: no more steps than the limit, no deeper than the body limit, no dependency cycle, routes (switch cases
//!   and default, `goto:`, `on_timeout`) to a sibling that isn't a trigger; triggers and finish only at the top, a
//!   trigger depending on nothing;
//! - the top level: a step that depends on nothing starts the run, so it is a trigger; there is a trigger and a
//!   finish; every step is reached from a trigger.
//!
//! The same checks, codes and messages as the TypeScript reference's (`packages/spec/src/workflow.ts`), which models
//! the specification's own checker (its `tools/workflow_support.py`). What a host decides — which events it emits,
//! its node providers, expressions, credentials — is not checked: the specification lists no host events, so an
//! `event` trigger's `on` is any value. [`crate::check_reading`] (and [`crate::check()`], [`crate::deliver`]) runs these
//! checks on every such body ([`crate::workflows_diagnostics`]); [`workflow_diagnostics`] checks a definition on its
//! own. Diagnostics come sorted by line, code and message.

use std::collections::{BTreeMap, HashMap, HashSet};
use std::sync::LazyLock;

use serde::Deserialize;
use serde_json::Value;

use crate::js::{js_number, js_space, js_trim, truthy, utf16_cmp};
use crate::types::{Diagnostic, Object, Severity};

/// The native workflow dialect a `:::workflow` names to be checked here.
pub const WORKFLOW_DIALECT: &str = "instruction/workflow";

/// The workflow registry as vendored: the specification's `workflow-registry.json`.
pub const WORKFLOW_REGISTRY_JSON: &str = include_str!("workflow-registry.json");

/// A workflow step kind's registry entry.
#[derive(Clone, Debug, Default, Deserialize)]
pub struct WorkflowKind {
    /// The kind's own fields (the common fields are the registry's `common_fields`).
    #[serde(default)]
    pub fields: Vec<String>,
    #[serde(default)]
    pub required: Vec<String>,
    /// A trigger: it can start a run.
    #[serde(default)]
    pub start: bool,
    #[serde(default)]
    pub summary: String,
}

/// The registry's published limits.
#[derive(Clone, Copy, Debug, Default, Deserialize)]
pub struct WorkflowLimits {
    /// Steps in one scope.
    pub steps: usize,
    /// Nested body levels.
    pub body_depth: usize,
    /// `retry.max`.
    pub retry_max: f64,
}

/// The workflow registry, typed.
#[derive(Clone, Debug, Default, Deserialize)]
pub struct WorkflowRegistry {
    /// instruction-workflow-registry/1
    pub format: String,
    /// instruction/workflow
    pub dialect: String,
    pub revision: String,
    pub kinds: BTreeMap<String, WorkflowKind>,
    /// The fields every step takes.
    pub common_fields: Vec<String>,
    pub limits: WorkflowLimits,
}

static REGISTRY: LazyLock<WorkflowRegistry> = LazyLock::new(|| serde_json::from_str(WORKFLOW_REGISTRY_JSON).unwrap_or_default());

/// The workflow registry.
pub fn workflow_registry() -> &'static WorkflowRegistry {
    &REGISTRY
}

/// The definition's fields (reference/workflows.md, Definition fields), and `$schema`, which its schema allows.
const DEFINITION_FIELDS: &[&str] = &[
    "name",
    "steps",
    "description",
    "armed",
    "inputs",
    "outputs",
    "concurrency",
    "key",
    "limits",
    "priority",
    "durable",
    "state",
    "unload",
    "tool",
    "act_for",
    "$schema",
];
const P: &str = ":::workflow";

/// The kinds whose field holds a nested scope of steps, and that field (reference/workflows.md, Graphs, scopes and
/// validation: `foreach`, `batch`, `iterate` and `subgraph` contain `body: {steps: …}`; `parallel` and `race` contain
/// named `branches`, each with its own `steps`). The registry lists each kind's fields but not which hold steps, so
/// this is the specification's text; a field of the same name on another kind (an `http` request's `body`) is that
/// kind's data, never a scope.
pub const WORKFLOW_SCOPES: &[(&str, &str)] =
    &[("batch", "body"), ("foreach", "body"), ("iterate", "body"), ("parallel", "branches"), ("race", "branches"), ("subgraph", "body")];

/// The field of `kind` that holds a nested scope of steps, if it is a scoping kind.
pub fn workflow_scope(kind: &str) -> Option<&'static str> {
    WORKFLOW_SCOPES.iter().find(|(k, _)| *k == kind).map(|(_, f)| *f)
}

/// `^[A-Za-z_][A-Za-z0-9_-]{0,63}$`
fn is_name(s: &str) -> bool {
    let b = s.as_bytes();
    !b.is_empty()
        && b.len() <= 64
        && (b[0].is_ascii_alphabetic() || b[0] == b'_')
        && b[1..].iter().all(|c| c.is_ascii_alphanumeric() || *c == b'_' || *c == b'-')
}

/// `^x-[a-z0-9_.-]+$`
fn is_extension_field(s: &str) -> bool {
    s.strip_prefix("x-")
        .is_some_and(|r| !r.is_empty() && r.bytes().all(|c| c.is_ascii_lowercase() || c.is_ascii_digit() || b"_.-".contains(&c)))
}

/// `^[a-z][a-z0-9-]*:[a-z][a-z0-9-]*$`
fn is_custom_kind(s: &str) -> bool {
    let part = |p: &str| {
        let b = p.as_bytes();
        !b.is_empty() && b[0].is_ascii_lowercase() && b.iter().all(|c| c.is_ascii_lowercase() || c.is_ascii_digit() || *c == b'-')
    };
    s.split_once(':').is_some_and(|(a, k)| part(a) && part(k))
}

/// `^(?:fail|continue|goto:[A-Za-z_][A-Za-z0-9_-]{0,63})$`
fn is_on_error(s: &str) -> bool {
    s == "fail" || s == "continue" || s.strip_prefix("goto:").is_some_and(is_name)
}

/// `Number.isInteger`.
fn integer(v: &Value) -> Option<f64> {
    v.as_f64().filter(|f| f.is_finite() && f.fract() == 0.0)
}

fn quote(s: &str) -> String {
    format!("\"{s}\"")
}

/// A mapping's keys, sorted as ECMAScript sorts strings.
fn keys(o: &Object) -> Vec<&str> {
    let mut k: Vec<&str> = o.keys().map(String::as_str).collect();
    k.sort_by(|a, b| utf16_cmp(a, b));
    k
}

fn join<'a>(a: &[&'a str], b: &[&'a str]) -> Vec<&'a str> {
    a.iter().chain(b).copied().collect()
}

fn steps_of(v: Option<&Value>) -> Option<&Object> {
    v.and_then(|b| b.get("steps")).and_then(Value::as_object)
}

/// A body: `{steps: {…}}` and nothing else.
fn is_body(v: Option<&Value>) -> bool {
    v.and_then(Value::as_object).is_some_and(|o| o.len() == 1 && o.get("steps").is_some_and(Value::is_object))
}

/// A workflow definition's diagnostics, without lines: what [`crate::check_reading`] reports for an
/// `instruction/workflow` body (it places each on the line of the key it is about). `extensions` is the document's front matter
/// `extensions`, which a namespaced `alias:node` kind needs its alias in.
pub fn workflow_diagnostics(definition: &Value, extensions: Option<&Object>) -> Vec<Diagnostic> {
    check(definition, &[], 0, extensions)
}

/// The checks, each diagnostic on the line of the deepest key of its path found in the body's lines (else `at`).
pub(crate) fn check(definition: &Value, lines: &[(u32, &str)], at: u32, extensions: Option<&Object>) -> Vec<Diagnostic> {
    let mut c = Checker { out: Vec::new(), lines, at, extensions, reg: workflow_registry() };
    let Some(def) = definition.as_object() else { return c.out }; // (the reader reports a body that isn't a mapping)
    if !def.get("name").and_then(Value::as_str).is_some_and(is_name) {
        c.diag(
            "invalid-workflow",
            format!("{P}: its name is required: 1 to 64 letters, digits, \"_\" and \"-\", starting with a letter or \"_\""),
            &["name"],
        );
    }
    for k in keys(def) {
        if !DEFINITION_FIELDS.contains(&k) && !is_extension_field(k) {
            c.diag("invalid-workflow", format!("{P}: \"{k}\" is not a field of a workflow definition"), &[k]);
        }
    }
    if let Some(concurrency) = def.get("concurrency").and_then(Value::as_object)
        && concurrency.get("scope").and_then(Value::as_str) == Some("key")
        && !def.contains_key("key")
    {
        c.diag("invalid-workflow", format!("{P}: key-scoped concurrency needs the workflow's key"), &["concurrency"]);
    }
    match def.get("steps").and_then(Value::as_object) {
        Some(steps) if !steps.is_empty() => c.scope(steps, &[], &["steps"], 0),
        _ => c.diag("invalid-workflow", format!("{P}: its steps are a nonempty mapping of step names to steps"), &["steps"]),
    }
    let line = |d: &Diagnostic| d.range.map_or(0, |r| r.start);
    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)));
    c.out
}

struct Checker<'a> {
    out: Vec<Diagnostic>,
    lines: &'a [(u32, &'a str)],
    at: u32,
    extensions: Option<&'a Object>,
    reg: &'static WorkflowRegistry,
}

impl Checker<'_> {
    fn diag(&mut self, code: &'static str, message: String, path: &[&str]) {
        let line = if self.lines.is_empty() { 0 } else { locate(self.lines, path).unwrap_or(self.at) };
        self.out.push(Diagnostic::new(code, Severity::Error, message, line));
    }

    fn kind(&self, k: &str) -> Option<&'static WorkflowKind> {
        self.reg.kinds.get(k)
    }

    /// One scope's steps: the top level (depth 0), or a body's or a branch's.
    fn scope<'a>(&mut self, steps: &'a Object, prefix: &[&'a str], at: &[&'a str], depth: usize) {
        let names = keys(steps);
        let limits = self.reg.limits;
        if names.len() > limits.steps {
            self.diag("limit-exceeded", format!("{P}: {} steps in one scope; the limit is {}", names.len(), limits.steps), at);
        }
        let path = |id: &'a str| join(at, &[id]);
        let label = |id: &str| quote(&prefix.iter().copied().chain([id]).collect::<Vec<_>>().join("."));
        let kind_of =
            |id: &str| -> Option<&str> { steps.get(id).and_then(Value::as_object).and_then(|s| s.get("kind")).and_then(Value::as_str) };
        let reg = self.reg;
        let is_trigger = |id: &str| kind_of(id).and_then(|k| reg.kinds.get(k)).is_some_and(|k| k.start);
        let deps_of = |id: &str| -> Vec<&str> {
            match steps.get(id).and_then(Value::as_object).and_then(|s| s.get("depends_on")) {
                Some(Value::Array(d)) => d.iter().filter_map(Value::as_str).collect(),
                _ => Vec::new(),
            }
        };
        let mut routes: HashMap<&str, Vec<&str>> = HashMap::new();
        let mut missing_dep: Vec<&str> = Vec::new();
        for &id in &names {
            let where_ = label(id);
            let here = path(id);
            let with = |k: &'a str| join(&here, &[k]);
            if !is_name(id) {
                self.diag(
                    "invalid-workflow",
                    format!(
                        "{P}: {where_} is not a valid step name: 1 to 64 letters, digits, \"_\" and \"-\", starting with a letter or \"_\""
                    ),
                    &here,
                );
            }
            let Some(s) = steps.get(id).and_then(Value::as_object) else {
                self.diag("invalid-workflow", format!("{P}: step {where_} is a mapping with a kind"), &here);
                continue;
            };
            let Some(kind) = s.get("kind").and_then(Value::as_str) else {
                self.diag("invalid-workflow", format!("{P}: step {where_} has no kind"), &here);
                continue;
            };
            let spec = self.kind(kind);
            match spec {
                None => {
                    if is_custom_kind(kind) {
                        let alias = kind.split(':').next().unwrap_or("");
                        if !truthy(self.extensions.and_then(|e| e.get(alias))) {
                            self.diag(
                                "extension-unavailable",
                                format!(
                                    "{P}: step {where_}: the extension alias \"{alias}\" is not declared in the front matter's extensions"
                                ),
                                &with("kind"),
                            );
                        }
                    } else {
                        self.diag("invalid-workflow", format!("{P}: step {where_}: \"{kind}\" is not a workflow step kind"), &with("kind"));
                    }
                }
                Some(spec) => {
                    for f in &spec.required {
                        if !s.contains_key(f) {
                            self.diag("invalid-workflow", format!("{P}: step {where_} ({kind}) needs {f}"), &here);
                        }
                    }
                    for f in keys(s) {
                        if !spec.fields.iter().any(|x| x == f) && !self.reg.common_fields.iter().any(|x| x == f) && !is_extension_field(f) {
                            self.diag(
                                "invalid-workflow",
                                format!("{P}: step {where_} ({kind}): \"{f}\" is not a field of {kind} or a common step field"),
                                &with(f),
                            );
                        }
                    }
                    if spec.start && depth > 0 {
                        self.diag(
                            "invalid-workflow",
                            format!("{P}: step {where_} ({kind}) is a trigger, which only the top-level steps can hold"),
                            &here,
                        );
                    }
                    if spec.start && !deps_of(id).is_empty() {
                        self.diag(
                            "invalid-workflow",
                            format!("{P}: step {where_} ({kind}) is a trigger, which depends on nothing"),
                            &with("depends_on"),
                        );
                    }
                    if kind == "finish" && depth > 0 {
                        self.diag(
                            "invalid-workflow",
                            format!("{P}: step {where_} is a finish, which only the top-level steps can hold"),
                            &here,
                        );
                    }
                    if kind == "schedule" && ["cron", "every", "at"].iter().filter(|f| s.contains_key(**f)).count() != 1 {
                        self.diag(
                            "invalid-workflow",
                            format!("{P}: step {where_} (schedule) sets exactly one of cron, every and at"),
                            &here,
                        );
                    }
                    if kind == "correlate" && !s.contains_key("window") {
                        self.diag("invalid-workflow", format!("{P}: step {where_} (correlate) needs a window"), &here);
                    }
                }
            }
            if let Some(d) = s.get("depends_on") {
                let distinct = |list: &[Value]| {
                    let mut seen = HashSet::new();
                    list.iter().all(|x| x.as_str().is_some_and(|x| seen.insert(x)))
                };
                if !d.as_array().is_some_and(|list| distinct(list)) {
                    self.diag(
                        "invalid-workflow",
                        format!("{P}: step {where_}: depends_on is a list of distinct step names"),
                        &with("depends_on"),
                    );
                }
                for dep in deps_of(id) {
                    if !steps.contains_key(dep) {
                        if !missing_dep.contains(&id) {
                            missing_dep.push(id);
                        }
                        self.diag(
                            "invalid-workflow",
                            format!("{P}: step {where_} depends on \"{dep}\", which is not a step in its scope"),
                            &with("depends_on"),
                        );
                    }
                }
            }
            if let Some(max) = s.get("retry").and_then(Value::as_object).and_then(|r| r.get("max")) {
                match integer(max) {
                    Some(n) if n > limits.retry_max => self.diag(
                        "limit-exceeded",
                        format!("{P}: step {where_} retries {} times; the limit is {}", js_number(n), js_number(limits.retry_max)),
                        &with("retry"),
                    ),
                    Some(n) if n >= 0.0 => {}
                    _ => self.diag(
                        "invalid-workflow",
                        format!("{P}: step {where_}: retry.max is a whole number of retries, at most {}", js_number(limits.retry_max)),
                        &with("retry"),
                    ),
                }
            }
            let mut targets: Vec<&str> = Vec::new();
            if let Some(on_error) = s.get("on_error") {
                match on_error.as_str() {
                    Some(e) if is_on_error(e) => {
                        if let Some(t) = e.strip_prefix("goto:") {
                            targets.push(t);
                        }
                    }
                    _ => self.diag(
                        "invalid-workflow",
                        format!("{P}: step {where_}: on_error is fail, continue or goto:<step>"),
                        &with("on_error"),
                    ),
                }
            }
            if kind == "switch" {
                if let Some(cases) = s.get("cases").and_then(Value::as_object) {
                    for case in keys(cases) {
                        match cases.get(case) {
                            Some(Value::String(t)) => targets.push(t),
                            _ => self.diag(
                                "invalid-workflow",
                                format!("{P}: step {where_} (switch): case \"{case}\" names one step, as a string"),
                                &with("cases"),
                            ),
                        }
                    }
                }
                if let Some(Value::String(t)) = s.get("default") {
                    targets.push(t);
                }
            }
            if let Some(Value::String(t)) = s.get("on_timeout") {
                targets.push(t);
            }
            for &t in &targets {
                if !steps.contains_key(t) {
                    self.diag("invalid-workflow", format!("{P}: step {where_} routes to \"{t}\", which is not a step in its scope"), &here);
                } else if is_trigger(t) {
                    self.diag(
                        "invalid-workflow",
                        format!("{P}: step {where_} routes to \"{t}\", a trigger: a route can't start a run"),
                        &here,
                    );
                }
            }
            routes.insert(id, targets.into_iter().filter(|t| steps.contains_key(*t)).collect());
            // the nested scopes: (prefix, path, steps)
            let mut nested: Vec<(Vec<&'a str>, Vec<&'a str>, &'a Object)> = Vec::new();
            let takes = |f: &str| spec.is_some() && workflow_scope(kind) == Some(f);
            let inner = steps_of;
            if takes("body") && s.contains_key("body") {
                match inner(s.get("body")).filter(|_| is_body(s.get("body"))) {
                    Some(st) => nested.push((prefix.iter().copied().chain([id]).collect(), [with("body"), vec!["steps"]].concat(), st)),
                    None => self.diag(
                        "invalid-workflow",
                        format!("{P}: step {where_}: its body is {{steps: …}}, a mapping of steps"),
                        &with("body"),
                    ),
                }
            }
            if takes("branches") && s.contains_key("branches") {
                match s.get("branches").and_then(Value::as_object) {
                    Some(b) if !b.is_empty() && b.values().all(|v| is_body(Some(v))) => {
                        for n in keys(b) {
                            if let Some(st) = inner(b.get(n)) {
                                nested.push((
                                    prefix.iter().copied().chain([id, n]).collect(),
                                    [with("branches"), vec![n, "steps"]].concat(),
                                    st,
                                ));
                            }
                        }
                    }
                    _ => self.diag(
                        "invalid-workflow",
                        format!("{P}: step {where_}: its branches are a mapping of names to {{steps: …}}"),
                        &with("branches"),
                    ),
                }
            }
            for (p, a, st) in nested {
                if depth + 1 > limits.body_depth {
                    self.diag("limit-exceeded", format!("{P}: step {where_} nests bodies deeper than {} levels", limits.body_depth), &here);
                    break;
                }
                self.scope(st, &p, &a, depth + 1);
            }
        }

        // dependency cycles, each found once: a depth-first walk in name order, dependencies in their written order
        // (iterative: a scope may hold any number of steps)
        let mut cyclic: Vec<&str> = Vec::new();
        let mut state: HashMap<&str, bool> = HashMap::new(); // false: visiting, true: done
        for &root in &names {
            if state.contains_key(root) {
                continue;
            }
            let mut stack: Vec<(&str, Vec<&str>, usize)> = vec![(root, deps_of(root), 0)];
            state.insert(root, false);
            while let Some(top) = stack.last_mut() {
                let Some(&dep) = top.1.get(top.2) else {
                    let (id, _, _) = stack.pop().unwrap_or((root, Vec::new(), 0));
                    state.insert(id, true);
                    continue;
                };
                top.2 += 1;
                if !steps.contains_key(dep) {
                    continue;
                }
                match state.get(dep) {
                    Some(false) => {
                        let from = stack.iter().position(|f| f.0 == dep).unwrap_or(0);
                        let cycle: Vec<&str> = stack[from..].iter().map(|f| f.0).collect();
                        for &c in &cycle {
                            if !cyclic.contains(&c) {
                                cyclic.push(c);
                            }
                        }
                        let shown: Vec<String> = cycle.iter().copied().chain([dep]).map(label).collect();
                        self.diag(
                            "invalid-workflow",
                            format!("{P}: the steps {} depend on each other in a cycle", shown.join(" → ")),
                            &path(dep),
                        );
                    }
                    Some(true) => {}
                    None => {
                        state.insert(dep, false);
                        stack.push((dep, deps_of(dep), 0));
                    }
                }
            }
        }

        if depth > 0 {
            return;
        }
        let routed: HashSet<&str> = routes.values().flatten().copied().collect();
        let triggers: Vec<&str> = names.iter().copied().filter(|id| is_trigger(id)).collect();
        // a namespaced node's role (trigger or step) is its extension's to say, and an unknown kind is already reported
        let unknown: Vec<&str> =
            names.iter().copied().filter(|id| kind_of(id).is_some_and(|k| !reg.kinds.contains_key(k)) && deps_of(id).is_empty()).collect();
        let roots: Vec<&str> = names
            .iter()
            .copied()
            .filter(|id| {
                kind_of(id).and_then(|k| reg.kinds.get(k)).is_some_and(|k| !k.start) && deps_of(id).is_empty() && !routed.contains(id)
            })
            .collect();
        let mut all_triggers: Vec<&str> = reg.kinds.iter().filter(|(_, k)| k.start).map(|(n, _)| n.as_str()).collect();
        all_triggers.sort_by(|a, b| utf16_cmp(a, b));
        let all_triggers = all_triggers.join(", ");
        for &id in &roots {
            self.diag(
                "invalid-workflow",
                format!(
                    "{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",
                    label(id),
                    kind_of(id).unwrap_or("")
                ),
                &path(id),
            );
        }
        if triggers.is_empty() && roots.is_empty() && unknown.is_empty() {
            self.diag("invalid-workflow", format!("{P}: the workflow has no trigger: one of {all_triggers} starts it"), &["steps"]);
        }
        if !names.iter().any(|id| kind_of(id) == Some("finish")) {
            self.diag("invalid-workflow", format!("{P}: the workflow has no finish step, which ends a run"), &["steps"]);
        }
        // reached from a trigger (or from where the checks above already stopped) through dependencies and routes
        let mut next: HashMap<&str, Vec<&str>> = names.iter().map(|&id| (id, routes.get(id).cloned().unwrap_or_default())).collect();
        for &id in &names {
            for dep in deps_of(id) {
                if let Some(n) = next.get_mut(dep) {
                    n.push(id);
                }
            }
        }
        let mut reached: HashSet<&str> = HashSet::new();
        let mut pending: Vec<&str> = [triggers, roots, unknown, missing_dep, cyclic].concat();
        while let Some(id) = pending.pop() {
            if !reached.insert(id) {
                continue;
            }
            if let Some(n) = next.get(id) {
                pending.extend(n.iter().copied().filter(|x| !reached.contains(x)));
            }
        }
        for &id in &names {
            if !reached.contains(id) && kind_of(id).is_some() {
                self.diag("invalid-workflow", format!("{P}: step {} can't be reached from a trigger", label(id)), &path(id));
            }
        }
    }
}

/// The line of the deepest key of `path` found in block-style YAML: each key at its parent's child indentation.
fn locate(lines: &[(u32, &str)], path: &[&str]) -> Option<u32> {
    let mut start = 0;
    let mut parent: isize = -1;
    let mut found = None;
    for key in path {
        let mut child: isize = -1;
        let mut hit = None;
        for (i, &(_, text)) in lines.iter().enumerate().skip(start) {
            if js_trim(text).is_empty() || text.trim_start_matches(js_space).starts_with('#') {
                continue;
            }
            let rest = text.trim_start_matches(js_space);
            let indent = text[..text.len() - rest.len()].chars().count() as isize;
            if indent <= parent {
                break;
            }
            if child < 0 {
                child = indent;
            }
            if indent != child {
                continue;
            }
            if key_at(rest, key) {
                hit = Some(i);
                break;
            }
        }
        let Some(i) = hit else { return found };
        found = Some(lines[i].0);
        start = i + 1;
        parent = child;
    }
    found
}

fn key_at(s: &str, key: &str) -> bool {
    ["", "\"", "'"].iter().any(|q| {
        let p = format!("{q}{key}{q}:");
        s.strip_prefix(p.as_str()).is_some_and(|after| after.is_empty() || after.starts_with([' ', '\t']))
    })
}