diff options
| -rw-r--r-- | src/corelib/statemachine/qstatemachine.cpp | 243 | ||||
| -rw-r--r-- | src/corelib/statemachine/qstatemachine_p.h | 17 | ||||
| -rw-r--r-- | tests/auto/corelib/statemachine/qstatemachine/tst_qstatemachine.cpp | 27 |
3 files changed, 220 insertions, 67 deletions
diff --git a/src/corelib/statemachine/qstatemachine.cpp b/src/corelib/statemachine/qstatemachine.cpp index f02e27330d..d91b4ba14a 100644 --- a/src/corelib/statemachine/qstatemachine.cpp +++ b/src/corelib/statemachine/qstatemachine.cpp @@ -177,6 +177,100 @@ QT_BEGIN_NAMESPACE // #define QSTATEMACHINE_DEBUG // #define QSTATEMACHINE_RESTORE_PROPERTIES_DEBUG +struct CalculationCache { + struct TransitionInfo { + QList<QAbstractState*> effectiveTargetStates; + QSet<QAbstractState*> exitSet; + QAbstractState *transitionDomain; + + bool effectiveTargetStatesIsKnown: 1; + bool exitSetIsKnown : 1; + bool transitionDomainIsKnown : 1; + + TransitionInfo() + : transitionDomain(0) + , effectiveTargetStatesIsKnown(false) + , exitSetIsKnown(false) + , transitionDomainIsKnown(false) + {} + }; + + typedef QHash<QAbstractTransition *, TransitionInfo> TransitionInfoCache; + TransitionInfoCache cache; + + bool effectiveTargetStates(QAbstractTransition *t, QList<QAbstractState *> *targets) const + { + Q_ASSERT(targets); + + TransitionInfoCache::const_iterator cacheIt = cache.find(t); + if (cacheIt == cache.end() || !cacheIt->effectiveTargetStatesIsKnown) + return false; + + *targets = cacheIt->effectiveTargetStates; + return true; + } + + void insert(QAbstractTransition *t, const QList<QAbstractState *> &targets) + { + TransitionInfoCache::iterator cacheIt = cache.find(t); + TransitionInfo &ti = cacheIt == cache.end() + ? *cache.insert(t, TransitionInfo()) + : *cacheIt; + + Q_ASSERT(!ti.effectiveTargetStatesIsKnown); + ti.effectiveTargetStates = targets; + ti.effectiveTargetStatesIsKnown = true; + } + + bool exitSet(QAbstractTransition *t, QSet<QAbstractState *> *exits) const + { + Q_ASSERT(exits); + + TransitionInfoCache::const_iterator cacheIt = cache.find(t); + if (cacheIt == cache.end() || !cacheIt->exitSetIsKnown) + return false; + + *exits = cacheIt->exitSet; + return true; + } + + void insert(QAbstractTransition *t, const QSet<QAbstractState *> &exits) + { + TransitionInfoCache::iterator cacheIt = cache.find(t); + TransitionInfo &ti = cacheIt == cache.end() + ? *cache.insert(t, TransitionInfo()) + : *cacheIt; + + Q_ASSERT(!ti.exitSetIsKnown); + ti.exitSet = exits; + ti.exitSetIsKnown = true; + } + + bool transitionDomain(QAbstractTransition *t, QAbstractState **domain) const + { + Q_ASSERT(domain); + + TransitionInfoCache::const_iterator cacheIt = cache.find(t); + if (cacheIt == cache.end() || !cacheIt->transitionDomainIsKnown) + return false; + + *domain = cacheIt->transitionDomain; + return true; + } + + void insert(QAbstractTransition *t, QAbstractState *domain) + { + TransitionInfoCache::iterator cacheIt = cache.find(t); + TransitionInfo &ti = cacheIt == cache.end() + ? *cache.insert(t, TransitionInfo()) + : *cacheIt; + + Q_ASSERT(!ti.transitionDomainIsKnown); + ti.transitionDomain = domain; + ti.transitionDomainIsKnown = true; + } +}; + /* The function as described in http://www.w3.org/TR/2014/WD-scxml-20140529/ : function isDescendant(state1, state2) @@ -245,8 +339,14 @@ function getEffectiveTargetStates(transition) targets.add(s) return targets */ -static QSet<QAbstractState *> getEffectiveTargetStates(QAbstractTransition *transition) +static QList<QAbstractState *> getEffectiveTargetStates(QAbstractTransition *transition, CalculationCache *cache) { + Q_ASSERT(cache); + + QList<QAbstractState *> targetsList; + if (cache->effectiveTargetStates(transition, &targetsList)) + return targetsList; + QSet<QAbstractState *> targets; foreach (QAbstractState *s, transition->targetStates()) { if (QHistoryState *historyState = QStateMachinePrivate::toHistoryState(s)) { @@ -266,7 +366,10 @@ static QSet<QAbstractState *> getEffectiveTargetStates(QAbstractTransition *tran targets.insert(s); } } - return targets; + + targetsList = targets.toList(); + cache->insert(transition, targetsList); + return targetsList; } template <class T> @@ -417,8 +520,9 @@ QState *QStateMachinePrivate::findLCCA(const QList<QAbstractState*> &states) con return findLCA(states, true); } -QList<QAbstractTransition*> QStateMachinePrivate::selectTransitions(QEvent *event) +QList<QAbstractTransition*> QStateMachinePrivate::selectTransitions(QEvent *event, CalculationCache *cache) { + Q_ASSERT(cache); Q_Q(const QStateMachine); QVarLengthArray<QAbstractState *> configuration_sorted; @@ -453,7 +557,7 @@ QList<QAbstractTransition*> QStateMachinePrivate::selectTransitions(QEvent *even } if (!enabledTransitions.isEmpty()) { - removeConflictingTransitions(enabledTransitions); + removeConflictingTransitions(enabledTransitions, cache); #ifdef QSTATEMACHINE_DEBUG qDebug() << q << ": enabled transitions after removing conflicts:" << enabledTransitions; #endif @@ -486,15 +590,20 @@ function removeConflictingTransitions(enabledTransitions): Note: the implementation below does not build the transitionsToRemove, but removes them in-place. */ -void QStateMachinePrivate::removeConflictingTransitions(QList<QAbstractTransition*> &enabledTransitions) +void QStateMachinePrivate::removeConflictingTransitions(QList<QAbstractTransition*> &enabledTransitions, CalculationCache *cache) { + Q_ASSERT(cache); + + if (enabledTransitions.size() == 1) + return; // There is no transition to conflict with. + QList<QAbstractTransition*> filteredTransitions; filteredTransitions.reserve(enabledTransitions.size()); std::sort(enabledTransitions.begin(), enabledTransitions.end(), transitionStateEntryLessThan); foreach (QAbstractTransition *t1, enabledTransitions) { bool t1Preempted = false; - QSet<QAbstractState*> exitSetT1 = computeExitSet_Unordered(QList<QAbstractTransition*>() << t1); + QSet<QAbstractState*> exitSetT1 = computeExitSet_Unordered(t1, cache); QList<QAbstractTransition*>::iterator t2It = filteredTransitions.begin(); while (t2It != filteredTransitions.end()) { QAbstractTransition *t2 = *t2It; @@ -505,7 +614,7 @@ void QStateMachinePrivate::removeConflictingTransitions(QList<QAbstractTransitio break; } - QSet<QAbstractState*> exitSetT2 = computeExitSet_Unordered(QList<QAbstractTransition*>() << t2); + QSet<QAbstractState*> exitSetT2 = computeExitSet_Unordered(t2, cache); if (exitSetT1.intersect(exitSetT2).isEmpty()) { // No conflict, no cry. Next patient please. ++t2It; @@ -529,17 +638,20 @@ void QStateMachinePrivate::removeConflictingTransitions(QList<QAbstractTransitio enabledTransitions = filteredTransitions; } -void QStateMachinePrivate::microstep(QEvent *event, const QList<QAbstractTransition*> &enabledTransitions) +void QStateMachinePrivate::microstep(QEvent *event, const QList<QAbstractTransition*> &enabledTransitions, + CalculationCache *cache) { + Q_ASSERT(cache); + #ifdef QSTATEMACHINE_DEBUG qDebug() << q_func() << ": begin microstep( enabledTransitions:" << enabledTransitions << ')'; qDebug() << q_func() << ": configuration before exiting states:" << configuration; #endif - QList<QAbstractState*> exitedStates = computeExitSet(enabledTransitions); + QList<QAbstractState*> exitedStates = computeExitSet(enabledTransitions, cache); QHash<RestorableId, QVariant> pendingRestorables = computePendingRestorables(exitedStates); QSet<QAbstractState*> statesForDefaultEntry; - QList<QAbstractState*> enteredStates = computeEntrySet(enabledTransitions, statesForDefaultEntry); + QList<QAbstractState*> enteredStates = computeEntrySet(enabledTransitions, statesForDefaultEntry, cache); #ifdef QSTATEMACHINE_DEBUG qDebug() << q_func() << ": computed exit set:" << exitedStates; @@ -598,42 +710,61 @@ function computeExitSet(transitions) statesToExit.add(s) return statesToExit */ -QList<QAbstractState*> QStateMachinePrivate::computeExitSet(const QList<QAbstractTransition*> &enabledTransitions) +QList<QAbstractState*> QStateMachinePrivate::computeExitSet(const QList<QAbstractTransition*> &enabledTransitions, + CalculationCache *cache) { - QList<QAbstractState*> statesToExit_sorted = computeExitSet_Unordered(enabledTransitions).toList(); + Q_ASSERT(cache); + + QList<QAbstractState*> statesToExit_sorted = computeExitSet_Unordered(enabledTransitions, cache).toList(); std::sort(statesToExit_sorted.begin(), statesToExit_sorted.end(), stateExitLessThan); return statesToExit_sorted; } -QSet<QAbstractState*> QStateMachinePrivate::computeExitSet_Unordered(const QList<QAbstractTransition*> &enabledTransitions) +QSet<QAbstractState*> QStateMachinePrivate::computeExitSet_Unordered(const QList<QAbstractTransition*> &enabledTransitions, + CalculationCache *cache) { + Q_ASSERT(cache); + QSet<QAbstractState*> statesToExit; - for (int i = 0; i < enabledTransitions.size(); ++i) { - QAbstractTransition *t = enabledTransitions.at(i); - 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()); - - domain = findLCCA(lst); - Q_ASSERT(domain != 0); - } + foreach (QAbstractTransition *t, enabledTransitions) + statesToExit.unite(computeExitSet_Unordered(t, cache)); + return statesToExit; +} - foreach (QAbstractState* s, configuration) { - if (isDescendant(s, domain)) - statesToExit.insert(s); - } - } +QSet<QAbstractState*> QStateMachinePrivate::computeExitSet_Unordered(QAbstractTransition *t, + CalculationCache *cache) +{ + Q_ASSERT(cache); + + QSet<QAbstractState*> statesToExit; + if (cache->exitSet(t, &statesToExit)) + return statesToExit; + + QList<QAbstractState *> effectiveTargetStates = getEffectiveTargetStates(t, cache); + QAbstractState *domain = getTransitionDomain(t, effectiveTargetStates, cache); + 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()); + + domain = findLCCA(lst); + Q_ASSERT(domain != 0); + } + + foreach (QAbstractState* s, configuration) { + if (isDescendant(s, domain)) + statesToExit.insert(s); + } + + cache->insert(t, statesToExit); return statesToExit; } @@ -695,8 +826,11 @@ void QStateMachinePrivate::executeTransitionContent(QEvent *event, const QList<Q } QList<QAbstractState*> QStateMachinePrivate::computeEntrySet(const QList<QAbstractTransition *> &enabledTransitions, - QSet<QAbstractState *> &statesForDefaultEntry) + QSet<QAbstractState *> &statesForDefaultEntry, + CalculationCache *cache) { + Q_ASSERT(cache); + QSet<QAbstractState*> statesToEnter; if (pendingErrorStates.isEmpty()) { foreach (QAbstractTransition *t, enabledTransitions) { @@ -704,8 +838,8 @@ QList<QAbstractState*> QStateMachinePrivate::computeEntrySet(const QList<QAbstra addDescendantStatesToEnter(s, statesToEnter, statesForDefaultEntry); } - QList<QAbstractState *> effectiveTargetStates = getEffectiveTargetStates(t).toList(); - QAbstractState *ancestor = getTransitionDomain(t, effectiveTargetStates); + QList<QAbstractState *> effectiveTargetStates = getEffectiveTargetStates(t, cache); + QAbstractState *ancestor = getTransitionDomain(t, effectiveTargetStates, cache); foreach (QAbstractState *s, effectiveTargetStates) { addAncestorStatesToEnter(s, ancestor, statesToEnter, statesForDefaultEntry); } @@ -742,11 +876,19 @@ function getTransitionDomain(t) else: return findLCCA([t.source].append(tstates)) */ -QAbstractState *QStateMachinePrivate::getTransitionDomain(QAbstractTransition *t, const QList<QAbstractState *> &effectiveTargetStates) const +QAbstractState *QStateMachinePrivate::getTransitionDomain(QAbstractTransition *t, + const QList<QAbstractState *> &effectiveTargetStates, + CalculationCache *cache) const { + Q_ASSERT(cache); + if (effectiveTargetStates.isEmpty()) return 0; + QAbstractState *domain = Q_NULLPTR; + if (cache->transitionDomain(t, &domain)) + return domain; + #if 0 // Qt only has external transitions, so skip the special case for the internal transitions if (QState *tSource = t->sourceState()) { @@ -768,7 +910,9 @@ QAbstractState *QStateMachinePrivate::getTransitionDomain(QAbstractTransition *t QList<QAbstractState *> states(effectiveTargetStates); if (QAbstractState *src = t->sourceState()) states.prepend(src); - return findLCCA(states); + domain = findLCCA(states); + cache->insert(t, domain); + return domain; } void QStateMachinePrivate::enterStates(QEvent *event, const QList<QAbstractState*> &exitedStates_sorted, @@ -1683,6 +1827,7 @@ void QStateMachinePrivate::_q_start() processingScheduled = true; // we call _q_process() below QList<QAbstractTransition*> transitions; + CalculationCache calculationCache; QAbstractTransition *initialTransition = createInitialTransition(); transitions.append(initialTransition); @@ -1690,7 +1835,7 @@ void QStateMachinePrivate::_q_start() executeTransitionContent(&nullEvent, transitions); QList<QAbstractState*> exitedStates = QList<QAbstractState*>(); QSet<QAbstractState*> statesForDefaultEntry; - QList<QAbstractState*> enteredStates = computeEntrySet(transitions, statesForDefaultEntry); + QList<QAbstractState*> enteredStates = computeEntrySet(transitions, statesForDefaultEntry, &calculationCache); QHash<RestorableId, QVariant> pendingRestorables; QHash<QAbstractState*, QList<QPropertyAssignment> > assignmentsForEnteredStates = computePropertyAssignments(enteredStates, pendingRestorables); @@ -1743,8 +1888,10 @@ void QStateMachinePrivate::_q_process() break; } QList<QAbstractTransition*> enabledTransitions; + CalculationCache calculationCache; + QEvent *e = new QEvent(QEvent::None); - enabledTransitions = selectTransitions(e); + enabledTransitions = selectTransitions(e, &calculationCache); if (enabledTransitions.isEmpty()) { delete e; e = 0; @@ -1753,7 +1900,7 @@ void QStateMachinePrivate::_q_process() #ifdef QSTATEMACHINE_DEBUG qDebug() << q << ": dequeued internal event" << e << "of type" << e->type(); #endif - enabledTransitions = selectTransitions(e); + enabledTransitions = selectTransitions(e, &calculationCache); if (enabledTransitions.isEmpty()) { delete e; e = 0; @@ -1764,7 +1911,7 @@ void QStateMachinePrivate::_q_process() #ifdef QSTATEMACHINE_DEBUG qDebug() << q << ": dequeued external event" << e << "of type" << e->type(); #endif - enabledTransitions = selectTransitions(e); + enabledTransitions = selectTransitions(e, &calculationCache); if (enabledTransitions.isEmpty()) { delete e; e = 0; @@ -1778,7 +1925,7 @@ void QStateMachinePrivate::_q_process() } if (!enabledTransitions.isEmpty()) { q->beginMicrostep(e); - microstep(e, enabledTransitions); + microstep(e, enabledTransitions, &calculationCache); q->endMicrostep(e); } #ifdef QSTATEMACHINE_DEBUG diff --git a/src/corelib/statemachine/qstatemachine_p.h b/src/corelib/statemachine/qstatemachine_p.h index a88f95f1f5..28fd96f507 100644 --- a/src/corelib/statemachine/qstatemachine_p.h +++ b/src/corelib/statemachine/qstatemachine_p.h @@ -75,6 +75,7 @@ class QState; class QAbstractAnimation; #endif +struct CalculationCache; class QStateMachine; class Q_CORE_EXPORT QStateMachinePrivate : public QStatePrivate { @@ -124,13 +125,14 @@ public: void clearHistory(); QAbstractTransition *createInitialTransition() const; - void removeConflictingTransitions(QList<QAbstractTransition*> &enabledTransitions); - void microstep(QEvent *event, const QList<QAbstractTransition*> &transitionList); - QList<QAbstractTransition *> selectTransitions(QEvent *event); + void removeConflictingTransitions(QList<QAbstractTransition*> &enabledTransitions, CalculationCache *cache); + void microstep(QEvent *event, const QList<QAbstractTransition*> &transitionList, CalculationCache *cache); + QList<QAbstractTransition *> selectTransitions(QEvent *event, CalculationCache *cache); void exitStates(QEvent *event, const QList<QAbstractState *> &statesToExit_sorted, const QHash<QAbstractState*, QList<QPropertyAssignment> > &assignmentsForEnteredStates); - QList<QAbstractState*> computeExitSet(const QList<QAbstractTransition*> &enabledTransitions); - QSet<QAbstractState*> computeExitSet_Unordered(const QList<QAbstractTransition*> &enabledTransitions); + QList<QAbstractState*> computeExitSet(const QList<QAbstractTransition*> &enabledTransitions, CalculationCache *cache); + QSet<QAbstractState*> computeExitSet_Unordered(const QList<QAbstractTransition*> &enabledTransitions, CalculationCache *cache); + QSet<QAbstractState*> computeExitSet_Unordered(QAbstractTransition *t, CalculationCache *cache); void executeTransitionContent(QEvent *event, const QList<QAbstractTransition*> &transitionList); void enterStates(QEvent *event, const QList<QAbstractState*> &exitedStates_sorted, const QList<QAbstractState*> &statesToEnter_sorted, @@ -141,9 +143,10 @@ public: #endif ); QList<QAbstractState*> computeEntrySet(const QList<QAbstractTransition*> &enabledTransitions, - QSet<QAbstractState*> &statesForDefaultEntry); + QSet<QAbstractState*> &statesForDefaultEntry, CalculationCache *cache); QAbstractState *getTransitionDomain(QAbstractTransition *t, - const QList<QAbstractState *> &effectiveTargetStates) const; + const QList<QAbstractState *> &effectiveTargetStates, + CalculationCache *cache) const; void addDescendantStatesToEnter(QAbstractState *state, QSet<QAbstractState*> &statesToEnter, QSet<QAbstractState*> &statesForDefaultEntry); diff --git a/tests/auto/corelib/statemachine/qstatemachine/tst_qstatemachine.cpp b/tests/auto/corelib/statemachine/qstatemachine/tst_qstatemachine.cpp index 96d0a62f6b..9fb2e40cb8 100644 --- a/tests/auto/corelib/statemachine/qstatemachine/tst_qstatemachine.cpp +++ b/tests/auto/corelib/statemachine/qstatemachine/tst_qstatemachine.cpp @@ -256,10 +256,12 @@ public: Entry, Exit }; - TestState(QState *parent) - : QState(parent) {} - TestState(ChildMode mode) - : QState(mode) {} + TestState(QState *parent, const QString &objectName = QString()) + : QState(parent) + { setObjectName(objectName); } + TestState(ChildMode mode, const QString &objectName = QString()) + : QState(mode) + { setObjectName(objectName); } QList<QPair<int, Event> > events; protected: virtual void onEntry(QEvent *) { @@ -273,9 +275,9 @@ protected: class TestTransition : public QAbstractTransition { public: - TestTransition(QAbstractState *target) + TestTransition(QAbstractState *target, const QString &objectName = QString()) : QAbstractTransition() - { setTargetState(target); } + { setTargetState(target); setObjectName(objectName); } QList<int> triggers; protected: virtual bool eventTest(QEvent *) { @@ -1352,15 +1354,16 @@ void tst_QStateMachine::stateEntryAndExit() { QStateMachine machine; - TestState *s1 = new TestState(&machine); - TestState *s11 = new TestState(s1); - TestState *s12 = new TestState(s1); - TestState *s2 = new TestState(&machine); + TestState *s1 = new TestState(&machine, "s1"); + TestState *s11 = new TestState(s1, "s11"); + TestState *s12 = new TestState(s1, "s12"); + TestState *s2 = new TestState(&machine, "s2"); QFinalState *s3 = new QFinalState(&machine); + s3->setObjectName("s3"); s1->setInitialState(s11); - TestTransition *t1 = new TestTransition(s12); + TestTransition *t1 = new TestTransition(s12, "t1"); s11->addTransition(t1); - TestTransition *t2 = new TestTransition(s2); + TestTransition *t2 = new TestTransition(s2, "t2"); s12->addTransition(t2); s2->addTransition(s3); |