Const Propagation Optimization in Rust

Const propagation is a compiler optimization technique that aims to replace uses of a constant expression with the constant value itself. This can lead to significant performance improvements, especially in scenarios involving compile-time calculations. This challenge asks you to implement a simplified version of const propagation for a subset of Rust code.

Problem Description

You are tasked with implementing a simplified const propagation algorithm. Given a list of expressions, where some expressions are constants, your function should identify and replace all occurrences of a constant expression with its value. The expressions are represented as strings. The algorithm should only propagate simple integer constants. More complex expressions (e.g., function calls, variable references) should be left untouched. The goal is to demonstrate the core concept of const propagation without the complexities of a full Rust compiler.

What needs to be achieved:

• Identify constant expressions (integers represented as strings).
• Replace all occurrences of a constant expression with its integer value (as a string).
• Handle multiple constants within the input list.
• Leave non-constant expressions unchanged.

Key Requirements:

• The input is a Vec<String> representing a list of expressions.
• The output is a Vec<String> with the constant expressions replaced by their values.
• The algorithm should be deterministic and produce the same output for the same input.
• Error handling is not required; assume the input contains only valid expressions (strings).

Expected Behavior:

The function should iterate through the input list. For each expression, it should check if it's a valid integer constant. If it is, it should replace the expression with its string representation of the integer value. If it's not a constant, it should leave the expression unchanged.

Important Edge Cases to Consider:

• Empty input list.
• List containing only non-constant expressions.
• List containing multiple constant expressions with the same value.
• List containing constant expressions with negative values.
• Expressions that look like numbers but are not (e.g., "123a"). These should not be treated as constants.

Examples

Example 1:

Input: ["10", "2 * 5", "10 + 5", "10"]
Output: ["10", "2 * 5", "10 + 5", "10"]
Explanation: "10" appears twice. Both instances are replaced with "10".

Example 2:

Input: ["5", "10", "5 + 2", "10 * 2"]
Output: ["5", "10", "5 + 2", "10 * 2"]
Explanation: "5" and "10" are constants and are left unchanged as they are already their values.

Example 3:

Input: ["-5", "10", "-5 + 2", "10 * 2"]
Output: ["-5", "10", "-5 + 2", "10 * 2"]
Explanation: Negative constants are handled correctly.

Example 4:

Input: ["123a", "123"]
Output: ["123a", "123"]
Explanation: "123a" is not a valid integer constant and is left unchanged.

Constraints

• The input Vec<String> will contain strings representing expressions.
• Constant expressions will be valid integers (positive, negative, or zero) represented as strings.
• The length of the input vector will be between 0 and 1000.
• The length of each string in the input vector will be between 1 and 20.
• Performance: The solution should complete within 1 second for the given constraints.

Notes

• You can use Rust's built-in string parsing functions to check if a string represents a valid integer. parse::<i32>() is a good starting point.
• Consider using a loop to iterate through the input vector and perform the replacements.
• Focus on the core concept of const propagation – identifying and replacing constant expressions. Don't worry about handling more complex expressions or optimizations.
• The goal is to demonstrate understanding of the concept, not to create a production-ready const propagation implementation.