/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.scxml2.semantics;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.commons.scxml2.ActionExecutionContext;
import org.apache.commons.scxml2.Context;
import org.apache.commons.scxml2.ErrorReporter;
import org.apache.commons.scxml2.SCInstance;
import org.apache.commons.scxml2.SCXMLExecutionContext;
import org.apache.commons.scxml2.SCXMLExpressionException;
import org.apache.commons.scxml2.SCXMLSemantics;
import org.apache.commons.scxml2.SCXMLSystemContext;
import org.apache.commons.scxml2.StateConfiguration;
import org.apache.commons.scxml2.TriggerEvent;
import org.apache.commons.scxml2.invoke.Invoker;
import org.apache.commons.scxml2.invoke.InvokerException;
import org.apache.commons.scxml2.model.Action;
import org.apache.commons.scxml2.model.DocumentOrder;
import org.apache.commons.scxml2.model.EnterableState;
import org.apache.commons.scxml2.model.Executable;
import org.apache.commons.scxml2.model.Final;
import org.apache.commons.scxml2.model.History;
import org.apache.commons.scxml2.model.Invoke;
import org.apache.commons.scxml2.model.OnEntry;
import org.apache.commons.scxml2.model.OnExit;
import org.apache.commons.scxml2.model.Script;
import org.apache.commons.scxml2.model.SimpleTransition;
import org.apache.commons.scxml2.model.TransitionalState;
import org.apache.commons.scxml2.model.ModelException;
import org.apache.commons.scxml2.model.Parallel;
import org.apache.commons.scxml2.model.SCXML;
import org.apache.commons.scxml2.model.State;
import org.apache.commons.scxml2.model.Transition;
import org.apache.commons.scxml2.model.TransitionTarget;
import org.apache.commons.scxml2.system.EventVariable;

/**
 * This class encapsulate and implements the
 * <a href="http://www.w3.org/TR/2014/CR-scxml-20140313/#AlgorithmforSCXMLInterpretation">
 *     W3C SCXML Algorithm for SCXML Interpretation</a>
 *
 * <p>Custom semantics can be created by sub-classing this implementation.</p>
 * <p>This implementation is full stateless and all methods are public accessible to make
 * it easier to extend, reuse and test its behavior.</p>
 */
public class SCXMLSemanticsImpl implements SCXMLSemantics {

    /**
     * Suffix for error event that are triggered in reaction to invalid data
     * model locations.
     */
    public static final String ERR_ILLEGAL_ALLOC = ".error.illegalalloc";

    /**
     * Optional post processing immediately following SCXMLReader. May be used
     * for removing pseudo-states etc.
     *
     * @param input  SCXML state machine
     * @param errRep ErrorReporter callback
     * @return normalized SCXML state machine, pseudo states are removed, etc.
     */
    public SCXML normalizeStateMachine(final SCXML input, final ErrorReporter errRep) {
        //it is a no-op for now
        return input;
    }

    /**
     * First step in the execution of an SCXML state machine.
     * <p>
     * This will first (re)initialize the state machine instance, destroying any existing state!
     * </p>
     * <p>
     * The first step is corresponding to the Algorithm for SCXML processing from the interpret() procedure to the
     * mainLoop() procedure up to the blocking wait for an external event.
     * </p>
     * <p>
     * This step will thus complete the SCXML initial execution and a subsequent macroStep to stabilize the state
     * machine again before returning.
     * </p>
     * <p>
     * If the state machine no longer is running after all this, first the {@link #finalStep(SCXMLExecutionContext)}
     * will be called for cleanup before returning.
     * </p>
     * @param exctx The execution context for this step
     * @throws ModelException if the state machine instance failed to initialize or a SCXML model error occurred during
     * the execution.
     */
    public void firstStep(final SCXMLExecutionContext exctx) throws ModelException {
        // (re)initialize the execution context and state machine instance
        exctx.initialize();
        // execute global script if defined
        executeGlobalScript(exctx);
        // enter initial states
        HashSet<TransitionalState> statesToInvoke = new HashSet<TransitionalState>();
        Step step = new Step(null);
        step.getTransitList().add(exctx.getStateMachine().getInitialTransition());
        microStep(exctx, step, statesToInvoke);
        // Execute Immediate Transitions

        if (exctx.isRunning()) {
            macroStep(exctx, statesToInvoke);
        }

        if (!exctx.isRunning()) {
            finalStep(exctx);
        }
    }

