diff options
Diffstat (limited to 'src/corelib/statemachine/qstatemachine.cpp')
| -rw-r--r-- | src/corelib/statemachine/qstatemachine.cpp | 566 |
1 files changed, 434 insertions, 132 deletions
diff --git a/src/corelib/statemachine/qstatemachine.cpp b/src/corelib/statemachine/qstatemachine.cpp index a681688d46..f103bec591 100644 --- a/src/corelib/statemachine/qstatemachine.cpp +++ b/src/corelib/statemachine/qstatemachine.cpp @@ -177,6 +177,98 @@ QT_BEGIN_NAMESPACE // #define QSTATEMACHINE_DEBUG // #define QSTATEMACHINE_RESTORE_PROPERTIES_DEBUG +/* The function as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ : + +function isDescendant(state1, state2) + +Returns 'true' if state1 is a descendant of state2 (a child, or a child of a child, or a child of a +child of a child, etc.) Otherwise returns 'false'. +*/ +static inline bool isDescendant(const QAbstractState *state1, const QAbstractState *state2) +{ + Q_ASSERT(state1 != 0); + + for (QAbstractState *it = state1->parentState(); it != 0; it = it->parentState()) { + if (it == state2) + return true; + } + + return false; +} + +static bool containsDecendantOf(const QSet<QAbstractState *> &states, const QAbstractState *node) +{ + Q_FOREACH (QAbstractState *s, states) + if (isDescendant(s, node)) + return true; + + return false; +} + +/* The function as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ : + +function getProperAncestors(state1, state2) + +If state2 is null, returns the set of all ancestors of state1 in ancestry order (state1's parent +followed by the parent's parent, etc. up to an including the <scxml> element). If state2 is +non-null, returns in ancestry order the set of all ancestors of state1, up to but not including +state2. (A "proper ancestor" of a state is its parent, or the parent's parent, or the parent's +parent's parent, etc.))If state2 is state1's parent, or equal to state1, or a descendant of state1, +this returns the empty set. +*/ +static QVector<QState*> getProperAncestors(const QAbstractState *state, const QAbstractState *upperBound) +{ + Q_ASSERT(state != 0); + QVector<QState*> result; + result.reserve(16); + for (QState *it = state->parentState(); it && it != upperBound; it = it->parentState()) { + result.append(it); + } + return result; +} + +/* The function as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ : + +function getEffectiveTargetStates(transition) + +Returns the states that will be the target when 'transition' is taken, dereferencing any history states. + +function getEffectiveTargetStates(transition) + targets = new OrderedSet() + for s in transition.target + if isHistoryState(s): + if historyValue[s.id]: + targets.union(historyValue[s.id]) + else: + targets.union(getEffectiveTargetStates(s.transition)) + else: + targets.add(s) + return targets +*/ +static QSet<QAbstractState *> getEffectiveTargetStates(QAbstractTransition *transition) +{ + QSet<QAbstractState *> targets; + foreach (QAbstractState *s, transition->targetStates()) { + if (QHistoryState *historyState = QStateMachinePrivate::toHistoryState(s)) { + QList<QAbstractState*> historyConfiguration = QHistoryStatePrivate::get(historyState)->configuration; + if (!historyConfiguration.isEmpty()) { + // There is a saved history, so apply that. + targets.unite(historyConfiguration.toSet()); + } else if (QAbstractState *defaultState = historyState->defaultState()) { + // Qt does not support initial transitions, but uses the default state of the history state for this. + targets.insert(defaultState); + } else { + // Woops, we found a history state without a default state. That's not valid! + QStateMachinePrivate *m = QStateMachinePrivate::get(historyState->machine()); + m->setError(QStateMachine::NoDefaultStateInHistoryStateError, historyState); + } + } else { + targets.insert(s); + } + } + return targets; +} + template <class T> static uint qHash(const QPointer<T> &p) { return qHash(p.data()); } @@ -246,21 +338,30 @@ static int indexOfDescendant(QState *s, QAbstractState *desc) QList<QAbstractState*> childStates = QStatePrivate::get(s)->childStates(); for (int i = 0; i < childStates.size(); ++i) { QAbstractState *c = childStates.at(i); - if ((c == desc) || QStateMachinePrivate::isDescendantOf(desc, c)) { + if ((c == desc) || isDescendant(desc, c)) { return i; } } return -1; } +bool QStateMachinePrivate::transitionStateEntryLessThan(QAbstractTransition *t1, QAbstractTransition *t2) +{ + QState *s1 = t1->sourceState(), *s2 = t2->sourceState(); + if (s1 == s2) + return QStatePrivate::get(s1)->transitions().indexOf(t1) < QStatePrivate::get(s2)->transitions().indexOf(t2); + else + return stateEntryLessThan(t1->sourceState(), t2->sourceState()); +} + bool QStateMachinePrivate::stateEntryLessThan(QAbstractState *s1, QAbstractState *s2) { if (s1->parent() == s2->parent()) { return s1->parent()->children().indexOf(s1) < s2->parent()->children().indexOf(s2); - } else if (isDescendantOf(s1, s2)) { + } else if (isDescendant(s1, s2)) { return false; - } else if (isDescendantOf(s2, s1)) { + } else if (isDescendant(s2, s1)) { return true; } else { Q_ASSERT(s1->machine() != 0); @@ -276,9 +377,9 @@ bool QStateMachinePrivate::stateExitLessThan(QAbstractState *s1, QAbstractState if (s1->parent() == s2->parent()) { return s2->parent()->children().indexOf(s2) < s1->parent()->children().indexOf(s1); - } else if (isDescendantOf(s1, s2)) { + } else if (isDescendant(s1, s2)) { return true; - } else if (isDescendantOf(s2, s1)) { + } else if (isDescendant(s2, s1)) { return false; } else { Q_ASSERT(s1->machine() != 0); @@ -289,17 +390,20 @@ bool QStateMachinePrivate::stateExitLessThan(QAbstractState *s1, QAbstractState } } -QState *QStateMachinePrivate::findLCA(const QList<QAbstractState*> &states) const +QState *QStateMachinePrivate::findLCA(const QList<QAbstractState*> &states, bool onlyCompound) const { if (states.isEmpty()) return 0; - QList<QState*> ancestors = properAncestors(states.at(0), rootState()->parentState()); + QVector<QState*> ancestors = getProperAncestors(states.at(0), rootState()->parentState()); for (int i = 0; i < ancestors.size(); ++i) { QState *anc = ancestors.at(i); + if (onlyCompound && !isCompound(anc)) + continue; + bool ok = true; for (int j = states.size() - 1; (j > 0) && ok; --j) { const QAbstractState *s = states.at(j); - if (!isDescendantOf(s, anc)) + if (!isDescendant(s, anc)) ok = false; } if (ok) @@ -308,40 +412,26 @@ QState *QStateMachinePrivate::findLCA(const QList<QAbstractState*> &states) cons return 0; } -bool QStateMachinePrivate::isPreempted(const QAbstractState *s, const QSet<QAbstractTransition*> &transitions) const +QState *QStateMachinePrivate::findLCCA(const QList<QAbstractState*> &states) const { - QSet<QAbstractTransition*>::const_iterator it; - for (it = transitions.constBegin(); it != transitions.constEnd(); ++it) { - QAbstractTransition *t = *it; - QList<QAbstractState*> lst = t->targetStates(); - if (!lst.isEmpty()) { - lst.prepend(t->sourceState()); - QAbstractState *lca = findLCA(lst); - if (isDescendantOf(s, lca)) { -#ifdef QSTATEMACHINE_DEBUG - qDebug() << q_func() << ':' << transitions << "preempts selection of a transition from" - << s << "because" << s << "is a descendant of" << lca; -#endif - return true; - } - } - } - return false; + return findLCA(states, true); } -QSet<QAbstractTransition*> QStateMachinePrivate::selectTransitions(QEvent *event) const +QList<QAbstractTransition*> QStateMachinePrivate::selectTransitions(QEvent *event) { Q_Q(const QStateMachine); - QSet<QAbstractTransition*> enabledTransitions; - QSet<QAbstractState*>::const_iterator it; + + QVarLengthArray<QAbstractState *> configuration_sorted; + foreach (QAbstractState *s, configuration) { + if (isAtomic(s)) + configuration_sorted.append(s); + } + std::sort(configuration_sorted.begin(), configuration_sorted.end(), stateEntryLessThan); + + QList<QAbstractTransition*> enabledTransitions; const_cast<QStateMachine*>(q)->beginSelectTransitions(event); - for (it = configuration.constBegin(); it != configuration.constEnd(); ++it) { - QAbstractState *state = *it; - if (!isAtomic(state)) - continue; - if (isPreempted(state, enabledTransitions)) - continue; - QList<QState*> lst = properAncestors(state, rootState()->parentState()); + foreach (QAbstractState *state, configuration_sorted) { + QVector<QState*> lst = getProperAncestors(state, Q_NULLPTR); if (QState *grp = toStandardState(state)) lst.prepend(grp); bool found = false; @@ -354,28 +444,93 @@ QSet<QAbstractTransition*> QStateMachinePrivate::selectTransitions(QEvent *event #ifdef QSTATEMACHINE_DEBUG qDebug() << q << ": selecting transition" << t; #endif - enabledTransitions.insert(t); + enabledTransitions.append(t); found = true; break; } } } } + + if (!enabledTransitions.isEmpty()) { + removeConflictingTransitions(enabledTransitions); +#ifdef QSTATEMACHINE_DEBUG + qDebug() << q << ": enabled transitions after removing conflicts:" << enabledTransitions; +#endif + } const_cast<QStateMachine*>(q)->endSelectTransitions(event); return enabledTransitions; } +/* The function as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ : + +function removeConflictingTransitions(enabledTransitions): + filteredTransitions = new OrderedSet() + // toList sorts the transitions in the order of the states that selected them + for t1 in enabledTransitions.toList(): + t1Preempted = false; + transitionsToRemove = new OrderedSet() + for t2 in filteredTransitions.toList(): + if computeExitSet([t1]).hasIntersection(computeExitSet([t2])): + if isDescendant(t1.source, t2.source): + transitionsToRemove.add(t2) + else: + t1Preempted = true + break + if not t1Preempted: + for t3 in transitionsToRemove.toList(): + filteredTransitions.delete(t3) + filteredTransitions.add(t1) + + return filteredTransitions +*/ +void QStateMachinePrivate::removeConflictingTransitions(QList<QAbstractTransition*> &enabledTransitions) +{ + QList<QAbstractTransition*> filteredTransitions; + filteredTransitions.reserve(enabledTransitions.size()); + std::sort(enabledTransitions.begin(), enabledTransitions.end(), transitionStateEntryLessThan); + + Q_FOREACH (QAbstractTransition *t1, enabledTransitions) { + bool t1Preempted = false; + QVarLengthArray<QAbstractTransition *> transitionsToRemove; + QSet<QAbstractState*> exitSetT1 = computeExitSet_Unordered(QList<QAbstractTransition*>() << t1); + Q_FOREACH (QAbstractTransition *t2, filteredTransitions) { + QSet<QAbstractState*> exitSetT2 = computeExitSet_Unordered(QList<QAbstractTransition*>() << t2); + if (!exitSetT1.intersect(exitSetT2).isEmpty()) { + if (isDescendant(t1->sourceState(), t2->sourceState())) { + transitionsToRemove.append(t2); + } else { + t1Preempted = true; + break; + } + } + } + if (!t1Preempted) { + Q_FOREACH (QAbstractTransition *t3, transitionsToRemove) + filteredTransitions.removeAll(t3); + filteredTransitions.append(t1); + } + } + + enabledTransitions = filteredTransitions; +} + void QStateMachinePrivate::microstep(QEvent *event, const QList<QAbstractTransition*> &enabledTransitions) { #ifdef QSTATEMACHINE_DEBUG qDebug() << q_func() << ": begin microstep( enabledTransitions:" << enabledTransitions << ')'; qDebug() << q_func() << ": configuration before exiting states:" << configuration; #endif - QList<QAbstractState*> exitedStates = computeStatesToExit(enabledTransitions); + QList<QAbstractState*> exitedStates = computeExitSet(enabledTransitions); QHash<RestorableId, QVariant> pendingRestorables = computePendingRestorables(exitedStates); QSet<QAbstractState*> statesForDefaultEntry; - QList<QAbstractState*> enteredStates = computeStatesToEnter(enabledTransitions, statesForDefaultEntry); + QList<QAbstractState*> enteredStates = computeEntrySet(enabledTransitions, statesForDefaultEntry); + +#ifdef QSTATEMACHINE_DEBUG + qDebug() << q_func() << ": computed exit set:" << exitedStates; + qDebug() << q_func() << ": computed entry set:" << enteredStates; +#endif QHash<QAbstractState*, QList<QPropertyAssignment> > assignmentsForEnteredStates = computePropertyAssignments(enteredStates, pendingRestorables); @@ -409,38 +564,63 @@ void QStateMachinePrivate::microstep(QEvent *event, const QList<QAbstractTransit #endif } -QList<QAbstractState*> QStateMachinePrivate::computeStatesToExit(const QList<QAbstractTransition*> &enabledTransitions) +/* The function as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ : + +procedure computeExitSet(enabledTransitions) + +For each transition t in enabledTransitions, if t is targetless then do nothing, else compute the +transition's domain. (This will be the source state in the case of internal transitions) or the +least common compound ancestor state of the source state and target states of t (in the case of +external transitions. Add to the statesToExit set all states in the configuration that are +descendants of the domain. + +function computeExitSet(transitions) + statesToExit = new OrderedSet + for t in transitions: + if (t.target): + domain = getTransitionDomain(t) + for s in configuration: + if isDescendant(s,domain): + statesToExit.add(s) + return statesToExit +*/ +QList<QAbstractState*> QStateMachinePrivate::computeExitSet(const QList<QAbstractTransition*> &enabledTransitions) +{ + QList<QAbstractState*> statesToExit_sorted = computeExitSet_Unordered(enabledTransitions).toList(); + std::sort(statesToExit_sorted.begin(), statesToExit_sorted.end(), stateExitLessThan); + return statesToExit_sorted; +} + +QSet<QAbstractState*> QStateMachinePrivate::computeExitSet_Unordered(const QList<QAbstractTransition*> &enabledTransitions) { QSet<QAbstractState*> statesToExit; -// QSet<QAbstractState*> statesToSnapshot; for (int i = 0; i < enabledTransitions.size(); ++i) { QAbstractTransition *t = enabledTransitions.at(i); - QList<QAbstractState*> lst = t->targetStates(); - if (lst.isEmpty()) - continue; - lst.prepend(t->sourceState()); - QAbstractState *lca = findLCA(lst); - if (lca == 0) { - setError(QStateMachine::NoCommonAncestorForTransitionError, t->sourceState()); - lst = pendingErrorStates.toList(); + QList<QAbstractState *> effectiveTargetStates = getEffectiveTargetStates(t).toList(); + QAbstractState *domain = getTransitionDomain(t, effectiveTargetStates); + if (domain == Q_NULLPTR && !t->targetStates().isEmpty()) { + // So we didn't find the least common ancestor for the source and target states of the + // transition. If there were not target states, that would be fine: then the transition + // will fire any events or signals, but not exit the state. + // + // However, there are target states, so it's either a node without a parent (or parent's + // parent, etc), or the state belongs to a different state machine. Either way, this + // makes the state machine invalid. + if (error == QStateMachine::NoError) + setError(QStateMachine::NoCommonAncestorForTransitionError, t->sourceState()); + QList<QAbstractState *> lst = pendingErrorStates.toList(); lst.prepend(t->sourceState()); - lca = findLCA(lst); - Q_ASSERT(lca != 0); + domain = findLCCA(lst); + Q_ASSERT(domain != 0); } - { - QSet<QAbstractState*>::const_iterator it; - for (it = configuration.constBegin(); it != configuration.constEnd(); ++it) { - QAbstractState *s = *it; - if (isDescendantOf(s, lca)) - statesToExit.insert(s); - } + Q_FOREACH (QAbstractState* s, configuration) { + if (isDescendant(s, domain)) + statesToExit.insert(s); } } - QList<QAbstractState*> statesToExit_sorted = statesToExit.toList(); - std::sort(statesToExit_sorted.begin(), statesToExit_sorted.end(), stateExitLessThan); - return statesToExit_sorted; + return statesToExit; } void QStateMachinePrivate::exitStates(QEvent *event, const QList<QAbstractState*> &statesToExit_sorted, @@ -457,7 +637,7 @@ void QStateMachinePrivate::exitStates(QEvent *event, const QList<QAbstractState* for (it = configuration.constBegin(); it != configuration.constEnd(); ++it) { QAbstractState *s0 = *it; if (QHistoryStatePrivate::get(h)->historyType == QHistoryState::DeepHistory) { - if (isAtomic(s0) && isDescendantOf(s0, s)) + if (isAtomic(s0) && isDescendant(s0, s)) QHistoryStatePrivate::get(h)->configuration.append(s0); } else if (s0->parentState() == s) { QHistoryStatePrivate::get(h)->configuration.append(s0); @@ -500,30 +680,20 @@ void QStateMachinePrivate::executeTransitionContent(QEvent *event, const QList<Q } } -QList<QAbstractState*> QStateMachinePrivate::computeStatesToEnter(const QList<QAbstractTransition *> &enabledTransitions, - QSet<QAbstractState *> &statesForDefaultEntry) +QList<QAbstractState*> QStateMachinePrivate::computeEntrySet(const QList<QAbstractTransition *> &enabledTransitions, + QSet<QAbstractState *> &statesForDefaultEntry) { QSet<QAbstractState*> statesToEnter; if (pendingErrorStates.isEmpty()) { - for (int i = 0; i < enabledTransitions.size(); ++i) { - QAbstractTransition *t = enabledTransitions.at(i); - QList<QAbstractState*> lst = t->targetStates(); - if (lst.isEmpty()) - continue; - QAbstractState *src = t->sourceState(); - if (src) - lst.prepend(src); - QState *lca = findLCA(lst); - for (int j = src ? 1 : 0; j < lst.size(); ++j) { - QAbstractState *s = lst.at(j); - addStatesToEnter(s, lca, statesToEnter, statesForDefaultEntry); + Q_FOREACH (QAbstractTransition *t, enabledTransitions) { + Q_FOREACH (QAbstractState *s, t->targetStates()) { + addDescendantStatesToEnter(s, statesToEnter, statesForDefaultEntry); } - if (isParallel(lca)) { - QList<QAbstractState*> lcac = QStatePrivate::get(lca)->childStates(); - foreach (QAbstractState* child,lcac) { - if (!statesToEnter.contains(child)) - addStatesToEnter(child,lca,statesToEnter,statesForDefaultEntry); - } + + QList<QAbstractState *> effectiveTargetStates = getEffectiveTargetStates(t).toList(); + QAbstractState *ancestor = getTransitionDomain(t, effectiveTargetStates); + Q_FOREACH (QAbstractState *s, effectiveTargetStates) { + addAncestorStatesToEnter(s, ancestor, statesToEnter, statesForDefaultEntry); } } } @@ -542,6 +712,51 @@ QList<QAbstractState*> QStateMachinePrivate::computeStatesToEnter(const QList<QA return statesToEnter_sorted; } +/* The algorithm as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ : + +function getTransitionDomain(transition) + +Return the compound state such that 1) all states that are exited or entered as a result of taking +'transition' are descendants of it 2) no descendant of it has this property. + +function getTransitionDomain(t) + tstates = getEffectiveTargetStates(t) + if not tstates: + return null + elif t.type == "internal" and isCompoundState(t.source) and tstates.every(lambda s: isDescendant(s,t.source)): + return t.source + else: + return findLCCA([t.source].append(tstates)) +*/ +QAbstractState *QStateMachinePrivate::getTransitionDomain(QAbstractTransition *t, const QList<QAbstractState *> &effectiveTargetStates) const +{ + if (effectiveTargetStates.isEmpty()) + return 0; + +#if 0 + // Qt only has external transitions, so skip the special case for the internal transitions + if (QState *tSource = t->sourceState()) { + if (isCompound(tSource)) { + bool allDescendants = true; + Q_FOREACH (QAbstractState *s, effectiveTargetStates) { + if (!isDescendant(s, tSource)) { + allDescendants = false; + break; + } + } + + if (allDescendants) + return tSource; + } + } +#endif + + QList<QAbstractState *> states(effectiveTargetStates); + if (QAbstractState *src = t->sourceState()) + states.prepend(src); + return findLCCA(states); +} + void QStateMachinePrivate::enterStates(QEvent *event, const QList<QAbstractState*> &exitedStates_sorted, const QList<QAbstractState*> &statesToEnter_sorted, const QSet<QAbstractState*> &statesForDefaultEntry, @@ -610,10 +825,9 @@ void QStateMachinePrivate::enterStates(QEvent *event, const QList<QAbstractState QState *parent = s->parentState(); if (parent) { if (parent != rootState()) { -#ifdef QSTATEMACHINE_DEBUG - qDebug() << q << ": emitting finished signal for" << parent; -#endif - QStatePrivate::get(parent)->emitFinished(); + QFinalState *finalState = qobject_cast<QFinalState *>(s); + Q_ASSERT(finalState); + emitStateFinished(parent, finalState); } QState *grandparent = parent->parentState(); if (grandparent && isParallel(grandparent)) { @@ -627,10 +841,9 @@ void QStateMachinePrivate::enterStates(QEvent *event, const QList<QAbstractState } } if (allChildStatesFinal && (grandparent != rootState())) { -#ifdef QSTATEMACHINE_DEBUG - qDebug() << q << ": emitting finished signal for" << grandparent; -#endif - QStatePrivate::get(grandparent)->emitFinished(); + QFinalState *finalState = qobject_cast<QFinalState *>(s); + Q_ASSERT(finalState); + emitStateFinished(grandparent, finalState); } } } @@ -719,30 +932,126 @@ void QStateMachinePrivate::addStatesToEnter(QAbstractState *s, QState *root, } } -void QStateMachinePrivate::addAncestorStatesToEnter(QAbstractState *s, QState *root, +/* The algorithm as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ has a bug. See + * QTBUG-44963 for details. The algorithm here is as described in + * http://www.w3.org/Voice/2013/scxml-irp/SCXML.htm as of Friday March 13, 2015. + +procedure addDescendantStatesToEnter(state,statesToEnter,statesForDefaultEntry, defaultHistoryContent): + if isHistoryState(state): + if historyValue[state.id]: + for s in historyValue[state.id]: + addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry, defaultHistoryContent) + for s in historyValue[state.id]: + addAncestorStatesToEnter(s, state.parent, statesToEnter, statesForDefaultEntry, defaultHistoryContent) + else: + defaultHistoryContent[state.parent.id] = state.transition.content + for s in state.transition.target: + addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry, defaultHistoryContent) + for s in state.transition.target: + addAncestorStatesToEnter(s, state.parent, statesToEnter, statesForDefaultEntry, defaultHistoryContent) + else: + statesToEnter.add(state) + if isCompoundState(state): + statesForDefaultEntry.add(state) + for s in state.initial.transition.target: + addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry, defaultHistoryContent) + for s in state.initial.transition.target: + addAncestorStatesToEnter(s, state, statesToEnter, statesForDefaultEntry, defaultHistoryContent) + else: + if isParallelState(state): + for child in getChildStates(state): + if not statesToEnter.some(lambda s: isDescendant(s,child)): + addDescendantStatesToEnter(child,statesToEnter,statesForDefaultEntry, defaultHistoryContent) +*/ +void QStateMachinePrivate::addDescendantStatesToEnter(QAbstractState *state, + QSet<QAbstractState*> &statesToEnter, + QSet<QAbstractState*> &statesForDefaultEntry) +{ + if (QHistoryState *h = toHistoryState(state)) { + QList<QAbstractState*> historyConfiguration = QHistoryStatePrivate::get(h)->configuration; + if (!historyConfiguration.isEmpty()) { + Q_FOREACH (QAbstractState *s, historyConfiguration) + addDescendantStatesToEnter(s, statesToEnter, statesForDefaultEntry); + Q_FOREACH (QAbstractState *s, historyConfiguration) + addAncestorStatesToEnter(s, state->parentState(), statesToEnter, statesForDefaultEntry); + +#ifdef QSTATEMACHINE_DEBUG + qDebug() << q_func() << ": restoring" + << ((QHistoryStatePrivate::get(h)->historyType == QHistoryState::DeepHistory) ? "deep" : "shallow") + << "history from" << state << ':' << historyConfiguration; +#endif + } else { + QList<QAbstractState*> defaultHistoryContent; + if (QHistoryStatePrivate::get(h)->defaultState) + defaultHistoryContent.append(QHistoryStatePrivate::get(h)->defaultState); + + if (defaultHistoryContent.isEmpty()) { + setError(QStateMachine::NoDefaultStateInHistoryStateError, h); + } else { + Q_FOREACH (QAbstractState *s, defaultHistoryContent) + addDescendantStatesToEnter(s, statesToEnter, statesForDefaultEntry); + Q_FOREACH (QAbstractState *s, defaultHistoryContent) + addAncestorStatesToEnter(s, state->parentState(), statesToEnter, statesForDefaultEntry); +#ifdef QSTATEMACHINE_DEBUG + qDebug() << q_func() << ": initial history targets for" << state << ':' << defaultHistoryContent; +#endif + } + } + } else { + if (state == rootState()) { + // Error has already been set by exitStates(). + Q_ASSERT(error != QStateMachine::NoError); + return; + } + statesToEnter.insert(state); + if (isCompound(state)) { + statesForDefaultEntry.insert(state); + if (QAbstractState *initial = toStandardState(state)->initialState()) { + Q_ASSERT(initial->machine() == q_func()); + + // Qt does not support initial transitions (which is a problem for parallel states). + // The way it simulates this for other states, is by having a single initial state. + statesForDefaultEntry.insert(initial); + + addDescendantStatesToEnter(initial, statesToEnter, statesForDefaultEntry); + addAncestorStatesToEnter(initial, state, statesToEnter, statesForDefaultEntry); + } else { + setError(QStateMachine::NoInitialStateError, state); + return; + } + } else if (isParallel(state)) { + QState *grp = toStandardState(state); + Q_FOREACH (QAbstractState *child, QStatePrivate::get(grp)->childStates()) { + if (!containsDecendantOf(statesToEnter, child)) + addDescendantStatesToEnter(child, statesToEnter, statesForDefaultEntry); + } + } + } +} + + +/* The algorithm as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ : + +procedure addAncestorStatesToEnter(state, ancestor, statesToEnter, statesForDefaultEntry, defaultHistoryContent) + for anc in getProperAncestors(state,ancestor): + statesToEnter.add(anc) + if isParallelState(anc): + for child in getChildStates(anc): + if not statesToEnter.some(lambda s: isDescendant(s,child)): + addDescendantStatesToEnter(child,statesToEnter,statesForDefaultEntry, defaultHistoryContent) +*/ +void QStateMachinePrivate::addAncestorStatesToEnter(QAbstractState *s, QAbstractState *ancestor, QSet<QAbstractState*> &statesToEnter, QSet<QAbstractState*> &statesForDefaultEntry) { - QList<QState*> ancs = properAncestors(s, root); - for (int i = 0; i < ancs.size(); ++i) { - QState *anc = ancs.at(i); + Q_FOREACH (QState *anc, getProperAncestors(s, ancestor)) { if (!anc->parentState()) continue; statesToEnter.insert(anc); if (isParallel(anc)) { - QList<QAbstractState*> lst = QStatePrivate::get(anc)->childStates(); - for (int j = 0; j < lst.size(); ++j) { - QAbstractState *child = lst.at(j); - bool hasDescendantInList = false; - QSet<QAbstractState*>::const_iterator it; - for (it = statesToEnter.constBegin(); it != statesToEnter.constEnd(); ++it) { - if (isDescendantOf(*it, child)) { - hasDescendantInList = true; - break; - } - } - if (!hasDescendantInList) - addStatesToEnter(child, anc, statesToEnter, statesForDefaultEntry); + Q_FOREACH (QAbstractState *child, QStatePrivate::get(anc)->childStates()) { + if (!containsDecendantOf(statesToEnter, child)) + addDescendantStatesToEnter(child, statesToEnter, statesForDefaultEntry); } } } @@ -780,27 +1089,6 @@ bool QStateMachinePrivate::isAtomic(const QAbstractState *s) const || (ss && QStatePrivate::get(ss)->isMachine && (ss != rootState())); } - -bool QStateMachinePrivate::isDescendantOf(const QAbstractState *state, const QAbstractState *other) -{ - Q_ASSERT(state != 0); - for (QAbstractState *s = state->parentState(); s != 0; s = s->parentState()) { - if (s == other) - return true; - } - return false; -} - -QList<QState*> QStateMachinePrivate::properAncestors(const QAbstractState *state, const QState *upperBound) -{ - Q_ASSERT(state != 0); - QList<QState*> result; - for (QState *s = state->parentState(); s && s != upperBound; s = s->parentState()) { - result.append(s); - } - return result; -} - QState *QStateMachinePrivate::toStandardState(QAbstractState *state) { if (state && (QAbstractStatePrivate::get(state)->stateType == QAbstractStatePrivate::StandardState)) @@ -1082,6 +1370,9 @@ void QStateMachinePrivate::setError(QStateMachine::Error errorCode, QAbstractSta Q_ASSERT(currentErrorState != rootState()); if (currentErrorState != 0) { +#ifdef QSTATEMACHINE_DEBUG + qDebug() << q << ": entering error state" << currentErrorState << "from" << currentContext; +#endif QState *lca = findLCA(QList<QAbstractState*>() << currentErrorState << currentContext); addStatesToEnter(currentErrorState, lca, pendingErrorStates, pendingErrorStatesForDefaultEntry); } else { @@ -1385,8 +1676,7 @@ void QStateMachinePrivate::_q_start() executeTransitionContent(&nullEvent, transitions); QList<QAbstractState*> exitedStates = QList<QAbstractState*>(); QSet<QAbstractState*> statesForDefaultEntry; - QList<QAbstractState*> enteredStates = computeStatesToEnter(transitions, - statesForDefaultEntry); + QList<QAbstractState*> enteredStates = computeEntrySet(transitions, statesForDefaultEntry); QHash<RestorableId, QVariant> pendingRestorables; QHash<QAbstractState*, QList<QPropertyAssignment> > assignmentsForEnteredStates = computePropertyAssignments(enteredStates, pendingRestorables); @@ -1440,7 +1730,7 @@ void QStateMachinePrivate::_q_process() processing = false; break; } - QSet<QAbstractTransition*> enabledTransitions; + QList<QAbstractTransition*> enabledTransitions; QEvent *e = new QEvent(QEvent::None); enabledTransitions = selectTransitions(e); if (enabledTransitions.isEmpty()) { @@ -1477,7 +1767,7 @@ void QStateMachinePrivate::_q_process() if (!enabledTransitions.isEmpty()) { didChange = true; q->beginMicrostep(e); - microstep(e, enabledTransitions.toList()); + microstep(e, enabledTransitions); q->endMicrostep(e); } else { @@ -1666,6 +1956,18 @@ void QStateMachinePrivate::endMacrostep(bool didChange) } +void QStateMachinePrivate::emitStateFinished(QState *forState, QFinalState *guiltyState) +{ + Q_UNUSED(guiltyState); + Q_ASSERT(guiltyState); + +#ifdef QSTATEMACHINE_DEBUG + qDebug() << q << ": emitting finished signal for" << forState; +#endif + + QStatePrivate::get(forState)->emitFinished(); +} + namespace _QStateMachine_Internal{ class GoToStateTransition : public QAbstractTransition |