/*
 * 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.scxml.semantics;

import java.io.Serializable;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.apache.commons.scxml.Context;
import org.apache.commons.scxml.ErrorReporter;
import org.apache.commons.scxml.Evaluator;
import org.apache.commons.scxml.EventDispatcher;
import org.apache.commons.scxml.NotificationRegistry;
import org.apache.commons.scxml.PathResolver;
import org.apache.commons.scxml.SCInstance;
import org.apache.commons.scxml.SCXMLExpressionException;
import org.apache.commons.scxml.SCXMLHelper;
import org.apache.commons.scxml.SCXMLSemantics;
import org.apache.commons.scxml.Step;
import org.apache.commons.scxml.TriggerEvent;
import org.apache.commons.scxml.invoke.Invoker;
import org.apache.commons.scxml.invoke.InvokerException;
import org.apache.commons.scxml.model.Action;
import org.apache.commons.scxml.model.Finalize;
import org.apache.commons.scxml.model.History;
import org.apache.commons.scxml.model.Initial;
import org.apache.commons.scxml.model.Invoke;
import org.apache.commons.scxml.model.ModelException;
import org.apache.commons.scxml.model.OnEntry;
import org.apache.commons.scxml.model.OnExit;
import org.apache.commons.scxml.model.Parallel;
import org.apache.commons.scxml.model.Param;
import org.apache.commons.scxml.model.Path;
import org.apache.commons.scxml.model.SCXML;
import org.apache.commons.scxml.model.State;
import org.apache.commons.scxml.model.Transition;
import org.apache.commons.scxml.model.TransitionTarget;

/**
 * <p>This class encapsulates a particular SCXML semantics, that is, a
 * particular semantic interpretation of Harel Statecharts, which aligns
 * mostly with W3C SCXML July 5 public draft (that is, UML 1.5). However,
 * certain aspects are taken from STATEMATE.</p>
 *
 * <p>Specific semantics can be created by subclassing this class.</p>
 */
public class SCXMLSemanticsImpl implements SCXMLSemantics, Serializable {

    /**
     * Serial version UID.
     */
    private static final long serialVersionUID = 1L;

    /**
     * SCXML Logger for the application.
     */
    private Log appLog = LogFactory.getLog(SCXMLSemantics.class);

    /**
     * The TransitionTarget comparator.
     */
    private TransitionTargetComparator targetComparator =
        new TransitionTargetComparator();

    /**
     * Current document namespaces are saved under this key in the parent
     * state's context.
     */
    private static final String NAMESPACES_KEY = "_ALL_NAMESPACES";

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

    /**
     * @param input
     *            SCXML state machine
     * @return normalized SCXML state machine, pseudo states are removed, etc.
     * @param errRep
     *            ErrorReporter callback
     */
    public SCXML normalizeStateMachine(final SCXML input,
            final ErrorReporter errRep) {
        //it is a no-op for now
        return input;
    }

    /**
     * @param input
     *            SCXML state machine [in]
     * @param targets
     *            a set of initial targets to populate [out]
     * @param entryList
     *            a list of States and Parallels to enter [out]
     * @param errRep
     *            ErrorReporter callback [inout]
     * @param scInstance
     *            The state chart instance [in]
     * @throws ModelException
     *             in case there is a fatal SCXML object model problem.
     */
    public void determineInitialStates(final SCXML input, final Set targets,
            final List entryList, final ErrorReporter errRep,
            final SCInstance scInstance)
            throws ModelException {
        TransitionTarget tmp = input.getInitialTarget();
        if (tmp == null) {
            errRep.onError(ErrorConstants.NO_INITIAL,
                    "SCXML initialstate is missing!", input);
        } else {
            targets.add(tmp);
            determineTargetStates(targets, errRep, scInstance);
            //set of ALL entered states (even if initialState is a jump-over)
            Set onEntry = SCXMLHelper.getAncestorClosure(targets, null);
            // sort onEntry according state hierarchy
            Object[] oen = onEntry.toArray();
            onEntry.clear();
            Arrays.sort(oen, getTTComparator());
            // we need to impose reverse order for the onEntry list
            List entering = Arrays.asList(oen);
            Collections.reverse(entering);
            entryList.addAll(entering);

        }
    }

