def do(SM_A, SM_B):
    """Find a state machine that stops right before the state machine 'SM_B'.
    If there is a lexeme 'l' (lowercase L) in SM_A:

                       l = [x0, x1, ... xj, xk, ... xN ]

    and '[xk ... xN]' is a lexeme from L(SM_B). The 'rcut(SM_A, SM_B)' shall
    only match 
                       '[x0, x1, ... xj]'. 
                       
    All lexemes 'l' translate into lexemes 's' in reverse(SM_A):

                       s = [xN, ... xk, xj, ... x1, x0 ]

    lexemes in SM_B translate into reverse(SM_B) as

                       t = [xN, ... xk]

    The 'cut' operation cut(reverse(SM_A), reverse(SM_B)) delivers

                       u = [ xj, ... x1, x0 ]

    Then, the 'reverse(cut(reverse(SM_A), reverse(SM_B)))' delivers

                       u = [ x0, x1, ... xj ]

    as desired for all lexemes in SM_A that end with something that 
    matches SM_B.
                       
    (C) Frank-Rene Schaefer
    """
    Ar        = beautifier.do(reverse.do(SM_A))
    Br        = beautifier.do(reverse.do(SM_B))
    cut_Ar_Br = complement_begin.do(Ar, Br)
    return reverse.do(cut_Ar_Br)

    def __init__(self, CoreSM, PreContextSM=None, PostContextSM=None, 
                 BeginOfLineF=False, EndOfLineF=False, Sr=SourceRef_VOID, 
                 PatternString="",
                 AllowNothingIsNecessaryF=False):
        assert PreContextSM is None or isinstance(PreContextSM, StateMachine)
        Pattern.check_initial(CoreSM, 
                              BeginOfLineF, PreContextSM, 
                              EndOfLineF, PostContextSM, 
                              Sr,
                              AllowNothingIsNecessaryF)

        self.__pattern_string = PatternString
        self.__sr             = Sr

        # (*) Setup the whole pattern
        self.__sm                         = CoreSM
        self.__post_context_sm            = PostContextSM
        self.__post_context_end_of_line_f = EndOfLineF
        assert self.__sm is not None

        # -- [optional] post contexts
        self.__post_context_f = (PostContextSM is not None)

        #    Backward input position detection requires an inversion of the 
        #    state machine. This can only be done after the (optional) codec
        #    transformation. Thus, a non-inverted version of the state machine
        #    is maintained until the transformation is done.
        self.__bipd_sm_to_be_inverted = None
        self.__bipd_sm                = None

        # -- [optional] pre contexts
        #
        #    Same as for backward input position detection holds for pre-contexts.
        self.__pre_context_sm_to_be_inverted = PreContextSM
        self.__pre_context_sm                = None

        # All state machines must be DFAs
        if not self.__sm.is_DFA_compliant(): 
            self.__sm  = beautifier.do(self.__sm)

        if         self.__pre_context_sm_to_be_inverted is not None \
           and not self.__pre_context_sm_to_be_inverted.is_DFA_compliant(): 
            self.__pre_context_sm_to_be_inverted = beautifier.do(self.__pre_context_sm_to_be_inverted)

        # Detect the trivial pre-context
        self.__pre_context_begin_of_line_f = BeginOfLineF
        
        # The line/column count information can only be determined when the 
        # line/column count database is present. Thus, it is delayed.
        self.__count_info = None

        # Ensure, that the pattern is never transformed twice
        self.__alarm_transformed_f = False

        self.__validate(Sr)

    def mount_post_context_sm(self):
        self.__sm,     \
        self.__bipd_sm_to_be_inverted = setup_post_context.do(self.__sm, 
                                                              self.__post_context_sm, 
                                                              self.__post_context_end_of_line_f, 
                                                              self.__sr)

        if self.__bipd_sm_to_be_inverted is None: 
            return

        if         self.__bipd_sm_to_be_inverted is not None \
           and not self.__bipd_sm_to_be_inverted.is_DFA_compliant(): 
            self.__bipd_sm_to_be_inverted = beautifier.do(self.__bipd_sm_to_be_inverted)

        self.__bipd_sm = beautifier.do(reverse.do(self.__bipd_sm_to_be_inverted))

