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

35 files changed, 370 insertions, 0 deletions

diff --git a/util/lexgen/tests/testdata/backtrack1/input b/util/lexgen/tests/testdata/backtrack1/input
new file mode 100644
index 0000000000..f5099b509d
--- /dev/null
+++ b/util/lexgen/tests/testdata/backtrack1/input
@@ -0,0 +1 @@
+LETX
diff --git a/util/lexgen/tests/testdata/backtrack1/output b/util/lexgen/tests/testdata/backtrack1/output
new file mode 100644
index 0000000000..6893deb014
--- /dev/null
+++ b/util/lexgen/tests/testdata/backtrack1/output
@@ -0,0 +1 @@
+TOK_LET|LET
diff --git a/util/lexgen/tests/testdata/backtrack1/rules.lexgen b/util/lexgen/tests/testdata/backtrack1/rules.lexgen
new file mode 100644
index 0000000000..ade8a15546
--- /dev/null
+++ b/util/lexgen/tests/testdata/backtrack1/rules.lexgen
@@ -0,0 +1,3 @@
+[Tokens]
+TOK_LET = LET
+TOK_LETXX = LETXX
diff --git a/util/lexgen/tests/testdata/backtrack2/input b/util/lexgen/tests/testdata/backtrack2/input
new file mode 100644
index 0000000000..59ff5b7301
--- /dev/null
+++ b/util/lexgen/tests/testdata/backtrack2/input
@@ -0,0 +1 @@
+LETXTRA
diff --git a/util/lexgen/tests/testdata/backtrack2/output b/util/lexgen/tests/testdata/backtrack2/output
new file mode 100644
index 0000000000..348b382818
--- /dev/null
+++ b/util/lexgen/tests/testdata/backtrack2/output
@@ -0,0 +1,2 @@
+TOK_LET|LET
+TOK_XTRA|XTRA
diff --git a/util/lexgen/tests/testdata/backtrack2/rules.lexgen b/util/lexgen/tests/testdata/backtrack2/rules.lexgen
new file mode 100644
index 0000000000..6f16986e83
--- /dev/null
+++ b/util/lexgen/tests/testdata/backtrack2/rules.lexgen
@@ -0,0 +1,4 @@
+[Tokens]
+TOK_LET = LET
+TOK_LETXX = LETXX
+TOK_XTRA = XTRA
diff --git a/util/lexgen/tests/testdata/casesensitivity/input b/util/lexgen/tests/testdata/casesensitivity/input
new file mode 100644
index 0000000000..72b7f4869c
--- /dev/null
+++ b/util/lexgen/tests/testdata/casesensitivity/input
@@ -0,0 +1 @@
+abcdAbcDABCDeFgEFGefgEfghiHIHihI
diff --git a/util/lexgen/tests/testdata/casesensitivity/output b/util/lexgen/tests/testdata/casesensitivity/output
new file mode 100644
index 0000000000..3a4e819060
--- /dev/null
+++ b/util/lexgen/tests/testdata/casesensitivity/output
@@ -0,0 +1,14 @@
+TOK_AB|ab
+TOK_CD|cd
+TOK_AB|Ab
+TOK_CD|cD
+TOK_AB|AB
+TOK_CD|CD
+TOK_EFG|eFg
+TOK_EFG|EFG
+TOK_EFG|efg
+TOK_EFG|Efg
+TOK_HI|hi
+TOK_HI|HI
+TOK_HI|Hi
+TOK_HI|hI
diff --git a/util/lexgen/tests/testdata/casesensitivity/rules.lexgen b/util/lexgen/tests/testdata/casesensitivity/rules.lexgen
new file mode 100644
index 0000000000..3347587ffe
--- /dev/null
+++ b/util/lexgen/tests/testdata/casesensitivity/rules.lexgen
@@ -0,0 +1,7 @@
+[Options]
+case-insensitive
+[Tokens]
+TOK_AB = ab
+TOK_CD = cd
+TOK_EFG = [e-g]{3}
+TOK_HI = [hi]{2}
diff --git a/util/lexgen/tests/testdata/comments/input b/util/lexgen/tests/testdata/comments/input
new file mode 100644
index 0000000000..03873e044a
--- /dev/null
+++ b/util/lexgen/tests/testdata/comments/input
@@ -0,0 +1 @@
+/* comment with stuff *//*another comment with * stars * inside*/
diff --git a/util/lexgen/tests/testdata/comments/output b/util/lexgen/tests/testdata/comments/output
new file mode 100644
index 0000000000..2395ad1873
--- /dev/null
+++ b/util/lexgen/tests/testdata/comments/output
@@ -0,0 +1,2 @@
+TOK_COMMENT|/* comment with stuff */
+TOK_COMMENT|/*another comment with * stars * inside*/
diff --git a/util/lexgen/tests/testdata/comments/rules.lexgen b/util/lexgen/tests/testdata/comments/rules.lexgen
new file mode 100644
index 0000000000..490c759cc5
--- /dev/null
+++ b/util/lexgen/tests/testdata/comments/rules.lexgen
@@ -0,0 +1,2 @@
+[Tokens]
+TOK_COMMENT = \/\*[^*]*\*+([^/*][^*]*\*+)*\/
diff --git a/util/lexgen/tests/testdata/dot/input b/util/lexgen/tests/testdata/dot/input
new file mode 100644
index 0000000000..e5b0ad6e91
--- /dev/null
+++ b/util/lexgen/tests/testdata/dot/input
@@ -0,0 +1 @@
+afbcxd
diff --git a/util/lexgen/tests/testdata/dot/output b/util/lexgen/tests/testdata/dot/output
new file mode 100644
index 0000000000..6a9afd4ced
--- /dev/null
+++ b/util/lexgen/tests/testdata/dot/output
@@ -0,0 +1,2 @@
+TOK_AB|afb
+TOK_CD|cxd
diff --git a/util/lexgen/tests/testdata/dot/rules.lexgen b/util/lexgen/tests/testdata/dot/rules.lexgen
new file mode 100644
index 0000000000..03873a71bf
--- /dev/null
+++ b/util/lexgen/tests/testdata/dot/rules.lexgen
@@ -0,0 +1,3 @@
+[Tokens]
+TOK_AB = a.b
+TOK_CD = c.d
diff --git a/util/lexgen/tests/testdata/negation/input b/util/lexgen/tests/testdata/negation/input
new file mode 100644
index 0000000000..9447b8005d
--- /dev/null
+++ b/util/lexgen/tests/testdata/negation/input
@@ -0,0 +1 @@
+aycabd
diff --git a/util/lexgen/tests/testdata/negation/output b/util/lexgen/tests/testdata/negation/output
new file mode 100644
index 0000000000..0b73263fb9
--- /dev/null
+++ b/util/lexgen/tests/testdata/negation/output
@@ -0,0 +1,2 @@
+TOK_A|ayc
+TOK_B|abd
diff --git a/util/lexgen/tests/testdata/negation/rules.lexgen b/util/lexgen/tests/testdata/negation/rules.lexgen
new file mode 100644
index 0000000000..179810b3a0
--- /dev/null
+++ b/util/lexgen/tests/testdata/negation/rules.lexgen
@@ -0,0 +1,3 @@
+[Tokens]
+TOK_A = a[^b]c
+TOK_B = abd
diff --git a/util/lexgen/tests/testdata/quoteinset/input b/util/lexgen/tests/testdata/quoteinset/input
new file mode 100644
index 0000000000..5a9b6804a9
--- /dev/null
+++ b/util/lexgen/tests/testdata/quoteinset/input
@@ -0,0 +1 @@
+"a
diff --git a/util/lexgen/tests/testdata/quoteinset/output b/util/lexgen/tests/testdata/quoteinset/output
new file mode 100644
index 0000000000..7ba8890d5d
--- /dev/null
+++ b/util/lexgen/tests/testdata/quoteinset/output
@@ -0,0 +1 @@
+TOK_QUOTEA|"a
diff --git a/util/lexgen/tests/testdata/quoteinset/rules.lexgen b/util/lexgen/tests/testdata/quoteinset/rules.lexgen
new file mode 100644
index 0000000000..9838276a7e
--- /dev/null
+++ b/util/lexgen/tests/testdata/quoteinset/rules.lexgen
@@ -0,0 +1,2 @@
+[Tokens]
+TOK_QUOTEA = ["]a
diff --git a/util/lexgen/tests/testdata/quotes/input b/util/lexgen/tests/testdata/quotes/input
new file mode 100644
index 0000000000..ac5445055d
--- /dev/null
+++ b/util/lexgen/tests/testdata/quotes/input
@@ -0,0 +1 @@
+quotedstring
diff --git a/util/lexgen/tests/testdata/quotes/output b/util/lexgen/tests/testdata/quotes/output
new file mode 100644
index 0000000000..c538e32d75
--- /dev/null
+++ b/util/lexgen/tests/testdata/quotes/output
@@ -0,0 +1 @@
+TOK_STR|quotedstring
diff --git a/util/lexgen/tests/testdata/quotes/rules.lexgen b/util/lexgen/tests/testdata/quotes/rules.lexgen
new file mode 100644
index 0000000000..d528cdd589
--- /dev/null
+++ b/util/lexgen/tests/testdata/quotes/rules.lexgen
@@ -0,0 +1,2 @@
+[Tokens]
+TOK_STR = "quotedstring"
diff --git a/util/lexgen/tests/testdata/simple/input b/util/lexgen/tests/testdata/simple/input
new file mode 100644
index 0000000000..acbe86c7c8
--- /dev/null
+++ b/util/lexgen/tests/testdata/simple/input
@@ -0,0 +1 @@
+abcd
diff --git a/util/lexgen/tests/testdata/simple/output b/util/lexgen/tests/testdata/simple/output
new file mode 100644
index 0000000000..a37a58ea31
--- /dev/null
+++ b/util/lexgen/tests/testdata/simple/output
@@ -0,0 +1,2 @@
+TOK_AB|ab
+TOK_CD|cd
diff --git a/util/lexgen/tests/testdata/simple/rules.lexgen b/util/lexgen/tests/testdata/simple/rules.lexgen
new file mode 100644
index 0000000000..5d958c429a
--- /dev/null
+++ b/util/lexgen/tests/testdata/simple/rules.lexgen
@@ -0,0 +1,3 @@
+[Tokens]
+TOK_AB = ab
+TOK_CD = cd
diff --git a/util/lexgen/tests/testdata/subsets1/input b/util/lexgen/tests/testdata/subsets1/input
new file mode 100644
index 0000000000..47f66d1c94
--- /dev/null
+++ b/util/lexgen/tests/testdata/subsets1/input
@@ -0,0 +1 @@
+abaf
diff --git a/util/lexgen/tests/testdata/subsets1/output b/util/lexgen/tests/testdata/subsets1/output
new file mode 100644
index 0000000000..75dd9361bc
--- /dev/null
+++ b/util/lexgen/tests/testdata/subsets1/output
@@ -0,0 +1,2 @@
+TOK_AB|ab
+TOK_AZ|af
diff --git a/util/lexgen/tests/testdata/subsets1/rules.lexgen b/util/lexgen/tests/testdata/subsets1/rules.lexgen
new file mode 100644
index 0000000000..94f51a91e2
--- /dev/null
+++ b/util/lexgen/tests/testdata/subsets1/rules.lexgen
@@ -0,0 +1,3 @@
+[Tokens]
+TOK_AB = ab
+TOK_AZ = a[a-z]
diff --git a/util/lexgen/tests/testdata/subsets2/input b/util/lexgen/tests/testdata/subsets2/input
new file mode 100644
index 0000000000..4d0dc3ad82
--- /dev/null
+++ b/util/lexgen/tests/testdata/subsets2/input
@@ -0,0 +1 @@
+abd
diff --git a/util/lexgen/tests/testdata/subsets2/output b/util/lexgen/tests/testdata/subsets2/output
new file mode 100644
index 0000000000..d5a7bc5bb7
--- /dev/null
+++ b/util/lexgen/tests/testdata/subsets2/output
@@ -0,0 +1,3 @@
+TOK_A|a
+TOK_B|b
+TOK_D|d
diff --git a/util/lexgen/tests/testdata/subsets2/rules.lexgen b/util/lexgen/tests/testdata/subsets2/rules.lexgen
new file mode 100644
index 0000000000..e0a76294bc
--- /dev/null
+++ b/util/lexgen/tests/testdata/subsets2/rules.lexgen
@@ -0,0 +1,4 @@
+[Tokens]
+TOK_D = [abcd]
+TOK_B = [bc]
+TOK_A = a
diff --git a/util/lexgen/tests/tests.pro b/util/lexgen/tests/tests.pro
new file mode 100644
index 0000000000..eb04439a13
--- /dev/null
+++ b/util/lexgen/tests/tests.pro
@@ -0,0 +1,6 @@
+CONFIG += qtestlib
+SOURCES += tst_lexgen.cpp
+TARGET = tst_lexgen
+include(../lexgen.pri)
+QT = core
+DEFINES += SRCDIR=\\\"$$PWD\\\"
diff --git a/util/lexgen/tests/tst_lexgen.cpp b/util/lexgen/tests/tst_lexgen.cpp
new file mode 100644
index 0000000000..c80de646d6
--- /dev/null
+++ b/util/lexgen/tests/tst_lexgen.cpp
@@ -0,0 +1,285 @@
+/****************************************************************************
+**
+** 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 <QtTest/QtTest>
+#define AUTOTEST
+#include "../main.cpp"
+
+class tst_LexGen : public QObject
+{
+    Q_OBJECT
+private slots:
+    void nfa_singleInput();
+    void nfa_alternating();
+    void nfa_concatenating();
+    void nfa_optional();
+    void nfa_toDFA_data();
+    void nfa_toDFA();
+    void lexgen_data();
+    void lexgen();
+};
+
+void tst_LexGen::nfa_singleInput()
+{
+    NFA nfa = NFA::createSingleInputNFA('a');
+
+    QCOMPARE(nfa.initialState, 0);
+    QCOMPARE(nfa.finalState, 1);
+
+    QCOMPARE(nfa.states.count(), 2);
+
+    QCOMPARE(nfa.states.at(0).transitions.count(), 1);
+    QVERIFY(nfa.states.at(0).transitions.contains('a'));
+    QCOMPARE(nfa.states.at(0).transitions.values('a').count(), 1);
+    QCOMPARE(nfa.states.at(0).transitions.value('a'), nfa.finalState);
+
+    QVERIFY(nfa.states.at(1).transitions.isEmpty());
+}
+
+void tst_LexGen::nfa_alternating()
+{
+    NFA a = NFA::createSingleInputNFA('a');
+    NFA b = NFA::createSingleInputNFA('b');
+    NFA nfa = NFA::createAlternatingNFA(a, b);
+
+    const int initialA = 1;
+    const int finalA = 2;
+
+    const int initialB = 3;
+    const int finalB = 4;
+
+    QCOMPARE(nfa.states.count(), 6);
+
+    QCOMPARE(nfa.initialState, 0);
+    QCOMPARE(nfa.finalState, 5);
+
+    QList<int> initialTransitions = nfa.states.at(0).transitions.values(Epsilon);
+    QCOMPARE(initialTransitions.count(), 2);
+    QVERIFY(initialTransitions.contains(initialA));
+    QVERIFY(initialTransitions.contains(initialB));
+
+    // no need to test the individual a and b NFAs, the other
+    // autotest already takes care of that. Just check whether
+    // the epsilon transitions to the final state exist.
+
+    QCOMPARE(nfa.states.at(finalA).transitions.count(), 1);
+    QCOMPARE(nfa.states.at(finalA).transitions.values(Epsilon).count(), 1);
+    QCOMPARE(nfa.states.at(finalA).transitions.value(Epsilon), nfa.finalState);
+
+    QCOMPARE(nfa.states.at(finalB).transitions.count(), 1);
+    QCOMPARE(nfa.states.at(finalB).transitions.values(Epsilon).count(), 1);
+    QCOMPARE(nfa.states.at(finalB).transitions.value(Epsilon), nfa.finalState);
+}
+
+void tst_LexGen::nfa_concatenating()
+{
+    NFA a = NFA::createSingleInputNFA('a');
+    NFA b = NFA::createSingleInputNFA('b');
+    NFA nfa = NFA::createConcatenatingNFA(a, b);
+
+    const int initialA = 1;
+    const int finalA = 2;
+
+    const int initialB = 3;
+    const int finalB = 4;
+
+    QCOMPARE(nfa.states.count(), 6);
+
+    QCOMPARE(nfa.initialState, 0);
+    QCOMPARE(nfa.finalState, 5);
+
+    QCOMPARE(nfa.states.at(0).transitions.count(), 1);
+    QCOMPARE(nfa.states.at(0).transitions.values(Epsilon).count(), 1);
+    QCOMPARE(nfa.states.at(0).transitions.value(Epsilon), initialA);
+
+    QCOMPARE(nfa.states.at(finalA).transitions.values(Epsilon).count(), 1);
+    QCOMPARE(nfa.states.at(finalA).transitions.value(Epsilon), initialB);
+
+    QCOMPARE(nfa.states.at(finalB).transitions.values(Epsilon).count(), 1);
+    QCOMPARE(nfa.states.at(finalB).transitions.value(Epsilon), nfa.finalState);
+}
+
+void tst_LexGen::nfa_optional()
+{
+    NFA a = NFA::createSingleInputNFA('a');
+    NFA nfa = NFA::createOptionalNFA(a);
+
+    const int initialA = 1;
+    const int finalA = 2;
+
+    QCOMPARE(nfa.states.count(), 4);
+
+    QCOMPARE(nfa.initialState, 0);
+    QCOMPARE(nfa.finalState, 3);
+
+    QCOMPARE(nfa.states.at(0).transitions.count(), 2);
+    QList<int> initialTransitions = nfa.states.at(0).transitions.values(Epsilon);
+    QVERIFY(initialTransitions.contains(nfa.finalState));
+    QVERIFY(initialTransitions.contains(initialA));
+
+    QList<int> finalEpsilonATransitions = nfa.states.at(finalA).transitions.values(Epsilon);
+    QVERIFY(finalEpsilonATransitions.contains(initialA));
+    QVERIFY(finalEpsilonATransitions.contains(nfa.finalState));
+}
+
+Q_DECLARE_METATYPE(NFA);
+Q_DECLARE_METATYPE(DFA);
+
+void tst_LexGen::nfa_toDFA_data()
+{
+    QTest::addColumn<NFA>("nfa");
+    QTest::addColumn<DFA>("expectedDFA");
+
+    NFA a = NFA::createSingleInputNFA('a');
+    NFA b = NFA::createSingleInputNFA('b');
+    NFA c = NFA::createSingleInputNFA('c');
+
+    NFA nfa;
+    DFA dfa;
+
+    dfa.clear();
+    dfa.resize(3);
+    dfa[0].transitions.insert('a', 1);
+    dfa[1].transitions.insert('b', 2);
+
+    nfa = NFA::createConcatenatingNFA(a, b);
+
+    QTest::newRow("simple concat") << nfa << dfa;
+
+    dfa.clear();
+    dfa.resize(3);
+    dfa[0].transitions.insert('a', 1);
+    dfa[0].transitions.insert('b', 2);
+
+    nfa = NFA::createAlternatingNFA(a, b);
+
+    QTest::newRow("simple alternate") << nfa << dfa;
+
+}
+
+void tst_LexGen::nfa_toDFA()
+{
+    QFETCH(NFA, nfa);
+    QFETCH(DFA, expectedDFA);
+
+    DFA dfa = nfa.toDFA();
+
+    QCOMPARE(dfa.count(), expectedDFA.count());
+    for (int i = 0; i < dfa.count(); ++i) {
+        if (dfa.at(i).transitions != expectedDFA.at(i).transitions) {
+            qDebug() << "DFAs differ in state" << i;
+            qDebug() << "NFA:";
+            nfa.debug();
+            qDebug() << "Actual DFA:";
+            dfa.debug();
+            qDebug() << "Expected DFA:";
+            expectedDFA.debug();
+            QVERIFY(false);
+        }
+    }
+}
+
+void tst_LexGen::lexgen_data()
+{
+    QTest::addColumn<QString>("ruleFile");
+    QTest::addColumn<QString>("input");
+    QTest::addColumn<QString>("expectedOutput");
+
+    QDir d(QString(SRCDIR));
+    d.cd("testdata");
+    foreach (QString test, d.entryList(QDir::Dirs | QDir::NoDotAndDotDot)) {
+        QString dir = d.absoluteFilePath(test) + '/';
+        QTest::newRow(qPrintable(test)) 
+            << dir + "rules.lexgen"
+            << dir + "input"
+            << dir + "output"
+            ;
+    }
+}
+
+void tst_LexGen::lexgen()
+{
+    QFETCH(QString, ruleFile);
+    QFETCH(QString, input);
+    QFETCH(QString, expectedOutput);
+
+    Config conf;
+    QVERIFY(loadConfig(ruleFile, &conf));
+    DFA dfa = generateMachine(conf);
+    QVERIFY(!dfa.isEmpty());
+    conf.debug = true;
+
+    QFile f(input);
+    QVERIFY(f.open(QIODevice::ReadOnly));
+    input = QString::fromUtf8(f.readAll());
+    f.close();
+    if (input.endsWith(QLatin1Char('\n')))
+        input.chop(1);
+//    machine.debug();
+    bool ok = false;
+    QList<Symbol> symbols = tokenize(dfa, input, &conf, &ok);
+    QVERIFY(ok);
+    f.setFileName(expectedOutput);
+    QVERIFY(f.open(QIODevice::ReadOnly));
+    QStringList lines;
+    while (!f.atEnd()) {
+        QString line = QString::fromUtf8(f.readLine());
+        if (line.endsWith(QLatin1Char('\n')))
+            line.chop(1);
+        lines << line;
+    }
+    f.close();
+
+//    dfa.debug();
+    QCOMPARE(lines.count(), symbols.count());
+
+    for (int i = 0; i < lines.count(); ++i) {
+        QStringList l = lines.at(i).split(QChar::fromLatin1('|'));
+        QCOMPARE(l.count(), 2);
+        QString expectedToken = l.at(0);
+        QString expectedLexem = l.at(1);
+        QCOMPARE(symbols.at(i).token, expectedToken);
+        QCOMPARE(symbols.at(i).lexem, expectedLexem);
+    }
+}
+
+QTEST_MAIN(tst_LexGen)
+#include "tst_lexgen.moc"