cpp_code_analysis 0.3.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
//! Paths, file identities, and reading files — behind a trait so that all of it is testable.
//!
//! # Why a trait and not `std::fs`
//!
//! Every interesting property of include resolution is about *which* of several candidate paths is found
//! first: a quoted include preferring the including file's own directory, a project directory shadowing a
//! system one, an include guard stopping a second visit. A test for any of those needs a specific tree of
//! files, and building one on disk is slow, needs cleanup, and makes the test depend on the filesystem's
//! case and separator rules rather than on the rules under test.
//!
//! So reading is a trait, with [`MemoryFiles`] for tests and [`DiskFiles`] for real use. The resolution
//! logic is then ordinary code with ordinary tests, and the part that touches the disk is small enough to
//! read in one sitting.
//!
//! # Why a `FileId` and not a `PathBuf`
//!
//! Two spellings of one file have to compare equal. `./a.h`, `a.h`, `inc/../a.h` and `A.H` on Windows are
//! one file, and a graph keyed by path would hold four nodes for it — four times the analysis, and a
//! reverse-dependency query that finds one of the four. A `FileId` is a number that the path table mints
//! once per distinct file, and everything downstream compares numbers.

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

/// A file's identity within one analysis.
///
/// Minted by [`PathInterner`], stable for as long as that interner lives, and meaningless outside it — a
/// `FileId` is not a handle to anything a caller can open, which is what keeps it small and copyable.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct FileId(u32);

impl FileId {
    /// The id's number, for a consumer that wants a dense array indexed by file.
    pub fn index(self) -> usize {
        self.0 as usize
    }

    /// Mint an id from a number. For the layer that owns the numbering ([`crate::Vfs`]) and nothing else.
    pub fn new(number: u32) -> FileId {
        FileId(number)
    }
}

/// Reads files. The only thing in this layer that touches a filesystem.
///
/// `Sync`, because a provider is shared by the threads that index a project's files at once — every provider here
/// is a handle over a lock or a unit struct, so the bound costs the implementations nothing.
pub trait FileProvider: Sync {
    /// The contents of a file, or `None` if it cannot be read.
    ///
    /// `None` rather than an error, because every reason a file cannot be read — missing, a directory,
    /// permissions, a deleted buffer, a path the editor has open but not yet saved — leads to the same
    /// decision: this include did not resolve, and the analysis continues without it.
    fn read(&self, path: &Path) -> Option<String>;

    /// Does this path name a file that can be read?
    ///
    /// Separate from [`read`](Self::read) so that resolution does not have to read a file to learn whether
    /// it exists. A search path of twenty directories, each `stat`ed rather than read, is the difference
    /// between a completion list that appears and one that does not.
    fn exists(&self, path: &Path) -> bool;

    /// Is this filesystem case-insensitive?
    ///
    /// Part of the provider because it is a property of the *filesystem*, not of the platform: a case-
    /// sensitive volume on Windows and a case-folding one on macOS both exist, and resolution is wrong on
    /// one of them whichever way it is hard-coded.
    fn is_case_insensitive(&self) -> bool {
        cfg!(windows)
    }

    /// Is this path one the **editor has open**, rather than one on disk?
    ///
    /// A question only an overlay can answer, which is why the default says `false`: a provider that is not an
    /// overlay reads the disk, and the disk is never a buffer. [`crate::OpenDocuments`] and
    /// [`OverlayFiles`] answer it for real, and the VFS records the answer with each entry —
    /// a view has to be able to say whether the analysis saw what the user sees.
    fn is_open_buffer(&self, _path: &Path) -> bool {
        false
    }
}

/// The real filesystem.
#[derive(Debug, Clone, Default)]
pub struct DiskFiles;

impl FileProvider for DiskFiles {
    fn read(&self, path: &Path) -> Option<String> {
        std::fs::read_to_string(path).ok()
    }

