1pub(super) use std::collections::BTreeMap;
2
3pub(super) use ruka_frontend::{FrontendNodeIndex, FrontendParent, ItemId};
4use thiserror::Error;
5
6pub(super) use crate::elab::elaborate_meta_generated_expr;
7pub(super) use crate::meta_builtins::{
8 TupleExprBuiltinError, TupleTypeBuiltinError, builtin_meta_call_arity, builtin_meta_call_name,
9 builtin_spec_by_name, string_concat, string_drop, string_starts_with, string_take,
10 tuple_expr_head, tuple_expr_is_empty, tuple_expr_tail, tuple_type_head_builtin,
11 tuple_type_tail_builtin,
12};
13pub(super) use crate::meta_types::{format_type_expr, meta_types_compatible};
14pub(super) use crate::semantic::{
15 BuilderBindingInfo, MetaType, ResolvedName, SemanticIssue, StagedSemanticInfo, analyze_program,
16};
17pub(super) use crate::syntax::ast::{
18 Block, CallArg, Expr, FunctionDecl, MetaBlock, MetaExpr, MetaFunctionDecl, MetaMatchPattern,
19 MetaStmt, NamedExprField, Program, QuotedCode, Stmt, TypeExpr,
20};
21
22use super::quote_match::format_meta_type;
23use super::runtime_eval::{eval_meta_block, expand_runtime_expr};
24
25pub(super) type RuntimeScope = BTreeMap<String, Option<TypeExpr>>;
26
27#[derive(Debug, Clone)]
28pub(super) struct BuilderEnvCursor {
29 envs: Vec<Vec<BuilderBindingInfo>>,
30 next: usize,
31 meta_entries: Vec<MetaExprSemanticEntry>,
32 next_meta: usize,
33 stmt_entries: Vec<MetaStmtSemanticEntry>,
34 next_stmt: usize,
35}
36
37#[derive(Debug, Clone)]
38pub(super) struct MetaExprSemanticEntry {
39 pub(super) resolved_name: Option<ResolvedName>,
40 pub(super) meta_type: Option<MetaType>,
41 pub(super) call_info: Option<crate::semantic::MetaCallInfo>,
42}
43
44#[derive(Debug, Clone)]
45pub(super) struct MetaStmtSemanticEntry {
46 pub(super) match_info: Option<crate::semantic::MetaMatchInfo>,
47}
48
49impl BuilderEnvCursor {
50 pub(super) fn for_runtime_function(
51 info: &StagedSemanticInfo,
52 runtime_function_index: usize,
53 import_count: usize,
54 ) -> Self {
55 let item_id = info
56 .nodes
57 .items
58 .keys()
59 .nth(import_count + runtime_function_index);
60 let envs = info
61 .nodes
62 .meta_expressions
63 .iter()
64 .filter_map(|(id, kind)| {
65 if !matches!(kind, crate::syntax::ast::MetaExprKind::BuildExpr) {
66 return None;
67 }
68 let item_id = item_id?;
69 meta_expr_belongs_to_item(&info.nodes, id, item_id)
70 .then(|| info.builder_envs[id].clone().unwrap_or_default())
71 })
72 .collect();
73 let meta_entries = info
74 .nodes
75 .meta_expressions
76 .keys()
77 .filter(|id| {
78 item_id.is_some_and(|item| meta_expr_belongs_to_item(&info.nodes, *id, item))
79 })
80 .map(|id| MetaExprSemanticEntry {
81 resolved_name: info.meta_name_resolution[id].clone(),
82 meta_type: info.meta_expr_types[id].clone(),
83 call_info: info.meta_call_info[id].clone(),
84 })
85 .collect();
86 let stmt_entries = info
87 .nodes
88 .meta_statements
89 .keys()
90 .filter(|id| {
91 item_id.is_some_and(|item| meta_stmt_belongs_to_item(&info.nodes, *id, item))
92 })
93 .map(|id| MetaStmtSemanticEntry {
94 match_info: info.meta_match_info[id].clone(),
95 })
96 .collect();
97 Self {
98 envs,
99 next: 0,
100 meta_entries,
101 next_meta: 0,
102 stmt_entries,
103 next_stmt: 0,
104 }
105 }
106
107 pub(super) fn next_env(&mut self) -> Option<&[BuilderBindingInfo]> {
108 let env = self.envs.get(self.next)?;
109 self.next += 1;
110 Some(env.as_slice())
111 }
112
113 pub(super) fn next_meta_entry(&mut self) -> Option<&MetaExprSemanticEntry> {
114 let entry = self.meta_entries.get(self.next_meta)?;
115 self.next_meta += 1;
116 Some(entry)
117 }
118
119 pub(super) fn next_stmt_entry(&mut self) -> Option<&MetaStmtSemanticEntry> {
120 let entry = self.stmt_entries.get(self.next_stmt)?;
121 self.next_stmt += 1;
122 Some(entry)
123 }
124}
125
126#[derive(Debug, Clone, PartialEq, Eq)]
128pub enum TemplateMetaBinding {
129 Int(i64),
131 String(String),
133 Type(TypeExpr),
135}
136
137#[derive(Debug, Clone, PartialEq, Eq)]
138pub(super) enum MetaValue {
139 Int(i64),
140 Bool(bool),
141 String(String),
142 Type(TypeExpr),
143 Expr { expr: Expr, ty: TypeExpr },
144 Code(CodeValue),
145}
146
147#[derive(Debug, Clone, PartialEq, Eq)]
148pub(super) enum CodeValue {
149 Expr(Expr),
150 Type(TypeExpr),
151}
152
153#[derive(Debug, Error, Clone, PartialEq, Eq)]
155pub enum MetaEvalError {
156 #[error("unknown meta binding `{name}`")]
158 UnknownBinding {
159 name: String,
161 },
162 #[error(
164 "runtime binding `{name}` is unavailable in meta phase; compute it inside `meta {{ ... }}` or pass `Expr[...]`"
165 )]
166 RuntimeBindingUnavailable {
167 name: String,
169 },
170 #[error(
172 "{kind} `{name}` is not a meta value; use staged syntax or pass the needed value explicitly"
173 )]
174 KnownNameNotMetaValue {
175 name: String,
177 kind: &'static str,
179 },
180 #[error("unknown meta function `{name}`")]
182 UnknownMetaFunction {
183 name: String,
185 },
186 #[error("meta function `{name}` has duplicate declarations")]
188 DuplicateMetaFunction {
189 name: String,
191 },
192 #[error("meta function `{name}` expected {expected} args, got {actual}")]
194 ArityMismatch {
195 name: String,
197 expected: usize,
199 actual: usize,
201 },
202 #[error("quote splice requires code value, found {found}")]
204 SpliceExpectedCode {
205 found: &'static str,
207 },
208 #[error("meta match requires code value")]
210 MatchExpectedCode,
211 #[error("meta builtin `{builtin}` requires tuple code value")]
213 ExpectedTupleCode {
214 builtin: &'static str,
216 },
217 #[error("meta builtin `{builtin}` requires tuple type value")]
219 ExpectedTupleType {
220 builtin: &'static str,
222 },
223 #[error("meta match had no matching arm")]
225 NoMatchArm,
226 #[error("meta function `{name}` did not produce a return value")]
228 MissingReturnValue {
229 name: String,
231 },
232 #[error("meta value type mismatch: expected `{expected}`, found `{actual}`")]
234 TypeMismatch {
235 expected: String,
237 actual: String,
239 },
240 #[error("meta expression elaboration failed: {message}")]
242 Elab {
243 message: String,
245 },
246}
247
248pub fn expand_program(program: &Program) -> Result<Program, MetaEvalError> {
250 let function_table = build_meta_function_table(program)?;
251 let semantic = analyze_program(program);
252 if let Some(issue) = semantic.meta_function_issues.values().next() {
253 return Err(meta_eval_error_from_semantic_issue(issue));
254 }
255 let mut functions = Vec::with_capacity(program.functions.len());
256 for (function_index, function) in program.functions.iter().enumerate() {
257 if should_defer_runtime_meta(function) {
258 functions.push(function.clone());
259 } else {
260 if let Some(issue) = first_semantic_issue_for_runtime_function(
261 &semantic,
262 function_index,
263 program.imports.len(),
264 ) {
265 return Err(meta_eval_error_from_semantic_issue(issue));
266 }
267 let mut builder_env_cursor = BuilderEnvCursor::for_runtime_function(
268 &semantic,
269 function_index,
270 program.imports.len(),
271 );
272 functions.push(expand_function(
273 program,
274 function,
275 &function_table,
276 Some(&mut builder_env_cursor),
277 )?);
278 }
279 }
280
281 Ok(Program {
282 imports: program.imports.clone(),
283 functions,
284 meta_functions: program.meta_functions.clone(),
285 extern_modules: program.extern_modules.clone(),
286 structs: program.structs.clone(),
287 enums: program.enums.clone(),
288 })
289}
290
291pub fn expand_function_template_instance(
293 program: &Program,
294 function: &FunctionDecl,
295 bindings: &BTreeMap<String, TemplateMetaBinding>,
296) -> Result<FunctionDecl, MetaEvalError> {
297 let function_table = build_meta_function_table(program)?;
298 let semantic = analyze_program(program);
299 if let Some(issue) = semantic.meta_function_issues.values().next() {
300 return Err(meta_eval_error_from_semantic_issue(issue));
301 }
302 let env = bindings
303 .iter()
304 .map(|(name, binding)| (name.clone(), template_binding_to_meta_value(binding)))
305 .collect::<BTreeMap<_, _>>();
306 let mut builder_env_cursor = program
307 .functions
308 .iter()
309 .position(|candidate| std::ptr::eq(candidate, function))
310 .map(|function_index| {
311 if let Some(issue) = first_semantic_issue_for_runtime_function(
312 &semantic,
313 function_index,
314 program.imports.len(),
315 ) {
316 return Err(meta_eval_error_from_semantic_issue(issue));
317 }
318 Ok(BuilderEnvCursor::for_runtime_function(
319 &semantic,
320 function_index,
321 program.imports.len(),
322 ))
323 })
324 .transpose()?;
325 expand_function_with_env(
326 program,
327 function,
328 &function_table,
329 &env,
330 builder_env_cursor.as_mut(),
331 )
332}
333
334fn meta_expr_belongs_to_item(
335 nodes: &FrontendNodeIndex,
336 meta_expr_id: ruka_frontend::MetaExprId,
337 item_id: ItemId,
338) -> bool {
339 let mut parent = nodes.meta_expression_parents[meta_expr_id];
340 while let Some(current) = parent {
341 match current {
342 FrontendParent::Item(current_item) => return current_item == item_id,
343 FrontendParent::Stmt(stmt) => parent = nodes.statement_parents[stmt],
344 FrontendParent::Expr(expr) => parent = nodes.expression_parents[expr],
345 FrontendParent::MetaStmt(stmt) => parent = nodes.meta_statement_parents[stmt],
346 FrontendParent::MetaExpr(expr) => parent = nodes.meta_expression_parents[expr],
347 FrontendParent::Type(ty) => parent = nodes.type_parents[ty],
348 }
349 }
350 false
351}
352
353fn meta_stmt_belongs_to_item(
354 nodes: &FrontendNodeIndex,
355 meta_stmt_id: ruka_frontend::MetaStmtId,
356 item_id: ItemId,
357) -> bool {
358 let mut parent = nodes.meta_statement_parents[meta_stmt_id];
359 while let Some(current) = parent {
360 match current {
361 FrontendParent::Item(current_item) => return current_item == item_id,
362 FrontendParent::Stmt(stmt) => parent = nodes.statement_parents[stmt],
363 FrontendParent::Expr(expr) => parent = nodes.expression_parents[expr],
364 FrontendParent::MetaStmt(stmt) => parent = nodes.meta_statement_parents[stmt],
365 FrontendParent::MetaExpr(expr) => parent = nodes.meta_expression_parents[expr],
366 FrontendParent::Type(ty) => parent = nodes.type_parents[ty],
367 }
368 }
369 false
370}
371
372fn first_semantic_issue_for_runtime_function<'a>(
373 semantic: &'a StagedSemanticInfo,
374 runtime_function_index: usize,
375 import_count: usize,
376) -> Option<&'a SemanticIssue> {
377 let item_id = semantic
378 .nodes
379 .items
380 .keys()
381 .nth(import_count + runtime_function_index)?;
382 semantic.issues.iter().find_map(|(meta_expr_id, issue)| {
383 meta_expr_belongs_to_item(&semantic.nodes, *meta_expr_id, item_id).then_some(issue)
384 })
385}
386
387pub(super) fn resolved_name_kind(name: &ResolvedName) -> Option<&'static str> {
388 match name {
389 ResolvedName::RuntimeFunction => Some("runtime function"),
390 ResolvedName::MetaFunction => Some("meta function"),
391 ResolvedName::Struct => Some("struct"),
392 ResolvedName::ExternModule => Some("extern module"),
393 ResolvedName::Type => Some("type"),
394 ResolvedName::RuntimeLocal | ResolvedName::MetaLocal => None,
395 }
396}
397
398pub(super) fn expected_builder_type(meta_type: &MetaType) -> Option<String> {
399 match meta_type {
400 MetaType::Expr(ty) => Some(format_type_expr(ty)),
401 MetaType::Int | MetaType::Bool | MetaType::String | MetaType::Type => None,
402 }
403}
404
405pub(super) fn match_requires_code_but_cannot_have_code(
406 info: &crate::semantic::MetaMatchInfo,
407) -> bool {
408 matches!(
409 info.matched_type,
410 Some(MetaType::Int | MetaType::Bool | MetaType::String)
411 ) && info.pattern_kinds.iter().all(|kind| {
412 matches!(
413 kind,
414 crate::semantic::MetaPatternKind::Quote | crate::semantic::MetaPatternKind::Type
415 )
416 })
417}
418
419pub(super) fn match_cannot_succeed(info: &crate::semantic::MetaMatchInfo) -> bool {
420 let Some(matched_type) = info.matched_type.as_ref() else {
421 return false;
422 };
423 !info
424 .pattern_kinds
425 .iter()
426 .any(|kind| match (matched_type, kind) {
427 (_, crate::semantic::MetaPatternKind::Wildcard) => true,
428 (MetaType::Int, crate::semantic::MetaPatternKind::Int) => true,
429 (MetaType::Bool, crate::semantic::MetaPatternKind::Bool) => true,
430 (MetaType::String, crate::semantic::MetaPatternKind::String) => true,
431 (MetaType::Type, crate::semantic::MetaPatternKind::Type) => true,
432 (MetaType::Expr(_), crate::semantic::MetaPatternKind::Quote) => true,
433 (MetaType::Expr(_), crate::semantic::MetaPatternKind::Type) => true,
434 _ => false,
435 })
436}
437
438fn meta_eval_error_from_semantic_issue(issue: &SemanticIssue) -> MetaEvalError {
439 match issue {
440 SemanticIssue::RuntimeBindingUnavailable { name } => {
441 MetaEvalError::RuntimeBindingUnavailable { name: name.clone() }
442 }
443 SemanticIssue::KnownNameNotMetaValue { name, kind } => {
444 MetaEvalError::KnownNameNotMetaValue {
445 name: name.clone(),
446 kind: resolved_name_kind(kind).expect("semantic issue should have non-meta kind"),
447 }
448 }
449 SemanticIssue::MetaTypeMismatch { expected, actual } => MetaEvalError::TypeMismatch {
450 expected: expected.clone(),
451 actual: actual.clone(),
452 },
453 }
454}
455
456fn should_defer_runtime_meta(function: &FunctionDecl) -> bool {
457 function.params.iter().any(|param| {
458 param.is_meta
459 || param.is_variadic
460 || (param.ty.mode == crate::syntax::ast::OwnershipMode::View
461 && matches!(param.ty.ty, TypeExpr::TypeKind))
462 })
463}
464
465pub(super) fn staged_builtin_arg_mismatch(
466 info: &crate::semantic::MetaCallInfo,
467) -> Option<(&'static str, String)> {
468 let expected = info.expected_arg_kinds.as_ref()?;
469 if expected.len() != info.arg_types.len() {
470 return None;
471 }
472 expected
473 .iter()
474 .zip(info.arg_types.iter())
475 .find_map(|(expected, actual)| {
476 let actual = actual.as_ref()?;
477 if meta_arg_kind_matches(*expected, actual) {
478 return None;
479 }
480 Some((meta_arg_kind_name(*expected), format_meta_type(actual)))
481 })
482}
483
484fn meta_arg_kind_matches(expected: crate::semantic::MetaArgKind, actual: &MetaType) -> bool {
485 matches!(
486 (expected, actual),
487 (crate::semantic::MetaArgKind::Int, MetaType::Int)
488 | (crate::semantic::MetaArgKind::Bool, MetaType::Bool)
489 | (crate::semantic::MetaArgKind::String, MetaType::String)
490 | (crate::semantic::MetaArgKind::Type, MetaType::Type)
491 | (crate::semantic::MetaArgKind::Expr, MetaType::Expr(_))
492 )
493}
494
495fn meta_arg_kind_name(kind: crate::semantic::MetaArgKind) -> &'static str {
496 match kind {
497 crate::semantic::MetaArgKind::Int => "i64",
498 crate::semantic::MetaArgKind::Bool => "Bool",
499 crate::semantic::MetaArgKind::String => "String",
500 crate::semantic::MetaArgKind::Type => "type",
501 crate::semantic::MetaArgKind::Expr => "Expr[...]",
502 }
503}
504
505fn template_binding_to_meta_value(binding: &TemplateMetaBinding) -> MetaValue {
506 match binding {
507 TemplateMetaBinding::Int(value) => MetaValue::Int(*value),
508 TemplateMetaBinding::String(value) => MetaValue::String(value.clone()),
509 TemplateMetaBinding::Type(ty) => MetaValue::Type(ty.clone()),
510 }
511}
512
513fn build_meta_function_table<'a>(
514 program: &'a Program,
515) -> Result<BTreeMap<String, &'a MetaFunctionDecl>, MetaEvalError> {
516 let mut table = BTreeMap::new();
517 for function in &program.meta_functions {
518 if table.insert(function.name.clone(), function).is_some() {
519 return Err(MetaEvalError::DuplicateMetaFunction {
520 name: function.name.clone(),
521 });
522 }
523 }
524 Ok(table)
525}
526
527fn expand_function(
528 program: &Program,
529 function: &FunctionDecl,
530 function_table: &BTreeMap<String, &MetaFunctionDecl>,
531 builder_env_cursor: Option<&mut BuilderEnvCursor>,
532) -> Result<FunctionDecl, MetaEvalError> {
533 expand_function_with_env(
534 program,
535 function,
536 function_table,
537 &BTreeMap::new(),
538 builder_env_cursor,
539 )
540}
541
542fn expand_function_with_env(
543 program: &Program,
544 function: &FunctionDecl,
545 function_table: &BTreeMap<String, &MetaFunctionDecl>,
546 template_env: &BTreeMap<String, MetaValue>,
547 builder_env_cursor: Option<&mut BuilderEnvCursor>,
548) -> Result<FunctionDecl, MetaEvalError> {
549 let mut runtime_scope = RuntimeScope::new();
550 for param in &function.params {
551 runtime_scope.insert(param.name.clone(), Some(param.ty.ty.clone()));
552 }
553 for name in template_env.keys() {
554 runtime_scope.remove(name);
555 }
556
557 Ok(FunctionDecl {
558 name: function.name.clone(),
559 params: function.params.clone(),
560 return_type: function.return_type.clone(),
561 body: expand_runtime_block(
562 program,
563 &function.body,
564 function_table,
565 &runtime_scope,
566 template_env,
567 builder_env_cursor,
568 )?,
569 })
570}
571
572pub(super) fn expand_runtime_block(
573 program: &Program,
574 block: &Block,
575 function_table: &BTreeMap<String, &MetaFunctionDecl>,
576 outer_runtime_scope: &RuntimeScope,
577 template_env: &BTreeMap<String, MetaValue>,
578 mut builder_env_cursor: Option<&mut BuilderEnvCursor>,
579) -> Result<Block, MetaEvalError> {
580 let mut runtime_scope = outer_runtime_scope.clone();
581 let mut statements = Vec::new();
582 for statement in &block.statements {
583 match statement {
584 Stmt::Meta { body } => {
585 let mut env = template_env.clone();
586 let outcome = eval_meta_block(
587 program,
588 body,
589 &mut env,
590 function_table,
591 true,
592 &runtime_scope,
593 builder_env_cursor.as_deref_mut(),
594 )?;
595 statements.extend(outcome.emitted_runtime_stmts);
596 }
597 Stmt::If {
598 condition,
599 then_block,
600 else_block,
601 } => {
602 let then_block = expand_runtime_block(
603 program,
604 then_block,
605 function_table,
606 &runtime_scope,
607 template_env,
608 builder_env_cursor.as_deref_mut(),
609 )?;
610 let else_block = else_block
611 .as_ref()
612 .map(|block| {
613 expand_runtime_block(
614 program,
615 block,
616 function_table,
617 &runtime_scope,
618 template_env,
619 builder_env_cursor.as_deref_mut(),
620 )
621 })
622 .transpose()?;
623 statements.push(Stmt::If {
624 condition: expand_runtime_expr(
625 program,
626 condition,
627 function_table,
628 &runtime_scope,
629 template_env,
630 builder_env_cursor.as_deref_mut(),
631 )?,
632 then_block,
633 else_block,
634 });
635 }
636 Stmt::For {
637 binding,
638 iterable,
639 body,
640 } => {
641 let mut loop_scope = runtime_scope.clone();
642 loop_scope.insert(binding.name.clone(), None);
643 let body = expand_runtime_block(
644 program,
645 body,
646 function_table,
647 &loop_scope,
648 template_env,
649 builder_env_cursor.as_deref_mut(),
650 )?;
651 statements.push(Stmt::For {
652 binding: binding.clone(),
653 iterable: expand_runtime_expr(
654 program,
655 iterable,
656 function_table,
657 &runtime_scope,
658 template_env,
659 builder_env_cursor.as_deref_mut(),
660 )?,
661 body,
662 });
663 }
664 Stmt::While { condition, body } => {
665 let body = expand_runtime_block(
666 program,
667 body,
668 function_table,
669 &runtime_scope,
670 template_env,
671 builder_env_cursor.as_deref_mut(),
672 )?;
673 statements.push(Stmt::While {
674 condition: expand_runtime_expr(
675 program,
676 condition,
677 function_table,
678 &runtime_scope,
679 template_env,
680 builder_env_cursor.as_deref_mut(),
681 )?,
682 body,
683 });
684 }
685 Stmt::Match { value, arms } => {
686 let value = expand_runtime_expr(
687 program,
688 value,
689 function_table,
690 &runtime_scope,
691 template_env,
692 builder_env_cursor.as_deref_mut(),
693 )?;
694 let mut expanded_arms = Vec::with_capacity(arms.len());
695 for arm in arms {
696 let mut arm_scope = runtime_scope.clone();
697 if let ruka_frontend::MatchPattern::Variant { binders, .. } = &arm.pattern {
698 for binder in binders.iter().flatten() {
699 arm_scope.insert(binder.name.clone(), None);
700 }
701 }
702 expanded_arms.push(ruka_frontend::MatchArm {
703 pattern: arm.pattern.clone(),
704 body: expand_runtime_block(
705 program,
706 &arm.body,
707 function_table,
708 &arm_scope,
709 template_env,
710 builder_env_cursor.as_deref_mut(),
711 )?,
712 });
713 }
714 statements.push(Stmt::Match {
715 value,
716 arms: expanded_arms,
717 });
718 }
719 Stmt::Expr { expr, has_semi } => {
720 statements.push(Stmt::Expr {
721 expr: expand_runtime_expr(
722 program,
723 expr,
724 function_table,
725 &runtime_scope,
726 template_env,
727 builder_env_cursor.as_deref_mut(),
728 )?,
729 has_semi: *has_semi,
730 });
731 }
732 Stmt::Let {
733 name,
734 name_span,
735 ownership,
736 mode,
737 value,
738 } => {
739 statements.push(Stmt::Let {
740 name: name.clone(),
741 name_span: *name_span,
742 ownership: *ownership,
743 mode: *mode,
744 value: expand_runtime_expr(
745 program,
746 value,
747 function_table,
748 &runtime_scope,
749 template_env,
750 builder_env_cursor.as_deref_mut(),
751 )?,
752 });
753 runtime_scope.insert(name.clone(), None);
754 }
755 Stmt::Assign {
756 target,
757 mode,
758 value,
759 } => {
760 statements.push(Stmt::Assign {
761 target: target.clone(),
762 mode: *mode,
763 value: expand_runtime_expr(
764 program,
765 value,
766 function_table,
767 &runtime_scope,
768 template_env,
769 builder_env_cursor.as_deref_mut(),
770 )?,
771 });
772 }
773 }
774 }
775 Ok(Block { statements })
776}