Relational Algebra to SQL Subqueries

#!/usr/bin/env python

# NAME         PYTHON-NOTATION                             HASKELL-NOTATION
# selektion:   S[a.name != b.name]( ... )                  S String Rel
# projektion:  P[a.name, b.budget]( ... )                  P String Rel
# join:        J[a.budget = b.budget, proj]( RELA, RELB )  J String String Rel Rel
# rename:      R[budget->geld, name->zeug]( ... )          R [(String,String)] Rel
# from:        F[a]( ... )                                 F String Rel
#              T[""]()                                     T String
#
# Beispiel: P[a.name,a.einnahmen,b.alter,CONCAT(b.vname, b.nname)](J[a.angestellter = b.id, a.name, a.einnahmen, b.alter, b.vname, b.nname](T["a"](), T["b"]()))
import re

def inherit_docstring(cls):
    for name, func in vars(cls).items():
        if not func.__doc__:
            for parent in cls.__bases__:
                parfunc = getattr(parent, name)
                if parfunc and getattr(parfunc, '__doc__', None):
                    func.__doc__ = parfunc.__doc__
                    break
    return cls

class Node(object):
    def __init__(self):
        """
        Vor.: der Konstruktor wird korrekt aufgerufen
        Erg.: -
        Eff.: ein Neues Objekt vom Typ {} wird erstellt
        """.format(type(self))
        self.children = []

    def appendChild(self, child):
        """Appends a Node below this one.

        Vor.: "self" und "child" sind Objekte, die von "Node" erben
        Erg.: -
        Eff.: "child" wird unter "self" angehängt
        """
        self.children.append(child)

    def render(self):
        """Renders the node to an SQL-command.

        Vor.: "self" ist ein Objekt, dass von "Node" erbt
        Erg.: ein String, der "self" als SQL-Befehlt repräsentiert
        Eff.: -
        """
        pass

class TableNode(Node):
    def __init__(self, name):
        self.name = name

    @inherit_docstring
    def render(self):
        return self.name

class RenameRelNode(Node):
    def __init__(self, new):
        self.new = new
        self.children = []

    @inherit_docstring
    def render(self):
        return "{} as {}".format(self.children[0].render(), self.new)

class JoinNode(Node):
    def __init__(self, condition, *attrs):
        self.condition  = condition
        self.attrs      = ", ".join(attrs)
        self.children = []

    @inherit_docstring
    def render(self):
        return "(SELECT {} FROM {}, {} WHERE {})".format(self.attrs, self.children[0].render(), self.children[1].render(), self.condition)

class ProjectionNode(Node):
    def __init__(self, *attrs):
        self.attrs = attrs
        self.children = []

    @inherit_docstring
    def render(self):
        return "(SELECT {} FROM {})".format(self.attrs, self.children[0].render())

class SelectionNode(Node):
    def __init__(self, condition):
        self.condition = condition
        self.children = []

    @inherit_docstring
    def render(self):
        return "(SELECT * FROM {} WHERE {})".format(self.children[0].render(), self.condition)

class RenameNode(Node):
    def __init__(self, names):
        self.names = names
        self.children = []

    @inherit_docstring
    def render(self):
        return "(SELECT {} FROM {})".format( ", ".join([ "{} as {}".format(old, self.names[old]) for old in self.names]),  self.children[0].render())

class RelAlgParser(Node):
    regex = re.compile("^(S|P|J|F|T|R)\[([^\[]*)\]\((.*)\)$")

    types = {
        "S": SelectionNode,
        "P": ProjectionNode,
        "J": JoinNode,
        "F": RenameRelNode,
        "R": RenameNode,
        "T": TableNode
    }

    def splitExpr(self, string):
        """Splits a string on commata, but minds nested parenthesis, brackets and quotation marks.

        For example: "abc, def(efg, hijk), (a,b[)c'd]', end"   =>  ["abc", "def(efg, hijk)", "(a,b[)c'd'", "end"]
        split = string.split(",")

        Vor.: "string" ist ein String
        Erg.: "string", an allen Kommas, die nicht in Klammern ('(', '[') oder Anführungszeichen stehen (''', '"'), in eine Liste unterteilt.
        Eff.: -
        """
        res = [""]
        symbols = {
            "(": ( 1, "("),
            ")": (-1, "("),
            "[": ( 1, "["),
            "]": (-1, "["),
            "'": ( 1, "'"),
            '"': ( 1, '"')
        }
        counts = { "(": 0, "[": 0, "'": 0, '"': 0 }

        for e in string.split(","):
            for symbol in symbols:
                typ = symbols[symbol]
                counts[typ[1]] += e.count(symbol) * typ[0]
            counts["'"] = counts["'"] % 2
            counts['"'] = counts['"'] % 2

            res[-1] += e + ","
            if len(res) > 0 and all(map(lambda x: counts[x]==0, counts)): # all counts zero
                res[-1] = res[-1][:-1]  # remove trailing ","
                if res[-1] != "":
                    res.append("")      # new part

        return res[:-1]

    def parse(self, string):
        """ecursively transforms an expression of Relational Algebra into an AST.

        Vor.: "string" ist ein String, auf den das definierte Muster passt
        Erg.: Wurzel-Knoten (Node), der den äußersten Befehl des relational-algebraischen Ausdrucks in "string" enthält.
        Eff.: Alle weiteren Befehle in "string" werden unter dem Wurzel-Knoten in einem Baum angeordnet
        """
        match = re.match(self.regex, string)
        if not match:
            print("ERR: no match in '{}'".format(string))
            return None
        func, params, rels = match.groups()

        node = self.types[func](*list(map(str.strip, self.splitExpr(params))))
        for rel in map(str.strip, self.splitExpr(rels)):
            node.appendChild(self.parse(rel))
        return node

