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