cpp_code_analysis 0.2.0

The analysis layer of cpp_ls: the preprocessor, symbol scopes, type inference and the semantic checks.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
//! The module graph: which file declares which module, and which files import which modules.
//!
//! # Why this is not the include graph
//!
//! [`crate::graph`] walks `#include`s and carries a **macro environment** along its edges, because inclusion
//! is textual: the includer's `#define`s are in force inside the header. Modules do not work that way. A
//! module unit is compiled on its own, so the importer's macros have no effect on it and its macros have no
//! effect on the importer.
//!
//! That difference is not a refinement of the include walk — it is a reason not to reuse it. An import edge
//! that inherited the importer's macro environment would decide the imported module's `#if` conditions
//! against macros no compiler ever used, and every answer that followed would be confidently wrong. So the
//! module graph resolves names to files and records dependencies, and it deliberately **does not carry a
//! macro environment at all**: there is no field for one, which is the cheapest way to make sure nobody adds
//! one by accident.
//!
//! # What it does carry
//!
//! Two things, and both are needed to answer "what does this edit affect":
//!
//! * **Units** — the files that declare a module, indexed by module name so an `import m;` can be resolved.
//!   A module has exactly one primary interface unit; partitions add more units to the same module.
//! * **Edges** — one per import declaration, in source order, carrying the resolution outcome. Forward edges
//!   answer "what does this file need"; the reverse answer is [`ModuleGraph::importers_of`], which is what a
//!   cache invalidation calls when a module interface changes.
//!
//! # Resolution, and why it is honest about failing
//!
//! Resolving `import m;` means finding the file that declares `m` — and that file's *name* is not part of
//! the language. Build systems conventionally name the interface unit after the module (`m.cppm`, `m.ixx`),
//! but nothing enforces it, so a resolver that trusted the convention would silently miss modules and one
//! that demanded a scan would be too expensive to run per keystroke.
//!
//! Both are tried, in that order, and the outcome records which one worked. When neither does, the answer is
//! [`Resolution::Unresolved`] and never a guess: an unresolved import means "this analysis does not know what
//! that module contains", which is a state a consumer renders differently from "the module is empty". See
//! [`ImportOutcome`] for the one case where the distinction is subtler than it looks.

use std::collections::HashMap;
use std::path::{Path, PathBuf};

use cpp_parser::CppSyntaxTree;

use crate::{
    config::CompilerConfig,
    directive::IncludeForm,
    include::{IncludeResolver, Resolution},
    module_info::{ImportTarget, ModuleInfo, ModuleUnit},
    paths::{FileId, FileProvider, PathInterner, join_normalized},
};

/// Extensions a module interface unit is commonly given.
///
/// Used only to *propose* candidates for the cheap path; a candidate is confirmed by parsing it, so a wrong
/// guess here costs a failed lookup and never a wrong answer.
pub const INTERFACE_UNIT_EXTENSIONS: &[&str] = &["cppm", "ixx", "ccm", "cxxm", "cpp", "cc", "cxx"];

/// One module unit: a file that declares a module.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ModuleUnitEntry {
    pub file: FileId,
    pub path: PathBuf,
    /// The module it belongs to, without the partition.
    pub module_name: Box<str>,
    /// Its partition, if it has one.
    pub partition_name: Option<Box<str>>,
    pub unit: ModuleUnit,
}

impl ModuleUnitEntry {
    /// The name this unit is known by inside its module: `m` or `m:part`.
    pub fn qualified_name(&self) -> String {
        match &self.partition_name {
            Some(partition) => format!("{}:{}", self.module_name, partition),
            None => self.module_name.to_string(),
        }
    }
}

