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
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
//! 找引用:一个宏的名字在项目里出现在哪些位置。
//!
//! `macro_across_files` 回答"游标下的名字定义在哪",这一层回答反过来的那个问题——**哪些位置上的这个名字
//! 指的是它**。重命名需要的正是这个列表,而它是第一个需要**读文件正文**的查询。
//!
//! # 为什么它需要 provider,而别的查询不需要
//!
//! 摘要里存的是**声明与指令**,没有标识符位置:`DeclFact` 说"某处声明了 `Widget`",却不说"第 812 个字节
//! 处写着 `Widget`"。所以"名字在哪儿出现过"这件事,索引答不了——它只能从文件正文里读出来。
//!
//! 这就带出这一层真正的设计问题:**一个项目里找一次引用要读多少东西。** 答案是一段阶梯,每一级都比上一级
//! 便宜,而且每一级都是**可靠**的(不是启发式):
//!
//! ```text
//! 1. 候选集    只有能看见某个定义的文件才可能是用户:定义所在文件 + 它们的传递反向 include 闭包
//! 2. 文本预筛  名字不是这个文件正文的子串,就一个标识符也不可能叫这个名字 → 连词法都不用做
//! 3. 词法      CppLexer 一遍:注释和字符串是**一个 token**,所以它们里的名字根本不会出现成 Identifier
//! 4. 精确判定  每个命中问一次**宏环境**(每个文件算一次):它是不是宏、是哪一条 #define
//! ```
//!
//! 第 3 级是这一层能成立的关键:**注释与字符串不需要解析就能排除**,而"用文本子串找引用"最大的假阳性
//! 正是它们。第 4 级是**唯一**不靠形状而是靠语义的一步,也正因为有它,第 2、3 级可以宽松。
//!
//! 要不要在摘要里存一张"标识符位置表"(那样就不必读正文)是一个**量出来的问题**,不是设计偏好:
//! `examples/find_references.rs` 把上面四级各自的代价打出来, 记着结论。
//!
//! # 它刻意不做的事
//!
//! * **不找普通名字的引用**。一个宏的名字是**文本**层面的东西:预处理器只有一张名字表,出现即替换。普通
//!   名字(`Widget`、`w`)的引用要问"这个偏移处的这个名字解析到那条声明吗",那需要每个候选文件的**作用域**,
//!   也就是每个候选文件一次解析——比这一层贵一个数量级。位置表那件事正是为它准备的。
//! * **不判断引用所在区域是否被编译**。一次引用是"这个名字在这里指的是这个宏",与那段代码在 `#if` 的哪一支
//!   无关:重命名两边都要改。
//! * **不猜**。命中只有三种归宿:确定是它(`Use`)、确定不是(计数进 `rejected`)、可能但说不准
//!   (`Uncertain` 带 `UnknownReason`)。

use std::collections::{HashMap, HashSet, VecDeque};
use std::path::PathBuf;

use cpp_parser::{CppLexer, CppTokenKind, LexerConfig, SourceRange};

use crate::file::paths::{FileProvider, normalize_path};
use crate::index::ProjectIndex;
use crate::summary::MacroKind;
use crate::symbol::{Known, UnknownReason};

/// How many candidate files one find-references will read.
///
/// The same shape as [`crate::IncludeBudget`] and for the same reason: a bound that is **reported** rather than
/// enforced quietly. A standard-library closure is a few hundred files and a project index is rarely past a few
/// thousand, so the default is far past anything measured — and a caller that hits it is told through
/// [`MacroReferences::not_looked_at`], because "there are no more references" and "I stopped looking" are two
/// different answers.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ReferenceBudget {
    pub max_files: usize,
}

impl Default for ReferenceBudget {
    fn default() -> Self {
        ReferenceBudget { max_files: 4096 }
    }
}

/// Every place a macro's name is written, and what each one turned out to be.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MacroReferences {
    /// The name asked about.
    pub name: String,
    /// The files with at least one reference, in path order — so that two runs over one project answer the same
    /// thing in the same order.
    pub files: Vec<FileReferences>,
    /// Candidate files that were read and lexed.
    pub looked_at: usize,
    /// Candidate files whose text does not contain the name at all, which is the cheap filter's work: reading
    /// them is one `read` and no lexing.
    pub without_the_name: usize,
    /// Identifier occurrences of the name that are **not** this macro: a variable of the same name, a function, or
    /// the name after an `#undef`. Counted rather than dropped silently, because "we looked and rejected these" is
    /// a different statement from "there was nothing to look at".
    pub rejected: usize,
    /// Candidate files the budget stopped before.
    pub not_looked_at: usize,
    /// Candidate files that could not be read: deleted between the index and the query.
    pub unreadable: Vec<PathBuf>,
}

/// The references written in one file.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FileReferences {
    pub file: PathBuf,
    /// In source order.
    pub references: Vec<Reference>,
}

/// One place the name is written.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Reference {
    pub range: SourceRange,
    pub kind: ReferenceKind,
}

/// What a place turned out to be.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ReferenceKind {
    /// The `#define` itself. Renaming edits it.
    Definition,
    /// An `#undef`: the name's history, and part of what a rename has to keep in step.
    Undefinition,
    /// An identifier the preprocessor replaces. `resolved_to` is the file whose `#define` is in force **at that
    /// offset**, which is not always the one the query started from: the same name can be defined twice, in two
    /// branches, and a rename edits both because the name is one name.
    Use { resolved_to: PathBuf },
    /// A place the name is a macro's, but not certainly *this* one: it is reached through a conditional
    /// `#include`, or through an `#if`. A caller that shows these must label them; a caller that edits them is
    /// guessing, which is why [`MacroReferences::rename`] leaves them alone.
    Uncertain(UnknownReason),
}

/// One edit a rename would make.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Rename {
    pub file: PathBuf,
    pub range: SourceRange,
    /// What replaces the range — the new name.
    pub replacement: String,
}

impl MacroReferences {
    /// How many references were found, across every file.
    pub fn total(&self) -> usize {
        self.files.iter().map(|file| file.references.len()).sum()
    }

    /// How many files the candidate rule named.
    ///
    /// An accessor rather than arithmetic at each call site, because the three fields it adds up mean three
    /// different things and a caller that forgets one of them gets a number that looks plausible: the first
    /// version of this module's own probe computed "candidates" as `looked_at + without_the_name` — which counts the
    /// skipped files twice and leaves the budget's files out.
    pub fn candidates(&self) -> usize {
        self.looked_at + self.not_looked_at + self.unreadable.len()
    }

    /// How many candidate files were **lexed**: the ones that got past the text filter.
    pub fn lexed(&self) -> usize {
        self.looked_at - self.without_the_name
    }

    /// How many of them a rename would **not** touch, because they might be something else.
    pub fn uncertain(&self) -> usize {
        self.files
            .iter()
            .flat_map(|file| &file.references)
            .filter(|reference| matches!(reference.kind, ReferenceKind::Uncertain(_)))
            .count()
    }

    /// The edits that rename this macro to `to`.
    ///
    /// The definition, the `#undef`s and the certain uses — and **not** the uncertain ones, which is a decision
    /// rather than an omission: an uncertain reference is a place where the name might be a variable, or might be
    /// another macro's, and an edit there is a change to code the user did not ask about. A caller that wants to
    /// show them can, through [`MacroReferences::files`]; a caller that renames cannot do it safely.
    ///
    /// A rename that would edit nothing is not an error: a macro only its own `#define` mentions is a macro with
    /// one reference, and that is the answer.
    pub fn rename(&self, to: &str) -> Vec<Rename> {
        let mut edits = Vec::new();

        for file in &self.files {
            for reference in &file.references {
                let certain = matches!(
                    reference.kind,
                    ReferenceKind::Definition
                        | ReferenceKind::Undefinition
                        | ReferenceKind::Use { .. }
                );

                if certain {
                    edits.push(Rename {
                        file: file.file.clone(),
                        range: reference.range,
                        replacement: to.to_string(),
                    });
                }
            }
        }

        edits
    }
}

