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-2023 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.errors;
  23 import dmd.expression;
  24 import dmd.expressionsem;
  25 import dmd.func;
  26 import dmd.hdrgen;
  27 import dmd.id;
  28 import dmd.identifier;
  29 import dmd.location;
  30 import dmd.mtype;
  31 import dmd.common.outbuffer;
  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         error(e.loc, "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/dmd/blob/cdfadf8a18f474e6a1b8352af2541efe3e3467cc/druntime/src/object.d#L4694
 115  * https://github.com/dlang/dmd/blob/master/druntime/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         error(e.loc, "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 = buildArrayOp(sc, e, tiargs);
 133
 134     import dmd.dtemplate : TemplateDeclaration;
 135     __gshared TemplateDeclaration arrayOp;
 136     if (arrayOp is null)
 137     {
 138         // Create .object._arrayOp
 139         Identifier idArrayOp = Identifier.idPool("_arrayOp");
 140         Expression id = new IdentifierExp(e.loc, Id.empty);
 141         id = new DotIdExp(e.loc, id, Id.object);
 142         id = new DotIdExp(e.loc, id, idArrayOp);
 143
 144         id = id.expressionSemantic(sc);
 145         if (auto te = id.isTemplateExp())
 146             arrayOp = te.td;
 147         else
 148             ObjectNotFound(idArrayOp);   // fatal error
 149     }
 150
 151     auto fd = resolveFuncCall(e.loc, sc, arrayOp, tiargs, null, ArgumentList(args), FuncResolveFlag.standard);
 152     if (!fd || fd.errors)
 153         return ErrorExp.get();
 154     return new CallExp(e.loc, new VarExp(e.loc, fd, false), args).expressionSemantic(sc);
 155 }
 156
 157 /// ditto
 158 Expression arrayOp(BinAssignExp e, Scope* sc)
 159 {
 160     //printf("BinAssignExp.arrayOp() %s\n", e.toChars());
 161
 162     /* Check that the elements of e1 can be assigned to
 163      */
 164     Type tn = e.e1.type.toBasetype().nextOf();
 165
 166     if (tn && (!tn.isMutable() || !tn.isAssignable()))
 167     {
 168         error(e.loc, "slice `%s` is not mutable", e.e1.toChars());
 169         if (e.op == EXP.addAssign)
 170             checkPossibleAddCatError!(AddAssignExp, CatAssignExp)(e.isAddAssignExp);
 171         return ErrorExp.get();
 172     }
 173     if (e.e1.op == EXP.arrayLiteral)
 174     {
 175         return e.e1.modifiableLvalue(sc, e.e1);
 176     }
 177
 178     return arrayOp(e.isBinExp(), sc);
 179 }
 180
 181 /******************************************
 182  * Convert the expression tree e to template and function arguments,
 183  * using reverse polish notation (RPN) to encode order of operations.
 184  * Encode operations as string arguments, using a "u" prefix for unary operations.
 185  */
 186 private Expressions* buildArrayOp(Scope* sc, Expression e, Objects* tiargs)
 187 {
 188     extern (C++) final class BuildArrayOpVisitor : Visitor
 189     {
 190         alias visit = Visitor.visit;
 191         Scope* sc;
 192         Objects* tiargs;
 193         Expressions* args;
 194
 195     public:
 196         extern (D) this(Scope* sc, Objects* tiargs) scope @safe
 197         {
 198             this.sc = sc;
 199             this.tiargs = tiargs;
 200             this.args = new Expressions();
 201         }
 202
 203         override void visit(Expression e)
 204         {
 205             tiargs.push(e.type);
 206             args.push(e);
 207         }
 208
 209         override void visit(SliceExp e)
 210         {
 211             visit(cast(Expression) e);
 212         }
 213
 214         override void visit(CastExp e)
 215         {
 216             visit(cast(Expression) e);
 217         }
 218
 219         override void visit(UnaExp e)
 220         {
 221             Type tb = e.type.toBasetype();
 222             if (tb.ty != Tarray && tb.ty != Tsarray) // hoist scalar expressions
 223             {
 224                 visit(cast(Expression) e);
 225             }
 226             else
 227             {
 228                 // RPN, prefix unary ops with u
 229                 OutBuffer buf;
 230                 buf.writestring("u");
 231                 buf.writestring(EXPtoString(e.op));
 232                 e.e1.accept(this);
 233                 tiargs.push(new StringExp(Loc.initial, buf.extractSlice()).expressionSemantic(sc));
 234             }
 235         }
 236
 237         override void visit(BinExp e)
 238         {
 239             Type tb = e.type.toBasetype();
 240             if (tb.ty != Tarray && tb.ty != Tsarray) // hoist scalar expressions
 241             {
 242                 visit(cast(Expression) e);
 243             }
 244             else
 245             {
 246                 // RPN
 247                 e.e1.accept(this);
 248                 e.e2.accept(this);
 249                 tiargs.push(new StringExp(Loc.initial, EXPtoString(e.op)).expressionSemantic(sc));
 250             }
 251         }
 252     }
 253
 254     scope v = new BuildArrayOpVisitor(sc, tiargs);
 255     e.accept(v);
 256     return v.args;
 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) @safe
 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) @safe
 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) @safe
 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     error(e.loc, "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     errorSupplemental(ae.loc, "did you mean to concatenate (`%s`) instead ?", ce.toChars());
 388 }