Semantic Analysis

Status: Complete (Phase 1) Crate: compiler/semantic-analysis Entry Point: pub fn type_check(items: &[Item]) -> Result<Vec<Warning>, Vec<TypeError>>

Overview

The semantic analysis feature slice performs type checking and semantic validation on the AST produced by the parser. It ensures type safety, validates variable and function scoping, and provides comprehensive error reporting with source location information.

Architecture

This slice follows the Vertical Slice Architecture pattern:

• Dependencies: ast-types (AST types), shared-types (common values)
• Public API: Single entry point (type_check)
• Public types: Type enum (semantic type representation), TypeError enum
• Internal implementation: Type checker logic is pub(crate)

Features

Type System (Phase 1)

The Type Lattice

Type (see types.rs) covers:

• Integers: I8, I16, I32, I64, U8, U16, U32, U64
• Floats: F16, BF16, F32, F64
• Other scalars: Bool, Char (a 32-bit Unicode scalar, ordered and castable, but not arithmetic), String, Void
• Nominal user types: Struct(name), Enum(name), Newtype(name), two values share a type only when the names match. A monomorphized generic is an ordinary nominal type with a mangled name, which is what keeps generics invisible to everything downstream
• Compound: Array { element, size } (length is part of the type), Tuple, Reference { inner, mutable }, Function { params, ret }, DynObject (a &dyn Trait receiver)
• Unknown: the error-recovery type. It is compatible with everything, so one reported error does not cascade into a second. Divergent expressions, panic, unreachable, and an if/match arm that returns, breaks, or continues, carry it for the same reason: they never produce a value, so they must not constrain the arms that do

Type Compatibility

There are no implicit conversions: compatibility is name-and-shape equality, with as the only widening or narrowing mechanism. Unknown is the single exception, and is compatible in both directions.

Semantic Checks

1. Type Checking

Expression type checking:

• Literals have their default types (i32, f64, bool)
• Identifiers lookup their declared type
• Binary operators check operand types and return result type
• Unary operators validate operand types
• Function calls check argument types and count

Statement type checking:

• Variable declarations validate initializer type matches declared type
• Return statements check return value matches function signature
• If/else conditions must be boolean
• Expression statements validate expression types

2. Scope Validation

Lexical scoping with shadowing support:

• Global scope for functions
• Function-level scope for parameters and local variables
• Block scope for if/else statements
• Inner scopes can shadow outer scopes

Example:

