cpp_code_analysis 0.1.4

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
//! The symbol model: names, scopes, bindings, and **what is not known**.
//!
//! This is the vocabulary the analysis layer speaks. It deliberately contains no lookup and no traversal —
//! those are the next step, and their correctness depends on getting these shapes right first.
//!
//! # Why knowledge is three-valued here
//!
//! A compiler resolves C++ completely or fails. An editor cannot: it analyses code that is half-written,
//! code behind conditions it cannot evaluate, and code whose meaning depends on macros that were expanded
//! somewhere it did not look. The temptation is to answer anyway, and the cost is a wrong answer that looks
//! exactly like a right one.
//!
//! So a resolved question here answers [`Known<T>`], which has a third value:
//!
//! ```text
//! Known::Yes(symbol)          -> this name means that declaration
//! Known::No                   -> this name is definitely not declared here
//! Known::Unknown(reason)      -> no answer is available, and here is why
//! ```
//!
//! `No` and `Unknown` are the distinction that matters, and collapsing them is the mistake this module
//! exists to prevent. "This name is not declared" makes a consumer grey out code or report an error; "I
//! could not tell" makes it stay quiet. The existing layers already work this way — [`crate::guard::Visibility`]
//! separates `Inactive` from `Unknown`, and [`crate::modules::ImportOutcome`] separates "no such module" from
//! "I cannot find it" — and [`UnknownReason`] is what lets a consumer explain itself instead of going silent.
//!
//! # Why the reason is a closed enum
//!
//! Because each variant has a different fix, and a consumer that cannot tell them apart can only ever say
//! "sorry". `MacroExpansion` means expand more or accept the gap; `UnresolvedInclude` means configure the
//! include path; `DependentName` means the answer depends on a template argument that is not known yet.
//! Making the set closed means adding a new source of uncertainty is a compile error at every match, which
//! is how the gaps stay visible instead of accumulating silently.
//!
//! # Why a name is not a string
//!
//! `operator+`, `~Widget`, `operator int`, and `Widget` are four different things that a `String` cannot tell
//! apart, and the difference is semantic rather than cosmetic: a constructor and a destructor are **not**
//! found by ordinary unqualified lookup, so a model that stored them as the class name would make
//! `~Widget` resolve to the class and `Widget w;` resolve to the constructor. [`NameKind`] keeps them apart,
//! and [`Name::is_ordinary`] is the predicate a lookup keys on.
//!
//! The spelling is kept alongside the kind because a consumer has to print it, and re-deriving `operator+`
//! from a token stream is a second implementation of a rule the parser already applied.

use std::collections::HashSet;

use cpp_parser::SourceRange;

use crate::paths::FileId;
use crate::summary::MacroScopeReading;

/// A question's answer, with "no answer" as a first-class value.
///
/// See the module documentation for why the third value exists. `Unknown` carries a reason rather than a
/// unit, because a consumer that can say *why* it does not know is useful and one that can only say "no" is
/// not.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Known<T> {
    Yes(T),
    No,
    /// No answer is available. Boxed so that a reason does not widen every `Known<SymbolId>` in the program —
    /// the common case is `Yes`, and it should not pay for the rare one.
    Unknown(UnknownReason),
}

impl<T> Known<T> {
    /// Did the question get an answer?
    pub fn is_known(&self) -> bool {
        matches!(self, Known::Yes(_))
    }

    /// Is this a definite no, as opposed to an absence of an answer?
    ///
    /// The predicate a consumer wants before it reports anything: only a definite no justifies "this name is
    /// not declared".
    pub fn is_definitely_absent(&self) -> bool {
        matches!(self, Known::No)
    }

    /// The answer, if there is one.
    pub fn value(self) -> Option<T> {
        match self {
            Known::Yes(value) => Some(value),
            _ => None,
        }
    }

    /// The answer by reference, if there is one.
    pub fn value_ref(&self) -> Option<&T> {
        match self {
            Known::Yes(value) => Some(value),
            _ => None,
        }
    }

    /// Why there is no answer, if that is the state.
    pub fn reason(&self) -> Option<&UnknownReason> {
        match self {
            Known::Unknown(reason) => Some(reason),
            _ => None,
        }
    }

    /// Transform the answer, leaving the other two states alone.
    ///
    /// The other two states are why this is not `Option::map`: a caller chaining transformations must not
    /// lose the difference between "no" and "unknown" on the way through.
    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Known<U> {
        match self {
            Known::Yes(value) => Known::Yes(f(value)),
            Known::No => Known::No,
            Known::Unknown(reason) => Known::Unknown(reason),
        }
    }

    /// The reason to give when a transformation cannot produce an answer.
    ///
    /// `None` when the input was a definite `No`, which stays a definite `No`: a question that already had
    /// an answer is not made uncertain by failing to refine it.
    pub fn then_unknown(self, reason: UnknownReason) -> Known<T> {
        match self {
            Known::No => Known::No,
            _ => Known::Unknown(reason),
        }
    }
}

