1use std::collections::HashSet;
4use std::sync::{Arc, Weak};
5
6use dive_ir::{Arg, DefId, Expr, ExprId, OpRef, StdKind, StdOp, StdSupport};
7use dive_value::{Fcn, Set, SetKind, Value};
8
9use crate::core::Core;
10use crate::env::{Env, Ev, Frame, OpVal, StateRef, SubstLink, Sv, Thunk};
11use crate::{ConstBinding, EvalError, Evaluator, HostControl, Result, Scope};
12
13mod scalar_callbacks;
14#[cfg(test)]
15mod tests;
16
17#[derive(Clone)]
24pub struct TupleConcatSources {
25 owner: Weak<Core>,
26}
27
28impl std::fmt::Debug for TupleConcatSources {
29 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
30 f.debug_struct("TupleConcatSources").finish_non_exhaustive()
31 }
32}
33
34impl TupleConcatSources {
35 #[must_use]
37 pub fn belongs_to(&self, evaluator: &Evaluator) -> bool {
38 self.owner.ptr_eq(&Arc::downgrade(&evaluator.core))
39 }
40}
41
42fn reserve<T>(values: &mut Vec<T>, count: usize) -> Result<()> {
43 values
44 .try_reserve(count)
45 .map_err(|_| EvalError::resource_limit("tuple name analysis allocation"))
46}
47
48fn push<T>(values: &mut Vec<T>, value: T) -> Result<()> {
49 reserve(values, 1)?;
50 values.push(value);
51 Ok(())
52}
53
54impl Evaluator {
55 pub fn tuple_concat_sources(
79 &self,
80 roots: &[(ExprId, Scope)],
81 definitions: &[DefId],
82 control: Option<&dyn HostControl>,
83 ) -> Result<Option<TupleConcatSources>> {
84 let mut analysis = Analysis {
85 ev: self,
86 control,
87 blocked: Vec::new(),
88 };
89 analysis.poll()?;
90 for binding in self.core.consts.iter().flatten() {
93 analysis.poll()?;
94 if let ConstBinding::Def(def) = binding
95 && let Some(op) = self.core.ir.def(self.redirected(*def)).std
96 {
97 push(&mut analysis.blocked, op)?;
98 }
99 }
100 for (index, def) in self.core.ir.defs().iter().enumerate() {
101 analysis.poll()?;
102 let id = DefId(
103 u32::try_from(index)
104 .map_err(|_| EvalError::resource_limit("tuple name definition index"))?,
105 );
106 if let Some(op) = def.std
107 && (self.redirected(id) != id || self.is_value_override(id))
108 {
109 push(&mut analysis.blocked, op)?;
110 }
111 }
112 let Some(mut sources) = analysis.captures(roots)? else {
113 return Ok(None);
114 };
115 for &def in definitions {
116 analysis.poll()?;
117 let Some(body) = analysis.user_body(def, 0) else {
118 return Ok(None);
119 };
120 push(&mut sources.exprs, body)?;
121 }
122 let Some(callbacks) = analysis.closed_scalar_callbacks(&sources)? else {
123 return Ok(None);
124 };
125 let tuples = analysis.results()?;
126 if !analysis.calls(&sources.exprs, &tuples, callbacks)? {
127 return Ok(None);
128 }
129 analysis.poll()?;
130 Ok(Some(TupleConcatSources {
131 owner: Arc::downgrade(&self.core),
132 }))
133 }
134}
135
136struct Analysis<'a> {
137 ev: &'a Evaluator,
138 control: Option<&'a dyn HostControl>,
139 blocked: Vec<StdOp>,
140}
141
142impl Analysis<'_> {
143 fn poll(&self) -> Result<()> {
144 if let Some(control) = self.control {
145 control.check().map_err(EvalError::interrupted)
146 } else {
147 self.ev.core.host.check_control()
148 }
149 }
150
151 fn native(&self, op: &OpRef, arity: usize) -> Option<StdOp> {
152 let op = match op {
153 OpRef::Std(op) => *op,
154 OpRef::Def(def) => {
155 let target = self.ev.ir().defs().get(def.index())?;
156 if self.ev.redirected(*def) != *def
157 || self.ev.is_value_override(*def)
158 || target.params.len() != arity
159 || target.params.iter().any(|p| p.arity != 0)
160 {
161 return None;
162 }
163 target.std?
164 }
165 _ => return None,
166 };
167 (op.kind() == StdKind::Value
168 && op.support() == StdSupport::Core
169 && usize::try_from(op.java_arity()).ok() == Some(arity)
170 && !self.blocked.contains(&op)
171 && !self.ev.core.std_redirects.contains_key(&op))
172 .then_some(op)
173 }
174
175 fn user_body(&self, def: DefId, arity: usize) -> Option<ExprId> {
176 let target = self.ev.ir().defs().get(def.index())?;
177 (target.std.is_none()
178 && self.ev.redirected(def) == def
179 && !self.ev.is_value_override(def)
180 && target.params.len() == arity
181 && target.params.iter().all(|p| p.arity == 0))
182 .then_some(target.body)
183 }
184
185 fn result_edges(&self, expr: &Expr, edges: &mut Vec<ExprId>) -> Result<()> {
188 match expr {
189 Expr::If { then, other, .. } => {
190 push(edges, *then)?;
191 push(edges, *other)?;
192 }
193 Expr::Case { arms, other } => {
194 for arm in arms {
195 push(edges, arm.value)?;
196 }
197 if let Some(other) = other {
198 push(edges, *other)?;
199 }
200 }
201 Expr::Label { body, .. }
202 | Expr::Selected(body)
203 | Expr::Let { body, .. }
204 | Expr::Subst { body, .. } => push(edges, *body)?,
205 Expr::Def(def) => {
206 if let Some(body) = self.user_body(*def, 0) {
207 push(edges, body)?;
208 }
209 }
210 Expr::Apply { callee, args } if args.iter().all(|a| matches!(a, Arg::Expr { .. })) => {
211 match self.native(callee, args.len()) {
212 Some(StdOp::SequencesConcat) => {
213 for arg in args {
214 if let Arg::Expr { expr, .. } = arg {
215 push(edges, *expr)?;
216 }
217 }
218 }
219 Some(_) => {}
220 None => {
221 if let OpRef::Def(def) = callee
222 && let Some(body) = self.user_body(*def, args.len())
223 {
224 push(edges, body)?;
225 }
226 }
227 }
228 }
229 _ => {}
230 }
231 Ok(())
232 }
233
234 fn results(&self) -> Result<Vec<bool>> {
235 let count = self.ev.ir().nodes().len();
236 let mut users = Vec::new();
237 reserve(&mut users, count)?;
238 users.resize_with(count, Vec::new);
239 let mut tuples = Vec::new();
240 reserve(&mut tuples, count)?;
241 tuples.resize(count, false);
242 let mut work = Vec::new();
243 for (index, node) in self.ev.ir().nodes().iter().enumerate() {
244 self.poll()?;
245 let id = ExprId(
246 u32::try_from(index)
247 .map_err(|_| EvalError::resource_limit("tuple name expression index"))?,
248 );
249 let mut edges = Vec::new();
250 self.result_edges(&node.expr, &mut edges)?;
251 for edge in edges {
252 let Some(dependents) = users.get_mut(edge.index()) else {
253 return Err(EvalError::bug("tuple name result dependency"));
254 };
255 push(dependents, id)?;
256 }
257 push(&mut work, id)?;
258 }
259 while let Some(id) = work.pop() {
260 self.poll()?;
261 if tuples[id.index()] {
262 continue;
263 }
264 let expr = self.ev.ir().expr(id);
265 let mut edges = Vec::new();
266 self.result_edges(expr, &mut edges)?;
267 let grounded = matches!(expr, Expr::Tuple(_))
268 || matches!(expr, Expr::Apply { callee, args }
269 if args.iter().all(|a| matches!(a, Arg::Expr { .. }))
270 && self.native(callee, args.len()) == Some(StdOp::SequencesAppend));
271 let proved = if matches!(expr, Expr::Apply { callee, args }
272 if self.native(callee, args.len()) == Some(StdOp::SequencesConcat))
273 {
274 edges.iter().any(|e| tuples[e.index()])
275 } else {
276 !edges.is_empty() && edges.iter().all(|e| tuples[e.index()])
277 };
278 if grounded || proved {
279 tuples[id.index()] = true;
280 for &user in &users[id.index()] {
281 push(&mut work, user)?;
282 }
283 }
284 }
285 Ok(tuples)
286 }
287
288 fn calls(&self, sources: &[ExprId], tuples: &[bool], callbacks: bool) -> Result<bool> {
289 let mut contexts = Vec::new();
290 push(&mut contexts, Lexical::default())?;
291 let mut seen = HashSet::new();
292 let mut work = Vec::new();
293 for &source in sources {
294 push(&mut work, (source, 0))?;
295 }
296 while let Some((id, context)) = work.pop() {
297 self.poll()?;
298 if seen.contains(&(id, context)) {
299 continue;
300 }
301 seen.try_reserve(1)
302 .map_err(|_| EvalError::resource_limit("tuple name call contexts allocation"))?;
303 seen.insert((id, context));
304 let Some(node) = self.ev.ir().nodes().get(id.index()) else {
305 return Ok(false);
306 };
307 match &node.expr {
308 Expr::Apply { callee, args } => {
309 if !self.call(
310 callee,
311 args,
312 tuples,
313 &contexts[context],
314 &mut work,
315 callbacks,
316 )? {
317 return Ok(false);
318 }
319 }
320 Expr::Def(def) if self.stored_value_leaf(*def) => {
321 }
324 Expr::Def(def) => {
325 if let Some(op) = self.native(&OpRef::Def(*def), 0) {
326 if op.creates_runtime_names() {
327 return Ok(false);
328 }
329 } else if let Some(body) = self.user_body(*def, 0) {
330 push(&mut work, (body, 0))?;
331 } else {
332 return Ok(false);
333 }
334 }
335 Expr::Let { defs, body } => {
336 let context = self.enter_let(defs, &contexts[context], tuples)?;
337 let next = if let Some(index) = contexts.iter().position(|old| *old == context)
338 {
339 index
340 } else {
341 let index = contexts.len();
342 push(&mut contexts, context)?;
343 index
344 };
345 push(&mut work, (*body, next))?;
346 for def in defs {
347 push(&mut work, (self.ev.ir().def(*def).body, 0))?;
348 }
349 continue;
350 }
351 _ => {}
352 }
353 let context = if matches!(
356 node.expr,
357 Expr::Quant { .. }
358 | Expr::SetFilter { .. }
359 | Expr::SetMap { .. }
360 | Expr::FcnCons { .. }
361 | Expr::RecFcn { .. }
362 | Expr::TemporalQuant { .. }
363 | Expr::Subst { .. }
364 | Expr::Except { .. }
365 | Expr::Prime(_)
366 | Expr::Enabled(_)
367 ) {
368 0
369 } else {
370 context
371 };
372 node.expr
373 .try_for_each_child(|child| push(&mut work, (child, context)))?;
374 }
375 Ok(true)
376 }
377
378 fn stored_value_leaf(&self, def: DefId) -> bool {
379 let Some(target) = self.ev.ir().defs().get(def.index()) else {
380 return false;
381 };
382 target.params.is_empty()
383 && target.std.is_none()
384 && self.ev.redirected(def) == def
385 && self.ev.core.def_values.contains_key(&def)
386 }
387
388 fn call(
389 &self,
390 callee: &OpRef,
391 args: &[Arg],
392 tuples: &[bool],
393 context: &Lexical,
394 work: &mut Vec<(ExprId, usize)>,
395 callbacks: bool,
396 ) -> Result<bool> {
397 if !callbacks && args.iter().any(|a| matches!(a, Arg::Op { .. })) {
398 return Ok(false);
399 }
400 if let Some(op) = self.native(callee, args.len()) {
401 if op.creates_runtime_names() && op != StdOp::SequencesConcat {
402 return Ok(false);
403 }
404 if op == StdOp::SequencesConcat
405 && !args.iter().any(|a| {
406 matches!(a, Arg::Expr { expr, .. }
407 if tuples[expr.index()] || self.local_tuple(*expr, context))
408 })
409 {
410 return Ok(false);
411 }
412 } else if callbacks
413 && args.len() == 2
414 && matches!(callee, OpRef::Param(_) | OpRef::Subst(_))
415 {
416 } else if let OpRef::Def(def) = callee
419 && let Some(body) = self.call_body(*def, args)
420 {
421 push(work, (body, 0))?;
424 } else {
425 return Ok(false);
426 }
427 Ok(true)
428 }
429
430 fn enter_let(&self, defs: &[DefId], old: &Lexical, tuples: &[bool]) -> Result<Lexical> {
431 let mut context = Lexical {
432 frame: old.frame,
433 slots: Vec::new(),
434 };
435 reserve(&mut context.slots, old.slots.len())?;
436 context.slots.extend_from_slice(&old.slots);
437 for &def in defs {
438 self.poll()?;
439 let definition = self.ev.ir().def(def);
440 let dive_ir::DefScope::LetValue { parent, slot, .. } = definition.scope else {
441 continue;
442 };
443 if context.frame != Some(parent) {
447 context.slots.clear();
448 context.frame = Some(parent);
449 }
450 context.slots.retain(|(bound, _)| *bound != slot);
451 let valid = self
452 .ev
453 .ir()
454 .def(parent)
455 .frame
456 .get(slot.index())
457 .is_some_and(|info| info.kind == dive_ir::SlotKind::LetValue(def));
458 if valid
459 && self.user_body(def, 0) == Some(definition.body)
460 && tuples[definition.body.index()]
461 {
462 push(&mut context.slots, (slot, def))?;
463 }
464 }
465 context.slots.sort_unstable();
466 Ok(context)
467 }
468
469 fn local_tuple(&self, expr: ExprId, context: &Lexical) -> bool {
470 let Expr::Local(local) = self.ev.ir().expr(expr) else {
471 return false;
472 };
473 local.up == 0
474 && context.slots.iter().any(|(slot, def)| {
475 *slot == local.slot
476 && matches!(self.ev.ir().def(*def).scope,
477 dive_ir::DefScope::LetValue { parent, slot: bound, .. }
478 if Some(parent) == context.frame && bound == local.slot)
479 })
480 }
481}
482
483#[derive(Default, PartialEq, Eq)]
486struct Lexical {
487 frame: Option<DefId>,
488 slots: Vec<(dive_ir::Slot, DefId)>,
489}
490
491struct Sources {
492 exprs: Vec<ExprId>,
493 scalar_callbacks: bool,
494}
495
496enum Capture {
497 Environment(Env),
498 Slot(Sv),
499 Value(Value),
500 State(StateRef),
501}
502
503#[derive(Default)]
504struct Retained {
505 frames: Vec<Arc<Frame>>,
506 links: Vec<Arc<SubstLink>>,
507 functions: Vec<Fcn>,
508 sets: Vec<Set>,
509 thunks: Vec<Arc<Thunk>>,
510 states: Vec<Arc<[Option<Value>]>>,
511 scalar_callbacks: bool,
512}
513
514impl Analysis<'_> {
515 fn captures(&self, roots: &[(ExprId, Scope)]) -> Result<Option<Sources>> {
516 let mut work = Vec::new();
517 let mut sources = Vec::new();
518 let mut retained = Retained::default();
519 for (expr, scope) in roots {
520 self.poll()?;
521 if !Arc::ptr_eq(&scope.owner, &self.ev.core.ir)
522 || !Arc::ptr_eq(&scope.names, &self.ev.core.names)
523 || !scope.context.ptr_eq(&Arc::downgrade(&self.ev.core))
524 {
525 return Ok(None);
526 }
527 push(&mut sources, *expr)?;
528 if let Some(wrapper) = scope.wrapper {
529 push(&mut sources, wrapper)?;
530 }
531 push(&mut work, Capture::Environment(scope.env.clone()))?;
532 }
533 for value in self.ev.core.def_values.values() {
534 push(&mut work, Capture::Value(value.clone()))?;
535 }
536 for value in self.ev.core.startup.iter().chain(&self.ev.core.def_cache) {
537 if let Some(value) = value.get() {
538 push(&mut work, Capture::Value(value.clone()))?;
539 }
540 }
541 for binding in self.ev.core.consts.iter().flatten() {
542 if let ConstBinding::Value(value) = binding {
543 push(&mut work, Capture::Value(value.clone()))?;
544 }
545 }
546 while let Some(task) = work.pop() {
547 self.poll()?;
548 let known = match task {
549 Capture::Environment(env) => {
550 self.capture_environment(env, &mut work, &mut retained)?
551 }
552 Capture::Slot(slot) => {
553 self.capture_slot(slot, &mut work, &mut sources, &mut retained)?
554 }
555 Capture::Value(value) => self.capture_value(value, &mut work, &mut retained)?,
556 Capture::State(StateRef::Null | StateRef::Empty) => true,
557 Capture::State(StateRef::Vals(values)) => {
558 if !retained
559 .states
560 .iter()
561 .any(|prior| Arc::ptr_eq(prior, &values))
562 {
563 push(&mut retained.states, values.clone())?;
564 for value in values.iter().flatten() {
565 push(&mut work, Capture::Value(value.clone()))?;
566 }
567 }
568 true
569 }
570 Capture::State(StateRef::Named(_)) => false,
571 };
572 if !known {
573 return Ok(None);
574 }
575 }
576 Ok(Some(Sources {
577 exprs: sources,
578 scalar_callbacks: retained.scalar_callbacks,
579 }))
580 }
581
582 fn capture_environment(
583 &self,
584 env: Env,
585 work: &mut Vec<Capture>,
586 retained: &mut Retained,
587 ) -> Result<bool> {
588 if env.dynamic.at.is_some() || env.dynamic.cut.is_some() {
589 return Ok(false);
590 }
591 let mut link = env.dynamic.subst.clone();
592 while let Some(current) = link.take() {
593 self.poll()?;
594 if retained
595 .links
596 .iter()
597 .any(|prior| Arc::ptr_eq(prior, ¤t))
598 {
599 break;
600 }
601 push(&mut retained.links, current.clone())?;
602 push(work, Capture::Slot(current.val.clone()))?;
603 link.clone_from(¤t.next);
604 }
605 let mut frame = Some(env.frame);
606 while let Some(current) = frame.take() {
607 self.poll()?;
608 if retained
609 .frames
610 .iter()
611 .any(|prior| Arc::ptr_eq(prior, ¤t))
612 {
613 break;
614 }
615 push(&mut retained.frames, current.clone())?;
616 let Some(definition) = self.ev.ir().defs().get(current.def.index()) else {
617 return Ok(false);
618 };
619 for (index, slot) in current.slots.iter().enumerate() {
620 if definition.params.get(index).is_some_and(|p| p.arity != 0)
621 && !matches!(slot, Sv::Op(_))
622 {
623 return Ok(false); }
625 push(work, Capture::Slot(slot.clone()))?;
626 }
627 frame.clone_from(¤t.parent);
628 }
629 Ok(true)
630 }
631
632 fn capture_slot(
633 &self,
634 slot: Sv,
635 work: &mut Vec<Capture>,
636 sources: &mut Vec<ExprId>,
637 retained: &mut Retained,
638 ) -> Result<bool> {
639 self.poll()?;
640 match slot {
641 Sv::Thunk(thunk) => {
642 if retained
643 .thunks
644 .iter()
645 .any(|prior| Arc::ptr_eq(prior, &thunk))
646 {
647 return Ok(true);
648 }
649 push(&mut retained.thunks, thunk.clone())?;
650 push(sources, thunk.expr)?;
651 push(work, Capture::Environment(thunk.env.clone()))?;
652 for cache in thunk.stored_caches().into_iter().flatten() {
653 let (Ev::V(value), before, after) = cache else {
654 return Ok(false);
655 };
656 push(work, Capture::Value(value))?;
657 push(work, Capture::State(before))?;
658 push(work, Capture::State(after))?;
659 }
660 }
661 Sv::Val(value) => push(work, Capture::Value(value))?,
662 Sv::Unset | Sv::AnalysisBound | Sv::AnalysisConstant => {}
663 Sv::Op(op) if self.scalar_operator(&op) => retained.scalar_callbacks = true,
664 Sv::Fcn(_) | Sv::Op(_) => return Ok(false),
665 }
666 Ok(true)
667 }
668
669 fn capture_value(
670 &self,
671 value: Value,
672 work: &mut Vec<Capture>,
673 retained: &mut Retained,
674 ) -> Result<bool> {
675 match value {
676 Value::Fcn(function) => {
677 if retained
678 .functions
679 .iter()
680 .any(|prior| prior.ptr_eq(&function))
681 {
682 return Ok(true);
683 }
684 push(&mut retained.functions, function.clone())?;
685 for (key, value) in function.iter() {
686 self.poll()?;
687 push(work, Capture::Value(key))?;
688 push(work, Capture::Value(value.clone()))?;
689 }
690 }
691 Value::Set(set) => {
692 if !matches!(
695 set.kind(),
696 SetKind::Raw
697 | SetKind::Enum
698 | SetKind::Interval
699 | SetKind::Nat
700 | SetKind::Int
701 | SetKind::Strings
702 ) {
703 return Ok(false);
704 }
705 if retained.sets.iter().any(|prior| prior.ptr_eq(&set)) {
706 return Ok(true);
707 }
708 push(&mut retained.sets, set.clone())?;
709 if matches!(set.kind(), SetKind::Raw | SetKind::Enum) {
710 let Some(values) = set.stored_elements() else {
711 return Ok(false);
712 };
713 for value in values {
714 self.poll()?;
715 push(work, Capture::Value(value.clone()))?;
716 }
717 }
718 }
719 _ => {}
720 }
721 Ok(true)
722 }
723}