0%

Section 2: Complete Type Inference

Goal: Full Hindley-Milner type inference

SPEC: spec/08-types.md, spec/09-properties-of-types.md

Status: Complete — Full Hindley-Milner inference with actionable type error messages. 744 Rust tests in ori_types (all pass), ~97 active Ori spec tests across inference/bindings/lambdas (all pass; collections.ori is entirely commented out), all 61 compile-fail test files pass including 5 conversion hint tests (int(x), float(x), str(x), byte(x), [x]). Verified 2026-03-29 (compile-fail count re).

2.1 Unification Algorithm

  • Implement: Occurs check — spec/08-types.md § Type Inference

    • Rust Tests: ori_types/src/unify/tests.rs — occurs_check_detects_infinite_type (prevents T = [T])
    • Ori Tests: tests/spec/inference/unification.ori — 25 tests (all pass)
    • Semantic pin: occurs_check_detects_infinite_type

  • Implement: Substitution application via resolve() — spec/08-types.md § Type Inference

    • Rust Tests: ori_types/src/unify/tests.rs — path_compression, error_propagates, never_unifies_with_anything
    • Ori Tests: tests/spec/inference/unification.ori — substitution verified through unification tests
    • Semantic pin: path_compression

  • Implement: Generalization (let-polymorphism) — spec/08-types.md § Type Inference

    • Rust Tests: ori_types/src/unify/tests.rs — generalize_identity_function, generalize_monomorphic, generalize_does_not_generalize_outer_vars, let_polymorphism_example, generalize_finds_vars_in_borrowed (7 total)
    • Ori Tests: tests/spec/inference/polymorphism.ori — 8 tests (all pass)
    • Verified: Polymorphic identity @id (x) = x works with both int and str
    • Semantic pin: let_polymorphism_example

  • Implement: Instantiation — spec/08-types.md § Type Inference

    • Rust Tests: ori_types/src/unify/tests.rs — instantiate_identity_scheme, instantiate_non_scheme, instantiate_twice_gives_different_vars
    • Ori Tests: tests/spec/inference/polymorphism.ori
    • Semantic pin: instantiate_twice_gives_different_vars

2.2 Expression Type Inference

  • Implement: Local variable inference — spec/08-types.md § Type Inference

    • Rust Tests: ori_types/src/infer/ — 183 inference-related tests
    • Ori Tests: tests/spec/expressions/bindings.ori — 17 tests (all pass)
    • Verified: let x = 42 infers int, let x = x + 1 chains correctly
    • Matrix: 9 types (int, str, bool, float, char, struct, nested struct, [int], (int,str)) / 7 patterns (inferred, annotated, shadow, struct destructure, list destructure, tuple destructure, nested destructure)

  • Implement: Lambda parameter inference — spec/08-types.md § Type Inference

    • Rust Tests: ori_types/src/infer/expr.rs — lambda inference tests
    • Ori Tests: tests/spec/expressions/lambdas.ori — 30 tests (all pass)
    • Verified: apply(x -> x + 1, 41) correctly infers x: int from context
    • Matrix: 10+ patterns (simple, multi-param, no-param, typed, closures, IIFE, HOF, currying, conditional, complex body)

  • Fix: Closure-returning-closure inference bug

    • (n: int) -> (int) -> int = { (x: int) -> int = base + n + x } — both annotated and unannotated patterns pass. test_aot_closure_capturing_closure in AOT and test_closure_returning_closure_annotated in spec both pass.
    • Dual-execution verified (interpreter + LLVM AOT)
    • Semantic pin: test_closure_returning_closure_annotated

  • Implement: Generic type argument inference — spec/08-types.md § Type Inference

    • Rust Tests: ori_types/src/infer/ — generic inference tests
    • Ori Tests: tests/spec/inference/generics.ori — 17 active tests (all pass)
    • Cleanup: Remove 5 orphan stub functions (infer_option_map, infer_option_and_then, infer_result_map, infer_result_map_err, infer_result_unwrap_or) that return constants without assertions — dead code inflating test counts
    • Semantic pin: test_infer_option_in_result

  • Implement: Collection element type inference — spec/08-types.md § Type Inference

    • Rust Tests: ori_types/src/infer/expr.rs — collection inference tests
    • Ori Tests: tests/spec/types/collections.ori — STALE TEST (blocked-by bug-tracker/plans/BUG-02-039/): file is entirely commented out (0/33 active tests). Collection inference is tested indirectly via unification.ori and generics.ori. Reactivation owned by BUG-02-039.
    • Verified: [1, 2, 3] infers [int], {"a": 1} infers {str: int} (verified through other test files)

2.3 Type Error Improvements