/// Why a question could not be answered.
///
/// Every variant is a source of uncertainty that C++ genuinely has, and each one has a different remedy. The
/// set is closed on purpose: a new source of doubt has to be added here, and every `match` in the program
/// then fails to compile until it is handled — which is how a gap stays visible instead of becoming a
/// silent `No`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum UnknownReason {
    /// The answer is inside a macro expansion this analysis did not perform.
    ///
    /// The name is the macro's, and it is kept so the message can say which one. The expansion's range is
    /// *not* kept: [`SourceRange`] is not `Hash` or `Ord`, and duplicating it here to save a lookup would
    /// make this type unusable as a map key for no gain — a consumer with a range already has it.
    MacroExpansion(Box<str>),
    /// The answer is inside a conditional region that could not be evaluated.
    ///
    /// Distinct from "the region is not compiled": a branch that is definitely dead has an answer (`No`), and
    /// only an undecidable one is unknown. See [`crate::guard::Visibility::Unknown`].
    ConditionalCompilation,
    /// The answer is in a header that was not found.
    UnresolvedInclude(Box<str>),
    /// The answer is in a module that is not part of the analysis.
    ///
    /// The everyday case is `import std;`, which is normally a prebuilt BMI with no source in the project —
    /// so "the module was not found" says nothing about whether the name exists.
    UnresolvedModule(Box<str>),
    /// The name depends on a template argument that is not known.
    ///
    /// `T::value_type` where `T` is a template parameter: the answer exists only at instantiation, and
    /// guessing a particular instantiation would produce an answer that is wrong for every other one.
    DependentName,
    /// The declaration is inside a template that has not been instantiated.
    ///
    /// Distinct from [`UnknownReason::DependentName`]: here the *declaration* is in a template body, so its
    /// contents are not known until instantiation, rather than a name being dependent on a parameter already
    /// in scope.
    UnexpandedTemplate,
    /// The name cannot be read from the syntax tree.
    ///
    /// Reached when a declaration's name is malformed or half-typed, or when the construct is one the
    /// grammar recovered from. Reported rather than skipped: a declaration with an unreadable name still
    /// exists, and dropping it would make the scope look empty where it is merely damaged.
    UnparsableName,
    /// The macro environment is incomplete, so a condition about this name cannot be decided.
    ///
    /// The state a header is analysed in when nothing is known about its includer — see
    /// [`crate::graph::FileEntry::missing_context`]. A name that the includer might define must not be
    /// reported as absent.
    IncompleteMacroContext,
    /// The name is not declared anywhere this file can see, so the declaration is in another file.
    ///
    /// The everyday reason for a single-file analysis, and the one that keeps "not here" apart from "nowhere":
    /// `values.push_back(1)` where `values` is a `std::vector` has an answer, and it is not in this translation
    /// unit. It carries the spelling so that a message can name what was not resolved.
    ///
    /// Distinct from [`UnknownReason::UnresolvedInclude`], which is about a *specific* `#include` that could not
    /// be found: here nothing is broken, the file simply does not contain the declaration — and an analysis that
    /// had followed its includes might well have found it.
    NotDeclaredHere(Box<str>),
    /// Several declarations are visible and nothing chooses between them.
    ///
    /// Overloads, a name declared in two headers a file includes, a bare name declared in two namespaces. The
    /// answer is not "the first one": picking would make a definition jump silently land on one of several
    /// entities, and a consumer that wants to *show* the choice needs the set, not one member of it.
    ///
    /// Boxed spelling, like the other reasons that carry a name, so that this type stays small enough to sit in
    /// a `Known<T>` that is almost always `Yes`.
    Ambiguous(Box<str>),
    /// The name was a macro above this point and an `#undef` has ended it.
    ///
    /// A positive finding rather than a gap: the name is an ordinary identifier *here*, and the answer a consumer
    /// wants is "there is nothing to jump to, and here is why" — which is why it is not [`UnknownReason::No`] and
    /// not a pointer at the `#define` that is no longer in force. It is `Unknown` rather than `Known::No` because
    /// the index sees a subset of the translation unit: a header included after the `#undef` could define the name
    /// again.
    ///
    /// [`UnknownReason::No`]: crate::Known::No
    UndefinedHere(Box<str>),
    /// The type of an expression could not be worked out.
    ///
    /// The first reason in this vocabulary that is about a *type* rather than a name, and it arrived with the
    /// first query that needs one: `widget.size` cannot be answered without knowing what `widget` is, and the
    /// spelling is carried so that a message can say which expression it gave up on. Distinct from the name
    /// reasons because the fix is different — nothing is missing from the index, the analysis simply does not
    /// infer types for this shape yet.
    UnknownType(Box<str>),
}

impl UnknownReason {
    /// A sentence a diagnostic or a log line can show.
    ///
    /// Written to say what is *missing*, not merely that something is — the same rule the module and include
    /// layers follow, and for the same reason: "I could not tell" is only actionable if it says what would
    /// have made it decidable.
    pub fn describe(&self) -> String {
        match self {
            UnknownReason::MacroExpansion(name) => {
                format!(
                    "the name comes from the expansion of `{name}`, which was not expanded here"
                )
            }
            UnknownReason::ConditionalCompilation => {
                "the name is behind a condition that could not be evaluated".to_string()
            }
            UnknownReason::UnresolvedInclude(name) => {
                format!("the name may be declared in `{name}`, which was not found")
            }
            UnknownReason::UnresolvedModule(name) => format!(
                "the name may be exported by module `{name}`, which is not part of this analysis"
            ),
            UnknownReason::DependentName => {
                "the name depends on a template argument that is not known yet".to_string()
            }
            UnknownReason::UnexpandedTemplate => {
                "the declaration is inside a template that has not been instantiated".to_string()
            }
            UnknownReason::UnparsableName => {
                "the declared name could not be read from the source".to_string()
            }
            UnknownReason::IncompleteMacroContext => {
                "this file's macro environment is not fully known".to_string()
            }
            UnknownReason::NotDeclaredHere(name) => format!(
                "`{name}` is not declared in this file, so its declaration is in a file that was not read"
            ),
            UnknownReason::Ambiguous(name) => format!(
                "`{name}` is declared more than once in what this file can see, and nothing here chooses \
                 between the declarations"
            ),
            UnknownReason::UndefinedHere(name) => format!(
                "`{name}` is a macro that an `#undef` above this point has ended, so this is an ordinary \
                 identifier"
            ),
            UnknownReason::UnknownType(written) => format!(
                "the type of `{written}` is not known here, so what its members are is not known either"
            ),
        }
    }
}

