use std::collections::HashMap;
use std::hash::{Hash, Hasher};
use super::effects::{
ChildFacts, EffectOracle, Effects, node_effects, node_may_dereference, node_reads_row,
};
use super::expr::LogicalExpr;
use super::schema::Schema;
use crate::expr::{BinaryOperator, Kind};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct NodeId(u32);
impl NodeId {
fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Frame(u32);
impl Frame {
pub const fn new(index: u32) -> Self {
Frame(index)
}
pub const fn next(self) -> Self {
Frame(self.0 + 1)
}
}
#[derive(Clone, Copy, Debug)]
pub struct Root<'a> {
pub expr: &'a LogicalExpr,
pub frame: Frame,
}
#[derive(Debug)]
pub struct DagNode<'a> {
pub expr: &'a LogicalExpr,
pub children: Vec<NodeId>,
pub effects: Effects,
pub checked_kind: Option<Kind>,
pub may_dereference: bool,
pub occurrences: Vec<Occurrence<'a>>,
first: Option<usize>,
}
#[derive(Debug)]
pub struct Occurrence<'a> {
pub at: *const LogicalExpr,
pub root: usize,
pub order: usize,
pub conditional: bool,
_region: std::marker::PhantomData<&'a LogicalExpr>,
}
struct NodeKey<'a> {
expr: &'a LogicalExpr,
children: Vec<NodeId>,
frame: Option<Frame>,
}
impl Hash for NodeKey<'_> {
fn hash<H: Hasher>(&self, state: &mut H) {
self.expr.shallow_hash(state);
self.children.hash(state);
self.frame.hash(state);
}
}
impl PartialEq for NodeKey<'_> {
fn eq(&self, other: &Self) -> bool {
#[cfg(test)]
SHALLOW_EQ_CALLS.with(|calls| calls.set(calls.get() + 1));
self.frame == other.frame
&& self.children == other.children
&& self.expr.shallow_eq(other.expr)
}
}
impl Eq for NodeKey<'_> {}
#[cfg(test)]
thread_local! {
static SHALLOW_EQ_CALLS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
#[derive(Debug)]
pub struct ExprDag<'a> {
pub nodes: Vec<DagNode<'a>>,
pub roots: Vec<NodeId>,
table: HashMap<NodeKey<'a>, NodeId>,
positions: HashMap<*const LogicalExpr, NodeId>,
holds_subquery: Vec<bool>,
}
impl std::fmt::Debug for NodeKey<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("NodeKey").field("children", &self.children).finish_non_exhaustive()
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SharedValue {
pub first: *const LogicalExpr,
pub reuses: Vec<*const LogicalExpr>,
}
unsafe impl Send for SharedValue {}
unsafe impl Sync for SharedValue {}
#[doc(hidden)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Reach {
Always,
Conditional,
Body,
}
#[doc(hidden)]
pub fn reach(parent: &LogicalExpr, index: usize) -> Reach {
match parent {
LogicalExpr::Broadcast {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Filter {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::Lookup {
..
}
| LogicalExpr::Destructure {
..
}
| LogicalExpr::Method {
..
}
| LogicalExpr::Index {
..
} => match index {
0 => Reach::Always,
_ => Reach::Body,
},
LogicalExpr::SetField {
..
}
| LogicalExpr::If(_) => match index {
0 => Reach::Always,
_ => Reach::Conditional,
},
LogicalExpr::RepeatRecurse(_) | LogicalExpr::Closure(_) => Reach::Body,
LogicalExpr::Binary {
op,
..
} => match (index, op) {
(
1,
BinaryOperator::And
| BinaryOperator::Or
| BinaryOperator::NullCoalescing
| BinaryOperator::TenaryCondition,
) => Reach::Conditional,
_ => Reach::Always,
},
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::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Each(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Invoke {
..
}
| LogicalExpr::Call(_)
| LogicalExpr::Throw(_)
| LogicalExpr::Break
| LogicalExpr::Continue
| LogicalExpr::Subquery(_) => Reach::Always,
}
}
struct Builder<'a, 'o> {
dag: ExprDag<'a>,
oracle: &'o dyn EffectOracle,
next_frame: u32,
root: usize,
order: usize,
}
impl<'a> Builder<'a, '_> {
fn intern(&mut self, expr: &'a LogicalExpr, frame: Frame) -> NodeId {
let mut children = Vec::new();
expr.for_each_child(&mut |child| children.push(child));
let children = children
.into_iter()
.enumerate()
.map(|(index, child)| {
let frame = match reach(expr, index) {
Reach::Body => self.body_frame(),
Reach::Always | Reach::Conditional => frame,
};
self.intern(child, frame)
})
.collect::<Vec<_>>();
let key = NodeKey {
expr,
children,
frame: node_reads_row(expr, self.oracle).then_some(frame),
};
let id = match self.dag.table.get(&key) {
Some(&id) => id,
None => {
let id = self.push(&key);
self.dag.table.insert(key, id);
id
}
};
self.dag.positions.insert(expr as *const LogicalExpr, id);
id
}
fn body_frame(&mut self) -> Frame {
let frame = Frame(self.next_frame);
self.next_frame += 1;
frame
}
fn push(&mut self, key: &NodeKey<'a>) -> NodeId {
let facts = key
.children
.iter()
.map(|child| {
let node = &self.dag.nodes[child.index()];
ChildFacts {
effects: node.effects,
checked_kind: node.checked_kind.clone(),
may_dereference: node.may_dereference,
}
})
.collect::<Vec<_>>();
let kinds = facts.iter().map(|facts| facts.checked_kind.clone()).collect::<Vec<_>>();
let id = NodeId(self.dag.nodes.len() as u32);
self.dag.nodes.push(DagNode {
expr: key.expr,
children: key.children.clone(),
effects: node_effects(key.expr, &facts, self.oracle),
checked_kind: key.expr.node_checked_kind(&kinds, &Schema::open()),
may_dereference: node_may_dereference(key.expr, &facts),
occurrences: Vec::new(),
first: None,
});
id
}
fn visit(&mut self, expr: &'a LogicalExpr, conditional: bool) {
let id = self.dag.positions[&(expr as *const LogicalExpr)];
let reused = self.dag.nodes[id.index()].first.is_some() && self.dag.first_is_reusable(id);
self.record(id, expr, conditional);
if reused {
return;
}
let mut children = Vec::new();
expr.for_each_child(&mut |child| children.push(child));
for (index, child) in children.into_iter().enumerate() {
match reach(expr, index) {
Reach::Always => self.visit(child, conditional),
Reach::Conditional => self.visit(child, true),
Reach::Body => {}
}
}
}
fn record(&mut self, id: NodeId, at: &'a LogicalExpr, conditional: bool) {
let order = self.order;
self.order += 1;
let node = &mut self.dag.nodes[id.index()];
if !conditional && node.first.is_none() {
node.first = Some(node.occurrences.len());
}
node.occurrences.push(Occurrence {
at: at as *const LogicalExpr,
root: self.root,
order,
conditional,
_region: std::marker::PhantomData,
});
}
}
pub fn build<'a>(roots: &[Root<'a>], oracle: &dyn EffectOracle) -> ExprDag<'a> {
let mut builder = Builder {
dag: ExprDag {
nodes: Vec::new(),
roots: Vec::with_capacity(roots.len()),
table: HashMap::new(),
positions: HashMap::new(),
holds_subquery: roots
.iter()
.map(|root| root.expr.any(|node| matches!(node, LogicalExpr::Subquery(_))))
.collect(),
},
oracle,
next_frame: roots.iter().map(|root| root.frame.0 + 1).max().unwrap_or(0),
root: 0,
order: 0,
};
for root in roots {
let id = builder.intern(root.expr, root.frame);
builder.dag.roots.push(id);
}
for (index, root) in roots.iter().enumerate() {
builder.root = index;
builder.visit(root.expr, false);
}
builder.dag
}
impl<'a> ExprDag<'a> {
pub fn len(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
pub fn checked_kind(&self, id: NodeId) -> Option<&Kind> {
self.nodes[id.index()].checked_kind.as_ref()
}
pub fn node_at(&self, at: *const LogicalExpr) -> Option<NodeId> {
self.positions.get(&at).copied()
}
pub fn kind_at(&self, at: &LogicalExpr) -> Option<&Kind> {
self.checked_kind(self.node_at(at)?)
}
#[cfg(test)]
pub fn find(&self, probe: &LogicalExpr, frame: Frame) -> Option<NodeId> {
let mut children = Vec::new();
probe.for_each_child(&mut |child| children.push(self.find(child, frame)));
let children = children.into_iter().collect::<Option<Vec<_>>>()?;
[None, Some(frame)].into_iter().find_map(|frame| {
let key = NodeKey {
expr: probe,
children: children.clone(),
frame,
};
self.table.get(&key).copied()
})
}
fn first_is_reusable(&self, id: NodeId) -> bool {
let node = &self.nodes[id.index()];
node.first.is_some_and(|first| {
!self.holds_subquery[node.occurrences[first].root]
&& !node.children.is_empty()
&& node.effects.pure()
})
}
pub fn shared(&self) -> Vec<SharedValue> {
let mut shared = self
.nodes
.iter()
.enumerate()
.filter(|(index, node)| {
self.first_is_reusable(NodeId(*index as u32))
&& node.first.is_some_and(|first| first + 1 < node.occurrences.len())
})
.map(|(_, node)| node)
.collect::<Vec<_>>();
shared.sort_by_key(|node| node.occurrences[node.first.unwrap_or(0)].order);
shared
.into_iter()
.map(|node| {
let first = node.first.unwrap_or(0);
SharedValue {
first: node.occurrences[first].at,
reuses: node.occurrences[first + 1..]
.iter()
.map(|occurrence| occurrence.at)
.collect(),
}
})
.collect()
}
}
#[cfg(test)]
mod tests {
use super::{Frame, Reach, Root, SHALLOW_EQ_CALLS, SharedValue, build, reach};
use crate::expr::logical::{
EffectOracle, EffectSet, LogicalExpr, LogicalLiteral, Schema, effects_of, lower_expr,
may_dereference,
};
use crate::expr::{BinaryOperator, Kind, Param};
struct Declared;
impl EffectOracle for Declared {
fn builtin(&self, name: &str) -> Option<EffectSet> {
Some(if name.starts_with("rand::") {
EffectSet::ENTROPY
} else {
EffectSet::PURE
})
}
fn closure_args(&self, _name: &str) -> Option<&'static [usize]> {
Some(&[])
}
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 expr(text: &str) -> LogicalExpr {
lower_expr(crate::syn::expr(text).expect("expression parses")).expect("expression lowers")
}
fn roots_in<'a>(exprs: &'a [LogicalExpr], frames: &[u32]) -> Vec<Root<'a>> {
exprs
.iter()
.zip(frames)
.map(|(expr, frame)| Root {
expr,
frame: Frame::new(*frame),
})
.collect()
}
fn shared_of(texts: &[&str]) -> (Vec<LogicalExpr>, usize, Vec<SharedValue>) {
let exprs = texts.iter().map(|text| expr(text)).collect::<Vec<_>>();
let (len, shared) = {
let roots = roots_in(&exprs, &vec![0; exprs.len()]);
let dag = build(&roots, &Declared);
(dag.len(), dag.shared())
};
(exprs, len, shared)
}
fn at(expr: &LogicalExpr) -> *const LogicalExpr {
expr as *const LogicalExpr
}
#[test]
fn gvn_merges_identical_subtrees() {
let (roots, len, shared) = shared_of(&["a * 2", "a * 2 + 1"]);
assert_eq!(len, 5);
let [value] = shared.as_slice() else {
panic!("one shared value, got {shared:?}");
};
assert_eq!(value.first, at(&roots[0]));
assert_eq!(value.reuses.len(), 1);
let LogicalExpr::Binary {
left,
..
} = &roots[1]
else {
panic!("a sum");
};
assert_eq!(value.reuses[0], at(left));
}
#[test]
fn a_conditional_first_occurrence_is_not_shared() {
let (_, _, shared) = shared_of(&["b AND a * 2 > 1", "a * 2"]);
assert!(shared.is_empty(), "{shared:?}");
}
#[test]
fn a_dominated_conditional_reuse_is_shared() {
let (roots, _, shared) = shared_of(&["a * 2 > 1 AND a * 2 < 9"]);
let [value] = shared.as_slice() else {
panic!("one shared value, got {shared:?}");
};
let LogicalExpr::Binary {
left,
right,
..
} = &roots[0]
else {
panic!("a conjunction");
};
let operand = |side: &LogicalExpr| {
let LogicalExpr::Binary {
left,
..
} = side
else {
panic!("a comparison, got {side:?}");
};
at(left)
};
assert_eq!(value.first, operand(left));
assert_eq!(value.reuses, vec![operand(right)]);
}
#[test]
fn body_occurrences_do_not_count() {
let (_, _, shared) = shared_of(&["arr[WHERE x * 2 > 1]", "x * 2"]);
assert!(shared.is_empty(), "{shared:?}");
}
#[test]
fn impure_is_never_shared() {
let (_, _, shared) = shared_of(&["rand::int(1, 9) + 1", "rand::int(1, 9) + 1"]);
assert!(shared.is_empty(), "{shared:?}");
}
#[test]
fn a_dereferencing_read_is_never_shared() {
let (_, _, shared) = shared_of(&["a.b + 1", "a.b + 1"]);
assert!(shared.is_empty(), "{shared:?}");
}
#[test]
fn dce_counts_only_reachable_nodes() {
let unfolded = [expr("IF true THEN a * 2 ELSE b * 3 END")];
let folded = [expr("a * 2")];
let dead = expr("b * 3");
let dag = build(&roots_in(&unfolded, &[0]), &Declared);
assert!(dag.find(&dead, Frame::new(0)).is_some());
let dag = build(&roots_in(&folded, &[0]), &Declared);
assert!(dag.find(&dead, Frame::new(0)).is_none());
assert_eq!(dag.len(), 3);
}
#[test]
fn a_subquery_root_cannot_hold_a_first_occurrence() {
let (_, _, shared) = shared_of(&["(SELECT * FROM t) + a * 2", "a * 2"]);
assert!(shared.is_empty(), "{shared:?}");
}
#[test]
fn the_nodes_of_a_reused_value_are_not_counted_again() {
let (_, _, shared) = shared_of(&["a * 2 + 1", "a * 2 + 1"]);
assert_eq!(shared.len(), 1, "{shared:?}");
}
#[test]
fn dag_records_each_nodes_proof() {
let root = [expr("<int> a + (a > 1)")];
let dag = build(&roots_in(&root, &[0]), &Declared);
let schema = Schema::open();
let mut compared = 0;
for (index, node) in dag.nodes.iter().enumerate() {
let id = super::NodeId(index as u32);
assert_eq!(dag.checked_kind(id), node.expr.checked_kind(&schema).as_ref());
compared += 1;
}
assert_eq!(compared, dag.len());
let of = |text: &str| {
let probe = expr(text);
let id = dag.find(&probe, Frame::new(0)).expect("the probe is in the DAG");
dag.checked_kind(id).cloned()
};
assert_eq!(of("a > 1"), Some(Kind::Bool));
assert_eq!(of("a"), None);
let LogicalExpr::Binary {
right,
..
} = &root[0]
else {
panic!("a sum");
};
assert_eq!(dag.kind_at(right), Some(&Kind::Bool));
assert_eq!(dag.kind_at(&root[0]), None);
}
fn expected(sample: &LogicalExpr) -> Vec<Reach> {
let count = sample.children().len();
let all = |reach: Reach| vec![reach; count];
let first_then = |rest: Reach| {
(0..count)
.map(|index| {
if index == 0 {
Reach::Always
} else {
rest
}
})
.collect()
};
match sample {
LogicalExpr::Array(_)
| LogicalExpr::Set(_)
| LogicalExpr::Object(_)
| LogicalExpr::RecordId(_) => all(Reach::Always),
LogicalExpr::Access {
..
}
| LogicalExpr::First(_)
| LogicalExpr::Last(_)
| LogicalExpr::Each(_)
| LogicalExpr::Flatten {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Throw(_) => all(Reach::Always),
LogicalExpr::Index {
..
} => first_then(Reach::Body),
LogicalExpr::Filter {
..
}
| LogicalExpr::Method {
..
}
| LogicalExpr::Destructure {
..
}
| LogicalExpr::Optional {
..
}
| LogicalExpr::Lookup {
..
}
| LogicalExpr::Recurse(_)
| LogicalExpr::Broadcast {
..
} => first_then(Reach::Body),
LogicalExpr::RepeatRecurse(_) | LogicalExpr::Closure(_) => all(Reach::Body),
LogicalExpr::SetField {
..
} => first_then(Reach::Conditional),
LogicalExpr::If(_) => first_then(Reach::Conditional),
LogicalExpr::Binary {
op,
..
} => {
if matches!(
op,
BinaryOperator::And
| BinaryOperator::Or
| BinaryOperator::NullCoalescing
| BinaryOperator::TenaryCondition
) {
first_then(Reach::Conditional)
} else {
all(Reach::Always)
}
}
LogicalExpr::Call(_)
| LogicalExpr::Invoke {
..
} => all(Reach::Always),
LogicalExpr::Literal(_)
| LogicalExpr::Param(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Break
| LogicalExpr::Continue
| LogicalExpr::Subquery(_) => Vec::new(),
}
}
fn marker(index: usize) -> LogicalExpr {
LogicalExpr::Param(Param::from(format!("c{index}")))
}
fn boxed(index: usize) -> Box<LogicalExpr> {
Box::new(marker(index))
}
#[test]
fn reach_is_pinned_per_variant() {
let binary = |op| LogicalExpr::Binary {
left: boxed(0),
op,
right: boxed(1),
};
let samples = vec![
LogicalExpr::Array(vec![marker(0), marker(1)]),
LogicalExpr::Set(vec![marker(0), marker(1)]),
LogicalExpr::Object(vec![("a".into(), marker(0)), ("b".into(), marker(1))]),
expr("t:[$c0, $c1]"),
LogicalExpr::Access {
base: boxed(0),
field: "f".into(),
},
LogicalExpr::Index {
base: boxed(0),
index: boxed(1),
},
LogicalExpr::First(boxed(0)),
LogicalExpr::Last(boxed(0)),
LogicalExpr::Each(boxed(0)),
LogicalExpr::Flatten {
base: boxed(0),
explicit: true,
},
LogicalExpr::Filter {
base: boxed(0),
predicate: boxed(1),
},
LogicalExpr::Method {
base: boxed(0),
name: "m".into(),
args: vec![marker(1), marker(2)],
},
expr("$c0.{ a: $c1, b: $c2 }"),
LogicalExpr::Optional {
base: boxed(0),
then: boxed(1),
},
expr("$c0->(likes WHERE x = $c1)"),
expr("$c0.{2}(.a[$c1])"),
LogicalExpr::RepeatRecurse(boxed(0)),
LogicalExpr::Broadcast {
base: boxed(0),
body: boxed(1),
flatten: false,
},
LogicalExpr::SetField {
base: boxed(0),
field: "k".into(),
value: boxed(1),
},
LogicalExpr::Prefix {
op: crate::expr::PrefixOperator::Negate,
expr: boxed(0),
},
LogicalExpr::Postfix {
expr: boxed(0),
op: crate::expr::logical::LogicalPostfixOperator::Range,
},
LogicalExpr::Invoke {
target: boxed(0),
args: vec![marker(1)],
},
binary(BinaryOperator::Add),
binary(BinaryOperator::And),
binary(BinaryOperator::Or),
binary(BinaryOperator::NullCoalescing),
binary(BinaryOperator::TenaryCondition),
expr("math::abs($c0)"),
expr("|$x: int| $x + $c0"),
expr("IF $c0 THEN $c1 ELSE IF $c2 THEN $c3 ELSE $c4 END"),
LogicalExpr::Throw(boxed(0)),
];
for sample in &samples {
let expected = expected(sample);
assert_eq!(sample.children().len(), expected.len(), "{sample:?}");
assert!(!expected.is_empty(), "{sample:?} has children");
for (index, want) in expected.into_iter().enumerate() {
assert_eq!(reach(sample, index), want, "child {index} of {sample:?}");
}
}
}
#[test]
fn a_set_field_value_does_not_hold_a_first_occurrence() {
let roots = [
LogicalExpr::SetField {
base: Box::new(expr("o")),
field: "k".into(),
value: Box::new(expr("a * 2")),
},
expr("a * 2"),
];
let dag = build(&roots_in(&roots, &[0, 0]), &Declared);
assert!(dag.shared().is_empty(), "{:?}", dag.shared());
}
#[test]
fn a_set_field_base_dominates_its_value() {
let roots = [LogicalExpr::SetField {
base: Box::new(expr("a * 2")),
field: "k".into(),
value: Box::new(expr("a * 2")),
}];
let dag = build(&roots_in(&roots, &[0]), &Declared);
let LogicalExpr::SetField {
base,
value,
..
} = &roots[0]
else {
panic!("a set-field");
};
assert_eq!(
dag.shared(),
vec![SharedValue {
first: at(base),
reuses: vec![at(value)],
}]
);
}
#[test]
fn an_if_condition_dominates_its_branches() {
let roots = [expr("IF a * 2 > 1 THEN a * 2 ELSE 0 END")];
let dag = build(&roots_in(&roots, &[0]), &Declared);
let shared = dag.shared();
let [value] = shared.as_slice() else {
panic!("one shared value, got {shared:?}");
};
assert_eq!(value.reuses.len(), 1);
let LogicalExpr::If(branches) = &roots[0] else {
panic!("an IF");
};
let LogicalExpr::Binary {
left,
..
} = &branches.branches[0].0
else {
panic!("a comparison");
};
assert_eq!(value.first, at(left));
assert_eq!(value.reuses[0], at(&branches.branches[0].1));
let (_, _, shared) = shared_of(&["IF b THEN 1 ELSE a * 2 END", "a * 2"]);
assert!(shared.is_empty(), "{shared:?}");
}
#[test]
fn a_conditional_occurrence_before_the_first_is_lowered_as_written() {
let (roots, _, shared) = shared_of(&["b AND a * 2 > 1", "a * 2", "a * 2 + 1"]);
let LogicalExpr::Binary {
left,
..
} = &roots[2]
else {
panic!("a sum");
};
assert_eq!(
shared,
vec![SharedValue {
first: at(&roots[1]),
reuses: vec![at(left)],
}]
);
}
#[test]
fn an_index_argument_is_a_body() {
let (_, _, shared) = shared_of(&["arr[a * 2]", "a * 2"]);
assert!(shared.is_empty(), "{shared:?}");
}
#[test]
fn frames_separate_row_reads() {
let roots = [expr("a * 2"), expr("a * 2")];
let dag = build(&roots_in(&roots, &[0, 1]), &Declared);
let probe = expr("a * 2");
let (first, second) =
(dag.find(&probe, Frame::new(0)).unwrap(), dag.find(&probe, Frame::new(1)).unwrap());
assert_ne!(first, second);
assert!(dag.shared().is_empty());
let roots = [expr("$p * 2"), expr("$p * 2")];
let dag = build(&roots_in(&roots, &[0, 1]), &Declared);
let probe = expr("$p * 2");
assert_eq!(dag.find(&probe, Frame::new(0)), dag.find(&probe, Frame::new(1)));
assert_eq!(dag.shared().len(), 1);
}
#[test]
fn a_body_read_never_merges_with_a_row_read() {
let roots = [expr("arr[WHERE x * 2 > 1]"), expr("x * 2")];
let dag = build(&roots_in(&roots, &[0, 0]), &Declared);
let LogicalExpr::Filter {
predicate,
..
} = &roots[0]
else {
panic!("a filter, got {:?}", roots[0]);
};
let LogicalExpr::Binary {
left: in_body,
..
} = &**predicate
else {
panic!("a comparison");
};
let in_body = dag.node_at(at(in_body)).unwrap();
let on_row = dag.node_at(at(&roots[1])).unwrap();
assert_ne!(in_body, on_row);
let field_of = |id: super::NodeId| dag.nodes[id.index()].children[0];
assert_ne!(field_of(in_body), field_of(on_row));
}
#[test]
fn facts_fold_from_children() {
let corpus = [
"a * 2",
"a * 2 + 1",
"b AND a * 2 > 1",
"a * 2 > 1 AND a * 2 < 9",
"arr[WHERE x * 2 > 1]",
"rand::int(1, 9) + 1",
"a.b + 1",
"<int> a + (a > 1)",
"<int> 1",
"<int> (1 > 0)",
"<string> (<int> v)",
"(1 > 0) AND (2 > 1)",
"(1 > 0) OR a",
"IF true THEN a * 2 ELSE b * 3 END",
"(SELECT * FROM t) + a * 2",
"-v",
"math::sqrt(v)",
"o[1]",
"[1, 2, a]",
"[1, 2, t:1]",
"{ a: 1, b: { c: t:1 } }",
"{ x: a }.x",
"{ x: 1 }.x.y",
"(<object> $v).f",
"(<string> b).x",
"a.{ x, y: z }",
"{ a: 1 }.{ a }",
"t:1.f",
"t:1.*",
"a.*",
"a[0]",
"a[$]",
"a.?.b",
"->likes->person",
"$this.f",
"$parent.f + 1",
"a ?? b",
"a ?: b",
"|$x: int| $x + 1",
"$f(1)",
"a.slice(1, 2)",
"t:[1, 2]",
"t:rand()",
"1..5",
"a..",
"$p * 2",
"fn::f(a) + 0",
];
let exprs = corpus.iter().map(|text| expr(text)).collect::<Vec<_>>();
let dag = build(&roots_in(&exprs, &vec![0; exprs.len()]), &Declared);
let schema = Schema::open();
assert!(!dag.is_empty());
for node in &dag.nodes {
assert_eq!(node.effects, effects_of(node.expr, &Declared), "{:?}", node.expr);
assert_eq!(node.checked_kind, node.expr.checked_kind(&schema), "{:?}", node.expr);
assert_eq!(node.may_dereference, may_dereference(node.expr), "{:?}", node.expr);
}
}
fn field(name: &str) -> LogicalExpr {
LogicalExpr::Field(name.into())
}
fn binary(left: LogicalExpr, op: BinaryOperator, right: LogicalExpr) -> LogicalExpr {
LogicalExpr::Binary {
left: Box::new(left),
op,
right: Box::new(right),
}
}
fn int(value: i64) -> LogicalExpr {
LogicalExpr::Literal(LogicalLiteral::Integer(value))
}
fn sum(n: usize) -> LogicalExpr {
let mut node = field(&format!("a{n}"));
for _ in 0..3 {
node =
binary(binary(node, BinaryOperator::Multiply, int(2)), BinaryOperator::Add, int(1));
}
node
}
#[test]
fn build_is_linear() {
const DISTINCT: usize = 5_000;
let mut exprs = (0..DISTINCT).map(sum).collect::<Vec<_>>();
exprs.extend((0..DISTINCT).map(sum));
SHALLOW_EQ_CALLS.with(|calls| calls.set(0));
let dag = build(&roots_in(&exprs, &vec![0; exprs.len()]), &Declared);
let calls = SHALLOW_EQ_CALLS.with(|calls| calls.get());
let visited: usize = exprs.iter().map(count).sum();
assert!(calls <= 4 * visited, "{calls} comparisons over {visited} positions");
assert_eq!(dag.len(), DISTINCT * 7 + 2);
assert_eq!(dag.shared().len(), DISTINCT);
}
fn count(expr: &LogicalExpr) -> usize {
let mut positions = 0;
let _ = expr.visit(&mut |_| {
positions += 1;
std::ops::ControlFlow::<()>::Continue(())
});
positions
}
}