root/trunk/blade/BladeRank.d

//  Written in the D programming language 1.0
//  Part of BLADE : Basic Linear Algebra D Expressions
/**
*  Determine the tensor rank of an expression.
*
*/

module blade.BladeRank;
private import blade.BladeVisitor;

public:
// return true if the given symbol has a non-zero stride.
// This happens whenever there is a slice (including a complete slice)
// where there is a later incomplete slice or index.
//
bool isStrided(char [] s)
{
   assert(s[$-1]==']', "BLADE ICE");
   if (s[$-2..$]=="[]") return false;
   int numbrack=0;
   int paren = 0;
   bool hasSliced=false;
   bool maybeSlice = false;
   bool startIndex=false;
   for(int i=1; i<s.length; ++i) {
        if (s[i]=='(') ++paren;
        else if (s[i]==')') --paren;
        if (paren==0 && s[i]==']') {
            if (startIndex && hasSliced) return true;
            numbrack--;
            if (s[i-1]=='[') { startIndex=false; }
        }
        if (paren==0 && s[i]=='[') {
            startIndex = true;
            maybeSlice = false;
            numbrack++;
        }
        if (paren==0 && numbrack==1 && s[i]==',') {
            if (hasSliced && startIndex) return true;
            if (maybeSlice) hasSliced = true;
            startIndex = true;
        }
        if (paren==0 && numbrack==2 && s[i]==',') { startIndex=false; hasSliced=true; }
        if (paren==0 && numbrack==1 && s[i]=='.' && s[i-1]=='.') {
             startIndex = false; // [..] slices don't move the index to the next value.
             maybeSlice = true;
        }
   }
   return false;
}

private:
unittest {
    assert(!isStrided("A[3..5][]"));
    assert(!isStrided("A[2..7][3]"));
    assert(!isStrided("A[][2]"));
    assert(!isStrided("A[2,[2,7]]"));
    assert(isStrided("A[[2,7],3]"));
    assert(isStrided("C[D..$,D]"));
    assert(!isStrided("A[7][B[[1,3],2]..6]"));
}

public:
/** Returns the (tensor) rank of the expression expr.
 * A negative number will be returned if an error is detected.
 * TODO: Should warn of expressions with no effect (ie, with no =).
 *
 * Params:
 * expr   Placeholder expression (A,B,... correspond to tuple[0],[1],...)
 * rank   The rank of each tuple member A, B, C, ...
 */
int exprRank(char [] expr, char [] ranks)
{
    return beginVisit(RankVisitor(ranks), expr);
}

int subexprRank(char [] expr, char [] ranks)
{
    return doVisit(RankVisitor(ranks), expr);
}


enum RankError : int {
    UnsupportedOperation = -1,
    RankIncrement = -2,
    AttemptToIndexAScalar = -3,
    NonScalarIndex = -4,
    NonScalarSlice = -5,
    DotDotExpected = -6,
    CommaExpected = -7,
    RankMismatch = -8,
    RankMismatchConcatenation = -9,
    RankMismatchDotProduct = -10,
    ExtraCharsAfterArrayLiteral = -11,
    ArrayLiteralRankMismatch = -12,
    AbsDimensionality = -13
}

char [] getRankErrorText(int err)
{
    return ["Unsupported vector operation",
            "Can only use ++ and -- on scalars",
            "Cannot index a scalar",
            "Vector can only be indexed by a scalar",
            "Vector can only be sliced by a scalar",
            ".. expected",
            ", expected",
            "Dimensionality mismatch (addition or subtraction)",
            "Dimensionality mismatch in concatenation",
            "Dimenionality error in dot product",
            "Extra characters after array literal",
            "Rank mismatch in array literal",
            "Can only use abs, sqrt with scalar or vector"
            ][-err-1];
}