/// Every place `name` is written as a macro, across the files the index holds.
///
/// # The candidate rule, and what it is worth
///
/// A file can only use a macro it can **see**: the name has to be `#define`d before the use, either in the file or
/// in something it includes. So the candidates are the files that define the name and everything that
/// **transitively includes** one of them. That is a sound narrowing rather than a guess — a file outside it has a
/// use of the name only if the name reaches it some other way, and the include graph is the only way there is.
///
/// What it costs is stated where it is paid: a file that writes an `#include` that did not resolve is not an
/// includer of anything, so it is not a candidate — correctly, because a compiler reading it would not see the
/// macro either.
///
/// # What it answers
///
/// * `Yes(references)` — the name is a macro somewhere in the index. The list may be short: see below.
/// * `Unknown(NotDeclaredHere)` — no file in the index defines the name. **Not** "no such macro": the index holds
///   the files it has been asked about, and under lazy indexing that is the difference between "not here" and
///   "not read yet" ([`crate::Session::pending`] is how a caller tells them apart).
pub fn macro_references<F: FileProvider>(
    index: &ProjectIndex,
    files: &F,
    name: &str,
    budget: ReferenceBudget,
) -> Known<MacroReferences> {
    let definers = files_defining(index, name);

    if definers.is_empty() {
        return Known::Unknown(UnknownReason::NotDeclaredHere(Box::from(name)));
    }

    let mut answer = MacroReferences {
        name: name.to_string(),
        files: Vec::new(),
        looked_at: 0,
        without_the_name: 0,
        rejected: 0,
        not_looked_at: 0,
        unreadable: Vec::new(),
    };

    for path in candidates(index, &definers, budget, &mut answer) {
        // The facts first, and they do not depend on the text: a `#define` is a reference to its own name by
        // definition, and a file that writes one necessarily contains the name — but reading the facts first keeps
        // the two halves of the answer independent of the order they are discovered in.
        let mut references: Vec<Reference> = index
            .summary(&path)
            .map(|summary| {
                summary
                    .macros
                    .iter()
                    .filter(|fact| fact.name == name)
                    .map(|fact| Reference {
                        range: fact.range,
                        kind: match fact.kind {
                            MacroKind::Definition => ReferenceKind::Definition,
                            MacroKind::Undefinition => ReferenceKind::Undefinition,
                        },
                    })
                    .collect()
            })
            .unwrap_or_default();

        let Some(text) = files.read(&path) else {
            // Readable when it was indexed, gone now. One deleted file does not stop the answer; the caller is told.
            answer.unreadable.push(path);
            continue;
        };

        answer.looked_at += 1;

        // The cheap filter, and it is exact rather than heuristic: an identifier token's text is a slice of the
        // file's text, so a file that does not contain the name as a substring cannot contain it as an identifier.
        if !text.contains(name) {
            answer.without_the_name += 1;
        } else {
            // A `#define`'s fact carries the **name's** range, so the identifier token for it is the same range and
            // has to be skipped — otherwise every definition would be reported twice.
            let claimed: HashSet<(usize, usize)> = references
                .iter()
                .filter(|reference| reference.kind == ReferenceKind::Definition)
                .map(|reference| (reference.range.start_offset, reference.range.end_offset()))
                .collect();

            // An `#undef`'s fact carries the **whole directive**, because the directive reader does not track where
            // the name is inside it — and the whole directive is the wrong thing for a rename to replace: it would
            // delete the `#undef`. The lexer is the thing that does know, so a hit inside one of these ranges is not
            // a use and not a rejection: it is the position that fact was missing.
            let undefinitions: Vec<usize> = references
                .iter()
                .enumerate()
                .filter(|(_, reference)| reference.kind == ReferenceKind::Undefinition)
                .map(|(index, _)| index)
                .collect();

            // The environment is computed **once per file** and then asked about every hit. Asking
            // `macro_definition` per hit instead was the first version of this function, and the measurement is what
            // killed it: 4 079 hits in one file, each walking the include graph, took **3.8 s** — for an answer
            // whose every input was the same walk. Lexing those files took 15 ms.
            let environment = index.macro_environment(name, &path);

            for range in identifiers(&text, name) {
                if claimed.contains(&(range.start_offset, range.end_offset())) {
                    continue;
                }

                if let Some(named) = undefinitions
                    .iter()
                    .copied()
                    .find(|index| covers(references[*index].range, range))
                {
                    references[named].range = range;
                    continue;
                }

                match environment.is_a_macro_at(range.start_offset) {
                    // It is a macro here, and it is a *definition* that settles it: this is a use.
                    Known::Yes(found) => references.push(Reference {
                        range,
                        kind: ReferenceKind::Use {
                            resolved_to: found.file().to_path_buf(),
                        },
                    }),
                    // A macro, but reached through an `#if`: renaming it is a guess.
                    Known::Unknown(reason @ UnknownReason::ConditionalCompilation) => {
                        references.push(Reference {
                            range,
                            kind: ReferenceKind::Uncertain(reason),
                        });
                    }
                    // Everything else is "not this macro here": a variable of the same name, a name `#undef`ed
                    // above this point, or a name whose only definition is behind an include that did not resolve.
                    // The most interesting rejection there is, because the text looks exactly like a use.
                    Known::Unknown(_) | Known::No => answer.rejected += 1,
                }
            }
        }

        if !references.is_empty() {
            references.sort_by_key(|reference| reference.range.start_offset);
            answer.files.push(FileReferences {
                file: path,
                references,
            });
        }
    }

    answer.files.sort_by(|one, other| one.file.cmp(&other.file));
    Known::Yes(answer)
}

/// The files whose own `#define`s are what the name means somewhere.
fn files_defining(index: &ProjectIndex, name: &str) -> Vec<PathBuf> {
    index.files_defining_macro(name)
}

/// The files that could use the name: the definers, and everything that transitively includes one.
///
/// The walk is over **reverse** include edges — the ones the index derives — because the question is the
/// opposite of the one an include answers: not "what does this file see" but "who sees this file". A file reached
/// twice is one file, which is what makes a diamond cheap and a cycle terminate.
fn candidates(
    index: &ProjectIndex,
    definers: &[PathBuf],
    budget: ReferenceBudget,
    answer: &mut MacroReferences,
) -> Vec<PathBuf> {
    let mut found: Vec<PathBuf> = Vec::new();
    let mut seen: HashSet<String> = HashSet::new();
    let mut pending: VecDeque<PathBuf> = definers.iter().cloned().collect();

    while let Some(path) = pending.pop_front() {
        if !seen.insert(normalize_path(&path, cfg!(windows))) {
            continue;
        }

        if found.len() >= budget.max_files {
            answer.not_looked_at += 1;
            continue;
        }

        found.push(path.clone());
        pending.extend(index.includers_of(&path));
    }

    // Path order, so that a second run answers in the same order: `includers_of` is a `BTreeSet` and the queue is
    // a `VecDeque`, and neither is a promise about the order two diamond paths arrive in.
    found.sort();
    found
}

/// Is `inner` inside `outer`?
fn covers(outer: SourceRange, inner: SourceRange) -> bool {
    outer.start_offset <= inner.start_offset && inner.end_offset() <= outer.end_offset()
}

