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

     2 **

     3 ** Copyright (C) 2008 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 QtXmlPatterns 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 /*

    43  * NOTE: This file is included by qxsdstatemachine_p.h

    44  * if you need some includes, put them in qxsdstatemachine_p.h (outside of the namespace)

    45  */

    46 

    47 template <typename TransitionType>

    48 XsdStateMachine<TransitionType>::XsdStateMachine()

    49     : m_counter(50)

    50 {

    51 }

    52 

    53 template <typename TransitionType>

    54 XsdStateMachine<TransitionType>::XsdStateMachine(const NamePool::Ptr &namePool)

    55     : m_namePool(namePool)

    56     , m_counter(50)

    57 {

    58 }

    59 

    60 template <typename TransitionType>

    61 typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::addState(StateType type)

    62 {

    63 #ifndef QT_NO_DEBUG

    64     // make sure we don't have two start states

    65     if (type == StartState) {

    66         QHashIterator<StateId, StateType> it(m_states);

    67         while (it.hasNext()) {

    68             it.next();

    69             Q_ASSERT(it.value() != StartState && it.value() != StartEndState);

    70         }

    71     }

    72 #endif // QT_NO_DEBUG

    73 

    74     // reserve new state id

    75     const StateId id = ++m_counter;

    76     m_states.insert(id, type);

    77 

    78     // if it is a start state, we make it to our current state

    79     if (type == StartState || type == StartEndState)

    80         m_currentState = id;

    81 

    82     return id;

    83 }

    84 

    85 template <typename TransitionType>

    86 void XsdStateMachine<TransitionType>::addTransition(StateId start, TransitionType transition, StateId end)

    87 {

    88     QHash<TransitionType, QVector<StateId> > &hash = m_transitions[start];

    89     QVector<StateId> &states = hash[transition];

    90     if (!states.contains(end))

    91         states.append(end);

    92 }

    93 

    94 template <typename TransitionType>

    95 void XsdStateMachine<TransitionType>::addEpsilonTransition(StateId start, StateId end)

    96 {

    97     QVector<StateId> &states = m_epsilonTransitions[start];

    98     states.append(end);

    99 }

   100 

   101 template <typename TransitionType>

   102 void XsdStateMachine<TransitionType>::reset()

   103 {

   104     // reset the machine to the start state

   105     QHashIterator<StateId, StateType> it(m_states);

   106     while (it.hasNext()) {

   107         it.next();

   108         if (it.value() == StartState || it.value() == StartEndState) {

   109             m_currentState = it.key();

   110             return;

   111         }

   112     }

   113 

   114     Q_ASSERT(false);

   115 }

   116 

   117 template <typename TransitionType>

   118 void XsdStateMachine<TransitionType>::clear()

   119 {

   120     m_states.clear();

   121     m_transitions.clear();

   122     m_epsilonTransitions.clear();

   123     m_currentState = -1;

   124     m_counter = 50;

   125 }

   126 

   127 template <typename TransitionType>

   128 bool XsdStateMachine<TransitionType>::proceed(TransitionType transition)

   129 {

   130     // check that we are not in an invalid state

   131     if (!m_transitions.contains(m_currentState)) {

   132         return false;

   133     }

   134 

   135     // fetch the transition entry for the current state

   136     const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];

   137     if (entry.contains(transition)) { // is there an transition for the given input?

   138         m_currentState = entry.value(transition).first();

   139         m_lastTransition = transition;

   140         return true;

   141     } else {

   142         return false;

   143     }

   144 }

   145 

   146 template <typename TransitionType>

   147 QList<TransitionType> XsdStateMachine<TransitionType>::possibleTransitions() const

   148 {

   149     // check that we are not in an invalid state

   150     if (!m_transitions.contains(m_currentState)) {

   151         return QList<TransitionType>();

   152     }

   153 

   154     // fetch the transition entry for the current state

   155     const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];

   156 

   157     return entry.keys();

   158 }

   159 

   160 template <typename TransitionType>

   161 template <typename InputType>

   162 bool XsdStateMachine<TransitionType>::proceed(InputType input)

   163 {

   164     // check that we are not in an invalid state

   165     if (!m_transitions.contains(m_currentState)) {

   166         return false;

   167     }

   168 

   169     // fetch the transition entry for the current state

   170     const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];

   171     QHashIterator<TransitionType, QVector<StateId> > it(entry);

   172     while (it.hasNext()) {

   173         it.next();

   174         if (inputEqualsTransition(input, it.key())) {

   175             m_currentState = it.value().first();

   176             m_lastTransition = it.key();

   177             return true;

   178         }

   179     }

   180 

   181     return false;

   182 }

   183 

   184 template <typename TransitionType>

   185 template <typename InputType>

   186 bool XsdStateMachine<TransitionType>::inputEqualsTransition(InputType input, TransitionType transition) const

   187 {

   188     return false;

   189 }

   190 

   191 template <typename TransitionType>

   192 bool XsdStateMachine<TransitionType>::inEndState() const

   193 {

   194     // check if current state is an end state

   195     return (m_states.value(m_currentState) == StartEndState || m_states.value(m_currentState) == EndState);

   196 }

   197 

   198 template <typename TransitionType>

   199 TransitionType XsdStateMachine<TransitionType>::lastTransition() const

   200 {

   201     return m_lastTransition;

   202 }

   203 

   204 template <typename TransitionType>

   205 typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::startState() const

   206 {

   207     QHashIterator<StateId, StateType> it(m_states);

   208     while (it.hasNext()) {

   209         it.next();

   210         if (it.value() == StartState || it.value() == StartEndState)

   211             return it.key();

   212     }

   213 

   214     Q_ASSERT(false); // should never be reached

   215     return -1;

   216 }

   217 

   218 template <typename TransitionType>

   219 QString XsdStateMachine<TransitionType>::transitionTypeToString(TransitionType type) const

   220 {

   221     Q_UNUSED(type)

   222 

   223     return QString();

   224 }

   225 

   226 template <typename TransitionType>

   227 bool XsdStateMachine<TransitionType>::outputGraph(QIODevice *device, const QString &graphName) const

   228 {

   229     if (!device->isOpen()) {

   230         qWarning("device must be open for writing");

   231         return false;

   232     }

   233 

   234     QByteArray graph;

   235     QTextStream s(&graph);

   236 

   237     QHashIterator<StateId, QHash<TransitionType, QVector<StateId> > > it(m_transitions);

   238     QHashIterator<StateId, StateType> it3(m_states);

   239 

   240     s << "digraph " << graphName << " {\n";

   241     s << "  mindist = 2.0\n";

   242 

   243     // draw edges

   244     while (it.hasNext()) {

   245         it.next();

   246 

   247         QHashIterator<TransitionType, QVector<StateId> > it2(it.value());

   248         while (it2.hasNext()) {

   249             it2.next();

   250             for (int i = 0; i < it2.value().count(); ++i)

   251                 s << "  " << it.key() << " -> " << it2.value().at(i) << " [label=\"" << transitionTypeToString(it2.key()) << "\"]\n";

   252         }

   253     }

   254 

   255     QHashIterator<StateId, QVector<StateId> > it4(m_epsilonTransitions);

   256     while (it4.hasNext()) {

   257         it4.next();

   258 

   259         const QVector<StateId> states = it4.value();

   260         for (int i = 0; i < states.count(); ++i)

   261             s << "  " << it4.key() << " -> " << states.at(i) << " [label=\"&#949;\"]\n";

   262     }

   263 

   264     // draw node infos

   265     while (it3.hasNext()) {

   266         it3.next();

   267 

   268         QString style;

   269         if (it3.value() == StartState) {

   270             style = QLatin1String("shape=circle, style=filled, color=blue");

   271         } else if (it3.value() == StartEndState) {

   272             style = QLatin1String("shape=doublecircle, style=filled, color=blue");

   273         } else if (it3.value() == InternalState) {

   274             style = QLatin1String("shape=circle, style=filled, color=red");

   275         } else if (it3.value() == EndState) {

   276             style = QLatin1String("shape=doublecircle, style=filled, color=green");

   277         }

   278 

   279         s << "  " << it3.key() << " [" << style << "]\n";

   280     }

   281 

   282     s << "}\n";

   283 

   284     s.flush();

   285 

   286     if (device->write(graph) == -1)

   287         return false;

   288 

   289     return true;

   290 }

   291 

   292 

   293 template <typename TransitionType>

   294 typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::dfaStateForNfaState(QSet<StateId> nfaState,

   295                                                                                                        QList< QPair<QSet<StateId>, StateId> > &stateTable,

   296                                                                                                        XsdStateMachine<TransitionType> &dfa) const

   297 {

   298     // check whether we have the given state in our lookup table

   299     // already, in that case simply return it

   300     for (int i = 0; i < stateTable.count(); ++i) {

   301         if (stateTable.at(i).first == nfaState)

   302             return stateTable.at(i).second;

   303     }

   304 

   305     // check if the NFA state set contains a Start or End

   306     // state, in that case our new DFA state will be a

   307     // Start or End state as well

   308     StateType type = InternalState;

   309     QSetIterator<StateId> it(nfaState);

   310     bool hasStartState = false;

   311     bool hasEndState = false;

   312     while (it.hasNext()) {

   313         const StateId state = it.next();

   314         if (m_states.value(state) == EndState) {

   315             hasEndState = true;

   316         } else if (m_states.value(state) == StartState) {

   317             hasStartState = true;

   318         }

   319     }

   320     if (hasStartState) {

   321         if (hasEndState)

   322             type = StartEndState;

   323         else

   324             type = StartState;

   325     } else if (hasEndState) {

   326         type = EndState;

   327     }

   328 

   329     // create the new DFA state

   330     const StateId dfaState = dfa.addState(type);

   331 

   332     // add the new DFA state to the lookup table

   333     stateTable.append(qMakePair<QSet<StateId>, StateId>(nfaState, dfaState));

   334 

   335     return dfaState;

   336 }

   337 

   338 

   339 template <typename TransitionType>

   340 QSet<typename XsdStateMachine<TransitionType>::StateId> XsdStateMachine<TransitionType>::epsilonClosure(const QSet<StateId> &input) const

   341 {

   342     // every state can reach itself by epsilon transition, so include the input states

   343     // in the result as well

   344     QSet<StateId> result = input;

   345 

   346     // add the input states to the list of to be processed states

   347     QList<StateId> workStates = input.toList();

   348     while (!workStates.isEmpty()) { // while there are states to be processed left...

   349 

   350         // dequeue one state from list

   351         const StateId state = workStates.takeFirst();

   352 

   353         // get the list of states that can be reached by the epsilon transition

   354         // from the current 'state'

   355         const QVector<StateId> targetStates = m_epsilonTransitions.value(state);

   356         for (int i = 0; i < targetStates.count(); ++i) {

   357             // if we have this target state not in our result set yet...

   358             if (!result.contains(targetStates.at(i))) {

   359                 // ... add it to the result set

   360                 result.insert(targetStates.at(i));

   361 

   362                 // add the target state to the list of to be processed states as well,

   363                 // as we want to have the epsilon transitions not only for the first

   364                 // level of following states

   365                 workStates.append(targetStates.at(i));

   366             }

   367         }

   368     }

   369 

   370     return result;

   371 }

   372 

   373 template <typename TransitionType>

   374 QSet<typename XsdStateMachine<TransitionType>::StateId> XsdStateMachine<TransitionType>::move(const QSet<StateId> &states, TransitionType input) const

   375 {

   376     QSet<StateId> result;

   377 

   378     QSetIterator<StateId> it(states);

   379     while (it.hasNext()) { // iterate over all given states

   380         const StateId state = it.next();

   381 

   382         // get the transition table for the current state

   383         const QHash<TransitionType, QVector<StateId> > transitions = m_transitions.value(state);

   384 

   385         // get the target states for the given input

   386         const QVector<StateId> targetStates = transitions.value(input);

   387 

   388         // add all target states to the result

   389         for (int i = 0; i < targetStates.size(); ++i)

   390             result.insert(targetStates.at(i));

   391     }

   392 

   393     return result;

   394 }

   395 

   396 template <typename TransitionType>

   397 XsdStateMachine<TransitionType> XsdStateMachine<TransitionType>::toDFA() const

   398 {

   399     XsdStateMachine<TransitionType> dfa(m_namePool);

   400     dfa.m_counter = 100;

   401     QList< QPair< QSet<StateId>, StateId> > table;

   402     QList< QSet<StateId> > isMarked;

   403 

   404     // search the start state as the algorithm starts with it...

   405     StateId startState = -1;

   406     QHashIterator<StateId, StateType> stateTypeIt(m_states);

   407     while (stateTypeIt.hasNext()) {

   408         stateTypeIt.next();

   409         if (stateTypeIt.value() == StartState) {

   410             startState = stateTypeIt.key();

   411             break;

   412         }

   413     }

   414     Q_ASSERT(startState != -1);

   415 

   416     // our list of state set that still have to be processed

   417     QList< QSet<StateId> > workStates;

   418 

   419     // add the start state to the list of to processed state sets

   420     workStates.append(epsilonClosure(QSet<StateId>() << startState));

   421 

   422     while (!workStates.isEmpty()) { // as long as there are state sets to process left

   423 

   424         // enqueue set of states

   425         const QSet<StateId> states = workStates.takeFirst();

   426 

   427         if (isMarked.contains(states)) // we processed this state set already

   428             continue;

   429 

   430         // mark as processed

   431         isMarked.append(states);

   432 

   433         // select a list of all inputs that are possible for

   434         // the 'states' set

   435         QList<TransitionType> input;

   436 

   437         {

   438             QSetIterator<StateId> it(states);

   439             while (it.hasNext()) {

   440                 input << m_transitions.value(it.next()).keys();

   441             }

   442         }

   443 

   444         // get the state in DFA that corresponds to the 'states' set in the NFA

   445         const StateId dfaBegin = dfaStateForNfaState(states, table, dfa);

   446 

   447         for (int i = 0; i < input.count(); ++i) { // for each possible input

   448             // retrieve the states that can  be reached from the 'states' set by the

   449             // given input or by epsilon transition

   450             const QSet<StateId> followStates = epsilonClosure(move(states, input.at(i)));

   451 

   452             // get the state in DFA that corresponds to the 'followStates' set in the NFA

   453             const StateId dfaEnd = dfaStateForNfaState(followStates, table, dfa);

   454 

   455             // adds a new transition to the DFA that corresponds to the transitions between

   456             // 'states' and 'followStates' in the NFA

   457             dfa.addTransition(dfaBegin, input.at(i), dfaEnd);

   458 

   459             // add the 'followStates' to the list of to be processed state sets

   460             workStates.append(followStates);

   461         }

   462     }

   463 

   464     return dfa;

   465 }

   466 

   467 template <typename TransitionType>

   468 QHash<typename XsdStateMachine<TransitionType>::StateId, typename XsdStateMachine<TransitionType>::StateType> XsdStateMachine<TransitionType>::states() const

   469 {

   470     return m_states;

   471 }

   472 

   473 template <typename TransitionType>

   474 QHash<typename XsdStateMachine<TransitionType>::StateId, QHash<TransitionType, QVector<typename XsdStateMachine<TransitionType>::StateId> > > XsdStateMachine<TransitionType>::transitions() const

   475 {

   476     return m_transitions;

   477 }