path: root/src/xmlpatterns/schema/qxsdstatemachine.cpp

/****************************************************************************
**
** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
** Contact: Qt Software Information (qt-info@nokia.com)
**
** This file is part of the QtXmlPatterns of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** No Commercial Usage
** This file contains pre-release code and may not be distributed.
** You may use this file in accordance with the terms and conditions
** contained in the either Technology Preview License Agreement or the
** Beta Release License Agreement.
**
** GNU Lesser General Public License Usage
** Alternatively, 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.0, 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.
**
** If you are unsure which license is appropriate for your use, please
** contact the sales department at http://qt.nokia.com/contact.
** $QT_END_LICENSE$
**
****************************************************************************/

/*
 * NOTE: This file is included by qxsdstatemachine_p.h
 * if you need some includes, put them in qxsdstatemachine_p.h (outside of the namespace)
 */

template <typename TransitionType>
XsdStateMachine<TransitionType>::XsdStateMachine()
    : m_counter(50)
{
}

template <typename TransitionType>
XsdStateMachine<TransitionType>::XsdStateMachine(const NamePool::Ptr &namePool)
    : m_namePool(namePool)
    , m_counter(50)
{
}

template <typename TransitionType>
typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::addState(StateType type)
{
#ifndef QT_NO_DEBUG
    // make sure we don't have two start states
    if (type == StartState) {
        QHashIterator<StateId, StateType> it(m_states);
        while (it.hasNext()) {
            it.next();
            Q_ASSERT(it.value() != StartState && it.value() != StartEndState);
        }
    }
#endif // QT_NO_DEBUG

    // reserve new state id
    const StateId id = ++m_counter;
    m_states.insert(id, type);

    // if it is a start state, we make it to our current state
    if (type == StartState || type == StartEndState)
        m_currentState = id;

    return id;
}

template <typename TransitionType>
void XsdStateMachine<TransitionType>::addTransition(StateId start, TransitionType transition, StateId end)
{
    QHash<TransitionType, QVector<StateId> > &hash = m_transitions[start];
    QVector<StateId> &states = hash[transition];
    if (!states.contains(end))
        states.append(end);
}

template <typename TransitionType>
void XsdStateMachine<TransitionType>::addEpsilonTransition(StateId start, StateId end)
{
    QVector<StateId> &states = m_epsilonTransitions[start];
    states.append(end);
}

template <typename TransitionType>
void XsdStateMachine<TransitionType>::reset()
{
    // reset the machine to the start state
    QHashIterator<StateId, StateType> it(m_states);
    while (it.hasNext()) {
        it.next();
        if (it.value() == StartState || it.value() == StartEndState) {
            m_currentState = it.key();
            return;
        }
    }

    Q_ASSERT(false);
}

template <typename TransitionType>
void XsdStateMachine<TransitionType>::clear()
{
    m_states.clear();
    m_transitions.clear();
    m_epsilonTransitions.clear();
    m_currentState = -1;
    m_counter = 50;
}

template <typename TransitionType>
bool XsdStateMachine<TransitionType>::proceed(TransitionType transition)
{
    // check that we are not in an invalid state
    if (!m_transitions.contains(m_currentState)) {
        return false;
    }

    // fetch the transition entry for the current state
    const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];
    if (entry.contains(transition)) { // is there an transition for the given input?
        m_currentState = entry.value(transition).first();
        m_lastTransition = transition;
        return true;
    } else {
        return false;
    }
}

template <typename TransitionType>
QList<TransitionType> XsdStateMachine<TransitionType>::possibleTransitions() const
{
    // check that we are not in an invalid state
    if (!m_transitions.contains(m_currentState)) {
        return QList<TransitionType>();
    }

    // fetch the transition entry for the current state
    const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];

    return entry.keys();
}

template <typename TransitionType>
template <typename InputType>
bool XsdStateMachine<TransitionType>::proceed(InputType input)
{
    // check that we are not in an invalid state
    if (!m_transitions.contains(m_currentState)) {
        return false;
    }

    // fetch the transition entry for the current state
    const QHash<TransitionType, QVector<StateId> > &entry = m_transitions[m_currentState];
    QHashIterator<TransitionType, QVector<StateId> > it(entry);
    while (it.hasNext()) {
        it.next();
        if (inputEqualsTransition(input, it.key())) {
            m_currentState = it.value().first();
            m_lastTransition = it.key();
            return true;
        }
    }

    return false;
}

template <typename TransitionType>
template <typename InputType>
bool XsdStateMachine<TransitionType>::inputEqualsTransition(InputType input, TransitionType transition) const
{
    return false;
}

