[556] | 1 | /****************************************************************************
|
---|
| 2 | **
|
---|
| 3 | ** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
|
---|
| 4 | ** All rights reserved.
|
---|
| 5 | ** Contact: Nokia Corporation ([email protected])
|
---|
| 6 | **
|
---|
| 7 | ** This file is part of the QtXmlPatterns module of the Qt Toolkit.
|
---|
| 8 | **
|
---|
| 9 | ** $QT_BEGIN_LICENSE:LGPL$
|
---|
| 10 | ** Commercial Usage
|
---|
| 11 | ** Licensees holding valid Qt Commercial licenses may use this file in
|
---|
| 12 | ** accordance with the Qt Commercial License Agreement provided with the
|
---|
| 13 | ** Software or, alternatively, in accordance with the terms contained in
|
---|
| 14 | ** a written agreement between you and Nokia.
|
---|
| 15 | **
|
---|
| 16 | ** GNU Lesser General Public License Usage
|
---|
| 17 | ** Alternatively, this file may be used under the terms of the GNU Lesser
|
---|
| 18 | ** General Public License version 2.1 as published by the Free Software
|
---|
| 19 | ** Foundation and appearing in the file LICENSE.LGPL included in the
|
---|
| 20 | ** packaging of this file. Please review the following information to
|
---|
| 21 | ** ensure the GNU Lesser General Public License version 2.1 requirements
|
---|
| 22 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
|
---|
| 23 | **
|
---|
| 24 | ** In addition, as a special exception, Nokia gives you certain additional
|
---|
| 25 | ** rights. These rights are described in the Nokia Qt LGPL Exception
|
---|
| 26 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
|
---|
| 27 | **
|
---|
| 28 | ** GNU General Public License Usage
|
---|
| 29 | ** Alternatively, this file may be used under the terms of the GNU
|
---|
| 30 | ** General Public License version 3.0 as published by the Free Software
|
---|
| 31 | ** Foundation and appearing in the file LICENSE.GPL included in the
|
---|
| 32 | ** packaging of this file. Please review the following information to
|
---|
| 33 | ** ensure the GNU General Public License version 3.0 requirements will be
|
---|
| 34 | ** met: http://www.gnu.org/copyleft/gpl.html.
|
---|
| 35 | **
|
---|
| 36 | ** If you have questions regarding the use of this file, please contact
|
---|
| 37 | ** Nokia at [email protected].
|
---|
| 38 | ** $QT_END_LICENSE$
|
---|
| 39 | **
|
---|
| 40 | ****************************************************************************/
|
---|
| 41 |
|
---|
| 42 | #include "qxsdstatemachinebuilder_p.h"
|
---|
| 43 |
|
---|
| 44 | #include "qxsdelement_p.h"
|
---|
| 45 | #include "qxsdmodelgroup_p.h"
|
---|
| 46 | #include "qxsdschemahelper_p.h"
|
---|
| 47 |
|
---|
| 48 | QT_BEGIN_NAMESPACE
|
---|
| 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>
|
---|
| 70 | QList< QList<T> > allCombinations(const QList<T> &input)
|
---|
| 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 |
|
---|
| 90 | XsdStateMachineBuilder::XsdStateMachineBuilder(XsdStateMachine<XsdTerm::Ptr> *machine, const NamePool::Ptr &namePool, Mode mode)
|
---|
| 91 | : m_stateMachine(machine), m_namePool(namePool), m_mode(mode)
|
---|
| 92 | {
|
---|
| 93 | }
|
---|
| 94 |
|
---|
| 95 | XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::reset()
|
---|
| 96 | {
|
---|
| 97 | Q_ASSERT(m_stateMachine);
|
---|
| 98 |
|
---|
| 99 | m_stateMachine->clear();
|
---|
| 100 |
|
---|
| 101 | return m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::EndState);
|
---|
| 102 | }
|
---|
| 103 |
|
---|
| 104 | XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::addStartState(XsdStateMachine<XsdTerm::Ptr>::StateId state)
|
---|
| 105 | {
|
---|
| 106 | const XsdStateMachine<XsdTerm::Ptr>::StateId startState = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::StartState);
|
---|
| 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 | */
|
---|
| 115 | XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::buildParticle(const XsdParticle::Ptr &particle, XsdStateMachine<XsdTerm::Ptr>::StateId endState)
|
---|
| 116 | {
|
---|
| 117 | XsdStateMachine<XsdTerm::Ptr>::StateId currentStartState = endState;
|
---|
| 118 | XsdStateMachine<XsdTerm::Ptr>::StateId currentEndState = endState;
|
---|
| 119 |
|
---|
| 120 | // 2
|
---|
| 121 | if (particle->maximumOccursUnbounded()) {
|
---|
| 122 | const XsdStateMachine<XsdTerm::Ptr>::StateId t = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState);
|
---|
| 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 | */
|
---|
| 157 | XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::buildTerm(const XsdTerm::Ptr &term, XsdStateMachine<XsdTerm::Ptr>::StateId endState)
|
---|
| 158 | {
|
---|
| 159 | if (term->isWildcard()) { // 1
|
---|
| 160 | const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState);
|
---|
| 161 | m_stateMachine->addTransition(b, term, endState);
|
---|
| 162 | return b;
|
---|
| 163 | } else if (term->isElement()) { // 2
|
---|
| 164 | const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState);
|
---|
| 165 | m_stateMachine->addTransition(b, term, endState);
|
---|
| 166 |
|
---|
| 167 | const XsdElement::Ptr element(term);
|
---|
| 168 | if (m_mode == CheckingMode) {
|
---|
| 169 | const XsdElement::List substGroups = element->substitutionGroups();
|
---|
| 170 | for (int i = 0; i < substGroups.count(); ++i)
|
---|
| 171 | m_stateMachine->addTransition(b, substGroups.at(i), endState);
|
---|
| 172 | } else if (m_mode == ValidatingMode) {
|
---|
| 173 | const XsdElement::List substGroups = element->substitutionGroups();
|
---|
| 174 | for (int i = 0; i < substGroups.count(); ++i) {
|
---|
| 175 | if (XsdSchemaHelper::substitutionGroupOkTransitive(element, substGroups.at(i), m_namePool))
|
---|
| 176 | m_stateMachine->addTransition(b, 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
|
---|
| 185 | const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState);
|
---|
| 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) {
|
---|
| 210 | const XsdStateMachine<XsdTerm::Ptr>::StateId newStartState = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState);
|
---|
| 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 |
|
---|
| 240 | static void internalParticleLookupMap(const XsdParticle::Ptr &particle, QHash<XsdTerm::Ptr, XsdParticle::Ptr> &hash)
|
---|
| 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 |
|
---|
| 252 | QHash<XsdTerm::Ptr, XsdParticle::Ptr> XsdStateMachineBuilder::particleLookupMap(const XsdParticle::Ptr &particle)
|
---|
| 253 | {
|
---|
| 254 | QHash<XsdTerm::Ptr, XsdParticle::Ptr> result;
|
---|
| 255 | internalParticleLookupMap(particle, result);
|
---|
| 256 |
|
---|
| 257 | return result;
|
---|
| 258 | }
|
---|
| 259 |
|
---|
| 260 | QT_END_NAMESPACE
|
---|