/// How an import resolved.
///
/// The variants are the states a consumer has to render differently, and the reason this is an enum rather
/// than an `Option<FileId>`: "I found the file" and "I cannot find the file" are different, and so are the
/// three flavours of not finding it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ImportOutcome {
    /// The declaring file was found.
    Resolved(FileId),
    /// Nothing in the project declares this module.
    ///
    /// The honest reading is "unknown", not "empty": the module may be provided by a prebuilt BMI the
    /// analysis has no source for, which is the normal state of affairs for `import std;` and for any
    /// library shipped as a module. A consumer must not conclude that the imported names do not exist.
    UnknownModule { name: Box<str> },
    /// The module is known but the named partition is not.
    ///
    /// Worth separating from [`ImportOutcome::UnknownModule`] because the module *is* here: the partition
    /// name is either misspelled or the partition's file is missing from the project, and the two lead to
    /// different fixes.
    UnknownPartition {
        module: Box<str>,
        partition: Box<str>,
    },
    /// A header unit whose header could not be found.
    ///
    /// Carries what was searched, so the message can say where it looked — the same reason
    /// [`crate::include::Unresolved`] keeps its candidates.
    UnknownHeaderUnit {
        name: Box<str>,
        searched: Vec<PathBuf>,
    },
    /// The name resolves to a file that does not declare it.
    ///
    /// The case that catches a real mistake: `import m;` finds `m.cppm` by the naming convention, and
    /// `m.cppm` turns out to declare `other`. Reporting a resolved edge here would attribute `other`'s
    /// declarations to `m` — so the mismatch is reported instead, and the file that was tried is kept so the
    /// message can name it.
    NotDeclaredHere { name: Box<str>, tried: PathBuf },
    /// A partition import from a file that is not part of the module.
    ///
    /// `import :part;` means "a partition of *my* module", so it can only appear in a file that declares a
    /// module — or in a partition of one. In a plain translation unit there is no module for it to belong to,
    /// and the import cannot be resolved at all.
    NoModuleToPartition,
    /// A partition import that named a partition which is not declared as such.
    ///
    /// Distinct from [`ImportOutcome::UnknownPartition`]: the file was found, and it is a unit of the right
    /// module, but it is not the partition the import asked for.
    PartitionMismatch {
        module: Box<str>,
        partition: Box<str>,
        tried: PathBuf,
    },
}

impl ImportOutcome {
    /// The file an import resolved to, if it did.
    pub fn file(&self) -> Option<FileId> {
        match self {
            ImportOutcome::Resolved(file) => Some(*file),
            _ => None,
        }
    }

    /// Did this resolve?
    pub fn is_resolved(&self) -> bool {
        matches!(self, ImportOutcome::Resolved(_))
    }

    /// Could names from this import be visible to the importer?
    ///
    /// `true` only for a resolved import. Everything else is *unknown* rather than absent, which is the
    /// distinction the whole enum exists for — an unresolved module may still have been compiled into a BMI
    /// the analysis cannot see, so hiding its names would be a guess and reporting them as missing would be
    /// a false positive.
    pub fn may_provide_names(&self) -> bool {
        self.is_resolved()
    }

    /// A sentence a diagnostic can show.
    ///
    /// Each phrasing says what was actually *established*, not merely that something failed. The header-unit
    /// case makes the point: "looked in 0 places" is the honest answer for an angle import in a project with
    /// no configured include paths, and it tells the user the fix is a build configuration rather than a
    /// missing file — which "cannot find vector" would not.
    pub fn describe(&self) -> String {
        match self {
            ImportOutcome::Resolved(_) => "resolved".to_string(),
            ImportOutcome::UnknownModule { name } => {
                format!("no file in this project declares module `{name}`")
            }
            ImportOutcome::UnknownPartition { module, partition } => {
                format!("module `{module}` declares no partition `:{partition}`")
            }
            ImportOutcome::UnknownHeaderUnit { name, searched } if searched.is_empty() => format!(
                "cannot build a header unit for `{name}`: no include directories are configured to search"
            ),
            ImportOutcome::UnknownHeaderUnit { name, searched } => format!(
                "cannot find a header for unit `{name}` (looked in {} place(s))",
                searched.len()
            ),
            ImportOutcome::NotDeclaredHere { name, tried } => format!(
                "`{}` was tried for module `{name}` but does not declare it",
                tried.display()
            ),
            ImportOutcome::NoModuleToPartition => {
                "`import :partition;` in a file that declares no module".to_string()
            }
            ImportOutcome::PartitionMismatch {
                module,
                partition,
                tried,
            } => format!(
                "`{}` is a unit of `{module}` but is not partition `:{partition}`",
                tried.display()
            ),
        }
    }
}

