lib/std/lang/il/link.rad 11.8 KiB raw
1
//! Bounded comparison of type contracts from separate RIL programs.
2
3
@test export mod tests;
4
5
use std::lang::il;
6
use std::mem::heap;
7
8
/// Largest comparison workspace accepted by the graph matcher.
9
export constant MAX_PAIRS: u32 = 65536;
10
11
/// Multiplier for the left descriptor index in a pair hash.
12
constant HASH_LEFT: u64 = 0x9e3779b1;
13
/// Multiplier for the right descriptor index in a pair hash.
14
constant HASH_RIGHT: u64 = 0x85ebca77;
15
16
/// A graph comparison exceeded its capacity or could not allocate storage.
17
export union Error: Copy {
18
    /// The number of distinct descriptor pairs exceeds the configured limit.
19
    Limit,
20
    /// The scratch heap has insufficient storage.
21
    Storage,
22
}
23
24
/// Descriptor table selected by a graph edge.
25
union Kind: Copy {
26
    /// Object representation and its protected slots.
27
    Layout,
28
    /// Function parameters, result, and borrow relations.
29
    Signature,
30
    /// Ordered method contracts and receiver rights.
31
    Trait,
32
}
33
34
/// One distinct pair of descriptors and its occupied hash-table slot.
35
record Pair: Copy {
36
    /// Descriptor table.
37
    kind: Kind,
38
    /// Index in the left program.
39
    left: u32,
40
    /// Index in the right program.
41
    right: u32,
42
    /// Slot which indexes this pair in Workspace.slots.
43
    bucket: u32,
44
}
45
46
/// Reusable storage for comparison of cyclic descriptor graphs.
47
export opaque record Workspace {
48
    /// Distinct pairs, in discovery order. Its length is the pair limit.
49
    pairs: *mut [Pair],
50
    /// Open-addressed pair indices plus one; zero denotes an empty slot.
51
    slots: *mut [u32],
52
    /// Initialized prefix of pairs.
53
    count: u32,
54
}
55
56
/// Allocate a bounded workspace. The heap must outlive all comparisons with it.
57
export fn workspace(limit: u32, arena: &heap::Heap) -> Workspace throws (Error) {
58
    if limit == 0 or limit > MAX_PAIRS {
59
        throw Error::Limit;
60
    }
61
    let mut size: u32 = 2;
62
    while size < limit * 2 {
63
        set size *= 2;
64
    }
65
    let mut slots: *mut [u32] = &mut [];
66
    let mut pairs: *mut [Pair] = &mut [];
67
    try slots.resize(size, 0, arena) catch {
68
        throw Error::Storage;
69
    };
70
    try pairs.resize(
71
        limit, Pair { kind: Kind::Layout, left: 0, right: 0, bucket: 0 }, arena
72
    ) catch {
73
        throw Error::Storage;
74
    };
75
    return Workspace { pairs, slots, count: 0 };
76
}
77
78
/// Clear the slots used by the previous comparison.
79
fn reset(work: &mut Workspace) {
80
    for pair in &work.pairs[.. work.count] {
81
        set work.slots[pair.bucket] = 0;
82
    }
83
    set work.count = 0;
84
}
85
86
/// Add an unseen edge. Existing pairs terminate traversal of a cycle.
87
fn edge(work: &mut Workspace, kind: Kind, left: u32, right: u32) throws (Error) {
88
    let mut tag: u64 = 0;
89
    match kind {
90
        case Kind::Layout    => set tag = 1,
91
        case Kind::Signature => set tag = 2,
92
        case Kind::Trait     => set tag = 3,
93
    }
94
    let hash = ((left as u64 * HASH_LEFT) ^ (right as u64 * HASH_RIGHT) ^ tag) as u32;
95
    let mask = work.slots.len - 1;
96
    let mut bucket = hash & mask;
97
    loop {
98
        let index = work.slots[bucket];
99
        if index == 0 {
100
            if work.count == work.pairs.len {
101
                throw Error::Limit;
102
            }
103
            set work.pairs[work.count] = Pair { kind, left, right, bucket };
104
            set work.count += 1;
105
            set work.slots[bucket] = work.count;
106
            return;
107
        }
108
        let pair = work.pairs[index - 1];
109
        if pair.kind == kind and pair.left == left and pair.right == right {
110
            return;
111
        }
112
        set bucket = (bucket + 1) & mask;
113
    }
114
}
115
116
/// Match pointer rights and enqueue the pointee layouts.
117
fn pointer(work: &mut Workspace, left: il::PtrType, right: il::PtrType) -> bool throws (Error) {
118
    if left.own <> right.own or left.mutable <> right.mutable or left.nullable <> right.nullable {
119
        return false;
120
    }
121
    try edge(work, Kind::Layout, left.layout, right.layout);
122
    return true;
123
}
124
125
/// Match a value type and enqueue its descriptor edges.
126
fn value(work: &mut Workspace, left: il::ValType, right: il::ValType) -> bool throws (Error) {
127
    match left {
128
        case il::ValType::Void => {
129
            if let case il::ValType::Void = right {
130
                return true;
131
            }
132
        }
133
        case il::ValType::Data(a) => {
134
            if let case il::ValType::Data(b) = right {
135
                return a == b;
136
            }
137
        }
138
        case il::ValType::Ptr(a) => {
139
            if let case il::ValType::Ptr(b) = right {
140
                return try pointer(work, a, b);
141
            }
142
        }
143
        case il::ValType::Fn(a) => {
144
            if let case il::ValType::Fn(b) = right {
145
                try edge(work, Kind::Signature, a, b);
146
                return true;
147
            }
148
        }
149
        case il::ValType::Heap(a) => {
150
            if let case il::ValType::Heap(b) = right {
151
                return a == b;
152
            }
153
        }
154
    }
155
    return false;
156
}
157
158
/// Match region positions, which determine the meaning of borrow contracts.
159
fn regions(left: &[u32], right: &[u32]) -> bool {
160
    if left.len <> right.len {
161
        return false;
162
    }
163
    for item, i in left {
164
        if item <> right[i] {
165
            return false;
166
        }
167
    }
168
    return true;
169
}
170
171
/// Match a protected slot and enqueue every referenced descriptor.
172
fn slot(work: &mut Workspace, left: il::SlotKind, right: il::SlotKind) -> bool throws (Error) {
173
    match left {
174
        case il::SlotKind::Ptr(a) => {
175
            if let case il::SlotKind::Ptr(b) = right {
176
                return try pointer(work, a, b);
177
            }
178
        }
179
        case il::SlotKind::Slice(a) => {
180
            if let case il::SlotKind::Slice(b) = right {
181
                return try pointer(work, a, b);
182
            }
183
        }
184
        case il::SlotKind::Fn(a) => {
185
            if let case il::SlotKind::Fn(b) = right {
186
                try edge(work, Kind::Signature, a, b);
187
                return true;
188
            }
189
        }
190
        case il::SlotKind::Heap(a) => {
191
            if let case il::SlotKind::Heap(b) = right {
192
                return a == b;
193
            }
194
        }
195
        case il::SlotKind::Trait(a) => {
196
            if let case il::SlotKind::Trait(b) = right {
197
                if a.own <> b.own or a.mutable <> b.mutable {
198
                    return false;
199
                }
200
                try edge(work, Kind::Trait, a.iface, b.iface);
201
                return true;
202
            }
203
        }
204
        case il::SlotKind::Sub(a) => {
205
            if let case il::SlotKind::Sub(b) = right {
206
                try edge(work, Kind::Layout, a, b);
207
                return true;
208
            }
209
        }
210
        case il::SlotKind::Array { layout: a, count: countA } => {
211
            if let case il::SlotKind::Array { layout: b, count: countB } = right {
212
                if countA <> countB {
213
                    return false;
214
                }
215
                try edge(work, Kind::Layout, a, b);
216
                return true;
217
            }
218
        }
219
        case il::SlotKind::Union { offset: offsetA, size: sizeA, variants: a } => {
220
            if let case il::SlotKind::Union { offset: offsetB, size: sizeB, variants: b } = right {
221
                if offsetA <> offsetB or sizeA <> sizeB or a.len <> b.len {
222
                    return false;
223
                }
224
                for variant, i in a {
225
                    if variant.tag <> b[i].tag or not regions(variant.regions, b[i].regions) {
226
                        return false;
227
                    }
228
                    if let child = variant.layout {
229
                        let other = b[i].layout else {
230
                            return false;
231
                        };
232
                        try edge(work, Kind::Layout, child, other);
233
                    } else if b[i].layout <> nil {
234
                        return false;
235
                    }
236
                }
237
                return true;
238
            }
239
        }
240
    }
241
    return false;
242
}
243
244
/// Check every reachable pair. Invalid table indices are mismatches.
245
fn finish(work: &mut Workspace, left: &il::Program, right: &il::Program) -> bool throws (Error) {
246
    let mut cursor: u32 = 0;
247
    while cursor < work.count {
248
        let pair = work.pairs[cursor];
249
        set cursor += 1;
250
        match pair.kind {
251
            case Kind::Layout => {
252
                if pair.left >= left.layouts.len or pair.right >= right.layouts.len {
253
                    return false;
254
                }
255
                let a = left.layouts[pair.left];
256
                let b = right.layouts[pair.right];
257
                if a.size <> b.size
258
                    or a.alignment <> b.alignment
259
                    or a.regions <> b.regions
260
                    or a.slots.len <> b.slots.len
261
                {
262
                    return false;
263
                }
264
                for item, i in a.slots {
265
                    let other = b.slots[i];
266
                    if item.offset <> other.offset
267
                        or not regions(item.regions, other.regions)
268
                        or not try slot(work, item.kind, other.kind)
269
                    {
270
                        return false;
271
                    }
272
                }
273
            }
274
            case Kind::Signature => {
275
                if pair.left >= left.signatures.len or pair.right >= right.signatures.len {
276
                    return false;
277
                }
278
                let a = left.signatures[pair.left];
279
                let b = right.signatures[pair.right];
280
                if a.params.len <> b.params.len
281
                    or not il::sameBorrows(a.borrows, b.borrows)
282
                    or not try value(work, a.ret, b.ret)
283
                {
284
                    return false;
285
                }
286
                for param, i in a.params {
287
                    if not try value(work, param, b.params[i]) {
288
                        return false;
289
                    }
290
                }
291
            }
292
            case Kind::Trait => {
293
                if pair.left >= left.traits.len or pair.right >= right.traits.len {
294
                    return false;
295
                }
296
                let a = left.traits[pair.left];
297
                let b = right.traits[pair.right];
298
                if a.methods.len <> b.methods.len {
299
                    return false;
300
                }
301
                for method, i in a.methods {
302
                    let other = b.methods[i];
303
                    if method.receiver <> other.receiver
304
                        or method.own <> other.own
305
                        or method.mutable <> other.mutable
306
                    {
307
                        return false;
308
                    }
309
                    try edge(work, Kind::Signature, method.sig, other.sig);
310
                }
311
            }
312
        }
313
    }
314
    return true;
315
}
316
317
/// Compare complete layout graphs across program-local indices.
318
export fn sameLayout(
319
    work: &mut Workspace, left: &il::Program, a: u32, right: &il::Program, b: u32
320
) -> bool throws (Error) {
321
    reset(work);
322
    try edge(work, Kind::Layout, a, b);
323
    return try finish(work, left, right);
324
}
325
326
/// Compare data declarations and their reachable layout graphs.
327
export fn sameData(
328
    work: &mut Workspace, left: &il::Program, a: &il::Data, right: &il::Program, b: &il::Data
329
) -> bool throws (Error) {
330
    if a.size <> b.size
331
        or a.alignment <> b.alignment
332
        or a.readOnly <> b.readOnly
333
        or a.heap <> b.heap
334
    {
335
        return false;
336
    }
337
    return try sameLayout(work, left, a.layout, right, b.layout);
338
}
339
340
/// Compare an importing signature with a provider's declared function.
341
export fn sameCallable(
342
    work: &mut Workspace, left: &il::Program, a: &il::Signature, right: &il::Program, b: &il::Fn
343
) -> bool throws (Error) {
344
    reset(work);
345
    if a.params.len <> b.params.len
346
        or not il::sameBorrows(a.borrows, b.borrows)
347
        or not try value(work, a.ret, b.returnType)
348
    {
349
        return false;
350
    }
351
    for param, i in a.params {
352
        if not try value(work, param, b.params[i].type) {
353
            return false;
354
        }
355
    }
356
    return try finish(work, left, right);
357
}