def do(sm):
    state_list = sm.states.items()
    for state_index, state in state_list:
        # Get the 'transition_list', i.e. a list of pairs (TargetState, NumberSet)
        # which indicates what target state is reached via what number set.
        transition_list = state.transitions().get_map().items()
        # Clear the state's transitions, now. This way it can absorb new
        # transitions to intermediate states.
        state.transitions().clear()
        # Loop over all transitions
        for target_state_index, number_set in transition_list:
            # We take the intervals with 'PromiseToTreatWellF' even though they
            # are changed. This is because the intervals would be lost anyway
            # after the state split, so we use the same memory and do not 
            # cause a time consuming memory copy and constructor calls.
            interval_list = number_set.get_intervals(PromiseToTreatWellF=True)

            # 1st check whether a modification is necessary
            modification_required_f = False
            for interval in interval_list:
                if interval.begin >= 0x10000: modification_required_f = True; break

            if modification_required_f == False:
                sm.states[state_index].add_transition(number_set, target_state_index)
                continue

            # Now, intermediate states may be added
            for interval in interval_list:
                create_intermediate_states(sm, state_index, target_state_index, interval)
    
    result = beautifier.do(sm)
    return result

def philosophical_cut(core_sm, post_context_sm):
    """The 'philosophical cut' is a technique introduced by Frank-Rene Schaefer
       to produce a pair of a core- and a post-condition that otherwise would 
       be forward and backward ambiguous. The philosophical ground for this
       cut is 'greed', i.e. a core pattern should eat as much characters as
       it can. This idea is followed during the whole construction of the lexical
       analyzer. 
       
       For the case of total ambiguity 'x+/x+', this idea translates into leaving
       the iteration in the core condition and cutting the iteration in the post
       condition. Thus 'x+/x+' is transformed into 'x+/x' and can be solved by
       the technique for forward ambiguous post conditions.

       __dive -- indicator of recursion! replace by TreeWalker
    """
    core_acceptance_state_list = core_sm.get_acceptance_state_list()

    pcsm_init_state = post_context_sm.get_init_state()
    for csm_state in core_acceptance_state_list:
        __dive_to_cut_iteration(core_sm, csm_state, post_context_sm, pcsm_init_state,
                                SM1_Path=[post_context_sm.init_state_index])

    # By means of cutting, some states might have become bold. That is, they have
    # only an epsilon transition. Thus, it is required to do a transformation NFA->DFA
    # and add a hopcroft optimization.
    new_post_sm = beautifier.do(post_context_sm)
    return new_post_sm

def is_all(SM):
    """Pattern has only two states: the init state which is not 
    accepting, and the accepting state which transits to itself
    forever.
    """
    sm = beautifier.do(SM)
    # Init State:
    #   -- not an acceptance state
    #   -- has only one transition on 'all' to an acceptance state
    #
    if   len(sm.states) != 2:                 return False
    init_state = sm.get_init_state()
    if   init_state.is_acceptance():          return False
    tm = init_state.target_map.get_map()
    if   len(tm) != 1:                        return False
    target_index, trigger_set = tm.iteritems().next()
    if trigger_set.is_all() == False:         return False
    if target_index == sm.init_state_index:   return False

    # The Acceptance State:
    #   -- has only one transition on 'all' to itself.
    #
    target_state = sm.states[target_index]
    if not target_state.is_acceptance():      return False
    tm = target_state.target_map.get_map()
    if len(tm) != 1:                          return False
    
    target_index_2, trigger_set = tm.iteritems().next()
    if trigger_set.is_all() == False:         return False
    if target_index_2 != target_index:        return False
    return True

def snap_term(stream, PatternDict):
    """term:  primary
              primary term 
    """
    __debug_entry("term", stream)    

    # -- primary
    result = snap_primary(stream, PatternDict) 
    __debug_print("##primary(in term):", result)
    if result is None: return __debug_exit(None, stream)
    position_1 = stream.tell()

    # -- optional 'term' 
    result_2 = snap_term(stream, PatternDict) 
    __debug_print("##term(in term):",  result_2)
    if result_2 is None: 
        stream.seek(position_1)
        return __debug_exit(result, stream)
    
    ## print "##1:", result.get_string(NormalizeF=False)
    ## print "##2:", result_2.get_string(NormalizeF=False)
    result = sequentialize.do([result, result_2], 
                              MountToFirstStateMachineF=True, 
                              CloneRemainingStateMachinesF=False)    

    return __debug_exit(beautifier.do(result), stream)

