    001    /*
    002     * Licensed to the Apache Software Foundation (ASF) under one or more
    003     * contributor license agreements.  See the NOTICE file distributed with
    004     * this work for additional information regarding copyright ownership.
    005     * The ASF licenses this file to You under the Apache License, Version 2.0
    006     * (the "License"); you may not use this file except in compliance with
    007     * the License.  You may obtain a copy of the License at
    008     *
    009     *     http://www.apache.org/licenses/LICENSE-2.0
    010     *
    011     * Unless required by applicable law or agreed to in writing, software
    012     * distributed under the License is distributed on an "AS IS" BASIS,
    013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014     * See the License for the specific language governing permissions and
    015     * limitations under the License.
    016     */
    017    package org.apache.commons.scxml.semantics;
    018
    019    import java.io.Serializable;
    020    import java.util.Arrays;
    021    import java.util.Collection;
    022    import java.util.Collections;
    023    import java.util.Comparator;
    024    import java.util.HashMap;
    025    import java.util.HashSet;
    026    import java.util.Iterator;
    027    import java.util.LinkedHashSet;
    028    import java.util.LinkedList;
    029    import java.util.List;
    030    import java.util.Map;
    031    import java.util.Set;
    032
    033    import org.apache.commons.logging.Log;
    034    import org.apache.commons.logging.LogFactory;
    035    import org.apache.commons.scxml.Context;
    036    import org.apache.commons.scxml.ErrorReporter;
    037    import org.apache.commons.scxml.Evaluator;
    038    import org.apache.commons.scxml.EventDispatcher;
    039    import org.apache.commons.scxml.NotificationRegistry;
    040    import org.apache.commons.scxml.PathResolver;
    041    import org.apache.commons.scxml.SCInstance;
    042    import org.apache.commons.scxml.SCXMLExpressionException;
    043    import org.apache.commons.scxml.SCXMLHelper;
    044    import org.apache.commons.scxml.SCXMLSemantics;
    045    import org.apache.commons.scxml.Step;
    046    import org.apache.commons.scxml.TriggerEvent;
    047    import org.apache.commons.scxml.invoke.Invoker;
    048    import org.apache.commons.scxml.invoke.InvokerException;
    049    import org.apache.commons.scxml.model.Action;
    050    import org.apache.commons.scxml.model.Finalize;
    051    import org.apache.commons.scxml.model.History;
    052    import org.apache.commons.scxml.model.Initial;
    053    import org.apache.commons.scxml.model.Invoke;
    054    import org.apache.commons.scxml.model.ModelException;
    055    import org.apache.commons.scxml.model.OnEntry;
    056    import org.apache.commons.scxml.model.OnExit;
    057    import org.apache.commons.scxml.model.Parallel;
    058    import org.apache.commons.scxml.model.Param;
    059    import org.apache.commons.scxml.model.Path;
    060    import org.apache.commons.scxml.model.SCXML;
    061    import org.apache.commons.scxml.model.State;
    062    import org.apache.commons.scxml.model.Transition;
    063    import org.apache.commons.scxml.model.TransitionTarget;
    064
    065    /**
    066     * <p>This class encapsulates a particular SCXML semantics, that is, a
    067     * particular semantic interpretation of Harel Statecharts, which aligns
    068     * mostly with W3C SCXML July 5 public draft (that is, UML 1.5). However,
    069     * certain aspects are taken from STATEMATE.</p>
    070     *
    071     * <p>Specific semantics can be created by subclassing this class.</p>
    072     */
    073    public class SCXMLSemanticsImpl implements SCXMLSemantics, Serializable {
    074
    075        /**
    076         * Serial version UID.
    077         */
    078        private static final long serialVersionUID = 1L;
    079
    080        /**
    081         * SCXML Logger for the application.
    082         */
    083        private Log appLog = LogFactory.getLog(SCXMLSemantics.class);
    084
    085        /**
    086         * The TransitionTarget comparator.
    087         */
    088        private TransitionTargetComparator targetComparator =
    089            new TransitionTargetComparator();
    090
    091        /**
    092         * Current document namespaces are saved under this key in the parent
    093         * state's context.
    094         */
    095        private static final String NAMESPACES_KEY = "_ALL_NAMESPACES";
    096
    097        /**
    098         * Suffix for error event that are triggered in reaction to invalid data
    099         * model locations.
    100         */
    101        private static final String ERR_ILLEGAL_ALLOC = ".error.illegalalloc";
    102
    103        /**
    104         * @param input
    105         *            SCXML state machine
    106         * @return normalized SCXML state machine, pseudo states are removed, etc.
    107         * @param errRep
    108         *            ErrorReporter callback
    109         */
    110        public SCXML normalizeStateMachine(final SCXML input,
    111                final ErrorReporter errRep) {
    112            //it is a no-op for now
    113            return input;
    114        }
    115
    116        /**
    117         * @param input
    118         *            SCXML state machine [in]
    119         * @param targets
    120         *            a set of initial targets to populate [out]
    121         * @param entryList
    122         *            a list of States and Parallels to enter [out]
    123         * @param errRep
    124         *            ErrorReporter callback [inout]
    125         * @param scInstance
    126         *            The state chart instance [in]
    127         * @throws ModelException
    128         *             in case there is a fatal SCXML object model problem.
    129         */
    130        public void determineInitialStates(final SCXML input, final Set targets,
    131                final List entryList, final ErrorReporter errRep,
    132                final SCInstance scInstance)
    133                throws ModelException {
    134            TransitionTarget tmp = input.getInitialTarget();
    135            if (tmp == null) {
    136                errRep.onError(ErrorConstants.NO_INITIAL,
    137                        "SCXML initialstate is missing!", input);
    138            } else {
    139                targets.add(tmp);
    140                determineTargetStates(targets, errRep, scInstance);
    141                //set of ALL entered states (even if initialState is a jump-over)
    142                Set onEntry = SCXMLHelper.getAncestorClosure(targets, null);
    143                // sort onEntry according state hierarchy
    144                Object[] oen = onEntry.toArray();
    145                onEntry.clear();
    146                Arrays.sort(oen, getTTComparator());
    147                // we need to impose reverse order for the onEntry list
    148                List entering = Arrays.asList(oen);
    149                Collections.reverse(entering);
    150                entryList.addAll(entering);
    151
    152            }
    153        }
    154
    155        /**
    156         * Executes all OnExit/Transition/OnEntry transitional actions.
    157         *
    158         * @param step
    159         *            provides EntryList, TransitList, ExitList gets
    160         *            updated its AfterStatus/Events
    161         * @param stateMachine
    162         *            state machine - SCXML instance
    163         * @param evtDispatcher
    164         *            the event dispatcher - EventDispatcher instance
    165         * @param errRep
    166         *            error reporter
    167         * @param scInstance
    168         *            The state chart instance
    169         * @throws ModelException
    170         *             in case there is a fatal SCXML object model problem.
    171         */
    172        public void executeActions(final Step step, final SCXML stateMachine,
    173                final EventDispatcher evtDispatcher,
    174                final ErrorReporter errRep, final SCInstance scInstance)
    175        throws ModelException {
    176            NotificationRegistry nr = scInstance.getNotificationRegistry();
    177            Collection internalEvents = step.getAfterStatus().getEvents();
    178            Map invokers = scInstance.getInvokers();
    179            // ExecutePhaseActions / OnExit
    180            for (Iterator i = step.getExitList().iterator(); i.hasNext();) {
    181                TransitionTarget tt = (TransitionTarget) i.next();
    182                OnExit oe = tt.getOnExit();
    183                try {
    184                    for (Iterator onExitIter = oe.getActions().iterator();
    185                            onExitIter.hasNext();) {
    186                        ((Action) onExitIter.next()).execute(evtDispatcher,
    187                            errRep, scInstance, appLog, internalEvents);
    188                    }
    189                } catch (SCXMLExpressionException e) {
    190                    errRep.onError(ErrorConstants.EXPRESSION_ERROR, e.getMessage(),
    191                            oe);
    192                }
    193                // check if invoke is active in this state
    194                if (invokers.containsKey(tt)) {
    195                    Invoker toCancel = (Invoker) invokers.get(tt);
    196                    try {
    197                        toCancel.cancel();
    198                    } catch (InvokerException ie) {
    199                        TriggerEvent te = new TriggerEvent(tt.getId()
    200                            + ".invoke.cancel.failed", TriggerEvent.ERROR_EVENT);
    201                        internalEvents.add(te);
    202                    }
    203                    // done here, don't wait for cancel response
    204                    invokers.remove(tt);
    205                }
    206                nr.fireOnExit(tt, tt);
    207                nr.fireOnExit(stateMachine, tt);
    208                TriggerEvent te = new TriggerEvent(tt.getId() + ".exit",
    209                        TriggerEvent.CHANGE_EVENT);
    210                internalEvents.add(te);
    211            }
    212            // ExecutePhaseActions / Transitions
    213            for (Iterator i = step.getTransitList().iterator(); i.hasNext();) {
    214                Transition t = (Transition) i.next();
    215                try {
    216                    for (Iterator transitIter = t.getActions().iterator();
    217                            transitIter.hasNext();) {
    218                        ((Action) transitIter.next()).execute(evtDispatcher,
    219                            errRep, scInstance, appLog, internalEvents);
    220                    }
    221                } catch (SCXMLExpressionException e) {
    222                    errRep.onError(ErrorConstants.EXPRESSION_ERROR,
    223                        e.getMessage(), t);
    224                }
    225                List rtargets = t.getRuntimeTargets();
    226                for (int j = 0; j < rtargets.size(); j++) {
    227                    TransitionTarget tt = (TransitionTarget) rtargets.get(j);
    228                    nr.fireOnTransition(t, t.getParent(), tt, t);
    229                    nr.fireOnTransition(stateMachine, t.getParent(), tt, t);
    230                }
    231            }
    232            // ExecutePhaseActions / OnEntry
    233            for (Iterator i = step.getEntryList().iterator(); i.hasNext();) {
    234                TransitionTarget tt = (TransitionTarget) i.next();
    235                OnEntry oe = tt.getOnEntry();
    236                try {
    237                    for (Iterator onEntryIter = oe.getActions().iterator();
    238                            onEntryIter.hasNext();) {
    239                        ((Action) onEntryIter.next()).execute(evtDispatcher,
    240                            errRep, scInstance, appLog, internalEvents);
    241                    }
    242                } catch (SCXMLExpressionException e) {
    243                    errRep.onError(ErrorConstants.EXPRESSION_ERROR, e.getMessage(),
    244                            oe);
    245                }
    246                nr.fireOnEntry(tt, tt);
    247                nr.fireOnEntry(stateMachine, tt);
    248                TriggerEvent te = new TriggerEvent(tt.getId() + ".entry",
    249                        TriggerEvent.CHANGE_EVENT);
    250                internalEvents.add(te);
    251                // actions in initial transition (if any) and .done events
    252                if (tt instanceof State) {
    253                    State ts = (State) tt;
    254                    Initial ini = ts.getInitial();
    255                    if (ts.isComposite() && ini != null) {
    256                        try {
    257                            for (Iterator iniIter = ini.getTransition().
    258                                    getActions().iterator(); iniIter.hasNext();) {
    259                                ((Action) iniIter.next()).execute(evtDispatcher,
    260                                    errRep, scInstance, appLog, internalEvents);
    261                            }
    262                        } catch (SCXMLExpressionException e) {
    263                            errRep.onError(ErrorConstants.EXPRESSION_ERROR,
    264                                e.getMessage(), ini);
    265                        }
    266                    }
    267                    if (ts.isFinal()) {
    268                        State parent = (State) ts.getParent();
    269                        String prefix = "";
    270                        if (parent != null) {
    271                            prefix = parent.getId();
    272                        }
    273                        te = new TriggerEvent(prefix + ".done",
    274                                TriggerEvent.CHANGE_EVENT);
    275                        internalEvents.add(te);
    276                        if (parent != null) {
    277                            scInstance.setDone(parent, true);
    278                        }
    279                        if (parent != null && parent.isRegion()) {
    280                            //3.4 we got a region, which is finalized
    281                            //let's check its siblings too
    282                            Parallel p = (Parallel) parent.getParent();
    283                            int finCount = 0;
    284                            int pCount = p.getChildren().size();
    285                            for (Iterator regions = p.getChildren().iterator();
    286                                    regions.hasNext();) {
    287                                State reg = (State) regions.next();
    288                                if (scInstance.isDone(reg)) {
    289                                    finCount++;
    290                                }
    291                            }
    292                            if (finCount == pCount) {
    293                                te = new TriggerEvent(p.getId() + ".done",
    294                                            TriggerEvent.CHANGE_EVENT);
    295                                internalEvents.add(te);
    296                                scInstance.setDone(p, true);
    297                                if (stateMachine.isLegacy()) {
    298                                    te = new TriggerEvent(p.getParent().getId()
    299                                        + ".done", TriggerEvent.CHANGE_EVENT);
    300                                    internalEvents.add(te);
    301                                    //this is not in the specs, but is makes sense
    302                                    scInstance.setDone(p.getParentState(), true);
    303                                }
    304                            }
    305                        }
    306                    }
    307                }
    308            }
    309        }
    310
    311        /**
    312         * @param stateMachine
    313         *            a SM to traverse [in]
    314         * @param step
    315         *            with current status and list of transitions to populate
    316         *            [inout]
    317         * @param errRep
    318         *            ErrorReporter callback [inout]
    319         */
    320        public void enumerateReachableTransitions(final SCXML stateMachine,
    321                final Step step, final ErrorReporter errRep) {
    322            // prevents adding the same transition multiple times
    323            Set transSet = new HashSet();
    324            // prevents visiting the same state multiple times
    325            Set stateSet = new HashSet(step.getBeforeStatus().getStates());
    326            // breath-first search to-do list
    327            LinkedList todoList = new LinkedList(stateSet);
    328            while (!todoList.isEmpty()) {
    329                TransitionTarget tt = (TransitionTarget) todoList.removeFirst();
    330                for (Iterator i = tt.getTransitionsList().iterator();
    331                        i.hasNext();) {
    332                    Transition t = (Transition) i.next();
    333                    if (!transSet.contains(t)) {
    334                        transSet.add(t);
    335                        step.getTransitList().add(t);
    336                    }
    337                }
    338                TransitionTarget parent = tt.getParent();
    339                if (parent != null && !stateSet.contains(parent)) {
    340                    stateSet.add(parent);
    341                    todoList.addLast(parent);
    342                }
    343            }
    344            transSet.clear();
    345            stateSet.clear();
    346            todoList.clear();
    347        }
    348
    349        /**
    350         * @param step
    351         *            [inout]
    352         * @param evtDispatcher
    353         *            The {@link EventDispatcher} [in]
    354         * @param errRep
    355         *            ErrorReporter callback [inout]
    356         * @param scInstance
    357         *            The state chart instance [in]
    358         * @throws ModelException
    359         *             in case there is a fatal SCXML object model problem.
    360         */
    361        public void filterTransitionsSet(final Step step,
    362                final EventDispatcher evtDispatcher,
    363                final ErrorReporter errRep, final SCInstance scInstance)
    364        throws ModelException {
    365            /*
    366             * - filter transition set by applying events
    367             * (step/beforeStatus/events + step/externalEvents) (local check)
    368             * - evaluating guard conditions for
    369             * each transition (local check) - transition precedence (bottom-up)
    370             * as defined by SCXML specs
    371             */
    372            Set allEvents = new HashSet(step.getBeforeStatus().getEvents().size()
    373                + step.getExternalEvents().size());
    374            allEvents.addAll(step.getBeforeStatus().getEvents());
    375            allEvents.addAll(step.getExternalEvents());
    376            // Finalize invokes, if applicable
    377            for (Iterator iter = scInstance.getInvokers().keySet().iterator();
    378                    iter.hasNext();) {
    379                State s = (State) iter.next();
    380                if (finalizeMatch(s.getId(), allEvents)) {
    381                    Finalize fn = s.getInvoke().getFinalize();
    382                    if (fn != null) {
    383                        try {
    384                            for (Iterator fnIter = fn.getActions().iterator();
    385                                    fnIter.hasNext();) {
    386                                ((Action) fnIter.next()).execute(evtDispatcher,
    387                                    errRep, scInstance, appLog,
    388                                    step.getAfterStatus().getEvents());
    389                            }
    390                        } catch (SCXMLExpressionException e) {
    391                            errRep.onError(ErrorConstants.EXPRESSION_ERROR,
    392                                e.getMessage(), fn);
    393                        }
    394                    }
    395                }
    396            }
    397            //remove list (filtered-out list)
    398            List removeList = new LinkedList();
    399            //iterate over non-filtered transition set
    400            for (Iterator iter = step.getTransitList().iterator();
    401                    iter.hasNext();) {
    402                Transition t = (Transition) iter.next();
    403                // event check
    404                String event = t.getEvent();
    405                if (!eventMatch(event, allEvents)) {
    406                    // t has a non-empty event which is not triggered
    407                    removeList.add(t);
    408                    continue; //makes no sense to eval guard cond.
    409                }
    410                // guard condition check
    411                Boolean rslt;
    412                String expr = t.getCond();
    413                if (SCXMLHelper.isStringEmpty(expr)) {
    414                    rslt = Boolean.TRUE;
    415                } else {
    416                    try {
    417                        Context ctx = scInstance.getContext(t.getParent());
    418                        ctx.setLocal(NAMESPACES_KEY, t.getNamespaces());
    419                        rslt = scInstance.getEvaluator().evalCond(ctx,
    420                            t.getCond());
    421                        ctx.setLocal(NAMESPACES_KEY, null);
    422                    } catch (SCXMLExpressionException e) {
    423                        rslt = Boolean.FALSE;
    424                        errRep.onError(ErrorConstants.EXPRESSION_ERROR, e
    425                                .getMessage(), t);
    426                    }
    427                }
    428                if (!rslt.booleanValue()) {
    429                    // guard condition has not passed
    430                    removeList.add(t);
    431                }
    432            }
    433            // apply event + guard condition filter
    434            step.getTransitList().removeAll(removeList);
    435            // cleanup temporary structures
    436            allEvents.clear();
    437            removeList.clear();
    438            // optimization - global precedence potentially applies
    439            // only if there are multiple enabled transitions
    440            if (step.getTransitList().size() > 1) {
    441                // global transition precedence check
    442                Object[] trans = step.getTransitList().toArray();
    443                // non-determinism candidates
    444                Set nonDeterm = new LinkedHashSet();
    445                for (int i = 0; i < trans.length; i++) {
    446                    Transition t = (Transition) trans[i];
    447                    TransitionTarget tsrc = t.getParent();
    448                    for (int j = i + 1; j < trans.length; j++) {
    449                        Transition t2 = (Transition) trans[j];
    450                        TransitionTarget t2src = t2.getParent();
    451                        if (SCXMLHelper.isDescendant(t2src, tsrc)) {
    452                            //t2 takes precedence over t
    453                            removeList.add(t);
    454                            break; //it makes no sense to waste cycles with t
    455                        } else if (SCXMLHelper.isDescendant(tsrc, t2src)) {
    456                            //t takes precendence over t2
    457                            removeList.add(t2);
    458                        } else {
    459                            //add both to the non-determinism candidates
    460                            nonDeterm.add(t);
    461                            nonDeterm.add(t2);
    462                        }
    463                    }
    464                }
    465                // check if all non-deterministic situations have been resolved
    466                nonDeterm.removeAll(removeList);
    467                if (nonDeterm.size() > 0) {
    468                    // if not, first one in each state / region (which is also
    469                    // first in document order) wins
    470                    Set regions = new HashSet();
    471                    Iterator iter = nonDeterm.iterator();
    472                    while (iter.hasNext()) {
    473                        Transition t = (Transition) iter.next();
    474                        TransitionTarget parent = t.getParent();
    475                        if (regions.contains(parent)) {
    476                            removeList.add(t);
    477                        } else {
    478                            regions.add(parent);
    479                        }
    480                    }
    481                }
    482                // apply global and document order transition filter
    483                step.getTransitList().removeAll(removeList);
    484            }
    485        }
    486
    487        /**
    488         * Populate the target set.
    489         * <ul>
    490         * <li>take targets of selected transitions</li>
    491         * <li>take exited regions into account and make sure every active
    492         * parallel region has all siblings active
    493         * [that is, explicitly visit or sibling regions in case of newly visited
    494         * (revisited) orthogonal states]</li>
    495         * </ul>
    496         * @param residual [in]
    497         * @param transitList [in]
    498         * @param errRep
    499         *            ErrorReporter callback [inout]
    500         * @return Set The target set
    501         */
    502        public Set seedTargetSet(final Set residual, final List transitList,
    503                final ErrorReporter errRep) {
    504            Set seedSet = new HashSet();
    505            Set regions = new HashSet();
    506            for (Iterator i = transitList.iterator(); i.hasNext();) {
    507                Transition t = (Transition) i.next();
    508                //iterate over transitions and add target states
    509                if (t.getTargets().size() > 0) {
    510                    seedSet.addAll(t.getTargets());
    511                }
    512                //build a set of all entered regions
    513                List paths = t.getPaths();
    514                for (int j = 0; j < paths.size(); j++) {
    515                    Path p = (Path) paths.get(j);
    516                    if (p.isCrossRegion()) {
    517                        List regs = p.getRegionsEntered();
    518                        for (Iterator k = regs.iterator(); k.hasNext();) {
    519                            State region = (State) k.next();
    520                            regions.addAll(((Parallel) region.getParent()).
    521                                getChildren());
    522                        }
    523                    }
    524                }
    525            }
    526            //check whether all active regions have their siblings active too
    527            Set allStates = new HashSet(residual);
    528            allStates.addAll(seedSet);
    529            allStates = SCXMLHelper.getAncestorClosure(allStates, null);
    530            regions.removeAll(allStates);
    531            //iterate over inactive regions and visit them implicitly using initial
    532            for (Iterator i = regions.iterator(); i.hasNext();) {
    533                State reg = (State) i.next();
    534                seedSet.add(reg);
    535            }
    536            return seedSet;
    537        }
    538
    539        /**
    540         * @param states
    541         *            a set seeded in previous step [inout]
    542         * @param errRep
    543         *            ErrorReporter callback [inout]
    544         * @param scInstance
    545         *            The state chart instance [in]
    546         * @throws ModelException On illegal configuration
    547         * @see #seedTargetSet(Set, List, ErrorReporter)
    548         */
    549        public void determineTargetStates(final Set states,
    550                final ErrorReporter errRep, final SCInstance scInstance)
    551        throws ModelException {
    552            LinkedList wrkSet = new LinkedList(states);
    553            // clear the seed-set - will be populated by leaf states
    554            states.clear();
    555            while (!wrkSet.isEmpty()) {
    556                TransitionTarget tt = (TransitionTarget) wrkSet.removeFirst();
    557                if (tt instanceof State) {
    558                    State st = (State) tt;
    559                    //state can either have parallel or substates w. initial
    560                    //or it is a leaf state
    561                    // NOTE: Digester has to verify this precondition!
    562                    if (st.isSimple()) {
    563                        states.add(st); //leaf
    564                    } else if (st.isOrthogonal()) { //TODO: Remove else if in v1.0
    565                        wrkSet.addLast(st.getParallel()); //parallel
    566                    } else {
    567                        // composite state
    568                        List initialStates = st.getInitial().getTransition().
    569                            getTargets();
    570                        wrkSet.addAll(initialStates);
    571                    }
    572                } else if (tt instanceof Parallel) {
    573                    Parallel prl = (Parallel) tt;
    574                    for (Iterator i = prl.getChildren().iterator(); i.hasNext();) {
    575                        //fork
    576                        wrkSet.addLast(i.next());
    577                    }
    578                } else if (tt instanceof History) {
    579                    History h = (History) tt;
    580                    if (scInstance.isEmpty(h)) {
    581                        wrkSet.addAll(h.getTransition().getRuntimeTargets());
    582                    } else {
    583                        wrkSet.addAll(scInstance.getLastConfiguration(h));
    584                    }
    585                } else {
    586                    throw new ModelException("Unknown TransitionTarget subclass:"
    587                            + tt.getClass().getName());
    588                }
    589            }
    590        }
    591
    592        /**
    593         * Go over the exit list and update history information for
    594         * relevant states.
    595         *
    596         * @param step
    597         *            [inout]
    598         * @param errRep
    599         *            ErrorReporter callback [inout]
    600         * @param scInstance
    601         *            The state chart instance [inout]
    602         */
    603        public void updateHistoryStates(final Step step,
    604                final ErrorReporter errRep, final SCInstance scInstance) {
    605            Set oldState = step.getBeforeStatus().getStates();
    606            for (Iterator i = step.getExitList().iterator(); i.hasNext();) {
    607                Object o = i.next();
    608                if (o instanceof State) {
    609                    State s = (State) o;
    610                    if (s.hasHistory()) {
    611                        Set shallow = null;
    612                        Set deep = null;
    613                        for (Iterator j = s.getHistory().iterator();
    614                                j.hasNext();) {
    615                            History h = (History) j.next();
    616                            if (h.isDeep()) {
    617                                if (deep == null) {
    618                                    //calculate deep history for a given state once
    619                                    deep = new HashSet();
    620                                    Iterator k = oldState.iterator();
    621                                    while (k.hasNext()) {
    622                                        State os = (State) k.next();
    623                                        if (SCXMLHelper.isDescendant(os, s)) {
    624                                            deep.add(os);
    625                                        }
    626                                    }
    627                                }
    628                                scInstance.setLastConfiguration(h, deep);
    629                            } else {
    630                                if (shallow == null) {
    631                                    //calculate shallow history for a given state
    632                                    // once
    633                                    shallow = new HashSet();
    634                                    shallow.addAll(s.getChildren().values());
    635                                    shallow.retainAll(SCXMLHelper
    636                                            .getAncestorClosure(oldState, null));
    637                                }
    638                                scInstance.setLastConfiguration(h, shallow);
    639                            }
    640                        }
    641                        shallow = null;
    642                        deep = null;
    643                    }
    644                }
    645            }
    646        }
    647
    648        /**
    649         * Follow the candidate transitions for this execution Step, and update the
    650         * lists of entered and exited states accordingly.
    651         *
    652         * @param step The current Step
    653         * @param errorReporter The ErrorReporter for the current environment
    654         * @param scInstance The state chart instance
    655         *
    656         * @throws ModelException
    657         *             in case there is a fatal SCXML object model problem.
    658         */
    659        public void followTransitions(final Step step,
    660                final ErrorReporter errorReporter, final SCInstance scInstance)
    661        throws ModelException {
    662            Set currentStates = step.getBeforeStatus().getStates();
    663            List transitions = step.getTransitList();
    664            // DetermineExitedStates (currentStates, transitList) -> exitedStates
    665            Set exitedStates = new HashSet();
    666            for (Iterator i = transitions.iterator(); i.hasNext();) {
    667                Transition t = (Transition) i.next();
    668                Set ext = SCXMLHelper.getStatesExited(t, currentStates);
    669                exitedStates.addAll(ext);
    670            }
    671            // compute residual states - these are preserved from the previous step
    672            Set residual = new HashSet(currentStates);
    673            residual.removeAll(exitedStates);
    674            // SeedTargetSet (residual, transitList) -> seedSet
    675            Set seedSet = seedTargetSet(residual, transitions, errorReporter);
    676            // DetermineTargetStates (initialTargetSet) -> targetSet
    677            Set targetSet = step.getAfterStatus().getStates();
    678            targetSet.addAll(seedSet); //copy to preserve seedSet
    679            determineTargetStates(targetSet, errorReporter, scInstance);
    680            // BuildOnEntryList (targetSet, seedSet) -> entryList
    681            Set entered = SCXMLHelper.getAncestorClosure(targetSet, seedSet);
    682            seedSet.clear();
    683            for (Iterator i = transitions.iterator(); i.hasNext();) {
    684                Transition t = (Transition) i.next();
    685                List paths = t.getPaths();
    686                for (int j = 0; j < paths.size(); j++) {
    687                    Path p = (Path) paths.get(j);
    688                    entered.addAll(p.getDownwardSegment());
    689                }
    690                // If target is a History pseudo state, remove from entered list
    691                List rtargets = t.getRuntimeTargets();
    692                for (int j = 0; j < rtargets.size(); j++) {
    693                    TransitionTarget tt = (TransitionTarget) rtargets.get(j);
    694                    if (tt instanceof History) {
    695                        entered.remove(tt);
    696                    }
    697                }
    698            }
    699            // Check whether the computed state config is legal
    700            targetSet.addAll(residual);
    701            residual.clear();
    702            if (!SCXMLHelper.isLegalConfig(targetSet, errorReporter)) {
    703                throw new ModelException("Illegal state machine configuration!");
    704            }
    705            // sort onEntry and onExit according state hierarchy
    706            Object[] oex = exitedStates.toArray();
    707            exitedStates.clear();
    708            Object[] oen = entered.toArray();
    709            entered.clear();
    710            Arrays.sort(oex, getTTComparator());
    711            Arrays.sort(oen, getTTComparator());
    712            step.getExitList().addAll(Arrays.asList(oex));
    713            // we need to impose reverse order for the onEntry list
    714            List entering = Arrays.asList(oen);
    715            Collections.reverse(entering);
    716            step.getEntryList().addAll(entering);
    717            // reset 'done' flag
    718            for (Iterator reset = entering.iterator(); reset.hasNext();) {
    719                Object o = reset.next();
    720                if (o instanceof State) {
    721                    scInstance.setDone((State) o, false);
    722                }
    723            }
    724        }
    725        /**
    726         * Process any existing invokes, includes forwarding external events,
    727         * and executing any finalize handlers.
    728         *
    729         * @param events
    730         *            The events to be forwarded
    731         * @param errRep
    732         *            ErrorReporter callback
    733         * @param scInstance
    734         *            The state chart instance
    735         * @throws ModelException
    736         *             in case there is a fatal SCXML object model problem.
    737         */
    738        public void processInvokes(final TriggerEvent[] events,
    739                final ErrorReporter errRep, final SCInstance scInstance)
    740        throws ModelException {
    741            Set allEvents = new HashSet();
    742            allEvents.addAll(Arrays.asList(events));
    743            for (Iterator invokeIter = scInstance.getInvokers().entrySet().
    744                    iterator(); invokeIter.hasNext();) {
    745                Map.Entry iEntry = (Map.Entry) invokeIter.next();
    746                String parentId = ((TransitionTarget) iEntry.getKey()).getId();
    747                if (!finalizeMatch(parentId, allEvents)) { // prevent cycles
    748                    Invoker inv = (Invoker) iEntry.getValue();
    749                    try {
    750                        inv.parentEvents(events);
    751                    } catch (InvokerException ie) {
    752                        appLog.error(ie.getMessage(), ie);
    753                        throw new ModelException(ie.getMessage(), ie.getCause());
    754                    }
    755                }
    756            }
    757        }
    758
    759        /**
    760         * Initiate any new invokes.
    761         *
    762         * @param step
    763         *            The current Step
    764         * @param errRep
    765         *            ErrorReporter callback
    766         * @param scInstance
    767         *            The state chart instance
    768         */
    769        public void initiateInvokes(final Step step, final ErrorReporter errRep,
    770                final SCInstance scInstance) {
    771            Evaluator eval = scInstance.getEvaluator();
    772            Collection internalEvents = step.getAfterStatus().getEvents();
    773            for (Iterator iter = step.getAfterStatus().getStates().iterator();
    774                    iter.hasNext();) {
    775                State s = (State) iter.next();
    776                Context ctx = scInstance.getContext(s);
    777                Invoke i = s.getInvoke();
    778                if (i != null && scInstance.getInvoker(s) == null) {
    779                    String src = i.getSrc();
    780                    if (src == null) {
    781                        String srcexpr = i.getSrcexpr();
    782                        Object srcObj = null;
    783                        try {
    784                            ctx.setLocal(NAMESPACES_KEY, i.getNamespaces());
    785                            srcObj = eval.eval(ctx, srcexpr);
    786                            ctx.setLocal(NAMESPACES_KEY, null);
    787                            src = String.valueOf(srcObj);
    788                        } catch (SCXMLExpressionException see) {
    789                            errRep.onError(ErrorConstants.EXPRESSION_ERROR,
    790                                see.getMessage(), i);
    791                        }
    792                    }
    793                    String source = src;
    794                    PathResolver pr = i.getPathResolver();
    795                    if (pr != null) {
    796                        source = i.getPathResolver().resolvePath(src);
    797                    }
    798                    String ttype = i.getTargettype();
    799                    Invoker inv = null;
    800                    try {
    801                        inv = scInstance.newInvoker(ttype);
    802                    } catch (InvokerException ie) {
    803                        TriggerEvent te = new TriggerEvent(s.getId()
    804                            + ".invoke.failed", TriggerEvent.ERROR_EVENT);
    805                        internalEvents.add(te);
    806                        continue;
    807                    }
    808                    inv.setParentStateId(s.getId());
    809                    inv.setSCInstance(scInstance);
    810                    List params = i.params();
    811                    Map args = new HashMap();
    812                    for (Iterator pIter = params.iterator(); pIter.hasNext();) {
    813                        Param p = (Param) pIter.next();
    814                        String argExpr = p.getExpr();
    815                        Object argValue = null;
    816                        ctx.setLocal(NAMESPACES_KEY, p.getNamespaces());
    817                        // Do we have an "expr" attribute?
    818                        if (argExpr != null && argExpr.trim().length() > 0) {
    819                            // Yes, evaluate and store as parameter value
    820                            try {
    821                                argValue = eval.eval(ctx, argExpr);
    822                            } catch (SCXMLExpressionException see) {
    823                                errRep.onError(ErrorConstants.EXPRESSION_ERROR,
    824                                    see.getMessage(), i);
    825                            }
    826                        } else {
    827                            // No. Does value of "name" attribute refer to a valid
    828                            // location in the data model?
    829                            try {
    830                                argValue = eval.evalLocation(ctx, p.getName());
    831                                if (argValue == null) {
    832                                    // Generate error, 4.3.1 in WD-scxml-20080516
    833                                    TriggerEvent te = new TriggerEvent(s.getId()
    834                                        + ERR_ILLEGAL_ALLOC,
    835                                        TriggerEvent.ERROR_EVENT);
    836                                    internalEvents.add(te);
    837                                }
    838                            } catch (SCXMLExpressionException see) {
    839                                errRep.onError(ErrorConstants.EXPRESSION_ERROR,
    840                                    see.getMessage(), i);
    841                            }
    842                        }
    843                        ctx.setLocal(NAMESPACES_KEY, null);
    844                        args.put(p.getName(), argValue);
    845                    }
    846                    try {
    847                        inv.invoke(source, args);
    848                    } catch (InvokerException ie) {
    849                        TriggerEvent te = new TriggerEvent(s.getId()
    850                            + ".invoke.failed", TriggerEvent.ERROR_EVENT);
    851                        internalEvents.add(te);
    852                        continue;
    853                    }
    854                    scInstance.setInvoker(s, inv);
    855                }
    856            }
    857        }
    858
    859        /**
    860         * Implements prefix match, that is, if, for example,
    861         * "mouse.click" is a member of eventOccurrences and a
    862         * transition is triggered by "mouse", the method returns true.
    863         *
    864         * @param transEvent
    865         *            a trigger event of a transition
    866         * @param eventOccurrences
    867         *            current events
    868         * @return true/false
    869         */
    870        protected boolean eventMatch(final String transEvent,
    871                final Set eventOccurrences) {
    872            if (SCXMLHelper.isStringEmpty(transEvent)) { // Eventless transition
    873                return true;
    874            } else {
    875                String trimTransEvent = transEvent.trim();
    876                Iterator i = eventOccurrences.iterator();
    877                while (i.hasNext()) {
    878                    TriggerEvent te = (TriggerEvent) i.next();
    879                    String event = te.getName();
    880                    if (event == null) {
    881                        continue; // Unnamed events
    882                    }
    883                    String trimEvent = event.trim();
    884                    if (trimEvent.equals(trimTransEvent)) {
    885                        return true; // Match
    886                    } else if (te.getType() != TriggerEvent.CHANGE_EVENT
    887                            && trimTransEvent.equals("*")) {
    888                        return true; // Wildcard, skip gen'ed ones like .done etc.
    889                    } else if (trimTransEvent.endsWith(".*")
    890                            && trimEvent.startsWith(trimTransEvent.substring(0,
    891                                    trimTransEvent.length() - 1))) {
    892                        return true; // Prefixed wildcard
    893                    }
    894                }
    895                return false;
    896            }
    897        }
    898
    899        /**
    900         * Implements event prefix match to ascertain <finalize> execution.
    901         *
    902         * @param parentStateId
    903         *            the ID of the parent state of the <invoke> holding
    904         *            the <finalize>
    905         * @param eventOccurrences
    906         *            current events
    907         * @return true/false
    908         */
    909        protected boolean finalizeMatch(final String parentStateId,
    910                final Set eventOccurrences) {
    911            String prefix = parentStateId + ".invoke."; // invoke prefix
    912            Iterator i = eventOccurrences.iterator();
    913            while (i.hasNext()) {
    914                String evt = ((TriggerEvent) i.next()).getName();
    915                if (evt == null) {
    916                    continue; // Unnamed events
    917                } else if (evt.trim().startsWith(prefix)) {
    918                    return true;
    919                }
    920            }
    921            return false;
    922        }
    923
    924        /**
    925         * TransitionTargetComparator factory method.
    926         * @return Comparator The TransitionTarget comparator
    927         */
    928        protected Comparator getTTComparator() {
    929            return targetComparator;
    930        }
    931
    932        /**
    933         * Set the log used by this <code>SCXMLSemantics</code> instance.
    934         *
    935         * @param log The new log.
    936         */
    937        protected void setLog(final Log log) {
    938            this.appLog = log;
    939        }
    940
    941        /**
    942         * Get the log used by this <code>SCXMLSemantics</code> instance.
    943         *
    944         * @return Log The log being used.
    945         */
    946        protected Log getLog() {
    947            return appLog;
    948        }
    949
    950    }
    951