1 /**************************************************************************** 2 ** 3 ** Copyright (C) 2015 The Qt Company Ltd. 4 ** Contact: http://www.qt.io/licensing/ 5 ** 6 ** This file is part of the QtXmlPatterns module of the Qt Toolkit. 7 ** 8 ** $QT_BEGIN_LICENSE:LGPL$ 9 ** Commercial License Usage 10 ** Licensees holding valid commercial Qt licenses may use this file in 11 ** accordance with the commercial license agreement provided with the 12 ** Software or, alternatively, in accordance with the terms contained in 13 ** a written agreement between you and The Qt Company. For licensing terms 14 ** and conditions see http://www.qt.io/terms-conditions. For further 15 ** information use the contact form at http://www.qt.io/contact-us. 16 ** 17 ** GNU Lesser General Public License Usage 18 ** Alternatively, this file may be used under the terms of the GNU Lesser 19 ** General Public License version 2.1 or version 3 as published by the Free 20 ** Software Foundation and appearing in the file LICENSE.LGPLv21 and 21 ** LICENSE.LGPLv3 included in the packaging of this file. Please review the 22 ** following information to ensure the GNU Lesser General Public License 23 ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and 24 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. 25 ** 26 ** As a special exception, The Qt Company gives you certain additional 27 ** rights. These rights are described in The Qt Company LGPL Exception 28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. 29 ** 30 ** GNU General Public License Usage 31 ** Alternatively, this file may be used under the terms of the GNU 32 ** General Public License version 3.0 as published by the Free Software 33 ** Foundation and appearing in the file LICENSE.GPL included in the 34 ** packaging of this file. Please review the following information to 35 ** ensure the GNU General Public License version 3.0 requirements will be 36 ** met: http://www.gnu.org/copyleft/gpl.html. 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 "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 */ transitions()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 */ epsilonClosure(const QSet<StateId> & input)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 */ move(const QSet<StateId> & states,TransitionType input)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 309