EVOLUTION-MANAGER

Edit File: nfa.py

# Copyright 2012 Matt Chaput. All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#
#    1. Redistributions of source code must retain the above copyright notice,
#       this list of conditions and the following disclaimer.
#
#    2. Redistributions in binary form must reproduce the above copyright
#       notice, this list of conditions and the following disclaimer in the
#       documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY MATT CHAPUT ``AS IS'' AND ANY EXPRESS OR
# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
# EVENT SHALL MATT CHAPUT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
# EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
# The views and conclusions contained in the software and documentation are
# those of the authors and should not be interpreted as representing official
# policies, either expressed or implied, of Matt Chaput.

from whoosh.automata.fst import Arc

class Instruction(object):
    def __repr__(self):
        return "%s()" % (self.__class__.__name__, )

class Char(Instruction):
    """
    Matches a literal character.
    """

def __init__(self, c):
        self.c = c

def __repr__(self):
        return "Char(%r)" % self.c

class Lit(Instruction):
    """
    Matches a literal string.
    """

def __init__(self, c):
        self.c = c

def __repr__(self):
        return "Lit(%r)" % self.c

class Any(Instruction):
    """
    Matches any character.
    """

class Match(Instruction):
    """
    Stop this thread: the string matched.
    """

def __repr__(self):
        return "Match()"

class Jmp(Instruction):
    """
    Jump to a specified instruction.
    """

def __init__(self, x):
        self.x = x

def __repr__(self):
        return "Jmp(%s)" % self.x

class Split(Instruction):
    """
    Split execution: continue at two separate specified instructions.
    """

def __init__(self, x, y):
        self.x = x
        self.y = y

def __repr__(self):
        return "Split(%s, %s)" % (self.x, self.y)

class Label(Instruction):
    """
    Placeholder to act as a target for JMP instructions
    """

def __hash__(self):
        return id(self)

def __repr__(self):
        return "L(%s)" % hex(id(self))

def concat(e1, e2):
    return e1 + e2

def alt(e1, e2):
    L1, L2, L3 = Label(), Label(), Label()
    return [L1] + e1 + [Jmp(L3), L2] + e2 + [L3]

def zero_or_one(e):
    L1, L2 = Label(), Label()
    return [Split(L1, L2), L1] + e + [L2]

def zero_or_more(e):
    L1, L2, L3 = Label(), Label(), Label()
    return [L1, Split(L2, L3), L2] + e + [Jmp(L1), L3]

def one_or_more(e):
    L1, L2 = Label(), Label()
    return [L1] + e + [Split(L1, L2), L2]

def fixup(program):
    refs = {}
    i = 0
    while i < len(program):
        op = program[i]
        if isinstance(op, Label):
            refs[op] = i
            program.pop(i)
        else:
            i += 1

if refs:
        for op in program:
            if isinstance(op, (Jmp, Split)):
                op.x = refs[op.x]
            if isinstance(op, Split):
                op.y = refs[op.y]

return program + [Match]

class ThreadList(object):
    def __init__(self, program, max=1000):
        self.program = program
        self.max = max
        self.threads = []

def __nonzero__(self):
        return bool(self.threads)

def current(self):
        return self.threads.pop()

def add(self, thread):
        op = self.program[thread.pc]
        optype = type(op)
        if optype is Jmp:
            self.add(thread.at(op.x))
        elif optype is Split:
            self.add(thread.copy_at(op.x))
            self.add(thread.at(op.y))
        else:
            self.threads.append(thread)

class Thread(object):
    def __init__(self, pc, address, sofar='', accept=False):
        self.pc = pc
        self.address = address
        self.sofar = sofar
        self.accept = accept

def at(self, pc):
        self.pc = pc
        return self

def copy_at(self, pc):
        return Thread(pc, self.address, self.sofar, self.accept)

def __repr__(self):
        d = self.__dict__
        return "Thread(%s)" % ",".join("%s=%r" % (k, v) for k, v in d.items())

def advance(thread, arc, c):
    thread.pc += 1
    thread.address = arc.target
    thread.sofar += c
    thread.accept = arc.accept

def run(graph, program, address):
    threads = ThreadList(program)
    threads.add(Thread(0, address))
    arc = Arc()
    while threads:
        thread = threads.current()
        address = thread.address
        op = program[thread.pc]
        optype = type(op)