    /**
     * Executes all OnExit/Transition/OnEntry transitional actions.
     *
     * @param step
     *            provides EntryList, TransitList, ExitList gets
     *            updated its AfterStatus/Events
     * @param stateMachine
     *            state machine - SCXML instance
     * @param evtDispatcher
     *            the event dispatcher - EventDispatcher instance
     * @param errRep
     *            error reporter
     * @param scInstance
     *            The state chart instance
     * @throws ModelException
     *             in case there is a fatal SCXML object model problem.
     */
    public void executeActions(final Step step, final SCXML stateMachine,
            final EventDispatcher evtDispatcher,
            final ErrorReporter errRep, final SCInstance scInstance)
    throws ModelException {
        NotificationRegistry nr = scInstance.getNotificationRegistry();
        Collection internalEvents = step.getAfterStatus().getEvents();
        Map invokers = scInstance.getInvokers();
        // ExecutePhaseActions / OnExit
        for (Iterator i = step.getExitList().iterator(); i.hasNext();) {
            TransitionTarget tt = (TransitionTarget) i.next();
            OnExit oe = tt.getOnExit();
            try {
                for (Iterator onExitIter = oe.getActions().iterator();
                        onExitIter.hasNext();) {
                    ((Action) onExitIter.next()).execute(evtDispatcher,
                        errRep, scInstance, appLog, internalEvents);
                }
            } catch (SCXMLExpressionException e) {
                errRep.onError(ErrorConstants.EXPRESSION_ERROR, e.getMessage(),
                        oe);
            }
            // check if invoke is active in this state
            if (invokers.containsKey(tt)) {
                Invoker toCancel = (Invoker) invokers.get(tt);
                try {
                    toCancel.cancel();
                } catch (InvokerException ie) {
                    TriggerEvent te = new TriggerEvent(tt.getId()
                        + ".invoke.cancel.failed", TriggerEvent.ERROR_EVENT);
                    internalEvents.add(te);
                }
                // done here, don't wait for cancel response
                invokers.remove(tt);
            }
            nr.fireOnExit(tt, tt);
            nr.fireOnExit(stateMachine, tt);
            TriggerEvent te = new TriggerEvent(tt.getId() + ".exit",
                    TriggerEvent.CHANGE_EVENT);
            internalEvents.add(te);
        }
        // ExecutePhaseActions / Transitions
        for (Iterator i = step.getTransitList().iterator(); i.hasNext();) {
            Transition t = (Transition) i.next();
            try {
                for (Iterator transitIter = t.getActions().iterator();
                        transitIter.hasNext();) {
                    ((Action) transitIter.next()).execute(evtDispatcher,
                        errRep, scInstance, appLog, internalEvents);
                }
            } catch (SCXMLExpressionException e) {
                errRep.onError(ErrorConstants.EXPRESSION_ERROR,
                    e.getMessage(), t);
            }
            List rtargets = t.getRuntimeTargets();
            for (int j = 0; j < rtargets.size(); j++) {
                TransitionTarget tt = (TransitionTarget) rtargets.get(j);
                nr.fireOnTransition(t, t.getParent(), tt, t);
                nr.fireOnTransition(stateMachine, t.getParent(), tt, t);
            }
        }
        // ExecutePhaseActions / OnEntry
        for (Iterator i = step.getEntryList().iterator(); i.hasNext();) {
            TransitionTarget tt = (TransitionTarget) i.next();
            OnEntry oe = tt.getOnEntry();
            try {
                for (Iterator onEntryIter = oe.getActions().iterator();
                        onEntryIter.hasNext();) {
                    ((Action) onEntryIter.next()).execute(evtDispatcher,
                        errRep, scInstance, appLog, internalEvents);
                }
            } catch (SCXMLExpressionException e) {
                errRep.onError(ErrorConstants.EXPRESSION_ERROR, e.getMessage(),
                        oe);
            }
            nr.fireOnEntry(tt, tt);
            nr.fireOnEntry(stateMachine, tt);
            TriggerEvent te = new TriggerEvent(tt.getId() + ".entry",
                    TriggerEvent.CHANGE_EVENT);
            internalEvents.add(te);
            // actions in initial transition (if any) and .done events
            if (tt instanceof State) {
                State ts = (State) tt;
                Initial ini = ts.getInitial();
                if (ts.isComposite() && ini != null) {
                    try {
                        for (Iterator iniIter = ini.getTransition().
                                getActions().iterator(); iniIter.hasNext();) {
                            ((Action) iniIter.next()).execute(evtDispatcher,
                                errRep, scInstance, appLog, internalEvents);
                        }
                    } catch (SCXMLExpressionException e) {
                        errRep.onError(ErrorConstants.EXPRESSION_ERROR,
                            e.getMessage(), ini);
                    }
                }
                if (ts.isFinal()) {
                    State parent = (State) ts.getParent();
                    String prefix = "";
                    if (parent != null) {
                        prefix = parent.getId();
                    }
                    te = new TriggerEvent(prefix + ".done",
                            TriggerEvent.CHANGE_EVENT);
                    internalEvents.add(te);
                    if (parent != null) {
                        scInstance.setDone(parent, true);
                    }
                    if (parent != null && parent.isRegion()) {
                        //3.4 we got a region, which is finalized
                        //let's check its siblings too
                        Parallel p = (Parallel) parent.getParent();
                        int finCount = 0;
                        int pCount = p.getChildren().size();
                        for (Iterator regions = p.getChildren().iterator();
                                regions.hasNext();) {
                            State reg = (State) regions.next();
                            if (scInstance.isDone(reg)) {
                                finCount++;
                            }
                        }
                        if (finCount == pCount) {
                            te = new TriggerEvent(p.getId() + ".done",
                                        TriggerEvent.CHANGE_EVENT);
                            internalEvents.add(te);
                            scInstance.setDone(p, true);
                            if (stateMachine.isLegacy()) {
                                te = new TriggerEvent(p.getParent().getId()
                                    + ".done", TriggerEvent.CHANGE_EVENT);
                                internalEvents.add(te);
                                //this is not in the specs, but is makes sense
                                scInstance.setDone(p.getParentState(), true);
                            }
                        }
                    }
                }
            }
        }
    }

