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