Resolusi Scope

"""Resolver scope untuk bahasa mini v1.

Antarmuka publik:
    Resolver(strict=True).resolve(program) -> list[ResolutionError]

Memakai AST dari topik desain-ast dan SymbolTable dari topik tabel-simbol.
Token, Lexer, AST, dan Parser disertakan ulang dari modul 1 dan 2 agar
berkas berdiri sendiri. Posisi sumber (line, column) dilampirkan ke
node AST lewat atribut _line dan _column tanpa mengubah struktur field
class, sehingga kontrak AST pada topik desain-ast tetap stabil.

Modus ketat menolak pemakaian nama sebelum deklarasi pada scope yang
sama. Modus longgar menjalankan pre-scan atas tiap blok untuk
mendefinisikan seluruh Let lebih dulu, sehingga referensi maju
diperbolehkan.
"""
from __future__ import annotations
from collections import namedtuple
from dataclasses import dataclass, field
from typing import Any


# ----- Token (salinan ringkas dari modul 1) -----
Token = namedtuple("Token", ["type", "lexeme", "line", "column"])

KEYWORDS = frozenset({
    "let", "print", "if", "else", "while",
    "true", "false", "nil", "and", "or",
})


# ----- Lexer ringkas (salinan dari modul 1) -----
DUA_KARAKTER = {"<=", ">=", "==", "!="}
SATU_KARAKTER = set("+-*/<>!=")
PUNCT = set("(){}")


class Lexer:
    def __init__(self, source: str):
        self.src = source
        self.pos = 0
        self.line = 1
        self.column = 1

    def _peek(self, offset: int = 0) -> str:
        idx = self.pos + offset
        if idx >= len(self.src):
            return ""
        return self.src[idx]

    def _advance(self) -> str:
        ch = self.src[self.pos]
        self.pos += 1
        if ch == "\n":
            self.line += 1
            self.column = 1
        else:
            self.column += 1
        return ch

    def _at_end(self) -> bool:
        return self.pos >= len(self.src)

    def tokens(self) -> list[Token]:
        out: list[Token] = []
        while not self._at_end():
            ch = self._peek()
            if ch in " \t\r\n":
                self._advance()
                continue
            if ch == "/" and self._peek(1) == "/":
                while not self._at_end() and self._peek() != "\n":
                    self._advance()
                continue
            if ch.isalpha() or ch == "_":
                out.append(self._identifier())
                continue
            if ch.isdigit():
                out.append(self._angka())
                continue
            if ch == '"':
                out.append(self._string())
                continue
            if ch in PUNCT:
                line, col = self.line, self.column
                self._advance()
                out.append(Token("PUNCT", ch, line, col))
                continue
            if ch in SATU_KARAKTER:
                out.append(self._operator())
                continue
            self._advance()
        out.append(Token("EOF", "", self.line, self.column))
        return out

    def _identifier(self) -> Token:
        line, col = self.line, self.column
        start = self.pos
        while not self._at_end() and (self._peek().isalnum() or self._peek() == "_"):
            self._advance()
        lex = self.src[start:self.pos]
        kelas = "KEYWORD" if lex in KEYWORDS else "IDENTIFIER"
        return Token(kelas, lex, line, col)

    def _angka(self) -> Token:
        line, col = self.line, self.column
        start = self.pos
        while not self._at_end() and self._peek().isdigit():
            self._advance()
        if self._peek() == "." and self._peek(1).isdigit():
            self._advance()
            while not self._at_end() and self._peek().isdigit():
                self._advance()
        return Token("NUMBER", self.src[start:self.pos], line, col)

    def _string(self) -> Token:
        line, col = self.line, self.column
        self._advance()
        start = self.pos
        while not self._at_end() and self._peek() != '"':
            self._advance()
        lex = '"' + self.src[start:self.pos] + '"'
        if not self._at_end():
            self._advance()
        return Token("STRING", lex, line, col)

    def _operator(self) -> Token:
        line, col = self.line, self.column
        dua = self._peek() + self._peek(1)
        if dua in DUA_KARAKTER:
            self._advance()
            self._advance()
            return Token("OPERATOR", dua, line, col)
        ch = self._advance()
        return Token("OPERATOR", ch, line, col)