    /**
     * @param stateMachine
     *            a SM to traverse [in]
     * @param step
     *            with current status and list of transitions to populate
     *            [inout]
     * @param errRep
     *            ErrorReporter callback [inout]
     */
    public void enumerateReachableTransitions(final SCXML stateMachine,
            final Step step, final ErrorReporter errRep) {
        // prevents adding the same transition multiple times
        Set transSet = new HashSet();
        // prevents visiting the same state multiple times
        Set stateSet = new HashSet(step.getBeforeStatus().getStates());
        // breath-first search to-do list
        LinkedList todoList = new LinkedList(stateSet);
        while (!todoList.isEmpty()) {
            TransitionTarget tt = (TransitionTarget) todoList.removeFirst();
            for (Iterator i = tt.getTransitionsList().iterator();
                    i.hasNext();) {
                Transition t = (Transition) i.next();
                if (!transSet.contains(t)) {
                    transSet.add(t);
                    step.getTransitList().add(t);
                }
            }
            TransitionTarget parent = tt.getParent();
            if (parent != null && !stateSet.contains(parent)) {
                stateSet.add(parent);
                todoList.addLast(parent);
            }
        }
        transSet.clear();
        stateSet.clear();
        todoList.clear();
    }

    /**
     * @param step
     *            [inout]
     * @param evtDispatcher
     *            The {@link EventDispatcher} [in]
     * @param errRep
     *            ErrorReporter callback [inout]
     * @param scInstance
     *            The state chart instance [in]
     * @throws ModelException
     *             in case there is a fatal SCXML object model problem.
     */
    public void filterTransitionsSet(final Step step,
            final EventDispatcher evtDispatcher,
            final ErrorReporter errRep, final SCInstance scInstance)
    throws ModelException {
        /*
         * - filter transition set by applying events
         * (step/beforeStatus/events + step/externalEvents) (local check)
         * - evaluating guard conditions for
         * each transition (local check) - transition precedence (bottom-up)
         * as defined by SCXML specs
         */
        Set allEvents = new HashSet(step.getBeforeStatus().getEvents().size()
            + step.getExternalEvents().size());
        allEvents.addAll(step.getBeforeStatus().getEvents());
        allEvents.addAll(step.getExternalEvents());
        // Finalize invokes, if applicable
        for (Iterator iter = scInstance.getInvokers().keySet().iterator();
                iter.hasNext();) {
            State s = (State) iter.next();
            if (finalizeMatch(s.getId(), allEvents)) {
                Finalize fn = s.getInvoke().getFinalize();
                if (fn != null) {
                    try {
                        for (Iterator fnIter = fn.getActions().iterator();
                                fnIter.hasNext();) {
                            ((Action) fnIter.next()).execute(evtDispatcher,
                                errRep, scInstance, appLog,
                                step.getAfterStatus().getEvents());
                        }
                    } catch (SCXMLExpressionException e) {
                        errRep.onError(ErrorConstants.EXPRESSION_ERROR,
                            e.getMessage(), fn);
                    }
                }
            }
        }
        //remove list (filtered-out list)
        List removeList = new LinkedList();
        //iterate over non-filtered transition set
        for (Iterator iter = step.getTransitList().iterator();
                iter.hasNext();) {
            Transition t = (Transition) iter.next();
            // event check
            String event = t.getEvent();
            if (!eventMatch(event, allEvents)) {
                // t has a non-empty event which is not triggered
                removeList.add(t);
                continue; //makes no sense to eval guard cond.
            }
            // guard condition check
            Boolean rslt;
            String expr = t.getCond();
            if (SCXMLHelper.isStringEmpty(expr)) {
                rslt = Boolean.TRUE;
            } else {
                try {
                    Context ctx = scInstance.getContext(t.getParent());
                    ctx.setLocal(NAMESPACES_KEY, t.getNamespaces());
                    rslt = scInstance.getEvaluator().evalCond(ctx,
                        t.getCond());
                    ctx.setLocal(NAMESPACES_KEY, null);
                } catch (SCXMLExpressionException e) {
                    rslt = Boolean.FALSE;
                    errRep.onError(ErrorConstants.EXPRESSION_ERROR, e
                            .getMessage(), t);
                }
            }
            if (!rslt.booleanValue()) {
                // guard condition has not passed
                removeList.add(t);
            }
        }
        // apply event + guard condition filter
        step.getTransitList().removeAll(removeList);
        // cleanup temporary structures
        allEvents.clear();
        removeList.clear();
        // optimization - global precedence potentially applies
        // only if there are multiple enabled transitions
        if (step.getTransitList().size() > 1) {
            // global transition precedence check
            Object[] trans = step.getTransitList().toArray();
            // non-determinism candidates
            Set nonDeterm = new LinkedHashSet();
            for (int i = 0; i < trans.length; i++) {
                Transition t = (Transition) trans[i];
                TransitionTarget tsrc = t.getParent();
                for (int j = i + 1; j < trans.length; j++) {
                    Transition t2 = (Transition) trans[j];
                    TransitionTarget t2src = t2.getParent();
                    if (SCXMLHelper.isDescendant(t2src, tsrc)) {
                        //t2 takes precedence over t
                        removeList.add(t);
                        break; //it makes no sense to waste cycles with t
                    } else if (SCXMLHelper.isDescendant(tsrc, t2src)) {
                        //t takes precendence over t2
                        removeList.add(t2);
                    } else {
                        //add both to the non-determinism candidates
                        nonDeterm.add(t);
                        nonDeterm.add(t2);
                    }
                }
            }
            // check if all non-deterministic situations have been resolved
            nonDeterm.removeAll(removeList);
            if (nonDeterm.size() > 0) {
                // if not, first one in each state / region (which is also
                // first in document order) wins
                Set regions = new HashSet();
                Iterator iter = nonDeterm.iterator();
                while (iter.hasNext()) {
                    Transition t = (Transition) iter.next();
                    TransitionTarget parent = t.getParent();
                    if (regions.contains(parent)) {
                        removeList.add(t);
                    } else {
                        regions.add(parent);
                    }
                }
            }
            // apply global and document order transition filter
            step.getTransitList().removeAll(removeList);
        }
    }

