root/trunk/blade/SyntaxTree.d

// Written in the D programming language 1.0
/** 
* Given an expression as a compile-time constant, create an abstract syntax tree
* with semantic information, at compile time.
* Part of BLADE : Basic Linear Algebra D Expressions
*
* Author: Don Clugston
* License: Public Domain
*
* THEORY:
* Nested mixins are used. One mixin tricks the compiler into
* converting the expression into a standard form with precedence and
* associativity information. The inner mixin determines the type and value
* of each symbol in the expression, by mixing in '.stringof' expressions.
* The '.stringof' property is a very powerful language feature which allows
* us to probe the compiler's symbol table. Because it can be applied to any
* expression or type, we can get away with a very rudimentary lexer.
*
* BUGS:
*  The following syntax is not supported by mixin_getPrecedence():
*       unary operators & !
*       && and || operators
*       Comparision operators, NCEG floating point operators, is, !is
*       ?:
*       cast
*       new, delete, anonymous classes, functions and delegates
*       mixin, assert, and import expressions
*       D 2.004 string literals.
*
* An unmatched ] in the expression generates a garbage error message after the
* sensible error message; this is a compiler bug.
*
* NOTES:
*  Functions (including properties) are typed as function pointers in the symbol table.
* ERROR HANDLING:
*  If the expression refers to a non-existent variable, the type will be an empty string,
*  and the value will be the name of the variable.
*  Syntax errors in the expression generate normal D errors in the user code, except
*  for mismatched parentheses.
* QUIRKS:
*  The syntaxtreeof() function and the Symbol and AST classes must be visible to the user code.
*/
module blade.SyntaxTree;
import blade.BladeUtil : enquote;

public:

/**
 * Returns a string, which, when mixed in, lexes, parses, and semantically 
 * analyses the given expression, then creates a struct literal of type
 * AbstractSyntaxTree, containing a syntax tree and a symbol table.
 * The symbol table contains the type, and value for each symbol.
 * If the symbol is an array, the number of dimensions is also returned.
 *
 * Syntax trees are represented as placeholder expressions, with associativity
 * and precedence indicated by parentheses. The placeholders are indices into
 * the symbol table.
 *
 * Typically, this function will be a code generator for a mixin.
 */
char [] syntaxtreeof(char [] expression)
{
    char [][] symbols = replaceSymbolsWithPlaceholders(expression);
    char [] result = `AbstractSyntaxTree(` ~ mixin_getPrecedence(expression) ~ `,[`;
        
    for(int i=0; i<symbols.length; ++i) {
        if (i>0) result ~= ",";
        result ~= `Symbol(` ~ mixin_typeOf(symbols[i])
                      ~ `,` ~ mixin_valueOf(symbols[i])
                      ~ `,` ~ mixin_rankOf(symbols[i])
                      ~ `,` ~ mixin_elementOf(symbols[i]) ~ `)`;
    }    
    
    result ~="])";
    return `mixin("` ~ enquote(result) ~ `")`;
}

/**
*  As for syntaxtreeof(), except that it creates a tuple as well as the abstract syntax tree
*/
char [] mixin_tupleAndSyntaxtreeof(char [] funcname, char [] expression)
{
    char [][] symbols = replaceSymbolsWithPlaceholders(expression);
    char [] result = `AbstractSyntaxTree(` ~ mixin_getPrecedence(expression) ~ `,[`;
    char [] tuple;
        
    for(int i=0; i<symbols.length; ++i) {
        if (i>0) {
            result ~= ",";
            tuple ~= ",";
        }
        result ~= `Symbol(` ~ mixin_typeOf(symbols[i])
                      ~ `,` ~ mixin_valueOf(symbols[i])
                      ~ `,` ~ mixin_rankOf(symbols[i])
                      ~ `,` ~ mixin_elementOf(symbols[i]) ~ `)`;
        tuple ~= mixin_typeOfOrVoid(symbols[i]);
    }    
    
    result ~="])";
    return funcname ~ `!(mixin("` ~ enquote(tuple) ~ `"))(mixin("` ~ enquote(result) ~ `"))`;
}

/** The result of semantic analysis of the original expression
 *
 */
