cpp_code_analysis 0.4.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
//! The name index — declarations and macro definitions, **inverted** from "per file" to "per name".
//!
//! # Why this exists
//!
//! [`ProjectIndex`](super::ProjectIndex) stores what each file *says*: a list of declarations per file. Every
//! question a language server asks is the other way round — "which files declare `Widget`", "what does `ns::C`
//! hold", "who defines this macro". Answering those from the per-file lists is a scan of the whole project, and
//! the scan grows with the project instead of with the answer: on a large workspace one keystroke in the
//! workspace-symbol box walked every declaration of every file, allocating two strings for each.
//!
//! This is the table that turns the question around. It is **derived** from the summaries and the cooked readings
//! and never authoritative: [`ProjectIndex`](super::ProjectIndex) is the only writer, it updates the table in the
//! same call that changes a summary, and a posting only *points* at a fact (`file`, `slot`), so the fact itself is
//! read from where it lives and can never disagree with the table about what it says.
//!
//! # What is keyed
//!
//! ```text
//! by_name    bare name       → the facts that declare it        (locals are left out, as every name query does)
//! by_scope   qualified scope → the facts written directly in it (what a member list is made of)
//! definers   macro name      → the files that `#define` it
//! sorted     lowercased name → the spellings it has           (what a workspace search walks, in order)
//! ```
//!
//! # Postings are ordered, and that is a contract
//!
//! A posting names a **file by its sequence number** — the number the index gave the file when it first appeared,
//! never reused — and **which of the file's readings** it points into, and a list is sorted by `(file, reading,
//! entry)`. So a query that walks a list visits files in insertion order, which is the order the per-file scan
//! visited them in, and two runs over one project answer in one order. Within a file the own summary (reading 0) comes
//! before the programs that read it, because a file read as a program is a *second* answer about the same text.

use std::collections::{BTreeMap, HashMap, HashSet};
use std::ops::Bound;

use crate::summary::{DeclFact, MacroFact};

/// Where one fact lives: which file (by sequence number), which of its readings, and which entry of that list.
///
/// **A file has more than one reading**, and a posting says which one it was indexed from: `0` is the file's own
/// summary (the file read on its own), and `1..` are the programs that have read it as part of a translation unit, in
/// the order they did — see [`crate::ProjectIndex::insert_cooked_in_a_program`]. Two programs that read one header
/// under different macros file different declarations for it, and a posting that did not say which reading it came
/// from would point a lookup at another translation unit's list.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(crate) struct Posting {
    pub file: u32,
    pub reading: u32,
    slot: u32,
}

impl Posting {
    fn new(file: u32, reading: u32, index: usize) -> Self {
        debug_assert!(
            index < u32::MAX as usize,
            "a file with four billion declarations"
        );
        Posting {
            file,
            reading,
            slot: index as u32,
        }
    }

    /// The position in the list it points into.
    pub fn index(self) -> usize {
        self.slot as usize
    }
}

#[derive(Debug, Default)]
pub(super) struct NameIndex {
    by_name: HashMap<Box<str>, Vec<Posting>>,
    by_scope: HashMap<Box<str>, Vec<Posting>>,
    definers: HashMap<Box<str>, Vec<u32>>,
    /// The distinct names, keyed by their lowercase form and **in that order**. A symbol search is case-insensitive
    /// and reports alphabetically, so walking this map is walking the answer: the search stops after the first
    /// `limit` hits instead of ranking every name in the project. Kept in step with `by_name` — a key is here
    /// exactly while its posting list is.
    sorted: BTreeMap<Box<str>, Vec<Box<str>>>,
}

impl NameIndex {
    /// Add the facts of one of a file's readings — its own summary (reading `0`) or one program's reading of it.
    pub fn add_declarations(&mut self, file: u32, reading: u32, facts: &[DeclFact]) {
        for (index, fact) in facts.iter().enumerate() {
            let posting = Posting::new(file, reading, index);

            // A local names nothing another file can see, so it is not indexed by name — `matches` in the project
            // index refuses one for the same reason. A scope is different: the scope of a local is `None`, so there
            // is no scope to key it under and nothing to leave out.
            if !fact.local {
                self.add_name(&fact.name, posting);
            }
            if let Some(scope) = &fact.scope {
                insert_sorted(&mut self.by_scope, scope, posting);
            }
        }
    }

    fn add_name(&mut self, name: &str, posting: Posting) {
        let is_new = !self.by_name.contains_key(name);
        insert_sorted(&mut self.by_name, name, posting);

        if is_new {
            self.sorted
                .entry(lowercase(name).into_boxed_str())
                .or_default()
                .push(Box::from(name));
        }
    }

