aver/types/
mod.rs

1/// Aver static type representation and built-in type namespaces.
2///
3/// Type annotations in the AST are plain strings; this module converts them
4/// to a structured enum and provides the compatibility relation used by
5/// the type checker.
6///
7/// Sub-modules:
8/// - `checker` — static type checker
9/// - `bool`, `int`, `float`, `string`, `list`, `map`, `char`, `byte` — pure namespace helpers (no effects)
10pub mod bool;
11pub mod branch_path;
12pub mod byte;
13pub mod char;
14pub mod checker;
15pub mod effect_event;
16pub mod float;
17pub mod int;
18#[cfg(feature = "runtime")]
19pub mod list;
20#[cfg(feature = "runtime")]
21pub mod map;
22pub mod option;
23pub mod result;
24#[cfg(feature = "runtime")]
25pub mod string;
26pub mod trace;
27#[cfg(feature = "runtime")]
28pub mod vector;
29
30#[derive(Debug, Clone, PartialEq)]
31pub enum Type {
32    Int,
33    Float,
34    Str,
35    Bool,
36    Unit,
37    Result(Box<Type>, Box<Type>),
38    Option(Box<Type>),
39    List(Box<Type>),
40    Tuple(Vec<Type>),
41    Map(Box<Type>, Box<Type>),
42    Vector(Box<Type>),
43    Fn(Vec<Type>, Box<Type>, Vec<String>),
44    Unknown,       // internal fallback when checker cannot infer a precise type
45    Named(String), // user-defined type: Shape, User, etc.
46}
47
48impl Type {
49    /// `a.compatible(b)` — can a value of type `self` be used where `other` is expected?
50    /// `Unknown` is compatible with everything (internal fallback).
51    /// Two concrete types must be equal (structurally) to be compatible.
52    pub fn compatible(&self, other: &Type) -> bool {
53        if matches!(self, Type::Unknown) || matches!(other, Type::Unknown) {
54            return true;
55        }
56        match (self, other) {
57            (Type::Int, Type::Int) => true,
58            (Type::Float, Type::Float) => true,
59            (Type::Str, Type::Str) => true,
60            (Type::Bool, Type::Bool) => true,
61            (Type::Unit, Type::Unit) => true,
62            (Type::Result(a1, b1), Type::Result(a2, b2)) => a1.compatible(a2) && b1.compatible(b2),
63            (Type::Option(a), Type::Option(b)) => a.compatible(b),
64            (Type::List(a), Type::List(b)) => a.compatible(b),
65            (Type::Tuple(a), Type::Tuple(b)) => {
66                a.len() == b.len() && a.iter().zip(b.iter()).all(|(x, y)| x.compatible(y))
67            }
68            (Type::Map(k1, v1), Type::Map(k2, v2)) => k1.compatible(k2) && v1.compatible(v2),
69            (Type::Vector(a), Type::Vector(b)) => a.compatible(b),
70            (Type::Fn(p1, r1, e1), Type::Fn(p2, r2, e2)) => {
71                p1.len() == p2.len()
72                    && p1.iter().zip(p2.iter()).all(|(a, b)| a.compatible(b))
73                    && r1.compatible(r2)
74                    && e1.iter().all(|actual| {
75                        e2.iter()
76                            .any(|expected| crate::effects::effect_satisfies(expected, actual))
77                    })
78            }
79            (Type::Named(a), Type::Named(b)) => {
80                a == b || a.ends_with(&format!(".{}", b)) || b.ends_with(&format!(".{}", a))
81            }
82            _ => false,
83        }
84    }
85
86    pub fn display(&self) -> String {
87        match self {
88            Type::Int => "Int".to_string(),
89            Type::Float => "Float".to_string(),
90            Type::Str => "String".to_string(),
91            Type::Bool => "Bool".to_string(),
92            Type::Unit => "Unit".to_string(),
93            Type::Result(ok, err) => format!("Result<{}, {}>", ok.display(), err.display()),
94            Type::Option(inner) => format!("Option<{}>", inner.display()),
95            Type::List(inner) => format!("List<{}>", inner.display()),
96            Type::Tuple(items) => format!(
97                "({})",
98                items
99                    .iter()
100                    .map(Type::display)
101                    .collect::<Vec<_>>()
102                    .join(", ")
103            ),
104            Type::Map(key, value) => format!("Map<{}, {}>", key.display(), value.display()),
105            Type::Vector(inner) => format!("Vector<{}>", inner.display()),
106            Type::Fn(params, ret, effects) => {
107                let ps: Vec<String> = params.iter().map(|p| p.display()).collect();
108                if effects.is_empty() {
109                    format!("Fn({}) -> {}", ps.join(", "), ret.display())
110                } else {
111                    format!(
112                        "Fn({}) -> {} ! [{}]",
113                        ps.join(", "),
114                        ret.display(),
115                        effects.join(", ")
116                    )
117                }
118            }
119            Type::Unknown => "Unknown".to_string(),
120            Type::Named(n) => n.clone(),
121        }
122    }
123}
124
125/// Parse a type annotation string strictly.
126/// Returns `Err(unknown_name)` if the string is a non-empty identifier
127/// that does not map to a known type (i.e. a likely typo).
128/// Generic forms (`Result<...>`, `Option<...>`, `List<...>`) with valid inner types are accepted.
129pub fn parse_type_str_strict(s: &str) -> Result<Type, String> {
130    let s = s.trim();
131    if s.is_empty() || s == "Any" {
132        return Err(s.to_string());
133    }
134    if let Some(fn_ty) = parse_fn_type_strict(s)? {
135        return Ok(fn_ty);
136    }
137
138    if s.starts_with('(') && s.ends_with(')') {
139        let inner = &s[1..s.len() - 1];
140        let parts = split_top_level(inner, ',')?;
141        if parts.len() < 2 {
142            return Err(s.to_string());
143        }
144        let elems = parts
145            .into_iter()
146            .map(parse_type_str_strict)
147            .collect::<Result<Vec<_>, _>>()?;
148        return Ok(Type::Tuple(elems));
149    }
150
151    match s {
152        "Int" => Ok(Type::Int),
153        "Float" => Ok(Type::Float),
154        "String" | "Str" => Ok(Type::Str),
155        "Bool" => Ok(Type::Bool),
156        "Unit" => Ok(Type::Unit),
157        _ => {
158            if let Some(inner) = strip_wrapper(s, "Result<", ">") {
159                if let Some((ok_s, err_s)) = split_top_level_comma(inner) {
160                    let ok_ty = parse_type_str_strict(ok_s)?;
161                    let err_ty = parse_type_str_strict(err_s)?;
162                    return Ok(Type::Result(Box::new(ok_ty), Box::new(err_ty)));
163                }
164                return Err(s.to_string());
165            }
166            if let Some(inner) = strip_wrapper(s, "Option<", ">") {
167                let inner_ty = parse_type_str_strict(inner)?;
168                return Ok(Type::Option(Box::new(inner_ty)));
169            }
170            if let Some(inner) = strip_wrapper(s, "List<", ">") {
171                let inner_ty = parse_type_str_strict(inner)?;
172                return Ok(Type::List(Box::new(inner_ty)));
173            }
174            if let Some(inner) = strip_wrapper(s, "Map<", ">") {
175                if let Some((key_s, value_s)) = split_top_level_comma(inner) {
176                    let key_ty = parse_type_str_strict(key_s)?;
177                    if matches!(key_ty, Type::Fn(..) | Type::Unit) {
178                        return Err(s.to_string());
179                    }
180                    let value_ty = parse_type_str_strict(value_s)?;
181                    return Ok(Type::Map(Box::new(key_ty), Box::new(value_ty)));
182                }
183                return Err(s.to_string());
184            }
185            if let Some(inner) = strip_wrapper(s, "Vector<", ">") {
186                let inner_ty = parse_type_str_strict(inner)?;
187                return Ok(Type::Vector(Box::new(inner_ty)));
188            }
189
190            // Capitalized identifier with only alphanumeric/_ and dot chars = user-defined type name
191            // Supports dotted names like "Tcp.Connection"
192            if s.chars().next().is_some_and(|c| c.is_uppercase())
193                && s.chars()
194                    .all(|c| c.is_alphanumeric() || c == '_' || c == '.')
195            {
196                return Ok(Type::Named(s.to_string()));
197            }
198
199            Err(s.to_string())
200        }
201    }
202}
203
204/// Parse an Aver type annotation string into a `Type`.
205/// Returns `Type::Unknown` for unknown identifiers (internal fallback).
206/// Prefer `parse_type_str_strict` for user-facing type annotations.
207pub fn parse_type_str(s: &str) -> Type {
208    let s = s.trim();
209    if s.starts_with("Fn(") {
210        if let Ok(Some(fn_ty)) = parse_fn_type_strict(s) {
211            return fn_ty;
212        }
213        return Type::Unknown;
214    }
215    if s.starts_with('(') && s.ends_with(')') {
216        let inner = &s[1..s.len() - 1];
217        if let Ok(parts) = split_top_level(inner, ',')
218            && parts.len() >= 2
219        {
220            return Type::Tuple(parts.into_iter().map(parse_type_str).collect());
221        }
222        return Type::Unknown;
223    }
224    match s {
225        "Int" => Type::Int,
226        "Float" => Type::Float,
227        "String" | "Str" => Type::Str,
228        "Bool" => Type::Bool,
229        "Unit" => Type::Unit,
230        "" => Type::Unknown,
231        _ => {
232            // Try generic forms: Result<A, B>, Option<A>, List<A>
233            if let Some(inner) = strip_wrapper(s, "Result<", ">") {
234                // Split on the first top-level comma
235                if let Some((ok_str, err_str)) = split_top_level_comma(inner) {
236                    return Type::Result(
237                        Box::new(parse_type_str(ok_str)),
238                        Box::new(parse_type_str(err_str)),
239                    );
240                }
241            }
242            if let Some(inner) = strip_wrapper(s, "Option<", ">") {
243                return Type::Option(Box::new(parse_type_str(inner)));
244            }
245            if let Some(inner) = strip_wrapper(s, "List<", ">") {
246                return Type::List(Box::new(parse_type_str(inner)));
247            }
248            if let Some(inner) = strip_wrapper(s, "Map<", ">")
249                && let Some((key_str, value_str)) = split_top_level_comma(inner)
250            {
251                return Type::Map(
252                    Box::new(parse_type_str(key_str)),
253                    Box::new(parse_type_str(value_str)),
254                );
255            }
256            if let Some(inner) = strip_wrapper(s, "Vector<", ">") {
257                return Type::Vector(Box::new(parse_type_str(inner)));
258            }
259            // Capitalized identifier with only alphanumeric/_ and dot chars = user-defined type
260            // Supports dotted names like "Tcp.Connection"
261            if s.chars().next().is_some_and(|c| c.is_uppercase())
262                && s.chars()
263                    .all(|c| c.is_alphanumeric() || c == '_' || c == '.')
264                && s != "Any"
265            {
266                return Type::Named(s.to_string());
267            }
268            // Unknown — internal fallback
269            Type::Unknown
270        }
271    }
272}
273
274fn parse_fn_type_strict(s: &str) -> Result<Option<Type>, String> {
275    if !s.starts_with("Fn(") {
276        return Ok(None);
277    }
278
279    let close_idx = find_matching_paren(s, 2).ok_or_else(|| s.to_string())?;
280    let params_src = &s[3..close_idx];
281
282    let after_params = s[close_idx + 1..].trim_start();
283    if !after_params.starts_with("->") {
284        return Err(s.to_string());
285    }
286    let ret_and_effects = after_params[2..].trim();
287    if ret_and_effects.is_empty() {
288        return Err(s.to_string());
289    }
290
291    let (ret_src, effects) = split_fn_effects_suffix(ret_and_effects)?;
292    let ret_ty = parse_type_str_strict(ret_src)?;
293    let params = parse_type_list_strict(params_src)?;
294    Ok(Some(Type::Fn(params, Box::new(ret_ty), effects)))
295}
296
297fn parse_type_list_strict(src: &str) -> Result<Vec<Type>, String> {
298    if src.trim().is_empty() {
299        return Ok(vec![]);
300    }
301    split_top_level(src, ',')?
302        .into_iter()
303        .map(|part| {
304            let part = part.trim();
305            if part.is_empty() {
306                Err(src.to_string())
307            } else {
308                parse_type_str_strict(part)
309            }
310        })
311        .collect()
312}
313
314fn split_fn_effects_suffix(src: &str) -> Result<(&str, Vec<String>), String> {
315    if let Some(bang_idx) = find_top_level_bang(src) {
316        let ret_src = src[..bang_idx].trim();
317        if ret_src.is_empty() {
318            return Err(src.to_string());
319        }
320        let effects_src = src[bang_idx + 1..].trim();
321        if !(effects_src.starts_with('[') && effects_src.ends_with(']')) {
322            return Err(src.to_string());
323        }
324        let inner = &effects_src[1..effects_src.len() - 1];
325        let effects = if inner.trim().is_empty() {
326            vec![]
327        } else {
328            split_top_level(inner, ',')?
329                .into_iter()
330                .map(|part| {
331                    let name = part.trim();
332                    if name.is_empty() {
333                        Err(src.to_string())
334                    } else {
335                        Ok(name.to_string())
336                    }
337                })
338                .collect::<Result<Vec<_>, _>>()?
339        };
340        Ok((ret_src, effects))
341    } else {
342        Ok((src.trim(), vec![]))
343    }
344}
345
346fn find_matching_paren(s: &str, open_idx: usize) -> Option<usize> {
347    if s.as_bytes().get(open_idx).copied() != Some(b'(') {
348        return None;
349    }
350    let mut depth = 1usize;
351    for (i, ch) in s.char_indices().skip(open_idx + 1) {
352        match ch {
353            '(' => depth += 1,
354            ')' => {
355                depth -= 1;
356                if depth == 0 {
357                    return Some(i);
358                }
359            }
360            _ => {}
361        }
362    }
363    None
364}
365
366fn find_top_level_bang(s: &str) -> Option<usize> {
367    let mut angle = 0usize;
368    let mut paren = 0usize;
369    let mut bracket = 0usize;
370
371    for (i, ch) in s.char_indices() {
372        match ch {
373            '<' => angle += 1,
374            '>' => angle = angle.saturating_sub(1),
375            '(' => paren += 1,
376            ')' => paren = paren.saturating_sub(1),
377            '[' => bracket += 1,
378            ']' => bracket = bracket.saturating_sub(1),
379            '!' if angle == 0 && paren == 0 && bracket == 0 => return Some(i),
380            _ => {}
381        }
382    }
383
384    None
385}
386
387fn split_top_level(s: &str, delimiter: char) -> Result<Vec<&str>, String> {
388    let mut out = Vec::new();
389    let mut start = 0usize;
390    let mut angle = 0usize;
391    let mut paren = 0usize;
392    let mut bracket = 0usize;
393
394    for (i, ch) in s.char_indices() {
395        match ch {
396            '<' => angle += 1,
397            '>' => {
398                if angle == 0 {
399                    return Err(s.to_string());
400                }
401                angle -= 1;
402            }
403            '(' => paren += 1,
404            ')' => {
405                if paren == 0 {
406                    return Err(s.to_string());
407                }
408                paren -= 1;
409            }
410            '[' => bracket += 1,
411            ']' => {
412                if bracket == 0 {
413                    return Err(s.to_string());
414                }
415                bracket -= 1;
416            }
417            _ if ch == delimiter && angle == 0 && paren == 0 && bracket == 0 => {
418                out.push(&s[start..i]);
419                start = i + ch.len_utf8();
420            }
421            _ => {}
422        }
423    }
424
425    if angle != 0 || paren != 0 || bracket != 0 {
426        return Err(s.to_string());
427    }
428    out.push(&s[start..]);
429    Ok(out)
430}
431
432/// If `s` starts with `prefix` and ends with `suffix`, return the middle part.
433fn strip_wrapper<'a>(s: &'a str, prefix: &str, suffix: &str) -> Option<&'a str> {
434    if s.starts_with(prefix) && s.ends_with(suffix) {
435        let inner = &s[prefix.len()..s.len() - suffix.len()];
436        Some(inner)
437    } else {
438        None
439    }
440}
441
442/// Split a string on the first top-level comma (depth=0), returning the two sides.
443fn split_top_level_comma(s: &str) -> Option<(&str, &str)> {
444    let mut angle = 0usize;
445    let mut paren = 0usize;
446    let mut bracket = 0usize;
447    for (i, ch) in s.char_indices() {
448        match ch {
449            '<' => angle += 1,
450            '>' => angle = angle.saturating_sub(1),
451            '(' => paren += 1,
452            ')' => paren = paren.saturating_sub(1),
453            '[' => bracket += 1,
454            ']' => bracket = bracket.saturating_sub(1),
455            ',' if angle == 0 && paren == 0 && bracket == 0 => {
456                return Some((&s[..i], &s[i + 1..]));
457            }
458            _ => {}
459        }
460    }
461    None
462}
463
464#[cfg(test)]
465mod tests {
466    use super::*;
467
468    #[test]
469    fn test_primitives() {
470        assert_eq!(parse_type_str("Int"), Type::Int);
471        assert_eq!(parse_type_str("Float"), Type::Float);
472        assert_eq!(parse_type_str("String"), Type::Str);
473        assert_eq!(parse_type_str("Bool"), Type::Bool);
474        assert_eq!(parse_type_str("Unit"), Type::Unit);
475    }
476
477    #[test]
478    fn test_generics() {
479        assert_eq!(
480            parse_type_str("Result<Int, String>"),
481            Type::Result(Box::new(Type::Int), Box::new(Type::Str))
482        );
483        assert_eq!(
484            parse_type_str("Option<Bool>"),
485            Type::Option(Box::new(Type::Bool))
486        );
487        assert_eq!(parse_type_str("List<Int>"), Type::List(Box::new(Type::Int)));
488        assert_eq!(
489            parse_type_str("Map<String, Int>"),
490            Type::Map(Box::new(Type::Str), Box::new(Type::Int))
491        );
492        assert_eq!(
493            parse_type_str("(Int, String)"),
494            Type::Tuple(vec![Type::Int, Type::Str])
495        );
496    }
497
498    #[test]
499    fn test_nested() {
500        assert_eq!(
501            parse_type_str("Result<Float, String>"),
502            Type::Result(Box::new(Type::Float), Box::new(Type::Str))
503        );
504    }
505
506    #[test]
507    fn test_unknown() {
508        // Capitalized identifiers are now parsed as user-defined Named types
509        assert_eq!(
510            parse_type_str("SomeUnknownType"),
511            Type::Named("SomeUnknownType".to_string())
512        );
513        // Lowercase non-keyword identifiers and empty strings become Unknown fallback
514        assert_eq!(parse_type_str(""), Type::Unknown);
515    }
516
517    #[test]
518    fn test_compatible() {
519        assert!(Type::Int.compatible(&Type::Int));
520        assert!(!Type::Int.compatible(&Type::Str));
521        assert!(Type::Unknown.compatible(&Type::Int));
522        assert!(Type::Int.compatible(&Type::Unknown));
523        assert!(!Type::Int.compatible(&Type::Float)); // no implicit widening
524        assert!(
525            Type::Result(Box::new(Type::Int), Box::new(Type::Str))
526                .compatible(&Type::Result(Box::new(Type::Int), Box::new(Type::Str)))
527        );
528        assert!(
529            Type::Map(Box::new(Type::Str), Box::new(Type::Int))
530                .compatible(&Type::Map(Box::new(Type::Str), Box::new(Type::Int)))
531        );
532        assert!(
533            !Type::Map(Box::new(Type::Str), Box::new(Type::Int))
534                .compatible(&Type::Map(Box::new(Type::Int), Box::new(Type::Int)))
535        );
536    }
537
538    #[test]
539    fn test_function_type_parsing() {
540        assert_eq!(
541            parse_type_str_strict("Fn(Int, String) -> Bool").unwrap(),
542            Type::Fn(vec![Type::Int, Type::Str], Box::new(Type::Bool), vec![])
543        );
544        assert_eq!(
545            parse_type_str_strict("Fn(Int) -> Int ! [Console]").unwrap(),
546            Type::Fn(
547                vec![Type::Int],
548                Box::new(Type::Int),
549                vec!["Console".to_string()]
550            )
551        );
552    }
553
554    #[test]
555    fn test_function_effect_compatibility_subset() {
556        let pure = Type::Fn(vec![Type::Int], Box::new(Type::Int), vec![]);
557        let console = Type::Fn(
558            vec![Type::Int],
559            Box::new(Type::Int),
560            vec!["Console".to_string()],
561        );
562
563        assert!(pure.compatible(&console));
564        assert!(!console.compatible(&pure));
565
566        let child = Type::Fn(
567            vec![Type::Int],
568            Box::new(Type::Int),
569            vec!["Http.get".to_string()],
570        );
571        let parent = Type::Fn(
572            vec![Type::Int],
573            Box::new(Type::Int),
574            vec!["Http".to_string()],
575        );
576        // Http.get fits where Http is expected (subset of namespace)
577        assert!(child.compatible(&parent));
578        // Http does NOT fit where Http.get is expected (might use Http.post)
579        assert!(!parent.compatible(&child));
580    }
581
582    #[test]
583    fn test_strict_parser_accepts_valid_generics() {
584        assert_eq!(
585            parse_type_str_strict("Result<Int, String>").unwrap(),
586            Type::Result(Box::new(Type::Int), Box::new(Type::Str))
587        );
588        assert_eq!(
589            parse_type_str_strict("List<Option<Float>>").unwrap(),
590            Type::List(Box::new(Type::Option(Box::new(Type::Float))))
591        );
592        assert_eq!(
593            parse_type_str_strict("Map<String, Int>").unwrap(),
594            Type::Map(Box::new(Type::Str), Box::new(Type::Int))
595        );
596        assert_eq!(
597            parse_type_str_strict("(Int, String)").unwrap(),
598            Type::Tuple(vec![Type::Int, Type::Str])
599        );
600    }
601
602    #[test]
603    fn test_strict_parser_accepts_user_defined_types() {
604        // Capitalized identifiers are accepted as user-defined Named types
605        assert_eq!(
606            parse_type_str_strict("Result<MyError, String>").unwrap(),
607            Type::Result(
608                Box::new(Type::Named("MyError".to_string())),
609                Box::new(Type::Str)
610            )
611        );
612        assert_eq!(
613            parse_type_str_strict("Option<Shape>").unwrap(),
614            Type::Option(Box::new(Type::Named("Shape".to_string())))
615        );
616        assert_eq!(
617            parse_type_str_strict("List<User>").unwrap(),
618            Type::List(Box::new(Type::Named("User".to_string())))
619        );
620        // Lowercase unknown types still fail
621        assert!(parse_type_str_strict("integ").is_err());
622    }
623
624    #[test]
625    fn test_dotted_named_type() {
626        assert_eq!(
627            parse_type_str("Tcp.Connection"),
628            Type::Named("Tcp.Connection".to_string())
629        );
630        assert_eq!(
631            parse_type_str_strict("Tcp.Connection").unwrap(),
632            Type::Named("Tcp.Connection".to_string())
633        );
634        assert_eq!(
635            parse_type_str_strict("Result<Tcp.Connection, String>").unwrap(),
636            Type::Result(
637                Box::new(Type::Named("Tcp.Connection".to_string())),
638                Box::new(Type::Str)
639            )
640        );
641    }
642
643    #[test]
644    fn test_strict_parser_rejects_malformed_generics() {
645        assert!(parse_type_str_strict("Result<Int>").is_err());
646        assert!(parse_type_str_strict("Option<Int, String>").is_err());
647        assert!(parse_type_str_strict("Map<Int>").is_err());
648        // List/User-type keys are now valid — HAMT runtime hashes deeply.
649        assert!(parse_type_str_strict("Map<List<Int>, String>").is_ok());
650        // Functions still cannot be hashed.
651        assert!(parse_type_str_strict("Map<Fn(Int) -> Int, String>").is_err());
652        assert!(parse_type_str_strict("(Int)").is_err());
653        assert!(parse_type_str_strict("Fn(Int) Int").is_err());
654        assert!(parse_type_str_strict("Fn(Int) -> ! [Console]").is_err());
655    }
656}
aver/types/mod.rs

aver/types/
mod.rs
