Skip to main content

olean_export/
join.rs

1//! Per-module exports and joining them back into one.
2
3use crate::{
4    blean::{self, Blean},
5    error::{corrupt, Result},
6    ndjson::{self, Ndjson},
7    record::{Counts, Record, Sink, Table},
8    Env, Exporter,
9};
10use rayon::prelude::*;
11use rustc_hash::{FxHashMap, FxHashSet};
12use serde_json::Value;
13use std::{
14    cell::OnceCell,
15    fs::File,
16    io::{BufWriter, Write},
17    path::{Path, PathBuf},
18};
19use xxhash_rust::xxh3::xxh3_128;
20
21/// The `meta` object of an NDJSON or blean export, read from its first record.
22pub fn meta(bytes: &[u8]) -> Result<Value> {
23    let json = if blean::sniff(bytes) {
24        match blean::entries(bytes)?.next() {
25            Some(Ok((Record::Meta(m), _))) => m.into_owned(),
26            Some(Err(e)) => return Err(e),
27            _ => return Err(corrupt("export does not start with meta")),
28        }
29    } else {
30        let line = bytes.split(|&b| b == b'\n').next().unwrap_or_default();
31        let v: Value = serde_json::from_slice(line)?;
32        v.get("meta")
33            .ok_or_else(|| corrupt("export does not start with meta"))?
34            .to_string()
35    };
36    Ok(serde_json::from_str(&json)?)
37}
38
39/// A per-module file's `meta`.
40struct Module {
41    name: String,
42    imports: Vec<(String, String)>,
43    interface: Option<String>,
44    public: bool,
45    inside: Vec<String>,
46}
47
48fn module(meta: &Value) -> Result<Module> {
49    let m = meta
50        .get("module")
51        .ok_or_else(|| corrupt("not a per-module export"))?;
52    let s = |v: &Value| v.as_str().map(str::to_owned);
53    let bad = || corrupt("bad module in meta");
54    Ok(Module {
55        name: m.get("name").and_then(s).ok_or_else(bad)?,
56        imports: m
57            .get("imports")
58            .and_then(Value::as_array)
59            .ok_or_else(bad)?
60            .iter()
61            .map(|i| Some((s(i.get("name")?)?, s(i.get("blake3")?)?)))
62            .collect::<Option<_>>()
63            .ok_or_else(bad)?,
64        interface: m.get("interface").and_then(s),
65        public: m.get("public").and_then(Value::as_bool) == Some(true),
66        inside: (m
67            .get("inside")
68            .and_then(Value::as_array)
69            .into_iter()
70            .flatten())
71        .filter_map(s)
72        .collect(),
73    })
74}
75
76/// Hex blake3 of an export's bytes, as per-module metas name their imports.
77#[must_use]
78pub fn hash(bytes: &[u8]) -> String {
79    blake3::hash(bytes).to_hex().to_string()
80}
81
82/// The order to join per-module `files` in, imports first. Fails unless every import of
83/// every file is among them with the hash it was exported against, or is the module whose
84/// interface has that hash.
85pub fn order(files: &[&[u8]]) -> Result<Vec<usize>> {
86    plan(files, None)
87}
88
89/// The files to join for `root` as Lean showed it its imports, imports first.
90pub fn view(files: &[&[u8]], root: &str) -> Result<Vec<usize>> {
91    plan(files, Some(root))
92}
93
94fn plan(files: &[&[u8]], root: Option<&str>) -> Result<Vec<usize>> {
95    let mods = files
96        .par_iter()
97        .map(|b| module(&meta(b)?))
98        .collect::<Result<Vec<_>>>()?;
99    let mut by_name: FxHashMap<&str, Vec<usize>> = FxHashMap::default();
100    for (i, m) in mods.iter().enumerate() {
101        let given = by_name.entry(m.name.as_str()).or_default();
102        if root.is_none() && !given.is_empty() {
103            return Err(corrupt(format!("module {} given twice", m.name)));
104        }
105        given.push(i);
106    }
107    // hashed on demand, a view only reads the files under its root
108    let hashes: Vec<OnceCell<String>> = vec![OnceCell::new(); files.len()];
109    let hashed = |j: usize| hashes[j].get_or_init(|| hash(files[j]));
110    let start = root
111        .map(|r| {
112            (by_name.get(r).into_iter().flatten().copied())
113                .find(|&j| !mods[j].public)
114                .ok_or_else(|| corrupt(format!("module {r} is not given")))
115        })
116        .transpose()?;
117    // a root outside the module system sees all of every module under it
118    let whole = start.is_none_or(|j| mods[j].interface.is_none());
119    let imports = |m: &Module| -> Result<Vec<usize>> {
120        let mut d = Vec::new();
121        for (i, h) in &m.imports {
122            let given = by_name
123                .get(i.as_str())
124                .ok_or_else(|| corrupt(format!("{} imports {i}, which is not given", m.name)))?;
125            let of = |j: usize| mods[j].interface.as_ref() == Some(h);
126            let found = (given.iter().copied())
127                .filter(|&j| hashed(j) == h || whole && of(j))
128                .min_by_key(|&j| mods[j].public);
129            d.push(found.ok_or_else(|| {
130                corrupt(if given.iter().any(|&j| of(j)) {
131                    format!(
132                        "{} imports the interface of {i}, which is not given",
133                        m.name
134                    )
135                } else {
136                    format!("{} was exported against another {i}", m.name)
137                })
138            })?);
139        }
140        Ok(d)
141    };
142    let mut deps = vec![Vec::new(); files.len()];
143    let mut seen = vec![false; files.len()];
144    let mut stack = start.map_or_else(|| (0..files.len()).collect(), |s| vec![s]);
145    while let Some(i) = stack.pop() {
146        if !std::mem::replace(&mut seen[i], true) {
147            deps[i] = imports(&mods[i])?;
148            stack.extend(&deps[i]);
149        }
150    }
151    if start.is_some() {
152        let reached: FxHashMap<&str, usize> = (0..files.len())
153            .filter(|&i| seen[i] && !mods[i].public)
154            .map(|i| (mods[i].name.as_str(), i))
155            .collect();
156        for d in deps.iter_mut().flatten() {
157            *d = *reached.get(mods[*d].name.as_str()).unwrap_or(d);
158        }
159        // the first copy of a declaration wins, so a module joined whole goes before an
160        // interface that states its constants as axioms
161        for (i, m) in mods.iter().enumerate() {
162            deps[i].extend(m.inside.iter().filter_map(|o| reached.get(o.as_str())));
163        }
164    }
165    let starts = start.map_or_else(|| (0..files.len()).collect(), |s| vec![s]);
166    let mut out = Vec::with_capacity(files.len());
167    let mut state = vec![0u8; files.len()];
168    for root in starts {
169        let mut stack = vec![(root, 0)];
170        while let Some((i, k)) = stack.pop() {
171            if k == 0 {
172                match state[i] {
173                    2 => continue,
174                    1 => return Err(corrupt(format!("import cycle at {}", mods[i].name))),
175                    _ => state[i] = 1,
176                }
177            }
178            if let Some(&j) = deps[i].get(k) {
179                stack.push((i, k + 1));
180                if state[j] != 2 {
181                    stack.push((j, 0));
182                }
183            } else {
184                state[i] = 2;
185                out.push(i);
186            }
187        }
188    }
189    Ok(out)
190}
191
192/// Shifts one file's ids past the files before it, and drops declarations an earlier file
193/// already made.
194struct Shift<'s, S> {
195    sink: &'s mut S,
196    base: Counts,
197    next: Counts,
198    names: &'s mut Vec<u128>,
199    declared: &'s mut FxHashSet<u128>,
200}
201
202impl<S: Sink> Shift<'_, S> {
203    fn name(&mut self, pre: u32, tag: u8, last: &[u8]) {
204        self.names.push(named(self.names[pre as usize], tag, last));
205    }
206
207    const fn id(&self, t: Table, i: u32) -> u32 {
208        match t {
209            Table::Names if i > 0 => self.base.names + i - 1,
210            Table::Levels if i > 0 => self.base.levels + i - 1,
211            Table::Exprs => self.base.exprs + i,
212            _ => i,
213        }
214    }
215}
216
217impl<S: Sink> Sink for &mut Shift<'_, S> {
218    type Output = ();
219
220    fn record(&mut self, id: Option<u32>, r: &Record<'_>) -> Result<()> {
221        match r {
222            Record::Meta(_) => Ok(()),
223            Record::End(c) => {
224                self.next = Counts {
225                    names: self.base.names + c.names - 1,
226                    levels: self.base.levels + c.levels - 1,
227                    exprs: self.base.exprs + c.exprs,
228                };
229                Ok(())
230            }
231            r => {
232                let mut r = r.clone();
233                r.map_ids(&|t, i| self.id(t, i));
234                let id = match (id, r.table()) {
235                    (Some(i), Some(t)) => Some(self.id(t, i)),
236                    (id, _) => id,
237                };
238                match &r {
239                    Record::NameStr { pre, str } => self.name(*pre, 0, str.as_bytes()),
240                    Record::NameNum { pre, i } => self.name(*pre, 1, &i.to_le_bytes()),
241                    Record::Decl(d) => {
242                        let n = d.name().and_then(|n| self.names.get(n as usize));
243                        if n.is_some_and(|&n| !self.declared.insert(n)) {
244                            return Ok(());
245                        }
246                    }
247                    _ => {}
248                }
249                self.sink.record(id, &r)
250            }
251        }
252    }
253
254    fn finish(self) -> Result<()> {
255        Ok(())
256    }
257}
258
259/// Join per-module `files` into one export on `sink`, in the order [`order`] gives. Names,
260/// levels and expressions two modules share appear once per module, a declaration two
261/// modules make appears once.
262pub fn join<S: Sink>(files: &[&[u8]], sink: S) -> Result<S::Output> {
263    join_in(files, &order(files)?, None, sink)
264}
265
266/// Join the files [`view`] picks for `root`.
267///
268/// The meta's `view` names the module and how many declarations come before its own. A
269/// checker may take those as given: Lean checks a statement where its module's imports
270/// unfold, not where an importer sees them hidden.
271pub fn join_view<S: Sink>(files: &[&[u8]], root: &str, sink: S) -> Result<S::Output> {
272    join_in(files, &view(files, root)?, Some(root), sink)
273}
274
275fn named(pre: u128, tag: u8, last: &[u8]) -> u128 {
276    let mut b = pre.to_le_bytes().to_vec();
277    b.push(tag);
278    b.extend_from_slice(last);
279    xxh3_128(&b)
280}
281
282/// The name of each declaration in a file, hashed as [`Shift`] does.
283struct Declared {
284    names: Vec<u128>,
285    decls: Vec<Option<u128>>,
286}
287
288impl Sink for Declared {
289    type Output = Vec<Option<u128>>;
290
291    fn record(&mut self, _: Option<u32>, r: &Record<'_>) -> Result<()> {
292        match r {
293            Record::NameStr { pre, str } => {
294                let h = named(self.names[*pre as usize], 0, str.as_bytes());
295                self.names.push(h);
296            }
297            Record::NameNum { pre, i } => {
298                let h = named(self.names[*pre as usize], 1, &i.to_le_bytes());
299                self.names.push(h);
300            }
301            Record::Decl(d) => {
302                let n = d.name().and_then(|n| self.names.get(n as usize));
303                self.decls.push(n.copied());
304            }
305            _ => {}
306        }
307        Ok(())
308    }
309
310    fn finish(self) -> Result<Self::Output> {
311        Ok(self.decls)
312    }
313}
314
315/// How many declarations [`pour`] lets through from `order`.
316fn count(files: &[&[u8]], order: &[usize]) -> Result<u64> {
317    let declared = order
318        .par_iter()
319        .map(|&i| {
320            let names = vec![0];
321            read(
322                files[i],
323                Declared {
324                    names,
325                    decls: Vec::new(),
326                },
327            )
328        })
329        .collect::<Result<Vec<_>>>()?;
330    let mut seen = FxHashSet::default();
331    Ok(declared
332        .iter()
333        .flatten()
334        .filter(|n| n.is_none_or(|n| seen.insert(n)))
335        .count() as u64)
336}
337
338fn read<S: Sink>(bytes: &[u8], sink: S) -> Result<S::Output> {
339    if blean::sniff(bytes) {
340        blean::read(bytes, sink)
341    } else {
342        ndjson::read(bytes, sink)
343    }
344}
345
346fn pour<S: Sink>(files: &[&[u8]], order: &[usize], sink: &mut S) -> Result<Counts> {
347    let mut next = Counts::default();
348    let mut names = vec![0];
349    let mut declared = FxHashSet::default();
350    for &i in order {
351        let mut shift = Shift {
352            sink: &mut *sink,
353            base: next,
354            next,
355            names: &mut names,
356            declared: &mut declared,
357        };
358        read(files[i], &mut shift)?;
359        next = shift.next;
360    }
361    Ok(next)
362}
363
364/// Join `files` in an order [`order`] gave, or one [`view`] gave for `root`.
365pub fn join_in<S: Sink>(
366    files: &[&[u8]],
367    order: &[usize],
368    root: Option<&str>,
369    mut sink: S,
370) -> Result<S::Output> {
371    let Some((_, imports)) = order.split_last() else {
372        return Err(corrupt("nothing to join"));
373    };
374    let mut m = meta(files[order[0]])?;
375    if let Some(o) = m.as_object_mut() {
376        o.remove("module");
377        if let Some(root) = root {
378            let n = count(files, imports)?;
379            o.insert(
380                "view".into(),
381                serde_json::json!({"module": root, "imported": n}),
382            );
383        }
384    }
385    sink.record(None, &Record::Meta(m.to_string().into()))?;
386    let next = pour(files, order, &mut sink)?;
387    sink.record(None, &Record::End(next))?;
388    sink.finish()
389}
390
391/// Hashes what it writes.
392struct Hashing<W> {
393    inner: W,
394    hash: blake3::Hasher,
395}
396
397impl<W: Write> Write for Hashing<W> {
398    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
399        let n = self.inner.write(buf)?;
400        self.hash.update(&buf[..n]);
401        Ok(n)
402    }
403
404    fn flush(&mut self) -> std::io::Result<()> {
405        self.inner.flush()
406    }
407}
408
409type Out = Hashing<BufWriter<File>>;
410
411/// Export every module of `env` to its own file in `dir`, named after the module.
412///
413/// Ids count from the start in each file. A file holds every constant its module declares and
414/// refers to its imports' constants by name, so joining the files gives a whole export,
415/// up to numbering and order, plus the internal constants nothing needs. Returns the files in module order.
416pub fn split(env: &Env, dir: &Path, blean: bool) -> Result<Vec<PathBuf>> {
417    split_each(env, dir, blean, false, &|| {})
418}
419
420/// Like [`split`], with each module written against what the module system shows it and
421/// its interface in `dir/public`.
422pub fn split_interfaces(env: &Env, dir: &Path, blean: bool) -> Result<Vec<PathBuf>> {
423    split_each(env, dir, blean, true, &|| {})
424}
425
426/// [`split`] or [`split_interfaces`], calling `each` after every file written.
427pub fn split_each(
428    env: &Env,
429    dir: &Path,
430    blean: bool,
431    interfaces: bool,
432    each: &dyn Fn(),
433) -> Result<Vec<PathBuf>> {
434    if blean {
435        split_with(env, dir, "blean", interfaces, Blean::new, each)
436    } else {
437        split_with(env, dir, "ndjson", interfaces, Ndjson::new, each)
438    }
439}
440
441fn split_with<S: Sink<Output = Out>>(
442    env: &Env,
443    dir: &Path,
444    ext: &str,
445    interfaces: bool,
446    sink: impl Fn(Out) -> S,
447    each: &dyn Fn(),
448) -> Result<Vec<PathBuf>> {
449    let public = dir.join("public");
450    std::fs::create_dir_all(if interfaces { &public } else { dir })?;
451    let paths: Vec<PathBuf> = env
452        .modules
453        .iter()
454        .map(|m| dir.join(format!("{m}.{ext}")))
455        .collect();
456    let files: Vec<(usize, bool, PathBuf)> = (0..paths.len())
457        .flat_map(|m| {
458            let shown = (interfaces && env.exported[m].is_some())
459                .then(|| (m, true, public.join(format!("{}.{ext}", env.modules[m]))));
460            shown.into_iter().chain([(m, false, paths[m].clone())])
461        })
462        .collect();
463    let open = |p: &Path| -> Result<S> {
464        Ok(sink(Hashing {
465            inner: BufWriter::with_capacity(1 << 20, File::create(p)?),
466            hash: blake3::Hasher::new(),
467        }))
468    };
469    let Some((_, _, first)) = files.first() else {
470        return Ok(paths);
471    };
472    let index: FxHashMap<&str, usize> = env
473        .modules
474        .iter()
475        .enumerate()
476        .map(|(i, m)| (m.as_str(), i))
477        .collect();
478    let mut whole: Vec<String> = Vec::with_capacity(paths.len());
479    let mut shown: Vec<Option<String>> = vec![None; paths.len()];
480    let mut ex = if interfaces {
481        Exporter::restricted(env, open(first)?)
482    } else {
483        Exporter::per_module(env, open(first)?)
484    };
485    for (k, (m, interface, _)) in files.iter().enumerate() {
486        let (m, name) = (*m, &env.modules[*m]);
487        let module = interfaces && env.exported[m].is_some();
488        let imports = env.imports[m]
489            .iter()
490            .filter(|i| !interface || i.exported)
491            .map(|i| {
492                let j = (index.get(i.module.as_str()).copied())
493                    .filter(|&j| j < whole.len())
494                    .ok_or_else(|| corrupt(format!("{name} imports unloaded {}", i.module)))?;
495                let seen = shown[j]
496                    .as_ref()
497                    .filter(|_| module && (*interface || !i.all));
498                Ok(serde_json::json!({
499                    "name": i.module,
500                    "blake3": seen.unwrap_or(&whole[j]),
501                    "all": i.all,
502                    "public": i.exported,
503                    "meta": i.meta,
504                }))
505            })
506            .collect::<Result<Vec<_>>>()?;
507        let mut meta = serde_json::json!({"name": name, "imports": imports});
508        if *interface {
509            meta["public"] = true.into();
510            meta["inside"] = ex.inside(m).map(|o| env.modules[o].as_str()).collect();
511            ex.meta_with(Some(meta))?;
512            ex.interface(m)?;
513        } else {
514            if let Some(h) = &shown[m] {
515                meta["interface"] = h.as_str().into();
516            }
517            ex.meta_with(Some(meta))?;
518            ex.module(m)?;
519        }
520        each();
521        let Some((_, _, next)) = files.get(k + 1) else {
522            break;
523        };
524        let mut out = ex.split(open(next)?)?;
525        out.flush()?;
526        let h = out.hash.finalize().to_hex().to_string();
527        if *interface {
528            shown[m] = Some(h);
529        } else {
530            whole.push(h);
531        }
532    }
533    ex.finish()?.flush()?;
534    Ok(paths)
535}