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 runtime: Runtime<'db>,
57
58 pub scope: Arc<Scope<'db, 'db>>,
60
61 variable_universes: Arc<Map<SymVariable<'db>, Universe>>,
63
64 variable_tys: Arc<Map<SymVariable<'db>, VariableTypeCell<'db>>>,
70
71 pub return_ty: Option<SymTy<'db>>,
73
74 assumptions: Arc<Vec<Assumption<'db>>>,
76}
77
78impl<'db> Env<'db> {
79 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![]), }
91 }
92
93 #[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 pub fn db(&self) -> &'db dyn crate::Db {
110 self.runtime.db
111 }
112
113 pub fn runtime(&self) -> &Runtime<'db> {
115 &self.runtime
116 }
117
118 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 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 #[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 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 pub fn increment_universe(&mut self) {
208 self.universe = self.universe.next();
209 }
210
211 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 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 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 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 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 #[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 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 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 #[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 #[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 #[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 #[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 #[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 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:?}") }
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 #[expect(dead_code)]
505 pub fn is_leased_var(&self, _var: SymVariable<'db>) -> bool {
506 false }
508
509 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 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 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 pub(crate) fn bound_vars(&self) -> Vec<SymVariable<'db>> {
587 self.scope.all_binders().into_iter().flatten().collect()
588 }
589
590 #[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 #[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
621pub 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 #[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 #[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 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 #[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 #[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 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#[derive(Copy, Clone)]
746enum VariableType<'db> {
747 Ast(VariableDecl<'db>),
757
758 InProgress(VariableDecl<'db>),
761
762 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}