    /**
     * Populate the target set.
     * <ul>
     * <li>take targets of selected transitions</li>
     * <li>take exited regions into account and make sure every active
     * parallel region has all siblings active
     * [that is, explicitly visit or sibling regions in case of newly visited
     * (revisited) orthogonal states]</li>
     * </ul>
     * @param residual [in]
     * @param transitList [in]
     * @param errRep
     *            ErrorReporter callback [inout]
     * @return Set The target set
     */
    public Set seedTargetSet(final Set residual, final List transitList,
            final ErrorReporter errRep) {
        Set seedSet = new HashSet();
        Set regions = new HashSet();
        for (Iterator i = transitList.iterator(); i.hasNext();) {
            Transition t = (Transition) i.next();
            //iterate over transitions and add target states
            if (t.getTargets().size() > 0) {
                seedSet.addAll(t.getTargets());
            }
            //build a set of all entered regions
            List paths = t.getPaths();
            for (int j = 0; j < paths.size(); j++) {
                Path p = (Path) paths.get(j);
                if (p.isCrossRegion()) {
                    List regs = p.getRegionsEntered();
                    for (Iterator k = regs.iterator(); k.hasNext();) {
                        State region = (State) k.next();
                        regions.addAll(((Parallel) region.getParent()).
                            getChildren());
                    }
                }
            }
        }
        //check whether all active regions have their siblings active too
        Set allStates = new HashSet(residual);
        allStates.addAll(seedSet);
        allStates = SCXMLHelper.getAncestorClosure(allStates, null);
        regions.removeAll(allStates);
        //iterate over inactive regions and visit them implicitly using initial
        for (Iterator i = regions.iterator(); i.hasNext();) {
            State reg = (State) i.next();
            seedSet.add(reg);
        }
        return seedSet;
    }

