1
/**
2
 * Flow analysis for Ownership/Borrowing
3
 *
4
 * Copyright:   Copyright (C) 1999-2019 by The D Language Foundation, All Rights Reserved
5
 * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
6
 * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
7
 * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/ob.d, _ob.d)
8
 * Documentation:  https://dlang.org/phobos/dmd_escape.html
9
 * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/ob.d
10
 */
11

12
module dmd.ob;
13

14
import core.stdc.stdio : printf;
15
import core.stdc.stdlib;
16
import core.stdc.string;
17

18
import dmd.root.array;
19
import dmd.root.rootobject;
20
import dmd.root.rmem;
21

22
import dmd.aggregate;
23
import dmd.apply;
24
import dmd.arraytypes;
25
import dmd.declaration;
26
import dmd.dscope;
27
import dmd.dsymbol;
28
import dmd.dtemplate;
29
import dmd.errors;
30
import dmd.escape;
31
import dmd.expression;
32
import dmd.foreachvar;
33
import dmd.func;
34
import dmd.globals;
35
import dmd.identifier;
36
import dmd.init;
37
import dmd.mtype;
38
import dmd.printast;
39
import dmd.statement;
40
import dmd.stmtstate;
41
import dmd.tokens;
42
import dmd.visitor;
43

44
import dmd.root.bitarray;
45
import dmd.root.outbuffer;
46

47
/**********************************
48
 * Perform ownership/borrowing checks for funcdecl.
49
 * Does not modify the AST, just checks for errors.
50
 */
51

52
void oblive(FuncDeclaration funcdecl)
53
{
54
    //printf("oblive() %s\n", funcdecl.toChars());
55
    //printf("fbody: %s\n", funcdecl.fbody.toChars());
56 1
    ObState obstate;
57

58
    /* Build the flow graph
59
     */
60 1
    setLabelStatementExtraFields(funcdecl.labtab);
61 1
    toObNodes(obstate.nodes, funcdecl.fbody);
62 1
    insertFinallyBlockCalls(obstate.nodes);
63 1
    insertFinallyBlockGotos(obstate.nodes);
64 1
    removeUnreachable(obstate.nodes);
65 1
    computePreds(obstate.nodes);
66

67 1
    numberNodes(obstate.nodes);
68
    //foreach (ob; obstate.nodes) ob.print();
69

70 1
    collectVars(funcdecl, obstate.vars);
71 1
    allocStates(obstate);
72 1
    doDataFlowAnalysis(obstate);
73

74 1
    checkObErrors(obstate);
75
}
76

77
alias ObNodes = Array!(ObNode*);
78

79
alias StmtState = dmd.stmtstate.StmtState!ObNode;
80

81
/*******************************************
82
 * Collect the state information.
83
 */
84
struct ObState
85
{
86
    ObNodes nodes;
87
    VarDeclarations vars;
88

89
    Array!size_t varStack;      /// temporary storage
90
    Array!bool mutableStack;    /// parallel to varStack[], is type mutable?
91

92
    PtrVarState[] varPool;      /// memory pool
93

94
    ~this()
95
    {
96 1
        mem.xfree(varPool.ptr);
97
    }
98
}
99

100
/***********************************************
101
 * A node in the function's expression graph, and its edges to predecessors and successors.
102
 */
103
struct ObNode
104
{
105
    Expression exp;     /// expression for the node
106
    ObNodes preds;      /// predecessors
107
    ObNodes succs;      /// successors
108
    ObNode* tryBlock;   /// try-finally block we're inside
109
    ObType obtype;
110
    uint index;         /// index of this in obnodes
111

112
    PtrVarState[] gen;    /// new states generated for this node
113
    PtrVarState[] input;  /// variable states on entry to exp
114
    PtrVarState[] output; /// variable states on exit to exp
115

116 1
    this(ObNode* tryBlock)
117
    {
118 1
        this.tryBlock = tryBlock;
119
    }
120

121
    void print()
122
    {
123 0
        printf("%d: %s %s\n", index, obtype.toString.ptr, exp ? exp.toChars() : "-");
124 0
        printf("  preds: ");
125 0
        foreach (ob; preds)
126 0
            printf(" %d", ob.index);
127 0
        printf("\n  succs: ");
128 0
        foreach (ob; succs)
129 0
            printf(" %d", ob.index);
130 0
        printf("\n\n");
131
    }
132
}
133

134

135
enum ObType : ubyte
136
{
137
    goto_,              /// goto one of the succs[]
138
    return_,            /// returns from function
139
    retexp,             /// returns expression from function
140
    throw_,             /// exits with throw
141
    exit,               /// exits program
142
    try_,
143
    finally_,
144
    fend,
145
}
146

147
string toString(ObType obtype)
148
{
149 0
    return obtype == ObType.goto_     ? "goto  "  :
150 0
           obtype == ObType.return_   ? "ret   "  :
151 0
           obtype == ObType.retexp    ? "retexp"  :
152 0
           obtype == ObType.throw_    ? "throw"   :
153 0
           obtype == ObType.exit      ? "exit"    :
154 0
           obtype == ObType.try_      ? "try"     :
155 0
           obtype == ObType.finally_  ? "finally" :
156 0
           obtype == ObType.fend      ? "fend"    :
157 0
           "---";
158
}
159

160
/***********
161
 Pointer variable states:
162

163
    Initial     state is not known; ignore for now
164

165
    Undefined   not in a usable state
166

167
                T* p = void;
168

169
    Owner       mutable pointer
170

171
                T* p = initializer;
172

173
    Borrowed    scope mutable pointer, borrowed from [p]
174

175
                T* p = initializer;
176
                scope T* b = p;
177

178
    Readonly    scope const pointer, copied from [p]
179

180
                T* p = initializer;
181
                scope const(T)* cp = p;
182

183
 Examples:
184

185
    T* p = initializer; // p is owner
186
    T** pp = &p;        // pp borrows from p
187

188
    T* p = initialize;  // p is owner
189
    T* q = p;           // transfer: q is owner, p is undefined
190
 */
191

192
enum PtrState : ubyte
193
{
194
    Initial, Undefined, Owner, Borrowed, Readonly
195
}
196

197
/************
198
 */
199
const(char)* toChars(PtrState state)
200
{
201 1
    return toString(state).ptr;
202
}
203

204
string toString(PtrState state)
205
{
206 1
    return ["Initial", "Undefined", "Owner", "Borrowed", "Readonly"][state];
207
}
208

209
/******
210
 * Carries the state of a pointer variable.
211
 */
212
struct PtrVarState
213
{
214
    BitArray deps;           /// dependencies
215
    PtrState state;          /// state the pointer variable is in
216

217
    void opAssign(const ref PtrVarState pvs)
218
    {
219 1
        state = pvs.state;
220 1
        deps = pvs.deps;
221
    }
222

223
    /* Combine `this` and `pvs` into `this`,
224
     * on the idea that the `this` and the `pvs` paths
225
     * are being merged
226
     * Params:
227
     *  pvs = path to be merged with `this`
228
     */
229
    void combine(ref PtrVarState pvs, size_t vi, PtrVarState[] gen)
230
    {
231 1
        static uint X(PtrState x1, PtrState x2) { return x1 * (PtrState.max + 1) + x2; }
232

233
        with (PtrState)
234
        {
235 1
            switch (X(state, pvs.state))
236
            {
237 0
                case X(Initial, Initial):
238 0
                    break;
239

240 0
                case X(Initial, Owner    ):
241 0
                case X(Initial, Borrowed ):
242 0
                case X(Initial, Readonly ):
243
                    // Transfer state to `this`
244 0
                    state = pvs.state;
245 0
                    deps = pvs.deps;
246 0
                    break;
247

248 1
                case X(Owner,    Initial):
249 1
                case X(Borrowed, Initial):
250 1
                case X(Readonly, Initial):
251 1
                    break;
252

253 0
                case X(Undefined, Initial):
254 0
                case X(Undefined, Undefined):
255 0
                case X(Undefined, Owner    ):
256 0
                case X(Undefined, Borrowed ):
257 0
                case X(Undefined, Readonly ):
258 0
                    break;
259

260 1
                case X(Owner    , Owner   ):
261 1
                    break;
262

263 0
                case X(Borrowed , Borrowed):
264 1
                case X(Readonly , Readonly):
265 1
                    deps.or(pvs.deps);
266 1
                    break;
267

268 1
                default:
269 1
                    makeUndefined(vi, gen);
270 1
                    break;
271
            }
272
        }
273
    }
274

275
    bool opEquals(const ref PtrVarState pvs) const
276
    {
277 1
        return state == pvs.state &&
278 1
                deps == pvs.deps;
279
    }
280

281
    /***********************
282
     */
283
    void print(VarDeclaration[] vars)
284
    {
285 0
        string s = toString(state);
286 0
        printf("%.*s [", cast(int)s.length, s.ptr);
287 0
        assert(vars.length == deps.length);
288 0
        OutBuffer buf;
289 0
        depsToBuf(buf, vars);
290 0
        string t = buf[];
291 0
        printf("%.*s]\n", cast(int)t.length, t.ptr);
292
    }
293

294
    /*****************************
295
     * Produce a user-readable comma separated string of the
296
     * dependencies.
297
     * Params:
298
     *  buf = write resulting string here
299
     *  vars = array from which to get the variable names
300
     */
301
    void depsToBuf(ref OutBuffer buf, const VarDeclaration[] vars)
302
    {
303 0
        bool any = false;
304 0
        foreach (i; 0 .. deps.length)
305
        {
306 0
            if (deps[i])
307
            {
308 0
                if (any)
309 0
                    buf.writestring(", ");
310 0
                buf.writestring(vars[i].toString());
311 0
                any = true;
312
            }
313
        }
314
    }
315
}
316

317

318
/*****************************************
319
 * Set the `.extra` field for LabelStatements in labtab[].
320
 */
321
void setLabelStatementExtraFields(DsymbolTable labtab)
322
{
323 1
    if (labtab)
324 0
        foreach (keyValue; labtab.tab.asRange)
325
        {
326
            //printf("  KV: %s = %s\n", keyValue.key.toChars(), keyValue.value.toChars());
327 0
            auto label = cast(LabelDsymbol)keyValue.value;
328 0
            if (label.statement)
329 0
                label.statement.extra = cast(void*) new ObNode(null);
330
        }
331
}
332

333
/*****************************************
334
 * Convert statement into ObNodes.
335
 */
336

