Skip to main content

olean_export/
olean.rs

1use crate::error::{at, corrupt, Error, Result};
2use memmap2::{Mmap, MmapOptions};
3use std::{fmt::Write as _, 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}
53
54/// The Lean releases whose object layouts this reader has been checked against.
55pub const SUPPORTED: RangeInclusive<u32> = 26..=35;
56
57fn cstr(b: &[u8]) -> String {
58    String::from_utf8_lossy(b.split(|&c| c == 0).next().unwrap_or_default()).into_owned()
59}
60
61impl Image {
62    pub(crate) fn open(path: &Path) -> Result<Self> {
63        let mut img = Self {
64            parts: Vec::new(),
65            header: Header::default(),
66            root: 0,
67        };
68        img.push_part(path)?;
69        Ok(img)
70    }
71
72    /// Open a module's `.olean`, adding its `.server` and `.private` parts if it is in the
73    /// module system. The root is then the private part's, which sees all of them.
74    pub(crate) fn open_module(path: &Path) -> Result<Self> {
75        let mut img = Self::open(path)?;
76        if img.scalar_u8(img.root, 0).map_err(at(path))? == 1 {
77            img.push_part(&path.with_extension("olean.server"))?;
78            img.push_part(&path.with_extension("olean.private"))?;
79        }
80        Ok(img)
81    }
82
83    pub(crate) fn push_part(&mut self, path: &Path) -> Result<()> {
84        self.map(path).map_err(at(path))
85    }
86
87    fn map(&mut self, path: &Path) -> Result<()> {
88        let file = File::open(path)?;
89        // SAFETY: the map is read-only and lives as long as `self`. Rewriting an .olean while
90        // it is being read is undefined behaviour, the same assumption Lean makes when it maps them.
91        #[allow(unsafe_code)]
92        let bytes = unsafe { MmapOptions::new().populate().map(&file)? };
93        bytes.advise(memmap2::Advice::WillNeed)?;
94        if bytes.len() < 96 || &bytes[..5] != b"olean" {
95            return Err(Error::NotOlean);
96        }
97        if bytes[5] != 2 {
98            return Err(Error::Format(bytes[5]));
99        }
100        let version = cstr(&bytes[7..40]);
101        let minor = version
102            .strip_prefix("4.")
103            .and_then(|v| v.split('.').next()?.parse().ok());
104        if !minor.is_some_and(|m| SUPPORTED.contains(&m)) {
105            return Err(Error::UnsupportedLean(version));
106        }
107        let githash = cstr(&bytes[40..80]);
108        if !self.parts.is_empty() && githash != self.header.githash {
109            return Err(corrupt(format!(
110                "built by Lean {githash}, but its .olean by {}",
111                self.header.githash
112            )));
113        }
114        self.header = Header {
115            version,
116            githash,
117            gmp: bytes[6] & 1 == 1,
118        };
119        let base = le64(&bytes[80..88]);
120        self.root = le64(&bytes[88..96]);
121        let slot = self.slots();
122        self.parts.push(Part { base, slot, bytes });
123        Ok(())
124    }
125
126    /// One past the largest slot, where every 8-byte aligned object address has a slot.
127    pub(crate) fn slots(&self) -> usize {
128        self.parts.last().map_or(0, |p| p.slot + p.bytes.len() / 8)
129    }
130
131    /// A dense index for the object at `addr`, for memo tables.
132    pub(crate) fn slot(&self, addr: u64) -> Result<usize> {
133        self.locate(addr, 8).map(|(p, off)| p.slot + off / 8)
134    }
135
136    fn locate(&self, addr: u64, len: usize) -> Result<(&Part, usize)> {
137        self.parts
138            .iter()
139            .find_map(|p| {
140                let off = usize::try_from(addr.checked_sub(p.base)?).ok()?;
141                (off.checked_add(len)? <= p.bytes.len()).then_some((p, off))
142            })
143            .ok_or_else(|| corrupt(format!("pointer {addr:#x} is outside the module")))
144    }
145
146    fn bytes(&self, addr: u64, len: usize) -> Result<&[u8]> {
147        self.locate(addr, len)
148            .map(|(p, off)| &p.bytes[off..off + len])
149    }
150
151    pub(crate) fn u64(&self, addr: u64) -> Result<u64> {
152        self.bytes(addr, 8).map(le64)
153    }
154
155    pub(crate) fn u8(&self, addr: u64) -> Result<u8> {
156        Ok(self.bytes(addr, 1)?[0])
157    }
158
159    pub(crate) fn tag(&self, o: u64) -> Result<u8> {
160        self.u8(o + 7)
161    }
162
163    pub(crate) fn field(&self, o: u64, i: u64) -> Result<u64> {
164        self.u64(o + 8 + 8 * i)
165    }
166
167    /// The `k`th byte of a constructor's scalar area, which follows its object fields.
168    pub(crate) fn scalar_u8(&self, o: u64, k: u64) -> Result<u8> {
169        let num_objs = u64::from(self.u8(o + 6)?);
170        self.u8(o + 8 + 8 * num_objs + k)
171    }
172
173    /// How the `ConstantInfo` at `info` was declared, from the flags its kind keeps in the
174    /// scalar area of its value.
175    pub(crate) fn safety(&self, info: u64) -> Result<Safety> {
176        let val = self.field(info, 0)?;
177        let flag = |k| Ok::<_, Error>(self.scalar_u8(val, k)? != 0);
178        Ok(match self.tag(info)? {
179            DEFN => match self.scalar_u8(val, 0)? {
180                0 => Safety::Unsafe,
181                1 => Safety::Safe,
182                _ => Safety::Partial,
183            },
184            AXIOM | OPAQUE | CTOR if flag(0)? => Safety::Unsafe,
185            INDUCT | REC if flag(1)? => Safety::Unsafe,
186            _ => Safety::Safe,
187        })
188    }
189
190    pub(crate) fn scalar_u32(&self, o: u64) -> Result<u32> {
191        let b = self.bytes(o + 8 + 8 * u64::from(self.u8(o + 6)?), 4)?;
192        Ok(u32::from_le_bytes([b[0], b[1], b[2], b[3]]))
193    }
194
195    /// The size in bytes of the object at `o`, calling `f` on each object it points to.
196    pub(crate) fn children(&self, o: u64, mut f: impl FnMut(u64)) -> Result<u64> {
197        let mut each = |from: u64, n: u64| -> Result<()> {
198            for i in 0..n {
199                let c = self.u64(from + 8 * i)?;
200                if !is_scalar(c) {
201                    f(c);
202                }
203            }
204            Ok(())
205        };
206        let b = self.bytes(o + 4, 2)?;
207        let cs_sz = u64::from(u16::from_le_bytes([b[0], b[1]]));
208        let size = match self.tag(o)? {
209            ARRAY => {
210                each(o + 24, self.u64(o + 8)?)?;
211                24 + 8 * self.u64(o + 16)?
212            }
213            SCALAR_ARRAY => 24 + u64::from(self.u8(o + 6)?) * self.u64(o + 16)?,
214            STRING => 32 + self.u64(o + 16)?,
215            THUNK | TASK => {
216                each(o + 8, 1)?;
217                24
218            }
219            REF => {
220                each(o + 8, 1)?;
221                16
222            }
223            MPZ => cs_sz,
224            t if t > MPZ => return Err(corrupt(format!("unexpected object tag {t} at {o:#x}"))),
225            _ => {
226                each(o + 8, u64::from(self.u8(o + 6)?))?;
227                cs_sz
228            }
229        };
230        Ok(size.next_multiple_of(8))
231    }
232
233    fn expect(&self, o: u64, tag: u8, what: &str) -> Result<()> {
234        if is_scalar(o) || self.tag(o)? != tag {
235            return Err(corrupt(format!("expected {what} at {o:#x}")));
236        }
237        Ok(())
238    }
239
240    pub(crate) fn str(&self, o: u64) -> Result<&str> {
241        self.expect(o, STRING, "a string")?;
242        let size = usize::try_from(self.u64(o + 8)?).map_err(corrupt)?;
243        let bytes = self.bytes(o + 32, size.saturating_sub(1))?;
244        str::from_utf8(bytes).map_err(corrupt)
245    }
246
247    pub(crate) fn array(&self, o: u64) -> Result<Vec<u64>> {
248        self.expect(o, ARRAY, "an array")?;
249        (0..self.u64(o + 8)?)
250            .map(|i| self.u64(o + 24 + 8 * i))
251            .collect()
252    }
253
254    pub(crate) fn list(&self, mut o: u64) -> Result<Vec<u64>> {
255        let mut out = Vec::new();
256        while !is_scalar(o) {
257            out.push(self.field(o, 0)?);
258            o = self.field(o, 1)?;
259        }
260        Ok(out)
261    }
262
263    pub(crate) fn nat_decimal(&self, o: u64) -> Result<String> {
264        if is_scalar(o) {
265            return Ok((o >> 1).to_string());
266        }
267        self.expect(o, MPZ, "a Nat")?;
268        if !self.header.gmp {
269            return Err(corrupt("big Nat literals need a Lean built with GMP"));
270        }
271        let b = self.bytes(o + 12, 4)?;
272        let size = u64::from(i32::from_le_bytes([b[0], b[1], b[2], b[3]]).unsigned_abs());
273        let mut digits = (0..size)
274            .map(|i| self.u64(o + 24 + 8 * i))
275            .collect::<Result<Vec<_>>>()?;
276        Ok(decimal(&mut digits))
277    }
278}
279
280pub(crate) const fn is_scalar(o: u64) -> bool {
281    o & 1 == 1
282}
283
284pub(crate) fn small_nat(o: u64) -> Result<u64> {
285    if is_scalar(o) {
286        Ok(o >> 1)
287    } else {
288        Err(corrupt(format!(
289            "expected a small Nat, found pointer {o:#x}"
290        )))
291    }
292}
293
294fn le64(b: &[u8]) -> u64 {
295    let mut a = [0; 8];
296    a.copy_from_slice(&b[..8]);
297    u64::from_le_bytes(a)
298}
299
300fn decimal(limbs: &mut Vec<u64>) -> String {
301    const CHUNK: u64 = 10_000_000_000_000_000_000;
302    let mut parts = Vec::new();
303    while limbs.iter().any(|&l| l != 0) {
304        let mut rem = 0u128;
305        for l in limbs.iter_mut().rev() {
306            let cur = (rem << 64) | u128::from(*l);
307            *l = u64::try_from(cur / u128::from(CHUNK)).expect("quotient fits");
308            rem = cur % u128::from(CHUNK);
309        }
310        parts.push(u64::try_from(rem).expect("remainder fits"));
311        while limbs.last() == Some(&0) {
312            limbs.pop();
313        }
314    }
315    let mut s = parts.pop().unwrap_or(0).to_string();
316    for p in parts.iter().rev() {
317        let _ = write!(s, "{p:019}");
318    }
319    s
320}