template <typename TransitionType>
bool XsdStateMachine<TransitionType>::inEndState() const
{
    // check if current state is an end state
    return (m_states.value(m_currentState) == StartEndState || m_states.value(m_currentState) == EndState);
}

template <typename TransitionType>
TransitionType XsdStateMachine<TransitionType>::lastTransition() const
{
    return m_lastTransition;
}

template <typename TransitionType>
typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::startState() const
{
    QHashIterator<StateId, StateType> it(m_states);
    while (it.hasNext()) {
        it.next();
        if (it.value() == StartState || it.value() == StartEndState)
            return it.key();
    }

    Q_ASSERT(false); // should never be reached
    return -1;
}

template <typename TransitionType>
QString XsdStateMachine<TransitionType>::transitionTypeToString(TransitionType type) const
{
    Q_UNUSED(type)

    return QString();
}

template <typename TransitionType>
bool XsdStateMachine<TransitionType>::outputGraph(QIODevice *device, const QString &graphName) const
{
    if (!device->isOpen()) {
        qWarning("device must be open for writing");
        return false;
    }

    QByteArray graph;
    QTextStream s(&graph);

    QHashIterator<StateId, QHash<TransitionType, QVector<StateId> > > it(m_transitions);
    QHashIterator<StateId, StateType> it3(m_states);

    s << "digraph " << graphName << " {\n";
    s << "  mindist = 2.0\n";

    // draw edges
    while (it.hasNext()) {
        it.next();

        QHashIterator<TransitionType, QVector<StateId> > it2(it.value());
        while (it2.hasNext()) {
            it2.next();
            for (int i = 0; i < it2.value().count(); ++i)
                s << "  " << it.key() << " -> " << it2.value().at(i) << " [label=\"" << transitionTypeToString(it2.key()) << "\"]\n";
        }
    }

    QHashIterator<StateId, QVector<StateId> > it4(m_epsilonTransitions);
    while (it4.hasNext()) {
        it4.next();

        const QVector<StateId> states = it4.value();
        for (int i = 0; i < states.count(); ++i)
            s << "  " << it4.key() << " -> " << states.at(i) << " [label=\"&#949;\"]\n";
    }

    // draw node infos
    while (it3.hasNext()) {
        it3.next();

        QString style;
        if (it3.value() == StartState) {
            style = QLatin1String("shape=circle, style=filled, color=blue");
        } else if (it3.value() == StartEndState) {
            style = QLatin1String("shape=doublecircle, style=filled, color=blue");
        } else if (it3.value() == InternalState) {
            style = QLatin1String("shape=circle, style=filled, color=red");
        } else if (it3.value() == EndState) {
            style = QLatin1String("shape=doublecircle, style=filled, color=green");
        }

        s << "  " << it3.key() << " [" << style << "]\n";
    }

    s << "}\n";

    s.flush();

    if (device->write(graph) == -1)
        return false;

    return true;
}


template <typename TransitionType>
typename XsdStateMachine<TransitionType>::StateId XsdStateMachine<TransitionType>::dfaStateForNfaState(QSet<StateId> nfaState,
                                                                                                       QList< QPair<QSet<StateId>, StateId> > &stateTable,
                                                                                                       XsdStateMachine<TransitionType> &dfa) const
{
    // check whether we have the given state in our lookup table
    // already, in that case simply return it
    for (int i = 0; i < stateTable.count(); ++i) {
        if (stateTable.at(i).first == nfaState)
            return stateTable.at(i).second;
    }

    // check if the NFA state set contains a Start or End
    // state, in that case our new DFA state will be a
    // Start or End state as well
    StateType type = InternalState;
    QSetIterator<StateId> it(nfaState);
    bool hasStartState = false;
    bool hasEndState = false;
    while (it.hasNext()) {
        const StateId state = it.next();
        if (m_states.value(state) == EndState) {
            hasEndState = true;
        } else if (m_states.value(state) == StartState) {
            hasStartState = true;
        }
    }
    if (hasStartState) {
        if (hasEndState)
            type = StartEndState;
        else
            type = StartState;
    } else if (hasEndState) {
        type = EndState;
    }

    // create the new DFA state
    const StateId dfaState = dfa.addState(type);

    // add the new DFA state to the lookup table
    stateTable.append(qMakePair<QSet<StateId>, StateId>(nfaState, dfaState));

    return dfaState;
}