    fn drop_name(&mut self, name: &str, file: u32, reading: u32) {
        if !remove_range(&mut self.by_name, name, file, reading) {
            return;
        }

        let lowered = lowercase(name);
        if let Some(spellings) = self.sorted.get_mut(lowered.as_str()) {
            spellings.retain(|spelling| &**spelling != name);
            if spellings.is_empty() {
                self.sorted.remove(lowered.as_str());
            }
        }
    }

    /// Take back what [`NameIndex::add_declarations`] added for the same file and reading.
    ///
    /// Takes the facts rather than a file number alone because that is what makes it cheap: the keys to visit are
    /// exactly the names in the list being dropped, so an edit to one file touches the lists of the names *it*
    /// declared and not every list in the project.
    pub fn remove_declarations(&mut self, file: u32, reading: u32, facts: &[DeclFact]) {
        let mut names: HashSet<&str> = HashSet::new();
        let mut scopes: HashSet<&str> = HashSet::new();

        for fact in facts {
            if !fact.local {
                names.insert(fact.name.as_str());
            }
            if let Some(scope) = &fact.scope {
                scopes.insert(scope.as_str());
            }
        }

        for name in names {
            self.drop_name(name, file, reading);
        }
        for scope in scopes {
            let _ = remove_range(&mut self.by_scope, scope, file, reading);
        }
    }

    /// Record which macros a file defines.
    pub fn add_macros(&mut self, file: u32, macros: &[MacroFact]) {
        for fact in macros.iter().filter(|fact| fact.kind.is_definition()) {
            let files = match self.definers.get_mut(fact.name.as_str()) {
                Some(files) => files,
                None => self
                    .definers
                    .entry(Box::from(fact.name.as_str()))
                    .or_default(),
            };

            match files.binary_search(&file) {
                Ok(_) => {}
                Err(at) => files.insert(at, file),
            }
        }
    }

    /// Take back what [`NameIndex::add_macros`] added for this file.
    pub fn remove_macros(&mut self, file: u32, macros: &[MacroFact]) {
        for name in macros
            .iter()
            .filter(|fact| fact.kind.is_definition())
            .map(|fact| fact.name.as_str())
            .collect::<HashSet<_>>()
        {
            let Some(files) = self.definers.get_mut(name) else {
                continue;
            };
            if let Ok(at) = files.binary_search(&file) {
                files.remove(at);
            }
            if files.is_empty() {
                self.definers.remove(name);
            }
        }
    }

    /// Every fact whose bare name is `name`, in `(file, slot)` order.
    pub fn named(&self, name: &str) -> &[Posting] {
        self.by_name.get(name).map(Vec::as_slice).unwrap_or(&[])
    }

    /// Every fact written directly in the scope `scope`, in `(file, slot)` order.
    pub fn scoped(&self, scope: &str) -> &[Posting] {
        self.by_scope.get(scope).map(Vec::as_slice).unwrap_or(&[])
    }

    /// The files that define the macro `name`, by sequence number, ascending.
    pub fn definers_of(&self, name: &str) -> &[u32] {
        self.definers.get(name).map(Vec::as_slice).unwrap_or(&[])
    }

    /// The spellings whose lowercase form is exactly `lowered`.
    pub fn spellings_of(&self, lowered: &str) -> Option<&[Box<str>]> {
        self.sorted.get(lowered).map(Vec::as_slice)
    }

    /// Every lowercase name from `lowered` on, in order, with its spellings.
    pub fn lowered_from<'a>(
        &'a self,
        lowered: &str,
    ) -> impl Iterator<Item = (&'a str, &'a [Box<str>])> + 'a {
        self.sorted
            .range::<str, _>((Bound::Included(lowered), Bound::Unbounded))
            .map(|(key, spellings)| (&**key, spellings.as_slice()))
    }

    /// How many distinct names are indexed — for the probes' tables.
    pub fn distinct_names(&self) -> usize {
        self.by_name.len()
    }

    /// **What the inverted index costs**, in the same units [`crate::MemoryReport`] uses.
    ///
    /// A posting is 12 bytes (`file`, `reading`, `slot`), a key is its own string plus the `Vec`'s three words, and
    /// the estimate counts exactly those: `postings × size_of::<Posting>()`, the keys' bytes, one `Vec` header per
    /// key. It does **not** count the `HashMap`'s own table (open addressing, ~1.14 × capacity × 24 bytes), which is
    /// the slack `memory.rs`'s module note already declares is not accounted.
    pub fn accounting(&self) -> NameIndexCost {
        let postings = |map: &HashMap<Box<str>, Vec<Posting>>| {
            let slots: usize = map.values().map(Vec::capacity).sum();
            let keys: usize = map.keys().map(|key| key.len()).sum();
            let entries = map.len();
            // The payload, the keys, and one `Vec` header per key.
            let bytes = slots * std::mem::size_of::<Posting>()
                + keys
                + entries * std::mem::size_of::<Vec<Posting>>();
            (entries, slots, bytes)
        };
        let (name_entries, name_postings, name_bytes) = postings(&self.by_name);
        let (scope_entries, scope_postings, scope_bytes) = postings(&self.by_scope);
        let definers: usize = self.definers.values().map(Vec::capacity).sum();
        let definer_keys: usize = self.definers.keys().map(|key| key.len()).sum();
        let definer_bytes = definers * std::mem::size_of::<u32>()
            + definer_keys
            + self.definers.len() * std::mem::size_of::<Vec<u32>>();
        let spellings: Vec<&Box<str>> = self.sorted.values().flatten().collect();
        let sorted_bytes = self.sorted.keys().map(|key| key.len()).sum::<usize>()
            + spellings
                .iter()
                .map(|spelling| spelling.len())
                .sum::<usize>()
            + self.sorted.len() * std::mem::size_of::<Vec<Box<str>>>()
            + spellings.len() * std::mem::size_of::<Box<str>>();
        NameIndexCost {
            name_entries,
            name_postings,
            scope_entries,
            scope_postings,
            definer_entries: self.definers.len(),
            definers,
            spelling_entries: spellings.len(),
            bytes: name_bytes + scope_bytes + definer_bytes + sorted_bytes,
        }
    }
}

