1use std::collections::{HashMap, HashSet};
2use std::hash::Hasher;
3use std::io::Write;
4use std::path::Path;
5use std::sync::atomic::{AtomicUsize, Ordering};
6use std::sync::Arc;
7
8use harn_lexer::{Lexer, LexerError};
9
10use crate::{BindingTypeInfo, InlayHintInfo, PredicateSite, TypeCheckFacts};
11use crate::{Parser, ParserError, SNode, TypeChecker, TypeDiagnostic};
12
13#[derive(Debug, Clone, PartialEq, Eq, Hash)]
15pub struct SourceId(String);
16
17impl SourceId {
18 pub fn new(value: impl Into<String>) -> Self {
19 Self(value.into())
20 }
21
22 pub fn path(path: &Path) -> Self {
23 Self(path.to_string_lossy().into_owned())
24 }
25
26 pub fn as_str(&self) -> &str {
27 &self.0
28 }
29}
30
31#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
33pub struct SourceVersion(pub u64);
34
35#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
37pub struct SourceDigest(u64);
38
39impl SourceDigest {
40 pub fn from_source(source: &str) -> Self {
41 let mut hash = 0xcbf29ce484222325u64;
42 for byte in source.as_bytes() {
43 hash ^= u64::from(*byte);
44 hash = hash.wrapping_mul(0x100000001b3);
45 }
46 Self(hash)
47 }
48}
49
50#[derive(Debug, Clone, Copy, PartialEq, Eq)]
51pub enum SourceUpdate {
52 Inserted,
53 Changed,
54 Unchanged,
55}
56
57#[derive(Debug, Clone, Default, PartialEq, Eq)]
58pub struct AnalysisStats {
59 pub lex_runs: usize,
60 pub parse_runs: usize,
61 pub typecheck_runs: usize,
62}
63
64static PARSE_RUNS: AtomicUsize = AtomicUsize::new(0);
65static TYPECHECK_RUNS: AtomicUsize = AtomicUsize::new(0);
66
67pub(crate) fn record_parse_run() {
68 PARSE_RUNS.fetch_add(1, Ordering::Relaxed);
69}
70
71pub(crate) fn record_typecheck_run() {
72 TYPECHECK_RUNS.fetch_add(1, Ordering::Relaxed);
73}
74
75pub fn process_stats() -> AnalysisStats {
80 AnalysisStats {
81 lex_runs: harn_lexer::process_tokenize_runs(),
82 parse_runs: PARSE_RUNS.load(Ordering::Relaxed),
83 typecheck_runs: TYPECHECK_RUNS.load(Ordering::Relaxed),
84 }
85}
86
87#[derive(Debug, Clone)]
90pub struct ParseOutput {
91 pub source: Arc<str>,
92 pub program: Arc<Vec<SNode>>,
93}
94
95#[derive(Debug, Clone)]
98pub struct TypeCheckOutput {
99 pub source: Arc<str>,
100 pub program: Arc<Vec<SNode>>,
101 pub diagnostics: Arc<Vec<TypeDiagnostic>>,
102 pub inlay_hints: Arc<Vec<InlayHintInfo>>,
103 pub binding_types: Arc<Vec<BindingTypeInfo>>,
104 pub predicate_sites: Arc<Vec<PredicateSite>>,
105}
106
107#[derive(Debug, Clone, PartialEq, Eq)]
108pub enum AnalysisError {
109 MissingSource(SourceId),
110 Lex {
111 source: String,
112 error: LexerError,
113 },
114 Parse {
115 source: String,
116 errors: Vec<ParserError>,
117 },
118}
119
120impl AnalysisError {
121 pub fn source(&self) -> Option<&str> {
122 match self {
123 AnalysisError::MissingSource(_) => None,
124 AnalysisError::Lex { source, .. } | AnalysisError::Parse { source, .. } => Some(source),
125 }
126 }
127}
128
129#[derive(Debug, Clone, Default)]
130pub struct TypeCheckConfig {
131 pub strict_types: bool,
132 pub privileged_wire_builtins: bool,
133 pub imported_names: Option<HashSet<String>>,
134 pub imported_type_decls: Vec<SNode>,
135 pub imported_callable_decls: Vec<SNode>,
136 pub namespace_imports: Vec<(String, crate::NamespaceImportBinding)>,
137}
138
139impl TypeCheckConfig {
140 pub fn new() -> Self {
141 Self::default()
142 }
143
144 pub fn with_strict_types(mut self, strict_types: bool) -> Self {
145 self.strict_types = strict_types;
146 self
147 }
148
149 pub fn with_privileged_wire_builtins(mut self, enabled: bool) -> Self {
150 self.privileged_wire_builtins = enabled;
151 self
152 }
153
154 pub fn with_imported_names(mut self, imported_names: Option<HashSet<String>>) -> Self {
155 self.imported_names = imported_names;
156 self
157 }
158
159 pub fn with_imported_type_decls(mut self, imported_type_decls: Vec<SNode>) -> Self {
160 self.imported_type_decls = imported_type_decls;
161 self
162 }
163
164 pub fn with_imported_callable_decls(mut self, imported_callable_decls: Vec<SNode>) -> Self {
165 self.imported_callable_decls = imported_callable_decls;
166 self
167 }
168
169 pub fn with_namespace_imports(
170 mut self,
171 namespace_imports: Vec<(String, crate::NamespaceImportBinding)>,
172 ) -> Self {
173 self.namespace_imports = namespace_imports;
174 self
175 }
176
177 fn cache_key(&self) -> TypeCheckCacheKey {
178 let mut imported_names = self
179 .imported_names
180 .as_ref()
181 .map(|names| names.iter().cloned().collect::<Vec<_>>());
182 if let Some(names) = &mut imported_names {
183 names.sort();
184 }
185 let mut namespace_imports: Vec<_> = self.namespace_imports.iter().collect();
186 namespace_imports.sort_by(|a, b| a.0.cmp(&b.0));
187 TypeCheckCacheKey {
188 strict_types: self.strict_types,
189 privileged_wire_builtins: self.privileged_wire_builtins,
190 imported_names,
191 imported_type_decls_digest: structural_digest(&self.imported_type_decls),
192 imported_callable_decls_digest: structural_digest(&self.imported_callable_decls),
193 namespace_imports_digest: structural_digest(&namespace_imports),
194 }
195 }
196
197 fn into_checker(self) -> TypeChecker {
198 let checker = TypeChecker::with_strict_types(self.strict_types)
199 .with_privileged_wire_builtins(self.privileged_wire_builtins);
200 self.apply_imports_to(checker)
201 }
202
203 pub fn apply_imports_to(self, mut checker: TypeChecker) -> TypeChecker {
205 if let Some(imported) = self.imported_names {
206 checker = checker.with_imported_names(imported);
207 }
208 if !self.imported_type_decls.is_empty() {
209 checker = checker.with_imported_type_decls(self.imported_type_decls);
210 }
211 if !self.imported_callable_decls.is_empty() {
212 checker = checker.with_imported_callable_decls(self.imported_callable_decls);
213 }
214 if !self.namespace_imports.is_empty() {
215 checker = checker.with_namespace_imports(self.namespace_imports);
216 }
217 checker
218 }
219
220 pub fn check_with_facts(&self, program: &[SNode], source: &str) -> TypeCheckFacts {
222 self.clone()
223 .into_checker()
224 .check_with_facts(program, source)
225 }
226}
227
228#[derive(Debug, Clone, PartialEq, Eq, Hash)]
229struct TypeCheckCacheKey {
230 strict_types: bool,
231 privileged_wire_builtins: bool,
232 imported_names: Option<Vec<String>>,
233 imported_type_decls_digest: u64,
234 imported_callable_decls_digest: u64,
235 namespace_imports_digest: u64,
236}
237
238#[derive(Debug, Clone)]
239struct CachedTypeCheck {
240 diagnostics: Arc<Vec<TypeDiagnostic>>,
241 inlay_hints: Arc<Vec<InlayHintInfo>>,
242 binding_types: Arc<Vec<BindingTypeInfo>>,
243 predicate_sites: Arc<Vec<PredicateSite>>,
244}
245
246#[derive(Debug, Clone)]
247struct SourceEntry {
248 source: Arc<str>,
249 version: SourceVersion,
250 digest: SourceDigest,
251 lex_error: Option<LexerError>,
252 program: Option<Result<Arc<Vec<SNode>>, Vec<ParserError>>>,
253 typechecks: HashMap<TypeCheckCacheKey, CachedTypeCheck>,
254}
255
256impl SourceEntry {
257 fn new(source: Arc<str>, version: SourceVersion, digest: SourceDigest) -> Self {
258 Self {
259 source,
260 version,
261 digest,
262 lex_error: None,
263 program: None,
264 typechecks: HashMap::new(),
265 }
266 }
267
268 fn replace_source(&mut self, source: Arc<str>, version: SourceVersion, digest: SourceDigest) {
269 self.source = source;
270 self.version = version;
271 self.digest = digest;
272 self.lex_error = None;
273 self.program = None;
274 self.typechecks.clear();
275 }
276}
277
278#[derive(Debug, Default)]
280pub struct AnalysisDatabase {
281 entries: HashMap<SourceId, SourceEntry>,
282 stats: AnalysisStats,
283}
284
285impl AnalysisDatabase {
286 pub fn new() -> Self {
287 Self::default()
288 }
289
290 pub fn stats(&self) -> AnalysisStats {
291 self.stats.clone()
292 }
293
294 pub fn remove_source(&mut self, id: &SourceId) -> bool {
301 self.entries.remove(id).is_some()
302 }
303
304 pub fn set_source(
305 &mut self,
306 id: SourceId,
307 source: String,
308 version: SourceVersion,
309 ) -> SourceUpdate {
310 let digest = SourceDigest::from_source(&source);
311 match self.entries.get_mut(&id) {
312 None => {
313 self.entries
314 .insert(id, SourceEntry::new(source.into(), version, digest));
315 SourceUpdate::Inserted
316 }
317 Some(entry) if entry.digest == digest => {
318 entry.version = version;
319 SourceUpdate::Unchanged
320 }
321 Some(entry) => {
322 entry.replace_source(source.into(), version, digest);
323 SourceUpdate::Changed
324 }
325 }
326 }
327
328 pub fn set_parsed_source(
329 &mut self,
330 id: SourceId,
331 source: String,
332 version: SourceVersion,
333 program: Vec<SNode>,
334 ) -> SourceUpdate {
335 let digest = SourceDigest::from_source(&source);
336 match self.entries.get_mut(&id) {
337 None => {
338 let mut entry = SourceEntry::new(source.into(), version, digest);
339 entry.program = Some(Ok(Arc::new(program)));
340 self.entries.insert(id, entry);
341 SourceUpdate::Inserted
342 }
343 Some(entry) if entry.digest == digest => {
344 entry.version = version;
345 entry.program = Some(Ok(Arc::new(program)));
346 SourceUpdate::Unchanged
347 }
348 Some(entry) => {
349 entry.replace_source(source.into(), version, digest);
350 entry.program = Some(Ok(Arc::new(program)));
351 SourceUpdate::Changed
352 }
353 }
354 }
355
356 pub fn parse(&mut self, id: &SourceId) -> Result<ParseOutput, AnalysisError> {
357 let entry = self
358 .entries
359 .get_mut(id)
360 .ok_or_else(|| AnalysisError::MissingSource(id.clone()))?;
361 if entry.program.is_none() {
362 if let Some(error) = &entry.lex_error {
363 return Err(AnalysisError::Lex {
364 source: entry.source.to_string(),
365 error: error.clone(),
366 });
367 }
368 self.stats.lex_runs += 1;
369 let tokens = Lexer::new(&entry.source).tokenize().map_err(|error| {
370 entry.lex_error = Some(error.clone());
371 AnalysisError::Lex {
372 source: entry.source.to_string(),
373 error,
374 }
375 })?;
376 self.stats.parse_runs += 1;
377 let mut parser = Parser::new(tokens);
378 entry.program = Some(parser.parse().map(Arc::new).map_err(|error| {
379 let mut errors = parser.all_errors().to_vec();
380 if errors.is_empty() {
381 errors.push(error);
382 }
383 errors
384 }));
385 }
386 match entry.program.as_ref().expect("program initialized") {
387 Ok(program) => Ok(ParseOutput {
388 source: Arc::clone(&entry.source),
389 program: Arc::clone(program),
390 }),
391 Err(errors) => Err(AnalysisError::Parse {
392 source: entry.source.to_string(),
393 errors: errors.clone(),
394 }),
395 }
396 }
397
398 pub fn typecheck(
399 &mut self,
400 id: &SourceId,
401 config: TypeCheckConfig,
402 ) -> Result<TypeCheckOutput, AnalysisError> {
403 let parsed = self.parse(id)?;
404 let key = config.cache_key();
405 if let Some(cached) = self
406 .entries
407 .get(id)
408 .expect("parse verified source entry")
409 .typechecks
410 .get(&key)
411 {
412 return Ok(TypeCheckOutput::from_cache(parsed, cached));
413 }
414
415 self.stats.typecheck_runs += 1;
416 let TypeCheckFacts {
417 diagnostics,
418 inlay_hints,
419 binding_types,
420 predicate_sites,
421 } = config
422 .into_checker()
423 .check_with_facts(&parsed.program, &parsed.source);
424 let cached = CachedTypeCheck {
425 diagnostics: Arc::new(diagnostics),
426 inlay_hints: Arc::new(inlay_hints),
427 binding_types: Arc::new(binding_types),
428 predicate_sites: Arc::new(predicate_sites),
429 };
430 let output = TypeCheckOutput::from_cache(parsed, &cached);
431 self.entries
432 .get_mut(id)
433 .expect("parse verified source entry")
434 .typechecks
435 .insert(key, cached);
436 Ok(output)
437 }
438}
439
440impl TypeCheckOutput {
441 fn from_cache(parsed: ParseOutput, cached: &CachedTypeCheck) -> Self {
442 Self {
443 source: parsed.source,
444 program: parsed.program,
445 diagnostics: Arc::clone(&cached.diagnostics),
446 inlay_hints: Arc::clone(&cached.inlay_hints),
447 binding_types: Arc::clone(&cached.binding_types),
448 predicate_sites: Arc::clone(&cached.predicate_sites),
449 }
450 }
451}
452
453fn structural_digest<T: serde::Serialize>(value: &T) -> u64 {
454 let mut hasher = StableHasher::default();
455 serde_json::to_writer(HasherWriter(&mut hasher), value)
456 .expect("typecheck cache-key values are JSON-serializable");
457 hasher.finish()
458}
459
460struct HasherWriter<'a>(&'a mut StableHasher);
461
462impl Write for HasherWriter<'_> {
463 fn write(&mut self, bytes: &[u8]) -> std::io::Result<usize> {
464 self.0.write(bytes);
465 Ok(bytes.len())
466 }
467
468 fn flush(&mut self) -> std::io::Result<()> {
469 Ok(())
470 }
471}
472
473#[derive(Default)]
474struct StableHasher(u64);
475
476impl Hasher for StableHasher {
477 fn finish(&self) -> u64 {
478 self.0
479 }
480
481 fn write(&mut self, bytes: &[u8]) {
482 let mut hash = if self.0 == 0 {
483 0xcbf29ce484222325u64
484 } else {
485 self.0
486 };
487 for byte in bytes {
488 hash ^= u64::from(*byte);
489 hash = hash.wrapping_mul(0x100000001b3);
490 }
491 self.0 = hash;
492 }
493}
494
495#[cfg(test)]
496mod tests {
497 use super::*;
498 use crate::{DiagnosticSeverity, TypeExpr};
499
500 fn source_id() -> SourceId {
501 SourceId::new("test.harn")
502 }
503
504 #[test]
505 fn parse_reuses_cached_program_for_unchanged_source() {
506 let mut db = AnalysisDatabase::new();
507 let id = source_id();
508 assert_eq!(
509 db.set_source(id.clone(), "const x = 1\n".to_string(), SourceVersion(1)),
510 SourceUpdate::Inserted
511 );
512 db.parse(&id).expect("initial parse");
513 db.parse(&id).expect("cached parse");
514 assert_eq!(db.stats().lex_runs, 1);
515 assert_eq!(db.stats().parse_runs, 1);
516
517 assert_eq!(
518 db.set_source(id.clone(), "const x = 1\n".to_string(), SourceVersion(2)),
519 SourceUpdate::Unchanged
520 );
521 db.parse(&id).expect("same digest parse");
522 assert_eq!(db.stats().lex_runs, 1);
523 assert_eq!(db.stats().parse_runs, 1);
524 }
525
526 #[test]
527 fn namespace_signature_changes_invalidate_cached_typechecks() {
528 let mut db = AnalysisDatabase::new();
529 let id = source_id();
530 db.set_source(
531 id.clone(),
532 "import * as api from \"api\"\napi.take(\"text\")\n".into(),
533 SourceVersion(1),
534 );
535 let config = |accepts: &str| {
536 TypeCheckConfig::new().with_namespace_imports(vec![(
537 "api".into(),
538 crate::NamespaceImportBinding {
539 module_path: "api".into(),
540 members: std::collections::BTreeSet::from(["take".into()]),
541 member_types: std::collections::BTreeMap::from([(
542 "take".into(),
543 TypeExpr::FnType {
544 params: vec![TypeExpr::Named(accepts.into())],
545 return_type: Box::new(TypeExpr::Named("nil".into())),
546 },
547 )]),
548 member_param_names: std::collections::BTreeMap::from([(
549 "take".into(),
550 vec!["input".into()],
551 )]),
552 member_required_params: std::collections::BTreeMap::from([("take".into(), 1)]),
553 member_type_predicates: Default::default(),
554 },
555 )])
556 };
557 assert!(db
558 .typecheck(&id, config("string"))
559 .unwrap()
560 .diagnostics
561 .is_empty());
562 db.typecheck(&id, config("string")).unwrap();
563 assert_eq!(
564 db.stats().typecheck_runs,
565 1,
566 "the unchanged contract must hit the cache"
567 );
568 assert!(db
569 .typecheck(&id, config("int"))
570 .unwrap()
571 .diagnostics
572 .iter()
573 .any(|diagnostic| diagnostic.severity == DiagnosticSeverity::Error));
574 assert_eq!(db.stats().typecheck_runs, 2);
575 }
576
577 #[test]
578 fn cached_results_are_shared_not_copied() {
579 let mut db = AnalysisDatabase::new();
580 let id = source_id();
581 db.set_source(id.clone(), "const x = 1\n".to_string(), SourceVersion(1));
582 let parsed = db.parse(&id).expect("parse");
583 let checked = db.typecheck(&id, TypeCheckConfig::new()).expect("check");
584 let again = db
585 .typecheck(&id, TypeCheckConfig::new())
586 .expect("cached check");
587 assert!(Arc::ptr_eq(&parsed.program, &checked.program));
588 assert!(Arc::ptr_eq(&parsed.source, &again.source));
589 assert!(Arc::ptr_eq(&checked.binding_types, &again.binding_types));
590 assert!(Arc::ptr_eq(&checked.diagnostics, &again.diagnostics));
591 }
592
593 #[test]
594 fn failed_analysis_is_cached_until_source_changes() {
595 for (source, parses) in [("#", 0), ("const =", 1)] {
596 let mut db = AnalysisDatabase::new();
597 let id = source_id();
598 db.set_source(id.clone(), source.into(), SourceVersion(1));
599 let first = db.parse(&id).unwrap_err();
600 let second = db.parse(&id).unwrap_err();
601 assert_eq!(first, second);
602 assert_eq!(db.stats().lex_runs, 1);
603 assert_eq!(db.stats().parse_runs, parses);
604 db.set_source(id.clone(), "const x = 1\n".into(), SourceVersion(2));
605 assert_eq!(db.parse(&id).unwrap().program.len(), 1);
606 assert_eq!(db.stats().lex_runs, 2);
607 assert_eq!(db.stats().parse_runs, parses + 1);
608 }
609 }
610
611 #[test]
612 fn source_change_invalidates_parse_and_typecheck_outputs() {
613 let mut db = AnalysisDatabase::new();
614 let id = source_id();
615 db.set_source(id.clone(), "const x = 1\n".to_string(), SourceVersion(1));
616 db.typecheck(&id, TypeCheckConfig::new())
617 .expect("initial check");
618 assert_eq!(
619 db.set_source(id.clone(), "const x = 2\n".to_string(), SourceVersion(2)),
620 SourceUpdate::Changed
621 );
622 db.typecheck(&id, TypeCheckConfig::new())
623 .expect("changed check");
624 assert_eq!(db.stats().lex_runs, 2);
625 assert_eq!(db.stats().parse_runs, 2);
626 assert_eq!(db.stats().typecheck_runs, 2);
627 }
628
629 #[test]
630 fn parsed_source_seed_skips_lex_and_parse() {
631 let mut db = AnalysisDatabase::new();
632 let id = source_id();
633 let source = "const x = 1\n".to_string();
634 let mut lexer = Lexer::new(&source);
635 let tokens = lexer.tokenize().expect("tokenize");
636 let mut parser = Parser::new(tokens);
637 let program = parser.parse().expect("parse");
638
639 assert_eq!(
640 db.set_parsed_source(id.clone(), source, SourceVersion(1), program),
641 SourceUpdate::Inserted
642 );
643 db.typecheck(&id, TypeCheckConfig::new())
644 .expect("seeded check");
645 assert_eq!(db.stats().lex_runs, 0);
646 assert_eq!(db.stats().parse_runs, 0);
647 assert_eq!(db.stats().typecheck_runs, 1);
648 }
649
650 #[test]
651 fn typecheck_cache_is_keyed_by_options() {
652 let mut db = AnalysisDatabase::new();
653 let id = source_id();
654 db.set_source(
655 id.clone(),
656 "pipeline main() {\n const x = read_file(\"a\")\n log(x.foo)\n}\n".to_string(),
657 SourceVersion(1),
658 );
659 db.typecheck(&id, TypeCheckConfig::new())
660 .expect("default check");
661 db.typecheck(&id, TypeCheckConfig::new())
662 .expect("cached default check");
663 db.typecheck(&id, TypeCheckConfig::new().with_strict_types(true))
664 .expect("strict check");
665 assert_eq!(db.stats().typecheck_runs, 2);
666 }
667
668 #[test]
669 fn typecheck_diagnostics_are_cached_with_hints() {
670 let mut db = AnalysisDatabase::new();
671 let id = source_id();
672 db.set_source(
673 id.clone(),
674 "pipeline main() {\n const x: int = \"nope\"\n}\n".to_string(),
675 SourceVersion(1),
676 );
677 let first = db.typecheck(&id, TypeCheckConfig::new()).expect("check");
678 let second = db.typecheck(&id, TypeCheckConfig::new()).expect("cached");
679 assert!(first
680 .diagnostics
681 .iter()
682 .any(|diag| diag.severity == DiagnosticSeverity::Error));
683 assert_eq!(first.diagnostics.len(), second.diagnostics.len());
684 assert_eq!(db.stats().typecheck_runs, 1);
685 }
686
687 #[test]
688 fn typecheck_facts_keep_shadowed_inferred_bindings_distinct() {
689 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";
690 let program = crate::parse_source(source).expect("parse");
691
692 let facts = TypeCheckConfig::new().check_with_facts(&program, source);
693 let values = facts
694 .binding_types
695 .iter()
696 .filter(|binding| binding.name == "value")
697 .collect::<Vec<_>>();
698
699 assert_eq!(values.len(), 2, "{:#?}", facts.binding_types);
700 assert_ne!(values[0].span, values[1].span);
701 assert_eq!(crate::format_type(&values[0].type_expr), "HarnessAgent");
702 assert_eq!(crate::format_type(&values[1].type_expr), "string");
703 }
704}