# ----- AST (salinan ringkas dari topik desain-ast) -----
@dataclass
class Expr:
    pass


@dataclass
class Binary(Expr):
    left: Expr
    op: str
    right: Expr


@dataclass
class Unary(Expr):
    op: str
    operand: Expr


@dataclass
class Literal(Expr):
    value: Any


@dataclass
class Variable(Expr):
    name: str


@dataclass
class Assign(Expr):
    name: str
    value: Expr


@dataclass
class Logical(Expr):
    left: Expr
    op: str
    right: Expr


@dataclass
class Grouping(Expr):
    expression: Expr


@dataclass
class Stmt:
    pass


@dataclass
class Let(Stmt):
    name: str
    initializer: Expr


@dataclass
class Print(Stmt):
    expression: Expr


@dataclass
class If(Stmt):
    condition: Expr
    then_branch: Stmt
    else_branch: Stmt | None = None


@dataclass
class While(Stmt):
    condition: Expr
    body: Stmt


@dataclass
class Block(Stmt):
    statements: list[Stmt] = field(default_factory=list)


@dataclass
class Expression(Stmt):
    expression: Expr


@dataclass
class Program:
    statements: list[Stmt] = field(default_factory=list)


# ----- Parser (ringkas, dengan penanda posisi pada AST) -----
class ParseError(Exception):
    pass


def _tag(node, tok):
    """Lampirkan posisi sumber ke node AST tanpa mengubah field."""
    node._line = tok.line
    node._column = tok.column
    return node