if __name__ == "__main__":
    import sys
    parser = RelAlgParser()
    cmd = ""
    if len(sys.argv) > 1:
        cmd = sys.argv[1]
    else:
        cmd = input()
    print( parser.parse(cmd).render() ) # argv[1] is das erste Argument in der Konsole

"""
class FA(object):
    def __init__(self, states, moves, ends):
        self.states = states
        self.moves = moves # moves = (from, char, to) / (from, None, to)
        self.ends = ends

    def newDfa( self ):
        state = self.new()
        n = FA( set([frozenset(state.pos)]), set(), set() )
        new = True
        while new:
            new = False
            nstates = set()
            for s in n.states:
                d = {}
                nmoves = set()
                for m in [ (m[1], m[2]) for m in self.moves if m[0] in s ]:
                    if not m[1] in d:
                        d[m[0]] = set()
                    d[m[0]].add(m[1])
                    for k in d:
                        if not d[k] in n.states:
                            nstates.add(frozenset(d[k]))
                            new = True
                        if not (s, k, frozenset(d[k])) in n.moves:
                            nmoves.add( (s,k,frozenset(d[k])) )
                n.moves |= nmoves
            n.states |= nstates

        states = {}
        nstates = n.states.copy()
        for i,s in enumerate(n.states):
            states[s] = i
            if any(ss in self.ends for ss in s):
                n.ends.add(i)
            nstates.remove(s)
            nstates.add(i)
        n.states = nstates

        nmoves = n.moves.copy()
        for i,m in enumerate(n.moves):
            print ( m, m[2] )
            nmoves.remove(m)
            nmoves.add( (states[m[0]],m[1],states[m[2]]) )
        n.moves = nmoves

        return n


    def new( self, start=1 ):
        return NFAState( self, start )

    def newD( self, start=1 ):
        return DFAState( self, start )

class NFAState(object):
    def __init__( self, nfa, start ):
        self.nfa = nfa
        self.reset( start )

    def reset( self, start ):
        self.pos = set([start])
        self.close()

    def doesTrans( self, str ):
        return self.trans(str) >= self.nfa.ends

    def trans( self, str ):
        for char in str:
            self.onetrans( char )
        return self.pos

    def onetrans( self, char ):
        self.onemove(char);
        self.close();

    def onemove( self, char ):
        self.pos = set([ to for (f, via, to) in self.nfa.moves if f in self.pos and via == char ])

    def close( self ):
        new = set([ to for (f, via, to) in self.nfa.moves if f in self.pos and via == None ])
        self.pos = self.pos.union(new)

class DFAState(object):
    def __init__( self, dfa, start ):
        self.dfa = dfa
        self.pos = start

    def reset( self, start ):
        self.pos = start

    def doesTrans( self, str ):
        return self.trans(str) in self.dfa.ends

    def trans( self, str ):
        for char in str:
            self.onemove( char )
        return self.pos

    def onemove( self, char ):
        print( "{}? --{}-> ??".format(self.pos , char ) )
        self.pos = [ to for (f, via, to) in self.dfa.moves if f == self.pos and via == char ][0]

if __name__ == "__main__":
    nfa = FA( set([1,2,3,4,5]), set([(1,'a',2), (3, None, 2), (2, 'a', 4), (4,'b',3), (4, None, 5), (2, 'c', 5), (2, 'c', 3)]), set([4,5]))
    print( nfa.new().doesTrans( "abc" ), nfa.new().trans( "abc" ) )
"""