#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""Expression system.

Like a filesystem shell, but made of expressions.

Status: running a REPL with ephemeral history, tokenizing expressions,
parsing them, evaluating them.  No longer crashes on every error.
Parse errors are all incorrect.  Usable as a sort of infix
floating-point calculator with autorecalc.  No hierarchy or
persistence yet.  Probably buggy as shit.  Definitely buggy with
circular references.  But hey, it’s what I managed in five hours
when I should have been sleeping.

Example session follows; the ¿whatever? is the prompt:

    : user@debian:~/devel/dev3; ./expsystem.py
    ¿a? r1: 1000
    r1: 1000 (1000)
    ¿a? r2: 2033
    r2: 2033 (2033)
    ¿a? vcc: 5
    vcc: 5 (5)
    ¿a? vr2: vcc * r2 / (r1 + r2)
    vr2: 3.3514671941971645 (vcc * r2 / (r1 + r2))
    ¿a? r2: 190
    r2: 190 (190)
    vr2: 0.7983193277310925 (vcc * r2 / (r1 + r2))
    ¿a? r2: 500
    r2: 500 (500)
    vr2: 1.6666666666666667 (vcc * r2 / (r1 + r2))
    ¿a? r3: 1000
    r3: 1000 (1000)
    ¿a? r4: 637
    r4: 637 (637)
    ¿a? vr4: vcc * r4 / (r3 + r4)
    vr4: 1.9456322541233964 (vcc * r4 / (r3 + r4))
    ¿a? dv: vr4 - vr2
    dv: 0.2789655874567296 (vr4 - vr2)
    ¿a? r2: 300
    r2: 300 (300)
    vr2: 1.1538461538461537 (vcc * r2 / (r1 + r2))
    dv: 0.7917861002772426 (vr4 - vr2)
    ¿a? r2: 600
    r2: 600 (600)
    vr2: 1.875 (vcc * r2 / (r1 + r2))
    dv: 0.07063225412339635 (vr4 - vr2)
    ¿a? r2: 700
    r2: 700 (700)
    vr2: 2.0588235294117645 (vcc * r2 / (r1 + r2))
    dv: -0.11319127528836814 (vr4 - vr2)
    ¿a? .l
    dv: -0.11319127528836814 (vr4 - vr2)
    r1: 1000 (1000)
    r2: 700 (700)
    r3: 1000 (1000)
    r4: 637 (637)
    vcc: 5 (5)
    vr2: 2.0588235294117645 (vcc * r2 / (r1 + r2))
    vr4: 1.9456322541233964 (vcc * r4 / (r3 + r4))
    ¿a? 1 / (1/(r1+r2) + 1/(r3 + r4))
    a: 833.952652082709 (1 / (1 / (r1 + r2) + 1 / (r3 + r4)))
    ¿b? .bye
    Buh-bye!