337
void toObNodes(ref ObNodes obnodes, Statement s)
338
{
339 1
    ObNode* curblock = new ObNode(null);
340 1
    obnodes.push(curblock);
341

342
    void visit(Statement s, StmtState* stmtstate)
343
    {
344 1
        if (!s)
345 1
            return;
346

347
        ObNode* newNode()
348
        {
349 1
            return new ObNode(stmtstate.tryBlock);
350
        }
351

352
        ObNode* nextNodeIs(ObNode* ob)
353
        {
354 1
            obnodes.push(ob);
355 1
            curblock = ob;
356 1
            return ob;
357
        }
358

359
        ObNode* nextNode()
360
        {
361 1
            return nextNodeIs(newNode());
362
        }
363

364
        ObNode* gotoNextNodeIs(ObNode* ob)
365
        {
366 1
            obnodes.push(ob);
367 1
            curblock.succs.push(ob);
368 1
            curblock = ob;
369 1
            return ob;
370
        }
371

372
        // block_goto(blx, BCgoto, null)
373
        ObNode* gotoNextNode()
374
        {
375 1
            return gotoNextNodeIs(newNode());
376
        }
377

378
        /***
379
         * Doing a goto to dest
380
         */
381
        ObNode* gotoDest(ObNode* dest)
382
        {
383 0
            curblock.succs.push(dest);
384 0
            return nextNode();
385
        }
386

387
        void visitExp(ExpStatement s)
388
        {
389 1
            curblock.obtype = ObType.goto_;
390 1
            curblock.exp = s.exp;
391 1
            gotoNextNode();
392
        }
393

394
        void visitDtorExp(DtorExpStatement s)
395
        {
396 0
            visitExp(s);
397
        }
398

399
        void visitCompound(CompoundStatement s)
400
        {
401 1
            if (s.statements)
402
            {
403 1
                foreach (s2; *s.statements)
404
                {
405 1
                    visit(s2, stmtstate);
406
                }
407
            }
408
        }
409

410
        void visitCompoundDeclaration(CompoundDeclarationStatement s)
411
        {
412 0
            visitCompound(s);
413
        }
414

415
        void visitUnrolledLoop(UnrolledLoopStatement s)
416
        {
417 0
            StmtState mystate = StmtState(stmtstate, s);
418 0
            mystate.breakBlock = newNode();
419

420 0
            gotoNextNode();
421

422 0
            foreach (s2; *s.statements)
423
            {
424 0
                if (s2)
425
                {
426 0
                    mystate.contBlock = newNode();
427

428 0
                    visit(s2, &mystate);
429

430 0
                    gotoNextNodeIs(mystate.contBlock);
431
                }
432
            }
433

434 0
            gotoNextNodeIs(mystate.breakBlock);
435
        }
436

437
        void visitScope(ScopeStatement s)
438
        {
439 1
            if (s.statement)
440
            {
441 1
                StmtState mystate = StmtState(stmtstate, s);
442

443 1
                if (mystate.prev.ident)
444 0
                    mystate.ident = mystate.prev.ident;
445

446 1
                visit(s.statement, &mystate);
447

448 1
                if (mystate.breakBlock)
449 0
                    gotoNextNodeIs(mystate.breakBlock);
450
            }
451
        }
452

453
        void visitDo(DoStatement s)
454
        {
455 0
            StmtState mystate = StmtState(stmtstate, s);
456 0
            mystate.breakBlock = newNode();
457 0
            mystate.contBlock = newNode();
458

459 0
            auto bpre = curblock;
460

461 0
            auto ob = newNode();
462 0
            obnodes.push(ob);
463 0
            curblock.succs.push(ob);
464 0
            curblock = ob;
465 0
            bpre.succs.push(curblock);
466

467 0
            mystate.contBlock.succs.push(curblock);
468 0
            mystate.contBlock.succs.push(mystate.breakBlock);
469

470 0
            visit(s._body, &mystate);
471

472 0
            gotoNextNodeIs(mystate.contBlock);
473 0
            mystate.contBlock.exp = s.condition;
474 0
            nextNodeIs(mystate.breakBlock);
475
        }
476

477
        void visitFor(ForStatement s)
478
        {
479
            //printf("visit(ForStatement)) %u..%u\n", s.loc.linnum, s.endloc.linnum);
480 1
            StmtState mystate = StmtState(stmtstate, s);
481 1
            mystate.breakBlock = newNode();
482 1
            mystate.contBlock = newNode();
483

484 1
            visit(s._init, &mystate);
485

486 1
            auto bcond = gotoNextNode();
487 1
            mystate.contBlock.succs.push(bcond);
488

489 1
            if (s.condition)
490
            {
491 1
                bcond.exp = s.condition;
492 1
                auto ob = newNode();
493 1
                obnodes.push(ob);
494 1
                bcond.succs.push(ob);
495 1
                bcond.succs.push(mystate.breakBlock);
496 1
                curblock = ob;
497
            }
498
            else
499
            {   /* No conditional, it's a straight goto
500
                 */
501 0
                bcond.exp = s.condition;
502 0
                bcond.succs.push(nextNode());
503
            }
504

505 1
            visit(s._body, &mystate);
506
            /* End of the body goes to the continue block
507
             */
508 1
            curblock.succs.push(mystate.contBlock);
509 1
            nextNodeIs(mystate.contBlock);
510

511 1
            if (s.increment)
512 1
                curblock.exp = s.increment;
513

514
            /* The 'break' block follows the for statement.
515
             */
516 1
            nextNodeIs(mystate.breakBlock);
517
        }
518

519
        void visitIf(IfStatement s)
520
        {
521 1
            StmtState mystate = StmtState(stmtstate, s);
522

523
            // bexit is the block that gets control after this IfStatement is done
524 1
            auto bexit = mystate.breakBlock ? mystate.breakBlock : newNode();
525

526 1
            curblock.exp = s.condition;
527

528 1
            auto bcond = curblock;
529 1
            gotoNextNode();
530

531 1
            visit(s.ifbody, &mystate);
532 1
            curblock.succs.push(bexit);
533

534 1
            if (s.elsebody)
535
            {
536 1
                bcond.succs.push(nextNode());
537

538 1
                visit(s.elsebody, &mystate);
539

540 1
                gotoNextNodeIs(bexit);
541
            }
542
            else
543
            {
544 0
                bcond.succs.push(bexit);
545 0
                nextNodeIs(bexit);
546
            }
547
        }
548

549
        void visitSwitch(SwitchStatement s)
550
        {
551 0
            StmtState mystate = StmtState(stmtstate, s);
552

553 0
            mystate.switchBlock = curblock;
554

555
            /* Block for where "break" goes to
556
             */
557 0
            mystate.breakBlock = newNode();
558

559
            /* Block for where "default" goes to.
560
             * If there is a default statement, then that is where default goes.
561
             * If not, then do:
562
             *   default: break;
563
             * by making the default block the same as the break block.
564
             */
565 0
            mystate.defaultBlock = s.sdefault ? newNode() : mystate.breakBlock;
566

567 0
            const numcases = s.cases ? s.cases.dim : 0;
568

569
            /* allocate a block for each case
570
             */
571 0
            if (numcases)
572 0
                foreach (cs; *s.cases)
573
                {
574 0
                    cs.extra = cast(void*)newNode();
575
                }
576

577 0
            curblock.exp = s.condition;
578

579 0
            if (s.hasVars)
580
            {   /* Generate a sequence of if-then-else blocks for the cases.
581
                 */
582 0
                if (numcases)
583 0
                    foreach (cs; *s.cases)
584
                    {
585 0
                        auto ecase = newNode();
586 0
                        obnodes.push(ecase);
587 0
                        ecase.exp = cs.exp;
588 0
                        curblock.succs.push(ecase);
589

590 0
                        auto cn = cast(ObNode*)cs.extra;
591 0
                        ecase.succs.push(cn);
592 0
                        ecase.succs.push(nextNode());
593
                    }
594

595
                /* The final 'else' clause goes to the default
596
                 */
597 0
                curblock.succs.push(mystate.defaultBlock);
598 0
                nextNode();
599

600 0
                visit(s._body, &mystate);
601

602
                /* Have the end of the switch body fall through to the block
603
                 * following the switch statement.
604
                 */
605 0
                gotoNextNodeIs(mystate.breakBlock);
606 0
                return;
607
            }
608

609 0
            auto ob = newNode();
610 0
            obnodes.push(ob);
611 0
            curblock = ob;
612

613 0
            mystate.switchBlock.succs.push(mystate.defaultBlock);
614

615 0
            visit(s._body, &mystate);
616

617
            /* Have the end of the switch body fall through to the block
618
             * following the switch statement.
619
             */
620 0
            gotoNextNodeIs(mystate.breakBlock);
621
        }
622

623
        void visitCase(CaseStatement s)
624
        {
625 0
            auto cb = cast(ObNode*)s.extra;
626 0
            cb.tryBlock = stmtstate.tryBlock;
627 0
            auto bsw = stmtstate.getSwitchBlock();
628 0
            bsw.succs.push(cb);
629 0
            gotoNextNodeIs(cb);
630

631 0
            visit(s.statement, stmtstate);
632
        }
633

634
        void visitDefault(DefaultStatement s)
635
        {
636 0
            auto bdefault = stmtstate.getDefaultBlock;
637 0
            bdefault.tryBlock = stmtstate.tryBlock;
638 0
            gotoNextNodeIs(bdefault);
639 0
            visit(s.statement, stmtstate);
640
        }
641

642
        void visitGotoDefault(GotoDefaultStatement s)
643
        {
644 0
            gotoDest(stmtstate.getDefaultBlock);
645
        }
646

647
        void visitGotoCase(GotoCaseStatement s)
648
        {
649 0
            gotoDest(cast(ObNode*)s.cs.extra);
650
        }
651

652
        void visitSwitchError(SwitchErrorStatement s)
653
        {
654 0
            curblock.obtype = ObType.throw_;
655 0
            curblock.exp = s.exp;
656

657 0
            nextNode();
658
        }
659

660
        void visitReturn(ReturnStatement s)
661
        {
662
            //printf("visitReturn() %s\n", s.toChars());
663 1
            curblock.obtype = s.exp && s.exp.type.toBasetype().ty != Tvoid
664 1
                        ? ObType.retexp
665 0
                        : ObType.return_;
666 1
            curblock.exp = s.exp;
667

668 1
            nextNode();
669
        }
670

671
        void visitBreak(BreakStatement s)
672
        {
673 0
            gotoDest(stmtstate.getBreakBlock(s.ident));
674
        }
675

676
        void visitContinue(ContinueStatement s)
677
        {
678 0
            gotoDest(stmtstate.getContBlock(s.ident));
679
        }
680

681
        void visitWith(WithStatement s)
682
        {
683 0
            visit(s._body, stmtstate);
684
        }
685

686
        void visitTryCatch(TryCatchStatement s)
687
        {
688
            /* tryblock
689
             * body
690
             * breakBlock
691
             * catches
692
             * breakBlock2
693
             */
694

695 0
            StmtState mystate = StmtState(stmtstate, s);
696 0
            mystate.breakBlock = newNode();
697

698 0
            auto tryblock = gotoNextNode();
699

700 0
            visit(s._body, &mystate);
701

702 0
            gotoNextNodeIs(mystate.breakBlock);
703

704
            // create new break block that follows all the catches
705 0
            auto breakBlock2 = newNode();
706

707 0
            gotoDest(breakBlock2);
708

709 0
            foreach (cs; *s.catches)
710
            {
711
                /* Each catch block is a successor to tryblock
712
                 * and the last block of try body
713
                 */
714 0
                StmtState catchState = StmtState(stmtstate, s);
715

716 0
                auto bcatch = curblock;
717 0
                tryblock.succs.push(bcatch);
718 0
                mystate.breakBlock.succs.push(bcatch);
719

720 0
                nextNode();
721

722 0
                visit(cs.handler, &catchState);
723

724 0
                gotoDest(breakBlock2);
725
            }
726

727 0
            curblock.succs.push(breakBlock2);
728 0
            obnodes.push(breakBlock2);
729 0
            curblock = breakBlock2;
730
        }
731

732
        void visitTryFinally(TryFinallyStatement s)
733
        {
734
            /* Build this:
735
             *  1  goto     [2]
736
             *  2  try_     [3] [5] [7]
737
             *  3  body
738
             *  4  goto     [8]
739
             *  5  finally_ [6]
740
             *  6  finalbody
741
             *  7  fend     [8]
742
             *  8  lastblock
743
             */
744

745 0
            StmtState bodyState = StmtState(stmtstate, s);
746

747 0
            auto b2 = gotoNextNode();
748 0
            b2.obtype = ObType.try_;
749 0
            bodyState.tryBlock = b2;
750

751 0
            gotoNextNode();
752

753 0
            visit(s._body, &bodyState);
754

755 0
            auto b4 = gotoNextNode();
756

757 0
            auto b5 = newNode();
758 0
            b5.obtype = ObType.finally_;
759 0
            nextNodeIs(b5);
760 0
            gotoNextNode();
761

762 0
            StmtState finallyState = StmtState(stmtstate, s);
763 0
            visit(s.finalbody, &finallyState);
764

765 0
            auto b7 = gotoNextNode();
766 0
            b7.obtype = ObType.fend;
767

768 0
            auto b8 = gotoNextNode();
769

770 0
            b2.succs.push(b5);
771 0
            b2.succs.push(b7);
772

773 0
            b4.succs.push(b8);
774
        }
775

776
        void visitThrow(ThrowStatement s)
777
        {
778 1
            curblock.obtype = ObType.throw_;
779 1
            curblock.exp = s.exp;
780 1
            nextNode();
781
        }
782

783
        void visitGoto(GotoStatement s)
784
        {
785 0
            gotoDest(cast(ObNode*)s.label.statement.extra);
786
        }
787

788
        void visitLabel(LabelStatement s)
789
        {
790 0
            StmtState mystate = StmtState(stmtstate, s);
791 0
            mystate.ident = s.ident;
792

793 0
            auto ob = cast(ObNode*)s.extra;
794 0
            ob.tryBlock = mystate.tryBlock;
795 0
            visit(s.statement, &mystate);
796
        }
797

798 1
        final switch (s.stmt)
799
        {
800 1
            case STMT.Exp:                 visitExp(s.isExpStatement()); break;
801 0
            case STMT.DtorExp:             visitDtorExp(s.isDtorExpStatement()); break;
802 1
            case STMT.Compound:            visitCompound(s.isCompoundStatement()); break;
803 0
            case STMT.CompoundDeclaration: visitCompoundDeclaration(s.isCompoundDeclarationStatement()); break;
804 0
            case STMT.UnrolledLoop:        visitUnrolledLoop(s.isUnrolledLoopStatement()); break;
805 1
            case STMT.Scope:               visitScope(s.isScopeStatement()); break;
806 0
            case STMT.Do:                  visitDo(s.isDoStatement()); break;
807 1
            case STMT.For:                 visitFor(s.isForStatement()); break;
808 1
            case STMT.If:                  visitIf(s.isIfStatement()); break;
809 0
            case STMT.Switch:              visitSwitch(s.isSwitchStatement()); break;
810 0
            case STMT.Case:                visitCase(s.isCaseStatement()); break;
811 0
            case STMT.Default:             visitDefault(s.isDefaultStatement()); break;
812 0
            case STMT.GotoDefault:         visitGotoDefault(s.isGotoDefaultStatement()); break;
813 0
            case STMT.GotoCase:            visitGotoCase(s.isGotoCaseStatement()); break;
814 0
            case STMT.SwitchError:         visitSwitchError(s.isSwitchErrorStatement()); break;
815 1
            case STMT.Return:              visitReturn(s.isReturnStatement()); break;
816 0
            case STMT.Break:               visitBreak(s.isBreakStatement()); break;
817 0
            case STMT.Continue:            visitContinue(s.isContinueStatement()); break;
818 0
            case STMT.With:                visitWith(s.isWithStatement()); break;
819 0
            case STMT.TryCatch:            visitTryCatch(s.isTryCatchStatement()); break;
820 0
            case STMT.TryFinally:          visitTryFinally(s.isTryFinallyStatement()); break;
821 1
            case STMT.Throw:               visitThrow(s.isThrowStatement()); break;
822 0
            case STMT.Goto:                visitGoto(s.isGotoStatement()); break;
823 0
            case STMT.Label:               visitLabel(s.isLabelStatement()); break;
824

825 0
            case STMT.CompoundAsm:
826 0
            case STMT.Asm:
827 0
            case STMT.InlineAsm:
828 0
            case STMT.GccAsm:
829

830 0
            case STMT.Pragma:
831 0
            case STMT.Import:
832 0
            case STMT.ScopeGuard:
833 0
            case STMT.Error:
834 0
                break;          // ignore these
835

836 0
            case STMT.Foreach:
837 0
            case STMT.ForeachRange:
838 0
            case STMT.Debug:
839 0
            case STMT.CaseRange:
840 0
            case STMT.StaticForeach:
841 0
            case STMT.StaticAssert:
842 0
            case STMT.Conditional:
843 0
            case STMT.While:
844 0
            case STMT.Forwarding:
845 0
            case STMT.Compile:
846 0
            case STMT.Peel:
847 0
            case STMT.Synchronized:
848 0
                debug printf("s: %s\n", s.toChars());
849 0
                assert(0);              // should have been rewritten
850
        }
851
    }
852

853 1
    StmtState stmtstate;
854 1
    visit(s, &stmtstate);
855 1
    curblock.obtype = ObType.return_;
856

857
    static if (0)
858
    {
859
        printf("toObNodes()\n");
860
        printf("------- before ----------\n");
861
        numberNodes(obnodes);
862
        foreach (ob; obnodes) ob.print();
863
        printf("-------------------------\n");
864
    }
865

866 1
    assert(stmtstate.breakBlock is null);
867 1
    assert(stmtstate.contBlock is null);
868 1
    assert(stmtstate.switchBlock is null);
869 1
    assert(stmtstate.defaultBlock is null);
870 1
    assert(stmtstate.tryBlock is null);
871
}
872