/// Every identifier token of `text` whose spelling is exactly `name`.
///
/// The lexer rather than a text scan, and that is the whole reason this layer is affordable: a comment is **one
/// token** and a string literal is one token, so the two commonest false positives of "search the text for the
/// name" cannot reach this function at all. A text scan plus a hand-written "am I inside a comment" state machine
/// would be a second implementation of the lexer, and it would disagree with the parser about raw strings,
/// continuations, and line comments ending at a `\`-continued newline.
fn identifiers(text: &str, name: &str) -> Vec<SourceRange> {
    let mut errors = Vec::new();
    let mut lexer = CppLexer::new(text, LexerConfig::default(), &mut errors);

    lexer
        .tokenize()
        .into_iter()
        .filter(|token| token.kind == CppTokenKind::Identifier)
        .filter(|token| text.get(token.range.start_offset..token.range.end_offset()) == Some(name))
        .map(|token| token.range)
        .collect()
}

/// **Every place a symbol's name is written** — the other half of find-references, and the half that was missing.
///
/// # What it was
///
/// Only [`macro_references`] existed. The handler asked it, and a name that is not a macro fell straight through to
/// an empty list: measured on a real file, `class Sux` answered **0 references** with `Sux sux;` two lines below it,
/// and `sux` answered 0 with `sux.print()` on the next line. A user who renames on that answer changes the
/// declaration and nothing else — the failure mode the macro version's design note calls out, in the one place a
/// user is most likely to hit it.
///
/// # The candidate rule, and why it is sound for a symbol too
///
/// The macro rule is "a file can only use a name it can **see**", and for a symbol the same sentence holds with a
/// different mechanism: a use of `Sux` outside the file that declares it has the declaration in scope, and the way
/// a declaration gets into scope is an `#include`. So the candidates are the declaring file and everything that
/// **transitively includes** it — the reverse-include walk [`candidates`] already does.
///
/// One case the rule does not cover, and it is stated rather than hidden: a symbol declared in a file that does
/// **not** include the header — a second translation unit writing its own `void helper();` — uses the name and is
/// not a candidate. Such a file declares the same qualified name, so it is added by name as well; what stays out is
/// a use in a third file that includes neither.
///
/// # What it answers
///
/// * `Yes(references)` — the declaration's own name is in the list, as [`SymbolReferenceKind::Declaration`], so a
///   caller that wants uses only filters it out rather than asking a second question.
/// * `Unknown(NotDeclaredHere)` — the caller could not say *which* symbol the cursor is on. Not "no references":
///   this layer never guesses a symbol from a spelling, which is the whole reason the cursor is resolved first.
pub fn symbol_references<F: FileProvider>(
    index: &ProjectIndex,
    files: &F,
    symbol: &SymbolToFind,
    budget: ReferenceBudget,
) -> Known<SymbolReferences> {
    let mut answer = SymbolReferences {
        name: symbol.name.clone(),
        qualified: symbol.qualified.clone(),
        declared_in: symbol.declared_in.clone(),
        files: Vec::new(),
        looked_at: 0,
        without_the_name: 0,
        not_looked_at: 0,
        unreadable: Vec::new(),
    };

    // **Every place the spelling itself is declared**, and by which qualified name — one posting-list read for the
    // whole query, so that the per-file filter below is a lookup rather than a second query. See the use site for
    // what it decides and why it is the only semantic call this layer can make without a parse.
    let declared_at = declarations_of_the_spelling(index, symbol);

    for path in symbol_candidates(index, symbol, budget, &mut answer) {
        // **The filter first, and it is what the read was for.** A candidate is every file that can *see* the
        // declaration — the declaring file and everything that transitively includes it — and the loop below reads
        // each one whole before it can ask whether the name is even written there. The summary already carries a
        // Bloom filter over the identifiers the file mentions ([`crate::FileSummary::use_filter`]), so a file that
        // cannot contain the name is skipped without a read.
        //
        // **A `false` here is certain**: the filter was built from every identifier token in the file, so a name it
        // does not contain is a name not written there. A `true` is "read it and see" — a false positive costs
        // exactly the read this used to cost unconditionally, and there is no false negative to be wrong about.
        //
        // A summary with no filter (an entry written before the field existed, a file the index has not read) says
        // `true`, which is the safe direction and the reason this can be added without invalidating anything.
        if let Some(summary) = index.summary(&path)
            && !crate::summary::use_filter_might_contain(&summary.use_filter, &symbol.last_segment)
        {
            answer.without_the_name += 1;
            continue;
        }

        let Some(text) = files.read(&path) else {
            answer.unreadable.push(path);
            continue;
        };

        // **The cheap filter first, and it is worth its line**: a candidate file that does not contain the
        // spelling at all needs no lexing, and in a header-heavy project most candidates are like that.
        if !text.contains(&symbol.last_segment) {
            answer.without_the_name += 1;
            continue;
        }

        answer.looked_at += 1;
        let here = identifiers(&text, &symbol.last_segment);
        if here.is_empty() {
            answer.without_the_name += 1;
            continue;
        }

        // **An occurrence that is another entity's declaration is not a reference to this one.** The lexer finds
        // every spelling; the index knows which offsets are *declarations*, and of what — so the one thing this
        // layer can decide without a parse is whether a hit is somebody else's name. Measured on a real two-file
        // project, `printf`'s reference list held `Name::printf`'s declaration **and** its out-of-class definition:
        // two places a rename would have edited, and neither of them the symbol the cursor was on.
        //
        // A declaration of the **same qualified name** is kept, which is what a redeclaration is (`extern int n;`
        // written in two headers), and so is every occurrence that is not a declaration name at all — that is a use,
        // and deciding *which* entity a use belongs to needs its file's scopes, which is the parse this layer does
        // not do (see the module documentation).
        let names_declared_here = declared_at.get(&normalize_path(&path, cfg!(windows)));

        let references: Vec<Reference> = here
            .into_iter()
            .filter(|range| {
                match names_declared_here.and_then(|declared| declared.get(&range.start_offset)) {
                    Some(qualified) => *qualified == symbol.qualified,
                    None => true,
                }
            })
            .map(|range| Reference {
                kind: if normalize_path(&path, cfg!(windows))
                    == normalize_path(&symbol.declared_in, cfg!(windows))
                    && range.start_offset == symbol.name_at
                {
                    ReferenceKind::Definition
                } else {
                    ReferenceKind::Use {
                        resolved_to: symbol.declared_in.clone(),
                    }
                },
                range,
            })
            .collect();

        answer.files.push(FileReferences {
            file: path,
            references,
        });
    }

    answer
        .files
        .sort_by(|left, right| left.file.cmp(&right.file));
    Known::Yes(answer)
}

/// **Where each declaration of a spelling starts, and what it is called** — by normalized file, then by offset.
///
/// The answer to the one question a lexer cannot ask: of the occurrences of `printf` in a file, which are
/// *declarations*, and of what? The index keeps a fact per declaration, so this is a posting-list read
/// ([`ProjectIndex::every_fact_named`]) and no parse.
///
/// The value is the declaration's **qualified** name, which is the identity two same-spelled declarations do not
/// share: `printf` at file scope and `Name::printf` inside a class are two entities that a rename must keep apart.
fn declarations_of_the_spelling(
    index: &ProjectIndex,
    symbol: &SymbolToFind,
) -> HashMap<String, HashMap<usize, String>> {
    let mut declared: HashMap<String, HashMap<usize, String>> = HashMap::new();

    for (path, fact) in index.every_fact_named(&symbol.last_segment) {
        declared
            .entry(normalize_path(&path, cfg!(windows)))
            .or_default()
            .insert(fact.name_range.start_offset, fact.qualified_name());
    }

    declared
}