"""
from __future__ import print_function
import readline, sys, re, operator, traceback
from collections import namedtuple

try:
    input = raw_input
except NameError:
    pass

cmds = {}

def cmd(name):
    def wrap(f):
        cmds[name] = f
        return f

    return wrap

@cmd(".help")
@cmd("help")
def help(shell, args):
    print("""Available commands:
    help -- this message
    .bye -- quit
    .r var -- delete expression named var
    .l -- list the expressions here
    .s var -- see the expression named var

    Numeric expression syntax is infix, e.g.:

        label: 1 / (1/(r1+r2) + 1/(r3 + r4))

    You are not required to provide a label; if you do not provide a
    label, one will be provided for you.  You have the right to remain
    calculating.
    """)

@cmd(".bye")
def bye(shell, args):
    print("Buh-bye!")
    sys.exit(0)

@cmd('.r')
def delete_var(shell, args):
    shell.remove(args[1])

@cmd('.l')
def list_vars(shell, args):
    for var in sorted(shell.fs):
        print(display_var(shell.fs[var], shell.vals.get(var)))

@cmd('.s')
def show_var(shell, args):
    print(display_var(shell.fs[args[1]], shell.vals.get(args[1])))

# For things other than meta-commands, that is to say expressions and
# assignments, we try parsing them with this simple recursive descent
# parser.

# Did I say “simple”?  This thing fucking sucks.

token = namedtuple('token', ('type', 'content', 'column'))

def tokenize(line):
    # Let’s tokenize!
    # Following the example in https://docs.python.org/3/library/re.html
    for mo in re.finditer(r'''
              (?P<num> \d+ (?:\.\d*)? | \.\d+) \s*
            | (?P<op> \*\* | [-:+*/%^]) \s* 
            | (?P<paren> [()]) \s*
            | (?P<id> [a-zA-Z$_] \w* ) \s* 
            | (?P<err> .)
            ''', line, re.VERBOSE):
        yield token(type=mo.lastgroup, content=mo.group(mo.lastgroup), column=mo.start())

ops = { '+': operator.add, '-': operator.sub, '*': operator.mul,
        '/': operator.truediv, '%': operator.mod, '**': operator.pow,
        '^': operator.pow }

# For display:
precedences = { '+': 1, '-': 1, '*': 2, '/': 2, '%': 2, '**': 3, '^': 3 }

eitem = namedtuple('eitem', ('name', 'expr'))


class binop(namedtuple('binop', ('op', 'a', 'b'))):
    def eval(self, context):
        a = self.a.eval(context)
        b = self.b.eval(context)
        #print('combining', self.op, a, b)
        return ops[self.op](a, b)
    
    def show(self, left, right):
        "Render for display, sensitive to left and right operator precedences."
        mine = precedences[self.op]
        a = self.a.show(left=0, right=mine)
        b = self.b.show(left=mine, right=0)
        s = '%s %s %s' % (a, self.op, b)
        return '(%s)' % s if mine <= left or mine < right else s

class varnode(namedtuple('var', ('name',))):
    def eval(self, context):
        return context[self.name]

    def show(self, left, right):
        return self.name

class constnode(namedtuple('const', ('value',))):
    def eval(self, context):
        return self.value

    def show(self, left, right):
        return str(self.value)

parse_err = namedtuple('parse_err', ('token', 'wish'))


def parse_line(line):
    tokens = list(tokenize(line))
    for tok in tokens:
        pass#print('got', tok)

    result, trailing = parse_assignment(tokens)
    if not trailing and not isinstance(result, parse_err):
        return result

    result2, trailing = parse_expr(tokens)
    if not trailing and not isinstance(result2, parse_err):
        return eitem(name=None, expr=result2)

    if isinstance(result, parse_err) and not isinstance(result2, parse_err):
        return result
    if not isinstance(result, parse_err):
        return result2
    if result.token is not None and result2.token is None:
        return result
    if result.token is None:
        return result2

    return max([result, result2], key=lambda err: err.token.column)

def parse_assignment(tokens):
    if tokens[0].type != 'id':
        return parse_err(tokens[0], wish='identifier'), tokens

    var = tokens[0].content
    if len(tokens) < 2 or tokens[1].content != ':':
        return parse_err(tokens[1] if tokens[1:] else None, wish=':'), tokens[1:]

    expr, trailing = parse_expr(tokens[2:])
    if isinstance(expr, parse_err):
        return expr, trailing

    # XXX maybe use some fucking exceptions
    return eitem(name=var, expr=expr), trailing

def parse_expr(tokens):
    expr, trailing = parse_term(tokens)
    if isinstance(expr, parse_err):
        return expr, trailing

    while trailing and trailing[0].content in ('+', '-'):
        op = trailing[0].content
        next_term, new_trailing = parse_term(trailing[1:])
        if isinstance(next_term, parse_err):
            break   # don’t propagate the error
        trailing = new_trailing
        expr = binop(op=op, a=expr, b=next_term)

    return expr, trailing

def parse_term(tokens):
    # No unary ops yet, so our choices are an atomic expression (var,
    # constant, or parenthesized) with zero or more multiplicative
    # things tagged onto the end.
    expr, trailing = parse_exp(tokens)
    if isinstance(expr, parse_err):
        return expr, trailing

    while trailing and trailing[0].content in ('*', '/', '%'):
        op = trailing[0].content
        next_factor, new_trailing = parse_exp(trailing[1:])
        if isinstance(next_factor, parse_err):
            break

        trailing = new_trailing
        expr = binop(op=op, a=expr, b=next_factor)

    return expr, trailing

def parse_exp(tokens):
    expr, trailing = parse_atomic(tokens)
    if isinstance(expr, parse_err):
        return expr, trailing

    while trailing and trailing[0].content in ('**', '^'):
        next_power, new_trailing = parse_exp(trailing[1:])
        if isinstance(next_power, parse_err):
            break

        trailing = new_trailing
        # XXX this associates to the left (3**4**5 is (3**4)**5); is
        # that OK?
        expr = binop(op='**', a=expr, b=next_power)

    return expr, trailing

def parse_atomic(tokens):
    wish = 'var, number, or left parenthesis'
    if not tokens:
        return parse_err(None, wish=wish), tokens

    if tokens[0].type == 'id':
        return varnode(tokens[0].content), tokens[1:]

    if tokens[0].content == '(':
        expr, trailing = parse_expr(tokens[1:])
        if isinstance(expr, parse_err):
            return expr, trailing
        if not trailing:
            return parse_err(None, wish='right parenthesis'), trailing
        if trailing[0].content != ')':
            return parse_err(trailing[0], wish='right parenthesis'), trailing

        return expr, trailing[1:]

    if tokens[0].type == 'num':
        if '.' in tokens[0].content:
            val = float(tokens[0].content)
        else:
            val = int(tokens[0].content)

        return constnode(val), tokens[1:]

    return parse_err(None, wish=wish), tokens


def display_var(ei, val):
    return '%s: %s (%s)' % (ei.name, val, ei.expr.show(0, 0))

class Graph:
    def __init__(self):
        self.forward = {}
        self.backward = {}

    def add(self, a, b):
        if a not in self.forward:
            self.forward[a] = set()
        self.forward[a].add(b)

        if b not in self.backward:
            self.backward[b] = set()
        self.backward[b].add(a)

    def remove(self, a, b):
        if a in self.forward:
            self.forward[a].remove(b)
        if b in self.backward:
            self.backward[b].remove(a)

    def get(self, a):
        return self.forward.get(a, set()).copy()

    def get_back(self, b):
        return self.backward.get(b, set()).copy()


class Shell:
    def __init__(self):
        self.fs = {}
        self.next_name = 'a'
        self.deps = Graph()
        self.vals = {}
        self.updates = []

    def increment_name(self):
        if all(c == 'z' for c in self.next_name):
            self.next_name = 'a' * (len(self.next_name) + 1)
            return

        i = len(self.next_name) - 1
        while self.next_name[i] == 'z':
            i -= 1
        # if name == 'aczz' then i == 1
        self.next_name = (self.next_name[:i]
                          + chr(ord(self.next_name[i]) + 1)
                          + 'a' * (len(self.next_name) - i - 1))

    def repl(self):
        print('Type help for help.')
        while True:
            while self.next_name in self.fs:
                self.increment_name()

            for name in self.updates:
                print(display_var(self.fs[name], self.vals[name]))
            self.updates = []

            prompt = '¿%s? ' % self.next_name
            line = input(prompt).strip() # XXX output to the right of formula would be nicer
            if not line:
                continue

            try:
                self.run(line, len(prompt))
            except Exception:
                traceback.print_exc()

    def run(self, line, prompt_len):
        cb = cmds.get(line.split()[0])
        if cb:
            cb(self, line.split())
        else:
            parsed = parse_line(line)
            #print('parsed as', parsed)
            if isinstance(parsed, parse_err):
                if parsed.token:
                    print(' ' * (prompt_len + parsed.token.column) + '↑')
                print("parsing failed here, hoping for", parsed.wish)
                return # XXX typing nonsense, lacking exception handling

            if parsed.name is None:
                while self.next_name in self.fs:
                    self.increment_name()

                parsed = eitem(name=self.next_name, expr=parsed.expr)

            assert isinstance(parsed, eitem), parsed
            self.fs[parsed.name] = parsed
            self.update(parsed.name)

    def update(self, name):
        # All the old dependencies, if any, are no longer valid.
        for observable in self.deps.get_back(name):
            self.deps.remove(observable, name)

        # What are the new dependencies?  And the new value?
        membrane = Membrane(self.vals) # audit what it reads
        try:
            value = self.fs[name].expr.eval(membrane)
        except Exception as e:
            value = e           # XXX store elsewhere?

        for observable in membrane.deps:
            self.deps.add(observable, name)

        # Now, we may need to change the value.  Or we may not.
        if name in self.vals and value == self.vals[name]:
            return

        # Note it for the shell.
        self.updates.append(name)

        # We do, so first we must retract the old one.
        self.retract(name)
        self.vals[name] = value
        self.propagate(name)
        
    def remove(self, name):
        del self.fs[name]
        self.retract(name)

    def retract(self, name):
        if name not in self.vals:
            return              # idempotency

        del self.vals[name]
        for observer in self.deps.get(name):
            self.retract(observer)

    def propagate(self, name):
        for observer in self.deps.get(name):
            if observer not in self.vals:
                self.update(observer)


class Membrane:
    "Audit accesses to a dictionary.  Like much of this code, inspired by Corbin Simpson."
    def __init__(self, kid):
        self.kid = kid
        self.deps = set()

    def __getitem__(self, item):
        self.deps.add(item)
        return self.kid[item]


if __name__ == '__main__':
    Shell().repl()