private fun matchFnPattern(
    pattern: FnPattern,
    fn: Functions.Fn,
    bindings: MutableMap<String, Functions.Fn>
): Boolean = when (pattern) {
    is FnPattern.Wild -> true

    is FnPattern.Var -> {
        val existing = bindings[pattern.name]
        if (existing == null) {
            bindings[pattern.name] = fn
            true
        } else {
            existing.graphSignature() == fn.graphSignature()
        }
    }

    is FnPattern.Num -> {
        val value = fn.graphNode().numbers["value"]
        value != null && abs(value - pattern.value) < 1e-12
    }

    is FnPattern.Op -> {
        val node = fn.graphNode()
        if (!opNamesMatch(pattern.op, node.op)) {
            false
        } else if (!pattern.constrained) {
            true
        } else {
            pattern.children.withIndex().all { (index, childPattern) ->
                val child = node.children.getOrNull(index)?.fn
                child != null && matchFnPattern(childPattern, child, bindings)
            }
        }
    }
}

private fun opNamesMatch(patternOp: String, nodeOp: String): Boolean {
    if (patternOp.equals(nodeOp, ignoreCase = true)) return true
    val a = OpRegistry.canonical(patternOp) ?: patternOp
    val b = OpRegistry.canonical(nodeOp) ?: nodeOp
    return a.equals(b, ignoreCase = true)
}

private val ALGEBRA_OPS = setOf("add", "subtract", "multiply", "divide", "+", "-", "*", "/")

private fun buildFnTemplate(
    template: FnPattern,
    bindings: Map<String, Functions.Fn>,
    matched: Functions.Fn
): Functions.Fn = when (template) {
    is FnPattern.Wild -> matched

    is FnPattern.Var ->
        bindings[template.name] ?: error("Template references unbound metavariable ?${template.name}")

    is FnPattern.Num -> Functions.c(template.value, matched.domain)

    is FnPattern.Op -> when {
        // bare op (no child list): transmute the matched node, preserving its children.
        !template.constrained -> matched.rebuildAsOp(template.op) ?: matched

        // algebra ops build directly from two child templates.
        OpRegistry.canonical(template.op)?.lowercase() in ALGEBRA_OPS || template.op.lowercase() in ALGEBRA_OPS -> {
            require(template.children.size == 2) { "Algebra op `${template.op}` needs two operands in a template" }
            val left = buildFnTemplate(template.children[0], bindings, matched)
            val right = buildFnTemplate(template.children[1], bindings, matched)
            val canonical = OpRegistry.canonical(template.op)?.lowercase() ?: template.op.lowercase()
            with(Functions) {
                when (canonical) {
                    "add", "+" -> left + right
                    "subtract", "-" -> left - right
                    "multiply", "*" -> left * right
                    "divide", "/" -> left / right
                    else -> error("unreachable")
                }
            }
        }

        else -> error(
            "Template op `${template.op}(...)` with explicit children is limited to algebra " +
                "(add/subtract/multiply/divide) in the string DSL. Use a bare op to transmute the " +
                "matched node, or the programmatic fnRule(name, lhs) { ... } builder for full control."
        )
    }
}

private fun splitRuleArrow(spec: String): Pair<String, String> {
    val trimmed = spec.trim().removePrefix("#fnrewrite").trim()
    val arrows = listOf("=>", "->", "→")
    var index = -1
    var length = 0
    for (arrow in arrows) {
        val at = trimmed.indexOf(arrow)
        if (at >= 0 && (index < 0 || at < index)) {
            index = at
            length = arrow.length
        }
    }
    require(index >= 0) { "Pattern rule needs `lhs => rhs`: `$spec`" }
    val lhs = trimmed.substring(0, index).trim()
    val rhs = trimmed.substring(index + length).trim()
    require(lhs.isNotEmpty()) { "Pattern rule has an empty left-hand side: `$spec`" }
    require(rhs.isNotEmpty()) { "Pattern rule has an empty right-hand side: `$spec`" }
    return lhs to rhs
}

private class FnPatternParser(text: String) {
    private val s = text.trim()
    private var i = 0

    fun parseWhole(): FnPattern {
        val term = parseTerm()
        skipWs()
        require(i >= s.length) { "Unexpected trailing input in pattern `$s` at $i" }
        return term
    }

    private fun parseTerm(): FnPattern {
        skipWs()
        require(i < s.length) { "Empty pattern term in `$s`" }
        val c = s[i]
        if (c == '?') {
            i++
            val name = readIdent()
            require(name.isNotEmpty()) { "Metavariable needs a name in `$s`" }
            return FnPattern.Var(name)
        }
        if (c == '_' && !isIdentPart(s.getOrNull(i + 1))) {
            i++
            return FnPattern.Wild
        }
        if (c == '-' || c == '+' || c == '.' || c.isDigit()) {
            readNumber()?.let { return FnPattern.Num(it) }
        }
        val op = readIdentOrSymbol()
        require(op.isNotEmpty()) { "Expected an op name or metavariable in `$s` at $i" }
        skipWs()
        if (i < s.length && s[i] == '(') {
            i++ // consume (
            val children = mutableListOf<FnPattern>()
            skipWs()
            if (i < s.length && s[i] != ')') {
                while (true) {
                    children += parseTerm()
                    skipWs()
                    if (i < s.length && s[i] == ',') {
                        i++
                        continue
                    }
                    break
                }
            }
            skipWs()
            require(i < s.length && s[i] == ')') { "Unbalanced parentheses in pattern `$s`" }
            i++ // consume )
            return FnPattern.Op(op, children, constrained = true)
        }
        return FnPattern.Op(op, emptyList(), constrained = false)
    }

    private fun readNumber(): Double? {
        val start = i
        if (i < s.length && (s[i] == '-' || s[i] == '+')) i++
        var digits = false
        while (i < s.length && (s[i].isDigit() || s[i] == '.')) {
            digits = true
            i++
        }
        if (i < s.length && (s[i] == 'e' || s[i] == 'E')) {
            i++
            if (i < s.length && (s[i] == '-' || s[i] == '+')) i++
            while (i < s.length && s[i].isDigit()) i++
        }
        if (!digits) {
            i = start
            return null
        }
        val token = s.substring(start, i)
        val parsed = token.toDoubleOrNull()
        if (parsed == null) {
            i = start
            return null
        }
        return parsed
    }

    private fun readIdent(): String {
        val start = i
        while (i < s.length && isIdentPart(s[i])) i++
        return s.substring(start, i)
    }

    private fun readIdentOrSymbol(): String {
        skipWs()
        if (i < s.length && s[i] in "+-*/") {
            return s[i].toString().also { i++ }
        }
        return readIdent()
    }

    private fun isIdentPart(c: Char?): Boolean = c != null && (c.isLetterOrDigit() || c == '_')

    private fun skipWs() {
        while (i < s.length && s[i].isWhitespace()) i++
    }
}