/// One import declaration and what became of it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ImportEdge {
    pub from: FileId,
    /// The module this import was written in, when the importing file declares one.
    ///
    /// The importer's own module, and the reason a partition import can be resolved at all: `import :part;`
    /// is looked up against this, not against the file system.
    pub from_module: Option<Box<str>>,
    pub target: ImportTarget,
    pub is_reexport: bool,
    pub outcome: ImportOutcome,
    pub range: cpp_parser::SourceRange,
}

/// Every module unit reached, and every import between them.
#[derive(Debug, Clone, Default)]
pub struct ModuleGraph {
    /// The units, in the order they were read.
    pub units: Vec<ModuleUnitEntry>,
    /// The imports, in the order they were read.
    pub edges: Vec<ImportEdge>,
    /// Every file that was read, in the order it was entered.
    pub analysed: Vec<FileId>,
}

impl ModuleGraph {
    /// The unit that declares `module`, if the project has one.
    ///
    /// Only a primary interface unit answers this: a partition interface unit is an interface, but nothing
    /// outside its module may import it by name, so returning one here would resolve an `import m;` to a file
    /// that does not export what the importer is asking for.
    pub fn interface_unit(&self, module: &str) -> Option<&ModuleUnitEntry> {
        self.units
            .iter()
            .find(|unit| &*unit.module_name == module && unit.unit.exports_to_importers())
    }

    /// The unit for a partition, if the project has one.
    pub fn partition_unit(&self, module: &str, partition: &str) -> Option<&ModuleUnitEntry> {
        self.units.iter().find(|unit| {
            &*unit.module_name == module
                && unit.partition_name.as_deref() == Some(partition)
                // An implementation unit for a partition does not *export* it. Which one is wanted depends
                // on the question, so the interface wins when both exist — that is the one a name from the
                // partition is visible through.
                && unit.unit.is_interface()
        })
    }

    /// Every unit of a module, including its partitions', in the order they were read.
    pub fn units_of(&self, module: &str) -> Vec<&ModuleUnitEntry> {
        self.units
            .iter()
            .filter(|unit| &*unit.module_name == module)
            .collect()
    }

    /// The imports a file makes, in source order.
    ///
    /// An iterator rather than a `Vec` because the caller almost always just walks it, and a `Vec` would make
    /// every read site allocate — including the ones that only want the first edge.
    pub fn imports_of(&self, file: FileId) -> impl Iterator<Item = &ImportEdge> {
        self.edges.iter().filter(move |edge| edge.from == file)
    }

    /// The resolved files a file imports — what it needs in order to be built.
    pub fn needs_of(&self, file: FileId) -> Vec<FileId> {
        self.imports_of(file)
            .filter_map(|edge| edge.outcome.file())
            .collect()
    }

    /// The files that import `file` **directly**, through a resolved import.
    ///
    /// The reverse edge, and the point of the module graph: a change to a module interface unit invalidates
    /// exactly these, and transitively whatever imports them. A consumer that had to re-scan the project to
    /// find them would be doing per-keystroke work proportional to the project.
    pub fn importers_of(&self, file: FileId) -> Vec<FileId> {
        let mut importers: Vec<FileId> = self
            .edges
            .iter()
            .filter(|edge| edge.outcome.file() == Some(file))
            .map(|edge| edge.from)
            .collect();

        importers.sort_unstable_by_key(|file| file.index());
        importers.dedup();
        importers
    }

