lisette_semantics/module_graph/
mod.rs

1pub mod kahn;
2
3use rustc_hash::{FxHashMap as HashMap, FxHashSet as HashSet};
4
5use deps::TypedefLocator;
6use syntax::ast::{ImportAlias, Span};
7use syntax::program::File;
8
9use crate::diagnostics::{emit_for_declaration_status, emit_for_locator_result};
10use crate::loader as semantics_loader;
11use crate::loader::Loader;
12use crate::store::Store;
13use diagnostics::LocalSink;
14
15pub type ModuleId = String;
16
17#[derive(Debug)]
18pub struct ModuleGraphResult {
19    pub order: Vec<ModuleId>,
20    pub cycles: Vec<Vec<ModuleId>>,
21    pub files: HashMap<ModuleId, Vec<File>>,
22    /// Direct dependencies of each module (module_id -> set of dependency module_ids).
23    /// Used for transitive cache invalidation.
24    pub edges: HashMap<ModuleId, HashSet<ModuleId>>,
25    /// `go:` modules that are only ever blank-imported in the visited file set.
26    pub link_only_modules: HashSet<ModuleId>,
27}
28
29pub fn build_module_graph(
30    store: &mut Store,
31    loader: Option<&dyn Loader>,
32    entry_module: &str,
33    sink: &LocalSink,
34    standalone_mode: bool,
35    locator: &TypedefLocator,
36) -> ModuleGraphResult {
37    let mut edges: HashMap<ModuleId, HashSet<ModuleId>> = HashMap::default();
38    let mut to_visit = vec![entry_module.to_string()];
39    let mut visited: HashSet<ModuleId> = HashSet::default();
40    let mut files: HashMap<ModuleId, Vec<File>> = HashMap::default();
41    let mut import_spans: HashMap<ModuleId, Span> = HashMap::default();
42    let mut blank_tracker = BlankTracker::default();
43
44    while !to_visit.is_empty() {
45        let drained: Vec<ModuleId> = std::mem::take(&mut to_visit);
46        let mut batch: Vec<ModuleId> = Vec::with_capacity(drained.len());
47        for module_id in drained {
48            if visited.insert(module_id.clone()) {
49                batch.push(module_id);
50            }
51        }
52        if batch.is_empty() {
53            continue;
54        }
55
56        batch.sort();
57
58        let mut parsed = batch_parse_modules(&batch, store, loader, sink);
59
60        for module_id in &batch {
61            let module_files = parsed.remove(module_id).unwrap_or_default();
62            let file_imports: Vec<_> = if !module_files.is_empty() {
63                module_files.iter().flat_map(|f| f.imports()).collect()
64            } else if let Some(module) = store.get_module(module_id) {
65                module.all_imports()
66            } else {
67                Vec::new()
68            };
69            let imports_with_spans = process_file_imports(
70                file_imports,
71                sink,
72                standalone_mode,
73                locator,
74                &mut blank_tracker,
75            );
76
77            let module_exists = !module_files.is_empty()
78                || store.has(module_id)
79                || module_id == entry_module
80                || module_id.starts_with("go:");
81
82            if !module_exists {
83                if let Some(span) = import_spans.get(module_id) {
84                    let is_go_stdlib =
85                        stdlib::get_go_stdlib_typedef(module_id, locator.target()).is_some();
86
87                    let src_prefix_hint = module_id
88                        .strip_prefix("src/")
89                        .filter(|stripped| {
90                            loader.is_some_and(|fs| !fs.scan_folder(stripped).is_empty())
91                        })
92                        .map(String::from);
93
94                    sink.push(diagnostics::module_graph::module_not_found(
95                        module_id,
96                        *span,
97                        is_go_stdlib,
98                        standalone_mode,
99                        src_prefix_hint,
100                    ));
101                }
102                continue;
103            }
104
105            files.insert(module_id.clone(), module_files);
106
107            let imports: HashSet<_> = imports_with_spans.keys().cloned().collect();
108
109            for (import, span) in imports_with_spans {
110                if !visited.contains(&import) {
111                    to_visit.push(import.clone());
112                }
113                import_spans.entry(import).or_insert(span);
114            }
115
116            edges.insert(module_id.clone(), imports);
117        }
118    }
119
120    let (order, cycles) = kahn::topological_sort(&edges);
121
122    ModuleGraphResult {
123        order,
124        cycles,
125        files,
126        edges,
127        link_only_modules: blank_tracker.into_link_only_modules(),
128    }
129}
130
131#[derive(Clone, Copy)]
132enum SeenLookup {
133    OkBlank,
134    OkNonBlank,
135    Errored,
136}
137
138#[derive(Default)]
139struct BlankTracker {
140    blank: HashSet<ModuleId>,
141    non_blank: HashSet<ModuleId>,
142}
143
144impl BlankTracker {
145    fn record_blank(&mut self, module_id: &str) {
146        self.blank.insert(module_id.to_string());
147    }
148
149    fn record_non_blank(&mut self, module_id: &str) {
150        self.non_blank.insert(module_id.to_string());
151    }
152
153    fn into_link_only_modules(self) -> HashSet<ModuleId> {
154        self.blank.difference(&self.non_blank).cloned().collect()
155    }
156}
157
158struct ParseJob {
159    module_id: ModuleId,
160    file_id: u32,
161    filename: String,
162    display_path: String,
163    source: String,
164}
165
166fn batch_parse_modules(
167    modules: &[ModuleId],
168    store: &Store,
169    loader: Option<&dyn Loader>,
170    sink: &LocalSink,
171) -> HashMap<ModuleId, Vec<File>> {
172    let Some(fs) = loader else {
173        return HashMap::default();
174    };
175
176    let mut jobs: Vec<ParseJob> = Vec::new();
177    for module_id in modules {
178        if store.has(module_id) {
179            continue;
180        }
181        let mut entries: Vec<(String, semantics_loader::FileContent)> =
182            fs.scan_folder(module_id).into_iter().collect();
183        entries.sort_by(|a, b| a.0.cmp(&b.0));
184        for (filename, content) in entries {
185            if filename.ends_with("_test.lis") {
186                sink.push(diagnostics::module_graph::test_file_not_supported(
187                    &content.display_path,
188                ));
189                continue;
190            }
191            let file_id = store.new_file_id();
192            jobs.push(ParseJob {
193                module_id: module_id.clone(),
194                file_id,
195                filename,
196                display_path: content.display_path,
197                source: content.source,
198            });
199        }
200    }
201
202    const PARALLEL_THRESHOLD: usize = 4;
203    let parsed: Vec<(ModuleId, File, Vec<syntax::ParseError>)> = if jobs.len() < PARALLEL_THRESHOLD
204    {
205        jobs.into_iter().map(parse_one).collect()
206    } else {
207        use rayon::prelude::*;
208        jobs.into_par_iter().map(parse_one).collect()
209    };
210
211    let mut grouped: HashMap<ModuleId, Vec<File>> = HashMap::default();
212    for (module_id, file, errors) in parsed {
213        sink.extend_parse_errors(errors);
214        grouped.entry(module_id).or_default().push(file);
215    }
216    grouped
217}
218
219fn parse_one(job: ParseJob) -> (ModuleId, File, Vec<syntax::ParseError>) {
220    let result = syntax::build_ast(&job.source, job.file_id);
221    let file = File::new(
222        &job.module_id,
223        &job.filename,
224        &job.display_path,
225        &job.source,
226        result.ast,
227        job.file_id,
228    );
229    (job.module_id, file, result.errors)
230}
231
232fn process_file_imports(
233    file_imports: Vec<syntax::program::FileImport>,
234    sink: &LocalSink,
235    standalone_mode: bool,
236    locator: &TypedefLocator,
237    blank_tracker: &mut BlankTracker,
238) -> HashMap<ModuleId, Span> {
239    let mut imports = HashMap::default();
240    let mut seen_go_imports: HashMap<String, SeenLookup> = HashMap::default();
241
242    for file_import in file_imports {
243        if file_import.name == "prelude" {
244            sink.push(diagnostics::module_graph::cannot_import_prelude(
245                file_import.span,
246            ));
247            continue;
248        }
249
250        if let Some(go_pkg) = file_import.name.strip_prefix("go:") {
251            let is_blank = matches!(file_import.alias, Some(ImportAlias::Blank(_)));
252
253            let prior = seen_go_imports.get(file_import.name.as_str()).copied();
254            let needs_lookup = match (prior, is_blank) {
255                (None, _) => true,
256                (Some(SeenLookup::Errored), _) => false,
257                (Some(SeenLookup::OkNonBlank), _) => false,
258                (Some(SeenLookup::OkBlank), true) => false,
259                (Some(SeenLookup::OkBlank), false) => true,
260            };
261
262            if !needs_lookup {
263                if matches!(prior, Some(SeenLookup::OkBlank | SeenLookup::OkNonBlank)) {
264                    let module_key = file_import.name.to_string();
265                    if is_blank {
266                        blank_tracker.record_blank(&module_key);
267                    } else {
268                        blank_tracker.record_non_blank(&module_key);
269                    }
270                    imports.insert(module_key, file_import.name_span);
271                }
272                continue;
273            }
274
275            let ok = if is_blank {
276                let status = locator.validate_declaration(go_pkg);
277                emit_for_declaration_status(
278                    &status,
279                    &file_import.name,
280                    go_pkg,
281                    file_import.name_span,
282                    locator.target(),
283                    standalone_mode,
284                    sink,
285                )
286            } else {
287                let result = locator.find_typedef_content(go_pkg);
288                emit_for_locator_result(
289                    &result,
290                    &file_import.name,
291                    go_pkg,
292                    Some(file_import.name_span),
293                    locator.target(),
294                    standalone_mode,
295                    sink,
296                )
297            };
298
299            seen_go_imports.insert(
300                file_import.name.to_string(),
301                if !ok {
302                    SeenLookup::Errored
303                } else if is_blank {
304                    SeenLookup::OkBlank
305                } else {
306                    SeenLookup::OkNonBlank
307                },
308            );
309            if ok {
310                let module_key = file_import.name.to_string();
311                if is_blank {
312                    blank_tracker.record_blank(&module_key);
313                } else {
314                    blank_tracker.record_non_blank(&module_key);
315                }
316                imports.insert(module_key, file_import.name_span);
317            }
318            continue;
319        }
320
321        let blank_span = match &file_import.alias {
322            Some(ImportAlias::Blank(span)) => Some(*span),
323            _ => None,
324        };
325        let is_dotted = file_import.name.contains('.');
326
327        if is_dotted && locator.is_declared_go_dep(&file_import.name) {
328            sink.push(diagnostics::module_graph::missing_go_prefix(
329                &file_import.name,
330                file_import.name_span,
331                blank_span.is_some(),
332            ));
333            continue;
334        }
335
336        if is_dotted {
337            sink.push(diagnostics::module_graph::invalid_module_path(
338                &file_import.name,
339                file_import.name_span,
340            ));
341        }
342        if let Some(span) = blank_span {
343            sink.push(diagnostics::infer::blank_import_non_go(span));
344        }
345        if is_dotted || blank_span.is_some() {
346            continue;
347        }
348
349        imports
350            .entry(file_import.name.to_string())
351            .or_insert(file_import.name_span);
352    }
353
354    imports
355}
lisette_semantics/module_graph/mod.rs

lisette_semantics/module_graph/
mod.rs