/// **Which symbol a cursor is on** — the answer a caller has to have before it can ask for the references.
///
/// Three fields because all three are needed and none can be derived from the others at the point of use: the
/// **name** is what a rename edits, the **last segment** is what a use of a qualified name spells (`size`, not
/// `std::vector::size`), and the **qualified** name is what makes two declarations of one spelling different
/// symbols — which is what [`SymbolReferences::qualified`] records and a caller can show.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SymbolToFind {
    /// The declaration's own name, as its file spells it.
    pub name: String,
    /// What a use writes: the part after the last `::`.
    pub last_segment: String,
    /// The qualified name, which is the identity two same-spelled declarations do not share.
    pub qualified: String,
    /// The file the declaration is in.
    pub declared_in: PathBuf,
    /// The offset of the declaration's own name in that file — the one occurrence that is the declaration rather
    /// than a use of it.
    pub name_at: usize,
}

impl SymbolToFind {
    /// The symbol a resolved declaration names.
    pub fn of(fact: &crate::summary::DeclFact, declared_in: PathBuf) -> Self {
        let name = fact.name.clone();
        let last_segment = match name.rsplit_once("::") {
            Some((_, last)) => last.to_string(),
            None => name.clone(),
        };

        SymbolToFind {
            name,
            last_segment,
            qualified: fact.qualified_name(),
            declared_in,
            name_at: fact.name_range.start_offset,
        }
    }
}

/// Every place a symbol's name is written, and what each one turned out to be.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SymbolReferences {
    /// The declaration's own name.
    pub name: String,
    /// The qualified name the declaration is known by — the identity a caller shows to say *which* symbol this is.
    pub qualified: String,
    /// Where it is declared.
    pub declared_in: PathBuf,
    /// The files with at least one occurrence, in path order.
    pub files: Vec<FileReferences>,
    /// Candidate files that were read and lexed.
    pub looked_at: usize,
    /// Candidate files that do not contain the spelling at all.
    pub without_the_name: usize,
    /// Candidate files the budget stopped before.
    pub not_looked_at: usize,
    /// Candidate files that could not be read.
    pub unreadable: Vec<PathBuf>,
}

impl SymbolReferences {
    /// Every reference, in file order.
    pub fn all(&self) -> impl Iterator<Item = (&PathBuf, &Reference)> {
        self.files.iter().flat_map(|file| {
            file.references
                .iter()
                .map(move |reference| (&file.file, reference))
        })
    }

    /// How many places the name is written.
    pub fn count(&self) -> usize {
        self.files.iter().map(|file| file.references.len()).sum()
    }
}

/// The files that could use the symbol: the declaring file, everything that transitively includes it, and every
/// file that declares the same **qualified** name.
///
/// The last of the three is the one the include rule cannot reach, and it is a real case rather than a
/// completeness gesture: a free function declared in two translation units, each with its own prototype, uses one
/// name that no include connects. The index answers it by name, so the candidates do too.
fn symbol_candidates(
    index: &ProjectIndex,
    symbol: &SymbolToFind,
    budget: ReferenceBudget,
    answer: &mut SymbolReferences,
) -> Vec<PathBuf> {
    let mut roots: Vec<PathBuf> = vec![symbol.declared_in.clone()];
    roots.extend(
        index
            .files_declaring(&symbol.qualified, &symbol.declared_in)
            .into_iter()
            .map(|found| found.file),
    );

    let mut found: Vec<PathBuf> = Vec::new();
    let mut seen: HashSet<String> = HashSet::new();
    let mut pending: VecDeque<PathBuf> = roots.into_iter().collect();

    while let Some(path) = pending.pop_front() {
        if !seen.insert(normalize_path(&path, cfg!(windows))) {
            continue;
        }

        if found.len() >= budget.max_files {
            answer.not_looked_at += 1;
            continue;
        }

        found.push(path.clone());
        pending.extend(index.includers_of(&path));
    }

    found.sort();
    found
}

#[cfg(test)]
mod tests {
    use super::{
        ReferenceBudget, ReferenceKind, SymbolToFind, macro_references, symbol_references,
    };
    use crate::cache::SummaryKey;
    use crate::file::paths::{FileProvider, MemoryFiles};
    use crate::include::config::CompilerConfig;
    use crate::include::graph::Marked;
    use crate::index::{FileIndexer, ProjectIndex};
    use crate::symbol::{Known, UnknownReason};
    use std::path::Path;

    /// An index over a set of in-memory files, with the include edges resolved.
    ///
    /// A real index built the real way — [`FileIndexer`] per file — because the whole query depends on the reverse
    /// edges, and an index built by hand would be an index whose graph is whatever the test believed it was.
    fn index_of(files: &MemoryFiles, paths: &[&str]) -> ProjectIndex {
        let config = CompilerConfig::default();
        let indexer = FileIndexer::new(files, &config);
        let mut index = ProjectIndex::new();

        for path in paths {
            let path = Path::new(path);
            let source = files.read(path).expect("the fixture has the file");
            index.insert(indexer.index(path, &source, SummaryKey::new(0, 0)));
        }

        index
    }

    /// The macros a compilation starts with, for the tests that ask what a *decided* condition does: what a
    /// compiler predefines (`-dM`) and what the command line says (`-D`) arrive in the same shape, and only the
    /// names matter here.
    fn defined(names: &[&str]) -> Marked {
        let mut marked = Marked::default();

        for name in names {
            marked.define_on_the_command_line(name, None);
        }

        marked
    }

    /// Every reference of `name`, as `file:kind:text` so that an assertion says *where* as well as *what*.
    fn shown(files: &MemoryFiles, index: &ProjectIndex, name: &str) -> Vec<String> {
        match macro_references(index, files, name, ReferenceBudget::default()) {
            Known::Yes(found) => found
                .files
                .iter()
                .flat_map(|file| {
                    let text = files.read(&file.file).unwrap_or_default();
                    file.references.iter().map(move |reference| {
                        let kind = match &reference.kind {
                            ReferenceKind::Definition => "define".to_string(),
                            ReferenceKind::Undefinition => "undef".to_string(),
                            ReferenceKind::Use { .. } => "use".to_string(),
                            ReferenceKind::Uncertain(_) => "maybe".to_string(),
                        };
                        format!(
                            "{}:{kind}:{}",
                            file.file.file_name().unwrap().to_string_lossy(),
                            &text[reference.range.start_offset..reference.range.end_offset()]
                        )
                    })
                })
                .collect(),
            Known::Unknown(reason) => vec![format!("unknown: {}", reason.describe())],
            Known::No => vec!["no".to_string()],
        }
    }

    /// One project, reused by most of the tests below:
    ///
    /// ```text
    /// api.h      #define API int
    /// main.cpp   #include "api.h"   API f();        <- a definition and a certain use
    /// guarded.h  #define GUARDED int
    /// cond.cpp   #if defined(X) #include "guarded.h" #endif   GUARDED g();
    /// ```
    fn fixture() -> MemoryFiles {
        MemoryFiles::new()
            .with_file("/p/api.h", "#define API int\n")
            .with_file("/p/main.cpp", "#include \"api.h\"\nAPI f() { return 0; }\n")
            .with_file("/p/guarded.h", "#define GUARDED int\n")
            .with_file(
                "/p/cond.cpp",
                "#if defined(X)\n#include \"guarded.h\"\n#endif\nGUARDED g() { return 0; }\n",
            )
    }

    const FIXTURE_FILES: &[&str] = &["/p/api.h", "/p/main.cpp", "/p/guarded.h", "/p/cond.cpp"];

    /// Every symbol reference of `symbol`, as `file:line-text` — and the **declaration is in the list**, because
    /// that is what `textDocument/references` with `includeDeclaration` asks for and what a rename edits first.
    fn symbol_shown(
        files: &MemoryFiles,
        index: &ProjectIndex,
        symbol: &SymbolToFind,
    ) -> Vec<String> {
        match symbol_references(index, files, symbol, ReferenceBudget::default()) {
            Known::Yes(found) => found
                .all()
                .map(|(file, reference)| {
                    let text = files.read(file).unwrap_or_default();
                    let line = text[..reference.range.start_offset.min(text.len())]
                        .matches('\n')
                        .count();
                    format!(
                        "{}:{line}:{}",
                        file.file_name().unwrap().to_string_lossy(),
                        &text[reference.range.start_offset..reference.range.end_offset()]
                    )
                })
                .collect(),
            Known::Unknown(reason) => vec![format!("unknown: {}", reason.describe())],
            Known::No => vec!["no".to_string()],
        }
    }

