1use 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#[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
100struct 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 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 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 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
332fn 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#[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
374pub 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}