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 | */ |
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(akey: 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(value: targetStates.at(i))) { |
239 | // ... add it to the result set |
240 | result.insert(value: 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(t: 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 | */ |
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(value: 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 | |