873
/***************************************************
874
 * Insert finally block calls when doing a goto from
875
 * inside a try block to outside.
876
 * Done after blocks are generated because then we know all
877
 * the edges of the graph, but before the pred's are computed.
878
 * Params:
879
 *      obnodes = graph of the function
880
 */
881

882
void insertFinallyBlockCalls(ref ObNodes obnodes)
883
{
884 1
    ObNode* bcret = null;
885 1
    ObNode* bcretexp = null;
886

887
    enum log = false;
888

889
    static if (log)
890
    {
891
        printf("insertFinallyBlockCalls()\n");
892
        printf("------- before ----------\n");
893
        numberNodes(obnodes);
894
        foreach (ob; obnodes) ob.print();
895
        printf("-------------------------\n");
896
    }
897

898 1
    foreach (ob; obnodes)
899
    {
900 1
        if (!ob.tryBlock)
901 1
            continue;
902

903 0
        switch (ob.obtype)
904
        {
905 0
            case ObType.return_:
906
                // Rewrite into a ObType.goto_ => ObType.return_
907 0
                if (!bcret)
908
                {
909 0
                    bcret = new ObNode();
910 0
                    bcret.obtype = ob.obtype;
911
                }
912 0
                ob.obtype = ObType.goto_;
913 0
                ob.succs.push(bcret);
914 0
                goto case_goto;
915

916 0
            case ObType.retexp:
917
                // Rewrite into a ObType.goto_ => ObType.retexp
918 0
                if (!bcretexp)
919
                {
920 0
                    bcretexp = new ObNode();
921 0
                    bcretexp.obtype = ob.obtype;
922
                }
923 0
                ob.obtype = ObType.goto_;
924 0
                ob.succs.push(bcretexp);
925 0
                goto case_goto;
926

927 0
            case ObType.goto_:
928 0
                if (ob.succs.length != 1)
929 0
                    break;
930

931
            case_goto:
932
            {
933 0
                auto target = ob.succs[0];              // destination of goto
934 0
                ob.succs.setDim(0);
935 0
                auto lasttry = target.tryBlock;
936 0
                auto blast = ob;
937 0
                for (auto bt = ob.tryBlock; bt != lasttry; bt = bt.tryBlock)
938
                {
939 0
                    assert(bt.obtype == ObType.try_);
940 0
                    auto bf = bt.succs[1];
941 0
                    assert(bf.obtype == ObType.finally_);
942 0
                    auto bfend = bt.succs[2];
943 0
                    assert(bfend.obtype == ObType.fend);
944

945 0
                    if (!blast.succs.contains(bf.succs[0]))
946 0
                        blast.succs.push(bf.succs[0]);
947

948 0
                    blast = bfend;
949
                }
950 0
                if (!blast.succs.contains(target))
951 0
                    blast.succs.push(target);
952

953 0
                break;
954
            }
955

956 0
            default:
957 0
                break;
958
        }
959
    }
960 1
    if (bcret)
961 0
        obnodes.push(bcret);
962 1
    if (bcretexp)
963 0
        obnodes.push(bcretexp);
964

965
    static if (log)
966
    {
967
        printf("------- after ----------\n");
968
        numberNodes(obnodes);
969
        foreach (ob; obnodes) ob.print();
970
        printf("-------------------------\n");
971
    }
972
}
973

974
/***************************************************
975
 * Remove try-finally scaffolding.
976
 * Params:
977
 *      obnodes = nodes for the function
978
 */
979

980
void insertFinallyBlockGotos(ref ObNodes obnodes)
981
{
982
    /* Remove all the try_, finally_, lpad and ret nodes.
983
     * Actually, just make them into no-ops.
984
     */
985 1
    foreach (ob; obnodes)
986
    {
987 1
        ob.tryBlock = null;
988 1
        switch (ob.obtype)
989
        {
990 0
            case ObType.try_:
991 0
                ob.obtype = ObType.goto_;
992 0
                ob.succs.remove(2);     // remove fend
993 0
                ob.succs.remove(1);     // remove finally_
994 0
                break;
995

996 0
            case ObType.finally_:
997 0
                ob.obtype = ObType.goto_;
998 0
                break;
999

1000 0
            case ObType.fend:
1001 0
                ob.obtype = ObType.goto_;
1002 0
                break;
1003

1004 1
            default:
1005 1
                break;
1006
        }
1007
    }
1008
}
1009

1010
/*********************************
1011
 * Set the `index` field of each ObNode
1012
 * to its index in the `obnodes[]` array.
1013
 */
1014
void numberNodes(ref ObNodes obnodes)
1015
{
1016
    //printf("numberNodes()\n");
1017 1
    foreach (i, ob; obnodes)
1018
    {
1019
        //printf("ob = %d, %p\n", i, ob);
1020 1
        ob.index = cast(uint)i;
1021
    }
1022

1023
    // Verify that nodes do not appear more than once in obnodes[]
1024
    debug
1025 1
    foreach (i, ob; obnodes)
1026
    {
1027 1
        assert(ob.index == cast(uint)i);
1028
    }
1029
}
1030

1031

1032
/*********************************
1033
 * Remove unreachable nodes and compress
1034
 * them out of obnodes[].
1035
 * Params:
1036
 *      obnodes = array of nodes
1037
 */
