use std::collections::HashSet;
use std::sync::{Arc, Weak};
use dive_ir::{Arg, DefId, Expr, ExprId, OpRef, StdKind, StdOp, StdSupport};
use dive_value::{Fcn, Set, SetKind, Value};
use crate::core::Core;
use crate::env::{Env, Ev, Frame, OpVal, StateRef, SubstLink, Sv, Thunk};
use crate::{ConstBinding, EvalError, Evaluator, HostControl, Result, Scope};
mod scalar_callbacks;
#[cfg(test)]
mod tests;
#[derive(Clone)]
pub struct TupleConcatSources {
owner: Weak<Core>,
}
impl std::fmt::Debug for TupleConcatSources {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("TupleConcatSources").finish_non_exhaustive()
}
}
impl TupleConcatSources {
#[must_use]
pub fn belongs_to(&self, evaluator: &Evaluator) -> bool {
self.owner.ptr_eq(&Arc::downgrade(&evaluator.core))
}
}
fn reserve<T>(values: &mut Vec<T>, count: usize) -> Result<()> {
values
.try_reserve(count)
.map_err(|_| EvalError::resource_limit("tuple name analysis allocation"))
}
fn push<T>(values: &mut Vec<T>, value: T) -> Result<()> {
reserve(values, 1)?;
values.push(value);
Ok(())
}
impl Evaluator {
pub fn tuple_concat_sources(
&self,
roots: &[(ExprId, Scope)],
definitions: &[DefId],
control: Option<&dyn HostControl>,
) -> Result<Option<TupleConcatSources>> {
let mut analysis = Analysis {
ev: self,
control,
blocked: Vec::new(),
};
analysis.poll()?;
for binding in self.core.consts.iter().flatten() {
analysis.poll()?;
if let ConstBinding::Def(def) = binding
&& let Some(op) = self.core.ir.def(self.redirected(*def)).std
{
push(&mut analysis.blocked, op)?;
}
}
for (index, def) in self.core.ir.defs().iter().enumerate() {
analysis.poll()?;
let id = DefId(
u32::try_from(index)
.map_err(|_| EvalError::resource_limit("tuple name definition index"))?,
);
if let Some(op) = def.std
&& (self.redirected(id) != id || self.is_value_override(id))
{
push(&mut analysis.blocked, op)?;
}
}
let Some(mut sources) = analysis.captures(roots)? else {
return Ok(None);
};
for &def in definitions {
analysis.poll()?;
let Some(body) = analysis.user_body(def, 0) else {
return Ok(None);
};
push(&mut sources.exprs, body)?;
}
let Some(callbacks) = analysis.closed_scalar_callbacks(&sources)? else {
return Ok(None);
};
let tuples = analysis.results()?;
if !analysis.calls(&sources.exprs, &tuples, callbacks)? {
return Ok(None);
}
analysis.poll()?;
Ok(Some(TupleConcatSources {
owner: Arc::downgrade(&self.core),
}))
}
}
struct Analysis<'a> {
ev: &'a Evaluator,
control: Option<&'a dyn HostControl>,
blocked: Vec<StdOp>,
}
impl Analysis<'_> {
fn poll(&self) -> Result<()> {
if let Some(control) = self.control {
control.check().map_err(EvalError::interrupted)
} else {
self.ev.core.host.check_control()
}
}
fn native(&self, op: &OpRef, arity: usize) -> Option<StdOp> {
let op = match op {
OpRef::Std(op) => *op,
OpRef::Def(def) => {
let target = self.ev.ir().defs().get(def.index())?;
if self.ev.redirected(*def) != *def
|| self.ev.is_value_override(*def)
|| target.params.len() != arity
|| target.params.iter().any(|p| p.arity != 0)
{
return None;
}
target.std?
}
_ => return None,
};
(op.kind() == StdKind::Value
&& op.support() == StdSupport::Core
&& usize::try_from(op.java_arity()).ok() == Some(arity)
&& !self.blocked.contains(&op)
&& !self.ev.core.std_redirects.contains_key(&op))
.then_some(op)
}
fn user_body(&self, def: DefId, arity: usize) -> Option<ExprId> {
let target = self.ev.ir().defs().get(def.index())?;
(target.std.is_none()
&& self.ev.redirected(def) == def
&& !self.ev.is_value_override(def)
&& target.params.len() == arity
&& target.params.iter().all(|p| p.arity == 0))
.then_some(target.body)
}
fn result_edges(&self, expr: &Expr, edges: &mut Vec<ExprId>) -> Result<()> {
match expr {
Expr::If { then, other, .. } => {
push(edges, *then)?;
push(edges, *other)?;
}
Expr::Case { arms, other } => {
for arm in arms {
push(edges, arm.value)?;
}
if let Some(other) = other {
push(edges, *other)?;
}
}
Expr::Label { body, .. }
| Expr::Selected(body)
| Expr::Let { body, .. }
| Expr::Subst { body, .. } => push(edges, *body)?,
Expr::Def(def) => {
if let Some(body) = self.user_body(*def, 0) {
push(edges, body)?;
}
}
Expr::Apply { callee, args } if args.iter().all(|a| matches!(a, Arg::Expr { .. })) => {
match self.native(callee, args.len()) {
Some(StdOp::SequencesConcat) => {
for arg in args {
if let Arg::Expr { expr, .. } = arg {
push(edges, *expr)?;
}
}
}
Some(_) => {}
None => {
if let OpRef::Def(def) = callee
&& let Some(body) = self.user_body(*def, args.len())
{
push(edges, body)?;
}
}
}
}
_ => {}
}
Ok(())
}
fn results(&self) -> Result<Vec<bool>> {
let count = self.ev.ir().nodes().len();
let mut users = Vec::new();
reserve(&mut users, count)?;
users.resize_with(count, Vec::new);
let mut tuples = Vec::new();
reserve(&mut tuples, count)?;
tuples.resize(count, false);
let mut work = Vec::new();
for (index, node) in self.ev.ir().nodes().iter().enumerate() {
self.poll()?;
let id = ExprId(
u32::try_from(index)
.map_err(|_| EvalError::resource_limit("tuple name expression index"))?,
);
let mut edges = Vec::new();
self.result_edges(&node.expr, &mut edges)?;
for edge in edges {
let Some(dependents) = users.get_mut(edge.index()) else {
return Err(EvalError::bug("tuple name result dependency"));
};
push(dependents, id)?;
}
push(&mut work, id)?;
}
while let Some(id) = work.pop() {
self.poll()?;
if tuples[id.index()] {
continue;
}
let expr = self.ev.ir().expr(id);
let mut edges = Vec::new();
self.result_edges(expr, &mut edges)?;
let grounded = matches!(expr, Expr::Tuple(_))
|| matches!(expr, Expr::Apply { callee, args }
if args.iter().all(|a| matches!(a, Arg::Expr { .. }))
&& self.native(callee, args.len()) == Some(StdOp::SequencesAppend));
let proved = if matches!(expr, Expr::Apply { callee, args }
if self.native(callee, args.len()) == Some(StdOp::SequencesConcat))
{
edges.iter().any(|e| tuples[e.index()])
} else {
!edges.is_empty() && edges.iter().all(|e| tuples[e.index()])
};
if grounded || proved {
tuples[id.index()] = true;
for &user in &users[id.index()] {
push(&mut work, user)?;
}
}
}
Ok(tuples)
}
fn calls(&self, sources: &[ExprId], tuples: &[bool], callbacks: bool) -> Result<bool> {
let mut contexts = Vec::new();
push(&mut contexts, Lexical::default())?;
let mut seen = HashSet::new();
let mut work = Vec::new();
for &source in sources {
push(&mut work, (source, 0))?;
}
while let Some((id, context)) = work.pop() {
self.poll()?;
if seen.contains(&(id, context)) {
continue;
}
seen.try_reserve(1)
.map_err(|_| EvalError::resource_limit("tuple name call contexts allocation"))?;
seen.insert((id, context));
let Some(node) = self.ev.ir().nodes().get(id.index()) else {
return Ok(false);
};
match &node.expr {
Expr::Apply { callee, args } => {
if !self.call(
callee,
args,
tuples,
&contexts[context],
&mut work,
callbacks,
)? {
return Ok(false);
}
}
Expr::Def(def) if self.stored_value_leaf(*def) => {
}
Expr::Def(def) => {
if let Some(op) = self.native(&OpRef::Def(*def), 0) {
if op.creates_runtime_names() {
return Ok(false);
}
} else if let Some(body) = self.user_body(*def, 0) {
push(&mut work, (body, 0))?;
} else {
return Ok(false);
}
}
Expr::Let { defs, body } => {
let context = self.enter_let(defs, &contexts[context], tuples)?;
let next = if let Some(index) = contexts.iter().position(|old| *old == context)
{
index
} else {
let index = contexts.len();
push(&mut contexts, context)?;
index
};
push(&mut work, (*body, next))?;
for def in defs {
push(&mut work, (self.ev.ir().def(*def).body, 0))?;
}
continue;
}
_ => {}
}
let context = if matches!(
node.expr,
Expr::Quant { .. }
| Expr::SetFilter { .. }
| Expr::SetMap { .. }
| Expr::FcnCons { .. }
| Expr::RecFcn { .. }
| Expr::TemporalQuant { .. }
| Expr::Subst { .. }
| Expr::Except { .. }
| Expr::Prime(_)
| Expr::Enabled(_)
) {
0
} else {
context
};
node.expr
.try_for_each_child(|child| push(&mut work, (child, context)))?;
}
Ok(true)
}
fn stored_value_leaf(&self, def: DefId) -> bool {
let Some(target) = self.ev.ir().defs().get(def.index()) else {
return false;
};
target.params.is_empty()
&& target.std.is_none()
&& self.ev.redirected(def) == def
&& self.ev.core.def_values.contains_key(&def)
}
fn call(
&self,
callee: &OpRef,
args: &[Arg],
tuples: &[bool],
context: &Lexical,
work: &mut Vec<(ExprId, usize)>,
callbacks: bool,
) -> Result<bool> {
if !callbacks && args.iter().any(|a| matches!(a, Arg::Op { .. })) {
return Ok(false);
}
if let Some(op) = self.native(callee, args.len()) {
if op.creates_runtime_names() && op != StdOp::SequencesConcat {
return Ok(false);
}
if op == StdOp::SequencesConcat
&& !args.iter().any(|a| {
matches!(a, Arg::Expr { expr, .. }
if tuples[expr.index()] || self.local_tuple(*expr, context))
})
{
return Ok(false);
}
} else if callbacks
&& args.len() == 2
&& matches!(callee, OpRef::Param(_) | OpRef::Subst(_))
{
} else if let OpRef::Def(def) = callee
&& let Some(body) = self.call_body(*def, args)
{
push(work, (body, 0))?;
} else {
return Ok(false);
}
Ok(true)
}
fn enter_let(&self, defs: &[DefId], old: &Lexical, tuples: &[bool]) -> Result<Lexical> {
let mut context = Lexical {
frame: old.frame,
slots: Vec::new(),
};
reserve(&mut context.slots, old.slots.len())?;
context.slots.extend_from_slice(&old.slots);
for &def in defs {
self.poll()?;
let definition = self.ev.ir().def(def);
let dive_ir::DefScope::LetValue { parent, slot, .. } = definition.scope else {
continue;
};
if context.frame != Some(parent) {
context.slots.clear();
context.frame = Some(parent);
}
context.slots.retain(|(bound, _)| *bound != slot);
let valid = self
.ev
.ir()
.def(parent)
.frame
.get(slot.index())
.is_some_and(|info| info.kind == dive_ir::SlotKind::LetValue(def));
if valid
&& self.user_body(def, 0) == Some(definition.body)
&& tuples[definition.body.index()]
{
push(&mut context.slots, (slot, def))?;
}
}
context.slots.sort_unstable();
Ok(context)
}
fn local_tuple(&self, expr: ExprId, context: &Lexical) -> bool {
let Expr::Local(local) = self.ev.ir().expr(expr) else {
return false;
};
local.up == 0
&& context.slots.iter().any(|(slot, def)| {
*slot == local.slot
&& matches!(self.ev.ir().def(*def).scope,
dive_ir::DefScope::LetValue { parent, slot: bound, .. }
if Some(parent) == context.frame && bound == local.slot)
})
}
}
#[derive(Default, PartialEq, Eq)]
struct Lexical {
frame: Option<DefId>,
slots: Vec<(dive_ir::Slot, DefId)>,
}
struct Sources {
exprs: Vec<ExprId>,
scalar_callbacks: bool,
}
enum Capture {
Environment(Env),
Slot(Sv),
Value(Value),
State(StateRef),
}
#[derive(Default)]
struct Retained {
frames: Vec<Arc<Frame>>,
links: Vec<Arc<SubstLink>>,
functions: Vec<Fcn>,
sets: Vec<Set>,
thunks: Vec<Arc<Thunk>>,
states: Vec<Arc<[Option<Value>]>>,
scalar_callbacks: bool,
}
impl Analysis<'_> {
fn captures(&self, roots: &[(ExprId, Scope)]) -> Result<Option<Sources>> {
let mut work = Vec::new();
let mut sources = Vec::new();
let mut retained = Retained::default();
for (expr, scope) in roots {
self.poll()?;
if !Arc::ptr_eq(&scope.owner, &self.ev.core.ir)
|| !Arc::ptr_eq(&scope.names, &self.ev.core.names)
|| !scope.context.ptr_eq(&Arc::downgrade(&self.ev.core))
{
return Ok(None);
}
push(&mut sources, *expr)?;
if let Some(wrapper) = scope.wrapper {
push(&mut sources, wrapper)?;
}
push(&mut work, Capture::Environment(scope.env.clone()))?;
}
for value in self.ev.core.def_values.values() {
push(&mut work, Capture::Value(value.clone()))?;
}
for value in self.ev.core.startup.iter().chain(&self.ev.core.def_cache) {
if let Some(value) = value.get() {
push(&mut work, Capture::Value(value.clone()))?;
}
}
for binding in self.ev.core.consts.iter().flatten() {
if let ConstBinding::Value(value) = binding {
push(&mut work, Capture::Value(value.clone()))?;
}
}
while let Some(task) = work.pop() {
self.poll()?;
let known = match task {
Capture::Environment(env) => {
self.capture_environment(env, &mut work, &mut retained)?
}
Capture::Slot(slot) => {
self.capture_slot(slot, &mut work, &mut sources, &mut retained)?
}
Capture::Value(value) => self.capture_value(value, &mut work, &mut retained)?,
Capture::State(StateRef::Null | StateRef::Empty) => true,
Capture::State(StateRef::Vals(values)) => {
if !retained
.states
.iter()
.any(|prior| Arc::ptr_eq(prior, &values))
{
push(&mut retained.states, values.clone())?;
for value in values.iter().flatten() {
push(&mut work, Capture::Value(value.clone()))?;
}
}
true
}
Capture::State(StateRef::Named(_)) => false,
};
if !known {
return Ok(None);
}
}
Ok(Some(Sources {
exprs: sources,
scalar_callbacks: retained.scalar_callbacks,
}))
}
fn capture_environment(
&self,
env: Env,
work: &mut Vec<Capture>,
retained: &mut Retained,
) -> Result<bool> {
if env.dynamic.at.is_some() || env.dynamic.cut.is_some() {
return Ok(false);
}
let mut link = env.dynamic.subst.clone();
while let Some(current) = link.take() {
self.poll()?;
if retained
.links
.iter()
.any(|prior| Arc::ptr_eq(prior, ¤t))
{
break;
}
push(&mut retained.links, current.clone())?;
push(work, Capture::Slot(current.val.clone()))?;
link.clone_from(¤t.next);
}
let mut frame = Some(env.frame);
while let Some(current) = frame.take() {
self.poll()?;
if retained
.frames
.iter()
.any(|prior| Arc::ptr_eq(prior, ¤t))
{
break;
}
push(&mut retained.frames, current.clone())?;
let Some(definition) = self.ev.ir().defs().get(current.def.index()) else {
return Ok(false);
};
for (index, slot) in current.slots.iter().enumerate() {
if definition.params.get(index).is_some_and(|p| p.arity != 0)
&& !matches!(slot, Sv::Op(_))
{
return Ok(false); }
push(work, Capture::Slot(slot.clone()))?;
}
frame.clone_from(¤t.parent);
}
Ok(true)
}
fn capture_slot(
&self,
slot: Sv,
work: &mut Vec<Capture>,
sources: &mut Vec<ExprId>,
retained: &mut Retained,
) -> Result<bool> {
self.poll()?;
match slot {
Sv::Thunk(thunk) => {
if retained
.thunks
.iter()
.any(|prior| Arc::ptr_eq(prior, &thunk))
{
return Ok(true);
}
push(&mut retained.thunks, thunk.clone())?;
push(sources, thunk.expr)?;
push(work, Capture::Environment(thunk.env.clone()))?;
for cache in thunk.stored_caches().into_iter().flatten() {
let (Ev::V(value), before, after) = cache else {
return Ok(false);
};
push(work, Capture::Value(value))?;
push(work, Capture::State(before))?;
push(work, Capture::State(after))?;
}
}
Sv::Val(value) => push(work, Capture::Value(value))?,
Sv::Unset | Sv::AnalysisBound | Sv::AnalysisConstant => {}
Sv::Op(op) if self.scalar_operator(&op) => retained.scalar_callbacks = true,
Sv::Fcn(_) | Sv::Op(_) => return Ok(false),
}
Ok(true)
}
fn capture_value(
&self,
value: Value,
work: &mut Vec<Capture>,
retained: &mut Retained,
) -> Result<bool> {
match value {
Value::Fcn(function) => {
if retained
.functions
.iter()
.any(|prior| prior.ptr_eq(&function))
{
return Ok(true);
}
push(&mut retained.functions, function.clone())?;
for (key, value) in function.iter() {
self.poll()?;
push(work, Capture::Value(key))?;
push(work, Capture::Value(value.clone()))?;
}
}
Value::Set(set) => {
if !matches!(
set.kind(),
SetKind::Raw
| SetKind::Enum
| SetKind::Interval
| SetKind::Nat
| SetKind::Int
| SetKind::Strings
) {
return Ok(false);
}
if retained.sets.iter().any(|prior| prior.ptr_eq(&set)) {
return Ok(true);
}
push(&mut retained.sets, set.clone())?;
if matches!(set.kind(), SetKind::Raw | SetKind::Enum) {
let Some(values) = set.stored_elements() else {
return Ok(false);
};
for value in values {
self.poll()?;
push(work, Capture::Value(value.clone()))?;
}
}
}
_ => {}
}
Ok(true)
}
}