Fix infinite loop when source and target of transition are in different trees

The SCXML algorithm depends on the guarantee that there is always an LCA
regardless of the state list. The case where the targets are in a different
tree than the source (e.g. if you have not given the target state a parent) is
a bug. The fix is to set an error when this happens in exitStates() and exit
states as if the pending error states were the target states. In enterStates
we will detect the error and skip the step of selecting states to enter, and
instead just enter the pending error states. This breaks transitions to and
from the root state, which is not supported by the SCXML algorithm.

2 files changed, 34 insertions, 15 deletions

diff --git a/src/corelib/statemachine/qstatemachine.cpp b/src/corelib/statemachine/qstatemachine.cpp
index 41d4c6c..efcf707 100644
--- a/src/corelib/statemachine/qstatemachine.cpp
+++ b/src/corelib/statemachine/qstatemachine.cpp
@@ -409,6 +409,15 @@ QList<QAbstractState*> QStateMachinePrivate::exitStates(QEvent *event, const QLi
             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) {
@@ -476,21 +485,23 @@ QList<QAbstractState*> QStateMachinePrivate::enterStates(QEvent *event, const QL
     QSet<QAbstractState*> statesToEnter;
     QSet<QAbstractState*> statesForDefaultEntry;
 
-    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);                    
+    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);                    
+                    }
                 }
             }
         }
@@ -976,6 +987,13 @@ void QStateMachinePrivate::setError(QStateMachine::Error errorCode, QAbstractSta
         errorString = QStateMachine::tr("Missing default state in history state '%1'")
                         .arg(currentContext->objectName());
         break;
+
+    case QStateMachine::NoCommonAncestorForTransitionError:
+        Q_ASSERT(currentContext != 0);
+
+        errorString = QStateMachine::tr("No common ancestor for targets and source of transition from state '%1'")
+                        .arg(currentContext->objectName());
+        break;
     default:
         errorString = QStateMachine::tr("Unknown error");
     };
diff --git a/src/corelib/statemachine/qstatemachine.h b/src/corelib/statemachine/qstatemachine.h
index 10bd443..d0927a3 100644
--- a/src/corelib/statemachine/qstatemachine.h
+++ b/src/corelib/statemachine/qstatemachine.h
@@ -87,6 +87,7 @@ public:
         NoError, 
         NoInitialStateError,
         NoDefaultStateInHistoryState,
+        NoCommonAncestorForTransitionError
     };
 
     QStateMachine(QObject *parent = 0);