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 if digits.is_empty() || !digits.bytes().all(|c| c.is_ascii_digit()) {
334 return Err(corrupt("keys: invalid natural literal"));
335 }
336 let n: malachite_nz::natural::Natural = digits
338 .parse()
339 .map_err(|()| corrupt("keys: invalid natural literal"))?;
340 let mut v: Vec<u8> = n
341 .to_limbs_asc()
342 .iter()
343 .flat_map(|l| l.to_le_bytes())
344 .collect();
345 while v.len() > 1 && v.last() == Some(&0) {
346 v.pop();
347 }
348 if v.is_empty() {
349 v.push(0);
350 }
351 Ok(v)
352}
353
354struct Enc<'k> {
356 k: &'k Keys,
357 own: &'k [u32],
358 buf: Vec<u8>,
359 names: FxHashMap<u32, u32>,
360 levels: FxHashMap<u32, u32>,
361 exprs: FxHashMap<u32, u32>,
362 next: u32,
363}
364
365impl<'k> Enc<'k> {
366 fn new(k: &'k Keys, own: &'k [u32]) -> Self {
367 Self {
368 k,
369 own,
370 buf: Vec::new(),
371 names: FxHashMap::default(),
372 levels: FxHashMap::default(),
373 exprs: FxHashMap::default(),
374 next: 0,
375 }
376 }
377
378 fn u64(&mut self, mut x: u64) {
379 while x >= 0x80 {
380 self.buf.push(x.to_le_bytes()[0] | 0x80);
381 x >>= 7;
382 }
383 self.buf.push(x.to_le_bytes()[0]);
384 }
385
386 fn bytes(&mut self, b: &[u8]) {
387 self.u64(b.len() as u64);
388 self.buf.extend_from_slice(b);
389 }
390
391 fn record(&mut self, t: u8, args: &[u64]) {
392 self.buf.push(t);
393 for &a in args {
394 self.u64(a);
395 }
396 }
397
398 fn name(&mut self, n: u32) -> u64 {
399 if let Some(&i) = self.names.get(&n) {
400 return i.into();
401 }
402 match &self.k.names[n as usize] {
403 Name::Anon => self.buf.push(tag::ANON),
404 Name::Str(p, s) => {
405 let p = self.name(*p);
406 self.record(tag::STR, &[p]);
407 self.bytes(s.as_bytes());
408 }
409 Name::Num(p, i) => {
410 let p = self.name(*p);
411 self.record(tag::NUM, &[p]);
412 self.buf.extend_from_slice(&i.to_le_bytes());
413 }
414 }
415 let i = u32::try_from(self.names.len()).expect("name count");
416 self.names.insert(n, i);
417 i.into()
418 }
419
420 fn level(&mut self, l: u32) -> u64 {
421 if let Some(&i) = self.levels.get(&l) {
422 return i.into();
423 }
424 match self.k.levels[l as usize] {
425 Level::Zero => self.record(tag::ZERO, &[]),
426 Level::Succ(x) => {
427 let x = self.level(x);
428 self.record(tag::SUCC, &[x]);
429 }
430 Level::Max(x, y) => {
431 let [x, y] = [self.level(x), self.level(y)];
432 self.record(tag::MAX, &[x, y]);
433 }
434 Level::IMax(x, y) => {
435 let [x, y] = [self.level(x), self.level(y)];
436 self.record(tag::IMAX, &[x, y]);
437 }
438 Level::Param(n) => {
439 let n = self.name(n);
440 self.record(tag::PARAM, &[n]);
441 }
442 }
443 let i = u32::try_from(self.levels.len()).expect("level count");
444 self.levels.insert(l, i);
445 i.into()
446 }
447
448 fn konst(&mut self, n: u32) -> Option<()> {
449 if let Some(off) = self.own.iter().position(|&o| o == n) {
450 self.record(tag::OWN, &[off as u64]);
451 } else {
452 let &(key, off) = self.k.decls.get(&n)?;
453 self.buf.push(tag::DEP);
454 self.buf.extend_from_slice(&key?);
455 self.u64(off.into());
456 }
457 Some(())
458 }
459
460 fn konsts(&mut self, ns: &[u32]) -> Option<()> {
461 self.u64(ns.len() as u64);
462 ns.iter()
463 .try_for_each(|&n| self.konst(self.k.name_of[n as usize]))
464 }
465
466 fn next(&mut self) -> u64 {
467 self.next += 1;
468 (self.next - 1).into()
469 }
470
471 fn expr(&mut self, e: u32) -> Option<u64> {
472 let k = self.k;
473 if let Expr::Var(i) = k.exprs[e as usize] {
474 self.record(tag::VAR, &[i]);
475 return Some(self.next());
476 }
477 if let Some(&i) = self.exprs.get(&e) {
478 return Some(i.into());
479 }
480 match &k.exprs[e as usize] {
481 Expr::Var(_) => unreachable!(),
482 Expr::Sort(l) => {
483 let l = self.level(*l);
484 self.record(tag::SORT, &[l]);
485 }
486 Expr::Const(n, us) => {
487 let ls: Vec<u64> = us.iter().map(|&u| self.level(u)).collect();
488 self.record(tag::CONST, &[ls.len() as u64]);
489 for &l in &ls {
490 self.u64(l);
491 }
492 self.konst(*n)?;
493 }
494 Expr::App(f, a) => {
495 let [f, a] = [self.expr(*f)?, self.expr(*a)?];
496 self.record(tag::APP, &[f, a]);
497 }
498 Expr::Lam(t, b) | Expr::Pi(t, b) => {
499 let tg = if matches!(k.exprs[e as usize], Expr::Lam(..)) {
500 tag::LAM
501 } else {
502 tag::PI
503 };
504 let [t, b] = [self.expr(*t)?, self.expr(*b)?];
505 self.record(tg, &[t, b]);
506 }
507 Expr::Let(t, v, b, nondep) => {
508 let t = self.expr(*t)?;
509 let v = self.expr(*v)?;
510 let b = self.expr(*b)?;
511 self.record(tag::LET, &[t, v, b, u64::from(*nondep)]);
512 }
513 Expr::Proj(n, idx, x) => {
514 let x = self.expr(*x)?;
515 self.record(tag::PROJ, &[*idx, x]);
516 self.konst(*n)?;
517 }
518 Expr::Nat(b) => {
519 self.buf.push(tag::NAT);
520 self.bytes(b);
521 }
522 Expr::Str(s) => {
523 self.buf.push(tag::STRLIT);
524 self.bytes(s.as_bytes());
525 }
526 }
527 let i = self.next;
528 self.next += 1;
529 self.exprs.insert(e, i);
530 Some(i.into())
531 }
532
533 fn info(&mut self, t: u8, h: &Head) -> Option<()> {
534 let k = self.k;
535 let n = self.name(k.name_of[h.name as usize]);
536 let us: Vec<u64> = h
537 .level_params
538 .iter()
539 .map(|&p| {
540 let p = k.name_of[p as usize];
541 self.level(k.level_ids[&Level::Param(p)])
542 })
543 .collect();
544 let ty = self.expr(k.expr_of[h.ty as usize])?;
545 self.record(t, &[n, ty, us.len() as u64]);
546 for &u in &us {
547 self.u64(u);
548 }
549 Some(())
550 }
551
552 fn value(&mut self, t: u8, h: &Head, v: u32) -> Option<()> {
553 let v = self.expr(self.k.expr_of[v as usize])?;
554 self.info(t, h)?;
555 self.u64(v);
556 Some(())
557 }
558
559 fn unit(mut self, d: &Decl) -> Option<Key> {
560 self.encode(d)?;
561 Some(*blake3::hash(&self.buf).as_bytes())
562 }
563
564 fn encode(&mut self, d: &Decl) -> Option<()> {
565 match d {
566 Decl::Axiom {
567 head, is_unsafe, ..
568 } => {
569 if *is_unsafe {
570 return None;
571 }
572 self.info(tag::AXIOM, head)
573 }
574 Decl::Quot { head, .. } => self.info(tag::QUOT, head),
575 Decl::Thm { head, value, .. } => self.value(tag::THM, head, *value),
576 Decl::Opaque {
577 head,
578 value,
579 is_unsafe,
580 ..
581 } => {
582 if *is_unsafe {
583 return None;
584 }
585 self.value(tag::OPAQUE, head, *value)
586 }
587 Decl::Def {
588 head,
589 value,
590 hints,
591 safety,
592 ..
593 } => {
594 if *safety != Safety::Safe {
595 return None;
596 }
597 self.value(tag::DEF, head, *value)?;
598 let h = match hints {
599 Hints::Opaque => 0,
600 Hints::Abbrev => 1,
601 Hints::Regular(k) => u64::from(*k) + 2,
602 };
603 self.buf.extend_from_slice(&h.to_le_bytes());
604 Some(())
605 }
606 Decl::Inductive { types, ctors, recs } => {
607 let unsafe_ = types.iter().any(|t| t.is_unsafe)
608 || ctors.iter().any(|c| c.is_unsafe)
609 || recs.iter().any(|r| r.is_unsafe);
610 if unsafe_ {
611 return None;
612 }
613 for t in types {
614 self.info(tag::IND, &t.head)?;
615 self.record(
616 tag::IND,
617 &[
618 u64::from(t.is_rec),
619 t.num_nested,
620 u64::from(t.is_reflexive),
621 t.num_params,
622 t.num_indices,
623 ],
624 );
625 self.konsts(&t.all)?;
626 self.konsts(&t.ctors)?;
627 }
628 for c in ctors {
629 self.info(tag::CTOR, &c.head)?;
630 self.record(tag::CTOR, &[c.cidx, c.num_params, c.num_fields]);
631 self.konst(self.k.name_of[c.induct as usize])?;
632 }
633 for r in recs {
634 self.info(tag::REC, &r.head)?;
635 self.record(
636 tag::REC,
637 &[
638 r.num_params,
639 r.num_indices,
640 r.num_motives,
641 r.num_minors,
642 u64::from(r.k),
643 r.rules.len() as u64,
644 ],
645 );
646 self.konsts(&r.all)?;
647 for rule in &r.rules {
648 let rhs = self.expr(self.k.expr_of[rule.rhs as usize])?;
649 self.record(tag::REC, &[rule.nfields, rhs]);
650 self.konst(self.k.name_of[rule.ctor as usize])?;
651 }
652 }
653 Some(())
654 }
655 }
656 }
657}
658
659#[cfg(test)]
660mod nat_le_tests {
661 use super::nat_le;
662
663 fn schoolbook(digits: &str) -> Vec<u8> {
665 let mut v = vec![0u8];
666 for c in digits.bytes() {
667 let mut carry = u32::from(c - b'0');
668 for b in &mut v {
669 let x = u32::from(*b) * 10 + carry;
670 *b = x.to_le_bytes()[0];
671 carry = x >> 8;
672 }
673 while carry > 0 {
674 v.push(carry.to_le_bytes()[0]);
675 carry >>= 8;
676 }
677 }
678 while v.len() > 1 && v.last() == Some(&0) {
679 v.pop();
680 }
681 v
682 }
683
684 #[test]
685 fn agrees_with_schoolbook() {
686 let long: String = (0..5000_usize)
687 .map(|i| char::from(b"0123456789"[i * 7 % 10]))
688 .collect();
689 for d in [
690 "0",
691 "00",
692 "1",
693 "255",
694 "256",
695 "18446744073709551616",
696 "000123",
697 &long,
698 ] {
699 assert_eq!(nat_le(d).unwrap(), schoolbook(d), "{d}");
700 }
701 assert!(nat_le("").is_err());
702 assert!(nat_le("12a").is_err());
703 }
704}