use std::fmt::{self, Debug, Formatter};
use std::ops::{BitOr, BitOrAssign, Bound};
use super::expr::{LogicalCall, LogicalDestructureField, LogicalExpr, LogicalRecordIdKey};
use super::schema::{Schema, coercion_is_identity, kind_may_be_record};
use crate::expr::{BinaryOperator, Function, Kind, PrefixOperator};
#[derive(Clone, Copy, PartialEq, Eq, Hash, Default)]
pub struct EffectSet(u32);
impl EffectSet {
pub const PURE: Self = Self(0);
pub const WRITES_DATA: Self = Self(1 << 0);
pub const WRITES_EXTERNAL: Self = Self(1 << 1);
pub const READS_EXTERNAL: Self = Self(1 << 2);
pub const ADVANCES_STATE: Self = Self(1 << 3);
pub const ENTROPY: Self = Self(1 << 4);
pub const CLOCK: Self = Self(1 << 5);
pub const BLOCKING: Self = Self(1 << 6);
pub const OPAQUE_BODY: Self = Self(1 << 7);
pub const READS_DATA: Self = Self(1 << 8);
pub const READS_CATALOG: Self = Self(1 << 9);
pub const READS_ROW: Self = Self(1 << 11);
pub const READS_PRINCIPAL: Self = Self(1 << 12);
pub const READS_SESSION_DB: Self = Self(1 << 13);
pub const WRITES_SESSION: Self = Self(1 << 14);
pub const NOTIFY: Self = Self(1 << 15);
pub const DEFERS: Self = Self(1 << 16);
pub const MAY_REJECT: Self = Self(1 << 17);
pub const CHANGES_CATALOG: Self = Self(1 << 18);
pub const READS_SESSION: Self = Self(Self::READS_PRINCIPAL.0 | Self::READS_SESSION_DB.0);
const NON_DETERMINISTIC: Self = Self(
Self::WRITES_DATA.0
| Self::WRITES_EXTERNAL.0
| Self::READS_EXTERNAL.0
| Self::ADVANCES_STATE.0
| Self::ENTROPY.0
| Self::CLOCK.0
| Self::BLOCKING.0
| Self::OPAQUE_BODY.0
| Self::WRITES_SESSION.0
| Self::NOTIFY.0
| Self::DEFERS.0
| Self::CHANGES_CATALOG.0,
);
pub const NON_DETERMINISTIC_BUT_FOR_CLOCK: Self =
Self(Self::NON_DETERMINISTIC.0 & !Self::CLOCK.0);
const MUTATING: Self = Self(
Self::WRITES_DATA.0
| Self::WRITES_EXTERNAL.0
| Self::ADVANCES_STATE.0
| Self::WRITES_SESSION.0
| Self::NOTIFY.0
| Self::DEFERS.0
| Self::CHANGES_CATALOG.0,
);
const ALL: &'static [(EffectSet, &'static str)] = &[
(Self::WRITES_DATA, "WRITES_DATA"),
(Self::WRITES_EXTERNAL, "WRITES_EXTERNAL"),
(Self::READS_EXTERNAL, "READS_EXTERNAL"),
(Self::ADVANCES_STATE, "ADVANCES_STATE"),
(Self::ENTROPY, "ENTROPY"),
(Self::CLOCK, "CLOCK"),
(Self::BLOCKING, "BLOCKING"),
(Self::OPAQUE_BODY, "OPAQUE_BODY"),
(Self::READS_DATA, "READS_DATA"),
(Self::READS_CATALOG, "READS_CATALOG"),
(Self::READS_ROW, "READS_ROW"),
(Self::READS_PRINCIPAL, "READS_PRINCIPAL"),
(Self::READS_SESSION_DB, "READS_SESSION_DB"),
(Self::WRITES_SESSION, "WRITES_SESSION"),
(Self::NOTIFY, "NOTIFY"),
(Self::DEFERS, "DEFERS"),
(Self::MAY_REJECT, "MAY_REJECT"),
(Self::CHANGES_CATALOG, "CHANGES_CATALOG"),
];
pub const TOP: Self = {
let mut bits = 0;
let mut i = 0;
while i < Self::ALL.len() {
bits |= Self::ALL[i].0.0;
i += 1;
}
Self(bits)
};
pub const fn union(self, other: Self) -> Self {
Self(self.0 | other.0)
}
pub const fn contains(self, other: Self) -> bool {
self.0 & other.0 == other.0
}
pub const fn intersects(self, other: Self) -> bool {
self.0 & other.0 != 0
}
pub const fn is_pure(self) -> bool {
self.0 == 0
}
pub const fn is_deterministic(self) -> bool {
!self.intersects(Self::NON_DETERMINISTIC)
}
pub const fn is_deterministic_but_for_clock(self) -> bool {
!self.intersects(Self(Self::NON_DETERMINISTIC.0 & !Self::CLOCK.0))
}
pub const fn writes_data(self) -> bool {
self.contains(Self::WRITES_DATA)
}
pub const fn mutates_state(self) -> bool {
self.intersects(Self::MUTATING)
}
}
impl BitOr for EffectSet {
type Output = Self;
fn bitor(self, rhs: Self) -> Self {
self.union(rhs)
}
}
impl BitOrAssign for EffectSet {
fn bitor_assign(&mut self, rhs: Self) {
*self = self.union(rhs);
}
}
impl Debug for EffectSet {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
if self.is_pure() {
return f.write_str("PURE");
}
let mut first = true;
for (flag, name) in Self::ALL {
if self.contains(*flag) {
if !first {
f.write_str(" | ")?;
}
f.write_str(name)?;
first = false;
}
}
Ok(())
}
}
pub const ROW_PARAMS: &[&str] = &["this", "self", "parent", "value"];
pub const ITERATION_PARAMS: &[&str] = &["this", "self", "parent"];
pub trait EffectOracle {
fn builtin(&self, name: &str) -> Option<EffectSet>;
fn closure_args(&self, name: &str) -> Option<&'static [usize]>;
fn method_always_dispatches(&self, name: &str) -> bool;
fn custom_function(&self, _name: &str) -> Option<EffectSet> {
None
}
fn evaluates_against_row(&self, name: &str) -> bool;
fn permission_checked_param(&self, name: &str) -> bool;
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Effects {
pub set: EffectSet,
pub impure: bool,
pub index_operator: bool,
pub may_raise: bool,
pub reads_row: bool,
pub reads_row_opaquely: bool,
}
impl Effects {
pub const fn effect_free(self) -> bool {
!self.impure && self.set.is_deterministic()
}
pub const fn pure(self) -> bool {
self.effect_free() && !self.index_operator
}
pub const INERT: Self = Self {
set: EffectSet::PURE,
impure: false,
index_operator: false,
may_raise: false,
reads_row: false,
reads_row_opaquely: false,
};
fn join(self, other: Self) -> Self {
Self {
set: self.set.union(other.set),
impure: self.impure || other.impure,
index_operator: self.index_operator || other.index_operator,
may_raise: self.may_raise || other.may_raise,
reads_row: self.reads_row || other.reads_row,
reads_row_opaquely: self.reads_row_opaquely || other.reads_row_opaquely,
}
}
}
#[derive(Clone, Debug)]
pub struct ChildFacts {
pub effects: Effects,
pub checked_kind: Option<Kind>,
pub may_dereference: bool,
}
pub fn facts_of(expr: &LogicalExpr, oracle: &dyn EffectOracle) -> ChildFacts {
let mut children = Vec::new();
expr.for_each_child(&mut |child| children.push(facts_of(child, oracle)));
let kinds = children.iter().map(|child| child.checked_kind.clone()).collect::<Vec<_>>();
ChildFacts {
effects: node_effects(expr, &children, oracle),
checked_kind: expr.node_checked_kind(&kinds, &Schema::open()),
may_dereference: node_may_dereference(expr, &children),
}
}
pub fn effects_of(expr: &LogicalExpr, oracle: &dyn EffectOracle) -> Effects {
facts_of(expr, oracle).effects
}
pub fn node_effects(
expr: &LogicalExpr,
children: &[ChildFacts],
oracle: &dyn EffectOracle,
) -> Effects {
let joined = children.iter().fold(Effects::INERT, |all, child| all.join(child.effects));
Effects {
set: joined.set.union(node_set(expr, oracle)),
impure: joined.impure || node_is_impure(expr, children, oracle),
index_operator: joined.index_operator
|| matches!(
expr,
LogicalExpr::Binary {
op: BinaryOperator::Matches(_) | BinaryOperator::NearestNeighbor(_),
..
}
),
may_raise: node_may_raise(expr, children, joined.may_raise, oracle),
reads_row: joined.reads_row || node_reads_row(expr, oracle),
reads_row_opaquely: joined.reads_row_opaquely || node_reads_row_opaquely(expr, oracle),
}
}
pub fn invokes_unseen_body(expr: &LogicalExpr, oracle: &dyn EffectOracle) -> bool {
match expr {
LogicalExpr::Invoke {
..
} => true,
LogicalExpr::Method {
name,
..
} => !oracle.method_always_dispatches(name.as_str()),
LogicalExpr::Call(call) => match &call.receiver {
Function::Normal(name) => {
let every_position = oracle
.builtin(name)
.is_none_or(|effects| effects.contains(EffectSet::OPAQUE_BODY));
match oracle.closure_args(name) {
Some(slots) if !every_position => slots
.iter()
.filter_map(|&slot| call.args.get(slot))
.any(may_carry_unseen_closure),
_ => call.args.iter().any(may_carry_unseen_closure),
}
}
Function::Model(_)
| Function::Custom(_)
| Function::Script(_)
| Function::Module(..)
| Function::Silo {
..
} => false,
},
LogicalExpr::Literal(_)
| LogicalExpr::Array(_)
| LogicalExpr::Set(_)
| LogicalExpr::Object(_)
| LogicalExpr::RecordId(_)
| LogicalExpr::Param(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Access {
..
}
| LogicalExpr::Index {
..
}
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Each(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Filter {
..
}
| LogicalExpr::Destructure {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Lookup {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::RepeatRecurse(_)
| LogicalExpr::Broadcast {
..
}
| LogicalExpr::SetField {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Binary {
..
}
| LogicalExpr::Closure(_)
| LogicalExpr::If(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue
| LogicalExpr::Subquery(_) => false,
}
}
pub fn may_carry_unseen_closure(arg: &LogicalExpr) -> bool {
match arg {
LogicalExpr::Closure(_)
| LogicalExpr::Literal(_)
| LogicalExpr::RecordId(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_) => false,
LogicalExpr::Array(items) | LogicalExpr::Set(items) => {
items.iter().any(may_carry_unseen_closure)
}
LogicalExpr::Object(fields) => {
fields.iter().any(|(_, value)| may_carry_unseen_closure(value))
}
LogicalExpr::Binary {
left,
op,
right,
} => match op {
BinaryOperator::NullCoalescing
| BinaryOperator::TenaryCondition
| BinaryOperator::And
| BinaryOperator::Or => may_carry_unseen_closure(left) || may_carry_unseen_closure(right),
BinaryOperator::Equal
| BinaryOperator::ExactEqual
| BinaryOperator::NotEqual
| BinaryOperator::AllEqual
| BinaryOperator::AnyEqual
| BinaryOperator::LessThan
| BinaryOperator::LessThanEqual
| BinaryOperator::MoreThan
| BinaryOperator::MoreThanEqual
| BinaryOperator::Contain
| BinaryOperator::NotContain
| BinaryOperator::ContainAll
| BinaryOperator::ContainAny
| BinaryOperator::ContainNone
| BinaryOperator::Inside
| BinaryOperator::NotInside
| BinaryOperator::AllInside
| BinaryOperator::AnyInside
| BinaryOperator::NoneInside
| BinaryOperator::Outside
| BinaryOperator::Intersects
| BinaryOperator::Add
| BinaryOperator::Subtract
| BinaryOperator::Multiply
| BinaryOperator::Divide
| BinaryOperator::Remainder
| BinaryOperator::Power
| BinaryOperator::Range
| BinaryOperator::RangeInclusive
| BinaryOperator::RangeSkip
| BinaryOperator::RangeSkipInclusive
| BinaryOperator::Matches(_)
| BinaryOperator::NearestNeighbor(_) => false,
},
LogicalExpr::Prefix {
op,
expr,
} => match op {
PrefixOperator::Not
| PrefixOperator::Positive
| PrefixOperator::Negate
| PrefixOperator::Range
| PrefixOperator::RangeInclusive => false,
PrefixOperator::Cast(_) => may_carry_unseen_closure(expr),
},
LogicalExpr::Param(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Access {
..
}
| LogicalExpr::Index {
..
}
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Each(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Filter {
..
}
| LogicalExpr::Method {
..
}
| LogicalExpr::Destructure {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Lookup {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::RepeatRecurse(_)
| LogicalExpr::Broadcast {
..
}
| LogicalExpr::SetField {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Invoke {
..
}
| LogicalExpr::Call(_)
| LogicalExpr::If(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue
| LogicalExpr::Subquery(_) => true,
}
}
fn call_evaluates_against_row(call: &LogicalCall, oracle: &dyn EffectOracle) -> bool {
match &call.receiver {
Function::Normal(name) => oracle.evaluates_against_row(name),
Function::Model(_) => false,
Function::Custom(_)
| Function::Script(_)
| Function::Module(..)
| Function::Silo {
..
} => true,
}
}
fn node_set(expr: &LogicalExpr, oracle: &dyn EffectOracle) -> EffectSet {
match expr {
LogicalExpr::Call(call) => match &call.receiver {
Function::Normal(name) => {
let mut set = oracle.builtin(name).unwrap_or(EffectSet::OPAQUE_BODY);
if oracle.evaluates_against_row(name) {
set = set.union(EffectSet::READS_ROW);
}
if invokes_unseen_body(expr, oracle) {
set = set.union(EffectSet::OPAQUE_BODY);
}
set
}
Function::Model(_) => EffectSet::READS_EXTERNAL,
Function::Custom(name) => oracle
.custom_function(name)
.unwrap_or(EffectSet::OPAQUE_BODY.union(EffectSet::READS_ROW)),
Function::Script(_)
| Function::Module(..)
| Function::Silo {
..
} => EffectSet::OPAQUE_BODY.union(EffectSet::READS_ROW),
},
LogicalExpr::Invoke {
..
}
| LogicalExpr::Method {
..
} => {
if invokes_unseen_body(expr, oracle) {
EffectSet::OPAQUE_BODY
} else {
EffectSet::PURE
}
}
LogicalExpr::Literal(_)
| LogicalExpr::Array(_)
| LogicalExpr::Set(_)
| LogicalExpr::Object(_)
| LogicalExpr::RecordId(_)
| LogicalExpr::Param(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Access {
..
}
| LogicalExpr::Index {
..
}
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Each(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Filter {
..
}
| LogicalExpr::Destructure {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Lookup {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::RepeatRecurse(_)
| LogicalExpr::Broadcast {
..
}
| LogicalExpr::SetField {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Binary {
..
}
| LogicalExpr::Closure(_)
| LogicalExpr::If(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue
| LogicalExpr::Subquery(_) => EffectSet::PURE,
}
}
fn node_is_impure(expr: &LogicalExpr, children: &[ChildFacts], oracle: &dyn EffectOracle) -> bool {
match expr {
LogicalExpr::Call(call) => match &call.receiver {
Function::Normal(name) => {
oracle.builtin(name).is_none_or(|effects| !effects.is_deterministic())
|| invokes_unseen_body(expr, oracle)
}
Function::Custom(_)
| Function::Script(_)
| Function::Model(_)
| Function::Module(..)
| Function::Silo {
..
} => true,
},
LogicalExpr::Method {
..
}
| LogicalExpr::Closure(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue
| LogicalExpr::Subquery(_)
| LogicalExpr::Invoke {
..
} => true,
LogicalExpr::RecordId(rid) => key_is_generated(&rid.key),
LogicalExpr::Access {
..
} => {
let base = base_facts(children);
base.may_dereference && !proven_not_record(base.checked_kind.as_ref())
}
LogicalExpr::Destructure {
fields,
..
} => {
let base = base_facts(children);
base.may_dereference && destructure_fetches(base.checked_kind.as_ref(), fields)
}
LogicalExpr::Each(_)
| LogicalExpr::Filter {
..
}
| LogicalExpr::Lookup {
..
} => base_facts(children).may_dereference,
LogicalExpr::Literal(_)
| LogicalExpr::Array(_)
| LogicalExpr::Set(_)
| LogicalExpr::Object(_)
| LogicalExpr::Param(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Index {
..
}
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::RepeatRecurse(_)
| LogicalExpr::Broadcast {
..
}
| LogicalExpr::SetField {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Binary {
..
}
| LogicalExpr::If(_) => false,
}
}
fn node_may_raise(
expr: &LogicalExpr,
child_facts: &[ChildFacts],
children: bool,
oracle: &dyn EffectOracle,
) -> bool {
match expr {
LogicalExpr::Param(param) => oracle.permission_checked_param(param.as_str()),
LogicalExpr::Literal(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_) => false,
LogicalExpr::RecordId(rid) => match &rid.key {
LogicalRecordIdKey::Number(_)
| LogicalRecordIdKey::String(_)
| LogicalRecordIdKey::Uuid(_) => false,
LogicalRecordIdKey::Array(_) | LogicalRecordIdKey::Object(_) => children,
LogicalRecordIdKey::Generate(_) | LogicalRecordIdKey::Range(_) => true,
},
LogicalExpr::Array(_)
| LogicalExpr::Set(_)
| LogicalExpr::Object(_)
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::If(_) => children,
LogicalExpr::Each(base) => {
base_dereference_may_raise(base, base_facts(child_facts).may_dereference) || children
}
LogicalExpr::Access {
base,
..
} => {
let facts = base_facts(child_facts);
(base_dereference_may_raise(base, facts.may_dereference)
&& !proven_not_record(facts.checked_kind.as_ref()))
|| children
}
LogicalExpr::Destructure {
base,
fields,
} => {
let facts = base_facts(child_facts);
(base_dereference_may_raise(base, facts.may_dereference)
&& destructure_fetches(facts.checked_kind.as_ref(), fields))
|| children
}
LogicalExpr::Prefix {
op,
..
} => match op {
PrefixOperator::Not
| PrefixOperator::Positive
| PrefixOperator::Range
| PrefixOperator::RangeInclusive => children,
PrefixOperator::Cast(kind) => {
!cast_is_identity(kind, base_facts(child_facts).checked_kind.as_ref()) || children
}
PrefixOperator::Negate => true,
},
LogicalExpr::Binary {
op,
..
} => match op {
BinaryOperator::Equal
| BinaryOperator::ExactEqual
| BinaryOperator::NotEqual
| BinaryOperator::AllEqual
| BinaryOperator::AnyEqual
| BinaryOperator::LessThan
| BinaryOperator::LessThanEqual
| BinaryOperator::MoreThan
| BinaryOperator::MoreThanEqual
| BinaryOperator::Contain
| BinaryOperator::NotContain
| BinaryOperator::ContainAll
| BinaryOperator::ContainAny
| BinaryOperator::ContainNone
| BinaryOperator::Inside
| BinaryOperator::NotInside
| BinaryOperator::AllInside
| BinaryOperator::AnyInside
| BinaryOperator::NoneInside
| BinaryOperator::Outside
| BinaryOperator::Intersects
| BinaryOperator::And
| BinaryOperator::Or
| BinaryOperator::NullCoalescing
| BinaryOperator::TenaryCondition => children,
BinaryOperator::Add
| BinaryOperator::Subtract
| BinaryOperator::Multiply
| BinaryOperator::Divide
| BinaryOperator::Remainder
| BinaryOperator::Power
| BinaryOperator::Range
| BinaryOperator::RangeInclusive
| BinaryOperator::RangeSkip
| BinaryOperator::RangeSkipInclusive
| BinaryOperator::Matches(_)
| BinaryOperator::NearestNeighbor(_) => true,
},
LogicalExpr::Index {
..
}
| LogicalExpr::Method {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Invoke {
..
}
| LogicalExpr::Call(_)
| LogicalExpr::Closure(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue
| LogicalExpr::Subquery(_)
| LogicalExpr::Lookup {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::RepeatRecurse(_)
| LogicalExpr::Broadcast {
..
}
| LogicalExpr::Filter {
..
}
| LogicalExpr::SetField {
..
} => true,
}
}
pub(super) fn node_reads_row(expr: &LogicalExpr, oracle: &dyn EffectOracle) -> bool {
match expr {
LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Subquery(_)
| LogicalExpr::Lookup {
..
} => true,
LogicalExpr::Param(param) => ROW_PARAMS.contains(¶m.as_str()),
LogicalExpr::Call(call) => call_evaluates_against_row(call, oracle),
LogicalExpr::Literal(_)
| LogicalExpr::Array(_)
| LogicalExpr::Set(_)
| LogicalExpr::Object(_)
| LogicalExpr::RecordId(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Access {
..
}
| LogicalExpr::Index {
..
}
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Each(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Filter {
..
}
| LogicalExpr::Method {
..
}
| LogicalExpr::Destructure {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::RepeatRecurse(_)
| LogicalExpr::Broadcast {
..
}
| LogicalExpr::SetField {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Invoke {
..
}
| LogicalExpr::Binary {
..
}
| LogicalExpr::Closure(_)
| LogicalExpr::If(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue => false,
}
}
fn node_reads_row_opaquely(expr: &LogicalExpr, oracle: &dyn EffectOracle) -> bool {
match expr {
LogicalExpr::Doc | LogicalExpr::Subquery(_) => true,
LogicalExpr::Param(param) => ITERATION_PARAMS.contains(¶m.as_str()),
LogicalExpr::Call(call) => {
call_evaluates_against_row(call, oracle) || invokes_unseen_body(expr, oracle)
}
LogicalExpr::Invoke {
..
}
| LogicalExpr::Method {
..
} => invokes_unseen_body(expr, oracle),
LogicalExpr::Literal(_)
| LogicalExpr::Array(_)
| LogicalExpr::Set(_)
| LogicalExpr::Object(_)
| LogicalExpr::RecordId(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Field(_)
| LogicalExpr::Current
| LogicalExpr::Access {
..
}
| LogicalExpr::Index {
..
}
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Each(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Filter {
..
}
| LogicalExpr::Destructure {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Lookup {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::RepeatRecurse(_)
| LogicalExpr::Broadcast {
..
}
| LogicalExpr::SetField {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Binary {
..
}
| LogicalExpr::Closure(_)
| LogicalExpr::If(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue => false,
}
}
pub fn key_is_generated(key: &LogicalRecordIdKey) -> bool {
match key {
LogicalRecordIdKey::Generate(_) => true,
LogicalRecordIdKey::Range(range) => [&range.start, &range.end].into_iter().any(
|bound| matches!(bound, Bound::Included(key) | Bound::Excluded(key) if key_is_generated(key)),
),
LogicalRecordIdKey::Number(_)
| LogicalRecordIdKey::String(_)
| LogicalRecordIdKey::Uuid(_)
| LogicalRecordIdKey::Array(_)
| LogicalRecordIdKey::Object(_) => false,
}
}
fn base_dereference_may_raise(base: &LogicalExpr, base_may_dereference: bool) -> bool {
if let LogicalExpr::Param(name) = base {
return !ITERATION_PARAMS.contains(&name.as_str());
}
base_may_dereference
}
fn base_facts(children: &[ChildFacts]) -> &ChildFacts {
&children[0]
}
fn proven_not_record(kind: Option<&Kind>) -> bool {
kind.is_some_and(|kind| !kind_may_be_record(kind))
}
fn destructure_fetches(kind: Option<&Kind>, fields: &[LogicalDestructureField]) -> bool {
!proven_not_record(kind) || fields_fetch(fields)
}
fn fields_fetch(fields: &[LogicalDestructureField]) -> bool {
fields.iter().any(|field| {
matches!(field, LogicalDestructureField::All(_) | LogicalDestructureField::Destructure(..))
})
}
fn cast_is_identity(kind: &Kind, operand: Option<&Kind>) -> bool {
operand.is_some_and(|checked| coercion_is_identity(kind, checked))
}
pub fn may_dereference(expr: &LogicalExpr) -> bool {
dereference_by(expr, || {
let mut any = false;
expr.for_each_child(&mut |child| any = any || may_dereference(child));
any
})
}
pub fn node_may_dereference(expr: &LogicalExpr, children: &[ChildFacts]) -> bool {
dereference_by(expr, || children.iter().any(|child| child.may_dereference))
}
fn dereference_by(expr: &LogicalExpr, any_child: impl FnOnce() -> bool) -> bool {
match expr {
LogicalExpr::Literal(_) => false,
LogicalExpr::Array(_) | LogicalExpr::Set(_) | LogicalExpr::Object(_) => any_child(),
LogicalExpr::RecordId(_)
| LogicalExpr::Param(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Access {
..
}
| LogicalExpr::Index {
..
}
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Each(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Filter {
..
}
| LogicalExpr::Method {
..
}
| LogicalExpr::Destructure {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Lookup {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::RepeatRecurse(_)
| LogicalExpr::Broadcast {
..
}
| LogicalExpr::SetField {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Invoke {
..
}
| LogicalExpr::Binary {
..
}
| LogicalExpr::Call(_)
| LogicalExpr::Closure(_)
| LogicalExpr::If(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue
| LogicalExpr::Subquery(_) => true,
}
}
#[cfg(test)]
mod tests {
use super::{EffectOracle, EffectSet, Effects, effects_of, invokes_unseen_body};
use crate::expr::logical::{
LogicalCall, LogicalClosure, LogicalExpr, LogicalLiteral, lower_expr,
};
use crate::expr::{BinaryOperator, Function, Param};
struct Declared;
impl EffectOracle for Declared {
fn builtin(&self, name: &str) -> Option<EffectSet> {
match name {
"array::any" | "array::fold" | "string::len" => Some(EffectSet::PURE),
"api::invoke" => Some(EffectSet::OPAQUE_BODY),
_ => None,
}
}
fn closure_args(&self, name: &str) -> Option<&'static [usize]> {
match name {
"array::any" => Some(&[1]),
"array::fold" => Some(&[2]),
"string::len" | "api::invoke" => Some(&[]),
_ => None,
}
}
fn method_always_dispatches(&self, _name: &str) -> bool {
false
}
fn evaluates_against_row(&self, _name: &str) -> bool {
false
}
fn permission_checked_param(&self, _name: &str) -> bool {
false
}
}
fn call(name: &str, args: Vec<LogicalExpr>) -> LogicalExpr {
LogicalExpr::Call(Box::new(LogicalCall {
receiver: Function::Normal(name.to_string()),
args,
}))
}
fn param(name: &str) -> LogicalExpr {
LogicalExpr::Param(Param::from(name.to_string()))
}
fn int(n: i64) -> LogicalExpr {
LogicalExpr::Literal(LogicalLiteral::Integer(n))
}
fn closure(body: LogicalExpr) -> LogicalExpr {
LogicalExpr::Closure(Box::new(LogicalClosure {
args: Vec::new(),
returns: None,
body_sql: std::sync::Arc::from(surrealdb_types::ToSql::to_sql(&body)),
body,
}))
}
#[test]
fn a_callback_builtin_handed_a_value_invokes_an_unseen_body() {
let one = LogicalExpr::Array(vec![int(1)]);
assert!(invokes_unseen_body(
&call("array::any", vec![one.clone(), param("pred")]),
&Declared
));
let field = LogicalExpr::Access {
base: Box::new(param("o")),
field: "check".into(),
};
assert!(invokes_unseen_body(&call("array::any", vec![one.clone(), field]), &Declared));
let inner = call("array::any", vec![one.clone(), param("pred")]);
assert!(invokes_unseen_body(&call("array::any", vec![one, inner]), &Declared));
assert!(invokes_unseen_body(&call("fn::unknown", vec![param("pred")]), &Declared));
}
#[test]
fn a_closure_written_in_the_call_is_not_unseen() {
let one = LogicalExpr::Array(vec![int(1)]);
let body = LogicalExpr::Binary {
left: Box::new(LogicalExpr::Field("secret".into())),
op: BinaryOperator::Equal,
right: Box::new(LogicalExpr::Literal(LogicalLiteral::String("yes".into()))),
};
assert!(!invokes_unseen_body(
&call("array::any", vec![one.clone(), closure(body)]),
&Declared
));
assert!(!invokes_unseen_body(&call("array::any", vec![one.clone(), int(1)]), &Declared));
let cmp = LogicalExpr::Binary {
left: Box::new(param("a")),
op: BinaryOperator::MoreThan,
right: Box::new(int(1)),
};
assert!(!invokes_unseen_body(&call("array::any", vec![one.clone(), cmp]), &Declared));
let coalesce = LogicalExpr::Binary {
left: Box::new(param("pred")),
op: BinaryOperator::NullCoalescing,
right: Box::new(int(1)),
};
assert!(invokes_unseen_body(&call("array::any", vec![one, coalesce]), &Declared));
}
#[test]
fn a_pure_builtin_runs_no_body_whatever_it_is_handed() {
assert!(!invokes_unseen_body(&call("string::len", vec![param("pred")]), &Declared));
assert!(!invokes_unseen_body(
&call("string::len", vec![LogicalExpr::Field("name".into())]),
&Declared
));
}
#[test]
fn only_the_declared_closure_position_is_judged() {
let tags = LogicalExpr::Field("tags".into());
assert!(!invokes_unseen_body(&call("array::any", vec![tags.clone(), int(1)]), &Declared));
assert!(!invokes_unseen_body(&call("array::any", vec![param("arr"), int(1)]), &Declared));
assert!(invokes_unseen_body(&call("array::any", vec![tags, param("pred")]), &Declared));
let body = closure(param("acc"));
assert!(!invokes_unseen_body(
&call("array::fold", vec![param("arr"), param("init"), body]),
&Declared
));
assert!(invokes_unseen_body(
&call("array::fold", vec![param("arr"), int(0), param("f")]),
&Declared
));
assert!(!invokes_unseen_body(&call("array::any", vec![param("arr")]), &Declared));
assert!(invokes_unseen_body(&call("api::invoke", vec![param("req")]), &Declared));
assert!(!invokes_unseen_body(&call("api::invoke", vec![int(1)]), &Declared));
}
#[test]
fn a_closure_a_builtin_runs_is_an_effect_of_the_call() {
use super::effects_of;
let tags = LogicalExpr::Field("tags".into());
let transparent = effects_of(&call("array::any", vec![tags.clone(), int(1)]), &Declared);
assert!(transparent.pure(), "{transparent:?}");
assert!(!transparent.reads_row_opaquely);
let opaque = effects_of(&call("array::any", vec![tags, param("pred")]), &Declared);
assert!(opaque.set.contains(EffectSet::OPAQUE_BODY), "{opaque:?}");
assert!(opaque.impure);
assert!(opaque.reads_row_opaquely);
}
#[test]
fn a_read_of_stable_state_is_deterministic_and_an_effect_is_not() {
assert!(EffectSet::PURE.is_deterministic());
assert!(
(EffectSet::READS_DATA
| EffectSet::READS_CATALOG
| EffectSet::READS_PRINCIPAL
| EffectSet::READS_SESSION_DB
| EffectSet::READS_ROW)
.is_deterministic()
);
assert!(EffectSet::READS_SESSION.is_deterministic());
for (flag, _) in EffectSet::ALL {
let stable = matches!(
*flag,
EffectSet::READS_DATA
| EffectSet::READS_CATALOG
| EffectSet::READS_PRINCIPAL
| EffectSet::READS_SESSION_DB
| EffectSet::READS_ROW
| EffectSet::MAY_REJECT
);
assert_eq!(flag.is_deterministic(), stable, "{flag:?}");
}
}
#[test]
fn what_outlives_the_statement_mutates_state() {
for (flag, _) in EffectSet::ALL {
let outlives = matches!(
*flag,
EffectSet::WRITES_DATA
| EffectSet::WRITES_EXTERNAL
| EffectSet::ADVANCES_STATE
| EffectSet::WRITES_SESSION
| EffectSet::NOTIFY
| EffectSet::DEFERS
| EffectSet::CHANGES_CATALOG
);
assert_eq!(flag.mutates_state(), outlives, "{flag:?}");
}
assert!(!EffectSet::PURE.mutates_state());
}
#[test]
fn only_a_data_write_decides_the_transaction() {
assert!(EffectSet::WRITES_DATA.writes_data());
assert!((EffectSet::OPAQUE_BODY | EffectSet::WRITES_DATA).writes_data());
assert!(!EffectSet::WRITES_EXTERNAL.writes_data());
assert!(!EffectSet::OPAQUE_BODY.writes_data());
}
#[test]
fn the_debug_form_names_every_flag_present() {
assert_eq!(format!("{:?}", EffectSet::PURE), "PURE");
assert_eq!(
format!("{:?}", EffectSet::WRITES_EXTERNAL | EffectSet::READS_EXTERNAL),
"WRITES_EXTERNAL | READS_EXTERNAL"
);
assert_eq!(EffectSet::ALL.len(), 18, "every flag is named");
assert_eq!(
format!("{:?}", EffectSet::READS_PRINCIPAL | EffectSet::READS_SESSION_DB),
"READS_PRINCIPAL | READS_SESSION_DB"
);
assert_eq!(
format!("{:?}", EffectSet::READS_SESSION),
format!("{:?}", EffectSet::READS_PRINCIPAL | EffectSet::READS_SESSION_DB)
);
}
#[test]
fn the_session_union_is_the_two_split_reads_and_no_listed_flag() {
assert_eq!(
EffectSet::READS_SESSION,
EffectSet::READS_PRINCIPAL | EffectSet::READS_SESSION_DB
);
assert!(EffectSet::ALL.iter().all(|(flag, _)| *flag != EffectSet::READS_SESSION));
let mut seen = EffectSet::PURE;
for (flag, _) in EffectSet::ALL {
assert!(!seen.intersects(*flag), "{flag:?} overlaps an earlier flag");
seen |= *flag;
}
assert!(!seen.intersects(EffectSet(1 << 10)));
}
#[test]
fn top_holds_every_flag_and_is_neither_deterministic_nor_inert() {
for (flag, _) in EffectSet::ALL {
assert!(EffectSet::TOP.contains(*flag), "TOP lacks {flag:?}");
}
assert!(EffectSet::TOP.contains(EffectSet::READS_SESSION));
assert!(!EffectSet::TOP.is_deterministic());
assert!(EffectSet::TOP.mutates_state());
}
fn effects(text: &str) -> Effects {
let expr = lower_expr(crate::syn::expr(text).expect("expression parses"))
.expect("expression lowers");
effects_of(&expr, &Declared)
}
#[test]
fn a_cast_proven_identity_raises_only_where_its_operand_does() {
assert!(!effects("<option<bool>> (a > 1)").may_raise);
assert!(effects("<number> (<int> a)").may_raise);
assert!(effects("<number> (a > 1)").may_raise);
assert!(effects("<any> (a + 1)").may_raise);
}
#[test]
fn a_read_of_a_base_proven_not_a_record_fetches_nothing() {
let object = effects("{ x: 1 }.x");
assert!(!object.may_raise);
assert!(object.pure());
assert!(!effects("{ x: a }.x").may_raise);
let cast = effects("(<object> $v).f");
assert!(!cast.impure);
assert!(cast.may_raise);
assert!(effects("(<record> $v).f").impure);
let field = effects("a.f");
assert!(field.may_raise);
assert!(field.impure);
assert!(!effects("(<array<object>> $v).f").impure);
assert!(effects("(<array<record>> $v).f").impure);
}
#[test]
fn a_destructure_fetching_a_field_is_no_read_of_a_value_in_hand() {
let plain = effects("(<object> $v).{ f }");
assert!(!plain.impure);
assert!(plain.may_raise);
assert!(!effects("{ f: 1 }.{ f }").may_raise);
for text in [
"(<object> $v).{ f.* }",
"(<object> $v).{ f.{ g } }",
"(<object> $v).{ f, h.* }",
"{ f: a }.{ f.* }",
] {
let fetch = effects(text);
assert!(fetch.impure, "{text} is impure");
assert!(fetch.may_raise, "{text} may raise");
}
}
#[test]
fn arithmetic_raises_whatever_the_operand_kinds() {
assert!(effects("(<int> a) + 1").may_raise);
assert!(effects("-(<float> a)").may_raise);
assert!(effects("(<int> a) / 0").may_raise);
}
}