use super::{
term::{Body, Const, Ctor, Defn, Expr, ExprId, Inductive, Kind, NameId, Rec},
Env,
};
use crate::error::{corrupt, Error, Result};
use rustc_hash::{FxHashMap, FxHashSet};
use std::{mem, path::PathBuf};
#[derive(Debug, Clone, Copy)]
pub(crate) struct Builtins {
nat: Option<NameId>,
strs: [Option<NameId>; 2],
pub(crate) quot: [Option<NameId>; 5],
}
impl Builtins {
pub(crate) fn find(env: &Env) -> Self {
let find = |s| env.find_name(s);
Self {
nat: find("Nat"),
strs: [find("Char.ofNat"), find("String.ofList")],
quot: ["Eq", "Quot", "Quot.mk", "Quot.lift", "Quot.ind"].map(find),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Depth {
Full,
Statements,
}
#[derive(Debug, Clone, Copy)]
pub(crate) enum Dep {
Expr(ExprId),
Const(NameId),
Member(NameId),
Literal(NameId),
Unloaded(NameId),
}
pub(crate) struct Family<'e> {
pub(crate) types: Vec<(&'e Const, &'e Inductive)>,
pub(crate) ctors: Vec<(&'e Const, &'e Ctor)>,
pub(crate) recs: Vec<(&'e Const, &'e Rec)>,
}
impl<'e> Family<'e> {
fn consts(&self) -> impl Iterator<Item = &'e Const> + '_ {
let ctors = self.ctors.iter().map(|&(k, _)| k);
let recs = self.recs.iter().map(|&(k, _)| k);
self.types.iter().map(|&(k, _)| k).chain(ctors).chain(recs)
}
fn terms(&self) -> impl Iterator<Item = ExprId> + '_ {
let rules = self
.recs
.iter()
.flat_map(|(_, r)| r.rules.iter().map(|u| u.rhs));
self.consts().map(|k| k.ty).chain(rules)
}
}
pub(super) struct Walk {
consts: FxHashSet<NameId>,
exprs: Vec<bool>,
depth: Depth,
}
impl Walk {
fn new(depth: Depth) -> Self {
Self {
consts: FxHashSet::default(),
exprs: Vec::new(),
depth,
}
}
}
impl Env {
pub fn load_cone(
search: &[PathBuf],
roots: &[&str],
consts: &[&str],
jobs: usize,
progress: &(dyn Fn(usize, usize) + Sync),
) -> Result<Self> {
let mut env = Self::build(search, roots, jobs, progress, true, true)?;
let mut live = env.live.take().expect("built live");
let mut todo = consts
.iter()
.map(|c| {
env.find_name(c)
.map(Dep::Const)
.ok_or_else(|| Error::UnknownConstant((*c).to_owned()))
})
.collect::<Result<Vec<_>>>()?;
let pending: FxHashMap<NameId, (usize, u64)> = live
.loaded
.iter()
.enumerate()
.flat_map(|(i, l)| l.pending.iter().map(move |&(n, o)| (n, (i, o))))
.collect();
let mut walk = Walk::new(Depth::Full);
loop {
let mut due: Vec<_> = env
.walk(&mut walk, todo)?
.into_iter()
.map(|n| (pending[&n], n))
.collect();
if due.is_empty() {
env.live = Some(live);
return Ok(env);
}
due.sort_unstable_by_key(|&(p, _)| p);
todo = Vec::new();
for (n, v) in env.decode_values(&mut live, &due)? {
if let Some(Const {
kind: Kind::Thm(t), ..
}) = env.consts.get_mut(&n)
{
t.value = Some(v);
}
todo.push(Dep::Expr(v));
}
}
}
pub fn load_statements(
search: &[PathBuf],
roots: &[&str],
jobs: usize,
progress: &(dyn Fn(usize, usize) + Sync),
) -> Result<Self> {
Self::build(search, roots, jobs, progress, false, true)
}
pub fn statement(&self, consts: &[NameId]) -> Result<Vec<(usize, NameId)>> {
let mut w = Walk::new(Depth::Statements);
let todo = consts
.iter()
.map(|&c| {
self.consts
.contains_key(&c)
.then_some(Dep::Const(c))
.ok_or_else(|| Error::UnknownConstant(self.display(c)))
})
.collect::<Result<_>>()?;
self.walk(&mut w, todo)?;
let mut module = 0;
Ok(self
.order
.iter()
.enumerate()
.filter_map(|(i, c)| {
while self.ends.get(module).is_some_and(|&end| i >= end) {
module += 1;
}
w.consts.contains(c).then_some((module, *c))
})
.collect())
}
fn walk(&self, w: &mut Walk, mut todo: Vec<Dep>) -> Result<Vec<NameId>> {
w.exprs.resize(self.exprs.bound(), false);
let b = Builtins::find(self);
let mut out = Vec::new();
while let Some(dep) = todo.pop() {
match dep {
Dep::Expr(e) => {
if !mem::replace(&mut w.exprs[e.index()], true) {
self.children(e, &b, |d| todo.push(d));
}
}
Dep::Const(c) | Dep::Member(c) | Dep::Literal(c) => {
if !w.consts.insert(c) {
continue;
}
if let Some(k) = self.consts.get(&c) {
self.mentions(k, w.depth, &b, |d| todo.push(d))?;
}
}
Dep::Unloaded(c) => out.push(c),
}
}
Ok(out)
}
pub(crate) fn children(&self, e: ExprId, b: &Builtins, mut f: impl FnMut(Dep)) {
match &self.exprs[e] {
Expr::Const(n, _) => f(Dep::Const(*n)),
Expr::App(x, y) | Expr::Lam(_, x, y, _) | Expr::Pi(_, x, y, _) => {
f(Dep::Expr(*x));
f(Dep::Expr(*y));
}
Expr::Let(l) => [l.1, l.2, l.3].into_iter().for_each(|e| f(Dep::Expr(e))),
Expr::Proj(_, _, x) => f(Dep::Expr(*x)),
Expr::Nat(_) => b.nat.into_iter().for_each(|c| f(Dep::Literal(c))),
Expr::Str(_) => b
.strs
.into_iter()
.flatten()
.for_each(|c| f(Dep::Literal(c))),
Expr::BVar(_) | Expr::Sort(_) => {}
}
}
pub(crate) fn mentions(
&self,
k: &Const,
depth: Depth,
b: &Builtins,
mut f: impl FnMut(Dep),
) -> Result<()> {
let mut ty = || f(Dep::Expr(k.ty));
match &k.kind {
Kind::Axiom => ty(),
Kind::Thm(_) if depth == Depth::Statements => ty(),
Kind::Defn(Defn { value, .. }) | Kind::Opaque(Body { value, .. }) => {
ty();
f(Dep::Expr(*value));
}
Kind::Thm(t) => {
ty();
f(t.value.map_or(Dep::Unloaded(k.name), Dep::Expr));
}
Kind::Quot(_) => {
let [eq, quot @ ..] = b.quot;
quot.into_iter().flatten().for_each(|c| f(Dep::Member(c)));
if let Some(eq) = eq {
f(Dep::Const(eq));
}
}
Kind::Induct(ind) => {
let fam = self.family(k, ind)?;
fam.consts().for_each(|c| f(Dep::Member(c.name)));
fam.terms().for_each(|e| f(Dep::Expr(e)));
}
Kind::Ctor(c) => f(Dep::Const(c.induct)),
Kind::Rec(r) => r.all.iter().for_each(|&i| f(Dep::Const(i))),
}
Ok(())
}
pub(crate) fn family<'e>(&'e self, base: &Const, ind: &'e Inductive) -> Result<Family<'e>> {
let types = ind
.all
.iter()
.map(|&n| {
self.lookup(n, "inductive", |k| match k {
Kind::Induct(i) => Some(i),
_ => None,
})
})
.collect::<Result<Vec<_>>>()?;
let ctors = types
.iter()
.flat_map(|(_, i)| &i.ctors)
.map(|&c| {
self.lookup(c, "constructor", |k| match k {
Kind::Ctor(c) => Some(c),
_ => None,
})
})
.collect::<Result<Vec<_>>>()?;
let recs = self
.recursors
.get(&base.name)
.map_or(&[][..], Vec::as_slice)
.iter()
.map(|&r| {
self.lookup(r, "recursor", |k| match k {
Kind::Rec(r) => Some(r),
_ => None,
})
})
.collect::<Result<Vec<_>>>()?;
Ok(Family { types, ctors, recs })
}
pub(crate) fn lookup<'e, T>(
&'e self,
n: NameId,
what: &str,
pick: impl Fn(&'e Kind) -> Option<&'e T>,
) -> Result<(&'e Const, &'e T)> {
self.consts
.get(&n)
.and_then(|c| Some((c, pick(&c.kind)?)))
.ok_or_else(|| corrupt(format!("{} is not a known {what}", self.display(n))))
}
}