Skip to main content

dada_ir_sym/check/
env.rs

1use std::{cell::Cell, ops::AsyncFnOnce, panic::Location, sync::Arc};
2
3use crate::{
4    check::{
5        debug::TaskDescription,
6        scope::Scope,
7        subtype::terms::{require_assignable_type, require_sub_terms},
8    },
9    ir::{
10        binder::BoundTerm,
11        generics::SymWhereClause,
12        indices::{FromInfer, InferVarIndex},
13        populate::variable_decl_requires_default_perm,
14        subst::SubstWith,
15        types::{
16            AnonymousPermSymbol, Assumption, AssumptionKind, SymGenericKind, SymGenericTerm,
17            SymPerm, SymTy, SymTyName, Variance,
18        },
19        variables::SymVariable,
20    },
21};
22use dada_ir_ast::{
23    ast::VariableDecl,
24    diagnostic::{Diagnostic, Err, Reported},
25    span::Span,
26};
27use dada_util::{Map, debug};
28
29use crate::{check::runtime::Runtime, check::universe::Universe, ir::exprs::SymExpr};
30
31use super::{
32    CheckTyInEnv,
33    debug::LogHandle,
34    inference::{Direction, InferVarKind, InferenceVarData},
35    live_places::LivePlaces,
36    predicates::{Predicate, require_where_clause::require_where_clause},
37    red::{RedPerm, RedTy},
38    report::{ArcOrElse, BooleanTypeRequired, OrElse},
39    runtime::DeferResult,
40    subtype::{
41        is_future::require_future_type,
42        is_numeric::{require_my_numeric_type, require_numeric_type},
43        relate_infer_bounds::relate_infer_bounds,
44        terms::reconcile_ty_bounds,
45    },
46};
47
48pub mod combinator;
49pub mod infer_bounds;
50pub(crate) struct Env<'db> {
51    pub log: LogHandle<'db>,
52
53    universe: Universe,
54
55    /// Reference to the runtime
56    runtime: Runtime<'db>,
57
58    /// Lexical scope for name resolution
59    pub scope: Arc<Scope<'db, 'db>>,
60
61    /// Universe of each free generic variable that is in scope.
62    variable_universes: Arc<Map<SymVariable<'db>, Universe>>,
63
64    /// Type for in-scope variables. Local variables
65    /// are stored directly in symbolic form but function
66    /// parameters are stored initially as AST types.
67    /// Those types are symbolified lazily.
68    /// See [`VariableType`] for details.
69    variable_tys: Arc<Map<SymVariable<'db>, VariableTypeCell<'db>>>,
70
71    /// If `None`, not type checking a function or method.
72    pub return_ty: Option<SymTy<'db>>,
73
74    /// Assumptions declared
75    assumptions: Arc<Vec<Assumption<'db>>>,
76}
77
78impl<'db> Env<'db> {
79    /// Create an empty environment
80    pub(crate) fn new(runtime: &Runtime<'db>, scope: Scope<'db, 'db>) -> Self {
81        Self {
82            log: runtime.root_log(),
83            universe: Universe::ROOT,
84            runtime: runtime.clone(),
85            scope: Arc::new(scope),
86            variable_tys: Default::default(),
87            variable_universes: Default::default(),
88            return_ty: Default::default(),
89            assumptions: Arc::new(vec![]), // FIXME
90        }
91    }
92
93    /// Extract the scope from the environment.
94    ///
95    /// # Panics
96    ///
97    /// If the scope has an outstanding reference.
98    #[track_caller]
99    pub fn into_scope(self) -> Scope<'db, 'db> {
100        Arc::into_inner(self.scope).unwrap()
101    }
102
103    #[expect(dead_code)]
104    pub fn universe(&self) -> Universe {
105        self.universe
106    }
107
108    /// Get the database
109    pub fn db(&self) -> &'db dyn crate::Db {
110        self.runtime.db
111    }
112
113    /// Access the lower-level type checking runtime
114    pub fn runtime(&self) -> &Runtime<'db> {
115        &self.runtime
116    }
117
118    /// Create a new environment from this environment.
119    /// The log will be adjusted per the `log` function.
120    pub fn fork(&self, log: impl FnOnce(&LogHandle<'db>) -> LogHandle<'db>) -> Env<'db> {
121        Env {
122            log: log(&self.log),
123            universe: self.universe,
124            runtime: self.runtime.clone(),
125            scope: self.scope.clone(),
126            variable_universes: self.variable_universes.clone(),
127            variable_tys: self.variable_tys.clone(),
128            return_ty: self.return_ty,
129            assumptions: self.assumptions.clone(),
130        }
131    }
132
133    /// True if the given variable is declared to meet the given predicate.
134    pub fn var_is_declared_to_be(&self, var: SymVariable<'db>, predicate: Predicate) -> bool {
135        let result = match predicate {
136            Predicate::Shared => self.assumed(var, |kind| {
137                matches!(
138                    kind,
139                    AssumptionKind::Shared | AssumptionKind::Our | AssumptionKind::Referenced
140                )
141            }),
142            Predicate::Unique => self.assumed(var, |kind| {
143                matches!(
144                    kind,
145                    AssumptionKind::Unique | AssumptionKind::My | AssumptionKind::Mutable
146                )
147            }),
148            Predicate::Owned => self.assumed(var, |kind| {
149                matches!(
150                    kind,
151                    AssumptionKind::Owned | AssumptionKind::My | AssumptionKind::Our
152                )
153            }),
154            Predicate::Lent => self.assumed(var, |kind| {
155                matches!(
156                    kind,
157                    AssumptionKind::Lent | AssumptionKind::Mutable | AssumptionKind::Referenced
158                )
159            }),
160        };
161
162        self.log("var_is_declared_to_be", &[&var, &predicate, &result]);
163
164        result
165    }
166
167    fn assumed(&self, var: SymVariable<'db>, kind: impl Fn(AssumptionKind) -> bool) -> bool {
168        self.assumptions
169            .iter()
170            .any(|a| a.var(self.db()) == var && kind(a.kind(self.db())))
171    }
172
173    /// Open the given symbols as universally quantified.
174    /// Creates a new universe.
175    #[allow(dead_code)]
176    pub fn open_universally<T>(&mut self, value: &T) -> T::LeafTerm
177    where
178        T: BoundTerm<'db>,
179    {
180        match value.as_binder() {
181            Err(leaf) => leaf.identity(),
182
183            Ok(binder) => {
184                self.increment_universe();
185                Arc::make_mut(&mut self.variable_universes)
186                    .extend(binder.variables.iter().map(|&v| (v, self.universe)));
187
188                self.open_universally(&binder.bound_value)
189            }
190        }
191    }
192
193    /// Create a substitution for `binder` consisting of inference variables
194    pub fn existential_substitution(
195        &mut self,
196        span: Span<'db>,
197        variables: &[SymVariable<'db>],
198    ) -> Vec<SymGenericTerm<'db>> {
199        let db = self.db();
200        variables
201            .iter()
202            .map(|&var| self.fresh_inference_var_term(var.kind(db), span))
203            .collect()
204    }
205
206    // Modify this environment to put it in a new universe.
207    pub fn increment_universe(&mut self) {
208        self.universe = self.universe.next();
209    }
210
211    /// Sets the symbolic type for a program variable. Used during environment
212    /// construction but typically you should use [`Self::push_program_variable_with_ty`]
213    /// instead.
214    pub fn set_variable_sym_ty(&mut self, lv: SymVariable<'db>, ty: SymTy<'db>) {
215        assert!(
216            self.scope.generic_sym_in_scope(self.db(), lv),
217            "variable `{lv:?}` not in scope"
218        );
219        assert!(
220            !self.variable_tys.contains_key(&lv),
221            "variable `{lv:?}` already has a type"
222        );
223        Arc::make_mut(&mut self.variable_tys).insert(lv, VariableTypeCell::symbolic(lv, ty));
224    }
225
226    /// Sets the AST type for a parameter that is in scope already.
227    /// This AST type will be lazily symbolified when requested.
228    pub fn set_variable_ast_ty(&mut self, lv: SymVariable<'db>, decl: VariableDecl<'db>) {
229        assert!(
230            self.scope.generic_sym_in_scope(self.db(), lv),
231            "variable `{lv:?}` not in scope"
232        );
233        assert!(
234            !self.variable_tys.contains_key(&lv),
235            "variable `{lv:?}` already has a type"
236        );
237        Arc::make_mut(&mut self.variable_tys).insert(lv, VariableTypeCell::ast(lv, decl));
238    }
239
240    /// Extends the scope with a new program variable given its type.
241    pub fn push_program_variable_with_ty(&mut self, lv: SymVariable<'db>, ty: SymTy<'db>) {
242        Arc::make_mut(&mut self.scope).push_link(lv);
243        self.set_variable_sym_ty(lv, ty);
244    }
245
246    /// Set the return type of the current function.
247    pub fn set_return_ty(&mut self, ty: SymTy<'db>) {
248        self.return_ty = Some(ty);
249    }
250
251    #[expect(dead_code)]
252    pub fn return_ty(&self) -> Option<SymTy<'db>> {
253        self.return_ty
254    }
255
256    /// Returns the type of the given variable.
257    ///
258    /// # Panics
259    ///
260    /// If the variable is not present.
261    pub async fn variable_ty(&mut self, lv: SymVariable<'db>) -> SymTy<'db> {
262        let variable_tys = self.variable_tys.clone();
263        variable_tys
264            .get(&lv)
265            .expect("variable not in scope")
266            .get(self)
267            .await
268    }
269
270    /// Create a fresh inference variable of the given kind.
271    #[track_caller]
272    pub fn fresh_inference_var(&mut self, kind: SymGenericKind, span: Span<'db>) -> InferVarIndex {
273        let data = match kind {
274            SymGenericKind::Type => {
275                let perm = self.fresh_inference_var(SymGenericKind::Perm, span);
276                InferenceVarData::new_ty(span, perm)
277            }
278            SymGenericKind::Perm => InferenceVarData::new_perm(span),
279            SymGenericKind::Place => panic!("inference variable of kind `Place` not supported"),
280        };
281        let infer = self.runtime.fresh_inference_var(&self.log, data);
282        self.log.log(
283            Location::caller(),
284            "created inference variable",
285            &[&infer, &kind, &span],
286        );
287
288        self.spawn(TaskDescription::RelateInferBounds, async move |env| {
289            relate_infer_bounds(env, infer).await
290        });
291
292        match kind {
293            SymGenericKind::Type => {
294                self.spawn(
295                    TaskDescription::ReconcileTyBounds(infer),
296                    async move |env| reconcile_ty_bounds(env, infer).await,
297                );
298            }
299            SymGenericKind::Perm => {}
300            SymGenericKind::Place => {}
301        }
302
303        infer
304    }
305
306    /// A fresh term with an inference variable of the given kind.
307    pub fn fresh_inference_var_term(
308        &mut self,
309        kind: SymGenericKind,
310        span: Span<'db>,
311    ) -> SymGenericTerm<'db> {
312        match kind {
313            SymGenericKind::Type => SymGenericTerm::Type(SymTy::infer(
314                self.db(),
315                self.fresh_inference_var(kind, span),
316            )),
317            SymGenericKind::Perm => SymGenericTerm::Perm(SymPerm::infer(
318                self.db(),
319                self.fresh_inference_var(kind, span),
320            )),
321            SymGenericKind::Place => panic!("cannot create inference variable for place"),
322        }
323    }
324
325    /// Create a fresh type inference variable.
326    pub fn fresh_ty_inference_var(&mut self, span: Span<'db>) -> SymTy<'db> {
327        SymTy::infer(
328            self.db(),
329            self.fresh_inference_var(SymGenericKind::Type, span),
330        )
331    }
332
333    /// Spawn a subtask that will require `value_ty` be assignable to `place_ty`.
334    #[track_caller]
335    pub(super) fn spawn_require_assignable_type(
336        &mut self,
337        live_after: LivePlaces,
338        value_ty: SymTy<'db>,
339        place_ty: SymTy<'db>,
340        or_else: &dyn OrElse<'db>,
341    ) {
342        debug!("defer require_assignable_object_type", value_ty, place_ty);
343        let or_else = or_else.to_arc();
344        self.runtime.spawn(
345            self,
346            TaskDescription::RequireAssignableType(value_ty, place_ty),
347            async move |env| {
348                debug!("require_assignable_object_type", value_ty, place_ty);
349
350                if let Ok(()) =
351                    require_assignable_type(env, live_after, value_ty, place_ty, &or_else).await
352                {
353                }
354            },
355        )
356    }
357
358    /// Spawn a subtask that will require `expected_ty` be equal to `found_ty`.
359    #[track_caller]
360    pub(super) fn spawn_require_equal_types(
361        &self,
362        live_after: LivePlaces,
363        expected_ty: SymTy<'db>,
364        found_ty: SymTy<'db>,
365        or_else: &dyn OrElse<'db>,
366    ) {
367        debug!("defer require_equal_object_types", expected_ty, found_ty);
368        let or_else = or_else.to_arc();
369        self.runtime.spawn(
370            self,
371            TaskDescription::RequireEqualTypes(expected_ty, found_ty),
372            async move |env| {
373                debug!("require_equal_object_types", expected_ty, found_ty);
374
375                env.require_both(
376                    async |env| {
377                        require_sub_terms(
378                            env,
379                            live_after,
380                            expected_ty.into(),
381                            found_ty.into(),
382                            &or_else,
383                        )
384                        .await
385                    },
386                    async |env| {
387                        require_sub_terms(
388                            env,
389                            live_after,
390                            found_ty.into(),
391                            expected_ty.into(),
392                            &or_else,
393                        )
394                        .await
395                    },
396                )
397                .await
398            },
399        )
400    }
401
402    /// Check that the value is a numeric type and has the permission `my`.
403    #[track_caller]
404    pub(super) fn spawn_require_my_numeric_type(
405        &mut self,
406        live_after: LivePlaces,
407        ty: SymTy<'db>,
408        or_else: &dyn OrElse<'db>,
409    ) {
410        let or_else = or_else.to_arc();
411        self.runtime.spawn(
412            self,
413            TaskDescription::RequireMyNumericType(ty),
414            async move |env| require_my_numeric_type(env, live_after, ty, &or_else).await,
415        )
416    }
417
418    /// Check that the value is a numeric type with any permission.
419    #[track_caller]
420    pub(super) fn spawn_require_numeric_type(&mut self, ty: SymTy<'db>, or_else: &dyn OrElse<'db>) {
421        let or_else = or_else.to_arc();
422        self.runtime.spawn(
423            self,
424            TaskDescription::RequireNumericType(ty),
425            async move |env| require_numeric_type(env, ty, &or_else).await,
426        )
427    }
428
429    #[track_caller]
430    pub(super) fn spawn_require_future_type(
431        &self,
432        live_after: LivePlaces,
433        ty: SymTy<'db>,
434        awaited_ty: SymTy<'db>,
435        or_else: &dyn OrElse<'db>,
436    ) {
437        let or_else = or_else.to_arc();
438        self.runtime.spawn(
439            self,
440            TaskDescription::RequireFutureType(ty),
441            async move |env| require_future_type(env, live_after, ty, awaited_ty, &or_else).await,
442        )
443    }
444
445    #[track_caller]
446    pub(super) fn spawn_require_where_clause(
447        &self,
448        where_clause: SymWhereClause<'db>,
449        or_else: &dyn OrElse<'db>,
450    ) {
451        let or_else = or_else.to_arc();
452        self.runtime.spawn(
453            self,
454            TaskDescription::RequireWhereClause(where_clause),
455            async move |env| require_where_clause(env, where_clause, &or_else).await,
456        )
457    }
458
459    /// Check whether any type in `tys` is known to be never (or error).
460    /// If so, do nothing.
461    /// Otherwise, if no type in `tys` is known to be never, invoke `op` (asynchronously).
462    #[track_caller]
463    pub fn spawn_if_not_never(
464        &mut self,
465        tys: &[SymTy<'db>],
466        op: impl AsyncFnOnce(&mut Env<'db>) + 'db,
467    ) {
468        let _tys = tys.to_vec();
469        self.runtime
470            .spawn(self, TaskDescription::IfNotNever, async move |env| {
471                // FIXME: check for never
472                op(env).await
473            })
474    }
475
476    pub fn describe_ty<'a>(&'a self, ty: SymTy<'db>) -> impl std::fmt::Display + 'a {
477        format!("{ty:?}") // FIXME
478    }
479
480    #[track_caller]
481    pub fn spawn<R>(
482        &mut self,
483        task_description: TaskDescription<'db>,
484        op: impl AsyncFnOnce(&mut Self) -> R + 'db,
485    ) where
486        R: DeferResult,
487    {
488        self.runtime
489            .spawn(self, task_description, async move |env| op(env).await)
490    }
491
492    pub(crate) fn require_expr_has_bool_ty(&mut self, live_after: LivePlaces, expr: SymExpr<'db>) {
493        let db = self.db();
494        let boolean_ty = SymTy::boolean(db);
495        self.spawn_require_assignable_type(
496            live_after,
497            expr.ty(db),
498            boolean_ty,
499            &BooleanTypeRequired::new(expr),
500        );
501    }
502
503    /// Check if the given (perm, type) variable is declared as mutable.
504    #[expect(dead_code)]
505    pub fn is_leased_var(&self, _var: SymVariable<'db>) -> bool {
506        false // FIXME
507    }
508
509    /// Span for code that prompted creation of inference variable `v`.
510    pub(crate) fn infer_var_span(&self, v: InferVarIndex) -> Span<'db> {
511        self.runtime.with_inference_var_data(v, |data| data.span())
512    }
513
514    /// Kind of this inference variable.
515    pub(crate) fn infer_var_kind(&self, v: InferVarIndex) -> InferVarKind {
516        self.runtime.with_inference_var_data(v, |data| data.kind())
517    }
518
519    pub(crate) fn variances(&self, n: SymTyName<'db>) -> Vec<Variance> {
520        match n {
521            SymTyName::Primitive(_) => vec![],
522            SymTyName::Future => vec![Variance::covariant()],
523            SymTyName::Tuple { arity } => vec![Variance::covariant(); arity],
524            SymTyName::Aggregate(aggr) => aggr.variances(self.db()),
525        }
526    }
527
528    /// If `infer` is a type variable, returns the permission variable associated with `infer`.
529    /// If `infer` is a permission variable, just returns `infer`.
530    pub fn perm_infer(&self, infer: InferVarIndex) -> InferVarIndex {
531        self.runtime().perm_infer(infer)
532    }
533
534    #[track_caller]
535    pub fn report(&self, diagnostic: Diagnostic) -> Reported {
536        self.log("report diagnostic", &[&diagnostic]);
537        diagnostic.report(self.db())
538    }
539
540    #[track_caller]
541    pub fn log(&self, message: &'static str, values: &[&dyn erased_serde::Serialize]) {
542        self.log.log(Location::caller(), message, values)
543    }
544
545    #[track_caller]
546    pub fn indent<R>(
547        &mut self,
548        message: &'static str,
549        values: &[&dyn erased_serde::Serialize],
550        op: impl AsyncFnOnce(&mut Self) -> R,
551    ) -> impl Future<Output = R>
552    where
553        R: erased_serde::Serialize,
554    {
555        let compiler_location = Location::caller();
556        self.indent_with_compiler_location(compiler_location, message, values, op)
557    }
558
559    pub async fn indent_with_compiler_location<R>(
560        &mut self,
561        compiler_location: &'static Location<'static>,
562        message: &'static str,
563        values: &[&dyn erased_serde::Serialize],
564        op: impl AsyncFnOnce(&mut Self) -> R,
565    ) -> R
566    where
567        R: erased_serde::Serialize,
568    {
569        self.log.indent(compiler_location, message, values);
570        let result = op(self).await;
571        self.log.log(compiler_location, "result", &[&result]);
572        self.log.undent(compiler_location, message);
573        result
574    }
575
576    pub fn log_result<T>(&mut self, compiler_location: &'static Location<'static>, value: T) -> T
577    where
578        T: erased_serde::Serialize,
579    {
580        self.log.log(compiler_location, "result", &[&value]);
581        value
582    }
583
584    /// Return a vector with all variables that are "bound" in the environment.
585    /// These correspond to in-scope function parameters, generic types, etc.
586    pub(crate) fn bound_vars(&self) -> Vec<SymVariable<'db>> {
587        self.scope.all_binders().into_iter().flatten().collect()
588    }
589
590    /// Record that `lower <: upper` must hold,
591    /// returning true if this is the first time that this has been recorded
592    /// or false if it has been recorded before.
593    ///
594    /// # Panics
595    ///
596    /// If `lower == upper`, as that is just always true, why record it?
597    #[track_caller]
598    pub fn insert_sub_infer_var_pair(
599        &mut self,
600        lower: InferVarIndex,
601        upper: InferVarIndex,
602    ) -> bool {
603        assert_ne!(lower, upper);
604        self.runtime
605            .insert_sub_infer_var_pair(lower, upper, &self.log)
606    }
607
608    /// Return a struct that gives ability to peek, modify, or block on the lower or upper red-ty-bound
609    /// on the given inference variable.
610    #[track_caller]
611    pub fn red_bound(&self, infer: InferVarIndex, direction: Direction) -> RedBound<'_, 'db> {
612        RedBound {
613            env: self,
614            infer,
615            direction,
616            compiler_location: Location::caller(),
617        }
618    }
619}
620
621/// Accessor for the bounding red-ty or red-perm on an inference variable.
622/// Can be used to read or modify the current values but
623/// can also be awaited through
624/// impl, which will block until a value is set by another task.
625/// Note that red-ty bounds can be set more than once but must always
626/// get tighter each time they are modified.
627pub struct RedBound<'env, 'db> {
628    env: &'env Env<'db>,
629    infer: InferVarIndex,
630    direction: Direction,
631    compiler_location: &'static Location<'static>,
632}
633
634impl<'env, 'db> RedBound<'env, 'db> {
635    /// Read the current value of the bound
636    #[track_caller]
637    pub fn peek_ty(self) -> Option<(RedTy<'db>, ArcOrElse<'db>)> {
638        self.env
639            .runtime
640            .with_inference_var_data(self.infer, |data| data.red_ty_bound(self.direction))
641    }
642
643    /// Modify the current value of the bound
644    #[track_caller]
645    pub fn set_ty(self, red_ty: RedTy<'db>, or_else: &dyn OrElse<'db>) {
646        self.env
647            .runtime
648            .mutate_inference_var_data(self.infer, &self.env.log, |data| {
649                data.set_red_ty_bound(self.direction, red_ty, or_else)
650            })
651    }
652
653    /// Convert to a future that blocks until the red-ty future is set
654    pub fn ty(self) -> impl Future<Output = Option<(RedTy<'db>, ArcOrElse<'db>)>> {
655        self.env.runtime.loop_on_inference_var(
656            self.infer,
657            self.compiler_location,
658            &self.env.log,
659            move |data| data.red_ty_bound(self.direction),
660        )
661    }
662
663    /// Read the current value of the bound
664    #[track_caller]
665    pub fn peek_perm(self) -> Option<(RedPerm<'db>, ArcOrElse<'db>)> {
666        self.env
667            .runtime
668            .with_inference_var_data(self.infer, |data| data.red_perm_bound(self.direction))
669    }
670
671    /// Modify the current value of the bound
672    #[track_caller]
673    pub fn set_perm(self, red_perm: RedPerm<'db>, or_else: &dyn OrElse<'db>) {
674        self.env
675            .runtime
676            .mutate_inference_var_data(self.infer, &self.env.log, |data| {
677                data.set_red_perm_bound(self.direction, red_perm, or_else)
678            })
679    }
680}
681
682#[derive(Clone)]
683struct VariableTypeCell<'db> {
684    lv: SymVariable<'db>,
685    state: Cell<VariableType<'db>>,
686}
687
688impl<'db> VariableTypeCell<'db> {
689    fn symbolic(lv: SymVariable<'db>, ty: SymTy<'db>) -> Self {
690        Self {
691            lv,
692            state: Cell::new(VariableType::Symbolic(ty)),
693        }
694    }
695
696    fn ast(lv: SymVariable<'db>, decl: VariableDecl<'db>) -> Self {
697        Self {
698            lv,
699            state: Cell::new(VariableType::Ast(decl)),
700        }
701    }
702
703    async fn get(&self, env: &mut Env<'db>) -> SymTy<'db> {
704        let db = env.db();
705        match self.state.get() {
706            VariableType::Ast(decl) => {
707                self.state.set(VariableType::InProgress(decl));
708                let sym_base_ty = decl.base_ty(db).check_in_env(env).await;
709
710                let sym_ty = if let Some(ast_perm) = decl.perm(db) {
711                    let sym_perm = ast_perm.check_in_env(env).await;
712                    SymTy::perm(db, sym_perm, sym_base_ty)
713                } else if variable_decl_requires_default_perm(db, decl, &env.scope) {
714                    let sym_perm = SymPerm::var(db, decl.anonymous_perm_symbol(db));
715                    SymTy::perm(db, sym_perm, sym_base_ty)
716                } else {
717                    sym_base_ty
718                };
719
720                // update state to symbolic unless it was already set to an error
721                if let VariableType::InProgress(_) = self.state.get() {
722                    self.state.set(VariableType::Symbolic(sym_ty));
723                }
724                sym_ty
725            }
726            VariableType::InProgress(decl) => {
727                let ty_err = SymTy::err(
728                    db,
729                    Diagnostic::error(
730                        db,
731                        decl.base_ty(db).span(db),
732                        format!("type of `{}` references itself", self.lv),
733                    )
734                    .report(db),
735                );
736                self.state.set(VariableType::Symbolic(ty_err));
737                ty_err
738            }
739            VariableType::Symbolic(sym_ty) => sym_ty,
740        }
741    }
742}
743
744/// The type of a variable.
745#[derive(Copy, Clone)]
746enum VariableType<'db> {
747    /// AST form of the type is available and we have not yet begun to symbolify it.
748    /// AST types are used when we introduce a set of variables, where each variable
749    /// may refer to others as part of its type. In that case we don't know the right
750    /// order to process the variables in so we have to do a depth-first search.
751    ///
752    /// e.g., in `fn foo(x: shared[y] String, y: my Vec[String])`, we could begin with
753    /// `y` then `x`, but that is not clear at first. So instead we begin with `x`, mark it as
754    /// in progress, and then to convert `y` to a symbolic expression, wind up converting
755    /// the type of `y`. If `y` did refer to `x`, this would result in an error.
756    Ast(VariableDecl<'db>),
757
758    /// AST form of the type is available and we have begun symbolifying it.
759    /// When in this state, a repeated request for the variable's type will report an error.
760    InProgress(VariableDecl<'db>),
761
762    /// Symbolic type is available. For local variables, we introduce the type directly
763    /// in this form, but for parameters or other cases where there are a set of variables
764    /// introduced at once, we have to begin with AST form.
765    Symbolic(SymTy<'db>),
766}
767
768impl<'db> std::fmt::Debug for Env<'db> {
769    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
770        f.debug_struct("Env").finish()
771    }
772}