csp_solve.nim

import tables, sequtils, sugar, macros, sets, heapqueue, strutils

## nimconstraint: A CSP-Solver written in Nim
##      Author: Timothy Hornick @Xydium
##      Date: 20 December, 2019

type
    Variable[T] = ref object
        ## Represents a Node in the CSP Graph
        name: string
            ## Unique name of the Variable
            ## TODO: Currently user-enforced
        domain: seq[T]
            ## Domain of the variable as a
            ## finite, ordered set
        value: T
            ## Current value of the variable,
            ## used to represent an assignment

    Constraint*[T] = ref object
        ## A function that subsets valid combinations
        ## of values for its variables. Represents
        ## an Arc or Multi-Arc in the CSP Graph
        variables: seq[Variable[T]]
            ## The list of Variable objects checked
        predicate: proc(x: varargs[T]): bool
            ## The function computing satisfaction

    Problem*[T] = ref object
        ## A CSP Graph with well-defined solving algorithms
        variables: TableRef[string, Variable[T]]
            ## Links the Names of Nodes to their Reference
        constraints: TableRef[string, seq[Constraint[T]]]
            ## Links the Names of Nodes to their Constraints

proc newProblem*[T](): Problem[T] =
    ## Returns an empty CSP Graph
    result = Problem[T](
        variables: newTable[string, Variable[T]](),
        constraints: newTable[string, seq[Constraint[T]]]()
    )

proc addVariable*[T](problem: Problem[T], name: string, domain: seq[T]) =
    ## Adds a named Node to the CSP Graph with the given domain
    let v = Variable[T](
        name: name,
        domain: domain
    )

    problem.variables.add(name, v)

proc addConstraint*[T](problem: Problem[T], predicate: (x: varargs[T]) -> bool,
    variables: varargs[string]) =
    ## Adds an N-Ary Constraint to the CSP Graph based on
    ## the number of Variable names supplied

    # Create the Constraint with direct Variable references
    let constraint = Constraint[T](
        variables: variables.map(s => problem.variables[s]),
        predicate: predicate
    )

    # Add the Constraint to the adjacency table
    for variable in constraint.variables:
        # Add a seq for the variable if needed
        discard problem.constraints.hasKeyOrPut(
            variable.name, newSeq[Constraint[T]]())

        problem.constraints[variable.name].add(constraint)

proc isUnary[T](constraint: Constraint[T]): bool =
    ## Returns whether the Constraint is Unary
    constraint.variables.len == 1

proc isBinary[T](constraint: Constraint[T]): bool =
    ## Returns whether the Constraint is Binary
    constraint.variables.len == 2

proc backtrack[T](problem: Problem[T], unassigned: seq[Variable[T]],
    assignment: TableRef[Variable[T], T]): bool =

    if unassigned.isEmpty:
        return # Assignment is Complete

    ## Select a variable
    let current = unassigned[0]

    ## Assign a variable
    for value in current.domain:
        assignment[current] = value

        ## Arc consistency -- preserve original domain
            ## Inconsistent? Continue
        ## N-ary consistency
            ## Inconsistent? Continue
        ## All clear?

        if problem.backtrack(unassigned[1..high(unassigned)], assignment):
            return true


    ## Perform arc consistency to check early inconsistent state
    ## Check any non-binary constraints involving the variable
    ## All clear? Recurse to next variable
    ## Not clear?

proc nodeConsistent[T](problem: Problem[T]): bool =
    ## Applies Node Consistency to all Nodes in the
    ## CSP Graph, subsetting domains for each constraint
    ##
    ## Return: Whether the Problem is Node Consistent
    for node in problem.variables.values:
        for constraint in problem.constraints[node.name]:
            # Node Consistency for Unary Constraints only
            if not constraint.isUnary: continue

            # There may be a faster way than constructing
            # a new seq, but as a 1-time step, not important.
            # Removing values is expensive, but is it more
            # expensive than constructing seqs
            var ncdomain = newSeq[T]()

            # Add the values which satisfy the unary constraint
            for value in node.domain:
                if constraint.predicate(value):
                    ncdomain.add(value)

            # Empty domain? Node is Inconsistent
            if ncdomain.len == 0:
                return false

            # Pass along the domain to the next constraint
            node.domain = ncdomain

    return true

proc search*[T](problem: Problem[T]): seq[tuple[name: string, value: T]] =
    ## Node Consistency
    discard

macro define*[T](problem: Problem[T], input: untyped): untyped =
    ## TODO: Remove looping/list
    result = newStmtList()

    for node in input:
        case node.kind:
        of nnkInfix:
            let name = node[1].strVal
            let domain = node[2]

            result.add quote do:
                `problem`.addVariable(`name`, `domain`)
        else:
            echo "Cannot Instantiate Variable without Infix Structure"
            echo node.treeRepr

proc parseVars(node: NimNode): (seq[string], NimNode) =
    ## Traverses the AST to find any identifiers
    ## and either replaces them with a constraint
    ## vararg access, or treats them as a Nim
    ## identifier if prefixed `u` or not alphanumeric.
    ##
    ## Return: The Variable names in AST First Occurence Order
    var variables = newTable[string, int]()
    var varOrder = newSeq[string]()

    proc inspect(node: NimNode): NimNode =
        result = node.copyNimNode

        for current in node:
            if current.kind == nnkIdent:
                if current.strVal[0] == 'u':
                    ## If tagged as a literal, keep it, but drop tag
                    result.add ident(current.strVal.substr(1))
                elif current.strVal.isAlphaNumeric:
                    ## Any untagged identifier is assumed a Variable
                    ## Track its order in the AST
                    if not variables.hasKeyOrPut(current.strVal, variables.len):
                        varOrder.add(current.strVal)

                    ## Then replace the Identifier with an Array Access
                    ## corresponding to its location in the constraint
                    result.add newNimNode(nnkBracketExpr).add(
                        ident("x"),
                        newIntLitNode(variables[current.strVal])
                    )
                else:
                    result.add current
            else:
                result.add inspect(current)

    return (varOrder, inspect(node))

macro constrain*(problem: Problem, input: untyped): untyped =

    let T = problem.getTypeInst()[1]

    var stmts = newStmtList()

    for i in 0..<input.len:
        let (vars, tree) = parseVars(input[i])

        let x = ident"x"

        var constcall = quote do: addConstraint(
            `problem`,
            proc(`x`: varargs[`T`]): bool = `tree`,
            `vars`)

        constcall[2][3][1][0] = ident"x"

        echo constcall.treeRepr

        stmts.add constcall

    return stmts

let test = newProblem[int]()

test.define:
    X in toSeq(0..9)
    Y in toSeq(0..9)

test.constrain:
    Y == X * X