struct AbstractSyntaxTree {
    char [] expression; /// syntax tree in Placeholder format, eg A+=(B*C)
    Symbol[] symbolTable; /// Textual form of the types and values of A,B,C,...
}

/** The values of the A, B, C, ... placeholders
*
* Members:
* type    the name of the type, as text
* value   The value, as text. This will be either a symbol name, or a literal.
*         Note that if it is a numeric or text literal, value[0] will be one of 
*         the characters 0123456789"'-
* rank    The tensor rank. '0' = scalar, '1' = vector, '2' = matrix, 
*         '3' = tensor of rank 3 or more.
* element The base type of each element. (eg, for "double" for double[][5]).
*         Not valid for tensors of rank > 3.        
*/
struct Symbol {
    char [] type;  /// the name of the type, as text
    char [] value; /// the value, as text.
    char rank;      /// the tensor rank ('0'=scalar, 1=vector, 2 = matrix, 3=tensor)
    char [] element; /// the type of each element of the vector or matrix
}

private:

//  ==== LEXER ====
/** 
 * Extract all terminal symbols(identifiers, type names, and literals)
 * from expression expr.
 * Replace each identifier with a placeholder A, B, C, D, ...
 *
 * Returns: an array of symbols (with no duplicates, though aliasing may exist)
 *
 * Supports *all* D syntax, except D2.004 string literals.
 */
char [][] replaceSymbolsWithPlaceholders(inout char [] expr)
{
    char [] code = "";
    char [][] symbols = [];
    expr ~= " "; // ensure that it ends.
    char quote=0; // character which marks end of string literal, 0 if none
    int startOfSymbol=0;
    for(int i=0; i<expr.length; ++i) {
        char c = expr[i];
        // Deal with string literals
        if (quote != 0) {
            if (c == quote && (i>0 || expr[i-1]!='\\')) quote=0;
            continue;
        } else if (c == '"' || c == '`' || c == '\'') { // Is a string literal beginning?
            quote = c;
            continue;
        }
        // Identifiers and numeric literals are a..zA..Z_ or non-ASCII.
        // + and - are part of the symbol, if it is a floating-point literal    
        // . is part of a symbol, unless it is a ".." slice
        if ((c >='a' && c <= 'z') || (c>='A' && c<='Z')
                || (c>='0' && c<='9') || (c=='_') || (c>0x7F)
           || ((c=='+' || c=='-') && i>0 && (expr[startOfSymbol]>='0' && expr[startOfSymbol]<='9') && (expr[i-1]=='e' ||expr[i-1]=='p'|| expr[i-1]=='E' || expr[i-1]=='P'))
           || (c=='.' && expr[i+1]!='.')
        ) continue;
         // The next character is NOT part of the symbol.
        char [] symbol = expr[startOfSymbol..i];
        if (symbol=="is" || symbol=="in") {
            code ~= symbol; // non-type keywords are NOT symbols
            symbol="";
        }
        if (symbol.length>0) {
            // Add the new symbol to the symbol table
            code ~= cast(char)('A' + symbols.length);
            symbols ~= symbol;               
        }
        if (c=='.') { // it was opSlice. Skip the next . as well.
            i++;
            code ~= ".";
        }
        if (c!='/' || i >= expr.length-1) {
            code ~= c;
        } else {
            // Ignore comments.
            if (expr[i..i+2]=="//") {
                for ( ; i<expr.length && expr[i]!='\n' ; ++i) {}
            } else if (expr[i..i+2]=="/*") {
                i+=3;
                for ( ; i<expr.length && expr[i-1..i+1] != "*/"; ++i) {}
                if ( i >= expr.length-1 ) break;
            } else if (expr[i..i+2]=="/+") {
                i++;
                for (int nest = 1; nest>0 && i < expr.length-1; ++i) {
                    if (expr[i..i+2] == "+/") { --nest; ++i; }
                    else if (expr[i..i+2] == "/+") { ++nest; ++i; }
                }
                --i;
                if (i >= expr.length-1) break;
            } else code~=c;
        }
        startOfSymbol = i+1;
    }
    if (code[$-1]==' ') code=code[0..$-1]; // remove the " " we added.
    expr = code;
    return symbols;
}

//  ==== SYNTAX PASS ====

