add ymake export to ydb

1 files changed, 255 insertions, 0 deletions

diff --git a/contrib/tools/cython/Cython/Plex/Machines.py b/contrib/tools/cython/Cython/Plex/Machines.py
new file mode 100644
index 0000000000..398850976b
--- /dev/null
+++ b/contrib/tools/cython/Cython/Plex/Machines.py
@@ -0,0 +1,255 @@
+#=======================================================================
+#
+#   Python Lexical Analyser
+#
+#   Classes for building NFAs and DFAs
+#
+#=======================================================================
+
+from __future__ import absolute_import
+
+import sys
+
+from .Transitions import TransitionMap
+
+try:
+    from sys import maxsize as maxint
+except ImportError:
+    from sys import maxint
+
+try:
+    unichr
+except NameError:
+    unichr = chr
+
+LOWEST_PRIORITY = -maxint
+
+
+class Machine(object):
+    """A collection of Nodes representing an NFA or DFA."""
+    states = None          # [Node]
+    next_state_number = 1
+    initial_states = None  # {(name, bol): Node}
+
+    def __init__(self):
+        self.states = []
+        self.initial_states = {}
+
+    def __del__(self):
+        #print "Destroying", self ###
+        for state in self.states:
+            state.destroy()
+
+    def new_state(self):
+        """Add a new state to the machine and return it."""
+        s = Node()
+        n = self.next_state_number
+        self.next_state_number = n + 1
+        s.number = n
+        self.states.append(s)
+        return s
+
+    def new_initial_state(self, name):
+        state = self.new_state()
+        self.make_initial_state(name, state)
+        return state
+
+    def make_initial_state(self, name, state):
+        self.initial_states[name] = state
+
+    def get_initial_state(self, name):
+        return self.initial_states[name]
+
+    def dump(self, file):
+        file.write("Plex.Machine:\n")
+        if self.initial_states is not None:
+            file.write("   Initial states:\n")
+            for (name, state) in sorted(self.initial_states.items()):
+                file.write("      '%s': %d\n" % (name, state.number))
+        for s in self.states:
+            s.dump(file)
+
+
+class Node(object):
+    """A state of an NFA or DFA."""
+    transitions = None      # TransitionMap
+    action = None           # Action
+    action_priority = None  # integer
+    number = 0              # for debug output
+    epsilon_closure = None  # used by nfa_to_dfa()
+
+    def __init__(self):
+        # Preinitialise the list of empty transitions, because
+        # the nfa-to-dfa algorithm needs it
+        #self.transitions = {'':[]}
+        self.transitions = TransitionMap()
+        self.action_priority = LOWEST_PRIORITY
+
+    def destroy(self):
+        #print "Destroying", self ###
+        self.transitions = None
+        self.action = None
+        self.epsilon_closure = None
+
+    def add_transition(self, event, new_state):
+        self.transitions.add(event, new_state)
+
+    def link_to(self, state):
+        """Add an epsilon-move from this state to another state."""
+        self.add_transition('', state)
+
+    def set_action(self, action, priority):
+        """Make this an accepting state with the given action. If
+        there is already an action, choose the action with highest
+        priority."""
+        if priority > self.action_priority:
+            self.action = action
+            self.action_priority = priority
+
+    def get_action(self):
+        return self.action
+
+    def get_action_priority(self):
+        return self.action_priority
+
+    def is_accepting(self):
+        return self.action is not None
+
+    def __str__(self):
+        return "State %d" % self.number
+
+    def dump(self, file):
+        # Header
+        file.write("   State %d:\n" % self.number)
+        # Transitions
+        #        self.dump_transitions(file)
+        self.transitions.dump(file)
+        # Action
+        action = self.action
+        priority = self.action_priority
+        if action is not None:
+            file.write("      %s [priority %d]\n" % (action, priority))
+
+    def __lt__(self, other):
+        return self.number < other.number
+
+
+class FastMachine(object):
+    """
+    FastMachine is a deterministic machine represented in a way that
+    allows fast scanning.
+    """
+    initial_states = None  # {state_name:state}
+    states = None          # [state]  where state = {event:state, 'else':state, 'action':Action}
+    next_number = 1        # for debugging
+
+    new_state_template = {
+        '': None, 'bol': None, 'eol': None, 'eof': None, 'else': None
+    }
+
+    def __init__(self):
+        self.initial_states = {}
+        self.states = []
+
+    def __del__(self):
+        for state in self.states:
+            state.clear()
+
+    def new_state(self, action=None):
+        number = self.next_number
+        self.next_number = number + 1
+        result = self.new_state_template.copy()
+        result['number'] = number
+        result['action'] = action
+        self.states.append(result)
+        return result
+
+    def make_initial_state(self, name, state):
+        self.initial_states[name] = state
+
+    def add_transitions(self, state, event, new_state, maxint=maxint):
+        if type(event) is tuple:
+            code0, code1 = event
+            if code0 == -maxint:
+                state['else'] = new_state
+            elif code1 != maxint:
+                while code0 < code1:
+                    state[unichr(code0)] = new_state
+                    code0 += 1
+        else:
+            state[event] = new_state
+
+    def get_initial_state(self, name):
+        return self.initial_states[name]
+
+    def dump(self, file):
+        file.write("Plex.FastMachine:\n")
+        file.write("   Initial states:\n")
+        for name, state in sorted(self.initial_states.items()):
+            file.write("      %s: %s\n" % (repr(name), state['number']))
+        for state in self.states:
+            self.dump_state(state, file)
+
+    def dump_state(self, state, file):
+        # Header
+        file.write("   State %d:\n" % state['number'])
+        # Transitions
+        self.dump_transitions(state, file)
+        # Action
+        action = state['action']
+        if action is not None:
+            file.write("      %s\n" % action)
+
+    def dump_transitions(self, state, file):
+        chars_leading_to_state = {}
+        special_to_state = {}
+        for (c, s) in state.items():
+            if len(c) == 1:
+                chars = chars_leading_to_state.get(id(s), None)
+                if chars is None:
+                    chars = []
+                    chars_leading_to_state[id(s)] = chars
+                chars.append(c)
+            elif len(c) <= 4:
+                special_to_state[c] = s
+        ranges_to_state = {}
+        for state in self.states:
+            char_list = chars_leading_to_state.get(id(state), None)
+            if char_list:
+                ranges = self.chars_to_ranges(char_list)
+                ranges_to_state[ranges] = state
+        ranges_list = ranges_to_state.keys()
+        ranges_list.sort()
+        for ranges in ranges_list:
+            key = self.ranges_to_string(ranges)
+            state = ranges_to_state[ranges]
+            file.write("      %s --> State %d\n" % (key, state['number']))
+        for key in ('bol', 'eol', 'eof', 'else'):
+            state = special_to_state.get(key, None)
+            if state:
+                file.write("      %s --> State %d\n" % (key, state['number']))
+
+    def chars_to_ranges(self, char_list):
+        char_list.sort()
+        i = 0
+        n = len(char_list)
+        result = []
+        while i < n:
+            c1 = ord(char_list[i])
+            c2 = c1
+            i += 1
+            while i < n and ord(char_list[i]) == c2 + 1:
+                i += 1
+                c2 += 1
+            result.append((chr(c1), chr(c2)))
+        return tuple(result)
+
+    def ranges_to_string(self, range_list):
+        return ','.join(map(self.range_to_string, range_list))
+
+    def range_to_string(self, range_tuple):
+        (c1, c2) = range_tuple
+        if c1 == c2:
+            return repr(c1)
+        else:
+            return "%s..%s" % (repr(c1), repr(c2))