    /**
     * @param states
     *            a set seeded in previous step [inout]
     * @param errRep
     *            ErrorReporter callback [inout]
     * @param scInstance
     *            The state chart instance [in]
     * @throws ModelException On illegal configuration
     * @see #seedTargetSet(Set, List, ErrorReporter)
     */
    public void determineTargetStates(final Set states,
            final ErrorReporter errRep, final SCInstance scInstance)
    throws ModelException {
        LinkedList wrkSet = new LinkedList(states);
        // clear the seed-set - will be populated by leaf states
        states.clear();
        while (!wrkSet.isEmpty()) {
            TransitionTarget tt = (TransitionTarget) wrkSet.removeFirst();
            if (tt instanceof State) {
                State st = (State) tt;
                //state can either have parallel or substates w. initial
                //or it is a leaf state
                // NOTE: Digester has to verify this precondition!
                if (st.isSimple()) {
                    states.add(st); //leaf
                } else if (st.isOrthogonal()) { //TODO: Remove else if in v1.0
                    wrkSet.addLast(st.getParallel()); //parallel
                } else {
                    // composite state
                    List initialStates = st.getInitial().getTransition().
                        getTargets();
                    wrkSet.addAll(initialStates);
                }
            } else if (tt instanceof Parallel) {
                Parallel prl = (Parallel) tt;
                for (Iterator i = prl.getChildren().iterator(); i.hasNext();) {
                    //fork
                    wrkSet.addLast(i.next());
                }
            } else if (tt instanceof History) {
                History h = (History) tt;
                if (scInstance.isEmpty(h)) {
                    wrkSet.addAll(h.getTransition().getRuntimeTargets());
                } else {
                    wrkSet.addAll(scInstance.getLastConfiguration(h));
                }
            } else {
                throw new ModelException("Unknown TransitionTarget subclass:"
                        + tt.getClass().getName());
            }
        }
    }