    fn exists(&self, path: &Path) -> bool {
        path.is_file()
    }
}

/// **One read of each file per run** — the layer every other layer's text comes from.
///
/// # Why this exists, and why it is not merely a speed-up
///
/// The walk, the index and the cooker have to see the **same bytes**. Read a file twice and an edit in between
/// makes them disagree — and a disagreement about macro state is not a diagnostic, it is every rule downstream
/// answering about a header that is not on disk. That is the failure clang's deps scanner hit when it tried to
/// share a `FileManager` across builds
/// ([b00de4d](https://github.com/llvm/llvm-project/commit/b00de4dd4156874fd5c163e9cecd69a54e45e083)), and the
/// answer is the one this layer takes: cache **content**, ask a question whose answer cannot go stale, and make
/// invalidation the caller's explicit act.
///
/// # What it is not
///
/// It is **not** a cache across runs — it is *this* run's snapshot, and the caches that do cross runs
/// ([`crate::SummaryStore`], [`crate::TranslationUnitCache`]) are keyed by **content hashes** for the same
/// reason. Nothing here looks at a timestamp: a file whose content changed while its mtime stood still is not a
/// case this layer can get wrong, because it never asks one. A caller that knows a file changed — an editor's
/// `didChange`, a watcher's event — says so with [`CachedFiles::reload`].
///
/// The text is shared as `Arc<str>`, which is what the layers above want anyway: a definition's body, a file's
/// source and a summary's slice are all substrings of the same bytes, and handing out a fresh `String` per reader
/// is an allocation per reader.
#[derive(Debug)]
pub struct CachedFiles<F: FileProvider = DiskFiles> {
    inner: F,
    /// `path → its text`, by normalized key. `None` is remembered too: a file that is not there is asked for
    /// **once** per run rather than once per `#include` that names it — an include search that keeps missing is
    /// the common case in a project whose configuration is not finished.
    contents: std::sync::Mutex<HashMap<String, Option<std::sync::Arc<str>>>>,
    /// How many times the provider **under** this one was asked, and for how many distinct paths.
    ///
    /// A measurement, and the only way to answer "is this layer doing its job": a run that reads each file once
    /// and a run that reads each file three times produce the same *answers*, so no assertion about a result can
    /// tell them apart.
    reads: std::sync::atomic::AtomicUsize,
    paths_read: std::sync::Mutex<std::collections::HashSet<String>>,
}

impl<F: FileProvider> CachedFiles<F> {
    pub fn new(inner: F) -> Self {
        CachedFiles {
            inner,
            contents: std::sync::Mutex::new(HashMap::new()),
            reads: std::sync::atomic::AtomicUsize::new(0),
            paths_read: std::sync::Mutex::new(std::collections::HashSet::new()),
        }
    }

    /// The provider underneath — for a caller that needs to ask it something this layer does not cache.
    pub fn inner(&self) -> &F {
        &self.inner
    }

    /// The text of a file, read **at most once** per run.
    ///
    /// The shared `Arc` rather than a fresh `String`: every layer above keeps a *slice* of this text, and the
    /// second asker should pay a refcount bump rather than a copy of the file.
    pub fn text(&self, path: &Path) -> Option<std::sync::Arc<str>> {
        let key = normalize_path(path, self.inner.is_case_insensitive());
        let mut contents = self
            .contents
            .lock()
            .expect("the content cache is not poisoned");

        if let Some(known) = contents.get(&key) {
            return known.clone();
        }

        self.reads
            .fetch_add(1, std::sync::atomic::Ordering::Relaxed);
        self.paths_read
            .lock()
            .expect("the read log is not poisoned")
            .insert(key.clone());

        let text = self
            .inner
            .read(path)
            .map(|text| std::sync::Arc::from(text.as_str()));
        contents.insert(key, text.clone());
        text
    }