/// What kind of thing a name names.
///
/// The variants are not decoration: they decide whether ordinary lookup finds the name at all, which is the
/// single most consequential question a lookup asks. See [`Name::is_ordinary`].
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum NameKind {
    /// An ordinary identifier: `Widget`, `count`, `std`.
    ///
    /// Also the kind of a **constructor**, whose declared name really is the class name — what distinguishes
    /// it is [`BindingKind::Constructor`], not a different spelling.
    Identifier(String),
    /// A destructor: `~Widget`.
    ///
    /// The spelling includes the `~`, because that is what makes it a destructor rather than the class, and
    /// ordinary lookup ignores it — `~Widget` is only found by an explicit destructor call.
    Destructor(String),
    /// A conversion function: `operator int`, `operator std::string`.
    ///
    /// The spelling is the type as written, whitespace removed, so `operator  int` and `operator int` are one
    /// name rather than two.
    Conversion(String),
    /// An overloadable operator: `operator+`, `operator[]`, `operator()`, `operator new`.
    ///
    /// The spelling is the operator as it appears after the keyword (`+`, `[]`, `()`, `new`), not the whole
    /// `operator+`, so that a consumer can compare it against an expression's operator without re-parsing.
    Operator(String),
    /// A user-defined literal operator: `operator""_km`.
    ///
    /// The spelling is the suffix without the quotes or the `_`, so `operator""_km` and `operator"" _km` are
    /// one name — they are the same operator, and the standard treats them as such.
    Literal(String),
}

impl NameKind {
    /// The spelling as it should be shown to a user.
    ///
    /// `operator` and the quotes around a literal suffix are put back, because a consumer showing `+` where
    /// the source says `operator+` would be showing something the user cannot find.
    ///
    /// The space after `operator` is conditional, and getting it wrong is visible in every message: the
    /// symbolic forms are written closed up (`operator+`, `operator[]`, `operator()`) while the word forms
    /// take a space (`operator new`, `operator delete`), because `operatornew` is not a spelling that appears
    /// anywhere in C++.
    pub fn text(&self) -> String {
        match self {
            NameKind::Identifier(name) => name.clone(),
            NameKind::Destructor(name) => format!("~{name}"),
            NameKind::Conversion(type_name) => format!("operator {type_name}"),
            NameKind::Operator(symbol) => {
                if symbol.starts_with(|first: char| first.is_alphanumeric() || first == '_') {
                    format!("operator {symbol}")
                } else {
                    format!("operator{symbol}")
                }
            }
            NameKind::Literal(suffix) => format!("operator\"\"_{suffix}"),
        }
    }
}

/// A name, as a lookup key rather than as a string.
///
/// Ordered and hashable so that a scope's declarations can live in a sorted vector or a map — the two
/// structures a scope needs, and the reason `NameKind` carries `String` rather than a borrow: a scope
/// outlives the source text it was read from.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Name {
    pub kind: NameKind,
}

impl Name {
    /// An ordinary identifier.
    pub fn identifier(text: impl Into<String>) -> Self {
        Name {
            kind: NameKind::Identifier(text.into()),
        }
    }

    pub fn destructor(class: impl Into<String>) -> Self {
        Name {
            kind: NameKind::Destructor(class.into()),
        }
    }

    pub fn conversion(type_name: impl Into<String>) -> Self {
        Name {
            kind: NameKind::Conversion(type_name.into()),
        }
    }

    pub fn operator(symbol: impl Into<String>) -> Self {
        Name {
            kind: NameKind::Operator(symbol.into()),
        }
    }

    pub fn literal(suffix: impl Into<String>) -> Self {
        Name {
            kind: NameKind::Literal(suffix.into()),
        }
    }

    /// The spelling a user would recognise.
    pub fn text(&self) -> String {
        self.kind.text()
    }

    /// Is this name found by ordinary unqualified lookup?
    ///
    /// False for everything except an identifier and a destructor, and the exception is the subtle one: a
    /// **constructor** is an identifier — its declared name is the class name — so it *is* found by ordinary
    /// lookup, and what stops `Widget x;` from resolving to it is that a constructor has no return type, not
    /// its name. A destructor, by contrast, is spelled `~Widget` and is invisible to ordinary lookup
    /// entirely: `~Widget` is only reached through an explicit call.
    ///
    /// A conversion function, an operator, and a literal are likewise never found by an ordinary name
    /// lookup — `operator+` is found by looking for `+` in an expression's context, which is a different
    /// question with a different answer (overload resolution, which this layer does not do).
    pub fn is_ordinary(&self) -> bool {
        matches!(self.kind, NameKind::Identifier(_) | NameKind::Destructor(_))
    }

    /// The identifier, when this name has one.
    ///
    /// `None` for a destructor: `~Widget` names no identifier, which is why [`Name::is_ordinary`] cannot be
    /// implemented in terms of this.
    pub fn identifier_text(&self) -> Option<&str> {
        match &self.kind {
            NameKind::Identifier(name) => Some(name),
            _ => None,
        }
    }

    /// The class a destructor destroys, or the identifier when there is one.
    pub fn base_text(&self) -> Option<&str> {
        match &self.kind {
            NameKind::Identifier(name) | NameKind::Destructor(name) => Some(name),
            _ => None,
        }
    }
}

/// A dotted or qualified name: `std`, `my.mod`, `ns::Inner`.
///
/// The components are kept unresolved rather than interned into one string, because resolution is exactly the
/// question this layer defers: `ns::Inner` needs a lookup for `ns` before `Inner` means anything, and
/// flattening it to `"ns::Inner"` would make that lookup impossible while looking like it had been done.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct QualifiedName {
    pub components: Vec<String>,
}

impl QualifiedName {
    pub fn single(component: impl Into<String>) -> Self {
        QualifiedName {
            components: vec![component.into()],
        }
    }

    pub fn from_components(components: impl IntoIterator<Item = String>) -> Self {
        QualifiedName {
            components: components.into_iter().collect(),
        }
    }

    /// The component the name ends with — what an unqualified reference would use.
    pub fn last(&self) -> Option<&str> {
        self.components.last().map(String::as_str)
    }

    /// The parts before the last, which have to be resolved for the whole name to mean anything.
    pub fn qualifiers(&self) -> &[String] {
        let end = self.components.len().saturating_sub(1);
        &self.components[..end]
    }

    /// The name as written, with `::` between components.
    pub fn text(&self) -> String {
        self.components.join("::")
    }

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

/// A header unit name: `<vector>` or `"local.h"`.
///
/// The spelling is kept because it decides which header is meant: the quoted form searches the including
/// file's own directory first and the angle form does not, so `"vector"` and `<vector>` can be two different
/// files.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct HeaderName {
    pub name: String,
    pub is_angle: bool,
}

