1use crate::{
9 env::Hints,
10 error::{corrupt, Result},
11 record::{Decl, Head, Record, Safety, Sink, Table},
12};
13use rustc_hash::FxHashMap;
14
15pub type Key = [u8; 32];
16
17#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct Keyed {
20 pub name: String,
21 pub key: Option<Key>,
22 pub offset: u32,
24}
25
26mod tag {
27 pub(super) const ANON: u8 = 0;
28 pub(super) const STR: u8 = 1;
29 pub(super) const NUM: u8 = 2;
30 pub(super) const ZERO: u8 = 3;
31 pub(super) const SUCC: u8 = 4;
32 pub(super) const MAX: u8 = 5;
33 pub(super) const IMAX: u8 = 6;
34 pub(super) const PARAM: u8 = 7;
35 pub(super) const VAR: u8 = 8;
36 pub(super) const SORT: u8 = 9;
37 pub(super) const CONST: u8 = 10;
38 pub(super) const APP: u8 = 11;
39 pub(super) const LAM: u8 = 12;
40 pub(super) const PI: u8 = 13;
41 pub(super) const LET: u8 = 14;
42 pub(super) const PROJ: u8 = 15;
43 pub(super) const NAT: u8 = 16;
44 pub(super) const STRLIT: u8 = 17;
45 pub(super) const OWN: u8 = 18;
46 pub(super) const DEP: u8 = 19;
47 pub(super) const AXIOM: u8 = 20;
48 pub(super) const QUOT: u8 = 21;
49 pub(super) const THM: u8 = 22;
50 pub(super) const DEF: u8 = 23;
51 pub(super) const OPAQUE: u8 = 24;
52 pub(super) const IND: u8 = 25;
53 pub(super) const CTOR: u8 = 26;
54 pub(super) const REC: u8 = 27;
55}
56
57#[derive(Debug, Clone, PartialEq, Eq, Hash)]
58enum Name {
59 Anon,
60 Str(u32, Box<str>),
61 Num(u32, u64),
62}
63
64#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
65enum Level {
66 Zero,
67 Succ(u32),
68 Max(u32, u32),
69 IMax(u32, u32),
70 Param(u32),
71}
72
73#[derive(Debug)]
75enum Expr {
76 Var(u64),
77 Sort(u32),
78 Const(u32, Box<[u32]>),
79 App(u32, u32),
80 Lam(u32, u32),
81 Pi(u32, u32),
82 Let(u32, u32, u32, bool),
83 Proj(u32, u64, u32),
84 Nat(Box<[u8]>),
85 Str(Box<str>),
86}
87
88#[derive(Debug)]
90pub struct Keys {
91 names: Vec<Name>,
92 name_ids: FxHashMap<Name, u32>,
93 name_of: Vec<u32>,
94 levels: Vec<Level>,
95 level_ids: FxHashMap<Level, u32>,
96 level_of: Vec<u32>,
97 exprs: Vec<Expr>,
98 expr_of: Vec<u32>,
99 decls: FxHashMap<u32, (Option<Key>, u32)>,
100 out: Vec<Keyed>,
101}
102
103impl Default for Keys {
104 fn default() -> Self {
105 let mut k = Self {
106 names: Vec::new(),
107 name_ids: FxHashMap::default(),
108 name_of: Vec::new(),
109 levels: Vec::new(),
110 level_ids: FxHashMap::default(),
111 level_of: Vec::new(),
112 exprs: Vec::new(),
113 expr_of: Vec::new(),
114 decls: FxHashMap::default(),
115 out: Vec::new(),
116 };
117 let anon = k.name(Name::Anon);
118 let zero = k.level(Level::Zero);
119 k.name_of.push(anon);
120 k.level_of.push(zero);
121 k
122 }
123}
124
125impl Keys {
126 #[must_use]
127 pub fn new() -> Self {
128 Self::default()
129 }
130
131 fn name(&mut self, n: Name) -> u32 {
132 if let Some(&i) = self.name_ids.get(&n) {
133 return i;
134 }
135 let i = u32::try_from(self.names.len()).expect("name count");
136 self.names.push(n.clone());
137 self.name_ids.insert(n, i);
138 i
139 }
140
141 fn level(&mut self, l: Level) -> u32 {
142 if let Some(&i) = self.level_ids.get(&l) {
143 return i;
144 }
145 let i = u32::try_from(self.levels.len()).expect("level count");
146 self.levels.push(l);
147 self.level_ids.insert(l, i);
148 i
149 }
150
151 fn n(&self, i: u32) -> Result<u32> {
152 self.name_of
153 .get(i as usize)
154 .copied()
155 .ok_or_else(|| corrupt("keys: unknown name id"))
156 }
157
158 fn l(&self, i: u32) -> Result<u32> {
159 self.level_of
160 .get(i as usize)
161 .copied()
162 .ok_or_else(|| corrupt("keys: unknown level id"))
163 }
164
165 fn e(&self, i: u32) -> Result<u32> {
166 self.expr_of
167 .get(i as usize)
168 .copied()
169 .ok_or_else(|| corrupt("keys: unknown expression id"))
170 }
171
172 fn dotted(&self, n: u32) -> String {
173 let (pre, last) = match &self.names[n as usize] {
174 Name::Anon => return String::new(),
175 Name::Str(p, s) => (*p, s.to_string()),
176 Name::Num(p, i) => (*p, i.to_string()),
177 };
178 match &self.names[pre as usize] {
179 Name::Anon => last,
180 _ => format!("{}.{last}", self.dotted(pre)),
181 }
182 }
183
184 fn push_expr(&mut self, x: Expr) {
185 let i = u32::try_from(self.exprs.len()).expect("expression count");
186 self.exprs.push(x);
187 self.expr_of.push(i);
188 }
189
190 fn take(&mut self, r: &Record<'_>) -> Result<()> {
191 match r {
192 Record::Meta(_) | Record::End(_) => {}
193 Record::NameStr { pre, str } => {
194 let n = Name::Str(self.n(*pre)?, str.as_ref().into());
195 let i = self.name(n);
196 self.name_of.push(i);
197 }
198 Record::NameNum { pre, i } => {
199 let n = Name::Num(self.n(*pre)?, *i);
200 let i = self.name(n);
201 self.name_of.push(i);
202 }
203 Record::Succ(a) => self.add_level(Level::Succ(self.l(*a)?)),
204 Record::Max(a, b) => self.add_level(Level::Max(self.l(*a)?, self.l(*b)?)),
205 Record::IMax(a, b) => self.add_level(Level::IMax(self.l(*a)?, self.l(*b)?)),
206 Record::Param(n) => self.add_level(Level::Param(self.n(*n)?)),
207 Record::BVar(i) => self.push_expr(Expr::Var(*i)),
208 Record::Sort(l) => self.push_expr(Expr::Sort(self.l(*l)?)),
209 Record::Const { name, us } => {
210 let us = us.iter().map(|&u| self.l(u)).collect::<Result<_>>()?;
211 self.push_expr(Expr::Const(self.n(*name)?, us));
212 }
213 Record::App { fun, arg } => self.push_expr(Expr::App(self.e(*fun)?, self.e(*arg)?)),
214 Record::Lam(b) => self.push_expr(Expr::Lam(self.e(b.ty)?, self.e(b.body)?)),
215 Record::Pi(b) => self.push_expr(Expr::Pi(self.e(b.ty)?, self.e(b.body)?)),
216 Record::Let {
217 ty,
218 value,
219 body,
220 nondep,
221 ..
222 } => self.push_expr(Expr::Let(
223 self.e(*ty)?,
224 self.e(*value)?,
225 self.e(*body)?,
226 *nondep,
227 )),
228 Record::Nat(d) => self.push_expr(Expr::Nat(nat_le(d)?.into())),
229 Record::Str(s) => self.push_expr(Expr::Str(s.as_ref().into())),
230 Record::Proj {
231 type_name,
232 idx,
233 struct_,
234 } => self.push_expr(Expr::Proj(self.n(*type_name)?, *idx, self.e(*struct_)?)),
235 Record::MData(x) => {
236 let x = self.e(*x)?;
237 self.expr_of.push(x);
238 }
239 Record::Decl(d) => self.unit(d)?,
240 }
241 Ok(())
242 }
243
244 fn check(&self, d: &Decl) -> Result<()> {
246 let ok = std::cell::Cell::new(true);
247 Record::Decl(d.clone()).map_ids(&|t, i| {
248 let n = match t {
249 Table::Names => self.name_of.len(),
250 Table::Levels => self.level_of.len(),
251 Table::Exprs => self.expr_of.len(),
252 };
253 ok.set(ok.get() && (i as usize) < n);
254 i
255 });
256 if ok.get() {
257 Ok(())
258 } else {
259 Err(corrupt("keys: declaration refers to an unknown id"))
260 }
261 }
262
263 fn add_level(&mut self, l: Level) {
264 let i = self.level(l);
265 self.level_of.push(i);
266 }
267
268 fn unit(&mut self, d: &Decl) -> Result<()> {
269 let members: Vec<&Head> = match d {
270 Decl::Axiom { head, .. }
271 | Decl::Def { head, .. }
272 | Decl::Thm { head, .. }
273 | Decl::Opaque { head, .. }
274 | Decl::Quot { head, .. } => vec![head],
275 Decl::Inductive { types, ctors, recs } => types
276 .iter()
277 .map(|t| &t.head)
278 .chain(ctors.iter().map(|c| &c.head))
279 .chain(recs.iter().map(|r| &r.head))
280 .collect(),
281 };
282 let names = members
283 .iter()
284 .map(|h| self.n(h.name))
285 .collect::<Result<Vec<_>>>()?;
286 self.check(d)?;
287 for h in &members {
288 for &p in &h.level_params {
289 let p = self.name_of[p as usize];
290 self.level(Level::Param(p));
291 }
292 }
293 let key = Enc::new(self, &names).unit(d);
294 for (offset, &n) in (0..).zip(&names) {
295 if self.decls.insert(n, (key, offset)).is_some() {
296 return Err(corrupt(format!(
297 "keys: duplicate declaration {}",
298 self.dotted(n)
299 )));
300 }
301 self.out.push(Keyed {
302 name: self.dotted(n),
303 key,
304 offset,
305 });
306 }
307 Ok(())
308 }
309}
310
311impl Sink for &mut Keys {
312 type Output = ();
313
314 fn record(&mut self, _: Option<u32>, r: &Record<'_>) -> Result<()> {
315 self.take(r)
316 }
317
318 fn finish(self) -> Result<()> {
319 Ok(())
320 }
321}
322
323impl Keys {
324 #[must_use]
326 pub fn into_keys(self) -> Vec<Keyed> {
327 self.out
328 }
329}
330
331fn nat_le(digits: &str) -> Result<Vec<u8>> {
333 let mut v = vec![0u8];
334 for c in digits.bytes() {
335 if !c.is_ascii_digit() {
336 return Err(corrupt("keys: invalid natural literal"));
337 }
338 let mut carry = u32::from(c - b'0');
339 for b in &mut v {
340 let x = u32::from(*b) * 10 + carry;
341 *b = x.to_le_bytes()[0];
342 carry = x >> 8;
343 }
344 while carry > 0 {
345 v.push(carry.to_le_bytes()[0]);
346 carry >>= 8;
347 }
348 }
349 while v.len() > 1 && v.last() == Some(&0) {
350 v.pop();
351 }
352 Ok(v)
353}
354
355struct Enc<'k> {
357 k: &'k Keys,
358 own: &'k [u32],
359 buf: Vec<u8>,
360 names: FxHashMap<u32, u32>,
361 levels: FxHashMap<u32, u32>,
362 exprs: FxHashMap<u32, u32>,
363 next: u32,
364}
365
366impl<'k> Enc<'k> {
367 fn new(k: &'k Keys, own: &'k [u32]) -> Self {
368 Self {
369 k,
370 own,
371 buf: Vec::new(),
372 names: FxHashMap::default(),
373 levels: FxHashMap::default(),
374 exprs: FxHashMap::default(),
375 next: 0,
376 }
377 }
378
379 fn u64(&mut self, mut x: u64) {
380 while x >= 0x80 {
381 self.buf.push(x.to_le_bytes()[0] | 0x80);
382 x >>= 7;
383 }
384 self.buf.push(x.to_le_bytes()[0]);
385 }
386
387 fn bytes(&mut self, b: &[u8]) {
388 self.u64(b.len() as u64);
389 self.buf.extend_from_slice(b);
390 }
391
392 fn record(&mut self, t: u8, args: &[u64]) {
393 self.buf.push(t);
394 for &a in args {
395 self.u64(a);
396 }
397 }
398
399 fn name(&mut self, n: u32) -> u64 {
400 if let Some(&i) = self.names.get(&n) {
401 return i.into();
402 }
403 match &self.k.names[n as usize] {
404 Name::Anon => self.buf.push(tag::ANON),
405 Name::Str(p, s) => {
406 let p = self.name(*p);
407 self.record(tag::STR, &[p]);
408 self.bytes(s.as_bytes());
409 }
410 Name::Num(p, i) => {
411 let p = self.name(*p);
412 self.record(tag::NUM, &[p]);
413 self.buf.extend_from_slice(&i.to_le_bytes());
414 }
415 }
416 let i = u32::try_from(self.names.len()).expect("name count");
417 self.names.insert(n, i);
418 i.into()
419 }
420
421 fn level(&mut self, l: u32) -> u64 {
422 if let Some(&i) = self.levels.get(&l) {
423 return i.into();
424 }
425 match self.k.levels[l as usize] {
426 Level::Zero => self.record(tag::ZERO, &[]),
427 Level::Succ(x) => {
428 let x = self.level(x);
429 self.record(tag::SUCC, &[x]);
430 }
431 Level::Max(x, y) => {
432 let [x, y] = [self.level(x), self.level(y)];
433 self.record(tag::MAX, &[x, y]);
434 }
435 Level::IMax(x, y) => {
436 let [x, y] = [self.level(x), self.level(y)];
437 self.record(tag::IMAX, &[x, y]);
438 }
439 Level::Param(n) => {
440 let n = self.name(n);
441 self.record(tag::PARAM, &[n]);
442 }
443 }
444 let i = u32::try_from(self.levels.len()).expect("level count");
445 self.levels.insert(l, i);
446 i.into()
447 }
448
449 fn konst(&mut self, n: u32) -> Option<()> {
450 if let Some(off) = self.own.iter().position(|&o| o == n) {
451 self.record(tag::OWN, &[off as u64]);
452 } else {
453 let &(key, off) = self.k.decls.get(&n)?;
454 self.buf.push(tag::DEP);
455 self.buf.extend_from_slice(&key?);
456 self.u64(off.into());
457 }
458 Some(())
459 }
460
461 fn konsts(&mut self, ns: &[u32]) -> Option<()> {
462 self.u64(ns.len() as u64);
463 ns.iter()
464 .try_for_each(|&n| self.konst(self.k.name_of[n as usize]))
465 }
466
467 fn next(&mut self) -> u64 {
468 self.next += 1;
469 (self.next - 1).into()
470 }
471
472 fn expr(&mut self, e: u32) -> Option<u64> {
473 let k = self.k;
474 if let Expr::Var(i) = k.exprs[e as usize] {
475 self.record(tag::VAR, &[i]);
476 return Some(self.next());
477 }
478 if let Some(&i) = self.exprs.get(&e) {
479 return Some(i.into());
480 }
481 match &k.exprs[e as usize] {
482 Expr::Var(_) => unreachable!(),
483 Expr::Sort(l) => {
484 let l = self.level(*l);
485 self.record(tag::SORT, &[l]);
486 }
487 Expr::Const(n, us) => {
488 let ls: Vec<u64> = us.iter().map(|&u| self.level(u)).collect();
489 self.record(tag::CONST, &[ls.len() as u64]);
490 for &l in &ls {
491 self.u64(l);
492 }
493 self.konst(*n)?;
494 }
495 Expr::App(f, a) => {
496 let [f, a] = [self.expr(*f)?, self.expr(*a)?];
497 self.record(tag::APP, &[f, a]);
498 }
499 Expr::Lam(t, b) | Expr::Pi(t, b) => {
500 let tg = if matches!(k.exprs[e as usize], Expr::Lam(..)) {
501 tag::LAM
502 } else {
503 tag::PI
504 };
505 let [t, b] = [self.expr(*t)?, self.expr(*b)?];
506 self.record(tg, &[t, b]);
507 }
508 Expr::Let(t, v, b, nondep) => {
509 let t = self.expr(*t)?;
510 let v = self.expr(*v)?;
511 let b = self.expr(*b)?;
512 self.record(tag::LET, &[t, v, b, u64::from(*nondep)]);
513 }
514 Expr::Proj(n, idx, x) => {
515 let x = self.expr(*x)?;
516 self.record(tag::PROJ, &[*idx, x]);
517 self.konst(*n)?;
518 }
519 Expr::Nat(b) => {
520 self.buf.push(tag::NAT);
521 self.bytes(b);
522 }
523 Expr::Str(s) => {
524 self.buf.push(tag::STRLIT);
525 self.bytes(s.as_bytes());
526 }
527 }
528 let i = self.next;
529 self.next += 1;
530 self.exprs.insert(e, i);
531 Some(i.into())
532 }
533
534 fn info(&mut self, t: u8, h: &Head) -> Option<()> {
535 let k = self.k;
536 let n = self.name(k.name_of[h.name as usize]);
537 let us: Vec<u64> = h
538 .level_params
539 .iter()
540 .map(|&p| {
541 let p = k.name_of[p as usize];
542 self.level(k.level_ids[&Level::Param(p)])
543 })
544 .collect();
545 let ty = self.expr(k.expr_of[h.ty as usize])?;
546 self.record(t, &[n, ty, us.len() as u64]);
547 for &u in &us {
548 self.u64(u);
549 }
550 Some(())
551 }
552
553 fn value(&mut self, t: u8, h: &Head, v: u32) -> Option<()> {
554 let v = self.expr(self.k.expr_of[v as usize])?;
555 self.info(t, h)?;
556 self.u64(v);
557 Some(())
558 }
559
560 fn unit(mut self, d: &Decl) -> Option<Key> {
561 self.encode(d)?;
562 Some(*blake3::hash(&self.buf).as_bytes())
563 }
564
565 fn encode(&mut self, d: &Decl) -> Option<()> {
566 match d {
567 Decl::Axiom {
568 head, is_unsafe, ..
569 } => {
570 if *is_unsafe {
571 return None;
572 }
573 self.info(tag::AXIOM, head)
574 }
575 Decl::Quot { head, .. } => self.info(tag::QUOT, head),
576 Decl::Thm { head, value, .. } => self.value(tag::THM, head, *value),
577 Decl::Opaque {
578 head,
579 value,
580 is_unsafe,
581 ..
582 } => {
583 if *is_unsafe {
584 return None;
585 }
586 self.value(tag::OPAQUE, head, *value)
587 }
588 Decl::Def {
589 head,
590 value,
591 hints,
592 safety,
593 ..
594 } => {
595 if *safety != Safety::Safe {
596 return None;
597 }
598 self.value(tag::DEF, head, *value)?;
599 let h = match hints {
600 Hints::Opaque => 0,
601 Hints::Abbrev => 1,
602 Hints::Regular(k) => u64::from(*k) + 2,
603 };
604 self.buf.extend_from_slice(&h.to_le_bytes());
605 Some(())
606 }
607 Decl::Inductive { types, ctors, recs } => {
608 let unsafe_ = types.iter().any(|t| t.is_unsafe)
609 || ctors.iter().any(|c| c.is_unsafe)
610 || recs.iter().any(|r| r.is_unsafe);
611 if unsafe_ {
612 return None;
613 }
614 for t in types {
615 self.info(tag::IND, &t.head)?;
616 self.record(
617 tag::IND,
618 &[
619 u64::from(t.is_rec),
620 t.num_nested,
621 u64::from(t.is_reflexive),
622 t.num_params,
623 t.num_indices,
624 ],
625 );
626 self.konsts(&t.all)?;
627 self.konsts(&t.ctors)?;
628 }
629 for c in ctors {
630 self.info(tag::CTOR, &c.head)?;
631 self.record(tag::CTOR, &[c.cidx, c.num_params, c.num_fields]);
632 self.konst(self.k.name_of[c.induct as usize])?;
633 }
634 for r in recs {
635 self.info(tag::REC, &r.head)?;
636 self.record(
637 tag::REC,
638 &[
639 r.num_params,
640 r.num_indices,
641 r.num_motives,
642 r.num_minors,
643 u64::from(r.k),
644 r.rules.len() as u64,
645 ],
646 );
647 self.konsts(&r.all)?;
648 for rule in &r.rules {
649 let rhs = self.expr(self.k.expr_of[rule.rhs as usize])?;
650 self.record(tag::REC, &[rule.nfields, rhs]);
651 self.konst(self.k.name_of[rule.ctor as usize])?;
652 }
653 }
654 Some(())
655 }
656 }
657 }
658}