php_ast/
fingerprint.rs

1//! Position-independent fingerprints of AST nodes.
2//!
3//! [`structural_fingerprint`] hashes a node's full structure — kinds, names,
4//! literals, operators, doc comments — while ignoring every [`Span`]. Two
5//! nodes that differ only in where they sit in the file (an edit above a
6//! function shifts every offset inside it) get the same fingerprint.
7//!
8//! This is meant for incremental tools such as salsa-based analyzers: store
9//! the fingerprint next to a declaration's subtree and compare fingerprints
10//! instead of nodes, so a declaration whose code did not change compares equal
11//! after unrelated edits and its downstream results can be reused. Results
12//! derived from such a node must not carry its absolute positions; keep them
13//! relative to the declaration and add its current start when reporting.
14//!
15//! It works on anything that implements [`serde::Serialize`], so both the
16//! arena and the owned AST are supported.
17//!
18//! ```
19//! use php_ast::fingerprint::structural_fingerprint;
20//! use php_ast::owned::{Expr, ExprKind};
21//! use php_ast::Span;
22//!
23//! let var = |name: &str, start: u32| Expr {
24//!     kind: ExprKind::Variable(name.into()),
25//!     span: Span::new(start, start + 1 + name.len() as u32),
26//! };
27//! // Same variable at two positions: equal fingerprints.
28//! assert_eq!(structural_fingerprint(&var("x", 10)), structural_fingerprint(&var("x", 90)));
29//! // A different variable: different fingerprints.
30//! assert_ne!(structural_fingerprint(&var("x", 10)), structural_fingerprint(&var("y", 10)));
31//! ```
32//!
33//! [`Span`]: crate::Span
34
35use std::collections::hash_map::DefaultHasher;
36use std::fmt;
37use std::hash::Hasher;
38
39use serde::ser::{self, Serialize};
40
41/// A 64-bit hash of `node`'s structure that ignores every [`Span`](crate::Span).
42///
43/// Equal nodes always produce equal fingerprints; two different nodes collide
44/// with probability around 2^-64, ample for comparing a node with its previous
45/// version. The value is deterministic within one build but not guaranteed to
46/// be stable across versions of this crate or of Rust, so use it for in-memory
47/// comparison rather than persisting it.
48pub fn structural_fingerprint<T: Serialize + ?Sized>(node: &T) -> u64 {
49    let mut fingerprinter = Fingerprinter(DefaultHasher::new());
50    // The serializer itself never fails; a custom `Serialize` impl could, in
51    // which case the fingerprint covers everything up to that point.
52    let _ = node.serialize(&mut fingerprinter);
53    fingerprinter.0.finish()
54}
55
56/// Struct and field names are not hashed: a value's Rust type already fixes
57/// which struct sits at each position, and enum variants are told apart by
58/// their index.
59struct Fingerprinter(DefaultHasher);
60
61/// Tags written before each value so that different shapes cannot produce the
62/// same byte stream.
63#[repr(u8)]
64enum Tag {
65    Bool,
66    Int,
67    Float,
68    Char,
69    Str,
70    Bytes,
71    None,
72    Some,
73    Unit,
74    UnitStruct,
75    UnitVariant,
76    NewtypeStruct,
77    NewtypeVariant,
78    Seq,
79    Tuple,
80    TupleStruct,
81    TupleVariant,
82    Map,
83    Struct,
84    StructVariant,
85    Field,
86    End,
87}
88
89impl Fingerprinter {
90    fn tag(&mut self, tag: Tag) {
91        self.0.write_u8(tag as u8);
92    }
93
94    fn u64(&mut self, value: u64) {
95        self.0.write_u64(value);
96    }
97
98    fn bytes(&mut self, bytes: &[u8]) {
99        self.u64(bytes.len() as u64);
100        self.0.write(bytes);
101    }
102}
103
104/// The serializer never fails on its own; this only satisfies the trait.
105#[derive(Debug)]
106struct FingerprintError(String);
107
108impl fmt::Display for FingerprintError {
109    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
110        f.write_str(&self.0)
111    }
112}
113
114impl std::error::Error for FingerprintError {}
115
116impl ser::Error for FingerprintError {
117    fn custom<T: fmt::Display>(msg: T) -> Self {
118        Self(msg.to_string())
119    }
120}
121
122/// Struct serializer that skips the contents of a `Span`.
123struct StructFingerprinter<'a> {
124    fingerprinter: Option<&'a mut Fingerprinter>,
125}
126
127impl<'a> ser::Serializer for &'a mut Fingerprinter {
128    type Ok = ();
129    type Error = FingerprintError;
130    type SerializeSeq = Self;
131    type SerializeTuple = Self;
132    type SerializeTupleStruct = Self;
133    type SerializeTupleVariant = Self;
134    type SerializeMap = Self;
135    type SerializeStruct = StructFingerprinter<'a>;
136    type SerializeStructVariant = Self;
137
138    fn serialize_bool(self, v: bool) -> Result<(), FingerprintError> {
139        self.tag(Tag::Bool);
140        self.u64(u64::from(v));
141        Ok(())
142    }
143
144    fn serialize_i8(self, v: i8) -> Result<(), FingerprintError> {
145        self.serialize_i64(i64::from(v))
146    }
147
148    fn serialize_i16(self, v: i16) -> Result<(), FingerprintError> {
149        self.serialize_i64(i64::from(v))
150    }
151
152    fn serialize_i32(self, v: i32) -> Result<(), FingerprintError> {
153        self.serialize_i64(i64::from(v))
154    }
155
156    fn serialize_i64(self, v: i64) -> Result<(), FingerprintError> {
157        self.tag(Tag::Int);
158        self.u64(v as u64);
159        Ok(())
160    }
161
162    fn serialize_u8(self, v: u8) -> Result<(), FingerprintError> {
163        self.serialize_u64(u64::from(v))
164    }
165
166    fn serialize_u16(self, v: u16) -> Result<(), FingerprintError> {
167        self.serialize_u64(u64::from(v))
168    }
169
170    fn serialize_u32(self, v: u32) -> Result<(), FingerprintError> {
171        self.serialize_u64(u64::from(v))
172    }
173
174    fn serialize_u64(self, v: u64) -> Result<(), FingerprintError> {
175        self.tag(Tag::Int);
176        self.u64(v);
177        Ok(())
178    }
179
180    fn serialize_f32(self, v: f32) -> Result<(), FingerprintError> {
181        self.serialize_f64(f64::from(v))
182    }
183
184    fn serialize_f64(self, v: f64) -> Result<(), FingerprintError> {
185        self.tag(Tag::Float);
186        self.u64(v.to_bits());
187        Ok(())
188    }
189
190    fn serialize_char(self, v: char) -> Result<(), FingerprintError> {
191        self.tag(Tag::Char);
192        self.u64(u64::from(v));
193        Ok(())
194    }
195
196    fn serialize_str(self, v: &str) -> Result<(), FingerprintError> {
197        self.tag(Tag::Str);
198        self.bytes(v.as_bytes());
199        Ok(())
200    }
201
202    fn serialize_bytes(self, v: &[u8]) -> Result<(), FingerprintError> {
203        self.tag(Tag::Bytes);
204        self.bytes(v);
205        Ok(())
206    }
207
208    fn serialize_none(self) -> Result<(), FingerprintError> {
209        self.tag(Tag::None);
210        Ok(())
211    }
212
213    fn serialize_some<T: Serialize + ?Sized>(self, value: &T) -> Result<(), FingerprintError> {
214        self.tag(Tag::Some);
215        value.serialize(self)
216    }
217
218    fn serialize_unit(self) -> Result<(), FingerprintError> {
219        self.tag(Tag::Unit);
220        Ok(())
221    }
222
223    fn serialize_unit_struct(self, _name: &'static str) -> Result<(), FingerprintError> {
224        self.tag(Tag::UnitStruct);
225        Ok(())
226    }
227
228    fn serialize_unit_variant(
229        self,
230        _name: &'static str,
231        index: u32,
232        _variant: &'static str,
233    ) -> Result<(), FingerprintError> {
234        self.tag(Tag::UnitVariant);
235        self.u64(u64::from(index));
236        Ok(())
237    }
238
239    fn serialize_newtype_struct<T: Serialize + ?Sized>(
240        self,
241        _name: &'static str,
242        value: &T,
243    ) -> Result<(), FingerprintError> {
244        self.tag(Tag::NewtypeStruct);
245        value.serialize(self)
246    }
247
248    fn serialize_newtype_variant<T: Serialize + ?Sized>(
249        self,
250        _name: &'static str,
251        index: u32,
252        _variant: &'static str,
253        value: &T,
254    ) -> Result<(), FingerprintError> {
255        self.tag(Tag::NewtypeVariant);
256        self.u64(u64::from(index));
257        value.serialize(self)
258    }
259
260    fn serialize_seq(self, _len: Option<usize>) -> Result<Self, FingerprintError> {
261        self.tag(Tag::Seq);
262        Ok(self)
263    }
264
265    fn serialize_tuple(self, _len: usize) -> Result<Self, FingerprintError> {
266        self.tag(Tag::Tuple);
267        Ok(self)
268    }
269
270    fn serialize_tuple_struct(
271        self,
272        _name: &'static str,
273        _len: usize,
274    ) -> Result<Self, FingerprintError> {
275        self.tag(Tag::TupleStruct);
276        Ok(self)
277    }
278
279    fn serialize_tuple_variant(
280        self,
281        _name: &'static str,
282        index: u32,
283        _variant: &'static str,
284        _len: usize,
285    ) -> Result<Self, FingerprintError> {
286        self.tag(Tag::TupleVariant);
287        self.u64(u64::from(index));
288        Ok(self)
289    }
290
291    fn serialize_map(self, _len: Option<usize>) -> Result<Self, FingerprintError> {
292        self.tag(Tag::Map);
293        Ok(self)
294    }
295
296    fn serialize_struct(
297        self,
298        name: &'static str,
299        _len: usize,
300    ) -> Result<StructFingerprinter<'a>, FingerprintError> {
301        if name == "Span" {
302            return Ok(StructFingerprinter {
303                fingerprinter: None,
304            });
305        }
306        self.tag(Tag::Struct);
307        Ok(StructFingerprinter {
308            fingerprinter: Some(self),
309        })
310    }
311
312    fn serialize_struct_variant(
313        self,
314        _name: &'static str,
315        index: u32,
316        _variant: &'static str,
317        _len: usize,
318    ) -> Result<Self, FingerprintError> {
319        self.tag(Tag::StructVariant);
320        self.u64(u64::from(index));
321        Ok(self)
322    }
323}
324
325impl ser::SerializeSeq for &mut Fingerprinter {
326    type Ok = ();
327    type Error = FingerprintError;
328
329    fn serialize_element<T: Serialize + ?Sized>(
330        &mut self,
331        value: &T,
332    ) -> Result<(), FingerprintError> {
333        value.serialize(&mut **self)
334    }
335
336    fn end(self) -> Result<(), FingerprintError> {
337        self.tag(Tag::End);
338        Ok(())
339    }
340}
341
342impl ser::SerializeTuple for &mut Fingerprinter {
343    type Ok = ();
344    type Error = FingerprintError;
345
346    fn serialize_element<T: Serialize + ?Sized>(
347        &mut self,
348        value: &T,
349    ) -> Result<(), FingerprintError> {
350        value.serialize(&mut **self)
351    }
352
353    fn end(self) -> Result<(), FingerprintError> {
354        self.tag(Tag::End);
355        Ok(())
356    }
357}
358
359impl ser::SerializeTupleStruct for &mut Fingerprinter {
360    type Ok = ();
361    type Error = FingerprintError;
362
363    fn serialize_field<T: Serialize + ?Sized>(
364        &mut self,
365        value: &T,
366    ) -> Result<(), FingerprintError> {
367        value.serialize(&mut **self)
368    }
369
370    fn end(self) -> Result<(), FingerprintError> {
371        self.tag(Tag::End);
372        Ok(())
373    }
374}
375
376impl ser::SerializeTupleVariant for &mut Fingerprinter {
377    type Ok = ();
378    type Error = FingerprintError;
379
380    fn serialize_field<T: Serialize + ?Sized>(
381        &mut self,
382        value: &T,
383    ) -> Result<(), FingerprintError> {
384        value.serialize(&mut **self)
385    }
386
387    fn end(self) -> Result<(), FingerprintError> {
388        self.tag(Tag::End);
389        Ok(())
390    }
391}
392
393impl ser::SerializeMap for &mut Fingerprinter {
394    type Ok = ();
395    type Error = FingerprintError;
396
397    fn serialize_key<T: Serialize + ?Sized>(&mut self, key: &T) -> Result<(), FingerprintError> {
398        key.serialize(&mut **self)
399    }
400
401    fn serialize_value<T: Serialize + ?Sized>(
402        &mut self,
403        value: &T,
404    ) -> Result<(), FingerprintError> {
405        value.serialize(&mut **self)
406    }
407
408    fn end(self) -> Result<(), FingerprintError> {
409        self.tag(Tag::End);
410        Ok(())
411    }
412}
413
414impl ser::SerializeStruct for StructFingerprinter<'_> {
415    type Ok = ();
416    type Error = FingerprintError;
417
418    fn serialize_field<T: Serialize + ?Sized>(
419        &mut self,
420        _key: &'static str,
421        value: &T,
422    ) -> Result<(), FingerprintError> {
423        let Some(fingerprinter) = self.fingerprinter.as_deref_mut() else {
424            return Ok(());
425        };
426        fingerprinter.tag(Tag::Field);
427        value.serialize(fingerprinter)
428    }
429
430    fn skip_field(&mut self, _key: &'static str) -> Result<(), FingerprintError> {
431        // A skipped optional field must not look like a present one.
432        if let Some(fingerprinter) = self.fingerprinter.as_deref_mut() {
433            fingerprinter.tag(Tag::None);
434        }
435        Ok(())
436    }
437
438    fn end(self) -> Result<(), FingerprintError> {
439        if let Some(fingerprinter) = self.fingerprinter {
440            fingerprinter.tag(Tag::End);
441        }
442        Ok(())
443    }
444}
445
446impl ser::SerializeStructVariant for &mut Fingerprinter {
447    type Ok = ();
448    type Error = FingerprintError;
449
450    fn serialize_field<T: Serialize + ?Sized>(
451        &mut self,
452        _key: &'static str,
453        value: &T,
454    ) -> Result<(), FingerprintError> {
455        self.tag(Tag::Field);
456        value.serialize(&mut **self)
457    }
458
459    fn end(self) -> Result<(), FingerprintError> {
460        self.tag(Tag::End);
461        Ok(())
462    }
463}
php_ast/fingerprint.rs

php_ast/
fingerprint.rs
