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
26void buildArrayIdent(Expression *e, OutBuffer *buf, Expressions *arguments);
27Expression *buildArrayLoop(Expression *e, Parameters *fparams);
28Expression *semantic(Expression *e, Scope *sc);
29
30/**************************************
31 * Hash table of array op functions already generated or known about.
32 */
33
34AA *arrayfuncs;
35
36/**************************************
37 * Structure to contain information needed to insert an array op call
38 */
39
40FuncDeclaration *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 */
101bool 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
143bool 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
156bool 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
173Expression *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
237Expression *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
263void 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
409Expression *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
549bool 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
566bool 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
590bool 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
614bool 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