class Parser:
    def __init__(self, tokens: list[Token]):
        self.tokens = tokens
        self.pos = 0

    def parse(self) -> Program:
        statements: list[Stmt] = []
        while not self._is_at_end():
            statements.append(self.statement())
        return Program(statements)

    def _peek(self) -> Token:
        return self.tokens[self.pos]

    def _previous(self) -> Token:
        return self.tokens[self.pos - 1]

    def _is_at_end(self) -> bool:
        return self._peek().type == "EOF"

    def _advance(self) -> Token:
        if not self._is_at_end():
            self.pos += 1
        return self._previous()

    def _check(self, type_, lexeme=None) -> bool:
        tok = self._peek()
        if tok.type != type_:
            return False
        return lexeme is None or tok.lexeme == lexeme

    def _match(self, type_, lexeme=None) -> bool:
        if self._check(type_, lexeme):
            self._advance()
            return True
        return False

    def _match_any(self, type_, lexemes) -> bool:
        tok = self._peek()
        if tok.type == type_ and tok.lexeme in lexemes:
            self._advance()
            return True
        return False

    def _consume(self, type_, lexeme, message) -> Token:
        if self._check(type_, lexeme):
            return self._advance()
        raise self._error(self._peek(), message)

    def _error(self, tok, message) -> ParseError:
        return ParseError(f"pada {tok.line}:{tok.column}: {message}")

    def statement(self) -> Stmt:
        if self._check("KEYWORD", "let"):
            return self.let_statement()
        if self._check("KEYWORD", "print"):
            return self.print_statement()
        if self._check("KEYWORD", "if"):
            return self.if_statement()
        if self._check("KEYWORD", "while"):
            return self.while_statement()
        if self._check("PUNCT", "{"):
            return self.block()
        return self.expression_statement()

    def let_statement(self) -> Let:
        self._advance()
        name_tok = self._consume("IDENTIFIER", None,
                                 "identifier diperlukan setelah 'let'")
        self._consume("OPERATOR", "=",
                      "'=' diperlukan setelah identifier pada pernyataan let")
        value = self.expression()
        return _tag(Let(name_tok.lexeme, value), name_tok)

    def print_statement(self) -> Print:
        kw = self._advance()  # 'print'
        value = self.expression()
        node = Print(value)
        node._line = kw.line
        node._column = kw.column
        return node

    def if_statement(self) -> If:
        self._advance()
        cond = self.expression()
        then_branch = self.block()
        else_branch = None
        if self._match("KEYWORD", "else"):
            else_branch = self.block()
        return If(cond, then_branch, else_branch)

    def while_statement(self) -> While:
        self._advance()
        cond = self.expression()
        body = self.block()
        return While(cond, body)

    def block(self) -> Block:
        self._consume("PUNCT", "{", "'{' diperlukan untuk memulai blok")
        statements: list[Stmt] = []
        while not self._check("PUNCT", "}") and not self._is_at_end():
            statements.append(self.statement())
        self._consume("PUNCT", "}", "'}' diperlukan untuk menutup blok")
        return Block(statements)

    def expression_statement(self) -> Expression:
        expr = self.expression()
        return Expression(expr)

    def expression(self) -> Expr:
        return self.assignment()

    def assignment(self) -> Expr:
        expr = self.logic_or()
        if self._match("OPERATOR", "="):
            value = self.assignment()
            if isinstance(expr, Variable):
                return _tag(Assign(expr.name, value), expr)
            raise self._error(self._previous(), "target penetapan tidak valid")
        return expr

    def logic_or(self) -> Expr:
        expr = self.logic_and()
        while self._match("KEYWORD", "or"):
            op_tok = self._previous()
            right = self.logic_and()
            expr = _tag(Logical(expr, "or", right), op_tok)
        return expr

    def logic_and(self) -> Expr:
        expr = self.equality()
        while self._match("KEYWORD", "and"):
            op_tok = self._previous()
            right = self.equality()
            expr = _tag(Logical(expr, "and", right), op_tok)
        return expr

    def equality(self) -> Expr:
        expr = self.comparison()
        while self._match_any("OPERATOR", {"==", "!="}):
            op_tok = self._previous()
            right = self.comparison()
            expr = _tag(Binary(expr, op_tok.lexeme, right), op_tok)
        return expr

    def comparison(self) -> Expr:
        expr = self.term()
        while self._match_any("OPERATOR", {"<", "<=", ">", ">="}):
            op_tok = self._previous()
            right = self.term()
            expr = _tag(Binary(expr, op_tok.lexeme, right), op_tok)
        return expr

    def term(self) -> Expr:
        expr = self.factor()
        while self._match_any("OPERATOR", {"+", "-"}):
            op_tok = self._previous()
            right = self.factor()
            expr = _tag(Binary(expr, op_tok.lexeme, right), op_tok)
        return expr

    def factor(self) -> Expr:
        expr = self.unary()
        while self._match_any("OPERATOR", {"*", "/"}):
            op_tok = self._previous()
            right = self.unary()
            expr = _tag(Binary(expr, op_tok.lexeme, right), op_tok)
        return expr

    def unary(self) -> Expr:
        if self._match_any("OPERATOR", {"-", "!"}):
            op_tok = self._previous()
            operand = self.unary()
            return _tag(Unary(op_tok.lexeme, operand), op_tok)
        return self.primary()

    def primary(self) -> Expr:
        if self._match("KEYWORD", "true"):
            return Literal(True)
        if self._match("KEYWORD", "false"):
            return Literal(False)
        if self._match("KEYWORD", "nil"):
            return Literal(None)
        if self._match("NUMBER", None):
            tok = self._previous()
            if "." in tok.lexeme:
                return Literal(float(tok.lexeme))
            return Literal(int(tok.lexeme))
        if self._match("STRING", None):
            tok = self._previous()
            return Literal(tok.lexeme[1:-1])
        if self._match("IDENTIFIER", None):
            tok = self._previous()
            return _tag(Variable(tok.lexeme), tok)
        if self._match("PUNCT", "("):
            inner = self.expression()
            self._consume("PUNCT", ")", "')' diperlukan setelah ekspresi")
            return Grouping(inner)
        raise self._error(self._peek(), "ekspresi diperlukan")


