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
56template <typename TransitionType>
57XsdStateMachine<TransitionType>::XsdStateMachine()
58 : m_counter(50),
59 m_lastTransition()
60{
61}
62
63template <typename TransitionType>
64XsdStateMachine<TransitionType>::XsdStateMachine(const NamePool::Ptr &namePool)
65 : m_namePool(namePool),
66 m_counter(50),
67 m_lastTransition()
68{
69}
70
71template <typename TransitionType>
72typename 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
94template <typename TransitionType>
95void 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
103template <typename TransitionType>
104void XsdStateMachine<TransitionType>::addEpsilonTransition(StateId start, StateId end)
105{
106 QVector<StateId> &states = m_epsilonTransitions[start];
107 states.append(t: end);
108}
109
110template <typename TransitionType>
111void 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
126template <typename TransitionType>
127void 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
136template <typename TransitionType>
137bool 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
155template <typename TransitionType>
156QList<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
169template <typename TransitionType>
170template <typename InputType>
171bool 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
193template <typename TransitionType>
194template <typename InputType>
195bool XsdStateMachine<TransitionType>::inputEqualsTransition(InputType input, TransitionType transition) const
196{
197 Q_UNUSED(input);
198 Q_UNUSED(transition);
199
200 return false;
201}
202
203template <typename TransitionType>
204bool 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
210template <typename TransitionType>
211TransitionType XsdStateMachine<TransitionType>::lastTransition() const
212{
213 return m_lastTransition;
214}
215
216template <typename TransitionType>
217typename 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
230template <typename TransitionType>
231QString XsdStateMachine<TransitionType>::transitionTypeToString(TransitionType type) const
232{
233 Q_UNUSED(type)
234
235 return QString();
236}
237
238template <typename TransitionType>
239bool 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=\"&#949;\"]\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
295template <typename TransitionType>
296typename 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
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 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
403template <typename TransitionType>
404QHash<typename XsdStateMachine<TransitionType>::StateId, typename XsdStateMachine<TransitionType>::StateType> XsdStateMachine<TransitionType>::states() const
405{
406 return m_states;
407}
408
409template <typename TransitionType>
410QHash<typename XsdStateMachine<TransitionType>::StateId, QHash<TransitionType, QVector<typename XsdStateMachine<TransitionType>::StateId> > > XsdStateMachine<TransitionType>::transitions() const
411{
412 return m_transitions;
413}
414

source code of qtxmlpatterns/src/xmlpatterns/schema/qxsdstatemachine_tpl_p.h