Changeset 159

Show
Ignore:
Timestamp:
12/12/07 03:12:39 (9 months ago)
Author:
Don Clugston
Message:

Index folding visitor -- not linked into the main line yet. Minor refactoring in other modules.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved
  • trunk/blade/BladeDemo.d

    r158 r159  
    3030        r[i]= q[i]*2213.3L; 
    3131    } 
    32     double [4][] another = [[33.1, 4543, 43, 878.7], [5.14, 455, 554, 2.43]]; 
     32    double [4][] another = [[33.1, 4543, 43, 878.7],  
     33                            [5.14, 455, 554, 2.43]]; 
    3334    real k=3.4; 
    3435 
    3536//    mixin(vectorize(` a += (d[2..$-1]*2.01*a[2]-another[][1])["abc".length-3..$]`)); 
    36      
     37/+     
    3738    mixin(vectorize(" a-= 2.01*(        3.04+k)*r")); 
    3839    mixin(vectorize("q+= q*2.01")); 
     
    4546    mixin(vectorize("another[0..$,1]+=6*a[0..2]")); 
    4647    mixin(vectorize("r-=another[0]")); 
    47  
     48+/ 
    4849    // Parses OK, but I don't think I'll support this. 
    4950//    mixin(vectorize("a+=6*another[1,[1,$]]")); 
    50  
    5151 
    5252// Parses, and simplifies to A*A, where A = dot(q,q). No codegen yet. 
  • trunk/blade/BladeRank.d

    r158 r159  
    117117    char [] rank; 
    118118static: 
    119     ReturnType onVisitSymbol(This this_, char sym) { 
    120         if (sym=='$') return 0; 
    121         return this_.rank[sym-'A']-'0'; 
     119    ReturnType onVisitSymbol(This this_, char [] sym) { 
     120        if (sym=="$") return 0; 
     121        return this_.rank[sym[0]-'A']-'0'; 
    122122    } 
    123123    ReturnType onVisitFunction(This this_, char [] func, char [][] args) { 
     
    146146    } 
    147147    // Includes multi-dimensional slicing and indexing.     
    148     ReturnType onVisitIndex(This this_, char [] base, char [][] startSlice, char [][] endSlice) { 
     148    ReturnType onVisitIndex(This this_, char [] base, char [][2][] slices) { 
    149149        int totrank = doVisit(this_, base); 
    150         for(int i=0; i<endSlice.length; ++i) { 
    151             int r = doVisit(this_,startSlice[i]); 
     150        for(int i=0; i<slices.length; ++i) { 
     151            int r = doVisit(this_,slices[i][0]); 
    152152            if (r!=0) return (r<0)? r :RankError.NonScalarIndex;  
    153             if (endSlice[i]==""){ 
     153            if (slices[i][1]==""){ 
    154154                --totrank; 
    155155            } else { 
    156                 r = doVisit(this_,endSlice[i]); 
     156                r = doVisit(this_,slices[i][1]); 
    157157                if (r!=0) return (r<0)?r:RankError.NonScalarSlice;  
    158158            } 
  • trunk/blade/BladeSimplify.d

    r158 r159  
    2929 
    3030public import blade.SyntaxTree : AbstractSyntaxTree, Symbol; 
    31 //private import blade.BladeVisitor; 
     31private import blade.BladeVisitor; 
    3232private import blade.BladeRank : exprLength, exprRank, subexprRank, 
    3333        hasScalarMultiply, getRankErrorText, isStrided;  
     
    336336RevisedExpression simplifyVectorExpression(char [] expr, char [] rank, Symbol[] symTable=[]) 
    337337{ 
     338//    char [] s = exprSimplify(foldIndices(expr, rank), rank, "", ""); 
    338339    char [] s = exprSimplify(expr, rank, "", ""); 
    339340    if (s.length>1 && s[0]=='(') s = s[1..$-1]; // strip off () 
    340341    char [][] comp; 
    341     char [] used=""; // which of the old variables are used; gives the new mapping 
     342    char [] used = ""; // which of the old variables are used; gives the new mapping 
    342343                  // of the name, or - if not used. 
    343344    for (int i=0; i<rank.length; ++i) used ~= "-"; 
     
    420421} 
    421422 
    422  
    423  
     423// ----------------------------------------------------------- 
     424 
     425// Given an array of slices/indices where 
     426//  slicing[0]= start of slice, or index 
     427//  slicing[1]= end of slice, or "" if it's an index, 
     428// combine everything into a single slicing expression. 
     429char [] createMultiSlice(char [][2][] slicing) 
     430
     431    char [] s="["; 
     432    for (int i=0; i<slicing.length;++i) { 
     433        if (i>0) s~= ","; 
     434        s ~= slicing[i][0]; 
     435        if (slicing[i][1].length>0) s~=".." ~ slicing[i][1]; 
     436    } 
     437    return s~"]"; 
     438
     439 
     440// Combines all the indexing and slicing operations together (dimension reduction). 
     441// Returns the new expression. This eliminates all unnecessary slice operations. 
     442// Furthermore, *any* value followed by '[' should be used as a new compound. 
     443struct IndexFoldingVisitor { 
     444    alias typeof(*this) This; 
     445    alias char [] ReturnType; 
     446    char [] rank; 
     447    char [] dollar; 
     448    char [][2][] slicing; // the indexing which applies to this complete expr. 
     449static: 
     450    ReturnType onVisitSymbol(This this_, char[] sym) { 
     451       if (this_.slicing.length==0) { 
     452           if (sym=="$") { 
     453               return this_.dollar; 
     454           } 
     455           else return sym; 
     456       } else { 
     457           assert(sym!="$" && this_.rank[sym[0]-'A']>'0', "Rank error " ~ sym); 
     458           // TODO: We want this to be a new terminal. 
     459           return sym ~ createMultiSlice(this_.slicing);            
     460       } 
     461    } 
     462    ReturnType onVisitFunction(This this_, char [] func, char [][] args) {         
     463        if (func=="d") { // dot product. 
     464            // Each element is reduced seperately 
     465            char [] left = wrapInParens(doVisit(this_,args[0])); 
     466            char [] right = wrapInParens(doVisit(this_, args[1])); 
     467            return func ~ "(" ~ left ~ "," ~ right ~ ")"; 
     468        } 
     469        assert(0, "BLADE ICE: Unsupported function"); 
     470        return ""; 
     471    } 
     472    ReturnType onVisitPrefix(This this_, char [] op, char [] expr) { 
     473        assert(this_.slicing.length==0, "BLADE ICE"); 
     474        return op ~ doVisit(this_, expr);         
     475    } 
     476    ReturnType onVisitPostfix(This this_, char [] op, char [] expr) { 
     477        assert(this_.slicing.length==0, "BLADE ICE"); 
     478        return doVisit(this_, expr) ~ op; 
     479    } 
     480    // Includes multi-dimensional slicing and indexing.     
     481    ReturnType onVisitIndex(This this_, char [] base, char [][2][] slices) { 
     482        if (slices.length==0) { // []  -- has no effect. 
     483             return doVisit(this_, base); 
     484         } 
     485//        printf("  %.*s --> %.*s %.*s\n", base, slices[0][0], slices[0][1]); 
     486        if (this_.slicing.length >0 && slices[$-1][1].length>0) { 
     487            // the new dimension block ends with a slice. This needs to be combined 
     488            // with the earliest existing dimension. 
     489            // * If the existing dimension is an index, 
     490            //   it might contain a dollar, which we need to replace.  
     491            // * If the existing dimension is a slice, the two slices will combine. 
     492            //  
     493            // The items inside the slice are top-level, ie have no slice or dollar. 
     494            char [] a = wrapInParens(doVisit(IndexFoldingVisitor(this_.rank,"$",[]), slices[$-1][0])); 
     495            char [] b = wrapInParens(doVisit(IndexFoldingVisitor(this_.rank,"$",[]), slices[$-1][1])); 
     496            char [] dollr = b ~ "-" ~ a; 
     497            char [] c = wrapInParens(doVisit(IndexFoldingVisitor(this_.rank,dollr,[]), this_.slicing[0][0])); 
     498            char [][2][] newslice=[]; 
     499             if (this_.slicing[0][1].length>0) { // slicing a slice 
     500               if (b=="$" && this_.slicing[0][1]=="$") { 
     501                   // very common special case, where both are sliced from end 
     502                    newslice ~= ["(" ~ a ~ "+" ~ c ~")","$"]; 
     503                } else { 
     504                   char [] d = wrapInParens(doVisit(IndexFoldingVisitor(this_.rank,dollr,[]), this_.slicing[0][1])); 
     505                    newslice ~= ["(" ~ a ~ "+" ~ c~ ")", "(" ~ a ~ "+" ~ d~ ")"]; 
     506                } 
     507            } else { 
     508                newslice ~= [a ~ "+" ~ c, ""]; 
     509            } 
     510            if (slices.length>1) {                 
     511                // append other slices, if any. 
     512                return doVisit(IndexFoldingVisitor(this_.rank, "$", slices[0..$-1] ~ newslice ~ this_.slicing[1..$]), base); 
     513            } else { 
     514                return doVisit(IndexFoldingVisitor(this_.rank, "$",newslice ~ this_.slicing[1..$]), base); 
     515            } 
     516        } else { // just append them. 
     517            return doVisit(IndexFoldingVisitor(this_.rank, "$", slices ~ this_.slicing), base); 
     518        } 
     519    } 
     520    ReturnType onVisitBinaryOp(This this_, char [] op, char [] left, char [] right) { 
     521        int lrank = subexprRank(left, this_.rank); 
     522        int rrank = subexprRank(right, this_.rank); 
     523        char [] first; 
     524        char [] second; 
     525        if ((op=="*" || op=="*=") && this_.slicing.length>0) { 
     526            // If one of these is a matrix, the slicing gets interesting... 
     527            // .. extremely so for slicing of matrix chain multiplication. 
     528            // Given U a row vector, V a column vector; A,B,C matrices; x, y scalars: 
     529            //  (U*V)[x][y]  = U[x]*V[y] 
     530            //  (U*V)[x] =  
     531            //  (U*A)[x]  = U*A[,x] 
     532            //  (A*U)[x]  = A[x]*U 
     533            //  (A*B)[x] = A[x]*B. 
     534            //  (A*B)[x..y] = A[x..y]*B[,x..y] 
     535            //  (A*B)[x][y] = A[x]*B[,y] 
     536            //  (A*B*C)[x][y] 
     537            if (lrank==0) { 
     538                // All dimensions apply to right operand 
     539                first = wrapInParens(doVisit(IndexFoldingVisitor(this_.rank, this_.dollar,[]), left)); 
     540                second = wrapInParens(doVisit(this_, right)); 
     541            } else if (rrank==0) { 
     542                // All dimensions apply to the left operand 
     543                first = wrapInParens(doVisit(this_, left)); 
     544                second = wrapInParens(doVisit(IndexFoldingVisitor(this_.rank, this_.dollar,[]), right)); 
     545            } else { 
     546                // vector * matrix, or matrix * matrix 
     547                assert(lrank<=2 && rrank<=2); 
     548                // Interesting case -- indices must be distributed between both. 
     549                assert(0, "Not yet implemented"); 
     550            } 
     551        } else { 
     552            first = wrapInParens(doVisit(this_, left)); 
     553            second = wrapInParens(doVisit(this_, right)); 
     554        }         
     555        return first ~ op ~ second; 
     556    } 
     557
     558 
     559char [] foldIndices(char [] expr, char [] ranks) 
     560
     561    return beginVisit(IndexFoldingVisitor(ranks,"$",[]), expr); 
     562
     563 
     564unittest { 
     565   //BUG: assert(0, foldIndices("((A*B)[C])[D]", "2200")); 
     566    assert(foldIndices("A+=(((D[B])*C)[B])", "2004")=="A+=((D[B,B])*C)"); 
     567    assert(foldIndices("((A[C..D])+B)[($-E)]", "21000")=="(A[C+((D-C)-E)])+(B[($-E)])"); 
     568    assert(foldIndices("(A[C])[D]", "3100")=="A[C,D]"); 
     569    assert(foldIndices("(A[B..C])[D]", "3000")=="A[B+D]"); 
     570    assert(foldIndices("(A[B])[C..D]", "3000")=="A[B,C..D]"); 
     571    assert(foldIndices("((A[$])[(C-$)])[D]", "3000")=="A[$,(C-$),D]"); 
     572    assert(foldIndices("(A[B..$])[C..$]", "3000")=="A[(B+C)..$]"); 
     573    assert(foldIndices("((A[])[C..$])[]", "3000")=="A[C..$]"); 
     574    assert(foldIndices("((A[])[(B[C])..$])[]", "3100")=="A[(B[C])..$]"); 
     575    assert(foldIndices("A[,B..$,C]", "300")=="A[,B..$,C]"); 
     576
  • trunk/blade/BladeVisitor.d

    r158 r159  
    2020V.ReturnType beginVisit(V)(V visitor, char [] expr) 
    2121{ 
    22 //    printf("\n%.*s\n", expr); 
    23     if (expr.length==1 && expr[0]>='A' && expr[0]<='Z'){ 
    24         return visitor.onVisitSymbol(visitor, expr[0]); 
     22    if (expr.length==1 && (expr[0]>='A' && expr[0]<='Z' || expr[0]=='$')){ 
     23        return visitor.onVisitSymbol(visitor, expr); 
    2524    } else return doVisit(visitor, "(" ~ expr ~ ")"); 
    2625} 
     
    3433    if (expr.length>1 && expr[0]=='(') expr = expr[1..$-1]; 
    3534    else if (expr.length==1 && ((expr[0]>='A' && expr[0]<='Z') || expr[0]=='$')){ 
    36         return visitor.onVisitSymbol(visitor, expr[0]); 
     35        return visitor.onVisitSymbol(visitor, expr); 
    3736    } 
    3837    if (expr.length>3 && (expr[0]>='a' && expr[1]<='z') && expr[1]=='(') { // function 
     
    6564    if (op=="[") { 
    6665        right = right[0..$-1]; 
    67 //    printf("%.*s\t%.*s\t%.*s\n", op, left, right); 
    68         char [][] startslice; 
    69         char [][] endslice; 
    70         char [] sofar =""; 
     66        char [][2][] allslices=[];         
    7167        int z = 0; 
    7268        while (z<right.length) { 
    73             int w = exprLength(right[z..$]); 
    74             sofar ~= right[z..z+w+1] ~ "#"; 
    75             startslice ~= right[z..z+w+1]; 
    76             if (z+w+3 < right.length && right[z+w+1..z+w+3]=="..") { 
    77                 int q = z+w+3; 
    78                 w = exprLength(right[q..$]); 
    79                 endslice ~= right[q..q+w+1]; 
    80                 z = q+w+2; // no comma to skip 
     69            if (right[z]==',') { // null dimension 
     70                allslices ~= ["",""]; 
     71                ++z; 
    8172            } else { 
    82                 endslice ~=""; 
    83                 z = z+w+2; // skip the comma, if any 
     73                int w = exprLength(right[z..$]); 
     74                if (z+w+3 < right.length && right[z+w+1..z+w+3]=="..") { 
     75                    int q = z+w+3; 
     76                    int t = exprLength(right[q..$]); 
     77                    allslices ~= [ right[z..z+w+1], right[q..q+t+1]]; 
     78                    z = q+t+2; // no comma to skip 
     79                } else { 
     80                    allslices ~= [ right[z..z+w+1], ""]; 
     81                    z = z+w+2; // skip the comma, if any 
     82                 } 
    8483             } 
    8584        } 
    86  //       assert(0, "BUG:" ~ sofar ~ right); 
    87        return visitor.onVisitIndex(visitor, left, startslice, endslice);  
     85       return visitor.onVisitIndex(visitor, left, allslices);  
    8886    } 
    89 //    printf("%.*s\t%.*s\t%.*s\n", op, left, right); 
    9087    return visitor.onVisitBinaryOp(visitor, op, left, right); 
    9188} 
     
    119116    assert(0, "BLADE ICE: " ~ s);    
    120117} 
     118 
     119/* Wrap parentheses around the expression, if required 
     120*/ 
     121char [] wrapInParens(char [] a) 
     122{ 
     123    return (a.length==1)? a : "(" ~ a ~ ")"; 
     124} 
  • trunk/blade/PostfixX86.d

    r158 r159  
    3838    char [] ranklist; 
    3939static: 
    40     ReturnType onVisitSymbol(This this_, char sym) { 
    41         return sym ~ ""
     40    ReturnType onVisitSymbol(This this_, char [] sym) { 
     41        return sym
    4242    } 
    4343    ReturnType onVisitFunction(This this_, char [] func, char [][] args) { 
     
    5050        assert(0, "BLADE ICE: Unsupported"); 
    5151    } 
    52     ReturnType onVisitIndex(This this_, char [] base, char [][] startSlice, char [][] endSlice) { 
     52    ReturnType onVisitIndex(This this_, char [] base, char [][2][] slices) { 
    5353        assert(0, "BLADE ICE: Unsupported"); 
    5454    } 
     
    110110    char [] ranklist; 
    111111static: 
    112     ReturnType onVisitSymbol(This this_, char sym) { 
    113         return sym ~ ""
     112    ReturnType onVisitSymbol(This this_, char [] sym) { 
     113        return sym
    114114    } 
    115115    ReturnType onVisitFunction(This this_, char [] func, char [][] args) { 
     
    122122        assert(0, "BLADE ICE: Unsupported"); 
    123123    } 
    124     ReturnType onVisitIndex(This this_, char [] base, char [][] startSlice, char [][] endSlice) { 
     124    ReturnType onVisitIndex(This this_, char [] base, char [][2][] slices) { 
    125125        assert(0, "BLADE ICE: Unsupported"); 
    126126    }