resolve_lang/program.rs
1//! The drivers: [`Program`] (several units resolved against each other),
2//! [`Resolver`] (one unit), and their result, [`Resolution`].
3
4use alloc::vec::Vec;
5
6use hir_lang::{
7 DefId, Hir, HirError, ItemId, ItemKind, Name, NodeRef, Pat, PatId, PathId, Res, UnitId, Vis,
8};
9use intern_lang::Lookup;
10
11use crate::{
12 collect::{Bases, collect},
13 diag::{DiagKind, Diagnostic},
14 env::{Env, NoEnv},
15 error::{Budget, ResolveError},
16 imports::resolve_imports,
17 index::{Index, RawRef, Target, UnitInput},
18 members::{Members, finish_deferred},
19 model::{Fold, Model, ScopeKind, Unit, ix},
20 pass::{Pass, UnitOut, entry_gate},
21 policy::{Namespace, Policy},
22 suggest::Suggester,
23};
24
25/// One member of a class's effective member table: its own members and
26/// those its mixins contribute, after `insteadof` and `as` rules.
27///
28/// # Examples
29///
30/// ```
31/// use hir_lang::{Name, Res, Symbol, Vis};
32/// use resolve_lang::{ClassMember, Namespace};
33///
34/// let m = ClassMember {
35/// name: Name::new(Symbol::from_u32(1).unwrap()),
36/// namespace: Namespace::Value,
37/// res: Res::Err,
38/// vis: Vis::Public,
39/// mixin: None,
40/// };
41/// assert!(m.mixin.is_none());
42/// ```
43#[derive(Clone, Copy, Debug, PartialEq, Eq)]
44pub struct ClassMember {
45 /// The member's name in this class (an alias's new name).
46 pub name: Name,
47 /// The table it lives in (after merging).
48 pub namespace: Namespace,
49 /// What it resolves to (for a mixin member, the mixin's item).
50 pub res: Res,
51 /// Its visibility in this class (a rule may change it).
52 pub vis: Vis,
53 /// The mixin it came from, or `None` for the class's own member.
54 pub mixin: Option<DefId>,
55}
56
57/// One resolved unit.
58///
59/// # Examples
60///
61/// ```
62/// use hir_lang::Builder;
63/// use intern_lang::Interner;
64///
65/// let mut b = Builder::new();
66/// let root = b.module(None, &[]);
67/// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
68/// assert_eq!(res.units().len(), 1);
69/// assert!(res.units()[0].hir().validate().is_ok());
70/// # Ok::<(), Box<dyn std::error::Error>>(())
71/// ```
72#[derive(Clone, Debug)]
73pub struct ResolvedUnit {
74 name: Option<Name>,
75 hir: Hir,
76 members: Vec<(ItemId, Vec<ClassMember>)>,
77 ident_matches: Vec<PatId>,
78}
79
80impl ResolvedUnit {
81 /// The unit's id.
82 ///
83 /// # Examples
84 ///
85 /// ```
86 /// use hir_lang::{Builder, UnitId};
87 /// use intern_lang::Interner;
88 ///
89 /// let mut b = Builder::for_unit(UnitId::new(4));
90 /// let root = b.module(None, &[]);
91 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
92 /// assert_eq!(res.units()[0].id(), UnitId::new(4));
93 /// # Ok::<(), Box<dyn std::error::Error>>(())
94 /// ```
95 #[must_use]
96 pub fn id(&self) -> UnitId {
97 self.hir.unit()
98 }
99
100 /// The root name other units reached this unit by, if it had one.
101 ///
102 /// # Examples
103 ///
104 /// ```
105 /// use hir_lang::Builder;
106 /// use intern_lang::Interner;
107 ///
108 /// let mut b = Builder::new();
109 /// let root = b.module(None, &[]);
110 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
111 /// assert!(res.units()[0].name().is_none());
112 /// # Ok::<(), Box<dyn std::error::Error>>(())
113 /// ```
114 #[must_use]
115 pub fn name(&self) -> Option<Name> {
116 self.name
117 }
118
119 /// The resolved HIR: every resolvable path's slot is filled through
120 /// hir-lang's checked setters, so it is still a valid `Hir`.
121 ///
122 /// # Examples
123 ///
124 /// ```
125 /// use hir_lang::Builder;
126 /// use intern_lang::Interner;
127 ///
128 /// let mut b = Builder::new();
129 /// let root = b.module(None, &[]);
130 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
131 /// assert_eq!(res.units()[0].hir().root(), root);
132 /// # Ok::<(), Box<dyn std::error::Error>>(())
133 /// ```
134 #[must_use]
135 pub fn hir(&self) -> &Hir {
136 &self.hir
137 }
138
139 /// Takes the resolved HIR.
140 ///
141 /// # Examples
142 ///
143 /// ```
144 /// use hir_lang::Builder;
145 /// use intern_lang::Interner;
146 ///
147 /// let mut b = Builder::new();
148 /// let root = b.module(None, &[]);
149 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
150 /// let (units, _, _) = res.into_parts();
151 /// let hir = units.into_iter().next().unwrap().into_hir();
152 /// assert!(hir.validate().is_ok());
153 /// # Ok::<(), Box<dyn std::error::Error>>(())
154 /// ```
155 #[must_use]
156 pub fn into_hir(self) -> Hir {
157 self.hir
158 }
159
160 /// The effective members of a class or interface item (its own members
161 /// plus what its mixins contribute), sorted by namespace, then by name
162 /// (symbol order, not spelling).
163 /// `None` for other items.
164 ///
165 /// # Examples
166 ///
167 /// ```
168 /// use hir_lang::{Builder, ClassDef, Item, ItemKind, Name};
169 /// use intern_lang::Interner;
170 ///
171 /// let mut names = Interner::new();
172 /// let mut b = Builder::new();
173 /// let body = b.block(&[], None);
174 /// let m = b.func(Name::new(names.intern("m")), &[], body);
175 /// let items = b.list(&[m]);
176 /// let class = b.item(Item::new(Some(Name::new(names.intern("C"))), ItemKind::Class(ClassDef { items, ..ClassDef::default() })));
177 /// let root = b.module(None, &[class]);
178 /// let res = resolve_lang::resolve(b.finish(root)?, &names)?;
179 /// assert_eq!(res.units()[0].members(class).map(<[_]>::len), Some(1));
180 /// # Ok::<(), Box<dyn std::error::Error>>(())
181 /// ```
182 #[must_use]
183 pub fn members(&self, class: ItemId) -> Option<&[ClassMember]> {
184 let i = self
185 .members
186 .binary_search_by_key(&class, |(c, _)| *c)
187 .ok()?;
188 self.members.get(i).map(|(_, m)| m.as_slice())
189 }
190
191 /// For a `Pat::Ident` pattern: `Some(true)` if it binds its binder,
192 /// `Some(false)` if its path named a constant, unit variant, or unit
193 /// record (it matches that value). `None` for other patterns.
194 ///
195 /// # Examples
196 ///
197 /// ```
198 /// use hir_lang::{Builder, PatId};
199 /// use intern_lang::Interner;
200 ///
201 /// let mut b = Builder::new();
202 /// let root = b.module(None, &[]);
203 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
204 /// assert_eq!(res.units()[0].ident_binds(PatId::from_index(0).unwrap()), None);
205 /// # Ok::<(), Box<dyn std::error::Error>>(())
206 /// ```
207 #[must_use]
208 pub fn ident_binds(&self, pat: PatId) -> Option<bool> {
209 matches!(self.hir.get_pat(pat), Some(Pat::Ident { .. }))
210 .then(|| self.ident_matches.binary_search(&pat).is_err())
211 }
212}
213
214/// The result of resolving a program: the resolved units, every diagnostic,
215/// and the definition/reference index.
216///
217/// # Examples
218///
219/// ```
220/// use hir_lang::{Builder, Name};
221/// use intern_lang::Interner;
222///
223/// let mut names = Interner::new();
224/// let mut b = Builder::new();
225/// let missing = b.name_expr(Name::new(names.intern("missing")));
226/// let body = b.block(&[], Some(missing));
227/// let f = b.func(Name::new(names.intern("f")), &[], body);
228/// let root = b.module(None, &[f]);
229/// let res = resolve_lang::resolve(b.finish(root)?, &names)?;
230/// assert!(!res.is_clean());
231/// assert_eq!(res.diagnostics()[0].message(&names), "cannot find value `missing` in this scope");
232/// # Ok::<(), Box<dyn std::error::Error>>(())
233/// ```
234#[derive(Clone, Debug)]
235pub struct Resolution {
236 units: Vec<ResolvedUnit>,
237 diagnostics: Vec<Diagnostic>,
238 index: Index,
239}
240
241impl Resolution {
242 /// The resolved units, in the order they were added.
243 ///
244 /// # Examples
245 ///
246 /// ```
247 /// use hir_lang::Builder;
248 /// use intern_lang::Interner;
249 ///
250 /// let mut b = Builder::new();
251 /// let root = b.module(None, &[]);
252 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
253 /// assert_eq!(res.units().len(), 1);
254 /// # Ok::<(), Box<dyn std::error::Error>>(())
255 /// ```
256 #[must_use]
257 pub fn units(&self) -> &[ResolvedUnit] {
258 &self.units
259 }
260
261 /// One unit by id.
262 ///
263 /// # Examples
264 ///
265 /// ```
266 /// use hir_lang::{Builder, UnitId};
267 /// use intern_lang::Interner;
268 ///
269 /// let mut b = Builder::for_unit(UnitId::new(2));
270 /// let root = b.module(None, &[]);
271 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
272 /// assert!(res.unit(UnitId::new(2)).is_some());
273 /// assert!(res.unit(UnitId::new(3)).is_none());
274 /// # Ok::<(), Box<dyn std::error::Error>>(())
275 /// ```
276 #[must_use]
277 pub fn unit(&self, id: UnitId) -> Option<&ResolvedUnit> {
278 self.units.iter().find(|u| u.id() == id)
279 }
280
281 /// The resolved HIR of one unit.
282 ///
283 /// # Examples
284 ///
285 /// ```
286 /// use hir_lang::{Builder, UnitId};
287 /// use intern_lang::Interner;
288 ///
289 /// let mut b = Builder::new();
290 /// let root = b.module(None, &[]);
291 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
292 /// assert!(res.hir(UnitId::new(0)).is_some());
293 /// # Ok::<(), Box<dyn std::error::Error>>(())
294 /// ```
295 #[must_use]
296 pub fn hir(&self, id: UnitId) -> Option<&Hir> {
297 self.unit(id).map(ResolvedUnit::hir)
298 }
299
300 /// Every diagnostic, sorted by unit, then position, then discovery.
301 ///
302 /// # Examples
303 ///
304 /// ```
305 /// use hir_lang::Builder;
306 /// use intern_lang::Interner;
307 ///
308 /// let mut b = Builder::new();
309 /// let root = b.module(None, &[]);
310 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
311 /// assert!(res.diagnostics().is_empty());
312 /// # Ok::<(), Box<dyn std::error::Error>>(())
313 /// ```
314 #[must_use]
315 pub fn diagnostics(&self) -> &[Diagnostic] {
316 &self.diagnostics
317 }
318
319 /// Whether resolution found nothing to report.
320 ///
321 /// # Examples
322 ///
323 /// ```
324 /// use hir_lang::Builder;
325 /// use intern_lang::Interner;
326 ///
327 /// let mut b = Builder::new();
328 /// let root = b.module(None, &[]);
329 /// assert!(resolve_lang::resolve(b.finish(root)?, &Interner::new())?.is_clean());
330 /// # Ok::<(), Box<dyn std::error::Error>>(())
331 /// ```
332 #[must_use]
333 pub fn is_clean(&self) -> bool {
334 self.diagnostics.is_empty()
335 }
336
337 /// The definition/reference index.
338 ///
339 /// # Examples
340 ///
341 /// ```
342 /// use hir_lang::Builder;
343 /// use intern_lang::Interner;
344 ///
345 /// let mut b = Builder::new();
346 /// let root = b.module(None, &[]);
347 /// let res = resolve_lang::resolve(b.finish(root)?, &Interner::new())?;
348 /// assert!(res.index().references_all().is_empty());
349 /// # Ok::<(), Box<dyn std::error::Error>>(())
350 /// ```
351 #[must_use]
352 pub fn index(&self) -> &Index {
353 &self.index
354 }
355
356 /// Takes the parts.
357 ///
358 /// # Examples
359 ///
360 /// ```
361 /// use hir_lang::Builder;
362 /// use intern_lang::Interner;
363 ///
364 /// let mut b = Builder::new();
365 /// let root = b.module(None, &[]);
366 /// let (units, diags, _index) = resolve_lang::resolve(b.finish(root)?, &Interner::new())?.into_parts();
367 /// assert_eq!((units.len(), diags.len()), (1, 0));
368 /// # Ok::<(), Box<dyn std::error::Error>>(())
369 /// ```
370 #[must_use]
371 pub fn into_parts(self) -> (Vec<ResolvedUnit>, Vec<Diagnostic>, Index) {
372 (self.units, self.diagnostics, self.index)
373 }
374}
375
376/// Resolves one unit (Tier 2): a policy, an environment, a budget.
377///
378/// # Examples
379///
380/// ```
381/// use hir_lang::{Builder, Name, Prim, Res};
382/// use intern_lang::Interner;
383/// use resolve_lang::{DefKind, Export, MapEnv, Namespace, Policy, Resolver};
384///
385/// let mut names = Interner::new();
386/// let int = Name::new(names.intern("int"));
387/// let env = MapEnv::new().with_prelude(int, Namespace::Type, Export::new(Res::Prim(Prim::I64), DefKind::Prim));
388///
389/// // const N: int = 1
390/// let mut b = Builder::new();
391/// let ty_path = b.name_path(int, hir_lang::Ns::Type);
392/// let ty = b.ty(hir_lang::Ty::Path(ty_path));
393/// let one = b.int(1);
394/// let n = b.item(hir_lang::Item::new(Some(Name::new(names.intern("N"))), hir_lang::ItemKind::Const { ty: Some(ty), value: Some(one) }));
395/// let root = b.module(None, &[n]);
396///
397/// let res = Resolver::new(Policy::kraken()).with_env(&env).resolve(b.finish(root)?, &names)?;
398/// assert!(res.is_clean());
399/// assert_eq!(res.units()[0].hir().path(ty_path).res, Res::Prim(Prim::I64));
400/// # Ok::<(), Box<dyn std::error::Error>>(())
401/// ```
402#[derive(Clone, Copy)]
403pub struct Resolver<'e> {
404 policy: Policy,
405 env: &'e dyn Env,
406 budget: Budget,
407}
408
409impl core::fmt::Debug for Resolver<'_> {
410 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
411 f.debug_struct("Resolver")
412 .field("policy", &self.policy)
413 .field("budget", &self.budget)
414 .finish_non_exhaustive()
415 }
416}
417
418impl Resolver<'static> {
419 /// A resolver with `policy`, no environment, and the default budget.
420 ///
421 /// # Examples
422 ///
423 /// ```
424 /// use resolve_lang::{Policy, Resolver};
425 ///
426 /// let _r = Resolver::new(Policy::python());
427 /// ```
428 #[must_use]
429 pub fn new(policy: Policy) -> Self {
430 Self {
431 policy,
432 env: &NoEnv,
433 budget: Budget::default(),
434 }
435 }
436}
437
438impl Resolver<'_> {
439 /// Uses `env` for names outside the unit.
440 ///
441 /// # Examples
442 ///
443 /// ```
444 /// use resolve_lang::{MapEnv, Policy, Resolver};
445 ///
446 /// let env = MapEnv::new();
447 /// let _r = Resolver::new(Policy::new()).with_env(&env);
448 /// ```
449 #[must_use]
450 pub fn with_env(self, env: &dyn Env) -> Resolver<'_> {
451 Resolver {
452 policy: self.policy,
453 env,
454 budget: self.budget,
455 }
456 }
457
458 /// Sets the budget.
459 ///
460 /// # Examples
461 ///
462 /// ```
463 /// use resolve_lang::{Budget, Policy, Resolver};
464 ///
465 /// let _r = Resolver::new(Policy::new()).with_budget(Budget::unlimited());
466 /// ```
467 #[must_use]
468 pub fn with_budget(mut self, budget: Budget) -> Self {
469 self.budget = budget;
470 self
471 }
472
473 /// Resolves `hir`.
474 ///
475 /// # Errors
476 ///
477 /// [`ResolveError::BudgetExceeded`] if the unit exceeds the budget.
478 ///
479 /// # Examples
480 ///
481 /// ```
482 /// use hir_lang::Builder;
483 /// use intern_lang::Interner;
484 /// use resolve_lang::{Policy, Resolver};
485 ///
486 /// let mut b = Builder::new();
487 /// let root = b.module(None, &[]);
488 /// let res = Resolver::new(Policy::php()).resolve(b.finish(root)?, &Interner::new())?;
489 /// assert!(res.is_clean());
490 /// # Ok::<(), Box<dyn std::error::Error>>(())
491 /// ```
492 pub fn resolve<L: Lookup>(self, hir: Hir, names: &L) -> Result<Resolution, ResolveError> {
493 let mut program = Program::new(self.policy)
494 .with_env(self.env)
495 .with_budget(self.budget);
496 program.add_unit(None, hir);
497 program.resolve(names)
498 }
499}
500
501/// Several units resolved against each other (Tier 3): the in-memory
502/// multi-unit driver. Each unit may be given a root name, by which every
503/// unit (itself included) can reach its root module as a path's first
504/// segment (`util::helper`, `import util`). Imports may form cycles across
505/// units.
506///
507/// # Examples
508///
509/// ```
510/// use hir_lang::{Builder, Def, Expr, FnDef, Item, ItemKind, Name, Ns, Path, Res, Segment, UnitId, Vis};
511/// use intern_lang::Interner;
512/// use resolve_lang::{Policy, Program};
513///
514/// let mut names = Interner::new();
515/// let (util, helper) = (Name::new(names.intern("util")), Name::new(names.intern("helper")));
516///
517/// // Unit 1, reachable as `util`: pub fn helper() {}
518/// let mut b = Builder::for_unit(UnitId::new(1));
519/// let body = b.block(&[], None);
520/// let f = b.item(Item::new(Some(helper), ItemKind::Fn(FnDef { body: Some(body), ..FnDef::default() })).with_vis(Vis::Public));
521/// let root = b.module(None, &[f]);
522/// let util_hir = b.finish(root)?;
523///
524/// // Unit 2: fn main() { util::helper }
525/// let mut b = Builder::for_unit(UnitId::new(2));
526/// let segs = [Segment::new(util, b.origin()), Segment::new(helper, b.origin())];
527/// let segs = b.list(&segs);
528/// let path = b.path(Path::new(segs, Ns::Value));
529/// let call = b.expr(Expr::Path(path));
530/// let body = b.block(&[], Some(call));
531/// let main = b.func(Name::new(names.intern("main")), &[], body);
532/// let root = b.module(None, &[main]);
533/// let app_hir = b.finish(root)?;
534///
535/// let mut program = Program::new(Policy::kraken());
536/// program.add_unit(Some(util), util_hir);
537/// program.add_unit(None, app_hir);
538/// let res = program.resolve(&names)?;
539/// assert!(res.is_clean());
540/// let app = res.hir(UnitId::new(2)).unwrap();
541/// let Res::Def(d) = app.path(path).res else { panic!("unresolved") };
542/// assert_eq!((d.unit(), d.def()), (UnitId::new(1), Def::Item(f)));
543/// # Ok::<(), Box<dyn std::error::Error>>(())
544/// ```
545pub struct Program<'e> {
546 policy: Policy,
547 env: &'e dyn Env,
548 budget: Budget,
549 units: Vec<(Option<Name>, u32, Hir)>,
550}
551
552impl core::fmt::Debug for Program<'_> {
553 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
554 f.debug_struct("Program")
555 .field("policy", &self.policy)
556 .field("budget", &self.budget)
557 .field("units", &self.units.len())
558 .finish_non_exhaustive()
559 }
560}
561
562impl Program<'static> {
563 /// An empty program with `policy`, no environment, and the default
564 /// budget.
565 ///
566 /// # Examples
567 ///
568 /// ```
569 /// use resolve_lang::{Policy, Program};
570 ///
571 /// let p = Program::new(Policy::kraken());
572 /// assert_eq!(p.len(), 0);
573 /// ```
574 #[must_use]
575 pub fn new(policy: Policy) -> Self {
576 Self {
577 policy,
578 env: &NoEnv,
579 budget: Budget::default(),
580 units: Vec::new(),
581 }
582 }
583}
584
585impl Program<'_> {
586 /// Uses `env` for names outside the program.
587 ///
588 /// # Examples
589 ///
590 /// ```
591 /// use resolve_lang::{MapEnv, Policy, Program};
592 ///
593 /// let env = MapEnv::new();
594 /// let _p = Program::new(Policy::new()).with_env(&env);
595 /// ```
596 #[must_use]
597 pub fn with_env(self, env: &dyn Env) -> Program<'_> {
598 Program {
599 policy: self.policy,
600 env,
601 budget: self.budget,
602 units: self.units,
603 }
604 }
605
606 /// Sets the budget.
607 ///
608 /// # Examples
609 ///
610 /// ```
611 /// use resolve_lang::{Budget, Policy, Program};
612 ///
613 /// let _p = Program::new(Policy::new()).with_budget(Budget::default().with_glob_bindings(10));
614 /// ```
615 #[must_use]
616 pub fn with_budget(mut self, budget: Budget) -> Self {
617 self.budget = budget;
618 self
619 }
620
621 /// Adds a unit in package 0, reachable by `name` (if given) from every
622 /// unit.
623 ///
624 /// # Examples
625 ///
626 /// ```
627 /// use hir_lang::Builder;
628 /// use resolve_lang::{Policy, Program};
629 ///
630 /// let mut b = Builder::new();
631 /// let root = b.module(None, &[]);
632 /// let mut p = Program::new(Policy::new());
633 /// p.add_unit(None, b.finish(root)?);
634 /// assert_eq!(p.len(), 1);
635 /// # Ok::<(), hir_lang::HirError>(())
636 /// ```
637 pub fn add_unit(&mut self, name: Option<Name>, hir: Hir) {
638 self.units.push((name, 0, hir));
639 }
640
641 /// Adds a unit to a package: `Vis::Package` items are visible across
642 /// units of the same package only.
643 ///
644 /// # Examples
645 ///
646 /// ```
647 /// use hir_lang::Builder;
648 /// use resolve_lang::{Policy, Program};
649 ///
650 /// let mut b = Builder::new();
651 /// let root = b.module(None, &[]);
652 /// let mut p = Program::new(Policy::new());
653 /// p.add_unit_in(7, None, b.finish(root)?);
654 /// assert!(!p.is_empty());
655 /// # Ok::<(), hir_lang::HirError>(())
656 /// ```
657 pub fn add_unit_in(&mut self, package: u32, name: Option<Name>, hir: Hir) {
658 self.units.push((name, package, hir));
659 }
660
661 /// The number of units added.
662 ///
663 /// # Examples
664 ///
665 /// ```
666 /// use resolve_lang::{Policy, Program};
667 ///
668 /// assert_eq!(Program::new(Policy::new()).len(), 0);
669 /// ```
670 #[must_use]
671 pub fn len(&self) -> usize {
672 self.units.len()
673 }
674
675 /// Whether no unit was added.
676 ///
677 /// # Examples
678 ///
679 /// ```
680 /// use resolve_lang::{Policy, Program};
681 ///
682 /// assert!(Program::new(Policy::new()).is_empty());
683 /// ```
684 #[must_use]
685 pub fn is_empty(&self) -> bool {
686 self.units.is_empty()
687 }
688
689 /// Resolves every unit.
690 ///
691 /// # Errors
692 ///
693 /// - [`ResolveError::DuplicateUnit`] if two units share a `UnitId`.
694 /// - [`ResolveError::BudgetExceeded`] if the program exceeds the budget.
695 ///
696 /// # Examples
697 ///
698 /// ```
699 /// use hir_lang::{Builder, UnitId};
700 /// use intern_lang::Interner;
701 /// use resolve_lang::{Policy, Program, ResolveError};
702 ///
703 /// let mut p = Program::new(Policy::new());
704 /// for _ in 0..2 {
705 /// let mut b = Builder::for_unit(UnitId::new(1));
706 /// let root = b.module(None, &[]);
707 /// p.add_unit(None, b.finish(root)?);
708 /// }
709 /// assert_eq!(p.resolve(&Interner::new()).unwrap_err(), ResolveError::DuplicateUnit { unit: UnitId::new(1) });
710 /// # Ok::<(), hir_lang::HirError>(())
711 /// ```
712 pub fn resolve<L: Lookup>(self, names: &L) -> Result<Resolution, ResolveError> {
713 let mut unit_ix: Vec<(UnitId, u32)> = self
714 .units
715 .iter()
716 .enumerate()
717 .map(|(i, (_, _, h))| (h.unit(), ix(i)))
718 .collect();
719 unit_ix.sort();
720 if let Some(w) = unit_ix
721 .windows(2)
722 .find(|w| w.first().map(|x| x.0) == w.get(1).map(|x| x.0))
723 {
724 if let Some(&(unit, _)) = w.first() {
725 return Err(ResolveError::DuplicateUnit { unit });
726 }
727 }
728 let mut m = Model {
729 policy: self.policy,
730 fold: Fold::build(&self.policy, names),
731 env: self.env,
732 units: Vec::with_capacity(self.units.len()),
733 unit_ix,
734 roots: Vec::new(),
735 scopes: Vec::new(),
736 bindings: Vec::new(),
737 imports: Vec::new(),
738 sums: Vec::new(),
739 diags: Vec::new(),
740 };
741 // Phase 1: collect.
742 for (u, (name, package, hir)) in self.units.into_iter().enumerate() {
743 let bases = Bases {
744 unit: ix(u),
745 scope: ix(m.scopes.len()),
746 binding: ix(m.bindings.len()),
747 import: ix(m.imports.len()),
748 sum: ix(m.sums.len()),
749 };
750 let c = collect(&hir, &m.policy, &m.fold, bases);
751 m.scopes.extend(c.scopes);
752 m.bindings.extend(c.bindings);
753 m.imports.extend(c.imports);
754 m.sums.extend(c.sums);
755 if let Some(name) = name {
756 let key = m.fold.key_ns(&m.policy, Namespace::Module, name);
757 m.roots.push((key, ix(u)));
758 }
759 m.units.push(Unit {
760 id: hir.unit(),
761 name,
762 package,
763 hir,
764 root_scope: c.root_scope,
765 item_scope: c.item_scope,
766 block_scope: c.block_scope,
767 sum_table: c.sum_table,
768 import_of: c.import_of,
769 after_decl: Vec::new(),
770 });
771 for (kind, span, node) in c.diags {
772 m.report(ix(u), kind, span, Some(node));
773 }
774 }
775 // The first unit to claim a root name keeps it.
776 m.roots.sort_by_key(|(n, u)| (*n, *u));
777 m.roots.dedup_by_key(|(n, _)| *n);
778 let mut sugg = Suggester::new(self.budget.suggestion_cells());
779 // Phase 2: imports.
780 resolve_imports(&mut m, names, &mut sugg, self.budget.glob_bindings())?;
781 // Declare-before-use entries, by gating item.
782 let mut gated: Vec<Vec<(u32, u32, u32)>> = m.units.iter().map(|_| Vec::new()).collect();
783 for (s, scope) in m.scopes.iter().enumerate() {
784 for (e, entry) in scope.table.iter().enumerate() {
785 if let Some(item) = entry_gate(&m, entry.state) {
786 if let Some(list) = gated.get_mut(scope.unit as usize) {
787 list.push((ix(item.index()), ix(s), ix(e)));
788 }
789 }
790 }
791 }
792 for (unit, mut list) in m.units.iter_mut().zip(gated) {
793 list.sort_unstable();
794 unit.after_decl = list;
795 }
796 // Phase 3: the walk.
797 let mut outs: Vec<UnitOut> = Vec::with_capacity(m.units.len());
798 for u in 0..m.units.len() {
799 if let Some(pass) = Pass::new(&m, names, &mut sugg, ix(u)) {
800 outs.push(pass.run());
801 }
802 }
803 // Phase 4: members, mixins, deferred paths.
804 let mut members = Members::build(&mut m, &outs, self.budget.member_steps())?;
805 finish_deferred(&m, &mut members, &mut outs)?;
806 // Apply plans to the HIR.
807 for (unit, out) in m.units.iter_mut().zip(outs.iter_mut()) {
808 apply(unit, out);
809 }
810 Ok(assemble(m, outs, &members))
811 }
812}
813
814/// Writes the planned resolutions through hir-lang's checked setters.
815fn apply(unit: &mut Unit, out: &mut UnitOut) {
816 let id = unit.id;
817 for i in 0..out.plan.len() {
818 let Some((res, unresolved)) = out.plan.get(i).copied().flatten() else {
819 continue;
820 };
821 let Some(p) = PathId::from_index(i) else {
822 continue;
823 };
824 let Err(error) = unit.hir.resolve_partial(p, res, unresolved) else {
825 continue;
826 };
827 // Keep the HIR valid: an error resolution is accepted everywhere.
828 let _always_ok = unit.hir.resolve(p, Res::Err);
829 if let Some(slot) = out.plan.get_mut(i) {
830 *slot = Some((Res::Err, 0));
831 }
832 let span = unit
833 .hir
834 .list(unit.hir.path(p).segments)
835 .first()
836 .map_or(unit.hir.origin(NodeRef::Path(p)).span, |s| s.origin.span);
837 let kind = match error {
838 HirError::OutOfScope { binder, .. } | HirError::NotCapturable { binder, .. } => {
839 let name = unit.hir.binder(binder).map(|b| b.name);
840 match name {
841 Some(name) => DiagKind::CannotCapture { name, binder },
842 None => DiagKind::Rejected { error },
843 }
844 }
845 _ => DiagKind::Rejected { error },
846 };
847 out.diag(id, p, kind, span, false);
848 }
849}
850
851/// Builds the result: units, sorted diagnostics, index.
852fn assemble(m: Model<'_>, outs: Vec<UnitOut>, members: &Members) -> Resolution {
853 let mut diagnostics = m.diags.clone();
854 for out in &outs {
855 diagnostics.extend(out.diags.iter().copied());
856 }
857 let order: Vec<UnitId> = m.units.iter().map(|u| u.id).collect();
858 let pos = |id: UnitId| order.iter().position(|u| *u == id).unwrap_or(usize::MAX);
859 diagnostics.sort_by_key(|d| (pos(d.unit), d.span.start(), d.span.end()));
860 // Index input per unit.
861 let mut inputs_refs: Vec<(Vec<RawRef>, Vec<hir_lang::BinderId>, Vec<ItemId>)> = Vec::new();
862 for (u, out) in outs.iter().enumerate() {
863 let Some(unit) = m.units.get(u) else { continue };
864 let mut refs = Vec::with_capacity(out.segs.len());
865 for s in &out.segs {
866 if unit.hir.path(s.path).res == Res::Err {
867 continue;
868 }
869 let Some(target) = target_of(unit, s.res) else {
870 continue;
871 };
872 let via = m
873 .imports
874 .get(s.via as usize)
875 .filter(|imp| is_alias(&m, imp.unit, imp.item))
876 .and_then(|imp| {
877 m.units
878 .get(imp.unit as usize)
879 .map(|x| Target::Import(x.id, imp.item))
880 });
881 refs.push(RawRef {
882 path: s.path,
883 seg: s.seg,
884 target,
885 via,
886 });
887 }
888 let dead: Vec<hir_lang::BinderId> = out
889 .ident_matches
890 .iter()
891 .filter_map(|p| match unit.hir.get_pat(*p) {
892 Some(Pat::Ident { binder, .. }) => Some(*binder),
893 _ => None,
894 })
895 .collect();
896 let aliases: Vec<ItemId> = m
897 .imports
898 .iter()
899 .filter(|imp| imp.unit == ix(u) && is_alias(&m, imp.unit, imp.item))
900 .map(|imp| imp.item)
901 .collect();
902 inputs_refs.push((refs, dead, aliases));
903 }
904 let inputs: Vec<UnitInput<'_>> = m
905 .units
906 .iter()
907 .zip(inputs_refs)
908 .map(|(unit, (refs, dead_binders, mut aliases))| {
909 aliases.sort();
910 UnitInput {
911 hir: &unit.hir,
912 refs,
913 dead_binders,
914 aliases,
915 }
916 })
917 .collect();
918 let index = Index::build(&inputs, &m.fold);
919 drop(inputs);
920 // Class members per unit.
921 let mut class_members: Vec<Vec<(ItemId, Vec<ClassMember>)>> =
922 m.units.iter().map(|_| Vec::new()).collect();
923 for (s, scope) in m.scopes.iter().enumerate() {
924 let ScopeKind::Type(item, _) = scope.kind else {
925 continue;
926 };
927 let list: Vec<ClassMember> = members
928 .tables
929 .get(s)
930 .into_iter()
931 .flatten()
932 .filter_map(|mem| {
933 let b = m.bindings.get(mem.binding as usize)?;
934 let mixin = match mem.from {
935 Some(Res::Def(d)) => Some(d),
936 _ => None,
937 };
938 Some(ClassMember {
939 name: b.name,
940 namespace: Namespace::from_index(mem.ns as usize),
941 res: b.res,
942 vis: b.vis,
943 mixin,
944 })
945 })
946 .collect();
947 if let Some(v) = class_members.get_mut(scope.unit as usize) {
948 v.push((item, list));
949 }
950 }
951 let mut units = Vec::with_capacity(m.units.len());
952 for ((unit, out), mut cm) in m.units.into_iter().zip(outs).zip(class_members) {
953 cm.sort_by_key(|(i, _)| *i);
954 let mut ident_matches = out.ident_matches;
955 ident_matches.sort();
956 ident_matches.dedup();
957 units.push(ResolvedUnit {
958 name: unit.name,
959 hir: unit.hir,
960 members: cm,
961 ident_matches,
962 });
963 }
964 Resolution {
965 units,
966 diagnostics,
967 index,
968 }
969}
970
971/// Whether an import item renames what it imports.
972fn is_alias(m: &Model<'_>, u: u32, item: ItemId) -> bool {
973 let Some(unit) = m.units.get(u as usize) else {
974 return false;
975 };
976 let it = unit.hir.item(item);
977 let ItemKind::Import { path, glob: false } = it.kind else {
978 return false;
979 };
980 let last = unit
981 .hir
982 .list(unit.hir.path(path).segments)
983 .last()
984 .map(|s| s.name);
985 it.name.is_some() && it.name != last
986}
987
988/// The index target of a resolution in `unit`.
989fn target_of(unit: &Unit, res: Res) -> Option<Target> {
990 match res {
991 Res::Def(d) => Some(Target::Def(d)),
992 Res::Local(b) => Some(Target::Local(unit.id, b)),
993 Res::Extern(s) => Some(Target::Extern(s)),
994 Res::Prim(_) | Res::Err | Res::Unresolved => None,
995 }
996}
997
998#[cfg(test)]
999#[allow(clippy::unwrap_used, clippy::expect_used)]
1000mod tests {
1001 use hir_lang::{BinderKind, Expr, Stmt};
1002
1003 use super::*;
1004 use crate::model::fixture::*;
1005
1006 #[test]
1007 fn test_apply_turns_refused_resolutions_into_diagnostics() {
1008 // fn f() { let x = 1; fn g() { x } } — plan `x` to the local anyway.
1009 let mut f = Fixture::new();
1010 let (x, g, fname) = (f.name("x"), f.name("g"), f.name("f"));
1011 let bx = f.b.new_binder(x, BinderKind::Local);
1012 let pat = f.b.bind(bx);
1013 let one = f.b.int(1);
1014 let s = f.b.let_stmt(pat, Some(one));
1015 let use_x = f.b.name_expr(x);
1016 let gb = f.b.block(&[], Some(use_x));
1017 let gi = f.b.func(g, &[], gb);
1018 let si = f.b.stmt(Stmt::Item(gi));
1019 let body = f.b.block(&[s, si], None);
1020 let fi = f.b.func(fname, &[], body);
1021 let root = f.b.module(None, &[fi]);
1022 let hir = f.finish(root);
1023 // `name_expr` made the unit's only path.
1024 let p = PathId::from_index(0).unwrap();
1025 assert_eq!(*hir.expr(use_x), Expr::Path(p));
1026 let (mut m, mut outs) = walked(hir, &f.names, Policy::new());
1027 // The walk already refused it; force the plan to exercise `apply`.
1028 outs[0].plan[p.index()] = Some((Res::Local(bx), 0));
1029 outs[0].diagnosed[p.index()] = false;
1030 outs[0].diags.clear();
1031 apply(&mut m.units[0], &mut outs[0]);
1032 assert_eq!(m.units[0].hir.path(p).res, Res::Err);
1033 assert!(matches!(
1034 outs[0].diags[..],
1035 [Diagnostic {
1036 kind: DiagKind::CannotCapture { .. },
1037 ..
1038 }]
1039 ));
1040 assert!(m.units[0].hir.validate().is_ok());
1041 }
1042
1043 #[test]
1044 fn test_ident_binds_only_for_ident_patterns() {
1045 let mut f = Fixture::new();
1046 let root = f.b.module(None, &[]);
1047 let hir = f.finish(root);
1048 let unit = ResolvedUnit {
1049 name: None,
1050 hir,
1051 members: Vec::new(),
1052 ident_matches: Vec::new(),
1053 };
1054 assert_eq!(unit.ident_binds(PatId::from_index(0).unwrap()), None);
1055 assert!(unit.members(ItemId::from_index(0).unwrap()).is_none());
1056 }
1057}