gcc/d/dmd/arrayop.c

   1
   2 /* Compiler implementation of the D programming language
   3  * Copyright (C) 1999-2021 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
  26 void buildArrayIdent(Expression *e, OutBuffer *buf, Expressions *arguments);
  27 Expression *buildArrayLoop(Expression *e, Parameters *fparams);
  28
  29 /**************************************
  30  * Hash table of array op functions already generated or known about.
  31  */
  32
  33 AA *arrayfuncs;
  34
  35 /**************************************
  36  * Structure to contain information needed to insert an array op call
  37  */
  38
  39 FuncDeclaration *buildArrayOp(Identifier *ident, BinExp *exp, Scope *sc)
  40 {
  41     Parameters *fparams = new Parameters();
  42     Expression *loopbody = buildArrayLoop(exp, fparams);
  43
  44     /* Construct the function body:
  45      *  foreach (i; 0 .. p.length)    for (size_t i = 0; i < p.length; i++)
  46      *      loopbody;
  47      *  return p;
  48      */
  49
  50     Parameter *p = (*fparams)[0];
  51     // foreach (i; 0 .. p.length)
  52     Statement *s1 = new ForeachRangeStatement(Loc(), TOKforeach,
  53         new Parameter(0, NULL, Id::p, NULL, NULL),
  54         new IntegerExp(Loc(), 0, Type::tsize_t),
  55         new ArrayLengthExp(Loc(), new IdentifierExp(Loc(), p->ident)),
  56         new ExpStatement(Loc(), loopbody),
  57         Loc());
  58     //printf("%s\n", s1->toChars());
  59     Statement *s2 = new ReturnStatement(Loc(), new IdentifierExp(Loc(), p->ident));
  60     //printf("s2: %s\n", s2->toChars());
  61     Statement *fbody = new CompoundStatement(Loc(), s1, s2);
  62
  63     // Built-in array ops should be @trusted, pure, nothrow and nogc
  64     StorageClass stc = STCtrusted | STCpure | STCnothrow | STCnogc;
  65
  66     /* Construct the function
  67      */
  68     TypeFunction *ftype = new TypeFunction(ParameterList(fparams), exp->e1->type, LINKc, stc);
  69     //printf("fd: %s %s\n", ident->toChars(), ftype->toChars());
  70     FuncDeclaration *fd = new FuncDeclaration(Loc(), Loc(), ident, STCundefined, ftype);
  71     fd->fbody = fbody;
  72     fd->protection = Prot(Prot::public_);
  73     fd->linkage = LINKc;
  74     fd->isArrayOp = 1;
  75
  76     sc->_module->importedFrom->members->push(fd);
  77
  78     sc = sc->push();
  79     sc->parent = sc->_module->importedFrom;
  80     sc->stc = 0;
  81     sc->linkage = LINKc;
  82     dsymbolSemantic(fd, sc);
  83     semantic2(fd, sc);
  84     unsigned errors = global.startGagging();
  85     semantic3(fd, sc);
  86     if (global.endGagging(errors))
  87     {
  88         fd->type = Type::terror;
  89         fd->errors = true;
  90         fd->fbody = NULL;
  91     }
  92     sc->pop();
  93
  94     return fd;
  95 }
  96
  97 /**********************************************
  98  * Check that there are no uses of arrays without [].
  99  */
 100 bool isArrayOpValid(Expression *e)
 101 {
 102     if (e->op == TOKslice)
 103         return true;
 104     if (e->op == TOKarrayliteral)
 105     {
 106         Type *t = e->type->toBasetype();
 107         while (t->ty == Tarray || t->ty == Tsarray)
 108             t = t->nextOf()->toBasetype();
 109         return (t->ty != Tvoid);
 110     }
 111     Type *tb = e->type->toBasetype();
 112     if (tb->ty == Tarray || tb->ty == Tsarray)
 113     {
 114         if (isUnaArrayOp(e->op))
 115         {
 116              return isArrayOpValid(((UnaExp *)e)->e1);
 117         }
 118         if (isBinArrayOp(e->op) ||
 119             isBinAssignArrayOp(e->op) ||
 120             e->op == TOKassign)
 121         {
 122             BinExp *be = (BinExp *)e;
 123             return isArrayOpValid(be->e1) && isArrayOpValid(be->e2);
 124         }
 125         if (e->op == TOKconstruct)
 126         {
 127             BinExp *be = (BinExp *)e;
 128             return be->e1->op == TOKslice && isArrayOpValid(be->e2);
 129         }
 130         if (e->op == TOKcall)
 131         {
 132              return false; // TODO: Decide if [] is required after arrayop calls.
 133         }
 134         else
 135         {
 136             return false;
 137         }
 138     }
 139     return true;
 140 }
 141
 142 bool isNonAssignmentArrayOp(Expression *e)
 143 {
 144     if (e->op == TOKslice)
 145         return isNonAssignmentArrayOp(((SliceExp *)e)->e1);
 146
 147     Type *tb = e->type->toBasetype();
 148     if (tb->ty == Tarray || tb->ty == Tsarray)
 149     {
 150         return (isUnaArrayOp(e->op) || isBinArrayOp(e->op));
 151     }
 152     return false;
 153 }
 154
 155 bool checkNonAssignmentArrayOp(Expression *e, bool suggestion)
 156 {
 157     if (isNonAssignmentArrayOp(e))
 158     {
 159         const char *s = "";
 160         if (suggestion)
 161             s = " (possible missing [])";
 162         e->error("array operation %s without destination memory not allowed%s", e->toChars(), s);
 163         return true;
 164     }
 165     return false;
 166 }
 167
 168 /***********************************
 169  * Construct the array operation expression.
 170  */
 171
 172 Expression *arrayOp(BinExp *e, Scope *sc)
 173 {
 174     //printf("BinExp::arrayOp() %s\n", toChars());
 175
 176     Type *tb = e->type->toBasetype();
 177     assert(tb->ty == Tarray || tb->ty == Tsarray);
 178     Type *tbn = tb->nextOf()->toBasetype();
 179     if (tbn->ty == Tvoid)
 180     {
 181         e->error("cannot perform array operations on void[] arrays");
 182         return new ErrorExp();
 183     }
 184     if (!isArrayOpValid(e))
 185     {
 186         e->error("invalid array operation %s (possible missing [])", e->toChars());
 187         return new ErrorExp();
 188     }
 189
 190     Expressions *arguments = new Expressions();
 191
 192     /* The expression to generate an array operation for is mangled
 193      * into a name to use as the array operation function name.
 194      * Mangle in the operands and operators in RPN order, and type.
 195      */
 196     OutBuffer buf;
 197     buf.writestring("_array");
 198     buildArrayIdent(e, &buf, arguments);
 199     buf.writeByte('_');
 200
 201     /* Append deco of array element type
 202      */
 203     buf.writestring(e->type->toBasetype()->nextOf()->toBasetype()->mutableOf()->deco);
 204
 205     char *name = buf.peekChars();
 206     Identifier *ident = Identifier::idPool(name);
 207
 208     FuncDeclaration **pFd = (FuncDeclaration **)dmd_aaGet(&arrayfuncs, (void *)ident);
 209     FuncDeclaration *fd = *pFd;
 210
 211     if (!fd)
 212         fd = buildArrayOp(ident, e, sc);
 213
 214     if (fd && fd->errors)
 215     {
 216         const char *fmt;
 217         if (tbn->ty == Tstruct || tbn->ty == Tclass)
 218             fmt = "invalid array operation '%s' because %s doesn't support necessary arithmetic operations";
 219         else if (!tbn->isscalar())
 220             fmt = "invalid array operation '%s' because %s is not a scalar type";
 221         else
 222             fmt = "invalid array operation '%s' for element type %s";
 223
 224         e->error(fmt, e->toChars(), tbn->toChars());
 225         return new ErrorExp();
 226     }
 227
 228     *pFd = fd;
 229
 230     Expression *ev = new VarExp(e->loc, fd);
 231     Expression *ec = new CallExp(e->loc, ev, arguments);
 232
 233     return expressionSemantic(ec, sc);
 234 }
 235
 236 Expression *arrayOp(BinAssignExp *e, Scope *sc)
 237 {
 238     //printf("BinAssignExp::arrayOp() %s\n", toChars());
 239
 240     /* Check that the elements of e1 can be assigned to
 241      */
 242     Type *tn = e->e1->type->toBasetype()->nextOf();
 243
 244     if (tn && (!tn->isMutable() || !tn->isAssignable()))
 245     {
 246         e->error("slice %s is not mutable", e->e1->toChars());
 247         return new ErrorExp();
 248     }
 249     if (e->e1->op == TOKarrayliteral)
 250     {
 251         return e->e1->modifiableLvalue(sc, e->e1);
 252     }
 253
 254     return arrayOp((BinExp *)e, sc);
 255 }
 256
 257 /******************************************
 258  * Construct the identifier for the array operation function,
 259  * and build the argument list to pass to it.
 260  */
 261
 262 void buildArrayIdent(Expression *e, OutBuffer *buf, Expressions *arguments)
 263 {
 264     class BuildArrayIdentVisitor : public Visitor
 265     {
 266         OutBuffer *buf;
 267         Expressions *arguments;
 268     public:
 269         BuildArrayIdentVisitor(OutBuffer *buf, Expressions *arguments)
 270             : buf(buf), arguments(arguments)
 271         {
 272         }
 273
 274         void visit(Expression *e)
 275         {
 276             buf->writestring("Exp");
 277             arguments->shift(e);
 278         }
 279
 280         void visit(CastExp *e)
 281         {
 282             Type *tb = e->type->toBasetype();
 283             if (tb->ty == Tarray || tb->ty == Tsarray)
 284             {
 285                 e->e1->accept(this);
 286             }
 287             else
 288                 visit((Expression *)e);
 289         }
 290
 291         void visit(ArrayLiteralExp *e)
 292         {
 293             buf->writestring("Slice");
 294             arguments->shift(e);
 295         }
 296
 297         void visit(SliceExp *e)
 298         {
 299             buf->writestring("Slice");
 300             arguments->shift(e);
 301         }
 302
 303         void visit(AssignExp *e)
 304         {
 305             /* Evaluate assign expressions right to left
 306              */
 307             e->e2->accept(this);
 308             e->e1->accept(this);
 309             buf->writestring("Assign");
 310         }
 311
 312         void visit(BinAssignExp *e)
 313         {
 314             /* Evaluate assign expressions right to left
 315              */
 316             e->e2->accept(this);
 317             e->e1->accept(this);
 318             const char *s;
 319             switch(e->op)
 320             {
 321             case TOKaddass: s = "Addass"; break;
 322             case TOKminass: s = "Minass"; break;
 323             case TOKmulass: s = "Mulass"; break;
 324             case TOKdivass: s = "Divass"; break;
 325             case TOKmodass: s = "Modass"; break;
 326             case TOKxorass: s = "Xorass"; break;
 327             case TOKandass: s = "Andass"; break;
 328             case TOKorass:  s = "Orass";  break;
 329             case TOKpowass: s = "Powass"; break;
 330             default: assert(0);
 331             }
 332             buf->writestring(s);
 333         }
 334
 335         void visit(NegExp *e)
 336         {
 337             e->e1->accept(this);
 338             buf->writestring("Neg");
 339         }
 340
 341         void visit(ComExp *e)
 342         {
 343             e->e1->accept(this);
 344             buf->writestring("Com");
 345         }
 346
 347         void visit(BinExp *e)
 348         {
 349             /* Evaluate assign expressions left to right
 350              */
 351             const char *s = NULL;
 352             switch(e->op)
 353             {
 354             case TOKadd: s = "Add"; break;
 355             case TOKmin: s = "Min"; break;
 356             case TOKmul: s = "Mul"; break;
 357             case TOKdiv: s = "Div"; break;
 358             case TOKmod: s = "Mod"; break;
 359             case TOKxor: s = "Xor"; break;
 360             case TOKand: s = "And"; break;
 361             case TOKor:  s = "Or";  break;
 362             case TOKpow: s = "Pow"; break;
 363             default: break;
 364             }
 365             if (s)
 366             {
 367                 Type *tb = e->type->toBasetype();
 368                 Type *t1 = e->e1->type->toBasetype();
 369                 Type *t2 = e->e2->type->toBasetype();
 370                 e->e1->accept(this);
 371                 if (t1->ty == Tarray &&
 372                     ((t2->ty == Tarray && !t1->equivalent(tb)) ||
 373                      (t2->ty != Tarray && !t1->nextOf()->equivalent(e->e2->type))))
 374                 {
 375                     // Bugzilla 12780: if A is narrower than B
 376                     //  A[] op B[]
 377                     //  A[] op B
 378                     buf->writestring("Of");
 379                     buf->writestring(t1->nextOf()->mutableOf()->deco);
 380                 }
 381                 e->e2->accept(this);
 382                 if (t2->ty == Tarray &&
 383                     ((t1->ty == Tarray && !t2->equivalent(tb)) ||
 384                      (t1->ty != Tarray && !t2->nextOf()->equivalent(e->e1->type))))
 385                 {
 386                     // Bugzilla 12780: if B is narrower than A:
 387                     //  A[] op B[]
 388                     //  A op B[]
 389                     buf->writestring("Of");
 390                     buf->writestring(t2->nextOf()->mutableOf()->deco);
 391                 }
 392                 buf->writestring(s);
 393             }
 394             else
 395                 visit((Expression *)e);
 396         }
 397     };
 398
 399     BuildArrayIdentVisitor v(buf, arguments);
 400     e->accept(&v);
 401 }
 402
 403 /******************************************
 404  * Construct the inner loop for the array operation function,
 405  * and build the parameter list.
 406  */
 407
 408 Expression *buildArrayLoop(Expression *e, Parameters *fparams)
 409 {
 410     class BuildArrayLoopVisitor : public Visitor
 411     {
 412         Parameters *fparams;
 413         Expression *result;
 414
 415     public:
 416         BuildArrayLoopVisitor(Parameters *fparams)
 417             : fparams(fparams), result(NULL)
 418         {
 419         }
 420
 421         void visit(Expression *e)
 422         {
 423             Identifier *id = Identifier::generateId("c", fparams->length);
 424             Parameter *param = new Parameter(0, e->type, id, NULL, NULL);
 425             fparams->shift(param);
 426             result = new IdentifierExp(Loc(), id);
 427         }
 428
 429         void visit(CastExp *e)
 430         {
 431             Type *tb = e->type->toBasetype();
 432             if (tb->ty == Tarray || tb->ty == Tsarray)
 433             {
 434                 e->e1->accept(this);
 435             }
 436             else
 437                 visit((Expression *)e);
 438         }
 439
 440         void visit(ArrayLiteralExp *e)
 441         {
 442             Identifier *id = Identifier::generateId("p", fparams->length);
 443             Parameter *param = new Parameter(STCconst, e->type, id, NULL, NULL);
 444             fparams->shift(param);
 445             Expression *ie = new IdentifierExp(Loc(), id);
 446             Expression *index = new IdentifierExp(Loc(), Id::p);
 447             result = new ArrayExp(Loc(), ie, index);
 448         }
 449
 450         void visit(SliceExp *e)
 451         {
 452             Identifier *id = Identifier::generateId("p", fparams->length);
 453             Parameter *param = new Parameter(STCconst, e->type, id, NULL, NULL);
 454             fparams->shift(param);
 455             Expression *ie = new IdentifierExp(Loc(), id);
 456             Expression *index = new IdentifierExp(Loc(), Id::p);
 457             result = new ArrayExp(Loc(), ie, index);
 458         }
 459
 460         void visit(AssignExp *e)
 461         {
 462             /* Evaluate assign expressions right to left
 463              */
 464             Expression *ex2 = buildArrayLoop(e->e2);
 465             /* Need the cast because:
 466              *   b = c + p[i];
 467              * where b is a byte fails because (c + p[i]) is an int
 468              * which cannot be implicitly cast to byte.
 469              */
 470             ex2 = new CastExp(Loc(), ex2, e->e1->type->nextOf());
 471             Expression *ex1 = buildArrayLoop(e->e1);
 472             Parameter *param = (*fparams)[0];
 473             param->storageClass = 0;
 474             result = new AssignExp(Loc(), ex1, ex2);
 475         }
 476
 477         void visit(BinAssignExp *e)
 478         {
 479             /* Evaluate assign expressions right to left
 480              */
 481             Expression *ex2 = buildArrayLoop(e->e2);
 482             Expression *ex1 = buildArrayLoop(e->e1);
 483             Parameter *param = (*fparams)[0];
 484             param->storageClass = 0;
 485             switch(e->op)
 486             {
 487             case TOKaddass: result = new AddAssignExp(e->loc, ex1, ex2); return;
 488             case TOKminass: result = new MinAssignExp(e->loc, ex1, ex2); return;
 489             case TOKmulass: result = new MulAssignExp(e->loc, ex1, ex2); return;
 490             case TOKdivass: result = new DivAssignExp(e->loc, ex1, ex2); return;
 491             case TOKmodass: result = new ModAssignExp(e->loc, ex1, ex2); return;
 492             case TOKxorass: result = new XorAssignExp(e->loc, ex1, ex2); return;
 493             case TOKandass: result = new AndAssignExp(e->loc, ex1, ex2); return;
 494             case TOKorass:  result = new OrAssignExp(e->loc, ex1, ex2); return;
 495             case TOKpowass: result = new PowAssignExp(e->loc, ex1, ex2); return;
 496             default:
 497                 assert(0);
 498             }
 499         }
 500
 501         void visit(NegExp *e)
 502         {
 503             Expression *ex1 = buildArrayLoop(e->e1);
 504             result = new NegExp(Loc(), ex1);
 505         }
 506
 507         void visit(ComExp *e)
 508         {
 509             Expression *ex1 = buildArrayLoop(e->e1);
 510             result = new ComExp(Loc(), ex1);
 511         }
 512
 513         void visit(BinExp *e)
 514         {
 515             if (isBinArrayOp(e->op))
 516             {
 517                 /* Evaluate assign expressions left to right
 518                  */
 519                 BinExp *be = (BinExp *)e->copy();
 520                 be->e1 = buildArrayLoop(be->e1);
 521                 be->e2 = buildArrayLoop(be->e2);
 522                 be->type = NULL;
 523                 result = be;
 524                 return;
 525             }
 526             else
 527             {
 528                 visit((Expression *)e);
 529                 return;
 530             }
 531         }
 532
 533         Expression *buildArrayLoop(Expression *e)
 534         {
 535             e->accept(this);
 536             return result;
 537         }
 538     };
 539
 540     BuildArrayLoopVisitor v(fparams);
 541     return v.buildArrayLoop(e);
 542 }
 543
 544 /***********************************************
 545  * Test if expression is a unary array op.
 546  */
 547
 548 bool isUnaArrayOp(TOK op)
 549 {
 550     switch (op)
 551     {
 552     case TOKneg:
 553     case TOKtilde:
 554         return true;
 555     default:
 556         break;
 557     }
 558     return false;
 559 }
 560
 561 /***********************************************
 562  * Test if expression is a binary array op.
 563  */
 564
 565 bool isBinArrayOp(TOK op)
 566 {
 567     switch (op)
 568     {
 569     case TOKadd:
 570     case TOKmin:
 571     case TOKmul:
 572     case TOKdiv:
 573     case TOKmod:
 574     case TOKxor:
 575     case TOKand:
 576     case TOKor:
 577     case TOKpow:
 578         return true;
 579     default:
 580         break;
 581     }
 582     return false;
 583 }
 584
 585 /***********************************************
 586  * Test if expression is a binary assignment array op.
 587  */
 588
 589 bool isBinAssignArrayOp(TOK op)
 590 {
 591     switch (op)
 592     {
 593     case TOKaddass:
 594     case TOKminass:
 595     case TOKmulass:
 596     case TOKdivass:
 597     case TOKmodass:
 598     case TOKxorass:
 599     case TOKandass:
 600     case TOKorass:
 601     case TOKpowass:
 602         return true;
 603     default:
 604         break;
 605     }
 606     return false;
 607 }
 608
 609 /***********************************************
 610  * Test if operand is a valid array op operand.
 611  */
 612
 613 bool isArrayOpOperand(Expression *e)
 614 {
 615     //printf("Expression::isArrayOpOperand() %s\n", e->toChars());
 616     if (e->op == TOKslice)
 617         return true;
 618     if (e->op == TOKarrayliteral)
 619     {
 620         Type *t = e->type->toBasetype();
 621         while (t->ty == Tarray || t->ty == Tsarray)
 622             t = t->nextOf()->toBasetype();
 623         return (t->ty != Tvoid);
 624     }
 625     Type *tb = e->type->toBasetype();
 626     if (tb->ty == Tarray)
 627     {
 628         return (isUnaArrayOp(e->op) ||
 629                 isBinArrayOp(e->op) ||
 630                 isBinAssignArrayOp(e->op) ||
 631                 e->op == TOKassign);
 632     }
 633     return false;
 634 }