# ----- Symbol (salinan ringkas dari topik tabel-simbol) -----
@dataclass
class Symbol:
    name: str
    kind: str
    declared_line: int
    declared_column: int


class SemanticError(Exception):
    pass


class Scope:
    def __init__(self, parent: "Scope | None" = None) -> None:
        self.parent = parent
        self.symbols: dict[str, Symbol] = {}


class SymbolTable:
    def __init__(self) -> None:
        self.root = Scope()
        self.current = self.root
        self.depth = 0

    def push(self) -> Scope:
        self.current = Scope(parent=self.current)
        self.depth += 1
        return self.current

    def pop(self) -> None:
        if self.current.parent is None:
            raise SemanticError("tidak dapat menutup scope global")
        self.current = self.current.parent
        self.depth -= 1

    def define(self, name: str, symbol: Symbol) -> Symbol:
        if name in self.current.symbols:
            existing = self.current.symbols[name]
            raise SemanticError(
                f"nama {name!r} sudah dideklarasikan pada "
                f"{existing.declared_line}:{existing.declared_column}"
            )
        self.current.symbols[name] = symbol
        return symbol

    def resolve(self, name: str) -> Symbol | None:
        scope: Scope | None = self.current
        while scope is not None:
            if name in scope.symbols:
                return scope.symbols[name]
            scope = scope.parent
        return None


# ----- Resolver -----
@dataclass
class ResolutionError:
    """Error resolusi sebagai data terstruktur."""
    line: int
    column: int
    name: str
    kind: str   # "undefined" | "use-before-def" | "redeclare" | "assign-undefined"
    message: str


class Resolver:
    def __init__(self, strict: bool = True) -> None:
        self.strict = strict
        self.symbols = SymbolTable()
        self.errors: list[ResolutionError] = []
        # Tiap entri pada stack ini adalah set nama yang dideklarasikan
        # pada scope saat ini, diisi saat pre-scan. Dipakai untuk membedakan
        # "use-before-def" dari "undefined" pada modus ketat.
        self._declared_in_scope: list[set[str]] = []

    def resolve(self, program: Program) -> list[ResolutionError]:
        self.symbols = SymbolTable()
        self.errors = []
        self._declared_in_scope = []
        self._block(program.statements, push_scope=False)
        return self.errors

    def _block(self, statements, push_scope: bool) -> None:
        if push_scope:
            self.symbols.push()
        self._declared_in_scope.append(set())
        # Pre-scan: nama Let di scope ini dicatat. Modus longgar
        # langsung mendefinisikan, modus ketat hanya mencatat untuk
        # membedakan use-before-def dari undefined.
        if not self.strict:
            for s in statements:
                if isinstance(s, Let):
                    self._declare(s)
                    self._declared_in_scope[-1].add(s.name)
        else:
            for s in statements:
                if isinstance(s, Let):
                    self._declared_in_scope[-1].add(s.name)
        for s in statements:
            self._stmt(s)
        self._declared_in_scope.pop()
        if push_scope:
            self.symbols.pop()

    def _stmt(self, s: Stmt) -> None:
        if isinstance(s, Let):
            if self.strict:
                self._declare(s)
            self._expr(s.initializer)
        elif isinstance(s, Print):
            self._expr(s.expression)
        elif isinstance(s, Expression):
            self._expr(s.expression)
        elif isinstance(s, If):
            self._expr(s.condition)
            self._stmt(s.then_branch)
            if s.else_branch is not None:
                self._stmt(s.else_branch)
        elif isinstance(s, While):
            self._expr(s.condition)
            self._stmt(s.body)
        elif isinstance(s, Block):
            self._block(s.statements, push_scope=True)

    def _declare(self, s: Let) -> None:
        line = getattr(s, "_line", 0)
        col = getattr(s, "_column", 0)
        sym = Symbol(s.name, "var", line, col)
        try:
            self.symbols.define(s.name, sym)
        except SemanticError as e:
            self.errors.append(ResolutionError(
                line=line, column=col, name=s.name,
                kind="redeclare", message=str(e)))

    def _expr(self, e: Expr) -> None:
        if isinstance(e, Variable):
            self._use(e, getattr(e, "_line", 0), getattr(e, "_column", 0),
                      is_assign=False)
        elif isinstance(e, Assign):
            self._use(e, getattr(e, "_line", 0), getattr(e, "_column", 0),
                      is_assign=True)
            self._expr(e.value)
        elif isinstance(e, (Binary, Logical)):
            self._expr(e.left)
            self._expr(e.right)
        elif isinstance(e, Unary):
            self._expr(e.operand)
        elif isinstance(e, Grouping):
            self._expr(e.expression)

    def _use(self, e, line, column, is_assign: bool) -> None:
        sym = self.symbols.resolve(e.name)
        if sym is not None:
            return
        if self._declared_in_scope and e.name in self._declared_in_scope[-1]:
            kind = "use-before-def"
            msg = (f"nama {e.name!r} dipakai sebelum dideklarasikan "
                   f"pada scope ini (modus ketat)")
        else:
            kind = "assign-undefined" if is_assign else "undefined"
            msg = (f"nama {e.name!r} tidak terdefinisi"
                   + (" pada penetapan" if is_assign else ""))
        self.errors.append(ResolutionError(
            line=line, column=column, name=e.name, kind=kind, message=msg))