def snap_expression(stream, PatternDict):
    """expression:  term
                    term | expression
    """              
    __debug_entry("expression", stream)    
    # -- term
    result = snap_term(stream, PatternDict) 
    if result is None: 
        return __debug_exit(None, stream)

    # -- optional '|'
    if not check(stream, '|'): 
        return __debug_exit(result, stream)
    
    position_1 = stream.tell()
    __debug_print("'|' (in expression)")

    # -- expression
    result_2 = snap_expression(stream, PatternDict) 
    __debug_print("expression(in expression):",  result_2)
    if result_2 is None:
        stream.seek(position_1) 
        return __debug_exit(result, stream)

    result = parallelize.do([result, result_2], CloneF=True)   # CloneF = False (shold be!)
    return __debug_exit(beautifier.do(result), stream)

    def specify_suppressor(self, Sm, sr):
        _error_if_defined_before(self.sm_newline_suppressor, sr)

        self.count_command_map.add(Sm.get_beginning_character_set(), 
                                   "begin(newline suppressor)", None, sr)
        if not Sm.is_DFA_compliant(): Sm = beautifier.do(Sm)
        self.sm_newline_suppressor.set(Sm, sr)

def __get_inverse_state_machine_that_finds_end_of_core_expression(PostConditionSM):
    """In case of a pseudo-ambiguous post condition one needs to go backwards
       in order to search for the end of the core condition. This function 
       creates the inverse state machine that is able to go backwards.

       NOTE: This is a special case, because one already knows that the state
       machine reaches the acceptance state sometime (this is where it actually
       started). That means, that in states other than acceptance states one
       can take out the 'drop out' triggers since they CANNOT occur. This
       enables some speed-up when going backwards.
    """
    result = beautifier.do(PostConditionSM.get_inverse())

    # -- delete 'drop-out' transitions in non-acceptance states
    #    NOTE: When going backwards one already knows that the acceptance
    #          state (the init state of the post condition) is reached, see above.
    # for state in result.states.values():
    #    # -- acceptance states can have 'drop-out' (actually, they need to have)
    #    if state.is_acceptance(): continue
    #
    #    state.transitions().replace_drop_out_target_states_with_adjacent_targets()
    #
    # result = nfa_to_dfa.do(result)
    # result = hopcroft.do(result)

    # Acceptance States need to be marked: Store input position.
    # NOTE: When tracing backwards the match is guaranteed, but there might
    #       still be some 'trail' in case of iterations that are not directly
    #       iterated to the ambiguous post condition. Thus drop out may
    #       happen and it must be clear where to put the input pointer in this case.

    return result

    def __specify_comment(self, Sm, sr):
        _error_if_defined_before(self.result.sm_comment, sr)

        self.specifier_count_op_map.add(Sm.get_beginning_character_set(), 
                                   "begin(comment to newline)", None, sr)
        if not Sm.is_DFA_compliant(): Sm = beautifier.do(Sm)
        self.result.sm_comment.set(Sm, sr)

def do_state_machine(SmIn):
    """Transforms a given state machine from 'Unicode Driven' to another
       character encoding type.
    
       RETURNS: 
       [0] Transformation complete (True->yes, False->not all transformed)
       [1] Transformed state machine. It may be the same as it was 
           before if there was no transformation actually.

       It is ensured that the result of this function is a DFA compliant
       state machine.
    """
    if SmIn is None: return True, None
    assert SmIn.is_DFA_compliant()

    # BEFORE: Forgive characters not in source range. What comes out is 
    #         important. It is checked in 'transform()' of the Pattern.
    complete_f, sm_out = Setup.buffer_codec.transform(SmIn)

    # AFTER: Whatever happend, the transitions in the state machine MUST
    #        lie in the drain_set.
    sm_out.assert_range(Setup.buffer_codec.drain_set)

    if sm_out.is_DFA_compliant(): return complete_f, sm_out
    else:                         return complete_f, beautifier.do(sm_out)

