SynTreeGen.cpp

/*
* Copyright 2019 Rochus Keller <mailto:me@rochus-keller.ch>
*
* This file is part of the EbnfStudio application.
*
* The following is the license that applies to this copy of the
* application. For a license to use the application under conditions
* other than those described here, please email to me@rochus-keller.ch.
*
* GNU General Public License Usage
* This file may be used under the terms of the GNU General Public
* License (GPL) versions 2.0 or 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 GNU General Public Licensing requirements will be met:
* http://www.fsf.org/licensing/licenses/info/GPLv2.html and
* http://www.gnu.org/copyleft/gpl.html.
*/

#include "SynTreeGen.h"
#include "EbnfSyntax.h"
#include "EbnfAnalyzer.h"
#include "GenUtils.h"
#include <QDir>
#include <QTextStream>
#include <QtDebug>

//#define _TT_USE_MEMCMP_
// if enabled the overall time measured with LisaPascal parser is ~1% slower, but the measurement error is likeli higher

bool SynTreeGen::generateTree(const QString& ebnfPath, EbnfSyntax* syn, bool includeNt)
{
    Q_ASSERT( syn != 0 );

    const QByteArray nameSpace = syn->getPragmaFirst("%namespace");
    const QByteArray nameSpace2 = nameSpace.isEmpty() ? nameSpace : ( nameSpace + "::" );
    QByteArray module = syn->getPragmaFirst("%module");
    if( !module.isEmpty() )
        module = module + "/";
    const bool parentPtr = !syn->getPragmaFirst("%parentptr").isEmpty();

    QDir dir = QFileInfo(ebnfPath).dir();

    QFile header( dir.absoluteFilePath( nameSpace + "SynTree.h") );
    header.open( QIODevice::WriteOnly );
    QTextStream hout(&header);
    hout.setCodec("utf-8");

    const QByteArray stopLabel = "__" + nameSpace.toUpper() + ( !nameSpace.isEmpty() ? "_" : "" ) + "SYNTREE__";
    hout << "#ifndef " << stopLabel << endl;
    hout << "#define " << stopLabel << endl;
    hout << "// This file was automatically generated by EbnfStudio; don't modify it!" << endl;
    hout << endl;
    hout << "#include <" << module << nameSpace << "TokenType.h>" << endl;
    hout << "#include <" << module << nameSpace << "Token.h>" << endl;
    hout << "#include <QList>" << endl;
    hout << endl;

    if( !nameSpace.isEmpty() )
        hout << "namespace " << nameSpace << " {" << endl;

    hout << endl;
    hout << "\t" << "struct SynTree {" << endl;

    typedef QMap<QString,const Ast::Definition*> DefSort;
    DefSort sort;
    foreach( const Ast::Definition* d, syn->getDefs() )
    {
        if( d->d_tok.d_op != EbnfToken::Transparent && d->d_node != 0 )
            // Add the symol unless explicitly suppressed or pseudoterminal, && !d->d_usedBy.isEmpty() )
            sort.insert( GenUtils::escapeDollars( d->d_tok.d_val.toStr() ), d );
    }

    DefSort::const_iterator i;
    if( includeNt )
    {
        hout << "\t\t" << "enum ParserRule {" << endl;
        hout << "\t\t\t" << "R_First = TT_Max + 1," << endl;
        for( i = sort.begin(); i != sort.end(); ++i )
        {
            hout << "\t\t\t" << "R_" << i.key();
            if( i.value()->d_tok.d_op == EbnfToken::Skip )
                hout << "_";
            hout << "," << endl;
        }
        hout << "\t\t\t" << "R_Last" << endl;
        hout << "\t\t" << "};" << endl;
    }

    hout << "\t\t" << "SynTree(quint16 r = Tok_Invalid, const Token& = Token() );" << endl;
    hout << "\t\t" << "SynTree(const Token& t ):d_tok(t)" << ( parentPtr ? ",d_parent(0)": "" ) << "{}" << endl;
    hout << "\t\t" << /* "virtual " << */ "~SynTree() { foreach(SynTree* n, d_children) delete n; }" << endl;
    hout << endl;
    hout << "\t\t" << "static const char* rToStr( quint16 r );" << endl;
    hout << endl;
    hout << "\t\t" << nameSpace2 << "Token d_tok;" << endl;
    hout << "\t\t" << "QList<SynTree*> d_children;" << endl;
    if( parentPtr )
        hout << "\t\t" << "SynTree* d_parent;" << endl;
    hout << "\t" << "};" << endl;
    hout << endl;
    if( !nameSpace.isEmpty() )
        hout << "}" << endl;
    hout << "#endif // " << stopLabel << endl;

    QFile body( dir.absoluteFilePath( nameSpace + "SynTree.cpp") );
    body.open( QIODevice::WriteOnly );
    QTextStream bout(&body);
    bout.setCodec("utf-8");

    bout << "// This file was automatically generated by EbnfStudio; don't modify it!" << endl;
    bout << "#include \"" << nameSpace << "SynTree.h\"" << endl;
#ifdef _TT_USE_MEMCMP_
    bout << "#include \"<string.h>\"" << endl;
#endif
    if( !nameSpace.isEmpty() )
        bout << "using namespace " << nameSpace << ";" << endl;
    bout << endl;

    bout << "SynTree::SynTree(quint16 r, const Token& t ):d_tok(r)" <<
            ( parentPtr ? ",d_parent(0)": "" ) << "{" << endl;
    bout << "\t" << "d_tok.d_lineNr = t.d_lineNr;" << endl;
    bout << "\t" << "d_tok.d_colNr = t.d_colNr;" << endl;
    bout << "\t" << "d_tok.d_sourcePath = t.d_sourcePath;" << endl;
    // don't copy: bout << "\t" << "d_tok.d_val = t.d_val;" << endl;
    bout << "}" << endl;
    bout << endl;

    bout << "const char* SynTree::rToStr( quint16 r ) {" << endl;
    if( includeNt )
    {
        bout << "\t" << "switch(r) {" << endl;
        for( i = sort.begin(); i != sort.end(); ++i )
        {
            bout << "\t\tcase R_" << i.key();
            if( i.value()->d_tok.d_op == EbnfToken::Skip )
                bout << "_";
            bout << ": return \"" << i.value()->d_tok.d_val.toStr() << "\";" << endl;
        }
        bout << "\tdefault: if(r<R_First) return tokenTypeName(r); else return \"\";" << endl;
        bout << "}" << endl;
    }else
        bout << "\t\t" << "return tokenTypeName(r);" << endl;
    bout << "}" << endl;

    return true;
}


