lib/std/lang/il/verify/layout.rad 30.9 KiB raw
1
//! Layout table checks and queries of the RIL verifier.
2
//!
3
//! A layout lists the slots of an object, the byte ranges that hold pointers,
4
//! slices, function values, trait objects and unions. All other bytes are plain data. The decoder
5
//! establishes that slots are sorted, aligned, disjoint and inside the size, and
6
//! that nested layouts have lower indices than the layouts that contain them.
7
//! The queries here rely on that, and on table indices that are in range.
8
//!
9
//! Descent through nested layouts is bounded by [`verify::Config::layoutDepth`],
10
//! which [`build`] checks, so no query recurses deeper than that.
11
12
use std::mem::heap;
13
use std::lang::il;
14
use std::lang::il::verify;
15
16
/// Size in bytes of a pointer or function slot.
17
export constant WORD: u64 = 8;
18
/// Size in bytes of a slice slot: pointer, length and capacity.
19
constant SLICE: u64 = 16;
20
/// Size in bytes of a trait object slot: receiver and method table.
21
constant TRAIT: u64 = 16;
22
23
/// Facts about a layout, computed once for the whole table.
24
export record Info: Copy {
25
    /// Nesting depth of sub and array nodes. A layout without such nodes has depth zero.
26
    depth: u32,
27
    /// Offset of the first byte that a pointer, slice, function or trait object slot
28
    /// protects, also in nested nodes, or nil when the layout is plain data.
29
    first: ?u64,
30
    /// Whether the layout has a slot that is written together, a slice, a trait object or a
31
    /// union, also in nested nodes.
32
    pairs: bool,
33
    /// Regions that can change through mutable pointers copied from this layout.
34
    shared: *[bool],
35
    /// Whether such a slot is reachable from the layout: it has one, or a pointer slot, also
36
    /// in nested nodes, whose pointee reaches one.
37
    reaches: bool,
38
}
39
40
/// A checked layout table.
41
export record Table: Copy {
42
    /// The layouts of the program.
43
    layouts: *[il::Layout],
44
    /// Facts about each layout, in table order.
45
    infos: *[Info],
46
}
47
48
/// A leaf slot found by a query.
49
export record Leaf: Copy {
50
    /// Byte offset of the slot from the start of the queried layout.
51
    start: u64,
52
    /// What the slot holds. Never a sub or array.
53
    kind: il::SlotKind,
54
}
55
56
/// A position inside a layout.
57
record At: Copy {
58
    /// Layout index.
59
    layout: u32,
60
    /// Byte offset from the start of the layout.
61
    offset: u64,
62
}
63
64
/// Build the error for a rule violation at layout `index`.
65
fn fail(index: u32, rule: verify::Rule) -> verify::Error {
66
    return verify::Error { rule, place: verify::Place::Layout(index) };
67
}
68
69
/// Add the facts of a nested layout to those of its container.
70
fn absorb(info: &mut Info, child: Info) {
71
    if child.depth + 1 > info.depth {
72
        set info.depth = child.depth + 1;
73
    }
74
    set info.pairs = info.pairs or child.pairs;
75
}
76
77
/// A layout that depends on a child for pair reachability.
78
record ReachEdge: Copy {
79
    /// Index of the parent layout.
80
    parent: u32,
81
    /// Next parent of the same child.
82
    next: ?u32,
83
}
84
85
/// Child whose reachable pairs are also reachable from this slot.
86
fn reachTarget(kind: il::SlotKind) -> ?u32 {
87
    match kind {
88
        case il::SlotKind::Ptr(p)     => return p.layout,
89
        case il::SlotKind::Sub(child) => return child,
90
        case il::SlotKind::Array { layout: child, count } => {
91
            if count > 0 {
92
                return child;
93
            }
94
            return nil;
95
        }
96
        else => return nil,
97
    }
98
}
99
100
/// Check the layout table against the limits of `config` and compute the facts about each
101
/// layout. Each slot and variant maps its region positions to regions of its layout.
102
export fn build(layouts: *[il::Layout], config: verify::Config, a: &heap::Heap) -> Table
103
    throws (verify::Error)