/// **What [`NameIndex`] costs**, split so that a report can name the part that grew.
///
/// The two posting maps are the same order of magnitude and different questions — `by_name` is "who declares this
/// name", `by_scope` is "what is declared in this scope" — so a project whose classes grow but whose name vocabulary
/// does not shows up in one and not the other.
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub struct NameIndexCost {
    /// Distinct names in `by_name`.
    pub name_entries: usize,
    /// Postings across them — one per non-local declaration.
    pub name_postings: usize,
    /// Distinct scopes in `by_scope`.
    pub scope_entries: usize,
    /// Postings across those.
    pub scope_postings: usize,
    /// Distinct macro names in `definers`.
    pub definer_entries: usize,
    /// Files across those lists.
    pub definers: usize,
    /// Spellings in `sorted` — the case-insensitive search's own copy of every name.
    pub spelling_entries: usize,
    /// The estimated bytes of all four maps.
    pub bytes: usize,
}

/// Insert keeping the list sorted. A file that is new has the largest sequence number, so the common case is a push.
fn insert_sorted(map: &mut HashMap<Box<str>, Vec<Posting>>, key: &str, posting: Posting) {
    let list = match map.get_mut(key) {
        Some(list) => list,
        None => map.entry(Box::from(key)).or_default(),
    };

    match list.last() {
        Some(last) if *last >= posting => {
            let at = list.partition_point(|held| *held < posting);
            list.insert(at, posting);
        }
        _ => list.push(posting),
    }
}

/// Drop one file's postings of one reading from `key`'s list — they are contiguous, so this is one `drain`.
///
/// Answers whether the list is now empty and was dropped.
fn remove_range(
    map: &mut HashMap<Box<str>, Vec<Posting>>,
    key: &str,
    file: u32,
    reading: u32,
) -> bool {
    let Some(list) = map.get_mut(key) else {
        return false;
    };

    // A list is sorted by `(file, reading, slot)`, so the block to drop is one interval: the file's, then that
    // reading's inside it.
    let start = list.partition_point(|held| held.file < file);
    let end = start + list[start..].partition_point(|held| held.file == file);
    let begin = start + list[start..end].partition_point(|held| held.reading < reading);
    let finish = begin + list[begin..end].partition_point(|held| held.reading == reading);

    list.drain(begin..finish);

    if list.is_empty() {
        map.remove(key);
        return true;
    }

    false
}

