harn_parser/
analysis.rs

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

harn_parser/
analysis.rs
