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