mod call;
mod coerce;
mod dynamic;
mod engine;
mod exhaust;
mod finalize;
mod generics;
mod index;
mod items;
mod lower;
mod ops;
mod pat;
mod paths;
mod plan;
mod traits;
use alloc::{collections::BTreeMap, vec::Vec};
use hir_lang::{
BinderId, Def, DefId, ExprId, Hir, IdKind, IntLit, ItemId, NodeRef, PatId, PathId, Prim,
Symbol, TyId,
};
use crate::{
diag::{Diagnostic, DiagnosticKind, Severity},
error::{Budget, CheckError, Meter},
infer::{Infer, UnifyCfg},
mono::{Strategy, Use},
profile::{Profile, RecordTyping},
typed::{Coercion, NONE, Typed, WNode},
types::{Field, Tag, TypeId, Types},
};
pub(crate) use index::Index;
const NEST_CAP: u32 = 32;
#[derive(Debug)]
pub struct Checker<'h> {
hir: &'h Hir,
profile: Profile,
budget: Budget,
types: Types,
host: Host,
}
#[derive(Debug, Default)]
pub(crate) struct Host {
pub(crate) externs: Vec<(Symbol, TypeId)>,
pub(crate) foreign: Vec<(DefId, TypeId)>,
pub(crate) intrinsics: Vec<(Symbol, TypeId)>,
pub(crate) members: Vec<(TypeId, Symbol, TypeId)>,
pub(crate) mono_attrs: Vec<(Symbol, Strategy)>,
}
fn upsert<K: Ord + Copy, V>(table: &mut Vec<(K, V)>, key: K, value: V) {
match table.binary_search_by(|(k, _)| k.cmp(&key)) {
Ok(i) => {
if let Some(slot) = table.get_mut(i) {
slot.1 = value;
}
}
Err(i) => table.insert(i, (key, value)),
}
}
fn find<K: Ord + Copy, V: Copy>(table: &[(K, V)], key: K) -> Option<V> {
table
.binary_search_by(|(k, _)| k.cmp(&key))
.ok()
.and_then(|i| table.get(i))
.map(|&(_, v)| v)
}
impl<'h> Checker<'h> {
#[must_use]
pub fn new(hir: &'h Hir, profile: Profile) -> Self {
Self {
hir,
profile,
budget: Budget::for_hir(hir),
types: Types::new(),
host: Host::default(),
}
}
pub fn set_budget(&mut self, budget: Budget) -> &mut Self {
self.budget = budget;
self
}
pub fn types_mut(&mut self) -> &mut Types {
&mut self.types
}
pub fn declare_extern(&mut self, name: Symbol, ty: TypeId) -> &mut Self {
upsert(&mut self.host.externs, name, ty);
self
}
pub fn declare_foreign(&mut self, def: DefId, ty: TypeId) -> &mut Self {
upsert(&mut self.host.foreign, def, ty);
self
}
pub fn declare_intrinsic(&mut self, name: Symbol, ty: TypeId) -> &mut Self {
upsert(&mut self.host.intrinsics, name, ty);
self
}
pub fn declare_member(&mut self, owner: TypeId, name: Symbol, ty: TypeId) -> &mut Self {
let key = (owner, name);
match self
.host
.members
.binary_search_by(|&(o, n, _)| (o, n).cmp(&key))
{
Ok(i) => {
if let Some(slot) = self.host.members.get_mut(i) {
slot.2 = ty;
}
}
Err(i) => self.host.members.insert(i, (owner, name, ty)),
}
self
}
pub fn declare_mono_attribute(&mut self, name: Symbol, strategy: Strategy) -> &mut Self {
upsert(&mut self.host.mono_attrs, name, strategy);
self
}
pub fn check(self) -> Result<Typed, CheckError> {
let profile = self.profile;
if !profile.discipline.is_implemented() {
return Err(CheckError::NotImplemented {
discipline: profile.discipline,
});
}
if !profile.default_int.is_int() || !profile.default_float.is_float() {
return Err(CheckError::InvalidProfile);
}
let mut cx = Ctx::new(self.hir, profile, self.budget, self.types, self.host);
cx.meter.tick(1)?;
cx.build_index()?;
if profile.is_static() {
cx.check_static()?;
} else {
cx.check_dynamic()?;
}
cx.into_typed()
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Frame {
pub(crate) declared: TypeId,
pub(crate) ret: TypeId,
pub(crate) throws: Option<TypeId>,
pub(crate) yields: Option<TypeId>,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Target {
pub(crate) result: Option<TypeId>,
pub(crate) is_loop: bool,
}
pub(crate) struct Ctx<'h> {
pub(crate) hir: &'h Hir,
pub(crate) profile: Profile,
pub(crate) types: Types,
pub(crate) infer: Infer,
pub(crate) meter: Meter,
pub(crate) host: Host,
pub(crate) idx: Index,
pub(crate) expr_ty: Vec<u32>,
pub(crate) pat_ty: Vec<u32>,
pub(crate) binder_ty: Vec<u32>,
pub(crate) binder_site: Vec<u32>,
pub(crate) diags: Vec<Diagnostic>,
pub(crate) methods: Vec<(ExprId, ItemId)>,
pub(crate) coercions: Vec<(ExprId, Coercion, TypeId)>,
pub(crate) expect: Vec<u32>,
pub(crate) poisoned: Vec<bool>,
pub(crate) int_lits: Vec<(NodeRef, TypeId, IntLit)>,
pub(crate) frames: Vec<Frame>,
pub(crate) targets: Vec<Target>,
pub(crate) label_pos: Vec<u32>,
pub(crate) cur_self: Option<TypeId>,
pub(crate) ty_memo: Vec<u32>,
pub(crate) alias_state: Vec<u8>,
pub(crate) sigs: Vec<u32>,
pub(crate) sig_arena: Vec<lower::Sig>,
pub(crate) decl_memo: Vec<u32>,
pub(crate) record_fields: Vec<Option<(u32, u32)>>,
pub(crate) field_pool: Vec<Field>,
pub(crate) field_memo: Vec<u32>,
pub(crate) const_memo: Vec<(u8, i128)>,
pub(crate) loops: Vec<u32>,
pub(crate) filled: Vec<bool>,
pub(crate) deferred_ops: Vec<(ExprId, hir_lang::OpKind, ops::Want)>,
pub(crate) null_checks: Vec<ExprId>,
pub(crate) delegated: Vec<(ExprId, TypeId)>,
pub(crate) record_targets: Vec<(ExprId, paths::RecordRef, TypeId)>,
pub(crate) let_types: Vec<(hir_lang::StmtId, TypeId)>,
pub(crate) closure_types: Vec<TypeId>,
pub(crate) path_def: Vec<Option<Def>>,
pub(crate) callee_sigs: Vec<u32>,
pub(crate) call_stack: Vec<call::CallTarget>,
pub(crate) probes: Vec<(ExprId, Vec<Option<TypeId>>)>,
pub(crate) tasks: Vec<engine::Task>,
pub(crate) item_stamp: Vec<u32>,
pub(crate) item_epoch: u32,
pub(crate) cur_item: Option<ItemId>,
pub(crate) lower_ctx: Option<ItemId>,
pub(crate) param_lists: Vec<generics::ParamList>,
pub(crate) params_memo: Vec<u32>,
pub(crate) bound_lists: Vec<generics::BoundList>,
pub(crate) bounds_memo: Vec<u32>,
pub(crate) bounds_partial: Vec<u32>,
pub(crate) impl_tys: Vec<(TyId, ItemId, bool)>,
pub(crate) impl_ty_index: Vec<(TyId, u32)>,
pub(crate) subst_memo: Vec<u32>,
pub(crate) subst_stamp: Vec<u32>,
pub(crate) subst_epoch: u32,
pub(crate) tr: traits::TraitIndex,
pub(crate) pending: Vec<traits::Obligation>,
pub(crate) stuck: Vec<traits::Obligation>,
pub(crate) solve_depth: u32,
pub(crate) norm_depth: u32,
pub(crate) hidden: Vec<(TyId, TypeId)>,
pub(crate) coerce_site: NodeRef,
pub(crate) lower_depth: u32,
pub(crate) walk_stamp: Vec<u32>,
pub(crate) walk_epoch: u32,
pub(crate) try_iface: Option<Option<ItemId>>,
pub(crate) uses: Vec<Use>,
pub(crate) dyn_uses: Vec<(Option<ItemId>, TypeId, TypeId)>,
pub(crate) use_args: Vec<TypeId>,
pub(crate) item_size: Vec<u32>,
pub(crate) matches: Vec<ExprId>,
pub(crate) lit_ids: BTreeMap<Vec<u8>, u64>,
pub(crate) witnesses: Vec<(ExprId, u32, u32)>,
pub(crate) wnodes: Vec<WNode>,
pub(crate) wsyms: Vec<Symbol>,
}
impl<'h> Ctx<'h> {
fn new(hir: &'h Hir, profile: Profile, budget: Budget, types: Types, host: Host) -> Self {
let n = |k| hir.count(k);
Self {
hir,
profile,
types,
infer: Infer::default(),
meter: Meter::new(budget),
host,
idx: Index::default(),
expr_ty: alloc::vec![NONE; n(IdKind::Expr)],
pat_ty: alloc::vec![NONE; n(IdKind::Pat)],
binder_ty: alloc::vec![NONE; n(IdKind::Binder)],
binder_site: alloc::vec![NONE; n(IdKind::Binder)],
diags: Vec::new(),
methods: Vec::new(),
coercions: Vec::new(),
expect: alloc::vec![NONE; n(IdKind::Expr)],
poisoned: alloc::vec![false; n(IdKind::Expr)],
int_lits: Vec::new(),
frames: Vec::new(),
targets: Vec::new(),
label_pos: alloc::vec![NONE; n(IdKind::Binder)],
cur_self: None,
ty_memo: alloc::vec![NONE; n(IdKind::Ty)],
alias_state: alloc::vec![0; n(IdKind::Item)],
sigs: alloc::vec![NONE; n(IdKind::Item)],
sig_arena: Vec::new(),
decl_memo: alloc::vec![NONE; n(IdKind::Item)],
record_fields: alloc::vec![None; n(IdKind::Item)],
field_pool: Vec::new(),
field_memo: alloc::vec![NONE; n(IdKind::Field)],
const_memo: alloc::vec![(0, 0); n(IdKind::Item)],
loops: Vec::new(),
filled: Vec::new(),
deferred_ops: Vec::new(),
delegated: Vec::new(),
record_targets: Vec::new(),
let_types: Vec::new(),
closure_types: Vec::new(),
path_def: alloc::vec![None; n(IdKind::Path)],
null_checks: Vec::new(),
callee_sigs: alloc::vec![NONE; n(IdKind::Expr)],
call_stack: Vec::new(),
probes: Vec::new(),
tasks: Vec::new(),
item_stamp: alloc::vec![0; n(IdKind::Item)],
item_epoch: 0,
cur_item: None,
lower_ctx: None,
param_lists: Vec::new(),
params_memo: alloc::vec![NONE; n(IdKind::Item)],
bound_lists: Vec::new(),
bounds_memo: alloc::vec![NONE; n(IdKind::Item)],
bounds_partial: alloc::vec![NONE; n(IdKind::Item)],
impl_tys: Vec::new(),
impl_ty_index: Vec::new(),
subst_memo: Vec::new(),
subst_stamp: Vec::new(),
subst_epoch: 0,
tr: traits::TraitIndex::default(),
pending: Vec::new(),
stuck: Vec::new(),
solve_depth: 0,
norm_depth: 0,
hidden: Vec::new(),
coerce_site: NodeRef::Item(hir.root()),
lower_depth: 0,
try_iface: None,
walk_stamp: Vec::new(),
walk_epoch: 0,
uses: Vec::new(),
dyn_uses: Vec::new(),
use_args: Vec::new(),
item_size: alloc::vec![0; n(IdKind::Item)],
matches: Vec::new(),
lit_ids: BTreeMap::new(),
witnesses: Vec::new(),
wnodes: Vec::new(),
wsyms: Vec::new(),
}
}
pub(crate) fn report(&mut self, node: NodeRef, kind: DiagnosticKind) {
self.report_with(node, kind, Severity::Error);
}
pub(crate) fn report_with(&mut self, node: NodeRef, kind: DiagnosticKind, severity: Severity) {
let origin = self.hir.origin(node);
self.diags.push(Diagnostic {
kind,
node,
origin,
severity,
});
}
pub(crate) fn record_use(
&mut self,
at: ExprId,
callee: ItemId,
args: &[TypeId],
dispatch: crate::mono::Dispatch,
) {
let start = u32::try_from(self.use_args.len()).unwrap_or(NONE);
self.use_args.extend_from_slice(args);
self.uses.push(Use {
at,
owner: self.cur_item,
callee,
args: (start, u32::try_from(args.len()).unwrap_or(0)),
dispatch,
});
}
pub(crate) fn fresh(&mut self, class: u8) -> TypeId {
self.infer.fresh(&mut self.types, class)
}
pub(crate) fn resolve(&self, t: TypeId) -> TypeId {
self.infer.resolve(t)
}
pub(crate) fn tag(&self, t: TypeId) -> Tag {
self.types.node(self.resolve(t)).tag
}
pub(crate) fn is_err(&self, t: TypeId) -> bool {
self.tag(t) == Tag::Error
}
pub(crate) fn prim_of(&self, t: TypeId) -> Option<Prim> {
match self.types.get(self.resolve(t)) {
crate::types::Type::Prim(p) => Some(p),
_ => None,
}
}
pub(crate) fn unify(&mut self, a: TypeId, b: TypeId) -> Result<bool, CheckError> {
let cfg = UnifyCfg {
int_to_float: self.profile.numeric_widening,
structural: self.profile.records == RecordTyping::Structural,
record_fields: &self.record_fields,
field_pool: &self.field_pool,
};
self.infer.unify(&self.types, &cfg, &mut self.meter, a, b)
}
pub(crate) fn ety(&self, e: ExprId) -> TypeId {
self.expr_ty
.get(e.index())
.copied()
.filter(|&r| r != NONE)
.map_or(TypeId::ERROR, TypeId::from_raw)
}
pub(crate) fn child(&self, e: ExprId) -> TypeId {
if self.poisoned.get(e.index()).copied().unwrap_or(false) {
TypeId::ERROR
} else {
self.ety(e)
}
}
pub(crate) fn typed(&self, e: ExprId) -> bool {
self.expr_ty.get(e.index()).is_some_and(|&r| r != NONE)
}
pub(crate) fn poison(&mut self, e: ExprId) {
if let Some(p) = self.poisoned.get_mut(e.index()) {
*p = true;
}
}
pub(crate) fn set_expect(&mut self, e: ExprId, t: TypeId) {
if let Some(slot) = self.expect.get_mut(e.index()) {
*slot = t.raw();
}
}
pub(crate) fn take_expect(&mut self, e: ExprId) -> Option<TypeId> {
let slot = self.expect.get_mut(e.index())?;
let v = core::mem::replace(slot, NONE);
(v != NONE).then(|| TypeId::from_raw(v))
}
pub(crate) fn peek_expect(&self, e: ExprId) -> Option<TypeId> {
self.expect
.get(e.index())
.copied()
.filter(|&v| v != NONE)
.map(TypeId::from_raw)
}
pub(crate) fn set_binder(&mut self, b: BinderId, t: TypeId, site: PatId) {
if let Some(slot) = self.binder_ty.get_mut(b.index()) {
*slot = t.raw();
}
if let Some(slot) = self.binder_site.get_mut(b.index()) {
if *slot == NONE {
*slot = u32::try_from(site.index()).unwrap_or(NONE);
}
}
}
pub(crate) fn binder_type(&self, b: BinderId) -> Option<TypeId> {
self.binder_ty
.get(b.index())
.copied()
.filter(|&v| v != NONE)
.map(TypeId::from_raw)
}
pub(crate) fn host_extern(&self, name: Symbol) -> Option<TypeId> {
find(&self.host.externs, name)
}
pub(crate) fn host_foreign(&self, def: DefId) -> Option<TypeId> {
find(&self.host.foreign, def)
}
pub(crate) fn host_intrinsic(&self, name: Symbol) -> Option<TypeId> {
find(&self.host.intrinsics, name)
}
pub(crate) fn host_member(&self, owner: TypeId, name: Symbol) -> Option<TypeId> {
let key = (owner, name);
self.host
.members
.binary_search_by(|&(o, n, _)| (o, n).cmp(&key))
.ok()
.and_then(|i| self.host.members.get(i))
.map(|&(_, _, t)| t)
}
pub(crate) fn record_path_def(&mut self, path: PathId, def: Def) {
if let Some(slot) = self.path_def.get_mut(path.index()) {
*slot = Some(def);
}
}
pub(crate) fn nest_limit(&self) -> u32 {
self.meter.budget.trait_depth.min(NEST_CAP)
}
pub(crate) fn new_visit(&mut self) {
self.item_epoch = self.item_epoch.wrapping_add(1);
if self.item_epoch == 0 {
self.item_stamp.iter_mut().for_each(|s| *s = 0);
self.item_epoch = 1;
}
}
pub(crate) fn visit(&mut self, item: ItemId) -> bool {
match self.item_stamp.get_mut(item.index()) {
Some(s) if *s == self.item_epoch => false,
Some(s) => {
*s = self.item_epoch;
true
}
None => false,
}
}
pub(crate) fn name_item(&mut self, item: ItemId) {
if let Some(name) = self.hir.get_item(item).and_then(|it| it.name) {
self.types.name_item(item, name.sym);
}
}
pub(crate) fn item_kind(&self, item: ItemId) -> hir_lang::ItemKind {
self.hir
.get_item(item)
.map_or(hir_lang::ItemKind::Err, |it| it.kind)
}
}