✨ feat: add typechecker crate by harehare · Pull Request #850 · harehare/mq

harehare · 2025-11-15T12:59:02Z

No description provided.

Copilot

Pull request overview

Introduces a new mq-typechecker crate implementing Hindley–Milner-style static type checking/type inference for mq, plus initial tests and workspace integration.

Changes:

Added mq-typechecker crate (types, constraint generation, unification, builtin signatures, and public TypeChecker API).
Added extensive test suite (integration, builtin typing via rstest, error location, and debug-oriented tests).
Wired the crate into the workspace; adjusted HIR call-argument parenting for improved symbol structure.

Reviewed changes

Copilot reviewed 17 out of 18 changed files in this pull request and generated 15 comments.

Show a summary per file

File	Description
crates/mq-typechecker/src/lib.rs	Public API + builtin type signatures and diagnostics types
crates/mq-typechecker/src/types.rs	Core type/type-scheme representation + basic matching utilities
crates/mq-typechecker/src/infer.rs	Inference context, substitutions, and overload resolution
crates/mq-typechecker/src/constraint.rs	HIR-to-constraints generation (operators, calls, collections, control flow)
crates/mq-typechecker/src/unify.rs	Constraint solving + unification/occurs check + span conversion
crates/mq-typechecker/tests/integration_test.rs	Broad end-to-end success/error cases for the typechecker
crates/mq-typechecker/tests/builtin_test.rs	Parameterized builtin/operator typing tests via `rstest`
crates/mq-typechecker/tests/type_errors_test.rs	Focused tests for known/expected type error detection
crates/mq-typechecker/tests/error_location_test.rs	Tests intended to validate span/error readability behavior
crates/mq-typechecker/tests/debug_builtin.rs	Debug-only HIR inspection test for builtins
crates/mq-typechecker/tests/debug_abs_test.rs	Debug-only typechecking inspection test for `abs(42)`
crates/mq-typechecker/README.md	Crate-level documentation and usage examples
crates/mq-typechecker/Cargo.toml	New crate manifest + dependencies/dev-dependencies
crates/mq-typechecker/.gitignore	Ignores generated `docs` dir for the new crate
crates/mq-lang/modules/table.mq	Modified module code/comments (currently appears corrupted)
crates/mq-hir/src/hir.rs	Ensures call arguments are parented under the call symbol node
Cargo.toml	Adds `crates/mq-typechecker` to the workspace members

crates/mq-lang/modules/table.mq

crates/mq-typechecker/src/infer.rs

crates/mq-typechecker/src/lib.rs

crates/mq-typechecker/src/constraint.rs

crates/mq-typechecker/tests/debug_builtin.rs

crates/mq-typechecker/tests/debug_abs_test.rs

crates/mq-typechecker/tests/error_location_test.rs

crates/mq-typechecker/tests/builtin_test.rs

crates/mq-typechecker/src/unify.rs

codspeed-hq · 2026-02-09T13:57:33Z

Merging this PR will not alter performance

✅ 29 untouched benchmarks

_{Comparing feat/add-typechecker-crate (e9abb63) with main (c776692)}

Copilot

Pull request overview

Copilot reviewed 15 out of 16 changed files in this pull request and generated 15 comments.

crates/mq-typechecker/Cargo.toml

crates/mq-typechecker/tests/type_errors_test.rs

crates/mq-typechecker/src/constraint.rs

crates/mq-typechecker/src/builtin.rs

crates/mq-typechecker/README.md

crates/mq-typechecker/src/lib.rs

crates/mq-typechecker/src/constraint.rs

crates/mq-typechecker/src/builtin.rs

crates/mq-typechecker/tests/integration_test.rs

crates/mq-typechecker/tests/type_errors_test.rs

Copilot

Pull request overview

Copilot reviewed 15 out of 16 changed files in this pull request and generated 8 comments.

crates/mq-typechecker/src/constraint.rs

crates/mq-typechecker/tests/type_errors_test.rs

crates/mq-typechecker/src/unify.rs

crates/mq-typechecker/src/builtin.rs

crates/mq-typechecker/Cargo.toml

Copilot

Pull request overview

