harn_parser/
analysis.rs

1use std::collections::{HashMap, HashSet};
2use std::hash::{Hash, Hasher};
3use std::path::Path;
4
5use harn_lexer::{Lexer, LexerError, Token};
6
7use crate::InlayHintInfo;
8use crate::{Parser, ParserError, SNode, TypeChecker, TypeDiagnostic};
9
10/// Stable source identity used by the incremental analysis cache.
11#[derive(Debug, Clone, PartialEq, Eq, Hash)]
12pub struct SourceId(String);
13
14impl SourceId {
15    pub fn new(value: impl Into<String>) -> Self {
16        Self(value.into())
17    }
18
19    pub fn path(path: &Path) -> Self {
20        Self(path.to_string_lossy().into_owned())
21    }
22
23    pub fn as_str(&self) -> &str {
24        &self.0
25    }
26}
27
28/// Monotonic caller-owned version for a source input.
29#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
30pub struct SourceVersion(pub u64);
31
32/// Deterministic content digest for a source input.
33#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
34pub struct SourceDigest(u64);
35
36impl SourceDigest {
37    pub fn from_source(source: &str) -> Self {
38        let mut hash = 0xcbf29ce484222325u64;
39        for byte in source.as_bytes() {
40            hash ^= u64::from(*byte);
41            hash = hash.wrapping_mul(0x100000001b3);
42        }
43        Self(hash)
44    }
45}
46
47#[derive(Debug, Clone, Copy, PartialEq, Eq)]
48pub enum SourceUpdate {
49    Inserted,
50    Changed,
51    Unchanged,
52}
53
54#[derive(Debug, Clone, Default, PartialEq, Eq)]
55pub struct AnalysisStats {
56    pub lex_runs: usize,
57    pub parse_runs: usize,
58    pub typecheck_runs: usize,
59}
60
61#[derive(Debug, Clone)]
62pub struct ParseOutput {
63    pub source: String,
64    pub program: Vec<SNode>,
65}
66
67#[derive(Debug, Clone)]
68pub struct TypeCheckOutput {
69    pub source: String,
70    pub program: Vec<SNode>,
71    pub diagnostics: Vec<TypeDiagnostic>,
72    pub inlay_hints: Vec<InlayHintInfo>,
73}
74
75#[derive(Debug, Clone)]
76pub enum AnalysisError {
77    MissingSource(SourceId),
78    Lex {
79        source: String,
80        error: LexerError,
81    },
82    Parse {
83        source: String,
84        errors: Vec<ParserError>,
85    },
86}
87
88impl AnalysisError {
89    pub fn source(&self) -> Option<&str> {
90        match self {
91            AnalysisError::MissingSource(_) => None,
92            AnalysisError::Lex { source, .. } | AnalysisError::Parse { source, .. } => Some(source),
93        }
94    }
95}
96
97#[derive(Debug, Clone, Default)]
98pub struct TypeCheckConfig {
99    pub strict_types: bool,
100    pub imported_names: Option<HashSet<String>>,
101    pub imported_type_decls: Vec<SNode>,
102    pub imported_callable_decls: Vec<SNode>,
103    pub namespace_imports: Vec<(String, crate::NamespaceImportBinding)>,
104}
105
106impl TypeCheckConfig {
107    pub fn new() -> Self {
108        Self::default()
109    }
110
111    pub fn with_strict_types(mut self, strict_types: bool) -> Self {
112        self.strict_types = strict_types;
113        self
114    }
115
116    pub fn with_imported_names(mut self, imported_names: Option<HashSet<String>>) -> Self {
117        self.imported_names = imported_names;
118        self
119    }
120
121    pub fn with_imported_type_decls(mut self, imported_type_decls: Vec<SNode>) -> Self {
122        self.imported_type_decls = imported_type_decls;
123        self
124    }
125
126    pub fn with_imported_callable_decls(mut self, imported_callable_decls: Vec<SNode>) -> Self {
127        self.imported_callable_decls = imported_callable_decls;
128        self
129    }
130
131    pub fn with_namespace_imports(
132        mut self,
133        namespace_imports: Vec<(String, crate::NamespaceImportBinding)>,
134    ) -> Self {
135        self.namespace_imports = namespace_imports;
136        self
137    }
138
139    fn cache_key(&self) -> TypeCheckCacheKey {
140        let mut imported_names = self
141            .imported_names
142            .as_ref()
143            .map(|names| names.iter().cloned().collect::<Vec<_>>());
144        if let Some(names) = &mut imported_names {
145            names.sort();
146        }
147        let mut namespace_aliases: Vec<String> = self
148            .namespace_imports
149            .iter()
150            .map(|(alias, _)| alias.clone())
151            .collect();
152        namespace_aliases.sort();
153        TypeCheckCacheKey {
154            strict_types: self.strict_types,
155            imported_names,
156            imported_type_decls_digest: debug_digest(&self.imported_type_decls),
157            imported_callable_decls_digest: debug_digest(&self.imported_callable_decls),
158            namespace_imports_digest: debug_digest(&namespace_aliases),
159        }
160    }
161
162    fn build_checker(&self) -> TypeChecker {
163        let mut checker = TypeChecker::with_strict_types(self.strict_types);
164        if let Some(imported) = self.imported_names.clone() {
165            checker = checker.with_imported_names(imported);
166        }
167        if !self.imported_type_decls.is_empty() {
168            checker = checker.with_imported_type_decls(self.imported_type_decls.clone());
169        }
170        if !self.imported_callable_decls.is_empty() {
171            checker = checker.with_imported_callable_decls(self.imported_callable_decls.clone());
172        }
173        if !self.namespace_imports.is_empty() {
174            checker = checker.with_namespace_imports(self.namespace_imports.clone());
175        }
176        checker
177    }
178}
179
180#[derive(Debug, Clone, PartialEq, Eq, Hash)]
181struct TypeCheckCacheKey {
182    strict_types: bool,
183    imported_names: Option<Vec<String>>,
184    imported_type_decls_digest: u64,
185    imported_callable_decls_digest: u64,
186    namespace_imports_digest: u64,
187}
188
189#[derive(Debug, Clone)]
190struct CachedTypeCheck {
191    diagnostics: Vec<TypeDiagnostic>,
192    inlay_hints: Vec<InlayHintInfo>,
193}
194
195#[derive(Debug, Clone)]
196struct SourceEntry {
197    source: String,
198    version: SourceVersion,
199    digest: SourceDigest,
200    tokens: Option<Result<Vec<Token>, LexerError>>,
201    program: Option<Result<Vec<SNode>, Vec<ParserError>>>,
202    typechecks: HashMap<TypeCheckCacheKey, CachedTypeCheck>,
203}
204
205impl SourceEntry {
206    fn new(source: String, version: SourceVersion, digest: SourceDigest) -> Self {
207        Self {
208            source,
209            version,
210            digest,
211            tokens: None,
212            program: None,
213            typechecks: HashMap::new(),
214        }
215    }
216
217    fn replace_source(&mut self, source: String, version: SourceVersion, digest: SourceDigest) {
218        self.source = source;
219        self.version = version;
220        self.digest = digest;
221        self.tokens = None;
222        self.program = None;
223        self.typechecks.clear();
224    }
225}
226
227/// Persistent query cache for lexing, parsing, and type checking Harn sources.
228#[derive(Debug, Default)]
229pub struct AnalysisDatabase {
230    entries: HashMap<SourceId, SourceEntry>,
231    stats: AnalysisStats,
232}
233
234impl AnalysisDatabase {
235    pub fn new() -> Self {
236        Self::default()
237    }
238
239    pub fn stats(&self) -> AnalysisStats {
240        self.stats.clone()
241    }
242
243    pub fn set_source(
244        &mut self,
245        id: SourceId,
246        source: String,
247        version: SourceVersion,
248    ) -> SourceUpdate {
249        let digest = SourceDigest::from_source(&source);
250        match self.entries.get_mut(&id) {
251            None => {
252                self.entries
253                    .insert(id, SourceEntry::new(source, version, digest));
254                SourceUpdate::Inserted
255            }
256            Some(entry) if entry.digest == digest => {
257                entry.version = version;
258                SourceUpdate::Unchanged
259            }
260            Some(entry) => {
261                entry.replace_source(source, version, digest);
262                SourceUpdate::Changed
263            }
264        }
265    }
266
267    pub fn set_parsed_source(
268        &mut self,
269        id: SourceId,
270        source: String,
271        version: SourceVersion,
272        program: Vec<SNode>,
273    ) -> SourceUpdate {
274        let digest = SourceDigest::from_source(&source);
275        match self.entries.get_mut(&id) {
276            None => {
277                let mut entry = SourceEntry::new(source, version, digest);
278                entry.program = Some(Ok(program));
279                self.entries.insert(id, entry);
280                SourceUpdate::Inserted
281            }
282            Some(entry) if entry.digest == digest => {
283                entry.version = version;
284                entry.program = Some(Ok(program));
285                SourceUpdate::Unchanged
286            }
287            Some(entry) => {
288                entry.replace_source(source, version, digest);
289                entry.program = Some(Ok(program));
290                SourceUpdate::Changed
291            }
292        }
293    }
294
295    pub fn parse(&mut self, id: &SourceId) -> Result<ParseOutput, AnalysisError> {
296        if let Some(entry) = self.entries.get(id) {
297            if let Some(program) = &entry.program {
298                return match program {
299                    Ok(program) => Ok(ParseOutput {
300                        source: entry.source.clone(),
301                        program: program.clone(),
302                    }),
303                    Err(errors) => Err(AnalysisError::Parse {
304                        source: entry.source.clone(),
305                        errors: errors.clone(),
306                    }),
307                };
308            }
309        }
310
311        let mut lexed = false;
312        let mut parsed_now = false;
313        let entry = self.entry_mut(id)?;
314        if entry.tokens.is_none() {
315            lexed = true;
316            let mut lexer = Lexer::new(&entry.source);
317            entry.tokens = Some(lexer.tokenize());
318        }
319        let tokens = match entry.tokens.as_ref().expect("tokens initialized") {
320            Ok(tokens) => tokens.clone(),
321            Err(error) => {
322                let source = entry.source.clone();
323                let error = error.clone();
324                if lexed {
325                    self.stats.lex_runs += 1;
326                }
327                return Err(AnalysisError::Lex { source, error });
328            }
329        };
330
331        if entry.program.is_none() {
332            parsed_now = true;
333            let mut parser = Parser::new(tokens);
334            entry.program = Some(match parser.parse() {
335                Ok(program) => Ok(program),
336                Err(error) => {
337                    let mut errors = parser.all_errors().to_vec();
338                    if errors.is_empty() {
339                        errors.push(error);
340                    }
341                    Err(errors)
342                }
343            });
344        }
345
346        let result = match entry.program.as_ref().expect("program initialized") {
347            Ok(program) => Ok(ParseOutput {
348                source: entry.source.clone(),
349                program: program.clone(),
350            }),
351            Err(errors) => Err(AnalysisError::Parse {
352                source: entry.source.clone(),
353                errors: errors.clone(),
354            }),
355        };
356        if lexed {
357            self.stats.lex_runs += 1;
358        }
359        if parsed_now {
360            self.stats.parse_runs += 1;
361        }
362        result
363    }
364
365    pub fn typecheck(
366        &mut self,
367        id: &SourceId,
368        config: TypeCheckConfig,
369    ) -> Result<TypeCheckOutput, AnalysisError> {
370        let parsed = self.parse(id)?;
371        let key = config.cache_key();
372        if let Some(cached) = self
373            .entries
374            .get(id)
375            .expect("parse verified source entry")
376            .typechecks
377            .get(&key)
378        {
379            return Ok(TypeCheckOutput {
380                source: parsed.source,
381                program: parsed.program,
382                diagnostics: cached.diagnostics.clone(),
383                inlay_hints: cached.inlay_hints.clone(),
384            });
385        }
386
387        self.stats.typecheck_runs += 1;
388        let (diagnostics, inlay_hints) = config
389            .build_checker()
390            .check_with_hints(&parsed.program, &parsed.source);
391        let cached = CachedTypeCheck {
392            diagnostics: diagnostics.clone(),
393            inlay_hints: inlay_hints.clone(),
394        };
395        self.entries
396            .get_mut(id)
397            .expect("parse verified source entry")
398            .typechecks
399            .insert(key, cached);
400        Ok(TypeCheckOutput {
401            source: parsed.source,
402            program: parsed.program,
403            diagnostics,
404            inlay_hints,
405        })
406    }
407
408    fn entry_mut(&mut self, id: &SourceId) -> Result<&mut SourceEntry, AnalysisError> {
409        self.entries
410            .get_mut(id)
411            .ok_or_else(|| AnalysisError::MissingSource(id.clone()))
412    }
413}
414
415fn debug_digest<T: std::fmt::Debug>(value: &T) -> u64 {
416    let mut hasher = StableHasher::default();
417    format!("{value:?}").hash(&mut hasher);
418    hasher.finish()
419}
420
421#[derive(Default)]
422struct StableHasher(u64);
423
424impl Hasher for StableHasher {
425    fn finish(&self) -> u64 {
426        self.0
427    }
428
429    fn write(&mut self, bytes: &[u8]) {
430        let mut hash = if self.0 == 0 {
431            0xcbf29ce484222325u64
432        } else {
433            self.0
434        };
435        for byte in bytes {
436            hash ^= u64::from(*byte);
437            hash = hash.wrapping_mul(0x100000001b3);
438        }
439        self.0 = hash;
440    }
441}
442
443#[cfg(test)]
444mod tests {
445    use super::*;
446    use crate::DiagnosticSeverity;
447
448    fn source_id() -> SourceId {
449        SourceId::new("test.harn")
450    }
451
452    #[test]
453    fn parse_reuses_cached_program_for_unchanged_source() {
454        let mut db = AnalysisDatabase::new();
455        let id = source_id();
456        assert_eq!(
457            db.set_source(id.clone(), "const x = 1\n".to_string(), SourceVersion(1)),
458            SourceUpdate::Inserted
459        );
460        db.parse(&id).expect("initial parse");
461        db.parse(&id).expect("cached parse");
462        assert_eq!(db.stats().lex_runs, 1);
463        assert_eq!(db.stats().parse_runs, 1);
464
465        assert_eq!(
466            db.set_source(id.clone(), "const x = 1\n".to_string(), SourceVersion(2)),
467            SourceUpdate::Unchanged
468        );
469        db.parse(&id).expect("same digest parse");
470        assert_eq!(db.stats().lex_runs, 1);
471        assert_eq!(db.stats().parse_runs, 1);
472    }
473
474    #[test]
475    fn source_change_invalidates_parse_and_typecheck_outputs() {
476        let mut db = AnalysisDatabase::new();
477        let id = source_id();
478        db.set_source(id.clone(), "const x = 1\n".to_string(), SourceVersion(1));
479        db.typecheck(&id, TypeCheckConfig::new())
480            .expect("initial check");
481        assert_eq!(
482            db.set_source(id.clone(), "const x = 2\n".to_string(), SourceVersion(2)),
483            SourceUpdate::Changed
484        );
485        db.typecheck(&id, TypeCheckConfig::new())
486            .expect("changed check");
487        assert_eq!(db.stats().lex_runs, 2);
488        assert_eq!(db.stats().parse_runs, 2);
489        assert_eq!(db.stats().typecheck_runs, 2);
490    }
491
492    #[test]
493    fn parsed_source_seed_skips_lex_and_parse() {
494        let mut db = AnalysisDatabase::new();
495        let id = source_id();
496        let source = "const x = 1\n".to_string();
497        let mut lexer = Lexer::new(&source);
498        let tokens = lexer.tokenize().expect("tokenize");
499        let mut parser = Parser::new(tokens);
500        let program = parser.parse().expect("parse");
501
502        assert_eq!(
503            db.set_parsed_source(id.clone(), source, SourceVersion(1), program),
504            SourceUpdate::Inserted
505        );
506        db.typecheck(&id, TypeCheckConfig::new())
507            .expect("seeded check");
508        assert_eq!(db.stats().lex_runs, 0);
509        assert_eq!(db.stats().parse_runs, 0);
510        assert_eq!(db.stats().typecheck_runs, 1);
511    }
512
513    #[test]
514    fn typecheck_cache_is_keyed_by_options() {
515        let mut db = AnalysisDatabase::new();
516        let id = source_id();
517        db.set_source(
518            id.clone(),
519            "pipeline main() {\n  const x = read_file(\"a\")\n  log(x.foo)\n}\n".to_string(),
520            SourceVersion(1),
521        );
522        db.typecheck(&id, TypeCheckConfig::new())
523            .expect("default check");
524        db.typecheck(&id, TypeCheckConfig::new())
525            .expect("cached default check");
526        db.typecheck(&id, TypeCheckConfig::new().with_strict_types(true))
527            .expect("strict check");
528        assert_eq!(db.stats().typecheck_runs, 2);
529    }
530
531    #[test]
532    fn typecheck_diagnostics_are_cached_with_hints() {
533        let mut db = AnalysisDatabase::new();
534        let id = source_id();
535        db.set_source(
536            id.clone(),
537            "pipeline main() {\n  const x: int = \"nope\"\n}\n".to_string(),
538            SourceVersion(1),
539        );
540        let first = db.typecheck(&id, TypeCheckConfig::new()).expect("check");
541        let second = db.typecheck(&id, TypeCheckConfig::new()).expect("cached");
542        assert!(first
543            .diagnostics
544            .iter()
545            .any(|diag| diag.severity == DiagnosticSeverity::Error));
546        assert_eq!(first.diagnostics.len(), second.diagnostics.len());
547        assert_eq!(db.stats().typecheck_runs, 1);
548    }
549}
harn_parser/analysis.rs

harn_parser/
analysis.rs
