source: trunk/src/xmlpatterns/schema/qxsdstatemachine.cpp@ 1163

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

trunk: Merged in qt 4.6.1 sources.
  • Property svn:eol-style set to native
File size: 13.4 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
4** All rights reserved.
5** Contact: Nokia Corporation (qt-info@nokia.com)
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 qt-info@nokia.com.
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42/*
43 * NOTE: This file is included by qxsdstatemachine_p.h
44 * if you need some includes, put them in qxsdstatemachine_p.h (outside of the namespace)
45 */
46
47template <typename TransitionType>
48XsdStateMachine<TransitionType>::XsdStateMachine()
49 : m_counter(50)
50{
51}
52
53template <typename TransitionType>
54XsdStateMachine<TransitionType>::XsdStateMachine(const NamePool::Ptr &namePool)
55 : m_namePool(namePool)
56 , m_counter(50)
57{
58}
59
60template <typename TransitionType>
61typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::addState(StateType type)
62{
63#ifndef QT_NO_DEBUG
64 // make sure we don't have two start states
65 if (type == StartState) {
66 QHashIterator<StateId, StateType> it(m_states);
67 while (it.hasNext()) {
68 it.next();
69 Q_ASSERT(it.value() != StartState && it.value() != StartEndState);
70 }
71 }
72#endif // QT_NO_DEBUG
73
74 // reserve new state id
75 const StateId id = ++m_counter;
76 m_states.insert(id, type);
77
78 // if it is a start state, we make it to our current state
79 if (type == StartState || type == StartEndState)
80 m_currentState = id;
81
82 return id;
83}
84
85template <typename TransitionType>
86void XsdStateMachine<TransitionType>::addTransition(StateId start, TransitionType transition, StateId end)
87{
88 QHash<TransitionType, QVector<StateId> > &hash = m_transitions[start];
89 QVector<StateId> &states = hash[transition];
90 if (!states.contains(end))
91 states.append(end);
92}
93
94template <typename TransitionType>
95void XsdStateMachine<TransitionType>::addEpsilonTransition(StateId start, StateId end)
96{
97 QVector<StateId> &states = m_epsilonTransitions[start];
98 states.append(end);
99}
100
101template <typename TransitionType>
102void XsdStateMachine<TransitionType>::reset()
103{
104 // reset the machine to the start state
105 QHashIterator<StateId, StateType> it(m_states);
106 while (it.hasNext()) {
107 it.next();
108 if (it.value() == StartState || it.value() == StartEndState) {
109 m_currentState = it.key();
110 return;
111 }
112 }
113
114 Q_ASSERT(false);
115}
116
117template <typename TransitionType>
118void XsdStateMachine<TransitionType>::clear()
119{
120 m_states.clear();
121 m_transitions.clear();
122 m_epsilonTransitions.clear();
123 m_currentState = -1;
124 m_counter = 50;
125}
126
127template <typename TransitionType>
128bool XsdStateMachine<TransitionType>::proceed(TransitionType transition)
129{
130 // check that we are not in an invalid state
131 if (!m_transitions.contains(m_currentState)) {
132 return false;
133 }
134
135 // fetch the transition entry for the current state
136 const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];
137 if (entry.contains(transition)) { // is there an transition for the given input?
138 m_currentState = entry.value(transition).first();
139 m_lastTransition = transition;
140 return true;
141 } else {
142 return false;
143 }
144}
145
146template <typename TransitionType>
147QList<TransitionType> XsdStateMachine<TransitionType>::possibleTransitions() const
148{
149 // check that we are not in an invalid state
150 if (!m_transitions.contains(m_currentState)) {
151 return QList<TransitionType>();
152 }
153
154 // fetch the transition entry for the current state
155 const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];
156
157 return entry.keys();
158}
159
160template <typename TransitionType>
161template <typename InputType>
162bool XsdStateMachine<TransitionType>::proceed(InputType input)
163{
164 // check that we are not in an invalid state
165 if (!m_transitions.contains(m_currentState)) {
166 return false;
167 }
168
169 // fetch the transition entry for the current state
170 const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];
171 QHashIterator<TransitionType, QVector<StateId> > it(entry);
172 while (it.hasNext()) {
173 it.next();
174 if (inputEqualsTransition(input, it.key())) {
175 m_currentState = it.value().first();
176 m_lastTransition = it.key();
177 return true;
178 }
179 }
180
181 return false;
182}
183
184template <typename TransitionType>
185template <typename InputType>
186bool XsdStateMachine<TransitionType>::inputEqualsTransition(InputType input, TransitionType transition) const
187{
188 return false;
189}
190
191template <typename TransitionType>
192bool XsdStateMachine<TransitionType>::inEndState() const
193{
194 // check if current state is an end state
195 return (m_states.value(m_currentState) == StartEndState || m_states.value(m_currentState) == EndState);
196}
197
198template <typename TransitionType>
199TransitionType XsdStateMachine<TransitionType>::lastTransition() const
200{
201 return m_lastTransition;
202}
203
204template <typename TransitionType>
205typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::startState() const
206{
207 QHashIterator<StateId, StateType> it(m_states);
208 while (it.hasNext()) {
209 it.next();
210 if (it.value() == StartState || it.value() == StartEndState)
211 return it.key();
212 }
213
214 Q_ASSERT(false); // should never be reached
215 return -1;
216}
217
218template <typename TransitionType>
219QString XsdStateMachine<TransitionType>::transitionTypeToString(TransitionType type) const
220{
221 Q_UNUSED(type)
222
223 return QString();
224}
225
226template <typename TransitionType>
227bool XsdStateMachine<TransitionType>::outputGraph(QIODevice *device, const QString &graphName) const
228{
229 if (!device->isOpen()) {
230 qWarning("device must be open for writing");
231 return false;
232 }
233
234 QByteArray graph;
235 QTextStream s(&graph);
236
237 QHashIterator<StateId, QHash<TransitionType, QVector<StateId> > > it(m_transitions);
238 QHashIterator<StateId, StateType> it3(m_states);
239
240 s << "digraph " << graphName << " {\n";
241 s << " mindist = 2.0\n";
242
243 // draw edges
244 while (it.hasNext()) {
245 it.next();
246
247 QHashIterator<TransitionType, QVector<StateId> > it2(it.value());
248 while (it2.hasNext()) {
249 it2.next();
250 for (int i = 0; i < it2.value().count(); ++i)
251 s << " " << it.key() << " -> " << it2.value().at(i) << " [label=\"" << transitionTypeToString(it2.key()) << "\"]\n";
252 }
253 }
254
255 QHashIterator<StateId, QVector<StateId> > it4(m_epsilonTransitions);
256 while (it4.hasNext()) {
257 it4.next();
258
259 const QVector<StateId> states = it4.value();
260 for (int i = 0; i < states.count(); ++i)
261 s << " " << it4.key() << " -> " << states.at(i) << " [label=\"&#949;\"]\n";
262 }
263
264 // draw node infos
265 while (it3.hasNext()) {
266 it3.next();
267
268 QString style;
269 if (it3.value() == StartState) {
270 style = QLatin1String("shape=circle, style=filled, color=blue");
271 } else if (it3.value() == StartEndState) {
272 style = QLatin1String("shape=doublecircle, style=filled, color=blue");
273 } else if (it3.value() == InternalState) {
274 style = QLatin1String("shape=circle, style=filled, color=red");
275 } else if (it3.value() == EndState) {
276 style = QLatin1String("shape=doublecircle, style=filled, color=green");
277 }
278
279 s << " " << it3.key() << " [" << style << "]\n";
280 }
281
282 s << "}\n";
283
284 s.flush();
285
286 if (device->write(graph) == -1)
287 return false;
288
289 return true;
290}
291
292
293template <typename TransitionType>
294typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::dfaStateForNfaState(QSet<StateId> nfaState,
295 QList< QPair<QSet<StateId>, StateId> > &stateTable,
296 XsdStateMachine<TransitionType> &dfa) const
297{
298 // check whether we have the given state in our lookup table
299 // already, in that case simply return it
300 for (int i = 0; i < stateTable.count(); ++i) {
301 if (stateTable.at(i).first == nfaState)
302 return stateTable.at(i).second;
303 }
304
305 // check if the NFA state set contains a Start or End
306 // state, in that case our new DFA state will be a
307 // Start or End state as well
308 StateType type = InternalState;
309 QSetIterator<StateId> it(nfaState);
310 bool hasStartState = false;
311 bool hasEndState = false;
312 while (it.hasNext()) {
313 const StateId state = it.next();
314 if (m_states.value(state) == EndState) {
315 hasEndState = true;
316 } else if (m_states.value(state) == StartState) {
317 hasStartState = true;
318 }
319 }
320 if (hasStartState) {
321 if (hasEndState)
322 type = StartEndState;
323 else
324 type = StartState;
325 } else if (hasEndState) {
326 type = EndState;
327 }
328
329 // create the new DFA state
330 const StateId dfaState = dfa.addState(type);
331
332 // add the new DFA state to the lookup table
333 stateTable.append(qMakePair<QSet<StateId>, StateId>(nfaState, dfaState));
334
335 return dfaState;
336}
337
338template <typename TransitionType>
339XsdStateMachine<TransitionType> XsdStateMachine<TransitionType>::toDFA() const
340{
341 XsdStateMachine<TransitionType> dfa(m_namePool);
342 dfa.m_counter = 100;
343 QList< QPair< QSet<StateId>, StateId> > table;
344 QList< QSet<StateId> > isMarked;
345
346 // search the start state as the algorithm starts with it...
347 StateId startState = -1;
348 QHashIterator<StateId, StateType> stateTypeIt(m_states);
349 while (stateTypeIt.hasNext()) {
350 stateTypeIt.next();
351 if (stateTypeIt.value() == StartState) {
352 startState = stateTypeIt.key();
353 break;
354 }
355 }
356 Q_ASSERT(startState != -1);
357
358 // our list of state set that still have to be processed
359 QList< QSet<StateId> > workStates;
360
361 // add the start state to the list of to processed state sets
362 workStates.append(epsilonClosure(QSet<StateId>() << startState));
363
364 while (!workStates.isEmpty()) { // as long as there are state sets to process left
365
366 // enqueue set of states
367 const QSet<StateId> states = workStates.takeFirst();
368
369 if (isMarked.contains(states)) // we processed this state set already
370 continue;
371
372 // mark as processed
373 isMarked.append(states);
374
375 // select a list of all inputs that are possible for
376 // the 'states' set
377 QList<TransitionType> input;
378
379 {
380 QSetIterator<StateId> it(states);
381 while (it.hasNext()) {
382 input << m_transitions.value(it.next()).keys();
383 }
384 }
385
386 // get the state in DFA that corresponds to the 'states' set in the NFA
387 const StateId dfaBegin = dfaStateForNfaState(states, table, dfa);
388
389 for (int i = 0; i < input.count(); ++i) { // for each possible input
390 // retrieve the states that can be reached from the 'states' set by the
391 // given input or by epsilon transition
392 const QSet<StateId> followStates = epsilonClosure(move(states, input.at(i)));
393
394 // get the state in DFA that corresponds to the 'followStates' set in the NFA
395 const StateId dfaEnd = dfaStateForNfaState(followStates, table, dfa);
396
397 // adds a new transition to the DFA that corresponds to the transitions between
398 // 'states' and 'followStates' in the NFA
399 dfa.addTransition(dfaBegin, input.at(i), dfaEnd);
400
401 // add the 'followStates' to the list of to be processed state sets
402 workStates.append(followStates);
403 }
404 }
405
406 return dfa;
407}
408
409template <typename TransitionType>
410QHash<typename XsdStateMachine<TransitionType>::StateId, typename XsdStateMachine<TransitionType>::StateType> XsdStateMachine<TransitionType>::states() const
411{
412 return m_states;
413}
Note: See TracBrowser for help on using the repository browser.