Qt 4.8
qxsdstatemachine.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
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 Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/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 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
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 
47 template <typename TransitionType>
49  : m_counter(50)
50 {
51 }
52 
53 template <typename TransitionType>
55  : m_namePool(namePool)
56  , m_counter(50)
57 {
58 }
59 
60 template <typename TransitionType>
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 
85 template <typename TransitionType>
86 void 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 
94 template <typename TransitionType>
96 {
97  QVector<StateId> &states = m_epsilonTransitions[start];
98  states.append(end);
99 }
100 
101 template <typename TransitionType>
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 
117 template <typename TransitionType>
119 {
120  m_states.clear();
121  m_transitions.clear();
122  m_epsilonTransitions.clear();
123  m_currentState = -1;
124  m_counter = 50;
125 }
126 
127 template <typename TransitionType>
128 bool 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 
146 template <typename TransitionType>
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 
160 template <typename TransitionType>
161 template <typename InputType>
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 
184 template <typename TransitionType>
185 template <typename InputType>
186 bool XsdStateMachine<TransitionType>::inputEqualsTransition(InputType input, TransitionType transition) const
187 {
188  return false;
189 }
190 
191 template <typename TransitionType>
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 
198 template <typename TransitionType>
200 {
201  return m_lastTransition;
202 }
203 
204 template <typename TransitionType>
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 
218 template <typename TransitionType>
220 {
221  Q_UNUSED(type)
222 
223  return QString();
224 }
225 
226 template <typename TransitionType>
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 
293 template <typename TransitionType>
295  QList< QPair<QSet<StateId>, StateId> > &stateTable,
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 
338 template <typename TransitionType>
340 {
341  XsdStateMachine<TransitionType> dfa(m_namePool);
342  dfa.m_counter = 100;
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 
409 template <typename TransitionType>
411 {
412  return m_states;
413 }
static uint hash(const uchar *p, int n)
Definition: qhash.cpp:68
int type
Definition: qmetatype.cpp:239
void addTransition(StateId start, TransitionType transition, StateId end)
#define it(className, varName)
int count(const T &t) const
Returns the number of occurrences of value in the vector.
Definition: qvector.h:742
The QByteArray class provides an array of bytes.
Definition: qbytearray.h:135
Q_CORE_EXPORT QTextStream & reset(QTextStream &s)
static void clear(QVariant::Private *d)
Definition: qvariant.cpp:197
QLatin1String(DBUS_INTERFACE_DBUS))) Q_GLOBAL_STATIC_WITH_ARGS(QString
int count(const T &t) const
Returns the number of occurrences of value in the list.
Definition: qlist.h:891
The QString class provides a Unicode character string.
Definition: qstring.h:83
The QHash class is a template class that provides a hash-table-based dictionary.
Definition: qdatastream.h:66
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
bool contains(const Key &key) const
Returns true if the hash contains an item with the key; otherwise returns false.
Definition: qhash.h:872
QStringList keys
const T value(const Key &key) const
Returns the value associated with the key.
Definition: qhash.h:606
bool isEmpty() const
Returns true if the list contains no items; otherwise returns false.
Definition: qlist.h:152
void append(const T &t)
Inserts value at the end of the list.
Definition: qlist.h:507
bool isOpen() const
Returns true if the device is open; otherwise returns false.
Definition: qiodevice.cpp:530
QBool contains(const T &t) const
Returns true if the list contains an occurrence of value; otherwise returns false.
Definition: qlist.h:880
T takeFirst()
Removes the first item in the list and returns it.
Definition: qlist.h:489
T value(int i) const
Returns the value at index position i in the vector.
Definition: qvector.h:559
const T & at(int i) const
Returns the item at index position i in the list.
Definition: qlist.h:468
void append(const T &t)
Inserts value at the end of the vector.
Definition: qvector.h:573
Q_CORE_EXPORT void qWarning(const char *,...)
T value(int i) const
Returns the value at index position i in the list.
Definition: qlist.h:661
const T & at(int i) const
Returns the item at index position i in the vector.
Definition: qvector.h:350
The QTextStream class provides a convenient interface for reading and writing text.
Definition: qtextstream.h:73
Q_OUTOFLINE_TEMPLATE QPair< T1, T2 > qMakePair(const T1 &x, const T2 &y)
Definition: qpair.h:102
bool contains(const T &t) const
Returns true if the vector contains an occurrence of value; otherwise returns false.
Definition: qvector.h:731
A state machine used for evaluation.
void flush()
Flushes any buffered data waiting to be written to the device.
qint64 write(const char *data, qint64 len)
Writes at most maxSize bytes of data from data to the device.
Definition: qiodevice.cpp:1342
static const KeyPair *const end
The QIODevice class is the base interface class of all I/O devices in Qt.
Definition: qiodevice.h:66
#define Q_UNUSED(x)
Indicates to the compiler that the parameter with the specified name is not used in the body of a fun...
Definition: qglobal.h:1729
StateId addState(StateType type)
The QList class is a template class that provides lists.
Definition: qdatastream.h:62