    /**
     * Next step in the execution of an SCXML state machine.
     * <p>
     * The next step is corresponding to the Algorithm for SCXML processing mainEventLoop() procedure after receiving an
     * external event, up to the blocking wait for another external event.
     * </p>
     * <p>
     * If the state machine isn't {@link SCXMLExecutionContext#isRunning()} (any more), invoking this method will simply
     * do nothing.
     * </p>
     * <p>
     * If the provided event is a {@link TriggerEvent#CANCEL_EVENT}, the state machine will stop running.
     * </p>
     * <p>
     * Otherwise, the event is set in the {@link SCXMLSystemContext} and processing of the event then is started, and
     * if the event leads to any transitions a microStep for this event will be performed, followed up by a macroStep
     * to stabilize the state machine again before returning.
     * </p>
     * <p>
     * If the state machine no longer is running after all this, first the {@link #finalStep(SCXMLExecutionContext)}
     * will be called for cleanup before returning.
     * </p>
     * @param exctx The execution context for this step
     * @param event The event to process
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void nextStep(final SCXMLExecutionContext exctx, final TriggerEvent event) throws ModelException {
        if (!exctx.isRunning()) {
            return;
        }
        if (isCancelEvent(event)) {
            exctx.stopRunning();
        }
        else {
            setSystemEventVariable(exctx.getScInstance(), event, false);
            processInvokes(exctx, event);
            Step step = new Step(event);
            selectTransitions(exctx, step);
            if (!step.getTransitList().isEmpty()) {
                HashSet<TransitionalState> statesToInvoke = new HashSet<TransitionalState>();
                microStep(exctx, step, statesToInvoke);
                if (exctx.isRunning()) {
                    macroStep(exctx, statesToInvoke);
                }
            }
        }
        if (!exctx.isRunning()) {
            finalStep(exctx);
        }
    }

    /**
     * The final step in the execution of an SCXML state machine.
     * <p>
     * This final step is corresponding to the Algorithm for SCXML processing exitInterpreter() procedure, after the
     * state machine stopped running.
     * </p>
     * <p>
     * If the state machine still is {@link SCXMLExecutionContext#isRunning()} invoking this method will simply
     * do nothing.
     * </p>
     * <p>
     * This final step will exit all remaining active states and cancel any active invokers.
     * </p>
     * <p>
     *  <em>TODO: the current implementation does not yet provide final donedata handling.</em>
     * </p>
     * @param exctx The execution context for this step
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void finalStep(SCXMLExecutionContext exctx) throws ModelException {
        if (exctx.isRunning()) {
            return;
        }
        ArrayList<EnterableState> configuration = new ArrayList<EnterableState>(exctx.getScInstance().getStateConfiguration().getActiveStates());
        Collections.sort(configuration, DocumentOrder.reverseDocumentOrderComparator);
        for (EnterableState es : configuration) {
            for (OnExit onexit : es.getOnExits()) {
                executeContent(exctx, onexit);
            }
            if (es instanceof TransitionalState) {
                // check if invokers are active in this state
                for (Invoke inv : ((TransitionalState)es).getInvokes()) {
                    exctx.cancelInvoker(inv);
                }
            }
            exctx.getNotificationRegistry().fireOnExit(es, es);
            exctx.getNotificationRegistry().fireOnExit(exctx.getStateMachine(), es);
            if (!(es instanceof Final && es.getParent() == null)) {
                exctx.getScInstance().getStateConfiguration().exitState(es);
            }
            // else: keep final Final
            // TODO: returnDoneEvent(s.donedata)?
        }
    }

    /**
     * Perform a micro step in the execution of a state machine.
     * <p>
     * This micro step is corresponding to the Algorithm for SCXML processing microstep() procedure.
     * <p>
     * @param exctx The execution context for this step
     * @param step The current micro step
     * @param statesToInvoke the set of activated states which invokes need to be invoked at the end of the current
     *                       macro step
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void microStep(final SCXMLExecutionContext exctx, final Step step,
                          final Set<TransitionalState> statesToInvoke)
            throws ModelException {
        buildStep(exctx, step);
        exitStates(exctx, step, statesToInvoke);
        executeTransitionContent(exctx, step);
        enterStates(exctx, step, statesToInvoke);
        step.clearIntermediateState();
    }

    /**
     * buildStep builds the exitSet and entrySet for the current configuration given the transitionList on the step.
     *
     * @param exctx The SCXML execution context
     * @param step The step containing the list of transitions to be taken
     * @throws ModelException if the result of taking the transitions would lead to an illegal configuration
     */
    public void buildStep(final SCXMLExecutionContext exctx, final Step step) throws ModelException {
        step.clearIntermediateState();

        // compute exitSet, if there is something to exit and record their History configurations if applicable
        if (!exctx.getScInstance().getStateConfiguration().getActiveStates().isEmpty()) {
            computeExitSet(step, exctx.getScInstance().getStateConfiguration());
        }
        // compute entrySet
        computeEntrySet(exctx, step);

        // default result states to entrySet
        Set<EnterableState> states = step.getEntrySet();
        if (!step.getExitSet().isEmpty()) {
            // calculate result states by taking current states, subtracting exitSet and adding entrySet
            states = new HashSet<EnterableState>(exctx.getScInstance().getStateConfiguration().getStates());
            states.removeAll(step.getExitSet());
            states.addAll(step.getEntrySet());
        }
        // validate the result states represent a legal configuration
        if (exctx.isCheckLegalConfiguration() && !isLegalConfiguration(states, exctx.getErrorReporter())) {
            throw new ModelException("Illegal state machine configuration!");
        }
    }