1038
void removeUnreachable(ref ObNodes obnodes)
1039
{
1040 1
    if (!obnodes.length)
1041 0
        return;
1042

1043
    /* Mark all nodes as unreachable,
1044
     * temporarilly reusing ObNode.index
1045
     */
1046 1
    foreach (ob; obnodes)
1047 1
        ob.index = 0;
1048

1049
    /* Recursively mark ob and all its successors as reachable
1050
     */
1051
    static void mark(ObNode* ob)
1052
    {
1053 1
        ob.index = 1;
1054 1
        foreach (succ; ob.succs)
1055
        {
1056 1
            if (!succ.index)
1057 1
                mark(succ);
1058
        }
1059
    }
1060

1061 1
    mark(obnodes[0]);   // first node is entry point
1062

1063
    /* Remove unreachable nodes by shifting the remainder left
1064
     */
1065 1
    size_t j = 1;
1066 1
    foreach (i; 1 .. obnodes.length)
1067
    {
1068 1
        if (obnodes[i].index)
1069
        {
1070 1
            if (i != j)
1071 0
                obnodes[j] = obnodes[i];
1072 1
            ++j;
1073
        }
1074
        else
1075
        {
1076 1
            obnodes[i].destroy();
1077
        }
1078
    }
1079 1
    obnodes.setDim(j);
1080
}
1081

1082

1083

1084
/*************************************
1085
 * Compute predecessors.
1086
 */
1087
void computePreds(ref ObNodes obnodes)
1088
{
1089 1
    foreach (ob; obnodes)
1090
    {
1091 1
        foreach (succ; ob.succs)
1092
        {
1093 1
            succ.preds.push(ob);
1094
        }
1095
    }
1096
}
1097

1098
/*******************************
1099
 * Are we interested in tracking variable `v`?
1100
 */
1101
bool isTrackableVar(VarDeclaration v)
1102
{
1103
    //printf("isTrackableVar() %s\n", v.toChars());
1104 1
    auto tb = v.type.toBasetype();
1105

1106
    /* Assume class references are managed by the GC,
1107
     * don't need to track them
1108
     */
1109 1
    if (tb.ty == Tclass)
1110 1
        return false;
1111

1112
    /* Assume types with a destructor are doing their own tracking,
1113
     * such as being a ref counted type
1114
     */
1115 1
    if (v.needsScopeDtor())
1116 0
        return false;
1117

1118
    /* Not tracking function parameters that are not mutable
1119
     */
1120 1
    if (v.storage_class & STC.parameter && !tb.hasPointersToMutableFields())
1121 1
        return false;
1122

1123
    /* Not tracking global variables
1124
     */
1125 1
    return !v.isDataseg();
1126
}
1127

1128
/*******************************
1129
 * Are we interested in tracking this expression?
1130
 * Returns:
1131
 *      variable if so, null if not
1132
 */
1133
VarDeclaration isTrackableVarExp(Expression e)
1134
{
1135 0
    if (auto ve = e.isVarExp())
1136
    {
1137 0
        if (auto v = ve.var.isVarDeclaration())
1138 0
            if (isTrackableVar(v))
1139 0
                return v;
1140
    }
1141 0
    return null;
1142
}
1143

1144

1145
/**************
1146
 * Find the pointer variable declarations in this function,
1147
 * and fill `vars` with them.
1148
 * Params:
1149
 *      funcdecl = function we are in
1150
 *      vars = array to fill in
1151
 */
1152
void collectVars(FuncDeclaration funcdecl, out VarDeclarations vars)
1153
{
1154
    enum log = false;
1155 1
    if (log)
1156 0
        printf("----------------collectVars()---------------\n");
1157

1158 1
    if (funcdecl.parameters)
1159 1
        foreach (v; (*funcdecl.parameters)[])
1160
        {
1161 1
            if (isTrackableVar(v))
1162 1
                vars.push(v);
1163
        }
1164

1165
    void dgVar(VarDeclaration v)
1166
    {
1167 1
        if (isTrackableVar(v))
1168 1
            vars.push(v);
1169
    }
1170

1171
    void dgExp(Expression e)
1172
    {
1173 1
        foreachVar(e, &dgVar);
1174
    }
1175

1176 1
    foreachExpAndVar(funcdecl.fbody, &dgExp, &dgVar);
1177

1178
    static if (log)
1179
    {
1180
        foreach (i, v; vars[])
1181
        {
1182
            printf("vars[%d] = %s\n", cast(int)i, v.toChars());
1183
        }
1184
    }
1185
}
1186

1187
/***********************************
1188
 * Allocate BitArrays in PtrVarState.
1189
 * Can be allocated much more efficiently by subdividing a single
1190
 * large array of bits
1191
 */
1192
void allocDeps(PtrVarState[] pvss)
1193
{
1194
    //printf("allocDeps()\n");
1195 1
    foreach (ref pvs; pvss)
1196
    {
1197 1
        pvs.deps.length = pvss.length;
1198
    }
1199
}
1200

1201

1202
/**************************************
1203
 * Allocate state variables foreach node.
1204
 */
1205
void allocStates(ref ObState obstate)
1206
{
1207
    //printf("---------------allocStates()------------------\n");
1208 1
    const vlen = obstate.vars.length;
1209 1
    PtrVarState* p = cast(PtrVarState*) mem.xcalloc(obstate.nodes.length * 3 * vlen, PtrVarState.sizeof);
1210 1
    obstate.varPool = p[0 .. obstate.nodes.length * 3 * vlen];
1211 1
    foreach (i, ob; obstate.nodes)
1212
    {
1213
        //printf(" [%d]\n", cast(int)i);
1214
//        ob.kill.length = obstate.vars.length;
1215
//        ob.comb.length = obstate.vars.length;
1216 1
        ob.gen         = p[0 .. vlen]; p += vlen;
1217 1
        ob.input       = p[0 .. vlen]; p += vlen;
1218 1
        ob.output      = p[0 .. vlen]; p += vlen;
1219

1220 1
        allocDeps(ob.gen);
1221 1
        allocDeps(ob.input);
1222 1
        allocDeps(ob.output);
1223
    }
1224
}
1225

1226
/******************************
1227
 * Does v meet the definiton of a `Borrowed` pointer?
1228
 * Returns:
1229
 *      true if it does
1230
 */
1231
bool isBorrowedPtr(VarDeclaration v)
1232
{
1233 1
    return v.isScope() && !v.isowner && v.type.nextOf().isMutable();
1234
}
1235

1236
/******************************
1237
 * Does v meet the definiton of a `Readonly` pointer?
1238
 * Returns:
1239
 *      true if it does
1240
 */
1241
bool isReadonlyPtr(VarDeclaration v)
1242
{
1243 1
    return v.isScope() && !v.type.nextOf().isMutable();
1244
}
1245

1246
/***************************************
1247
 * Compute the gen vector for ob.
1248
 */