/// `text` lowercased — the form the sorted map is keyed by, and the form a search is compared in.
pub(super) fn lowercase(text: &str) -> String {
    if text.is_ascii() {
        text.to_ascii_lowercase()
    } else {
        text.to_lowercase()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::cache::SummaryKey;
    use crate::index::summarize;
    use std::path::Path;

    fn facts_of(source: &str) -> Vec<DeclFact> {
        summarize(Path::new("/p/a.h"), source, SummaryKey::new(0, 0)).declarations
    }

    fn held(index: &NameIndex, name: &str) -> Vec<(u32, u32)> {
        index
            .named(name)
            .iter()
            .map(|posting| (posting.file, posting.reading))
            .collect()
    }

    #[test]
    fn a_list_stays_in_file_order_whatever_order_files_arrive_in() {
        let facts = facts_of("int x;\n");
        let mut index = NameIndex::default();
        index.add_declarations(3, 0, &facts);
        index.add_declarations(1, 0, &facts);
        index.add_declarations(2, 1, &facts);
        index.add_declarations(2, 0, &facts);

        assert_eq!(held(&index, "x"), vec![(1, 0), (2, 0), (2, 1), (3, 0)]);
    }

    #[test]
    fn removing_one_reading_of_a_file_leaves_the_other() {
        let facts = facts_of("namespace ns { int x; int y; }\n");
        let mut index = NameIndex::default();
        index.add_declarations(1, 0, &facts);
        index.add_declarations(1, 1, &facts);
        index.add_declarations(2, 0, &facts);
        let scoped = index.scoped("ns").len();
        assert_eq!(scoped, 6, "two facts in the scope, three readings");

        index.remove_declarations(1, 1, &facts);
        assert_eq!(held(&index, "x"), vec![(1, 0), (2, 0)]);
        assert_eq!(index.scoped("ns").len(), 4);

        index.remove_declarations(1, 0, &facts);
        index.remove_declarations(2, 0, &facts);
        assert!(index.named("x").is_empty());
        assert!(index.scoped("ns").is_empty());
        assert_eq!(
            index.distinct_names(),
            0,
            "an emptied list is dropped, not kept as an empty entry"
        );
    }

    #[test]
    fn a_local_has_no_name_entry() {
        let facts = facts_of("void f() { int inner; }\n");
        assert!(
            facts.iter().any(|fact| fact.name == "inner" && fact.local),
            "the fixture has a local"
        );

        let mut index = NameIndex::default();
        index.add_declarations(1, 0, &facts);

        assert!(index.named("inner").is_empty());
        assert_eq!(index.named("f").len(), 1);
    }

    #[test]
    fn a_posting_points_at_the_slot_it_was_made_for() {
        let facts = facts_of("int a;\nint b;\n");
        let cooked = facts_of("int b;\n");
        let mut index = NameIndex::default();
        index.add_declarations(7, 0, &facts);
        index.add_declarations(7, 1, &cooked);

        let b = index.named("b");
        assert_eq!((b[0].index(), b[0].reading), (1, 0));
        assert_eq!((b[1].index(), b[1].reading), (0, 1));
    }

    #[test]
    fn the_sorted_names_are_in_step_with_the_lists() {
        let upper = facts_of("int Size;\n");
        let lower = facts_of("int size;\n");
        let mut index = NameIndex::default();
        index.add_declarations(1, 0, &upper);
        index.add_declarations(2, 0, &lower);
        index.add_declarations(3, 0, &lower);

        let spellings = |index: &NameIndex| -> Vec<String> {
            index
                .spellings_of("size")
                .map(|held| held.iter().map(|spelling| spelling.to_string()).collect())
                .unwrap_or_default()
        };
        assert_eq!(
            spellings(&index).len(),
            2,
            "two spellings, one lowercase key: {:?}",
            spellings(&index)
        );

        index.remove_declarations(2, 0, &lower);
        assert_eq!(spellings(&index).len(), 2, "file 3 still declares `size`");

        index.remove_declarations(3, 0, &lower);
        assert_eq!(spellings(&index), vec!["Size".to_string()]);

        index.remove_declarations(1, 0, &upper);
        assert!(index.spellings_of("size").is_none());
        assert_eq!(index.lowered_from("").count(), 0);
    }

    #[test]
    fn a_walk_from_a_key_is_in_lowercase_order() {
        let mut index = NameIndex::default();
        for (file, source) in [
            "int banana;\n",
            "int Apple;\n",
            "int cherry;\n",
            "int apple2;\n",
        ]
        .iter()
        .enumerate()
        {
            index.add_declarations(file as u32, 0, &facts_of(source));
        }

        let keys: Vec<&str> = index.lowered_from("apple").map(|(key, _)| key).collect();
        assert_eq!(keys, vec!["apple", "apple2", "banana", "cherry"]);
    }

    #[test]
    fn the_definers_of_a_macro_are_the_files_that_define_it() {
        let define = summarize(
            Path::new("/p/a.h"),
            "#define M 1\n#define M 2\n",
            SummaryKey::new(0, 0),
        );
        let use_only = summarize(
            Path::new("/p/b.h"),
            "#ifdef M\n#endif\n",
            SummaryKey::new(0, 0),
        );

        let mut index = NameIndex::default();
        index.add_macros(5, &define.macros);
        index.add_macros(2, &define.macros);
        index.add_macros(9, &use_only.macros);
        assert_eq!(
            index.definers_of("M"),
            &[2, 5],
            "sorted, once per file, and a use is not a definition"
        );

        index.remove_macros(5, &define.macros);
        assert_eq!(index.definers_of("M"), &[2]);
        index.remove_macros(2, &define.macros);
        assert!(index.definers_of("M").is_empty());
    }
}