1use crate::error::{at, corrupt, Error, Result};
2use memmap2::{Mmap, MmapOptions};
3use std::{fs::File, ops::RangeInclusive, path::Path, str};
4
5pub(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#[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#[derive(Debug)]
48pub(crate) struct Image {
49 pub(crate) parts: Vec<Part>,
50 pub(crate) header: Header,
51 pub(crate) root: u64,
52 pub(crate) public: u64,
54}
55
56pub 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 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 #[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 pub(crate) fn slots(&self) -> usize {
134 self.parts.last().map_or(0, |p| p.slot + p.bytes.len() / 8)
135 }
136
137 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 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 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 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 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
320fn 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 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}