Copilot reviewed 15 out of 16 changed files in this pull request and generated 7 comments.

crates/mq-typechecker/tests/integration_test.rs

crates/mq-typechecker/tests/error_location_test.rs

crates/mq-typechecker/README.md

crates/mq-typechecker/tests/type_errors_test.rs

crates/mq-typechecker/Cargo.toml

crates/mq-typechecker/README.md

Copilot

Pull request overview

Copilot reviewed 15 out of 16 changed files in this pull request and generated 1 comment.

crates/mq-typechecker/README.md

Copilot

Pull request overview

Copilot reviewed 16 out of 17 changed files in this pull request and generated 7 comments.

crates/mq-typechecker/src/unify.rs

crates/mq-typechecker/tests/error_location_test.rs

crates/mq-typechecker/src/builtin.rs

crates/mq-typechecker/src/lib.rs

crates/mq-typechecker/src/main.rs

crates/mq-typechecker/tests/type_errors_test.rs

…rt comparator Co-authored-by: harehare <[email protected]>

…checks

…pe inference

Co-authored-by: Copilot <[email protected]>

Co-authored-by: harehare <[email protected]>

…hance error location tests

Co-authored-by: Copilot <[email protected]>

…e type checking tests

…der function type checking and enhance lambda type validation in integration tests

…a and function definitions

…hance error location tests

…n in debug functions

…ns with generic and None propagation support

…orting - Refactored constraint generation to use a pre-built children index for efficient symbol traversal. - Added single-pass symbol categorization to replace multiple iterations. - Improved error reporting with new report_no_matching_overload method. - Updated function signatures to use the new index. - Changed Substitution to use FxHashMap for performance. Related files: constraint.rs, infer.rs, lib.rs, types.rs

Copilot

Pull request overview

Copilot reviewed 17 out of 19 changed files in this pull request and generated 1 comment.

Copilot · 2026-02-28T04:42:37Z

crates/mq-typechecker/src/builtin.rs

