ktrs_parser/builder/
chameleon_cache.rs

1//! [`ChameleonCache`]: expanded lazy nodes (`BLOCK`, `LAMBDA_EXPRESSION`, `DOC_COMMENT`, ...) keyed
2//! by kind and text, for re-parsing text that is mostly unchanged (the formatter parses each file
3//! about three times, and most bodies survive import sorting and trailing-comma edits verbatim).
4//!
5//! Exact: a chameleon's subtree depends only on its kind and text (see `LazyLeaf`), and each entry
6//! is a standalone [`Tree`] spliced in with rebased indices. Only error-free subtrees are kept, so a
7//! hit never has to replay error messages.
8
9use std::collections::HashMap;
10
11use ktrs_syntax::{SyntaxKind, Tree};
12
13#[derive(Default)]
14pub struct ChameleonCache {
15    /// The entry's own text is its key; the hash only picks the bucket.
16    subtrees: HashMap<u64, Vec<Tree>>,
17}
18
19impl ChameleonCache {
20    pub fn new() -> ChameleonCache {
21        ChameleonCache::default()
22    }
23
24    pub(super) fn get(&self, kind: SyntaxKind, text: &str) -> Option<&Tree> {
25        let bucket = self.subtrees.get(&hash(kind, text))?;
26        bucket.iter().find(|t| t.kind(Tree::ROOT) == kind && t.text() == text)
27    }
28
29    pub(super) fn insert(&mut self, subtree: Tree) {
30        let key = hash(subtree.kind(Tree::ROOT), subtree.text());
31        self.subtrees.entry(key).or_default().push(subtree);
32    }
33}
34
35/// FxHash-style multiply-rotate over 8-byte words.
36fn hash(kind: SyntaxKind, text: &str) -> u64 {
37    let mut h = kind as u64;
38    let mut mix = |word: u64| h = (h.rotate_left(5) ^ word).wrapping_mul(0x517c_c1b7_2722_0a95);
39    let (words, rest) = text.as_bytes().as_chunks::<8>();
40    for &word in words {
41        mix(u64::from_le_bytes(word));
42    }
43    let mut tail = [0u8; 8];
44    tail[..rest.len()].copy_from_slice(rest);
45    mix(u64::from_le_bytes(tail) ^ (text.len() as u64) << 56);
46    h ^ h >> 29
47}
ktrs_parser/builder/chameleon_cache.rs

ktrs_parser/builder/
chameleon_cache.rs
