src/xmlpatterns/schema/qxsdstatemachine.cpp

   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 template <typename TransitionType>
 339 XsdStateMachine<TransitionType> XsdStateMachine<TransitionType>::toDFA() const
 340 {
 341     XsdStateMachine<TransitionType> dfa(m_namePool);
 342     dfa.m_counter = 100;
 343     QList< QPair< QSet<StateId>, StateId> > table;
 344     QList< QSet<StateId> > isMarked;
 345
 346     // search the start state as the algorithm starts with it...
 347     StateId startState = -1;
 348     QHashIterator<StateId, StateType> stateTypeIt(m_states);
 349     while (stateTypeIt.hasNext()) {
 350         stateTypeIt.next();
 351         if (stateTypeIt.value() == StartState) {
 352             startState = stateTypeIt.key();
 353             break;
 354         }
 355     }
 356     Q_ASSERT(startState != -1);
 357
 358     // our list of state set that still have to be processed
 359     QList< QSet<StateId> > workStates;
 360
 361     // add the start state to the list of to processed state sets
 362     workStates.append(epsilonClosure(QSet<StateId>() << startState));
 363
 364     while (!workStates.isEmpty()) { // as long as there are state sets to process left
 365
 366         // enqueue set of states
 367         const QSet<StateId> states = workStates.takeFirst();
 368
 369         if (isMarked.contains(states)) // we processed this state set already
 370             continue;
 371
 372         // mark as processed
 373         isMarked.append(states);
 374
 375         // select a list of all inputs that are possible for
 376         // the 'states' set
 377         QList<TransitionType> input;
 378
 379         {
 380             QSetIterator<StateId> it(states);
 381             while (it.hasNext()) {
 382                 input << m_transitions.value(it.next()).keys();
 383             }
 384         }
 385
 386         // get the state in DFA that corresponds to the 'states' set in the NFA
 387         const StateId dfaBegin = dfaStateForNfaState(states, table, dfa);
 388
 389         for (int i = 0; i < input.count(); ++i) { // for each possible input
 390             // retrieve the states that can  be reached from the 'states' set by the
 391             // given input or by epsilon transition
 392             const QSet<StateId> followStates = epsilonClosure(move(states, input.at(i)));
 393
 394             // get the state in DFA that corresponds to the 'followStates' set in the NFA
 395             const StateId dfaEnd = dfaStateForNfaState(followStates, table, dfa);
 396
 397             // adds a new transition to the DFA that corresponds to the transitions between
 398             // 'states' and 'followStates' in the NFA
 399             dfa.addTransition(dfaBegin, input.at(i), dfaEnd);
 400
 401             // add the 'followStates' to the list of to be processed state sets
 402             workStates.append(followStates);
 403         }
 404     }
 405
 406     return dfa;
 407 }
 408
 409 template <typename TransitionType>
 410 QHash<typename XsdStateMachine<TransitionType>::StateId, typename XsdStateMachine<TransitionType>::StateType> XsdStateMachine<TransitionType>::states() const
 411 {
 412     return m_states;
 413 }