impl HeaderName {
    pub fn text(&self) -> String {
        if self.is_angle {
            format!("<{}>", self.name)
        } else {
            format!("\"{}\"", self.name)
        }
    }
}

/// The name a declaration declares.
///
/// One variant per *shape*, because the shapes are resolved by different rules — see [`Name::is_ordinary`].
/// `None` is a real case and not an error: `static_assert`, an anonymous namespace, and a malformed
/// declaration all declare something with no name, and a model that made a name mandatory would have to
/// invent one.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum DeclName {
    /// A name that introduces an entity: `int count;`, `namespace ns {`, `class Widget {`.
    Named(Name),
    /// A qualified name: `int Inner::count;`, `void ns::f();`.
    ///
    /// Kept separate because a consumer has to resolve the qualifier before the name means anything, and
    /// doing that is a lookup rather than a string operation.
    Qualified(QualifiedName),
    /// A **module** name: `export module my.mod;`, `import std;`.
    Module(QualifiedName),
    /// A **header unit** name: `import <vector>;`.
    HeaderUnit(HeaderName),
    /// A **partition** of the enclosing module: `module my.mod:part;`, `import :part;`.
    Partition(QualifiedName),
}

impl DeclName {
    /// The name as it should be shown to a user.
    pub fn text(&self) -> String {
        match self {
            DeclName::Named(name) => name.text(),
            DeclName::Qualified(qualified) => qualified.text(),
            DeclName::Module(module) => module.text(),
            DeclName::HeaderUnit(header) => header.text(),
            DeclName::Partition(partition) => format!(":{}", partition.text()),
        }
    }

    /// The name as an ordinary lookup key, for the kinds that have one.
    ///
    /// `None` for a qualified name — the qualifier has to be resolved first — and for the module-shaped
    /// names, which are matched against the module graph rather than against a scope.
    pub fn ordinary_name(&self) -> Option<&Name> {
        match self {
            DeclName::Named(name) if name.is_ordinary() => Some(name),
            _ => None,
        }
    }
}

/// The name of a declaration or an import, when there is one.
///
/// A type alias rather than a wrapper, because "this declaration has no name" is a fact about the program and
/// not a failure of the analysis: `namespace { }` and `static_assert(...)` are ordinary C++, and a consumer
/// has to handle an unnamed declaration either way. Keeping it an `Option` means an unnamed declaration
/// cannot be confused with a name that could not be *read*, which is
/// [`UnknownReason::UnparsableName`].
pub type MaybeName = Option<DeclName>;

/// What a binding binds, as far as the syntax can say.
///
/// Derived from the *shape* of the declaration and not from types, because at this layer there are no types.
/// `Class` for `class Widget` and `Template` for `template <...> class Widget` are the two that matter most,
/// and both are read straight off the declaration.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum BindingKind {
    Namespace,
    /// `class`, `struct`, or `union` — the tag kinds, which share one name space in C++.
    Class,
    Enum,
    /// An enumerator: the `Red` in `enum { Red }`.
    Enumerator,
    Function,
    /// A constructor. Its [`Name`] is an identifier spelling the class name, because that is genuinely how it
    /// is spelled.
    Constructor,
    /// A destructor. Its [`Name`] carries the `~`.
    Destructor,
    /// A conversion function: `operator int`.
    ConversionFunction,
    /// An overloaded operator: `operator+`.
    OperatorFunction,
    /// A user-defined literal operator: `operator""_km`.
    LiteralOperator,
    /// A variable, including a function parameter, a field, and a structured binding.
    Variable,
    /// A `using` declaration that names an existing entity: `using ns::f;`.
    UsingDeclaration,
    /// A `using` directive: `using namespace ns;`, which makes a whole namespace's names visible without
    /// declaring any of them.
    UsingDirective,
    /// A type or namespace alias: `using Int = int;`, `namespace fs = std::filesystem;`.
    Alias,
    /// A `typedef`.
    Typedef,
    /// A template parameter: the `T` in `template <typename T>`, or the non-type `N` in `template <int N>`.
    ///
    /// Its own kind rather than an alias, because it is declared in a scope of its own — the template
    /// parameter list — and shadows nothing outside the declaration it belongs to. A consumer listing what a
    /// template declares has to find it, and a consumer resolving `T::value_type` has to know it is a
    /// parameter rather than a real type: that is the difference between a name that can be looked up now and
    /// one that is [`UnknownReason::DependentName`].
    TemplateParameter,
    /// A label, which is in a name space of its own and is never found by ordinary lookup.
    Label,
    /// A deduction guide, a `static_assert`'s name, or anything else the syntax identified as a declaration
    /// without a more specific shape.
    Other,
}

impl BindingKind {
    /// Is this binding a type, as far as its shape says?
    ///
    /// What a consumer keying on "the thing after `::` must be a type or a namespace" needs. Deliberately
    /// shape-based: a `typedef` and an alias are types, a variable is not, and a template is not known to be
    /// either until its arguments are.
    pub fn is_type_like(self) -> bool {
        matches!(
            self,
            BindingKind::Class
                | BindingKind::Enum
                | BindingKind::Alias
                | BindingKind::Typedef
                | BindingKind::Namespace
        )
    }

    /// Does this binding introduce a scope of its own?
    pub fn opens_a_scope(self) -> bool {
        matches!(
            self,
            BindingKind::Namespace | BindingKind::Class | BindingKind::Enum | BindingKind::Function
        )
    }
}