struct RankVisitor {
    alias typeof(*this) This;
    alias int ReturnType;
    char [] rank;
static:
    ReturnType onVisitSymbol(This this_, char [] sym) {
        if (sym=="$") return 0;
        return this_.rank[sym[0]-'A']-'0';
    }
    ReturnType onVisitFunction(This this_, char [] func, char [][] args) {
        switch(func) {
        case "dot":
            if (args.length!=2) return RankError.CommaExpected;
            auto lrank = doVisit(this_,args[0]);
            if (lrank<0) return lrank; // propagate errors
            auto rrank = doVisit(this_, args[1]);
            if (rrank<0) return rrank; // propagate errors
            if (lrank!=1 || rrank!=1) return RankError.RankMismatchDotProduct;
            return 0;
        case "sum":
        case "prod":
            auto lrank = doVisit(this_,args[0]);
            if (lrank<0) return lrank; // propagate errors
            return 0;
        case "abs":
        case "sqrt":
            auto lrank = doVisit(this_,args[0]);
            if (lrank>1) return RankError.AbsDimensionality;
            return 0;
        default:
            assert(0, "BLADE ICE: Unsupported function:" ~ func);
            return 0;
        }
    }
    ReturnType onVisitPrefix(This this_, char [] op, char [] expr) {
        if (op=="+" || op=="-") return doVisit(this_, expr);
        auto r = doVisit(this_, expr);
        if (r<=0) return r;
        return RankError.RankIncrement;
    }
    ReturnType onVisitPostfix(This this_, char [] op, char [] expr) {
        auto r = doVisit(this_, expr);
        if (r<=0) return r;
        return RankError.RankIncrement;
    }
    // Includes multi-dimensional slicing and indexing.
    ReturnType onVisitIndex(This this_, char [] base, char [][2][] slices) {
        int totrank = doVisit(this_, base);
        for(int i=0; i<slices.length; ++i) {
            int r = doVisit(this_,slices[i][0]);
            if (r!=0) return (r<0)? r :RankError.NonScalarIndex;
            if (slices[i][1]==""){
                --totrank;
            } else {
                r = doVisit(this_,slices[i][1]);
                if (r!=0) return (r<0)?r:RankError.NonScalarSlice;
            }
        }
        return totrank;
    }
    ReturnType onVisitBinaryOp(This this_, char [] op, char [] left, char [] right) {
        int lrank = doVisit(this_, left);
        int rrank = doVisit(this_, right);
        if (rrank<0) return rrank; // propagate errors
        if (lrank<0) return lrank; // propagate errors
        if (op=="+" || op=="-" || op=="=" || op=="+=" || op=="-=") {
            if (lrank!=rrank) {
                return RankError.RankMismatch;
            }
            return lrank;
        }
        if (op=="~") { // concatentating scalars and vectors, or vectors and matrices, is permitted
            if (lrank==rrank || lrank==(rrank+1) || rrank==(lrank+1))
                return (lrank>rrank)? lrank: rrank;
            else return RankError.RankMismatchConcatenation;
        }
        if (op=="~=") { // can do vector~=scalar, but not scalar~=vector.
            if (lrank==rrank || lrank==(rrank+1))  return lrank;
            else return RankError.RankMismatchConcatenation;
        }
        // For / and /=, only scalar operations are permitted
        if ((op=="*=" || op=="/=") && rrank==0) return lrank;
        if (op=="*=" && lrank==2 && rrank==2) return lrank; // mat *= mat
        if (op=="*=" && lrank==1 && rrank==2) return lrank; // vec *= mat
        if (op=="*" || op=="/") {
            if (lrank==0) return rrank;
            if (rrank==0) return lrank;
            if (lrank==2 && rrank==2) return lrank;
            if (lrank==2 && rrank==2) return lrank;
            if (lrank+rrank==3) return 1; // vec*mat or mat*vec
        }
        // All other operations are only valid for scalars.
        if (lrank==0 && rrank==0) return 0;
        return RankError.UnsupportedOperation;
    }
}

unittest {
    assert(exprRank("(A[B..C])[C]", "300")==2);
    assert(exprRank("A+=(A[B..C])", "300")==3);

    assert(exprRank("A+(B*C)", "000")==0);
    assert(exprRank("A=(B*C)", "202")==2);
    assert(exprRank("B*=(C*A)", "010")==1);
    assert(exprRank("(A[])+B", "22")==2);
    assert(exprRank("D+=((A+C)*B)", "2022")==2);
    assert(exprRank("D+=((A&C)*B)", "0101")==1);

    assert(exprRank("C~=(((A[B])[B])~C)", "302")==2);
    assert(exprRank("((D[E])[E])+(-((C[B])[B..E]))", "202300")==1);

    assert(exprRank("A+((((++B)+D)--)*C)", "1010")==1);

    assert(exprRank("C+=(A[B])", "302")==2);
    assert(exprRank("dot(A)", "1")==RankError.CommaExpected);
    assert(exprRank("dot(A,B)", "10")==RankError.RankMismatchDotProduct);

    assert(exprRank("dot(B,(A*(dot(B,B))))", "11")==0);

    assert(exprRank("prod(A*B)", "10")==0);

    assert(exprRank("A[B,B,B]", "60")==3);
    assert(exprRank("A[B,B,C,B]", "600")==2);
    assert(exprRank("A+=(B[C..$])", "110")==1);
    assert(exprRank("A+=(B[C,D..$])", "2300")==2);

    // bug fixes:
    assert(exprRank("(A[B..$,C])+=D", "2001")==1);
}