1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://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 https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://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 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or (at your option) the GNU General |
28 | ** Public license version 3 or any later version approved by the KDE Free |
29 | ** Qt Foundation. The licenses are as published by the Free Software |
30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
31 | ** included in the packaging of this file. Please review the following |
32 | ** information to ensure the GNU General Public License requirements will |
33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
35 | ** |
36 | ** $QT_END_LICENSE$ |
37 | ** |
38 | ****************************************************************************/ |
39 | |
40 | // |
41 | // W A R N I N G |
42 | // ------------- |
43 | // |
44 | // This file is not part of the Qt API. It exists purely as an |
45 | // implementation detail. This header file may change from version to |
46 | // version without notice, or even be removed. |
47 | // |
48 | // We mean it. |
49 | // |
50 | |
51 | /* |
52 | * NOTE: This file is included by qxsdstatemachine_p.h |
53 | * if you need some includes, put them in qxsdstatemachine_p.h (outside of the namespace) |
54 | */ |
55 | |
56 | template <typename TransitionType> |
57 | XsdStateMachine<TransitionType>::XsdStateMachine() |
58 | : m_counter(50), |
59 | m_lastTransition() |
60 | { |
61 | } |
62 | |
63 | template <typename TransitionType> |
64 | XsdStateMachine<TransitionType>::XsdStateMachine(const NamePool::Ptr &namePool) |
65 | : m_namePool(namePool), |
66 | m_counter(50), |
67 | m_lastTransition() |
68 | { |
69 | } |
70 | |
71 | template <typename TransitionType> |
72 | typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::addState(StateType type) |
73 | { |
74 | #ifndef QT_NO_DEBUG |
75 | // make sure we don't have two start states |
76 | if (type == StartState) { |
77 | for (auto it = m_states.cbegin(), end = m_states.cend(); it != end; ++it) { |
78 | Q_ASSERT(it.value() != StartState && it.value() != StartEndState); |
79 | } |
80 | } |
81 | #endif // QT_NO_DEBUG |
82 | |
83 | // reserve new state id |
84 | const StateId id = ++m_counter; |
85 | m_states.insert(id, type); |
86 | |
87 | // if it is a start state, we make it to our current state |
88 | if (type == StartState || type == StartEndState) |
89 | m_currentState = id; |
90 | |
91 | return id; |
92 | } |
93 | |
94 | template <typename TransitionType> |
95 | void XsdStateMachine<TransitionType>::addTransition(StateId start, TransitionType transition, StateId end) |
96 | { |
97 | QHash<TransitionType, QVector<StateId> > &hash = m_transitions[start]; |
98 | QVector<StateId> &states = hash[transition]; |
99 | if (!states.contains(t: end)) |
100 | states.append(t: end); |
101 | } |
102 | |
103 | template <typename TransitionType> |
104 | void XsdStateMachine<TransitionType>::addEpsilonTransition(StateId start, StateId end) |
105 | { |
106 | QVector<StateId> &states = m_epsilonTransitions[start]; |
107 | states.append(t: end); |
108 | } |
109 | |
110 | template <typename TransitionType> |
111 | void XsdStateMachine<TransitionType>::reset() |
112 | { |
113 | // reset the machine to the start state |
114 | auto it = m_states.cbegin(); |
115 | auto end = m_states.cend(); |
116 | for ( ; it != end; ++it) { |
117 | if (it.value() == StartState || it.value() == StartEndState) { |
118 | m_currentState = it.key(); |
119 | return; |
120 | } |
121 | } |
122 | |
123 | Q_ASSERT(false); |
124 | } |
125 | |
126 | template <typename TransitionType> |
127 | void XsdStateMachine<TransitionType>::clear() |
128 | { |
129 | m_states.clear(); |
130 | m_transitions.clear(); |
131 | m_epsilonTransitions.clear(); |
132 | m_currentState = -1; |
133 | m_counter = 50; |
134 | } |
135 | |
136 | template <typename TransitionType> |
137 | bool XsdStateMachine<TransitionType>::proceed(TransitionType transition) |
138 | { |
139 | // check that we are not in an invalid state |
140 | if (!m_transitions.contains(m_currentState)) { |
141 | return false; |
142 | } |
143 | |
144 | // fetch the transition entry for the current state |
145 | const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState]; |
146 | if (entry.contains(transition)) { // is there an transition for the given input? |
147 | m_currentState = entry.value(transition).first(); |
148 | m_lastTransition = transition; |
149 | return true; |
150 | } else { |
151 | return false; |
152 | } |
153 | } |
154 | |
155 | template <typename TransitionType> |
156 | QList<TransitionType> XsdStateMachine<TransitionType>::possibleTransitions() const |
157 | { |
158 | // check that we are not in an invalid state |
159 | if (!m_transitions.contains(m_currentState)) { |
160 | return QList<TransitionType>(); |
161 | } |
162 | |
163 | // fetch the transition entry for the current state |
164 | const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState]; |
165 | |
166 | return entry.keys(); |
167 | } |
168 | |
169 | template <typename TransitionType> |
170 | template <typename InputType> |
171 | bool XsdStateMachine<TransitionType>::proceed(InputType input) |
172 | { |
173 | // check that we are not in an invalid state |
174 | if (!m_transitions.contains(m_currentState)) { |
175 | return false; |
176 | } |
177 | |
178 | // fetch the transition entry for the current state |
179 | const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState]; |
180 | auto it = entry.cbegin(); |
181 | auto end = entry.cend(); |
182 | for ( ; it != end; ++it) { |
183 | if (inputEqualsTransition(input, it.key())) { |
184 | m_currentState = it.value().first(); |
185 | m_lastTransition = it.key(); |
186 | return true; |
187 | } |
188 | } |
189 | |
190 | return false; |
191 | } |
192 | |
193 | template <typename TransitionType> |
194 | template <typename InputType> |
195 | bool XsdStateMachine<TransitionType>::inputEqualsTransition(InputType input, TransitionType transition) const |
196 | { |
197 | Q_UNUSED(input); |
198 | Q_UNUSED(transition); |
199 | |
200 | return false; |
201 | } |
202 | |
203 | template <typename TransitionType> |
204 | bool XsdStateMachine<TransitionType>::inEndState() const |
205 | { |
206 | // check if current state is an end state |
207 | return (m_states.value(m_currentState) == StartEndState || m_states.value(m_currentState) == EndState); |
208 | } |
209 | |
210 | template <typename TransitionType> |
211 | TransitionType XsdStateMachine<TransitionType>::lastTransition() const |
212 | { |
213 | return m_lastTransition; |
214 | } |
215 | |
216 | template <typename TransitionType> |
217 | typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::startState() const |
218 | { |
219 | auto it = m_states.cbegin(); |
220 | auto end = m_states.cend(); |
221 | for ( ; it != end; ++it) { |
222 | if (it.value() == StartState || it.value() == StartEndState) |
223 | return it.key(); |
224 | } |
225 | |
226 | Q_ASSERT(false); // should never be reached |
227 | return -1; |
228 | } |
229 | |
230 | template <typename TransitionType> |
231 | QString XsdStateMachine<TransitionType>::transitionTypeToString(TransitionType type) const |
232 | { |
233 | Q_UNUSED(type) |
234 | |
235 | return QString(); |
236 | } |
237 | |
238 | template <typename TransitionType> |
239 | bool XsdStateMachine<TransitionType>::outputGraph(QIODevice *device, const QString &graphName) const |
240 | { |
241 | if (!device->isOpen()) { |
242 | qWarning(msg: "device must be open for writing" ); |
243 | return false; |
244 | } |
245 | |
246 | QByteArray graph; |
247 | QTextStream s(&graph); |
248 | |
249 | s << "digraph " << graphName << " {\n" ; |
250 | s << " mindist = 2.0\n" ; |
251 | |
252 | // draw edges |
253 | for (auto it = m_transitions.cbegin(), end = m_transitions.cend(); it != end; ++it) { |
254 | |
255 | for (auto it2 = it.value().cbegin(), end = it.value().cend(); it2 != end; ++it2) { |
256 | for (int i = 0; i < it2.value().count(); ++i) |
257 | s << " " << it.key() << " -> " << it2.value().at(i) << " [label=\"" << transitionTypeToString(type: it2.key()) << "\"]\n" ; |
258 | } |
259 | } |
260 | |
261 | for (auto it = m_epsilonTransitions.cbegin(), end = m_epsilonTransitions.cend(); it != end; ++it) { |
262 | const QVector<StateId> states = it.value(); |
263 | for (int i = 0; i < states.count(); ++i) |
264 | s << " " << it.key() << " -> " << states.at(i) << " [label=\"ε\"]\n" ; |
265 | } |
266 | |
267 | // draw node info |
268 | for (auto it = m_states.cbegin(), end = m_states.cend(); it != end; ++it) { |
269 | |
270 | QString style; |
271 | if (it.value() == StartState) { |
272 | style = QLatin1String("shape=circle, style=filled, color=blue" ); |
273 | } else if (it.value() == StartEndState) { |
274 | style = QLatin1String("shape=doublecircle, style=filled, color=blue" ); |
275 | } else if (it.value() == InternalState) { |
276 | style = QLatin1String("shape=circle, style=filled, color=red" ); |
277 | } else if (it.value() == EndState) { |
278 | style = QLatin1String("shape=doublecircle, style=filled, color=green" ); |
279 | } |
280 | |
281 | s << " " << it.key() << " [" << style << "]\n" ; |
282 | } |
283 | |
284 | s << "}\n" ; |
285 | |
286 | s.flush(); |
287 | |
288 | if (device->write(data: graph) == -1) |
289 | return false; |
290 | |
291 | return true; |
292 | } |
293 | |
294 | |
295 | template <typename TransitionType> |
296 | typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::dfaStateForNfaState(QSet<StateId> nfaState, |
297 | QList< QPair<QSet<StateId>, StateId> > &stateTable, |
298 | XsdStateMachine<TransitionType> &dfa) const |
299 | { |
300 | // check whether we have the given state in our lookup table |
301 | // already, in that case simply return it |
302 | for (int i = 0; i < stateTable.count(); ++i) { |
303 | if (stateTable.at(i).first == nfaState) |
304 | return stateTable.at(i).second; |
305 | } |
306 | |
307 | // check if the NFA state set contains a Start or End |
308 | // state, in that case our new DFA state will be a |
309 | // Start or End state as well |
310 | StateType type = InternalState; |
311 | bool hasStartState = false; |
312 | bool hasEndState = false; |
313 | for (const StateId state : qAsConst(t&: nfaState)) { |
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(t: qMakePair<QSet<StateId>, StateId>(x: nfaState, y: dfaState)); |
334 | |
335 | return dfaState; |
336 | } |
337 | |
338 | template <typename TransitionType> |
339 | 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 | auto it = m_states.cbegin(); |
349 | auto end = m_states.cend(); |
350 | for ( ; it != end; ++it) { |
351 | if (it.value() == StartState) { |
352 | startState = it.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 | auto firstDfaState = epsilonClosure(input: QSet<StateId>() << startState); |
363 | workStates.append(firstDfaState); |
364 | isMarked.append(firstDfaState); |
365 | |
366 | while (!workStates.isEmpty()) { // as long as there are state sets to process left |
367 | // enqueue set of states |
368 | const QSet<StateId> states = workStates.takeFirst(); |
369 | |
370 | // select a list of all inputs that are possible for |
371 | // the 'states' set |
372 | QList<TransitionType> input; |
373 | |
374 | for (const StateId state : states) |
375 | input << m_transitions.value(state).keys(); |
376 | |
377 | // get the state in DFA that corresponds to the 'states' set in the NFA |
378 | const StateId dfaBegin = dfaStateForNfaState(nfaState: states, stateTable&: table, dfa); |
379 | |
380 | for (int i = 0; i < input.count(); ++i) { // for each possible input |
381 | // retrieve the states that can be reached from the 'states' set by the |
382 | // given input or by epsilon transition |
383 | const QSet<StateId> followStates = epsilonClosure(input: move(states, input: input.at(i))); |
384 | |
385 | // get the state in DFA that corresponds to the 'followStates' set in the NFA |
386 | const StateId dfaEnd = dfaStateForNfaState(nfaState: followStates, stateTable&: table, dfa); |
387 | |
388 | // adds a new transition to the DFA that corresponds to the transitions between |
389 | // 'states' and 'followStates' in the NFA |
390 | dfa.addTransition(dfaBegin, input.at(i), dfaEnd); |
391 | |
392 | // add the 'followStates' to the list of to be processed state sets |
393 | if (!isMarked.contains(t: followStates)) { |
394 | workStates.append(t: followStates); |
395 | isMarked.append(t: followStates); // only needs to be processed once |
396 | } |
397 | } |
398 | } |
399 | |
400 | return dfa; |
401 | } |
402 | |
403 | template <typename TransitionType> |
404 | QHash<typename XsdStateMachine<TransitionType>::StateId, typename XsdStateMachine<TransitionType>::StateType> XsdStateMachine<TransitionType>::states() const |
405 | { |
406 | return m_states; |
407 | } |
408 | |
409 | template <typename TransitionType> |
410 | QHash<typename XsdStateMachine<TransitionType>::StateId, QHash<TransitionType, QVector<typename XsdStateMachine<TransitionType>::StateId> > > XsdStateMachine<TransitionType>::transitions() const |
411 | { |
412 | return m_transitions; |
413 | } |
414 | |