compiler: Initialize ownership checker binding slots

ecf232b6ef6556b858862566ad263eeb5997a7cde74011add0ce34cf1013afdd
Alexis Sellier committed ago 1 parent 50908ae8
lib/std/lang/resolver.rad +31 -19
935 935
    /// Consumption rule fixed before ownership analysis.
936 936
    usage: BindingUse,
937 937
}
938 938
939 939
/// Per-control-flow-path ownership state.
940 -
/// Read only the initialized symbol prefix below `len`.
940 +
/// Active binding slots below `len` must contain metadata.
941 941
record LinearEnv: Copy {
942 942
    /// Active full-region loans, indexed by the checker's regional loan table.
943 943
    regionalLoans: u64,
944 -
    /// Resolved binding metadata. Entries below `len` are initialized.
945 -
    symbols: [TrackedSymbol; MAX_LINEAR_BINDINGS],
944 +
    /// Initialized slots for resolved binding metadata.
945 +
    symbols: [?TrackedSymbol; MAX_LINEAR_BINDINGS],
946 946
    /// Bit set for each binding that remains available.
947 947
    available: u64,
948 -
    /// Number of initialized entries in `symbols`.
948 +
    /// Number of active binding slots in `symbols`.
949 949
    len: u32,
950 950
    /// Whether this control-flow path has terminated.
951 951
    terminated: bool,
952 952
}
953 953
10006 10006
    for stmt in block.statements {
10007 10007
        try visitDecl(res, stmt);
10008 10008
    }
