1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
//! The **read interpreter** — schema over a live data file → a [`Value`] tree, with no
//! compiled-in types. The non-recursive counterpart of a typed block read: it follows
//! owning edges into child blocks and stops (recording just the offset) at non-owning
//! ones, which also breaks reference cycles.
use std::collections::HashMap;
use bstack::BStack;
use crate::primitives::{EightCC, WidePtr};
use crate::util::read_u64;
use super::walk::{checked_vec_len, pop_n, pop_named};
use super::{
AnyRef, BYTEVEC_HEADER, RttiBody, RttiOrdinal, RttiRegistry, RttiType, Shape, Value, add_off,
mul_off, unknown_tag,
};
use super::{RttiResult, rtti_err};
/// One step of the non-recursive walk. The interpreter runs a `work` stack of these
/// against a `results` value stack: leaf steps push a [`Value`]; an `Assemble*` step
/// pops the `n` values its children pushed and combines them into one.
pub(in crate::rtti) enum Op {
/// Read the block of type `ord` at `block_off` (its whole `OnDisk`, header + fields).
Block {
ord: RttiOrdinal,
block_off: u64,
},
/// Interpret one shape at an absolute data offset.
Shape {
shape: Shape,
offset: u64,
},
/// Pop `n` field values (child-first order) and assemble a struct block.
MakeBlock {
tag: EightCC,
names: Box<[String]>,
},
/// Pop `n` field values and assemble an enum block.
MakeEnum {
tag: EightCC,
variant: String,
names: Box<[String]>,
},
/// Pop `n` values into an array / vec / tuple.
MakeArray(usize),
MakeVec(usize),
MakeTuple(usize),
/// Pop one value and wrap it in `Some`.
MakeSome,
}
impl RttiRegistry {
/// Read a structure of type `ordinal` at `block_off` in `data` into a [`Value`]
/// tree — the core RTTI operation: interpret an on-disk structure with no
/// compiled-in Rust type.
///
/// The walk is **non-recursive** (an explicit `work` stack), so arbitrarily deep
/// or self-referential data cannot blow the call stack. It **follows** owning
/// edges (`owned` / `strong` / `embed`) into child blocks, and **stops** at
/// non-owning ones (`weak` / `ref` / `foreign`), recording just their offset —
/// which also breaks any reference cycle. A node budget guards against a corrupt
/// file describing an unterminated walk.
pub fn read_value(
&self,
data: &BStack,
ordinal: RttiOrdinal,
block_off: u64,
) -> RttiResult<Value> {
self.run_read(
data,
Op::Block {
ord: ordinal,
block_off,
},
)
}
/// The read machine: run a `work` stack to a single [`Value`], from one `seed`
/// [`Op`] — a `Block` op from [`read_value`](Self::read_value) (a whole block) or a
/// `Shape` op from [`get`](Self::get) (one field). The seed is singular by contract:
/// the walk must bottom out at exactly one value (enforced at the tail).
pub(in crate::rtti) fn run_read(&self, data: &BStack, seed: Op) -> RttiResult<Value> {
let mut cache: HashMap<RttiOrdinal, RttiType> = HashMap::new();
let mut work: Vec<Op> = vec![seed];
let mut results: Vec<Value> = Vec::new();
// Bounds the total nodes visited: a corrupt schema/data pair (or a strong
// cycle) can otherwise loop forever.
let mut budget: u64 = 4_000_000;
while let Some(op) = work.pop() {
budget = budget.checked_sub(1).ok_or_else(|| {
rtti_err!(
Budget,
"RTTI interpret budget exceeded (corrupt data or a cycle?)"
)
})?;
match op {
Op::Block { ord, block_off } => {
if let std::collections::hash_map::Entry::Vacant(e) = cache.entry(ord) {
e.insert(self.load_type(ord)?);
}
let ty = &cache[&ord];
match &ty.body {
RttiBody::Struct(fields) => {
let names = fields.iter().map(|f| f.name.clone()).collect();
// Assemble marker first (popped last), then fields in
// order (so they pop child-first into the marker).
let field_ops: Vec<Op> = fields
.iter()
.map(|f| -> RttiResult<Op> {
Ok(Op::Shape {
shape: f.shape.clone(),
offset: add_off(block_off, f.offset as u64)?,
})
})
.collect::<RttiResult<Vec<Op>>>()?;
work.push(Op::MakeBlock { tag: ty.tag, names });
work.extend(field_ops);
}
RttiBody::Enum(e) => {
let (variant, payload_base) = e.resolve_variant(data, block_off)?;
let names = variant.fields.iter().map(|f| f.name.clone()).collect();
let field_ops: Vec<Op> = variant
.fields
.iter()
.map(|f| -> RttiResult<Op> {
Ok(Op::Shape {
shape: f.shape.clone(),
offset: add_off(payload_base, f.offset as u64)?,
})
})
.collect::<RttiResult<Vec<Op>>>()?;
work.push(Op::MakeEnum {
tag: ty.tag,
variant: variant.name.clone(),
names,
});
work.extend(field_ops);
}
}
}
Op::Shape { shape, offset } => match shape {
Shape::Pod { width } => {
// `width` is an untrusted record field; bound it against the
// stack before sizing an allocation with it (the read after
// would fail anyway — this fails first, without the alloc).
if width as u64 > data.len()?.saturating_sub(offset) {
return Err(rtti_err!(
Malformed,
"RTTI POD width runs past the end of the data stack",
));
}
let mut buf = vec![0u8; width as usize];
data.get_into(offset, &mut buf)?;
results.push(Value::Pod(buf.into()));
}
Shape::Class { value, .. } => {
// A class variable's value is schema-side, not per-instance.
results.push(Value::Class(value));
}
Shape::Owned(tag) | Shape::Strong(tag) => {
let child = read_u64(data, offset)?;
if child == 0 {
results.push(Value::Null);
} else {
let ord = self.ordinal_of(tag).ok_or_else(unknown_tag)?;
work.push(Op::Block {
ord,
block_off: child,
});
}
}
Shape::Embed(tag) => {
// The child's whole OnDisk is inline at this slot (no pointer).
let ord = self.ordinal_of(tag).ok_or_else(unknown_tag)?;
work.push(Op::Block {
ord,
block_off: offset,
});
}
Shape::Weak(tag) | Shape::Ref(tag) => {
results.push(Value::Ref {
tag,
offset: read_u64(data, offset)?,
});
}
Shape::Foreign { tag, kind } => {
// WidePtr { file_id:u32 @0, type_index:u32 @4, offset:u64 @8 }.
// The target is in another file — recorded, not followed.
let __wp = WidePtr::read_from_stack(data, offset)?;
let (file_id, off) = (__wp.file_id(), __wp.offset().get());
results.push(Value::Foreign {
tag,
kind,
file_id,
offset: off,
});
}
Shape::Option(inner) => {
// Niche location depends on the inner shape (a `Foreign`'s is
// its offset word @8, not the leading word).
if inner.option_present(data, offset)? {
work.push(Op::MakeSome);
work.push(Op::Shape {
shape: *inner,
offset,
});
} else {
results.push(Value::Null);
}
}
Shape::Array { n, inner } => {
// Charge the budget for all elements up front, as the `Vec`
// arm does — `n` comes off an untrusted record, and the ops
// are materialized eagerly, so an absurd count must fail
// cleanly rather than pre-allocate past the budget.
budget = budget.checked_sub(n as u64).ok_or_else(|| {
rtti_err!(
Budget,
"RTTI interpret budget exceeded (corrupt data or a cycle?)"
)
})?;
let stride = self.shape_stride(&inner, &mut cache)?;
let elem_ops: Vec<Op> = (0..n as u64)
.map(|i| -> RttiResult<Op> {
Ok(Op::Shape {
shape: (*inner).clone(),
offset: add_off(offset, mul_off(i, stride)?)?,
})
})
.collect::<RttiResult<Vec<Op>>>()?;
work.push(Op::MakeArray(n as usize));
work.extend(elem_ops);
}
Shape::Vec(inner) => {
let data_off = read_u64(data, offset)?; // VecDesc.data_off @0
if data_off == 0 {
results.push(Value::Vec(Box::default()));
} else {
// `@0` is the byte length, validated against the block size
// (`VecDesc.data_size` @8) so a forged length can't drive an
// out-of-block read / petabyte allocation.
let data_size = read_u64(data, add_off(offset, 8)?)?;
let base = add_off(data_off, BYTEVEC_HEADER)?;
let stride = self.shape_stride(&inner, &mut cache)?;
let byte_len = read_u64(data, data_off)?;
let len = checked_vec_len(byte_len, data_size, stride)?;
// Charge the budget for all elements up front — the ops are
// materialized eagerly, so a huge (but in-block) length must
// fail cleanly rather than pre-allocate past the budget.
budget = budget.checked_sub(len).ok_or_else(|| {
rtti_err!(
Budget,
"RTTI interpret budget exceeded (corrupt data or a cycle?)"
)
})?;
let elem_ops: Vec<Op> = (0..len)
.map(|i| -> RttiResult<Op> {
Ok(Op::Shape {
shape: (*inner).clone(),
offset: add_off(base, mul_off(i, stride)?)?,
})
})
.collect::<RttiResult<Vec<Op>>>()?;
work.push(Op::MakeVec(len as usize));
work.extend(elem_ops);
}
}
Shape::Tuple(items) => {
let mut elem_ops: Vec<Op> = Vec::with_capacity(items.len());
let mut off = offset;
for it in &items {
elem_ops.push(Op::Shape {
shape: it.clone(),
offset: off,
});
off = add_off(off, self.shape_stride(it, &mut cache)?)?;
}
work.push(Op::MakeTuple(items.len()));
work.extend(elem_ops);
}
},
Op::MakeBlock { tag, names } => {
let fields = pop_named(&mut results, &names)?;
results.push(Value::Block {
tag,
fields: fields.into(),
});
}
Op::MakeEnum {
tag,
variant,
names,
} => {
let fields = pop_named(&mut results, &names)?;
results.push(Value::Enum {
tag,
variant,
fields: fields.into(),
});
}
Op::MakeArray(n) => {
let v = pop_n(&mut results, n)?;
results.push(Value::Array(v.into()));
}
Op::MakeVec(n) => {
let v = pop_n(&mut results, n)?;
results.push(Value::Vec(v.into()));
}
Op::MakeTuple(n) => {
let v = pop_n(&mut results, n)?;
results.push(Value::Tuple(v.into()));
}
Op::MakeSome => {
let inner = results
.pop()
.ok_or_else(|| rtti_err!(Interpret, "RTTI interpret stack underflow"))?;
results.push(Value::Some(Box::new(inner)));
}
}
}
match results.len() {
1 => Ok(results.pop().unwrap()),
n => Err(rtti_err!(
Interpret,
"RTTI interpret produced {} values (expected 1)",
n
)),
}
}
/// Read the structure a typed [`WidePtr`] points at, within `data`. The
/// pointer must be **typed** (carry an RTTI ordinal), and `data` must be the file
/// it targets. This resolves within a single file by design — for a cross-file
/// pointer, resolve its `file_id` through the [`registry`](crate::registry) first
/// and call this against that file's stack.
pub fn read_ptr(&self, data: &BStack, ptr: WidePtr) -> RttiResult<Value> {
let ord = self.resolve_ptr(ptr).ok_or_else(|| {
rtti_err!(
UntypedPointer,
"cannot read an untyped / out-of-range RTTI pointer"
)
})?;
self.read_value(data, ord, ptr.offset().get())
}
/// The runtime-typed [`AnyRef`] a **typed** pointer denotes — its registry tag
/// (resolved from the pointer's `type_index`) plus offset. `None` for an untyped
/// (`type_index == 0`) or out-of-range pointer, so a stray pointer can never
/// masquerade as a registered type. Downcast the result with
/// [`AnyRef::downcast`], or read it generically with [`read_any`](Self::read_any).
pub fn any_ref(&self, ptr: WidePtr) -> Option<AnyRef> {
let ord = self.resolve_ptr(ptr)?;
let tag = self.tag_of(ord)?;
// SAFETY: the tag is registry-authoritative for the pointer's type_index,
// and the offset is the typed pointer's own target.
Some(unsafe { AnyRef::new(tag, ptr.offset().get()) })
}
/// Interpret the structure an [`AnyRef`] points at into a [`Value`] tree — the
/// generic fallback when [`AnyRef::downcast`] does not match a compiled-in type.
/// Errors if the reference's tag is not a registered type.
pub fn read_any(&self, data: &BStack, any: &AnyRef) -> RttiResult<Value> {
let ord = self.ordinal_of(any.tag()).ok_or_else(unknown_tag)?;
self.read_value(data, ord, any.offset())
}
}