    /**
     * Go over the exit list and update history information for
     * relevant states.
     *
     * @param step
     *            [inout]
     * @param errRep
     *            ErrorReporter callback [inout]
     * @param scInstance
     *            The state chart instance [inout]
     */
    public void updateHistoryStates(final Step step,
            final ErrorReporter errRep, final SCInstance scInstance) {
        Set oldState = step.getBeforeStatus().getStates();
        for (Iterator i = step.getExitList().iterator(); i.hasNext();) {
            Object o = i.next();
            if (o instanceof State) {
                State s = (State) o;
                if (s.hasHistory()) {
                    Set shallow = null;
                    Set deep = null;
                    for (Iterator j = s.getHistory().iterator();
                            j.hasNext();) {
                        History h = (History) j.next();
                        if (h.isDeep()) {
                            if (deep == null) {
                                //calculate deep history for a given state once
                                deep = new HashSet();
                                Iterator k = oldState.iterator();
                                while (k.hasNext()) {
                                    State os = (State) k.next();
                                    if (SCXMLHelper.isDescendant(os, s)) {
                                        deep.add(os);
                                    }
                                }
                            }
                            scInstance.setLastConfiguration(h, deep);
                        } else {
                            if (shallow == null) {
                                //calculate shallow history for a given state
                                // once
                                shallow = new HashSet();
                                shallow.addAll(s.getChildren().values());
                                shallow.retainAll(SCXMLHelper
                                        .getAncestorClosure(oldState, null));
                            }
                            scInstance.setLastConfiguration(h, shallow);
                        }
                    }
                    shallow = null;
                    deep = null;
                }
            }
        }
    }

    /**
     * Follow the candidate transitions for this execution Step, and update the
     * lists of entered and exited states accordingly.
     *
     * @param step The current Step
     * @param errorReporter The ErrorReporter for the current environment
     * @param scInstance The state chart instance
     *
     * @throws ModelException
     *             in case there is a fatal SCXML object model problem.
     */
    public void followTransitions(final Step step,
            final ErrorReporter errorReporter, final SCInstance scInstance)
    throws ModelException {
        Set currentStates = step.getBeforeStatus().getStates();
        List transitions = step.getTransitList();
        // DetermineExitedStates (currentStates, transitList) -> exitedStates
        Set exitedStates = new HashSet();
        for (Iterator i = transitions.iterator(); i.hasNext();) {
            Transition t = (Transition) i.next();
            Set ext = SCXMLHelper.getStatesExited(t, currentStates);
            exitedStates.addAll(ext);
        }
        // compute residual states - these are preserved from the previous step
        Set residual = new HashSet(currentStates);
        residual.removeAll(exitedStates);
        // SeedTargetSet (residual, transitList) -> seedSet
        Set seedSet = seedTargetSet(residual, transitions, errorReporter);
        // DetermineTargetStates (initialTargetSet) -> targetSet
        Set targetSet = step.getAfterStatus().getStates();
        targetSet.addAll(seedSet); //copy to preserve seedSet
        determineTargetStates(targetSet, errorReporter, scInstance);
        // BuildOnEntryList (targetSet, seedSet) -> entryList
        Set entered = SCXMLHelper.getAncestorClosure(targetSet, seedSet);
        seedSet.clear();
        for (Iterator i = transitions.iterator(); i.hasNext();) {
            Transition t = (Transition) i.next();
            List paths = t.getPaths();
            for (int j = 0; j < paths.size(); j++) {
                Path p = (Path) paths.get(j);
                entered.addAll(p.getDownwardSegment());
            }
            // If target is a History pseudo state, remove from entered list
            List rtargets = t.getRuntimeTargets();
            for (int j = 0; j < rtargets.size(); j++) {
                TransitionTarget tt = (TransitionTarget) rtargets.get(j);
                if (tt instanceof History) {
                    entered.remove(tt);
                }
            }
        }
        // Check whether the computed state config is legal
        targetSet.addAll(residual);
        residual.clear();
        if (!SCXMLHelper.isLegalConfig(targetSet, errorReporter)) {
            throw new ModelException("Illegal state machine configuration!");
        }
        // sort onEntry and onExit according state hierarchy
        Object[] oex = exitedStates.toArray();
        exitedStates.clear();
        Object[] oen = entered.toArray();
        entered.clear();
        Arrays.sort(oex, getTTComparator());
        Arrays.sort(oen, getTTComparator());
        step.getExitList().addAll(Arrays.asList(oex));
        // we need to impose reverse order for the onEntry list
        List entering = Arrays.asList(oen);
        Collections.reverse(entering);
        step.getEntryList().addAll(entering);
        // reset 'done' flag
        for (Iterator reset = entering.iterator(); reset.hasNext();) {
            Object o = reset.next();
            if (o instanceof State) {
                scInstance.setDone((State) o, false);
            }
        }
    }
    /**
     * Process any existing invokes, includes forwarding external events,
     * and executing any finalize handlers.
     *
     * @param events
     *            The events to be forwarded
     * @param errRep
     *            ErrorReporter callback
     * @param scInstance
     *            The state chart instance
     * @throws ModelException
     *             in case there is a fatal SCXML object model problem.
     */
    public void processInvokes(final TriggerEvent[] events,
            final ErrorReporter errRep, final SCInstance scInstance)
    throws ModelException {
        Set allEvents = new HashSet();
        allEvents.addAll(Arrays.asList(events));
        for (Iterator invokeIter = scInstance.getInvokers().entrySet().
                iterator(); invokeIter.hasNext();) {
            Map.Entry iEntry = (Map.Entry) invokeIter.next();
            String parentId = ((TransitionTarget) iEntry.getKey()).getId();
            if (!finalizeMatch(parentId, allEvents)) { // prevent cycles
                Invoker inv = (Invoker) iEntry.getValue();
                try {
                    inv.parentEvents(events);
                } catch (InvokerException ie) {
                    appLog.error(ie.getMessage(), ie);
                    throw new ModelException(ie.getMessage(), ie.getCause());
                }
            }
        }
    }

