"""
Part 3: DAG Evaluation -- Tree Walker
=======================================
Evaluating the AST bottom-up is equivalent to topological-sort
evaluation of a DAG. We must evaluate a node's children before
the node itself -- just like in any dependency graph.

For a tree, post-order traversal gives a topological ordering.
The recursive evaluate() function naturally does this:
  1. Recursively evaluate all children (dependencies)
  2. Combine the results (compute this node's value)
  3. Return the result (make it available to the parent)

This is the same pattern as:
  - make: build dependencies before the target
  - pip/npm install: install dependencies before the package
  - Spreadsheet recalculation: compute referenced cells first
"""

from parser import NumberNode, BinOpNode, UnaryOpNode, Node
from tokenizer import TokenType


# ---------- Errors ----------

class EvalError(Exception):
    pass


# ---------- Evaluator ----------

OP_SYMBOLS = {
    TokenType.PLUS: '+',
    TokenType.MINUS: '-',
    TokenType.MULTIPLY: '*',
    TokenType.DIVIDE: '/',
    TokenType.POWER: '^',
    TokenType.UNARY_MINUS: 'neg',
}


def evaluate(node):
    """
    Evaluate an AST by walking it bottom-up (post-order traversal).

    This is a recursive function that mirrors the DAG structure:
    each recursive call follows a DAG edge to a child node.
    Children are evaluated before parents -- topological order.
    """
    match node:
        case NumberNode(value=v):
            return v

        case UnaryOpNode(op=TokenType.UNARY_MINUS, operand=child):
            return -evaluate(child)

        case BinOpNode(op=op, left=left, right=right):
            left_val = evaluate(left)
            right_val = evaluate(right)
            match op:
                case TokenType.PLUS:
                    return left_val + right_val
                case TokenType.MINUS:
                    return left_val - right_val
                case TokenType.MULTIPLY:
                    return left_val * right_val
                case TokenType.DIVIDE:
                    if right_val == 0:
                        raise EvalError("division by zero")
                    return left_val / right_val
                case TokenType.POWER:
                    return left_val ** right_val

    raise EvalError(f"unknown node type: {type(node)}")


def evaluate_traced(node):
    """
    Like evaluate(), but records each step for educational display.
    Returns (result, list_of_trace_lines).

    The trace shows the topological evaluation order -- how the DAG
    is evaluated from leaves to root. Each step shows a node being
    evaluated after all its dependencies are resolved.
    """
    steps = []
    counter = [0]  # mutable counter for step numbering

    def _walk(node, depth):
        indent = "  " * depth
        counter[0] += 1
        step = counter[0]

        match node:
            case NumberNode(value=v):
                result = v
                display = _format_number(v)
                steps.append(f"{indent}Step {step}: {display} => {_format_number(result)}")
                return result

            case UnaryOpNode(op=TokenType.UNARY_MINUS, operand=child):
                child_val = _walk(child, depth + 1)
                result = -child_val
                counter[0] += 1
                step = counter[0]
                steps.append(
                    f"{indent}Step {step}: neg({_format_number(child_val)}) "
                    f"=> {_format_number(result)}"
                )
                return result

            case BinOpNode(op=op, left=left, right=right):
                left_val = _walk(left, depth + 1)
                right_val = _walk(right, depth + 1)
                sym = OP_SYMBOLS[op]
                match op:
                    case TokenType.PLUS:
                        result = left_val + right_val
                    case TokenType.MINUS:
                        result = left_val - right_val
                    case TokenType.MULTIPLY:
                        result = left_val * right_val
                    case TokenType.DIVIDE:
                        if right_val == 0:
                            raise EvalError("division by zero")
                        result = left_val / right_val
                    case TokenType.POWER:
                        result = left_val ** right_val
                counter[0] += 1
                step = counter[0]
                steps.append(
                    f"{indent}Step {step}: {_format_number(left_val)} {sym} "
                    f"{_format_number(right_val)} => {_format_number(result)}"
                )
                return result

        raise EvalError(f"unknown node type: {type(node)}")

    result = _walk(node, 0)
    return result, steps


def _format_number(v):
    """Display a number as integer when possible."""
    if isinstance(v, float) and v == int(v):
        return str(int(v))
    return str(v)