104
{
105
    let mut infos: *mut [Info] = &mut [];
106
    try infos.reserve(layouts.len, a) catch {
107
        throw verify::STORAGE;
108
    };
109
    for i in 0 .. layouts.len {
110
        let layout = layouts[i];
111
        if layout.size > config.layoutSize {
112
            throw fail(i, verify::Rule::Limit);
113
        }
114
        let mut info = Info {
115
            depth: 0, first: nil, pairs: false, shared: &[], reaches: false
116
        };
117
        for slot in layout.slots {
118
            match slot.kind {
119
                case il::SlotKind::Slice(_), il::SlotKind::Trait(_) => set info.pairs = true,
120
                case il::SlotKind::Ptr(_), il::SlotKind::Fn(_), il::SlotKind::Heap(_) => {}
121
                case il::SlotKind::Union { offset, size: width, variants } => {
122
                    set info.pairs = true;
123
                    if offset == 0 or width == 0 {
124
                        throw fail(i, verify::Rule::Layout);
125
                    }
126
                    let mut seen: [bool; 256] = [false; 256];
127
                    for variant in variants {
128
                        if variant.tag > 255 or seen[variant.tag] {
129
                            throw fail(i, verify::Rule::Layout);
130
                        }
131
                        set seen[variant.tag] = true;
132
                        let child = variant.layout else {
133
                            continue;
134
                        };
135
                        // The payload is an object of the variant layout inside the slot.
136
                        if child >= i
137
                            or offset % layouts[child].alignment <> 0
138
                            or offset as u64 + layouts[child].size as u64 > width as u64
139
                        {
140
                            throw fail(i, verify::Rule::Layout);
141
                        }
142
                        absorb(&mut info, infos[child]);
143
                    }
144
                }
145
                case il::SlotKind::Sub(child) => {
146
                    if child >= i {
147
                        throw fail(i, verify::Rule::Layout);
148
                    }
149
                    absorb(&mut info, infos[child]);
150
                }
151
                case il::SlotKind::Array { layout: child, count } => {
152
                    if child >= i {
153
                        throw fail(i, verify::Rule::Layout);
154
                    }
155
                    // An empty array holds nothing, but it still nests.
156
                    if count > 0 {
157
                        absorb(&mut info, infos[child]);
158
                    }
159
                }
160
            }
161
        }
162
        if info.depth > config.layoutDepth {
163
            throw fail(i, verify::Rule::Limit);
164
        }
165
        set info.first = firstOfSlots(&infos[..], &layout.slots[..]);
166
        set info.reaches = info.pairs;
167
        try infos.append(info, a) catch {
168
            throw verify::STORAGE;
169
        };
170
    }
171
    // Pointer pointees can have any index, so their facts are known only now.
172
    for i in 0 .. layouts.len {
173
        for slot in layouts[i].slots {
174
            if not mapsRegions(layouts, i, slot.regions, slotPositions(layouts, slot.kind)) {
175
                throw fail(i, verify::Rule::Layout);
176
            }
177
            if let case il::SlotKind::Union { variants, .. } = slot.kind {
178
                for variant in variants {
179
                    let mut count: u32 = 0;
180
                    if let child = variant.layout {
181
                        set count = layouts[child].regions;
182
                    }
183
                    if not mapsRegions(layouts, i, variant.regions, count) {
184
                        throw fail(i, verify::Rule::Layout);
185
                    }
186
                }
187
            }
188
        }
189
    }
190
    try sharedRegions(layouts, &mut infos[..], a);
191
    // A pair is reachable through pointers when a pointee has one. Pointees can have any index,
192
    // so the facts are propagated until they stop changing.
193
    let mut work: *mut [u32] = &mut [];
194
    try work.reserve(layouts.len, a) catch {
195
        throw verify::STORAGE;
196
    };
197
    for i in 0 .. infos.len {
198
        if infos[i].reaches {
199
            try work.append(i, a) catch {
200
                throw verify::STORAGE;
201
            };
202
        }
203
    }
204
    if work.len == 0 {
205
        return Table { layouts, infos: &infos[..] };
206
    }
207
    let mut edgeCount: u32 = 0;
208
    for item, i in layouts {
209
        if infos[i].reaches {
210
            continue;
211
        }
212
        for slot in item.slots {
213
            if reachTarget(slot.kind) <> nil {
214
                set edgeCount += 1;
215
            }
216
        }
217
    }
218
    let mut heads: *mut [?u32] = &mut [];
219
    let mut edges: *mut [ReachEdge] = &mut [];
220
    try heads.resize(layouts.len, nil, a) catch {
221
        throw verify::STORAGE;
222
    };
223
    try edges.reserve(edgeCount, a) catch {
224
        throw verify::STORAGE;
225
    };
226
    for item, i in layouts {
227
        if infos[i].reaches {
228
            continue;
229
        }
230
        for slot in item.slots {
231
            if let child = reachTarget(slot.kind) {
232
                let index = edges.len;
233
                try edges.append(ReachEdge { parent: i, next: heads[child] }, a) catch {
234
                    throw verify::STORAGE;
235
                };
236
                set heads[child] = index;
237
            }
238
        }
239
    }
240
    let mut at: u32 = 0;
241
    while at < work.len {
242
        let mut edge = heads[work[at]];
243
        while let index = edge {
244
            let parent = edges[index].parent;
245
            if not infos[parent].reaches {
246
                set infos[parent].reaches = true;
247
                try work.append(parent, a) catch {
248
                    throw verify::STORAGE;
249
                };
250
            }
251
            set edge = edges[index].next;
252
        }
253
        set at += 1;
254
    }
255
    return Table { layouts, infos: &infos[..] };
256
}
257
258
/// Compute regions shared through copied mutable pointers. Read-only pointer
259
/// paths can reach mutable pointers, and recursive layouts require a fixed point.
260
fn sharedRegions(layouts: *[il::Layout], infos: &mut [Info], a: &heap::Heap)
261
    throws (verify::Error)