    /// Forget what this layer holds for a path, so the next read asks the provider again.
    ///
    /// What an editor calls when a buffer changes, and the only way this cache can be wrong — which is the point:
    /// invalidation is a statement the *caller* makes, not a guess this layer takes.
    pub fn reload(&self, path: &Path) {
        let key = normalize_path(path, self.inner.is_case_insensitive());
        self.contents
            .lock()
            .expect("the content cache is not poisoned")
            .remove(&key);
    }

    /// How many times the provider underneath has been asked — one per path per run, when this layer is used.
    pub fn reads(&self) -> usize {
        self.reads.load(std::sync::atomic::Ordering::Relaxed)
    }

    /// How many **distinct** paths were read.
    ///
    /// Beside [`CachedFiles::reads`] because the two answer different questions: "did anything read a file more
    /// than once" is the first number against the second, and a run that reads 255 files once each and one that
    /// reads 3 files 255 times are the same number of reads and different worlds.
    pub fn paths_read(&self) -> usize {
        self.paths_read
            .lock()
            .expect("the read log is not poisoned")
            .len()
    }
}

impl<F: FileProvider> FileProvider for CachedFiles<F> {
    /// The cached text, as an owned `String` — the trait's shape, not this layer's preference: a caller that
    /// wants to avoid the copy asks [`CachedFiles::text`].
    fn read(&self, path: &Path) -> Option<String> {
        self.text(path).map(|text| text.to_string())
    }

    /// **Not cached**: existence is a `stat`, and a run that starts before a file is written should see it appear.
    /// The hazard this layer exists for is two *contents* disagreeing, and there is no content here to disagree.
    fn exists(&self, path: &Path) -> bool {
        self.inner.exists(path)
    }

    fn is_case_insensitive(&self) -> bool {
        self.inner.is_case_insensitive()
    }

    fn is_open_buffer(&self, path: &Path) -> bool {
        self.inner.is_open_buffer(path)
    }
}

/// Files held in memory.
///
/// The test double, and also the shape an editor needs: an unsaved buffer's include must resolve to the
/// buffer, not to whatever is on disk. A caller with open documents puts them here and the rest fall
/// through to [`DiskFiles`] via [`OverlayFiles`].
///
/// Reads are counted, because "did this analysis read that file" is a question about performance that no
/// assertion about the *result* can answer: a walk that read a file and then found nothing in it produces the
/// same graph as one that never looked. [`MemoryFiles::reads_of`] is what tells them apart.
#[derive(Debug, Clone, Default)]
pub struct MemoryFiles {
    files: HashMap<String, String>,
    case_insensitive: bool,
    reads: std::sync::Arc<std::sync::Mutex<Vec<String>>>,
    probes: std::sync::Arc<std::sync::Mutex<Vec<String>>>,
}

impl MemoryFiles {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn with_case_insensitive(mut self, value: bool) -> Self {
        self.case_insensitive = value;
        self
    }

    /// How many times a path has been read, by normalized key.
    ///
    /// Shared across clones, so a provider moved into a walk and a copy kept by the test see the same count —
    /// which is the only way this can be used from outside the call that did the reading.
    pub fn reads_of(&self, path: impl AsRef<Path>) -> usize {
        let wanted = normalize_path(path.as_ref(), self.case_insensitive);
        let reads = self.reads.lock().expect("the read log is not poisoned");
        reads.iter().filter(|read| **read == wanted).count()
    }

    /// Every path read, in order, for a failure message that says what happened.
    pub fn reads(&self) -> Vec<String> {
        self.reads
            .lock()
            .expect("the read log is not poisoned")
            .clone()
    }

    /// How many times a path has been **looked for**, by normalized key.
    ///
    /// The counterpart of [`MemoryFiles::reads_of`], and the question it answers is the one the resolver asks: a
    /// candidate path is probed once per `#include` that could name it. So "did anything search for this header"
    /// is answerable here and nowhere else — a cache hit that never calls `exists` is a hit that never resolved
    /// an include, which is a hit that never built a summary.
    pub fn exists_of(&self, path: impl AsRef<Path>) -> usize {
        let wanted = normalize_path(path.as_ref(), self.case_insensitive);
        let probes = self.probes.lock().expect("the probe log is not poisoned");
        probes.iter().filter(|probe| **probe == wanted).count()
    }

