1use std::collections::HashSet;
4use std::fmt;
5use std::sync::Arc;
6
7use dive_ir::{Arg, DefId, DefScope, Expr, ExprId, OpRef};
8use dive_value::Interner;
9
10use crate::{ConstBinding, EvalError, Evaluator, Model, Scope};
11
12#[derive(Clone, Debug, PartialEq, Eq)]
15pub struct ContextError {
16 kind: ContextErrorKind,
17 detail: String,
18}
19
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
22#[non_exhaustive]
23pub enum ContextErrorKind {
24 UnknownId,
26 Arity,
28 RedirectCycle,
30 ForeignContext,
32 Structure,
34}
35
36impl ContextError {
37 pub(crate) fn new(kind: ContextErrorKind, detail: impl Into<String>) -> Self {
38 Self {
39 kind,
40 detail: detail.into(),
41 }
42 }
43 #[must_use]
45 pub const fn kind(&self) -> ContextErrorKind {
46 self.kind
47 }
48 #[must_use]
50 pub const fn code(&self) -> &'static str {
51 match self.kind {
52 ContextErrorKind::UnknownId => "DIVE-EVAL-C001",
53 ContextErrorKind::Arity => "DIVE-EVAL-C002",
54 ContextErrorKind::RedirectCycle => "DIVE-EVAL-C003",
55 ContextErrorKind::ForeignContext => "DIVE-EVAL-C004",
56 ContextErrorKind::Structure => "DIVE-EVAL-C005",
57 }
58 }
59 #[must_use]
61 pub fn detail(&self) -> &str {
62 &self.detail
63 }
64}
65impl fmt::Display for ContextError {
66 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
67 write!(f, "{}: {}", self.code(), self.detail)
68 }
69}
70impl std::error::Error for ContextError {}
71impl From<ContextError> for EvalError {
72 fn from(error: ContextError) -> Self {
73 Self::unsupported(format!("invalid evaluator context ({error})"))
74 }
75}
76
77type CResult<T> = Result<T, ContextError>;
78
79pub fn validate_ir(ir: &Arc<dive_ir::Ir>) -> CResult<()> {
95 validate(&mut Model::new(ir.clone()))
96}
97
98fn unknown(what: impl Into<String>) -> ContextError {
99 ContextError::new(ContextErrorKind::UnknownId, what)
100}
101
102#[allow(
103 clippy::too_many_lines,
104 reason = "the ordered admission checks are reviewed together before any interning or callback"
105)]
106pub(crate) fn validate(model: &mut Model) -> CResult<()> {
107 let ir = &model.ir;
108 if ir.modules().get(ir.root().index()).is_none() {
109 return Err(unknown("root module"));
110 }
111 for module in ir.modules() {
112 if module
113 .parent
114 .is_some_and(|p| p.index() >= ir.modules().len())
115 || module
116 .extends
117 .iter()
118 .any(|p| p.index() >= ir.modules().len())
119 || module
120 .assumptions
121 .iter()
122 .chain(&module.theorems)
123 .any(|p| p.index() >= ir.defs().len())
124 || module
125 .tlc_constants
126 .iter()
127 .any(|p| p.index() >= ir.decls().len())
128 || module.context.iter().any(|(_, s)| match s {
129 dive_ir::Symbol::Def(d) => d.index() >= ir.defs().len(),
130 dive_ir::Symbol::Decl(d) => d.index() >= ir.decls().len(),
131 dive_ir::Symbol::Instance => false,
132 })
133 {
134 return Err(unknown("module references"));
135 }
136 }
137 for decl in ir.decls() {
138 if decl.module.index() >= ir.modules().len()
139 || decl.var.is_some_and(|v| v.index() >= ir.vars().len())
140 || decl
141 .constant
142 .is_some_and(|c| c.index() >= ir.consts().len())
143 {
144 return Err(unknown("declaration references"));
145 }
146 }
147 if ir.tlc_var_order().len() != ir.vars().len()
148 || ir
149 .tlc_var_order()
150 .iter()
151 .map(|v| v.index())
152 .collect::<HashSet<_>>()
153 .len()
154 != ir.vars().len()
155 || ir
156 .tlc_var_order()
157 .iter()
158 .any(|v| v.index() >= ir.vars().len())
159 {
160 return Err(ContextError::new(
161 ContextErrorKind::Structure,
162 "TLC variable order",
163 ));
164 }
165 for def in ir.defs() {
166 if def.params.len() > def.frame.len() {
167 return Err(ContextError::new(
168 ContextErrorKind::Arity,
169 "parameters exceed frame slots",
170 ));
171 }
172 let parent = match def.scope {
173 DefScope::TopLevel => None,
174 DefScope::Local { parent }
175 | DefScope::Inline { parent }
176 | DefScope::LetValue { parent, .. } => Some(parent),
177 };
178 if parent.is_some_and(|d| d.index() >= ir.defs().len())
179 || def.source.is_some_and(|d| d.index() >= ir.defs().len())
180 || def.frame.iter().any(|slot| matches!(slot.kind, dive_ir::SlotKind::LetValue(d) if d.index() >= ir.defs().len()))
181 { return Err(unknown("definition frame references")); }
182 if def.recursive && matches!(def.scope, DefScope::Inline { .. }) {
183 return Err(ContextError::new(
184 ContextErrorKind::Structure,
185 "recursive inline frame",
186 ));
187 }
188 }
189 for (i, node) in ir.nodes().iter().enumerate() {
191 if let Expr::Apply { callee, args } = &node.expr {
192 let expected = match callee {
193 OpRef::Def(d) => Some(
194 ir.defs()
195 .get(d.index())
196 .ok_or_else(|| unknown("application definition"))?
197 .params
198 .len(),
199 ),
200 OpRef::Const(c) => Some(
201 ir.consts()
202 .get(c.index())
203 .and_then(|d| ir.decls().get(d.index()))
204 .ok_or_else(|| unknown("application constant"))?
205 .arity as usize,
206 ),
207 OpRef::Subst(d) => Some(
208 ir.decls()
209 .get(d.index())
210 .ok_or_else(|| unknown("application substitution"))?
211 .arity as usize,
212 ),
213 _ => None,
214 };
215 if expected.is_some_and(|n| n != args.len()) {
216 return Err(ContextError::new(
217 ContextErrorKind::Arity,
218 "IR application argument count",
219 ));
220 }
221 }
222 if node
223 .expr
224 .try_for_each_child(|e| if e.index() >= i { Err(()) } else { Ok(()) })
225 .is_err()
226 {
227 return Err(ContextError::new(
228 ContextErrorKind::Structure,
229 "expression child is not older than its parent",
230 ));
231 }
232 }
233 let mut parents = vec![false; ir.nodes().len()];
236 let mut claim = |expr: ExprId| -> CResult<()> {
237 let parent = parents
238 .get_mut(expr.index())
239 .ok_or_else(|| unknown("expression body or child"))?;
240 if std::mem::replace(parent, true) {
241 return Err(ContextError::new(
242 ContextErrorKind::Structure,
243 "expression has multiple parents",
244 ));
245 }
246 Ok(())
247 };
248 for def in ir.defs() {
249 claim(def.body)?;
250 }
251 for node in ir.nodes() {
252 node.expr.try_for_each_child(&mut claim)?;
253 }
254 frame_expansion(ir)?;
255 let (owners, _) = frame_metadata(ir);
256 for (i, node) in ir.nodes().iter().enumerate() {
257 let frame = ir
258 .defs()
259 .get(owners[i].index())
260 .ok_or_else(|| unknown("expression frame"))?;
261 let bounds: &[dive_ir::Bound] = match &node.expr {
262 Expr::Quant { bounds, .. }
263 | Expr::SetMap { bounds, .. }
264 | Expr::FcnCons { bounds, .. }
265 | Expr::RecFcn { bounds, .. } => bounds,
266 Expr::SetFilter { bound, .. } => std::slice::from_ref(bound),
267 _ => &[],
268 };
269 if bounds
270 .iter()
271 .flat_map(|b| b.vars.iter())
272 .any(|s| s.index() >= frame.frame.len())
273 || matches!(&node.expr, Expr::TemporalQuant { vars, .. } if vars.iter().any(|s| s.index() >= frame.frame.len()))
274 || matches!(&node.expr, Expr::RecFcn { name, .. } if name.index() >= frame.frame.len())
275 {
276 return Err(unknown("binder frame slot"));
277 }
278 }
279 let violations = dive_ir::validate::check(ir);
280 if let Some(first) = violations.first() {
281 return Err(ContextError::new(ContextErrorKind::Structure, first));
282 }
283 if model.constants.len() != ir.consts().len() {
284 return Err(ContextError::new(
285 ContextErrorKind::Structure,
286 "constant binding table length",
287 ));
288 }
289 for (&source, &target) in &model.redirects {
290 let a = ir
291 .defs()
292 .get(source.index())
293 .ok_or_else(|| unknown("redirect source"))?;
294 let b = ir
295 .defs()
296 .get(target.index())
297 .ok_or_else(|| unknown("redirect target"))?;
298 if a.params
299 .iter()
300 .map(|p| p.arity)
301 .ne(b.params.iter().map(|p| p.arity))
302 {
303 return Err(ContextError::new(
304 ContextErrorKind::Arity,
305 "redirect signature",
306 ));
307 }
308 }
309 let mut normalized = std::collections::HashMap::new();
310 for &source in model.redirects.keys() {
311 let mut seen = HashSet::new();
312 let mut target = source;
313 while let Some(&next) = model.redirects.get(&target) {
314 if next == target {
315 break;
316 }
317 if !seen.insert(target) {
318 return Err(ContextError::new(
319 ContextErrorKind::RedirectCycle,
320 "definition redirect cycle",
321 ));
322 }
323 target = next;
324 }
325 normalized.insert(source, target);
326 }
327 for (i, binding) in model.constants.iter().enumerate() {
328 match binding {
329 Some(ConstBinding::Def(d)) => {
330 let def = ir
331 .defs()
332 .get(d.index())
333 .ok_or_else(|| unknown("constant definition binding"))?;
334 if def.params.len() != ir.decl(ir.consts()[i]).arity as usize {
335 return Err(ContextError::new(
336 ContextErrorKind::Arity,
337 "constant definition arity",
338 ));
339 }
340 }
341 Some(ConstBinding::Value(_)) if ir.decl(ir.consts()[i]).arity != 0 => {
342 return Err(ContextError::new(
343 ContextErrorKind::Arity,
344 "parameterized constant bound to a value",
345 ));
346 }
347 Some(ConstBinding::Value(_)) | None => {}
348 }
349 }
350 for &d in model.def_values.keys() {
351 let def = ir
352 .defs()
353 .get(d.index())
354 .ok_or_else(|| unknown("definition value binding"))?;
355 if !def.params.is_empty() {
356 return Err(ContextError::new(
357 ContextErrorKind::Arity,
358 "parameterized definition bound to a value",
359 ));
360 }
361 }
362 model.redirects = normalized;
363 Ok(())
364}
365
366impl Evaluator {
367 pub(crate) fn admit_def(&self, d: DefId) -> crate::Result<&dive_ir::Def> {
368 self.core
369 .ir
370 .defs()
371 .get(d.index())
372 .ok_or_else(|| unknown("definition ID").into())
373 }
374 pub(crate) fn admit_expr(&self, e: ExprId) -> crate::Result<()> {
375 if self.core.ir.nodes().get(e.index()).is_none() {
376 return Err(unknown("expression ID").into());
377 }
378 Ok(())
379 }
380 pub fn validate_scope(&self, scope: &Scope) -> crate::Result<()> {
385 if !Arc::ptr_eq(&self.core.ir, &scope.owner)
386 || !Arc::ptr_eq(&self.core.names, &scope.names)
387 || !std::sync::Weak::ptr_eq(&scope.context, &Arc::downgrade(&self.core))
388 {
389 return Err(ContextError::new(
390 ContextErrorKind::ForeignContext,
391 "scope belongs to another evaluator",
392 )
393 .into());
394 }
395 Ok(())
396 }
397 pub(crate) fn admit_parent(
398 &self,
399 scope: &Scope,
400 def: DefId,
401 ) -> crate::Result<Option<Arc<crate::env::Frame>>> {
402 let d = self.admit_def(def)?;
403 let (parent, depth) = match d.scope {
404 DefScope::TopLevel => return Ok(None),
405 DefScope::Local { parent } | DefScope::Inline { parent } => {
406 (parent, d.depth.saturating_sub(1))
407 }
408 DefScope::LetValue { parent, .. } => (parent, d.depth),
409 };
410 let frame = scope
411 .env
412 .frame_at_depth(depth)
413 .filter(|f| f.def == parent)
414 .ok_or_else(|| {
415 ContextError::new(
416 ContextErrorKind::Structure,
417 "missing or incompatible enclosing frame",
418 )
419 })?;
420 Ok(Some(frame.clone()))
421 }
422 pub(crate) fn admit_args(&self, scope: &Scope, def: DefId, args: &[Arg]) -> crate::Result<()> {
423 self.validate_scope(scope)?;
424 let d = self.admit_def(def)?;
425 if args.len() != d.params.len() {
426 return Err(
427 ContextError::new(ContextErrorKind::Arity, "operator argument count").into(),
428 );
429 }
430 for (arg, param) in args.iter().zip(&d.params) {
431 let arity = match arg {
432 Arg::Expr { expr, .. } => {
433 self.admit_scoped_expr(scope, *expr)?;
434 0
435 }
436 Arg::Op { op, .. } => match op {
437 OpRef::Def(d) => {
438 self.admit_parent(scope, *d)?;
439 self.admit_def(*d)?.params.len()
440 }
441 OpRef::Const(c) => {
442 self.core
443 .ir
444 .consts()
445 .get(c.index())
446 .and_then(|d| self.core.ir.decls().get(d.index()))
447 .ok_or_else(|| unknown("operator constant"))?
448 .arity as usize
449 }
450 OpRef::Subst(d) => {
451 self.core
452 .ir
453 .decls()
454 .get(d.index())
455 .ok_or_else(|| unknown("substituted operator"))?
456 .arity as usize
457 }
458 OpRef::Param(r) => {
459 let frame = scope
460 .env
461 .frame_up(r.up)
462 .ok_or_else(|| unknown("operator parameter frame"))?;
463 let owner = self.admit_def(frame.def)?;
464 if !matches!(frame.slots.get(r.slot.index()), Some(crate::env::Sv::Op(_))) {
465 return Err(ContextError::new(
466 ContextErrorKind::Structure,
467 "operator parameter is not bound to an operator",
468 )
469 .into());
470 }
471 owner
472 .params
473 .get(r.slot.index())
474 .ok_or_else(|| unknown("operator parameter slot"))?
475 .arity as usize
476 }
477 OpRef::Std(op) => usize::try_from(op.java_arity()).map_err(|_| {
478 ContextError::new(
479 ContextErrorKind::Arity,
480 "variadic standard operator argument",
481 )
482 })?,
483 OpRef::Builtin(op) => {
484 use dive_ir::BuiltinOp::{
485 Always, BigUnion, Boolean, Domain, Enabled, Eventually, Not, PowerSet,
486 Prime, String, Unchanged,
487 };
488 match op {
489 Boolean | String => 0,
490 PowerSet | BigUnion | Domain | Not | Prime | Enabled | Unchanged
491 | Always | Eventually => 1,
492 _ => 2,
493 }
494 }
495 OpRef::Unbound(_) => {
496 return Err(ContextError::new(
497 ContextErrorKind::UnknownId,
498 "unbound operator argument",
499 )
500 .into());
501 }
502 },
503 };
504 if arity != param.arity as usize {
505 return Err(ContextError::new(
506 ContextErrorKind::Arity,
507 "operator argument signature",
508 )
509 .into());
510 }
511 }
512 Ok(())
513 }
514}
515
516fn frame_expansion(ir: &dive_ir::Ir) -> CResult<()> {
517 let mut incoming = vec![0_usize; ir.defs().len()];
518 let mut edges = vec![Vec::new(); ir.defs().len()];
519 for (i, def) in ir.defs().iter().enumerate() {
520 let mut work = vec![def.body];
521 while let Some(e) = work.pop() {
522 let node = ir
523 .nodes()
524 .get(e.index())
525 .ok_or_else(|| unknown("definition body"))?;
526 let mut add = |d: DefId| -> CResult<()> {
527 let count = incoming
528 .get_mut(d.index())
529 .ok_or_else(|| unknown("frame expansion definition"))?;
530 *count += 1;
531 edges[i].push(d.index());
532 Ok(())
533 };
534 if let Expr::Let { defs, .. } = &node.expr {
535 for &d in defs {
536 add(d)?;
537 }
538 }
539 let inline = |d: DefId| {
540 ir.defs()
541 .get(d.index())
542 .is_some_and(|d| matches!(d.scope, DefScope::Inline { .. }))
543 };
544 if let Expr::Def(d) = &node.expr
545 && inline(*d)
546 {
547 add(*d)?;
548 }
549 for op in node.expr.op_refs() {
550 if let OpRef::Def(d) = op
551 && inline(*d)
552 {
553 add(*d)?;
554 }
555 }
556 node.expr.for_each_child(|child| work.push(child));
557 }
558 }
559 let mut ready: Vec<_> = incoming
560 .iter()
561 .enumerate()
562 .filter_map(|(i, &n)| (n == 0).then_some(i))
563 .collect();
564 let mut count = 0;
565 while let Some(i) = ready.pop() {
566 count += 1;
567 for &to in &edges[i] {
568 incoming[to] -= 1;
569 if incoming[to] == 0 {
570 ready.push(to);
571 }
572 }
573 }
574 if count != incoming.len() {
575 return Err(ContextError::new(
576 ContextErrorKind::Structure,
577 "cyclic lexical frame expansion",
578 ));
579 }
580 Ok(())
581}
582
583pub(crate) fn frame_metadata(ir: &dive_ir::Ir) -> (Vec<DefId>, Vec<bool>) {
584 let mut owners = vec![DefId(0); ir.nodes().len()];
585 for (i, def) in ir.defs().iter().enumerate() {
586 let mut owner = DefId(u32::try_from(i).unwrap_or(u32::MAX));
587 for _ in 0..ir.defs().len() {
588 match ir.defs().get(owner.index()).map(|d| d.scope) {
589 Some(DefScope::LetValue { parent, .. }) if parent != owner => owner = parent,
590 _ => break,
591 }
592 }
593 let mut work = vec![def.body];
594 while let Some(e) = work.pop() {
595 if let Some(o) = owners.get_mut(e.index()) {
596 *o = owner;
597 }
598 if let Some(node) = ir.nodes().get(e.index()) {
599 node.expr.for_each_child(|child| work.push(child));
600 }
601 }
602 }
603 let mut required = vec![false; ir.nodes().len()];
604 for (i, node) in ir.nodes().iter().enumerate() {
605 let local_def = |d: DefId| {
606 ir.defs()
607 .get(d.index())
608 .is_some_and(|d| d.scope != DefScope::TopLevel)
609 };
610 let local = matches!(
611 node.expr,
612 Expr::Local(_)
613 | Expr::Let { .. }
614 | Expr::Quant { .. }
615 | Expr::SetFilter { .. }
616 | Expr::SetMap { .. }
617 | Expr::FcnCons { .. }
618 | Expr::RecFcn { .. }
619 | Expr::TemporalQuant { .. }
620 ) || matches!(node.expr, Expr::Def(d) if local_def(d))
621 || node.expr.op_refs().iter().any(|op| {
622 matches!(op, OpRef::Param(_)) || matches!(op, OpRef::Def(d) if local_def(*d))
623 });
624 required[i] = local
625 || node
626 .expr
627 .try_for_each_child(|e| {
628 if required.get(e.index()).copied().unwrap_or(true) {
629 Err(())
630 } else {
631 Ok(())
632 }
633 })
634 .is_err();
635 }
636 (owners, required)
637}
638
639impl Evaluator {
640 #[must_use]
652 pub fn admits_scoped_expr(&self, scope: &Scope, expr: ExprId) -> bool {
653 self.admit_scoped_expr(scope, expr).is_ok()
654 }
655
656 pub(crate) fn admit_scoped_expr(&self, scope: &Scope, expr: ExprId) -> crate::Result<()> {
657 self.validate_scope(scope)?;
658 self.admit_expr(expr)?;
659 if self.core.frame_required[expr.index()]
660 && scope.def() != self.core.frame_owners[expr.index()]
661 {
662 return Err(ContextError::new(
663 ContextErrorKind::Structure,
664 "expression requires another lexical frame",
665 )
666 .into());
667 }
668 Ok(())
669 }
670}
671
672impl Evaluator {
673 pub fn validate_model_context(
680 &self,
681 ir: &Arc<dive_ir::Ir>,
682 names: &Arc<Interner>,
683 ) -> CResult<()> {
684 if !Arc::ptr_eq(ir, &self.core.ir) || !Arc::ptr_eq(names, &self.core.names) {
685 return Err(ContextError::new(
686 ContextErrorKind::ForeignContext,
687 "model metadata belongs to another evaluator context",
688 ));
689 }
690 Ok(())
691 }
692 pub fn validate_predicate(&self, scope: &Scope, expr: ExprId) -> crate::Result<()> {
698 self.admit_scoped_expr(scope, expr)
699 }
700}