Skip to main content

olean_export/env/
mod.rs

1mod decode;
2mod reload;
3mod table;
4mod term;
5mod walk;
6
7pub use reload::Reload;
8pub use table::{Exprs, Table};
9pub use term::{
10    Binder, Body, Const, Ctor, Defn, Expr, ExprId, Hints, Id, Inductive, Kind, Level, LevelId,
11    Name, NameId, QuotKind, Rec, Rule, Theorem, ANON, ZERO,
12};
13pub(crate) use walk::{Builtins, Dep, Depth, Family};
14
15use self::{
16    decode::{decode_all, Module},
17    reload::{stamp, Live, Loaded, Stamp},
18    table::{Shared, SharedExprs, Tables},
19};
20use crate::{
21    error::{at, Error, Result},
22    olean::{Header, Image},
23};
24use rustc_hash::{FxHashMap, FxHashSet};
25use std::{
26    env,
27    path::{Path, PathBuf},
28    sync::atomic::{AtomicU64, Ordering::Relaxed},
29    thread,
30};
31
32static LINEAGE: AtomicU64 = AtomicU64::new(0);
33
34/// Every constant reachable from a set of root modules, in import order.
35#[derive(Debug)]
36pub struct Env {
37    pub names: Table<Name>,
38    pub levels: Table<Level>,
39    pub exprs: Exprs,
40    pub consts: FxHashMap<NameId, Const>,
41    pub order: Vec<NameId>,
42    pub recursors: FxHashMap<NameId, Vec<NameId>>,
43    pub modules: Vec<String>,
44    pub header: Header,
45    pub skipped: usize,
46    /// Where each module's constants end in `order`.
47    ends: Vec<usize>,
48    pub(crate) lineage: u64,
49    live: Option<Box<Live>>,
50}
51
52fn discover_all(search: &[PathBuf], roots: &[&str]) -> Result<Vec<(String, PathBuf)>> {
53    let mut seen = FxHashSet::default();
54    let mut found = Vec::new();
55    for root in roots {
56        discover(search, root, &mut seen, &mut found)?;
57    }
58    Ok(found)
59}
60
61/// Find `module` and its imports, appending them to `out` in import order.
62fn discover(
63    search: &[PathBuf],
64    module: &str,
65    seen: &mut FxHashSet<String>,
66    out: &mut Vec<(String, PathBuf)>,
67) -> Result<()> {
68    if !seen.insert(module.to_owned()) {
69        return Ok(());
70    }
71    let path = resolve(search, module)?;
72    let img = Image::open(&path)?;
73    let imports = img.imports().map_err(at(&path))?;
74    drop(img);
75    for import in &imports {
76        discover(search, import, seen, out)?;
77    }
78    out.push((module.to_owned(), path));
79    Ok(())
80}
81
82/// The `.olean` for a dotted module name such as `Init.Prelude`, from the first directory
83/// of `search` that has it.
84pub fn resolve(search: &[PathBuf], module: &str) -> Result<PathBuf> {
85    let rel: PathBuf = module.split('.').collect();
86    search
87        .iter()
88        .map(|dir| dir.join(&rel).with_extension("olean"))
89        .find(|p| p.is_file())
90        .ok_or_else(|| Error::ModuleNotFound(module.to_owned()))
91}
92
93#[must_use]
94pub fn search_path() -> Vec<PathBuf> {
95    let mut dirs: Vec<PathBuf> = env::var_os("LEAN_PATH")
96        .map(|p| env::split_paths(&p).collect())
97        .unwrap_or_default();
98    if let Some(root) = env::var_os("LEAN_SYSROOT") {
99        dirs.push(Path::new(&root).join("lib").join("lean"));
100    }
101    dirs
102}
103
104impl Env {
105    /// Load `roots` and their transitive imports, resolving modules against `search`.
106    pub fn load(search: &[PathBuf], roots: &[&str]) -> Result<Self> {
107        let jobs = thread::available_parallelism().map_or(1, usize::from);
108        Self::load_with(search, roots, jobs, &|_, _| {})
109    }
110
111    /// Like [`Env::load`] on `jobs` threads, calling `progress` with the number of modules
112    /// and constants decoded so far.
113    ///
114    /// Modules decode in parallel straight into shared tables, and the result is the same
115    /// for any `jobs`.
116    pub fn load_with(
117        search: &[PathBuf],
118        roots: &[&str],
119        jobs: usize,
120        progress: &(dyn Fn(usize, usize) + Sync),
121    ) -> Result<Self> {
122        Self::build(search, roots, jobs, progress, false, false)
123    }
124
125    fn build(
126        search: &[PathBuf],
127        roots: &[&str],
128        jobs: usize,
129        progress: &(dyn Fn(usize, usize) + Sync),
130        live: bool,
131        lazy: bool,
132    ) -> Result<Self> {
133        let found = discover_all(search, roots)?;
134        let stamps: Vec<Stamp> = found.iter().map(|(_, p)| stamp(p)).collect();
135        // Sizing the tables up front avoids rehashing them while they grow. Across Lean and
136        // Mathlib there is about one expression per 64 bytes of olean and one name per 1200.
137        let bytes: u64 = stamps.iter().flatten().map(|(len, _)| len).sum();
138        let estimate = |per: u64| usize::try_from(bytes / per).unwrap_or(0);
139        let tables = Tables {
140            names: Shared::new(Name::Anon, estimate(1200)),
141            levels: Shared::new(Level::Zero, 0),
142            exprs: SharedExprs::new(estimate(64)),
143        };
144        let paths: Vec<_> = found.iter().map(|(_, p)| p.as_path()).enumerate().collect();
145        let decoded = decode_all(&tables, &paths, jobs, progress, lazy);
146        let (exprs, index, ranks) = tables.exprs.freeze();
147        let kept = live.then_some((index, ranks));
148        let decoded = decoded?;
149        let mut env = Self {
150            names: tables.names.freeze(),
151            levels: tables.levels.freeze(),
152            exprs,
153            consts: FxHashMap::default(),
154            order: Vec::new(),
155            recursors: FxHashMap::default(),
156            modules: Vec::new(),
157            header: Header::default(),
158            skipped: 0,
159            ends: Vec::new(),
160            lineage: LINEAGE.fetch_add(1, Relaxed),
161            live: None,
162        };
163        let loaded: Vec<_> = found
164            .into_iter()
165            .zip(stamps)
166            .zip(decoded)
167            .map(|(((module, path), stamp), m)| env.add(module, path, stamp, m))
168            .collect();
169        env.index(&loaded);
170        if let Some((index, ranks)) = kept {
171            env.live = Some(Box::new(Live {
172                search: search.to_vec(),
173                roots: roots.iter().map(|&r| r.to_owned()).collect(),
174                jobs,
175                index,
176                ranks,
177                loaded,
178            }));
179        }
180        Ok(env)
181    }
182
183    fn add(&mut self, module: String, path: PathBuf, stamp: Stamp, m: Module) -> Loaded {
184        let consts = m.consts.iter().map(|c| c.name).collect();
185        self.consts
186            .extend(m.consts.into_iter().map(|c| (c.name, c)));
187        Loaded {
188            module,
189            path,
190            stamp,
191            consts,
192            recursors: m.recursors,
193            skipped: m.skipped,
194            header: m.header,
195            pending: m.pending,
196        }
197    }
198
199    /// Rebuild the load order and everything summed over modules.
200    fn index(&mut self, loaded: &[Loaded]) {
201        self.order = loaded
202            .iter()
203            .flat_map(|l| l.consts.iter().copied())
204            .collect();
205        self.recursors.clear();
206        for (ind, recs) in loaded.iter().flat_map(|l| &l.recursors) {
207            self.recursors.entry(*ind).or_default().extend(recs);
208        }
209        self.modules = loaded.iter().map(|l| l.module.clone()).collect();
210        self.header = loaded.last().map(|l| l.header.clone()).unwrap_or_default();
211        self.skipped = loaded.iter().map(|l| l.skipped).sum();
212        self.ends = loaded
213            .iter()
214            .scan(0, |end, l| {
215                *end += l.consts.len();
216                Some(*end)
217            })
218            .collect();
219    }
220
221    /// The constants `lean4export` exports when given no explicit names.
222    pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
223        self.order.iter().copied().filter(|&c| !self.is_internal(c))
224    }
225
226    /// Look up a dotted name such as `Nat.add` without interning it.
227    #[must_use]
228    pub fn find_name(&self, dotted: &str) -> Option<NameId> {
229        dotted.split('.').try_fold(ANON, |pre, s| {
230            let n = s
231                .parse()
232                .map_or_else(|_| Name::Str(pre, s.into()), |i| Name::Num(pre, i));
233            self.names.get(&n)
234        })
235    }
236
237    #[must_use]
238    pub fn display(&self, n: NameId) -> String {
239        match &self.names[n] {
240            Name::Anon => String::new(),
241            Name::Str(ANON, s) => s.to_string(),
242            Name::Num(ANON, i) => i.to_string(),
243            Name::Str(p, s) => format!("{}.{s}", self.display(*p)),
244            Name::Num(p, i) => format!("{}.{i}", self.display(*p)),
245        }
246    }
247
248    #[must_use]
249    pub fn is_internal(&self, n: NameId) -> bool {
250        match &self.names[n] {
251            Name::Anon => false,
252            Name::Str(p, s) => s.starts_with('_') || self.is_internal(*p),
253            Name::Num(p, _) => self.is_internal(*p),
254        }
255    }
256}