    /**
     * Perform a macro step in the execution of a state machine.
     * <p>
     * This macro step is corresponding to the Algorithm for SCXML processing mainEventLoop() procedure macro step
     * sub-flow, which are the first <em>3</em> steps of the described <em>4</em>, so everything up to the blocking
     * wait for an external event.
     * <p>
     * @param exctx The execution context for this step
     * @param statesToInvoke the set of activated states which invokes need to be invoked at the end of the current
     *                       macro step
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void macroStep(final SCXMLExecutionContext exctx, final Set<TransitionalState> statesToInvoke)
            throws ModelException {
        do {
            boolean macroStepDone = false;
            do {
                Step step = new Step(null);
                selectTransitions(exctx, step);
                if (step.getTransitList().isEmpty()) {
                    TriggerEvent event = exctx.nextInternalEvent();
                    if (event != null) {
                        if (isCancelEvent(event)) {
                            exctx.stopRunning();
                        }
                        else {
                            setSystemEventVariable(exctx.getScInstance(), event, true);
                            step = new Step(event);
                            selectTransitions(exctx, step);
                        }
                    }
                }
                if (step.getTransitList().isEmpty()) {
                    macroStepDone = true;
                }
                else {
                    microStep(exctx, step, statesToInvoke);
                }

            } while (exctx.isRunning() && !macroStepDone);

            if (exctx.isRunning() && !statesToInvoke.isEmpty()) {
                initiateInvokes(exctx, statesToInvoke);
                statesToInvoke.clear();
            }
        } while (exctx.isRunning() && exctx.hasPendingInternalEvent());
    }

    /**
     * Compute and store the set of states to exit for the current list of transitions in the provided step.
     * <p>
     * This method corresponds to the Algorithm for SCXML processing computeExitSet() procedure.
     * <p>
     * @param step The step containing the list of transitions to be taken
     * @param stateConfiguration The current configuration of the state machine ({@link SCInstance#getStateConfiguration()}).
     */
    public void computeExitSet(final Step step, final StateConfiguration stateConfiguration) {
        if (!stateConfiguration.getActiveStates().isEmpty()) {
            for (SimpleTransition st : step.getTransitList()) {
                computeExitSet(st, step.getExitSet(), stateConfiguration.getActiveStates());
            }
            recordHistory(step, stateConfiguration.getStates(), stateConfiguration.getActiveStates());
        }
    }

    /**
     * Compute and store the set of states to exit for one specific transition in the provided step.
     * <p>
     * This method corresponds to the Algorithm for SCXML processing computeExitSet() procedure.
     * <p>
     * @param transition The transition to compute the states to exit from
     * @param exitSet The set for adding the states to exit to
     * @param activeStates The current active states of the state machine ({@link StateConfiguration#getActiveStates()}).
     */
    public void computeExitSet(SimpleTransition transition, Set<EnterableState> exitSet, Set<EnterableState> activeStates) {
        if (!transition.getTargets().isEmpty()) {
            TransitionalState transitionDomain = transition.getTransitionDomain();
            if (transitionDomain == null) {
                // root transition: every active state will be exited
                exitSet.addAll(activeStates);
            }
            else {
                for (EnterableState state : activeStates) {
                    if (state.isDescendantOf(transitionDomain)) {
                        exitSet.add(state);
                    }
                }
            }
        }
    }

    /**
     * Record the history configurations for states to exit if applicable and temporarily store this in the step.
     * <p>
     * These history configurations must be pre-recorded as they might impact (re)entrance calculation during
     * {@link #computeEntrySet(SCXMLExecutionContext, Step)}.
     * </p>
     * <p>
     * Only after the new configuration has been validated (see: {@link #isLegalConfiguration(Set, ErrorReporter)}), the
     * history configurations will be persisted during the actual {@link #exitStates(SCXMLExecutionContext, Step, Set)}
     * processing.
     * </p>
     * @param step The step containing the list of states to exit, and the map to record the new history configurations
     * @param atomicStates The current set of active atomic states in the state machine
     * @param activeStates The current set of all active states in the state machine
     */
    public void recordHistory(final Step step, final Set<EnterableState> atomicStates, final Set<EnterableState> activeStates) {
        for (EnterableState es : step.getExitSet()) {
            if (es instanceof TransitionalState && ((TransitionalState)es).hasHistory()) {
                TransitionalState ts = (TransitionalState)es;
                Set<EnterableState> shallow = null;
                Set<EnterableState> deep = null;
                for (History h : ts.getHistory()) {
                    if (h.isDeep()) {
                        if (deep == null) {
                            //calculate deep history for a given state once
                            deep = new HashSet<EnterableState>();
                            for (EnterableState ott : atomicStates) {
                                if (ott.isDescendantOf(es)) {
                                    deep.add(ott);
                                }
                            }
                        }
                        step.getNewHistoryConfigurations().put(h, deep);
                    } else {
                        if (shallow == null) {
                            //calculate shallow history for a given state once
                            shallow = new HashSet<EnterableState>(ts.getChildren());
                            shallow.retainAll(activeStates);
                        }
                        step.getNewHistoryConfigurations().put(h, shallow);
                    }
                }
            }
        }
    }

