/****************************************************************************

**

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

** All rights reserved.

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

**

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

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

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

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

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

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

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

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

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

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

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

**

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

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

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

**

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

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

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qstatemachine.h"

#ifndef QT_NO_STATEMACHINE

#include "qstate.h"

#include "qstate_p.h"

#include "qstatemachine_p.h"

#include "qabstracttransition.h"

#include "qabstracttransition_p.h"

#include "qsignaltransition.h"

#include "qsignaltransition_p.h"

#include "qsignaleventgenerator_p.h"

#include "qabstractstate.h"

#include "qabstractstate_p.h"

#include "qfinalstate.h"

#include "qhistorystate.h"

#include "qhistorystate_p.h"

#include "private/qobject_p.h"

#include "private/qthread_p.h"

#ifndef QT_NO_STATEMACHINE_EVENTFILTER

#include "qeventtransition.h"

#include "qeventtransition_p.h"

#endif

#ifndef QT_NO_ANIMATION

#include "qpropertyanimation.h"

#include "qanimationgroup.h"

#include <private/qvariantanimation_p.h>

#endif

#include <QtCore/qmetaobject.h>

#include <qdebug.h>

QT_BEGIN_NAMESPACE

/*!

    \class QStateMachine

    \reentrant

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

    \since 4.6

    \ingroup statemachine

    QStateMachine is based on the concepts and notation of

    \l{Statecharts: A visual formalism for complex

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

    Machine Framework}.

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

    QAbstractState) and transitions (descendants of

    QAbstractTransition) between those states; these states and

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

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

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

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

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

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

    build them.

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

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

    the machine is running is discouraged.

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

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

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

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

    entered.

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

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

    means that it executes asynchronously, and that it will not

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

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

    QEventTransition and its subclasses, handle this. But for custom

    transitions triggered by events, postEvent() is useful.

    The state machine processes events and takes transitions until a

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

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

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

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

    is clicked:

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

    This code example uses QState, which inherits QAbstractState. The

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

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

    exited. It also contains convenience functions for adding

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

    the QState class description for further details.

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

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

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

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

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

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

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

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

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

*/

/*!

    \property QStateMachine::errorString

    \brief the error string of this state machine

*/

/*!

    \property QStateMachine::globalRestorePolicy

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

    The default value of this property is

    QStateMachine::DoNotRestoreProperties.

*/

#ifndef QT_NO_ANIMATION

/*!

    \property QStateMachine::animationsEnabled

    \brief whether animations are enabled

    The default value of this property is true.

    \sa QAbstractTransition::addAnimation()

*/

#endif

// #define QSTATEMACHINE_DEBUG

QStateMachinePrivate::QStateMachinePrivate()

{

    state = NotRunning;

    _startState = 0;

    processing = false;

    processingScheduled = false;

    stop = false;

    stopProcessingReason = EventQueueEmpty;

    error = QStateMachine::NoError;

    globalRestorePolicy = QStateMachine::DoNotRestoreProperties;

    signalEventGenerator = 0;

#ifndef QT_NO_ANIMATION

    animationsEnabled = true;

#endif

}

QStateMachinePrivate::~QStateMachinePrivate()

{

    qDeleteAll(internalEventQueue);

    qDeleteAll(externalEventQueue);

}

QStateMachinePrivate *QStateMachinePrivate::get(QStateMachine *q)

{

    if (q)

        return q->d_func();

    return 0;

}

QState *QStateMachinePrivate::rootState() const

{

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

}

static QEvent *cloneEvent(QEvent *e)

{

    switch (e->type()) {

    case QEvent::None:

        return new QEvent(*e);

    case QEvent::Timer:

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

    default:

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

        break;

    }

    return 0;

}

const QStateMachinePrivate::Handler qt_kernel_statemachine_handler = {

    cloneEvent

};

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

Q_CORE_EXPORT const QStateMachinePrivate::Handler *qcoreStateMachineHandler()

{

    return &qt_kernel_statemachine_handler;

}

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)) {

            return i;

        }

    }

    return -1;

}

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