1func test() -> i32 {2    val x: i32 = 1       // Outer scope3    if true {4        val x: i32 = 2   // Shadows outer x (allowed)5        return x         // Returns 26    }7    return x             // Returns 18}

3. Function Signature Validation

• Parameter types must be resolved
• Return type must match all return statements
• Function names must be unique (no overloading in Phase 1)
• Forward references are supported

4. Variable Declaration Validation

• Variables must have a type (explicit or inferred)
• Variables cannot be used before declaration
• Variable names must be unique in scope
• Uninitialized variables require explicit type annotation

Usage

Basic Type Checking

1use syntax_parsing::parse;2use semantic_analysis::type_check;3 4let source = r#"5    func add(a: i32, b: i32) -> i32 {6        return a + b7    }8"#;9 10let ast = parse(source)?;11match type_check(&ast) {12    Ok(()) => println!("✓ Program is type-correct"),13    Err(errors) => {14        for error in errors {15            eprintln!("Type error: {}", error);16        }17    }18}

Error Collection

The type checker uses a fail-slow approach, collecting all errors:

1let source = r#"2    func bad() -> i32 {3        val x: i32 = true    // Error 1: type mismatch4        return undefined_var  // Error 2: undefined variable5    }6"#;7 8let ast = parse(source).unwrap();9let errors = type_check(&ast).unwrap_err();10 11assert_eq!(errors.len(), 2);12// Both errors are reported

Error Types

Every diagnostic is a TypeError variant carrying the span of the offending expression or item; the checker collects them and keeps going, so one run reports every error it finds. The set is large (core mismatches and undefined names; mutability; generics, turbofish, and trait bounds; Copy/Drop/operator-trait rules; control flow) and grows with each feature, so this document does not reproduce it. The authoritative list, with its user-facing messages, is compiler/semantic-analysis/src/errors.rs.

Implementation Details

Type Checker State

The checker holds a scope stack of bindings (each with its type, mutability, and move state), maps of registered functions, structs, methods, traits, generic enums, and newtypes, the accumulated TypeError and Warning lists, and per-function context (return type, loop depth) for validation. Field-level detail belongs to type_checkers/mod.rs; a pasted copy here would only drift.

The symbol table tracks lexical scopes plus ownership: whether a binding still owns its value, which is what drives use-after-move detection in type_checkers/moves.rs.

Type Inference (Simple)

Phase 1 supports basic type inference:

1val x = 42        // Inferred as i322val y = 3.14      // Inferred as f643val z = true      // Inferred as bool4 5val a: i32 = 42   // Explicit type (checked)

No inference for:

• Function parameters (must be explicit)
• Function return types (must be explicit)
• Uninitialized variables (must have explicit type)

Testing

Test categories:

• Positive tests: Valid programs that should type check
• Negative tests: Invalid programs with specific error types
• Scoping tests: Variable shadowing, nested scopes
• Function tests: Calls, signatures, parameter type checking
• Operator tests: Binary/unary operators with various types
• Control flow tests: If/else with different types

Example test:

1#[test]2fn error_type_mismatch() {3    let source = r#"func test() -> i32 {4        val x: i32 = true5        return x6    }"#;7 8    let items = syntax_parsing::parse(source).unwrap();9    let result = type_check(&items);10 11    assert!(result.is_err());12    let errors = result.unwrap_err();13    assert!(errors.iter().any(|e| matches!(e, TypeError::Mismatch { .. })));14}

Design Decisions

Fail-Slow Error Collection

Why collect all errors?

• Better developer experience
• See all issues at once
• No need to fix-compile-repeat cycle

Implementation:

• Type checker continues after errors
• Uses Unknown type for error recovery
• Returns all collected errors at end

Strict Type System (Phase 1)

No implicit conversions:

1val x: i64 = 42  // Error: expected i64, found i32

Why:

• Simplicity for Phase 1
• Predictable behavior
• Easy to add explicit conversions later

Lexical Scoping with Shadowing

Why allow shadowing?

• Functional programming pattern
• Useful for local scope redefinition
• Prevents accidental name clashes

Example:

1val x = 12if condition {3    val x = 2  // New variable, shadows outer x4}

Type Checking Algorithm

Multi-Pass Algorithm

check_program walks the item list several times. Each pass registers only what the next one needs, which is what makes declaration order irrelevant. Passes are lettered where a later requirement was slotted between two existing ones.

Pass 2 registers each method under a mangled key, see Method Name Mangling below.

The ordering guarantees that all type names are known before any signature is read, and all signatures are known before any body is checked, which is what enables forward references, mutual recursion, and definition-order independence.

Method Name Mangling

Methods live in the same flat function table as free functions, keyed by StructName__methodName. __ is reserved as the compiler's symbol separator: the backend recovers a method's receiver struct by splitting its symbol on __, so no generated name may introduce a second __.

Two consequences:

• Monomorphized instance names use a single-underscore marker, _g_ for a generic struct instance (Pair_g_i32_f64) and for a generic function instance (identity_g_i32), never __.
• User-declared identifiers may not contain __. A declaration that does is rejected with TypeError::ReservedNameSeparator, which keeps a user method from ever colliding with a generated instance or vtable-thunk symbol.

Expression Type Checking

1fn check_expr(&mut self, expr: &Expr) -> Result<Type, ()> {2    match expr {3        Expr::Literal(lit, _) => infer_literal_type(lit),4        Expr::Identifier(ident) => self.symbols.lookup(&ident.name),5        Expr::Binary { left, op, right, .. } => {6            let left_ty = self.check_expr(left)?;7            let right_ty = self.check_expr(right)?;8            validate_binary_op(op, left_ty, right_ty)9        }10        // ... other cases11    }12}

API Reference

Public Functions

1/// Type check a Neuro program, returning the lint warnings it collected2pub fn type_check(items: &[Item]) -> Result<Vec<Warning>, Vec<TypeError>>

Public Types

1pub enum Type { ... }2pub enum TypeError { ... }

Integration Points

Upstream Dependencies

• syntax-parsing: AST types (Item, Expr, Stmt, etc.)
• shared-types: Common types (Span, Identifier, Literal)

Downstream Consumers

• llvm-backend: Uses Type for code generation
• neurc: Reports type errors to user
• LSP server (Phase 8): Type information for IDE features

Examples

Type Checking Success

1func factorial(n: i32) -> i32 {2    if n <= 1 {3        return 14    } else {5        return n * factorial(n - 1)6    }7}

Type check: Pass

• n has type i32
• n <= 1 returns bool (valid condition)
• factorial(n - 1) recursive call type checks
• All return statements return i32

Type Checking Errors

1func bad_example() -> i32 {2    val x = "hello"      // x has type string3    return x + 1         // Error: can't add string and i324}

Errors:

1. TypeError::InvalidBinaryOperator: Cannot apply + to string and i32

Future Enhancements

Open checker items

Phase 1 (Core Language) is complete: structs, methods, arrays, tuples, as conversions, the borrow checker, enums and pattern matching, generics, traits, and dispatch have all landed. See the Quick Roadmap for the phase now open. What the checker still owes:

• Generic type arguments beyond Copy: type arguments are Copy-restricted, and a generic may not be instantiated with an enclosing type parameter
• A never type: divergence is modelled with Unknown today, which is compatible with everything by design; a dedicated bottom type would let the checker distinguish "diverges" from "unknown because an error was already reported"

Phase 2: Tensor Types

• Static tensor types: Tensor<f32, [3, 3]> resolves to Type::Tensor { element, shape }; the element is restricted to a fixed-width scalar and the type is non-Copy
• Tensor construction: a nested array literal coerces under a tensor annotation, and the Tensor::<T, [...]>::… constructors are resolved against the turbofish or the surrounding expectation — see the slice's CONTEXT.md for the rules and diagnostics
• Tensor ownership: .clone() (nullary, auto-derefs a borrow, moves nothing) and .to(device) (one Device argument, consumes the receiver, value receivers only) resolve as intrinsics on a tensor receiver
• Shape checking beyond identity: broadcasting and shape generics; today two tensors match only when their elements and every extent are equal
• Broadcasting: NumPy-style broadcasting rules

Troubleshooting

"Type mismatch" errors

Problem: Types don't match expectations

Solution:

• Check variable and function type annotations
• Ensure return type matches all return statements
• Verify operator operand types are compatible

"Undefined variable" errors

Problem: Variable not in scope

Solution:

• Check variable is declared before use
• Verify variable name spelling
• Check scope (variable may be in different block)

"Argument count mismatch" errors

Problem: Wrong number of function arguments

Solution:

• Check function signature
• Ensure all required arguments are provided
• Verify no extra arguments

Performance

• Type checking speed: <1ms for small programs
• Memory: O(n) for symbol table
• Body checking: one traversal per body, after the registration passes; the registration passes themselves are linear scans over the item list

References

• Type Systems
• Bidirectional Type Checking
• Source: compiler/semantic-analysis/src/lib.rs