1use 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#[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
99struct 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 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 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 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
331fn 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#[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
373pub 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}