    /// **A class and a variable, which is the shape that answered nothing at all.**
    ///
    /// Measured before this query existed, on a real file: `class Sux` answered **0 references** with `Sux sux;`
    /// two lines below it, and `sux` answered 0 with `sux.print()` on the next line — because the only query was
    /// [`macro_references`] and a name that is not a macro fell through to an empty list. The protocol has no "and
    /// there may be more" for a reference list, so that empty answer is the claim that nothing uses the name, and a
    /// user who renames on it changes the declaration and nothing else.
    ///
    /// Both halves are pinned here: the class (`Sux` in two places, one of them in a file that includes the one
    /// that declares it) and the object (`sux` in two places, both in one file). A third name is pinned for the
    /// negative: `other` is spelled inside a **comment and a string**, which is where a text search finds what a
    /// lexer does not.
    #[test]
    fn a_symbols_references_are_every_place_its_name_is_written() {
        let files = MemoryFiles::new()
            .with_file("/p/sux.h", "class Sux {\npublic:\n  void print();\n};\n")
            .with_file(
                "/p/main.cpp",
                "#include \"sux.h\"\nSux sux;\n// Sux in a comment\nconst char* s = \"Sux\";\nvoid f() { sux.print(); }\n",
            );

        let index = index_of(&files, &["/p/sux.h", "/p/main.cpp"]);

        let class = SymbolToFind {
            name: "Sux".to_string(),
            last_segment: "Sux".to_string(),
            qualified: "Sux".to_string(),
            declared_in: std::path::PathBuf::from("/p/sux.h"),
            name_at: 6,
        };

        assert_eq!(
            symbol_shown(&files, &index, &class),
            vec![
                // Path order, which is what makes two runs over one project answer the same thing in the same
                // order. The use in the file that includes the header — and **not** the comment or the string,
                // which the lexer makes into single tokens: a text scan would report four places here, three of
                // them wrong.
                "main.cpp:1:Sux".to_string(),
                // The declaration, in the header.
                "sux.h:0:Sux".to_string(),
            ],
            "a class is used in the file that includes its header, and in no comment"
        );

        let object = SymbolToFind {
            name: "sux".to_string(),
            last_segment: "sux".to_string(),
            qualified: "sux".to_string(),
            declared_in: std::path::PathBuf::from("/p/main.cpp"),
            name_at: 23,
        };

        assert_eq!(
            symbol_shown(&files, &index, &object),
            vec!["main.cpp:1:sux".to_string(), "main.cpp:4:sux".to_string(),],
            "an object declared at file scope is used in the function below it"
        );
    }

    /// **A same-spelled declaration of another entity is not a reference** — the one semantic call this layer makes.
    ///
    /// Reported from an editor as "references are lexical": a `.cpp` that includes a header declaring
    /// `struct Name { void printf(int); };` — twice over, in the class and again `void Name::printf(int i)` — and
    /// the C library's `printf`, then asks for the references of the global `printf`. Every occurrence of the
    /// spelling came back, the class's two declarations among them, and a rename would have edited all of them.
    ///
    /// The index knows which offsets are declarations and by what qualified name, so those two are dropped while
    /// every **use** stays — deciding which entity a use belongs to needs that file's scopes, which is a parse this
    /// layer does not do (module documentation).
    #[test]
    fn another_entity_declaration_of_the_same_spelling_is_not_a_reference() {
        let files = MemoryFiles::new()
            .with_file(
                "/p/name.h",
                "struct Name {\n    void printf(int i);\n};\nvoid Name::printf(int i) { }\n",
            )
            .with_file("/p/stdio.h", "void printf(const char* format, ...);\n")
            .with_file(
                "/p/main.cpp",
                "#include \"name.h\"\n#include \"stdio.h\"\nvoid f() { printf(\"x\"); }\n",
            );

        let index = index_of(&files, &["/p/name.h", "/p/stdio.h", "/p/main.cpp"]);
        let global = SymbolToFind {
            name: "printf".to_string(),
            last_segment: "printf".to_string(),
            qualified: "printf".to_string(),
            declared_in: std::path::PathBuf::from("/p/stdio.h"),
            name_at: 5,
        };

        assert_eq!(
            symbol_shown(&files, &index, &global),
            vec![
                // The use in the file that includes both headers.
                "main.cpp:2:printf".to_string(),
                // The declaration the symbol is: `void printf(const char* format, ...);`
                "stdio.h:0:printf".to_string(),
            ],
            "`Name::printf`'s declaration and its definition are a different entity"
        );
    }

    #[test]
    fn a_use_in_the_file_that_includes_the_definition_is_found() {
        let files = fixture();
        let index = index_of(&files, FIXTURE_FILES);

        assert_eq!(
            shown(&files, &index, "API"),
            ["api.h:define:API", "main.cpp:use:API"],
            "the definition and the one use, in path order"
        );
    }

    #[test]
    fn a_name_in_a_comment_or_a_string_is_not_a_reference() {
        // The two commonest false positives of a text search, and the reason this layer lexes rather than greps:
        // a comment is one token and a string is one token, so neither can reach the identifier filter.
        let files = MemoryFiles::new()
            .with_file("/p/api.h", "#define API int\n")
            .with_file(
                "/p/main.cpp",
                "#include \"api.h\"\n// API is a macro\nconst char* s = \"API\";\nAPI f() { return 0; }\n",
            );
        let index = index_of(&files, &["/p/api.h", "/p/main.cpp"]);

        assert_eq!(
            shown(&files, &index, "API"),
            ["api.h:define:API", "main.cpp:use:API"]
        );

        match macro_references(&index, &files, "API", ReferenceBudget::default()) {
            Known::Yes(found) => assert_eq!(
                found.rejected, 0,
                "a comment and a string are not even candidates for rejection: they are not identifiers"
            ),
            other => panic!("the macro is indexed, got {other:?}"),
        }
    }

    #[test]
    fn a_name_after_an_undef_is_rejected_rather_than_reported() {
        // Text that looks exactly like a use and is not one. The `#undef` itself *is* a reference — a rename has to
        // keep it in step — and the name inside the directive is covered by that fact rather than reported twice.
        let files = MemoryFiles::new()
            .with_file("/p/api.h", "#define API int\n")
            .with_file(
                "/p/main.cpp",
                "#include \"api.h\"\n#undef API\nint API = 1;\n",
            );
        let index = index_of(&files, &["/p/api.h", "/p/main.cpp"]);

        assert_eq!(
            shown(&files, &index, "API"),
            ["api.h:define:API", "main.cpp:undef:API"],
            "the `#undef` is a reference, and it points at the *name* — not at the whole line, which is what the \
             directive reader recorded and what a rename must not replace"
        );

        match macro_references(&index, &files, "API", ReferenceBudget::default()) {
            Known::Yes(found) => assert_eq!(found.rejected, 1, "and the rejection is counted"),
            other => panic!("the macro is indexed, got {other:?}"),
        }
    }

