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 rustc_hash::{FxHashMap, FxHashSet};
11use serde_json::Value;
12use std::{
13    fs::File,
14    io::{BufWriter, Write},
15    path::{Path, PathBuf},
16};
17use xxhash_rust::xxh3::xxh3_128;
18
19/// The `meta` object of an NDJSON or blean export, read from its first record.
20pub fn meta(bytes: &[u8]) -> Result<Value> {
21    let json = if blean::sniff(bytes) {
22        match blean::entries(bytes)?.next() {
23            Some(Ok((Record::Meta(m), _))) => m.into_owned(),
24            Some(Err(e)) => return Err(e),
25            _ => return Err(corrupt("export does not start with meta")),
26        }
27    } else {
28        let line = bytes.split(|&b| b == b'\n').next().unwrap_or_default();
29        let v: Value = serde_json::from_slice(line)?;
30        v.get("meta")
31            .ok_or_else(|| corrupt("export does not start with meta"))?
32            .to_string()
33    };
34    Ok(serde_json::from_str(&json)?)
35}
36
37/// A per-module file's module name and its imports with their blake3 hashes.
38fn module(meta: &Value) -> Result<(String, Vec<(String, String)>)> {
39    let m = meta
40        .get("module")
41        .ok_or_else(|| corrupt("not a per-module export"))?;
42    let s = |v: &Value| v.as_str().map(str::to_owned);
43    let bad = || corrupt("bad module in meta");
44    let name = m.get("name").and_then(s).ok_or_else(bad)?;
45    let imports = m
46        .get("imports")
47        .and_then(Value::as_array)
48        .ok_or_else(bad)?
49        .iter()
50        .map(|i| Some((s(i.get("name")?)?, s(i.get("blake3")?)?)))
51        .collect::<Option<_>>()
52        .ok_or_else(bad)?;
53    Ok((name, imports))
54}
55
56/// Hex blake3 of an export's bytes, as per-module metas name their imports.
57#[must_use]
58pub fn hash(bytes: &[u8]) -> String {
59    blake3::hash(bytes).to_hex().to_string()
60}
61
62/// The order to join per-module `files` in, imports first. Fails unless every import of
63/// every file is among them with the hash it was exported against.
64pub fn order(files: &[&[u8]]) -> Result<Vec<usize>> {
65    let mods = files
66        .iter()
67        .map(|b| module(&meta(b)?))
68        .collect::<Result<Vec<_>>>()?;
69    let mut by_name = FxHashMap::default();
70    for (i, (n, _)) in mods.iter().enumerate() {
71        if by_name.insert(n.as_str(), i).is_some() {
72            return Err(corrupt(format!("module {n} given twice")));
73        }
74    }
75    let hashes: Vec<String> = files.iter().map(|b| hash(b)).collect();
76    let mut deps = Vec::with_capacity(files.len());
77    for (n, imports) in &mods {
78        let mut d = Vec::new();
79        for (i, h) in imports {
80            let &j = by_name
81                .get(i.as_str())
82                .ok_or_else(|| corrupt(format!("{n} imports {i}, which is not given")))?;
83            if hashes[j] != *h {
84                return Err(corrupt(format!("{n} was exported against another {i}")));
85            }
86            d.push(j);
87        }
88        deps.push(d);
89    }
90    let mut out = Vec::with_capacity(files.len());
91    let mut state = vec![0u8; files.len()];
92    for root in 0..files.len() {
93        let mut stack = vec![(root, 0)];
94        while let Some((i, k)) = stack.pop() {
95            if k == 0 {
96                match state[i] {
97                    2 => continue,
98                    1 => return Err(corrupt(format!("import cycle at {}", mods[i].0))),
99                    _ => state[i] = 1,
100                }
101            }
102            if let Some(&j) = deps[i].get(k) {
103                stack.push((i, k + 1));
104                if state[j] != 2 {
105                    stack.push((j, 0));
106                }
107            } else {
108                state[i] = 2;
109                out.push(i);
110            }
111        }
112    }
113    Ok(out)
114}
115
116/// Shifts one file's ids past the files before it, and drops declarations an earlier file
117/// already made.
118struct Shift<'s, S> {
119    sink: &'s mut S,
120    base: Counts,
121    next: Counts,
122    names: &'s mut Vec<u128>,
123    declared: &'s mut FxHashSet<u128>,
124}
125
126impl<S: Sink> Shift<'_, S> {
127    fn name(&mut self, pre: u32, tag: u8, last: &[u8]) {
128        let mut b = self.names[pre as usize].to_le_bytes().to_vec();
129        b.push(tag);
130        b.extend_from_slice(last);
131        self.names.push(xxh3_128(&b));
132    }
133
134    const fn id(&self, t: Table, i: u32) -> u32 {
135        match t {
136            Table::Names if i > 0 => self.base.names + i - 1,
137            Table::Levels if i > 0 => self.base.levels + i - 1,
138            Table::Exprs => self.base.exprs + i,
139            _ => i,
140        }
141    }
142}
143
144impl<S: Sink> Sink for &mut Shift<'_, S> {
145    type Output = ();
146
147    fn record(&mut self, id: Option<u32>, r: &Record<'_>) -> Result<()> {
148        match r {
149            Record::Meta(_) => Ok(()),
150            Record::End(c) => {
151                self.next = Counts {
152                    names: self.base.names + c.names - 1,
153                    levels: self.base.levels + c.levels - 1,
154                    exprs: self.base.exprs + c.exprs,
155                };
156                Ok(())
157            }
158            r => {
159                let mut r = r.clone();
160                r.map_ids(&|t, i| self.id(t, i));
161                let id = match (id, r.table()) {
162                    (Some(i), Some(t)) => Some(self.id(t, i)),
163                    (id, _) => id,
164                };
165                match &r {
166                    Record::NameStr { pre, str } => self.name(*pre, 0, str.as_bytes()),
167                    Record::NameNum { pre, i } => self.name(*pre, 1, &i.to_le_bytes()),
168                    Record::Decl(d) => {
169                        let n = d.name().and_then(|n| self.names.get(n as usize));
170                        if n.is_some_and(|&n| !self.declared.insert(n)) {
171                            return Ok(());
172                        }
173                    }
174                    _ => {}
175                }
176                self.sink.record(id, &r)
177            }
178        }
179    }
180
181    fn finish(self) -> Result<()> {
182        Ok(())
183    }
184}
185
186/// Join per-module `files` into one export on `sink`, in the order [`order`] gives. Names,
187/// levels and expressions two modules share appear once per module, a declaration two
188/// modules make appears once.
189pub fn join<S: Sink>(files: &[&[u8]], mut sink: S) -> Result<S::Output> {
190    let order = order(files)?;
191    let Some(&first) = order.first() else {
192        return Err(corrupt("nothing to join"));
193    };
194    let mut m = meta(files[first])?;
195    if let Some(o) = m.as_object_mut() {
196        o.remove("module");
197    }
198    sink.record(None, &Record::Meta(m.to_string().into()))?;
199    let mut next = Counts::default();
200    let mut names = vec![0];
201    let mut declared = FxHashSet::default();
202    for i in order {
203        let mut shift = Shift {
204            sink: &mut sink,
205            base: next,
206            next,
207            names: &mut names,
208            declared: &mut declared,
209        };
210        let bytes = files[i];
211        if blean::sniff(bytes) {
212            blean::read(bytes, &mut shift)?;
213        } else {
214            ndjson::read(bytes, &mut shift)?;
215        }
216        next = shift.next;
217    }
218    sink.record(None, &Record::End(next))?;
219    sink.finish()
220}
221
222/// Hashes what it writes.
223struct Hashing<W> {
224    inner: W,
225    hash: blake3::Hasher,
226}
227
228impl<W: Write> Write for Hashing<W> {
229    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
230        let n = self.inner.write(buf)?;
231        self.hash.update(&buf[..n]);
232        Ok(n)
233    }
234
235    fn flush(&mut self) -> std::io::Result<()> {
236        self.inner.flush()
237    }
238}
239
240type Out = Hashing<BufWriter<File>>;
241
242/// Export every module of `env` to its own file in `dir`, named after the module.
243///
244/// Ids count from the start in each file. A file holds every constant its module declares and
245/// refers to its imports' constants by name, so joining the files gives a whole export,
246/// up to numbering and order, plus the internal constants nothing needs. Returns the files in module order.
247pub fn split(env: &Env, dir: &Path, blean: bool) -> Result<Vec<PathBuf>> {
248    if blean {
249        split_with(env, dir, "blean", Blean::new)
250    } else {
251        split_with(env, dir, "ndjson", Ndjson::new)
252    }
253}
254
255fn split_with<S: Sink<Output = Out>>(
256    env: &Env,
257    dir: &Path,
258    ext: &str,
259    sink: impl Fn(Out) -> S,
260) -> Result<Vec<PathBuf>> {
261    std::fs::create_dir_all(dir)?;
262    let paths: Vec<PathBuf> = env
263        .modules
264        .iter()
265        .map(|m| dir.join(format!("{m}.{ext}")))
266        .collect();
267    let open = |p: &Path| -> Result<S> {
268        Ok(sink(Hashing {
269            inner: BufWriter::with_capacity(1 << 20, File::create(p)?),
270            hash: blake3::Hasher::new(),
271        }))
272    };
273    let Some(first) = paths.first() else {
274        return Ok(paths);
275    };
276    let index: FxHashMap<&str, usize> = env
277        .modules
278        .iter()
279        .enumerate()
280        .map(|(i, m)| (m.as_str(), i))
281        .collect();
282    let mut hashes: Vec<String> = Vec::with_capacity(paths.len());
283    let mut ex = Exporter::per_module(env, open(first)?);
284    for m in 0..paths.len() {
285        let imports = env.imports[m]
286            .iter()
287            .map(|i| {
288                let h = index
289                    .get(i.as_str())
290                    .and_then(|&j| hashes.get(j))
291                    .ok_or_else(|| corrupt(format!("{} imports unloaded {i}", env.modules[m])))?;
292                Ok(serde_json::json!({"name": i, "blake3": h}))
293            })
294            .collect::<Result<Vec<_>>>()?;
295        ex.meta_with(Some(
296            serde_json::json!({"name": env.modules[m], "imports": imports}),
297        ))?;
298        ex.module(m)?;
299        if m + 1 == paths.len() {
300            break;
301        }
302        let mut out = ex.split(open(&paths[m + 1])?)?;
303        out.flush()?;
304        hashes.push(out.hash.finalize().to_hex().to_string());
305    }
306    ex.finish()?.flush()?;
307    Ok(paths)
308}