    /// Every file that depends on `file`, directly or through other imports — what a cache invalidation
    /// has to discard.
    pub fn dependents_of(&self, file: FileId) -> Vec<FileId> {
        let mut out = Vec::new();
        let mut seen: std::collections::HashSet<FileId> = std::collections::HashSet::new();
        let mut stack = vec![file];

        while let Some(current) = stack.pop() {
            for importer in self.importers_of(current) {
                if seen.insert(importer) {
                    out.push(importer);
                    stack.push(importer);
                }
            }
        }

        out
    }

    /// The imports that did not resolve, with what was tried.
    pub fn unresolved_imports(&self) -> Vec<&ImportEdge> {
        self.edges
            .iter()
            .filter(|edge| !edge.outcome.is_resolved())
            .collect()
    }

    /// The entry for a file, if it was read.
    pub fn unit_of(&self, file: FileId) -> Option<&ModuleUnitEntry> {
        self.units.iter().find(|unit| unit.file == file)
    }
}

/// Reads files and resolves their imports.
///
/// Holds no macro environment, by design — see the module documentation. The interner is passed to each
/// resolution rather than held, because minting a `FileId` mutates it and a scanner that borrowed it for its
/// whole life would make the caller's other uses of the same table impossible.
pub struct ModuleScanner<'a, F: FileProvider> {
    files: &'a F,
    config: &'a CompilerConfig,
    /// Module name → the files that declare it, from the last scan.
    ///
    /// Built once per scan rather than per lookup: resolution asks the same question for every import in the
    /// project, and re-parsing every candidate file per import is the difference between one pass and
    /// quadratic work.
    index: HashMap<Box<str>, Vec<ModuleUnitEntry>>,
    /// The units read so far, in the order read — what becomes [`ModuleGraph::units`].
    scanned_units: Vec<ModuleUnitEntry>,
}

impl<'a, F: FileProvider> ModuleScanner<'a, F> {
    pub fn new(files: &'a F, config: &'a CompilerConfig) -> Self {
        ModuleScanner {
            files,
            config,
            index: HashMap::new(),
            scanned_units: Vec::new(),
        }
    }

    /// Read a file and add its unit to the index, returning what it declares.
    ///
    /// Parsing the file is the caller's business: it usually has the tree already, and this layer exists to
    /// answer questions about the tree, not to be a second parser.
    pub fn add_file(&mut self, file: FileId, path: &Path, tree: &CppSyntaxTree) -> ModuleInfo {
        let info = ModuleInfo::from_tree(&tree.get_red_root());

        if let (Some(unit), Some(module_name)) = (info.unit, info.module_name.clone()) {
            let entry = ModuleUnitEntry {
                file,
                path: path.to_path_buf(),
                module_name: module_name.clone(),
                partition_name: info.partition_name.clone(),
                unit,
            };

            self.index
                .entry(module_name)
                .or_default()
                .push(entry.clone());
            // A file read twice is one unit. The same path reached from two importers is the same file, and
            // a duplicate would make `units_of` report a module with two interface units — which is a
            // contradiction a consumer would have to defend against.
            if !self.scanned_units.iter().any(|unit| unit.file == file) {
                self.scanned_units.push(entry);
            }
        }

        info
    }

    /// Every unit read so far, in the order read.
    pub fn units(&self) -> &[ModuleUnitEntry] {
        &self.scanned_units
    }

