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