logicaffeine_compile/analysis/
tower.rs

1//! Which values of a program the exact extension reaches: the bindings, function results and
2//! parameters that can hold an infinitesimal, a hyperreal, an infinite integer, an algebraic number, a
3//! computable real, an ordinal, a residue-dependent value or a provisional answer.
4//!
5//! The answer is a fixpoint over the whole program. A value is reached when it is made by a builtin of
6//! the extension (`infinitesimal`, `standardPart`, `tripCount`, `affinePower`, … — every
7//! [`logicaffeine_base::extension::Builtin`]) or by `definedReal`, declared with one of
8//! the exact types, or computed from a reached value — arithmetic and comparison lift through it, an
9//! item, a run of items and a copy of a reached list are reached, and `not` lifts over it. A binding is
10//! reached when anything assigned to it is; a function's result when anything it returns is; a
11//! parameter when any call passes it a reached value. `and`/`or` decide their operands, so they reach
12//! nothing. A list an item of the extension is stored into is reached; a map or a record stores one under
13//! a key and keeps its own kind, as every backend that lowers the bytecode reads it
14//! (`vm::tower::exact_write`).
15//!
16//! Every tier that keeps static types reads it: the optimizer leaves alone the integer-only rewrites
17//! of a reached value, and a compiled backend holds a reached binding in its exact value model. The
18//! answer over-approximates — names are keyed by the function they live in, not by block — which costs
19//! a compiled program speed, never meaning: a value model that keeps canonical forms holds a standard
20//! integer as one.
21
22use std::collections::{HashMap, HashSet};
23
24use logicaffeine_base::extension::Builtin;
25
26use crate::ast::stmt::{BinaryOpKind, Block, Expr, Pattern, SelectBranch, Stmt, TypeExpr};
27use crate::intern::{Interner, Symbol};
28
29/// The builtins whose result is reached when an argument is: they round, measure or combine a number
30/// in its own kind.
31pub(crate) const LIFTING_BUILTINS: &[&str] = &["floor", "ceil", "round", "abs", "min", "max", "pow", "sqrt"];
32
33/// The builtins outside the extension that make one of its values: a real number a function the
34/// program defines.
35pub(crate) const DEFINERS: &[&str] = &["definedReal"];
36
37/// The declared types that name the extension.
38pub(crate) const TOWER_TYPES: &[&str] = &["Algebraic", "ExactReal", "Hyperreal", "Hypernatural", "Ordinal"];
39
40/// Where a name lives: a function's body, or the program's root (`None`).
41pub type Scope = Option<Symbol>;
42
43/// The reached bindings, results and parameters of a program.
44#[derive(Debug, Default, Clone, PartialEq, Eq)]
45pub struct TowerTypes {
46    bindings: HashSet<(Scope, Symbol)>,
47    returns: HashSet<Symbol>,
48    params: HashMap<Symbol, Vec<Symbol>>,
49    /// The program's spellings of the extension's builtins and of [`LIFTING_BUILTINS`].
50    makers: HashSet<Symbol>,
51    lifters: HashSet<Symbol>,
52    /// The program calls a builtin of the extension somewhere.
53    touched: bool,
54    /// The bindings some assignment makes a map or a record, and those some assignment makes anything else:
55    /// a binding only ever a map or a record stores an item under a key.
56    keyed: HashSet<(Scope, Symbol)>,
57    unkeyed: HashSet<(Scope, Symbol)>,
58    /// The names each function binds itself (its parameters, its `Let`s, its loop variables, what it pops into):
59    /// any other name a function assigns is the program's root binding.
60    locals: HashMap<Symbol, HashSet<Symbol>>,
61}
62
63impl TowerTypes {
64    /// The program's answer, or `None` when the extension reaches nothing.
65    pub fn of_program(stmts: &[Stmt], interner: &Interner) -> Option<TowerTypes> {
66        let spelled = |names: &mut dyn Iterator<Item = &str>| {
67            names.filter_map(|n| interner.lookup(n)).collect()
68        };
69        let mut t = TowerTypes {
70            makers: spelled(&mut Builtin::ALL.iter().map(|b| b.name()).chain(DEFINERS.iter().copied())),
71            lifters: spelled(&mut LIFTING_BUILTINS.iter().copied()),
72            ..TowerTypes::default()
73        };
74        for s in stmts {
75            if let Stmt::FunctionDef { name, params, body, .. } = s {
76                t.params.insert(*name, params.iter().map(|(p, _)| *p).collect());
77                let mut locals: HashSet<Symbol> = params.iter().map(|(p, _)| *p).collect();
78                bound_names(body, &mut locals);
79                t.locals.insert(*name, locals);
80            }
81        }
82        t.seed_declared(None, stmts, interner);
83        t.seed_keyed(None, stmts, interner);
84        loop {
85            let before = (t.bindings.len(), t.returns.len());
86            t.pass(None, stmts);
87            for s in stmts {
88                if let Stmt::FunctionDef { name, body, .. } = s {
89                    t.pass(Some(*name), body);
90                }
91            }
92            if (t.bindings.len(), t.returns.len()) == before {
93                break;
94            }
95        }
96        (t.touched || !t.bindings.is_empty() || !t.returns.is_empty()).then_some(t)
97    }
98
99    /// Whether `sym`, as named in `scope`, can hold a value of the extension. A function reads the
100    /// program's root bindings too.
101    pub fn binding(&self, scope: Scope, sym: Symbol) -> bool {
102        self.bindings.contains(&(scope, sym)) || self.bindings.contains(&(None, sym))
103    }
104
105    /// Whether the function `f` can return a value of the extension.
106    pub fn returns(&self, f: Symbol) -> bool {
107        self.returns.contains(&f)
108    }
109
110    /// Whether the `i`th parameter of the program's function `f` can hold a value of the extension.
111    pub fn param_at(&self, f: Symbol, i: usize) -> bool {
112        self.params
113            .get(&f)
114            .and_then(|ps| ps.get(i))
115            .is_some_and(|p| self.binding(Some(f), *p))
116    }
117
118    /// Whether the program declares a function named `f`, which a call of `f` then means over any
119    /// builtin of that name.
120    pub fn declares(&self, f: Symbol) -> bool {
121        self.params.contains_key(&f)
122    }
123
124    /// Every name, in any scope, that can hold a value of the extension.
125    pub fn names(&self) -> HashSet<Symbol> {
126        self.bindings.iter().map(|(_, s)| *s).collect()
127    }
128
129    /// Whether `expr`, evaluated in `scope`, can be a value of the extension.
130    pub fn expr(&self, scope: Scope, expr: &Expr) -> bool {
131        match expr {
132            Expr::Identifier(s) => self.binding(scope, *s),
133            Expr::BinaryOp { op, left, right } => {
134                !matches!(op, BinaryOpKind::And | BinaryOpKind::Or | BinaryOpKind::Concat)
135                    && (self.expr(scope, left) || self.expr(scope, right))
136            }
137            Expr::Not { operand } => self.expr(scope, operand),
138            Expr::Call { function, args } => {
139                self.makers.contains(function)
140                    || self.returns(*function)
141                    || (self.lifters.contains(function) && args.iter().any(|a| self.expr(scope, a)))
142            }
143            Expr::Index { collection, .. } | Expr::Slice { collection, .. } => self.expr(scope, collection),
144            Expr::Copy { expr: inner } => self.expr(scope, inner),
145            Expr::List(items) => items.iter().any(|i| self.expr(scope, i)),
146            _ => false,
147        }
148    }
149
150    fn seed_declared(&mut self, scope: Scope, stmts: &[Stmt], interner: &Interner) {
151        let exact = |t: &TypeExpr| {
152            matches!(t, TypeExpr::Primitive(s) | TypeExpr::Named(s) if TOWER_TYPES.contains(&interner.resolve(*s)))
153        };
154        for s in stmts {
155            match s {
156                Stmt::Let { var, ty: Some(t), .. } if exact(t) => {
157                    self.bindings.insert((scope, *var));
158                }
159                Stmt::FunctionDef {
160                    name,
161                    params,
162                    body,
163                    return_type,
164                    ..
165                } => {
166                    for (p, t) in params {
167                        if exact(t) {
168                            self.bindings.insert((Some(*name), *p));
169                        }
170                    }
171                    if return_type.is_some_and(|t| exact(t)) {
172                        self.returns.insert(*name);
173                    }
174                    self.seed_declared(Some(*name), body, interner);
175                }
176                other => {
177                    for b in nested_blocks(other) {
178                        self.seed_declared(scope, b, interner);
179                    }
180                }
181            }
182        }
183    }
184
185    /// Which bindings each assignment of `stmts`, in `scope`, makes a map or a record (`a new Map of …`,
186    /// `a new Box with …`) and which it makes anything else.
187    fn seed_keyed(&mut self, scope: Scope, stmts: &[Stmt], interner: &Interner) {
188        let keyed = |value: &Expr| match value {
189            Expr::New { type_name, .. } => {
190                !matches!(interner.resolve(*type_name), "Seq" | "List" | "Set" | "HashSet")
191            }
192            _ => false,
193        };
194        for s in stmts {
195            match s {
196                Stmt::Let { var, value, .. } | Stmt::Set { target: var, value } => {
197                    if keyed(value) {
198                        self.keyed.insert((scope, *var));
199                    } else {
200                        self.unkeyed.insert((scope, *var));
201                    }
202                }
203                Stmt::FunctionDef { name, body, .. } => self.seed_keyed(Some(*name), body, interner),
204                _ => {}
205            }
206            if !matches!(s, Stmt::FunctionDef { .. }) {
207                for b in nested_blocks(s) {
208                    self.seed_keyed(scope, b, interner);
209                }
210            }
211        }
212    }
213
214    /// Whether `sym`, as named in `scope`, is only ever a map or a record.
215    fn keyed(&self, scope: Scope, sym: Symbol) -> bool {
216        let at = if self.keyed.contains(&(scope, sym)) || self.unkeyed.contains(&(scope, sym)) {
217            (scope, sym)
218        } else {
219            (None, sym)
220        };
221        self.keyed.contains(&at) && !self.unkeyed.contains(&at)
222    }
223
224    /// Reach `sym` as `scope` names it: a function's own binding, or the program's root binding a function assigns
225    /// without binding it itself.
226    fn reach(&mut self, scope: Scope, sym: Symbol) {
227        let own = scope.is_some_and(|f| self.locals.get(&f).is_some_and(|names| names.contains(&sym)));
228        let at = if scope.is_none() || own { scope } else { None };
229        self.bindings.insert((at, sym));
230    }
231
232    fn reach_args(&mut self, scope: Scope, function: Symbol, args: &[&Expr]) {
233        self.touched |= self.makers.contains(&function);
234        let reached: Vec<usize> = args
235            .iter()
236            .enumerate()
237            .filter(|(_, a)| self.expr(scope, a))
238            .map(|(i, _)| i)
239            .collect();
240        if let Some(params) = self.params.get(&function).cloned() {
241            for i in reached {
242                if let Some(p) = params.get(i) {
243                    self.reach(Some(function), *p);
244                }
245            }
246        }
247        for a in args {
248            self.calls_in(scope, a);
249        }
250    }
251
252    /// The calls inside an expression, each passing what it passes.
253    fn calls_in(&mut self, scope: Scope, expr: &Expr) {
254        match expr {
255            Expr::Call { function, args } => self.reach_args(scope, *function, args),
256            Expr::BinaryOp { left, right, .. } => {
257                self.calls_in(scope, left);
258                self.calls_in(scope, right);
259            }
260            Expr::Not { operand } => self.calls_in(scope, operand),
261            Expr::Index { collection, index } => {
262                self.calls_in(scope, collection);
263                self.calls_in(scope, index);
264            }
265            Expr::List(items) => {
266                for i in items {
267                    self.calls_in(scope, i);
268                }
269            }
270            _ => {}
271        }
272    }
273
274    fn pass(&mut self, scope: Scope, stmts: &[Stmt]) {
275        for s in stmts {
276            match s {
277                Stmt::FunctionDef { .. } => {}
278                Stmt::Let { var, value, .. } | Stmt::Set { target: var, value } => {
279                    if self.expr(scope, value) {
280                        self.reach(scope, *var);
281                    }
282                    self.calls_in(scope, value);
283                }
284                Stmt::Repeat {
285                    pattern, iterable, ..
286                } => {
287                    if self.expr(scope, iterable) {
288                        match pattern {
289                            Pattern::Identifier(x) => self.reach(scope, *x),
290                            Pattern::Tuple(xs) => {
291                                for x in xs {
292                                    self.reach(scope, *x);
293                                }
294                            }
295                        }
296                    }
297                    self.calls_in(scope, iterable);
298                }
299                Stmt::Push { value, collection } | Stmt::SetIndex {
300                    collection, value, ..
301                } => {
302                    if self.expr(scope, value) {
303                        if let Expr::Identifier(c) = collection {
304                            let under_a_key = matches!(s, Stmt::SetIndex { .. }) && self.keyed(scope, *c);
305                            if !under_a_key {
306                                self.reach(scope, *c);
307                            }
308                        }
309                    }
310                    self.calls_in(scope, value);
311                }
312                Stmt::Return { value: Some(v) } => {
313                    if let Some(f) = scope {
314                        if self.expr(scope, v) {
315                            self.returns.insert(f);
316                        }
317                    }
318                    self.calls_in(scope, v);
319                }
320                Stmt::Call { function, args } => self.reach_args(scope, *function, args),
321                Stmt::Pop {
322                    collection: Expr::Identifier(c),
323                    into: Some(v),
324                } => {
325                    if self.binding(scope, *c) {
326                        self.reach(scope, *v);
327                    }
328                }
329                Stmt::If { cond, .. } | Stmt::While { cond, .. } => self.calls_in(scope, cond),
330                Stmt::Show { object, .. } => self.calls_in(scope, object),
331                _ => {}
332            }
333            for b in nested_blocks(s) {
334                self.pass(scope, b);
335            }
336        }
337    }
338}
339
340/// The names `stmts` bind, nested blocks included: each `Let`, loop variable and `Pop … into`.
341fn bound_names(stmts: &[Stmt], into: &mut HashSet<Symbol>) {
342    for s in stmts {
343        match s {
344            Stmt::Let { var, .. } => {
345                into.insert(*var);
346            }
347            Stmt::Repeat { pattern, .. } => match pattern {
348                Pattern::Identifier(x) => {
349                    into.insert(*x);
350                }
351                Pattern::Tuple(xs) => into.extend(xs.iter().copied()),
352            },
353            Stmt::Pop { into: Some(v), .. } => {
354                into.insert(*v);
355            }
356            _ => {}
357        }
358        if !matches!(s, Stmt::FunctionDef { .. }) {
359            for b in nested_blocks(s) {
360                bound_names(b, into);
361            }
362        }
363    }
364}
365
366/// The statement blocks nested in `stmt` that share its scope; a function's body is its own scope and
367/// is not among them. Exhaustive over `Stmt`: a statement kind added to the language does not compile
368/// here until its blocks are named.
369pub(crate) fn nested_blocks<'s, 'a>(stmt: &'s Stmt<'a>) -> Vec<Block<'a>> {
370    match stmt {
371        Stmt::If {
372            then_block,
373            else_block,
374            ..
375        } => {
376            let mut v = vec![*then_block];
377            v.extend(else_block.iter().copied());
378            v
379        }
380        Stmt::While { body, .. }
381        | Stmt::Repeat { body, .. }
382        | Stmt::TestDef { body, .. }
383        | Stmt::ExpectFail { body, .. }
384        | Stmt::During { body, .. }
385        | Stmt::ForAll { body, .. }
386        | Stmt::Splice { body }
387        | Stmt::Reversibly { body }
388        | Stmt::Zone { body, .. }
389        | Stmt::MiddlewareDef { body, .. } => vec![*body],
390        Stmt::Concurrent { tasks } | Stmt::Parallel { tasks } => vec![*tasks],
391        Stmt::Inspect { arms, .. } => arms.iter().map(|a| a.body).collect(),
392        Stmt::Select { branches } => branches
393            .iter()
394            .map(|b| match b {
395                SelectBranch::Receive { body, .. } | SelectBranch::Timeout { body, .. } => *body,
396            })
397            .collect(),
398        Stmt::DirectiveDef { body, removed, .. } => {
399            let mut v = vec![*body];
400            v.extend(removed.iter().copied());
401            v
402        }
403        Stmt::RouteDef { body, .. } => match &**body {
404            crate::ast::component::RouteBody::Statements(b) => vec![*b],
405            crate::ast::component::RouteBody::View(_) => Vec::new(),
406        },
407        Stmt::ComponentDef(def) => def
408            .events
409            .iter()
410            .map(|e| e.body)
411            .chain(def.actions.iter().map(|a| a.body))
412            .collect(),
413        Stmt::FunctionDef { .. }
414        | Stmt::Let { .. }
415        | Stmt::Set { .. }
416        | Stmt::Swap { .. }
417        | Stmt::Call { .. }
418        | Stmt::Return { .. }
419        | Stmt::Break
420        | Stmt::Assert { .. }
421        | Stmt::Trust { .. }
422        | Stmt::RuntimeAssert { .. }
423        | Stmt::Fail { .. }
424        | Stmt::Give { .. }
425        | Stmt::Show { .. }
426        | Stmt::SetField { .. }
427        | Stmt::StructDef { .. }
428        | Stmt::Expect { .. }
429        | Stmt::ExpectOutput { .. }
430        | Stmt::AdvanceTime { .. }
431        | Stmt::GivenFile { .. }
432        | Stmt::Observe { .. }
433        | Stmt::Push { .. }
434        | Stmt::Pop { .. }
435        | Stmt::Add { .. }
436        | Stmt::Remove { .. }
437        | Stmt::SetIndex { .. }
438        | Stmt::ReadFrom { .. }
439        | Stmt::WriteFile { .. }
440        | Stmt::Spawn { .. }
441        | Stmt::SendMessage { .. }
442        | Stmt::AwaitMessage { .. }
443        | Stmt::StreamMessage { .. }
444        | Stmt::MergeCrdt { .. }
445        | Stmt::JoinCrdt { .. }
446        | Stmt::IncreaseCrdt { .. }
447        | Stmt::DecreaseCrdt { .. }
448        | Stmt::AppendToSequence { .. }
449        | Stmt::ResolveConflict { .. }
450        | Stmt::Check { .. }
451        | Stmt::Listen { .. }
452        | Stmt::Serve { .. }
453        | Stmt::ConnectTo { .. }
454        | Stmt::LetPeerAgent { .. }
455        | Stmt::Sleep { .. }
456        | Stmt::Sync { .. }
457        | Stmt::Ui(_)
458        | Stmt::Fetch { .. }
459        | Stmt::Replay { .. }
460        | Stmt::ServeFetches
461        | Stmt::GivenFetch { .. }
462        | Stmt::RedirectDef { .. }
463        | Stmt::Mount { .. }
464        | Stmt::LaunchTask { .. }
465        | Stmt::LaunchTaskWithHandle { .. }
466        | Stmt::CreatePipe { .. }
467        | Stmt::SendPipe { .. }
468        | Stmt::ReceivePipe { .. }
469        | Stmt::TrySendPipe { .. }
470        | Stmt::TryReceivePipe { .. }
471        | Stmt::StopTask { .. }
472        | Stmt::CloseChannel { .. }
473        | Stmt::AwaitTask { .. }
474        | Stmt::Theorem(_)
475        | Stmt::Definition(_)
476        | Stmt::Axiom(_)
477        | Stmt::Theory(_)
478        | Stmt::Escape { .. }
479        | Stmt::Require { .. }
480        | Stmt::Site(_) => Vec::new(),
481    }
482}
483
484#[cfg(test)]
485#[path = "../../../logicaffeine_tests/unit/logicaffeine_compile/analysis/tower/tests.rs"]
486mod tests;
logicaffeine_compile/analysis/tower.rs

logicaffeine_compile/analysis/
tower.rs
