gcc/d/dmd/arrayop.d

   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  */
  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
  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  */
 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
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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
 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
 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 }