logicaffeine_compile/vm/reach.rs
1//! Which compiled functions — and which ops — can run.
2//!
3//! A program's bytecode carries every function the loader spliced in: the author's, and whole
4//! standard-library modules a type name or a builtin demanded. Most of a demanded module is never
5//! called. A backend that lowers only what runs (the WebAssembly backend's dead-function
6//! elimination) must agree with the gate that refuses what it cannot lower (the unlinkable-code
7//! gate), or a function nothing calls either breaks the build (the gate refuses dead code) or ships
8//! a stub a live call lands on (the backend drops live code). This module is the one answer both
9//! ask.
10//!
11//! # The code stream
12//!
13//! Main is `code[0 .. main_end)`. Regular (`## To`) functions follow as a contiguous, entry-sorted
14//! tail, each ending where the next begins. A closure body is INLINE: emitted inside its enclosing
15//! region and jumped over by a `Jump` at `entry_pc - 1` whose target is the body's end, so a region
16//! contains its closures' bodies as holes.
17//!
18//! # The edges
19//!
20//! A function runs when Main or a running function names it: a `Call`, a `MakeClosure` body, or a
21//! `Spawn`/`SpawnHandle` task. Two facts no op carries are part of the graph too, because the
22//! backends act on them:
23//!
24//! - `text_from_bytes` validates through `validUtf8 (data: Seq of Int) -> Bool`, a call the wasm
25//! backend writes from the builtin;
26//! - a page's entries (`lgx_lower::LGX_ENTRIES`) are entered by the HOST, never by the module; so
27//! is the mount of a component the host was asked to mount on demand ([`HostEntries`]).
28//!
29//! Three facts gate edges:
30//!
31//! - a drawn component's members (its actions, bindings, patchers and callback trampolines) run only
32//! for an instance, so an edge into one from outside the component is followed once the
33//! component's render is reached (`ComponentOwners`);
34//! - a `vdom.lg` feature's functions run only on a tape holding records its writers laid down
35//! (`lgx_lower::VDOM_FEATURES`), so an edge into one is followed once a writer is reached
36//! (`VdomFeatures`);
37//! - hydration (`vdHydrate`) runs only for a page its build pre-rendered, which the host says
38//! ([`HostEntries::drawing_fresh`] says it never is).
39
40use super::instruction::{CompiledProgram, Op};
41use crate::semantics::builtins::BuiltinId;
42use crate::Interner;
43
44/// How the flat code stream partitions into functions.
45pub struct CodeLayout {
46 /// Main's region end (exclusive): the first regular-function entry, or `code.len()`.
47 pub main_end: usize,
48 /// Per-function `[start, end)` in the code stream, holes included.
49 pub func_region: Vec<(usize, usize)>,
50 /// Every closure body's `[start, end)` — the holes to excise from an enclosing region.
51 pub closure_ranges: Vec<(usize, usize)>,
52 /// `is_closure[fi]` — whether function `fi` is a closure body (a `MakeClosure` target).
53 pub is_closure: Vec<bool>,
54}
55
56/// Resolve the [`CodeLayout`]: a `MakeClosure` target is a closure body spanning
57/// `[entry, jump-over target)`; the regular functions are the entry-sorted tail after Main.
58/// `Err` names a closure body with no jump-over, which no compiler output has.
59pub fn code_layout(program: &CompiledProgram) -> Result<CodeLayout, &'static str> {
60 let code_len = program.code.len();
61 let nf = program.functions.len();
62 let mut is_closure = vec![false; nf];
63 for op in &program.code {
64 if let Op::MakeClosure { func, .. } = *op {
65 if (func as usize) < nf {
66 is_closure[func as usize] = true;
67 }
68 }
69 }
70 let mut func_region = vec![(0usize, 0usize); nf];
71 let mut closure_ranges = Vec::new();
72 for (fi, f) in program.functions.iter().enumerate() {
73 if is_closure[fi] {
74 let entry = f.entry_pc;
75 let end = match (entry >= 1).then(|| program.code.get(entry - 1)).flatten() {
76 Some(Op::Jump { target }) if *target > entry && *target <= code_len => *target,
77 _ => return Err("closure body without a jump-over"),
78 };
79 func_region[fi] = (entry, end);
80 closure_ranges.push((entry, end));
81 }
82 }
83 let mut regular: Vec<usize> = (0..nf).filter(|&fi| !is_closure[fi]).collect();
84 regular.sort_by_key(|&fi| program.functions[fi].entry_pc);
85 let main_end = regular
86 .first()
87 .map(|&fi| program.functions[fi].entry_pc)
88 .unwrap_or(code_len);
89 for w in 0..regular.len() {
90 let fi = regular[w];
91 let start = program.functions[fi].entry_pc;
92 let end = regular
93 .get(w + 1)
94 .map(|&g| program.functions[g].entry_pc)
95 .unwrap_or(code_len);
96 func_region[fi] = (start, end);
97 }
98 Ok(CodeLayout {
99 main_end,
100 func_region,
101 closure_ranges,
102 is_closure,
103 })
104}
105
106/// What can run.
107pub struct Reach {
108 /// `functions[fi]` — whether function `fi` can be entered.
109 pub functions: Vec<bool>,
110 /// `code[pc]` — whether the op at `pc` lies in Main or in the region of a function that can be
111 /// entered. A region is scanned whole, holes included, so an inline closure body inside a
112 /// running region counts as running with it: the edges it names are followed either way.
113 pub code: Vec<bool>,
114}
115
116/// The functions a page's HOST enters by name, beyond Main: every fixed page entry of
117/// `lgx_lower::LGX_ENTRIES` the program defines, always; and the mount of each component the host
118/// is asked to be able to mount on demand — a test that mounts a component at a statement of its
119/// own. A shipped page has no such components (its only mount is the one its own `main` performs),
120/// so the default is the fixed page entries alone.
121#[derive(Clone, Debug, Default, PartialEq, Eq)]
122pub struct HostEntries {
123 mounts: Vec<String>,
124 /// The host serves no pre-rendered markup, so the page's mount never adopts any.
125 fresh: bool,
126}
127
128impl HostEntries {
129 /// A page whose host may also mount each of `components`, by name, at any time.
130 pub fn mounting<I, S>(components: I) -> HostEntries
131 where
132 I: IntoIterator<Item = S>,
133 S: Into<String>,
134 {
135 let mut mounts: Vec<String> = components.into_iter().map(Into::into).collect();
136 mounts.sort();
137 mounts.dedup();
138 HostEntries {
139 mounts,
140 fresh: false,
141 }
142 }
143
144 /// These entries for a host that serves the page with no pre-rendered markup — a page whose
145 /// build could not pre-render it, a module emitted on its own: its mount draws fresh and never
146 /// hydrates, so the hydration paths are left out.
147 pub fn drawing_fresh(mut self) -> HostEntries {
148 self.fresh = true;
149 self
150 }
151
152 /// Whether the page's mount may adopt markup a build pre-rendered.
153 pub fn hydrates(&self) -> bool {
154 !self.fresh
155 }
156
157 /// The components the host may mount on demand, sorted.
158 pub fn mounts(&self) -> &[String] {
159 &self.mounts
160 }
161
162 /// Every function the host enters by name: the fixed page entries, then the requested mounts.
163 pub fn names(&self) -> Vec<String> {
164 use logicaffeine_language::parser::lgx_lower::{mount_fn_name, EntryHost, LGX_ENTRIES};
165 LGX_ENTRIES
166 .iter()
167 .filter(|e| !e.family && e.host == EntryHost::Page)
168 .map(|e| e.name.to_string())
169 .chain(self.mounts.iter().map(|c| mount_fn_name(c)))
170 .collect()
171 }
172}
173
174/// The function `text_from_bytes` validates through.
175pub const UTF8_VALIDATOR: &str = "validUtf8";
176
177/// Walk the call graph from Main and a shipped page's host entries.
178pub fn reach(program: &CompiledProgram, layout: &CodeLayout, interner: &Interner) -> Reach {
179 reach_with(program, layout, interner, &HostEntries::default())
180}
181
182/// Walk the call graph from Main and every one of `entries`.
183pub fn reach_with(
184 program: &CompiledProgram,
185 layout: &CodeLayout,
186 interner: &Interner,
187 entries: &HostEntries,
188) -> Reach {
189 let by_name = |name: &str| {
190 program
191 .functions
192 .iter()
193 .position(|f| interner.resolve(f.name) == name)
194 };
195 let utf8_validator = by_name(UTF8_VALIDATOR);
196 let hydrate = if entries.hydrates() {
197 None
198 } else {
199 by_name(HYDRATE)
200 };
201 let owners = ComponentOwners::of(program, interner);
202 let mut features = VdomFeatures::of(program, interner);
203 let mut functions = vec![false; program.functions.len()];
204 let mut code = vec![false; program.code.len()];
205 let mut pending: Vec<Vec<usize>> = vec![Vec::new(); owners.renders.len()];
206 let mut stack: Vec<usize> = entries.names().iter().filter_map(|n| by_name(n)).collect();
207 // `from` is the component that owns the region being scanned (`None` for Main and the page's
208 // own entries): an edge from outside a drawn component into one of its members waits for that
209 // component's render to be reached.
210 let scan = |start: usize,
211 end: usize,
212 from: Option<usize>,
213 code: &mut [bool],
214 functions: &[bool],
215 stack: &mut Vec<usize>,
216 pending: &mut Vec<Vec<usize>>,
217 features: &mut VdomFeatures| {
218 for pc in start..end {
219 code[pc] = true;
220 match program.code[pc] {
221 Op::Call { func, .. }
222 | Op::MakeClosure { func, .. }
223 | Op::Spawn { func, .. }
224 | Op::SpawnHandle { func, .. } => {
225 let func = func as usize;
226 if Some(func) == hydrate {
227 continue;
228 }
229 match owners.gate(func, from) {
230 Some(c) if !functions[owners.renders[c]] => pending[c].push(func),
231 _ => features.follow(func, stack),
232 }
233 }
234 Op::CallBuiltin {
235 builtin: BuiltinId::TextFromBytes,
236 ..
237 } => stack.extend(utf8_validator),
238 _ => {}
239 }
240 }
241 };
242 scan(
243 0,
244 layout.main_end.min(program.code.len()),
245 None,
246 &mut code,
247 &functions,
248 &mut stack,
249 &mut pending,
250 &mut features,
251 );
252 while let Some(fi) = stack.pop() {
253 if fi >= functions.len() || functions[fi] {
254 continue;
255 }
256 functions[fi] = true;
257 if let Some(c) = owners.renders.iter().position(|&r| r == fi) {
258 stack.append(&mut pending[c]);
259 }
260 features.reached(fi, &mut stack);
261 let (s, e) = layout.func_region[fi];
262 if s <= e && e <= program.code.len() {
263 scan(
264 s,
265 e,
266 owners.owner[fi],
267 &mut code,
268 &functions,
269 &mut stack,
270 &mut pending,
271 &mut features,
272 );
273 }
274 }
275 Reach { functions, code }
276}
277
278/// The function a page's mount adopts pre-rendered markup through.
279const HYDRATE: &str = "vdHydrate";
280
281/// Which `vdom.lg` feature each function belongs to (`lgx_lower::VDOM_FEATURES`), and which features
282/// a reached writer has opened: an edge into a feature waits, in `pending`, for its first writer.
283struct VdomFeatures {
284 feature_of: Vec<Option<usize>>,
285 writers: Vec<Vec<usize>>,
286 open: Vec<bool>,
287 pending: Vec<Vec<usize>>,
288}
289
290impl VdomFeatures {
291 fn of(program: &CompiledProgram, interner: &Interner) -> VdomFeatures {
292 use logicaffeine_language::parser::lgx_lower::VDOM_FEATURES;
293 let names: Vec<&str> = program
294 .functions
295 .iter()
296 .map(|f| interner.resolve(f.name))
297 .collect();
298 let feature_of = names
299 .iter()
300 .map(|n| VDOM_FEATURES.iter().position(|f| n.starts_with(f.prefix)))
301 .collect();
302 let writers = VDOM_FEATURES
303 .iter()
304 .map(|f| {
305 names
306 .iter()
307 .enumerate()
308 .filter(|(_, n)| f.writers.contains(n))
309 .map(|(fi, _)| fi)
310 .collect()
311 })
312 .collect();
313 VdomFeatures {
314 feature_of,
315 writers,
316 open: vec![false; VDOM_FEATURES.len()],
317 pending: vec![Vec::new(); VDOM_FEATURES.len()],
318 }
319 }
320
321 /// Follows an edge into `func` now, or once its feature opens.
322 fn follow(&mut self, func: usize, stack: &mut Vec<usize>) {
323 match self.feature_of.get(func).copied().flatten() {
324 Some(f) if !self.open[f] => self.pending[f].push(func),
325 _ => stack.push(func),
326 }
327 }
328
329 /// `fi` was reached: every feature it writes opens, and the edges that waited on it are followed.
330 fn reached(&mut self, fi: usize, stack: &mut Vec<usize>) {
331 for f in 0..self.writers.len() {
332 if !self.open[f] && self.writers[f].contains(&fi) {
333 self.open[f] = true;
334 stack.append(&mut self.pending[f]);
335 }
336 }
337 }
338}
339
340/// Which drawn component each lowered function belongs to.
341///
342/// ★ A PAGE ENTRY FANS OUT OVER EVERY COMPONENT. The dispatcher calls every component's actions,
343/// the clock every component's timers, the route and failure entries every component's handlers —
344/// so rooting the entries would make every component's code reachable whether or not anything
345/// draws it. A component's members run only for an instance, and an instance exists only once
346/// its render has run: an edge from outside a component into one of its actions, bindings,
347/// patchers or callback trampolines is followed when that component's `__render_` is reached,
348/// and not before. Its render and its mount are how it comes to be drawn, so edges to those are
349/// followed at once.
350struct ComponentOwners {
351 /// `renders[c]` — the function index of component `c`'s render.
352 renders: Vec<usize>,
353 /// `owner[fi]` — the component function `fi` is a member of, if any.
354 owner: Vec<Option<usize>>,
355 /// `drawn_by_edge[fi]` — whether `fi` is a render or a mount: followed from anywhere.
356 drawn_by_edge: Vec<bool>,
357}
358
359impl ComponentOwners {
360 fn of(program: &CompiledProgram, interner: &Interner) -> ComponentOwners {
361 use logicaffeine_language::parser::lgx_lower::{
362 action_fn_name, bind_fn_name, callback_trampoline_fn_name, mount_fn_name,
363 patch_fn_name, render_fn_name,
364 };
365 let names: Vec<&str> = program
366 .functions
367 .iter()
368 .map(|f| interner.resolve(f.name))
369 .collect();
370 let render_prefix = render_fn_name("");
371 let components: Vec<(String, usize)> = names
372 .iter()
373 .enumerate()
374 .filter_map(|(fi, n)| {
375 n.strip_prefix(render_prefix.as_str())
376 .map(|c| (c.to_string(), fi))
377 })
378 .collect();
379 let mut owner = vec![None; names.len()];
380 let mut drawn_by_edge = vec![false; names.len()];
381 for (fi, name) in names.iter().enumerate() {
382 let mut best: Option<usize> = None;
383 for (c, (component, _)) in components.iter().enumerate() {
384 let drawn = *name == render_fn_name(component) || *name == mount_fn_name(component);
385 let member = [
386 action_fn_name(component, ""),
387 bind_fn_name(component, ""),
388 patch_fn_name(component, ""),
389 callback_trampoline_fn_name(component, ""),
390 ]
391 .iter()
392 .any(|prefix| name.starts_with(prefix.as_str()));
393 if drawn || member {
394 let longer = best.map_or(true, |b| component.len() > components[b].0.len());
395 if longer {
396 best = Some(c);
397 drawn_by_edge[fi] = drawn;
398 }
399 }
400 }
401 owner[fi] = best;
402 }
403 ComponentOwners {
404 renders: components.iter().map(|(_, fi)| *fi).collect(),
405 owner,
406 drawn_by_edge,
407 }
408 }
409
410 /// The component an edge from a region of component `from` into `to` waits for, if any.
411 fn gate(&self, to: usize, from: Option<usize>) -> Option<usize> {
412 let c = self.owner.get(to).copied().flatten()?;
413 (from != Some(c) && !self.drawn_by_edge[to]).then_some(c)
414 }
415}
416
417/// Every op that can run in a shipped page, with its pc. A program whose layout cannot be resolved
418/// is taken whole: the caller is a gate, and a gate that cannot tell must not wave code through.
419pub fn running_ops<'p>(program: &'p CompiledProgram, interner: &Interner) -> Vec<(usize, &'p Op)> {
420 running_ops_with(program, interner, &HostEntries::default())
421}
422
423/// Every op that can run once the host may also enter `entries`, with its pc — what a gate judges
424/// when a module is built for a host that mounts components on demand.
425pub fn running_ops_with<'p>(
426 program: &'p CompiledProgram,
427 interner: &Interner,
428 entries: &HostEntries,
429) -> Vec<(usize, &'p Op)> {
430 match code_layout(program) {
431 Ok(layout) => {
432 let r = reach_with(program, &layout, interner, entries);
433 program
434 .code
435 .iter()
436 .enumerate()
437 .filter(|(pc, _)| r.code[*pc])
438 .collect()
439 }
440 Err(_) => program.code.iter().enumerate().collect(),
441 }
442}