Unofficial Dub Package Documentation 
1 /**
2  * Compiler implementation of the
3  * $(LINK2 http://www.dlang.org, D programming language).
4  *
5  * Copyright:   Copyright (c) 1999-2016 by Digital Mars, All Rights Reserved
6  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
7  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
8  * Source:      $(DMDSRC _arrayop.d)
9  */
10 
11 module ddmd.arrayop;
12 
13 import core.stdc.stdio;
14 import ddmd.arraytypes;
15 import ddmd.declaration;
16 import ddmd.dscope;
17 import ddmd.dsymbol;
18 import ddmd.expression;
19 import ddmd.func;
20 import ddmd.globals;
21 import ddmd.id;
22 import ddmd.identifier;
23 import ddmd.mtype;
24 import ddmd.root.outbuffer;
25 import ddmd.statement;
26 import ddmd.tokens;
27 import ddmd.visitor;
28 
29 /**************************************
30  * Hash table of array op functions already generated or known about.
31  */
32 private __gshared FuncDeclaration[void*] arrayfuncs;
33 
34 
35 /**************************************
36  * Structure to contain information needed to insert an array op call
37  */
38 extern (C++) FuncDeclaration buildArrayOp(Identifier ident, BinExp exp, Scope* sc, Loc loc)
39 {
40     auto fparams = new Parameters();
41     Expression loopbody = buildArrayLoop(exp, fparams);
42 
43     /* Construct the function body:
44      *  foreach (i; 0 .. p.length)    for (size_t i = 0; i < p.length; i++)
45      *      loopbody;
46      *  return p;
47      */
48 
49     Parameter p = (*fparams)[0];
50     // foreach (i; 0 .. p.length)
51     Statement s1 = new ForeachRangeStatement(Loc(), TOKforeach,
52         new Parameter(0, null, Id.p, null),
53         new IntegerExp(Loc(), 0, Type.tsize_t),
54         new ArrayLengthExp(Loc(), new IdentifierExp(Loc(), p.ident)),
55         new ExpStatement(Loc(), loopbody),
56         Loc());
57     //printf("%s\n", s1.toChars());
58     Statement s2 = new ReturnStatement(Loc(), new IdentifierExp(Loc(), p.ident));
59     //printf("s2: %s\n", s2.toChars());
60     Statement fbody = new CompoundStatement(Loc(), s1, s2);
61 
62     // Built-in array ops should be @trusted, pure, nothrow and nogc
63     StorageClass stc = STCtrusted | STCpure | STCnothrow | STCnogc;
64 
65     /* Construct the function
66      */
67     auto ftype = new TypeFunction(fparams, exp.e1.type, 0, LINKc, stc);
68     //printf("fd: %s %s\n", ident.toChars(), ftype.toChars());
69     //printf("fbody: %s\n", fbody.toChars());
70     auto fd = new FuncDeclaration(Loc(), Loc(), ident, STCundefined, ftype);
71     fd.fbody = fbody;
72     fd.protection = Prot(PROTpublic);
73     fd.linkage = LINKc;
74     fd.isArrayOp = 1;
75 
76     sc._module.importedFrom.members.push(fd);
77 
78     sc = sc.push();
79     sc.parent = sc._module.importedFrom;
80     sc.stc = 0;
81     sc.linkage = LINKc;
82     fd.semantic(sc);
83     fd.semantic2(sc);
84     uint errors = global.startGagging();
85     fd.semantic3(sc);
86     if (global.endGagging(errors))
87     {
88         fd.type = Type.terror;
89         fd.errors = true;
90         fd.fbody = null;
91     }
92     sc.pop();
93 
94     return fd;
95 }
96 
97 /**********************************************
98  * Check that there are no uses of arrays without [].
99  */
100 extern (C++) bool isArrayOpValid(Expression e)
101 {
102     if (e.op == TOKslice)
103         return true;
104     if (e.op == TOKarrayliteral)
105     {
106         Type t = e.type.toBasetype();
107         while (t.ty == Tarray || t.ty == Tsarray)
108             t = t.nextOf().toBasetype();
109         return (t.ty != Tvoid);
110     }
111     Type tb = e.type.toBasetype();
112     if (tb.ty == Tarray || tb.ty == Tsarray)
113     {
114         if (isUnaArrayOp(e.op))
115         {
116             return isArrayOpValid((cast(UnaExp)e).e1);
117         }
118         if (isBinArrayOp(e.op) || isBinAssignArrayOp(e.op) || e.op == TOKassign)
119         {
120             BinExp be = cast(BinExp)e;
121             return isArrayOpValid(be.e1) && isArrayOpValid(be.e2);
122         }
123         if (e.op == TOKconstruct)
124         {
125             BinExp be = cast(BinExp)e;
126             return be.e1.op == TOKslice && isArrayOpValid(be.e2);
127         }
128         if (e.op == TOKcall)
129         {
130             return false; // TODO: Decide if [] is required after arrayop calls.
131         }
132         else
133         {
134             return false;
135         }
136     }
137     return true;
138 }
139 
140 extern (C++) bool isNonAssignmentArrayOp(Expression e)
141 {
142     if (e.op == TOKslice)
143         return isNonAssignmentArrayOp((cast(SliceExp)e).e1);
144 
145     Type tb = e.type.toBasetype();
146     if (tb.ty == Tarray || tb.ty == Tsarray)
147     {
148         return (isUnaArrayOp(e.op) || isBinArrayOp(e.op));
149     }
150     return false;
151 }
152 
153 extern (C++) bool checkNonAssignmentArrayOp(Expression e, bool suggestion = false)
154 {
155     if (isNonAssignmentArrayOp(e))
156     {
157         const(char)* s = "";
158         if (suggestion)
159             s = " (possible missing [])";
160         e.error("array operation %s without destination memory not allowed%s", e.toChars(), s);
161         return true;
162     }
163     return false;
164 }
165 
166 /***********************************
167  * Construct the array operation expression.
168  */
169 extern (C++) Expression arrayOp(BinExp e, Scope* sc)
170 {
171     //printf("BinExp.arrayOp() %s\n", toChars());
172     Type tb = e.type.toBasetype();
173     assert(tb.ty == Tarray || tb.ty == Tsarray);
174     Type tbn = tb.nextOf().toBasetype();
175     if (tbn.ty == Tvoid)
176     {
177         e.error("cannot perform array operations on void[] arrays");
178         return new ErrorExp();
179     }
180     if (!isArrayOpValid(e))
181     {
182         e.error("invalid array operation %s (possible missing [])", e.toChars());
183         return new ErrorExp();
184     }
185 
186     auto arguments = new Expressions();
187 
188     /* The expression to generate an array operation for is mangled
189      * into a name to use as the array operation function name.
190      * Mangle in the operands and operators in RPN order, and type.
191      */
192     OutBuffer buf;
193     buf.writestring("_array");
194     buildArrayIdent(e, &buf, arguments);
195     buf.writeByte('_');
196 
197     /* Append deco of array element type
198      */
199     buf.writestring(e.type.toBasetype().nextOf().toBasetype().mutableOf().deco);
200 
201     auto ident = Identifier.idPool(buf.peekSlice());
202 
203     FuncDeclaration* pFd = cast(void*)ident in arrayfuncs;
204     FuncDeclaration fd;
205     if (pFd)
206         fd = *pFd;
207     else
208         fd = buildArrayOp(ident, e, sc, e.loc);
209 
210     if (fd && fd.errors)
211     {
212         const(char)* fmt;
213         if (tbn.ty == Tstruct || tbn.ty == Tclass)
214             fmt = "invalid array operation '%s' because %s doesn't support necessary arithmetic operations";
215         else if (!tbn.isscalar())
216             fmt = "invalid array operation '%s' because %s is not a scalar type";
217         else
218             fmt = "invalid array operation '%s' for element type %s";
219         e.error(fmt, e.toChars(), tbn.toChars());
220         return new ErrorExp();
221     }
222 
223     if (!pFd)
224         arrayfuncs[cast(void*)ident] = fd;
225 
226     Expression ev = new VarExp(e.loc, fd);
227     Expression ec = new CallExp(e.loc, ev, arguments);
228     return ec.semantic(sc);
229 }
230 
231 extern (C++) Expression arrayOp(BinAssignExp e, Scope* sc)
232 {
233     //printf("BinAssignExp.arrayOp() %s\n", toChars());
234 
235     /* Check that the elements of e1 can be assigned to
236      */
237     Type tn = e.e1.type.toBasetype().nextOf();
238 
239     if (tn && (!tn.isMutable() || !tn.isAssignable()))
240     {
241         e.error("slice %s is not mutable", e.e1.toChars());
242         return new ErrorExp();
243     }
244     if (e.e1.op == TOKarrayliteral)
245     {
246         return e.e1.modifiableLvalue(sc, e.e1);
247     }
248 
249     return arrayOp(cast(BinExp)e, sc);
250 }
251 
252 /******************************************
253  * Construct the identifier for the array operation function,
254  * and build the argument list to pass to it.
255  */
256 extern (C++) void buildArrayIdent(Expression e, OutBuffer* buf, Expressions* arguments)
257 {
258     extern (C++) final class BuildArrayIdentVisitor : Visitor
259     {
260         alias visit = super.visit;
261         OutBuffer* buf;
262         Expressions* arguments;
263 
264     public:
265         extern (D) this(OutBuffer* buf, Expressions* arguments)
266         {
267             this.buf = buf;
268             this.arguments = arguments;
269         }
270 
271         override void visit(Expression e)
272         {
273             buf.writestring("Exp");
274             arguments.shift(e);
275         }
276 
277         override void visit(CastExp e)
278         {
279             Type tb = e.type.toBasetype();
280             if (tb.ty == Tarray || tb.ty == Tsarray)
281             {
282                 e.e1.accept(this);
283             }
284             else
285                 visit(cast(Expression)e);
286         }
287 
288         override void visit(ArrayLiteralExp e)
289         {
290             buf.writestring("Slice");
291             arguments.shift(e);
292         }
293 
294         override void visit(SliceExp e)
295         {
296             buf.writestring("Slice");
297             arguments.shift(e);
298         }
299 
300         override void visit(AssignExp e)
301         {
302             /* Evaluate assign expressions right to left
303              */
304             e.e2.accept(this);
305             e.e1.accept(this);
306             buf.writestring("Assign");
307         }
308 
309         override void visit(BinAssignExp e)
310         {
311             /* Evaluate assign expressions right to left
312              */
313             e.e2.accept(this);
314             e.e1.accept(this);
315             const(char)* s;
316             switch (e.op)
317             {
318             case TOKaddass: s = "Addass";   break;
319             case TOKminass: s = "Subass";   break;
320             case TOKmulass: s = "Mulass";   break;
321             case TOKdivass: s = "Divass";   break;
322             case TOKmodass: s = "Modass";   break;
323             case TOKxorass: s = "Xorass";   break;
324             case TOKandass: s = "Andass";   break;
325             case TOKorass:  s =  "Orass";   break;
326             case TOKpowass: s = "Powass";   break;
327             default:
328                 assert(0);
329             }
330             buf.writestring(s);
331         }
332 
333         override void visit(NegExp e)
334         {
335             e.e1.accept(this);
336             buf.writestring("Neg");
337         }
338 
339         override void visit(ComExp e)
340         {
341             e.e1.accept(this);
342             buf.writestring("Com");
343         }
344 
345         override void visit(BinExp e)
346         {
347             /* Evaluate assign expressions left to right
348              */
349             const(char)* s = null;
350             switch (e.op)
351             {
352             case TOKadd:    s = "Add";  break;
353             case TOKmin:    s = "Sub";  break;
354             case TOKmul:    s = "Mul";  break;
355             case TOKdiv:    s = "Div";  break;
356             case TOKmod:    s = "Mod";  break;
357             case TOKxor:    s = "Xor";  break;
358             case TOKand:    s = "And";  break;
359             case TOKor:     s = "Or";   break;
360             case TOKpow:    s = "Pow";  break;
361             default:
362                 break;
363             }
364             if (s)
365             {
366                 Type tb = e.type.toBasetype();
367                 Type t1 = e.e1.type.toBasetype();
368                 Type t2 = e.e2.type.toBasetype();
369                 e.e1.accept(this);
370                 if (t1.ty == Tarray &&
371                     (t2.ty == Tarray && !t1.equivalent(tb) ||
372                      t2.ty != Tarray && !t1.nextOf().equivalent(e.e2.type)))
373                 {
374                     // Bugzilla 12780: if A is narrower than B
375                     //  A[] op B[]
376                     //  A[] op B
377                     buf.writestring("Of");
378                     buf.writestring(t1.nextOf().mutableOf().deco);
379                 }
380                 e.e2.accept(this);
381                 if (t2.ty == Tarray &&
382                     (t1.ty == Tarray && !t2.equivalent(tb) ||
383                      t1.ty != Tarray && !t2.nextOf().equivalent(e.e1.type)))
384                 {
385                     // Bugzilla 12780: if B is narrower than A:
386                     //  A[] op B[]
387                     //  A op B[]
388                     buf.writestring("Of");
389                     buf.writestring(t2.nextOf().mutableOf().deco);
390                 }
391                 buf.writestring(s);
392             }
393             else
394                 visit(cast(Expression)e);
395         }
396     }
397 
398     scope BuildArrayIdentVisitor v = new BuildArrayIdentVisitor(buf, arguments);
399     e.accept(v);
400 }
401 
402 /******************************************
403  * Construct the inner loop for the array operation function,
404  * and build the parameter list.
405  */
406 extern (C++) Expression buildArrayLoop(Expression e, Parameters* fparams)
407 {
408     extern (C++) final class BuildArrayLoopVisitor : Visitor
409     {
410         alias visit = super.visit;
411         Parameters* fparams;
412         Expression result;
413 
414     public:
415         extern (D) this(Parameters* fparams)
416         {
417             this.fparams = fparams;
418         }
419 
420         override void visit(Expression e)
421         {
422             Identifier id = Identifier.generateId("c", fparams.dim);
423             auto param = new Parameter(0, e.type, id, null);
424             fparams.shift(param);
425             result = new IdentifierExp(Loc(), id);
426         }
427 
428         override void visit(CastExp e)
429         {
430             Type tb = e.type.toBasetype();
431             if (tb.ty == Tarray || tb.ty == Tsarray)
432             {
433                 e.e1.accept(this);
434             }
435             else
436                 visit(cast(Expression)e);
437         }
438 
439         override void visit(ArrayLiteralExp e)
440         {
441             Identifier id = Identifier.generateId("p", fparams.dim);
442             auto param = new Parameter(STCconst, e.type, id, null);
443             fparams.shift(param);
444             Expression ie = new IdentifierExp(Loc(), id);
445             Expression index = new IdentifierExp(Loc(), Id.p);
446             result = new ArrayExp(Loc(), ie, index);
447         }
448 
449         override void visit(SliceExp e)
450         {
451             Identifier id = Identifier.generateId("p", fparams.dim);
452             auto param = new Parameter(STCconst, e.type, id, null);
453             fparams.shift(param);
454             Expression ie = new IdentifierExp(Loc(), id);
455             Expression index = new IdentifierExp(Loc(), Id.p);
456             result = new ArrayExp(Loc(), ie, index);
457         }
458 
459         override void visit(AssignExp e)
460         {
461             /* Evaluate assign expressions right to left
462              */
463             Expression ex2 = buildArrayLoop(e.e2);
464             /* Need the cast because:
465              *   b = c + p[i];
466              * where b is a byte fails because (c + p[i]) is an int
467              * which cannot be implicitly cast to byte.
468              */
469             ex2 = new CastExp(Loc(), ex2, e.e1.type.nextOf());
470             Expression ex1 = buildArrayLoop(e.e1);
471             Parameter param = (*fparams)[0];
472             param.storageClass = 0;
473             result = new AssignExp(Loc(), ex1, ex2);
474         }
475 
476         override void visit(BinAssignExp e)
477         {
478             /* Evaluate assign expressions right to left
479              */
480             Expression ex2 = buildArrayLoop(e.e2);
481             Expression ex1 = buildArrayLoop(e.e1);
482             Parameter param = (*fparams)[0];
483             param.storageClass = 0;
484             switch (e.op)
485             {
486             case TOKaddass: result = new AddAssignExp(e.loc, ex1, ex2); return;
487             case TOKminass: result = new MinAssignExp(e.loc, ex1, ex2); return;
488             case TOKmulass: result = new MulAssignExp(e.loc, ex1, ex2); return;
489             case TOKdivass: result = new DivAssignExp(e.loc, ex1, ex2); return;
490             case TOKmodass: result = new ModAssignExp(e.loc, ex1, ex2); return;
491             case TOKxorass: result = new XorAssignExp(e.loc, ex1, ex2); return;
492             case TOKandass: result = new AndAssignExp(e.loc, ex1, ex2); return;
493             case TOKorass:  result = new  OrAssignExp(e.loc, ex1, ex2); return;
494             case TOKpowass: result = new PowAssignExp(e.loc, ex1, ex2); return;
495             default:
496                 assert(0);
497             }
498         }
499 
500         override void visit(NegExp e)
501         {
502             Expression ex1 = buildArrayLoop(e.e1);
503             result = new NegExp(Loc(), ex1);
504         }
505 
506         override void visit(ComExp e)
507         {
508             Expression ex1 = buildArrayLoop(e.e1);
509             result = new ComExp(Loc(), ex1);
510         }
511 
512         override void visit(BinExp e)
513         {
514             if (isBinArrayOp(e.op))
515             {
516                 /* Evaluate assign expressions left to right
517                  */
518                 BinExp be = cast(BinExp)e.copy();
519                 be.e1 = buildArrayLoop(be.e1);
520                 be.e2 = buildArrayLoop(be.e2);
521                 be.type = null;
522                 result = be;
523                 return;
524             }
525             else
526             {
527                 visit(cast(Expression)e);
528                 return;
529             }
530         }
531 
532         Expression buildArrayLoop(Expression e)
533         {
534             e.accept(this);
535             return result;
536         }
537     }
538 
539     scope BuildArrayLoopVisitor v = new BuildArrayLoopVisitor(fparams);
540     return v.buildArrayLoop(e);
541 }
542 
543 /***********************************************
544  * Test if expression is a unary array op.
545  */
546 extern (C++) bool isUnaArrayOp(TOK op)
547 {
548     switch (op)
549     {
550     case TOKneg:
551     case TOKtilde:
552         return true;
553     default:
554         break;
555     }
556     return false;
557 }
558 
559 /***********************************************
560  * Test if expression is a binary array op.
561  */
562 extern (C++) bool isBinArrayOp(TOK op)
563 {
564     switch (op)
565     {
566     case TOKadd:
567     case TOKmin:
568     case TOKmul:
569     case TOKdiv:
570     case TOKmod:
571     case TOKxor:
572     case TOKand:
573     case TOKor:
574     case TOKpow:
575         return true;
576     default:
577         break;
578     }
579     return false;
580 }
581 
582 /***********************************************
583  * Test if expression is a binary assignment array op.
584  */
585 extern (C++) bool isBinAssignArrayOp(TOK op)
586 {
587     switch (op)
588     {
589     case TOKaddass:
590     case TOKminass:
591     case TOKmulass:
592     case TOKdivass:
593     case TOKmodass:
594     case TOKxorass:
595     case TOKandass:
596     case TOKorass:
597     case TOKpowass:
598         return true;
599     default:
600         break;
601     }
602     return false;
603 }
604 
605 /***********************************************
606  * Test if operand is a valid array op operand.
607  */
608 extern (C++) bool isArrayOpOperand(Expression e)
609 {
610     //printf("Expression.isArrayOpOperand() %s\n", e->toChars());
611     if (e.op == TOKslice)
612         return true;
613     if (e.op == TOKarrayliteral)
614     {
615         Type t = e.type.toBasetype();
616         while (t.ty == Tarray || t.ty == Tsarray)
617             t = t.nextOf().toBasetype();
618         return (t.ty != Tvoid);
619     }
620     Type tb = e.type.toBasetype();
621     if (tb.ty == Tarray)
622     {
623         return (isUnaArrayOp(e.op) ||
624                 isBinArrayOp(e.op) ||
625                 isBinAssignArrayOp(e.op) ||
626                 e.op == TOKassign);
627     }
628     return false;
629 }
Page generated by adrdox