src/xmlpatterns/schema/qxsdstatemachine_p.h

   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 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  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 class QIODevice;
  62
  63 QT_BEGIN_HEADER
  64
  65 QT_BEGIN_NAMESPACE
  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              * The implementation is inlined in order to workaround a compiler
 209              * bug on Symbian/winscw.
 210              */
 211             QHash<StateId, QHash<TransitionType, QVector<StateId> > > transitions() const
 212             {
 213                 return m_transitions;
 214             }
 215
 216         private:
 217             /**
 218              * Returns the DFA state for the given @p nfaStat from the given @p stateTable.
 219              * If there is no corresponding DFA state yet, a new one is created.
 220              */
 221             StateId dfaStateForNfaState(QSet<StateId> nfaState, QList< QPair< QSet<StateId>, StateId> > &stateTable, XsdStateMachine<TransitionType> &dfa) const;
 222
 223             /**
 224              * Returns the set of all states that can be reached from the set of @p input states
 225              * by the epsilon transition.
 226              *
 227              * The implementation is inlined in order to workaround a compiler
 228              * bug on Symbian/winscw.
 229              */
 230             QSet<StateId> epsilonClosure(const QSet<StateId> &input) const
 231             {
 232                 // every state can reach itself by epsilon transition, so include the input states
 233                 // in the result as well
 234                 QSet<StateId> result = input;
 235
 236                 // add the input states to the list of to be processed states
 237                 QList<StateId> workStates = input.toList();
 238                 while (!workStates.isEmpty()) { // while there are states to be processed left...
 239
 240                     // dequeue one state from list
 241                     const StateId state = workStates.takeFirst();
 242
 243                     // get the list of states that can be reached by the epsilon transition
 244                     // from the current 'state'
 245                     const QVector<StateId> targetStates = m_epsilonTransitions.value(state);
 246                     for (int i = 0; i < targetStates.count(); ++i) {
 247                         // if we have this target state not in our result set yet...
 248                         if (!result.contains(targetStates.at(i))) {
 249                             // ... add it to the result set
 250                             result.insert(targetStates.at(i));
 251
 252                             // add the target state to the list of to be processed states as well,
 253                             // as we want to have the epsilon transitions not only for the first
 254                             // level of following states
 255                             workStates.append(targetStates.at(i));
 256                         }
 257                     }
 258                 }
 259
 260                 return result;
 261             }
 262
 263             /**
 264              * Returns the set of all states that can be reached from the set of given @p states
 265              * by the given @p input.
 266              *
 267              * The implementation is inlined in order to workaround a compiler
 268              * bug on Symbian/winscw.
 269              */
 270             QSet<StateId> move(const QSet<StateId> &states, TransitionType input) const
 271             {
 272                 QSet<StateId> result;
 273
 274                 QSetIterator<StateId> it(states);
 275                 while (it.hasNext()) { // iterate over all given states
 276                     const StateId state = it.next();
 277
 278                     // get the transition table for the current state
 279                     const QHash<TransitionType, QVector<StateId> > transitions = m_transitions.value(state);
 280
 281                     // get the target states for the given input
 282                     const QVector<StateId> targetStates = transitions.value(input);
 283
 284                     // add all target states to the result
 285                     for (int i = 0; i < targetStates.size(); ++i)
 286                         result.insert(targetStates.at(i));
 287                 }
 288
 289                 return result;
 290             }
 291
 292             NamePool::Ptr                                             m_namePool;
 293             QHash<StateId, StateType>                                 m_states;
 294             QHash<StateId, QHash<TransitionType, QVector<StateId> > > m_transitions;
 295             QHash<StateId, QVector<StateId> >                         m_epsilonTransitions;
 296             StateId                                                   m_currentState;
 297             qint32                                                    m_counter;
 298             TransitionType                                            m_lastTransition;
 299     };
 300
 301     #include "qxsdstatemachine.cpp"
 302 }
 303
 304 QT_END_NAMESPACE
 305
 306 QT_END_HEADER
 307
 308 #endif