    /**
     * Initiate any new invokes.
     *
     * @param step
     *            The current Step
     * @param errRep
     *            ErrorReporter callback
     * @param scInstance
     *            The state chart instance
     */
    public void initiateInvokes(final Step step, final ErrorReporter errRep,
            final SCInstance scInstance) {
        Evaluator eval = scInstance.getEvaluator();
        Collection internalEvents = step.getAfterStatus().getEvents();
        for (Iterator iter = step.getAfterStatus().getStates().iterator();
                iter.hasNext();) {
            State s = (State) iter.next();
            Context ctx = scInstance.getContext(s);
            Invoke i = s.getInvoke();
            if (i != null && scInstance.getInvoker(s) == null) {
                String src = i.getSrc();
                if (src == null) {
                    String srcexpr = i.getSrcexpr();
                    Object srcObj = null;
                    try {
                        ctx.setLocal(NAMESPACES_KEY, i.getNamespaces());
                        srcObj = eval.eval(ctx, srcexpr);
                        ctx.setLocal(NAMESPACES_KEY, null);
                        src = String.valueOf(srcObj);
                    } catch (SCXMLExpressionException see) {
                        errRep.onError(ErrorConstants.EXPRESSION_ERROR,
                            see.getMessage(), i);
                    }
                }
                String source = src;
                PathResolver pr = i.getPathResolver();
                if (pr != null) {
                    source = i.getPathResolver().resolvePath(src);
                }
                String ttype = i.getTargettype();
                Invoker inv = null;
                try {
                    inv = scInstance.newInvoker(ttype);
                } catch (InvokerException ie) {
                    TriggerEvent te = new TriggerEvent(s.getId()
                        + ".invoke.failed", TriggerEvent.ERROR_EVENT);
                    internalEvents.add(te);
                    continue;
                }
                inv.setParentStateId(s.getId());
                inv.setSCInstance(scInstance);
                List params = i.params();
                Map args = new HashMap();
                for (Iterator pIter = params.iterator(); pIter.hasNext();) {
                    Param p = (Param) pIter.next();
                    String argExpr = p.getExpr();
                    Object argValue = null;
                    ctx.setLocal(NAMESPACES_KEY, p.getNamespaces());
                    // Do we have an "expr" attribute?
                    if (argExpr != null && argExpr.trim().length() > 0) {
                        // Yes, evaluate and store as parameter value
                        try {
                            argValue = eval.eval(ctx, argExpr);
                        } catch (SCXMLExpressionException see) {
                            errRep.onError(ErrorConstants.EXPRESSION_ERROR,
                                see.getMessage(), i);
                        }
                    } else {
                        // No. Does value of "name" attribute refer to a valid
                        // location in the data model?
                        try {
                            argValue = eval.evalLocation(ctx, p.getName());
                            if (argValue == null) {
                                // Generate error, 4.3.1 in WD-scxml-20080516
                                TriggerEvent te = new TriggerEvent(s.getId()
                                    + ERR_ILLEGAL_ALLOC,
                                    TriggerEvent.ERROR_EVENT);
                                internalEvents.add(te);
                            }
                        } catch (SCXMLExpressionException see) {
                            errRep.onError(ErrorConstants.EXPRESSION_ERROR,
                                see.getMessage(), i);
                        }
                    }
                    ctx.setLocal(NAMESPACES_KEY, null);
                    args.put(p.getName(), argValue);
                }
                try {
                    inv.invoke(source, args);
                } catch (InvokerException ie) {
                    TriggerEvent te = new TriggerEvent(s.getId()
                        + ".invoke.failed", TriggerEvent.ERROR_EVENT);
                    internalEvents.add(te);
                    continue;
                }
                scInstance.setInvoker(s, inv);
            }
        }
    }