if optype is Char:
            if address:
                arc = graph.find_arc(address, op.c, arc)
                if arc:
                    advance(thread, arc)
                    threads.add(thread)
        elif optype is Lit:
            if address:
                c = op.c
                arc = graph.find_path(c, arc, address)
                if arc:
                    advance(thread, arc, c)
                    threads.add(thread)
        elif optype is Any:
            if address:
                sofar = thread.sofar
                pc = thread.pc + 1
                for arc in graph.iter_arcs(address, arc):
                    t = Thread(pc, arc.target, sofar + arc.label, arc.accept)
                    threads.add(t)
        elif op is Match:
            if thread.accept:
                yield thread.sofar
        else:
            raise Exception("Don't know what to do with %r" % op)

LO = 0
HI = 1

def regex_limit(graph, mode, program, address):
    low = mode == LO
    output = []
    threads = ThreadList(program)
    threads.add(Thread(0, address))
    arc = Arc()
    while threads:
        thread = threads.current()
        address = thread.address
        op = program[thread.pc]
        optype = type(op)

if optype is Char:
            if address:
                arc = graph.find_arc(address, op.c, arc)
                if arc:
                    if low and arc.accept:
                        return thread.sofar + thread.label
                    advance(thread, arc)
                    threads.add(thread)
        elif optype is Lit:
            if address:
                labels = op.c
                for label in labels:
                    arc = graph.find_arc(address, label)
                    if arc is None:
                        return thread.sofar
            elif thread.accept:
                return thread.sofar
        elif optype is Any:
            if address:
                if low:
                    arc = graph.arc_at(address, arc)
                else:
                    for arc in graph.iter_arcs(address):
                        pass
                advance(thread, arc, arc.label)
                threads.add(thread)
            elif thread.accept:
                return thread.sofar
        elif op is Match:
            return thread.sofar
        else:
            raise Exception("Don't know what to do with %r" % op)

# if __name__ == "__main__":
#     from whoosh import index, query
#     from whoosh.filedb.filestore import RamStorage
#     from whoosh.automata import fst
#     from whoosh.util.testing import timing
#
#     st = RamStorage()
#     gw = fst.GraphWriter(st.create_file("test"))
#     gw.start_field("test")
#     for key in ["aaaa", "aaab", "aabb", "abbb", "babb", "bbab", "bbba"]:
#         gw.insert(key)
#     gw.close()
#     gr = fst.GraphReader(st.open_file("test"))
#
#     program = one_or_more([Lit("a")])
#     print program
#     program = fixup(program)
#     print program
#     print list(run(gr, program, gr.root("test")))
#
#     ix = index.open_dir("e:/dev/src/houdini/help/index")
#     r = ix.reader()
#     gr = r._get_graph()
#
# #    program = fixup([Any(), Any(), Any(), Any(), Any()])
# #    program = fixup(concat(zero_or_more([Any()]), [Char("/")]))
# #    with timing():
# #        x = list(run(gr, program, gr.root("path")))
# #    print len(x)
#
#     q = query.Regex("path", "^.[abc].*/$")
#     with timing():
#         y = list(q._btexts(r))
#     print len(y)
#     print y[0], y[-1]
#
#     pr = [Any()] + alt([Lit("c")], alt([Lit("b")], [Lit("a")])) + zero_or_more([Any()]) + [Lit("/")]
#     program = fixup(pr)
# #    with timing():
# #        x = list(run(gr, program, gr.root("path")))
# #    print len(x), x
#
#     with timing():
#         print "lo=", regex_limit(gr, LO, program, gr.root("path"))
#         print "hi=", regex_limit(gr, HI, program, gr.root("path"))
#
#
#
# #int
# #backtrackingvm(Inst *prog, char *input)
# #{
# #    enum { MAXTHREAD = 1000 };
# #    Thread ready[MAXTHREAD];
# #    int nready;
# #    Inst *pc;
# #    char *sp;
# #
# #    /* queue initial thread */
# #    ready[0] = thread(prog, input);
# #    nready = 1;
# #
# #    /* run threads in stack order */
# #    while(nready > 0){
# #        --nready;  /* pop state for next thread to run */
# #        pc = ready[nready].pc;
# #        sp = ready[nready].sp;
# #        for(;;){
# #            switch(pc->opcode){
# #            case Char:
# #                if(*sp != pc->c)
# #                    goto Dead;
# #                pc++;
# #                sp++;
# #                continue;
# #            case Match:
# #                return 1;
# #            case Jmp:
# #                pc = pc->x;
# #                continue;
# #            case Split:
# #                if(nready >= MAXTHREAD){
# #                    fprintf(stderr, "regexp overflow");
# #                    return -1;
# #                }
# #                /* queue new thread */
# #                ready[nready++] = thread(pc->y, sp);
# #                pc = pc->x;  /* continue current thread */
# #                continue;
# #            }
# #        }
# #    Dead:;
# #    }
# #    return 0;
# #}
#
#