1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://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 http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://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 2.1 or version 3 as published by the Free
20 ** Software Foundation and appearing in the file LICENSE.LGPLv21 and
21 ** LICENSE.LGPLv3 included in the packaging of this file. Please review the
22 ** following information to ensure the GNU Lesser General Public License
23 ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
24 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
25 **
26 ** As a special exception, The Qt Company gives you certain additional
27 ** rights. These rights are described in The Qt Company LGPL Exception
28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 **
30 ** GNU General Public License Usage
31 ** Alternatively, this file may be used under the terms of the GNU
32 ** General Public License version 3.0 as published by the Free Software
33 ** Foundation and appearing in the file LICENSE.GPL included in the
34 ** packaging of this file. Please review the following information to
35 ** ensure the GNU General Public License version 3.0 requirements will be
36 ** met: http://www.gnu.org/copyleft/gpl.html.
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>
XsdStateMachine()48 XsdStateMachine<TransitionType>::XsdStateMachine()
49 : m_counter(50)
50 {
51 }
52
53 template <typename TransitionType>
XsdStateMachine(const NamePool::Ptr & namePool)54 XsdStateMachine<TransitionType>::XsdStateMachine(const NamePool::Ptr &namePool)
55 : m_namePool(namePool)
56 , m_counter(50)
57 {
58 }
59
60 template <typename TransitionType>
addState(StateType type)61 typename 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
85 template <typename TransitionType>
addTransition(StateId start,TransitionType transition,StateId end)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>
addEpsilonTransition(StateId start,StateId end)95 void XsdStateMachine<TransitionType>::addEpsilonTransition(StateId start, StateId end)
96 {
97 QVector<StateId> &states = m_epsilonTransitions[start];
98 states.append(end);
99 }
100
101 template <typename TransitionType>
reset()102 void 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
117 template <typename TransitionType>
clear()118 void 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
127 template <typename TransitionType>
proceed(TransitionType transition)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>
possibleTransitions() const147 QList<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
160 template <typename TransitionType>
161 template <typename InputType>
proceed(InputType input)162 bool 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
184 template <typename TransitionType>
185 template <typename InputType>
inputEqualsTransition(InputType input,TransitionType transition) const186 bool XsdStateMachine<TransitionType>::inputEqualsTransition(InputType input, TransitionType transition) const
187 {
188 return false;
189 }
190
191 template <typename TransitionType>
inEndState() const192 bool 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
198 template <typename TransitionType>
lastTransition() const199 TransitionType XsdStateMachine<TransitionType>::lastTransition() const
200 {
201 return m_lastTransition;
202 }
203
204 template <typename TransitionType>
startState() const205 typename 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
218 template <typename TransitionType>
transitionTypeToString(TransitionType type) const219 QString XsdStateMachine<TransitionType>::transitionTypeToString(TransitionType type) const
220 {
221 Q_UNUSED(type)
222
223 return QString();
224 }
225
226 template <typename TransitionType>
outputGraph(QIODevice * device,const QString & graphName) const227 bool 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=\"ε\"]\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>
dfaStateForNfaState(QSet<StateId> nfaState,QList<QPair<QSet<StateId>,StateId>> & stateTable,XsdStateMachine<TransitionType> & dfa) const294 typename 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
338 template <typename TransitionType>
toDFA() const339 XsdStateMachine<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
409 template <typename TransitionType>
states() const410 QHash<typename XsdStateMachine<TransitionType>::StateId, typename XsdStateMachine<TransitionType>::StateType> XsdStateMachine<TransitionType>::states() const
411 {
412 return m_states;
413 }
414