+    // `&&` and `||` can accept any types (e.g., `none || "default"`, `is_array(x) && len(x)`).
+    for name in ["&&", "||", "and", "or"] {
+        let (a, b) = (ctx.fresh_var(), ctx.fresh_var());
+        register_binary(ctx, name, Type::Var(a), Type::Var(b), Type::Var(b));
+    }
+
+    // Variadic logical: or/and with 3-6 boolean arguments
+    for n in 3..=6 {
+        let params = vec![Type::Bool; n];
+        for name in ["or", "and"] {
+            ctx.register_builtin(name, Type::function(params.clone(), Type::Bool));


The generic overload for and/or/&&/|| is registered as (a, b) -> b, but mq’s runtime semantics can also produce false (and for || it can return either operand depending on truthiness). This will cause incorrect inferred types (e.g., x = "a" || 0 can evaluate to a string, but the checker will force x to type like 0). Consider making the return type a union that includes bool plus the possible operand types, and ensure the signatures reflect the actual variadic behavior of and(...)/or(...).

Suggested change

// `&&` and `||` can accept any types (e.g., `none || "default"`, `is_array(x) && len(x)`).

for name in ["&&", "||", "and", "or"] {

let (a, b) = (ctx.fresh_var(), ctx.fresh_var());

register_binary(ctx, name, Type::Var(a), Type::Var(b), Type::Var(b));

}

// Variadic logical: or/and with 3-6 boolean arguments

for n in 3..=6 {

let params = vec![Type::Bool; n];

for name in ["or", "and"] {

ctx.register_builtin(name, Type::function(params.clone(), Type::Bool));

// `&&` and `||` (and their word forms) can accept any types and may return:

// - `false`, or

// - either operand, depending on truthiness.

//

// We approximate this with a generic overload:

// forall a b. (a, b) -> bool | a | b

for name in ["&&", "||", "and", "or"] {

let (a, b) = (ctx.fresh_var(), ctx.fresh_var());

let lhs = Type::Var(a);

let rhs = Type::Var(b);

let result = Type::union(vec![Type::Bool, lhs.clone(), rhs.clone()]);

register_binary(ctx, name, lhs, rhs, result);

}

// Variadic logical: and/or with 3-6 arguments.

// Runtime semantics: may return `false` or any of the operands based on truthiness.

// We model this as:

// forall a1..an. (a1, ..., an) -> bool | a1 | ... | an

for n in 3..=6 {

let type_vars: Vec<_> = (0..n).map(|_| ctx.fresh_var()).collect();

let params: Vec<Type> = type_vars.iter().map(|v| Type::Var(*v)).collect();

let mut result_members: Vec<Type> = vec![Type::Bool];

result_members.extend(type_vars.iter().map(|v| Type::Var(*v)));

let result = Type::union(result_members);

for name in ["or", "and"] {

ctx.register_builtin(name, Type::function(params.clone(), result.clone()));

… tests for mixed type operations

… type error tests

… variable reassignment tests

Copilot

Pull request overview

Copilot reviewed 19 out of 21 changed files in this pull request and generated 3 comments.

Copilot · 2026-02-28T12:47:36Z

crates/mq-typechecker/src/unify.rs

+        // Union types: a union can unify with a type if any of its members can unify with it
+        (Type::Union(types), other) | (other, Type::Union(types)) => {
+            // Check if the other type matches any member of the union
+            let matches_any = types.iter().any(|t| {
+                // Try to check if types can match without adding errors
+                match (t, other) {
+                    (t1, t2) if std::mem::discriminant(t1) == std::mem::discriminant(t2) => true,
+                    (Type::Var(_), _) | (_, Type::Var(_)) => true,
+                    _ => false,
+                }
+            });
+
+            if !matches_any {
+                // No member of the union can unify with the other type - report error
+                let resolved_t1 = ctx.resolve_type(t1);
+                let resolved_t2 = ctx.resolve_type(t2);
+                ctx.add_error(TypeError::Mismatch {
+                    expected: resolved_t1.display_renumbered(),
+                    found: resolved_t2.display_renumbered(),
+                    span: range.as_ref().map(range_to_span),
+                    location: range.as_ref().map(|r| (r.start.line, r.start.column)),
+                });
+            }
+            // If at least one member matches, allow it (union type semantics)
+        }


Union unification currently treats two types as compatible if their enum discriminants match (e.g. any array<T> matches any array<U>), which can let obviously-incompatible union members slip through without errors. This can silently accept invalid programs (and will also mis-handle nested structures). Consider using the existing structural compatibility check (Type::can_match) against the resolved types, or perform a non-allocating structural comparison that checks element/key/value/params recursively instead of only the top-level variant.

Copilot · 2026-02-28T12:47:37Z

crates/mq-typechecker/src/builtin.rs

+    // keys: {k: v} -> [k]
+    let (k, v) = (ctx.fresh_var(), ctx.fresh_var());
+    register_unary(
+        ctx,
+        "keys",
+        Type::dict(Type::Var(k), Type::Var(v)),
+        Type::array(Type::Var(k)),
+    );
+
+    // Generic fallback: keys/values/entries accept any type (for dynamically typed code
+    // where the argument type is determined by runtime guards like `is_dict`)
+    let (a, b) = (ctx.fresh_var(), ctx.fresh_var());
+    register_unary(ctx, "keys", Type::Var(a), Type::array(Type::Var(b)));


keys is typed as {k: v} -> [k], but at runtime it always returns an array of strings (RuntimeValue::String(k.as_str())). The current signature will infer incorrect key types and can mask errors in downstream code; consider returning [string] (and keep the none -> none propagation overload).

Suggested change

// keys: {k: v} -> [k]

let (k, v) = (ctx.fresh_var(), ctx.fresh_var());

register_unary(

ctx,

"keys",

Type::dict(Type::Var(k), Type::Var(v)),

Type::array(Type::Var(k)),

);

// Generic fallback: keys/values/entries accept any type (for dynamically typed code

// where the argument type is determined by runtime guards like `is_dict`)

let (a, b) = (ctx.fresh_var(), ctx.fresh_var());

register_unary(ctx, "keys", Type::Var(a), Type::array(Type::Var(b)));

// keys: {k: v} -> [string]

let (k, v) = (ctx.fresh_var(), ctx.fresh_var());

register_unary(

ctx,

"keys",

Type::dict(Type::Var(k), Type::Var(v)),

Type::array(Type::string()),

);

// Generic fallback: keys/values/entries accept any type (for dynamically typed code

// where the argument type is determined by runtime guards like `is_dict`)

let (a, _b) = (ctx.fresh_var(), ctx.fresh_var());

register_unary(ctx, "keys", Type::Var(a), Type::array(Type::string()));

crates/mq-typechecker/src/builtin.rs

harehare force-pushed the feat/add-typechecker-crate branch from 53ab26c to 9ffd4ee Compare November 23, 2025 13:39

harehare force-pushed the main branch from 5909fcc to 538cf46 Compare December 3, 2025 15:01

harehare force-pushed the feat/add-typechecker-crate branch from 9ffd4ee to f1eb752 Compare December 13, 2025 12:49

harehare force-pushed the main branch from 5f72edb to b609992 Compare February 7, 2026 04:04

harehare force-pushed the feat/add-typechecker-crate branch from f1eb752 to 02334e8 Compare February 9, 2026 13:43

Copilot AI review requested due to automatic review settings February 9, 2026 13:43

Copilot AI reviewed Feb 9, 2026

View reviewed changes

harehare closed this Feb 15, 2026

harehare reopened this Feb 15, 2026

harehare force-pushed the feat/add-typechecker-crate branch from 02334e8 to db1b2b1 Compare February 15, 2026 08:37

harehare changed the title ~~✨ feat(typechecker): add Hindley-Milner type inference crate~~ ✨ feat(typechecker): add typechecker crate Feb 15, 2026

harehare changed the title ~~✨ feat(typechecker): add typechecker crate~~ ✨ feat: add typechecker crate Feb 15, 2026

Copilot AI review requested due to automatic review settings February 15, 2026 08:42

Copilot started reviewing on behalf of harehare February 15, 2026 08:43 View session

Copilot AI reviewed Feb 15, 2026

View reviewed changes

Copilot AI review requested due to automatic review settings February 15, 2026 10:35

Copilot started reviewing on behalf of harehare February 15, 2026 10:36 View session

Copilot AI reviewed Feb 15, 2026

View reviewed changes

Copilot AI review requested due to automatic review settings February 15, 2026 11:34

Copilot started reviewing on behalf of harehare February 15, 2026 11:35 View session

Copilot AI reviewed Feb 15, 2026

View reviewed changes

Copilot AI review requested due to automatic review settings February 15, 2026 14:21

harehare force-pushed the feat/add-typechecker-crate branch from 538c9cb to 4e5cbf1 Compare February 15, 2026 14:21

Copilot started reviewing on behalf of harehare February 15, 2026 14:22 View session

Copilot AI reviewed Feb 15, 2026

View reviewed changes

crates/mq-typechecker/README.md Outdated Show resolved Hide resolved

harehare marked this pull request as ready for review February 15, 2026 14:47

Copilot AI review requested due to automatic review settings February 16, 2026 00:41

Copilot started reviewing on behalf of harehare February 16, 2026 00:41 View session

Copilot AI reviewed Feb 16, 2026

View reviewed changes

Copilot AI and others added 18 commits February 28, 2026 13:36

🐛 fix(mq-typechecker): avoid O(n log n) allocations in Type::union so…

4023aff

…rt comparator Co-authored-by: harehare <[email protected]>

✨ Feat(typechecker): add support for loop expressions and union type …

9c6a9ba

…checks

✨ feat(typechecker): update README and improve type inference comments

d0e01a3

✨ feat(typechecker): implement break expression handling and union ty…

779a349

…pe inference

Update crates/mq-typechecker/tests/builtin_test.rs

c8d46ba

Co-authored-by: Copilot <[email protected]>

Initial plan

1caf12a

✅ test: fix pattern match syntax in integration tests

cc06adb

Co-authored-by: harehare <[email protected]>

🎨 Format code

b19f57e

✨ feat(typechecker): enhance type inference with new built-in functions

a5e36de

✨ feat(typechecker): add utility functions for type conversion and en…

6d34398

…hance error location tests

Update crates/mq-typechecker/src/builtin.rs

26d3a9d

Co-authored-by: Copilot <[email protected]>

✨ feat(typechecker): refine utility function registrations and enhanc…

e63c5a5

…e type checking tests

✨ feat(typechecker): implement deferred parameter calls for higher-or…

12fdf97

…der function type checking and enhance lambda type validation in integration tests

✨ feat(typechecker): add tests for chained binary operations in lambd…

ffd597b

…a and function definitions

✨ feat(typechecker): add utility functions for type conversion and en…

34dc4e7

…hance error location tests

✨ feat(typechecker): change 'assert' from binary to unary registratio…

9a5eb10

…n in debug functions

✨ feat(typechecker): enhance dict and collection function registratio…

d7117dc

…ns with generic and None propagation support

Copilot started reviewing on behalf of harehare February 28, 2026 04:36 View session

Copilot AI reviewed Feb 28, 2026

View reviewed changes

harehare added 2 commits February 28, 2026 15:01

✨ feat(typechecker): add bsearch registration and enhance integration…

3fd8b7a

… tests for mixed type operations

✨ feat(typechecker): improve constraint generation and enhance lambda…

4d22d1d

… type error tests

harehare force-pushed the feat/add-typechecker-crate branch from d209665 to 4d22d1d Compare February 28, 2026 06:53

✨ feat(typechecker): implement assignment symbol handling and enhance…

46e5ffd

… variable reassignment tests

Copilot AI review requested due to automatic review settings February 28, 2026 12:43

Copilot started reviewing on behalf of harehare February 28, 2026 12:43 View session

📝 Chore(typechecker): ensure publish is set to false in Cargo.toml

e9abb63

Copilot AI reviewed Feb 28, 2026

View reviewed changes

harehare merged commit ac9e417 into main Feb 28, 2026
9 checks passed

BrewTestBot mentioned this pull request Feb 28, 2026

mq 0.5.17 Homebrew/homebrew-core#269913

Merged

-    // `&&` and `||` can accept any types (e.g., `none || "default"`, `is_array(x) && len(x)`).
-    for name in ["&&", "||", "and", "or"] {
-        let (a, b) = (ctx.fresh_var(), ctx.fresh_var());
-        register_binary(ctx, name, Type::Var(a), Type::Var(b), Type::Var(b));
-    }
-    // Variadic logical: or/and with 3-6 boolean arguments
-    for n in 3..=6 {
-        let params = vec![Type::Bool; n];
-        for name in ["or", "and"] {
-            ctx.register_builtin(name, Type::function(params.clone(), Type::Bool));
+    // `&&` and `||` (and their word forms) can accept any types and may return:
+    // - `false`, or
+    // - either operand, depending on truthiness.
+    //
+    // We approximate this with a generic overload:
+    //   forall a b. (a, b) -> bool | a | b
+    for name in ["&&", "||", "and", "or"] {
+        let (a, b) = (ctx.fresh_var(), ctx.fresh_var());
+        let lhs = Type::Var(a);
+        let rhs = Type::Var(b);
+        let result = Type::union(vec![Type::Bool, lhs.clone(), rhs.clone()]);
+        register_binary(ctx, name, lhs, rhs, result);
+    }
+    // Variadic logical: and/or with 3-6 arguments.
+    // Runtime semantics: may return `false` or any of the operands based on truthiness.
+    // We model this as:
+    //   forall a1..an. (a1, ..., an) -> bool | a1 | ... | an
+    for n in 3..=6 {
+        let type_vars: Vec<_> = (0..n).map(|_| ctx.fresh_var()).collect();
+        let params: Vec<Type> = type_vars.iter().map(|v| Type::Var(*v)).collect();
+        let mut result_members: Vec<Type> = vec![Type::Bool];
+        result_members.extend(type_vars.iter().map(|v| Type::Var(*v)));
+        let result = Type::union(result_members);
+        for name in ["or", "and"] {
+            ctx.register_builtin(name, Type::function(params.clone(), result.clone()));

Conversation

harehare commented Nov 15, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

codspeed-hq bot commented Feb 9, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Merging this PR will not alter performance

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Uh oh!

harehare commented Nov 15, 2025 •

edited

Loading

codspeed-hq bot commented Feb 9, 2026 •

edited

Loading