    /**
     * Implements prefix match, that is, if, for example,
     * &quot;mouse.click&quot; is a member of eventOccurrences and a
     * transition is triggered by &quot;mouse&quot;, the method returns true.
     *
     * @param transEvent
     *            a trigger event of a transition
     * @param eventOccurrences
     *            current events
     * @return true/false
     */
    protected boolean eventMatch(final String transEvent,
            final Set eventOccurrences) {
        if (SCXMLHelper.isStringEmpty(transEvent)) { // Eventless transition
            return true;
        } else {
            String trimTransEvent = transEvent.trim();
            Iterator i = eventOccurrences.iterator();
            while (i.hasNext()) {
                TriggerEvent te = (TriggerEvent) i.next();
                String event = te.getName();
                if (event == null) {
                    continue; // Unnamed events
                }
                String trimEvent = event.trim();
                if (trimEvent.equals(trimTransEvent)) {
                    return true; // Match
                } else if (te.getType() != TriggerEvent.CHANGE_EVENT
                        && trimTransEvent.equals("*")) {
                    return true; // Wildcard, skip gen'ed ones like .done etc.
                } else if (trimTransEvent.endsWith(".*")
                        && trimEvent.startsWith(trimTransEvent.substring(0,
                                trimTransEvent.length() - 1))) {
                    return true; // Prefixed wildcard
                }
            }
            return false;
        }
    }

    /**
     * Implements event prefix match to ascertain &lt;finalize&gt; execution.
     *
     * @param parentStateId
     *            the ID of the parent state of the &lt;invoke&gt; holding
     *            the &lt;finalize&gt;
     * @param eventOccurrences
     *            current events
     * @return true/false
     */
    protected boolean finalizeMatch(final String parentStateId,
            final Set eventOccurrences) {
        String prefix = parentStateId + ".invoke."; // invoke prefix
        Iterator i = eventOccurrences.iterator();
        while (i.hasNext()) {
            String evt = ((TriggerEvent) i.next()).getName();
            if (evt == null) {
                continue; // Unnamed events
            } else if (evt.trim().startsWith(prefix)) {
                return true;
            }
        }
        return false;
    }

    /**
     * TransitionTargetComparator factory method.
     * @return Comparator The TransitionTarget comparator
     */
    protected Comparator getTTComparator() {
        return targetComparator;
    }

    /**
     * Set the log used by this <code>SCXMLSemantics</code> instance.
     *
     * @param log The new log.
     */
    protected void setLog(final Log log) {
        this.appLog = log;
    }

    /**
     * Get the log used by this <code>SCXMLSemantics</code> instance.
     *
     * @return Log The log being used.
     */
    protected Log getLog() {
        return appLog;
    }

}