SynTreeGen::SynTreeGen()
{

}

static QString escapeCpp( QString in )
{
    in.replace( "\\", "\\\\" );
    in.replace( "\"", "\\\"" );
    return in;
}

SynTreeGen::TokenNameValueList SynTreeGen::generateTokenList(EbnfSyntax* syn, int* startOfSpecial )
{
    TokenNameValueList res;

    const QStringList tokens = GenUtils::orderedTokenList( EbnfAnalyzer::collectAllTerminalStrings( syn ), false );
    const QStringList specials = EbnfAnalyzer::collectAllTerminalProductions( syn );

    // Tok_Invalid ist hier absichtlich nicht enthalten, da z.B. Coco/R Index=0 für _EOF beansprucht

    res.append( qMakePair(QString("Literals"),QString()) );

    bool keyWordSection = false;
    for( int i = 0; i < tokens.size(); i++ )
    {
        if( !keyWordSection && GenUtils::containsAlnum( tokens[i] ) )
        {
            res.append( qMakePair(QString("Keywords"),QString()) );
            keyWordSection = true;
        }
        res.append( qMakePair(GenUtils::symToString(tokens[i]),tokens[i]) );
    }
    if( startOfSpecial )
        *startOfSpecial = res.size();

    res.append( qMakePair(QByteArray("Specials"),QByteArray()) );

    foreach( const QString& t, specials )
        res.append( qMakePair(GenUtils::escapeDollars(t),t) );

    res.append( qMakePair(QByteArray("Eof"),QByteArray("<eof>") ) );
    res.append( qMakePair(QByteArray("MaxToken"),QByteArray()) );

    return res;
}

static inline bool lessThan( const QPair<QString,QString>& lhs, const QPair<QString,QString>& rhs )
{
    return lhs.second < rhs.second;
}

struct CharBin
{
    QChar d_c;
    QString d_tok;
    QList<CharBin*> d_subs;
    CharBin(QChar c = 0 ):d_c(c){}
    ~CharBin(){ foreach( CharBin* b, d_subs ) delete b; }
    void print(int level = 0)
    {
        qDebug() << QByteArray(level*2,'_').data() << d_c << ( !d_tok.isEmpty() ? d_tok : "" );
        foreach( CharBin* b, d_subs )
            b->print(level+1);
    }
};

