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