expectation_graph/
lib.rs

1//! Analysis of a suite as a graph of expectations:
2//!
3//! - [`precedence`]: the override DAG (exceptions and what they override),
4//! - [`conflict`]: pairs of expectations that can't both hold, settled or not,
5//! - [`flow`]: the DAG of what leads to what, from the Background,
6//! - [`semantics`]: stepping a state through an action, shared with story planning.
7
8pub mod conflict;
9pub mod export;
10pub mod flow;
11pub mod precedence;
12pub mod semantics;
13
14pub use conflict::{Conflict, Kind as ConflictKind};
15pub use flow::{Flow, Limits, Node, Route};
16pub use precedence::Precedence;
17
18use expectation_model::{Condition, Diagnostic, ExpId, FeatureId, SectionId, Suite};
19
20pub struct Analysis {
21    pub precedence: Precedence,
22    pub conflicts: Vec<Conflict>,
23    pub flow: Flow,
24    /// Per section: the expectations that lead from its parent's start into its own.
25    pub section_routes: Vec<Option<Route>>,
26    pub diagnostics: Vec<Diagnostic>,
27}
28
29impl Analysis {
30    pub fn has_errors(&self) -> bool {
31        expectation_model::diagnostic::has_errors(&self.diagnostics)
32    }
33
34    /// Conflicts an override settles: the suite's exceptions.
35    pub fn exceptions(&self) -> impl Iterator<Item = &Conflict> {
36        self.conflicts.iter().filter(|c| c.winner.is_some())
37    }
38
39    /// Features in dependency order: after the features their expectations follow on from
40    /// (flow edges) or make exceptions to (overrides). Among those ready, the earliest in the
41    /// flow first, then the most depended on, then declaration order. Cycles fall back to
42    /// declaration order.
43    pub fn feature_order(&self, suite: &Suite) -> Vec<FeatureId> {
44        let n = suite.features.len();
45        let feature = |e: ExpId| suite.exp(e).feature.0 as usize;
46        let mut deps = vec![std::collections::BTreeSet::new(); n];
47        for (p, c) in &self.flow.edges {
48            if let Node::Exp(p) = p {
49                deps[feature(*c)].insert(feature(*p));
50            }
51        }
52        for (w, l) in &self.precedence.declared {
53            deps[feature(*w)].insert(feature(*l));
54        }
55        for (f, d) in deps.iter_mut().enumerate() {
56            d.remove(&f);
57        }
58        let dependents: Vec<usize> = (0..n).map(|f| deps.iter().filter(|d| d.contains(&f)).count()).collect();
59        let earliest: Vec<u32> = suite
60            .features
61            .iter()
62            .map(|f| f.expectations.iter().filter_map(|e| self.flow.level[e.0 as usize]).min().unwrap_or(u32::MAX))
63            .collect();
64        let key = |f: usize| (earliest[f], std::cmp::Reverse(dependents[f]), f);
65        let mut placed = vec![false; n];
66        let mut order = vec![];
67        while order.len() < n {
68            let ready = (0..n).filter(|&f| !placed[f] && deps[f].iter().all(|&d| placed[d])).min_by_key(|&f| key(f));
69            let next = ready.unwrap_or_else(|| (0..n).find(|&f| !placed[f]).unwrap());
70            placed[next] = true;
71            order.push(FeatureId(next as u32));
72        }
73        order
74    }
75}
76
77/// The states searches start from: the start of each section with features or stories in
78/// it, and each scenario's arranged start. (A section that only groups others has nothing that
79/// starts from it; searching from an empty root would mean searching every state there is.)
80pub fn roots(suite: &Suite) -> Vec<(Condition, SectionId)> {
81    let mut roots: Vec<(Condition, SectionId)> = vec![];
82    let starts = suite
83        .sections
84        .iter()
85        .filter(|s| !s.features.is_empty() || !s.stories.is_empty())
86        .map(|s| (s.start.clone(), s.id));
87    let scenarios = suite.stories.iter().flat_map(|story| {
88        let start = &suite.section(story.section).start;
89        story.scenarios.iter().map(move |sc| (start.overlay(&sc.given), story.section))
90    });
91    for r in starts.chain(scenarios) {
92        if !roots.contains(&r) {
93            roots.push(r);
94        }
95    }
96    roots
97}
98
99/// For each section, how its setup is reached from its parent's start: the chain of
100/// expectations that gets there. `None` for the root, for a section that adds no setup, and
101/// for one nothing leads into.
102pub fn section_routes(suite: &Suite, prec: &Precedence, limits: Limits) -> Vec<Option<Route>> {
103    suite
104        .sections
105        .iter()
106        .map(|s| {
107            let parent = s.parent.map(|p| &suite.section(p).start)?;
108            if s.setup.is_unconstrained() || parent.implies(&s.start) {
109                return None;
110            }
111            flow::route_to(suite, prec, parent, &s.start, limits)
112        })
113        .collect()
114}
115
116pub fn analyze(suite: &Suite) -> Analysis {
117    analyze_with(suite, Limits::default())
118}
119
120pub fn analyze_with(suite: &Suite, limits: Limits) -> Analysis {
121    let (precedence, mut diagnostics) = precedence::build(suite);
122    let conflicts = conflict::detect(suite, &precedence);
123    diagnostics.extend(conflict::diagnose(suite, &precedence, &conflicts));
124    let flow = flow::explore(suite, &precedence, &roots(suite), limits);
125    if !flow.truncated {
126        for e in suite.expectations.iter().filter(|e| flow.level[e.id.0 as usize].is_none()) {
127            let needs = if e.is_invariant() {
128                suite.describe(&e.given)
129            } else {
130                format!("{}, and then {}", suite.describe(&e.given), suite.describe_trigger(&e.trigger))
131            };
132            diagnostics.push(
133                Diagnostic::warning("unreachable", format!("«{}» can never happen, starting from any section's setup", e.name))
134                    .at(&e.span, format!("it needs {needs}"))
135                    .help("no chain of expectations leads there; check the Background, or add the expectation that gets there"),
136            );
137        }
138    }
139    let section_routes = section_routes(suite, &precedence, limits);
140    for (s, route) in suite.sections.iter().zip(&section_routes) {
141        let Some(parent) = s.parent.map(|p| suite.section(p)) else { continue };
142        // From a parent with no setup there's nothing to route from: getting there is starting
143        // the program, which happens outside the suite.
144        let from_somewhere = !parent.start.is_unconstrained();
145        if from_somewhere && route.is_none() && !s.setup.is_unconstrained() && !parent.start.implies(&s.start) {
146            let span = s.setup_steps.first().map(|t| &t.span).or(s.span.as_ref());
147            let mut d =
148                Diagnostic::warning("no-way-in", format!("nothing leads from «{}» into «{}»", parent.name, s.name))
149                    .note_that(format!("«{}» starts with {}", s.name, suite.describe(&parent.start.unproven(&s.start))))
150                    .help("add the expectation that gets there, so the docs can say how to get to this section");
151            if let Some(span) = span {
152                d = d.at(span, "");
153            }
154            diagnostics.push(d);
155        }
156    }
157    Analysis { precedence, conflicts, flow, section_routes, diagnostics }
158}
159
160#[cfg(test)]
161mod tests {
162    use super::*;
163
164    const VOCAB: &str = "
165Vocabulary:
166  State: the kettle is off | heating | dry
167  State: the dial is 0..100 %
168  State: the child lock is on | off
169  State: the help screen is shown | hidden
170  Event: the user presses reset
171  Event: the user presses help
172  Event: the water runs out
173
174Background:
175  Given the kettle is off
176  And the dial is 0 %
177  And the child lock is off
178  And the help screen is hidden
179";
180
181    const HEATING: &str = "
182Feature: Heating
183  Expectation: Turning the dial up starts the kettle
184    Given the kettle is off
185    When the dial is above 55 %
186    Then the kettle is heating
187
188  Expectation: The child lock holds the kettle
189    Given the kettle is off
190    And the child lock is on
191    When the dial is above 70 %
192    Then the kettle is off
193
194  Expectation: Running dry stops the kettle
195    Given the kettle is heating
196    When the water runs out
197    Then the kettle is dry
198
199  Expectation: Reset turns the kettle off
200    When the user presses reset
201    Then the kettle is off
202";
203
204    fn suite(extra: &str) -> Suite {
205        let src = format!("{VOCAB}{HEATING}{extra}");
206        let l = expectation_language::load_sources("t", &[("t.expect", &src)]);
207        assert!(!l.has_errors(), "{}", l.render_diagnostics());
208        l.suite
209    }
210
211    fn named(s: &Suite, name: &str) -> ExpId {
212        s.expectations.iter().find(|e| e.name == name).unwrap().id
213    }
214
215    #[test]
216    fn finds_an_outcome_conflict_and_where_it_happens() {
217        let s = suite("");
218        let a = analyze(&s);
219        let [c] = &a.conflicts[..] else { panic!("{:?}", a.conflicts) };
220        assert_eq!((c.a, c.b), (named(&s, "Turning the dial up starts the kettle"), named(&s, "The child lock holds the kettle")));
221        assert_eq!(c.winner, None);
222        // The triggers overlap above 70 %, and both Givens hold with the child lock on.
223        assert_eq!(s.describe_trigger(&c.trigger), "the dial is above 70 %");
224        assert!(s.describe(&c.situation).contains("the child lock is on"));
225        let d = a.diagnostics.iter().find(|d| d.code == "conflict").unwrap();
226        assert!(d.help.as_ref().unwrap().contains("«The child lock holds the kettle» is the more specific"), "{:?}", d.help);
227    }
228
229    #[test]
230    fn an_override_settles_it() {
231        let s = suite("");
232        let src = format!("{VOCAB}{}", HEATING.replace("    Given the kettle is off\n    And the child", "    Overrides: Turning the dial up starts the kettle\n    Given the kettle is off\n    And the child"));
233        let l = expectation_language::load_sources("t", &[("t.expect", &src)]);
234        let a = analyze(&l.suite);
235        assert!(!a.has_errors(), "{}", expectation_model::diagnostic::render_all(&a.diagnostics, &l.suite.sources));
236        assert_eq!(a.exceptions().count(), 1);
237        assert_eq!(a.exceptions().next().unwrap().winner, Some(named(&s, "The child lock holds the kettle")));
238    }
239
240    #[test]
241    fn disjoint_givens_or_different_triggers_dont_conflict() {
242        let s = suite(
243            "
244Feature: More
245  Expectation: Help while heating
246    Given the kettle is heating
247    When the user presses help
248    Then the help screen is shown
249  Expectation: Help is ignored while off
250    Given the kettle is off
251    When the user presses help
252    Then the help screen is hidden
253",
254        );
255        let a = analyze(&s);
256        assert_eq!(a.conflicts.len(), 1, "only the child lock conflict: {:?}", a.conflicts);
257    }
258
259    #[test]
260    fn invariant_conflicts() {
261        let s = suite(
262            "
263Feature: Help
264  Expectation: Help toggles on
265    Given the help screen is hidden
266    When the user presses help
267    Then the help screen is shown
268  Expectation: No help while heating
269    Given the kettle is heating
270    Then the help screen is hidden
271",
272        );
273        let a = analyze(&s);
274        let c = a.conflicts.iter().find(|c| c.kind == ConflictKind::Invariant).expect("help toggles while heating");
275        assert_eq!((c.a, c.b), (named(&s, "Help toggles on"), named(&s, "No help while heating")));
276    }
277
278    #[test]
279    fn override_cycles_are_errors() {
280        let src = format!(
281            "{VOCAB}
282Feature: F
283  Expectation: A
284    Overrides: B
285    When the user presses help
286    Then the help screen is shown
287  Expectation: B
288    Overrides: A
289    When the user presses help
290    Then the help screen is hidden
291"
292        );
293        let l = expectation_language::load_sources("t", &[("t.expect", &src)]);
294        let a = analyze(&l.suite);
295        assert!(a.diagnostics.iter().any(|d| d.code == "override-cycle"));
296    }
297
298    #[test]
299    fn flow_levels_edges_and_routes() {
300        let s = suite("");
301        let a = analyze(&s);
302        let start = named(&s, "Turning the dial up starts the kettle");
303        let dry = named(&s, "Running dry stops the kettle");
304        let reset = named(&s, "Reset turns the kettle off");
305        let lock = named(&s, "The child lock holds the kettle");
306        let level = |e: ExpId| a.flow.level[e.0 as usize];
307        assert_eq!(level(start), Some(0));
308        assert_eq!(level(reset), Some(0));
309        assert_eq!(level(dry), Some(1));
310        assert!(a.flow.edges.contains(&(Node::Start, start)));
311        assert!(a.flow.edges.contains(&(Node::Exp(start), dry)));
312        // Nothing turns the child lock on, so its exception can't happen from the Background.
313        assert_eq!(level(lock), None);
314        assert!(a.diagnostics.iter().any(|d| d.code == "unreachable"));
315        // Levels grow along every edge: a DAG, even though reset loops back to the start.
316        for (p, c) in &a.flow.edges {
317            if let Node::Exp(p) = p {
318                assert!(level(*p) < level(*c));
319            }
320        }
321        let route = a.flow.routes[dry.0 as usize].as_ref().unwrap();
322        assert_eq!(route.steps, vec![start, dry]);
323    }
324
325    #[test]
326    fn relative_thens_conflict_and_sections_have_a_way_in() {
327        let root = "Vocabulary:\n State: the tool is none | PEN\n State: the drawing has 0..100 shapes\n Event: the user presses PEN\n Event: the user clicks the canvas\nBackground:\n Given the tool is none\n And the drawing has 0 shapes\nFeature: Tools\n Expectation: PEN picks the pen\n  Given the tool is none\n  When the user presses PEN\n  Then the tool is PEN\n";
328        let drawing = "Background:\n Given the tool is PEN\nFeature: Shapes\n Expectation: A click adds a shape\n  Given the tool is PEN\n  When the user clicks the canvas\n  Then the drawing goes up by 1\n Expectation: A click adds two\n  Given the tool is PEN\n  When the user clicks the canvas\n  Then the drawing goes up by 2\n";
329        let l = expectation_language::load_sources("t", &[("root.expect", root), ("drawing/w.expect", drawing)]);
330        assert!(!l.has_errors(), "{}", l.render_diagnostics());
331        let a = analyze(&l.suite);
332        let [c] = &a.conflicts[..] else { panic!("{:?}", a.conflicts) };
333        assert_eq!((c.a, c.b), (ExpId(1), ExpId(2)));
334        // From the root's start, pressing PEN gets into the drawing section.
335        let route = a.section_routes[1].as_ref().expect("a way into drawing");
336        assert_eq!(route.steps, vec![ExpId(0)]);
337        assert!(!a.diagnostics.iter().any(|d| d.code == "no-way-in"));
338    }
339
340    #[test]
341    fn mermaid_mentions_everything() {
342        let s = suite("");
343        let a = analyze(&s);
344        let m = export::mermaid(&s, &a, &|_| None);
345        assert!(m.contains("start --> e0"));
346        assert!(m.contains("<-. conflict .->"));
347        assert!(m.contains("class e1 unreachable"));
348        assert!(export::dot(&s, &a).contains("color=red"));
349    }
350}
expectation_graph/lib.rs

expectation_graph/
lib.rs