def do(the_state_machine, pre_context_sm, BeginOfLinePreContextF):
    """Sets up a pre-condition to the given state machine. This process
       is entirely different from any sequentializing or parallelization
       of state machines. Here, the state machine representing the pre-
       condition is **not** webbed into the original state machine!

       Instead, the following happens:

          -- the pre-condition state machine is inverted, because
             it is to be walked through backwards.
          -- the inverted state machine is marked with the state machine id
             of the_state_machine.        
          -- the original state machine will refer to the inverse
             state machine of the pre-condition.
          -- the initial state origins and the origins of the acceptance
             states are marked as 'pre-conditioned' indicating the id
             of the inverted state machine of the pre-condition.             
    """
    #___________________________________________________________________________________________
    # (*) do some consistency checking   
    # -- state machines with no states are senseless here. 
    assert not the_state_machine.is_empty() 
    assert pre_context_sm is None or not pre_context_sm.is_empty()
    # -- trivial pre-conditions should be added last, for simplicity

    #___________________________________________________________________________________________
    if pre_context_sm is None:
        # NOT: 'and ...' !
        if BeginOfLinePreContextF:
            # Mark all acceptance states with the 'trivial pre-context BeginOfLine' flag
            for state in the_state_machine.get_acceptance_state_list():
                state.set_pre_context_id(E_PreContextIDs.BEGIN_OF_LINE)
        return None

    # (*) Reverse the state machine of the pre-condition 
    reverse_pre_context = reverse.do(pre_context_sm)
        
    if BeginOfLinePreContextF:
        # Extend the existing pre-context with a preceeding 'begin-of-line'.
        reverse_newline_sm  = reverse.do(StateMachine_Newline())
        reverse_pre_context = sequentialize.do([reverse_pre_context, 
                                                reverse_newline_sm])

    # (*) Once an acceptance state is reached no further analysis is necessary.
    acceptance_pruning.do(reverse_pre_context)

    # (*) Clean up what has been done by inversion (and optionally 'BeginOfLinePreContextF')
    #     AFTER acceptance_pruning (!)
    reverse_pre_context = beautifier.do(reverse_pre_context)

    # (*) let the state machine refer to it 
    #     [Is this necessary? Is it not enough that the acceptance origins point to it? <fschaef>]
    pre_context_sm_id = reverse_pre_context.get_id()

    # (*) Associate acceptance with pre-context id. 
    for state in the_state_machine.get_acceptance_state_list():
        state.set_pre_context_id(pre_context_sm_id)
    
    return reverse_pre_context

def do(the_state_machine, pre_context_sm, BeginOfLinePreContextF):
    """Sets up a pre-condition to the given state machine. This process
       is entirely different from any sequentializing or parallelization
       of state machines. Here, the state machine representing the pre-
       condition is **not** webbed into the original state machine!

       Instead, the following happens:

          -- the pre-condition state machine is inverted, because
             it is to be walked through backwards.
          -- the inverted state machine is marked with the state machine id
             of the_state_machine.        
          -- the original state machine will refer to the inverse
             state machine of the pre-condition.
          -- the initial state origins and the origins of the acceptance
             states are marked as 'pre-conditioned' indicating the id
             of the inverted state machine of the pre-condition.             
    """
    #___________________________________________________________________________________________
    # (*) do some consistency checking   
    # -- state machines with no states are senseless here. 
    assert not the_state_machine.is_empty() 
    assert pre_context_sm is None or not pre_context_sm.is_empty()
    # -- trivial pre-conditions should be added last, for simplicity

    #___________________________________________________________________________________________
    if pre_context_sm is  None:
        if BeginOfLinePreContextF:
            # Mark all acceptance states with the 'trivial pre-context BeginOfLine' flag
            for state in the_state_machine.get_acceptance_state_list():
                state.set_pre_context_id(E_PreContextIDs.BEGIN_OF_LINE)
        return None

    # (*) Reverse the state machine of the pre-condition 
    inverse_pre_context = reverse.do(pre_context_sm)
        
    if BeginOfLinePreContextF:
        # Extend the existing pre-context with a preceeding 'begin-of-line'.
        inverse_pre_context.mount_newline_to_acceptance_states(Setup.dos_carriage_return_newline_f, 
                                                               InverseF=True)

    # (*) Once an acceptance state is reached no further analysis is necessary.
    acceptance_pruning.do(inverse_pre_context)

    # (*) Clean up what has been done by inversion (and optionally 'BeginOfLinePreContextF')
    #     AFTER acceptance_pruning (!)
    inverse_pre_context = beautifier.do(inverse_pre_context)

    # (*) let the state machine refer to it 
    #     [Is this necessary? Is it not enough that the acceptance origins point to it? <fschaef>]
    pre_context_sm_id = inverse_pre_context.get_id()

    # (*) create origin data, in case where there is none yet create new one.
    #     (do not delete, otherwise existing information gets lost)
    for state in the_state_machine.states.itervalues():
        if not state.is_acceptance(): continue
        state.set_pre_context_id(pre_context_sm_id)
    
    return inverse_pre_context

def __DFA(SM):
    if SM is None:
        return None
    elif SM.is_DFA_compliant():
        return SM

    result = beautifier.do(SM)
    return result

def is_none(SM):
    """Does the given state machine represent a pattern which 
    matches absolutely nothing?
    """
    sm = beautifier.do(SM)
    if   len(sm.states) != 1:                 return False
    elif sm.get_init_state().is_acceptance(): return False
    else:                                     return True

