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#include "qxsdstatemachinebuilder_p.h"
41
42#include "qxsdelement_p.h"
43#include "qxsdmodelgroup_p.h"
44#include "qxsdschemahelper_p.h"
45
46QT_BEGIN_NAMESPACE
47
48using namespace QPatternist;
49
50/*
51 * This methods takes a list of objects and returns a list of list
52 * of all combinations the objects can be ordered.
53 *
54 * e.g. input = [ 1, 2, 3 ]
55 * output = [
56 * [ 1, 2, 3 ],
57 * [ 1, 3, 2 ],
58 * [ 2, 1, 3 ],
59 * [ 2, 3, 1 ],
60 * [ 3, 1, 2 ],
61 * [ 3, 2, 1 ]
62 * ]
63 *
64 * The method is used to create all possible combinations for the particles
65 * in an <all> model group.
66 */
67template <typename T>
68QList< QList<T> > allCombinations(const QList<T> &input)
69{
70 if (input.count() == 1)
71 return (QList< QList<T> >() << input);
72
73 QList< QList<T> > result;
74 for (int i = 0; i < input.count(); ++i) {
75 QList<T> subList = input;
76 T value = subList.takeAt(i);
77
78 QList< QList<T> > subLists = allCombinations(subList);
79 for (int j = 0; j < subLists.count(); ++j) {
80 subLists[j].prepend(value);
81 }
82 result << subLists;
83 }
84
85 return result;
86}
87
88XsdStateMachineBuilder::XsdStateMachineBuilder(XsdStateMachine<XsdTerm::Ptr> *machine, const NamePool::Ptr &namePool, Mode mode)
89 : m_stateMachine(machine), m_namePool(namePool), m_mode(mode)
90{
91}
92
93XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::reset()
94{
95 Q_ASSERT(m_stateMachine);
96
97 m_stateMachine->clear();
98
99 return m_stateMachine->addState(type: XsdStateMachine<XsdTerm::Ptr>::EndState);
100}
101
102XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::addStartState(XsdStateMachine<XsdTerm::Ptr>::StateId state)
103{
104 const XsdStateMachine<XsdTerm::Ptr>::StateId startState = m_stateMachine->addState(type: XsdStateMachine<XsdTerm::Ptr>::StartState);
105 m_stateMachine->addEpsilonTransition(start: startState, end: state);
106
107 return startState;
108}
109
110/*
111 * Create the FSA according to Algorithm Tp(S) from http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html
112 */
113XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::buildParticle(const XsdParticle::Ptr &particle, XsdStateMachine<XsdTerm::Ptr>::StateId endState)
114{
115 XsdStateMachine<XsdTerm::Ptr>::StateId currentStartState = endState;
116 XsdStateMachine<XsdTerm::Ptr>::StateId currentEndState = endState;
117
118 // 2
119 if (particle->maximumOccursUnbounded()) {
120 const XsdStateMachine<XsdTerm::Ptr>::StateId t = m_stateMachine->addState(type: XsdStateMachine<XsdTerm::Ptr>::InternalState);
121 const XsdStateMachine<XsdTerm::Ptr>::StateId n = buildTerm(term: particle->term(), endState: t);
122
123 m_stateMachine->addEpsilonTransition(start: t, end: n);
124 m_stateMachine->addEpsilonTransition(start: n, end: endState);
125
126 currentEndState = t;
127 currentStartState = t;
128 } else { // 3
129 int count = (particle->maximumOccurs() - particle->minimumOccurs());
130 if (count > 100)
131 count = 100;
132
133 for (int i = 0; i < count; ++i) {
134 currentStartState = buildTerm(term: particle->term(), endState: currentEndState);
135 m_stateMachine->addEpsilonTransition(start: currentStartState, end: endState);
136 currentEndState = currentStartState;
137 }
138 }
139
140 int minOccurs = particle->minimumOccurs();
141 if (minOccurs > 100)
142 minOccurs = 100;
143
144 for (int i = 0; i < minOccurs; ++i) {
145 currentStartState = buildTerm(term: particle->term(), endState: currentEndState);
146 currentEndState = currentStartState;
147 }
148
149 return currentStartState;
150}
151
152/*
153 * Create the FSA according to Algorithm Tt(S) from http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html
154 */
155XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::buildTerm(const XsdTerm::Ptr &term, XsdStateMachine<XsdTerm::Ptr>::StateId endState)
156{
157 if (term->isWildcard()) { // 1
158 const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(type: XsdStateMachine<XsdTerm::Ptr>::InternalState);
159 m_stateMachine->addTransition(start: b, transition: term, end: endState);
160 return b;
161 } else if (term->isElement()) { // 2
162 const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(type: XsdStateMachine<XsdTerm::Ptr>::InternalState);
163 m_stateMachine->addTransition(start: b, transition: term, end: endState);
164
165 const XsdElement::Ptr element(term);
166 if (m_mode == CheckingMode) {
167 const XsdElement::List substGroups = element->substitutionGroups();
168 for (int i = 0; i < substGroups.count(); ++i)
169 m_stateMachine->addTransition(start: b, transition: substGroups.at(i), end: endState);
170 } else if (m_mode == ValidatingMode) {
171 const XsdElement::List substGroups = element->substitutionGroups();
172 for (int i = 0; i < substGroups.count(); ++i) {
173 if (XsdSchemaHelper::substitutionGroupOkTransitive(head: element, member: substGroups.at(i), namePool: m_namePool))
174 m_stateMachine->addTransition(start: b, transition: substGroups.at(i), end: endState);
175 }
176 }
177
178 return b;
179 } else if (term->isModelGroup()) {
180 const XsdModelGroup::Ptr group(term);
181
182 if (group->compositor() == XsdModelGroup::ChoiceCompositor) { // 3
183 const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(type: XsdStateMachine<XsdTerm::Ptr>::InternalState);
184
185 for (int i = 0; i < group->particles().count(); ++i) {
186 const XsdParticle::Ptr particle(group->particles().at(i));
187 if (particle->maximumOccurs() != 0) {
188 const XsdStateMachine<XsdTerm::Ptr>::StateId state = buildParticle(particle, endState);
189 m_stateMachine->addEpsilonTransition(start: b, end: state);
190 }
191 }
192
193 return b;
194 } else if (group->compositor() == XsdModelGroup::SequenceCompositor) { // 4
195 XsdStateMachine<XsdTerm::Ptr>::StateId currentStartState = endState;
196 XsdStateMachine<XsdTerm::Ptr>::StateId currentEndState = endState;
197
198 for (int i = (group->particles().count() - 1); i >= 0; --i) { // iterate reverse
199 const XsdParticle::Ptr particle(group->particles().at(i));
200 if (particle->maximumOccurs() != 0) {
201 currentStartState = buildParticle(particle, endState: currentEndState);
202 currentEndState = currentStartState;
203 }
204 }
205
206 return currentStartState;
207 } else if (group->compositor() == XsdModelGroup::AllCompositor) {
208 const XsdStateMachine<XsdTerm::Ptr>::StateId newStartState = m_stateMachine->addState(type: XsdStateMachine<XsdTerm::Ptr>::InternalState);
209
210 const QList<XsdParticle::List> list = allCombinations(input: group->particles());
211
212 for (int i = 0; i < list.count(); ++i) {
213 XsdStateMachine<XsdTerm::Ptr>::StateId currentStartState = endState;
214 XsdStateMachine<XsdTerm::Ptr>::StateId currentEndState = endState;
215
216 const XsdParticle::List particles = list.at(i);
217 for (int j = (particles.count() - 1); j >= 0; --j) { // iterate reverse
218 const XsdParticle::Ptr particle(particles.at(i: j));
219 if (particle->maximumOccurs() != 0) {
220 currentStartState = buildParticle(particle, endState: currentEndState);
221 currentEndState = currentStartState;
222 }
223 }
224 m_stateMachine->addEpsilonTransition(start: newStartState, end: currentStartState);
225 }
226
227 if (list.isEmpty())
228 return endState;
229 else
230 return newStartState;
231 }
232 }
233
234 Q_ASSERT(false);
235 return 0;
236}
237
238static void internalParticleLookupMap(const XsdParticle::Ptr &particle, QHash<XsdTerm::Ptr, XsdParticle::Ptr> &hash)
239{
240 hash.insert(akey: particle->term(), avalue: particle);
241
242 if (particle->term()->isModelGroup()) {
243 const XsdModelGroup::Ptr group(particle->term());
244 const XsdParticle::List particles = group->particles();
245 for (int i = 0; i < particles.count(); ++i)
246 internalParticleLookupMap(particle: particles.at(i), hash);
247 }
248}
249
250QHash<XsdTerm::Ptr, XsdParticle::Ptr> XsdStateMachineBuilder::particleLookupMap(const XsdParticle::Ptr &particle)
251{
252 QHash<XsdTerm::Ptr, XsdParticle::Ptr> result;
253 internalParticleLookupMap(particle, hash&: result);
254
255 return result;
256}
257
258QT_END_NAMESPACE
259

source code of qtxmlpatterns/src/xmlpatterns/schema/qxsdstatemachinebuilder.cpp