    #[test]
    fn a_condition_is_decided_by_a_define_the_closure_wrote_earlier() {
        // The shape libstdc++ is built on: `bits/c++config.h` defines `_GLIBCXX_USE_CXX11_ABI` as `1`, and headers
        // written after it test `#if _GLIBCXX_USE_CXX11_ABI`. The condition is about a macro **no file in the
        // translation unit's environment defines** and the closure does — so it is the walk that decides it, by
        // reading the unit in order: `config.h`'s facts are in force by the time `widget.h` is read.
        //
        // Both halves are here and they are different answers from the same machinery: `ABI == 1` needs the
        // *value* (`MacroFact::value`, one integer literal) and `FEATURE` needs only the name.
        let files = MemoryFiles::new()
            .with_file("/p/config.h", "#define ABI 1\n#define FEATURE\n")
            .with_file(
                "/p/widget.h",
                "#include \"config.h\"\n#if ABI == 1\n#include \"modern.h\"\n#endif\n\
                 #ifdef FEATURE\n#include \"feature.h\"\n#endif\n",
            )
            .with_file("/p/modern.h", "#define MODERN int\n")
            .with_file("/p/feature.h", "#define FEATURE_ONLY int\n")
            .with_file(
                "/p/main.cpp",
                "#include \"widget.h\"\nMODERN a;\nFEATURE_ONLY b;\n",
            );

        let index = index_of(
            &files,
            &[
                "/p/config.h",
                "/p/widget.h",
                "/p/modern.h",
                "/p/feature.h",
                "/p/main.cpp",
            ],
        );

        assert_eq!(
            shown(&files, &index, "MODERN"),
            ["main.cpp:use:MODERN", "modern.h:define:MODERN"],
            "the value is read out of `config.h`, so the `#if` is taken and the include is certain"
        );
        assert_eq!(
            shown(&files, &index, "FEATURE_ONLY"),
            ["feature.h:define:FEATURE_ONLY", "main.cpp:use:FEATURE_ONLY"],
            "and a name defined with no body at all is enough for an `#ifdef`"
        );
    }

    #[test]
    fn a_condition_about_a_define_that_comes_later_after_the_include_is_not_decided() {
        // The order is the whole answer, so the *same two files* the other way round must not decide anything: a
        // `#define` below the `#include` is not in force when the include is read. A walk that collected every fact
        // of every reachable file and then evaluated would get this wrong, which is why the state is built as the
        // walk passes each fact rather than in one pass at the end.
        let files = MemoryFiles::new()
            .with_file("/p/config.h", "#define ABI 1\n")
            .with_file(
                "/p/widget.h",
                "#if ABI == 1\n#include \"modern.h\"\n#endif\n#include \"config.h\"\n",
            )
            .with_file("/p/modern.h", "#define MODERN int\n")
            .with_file("/p/main.cpp", "#include \"widget.h\"\nMODERN a;\n");

        let index = index_of(
            &files,
            &["/p/config.h", "/p/widget.h", "/p/modern.h", "/p/main.cpp"],
        );

        assert_eq!(
            shown(&files, &index, "MODERN"),
            ["main.cpp:maybe:MODERN", "modern.h:define:MODERN"],
            "at the `#if` the name was not defined yet: the include may or may not have happened"
        );
    }

    #[test]
    fn a_define_inside_a_region_the_walk_cannot_decide_does_not_decide_a_later_condition() {
        // The soundness rule for the state: a fact whose own region is undecidable is **not** in force, so it cannot
        // make a later condition decided. `#ifdef SETTING / #define WIDE 1 / #endif` says nothing about `WIDE` when
        // `SETTING` is unknown — and a state that took it anyway would answer the second `#if` with evidence that
        // depends on the first one's unknown answer.
        let files = MemoryFiles::new()
            .with_file(
                "/p/widget.h",
                "#ifdef SETTING\n#define WIDE 1\n#endif\n#if WIDE == 1\n#include \"wide.h\"\n#endif\n",
            )
            .with_file("/p/wide.h", "#define WIDE_ONLY int\n")
            .with_file("/p/main.cpp", "#include \"widget.h\"\nWIDE_ONLY a;\n");

        let index = index_of(&files, &["/p/widget.h", "/p/wide.h", "/p/main.cpp"]);

        assert_eq!(
            shown(&files, &index, "WIDE_ONLY"),
            ["main.cpp:maybe:WIDE_ONLY", "wide.h:define:WIDE_ONLY"],
            "the value came from a branch nobody can decide"
        );
    }

    #[test]
    fn a_define_inside_a_settled_region_is_in_force_without_its_value() {
        // `#ifndef NAME / #define NAME 1 / #endif` — the idiom `MacroFact::settles_the_name` exists for. The name
        // *is* a macro after the block whichever branch ran, so a later `#ifdef` is decided; and the *value* is not
        // certain (the other branch may have defined it differently), so a later `#if NAME == 1` is not.
        let files = MemoryFiles::new()
            .with_file(
                "/p/widget.h",
                "int early;\n#ifndef WIDE\n#define WIDE 1\n#endif\n\
                 #ifdef WIDE\n#include \"named.h\"\n#endif\n#if WIDE == 1\n#include \"valued.h\"\n#endif\n",
            )
            .with_file("/p/named.h", "#define NAMED int\n")
            .with_file("/p/valued.h", "#define VALUED int\n")
            .with_file("/p/main.cpp", "#include \"widget.h\"\nNAMED a;\nVALUED b;\n");

        let index = index_of(
            &files,
            &["/p/widget.h", "/p/named.h", "/p/valued.h", "/p/main.cpp"],
        );

        assert_eq!(
            shown(&files, &index, "NAMED"),
            ["main.cpp:use:NAMED", "named.h:define:NAMED"],
            "definedness is settled by the shape"
        );
        assert_eq!(
            shown(&files, &index, "VALUED"),
            ["main.cpp:maybe:VALUED", "valued.h:define:VALUED"],
            "the value is not: the other branch could have defined it as anything"
        );
    }

    #[test]
    fn a_guard_on_a_name_nothing_defines_is_taken_when_the_caller_declares_the_inputs_complete() {
        // The same fixture as the test above, with the *other* environment answer — the one `Session::open` gives a
        // project whose compile database it read. `NT_INCLUDED` is defined nowhere, and "nowhere" is a conclusion
        // the caller is entitled to draw when it has told us how the project is compiled: the guard is taken, the
        // include is certain, and the use behind it is a use.
        //
        // This is the MinGW `windef.h` shape, and the reason every one of `STDMETHODCALLTYPE`'s four thousand
        // references was a "maybe".
        let files = MemoryFiles::new()
            .with_file("/p/winnt.h", "#define WIN_ONLY int\n")
            .with_file(
                "/p/windef.cpp",
                "int early;\n#ifndef NT_INCLUDED\n#include \"winnt.h\"\n#endif\nWIN_ONLY x;\n",
            );

        // `Marked::default()` is a *complete* environment with nothing in it: the compiler predefines nothing and
        // the command line said nothing, which is the whole of what this compilation defines.
        let index =
            index_of(&files, &["/p/winnt.h", "/p/windef.cpp"]).with_macros(Marked::default());

        assert_eq!(
            shown(&files, &index, "WIN_ONLY"),
            ["windef.cpp:use:WIN_ONLY", "winnt.h:define:WIN_ONLY"],
            "the guard is not taken, so the include is in the translation unit"
        );
    }

    #[test]
    fn an_include_that_did_not_resolve_takes_the_completeness_claim_back() {
        // The other half of that bargain, and the reason it is safe to make: a walk that runs into an `#include`
        // it cannot read has a hole in what it knows — the file it names may define *anything* — so every later
        // "nothing defines this" answer is off again. Without this, a missing header would quietly turn into
        // negative answers about names it might have defined.
        let files = MemoryFiles::new()
            .with_file(
                "/p/windef.cpp",
                "#include \"nowhere_to_be_found.h\"\nint early;\n\
                 #ifndef NT_INCLUDED\n#include \"winnt.h\"\n#endif\nWIN_ONLY x;\n",
            )
            .with_file("/p/winnt.h", "#define WIN_ONLY int\n");

        let index =
            index_of(&files, &["/p/winnt.h", "/p/windef.cpp"]).with_macros(Marked::default());

        assert_eq!(
            shown(&files, &index, "WIN_ONLY"),
            ["windef.cpp:maybe:WIN_ONLY", "winnt.h:define:WIN_ONLY"],
            "the unresolved include could have defined `NT_INCLUDED`, so the guard is undecided"
        );
    }