template <typename TransitionType>
QSet<typename XsdStateMachine<TransitionType>::StateId> XsdStateMachine<TransitionType>::epsilonClosure(const QSet<StateId> &input) const
{
    // every state can reach itself by epsilon transition, so include the input states
    // in the result as well
    QSet<StateId> result = input;

    // add the input states to the list of to be processed states
    QList<StateId> workStates = input.toList();
    while (!workStates.isEmpty()) { // while there are states to be processed left...

        // dequeue one state from list
        const StateId state = workStates.takeFirst();

        // get the list of states that can be reached by the epsilon transition
        // from the current 'state'
        const QVector<StateId> targetStates = m_epsilonTransitions.value(state);
        for (int i = 0; i < targetStates.count(); ++i) {
            // if we have this target state not in our result set yet...
            if (!result.contains(targetStates.at(i))) {
                // ... add it to the result set
                result.insert(targetStates.at(i));

                // add the target state to the list of to be processed states as well,
                // as we want to have the epsilon transitions not only for the first
                // level of following states
                workStates.append(targetStates.at(i));
            }
        }
    }

    return result;
}

template <typename TransitionType>
QSet<typename XsdStateMachine<TransitionType>::StateId> XsdStateMachine<TransitionType>::move(const QSet<StateId> &states, TransitionType input) const
{
    QSet<StateId> result;

    QSetIterator<StateId> it(states);
    while (it.hasNext()) { // iterate over all given states
        const StateId state = it.next();

        // get the transition table for the current state
        const QHash<TransitionType, QVector<StateId> > transitions = m_transitions.value(state);

        // get the target states for the given input
        const QVector<StateId> targetStates = transitions.value(input);

        // add all target states to the result
        for (int i = 0; i < targetStates.size(); ++i)
            result.insert(targetStates.at(i));
    }

    return result;
}

template <typename TransitionType>
XsdStateMachine<TransitionType> XsdStateMachine<TransitionType>::toDFA() const
{
    XsdStateMachine<TransitionType> dfa(m_namePool);
    dfa.m_counter = 100;
    QList< QPair< QSet<StateId>, StateId> > table;
    QList< QSet<StateId> > isMarked;

    // search the start state as the algorithm starts with it...
    StateId startState = -1;
    QHashIterator<StateId, StateType> stateTypeIt(m_states);
    while (stateTypeIt.hasNext()) {
        stateTypeIt.next();
        if (stateTypeIt.value() == StartState) {
            startState = stateTypeIt.key();
            break;
        }
    }
    Q_ASSERT(startState != -1);

    // our list of state set that still have to be processed
    QList< QSet<StateId> > workStates;

    // add the start state to the list of to processed state sets
    workStates.append(epsilonClosure(QSet<StateId>() << startState));

    while (!workStates.isEmpty()) { // as long as there are state sets to process left

        // enqueue set of states
        const QSet<StateId> states = workStates.takeFirst();

        if (isMarked.contains(states)) // we processed this state set already
            continue;

        // mark as processed
        isMarked.append(states);

        // select a list of all inputs that are possible for
        // the 'states' set
        QList<TransitionType> input;

        {
            QSetIterator<StateId> it(states);
            while (it.hasNext()) {
                input << m_transitions.value(it.next()).keys();
            }
        }

        // get the state in DFA that corresponds to the 'states' set in the NFA
        const StateId dfaBegin = dfaStateForNfaState(states, table, dfa);

        for (int i = 0; i < input.count(); ++i) { // for each possible input
            // retrieve the states that can  be reached from the 'states' set by the
            // given input or by epsilon transition
            const QSet<StateId> followStates = epsilonClosure(move(states, input.at(i)));

            // get the state in DFA that corresponds to the 'followStates' set in the NFA
            const StateId dfaEnd = dfaStateForNfaState(followStates, table, dfa);

            // adds a new transition to the DFA that corresponds to the transitions between
            // 'states' and 'followStates' in the NFA
            dfa.addTransition(dfaBegin, input.at(i), dfaEnd);

            // add the 'followStates' to the list of to be processed state sets
            workStates.append(followStates);
        }
    }

    return dfa;
}

template <typename TransitionType>
QHash<typename XsdStateMachine<TransitionType>::StateId, typename XsdStateMachine<TransitionType>::StateType> XsdStateMachine<TransitionType>::states() const
{
    return m_states;
}

template <typename TransitionType>
QHash<typename XsdStateMachine<TransitionType>::StateId, QHash<TransitionType, QVector<typename XsdStateMachine<TransitionType>::StateId> > > XsdStateMachine<TransitionType>::transitions() const
{
    return m_transitions;
}