static void fillCharBin(const SynTreeGen::TokenNameValueList& tokens, int start, int len, int depth, CharBin* super )
{
    int n = start;
    const int size = qMin( tokens.size(), start + len );
    while( n < size )
    {
        if( depth < tokens[n].second.size() )
        {
            const QChar leadChar = tokens[n].second[depth];
            int count = 1;
            while( n+count < size && depth < tokens[n+count].second.size() &&
                   tokens[n+count].second[depth] == leadChar )
                count++;
            CharBin* bin = new CharBin( leadChar );
            super->d_subs.append( bin );
            fillCharBin( tokens, n, count, depth + 1, bin );
            n += count;
        }else
        {
            if( !tokens[n].second.isEmpty() )
                super->d_tok = tokens[n].first;
            n++;
        }
    }
}

static inline QString escChar( QChar c )
{
    if( c == '\'' )
        return "\\'";
    else
        return QString(1,c);
}

#ifdef _TT_USE_MEMCMP_
static inline QString collect( const CharBin& bin )
{
    if( !bin.d_subs.isEmpty() )
        return escChar(bin.d_c) + collect( *bin.d_subs.first() );
    else
        return escChar(bin.d_c);
}

static inline int checkLinear( const CharBin& bin )
{
    if( bin.d_subs.size() > 1 )
        return -1;
    else if( bin.d_subs.size() == 1 )
    {
        if( !bin.d_tok.isEmpty() )
            return -1;
        const int sub = checkLinear(*bin.d_subs.first());
        if( sub == -1 )
            return sub;
        else
            return 1 + sub;
    }else
        return 1;
}

static inline QString lastTok( const CharBin& bin )
{
    if( !bin.d_subs.isEmpty() )
        return lastTok( *bin.d_subs.first() );
    else
        return bin.d_tok;
}

#endif

static void generateLexer( QTextStream& bout, const CharBin& bin, int level = 0 )
{
    const QByteArray ws = "\t\t" + QByteArray(level,'\t');
    const QByteArray plus = level > 0 ? QByteArray("+") + QByteArray::number(level) : QByteArray();
    if( bin.d_subs.size() == 1 )
    {
#ifdef _TT_USE_MEMCMP_
        int len = checkLinear(*bin.d_subs[0]);
        if( len > 1 )
        {
            const QString cmp = collect(*bin.d_subs[0]);
            bout << ws << "if( memcmp( str+" << level << ", \"" << cmp << "\", " << len << ") == 0 ) {" << endl;
            bout << ws << "\t" <<  "res = Tok_" << lastTok(bin) << "; i += " << level + len << ";" << endl;
            if( !bin.d_tok.isEmpty() )
                bout << ws << "} else {" << endl << ws << "\t"
                     << "res = Tok_" << bin.d_tok << "; i += " << level << ";" << endl;
            bout << ws << "}" << endl;
            return;
        }
#endif
        bout << ws << "if( at(str,len,i" << plus << ") == '" <<
                escChar(bin.d_subs[0]->d_c) << "' ){" << endl;
        generateLexer(bout, *bin.d_subs[0], level+1 );
        if( !bin.d_tok.isEmpty() )
            bout << ws << "} else {" << endl << ws << "\t"
                 << "res = Tok_" << bin.d_tok << "; i += " << level << ";" << endl;
        bout << ws << "}" << endl;
    }else if( !bin.d_subs.isEmpty() )
    {
        bout << ws << "switch( at(str,len,i" << plus << ") ){" << endl;
        for( int i = 0; i < bin.d_subs.size(); i++ )
        {
            bout << ws << "case '" << escChar(bin.d_subs[i]->d_c) << "':" << endl;
            generateLexer(bout, *bin.d_subs[i], level+1 );
            bout << ws << "\t" << "break;" << endl;
        }
        if( !bin.d_tok.isEmpty() )
            bout << ws << "default:" << endl
                 << ws << "\t" << "res = Tok_" << bin.d_tok << "; i += " << level << ";" << endl
                 << ws << "\t" << "break;" << endl;
        bout << ws << "}" << endl;
    }else
    {
        Q_ASSERT( bin.d_subs.isEmpty() );
        // at the bottom of the if-tree
        if( !bin.d_tok.isEmpty() )
            bout << ws << "res = Tok_" << bin.d_tok << "; i += " << level << ";" << endl;
    }
}

