gcc/d/dmd/arrayop.c

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