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
59QT_BEGIN_NAMESPACE
60
61class QIODevice;
62
63namespace 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
292QT_END_NAMESPACE
293
294#endif
295

source code of qtxmlpatterns/src/xmlpatterns/schema/qxsdstatemachine_p.h