Skip to main content

olean_export/
info.rs

1//! Facts about each expression that kernels otherwise compute on import.
2
3use crate::{
4    error::{corrupt, Result},
5    record::{Binding, Record},
6};
7use serde::{Deserialize, Serialize};
8use xxhash_rust::xxh3::xxh3_64;
9
10/// Written after every expression record in a blean file.
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Serialize, Deserialize)]
12pub struct Info {
13    /// Structural hash, blind to binder names and binder info as expression identity is.
14    #[serde(with = "postcard::fixint::le")]
15    pub hash: u64,
16    /// One more than the largest de Bruijn index that escapes the term, or 0 if it is closed.
17    pub loose_bvar_range: u32,
18    /// [`Info::LEVEL_PARAM`] and [`Info::FVAR`].
19    pub flags: u8,
20}
21
22impl Info {
23    pub const LEVEL_PARAM: u8 = 1;
24    /// Never set by exporters, since declarations are closed; kept for kernels that share the
25    /// layout with their own terms.
26    pub const FVAR: u8 = 2;
27
28    #[must_use]
29    pub const fn has_level_param(self) -> bool {
30        self.flags & Self::LEVEL_PARAM != 0
31    }
32}
33
34/// Computes [`Info`] for a record stream, from the info of the records each one refers to.
35#[derive(Debug, Default)]
36pub struct Tracker {
37    names: Vec<u64>,
38    levels: Vec<(u64, bool)>,
39    exprs: Vec<Info>,
40    buf: Vec<u8>,
41}
42
43/// `xxh3_64(tag ++ parts)`: the hash of every node, with child hashes and integers
44/// little-endian and strings as their UTF-8 bytes.
45fn hash(buf: &mut Vec<u8>, tag: u8, parts: impl FnOnce(&mut Vec<u8>)) -> u64 {
46    buf.clear();
47    buf.push(tag);
48    parts(buf);
49    xxh3_64(buf)
50}
51
52fn put(buf: &mut Vec<u8>, x: u64) {
53    buf.extend_from_slice(&x.to_le_bytes());
54}
55
56impl Tracker {
57    #[must_use]
58    pub fn new() -> Self {
59        let mut buf = Vec::new();
60        Self {
61            names: vec![hash(&mut buf, 0, |_| {})],
62            levels: vec![(hash(&mut buf, 3, |_| {}), false)],
63            exprs: Vec::new(),
64            buf,
65        }
66    }
67
68    fn name(&self, id: u32) -> Result<u64> {
69        get(&self.names, id).copied()
70    }
71
72    fn level(&self, id: u32) -> Result<(u64, bool)> {
73        get(&self.levels, id).copied()
74    }
75
76    fn expr(&self, id: u32) -> Result<Info> {
77        get(&self.exprs, id).copied()
78    }
79
80    /// Take in the next record, returning its info if it is an expression.
81    pub fn observe(&mut self, r: &Record<'_>) -> Result<Option<Info>> {
82        let buf = &mut self.buf;
83        match r {
84            Record::NameStr { pre, str } => {
85                let p = get(&self.names, *pre)?;
86                let h = hash(buf, 1, |b| {
87                    put(b, *p);
88                    b.extend_from_slice(str.as_bytes());
89                });
90                self.names.push(h);
91            }
92            Record::NameNum { pre, i } => {
93                let p = get(&self.names, *pre)?;
94                let h = hash(buf, 2, |b| {
95                    put(b, *p);
96                    put(b, *i);
97                });
98                self.names.push(h);
99            }
100            Record::Succ(a) => {
101                let (a, p) = self.level(*a)?;
102                let h = hash(&mut self.buf, 4, |b| put(b, a));
103                self.levels.push((h, p));
104            }
105            Record::Max(a, b) | Record::IMax(a, b) => {
106                let ((a, pa), (b, pb)) = (self.level(*a)?, self.level(*b)?);
107                let tag = if matches!(r, Record::Max(..)) { 5 } else { 6 };
108                let h = hash(&mut self.buf, tag, |x| {
109                    put(x, a);
110                    put(x, b);
111                });
112                self.levels.push((h, pa || pb));
113            }
114            Record::Param(n) => {
115                let n = self.name(*n)?;
116                let h = hash(&mut self.buf, 7, |b| put(b, n));
117                self.levels.push((h, true));
118            }
119            Record::Meta(_) | Record::Decl(_) | Record::End(_) => {}
120            _ => {
121                let info = self.expr_info(r)?;
122                self.exprs.push(info);
123                return Ok(Some(info));
124            }
125        }
126        Ok(None)
127    }
128
129    fn expr_info(&mut self, r: &Record<'_>) -> Result<Info> {
130        let lp = |b: bool| if b { Info::LEVEL_PARAM } else { 0 };
131        let node = |this: &mut Self, tag: u8, kids: &[Info], extra: &[u64], lbr: u32| {
132            let h = hash(&mut this.buf, tag, |b| {
133                for k in kids {
134                    put(b, k.hash);
135                }
136                for &x in extra {
137                    put(b, x);
138                }
139            });
140            Info {
141                hash: h,
142                loose_bvar_range: lbr,
143                flags: kids.iter().fold(0, |f, k| f | k.flags),
144            }
145        };
146        let binder = |this: &mut Self, tag: u8, b: &Binding| -> Result<Info> {
147            let (t, body) = (this.expr(b.ty)?, this.expr(b.body)?);
148            let lbr = t
149                .loose_bvar_range
150                .max(body.loose_bvar_range.saturating_sub(1));
151            Ok(node(this, tag, &[t, body], &[], lbr))
152        };
153        Ok(match r {
154            Record::BVar(i) => {
155                let i = u32::try_from(*i)
156                    .ok()
157                    .and_then(|i| i.checked_add(1))
158                    .ok_or_else(|| corrupt("bound variable index too large"))?;
159                Info {
160                    hash: hash(&mut self.buf, 8, |b| put(b, u64::from(i - 1))),
161                    loose_bvar_range: i,
162                    flags: 0,
163                }
164            }
165            Record::Sort(l) => {
166                let (l, p) = self.level(*l)?;
167                Info {
168                    hash: hash(&mut self.buf, 9, |b| put(b, l)),
169                    loose_bvar_range: 0,
170                    flags: lp(p),
171                }
172            }
173            Record::Const { name, us } => {
174                let n = self.name(*name)?;
175                let us = us
176                    .iter()
177                    .map(|&u| self.level(u))
178                    .collect::<Result<Vec<_>>>()?;
179                Info {
180                    hash: hash(&mut self.buf, 10, |b| {
181                        put(b, n);
182                        for &(u, _) in &us {
183                            put(b, u);
184                        }
185                    }),
186                    loose_bvar_range: 0,
187                    flags: lp(us.iter().any(|u| u.1)),
188                }
189            }
190            Record::App { fun, arg } => {
191                let (f, a) = (self.expr(*fun)?, self.expr(*arg)?);
192                let lbr = f.loose_bvar_range.max(a.loose_bvar_range);
193                node(self, 11, &[f, a], &[], lbr)
194            }
195            Record::Lam(b) => binder(self, 12, b)?,
196            Record::Pi(b) => binder(self, 13, b)?,
197            Record::Let {
198                ty, value, body, ..
199            } => {
200                let (t, v, b) = (self.expr(*ty)?, self.expr(*value)?, self.expr(*body)?);
201                let lbr = t
202                    .loose_bvar_range
203                    .max(v.loose_bvar_range)
204                    .max(b.loose_bvar_range.saturating_sub(1));
205                node(self, 14, &[t, v, b], &[], lbr)
206            }
207            Record::Nat(v) | Record::Str(v) => {
208                let tag = if matches!(r, Record::Nat(_)) { 15 } else { 16 };
209                Info {
210                    hash: hash(&mut self.buf, tag, |b| b.extend_from_slice(v.as_bytes())),
211                    ..Info::default()
212                }
213            }
214            Record::Proj {
215                type_name,
216                idx,
217                struct_,
218            } => {
219                let (n, x) = (self.name(*type_name)?, self.expr(*struct_)?);
220                let lbr = x.loose_bvar_range;
221                node(self, 17, &[x], &[n, *idx], lbr)
222            }
223            Record::MData(x) => self.expr(*x)?,
224            Record::Meta(_)
225            | Record::NameStr { .. }
226            | Record::NameNum { .. }
227            | Record::Succ(_)
228            | Record::Max(..)
229            | Record::IMax(..)
230            | Record::Param(_)
231            | Record::Decl(_)
232            | Record::End(_) => unreachable!("not an expression"),
233        })
234    }
235}
236
237fn get<T>(table: &[T], id: u32) -> Result<&T> {
238    table
239        .get(id as usize)
240        .ok_or_else(|| corrupt(format!("reference to undefined id {id}")))
241}