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                scenarios: Vec::new(),
416                phase: Some(phase.to_owned()),
417                subsection: sub.map(str::to_owned),
418                line: u32::try_from(n + 1).unwrap(),
419                byte_range: [0, 0],
420                line_hash: String::new(),
421            })
422            .collect();
423        ParsedTasks {
424            path: "tasks.md".to_owned(),
425            phases: Vec::new(),
426            totals: Totals::default(),
427            tasks,
428            dependency_mode,
429        }
430    }
431
432    fn states(s: &Schedule) -> Vec<(&str, TaskState, Vec<&str>)> {
433        s.tasks
434            .iter()
435            .map(|t| {
436                (
437                    t.id.as_str(),
438                    t.state,
439                    t.blocked_by.iter().map(String::as_str).collect(),
440                )
441            })
442            .collect()
443    }
444
445    use TaskState::{Blocked, Done, Ready};
446
447    const SETUP: &str = "Phase 1: Setup";
448    const FOUND: &str = "Phase 2: Foundational";
449    const US1: &str = "Phase 3: User Story 1 - A";
450    const US2: &str = "Phase 4: User Story 2 - B";
451    const POLISH: &str = "Phase 5: Polish & Cross-Cutting Concerns";
452
453    #[test]
454    fn classifies_spec_kit_headings() {
455        assert_eq!(
456            classify("Phase 1: Setup (Shared Infrastructure)", false),
457            PhaseKind::Setup
458        );
459        assert_eq!(
460            classify("Phase 2: Foundational (Blocking Prerequisites)", false),
461            PhaseKind::Foundational
462        );
463        assert_eq!(
464            classify("Phase 3: User Story 1 - Login (Priority: P1) 🎯 MVP", false),
465            PhaseKind::Story
466        );
467        assert_eq!(
468            classify("Phase 9: Polish & Cross-Cutting Concerns", false),
469            PhaseKind::Polish
470        );
471        assert_eq!(
472            classify("Phase 10: Convergence", false),
473            PhaseKind::Convergence
474        );
475        assert_eq!(classify("Phase 4: Login", true), PhaseKind::Story);
476        assert_eq!(classify("User stories overview", false), PhaseKind::Other);
477    }
478
479    #[test]
480    fn open_setup_blocks_everything_after_it() {
481        let p = parsed(&[
482            ("T001", SETUP, None, false, None, false, &[]),
483            ("T002", FOUND, None, false, None, false, &[]),
484            ("T003", US1, None, false, Some("US1"), false, &[]),
485        ]);
486        let (s, d) = schedule(&p);
487        assert!(d.is_empty());
488        assert_eq!(
489            states(&s),
490            [
491                ("T001", Ready, vec![]),
492                ("T002", Blocked, vec!["T001"]),
493                ("T003", Blocked, vec!["T001", "T002"]),
494            ]
495        );
496    }
497
498    #[test]
499    fn a_skipped_task_names_what_waits_on_it() {
500        let p = parsed(&[
501            ("T001", SETUP, None, false, None, false, &[]),
502            ("T002", FOUND, None, false, None, false, &[]),
503            ("T003", US1, None, false, Some("US1"), false, &[]),
504        ]);
505        let (s, _) = schedule(&p);
506        assert_eq!(dependents(&s, "T001"), ["T002", "T003"]);
507        assert_eq!(dependents(&s, "T002"), ["T003"]);
508        assert!(dependents(&s, "T003").is_empty());
509    }
510
511    #[test]
512    fn stories_are_independent_and_polish_waits_for_all() {
513        let p = parsed(&[
514            ("T001", SETUP, None, false, None, true, &[]),
515            ("T002", FOUND, None, false, None, true, &[]),
516            ("T003", US1, None, false, Some("US1"), false, &[]),
517            ("T004", US2, None, false, Some("US2"), false, &[]),
518            ("T005", POLISH, None, false, None, false, &[]),
519        ]);
520        let (s, _) = schedule(&p);
521        assert_eq!(
522            states(&s),
523            [
524                ("T001", Done, vec![]),
525                ("T002", Done, vec![]),
526                ("T003", Ready, vec![]),
527                ("T004", Ready, vec![]),
528                ("T005", Blocked, vec!["T003", "T004"]),
529            ]
530        );
531        assert_eq!(
532            s.totals,
533            ScheduleTotals {
534                done: 2,
535                ready: 2,
536                blocked: 1
537            }
538        );
539    }
540
541    #[test]
542    fn parallel_runs_fork_and_join() {
543        let p = parsed(&[
544            ("T001", SETUP, None, false, None, true, &[]),
545            ("T002", SETUP, None, true, None, false, &[]),
546            ("T003", SETUP, None, true, None, false, &[]),
547            ("T004", SETUP, None, false, None, false, &[]),
548        ]);
549        let (s, _) = schedule(&p);
550        assert_eq!(
551            states(&s),
552            [
553                ("T001", Done, vec![]),
554                ("T002", Ready, vec![]),
555                ("T003", Ready, vec![]),
556                ("T004", Blocked, vec!["T002", "T003"]),
557            ]
558        );
559    }
560
561    #[test]
562    fn tests_subsection_comes_before_implementation() {
563        let p = parsed(&[
564            (
565                "T001",
566                US1,
567                Some("Tests for User Story 1"),
568                true,
569                Some("US1"),
570                false,
571                &[],
572            ),
573            (
574                "T002",
575                US1,
576                Some("Implementation for User Story 1"),
577                true,
578                Some("US1"),
579                false,
580                &[],
581            ),
582        ]);
583        let (s, _) = schedule(&p);
584        assert_eq!(states(&s)[1], ("T002", Blocked, vec!["T001"]));
585    }
586
587    #[test]
588    fn explicit_dependency_crosses_stories() {
589        let p = parsed(&[
590            ("T001", US1, None, false, Some("US1"), false, &[]),
591            ("T002", US2, None, false, Some("US2"), false, &["T001"]),
592        ]);
593        let (s, _) = schedule(&p);
594        assert_eq!(states(&s)[1], ("T002", Blocked, vec!["T001"]));
595        assert_eq!(s.tasks[1].depends_on[0].kind, DependencyKind::Explicit);
596    }
597
598    #[test]
599    fn declared_mode_keeps_phase_order_but_drops_structure_within_a_phase() {
600        let p = parsed_in(
601            DependencyMode::Declared,
602            &[
603                ("T001", SETUP, None, false, None, true, &[]),
604                ("T002", SETUP, None, false, None, false, &["T001"]),
605                ("T003", SETUP, None, true, None, false, &["T001"]),
606                (
607                    "T004",
608                    US1,
609                    Some("Tests"),
610                    true,
611                    Some("US1"),
612                    false,
613                    &["T002"],
614                ),
615                (
616                    "T005",
617                    US1,
618                    Some("Implementation"),
619                    true,
620                    Some("US1"),
621                    false,
622                    &[],
623                ),
624            ],
625        );
626        let (s, d) = schedule(&p);
627        assert!(d.is_empty());
628        assert_eq!(
629            states(&s),
630            [
631                ("T001", Done, vec![]),
632                ("T002", Ready, vec![]),
633                ("T003", Ready, vec![]),
634                ("T004", Blocked, vec!["T002", "T003"]),
635                ("T005", Blocked, vec!["T002", "T003"]),
636            ]
637        );
638    }
639
640    #[test]
641    fn dangling_reference_is_an_error_and_blocks() {
642        let p = parsed(&[("T001", SETUP, None, false, None, false, &["T099"])]);
643        let (s, d) = schedule(&p);
644        assert_eq!(d[0].code, "graph.dangling");
645        assert_eq!(d[0].line, Some(1));
646        assert_eq!(states(&s)[0], ("T001", Blocked, vec!["T099"]));
647        assert!(s.tasks[0].depends_on[0].missing);
648    }
649
650    #[test]
651    fn cycles_and_self_references_are_errors_and_never_ready() {
652        // T002 waits on T001 structurally; T001 explicitly waits on T002.
653        let p = parsed(&[
654            ("T001", SETUP, None, false, None, false, &["T002"]),
655            ("T002", SETUP, None, false, None, true, &[]),
656            ("T003", POLISH, None, false, None, false, &["T003"]),
657        ]);
658        let (s, d) = schedule(&p);
659        let codes: Vec<_> = d
660            .iter()
661            .map(|d| (d.code.as_str(), d.message.as_str()))
662            .collect();
663        assert_eq!(
664            codes,
665            [
666                ("graph.cycle", "dependency cycle: T001 → T002"),
667                ("graph.cycle", "dependency cycle: T003"),
668            ]
669        );
670        assert_eq!(s.tasks[0].state, Blocked);
671        assert_eq!(s.tasks[2].state, Blocked);
672    }
673
674    mod properties {
675        use super::*;
676        use proptest::prelude::*;
677
678        /// Owned form of [`Spec`] while generating.
679        type OwnedSpec = (
680            String,
681            &'static str,
682            Option<String>,
683            bool,
684            Option<&'static str>,
685            bool,
686            Vec<String>,
687        );
688
689        const PHASES: [&str; 6] = [SETUP, FOUND, US1, US2, "Phase 6: Story notes", POLISH];
690
691        /// Random task lists: phases in template order, subsections, `[P]`,
692        /// done flags, and explicit references only to earlier tasks.
693        fn task_lists() -> impl Strategy<Value = ParsedTasks> {
694            prop::collection::vec(
695                (
696                    0..PHASES.len(),
697                    0..3usize,
698                    any::<bool>(),
699                    any::<bool>(),
700                    prop::option::of(0..64usize),
701                ),
702                1..40,
703            )
704            .prop_map(|mut rows| {
705                rows.sort_by_key(|r| (r.0, r.1));
706                let ids: Vec<String> = (1..=rows.len()).map(|n| format!("T{n:03}")).collect();
707                let spec: Vec<OwnedSpec> = rows
708                    .iter()
709                    .enumerate()
710                    .map(|(i, &(ph, sub, par, done, back))| {
711                        let story = match ph {
712                            2 => Some("US1"),
713                            3 => Some("US2"),
714                            _ => None,
715                        };
716                        let deps = back
717                            .filter(|_| i > 0)
718                            .map(|b| vec![ids[b % i].clone()])
719                            .unwrap_or_default();
720                        (
721                            ids[i].clone(),
722                            PHASES[ph],
723                            Some(format!("S{sub}")),
724                            par,
725                            story,
726                            done,
727                            deps,
728                        )
729                    })
730                    .collect();
731                let owned: Vec<Vec<&str>> = spec
732                    .iter()
733                    .map(|r| r.6.iter().map(String::as_str).collect())
734                    .collect();
735                let rows: Vec<Spec<'_>> = spec
736                    .iter()
737                    .zip(&owned)
738                    .map(|(r, d)| {
739                        (
740                            r.0.as_str(),
741                            r.1,
742                            r.2.as_deref(),
743                            r.3,
744                            r.4,
745                            r.5,
746                            d.as_slice(),
747                        )
748                    })
749                    .collect();
750                parsed(&rows)
751            })
752        }
753
754        proptest! {
755            #[test]
756            fn ready_means_every_dependency_is_done(p in task_lists()) {
757                let (s, _) = schedule(&p);
758                let done: HashMap<&str, bool> = p.tasks.iter().map(|t| (t.id.as_str(), t.done)).collect();
759                for t in &s.tasks {
760                    if t.state == Ready {
761                        prop_assert!(t.depends_on.iter().all(|d| done[d.id.as_str()]));
762                    }
763                }
764            }
765
766            #[test]
767            fn open_tasks_with_done_dependencies_are_ready(p in task_lists()) {
768                let (s, _) = schedule(&p);
769                let done: HashMap<&str, bool> = p.tasks.iter().map(|t| (t.id.as_str(), t.done)).collect();
770                for (t, task) in s.tasks.iter().zip(&p.tasks) {
771                    if !task.done && t.depends_on.iter().all(|d| done[d.id.as_str()]) {
772                        prop_assert_eq!(t.state, Ready);
773                    }
774                }
775            }
776
777            #[test]
778            fn stories_never_depend_structurally_on_each_other(p in task_lists()) {
779                let (s, _) = schedule(&p);
780                let story: HashMap<&str, Option<&str>> =
781                    p.tasks.iter().map(|t| (t.id.as_str(), t.story.as_deref())).collect();
782                for t in &s.tasks {
783                    for d in t.depends_on.iter().filter(|d| d.kind == DependencyKind::Structural) {
784                        if let (Some(a), Some(b)) = (story[t.id.as_str()], story[d.id.as_str()]) {
785                            prop_assert_eq!(a, b);
786                        }
787                    }
788                }
789            }
790
791            #[test]
792            fn backward_references_never_create_cycles(p in task_lists()) {
793                let (s, d) = schedule(&p);
794                prop_assert!(d.is_empty(), "{:?}", d);
795                prop_assert_eq!(s.totals.done + s.totals.ready + s.totals.blocked, p.tasks.len());
796            }
797        }
798    }
799}