root/trunk/blade/BladeVisitor.d

//  Written in the D programming language 1.0
/**
* Traverse a syntax tree in text form.
* Part of BLADE : Basic Linear Algebra D Expressions
*
* Author:
*   Don Clugston.
* License:
*   Public domain.
*/

module blade.BladeVisitor;

public:
//--------------------------------------------------------
//      BLADE Visitor -- walk the syntax tree
//--------------------------------------------------------

// The lowest level doesn't need to have parens around it.
V.ReturnType beginVisit(V)(V visitor, char [] expr)
{
    if (isSimpleExpr(expr)) {
        return doVisit(visitor, expr);
    } else return doVisit(visitor, "(" ~ expr ~ ")");
}

// Walk the tree, invoking 'visitor' at each node
V.ReturnType doVisit(V)(V visitor, char [] expr)
{
    // BUG: also need to deal with comma, ?:, &&, ||, is, !is, in, 
    // unary &, unary !

    if (expr.length>1 && expr[0]=='(') expr = expr[1..$-1];
    else if (expr.length==1 && ((expr[0]>='A' && expr[0]<='Z') || expr[0]=='$')){
        return visitor.onVisitSymbol(visitor, expr);
    }
    if (expr[0]>='a' && expr[0]<='z' && exprLength(expr)==expr.length) { // function
        char [][] args;
        int z=1;
        while(z<expr.length && expr[z]!='(') ++z;
        int x = z+1;
        while (x<expr.length) {
            int y = exprLength(expr[x..$-1]);
            args ~= expr[x..x+y];
            x = x+y+1; // skip the comma
        }
        return visitor.onVisitFunction(visitor, expr[0..z], args);
    }
    if (expr.length>2 && (expr[0..2]=="++" || expr[0..2]=="--")) {
        return visitor.onVisitPrefix(visitor, expr[0..2], expr[2..$]);
    }
    if (expr.length>1 && (expr[0]=='+' || expr[0]=='-')) {
        return visitor.onVisitPrefix(visitor, expr[0..1], expr[1..$]);
    }
    if (expr.length>2 && (expr[$-2..$]=="++" || expr[$-2..$]=="--")) {
        return visitor.onVisitPostfix(visitor, expr[$-2..$], expr[0..$-2]);
    }
    int x = exprLength(expr);
    int y = x;
    assert(y < expr.length, "BLADE ICE:" ~ expr);
    // Deal with shifts, op=, and NCEG operators
    while (expr[y+1]=='<' || expr[y+1]=='>' || expr[y+1]=='=') ++y;
    char [] op = expr[x..y+1];    
    char [] left = expr[0..x];
    char [] right = expr[y+1..$];
    if (op=="[") {
        right = right[0..$-1];
        char [][2][] allslices=[];        
        int z = 0;
        while (z<right.length) {
            if (right[z]==',') { // null dimension
                allslices ~= ["",""];
                ++z;
            } else {
                    int w = exprLength(right[z..$]);
                    if (z+w+2 < right.length && right[z+w..z+w+2]=="..") {
                        int q = z+w+2;
                        int t = exprLength(right[q..$]);
                        allslices ~= [ right[z..z+w], right[q..q+t]];
                        z = q+t+1; // no comma to skip
                    } else {
 
                     if (right.length>z+1 && right[z+1]=='[') { // fake slice -- support this for now
                            int w2 = exprLength(right[z+2..$-2]);
                            int q = z+w2+1; // skip the ,
                            int t = exprLength(right[q+2..$]);
                            allslices ~= [ right[z+2..q+1], right[q+2..q+2+t]];
                            z = z+w+2;
                    } else {
                        allslices ~= [ right[z..z+w], ""];
                        z = z+w+1; // skip the comma, if any
                    }
                }
             }
        }
       return visitor.onVisitIndex(visitor, left, allslices); 
    }
    return visitor.onVisitBinaryOp(visitor, op, left, right);
}

/** Return the length of a sub-expression
 * The sub-expression must be one of:
 *  - a single character (eg "X"), OR
 *  - a lower-case intrinsic function (eg "abc(B,(C*D))"), OR
 *  - an expression in parenthesis, OR
 *  - an array literal 
 */
int exprLength(char [] s)
{
    if ((s[0]>='A' && s[0]<='Z') || s[0]=='$') return 1;
    int i = 0;    
    while (s[i]>='a' && s[i]<='z'){ // intrinsic function call
        ++i; // next char will be '(' so code below works
    }
    int numParens = 0;
    int numBrack = 0;
    for (; i<s.length; ++i) {
        if (s[i]=='(')  ++numParens;
        if (s[i]==')') numParens--;       
        if (s[i]=='[') ++numBrack;
        if (s[i]==']') --numBrack;
        if (numParens == 0 && numBrack == 0) {
            return i+1;
        }
    }
    assert(0, "BLADE ICE: " ~ s);   
}

// Return true if the function is a single variable, or an intrinsic.
bool isSimpleExpr(char [] s)
{
    if (s.length==1) return true;
    if (s[0]<'a' || s[0]>'z') return false;
    return exprLength(s)==s.length;
}

unittest {
    assert(exprLength("A*B")==1);
    assert(exprLength("dot(A,B)*C")==8);
}

/* Wrap parentheses around the expression, if required
*/
char [] wrapInParens(char [] a)
{
    return (a.length==1 || (a[0]>='a' && a[0]<='z' && exprLength(a)==a.length))? a : "(" ~ a ~ ")";
}

// Return true if this expression contains an assignment.
bool expressionContainsAssignment(char [] expr)
{
    if (isSimpleExpr(expr)) return false;
    // BUG: also need to deal with comma, ?:, &&, ||, is, !is, in, 
    // unary &, unary !
    if (expr.length>1 && expr[0]=='(') expr = expr[1..$-1];
    if (expr.length>2 && (expr[0..2]=="++" || expr[0..2]=="--")) {
        return false;
    }
    if (expr.length>1 && (expr[0]=='+' || expr[0]=='-')) {
        return false;
    }
    if (expr.length>2 && (expr[$-2..$]=="++" || expr[$-2..$]=="--")) {
        return false; // BUG: actually this _is_ an assignment
    }
    int y = exprLength(expr);
    assert(y < expr.length, "BLADE ICE:" ~ expr);
    // Deal with shifts, op=, and NCEG operators
    if (expr[y+1]=='<' || expr[y+1]=='>') return false;
    if (expr[y]=='=' && expr[y+1]=='=') return false;
    if (expr[y]=='=') return true;
    if (expr[y+1]!='=') return false;
    if (expr[y]=='<' || expr[y]=='<' || expr[y]=='!') return false;
    return true;
}