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
//! Semantic classification: **what each name in a file is**, as far as this analysis can tell.
//!
//! A semantic highlighter's question is asked once per identifier in a file, and the honest cheap answer is "what
//! does this name resolve to" — the question this crate already answers everywhere else, through the scope tree for
//! a name written here and through the index for one a header declares. Nothing here is a new reading of the
//! language. What it is, is the **bulk form** of that question:
//!
//! ```text
//! for every identifier token, in source order:
//! 1. is it the name a declaration gives itself? the scope tree's bindings carry the name's own span, so
//! this is one hash lookup → `declaration: true`
//! 2. is it a `#define` this file writes? the directive list, which is also the only layer that can
//! answer for a macro — a macro is not a declaration
//! 3. otherwise, which declaration does it refer to? `sema::resolve::definition_at` — this file's own scopes —
//! and then the index, asked **once per distinct spelling**
//! 4. and if nothing answers **no** classification: a colour is a claim, and this layer
//! only makes claims it can support
//! ```
//!
//! # Why the reference question, and not a spelling map
//!
//! The first version of this module answered step 3 by **spelling**: it built a map from "what this file declares",
//! keyed by the declared name, and classified every use of that spelling as if it named that declaration. It is
//! cheap — one map, no lookup — and it is wrong in the ways a reader notices first:
//!
//! ```text
//! struct Widget { int size; }; the use of `size` in `scale` refers to the **parameter**, and the use of
//! int size(int value); `size` in `area` is a member of `Widget`. A map keyed on the spelling
//! int scale(Widget& w, int size) { cannot tell either of them apart from the file-scope function that
//! return w.size * size; happens to share the spelling, so it drew all three as `Function`.
//! }
//! ```
//!
//! The correction is not a better guess at the same question — it is asking the question the answer is a fact
//! about, which this crate already knows how to ask. Both misclassifications are pinned as tests
//! (`tests/semantic.rs`), and the vocabulary that falls out of it ([`Provenance`]) is what the probe prints.
//!
//! # Where each answer comes from, said out loud
//!
//! Each [`Name`] carries its [`Provenance`], because "the scope tree says so" and "the index says so" are answers
//! with different strengths: the first is a binding with a kind, the second a summary fact whose kind is coarser (a
//! parameter of a function in another file arrives as a local variable — the summary does not keep the
//! distinction). A consumer that wants to draw only what is certain can filter on it, a probe can print it, and a
//! reader of a bug report can see which layer answered.
//!
//! # Why the file's own answer is never second-guessed
//!
//! [`definition_at`] implements C++ ordinary lookup over one file's scopes — the shadowing rule, the enclosing
//! scopes, `using namespace` targets. Whatever it finds **is** what the name means in this file, so the index is not
//! consulted on top of it: an index keyed on bare names cannot see a scope, and asking it would replace a known
//! answer with a coarser one. The index is asked exactly when the file's scopes have nothing to say, which is the
//! case it exists for: a name a header declares.
//!
//! A name the file declares somewhere but **cannot see from here** is the same rule read the other way, and it is
//! why the step below does not fall through to the index on a miss: what the file declares under that spelling is
//! either out of scope at this position or a member of a class, and an index keyed on bare names would answer with
//! some *other* declaration that happens to share the spelling.
//!
//! # What a name is *not* classified by
//!
//! Nothing here asks the parser whether a name stands in a type position. `Widget w;` and `Widget(1)` are a type
//! and a constructor call, and the tree shape differs — but the *kind* a highlighter wants is the one the
//! **declaration** has, and reading it from the declaration is how the two spellings agree. A name the analysis
//! cannot place at all gets no classification rather than a guess from its shape.
//!
//! # What the answer depends on, and what it does not
//!
//! The file's text, its scope tree, and the index — not the cursor, and not the client. A file whose includes have
//! not been read yet answers with **fewer** classifications rather than with different ones: a smaller index
//! resolves fewer spellings, and every name this file declares itself is answered the same way whatever the index
//! holds.
//!
//! # What it costs, and where that was measured
//!
//! `examples/semantic_probe.rs` is the instrument, and it prints the time and the distribution of the answers by
//! [`Provenance`]. Measured on the MinGW standard-library closure (356 files, the 45 largest classified, 19 797
//! identifiers, release): **35 ms for 5 591 classifications — 1.8 µs per identifier**. Three findings from building
//! it are worth keeping, because each one was two orders of magnitude away from where it looked:
//!
//! ```text
//! · a tree descent per spelling 600 ms of a 630 ms pass. `qualified_name_at` walks down to the
//! offset, which is the right price for a cursor and the wrong one
//! for every name in a file — see `qualified_names`
//! · a member access rejected by reading it `(a && b)` parses as the same node kind `w.size` does, so a
//! header of 447 `#if defined(…)` conditions paid a subtree walk per
//! condition to learn there is no member access in it
//! · a scope walk for a name no scope binds one `HashSet` of the spellings this file declares is the filter
//! ```
use ;
use Path;
use ;
use crateIndexedKind;
use crateDirective;
use cratedefinition_at;
use crate;
use crate::;
/// What a name is, in as many kinds as this analysis can honestly tell apart.
///
/// The set is chosen against what a client can draw (the protocol's own token types) rather than against the
/// model: a caller maps these onto its legend, and a kind nobody can draw is a kind that should not be here.
/// Where a classification came from — which layer answered, and therefore how strong the answer is.
///
/// Not decoration: these are different kinds of evidence, and a consumer that has to decide whether to draw a name
/// at all needs to be able to tell them apart. See the module documentation.
/// One name in a file, with what it is.
/// **A property of a name that is not its kind** — what a client draws as a *modifier* beside the colour.
///
/// The protocol has a fixed set of these and a client declares which it can draw, so this is chosen against that set
/// rather than against the language: `readonly` for a `const` object, `static` for one with internal linkage or no
/// instance, `deprecated` for a declaration that says so.
///
/// # Why only the file's own declarations have one
///
/// Because a modifier is a fact about a **declaration**, and the only declarations this layer can read are the ones
/// in the file in hand: the specifiers are tokens of a tree that is already parsed. A declaration reached through
/// the index carries a kind, a scope and a type — and none of those is "is this object `const`" — so a use of a
/// header's `const` variable is drawn without the modifier rather than with a guess. That is the direction this whole
/// module fails in: a colour missing is a colour the client's own theme supplies.
/// **What each name in this file is** — the classification a semantic highlighter draws colours from.
///
/// Every identifier in the file is considered, in source order; one that nothing can be said about is left out
/// rather than guessed at. The result is therefore a list of *claims*, and the caller draws only those.
///
/// # The questions, in order
///
/// 1. **is this identifier a declaration's own name?** The scope tree's bindings carry a name range, so this is a
/// map lookup — and the binding's kind is finer than anything the index records: an enumerator is not a
/// variable, a constructor is not a function, and a *parameter* is distinguishable from a local.
/// 2. **is it a `#define` this file writes?** A macro is not a declaration in the C++ tree at all, so nothing in
/// the scope tree can answer for it — and where a spelling is both, the preprocessor's reading is the one a
/// reader is looking at.
/// 3. **otherwise, which declaration does it refer to?** [`definition_at`] answers for the position, within this
/// file: the scope chain from the offset, the enclosing scopes, and `using namespace` targets. It is the same
/// answer "go to definition" gives, so a name that jumps somewhere is a name that is coloured — and a shadowed
/// local is coloured as the local rather than as the file-scope declaration sharing its spelling.
/// 4. **otherwise the index**, asked once per **spelling** — and asked with the name as written, so `std::size_t`
/// is a question about that name rather than about `size_t`. The cache holds the misses too, which is what makes
/// a file full of library names cheap rather than quadratic.
///
/// A member access (`w.size`) is deliberately **not** resolved by step 3: the member belongs to the type of `w`,
/// the index is what knows a class's members, and claiming one from the scope chain is the spelling mistake in
/// another costume. Such a name reaches step 4, where the question is the bare name the file wrote — and where an
/// answer that several unrelated declarations share comes back `Ambiguous` and gets **no** colour, which is this
/// layer's way of refusing to guess.
/// The file's **own** declarations, by the offset of the name each gives itself.
///
/// A binding's `name_range` is the identifier the declaration introduces — the same span a rename edits — which is
/// exactly the offset an identifier token starts at. So "is this token a declaration's own name" is one hash
/// lookup per token, and it is asked for every identifier in the file.
/// What the name written at `offset` refers to, **within this file**.
/// Every spelling this file **declares as an ordinary identifier**: a binding's own name, from every scope in the
/// table.
///
/// Not the same question as [`declarations_by_offset`], which is keyed by *where* a name is declared; this is keyed
/// by the name, and asked about a *use*. It exists as a filter rather than as an answer: a scope walk that cannot
/// succeed is the expensive way to learn nothing, and most of what a header's identifiers are is names declared
/// somewhere else entirely — in the standard library, or nowhere this file can see.
///
/// Ordinary identifiers only, which is why the raw spelling is read rather than [`crate::Name::text`]: a
/// constructor, a conversion operator and a literal are *found* by their own rules (a destructor is not found by
/// ordinary lookup at all), so a `~`/`operator`-shaped spelling matched against raw source text would be a filter
/// that lets nothing through and costs a lookup to learn it.
/// The offsets at which the file writes a **member access** — the `size` of `w.size`.
///
/// Keyed by *offset* and not by spelling, which is the whole point: `size` is also the name of a parameter in the
/// fixture that pins this, and a set of spellings would make every `size` in the file a member access. The same
/// spelling in two places can be two different questions, so the position is part of the question.
///
/// An access whose member is not written yet (`w.`) contributes nothing, which is right — there is no name to
/// classify.
///
/// # Why the operator is looked for before the member is read
///
/// The parser produces an [`IndexExpr`](cpp_parser::CppSyntaxKind::IndexExpr) for `w.size` **and** for `(a && b)` —
/// one node kind with a `.` where brackets would be, which is why [`member_access_of`] decides by the operator
/// rather than by the kind. So a file full of `#if defined(A) && defined(B)` is a file full of nodes this walk has
/// to *reject*, and rejecting one costs whatever `member_access_of` costs: it collects every identifier below the
/// operator it is looking for. On a header of 447 nested conditions that was the entire cost of the pass — a
/// subtree walk per condition to learn that there is no member access in it.
///
/// The operator among the node's **direct children** answers the same question for the price of one child list,
/// because an operator is a direct child of the expression it belongs to.
///
/// [`member_access_of`]: crate::sema::resolve::member_access_of
/// **What else is true of the declaration a name is**, from the file's own tokens.
///
/// The specifiers are the tokens between the start of a declaration and its name, and they are read the way every
/// other spelling in this project is: by text, from a tree that is already parsed. `constexpr` counts as `const`
/// because it is one — an object `constexpr int n` cannot be written through either — and `const` is looked for as a
/// **word**, so `constexpr` and `const_iterator` are not mistaken for it.
///
/// `None` for a name whose declaration this layer cannot see: a use of a name from a header, whose specifiers are not
/// in any tree this pass holds. See [`NameModifier`] for why that is the right answer rather than a guess.
/// `shapes` is the **file's** shape table, built once by the caller — see [`classified_names`]. It is a
/// [`OnceCell`](std::cell::OnceCell) because a file whose colouring reaches no value declaration should not pay for
/// one, and a file with two thousand of them must not pay for two thousand.
/// **What each member access in this file names**, by the offset of the member.
///
/// # Why a scope tree cannot answer this, and what the first version settled for
///
/// `w.size` is resolved through the **type of `w`**, which is not a scope: what this file declares under the
/// spelling `size` says nothing about it. The first version collected the member offsets and let them fall through
/// to the index by their **bare name** — and that is where the feature stopped working, because a bare member name
/// is exactly the spelling the whole project shares: measured on a real file, `v.push_back` and `t.size()` got **no
/// colour at all** (the index answers `Ambiguous` and this layer refuses to guess) while `sux.print()` did, because
/// `print` happens to be unique in that project. A reader saw every standard-library member go grey and concluded
/// the highlighter was crude — which it was, in the one place members are the whole point.
///
/// The answer is the one the note above has always named: ask the **type**. [`member_across_files`] is the query
/// that does it — the same one a jump to a member's declaration uses, so a member that can be jumped to is a member
/// that is coloured — and its answer carries the declaration's kind, which is what a colour is chosen from.
/// The declaration the name at `offset` refers to, within this file — see [`Held`].
///
/// The caller has already excluded the two shapes that are not this question: a declaration's own name (a map
/// lookup, and the only one that sets [`Name::declaration`]) and a member access ([`member_offsets`], and the note
/// there for why a scope tree cannot answer one). What is left is ordinary lookup, which is [`definition_at`]'s own
/// question, so this is a call rather than a rule.
/// Is this scope inside a class?
/// The offsets of every **parameter's name** in the file.
///
/// Read from the tree rather than from the bindings, because a binding does not record how it was declared: the
/// scope model binds a parameter and a local in the same scope, in the same kind, and the two are the same thing
/// to every *lookup*. A highlighter is the one consumer that has to tell them apart — a reader expects a
/// parameter to look like a parameter — and the parameter list is where the difference is written.
///
/// Keyed by the span the name was declared with, so one set answers both questions this module asks: "is this
/// declaration a parameter" (the token's own offset is in it) and "does this use name a parameter" (the binding's
/// `name_range` is).
/// The names this file `#define`s, by spelling — with the range of each name as written.
///
/// From the **directives** rather than from the macro table in force, and the difference is deliberate: the table
/// answers "what is defined at this offset", which is a position question per identifier, while a reader's question
/// is "is this name a macro in this file at all". A macro defined in a branch nobody takes is still a name the file
/// defines and a reader sees.
/// The spellings the file writes **with a qualifier**, by the offset each identifier starts at: `std::size_t` at
/// the offset of `size_t`, and `ns::Widget<int>` at the offset of `Widget`.
///
/// Asked because an index keyed on bare names cannot tell `a::Widget` from `b::Widget`, and a file that writes the
/// qualifier is telling the analysis which one it means.
///
/// # Why it is a map built in one walk rather than a query per name
///
/// [`qualified_name_at`](crate::sema::resolve::qualified_name_at) answers this for a cursor, and it does so by
/// **descending the tree** from the root to the offset — which is the right price for one cursor and the wrong one
/// for a pass that asks about every spelling in a file. Measured on `bits/version.h` (3 669 identifiers, 606 `::`
/// written in `#if defined(__glibcxx_want_…)` conditions): calling it per spelling was **600 ms of a 630 ms
/// pass** — 95% of the work, spent descending to names that are not qualified at all.
///
/// The walk here looks for the `::` among a name node's **direct children** first, which is what tells a qualified
/// spelling from a bare one, and descends no further for the names that have none. A bare name needs no entry: its
/// spelling *is* the token's own text, which is what the caller already has.
/// The name as written, with the leading `::` of a global name put back.
/// What a binding is, or `None` for a name a highlighter should not claim anything about.
/// What an indexed declaration of this shape is, for a colour.
///
/// Coarser than a binding, and the two are not merged into one function because they are not the same question: the
/// index records what a summary can hold (a kind, a scope name, whether the declaration is local), while a binding
/// knows which *scope object* it was bound in. A parameter of a function in another file, for example, arrives here
/// as a local variable — the summary does not keep the distinction, and guessing it from the spelling would be a
/// guess.
///
/// **A scoped function is a method**, and a namespace is the price of that: a summary records the scope's
/// *spelling* and not whether it is a class, so `std::to_string` arrives looking exactly like a member. The
/// alternative is to draw every library function as a free one, which is wrong about all of them; this is wrong
/// about the ones in a namespace, and only in the modifier a client draws differently.