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

harn_parser/
analysis.rs
