/** * Flow analysis for Ownership/Borrowing * * Copyright: Copyright (C) 1999-2022 by The D Language Foundation, All Rights Reserved * Authors: $(LINK2 https://www.digitalmars.com, Walter Bright) * License: $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) * Source: $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/ob.d, _ob.d) * Documentation: https://dlang.org/phobos/dmd_escape.html * Coverage: https://codecov.io/gh/dlang/dmd/src/master/src/dmd/ob.d */ module dmd.ob; import core.stdc.stdio : printf; import core.stdc.stdlib; import core.stdc.string; import dmd.root.array; import dmd.root.rootobject; import dmd.root.rmem; import dmd.aggregate; import dmd.apply; import dmd.arraytypes; import dmd.astenums; import dmd.declaration; import dmd.dscope; import dmd.dsymbol; import dmd.dtemplate; import dmd.errors; import dmd.escape; import dmd.expression; import dmd.foreachvar; import dmd.func; import dmd.globals; import dmd.identifier; import dmd.init; import dmd.mtype; import dmd.printast; import dmd.statement; import dmd.stmtstate; import dmd.tokens; import dmd.visitor; import dmd.root.bitarray; import dmd.common.outbuffer; /********************************** * Perform ownership/borrowing checks for funcdecl. * Does not modify the AST, just checks for errors. */ void oblive(FuncDeclaration funcdecl) { //printf("oblive() %s\n", funcdecl.toChars()); //printf("fbody: %s\n", funcdecl.fbody.toChars()); ObState obstate; /* Build the flow graph */ setLabelStatementExtraFields(funcdecl.labtab); toObNodes(obstate.nodes, funcdecl.fbody); insertFinallyBlockCalls(obstate.nodes); insertFinallyBlockGotos(obstate.nodes); removeUnreachable(obstate.nodes); computePreds(obstate.nodes); numberNodes(obstate.nodes); //foreach (ob; obstate.nodes) ob.print(); collectVars(funcdecl, obstate.vars); allocStates(obstate); doDataFlowAnalysis(obstate); checkObErrors(obstate); } alias ObNodes = Array!(ObNode*); alias StmtState = dmd.stmtstate.StmtState!ObNode; /******************************************* * Collect the state information. */ struct ObState { ObNodes nodes; VarDeclarations vars; Array!size_t varStack; /// temporary storage Array!bool mutableStack; /// parallel to varStack[], is type mutable? PtrVarState[] varPool; /// memory pool ~this() { mem.xfree(varPool.ptr); } } /*********************************************** * A node in the function's expression graph, and its edges to predecessors and successors. */ struct ObNode { Expression exp; /// expression for the node ObNodes preds; /// predecessors ObNodes succs; /// successors ObNode* tryBlock; /// try-finally block we're inside ObType obtype; uint index; /// index of this in obnodes PtrVarState[] gen; /// new states generated for this node PtrVarState[] input; /// variable states on entry to exp PtrVarState[] output; /// variable states on exit to exp this(ObNode* tryBlock) { this.tryBlock = tryBlock; } void print() { printf("%d: %s %s\n", index, obtype.toString.ptr, exp ? exp.toChars() : "-"); printf(" preds: "); foreach (ob; preds) printf(" %d", ob.index); printf("\n succs: "); foreach (ob; succs) printf(" %d", ob.index); printf("\n\n"); } } enum ObType : ubyte { goto_, /// goto one of the succs[] return_, /// returns from function retexp, /// returns expression from function throw_, /// exits with throw exit, /// exits program try_, finally_, fend, } string toString(ObType obtype) { return obtype == ObType.goto_ ? "goto " : obtype == ObType.return_ ? "ret " : obtype == ObType.retexp ? "retexp" : obtype == ObType.throw_ ? "throw" : obtype == ObType.exit ? "exit" : obtype == ObType.try_ ? "try" : obtype == ObType.finally_ ? "finally" : obtype == ObType.fend ? "fend" : "---"; } /*********** Pointer variable states: Initial state is not known; ignore for now Undefined not in a usable state T* p = void; Owner mutable pointer T* p = initializer; Borrowed scope mutable pointer, borrowed from [p] T* p = initializer; scope T* b = p; Readonly scope const pointer, copied from [p] T* p = initializer; scope const(T)* cp = p; Examples: T* p = initializer; // p is owner T** pp = &p; // pp borrows from p T* p = initialize; // p is owner T* q = p; // transfer: q is owner, p is undefined */ enum PtrState : ubyte { Initial, Undefined, Owner, Borrowed, Readonly } /************ */ const(char)* toChars(PtrState state) { return toString(state).ptr; } string toString(PtrState state) { return ["Initial", "Undefined", "Owner", "Borrowed", "Readonly"][state]; } /****** * Carries the state of a pointer variable. */ struct PtrVarState { BitArray deps; /// dependencies PtrState state; /// state the pointer variable is in void opAssign(const ref PtrVarState pvs) { state = pvs.state; deps = pvs.deps; } /* Combine `this` and `pvs` into `this`, * on the idea that the `this` and the `pvs` paths * are being merged * Params: * pvs = path to be merged with `this` */ void combine(ref PtrVarState pvs, size_t vi, PtrVarState[] gen) { static uint X(PtrState x1, PtrState x2) { return x1 * (PtrState.max + 1) + x2; } with (PtrState) { switch (X(state, pvs.state)) { case X(Initial, Initial): break; case X(Initial, Owner ): case X(Initial, Borrowed ): case X(Initial, Readonly ): // Transfer state to `this` state = pvs.state; deps = pvs.deps; break; case X(Owner, Initial): case X(Borrowed, Initial): case X(Readonly, Initial): break; case X(Undefined, Initial): case X(Undefined, Undefined): case X(Undefined, Owner ): case X(Undefined, Borrowed ): case X(Undefined, Readonly ): break; case X(Owner , Owner ): break; case X(Borrowed , Borrowed): case X(Readonly , Readonly): deps.or(pvs.deps); break; default: makeUndefined(vi, gen); break; } } } bool opEquals(const ref PtrVarState pvs) const { return state == pvs.state && deps == pvs.deps; } /*********************** */ void print(VarDeclaration[] vars) { string s = toString(state); printf("%.*s [", cast(int)s.length, s.ptr); assert(vars.length == deps.length); OutBuffer buf; depsToBuf(buf, vars); auto t = buf[]; printf("%.*s]\n", cast(int)t.length, t.ptr); } /***************************** * Produce a user-readable comma separated string of the * dependencies. * Params: * buf = write resulting string here * vars = array from which to get the variable names */ void depsToBuf(ref OutBuffer buf, const VarDeclaration[] vars) { bool any = false; foreach (i; 0 .. deps.length) { if (deps[i]) { if (any) buf.writestring(", "); buf.writestring(vars[i].toString()); any = true; } } } } /***************************************** * Set the `.extra` field for LabelStatements in labtab[]. */ void setLabelStatementExtraFields(DsymbolTable labtab) { if (labtab) foreach (keyValue; labtab.tab.asRange) { //printf(" KV: %s = %s\n", keyValue.key.toChars(), keyValue.value.toChars()); auto label = cast(LabelDsymbol)keyValue.value; if (label.statement) label.statement.extra = cast(void*) new ObNode(null); } } /***************************************** * Convert statement into ObNodes. */ void toObNodes(ref ObNodes obnodes, Statement s) { ObNode* curblock = new ObNode(null); obnodes.push(curblock); void visit(Statement s, StmtState* stmtstate) { if (!s) return; ObNode* newNode() { return new ObNode(stmtstate.tryBlock); } ObNode* nextNodeIs(ObNode* ob) { obnodes.push(ob); curblock = ob; return ob; } ObNode* nextNode() { return nextNodeIs(newNode()); } ObNode* gotoNextNodeIs(ObNode* ob) { obnodes.push(ob); curblock.succs.push(ob); curblock = ob; return ob; } // block_goto(blx, BCgoto, null) ObNode* gotoNextNode() { return gotoNextNodeIs(newNode()); } /*** * Doing a goto to dest */ ObNode* gotoDest(ObNode* dest) { curblock.succs.push(dest); return nextNode(); } void visitExp(ExpStatement s) { curblock.obtype = ObType.goto_; curblock.exp = s.exp; gotoNextNode(); } void visitDtorExp(DtorExpStatement s) { visitExp(s); } void visitCompound(CompoundStatement s) { if (s.statements) { foreach (s2; *s.statements) { visit(s2, stmtstate); } } } void visitCompoundDeclaration(CompoundDeclarationStatement s) { visitCompound(s); } void visitUnrolledLoop(UnrolledLoopStatement s) { StmtState mystate = StmtState(stmtstate, s); mystate.breakBlock = newNode(); gotoNextNode(); foreach (s2; *s.statements) { if (s2) { mystate.contBlock = newNode(); visit(s2, &mystate); gotoNextNodeIs(mystate.contBlock); } } gotoNextNodeIs(mystate.breakBlock); } void visitScope(ScopeStatement s) { if (s.statement) { StmtState mystate = StmtState(stmtstate, s); if (mystate.prev.ident) mystate.ident = mystate.prev.ident; visit(s.statement, &mystate); if (mystate.breakBlock) gotoNextNodeIs(mystate.breakBlock); } } void visitDo(DoStatement s) { StmtState mystate = StmtState(stmtstate, s); mystate.breakBlock = newNode(); mystate.contBlock = newNode(); auto bpre = curblock; auto ob = newNode(); obnodes.push(ob); curblock.succs.push(ob); curblock = ob; bpre.succs.push(curblock); mystate.contBlock.succs.push(curblock); mystate.contBlock.succs.push(mystate.breakBlock); visit(s._body, &mystate); gotoNextNodeIs(mystate.contBlock); mystate.contBlock.exp = s.condition; nextNodeIs(mystate.breakBlock); } void visitFor(ForStatement s) { //printf("visit(ForStatement)) %u..%u\n", s.loc.linnum, s.endloc.linnum); StmtState mystate = StmtState(stmtstate, s); mystate.breakBlock = newNode(); mystate.contBlock = newNode(); visit(s._init, &mystate); auto bcond = gotoNextNode(); mystate.contBlock.succs.push(bcond); if (s.condition) { bcond.exp = s.condition; auto ob = newNode(); obnodes.push(ob); bcond.succs.push(ob); bcond.succs.push(mystate.breakBlock); curblock = ob; } else { /* No conditional, it's a straight goto */ bcond.exp = s.condition; bcond.succs.push(nextNode()); } visit(s._body, &mystate); /* End of the body goes to the continue block */ curblock.succs.push(mystate.contBlock); nextNodeIs(mystate.contBlock); if (s.increment) curblock.exp = s.increment; /* The 'break' block follows the for statement. */ nextNodeIs(mystate.breakBlock); } void visitIf(IfStatement s) { StmtState mystate = StmtState(stmtstate, s); // bexit is the block that gets control after this IfStatement is done auto bexit = mystate.breakBlock ? mystate.breakBlock : newNode(); curblock.exp = s.condition; auto bcond = curblock; gotoNextNode(); visit(s.ifbody, &mystate); curblock.succs.push(bexit); if (s.elsebody) { bcond.succs.push(nextNode()); visit(s.elsebody, &mystate); gotoNextNodeIs(bexit); } else { bcond.succs.push(bexit); nextNodeIs(bexit); } } void visitSwitch(SwitchStatement s) { StmtState mystate = StmtState(stmtstate, s); mystate.switchBlock = curblock; /* Block for where "break" goes to */ mystate.breakBlock = newNode(); /* Block for where "default" goes to. * If there is a default statement, then that is where default goes. * If not, then do: * default: break; * by making the default block the same as the break block. */ mystate.defaultBlock = s.sdefault ? newNode() : mystate.breakBlock; const numcases = s.cases ? s.cases.dim : 0; /* allocate a block for each case */ if (numcases) foreach (cs; *s.cases) { cs.extra = cast(void*)newNode(); } curblock.exp = s.condition; if (s.hasVars) { /* Generate a sequence of if-then-else blocks for the cases. */ if (numcases) foreach (cs; *s.cases) { auto ecase = newNode(); obnodes.push(ecase); ecase.exp = cs.exp; curblock.succs.push(ecase); auto cn = cast(ObNode*)cs.extra; ecase.succs.push(cn); ecase.succs.push(nextNode()); } /* The final 'else' clause goes to the default */ curblock.succs.push(mystate.defaultBlock); nextNode(); visit(s._body, &mystate); /* Have the end of the switch body fall through to the block * following the switch statement. */ gotoNextNodeIs(mystate.breakBlock); return; } auto ob = newNode(); obnodes.push(ob); curblock = ob; mystate.switchBlock.succs.push(mystate.defaultBlock); visit(s._body, &mystate); /* Have the end of the switch body fall through to the block * following the switch statement. */ gotoNextNodeIs(mystate.breakBlock); } void visitCase(CaseStatement s) { auto cb = cast(ObNode*)s.extra; cb.tryBlock = stmtstate.tryBlock; auto bsw = stmtstate.getSwitchBlock(); bsw.succs.push(cb); gotoNextNodeIs(cb); visit(s.statement, stmtstate); } void visitDefault(DefaultStatement s) { auto bdefault = stmtstate.getDefaultBlock; bdefault.tryBlock = stmtstate.tryBlock; gotoNextNodeIs(bdefault); visit(s.statement, stmtstate); } void visitGotoDefault(GotoDefaultStatement s) { gotoDest(stmtstate.getDefaultBlock); } void visitGotoCase(GotoCaseStatement s) { gotoDest(cast(ObNode*)s.cs.extra); } void visitSwitchError(SwitchErrorStatement s) { curblock.obtype = ObType.throw_; curblock.exp = s.exp; nextNode(); } void visitReturn(ReturnStatement s) { //printf("visitReturn() %s\n", s.toChars()); curblock.obtype = s.exp && s.exp.type.toBasetype().ty != Tvoid ? ObType.retexp : ObType.return_; curblock.exp = s.exp; nextNode(); } void visitBreak(BreakStatement s) { gotoDest(stmtstate.getBreakBlock(s.ident)); } void visitContinue(ContinueStatement s) { gotoDest(stmtstate.getContBlock(s.ident)); } void visitWith(WithStatement s) { visit(s._body, stmtstate); } void visitTryCatch(TryCatchStatement s) { /* tryblock * body * breakBlock * catches * breakBlock2 */ StmtState mystate = StmtState(stmtstate, s); mystate.breakBlock = newNode(); auto tryblock = gotoNextNode(); visit(s._body, &mystate); gotoNextNodeIs(mystate.breakBlock); // create new break block that follows all the catches auto breakBlock2 = newNode(); gotoDest(breakBlock2); foreach (cs; *s.catches) { /* Each catch block is a successor to tryblock * and the last block of try body */ StmtState catchState = StmtState(stmtstate, s); auto bcatch = curblock; tryblock.succs.push(bcatch); mystate.breakBlock.succs.push(bcatch); nextNode(); visit(cs.handler, &catchState); gotoDest(breakBlock2); } curblock.succs.push(breakBlock2); obnodes.push(breakBlock2); curblock = breakBlock2; } void visitTryFinally(TryFinallyStatement s) { /* Build this: * 1 goto [2] * 2 try_ [3] [5] [7] * 3 body * 4 goto [8] * 5 finally_ [6] * 6 finalbody * 7 fend [8] * 8 lastblock */ StmtState bodyState = StmtState(stmtstate, s); auto b2 = gotoNextNode(); b2.obtype = ObType.try_; bodyState.tryBlock = b2; gotoNextNode(); visit(s._body, &bodyState); auto b4 = gotoNextNode(); auto b5 = newNode(); b5.obtype = ObType.finally_; nextNodeIs(b5); gotoNextNode(); StmtState finallyState = StmtState(stmtstate, s); visit(s.finalbody, &finallyState); auto b7 = gotoNextNode(); b7.obtype = ObType.fend; auto b8 = gotoNextNode(); b2.succs.push(b5); b2.succs.push(b7); b4.succs.push(b8); } void visitThrow(ThrowStatement s) { curblock.obtype = ObType.throw_; curblock.exp = s.exp; nextNode(); } void visitGoto(GotoStatement s) { gotoDest(cast(ObNode*)s.label.statement.extra); } void visitLabel(LabelStatement s) { StmtState mystate = StmtState(stmtstate, s); mystate.ident = s.ident; auto ob = cast(ObNode*)s.extra; ob.tryBlock = mystate.tryBlock; visit(s.statement, &mystate); } final switch (s.stmt) { case STMT.Exp: visitExp(s.isExpStatement()); break; case STMT.DtorExp: visitDtorExp(s.isDtorExpStatement()); break; case STMT.Compound: visitCompound(s.isCompoundStatement()); break; case STMT.CompoundDeclaration: visitCompoundDeclaration(s.isCompoundDeclarationStatement()); break; case STMT.UnrolledLoop: visitUnrolledLoop(s.isUnrolledLoopStatement()); break; case STMT.Scope: visitScope(s.isScopeStatement()); break; case STMT.Do: visitDo(s.isDoStatement()); break; case STMT.For: visitFor(s.isForStatement()); break; case STMT.If: visitIf(s.isIfStatement()); break; case STMT.Switch: visitSwitch(s.isSwitchStatement()); break; case STMT.Case: visitCase(s.isCaseStatement()); break; case STMT.Default: visitDefault(s.isDefaultStatement()); break; case STMT.GotoDefault: visitGotoDefault(s.isGotoDefaultStatement()); break; case STMT.GotoCase: visitGotoCase(s.isGotoCaseStatement()); break; case STMT.SwitchError: visitSwitchError(s.isSwitchErrorStatement()); break; case STMT.Return: visitReturn(s.isReturnStatement()); break; case STMT.Break: visitBreak(s.isBreakStatement()); break; case STMT.Continue: visitContinue(s.isContinueStatement()); break; case STMT.With: visitWith(s.isWithStatement()); break; case STMT.TryCatch: visitTryCatch(s.isTryCatchStatement()); break; case STMT.TryFinally: visitTryFinally(s.isTryFinallyStatement()); break; case STMT.Throw: visitThrow(s.isThrowStatement()); break; case STMT.Goto: visitGoto(s.isGotoStatement()); break; case STMT.Label: visitLabel(s.isLabelStatement()); break; case STMT.CompoundAsm: case STMT.Asm: case STMT.InlineAsm: case STMT.GccAsm: case STMT.Pragma: case STMT.Import: case STMT.ScopeGuard: case STMT.Error: break; // ignore these case STMT.Foreach: case STMT.ForeachRange: case STMT.Debug: case STMT.CaseRange: case STMT.StaticForeach: case STMT.StaticAssert: case STMT.Conditional: case STMT.While: case STMT.Forwarding: case STMT.Compile: case STMT.Peel: case STMT.Synchronized: debug printf("s: %s\n", s.toChars()); assert(0); // should have been rewritten } } StmtState stmtstate; visit(s, &stmtstate); curblock.obtype = ObType.return_; static if (0) { printf("toObNodes()\n"); printf("------- before ----------\n"); numberNodes(obnodes); foreach (ob; obnodes) ob.print(); printf("-------------------------\n"); } assert(stmtstate.breakBlock is null); assert(stmtstate.contBlock is null); assert(stmtstate.switchBlock is null); assert(stmtstate.defaultBlock is null); assert(stmtstate.tryBlock is null); } /*************************************************** * Insert finally block calls when doing a goto from * inside a try block to outside. * Done after blocks are generated because then we know all * the edges of the graph, but before the pred's are computed. * Params: * obnodes = graph of the function */ void insertFinallyBlockCalls(ref ObNodes obnodes) { ObNode* bcret = null; ObNode* bcretexp = null; enum log = false; static if (log) { printf("insertFinallyBlockCalls()\n"); printf("------- before ----------\n"); numberNodes(obnodes); foreach (ob; obnodes) ob.print(); printf("-------------------------\n"); } foreach (ob; obnodes) { if (!ob.tryBlock) continue; switch (ob.obtype) { case ObType.return_: // Rewrite into a ObType.goto_ => ObType.return_ if (!bcret) { bcret = new ObNode(); bcret.obtype = ob.obtype; } ob.obtype = ObType.goto_; ob.succs.push(bcret); goto case_goto; case ObType.retexp: // Rewrite into a ObType.goto_ => ObType.retexp if (!bcretexp) { bcretexp = new ObNode(); bcretexp.obtype = ob.obtype; } ob.obtype = ObType.goto_; ob.succs.push(bcretexp); goto case_goto; case ObType.goto_: if (ob.succs.length != 1) break; case_goto: { auto target = ob.succs[0]; // destination of goto ob.succs.setDim(0); auto lasttry = target.tryBlock; auto blast = ob; for (auto bt = ob.tryBlock; bt != lasttry; bt = bt.tryBlock) { assert(bt.obtype == ObType.try_); auto bf = bt.succs[1]; assert(bf.obtype == ObType.finally_); auto bfend = bt.succs[2]; assert(bfend.obtype == ObType.fend); if (!blast.succs.contains(bf.succs[0])) blast.succs.push(bf.succs[0]); blast = bfend; } if (!blast.succs.contains(target)) blast.succs.push(target); break; } default: break; } } if (bcret) obnodes.push(bcret); if (bcretexp) obnodes.push(bcretexp); static if (log) { printf("------- after ----------\n"); numberNodes(obnodes); foreach (ob; obnodes) ob.print(); printf("-------------------------\n"); } } /*************************************************** * Remove try-finally scaffolding. * Params: * obnodes = nodes for the function */ void insertFinallyBlockGotos(ref ObNodes obnodes) { /* Remove all the try_, finally_, lpad and ret nodes. * Actually, just make them into no-ops. */ foreach (ob; obnodes) { ob.tryBlock = null; switch (ob.obtype) { case ObType.try_: ob.obtype = ObType.goto_; ob.succs.remove(2); // remove fend ob.succs.remove(1); // remove finally_ break; case ObType.finally_: ob.obtype = ObType.goto_; break; case ObType.fend: ob.obtype = ObType.goto_; break; default: break; } } } /********************************* * Set the `index` field of each ObNode * to its index in the `obnodes[]` array. */ void numberNodes(ref ObNodes obnodes) { //printf("numberNodes()\n"); foreach (i, ob; obnodes) { //printf("ob = %d, %p\n", i, ob); ob.index = cast(uint)i; } // Verify that nodes do not appear more than once in obnodes[] debug foreach (i, ob; obnodes) { assert(ob.index == cast(uint)i); } } /********************************* * Remove unreachable nodes and compress * them out of obnodes[]. * Params: * obnodes = array of nodes */ void removeUnreachable(ref ObNodes obnodes) { if (!obnodes.length) return; /* Mark all nodes as unreachable, * temporarilly reusing ObNode.index */ foreach (ob; obnodes) ob.index = 0; /* Recursively mark ob and all its successors as reachable */ static void mark(ObNode* ob) { ob.index = 1; foreach (succ; ob.succs) { if (!succ.index) mark(succ); } } mark(obnodes[0]); // first node is entry point /* Remove unreachable nodes by shifting the remainder left */ size_t j = 1; foreach (i; 1 .. obnodes.length) { if (obnodes[i].index) { if (i != j) obnodes[j] = obnodes[i]; ++j; } else { obnodes[i].destroy(); } } obnodes.setDim(j); } /************************************* * Compute predecessors. */ void computePreds(ref ObNodes obnodes) { foreach (ob; obnodes) { foreach (succ; ob.succs) { succ.preds.push(ob); } } } /******************************* * Are we interested in tracking variable `v`? */ bool isTrackableVar(VarDeclaration v) { //printf("isTrackableVar() %s\n", v.toChars()); auto tb = v.type.toBasetype(); /* Assume class references are managed by the GC, * don't need to track them */ if (tb.ty == Tclass) return false; /* Assume types with a destructor are doing their own tracking, * such as being a ref counted type */ if (v.needsScopeDtor()) return false; /* Not tracking function parameters that are not mutable */ if (v.storage_class & STC.parameter && !tb.hasPointersToMutableFields()) return false; /* Not tracking global variables */ return !v.isDataseg(); } /******************************* * Are we interested in tracking this expression? * Returns: * variable if so, null if not */ VarDeclaration isTrackableVarExp(Expression e) { if (auto ve = e.isVarExp()) { if (auto v = ve.var.isVarDeclaration()) if (isTrackableVar(v)) return v; } return null; } /************** * Find the pointer variable declarations in this function, * and fill `vars` with them. * Params: * funcdecl = function we are in * vars = array to fill in */ void collectVars(FuncDeclaration funcdecl, out VarDeclarations vars) { enum log = false; if (log) printf("----------------collectVars()---------------\n"); if (funcdecl.parameters) foreach (v; (*funcdecl.parameters)[]) { if (isTrackableVar(v)) vars.push(v); } void dgVar(VarDeclaration v) { if (isTrackableVar(v)) vars.push(v); } void dgExp(Expression e) { foreachVar(e, &dgVar); } foreachExpAndVar(funcdecl.fbody, &dgExp, &dgVar); static if (log) { foreach (i, v; vars[]) { printf("vars[%d] = %s\n", cast(int)i, v.toChars()); } } } /*********************************** * Allocate BitArrays in PtrVarState. * Can be allocated much more efficiently by subdividing a single * large array of bits */ void allocDeps(PtrVarState[] pvss) { //printf("allocDeps()\n"); foreach (ref pvs; pvss) { pvs.deps.length = pvss.length; } } /************************************** * Allocate state variables foreach node. */ void allocStates(ref ObState obstate) { //printf("---------------allocStates()------------------\n"); const vlen = obstate.vars.length; PtrVarState* p = cast(PtrVarState*) mem.xcalloc(obstate.nodes.length * 3 * vlen, PtrVarState.sizeof); obstate.varPool = p[0 .. obstate.nodes.length * 3 * vlen]; foreach (i, ob; obstate.nodes) { //printf(" [%d]\n", cast(int)i); // ob.kill.length = obstate.vars.length; // ob.comb.length = obstate.vars.length; ob.gen = p[0 .. vlen]; p += vlen; ob.input = p[0 .. vlen]; p += vlen; ob.output = p[0 .. vlen]; p += vlen; allocDeps(ob.gen); allocDeps(ob.input); allocDeps(ob.output); } } /****************************** * Does v meet the definiton of a `Borrowed` pointer? * Returns: * true if it does */ bool isBorrowedPtr(VarDeclaration v) { return v.isScope() && !v.isowner && v.type.nextOf().isMutable(); } /****************************** * Does v meet the definiton of a `Readonly` pointer? * Returns: * true if it does */ bool isReadonlyPtr(VarDeclaration v) { return v.isScope() && !v.type.nextOf().isMutable(); } /*************************************** * Compute the gen vector for ob. */ void genKill(ref ObState obstate, ObNode* ob) { enum log = false; if (log) printf("-----------computeGenKill()-----------\n"); /*************** * Assigning result of expression `e` to variable `v`. */ void dgWriteVar(ObNode* ob, VarDeclaration v, Expression e, bool initializer) { if (log) printf("dgWriteVar() %s := %s %d\n", v.toChars(), e.toChars(), initializer); const vi = obstate.vars.find(v); assert(vi != size_t.max); PtrVarState* pvs = &ob.gen[vi]; readVar(ob, vi, true, ob.gen); if (e) { if (isBorrowedPtr(v)) pvs.state = PtrState.Borrowed; else if (isReadonlyPtr(v)) pvs.state = PtrState.Readonly; else pvs.state = PtrState.Owner; pvs.deps.zero(); EscapeByResults er; escapeByValue(e, &er, true); bool any = false; // if any variables are assigned to v void by(VarDeclaration r) { const ri = obstate.vars.find(r); if (ri != size_t.max && ri != vi) { pvs.deps[ri] = true; // v took from r auto pvsr = &ob.gen[ri]; any = true; if (isBorrowedPtr(v)) { // v is borrowing from r pvs.state = PtrState.Borrowed; } else if (isReadonlyPtr(v)) { pvs.state = PtrState.Readonly; } else { // move r to v, which "consumes" r pvsr.state = PtrState.Undefined; pvsr.deps.zero(); } } } foreach (VarDeclaration v2; er.byvalue) by(v2); foreach (VarDeclaration v2; er.byref) by(v2); /* Make v an Owner for initializations like: * scope v = malloc(); */ if (initializer && !any && isBorrowedPtr(v)) { v.isowner = true; pvs.state = PtrState.Owner; } } else { if (isBorrowedPtr(v)) pvs.state = PtrState.Borrowed; else if (isReadonlyPtr(v)) pvs.state = PtrState.Readonly; else pvs.state = PtrState.Owner; pvs.deps.zero(); } } void dgReadVar(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) { if (log) printf("dgReadVar() %s %d\n", v.toChars(), mutable); const vi = obstate.vars.find(v); assert(vi != size_t.max); readVar(ob, vi, mutable, ob.gen); } void foreachExp(ObNode* ob, Expression e) { extern (C++) final class ExpWalker : Visitor { alias visit = typeof(super).visit; extern (D) void delegate(ObNode*, VarDeclaration, Expression, bool) dgWriteVar; extern (D) void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) dgReadVar; ObNode* ob; ObState* obstate; extern (D) this(void delegate(ObNode*, VarDeclaration, Expression, bool) dgWriteVar, void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) dgReadVar, ObNode* ob, ref ObState obstate) { this.dgWriteVar = dgWriteVar; this.dgReadVar = dgReadVar; this.ob = ob; this.obstate = &obstate; } override void visit(Expression e) { //printf("[%s] %s: %s\n", e.loc.toChars(), EXPtoString(e.op).ptr, e.toChars()); //assert(0); } void visitAssign(AssignExp ae, bool initializer) { ae.e2.accept(this); if (auto ve = ae.e1.isVarExp()) { if (auto v = ve.var.isVarDeclaration()) if (isTrackableVar(v)) dgWriteVar(ob, v, ae.e2, initializer); } else ae.e1.accept(this); } override void visit(AssignExp ae) { visitAssign(ae, false); } override void visit(DeclarationExp e) { void Dsymbol_visit(Dsymbol s) { if (auto vd = s.isVarDeclaration()) { s = s.toAlias(); if (s != vd) return Dsymbol_visit(s); if (!isTrackableVar(vd)) return; if (!(vd._init && vd._init.isVoidInitializer())) { auto ei = vd._init ? vd._init.isExpInitializer() : null; if (ei) visitAssign(cast(AssignExp)ei.exp, true); else dgWriteVar(ob, vd, null, false); } } else if (auto td = s.isTupleDeclaration()) { td.foreachVar(&Dsymbol_visit); } } Dsymbol_visit(e.declaration); } override void visit(VarExp ve) { //printf("VarExp: %s\n", ve.toChars()); if (auto v = ve.var.isVarDeclaration()) if (isTrackableVar(v)) { dgReadVar(ve.loc, ob, v, isMutableRef(ve.type)); } } override void visit(CallExp ce) { //printf("CallExp() %s\n", ce.toChars()); ce.e1.accept(this); auto t = ce.e1.type.toBasetype(); auto tf = t.isTypeFunction(); if (!tf) { assert(t.ty == Tdelegate); tf = t.nextOf().isTypeFunction(); assert(tf); } // j=1 if _arguments[] is first argument const int j = tf.isDstyleVariadic(); bool hasOut; const varStackSave = obstate.varStack.length; foreach (const i, arg; (*ce.arguments)[]) { if (i - j < tf.parameterList.length && i >= j) { Parameter p = tf.parameterList[i - j]; auto pt = p.type.toBasetype(); EscapeByResults er; escapeByValue(arg, &er, true); if (!(p.storageClass & STC.out_ && arg.isVarExp())) arg.accept(this); void by(VarDeclaration v) { if (!isTrackableVar(v)) return; const vi = obstate.vars.find(v); if (vi == size_t.max) return; if (p.storageClass & STC.out_) { /// initialize hasOut = true; makeUndefined(vi, ob.gen); } else if (p.storageClass & STC.scope_) { // borrow obstate.varStack.push(vi); obstate.mutableStack.push(isMutableRef(pt)); } else { // move (i.e. consume arg) makeUndefined(vi, ob.gen); } } foreach (VarDeclaration v2; er.byvalue) by(v2); foreach (VarDeclaration v2; er.byref) by(v2); } else // variadic args { arg.accept(this); EscapeByResults er; escapeByValue(arg, &er, true); void byv(VarDeclaration v) { if (!isTrackableVar(v)) return; const vi = obstate.vars.find(v); if (vi == size_t.max) return; if (tf.parameterList.stc & STC.scope_) { // borrow obstate.varStack.push(vi); obstate.mutableStack.push(isMutableRef(arg.type) && !(tf.parameterList.stc & (STC.const_ | STC.immutable_))); } else // move (i.e. consume arg) makeUndefined(vi, ob.gen); } foreach (VarDeclaration v2; er.byvalue) byv(v2); foreach (VarDeclaration v2; er.byref) byv(v2); } } /* Do a dummy 'read' of each variable passed to the function, * to detect O/B errors */ assert(obstate.varStack.length == obstate.mutableStack.length); foreach (i; varStackSave .. obstate.varStack.length) { const vi = obstate.varStack[i]; // auto pvs = &ob.gen[vi]; auto v = obstate.vars[vi]; //if (pvs.state == PtrState.Undefined) //v.error(ce.loc, "is Undefined, cannot pass to function"); dgReadVar(ce.loc, ob, v, obstate.mutableStack[i]); } /* Pop off stack all variables for this function call */ obstate.varStack.setDim(varStackSave); obstate.mutableStack.setDim(varStackSave); if (hasOut) // Initialization of out's only happens after the function call foreach (const i, arg; (*ce.arguments)[]) { if (i - j < tf.parameterList.length && i >= j) { Parameter p = tf.parameterList[i - j]; if (p.storageClass & STC.out_) { if (auto v = isTrackableVarExp(arg)) dgWriteVar(ob, v, null, true); } } } } override void visit(SymOffExp e) { if (auto v = e.var.isVarDeclaration()) if (isTrackableVar(v)) { dgReadVar(e.loc, ob, v, isMutableRef(e.type)); } } override void visit(LogicalExp e) { e.e1.accept(this); const vlen = obstate.vars.length; auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); PtrVarState[] gen1 = p[0 .. vlen]; foreach (i, ref pvs; gen1) { pvs = ob.gen[i]; } e.e2.accept(this); // Merge gen1 into ob.gen foreach (i; 0 .. vlen) { ob.gen[i].combine(gen1[i], i, ob.gen); } mem.xfree(p); // should free .deps too } override void visit(CondExp e) { e.econd.accept(this); const vlen = obstate.vars.length; auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); PtrVarState[] gen1 = p[0 .. vlen]; foreach (i, ref pvs; gen1) { pvs = ob.gen[i]; } e.e1.accept(this); // Swap gen1 with ob.gen foreach (i; 0 .. vlen) { gen1[i].deps.swap(ob.gen[i].deps); const state = gen1[i].state; gen1[i].state = ob.gen[i].state; ob.gen[i].state = state; } e.e2.accept(this); /* xxx1 is the state from expression e1, ob.xxx is the state from e2. * Merge xxx1 into ob.xxx to get the state from `e`. */ foreach (i; 0 .. vlen) { ob.gen[i].combine(gen1[i], i, ob.gen); } mem.xfree(p); // should free .deps too } override void visit(AddrExp e) { /* Taking the address of struct literal is normally not * allowed, but CTFE can generate one out of a new expression, * but it'll be placed in static data so no need to check it. */ if (e.e1.op != EXP.structLiteral) e.e1.accept(this); } override void visit(UnaExp e) { e.e1.accept(this); } override void visit(BinExp e) { e.e1.accept(this); e.e2.accept(this); } override void visit(ArrayLiteralExp e) { Type tb = e.type.toBasetype(); if (tb.ty == Tsarray || tb.ty == Tarray) { if (e.basis) e.basis.accept(this); foreach (el; *e.elements) { if (el) el.accept(this); } } } override void visit(StructLiteralExp e) { if (e.elements) { foreach (ex; *e.elements) { if (ex) ex.accept(this); } } } override void visit(AssocArrayLiteralExp e) { if (e.keys) { foreach (i, key; *e.keys) { if (key) key.accept(this); if (auto value = (*e.values)[i]) value.accept(this); } } } override void visit(NewExp e) { if (e.arguments) { foreach (ex; *e.arguments) { if (ex) ex.accept(this); } } } override void visit(SliceExp e) { e.e1.accept(this); if (e.lwr) e.lwr.accept(this); if (e.upr) e.upr.accept(this); } } if (e) { scope ExpWalker ew = new ExpWalker(&dgWriteVar, &dgReadVar, ob, obstate); e.accept(ew); } } foreachExp(ob, ob.exp); } /*************************************** * Determine the state of a variable based on * its type and storage class. */ PtrState toPtrState(VarDeclaration v) { /* pointer to mutable: Owner * pointer to mutable, scope: Borrowed * pointer to const: Owner * pointer to const, scope: Readonly * ref: Borrowed * const ref: Readonly */ auto t = v.type; if (v.isReference()) { return t.hasMutableFields() ? PtrState.Borrowed : PtrState.Readonly; } if (v.isScope()) { return t.hasPointersToMutableFields() ? PtrState.Borrowed : PtrState.Readonly; } else return PtrState.Owner; } /********************************** * Does type `t` contain any pointers to mutable? */ bool hasPointersToMutableFields(Type t) { auto tb = t.toBasetype(); if (!tb.isMutable()) return false; if (auto tsa = tb.isTypeSArray()) { return tsa.nextOf().hasPointersToMutableFields(); } if (auto ts = tb.isTypeStruct()) { foreach (v; ts.sym.fields) { if (v.isReference()) { if (v.type.hasMutableFields()) return true; } else if (v.type.hasPointersToMutableFields()) return true; } return false; } auto tbn = tb.nextOf(); return tbn && tbn.hasMutableFields(); } /******************************** * Does type `t` have any mutable fields? */ bool hasMutableFields(Type t) { auto tb = t.toBasetype(); if (!tb.isMutable()) return false; if (auto tsa = tb.isTypeSArray()) { return tsa.nextOf().hasMutableFields(); } if (auto ts = tb.isTypeStruct()) { foreach (v; ts.sym.fields) { if (v.type.hasMutableFields()) return true; } return false; } return true; } /*************************************** * Do the data flow analysis (i.e. compute the input[] * and output[] vectors for each ObNode). */ void doDataFlowAnalysis(ref ObState obstate) { enum log = false; if (log) { printf("-----------------doDataFlowAnalysis()-------------------------\n"); foreach (ob; obstate.nodes) ob.print(); printf("------------------------------------------\n"); } if (!obstate.nodes.length) return; auto startnode = obstate.nodes[0]; assert(startnode.preds.length == 0); /* Set opening state `input[]` for first node */ foreach (i, ref ps; startnode.input) { auto v = obstate.vars[i]; auto state = toPtrState(v); if (v.isParameter()) { if (v.isOut()) state = PtrState.Undefined; else if (v.isBorrowedPtr()) state = PtrState.Borrowed; else state = PtrState.Owner; } else state = PtrState.Undefined; ps.state = state; ps.deps.zero(); startnode.gen[i] = ps; } /* Set all output[]s to Initial */ foreach (ob; obstate.nodes[]) { foreach (ref ps; ob.output) { ps.state = PtrState.Initial; ps.deps.zero(); } } const vlen = obstate.vars.length; PtrVarState pvs; pvs.deps.length = vlen; int counter = 0; bool changes; do { changes = false; assert(++counter <= 1000); // should converge, but don't hang if it doesn't foreach (ob; obstate.nodes[]) { /* Construct ob.gen[] by combining the .output[]s of each ob.preds[] * and set ob.input[] to the same state */ if (ob != startnode) { assert(ob.preds.length); foreach (i; 0 .. vlen) { ob.gen[i] = ob.preds[0].output[i]; } foreach (j; 1 .. ob.preds.length) { foreach (i; 0 .. vlen) { ob.gen[i].combine(ob.preds[j].output[i], i, ob.gen); } } /* Set ob.input[] to ob.gen[], * if any changes were made we'll have to do another iteration */ foreach (i; 0 .. vlen) { if (ob.gen[i] != ob.input[i]) { ob.input[i] = ob.gen[i]; changes = true; } } } /* Compute gen[] for node ob */ genKill(obstate, ob); foreach (i; 0 .. vlen) { if (ob.gen[i] != ob.output[i]) { ob.output[i] = ob.gen[i]; changes = true; } } } } while (changes); static if (log) { foreach (obi, ob; obstate.nodes) { printf("%d: %s\n", obi, ob.exp ? ob.exp.toChars() : "".ptr); printf(" input:\n"); foreach (i, ref pvs2; ob.input[]) { printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); } printf(" gen:\n"); foreach (i, ref pvs2; ob.gen[]) { printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); } printf(" output:\n"); foreach (i, ref pvs2; ob.output[]) { printf(" %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]); } } printf("\n"); } } /*************************************** * Check for Ownership/Borrowing errors. */ void checkObErrors(ref ObState obstate) { enum log = false; if (log) printf("------------checkObErrors()----------\n"); void dgWriteVar(ObNode* ob, PtrVarState[] cpvs, VarDeclaration v, Expression e) { if (log) printf("dgWriteVar(v:%s, e:%s)\n", v.toChars(), e ? e.toChars() : "null"); const vi = obstate.vars.find(v); assert(vi != size_t.max); PtrVarState* pvs = &cpvs[vi]; readVar(ob, vi, true, cpvs); if (e) { if (isBorrowedPtr(v)) pvs.state = PtrState.Borrowed; else if (isReadonlyPtr(v)) pvs.state = PtrState.Readonly; else { if (pvs.state == PtrState.Owner && v.type.hasPointersToMutableFields()) v.error(e.loc, "assigning to Owner without disposing of owned value"); pvs.state = PtrState.Owner; } pvs.deps.zero(); EscapeByResults er; escapeByValue(e, &er, true); void by(VarDeclaration r) // `v` = `r` { //printf(" by(%s)\n", r.toChars()); const ri = obstate.vars.find(r); if (ri == size_t.max) return; with (PtrState) { pvs.deps[ri] = true; // v took from r auto pvsr = &cpvs[ri]; if (pvsr.state == Undefined) { v.error(e.loc, "is reading from `%s` which is Undefined", r.toChars()); } else if (isBorrowedPtr(v)) // v is going to borrow from r { if (pvsr.state == Readonly) v.error(e.loc, "is borrowing from `%s` which is Readonly", r.toChars()); pvs.state = Borrowed; } else if (isReadonlyPtr(v)) { pvs.state = Readonly; } else { // move from r to v pvsr.state = Undefined; pvsr.deps.zero(); } } } foreach (VarDeclaration v2; er.byvalue) by(v2); foreach (VarDeclaration v2; er.byref) by(v2); } else { if (isBorrowedPtr(v)) pvs.state = PtrState.Borrowed; else if (isReadonlyPtr(v)) pvs.state = PtrState.Readonly; else pvs.state = PtrState.Owner; pvs.deps.zero(); } } void dgReadVar(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[] gen) { if (log) printf("dgReadVar() %s\n", v.toChars()); const vi = obstate.vars.find(v); assert(vi != size_t.max); auto pvs = &gen[vi]; if (pvs.state == PtrState.Undefined) v.error(loc, "has undefined state and cannot be read"); readVar(ob, vi, mutable, gen); } void foreachExp(ObNode* ob, Expression e, PtrVarState[] cpvs) { extern (C++) final class ExpWalker : Visitor { alias visit = typeof(super).visit; extern (D) void delegate(ObNode*, PtrVarState[], VarDeclaration, Expression) dgWriteVar; extern (D) void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[]) dgReadVar; PtrVarState[] cpvs; ObNode* ob; ObState* obstate; extern (D) this(void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[]) dgReadVar, void delegate(ObNode*, PtrVarState[], VarDeclaration, Expression) dgWriteVar, PtrVarState[] cpvs, ObNode* ob, ref ObState obstate) { this.dgReadVar = dgReadVar; this.dgWriteVar = dgWriteVar; this.cpvs = cpvs; this.ob = ob; this.obstate = &obstate; } override void visit(Expression) { } override void visit(DeclarationExp e) { void Dsymbol_visit(Dsymbol s) { if (auto vd = s.isVarDeclaration()) { s = s.toAlias(); if (s != vd) return Dsymbol_visit(s); if (!isTrackableVar(vd)) return; if (vd._init && vd._init.isVoidInitializer()) return; auto ei = vd._init ? vd._init.isExpInitializer() : null; if (ei) { auto e = ei.exp; if (auto ae = e.isConstructExp()) e = ae.e2; dgWriteVar(ob, cpvs, vd, e); } else dgWriteVar(ob, cpvs, vd, null); } else if (auto td = s.isTupleDeclaration()) { td.foreachVar(&Dsymbol_visit); } } Dsymbol_visit(e.declaration); } override void visit(AssignExp ae) { ae.e2.accept(this); if (auto ve = ae.e1.isVarExp()) { if (auto v = ve.var.isVarDeclaration()) if (isTrackableVar(v)) dgWriteVar(ob, cpvs, v, ae.e2); } else ae.e1.accept(this); } override void visit(VarExp ve) { //printf("VarExp: %s\n", ve.toChars()); if (auto v = ve.var.isVarDeclaration()) if (isTrackableVar(v)) { dgReadVar(ve.loc, ob, v, isMutableRef(ve.type), cpvs); } } override void visit(CallExp ce) { //printf("CallExp(%s)\n", ce.toChars()); ce.e1.accept(this); auto t = ce.e1.type.toBasetype(); auto tf = t.isTypeFunction(); if (!tf) { assert(t.ty == Tdelegate); tf = t.nextOf().isTypeFunction(); assert(tf); } // j=1 if _arguments[] is first argument const int j = tf.isDstyleVariadic(); bool hasOut; const varStackSave = obstate.varStack.length; foreach (const i, arg; (*ce.arguments)[]) { if (i - j < tf.parameterList.length && i >= j) { Parameter p = tf.parameterList[i - j]; auto pt = p.type.toBasetype(); if (!(p.storageClass & STC.out_ && arg.isVarExp())) arg.accept(this); EscapeByResults er; escapeByValue(arg, &er, true); void by(VarDeclaration v) { if (!isTrackableVar(v)) return; const vi = obstate.vars.find(v); if (vi == size_t.max) return; auto pvs = &cpvs[vi]; if (p.storageClass & STC.out_) { /// initialize hasOut = true; makeUndefined(vi, cpvs); } else if (p.storageClass & STC.scope_) { // borrow obstate.varStack.push(vi); obstate.mutableStack.push(isMutableRef(pt)); } else { // move (i.e. consume arg) if (pvs.state != PtrState.Owner) v.error(arg.loc, "is not Owner, cannot consume its value"); makeUndefined(vi, cpvs); } } foreach (VarDeclaration v2; er.byvalue) by(v2); foreach (VarDeclaration v2; er.byref) by(v2); } else // variadic args { arg.accept(this); EscapeByResults er; escapeByValue(arg, &er, true); void byv(VarDeclaration v) { if (!isTrackableVar(v)) return; const vi = obstate.vars.find(v); if (vi == size_t.max) return; auto pvs = &cpvs[vi]; if (tf.parameterList.stc & STC.scope_) { // borrow obstate.varStack.push(vi); obstate.mutableStack.push(isMutableRef(arg.type) && !(tf.parameterList.stc & (STC.const_ | STC.immutable_))); } else { // move (i.e. consume arg) if (pvs.state != PtrState.Owner) v.error(arg.loc, "is not Owner, cannot consume its value"); makeUndefined(vi, cpvs); } } foreach (VarDeclaration v2; er.byvalue) byv(v2); foreach (VarDeclaration v2; er.byref) byv(v2); } } /* Do a dummy 'read' of each variable passed to the function, * to detect O/B errors */ assert(obstate.varStack.length == obstate.mutableStack.length); foreach (i; varStackSave .. obstate.varStack.length) { const vi = obstate.varStack[i]; auto pvs = &cpvs[vi]; auto v = obstate.vars[vi]; //if (pvs.state == PtrState.Undefined) //v.error(ce.loc, "is Undefined, cannot pass to function"); dgReadVar(ce.loc, ob, v, obstate.mutableStack[i], cpvs); if (pvs.state == PtrState.Owner) { for (size_t k = i + 1; k < obstate.varStack.length;++k) { const vk = obstate.varStack[k]; if (vk == vi) { if (obstate.mutableStack[vi] || obstate.mutableStack[vk]) { v.error(ce.loc, "is passed as Owner more than once"); break; // no need to continue } } } } } /* Pop off stack all variables for this function call */ obstate.varStack.setDim(varStackSave); obstate.mutableStack.setDim(varStackSave); if (hasOut) // Initialization of out's only happens after the function call foreach (const i, arg; (*ce.arguments)[]) { if (i - j < tf.parameterList.length && i >= j) { Parameter p = tf.parameterList[i - j]; if (p.storageClass & STC.out_) { if (auto v = isTrackableVarExp(arg)) { dgWriteVar(ob, cpvs, v, null); } } } } } override void visit(SymOffExp e) { if (auto v = e.var.isVarDeclaration()) if (isTrackableVar(v)) { dgReadVar(e.loc, ob, v, isMutableRef(e.type), cpvs); } } override void visit(LogicalExp e) { e.e1.accept(this); const vlen = obstate.vars.length; auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); PtrVarState[] out1 = p[0 .. vlen]; foreach (i, ref pvs; out1) { pvs = cpvs[i]; } e.e2.accept(this); // Merge out1 into cpvs foreach (i; 0 .. vlen) { cpvs[i].combine(out1[i], i, cpvs); } mem.xfree(p); // should free .deps too } override void visit(CondExp e) { e.econd.accept(this); const vlen = obstate.vars.length; auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); PtrVarState[] out1 = p[0 .. vlen]; foreach (i, ref pvs; out1) { pvs = cpvs[i]; } e.e1.accept(this); // Swap out1 with cpvs foreach (i; 0 .. vlen) { out1[i].deps.swap(cpvs[i].deps); const state = out1[i].state; out1[i].state = cpvs[i].state; cpvs[i].state = state; } e.e2.accept(this); // Merge out1 into cpvs foreach (i; 0 .. vlen) { cpvs[i].combine(out1[i], i, cpvs); } mem.xfree(p); // should free .deps too } override void visit(AddrExp e) { /* Taking the address of struct literal is normally not * allowed, but CTFE can generate one out of a new expression, * but it'll be placed in static data so no need to check it. */ if (e.e1.op != EXP.structLiteral) e.e1.accept(this); } override void visit(UnaExp e) { e.e1.accept(this); } override void visit(BinExp e) { e.e1.accept(this); e.e2.accept(this); } override void visit(ArrayLiteralExp e) { Type tb = e.type.toBasetype(); if (tb.ty == Tsarray || tb.ty == Tarray) { if (e.basis) e.basis.accept(this); foreach (el; *e.elements) { if (el) el.accept(this); } } } override void visit(StructLiteralExp e) { if (e.elements) { foreach (ex; *e.elements) { if (ex) ex.accept(this); } } } override void visit(AssocArrayLiteralExp e) { if (e.keys) { foreach (i, key; *e.keys) { if (key) key.accept(this); if (auto value = (*e.values)[i]) value.accept(this); } } } override void visit(NewExp e) { if (e.arguments) { foreach (ex; *e.arguments) { if (ex) ex.accept(this); } } } override void visit(SliceExp e) { e.e1.accept(this); if (e.lwr) e.lwr.accept(this); if (e.upr) e.upr.accept(this); } } if (e) { scope ExpWalker ew = new ExpWalker(&dgReadVar, &dgWriteVar, cpvs, ob, obstate); e.accept(ew); } } const vlen = obstate.vars.length; auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof); PtrVarState[] cpvs = p[0 .. vlen]; foreach (ref pvs; cpvs) pvs.deps.length = vlen; foreach (obi, ob; obstate.nodes) { static if (log) { printf("%d: %s\n", obi, ob.exp ? ob.exp.toChars() : "".ptr); printf(" input:\n"); foreach (i, ref pvs; ob.input[]) { printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); } } /* Combine the .output[]s of each ob.preds[] looking for errors */ if (obi) // skip startnode { assert(ob.preds.length); foreach (i; 0 .. vlen) { ob.gen[i] = ob.preds[0].output[i]; } foreach (j; 1 .. ob.preds.length) { foreach (i; 0 .. vlen) { auto pvs1 = &ob.gen[i]; auto pvs2 = &ob.preds[j].output[i]; const s1 = pvs1.state; const s2 = pvs2.state; if (s1 != s2 && (s1 == PtrState.Owner || s2 == PtrState.Owner)) { auto v = obstate.vars[i]; v.error(ob.exp ? ob.exp.loc : v.loc, "is both %s and %s", s1.toChars(), s2.toChars()); } pvs1.combine(*pvs2, i, ob.gen); } } } /* Prolly should use gen[] instead of cpvs[], or vice versa */ foreach (i, ref pvs; ob.input) { cpvs[i] = pvs; } foreachExp(ob, ob.exp, cpvs); static if (log) { printf(" cpvs:\n"); foreach (i, ref pvs; cpvs[]) { printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); } printf(" output:\n"); foreach (i, ref pvs; ob.output[]) { printf(" %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); } } if (ob.obtype == ObType.retexp) { EscapeByResults er; escapeByValue(ob.exp, &er, true); void by(VarDeclaration r) // `r` is the rvalue { const ri = obstate.vars.find(r); if (ri == size_t.max) return; with (PtrState) { auto pvsr = &ob.output[ri]; switch (pvsr.state) { case Undefined: r.error(ob.exp.loc, "is returned but is Undefined"); break; case Owner: pvsr.state = Undefined; // returning a pointer "consumes" it break; case Borrowed: case Readonly: break; default: assert(0); } } } foreach (VarDeclaration v2; er.byvalue) by(v2); foreach (VarDeclaration v2; er.byref) by(v2); } if (ob.obtype == ObType.return_ || ob.obtype == ObType.retexp) { foreach (i, ref pvs; ob.output[]) { //printf("%s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]); if (pvs.state == PtrState.Owner) { auto v = obstate.vars[i]; if (v.type.hasPointers()) v.error(v.loc, "is left dangling at return"); } } } } } /*************************************************** * Read from variable vi. * The beginning of the 'scope' of a variable is when it is first read. * Hence, when a read is done, instead of when assignment to the variable is done, the O/B rules are enforced. * (Also called "non-lexical scoping".) */ void readVar(ObNode* ob, const size_t vi, bool mutable, PtrVarState[] gen) { //printf("readVar(v%d)\n", cast(int)vi); auto pvso = &gen[vi]; switch (pvso.state) { case PtrState.Owner: //printf("t: %s\n", t.toChars()); if (mutable) // if mutable read { makeChildrenUndefined(vi, gen); } else // const read { // If there's a Borrow child, set that to Undefined foreach (di; 0 .. gen.length) { auto pvsd = &gen[di]; if (pvsd.deps[vi] && pvsd.state == PtrState.Borrowed) // if di borrowed vi { makeUndefined(di, gen); } } } break; case PtrState.Borrowed: /* All children become Undefined */ makeChildrenUndefined(vi, gen); break; case PtrState.Readonly: break; case PtrState.Undefined: break; default: break; } } /******************** * Recursively make Undefined all who list vi as a dependency */ void makeChildrenUndefined(size_t vi, PtrVarState[] gen) { //printf("makeChildrenUndefined(%d)\n", vi); foreach (di; 0 .. gen.length) { if (gen[di].deps[vi]) // if di depends on vi { if (gen[di].state != PtrState.Undefined) { gen[di].state = PtrState.Undefined; // set this first to avoid infinite recursion makeChildrenUndefined(di, gen); gen[di].deps.zero(); } } } } /******************** * Recursively make Undefined vi undefined and all who list vi as a dependency */ void makeUndefined(size_t vi, PtrVarState[] gen) { auto pvs = &gen[vi]; pvs.state = PtrState.Undefined; // set this first to avoid infinite recursion makeChildrenUndefined(vi, gen); pvs.deps.zero(); } /************************* * Is type `t` a reference to a const or a reference to a mutable? */ bool isMutableRef(Type t) { auto tb = t.toBasetype(); return (tb.nextOf() ? tb.nextOf() : tb).isMutable(); }