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

harn_parser/
analysis.rs
