Skip to main content

olean_export/
key.rs

1//! Declaration keys, shared by external checkers.
2//!
3//! A unit is one declaration, or one inductive block, and its key is the blake3 hash of a
4//! canonical encoding of the unit that names every constant it mentions from an earlier
5//! unit by that unit's key. So a key covers its unit's whole dependency closure, and does
6//! not depend on id numbering, record order or which file a unit came from.
7
8use 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/// A declaration and the key of its unit, `None` when the unit has none.
18#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct Keyed {
20    pub name: String,
21    pub key: Option<Key>,
22    /// Position in its unit.
23    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/// Children are resolved through `MData`, names and levels are canonical.
74#[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/// A [`Sink`] that computes the key of every declaration in an export.
89#[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    /// Every id the declaration refers to is in range, so encoding can index freely.
245    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    /// Every declaration seen so far with its key, in export order.
325    #[must_use]
326    pub fn into_keys(self) -> Vec<Keyed> {
327        self.out
328    }
329}
330
331/// Little-endian bytes of a decimal numeral, `[0]` for zero, as `BigUint::to_bytes_le`.
332fn 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
355/// The encoding of one unit. `None` stands for a unit without a key.
356struct 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}