1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
6 ** This file is part of the QtXmlPatterns module of the Qt Toolkit.
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** GNU Lesser General Public License Usage
10 ** This file may be used under the terms of the GNU Lesser General Public
11 ** License version 2.1 as published by the Free Software Foundation and
12 ** appearing in the file LICENSE.LGPL included in the packaging of this
13 ** file. Please review the following information to ensure the GNU Lesser
14 ** General Public License version 2.1 requirements will be met:
15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
17 ** In addition, as a special exception, Nokia gives you certain additional
18 ** rights. These rights are described in the Nokia Qt LGPL Exception
19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
21 ** GNU General Public License Usage
22 ** Alternatively, this file may be used under the terms of the GNU General
23 ** Public License version 3.0 as published by the Free Software Foundation
24 ** and appearing in the file LICENSE.GPL included in the packaging of this
25 ** file. Please review the following information to ensure the GNU General
26 ** Public License version 3.0 requirements will be met:
27 ** http://www.gnu.org/copyleft/gpl.html.
30 ** Alternatively, this file may be used in accordance with the terms and
31 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
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.
52 #ifndef Patternist_XsdStateMachine_H
53 #define Patternist_XsdStateMachine_H
55 #include <private/qnamepool_p.h>
57 #include <QtCore/QHash>
58 #include <QtCore/QSet>
59 #include <QtCore/QTextStream>
70 * @short A state machine used for evaluation.
72 * @ingroup Patternist_schema
73 * @author Tobias Koenig <tobias.koenig@nokia.com>
75 template <typename TransitionType>
79 typedef qint32 StateId;
82 * Describes the type of state.
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.
93 * Creates a new state machine object.
98 * Creates a new state machine object.
100 * The name pool to use for accessing object names.
102 XsdStateMachine(const NamePool::Ptr &namePool);
105 * Adds a new state of the given @p type to the state machine.
107 * @return The id of the new state.
109 StateId addState(StateType type);
112 * Adds a new @p transition to the state machine.
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.
118 void addTransition(StateId start, TransitionType transition, StateId end);
121 * Adds a new epsilon @p transition to the state machine.
123 * @param start The start state.
124 * @param end The end state.
126 void addEpsilonTransition(StateId start, StateId end);
129 * Resets the machine to the start state.
134 * Removes all states and transitions from the state machine.
139 * Continues execution of the machine with the given input @p transition.
141 * @return @c true if the transition was successful, @c false otherwise.
143 bool proceed(TransitionType transition);
146 * Returns the list of transitions that are reachable from the current
149 QList<TransitionType> possibleTransitions() const;
152 * Continues execution of the machine with the given @p input.
154 * @note To use this method, inputEqualsTransition must be implemented
155 * to find the right transition to use.
157 * @return @c true if the transition was successful, @c false otherwise.
159 template <typename InputType>
160 bool proceed(InputType input);
163 * Returns whether the given @p input matches the given @p transition.
165 template <typename InputType>
166 bool inputEqualsTransition(InputType input, TransitionType transition) const;
169 * Returns whether the machine is in an allowed end state.
171 bool inEndState() const;
174 * Returns the last transition that was taken.
176 TransitionType lastTransition() const;
179 * Returns the start state of the machine.
181 StateId startState() const;
184 * This method should be redefined by template specialization for every
185 * concret TransitionType.
187 QString transitionTypeToString(TransitionType type) const;
190 * Outputs the state machine in DOT format to the given
193 bool outputGraph(QIODevice *device, const QString &graphName) const;
196 * Returns a DFA that is equal to the NFA of the state machine.
198 XsdStateMachine<TransitionType> toDFA() const;
201 * Returns the information of all states of the state machine.
203 QHash<StateId, StateType> states() const;
206 * Returns the information of all transitions of the state machine.
208 QHash<StateId, QHash<TransitionType, QVector<StateId> > > transitions() const;
212 * Returns the DFA state for the given @p nfaStat from the given @p stateTable.
213 * If there is no corresponding DFA state yet, a new one is created.
215 StateId dfaStateForNfaState(QSet<StateId> nfaState, QList< QPair< QSet<StateId>, StateId> > &stateTable, XsdStateMachine<TransitionType> &dfa) const;
218 * Returns the set of all states that can be reached from the set of @p input states
219 * by the epsilon transition.
221 * The implementation is inlined in order to workaround a compiler
222 * bug on Symbian/winscw.
224 QSet<StateId> epsilonClosure(const QSet<StateId> &input) const
226 // every state can reach itself by epsilon transition, so include the input states
227 // in the result as well
228 QSet<StateId> result = input;
230 // add the input states to the list of to be processed states
231 QList<StateId> workStates = input.toList();
232 while (!workStates.isEmpty()) { // while there are states to be processed left...
234 // dequeue one state from list
235 const StateId state = workStates.takeFirst();
237 // get the list of states that can be reached by the epsilon transition
238 // from the current 'state'
239 const QVector<StateId> targetStates = m_epsilonTransitions.value(state);
240 for (int i = 0; i < targetStates.count(); ++i) {
241 // if we have this target state not in our result set yet...
242 if (!result.contains(targetStates.at(i))) {
243 // ... add it to the result set
244 result.insert(targetStates.at(i));
246 // add the target state to the list of to be processed states as well,
247 // as we want to have the epsilon transitions not only for the first
248 // level of following states
249 workStates.append(targetStates.at(i));
258 * Returns the set of all states that can be reached from the set of given @p states
259 * by the given @p input.
261 * The implementation is inlined in order to workaround a compiler
262 * bug on Symbian/winscw.
264 QSet<StateId> move(const QSet<StateId> &states, TransitionType input) const
266 QSet<StateId> result;
268 QSetIterator<StateId> it(states);
269 while (it.hasNext()) { // iterate over all given states
270 const StateId state = it.next();
272 // get the transition table for the current state
273 const QHash<TransitionType, QVector<StateId> > transitions = m_transitions.value(state);
275 // get the target states for the given input
276 const QVector<StateId> targetStates = transitions.value(input);
278 // add all target states to the result
279 for (int i = 0; i < targetStates.size(); ++i)
280 result.insert(targetStates.at(i));
286 NamePool::Ptr m_namePool;
287 QHash<StateId, StateType> m_states;
288 QHash<StateId, QHash<TransitionType, QVector<StateId> > > m_transitions;
289 QHash<StateId, QVector<StateId> > m_epsilonTransitions;
290 StateId m_currentState;
292 TransitionType m_lastTransition;
295 #include "qxsdstatemachine_tpl_p.h"