    /**
     * Compute and store the set of states to enter for the current list of transitions in the provided step.
     * <p>
     * This method corresponds to the Algorithm for SCXML processing computeEntrySet() procedure.
     * <p>
     * @param exctx The execution context for this step
     * @param step The step containing the list of transitions to be taken
     */
    public void computeEntrySet(final SCXMLExecutionContext exctx, final Step step) {
        Set<History> historyTargets = new HashSet<History>();
        Set<EnterableState> entrySet = new HashSet<EnterableState>();
        for (SimpleTransition st : step.getTransitList()) {
            for (TransitionTarget tt : st.getTargets()) {
                if (tt instanceof EnterableState) {
                    entrySet.add((EnterableState) tt);
                }
                else {
                    // History
                    historyTargets.add((History)tt);
                }
            }
        }
        for (EnterableState es : entrySet) {
            addDescendantStatesToEnter(exctx, step, es);
        }
        for (History h : historyTargets) {
            addDescendantStatesToEnter(exctx, step, h);
        }
        for (SimpleTransition st : step.getTransitList()) {
            TransitionalState ancestor = st.getTransitionDomain();
            for (TransitionTarget tt : st.getTargets()) {
                addAncestorStatesToEnter(exctx, step, tt, ancestor);
            }
        }
    }

    /**
     * This method corresponds to the Algorithm for SCXML processing addDescendantStatesToEnter() procedure.
     *
     * @param exctx The execution context for this step
     * @param step The step
     * @param tt The TransitionTarget
     */
    public void addDescendantStatesToEnter(final SCXMLExecutionContext exctx, final Step step,
                                              final TransitionTarget tt) {
        if (tt instanceof History) {
            History h = (History) tt;
            Set<EnterableState> lastConfiguration = step.getNewHistoryConfigurations().get(h);
            if (lastConfiguration == null) {
                lastConfiguration = exctx.getScInstance().getLastConfiguration(h);
            }
            if (lastConfiguration.isEmpty()) {
                step.getDefaultHistoryTransitions().put(h.getParent(), h.getTransition());
                for (TransitionTarget dtt : h.getTransition().getTargets()) {
                    addDescendantStatesToEnter(exctx, step, dtt);
                }
                for (TransitionTarget dtt : h.getTransition().getTargets()) {
                    addAncestorStatesToEnter(exctx, step, dtt, tt.getParent());
                }
            } else {
                for (TransitionTarget dtt : lastConfiguration) {
                    addDescendantStatesToEnter(exctx, step, dtt);
                }
                for (TransitionTarget dtt : lastConfiguration) {
                    addAncestorStatesToEnter(exctx, step, dtt, tt.getParent());
                }
            }
        }
        else { // tt instanceof EnterableState
            EnterableState es = (EnterableState)tt;
            step.getEntrySet().add(es);
            if (es instanceof Parallel) {
                for (EnterableState child : ((Parallel)es).getChildren()) {
                    if (!containsDescendant(step.getEntrySet(), child)) {
                        addDescendantStatesToEnter(exctx, step, child);
                    }
                }
            }
            else if (es instanceof State && ((State) es).isComposite()) {
                step.getDefaultEntrySet().add(es);
                for (TransitionTarget dtt : ((State)es).getInitial().getTransition().getTargets()) {
                    addDescendantStatesToEnter(exctx, step, dtt);
                }
                for (TransitionTarget dtt : ((State)es).getInitial().getTransition().getTargets()) {
                    addAncestorStatesToEnter(exctx, step, dtt, tt);
                }
            }
        }
    }

    /**
     * This method corresponds to the Algorithm for SCXML processing addAncestorStatesToEnter() procedure.
     *
     * @param exctx The execution context for this step
     * @param step The step
     * @param tt The TransitionTarget
     * @param ancestor The ancestor TransitionTarget
     */
    public void addAncestorStatesToEnter(final SCXMLExecutionContext exctx, final Step step,
                                            final TransitionTarget tt, TransitionTarget ancestor) {
        // for for anc in getProperAncestors(tt,ancestor)
        for (int i = tt.getNumberOfAncestors()-1; i > -1; i--) {
            EnterableState anc = tt.getAncestor(i);
            if (anc == ancestor) {
                break;
            }
            step.getEntrySet().add(anc);
            if (anc instanceof Parallel) {
                for (EnterableState child : ((Parallel)anc).getChildren()) {
                    if (!containsDescendant(step.getEntrySet(), child)) {
                        addDescendantStatesToEnter(exctx, step, child);
                    }
                }

            }
        }
    }

    /**
     * @return Returns true if a member of the provided states set is a descendant of the provided state.
     * @param states the set of states to check for descendants
     * @param state the state to check with
     */
    public boolean containsDescendant(Set<EnterableState> states, EnterableState state) {
        for (EnterableState es : states) {
            if (es.isDescendantOf(state)) {
                return true;
            }
        }
        return false;
    }