    /// Resolve a module name to its primary interface unit.
    ///
    /// The two-step order, and why each step is there:
    ///
    /// 1. **The index** — the units already read, which is exact. A module name that appears here is
    ///    resolved with no I/O at all.
    /// 2. **The naming convention** — `m` → `m.cppm` and friends beside the importing file and along the
    ///    include paths. Only ever a *proposal*: the candidate is read and must declare `m`, so a file that
    ///    merely has the right name is rejected rather than accepted.
    ///
    /// Nothing else is tried. A full project scan would find modules with unconventional names, and it is
    /// the wrong trade for a per-keystroke analysis: the cost is proportional to the project on every lookup,
    /// and the case it fixes is one a build system has already solved by knowing where its own sources are.
    ///
    /// # `directory` is a **directory**
    ///
    /// The importing file's own directory, which is what [`candidate_paths`](Self::candidate_paths)
    /// joins a name onto. A caller that passes the importing *file* gets `<dir>/main.cpp/math.cppm`
    /// for every candidate, no filesystem has that path, and the answer is `UnknownModule` — a
    /// silence, not an error.
    pub fn resolve_module(
        &mut self,
        name: &str,
        directory: &Path,
        interner: &mut PathInterner,
    ) -> ImportOutcome {
        if let Some(entry) = self
            .index
            .get(name)
            .and_then(|units| units.iter().find(|unit| unit.unit.exports_to_importers()))
        {
            return ImportOutcome::Resolved(entry.file);
        }

        for candidate in self.candidate_paths(name, directory) {
            let Some(source) = self.files.read(&candidate) else {
                continue;
            };

            let tree = cpp_parser::CppParser::parse(&source, cpp_parser::ParserConfig::default());
            let info = ModuleInfo::from_tree(&tree.get_red_root());

            if info.module_name.as_deref() != Some(name) {
                // The file exists and is not the module. Reported rather than skipped: this is the one
                // failure that indicates a real mistake — a renamed module, a copy-paste, a file in the
                // wrong directory — and silently moving on would leave the user with "module not found"
                // about a module that is right there.
                return ImportOutcome::NotDeclaredHere {
                    name: name.into(),
                    tried: candidate,
                };
            }

            if info.unit != Some(ModuleUnit::InterfaceUnit) {
                // It declares the module but is not the unit importers see.
                return ImportOutcome::NotDeclaredHere {
                    name: name.into(),
                    tried: candidate,
                };
            }

            let file = interner.intern(&candidate);
            self.add_file(file, &candidate, &tree);

            return ImportOutcome::Resolved(file);
        }

        ImportOutcome::UnknownModule { name: name.into() }
    }

    /// Resolve `import :partition;` against the importing file's own module.
    pub fn resolve_partition(
        &mut self,
        module: Option<&str>,
        partition: &str,
        directory: &Path,
        interner: &mut PathInterner,
    ) -> ImportOutcome {
        let Some(module) = module else {
            return ImportOutcome::NoModuleToPartition;
        };

        if let Some(entry) = self.index.get(module).and_then(|units| {
            units.iter().find(|unit| {
                unit.partition_name.as_deref() == Some(partition) && unit.unit.is_interface()
            })
        }) {
            return ImportOutcome::Resolved(entry.file);
        }

        // The partition's file may exist and not have been read yet: `m:part` is named after the module, so
        // the same convention applies with the partition appended.
        let qualified = format!("{module}:{partition}");
        for candidate in self.candidate_paths(&qualified, directory) {
            let Some(source) = self.files.read(&candidate) else {
                continue;
            };

            let tree = cpp_parser::CppParser::parse(&source, cpp_parser::ParserConfig::default());
            let info = ModuleInfo::from_tree(&tree.get_red_root());

            let matches = info.module_name.as_deref() == Some(module)
                && info.partition_name.as_deref() == Some(partition);

            if !matches {
                return ImportOutcome::PartitionMismatch {
                    module: module.into(),
                    partition: partition.into(),
                    tried: candidate,
                };
            }

            let file = interner.intern(&candidate);
            self.add_file(file, &candidate, &tree);

            return ImportOutcome::Resolved(file);
        }

        ImportOutcome::UnknownPartition {
            module: module.into(),
            partition: partition.into(),
        }
    }

