1use 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
22pub 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 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
105fn 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
123struct Printer<'e> {
125 env: &'e Env,
126 max: usize,
127 out: String,
128 scope: Vec<String>,
129 loose: FxHashMap<ExprId, u64>,
130}
131
132const TOP: u8 = 0;
134const DOMAIN: u8 = 1;
135const ARG: u8 = 2;
136
137enum Step {
139 Expr(ExprId, u8),
140 Text(String),
141 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 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 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 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
420fn 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}