1use crate::{
4 error::{corrupt, Result},
5 record::{Binding, Record},
6};
7use serde::{Deserialize, Serialize};
8use xxhash_rust::xxh3::xxh3_64;
9
10#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Serialize, Deserialize)]
12pub struct Info {
13 #[serde(with = "postcard::fixint::le")]
15 pub hash: u64,
16 pub loose_bvar_range: u32,
18 pub flags: u8,
20}
21
22impl Info {
23 pub const LEVEL_PARAM: u8 = 1;
24 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#[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
43fn 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 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}