/** Generate a syntax tree

We trick the compiler into generating a syntax tree for us. We replace
every symbol x with a variable of type AST!("x"), which supports all possible
operator overloads. All that the overloaded operators do, is record which
operation was performed. This gives the associativity and precedence rules
which the compiler used.

Extension: This code allows opSlice and opIndex to be mixed, even though it is
not yet allowed in normal D code.
*/
class AST(char [] expr)
{
    alias expr text;
    // Binary, pre- and post- operators
    template binOp(char [] op, T) {
        alias AST!("(" ~ text ~ op ~ T.text ~ ")") binOp;
    }
    template preOp(char [] op) {
        alias AST!("(" ~ op ~ text ~ ")") preOp;
    }
    template postOp(char [] op) {
        alias AST!("(" ~ text ~ op ~ ")") postOp;
    }
   
    // Simple binary operators
    binOp!("+", T) opAdd(T)(T x){ return null; }
    binOp!("-", T) opSub(T)(T x){ return null; }
    binOp!("*", T) opMul(T)(T x){ return null; }
    binOp!("/", T) opDiv(T)(T x){ return null; }
    binOp!("%", T) opMod(T)(T x){ return null; }
    binOp!("~", T) opCat(T)(T x){ return null; }
    binOp!("&", T) opAnd(T)(T x){ return null; }
    binOp!("|", T) opOr(T)(T x) { return null; }
    binOp!("^", T) opXor(T)(T x){ return null; }
    binOp!("<<", T)  opShl(T)(T x)  { return null; }
    binOp!(">>", T)  opShr(T)(T x)  { return null; }
    binOp!(">>>", T) opUShr(T)(T x) { return null; }
    binOp!("in", T) opIn(T)(T x)   { return null; }
    binOp!("=", T)  opAssign(T)(T x){ return null; }
    binOp!("+=", T) opAddAssign(T)(T x){ return null; }
    binOp!("-=", T) opSubAssign(T)(T x){ return null; }
    binOp!("*=", T) opMulAssign(T)(T x){ return null; }
    binOp!("/=", T) opDivAssign(T)(T x){ return null; }
    binOp!("%=", T) opModAssign(T)(T x){ return null; }
    binOp!("~=", T) opCatAssign(T)(T x){ return null; }
    binOp!("&=", T) opAndAssign(T)(T x){ return null; }
    binOp!("|=", T) opOrAssign(T)(T x) { return null; }
    binOp!("^=", T) opXorAssign(T)(T x){ return null; }
    binOp!("<<=", T)  opShlAssign(T)(T x)  { return null; }
    binOp!(">>=", T)  opShrAssign(T)(T x)  { return null; }
    binOp!(">>>=", T) opUShrAssign(T)(T x) { return null; }
    // Pre-inc operators  are special cases of +=,-=.
    preOp!("++") opAddAssign(T:int=int)(int x){ return null; }
    preOp!("--") opSubAssign(T:int=int)(int x){ return null; }  
    // OpSlice is combined with opIndex.
//    AST!("(" ~ text ~ "[" ~ T.text ~ ".." ~ U.text ~ "])") opSlice(T, U)(T x, U y){ return null; }    
    AST!("(" ~ text ~ "[" ~ AllText!(T) ~ "])") opIndex(T...)(T x){ return null; }
    AST!("((" ~ text ~ "[" ~ AllText!(T) ~ "])=" ~ U.text ~ ")") opIndexAssign(U, T...)(U,T){ return null; }
    AST!("(" ~ text ~ "(" ~ AllText!(T) ~ "))") opCall(T...)(T){ return null; }

    // Avoid infinite recursion by templating these functions.
    preOp!("~") opCom(dummy=void)(){ return null; }
    preOp!("+") opPos(dummy=void)(){ return null; }
    preOp!("-") opNeg(dummy=void)(){ return null; }
    preOp!("*") opStar(dummy=void)(){ return null; }  // D2.0 only

    postOp!("[]") opSlice(dummy=void)(){ return null; }
    static if (text.length>3 && text[$-3..$]!="++)" && text[$-3..$]!="--)") {
        postOp!("++") opPostInc(){ return null; }
        postOp!("--") opPostDec(){ return null; }
    }
// Unfortunately, opCast doesn't work, because the return type must be the same as typeof(this).
// Likewise, opEquals and opCmp must return an int.
// Other operators are not overloadable
}