    /// Resolve a header unit through the include search order.
    ///
    /// A header unit *is* built from a header, by the same search the preprocessor would use, so this
    /// delegates rather than reimplementing it — a second implementation of "which `vector` did you mean"
    /// is free to disagree with the first, and then the analysis and the compiler disagree.
    pub fn resolve_header_unit(
        &mut self,
        name: &str,
        is_angle: bool,
        directory: &Path,
        interner: &mut PathInterner,
    ) -> ImportOutcome {
        let include = crate::directive::Include {
            target: name.into(),
            form: if is_angle {
                IncludeForm::Angle
            } else {
                IncludeForm::Quote
            },
            is_next: false,
        };

        let resolver = IncludeResolver::new(self.files, self.config);
        let outcome = resolver.resolve(&include, directory, None, interner);

        match outcome {
            Resolution::Resolved(resolved) => ImportOutcome::Resolved(resolved.file),
            Resolution::Unresolved(unresolved) => ImportOutcome::UnknownHeaderUnit {
                name: name.into(),
                searched: unresolved.searched,
            },
        }
    }

    /// Candidate files for a module name, in the order they are worth trying.
    ///
    /// A module name maps to a file name by convention, and there is more than one convention in use, so
    /// several spellings are tried. Each is only a *proposal*: a candidate is read and must declare the
    /// module before it is accepted, so a wrong guess costs one failed read and never a wrong answer.
    ///
    /// The partition separator is where the conventions genuinely differ, and where a single rule would fail
    /// every real project:
    ///
    /// ```text
    /// m:part   ->  m-part.cppm     the common spelling; a colon is not portable in a file name
    ///          ->  m.part.cppm     used where the module name is kept verbatim
    ///          ->  m/part.cppm     used where partitions live in a directory of their own
    /// my.mod   ->  my/mod.cppm     dots as directories
    ///          ->  my.mod.cppm     kept flat
    /// ```
    ///
    /// # The importing file's directory, and why it is not the empty path
    ///
    /// Because a candidate is **read**, and a relative path read against the process's working directory is a
    /// path nobody meant: measured on the module fixture (`tests/fixtures/modules`, built by
    /// `target/build_modules.bat`), `import mathlib;` in `main.cpp` beside `mathlib.ixx` answered "no file in this
    /// project declares module `mathlib`" — the convention had proposed `mathlib.ixx`, and that spelling was
    /// resolved against the analysis's own directory rather than the file that wrote the `import`. So the
    /// importing file's directory is joined **here**, and the include paths after it.
    fn candidate_paths(&self, name: &str, including: &Path) -> Vec<PathBuf> {
        let mut candidates = Vec::new();
        let case_insensitive = self.files.is_case_insensitive();

        // `:` and `.` are both separators between a module and its partition, so both are expanded; the
        // difference between them is only which spelling of the *name* they came from.
        let dotted = name.replace(':', ".");
        // **The underscore is the shape a project actually writes**: CMake's module documentation and `test_module`
        // both name a partition file `<module>_<partition>.cppm`, while this list had only `-`, `/` and `.`. A
        // candidate is verified by reading it — it has to declare `export module m:part;` — so one more spelling costs
        // a failed read at worst, and a partition nothing could find made `import geometry;` see nothing of
        // `:shapes` (`tests/partition_probe.rs`, `docs/buglist.md` section 11).
        let stems = [
            name.replace(':', "-").replace('.', "/"),
            name.replace(':', "-"),
            dotted.replace('.', "/"),
            dotted.clone(),
            name.replace(':', "_").replace('.', "/"),
            name.replace(':', "_"),
        ];

        for directory in self.search_directories(including) {
            for stem in &stems {
                for extension in INTERFACE_UNIT_EXTENSIONS {
                    let candidate = join_normalized(
                        &directory,
                        Path::new(&format!("{stem}.{extension}")),
                        case_insensitive,
                    );
                    if !candidates.contains(&candidate) {
                        candidates.push(candidate);
                    }
                }
            }
        }

        // **GCC's standard module is a *source file* inside the include tree**, and it is spelled unlike any
        // other module unit: `<include>/bits/std.cc` (97 KB on MinGW GCC 15.1: `module;`, `#include
        // <bits/stdc++.h>`, `export module std;`, then `export namespace std { … }` blocks) and
        // `<include>/bits/std.compat.cc`.
        //
        // A default GCC install has **no** `std.gcm` — the compiler answers `import std;` with *"failed to read
        // compiled module: No such file or directory … compiled module file is 'gcm.cache/std.gcm'"* (verified by
        // running the project's compiler) — so the source is the only thing an analysis can read, and it is the
        // right thing: it *is* the module's interface unit, and reading it gives the exported names exactly as the
        // compiler would.
        //
        // Appended **after** the naming conventions so that a project shipping its own `std.cppm` still wins, and
        // only for the two standard names: `bits/<anything>.cc` is not a convention, it is where this one library
        // put these two files.
        if matches!(name, "std" | "std.compat") {
            for directory in self.search_directories(including) {
                let candidate = join_normalized(
                    &directory,
                    Path::new(&format!("bits/{name}.cc")),
                    case_insensitive,
                );
                if !candidates.contains(&candidate) {
                    candidates.push(candidate);
                }
            }
        }

        candidates
    }

