Skip to main content

speccoder_core/
graph.rs

1//! Task dependencies from what `tasks.md` documents, and which tasks are ready.
2//!
3//! Edges come only from structure and from IDs written in task text; nothing
4//! is inferred:
5//!
6//! - **Phases.** Foundational waits on all earlier phases; each user-story
7//!   phase waits on the earlier *non-story* phases only, so stories are
8//!   independent of each other; polish, convergence and unrecognised phases
9//!   wait on all earlier phases.
10//! - **Subsections.** A `###` subsection waits on the earlier subsections of
11//!   its phase (tests before implementation).
12//! - **`[P]` runs.** A `[P]` task waits on the previous non-`[P]` task; a
13//!   non-`[P]` task waits on the whole preceding `[P]` run, or on the previous
14//!   task when there is no run.
15//! - **Explicit.** `depends on T012` / `after T012` in the task text.
16//!
17//! In **declared** mode (the Format line documents `(depends on …)`) the
18//! written references are the complete order within a phase:
19//! subsection and `[P]` edges are dropped, phase order is kept.
20//!
21//! In **chain** mode (OpenSpec) a group waits on every earlier group and a
22//! task on the one before it in its group; written references are added.
23//!
24//! Dangling references and cycles are errors; the tasks involved are blocked.
25
26use std::collections::{BTreeSet, HashMap};
27
28use crate::snapshot::{
29    Dependency, DependencyKind, DependencyMode, Diagnostic, ParsedTasks, Schedule, ScheduleTotals,
30    ScheduledTask, Severity, Task, TaskState,
31};
32
33/// What a phase heading says the phase is.
34#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35pub enum PhaseKind {
36    /// Shared infrastructure.
37    Setup,
38    /// Blocking prerequisites of every story.
39    Foundational,
40    /// One user story; independent of the other stories.
41    Story,
42    /// Cross-cutting work after the stories.
43    Polish,
44    /// Tasks appended by `/speckit-converge`.
45    Convergence,
46    /// Anything else; waits on everything before it.
47    Other,
48}
49
50/// Classifies a phase by its heading and whether its tasks carry story labels.
51#[must_use]
52pub fn classify(title: &str, has_story_labels: bool) -> PhaseKind {
53    let t = title.to_lowercase();
54    if t.contains("convergence") {
55        PhaseKind::Convergence
56    } else if t.contains("polish") {
57        PhaseKind::Polish
58    } else if has_story_labels || names_a_user_story(&t) {
59        PhaseKind::Story
60    } else if t.contains("foundational") {
61        PhaseKind::Foundational
62    } else if t.contains("setup") {
63        PhaseKind::Setup
64    } else {
65        PhaseKind::Other
66    }
67}
68
69fn names_a_user_story(lower: &str) -> bool {
70    lower.match_indices("user story").any(|(i, m)| {
71        lower[i + m.len()..]
72            .trim_start()
73            .starts_with(|c: char| c.is_ascii_digit())
74    })
75}
76
77/// A run of consecutive tasks sharing a phase heading.
78struct Group {
79    kind: PhaseKind,
80    /// Task indices, split into consecutive subsection blocks.
81    blocks: Vec<Vec<usize>>,
82}
83
84/// While grouping: (phase title, subsection blocks, current subsection).
85type OpenGroup<'t> = (Option<&'t str>, Vec<Vec<usize>>, Option<&'t str>);
86
87fn groups(tasks: &[Task]) -> Vec<Group> {
88    let mut out: Vec<OpenGroup<'_>> = Vec::new();
89    for (i, t) in tasks.iter().enumerate() {
90        let phase = t.phase.as_deref();
91        let sub = t.subsection.as_deref();
92        match out.last_mut() {
93            Some((p, blocks, last_sub)) if *p == phase => {
94                if *last_sub == sub {
95                    if let Some(b) = blocks.last_mut() {
96                        b.push(i);
97                    }
98                } else {
99                    blocks.push(vec![i]);
100                    *last_sub = sub;
101                }
102            }
103            _ => out.push((phase, vec![vec![i]], sub)),
104        }
105    }
106    out.into_iter()
107        .map(|(phase, blocks, _)| {
108            let labelled = blocks.iter().flatten().any(|&i| tasks[i].story.is_some());
109            Group {
110                kind: classify(phase.unwrap_or(""), labelled),
111                blocks,
112            }
113        })
114        .collect()
115}
116
117/// Builds the schedule of `parsed`, with `graph.*` diagnostics.
118#[must_use]
119pub fn schedule(parsed: &ParsedTasks) -> (Schedule, Vec<Diagnostic>) {
120    let tasks = &parsed.tasks;
121    let mut diags = Vec::new();
122    let index: HashMap<&str, usize> = tasks
123        .iter()
124        .enumerate()
125        .rev() // the first occurrence of a duplicate wins
126        .map(|(i, t)| (t.id.as_str(), i))
127        .collect();
128
129    // Structural dependencies, as task indices.
130    let mut structural: Vec<Vec<usize>> = vec![Vec::new(); tasks.len()];
131    let declared = parsed.dependency_mode == DependencyMode::Declared;
132    let chain = parsed.dependency_mode == DependencyMode::Chain;
133    let groups = groups(tasks);
134    for (g, group) in groups.iter().enumerate() {
135        if chain {
136            let earlier: Vec<usize> = groups[..g]
137                .iter()
138                .flat_map(|e| e.blocks.iter().flatten().copied())
139                .collect();
140            let mut previous: Option<usize> = None;
141            for &i in group.blocks.iter().flatten() {
142                let mut deps = earlier.clone();
143                deps.extend(previous);
144                structural[i] = deps;
145                previous = Some(i);
146            }
147            continue;
148        }
149        let phase_barrier: Vec<usize> = groups[..g]
150            .iter()
151            .filter(|earlier| group.kind != PhaseKind::Story || earlier.kind != PhaseKind::Story)
152            .flat_map(|earlier| earlier.blocks.iter().flatten().copied())
153            .collect();
154        for (b, block) in group.blocks.iter().enumerate() {
155            let sub_barrier: Vec<usize> = group.blocks[..b].iter().flatten().copied().collect();
156            let mut last_serial: Option<usize> = None;
157            let mut run: Vec<usize> = Vec::new();
158            for &i in block {
159                let mut deps = phase_barrier.clone();
160                if declared {
161                    structural[i] = deps;
162                    continue;
163                }
164                deps.extend(&sub_barrier);
165                if tasks[i].parallel {
166                    deps.extend(last_serial);
167                    run.push(i);
168                } else {
169                    if run.is_empty() {
170                        deps.extend(last_serial);
171                    } else {
172                        deps.append(&mut run);
173                    }
174                    last_serial = Some(i);
175                }
176                structural[i] = deps;
177            }
178        }
179    }
180
181    // Direct dependencies with kinds; explicit ones resolved by ID.
182    let mut direct: Vec<Vec<Dependency>> = Vec::with_capacity(tasks.len());
183    let mut edges: Vec<Vec<usize>> = Vec::with_capacity(tasks.len());
184    for (i, t) in tasks.iter().enumerate() {
185        let mut seen = BTreeSet::new();
186        let mut deps = Vec::new();
187        let mut resolved = Vec::new();
188        for &d in &structural[i] {
189            if seen.insert(tasks[d].id.as_str()) {
190                deps.push(Dependency {
191                    id: tasks[d].id.clone(),
192                    kind: DependencyKind::Structural,
193                    missing: false,
194                });
195                resolved.push(d);
196            }
197        }
198        for id in &t.depends_on {
199            if !seen.insert(id.as_str()) {
200                continue;
201            }
202            match index.get(id.as_str()) {
203                Some(&d) => resolved.push(d),
204                None => diags.push(
205                    Diagnostic::new(
206                        Severity::Error,
207                        "graph.dangling",
208                        format!("{} depends on {id}, which does not exist", t.id),
209                    )
210                    .at(&parsed.path)
211                    .line(t.line)
212                    .hint("fix the task ID or remove the reference"),
213                ),
214            }
215            deps.push(Dependency {
216                id: id.clone(),
217                kind: DependencyKind::Explicit,
218                missing: !index.contains_key(id.as_str()),
219            });
220        }
221        direct.push(deps);
222        edges.push(resolved);
223    }
224
225    // Cycles: strongly connected components with more than one task, or a self-loop.
226    let component = strongly_connected(&edges);
227    let mut members: HashMap<usize, Vec<usize>> = HashMap::new();
228    for (i, &c) in component.iter().enumerate() {
229        members.entry(c).or_default().push(i);
230    }
231    let in_cycle = |i: usize| members[&component[i]].len() > 1 || edges[i].contains(&i);
232    let mut reported = BTreeSet::new();
233    for i in 0..tasks.len() {
234        if in_cycle(i) && reported.insert(component[i]) {
235            let ids: Vec<&str> = members[&component[i]]
236                .iter()
237                .map(|&m| tasks[m].id.as_str())
238                .collect();
239            diags.push(
240                Diagnostic::new(
241                    Severity::Error,
242                    "graph.cycle",
243                    format!("dependency cycle: {}", ids.join(" → ")),
244                )
245                .at(&parsed.path)
246                .line(tasks[i].line)
247                .hint("remove one of the `depends on` references"),
248            );
249        }
250    }
251
252    // States.
253    let mut out = Vec::with_capacity(tasks.len());
254    let mut totals = ScheduleTotals::default();
255    for (i, t) in tasks.iter().enumerate() {
256        let mut blockers: Vec<(usize, String)> = Vec::new();
257        for (dep, &d) in direct[i]
258            .iter()
259            .zip(resolved_or_missing(&direct[i], &index).iter())
260        {
261            match d {
262                None => blockers.push((usize::MAX, dep.id.clone())),
263                Some(d) => {
264                    let cyclic = in_cycle(i) && component[d] == component[i];
265                    if !tasks[d].done || cyclic {
266                        blockers.push((d, dep.id.clone()));
267                    }
268                }
269            }
270        }
271        blockers.sort();
272        blockers.dedup();
273        let state = if t.done {
274            totals.done += 1;
275            TaskState::Done
276        } else if blockers.is_empty() && !in_cycle(i) {
277            totals.ready += 1;
278            TaskState::Ready
279        } else {
280            totals.blocked += 1;
281            TaskState::Blocked
282        };
283        out.push(ScheduledTask {
284            id: t.id.clone(),
285            state,
286            depends_on: direct[i].clone(),
287            blocked_by: if t.done {
288                Vec::new()
289            } else {
290                blockers.into_iter().map(|(_, id)| id).collect()
291            },
292        });
293    }
294    (Schedule { tasks: out, totals }, diags)
295}
296
297fn resolved_or_missing(deps: &[Dependency], index: &HashMap<&str, usize>) -> Vec<Option<usize>> {
298    deps.iter()
299        .map(|d| index.get(d.id.as_str()).copied())
300        .collect()
301}
302
303/// Iterative Tarjan: the component number of every node.
304fn strongly_connected(edges: &[Vec<usize>]) -> Vec<usize> {
305    const UNSEEN: usize = usize::MAX;
306    let n = edges.len();
307    let mut order = vec![UNSEEN; n];
308    let mut low = vec![0; n];
309    let mut on_stack = vec![false; n];
310    let mut component = vec![UNSEEN; n];
311    let mut stack = Vec::new();
312    let mut next_order = 0;
313    let mut next_component = 0;
314
315    for root in 0..n {
316        if order[root] != UNSEEN {
317            continue;
318        }
319        // (node, index of the next edge to visit)
320        let mut work = vec![(root, 0usize)];
321        while let Some(&mut (v, ref mut e)) = work.last_mut() {
322            if *e == 0 && order[v] == UNSEEN {
323                order[v] = next_order;
324                low[v] = next_order;
325                next_order += 1;
326                stack.push(v);
327                on_stack[v] = true;
328            }
329            if let Some(&w) = edges[v].get(*e) {
330                *e += 1;
331                if order[w] == UNSEEN {
332                    work.push((w, 0));
333                } else if on_stack[w] {
334                    low[v] = low[v].min(order[w]);
335                }
336                continue;
337            }
338            work.pop();
339            if let Some(&(parent, _)) = work.last() {
340                low[parent] = low[parent].min(low[v]);
341            }
342            if low[v] == order[v] {
343                while let Some(w) = stack.pop() {
344                    on_stack[w] = false;
345                    component[w] = next_component;
346                    if w == v {
347                        break;
348                    }
349                }
350                next_component += 1;
351            }
352        }
353    }
354    component
355}
356
357/// The open tasks that wait on `id`, directly or through another, in
358/// document order: what stays blocked when it is skipped.
359#[must_use]
360pub fn dependents(schedule: &Schedule, id: &str) -> Vec<String> {
361    let mut waiting: BTreeSet<&str> = BTreeSet::from([id]);
362    loop {
363        let before = waiting.len();
364        for t in &schedule.tasks {
365            if t.state != TaskState::Done
366                && t.depends_on.iter().any(|d| waiting.contains(d.id.as_str()))
367            {
368                waiting.insert(t.id.as_str());
369            }
370        }
371        if waiting.len() == before {
372            break;
373        }
374    }
375    schedule
376        .tasks
377        .iter()
378        .filter(|t| t.id != id && waiting.contains(t.id.as_str()))
379        .map(|t| t.id.clone())
380        .collect()
381}
382
383#[cfg(test)]
384mod tests {
385    use super::*;
386    use crate::snapshot::Totals;
387
388    /// `spec`: (id, phase, subsection, parallel, story, done, explicit deps)
389    type Spec<'a> = (
390        &'a str,
391        &'a str,
392        Option<&'a str>,
393        bool,
394        Option<&'a str>,
395        bool,
396        &'a [&'a str],
397    );
398
399    fn parsed(spec: &[Spec<'_>]) -> ParsedTasks {
400        parsed_in(DependencyMode::Structural, spec)
401    }
402
403    fn parsed_in(dependency_mode: DependencyMode, spec: &[Spec<'_>]) -> ParsedTasks {
404        let tasks: Vec<Task> = spec
405            .iter()
406            .enumerate()
407            .map(|(n, &(id, phase, sub, parallel, story, done, deps))| Task {
408                id: id.to_owned(),
409                done,
410                parallel,
411                story: story.map(str::to_owned),
412                yours: false,
413                title: String::new(),
414                depends_on: deps.iter().map(|d| (*d).to_owned()).collect(),
415                phase: Some(phase.to_owned()),
416                subsection: sub.map(str::to_owned),
417                line: u32::try_from(n + 1).unwrap(),
418                byte_range: [0, 0],
419                line_hash: String::new(),
420            })
421            .collect();
422        ParsedTasks {
423            path: "tasks.md".to_owned(),
424            phases: Vec::new(),
425            totals: Totals::default(),
426            tasks,
427            dependency_mode,
428        }
429    }
430
431    fn states(s: &Schedule) -> Vec<(&str, TaskState, Vec<&str>)> {
432        s.tasks
433            .iter()
434            .map(|t| {
435                (
436                    t.id.as_str(),
437                    t.state,
438                    t.blocked_by.iter().map(String::as_str).collect(),
439                )
440            })
441            .collect()
442    }
443
444    use TaskState::{Blocked, Done, Ready};
445
446    const SETUP: &str = "Phase 1: Setup";
447    const FOUND: &str = "Phase 2: Foundational";
448    const US1: &str = "Phase 3: User Story 1 - A";
449    const US2: &str = "Phase 4: User Story 2 - B";
450    const POLISH: &str = "Phase 5: Polish & Cross-Cutting Concerns";
451
452    #[test]
453    fn classifies_spec_kit_headings() {
454        assert_eq!(
455            classify("Phase 1: Setup (Shared Infrastructure)", false),
456            PhaseKind::Setup
457        );
458        assert_eq!(
459            classify("Phase 2: Foundational (Blocking Prerequisites)", false),
460            PhaseKind::Foundational
461        );
462        assert_eq!(
463            classify("Phase 3: User Story 1 - Login (Priority: P1) 🎯 MVP", false),
464            PhaseKind::Story
465        );
466        assert_eq!(
467            classify("Phase 9: Polish & Cross-Cutting Concerns", false),
468            PhaseKind::Polish
469        );
470        assert_eq!(
471            classify("Phase 10: Convergence", false),
472            PhaseKind::Convergence
473        );
474        assert_eq!(classify("Phase 4: Login", true), PhaseKind::Story);
475        assert_eq!(classify("User stories overview", false), PhaseKind::Other);
476    }
477
478    #[test]
479    fn open_setup_blocks_everything_after_it() {
480        let p = parsed(&[
481            ("T001", SETUP, None, false, None, false, &[]),
482            ("T002", FOUND, None, false, None, false, &[]),
483            ("T003", US1, None, false, Some("US1"), false, &[]),
484        ]);
485        let (s, d) = schedule(&p);
486        assert!(d.is_empty());
487        assert_eq!(
488            states(&s),
489            [
490                ("T001", Ready, vec![]),
491                ("T002", Blocked, vec!["T001"]),
492                ("T003", Blocked, vec!["T001", "T002"]),
493            ]
494        );
495    }
496
497    #[test]
498    fn a_skipped_task_names_what_waits_on_it() {
499        let p = parsed(&[
500            ("T001", SETUP, None, false, None, false, &[]),
501            ("T002", FOUND, None, false, None, false, &[]),
502            ("T003", US1, None, false, Some("US1"), false, &[]),
503        ]);
504        let (s, _) = schedule(&p);
505        assert_eq!(dependents(&s, "T001"), ["T002", "T003"]);
506        assert_eq!(dependents(&s, "T002"), ["T003"]);
507        assert!(dependents(&s, "T003").is_empty());
508    }
509
510    #[test]
511    fn stories_are_independent_and_polish_waits_for_all() {
512        let p = parsed(&[
513            ("T001", SETUP, None, false, None, true, &[]),
514            ("T002", FOUND, None, false, None, true, &[]),
515            ("T003", US1, None, false, Some("US1"), false, &[]),
516            ("T004", US2, None, false, Some("US2"), false, &[]),
517            ("T005", POLISH, None, false, None, false, &[]),
518        ]);
519        let (s, _) = schedule(&p);
520        assert_eq!(
521            states(&s),
522            [
523                ("T001", Done, vec![]),
524                ("T002", Done, vec![]),
525                ("T003", Ready, vec![]),
526                ("T004", Ready, vec![]),
527                ("T005", Blocked, vec!["T003", "T004"]),
528            ]
529        );
530        assert_eq!(
531            s.totals,
532            ScheduleTotals {
533                done: 2,
534                ready: 2,
535                blocked: 1
536            }
537        );
538    }
539
540    #[test]
541    fn parallel_runs_fork_and_join() {
542        let p = parsed(&[
543            ("T001", SETUP, None, false, None, true, &[]),
544            ("T002", SETUP, None, true, None, false, &[]),
545            ("T003", SETUP, None, true, None, false, &[]),
546            ("T004", SETUP, None, false, None, false, &[]),
547        ]);
548        let (s, _) = schedule(&p);
549        assert_eq!(
550            states(&s),
551            [
552                ("T001", Done, vec![]),
553                ("T002", Ready, vec![]),
554                ("T003", Ready, vec![]),
555                ("T004", Blocked, vec!["T002", "T003"]),
556            ]
557        );
558    }
559
560    #[test]
561    fn tests_subsection_comes_before_implementation() {
562        let p = parsed(&[
563            (
564                "T001",
565                US1,
566                Some("Tests for User Story 1"),
567                true,
568                Some("US1"),
569                false,
570                &[],
571            ),
572            (
573                "T002",
574                US1,
575                Some("Implementation for User Story 1"),
576                true,
577                Some("US1"),
578                false,
579                &[],
580            ),
581        ]);
582        let (s, _) = schedule(&p);
583        assert_eq!(states(&s)[1], ("T002", Blocked, vec!["T001"]));
584    }
585
586    #[test]
587    fn explicit_dependency_crosses_stories() {
588        let p = parsed(&[
589            ("T001", US1, None, false, Some("US1"), false, &[]),
590            ("T002", US2, None, false, Some("US2"), false, &["T001"]),
591        ]);
592        let (s, _) = schedule(&p);
593        assert_eq!(states(&s)[1], ("T002", Blocked, vec!["T001"]));
594        assert_eq!(s.tasks[1].depends_on[0].kind, DependencyKind::Explicit);
595    }
596
597    #[test]
598    fn declared_mode_keeps_phase_order_but_drops_structure_within_a_phase() {
599        let p = parsed_in(
600            DependencyMode::Declared,
601            &[
602                ("T001", SETUP, None, false, None, true, &[]),
603                ("T002", SETUP, None, false, None, false, &["T001"]),
604                ("T003", SETUP, None, true, None, false, &["T001"]),
605                (
606                    "T004",
607                    US1,
608                    Some("Tests"),
609                    true,
610                    Some("US1"),
611                    false,
612                    &["T002"],
613                ),
614                (
615                    "T005",
616                    US1,
617                    Some("Implementation"),
618                    true,
619                    Some("US1"),
620                    false,
621                    &[],
622                ),
623            ],
624        );
625        let (s, d) = schedule(&p);
626        assert!(d.is_empty());
627        assert_eq!(
628            states(&s),
629            [
630                ("T001", Done, vec![]),
631                ("T002", Ready, vec![]),
632                ("T003", Ready, vec![]),
633                ("T004", Blocked, vec!["T002", "T003"]),
634                ("T005", Blocked, vec!["T002", "T003"]),
635            ]
636        );
637    }
638
639    #[test]
640    fn dangling_reference_is_an_error_and_blocks() {
641        let p = parsed(&[("T001", SETUP, None, false, None, false, &["T099"])]);
642        let (s, d) = schedule(&p);
643        assert_eq!(d[0].code, "graph.dangling");
644        assert_eq!(d[0].line, Some(1));
645        assert_eq!(states(&s)[0], ("T001", Blocked, vec!["T099"]));
646        assert!(s.tasks[0].depends_on[0].missing);
647    }
648
649    #[test]
650    fn cycles_and_self_references_are_errors_and_never_ready() {
651        // T002 waits on T001 structurally; T001 explicitly waits on T002.
652        let p = parsed(&[
653            ("T001", SETUP, None, false, None, false, &["T002"]),
654            ("T002", SETUP, None, false, None, true, &[]),
655            ("T003", POLISH, None, false, None, false, &["T003"]),
656        ]);
657        let (s, d) = schedule(&p);
658        let codes: Vec<_> = d
659            .iter()
660            .map(|d| (d.code.as_str(), d.message.as_str()))
661            .collect();
662        assert_eq!(
663            codes,
664            [
665                ("graph.cycle", "dependency cycle: T001 → T002"),
666                ("graph.cycle", "dependency cycle: T003"),
667            ]
668        );
669        assert_eq!(s.tasks[0].state, Blocked);
670        assert_eq!(s.tasks[2].state, Blocked);
671    }
672
673    mod properties {
674        use super::*;
675        use proptest::prelude::*;
676
677        /// Owned form of [`Spec`] while generating.
678        type OwnedSpec = (
679            String,
680            &'static str,
681            Option<String>,
682            bool,
683            Option<&'static str>,
684            bool,
685            Vec<String>,
686        );
687
688        const PHASES: [&str; 6] = [SETUP, FOUND, US1, US2, "Phase 6: Story notes", POLISH];
689
690        /// Random task lists: phases in template order, subsections, `[P]`,
691        /// done flags, and explicit references only to earlier tasks.
692        fn task_lists() -> impl Strategy<Value = ParsedTasks> {
693            prop::collection::vec(
694                (
695                    0..PHASES.len(),
696                    0..3usize,
697                    any::<bool>(),
698                    any::<bool>(),
699                    prop::option::of(0..64usize),
700                ),
701                1..40,
702            )
703            .prop_map(|mut rows| {
704                rows.sort_by_key(|r| (r.0, r.1));
705                let ids: Vec<String> = (1..=rows.len()).map(|n| format!("T{n:03}")).collect();
706                let spec: Vec<OwnedSpec> = rows
707                    .iter()
708                    .enumerate()
709                    .map(|(i, &(ph, sub, par, done, back))| {
710                        let story = match ph {
711                            2 => Some("US1"),
712                            3 => Some("US2"),
713                            _ => None,
714                        };
715                        let deps = back
716                            .filter(|_| i > 0)
717                            .map(|b| vec![ids[b % i].clone()])
718                            .unwrap_or_default();
719                        (
720                            ids[i].clone(),
721                            PHASES[ph],
722                            Some(format!("S{sub}")),
723                            par,
724                            story,
725                            done,
726                            deps,
727                        )
728                    })
729                    .collect();
730                let owned: Vec<Vec<&str>> = spec
731                    .iter()
732                    .map(|r| r.6.iter().map(String::as_str).collect())
733                    .collect();
734                let rows: Vec<Spec<'_>> = spec
735                    .iter()
736                    .zip(&owned)
737                    .map(|(r, d)| {
738                        (
739                            r.0.as_str(),
740                            r.1,
741                            r.2.as_deref(),
742                            r.3,
743                            r.4,
744                            r.5,
745                            d.as_slice(),
746                        )
747                    })
748                    .collect();
749                parsed(&rows)
750            })
751        }
752
753        proptest! {
754            #[test]
755            fn ready_means_every_dependency_is_done(p in task_lists()) {
756                let (s, _) = schedule(&p);
757                let done: HashMap<&str, bool> = p.tasks.iter().map(|t| (t.id.as_str(), t.done)).collect();
758                for t in &s.tasks {
759                    if t.state == Ready {
760                        prop_assert!(t.depends_on.iter().all(|d| done[d.id.as_str()]));
761                    }
762                }
763            }
764
765            #[test]
766            fn open_tasks_with_done_dependencies_are_ready(p in task_lists()) {
767                let (s, _) = schedule(&p);
768                let done: HashMap<&str, bool> = p.tasks.iter().map(|t| (t.id.as_str(), t.done)).collect();
769                for (t, task) in s.tasks.iter().zip(&p.tasks) {
770                    if !task.done && t.depends_on.iter().all(|d| done[d.id.as_str()]) {
771                        prop_assert_eq!(t.state, Ready);
772                    }
773                }
774            }
775
776            #[test]
777            fn stories_never_depend_structurally_on_each_other(p in task_lists()) {
778                let (s, _) = schedule(&p);
779                let story: HashMap<&str, Option<&str>> =
780                    p.tasks.iter().map(|t| (t.id.as_str(), t.story.as_deref())).collect();
781                for t in &s.tasks {
782                    for d in t.depends_on.iter().filter(|d| d.kind == DependencyKind::Structural) {
783                        if let (Some(a), Some(b)) = (story[t.id.as_str()], story[d.id.as_str()]) {
784                            prop_assert_eq!(a, b);
785                        }
786                    }
787                }
788            }
789
790            #[test]
791            fn backward_references_never_create_cycles(p in task_lists()) {
792                let (s, d) = schedule(&p);
793                prop_assert!(d.is_empty(), "{:?}", d);
794                prop_assert_eq!(s.totals.done + s.totals.ready + s.totals.blocked, p.tasks.len());
795            }
796        }
797    }
798}