.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
bits/
char/
collections/
fs/
hash/
lang/
alloc/
ast/
gen/
il/
binary/
link/
printer/
verify/
data.rad
12.4 KiB
flow.rad
6.9 KiB
layout.rad
30.9 KiB
linking.rad
7.2 KiB
tests.rad
216.6 KiB
binary.rad
14.7 KiB
link.rad
11.8 KiB
printer.rad
31.7 KiB
verify.rad
99.5 KiB
layout/
lower/
manifest/
module/
parser/
resolver/
scanner/
sexpr/
alloc.rad
1.2 KiB
ast.rad
36.0 KiB
gen.rad
513 B
il.rad
48.5 KiB
layout.rad
6.9 KiB
lower.rad
487.6 KiB
manifest.rad
22.5 KiB
module.rad
17.8 KiB
package.rad
1.5 KiB
parser.rad
114.1 KiB
pretty.rad
103.6 KiB
resolver.rad
508.1 KiB
scanner.rad
19.3 KiB
sexpr.rad
7.1 KiB
strings.rad
3.3 KiB
types.rad
620 B
mem/
sys/
arch.rad
68 B
bits.rad
1.6 KiB
char.rad
1.5 KiB
collections.rad
39 B
fmt.rad
11.6 KiB
fs.rad
11.0 KiB
hash.rad
41 B
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
335 B
mem.rad
12.0 KiB
mem.ras
919 B
process.rad
6.2 KiB
std.manifest
4.9 KiB
std.rad
349 B
sys.rad
1.0 KiB
testing.rad
2.4 KiB
tests.rad
26.6 KiB
vec.rad
3.2 KiB
scripts/
seed/
sublime/
test/
vim/
.gitignore
333 B
.gitsigners
224 B
AGENTS.md
8.3 KiB
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
2.5 KiB
README
3.4 KiB
STYLE
3.2 KiB
std.lib
2.1 KiB
std.lib.test
1.1 KiB
lib/std/lang/il/verify/layout.rad
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 | } |