262
{
263
    let mut facts: *mut [bool] = &mut [];
264
    let mut starts: *mut [u32] = &mut [];
265
    for item in layouts {
266
        try starts.append(facts.len, a) catch {
267
            throw verify::STORAGE;
268
        };
269
        for _ in 0 .. item.regions {
270
            try facts.append(false, a) catch {
271
                throw verify::STORAGE;
272
            };
273
        }
274
    }
275
    let mut changed = true;
276
    while changed {
277
        set changed = false;
278
        for item, l in layouts {
279
            for slot in item.slots {
280
                for region, position in slot.regions {
281
                    if not facts[starts[l] + region]
282
                        and sharedPosition(&facts[..], &starts[..], slot.kind, position)
283
                    {
284
                        set facts[starts[l] + region] = true;
285
                        set changed = true;
286
                    }
287
                }
288
                if let case il::SlotKind::Union { variants, .. } = slot.kind {
289
                    for variant in variants {
290
                        let child = variant.layout else continue;
291
                        for region, position in variant.regions {
292
                            if not facts[starts[l] + region] and facts[starts[child] + position] {
293
                                set facts[starts[l] + region] = true;
294
                                set changed = true;
295
                            }
296
                        }
297
                    }
298
                }
299
            }
300
        }
301
    }
302
    let values: *[bool] = &facts[..];
303
    for i in 0 .. infos.len {
304
        set infos[i].shared = &values[starts[i] .. starts[i] + layouts[i].regions];
305
    }
306
}
307
308
/// Whether a copied slot shares its region position through a mutable pointer.
309
fn sharedPosition(
310
    facts: &[bool], starts: &[u32], kind: il::SlotKind, position: u32
311
) -> bool {
312
    if let p = pointerSlot(kind) {
313
        let address: u32 = 0 if p.own else 1;
314
        if position < address {
315
            return false;
316
        }
317
        return p.mutable or facts[starts[p.layout] + position - address];
318
    }
319
    match kind {
320
        case il::SlotKind::Sub(child) => return facts[starts[child] + position],
321
        case il::SlotKind::Array { layout: child, count } =>
322
            return count > 0 and facts[starts[child] + position],
323
        else => return false,
324
    }
325
}
326
327
/// Size in bytes of layout `l`.
328
export fn size(t: &Table, l: u32) -> u64 {
329
    return t.layouts[l].size as u64;
330
}
331
332
/// Whether layout `l` is plain data, without any slot.
333
export fn isPlain(t: &Table, l: u32) -> bool {
334
    return t.infos[l].first == nil;
335
}
336
337
/// Number of bytes that a slot of kind `kind` covers. A union slot covers its tag and payload.
338
export fn slotWidth(t: &Table, kind: il::SlotKind) -> u64 {
339
    return width(t.layouts, kind);
340
}
341
342
/// Byte width of a slot in a layout table.
343
fn width(layouts: &[il::Layout], kind: il::SlotKind) -> u64 {
344
    match kind {
345
        case il::SlotKind::Ptr(_), il::SlotKind::Fn(_), il::SlotKind::Heap(_) => return WORD,
346
        case il::SlotKind::Slice(_) => return SLICE,
347
        case il::SlotKind::Trait(_) => return TRAIT,
348
        case il::SlotKind::Union { size: width, .. } => return width as u64,
349
        case il::SlotKind::Sub(child) => return layouts[child].size as u64,
350
        case il::SlotKind::Array { layout, count } =>
351
            return layouts[layout].size as u64 * count as u64,
352
    }
353
}
354
355
/// Index of the first slot in `slots` that ends after byte `o`. Slots are sorted and do not
356
/// overlap, so their ends increase.
357
fn firstEndingAfter(layouts: &[il::Layout], slots: *[il::Slot], o: u64) -> u32 {
358
    let mut low: u32 = 0;
359
    let mut high: u32 = slots.len;
360
    while low < high {
361
        let mid = low + (high - low) / 2;
362
        if slots[mid].offset as u64 + width(layouts, slots[mid].kind) > o {
363
            set high = mid;
364
        } else {
365
            set low = mid + 1;
366
        }
367
    }
368
    return low;
369
}
370
371
/// Find the slot of layout `l` that covers byte `o`, if any.
372
fn covering(layouts: &[il::Layout], l: u32, o: u64) -> ?il::Slot {
373
    let slots = layouts[l].slots;
374
    let i = firstEndingAfter(layouts, slots, o);
375
    if i < slots.len and slots[i].offset as u64 <= o {
376
        return slots[i];
377
    }
378
    return nil;
379
}
380
381
/// Step into the nested object or array element that covers `at`, if any.
382
fn inner(t: &Table, at: At) -> ?At {
383
    let slot = covering(t.layouts, at.layout, at.offset) else {
384
        return nil;
385
    };
386
    return enter(t.layouts, slot, at.offset);
387
}
388
389
/// Enter the nested object or array element of `slot` that covers offset `o` of its layout.
390
/// A leaf slot has no inside.
391
fn enter(layouts: &[il::Layout], slot: il::Slot, o: u64) -> ?At {
392
    match slot.kind {
393
        case il::SlotKind::Sub(child) =>
394
            return At { layout: child, offset: o - slot.offset as u64 },
395
        // The slot covers a byte, so the element size is not zero.
396
        case il::SlotKind::Array { layout, .. } =>
397
            return At { layout, offset: (o - slot.offset as u64) % layouts[layout].size as u64 },
398
        else => return nil,
399
    }
400
}
401
402
/// Find the leaf slot that covers byte `o` of layout `l`, looking through nested objects.
403
export fn leafAround(t: &Table, l: u32, o: u64) -> ?Leaf {
404
    let mut at = At { layout: l, offset: o };
405
    loop {
406
        let slot = covering(t.layouts, at.layout, at.offset) else {
407
            return nil;
408
        };
409
        if let next = enter(t.layouts, slot, at.offset) {
410
            set at = next;
411
            continue;
412
        }
413
        return Leaf { start: o - at.offset + slot.offset as u64, kind: slot.kind };
414
    }
415
}
416
417
/// Find the variant of a union slot with the given tag.
418
export fn variantWith(variants: *[il::UnionVariant], tag: u64) -> ?il::UnionVariant {
419
    for variant in variants {
420
        if variant.tag as u64 == tag {
421
            return variant;
422
        }
423
    }
424
    return nil;
425
}
426
427
/// Find the leaf slot that starts exactly at byte `o` of layout `l`.
428
export fn slotAt(t: &Table, l: u32, o: u64) -> ?il::SlotKind {
429
    if let leaf = leafAround(t, l, o) {
430
        if leaf.start == o {
431
            return leaf.kind;
432
        }
433
    }
434
    return nil;
435
}
436
437
/// Offset of the first protected byte of a slot of kind `kind`, from the start of the slot,
438
/// or nil when the slot protects none. `infos` has the facts about the nested layouts.
439
fn protectedStart(infos: &[Info], kind: il::SlotKind) -> ?u64 {
440
    match kind {
441
        case
442
            il::SlotKind::Ptr(_),
443
            il::SlotKind::Fn(_),
444
            il::SlotKind::Heap(_),
445
            il::SlotKind::Slice(_),
446
            il::SlotKind::Trait(_),
447
            il::SlotKind::Union { .. } => return 0,
448
        case il::SlotKind::Sub(child) => return infos[child].first,
449
        case il::SlotKind::Array { layout, count } => {
450
            if count == 0 {
451
                return nil;
452
            }
453
            return infos[layout].first;
454
        }
455
    }
456
}
457
458
/// Offset of the first protected byte of a layout with the sorted `slots`, or nil when the
459
/// slots protect none. `infos` has the facts about the layouts that the slots nest.
460
fn firstOfSlots(infos: &[Info], slots: &[il::Slot]) -> ?u64 {
461
    for slot in slots {
462
        if let f = protectedStart(infos, slot.kind) {
463
            return slot.offset as u64 + f;
464
        }
465
    }
466
    return nil;
467
}
468
469
/// Offset of the first protected byte of `slot` at or after byte `rel` of the slot, from the
470
/// start of the slot, or nil when there is none. The byte `rel` must lie inside the slot.
471
fn protectedFrom(t: &Table, slot: il::Slot, rel: u64) -> ?u64 {
472
    match slot.kind {
473
        case
474
            il::SlotKind::Ptr(_),
475
            il::SlotKind::Fn(_),
476
            il::SlotKind::Heap(_),
477
            il::SlotKind::Slice(_),
478
            il::SlotKind::Trait(_),
479
            il::SlotKind::Union { .. } => return rel,
480
        case il::SlotKind::Sub(child) => return firstProtected(t, child, rel),
481
        case il::SlotKind::Array { layout, count } => {
482
            // The slot covers a byte, so the element size is not zero.
483
            let element = size(t, layout);
484
            let index = rel / element;
485
            if let f = firstProtected(t, layout, rel % element) {
486
                return index * element + f;
487
            }
488
            // The element has no protected byte left, so the next one decides.
489
            if index + 1 < count as u64 {
490
                if let f = t.infos[layout].first {
491
                    return (index + 1) * element + f;
492
                }
493
            }
494
            return nil;
495
        }
496
    }
497
}
498
499
/// Offset of the first protected byte of layout `l` at or after byte `lo`, or nil when there
500
/// is none. It descends one path through the nested layouts: only the slot that covers `lo`
501
/// is searched, and the slots after it are answered by the facts of the table.
502
fn firstProtected(t: &Table, l: u32, lo: u64) -> ?u64 {
503
    let slots = t.layouts[l].slots;
504
    let mut i = firstEndingAfter(t.layouts, slots, lo);
505
    if i < slots.len and slots[i].offset as u64 <= lo {
506
        let start = slots[i].offset as u64;
507
        if let f = protectedFrom(t, slots[i], lo - start) {
508
            return start + f;
509
        }
510
        set i += 1;
511
    }
512
    return firstOfSlots(&t.infos[..], &slots[i ..]);
513
}
514
515
/// Whether bytes `lo..hi` of layout `l` hold no protected byte. The capacity of a slice is
516
/// plain. The cost is linear in the nesting depth of the layout.
517
export fn plain(t: &Table, l: u32, lo: u64, hi: u64) -> bool {
518
    if hi <= lo {
519
        return true;
520
    }
521
    let first = firstProtected(t, l, lo) else {
522
        return true;
523
    };
524
    return first >= hi;
525
}
526
527
/// Alignment in bytes of layout `l`.
528
export fn alignment(t: &Table, l: u32) -> u64 {
529
    return t.layouts[l].alignment as u64;
530
}
531
532
/// Whether the `width` bytes at byte `o` of layout `l` are a plain region that an object of
533
/// `boundary` bytes of alignment can occupy. The object of `l` is aligned to its alignment, so `o`
534
/// must be a multiple of `boundary`, and `l` must be at least as aligned.
535
export fn plainRegion(t: &Table, l: u32, o: u64, width: u64, boundary: u64) -> bool {
536
    return o + width <= size(t, l)
537
        and plain(t, l, o, o + width)
538
        and o % boundary == 0
539
        and boundary <= alignment(t, l);
540
}
541
542
/// Whether a pointer to layout `l` at byte `o` can be used as a pointer to layout `m`.
543
/// A plain `m` fits any plain region of `l` that is inside it and aligned for `m`. Any other
544
/// `m` must be `l` itself, or a nested object or array element that starts at `o`, which the
545
/// layout checks of the decoder align.
546
export fn view(t: &Table, l: u32, o: u64, m: u32) -> bool {
547
    if isPlain(t, m) {
548
        return plainRegion(t, l, o, size(t, m), alignment(t, m));
549
    }
550
    let mut at = At { layout: l, offset: o };
551
    while not (at.offset == 0 and at.layout == m) {
552
        let next = inner(t, at) else {
553
            return false;
554
        };
555
        set at = next;
556
    }
557
    return true;
558
}
559
560
/// Whether an object of layout `m` can be read at byte `o` of layout `l`.
561
/// A read can reduce slot rights while preserving shape and region positions.
562
export fn holds(t: &Table, l: u32, o: u64, m: u32) -> bool {
563
    if view(t, l, o, m) {
564
        return true;
565
    }
566
    let mut at = At { layout: l, offset: o };
567
    loop {
568
        if at.offset == 0 and readsLayout(t, at.layout, m) {
569
            return true;
570
        }
571
        let next = inner(t, at) else {
572
            break;
573
        };
574
        set at = next;
575
    }
576
    let slots = t.layouts[m].slots;
577
    if slots.len <> 1 or slots[0].offset <> 0 or slotWidth(t, slots[0].kind) <> size(t, m) {
578
        return false;
579
    }
580
    let kind = slotAt(t, l, o) else {
581
        return false;
582
    };
583
    return reads(t, kind, slots[0].kind);
584
}
585
586
/// Whether two complete layouts have the same shape and region maps, with
587
/// the same or fewer rights in the layout being read.
588
fn readsLayout(t: &Table, have: u32, want: u32) -> bool {
589
    if have == want {
590
        return true;
591
    }
592
    let a = t.layouts[have];
593
    let b = t.layouts[want];
594
    if a.size <> b.size
595
        or a.alignment <> b.alignment
596
        or a.regions <> b.regions
597
        or a.slots.len <> b.slots.len
598
    {
599
        return false;
600
    }
601
    for slot, i in a.slots {
602
        let next = b.slots[i];
603
        if slot.offset <> next.offset
604
            or slot.regions.len <> next.regions.len
605
            or not reads(t, slot.kind, next.kind)
606
        {
607
            return false;
608
        }
609
        for region, k in slot.regions {
610
            if region <> next.regions[k] {
611
                return false;
612
            }
613
        }
614
    }
615
    return true;
616
}
617
618
/// Rights and pointee type of a pointer or slice slot.
619
fn pointerSlot(kind: il::SlotKind) -> ?il::PtrType {
620
    match kind {
621
        case il::SlotKind::Ptr(p)   => return p,
622
        case il::SlotKind::Slice(p) => return p,
623
        else                        => return nil,
624
    }
625
}
626
627
/// Whether a slot can be read as another slot with the same or fewer rights.
628
/// Nested layouts preserve shape and region maps.
629
fn reads(t: &Table, a: il::SlotKind, b: il::SlotKind) -> bool {
630
    if let want = pointerSlot(b) {
631
        let have = pointerSlot(a) else {
632
            return false;
633
        };
634
        // Pointer and slice slots have different widths.
635
        return slotWidth(t, a) == slotWidth(t, b) and fewerRights(want, have);
636
    }
637
    match b {
638
        case il::SlotKind::Heap(want) => {
639
            let case il::SlotKind::Heap(have) = a else {
640
                return false;
641
            };
642
            return heapFits(have, want);
643
        }
644
        case il::SlotKind::Trait(want) => {
645
            let case il::SlotKind::Trait(have) = a else {
646
                return false;
647
            };
648
            return want.iface == have.iface
649
                and want.own == have.own
650
                and (have.mutable or not want.mutable);
651
        }
652
        case il::SlotKind::Sub(want) => {
653
            let case il::SlotKind::Sub(have) = a else {
654
                return false;
655
            };
656
            return readsLayout(t, have, want);
657
        }
658
        case il::SlotKind::Array { layout: want, count } => {
659
            let case il::SlotKind::Array { layout: have, count: length } = a else {
660
                return false;
661
            };
662
            return count == length and readsLayout(t, have, want);
663
        }
664
        else => {}
665
    }
666
    let case il::SlotKind::Union { offset, size, variants } = a else {
667
        return a == b;
668
    };
669
    let case il::SlotKind::Union { offset: other, size: width, variants: others } = b else {
670
        return false;
671
    };
672
    if offset <> other or size <> width or variants.len <> others.len {
673
        return false;
674
    }
675
    for variant, i in variants {
676
        let next = others[i];
677
        if variant.tag <> next.tag or variant.regions.len <> next.regions.len {
678
            return false;
679
        }
680
        if let child = variant.layout {
681
            let target = next.layout else {
682
                return false;
683
            };
684
            if not readsLayout(t, child, target) {
685
                return false;
686
            }
687
        } else if next.layout <> nil {
688
            return false;
689
        }
690
        for region, k in variant.regions {
691
            if region <> next.regions[k] {
692
                return false;
693
            }
694
        }
695
    }
696
    return true;
697
}
698
699
/// Whether a heap handle can be used with the declared rights.
700
export fn heapFits(have: il::HeapType, want: il::HeapType) -> bool {
701
    return want == il::HeapType::Plain or have == want;
702
}
703
704
/// Whether pointer type `want` is `have` with the same or fewer rights.
705
fn fewerRights(want: il::PtrType, have: il::PtrType) -> bool {
706
    return want.layout == have.layout
707
        and want.own == have.own
708
        and want.nullable == have.nullable
709
        and (have.mutable or not want.mutable);
710
}
711
712
/// Whether a pointer to layout `l` at byte `o` can be used as a pointer to `count` consecutive
713
/// objects of layout `e`. A plain `e` needs a plain region that is inside `l`. Any other
714
/// `e` needs an array node of `e` with at least that count, or a single object that is a view.
715
export fn arrayView(t: &Table, l: u32, o: u64, e: u32, count: u32) -> bool {
716
    let total = size(t, e) * count as u64;
717
    if o + total > size(t, l) {
718
        return false;
719
    }
720
    if isPlain(t, e) {
721
        return plainRegion(t, l, o, total, alignment(t, e));
722
    }
723
    if count == 1 {
724
        return view(t, l, o, e);
725
    }
726
    let mut at = At { layout: l, offset: o };
727
    loop {
728
        let slot = covering(t.layouts, at.layout, at.offset) else {
729
            return false;
730
        };
731
        if slot.offset as u64 == at.offset {
732
            if let case il::SlotKind::Array { layout, count: n } = slot.kind {
733
                if layout == e and n >= count {
734
                    return true;
735
                }
736
            }
737
        }
738
        let next = enter(t.layouts, slot, at.offset) else {
739
            return false;
740
        };
741
        set at = next;
742
    }
743
}
744
745
/// Whether `regions` maps `count` positions to regions of layout `l`.
746
fn mapsRegions(layouts: &[il::Layout], l: u32, regions: *[u32], count: u32) -> bool {
747
    if regions.len <> count {
748
        return false;
749
    }
750
    for region in regions {
751
        if region >= layouts[l].regions {
752
            return false;
753
        }
754
    }
755
    return true;
756
}
757
758
/// Whether a slot holds a non-owning pointer, slice or trait object, whose
759
/// address is its first region position.
760
fn borrows(kind: il::SlotKind) -> bool {
761
    match kind {
762
        case il::SlotKind::Ptr(p)        => return not p.own,
763
        case il::SlotKind::Slice(p)      => return not p.own,
764
        case il::SlotKind::Trait(object) => return not object.own,
765
        else                             => return false,
766
    }
767
}
768
769
/// Number of region positions of a slot: the address of a non-owning pointer,
770
/// slice or trait object, then the regions of its pointee, element or nested
771
/// layout. A union maps the regions of its payloads in its variants.
772
export fn slotPositions(layouts: &[il::Layout], kind: il::SlotKind) -> u32 {
773
    let address: u32 = 1 if borrows(kind) else 0;
774
    match kind {
775
        case il::SlotKind::Ptr(p)               => return address + layouts[p.layout].regions,
776
        case il::SlotKind::Slice(p)             => return address + layouts[p.layout].regions,
777
        case il::SlotKind::Sub(child)           => return layouts[child].regions,
778
        case il::SlotKind::Array { layout, .. } => return layouts[layout].regions,
779
        else                                    => return address,
780
    }
781
}
782
783
/// Region of layout `l` for region `i` of the object of layout `view` at byte
784
/// `o`, or nil when that region holds nothing there. Array elements share the
785
/// regions of their element layout.
786
export fn viewRegion(t: &Table, l: u32, o: u64, view: u32, i: u32) -> ?u32 {
787
    if l == view and o == 0 {
788
        return i;
789
    }
790
    if o == 0 and readsLayout(t, l, view) {
791
        return i;
792
    }
793
    let slot = covering(t.layouts, l, o) else return nil;
794
    if let child = enter(t.layouts, slot, o) {
795
        let region = viewRegion(t, child.layout, child.offset, view, i) else return nil;
796
        return slot.regions[region];
797
    }
798
    // A layout of a single slot views the same slot of `l`, as in [`holds`].
799
    let slots = t.layouts[view].slots;
800
    if slots.len <> 1 or slot.offset as u64 <> o {
801
        return nil;
802
    }
803
    if let found = sameRegion(slots[0].regions, slot.regions, i) {
804
        return found;
805
    }
806
    // A union slot maps the regions of its payloads in its variants.
807
    let case il::SlotKind::Union { variants: inner, .. } = slots[0].kind else return nil;
808
    let case il::SlotKind::Union { variants: outer, .. } = slot.kind else return nil;
809
    for variant, k in inner {
810
        if let found = sameRegion(variant.regions, outer[k].regions, i) {
811
            return found;
812
        }
813
    }
814
    return nil;
815
}
816
817
/// Region of `outer` at the first position where `inner` has region `i`.
818
fn sameRegion(inner: *[u32], outer: *[u32], i: u32) -> ?u32 {
819
    for region, k in inner {
820
        if region == i {
821
            return outer[k];
822
        }
823
    }
824
    return nil;
825
}
826
827
/// Region of layout `l` for position `k` of the leaf slot that starts at byte `o`.
828
fn leafRegion(t: &Table, l: u32, o: u64, k: u32) -> ?u32 {
829
    let slot = covering(t.layouts, l, o) else return nil;
830
    if let child = enter(t.layouts, slot, o) {
831
        let region = leafRegion(t, child.layout, child.offset, k) else return nil;
832
        return slot.regions[region];
833
    }
834
    if slot.offset as u64 <> o or k >= slot.regions.len {
835
        return nil;
836
    }
837
    return slot.regions[k];
838
}
839
840
/// Region of layout `l` for the address of the non-owning pointer, slice or
841
/// trait object slot that starts at byte `o`, if there is one.
842
export fn addressRegion(t: &Table, l: u32, o: u64) -> ?u32 {
843
    let kind = slotAt(t, l, o) else return nil;
844
    if not borrows(kind) {
845
        return nil;
846
    }
847
    return leafRegion(t, l, o, 0);
848
}
849
850
/// Region of layout `l` for region `i` of the pointee or element layout of the
851
/// pointer or slice slot that starts at byte `o`.
852
export fn pointeeRegion(t: &Table, l: u32, o: u64, i: u32) -> ?u32 {
853
    let kind = slotAt(t, l, o) else return nil;
854
    let address: u32 = 1 if borrows(kind) else 0;
855
    return leafRegion(t, l, o, address + i);
856
}
857
858
/// Region of layout `l` for region `i` of the payload of variant `tag` of the
859
/// union slot at byte `o`.
860
export fn variantRegion(t: &Table, l: u32, o: u64, tag: u32, i: u32) -> ?u32 {
861
    let slot = covering(t.layouts, l, o) else return nil;
862
    if let child = enter(t.layouts, slot, o) {
863
        let region = variantRegion(t, child.layout, child.offset, tag, i) else return nil;
864
        return slot.regions[region];
865
    }
866
    let case il::SlotKind::Union { variants, .. } = slot.kind else return nil;
867
    if slot.offset as u64 <> o {
868
        return nil;
869
    }
870
    let variant = variantWith(variants, tag as u64) else return nil;
871
    if i >= variant.regions.len {
872
        return nil;
873
    }
874
    return variant.regions[i];
875
}