chandeliers_san/causality/
mod.rs

1//! Check proper causality (acyclicity of dependencies)
2//!
3//! Most of the hard work is delegated to `graph` for cycle detection
4//! and `depends` for constraint definition.
5//! Here we only need to recurse into the program AST deep enough for
6//! the structures that need to have their dependencies analyzed,
7//! which is done by the `Causality` trait.
8
9use chandeliers_err::EAccum;
10
11use crate::ast;
12use crate::sp::Sp;
13
14pub mod depends;
15pub mod graph;
16
17use depends::Reference;
18use graph::Graph;
19
20/// Sort the internals of `Self` to remove cyclic dependencies and allow
21/// typechecking in the right order.
22pub trait Causality: Sized {
23    /// Rearrange the internal contents in a causally consistent ordering.
24    /// # Errors
25    /// Fails if there is a cycle (including of length 1).
26    fn causality(self, eaccum: &mut EAccum) -> Option<Self>;
27}
28
29impl Causality for ast::decl::Prog {
30    /// Sort the declarations of the program to remove cycles.
31    fn causality(self, eaccum: &mut EAccum) -> Option<Self> {
32        let Self { decls } = self;
33        let mut g = Graph::default();
34        for decl in decls {
35            g.insert(decl.causality(eaccum)?);
36        }
37        let decls = g.scheduling(eaccum)?;
38        Some(Self { decls })
39    }
40}
41
42impl<T: Causality> Causality for Sp<T> {
43    /// Trivial projection.
44    fn causality(self, eaccum: &mut EAccum) -> Option<Self> {
45        self.map(|_, t| t.causality(eaccum)).transpose()
46    }
47}
48
49impl Causality for ast::decl::Decl {
50    /// Trivial projection.
51    fn causality(self, eaccum: &mut EAccum) -> Option<Self> {
52        Some(match self {
53            Self::Node(n) => Self::Node(n.causality(eaccum)?),
54            _ => self,
55        })
56    }
57}
58
59impl Causality for ast::decl::Node {
60    /// Sort the statements of a node to
61    /// - verify that no inputs are redefined
62    /// - verify that all locals and outputs are well-defined
63    /// - ensure that there is no dependency cycle.
64    fn causality(self, eaccum: &mut EAccum) -> Option<Self> {
65        let Self {
66            name,
67            options,
68            inputs,
69            outputs,
70            locals,
71            blocks,
72            deptys,
73            stmts,
74            registers,
75            flips,
76        } = self;
77        let mut g = Graph::default();
78        for i in inputs.t.iter() {
79            g.already_provided(&Reference::LocalVarName(
80                i.t.name.as_ref().map(|_, t| t.repr.t.clone()),
81            ));
82        }
83        for stmt in stmts {
84            g.insert(stmt);
85        }
86        // Define interface
87        for l in locals.t.iter() {
88            let unit = Reference::LocalVarName(l.t.name.as_ref().map(|_, t| t.repr.t.clone()));
89            g.must_provide(eaccum, &unit)?;
90        }
91        for o in outputs.t.iter() {
92            let unit = Reference::LocalVarName(o.t.name.as_ref().map(|_, t| t.repr.t.clone()));
93            g.must_provide(eaccum, &unit)?;
94        }
95        // Sort internals
96        let stmts = g.scheduling(eaccum)?;
97        Some(Self {
98            name,
99            options,
100            inputs,
101            outputs,
102            locals,
103            blocks,
104            deptys,
105            stmts,
106            registers,
107            flips,
108        })
109    }
110}
chandeliers_san/causality/mod.rs

chandeliers_san/causality/
mod.rs