    #[test]
    fn a_use_reached_through_a_conditional_include_is_certain_when_the_environment_decides_it() {
        // The same text as the test above, and the other answer. `-DX` is a fact about the *compilation*, not a
        // doubt about it: a compiler that was given `-DX` read `guarded.h`, so the use is a use. This is the
        // whole point of storing each region's condition in the summary and evaluating it at query time — the
        // summary is keyed without the macro environment, so the answer cannot be baked into it.
        let files = fixture();
        let index = index_of(&files, FIXTURE_FILES).with_macros(defined(&["X"]));

        assert_eq!(
            shown(&files, &index, "GUARDED"),
            ["cond.cpp:use:GUARDED", "guarded.h:define:GUARDED"],
            "no `maybe`: the include is in the translation unit"
        );
    }

    #[test]
    fn a_use_reached_through_an_include_the_environment_rules_out_is_not_a_use() {
        // The other decided answer, and it is the stronger claim: `#if 0` is not "I do not know", it is "not
        // compiled", so the include is not followed at all and the name in `never.cpp` is not a macro there.
        // Before the condition was evaluated this was a *maybe*, which is a use a rename would have been shown
        // and could have edited by mistake.
        let files = MemoryFiles::new()
            .with_file("/p/skipped.h", "#define SKIPPED int\n")
            .with_file(
                "/p/never.cpp",
                "#if 0\n#include \"skipped.h\"\n#endif\nSKIPPED x;\n",
            );
        let index = index_of(&files, &["/p/skipped.h", "/p/never.cpp"]);

        assert_eq!(
            shown(&files, &index, "SKIPPED"),
            ["skipped.h:define:SKIPPED"],
            "only the definition: the include is not in the translation unit"
        );
    }

    #[test]
    fn a_guard_on_a_name_nothing_defines_is_still_unknown_rather_than_untaken() {
        // `NT_INCLUDED` is the case this whole rule is careful about, measured in the MinGW headers:
        // `#ifndef NT_INCLUDED / #include <winnt.h> / #endif` in `windef.h`, where nothing in the closure defines
        // `NT_INCLUDED` at all. A closed-world reading says the guard is taken *or* not taken; the truth is that
        // the index cannot tell, and the include has to be followed with doubt rather than dropped.
        //
        // The declaration before the conditional keeps it from being the file's own guard, which is the one
        // conditional that is *not* a condition (see `deguard_the_files_own_guard`).
        let files = MemoryFiles::new()
            .with_file("/p/winnt.h", "#define WIN_ONLY int\n")
            .with_file(
                "/p/windef.cpp",
                "int early;\n#ifndef NT_INCLUDED\n#include \"winnt.h\"\n#endif\nWIN_ONLY x;\n",
            );
        let index = index_of(&files, &["/p/winnt.h", "/p/windef.cpp"]);

        assert_eq!(
            shown(&files, &index, "WIN_ONLY"),
            ["windef.cpp:maybe:WIN_ONLY", "winnt.h:define:WIN_ONLY"],
            "the include may have happened, so the use may be a use"
        );
    }

    #[test]
    fn a_definition_the_environment_rules_out_is_not_a_candidate() {
        // `#if 0` around a `#define`: the fact is in the file's text and a compiler never reads it, so the name is
        // not a macro in any file that includes this one. The region needs no environment to decide — `0` is `0` —
        // and the *use* in `main.cpp` is therefore not a use. Before the fact's own region was evaluated this was a
        // "maybe", which is a reference a rename would have been offered.
        let files = MemoryFiles::new()
            .with_file("/p/api.h", "#if 0\n#define API int\n#endif\n")
            .with_file("/p/main.cpp", "#include \"api.h\"\nAPI f();\n");
        let index = index_of(&files, &["/p/api.h", "/p/main.cpp"]);

        assert_eq!(
            shown(&files, &index, "API"),
            ["api.h:define:API"],
            "the `#define` is a fact about the text, and the use is not a use"
        );
    }

    #[test]
    fn a_use_reached_through_a_conditional_include_is_uncertain() {
        // Whether the include happened depends on a macro the analysis does not have, so the use *may* be a use.
        // `Uncertain` rather than `Use`, because everything downstream treats the two differently: one is edited,
        // the other is shown.
        let files = fixture();
        let index = index_of(&files, FIXTURE_FILES);

        assert_eq!(
            shown(&files, &index, "GUARDED"),
            ["cond.cpp:maybe:GUARDED", "guarded.h:define:GUARDED"],
            "path order, so `cond.cpp` comes first"
        );

        match macro_references(&index, &files, "GUARDED", ReferenceBudget::default()) {
            Known::Yes(found) => {
                assert_eq!(found.uncertain(), 1);
                assert_eq!(
                    found.rename("OTHER").len(),
                    1,
                    "only the definition is certain"
                );
            }
            other => panic!("the macro is indexed, got {other:?}"),
        }
    }

    #[test]
    fn a_file_that_cannot_see_the_macro_is_not_even_read() {
        // The candidate rule, and the money it saves: `other.cpp` uses the name but includes nothing, so no
        // preprocessor reading it would expand anything. It is not a candidate, and the provider proves it was not
        // read — an assertion about the *result* could not tell "not read" from "read and rejected".
        let files = fixture().with_file("/p/other.cpp", "API f() { return 0; }\n");
        let index = index_of(
            &files,
            &[
                "/p/api.h",
                "/p/main.cpp",
                "/p/other.cpp",
                "/p/guarded.h",
                "/p/cond.cpp",
            ],
        );

        assert_eq!(
            shown(&files, &index, "API"),
            ["api.h:define:API", "main.cpp:use:API"]
        );
        assert_eq!(
            files.reads_of("/p/other.cpp"),
            1,
            "read once, by the indexer — and never by the query"
        );
    }

    #[test]
    fn a_candidate_whose_text_has_no_such_name_is_filtered_before_the_lexer() {
        let files = fixture().with_file("/p/quiet.cpp", "#include \"api.h\"\nint x;\n");
        let index = index_of(&files, &["/p/api.h", "/p/main.cpp", "/p/quiet.cpp"]);

        match macro_references(&index, &files, "API", ReferenceBudget::default()) {
            Known::Yes(found) => {
                assert_eq!(
                    found.looked_at, 3,
                    "three candidates: both files and the definition"
                );
                assert_eq!(
                    found.without_the_name, 1,
                    "and one of them has no `API` in it"
                );
            }
            other => panic!("the macro is indexed, got {other:?}"),
        }
    }

    #[test]
    fn a_name_no_file_defines_is_unknown_rather_than_empty() {
        // The distinction the whole crate is built on: "nothing in the index defines it" is not "there are no
        // references". Under lazy indexing it also covers "the file that defines it has not been read yet".
        let files = fixture();
        let index = index_of(&files, FIXTURE_FILES);

        assert_eq!(
            macro_references(&index, &files, "NOTHING", ReferenceBudget::default()),
            Known::Unknown(UnknownReason::NotDeclaredHere(Box::from("NOTHING")))
        );
    }