/// A name bound to a declaration, in a scope.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Binding {
    pub name: Name,
    pub kind: BindingKind,
    /// The whole declaration's range — what a go-to-definition highlights and what a rename replaces.
    pub range: SourceRange,
    /// Just the name's range.
    ///
    /// Separate from `range` because the two are needed at different times: a reference search matches the
    /// *name*, while a definition jump highlights the *declaration*. Collapsing them is the difference
    /// between a rename that edits one identifier and one that deletes the whole declaration.
    pub name_range: SourceRange,
    pub scope: ScopeId,
    /// Where the declaration came from, when it did not come from this file's own text.
    ///
    /// `None` for a declaration written here. The macro case is the one that matters: a binding produced by
    /// `DEFINE_FOO(x)` has a range inside the macro's expansion, and a consumer that treated it as ordinary
    /// text would offer a rename that edits the macro definition's arguments.
    ///
    /// Distinct from [`crate::expand::Origin`], which answers the same-shaped question for a *token*. The two
    /// cannot be one type: expansion tracks a whole invocation chain because a token can come from a macro
    /// that was written by another macro, while a binding is either written in this file or reached through
    /// one `#include`, and recording more here would imply a precision the symbol layer does not have.
    pub origin: Option<BindingOrigin>,
}

/// Where a binding came from, when that is not simply "here".
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum BindingOrigin {
    /// Produced by a macro expansion. The name is the macro's.
    ///
    /// The invocation's range is where a consumer should send the user, because that is the text they can
    /// edit — see [`crate::expand::Expansion`], where the same rule is applied to tokens.
    MacroExpansion {
        macro_name: String,
        definition: SourceRange,
    },
    /// Declared in an `#include`d file and visible here because inclusion is textual.
    ///
    /// The file is recorded because the binding's range is meaningless without it: an offset into a header is
    /// an offset into *that* header, not into the file being analysed.
    Included { file: FileId },
}

/// What a scope is.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum ScopeKind {
    /// The translation unit itself. Every file has exactly one, including a header — a header's file scope is
    /// where its top-level declarations live when it is analysed on its own.
    TranslationUnit,
    Namespace,
    /// Also a class, struct, or union. One variant because the difference is access, which is a member's
    /// property rather than the scope's.
    Class,
    Enum,
    /// A function's body, and its parameter scope — they differ only in what is bound, not in how lookup
    /// works.
    Function,
    /// A statement block: `{ ... }`, a loop body, a branch.
    Block,
    /// A template's parameter list, which is in scope for the declaration that follows.
    TemplateParameters,
    /// A lambda's body, which introduces a scope of its own and captures names into it.
    Lambda,
}

/// A region of the program in which names are declared and looked up.
///
/// The tree mirrors the syntax tree rather than being derived from it lazily: a scope corresponds to a node,
/// and keeping the correspondence explicit is what lets a consumer at a cursor position find its scope
/// without re-walking the tree.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Scope {
    pub parent: Option<ScopeId>,
    pub children: Vec<ScopeId>,
    pub kind: ScopeKind,
    /// The name this scope *introduces*: `ns` for `namespace ns { }`, `Widget` for `struct Widget { }`.
    ///
    /// A property of the scope rather than of the binding, because the two answer different questions. The
    /// binding says "`Widget` is declared in the enclosing scope" — which is where a consumer looks the name
    /// up — while this says "inside here, the current entity is `Widget`". Only the second can produce a
    /// **qualified** name, and a qualified name is what an index keys on: `ns::C::f` cannot be recovered from
    /// the binding of `f` alone, and it cannot be recovered from the enclosing scope either, because the
    /// scope does not know what it is called.
    ///
    /// `None` where the construct introduces no name: a function body, a statement block, a template parameter
    /// list, a lambda, an anonymous namespace, and the translation unit. Those are exactly the scopes that
    /// contribute nothing to a qualified name, which is why [`ScopeTree::qualified_name_of`] skips them.
    pub name: Option<Box<str>>,
    /// The syntax node this scope came from, as a range. `None` for a scope the model synthesised, such as
    /// the file scope of an empty file.
    pub range: Option<SourceRange>,
    /// **Is this an `enum` whose enumerators are visible in the enclosing scope?** — an *unscoped* enumeration
    /// (`enum E { … }` or `enum { … }`) yes, an `enum class`/`enum struct` no.
    ///
    /// Separate from [`ScopeKind::Enum`] because both forms are that kind, and the difference is exactly the
    /// lookup rule: an unscoped enumeration's enumerators are also visible one scope out, which is a second
    /// place to look rather than a second binding — see [`crate::sema::resolve::definitions_at`], which is where
    /// the extra look happens.
    ///
    /// Measured on a file with `enum { MyClass = 123, AnotherClass };` and a use of `AnotherClass` in `main`:
    /// the name resolved nowhere, so the highlighter drew no token for the use (the client's own fallback
    /// coloured it as an unknown variable) while the *definition* was coloured correctly.
    pub unscoped_enum: bool,
    /// The declarations written directly in this scope, by name.
    ///
    /// A `Vec` rather than a map because a name may be declared more than once — overloads, redeclarations, a
    /// variable shadowing a function — and returning only one of them would be a resolution decision this
    /// layer is not entitled to make. Ordered by name so a lookup can binary-search it.
    pub bindings: Vec<Binding>,
}

impl Scope {
    /// Every binding of a name in this scope, in declaration order.
    ///
    /// **This scope only.** It does not walk outward, because outward lookup is not "the parent scope" in
    /// C++: a class's base classes, a `using namespace` directive, and argument-dependent lookup all
    /// contribute, and a method that silently did only the parent walk would make a consumer's call site look
    /// complete when it is not. Outward lookup is a separate step with its own signature.
    pub fn bindings_of(&self, name: &Name) -> impl Iterator<Item = &Binding> {
        self.bindings
            .iter()
            .filter(move |binding| &binding.name == name)
    }

    /// Every name declared directly in this scope, deduplicated and sorted.
    pub fn declared_names(&self) -> Vec<&Name> {
        let mut names: Vec<&Name> = self.bindings.iter().map(|binding| &binding.name).collect();
        names.sort_unstable();
        names.dedup();
        names
    }

    /// Is this scope empty of declarations?
    pub fn is_empty(&self) -> bool {
        self.bindings.is_empty()
    }
}

/// A scope's identity.
///
/// Indices into a [`ScopeTree`] rather than pointers, for the same reason [`FileId`] is an index: the table
/// owns the scopes, so a `ScopeId` that outlives one table cannot be silently valid in another. A pointer
/// would make that mistake possible and a reference would make the table unbuildable while it is being
/// filled.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ScopeId(pub usize);