    /**
     * This method corresponds to the Algorithm for SCXML processing selectTransitions() as well as the
     * selectEventlessTransitions() procedure, depending on the event (or null) in the provided step
     * <p>
     * @param exctx The execution context for this step
     * @param step The step
     */
    public void selectTransitions(final SCXMLExecutionContext exctx, final Step step) throws ModelException {
        step.getTransitList().clear();
        ArrayList<Transition> enabledTransitions = new ArrayList<Transition>();

        ArrayList<EnterableState> configuration = new ArrayList<EnterableState>(exctx.getScInstance().getStateConfiguration().getActiveStates());
        Collections.sort(configuration,DocumentOrder.documentOrderComparator);

        HashSet<EnterableState> visited = new HashSet<EnterableState>();

        String eventName = step.getEvent() != null ? step.getEvent().getName() : null;
        for (EnterableState es : configuration) {
            if (es.isAtomicState()) {
                if (es instanceof Final) {
                    // Final states don't have transitions, skip to parent
                    if (es.getParent() == null) {
                        // should not happen: a top level active Final state should have stopped the state machine
                        throw new ModelException("Illegal state machine configuration: encountered top level <final> "
                                + "state while processing an event");
                    }
                    else {
                        es = es.getParent();
                    }
                }
                TransitionalState state = (TransitionalState)es;
                TransitionalState current = state;
                int ancestorIndex = state.getNumberOfAncestors()-1;
                boolean transitionMatched = false;
                do {
                    for (Transition transition : current.getTransitionsList()) {
                        if (transitionMatched = matchTransition(exctx, transition, eventName)) {
                            enabledTransitions.add(transition);
                            break;
                        }
                    }
                    current = (!transitionMatched && ancestorIndex > -1) ? state.getAncestor(ancestorIndex--) : null;
                } while (!transitionMatched && current != null && visited.add(current));
            }
        }
        removeConflictingTransitions(exctx, step, enabledTransitions);
    }

    /**
     * This method corresponds to the Algorithm for SCXML processing removeConflictingTransitions() procedure.
     *
     * @param exctx The execution context for this step
     * @param step The step
     * @param enabledTransitions The list of enabled transitions
     */
    public void removeConflictingTransitions(final SCXMLExecutionContext exctx, final Step step,
                                             final List<Transition> enabledTransitions) {
        LinkedHashSet<Transition> filteredTransitions = new LinkedHashSet<Transition>();
        LinkedHashSet<Transition> preemptedTransitions = new LinkedHashSet<Transition>();
        Map<Transition, Set<EnterableState>> exitSets = new HashMap<Transition, Set<EnterableState>>();

        Set<EnterableState> configuration = exctx.getScInstance().getStateConfiguration().getActiveStates();
        Collections.sort(enabledTransitions, DocumentOrder.documentOrderComparator);

        for (Transition t1 : enabledTransitions) {
            boolean t1Preempted = false;
            Set<EnterableState> t1ExitSet = exitSets.get(t1);
            for (Transition t2 : filteredTransitions) {
                if (t1ExitSet == null) {
                    t1ExitSet = new HashSet<EnterableState>();
                    computeExitSet(t1, t1ExitSet, configuration);
                    exitSets.put(t1, t1ExitSet);
                }
                Set<EnterableState> t2ExitSet = exitSets.get(t2);
                if (t2ExitSet == null) {
                    t2ExitSet = new HashSet<EnterableState>();
                    computeExitSet(t2, t2ExitSet, configuration);
                    exitSets.put(t2, t2ExitSet);
                }
                Set<EnterableState> smaller = t1ExitSet.size() < t2ExitSet.size() ? t1ExitSet : t2ExitSet;
                Set<EnterableState> larger = smaller == t1ExitSet ? t2ExitSet : t1ExitSet;
                boolean hasIntersection = false;
                for (EnterableState s1 : smaller) {
                    hasIntersection = larger.contains(s1);
                    if (hasIntersection) {
                        break;
                    }
                }
                if (hasIntersection) {
                    if (t1.getParent().isDescendantOf(t2.getParent())) {
                        preemptedTransitions.add(t2);
                    }
                    else {
                        t1Preempted = true;
                        break;
                    }
                }
            }
            if (t1Preempted) {
                exitSets.remove(t1);
            }
            else {
                for (Transition preempted : preemptedTransitions) {
                    filteredTransitions.remove(preempted);
                    exitSets.remove(preempted);
                }
                filteredTransitions.add(t1);
            }
        }
        step.getTransitList().addAll(filteredTransitions);
    }

    /**
     * @param exctx The execution context for this step
     * @param transition The transition
     * @param eventName The (optional) event name to match against
     * @return Returns true if the transition matches against the provided eventName, or is event-less when no eventName
     *         is provided, <em>AND</em> its (optional) condition guard evaluates to true.
     */
    public boolean matchTransition(final SCXMLExecutionContext exctx, final Transition transition, final String eventName) {
        if (eventName != null) {
            if (!(transition.isNoEventsTransition() || transition.isAllEventsTransition())) {
                boolean eventMatch = false;
                for (String event : transition.getEvents()) {
                    if (eventName.startsWith(event)) {
                        if (eventName.length() == event.length() || eventName.charAt(event.length())=='.')
                            eventMatch = true;
                        break;
                    }
                }
                if (!eventMatch) {
                    return false;
                }
            }
            else if (!transition.isAllEventsTransition()) {
                return false;
            }
        }
        else if (!transition.isNoEventsTransition()) {
            return false;
        }
        if (transition.getCond() != null) {
            Boolean result = Boolean.FALSE;
            Context context = exctx.getScInstance().getContext(transition.getParent());
            context.setLocal(Context.NAMESPACES_KEY, transition.getNamespaces());
            try {
                if ((result = exctx.getEvaluator().evalCond(context, transition.getCond())) == null) {
                    result = Boolean.FALSE;
                    if (exctx.getAppLog().isDebugEnabled()) {
                        exctx.getAppLog().debug("Treating as false because the cond expression was evaluated as null: '"
                                + transition.getCond() + "'");
                    }
                }
            }
            catch (SCXMLExpressionException e) {
                exctx.getInternalIOProcessor().addEvent(new TriggerEvent(TriggerEvent.ERROR_EXECUTION, TriggerEvent.ERROR_EVENT));
                exctx.getErrorReporter().onError(ErrorConstants.EXPRESSION_ERROR, "Treating as false due to error: "
                        + e.getMessage(), transition);
            }
            finally {
                context.setLocal(Context.NAMESPACES_KEY, null);
            }
            return result;
        }
        return true;
    }

