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    borrow::Cow,
27    env,
28    path::{Path, PathBuf},
29    sync::atomic::{AtomicU64, Ordering::Relaxed},
30    thread,
31};
32
33static LINEAGE: AtomicU64 = AtomicU64::new(0);
34
35/// Every constant reachable from a set of root modules, in import order.
36#[derive(Debug)]
37pub struct Env {
38    pub names: Table<Name>,
39    pub levels: Table<Level>,
40    pub exprs: Exprs,
41    pub consts: FxHashMap<NameId, Const>,
42    pub order: Vec<NameId>,
43    pub recursors: FxHashMap<NameId, Vec<NameId>>,
44    pub modules: Vec<String>,
45    /// The direct imports of each module in `modules`.
46    pub imports: Vec<Vec<String>>,
47    pub header: Header,
48    pub skipped: usize,
49    /// Where each module's constants end in `order`.
50    ends: Vec<usize>,
51    pub(crate) lineage: u64,
52    live: Option<Box<Live>>,
53}
54
55/// Identifier-shaped tokens of Lean's term and command syntax, which a name must not print
56/// as. Universe syntax adds `max` and `imax`, which the statement printer escapes itself.
57#[rustfmt::skip]
58const KEYWORDS: &[&str] = &[
59    "Prop", "Sort", "Type", "abbrev", "at", "attribute", "axiom", "by", "calc", "class", "def",
60    "deriving", "do", "else", "end", "example", "export", "forall", "from", "fun", "have", "if",
61    "import", "in", "inductive", "instance", "let", "local", "macro", "match", "mutual",
62    "namespace", "noncomputable", "nofun", "nomatch", "opaque", "open", "partial", "private",
63    "protected", "scoped", "section", "set_option", "show", "sorry", "structure", "suffices",
64    "syntax", "then", "theorem", "this", "universe", "unsafe", "variable", "where", "with",
65];
66/// A name component in `«»` unless Lean would read it back as itself unescaped. Lean has no
67/// way to write a `»` in a name, so `»` and `\` are written after a `\`, which no name Lean
68/// can print contains.
69pub(crate) fn escape(s: &str) -> Cow<'_, str> {
70    let letter = |c: char| {
71        let u = u32::from(c);
72        c.is_ascii_alphabetic()
73            || c == '_'
74            || ((0x3b1..=0x3c9).contains(&u) && u != 0x3bb)
75            || ((0x391..=0x3a9).contains(&u) && u != 0x3a0 && u != 0x3a3)
76            || matches!(u, 0x3ca..=0x3fb | 0x1f00..=0x1ffe | 0x2100..=0x214f | 0x1d49c..=0x1d59f)
77    };
78    let rest = |c: char| {
79        letter(c)
80            || c.is_ascii_digit()
81            || matches!(c, '\'' | '!' | '?')
82            || matches!(u32::from(c), 0x2080..=0x2089 | 0x2090..=0x209c | 0x1d62..=0x1d6a | 0x2c7c)
83    };
84    let mut cs = s.chars();
85    let plain = cs.next().is_some_and(letter) && cs.all(rest) && !KEYWORDS.contains(&s);
86    if plain {
87        Cow::Borrowed(s)
88    } else if s.contains(['»', '\\']) {
89        Cow::Owned(format!("«{}»", s.replace('\\', "\\\\").replace('»', "\\»")))
90    } else {
91        Cow::Owned(format!("«{s}»"))
92    }
93}
94
95fn discover_all(search: &[PathBuf], roots: &[&str]) -> Result<Vec<(String, PathBuf)>> {
96    let mut seen = FxHashSet::default();
97    let mut found = Vec::new();
98    for root in roots {
99        discover(search, root, &mut seen, &mut found)?;
100    }
101    Ok(found)
102}
103
104/// Find `module` and its imports, appending them to `out` in import order.
105fn discover(
106    search: &[PathBuf],
107    module: &str,
108    seen: &mut FxHashSet<String>,
109    out: &mut Vec<(String, PathBuf)>,
110) -> Result<()> {
111    if !seen.insert(module.to_owned()) {
112        return Ok(());
113    }
114    let path = resolve(search, module)?;
115    let img = Image::open(&path)?;
116    let imports = img.imports().map_err(at(&path))?;
117    drop(img);
118    for import in &imports {
119        discover(search, import, seen, out)?;
120    }
121    out.push((module.to_owned(), path));
122    Ok(())
123}
124
125/// The `.olean` for a dotted module name such as `Init.Prelude`, from the first directory
126/// of `search` that has it.
127pub fn resolve(search: &[PathBuf], module: &str) -> Result<PathBuf> {
128    let rel: PathBuf = module.split('.').collect();
129    search
130        .iter()
131        .map(|dir| dir.join(&rel).with_extension("olean"))
132        .find(|p| p.is_file())
133        .ok_or_else(|| Error::ModuleNotFound(module.to_owned()))
134}
135
136#[must_use]
137pub fn search_path() -> Vec<PathBuf> {
138    let mut dirs: Vec<PathBuf> = env::var_os("LEAN_PATH")
139        .map(|p| env::split_paths(&p).collect())
140        .unwrap_or_default();
141    if let Some(root) = env::var_os("LEAN_SYSROOT") {
142        dirs.push(Path::new(&root).join("lib").join("lean"));
143    }
144    dirs
145}
146
147impl Env {
148    /// Load `roots` and their transitive imports, resolving modules against `search`.
149    pub fn load(search: &[PathBuf], roots: &[&str]) -> Result<Self> {
150        let jobs = thread::available_parallelism().map_or(1, usize::from);
151        Self::load_with(search, roots, jobs, &|_, _| {})
152    }
153
154    /// Like [`Env::load`] on `jobs` threads, calling `progress` with the number of modules
155    /// and constants decoded so far.
156    ///
157    /// Modules decode in parallel straight into shared tables, and the result is the same
158    /// for any `jobs`.
159    pub fn load_with(
160        search: &[PathBuf],
161        roots: &[&str],
162        jobs: usize,
163        progress: &(dyn Fn(usize, usize) + Sync),
164    ) -> Result<Self> {
165        Self::build(search, roots, jobs, progress, false, false)
166    }
167
168    fn build(
169        search: &[PathBuf],
170        roots: &[&str],
171        jobs: usize,
172        progress: &(dyn Fn(usize, usize) + Sync),
173        live: bool,
174        lazy: bool,
175    ) -> Result<Self> {
176        let found = discover_all(search, roots)?;
177        let stamps: Vec<Stamp> = found.iter().map(|(_, p)| stamp(p)).collect();
178        // Sizing the tables up front avoids rehashing them while they grow. Across Lean and
179        // Mathlib there is about one expression per 64 bytes of olean and one name per 1200.
180        let bytes: u64 = stamps.iter().flatten().map(|(len, _)| len).sum();
181        let estimate = |per: u64| usize::try_from(bytes / per).unwrap_or(0);
182        let tables = Tables {
183            names: Shared::new(Name::Anon, estimate(1200)),
184            levels: Shared::new(Level::Zero, 0),
185            exprs: SharedExprs::new(estimate(64)),
186        };
187        let paths: Vec<_> = found.iter().map(|(_, p)| p.as_path()).enumerate().collect();
188        let decoded = decode_all(&tables, &paths, jobs, progress, lazy);
189        let (exprs, index, ranks) = tables.exprs.freeze();
190        let kept = live.then_some((index, ranks));
191        let decoded = decoded?;
192        let mut env = Self {
193            names: tables.names.freeze(),
194            levels: tables.levels.freeze(),
195            exprs,
196            consts: FxHashMap::default(),
197            order: Vec::new(),
198            recursors: FxHashMap::default(),
199            modules: Vec::new(),
200            imports: Vec::new(),
201            header: Header::default(),
202            skipped: 0,
203            ends: Vec::new(),
204            lineage: LINEAGE.fetch_add(1, Relaxed),
205            live: None,
206        };
207        let loaded: Vec<_> = found
208            .into_iter()
209            .zip(stamps)
210            .zip(decoded)
211            .map(|(((module, path), stamp), m)| env.add(module, path, stamp, m))
212            .collect();
213        env.index(&loaded);
214        if let Some((index, ranks)) = kept {
215            env.live = Some(Box::new(Live {
216                search: search.to_vec(),
217                roots: roots.iter().map(|&r| r.to_owned()).collect(),
218                jobs,
219                index,
220                ranks,
221                loaded,
222            }));
223        }
224        Ok(env)
225    }
226
227    fn add(&mut self, module: String, path: PathBuf, stamp: Stamp, m: Module) -> Loaded {
228        let consts = m.consts.iter().map(|c| c.name).collect();
229        self.consts
230            .extend(m.consts.into_iter().map(|c| (c.name, c)));
231        Loaded {
232            module,
233            path,
234            stamp,
235            consts,
236            recursors: m.recursors,
237            skipped: m.skipped,
238            header: m.header,
239            imports: m.imports,
240            pending: m.pending,
241        }
242    }
243
244    /// Rebuild the load order and everything summed over modules.
245    fn index(&mut self, loaded: &[Loaded]) {
246        self.order = loaded
247            .iter()
248            .flat_map(|l| l.consts.iter().copied())
249            .collect();
250        self.recursors.clear();
251        // two modules may both declare a type, as realized or independent copies
252        for (ind, recs) in loaded.iter().flat_map(|l| &l.recursors) {
253            let all = self.recursors.entry(*ind).or_default();
254            for r in recs {
255                if !all.contains(r) {
256                    all.push(*r);
257                }
258            }
259        }
260        self.modules = loaded.iter().map(|l| l.module.clone()).collect();
261        self.imports = loaded.iter().map(|l| l.imports.clone()).collect();
262        self.header = loaded.last().map(|l| l.header.clone()).unwrap_or_default();
263        self.skipped = loaded.iter().map(|l| l.skipped).sum();
264        self.ends = loaded
265            .iter()
266            .scan(0, |end, l| {
267                *end += l.consts.len();
268                Some(*end)
269            })
270            .collect();
271    }
272
273    /// The constants module `m` declares, in load order.
274    #[must_use]
275    pub fn module_consts(&self, m: usize) -> &[NameId] {
276        let start = m.checked_sub(1).map_or(0, |p| self.ends[p]);
277        &self.order[start..self.ends[m]]
278    }
279
280    /// The constants `lean4export` exports when given no explicit names.
281    pub fn roots(&self) -> impl Iterator<Item = NameId> + '_ {
282        self.order.iter().copied().filter(|&c| !self.is_internal(c))
283    }
284
285    /// Look up a name such as `Nat.add` or `Foo.«bar.baz»`, as [`Env::display`] writes it,
286    /// without interning it.
287    #[must_use]
288    pub fn find_name(&self, dotted: &str) -> Option<NameId> {
289        let (mut pre, mut rest) = (ANON, dotted);
290        loop {
291            let (n, tail) = if let Some(r) = rest.strip_prefix('«') {
292                let (mut s, mut cs) = (String::new(), r.char_indices());
293                let end = loop {
294                    match cs.next()? {
295                        (_, '\\') => s.push(cs.next()?.1),
296                        (i, '»') => break i + '»'.len_utf8(),
297                        (_, c) => s.push(c),
298                    }
299                };
300                (Name::Str(pre, s.into()), &r[end..])
301            } else {
302                let (s, tail) = rest.split_at(rest.find('.').unwrap_or(rest.len()));
303                let n = s
304                    .parse()
305                    .map_or_else(|_| Name::Str(pre, s.into()), |i| Name::Num(pre, i));
306                (n, tail)
307            };
308            pre = self.names.get(&n)?;
309            match tail.strip_prefix('.') {
310                Some(t) => rest = t,
311                None => return tail.is_empty().then_some(pre),
312            }
313        }
314    }
315
316    /// `n` as Lean reads it back: components that are not plain identifiers, or are
317    /// keywords, go in `«»`.
318    #[must_use]
319    pub fn display(&self, n: NameId) -> String {
320        self.join(n, true)
321    }
322
323    /// `n` with its components joined as they are, as `declRangeExt` keys it.
324    pub(crate) fn dotted(&self, n: NameId) -> String {
325        self.join(n, false)
326    }
327
328    fn join(&self, n: NameId, escaped: bool) -> String {
329        let (pre, last) = match &self.names[n] {
330            Name::Anon => return String::new(),
331            Name::Str(p, s) if escaped => (*p, escape(s).into_owned()),
332            Name::Str(p, s) => (*p, s.to_string()),
333            Name::Num(p, i) => (*p, i.to_string()),
334        };
335        match pre {
336            ANON => last,
337            p => format!("{}.{last}", self.join(p, escaped)),
338        }
339    }
340
341    #[must_use]
342    pub fn is_internal(&self, n: NameId) -> bool {
343        match &self.names[n] {
344            Name::Anon => false,
345            Name::Str(p, s) => s.starts_with('_') || self.is_internal(*p),
346            Name::Num(p, _) => self.is_internal(*p),
347        }
348    }
349}