1249
void genKill(ref ObState obstate, ObNode* ob)
1250
{
1251
    enum log = false;
1252 1
    if (log)
1253 0
        printf("-----------computeGenKill()-----------\n");
1254

1255
    /***************
1256
     * Assigning result of expression `e` to variable `v`.
1257
     */
1258
    void dgWriteVar(ObNode* ob, VarDeclaration v, Expression e, bool initializer)
1259
    {
1260 1
        if (log)
1261 0
            printf("dgWriteVar() %s := %s %d\n", v.toChars(), e.toChars(), initializer);
1262 1
        const vi = obstate.vars.find(v);
1263 1
        assert(vi != size_t.max);
1264 1
        PtrVarState* pvs = &ob.gen[vi];
1265 1
        readVar(ob, vi, true, ob.gen);
1266 1
        if (e)
1267
        {
1268 1
            if (isBorrowedPtr(v))
1269 1
                pvs.state = PtrState.Borrowed;
1270 1
            else if (isReadonlyPtr(v))
1271 1
                pvs.state = PtrState.Readonly;
1272
            else
1273 1
                pvs.state = PtrState.Owner;
1274 1
            pvs.deps.zero();
1275

1276 1
            EscapeByResults er;
1277 1
            escapeByValue(e, &er, true);
1278 1
            bool any = false;           // if any variables are assigned to v
1279

1280
            void by(VarDeclaration r)
1281
            {
1282 1
                const ri = obstate.vars.find(r);
1283 1
                if (ri != size_t.max && ri != vi)
1284
                {
1285 1
                    pvs.deps[ri] = true;         // v took from r
1286 1
                    auto pvsr = &ob.gen[ri];
1287 1
                    any = true;
1288

1289 1
                    if (isBorrowedPtr(v))
1290
                    {
1291
                        // v is borrowing from r
1292 1
                        pvs.state = PtrState.Borrowed;
1293
                    }
1294 1
                    else if (isReadonlyPtr(v))
1295
                    {
1296 1
                        pvs.state = PtrState.Readonly;
1297
                    }
1298
                    else
1299
                    {
1300
                        // move r to v, which "consumes" r
1301 1
                        pvsr.state = PtrState.Undefined;
1302 1
                        pvsr.deps.zero();
1303
                    }
1304
                }
1305
            }
1306

1307 1
            foreach (VarDeclaration v2; er.byvalue)
1308 1
                by(v2);
1309 1
            foreach (VarDeclaration v2; er.byref)
1310 1
                by(v2);
1311

1312
            /* Make v an Owner for initializations like:
1313
             *    scope v = malloc();
1314
             */
1315 1
            if (initializer && !any && isBorrowedPtr(v))
1316
            {
1317 1
                v.isowner = true;
1318 1
                pvs.state = PtrState.Owner;
1319
            }
1320
        }
1321
        else
1322
        {
1323 0
            if (isBorrowedPtr(v))
1324 0
                pvs.state = PtrState.Borrowed;
1325 0
            else if (isReadonlyPtr(v))
1326 0
                pvs.state = PtrState.Readonly;
1327
            else
1328 0
                pvs.state = PtrState.Owner;
1329 0
            pvs.deps.zero();
1330
        }
1331
    }
1332

1333
    void dgReadVar(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable)
1334
    {
1335 1
        if (log)
1336 0
            printf("dgReadVar() %s %d\n", v.toChars(), mutable);
1337 1
        const vi = obstate.vars.find(v);
1338 1
        assert(vi != size_t.max);
1339 1
        readVar(ob, vi, mutable, ob.gen);
1340
    }
1341

1342
    void foreachExp(ObNode* ob, Expression e)
1343
    {
1344
        extern (C++) final class ExpWalker : Visitor
1345
        {
1346
            alias visit = typeof(super).visit;
1347
            extern (D) void delegate(ObNode*, VarDeclaration, Expression, bool) dgWriteVar;
1348
            extern (D) void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) dgReadVar;
1349
            ObNode* ob;
1350
            ObState* obstate;
1351

1352 1
            extern (D) this(void delegate(ObNode*, VarDeclaration, Expression, bool) dgWriteVar,
1353
                            void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable) dgReadVar,
1354
                            ObNode* ob, ref ObState obstate)
1355
            {
1356 1
                this.dgWriteVar = dgWriteVar;
1357 1
                this.dgReadVar  = dgReadVar;
1358 1
                this.ob = ob;
1359 1
                this.obstate = &obstate;
1360
            }
1361

1362
            override void visit(Expression e)
1363
            {
1364
                //printf("[%s] %s: %s\n", e.loc.toChars(), Token.toChars(e.op), e.toChars());
1365
                //assert(0);
1366
            }
1367

1368
            void visitAssign(AssignExp ae, bool initializer)
1369
            {
1370 1
                ae.e2.accept(this);
1371 1
                if (auto ve = ae.e1.isVarExp())
1372
                {
1373 1
                    if (auto v = ve.var.isVarDeclaration())
1374 1
                        if (isTrackableVar(v))
1375 1
                            dgWriteVar(ob, v, ae.e2, initializer);
1376
                }
1377
                else
1378 1
                    ae.e1.accept(this);
1379
            }
1380

1381
            override void visit(AssignExp ae)
1382
            {
1383 1
                visitAssign(ae, false);
1384
            }
1385

1386
            override void visit(DeclarationExp e)
1387
            {
1388
                void Dsymbol_visit(Dsymbol s)
1389
                {
1390 1
                    if (auto vd = s.isVarDeclaration())
1391
                    {
1392 1
                        s = s.toAlias();
1393 1
                        if (s != vd)
1394 0
                            return Dsymbol_visit(s);
1395 1
                        if (!isTrackableVar(vd))
1396 0
                            return;
1397

1398 1
                        if (!(vd._init && vd._init.isVoidInitializer()))
1399
                        {
1400 1
                            auto ei = vd._init ? vd._init.isExpInitializer() : null;
1401 1
                            if (ei)
1402 1
                                visitAssign(cast(AssignExp)ei.exp, true);
1403
                            else
1404 0
                                dgWriteVar(ob, vd, null, false);
1405
                        }
1406
                    }
1407 0
                    else if (auto td = s.isTupleDeclaration())
1408
                    {
1409 0
                        foreach (o; *td.objects)
1410
                        {
1411 0
                            if (auto eo = o.isExpression())
1412
                            {
1413 0
                                if (auto se = eo.isDsymbolExp())
1414
                                {
1415 0
                                    Dsymbol_visit(se.s);
1416
                                }
1417
                            }
1418
                        }
1419
                    }
1420
                }
1421

1422 1
                Dsymbol_visit(e.declaration);
1423
            }
1424

1425
            override void visit(VarExp ve)
1426
            {
1427
                //printf("VarExp: %s\n", ve.toChars());
1428 1
                if (auto v = ve.var.isVarDeclaration())
1429 1
                    if (isTrackableVar(v))
1430
                    {
1431 1
                        dgReadVar(ve.loc, ob, v, isMutableRef(ve.type));
1432
                    }
1433
            }
1434

1435
            override void visit(CallExp ce)
1436
            {
1437
                //printf("CallExp() %s\n", ce.toChars());
1438 1
                ce.e1.accept(this);
1439 1
                auto t = ce.e1.type.toBasetype();
1440 1
                auto tf = t.isTypeFunction();
1441 1
                if (!tf)
1442
                {
1443 0
                    assert(t.ty == Tdelegate);
1444 0
                    tf = t.nextOf().isTypeFunction();
1445 0
                    assert(tf);
1446
                }
1447

1448
                // j=1 if _arguments[] is first argument
1449 1
                const int j = tf.isDstyleVariadic();
1450 1
                bool hasOut;
1451 1
                const varStackSave = obstate.varStack.length;
1452

1453 1
                foreach (const i, arg; (*ce.arguments)[])
1454
                {
1455 1
                    if (i - j < tf.parameterList.length &&
1456 1
                        i >= j)
1457
                    {
1458 1
                        Parameter p = tf.parameterList[i - j];
1459 1
                        auto pt = p.type.toBasetype();
1460

1461 1
                        EscapeByResults er;
1462 1
                        escapeByValue(arg, &er, true);
1463

1464 1
                        if (!(p.storageClass & STC.out_ && arg.isVarExp()))
1465 1
                            arg.accept(this);
1466

1467
                        void by(VarDeclaration v)
1468
                        {
1469 1
                            if (!isTrackableVar(v))
1470 0
                                return;
1471

1472 1
                            const vi = obstate.vars.find(v);
1473 1
                            if (vi == size_t.max)
1474 0
                                return;
1475

1476 1
                            if (p.storageClass & STC.out_)
1477
                            {
1478
                                /// initialize
1479 0
                                hasOut = true;
1480 0
                                makeUndefined(vi, ob.gen);
1481
                            }
1482 1
                            else if (p.storageClass & STC.scope_)
1483
                            {
1484
                                // borrow
1485 1
                                obstate.varStack.push(vi);
1486 1
                                obstate.mutableStack.push(isMutableRef(pt));
1487
                            }
1488
                            else
1489
                            {
1490
                                // move (i.e. consume arg)
1491 1
                                makeUndefined(vi, ob.gen);
1492
                            }
1493
                        }
1494

1495 1
                        foreach (VarDeclaration v2; er.byvalue)
1496 1
                            by(v2);
1497 1
                        foreach (VarDeclaration v2; er.byref)
1498 0
                            by(v2);
1499
                    }
1500
                    else // variadic args
1501
                    {
1502 1
                        arg.accept(this);
1503

1504 1
                        EscapeByResults er;
1505 1
                        escapeByValue(arg, &er, true);
1506

1507
                        void byv(VarDeclaration v)
1508
                        {
1509 1
                            if (!isTrackableVar(v))
1510 0
                                return;
1511

1512 1
                            const vi = obstate.vars.find(v);
1513 1
                            if (vi == size_t.max)
1514 0
                                return;
1515

1516 1
                            if (tf.parameterList.stc & STC.scope_)
1517
                            {
1518
                                // borrow
1519 1
                                obstate.varStack.push(vi);
1520 1
                                obstate.mutableStack.push(isMutableRef(arg.type) &&
1521 1
                                        !(tf.parameterList.stc & (STC.const_ | STC.immutable_)));
1522
                            }
1523
                            else
1524
                                // move (i.e. consume arg)
1525 0
                                makeUndefined(vi, ob.gen);
1526
                        }
1527

1528 1
                        foreach (VarDeclaration v2; er.byvalue)
1529 1
                            byv(v2);
1530 1
                        foreach (VarDeclaration v2; er.byref)
1531 0
                            byv(v2);
1532
                    }
1533
                }
1534

1535
                /* Do a dummy 'read' of each variable passed to the function,
1536
                 * to detect O/B errors
1537
                 */
1538 1
                assert(obstate.varStack.length == obstate.mutableStack.length);
1539 1
                foreach (i; varStackSave .. obstate.varStack.length)
1540
                {
1541 1
                    const vi = obstate.varStack[i];
1542
                    // auto pvs = &ob.gen[vi];
1543 1
                    auto v = obstate.vars[vi];
1544
                    //if (pvs.state == PtrState.Undefined)
1545
                        //v.error(ce.loc, "is Undefined, cannot pass to function");
1546

1547 1
                    dgReadVar(ce.loc, ob, v, obstate.mutableStack[i]);
1548
                }
1549

1550
                /* Pop off stack all variables for this function call
1551
                 */
1552 1
                obstate.varStack.setDim(varStackSave);
1553 1
                obstate.mutableStack.setDim(varStackSave);
1554

1555 1
                if (hasOut)
1556
                    // Initialization of out's only happens after the function call
1557 0
                    foreach (const i, arg; (*ce.arguments)[])
1558
                    {
1559 0
                        if (i - j < tf.parameterList.length &&
1560 0
                            i >= j)
1561
                        {
1562 0
                            Parameter p = tf.parameterList[i - j];
1563 0
                            if (p.storageClass & STC.out_)
1564
                            {
1565 0
                                if (auto v = isTrackableVarExp(arg))
1566 0
                                    dgWriteVar(ob, v, null, true);
1567
                            }
1568
                        }
1569
                    }
1570
            }
1571

1572
            override void visit(SymOffExp e)
1573
            {
1574 1
                if (auto v = e.var.isVarDeclaration())
1575 1
                    if (isTrackableVar(v))
1576
                    {
1577 1
                        dgReadVar(e.loc, ob, v, isMutableRef(e.type));
1578
                    }
1579
            }
1580

1581
            override void visit(LogicalExp e)
1582
            {
1583 0
                e.e1.accept(this);
1584

1585 0
                const vlen = obstate.vars.length;
1586 0
                auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof);
1587 0
                PtrVarState[] gen1 = p[0 .. vlen];
1588 0
                foreach (i, ref pvs; gen1)
1589
                {
1590 0
                    pvs = ob.gen[i];
1591
                }
1592

1593 0
                e.e2.accept(this);
1594

1595
                // Merge gen1 into ob.gen
1596 0
                foreach (i; 0 .. vlen)
1597
                {
1598 0
                    ob.gen[i].combine(gen1[i], i, ob.gen);
1599
                }
1600

1601 0
                mem.xfree(p); // should free .deps too
1602
            }
1603

1604
            override void visit(CondExp e)
1605
            {
1606 0
                e.econd.accept(this);
1607

1608 0
                const vlen = obstate.vars.length;
1609 0
                auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof);
1610 0
                PtrVarState[] gen1 = p[0 .. vlen];
1611 0
                foreach (i, ref pvs; gen1)
1612
                {
1613 0
                    pvs = ob.gen[i];
1614
                }
1615

1616 0
                e.e1.accept(this);
1617

1618
                // Swap gen1 with ob.gen
1619 0
                foreach (i; 0 .. vlen)
1620
                {
1621 0
                    gen1[i].deps.swap(ob.gen[i].deps);
1622 0
                    const state = gen1[i].state;
1623 0
                    gen1[i].state = ob.gen[i].state;
1624 0
                    ob.gen[i].state = state;
1625
                }
1626

1627 0
                e.e2.accept(this);
1628

1629
                /* xxx1 is the state from expression e1, ob.xxx is the state from e2.
1630
                 * Merge xxx1 into ob.xxx to get the state from `e`.
1631
                 */
1632 0
                foreach (i; 0 .. vlen)
1633
                {
1634 0
                    ob.gen[i].combine(gen1[i], i, ob.gen);
1635
                }
1636

1637 0
                mem.xfree(p); // should free .deps too
1638
            }
1639

1640
            override void visit(AddrExp e)
1641
            {
1642
                /* Taking the address of struct literal is normally not
1643
                 * allowed, but CTFE can generate one out of a new expression,
1644
                 * but it'll be placed in static data so no need to check it.
1645
                 */
1646 0
                if (e.e1.op != TOK.structLiteral)
1647 0
                    e.e1.accept(this);
1648
            }
1649

1650
            override void visit(UnaExp e)
1651
            {
1652 1
                e.e1.accept(this);
1653
            }
1654

1655
            override void visit(BinExp e)
1656
            {
1657 1
                e.e1.accept(this);
1658 1
                e.e2.accept(this);
1659
            }
1660

1661
            override void visit(ArrayLiteralExp e)
1662
            {
1663 0
                Type tb = e.type.toBasetype();
1664 0
                if (tb.ty == Tsarray || tb.ty == Tarray)
1665
                {
1666 0
                    if (e.basis)
1667 0
                        e.basis.accept(this);
1668 0
                    foreach (el; *e.elements)
1669
                    {
1670 0
                        if (el)
1671 0
                            el.accept(this);
1672
                    }
1673
                }
1674
            }
1675

1676
            override void visit(StructLiteralExp e)
1677
            {
1678 0
                if (e.elements)
1679
                {
1680 0
                    foreach (ex; *e.elements)
1681
                    {
1682 0
                        if (ex)
1683 0
                            ex.accept(this);
1684
                    }
1685
                }
1686
            }
1687

1688
            override void visit(AssocArrayLiteralExp e)
1689
            {
1690 0
                if (e.keys)
1691
                {
1692 0
                    foreach (i, key; *e.keys)
1693
                    {
1694 0
                        if (key)
1695 0
                            key.accept(this);
1696 0
                        if (auto value = (*e.values)[i])
1697 0
                            value.accept(this);
1698
                    }
1699
                }
1700
            }
1701

1702
            override void visit(NewExp e)
1703
            {
1704 1
                if (e.arguments)
1705
                {
1706 1
                    foreach (ex; *e.arguments)
1707
                    {
1708 1
                        if (ex)
1709 1
                            ex.accept(this);
1710
                    }
1711
                }
1712
            }
