Skip to main content

olean_export/
statement.rs

1//! What a theorem's statement rests on, printed as raw terms for a person to review.
2//!
3//! Notation, coercions and macros never reach an olean, so the terms print as the kernel
4//! sees them, in Lean syntax but without notation. Binder names are only labels: they come
5//! from one of the copies of a shared term, and are renamed apart from each other and from
6//! every constant, so that no name reads as something it is not.
7
8use crate::{
9    env::{resolve, Binder, Env, Expr, ExprId, Hints, Kind, Level, LevelId, NameId},
10    error::Result,
11    olean::{small_nat, Image},
12};
13use rustc_hash::FxHashMap;
14use std::{
15    collections::hash_map::Entry,
16    fmt::Write as _,
17    io::Write,
18    mem,
19    path::{Path, PathBuf},
20};
21
22/// Print the statements of `roots` and what they rest on, outside the modules `trust` names.
23///
24/// Every definition, inductive, opaque, axiom and theorem reached prints in load order with
25/// the lines of source it came from, theorems without their proofs. A module is trusted if a name in `trust` is it or a prefix of it.
26/// Each term stops after `max` characters, if not 0.
27pub fn report(
28    env: &Env,
29    search: &[PathBuf],
30    roots: &[NameId],
31    trust: &[String],
32    max: usize,
33    out: &mut dyn Write,
34) -> Result<()> {
35    let cone = env.statement(roots)?;
36    let trusted = |m: usize| {
37        let m = &env.modules[m];
38        trust.iter().any(|t| {
39            m == t
40                || m.strip_prefix(t.as_str())
41                    .is_some_and(|r| r.starts_with('.'))
42        })
43    };
44    // constructors and recursors print with their inductive
45    let listed = |&(_, c): &(usize, NameId)| {
46        !roots.contains(&c) && !matches!(env.consts[&c].kind, Kind::Ctor(_) | Kind::Rec(_))
47    };
48    let (hidden, shown): (Vec<_>, Vec<_>) = cone
49        .iter()
50        .copied()
51        .filter(listed)
52        .partition(|&(m, _)| trusted(m));
53    let named = |pick: fn(&Kind) -> bool| {
54        let names: Vec<String> = cone
55            .iter()
56            .filter(|&&(_, c)| !roots.contains(&c) && pick(&env.consts[&c].kind))
57            .map(|&(_, c)| env.display(c))
58            .collect();
59        if names.is_empty() {
60            "none".into()
61        } else {
62            names.join(", ")
63        }
64    };
65    let axioms = named(|k| matches!(k, Kind::Axiom));
66    let assumed = named(|k| matches!(k, Kind::Thm(_)));
67    let mut modules: Vec<usize> = shown.iter().map(|&(m, _)| m).collect();
68    modules.dedup();
69    let names: Vec<String> = roots.iter().map(|&c| env.display(c)).collect();
70    let plural = |n: usize, what: &str| format!("{n} {what}{}", if n == 1 { "" } else { "s" });
71    write!(
72        out,
73        "-- {} rests on {} in {}",
74        names.join(", "),
75        plural(shown.len(), "declaration"),
76        plural(modules.len(), "module"),
77    )?;
78    if !trust.is_empty() {
79        write!(out, ", and {} more in {}", hidden.len(), trust.join(", "))?;
80    }
81    writeln!(
82        out,
83        "\n-- axioms: {axioms}\n-- theorems taken as stated: {assumed}"
84    )?;
85    let mut p = Printer::new(env, max);
86    let mut lines = FxHashMap::default();
87    let module: FxHashMap<NameId, usize> = cone.iter().map(|&(m, c)| (c, m)).collect();
88    let roots = roots.iter().map(|&c| (module[&c], c));
89    for (m, c) in roots.chain(shown) {
90        let module = &env.modules[m];
91        if let Entry::Vacant(e) = lines.entry(m) {
92            e.insert(ranges(&resolve(search, module)?)?);
93        }
94        let file = format!("{}.lean", module.replace('.', "/"));
95        let at = match lines[&m].get(&env.display(c)) {
96            Some((a, b)) if a == b => format!("{file}:{a}"),
97            Some((a, b)) => format!("{file}:{a}-{b}"),
98            None => file,
99        };
100        writeln!(out, "\n-- {at}\n{}", p.decl(c))?;
101    }
102    Ok(())
103}
104
105/// The first and last source line of each declaration of a module, from `declRangeExt`.
106fn ranges(path: &Path) -> Result<FxHashMap<String, (u64, u64)>> {
107    let img = Image::open_module(path)?;
108    let mut out = FxHashMap::default();
109    for e in img.array(img.field(img.root, 4)?)? {
110        if img.str_name(img.field(e, 0)?)? != "Lean.declRangeExt" {
111            continue;
112        }
113        for d in img.array(img.field(e, 1)?)? {
114            let range = img.field(img.field(d, 1)?, 0)?;
115            let line = |pos| img.field(pos, 0).and_then(small_nat);
116            let span = (line(img.field(range, 0)?)?, line(img.field(range, 2)?)?);
117            out.insert(img.str_name(img.field(d, 0)?)?, span);
118        }
119    }
120    Ok(out)
121}
122
123/// Prints declarations and terms without notation, naming bound variables apart.
124struct Printer<'e> {
125    env: &'e Env,
126    max: usize,
127    out: String,
128    scope: Vec<String>,
129    loose: FxHashMap<ExprId, u64>,
130}
131
132/// Contexts, loosest first: a binder body, an arrow's domain, an application's argument.
133const TOP: u8 = 0;
134const DOMAIN: u8 = 1;
135const ARG: u8 = 2;
136
137/// A step of printing a term, kept on a stack since terms can be deeper than the call stack.
138enum Step {
139    Expr(ExprId, u8),
140    Text(String),
141    /// The rest of a run of binders, ending at `sep` with the scope back at `depth`.
142    Binders {
143        e: ExprId,
144        lam: bool,
145        sep: &'static str,
146        depth: usize,
147    },
148    Bind(String),
149    Unbind(usize),
150}
151
152impl<'e> Printer<'e> {
153    fn new(env: &'e Env, max: usize) -> Self {
154        Self {
155            env,
156            max,
157            out: String::new(),
158            scope: Vec::new(),
159            loose: FxHashMap::default(),
160        }
161    }
162
163    fn decl(&mut self, c: NameId) -> String {
164        let env = self.env;
165        let k = &env.consts[&c];
166        let (word, value) = match &k.kind {
167            Kind::Axiom => ("axiom", None),
168            Kind::Defn(d) if d.hints == Hints::Abbrev => ("abbrev", Some(d.value)),
169            Kind::Defn(d) => ("def", Some(d.value)),
170            Kind::Thm(_) => ("theorem", None),
171            Kind::Opaque(_) => ("opaque", None),
172            Kind::Quot(_) => ("quot", None),
173            Kind::Induct(_) => ("inductive", None),
174            Kind::Ctor(_) => ("ctor", None),
175            Kind::Rec(_) => ("recursor", None),
176        };
177        let mut s = format!("{word} {}", self.head(c));
178        if let Some(v) = value {
179            write!(s, " :=\n  {}", self.term(v)).expect("string");
180        }
181        if let Kind::Induct(i) = &k.kind {
182            for &ctor in &i.ctors {
183                write!(s, "\n| {}", self.head(ctor)).expect("string");
184            }
185        }
186        s
187    }
188
189    fn head(&mut self, c: NameId) -> String {
190        let k = &self.env.consts[&c];
191        let ps: Vec<String> = k
192            .level_params
193            .iter()
194            .map(|&n| self.env.display(n))
195            .collect();
196        let us = if ps.is_empty() {
197            String::new()
198        } else {
199            format!(".{{{}}}", ps.join(", "))
200        };
201        format!("{}{us} : {}", self.env.display(c), self.term(k.ty))
202    }
203
204    fn term(&mut self, e: ExprId) -> String {
205        self.out.clear();
206        self.scope.clear();
207        let mut todo = vec![Step::Expr(e, TOP)];
208        while let Some(step) = todo.pop() {
209            if self.max > 0 && self.out.len() > self.max {
210                break;
211            }
212            self.step(step, &mut todo);
213        }
214        let mut s = mem::take(&mut self.out);
215        if self.max > 0 && s.len() > self.max {
216            let mut cut = self.max;
217            while !s.is_char_boundary(cut) {
218                cut -= 1;
219            }
220            s.truncate(cut);
221            s.push_str(" ...[cut]");
222        }
223        s
224    }
225
226    fn step(&mut self, step: Step, todo: &mut Vec<Step>) {
227        let env = self.env;
228        let text = |s: &str| Step::Text(s.to_owned());
229        let paren = |on: bool, mut steps: Vec<Step>| {
230            if on {
231                steps.insert(0, text("("));
232                steps.push(text(")"));
233            }
234            steps
235        };
236        let depth = self.scope.len();
237        let steps = match step {
238            Step::Text(s) => {
239                self.out.push_str(&s);
240                return;
241            }
242            Step::Bind(x) => {
243                self.scope.push(x);
244                return;
245            }
246            Step::Unbind(d) => {
247                self.scope.truncate(d);
248                return;
249            }
250            Step::Binders { e, lam, sep, depth } => match self.binder(e, lam) {
251                Some((n, ty, body, bi)) => {
252                    let x = self.fresh(n);
253                    let (l, r) = match bi {
254                        Binder::Default => ("(", ")"),
255                        Binder::Implicit => ("{", "}"),
256                        Binder::StrictImplicit => ("⦃", "⦄"),
257                        Binder::InstImplicit => ("[", "]"),
258                    };
259                    vec![
260                        Step::Text(format!(" {l}{x} : ")),
261                        Step::Expr(ty, TOP),
262                        text(r),
263                        Step::Bind(x),
264                        Step::Binders {
265                            e: body,
266                            lam,
267                            sep,
268                            depth,
269                        },
270                    ]
271                }
272                None => vec![text(sep), Step::Expr(e, TOP), Step::Unbind(depth)],
273            },
274            Step::Expr(e, prec) => match &env.exprs[e] {
275                Expr::BVar(i) => {
276                    let name = usize::try_from(*i)
277                        .ok()
278                        .and_then(|i| depth.checked_sub(i + 1))
279                        .map_or_else(|| format!("#{i}"), |j| self.scope[j].clone());
280                    vec![Step::Text(name)]
281                }
282                Expr::Sort(l) => {
283                    let s = sort(env, *l);
284                    paren(prec >= ARG && s.contains(' '), vec![Step::Text(s)])
285                }
286                Expr::Const(n, us) => {
287                    let mut s = env.display(*n);
288                    if !us.is_empty() {
289                        let us: Vec<String> = us.iter().map(|&u| level(env, u, false)).collect();
290                        write!(s, ".{{{}}}", us.join(", ")).expect("string");
291                    }
292                    vec![Step::Text(s)]
293                }
294                Expr::App(..) => {
295                    let mut args = Vec::new();
296                    let mut f = e;
297                    while let Expr::App(g, a) = &env.exprs[f] {
298                        args.push(*a);
299                        f = *g;
300                    }
301                    let mut steps = vec![Step::Expr(f, ARG)];
302                    for &a in args.iter().rev() {
303                        steps.extend([text(" "), Step::Expr(a, ARG)]);
304                    }
305                    paren(prec >= ARG, steps)
306                }
307                Expr::Pi(_, ty, body, bi) if *bi == Binder::Default && self.range(*body) == 0 => {
308                    let steps = vec![
309                        Step::Expr(*ty, DOMAIN),
310                        text(" → "),
311                        Step::Bind(String::new()),
312                        Step::Expr(*body, TOP),
313                        Step::Unbind(depth),
314                    ];
315                    paren(prec > TOP, steps)
316                }
317                Expr::Lam(..) | Expr::Pi(..) => {
318                    let lam = matches!(env.exprs[e], Expr::Lam(..));
319                    let (word, sep) = if lam { ("fun", " => ") } else { ("∀", ", ") };
320                    let steps = vec![text(word), Step::Binders { e, lam, sep, depth }];
321                    paren(prec > TOP, steps)
322                }
323                Expr::Let(n, ty, v, body) => {
324                    let x = self.fresh(*n);
325                    let steps = vec![
326                        Step::Text(format!("let {x} : ")),
327                        Step::Expr(*ty, TOP),
328                        text(" := "),
329                        Step::Expr(*v, TOP),
330                        text("; "),
331                        Step::Bind(x),
332                        Step::Expr(*body, TOP),
333                        Step::Unbind(depth),
334                    ];
335                    paren(prec > TOP, steps)
336                }
337                Expr::Nat(n) => vec![Step::Text(n.to_string())],
338                Expr::Str(s) => vec![Step::Text(quote(s))],
339                Expr::Proj(_, i, x) => vec![Step::Expr(*x, ARG), Step::Text(format!(".{}", i + 1))],
340            },
341        };
342        todo.extend(steps.into_iter().rev());
343    }
344
345    /// The binder at `e` if it continues a run of lambdas, or of dependent or non-default pis.
346    fn binder(&mut self, e: ExprId, lam: bool) -> Option<(NameId, ExprId, ExprId, Binder)> {
347        match self.env.exprs[e] {
348            Expr::Lam(n, t, b, bi) if lam => Some((n, t, b, bi)),
349            Expr::Pi(n, t, b, bi) if !lam && (bi != Binder::Default || self.range(b) > 0) => {
350                Some((n, t, b, bi))
351            }
352            _ => None,
353        }
354    }
355
356    /// One more than the largest loose bound variable of `e`, or 0 if it is closed.
357    fn range(&mut self, e: ExprId) -> u64 {
358        let mut todo = vec![(e, false)];
359        while let Some((x, ready)) = todo.pop() {
360            if self.loose.contains_key(&x) {
361                continue;
362            }
363            let (subs, binds): (Vec<ExprId>, usize) = match self.env.exprs[x] {
364                Expr::App(a, b) => (vec![a, b], 0),
365                Expr::Lam(_, t, b, _) | Expr::Pi(_, t, b, _) => (vec![t, b], 1),
366                Expr::Let(_, t, v, b) => (vec![t, v, b], 1),
367                Expr::Proj(_, _, y) => (vec![y], 0),
368                _ => (Vec::new(), 0),
369            };
370            if !ready && !subs.is_empty() {
371                todo.push((x, true));
372                todo.extend(subs.into_iter().map(|s| (s, false)));
373                continue;
374            }
375            let last = subs.len().saturating_sub(binds);
376            let r = match self.env.exprs[x] {
377                Expr::BVar(i) => i + 1,
378                _ => subs
379                    .iter()
380                    .enumerate()
381                    .map(|(j, s)| {
382                        let r = self.loose[s];
383                        if j >= last {
384                            r.saturating_sub(1)
385                        } else {
386                            r
387                        }
388                    })
389                    .max()
390                    .unwrap_or(0),
391            };
392            self.loose.insert(x, r);
393        }
394        self.loose[&e]
395    }
396
397    /// The binder's name without hygiene, made distinct from every name in scope and every
398    /// constant.
399    fn fresh(&self, n: NameId) -> String {
400        let env = self.env;
401        let full = env.display(n);
402        let base = full.split("._@").next().unwrap_or_default();
403        let base = if base.is_empty() { "x" } else { base };
404        let taken = |x: &str| {
405            self.scope.iter().any(|s| s == x)
406                || env
407                    .find_name(x)
408                    .is_some_and(|c| env.consts.contains_key(&c))
409        };
410        let mut x = base.to_owned();
411        let mut i = 1;
412        while taken(&x) {
413            x = format!("{base}_{i}");
414            i += 1;
415        }
416        x
417    }
418}
419
420/// `s` as a Lean string literal.
421fn quote(s: &str) -> String {
422    let mut q = String::from('"');
423    for c in s.chars() {
424        match c {
425            '"' => q.push_str("\\\""),
426            '\\' => q.push_str("\\\\"),
427            '\n' => q.push_str("\\n"),
428            '\t' => q.push_str("\\t"),
429            '\r' => q.push_str("\\r"),
430            c if c.is_control() => write!(q, "\\x{:02x}", u32::from(c)).expect("string"),
431            c => q.push(c),
432        }
433    }
434    q.push('"');
435    q
436}
437
438fn sort(env: &Env, l: LevelId) -> String {
439    match &env.levels[l] {
440        Level::Zero => "Prop".into(),
441        Level::Succ(u) if matches!(env.levels[*u], Level::Zero) => "Type".into(),
442        Level::Succ(u) => format!("Type {}", level(env, *u, true)),
443        _ => format!("Sort {}", level(env, l, true)),
444    }
445}
446
447fn level(env: &Env, l: LevelId, arg: bool) -> String {
448    let mut n = 0;
449    let mut base = l;
450    while let Level::Succ(u) = &env.levels[base] {
451        n += 1;
452        base = *u;
453    }
454    let paren = |s: String| if arg { format!("({s})") } else { s };
455    let b = match &env.levels[base] {
456        Level::Zero => return n.to_string(),
457        Level::Param(p) => env.display(*p),
458        Level::Max(a, b) => paren(format!(
459            "max {} {}",
460            level(env, *a, true),
461            level(env, *b, true)
462        )),
463        Level::IMax(a, b) => paren(format!(
464            "imax {} {}",
465            level(env, *a, true),
466            level(env, *b, true)
467        )),
468        Level::Succ(_) => unreachable!("peeled"),
469    };
470    if n == 0 {
471        b
472    } else {
473        paren(format!("{b} + {n}"))
474    }
475}