    /**
     * This method corresponds to the Algorithm for SCXML processing isFinalState() function.
     *
     * @param es the enterable state to check
     * @param configuration the current state machine configuration
     * @return Return true if s is a compound state and one of its children is an active final state (i.e. is a member
     *         of the current configuration), or if s is a parallel state and isInFinalState is true of all its children.
     */
    public boolean isInFinalState(final EnterableState es, final Set<EnterableState> configuration) {
        if (es instanceof State) {
            for (EnterableState child : ((State)es).getChildren()) {
                if (child instanceof Final && configuration.contains(child)) {
                    return true;
                }
            }
        }
        else if (es instanceof Parallel) {
            for (EnterableState child : ((Parallel)es).getChildren()) {
                if (!isInFinalState(child, configuration)) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

    /**
     * Checks if an external event was send (back) by an specific Invoker
     *
     * @param invokerId the invokerId
     *
     * @param event received external event
     * @return true if this event was send by the specific Invoker
     */
    public boolean isInvokerEvent(final String invokerId, final TriggerEvent event) {
        return event.getName().equals("done.invoke."+invokerId) ||
                event.getName().startsWith("done.invoke."+invokerId+".");
    }

    /**
     * Check if an external event indicates the state machine execution must be cancelled.
     *
     * @param event received external event
     * @return true if this event is of type {@link TriggerEvent#CANCEL_EVENT}.
     */
    public boolean isCancelEvent(TriggerEvent event) {
        return (event.getType() == TriggerEvent.CANCEL_EVENT);
    }

    /**
     * Checks whether a given set of states is a legal Harel State Table
     * configuration (with the respect to the definition of the OR and AND
     * states).
     *
     * @param states a set of states
     * @param errRep ErrorReporter to report detailed error info if needed
     * @return true if a given state configuration is legal, false otherwise
     */
    public boolean isLegalConfiguration(final Set<EnterableState> states, final ErrorReporter errRep) {
        /*
         * For every active state we add 1 to the count of its parent. Each
         * Parallel should reach count equal to the number of its children and
         * contribute by 1 to its parent. Each State should reach count exactly
         * 1. SCXML elemnt (top) should reach count exactly 1. We essentially
         * summarize up the hierarchy tree starting with a given set of
         * states = active configuration.
         */
        boolean legalConfig = true; // let's be optimists
        Map<EnterableState, Set<EnterableState>> counts = new HashMap<EnterableState, Set<EnterableState>>();
        Set<EnterableState> scxmlCount = new HashSet<EnterableState>();
        for (EnterableState es : states) {
            EnterableState parent;
            while ((parent = es.getParent()) != null) {
                Set<EnterableState> cnt = counts.get(parent);
                if (cnt == null) {
                    cnt = new HashSet<EnterableState>();
                    counts.put(parent, cnt);
                }
                cnt.add(es);
                es = parent;
            }
            //top-level contribution
            scxmlCount.add(es);
        }
        if (scxmlCount.size() > 1) {
            errRep.onError(ErrorConstants.ILLEGAL_CONFIG, "Multiple top-level OR states active!", scxmlCount);
            legalConfig = false;
        }
        else {
            //Validate child counts:
            for (Map.Entry<EnterableState, Set<EnterableState>> entry : counts.entrySet()) {
                EnterableState es = entry.getKey();
                Set<EnterableState> count = entry.getValue();
                if (es instanceof Parallel) {
                    Parallel p = (Parallel) es;
                    if (count.size() < p.getChildren().size()) {
                        errRep.onError(ErrorConstants.ILLEGAL_CONFIG, "Not all AND states active for parallel " + p.getId(), entry);
                        legalConfig = false;
                    }
                } else {
                    if (count.size() > 1) {
                        errRep.onError(ErrorConstants.ILLEGAL_CONFIG, "Multiple OR states active for state " + es.getId(), entry);
                        legalConfig = false;
                    }
                }
                count.clear(); //cleanup
            }
        }
        //cleanup
        scxmlCount.clear();
        counts.clear();
        return legalConfig;
    }

    /**
     * Stores the provided event in the system context
     * <p>
     * For the event a EventVariable is instantiated and the provided event its type is mapped to the one of the
     * SCXML specification predefined types.
     * </p>
     * @param scInstance the state machine instance holding the system context
     * @param event The event being stored
     * @param internal Flag indicating the event was received internally or externally
     */
    public void setSystemEventVariable(final SCInstance scInstance, final TriggerEvent event, boolean internal) {
        Context systemContext = scInstance.getSystemContext();
        EventVariable eventVar = null;
        if (event != null) {
            String eventType = internal ? EventVariable.TYPE_INTERNAL : EventVariable.TYPE_EXTERNAL;

            final int triggerEventType = event.getType();
            if (triggerEventType == TriggerEvent.ERROR_EVENT || triggerEventType == TriggerEvent.CHANGE_EVENT) {
                eventType = EventVariable.TYPE_PLATFORM;
            }

            // TODO: determine sendid, origin, originType and invokeid based on context later.
            eventVar = new EventVariable(event.getName(), eventType, null, null, null, null, event.getPayload());
        }
        systemContext.setLocal(SCXMLSystemContext.EVENT_KEY, eventVar);
    }

    /**
     * Executes the global SCXML script element
     *
     * @param exctx The execution context
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void executeGlobalScript(final SCXMLExecutionContext exctx) throws ModelException {
        Script globalScript = exctx.getStateMachine().getGlobalScript();
        if ( globalScript != null) {
            try {
                globalScript.execute(exctx.getActionExecutionContext());
            } catch (SCXMLExpressionException e) {
                exctx.getInternalIOProcessor().addEvent(new TriggerEvent(TriggerEvent.ERROR_EXECUTION, TriggerEvent.ERROR_EVENT));
                exctx.getErrorReporter().onError(ErrorConstants.EXPRESSION_ERROR, e.getMessage(), exctx.getStateMachine());
            }
        }
    }

    /**
     * This method corresponds to the Algorithm for SCXML processing exitStates() procedure, where the states to exit
     * already have been pre-computed in {@link #microStep(SCXMLExecutionContext, Step, java.util.Set)}.
     *
     * @param exctx The execution context for this micro step
     * @param step the step
     * @param statesToInvoke the set of activated states which invokes need to be invoked at the end of the current
     *                       macro step
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void exitStates(final SCXMLExecutionContext exctx, final Step step,
                           final Set<TransitionalState> statesToInvoke)
            throws ModelException {
        if (step.getExitSet().isEmpty()) {
            return;
        }
        ArrayList<EnterableState> exitList = new ArrayList<EnterableState>(step.getExitSet());
        Collections.sort(exitList, DocumentOrder.reverseDocumentOrderComparator);

        for (EnterableState es : exitList) {

            if (es instanceof TransitionalState && ((TransitionalState)es).hasHistory()) {
                // persist the new history configurations for this state to exit
                for (History h : ((TransitionalState)es).getHistory()) {
                    exctx.getScInstance().setLastConfiguration(h, step.getNewHistoryConfigurations().get(h));
                }
            }

            boolean onexitEventRaised = false;
            for (OnExit onexit : es.getOnExits()) {
                executeContent(exctx, onexit);
                if (!onexitEventRaised && onexit.isRaiseEvent()) {
                    onexitEventRaised = true;
                    exctx.getInternalIOProcessor().addEvent(new TriggerEvent("exit.state."+es.getId(), TriggerEvent.CHANGE_EVENT));
                }
            }
            exctx.getNotificationRegistry().fireOnExit(es, es);
            exctx.getNotificationRegistry().fireOnExit(exctx.getStateMachine(), es);

            if (es instanceof TransitionalState && !statesToInvoke.remove(es)) {
                // check if invokers are active in this state
                for (Invoke inv : ((TransitionalState)es).getInvokes()) {
                    exctx.cancelInvoker(inv);
                }
            }
            exctx.getScInstance().getStateConfiguration().exitState(es);
        }
    }

    /**
     * Executes the executable content for all transitions in the micro step
     *
     * @param exctx The execution context for this micro step
     * @param step the step
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void executeTransitionContent(final SCXMLExecutionContext exctx, final Step step) throws ModelException {
        for (SimpleTransition transition : step.getTransitList()) {
            executeContent(exctx, transition);
        }
    }

    /**
     * Executes the executable content for a specific executable in the micro step
     *
     * @param exctx The execution context for this micro step
     * @param exec the executable providing the execution content
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void executeContent(SCXMLExecutionContext exctx, Executable exec) throws ModelException {
        try {
            for (Action action : exec.getActions()) {
                action.execute(exctx.getActionExecutionContext());
            }
        } catch (SCXMLExpressionException e) {
            exctx.getInternalIOProcessor().addEvent(new TriggerEvent(TriggerEvent.ERROR_EXECUTION, TriggerEvent.ERROR_EVENT));
            exctx.getErrorReporter().onError(ErrorConstants.EXPRESSION_ERROR, e.getMessage(), exec);
        }
        if (exec instanceof Transition) {
            Transition t = (Transition)exec;
            if (t.getTargets().isEmpty()) {
                notifyOnTransition(exctx, t, t.getParent());
            }
            else {
                for (TransitionTarget tt : t.getTargets()) {
                    notifyOnTransition(exctx, t, tt);
                }
            }
        }
    }

    /**
     * Notifies SCXMLListeners on the transition taken
     *
     * @param exctx The execution context for this micro step
     * @param t The Transition taken
     * @param target The target of the Transition
     */
    public void notifyOnTransition(final SCXMLExecutionContext exctx, final Transition t,
                                      final TransitionTarget target) {
        EventVariable event = (EventVariable)exctx.getScInstance().getSystemContext().getVars().get(SCXMLSystemContext.EVENT_KEY);
        String eventName = event != null ? event.getName() : null;
        exctx.getNotificationRegistry().fireOnTransition(t, t.getParent(), target, t, eventName);
        exctx.getNotificationRegistry().fireOnTransition(exctx.getStateMachine(), t.getParent(), target, t, eventName);
    }

    /**
     * This method corresponds to the Algorithm for SCXML processing enterStates() procedure, where the states to enter
     * already have been pre-computed in {@link #microStep(SCXMLExecutionContext, Step, java.util.Set)}.
     *
     * @param exctx The execution context for this micro step
     * @param step the step
     * @param statesToInvoke the set of activated states which invokes need to be invoked at the end of the current
     *                       macro step
     * @throws ModelException if a SCXML model error occurred during the execution.
     */
    public void enterStates(final SCXMLExecutionContext exctx, final Step step,
                            final Set<TransitionalState> statesToInvoke)
            throws ModelException {
        if (step.getEntrySet().isEmpty()) {
            return;
        }
        ArrayList<EnterableState> entryList = new ArrayList<EnterableState>(step.getEntrySet());
        Collections.sort(entryList, DocumentOrder.documentOrderComparator);
        for (EnterableState es : entryList) {
            exctx.getScInstance().getStateConfiguration().enterState(es);
            if (es instanceof TransitionalState && !((TransitionalState)es).getInvokes().isEmpty()) {
                statesToInvoke.add((TransitionalState) es);
            }

            boolean onentryEventRaised = false;
            for (OnEntry onentry : es.getOnEntries()) {
                executeContent(exctx, onentry);
                if (!onentryEventRaised && onentry.isRaiseEvent()) {
                    onentryEventRaised = true;
                    exctx.getInternalIOProcessor().addEvent(new TriggerEvent("entry.state."+es.getId(), TriggerEvent.CHANGE_EVENT));
                }
            }
            exctx.getNotificationRegistry().fireOnEntry(es, es);
            exctx.getNotificationRegistry().fireOnEntry(exctx.getStateMachine(), es);

            if (es instanceof State && step.getDefaultEntrySet().contains(es) && ((State)es).getInitial() != null) {
                executeContent(exctx, ((State)es).getInitial().getTransition());
            }
            if (es instanceof TransitionalState) {
                SimpleTransition hTransition = step.getDefaultHistoryTransitions().get(es);
                if (hTransition != null) {
                    executeContent(exctx, hTransition);
                }
            }

            if (es instanceof Final) {
                State parent = (State)es.getParent();
                if (parent == null) {
                    exctx.stopRunning();
                }
                else {
                    exctx.getInternalIOProcessor().addEvent(new TriggerEvent("done.state."+parent.getId(),TriggerEvent.CHANGE_EVENT));
                    if (parent.isRegion()) {
                        if (isInFinalState(parent.getParent(), exctx.getScInstance().getStateConfiguration().getActiveStates())) {
                            exctx.getInternalIOProcessor().addEvent(new TriggerEvent("done.state."+parent.getParent().getId()
                                    , TriggerEvent.CHANGE_EVENT));
                        }
                    }
                }
            }
        }
    }

    /**
     * Initiate any new invoked activities.
     *
     * @param exctx provides the execution context
     * @param statesToInvoke the set of activated states which invokes need to be invoked
     */
    public void initiateInvokes(final SCXMLExecutionContext exctx,
                                final Set<TransitionalState> statesToInvoke) throws ModelException {
        ActionExecutionContext aexctx = exctx.getActionExecutionContext();
        for (TransitionalState ts : statesToInvoke) {
            for (Invoke invoke : ts.getInvokes()) {
                Context ctx = aexctx.getContext(invoke.getParentEnterableState());
                String exctxKey = invoke.getCurrentSCXMLExecutionContextKey();
                ctx.setLocal(exctxKey, exctx);
                invoke.execute(aexctx);
                ctx.setLocal(exctxKey, null);
            }
        }
    }

    /**
     * Forward events to invoked activities, execute finalize handlers.
     *
     * @param exctx provides the execution context
     * @param event The events to be forwarded
     *
     * @throws ModelException in case there is a fatal SCXML object model problem.
     */
    public void processInvokes(final SCXMLExecutionContext exctx, final TriggerEvent event) throws ModelException {
        for (Map.Entry<Invoke, String> entry : exctx.getInvokeIds().entrySet()) {
            if (!isInvokerEvent(entry.getValue(), event)) {
                if (entry.getKey().isAutoForward()) {
                    Invoker inv = exctx.getInvoker(entry.getKey());
                    try {
                        inv.parentEvent(event);
                    } catch (InvokerException ie) {
                        exctx.getAppLog().error(ie.getMessage(), ie);
                        throw new ModelException(ie.getMessage(), ie.getCause());
                    }
                }
            }
            /*
            else {
                // TODO: applyFinalize
            }
            */
        }
    }
}