devscout_rs/resolve/index.rs
1use crate::graph::{AlsoIn, Def, FragExtensionMethod, FragFact, FragRef, Fragment, OrderedMap};
2use std::collections::{HashMap, HashSet};
3
4// ---------------------------------------------------------------------------
5// Def index.
6// ---------------------------------------------------------------------------
7
8/// `Vec<Def>` in first-insertion order (partial-class duplicates land in
9/// `also_in`, never as a second Vec entry) plus two lookup indexes over it:
10/// `qualified_name_to_def` (id -> index, every def incl. enum members) and
11/// `simple_name_to_defs` (bare name -> indexes, EVERY def EXCEPT enum members
12/// -- the asymmetry described in the module header).
13pub struct DefIndex {
14 /// The defs value.
15 pub defs: Vec<Def>,
16 /// Parallel to `defs` (same indexes), NOT fields on `Def`: a def's
17 /// property/field lists are RESOLUTION inputs only. No graph.json reader
18 /// consumes them (graph-query walks EDGES), so serializing them would
19 /// multiply the def table's size on disk and in every `scout refs`/`scout
20 /// impact` read for nothing. Keeping them off `Def` keeps the on-disk def
21 /// rows to exactly the serialized fields.
22 pub member_lists: Vec<MemberLists>,
23 /// The qualified name to def value.
24 pub qualified_name_to_def: HashMap<String, usize>,
25 /// The qualified name and arity to def value.
26 pub qualified_name_and_arity_to_def: HashMap<(String, usize), usize>,
27 /// The simple name to defs value.
28 pub simple_name_to_defs: HashMap<String, Vec<usize>>,
29 /// The extension tier's own lookup: "<method_name> <this_type>" (one ASCII
30 /// space) -> every candidate declaring that PAIR, as (def index, entry).
31 ///
32 /// The key was the (name, this_type, arity) TRIPLE until the range
33 /// amendment. Arity moved out of the key and into a per-entry range filter
34 /// because an exact arity is not the language's rule:
35 /// `Send(this T t, X a, Y b = null)` accepts two OR three arguments, and
36 /// keying on 3 alone made a call with two arguments miss it -- which in turn
37 /// made a DIFFERENT class's exact-arity-2 `Send` look like the only
38 /// candidate and win an edge it had no right to -- the false-uniqueness
39 /// shape.
40 ///
41 /// Build order is def order -- files in fragment-map order, defs in source
42 /// order, extension entries in declaration order -- so a bucket holding two
43 /// candidates holds them in the same order on every run. The tier refuses on
44 /// a 2-candidate bucket anyway; the order is pinned because it is what a
45 /// later scored tier would read.
46 pub extension_index: HashMap<String, Vec<ExtCandidate>>,
47 /// Member name -> every def that vouches for a member of that name, the
48 /// pool the scored tier's UNIQUENESS FALLBACK draws from when a ref's
49 /// qualifier resolves to nothing at all (`x.Tally()` where the extractor
50 /// could vouch for no type for `x`). Built AFTER the main def loop, not
51 /// during it, so a partial class contributes its accumulated member set once
52 /// instead of appearing in a bucket per declaring file.
53 ///
54 /// Insertion order is def order (fragment order, then source order), and
55 /// within one def the names are collected methods -> properties -> fields ->
56 /// extension-method names, first insertion winning. This order decides which
57 /// candidates a `<= SCORED_UNIQUENESS_CAP` pool holds.
58 pub member_name_to_defs: HashMap<String, Vec<usize>>,
59}
60
61/// One bucket slot: which def declares the entry, and the entry itself (the
62/// range + generic-argument facts the tier filters on).
63pub struct ExtCandidate {
64 /// The def idx value.
65 pub def_idx: usize,
66 /// The entry value.
67 pub entry: FragExtensionMethod,
68}
69
70/// The non-method halves of a def's member surface. `methods` stays on `Def`
71/// (it IS serialized).
72#[derive(Default)]
73pub struct MemberLists {
74 /// The properties value.
75 pub properties: Vec<String>,
76 /// The fields value.
77 pub fields: Vec<String>,
78 /// Kept here for the same reason as `properties`/`fields`: a resolution
79 /// input, never a serialized def field. Holds the (name, this_type,
80 /// arity_min, arity_max) QUADRUPLES this def has already contributed, so a
81 /// partial class re-declaring one of its own entries in a second file can
82 /// never push the def into its own extension bucket twice and make itself
83 /// look like two candidates.
84 pub extension_methods: Vec<(String, String, usize, i64)>,
85 /// DIRECT base-type names, unioned across a partial class's declarations,
86 /// resolved LAZILY by the veto walk.
87 pub bases: Vec<String>,
88 /// The declaring type's own type-parameter names (empty for a non-generic
89 /// declaration). A resolution input, like `bases`: the ctor-DI resolver's
90 /// "is this def itself an open-generic implementation" signal. First
91 /// declaration wins, like `namespace`/`kind` -- not unioned across a partial
92 /// class the way `bases` is.
93 pub type_params: Vec<String>,
94 /// Per base name that carried a type-argument list, that list's generic-arg
95 /// descriptors relative to `type_params`. First declaration wins, same as
96 /// `type_params`.
97 pub base_generic_args: Vec<(String, Vec<String>)>,
98 /// Method name -> declared return type NAME, the fact that turns a
99 /// `var x = Q.M(...)` local into an ordinary receiver. A partial class's
100 /// later parts contribute the names the first part did not answer; a name it
101 /// already answered keeps its answer.
102 pub method_returns: OrderedMap<String>,
103 /// Property name -> declared type fact, the second half of a property hop.
104 /// Merged across a partial class exactly like `method_returns`.
105 pub property_types: OrderedMap<FragFact>,
106 /// Field name -> declared type fact, the field half of a bare-identifier
107 /// receiver's type when the file that reads it carries no local/
108 /// parameter/field fact of its own for the name (a sibling partial-class
109 /// file's field, reached only through this merged table). Merged across
110 /// a partial class exactly like `property_types`.
111 pub field_types: OrderedMap<FragFact>,
112 /// The file whose declaration supplied each `property_types` /
113 /// `field_types` entry -- one key per key of the table beside it, filled
114 /// in at merge time. Purely an in-memory bookkeeping table (nothing here
115 /// is serialized), and the only record of WHERE a merged fact came from:
116 /// a partial class's def carries the FIRST declaring file, which is not
117 /// necessarily the file that declared any given member. The type name a
118 /// fact holds is a bare identifier that only means anything under the
119 /// `using` directives, aliases and namespace of the file that WROTE it,
120 /// so `bare_receiver_field_or_property_type`'s caller resolves it in
121 /// that file's context rather than the reading file's.
122 pub property_type_files: OrderedMap<String>,
123 /// The `field_types` half of `property_type_files`.
124 pub field_type_files: OrderedMap<String>,
125 /// Method name -> the generic-arg descriptors `method_returns` itself
126 /// strips off (see `FragDef.method_return_args`), read ONLY by the
127 /// awaited-call unwrap: an entry here exists exactly when the same name
128 /// has a `method_returns` entry AND that return type carried a
129 /// top-level type-argument list. Merged across a partial class exactly
130 /// like `method_returns`.
131 pub method_return_args: OrderedMap<Vec<String>>,
132 /// Declared method names `methods` (on `Def`) does not carry -- see
133 /// `FragDef.non_public_methods`. Merged across a partial class exactly
134 /// like `properties`/`fields` (union, first-insertion order). Read ONLY
135 /// by `declares_member_any_visibility`, itself read ONLY for
136 /// hierarchy-internal receivers (`base.` and the `this.` shape's own
137 /// base walk); every other caller of a "does this def declare the
138 /// member" question keeps reading `Def.methods` alone.
139 pub non_public_methods: Vec<String>,
140 /// Method name -> the (min, max) argument-count ranges the overloads
141 /// sharing that name accept -- see `FragDef.method_arities`. Merged
142 /// across a partial class as a UNION of ranges per NAME, the way
143 /// `Def.methods` unions the names themselves: every declaring part
144 /// contributes the overloads it declares, duplicates dropped, because
145 /// the parts of one partial class share a single overload set and a
146 /// call some part's overload accepts is a call the type accepts. Read
147 /// by `declares_member`/`declares_member_any_visibility` for a ref that
148 /// carries an `argCount`.
149 pub method_arities: OrderedMap<Vec<(usize, i64)>>,
150 /// Method name -> the overloads' own parameter-descriptor lists, each
151 /// paired with the file whose fragment declared it -- see
152 /// `FragDef.method_params`. Merged across a partial class as a UNION per
153 /// NAME, the way `method_arities` is: every declaring part contributes
154 /// the overloads it declares, an overload whose `params` list already
155 /// exists for that name skipped (first file wins for duplicates). In
156 /// memory only; nothing here is serialized.
157 pub method_params: HashMap<String, Vec<MethodOverloadParams>>,
158}
159
160/// One method overload's parameter-descriptor list plus its declaring file.
161///
162/// The (params, file) pair `MemberLists::method_params` keeps per method
163/// name. In-memory resolution input only; nothing here is serialized.
164pub struct MethodOverloadParams {
165 /// The parameter type descriptors, in order (see extract.rs's
166 /// `type_descriptor`/`DefRecord::method_params`).
167 pub params: Vec<String>,
168 /// The fragment-relative file path that declared this overload.
169 pub file: String,
170}
171
172#[allow(
173 clippy::too_many_lines,
174 clippy::cognitive_complexity,
175 reason = "one ordered pass building every lookup table the resolver ladder reads, so the tables stay mutually consistent"
176)]
177pub(super) fn build_def_index(fragments_by_file: &[(String, Fragment)]) -> DefIndex {
178 let mut defs: Vec<Def> = Vec::new();
179 let mut member_lists: Vec<MemberLists> = Vec::new();
180 let mut qualified_name_to_def: HashMap<String, usize> = HashMap::new();
181 let mut qualified_name_and_arity_to_def: HashMap<(String, usize), usize> = HashMap::new();
182 let mut simple_name_to_defs: HashMap<String, Vec<usize>> = HashMap::new();
183 let mut extension_index: HashMap<String, Vec<ExtCandidate>> = HashMap::new();
184
185 // One entry per key of `map`, all naming `file` -- the shape
186 // `MemberLists::property_type_files`/`field_type_files` hold for a def's
187 // FIRST declaration, where every fact came from the same file by
188 // construction.
189 fn keys_mapped_to_file<V>(map: &OrderedMap<V>, file: &str) -> OrderedMap<String> {
190 let mut out = OrderedMap::new();
191 for (name, _) in map.iter() {
192 out.insert(name.clone(), file.to_string());
193 }
194 out
195 }
196
197 // Dedupe on the def's OWN quadruple list FIRST, then push into the bucket --
198 // the guard is what keeps one def out of the same bucket twice.
199 fn add_extension_method(
200 member_lists: &mut [MemberLists],
201 extension_index: &mut HashMap<String, Vec<ExtCandidate>>,
202 idx: usize,
203 entry: &FragExtensionMethod,
204 ) {
205 if member_lists[idx]
206 .extension_methods
207 .iter()
208 .any(|(n, t, lo, hi)| {
209 *n == entry.name
210 && *t == entry.this_type
211 && *lo == entry.arity_min
212 && *hi == entry.arity_max
213 })
214 {
215 return;
216 }
217 member_lists[idx].extension_methods.push((
218 entry.name.clone(),
219 entry.this_type.clone(),
220 entry.arity_min,
221 entry.arity_max,
222 ));
223 extension_index
224 .entry(format!("{} {}", entry.name, entry.this_type))
225 .or_default()
226 .push(ExtCandidate {
227 def_idx: idx,
228 entry: entry.clone(),
229 });
230 }
231
232 for (file, frag) in fragments_by_file {
233 for d in &frag.defs {
234 let def_key = (d.id.clone(), d.type_params.len());
235 match qualified_name_and_arity_to_def.get(&def_key) {
236 None => {
237 let idx = defs.len();
238 defs.push(Def {
239 id: d.id.clone(),
240 name: d.name.clone(),
241 namespace: d.namespace.clone(),
242 kind: d.kind.clone(),
243 file: file.clone(),
244 line: d.line,
245 methods: d.methods.clone(),
246 test_methods: d.test_methods.clone(),
247 also_in: Vec::new(),
248 end_line: d.end_line,
249 });
250 member_lists.push(MemberLists {
251 properties: d.properties.clone(),
252 fields: d.fields.clone(),
253 extension_methods: Vec::new(),
254 bases: d.bases.clone(),
255 type_params: d.type_params.clone(),
256 base_generic_args: d
257 .base_generic_args
258 .iter()
259 .map(|(k, v)| (k.clone(), v.clone()))
260 .collect(),
261 method_returns: d.method_returns.clone(),
262 property_types: d.property_types.clone(),
263 field_types: d.field_types.clone(),
264 property_type_files: keys_mapped_to_file(&d.property_types, file),
265 field_type_files: keys_mapped_to_file(&d.field_types, file),
266 method_return_args: d.method_return_args.clone(),
267 non_public_methods: d.non_public_methods.clone(),
268 method_arities: d.method_arities.clone(),
269 method_params: {
270 let mut m: HashMap<String, Vec<MethodOverloadParams>> = HashMap::new();
271 for (name, overloads) in d.method_params.iter() {
272 m.insert(
273 name.clone(),
274 overloads
275 .iter()
276 .map(|params| MethodOverloadParams {
277 params: params.clone(),
278 file: file.clone(),
279 })
280 .collect(),
281 );
282 }
283 m
284 },
285 });
286 for e in &d.extension_methods {
287 add_extension_method(&mut member_lists, &mut extension_index, idx, e);
288 }
289 qualified_name_to_def.entry(d.id.clone()).or_insert(idx);
290 qualified_name_and_arity_to_def.insert(def_key, idx);
291 // Enum members are reachable by exact id (below, via
292 // qualified_name_to_def) but deliberately excluded from
293 // simple_name_to_defs -- see module header.
294 if d.kind != "enum-member" {
295 simple_name_to_defs
296 .entry(d.name.clone())
297 .or_default()
298 .push(idx);
299 }
300 }
301 Some(&idx) => {
302 // A partial class contributes its own members to the same
303 // record; first declaring file wins the order, later ones
304 // append what is new.
305 defs[idx].also_in.push(AlsoIn {
306 file: file.clone(),
307 line: d.line,
308 });
309 for m in &d.methods {
310 if !defs[idx].methods.contains(m) {
311 defs[idx].methods.push(m.clone());
312 }
313 }
314 // Test-coverage stage -- unioned exactly like `methods`
315 // above it, so a partial test class split across two files
316 // is one def declaring the union of both parts' tests.
317 for t in &d.test_methods {
318 if !defs[idx].test_methods.contains(t) {
319 defs[idx].test_methods.push(t.clone());
320 }
321 }
322 for p in &d.properties {
323 if !member_lists[idx].properties.contains(p) {
324 member_lists[idx].properties.push(p.clone());
325 }
326 }
327 for f in &d.fields {
328 if !member_lists[idx].fields.contains(f) {
329 member_lists[idx].fields.push(f.clone());
330 }
331 }
332 for m in &d.non_public_methods {
333 if !member_lists[idx].non_public_methods.contains(m) {
334 member_lists[idx].non_public_methods.push(m.clone());
335 }
336 }
337 for e in &d.extension_methods {
338 add_extension_method(&mut member_lists, &mut extension_index, idx, e);
339 }
340 for b in &d.bases {
341 if !member_lists[idx].bases.contains(b) {
342 member_lists[idx].bases.push(b.clone());
343 }
344 }
345 // A partial class's later parts contribute the member types
346 // the first part did not declare; a name the first part
347 // already answered keeps its answer, the same
348 // first-declaration-wins rule the extractor applies within
349 // one declaration.
350 for (name, returns) in d.method_returns.iter() {
351 if member_lists[idx].method_returns.get(name).is_none() {
352 member_lists[idx]
353 .method_returns
354 .insert(name.clone(), returns.clone());
355 }
356 }
357 // The declaring FILE is recorded alongside each fact
358 // it accepts -- see `MemberLists::property_type_files`:
359 // a type name is only meaningful under the usings of
360 // the file that wrote it, and for a partial class that
361 // is not always the def's own first-declaring file.
362 for (name, fact) in d.property_types.iter() {
363 if member_lists[idx].property_types.get(name).is_none() {
364 member_lists[idx]
365 .property_types
366 .insert(name.clone(), fact.clone());
367 member_lists[idx]
368 .property_type_files
369 .insert(name.clone(), file.clone());
370 }
371 }
372 for (name, fact) in d.field_types.iter() {
373 if member_lists[idx].field_types.get(name).is_none() {
374 member_lists[idx]
375 .field_types
376 .insert(name.clone(), fact.clone());
377 member_lists[idx]
378 .field_type_files
379 .insert(name.clone(), file.clone());
380 }
381 }
382 for (name, args) in d.method_return_args.iter() {
383 if member_lists[idx].method_return_args.get(name).is_none() {
384 member_lists[idx]
385 .method_return_args
386 .insert(name.clone(), args.clone());
387 }
388 }
389 // A UNION per NAME, unlike `method_returns` above: a
390 // partial class's parts declare OVERLOADS of one name,
391 // not competing answers for it, so `void Run()` in one
392 // file and `void Run(int)` in another must both be
393 // admitted -- first-declaration-wins here would have
394 // hidden the sibling file's overload and made
395 // `method_arity_admits` refuse a call the type really
396 // accepts. Ranges already recorded are not repeated, so
397 // a part re-declaring an overload the merged set holds
398 // leaves the set unchanged.
399 for (name, ranges) in d.method_arities.iter() {
400 let mut merged = member_lists[idx]
401 .method_arities
402 .get(name)
403 .cloned()
404 .unwrap_or_default();
405 for range in ranges {
406 if !merged.contains(range) {
407 merged.push(*range);
408 }
409 }
410 member_lists[idx]
411 .method_arities
412 .insert(name.clone(), merged);
413 }
414 // A UNION per NAME, same as `method_arities` just above:
415 // every declaring part's overloads are admitted, an
416 // overload whose `params` list a merged entry already
417 // holds skipped -- first file wins for that duplicate.
418 for (name, overloads) in d.method_params.iter() {
419 let merged = member_lists[idx]
420 .method_params
421 .entry(name.clone())
422 .or_default();
423 for params in overloads {
424 if !merged.iter().any(|o| &o.params == params) {
425 merged.push(MethodOverloadParams {
426 params: params.clone(),
427 file: file.clone(),
428 });
429 }
430 }
431 }
432 }
433 }
434 }
435 }
436
437 // See `DefIndex::member_name_to_defs`. A second pass over the ALREADY-MERGED
438 // def records, so a partial class spread over three files lands in each of
439 // its member-name buckets exactly once.
440 let mut member_name_to_defs: HashMap<String, Vec<usize>> = HashMap::new();
441 for idx in 0..defs.len() {
442 let mut names: Vec<&str> = Vec::new();
443 let mut seen: HashSet<&str> = HashSet::new();
444 for m in &defs[idx].methods {
445 if seen.insert(m.as_str()) {
446 names.push(m.as_str());
447 }
448 }
449 for p in &member_lists[idx].properties {
450 if seen.insert(p.as_str()) {
451 names.push(p.as_str());
452 }
453 }
454 for f in &member_lists[idx].fields {
455 if seen.insert(f.as_str()) {
456 names.push(f.as_str());
457 }
458 }
459 for (name, ..) in &member_lists[idx].extension_methods {
460 if seen.insert(name.as_str()) {
461 names.push(name.as_str());
462 }
463 }
464 for n in names {
465 member_name_to_defs
466 .entry(n.to_string())
467 .or_default()
468 .push(idx);
469 }
470 }
471
472 DefIndex {
473 defs,
474 member_lists,
475 qualified_name_to_def,
476 qualified_name_and_arity_to_def,
477 simple_name_to_defs,
478 extension_index,
479 member_name_to_defs,
480 }
481}
482
483// A synthetic bare type reference, for re-running the ladder on a name the
484// RESOLVER derived rather than one it read off a ref: a base type, a receiver's
485// recorded type, a property's declared type, a callee's owner. Every field
486// except `name`/`outer_types` is what a bare, non-generic, non-member reference
487// carries, so a probe can never re-enter a member tier by accident.
488pub(super) fn name_probe(name: String, namespace: &str, outer_types: Vec<String>) -> FragRef {
489 FragRef {
490 kind: "uses-type".to_string(),
491 name,
492 qualified: None,
493 member: None,
494 line: 0,
495 namespace: Some(namespace.to_string()),
496 type_arg_count: None,
497 generic: false,
498 receiver_type: None,
499 arg_count: None,
500 receiver_args: None,
501 outer_types,
502 args: None,
503 receiver_property_owner: None,
504 receiver_call_owner: None,
505 receiver_call_member: None,
506 receiver_base: false,
507 receiver_awaited: false,
508 receiver_local: false,
509 receiver_lambda: None,
510 }
511}