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