bool SynTreeGen::generateTt(const QString& ebnfPath, EbnfSyntax* syn, bool includeLex, bool includeNt )
{
    Q_ASSERT( syn != 0 );

    const QString nameSpace = syn->getPragmaFirst("%namespace").toStr();

    QDir dir = QFileInfo(ebnfPath).dir();

    QFile header( dir.absoluteFilePath( nameSpace + "TokenType.h") );
    header.open( QIODevice::WriteOnly );
    QTextStream hout(&header);
    hout.setCodec("utf-8");

    const QString stopLabel = "__" + nameSpace.toUpper() + ( !nameSpace.isEmpty() ? "_" : "" ) + "TOKENTYPE__";
    hout << "#ifndef " << stopLabel << endl;
    hout << "#define " << stopLabel << endl;
    hout << "// This file was automatically generated by EbnfStudio; don't modify it!" << endl;
    hout << endl << endl;

    hout << "#include <QByteArray>" << endl << endl;

    foreach( const EbnfToken::Sym& define, syn->getDefines() )
    {
        hout << "#define " << nameSpace.toUpper() << ( !nameSpace.isEmpty() ? "_" : "" )
             << define.toStr().toUpper() << endl;
    }
    if( !syn->getDefines().isEmpty() )
        hout << endl;

    if( !nameSpace.isEmpty() )
        hout << "namespace " << nameSpace << " {" << endl;

    int startOfSpecial = 0;
    TokenNameValueList tokens = generateTokenList(syn,&startOfSpecial);

    hout << "\t" << "enum TokenType {" << endl;
    hout << "\t\t" << "Tok_Invalid = 0," << endl;

    for( int i = 0; i < tokens.size(); i++ )
    {
        if( tokens[i].second.isEmpty() )
            hout << endl << "\t\t" << "TT_" << tokens[i].first << "," << endl;
        else
            hout << "\t\t" << "Tok_" << tokens[i].first << "," << endl;
    }
    if( includeNt )
    {
        hout << endl << "\t\t" << "TT_Nonterminals," << endl;

        foreach( const Ast::Definition* d, syn->getDefs() )
        {
            if( d->d_tok.d_op == EbnfToken::Normal && !d->d_usedBy.isEmpty() && d->d_node != 0 )
                hout << "\t\t" << "R_" << GenUtils::escapeDollars( d->d_tok.d_val.toStr() ) << "," << endl;
        }
    }
    hout << endl << "\t\t" << "TT_Max" << endl;
    hout << "\t" << "};" << endl;

    hout << endl;

    hout << "\t" << "const char* tokenTypeString( int ); // Pretty with punctuation chars" << endl;
    hout << "\t" << "const char* tokenTypeName( int ); // Just the names without punctuation chars" << endl;
    hout << "\t" << "bool tokenTypeIsLiteral( int );" << endl;
    hout << "\t" << "bool tokenTypeIsKeyword( int );" << endl;
    hout << "\t" << "bool tokenTypeIsSpecial( int );" << endl;
    if( includeNt )
        hout << "\t" << "bool tokenTypeIsNonterminal( int );" << endl;
    if( includeLex )
    {
        hout << "\t" << "TokenType tokenTypeFromString( const QByteArray& str, int* pos = 0 );" << endl;
        hout << "\t" << "TokenType tokenTypeFromString( const char* str, quint32 len, int* pos = 0 );" << endl;
    }


    if( !nameSpace.isEmpty() )
        hout << "}" << endl; // end namespace

    hout << "#endif // " << stopLabel << endl;

    QFile body( dir.absoluteFilePath( nameSpace + "TokenType.cpp") );
    body.open( QIODevice::WriteOnly );
    QTextStream bout(&body);
    bout.setCodec("utf-8");

    bout << "// This file was automatically generated by EbnfStudio; don't modify it!" << endl;
    bout << "#include \"" << nameSpace << "TokenType.h\"" << endl;
    bout << endl;

    if( !nameSpace.isEmpty() )
        bout << "namespace " << nameSpace << " {"<< endl;

    bout << "\t" << "const char* tokenTypeString( int r ) {" << endl;
    bout << "\t\t" << "switch(r) {" << endl;
    bout << "\t\t\t" << "case Tok_Invalid: return \"<invalid>\";" << endl;

    for( int i = 0; i < tokens.size(); i++ )
    {
        if( !tokens[i].second.isEmpty() )
            bout << "\t\t\t" << "case Tok_" << tokens[i].first <<
                ": return \"" << escapeCpp( tokens[i].second ) << "\";" << endl;
    }
    if( includeNt )
    {
        foreach( const Ast::Definition* d, syn->getDefs() )
        {
            if( d->d_tok.d_op == EbnfToken::Normal && !d->d_usedBy.isEmpty() && d->d_node != 0 )
                bout << "\t\t\t" << "case R_" << GenUtils::escapeDollars( d->d_tok.d_val.toStr() ) <<
                        ": return \"" << d->d_tok.d_val.toStr() << "\";" << endl;
        }
    }

    bout << "\t\t\t" << "default: return \"\";" << endl;
    bout << "\t\t" << "}" << endl; // switch
    bout << "\t" << "}" << endl; // function

    bout << "\t" << "const char* tokenTypeName( int r ) {" << endl;
    bout << "\t\t" << "switch(r) {" << endl;
    bout << "\t\t\t" << "case Tok_Invalid: return \"Tok_Invalid\";" << endl;

    for( int i = 0; i < tokens.size(); i++ )
    {
        if( !tokens[i].second.isEmpty() )
            bout << "\t\t\t" << "case Tok_" << tokens[i].first <<
                ": return \"Tok_" << tokens[i].first << "\";" << endl;
    }
    if( includeNt )
    {
        foreach( const Ast::Definition* d, syn->getDefs() )
        {
            const QString name = GenUtils::escapeDollars( d->d_tok.d_val.toStr() );
            if( d->d_tok.d_op == EbnfToken::Normal && !d->d_usedBy.isEmpty() && d->d_node != 0 )
                bout << "\t\t\t" << "case R_" << name <<
                        ": return \"R_" << name << "\";" << endl;
        }
    }

    bout << "\t\t\t" << "default: return \"\";" << endl;
    bout << "\t\t" << "}" << endl; // switch
    bout << "\t" << "}" << endl; // function


    bout << "\t" << "bool tokenTypeIsLiteral( int r ) {" << endl;
    bout << "\t\t" << "return r > TT_Literals && r < TT_Keywords;" << endl;
    bout << "\t" << "}" << endl; // function

    bout << "\t" << "bool tokenTypeIsKeyword( int r ) {" << endl;
    bout << "\t\t" << "return r > TT_Keywords && r < TT_Specials;" << endl;
    bout << "\t" << "}" << endl; // function

    bout << "\t" << "bool tokenTypeIsSpecial( int r ) {" << endl;
    if( includeNt )
        bout << "\t\t" << "return r > TT_Specials && r < TT_Nonterminals;" << endl;
    else
        bout << "\t\t" << "return r > TT_Specials && r < TT_Max;" << endl;
    bout << "\t" << "}" << endl; // function

    if( includeNt )
    {
        bout << "\t" << "bool tokenTypeIsNonterminal( int r ) {" << endl;
        bout << "\t\t" << "return r > TT_Nonterminals && r < TT_Max;" << endl;
        bout << "\t" << "}" << endl; // function
    }

    if( includeLex )
    {
        bout << "\t" << "static inline char at( const char* str, quint32 len, int i ){" << endl;
        bout << "\t\t" << "return ( i < len ? str[i] : 0 );" << endl;
        bout << "\t" << "}" << endl; // function


        bout << "\t" << "TokenType tokenTypeFromString( const QByteArray& str, int* pos ) {" << endl;
        bout << "\t\t" << "return tokenTypeFromString(str.constData(),str.size(),pos);" << endl;
        bout << "\t" << "}" << endl; // function

        bout << "\t" << "TokenType tokenTypeFromString( const char* str, quint32 len, int* pos ) {" << endl;
        bout << "\t\t" << "int i = ( pos != 0 ? *pos: 0 );" << endl;
        bout << "\t\t" << "TokenType res = Tok_Invalid;" << endl;
        tokens = tokens.mid(0,startOfSpecial);
        std::sort( tokens.begin(), tokens.end(), lessThan );
        CharBin bin;
        fillCharBin( tokens, 0, tokens.size(), 0, &bin );
        generateLexer( bout, bin );
        bout << "\t\t" << "if(pos) *pos = i;" << endl;
        bout << "\t\t" << "return res;" << endl;
        bout << "\t" << "}" << endl; // function
    }

    if( !nameSpace.isEmpty() )
        bout << "}" << endl; // namespace
    return true;
}