    #[test]
    fn a_candidate_that_cannot_be_read_is_reported_rather_than_dropped() {
        // The file was in the index a moment ago and is gone now. One deleted file does not stop the answer, and it
        // is not silently missing from it either.
        let files = fixture();
        let index = index_of(&files, FIXTURE_FILES);
        let nothing = MemoryFiles::new();

        match macro_references(&index, &nothing, "API", ReferenceBudget::default()) {
            Known::Yes(found) => {
                assert_eq!(found.looked_at, 0);
                assert_eq!(
                    found.unreadable.len(),
                    2,
                    "the definer and the file that includes it — the closure comes from the index, not from reading"
                );
                assert_eq!(found.candidates(), 2, "and they are still the candidates");
                assert_eq!(found.total(), 0);
            }
            other => panic!("the macro is indexed, got {other:?}"),
        }
    }

    #[test]
    fn the_counters_add_up_to_the_ladder_they_describe() {
        // Every number in this struct is one rung of the same ladder, and a caller reading them has to be able to
        // trust that. `_inline`'s first version of the probe did not: it added the skipped files to the read ones
        // and reported a candidate count that was 132 too high, which is a number nobody would have questioned.
        let files = fixture().with_file("/p/quiet.cpp", "#include \"api.h\"\nint x;\n");
        let index = index_of(&files, &["/p/api.h", "/p/main.cpp", "/p/quiet.cpp"]);

        let Known::Yes(found) = macro_references(&index, &files, "API", ReferenceBudget::default())
        else {
            panic!("the macro is indexed");
        };

        assert_eq!(
            found.candidates(),
            3,
            "the definer and the two files that include it"
        );
        assert_eq!(found.looked_at, 3, "all three were read");
        assert_eq!(found.without_the_name, 1, "one of them has no `API` in it");
        assert_eq!(found.lexed(), 2, "so two were lexed");
        assert_eq!(found.not_looked_at, 0);
        assert!(found.unreadable.is_empty());
    }

    #[test]
    fn the_budget_stops_the_answer_and_says_how_much_it_missed() {
        let files = fixture();
        let index = index_of(&files, FIXTURE_FILES);

        match macro_references(&index, &files, "API", ReferenceBudget { max_files: 1 }) {
            Known::Yes(found) => {
                assert_eq!(found.looked_at, 1);
                assert_eq!(found.not_looked_at, 1, "one candidate was left unread");
                assert_eq!(
                    found.candidates(),
                    2,
                    "and it is still counted as a candidate"
                );
                assert!(
                    found.total() < 2,
                    "the answer is short because of it: {} references",
                    found.total()
                );
            }
            other => panic!("the macro is indexed, got {other:?}"),
        }
    }

    #[test]
    fn renaming_edits_exactly_the_ranges_that_hold_the_name() {
        // The test that makes "find references" a rename rather than a list: apply the edits backwards and the file
        // that comes out is the file with the new name. A range that is off by one character fails here, and it
        // would fail silently in a client that only compared counts.
        let files = fixture();
        let index = index_of(&files, FIXTURE_FILES);

        let Known::Yes(found) = macro_references(&index, &files, "API", ReferenceBudget::default())
        else {
            panic!("the macro is indexed");
        };

        let edits = found.rename("INT_TYPE");
        assert_eq!(edits.len(), 2, "the definition and the one use");

        let mut text = files
            .read(Path::new("/p/main.cpp"))
            .expect("the file reads");
        for edit in edits
            .iter()
            .filter(|edit| edit.file == Path::new("/p/main.cpp"))
        {
            text.replace_range(
                edit.range.start_offset..edit.range.end_offset(),
                &edit.replacement,
            );
        }

        assert_eq!(text, "#include \"api.h\"\nINT_TYPE f() { return 0; }\n");
    }

    #[test]
    fn the_answer_is_in_path_order_whatever_order_the_graph_reaches_files_in() {
        // Determinism, asserted because a query whose output order depends on a `HashMap` is a bug that only shows
        // up in a test that runs twice. The files are given to the index in an order that is *not* path order.
        let files = fixture();
        let index = index_of(
            &files,
            &["/p/cond.cpp", "/p/main.cpp", "/p/guarded.h", "/p/api.h"],
        );

        match macro_references(&index, &files, "API", ReferenceBudget::default()) {
            Known::Yes(found) => {
                let names: Vec<String> = found
                    .files
                    .iter()
                    .map(|file| file.file.file_name().unwrap().to_string_lossy().to_string())
                    .collect();
                assert_eq!(names, ["api.h", "main.cpp"]);
            }
            other => panic!("the macro is indexed, got {other:?}"),
        }
    }
}

/// **Every place a name is written, across the files that can see it** — the non-macro half of
/// [`crate::ProjectIndex::macro_references`], and the answer `textDocument/references` needs for a function, a class or
/// a variable.
///
/// # The rule, and where it is silent
///
/// A file can only refer to a name it can see, so the candidates are the files that declare it and everything that
/// **transitively includes** one of those. That is the same narrowing the macro path makes, and it is a sound one: a
/// file outside the closure refers to the name only if it reaches it another way, and the include graph is the only way
/// a name crosses a file boundary.
///
/// A candidate that **declares the same spelling as a local** is not searched. Its uses may name its own local, and a
/// listing that said so would be a list of two different things under one name — which is exactly the shape a rename
/// must never be built on. Those files come back in `not_looked_at`, because "there are no more references" and "I did
/// not look" are different answers.
///
/// # What it costs
///
/// One `read` and one lex per candidate, bounded by `budget` files. A candidate whose text does not contain the name is
/// one read and no lex, which is the cheap filter that makes a large closure affordable.
pub fn name_references(
    index: &crate::ProjectIndex,
    read: &dyn Fn(&std::path::Path) -> Option<String>,
    name: &str,
    declaring: &[std::path::PathBuf],
    budget: usize,
) -> NameReferences {
    use std::collections::{HashSet, VecDeque};

    let mut found = NameReferences::default();
    let mut seen: HashSet<std::path::PathBuf> = HashSet::new();
    let mut queue: VecDeque<std::path::PathBuf> = declaring.iter().cloned().collect();
    while let Some(path) = queue.pop_front() {
        if !seen.insert(path.clone()) {
            continue;
        }
        for includer in index.includers_of(&path) {
            if !seen.contains(&includer) {
                queue.push_back(includer);
            }
        }
    }

    for path in seen {
        if found.looked_at >= budget {
            found.not_looked_at.push(path);
            continue;
        }
        let Some(text) = read(&path) else {
            found.not_looked_at.push(path);
            continue;
        };
        // **A file that declares the spelling as a local is not searched.** Its uses may mean its own local.
        let declares_a_local = index.summary(&path).is_some_and(|summary| {
            summary
                .declarations
                .iter()
                .any(|fact| fact.local && fact.name == name)
        });
        if declares_a_local {
            found.not_looked_at.push(path);
            continue;
        }
        if !text.contains(name) {
            found.looked_at += 1;
            continue;
        }
        found.looked_at += 1;
        let (tokens, _) = cpp_parser::lex(&text, &cpp_parser::LexerConfig::default());
        let at: Vec<cpp_parser::SourceRange> = tokens
            .iter()
            .filter(|token| {
                token.kind == cpp_parser::CppTokenKind::Identifier
                    && text
                        .get(token.range.start_offset..token.range.end_offset())
                        .is_some_and(|spelled| spelled == name)
            })
            .map(|token| token.range)
            .collect();
        if !at.is_empty() {
            found.found.push((path, at));
        }
    }

    found
}

/// What [`name_references`] answered: the places, the files that were read, and the files it would not read.
#[derive(Debug, Default)]
pub struct NameReferences {
    /// Places the name is written, one entry per file, in the order the files were examined.
    pub found: Vec<(std::path::PathBuf, Vec<cpp_parser::SourceRange>)>,
    /// How many files were read and lexed.
    pub looked_at: usize,
    /// Files that were **not** searched: over budget, unreadable, or declaring the spelling as a local.
    pub not_looked_at: Vec<std::path::PathBuf>,
}