1713

1714
            override void visit(SliceExp e)
1715
            {
1716 0
                e.e1.accept(this);
1717 0
                if (e.lwr)
1718 0
                    e.lwr.accept(this);
1719 0
                if (e.upr)
1720 0
                    e.upr.accept(this);
1721
            }
1722
        }
1723

1724 1
        if (e)
1725
        {
1726 1
            scope ExpWalker ew = new ExpWalker(&dgWriteVar, &dgReadVar, ob, obstate);
1727 1
            e.accept(ew);
1728
        }
1729
    }
1730

1731 1
    foreachExp(ob, ob.exp);
1732
}
1733

1734
/***************************************
1735
 * Determine the state of a variable based on
1736
 * its type and storage class.
1737
 */
1738
PtrState toPtrState(VarDeclaration v)
1739
{
1740
    /* pointer to mutable:        Owner
1741
     * pointer to mutable, scope: Borrowed
1742
     * pointer to const:          Owner
1743
     * pointer to const, scope:   Readonly
1744
     * ref:                       Borrowed
1745
     * const ref:                 Readonly
1746
     */
1747

1748 1
    auto t = v.type;
1749 1
    if (v.isRef())
1750
    {
1751 0
        return t.hasMutableFields() ? PtrState.Borrowed : PtrState.Readonly;
1752
    }
1753 1
    if (v.isScope())
1754
    {
1755 1
        return t.hasPointersToMutableFields() ? PtrState.Borrowed : PtrState.Readonly;
1756
    }
1757
    else
1758 1
        return PtrState.Owner;
1759
}
1760

1761
/**********************************
1762
 * Does type `t` contain any pointers to mutable?
1763
 */
1764
bool hasPointersToMutableFields(Type t)
1765
{
1766 1
    auto tb = t.toBasetype();
1767 1
    if (!tb.isMutable())
1768 1
        return false;
1769 1
    if (auto tsa = tb.isTypeSArray())
1770
    {
1771 1
        return tsa.nextOf().hasPointersToMutableFields();
1772
    }
1773 1
    if (auto ts = tb.isTypeStruct())
1774
    {
1775 1
        foreach (v; ts.sym.fields)
1776
        {
1777 1
            if (v.isRef())
1778
            {
1779 0
                if (v.type.hasMutableFields())
1780 0
                    return true;
1781
            }
1782 1
            else if (v.type.hasPointersToMutableFields())
1783 1
                return true;
1784
        }
1785 1
        return false;
1786
    }
1787 1
    auto tbn = tb.nextOf();
1788 1
    return tbn && tbn.hasMutableFields();
1789
}
1790

1791
/********************************
1792
 * Does type `t` have any mutable fields?
1793
 */
1794
bool hasMutableFields(Type t)
1795
{
1796 1
    auto tb = t.toBasetype();
1797 1
    if (!tb.isMutable())
1798 1
        return false;
1799 1
    if (auto tsa = tb.isTypeSArray())
1800
    {
1801 0
        return tsa.nextOf().hasMutableFields();
1802
    }
1803 1
    if (auto ts = tb.isTypeStruct())
1804
    {
1805 0
        foreach (v; ts.sym.fields)
1806
        {
1807 0
            if (v.type.hasMutableFields())
1808 0
                return true;
1809
        }
1810 0
        return false;
1811
    }
1812 1
    return true;
1813
}
1814

1815

1816

1817
/***************************************
1818
 * Do the data flow analysis (i.e. compute the input[]
1819
 * and output[] vectors for each ObNode).
1820
 */
