1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
use super::*;
impl TypeChecker {
pub(super) fn check(&mut self, items: &[TopLevel], base_dir: Option<&str>) {
self.build_signatures(items);
if let Some(base) = base_dir
&& let Some(module) = Self::module_decl(items)
{
match crate::source::load_module_tree(&module.depends, base) {
Ok(modules) => {
let pairs: Vec<_> = modules
.iter()
.map(|m| (m.dep_name.clone(), m.items.clone()))
.collect();
let registry = crate::visibility::SymbolRegistry::from_modules(&pairs);
if let Err(e) = self.integrate_registry(®istry) {
self.error(e);
}
}
Err(e) => self.error(e),
}
}
self.check_top_level_stmts(items);
self.check_verify_blocks(items);
for item in items {
if let TopLevel::FnDef(f) = item {
self.check_fn(f);
}
}
}
// ── Memo-safety analysis ─────────────────────────────────────────────
/// A type is memo-safe if its runtime values can be cheaply hashed and
/// compared for equality (scalars, records/variants of scalars).
pub(super) fn is_memo_safe(&self, ty: &Type, visiting: &mut HashSet<String>) -> bool {
match ty {
// String stays excluded for now: memo keys hash String content,
// so string-heavy recursion can degrade to O(n) keying work.
Type::Int | Type::Float | Type::Bool | Type::Unit => true,
Type::Str => false,
Type::Tuple(items) => items.iter().all(|item| self.is_memo_safe(item, visiting)),
Type::List(_)
| Type::Vector(_)
| Type::Map(_, _)
| Type::Fn(_, _, _)
| Type::Unknown => false,
Type::Result(_, _) | Type::Option(_) => false,
Type::Named(name) => {
// Prevent infinite recursion for cyclic type defs
if !visiting.insert(name.clone()) {
return true;
}
let safe = self.named_type_memo_safe(name, visiting);
visiting.remove(name);
safe
}
}
}
/// Check whether a named user-defined type has only memo-safe fields.
pub(super) fn named_type_memo_safe(&self, name: &str, visiting: &mut HashSet<String>) -> bool {
// Check record fields: keys are "TypeName.fieldName"
let prefix = format!("{}.", name);
let mut found_fields = false;
for (key, field_ty) in &self.record_field_types {
if key.starts_with(&prefix) {
found_fields = true;
if !self.is_memo_safe(field_ty, visiting) {
return false;
}
}
}
if found_fields {
return true;
}
// Check sum type variants: constructors are registered in fn_sigs
// as "TypeName.VariantName" with param types, or in value_members
// for zero-arg constructors.
let mut found_variants = false;
for (key, sig) in &self.fn_sigs {
if key.starts_with(&prefix) && key.len() > prefix.len() {
found_variants = true;
for param in &sig.params {
if !self.is_memo_safe(param, visiting) {
return false;
}
}
}
}
for key in self.value_members.keys() {
if key.starts_with(&prefix) && key.len() > prefix.len() {
found_variants = true;
// Zero-arg constructors carry no data — always safe
}
}
if found_variants {
return true;
}
// Unknown named type — conservatively not safe
false
}
/// Compute the set of user-defined type names that are memo-safe.
pub(super) fn compute_memo_safe_types(&self, items: &[TopLevel]) -> HashSet<String> {
let mut safe = HashSet::new();
for item in items {
if let TopLevel::TypeDef(td) = item {
let name = match td {
TypeDef::Sum { name, .. } | TypeDef::Product { name, .. } => name,
};
let mut visiting = HashSet::new();
if self.is_memo_safe(&Type::Named(name.clone()), &mut visiting) {
safe.insert(name.clone());
}
}
}
safe
}
}