def do(SM_List):
    """The 'parallelize' module does a union of multiple state machines,
    even if they have different origins and need to be combined carefully.
    There is no reason, why another 'union' operation should be implemented
    in this case.
    """
    result = parallelize.do(SM_List)
    return beautifier.do(result)

def equal(X_str, Y_str):
    global X
    global Y
    global report
    exec("sm0 = " + X_str.replace("All", "All_sm").replace("None", "None_sm"))
    exec("sm1 = " + Y_str.replace("All", "All_sm").replace("None", "None_sm"))
    sm0 = beautifier.do(sm0)
    sm1 = beautifier.do(sm1)
    result = identity.do(sm0, sm1)
    if result is False:
        print "X:", X
        # print "Y:", Y
        print "Error"
        print "%s: -->\n%s" % (X_str, sm0)
        print "%s: -->\n%s" % (Y_str, sm1)
        print "#---------------------------------------------------------"
    protocol.append((X_str, "==", Y_str, result))

def _prepare_indentation_counter(ModeName, OptionsDb, CounterDb, IncidenceDb, MHI):
    """Prepare indentation counter. An indentation counter is implemented by 
    the following:

    'newline' pattern --> triggers as soon as an UNSUPPRESSED newline occurs. 
                      --> entry to the INDENTATION COUNTER.

    'suppressed newline' --> INDENTATION COUNTER is NOT triggered.
     
    The supressed newline pattern is longer (and has precedence) over the
    newline pattern. With the suppressed newline it is possible to write
    lines which overstep the newline (see backslahs in Python, for example).

    RETURNS: List of:
             [0] newline PPT and
             [1] optionally the PPT of the newline suppressor.

    The primary pattern action pair list is to be the head of all pattern
    action pairs.

    MHI = Mode hierarchie index defining the priority of the current mode.
    """
    ISetup = OptionsDb.value("indentation")
    if ISetup is None: return [], []

    check_indentation_setup(ISetup)

    if ISetup.sm_newline_suppressor.get() is not None:
        sm_suppressed_newline = sequentialize.do([ISetup.sm_newline_suppressor.get(),
                                                  ISetup.sm_newline.get()])
        sm_suppressed_newline = beautifier.do(sm_suppressed_newline)
    else:
        sm_suppressed_newline = None

    data = { 
        "counter_db":                    CounterDb,
        "indentation_setup":             ISetup,
        "incidence_db":                  IncidenceDb,
        "default_indentation_handler_f": IncidenceDb.default_indentation_handler_f(),
        "mode_name":                     ModeName,
        "sm_suppressed_newline":         sm_suppressed_newline,
    }

    ppt_list = [
        # 'newline' triggers --> indentation counter
        PPT_indentation_handler_newline(MHI, data, ISetup, CounterDb)
    ]

    if sm_suppressed_newline is not None:
        ppt_list.append(
            # 'newline-suppressor' followed by 'newline' is ignored (skipped)
            PPT_indentation_handler_suppressed_newline(MHI, 
                                                       sm_suppressed_newline)
        )

    return [], ppt_list

def detect_backward(CoreStateMachine, PostConditionStateMachine):

    """A 'backward ambiguity' denotes the case where it cannot be clearly be
       determined how far to go back from the end of a post-condition. 
       
       NOTE: This does not mean that the post-condition is ambiguous. Many
       cases that are backward ambiguous can be handled by quex's normal
       post-condition handling.

       Examples:  x/x+   is backward ambiguous because in a stream
                         of 'x' one cannot determine with a pure
                         state machine where to stop. This case,
                         though can be handled by the normal post-
                         condition implementation.

                  x+/x+  is backward ambiguous and cannot be handled
                         by the normal implementation. In fact, this
                         specification does not allow any conclusions
                         about the users intend where to reset the 
                         input after match.
    """

    __assert_state_machines(CoreStateMachine, PostConditionStateMachine)

    my_post_context_sm = PostConditionStateMachine.clone()

    # (*) Create a modified version of the post condition, where the
    #     initial state is an acceptance state, and no other. This 
    #     allows the detector to trigger on 'iteration'.
    #
    # -- delete all acceptance states in the post condition
    # for state in my_post_context_sm.states.values():
    #   state.set_acceptance(False)
    # -- set the initial state as acceptance state
    # my_post_context_sm.get_init_state().set_acceptance(True)
    my_core_sm = beautifier.do(reverse.do(CoreStateMachine))

    tmp = deepcopy(PostConditionStateMachine) # no deeepcopy needed here, I guess <fschaef 11y11m01d>
    my_post_context_sm = beautifier.do(reverse.do(tmp))

    return detect_forward(my_post_context_sm, my_core_sm)