| /**************************************************************************** |
| ** |
| ** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies). |
| ** All rights reserved. |
| ** Contact: Nokia Corporation (qt-info@nokia.com) |
| ** |
| ** This file is part of the QtXmlPatterns module of the Qt Toolkit. |
| ** |
| ** $QT_BEGIN_LICENSE:LGPL$ |
| ** GNU Lesser General Public License Usage |
| ** This file may be used under the terms of the GNU Lesser General Public |
| ** License version 2.1 as published by the Free Software Foundation and |
| ** appearing in the file LICENSE.LGPL included in the packaging of this |
| ** file. Please review the following information to ensure the GNU Lesser |
| ** General Public License version 2.1 requirements will be met: |
| ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
| ** |
| ** In addition, as a special exception, Nokia gives you certain additional |
| ** rights. These rights are described in the Nokia Qt LGPL Exception |
| ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
| ** |
| ** GNU General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU General |
| ** Public License version 3.0 as published by the Free Software Foundation |
| ** and appearing in the file LICENSE.GPL included in the packaging of this |
| ** file. Please review the following information to ensure the GNU General |
| ** Public License version 3.0 requirements will be met: |
| ** http://www.gnu.org/copyleft/gpl.html. |
| ** |
| ** Other Usage |
| ** Alternatively, this file may be used in accordance with the terms and |
| ** conditions contained in a signed written agreement between you and Nokia. |
| ** |
| ** |
| ** |
| ** |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| |
| #include "qxsdstatemachinebuilder_p.h" |
| |
| #include "qxsdelement_p.h" |
| #include "qxsdmodelgroup_p.h" |
| #include "qxsdschemahelper_p.h" |
| |
| QT_BEGIN_NAMESPACE |
| |
| using namespace QPatternist; |
| |
| /* |
| * This methods takes a list of objects and returns a list of list |
| * of all combinations the objects can be ordered. |
| * |
| * e.g. input = [ 1, 2, 3 ] |
| * output = [ |
| * [ 1, 2, 3 ], |
| * [ 1, 3, 2 ], |
| * [ 2, 1, 3 ], |
| * [ 2, 3, 1 ], |
| * [ 3, 1, 2 ], |
| * [ 3, 2, 1 ] |
| * ] |
| * |
| * The method is used to create all possible combinations for the particles |
| * in an <all> model group. |
| */ |
| template <typename T> |
| QList< QList<T> > allCombinations(const QList<T> &input) |
| { |
| if (input.count() == 1) |
| return (QList< QList<T> >() << input); |
| |
| QList< QList<T> > result; |
| for (int i = 0; i < input.count(); ++i) { |
| QList<T> subList = input; |
| T value = subList.takeAt(i); |
| |
| QList< QList<T> > subLists = allCombinations(subList); |
| for (int j = 0; j < subLists.count(); ++j) { |
| subLists[j].prepend(value); |
| } |
| result << subLists; |
| } |
| |
| return result; |
| } |
| |
| XsdStateMachineBuilder::XsdStateMachineBuilder(XsdStateMachine<XsdTerm::Ptr> *machine, const NamePool::Ptr &namePool, Mode mode) |
| : m_stateMachine(machine), m_namePool(namePool), m_mode(mode) |
| { |
| } |
| |
| XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::reset() |
| { |
| Q_ASSERT(m_stateMachine); |
| |
| m_stateMachine->clear(); |
| |
| return m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::EndState); |
| } |
| |
| XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::addStartState(XsdStateMachine<XsdTerm::Ptr>::StateId state) |
| { |
| const XsdStateMachine<XsdTerm::Ptr>::StateId startState = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::StartState); |
| m_stateMachine->addEpsilonTransition(startState, state); |
| |
| return startState; |
| } |
| |
| /* |
| * Create the FSA according to Algorithm Tp(S) from http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html |
| */ |
| XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::buildParticle(const XsdParticle::Ptr &particle, XsdStateMachine<XsdTerm::Ptr>::StateId endState) |
| { |
| XsdStateMachine<XsdTerm::Ptr>::StateId currentStartState = endState; |
| XsdStateMachine<XsdTerm::Ptr>::StateId currentEndState = endState; |
| |
| // 2 |
| if (particle->maximumOccursUnbounded()) { |
| const XsdStateMachine<XsdTerm::Ptr>::StateId t = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState); |
| const XsdStateMachine<XsdTerm::Ptr>::StateId n = buildTerm(particle->term(), t); |
| |
| m_stateMachine->addEpsilonTransition(t, n); |
| m_stateMachine->addEpsilonTransition(n, endState); |
| |
| currentEndState = t; |
| currentStartState = t; |
| } else { // 3 |
| int count = (particle->maximumOccurs() - particle->minimumOccurs()); |
| if (count > 100) |
| count = 100; |
| |
| for (int i = 0; i < count; ++i) { |
| currentStartState = buildTerm(particle->term(), currentEndState); |
| m_stateMachine->addEpsilonTransition(currentStartState, endState); |
| currentEndState = currentStartState; |
| } |
| } |
| |
| int minOccurs = particle->minimumOccurs(); |
| if (minOccurs > 100) |
| minOccurs = 100; |
| |
| for (int i = 0; i < minOccurs; ++i) { |
| currentStartState = buildTerm(particle->term(), currentEndState); |
| currentEndState = currentStartState; |
| } |
| |
| return currentStartState; |
| } |
| |
| /* |
| * Create the FSA according to Algorithm Tt(S) from http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html |
| */ |
| XsdStateMachine<XsdTerm::Ptr>::StateId XsdStateMachineBuilder::buildTerm(const XsdTerm::Ptr &term, XsdStateMachine<XsdTerm::Ptr>::StateId endState) |
| { |
| if (term->isWildcard()) { // 1 |
| const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState); |
| m_stateMachine->addTransition(b, term, endState); |
| return b; |
| } else if (term->isElement()) { // 2 |
| const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState); |
| m_stateMachine->addTransition(b, term, endState); |
| |
| const XsdElement::Ptr element(term); |
| if (m_mode == CheckingMode) { |
| const XsdElement::List substGroups = element->substitutionGroups(); |
| for (int i = 0; i < substGroups.count(); ++i) |
| m_stateMachine->addTransition(b, substGroups.at(i), endState); |
| } else if (m_mode == ValidatingMode) { |
| const XsdElement::List substGroups = element->substitutionGroups(); |
| for (int i = 0; i < substGroups.count(); ++i) { |
| if (XsdSchemaHelper::substitutionGroupOkTransitive(element, substGroups.at(i), m_namePool)) |
| m_stateMachine->addTransition(b, substGroups.at(i), endState); |
| } |
| } |
| |
| return b; |
| } else if (term->isModelGroup()) { |
| const XsdModelGroup::Ptr group(term); |
| |
| if (group->compositor() == XsdModelGroup::ChoiceCompositor) { // 3 |
| const XsdStateMachine<XsdTerm::Ptr>::StateId b = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState); |
| |
| for (int i = 0; i < group->particles().count(); ++i) { |
| const XsdParticle::Ptr particle(group->particles().at(i)); |
| if (particle->maximumOccurs() != 0) { |
| const XsdStateMachine<XsdTerm::Ptr>::StateId state = buildParticle(particle, endState); |
| m_stateMachine->addEpsilonTransition(b, state); |
| } |
| } |
| |
| return b; |
| } else if (group->compositor() == XsdModelGroup::SequenceCompositor) { // 4 |
| XsdStateMachine<XsdTerm::Ptr>::StateId currentStartState = endState; |
| XsdStateMachine<XsdTerm::Ptr>::StateId currentEndState = endState; |
| |
| for (int i = (group->particles().count() - 1); i >= 0; --i) { // iterate reverse |
| const XsdParticle::Ptr particle(group->particles().at(i)); |
| if (particle->maximumOccurs() != 0) { |
| currentStartState = buildParticle(particle, currentEndState); |
| currentEndState = currentStartState; |
| } |
| } |
| |
| return currentStartState; |
| } else if (group->compositor() == XsdModelGroup::AllCompositor) { |
| const XsdStateMachine<XsdTerm::Ptr>::StateId newStartState = m_stateMachine->addState(XsdStateMachine<XsdTerm::Ptr>::InternalState); |
| |
| const QList<XsdParticle::List> list = allCombinations(group->particles()); |
| |
| for (int i = 0; i < list.count(); ++i) { |
| XsdStateMachine<XsdTerm::Ptr>::StateId currentStartState = endState; |
| XsdStateMachine<XsdTerm::Ptr>::StateId currentEndState = endState; |
| |
| const XsdParticle::List particles = list.at(i); |
| for (int j = (particles.count() - 1); j >= 0; --j) { // iterate reverse |
| const XsdParticle::Ptr particle(particles.at(j)); |
| if (particle->maximumOccurs() != 0) { |
| currentStartState = buildParticle(particle, currentEndState); |
| currentEndState = currentStartState; |
| } |
| } |
| m_stateMachine->addEpsilonTransition(newStartState, currentStartState); |
| } |
| |
| if (list.isEmpty()) |
| return endState; |
| else |
| return newStartState; |
| } |
| } |
| |
| Q_ASSERT(false); |
| return 0; |
| } |
| |
| static void internalParticleLookupMap(const XsdParticle::Ptr &particle, QHash<XsdTerm::Ptr, XsdParticle::Ptr> &hash) |
| { |
| hash.insert(particle->term(), particle); |
| |
| if (particle->term()->isModelGroup()) { |
| const XsdModelGroup::Ptr group(particle->term()); |
| const XsdParticle::List particles = group->particles(); |
| for (int i = 0; i < particles.count(); ++i) |
| internalParticleLookupMap(particles.at(i), hash); |
| } |
| } |
| |
| QHash<XsdTerm::Ptr, XsdParticle::Ptr> XsdStateMachineBuilder::particleLookupMap(const XsdParticle::Ptr &particle) |
| { |
| QHash<XsdTerm::Ptr, XsdParticle::Ptr> result; |
| internalParticleLookupMap(particle, result); |
| |
| return result; |
| } |
| |
| QT_END_NAMESPACE |