    /// The directories a module named after its file would be found in.
    ///
    /// The importing file's own directory first, which is where a project's modules live beside the file that
    /// imports them, then the include paths — the same order the quoted form of `#include` searches, and for
    /// modules there is no angle form to distinguish from, because a module name is never written in brackets.
    ///
    /// # `../modules`, which is where a *standard* module lives
    ///
    /// `import std;` is not in any project and not in an include path: MSVC ships it as
    /// `<VC>/Tools/MSVC/<version>/modules/std.ixx` — **beside** the include directory, not inside it (measured on
    /// 14.35.32215: `modules/std.ixx` is 3 194 bytes of `export module std;` followed by an `#include` of every
    /// standard header, and `modules/std.compat.ixx` re-exports it). So for every include path, its sibling
    /// `modules` directory is tried as well.
    ///
    /// The candidate is still only a *proposal* — it is read and must declare the module — so a directory that does
    /// not exist costs one failed read, and a compiler that keeps its standard module somewhere else is a module
    /// this scan does not find rather than one it finds wrongly.
    fn search_directories(&self, including: &Path) -> Vec<PathBuf> {
        let mut directories = vec![including.to_path_buf()];

        for directory in self
            .config
            .user_include_paths()
            .chain(self.config.system_include_paths())
        {
            directories.push(directory.to_path_buf());

            if let Some(parent) = directory.parent() {
                let modules = parent.join("modules");
                if !directories.contains(&modules) {
                    directories.push(modules);
                }
            }
        }

        directories
    }
}

/// How deep imports are followed before the scan gives up.
///
/// The module analogue of [`crate::graph::MAX_INCLUDE_DEPTH`], and there for the same reason: `import`
/// cycles are possible (two modules may import each other's partitions, and a partition may import its own
/// module), so a walk that trusted the graph would not terminate. The budget also bounds the work a single
/// keystroke can trigger.
pub const MAX_IMPORT_DEPTH: usize = 64;

/// Read a translation unit and everything it imports, building a module graph.
///
/// `tree` is the already-parsed root, handed over rather than re-parsed — the caller usually has it, and
/// parsing twice is the most expensive thing this could do. The file's *text* is not needed: every question
/// this layer asks is a question about the tree, and the two files it does need to read (a candidate
/// interface unit, a header unit) it reads itself.
///
/// # The root is taken as given; everything else is a candidate
///
/// Each import is *resolved*, which may read a candidate file to confirm it declares what its name claims,
/// and a resolved module is scanned in turn. The result records both the units found and every import with
/// its outcome, so a consumer can distinguish "this file imports nothing" from "this file imports things
/// this analysis could not find" — see [`ImportOutcome`].
///
/// # No macro environment is threaded
///
/// Deliberately, and the contrast with [`crate::graph::walk`] is the point of this module. An import does not
/// make the importer's macros visible to the imported module, so there is nothing to inherit and nothing to
/// propagate back. A consumer that needs a file's macros asks [`crate::graph`] about its `#include`s.
pub fn scan_imports<F: FileProvider>(
    tree: &CppSyntaxTree,
    root_path: &Path,
    files: &F,
    config: &CompilerConfig,
    interner: &mut PathInterner,
) -> ModuleGraph {
    let mut graph = ModuleGraph::default();
    let mut state = ScanState::default();
    let mut scanner = ModuleScanner::new(files, config);

    let root = interner.intern(root_path);
    graph.analysed.push(root);

    // The root's own unit is read first, so that a partition importing its own module resolves from the
    // index instead of hunting for a file that is the very one being read.
    let root_info = scanner.add_file(root, root_path, tree);

    follow_imports(
        &root_info,
        root,
        root_path,
        &mut scanner,
        &mut graph,
        &mut state,
        interner,
        0,
    );

    graph.units = scanner.units().to_vec();
    graph
}