impl ScopeId {
    pub fn index(self) -> usize {
        self.0
    }
}

/// One file's scopes and bindings.
///
/// The unit the analysis layer works in, and the reason it can answer the most frequent editor questions
/// without consulting anything else: completion at a cursor needs this file's scopes, its own preprocessor
/// state, and nothing more. A table that required the project to be walked first would make every keystroke
/// cost the whole project.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct ScopeTree {
    scopes: Vec<Scope>,
    /// The file scope, when one was created. Every non-empty file has exactly one.
    root: Option<ScopeId>,
    /// The places where a scope in this table was read from a **macro's replacement list** rather than from the
    /// file's own braces — see [`MacroScopeReading`].
    ///
    /// Kept on the table because the walk that produced the scopes is the only thing that knows, and because the
    /// step that stores a summary takes the table apart anyway. Sorted by position, which is the order the walk
    /// meets them in, so two walks of the same text produce the same list.
    pub macro_readings: Vec<MacroScopeReading>,
    /// **The named scopes, by their `::`-qualified spelling** — what [`ScopeTree::scope_with_qualified_name`] answers
    /// from. Filled as the scopes are created, so the walk that joins the segments is paid once per scope rather than
    /// once per scope per query: see that function for the measurement.
    by_qualified_name: std::collections::HashMap<String, ScopeId>,
    /// **Every scope that carries a range, in creation order** — which is pre-order, so this is sorted by start.
    /// What [`ScopeTree::scope_at`] binary-searches; see that function for why it was not a scan.
    by_start: Vec<(usize, ScopeId)>,
}

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

    /// The scopes this file read out of macro bodies, in the order the walk met them.
    pub fn macro_readings(&self) -> &[MacroScopeReading] {
        &self.macro_readings
    }

    /// The file scope, if the table has one.
    pub fn root(&self) -> Option<ScopeId> {
        self.root
    }

    pub fn scope(&self, id: ScopeId) -> Option<&Scope> {
        self.scopes.get(id.index())
    }

    pub fn scope_mut(&mut self, id: ScopeId) -> Option<&mut Scope> {
        self.scopes.get_mut(id.index())
    }

    pub fn scopes(&self) -> &[Scope] {
        &self.scopes
    }

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

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

    /// Create a scope, returning its id.
    ///
    /// The file scope is recognised by having no parent, so a caller cannot create two of them by accident —
    /// a second root would make "the file's declarations" ambiguous.
    ///
    /// This is the **unnamed** form: the scope introduces nothing, which is right for a function body, a block,
    /// a lambda and a template parameter list. A scope that introduces a name — `namespace ns`, `struct Widget`
    /// — is created with [`ScopeTree::create_named_scope`], because the name is what makes a qualified name
    /// reachable and there is no moment at which a scope is usefully nameless-but-shouldn't-be.
    pub fn create_scope(
        &mut self,
        kind: ScopeKind,
        parent: Option<ScopeId>,
        range: Option<SourceRange>,
    ) -> ScopeId {
        self.create_named_scope(kind, parent, range, None)
    }

    /// [`ScopeTree::create_scope`] for a scope that **introduces a name**: `namespace ns`, `struct Widget`.
    ///
    /// The name is the *introduced* segment, not a `::`-qualified spelling: `namespace a::b` creates one scope
    /// per level and each records its own part, which is what makes `namespace a::b {` and
    /// `namespace a { namespace b {` produce the same qualified name. Joining the segments is
    /// [`ScopeTree::qualified_name_of`]'s job.
    pub fn create_named_scope(
        &mut self,
        kind: ScopeKind,
        parent: Option<ScopeId>,
        range: Option<SourceRange>,
        name: Option<&str>,
    ) -> ScopeId {
        let id = ScopeId(self.scopes.len());

        self.scopes.push(Scope {
            parent,
            children: Vec::new(),
            kind,
            name: name.map(Box::from),
            range,
            unscoped_enum: false,
            bindings: Vec::new(),
        });

        match parent {
            Some(parent) => {
                if let Some(scope) = self.scopes.get_mut(parent.index()) {
                    scope.children.push(id);
                }
            }
            None => {
                if self.root.is_none() {
                    self.root = Some(id);
                }
            }
        }

        // **The table's own index, kept as the scopes are made.** The lookup this serves used to scan every scope and
        // join its segments into a fresh `String`, per query: on a 2 800-line file a member query asked it once and
        // paid **780 ms** — the whole cost of typing `currentPos`, a local name. A map filled here is the same total
        // walk (one per scope, once per parse) and turns the query into a hash.
        if name.is_some()
            && let Some(qualified) = self.qualified_name_of(id)
        {
            // The **first** scope with a spelling wins, which is what the scan returned: a reopened namespace
            // (`namespace a { } namespace a { }`) has two scopes with one name.
            self.by_qualified_name.entry(qualified).or_insert(id);
        }

        // …and the position index [`ScopeTree::scope_at`] reads. Scopes are created in pre-order, so a scope's start
        // is never before the start of the one created just before it — the vector is sorted by construction.
        if let Some(range) = range {
            self.by_start.push((range.start_offset, id));
        }

        id
    }

    /// The `::`-qualified name of what a scope introduces, outermost segment first.
    ///
    /// `Some("ns::C")` for the body of `namespace ns { struct C { … }; }`, and `None` for a scope that
    /// introduces no name at all: a function body, a block, a lambda, the translation unit.
    ///
    /// # Which scopes contribute a segment
    ///
    /// A name-bearing scope contributes its own name; a scope that bears no name contributes nothing *and
    /// stops nothing* — walking past it continues to whatever encloses it. That is what makes `void ns::f() {`
    /// and `void f() {` agree: the function body is transparent in both, and only the namespace the function
    /// was written in is part of the answer.
    ///
    /// The one kind that must **stop** the walk rather than pass through is an unnamed [`ScopeKind::Class`] or
    /// [`ScopeKind::Enum`]: what a member declares is `C::m` and never `ns::m`, so a class with no name of its
    /// own is a dead end — it has no segment to contribute and none to inherit, and continuing past it would
    /// invent a qualification that does not exist.
    pub fn qualified_name_of(&self, scope: ScopeId) -> Option<String> {
        let mut segments: Vec<&str> = Vec::new();
        let mut seen = HashSet::new();
        let mut current = Some(scope);

        while let Some(id) = current {
            // A cycle cannot occur in a table this type builds, but a hand-constructed one could — the same
            // guard `scope_chain` carries, for the same reason.
            if !seen.insert(id) {
                break;
            }

            let Some(scope) = self.scopes.get(id.index()) else {
                break;
            };

            match &scope.name {
                Some(name) => segments.push(name),
                None if matches!(scope.kind, ScopeKind::Class | ScopeKind::Enum) => break,
                None => {}
            }

            current = scope.parent;
        }

        if segments.is_empty() {
            return None;
        }

        segments.reverse();
        Some(segments.join("::"))
    }

    /// Add a binding to a scope.
    ///
    /// `false` when the scope does not exist, or when its [`ScopeKind`] cannot hold a binding of this kind —
    /// a label in a namespace, say. Reported rather than panicking because this layer runs on malformed
    /// input, and a rejected binding is a gap a consumer can see while a panic is an editor that stops
    /// working.
    pub fn add_binding(&mut self, scope: ScopeId, binding: Binding) -> bool {
        let Some(target) = self.scopes.get_mut(scope.index()) else {
            return false;
        };

        if !accepts_binding(target.kind, binding.kind) {
            return false;
        }

        // Kept sorted by name so a lookup can binary-search, and stable within a name so that declaration
        // order survives — a consumer showing overloads shows them in the order they were written.
        let position = target
            .bindings
            .partition_point(|existing| existing.name <= binding.name);

        target.bindings.insert(position, binding);
        true
    }

    /// The prefix a declaration written **in** this scope is qualified by: the scope's own qualified name,
    /// for a scope that is part of a qualified name at all.
    ///
    /// The difference from [`ScopeTree::qualified_name_of`] is one question: does the scope's own name count?
    /// For the scope that *introduces* an entity it does — `namespace ns` introduces `ns`, so a declaration
    /// written in it is `ns::x`. For a scope that merely *holds* declarations it does not: a member of
    /// `struct C` is `C::member` and not `C::C::member`, and a local in `void f()` is `local` and not `f::local`
    /// — or worse, `ns::f::local`, since a function body's name is not a scope a name can be written from.
    ///
    /// So the same set of transparent scopes is skipped, and the answer is then used as a **prefix** rather
    /// than as the name itself. A file scope and a function body both end up with `None`, which is the same
    /// answer and for the same reason: neither contributes a segment, and neither has a name to start from.
    pub fn qualification_prefix_of(&self, scope: ScopeId) -> Option<String> {
        match self.scopes.get(scope.index())?.kind {
            // A scope whose own name is the first segment of everything written inside it.
            ScopeKind::Namespace | ScopeKind::Class | ScopeKind::Enum => {
                self.qualified_name_of(scope)
            }
            // A file, a function body, a block, a lambda, a template parameter list: declarations written here
            // are not qualified by anything this scope knows, and walking outward would attribute them to an
            // enclosing entity they are not part of.
            ScopeKind::TranslationUnit
            | ScopeKind::Function
            | ScopeKind::Block
            | ScopeKind::Lambda
            | ScopeKind::TemplateParameters => None,
        }
    }

    /// The scope that contains `offset`, innermost first.
    ///
    /// "Innermost" is the scope with the smallest range containing the offset, which is what a consumer at a
    /// cursor position needs. `None` when the table has no scope covering the offset — an offset past the end
    /// of the file, or a table built from a different source.
    pub fn scope_at(&self, offset: usize) -> Option<ScopeId> {
        // **The latest-started scope, then its parents.** Every scope containing the offset is on the ancestry chain
        // of the scope started last but not after it, so walking up from that one finds the innermost in
        // O(log n + depth) instead of the O(scopes) scan this used to be — and it was asked once per name lookup in
        // the inference, which on a 2 800-line file is thousands of times per diagnostics pull.
        let at = self.by_start.partition_point(|(start, _)| *start <= offset);
        let mut current = at.checked_sub(1).map(|index| self.by_start[index].1);
        while let Some(id) = current {
            let scope = self.scopes.get(id.index())?;
            if let Some(range) = scope.range
                && offset >= range.start_offset
                && offset <= range.end_offset()
            {
                return Some(id);
            }
            current = scope.parent;
        }
        None
    }

    /// The chain from a scope outward to the file scope, innermost first.
    ///
    /// Innermost-first because that is the order C++ lookup considers them, so a consumer walking the chain
    /// is walking in the order the language does. It stops at the file scope: crossing into another file is
    /// the include graph's business, not this table's.
    pub fn scope_chain(&self, from: ScopeId) -> Vec<ScopeId> {
        let mut chain = Vec::new();
        let mut seen = HashSet::new();
        let mut current = Some(from);

        while let Some(id) = current {
            // A cycle cannot occur in a table this type builds, but a hand-constructed one could, and a
            // consumer that hung on it would be worse than one that stopped early.
            if !seen.insert(id) {
                break;
            }

            let Some(scope) = self.scopes.get(id.index()) else {
                break;
            };

            chain.push(id);
            current = scope.parent;
        }

        chain
    }

    /// The scopes whose declarations are visible from `scope`, innermost first.
    ///
    /// The scope chain, and beside every **unnamed namespace** in it, the scope that namespace holds.
    /// [namespace.def] says an unnamed namespace is equivalent to `namespace unique { … } using namespace unique;`
    /// — its members are visible in the enclosing scope for the rest of the file, and only in this file. A plain
    /// [`ScopeTree::scope_chain`] walk therefore misses the shape every C++ file with internal linkage uses:
    ///
    /// ```cpp
    /// namespace { int helper(int); }     // internal linkage by construction
    /// int use(int n) { return helper(n); }
    /// ```
    ///
    /// `helper` is declared in the unnamed namespace's scope, which is a *child* of the file scope rather than an
    /// ancestor of the use, so a chain walk never reaches it and the name reads as undeclared.
    ///
    /// The returned list is not ordered by the language's lookup rules beyond "innermost first" of the chain;
    /// a consumer that must respect a declaration's position (a name is visible from its declaration onward) still
    /// has to compare offsets itself.
    pub fn scopes_visible_from(&self, from: ScopeId) -> Vec<ScopeId> {
        let mut visible = self.scope_chain(from);
        // The list grows while it is walked, which is what takes the descendants of an unnamed namespace too:
        // `namespace { namespace { int x; } }` is two levels of the same rule.
        let mut index = 0;
        while index < visible.len() {
            let id = visible[index];
            index += 1;
            let Some(scope) = self.scopes.get(id.index()) else {
                continue;
            };
            for child in &scope.children {
                let Some(child_scope) = self.scopes.get(child.index()) else {
                    continue;
                };
                if child_scope.kind == ScopeKind::Namespace && child_scope.name.is_none() {
                    visible.push(*child);
                }
            }
        }
        visible
    }

    /// The scope a `::`-qualified spelling names: `ns::C` for the body of `namespace ns { struct C { … }; }`.
    ///
    /// The counterpart of [`ScopeTree::qualified_name_of`], and the reason a *qualified* name can be resolved at
    /// all: `ns::C::f` is not a name to look up, it is a scope to find and then a name to look up **in it**. The
    /// spelling is compared against the joined segments rather than parsed, so `namespace a::b {` and
    /// `namespace a { namespace b {` — which produce the same spelling — are found by the same query.
    ///
    /// # Why this is a map rather than a scan
    ///
    /// It was `(0..len).find(|id| self.qualified_name_of(*id).as_deref() == Some(name))` — a scan of every scope in
    /// the file, each one joining its ancestors into a **fresh `String`**. That is a per-file table's worth of work
    /// per *query*, and a member query asks it once: measured on `LuaSyntaxTree.cpp` (2 800 lines), typing the local
    /// `currentPos` cost **780 ms**, and one member access `_nodeOrTokens.size()` **2 340 ms** over the file — both
    /// almost entirely this function. The map is built as the scopes are created, so the same joining happens once
    /// per scope per parse; a query is a hash and a copy of the id.
    ///
    /// `None` when no scope bears that name — including for the empty spelling, which no scope records: the file
    /// scope has no name of its own and is reached through [`ScopeTree::root`].
    pub fn scope_with_qualified_name(&self, name: &str) -> Option<ScopeId> {
        self.by_qualified_name.get(name).copied()
    }

    /// Is a declaration written in this scope **local** — nameable only from inside the body it sits in?
    ///
    /// True when the chain outward reaches a function body, a block or a lambda, however far in it is: a local
    /// class, a `typedef` in a loop, a variable in a member function. False at file scope, in a namespace, and in a
    /// class body — a *member* function's declaration is not local, only its body is.
    ///
    /// The three kinds are the ones whose name reaches no qualified name ([`ScopeTree::qualification_prefix_of`]
    /// lists the same set from the other side): a function, a block and a lambda each introduce no segment, so a
    /// declaration inside one has a bare name and no scope to be found in. What this adds is the thing a consumer
    /// needs and a qualified name cannot say: *which* of the two `None`-scoped cases a declaration is.
    ///
    /// The file scope is deliberately not "local": a declaration written directly at file scope is visible to every
    /// file that includes this one, which is the whole distinction.
    /// **The binding a name written at `offset` introduces** — the cursor is on a declaration's own name.
    ///
    /// Ordinary lookup answers "which declaration does this *use* refer to"; a name at its own declaration refers to
    /// itself, and no scope walk was ever asked that. It is the first question every cursor feature asks, and it is
    /// why hovering an enumerator's **definition** answered nothing while hovering its use answered fine — measured on
    /// `enum { MyClass = 123, AnotherClass };`, where `definitions` at `AnotherClass`'s own offset answered
    /// `Unknown(UnparsableName)`: an enumerator's name is a plain token rather than a `NameExpr`, so the reader that
    /// takes a name's spelling had nothing to read.
    ///
    /// First in creation order, which is declaration order for the scopes a file writes: two declarations' name ranges
    /// do not overlap, so the order only decides a malformed file.
    pub fn binding_declared_at(&self, offset: usize) -> Option<&Binding> {
        self.scopes
            .iter()
            .flat_map(|scope| scope.bindings.iter())
            .find(|binding| binding.name_range.contain(offset))
    }

    pub fn declares_a_local(&self, scope: ScopeId) -> bool {
        self.scope_chain(scope).iter().any(|id| {
            matches!(
                self.scopes.get(id.index()).map(|scope| scope.kind),
                Some(ScopeKind::Function | ScopeKind::Block | ScopeKind::Lambda)
            )
        })
    }
}