Compile-fail test harness: Implemented via #compile_fail("expected_error") attribute. All 61 compile-fail test files pass: cargo run -p oric --bin ori -- test tests/compile-fail/ (count updated 2026-06-07)

  • Implement: Expected vs found messages — spec/08-types.md § Type Errors WEAK TESTS

    • Rust Tests: ori_types/src/ — 20+ type error tests
    • Ori Tests: tests/compile-fail/type_mismatch_arg.ori — 1 test (passes)
    • WEAK TESTS: single compile-fail scenario (str->int argument mismatch). No matrix of type pairs. Rust unit tests compensate.
    • Improve: Add compile-fail tests for more type pairs (int->str, bool->int, struct->primitive, etc.)

  • Implement: Type conversion hints — spec/08-types.md § Type Errors

    • Implement: Edit-distance typo suggestions (“did you mean?”)
    • Rust Tests: ori_types/src/infer/env.rs — 21 tests including edit distance for typo suggestions
    • Ori Tests: tests/compile-fail/type_hints.ori — 5 non-skipped tests pass
    • Implement: Conversion function suggestions in type mismatch errors (int(x), float(x), str(x), byte(x), [x])
    • Ori Tests: tests/compile-fail/type_hints.ori — 5 compile_fail tests pass (float->int, int->float, int->str, str->byte, int->[int])

  • Implement: Source location in errors — spec/08-types.md § Type Errors WEAK TESTS

    • Ori Tests: tests/compile-fail/return_type_mismatch.ori — 1 test (passes)
    • Verified: All type errors include span information
    • WEAK TESTS: single scenario, does not verify span accuracy (only tests that the error is produced)

  • Cleanup: Standardize compile-fail syntax — type_mismatch_arg.ori and return_type_mismatch.ori use old #[compile_fail("...")] (square brackets) while type_hints.ori uses #compile_fail("...") (no brackets). Both work but should be consistent.

2.4 Section Completion Checklist

Exit Criteria Met: Complete type inference with error messages and hints.

  • All 2.1 items complete — unification, occurs check, generalization, instantiation
  • All 2.2 items complete — local variable, lambda, generic, collection inference — closure-returning-closure bug fixed
  • All 2.3 items complete — expected/found, hints, source locations
  • 744 Rust unit tests pass (ori_types)(2026-02-10, count updated 2026-03-29)
  • Spec and compile-fail tests pass — ~97 active Ori spec tests + 61 compile-fail files(2026-02-10, counts updated 2026-06-07)
  • Run full test suite: ./test-all.sh — all pass
  • /tpr-review passed — independent Codex review found no critical or major issues (or all findings triaged)
  • /impl-hygiene-review passed — implementation hygiene review clean (phase boundaries, SSOT, algorithmic DRY, naming). MUST run AFTER /tpr-review is clean.
  • /improve-tooling retrospective completed — MANDATORY at section close, after both reviews are clean. Reflect on the section’s debugging journey (which diagnostics/ scripts you ran, which command sequences you repeated, where you added ad-hoc dbg!/tracing calls, where output was hard to interpret) and identify any tool/log/diagnostic improvement that would have made this section materially easier OR that would help the next section touching this area. Implement every accepted improvement NOW (zero deferral) and commit each via SEPARATE /commit-push. The retrospective is mandatory even when nothing felt painful — that is exactly when blind spots accumulate. See .claude/skills/improve-tooling/SKILL.md “Retrospective Mode” for the full protocol.

Hygiene Notes (non-blocking, from verification 2026-03-29)

  • BLOAT: 4 source files over 500-line limit in unify/infer modules — split when next touched (line counts verified 2026-06-07):

    • compiler/ori_types/src/unify/mod.rs — 751 lines
    • compiler/ori_types/src/infer/mod.rs — 697 lines
    • compiler/ori_types/src/infer/expr/calls/monomorphization.rs — 705 lines
    • compiler/ori_types/src/infer/expr/calls/impl_lookup.rs — 591 lines

  • MISSING NEGATIVE PINS (blocked-by bug): No dedicated compile-fail test for unification rejection (e.g., let x: int = "hello" should fail with type mismatch). Partially covered by existing tests but not comprehensive. Owned by bug-tracker/plans/BUG-02-039/.

  • Subsection close-out (2.4) — MANDATORY before starting the next subsection. Run /improve-tooling retrospectively on THIS subsection’s debugging journey (per .claude/skills/improve-tooling/SKILL.md “Per-Subsection Workflow”): which diagnostics/ scripts you ran, where you added dbg!/tracing calls, where output was hard to interpret, where test failures gave unhelpful messages, where you ran the same command sequence repeatedly. Forward-look: what tool/log/diagnostic would shorten the next regression in this code path by 10 minutes? Implement improvements NOW (zero deferral) and commit each via SEPARATE /commit-push using a valid conventional-commit type (build(diagnostics): ... — surfaced by section-2.4 retrospective — build/test/chore/ci/docs are valid; tools(...) is rejected by the lefthook commit-msg hook). Mandatory even when nothing felt painful. If genuinely no gaps, document briefly: “Retrospective 2.4: no tooling gaps”. Update this subsection’s status in section frontmatter to complete.

  • /sync-claude section-close doc sync — verify Claude artifacts across all section commits. Map changed crates to rules files, check CLAUDE.md, canon.md. Fix drift NOW.

  • Repo hygiene check — run diagnostics/repo-hygiene.sh --check and clean any detected temp files.

  • /tpr-review passed — independent review found no critical or major issues (or all findings triaged)

  • /impl-hygiene-review passed — hygiene review clean. MUST run AFTER /tpr-review is clean.