Simple Type Checker in Rust

This challenge asks you to implement a basic type checker for a simplified expression language in Rust. Type checking ensures that operations are performed on compatible data types, preventing runtime errors and improving code reliability. This exercise will test your understanding of Rust's type system, pattern matching, and data structures.

Problem Description

You are tasked with building a type checker for a language with the following data types: Int, Bool, and String. Expressions in this language can be:

• Literals: Int(i32), Bool(bool), String(String)
• Binary Operations: BinOp(Operator, Expression, Expression) where Operator can be Add, Sub, Mul, Div, Eq, Lt.
• Variables: Var(String) (for simplicity, variable types are not stored; the type checker must infer them).

The type checker should determine the type of each expression. If an expression is type-safe (i.e., operations are valid for the given types), it should return Ok(Type). If an expression is type-unsafe (e.g., adding a string to an integer), it should return Err(String) with a descriptive error message.

Key Requirements:

• Implement the Expression enum and Operator enum as described above.
• Implement a Type enum with variants IntType, BoolType, and StringType.
• Implement a type_check function that takes an Expression and returns a Result<Type, String>.
• Handle all supported operators and their type compatibility rules.
• Infer the type of variables (assume variables are always defined and have a type). For this challenge, assume that Var("x") always has type IntType, Var("y") always has type BoolType, and Var("z") always has type StringType. All other variables should return an error.

Expected Behavior:

The type checker should correctly determine the type of valid expressions and return an error for invalid ones. Error messages should be informative.

Edge Cases to Consider:

• Division by zero (should not be a type error, but a runtime error – this challenge does not require handling runtime errors, only type errors).
• Unsupported operators between incompatible types.
• Undefined variables.
• Empty expressions (though the language doesn't explicitly define these, consider how your code handles them).

Examples

Example 1:

Input: BinOp(Add, Int(5), Int(10))
Output: Ok(IntType)
Explanation: Adding two integers results in an integer.

Example 2:

Input: BinOp(Eq, Int(5), Bool(true))
Output: Err("Type mismatch: cannot compare Int and Bool")
Explanation: Comparing an integer and a boolean is not allowed.

Example 3:

Input: BinOp(Mul, Var("x"), Int(2))
Output: Ok(IntType)
Explanation: Variable "x" is assumed to be of type Int, and multiplying an integer by an integer results in an integer.

Example 4:

Input: BinOp(Add, Var("x"), Var("y"))
Output: Err("Type mismatch: cannot add Int and Bool")
Explanation: Variable "x" is assumed to be of type Int, and variable "y" is assumed to be of type Bool. Adding an integer and a boolean is not allowed.

Example 5:

Input: BinOp(Lt, Var("y"), Var("x"))
Output: Ok(BoolType)
Explanation: Variable "y" is assumed to be of type Bool, and variable "x" is assumed to be of type Int. Comparing a boolean and an integer is allowed, resulting in a boolean.

Constraints

• The language only supports Int, Bool, and String types.
• The language only supports the operators Add, Sub, Mul, Div, Eq, and Lt.
• Variable names are limited to single characters: "x", "y", and "z".
• The type checker should be reasonably efficient (avoid unnecessary recursion or data structures). Performance is not a primary concern, but avoid obviously inefficient solutions.
• Error messages should be clear and concise.

Notes

• Consider using pattern matching extensively to handle different expression types.
• Think about how to represent types and operators in a clear and maintainable way.
• Start with simple expressions and gradually increase complexity.
• The variable type inference is a simplification for this exercise. In a real-world type checker, variable types would be stored and used during type checking.
• Focus on correctness and clarity over extreme optimization.
• The Div operator should not trigger a type error if the divisor is zero. It's a runtime concern, not a type concern.