sigil_parser/
typeck.rs

1//! Type checker for Sigil.
2//!
3//! Implements bidirectional type inference with evidentiality tracking.
4//! The type system enforces that evidence levels propagate correctly
5//! through computations.
6
7use crate::ast::*;
8use crate::span::Span;
9use std::collections::HashMap;
10use std::fmt;
11use std::rc::Rc;
12use std::cell::RefCell;
13
14/// Internal type representation.
15#[derive(Debug, Clone, PartialEq)]
16pub enum Type {
17    /// Primitive types
18    Unit,
19    Bool,
20    Int(IntSize),
21    Float(FloatSize),
22    Char,
23    Str,
24
25    /// Compound types
26    Array { element: Box<Type>, size: Option<usize> },
27    Slice(Box<Type>),
28    Tuple(Vec<Type>),
29
30    /// Named type (struct, enum, type alias)
31    Named {
32        name: String,
33        generics: Vec<Type>,
34    },
35
36    /// Function type
37    Function {
38        params: Vec<Type>,
39        return_type: Box<Type>,
40        is_async: bool,
41    },
42
43    /// Reference types
44    Ref { mutable: bool, inner: Box<Type> },
45    Ptr { mutable: bool, inner: Box<Type> },
46
47    /// Evidential wrapper - the core of Sigil's type system
48    Evidential {
49        inner: Box<Type>,
50        evidence: EvidenceLevel,
51    },
52
53    /// Cyclic type (modular arithmetic)
54    Cycle { modulus: usize },
55
56    /// SIMD vector type
57    Simd { element: Box<Type>, lanes: u8 },
58
59    /// Atomic type
60    Atomic(Box<Type>),
61
62    /// Type variable for inference
63    Var(TypeVar),
64
65    /// Error type (for error recovery)
66    Error,
67
68    /// Never type (diverging)
69    Never,
70}
71
72/// Integer sizes
73#[derive(Debug, Clone, Copy, PartialEq, Eq)]
74pub enum IntSize {
75    I8, I16, I32, I64, I128,
76    U8, U16, U32, U64, U128,
77    ISize, USize,
78}
79
80/// Float sizes
81#[derive(Debug, Clone, Copy, PartialEq, Eq)]
82pub enum FloatSize {
83    F32, F64,
84}
85
86/// Evidence levels in the type system.
87///
88/// Evidence forms a lattice:
89///   Known (!) < Uncertain (?) < Reported (~) < Paradox (‽)
90///
91/// Operations combine evidence levels using join (⊔):
92///   a + b : join(evidence(a), evidence(b))
93#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
94pub enum EvidenceLevel {
95    /// Direct knowledge - computed locally, verified
96    Known,      // !
97    /// Uncertain - inferred, possible, not verified
98    Uncertain,  // ?
99    /// Reported - from external source, hearsay
100    Reported,   // ~
101    /// Paradox - contradictory information
102    Paradox,    // ‽
103}
104
105impl EvidenceLevel {
106    /// Join two evidence levels (least upper bound in lattice)
107    pub fn join(self, other: Self) -> Self {
108        std::cmp::max(self, other)
109    }
110
111    /// Meet two evidence levels (greatest lower bound)
112    pub fn meet(self, other: Self) -> Self {
113        std::cmp::min(self, other)
114    }
115
116    /// Convert from AST representation
117    pub fn from_ast(e: Evidentiality) -> Self {
118        match e {
119            Evidentiality::Known => EvidenceLevel::Known,
120            Evidentiality::Uncertain => EvidenceLevel::Uncertain,
121            Evidentiality::Reported => EvidenceLevel::Reported,
122            Evidentiality::Paradox => EvidenceLevel::Paradox,
123        }
124    }
125
126    /// Symbol representation
127    pub fn symbol(&self) -> &'static str {
128        match self {
129            EvidenceLevel::Known => "!",
130            EvidenceLevel::Uncertain => "?",
131            EvidenceLevel::Reported => "~",
132            EvidenceLevel::Paradox => "‽",
133        }
134    }
135
136    /// Human-readable name
137    pub fn name(&self) -> &'static str {
138        match self {
139            EvidenceLevel::Known => "known",
140            EvidenceLevel::Uncertain => "uncertain",
141            EvidenceLevel::Reported => "reported",
142            EvidenceLevel::Paradox => "paradox",
143        }
144    }
145
146    /// Check if this evidence level can satisfy a required level.
147    ///
148    /// Evidence is covariant: you can pass more certain data where less certain is expected.
149    /// Known (!) can satisfy any requirement.
150    /// Reported (~) can only satisfy Reported or Paradox requirements.
151    ///
152    /// Returns true if `self` (actual) can be used where `required` is expected.
153    pub fn satisfies(self, required: Self) -> bool {
154        // More certain evidence (lower in lattice) can satisfy less certain requirements
155        // Known <= Uncertain <= Reported <= Paradox
156        self <= required
157    }
158}
159
160/// Type variable for inference
161#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
162pub struct TypeVar(pub u32);
163
164/// Type error
165#[derive(Debug, Clone)]
166pub struct TypeError {
167    pub message: String,
168    pub span: Option<Span>,
169    pub notes: Vec<String>,
170}
171
172impl TypeError {
173    pub fn new(message: impl Into<String>) -> Self {
174        Self {
175            message: message.into(),
176            span: None,
177            notes: Vec::new(),
178        }
179    }
180
181    pub fn with_span(mut self, span: Span) -> Self {
182        self.span = Some(span);
183        self
184    }
185
186    pub fn with_note(mut self, note: impl Into<String>) -> Self {
187        self.notes.push(note.into());
188        self
189    }
190}
191
192impl fmt::Display for TypeError {
193    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
194        write!(f, "{}", self.message)?;
195        if let Some(span) = self.span {
196            write!(f, " at {}", span)?;
197        }
198        for note in &self.notes {
199            write!(f, "\n  note: {}", note)?;
200        }
201        Ok(())
202    }
203}
204
205/// Type environment for scoped lookups
206#[derive(Debug, Clone)]
207pub struct TypeEnv {
208    /// Variable bindings: name -> (type, evidence)
209    bindings: HashMap<String, (Type, EvidenceLevel)>,
210    /// Parent scope
211    parent: Option<Rc<RefCell<TypeEnv>>>,
212}
213
214impl TypeEnv {
215    pub fn new() -> Self {
216        Self {
217            bindings: HashMap::new(),
218            parent: None,
219        }
220    }
221
222    pub fn with_parent(parent: Rc<RefCell<TypeEnv>>) -> Self {
223        Self {
224            bindings: HashMap::new(),
225            parent: Some(parent),
226        }
227    }
228
229    /// Define a new binding
230    pub fn define(&mut self, name: String, ty: Type, evidence: EvidenceLevel) {
231        self.bindings.insert(name, (ty, evidence));
232    }
233
234    /// Look up a binding
235    pub fn lookup(&self, name: &str) -> Option<(Type, EvidenceLevel)> {
236        if let Some(binding) = self.bindings.get(name) {
237            Some(binding.clone())
238        } else if let Some(ref parent) = self.parent {
239            parent.borrow().lookup(name)
240        } else {
241            None
242        }
243    }
244}
245
246impl Default for TypeEnv {
247    fn default() -> Self {
248        Self::new()
249    }
250}
251
252/// Type definitions (structs, enums, type aliases)
253#[derive(Debug, Clone)]
254pub enum TypeDef {
255    Struct {
256        generics: Vec<String>,
257        fields: Vec<(String, Type)>,
258    },
259    Enum {
260        generics: Vec<String>,
261        variants: Vec<(String, Option<Vec<Type>>)>,
262    },
263    Alias {
264        generics: Vec<String>,
265        target: Type,
266    },
267}
268
269/// The type checker
270pub struct TypeChecker {
271    /// Type environment stack
272    env: Rc<RefCell<TypeEnv>>,
273    /// Type definitions
274    types: HashMap<String, TypeDef>,
275    /// Function signatures
276    functions: HashMap<String, Type>,
277    /// Type variable counter
278    next_var: u32,
279    /// Inferred type variable substitutions
280    substitutions: HashMap<TypeVar, Type>,
281    /// Collected errors
282    errors: Vec<TypeError>,
283}
284
285impl TypeChecker {
286    pub fn new() -> Self {
287        let mut checker = Self {
288            env: Rc::new(RefCell::new(TypeEnv::new())),
289            types: HashMap::new(),
290            functions: HashMap::new(),
291            next_var: 0,
292            substitutions: HashMap::new(),
293            errors: Vec::new(),
294        };
295
296        // Register built-in types and functions
297        checker.register_builtins();
298        checker
299    }
300
301    fn register_builtins(&mut self) {
302        // Helper to create a function type
303        let func = |params: Vec<Type>, ret: Type| Type::Function {
304            params,
305            return_type: Box::new(ret),
306            is_async: false,
307        };
308
309        // Type variable for generic functions
310        let any = Type::Var(TypeVar(9999)); // Use high number to avoid conflicts
311
312        // ===================
313        // Core I/O
314        // ===================
315        // print accepts any type (polymorphic)
316        self.functions.insert("print".to_string(), func(vec![any.clone()], Type::Unit));
317        self.functions.insert("println".to_string(), func(vec![any.clone()], Type::Unit));
318        self.functions.insert("input".to_string(), func(vec![], Type::Str));
319        self.functions.insert("input_line".to_string(), func(vec![], Type::Str));
320
321        // ===================
322        // Type inspection
323        // ===================
324        self.functions.insert("type_of".to_string(), func(vec![any.clone()], Type::Str));
325        self.functions.insert("len".to_string(), func(vec![any.clone()], Type::Int(IntSize::USize)));
326
327        // ===================
328        // String functions
329        // ===================
330        self.functions.insert("str".to_string(), func(vec![any.clone()], Type::Str));
331        self.functions.insert("upper".to_string(), func(vec![Type::Str], Type::Str));
332        self.functions.insert("lower".to_string(), func(vec![Type::Str], Type::Str));
333        self.functions.insert("trim".to_string(), func(vec![Type::Str], Type::Str));
334        self.functions.insert("split".to_string(), func(
335            vec![Type::Str, Type::Str],
336            Type::Array { element: Box::new(Type::Str), size: None }
337        ));
338        self.functions.insert("join".to_string(), func(
339            vec![Type::Array { element: Box::new(Type::Str), size: None }, Type::Str],
340            Type::Str
341        ));
342        self.functions.insert("contains".to_string(), func(vec![Type::Str, Type::Str], Type::Bool));
343        self.functions.insert("starts_with".to_string(), func(vec![Type::Str, Type::Str], Type::Bool));
344        self.functions.insert("ends_with".to_string(), func(vec![Type::Str, Type::Str], Type::Bool));
345        self.functions.insert("replace".to_string(), func(vec![Type::Str, Type::Str, Type::Str], Type::Str));
346        self.functions.insert("char_at".to_string(), func(vec![Type::Str, Type::Int(IntSize::I64)], Type::Str));
347        self.functions.insert("substring".to_string(), func(
348            vec![Type::Str, Type::Int(IntSize::I64), Type::Int(IntSize::I64)],
349            Type::Str
350        ));
351
352        // ===================
353        // Math functions
354        // ===================
355        let f64_ty = Type::Float(FloatSize::F64);
356        let i64_ty = Type::Int(IntSize::I64);
357
358        self.functions.insert("abs".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
359        self.functions.insert("sqrt".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
360        self.functions.insert("sin".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
361        self.functions.insert("cos".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
362        self.functions.insert("tan".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
363        self.functions.insert("floor".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
364        self.functions.insert("ceil".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
365        self.functions.insert("round".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
366        self.functions.insert("pow".to_string(), func(vec![f64_ty.clone(), f64_ty.clone()], f64_ty.clone()));
367        self.functions.insert("log".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
368        self.functions.insert("exp".to_string(), func(vec![f64_ty.clone()], f64_ty.clone()));
369        self.functions.insert("min".to_string(), func(vec![any.clone(), any.clone()], any.clone()));
370        self.functions.insert("max".to_string(), func(vec![any.clone(), any.clone()], any.clone()));
371
372        // ===================
373        // Array/Collection functions
374        // ===================
375        self.functions.insert("sum".to_string(), func(vec![any.clone()], f64_ty.clone()));
376        self.functions.insert("avg".to_string(), func(vec![any.clone()], f64_ty.clone()));
377        self.functions.insert("push".to_string(), func(vec![any.clone(), any.clone()], Type::Unit));
378        self.functions.insert("pop".to_string(), func(vec![any.clone()], any.clone()));
379        self.functions.insert("first".to_string(), func(vec![any.clone()], any.clone()));
380        self.functions.insert("last".to_string(), func(vec![any.clone()], any.clone()));
381        self.functions.insert("reverse".to_string(), func(vec![any.clone()], any.clone()));
382        self.functions.insert("sort".to_string(), func(vec![any.clone()], any.clone()));
383        self.functions.insert("range".to_string(), func(
384            vec![i64_ty.clone(), i64_ty.clone()],
385            Type::Array { element: Box::new(i64_ty.clone()), size: None }
386        ));
387
388        // ===================
389        // Assertions (for testing)
390        // ===================
391        self.functions.insert("assert".to_string(), func(vec![Type::Bool], Type::Unit));
392        self.functions.insert("assert_eq".to_string(), func(vec![any.clone(), any.clone()], Type::Unit));
393        self.functions.insert("assert_ne".to_string(), func(vec![any.clone(), any.clone()], Type::Unit));
394        self.functions.insert("assert_lt".to_string(), func(vec![any.clone(), any.clone()], Type::Unit));
395        self.functions.insert("assert_le".to_string(), func(vec![any.clone(), any.clone()], Type::Unit));
396        self.functions.insert("assert_gt".to_string(), func(vec![any.clone(), any.clone()], Type::Unit));
397        self.functions.insert("assert_ge".to_string(), func(vec![any.clone(), any.clone()], Type::Unit));
398        self.functions.insert("assert_true".to_string(), func(vec![Type::Bool], Type::Unit));
399        self.functions.insert("assert_false".to_string(), func(vec![Type::Bool], Type::Unit));
400        self.functions.insert("assert_null".to_string(), func(vec![any.clone()], Type::Unit));
401        self.functions.insert("assert_not_null".to_string(), func(vec![any.clone()], Type::Unit));
402        self.functions.insert("assert_contains".to_string(), func(vec![any.clone(), any.clone()], Type::Unit));
403        self.functions.insert("assert_len".to_string(), func(vec![any.clone(), i64_ty.clone()], Type::Unit));
404
405        // ===================
406        // Random
407        // ===================
408        self.functions.insert("random".to_string(), func(vec![], f64_ty.clone()));
409        self.functions.insert("random_int".to_string(), func(vec![i64_ty.clone(), i64_ty.clone()], i64_ty.clone()));
410        self.functions.insert("shuffle".to_string(), func(vec![any.clone()], any.clone()));
411
412        // ===================
413        // Time
414        // ===================
415        self.functions.insert("now".to_string(), func(vec![], f64_ty.clone()));
416        self.functions.insert("sleep".to_string(), func(vec![f64_ty.clone()], Type::Unit));
417
418        // ===================
419        // Conversion
420        // ===================
421        self.functions.insert("int".to_string(), func(vec![any.clone()], i64_ty.clone()));
422        self.functions.insert("float".to_string(), func(vec![any.clone()], f64_ty.clone()));
423        self.functions.insert("bool".to_string(), func(vec![any.clone()], Type::Bool));
424
425        // ===================
426        // Error handling
427        // ===================
428        self.functions.insert("panic".to_string(), func(vec![Type::Str], Type::Never));
429        self.functions.insert("todo".to_string(), func(vec![], Type::Never));
430        self.functions.insert("unreachable".to_string(), func(vec![], Type::Never));
431
432        // ===================
433        // Evidentiality functions
434        // ===================
435        // Create known evidence (!)
436        self.functions.insert("known".to_string(), func(vec![any.clone()], Type::Evidential {
437            inner: Box::new(any.clone()),
438            evidence: EvidenceLevel::Known,
439        }));
440        // Create uncertain evidence (?)
441        self.functions.insert("uncertain".to_string(), func(vec![any.clone()], Type::Evidential {
442            inner: Box::new(any.clone()),
443            evidence: EvidenceLevel::Uncertain,
444        }));
445        // Create reported evidence (~)
446        self.functions.insert("reported".to_string(), func(vec![any.clone()], Type::Evidential {
447            inner: Box::new(any.clone()),
448            evidence: EvidenceLevel::Reported,
449        }));
450        // Get evidence level as string
451        self.functions.insert("evidence_of".to_string(), func(vec![any.clone()], Type::Str));
452        // Validate reported -> uncertain
453        self.functions.insert("validate".to_string(), func(vec![any.clone()], Type::Evidential {
454            inner: Box::new(any.clone()),
455            evidence: EvidenceLevel::Uncertain,
456        }));
457        // Verify uncertain -> known
458        self.functions.insert("verify".to_string(), func(vec![any.clone()], Type::Evidential {
459            inner: Box::new(any.clone()),
460            evidence: EvidenceLevel::Known,
461        }));
462
463        // ===================
464        // Poly-cultural math (cycles, music theory)
465        // ===================
466        // MIDI note to frequency (A4 = 440Hz)
467        self.functions.insert("freq".to_string(), func(vec![i64_ty.clone()], f64_ty.clone()));
468        // Octave calculation (12-tone equal temperament)
469        self.functions.insert("octave".to_string(), func(vec![i64_ty.clone()], i64_ty.clone()));
470        // Note within octave (0-11)
471        self.functions.insert("pitch_class".to_string(), func(vec![i64_ty.clone()], i64_ty.clone()));
472        // Modular arithmetic (cycles)
473        self.functions.insert("mod_cycle".to_string(), func(vec![i64_ty.clone(), i64_ty.clone()], i64_ty.clone()));
474    }
475
476    /// Fresh type variable
477    fn fresh_var(&mut self) -> Type {
478        let var = TypeVar(self.next_var);
479        self.next_var += 1;
480        Type::Var(var)
481    }
482
483    /// Freshen a type by replacing all type variables with fresh ones
484    /// This is used for polymorphic built-in functions
485    fn freshen(&mut self, ty: &Type) -> Type {
486        let mut mapping = std::collections::HashMap::new();
487        self.freshen_inner(ty, &mut mapping)
488    }
489
490    fn freshen_inner(&mut self, ty: &Type, mapping: &mut std::collections::HashMap<u32, Type>) -> Type {
491        match ty {
492            Type::Var(TypeVar(id)) => {
493                if let Some(fresh) = mapping.get(id) {
494                    fresh.clone()
495                } else {
496                    let fresh = self.fresh_var();
497                    mapping.insert(*id, fresh.clone());
498                    fresh
499                }
500            }
501            Type::Array { element, size } => Type::Array {
502                element: Box::new(self.freshen_inner(element, mapping)),
503                size: *size,
504            },
505            Type::Slice(inner) => Type::Slice(Box::new(self.freshen_inner(inner, mapping))),
506            Type::Ref { mutable, inner } => Type::Ref {
507                mutable: *mutable,
508                inner: Box::new(self.freshen_inner(inner, mapping)),
509            },
510            Type::Tuple(elems) => Type::Tuple(
511                elems.iter().map(|e| self.freshen_inner(e, mapping)).collect()
512            ),
513            Type::Function { params, return_type, is_async } => Type::Function {
514                params: params.iter().map(|p| self.freshen_inner(p, mapping)).collect(),
515                return_type: Box::new(self.freshen_inner(return_type, mapping)),
516                is_async: *is_async,
517            },
518            Type::Evidential { inner, evidence } => Type::Evidential {
519                inner: Box::new(self.freshen_inner(inner, mapping)),
520                evidence: *evidence,
521            },
522            Type::Named { name, generics } => Type::Named {
523                name: name.clone(),
524                generics: generics.iter().map(|g| self.freshen_inner(g, mapping)).collect(),
525            },
526            // Primitive types don't contain type variables
527            _ => ty.clone(),
528        }
529    }
530
531    /// Push a new scope
532    fn push_scope(&mut self) {
533        let new_env = TypeEnv::with_parent(self.env.clone());
534        self.env = Rc::new(RefCell::new(new_env));
535    }
536
537    /// Pop current scope
538    fn pop_scope(&mut self) {
539        let parent = self.env.borrow().parent.clone();
540        if let Some(p) = parent {
541            self.env = p;
542        }
543    }
544
545    /// Record an error
546    fn error(&mut self, err: TypeError) {
547        self.errors.push(err);
548    }
549
550    /// Check if actual evidence can satisfy expected evidence requirement.
551    /// Returns Ok(()) if compatible, Err with helpful message if not.
552    fn check_evidence(
553        &mut self,
554        expected: EvidenceLevel,
555        actual: EvidenceLevel,
556        context: &str,
557    ) -> bool {
558        if actual.satisfies(expected) {
559            true
560        } else {
561            let mut err = TypeError::new(format!(
562                "evidence mismatch {}: expected {} ({}), found {} ({})",
563                context,
564                expected.name(),
565                expected.symbol(),
566                actual.name(),
567                actual.symbol(),
568            ));
569
570            // Add helpful notes based on the specific mismatch
571            match (expected, actual) {
572                (EvidenceLevel::Known, EvidenceLevel::Reported) => {
573                    err = err.with_note(
574                        "reported data (~) cannot be used where known data (!) is required"
575                    );
576                    err = err.with_note(
577                        "help: use |validate!{...} to verify and promote evidence level"
578                    );
579                }
580                (EvidenceLevel::Known, EvidenceLevel::Uncertain) => {
581                    err = err.with_note(
582                        "uncertain data (?) cannot be used where known data (!) is required"
583                    );
584                    err = err.with_note(
585                        "help: use pattern matching or unwrap to handle the uncertainty"
586                    );
587                }
588                (EvidenceLevel::Uncertain, EvidenceLevel::Reported) => {
589                    err = err.with_note(
590                        "reported data (~) cannot be used where uncertain data (?) is required"
591                    );
592                    err = err.with_note(
593                        "help: use |validate?{...} to verify external data"
594                    );
595                }
596                _ => {
597                    err = err.with_note(format!(
598                        "evidence lattice: known (!) < uncertain (?) < reported (~) < paradox (‽)"
599                    ));
600                }
601            }
602
603            self.error(err);
604            false
605        }
606    }
607
608    /// Extract evidence level from a type, defaulting to Known
609    fn get_evidence(&self, ty: &Type) -> EvidenceLevel {
610        match ty {
611            Type::Evidential { evidence, .. } => *evidence,
612            _ => EvidenceLevel::Known,
613        }
614    }
615
616    /// Check a source file
617    pub fn check_file(&mut self, file: &SourceFile) -> Result<(), Vec<TypeError>> {
618        // First pass: collect type definitions
619        for item in &file.items {
620            self.collect_type_def(&item.node);
621        }
622
623        // Second pass: collect function signatures
624        for item in &file.items {
625            self.collect_fn_sig(&item.node);
626        }
627
628        // Third pass: check function bodies
629        for item in &file.items {
630            self.check_item(&item.node);
631        }
632
633        if self.errors.is_empty() {
634            Ok(())
635        } else {
636            Err(std::mem::take(&mut self.errors))
637        }
638    }
639
640    /// Collect type definitions (first pass)
641    fn collect_type_def(&mut self, item: &Item) {
642        match item {
643            Item::Struct(s) => {
644                let generics = s.generics.as_ref()
645                    .map(|g| g.params.iter().filter_map(|p| {
646                        if let GenericParam::Type { name, .. } = p {
647                            Some(name.name.clone())
648                        } else {
649                            None
650                        }
651                    }).collect())
652                    .unwrap_or_default();
653
654                let fields = match &s.fields {
655                    StructFields::Named(fs) => fs.iter()
656                        .map(|f| (f.name.name.clone(), self.convert_type(&f.ty)))
657                        .collect(),
658                    StructFields::Tuple(ts) => ts.iter()
659                        .enumerate()
660                        .map(|(i, t)| (i.to_string(), self.convert_type(t)))
661                        .collect(),
662                    StructFields::Unit => vec![],
663                };
664
665                self.types.insert(s.name.name.clone(), TypeDef::Struct { generics, fields });
666            }
667            Item::Enum(e) => {
668                let generics = e.generics.as_ref()
669                    .map(|g| g.params.iter().filter_map(|p| {
670                        if let GenericParam::Type { name, .. } = p {
671                            Some(name.name.clone())
672                        } else {
673                            None
674                        }
675                    }).collect())
676                    .unwrap_or_default();
677
678                let variants = e.variants.iter()
679                    .map(|v| {
680                        let fields = match &v.fields {
681                            StructFields::Tuple(ts) => Some(ts.iter()
682                                .map(|t| self.convert_type(t))
683                                .collect()),
684                            StructFields::Named(fs) => Some(fs.iter()
685                                .map(|f| self.convert_type(&f.ty))
686                                .collect()),
687                            StructFields::Unit => None,
688                        };
689                        (v.name.name.clone(), fields)
690                    })
691                    .collect();
692
693                self.types.insert(e.name.name.clone(), TypeDef::Enum { generics, variants });
694            }
695            Item::TypeAlias(t) => {
696                let generics = t.generics.as_ref()
697                    .map(|g| g.params.iter().filter_map(|p| {
698                        if let GenericParam::Type { name, .. } = p {
699                            Some(name.name.clone())
700                        } else {
701                            None
702                        }
703                    }).collect())
704                    .unwrap_or_default();
705
706                let target = self.convert_type(&t.ty);
707                self.types.insert(t.name.name.clone(), TypeDef::Alias { generics, target });
708            }
709            _ => {}
710        }
711    }
712
713    /// Collect function signatures (second pass)
714    fn collect_fn_sig(&mut self, item: &Item) {
715        if let Item::Function(f) = item {
716            let params: Vec<Type> = f.params.iter()
717                .map(|p| self.convert_type(&p.ty))
718                .collect();
719
720            let return_type = f.return_type.as_ref()
721                .map(|t| self.convert_type(t))
722                .unwrap_or(Type::Unit);
723
724            let fn_type = Type::Function {
725                params,
726                return_type: Box::new(return_type),
727                is_async: f.is_async,
728            };
729
730            self.functions.insert(f.name.name.clone(), fn_type);
731        }
732    }
733
734    /// Check an item (third pass)
735    fn check_item(&mut self, item: &Item) {
736        match item {
737            Item::Function(f) => self.check_function(f),
738            Item::Const(c) => {
739                let declared = self.convert_type(&c.ty);
740                let inferred = self.infer_expr(&c.value);
741                if !self.unify(&declared, &inferred) {
742                    self.error(TypeError::new(format!(
743                        "type mismatch in const '{}': expected {:?}, found {:?}",
744                        c.name.name, declared, inferred
745                    )).with_span(c.name.span));
746                }
747            }
748            Item::Static(s) => {
749                let declared = self.convert_type(&s.ty);
750                let inferred = self.infer_expr(&s.value);
751                if !self.unify(&declared, &inferred) {
752                    self.error(TypeError::new(format!(
753                        "type mismatch in static '{}': expected {:?}, found {:?}",
754                        s.name.name, declared, inferred
755                    )).with_span(s.name.span));
756                }
757            }
758            _ => {}
759        }
760    }
761
762    /// Check a function body
763    fn check_function(&mut self, func: &Function) {
764        self.push_scope();
765
766        // Bind parameters
767        for param in &func.params {
768            let ty = self.convert_type(&param.ty);
769            let evidence = param.pattern
770                .evidentiality()
771                .map(EvidenceLevel::from_ast)
772                .unwrap_or(EvidenceLevel::Known);
773
774            if let Some(name) = param.pattern.binding_name() {
775                self.env.borrow_mut().define(name, ty, evidence);
776            }
777        }
778
779        // Check body
780        if let Some(ref body) = func.body {
781            let body_type = self.check_block(body);
782
783            // Check return type
784            let expected_return = func.return_type.as_ref()
785                .map(|t| self.convert_type(t))
786                .unwrap_or(Type::Unit);
787
788            // Check structural type compatibility
789            if !self.unify(&expected_return, &body_type) {
790                self.error(TypeError::new(format!(
791                    "return type mismatch in '{}': expected {:?}, found {:?}",
792                    func.name.name, expected_return, body_type
793                )).with_span(func.name.span));
794            }
795
796            // Check evidence compatibility for return
797            let expected_evidence = self.get_evidence(&expected_return);
798            let actual_evidence = self.get_evidence(&body_type);
799            self.check_evidence(
800                expected_evidence,
801                actual_evidence,
802                &format!("in return type of '{}'", func.name.name),
803            );
804        }
805
806        self.pop_scope();
807    }
808
809    /// Check a block and return its type
810    fn check_block(&mut self, block: &Block) -> Type {
811        self.push_scope();
812
813        let mut diverges = false;
814        for stmt in &block.stmts {
815            let stmt_ty = self.check_stmt(stmt);
816            if matches!(stmt_ty, Type::Never) {
817                diverges = true;
818            }
819        }
820
821        let result = if let Some(ref expr) = block.expr {
822            self.infer_expr(expr)
823        } else if diverges {
824            Type::Never
825        } else {
826            Type::Unit
827        };
828
829        self.pop_scope();
830        result
831    }
832
833    /// Check a statement and return its type (Never if it diverges)
834    fn check_stmt(&mut self, stmt: &Stmt) -> Type {
835        match stmt {
836            Stmt::Let { pattern, ty, init } => {
837                let declared_ty = ty.as_ref().map(|t| self.convert_type(t));
838                let init_ty = init.as_ref().map(|e| self.infer_expr(e));
839
840                let final_ty = match (declared_ty, init_ty) {
841                    (Some(d), Some(i)) => {
842                        if !self.unify(&d, &i) {
843                            self.error(TypeError::new(format!(
844                                "type mismatch in let binding: expected {:?}, found {:?}",
845                                d, i
846                            )));
847                        }
848                        d
849                    }
850                    (Some(d), None) => d,
851                    (None, Some(i)) => i,
852                    (None, None) => self.fresh_var(),
853                };
854
855                let evidence = pattern
856                    .evidentiality()
857                    .map(EvidenceLevel::from_ast)
858                    .unwrap_or(EvidenceLevel::Known);
859
860                if let Some(name) = pattern.binding_name() {
861                    self.env.borrow_mut().define(name, final_ty, evidence);
862                }
863                Type::Unit
864            }
865            Stmt::Expr(e) | Stmt::Semi(e) => {
866                self.infer_expr(e)
867            }
868            Stmt::Item(item) => {
869                self.check_item(item);
870                Type::Unit
871            }
872        }
873    }
874
875    /// Infer the type of an expression
876    pub fn infer_expr(&mut self, expr: &Expr) -> Type {
877        match expr {
878            Expr::Literal(lit) => self.infer_literal(lit),
879
880            Expr::Path(path) => {
881                if path.segments.len() == 1 {
882                    let name = &path.segments[0].ident.name;
883                    if let Some((ty, _)) = self.env.borrow().lookup(name) {
884                        return ty;
885                    }
886                    if let Some(ty) = self.functions.get(name).cloned() {
887                        // Freshen polymorphic types to get fresh type variables
888                        return self.freshen(&ty);
889                    }
890                }
891                self.error(TypeError::new(format!("undefined: {:?}", path)));
892                Type::Error
893            }
894
895            Expr::Binary { left, op, right } => {
896                let lt = self.infer_expr(left);
897                let rt = self.infer_expr(right);
898                self.infer_binary_op(op, &lt, &rt)
899            }
900
901            Expr::Unary { op, expr } => {
902                let inner = self.infer_expr(expr);
903                self.infer_unary_op(op, &inner)
904            }
905
906            Expr::Call { func, args } => {
907                let fn_type = self.infer_expr(func);
908                let arg_types: Vec<Type> = args.iter()
909                    .map(|a| self.infer_expr(a))
910                    .collect();
911
912                if let Type::Function { params, return_type, .. } = fn_type {
913                    // Check argument count
914                    if params.len() != arg_types.len() {
915                        self.error(TypeError::new(format!(
916                            "expected {} arguments, found {}",
917                            params.len(), arg_types.len()
918                        )));
919                    }
920
921                    // Check argument types and evidence levels
922                    for (i, (param, arg)) in params.iter().zip(arg_types.iter()).enumerate() {
923                        // First check structural type compatibility
924                        if !self.unify(param, arg) {
925                            self.error(TypeError::new(format!(
926                                "argument type mismatch: expected {:?}, found {:?}",
927                                param, arg
928                            )));
929                        }
930
931                        // Check evidence compatibility only for non-polymorphic parameters.
932                        // Type variables (used in polymorphic functions like print, len, etc.)
933                        // accept arguments of any evidence level.
934                        if !matches!(param, Type::Var(_)) {
935                            let expected_evidence = self.get_evidence(param);
936                            let actual_evidence = self.get_evidence(arg);
937                            self.check_evidence(
938                                expected_evidence,
939                                actual_evidence,
940                                &format!("in argument {}", i + 1),
941                            );
942                        }
943                    }
944
945                    *return_type
946                } else {
947                    self.error(TypeError::new("cannot call non-function"));
948                    Type::Error
949                }
950            }
951
952            Expr::Array(elements) => {
953                if elements.is_empty() {
954                    Type::Array {
955                        element: Box::new(self.fresh_var()),
956                        size: Some(0),
957                    }
958                } else {
959                    let elem_ty = self.infer_expr(&elements[0]);
960                    for elem in &elements[1..] {
961                        let t = self.infer_expr(elem);
962                        if !self.unify(&elem_ty, &t) {
963                            self.error(TypeError::new("array elements must have same type"));
964                        }
965                    }
966                    Type::Array {
967                        element: Box::new(elem_ty),
968                        size: Some(elements.len()),
969                    }
970                }
971            }
972
973            Expr::Tuple(elements) => {
974                Type::Tuple(elements.iter().map(|e| self.infer_expr(e)).collect())
975            }
976
977            Expr::Block(block) => self.check_block(block),
978
979            Expr::If { condition, then_branch, else_branch } => {
980                let cond_ty = self.infer_expr(condition);
981                if !self.unify(&Type::Bool, &cond_ty) {
982                    self.error(TypeError::new("if condition must be bool"));
983                }
984
985                let then_ty = self.check_block(then_branch);
986
987                if let Some(else_expr) = else_branch {
988                    // Else branch can be another expr (e.g., if-else chain) or a block
989                    let else_ty = match else_expr.as_ref() {
990                        Expr::Block(block) => self.check_block(block),
991                        other => self.infer_expr(other),
992                    };
993                    if !self.unify(&then_ty, &else_ty) {
994                        self.error(TypeError::new("if branches must have same type"));
995                    }
996                    then_ty
997                } else {
998                    Type::Unit
999                }
1000            }
1001
1002            Expr::Pipe { expr, operations } => {
1003                let mut current = self.infer_expr(expr);
1004
1005                for op in operations {
1006                    current = self.infer_pipe_op(op, &current);
1007                }
1008
1009                current
1010            }
1011
1012            Expr::Index { expr, index } => {
1013                let coll_ty = self.infer_expr(expr);
1014                let idx_ty = self.infer_expr(index);
1015
1016                match coll_ty {
1017                    Type::Array { element, .. } | Type::Slice(element) => {
1018                        if !matches!(idx_ty, Type::Int(_)) {
1019                            self.error(TypeError::new("index must be integer"));
1020                        }
1021                        *element
1022                    }
1023                    _ => {
1024                        self.error(TypeError::new("cannot index non-array"));
1025                        Type::Error
1026                    }
1027                }
1028            }
1029
1030            Expr::Return(val) => {
1031                if let Some(e) = val {
1032                    self.infer_expr(e);
1033                }
1034                Type::Never
1035            }
1036
1037            // Mark expression with evidence
1038            Expr::Evidential { expr, evidentiality } => {
1039                let inner = self.infer_expr(expr);
1040                Type::Evidential {
1041                    inner: Box::new(inner),
1042                    evidence: EvidenceLevel::from_ast(*evidentiality),
1043                }
1044            }
1045
1046            _ => {
1047                // Handle other expression types
1048                self.fresh_var()
1049            }
1050        }
1051    }
1052
1053    /// Infer type from literal
1054    fn infer_literal(&self, lit: &Literal) -> Type {
1055        match lit {
1056            Literal::Int { .. } => Type::Int(IntSize::I64),
1057            Literal::Float { .. } => Type::Float(FloatSize::F64),
1058            Literal::Bool(_) => Type::Bool,
1059            Literal::Char(_) => Type::Char,
1060            Literal::String(_) => Type::Str,
1061            Literal::MultiLineString(_) => Type::Str,
1062            Literal::RawString(_) => Type::Str,
1063            Literal::ByteString(bytes) => Type::Array {
1064                element: Box::new(Type::Int(IntSize::U8)),
1065                size: Some(bytes.len()),
1066            },
1067            Literal::InterpolatedString { .. } => Type::Str,
1068            Literal::SigilStringSql(_) => Type::Str,
1069            Literal::SigilStringRoute(_) => Type::Str,
1070            Literal::Null => Type::Unit,  // null has unit type
1071            Literal::Empty => Type::Unit,
1072            Literal::Infinity => Type::Float(FloatSize::F64),
1073            Literal::Circle => Type::Float(FloatSize::F64),
1074        }
1075    }
1076
1077    /// Infer type of binary operation
1078    fn infer_binary_op(&mut self, op: &BinOp, left: &Type, right: &Type) -> Type {
1079        // Extract evidence levels for propagation
1080        let (left_inner, left_ev) = self.strip_evidence(left);
1081        let (right_inner, right_ev) = self.strip_evidence(right);
1082
1083        let result_ty = match op {
1084            // Arithmetic: numeric -> numeric
1085            BinOp::Add | BinOp::Sub | BinOp::Mul | BinOp::Div |
1086            BinOp::Rem | BinOp::Pow => {
1087                if !self.unify(&left_inner, &right_inner) {
1088                    self.error(TypeError::new("arithmetic operands must have same type"));
1089                }
1090                left_inner
1091            }
1092
1093            // Comparison: any -> bool
1094            BinOp::Eq | BinOp::Ne | BinOp::Lt | BinOp::Le |
1095            BinOp::Gt | BinOp::Ge => {
1096                if !self.unify(&left_inner, &right_inner) {
1097                    self.error(TypeError::new("comparison operands must have same type"));
1098                }
1099                Type::Bool
1100            }
1101
1102            // Logical: bool -> bool
1103            BinOp::And | BinOp::Or => {
1104                if !self.unify(&Type::Bool, &left_inner) {
1105                    self.error(TypeError::new("logical operand must be bool"));
1106                }
1107                if !self.unify(&Type::Bool, &right_inner) {
1108                    self.error(TypeError::new("logical operand must be bool"));
1109                }
1110                Type::Bool
1111            }
1112
1113            // Bitwise: int -> int
1114            BinOp::BitAnd | BinOp::BitOr | BinOp::BitXor |
1115            BinOp::Shl | BinOp::Shr => {
1116                left_inner
1117            }
1118
1119            // String concatenation
1120            BinOp::Concat => {
1121                if !self.unify(&Type::Str, &left_inner) {
1122                    self.error(TypeError::new("concat operand must be string"));
1123                }
1124                Type::Str
1125            }
1126        };
1127
1128        // Combine evidence levels
1129        let combined_ev = left_ev.join(right_ev);
1130
1131        // Wrap result in evidence if either operand had evidence
1132        if combined_ev > EvidenceLevel::Known {
1133            Type::Evidential {
1134                inner: Box::new(result_ty),
1135                evidence: combined_ev,
1136            }
1137        } else {
1138            result_ty
1139        }
1140    }
1141
1142    /// Infer type of unary operation
1143    fn infer_unary_op(&mut self, op: &UnaryOp, inner: &Type) -> Type {
1144        let (inner_ty, evidence) = self.strip_evidence(inner);
1145
1146        let result = match op {
1147            UnaryOp::Neg => inner_ty,
1148            UnaryOp::Not => {
1149                if !self.unify(&Type::Bool, &inner_ty) {
1150                    self.error(TypeError::new("! operand must be bool"));
1151                }
1152                Type::Bool
1153            }
1154            UnaryOp::Ref => Type::Ref { mutable: false, inner: Box::new(inner_ty) },
1155            UnaryOp::RefMut => Type::Ref { mutable: true, inner: Box::new(inner_ty) },
1156            UnaryOp::Deref => {
1157                if let Type::Ref { inner, .. } | Type::Ptr { inner, .. } = inner_ty {
1158                    *inner
1159                } else {
1160                    self.error(TypeError::new("cannot dereference non-pointer"));
1161                    Type::Error
1162                }
1163            }
1164        };
1165
1166        // Preserve evidence
1167        if evidence > EvidenceLevel::Known {
1168            Type::Evidential {
1169                inner: Box::new(result),
1170                evidence,
1171            }
1172        } else {
1173            result
1174        }
1175    }
1176
1177    /// Infer type of pipe operation
1178    fn infer_pipe_op(&mut self, op: &PipeOp, input: &Type) -> Type {
1179        let (inner, evidence) = self.strip_evidence(input);
1180
1181        let result = match op {
1182            // Transform: [T] -> [U] where body: T -> U
1183            PipeOp::Transform(_body) => {
1184                if let Type::Array { element, size } = inner {
1185                    Type::Array { element, size }
1186                } else if let Type::Slice(element) = inner {
1187                    Type::Slice(element)
1188                } else {
1189                    self.error(TypeError::new("transform requires array or slice"));
1190                    Type::Error
1191                }
1192            }
1193
1194            // Filter: [T] -> [T]
1195            PipeOp::Filter(_pred) => inner,
1196
1197            // Sort: [T] -> [T]
1198            PipeOp::Sort(_) => inner,
1199
1200            // Reduce: [T] -> T
1201            PipeOp::Reduce(_) => {
1202                if let Type::Array { element, .. } | Type::Slice(element) = inner {
1203                    *element
1204                } else {
1205                    self.error(TypeError::new("reduce requires array or slice"));
1206                    Type::Error
1207                }
1208            }
1209
1210            // Method call
1211            PipeOp::Method { name, args: _ } => {
1212                // Look up method
1213                if let Some(fn_ty) = self.functions.get(&name.name).cloned() {
1214                    // Freshen to get fresh type variables for polymorphic functions
1215                    let fresh_ty = self.freshen(&fn_ty);
1216                    if let Type::Function { return_type, .. } = fresh_ty {
1217                        *return_type
1218                    } else {
1219                        Type::Error
1220                    }
1221                } else {
1222                    // Could be a method on the type
1223                    self.fresh_var()
1224                }
1225            }
1226
1227            // Named operation (morpheme)
1228            PipeOp::Named { prefix, body: _ } => {
1229                // Named operations like |sum, |product
1230                if let Some(first) = prefix.first() {
1231                    match first.name.as_str() {
1232                        "sum" | "product" => {
1233                            if let Type::Array { element, .. } | Type::Slice(element) = inner {
1234                                *element
1235                            } else {
1236                                self.error(TypeError::new("sum/product requires array"));
1237                                Type::Error
1238                            }
1239                        }
1240                        _ => self.fresh_var(),
1241                    }
1242                } else {
1243                    self.fresh_var()
1244                }
1245            }
1246
1247            // Await: unwrap future
1248            PipeOp::Await => {
1249                // Future<T> -> T
1250                inner
1251            }
1252
1253            // Access morphemes: [T] -> T (return element type)
1254            PipeOp::First | PipeOp::Last | PipeOp::Middle |
1255            PipeOp::Choice | PipeOp::Nth(_) | PipeOp::Next => {
1256                if let Type::Array { element, .. } | Type::Slice(element) = inner {
1257                    *element
1258                } else if let Type::Tuple(elements) = inner {
1259                    // For tuple, return Any since elements might be different types
1260                    if let Some(first) = elements.first() {
1261                        first.clone()
1262                    } else {
1263                        Type::Unit
1264                    }
1265                } else {
1266                    self.error(TypeError::new("access morpheme requires array, slice, or tuple"));
1267                    Type::Error
1268                }
1269            }
1270
1271            // Parallel morpheme: ∥ - wraps another operation
1272            // Type is determined by the inner operation
1273            PipeOp::Parallel(inner_op) => {
1274                self.infer_pipe_op(inner_op, input)
1275            }
1276
1277            // GPU morpheme: ⊛ - wraps another operation for GPU execution
1278            // Type is determined by the inner operation
1279            PipeOp::Gpu(inner_op) => {
1280                self.infer_pipe_op(inner_op, input)
1281            }
1282
1283            // ==========================================
1284            // Protocol Operations - Sigil-native networking
1285            // All protocol results have Reported evidentiality
1286            // ==========================================
1287
1288            // Send: connection -> response (with Reported evidence)
1289            PipeOp::Send(_) => {
1290                // Returns response object with Reported evidentiality
1291                Type::Evidential {
1292                    inner: Box::new(self.fresh_var()),
1293                    evidence: EvidenceLevel::Reported,
1294                }
1295            }
1296
1297            // Recv: connection -> data (with Reported evidence)
1298            PipeOp::Recv => {
1299                // Returns received data with Reported evidentiality
1300                Type::Evidential {
1301                    inner: Box::new(self.fresh_var()),
1302                    evidence: EvidenceLevel::Reported,
1303                }
1304            }
1305
1306            // Stream: connection -> Stream<T> (elements have Reported evidence)
1307            PipeOp::Stream(_) => {
1308                // Returns a stream type
1309                self.fresh_var()
1310            }
1311
1312            // Connect: url/config -> connection
1313            PipeOp::Connect(_) => {
1314                // Returns connection object
1315                self.fresh_var()
1316            }
1317
1318            // Close: connection -> ()
1319            PipeOp::Close => Type::Unit,
1320
1321            // Header: request -> request (adds header)
1322            PipeOp::Header { .. } => inner,
1323
1324            // Body: request -> request (sets body)
1325            PipeOp::Body(_) => inner,
1326
1327            // Timeout: request -> request (sets timeout)
1328            PipeOp::Timeout(_) => inner,
1329
1330            // Retry: request -> request (sets retry policy)
1331            PipeOp::Retry { .. } => inner,
1332        };
1333
1334        // Preserve evidence through pipe
1335        if evidence > EvidenceLevel::Known {
1336            Type::Evidential {
1337                inner: Box::new(result),
1338                evidence,
1339            }
1340        } else {
1341            result
1342        }
1343    }
1344
1345    /// Strip evidence wrapper, returning (inner_type, evidence_level)
1346    fn strip_evidence(&self, ty: &Type) -> (Type, EvidenceLevel) {
1347        match ty {
1348            Type::Evidential { inner, evidence } => (*inner.clone(), *evidence),
1349            _ => (ty.clone(), EvidenceLevel::Known),
1350        }
1351    }
1352
1353    /// Attempt to unify two types
1354    fn unify(&mut self, a: &Type, b: &Type) -> bool {
1355        match (a, b) {
1356            // Same types
1357            (Type::Unit, Type::Unit) |
1358            (Type::Bool, Type::Bool) |
1359            (Type::Char, Type::Char) |
1360            (Type::Str, Type::Str) |
1361            (Type::Never, Type::Never) |
1362            (Type::Error, _) |
1363            (_, Type::Error) |
1364            // Never (bottom type) unifies with anything
1365            (Type::Never, _) |
1366            (_, Type::Never) => true,
1367
1368            (Type::Int(a), Type::Int(b)) => a == b,
1369            (Type::Float(a), Type::Float(b)) => a == b,
1370
1371            // Arrays
1372            (Type::Array { element: a, size: sa }, Type::Array { element: b, size: sb }) => {
1373                (sa == sb || sa.is_none() || sb.is_none()) && self.unify(a, b)
1374            }
1375
1376            // Slices
1377            (Type::Slice(a), Type::Slice(b)) => self.unify(a, b),
1378
1379            // Tuples
1380            (Type::Tuple(a), Type::Tuple(b)) if a.len() == b.len() => {
1381                a.iter().zip(b.iter()).all(|(x, y)| self.unify(x, y))
1382            }
1383
1384            // References
1385            (Type::Ref { mutable: ma, inner: a }, Type::Ref { mutable: mb, inner: b }) => {
1386                ma == mb && self.unify(a, b)
1387            }
1388
1389            // Functions
1390            (Type::Function { params: pa, return_type: ra, is_async: aa },
1391             Type::Function { params: pb, return_type: rb, is_async: ab }) => {
1392                aa == ab && pa.len() == pb.len() &&
1393                pa.iter().zip(pb.iter()).all(|(x, y)| self.unify(x, y)) &&
1394                self.unify(ra, rb)
1395            }
1396
1397            // Named types
1398            (Type::Named { name: na, generics: ga }, Type::Named { name: nb, generics: gb }) => {
1399                na == nb && ga.len() == gb.len() &&
1400                ga.iter().zip(gb.iter()).all(|(x, y)| self.unify(x, y))
1401            }
1402
1403            // Evidential types: inner must unify, evidence can differ
1404            (Type::Evidential { inner: a, .. }, Type::Evidential { inner: b, .. }) => {
1405                self.unify(a, b)
1406            }
1407            (Type::Evidential { inner: a, .. }, b) => {
1408                self.unify(a, b)
1409            }
1410            (a, Type::Evidential { inner: b, .. }) => {
1411                self.unify(a, b)
1412            }
1413
1414            // Type variables
1415            (Type::Var(v), t) => {
1416                if let Some(resolved) = self.substitutions.get(v) {
1417                    let resolved = resolved.clone();
1418                    self.unify(&resolved, t)
1419                } else {
1420                    self.substitutions.insert(*v, t.clone());
1421                    true
1422                }
1423            }
1424            (t, Type::Var(v)) => {
1425                if let Some(resolved) = self.substitutions.get(v) {
1426                    let resolved = resolved.clone();
1427                    self.unify(t, &resolved)
1428                } else {
1429                    self.substitutions.insert(*v, t.clone());
1430                    true
1431                }
1432            }
1433
1434            // Cycles
1435            (Type::Cycle { modulus: a }, Type::Cycle { modulus: b }) => a == b,
1436
1437            _ => false,
1438        }
1439    }
1440
1441    /// Convert AST type to internal type
1442    fn convert_type(&self, ty: &TypeExpr) -> Type {
1443        match ty {
1444            TypeExpr::Path(path) => {
1445                if path.segments.len() == 1 {
1446                    let name = &path.segments[0].ident.name;
1447                    match name.as_str() {
1448                        "bool" => return Type::Bool,
1449                        "char" => return Type::Char,
1450                        "str" | "String" => return Type::Str,
1451                        "i8" => return Type::Int(IntSize::I8),
1452                        "i16" => return Type::Int(IntSize::I16),
1453                        "i32" => return Type::Int(IntSize::I32),
1454                        "i64" => return Type::Int(IntSize::I64),
1455                        "i128" => return Type::Int(IntSize::I128),
1456                        "isize" => return Type::Int(IntSize::ISize),
1457                        "u8" => return Type::Int(IntSize::U8),
1458                        "u16" => return Type::Int(IntSize::U16),
1459                        "u32" => return Type::Int(IntSize::U32),
1460                        "u64" => return Type::Int(IntSize::U64),
1461                        "u128" => return Type::Int(IntSize::U128),
1462                        "usize" => return Type::Int(IntSize::USize),
1463                        "f32" => return Type::Float(FloatSize::F32),
1464                        "f64" => return Type::Float(FloatSize::F64),
1465                        _ => {}
1466                    }
1467                }
1468
1469                let name = path.segments.iter()
1470                    .map(|s| s.ident.name.clone())
1471                    .collect::<Vec<_>>()
1472                    .join("::");
1473
1474                let generics = path.segments.last()
1475                    .and_then(|s| s.generics.as_ref())
1476                    .map(|gs| gs.iter().map(|t| self.convert_type(t)).collect())
1477                    .unwrap_or_default();
1478
1479                Type::Named { name, generics }
1480            }
1481
1482            TypeExpr::Reference { mutable, inner } => {
1483                Type::Ref {
1484                    mutable: *mutable,
1485                    inner: Box::new(self.convert_type(inner)),
1486                }
1487            }
1488
1489            TypeExpr::Pointer { mutable, inner } => {
1490                Type::Ptr {
1491                    mutable: *mutable,
1492                    inner: Box::new(self.convert_type(inner)),
1493                }
1494            }
1495
1496            TypeExpr::Array { element, size: _ } => {
1497                Type::Array {
1498                    element: Box::new(self.convert_type(element)),
1499                    size: None, // Could evaluate const expr
1500                }
1501            }
1502
1503            TypeExpr::Slice(inner) => {
1504                Type::Slice(Box::new(self.convert_type(inner)))
1505            }
1506
1507            TypeExpr::Tuple(elements) => {
1508                Type::Tuple(elements.iter().map(|t| self.convert_type(t)).collect())
1509            }
1510
1511            TypeExpr::Function { params, return_type } => {
1512                Type::Function {
1513                    params: params.iter().map(|t| self.convert_type(t)).collect(),
1514                    return_type: Box::new(
1515                        return_type.as_ref()
1516                            .map(|t| self.convert_type(t))
1517                            .unwrap_or(Type::Unit)
1518                    ),
1519                    is_async: false,
1520                }
1521            }
1522
1523            TypeExpr::Evidential { inner, evidentiality } => {
1524                Type::Evidential {
1525                    inner: Box::new(self.convert_type(inner)),
1526                    evidence: EvidenceLevel::from_ast(*evidentiality),
1527                }
1528            }
1529
1530            TypeExpr::Cycle { modulus: _ } => {
1531                Type::Cycle { modulus: 12 } // Default, should evaluate
1532            }
1533
1534            TypeExpr::Simd { element, lanes } => {
1535                let elem_ty = self.convert_type(element);
1536                Type::Simd {
1537                    element: Box::new(elem_ty),
1538                    lanes: *lanes,
1539                }
1540            }
1541
1542            TypeExpr::Atomic(inner) => {
1543                let inner_ty = self.convert_type(inner);
1544                Type::Atomic(Box::new(inner_ty))
1545            }
1546
1547            TypeExpr::Never => Type::Never,
1548            TypeExpr::Infer => Type::Var(TypeVar(0)), // Fresh var
1549        }
1550    }
1551
1552    /// Get errors
1553    pub fn errors(&self) -> &[TypeError] {
1554        &self.errors
1555    }
1556}
1557
1558impl Default for TypeChecker {
1559    fn default() -> Self {
1560        Self::new()
1561    }
1562}
1563
1564// Helper trait for Pattern
1565trait PatternExt {
1566    fn evidentiality(&self) -> Option<Evidentiality>;
1567    fn binding_name(&self) -> Option<String>;
1568}
1569
1570impl PatternExt for Pattern {
1571    fn evidentiality(&self) -> Option<Evidentiality> {
1572        match self {
1573            Pattern::Ident { evidentiality, .. } => *evidentiality,
1574            _ => None,
1575        }
1576    }
1577
1578    fn binding_name(&self) -> Option<String> {
1579        match self {
1580            Pattern::Ident { name, .. } => Some(name.name.clone()),
1581            _ => None,
1582        }
1583    }
1584}
1585
1586impl fmt::Display for Type {
1587    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1588        match self {
1589            Type::Unit => write!(f, "()"),
1590            Type::Bool => write!(f, "bool"),
1591            Type::Int(size) => write!(f, "{:?}", size),
1592            Type::Float(size) => write!(f, "{:?}", size),
1593            Type::Char => write!(f, "char"),
1594            Type::Str => write!(f, "str"),
1595            Type::Array { element, size } => {
1596                if let Some(n) = size {
1597                    write!(f, "[{}; {}]", element, n)
1598                } else {
1599                    write!(f, "[{}]", element)
1600                }
1601            }
1602            Type::Slice(inner) => write!(f, "[{}]", inner),
1603            Type::Tuple(elems) => {
1604                write!(f, "(")?;
1605                for (i, e) in elems.iter().enumerate() {
1606                    if i > 0 { write!(f, ", ")?; }
1607                    write!(f, "{}", e)?;
1608                }
1609                write!(f, ")")
1610            }
1611            Type::Named { name, generics } => {
1612                write!(f, "{}", name)?;
1613                if !generics.is_empty() {
1614                    write!(f, "<")?;
1615                    for (i, g) in generics.iter().enumerate() {
1616                        if i > 0 { write!(f, ", ")?; }
1617                        write!(f, "{}", g)?;
1618                    }
1619                    write!(f, ">")?;
1620                }
1621                Ok(())
1622            }
1623            Type::Function { params, return_type, is_async } => {
1624                if *is_async { write!(f, "async ")?; }
1625                write!(f, "fn(")?;
1626                for (i, p) in params.iter().enumerate() {
1627                    if i > 0 { write!(f, ", ")?; }
1628                    write!(f, "{}", p)?;
1629                }
1630                write!(f, ") -> {}", return_type)
1631            }
1632            Type::Ref { mutable, inner } => {
1633                write!(f, "&{}{}", if *mutable { "mut " } else { "" }, inner)
1634            }
1635            Type::Ptr { mutable, inner } => {
1636                write!(f, "*{}{}", if *mutable { "mut " } else { "const " }, inner)
1637            }
1638            Type::Evidential { inner, evidence } => {
1639                write!(f, "{}{}", inner, evidence.symbol())
1640            }
1641            Type::Cycle { modulus } => write!(f, "Cycle<{}>", modulus),
1642            Type::Var(v) => write!(f, "?{}", v.0),
1643            Type::Error => write!(f, "<error>"),
1644            Type::Never => write!(f, "!"),
1645            Type::Simd { element, lanes } => write!(f, "simd<{}, {}>", element, lanes),
1646            Type::Atomic(inner) => write!(f, "atomic<{}>", inner),
1647        }
1648    }
1649}
1650
1651#[cfg(test)]
1652mod tests {
1653    use super::*;
1654    use crate::Parser;
1655
1656    fn check(source: &str) -> Result<(), Vec<TypeError>> {
1657        let mut parser = Parser::new(source);
1658        let file = parser.parse_file().expect("parse failed");
1659        let mut checker = TypeChecker::new();
1660        checker.check_file(&file)
1661    }
1662
1663    #[test]
1664    fn test_basic_types() {
1665        assert!(check("fn main() { let x: i64 = 42; }").is_ok());
1666        assert!(check("fn main() { let x: bool = true; }").is_ok());
1667        assert!(check("fn main() { let x: f64 = 3.14; }").is_ok());
1668    }
1669
1670    #[test]
1671    fn test_type_mismatch() {
1672        assert!(check("fn main() { let x: bool = 42; }").is_err());
1673    }
1674
1675    #[test]
1676    fn test_evidence_propagation() {
1677        // Evidence should propagate through operations
1678        assert!(check(r#"
1679            fn main() {
1680                let known: i64! = 42;
1681                let uncertain: i64? = 10;
1682                let result = known + uncertain;
1683            }
1684        "#).is_ok());
1685    }
1686
1687    #[test]
1688    fn test_function_return() {
1689        let result = check(r#"
1690            fn add(a: i64, b: i64) -> i64 {
1691                return a + b;
1692            }
1693            fn main() {
1694                let x = add(1, 2);
1695            }
1696        "#);
1697        if let Err(errors) = &result {
1698            for e in errors {
1699                eprintln!("Error: {}", e);
1700            }
1701        }
1702        assert!(result.is_ok());
1703    }
1704
1705    #[test]
1706    fn test_array_types() {
1707        assert!(check(r#"
1708            fn main() {
1709                let arr = [1, 2, 3];
1710                let x = arr[0];
1711            }
1712        "#).is_ok());
1713    }
1714}
sigil_parser/typeck.rs

sigil_parser/
typeck.rs