/// Can a scope of this kind hold a binding of that kind?
///
/// The rules are small and worth writing down because getting them wrong is silent: a label added to a
/// namespace would make `goto` completion offer names that cannot be jumped to, and a namespace added to a
/// function would make `namespace ns { }` inside a body look like it declared something at file scope.
///
/// A label is only legal in a function or a block; a namespace is only legal at file scope or inside another
/// namespace; and a template parameter list holds template parameters and nothing else, because it is the one
/// scope in C++ that is not a place for a declaration.
fn accepts_binding(scope: ScopeKind, binding: BindingKind) -> bool {
    match binding {
        BindingKind::Label => matches!(
            scope,
            ScopeKind::Function | ScopeKind::Block | ScopeKind::Lambda
        ),
        BindingKind::Namespace | BindingKind::UsingDirective => {
            matches!(scope, ScopeKind::TranslationUnit | ScopeKind::Namespace)
        }
        BindingKind::TemplateParameter => matches!(scope, ScopeKind::TemplateParameters),
        // A template parameter list is the one scope a declaration cannot appear in: `template <int N, int x;>`
        // is not a thing, and a `Variable` binding there is a sign the extractor misread a default argument.
        // Everything else is legal wherever a declaration is.
        _ => !matches!(scope, ScopeKind::TemplateParameters),
    }
}