Skip to main content

olean_export/env/
walk.rs

1use super::{
2    term::{Body, Const, Ctor, Defn, Expr, ExprId, Inductive, Kind, NameId, Rec},
3    Env,
4};
5use crate::error::{corrupt, Error, Result};
6use rustc_hash::{FxHashMap, FxHashSet};
7use std::{mem, path::PathBuf};
8
9/// Constants the kernel relies on without a term naming them: `Nat` for numeric literals,
10/// what string literals unfold to, and `Eq` with the quotient constants.
11#[derive(Debug, Clone, Copy)]
12pub(crate) struct Builtins {
13    nat: Option<NameId>,
14    strs: [Option<NameId>; 2],
15    pub(crate) quot: [Option<NameId>; 5],
16}
17
18impl Builtins {
19    pub(crate) fn find(env: &Env) -> Self {
20        let find = |s| env.find_name(s);
21        Self {
22            nat: find("Nat"),
23            strs: [find("Char.ofNat"), find("String.ofList")],
24            quot: ["Eq", "Quot", "Quot.mk", "Quot.lift", "Quot.ind"].map(find),
25        }
26    }
27}
28
29/// How much of a constant a walk follows.
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
31pub(crate) enum Depth {
32    /// Everything, proofs included.
33    Full,
34    /// Theorems as axioms over their types, as [`crate::Exporter::statements`] writes them.
35    Statements,
36}
37
38/// Something a constant or term mentions.
39#[derive(Debug, Clone, Copy)]
40pub(crate) enum Dep {
41    Expr(ExprId),
42    Const(NameId),
43    /// Declared together with the constant, in one inductive or quotient block.
44    Member(NameId),
45    /// Reached through a literal rather than named.
46    Literal(NameId),
47    /// A theorem whose value is still in its olean.
48    Unloaded(NameId),
49}
50
51/// An inductive block: its types, their constructors, and the recursors.
52pub(crate) struct Family<'e> {
53    pub(crate) types: Vec<(&'e Const, &'e Inductive)>,
54    pub(crate) ctors: Vec<(&'e Const, &'e Ctor)>,
55    pub(crate) recs: Vec<(&'e Const, &'e Rec)>,
56}
57
58impl<'e> Family<'e> {
59    fn consts(&self) -> impl Iterator<Item = &'e Const> + '_ {
60        let ctors = self.ctors.iter().map(|&(k, _)| k);
61        let recs = self.recs.iter().map(|&(k, _)| k);
62        self.types.iter().map(|&(k, _)| k).chain(ctors).chain(recs)
63    }
64
65    /// Every term of the block, in the order lean4export visits them.
66    fn terms(&self) -> impl Iterator<Item = ExprId> + '_ {
67        let rules = self
68            .recs
69            .iter()
70            .flat_map(|(_, r)| r.rules.iter().map(|u| u.rhs));
71        self.consts().map(|k| k.ty).chain(rules)
72    }
73}
74
75/// What a decoding walk has visited, kept across its rounds.
76pub(super) struct Walk {
77    consts: FxHashSet<NameId>,
78    exprs: Vec<bool>,
79    depth: Depth,
80}
81
82impl Walk {
83    fn new(depth: Depth) -> Self {
84        Self {
85            consts: FxHashSet::default(),
86            exprs: Vec::new(),
87            depth,
88        }
89    }
90}
91
92impl Env {
93    /// Like [`Env::load_with`], but decode only the theorem values that exporting `consts`
94    /// reaches. The rest stay in their oleans, as `None`.
95    pub fn load_cone(
96        search: &[PathBuf],
97        roots: &[&str],
98        consts: &[&str],
99        jobs: usize,
100        progress: &(dyn Fn(usize, usize) + Sync),
101    ) -> Result<Self> {
102        let mut env = Self::build(search, roots, jobs, progress, true, true)?;
103        let mut live = env.live.take().expect("built live");
104        let mut todo = consts
105            .iter()
106            .map(|c| {
107                env.find_name(c)
108                    .map(Dep::Const)
109                    .ok_or_else(|| Error::UnknownConstant((*c).to_owned()))
110            })
111            .collect::<Result<Vec<_>>>()?;
112        let pending: FxHashMap<NameId, (usize, u64)> = live
113            .loaded
114            .iter()
115            .enumerate()
116            .flat_map(|(i, l)| l.pending.iter().map(move |&(n, o)| (n, (i, o))))
117            .collect();
118        let mut walk = Walk::new(Depth::Full);
119        loop {
120            let mut due: Vec<_> = env
121                .walk(&mut walk, todo)?
122                .into_iter()
123                .map(|n| (pending[&n], n))
124                .collect();
125            if due.is_empty() {
126                env.live = Some(live);
127                return Ok(env);
128            }
129            due.sort_unstable_by_key(|&(p, _)| p);
130            todo = Vec::new();
131            for (n, v) in env.decode_values(&mut live, &due)? {
132                if let Some(Const {
133                    kind: Kind::Thm(t), ..
134                }) = env.consts.get_mut(&n)
135                {
136                    t.value = Some(v);
137                }
138                todo.push(Dep::Expr(v));
139            }
140        }
141    }
142
143    /// Load like [`Env::load_with`], leaving every theorem value undecoded, for
144    /// [`Env::statement`] and [`crate::Exporter::statements`].
145    pub fn load_statements(
146        search: &[PathBuf],
147        roots: &[&str],
148        jobs: usize,
149        progress: &(dyn Fn(usize, usize) + Sync),
150    ) -> Result<Self> {
151        Self::build(search, roots, jobs, progress, false, true)
152    }
153
154    /// What the statements of `consts` rest on, with the index of each one's module, in
155    /// load order: everything their types mention, and through it the values of
156    /// definitions and whole inductive families, but no proof. A theorem reached inside a
157    /// definition is taken as stated, as [`crate::Exporter::statements`] writes it.
158    pub fn statement(&self, consts: &[NameId]) -> Result<Vec<(usize, NameId)>> {
159        let mut w = Walk::new(Depth::Statements);
160        let todo = consts
161            .iter()
162            .map(|&c| {
163                self.consts
164                    .contains_key(&c)
165                    .then_some(Dep::Const(c))
166                    .ok_or_else(|| Error::UnknownConstant(self.display(c)))
167            })
168            .collect::<Result<_>>()?;
169        self.walk(&mut w, todo)?;
170        let mut module = 0;
171        Ok(self
172            .order
173            .iter()
174            .enumerate()
175            .filter_map(|(i, c)| {
176                while self.ends.get(module).is_some_and(|&end| i >= end) {
177                    module += 1;
178                }
179                w.consts.contains(c).then_some((module, *c))
180            })
181            .collect())
182    }
183
184    /// Continue `w` from `todo` over everything an export of it would visit, returning the
185    /// theorems reached whose values are not decoded.
186    fn walk(&self, w: &mut Walk, mut todo: Vec<Dep>) -> Result<Vec<NameId>> {
187        w.exprs.resize(self.exprs.bound(), false);
188        let b = Builtins::find(self);
189        let mut out = Vec::new();
190        while let Some(dep) = todo.pop() {
191            match dep {
192                Dep::Expr(e) => {
193                    if !mem::replace(&mut w.exprs[e.index()], true) {
194                        self.children(e, &b, |d| todo.push(d));
195                    }
196                }
197                Dep::Const(c) | Dep::Member(c) | Dep::Literal(c) => {
198                    if !w.consts.insert(c) {
199                        continue;
200                    }
201                    if let Some(k) = self.consts.get(&c) {
202                        self.mentions(k, w.depth, &b, |d| todo.push(d))?;
203                    }
204                }
205                Dep::Unloaded(c) => out.push(c),
206            }
207        }
208        Ok(out)
209    }
210
211    /// The immediate subterms of `e` and the constants it names or its literals need.
212    pub(crate) fn children(&self, e: ExprId, b: &Builtins, mut f: impl FnMut(Dep)) {
213        match &self.exprs[e] {
214            Expr::Const(n, _) => f(Dep::Const(*n)),
215            Expr::App(x, y) | Expr::Lam(_, x, y, _) | Expr::Pi(_, x, y, _) => {
216                f(Dep::Expr(*x));
217                f(Dep::Expr(*y));
218            }
219            Expr::Let(_, t, v, x) => [t, v, x].into_iter().for_each(|&e| f(Dep::Expr(e))),
220            Expr::Proj(_, _, x) => f(Dep::Expr(*x)),
221            Expr::Nat(_) => b.nat.into_iter().for_each(|c| f(Dep::Literal(c))),
222            Expr::Str(_) => b
223                .strs
224                .into_iter()
225                .flatten()
226                .for_each(|c| f(Dep::Literal(c))),
227            Expr::BVar(_) | Expr::Sort(_) => {}
228        }
229    }
230
231    /// What declaring `k` mentions at `depth`, in the order lean4export visits it. A
232    /// constructor or recursor leads to its inductive, which declares the whole block.
233    pub(crate) fn mentions(
234        &self,
235        k: &Const,
236        depth: Depth,
237        b: &Builtins,
238        mut f: impl FnMut(Dep),
239    ) -> Result<()> {
240        let mut ty = || f(Dep::Expr(k.ty));
241        match &k.kind {
242            Kind::Axiom => ty(),
243            Kind::Thm(_) if depth == Depth::Statements => ty(),
244            Kind::Defn(Defn { value, .. }) | Kind::Opaque(Body { value, .. }) => {
245                ty();
246                f(Dep::Expr(*value));
247            }
248            Kind::Thm(t) => {
249                ty();
250                f(t.value.map_or(Dep::Unloaded(k.name), Dep::Expr));
251            }
252            Kind::Quot(_) => {
253                let [eq, quot @ ..] = b.quot;
254                quot.into_iter().flatten().for_each(|c| f(Dep::Member(c)));
255                if let Some(eq) = eq {
256                    f(Dep::Const(eq));
257                }
258            }
259            Kind::Induct(ind) => {
260                let fam = self.family(k, ind)?;
261                fam.consts().for_each(|c| f(Dep::Member(c.name)));
262                fam.terms().for_each(|e| f(Dep::Expr(e)));
263            }
264            Kind::Ctor(c) => f(Dep::Const(c.induct)),
265            Kind::Rec(r) => r.all.iter().for_each(|&i| f(Dep::Const(i))),
266        }
267        Ok(())
268    }
269
270    /// The mutual block of `base`: its types, their constructors and their recursors.
271    pub(crate) fn family<'e>(&'e self, base: &Const, ind: &'e Inductive) -> Result<Family<'e>> {
272        let types = ind
273            .all
274            .iter()
275            .map(|&n| {
276                self.lookup(n, "inductive", |k| match k {
277                    Kind::Induct(i) => Some(i),
278                    _ => None,
279                })
280            })
281            .collect::<Result<Vec<_>>>()?;
282        let ctors = types
283            .iter()
284            .flat_map(|(_, i)| &i.ctors)
285            .map(|&c| {
286                self.lookup(c, "constructor", |k| match k {
287                    Kind::Ctor(c) => Some(c),
288                    _ => None,
289                })
290            })
291            .collect::<Result<Vec<_>>>()?;
292        let recs = self
293            .recursors
294            .get(&base.name)
295            .map_or(&[][..], Vec::as_slice)
296            .iter()
297            .map(|&r| {
298                self.lookup(r, "recursor", |k| match k {
299                    Kind::Rec(r) => Some(r),
300                    _ => None,
301                })
302            })
303            .collect::<Result<Vec<_>>>()?;
304        Ok(Family { types, ctors, recs })
305    }
306
307    /// The constant `n` as the kind `pick` selects, `what` naming it in the error.
308    pub(crate) fn lookup<'e, T>(
309        &'e self,
310        n: NameId,
311        what: &str,
312        pick: impl Fn(&'e Kind) -> Option<&'e T>,
313    ) -> Result<(&'e Const, &'e T)> {
314        self.consts
315            .get(&n)
316            .and_then(|c| Some((c, pick(&c.kind)?)))
317            .ok_or_else(|| corrupt(format!("{} is not a known {what}", self.display(n))))
318    }
319}