1use std::collections::HashMap;
40
41use crate::ast::{FnDef, TopLevel, TypeDef, TypeVariant};
42use crate::codegen::ModuleInfo;
43use crate::ir::identity::{BuiltinId, CtorId, FnId, FnKey, ModuleId, TypeId, TypeKey};
44
45#[derive(Debug, Clone)]
50pub struct FnEntry {
51 pub key: FnKey,
52 pub module: ModuleId,
53 pub index_in_module: u32,
54}
55
56#[derive(Debug, Clone)]
58pub struct TypeEntry {
59 pub key: TypeKey,
60 pub module: ModuleId,
61 pub index_in_module: u32,
62 pub variants: Vec<CtorId>,
66 pub is_product: bool,
72}
73
74#[derive(Debug, Clone)]
78pub struct CtorEntry {
79 pub owning_type: TypeId,
80 pub name: String,
85}
86
87#[derive(Debug, Clone)]
91pub struct ModuleEntry {
92 pub prefix: Option<String>,
94}
95
96#[derive(Debug, Clone, Default)]
101pub struct SymbolTable {
102 pub modules: Vec<ModuleEntry>,
103 pub fns: Vec<FnEntry>,
104 pub types: Vec<TypeEntry>,
105 pub ctors: Vec<CtorEntry>,
106 pub builtins: Vec<BuiltinEntry>,
113
114 fn_index: HashMap<FnKey, FnId>,
115 type_index: HashMap<TypeKey, TypeId>,
116 ctor_index: HashMap<(TypeId, String), CtorId>,
121 builtin_index: HashMap<String, BuiltinId>,
123}
124
125#[derive(Debug, Clone)]
131pub struct BuiltinEntry {
132 pub name: String,
133}
134
135impl SymbolTable {
136 pub fn build(entry_items: &[TopLevel], dep_modules: &[ModuleInfo]) -> Self {
143 let mut table = SymbolTable::default();
144
145 table.modules.push(ModuleEntry { prefix: None });
147 for m in dep_modules {
148 table.modules.push(ModuleEntry {
149 prefix: Some(m.prefix.clone()),
150 });
151 }
152
153 let entry_fns: Vec<&FnDef> = entry_items
157 .iter()
158 .filter_map(|i| match i {
159 TopLevel::FnDef(fd) => Some(fd),
160 _ => None,
161 })
162 .collect();
163 let entry_types: Vec<&TypeDef> = entry_items
164 .iter()
165 .filter_map(|i| match i {
166 TopLevel::TypeDef(td) => Some(td),
167 _ => None,
168 })
169 .collect();
170
171 type ScopeWalk<'a> = (ModuleId, Option<&'a str>, Vec<&'a FnDef>, Vec<&'a TypeDef>);
172 let scopes: Vec<ScopeWalk> =
173 std::iter::once((ModuleId::ENTRY, None, entry_fns, entry_types))
174 .chain(dep_modules.iter().enumerate().map(|(i, m)| {
175 let module_id = ModuleId((i + 1) as u32);
176 let fns: Vec<&FnDef> = m.fn_defs.iter().collect();
177 let types: Vec<&TypeDef> = m.type_defs.iter().collect();
178 (module_id, Some(m.prefix.as_str()), fns, types)
179 }))
180 .collect();
181
182 for (module_id, prefix, fns, types) in scopes {
183 for (index_in_module, fd) in fns.into_iter().enumerate() {
184 let key = match prefix {
185 Some(p) => FnKey::in_module(p.to_string(), fd.name.clone()),
186 None => FnKey::entry(fd.name.clone()),
187 };
188 let id = FnId(table.fns.len() as u32);
189 table.fn_index.insert(key.clone(), id);
190 table.fns.push(FnEntry {
191 key,
192 module: module_id,
193 index_in_module: index_in_module as u32,
194 });
195 }
196 for (index_in_module, td) in types.into_iter().enumerate() {
197 let (type_name, variants, is_product) = match td {
198 TypeDef::Sum { name, variants, .. } => (name.clone(), variants.clone(), false),
199 TypeDef::Product { name, .. } => (name.clone(), Vec::new(), true),
200 };
201 let key = match prefix {
202 Some(p) => TypeKey::in_module(p.to_string(), type_name.clone()),
203 None => TypeKey::entry(type_name.clone()),
204 };
205 let type_id = TypeId(table.types.len() as u32);
206 table.type_index.insert(key.clone(), type_id);
207 let ctor_ids: Vec<CtorId> = if is_product {
210 let cid = CtorId(table.ctors.len() as u32);
211 table.ctors.push(CtorEntry {
212 owning_type: type_id,
213 name: type_name.clone(),
214 });
215 table.ctor_index.insert((type_id, type_name.clone()), cid);
216 vec![cid]
217 } else {
218 let mut ids = Vec::with_capacity(variants.len());
219 for v in &variants {
220 let cid = CtorId(table.ctors.len() as u32);
221 table.ctors.push(CtorEntry {
222 owning_type: type_id,
223 name: v.name.clone(),
224 });
225 table.ctor_index.insert((type_id, v.name.clone()), cid);
226 ids.push(cid);
227 }
228 ids
229 };
230 table.types.push(TypeEntry {
231 key,
232 module: module_id,
233 index_in_module: index_in_module as u32,
234 variants: ctor_ids,
235 is_product,
236 });
237 }
238 }
239
240 table
241 }
242
243 pub fn fn_id_of(&self, key: &FnKey) -> Option<FnId> {
246 self.fn_index.get(key).copied()
247 }
248
249 pub fn type_id_of(&self, key: &TypeKey) -> Option<TypeId> {
251 self.type_index.get(key).copied()
252 }
253
254 pub fn type_id_by_bare_name(&self, name: &str) -> Option<TypeId> {
270 let mut found: Option<TypeId> = None;
271 for (key, id) in &self.type_index {
272 if key.name == name {
273 if found.is_some() {
274 return None;
277 }
278 found = Some(*id);
279 }
280 }
281 found
282 }
283
284 pub fn ctor_id_of(&self, owning_type: TypeId, variant: &str) -> Option<CtorId> {
286 self.ctor_index
287 .get(&(owning_type, variant.to_string()))
288 .copied()
289 }
290
291 pub fn fn_entry(&self, id: FnId) -> &FnEntry {
296 &self.fns[id.0 as usize]
297 }
298
299 pub fn type_entry(&self, id: TypeId) -> &TypeEntry {
300 &self.types[id.0 as usize]
301 }
302
303 pub fn ctor_entry(&self, id: CtorId) -> &CtorEntry {
304 &self.ctors[id.0 as usize]
305 }
306
307 pub fn module_entry(&self, id: ModuleId) -> &ModuleEntry {
308 &self.modules[id.0 as usize]
309 }
310
311 pub fn builtin_entry(&self, id: BuiltinId) -> &BuiltinEntry {
316 &self.builtins[id.0 as usize]
317 }
318
319 pub fn intern_builtin(&mut self, name: &str) -> BuiltinId {
326 if let Some(id) = self.builtin_index.get(name) {
327 return *id;
328 }
329 let id = BuiltinId(self.builtins.len() as u32);
330 self.builtins.push(BuiltinEntry {
331 name: name.to_string(),
332 });
333 self.builtin_index.insert(name.to_string(), id);
334 id
335 }
336
337 pub fn builtin_id_of(&self, name: &str) -> Option<BuiltinId> {
342 self.builtin_index.get(name).copied()
343 }
344
345 #[cfg(test)]
350 pub(crate) fn assert_consistent(&self) {
351 for (i, entry) in self.fns.iter().enumerate() {
352 assert_eq!(
353 self.fn_index.get(&entry.key),
354 Some(&FnId(i as u32)),
355 "fn_index out of sync at index {i}"
356 );
357 }
358 for (i, entry) in self.types.iter().enumerate() {
359 assert_eq!(
360 self.type_index.get(&entry.key),
361 Some(&TypeId(i as u32)),
362 "type_index out of sync at index {i}"
363 );
364 }
365 for (i, entry) in self.ctors.iter().enumerate() {
366 assert_eq!(
367 self.ctor_index
368 .get(&(entry.owning_type, entry.name.clone())),
369 Some(&CtorId(i as u32)),
370 "ctor_index out of sync at index {i}"
371 );
372 }
373 }
374}
375
376#[allow(dead_code)] fn _no_warning_for_unused_variant_field(_v: &TypeVariant) {}
378
379#[cfg(test)]
380mod tests {
381 use super::*;
382 use crate::ast::{TypeDef, TypeVariant};
383
384 fn product(name: &str, line: usize) -> TypeDef {
385 TypeDef::Product {
386 name: name.to_string(),
387 fields: vec![("value".to_string(), "Int".to_string())],
388 line,
389 }
390 }
391
392 fn sum(name: &str, variants: &[&str], line: usize) -> TypeDef {
393 TypeDef::Sum {
394 name: name.to_string(),
395 variants: variants
396 .iter()
397 .map(|v| TypeVariant {
398 name: v.to_string(),
399 fields: Vec::new(),
400 })
401 .collect(),
402 line,
403 }
404 }
405
406 fn module(prefix: &str, fns: Vec<FnDef>, types: Vec<TypeDef>) -> ModuleInfo {
407 ModuleInfo {
408 prefix: prefix.to_string(),
409 depends: Vec::new(),
410 type_defs: types,
411 fn_defs: fns,
412 verify_laws: Vec::new(),
413 analysis: None,
414 }
415 }
416
417 fn fn_def(name: &str) -> FnDef {
418 use crate::ast::{FnBody, Literal, Spanned};
419 FnDef {
420 name: name.to_string(),
421 line: 1,
422 params: Vec::new(),
423 return_type: "Int".to_string(),
424 effects: Vec::new(),
425 desc: None,
426 body: std::sync::Arc::new(FnBody::from_expr(Spanned::new(
427 crate::ast::Expr::Literal(Literal::Int(0)),
428 1,
429 ))),
430 resolution: None,
431 }
432 }
433
434 #[test]
435 fn entry_only_program_gets_entry_module_and_indexed_fns() {
436 let items = vec![
437 TopLevel::FnDef(fn_def("foo")),
438 TopLevel::FnDef(fn_def("bar")),
439 ];
440 let table = SymbolTable::build(&items, &[]);
441 table.assert_consistent();
442
443 assert_eq!(table.modules.len(), 1, "entry-only build has just ENTRY");
444 assert!(table.modules[0].prefix.is_none());
445
446 let foo_id = table.fn_id_of(&FnKey::entry("foo")).expect("foo missing");
447 let bar_id = table.fn_id_of(&FnKey::entry("bar")).expect("bar missing");
448 assert_ne!(foo_id, bar_id);
449 assert!(table.fn_entry(foo_id).module.is_entry());
450 }
451
452 #[test]
453 fn cross_module_same_bare_name_fns_get_distinct_ids() {
454 let mod_a = module("A", vec![fn_def("foo")], vec![]);
458 let mod_b = module("B", vec![fn_def("foo")], vec![]);
459 let table = SymbolTable::build(&[], &[mod_a, mod_b]);
460 table.assert_consistent();
461
462 let a_foo = table
463 .fn_id_of(&FnKey::in_module("A", "foo"))
464 .expect("A.foo missing");
465 let b_foo = table
466 .fn_id_of(&FnKey::in_module("B", "foo"))
467 .expect("B.foo missing");
468 assert_ne!(a_foo, b_foo);
469
470 assert!(
473 table.fn_id_of(&FnKey::entry("foo")).is_none(),
474 "bare-entry `foo` must miss when only module fns named `foo` exist"
475 );
476 }
477
478 #[test]
479 fn product_type_has_one_constructor_under_its_own_name() {
480 let items = vec![TopLevel::TypeDef(product("Natural", 1))];
481 let table = SymbolTable::build(&items, &[]);
482 table.assert_consistent();
483
484 let nat_id = table.type_id_of(&TypeKey::entry("Natural")).unwrap();
485 let entry = table.type_entry(nat_id);
486 assert!(entry.is_product);
487 assert_eq!(entry.variants.len(), 1);
488 let ctor_id = entry.variants[0];
489 assert_eq!(table.ctor_entry(ctor_id).name, "Natural");
490 assert_eq!(table.ctor_entry(ctor_id).owning_type, nat_id);
491 assert_eq!(table.ctor_id_of(nat_id, "Natural"), Some(ctor_id));
492 }
493
494 #[test]
495 fn sum_type_registers_each_variant_under_its_type() {
496 let items = vec![TopLevel::TypeDef(sum("Shape", &["Circle", "Square"], 1))];
497 let table = SymbolTable::build(&items, &[]);
498 table.assert_consistent();
499
500 let shape_id = table.type_id_of(&TypeKey::entry("Shape")).unwrap();
501 let entry = table.type_entry(shape_id);
502 assert!(!entry.is_product);
503 assert_eq!(entry.variants.len(), 2);
504 let circle = table.ctor_id_of(shape_id, "Circle").unwrap();
505 let square = table.ctor_id_of(shape_id, "Square").unwrap();
506 assert_ne!(circle, square);
507 assert_eq!(table.ctor_entry(circle).name, "Circle");
508 assert_eq!(table.ctor_entry(square).name, "Square");
509 }
510
511 #[test]
512 fn variant_name_collision_across_unrelated_sums_is_resolved_per_type() {
513 let items = vec![
519 TopLevel::TypeDef(sum("Validation", &["Ok", "Invalid"], 1)),
520 TopLevel::TypeDef(sum("Status", &["Ok", "Failed"], 5)),
521 ];
522 let table = SymbolTable::build(&items, &[]);
523 table.assert_consistent();
524
525 let v_id = table.type_id_of(&TypeKey::entry("Validation")).unwrap();
526 let s_id = table.type_id_of(&TypeKey::entry("Status")).unwrap();
527 let v_ok = table.ctor_id_of(v_id, "Ok").unwrap();
528 let s_ok = table.ctor_id_of(s_id, "Ok").unwrap();
529 assert_ne!(
530 v_ok, s_ok,
531 "same-bare-name variants across unrelated sums must be distinct"
532 );
533 }
534
535 #[test]
536 fn deterministic_indexing_across_repeated_builds() {
537 let items_a = vec![
541 TopLevel::FnDef(fn_def("a")),
542 TopLevel::FnDef(fn_def("b")),
543 TopLevel::TypeDef(product("R", 1)),
544 ];
545 let items_b = items_a.clone();
546 let t1 = SymbolTable::build(&items_a, &[]);
547 let t2 = SymbolTable::build(&items_b, &[]);
548 assert_eq!(
549 t1.fn_id_of(&FnKey::entry("a")),
550 t2.fn_id_of(&FnKey::entry("a"))
551 );
552 assert_eq!(
553 t1.type_id_of(&TypeKey::entry("R")),
554 t2.type_id_of(&TypeKey::entry("R"))
555 );
556 }
557
558 #[test]
559 fn entry_scope_is_always_module_id_zero() {
560 let mod_a = module("A", vec![fn_def("x")], vec![]);
563 let mod_b = module("B", vec![fn_def("y")], vec![]);
564 let table = SymbolTable::build(&[TopLevel::FnDef(fn_def("entry_fn"))], &[mod_a, mod_b]);
565 table.assert_consistent();
566 let entry_fn = table.fn_id_of(&FnKey::entry("entry_fn")).unwrap();
567 assert_eq!(table.fn_entry(entry_fn).module, ModuleId::ENTRY);
568 assert_eq!(table.module_entry(ModuleId::ENTRY).prefix, None);
569 }
570
571 #[test]
572 fn type_id_by_bare_name_resolves_unique_cross_module_type() {
573 let mod_a = module("A", vec![], vec![sum("Color", &["Red", "Blue"], 1)]);
579 let mod_b = module("B", vec![], vec![product("Val", 1)]);
580 let table = SymbolTable::build(&[], &[mod_a, mod_b]);
581 table.assert_consistent();
582
583 let val_id = table.type_id_by_bare_name("Val");
584 let qualified = table.type_id_of(&TypeKey::in_module("B", "Val"));
585 assert_eq!(val_id, qualified, "bare `Val` resolves to B.Val");
586 assert!(val_id.is_some());
587
588 let color_id = table.type_id_by_bare_name("Color");
589 assert_eq!(
590 color_id,
591 table.type_id_of(&TypeKey::in_module("A", "Color"))
592 );
593 }
594
595 #[test]
596 fn type_id_by_bare_name_returns_none_on_ambiguity() {
597 let mod_a = module("A", vec![], vec![product("T", 1)]);
605 let mod_b = module("B", vec![], vec![product("T", 1)]);
606 let table = SymbolTable::build(&[], &[mod_a, mod_b]);
607 table.assert_consistent();
608
609 assert_eq!(table.type_id_by_bare_name("T"), None);
610
611 assert!(table.type_id_of(&TypeKey::in_module("A", "T")).is_some());
613 assert!(table.type_id_of(&TypeKey::in_module("B", "T")).is_some());
614 }
615
616 #[test]
617 fn type_id_by_bare_name_finds_entry_scope_type() {
618 let entry_type = product("Cfg", 1);
621 let mod_a = module("A", vec![], vec![sum("Other", &["X"], 1)]);
622 let table = SymbolTable::build(&[TopLevel::TypeDef(entry_type)], &[mod_a]);
623 table.assert_consistent();
624
625 let cfg = table.type_id_by_bare_name("Cfg");
626 assert_eq!(cfg, table.type_id_of(&TypeKey::entry("Cfg")));
627 assert!(cfg.is_some());
628 }
629
630 #[test]
631 fn type_id_by_bare_name_missing_name_is_none() {
632 let mod_a = module("A", vec![], vec![product("X", 1)]);
633 let table = SymbolTable::build(&[], &[mod_a]);
634 table.assert_consistent();
635 assert_eq!(table.type_id_by_bare_name("NotATypeAnywhere"), None);
636 }
637}