    /// Every path looked for, in order.
    pub fn probes(&self) -> Vec<String> {
        self.probes
            .lock()
            .expect("the probe log is not poisoned")
            .clone()
    }

    /// Add a file. The key is normalized the same way resolution normalizes a path.
    pub fn insert(&mut self, path: impl AsRef<Path>, contents: impl Into<String>) -> &mut Self {
        self.files.insert(
            normalize_path(path.as_ref(), self.case_insensitive),
            contents.into(),
        );
        self
    }

    pub fn with_file(mut self, path: impl AsRef<Path>, contents: impl Into<String>) -> Self {
        self.insert(path, contents);
        self
    }

    /// Build from `(path, contents)` pairs.
    pub fn from_files<I, P>(files: I, case_insensitive: bool) -> Self
    where
        I: IntoIterator<Item = (P, &'static str)>,
        P: AsRef<Path>,
    {
        let mut memory = MemoryFiles::new().with_case_insensitive(case_insensitive);
        for (path, contents) in files {
            memory.insert(path, contents);
        }
        memory
    }
}

impl FileProvider for MemoryFiles {
    fn read(&self, path: &Path) -> Option<String> {
        let key = normalize_path(path, self.case_insensitive);

        self.reads
            .lock()
            .expect("the read log is not poisoned")
            .push(key.clone());

        self.files.get(&key).cloned()
    }

    fn exists(&self, path: &Path) -> bool {
        let key = normalize_path(path, self.case_insensitive);

        self.probes
            .lock()
            .expect("the probe log is not poisoned")
            .push(key.clone());

        self.files.contains_key(&key)
    }

    fn is_case_insensitive(&self) -> bool {
        self.case_insensitive
    }
}

/// One provider in front of another: open documents first, then the disk.
///
/// What an editor actually needs. An unsaved buffer's includes have to resolve against what the user has
/// typed, and a buffer that has never been saved has no file on disk at all — so the overlay is the
/// difference between "works while you type" and "works after you save".
#[derive(Debug, Clone)]
pub struct OverlayFiles<F: FileProvider, G: FileProvider> {
    pub overlay: F,
    pub fallback: G,
}

impl<F: FileProvider, G: FileProvider> OverlayFiles<F, G> {
    pub fn new(overlay: F, fallback: G) -> Self {
        OverlayFiles { overlay, fallback }
    }
}

impl<F: FileProvider, G: FileProvider> FileProvider for OverlayFiles<F, G> {
    fn read(&self, path: &Path) -> Option<String> {
        self.overlay.read(path).or_else(|| self.fallback.read(path))
    }

    fn exists(&self, path: &Path) -> bool {
        self.overlay.exists(path) || self.fallback.exists(path)
    }

    fn is_case_insensitive(&self) -> bool {
        self.overlay.is_case_insensitive() || self.fallback.is_case_insensitive()
    }

    /// The overlay's answer, and only the overlay's: the fallback is the filesystem, which has no buffers.
    fn is_open_buffer(&self, path: &Path) -> bool {
        self.overlay.is_open_buffer(path)
    }
}

/// Mints a [`FileId`] per distinct path, and remembers which path that was.
#[derive(Debug, Clone, Default)]
pub struct PathInterner {
    by_normalized: HashMap<String, FileId>,
    paths: Vec<PathBuf>,
    case_insensitive: bool,
}

impl PathInterner {
    pub fn new(case_insensitive: bool) -> Self {
        PathInterner {
            case_insensitive,
            ..PathInterner::default()
        }
    }

    pub fn case_insensitive(&self) -> bool {
        self.case_insensitive
    }