// Helper for opCall() etc
template AllText(T...)
{
    static if (T.length==0) const char [] AllText = "";
    else static if (T.length==1) const char [] AllText = T[0].text;
    else static if (T.length>2 && T[1].text=="..") // Convert back to a slice
        const char [] AllText = T[0].text ~ ".." ~ AllText!(T[2..$]);
    else const char [] AllText = T[0].text ~ "," ~ AllText!(T[1..$]);
}

/**
 * Insert parentheses around each symbol, to enforce normal D precedence rules.
 * Returns: a string which, when mixed in, generates a parenthesised expression.
 */
char [] mixin_getPrecedence(char [] expr)
{    
    if (expr.length<2) return "`" ~ expr ~ "`";
    // The scheme doesn't work directly for array literals. Instead, change them
    // into opIndex of a nameless `` symbol.
    bool lastWasSymbol=false; // hack for array literals
    char [] code = "typeof(";
        for(int i=0; i<expr.length; ++i) {
            if (expr[i]>='A' && expr[i]<='Z' || expr[i]=='$') {
                code ~= "(cast(AST!(`" ~ expr[i] ~"`))(null))";
                lastWasSymbol = true;
            } else {                
                if (!lastWasSymbol && expr[i]=='[') {
                    code ~= "(cast(AST!(``))(null))";
                }
                if (expr[i]!=' ' && expr[i]!='\t' && expr[i]!='\r' 
                    && expr[i]!= '\n' && expr[i]!=')') lastWasSymbol = false;
                if (expr[i]==']') lastWasSymbol=true;
                if (i<expr.length-1 && expr[i..i+2]=="..") {
                    code ~= ",(cast(AST!(`..`))(null)),";
                    ++i;
                }
                else code ~= expr[i];
            }
        }
    return code ~ ").text[1..$-1]"; // remove the outer ()
}

//  ==== SEMANTIC PASS ====

// Returns typeof(sym).stringof.
char [] mixin_typeOf(char [] sym)
{
    // If sym is a function, we take its address, since
    //   typeof(x).stringof doesn't compile if x is a function.
    // If sym doesn't compile at all, return an empty string.
    return `mixin(!is(typeof(` ~ sym ~ `))?"\"\"" : is(typeof(` ~ sym ~ `)==function)?"` ~ enquote("typeof(&" ~ sym ~ ").stringof")~`":"` ~ enquote("typeof(" ~ sym ~ ").stringof") ~ `")`;
}

char [] mixin_typeOfOrVoid(char [] sym)
{
    // If sym is a function, we take its address, since
    //   typeof(x).stringof doesn't compile if x is a function.
    // If sym doesn't compile at all, return "void".
    return `mixin(!is(typeof(` ~ sym ~ `))?"\"void\"" : is(typeof(` ~ sym ~ `)==function)?"` ~ enquote("typeof(&" ~ sym ~ ").stringof")~`":"` ~ enquote("typeof(" ~ sym ~ ").stringof") ~ `")`;
}

// Returns sym.stringof, with workarounds for compiler bugs
char [] mixin_valueOf(char [] sym)
{
    // This function would just return sym.stringof, except that:
    // (1) 1.23.stringof fails to compile (compiler bug).
    //  Fortunately (1.23).stringof works.
    // (2) x.stringof doesn't compile, if x is a function. Just return x instead.
    //     We also return x if x doesn't compile (eg, is an undefined variable).
    if (sym[0]>='0' && sym[0]<='9') { // numeric literal
        return `(` ~ sym ~ `).stringof`;
    }
    return `mixin(is(typeof(` ~ sym ~ `)==function) || !is(typeof(` ~ sym ~ `))?"\"` ~ enquote(sym, `\\\`) ~ `\"":"` ~ enquote(sym ~ ".stringof") ~ `")`;
}

// BLADE-SPECIFIC SEMANTIC PASS

// When mixed in, creates a const char describing the (tensor) rank of symbol sym.
// Possible results are 0 = scalar, 1 = vector, 2 = matrix, 3 = tensor of rank 3 or more.
char [] mixin_rankOf(char [] sym)
{
    // Implementation: If sym[0][0] is a valid type, we know it's a matrix.
    // else if sym[0] is a valid type, we know it's a vector. Etc.
    return "is(typeof(" ~ sym ~ "[0]))?is(typeof(" ~ sym ~ "[0][0]))?is(typeof(" ~ sym ~ "[0][0][0]))?'3':'2':'1':'0'";
}

char [] mixin_elementOf(char [] sym)
{
    // Implementation: If sym[0][0] is a valid type, we know it's a matrix.
    // else if sym[0] is a valid type, we know it's a vector. Etc.
    char [] s = enquote(sym);
    return mixin_typeOf("mixin(is(typeof(" ~ sym ~ "[0]))?is(typeof(" ~ sym ~ "[0][0]))?is(typeof(" ~ sym ~ `[0][0][0]))?"`
    ~ s ~ `[0][0][0]":"` ~ s ~ `[0][0]":"` ~ s ~ `[0]":"` ~ s ~ `")`);   
}

