Building a Simple Type Checker in Rust

This challenge involves creating a fundamental type checker for a simplified programming language. A type checker is a crucial part of a compiler or interpreter that ensures the program uses data types correctly, preventing runtime errors and improving code reliability. You will implement logic to verify type compatibility in expressions and assignments.

Problem Description

Your task is to implement a type checker for a mini-language that supports basic arithmetic operations, integer and boolean literals, and variable declarations/usage. The type checker will take an Abstract Syntax Tree (AST) representing a program and determine if it adheres to type rules.

Key Requirements:

1. Type Representation: Define an enum to represent the supported types: Int and Bool.
2. AST Definition: You'll be provided with a basic AST structure for expressions and statements. You'll need to augment this or define your own to include type information.
3. Type Checking Logic:
   • Literals: Assign the correct type to integer and boolean literals.
   • Variables: Look up the type of a variable from a symbol table (which you'll also need to implement or simulate).
   • Binary Operations: Ensure that operands for arithmetic operations (+, -, *, /) are both Int. Ensure that operands for comparison operations (<, >, ==, !=) are of compatible types (e.g., both Int or both Bool). The result of a comparison should be Bool.
   • Unary Operations: Ensure that the operand for the logical NOT operation (!) is Bool.
   • Assignments: Verify that the type of the expression being assigned matches the type of the variable being assigned to.
   • Sequential Statements: Type check each statement in sequence.
4. Error Reporting: When a type mismatch is detected, the type checker should report an error, indicating the location (e.g., line number, if available in AST) and the nature of the error.
5. Symbol Table: Implement a simple symbol table to store variable names and their associated types. This will be necessary to track variable types during type checking.

Expected Behavior:

• The type checker should traverse the AST.
• For each node, it should infer or verify the type.
• If a type error is found, it should return an error.
• If the AST is type-correct, it should indicate success and potentially return the AST with type annotations.

Edge Cases:

• Undeclared variables.
• Type mismatches in operations.
• Operations on incompatible types (e.g., adding a boolean to an integer).
• Assignments with incorrect types.

Examples

Example 1:

// Assume AST structure:
// Expression::Binary(Box<Expression>, BinaryOp, Box<Expression>)
// Expression::LiteralInt(i32)
// Expression::LiteralBool(bool)
// Statement::Let(String, Box<Expression>)
// Statement::Block(Vec<Statement>)

// Input AST (simplified representation):
// Block {
//   statements: [
//     Let("x", LiteralInt(10)),
//     Let("y", LiteralInt(20)),
//     // Assume print statement exists and takes an expression
//     Print(Binary(
//       Box::new(Identifier("x")),
//       Op::Add,
//       Box::new(Identifier("y"))
//     ))
//   ]
// }

Output:
Type Checking Successful!

Explanation: The AST represents declaring two integers x and y, and then printing their sum. The type checker verifies that x and y are Int, that the + operation is valid for two Ints, and that the result is also an Int (which is compatible with a print operation that expects an Int).

Example 2:

// Input AST (simplified representation):
// Block {
//   statements: [
//     Let("a", LiteralBool(true)),
//     Let("b", LiteralInt(5)),
//     Print(Binary(
//       Box::new(Identifier("a")),
//       Op::Add,
//       Box::new(Identifier("b"))
//     ))
//   ]
// }

Output:
Type Error at line X: Cannot apply operator '+' to operands of type Bool and Int.

Explanation: The AST attempts to add a boolean variable a with an integer variable b. The type checker detects that the + operator is only defined for integers, not for a Bool and Int combination, and reports an error. (Line number X would be inferred from the AST if available).

Example 3:

// Input AST (simplified representation):
// Block {
//   statements: [
//     Let("flag", LiteralBool(false)),
//     Let("count", LiteralInt(0)),
//     Assign("flag", Binary(
//       Box::new(LiteralInt(10)),
//       Op::Add,
//       Box::new(LiteralInt(20))
//     ))
//   ]
// }

Output:
Type Error at line Y: Cannot assign value of type Int to variable 'flag' which has type Bool.

Explanation: This AST declares flag as a boolean and count as an integer. It then attempts to assign the result of an integer addition (which is Int) to the flag variable, which is of type Bool. The type checker detects this assignment type mismatch.

Constraints

• The AST will be provided as a Rust data structure (you'll define this).
• Supported types are Int and Bool.
• Supported operations: +, -, *, / (arithmetic), <, >, ==, != (comparison), ! (logical NOT).
• Variable declarations will use a let keyword.
• Assignments will use an assignment operator (e.g., =).
• Error messages should be clear and informative, mentioning the type of error and potentially the location.
• Performance is not a primary concern for this basic implementation, but the approach should be efficient (e.g., single pass over the AST).

Notes

• You'll need to define your AST nodes, potentially including fields for type information.
• Consider how to represent and pass around the symbol table during the type checking process.
• A good starting point is to use recursion to traverse the AST.
• Think about how to represent and return type checking errors. A Result type in Rust is a natural fit.
• For simplicity, you can assume that all variables are declared before use for the initial implementation. Handling undeclared variables can be an extension.
• You might want to add line numbers to your AST nodes to improve error reporting accuracy.