.githooks/
compiler/
kernel/
lib/
examples/
std/
arch/
bits/
char/
collections/
fs/
hash/
lang/
alloc/
ast/
gen/
il/
binary/
link/
printer/
verify/
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/link.rad
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 | } |