source: trunk/src/xmlpatterns/schema/qxsdstatemachine_p.h@ 769

Last change on this file since 769 was 561, checked in by Dmitry A. Kuminov, 15 years ago

trunk: Merged in qt 4.6.1 sources.
  • Property svn:eol-style set to native
File size: 11.3 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
4** All rights reserved.
5** Contact: Nokia Corporation ([email protected])
6**
7** This file is part of the QtXmlPatterns module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial Usage
11** Licensees holding valid Qt Commercial licenses may use this file in
12** accordance with the Qt Commercial License Agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and Nokia.
15**
16** GNU Lesser General Public License Usage
17** Alternatively, this file may be used under the terms of the GNU Lesser
18** General Public License version 2.1 as published by the Free Software
19** Foundation and appearing in the file LICENSE.LGPL included in the
20** packaging of this file. Please review the following information to
21** ensure the GNU Lesser General Public License version 2.1 requirements
22** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
23**
24** In addition, as a special exception, Nokia gives you certain additional
25** rights. These rights are described in the Nokia Qt LGPL Exception
26** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you have questions regarding the use of this file, please contact
37** Nokia at [email protected].
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
61class QIODevice;
62
63QT_BEGIN_HEADER
64
65QT_BEGIN_NAMESPACE
66
67namespace QPatternist
68{
69 /**
70 * @short A state machine used for evaluation.
71 *
72 * @ingroup Patternist_schema
73 * @author Tobias Koenig <[email protected]>
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 successfull, @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 successfull, @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
304QT_END_NAMESPACE
305
306QT_END_HEADER
307
308#endif
Note: See TracBrowser for help on using the repository browser.