1821
void doDataFlowAnalysis(ref ObState obstate)
1822
{
1823
    enum log = false;
1824 1
    if (log)
1825
    {
1826 0
        printf("-----------------doDataFlowAnalysis()-------------------------\n");
1827 0
        foreach (ob; obstate.nodes) ob.print();
1828 0
        printf("------------------------------------------\n");
1829
    }
1830

1831 1
    if (!obstate.nodes.length)
1832 0
        return;
1833

1834 1
    auto startnode = obstate.nodes[0];
1835 1
    assert(startnode.preds.length == 0);
1836

1837
    /* Set opening state `input[]` for first node
1838
     */
1839 1
    foreach (i, ref ps; startnode.input)
1840
    {
1841 1
        auto v = obstate.vars[i];
1842 1
        auto state = toPtrState(v);
1843 1
        if (v.isParameter())
1844
        {
1845 1
            if (v.isOut())
1846 0
                state = PtrState.Undefined;
1847
            else
1848 1
                state = PtrState.Owner;
1849
        }
1850
        else
1851 1
            state = PtrState.Undefined;
1852 1
        ps.state = state;
1853 1
        ps.deps.zero();
1854 1
        startnode.gen[i] = ps;
1855
    }
1856

1857
    /* Set all output[]s to Initial
1858
     */
1859 1
    foreach (ob; obstate.nodes[])
1860
    {
1861 1
        foreach (ref ps; ob.output)
1862
        {
1863 1
            ps.state = PtrState.Initial;
1864 1
            ps.deps.zero();
1865
        }
1866
    }
1867

1868 1
    const vlen = obstate.vars.length;
1869 1
    PtrVarState pvs;
1870 1
    pvs.deps.length = vlen;
1871 1
    int counter = 0;
1872 1
    bool changes;
1873
    do
1874
    {
1875 1
        changes = false;
1876 1
        assert(++counter <= 1000);      // should converge, but don't hang if it doesn't
1877 1
        foreach (ob; obstate.nodes[])
1878
        {
1879
            /* Construct ob.gen[] by combining the .output[]s of each ob.preds[]
1880
             * and set ob.input[] to the same state
1881
             */
1882 1
            if (ob != startnode)
1883
            {
1884 1
                assert(ob.preds.length);
1885

1886 1
                foreach (i; 0 .. vlen)
1887
                {
1888 1
                    ob.gen[i] = ob.preds[0].output[i];
1889
                }
1890

1891 1
                foreach (j; 1 .. ob.preds.length)
1892
                {
1893 1
                    foreach (i; 0 .. vlen)
1894
                    {
1895 1
                        ob.gen[i].combine(ob.preds[j].output[i], i, ob.gen);
1896
                    }
1897
                }
1898

1899
                /* Set ob.input[] to ob.gen[],
1900
                 * if any changes were made we'll have to do another iteration
1901
                 */
1902 1
                foreach (i; 0 .. vlen)
1903
                {
1904 1
                    if (ob.gen[i] != ob.input[i])
1905
                    {
1906 1
                        ob.input[i] = ob.gen[i];
1907 1
                        changes = true;
1908
                    }
1909
                }
1910
            }
1911

1912
            /* Compute gen[] for node ob
1913
             */
1914 1
            genKill(obstate, ob);
1915

1916 1
            foreach (i; 0 .. vlen)
1917
            {
1918 1
                if (ob.gen[i] != ob.output[i])
1919
                {
1920 1
                    ob.output[i] = ob.gen[i];
1921 1
                    changes = true;
1922
                }
1923
            }
1924
        }
1925 1
    } while (changes);
1926

1927
    static if (log)
1928
    {
1929
        foreach (obi, ob; obstate.nodes)
1930
        {
1931
            printf("%d: %s\n", obi, ob.exp ? ob.exp.toChars() : "".ptr);
1932
            printf("  input:\n");
1933
            foreach (i, ref pvs2; ob.input[])
1934
            {
1935
                printf("    %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]);
1936
            }
1937

1938
            printf("  gen:\n");
1939
            foreach (i, ref pvs2; ob.gen[])
1940
            {
1941
                printf("    %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]);
1942
            }
1943
            printf("  output:\n");
1944
            foreach (i, ref pvs2; ob.output[])
1945
            {
1946
                printf("    %s: ", obstate.vars[i].toChars()); pvs2.print(obstate.vars[]);
1947
            }
1948
        }
1949
        printf("\n");
1950
    }
1951
}
1952

1953

1954
/***************************************
1955
 * Check for Ownership/Borrowing errors.
1956
 */
1957
void checkObErrors(ref ObState obstate)
1958
{
1959
    enum log = false;
1960 1
    if (log)
1961 0
        printf("------------checkObErrors()----------\n");
1962

1963
    void dgWriteVar(ObNode* ob, PtrVarState[] cpvs, VarDeclaration v, Expression e)
1964
    {
1965 1
        if (log) printf("dgWriteVar(v:%s, e:%s)\n", v.toChars(), e ? e.toChars() : "null");
1966 1
        const vi = obstate.vars.find(v);
1967 1
        assert(vi != size_t.max);
1968 1
        PtrVarState* pvs = &cpvs[vi];
1969 1
        readVar(ob, vi, true, cpvs);
1970 1
        if (e)
1971
        {
1972 1
            if (isBorrowedPtr(v))
1973 1
                pvs.state = PtrState.Borrowed;
1974 1
            else if (isReadonlyPtr(v))
1975 1
                pvs.state = PtrState.Readonly;
1976
            else
1977 1
                pvs.state = PtrState.Owner;
1978 1
            pvs.deps.zero();
1979

1980 1
            EscapeByResults er;
1981 1
            escapeByValue(e, &er, true);
1982

1983
            void by(VarDeclaration r)   // `v` = `r`
1984
            {
1985
                //printf("  by(%s)\n", r.toChars());
1986 1
                const ri = obstate.vars.find(r);
1987 1
                if (ri == size_t.max)
1988 0
                    return;
1989

1990
                with (PtrState)
1991
                {
1992 1
                    pvs.deps[ri] = true;         // v took from r
1993 1
                    auto pvsr = &cpvs[ri];
1994

1995 1
                    if (pvsr.state == Undefined)
1996
                    {
1997 0
                        v.error(e.loc, "is reading from `%s` which is Undefined", r.toChars());
1998
                    }
1999 1
                    else if (isBorrowedPtr(v))  // v is going to borrow from r
2000
                    {
2001 1
                        if (pvsr.state == Readonly)
2002 0
                            v.error(e.loc, "is borrowing from `%s` which is Readonly", r.toChars());
2003

2004 1
                        pvs.state = Borrowed;
2005
                    }
2006 1
                    else if (isReadonlyPtr(v))
2007
                    {
2008 1
                        pvs.state = Readonly;
2009
                    }
2010
                    else
2011
                    {
2012
                        // move from r to v
2013 1
                        pvsr.state = Undefined;
2014 1
                        pvsr.deps.zero();
2015
                    }
2016
                }
2017
            }
2018

2019 1
            foreach (VarDeclaration v2; er.byvalue)
2020 1
                by(v2);
2021 1
            foreach (VarDeclaration v2; er.byref)
2022 1
                by(v2);
2023
        }
2024
        else
2025
        {
2026 0
            if (isBorrowedPtr(v))
2027 0
                pvs.state = PtrState.Borrowed;
2028 0
            else if (isReadonlyPtr(v))
2029 0
                pvs.state = PtrState.Readonly;
2030
            else
2031 0
                pvs.state = PtrState.Owner;
2032 0
            pvs.deps.zero();
2033
        }
2034
    }
2035

2036
    void dgReadVar(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[] gen)
2037
    {
2038 1
        if (log) printf("dgReadVar() %s\n", v.toChars());
2039 1
        const vi = obstate.vars.find(v);
2040 1
        assert(vi != size_t.max);
2041 1
        auto pvs = &gen[vi];
2042 1
        if (pvs.state == PtrState.Undefined)
2043 1
            v.error(loc, "has undefined state and cannot be read");
2044

2045 1
        readVar(ob, vi, mutable, gen);
2046
    }
2047

2048
    void foreachExp(ObNode* ob, Expression e, PtrVarState[] cpvs)
2049
    {
2050
        extern (C++) final class ExpWalker : Visitor
2051
        {
2052
            alias visit = typeof(super).visit;
2053
            extern (D) void delegate(ObNode*, PtrVarState[], VarDeclaration, Expression) dgWriteVar;
2054
            extern (D) void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[]) dgReadVar;
2055
            PtrVarState[] cpvs;
2056
            ObNode* ob;
2057
            ObState* obstate;
2058

2059 1
            extern (D) this(void delegate(const ref Loc loc, ObNode* ob, VarDeclaration v, bool mutable, PtrVarState[]) dgReadVar,
2060
                            void delegate(ObNode*, PtrVarState[], VarDeclaration, Expression) dgWriteVar,
2061
                            PtrVarState[] cpvs, ObNode* ob, ref ObState obstate)
2062
            {
2063 1
                this.dgReadVar  = dgReadVar;
2064 1
                this.dgWriteVar = dgWriteVar;
2065 1
                this.cpvs = cpvs;
2066 1
                this.ob = ob;
2067 1
                this.obstate = &obstate;
2068
            }
2069

2070
            override void visit(Expression)
2071
            {
2072
            }
2073

2074
            override void visit(DeclarationExp e)
2075
            {
2076
                void Dsymbol_visit(Dsymbol s)
2077
                {
2078 1
                    if (auto vd = s.isVarDeclaration())
2079
                    {
2080 1
                        s = s.toAlias();
2081 1
                        if (s != vd)
2082 0
                            return Dsymbol_visit(s);
2083 1
                        if (!isTrackableVar(vd))
2084 0
                            return;
2085

2086 1
                        if (vd._init && vd._init.isVoidInitializer())
2087 1
                            return;
2088

2089 1
                        auto ei = vd._init ? vd._init.isExpInitializer() : null;
2090 1
                        if (ei)
2091
                        {
2092 1
                            auto e = ei.exp;
2093 1
                            if (auto ae = e.isConstructExp())
2094 1
                                e = ae.e2;
2095 1
                            dgWriteVar(ob, cpvs, vd, e);
2096
                        }
2097
                        else
2098 0
                            dgWriteVar(ob, cpvs, vd, null);
2099
                    }
2100 0
                    else if (auto td = s.isTupleDeclaration())
2101
                    {
2102 0
                        foreach (o; *td.objects)
2103
                        {
2104 0
                            if (auto eo = o.isExpression())
2105
                            {
2106 0
                                if (auto se = eo.isDsymbolExp())
2107
                                {
2108 0
                                    Dsymbol_visit(se.s);
2109
                                }
2110
                            }
2111
                        }
2112
                    }
2113
                }
2114

2115 1
                Dsymbol_visit(e.declaration);
2116
            }
2117

2118
            override void visit(AssignExp ae)
2119
            {
2120 1
                ae.e2.accept(this);
2121 1
                if (auto ve = ae.e1.isVarExp())
2122
                {
2123 1
                    if (auto v = ve.var.isVarDeclaration())
2124 1
                        if (isTrackableVar(v))
2125 1
                            dgWriteVar(ob, cpvs, v, ae.e2);
2126
                }
2127
                else
2128 1
                    ae.e1.accept(this);
2129
            }
2130

2131
            override void visit(VarExp ve)
2132
            {
2133
                //printf("VarExp: %s\n", ve.toChars());
2134 1
                if (auto v = ve.var.isVarDeclaration())
2135 1
                    if (isTrackableVar(v))
2136
                    {
2137 1
                        dgReadVar(ve.loc, ob, v, isMutableRef(ve.type), cpvs);
2138
                    }
2139
            }
2140

2141
            override void visit(CallExp ce)
2142
            {
2143
                //printf("CallExp(%s)\n", ce.toChars());
2144 1
                ce.e1.accept(this);
2145 1
                auto t = ce.e1.type.toBasetype();
2146 1
                auto tf = t.isTypeFunction();
2147 1
                if (!tf)
2148
                {
2149 0
                    assert(t.ty == Tdelegate);
2150 0
                    tf = t.nextOf().isTypeFunction();
2151 0
                    assert(tf);
2152
                }
2153

2154
                // j=1 if _arguments[] is first argument
2155 1
                const int j = tf.isDstyleVariadic();
2156 1
                bool hasOut;
2157 1
                const varStackSave = obstate.varStack.length;
2158

2159 1
                foreach (const i, arg; (*ce.arguments)[])
2160
                {
2161 1
                    if (i - j < tf.parameterList.length &&
2162 1
                        i >= j)
2163
                    {
2164 1
                        Parameter p = tf.parameterList[i - j];
2165 1
                        auto pt = p.type.toBasetype();
2166

2167 1
                        if (!(p.storageClass & STC.out_ && arg.isVarExp()))
2168 1
                            arg.accept(this);
2169

2170 1
                        EscapeByResults er;
2171 1
                        escapeByValue(arg, &er, true);
2172

2173
                        void by(VarDeclaration v)
2174
                        {
2175 1
                            if (!isTrackableVar(v))
2176 0
                                return;
2177

2178 1
                            const vi = obstate.vars.find(v);
2179 1
                            if (vi == size_t.max)
2180 0
                                return;
2181

2182 1
                            auto pvs = &cpvs[vi];
2183

2184 1
                            if (p.storageClass & STC.out_)
2185
                            {
2186
                                /// initialize
2187 0
                                hasOut = true;
2188 0
                                makeUndefined(vi, cpvs);
2189
                            }
2190 1
                            else if (p.storageClass & STC.scope_)
2191
                            {
2192
                                // borrow
2193 1
                                obstate.varStack.push(vi);
2194 1
                                obstate.mutableStack.push(isMutableRef(pt));
2195
                            }
2196
                            else
2197
                            {
2198
                                // move (i.e. consume arg)
2199 1
                                if (pvs.state != PtrState.Owner)
2200 1
                                    v.error(arg.loc, "is not Owner, cannot consume its value");
2201 1
                                makeUndefined(vi, cpvs);
2202
                            }
2203
                        }
2204

2205 1
                        foreach (VarDeclaration v2; er.byvalue)
2206 1
                            by(v2);
2207 1
                        foreach (VarDeclaration v2; er.byref)
2208 0
                            by(v2);
2209
                    }
2210
                    else // variadic args
2211
                    {
2212 1
                        arg.accept(this);
2213

2214 1
                        EscapeByResults er;
2215 1
                        escapeByValue(arg, &er, true);
2216

2217
                        void byv(VarDeclaration v)
2218
                        {
2219 1
                            if (!isTrackableVar(v))
2220 0
                                return;
2221

2222 1
                            const vi = obstate.vars.find(v);
2223 1
                            if (vi == size_t.max)
2224 0
                                return;
2225

2226 1
                            auto pvs = &cpvs[vi];
2227

2228 1
                            if (tf.parameterList.stc & STC.scope_)
2229
                            {
2230
                                // borrow
2231 1
                                obstate.varStack.push(vi);
2232 1
                                obstate.mutableStack.push(isMutableRef(arg.type) &&
2233 1
                                        !(tf.parameterList.stc & (STC.const_ | STC.immutable_)));
2234
                            }
2235
                            else
2236
                            {
2237
                                // move (i.e. consume arg)
2238 0
                                if (pvs.state != PtrState.Owner)
2239 0
                                    v.error(arg.loc, "is not Owner, cannot consume its value");
2240 0
                                makeUndefined(vi, cpvs);
2241
                            }
2242
                        }
2243

2244 1
                        foreach (VarDeclaration v2; er.byvalue)
2245 1
                            byv(v2);
2246 1
                        foreach (VarDeclaration v2; er.byref)
2247 0
                            byv(v2);
2248
                    }
2249
                }
2250

2251
                /* Do a dummy 'read' of each variable passed to the function,
2252
                 * to detect O/B errors
2253
                 */
2254 1
                assert(obstate.varStack.length == obstate.mutableStack.length);
2255 1
                foreach (i; varStackSave .. obstate.varStack.length)
2256
                {
2257 1
                    const vi = obstate.varStack[i];
2258 1
                    auto pvs = &cpvs[vi];
2259 1
                    auto v = obstate.vars[vi];
2260
                    //if (pvs.state == PtrState.Undefined)
2261
                        //v.error(ce.loc, "is Undefined, cannot pass to function");
2262

2263 1
                    dgReadVar(ce.loc, ob, v, obstate.mutableStack[i], cpvs);
2264

2265 1
                    if (pvs.state == PtrState.Owner)
2266
                    {
2267 1
                        for (size_t k = i + 1; k < obstate.varStack.length;++k)
2268
                        {
2269 1
                            const vk = obstate.varStack[k];
2270 1
                            if (vk == vi)
2271
                            {
2272 1
                                if (obstate.mutableStack[vi] || obstate.mutableStack[vk])
2273
                                {
2274 1
                                    v.error(ce.loc, "is passed as Owner more than once");
2275 1
                                    break;  // no need to continue
2276
                                }
2277
                            }
2278
                        }
2279
                    }
2280
                }
2281

2282
                /* Pop off stack all variables for this function call
2283
                 */
2284 1
                obstate.varStack.setDim(varStackSave);
2285 1
                obstate.mutableStack.setDim(varStackSave);
2286

2287 1
                if (hasOut)
2288
                    // Initialization of out's only happens after the function call
2289 0
                    foreach (const i, arg; (*ce.arguments)[])
2290
                    {
2291 0
                        if (i - j < tf.parameterList.length &&
2292 0
                            i >= j)
2293
                        {
2294 0
                            Parameter p = tf.parameterList[i - j];
2295 0
                            if (p.storageClass & STC.out_)
2296
                            {
2297 0
                                if (auto v = isTrackableVarExp(arg))
2298
                                {
2299 0
                                    dgWriteVar(ob, cpvs, v, null);
2300
                                }
2301
                            }
2302
                        }
2303
                    }
2304
            }
2305

2306
            override void visit(SymOffExp e)
2307
            {
2308 0
                if (auto v = e.var.isVarDeclaration())
2309 0
                    if (isTrackableVar(v))
2310
                    {
2311 0
                        dgReadVar(e.loc, ob, v, isMutableRef(e.type), cpvs);
2312
                    }
2313
            }
2314

2315
            override void visit(LogicalExp e)
2316
            {
2317 0
                e.e1.accept(this);
2318

2319 0
                const vlen = obstate.vars.length;
2320 0
                auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof);
2321 0
                PtrVarState[] out1 = p[0 .. vlen];
2322 0
                foreach (i, ref pvs; out1)
2323
                {
2324 0
                    pvs = cpvs[i];
2325
                }
2326

2327 0
                e.e2.accept(this);
2328

2329
                // Merge out1 into cpvs
2330 0
                foreach (i; 0 .. vlen)
2331
                {
2332 0
                    cpvs[i].combine(out1[i], i, cpvs);
2333
                }
2334

2335 0
                mem.xfree(p); // should free .deps too
2336
            }
2337

2338
            override void visit(CondExp e)
2339
            {
2340 0
                e.econd.accept(this);
2341

2342 0
                const vlen = obstate.vars.length;
2343 0
                auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof);
2344 0
                PtrVarState[] out1 = p[0 .. vlen];
2345 0
                foreach (i, ref pvs; out1)
2346
                {
2347 0
                    pvs = cpvs[i];
2348
                }
2349

2350 0
                e.e1.accept(this);
2351

2352
                // Swap out1 with cpvs
2353 0
                foreach (i; 0 .. vlen)
2354
                {
2355 0
                    out1[i].deps.swap(cpvs[i].deps);
2356 0
                    const state = out1[i].state;
2357 0
                    out1[i].state = cpvs[i].state;
2358 0
                    cpvs[i].state = state;
2359
                }
2360

2361 0
                e.e2.accept(this);
2362

2363
                // Merge out1 into cpvs
2364 0
                foreach (i; 0 .. vlen)
2365
                {
2366 0
                    cpvs[i].combine(out1[i], i, cpvs);
2367
                }
2368

2369 0
                mem.xfree(p); // should free .deps too
2370
            }
2371

2372
            override void visit(AddrExp e)
2373
            {
2374
                /* Taking the address of struct literal is normally not
2375
                 * allowed, but CTFE can generate one out of a new expression,
2376
                 * but it'll be placed in static data so no need to check it.
2377
                 */
2378 0
                if (e.e1.op != TOK.structLiteral)
2379 0
                    e.e1.accept(this);
2380
            }
2381

2382
            override void visit(UnaExp e)
2383
            {
2384 1
                e.e1.accept(this);
2385
            }
2386

2387
            override void visit(BinExp e)
2388
            {
2389 1
                e.e1.accept(this);
2390 1
                e.e2.accept(this);
2391
            }
2392

2393
            override void visit(ArrayLiteralExp e)
2394
            {
2395 0
                Type tb = e.type.toBasetype();
2396 0
                if (tb.ty == Tsarray || tb.ty == Tarray)
2397
                {
2398 0
                    if (e.basis)
2399 0
                        e.basis.accept(this);
2400 0
                    foreach (el; *e.elements)
2401
                    {
2402 0
                        if (el)
2403 0
                            el.accept(this);
2404
                    }
2405
                }
2406
            }
2407

2408
            override void visit(StructLiteralExp e)
2409
            {
2410 0
                if (e.elements)
2411
                {
2412 0
                    foreach (ex; *e.elements)
2413
                    {
2414 0
                        if (ex)
2415 0
                            ex.accept(this);
2416
                    }
2417
                }
2418
            }
2419

2420
            override void visit(AssocArrayLiteralExp e)
2421
            {
2422 0
                if (e.keys)
2423
                {
2424 0
                    foreach (i, key; *e.keys)
2425
                    {
2426 0
                        if (key)
2427 0
                            key.accept(this);
2428 0
                        if (auto value = (*e.values)[i])
2429 0
                            value.accept(this);
2430
                    }
2431
                }
2432
            }
2433

2434
            override void visit(NewExp e)
2435
            {
2436 1
                if (e.arguments)
2437
                {
2438 1
                    foreach (ex; *e.arguments)
2439
                    {
2440 1
                        if (ex)
2441 1
                            ex.accept(this);
2442
                    }
2443
                }
2444
            }
2445

2446
            override void visit(SliceExp e)
2447
            {
2448 0
                e.e1.accept(this);
2449 0
                if (e.lwr)
2450 0
                    e.lwr.accept(this);
2451 0
                if (e.upr)
2452 0
                    e.upr.accept(this);
2453
            }
2454
        }
2455

2456 1
        if (e)
2457
        {
2458 1
            scope ExpWalker ew = new ExpWalker(&dgReadVar, &dgWriteVar, cpvs, ob, obstate);
2459 1
            e.accept(ew);
2460
        }
2461
    }