{

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

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

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

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

        return false;

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

        return true;

    } else {

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

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

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

        Q_ASSERT(lca != 0);

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

    }

}

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

{

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

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

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

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

        return true;

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

        return false;

    } else {

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

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

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

        Q_ASSERT(lca != 0);

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

    }

}

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

{

    if (states.isEmpty())

        return 0;

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

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

        QState *anc = ancestors.at(i);

        bool ok = true;

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

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

            if (!isDescendantOf(s, anc))

                ok = false;

        }

        if (ok)

            return anc;

    }

    return 0;

}

bool QStateMachinePrivate::isPreempted(const QAbstractState *s, const QSet<QAbstractTransition*> &transitions) 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;

}

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

{

    Q_Q(const QStateMachine);

    QSet<QAbstractTransition*> enabledTransitions;

    QSet<QAbstractState*>::const_iterator it;

    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());

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

            lst.prepend(grp);

        bool found = false;

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

            QState *s = lst.at(j);

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

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

                QAbstractTransition *t = transitions.at(k);

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

#ifdef QSTATEMACHINE_DEBUG

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

#endif

                    enabledTransitions.insert(t);

                    found = true;

                    break;

                }

            }

        }

    }

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

    return enabledTransitions;

}

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 = exitStates(event, enabledTransitions);

#ifdef QSTATEMACHINE_DEBUG

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

#endif

    executeTransitionContent(event, enabledTransitions);

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

#ifndef QT_NO_PROPERTIES

    applyProperties(enabledTransitions, exitedStates, enteredStates);

#endif

#ifdef QSTATEMACHINE_DEBUG

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

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

#endif

}

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

{

//    qDebug() << "exitStates(" << 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();

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

            lca = findLCA(lst);

            Q_ASSERT(lca != 0);

        }

        {

            QSet<QAbstractState*>::const_iterator it;

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

                QAbstractState *s = *it;

                if (isDescendantOf(s, lca))

                    statesToExit.insert(s);

            }

        }

    }

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

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

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

        QAbstractState *s = statesToExit_sorted.at(i);

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

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

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

                QHistoryState *h = hlst.at(j);

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

                QSet<QAbstractState*>::const_iterator it;

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

                    QAbstractState *s0 = *it;

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

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

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

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

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

                    }

                }

#ifdef QSTATEMACHINE_DEBUG

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

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

#endif

            }

        }

    }

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

        QAbstractState *s = statesToExit_sorted.at(i);

#ifdef QSTATEMACHINE_DEBUG

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

#endif

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

        configuration.remove(s);

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

    }

    return statesToExit_sorted;

}

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

{

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

        QAbstractTransition *t = enabledTransitions.at(i);

#ifdef QSTATEMACHINE_DEBUG

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

#endif

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

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

    }

}

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

{

#ifdef QSTATEMACHINE_DEBUG

    Q_Q(QStateMachine);

#endif

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

    QSet<QAbstractState*> statesToEnter;

    QSet<QAbstractState*> statesForDefaultEntry;

    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;

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

            QState *lca = findLCA(lst);

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

                QAbstractState *s = lst.at(j);

			    addStatesToEnter(s, lca, 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);                    

                    }

                }

            }

        }

    }

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

    if (!pendingErrorStates.isEmpty()) {

        statesToEnter.clear();

        statesToEnter = pendingErrorStates;

        statesForDefaultEntry = pendingErrorStatesForDefaultEntry;

        pendingErrorStates.clear();

        pendingErrorStatesForDefaultEntry.clear();

    }

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

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

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

        QAbstractState *s = statesToEnter_sorted.at(i);

#ifdef QSTATEMACHINE_DEBUG

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

#endif

        configuration.insert(s);

        registerTransitions(s);

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

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

        if (statesForDefaultEntry.contains(s)) {

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

        }

        if (isFinal(s)) {

            QState *parent = s->parentState();

            if (parent) {

                if (parent != rootState()) {

#ifdef QSTATEMACHINE_DEBUG

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

#endif

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

                }

                QState *grandparent = parent->parentState();

                if (grandparent && isParallel(grandparent)) {