Constant Propagation in Go

Constant propagation is a compiler optimization technique that replaces variables with their constant values where possible. This can lead to significant performance improvements by allowing the compiler to perform further optimizations and reduce runtime computations. Your task is to implement a simplified constant propagation pass for a small subset of Go code.

Problem Description

You are to implement a function PropagateConstants that takes an abstract syntax tree (AST) representing a simple Go expression and performs constant propagation. The AST will consist of only assignment statements and simple arithmetic expressions (addition and subtraction) involving variables and integer constants. The goal is to replace variables with their constant values wherever possible after evaluating the assignment statements.

What needs to be achieved:

1. Evaluate Assignments: Evaluate all assignment statements in the input AST. This involves calculating the constant value assigned to each variable.
2. Propagate Constants: After evaluation, traverse the AST again. If a variable appears in an expression and has a known constant value (determined in step 1), replace the variable with its constant value.
3. Return Modified AST: Return a new AST with the constant propagation applied.

Key Requirements:

• The input AST is represented as a nested Node struct (defined below).
• The AST only contains assignment statements and arithmetic expressions (addition and subtraction).
• Variables are represented as strings.
• Constants are integers.
• The AST is guaranteed to be well-formed.
• The propagation should be performed after all assignments have been evaluated.

Expected Behavior:

The function should return a new AST where variables have been replaced with their constant values whenever possible. If a variable does not have a constant value after evaluation, it should remain unchanged in the output AST.

Important Edge Cases to Consider:

• Variables appearing on both sides of an assignment statement. (These should be resolved before propagation).
• Expressions involving multiple variables.
• Expressions with no constants.
• Empty AST.

Examples

Example 1:

Input:
[
  {"type": "assignment", "variable": "x", "value": {"type": "add", "left": {"type": "const", "value": 10}, "right": {"type": "const", "value": 5}}},
  {"type": "add", "left": {"type": "const", "value": 20}, "right": {"type": "variable", "name": "x"}}
]
Output:
[
  {"type": "add", "left": {"type": "const", "value": 20}, "right": {"type": "const", "value": 15}}
]
Explanation:
x = 10 + 5 is evaluated to x = 15.  Then, 20 + x is replaced with 20 + 15 = 35.

Example 2:

Input:
[
  {"type": "assignment", "variable": "x", "value": {"type": "const", "value": 5}},
  {"type": "add", "left": {"type": "variable", "name": "x"}, "right": {"type": "const", "value": 10}}
]
Output:
[
  {"type": "add", "left": {"type": "const", "value": 5}, "right": {"type": "const", "value": 10}}
]
Explanation:
x = 5. Then, x + 10 is replaced with 5 + 10 = 15.

Example 3:

Input:
[
  {"type": "assignment", "variable": "x", "value": {"type": "add", "left": {"type": "const", "value": 1}, "right": {"type": "const", "value": 2}}},
  {"type": "assignment", "variable": "y", "value": {"type": "add", "left": {"type": "const", "value": 3}, "right": {"type": "const", "value": 4}}},
  {"type": "add", "left": {"type": "variable", "name": "x"}, "right": {"type": "variable", "name": "y"}}
]
Output:
[
  {"type": "add", "left": {"type": "const", "value": 3}, "right": {"type": "const", "value": 7}}
]
Explanation:
x = 1 + 2 = 3. y = 3 + 4 = 7. x + y is replaced with 3 + 7 = 10.

Constraints

• The input AST will contain at most 10 assignment statements and 10 expressions.
• Variable names will be strings of length at most 10.
• Constant values will be integers between -100 and 100.
• The AST will be valid Go-like syntax for the described subset.
• The solution should be reasonably efficient (avoiding unnecessary recursion or iterations).

Notes

• You will need to define a Node struct to represent the AST.
• Consider using a map to store the constant values of variables after evaluation.
• The order of operations matters. Assignments should be evaluated before propagation.
• Focus on correctness first, then optimize for performance.
• The provided examples are not exhaustive; consider other possible scenarios.
• The AST is a simplified representation and does not include all features of Go syntax.

type Node struct {
	Type      string
	Variable  string
	Value     *Node
	Left      *Node
	Right     *Node
	Name      string
	ConstValue int
}