Constant Propagation in JavaScript

Constant propagation is a compiler optimization technique that replaces variables with their known constant values. This can simplify expressions and enable further optimizations. Your task is to implement a simplified version of constant propagation for a subset of JavaScript code, focusing on replacing variables with constant values where possible.

Problem Description

You are given an Abstract Syntax Tree (AST) representing a JavaScript expression. This AST will consist of simple expressions involving variables and constant numeric values. Your goal is to traverse the AST and perform constant propagation: wherever a variable is assigned a constant value, and that variable is subsequently used without being reassigned, replace the variable with its constant value. The AST nodes you'll encounter are:

• AssignmentExpression: Represents an assignment operation (e.g., x = 5). Has properties left (the variable being assigned to) and right (the value being assigned). left will always be a simple identifier. right can be a numeric literal or another identifier.
• Identifier: Represents a variable (e.g., x). Has a property name (the variable's name).
• NumericLiteral: Represents a numeric constant (e.g., 5). Has a property value (the numeric value).
• BinaryExpression: Represents a binary operation (e.g., x + 5). Has properties left, right, and operator (e.g., +, -, *, /). left and right can be any of the above node types.

You should return a new AST representing the expression after constant propagation has been applied. The new AST should have the same structure as the original, but with variables replaced by their constant values where possible.

Key Requirements:

• The AST is a simplified representation; you don't need to handle complex JavaScript features like functions, objects, or control flow.
• Focus on numeric constants only.
• Assume that variables are only assigned once within the scope of the provided AST. (No multiple assignments to the same variable).
• If a variable is reassigned, do not propagate the previous constant value.
• If a variable is used before it's assigned, leave it as is.

Examples

Example 1:

Input:
{
  "type": "BinaryExpression",
  "operator": "+",
  "left": { "type": "Identifier", "name": "x" },
  "right": { "type": "NumericLiteral", "value": 5 }
}

// Assume x = 10 is defined before this expression
// and x has not been reassigned.

Output:
{
  "type": "BinaryExpression",
  "operator": "+",
  "left": { "type": "NumericLiteral", "value": 10 },
  "right": { "type": "NumericLiteral", "value": 5 }
}

Explanation: The variable x is assumed to be assigned the value 10 before this expression. Since x is not reassigned, it's replaced with its constant value (10).

Example 2:

Input:
{
  "type": "BinaryExpression",
  "operator": "+",
  "left": { "type": "Identifier", "name": "x" },
  "right": { "type": "Identifier", "name": "y" }
}

// Assume x = 5 and y = 10 are defined before this expression
// and neither x nor y have been reassigned.

Output:
{
  "type": "BinaryExpression",
  "operator": "+",
  "left": { "type": "NumericLiteral", "value": 5 },
  "right": { "type": "NumericLiteral", "value": 10 }
}

Explanation: Both x and y are assigned constant values (5 and 10 respectively) and are not reassigned, so they are replaced with their constant values.

Example 3:

Input:
{
  "type": "AssignmentExpression",
  "left": { "type": "Identifier", "name": "x" },
  "right": { "type": "BinaryExpression",
             "operator": "+",
             "left": { "type": "Identifier", "name": "y" },
             "right": { "type": "NumericLiteral", "value": 5 }
            }
}

// Assume y = 2 is defined before this expression and y is not reassigned.

Output:
{
  "type": "AssignmentExpression",
  "left": { "type": "Identifier", "name": "x" },
  "right": { "type": "BinaryExpression",
             "operator": "+",
             "left": { "type": "NumericLiteral", "value": 2 },
             "right": { "type": "NumericLiteral", "value": 5 }
            }
}

Explanation: The variable y is replaced with its constant value (2) within the right-hand side of the assignment.

Constraints

• The input AST will always be a valid AST conforming to the described node types.
• Variable names will be strings.
• Numeric literals will be integers.
• The AST will not contain any loops or complex control flow.
• The AST will not contain function calls or object properties.
• The maximum depth of the AST will be 10.

Notes

• You'll need to implement a recursive traversal of the AST.
• Maintain a "constant map" to store variable names and their constant values.
• Consider how to handle cases where a variable is used before it's assigned.
• Think about how to avoid infinite recursion when encountering identifiers within the right-hand side of an assignment. You might need to track which variables are currently being assigned.
• The provided examples are simplified. Your solution should be able to handle more complex expressions.
• Focus on correctness first, then consider optimizing for performance.