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