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