def parse(source: str) -> Program:
    return Parser(Lexer(source).tokens()).parse()


def main() -> None:
    source = (
        "let x = 1\n"
        "{\n"
        "  let x = 2\n"
        "  print x\n"
        "}\n"
        "print x\n"
    )
    print("=== Sumber ===")
    print(source, end="")
    program = parse(source)

    print()
    print("=== Modus ketat (shadowing diperbolehkan) ===")
    errors = Resolver(strict=True).resolve(program)
    if not errors:
        print("(tidak ada error resolusi)")
    for e in errors:
        print(f"  {e.line}:{e.column} [{e.kind}] {e.name}: {e.message}")

    print()
    print("=== Modus longgar ===")
    errors = Resolver(strict=False).resolve(program)
    if not errors:
        print("(tidak ada error resolusi)")
    for e in errors:
        print(f"  {e.line}:{e.column} [{e.kind}] {e.name}: {e.message}")

    print()
    print("=== Pemakaian sebelum definisi ===")
    bad = "print y\nlet y = 10\n"
    print(bad, end="")
    p2 = parse(bad)
    print("-- ketat --")
    for e in Resolver(strict=True).resolve(p2):
        print(f"  {e.line}:{e.column} [{e.kind}] {e.name}: {e.message}")
    print("-- longgar --")
    for e in Resolver(strict=False).resolve(p2):
        print(f"  {e.line}:{e.column} [{e.kind}] {e.name}: {e.message}")

    print()
    print("=== Redeclarasi pada scope yang sama ===")
    dup = "let z = 1\nlet z = 2\n"
    print(dup, end="")
    p3 = parse(dup)
    for e in Resolver(strict=True).resolve(p3):
        print(f"  {e.line}:{e.column} [{e.kind}] {e.name}: {e.message}")


if __name__ == "__main__":
    main()

=== Sumber ===
let x = 1
{
  let x = 2
  print x
}
print x

=== Modus ketat (shadowing diperbolehkan) ===
(tidak ada error resolusi)

=== Modus longgar ===
(tidak ada error resolusi)

=== Pemakaian sebelum definisi ===
print y
let y = 10
-- ketat --
  1:7 [use-before-def] y: nama 'y' dipakai sebelum dideklarasikan pada scope ini (modus ketat)
-- longgar --

=== Redeclarasi pada scope yang sama ===
let z = 1
let z = 2
  2:5 [redeclare] z: nama 'z' sudah dideklarasikan pada 1:5