    /// The id for a path, minting one if this is the first time it is seen.
    ///
    /// The path is recorded as it was *first* spelled. A later spelling with different case — the same
    /// file, on a case-insensitive filesystem — resolves to the earlier id and does not replace the stored
    /// path, so a consumer displaying the file's name shows the spelling that was seen first rather than
    /// whichever include happened to be resolved last.
    pub fn intern(&mut self, path: &Path) -> FileId {
        let key = normalize_path(path, self.case_insensitive);

        if let Some(existing) = self.by_normalized.get(&key) {
            return *existing;
        }

        let id = FileId(self.paths.len() as u32);
        self.paths.push(path.to_path_buf());
        self.by_normalized.insert(key, id);
        id
    }

    /// The id for a path, if it has been seen.
    pub fn get(&self, path: &Path) -> Option<FileId> {
        self.by_normalized
            .get(&normalize_path(path, self.case_insensitive))
            .copied()
    }

    pub fn path(&self, id: FileId) -> Option<&Path> {
        self.paths.get(id.index()).map(PathBuf::as_path)
    }

    pub fn len(&self) -> usize {
        self.paths.len()
    }

    pub fn is_empty(&self) -> bool {
        self.paths.is_empty()
    }
}

/// Normalize a path for comparison: separators unified, `.` and `..` resolved, case folded if asked.
///
/// # Why this is not `canonicalize`
///
/// `std::fs::canonicalize` touches the disk, follows symlinks, and fails on a file that does not exist —
/// and a path that does not exist is exactly the case resolution has to handle, because it is what makes
/// an include fail. It also resolves symlinks, which would merge two project directories that are
/// deliberately two different trees.
///
/// So this is lexical: `/` and `\` become one, a trailing separator goes, and `.`/`..` are folded without
/// consulting anything. The result compares equal for any two spellings of the same path, which is the
/// whole requirement.
///
/// # Drive letters
///
/// A Windows path has a *prefix* component (`C:`) that is not a directory and must not be joined with a
/// separator: `C:\a` is `C:/a`, and `C://a` is a different string that compares unequal to it. The prefix
/// is therefore attached to the root rather than treated as a segment, which is the one place this
/// function is not purely mechanical.
pub fn normalize_path(path: &Path, case_insensitive: bool) -> String {
    // **A verbatim prefix is dropped before anything else.** `std::fs::canonicalize` returns one on Windows
    // (`\\?\E:\…`), and it is not the path it names for the purposes this function serves: the rewritten form below
    // keeps the prefix's own backslashes and joins everything after it with `/`, and the result is a path whose
    // components Rust no longer matches against the plain spelling — `is_file` answers `false` for a file that is
    // there.
    //
    // Measured on a real project, and it was the whole of one failure: every quoted include of
    // `E:\EmmyLuaCodeStyle\CodeFormatServer\src\main.cpp` — `Session/StandardIOSession.h`, `LanguageServer.h` —
    // resolved to nothing, so the closure of that file was **14 files instead of the program**, and every summary
    // that recorded an unresolved include was refused by the disk cache (`1046 of 1729 files` in one index run).
    // Both files are in the same directory as `main.cpp`; only the spelling of the path was wrong.
    //
    // `\\?\UNC\server\share` comes back as `\\server\share`, which is the same path in the spelling the rest of
    // this crate compares.
    let raw = path.to_string_lossy();
    let text: String = match raw.strip_prefix(r"\\?\UNC\") {
        Some(rest) => format!(r"\\{rest}"),
        None => match raw.strip_prefix(r"\\?\") {
            Some(rest) => rest.to_string(),
            None => raw.into_owned(),
        },
    };
    let text = text.as_str();

    // **The prefix is text, not a `std::path` component.** `Path::components()` reads a drive letter or a UNC root
    // only on Windows, so the rule this function exists for was invisible to a test run anywhere else — and a
    // rendering made on one machine may be read on another. Splitting the spelling itself makes the answer the same
    // everywhere, which is what "normalized" has to mean for two spellings to compare equal.
    let mut parts: Vec<String> = Vec::new();
    let mut rest: &str = text;

    if let Some(unc) = rest.strip_prefix(r"\\") {
        // `\\server\share\dir` — the first two segments are the root, and they are kept in that spelling.
        let mut segments = unc.split(['/', '\\']);
        let server = segments.next().unwrap_or_default();
        let share = segments.next().unwrap_or_default();
        if !server.is_empty() {
            parts.push(format!(r"\\{server}\{share}"));
            rest = unc
                .get(server.len() + 1 + share.len()..)
                .unwrap_or_default();
        }
    } else if rest.len() >= 2 && rest.as_bytes()[1] == b':' {
        // `C:` is a *prefix*, not a directory: `C:\a` is `C:/a`. A drive with no separator after it (`C:foo`) is
        // drive-relative, and the answer keeps the prefix as it was written.
        let drive = &rest[..2];
        rest = &rest[2..];
        let rooted = rest.starts_with('/') || rest.starts_with('\\');
        parts.push(if rooted {
            format!("{drive}/")
        } else {
            drive.to_string()
        });
    } else if rest.starts_with('/') || rest.starts_with('\\') {
        parts.push("/".to_string());
    }

    for segment in rest.split(['/', '\\']) {
        match segment {
            "" | "." => {}
            ".." => match parts.last() {
                // `..` above the root is defined to be the root: `/../a.h` and `/a.h` are one file. Above a
                // relative path it is kept, because there it changes what the path means.
                Some(last) if is_a_root(last) => {}
                Some(last) if last != ".." => {
                    parts.pop();
                }
                _ => parts.push("..".to_string()),
            },
            name => parts.push(name.to_string()),
        }
    }

    // A rooted part already carries its own trailing separator when it is a drive; joining it with `/`
    // would double the separator, so the pieces are concatenated around it rather than naive-joined.
    let mut joined = String::new();
    for part in &parts {
        if !joined.is_empty() && !joined.ends_with('/') {
            joined.push('/');
        }
        joined.push_str(part);
    }

    if case_insensitive {
        joined.to_lowercase()
    } else {
        joined
    }
}

/// **Is this part a root rather than a directory?** — `/`, `C:/`, and a UNC root (`\\server\share`). `..` at a root is
/// the root itself, and popping it would leave a relative path where an absolute one was written.
fn is_a_root(part: &str) -> bool {
    part == "/"
        || part.ends_with(":/")
        || (part.starts_with(r"\\") && part.matches('\\').count() >= 2)
}
/// Join a directory and a relative path, then normalize.
pub fn join_normalized(directory: &Path, relative: &Path, case_insensitive: bool) -> PathBuf {
    let joined = directory.join(relative);
    PathBuf::from(normalize_path(&joined, case_insensitive))
}

/// The directory a path lives in, normalized, or an empty path when there is none.
pub fn parent_normalized(path: &Path, case_insensitive: bool) -> PathBuf {
    match path.parent() {
        Some(parent) => PathBuf::from(normalize_path(parent, case_insensitive)),
        None => PathBuf::new(),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn normalization_folds_the_spellings_of_one_path() {
        let cases = [
            ("./a/b.h", "a/b.h"),
            ("a/./b.h", "a/b.h"),
            ("a/c/../b.h", "a/b.h"),
            ("a\\b.h", "a/b.h"),
            ("a//b.h", "a/b.h"),
        ];

        for (input, expected) in cases {
            assert_eq!(normalize_path(Path::new(input), false), expected, "{input}");
        }
    }

    #[test]
    fn normalization_keeps_what_it_cannot_resolve() {
        // Above the root, and above a relative path's start: `..` is part of the meaning.
        assert_eq!(normalize_path(Path::new("/../a.h"), false), "/a.h");
        assert_eq!(normalize_path(Path::new("../a.h"), false), "../a.h");
        assert_eq!(normalize_path(Path::new("a/../../b.h"), false), "../b.h");
    }

    #[test]
    fn normalization_can_fold_case() {
        assert_eq!(normalize_path(Path::new("A/B.H"), true), "a/b.h");
        assert_ne!(
            normalize_path(Path::new("A/B.H"), true),
            normalize_path(Path::new("A/B.H"), false)
        );
    }

    /// A drive prefix is part of the root, not a directory: `C:\a` is `C:/a` and never `C://a`, which would
    /// compare unequal to the same path written with forward slashes.
    #[test]
    fn a_drive_prefix_is_attached_to_the_root() {
        assert_eq!(normalize_path(Path::new("C:\\a\\b.h"), false), "C:/a/b.h");
        assert_eq!(normalize_path(Path::new("C:/a/b.h"), false), "C:/a/b.h");
        assert_eq!(normalize_path(Path::new("C:\\a\\..\\b.h"), false), "C:/b.h");
        assert_eq!(normalize_path(Path::new("C:\\..\\b.h"), false), "C:/b.h");
    }

    #[test]
    fn interning_gives_one_id_per_file() {
        let mut interner = PathInterner::new(false);

        let first = interner.intern(Path::new("a/b.h"));
        let again = interner.intern(Path::new("./a/b.h"));
        let other = interner.intern(Path::new("a/c.h"));

        assert_eq!(first, again, "two spellings of one path are one file");
        assert_ne!(first, other);
        assert_eq!(interner.len(), 2);
    }

    #[test]
    fn a_read_and_a_search_are_counted_separately() {
        // The two questions this double exists to answer, and they are not the same one: a file that was *read*
        // was parsed or hashed, and a path that was *looked for* was a candidate of some `#include`. A cache hit
        // is the case where the second number stays put.
        let files = MemoryFiles::new().with_file("/p/a.h", "int x;\n");

        assert_eq!(files.exists_of("/p/a.h"), 0);
        assert!(files.exists(Path::new("/p/a.h")));
        assert!(files.exists(Path::new("/p/./a.h")), "spellings fold");
        assert_eq!(files.exists_of("/p/a.h"), 2);
        assert_eq!(
            files.reads_of("/p/a.h"),
            0,
            "looking for a file is not reading it"
        );

        assert_eq!(files.read(Path::new("/p/a.h")).as_deref(), Some("int x;\n"));
        assert_eq!(files.reads_of("/p/a.h"), 1);
        assert_eq!(files.probes().len(), 2, "and the two logs are separate");
    }

    #[test]
    fn interning_folds_case_when_the_filesystem_does() {
        let mut interner = PathInterner::new(true);

        assert_eq!(
            interner.intern(Path::new("A.H")),
            interner.intern(Path::new("a.h"))
        );
    }

    /// A later spelling does not replace the stored one: a consumer showing the file's name shows the
    /// spelling that was seen first.
    #[test]
    fn the_first_spelling_of_a_path_is_the_one_remembered() {
        let mut interner = PathInterner::new(true);
        let id = interner.intern(Path::new("A.h"));
        interner.intern(Path::new("a.h"));

        assert_eq!(interner.path(id), Some(Path::new("A.h")));
    }

    #[test]
    fn memory_files_normalize_like_the_interner_does() {
        let memory = MemoryFiles::new().with_file("inc/a.h", "contents");

        assert!(memory.exists(Path::new("./inc/a.h")));
        assert!(memory.exists(Path::new("inc/b/../a.h")));
        assert_eq!(
            memory.read(Path::new("inc/a.h")).as_deref(),
            Some("contents")
        );
    }

    #[test]
    fn an_overlay_finds_a_buffer_before_the_disk() {
        let memory = MemoryFiles::new().with_file("a.h", "from memory");
        let disk = MemoryFiles::new().with_file("a.h", "from disk");
        let overlay = OverlayFiles::new(memory, disk);

        assert_eq!(
            overlay.read(Path::new("a.h")).as_deref(),
            Some("from memory")
        );
    }

    #[test]
    fn an_overlay_falls_through_to_the_disk() {
        let memory = MemoryFiles::new().with_file("a.h", "from memory");
        let disk = MemoryFiles::new().with_file("b.h", "from disk");
        let overlay = OverlayFiles::new(memory, disk);

        assert_eq!(overlay.read(Path::new("b.h")).as_deref(), Some("from disk"));
    }

    /// **The second asker pays a refcount bump and not a read.**
    ///
    /// The count is the assertion because the *answers* are the same either way: a layer that reads a file once
    /// and a layer that reads it three times produce identical analyses, and only the provider knows which
    /// happened.
    #[test]
    fn a_content_cache_reads_each_file_once() {
        let inner = MemoryFiles::new()
            .with_file("a.h", "contents")
            .with_file("b.h", "other");
        let files = CachedFiles::new(inner);

        let first = files.text(Path::new("a.h")).expect("read");
        let second = files.text(Path::new("a.h")).expect("read");
        assert_eq!(&*first, "contents");
        assert_eq!(first.as_ptr(), second.as_ptr(), "the same text, not a copy");
        assert_eq!(files.reads(), 1, "one read for two asks");
        assert_eq!(files.paths_read(), 1);

        // A `FileProvider` caller gets the trait's `String`, and that does not read again either.
        assert_eq!(files.read(Path::new("a.h")).as_deref(), Some("contents"));
        assert_eq!(files.reads(), 1);

        // **A file that is not there is remembered as missing.** An include search that keeps missing is the
        // common case while a project's configuration is unfinished, and one `stat`-and-fail per `#include` is
        // the difference between a completion list that appears and one that does not.
        assert_eq!(files.text(Path::new("missing.h")), None);
        assert_eq!(files.text(Path::new("missing.h")), None);
        assert_eq!(files.reads(), 2, "a.h once and missing.h once");

        // The other file is a read of its own — one per path, not one per run.
        assert_eq!(files.text(Path::new("b.h")).as_deref(), Some("other"));
        assert_eq!(files.paths_read(), 3);
    }

    /// **Invalidation is the caller's act**, and that is the whole validity argument for this layer.
    ///
    /// Nothing here looks at a timestamp: a file whose content changed while its mtime stood still is not a case
    /// it can get wrong, because it never asks. What it *can* get wrong is being told nothing — so an editor's
    /// `didChange` is a `reload`, and the next read sees the new text.
    #[test]
    fn a_content_cache_forgets_a_file_when_it_is_told_to() {
        let inner = MemoryFiles::new().with_file("a.h", "before");
        let files = CachedFiles::new(inner);
        assert_eq!(files.text(Path::new("a.h")).as_deref(), Some("before"));

        // The provider underneath is where a change would come from; this layer holds `a.h` until it is told.
        files.reload(Path::new("a.h"));
        assert_eq!(
            files.text(Path::new("a.h")).as_deref(),
            Some("before"),
            "the text is re-read, and the provider still says what it said"
        );
        assert_eq!(files.reads(), 2, "the second ask went to the provider");
    }

    /// Existence is **not** cached: it is a `stat`, and a run that starts before a file is written should see it
    /// appear. The hazard this layer exists for is two *contents* disagreeing, and there is no content here.
    #[test]
    fn a_content_cache_does_not_cache_existence() {
        let inner = MemoryFiles::new().with_file("a.h", "contents");
        let files = CachedFiles::new(inner);

        assert!(files.exists(Path::new("a.h")));
        assert!(!files.exists(Path::new("b.h")));
        assert_eq!(
            files.reads(),
            0,
            "existence is the provider's question, not the cache's"
        );
    }
}