src/xmlpatterns/schema/qxsdstatemachine_p.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtXmlPatterns module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 //
  43 //  W A R N I N G
  44 //  -------------
  45 //
  46 // This file is not part of the Qt API.  It exists purely as an
  47 // implementation detail.  This header file may change from version to
  48 // version without notice, or even be removed.
  49 //
  50 // We mean it.
  51
  52 #ifndef Patternist_XsdStateMachine_H
  53 #define Patternist_XsdStateMachine_H
  54
  55 #include <private/qnamepool_p.h>
  56
  57 #include <QtCore/QHash>
  58 #include <QtCore/QSet>
  59 #include <QtCore/QTextStream>
  60
  61 QT_BEGIN_HEADER
  62
  63 QT_BEGIN_NAMESPACE
  64
  65 class QIODevice;
  66
  67 namespace QPatternist
  68 {
  69     /**
  70      * @short A state machine used for evaluation.
  71      *
  72      * @ingroup Patternist_schema
  73      * @author Tobias Koenig <tobias.koenig@nokia.com>
  74      */
  75     template <typename TransitionType>
  76     class XsdStateMachine
  77     {
  78         public:
  79             typedef qint32 StateId;
  80
  81             /**
  82              * Describes the type of state.
  83              */
  84             enum StateType
  85             {
  86                 StartState,     ///< The state the machine will start with.
  87                 StartEndState,  ///< The state the machine will start with, can be end state as well.
  88                 InternalState,  ///< Any state that is not start or end state.
  89                 EndState        ///< Any state where the machine is allowed to stop.
  90             };
  91
  92             /**
  93              * Creates a new state machine object.
  94              */
  95             XsdStateMachine();
  96
  97             /**
  98              * Creates a new state machine object.
  99              *
 100              * The name pool to use for accessing object names.
 101              */
 102             XsdStateMachine(const NamePool::Ptr &namePool);
 103
 104             /**
 105              * Adds a new state of the given @p type to the state machine.
 106              *
 107              * @return The id of the new state.
 108              */
 109             StateId addState(StateType type);
 110
 111             /**
 112              * Adds a new @p transition to the state machine.
 113              *
 114              * @param start The start state.
 115              * @param transition The transition to come from the start to the end state.
 116              * @param end The end state.
 117              */
 118             void addTransition(StateId start, TransitionType transition, StateId end);
 119
 120             /**
 121              * Adds a new epsilon @p transition to the state machine.
 122              *
 123              * @param start The start state.
 124              * @param end The end state.
 125              */
 126             void addEpsilonTransition(StateId start, StateId end);
 127
 128             /**
 129              * Resets the machine to the start state.
 130              */
 131             void reset();
 132
 133             /**
 134              * Removes all states and transitions from the state machine.
 135              */
 136             void clear();
 137
 138             /**
 139              * Continues execution of the machine with the given input @p transition.
 140              *
 141              * @return @c true if the transition was successful, @c false otherwise.
 142              */
 143             bool proceed(TransitionType transition);
 144
 145             /**
 146              * Returns the list of transitions that are reachable from the current
 147              * state.
 148              */
 149             QList<TransitionType> possibleTransitions() const;
 150
 151             /**
 152              * Continues execution of the machine with the given @p input.
 153              *
 154              * @note To use this method, inputEqualsTransition must be implemented
 155              *       to find the right transition to use.
 156              *
 157              * @return @c true if the transition was successful, @c false otherwise.
 158              */
 159             template <typename InputType>
 160             bool proceed(InputType input);
 161
 162             /**
 163              * Returns whether the given @p input matches the given @p transition.
 164              */
 165             template <typename InputType>
 166             bool inputEqualsTransition(InputType input, TransitionType transition) const;
 167
 168             /**
 169              * Returns whether the machine is in an allowed end state.
 170              */
 171             bool inEndState() const;
 172
 173             /**
 174              * Returns the last transition that was taken.
 175              */
 176             TransitionType lastTransition() const;
 177
 178             /**
 179              * Returns the start state of the machine.
 180              */
 181             StateId startState() const;
 182
 183             /**
 184              * This method should be redefined by template specialization for every
 185              * concret TransitionType.
 186              */
 187             QString transitionTypeToString(TransitionType type) const;
 188
 189             /**
 190              * Outputs the state machine in DOT format to the given
 191              * output @p device.
 192              */
 193             bool outputGraph(QIODevice *device, const QString &graphName) const;
 194
 195             /**
 196              * Returns a DFA that is equal to the NFA of the state machine.
 197              */
 198             XsdStateMachine<TransitionType> toDFA() const;
 199
 200             /**
 201              * Returns the information of all states of the state machine.
 202              */
 203             QHash<StateId, StateType> states() const;
 204
 205             /**
 206              * Returns the information of all transitions of the state machine.
 207              */
 208             QHash<StateId, QHash<TransitionType, QVector<StateId> > > transitions() const;
 209
 210         private:
 211             /**
 212              * Returns the DFA state for the given @p nfaStat from the given @p stateTable.
 213              * If there is no corresponding DFA state yet, a new one is created.
 214              */
 215             StateId dfaStateForNfaState(QSet<StateId> nfaState, QList< QPair< QSet<StateId>, StateId> > &stateTable, XsdStateMachine<TransitionType> &dfa) const;
 216
 217             /**
 218              * Returns the set of all states that can be reached from the set of @p input states
 219              * by the epsilon transition.
 220              *
 221              * The implementation is inlined in order to workaround a compiler
 222              * bug on Symbian/winscw.
 223              */
 224             QSet<StateId> epsilonClosure(const QSet<StateId> &input) const
 225             {
 226                 // every state can reach itself by epsilon transition, so include the input states
 227                 // in the result as well
 228                 QSet<StateId> result = input;
 229
 230                 // add the input states to the list of to be processed states
 231                 QList<StateId> workStates = input.toList();
 232                 while (!workStates.isEmpty()) { // while there are states to be processed left...
 233
 234                     // dequeue one state from list
 235                     const StateId state = workStates.takeFirst();
 236
 237                     // get the list of states that can be reached by the epsilon transition
 238                     // from the current 'state'
 239                     const QVector<StateId> targetStates = m_epsilonTransitions.value(state);
 240                     for (int i = 0; i < targetStates.count(); ++i) {
 241                         // if we have this target state not in our result set yet...
 242                         if (!result.contains(targetStates.at(i))) {
 243                             // ... add it to the result set
 244                             result.insert(targetStates.at(i));
 245
 246                             // add the target state to the list of to be processed states as well,
 247                             // as we want to have the epsilon transitions not only for the first
 248                             // level of following states
 249                             workStates.append(targetStates.at(i));
 250                         }
 251                     }
 252                 }
 253
 254                 return result;
 255             }
 256
 257             /**
 258              * Returns the set of all states that can be reached from the set of given @p states
 259              * by the given @p input.
 260              *
 261              * The implementation is inlined in order to workaround a compiler
 262              * bug on Symbian/winscw.
 263              */
 264             QSet<StateId> move(const QSet<StateId> &states, TransitionType input) const
 265             {
 266                 QSet<StateId> result;
 267
 268                 QSetIterator<StateId> it(states);
 269                 while (it.hasNext()) { // iterate over all given states
 270                     const StateId state = it.next();
 271
 272                     // get the transition table for the current state
 273                     const QHash<TransitionType, QVector<StateId> > transitions = m_transitions.value(state);
 274
 275                     // get the target states for the given input
 276                     const QVector<StateId> targetStates = transitions.value(input);
 277
 278                     // add all target states to the result
 279                     for (int i = 0; i < targetStates.size(); ++i)
 280                         result.insert(targetStates.at(i));
 281                 }
 282
 283                 return result;
 284             }
 285
 286             NamePool::Ptr                                             m_namePool;
 287             QHash<StateId, StateType>                                 m_states;
 288             QHash<StateId, QHash<TransitionType, QVector<StateId> > > m_transitions;
 289             QHash<StateId, QVector<StateId> >                         m_epsilonTransitions;
 290             StateId                                                   m_currentState;
 291             qint32                                                    m_counter;
 292             TransitionType                                            m_lastTransition;
 293     };
 294
 295     #include "qxsdstatemachine.cpp"
 296 }
 297
 298 QT_END_NAMESPACE
 299
 300 QT_END_HEADER
 301
 302 #endif