1 /** 2 * Flow analysis for Ownership/Borrowing 3 * 4 * Copyright: Copyright (C) 1999-2019 by The D Language Foundation, All Rights Reserved 5 * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) 6 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 7 * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/ob.d, _ob.d) 8 * Documentation: https://dlang.org/phobos/dmd_escape.html 9 * Coverage: https://codecov.io/gh/dlang/dmd/src/master/src/dmd/ob.d 10 */ 11 12 module dmd.ob; 13 14 import core.stdc.stdio : printf; 15 import core.stdc.stdlib; 16 import core.stdc.string; 17 18 import dmd.root.array; 19 import dmd.root.rootobject; 20 import dmd.root.rmem; 21 22 import dmd.aggregate; 23 import dmd.apply; 24 import dmd.arraytypes; 25 import dmd.declaration; 26 import dmd.dscope; 27 import dmd.dsymbol; 28 import dmd.dtemplate; 29 import dmd.errors; 30 import dmd.escape; 31 import dmd.expression; 32 import dmd.foreachvar; 33 import dmd.func; 34 import dmd.globals; 35 import dmd.identifier; 36 import dmd.init; 37 import dmd.mtype; 38 import dmd.printast; 39 import dmd.statement; 40 import dmd.stmtstate; 41 import dmd.tokens; 42 import dmd.visitor; 43 44 import dmd.root.bitarray; 45 import dmd.root.outbuffer; 46 47 /********************************** 48 * Perform ownership/borrowing checks for funcdecl. 49 * Does not modify the AST, just checks for errors. 50 */ 51 52 void oblive(FuncDeclaration funcdecl) 53 { 54 //printf("oblive() %s\n", funcdecl.toChars()); 55 //printf("fbody: %s\n", funcdecl.fbody.toChars()); 56 ObState obstate; 57 58 /* Build the flow graph 59 */ 60 setLabelStatementExtraFields(funcdecl.labtab); 61 toObNodes(obstate.nodes, funcdecl.fbody); 62 insertFinallyBlockCalls(obstate.nodes); 63 insertFinallyBlockGotos(obstate.nodes); 64 removeUnreachable(obstate.nodes); 65 computePreds(obstate.nodes); 66 67 numberNodes(obstate.nodes); 68 //foreach (ob; obstate.nodes) ob.print(); 69 70 collectVars(funcdecl, obstate.vars); 71 allocStates(obstate); 72 doDataFlowAnalysis(obstate); 73 74 checkObErrors(obstate); 75 } 76 77 alias ObNodes = Array!(ObNode*); 78 79 alias StmtState = dmd.stmtstate.StmtState!ObNode; 80 81 /******************************************* 82 * Collect the state information. 83 */ 84 struct ObState 85 { 86 ObNodes nodes; 87 VarDeclarations vars; 88 89 Array!size_t varStack; /// temporary storage 90 Array!bool mutableStack; /// parallel to varStack[], is type mutable? 91 92 PtrVarState[] varPool; /// memory pool 93 94 ~this() 95 { 96 mem.xfree(varPool.ptr); 97 } 98 } 99 100 /*********************************************** 101 * A node in the function's expression graph, and its edges to predecessors and successors. 102 */ 103 struct ObNode 104 { 105 Expression exp; /// expression for the node 106 ObNodes preds; /// predecessors 107 ObNodes succs; /// successors 108 ObNode* tryBlock; /// try-finally block we're inside 109 ObType obtype; 110 uint index; /// index of this in obnodes 111 112 PtrVarState[] gen; /// new states generated for this node 113 PtrVarState[] input; /// variable states on entry to exp 114 PtrVarState[] output; /// variable states on exit to exp 115 116 this(ObNode* tryBlock) 117 { 118 this.tryBlock = tryBlock; 119 } 120 121 void print() 122 { 123 printf("%d: %s %s\n", index, obtype.toString.ptr, exp ? exp.toChars() : "-"); 124 printf(" preds: "); 125 foreach (ob; preds) 126 printf(" %d", ob.index); 127 printf("\n succs: "); 128 foreach (ob; succs) 129 printf(" %d", ob.index); 130 printf("\n\n"); 131 } 132 } 133 134 135 enum ObType : ubyte 136 { 137 goto_, /// goto one of the succs[] 138 return_, /// returns from function 139 retexp, /// returns expression from function 140 throw_, /// exits with throw 141 exit, /// exits program 142 try_, 143 finally_, 144 fend, 145 } 146 147 string toString(ObType obtype) 148 { 149 return obtype == ObType.goto_ ? "goto " : 150 obtype == ObType.return_ ? "ret " : 151 obtype == ObType.retexp ? "retexp" : 152 obtype == ObType.throw_ ? "throw" : 153 obtype == ObType.exit ? "exit" : 154 obtype == ObType.try_ ? "try" : 155 obtype == ObType.finally_ ? "finally" : 156 obtype == ObType.fend ? "fend" : 157 "---"; 158 } 159 160 /*********** 161 Pointer variable states: 162 163 Initial state is not known; ignore for now 164 165 Undefined not in a usable state 166 167 T* p = void; 168 169 Owner mutable pointer 170 171 T* p = initializer; 172 173 Borrowed scope mutable pointer, borrowed from [p] 174 175 T* p = initializer; 176 scope T* b = p; 177 178 Readonly scope const pointer, copied from [p] 179 180 T* p = initializer; 181 scope const(T)* cp = p; 182 183 Examples: 184 185 T* p = initializer; // p is owner 186 T** pp = &p; // pp borrows from p 187 188 T* p = initialize; // p is owner 189 T* q = p; // transfer: q is owner, p is undefined 190 */ 191 192 enum PtrState : ubyte 193 { 194 Initial, Undefined, Owner, Borrowed, Readonly 195 } 196 197 /************ 198 */ 199 const(char)* toChars(PtrState state) 200 { 201 return toString(state).ptr; 202 } 203 204 string toString(PtrState state) 205 { 206 return ["Initial", "Undefined", "Owner", "Borrowed", "Readonly"][state]; 207 } 208 209 /****** 210 * Carries the state of a pointer variable. 211 */ 212 struct PtrVarState 213 { 214 BitArray deps; /// dependencies 215 PtrState state; /// state the pointer variable is in 216 217 void opAssign(const ref PtrVarState pvs) 218 { 219 state = pvs.state; 220 deps = pvs.deps; 221 } 222 223 /* Combine `this` and `pvs` into `this`, 224 * on the idea that the `this` and the `pvs` paths 225 * are being merged 226 * Params: 227 * pvs = path to be merged with `this` 228 */ 229 void combine(ref PtrVarState pvs, size_t vi, PtrVarState[] gen) 230 { 231 static uint X(PtrState x1, PtrState x2) { return x1 * (PtrState.max + 1) + x2; } 232 233 with (PtrState) 234 { 235 switch (X(state, pvs.state)) 236 { 237 case X(Initial, Initial): 238 break; 239 240 case X(Initial, Owner ): 241 case X(Initial, Borrowed ): 242 case X(Initial, Readonly ): 243 // Transfer state to `this` 244 state = pvs.state; 245 deps = pvs.deps; 246 break; 247 248 case X(Owner, Initial): 249 case X(Borrowed, Initial): 250 case X(Readonly, Initial): 251 break; 252 253 case X(Undefined, Initial): 254 case X(Undefined, Undefined): 255 case X(Undefined, Owner ): 256 case X(Undefined, Borrowed ): 257 case X(Undefined, Readonly ): 258 break; 259 260 case X(Owner , Owner ): 261 break; 262 263 case X(Borrowed , Borrowed): 264 case X(Readonly , Readonly): 265 deps.or(pvs.deps); 266 break; 267 268 default: 269 makeUndefined(vi, gen); 270 break; 271 } 272 } 273 } 274 275 bool opEquals(const ref PtrVarState pvs) const 276 { 277 return state == pvs.state && 278 deps == pvs.deps; 279 } 280 281 /*********************** 282 */ 283 void print(VarDeclaration[] vars) 284 { 285 string s = toString(state); 286 printf("%.*s [", cast(int)s.length, s.ptr); 287 assert(vars.length == deps.length); 288 OutBuffer buf; 289 depsToBuf(buf, vars); 290 string t = buf[]; 291 printf("%.*s]\n", cast(int)t.length, t.ptr); 292 } 293 294 /***************************** 295 * Produce a user-readable comma separated string of the 296 * dependencies. 297 * Params: 298 * buf = write resulting string here 299 * vars = array from which to get the variable names 300 */ 301 void depsToBuf(ref OutBuffer buf, const VarDeclaration[] vars) 302 { 303 bool any = false; 304 foreach (i; 0 .. deps.length) 305 { 306 if (deps[i]) 307 { 308 if (any) 309 buf.writestring(", "); 310 buf.writestring(vars[i].toString()); 311 any = true; 312 } 313 } 314 } 315 } 316 317 318 /***************************************** 319 * Set the `.extra` field for LabelStatements in labtab[]. 320 */ 321 void setLabelStatementExtraFields(DsymbolTable labtab) 322 { 323 if (labtab) 324 foreach (keyValue; labtab.tab.asRange) 325 { 326 //printf(" KV: %s = %s\n", keyValue.key.toChars(), keyValue.value.toChars()); 327 auto label = cast(LabelDsymbol)keyValue.value; 328 if (label.statement) 329 label.statement.extra = cast(void*) new ObNode(null); 330 } 331 } 332 333 /***************************************** 334 * Convert statement into ObNodes. 335 */ 336 337 void toObNodes(ref ObNodes obnodes, Statement s) 338 { 339 ObNode* curblock = new ObNode(null); 340 obnodes.push(curblock); 341 342 void visit(Statement s, StmtState* stmtstate) 343 { 344 if (!s) 345 return; 346 347 ObNode* newNode() 348 { 349 return new ObNode(stmtstate.tryBlock); 350 } 351 352 ObNode* nextNodeIs(ObNode* ob) 353 { 354 obnodes.push(ob); 355 curblock = ob; 356 return ob; 357 } 358 359 ObNode* nextNode() 360 { 361 return nextNodeIs(newNode()); 362 } 363 364 ObNode* gotoNextNodeIs(ObNode* ob) 365 { 366 obnodes.push(ob); 367 curblock.succs.push(ob); 368 curblock = ob; 369 return ob; 370 } 371 372 // block_goto(blx, BCgoto, null) 373 ObNode* gotoNextNode() 374 { 375 return gotoNextNodeIs(newNode()); 376 } 377 378 /*** 379 * Doing a goto to dest 380 */ 381 ObNode* gotoDest(ObNode* dest) 382 { 383 curblock.succs.push(dest); 384 return nextNode(); 385 } 386 387 void visitExp(ExpStatement s) 388 { 389 curblock.obtype = ObType.goto_; 390 curblock.exp = s.exp; 391 gotoNextNode(); 392 } 393 394 void visitDtorExp(DtorExpStatement s) 395 { 396 visitExp(s); 397 } 398 399 void visitCompound(CompoundStatement s) 400 { 401 if (s.statements) 402 { 403 foreach (s2; *s.statements) 404 { 405 visit(s2, stmtstate); 406 } 407 } 408 } 409 410 void visitCompoundDeclaration(CompoundDeclarationStatement s) 411 { 412 visitCompound(s); 413 } 414 415 void visitUnrolledLoop(UnrolledLoopStatement s) 416 { 417 StmtState mystate = StmtState(stmtstate, s); 418 mystate.breakBlock = newNode(); 419 420 gotoNextNode(); 421 422 foreach (s2; *s.statements) 423 { 424 if (s2) 425 { 426 mystate.contBlock = newNode(); 427 428 visit(s2, &mystate); 429 430 gotoNextNodeIs(mystate.contBlock); 431 } 432 } 433 434 gotoNextNodeIs(mystate.breakBlock); 435 } 436 437 void visitScope(ScopeStatement s) 438 { 439 if (s.statement) 440 { 441 StmtState mystate = StmtState(stmtstate, s); 442 443 if (mystate.prev.ident) 444 mystate.ident = mystate.prev.ident; 445 446 visit(s.statement, &mystate); 447 448 if (mystate.breakBlock) 449 gotoNextNodeIs(mystate.breakBlock); 450 } 451 } 452 453 void visitDo(DoStatement s) 454 { 455 StmtState mystate = StmtState(stmtstate, s); 456 mystate.breakBlock = newNode(); 457 mystate.contBlock = newNode(); 458 459 auto bpre = curblock; 460 461 auto ob = newNode(); 462 obnodes.push(ob); 463 curblock.succs.push(ob); 464 curblock = ob; 465 bpre.succs.push(curblock); 466 467 mystate.contBlock.succs.push(curblock); 468 mystate.contBlock.succs.push(mystate.breakBlock); 469 470 visit(s._body, &mystate); 471 472 gotoNextNodeIs(mystate.contBlock); 473 mystate.contBlock.exp = s.condition; 474 nextNodeIs(mystate.breakBlock); 475 } 476 477 void visitFor(ForStatement s) 478 { 479 //printf("visit(ForStatement)) %u..%u\n", s.loc.linnum, s.endloc.linnum); 480 StmtState mystate = StmtState(stmtstate, s); 481 mystate.breakBlock = newNode(); 482 mystate.contBlock = newNode(); 483 484 visit(s._init, &mystate); 485 486 auto bcond = gotoNextNode(); 487 mystate.contBlock.succs.push(bcond); 488 489 if (s.condition) 490 { 491 bcond.exp = s.condition; 492 auto ob = newNode(); 493 obnodes.push(ob); 494 bcond.succs.push(ob); 495 bcond.succs.push(mystate.breakBlock); 496 curblock = ob; 497 } 498 else 499 { /* No conditional, it's a straight goto 500 */ 501 bcond.exp = s.condition; 502 bcond.succs.push(nextNode()); 503 } 504 505 visit(s._body, &mystate); 506 /* End of the body goes to the continue block 507 */ 508 curblock.succs.push(mystate.contBlock); 509 nextNodeIs(mystate.contBlock); 510 511 if (s.increment) 512 curblock.exp = s.increment; 513 514 /* The 'break' block follows the for statement. 515 */ 516 nextNodeIs(mystate.breakBlock); 517 } 518 519 void visitIf(IfStatement s) 520 { 521 StmtState mystate = StmtState(stmtstate, s); 522 523 // bexit is the block that gets control after this IfStatement is done 524 auto bexit = mystate.breakBlock ? mystate.breakBlock : newNode(); 525 526 curblock.exp = s.condition; 527 528 auto bcond = curblock; 529 gotoNextNode(); 530 531 visit(s.ifbody, &mystate); 532 curblock.succs.push(bexit); 533 534 if (s.elsebody) 535 { 536 bcond.succs.push(nextNode()); 537 538 visit(s.elsebody, &mystate); 539 540 gotoNextNodeIs(bexit); 541 } 542 else 543 { 544 bcond.succs.push(bexit); 545 nextNodeIs(bexit); 546 } 547 } 548 549 void visitSwitch(SwitchStatement s) 550 { 551 StmtState mystate = StmtState(stmtstate, s); 552 553 mystate.switchBlock = curblock; 554 555 /* Block for where "break" goes to 556 */ 557 mystate.breakBlock = newNode(); 558 559 /* Block for where "default" goes to. 560 * If there is a default statement, then that is where default goes. 561 * If not, then do: 562 * default: break; 563 * by making the default block the same as the break block. 564 */ 565 mystate.defaultBlock = s.sdefault ? newNode() : mystate.breakBlock; 566 567 const numcases = s.cases ? s.cases.dim : 0; 568 569 /* allocate a block for each case 570 */ 571 if (numcases) 572 foreach (cs; *s.cases) 573 { 574 cs.extra = cast(void*)newNode(); 575 } 576 577 curblock.exp = s.condition; 578 579 if (s.hasVars) 580 { /* Generate a sequence of if-then-else blocks for the cases. 581 */ 582 if (numcases) 583 foreach (cs; *s.cases) 584 { 585 auto ecase = newNode(); 586 obnodes.push(ecase); 587 ecase.exp = cs.exp; 588 curblock.succs.push(ecase); 589 590 auto cn = cast(ObNode*)cs.extra; 591 ecase.succs.push(cn); 592 ecase.succs.push(nextNode()); 593 } 594 595 /* The final 'else' clause goes to the default 596 */ 597 curblock.succs.push(mystate.defaultBlock); 598 nextNode(); 599 600 visit(s._body, &mystate); 601 602 /* Have the end of the switch body fall through to the block 603 * following the switch statement. 604 */ 605 gotoNextNodeIs(mystate.breakBlock); 606 return; 607 } 608 609 auto ob = newNode(); 610 obnodes.push(ob); 611 curblock = ob; 612 613 mystate.switchBlock.succs.push(mystate.defaultBlock); 614 615 visit(s._body, &mystate); 616 617 /* Have the end of the switch body fall through to the block 618 * following the switch statement. 619 */ 620 gotoNextNodeIs(mystate.breakBlock); 621 } 622 623 void visitCase(CaseStatement s) 624 { 625 auto cb = cast(ObNode*)s.extra; 626 cb.tryBlock = stmtstate.tryBlock; 627 auto bsw = stmtstate.getSwitchBlock(); 628 bsw.succs.push(cb); 629 gotoNextNodeIs(cb); 630 631 visit(s.statement, stmtstate); 632 } 633 634 void visitDefault(DefaultStatement s) 635 { 636 auto bdefault = stmtstate.getDefaultBlock; 637 bdefault.tryBlock = stmtstate.tryBlock; 638 gotoNextNodeIs(bdefault); 639 visit(s.statement, stmtstate); 640 } 641 642 void visitGotoDefault(GotoDefaultStatement s) 643 { 644 gotoDest(stmtstate.getDefaultBlock); 645 } 646 647 void visitGotoCase(GotoCaseStatement s) 648 { 649 gotoDest(cast(ObNode*)s.cs.extra); 650 } 651 652 void visitSwitchError(SwitchErrorStatement s) 653 { 654 curblock.obtype = ObType.throw_; 655 curblock.exp = s.exp; 656 657 nextNode(); 658 } 659 660 void visitReturn(ReturnStatement s) 661 { 662 //printf("visitReturn() %s\n", s.toChars()); 663 curblock.obtype = s.exp && s.exp.type.toBasetype().ty != Tvoid 664 ? ObType.retexp 665 : ObType.return_; 666 curblock.exp = s.exp; 667 668 nextNode(); 669 } 670 671 void visitBreak(BreakStatement s) 672 { 673 gotoDest(stmtstate.getBreakBlock(s.ident)); 674 } 675 676 void visitContinue(ContinueStatement s) 677 { 678 gotoDest(stmtstate.getContBlock(s.ident)); 679 } 680 681 void visitWith(WithStatement s) 682 { 683 visit(s._body, stmtstate); 684 } 685 686 void visitTryCatch(TryCatchStatement s) 687 { 688 /* tryblock 689 * body 690 * breakBlock 691 * catches 692 * breakBlock2 693 */ 694 695 StmtState mystate = StmtState(stmtstate, s); 696 mystate.breakBlock = newNode(); 697 698 auto tryblock = gotoNextNode(); 699 700 visit(s._body, &mystate); 701 702 gotoNextNodeIs(mystate.breakBlock); 703 704 // create new break block that follows all the catches 705 auto breakBlock2 = newNode(); 706 707 gotoDest(breakBlock2); 708 709 foreach (cs; *s.catches) 710 { 711 /* Each catch block is a successor to tryblock 712 * and the last block of try body 713 */ 714 StmtState catchState = StmtState(stmtstate, s); 715 716 auto bcatch = curblock; 717 tryblock.succs.push(bcatch); 718 mystate.breakBlock.succs.push(bcatch); 719 720 nextNode(); 721 722 visit(cs.handler, &catchState); 723 724 gotoDest(breakBlock2); 725 } 726 727 curblock.succs.push(breakBlock2); 728 obnodes.push(breakBlock2); 729 curblock = breakBlock2; 730 } 731 732 void visitTryFinally(TryFinallyStatement s) 733 { 734 /* Build this: 735 * 1 goto [2] 736 * 2 try_ [3] [5] [7] 737 * 3 body 738 * 4 goto [8] 739 * 5 finally_ [6] 740 * 6 finalbody 741 * 7 fend [8] 742 * 8 lastblock 743 */ 744 745 StmtState bodyState = StmtState(stmtstate, s); 746 747 auto b2 = gotoNextNode(); 748 b2.obtype = ObType.try_; 749 bodyState.tryBlock = b2; 750 751 gotoNextNode(); 752 753 visit(s._body, &bodyState); 754 755 auto b4 = gotoNextNode(); 756 757 auto b5 = newNode(); 758 b5.obtype = ObType.finally_; 759 nextNodeIs(b5); 760 gotoNextNode(); 761 762 StmtState finallyState = StmtState(stmtstate, s); 763 visit(s.finalbody, &finallyState); 764 765 auto b7 = gotoNextNode(); 766 b7.obtype = ObType.fend; 767 768 auto b8 = gotoNextNode(); 769 770 b2.succs.push(b5); 771 b2.succs.push(b7); 772 773 b4.succs.push(b8); 774 } 775 776 void visitThrow(ThrowStatement s) 777 { 778 curblock.obtype = ObType.throw_; 779 curblock.exp = s.exp; 780 nextNode(); 781 } 782 783 void visitGoto(GotoStatement s) 784 { 785 gotoDest(cast(ObNode*)s.label.statement.extra); 786 } 787 788 void visitLabel(LabelStatement s) 789 { 790 StmtState mystate = StmtState(stmtstate, s); 791 mystate.ident = s.ident; 792 793 auto ob = cast(ObNode*)s.extra; 794 ob.tryBlock = mystate.tryBlock; 795 visit(s.statement, &mystate); 796 } 797 798 final switch (s.stmt) 799 { 800 case STMT.Exp: visitExp(s.isExpStatement()); break; 801 case STMT.DtorExp: visitDtorExp(s.isDtorExpStatement()); break; 802 case STMT.Compound: visitCompound(s.isCompoundStatement()); break; 803 case STMT.CompoundDeclaration: visitCompoundDeclaration(s.isCompoundDeclarationStatement()); break; 804 case STMT.UnrolledLoop: visitUnrolledLoop(s.isUnrolledLoopStatement()); break; 805 case STMT.Scope: visitScope(s.isScopeStatement()); break; 806 case STMT.Do: visitDo(s.isDoStatement()); break; 807 case STMT.For: visitFor(s.isForStatement()); break; 808 case STMT.If: visitIf(s.isIfStatement()); break; 809 case STMT.Switch: visitSwitch(s.isSwitchStatement()); break; 810 case STMT.Case: visitCase(s.isCaseStatement()); break; 811 case STMT.Default: visitDefault(s.isDefaultStatement()); break; 812 case STMT.GotoDefault: visitGotoDefault(s.isGotoDefaultStatement()); break; 813 case STMT.GotoCase: visitGotoCase(s.isGotoCaseStatement()); break; 814 case STMT.SwitchError: visitSwitchError(s.isSwitchErrorStatement()); break; 815 case STMT.Return: visitReturn(s.isReturnStatement()); break; 816 case STMT.Break: visitBreak(s.isBreakStatement()); break; 817 case STMT.Continue: visitContinue(s.isContinueStatement()); break; 818 case STMT.With: visitWith(s.isWithStatement()); break; 819 case STMT.TryCatch: visitTryCatch(s.isTryCatchStatement()); break; 820 case STMT.TryFinally: visitTryFinally(s.isTryFinallyStatement()); break; 821 case STMT.Throw: visitThrow(s.isThrowStatement()); break; 822 case STMT.Goto: visitGoto(s.isGotoStatement()); break; 823 case STMT.Label: visitLabel(s.isLabelStatement()); break; 824 825 case STMT.CompoundAsm: 826 case STMT.Asm: 827 case STMT.InlineAsm: 828 case STMT.GccAsm: 829 830 case STMT.Pragma: 831 case STMT.Import: 832 case STMT.ScopeGuard: 833 case STMT.Error: 834 break; // ignore these 835 836 case STMT.Foreach: 837 case STMT.ForeachRange: 838 case STMT.Debug: 839 case STMT.CaseRange: 840 case STMT.StaticForeach: 841 case STMT.StaticAssert: 842 case STMT.Conditional: 843 case STMT.While: 844 case STMT.Forwarding: 845 case STMT.Compile: 846 case STMT.Peel: 847 case STMT.Synchronized: 848 debug printf("s: %s\n", s.toChars()); 849 assert(0); // should have been rewritten 850 } 851 } 852 853 StmtState stmtstate; 854 visit(s, &stmtstate); 855 curblock.obtype = ObType.return_; 856 857 static if (0) 858 { 859 printf("toObNodes()\n"); 860 printf("------- before ----------\n"); 861 numberNodes(obnodes); 862 foreach (ob; obnodes) ob.print(); 863 printf("-------------------------\n"); 864 } 865 866 assert(stmtstate.breakBlock is null); 867 assert(stmtstate.contBlock is null); 868 assert(stmtstate.switchBlock is null); 869 assert(stmtstate.defaultBlock is null); 870 assert(stmtstate.tryBlock is null); 871 } 872 873 /*************************************************** 874 * Insert finally block calls when doing a goto from 875 * inside a try block to outside. 876 * Done after blocks are generated because then we know all 877 * the edges of the graph, but before the pred's are computed. 878 * Params: 879 * obnodes = graph of the function 880 */ 881 882 void insertFinallyBlockCalls(ref ObNodes obnodes) 883 { 884 ObNode* bcret = null; 885 ObNode* bcretexp = null; 886 887 enum log = false; 888 889 static if (log) 890 { 891 printf("insertFinallyBlockCalls()\n"); 892 printf("------- before ----------\n"); 893 numberNodes(obnodes); 894 foreach (ob; obnodes) ob.print(); 895 printf("-------------------------\n"); 896 } 897 898 foreach (ob; obnodes) 899 { 900 if (!ob.tryBlock) 901 continue; 902 903 switch (ob.obtype) 904 { 905 case ObType.return_: 906 // Rewrite into a ObType.goto_ => ObType.return_ 907 if (!bcret) 908 { 909 bcret = new ObNode(); 910 bcret.obtype = ob.obtype; 911 } 912 ob.obtype = ObType.goto_; 913 ob.succs.push(bcret); 914 goto case_goto; 915 916 case ObType.retexp: 917 // Rewrite into a ObType.goto_ => ObType.retexp 918 if (!bcretexp) 919 { 920 bcretexp = new ObNode(); 921 bcretexp.obtype = ob.obtype; 922 } 923 ob.obtype = ObType.goto_; 924 ob.succs.push(bcretexp); 925 goto case_goto; 926 927 case ObType.goto_: 928 if (ob.succs.length != 1) 929 break; 930 931 case_goto: 932 { 933 auto target = ob.succs[0]; // destination of goto 934 ob.succs.setDim(0); 935 auto lasttry = target.tryBlock; 936 auto blast = ob; 937 for (auto bt = ob.tryBlock; bt != lasttry; bt = bt.tryBlock) 938 { 939 assert(bt.obtype == ObType.try_); 940 auto bf = bt.succs[1]; 941 assert(bf.obtype == ObType.finally_); 942 auto bfend = bt.succs[2]; 943 assert(bfend.obtype == ObType.fend); 944 945 if (!blast.succs.contains(bf.succs[0])) 946 blast.succs.push(bf.succs[0]); 947 948 blast = bfend; 949 } 950 if (!blast.succs.contains(target)) 951 blast.succs.push(target); 952 953 break; 954 } 955 956 default: 957 break; 958 } 959 } 960 if (bcret) 961 obnodes.push(bcret); 962 if (bcretexp) 963 obnodes.push(bcretexp); 964 965 static if (log) 966 { 967 printf("------- after ----------\n"); 968 numberNodes(obnodes); 969 foreach (ob; obnodes) ob.print(); 970 printf("-------------------------\n"); 971 } 972 } 973 974 /*************************************************** 975 * Remove try-finally scaffolding. 976 * Params: 977 * obnodes = nodes for the function 978 */ 979 980 void insertFinallyBlockGotos(ref ObNodes obnodes) 981 { 982 /* Remove all the try_, finally_, lpad and ret nodes. 983 * Actually, just make them into no-ops. 984 */ 985 foreach (ob; obnodes) 986 { 987 ob.tryBlock = null; 988 switch (ob.obtype) 989 { 990 case ObType.try_: 991 ob.obtype = ObType.goto_; 992 ob.succs.remove(2); // remove fend 993 ob.succs.remove(1); // remove finally_ 994 break; 995 996 case ObType.finally_: 997 ob.obtype = ObType.goto_; 998 break; 999 1000 case ObType.fend: 1001 ob.obtype = ObType.goto_; 1002 break; 1003 1004 default: 1005 break; 1006 } 1007 } 1008 } 1009 1010 /********************************* 1011 * Set the `index` field of each ObNode 1012 * to its index in the `obnodes[]` array. 1013 */ 1014 void numberNodes(ref ObNodes obnodes) 1015 { 1016 //printf("numberNodes()\n"); 1017 foreach (i, ob; obnodes) 1018 { 1019 //printf("ob = %d, %p\n", i, ob); 1020 ob.index = cast(uint)i; 1021 } 1022 1023 // Verify that nodes do not appear more than once in obnodes[] 1024 debug 1025 foreach (i, ob; obnodes) 1026 { 1027 assert(ob.index == cast(uint)i); 1028 } 1029 } 1030 1031 1032 /********************************* 1033 * Remove unreachable nodes and compress 1034 * them out of obnodes[]. 1035 * Params: 1036 * obnodes = array of nodes 1037 */ 1038 void removeUnreachable(ref ObNodes obnodes) 1039 { 1040 if (!obnodes.length) 1041 return; 1042 1043 /* Mark all nodes as unreachable, 1044 * temporarilly reusing ObNode.index 1045 */ 1046 foreach (ob; obnodes) 1047 ob.index = 0; 1048 1049 /* Recursively mark ob and all its successors as reachable 1050 */ 1051 static void mark(ObNode* ob) 1052 { 1053 ob.index = 1; 1054 foreach (succ; ob.succs) 1055 { 1056 if (!succ.index) 1057 mark(succ); 1058 } 1059 } 1060 1061 mark(obnodes[0]); // first node is entry point 1062 1063 /* Remove unreachable nodes by shifting the remainder left 1064 */ 1065 size_t j = 1; 1066 foreach (i; 1 .. obnodes.length) 1067 { 1068 if (obnodes[i].index) 1069 { 1070 if (i != j) 1071 obnodes[j] = obnodes[i]; 1072 ++j; 1073 } 1074 else 1075 { 1076 obnodes[i].destroy(); 1077 } 1078 } 1079 obnodes.setDim(j); 1080 } 1081 1082 1083 1084 /************************************* 1085 * Compute predecessors. 1086 */ 1087 void computePreds(ref ObNodes obnodes) 1088 { 1089 foreach (ob; obnodes) 1090 { 1091 foreach (succ; ob.succs) 1092 { 1093 succ.preds.push(ob); 1094 } 1095 } 1096 } 1097 1098 /******************************* 1099 * Are we interested in tracking variable `v`? 1100 */ 1101 bool isTrackableVar(VarDeclaration v) 1102 { 1103 //printf("isTrackableVar() %s\n", v.toChars()); 1104 auto tb = v.type.toBasetype(); 1105 1106 /* Assume class references are managed by the GC, 1107 * don't need to track them 1108 */ 1109 if (tb.ty == Tclass) 1110 return false; 1111 1112 /* Assume types with a destructor are doing their own tracking, 1113 * such as being a ref counted type 1114 */ 1115 if (v.needsScopeDtor()) 1116 return false; 1117 1118 /* Not tracking function parameters that are not mutable 1119 */ 1120 if (v.storage_class & STC.parameter && !tb.hasPointersToMutableFields()) 1121 return false; 1122 1123 /* Not tracking global variables 1124 */ 1125 return !v.isDataseg(); 1126 } 1127 1128 /******************************* 1129 * Are we interested in tracking this expression? 1130 * Returns: 1131 * variable if so, null if not 1132 */ 1133 VarDeclaration isTrackableVarExp(Expression e) 1134 { 1135 if (auto ve = e.isVarExp()) 1136 { 1137 if (auto v = ve.var.isVarDeclaration()) 1138 if (isTrackableVar(v)) 1139 return v; 1140 } 1141 return null; 1142 } 1143 1144 1145 /************** 1146 * Find the pointer variable declarations in this function, 1147 * and fill `vars` with them. 1148 * Params: 1149 * funcdecl = function we are in 1150 * vars = array to fill in 1151 */ 1152 void collectVars(FuncDeclaration funcdecl, out VarDeclarations vars) 1153 { 1154 enum log = false; 1155 if (log) 1156 printf("----------------collectVars()---------------\n"); 1157 1158 if (funcdecl.parameters) 1159 foreach (v; (*funcdecl.parameters)[]) 1160 { 1161 if (isTrackableVar(v)) 1162 vars.push(v); 1163 } 1164 1165 void dgVar(VarDeclaration v) 1166 { 1167 if (isTrackableVar(v)) 1168 vars.push(v); 1169 } 1170 1171 void dgExp(Expression e) 1172 { 1173 foreachVar(e, &dgVar); 1174 } 1175 1176 foreachExpAndVar(funcdecl.fbody, &dgExp, &dgVar); 1177 1178 static if (log) 1179 { 1180 foreach (i, v; vars[]) 1181 { 1182 printf("vars[%d] = %s\n", cast(int)i, v.toChars()); 1183 } 1184 } 1185 } 1186 1187 /*********************************** 1188 * Allocate BitArrays in PtrVarState. 1189 * Can be allocated much more efficiently by subdividing a single 1190 * large array of bits 1191 */ 1192 void allocDeps(PtrVarState[] pvss) 1193 { 1194 //printf("allocDeps()\n"); 1195 foreach (ref pvs; pvss) 1196 { 1197 pvs.deps.length = pvss.length; 1198 } 1199 } 1200 1201 1202 /************************************** 1203 * Allocate state variables foreach node. 1204 */ 1205 void allocStates(ref ObState obstate) 1206 { 1207 //printf("---------------allocStates()------------------\n"); 1208 const vlen = obstate.vars.length; 1209 PtrVarState* p = cast(PtrVarState*) mem.xcalloc(obstate.nodes.length * 3 * vlen, PtrVarState.sizeof); 1210 obstate.varPool = p[0 .. obstate.nodes.length * 3 * vlen]; 1211 foreach (i, ob; obstate.nodes) 1212 { 1213 //printf(" [%d]\n", cast(int)i); 1214 // ob.kill.length = obstate.vars.length; 1215 // ob.comb.length = obstate.vars.length; 1216 ob.gen = p[0 .. vlen]; p += vlen; 1217 ob.input = p[0 .. vlen]; p += vlen; 1218 ob.output = p[0 .. vlen]; p += vlen; 1219 1220 allocDeps(ob.gen); 1221 allocDeps(ob.input); 1222 allocDeps(ob.output); 1223 } 1224 } 1225 1226 /****************************** 1227 * Does v meet the definiton of a `Borrowed` pointer? 1228 * Returns: 1229 * true if it does 1230 */ 1231 bool isBorrowedPtr(VarDeclaration v) 1232 { 1233 return v.isScope() && !v.isowner && v.type.nextOf().isMutable(); 1234 } 1235 1236 /****************************** 1237 * Does v meet the definiton of a `Readonly` pointer? 1238 * Returns: 1239 * true if it does 1240 */ 1241 bool isReadonlyPtr(VarDeclaration v) 1242 { 1243 return v.isScope() && !v.type.nextOf().isMutable(); 1244 } 1245 1246 /*************************************** 1247 * Compute the gen vector for ob. 1248 */ 1249 void genKill(ref ObState obstate, ObNode* ob) 1250 { 1251 enum log = false; 1252 if (log) 1253 printf("-----------computeGenKill()-----------\n"); 1254 1255 /*************** 1256 * Assigning result of expression `e` to variable `v`. 1257 */ 1258 void dgWriteVar(ObNode* ob, VarDeclaration v, Expression e, bool initializer) 1259 { 1260 if (log) 1261 printf("dgWriteVar() %s := %s %d\n", v.toChars(), e.toChars(), initializer); 1262 const vi = obstate.vars.find(v); 1263 assert(vi != size_t.max); 1264 PtrVarState* pvs = &ob.gen[vi]; 1265 readVar(ob, vi, true, ob.gen); 1266 if (e) 1267 { 1268 if (isBorrowedPtr(v)) 1269 pvs.state = PtrState.Borrowed; 1270 else if (isReadonlyPtr(v)) 1271 pvs.state = PtrState.Readonly; 1272 else 1273 pvs.state = PtrState.Owner; 1274 pvs.deps.zero(); 1275 1276 EscapeByResults er; 1277 escapeByValue(e, &er, true); 1278 bool any = false; // if any variables are assigned to v 1279 1280 void by(VarDeclaration r) 1281 { 1282 const ri = obstate.vars.find(r); 1283 if (ri != size_t.max && ri != vi) 1284 { 1285 pvs.deps[ri] = true; // v took from r 1286 auto pvsr = &ob.gen[ri]; 1287 any = true; 1288 1289 if (isBorrowedPtr(v)) 1290 { 1291 // v is borrowing from r 1292 pvs.state = PtrState.Borrowed; 1293 } 1294 else if (isReadonlyPtr(v)) 1295 { 1296 pvs.state = PtrState.Readonly; 1297 } 1298 else 1299 { 1300 // move r to v, which "consumes" r 1301 pvsr.state = PtrState.Undefined; 1302 pvsr.deps.zero(); 1303 } 1304 } 1305 } 1306 1307 foreach (VarDeclaration v2; er.byvalue) 1308 by(v2); 1309 foreach (VarDeclaration v2; er.byref) 1310 by(v2); 1311 1312 /* Make v an Owner for initializations like: 1313 * scope v = malloc(); 1314 */ 1315 if (initializer && !any && isBorrowedPtr(v)) 1316 { 1317 v.isowner = true; 1318 pvs.state = PtrState.Owner; 1319 } 1320 } 1321 else 1322 { 1323 if (isBorrowedPtr(v)) 1324 pvs.state = PtrState.Borrowed; 1325 else if (isReadonlyPtr(v)) 1326 pvs.state = PtrState.Readonly; 1327 else 1328 pvs.state = PtrState.Owner; 1329 pvs.deps.zero(); 1330 } 1331 } 1332 1333 void dgReadVar(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) 1334 { 1335 if (log) 1336 printf("dgReadVar() %s %d\n", v.toChars(), mutable); 1337 const vi = obstate.vars.find(v); 1338 assert(vi != size_t.max); 1339 readVar(ob, vi, mutable, ob.gen); 1340 } 1341 1342 void foreachExp(ObNode* ob, Expression e) 1343 { 1344 extern (C++) final class ExpWalker : Visitor 1345 { 1346 alias visit = typeof(super).visit; 1347 extern (D) void delegate(ObNode*, VarDeclaration, Expression, bool) dgWriteVar; 1348 extern (D) void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) dgReadVar; 1349 ObNode* ob; 1350 ObState* obstate; 1351 1352 extern (D) this(void delegate(ObNode*, VarDeclaration, Expression, bool) dgWriteVar, 1353 void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) dgReadVar, 1354 ObNode* ob, ref ObState obstate) 1355 { 1356 this.dgWriteVar = dgWriteVar; 1357 this.dgReadVar = dgReadVar; 1358 this.ob = ob; 1359 this.obstate = &obstate; 1360 } 1361 1362 override void visit(Expression e) 1363 { 1364 //printf("[%s] %s: %s\n", e.loc.toChars(), Token.toChars(e.op), e.toChars()); 1365 //assert(0); 1366 } 1367 1368 void visitAssign(AssignExp ae, bool initializer) 1369 { 1370 ae.e2.accept(this); 1371 if (auto ve = ae.e1.isVarExp()) 1372 { 1373 if (auto v = ve.var.isVarDeclaration()) 1374 if (isTrackableVar(v)) 1375 dgWriteVar(ob, v, ae.e2, initializer); 1376 } 1377 else 1378 ae.e1.accept(this); 1379 } 1380 1381 override void visit(AssignExp ae) 1382 { 1383 visitAssign(ae, false); 1384 } 1385 1386 override void visit(DeclarationExp e) 1387 { 1388 void Dsymbol_visit(Dsymbol s) 1389 { 1390 if (auto vd = s.isVarDeclaration()) 1391 { 1392 s = s.toAlias(); 1393 if (s != vd) 1394 return Dsymbol_visit(s); 1395 if (!isTrackableVar(vd)) 1396 return; 1397 1398 if (!(vd._init && vd._init.isVoidInitializer())) 1399 { 1400 auto ei = vd._init ? vd._init.isExpInitializer() : null; 1401 if (ei) 1402 visitAssign(cast(AssignExp)ei.exp, true); 1403 else 1404 dgWriteVar(ob, vd, null, false); 1405 } 1406 } 1407 else if (auto td = s.isTupleDeclaration()) 1408 { 1409 foreach (o; *td.objects) 1410 { 1411 if (auto eo = o.isExpression()) 1412 { 1413 if (auto se = eo.isDsymbolExp()) 1414 { 1415 Dsymbol_visit(se.s); 1416 } 1417 } 1418 } 1419 } 1420 } 1421 1422 Dsymbol_visit(e.declaration); 1423 } 1424 1425 override void visit(VarExp ve) 1426 { 1427 //printf("VarExp: %s\n", ve.toChars()); 1428 if (auto v = ve.var.isVarDeclaration()) 1429 if (isTrackableVar(v)) 1430 { 1431 dgReadVar(ve.loc, ob, v, isMutableRef(ve.type)); 1432 } 1433 } 1434 1435 override void visit(CallExp ce) 1436 { 1437 //printf("CallExp() %s\n", ce.toChars()); 1438 ce.e1.accept(this); 1439 auto t = ce.e1.type.toBasetype(); 1440 auto tf = t.isTypeFunction(); 1441 if (!tf) 1442 { 1443 assert(t.ty == Tdelegate); 1444 tf = t.nextOf().isTypeFunction(); 1445 assert(tf); 1446 } 1447 1448 // j=1 if _arguments[] is first argument 1449 const int j = tf.isDstyleVariadic(); 1450 bool hasOut; 1451 const varStackSave = obstate.varStack.length; 1452 1453 foreach (const i, arg; (*ce.arguments)[]) 1454 { 1455 if (i - j < tf.parameterList.length && 1456 i >= j) 1457 { 1458 Parameter p = tf.parameterList[i - j]; 1459 auto pt = p.type.toBasetype(); 1460 1461 EscapeByResults er; 1462 escapeByValue(arg, &er, true); 1463 1464 if (!(p.storageClass & STC.out_ && arg.isVarExp())) 1465 arg.accept(this); 1466 1467 void by(VarDeclaration v) 1468 { 1469 if (!isTrackableVar(v)) 1470 return; 1471 1472 const vi = obstate.vars.find(v); 1473 if (vi == size_t.max) 1474 return; 1475 1476 if (p.storageClass & STC.out_) 1477 { 1478 /// initialize 1479 hasOut = true; 1480 makeUndefined(vi, ob.gen); 1481 } 1482 else if (p.storageClass & STC.scope_) 1483 { 1484 // borrow 1485 obstate.varStack.push(vi); 1486 obstate.mutableStack.push(isMutableRef(pt)); 1487 } 1488 else 1489 { 1490 // move (i.e. consume arg) 1491 makeUndefined(vi, ob.gen); 1492 } 1493 } 1494 1495 foreach (VarDeclaration v2; er.byvalue) 1496 by(v2); 1497 foreach (VarDeclaration v2; er.byref) 1498 by(v2); 1499 } 1500 else // variadic args 1501 { 1502 arg.accept(this); 1503 1504 EscapeByResults er; 1505 escapeByValue(arg, &er, true); 1506 1507 void byv(VarDeclaration v) 1508 { 1509 if (!isTrackableVar(v)) 1510 return; 1511 1512 const vi = obstate.vars.find(v); 1513 if (vi == size_t.max) 1514 return; 1515 1516 obstate.varStack.push(vi); 1517 obstate.mutableStack.push(isMutableRef(arg.type)); 1518 1519 // move (i.e. consume arg) 1520 makeUndefined(vi, ob.gen); 1521 } 1522 1523 foreach (VarDeclaration v2; er.byvalue) 1524 byv(v2); 1525 foreach (VarDeclaration v2; er.byref) 1526 byv(v2); 1527 } 1528 } 1529 1530 /* Do a dummy 'read' of each variable passed to the function, 1531 * to detect O/B errors 1532 */ 1533 assert(obstate.varStack.length == obstate.mutableStack.length); 1534 foreach (i; varStackSave .. obstate.varStack.length) 1535 { 1536 const vi = obstate.varStack[i]; 1537 // auto pvs = &ob.gen[vi]; 1538 auto v = obstate.vars[vi]; 1539 //if (pvs.state == PtrState.Undefined) 1540 //v.error(ce.loc, "is Undefined, cannot pass to function"); 1541 1542 dgReadVar(ce.loc, ob, v, obstate.mutableStack[i]); 1543 } 1544 1545 /* Pop off stack all variables for this function call 1546 */ 1547 obstate.varStack.setDim(varStackSave); 1548 obstate.mutableStack.setDim(varStackSave); 1549 1550 if (hasOut) 1551 // Initialization of out's only happens after the function call 1552 foreach (const i, arg; (*ce.arguments)[]) 1553 { 1554 if (i - j < tf.parameterList.length && 1555 i >= j) 1556 { 1557 Parameter p = tf.parameterList[i - j]; 1558 if (p.storageClass & STC.out_) 1559 { 1560 if (auto v = isTrackableVarExp(arg)) 1561 dgWriteVar(ob, v, null, true); 1562 } 1563 } 1564 } 1565 } 1566 1567 override void visit(SymOffExp e) 1568 { 1569 if (auto v = e.var.isVarDeclaration()) 1570 if (isTrackableVar(v)) 1571 { 1572 dgReadVar(e.loc, ob, v, isMutableRef(e.type)); 1573 } 1574 } 1575 1576 override void visit(LogicalExp e) 1577 { 1578 e.e1.accept(this); 1579 1580 const vlen = obstate.vars.length; 1581 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 1582 PtrVarState[] gen1 = p[0 .. vlen]; 1583 foreach (i, ref pvs; gen1) 1584 { 1585 pvs = ob.gen[i]; 1586 } 1587 1588 e.e2.accept(this); 1589 1590 // Merge gen1 into ob.gen 1591 foreach (i; 0 .. vlen) 1592 { 1593 ob.gen[i].combine(gen1[i], i, ob.gen); 1594 } 1595 1596 mem.xfree(p); // should free .deps too 1597 } 1598 1599 override void visit(CondExp e) 1600 { 1601 e.econd.accept(this); 1602 1603 const vlen = obstate.vars.length; 1604 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 1605 PtrVarState[] gen1 = p[0 .. vlen]; 1606 foreach (i, ref pvs; gen1) 1607 { 1608 pvs = ob.gen[i]; 1609 } 1610 1611 e.e1.accept(this); 1612 1613 // Swap gen1 with ob.gen 1614 foreach (i; 0 .. vlen) 1615 { 1616 gen1[i].deps.swap(ob.gen[i].deps); 1617 const state = gen1[i].state; 1618 gen1[i].state = ob.gen[i].state; 1619 ob.gen[i].state = state; 1620 } 1621 1622 e.e2.accept(this); 1623 1624 /* xxx1 is the state from expression e1, ob.xxx is the state from e2. 1625 * Merge xxx1 into ob.xxx to get the state from `e`. 1626 */ 1627 foreach (i; 0 .. vlen) 1628 { 1629 ob.gen[i].combine(gen1[i], i, ob.gen); 1630 } 1631 1632 mem.xfree(p); // should free .deps too 1633 } 1634 1635 override void visit(AddrExp e) 1636 { 1637 /* Taking the address of struct literal is normally not 1638 * allowed, but CTFE can generate one out of a new expression, 1639 * but it'll be placed in static data so no need to check it. 1640 */ 1641 if (e.e1.op != TOK.structLiteral) 1642 e.e1.accept(this); 1643 } 1644 1645 override void visit(UnaExp e) 1646 { 1647 e.e1.accept(this); 1648 } 1649 1650 override void visit(BinExp e) 1651 { 1652 e.e1.accept(this); 1653 e.e2.accept(this); 1654 } 1655 1656 override void visit(ArrayLiteralExp e) 1657 { 1658 Type tb = e.type.toBasetype(); 1659 if (tb.ty == Tsarray || tb.ty == Tarray) 1660 { 1661 if (e.basis) 1662 e.basis.accept(this); 1663 foreach (el; *e.elements) 1664 { 1665 if (el) 1666 el.accept(this); 1667 } 1668 } 1669 } 1670 1671 override void visit(StructLiteralExp e) 1672 { 1673 if (e.elements) 1674 { 1675 foreach (ex; *e.elements) 1676 { 1677 if (ex) 1678 ex.accept(this); 1679 } 1680 } 1681 } 1682 1683 override void visit(AssocArrayLiteralExp e) 1684 { 1685 if (e.keys) 1686 { 1687 foreach (i, key; *e.keys) 1688 { 1689 if (key) 1690 key.accept(this); 1691 if (auto value = (*e.values)[i]) 1692 value.accept(this); 1693 } 1694 } 1695 } 1696 1697 override void visit(NewExp e) 1698 { 1699 if (e.arguments) 1700 { 1701 foreach (ex; *e.arguments) 1702 { 1703 if (ex) 1704 ex.accept(this); 1705 } 1706 } 1707 } 1708 1709 override void visit(SliceExp e) 1710 { 1711 e.e1.accept(this); 1712 if (e.lwr) 1713 e.lwr.accept(this); 1714 if (e.upr) 1715 e.upr.accept(this); 1716 } 1717 } 1718 1719 if (e) 1720 { 1721 scope ExpWalker ew = new ExpWalker(&dgWriteVar, &dgReadVar, ob, obstate); 1722 e.accept(ew); 1723 } 1724 } 1725 1726 foreachExp(ob, ob.exp); 1727 } 1728 1729 /*************************************** 1730 * Determine the state of a variable based on 1731 * its type and storage class. 1732 */ 1733 PtrState toPtrState(VarDeclaration v) 1734 { 1735 /* pointer to mutable: Owner 1736 * pointer to mutable, scope: Borrowed 1737 * pointer to const: Owner 1738 * pointer to const, scope: Readonly 1739 * ref: Borrowed 1740 * const ref: Readonly 1741 */ 1742 1743 auto t = v.type; 1744 if (v.isRef()) 1745 { 1746 return t.hasMutableFields() ? PtrState.Borrowed : PtrState.Readonly; 1747 } 1748 if (v.isScope()) 1749 { 1750 return t.hasPointersToMutableFields() ? PtrState.Borrowed : PtrState.Readonly; 1751 } 1752 else 1753 return PtrState.Owner; 1754 } 1755 1756 /********************************** 1757 * Does type `t` contain any pointers to mutable? 1758 */ 1759 bool hasPointersToMutableFields(Type t) 1760 { 1761 auto tb = t.toBasetype(); 1762 if (!tb.isMutable()) 1763 return false; 1764 if (auto tsa = tb.isTypeSArray()) 1765 { 1766 return tsa.nextOf().hasPointersToMutableFields(); 1767 } 1768 if (auto ts = tb.isTypeStruct()) 1769 { 1770 foreach (v; ts.sym.fields) 1771 { 1772 if (v.isRef()) 1773 { 1774 if (v.type.hasMutableFields()) 1775 return true; 1776 } 1777 else if (v.type.hasPointersToMutableFields()) 1778 return true; 1779 } 1780 return false; 1781 } 1782 auto tbn = tb.nextOf(); 1783 return tbn && tbn.hasMutableFields(); 1784 } 1785 1786 /******************************** 1787 * Does type `t` have any mutable fields? 1788 */ 1789 bool hasMutableFields(Type t) 1790 { 1791 auto tb = t.toBasetype(); 1792 if (!tb.isMutable()) 1793 return false; 1794 if (auto tsa = tb.isTypeSArray()) 1795 { 1796 return tsa.nextOf().hasMutableFields(); 1797 } 1798 if (auto ts = tb.isTypeStruct()) 1799 { 1800 foreach (v; ts.sym.fields) 1801 { 1802 if (v.type.hasMutableFields()) 1803 return true; 1804 } 1805 return false; 1806 } 1807 return true; 1808 } 1809 1810 1811 1812 /*************************************** 1813 * Do the data flow analysis (i.e. compute the input[] 1814 * and output[] vectors for each ObNode). 1815 */ 1816 void doDataFlowAnalysis(ref ObState obstate) 1817 { 1818 enum log = false; 1819 if (log) 1820 { 1821 printf("-----------------doDataFlowAnalysis()-------------------------\n"); 1822 foreach (ob; obstate.nodes) ob.print(); 1823 printf("------------------------------------------\n"); 1824 } 1825 1826 if (!obstate.nodes.length) 1827 return; 1828 1829 auto startnode = obstate.nodes[0]; 1830 assert(startnode.preds.length == 0); 1831 1832 /* Set opening state `input[]` for first node 1833 */ 1834 foreach (i, ref ps; startnode.input) 1835 { 1836 auto v = obstate.vars[i]; 1837 auto state = toPtrState(v); 1838 if (v.isParameter()) 1839 { 1840 if (v.isOut()) 1841 state = PtrState.Undefined; 1842 else 1843 state = PtrState.Owner; 1844 } 1845 else 1846 state = PtrState.Undefined; 1847 ps.state = state; 1848 ps.deps.zero(); 1849 startnode.gen[i] = ps; 1850 } 1851 1852 /* Set all output[]s to Initial 1853 */ 1854 foreach (ob; obstate.nodes[]) 1855 { 1856 foreach (ref ps; ob.output) 1857 { 1858 ps.state = PtrState.Initial; 1859 ps.deps.zero(); 1860 } 1861 } 1862 1863 const vlen = obstate.vars.length; 1864 PtrVarState pvs; 1865 pvs.deps.length = vlen; 1866 int counter = 0; 1867 bool changes; 1868 do 1869 { 1870 changes = false; 1871 assert(++counter <= 1000); // should converge, but don't hang if it doesn't 1872 foreach (ob; obstate.nodes[]) 1873 { 1874 /* Construct ob.gen[] by combining the .output[]s of each ob.preds[] 1875 * and set ob.input[] to the same state 1876 */ 1877 if (ob != startnode) 1878 { 1879 assert(ob.preds.length); 1880 1881 foreach (i; 0 .. vlen) 1882 { 1883 ob.gen[i] = ob.preds[0].output[i]; 1884 } 1885 1886 foreach (j; 1 .. ob.preds.length) 1887 { 1888 foreach (i; 0 .. vlen) 1889 { 1890 ob.gen[i].combine(ob.preds[j].output[i], i, ob.gen); 1891 } 1892 } 1893 1894 /* Set ob.input[] to ob.gen[], 1895 * if any changes were made we'll have to do another iteration 1896 */ 1897 foreach (i; 0 .. vlen) 1898 { 1899 if (ob.gen[i] != ob.input[i]) 1900 { 1901 ob.input[i] = ob.gen[i]; 1902 changes = true; 1903 } 1904 } 1905 } 1906 1907 /* Compute gen[] for node ob 1908 */ 1909 genKill(obstate, ob); 1910 1911 foreach (i; 0 .. vlen) 1912 { 1913 if (ob.gen[i] != ob.output[i]) 1914 { 1915 ob.output[i] = ob.gen[i]; 1916 changes = true; 1917 } 1918 } 1919 } 1920 } while (changes); 1921 1922 static if (log) 1923 { 1924 foreach (obi, ob; obstate.nodes) 1925 { 1926 printf("%d: %s\n", obi, ob.exp ? ob.exp.toChars() : "".ptr); 1927 printf(" input:\n"); 1928 foreach (i, ref pvs2; ob.input[]) 1929 { 1930 printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); 1931 } 1932 1933 printf(" gen:\n"); 1934 foreach (i, ref pvs2; ob.gen[]) 1935 { 1936 printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); 1937 } 1938 printf(" output:\n"); 1939 foreach (i, ref pvs2; ob.output[]) 1940 { 1941 printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); 1942 } 1943 } 1944 printf("\n"); 1945 } 1946 } 1947 1948 1949 /*************************************** 1950 * Check for Ownership/Borrowing errors. 1951 */ 1952 void checkObErrors(ref ObState obstate) 1953 { 1954 enum log = false; 1955 if (log) 1956 printf("------------checkObErrors()----------\n"); 1957 1958 void dgWriteVar(ObNode* ob, PtrVarState[] cpvs, VarDeclaration v, Expression e) 1959 { 1960 if (log) printf("dgWriteVar(v:%s, e:%s)\n", v.toChars(), e ? e.toChars() : "null"); 1961 const vi = obstate.vars.find(v); 1962 assert(vi != size_t.max); 1963 PtrVarState* pvs = &cpvs[vi]; 1964 readVar(ob, vi, true, cpvs); 1965 if (e) 1966 { 1967 if (isBorrowedPtr(v)) 1968 pvs.state = PtrState.Borrowed; 1969 else if (isReadonlyPtr(v)) 1970 pvs.state = PtrState.Readonly; 1971 else 1972 pvs.state = PtrState.Owner; 1973 pvs.deps.zero(); 1974 1975 EscapeByResults er; 1976 escapeByValue(e, &er, true); 1977 1978 void by(VarDeclaration r) // `v` = `r` 1979 { 1980 //printf(" by(%s)\n", r.toChars()); 1981 const ri = obstate.vars.find(r); 1982 if (ri == size_t.max) 1983 return; 1984 1985 with (PtrState) 1986 { 1987 pvs.deps[ri] = true; // v took from r 1988 auto pvsr = &cpvs[ri]; 1989 1990 if (pvsr.state == Undefined) 1991 { 1992 v.error(e.loc, "is reading from `%s` which is Undefined", r.toChars()); 1993 } 1994 else if (isBorrowedPtr(v)) // v is going to borrow from r 1995 { 1996 if (pvsr.state == Readonly) 1997 v.error(e.loc, "is borrowing from `%s` which is Readonly", r.toChars()); 1998 1999 pvs.state = Borrowed; 2000 } 2001 else if (isReadonlyPtr(v)) 2002 { 2003 pvs.state = Readonly; 2004 } 2005 else 2006 { 2007 // move from r to v 2008 pvsr.state = Undefined; 2009 pvsr.deps.zero(); 2010 } 2011 } 2012 } 2013 2014 foreach (VarDeclaration v2; er.byvalue) 2015 by(v2); 2016 foreach (VarDeclaration v2; er.byref) 2017 by(v2); 2018 } 2019 else 2020 { 2021 if (isBorrowedPtr(v)) 2022 pvs.state = PtrState.Borrowed; 2023 else if (isReadonlyPtr(v)) 2024 pvs.state = PtrState.Readonly; 2025 else 2026 pvs.state = PtrState.Owner; 2027 pvs.deps.zero(); 2028 } 2029 } 2030 2031 void dgReadVar(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[] gen) 2032 { 2033 if (log) printf("dgReadVar() %s\n", v.toChars()); 2034 const vi = obstate.vars.find(v); 2035 assert(vi != size_t.max); 2036 auto pvs = &gen[vi]; 2037 if (pvs.state == PtrState.Undefined) 2038 v.error(loc, "has undefined state and cannot be read"); 2039 2040 readVar(ob, vi, mutable, gen); 2041 } 2042 2043 void foreachExp(ObNode* ob, Expression e, PtrVarState[] cpvs) 2044 { 2045 extern (C++) final class ExpWalker : Visitor 2046 { 2047 alias visit = typeof(super).visit; 2048 extern (D) void delegate(ObNode*, PtrVarState[], VarDeclaration, Expression) dgWriteVar; 2049 extern (D) void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[]) dgReadVar; 2050 PtrVarState[] cpvs; 2051 ObNode* ob; 2052 ObState* obstate; 2053 2054 extern (D) this(void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[]) dgReadVar, 2055 void delegate(ObNode*, PtrVarState[], VarDeclaration, Expression) dgWriteVar, 2056 PtrVarState[] cpvs, ObNode* ob, ref ObState obstate) 2057 { 2058 this.dgReadVar = dgReadVar; 2059 this.dgWriteVar = dgWriteVar; 2060 this.cpvs = cpvs; 2061 this.ob = ob; 2062 this.obstate = &obstate; 2063 } 2064 2065 override void visit(Expression) 2066 { 2067 } 2068 2069 override void visit(DeclarationExp e) 2070 { 2071 void Dsymbol_visit(Dsymbol s) 2072 { 2073 if (auto vd = s.isVarDeclaration()) 2074 { 2075 s = s.toAlias(); 2076 if (s != vd) 2077 return Dsymbol_visit(s); 2078 if (!isTrackableVar(vd)) 2079 return; 2080 2081 if (vd._init && vd._init.isVoidInitializer()) 2082 return; 2083 2084 auto ei = vd._init ? vd._init.isExpInitializer() : null; 2085 if (ei) 2086 { 2087 auto e = ei.exp; 2088 if (auto ae = e.isConstructExp()) 2089 e = ae.e2; 2090 dgWriteVar(ob, cpvs, vd, e); 2091 } 2092 else 2093 dgWriteVar(ob, cpvs, vd, null); 2094 } 2095 else if (auto td = s.isTupleDeclaration()) 2096 { 2097 foreach (o; *td.objects) 2098 { 2099 if (auto eo = o.isExpression()) 2100 { 2101 if (auto se = eo.isDsymbolExp()) 2102 { 2103 Dsymbol_visit(se.s); 2104 } 2105 } 2106 } 2107 } 2108 } 2109 2110 Dsymbol_visit(e.declaration); 2111 } 2112 2113 override void visit(AssignExp ae) 2114 { 2115 ae.e2.accept(this); 2116 if (auto ve = ae.e1.isVarExp()) 2117 { 2118 if (auto v = ve.var.isVarDeclaration()) 2119 if (isTrackableVar(v)) 2120 dgWriteVar(ob, cpvs, v, ae.e2); 2121 } 2122 else 2123 ae.e1.accept(this); 2124 } 2125 2126 override void visit(VarExp ve) 2127 { 2128 //printf("VarExp: %s\n", ve.toChars()); 2129 if (auto v = ve.var.isVarDeclaration()) 2130 if (isTrackableVar(v)) 2131 { 2132 dgReadVar(ve.loc, ob, v, isMutableRef(ve.type), cpvs); 2133 } 2134 } 2135 2136 override void visit(CallExp ce) 2137 { 2138 //printf("CallExp(%s)\n", ce.toChars()); 2139 ce.e1.accept(this); 2140 auto t = ce.e1.type.toBasetype(); 2141 auto tf = t.isTypeFunction(); 2142 if (!tf) 2143 { 2144 assert(t.ty == Tdelegate); 2145 tf = t.nextOf().isTypeFunction(); 2146 assert(tf); 2147 } 2148 2149 // j=1 if _arguments[] is first argument 2150 const int j = tf.isDstyleVariadic(); 2151 bool hasOut; 2152 const varStackSave = obstate.varStack.length; 2153 2154 foreach (const i, arg; (*ce.arguments)[]) 2155 { 2156 if (i - j < tf.parameterList.length && 2157 i >= j) 2158 { 2159 Parameter p = tf.parameterList[i - j]; 2160 auto pt = p.type.toBasetype(); 2161 2162 if (!(p.storageClass & STC.out_ && arg.isVarExp())) 2163 arg.accept(this); 2164 2165 EscapeByResults er; 2166 escapeByValue(arg, &er, true); 2167 2168 void by(VarDeclaration v) 2169 { 2170 if (!isTrackableVar(v)) 2171 return; 2172 2173 const vi = obstate.vars.find(v); 2174 if (vi == size_t.max) 2175 return; 2176 2177 auto pvs = &cpvs[vi]; 2178 2179 if (p.storageClass & STC.out_) 2180 { 2181 /// initialize 2182 hasOut = true; 2183 makeUndefined(vi, cpvs); 2184 } 2185 else if (p.storageClass & STC.scope_) 2186 { 2187 // borrow 2188 obstate.varStack.push(vi); 2189 obstate.mutableStack.push(isMutableRef(pt)); 2190 } 2191 else 2192 { 2193 // move (i.e. consume arg) 2194 if (pvs.state != PtrState.Owner) 2195 v.error(arg.loc, "is not Owner, cannot consume its value"); 2196 makeUndefined(vi, cpvs); 2197 } 2198 } 2199 2200 foreach (VarDeclaration v2; er.byvalue) 2201 by(v2); 2202 foreach (VarDeclaration v2; er.byref) 2203 by(v2); 2204 } 2205 else // variadic args 2206 { 2207 arg.accept(this); 2208 2209 EscapeByResults er; 2210 escapeByValue(arg, &er, true); 2211 2212 void byv(VarDeclaration v) 2213 { 2214 if (!isTrackableVar(v)) 2215 return; 2216 2217 const vi = obstate.vars.find(v); 2218 if (vi == size_t.max) 2219 return; 2220 2221 auto pvs = &cpvs[vi]; 2222 obstate.varStack.push(vi); 2223 obstate.mutableStack.push(isMutableRef(arg.type)); 2224 2225 // move (i.e. consume arg) 2226 if (pvs.state != PtrState.Owner) 2227 v.error(arg.loc, "is not Owner, cannot consume its value"); 2228 makeUndefined(vi, cpvs); 2229 } 2230 2231 foreach (VarDeclaration v2; er.byvalue) 2232 byv(v2); 2233 foreach (VarDeclaration v2; er.byref) 2234 byv(v2); 2235 } 2236 } 2237 2238 /* Do a dummy 'read' of each variable passed to the function, 2239 * to detect O/B errors 2240 */ 2241 assert(obstate.varStack.length == obstate.mutableStack.length); 2242 foreach (i; varStackSave .. obstate.varStack.length) 2243 { 2244 const vi = obstate.varStack[i]; 2245 auto pvs = &cpvs[vi]; 2246 auto v = obstate.vars[vi]; 2247 //if (pvs.state == PtrState.Undefined) 2248 //v.error(ce.loc, "is Undefined, cannot pass to function"); 2249 2250 dgReadVar(ce.loc, ob, v, obstate.mutableStack[i], cpvs); 2251 2252 if (pvs.state == PtrState.Owner) 2253 { 2254 for (size_t k = i + 1; k < obstate.varStack.length;++k) 2255 { 2256 const vk = obstate.varStack[k]; 2257 if (vk == vi) 2258 { 2259 if (obstate.mutableStack[vi] || obstate.mutableStack[vk]) 2260 { 2261 v.error(ce.loc, "is passed as Owner more than once"); 2262 break; // no need to continue 2263 } 2264 } 2265 } 2266 } 2267 } 2268 2269 /* Pop off stack all variables for this function call 2270 */ 2271 obstate.varStack.setDim(varStackSave); 2272 obstate.mutableStack.setDim(varStackSave); 2273 2274 if (hasOut) 2275 // Initialization of out's only happens after the function call 2276 foreach (const i, arg; (*ce.arguments)[]) 2277 { 2278 if (i - j < tf.parameterList.length && 2279 i >= j) 2280 { 2281 Parameter p = tf.parameterList[i - j]; 2282 if (p.storageClass & STC.out_) 2283 { 2284 if (auto v = isTrackableVarExp(arg)) 2285 { 2286 dgWriteVar(ob, cpvs, v, null); 2287 } 2288 } 2289 } 2290 } 2291 } 2292 2293 override void visit(SymOffExp e) 2294 { 2295 if (auto v = e.var.isVarDeclaration()) 2296 if (isTrackableVar(v)) 2297 { 2298 dgReadVar(e.loc, ob, v, isMutableRef(e.type), cpvs); 2299 } 2300 } 2301 2302 override void visit(LogicalExp e) 2303 { 2304 e.e1.accept(this); 2305 2306 const vlen = obstate.vars.length; 2307 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 2308 PtrVarState[] out1 = p[0 .. vlen]; 2309 foreach (i, ref pvs; out1) 2310 { 2311 pvs = cpvs[i]; 2312 } 2313 2314 e.e2.accept(this); 2315 2316 // Merge out1 into cpvs 2317 foreach (i; 0 .. vlen) 2318 { 2319 cpvs[i].combine(out1[i], i, cpvs); 2320 } 2321 2322 mem.xfree(p); // should free .deps too 2323 } 2324 2325 override void visit(CondExp e) 2326 { 2327 e.econd.accept(this); 2328 2329 const vlen = obstate.vars.length; 2330 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 2331 PtrVarState[] out1 = p[0 .. vlen]; 2332 foreach (i, ref pvs; out1) 2333 { 2334 pvs = cpvs[i]; 2335 } 2336 2337 e.e1.accept(this); 2338 2339 // Swap out1 with cpvs 2340 foreach (i; 0 .. vlen) 2341 { 2342 out1[i].deps.swap(cpvs[i].deps); 2343 const state = out1[i].state; 2344 out1[i].state = cpvs[i].state; 2345 cpvs[i].state = state; 2346 } 2347 2348 e.e2.accept(this); 2349 2350 // Merge out1 into cpvs 2351 foreach (i; 0 .. vlen) 2352 { 2353 cpvs[i].combine(out1[i], i, cpvs); 2354 } 2355 2356 mem.xfree(p); // should free .deps too 2357 } 2358 2359 override void visit(AddrExp e) 2360 { 2361 /* Taking the address of struct literal is normally not 2362 * allowed, but CTFE can generate one out of a new expression, 2363 * but it'll be placed in static data so no need to check it. 2364 */ 2365 if (e.e1.op != TOK.structLiteral) 2366 e.e1.accept(this); 2367 } 2368 2369 override void visit(UnaExp e) 2370 { 2371 e.e1.accept(this); 2372 } 2373 2374 override void visit(BinExp e) 2375 { 2376 e.e1.accept(this); 2377 e.e2.accept(this); 2378 } 2379 2380 override void visit(ArrayLiteralExp e) 2381 { 2382 Type tb = e.type.toBasetype(); 2383 if (tb.ty == Tsarray || tb.ty == Tarray) 2384 { 2385 if (e.basis) 2386 e.basis.accept(this); 2387 foreach (el; *e.elements) 2388 { 2389 if (el) 2390 el.accept(this); 2391 } 2392 } 2393 } 2394 2395 override void visit(StructLiteralExp e) 2396 { 2397 if (e.elements) 2398 { 2399 foreach (ex; *e.elements) 2400 { 2401 if (ex) 2402 ex.accept(this); 2403 } 2404 } 2405 } 2406 2407 override void visit(AssocArrayLiteralExp e) 2408 { 2409 if (e.keys) 2410 { 2411 foreach (i, key; *e.keys) 2412 { 2413 if (key) 2414 key.accept(this); 2415 if (auto value = (*e.values)[i]) 2416 value.accept(this); 2417 } 2418 } 2419 } 2420 2421 override void visit(NewExp e) 2422 { 2423 if (e.arguments) 2424 { 2425 foreach (ex; *e.arguments) 2426 { 2427 if (ex) 2428 ex.accept(this); 2429 } 2430 } 2431 } 2432 2433 override void visit(SliceExp e) 2434 { 2435 e.e1.accept(this); 2436 if (e.lwr) 2437 e.lwr.accept(this); 2438 if (e.upr) 2439 e.upr.accept(this); 2440 } 2441 } 2442 2443 if (e) 2444 { 2445 scope ExpWalker ew = new ExpWalker(&dgReadVar, &dgWriteVar, cpvs, ob, obstate); 2446 e.accept(ew); 2447 } 2448 } 2449 2450 const vlen = obstate.vars.length; 2451 auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); 2452 PtrVarState[] cpvs = p[0 .. vlen]; 2453 foreach (ref pvs; cpvs) 2454 pvs.deps.length = vlen; 2455 2456 foreach (obi, ob; obstate.nodes) 2457 { 2458 static if (log) 2459 { 2460 printf("%d: %s\n", obi, ob.exp ? ob.exp.toChars() : "".ptr); 2461 printf(" input:\n"); 2462 foreach (i, ref pvs; ob.input[]) 2463 { 2464 printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); 2465 } 2466 } 2467 2468 /* Combine the .output[]s of each ob.preds[] looking for errors 2469 */ 2470 if (obi) // skip startnode 2471 { 2472 assert(ob.preds.length); 2473 2474 foreach (i; 0 .. vlen) 2475 { 2476 ob.gen[i] = ob.preds[0].output[i]; 2477 } 2478 2479 foreach (j; 1 .. ob.preds.length) 2480 { 2481 foreach (i; 0 .. vlen) 2482 { 2483 auto pvs1 = &ob.gen[i]; 2484 auto pvs2 = &ob.preds[j].output[i]; 2485 const s1 = pvs1.state; 2486 const s2 = pvs2.state; 2487 if (s1 != s2 && (s1 == PtrState.Owner || s2 == PtrState.Owner)) 2488 { 2489 auto v = obstate.vars[i]; 2490 v.error(ob.exp ? ob.exp.loc : v.loc, "is both %s and %s", s1.toChars(), s2.toChars()); 2491 } 2492 pvs1.combine(*pvs2, i, ob.gen); 2493 } 2494 } 2495 } 2496 2497 /* Prolly should use gen[] instead of cpvs[], or vice versa 2498 */ 2499 foreach (i, ref pvs; ob.input) 2500 { 2501 cpvs[i] = pvs; 2502 } 2503 2504 foreachExp(ob, ob.exp, cpvs); 2505 2506 static if (log) 2507 { 2508 printf(" cpvs:\n"); 2509 foreach (i, ref pvs; cpvs[]) 2510 { 2511 printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); 2512 } 2513 printf(" output:\n"); 2514 foreach (i, ref pvs; ob.output[]) 2515 { 2516 printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); 2517 } 2518 } 2519 2520 if (ob.obtype == ObType.retexp) 2521 { 2522 EscapeByResults er; 2523 escapeByValue(ob.exp, &er, true); 2524 2525 void by(VarDeclaration r) // `r` is the rvalue 2526 { 2527 const ri = obstate.vars.find(r); 2528 if (ri == size_t.max) 2529 return; 2530 with (PtrState) 2531 { 2532 auto pvsr = &ob.output[ri]; 2533 switch (pvsr.state) 2534 { 2535 case Undefined: 2536 r.error(ob.exp.loc, "is returned but is Undefined"); 2537 break; 2538 2539 case Owner: 2540 pvsr.state = Undefined; // returning a pointer "consumes" it 2541 break; 2542 2543 case Borrowed: 2544 case Readonly: 2545 break; 2546 2547 default: 2548 assert(0); 2549 } 2550 } 2551 } 2552 2553 foreach (VarDeclaration v2; er.byvalue) 2554 by(v2); 2555 foreach (VarDeclaration v2; er.byref) 2556 by(v2); 2557 } 2558 2559 if (ob.obtype == ObType.return_ || ob.obtype == ObType.retexp) 2560 { 2561 foreach (i, ref pvs; ob.output[]) 2562 { 2563 //printf("%s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); 2564 if (pvs.state == PtrState.Owner) 2565 { 2566 auto v = obstate.vars[i]; 2567 if (v.type.hasPointers()) 2568 v.error(v.loc, "is left dangling at return"); 2569 } 2570 } 2571 } 2572 } 2573 } 2574 2575 2576 /*************************************************** 2577 * Read from variable vi. 2578 * The beginning of the 'scope' of a variable is when it is first read. 2579 * Hence, when a read is done, instead of when assignment to the variable is done, the O/B rules are enforced. 2580 * (Also called "non-lexical scoping".) 2581 */ 2582 void readVar(ObNode* ob, const size_t vi, bool mutable, PtrVarState[] gen) 2583 { 2584 //printf("readVar(v%d)\n", cast(int)vi); 2585 auto pvso = &gen[vi]; 2586 switch (pvso.state) 2587 { 2588 case PtrState.Owner: 2589 //printf("t: %s\n", t.toChars()); 2590 if (mutable) // if mutable read 2591 { 2592 makeChildrenUndefined(vi, gen); 2593 } 2594 else // const read 2595 { 2596 // If there's a Borrow child, set that to Undefined 2597 foreach (di; 0 .. gen.length) 2598 { 2599 auto pvsd = &gen[di]; 2600 if (pvsd.deps[vi] && pvsd.state == PtrState.Borrowed) // if di borrowed vi 2601 { 2602 makeUndefined(di, gen); 2603 } 2604 } 2605 } 2606 break; 2607 2608 case PtrState.Borrowed: 2609 /* All children become Undefined 2610 */ 2611 makeChildrenUndefined(vi, gen); 2612 break; 2613 2614 case PtrState.Readonly: 2615 break; 2616 2617 case PtrState.Undefined: 2618 break; 2619 2620 default: 2621 break; 2622 } 2623 } 2624 2625 /******************** 2626 * Recursively make Undefined all who list vi as a dependency 2627 */ 2628 void makeChildrenUndefined(size_t vi, PtrVarState[] gen) 2629 { 2630 //printf("makeChildrenUndefined(%d)\n", vi); 2631 foreach (di; 0 .. gen.length) 2632 { 2633 if (gen[di].deps[vi]) // if di depends on vi 2634 { 2635 if (gen[di].state != PtrState.Undefined) 2636 { 2637 gen[di].state = PtrState.Undefined; // set this first to avoid infinite recursion 2638 makeChildrenUndefined(di, gen); 2639 gen[di].deps.zero(); 2640 } 2641 } 2642 } 2643 } 2644 2645 2646 /******************** 2647 * Recursively make Undefined vi undefined and all who list vi as a dependency 2648 */ 2649 void makeUndefined(size_t vi, PtrVarState[] gen) 2650 { 2651 auto pvs = &gen[vi]; 2652 pvs.state = PtrState.Undefined; // set this first to avoid infinite recursion 2653 makeChildrenUndefined(vi, gen); 2654 pvs.deps.zero(); 2655 } 2656 2657 /************************* 2658 * Is type `t` a reference to a const or a reference to a mutable? 2659 */ 2660 bool isMutableRef(Type t) 2661 { 2662 auto tb = t.toBasetype(); 2663 return (tb.nextOf() ? tb.nextOf() : tb).isMutable(); 2664 }