1 /**
2  * Implement array operations, such as `a[] = b[] + c[]`.
3  *
4  * Specification: $(LINK2 https://dlang.org/spec/arrays.html#array-operations, Array Operations)
5  *
6  * Copyright:   Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved
7  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
8  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
9  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/arrayop.d, _arrayop.d)
10  * Documentation:  https://dlang.org/phobos/dmd_arrayop.html
11  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/arrayop.d
12  */
13 
14 module dmd.arrayop;
15 
16 import core.stdc.stdio;
17 import dmd.arraytypes;
18 import dmd.declaration;
19 import dmd.dscope;
20 import dmd.dsymbol;
21 import dmd.expression;
22 import dmd.expressionsem;
23 import dmd.func;
24 import dmd.globals;
25 import dmd.id;
26 import dmd.identifier;
27 import dmd.mtype;
28 import dmd.root.outbuffer;
29 import dmd.statement;
30 import dmd.tokens;
31 import dmd.visitor;
32 
33 /**********************************************
34  * Check that there are no uses of arrays without [].
35  */
36 bool isArrayOpValid(Expression e)
37 {
38     //printf("isArrayOpValid() %s\n", e.toChars());
39     if (e.op == TOK.slice)
40         return true;
41     if (e.op == TOK.arrayLiteral)
42     {
43         Type t = e.type.toBasetype();
44         while (t.ty == Tarray || t.ty == Tsarray)
45             t = t.nextOf().toBasetype();
46         return (t.ty != Tvoid);
47     }
48     Type tb = e.type.toBasetype();
49     if (tb.ty == Tarray || tb.ty == Tsarray)
50     {
51         if (isUnaArrayOp(e.op))
52         {
53             return isArrayOpValid((cast(UnaExp)e).e1);
54         }
55         if (isBinArrayOp(e.op) || isBinAssignArrayOp(e.op) || e.op == TOK.assign)
56         {
57             BinExp be = cast(BinExp)e;
58             return isArrayOpValid(be.e1) && isArrayOpValid(be.e2);
59         }
60         if (e.op == TOK.construct)
61         {
62             BinExp be = cast(BinExp)e;
63             return be.e1.op == TOK.slice && isArrayOpValid(be.e2);
64         }
65         // if (e.op == TOK.call)
66         // {
67         // TODO: Decide if [] is required after arrayop calls.
68         // }
69         return false;
70     }
71     return true;
72 }
73 
74 bool isNonAssignmentArrayOp(Expression e)
75 {
76     if (e.op == TOK.slice)
77         return isNonAssignmentArrayOp((cast(SliceExp)e).e1);
78 
79     Type tb = e.type.toBasetype();
80     if (tb.ty == Tarray || tb.ty == Tsarray)
81     {
82         return (isUnaArrayOp(e.op) || isBinArrayOp(e.op));
83     }
84     return false;
85 }
86 
87 bool checkNonAssignmentArrayOp(Expression e, bool suggestion = false)
88 {
89     if (isNonAssignmentArrayOp(e))
90     {
91         const(char)* s = "";
92         if (suggestion)
93             s = " (possible missing [])";
94         e.error("array operation `%s` without destination memory not allowed%s", e.toChars(), s);
95         return true;
96     }
97     return false;
98 }
99 
100 /***********************************
101  * Construct the array operation expression, call object._arrayOp!(tiargs)(args).
102  *
103  * Encode operand types and operations into tiargs using reverse polish notation (RPN) to preserve precedence.
104  * Unary operations are prefixed with "u" (e.g. "u~").
105  * Pass operand values (slices or scalars) as args.
106  *
107  * Scalar expression sub-trees of `e` are evaluated before calling
108  * into druntime to hoist them out of the loop. This is a valid
109  * evaluation order as the actual array operations have no
110  * side-effect.
111  * References:
112  * https://github.com/dlang/druntime/blob/master/src/object.d#L3944
113  * https://github.com/dlang/druntime/blob/master/src/core/internal/array/operations.d
114  */
115 Expression arrayOp(BinExp e, Scope* sc)
116 {
117     //printf("BinExp.arrayOp() %s\n", e.toChars());
118     Type tb = e.type.toBasetype();
119     assert(tb.ty == Tarray || tb.ty == Tsarray);
120     Type tbn = tb.nextOf().toBasetype();
121     if (tbn.ty == Tvoid)
122     {
123         e.error("cannot perform array operations on `void[]` arrays");
124         return ErrorExp.get();
125     }
126     if (!isArrayOpValid(e))
127         return arrayOpInvalidError(e);
128 
129     auto tiargs = new Objects();
130     auto args = new Expressions();
131     buildArrayOp(sc, e, tiargs, args);
132 
133     import dmd.dtemplate : TemplateDeclaration;
134     __gshared TemplateDeclaration arrayOp;
135     if (arrayOp is null)
136     {
137         // Create .object._arrayOp
138         Identifier idArrayOp = Identifier.idPool("_arrayOp");
139         Expression id = new IdentifierExp(e.loc, Id.empty);
140         id = new DotIdExp(e.loc, id, Id.object);
141         id = new DotIdExp(e.loc, id, idArrayOp);
142 
143         id = id.expressionSemantic(sc);
144         if (auto te = id.isTemplateExp())
145             arrayOp = te.td;
146         else
147             ObjectNotFound(idArrayOp);   // fatal error
148     }
149 
150     auto fd = resolveFuncCall(e.loc, sc, arrayOp, tiargs, null, args, FuncResolveFlag.standard);
151     if (!fd || fd.errors)
152         return ErrorExp.get();
153     return new CallExp(e.loc, new VarExp(e.loc, fd, false), args).expressionSemantic(sc);
154 }
155 
156 /// ditto
157 Expression arrayOp(BinAssignExp e, Scope* sc)
158 {
159     //printf("BinAssignExp.arrayOp() %s\n", toChars());
160 
161     /* Check that the elements of e1 can be assigned to
162      */
163     Type tn = e.e1.type.toBasetype().nextOf();
164 
165     if (tn && (!tn.isMutable() || !tn.isAssignable()))
166     {
167         e.error("slice `%s` is not mutable", e.e1.toChars());
168         if (e.op == TOK.addAssign)
169             checkPossibleAddCatError!(AddAssignExp, CatAssignExp)(e.isAddAssignExp);
170         return ErrorExp.get();
171     }
172     if (e.e1.op == TOK.arrayLiteral)
173     {
174         return e.e1.modifiableLvalue(sc, e.e1);
175     }
176 
177     return arrayOp(cast(BinExp)e, sc);
178 }
179 
180 /******************************************
181  * Convert the expression tree e to template and function arguments,
182  * using reverse polish notation (RPN) to encode order of operations.
183  * Encode operations as string arguments, using a "u" prefix for unary operations.
184  */
185 private void buildArrayOp(Scope* sc, Expression e, Objects* tiargs, Expressions* args)
186 {
187     extern (C++) final class BuildArrayOpVisitor : Visitor
188     {
189         alias visit = Visitor.visit;
190         Scope* sc;
191         Objects* tiargs;
192         Expressions* args;
193 
194     public:
195         extern (D) this(Scope* sc, Objects* tiargs, Expressions* args)
196         {
197             this.sc = sc;
198             this.tiargs = tiargs;
199             this.args = args;
200         }
201 
202         override void visit(Expression e)
203         {
204             tiargs.push(e.type);
205             args.push(e);
206         }
207 
208         override void visit(SliceExp e)
209         {
210             visit(cast(Expression) e);
211         }
212 
213         override void visit(CastExp e)
214         {
215             visit(cast(Expression) e);
216         }
217 
218         override void visit(UnaExp e)
219         {
220             Type tb = e.type.toBasetype();
221             if (tb.ty != Tarray && tb.ty != Tsarray) // hoist scalar expressions
222             {
223                 visit(cast(Expression) e);
224             }
225             else
226             {
227                 // RPN, prefix unary ops with u
228                 OutBuffer buf;
229                 buf.writestring("u");
230                 buf.writestring(Token.toString(e.op));
231                 e.e1.accept(this);
232                 tiargs.push(new StringExp(Loc.initial, buf.extractSlice()).expressionSemantic(sc));
233             }
234         }
235 
236         override void visit(BinExp e)
237         {
238             Type tb = e.type.toBasetype();
239             if (tb.ty != Tarray && tb.ty != Tsarray) // hoist scalar expressions
240             {
241                 visit(cast(Expression) e);
242             }
243             else
244             {
245                 // RPN
246                 e.e1.accept(this);
247                 e.e2.accept(this);
248                 tiargs.push(new StringExp(Loc.initial, Token.toString(e.op)).expressionSemantic(sc));
249             }
250         }
251     }
252 
253     scope v = new BuildArrayOpVisitor(sc, tiargs, args);
254     e.accept(v);
255 }
256 
257 /***********************************************
258  * Some implicit casting can be performed by the _arrayOp template.
259  * Params:
260  *      tfrom = type converting from
261  *      tto   = type converting to
262  * Returns:
263  *      true if can be performed by _arrayOp
264  */
265 bool isArrayOpImplicitCast(TypeDArray tfrom, TypeDArray tto)
266 {
267     const tyf = tfrom.nextOf().toBasetype().ty;
268     const tyt = tto  .nextOf().toBasetype().ty;
269     return tyf == tyt ||
270            tyf == Tint32 && tyt == Tfloat64;
271 }
272 
273 /***********************************************
274  * Test if expression is a unary array op.
275  */
276 bool isUnaArrayOp(TOK op)
277 {
278     switch (op)
279     {
280     case TOK.negate:
281     case TOK.tilde:
282         return true;
283     default:
284         break;
285     }
286     return false;
287 }
288 
289 /***********************************************
290  * Test if expression is a binary array op.
291  */
292 bool isBinArrayOp(TOK op)
293 {
294     switch (op)
295     {
296     case TOK.add:
297     case TOK.min:
298     case TOK.mul:
299     case TOK.div:
300     case TOK.mod:
301     case TOK.xor:
302     case TOK.and:
303     case TOK.or:
304     case TOK.pow:
305         return true;
306     default:
307         break;
308     }
309     return false;
310 }
311 
312 /***********************************************
313  * Test if expression is a binary assignment array op.
314  */
315 bool isBinAssignArrayOp(TOK op)
316 {
317     switch (op)
318     {
319     case TOK.addAssign:
320     case TOK.minAssign:
321     case TOK.mulAssign:
322     case TOK.divAssign:
323     case TOK.modAssign:
324     case TOK.xorAssign:
325     case TOK.andAssign:
326     case TOK.orAssign:
327     case TOK.powAssign:
328         return true;
329     default:
330         break;
331     }
332     return false;
333 }
334 
335 /***********************************************
336  * Test if operand is a valid array op operand.
337  */
338 bool isArrayOpOperand(Expression e)
339 {
340     //printf("Expression.isArrayOpOperand() %s\n", e.toChars());
341     if (e.op == TOK.slice)
342         return true;
343     if (e.op == TOK.arrayLiteral)
344     {
345         Type t = e.type.toBasetype();
346         while (t.ty == Tarray || t.ty == Tsarray)
347             t = t.nextOf().toBasetype();
348         return (t.ty != Tvoid);
349     }
350     Type tb = e.type.toBasetype();
351     if (tb.ty == Tarray)
352     {
353         return (isUnaArrayOp(e.op) ||
354                 isBinArrayOp(e.op) ||
355                 isBinAssignArrayOp(e.op) ||
356                 e.op == TOK.assign);
357     }
358     return false;
359 }
360 
361 
362 /***************************************************
363  * Print error message about invalid array operation.
364  * Params:
365  *      e = expression with the invalid array operation
366  * Returns:
367  *      instance of ErrorExp
368  */
369 
370 ErrorExp arrayOpInvalidError(Expression e)
371 {
372     e.error("invalid array operation `%s` (possible missing [])", e.toChars());
373     if (e.op == TOK.add)
374         checkPossibleAddCatError!(AddExp, CatExp)(e.isAddExp());
375     else if (e.op == TOK.addAssign)
376         checkPossibleAddCatError!(AddAssignExp, CatAssignExp)(e.isAddAssignExp());
377     return ErrorExp.get();
378 }
379 
380 private void checkPossibleAddCatError(AddT, CatT)(AddT ae)
381 {
382     if (!ae.e2.type || ae.e2.type.ty != Tarray || !ae.e2.type.implicitConvTo(ae.e1.type))
383         return;
384     CatT ce = new CatT(ae.loc, ae.e1, ae.e2);
385     ae.errorSupplemental("did you mean to concatenate (`%s`) instead ?", ce.toChars());
386 }