Implementing Compile-Time Constant Evaluation in Rust

Rust's const fn allows functions to be evaluated at compile time, enabling powerful optimizations and enabling the creation of truly immutable constants derived from complex logic. This challenge asks you to implement a simplified, custom compile-time constant evaluator that can handle a subset of Rust's const fn capabilities. This exercise will deepen your understanding of how compile-time evaluation works and the challenges involved.

Problem Description

Your task is to build a Rust program that simulates a limited const fn evaluator. You will be given an abstract representation of a simple Rust function and its arguments. Your evaluator should attempt to compute the function's result at compile time. If the computation can be fully resolved at compile time, your program should output the computed constant value. If the computation involves operations or constructs that cannot be resolved at compile time (in this simplified model), it should indicate that the evaluation could not be performed.

Key Requirements:

• Abstract Syntax Tree (AST) Representation: You will need to define data structures to represent a simplified AST of functions, variables, and basic operations.
• Evaluation Engine: Implement a function that takes an AST node representing a function call and its arguments, and attempts to evaluate it.
• Supported Operations: The evaluator should support basic arithmetic operations (addition, subtraction, multiplication, division), integer literals, and variable lookups.
• Constant Propagation: If a variable's value is known at compile time, use that value.
• Error Handling: Clearly distinguish between successful compile-time evaluations and cases where evaluation cannot be completed (e.g., division by zero at compile time, unsupported operations).

Expected Behavior:

Your evaluator should process function calls. If all operands and operations within the function can be resolved to a concrete integer value at "compile time" (i.e., during your program's execution), it should return that integer. Otherwise, it should signal an error.

Edge Cases:

• Division by zero.
• Functions with no arguments.
• Functions where some arguments are literals and others are variables with known values.
• Nested function calls (for simplicity, limit nesting to one level for this challenge).

Examples

Example 1:

Input: A function add that takes two integers and returns their sum. Call: add(5, 10)

Output: 15

Explanation: The add function is called with literal values 5 and 10. The evaluator can directly compute 5 + 10 to 15.

Example 2:

Input: A function multiply that takes two integers and returns their product. Call: multiply(7, 0)

Output: 0

Explanation: The multiply function is called with literal values 7 and 0. The evaluator computes 7 * 0 to 0.

Example 3:

Input: A function divide that takes two integers and returns their quotient. Call: divide(10, 2)

Output: 5

Explanation: The divide function is called with literal values 10 and 2. The evaluator computes 10 / 2 to 5.

Example 4: (Illustrating a "non-evaluatable" scenario in this simplified model)

Input: A hypothetical "runtime" function get_input() that returns an integer from user input (which cannot be known at compile time). A function subtract that takes two integers and returns their difference. Call: subtract(20, get_input())

Output: Evaluation Error: Cannot evaluate because 'get_input' is not a const-evaluatable operation.

Explanation: While 20 is a known value, get_input() represents an operation that cannot be resolved at compile time in this model. Therefore, the entire expression cannot be evaluated.

Example 5: (Division by zero)

Input: A function divide that takes two integers and returns their quotient. Call: divide(5, 0)

Output: Evaluation Error: Division by zero.

Explanation: The evaluator detects that the divisor is 0, which is an invalid operation for compile-time evaluation.

Constraints

• Integer Types: All numeric values will be 32-bit signed integers (i32).
• Function Signatures: Functions will take a fixed number of i32 arguments and return an i32.
• Operations: Only addition (+), subtraction (-), multiplication (*), and integer division (/) are supported for compile-time evaluation.
• Variable Scopes: Assume a single, flat scope for variables within the function body.
• No Control Flow: Functions will not contain if, loop, match, or other control flow structures. They will be simple expressions.
• No Function Pointers or Closures: Direct function calls only.
• No External Calls: Only operations defined within your evaluator are allowed.

Notes

• You'll need to define your AST nodes and a recursive evaluation function.
• Consider how you will represent an "unknown" or "runtime" value versus a known constant. An Option<i32> or a custom EvalResult enum could be useful.
• Think about how to pass "known" values down during evaluation.
• This is a simplified model of Rust's const fn. Actual Rust const evaluation is significantly more complex and handles many more features. Focus on the core logic of resolving expressions to constants.
• Success is defined by correctly evaluating all valid constant expressions and accurately reporting errors for non-constant expressions or invalid operations.