Significantly improve memory usage in XsdStateMachine::toDFA

We now mark DFA state sets immediately when they are enqueued and
check for that mark before enqueing them. This way, we save a lot
of memory when a set has many states and is encountered often.
In the referenced bug report, there were 60000 copies of a set with
40000 entries, wasting tens of gigabytes of memory.

Task-number: QTBUG-65067
Change-Id: Iec3a04c8badfac29faefbba22c2942ed104effbb
Reviewed-by: Kari Hormi <kari.hormi@qt.io>
Reviewed-by: Erik Verbruggen <erik.verbruggen@qt.io>

1 files changed, 7 insertions, 9 deletions

diff --git a/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h b/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h
index 1cb2e72..9277c1b 100644
--- a/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h
+++ b/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h
@@ -359,19 +359,14 @@ XsdStateMachine<TransitionType> XsdStateMachine<TransitionType>::toDFA() const
     QList< QSet<StateId> > workStates;
 
     // add the start state to the list of to processed state sets
-    workStates.append(epsilonClosure(QSet<StateId>() << startState));
+    auto firstDfaState = epsilonClosure(QSet<StateId>() << startState);
+    workStates.append(firstDfaState);
+    isMarked.append(firstDfaState);
 
     while (!workStates.isEmpty()) { // as long as there are state sets to process left
-
         // enqueue set of states
         const QSet<StateId> states = workStates.takeFirst();
 
-        if (isMarked.contains(states)) // we processed this state set already
-            continue;
-
-        // mark as processed
-        isMarked.append(states);
-
         // select a list of all inputs that are possible for
         // the 'states' set
         QList<TransitionType> input;
@@ -395,7 +390,10 @@ XsdStateMachine<TransitionType> XsdStateMachine<TransitionType>::toDFA() const
             dfa.addTransition(dfaBegin, input.at(i), dfaEnd);
 
             // add the 'followStates' to the list of to be processed state sets
-            workStates.append(followStates);
+            if (!isMarked.contains(followStates)) {
+                workStates.append(followStates);
+                isMarked.append(followStates); // only needs to be processed once
+            }
         }
     }