Initial import from the monolithic Qt.

This is the beginning of revision history for this module. If you
want to look at revision history older than this, please refer to the
Qt Git wiki for how to use Git history grafting. At the time of
writing, this wiki is located here:

http://qt.gitorious.org/qt/pages/GitIntroductionWithQt

If you have already performed the grafting and you don't see any
history beyond this commit, try running "git log" with the "--follow"
argument.

Branched from the monolithic repo, Qt master branch, at commit
896db169ea224deb96c59ce8af800d019de63f12

1 files changed, 508 insertions, 0 deletions

diff --git a/util/lexgen/nfa.cpp b/util/lexgen/nfa.cpp
new file mode 100644
index 0000000000..4adde3a5cf
--- /dev/null
+++ b/util/lexgen/nfa.cpp
@@ -0,0 +1,508 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the utils 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 Technology Preview License Agreement accompanying
+** this package.
+**
+** 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.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+#include "nfa.h"
+#include <QSet>
+#include <limits.h>
+
+NFA NFA::createSingleInputNFA(InputType input)
+{
+    NFA result;
+    result.initialize(2);
+    result.addTransition(result.initialState, input, result.finalState);
+    return result;
+}
+
+NFA NFA::createSymbolNFA(const QString &symbol)
+{
+    NFA result = NFA::createSingleInputNFA(Epsilon);
+    result.states[result.finalState].symbol = symbol;
+    return result;
+}
+
+void NFA::initialize(int size)
+{
+    states.resize(size);
+    states.fill(State());
+    initialState = 0;
+    finalState = size - 1;
+}
+
+void NFA::addTransition(int from, InputType input, int to)
+{
+    assertValidState(from);
+    assertValidState(to);
+
+    states[from].transitions.insertMulti(input, to);
+}
+
+void NFA::copyFrom(const NFA &other, int baseState)
+{
+    assertValidState(baseState);
+    assertValidState(baseState + other.states.count() - 1);
+
+    for (int i = 0; i < other.states.count(); ++i) {
+        State s = other.states.at(i);
+
+        for (TransitionMap::Iterator it = s.transitions.begin(),
+             end = s.transitions.end(); it != end; ++it)
+            *it += baseState;
+
+        states[baseState + i] = s;
+    }
+}
+
+void NFA::initializeFromPair(const NFA &a, const NFA &b,
+                             int *initialA, int *finalA,
+                             int *initialB, int *finalB)
+{
+    initialize(a.states.count() + b.states.count() + 2);
+
+    int baseIdxA = 1;
+    int baseIdxB = 1 + a.states.count();
+
+    *initialA = a.initialState + baseIdxA;
+    *finalA = a.finalState + baseIdxA;
+
+    *initialB = b.initialState + baseIdxB;
+    *finalB = b.finalState + baseIdxB;
+
+    copyFrom(a, baseIdxA);
+    copyFrom(b, baseIdxB);
+}
+
+NFA NFA::createAlternatingNFA(const NFA &a, const NFA &b)
+{
+    NFA result;
+
+    int newInitialA, newFinalA,
+        newInitialB, newFinalB;
+
+    result.initializeFromPair(a, b, &newInitialA, &newFinalA,
+                              &newInitialB, &newFinalB);
+
+    result.addTransition(result.initialState, Epsilon, newInitialA);
+    result.addTransition(result.initialState, Epsilon, newInitialB);
+
+    result.addTransition(newFinalA, Epsilon, result.finalState);
+    result.addTransition(newFinalB, Epsilon, result.finalState);
+
+    return result;
+}
+
+NFA NFA::createConcatenatingNFA(const NFA &a, const NFA &b)
+{
+    NFA result;
+
+    int initialA, finalA,
+        initialB, finalB;
+
+    result.initializeFromPair(a, b, &initialA, &finalA, &initialB, &finalB);
+
+    result.addTransition(result.initialState, Epsilon, initialA);
+    result.addTransition(finalA, Epsilon, initialB);
+    result.addTransition(finalB, Epsilon, result.finalState);
+    return result;
+}
+
+NFA NFA::createOptionalNFA(const NFA &a)
+{
+    NFA result;
+
+    result.initialize(a.states.count() + 2);
+
+    int baseIdxA = 1;
+    int initialA = a.initialState + baseIdxA;
+    int finalA = a.finalState + baseIdxA;
+
+    result.copyFrom(a, baseIdxA);
+
+    result.addTransition(result.initialState, Epsilon, initialA);
+    result.addTransition(result.initialState, Epsilon, result.finalState);
+
+    result.addTransition(finalA, Epsilon, initialA);
+    result.addTransition(finalA, Epsilon, result.finalState);
+
+    return result;
+}
+
+NFA NFA::createStringNFA(const QByteArray &str)
+{
+    NFA result;
+    foreach (char c, str) {
+        NFA ch = NFA::createSingleInputNFA(c);
+        if (result.isEmpty())
+            result = ch;
+        else
+            result = NFA::createConcatenatingNFA(result, ch);
+    }
+    return result;
+}
+
+NFA NFA::createSetNFA(const QSet<InputType> &set)
+{
+    NFA result;
+    result.initialize(set.count() + 2);
+
+    int state = 1;
+    for (QSet<InputType>::ConstIterator it = set.constBegin(), end = set.constEnd();
+         it != end; ++it, ++state) {
+        result.addTransition(result.initialState, Epsilon, state);
+        result.addTransition(state, *it, result.finalState);
+    }
+
+    /*
+    foreach (InputType input, set) {
+        NFA ch = NFA::createSingleInputNFA(input);
+        if (result.isEmpty())
+            result = ch;
+        else
+            result = NFA::createAlternatingNFA(result, ch);
+    }
+    */
+    return result;
+}
+
+NFA NFA::createZeroOrOneNFA(const NFA &a)
+{
+    NFA epsilonNFA = createSingleInputNFA(Epsilon);
+    return NFA::createAlternatingNFA(a, epsilonNFA);
+}
+
+NFA NFA::applyQuantity(const NFA &a, int minOccurrences, int maxOccurrences)
+{
+    NFA result = a;
+    NFA epsilonNFA = createSingleInputNFA(Epsilon);
+
+    if (minOccurrences == 0) {
+        result = NFA::createAlternatingNFA(result, epsilonNFA);
+    } else {
+        minOccurrences--;
+    }
+    maxOccurrences--;
+
+    for (int i = 0; i < minOccurrences; ++i)
+        result = NFA::createConcatenatingNFA(result, a);
+
+    for (int i = minOccurrences; i < maxOccurrences; ++i)
+        result = NFA::createConcatenatingNFA(result, NFA::createAlternatingNFA(a, epsilonNFA));
+
+    return result;
+}
+
+void NFA::debug()
+{
+    qDebug() << "NFA has" << states.count() << "states";
+    qDebug() << "initial state is" << initialState;
+    qDebug() << "final state is" << finalState;
+
+    for (int i = 0; i < states.count(); ++i) {
+        const State &s = states.at(i);
+        for (TransitionMap::ConstIterator it = s.transitions.constBegin(),
+             end = s.transitions.constEnd(); it != end; ++it)
+            qDebug() << "transition from state" << i << "to" << it.value() << "through"
+                     << (it.key() == Epsilon ? QString("Epsilon") : QString(char(it.key())));
+        if (!s.symbol.isEmpty())
+            qDebug() << "State" << i << "leads to symbol" << s.symbol;
+    }
+}
+
+// helper
+typedef QSet<int> DFAState;
+
+// that's a bad hash, but it's good enough for us
+// and it allows us to use the nice QHash API :)
+inline uint qHash(const DFAState &state)
+{
+    uint val = 0;
+    foreach (int s, state)
+        val |= qHash(s);
+    return val;
+}
+
+DFA NFA::toDFA() const
+{
+    DFA result;
+    result.reserve(states.count());
+
+    QHash<QString, int> symbolReferenceCounts;
+    {
+        QSet<int> symbolStates;
+        for (int i = 0; i < states.count(); ++i)
+            if (!states.at(i).symbol.isEmpty())
+                symbolStates.insert(i);
+
+        QHash<int, QString> epsilonStates;
+        for (int i = 0; i < states.count(); ++i) {
+            const State &s = states.at(i);
+            for (TransitionMap::ConstIterator transition = s.transitions.constBegin(), end = s.transitions.constEnd();
+                 transition != end; ++transition)
+                if (transition.key() == Epsilon && symbolStates.contains(transition.value()))
+                    epsilonStates.insert(i, states.at(transition.value()).symbol);
+        }
+
+        int lastCount;
+        do {
+            lastCount = epsilonStates.count();
+            for (int i = 0; i < states.count(); ++i) {
+                const State &s = states.at(i);
+                for (TransitionMap::ConstIterator transition = s.transitions.constBegin(), end = s.transitions.constEnd();
+                     transition != end; ++transition)
+                    if (transition.key() == Epsilon && epsilonStates.contains(transition.value()))
+                        epsilonStates.insert(i, epsilonStates.value(transition.value()));
+            }
+
+        } while (lastCount != epsilonStates.count());
+
+        for (int i = 0; i < states.count(); ++i) {
+            const State &s = states.at(i);
+            for (TransitionMap::ConstIterator transition = s.transitions.constBegin(), end = s.transitions.constEnd();
+                 transition != end; ++transition) {
+                if (transition.key() == Epsilon)
+                    continue;
+                if (symbolStates.contains(transition.value())) {
+                    const QString symbol = states.at(transition.value()).symbol;
+                    symbolReferenceCounts[symbol]++;
+                } else if (epsilonStates.contains(transition.value())) {
+                    const QString symbol = epsilonStates.value(transition.value());
+                    symbolReferenceCounts[symbol]++;
+                }
+            }
+        }
+        /*
+        for (QHash<QString, int>::ConstIterator symIt = symbolReferenceCounts.constBegin(), symEnd = symbolReferenceCounts.constEnd();
+             symIt != symEnd; ++symIt)
+            qDebug() << "symbol" << symIt.key() << "is reached" << symIt.value() << "times";
+            */
+    }
+
+    
+    QSet<InputType> validInput;
+    foreach (const State &s, states)
+        for (TransitionMap::ConstIterator it = s.transitions.constBegin(),
+             end = s.transitions.constEnd(); it != end; ++it)
+            if (it.key() != Epsilon)
+                validInput.insert(it.key());
+
+    // A DFA state can consist of multiple NFA states.
+    // the dfaStateMap maps from these to the actual
+    // state index within the resulting DFA vector
+    QHash<DFAState, int> dfaStateMap;
+    QStack<DFAState> pendingDFAStates;
+
+    DFAState startState = epsilonClosure(QSet<int>() << initialState);
+
+    result.resize(1);
+    dfaStateMap.insert(startState, 0);
+
+    pendingDFAStates.push(startState);
+
+    while (!pendingDFAStates.isEmpty()) {
+        DFAState state = pendingDFAStates.pop();
+//        qDebug() << "processing" << state << "from the stack of pending states";
+
+        foreach (InputType input, validInput) {
+
+            QSet<int> reachableStates;
+
+            foreach (int nfaState, state) {
+                const TransitionMap &transitions = states.at(nfaState).transitions;
+                TransitionMap::ConstIterator it = transitions.find(input);
+                while (it != transitions.constEnd() && it.key() == input) {
+                    reachableStates.insert(it.value());
+                    ++it;
+                }
+            }
+
+            if (reachableStates.isEmpty())
+                continue;
+
+//            qDebug() << "can reach" << reachableStates << "from input" << char(input);
+
+            QSet<int> closure = epsilonClosure(reachableStates);
+
+//            qDebug() << "closure is" << closure;
+
+            if (!dfaStateMap.contains(closure)) {
+                int dfaState = result.count();
+                result.append(State());
+
+                QString symbol;
+                int refCount = INT_MAX;
+                foreach (int nfaState, closure)
+                    if (!states.at(nfaState).symbol.isEmpty()) {
+//                        qDebug() << "closure also contains symbol" << states.at(nfaState).symbol;
+                        QString candidate = states.at(nfaState).symbol;
+                        int candidateRefCount =symbolReferenceCounts.value(candidate, INT_MAX);
+                        if (candidateRefCount < refCount) {
+                            refCount = candidateRefCount;
+                            symbol = candidate;
+                        }
+                    }
+                if (!symbol.isEmpty())
+                    result.last().symbol = symbol;
+
+                dfaStateMap.insert(closure, dfaState);
+
+                Q_ASSERT(!pendingDFAStates.contains(closure));
+                pendingDFAStates.prepend(closure);
+            }
+
+            result[dfaStateMap.value(state)].transitions.insert(input, dfaStateMap.value(closure));
+        }
+    }
+
+    return result;
+}
+
+QSet<int> NFA::epsilonClosure(const QSet<int> &initialClosure) const
+{
+    QSet<int> closure = initialClosure;
+    closure.reserve(closure.count() * 4);
+
+    QStack<int> stateStack;
+    stateStack.resize(closure.count());
+    qCopy(closure.constBegin(), closure.constEnd(), stateStack.begin());
+
+    while (!stateStack.isEmpty()) {
+        int t = stateStack.pop();
+        const TransitionMap &transitions = states.at(t).transitions;
+        TransitionMap::ConstIterator it = transitions.find(Epsilon);
+        while (it != transitions.constEnd() && it.key() == Epsilon) {
+            const int u = it.value();
+            if (!closure.contains(u)) {
+                closure.insert(u);
+                stateStack.push(u);
+            }
+            ++it;
+        }
+    }
+
+    return closure;
+}
+
+void NFA::setTerminationSymbol(const QString &symbol)
+{
+    states[finalState].symbol = symbol;
+}
+
+void DFA::debug() const
+{
+    qDebug() << "DFA has" << count() << "states";
+
+    for (int i = 0; i < count(); ++i) {
+        const State &s = at(i);
+        if (s.transitions.isEmpty()) {
+            qDebug() << "State" << i << "has no transitions";
+        } else {
+            for (TransitionMap::ConstIterator it = s.transitions.constBegin(),
+                 end = s.transitions.constEnd(); it != end; ++it)
+                qDebug() << "transition from state" << i << "to" << it.value() << "through"
+                         << (it.key() == Epsilon ? QString("Epsilon") : QString(char(it.key())));
+        }
+        if (!s.symbol.isEmpty())
+            qDebug() << "State" << i << "leads to symbol" << s.symbol;
+    }
+
+}
+
+DFA DFA::minimize() const
+{
+    QVector<bool> inequivalentStates(count() * count());
+    inequivalentStates.fill(false);
+
+    for (int i = 0; i < count(); ++i)
+        for (int j = 0; j < i; ++j) {
+            if (i != j && at(i).symbol != at(j).symbol)
+                inequivalentStates[i * count() + j] = true;
+        }
+
+    bool done;
+    do {
+        done = true;
+        for (int i = 0; i < count(); ++i)
+            for (int j = 0; j < count(); ++j) {
+                if (i == j)
+                    continue;
+
+                if (inequivalentStates[i * count() + j])
+                    continue;
+
+                if (at(i).transitions.keys() != at(j).transitions.keys()) {
+                    inequivalentStates[i * count() + j] = true;
+                    done = false;
+                    continue;
+                }
+
+                foreach (InputType a, at(i).transitions.keys()) {
+                    int r = at(i).transitions.value(a, -1);
+                    if (r == -1)
+                        continue;
+                    int s = at(j).transitions.value(a, -1);
+                    if (s == -1)
+                        continue;
+
+                    if (inequivalentStates[r * count() + s]
+                        || r == s) {
+                        inequivalentStates[i * count() + j] = true;
+                        done = false;
+                        break;
+                    }
+                }
+            }
+    } while (!done);
+
+    QHash<int, int> statesToEliminate;
+    for (int i = 0; i < count(); ++i)
+        for (int j = 0; j < i; ++j)
+            if (!inequivalentStates[i * count() + j]) {
+                statesToEliminate.insertMulti(i, j);
+            }
+
+    /*
+    qDebug() << "states to eliminiate:" << statesToEliminate.count();;
+    qDebug() << "merging" << statesToEliminate;
+    debug();
+    */
+
+    return *this;
+}
+
+