View Javadoc

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