# Copyright (c) 2025-2026, Chris Pressey, Cat's Eye Technologies.
# This file is distributed under a 2-clause BSD license.  See LICENSES/ dir.
# SPDX-License-Identifier: LicenseRef-BSD-2-Clause-X-Lome

from typing import Dict, Optional

from .term import Ctor, Term, is_variable, terms_equal


class MatchResult:
    def __init__(self, success: bool, bindings: Optional[Dict[str, Term]] = None):
        self.success = success
        self.bindings = bindings or {}


def match_term(pattern: Term, target: Term, bindings: Optional[Dict[str, Term]] = None) -> MatchResult:
    """
    Match a pattern term against a target term, collecting variable bindings.
    Variables are represented by single uppercase letters.
    """
    if bindings is None:
        bindings = {}

    if is_variable(pattern):
        assert isinstance(pattern, Ctor)
        if pattern.symbol in bindings:
            # Variable already bound, check if it matches
            if terms_equal(bindings[pattern.symbol], target):
                return MatchResult(True, bindings)
            else:
                return MatchResult(False)
        else:
            # Variable not bound yet, so bind it
            bindings = bindings.copy()
            bindings[pattern.symbol] = target
            return MatchResult(True, bindings)

    if pattern.symbol != target.symbol:
        return MatchResult(False)
    if len(pattern.subterms) != len(target.subterms):
        return MatchResult(False)

    # Recursively match all subterms, too
    current_bindings = bindings.copy()
    for pattern_sub, target_sub in zip(pattern.subterms, target.subterms):
        result = match_term(pattern_sub, target_sub, current_bindings)
        if not result.success:
            return MatchResult(False)
        current_bindings = result.bindings

    return MatchResult(True, current_bindings)


def substitute_term(term: Term, bindings: Dict[str, Term]) -> Term:
    """
    Substitute variables in a term with their bindings.
    """
    if not isinstance(term, Ctor):
        return term

    if is_variable(term) and term.symbol in bindings:
        return bindings[term.symbol]

    if term.subterms:
        new_subterms = [substitute_term(subterm, bindings) for subterm in term.subterms]
        return Ctor(term.symbol, new_subterms)
    else:
        return term