1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtCore module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qstatemachine.h"

    43 

    44 #ifndef QT_NO_STATEMACHINE

    45 

    46 #include "qstate.h"

    47 #include "qstate_p.h"

    48 #include "qstatemachine_p.h"

    49 #include "qabstracttransition.h"

    50 #include "qabstracttransition_p.h"

    51 #include "qsignaltransition.h"

    52 #include "qsignaltransition_p.h"

    53 #include "qsignaleventgenerator_p.h"

    54 #include "qabstractstate.h"

    55 #include "qabstractstate_p.h"

    56 #include "qfinalstate.h"

    57 #include "qhistorystate.h"

    58 #include "qhistorystate_p.h"

    59 #include "private/qobject_p.h"

    60 #include "private/qthread_p.h"

    61 

    62 #ifndef QT_NO_STATEMACHINE_EVENTFILTER

    63 #include "qeventtransition.h"

    64 #include "qeventtransition_p.h"

    65 #endif

    66 

    67 #ifndef QT_NO_ANIMATION

    68 #include "qpropertyanimation.h"

    69 #include "qanimationgroup.h"

    70 #include <private/qvariantanimation_p.h>

    71 #endif

    72 

    73 #include <QtCore/qmetaobject.h>

    74 #include <qdebug.h>

    75 

    76 QT_BEGIN_NAMESPACE

    77 

    78 /*!

    79     \class QStateMachine

    80     \reentrant

    81 

    82     \brief The QStateMachine class provides a hierarchical finite state machine.

    83 

    84     \since 4.6

    85     \ingroup statemachine

    86 

    87     QStateMachine is based on the concepts and notation of

    88     \l{Statecharts: A visual formalism for complex

    89     systems}{Statecharts}. QStateMachine is part of \l{The State

    90     Machine Framework}.

    91 

    92     A state machine manages a set of states (classes that inherit from

    93     QAbstractState) and transitions (descendants of

    94     QAbstractTransition) between those states; these states and

    95     transitions define a state graph. Once a state graph has been

    96     built, the state machine can execute it. QStateMachine's

    97     execution algorithm is based on the \l{State Chart XML: State

    98     Machine Notation for Control Abstraction}{State Chart XML (SCXML)}

    99     algorithm. The framework's \l{The State Machine

   100     Framework}{overview} gives several state graphs and the code to

   101     build them.

   102 

   103     Use the addState() function to add a top-level state to the state machine.

   104     States are removed with the removeState() function. Removing states while

   105     the machine is running is discouraged.

   106 

   107     Before the machine can be started, the \l{initialState}{initial

   108     state} must be set. The initial state is the state that the

   109     machine enters when started. You can then start() the state

   110     machine. The started() signal is emitted when the initial state is

   111     entered.

   112 

   113     The machine is event driven and keeps its own event loop. Events

   114     are posted to the machine through postEvent(). Note that this

   115     means that it executes asynchronously, and that it will not

   116     progress without a running event loop. You will normally not have

   117     to post events to the machine directly as Qt's transitions, e.g.,

   118     QEventTransition and its subclasses, handle this. But for custom

   119     transitions triggered by events, postEvent() is useful.

   120 

   121     The state machine processes events and takes transitions until a

   122     top-level final state is entered; the state machine then emits the

   123     finished() signal. You can also stop() the state machine

   124     explicitly. The stopped() signal is emitted in this case.

   125 

   126     The following snippet shows a state machine that will finish when a button

   127     is clicked:

   128 

   129     \snippet doc/src/snippets/code/src_corelib_statemachine_qstatemachine.cpp simple state machine

   130 

   131     This code example uses QState, which inherits QAbstractState. The

   132     QState class provides a state that you can use to set properties

   133     and invoke methods on \l{QObject}s when the state is entered or

   134     exited. It also contains convenience functions for adding

   135     transitions, e.g., \l{QSignalTransition}s as in this example. See

   136     the QState class description for further details.

   137 

   138     If an error is encountered, the machine will look for an

   139     \l{errorState}{error state}, and if one is available, it will

   140     enter this state. The types of errors possible are described by the

   141     \l{QStateMachine::}{Error} enum. After the error state is entered,

   142     the type of the error can be retrieved with error(). The execution

   143     of the state graph will not stop when the error state is entered. If 

   144     no error state applies to the erroneous state, the machine will stop 

   145     executing and an error message will be printed to the console.

   146 

   147     \sa QAbstractState, QAbstractTransition, QState, {The State Machine Framework}

   148 */

   149 

   150 /*!

   151     \property QStateMachine::errorString

   152 

   153     \brief the error string of this state machine

   154 */

   155 

   156 /*!

   157     \property QStateMachine::globalRestorePolicy

   158 

   159     \brief the restore policy for states of this state machine.

   160 

   161     The default value of this property is

   162     QStateMachine::DoNotRestoreProperties.

   163 */

   164 

   165 #ifndef QT_NO_ANIMATION

   166 /*!

   167     \property QStateMachine::animationsEnabled

   168 

   169     \brief whether animations are enabled

   170 

   171     The default value of this property is true.

   172 

   173     \sa QAbstractTransition::addAnimation()

   174 */

   175 #endif

   176 

   177 // #define QSTATEMACHINE_DEBUG

   178 

   179 QStateMachinePrivate::QStateMachinePrivate()

   180 {

   181     state = NotRunning;

   182     _startState = 0;

   183     processing = false;

   184     processingScheduled = false;

   185     stop = false;

   186     stopProcessingReason = EventQueueEmpty;

   187     error = QStateMachine::NoError;

   188     globalRestorePolicy = QStateMachine::DoNotRestoreProperties;

   189     signalEventGenerator = 0;

   190 #ifndef QT_NO_ANIMATION

   191     animationsEnabled = true;

   192 #endif

   193 }

   194 

   195 QStateMachinePrivate::~QStateMachinePrivate()

   196 {

   197     qDeleteAll(internalEventQueue);

   198     qDeleteAll(externalEventQueue);

   199 }

   200 

   201 QStateMachinePrivate *QStateMachinePrivate::get(QStateMachine *q)

   202 {

   203     if (q)

   204         return q->d_func();

   205     return 0;

   206 }

   207 

   208 QState *QStateMachinePrivate::rootState() const

   209 {

   210     return const_cast<QStateMachine*>(q_func());

   211 }

   212 

   213 static QEvent *cloneEvent(QEvent *e)

   214 {

   215     switch (e->type()) {

   216     case QEvent::None:

   217         return new QEvent(*e);

   218     case QEvent::Timer:

   219         return new QTimerEvent(*static_cast<QTimerEvent*>(e));

   220     default:

   221         Q_ASSERT_X(false, "cloneEvent()", "not implemented");

   222         break;

   223     }

   224     return 0;

   225 }

   226 

   227 const QStateMachinePrivate::Handler qt_kernel_statemachine_handler = {

   228     cloneEvent

   229 };

   230 

   231 const QStateMachinePrivate::Handler *QStateMachinePrivate::handler = &qt_kernel_statemachine_handler;

   232 

   233 Q_CORE_EXPORT const QStateMachinePrivate::Handler *qcoreStateMachineHandler()

   234 {

   235     return &qt_kernel_statemachine_handler;

   236 }

   237 

   238 static int indexOfDescendant(QState *s, QAbstractState *desc)

   239 {

   240     QList<QAbstractState*> childStates = QStatePrivate::get(s)->childStates();

   241     for (int i = 0; i < childStates.size(); ++i) {

   242         QAbstractState *c = childStates.at(i);

   243         if ((c == desc) || QStateMachinePrivate::isDescendantOf(desc, c)) {

   244             return i;

   245         }

   246     }

   247     return -1;

   248 }

   249 

   250 bool QStateMachinePrivate::stateEntryLessThan(QAbstractState *s1, QAbstractState *s2)

   251 {

   252     if (s1->parent() == s2->parent()) {

   253         return s1->children().indexOf(s1)

   254             < s2->children().indexOf(s2);

   255     } else if (isDescendantOf(s1, s2)) {

   256         return false;

   257     } else if (isDescendantOf(s2, s1)) {

   258         return true;

   259     } else {

   260         Q_ASSERT(s1->machine() != 0);

   261         QStateMachinePrivate *mach = QStateMachinePrivate::get(s1->machine());

   262         QState *lca = mach->findLCA(QList<QAbstractState*>() << s1 << s2);

   263         Q_ASSERT(lca != 0);

   264         return (indexOfDescendant(lca, s1) < indexOfDescendant(lca, s2));

   265     }

   266 }

   267 

   268 bool QStateMachinePrivate::stateExitLessThan(QAbstractState *s1, QAbstractState *s2)

   269 {

   270     if (s1->parent() == s2->parent()) {

   271         return s1->children().indexOf(s1)

   272             < s2->children().indexOf(s2);

   273     } else if (isDescendantOf(s1, s2)) {

   274         return true;

   275     } else if (isDescendantOf(s2, s1)) {

   276         return false;

   277     } else {

   278         Q_ASSERT(s1->machine() != 0);

   279         QStateMachinePrivate *mach = QStateMachinePrivate::get(s1->machine());

   280         QState *lca = mach->findLCA(QList<QAbstractState*>() << s1 << s2);

   281         Q_ASSERT(lca != 0);

   282         return (indexOfDescendant(lca, s1) < indexOfDescendant(lca, s2));

   283     }

   284 }

   285 

   286 QState *QStateMachinePrivate::findLCA(const QList<QAbstractState*> &states) const

   287 {

   288     if (states.isEmpty())

   289         return 0;

   290     QList<QState*> ancestors = properAncestors(states.at(0), rootState()->parentState());

   291     for (int i = 0; i < ancestors.size(); ++i) {

   292         QState *anc = ancestors.at(i);

   293         bool ok = true;

   294         for (int j = states.size() - 1; (j > 0) && ok; --j) {

   295             const QAbstractState *s = states.at(j);

   296             if (!isDescendantOf(s, anc))

   297                 ok = false;

   298         }

   299         if (ok)

   300             return anc;

   301     }

   302     return 0;

   303 }

   304 

   305 bool QStateMachinePrivate::isPreempted(const QAbstractState *s, const QSet<QAbstractTransition*> &transitions) const

   306 {

   307     QSet<QAbstractTransition*>::const_iterator it;

   308     for (it = transitions.constBegin(); it != transitions.constEnd(); ++it) {

   309         QAbstractTransition *t = *it;

   310         QList<QAbstractState*> lst = t->targetStates();

   311         if (!lst.isEmpty()) {

   312             lst.prepend(t->sourceState());

   313             QAbstractState *lca = findLCA(lst);

   314             if (isDescendantOf(s, lca)) {

   315 #ifdef QSTATEMACHINE_DEBUG

   316                 qDebug() << q_func() << ':' << transitions << "preempts selection of a transition from"

   317                          << s << "because" << s << "is a descendant of" << lca;

   318 #endif

   319                 return true;

   320             }

   321         }

   322     }

   323     return false;

   324 }

   325 

   326 QSet<QAbstractTransition*> QStateMachinePrivate::selectTransitions(QEvent *event) const

   327 {

   328     Q_Q(const QStateMachine);

   329     QSet<QAbstractTransition*> enabledTransitions;

   330     QSet<QAbstractState*>::const_iterator it;

   331     const_cast<QStateMachine*>(q)->beginSelectTransitions(event);

   332     for (it = configuration.constBegin(); it != configuration.constEnd(); ++it) {

   333         QAbstractState *state = *it;

   334         if (!isAtomic(state))

   335             continue;

   336         if (isPreempted(state, enabledTransitions))

   337             continue;

   338         QList<QState*> lst = properAncestors(state, rootState()->parentState());

   339         if (QState *grp = qobject_cast<QState*>(state))

   340             lst.prepend(grp);

   341         bool found = false;

   342         for (int j = 0; (j < lst.size()) && !found; ++j) {

   343             QState *s = lst.at(j);

   344             QList<QAbstractTransition*> transitions = QStatePrivate::get(s)->transitions();

   345             for (int k = 0; k < transitions.size(); ++k) {

   346                 QAbstractTransition *t = transitions.at(k);

   347                 if (QAbstractTransitionPrivate::get(t)->callEventTest(event)) {

   348 #ifdef QSTATEMACHINE_DEBUG

   349                     qDebug() << q << ": selecting transition" << t;

   350 #endif

   351                     enabledTransitions.insert(t);

   352                     found = true;

   353                     break;

   354                 }

   355             }

   356         }

   357     }

   358     const_cast<QStateMachine*>(q)->endSelectTransitions(event);

   359     return enabledTransitions;

   360 }

   361 

   362 void QStateMachinePrivate::microstep(QEvent *event, const QList<QAbstractTransition*> &enabledTransitions)

   363 {

   364 #ifdef QSTATEMACHINE_DEBUG

   365     qDebug() << q_func() << ": begin microstep( enabledTransitions:" << enabledTransitions << ')';

   366     qDebug() << q_func() << ": configuration before exiting states:" << configuration;

   367 #endif

   368     QList<QAbstractState*> exitedStates = exitStates(event, enabledTransitions);

   369 #ifdef QSTATEMACHINE_DEBUG

   370     qDebug() << q_func() << ": configuration after exiting states:" << configuration;

   371 #endif

   372     executeTransitionContent(event, enabledTransitions);

   373     QList<QAbstractState*> enteredStates = enterStates(event, enabledTransitions);

   374 #ifndef QT_NO_PROPERTIES

   375     applyProperties(enabledTransitions, exitedStates, enteredStates);

   376 #endif

   377 #ifdef QSTATEMACHINE_DEBUG

   378     qDebug() << q_func() << ": configuration after entering states:" << configuration;

   379     qDebug() << q_func() << ": end microstep";

   380 #endif

   381 }

   382 

   383 QList<QAbstractState*> QStateMachinePrivate::exitStates(QEvent *event, const QList<QAbstractTransition*> &enabledTransitions)

   384 {

   385 //    qDebug() << "exitStates(" << enabledTransitions << ')';

   386     QSet<QAbstractState*> statesToExit;

   387 //    QSet<QAbstractState*> statesToSnapshot;

   388     for (int i = 0; i < enabledTransitions.size(); ++i) {

   389         QAbstractTransition *t = enabledTransitions.at(i);

   390         QList<QAbstractState*> lst = t->targetStates();

   391         if (lst.isEmpty())

   392             continue;

   393         lst.prepend(t->sourceState());

   394         QAbstractState *lca = findLCA(lst);

   395         if (lca == 0) {

   396             setError(QStateMachine::NoCommonAncestorForTransitionError, t->sourceState());

   397             lst = pendingErrorStates.toList();

   398             lst.prepend(t->sourceState());

   399             

   400             lca = findLCA(lst);

   401             Q_ASSERT(lca != 0);

   402         }

   403 

   404         {

   405             QSet<QAbstractState*>::const_iterator it;

   406             for (it = configuration.constBegin(); it != configuration.constEnd(); ++it) {

   407                 QAbstractState *s = *it;

   408                 if (isDescendantOf(s, lca))

   409                     statesToExit.insert(s);

   410             }

   411         }

   412     }

   413     QList<QAbstractState*> statesToExit_sorted = statesToExit.toList();

   414     qSort(statesToExit_sorted.begin(), statesToExit_sorted.end(), stateExitLessThan);

   415     for (int i = 0; i < statesToExit_sorted.size(); ++i) {

   416         QAbstractState *s = statesToExit_sorted.at(i);

   417         if (QState *grp = qobject_cast<QState*>(s)) {

   418             QList<QHistoryState*> hlst = QStatePrivate::get(grp)->historyStates();

   419             for (int j = 0; j < hlst.size(); ++j) {

   420                 QHistoryState *h = hlst.at(j);

   421                 QHistoryStatePrivate::get(h)->configuration.clear();

   422                 QSet<QAbstractState*>::const_iterator it;

   423                 for (it = configuration.constBegin(); it != configuration.constEnd(); ++it) {

   424                     QAbstractState *s0 = *it;

   425                     if (QHistoryStatePrivate::get(h)->historyType == QHistoryState::DeepHistory) {

   426                         if (isAtomic(s0) && isDescendantOf(s0, s))

   427                             QHistoryStatePrivate::get(h)->configuration.append(s0);

   428                     } else if (s0->parentState() == s) {

   429                         QHistoryStatePrivate::get(h)->configuration.append(s0);

   430                     }

   431                 }

   432 #ifdef QSTATEMACHINE_DEBUG

   433                 qDebug() << q_func() << ": recorded" << ((QHistoryStatePrivate::get(h)->historyType == QHistoryState::DeepHistory) ? "deep" : "shallow")

   434                          << "history for" << s << "in" << h << ':' << QHistoryStatePrivate::get(h)->configuration;

   435 #endif

   436             }

   437         }

   438     }

   439     for (int i = 0; i < statesToExit_sorted.size(); ++i) {

   440         QAbstractState *s = statesToExit_sorted.at(i);

   441 #ifdef QSTATEMACHINE_DEBUG

   442         qDebug() << q_func() << ": exiting" << s;

   443 #endif

   444         QAbstractStatePrivate::get(s)->callOnExit(event);

   445         configuration.remove(s);

   446         QAbstractStatePrivate::get(s)->emitExited();

   447     }

   448     return statesToExit_sorted;

   449 }

   450 

   451 void QStateMachinePrivate::executeTransitionContent(QEvent *event, const QList<QAbstractTransition*> &enabledTransitions)

   452 {

   453     for (int i = 0; i < enabledTransitions.size(); ++i) {

   454         QAbstractTransition *t = enabledTransitions.at(i);

   455 #ifdef QSTATEMACHINE_DEBUG

   456         qDebug() << q_func() << ": triggering" << t;

   457 #endif

   458         QAbstractTransitionPrivate::get(t)->callOnTransition(event);

   459         QAbstractTransitionPrivate::get(t)->emitTriggered();

   460     }

   461 }

   462 

   463 QList<QAbstractState*> QStateMachinePrivate::enterStates(QEvent *event, const QList<QAbstractTransition*> &enabledTransitions)

   464 {

   465 #ifdef QSTATEMACHINE_DEBUG

   466     Q_Q(QStateMachine);

   467 #endif

   468 //    qDebug() << "enterStates(" << enabledTransitions << ')';

   469     QSet<QAbstractState*> statesToEnter;

   470     QSet<QAbstractState*> statesForDefaultEntry;

   471 

   472     if (pendingErrorStates.isEmpty()) {

   473         for (int i = 0; i < enabledTransitions.size(); ++i) {

   474             QAbstractTransition *t = enabledTransitions.at(i);

   475             QList<QAbstractState*> lst = t->targetStates();

   476             if (lst.isEmpty())

   477                 continue;

   478             lst.prepend(t->sourceState());

   479             QState *lca = findLCA(lst);

   480             for (int j = 1; j < lst.size(); ++j) {

   481                 QAbstractState *s = lst.at(j);

   482 			    addStatesToEnter(s, lca, statesToEnter, statesForDefaultEntry);

   483                 if (isParallel(lca)) {

   484                     QList<QAbstractState*> lcac = QStatePrivate::get(lca)->childStates();

   485                     foreach (QAbstractState* child,lcac) {

   486                         if (!statesToEnter.contains(child))

   487                             addStatesToEnter(child,lca,statesToEnter,statesForDefaultEntry);                    

   488                     }

   489                 }

   490             }

   491         }

   492     }

   493 

   494     // Did an error occur while selecting transitions? Then we enter the error state.

   495     if (!pendingErrorStates.isEmpty()) {

   496         statesToEnter.clear();

   497         statesToEnter = pendingErrorStates;

   498         statesForDefaultEntry = pendingErrorStatesForDefaultEntry;

   499         pendingErrorStates.clear();

   500         pendingErrorStatesForDefaultEntry.clear();

   501     }

   502 

   503     QList<QAbstractState*> statesToEnter_sorted = statesToEnter.toList();

   504     qSort(statesToEnter_sorted.begin(), statesToEnter_sorted.end(), stateEntryLessThan);

   505 

   506     for (int i = 0; i < statesToEnter_sorted.size(); ++i) {

   507         QAbstractState *s = statesToEnter_sorted.at(i);

   508 #ifdef QSTATEMACHINE_DEBUG

   509         qDebug() << q << ": entering" << s;

   510 #endif

   511         configuration.insert(s);

   512         registerTransitions(s);

   513         QAbstractStatePrivate::get(s)->callOnEntry(event);

   514         QAbstractStatePrivate::get(s)->emitEntered();

   515         if (statesForDefaultEntry.contains(s)) {

   516             // ### executeContent(s.initial.transition.children())

   517         }

   518         if (isFinal(s)) {

   519             QState *parent = s->parentState();

   520             if (parent) {

   521                 if (parent != rootState()) {

   522 #ifdef QSTATEMACHINE_DEBUG

   523                     qDebug() << q << ": emitting finished signal for" << parent;

   524 #endif

   525                     QStatePrivate::get(parent)->emitFinished();

   526                 }

   527                 QState *grandparent = parent->parentState();

   528                 if (grandparent && isParallel(grandparent)) {

   529                     bool allChildStatesFinal = true;

   530                     QList<QAbstractState*> childStates = QStatePrivate::get(grandparent)->childStates();

   531                     for (int j = 0; j < childStates.size(); ++j) {

   532                         QAbstractState *cs = childStates.at(j);

   533                         if (!isInFinalState(cs)) {

   534                             allChildStatesFinal = false;

   535                             break;

   536                         }

   537                     }

   538                     if (allChildStatesFinal && (grandparent != rootState())) {

   539 #ifdef QSTATEMACHINE_DEBUG

   540                         qDebug() << q << ": emitting finished signal for" << grandparent;

   541 #endif

   542                         QStatePrivate::get(grandparent)->emitFinished();

   543                     }

   544                 }

   545             }

   546         }

   547     }

   548     {

   549         QSet<QAbstractState*>::const_iterator it;

   550         for (it = configuration.constBegin(); it != configuration.constEnd(); ++it) {

   551             if (isFinal(*it) && (*it)->parentState() == rootState()) {

   552                 processing = false;

   553                 stopProcessingReason = Finished;

   554                 break;

   555             }

   556         }

   557     }

   558 //    qDebug() << "configuration:" << configuration.toList();

   559     return statesToEnter_sorted;

   560 }

   561 

   562 void QStateMachinePrivate::addStatesToEnter(QAbstractState *s, QState *root,

   563                                             QSet<QAbstractState*> &statesToEnter,

   564                                             QSet<QAbstractState*> &statesForDefaultEntry)

   565 {

   566 	if (QHistoryState *h = qobject_cast<QHistoryState*>(s)) {

   567 		QList<QAbstractState*> hconf = QHistoryStatePrivate::get(h)->configuration;

   568 		if (!hconf.isEmpty()) {

   569 			for (int k = 0; k < hconf.size(); ++k) {

   570 				QAbstractState *s0 = hconf.at(k);

   571 				addStatesToEnter(s0, root, statesToEnter, statesForDefaultEntry);

   572 			}

   573 	#ifdef QSTATEMACHINE_DEBUG

   574 			qDebug() <<q_func() << ": restoring"

   575 					<< ((QHistoryStatePrivate::get(h)->historyType == QHistoryState::DeepHistory) ? "deep" : "shallow")

   576 					<< "history from" << s << ':' << hconf;

   577 	#endif

   578 		} else {

   579 			QList<QAbstractState*> hlst;

   580 			if (QHistoryStatePrivate::get(h)->defaultState)

   581 				hlst.append(QHistoryStatePrivate::get(h)->defaultState);

   582 

   583 			if (hlst.isEmpty()) {

   584 				setError(QStateMachine::NoDefaultStateInHistoryStateError, h);

   585 			} else {

   586 				for (int k = 0; k < hlst.size(); ++k) {

   587 					QAbstractState *s0 = hlst.at(k);

   588 					addStatesToEnter(s0, root, statesToEnter, statesForDefaultEntry);

   589 				}

   590 	#ifdef QSTATEMACHINE_DEBUG

   591 				qDebug() << q_func() << ": initial history targets for" << s << ':' << hlst;

   592 	#endif

   593 			}

   594 		}

   595 	} else {

   596             if (s == rootState()) {

   597                 // Error has already been set by exitStates().

   598                 Q_ASSERT(error != QStateMachine::NoError);

   599                 return;

   600             }

   601 		statesToEnter.insert(s);

   602 		if (isParallel(s)) {

   603 			QState *grp = qobject_cast<QState*>(s);

   604 			QList<QAbstractState*> lst = QStatePrivate::get(grp)->childStates();

   605 			for (int i = 0; i < lst.size(); ++i) {

   606 				QAbstractState *child = lst.at(i);

   607 				addStatesToEnter(child, grp, statesToEnter, statesForDefaultEntry);

   608 			}

   609 		} else if (isCompound(s)) {

   610 			statesForDefaultEntry.insert(s);

   611 			QState *grp = qobject_cast<QState*>(s);

   612 			QAbstractState *initial = grp->initialState();

   613 			if (initial != 0) {

   614                             Q_ASSERT(initial->machine() == q_func());

   615 				addStatesToEnter(initial, grp, statesToEnter, statesForDefaultEntry);

   616 			} else {

   617 				setError(QStateMachine::NoInitialStateError, grp);

   618 				return;

   619 			}

   620 		}

   621 		QList<QState*> ancs = properAncestors(s, root);

   622 		for (int i = 0; i < ancs.size(); ++i) {

   623 			QState *anc = ancs.at(i);

   624 			if (!anc->parentState())

   625 				continue;

   626 			statesToEnter.insert(anc);

   627 			if (isParallel(anc)) {

   628 				QList<QAbstractState*> lst = QStatePrivate::get(anc)->childStates();

   629 				for (int j = 0; j < lst.size(); ++j) {

   630 					QAbstractState *child = lst.at(j);

   631 					bool hasDescendantInList = false;

   632 					QSet<QAbstractState*>::const_iterator it;

   633 					for (it = statesToEnter.constBegin(); it != statesToEnter.constEnd(); ++it) {

   634 						if (isDescendantOf(*it, child)) {

   635 							hasDescendantInList = true;

   636 							break;

   637 						}

   638 					}

   639 					if (!hasDescendantInList)

   640 						addStatesToEnter(child, anc, statesToEnter, statesForDefaultEntry);

   641 				}

   642 			}

   643 		}

   644 	}

   645 }

   646 

   647 #ifndef QT_NO_PROPERTIES

   648 

   649 void QStateMachinePrivate::applyProperties(const QList<QAbstractTransition*> &transitionList,

   650                                            const QList<QAbstractState*> &exitedStates,

   651                                            const QList<QAbstractState*> &enteredStates)

   652 {

   653 #ifdef QT_NO_ANIMATION

   654     Q_UNUSED(transitionList);

   655     Q_UNUSED(exitedStates);

   656 #else

   657     Q_Q(QStateMachine);

   658 #endif

   659     // Process the property assignments of the entered states.

   660     QHash<QAbstractState*, QList<QPropertyAssignment> > propertyAssignmentsForState;

   661     QHash<RestorableId, QVariant> pendingRestorables = registeredRestorables;

   662     for (int i = 0; i < enteredStates.size(); ++i) {

   663         QState *s = qobject_cast<QState*>(enteredStates.at(i));

   664         if (!s)

   665             continue;

   666 

   667         QList<QPropertyAssignment> assignments = QStatePrivate::get(s)->propertyAssignments;

   668         for (int j = 0; j < assignments.size(); ++j) {

   669             const QPropertyAssignment &assn = assignments.at(j);

   670             if (globalRestorePolicy == QStateMachine::RestoreProperties) {

   671                 registerRestorable(assn.object, assn.propertyName);

   672             }

   673             pendingRestorables.remove(RestorableId(assn.object, assn.propertyName));

   674             propertyAssignmentsForState[s].append(assn);

   675         }

   676 

   677         // Remove pending restorables for all parent states to avoid restoring properties

   678         // before the state that assigned them is exited. If state does not explicitly 

   679         // assign a property which is assigned by the parent, it inherits the parent's assignment.

   680         QState *parentState = s;

   681         while ((parentState = parentState->parentState()) != 0) {

   682             assignments = QStatePrivate::get(parentState)->propertyAssignments;

   683             for (int j=0; j<assignments.size(); ++j) {

   684                 const QPropertyAssignment &assn = assignments.at(j);

   685                 int c = pendingRestorables.remove(RestorableId(assn.object, assn.propertyName));

   686                 if (c > 0)

   687                     propertyAssignmentsForState[s].append(assn);                

   688             }

   689         }

   690     }

   691     if (!pendingRestorables.isEmpty()) {

   692         QAbstractState *s;

   693         if (!enteredStates.isEmpty())

   694             s = enteredStates.last(); // ### handle if parallel

   695         else

   696             s = 0;

   697         propertyAssignmentsForState[s] << restorablesToPropertyList(pendingRestorables);

   698     }

   699 

   700 #ifndef QT_NO_ANIMATION

   701     // Gracefully terminate playing animations for states that are exited.

   702     for (int i = 0; i < exitedStates.size(); ++i) {

   703         QAbstractState *s = exitedStates.at(i);

   704         QList<QAbstractAnimation*> animations = animationsForState.take(s);

   705         for (int j = 0; j < animations.size(); ++j) {

   706             QAbstractAnimation *anim = animations.at(j);

   707             QObject::disconnect(anim, SIGNAL(finished()), q, SLOT(_q_animationFinished()));

   708             stateForAnimation.remove(anim);

   709 

   710             // Stop the (top-level) animation.

   711             // ### Stopping nested animation has weird behavior.

   712             QAbstractAnimation *topLevelAnim = anim;

   713             while (QAnimationGroup *group = topLevelAnim->group())

   714                 topLevelAnim = group;

   715             topLevelAnim->stop();

   716 

   717             if (resetAnimationEndValues.contains(anim)) {

   718                 qobject_cast<QVariantAnimation*>(anim)->setEndValue(QVariant()); // ### generalize

   719                 resetAnimationEndValues.remove(anim);

   720             }

   721             QPropertyAssignment assn = propertyForAnimation.take(anim);

   722             Q_ASSERT(assn.object != 0);

   723             // If there is no property assignment that sets this property,

   724             // set the property to its target value.

   725             bool found = false;

   726             QHash<QAbstractState*, QList<QPropertyAssignment> >::const_iterator it;

   727             for (it = propertyAssignmentsForState.constBegin(); it != propertyAssignmentsForState.constEnd(); ++it) {

   728                 const QList<QPropertyAssignment> &assignments = it.value();

   729                 for (int k = 0; k < assignments.size(); ++k) {

   730                     if ((assignments.at(k).object == assn.object)

   731                         && (assignments.at(k).propertyName == assn.propertyName)) {

   732                         found = true;

   733                         break;

   734                     }

   735                 }

   736             }

   737             if (!found) {

   738                 assn.object->setProperty(assn.propertyName, assn.value);

   739             }

   740         }

   741     }

   742 

   743     // Find the animations to use for the state change.

   744     QList<QAbstractAnimation*> selectedAnimations;

   745     if (animationsEnabled) {

   746         for (int i = 0; i < transitionList.size(); ++i) {

   747             QAbstractTransition *transition = transitionList.at(i);

   748 

   749             selectedAnimations << transition->animations();

   750             selectedAnimations << defaultAnimationsForSource.values(transition->sourceState());

   751 

   752             QList<QAbstractState *> targetStates = transition->targetStates();

   753             for (int j=0; j<targetStates.size(); ++j) 

   754                 selectedAnimations << defaultAnimationsForTarget.values(targetStates.at(j));

   755         }

   756         selectedAnimations << defaultAnimations;

   757     }

   758 

   759     // Initialize animations from property assignments.

   760     for (int i = 0; i < selectedAnimations.size(); ++i) {

   761         QAbstractAnimation *anim = selectedAnimations.at(i);

   762         QHash<QAbstractState*, QList<QPropertyAssignment> >::iterator it;

   763         for (it = propertyAssignmentsForState.begin(); it != propertyAssignmentsForState.end(); ) {

   764             QList<QPropertyAssignment>::iterator it2;

   765             QAbstractState *s = it.key();

   766             QList<QPropertyAssignment> &assignments = it.value();

   767             for (it2 = assignments.begin(); it2 != assignments.end(); ) {

   768                 QPair<QList<QAbstractAnimation*>, QList<QAbstractAnimation*> > ret;

   769                 ret = initializeAnimation(anim, *it2);

   770                 QList<QAbstractAnimation*> handlers = ret.first;

   771                 if (!handlers.isEmpty()) {

   772                     for (int j = 0; j < handlers.size(); ++j) {

   773                         QAbstractAnimation *a = handlers.at(j);

   774                         propertyForAnimation.insert(a, *it2);

   775                         stateForAnimation.insert(a, s);

   776                         animationsForState[s].append(a);

   777                         // ### connect to just the top-level animation?

   778                         QObject::connect(a, SIGNAL(finished()), q, SLOT(_q_animationFinished()), Qt::UniqueConnection);

   779                     }

   780                     it2 = assignments.erase(it2);

   781                 } else {

   782                     ++it2;

   783                 }

   784                 for (int j = 0; j < ret.second.size(); ++j)

   785                     resetAnimationEndValues.insert(ret.second.at(j));

   786             }

   787             if (assignments.isEmpty())

   788                 it = propertyAssignmentsForState.erase(it);

   789             else

   790                 ++it;

   791         }

   792         // We require that at least one animation is valid.

   793         // ### generalize

   794         QList<QVariantAnimation*> variantAnims = qFindChildren<QVariantAnimation*>(anim);

   795         if (QVariantAnimation *va = qobject_cast<QVariantAnimation*>(anim))

   796             variantAnims.append(va);

   797         

   798         bool hasValidEndValue = false;

   799         for (int j = 0; j < variantAnims.size(); ++j) {

   800             if (variantAnims.at(j)->endValue().isValid()) {

   801                 hasValidEndValue = true;

   802                 break;

   803             }

   804         }

   805 

   806         if (hasValidEndValue) {

   807             if (anim->state() == QAbstractAnimation::Running) {

   808                 // The animation is still running. This can happen if the

   809                 // animation is a group, and one of its children just finished,

   810                 // and that caused a state to emit its polished() signal, and

   811                 // that triggered a transition in the machine.

   812                 // Just stop the animation so it is correctly restarted again.

   813                 anim->stop();

   814             }

   815             anim->start();

   816         }

   817     }

   818 #endif // !QT_NO_ANIMATION

   819 

   820     // Immediately set the properties that are not animated.

   821     {

   822         QHash<QAbstractState*, QList<QPropertyAssignment> >::const_iterator it;

   823         for (it = propertyAssignmentsForState.constBegin(); it != propertyAssignmentsForState.constEnd(); ++it) {

   824             const QList<QPropertyAssignment> &assignments = it.value();

   825             for (int i = 0; i < assignments.size(); ++i) {

   826                 const QPropertyAssignment &assn = assignments.at(i);

   827                 assn.object->setProperty(assn.propertyName, assn.value);

   828             }

   829         }

   830     }

   831 

   832     // Emit polished signal for entered states that have no animated properties.

   833     for (int i = 0; i < enteredStates.size(); ++i) {

   834         QState *s = qobject_cast<QState*>(enteredStates.at(i));

   835         if (s 

   836 #ifndef QT_NO_ANIMATION

   837             && !animationsForState.contains(s)

   838 #endif

   839             )

   840             QStatePrivate::get(s)->emitPolished();

   841     }

   842 }

   843 

   844 #endif // QT_NO_PROPERTIES

   845 

   846 bool QStateMachinePrivate::isFinal(const QAbstractState *s)

   847 {

   848     return qobject_cast<const QFinalState*>(s) != 0;

   849 }

   850 

   851 bool QStateMachinePrivate::isParallel(const QAbstractState *s)

   852 {

   853     const QState *ss = qobject_cast<const QState*>(s);

   854     return ss && (QStatePrivate::get(ss)->childMode == QState::ParallelStates);

   855 }

   856 

   857 bool QStateMachinePrivate::isCompound(const QAbstractState *s) const

   858 {

   859     const QState *group = qobject_cast<const QState*>(s);

   860     if (!group)

   861         return false;

   862     bool isMachine = (qobject_cast<const QStateMachine*>(group) != 0);

   863     // Don't treat the machine as compound if it's a sub-state of this machine

   864     if (isMachine && (group != rootState()))

   865         return false;

   866     return (!isParallel(group) && !QStatePrivate::get(group)->childStates().isEmpty())

   867         || isMachine;

   868 }

   869 

   870 bool QStateMachinePrivate::isAtomic(const QAbstractState *s) const

   871 {

   872     const QState *ss = qobject_cast<const QState*>(s);

   873     return (ss && QStatePrivate::get(ss)->childStates().isEmpty())

   874         || isFinal(s)

   875         // Treat the machine as atomic if it's a sub-state of this machine

   876         || (ss && (qobject_cast<const QStateMachine*>(ss) != 0) && (ss != rootState()));

   877 }

   878 

   879 

   880 bool QStateMachinePrivate::isDescendantOf(const QAbstractState *state, const QAbstractState *other)

   881 {

   882     Q_ASSERT(state != 0);

   883     for (QAbstractState *s = state->parentState(); s != 0; s = s->parentState()) {

   884         if (s == other)

   885             return true;

   886     }

   887     return false;

   888 }

   889 

   890 QList<QState*> QStateMachinePrivate::properAncestors(const QAbstractState *state, const QState *upperBound)

   891 {

   892     Q_ASSERT(state != 0);

   893     QList<QState*> result;

   894     for (QState *s = state->parentState(); s && s != upperBound; s = s->parentState()) {

   895         result.append(s);

   896     }

   897     return result;

   898 }

   899 

   900 bool QStateMachinePrivate::isInFinalState(QAbstractState* s) const

   901 {

   902     if (isCompound(s)) {

   903         QState *grp = qobject_cast<QState*>(s);

   904         QList<QAbstractState*> lst = QStatePrivate::get(grp)->childStates();

   905         for (int i = 0; i < lst.size(); ++i) {

   906             QAbstractState *cs = lst.at(i);

   907             if (isFinal(cs) && configuration.contains(cs))

   908                 return true;

   909         }

   910         return false;

   911     } else if (isParallel(s)) {

   912         QState *grp = qobject_cast<QState*>(s);

   913         QList<QAbstractState*> lst = QStatePrivate::get(grp)->childStates();

   914         for (int i = 0; i < lst.size(); ++i) {

   915             QAbstractState *cs = lst.at(i);

   916             if (!isInFinalState(cs))

   917                 return false;

   918         }

   919         return true;

   920     }

   921     else

   922         return false;

   923 }

   924 

   925 #ifndef QT_NO_PROPERTIES

   926 

   927 void QStateMachinePrivate::registerRestorable(QObject *object, const QByteArray &propertyName)

   928 {

   929     RestorableId id(object, propertyName);

   930     if (!registeredRestorables.contains(id))

   931         registeredRestorables.insert(id, object->property(propertyName));

   932 }

   933 

   934 QList<QPropertyAssignment> QStateMachinePrivate::restorablesToPropertyList(const QHash<RestorableId, QVariant> &restorables) const

   935 {

   936     QList<QPropertyAssignment> result;

   937     QHash<RestorableId, QVariant>::const_iterator it;

   938     for (it = restorables.constBegin(); it != restorables.constEnd(); ++it) {

   939 //        qDebug() << "restorable:" << it.key().first << it.key().second << it.value();

   940         result.append(QPropertyAssignment(it.key().first, it.key().second, it.value(), /*explicitlySet=*/false));

   941     }

   942     return result;

   943 }

   944 

   945 /*! 

   946    \internal

   947    Returns true if the variable with the given \a id has been registered for restoration.

   948 */

   949 bool QStateMachinePrivate::hasRestorable(QObject *object, const QByteArray &propertyName) const

   950 {

   951     return registeredRestorables.contains(RestorableId(object, propertyName));

   952 }

   953 

   954 QVariant QStateMachinePrivate::restorableValue(QObject *object, const QByteArray &propertyName) const

   955 {

   956     return registeredRestorables.value(RestorableId(object, propertyName), QVariant());

   957 }

   958 

   959 

   960 /*!

   961    \internal

   962     Unregisters the variable identified by \a id

   963 */

   964 void QStateMachinePrivate::unregisterRestorable(QObject *object, const QByteArray &propertyName)

   965 {

   966 //    qDebug() << "unregisterRestorable(" << object << propertyName << ')';

   967     RestorableId id(object, propertyName);

   968     registeredRestorables.remove(id);

   969 }

   970 

   971 #endif // QT_NO_PROPERTIES

   972 

   973 QAbstractState *QStateMachinePrivate::findErrorState(QAbstractState *context)

   974 {

   975     // Find error state recursively in parent hierarchy if not set explicitly for context state

   976     QAbstractState *errorState = 0;

   977     if (context != 0) {

   978         QState *s = qobject_cast<QState*>(context);

   979         if (s != 0)

   980             errorState = s->errorState();

   981 

   982         if (errorState == 0)

   983             errorState = findErrorState(context->parentState());

   984     }

   985     

   986     return errorState;   

   987 }

   988 

   989 void QStateMachinePrivate::setError(QStateMachine::Error errorCode, QAbstractState *currentContext)

   990 {

   991     Q_Q(QStateMachine);

   992     

   993     error = errorCode;

   994     switch (errorCode) {

   995     case QStateMachine::NoInitialStateError:        

   996         Q_ASSERT(currentContext != 0);

   997 

   998         errorString = QStateMachine::tr("Missing initial state in compound state '%1'")

   999                         .arg(currentContext->objectName());

  1000 

  1001         break;

  1002     case QStateMachine::NoDefaultStateInHistoryStateError:

  1003         Q_ASSERT(currentContext != 0);

  1004 

  1005         errorString = QStateMachine::tr("Missing default state in history state '%1'")

  1006                         .arg(currentContext->objectName());

  1007         break;

  1008 

  1009     case QStateMachine::NoCommonAncestorForTransitionError:

  1010         Q_ASSERT(currentContext != 0);

  1011 

  1012         errorString = QStateMachine::tr("No common ancestor for targets and source of transition from state '%1'")

  1013                         .arg(currentContext->objectName());

  1014         break;

  1015     default:

  1016         errorString = QStateMachine::tr("Unknown error");

  1017     };

  1018 

  1019     pendingErrorStates.clear(); 

  1020     pendingErrorStatesForDefaultEntry.clear();

  1021 

  1022     QAbstractState *currentErrorState = findErrorState(currentContext);

  1023 

  1024     // Avoid infinite loop if the error state itself has an error

  1025     if (currentContext == currentErrorState)

  1026         currentErrorState = 0;    

  1027 

  1028     Q_ASSERT(currentErrorState != rootState());

  1029 

  1030     if (currentErrorState != 0) {    

  1031         QState *lca = findLCA(QList<QAbstractState*>() << currentErrorState << currentContext);

  1032         addStatesToEnter(currentErrorState, lca, pendingErrorStates, pendingErrorStatesForDefaultEntry);

  1033     } else {

  1034         qWarning("Unrecoverable error detected in running state machine: %s", 

  1035                  qPrintable(errorString));

  1036         q->stop();

  1037     }

  1038 }

  1039 

  1040 #ifndef QT_NO_ANIMATION

  1041 

  1042 QPair<QList<QAbstractAnimation*>, QList<QAbstractAnimation*> >

  1043 QStateMachinePrivate::initializeAnimation(QAbstractAnimation *abstractAnimation, 

  1044                                           const QPropertyAssignment &prop)

  1045 {

  1046     QList<QAbstractAnimation*> handledAnimations;

  1047     QList<QAbstractAnimation*> localResetEndValues;

  1048     QAnimationGroup *group = qobject_cast<QAnimationGroup*>(abstractAnimation);

  1049     if (group) {

  1050         for (int i = 0; i < group->animationCount(); ++i) {

  1051             QAbstractAnimation *animationChild = group->animationAt(i);

  1052             QPair<QList<QAbstractAnimation*>, QList<QAbstractAnimation*> > ret;

  1053             ret = initializeAnimation(animationChild, prop);

  1054             handledAnimations << ret.first;

  1055             localResetEndValues << ret.second;

  1056         }

  1057     } else { 

  1058         QPropertyAnimation *animation = qobject_cast<QPropertyAnimation *>(abstractAnimation);

  1059         if (animation != 0 

  1060             && prop.object == animation->targetObject()

  1061             && prop.propertyName == animation->propertyName()) {

  1062 

  1063             // Only change end value if it is undefined

  1064             if (!animation->endValue().isValid()) {

  1065                 animation->setEndValue(prop.value);

  1066                 localResetEndValues.append(animation);

  1067             }

  1068             handledAnimations.append(animation);

  1069         }

  1070     }

  1071     return qMakePair(handledAnimations, localResetEndValues);

  1072 }

  1073 

  1074 void QStateMachinePrivate::_q_animationFinished()

  1075 {

  1076     Q_Q(QStateMachine);

  1077     QAbstractAnimation *anim = qobject_cast<QAbstractAnimation*>(q->sender());

  1078     Q_ASSERT(anim != 0);

  1079     QObject::disconnect(anim, SIGNAL(finished()), q, SLOT(_q_animationFinished()));

  1080     if (resetAnimationEndValues.contains(anim)) {

  1081         qobject_cast<QVariantAnimation*>(anim)->setEndValue(QVariant()); // ### generalize

  1082         resetAnimationEndValues.remove(anim);

  1083     }

  1084 

  1085 #ifndef QT_NO_PROPERTIES

  1086     // Set the final property value.

  1087     QPropertyAssignment assn = propertyForAnimation.take(anim);

  1088     Q_ASSERT(assn.object != 0);

  1089     assn.object->setProperty(assn.propertyName, assn.value);

  1090     if (!assn.explicitlySet)

  1091         unregisterRestorable(assn.object, assn.propertyName);

  1092 #endif

  1093 

  1094     QAbstractState *state = stateForAnimation.take(anim);

  1095     Q_ASSERT(state != 0);

  1096     QHash<QAbstractState*, QList<QAbstractAnimation*> >::iterator it;

  1097     it = animationsForState.find(state);

  1098     Q_ASSERT(it != animationsForState.end());

  1099     QList<QAbstractAnimation*> &animations = it.value();

  1100     animations.removeOne(anim);

  1101     if (animations.isEmpty()) {

  1102         animationsForState.erase(it);

  1103         QStatePrivate::get(qobject_cast<QState*>(state))->emitPolished();

  1104     }

  1105 }

  1106 

  1107 #endif // !QT_NO_ANIMATION

  1108 

  1109 namespace {

  1110 

  1111 class StartState : public QState

  1112 {

  1113 public:

  1114     StartState(QState *parent)

  1115         : QState(parent) {}

  1116 protected:

  1117     void onEntry(QEvent *) {}

  1118     void onExit(QEvent *) {}

  1119 };

  1120 

  1121 class InitialTransition : public QAbstractTransition

  1122 {

  1123 public:

  1124     InitialTransition(QAbstractState *target)

  1125         : QAbstractTransition()

  1126     { setTargetState(target); }

  1127 protected:

  1128     virtual bool eventTest(QEvent *) { return true; }

  1129     virtual void onTransition(QEvent *) {}

  1130 };

  1131 

  1132 } // namespace

  1133 

  1134 QState *QStateMachinePrivate::startState()