2462

2463 1
    const vlen = obstate.vars.length;
2464 1
    auto p = cast(PtrVarState*)mem.xcalloc(vlen, PtrVarState.sizeof);
2465 1
    PtrVarState[] cpvs = p[0 .. vlen];
2466 1
    foreach (ref pvs; cpvs)
2467 1
        pvs.deps.length = vlen;
2468

2469 1
    foreach (obi, ob; obstate.nodes)
2470
    {
2471
        static if (log)
2472
        {
2473
            printf("%d: %s\n", obi, ob.exp ? ob.exp.toChars() : "".ptr);
2474
            printf("  input:\n");
2475
            foreach (i, ref pvs; ob.input[])
2476
            {
2477
                printf("    %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]);
2478
            }
2479
        }
2480

2481
        /* Combine the .output[]s of each ob.preds[] looking for errors
2482
         */
2483 1
        if (obi)   // skip startnode
2484
        {
2485 1
            assert(ob.preds.length);
2486

2487 1
            foreach (i; 0 .. vlen)
2488
            {
2489 1
                ob.gen[i] = ob.preds[0].output[i];
2490
            }
2491

2492 1
            foreach (j; 1 .. ob.preds.length)
2493
            {
2494 1
                foreach (i; 0 .. vlen)
2495
                {
2496 1
                    auto pvs1 = &ob.gen[i];
2497 1
                    auto pvs2 = &ob.preds[j].output[i];
2498 1
                    const s1 = pvs1.state;
2499 1
                    const s2 = pvs2.state;
2500 1
                    if (s1 != s2 && (s1 == PtrState.Owner || s2 == PtrState.Owner))
2501
                    {
2502 1
                        auto v = obstate.vars[i];
2503 1
                        v.error(ob.exp ? ob.exp.loc : v.loc, "is both %s and %s", s1.toChars(), s2.toChars());
2504
                    }
2505 1
                    pvs1.combine(*pvs2, i, ob.gen);
2506
                }
2507
            }
2508
        }
2509

2510
        /* Prolly should use gen[] instead of cpvs[], or vice versa
2511
         */
2512 1
        foreach (i, ref pvs; ob.input)
2513
        {
2514 1
            cpvs[i] = pvs;
2515
        }
2516

2517 1
        foreachExp(ob, ob.exp, cpvs);
2518

2519
        static if (log)
2520
        {
2521
            printf("  cpvs:\n");
2522
            foreach (i, ref pvs; cpvs[])
2523
            {
2524
                printf("    %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]);
2525
            }
2526
            printf("  output:\n");
2527
            foreach (i, ref pvs; ob.output[])
2528
            {
2529
                printf("    %s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]);
2530
            }
2531
        }
2532

2533 1
        if (ob.obtype == ObType.retexp)
2534
        {
2535 1
            EscapeByResults er;
2536 1
            escapeByValue(ob.exp, &er, true);
2537

2538
            void by(VarDeclaration r)   // `r` is the rvalue
2539
            {
2540 1
                const ri = obstate.vars.find(r);
2541 1
                if (ri == size_t.max)
2542 0
                    return;
2543
                with (PtrState)
2544
                {
2545 1
                    auto pvsr = &ob.output[ri];
2546 1
                    switch (pvsr.state)
2547
                    {
2548 1
                        case Undefined:
2549 1
                            r.error(ob.exp.loc, "is returned but is Undefined");
2550 1
                            break;
2551

2552 1
                        case Owner:
2553 1
                            pvsr.state = Undefined;     // returning a pointer "consumes" it
2554 1
                            break;
2555

2556 0
                        case Borrowed:
2557 0
                        case Readonly:
2558 0
                            break;
2559

2560 0
                        default:
2561 0
                            assert(0);
2562
                    }
2563
                }
2564
            }
2565

2566 1
            foreach (VarDeclaration v2; er.byvalue)
2567 1
                by(v2);
2568 1
            foreach (VarDeclaration v2; er.byref)
2569 0
                by(v2);
2570
        }
2571

2572 1
        if (ob.obtype == ObType.return_ || ob.obtype == ObType.retexp)
2573
        {
2574 1
            foreach (i, ref pvs; ob.output[])
2575
            {
2576
                //printf("%s: ", obstate.vars[i].toChars()); pvs.print(obstate.vars[]);
2577 1
                if (pvs.state == PtrState.Owner)
2578
                {
2579 1
                    auto v = obstate.vars[i];
2580 1
                    if (v.type.hasPointers())
2581 1
                        v.error(v.loc, "is left dangling at return");
2582
                }
2583
            }
2584
        }
2585
    }
2586
}
2587

2588

2589
/***************************************************
2590
 * Read from variable vi.
2591
 * The beginning of the 'scope' of a variable is when it is first read.
2592
 * Hence, when a read is done, instead of when assignment to the variable is done, the O/B rules are enforced.
2593
 * (Also called "non-lexical scoping".)
2594
 */
2595
void readVar(ObNode* ob, const size_t vi, bool mutable, PtrVarState[] gen)
2596
{
2597
    //printf("readVar(v%d)\n", cast(int)vi);
2598 1
    auto pvso = &gen[vi];
2599 1
    switch (pvso.state)
2600
    {
2601 1
        case PtrState.Owner:
2602
            //printf("t: %s\n", t.toChars());
2603 1
            if (mutable) // if mutable read
2604
            {
2605 1
                makeChildrenUndefined(vi, gen);
2606
            }
2607
            else // const read
2608
            {
2609
                // If there's a Borrow child, set that to Undefined
2610 1
                foreach (di; 0 .. gen.length)
2611
                {
2612 1
                    auto pvsd = &gen[di];
2613 1
                    if (pvsd.deps[vi] && pvsd.state == PtrState.Borrowed) // if di borrowed vi
2614
                    {
2615 1
                        makeUndefined(di, gen);
2616
                    }
2617
                }
2618
            }
2619 1
            break;
2620

2621 0
        case PtrState.Borrowed:
2622
            /* All children become Undefined
2623
             */
2624 0
            makeChildrenUndefined(vi, gen);
2625 0
            break;
2626

2627 1
        case PtrState.Readonly:
2628 1
            break;
2629

2630 1
        case PtrState.Undefined:
2631 1
            break;
2632

2633 0
        default:
2634 0
            break;
2635
    }
2636
}
2637

2638
/********************
2639
 * Recursively make Undefined all who list vi as a dependency
2640
 */
2641
void makeChildrenUndefined(size_t vi, PtrVarState[] gen)
2642
{
2643
    //printf("makeChildrenUndefined(%d)\n", vi);
2644 1
    foreach (di; 0 .. gen.length)
2645
    {
2646 1
        if (gen[di].deps[vi])    // if di depends on vi
2647
        {
2648 1
            if (gen[di].state != PtrState.Undefined)
2649
            {
2650 1
                gen[di].state = PtrState.Undefined;  // set this first to avoid infinite recursion
2651 1
                makeChildrenUndefined(di, gen);
2652 1
                gen[di].deps.zero();
2653
            }
2654
        }
2655
    }
2656
}
2657

2658

2659
/********************
2660
 * Recursively make Undefined vi undefined and all who list vi as a dependency
2661
 */
2662
void makeUndefined(size_t vi, PtrVarState[] gen)
2663
{
2664 1
    auto pvs = &gen[vi];
2665 1
    pvs.state = PtrState.Undefined;  // set this first to avoid infinite recursion
2666 1
    makeChildrenUndefined(vi, gen);
2667 1
    pvs.deps.zero();
2668
}
2669

2670
/*************************
2671
 * Is type `t` a reference to a const or a reference to a mutable?
2672
 */
2673
bool isMutableRef(Type t)
2674
{
2675 1
    auto tb = t.toBasetype();
2676 1
    return (tb.nextOf() ? tb.nextOf() : tb).isMutable();
2677
}

Read our documentation on viewing source code .

Loading