lisette_semantics/pattern_analysis/
inhabitance.rs

1use rustc_hash::FxHashMap as HashMap;
2use std::cell::RefCell;
3
4use crate::store::Store;
5use syntax::ast::{EnumVariant, Generic, StructFieldDefinition};
6use syntax::program::Definition;
7use syntax::types::Type;
8use syntax::types::{SubstitutionMap, substitute};
9
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11enum InhabitanceState {
12    Visiting,
13    Inhabited,
14    Uninhabited,
15}
16
17#[derive(Default)]
18pub struct InhabitanceCache {
19    cache: RefCell<HashMap<String, InhabitanceState>>,
20}
21
22impl InhabitanceCache {
23    pub fn new() -> Self {
24        Self::default()
25    }
26}
27
28fn type_key(ty: &Type) -> String {
29    match ty.resolve() {
30        Type::Never => "Never".to_string(),
31        Type::Constructor { id, params, .. } => {
32            if params.is_empty() {
33                id.to_string()
34            } else {
35                let param_keys: Vec<String> = params.iter().map(type_key).collect();
36                format!("{}<{}>", id, param_keys.join(", "))
37            }
38        }
39        Type::Tuple(elements) => {
40            let elem_keys: Vec<String> = elements.iter().map(type_key).collect();
41            format!("({})", elem_keys.join(", "))
42        }
43        Type::Function { .. } => "fn".to_string(),
44        Type::Variable(_) | Type::Parameter(_) | Type::Error => "param".to_string(),
45        Type::Forall { body, .. } => type_key(&body),
46    }
47}
48
49pub fn is_inhabited(ty: &Type, store: &Store, cache: &InhabitanceCache) -> bool {
50    let resolved = ty.resolve();
51
52    match &resolved {
53        Type::Never => return false,
54        Type::Function { .. } => return true,
55        Type::Variable(_) | Type::Parameter(_) => return true,
56        _ => {}
57    }
58
59    if let Type::Tuple(elements) = &resolved {
60        return elements.iter().all(|e| is_inhabited(e, store, cache));
61    }
62
63    let key = type_key(&resolved);
64
65    {
66        let cache_ref = cache.cache.borrow();
67        if let Some(state) = cache_ref.get(&key) {
68            return match state {
69                InhabitanceState::Visiting => true,
70                InhabitanceState::Inhabited => true,
71                InhabitanceState::Uninhabited => false,
72            };
73        }
74    }
75
76    cache
77        .cache
78        .borrow_mut()
79        .insert(key.clone(), InhabitanceState::Visiting);
80
81    let result = match &resolved {
82        Type::Constructor { id, params, .. } => {
83            check_constructor_inhabited(id, params, store, cache)
84        }
85        Type::Forall { body, .. } => is_inhabited(body, store, cache),
86        _ => true,
87    };
88
89    let final_state = if result {
90        InhabitanceState::Inhabited
91    } else {
92        InhabitanceState::Uninhabited
93    };
94    cache.cache.borrow_mut().insert(key, final_state);
95
96    result
97}
98
99fn check_constructor_inhabited(
100    id: &str,
101    params: &[Type],
102    store: &Store,
103    cache: &InhabitanceCache,
104) -> bool {
105    let Some(definition) = store.get_definition(id) else {
106        return true;
107    };
108
109    match definition {
110        Definition::Enum {
111            generics, variants, ..
112        } => {
113            let map = build_substitution_map(generics, params);
114            variants
115                .iter()
116                .any(|v| is_variant_inhabited_with_map(v, &map, store, cache))
117        }
118
119        Definition::Struct {
120            generics, fields, ..
121        } => {
122            let map = build_substitution_map(generics, params);
123            fields.iter().all(|f| {
124                let field_ty = substitute(&f.ty, &map);
125                is_inhabited(&field_ty, store, cache)
126            })
127        }
128
129        Definition::TypeAlias { ty, generics, .. } => {
130            let map = build_substitution_map(generics, params);
131            let target_ty = substitute(ty, &map);
132
133            if is_self_referential_alias(id, &target_ty) {
134                return true;
135            }
136
137            is_inhabited(&target_ty, store, cache)
138        }
139
140        Definition::ValueEnum { .. } | Definition::Interface { .. } | Definition::Value { .. } => {
141            true
142        }
143    }
144}
145
146fn is_self_referential_alias(alias_id: &str, target_ty: &Type) -> bool {
147    match target_ty {
148        Type::Constructor { id, .. } => id == alias_id,
149        Type::Forall { body, .. } => is_self_referential_alias(alias_id, body),
150        _ => false,
151    }
152}
153
154pub fn is_variant_inhabited(
155    variant: &EnumVariant,
156    type_args: &[Type],
157    generics: &[Generic],
158    store: &Store,
159    cache: &InhabitanceCache,
160) -> bool {
161    let map = build_substitution_map(generics, type_args);
162    is_variant_inhabited_with_map(variant, &map, store, cache)
163}
164
165fn is_variant_inhabited_with_map(
166    variant: &EnumVariant,
167    map: &SubstitutionMap,
168    store: &Store,
169    cache: &InhabitanceCache,
170) -> bool {
171    variant.fields.iter().all(|field| {
172        let field_ty = substitute(&field.ty, map);
173        is_inhabited(&field_ty, store, cache)
174    })
175}
176
177pub fn is_struct_inhabited(
178    fields: &[StructFieldDefinition],
179    type_args: &[Type],
180    generics: &[Generic],
181    store: &Store,
182    cache: &InhabitanceCache,
183) -> bool {
184    let map = build_substitution_map(generics, type_args);
185    fields.iter().all(|f| {
186        let field_ty = substitute(&f.ty, &map);
187        is_inhabited(&field_ty, store, cache)
188    })
189}
190
191fn build_substitution_map(generics: &[Generic], type_args: &[Type]) -> SubstitutionMap {
192    generics
193        .iter()
194        .map(|g| g.name.clone())
195        .zip(type_args.iter().cloned())
196        .collect()
197}
lisette_semantics/pattern_analysis/inhabitance.rs

lisette_semantics/pattern_analysis/
inhabitance.rs