10009 10009
}
10010 10010
10011 +
/// Create an empty ownership environment with initialized binding slots.
10012 +
fn linearEnv() -> LinearEnv {
10013 +
    return LinearEnv {
10014 +
        regionalLoans: 0,
10015 +
        symbols: [nil; MAX_LINEAR_BINDINGS],
10016 +
        available: 0,
10017 +
        len: 0,
10018 +
        terminated: false,
10019 +
    };
10020 +
}
10021 +
10022 +
/// Read initialized binding metadata from the active prefix.
10023 +
fn linearSymbol(env: &LinearEnv, index: u32) -> TrackedSymbol {
10024 +
    assert index < env.len, "linearSymbol: binding index outside active prefix";
10025 +
    let symbol = env.symbols[index] else panic "linearSymbol: missing active binding";
10026 +
    return symbol;
10027 +
}
10028 +
10011 10029
/// Find a tracked binding by symbol identity.
10012 10030
fn findLinearBinding(env: &LinearEnv, symbolId: u32) -> ?u32 {
10013 10031
    for i in 0..env.len {
10014 -
        if env.symbols[i].id == symbolId {
10032 +
        if linearSymbol(env, i).id == symbolId {
10015 10033
            return i;
10016 10034
        }
10017 10035
    }
10018 10036
    return nil;
10019 10037
}
10055 10073
    start: u32,
10056 10074
) throws (ResolveError) where 'arena: 'checking {
10057 10075
    if not env.terminated {
10058 10076
        for i in start..env.len {
10059 10077
            if linearBindingAvailable(env, i) {
10060 -
                let sym = env.symbols[i];
10078 +
                let sym = linearSymbol(env, i);
10061 10079
                if sym.usage == BindingUse::Linear {
10062 10080
                    throw emitError(
10063 10081
                        checker.resolver,
10064 10082
                        sym.node,
10065 10083
                        ErrorKind::LinearNotConsumed(sym.name),
10078 10096
    node: *ast::Node,
10079 10097
) throws (ResolveError) where 'arena: 'checking {
10080 10098
    let binding = checker.resolver.nodeData.entries[node.id].binding else return;
10081 10099
    let index = findLinearBinding(env, binding.id) else return;
10082 10100
    if not linearBindingAvailable(env, index) {
10083 -
        let sym = env.symbols[index];
10101 +
        let sym = linearSymbol(env, index);
10084 10102
        let kind = ErrorKind::LinearUseAfterConsume(sym.name) if sym.usage == BindingUse::Linear
10085 10103
            else ErrorKind::AffineUseAfterMove(sym.name);
10086 10104
        throw emitError(checker.resolver, node, kind);
10087 10105
    }
10088 10106
}
10123 10141
    }
10124 10142
    assert left.len == right.len, "joinLinearBranches: scope mismatch";
10125 10143
    let mut available = left.available;
10126 10144
    for i in 0..left.len {
10127 10145
        if linearBindingAvailable(left, i) <> linearBindingAvailable(right, i) {
10128 -
            let sym = left.symbols[i];
10146 +
            let sym = linearSymbol(left, i);
10129 10147
            if sym.usage == BindingUse::Linear {
10130 10148
                throw emitError(
10131 10149
                    checker.resolver,
10132 10150
                    node,
10133 10151
                    ErrorKind::LinearBranchMismatch(sym.name),
10150 10168
    if env.terminated {
10151 10169
        return;
10152 10170
    }
10153 10171
    for i in 0..env.len {
10154 10172
        if linearBindingAvailable(env, i) {
10155 -
            let sym = env.symbols[i];
10173 +
            let sym = linearSymbol(env, i);
10156 10174
            if sym.usage == BindingUse::Linear {
10157 10175
                throw emitError(
10158 10176
                    checker.resolver,
10159 10177
                    sym.node,
10160 10178
                    ErrorKind::LinearNotConsumed(sym.name),
10634 10652
    let mark = checker.loopMarks[depth];
10635 10653
    let entryAvailable = checker.loopAvailable[depth];
10636 10654
    for i in 0..mark {
10637 10655
        let bit = (1 as u64) << (i as u64);
10638 10656
        if (env.available & bit) <> (entryAvailable & bit) {
10639 -
            let sym = env.symbols[i];
10657 +
            let sym = linearSymbol(env, i);
10640 10658
            throw emitError(
10641 10659
                checker.resolver,
10642 10660
                node,
10643 10661
                ErrorKind::LinearBranchMismatch(sym.name),
10644 10662
            );
10668 10686
    if checker.loopHasNaturalExit[depth] or checker.loopBreakSeen[depth] {
10669 10687
        let expected = checker.loopExitAvailable[depth];
10670 10688
        for i in 0..mark {
10671 10689
            let bit = (1 as u64) << (i as u64);
10672 10690
            if (env.available & bit) <> (expected & bit) {
10673 -
                let sym = env.symbols[i];
10691 +
                let sym = linearSymbol(env, i);
10674 10692
                throw emitError(
10675 10693
                    checker.resolver,
10676 10694
                    node,
10677 10695
                    ErrorKind::LinearBranchMismatch(sym.name),
10678 10696
                );
10767 10785
            }
10768 10786
            case ast::ProngArm::Else => {}
10769 10787
        }
10770 10788
        if prong.guard <> nil {
10771 10789
            for i in bindingsStart..branch.len {
10772 -
                let sym = branch.symbols[i];
10790 +
                let sym = linearSymbol(&branch, i);
10773 10791
                if sym.usage == BindingUse::Linear {
10774 10792
                    throw emitError(checker.resolver, prongNode, ErrorKind::LinearDiscard);
10775 10793
                }
10776 10794
            }
10777 10795
        }
11644 11662
            loopExitAvailable: undefined,
11645 11663
            loopHasNaturalExit: undefined,
11646 11664
            loopBreakSeen: undefined,
11647 11665
            loopDepth: 0,
11648 11666
        };
11649 -
        let mut env = LinearEnv {
11650 -
            regionalLoans: 0,
11651 -
            symbols: undefined,
11652 -
            available: 0,
11653 -
            len: 0,
11654 -
            terminated: false,
11655 -
        };
11667 +
        let mut env = linearEnv();
11656 11668
        if let receiverNode = receiver {
11657 11669
            try addLinearBinding(&mut checker, &mut env, receiverNode);
11658 11670
        }
11659 11671
        for paramNode in params {
11660 11672
            let case ast::NodeValue::FnParam(_) = paramNode.value
lib/std/lang/resolver/tests.rad +20 -0
53 53
            }
54 54
        }
55 55
    }
56 56
}
57 57
58 +
/// Reused ownership slots retain the current binding's exact-use diagnostics.
59 +
@test unsafe fn testLinearScratchSlotReuse() throws (testing::TestError) {
60 +
    let mut arena = testArena();
61 +
    let storage: 'test = &mut arena in {
62 +
        let mut res = testResolver(storage);
63 +
        let result = try resolveProgramStr(&mut res,
64 +
            "union Token: Once { Value(u32) } fn consume(t: Token) { match t { case Token::Value(_) => {} } } fn f() { { let first = Token::Value(1); consume(first); } let second = Token::Value(2); consume(second); consume(second); }"
65 +
        );
66 +
        try expectErrorKind(&result, super::ErrorKind::LinearUseAfterConsume("second"));
67 +
    }
68 +
    let mut branchArena = testArena();
69 +
    let branchStorage: 'branch = &mut branchArena in {
70 +
        let mut res = testResolver(branchStorage);
71 +
        let result = try resolveProgramStr(&mut res,
72 +
            "union Token: Once { Value(u32) } fn consume(t: Token) { match t { case Token::Value(_) => {} } } fn f(choice: bool) { { let first = Token::Value(1); consume(first); } let second = Token::Value(2); if choice { consume(second); } }"
73 +
        );
74 +
        try expectErrorKind(&result, super::ErrorKind::LinearBranchMismatch("second"));
75 +
    }
76 +
}
77 +
58 78
/// Loop bindings and lowering metadata retain the same item type and names.
59 79
@test unsafe fn testForLoopMetadata() throws (testing::TestError) {
60 80
    let mut arena = testArena();
61 81
    let storage: 'test = &mut arena in {
62 82
        let mut res = testResolver(storage);
test/tests/linear.scratch.slots.rad added +107 -0
1 +
//! returns: 0
2 +
3 +
/// Exact-use token retained in ownership-checker scratch slots.
4 +
union Token: Once {
5 +
    /// Token payload.
6 +
    Value(u32),
7 +
}
8 +
9 +
/// Consume a token and return its payload.
10 +
fn consume(token: Token) -> u32 {
11 +
    match token {
12 +
        case Token::Value(value) => return value,
13 +
    }
14 +
}
15 +
16 +
/// Fill every tracking slot, copy branch state, and reuse slots after scope exit.
17 +
fn exercise(choice: bool) -> u32 {
18 +
    let mut sum: u32 = 0;
19 +
    {
20 +
        let t0 = Token::Value(0);
21 +
        let t1 = Token::Value(1);
22 +
        let t2 = Token::Value(2);
23 +
        let t3 = Token::Value(3);
24 +
        let t4 = Token::Value(4);
25 +
        let t5 = Token::Value(5);
26 +
        let t6 = Token::Value(6);
27 +
        let t7 = Token::Value(7);
28 +
        let t8 = Token::Value(8);
29 +
        let t9 = Token::Value(9);
30 +
        let t10 = Token::Value(10);
31 +
        let t11 = Token::Value(11);
32 +
        let t12 = Token::Value(12);
33 +
        let t13 = Token::Value(13);
34 +
        let t14 = Token::Value(14);
35 +
        let t15 = Token::Value(15);
36 +
        let t16 = Token::Value(16);
37 +
        let t17 = Token::Value(17);
38 +
        let t18 = Token::Value(18);
39 +
        let t19 = Token::Value(19);
40 +
        let t20 = Token::Value(20);
41 +
        let t21 = Token::Value(21);
42 +
        let t22 = Token::Value(22);
43 +
        let t23 = Token::Value(23);
44 +
        let t24 = Token::Value(24);
45 +
        let t25 = Token::Value(25);
46 +
        let t26 = Token::Value(26);
47 +
        let t27 = Token::Value(27);
48 +
        let t28 = Token::Value(28);
49 +
        let t29 = Token::Value(29);
50 +
        let t30 = Token::Value(30);
51 +
        let t31 = Token::Value(31);
52 +
        if choice {
53 +
            set sum += consume(t0);
54 +
        } else {
55 +
            set sum += consume(t0);
56 +
        }
57 +
        set sum += consume(t1);
58 +
        set sum += consume(t2);
59 +
        set sum += consume(t3);
60 +
        set sum += consume(t4);
61 +
        set sum += consume(t5);
62 +
        set sum += consume(t6);
63 +
        set sum += consume(t7);
64 +
        set sum += consume(t8);
65 +
        set sum += consume(t9);
66 +
        set sum += consume(t10);
67 +
        set sum += consume(t11);
68 +
        set sum += consume(t12);
69 +
        set sum += consume(t13);
70 +
        set sum += consume(t14);
71 +
        set sum += consume(t15);
72 +
        set sum += consume(t16);
73 +
        set sum += consume(t17);
74 +
        set sum += consume(t18);
75 +
        set sum += consume(t19);
76 +
        set sum += consume(t20);
77 +
        set sum += consume(t21);
78 +
        set sum += consume(t22);
79 +
        set sum += consume(t23);
80 +
        set sum += consume(t24);
81 +
        set sum += consume(t25);
82 +
        set sum += consume(t26);
83 +
        set sum += consume(t27);
84 +
        set sum += consume(t28);
85 +
        set sum += consume(t29);
86 +
        set sum += consume(t30);
87 +
        set sum += consume(t31);
88 +
    }
89 +
    for i in 0..3 {
90 +
        let token = Token::Value(i);
91 +
        if i == 1 {
92 +
            set sum += consume(token);
93 +
            continue;
94 +
        }
95 +
        set sum += consume(token);
96 +
    }
97 +
    let last = Token::Value(1);
98 +
    set sum += consume(last);
99 +
    return sum;
100 +
}
101 +
102 +
/// Execute both branch paths and verify all token payloads.
103 +
@default fn main() -> u32 {
104 +
    assert exercise(true) == 500;
105 +
    assert exercise(false) == 500;
106 +
    return 0;
107 +
}