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