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