/// Where the scan has been.
#[derive(Debug, Default)]
struct ScanState {
    /// Files whose imports have been followed, so a diamond does not re-read them.
    visited: std::collections::HashSet<FileId>,
    /// The chain currently being followed, for cycle detection.
    ///
    /// Separate from `visited` because the two answer different questions: a file already *visited* is a
    /// diamond and may be skipped safely, while a file on the *path* is a cycle and a compiler would reject
    /// it — a distinction worth keeping so a consumer can report the cycle rather than silently accepting it.
    on_path: Vec<FileId>,
}

/// Read one file's imports and follow the ones that resolved.
#[allow(clippy::too_many_arguments)]
fn follow_imports<F: FileProvider>(
    info: &ModuleInfo,
    file: FileId,
    path: &Path,
    scanner: &mut ModuleScanner<'_, F>,
    graph: &mut ModuleGraph,
    state: &mut ScanState,
    interner: &mut PathInterner,
    depth: usize,
) {
    state.visited.insert(file);
    state.on_path.push(file);

    let including = crate::paths::parent_normalized(path, scanner.files.is_case_insensitive());

    for declaration in &info.imports {
        let outcome = match &declaration.target {
            ImportTarget::Module(name) => scanner.resolve_module(name, &including, interner),
            ImportTarget::Partition(partition) => scanner.resolve_partition(
                info.module_name.as_deref(),
                partition,
                &including,
                interner,
            ),
            ImportTarget::HeaderUnit { name, is_angle } => {
                scanner.resolve_header_unit(name, *is_angle, &including, interner)
            }
        };

        graph.edges.push(ImportEdge {
            from: file,
            from_module: info.module_name.clone(),
            target: declaration.target.clone(),
            is_reexport: declaration.is_reexport,
            outcome: outcome.clone(),
            range: declaration.range,
        });

        let Some(target) = outcome.file() else {
            continue;
        };

        // A cycle, or a budget exhausted. The edge above is kept either way — the module *was* found, and
        // hiding the edge would lose the fact that the dependency exists. What stops is the recursion.
        if state.on_path.contains(&target) || depth + 1 > MAX_IMPORT_DEPTH {
            continue;
        }

        // A diamond, not a cycle: the file is in the graph once and its own imports were recorded the first
        // time. Re-reading it would duplicate every edge below it.
        if state.visited.contains(&target) {
            continue;
        }

        let Some(target_path) = interner.path(target).map(Path::to_path_buf) else {
            continue;
        };

        let Some(target_source) = scanner.files.read(&target_path) else {
            continue;
        };

        let target_tree =
            cpp_parser::CppParser::parse(&target_source, cpp_parser::ParserConfig::default());
        let target_info = scanner.add_file(target, &target_path, &target_tree);

        if !graph.analysed.contains(&target) {
            graph.analysed.push(target);
        }

        follow_imports(
            &target_info,
            target,
            &target_path,
            scanner,
            graph,
            state,
            interner,
            depth + 1,
        );
    }

    state.on_path.pop();
}