Skip to main content

olean_export/
compare.rs

1//! Compare two exports up to id numbering, record order and binders.
2//!
3//! lean4export shares subterms by Lean's `BEq`, which ignores binders, so where two
4//! alpha-equivalent terms meet it may write either's binders. Both streams are hash-consed
5//! into one table, so equal terms get equal ids on either side and a declaration compares
6//! by `==` in time linear in its DAG, never its tree.
7
8use crate::{
9    blean,
10    error::{corrupt, Result},
11    ndjson,
12    record::{Decl, Head, IndCtor, IndRec, IndRule, IndType, Record, Sink, Table},
13};
14use hashbrown::{hash_table::Entry, HashTable};
15use parking_lot::Mutex;
16use rustc_hash::{FxBuildHasher, FxHashMap};
17use std::{cell::Cell, hash::BuildHasher, mem, thread};
18
19#[derive(Debug, Clone, PartialEq, Eq, Hash)]
20enum Key {
21    Anon,
22    Zero,
23    NameStr(u32, Box<str>),
24    NameNum(u32, u64),
25    Succ(u32),
26    Max(u32, u32),
27    IMax(u32, u32),
28    Param(u32),
29    BVar(u64),
30    Sort(u32),
31    Const(u32, Box<[u32]>),
32    App(u32, u32),
33    Lam(u32, u32),
34    Pi(u32, u32),
35    Let(u32, u32, u32, bool),
36    Nat(Box<str>),
37    Str(Box<str>),
38    Proj(u32, u64, u32),
39}
40
41const SHARDS: usize = 256;
42
43#[derive(Debug, Default)]
44struct Shard {
45    nodes: Vec<Key>,
46    index: HashTable<u32>,
47}
48
49/// The shared table, sharded so both streams can intern at once. Node `i` lives in shard
50/// `i % SHARDS`.
51#[derive(Debug)]
52struct Canon(Vec<Mutex<Shard>>);
53
54impl Canon {
55    fn new() -> Self {
56        Self((0..SHARDS).map(|_| Mutex::default()).collect())
57    }
58
59    fn intern(&self, k: Key) -> u32 {
60        let h = FxBuildHasher.hash_one(&k);
61        let s = (h.wrapping_mul(0x9e37_79b9_7f4a_7c15) >> 56) as usize % SHARDS;
62        let mut shard = self.0[s].lock();
63        let Shard { nodes, index } = &mut *shard;
64        let local = match index.entry(
65            h,
66            |&i| nodes[i as usize] == k,
67            |&i| FxBuildHasher.hash_one(&nodes[i as usize]),
68        ) {
69            Entry::Occupied(e) => *e.get(),
70            Entry::Vacant(e) => {
71                let i = u32::try_from(nodes.len()).expect("table overflow");
72                nodes.push(k);
73                e.insert(i);
74                i
75            }
76        };
77        drop(shard);
78        u32::try_from(local as usize * SHARDS + s).expect("table overflow")
79    }
80
81    fn get(&self, n: u32) -> Key {
82        let n = n as usize;
83        self.0[n % SHARDS].lock().nodes[n / SHARDS].clone()
84    }
85
86    fn name(&self, n: u32) -> String {
87        let join = |p: u32, s: &str| match self.get(p) {
88            Key::Anon => s.to_string(),
89            _ => format!("{}.{s}", self.name(p)),
90        };
91        match self.get(n) {
92            Key::NameStr(p, s) => join(p, &s),
93            Key::NameNum(p, i) => join(p, &i.to_string()),
94            _ => String::new(),
95        }
96    }
97}
98
99/// One stream's ids mapped into the shared table, and its declarations by first name.
100struct Side<'c> {
101    canon: &'c Canon,
102    names: Vec<u32>,
103    levels: Vec<u32>,
104    exprs: Vec<u32>,
105    decls: FxHashMap<u32, Decl>,
106    dups: Vec<u32>,
107    count: usize,
108    /// The first reference to an id not yet defined, if any.
109    dangling: Cell<Option<u32>>,
110}
111
112impl<'c> Side<'c> {
113    fn new(canon: &'c Canon) -> Self {
114        let names = vec![canon.intern(Key::Anon)];
115        let levels = vec![canon.intern(Key::Zero)];
116        Self {
117            canon,
118            names,
119            levels,
120            exprs: Vec::new(),
121            decls: FxHashMap::default(),
122            dups: Vec::new(),
123            count: 0,
124            dangling: Cell::new(None),
125        }
126    }
127
128    fn id(&self, table: &[u32], i: u32) -> u32 {
129        table.get(i as usize).copied().unwrap_or_else(|| {
130            self.dangling.set(self.dangling.get().or(Some(i)));
131            0
132        })
133    }
134
135    fn n(&self, i: u32) -> u32 {
136        self.id(&self.names, i)
137    }
138
139    fn ns(&self, is: &[u32]) -> Vec<u32> {
140        is.iter().map(|&i| self.n(i)).collect()
141    }
142
143    fn l(&self, i: u32) -> u32 {
144        self.id(&self.levels, i)
145    }
146
147    fn e(&self, i: u32) -> u32 {
148        self.id(&self.exprs, i)
149    }
150
151    fn head(&self, h: &Head) -> Head {
152        Head {
153            name: self.n(h.name),
154            level_params: self.ns(&h.level_params),
155            ty: self.e(h.ty),
156        }
157    }
158
159    /// `d` over shared ids, with what lean4export may vary dropped: the `all` of axioms
160    /// and opaques, which only some versions write, and the order of a block's recursors.
161    fn decl(&self, d: &Decl) -> Decl {
162        match d {
163            Decl::Axiom {
164                head, is_unsafe, ..
165            } => Decl::Axiom {
166                head: self.head(head),
167                is_unsafe: *is_unsafe,
168                all: None,
169            },
170            Decl::Def {
171                head,
172                value,
173                hints,
174                safety,
175                all,
176            } => Decl::Def {
177                head: self.head(head),
178                value: self.e(*value),
179                hints: *hints,
180                safety: *safety,
181                all: self.ns(all),
182            },
183            Decl::Thm { head, value, all } => Decl::Thm {
184                head: self.head(head),
185                value: self.e(*value),
186                all: self.ns(all),
187            },
188            Decl::Opaque {
189                head,
190                value,
191                is_unsafe,
192                ..
193            } => Decl::Opaque {
194                head: self.head(head),
195                value: self.e(*value),
196                is_unsafe: *is_unsafe,
197                all: None,
198            },
199            Decl::Quot { head, kind } => Decl::Quot {
200                head: self.head(head),
201                kind: *kind,
202            },
203            Decl::Inductive { types, ctors, recs } => {
204                let mut recs: Vec<IndRec> = recs
205                    .iter()
206                    .map(|r| IndRec {
207                        head: self.head(&r.head),
208                        all: self.ns(&r.all),
209                        rules: r
210                            .rules
211                            .iter()
212                            .map(|u| IndRule {
213                                ctor: self.n(u.ctor),
214                                nfields: u.nfields,
215                                rhs: self.e(u.rhs),
216                            })
217                            .collect(),
218                        ..r.clone()
219                    })
220                    .collect();
221                recs.sort_by_key(|r| r.head.name);
222                Decl::Inductive {
223                    types: types
224                        .iter()
225                        .map(|t| IndType {
226                            head: self.head(&t.head),
227                            all: self.ns(&t.all),
228                            ctors: self.ns(&t.ctors),
229                            ..t.clone()
230                        })
231                        .collect(),
232                    ctors: ctors
233                        .iter()
234                        .map(|c| IndCtor {
235                            head: self.head(&c.head),
236                            induct: self.n(c.induct),
237                            ..c.clone()
238                        })
239                        .collect(),
240                    recs,
241                }
242            }
243        }
244    }
245}
246
247impl Side<'_> {
248    fn check(&self) -> Result<()> {
249        self.dangling.get().map_or(Ok(()), |i| {
250            Err(corrupt(format!("reference to undefined id {i}")))
251        })
252    }
253}
254
255impl Sink for &mut Side<'_> {
256    type Output = ();
257
258    fn record(&mut self, _: Option<u32>, r: &Record<'_>) -> Result<()> {
259        let key = match r {
260            Record::Meta(_) | Record::End(_) => return Ok(()),
261            Record::Decl(d) => {
262                let d = self.decl(d);
263                let k = first(&d);
264                self.count += 1;
265                if self.decls.insert(k, d).is_some() {
266                    self.dups.push(k);
267                }
268                return self.check();
269            }
270            Record::NameStr { pre, str } => Key::NameStr(self.n(*pre), (**str).into()),
271            Record::NameNum { pre, i } => Key::NameNum(self.n(*pre), *i),
272            Record::Succ(l) => Key::Succ(self.l(*l)),
273            Record::Max(a, b) => Key::Max(self.l(*a), self.l(*b)),
274            Record::IMax(a, b) => Key::IMax(self.l(*a), self.l(*b)),
275            Record::Param(n) => Key::Param(self.n(*n)),
276            Record::BVar(i) => Key::BVar(*i),
277            Record::Sort(l) => Key::Sort(self.l(*l)),
278            Record::Const { name, us } => {
279                Key::Const(self.n(*name), us.iter().map(|&u| self.l(u)).collect())
280            }
281            Record::App { fun, arg } => Key::App(self.e(*fun), self.e(*arg)),
282            Record::Lam(b) => Key::Lam(self.e(b.ty), self.e(b.body)),
283            Record::Pi(b) => Key::Pi(self.e(b.ty), self.e(b.body)),
284            Record::Let {
285                ty,
286                value,
287                body,
288                nondep,
289                ..
290            } => Key::Let(self.e(*ty), self.e(*value), self.e(*body), *nondep),
291            Record::Nat(s) => Key::Nat((**s).into()),
292            Record::Str(s) => Key::Str((**s).into()),
293            Record::Proj {
294                type_name,
295                idx,
296                struct_,
297            } => Key::Proj(self.n(*type_name), *idx, self.e(*struct_)),
298            // lean4export's kernels read mdata as the term it wraps, and so does the exporter
299            Record::MData(e) => {
300                let id = self.e(*e);
301                self.exprs.push(id);
302                return self.check();
303            }
304        };
305        let table = r.table();
306        let id = self.canon.intern(key);
307        match table {
308            Some(Table::Names) => self.names.push(id),
309            Some(Table::Levels) => self.levels.push(id),
310            _ => self.exprs.push(id),
311        }
312        self.check()
313    }
314
315    fn finish(self) -> Result<()> {
316        Ok(())
317    }
318}
319
320fn first(d: &Decl) -> u32 {
321    match d {
322        Decl::Axiom { head, .. }
323        | Decl::Def { head, .. }
324        | Decl::Thm { head, .. }
325        | Decl::Opaque { head, .. }
326        | Decl::Quot { head, .. } => head.name,
327        Decl::Inductive { types, .. } => types.first().map_or(0, |t| t.head.name),
328    }
329}
330
331/// Which part of two declarations under one name first differs.
332fn what(a: &Decl, b: &Decl) -> &'static str {
333    let parts = |d: &Decl| match d {
334        Decl::Axiom { head, .. } | Decl::Quot { head, .. } => Some((head.clone(), None)),
335        Decl::Def { head, value, .. }
336        | Decl::Thm { head, value, .. }
337        | Decl::Opaque { head, value, .. } => Some((head.clone(), Some(*value))),
338        Decl::Inductive { .. } => None,
339    };
340    if mem::discriminant(a) != mem::discriminant(b) {
341        return "kind";
342    }
343    match (parts(a), parts(b)) {
344        (Some((x, _)), Some((y, _))) if x.level_params != y.level_params => "level params",
345        (Some((x, _)), Some((y, _))) if x.ty != y.ty => "type",
346        (Some((_, v)), Some((_, w))) if v != w => "value",
347        (None, None) => "inductive block",
348        _ => "attributes",
349    }
350}
351
352/// How two exports differ, every list sorted by name.
353#[derive(Debug, Default)]
354pub struct Diff {
355    pub decls: (usize, usize),
356    pub only_a: Vec<String>,
357    pub only_b: Vec<String>,
358    pub differ: Vec<(String, &'static str)>,
359    pub dups: (Vec<String>, Vec<String>),
360}
361
362impl Diff {
363    #[must_use]
364    pub const fn is_empty(&self) -> bool {
365        self.only_a.is_empty()
366            && self.only_b.is_empty()
367            && self.differ.is_empty()
368            && self.dups.0.is_empty()
369            && self.dups.1.is_empty()
370    }
371}
372
373/// Compare two exports, each NDJSON or blean.
374pub fn compare(a: &[u8], b: &[u8]) -> Result<Diff> {
375    fn load(bytes: &[u8], side: &mut Side<'_>) -> Result<()> {
376        if blean::sniff(bytes) {
377            blean::read(bytes, side)
378        } else {
379            ndjson::read(bytes, side)
380        }
381    }
382    let canon = Canon::new();
383    let side = |bytes: &[u8]| {
384        let mut s = Side::new(&canon);
385        load(bytes, &mut s).map(|()| (s.decls, s.count, s.dups))
386    };
387    let (ra, rb) = thread::scope(|t| {
388        let a = t.spawn(|| side(a));
389        let b = side(b);
390        (a.join().expect("compare thread panicked"), b)
391    });
392    let ((da, ca, pa), (db, cb, pb)) = (ra?, rb?);
393    let names = |ks: &mut dyn Iterator<Item = u32>| {
394        let mut v: Vec<String> = ks.map(|k| canon.name(k)).collect();
395        v.sort_unstable();
396        v
397    };
398    let mut differ: Vec<_> = da
399        .iter()
400        .filter_map(|(k, x)| {
401            let y = db.get(k)?;
402            (x != y).then(|| (canon.name(*k), what(x, y)))
403        })
404        .collect();
405    differ.sort_unstable();
406    Ok(Diff {
407        decls: (ca, cb),
408        only_a: names(&mut da.keys().copied().filter(|k| !db.contains_key(k))),
409        only_b: names(&mut db.keys().copied().filter(|k| !da.contains_key(k))),
410        differ,
411        dups: (names(&mut pa.into_iter()), names(&mut pb.into_iter())),
412    })
413}