1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the utils of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    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 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include <QtTest/QtTest>

    43 #define AUTOTEST

    44 #include "../main.cpp"

    45 

    46 class tst_LexGen : public QObject

    47 {

    48     Q_OBJECT

    49 private slots:

    50     void nfa_singleInput();

    51     void nfa_alternating();

    52     void nfa_concatenating();

    53     void nfa_optional();

    54     void nfa_toDFA_data();

    55     void nfa_toDFA();

    56     void lexgen_data();

    57     void lexgen();

    58 };

    59 

    60 void tst_LexGen::nfa_singleInput()

    61 {

    62     NFA nfa = NFA::createSingleInputNFA('a');

    63 

    64     QCOMPARE(nfa.initialState, 0);

    65     QCOMPARE(nfa.finalState, 1);

    66 

    67     QCOMPARE(nfa.states.count(), 2);

    68 

    69     QCOMPARE(nfa.states.at(0).transitions.count(), 1);

    70     QVERIFY(nfa.states.at(0).transitions.contains('a'));

    71     QCOMPARE(nfa.states.at(0).transitions.values('a').count(), 1);

    72     QCOMPARE(nfa.states.at(0).transitions.value('a'), nfa.finalState);

    73 

    74     QVERIFY(nfa.states.at(1).transitions.isEmpty());

    75 }

    76 

    77 void tst_LexGen::nfa_alternating()

    78 {

    79     NFA a = NFA::createSingleInputNFA('a');

    80     NFA b = NFA::createSingleInputNFA('b');

    81     NFA nfa = NFA::createAlternatingNFA(a, b);

    82 

    83     const int initialA = 1;

    84     const int finalA = 2;

    85 

    86     const int initialB = 3;

    87     const int finalB = 4;

    88 

    89     QCOMPARE(nfa.states.count(), 6);

    90 

    91     QCOMPARE(nfa.initialState, 0);

    92     QCOMPARE(nfa.finalState, 5);

    93 

    94     QList<int> initialTransitions = nfa.states.at(0).transitions.values(Epsilon);

    95     QCOMPARE(initialTransitions.count(), 2);

    96     QVERIFY(initialTransitions.contains(initialA));

    97     QVERIFY(initialTransitions.contains(initialB));

    98 

    99     // no need to test the individual a and b NFAs, the other

   100     // autotest already takes care of that. Just check whether

   101     // the epsilon transitions to the final state exist.

   102 

   103     QCOMPARE(nfa.states.at(finalA).transitions.count(), 1);

   104     QCOMPARE(nfa.states.at(finalA).transitions.values(Epsilon).count(), 1);

   105     QCOMPARE(nfa.states.at(finalA).transitions.value(Epsilon), nfa.finalState);

   106 

   107     QCOMPARE(nfa.states.at(finalB).transitions.count(), 1);

   108     QCOMPARE(nfa.states.at(finalB).transitions.values(Epsilon).count(), 1);

   109     QCOMPARE(nfa.states.at(finalB).transitions.value(Epsilon), nfa.finalState);

   110 }

   111 

   112 void tst_LexGen::nfa_concatenating()

   113 {

   114     NFA a = NFA::createSingleInputNFA('a');

   115     NFA b = NFA::createSingleInputNFA('b');

   116     NFA nfa = NFA::createConcatenatingNFA(a, b);

   117 

   118     const int initialA = 1;

   119     const int finalA = 2;

   120 

   121     const int initialB = 3;

   122     const int finalB = 4;

   123 

   124     QCOMPARE(nfa.states.count(), 6);

   125 

   126     QCOMPARE(nfa.initialState, 0);

   127     QCOMPARE(nfa.finalState, 5);

   128 

   129     QCOMPARE(nfa.states.at(0).transitions.count(), 1);

   130     QCOMPARE(nfa.states.at(0).transitions.values(Epsilon).count(), 1);

   131     QCOMPARE(nfa.states.at(0).transitions.value(Epsilon), initialA);

   132 

   133     QCOMPARE(nfa.states.at(finalA).transitions.values(Epsilon).count(), 1);

   134     QCOMPARE(nfa.states.at(finalA).transitions.value(Epsilon), initialB);

   135 

   136     QCOMPARE(nfa.states.at(finalB).transitions.values(Epsilon).count(), 1);

   137     QCOMPARE(nfa.states.at(finalB).transitions.value(Epsilon), nfa.finalState);

   138 }

   139 

   140 void tst_LexGen::nfa_optional()

   141 {

   142     NFA a = NFA::createSingleInputNFA('a');

   143     NFA nfa = NFA::createOptionalNFA(a);

   144 

   145     const int initialA = 1;

   146     const int finalA = 2;

   147 

   148     QCOMPARE(nfa.states.count(), 4);

   149 

   150     QCOMPARE(nfa.initialState, 0);

   151     QCOMPARE(nfa.finalState, 3);

   152 

   153     QCOMPARE(nfa.states.at(0).transitions.count(), 2);

   154     QList<int> initialTransitions = nfa.states.at(0).transitions.values(Epsilon);

   155     QVERIFY(initialTransitions.contains(nfa.finalState));

   156     QVERIFY(initialTransitions.contains(initialA));

   157 

   158     QList<int> finalEpsilonATransitions = nfa.states.at(finalA).transitions.values(Epsilon);

   159     QVERIFY(finalEpsilonATransitions.contains(initialA));

   160     QVERIFY(finalEpsilonATransitions.contains(nfa.finalState));

   161 }

   162 

   163 Q_DECLARE_METATYPE(NFA);

   164 Q_DECLARE_METATYPE(DFA);

   165 

   166 void tst_LexGen::nfa_toDFA_data()

   167 {

   168     QTest::addColumn<NFA>("nfa");

   169     QTest::addColumn<DFA>("expectedDFA");

   170 

   171     NFA a = NFA::createSingleInputNFA('a');

   172     NFA b = NFA::createSingleInputNFA('b');

   173     NFA c = NFA::createSingleInputNFA('c');

   174 

   175     NFA nfa;

   176     DFA dfa;

   177 

   178     dfa.clear();

   179     dfa.resize(3);

   180     dfa[0].transitions.insert('a', 1);

   181     dfa[1].transitions.insert('b', 2);

   182 

   183     nfa = NFA::createConcatenatingNFA(a, b);

   184 

   185     QTest::newRow("simple concat") << nfa << dfa;

   186 

   187     dfa.clear();

   188     dfa.resize(3);

   189     dfa[0].transitions.insert('a', 1);

   190     dfa[0].transitions.insert('b', 2);

   191 

   192     nfa = NFA::createAlternatingNFA(a, b);

   193 

   194     QTest::newRow("simple alternate") << nfa << dfa;

   195 

   196 }

   197 

   198 void tst_LexGen::nfa_toDFA()

   199 {

   200     QFETCH(NFA, nfa);

   201     QFETCH(DFA, expectedDFA);

   202 

   203     DFA dfa = nfa.toDFA();

   204 

   205     QCOMPARE(dfa.count(), expectedDFA.count());

   206     for (int i = 0; i < dfa.count(); ++i) {

   207         if (dfa.at(i).transitions != expectedDFA.at(i).transitions) {

   208             qDebug() << "DFAs differ in state" << i;

   209             qDebug() << "NFA:";

   210             nfa.debug();

   211             qDebug() << "Actual DFA:";

   212             dfa.debug();

   213             qDebug() << "Expected DFA:";

   214             expectedDFA.debug();

   215             QVERIFY(false);

   216         }

   217     }

   218 }

   219 

   220 void tst_LexGen::lexgen_data()

   221 {

   222     QTest::addColumn<QString>("ruleFile");

   223     QTest::addColumn<QString>("input");

   224     QTest::addColumn<QString>("expectedOutput");

   225 

   226     QDir d(QString(SRCDIR));

   227     d.cd("testdata");

   228     foreach (QString test, d.entryList(QDir::Dirs | QDir::NoDotAndDotDot)) {

   229         QString dir = d.absoluteFilePath(test) + '/';

   230         QTest::newRow(qPrintable(test)) 

   231             << dir + "rules.lexgen"

   232             << dir + "input"

   233             << dir + "output"

   234             ;

   235     }

   236 }

   237 

   238 void tst_LexGen::lexgen()

   239 {

   240     QFETCH(QString, ruleFile);

   241     QFETCH(QString, input);

   242     QFETCH(QString, expectedOutput);

   243 

   244     Config conf;

   245     QVERIFY(loadConfig(ruleFile, &conf));

   246     DFA dfa = generateMachine(conf);

   247     QVERIFY(!dfa.isEmpty());

   248     conf.debug = true;

   249 

   250     QFile f(input);

   251     QVERIFY(f.open(QIODevice::ReadOnly));

   252     input = QString::fromUtf8(f.readAll());

   253     f.close();

   254     if (input.endsWith(QLatin1Char('\n')))

   255         input.chop(1);

   256 //    machine.debug();

   257     bool ok = false;

   258     QList<Symbol> symbols = tokenize(dfa, input, &conf, &ok);

   259     QVERIFY(ok);

   260     f.setFileName(expectedOutput);

   261     QVERIFY(f.open(QIODevice::ReadOnly));

   262     QStringList lines;

   263     while (!f.atEnd()) {

   264         QString line = QString::fromUtf8(f.readLine());

   265         if (line.endsWith(QLatin1Char('\n')))

   266             line.chop(1);

   267         lines << line;

   268     }

   269     f.close();

   270 

   271 //    dfa.debug();

   272     QCOMPARE(lines.count(), symbols.count());

   273 

   274     for (int i = 0; i < lines.count(); ++i) {

   275         QStringList l = lines.at(i).split(QChar::fromLatin1('|'));

   276         QCOMPARE(l.count(), 2);

   277         QString expectedToken = l.at(0);

   278         QString expectedLexem = l.at(1);

   279         QCOMPARE(symbols.at(i).token, expectedToken);

   280         QCOMPARE(symbols.at(i).lexem, expectedLexem);

   281     }

   282 }

   283 

   284 QTEST_MAIN(tst_LexGen)

   285 #include "tst_lexgen.moc"