Skip to main content

olean_export/
olean.rs

1use crate::error::{at, corrupt, Error, Result};
2use memmap2::{Mmap, MmapOptions};
3use std::{fs::File, ops::RangeInclusive, path::Path, str};
4
5// `ConstantInfo` constructor tags.
6pub(crate) const AXIOM: u8 = 0;
7pub(crate) const DEFN: u8 = 1;
8pub(crate) const THM: u8 = 2;
9pub(crate) const OPAQUE: u8 = 3;
10pub(crate) const QUOT: u8 = 4;
11pub(crate) const INDUCT: u8 = 5;
12pub(crate) const CTOR: u8 = 6;
13pub(crate) const REC: u8 = 7;
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
16pub(crate) enum Safety {
17    Safe,
18    Unsafe,
19    Partial,
20}
21
22const ARRAY: u8 = 246;
23const SCALAR_ARRAY: u8 = 248;
24const STRING: u8 = 249;
25const MPZ: u8 = 250;
26const THUNK: u8 = 251;
27const TASK: u8 = 252;
28const REF: u8 = 253;
29
30/// Fields of the fixed-size header that precedes every compacted region.
31#[derive(Debug, Clone, Default)]
32pub struct Header {
33    pub version: String,
34    pub githash: String,
35    pub gmp: bool,
36}
37
38#[derive(Debug)]
39pub(crate) struct Part {
40    pub(crate) base: u64,
41    slot: usize,
42    pub(crate) bytes: Mmap,
43}
44
45/// One module's compacted regions. Objects are addressed by the absolute pointers the
46/// compactor wrote, and the parts of a `module` file share one address space.
47#[derive(Debug)]
48pub(crate) struct Image {
49    pub(crate) parts: Vec<Part>,
50    pub(crate) header: Header,
51    pub(crate) root: u64,
52    /// The root of the first part, which lists what the module exports.
53    pub(crate) public: u64,
54}
55
56/// The Lean releases whose object layouts this reader has been checked against.
57pub const SUPPORTED: RangeInclusive<u32> = 26..=35;
58
59fn cstr(b: &[u8]) -> String {
60    String::from_utf8_lossy(b.split(|&c| c == 0).next().unwrap_or_default()).into_owned()
61}
62
63impl Image {
64    pub(crate) fn open(path: &Path) -> Result<Self> {
65        let mut img = Self {
66            parts: Vec::new(),
67            header: Header::default(),
68            root: 0,
69            public: 0,
70        };
71        img.push_part(path)?;
72        Ok(img)
73    }
74
75    /// Open a module's `.olean`, adding its `.server` and `.private` parts if it is in the
76    /// module system. The root is then the private part's, which sees all of them.
77    pub(crate) fn open_module(path: &Path) -> Result<Self> {
78        let mut img = Self::open(path)?;
79        if img.scalar_u8(img.root, 0).map_err(at(path))? == 1 {
80            img.push_part(&path.with_extension("olean.server"))?;
81            img.push_part(&path.with_extension("olean.private"))?;
82        }
83        Ok(img)
84    }
85
86    pub(crate) fn push_part(&mut self, path: &Path) -> Result<()> {
87        self.map(path).map_err(at(path))
88    }
89
90    fn map(&mut self, path: &Path) -> Result<()> {
91        let file = File::open(path)?;
92        // SAFETY: the map is read-only and lives as long as `self`. Rewriting an .olean while
93        // it is being read is undefined behaviour, the same assumption Lean makes when it maps them.
94        #[allow(unsafe_code)]
95        let bytes = unsafe { MmapOptions::new().populate().map(&file)? };
96        bytes.advise(memmap2::Advice::WillNeed)?;
97        if bytes.len() < 96 || &bytes[..5] != b"olean" {
98            return Err(Error::NotOlean);
99        }
100        if bytes[5] != 2 {
101            return Err(Error::Format(bytes[5]));
102        }
103        let version = cstr(&bytes[7..40]);
104        let minor = version
105            .strip_prefix("4.")
106            .and_then(|v| v.split('.').next()?.parse::<u32>().ok());
107        if !minor.is_some_and(|m| SUPPORTED.contains(&m)) {
108            return Err(Error::UnsupportedLean(version));
109        }
110        let githash = cstr(&bytes[40..80]);
111        if !self.parts.is_empty() && githash != self.header.githash {
112            return Err(corrupt(format!(
113                "built by Lean {githash}, but its .olean by {}",
114                self.header.githash
115            )));
116        }
117        self.header = Header {
118            version,
119            githash,
120            gmp: bytes[6] & 1 == 1,
121        };
122        let base = le64(&bytes[80..88]);
123        self.root = le64(&bytes[88..96]);
124        if self.parts.is_empty() {
125            self.public = self.root;
126        }
127        let slot = self.slots();
128        self.parts.push(Part { base, slot, bytes });
129        Ok(())
130    }
131
132    /// One past the largest slot, where every 8-byte aligned object address has a slot.
133    pub(crate) fn slots(&self) -> usize {
134        self.parts.last().map_or(0, |p| p.slot + p.bytes.len() / 8)
135    }
136
137    /// A dense index for the object at `addr`, for memo tables.
138    pub(crate) fn slot(&self, addr: u64) -> Result<usize> {
139        self.locate(addr, 8).map(|(p, off)| p.slot + off / 8)
140    }
141
142    fn locate(&self, addr: u64, len: usize) -> Result<(&Part, usize)> {
143        self.parts
144            .iter()
145            .find_map(|p| {
146                let off = usize::try_from(addr.checked_sub(p.base)?).ok()?;
147                (off.checked_add(len)? <= p.bytes.len()).then_some((p, off))
148            })
149            .ok_or_else(|| corrupt(format!("pointer {addr:#x} is outside the module")))
150    }
151
152    fn bytes(&self, addr: u64, len: usize) -> Result<&[u8]> {
153        self.locate(addr, len)
154            .map(|(p, off)| &p.bytes[off..off + len])
155    }
156
157    pub(crate) fn u64(&self, addr: u64) -> Result<u64> {
158        self.bytes(addr, 8).map(le64)
159    }
160
161    pub(crate) fn u8(&self, addr: u64) -> Result<u8> {
162        Ok(self.bytes(addr, 1)?[0])
163    }
164
165    pub(crate) fn tag(&self, o: u64) -> Result<u8> {
166        self.u8(o + 7)
167    }
168
169    pub(crate) fn field(&self, o: u64, i: u64) -> Result<u64> {
170        self.u64(o + 8 + 8 * i)
171    }
172
173    /// The `k`th byte of a constructor's scalar area, which follows its object fields.
174    pub(crate) fn scalar_u8(&self, o: u64, k: u64) -> Result<u8> {
175        let num_objs = u64::from(self.u8(o + 6)?);
176        self.u8(o + 8 + 8 * num_objs + k)
177    }
178
179    /// How the `ConstantInfo` at `info` was declared, from the flags its kind keeps in the
180    /// scalar area of its value.
181    pub(crate) fn safety(&self, info: u64) -> Result<Safety> {
182        let val = self.field(info, 0)?;
183        let flag = |k| Ok::<_, Error>(self.scalar_u8(val, k)? != 0);
184        Ok(match self.tag(info)? {
185            DEFN => match self.scalar_u8(val, 0)? {
186                0 => Safety::Unsafe,
187                1 => Safety::Safe,
188                _ => Safety::Partial,
189            },
190            AXIOM | OPAQUE | CTOR if flag(0)? => Safety::Unsafe,
191            INDUCT | REC if flag(1)? => Safety::Unsafe,
192            _ => Safety::Safe,
193        })
194    }
195
196    pub(crate) fn scalar_u32(&self, o: u64) -> Result<u32> {
197        let b = self.bytes(o + 8 + 8 * u64::from(self.u8(o + 6)?), 4)?;
198        Ok(u32::from_le_bytes([b[0], b[1], b[2], b[3]]))
199    }
200
201    /// The size in bytes of the object at `o`, calling `f` on each object it points to.
202    pub(crate) fn children(&self, o: u64, mut f: impl FnMut(u64)) -> Result<u64> {
203        let mut each = |from: u64, n: u64| -> Result<()> {
204            for i in 0..n {
205                let c = self.u64(from + 8 * i)?;
206                if !is_scalar(c) {
207                    f(c);
208                }
209            }
210            Ok(())
211        };
212        let b = self.bytes(o + 4, 2)?;
213        let cs_sz = u64::from(u16::from_le_bytes([b[0], b[1]]));
214        let size = match self.tag(o)? {
215            ARRAY => {
216                each(o + 24, self.u64(o + 8)?)?;
217                24 + 8 * self.u64(o + 16)?
218            }
219            SCALAR_ARRAY => 24 + u64::from(self.u8(o + 6)?) * self.u64(o + 16)?,
220            STRING => 32 + self.u64(o + 16)?,
221            THUNK | TASK => {
222                each(o + 8, 1)?;
223                24
224            }
225            REF => {
226                each(o + 8, 1)?;
227                16
228            }
229            MPZ => cs_sz,
230            t if t > MPZ => return Err(corrupt(format!("unexpected object tag {t} at {o:#x}"))),
231            _ => {
232                each(o + 8, u64::from(self.u8(o + 6)?))?;
233                cs_sz
234            }
235        };
236        Ok(size.next_multiple_of(8))
237    }
238
239    fn expect(&self, o: u64, tag: u8, what: &str) -> Result<()> {
240        if is_scalar(o) || self.tag(o)? != tag {
241            return Err(corrupt(format!("expected {what} at {o:#x}")));
242        }
243        Ok(())
244    }
245
246    pub(crate) fn str(&self, o: u64) -> Result<&str> {
247        self.expect(o, STRING, "a string")?;
248        let size = usize::try_from(self.u64(o + 8)?).map_err(corrupt)?;
249        let bytes = self.bytes(o + 32, size.saturating_sub(1))?;
250        str::from_utf8(bytes).map_err(corrupt)
251    }
252
253    pub(crate) fn array(&self, o: u64) -> Result<Vec<u64>> {
254        self.expect(o, ARRAY, "an array")?;
255        (0..self.u64(o + 8)?)
256            .map(|i| self.u64(o + 24 + 8 * i))
257            .collect()
258    }
259
260    pub(crate) fn list(&self, mut o: u64) -> Result<Vec<u64>> {
261        let mut out = Vec::new();
262        while !is_scalar(o) {
263            out.push(self.field(o, 0)?);
264            o = self.field(o, 1)?;
265        }
266        Ok(out)
267    }
268
269    pub(crate) fn nat_decimal(&self, o: u64) -> Result<String> {
270        if is_scalar(o) {
271            return Ok((o >> 1).to_string());
272        }
273        self.expect(o, MPZ, "a Nat")?;
274        // GMP's `__mpz_struct` has an `i32` size and 64-bit limbs; without GMP, Lean's own
275        // `mpz` has a `bool` sign, a `size_t` size and 32-bit digits. Either way the compactor
276        // puts the digits right after the object, so the stored pointer must say so.
277        let (at, n, width) = if self.header.gmp {
278            let b = self.bytes(o + 12, 4)?;
279            let n = i32::from_le_bytes([b[0], b[1], b[2], b[3]]).unsigned_abs();
280            (o + 24, u64::from(n), 8)
281        } else {
282            (o + 32, self.u64(o + 16)?, 4)
283        };
284        let len = n
285            .checked_mul(width)
286            .and_then(|l| usize::try_from(l).ok())
287            .ok_or_else(|| corrupt(format!("Nat at {o:#x} is too large")))?;
288        if self.u64(at - 8)? != at {
289            return Err(corrupt(format!("Nat at {o:#x} does not hold its digits")));
290        }
291        let digits: Vec<u64> = self
292            .bytes(at, len)?
293            .chunks(8)
294            .map(|c| c.iter().rev().fold(0, |v, &b| v << 8 | u64::from(b)))
295            .collect();
296        Ok(decimal(&digits))
297    }
298}
299
300pub(crate) const fn is_scalar(o: u64) -> bool {
301    o & 1 == 1
302}
303
304pub(crate) fn small_nat(o: u64) -> Result<u64> {
305    if is_scalar(o) {
306        Ok(o >> 1)
307    } else {
308        Err(corrupt(format!(
309            "expected a small Nat, found pointer {o:#x}"
310        )))
311    }
312}
313
314fn le64(b: &[u8]) -> u64 {
315    let mut a = [0; 8];
316    a.copy_from_slice(&b[..8]);
317    u64::from_le_bytes(a)
318}
319
320/// The decimal digits of the natural number with little-endian 64-bit `limbs`.
321///
322/// Divide and conquer (malachite): converting one limb at a time is quadratic, and some
323/// developments hold literals of millions of digits (CFSG's certificates: the export spent
324/// over an hour here before).
325fn decimal(limbs: &[u64]) -> String {
326    malachite_nz::natural::Natural::from_limbs_asc(limbs).to_string()
327}
328
329#[cfg(test)]
330mod decimal_tests {
331    use super::decimal;
332    use std::fmt::Write as _;
333
334    /// The conversion this replaces: one limb at a time, quadratic.
335    fn schoolbook(limbs: &[u64]) -> String {
336        const CHUNK: u128 = 10_000_000_000_000_000_000;
337        let mut limbs = limbs.to_vec();
338        let mut parts = Vec::new();
339        while limbs.iter().any(|&l| l != 0) {
340            let mut rem = 0u128;
341            for l in limbs.iter_mut().rev() {
342                let cur = (rem << 64) | u128::from(*l);
343                *l = u64::try_from(cur / CHUNK).unwrap();
344                rem = cur % CHUNK;
345            }
346            parts.push(u64::try_from(rem).unwrap());
347            while limbs.last() == Some(&0) {
348                limbs.pop();
349            }
350        }
351        let mut s = parts.pop().unwrap_or(0).to_string();
352        for p in parts.iter().rev() {
353            write!(s, "{p:019}").unwrap();
354        }
355        s
356    }
357
358    #[test]
359    fn agrees_with_schoolbook() {
360        let mut x = 0x9e37_79b9_7f4a_7c15_u64;
361        let mut next = || {
362            x ^= x << 13;
363            x ^= x >> 7;
364            x ^= x << 17;
365            x
366        };
367        for limbs in [
368            vec![],
369            vec![0],
370            vec![1],
371            vec![u64::MAX],
372            vec![0, 1],
373            vec![u64::MAX; 3],
374        ] {
375            assert_eq!(decimal(&limbs), schoolbook(&limbs), "{limbs:?}");
376        }
377        for n in [1, 2, 7, 40, 300, 2000] {
378            let limbs: Vec<u64> = (0..n).map(|_| next()).collect();
379            assert_eq!(decimal(&limbs), schoolbook(&limbs), "{n} limbs");
380        }
381    }
382}