diff options
Diffstat (limited to 'gcc/d/dmd/ob.d')
| -rw-r--r-- | gcc/d/dmd/ob.d | 2680 |
1 files changed, 2680 insertions, 0 deletions
diff --git a/gcc/d/dmd/ob.d b/gcc/d/dmd/ob.d new file mode 100644 index 0000000..7719ccf --- /dev/null +++ b/gcc/d/dmd/ob.d @@ -0,0 +1,2680 @@ +/** + * Flow analysis for Ownership/Borrowing + * + * Copyright: Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved + * Authors: $(LINK2 http://www.digitalmars.com, Walter Bright) + * License: $(LINK2 http://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.root.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(), Token.toChars(e.op), 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()) + { + foreach (o; *td.objects) + { + if (auto eo = o.isExpression()) + { + if (auto se = eo.isDsymbolExp()) + { + Dsymbol_visit(se.s); + } + } + } + } + } + + 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 != TOK.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.isRef()) + { + 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.isRef()) + { + 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 + 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()) + { + foreach (o; *td.objects) + { + if (auto eo = o.isExpression()) + { + if (auto se = eo.isDsymbolExp()) + { + Dsymbol_visit(se.s); + } + } + } + } + } + + 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 != TOK.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(); +} |