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#[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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
31pub(crate) enum Depth {
32 Full,
34 Statements,
36}
37
38#[derive(Debug, Clone, Copy)]
40pub(crate) enum Dep {
41 Expr(ExprId),
42 Const(NameId),
43 Member(NameId),
45 Literal(NameId),
47 Unloaded(NameId),
49}
50
51pub(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 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
75pub(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 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 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 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 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 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(l) => [l.1, l.2, l.3].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 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 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 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}