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    if digits.is_empty() || !digits.bytes().all(|c| c.is_ascii_digit()) {
334        return Err(corrupt("keys: invalid natural literal"));
335    }
336    // divide and conquer (malachite): digit by digit is quadratic on huge literals
337    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
354/// The encoding of one unit. `None` stands for a unit without a key.
355struct 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    /// The conversion this replaces: digit by digit, quadratic.
664    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}