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