lisette_semantics/checker/infer/validation/
const_cycles.rs

1use rustc_hash::{FxHashMap as HashMap, FxHashSet as HashSet};
2
3use ecow::EcoString;
4use syntax::ast::{Expression, Span};
5
6use crate::checker::TaskState;
7use crate::store::Store;
8
9struct ConstEntry<'a> {
10    name: &'a EcoString,
11    name_span: Span,
12    body: &'a Expression,
13}
14
15impl TaskState<'_> {
16    pub fn check_const_cycles(&mut self, store: &Store, items_per_file: &[&[Expression]]) {
17        let module_const_names_empty = store
18            .get_module(&self.cursor.module_id)
19            .is_some_and(|m| m.const_names.is_empty());
20        if module_const_names_empty {
21            return;
22        }
23
24        let mut consts: Vec<ConstEntry<'_>> = Vec::new();
25        for items in items_per_file {
26            for item in *items {
27                if let Expression::Const {
28                    identifier,
29                    identifier_span,
30                    expression,
31                    ..
32                } = item
33                {
34                    consts.push(ConstEntry {
35                        name: identifier,
36                        name_span: *identifier_span,
37                        body: expression,
38                    });
39                }
40            }
41        }
42
43        if consts.is_empty() {
44            return;
45        }
46
47        let const_names: HashSet<&EcoString> = consts.iter().map(|c| c.name).collect();
48
49        let mut deps: HashMap<&EcoString, Vec<&EcoString>> = HashMap::default();
50        let mut spans: HashMap<&EcoString, Span> = HashMap::default();
51        for entry in &consts {
52            let mut refs: Vec<&EcoString> = Vec::new();
53            collect_const_refs(entry.body, &const_names, &mut refs);
54            refs.sort();
55            refs.dedup();
56            deps.insert(entry.name, refs);
57            spans.insert(entry.name, entry.name_span);
58        }
59
60        let mut color: HashMap<&EcoString, Color> = HashMap::default();
61        for entry in &consts {
62            color.insert(entry.name, Color::White);
63        }
64
65        let mut reported: HashSet<&EcoString> = HashSet::default();
66        for entry in &consts {
67            if color[&entry.name] == Color::White {
68                let mut path: Vec<&EcoString> = Vec::new();
69                dfs(
70                    entry.name,
71                    &deps,
72                    &spans,
73                    &mut color,
74                    &mut path,
75                    &mut reported,
76                    self.sink,
77                );
78            }
79        }
80    }
81}
82
83#[derive(PartialEq, Eq, Clone, Copy)]
84enum Color {
85    White,
86    Gray,
87    Black,
88}
89
90fn dfs<'a>(
91    node: &'a EcoString,
92    deps: &HashMap<&'a EcoString, Vec<&'a EcoString>>,
93    spans: &HashMap<&'a EcoString, Span>,
94    color: &mut HashMap<&'a EcoString, Color>,
95    path: &mut Vec<&'a EcoString>,
96    reported: &mut HashSet<&'a EcoString>,
97    sink: &diagnostics::LocalSink,
98) {
99    color.insert(node, Color::Gray);
100    path.push(node);
101
102    if let Some(neighbors) = deps.get(node) {
103        for next in neighbors {
104            match color.get(next).copied().unwrap_or(Color::White) {
105                Color::White => dfs(next, deps, spans, color, path, reported, sink),
106                Color::Gray => {
107                    let start = path.iter().position(|n| *n == *next).unwrap_or(0);
108                    let cycle: Vec<String> = path[start..].iter().map(|n| n.to_string()).collect();
109                    let representative = path[start];
110                    if reported.insert(representative)
111                        && let Some(span) = spans.get(representative)
112                    {
113                        sink.push(diagnostics::infer::const_cycle(&cycle, *span));
114                    }
115                }
116                Color::Black => {}
117            }
118        }
119    }
120
121    path.pop();
122    color.insert(node, Color::Black);
123}
124
125fn collect_const_refs<'a>(
126    expression: &'a Expression,
127    const_names: &HashSet<&'a EcoString>,
128    out: &mut Vec<&'a EcoString>,
129) {
130    if let Expression::Identifier {
131        value, qualified, ..
132    } = expression
133    {
134        if qualified.is_none()
135            && let Some(&name) = const_names.get(value)
136        {
137            out.push(name);
138        }
139        return;
140    }
141    for child in expression.children() {
142        collect_const_refs(child, const_names, out);
143    }
144}
lisette_semantics/checker/infer/validation/const_cycles.rs

lisette_semantics/checker/infer/validation/
const_cycles.rs