//  ==== TESTS ====

unittest {
    char [] expr = "xyzzy+ y/+ comment/++ /++//++/+/ +/*2";
    char [][] symbols = replaceSymbolsWithPlaceholders(expr);
    assert(expr == "A+ B*C");
    
    assert(mixin(mixin_getPrecedence("D -= A+B *C"))=="D-=(A+(B*C))");
    assert(mixin(mixin_getPrecedence("D -= ++A"))=="D-=(++A)");
    assert(mixin(mixin_getPrecedence("A[B,$-C/D]=E+F"))=="(A[B,($-(C/D))])=(E+F)");
    assert(mixin(mixin_getPrecedence("A[B]=E+F"))=="(A[B])=(E+F)");
    assert(mixin(mixin_getPrecedence("A+=B[E]"))=="A+=(B[E])");
    assert(mixin(mixin_getPrecedence("A[B][$]=A[E]+F"))=="((A[B])[$])=((A[E])+F)");
    assert(mixin(mixin_getPrecedence("G-=A[B][C..B^D][D]*E+F"))=="G-=(((((A[B])[C..(B^D)])[D])*E)+F)");
    assert(mixin(mixin_getPrecedence("E=A[B,C/D]*F"))=="E=((A[B,(C/D)])*F)");
    assert(mixin(mixin_getPrecedence("(A+B)  in(C^D)"))=="(A+B)in(C^D)");
    assert(mixin(mixin_getPrecedence("A"))=="A");
    assert(mixin(mixin_getPrecedence("--A"))=="--A");
//   assert(mixin(mixin_getPrecedence("A--"))=="A--"); // BUG: fails
    
    assert(mixin(mixin_getPrecedence("A[B,[C,D]]"))=="A[B,([C,D])]");
    assert(mixin(mixin_getPrecedence("A[B,C..D]"))=="A[B,C..D]");
    assert(mixin(mixin_getPrecedence("A[B][C,D]"))=="(A[B])[C,D]");
    assert(mixin(mixin_getPrecedence("A[B,([C,D])]"))=="A[B,([C,D])]");
    assert(mixin(mixin_getPrecedence("A([B,C])"))=="A(([B,C]))");    
}
/+   // NO LONGER USED
/** Return true if text is a non-value, non-type D keyword
 */
bool isNonTypeKeyword(char [] text) {
    char [][] keywords = [ 
    "abstract", "alias", "align", "asm", "assert", "auto", "body", "break",
    "case", "cast", "catch", "class", "const", "continue", "dchar", "debug",
    "default", "delegate", "delete", "deprecated", "do", "else", "enum",
    "export", "extern", "final", "finally", "for", "foreach", "foreach_reverse",
    "function", "goto", "if", "import", "in", "inout", "interface", "invariant",
    "is", "lazy", "macro", "mixin", "module", "new", "out", "override",
    "package", "pragma", "private", "protected", "public", "ref", "return",
    "scope", "static", "struct", "switch", "synchronized", "template", "throw",
    "__traits", "try", "typedef", "typeid", "typeof", "union", "unittest",
    "version", "volatile", "while", "with" ];
    
    foreach(char [] s; keywords) {
        if (s==text) return true;
    }
    return false;
}
+/