wolf_resolve/
targets.rs

1//! Target binding of modules (spec chapter 7, section 8.5): a module whose extern names are not
2//! declared for a target is not available for it, and neither is a module that imports it.
3
4use std::collections::btree_map::Entry;
5use std::collections::{BTreeMap, BTreeSet, VecDeque};
6
7use wolf_ast::{ExternDeclKind, ItemKind};
8use wolf_diag::{Diagnostic, codes};
9use wolf_span::Span;
10
11use crate::{ModuleInput, Role};
12
13/// The extern facts of one module: the span of its `extern` header and the names each target
14/// block declares.
15struct Externs {
16    header: Span,
17    names: BTreeMap<String, BTreeSet<String>>,
18}
19
20impl Externs {
21    /// The extern names that the block of `target` misses.
22    fn missing(&self, target: &str) -> Vec<String> {
23        let all: BTreeSet<&String> = self.names.values().flatten().collect();
24        let declared = self.names.get(target);
25        all.into_iter()
26            .filter(|n| !declared.is_some_and(|d| d.contains(*n)))
27            .cloned()
28            .collect()
29    }
30}
31
32/// The imports and the `extern` sections of the modules of a program.
33struct Graph {
34    imports: Vec<Vec<usize>>,
35    /// Where each module imports another, for native modules (they have no source of their own).
36    import_spans: BTreeMap<(usize, usize), Span>,
37    externs: BTreeMap<usize, Externs>,
38}
39
40fn graph(modules: &[ModuleInput<'_>]) -> Graph {
41    let index: BTreeMap<&[String], usize> = modules
42        .iter()
43        .enumerate()
44        .map(|(i, m)| (m.path.as_slice(), i))
45        .collect();
46    let mut imports: Vec<Vec<usize>> = vec![Vec::new(); modules.len()];
47    let mut import_spans: BTreeMap<(usize, usize), Span> = BTreeMap::new();
48    let mut externs: BTreeMap<usize, Externs> = BTreeMap::new();
49    for (i, m) in modules.iter().enumerate() {
50        if matches!(m.role, Role::Std | Role::Prelude) {
51            continue;
52        }
53        for section in &m.ast.sections {
54            for item in &section.items {
55                match &item.kind {
56                    ItemKind::Import(import) => {
57                        let path: Vec<String> = import
58                            .path
59                            .segments
60                            .iter()
61                            .map(|s| s.name.clone())
62                            .collect();
63                        if let (Some(j), Some(list)) =
64                            (index.get(path.as_slice()), imports.get_mut(i))
65                        {
66                            list.push(*j);
67                            import_spans.entry((i, *j)).or_insert(import.path.span);
68                        }
69                    }
70                    ItemKind::ExternTarget(block) => {
71                        let e = externs.entry(i).or_insert_with(|| Externs {
72                            header: section.name_span,
73                            names: BTreeMap::new(),
74                        });
75                        let names = e.names.entry(block.target.name.clone()).or_default();
76                        for decl in &block.decls {
77                            let name = match &decl.kind {
78                                ExternDeclKind::Fn(sig) => &sig.name.name,
79                                ExternDeclKind::Type(name) => &name.name,
80                                ExternDeclKind::Struct(_) => continue,
81                            };
82                            names.insert(name.clone());
83                        }
84                    }
85                    _ => {}
86                }
87            }
88        }
89    }
90    Graph {
91        imports,
92        import_spans,
93        externs,
94    }
95}
96
97impl Graph {
98    /// The modules reached from each group of roots in turn, each with the module it was first
99    /// reached from.
100    fn reach(&self, groups: Vec<Vec<usize>>) -> BTreeMap<usize, Option<usize>> {
101        let mut parent: BTreeMap<usize, Option<usize>> = BTreeMap::new();
102        for group in groups {
103            let mut queue: VecDeque<usize> = VecDeque::new();
104            for r in group {
105                if let Entry::Vacant(v) = parent.entry(r) {
106                    v.insert(None);
107                    queue.push_back(r);
108                }
109            }
110            while let Some(i) = queue.pop_front() {
111                for &j in self.imports.get(i).map_or(&[][..], Vec::as_slice) {
112                    if let Entry::Vacant(v) = parent.entry(j) {
113                        v.insert(Some(i));
114                        queue.push_back(j);
115                    }
116                }
117            }
118        }
119        parent
120    }
121}
122
123/// The chain of imports from a root to module `i`, as module paths.
124fn chain(
125    modules: &[ModuleInput<'_>],
126    parent: &BTreeMap<usize, Option<usize>>,
127    i: usize,
128) -> Vec<String> {
129    let path_of = |k: usize| modules.get(k).map(|m| m.path.join(".")).unwrap_or_default();
130    let mut chain = vec![path_of(i)];
131    let mut cur = i;
132    while let Some(Some(p)) = parent.get(&cur) {
133        chain.push(path_of(*p));
134        cur = *p;
135    }
136    chain.reverse();
137    chain
138}
139
140/// E0807 for every module reachable from the modules that `root` selects that has an `extern`
141/// section or is a native module: the VM runs no code of the targets (spec chapter 10,
142/// section 3). `help` says how to run the program on a target instead.
143pub fn check_vm(
144    modules: &[ModuleInput<'_>],
145    root: impl Fn(&ModuleInput<'_>) -> bool,
146    help: &str,
147) -> Vec<Diagnostic> {
148    let g = graph(modules);
149    let roots: Vec<usize> = modules
150        .iter()
151        .enumerate()
152        .filter(|(_, m)| !matches!(m.role, Role::Std | Role::Prelude) && root(m))
153        .map(|(i, _)| i)
154        .collect();
155    let parent = g.reach(vec![roots]);
156    let mut out = Vec::new();
157    for (&i, e) in &g.externs {
158        if !parent.contains_key(&i) {
159            continue;
160        }
161        let chain = chain(modules, &parent, i);
162        let name = modules.get(i).map(|m| m.path.join(".")).unwrap_or_default();
163        let native = modules.get(i).is_some_and(|m| m.role == Role::Native);
164        let mut d = if native {
165            let importer = parent.get(&i).copied().flatten();
166            let mut d = Diagnostic::new(
167                codes::E0807,
168                format!("the native module `{name}` cannot run in the VM"),
169            );
170            if let Some(span) = importer.and_then(|p| g.import_spans.get(&(p, i)).copied()) {
171                d = d.primary(span, "code of the targets is imported here");
172            }
173            d
174        } else {
175            Diagnostic::new(
176                codes::E0807,
177                format!("module `{name}` cannot run in the VM"),
178            )
179            .primary(e.header, "code of the targets is called here")
180        };
181        if chain.len() > 1 {
182            d = d.note(format!("imported through {}", chain.join(" -> ")));
183        }
184        out.push(d.help(help.to_string()));
185    }
186    out
187}
188
189/// E0704 for every module of a build for `target` that is not available for it. `built` says
190/// which modules the build contains; std modules are always available.
191pub fn check_target(
192    modules: &[ModuleInput<'_>],
193    target: &str,
194    built: impl Fn(Role) -> bool,
195) -> Vec<Diagnostic> {
196    let g = graph(modules);
197    let (import_spans, externs) = (&g.import_spans, &g.externs);
198    // The roots of the build and, for each module, the module it was first reached from.
199    let roots: Vec<usize> = modules
200        .iter()
201        .enumerate()
202        .filter(|(_, m)| {
203            matches!(m.role, Role::Entry | Role::Example | Role::Test) && built(m.role)
204        })
205        .map(|(i, _)| i)
206        .collect();
207    // Modules of `src/` that no root imports are built too; they are reached last.
208    let rest: Vec<usize> = modules
209        .iter()
210        .enumerate()
211        .filter(|(_, m)| m.role == Role::Src)
212        .map(|(i, _)| i)
213        .collect();
214    let parent = g.reach(vec![roots, rest]);
215    let mut out = Vec::new();
216    for (&i, e) in externs {
217        if !parent.contains_key(&i) {
218            continue;
219        }
220        let missing = e.missing(target);
221        if missing.is_empty() {
222            continue;
223        }
224        let name = modules.get(i).map(|m| m.path.join(".")).unwrap_or_default();
225        let chain = chain(modules, &parent, i);
226        let bound: Vec<&str> = e
227            .names
228            .keys()
229            .filter(|t| e.missing(t).is_empty())
230            .map(String::as_str)
231            .collect();
232        let list = missing
233            .iter()
234            .map(|n| format!("`{n}`"))
235            .collect::<Vec<_>>()
236            .join(", ");
237        // A native module (spec chapter 6, section 1a) is reported where it is imported.
238        if modules.get(i).is_some_and(|m| m.role == Role::Native) {
239            let importer = parent.get(&i).copied().flatten();
240            let span = importer.and_then(|p| import_spans.get(&(p, i)).copied());
241            let mut d = Diagnostic::new(
242                codes::E0704,
243                format!("the native module `{name}` is not available for `{target}`"),
244            );
245            if let Some(span) = span {
246                d = d.primary(span, format!("no `{target}` code for {list}"));
247            }
248            if chain.len() > 2 {
249                d = d.note(format!("imported through {}", chain.join(" -> ")));
250            }
251            let others = bound
252                .iter()
253                .map(|t| format!("`{t}`"))
254                .collect::<Vec<_>>()
255                .join(" or ");
256            out.push(d.help(format!(
257                "add the `{target}` code of the module, or build for {others}"
258            )));
259            continue;
260        }
261        let mut d = Diagnostic::new(
262            codes::E0704,
263            format!("module `{name}` is not available for `{target}`"),
264        )
265        .primary(e.header, format!("no `{target}` declaration for {list}"));
266        if chain.len() > 1 {
267            d = d.note(format!("imported through {}", chain.join(" -> ")));
268        }
269        d = if bound.is_empty() {
270            d.help(format!("declare {list} in a `{target}` block"))
271        } else {
272            d.help(format!(
273                "declare {list} in a `{target}` block, or build for {}",
274                bound
275                    .iter()
276                    .map(|t| format!("`{t}`"))
277                    .collect::<Vec<_>>()
278                    .join(" or ")
279            ))
280        };
281        out.push(d);
282    }
283    out
284}
wolf_resolve/targets.rs

wolf_resolve/
targets.rs
