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