use super::expr::{
LogicalCall, LogicalDestructureField, LogicalExpr, LogicalField, LogicalFields, LogicalLiteral,
LogicalLookup, LogicalRecurseInstruction,
};
use super::{EvalFrame, LogicalOp};
pub const LINK: &str = "\u{0}trace::link";
pub const ANCHOR: &str = "\u{0}trace::anchor";
pub fn is_internal(name: &str) -> bool {
name == LINK || name == ANCHOR
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
pub enum LookupTrace {
#[default]
None,
Traced,
Partial,
Inner,
}
impl LookupTrace {
fn changed(self) -> Self {
match self {
LookupTrace::Traced | LookupTrace::Partial | LookupTrace::Inner => LookupTrace::Partial,
LookupTrace::None => LookupTrace::None,
}
}
fn below(self) -> Self {
match self {
LookupTrace::Traced | LookupTrace::Inner => LookupTrace::Inner,
LookupTrace::Partial | LookupTrace::None => self,
}
}
}
pub fn mark(op: &mut LogicalOp) {
mark_op(op, LookupTrace::Traced);
}
pub fn mark_fields(fields: &mut LogicalFields, role: LookupTrace) {
fields_in(fields, role);
}
fn mark_op(op: &mut LogicalOp, role: LookupTrace) {
if let LogicalOp::Write(_) = op {
for scalar in op.scalars_mut() {
expr(scalar, LookupTrace::None);
}
if let LogicalOp::Write(write) = op {
write.trace = role;
}
return;
}
match op {
LogicalOp::Project(project) => {
fields_in(&mut project.fields, role);
for omit in &mut project.omit {
expr(omit, LookupTrace::None);
}
mark_op(&mut project.input, role);
}
LogicalOp::Values(values) => expr(&mut values.expr, role),
LogicalOp::Eval(eval) => expr(&mut eval.expr, role),
LogicalOp::Source(source) => {
let mut exprs = Vec::new();
source.source.exprs_mut(&mut exprs);
for value in exprs {
expr(value, role);
}
}
LogicalOp::Aggregate(aggregate) => {
for group in &mut aggregate.group {
expr(group, LookupTrace::None);
}
fields_in(&mut aggregate.fields, role.changed());
mark_op(&mut aggregate.input, role);
}
LogicalOp::Window(_) => {
let changed = role.changed();
for scalar in op.scalars_mut() {
expr(scalar, changed);
}
for child in op.children_mut() {
mark_op(child, role);
}
}
LogicalOp::Let(binding) => mark_op(&mut binding.value, role),
LogicalOp::Return(ret) => {
mark_op(&mut ret.what, role);
for fetch in &mut ret.fetch {
expr(fetch, LookupTrace::None);
}
}
LogicalOp::Limit(_) | LogicalOp::Distinct(_) | LogicalOp::Filter(_) => {
for scalar in op.scalars_mut() {
expr(scalar, LookupTrace::None);
}
let changed = role.changed();
for child in op.children_mut() {
mark_op(child, changed);
}
}
LogicalOp::Foreach(foreach) => {
expr(&mut foreach.range, LookupTrace::None);
mark_op(&mut foreach.body, LookupTrace::None);
}
other @ LogicalOp::Match(_)
| other @ LogicalOp::Subquery(_)
| other @ LogicalOp::Write(_)
| other @ LogicalOp::Ddl(_)
| other @ LogicalOp::UnionAll(_)
| other @ LogicalOp::Join(_)
| other @ LogicalOp::PermissionFilter(_)
| other @ LogicalOp::Split(_)
| other @ LogicalOp::Sort(_)
| other @ LogicalOp::Fetch(_)
| other @ LogicalOp::Timeout(_)
| other @ LogicalOp::VersionScope(_)
| other @ LogicalOp::Only(_)
| other @ LogicalOp::Explain(_)
| other @ LogicalOp::Sequence(_)
| other @ LogicalOp::If(_)
| other @ LogicalOp::Throw(_)
| other @ LogicalOp::Break(_)
| other @ LogicalOp::Continue(_)
| other @ LogicalOp::Info(_)
| other @ LogicalOp::Sleep(_) => {
for scalar in other.scalars_mut() {
expr(scalar, LookupTrace::None);
}
for child in other.children_mut() {
mark_op(child, role);
}
}
}
}
fn fields_in(fields: &mut LogicalFields, role: LookupTrace) {
match fields {
LogicalFields::Value {
expr: value,
..
} => expr(value, role),
LogicalFields::Select(fields) => {
for field in fields {
if let LogicalField::Single {
expr: value,
alias,
frame,
..
} = field
{
let role = if *frame == EvalFrame::caller() {
role
} else {
LookupTrace::None
};
let unmarked = (alias.is_none() && !matches!(role, LookupTrace::None))
.then(|| value.clone());
expr(value, role);
if let Some(unmarked) = unmarked
&& unmarked != *value
{
*alias = Some(unmarked.named_after_gates().output_path());
}
}
}
}
}
}
fn lookup_in(lookup: &mut LogicalLookup, role: LookupTrace) {
lookup.trace = role;
if let Some(fields) = &mut lookup.expr {
fields_in(fields, role);
}
if let Some(cond) = &mut lookup.cond {
expr(cond, LookupTrace::None);
}
for clause in [&mut lookup.split, &mut lookup.group].into_iter().flatten() {
for value in clause {
expr(value, LookupTrace::None);
}
}
if let Some(order) = &mut lookup.order {
let mut keys = Vec::new();
order.exprs_mut(&mut keys);
for key in keys {
expr(key, LookupTrace::None);
}
}
for page in [&mut lookup.limit, &mut lookup.start].into_iter().flatten() {
expr(page, LookupTrace::None);
}
}
fn destructure_in(fields: &mut [LogicalDestructureField], role: LookupTrace) {
for field in fields {
match field {
LogicalDestructureField::Aliased(_, body) => expr(body, role),
LogicalDestructureField::Destructure(_, nested) => destructure_in(nested, role),
LogicalDestructureField::All(_)
| LogicalDestructureField::Field(_)
| LogicalDestructureField::Rest => {}
}
}
}
fn link_read(read: &mut LogicalExpr, role: LookupTrace) {
if matches!(role, LookupTrace::None) {
return;
}
let Some((holder, field)) = field_read(cuts(read).unwrap_or(read)) else {
return;
};
let holder = match role {
LookupTrace::Partial => LogicalExpr::Literal(LogicalLiteral::None),
LookupTrace::None | LookupTrace::Traced | LookupTrace::Inner => holder,
};
let value = std::mem::replace(read, LogicalExpr::Literal(LogicalLiteral::None));
*read = LogicalExpr::Call(Box::new(LogicalCall {
receiver: crate::expr::Function::Normal(LINK.to_owned()),
args: vec![value, holder, LogicalExpr::Literal(LogicalLiteral::String(field))],
}));
}
fn field_read(read: &LogicalExpr) -> Option<(LogicalExpr, surrealdb_strand::Strand)> {
if let LogicalExpr::Field(field) = read {
return Some((LogicalExpr::Doc, field.clone()));
}
let LogicalExpr::Access {
base,
field,
} = read
else {
return None;
};
let holder = if rereads(base) {
(**base).clone()
} else {
LogicalExpr::Literal(LogicalLiteral::None)
};
Some((holder, field.clone()))
}
fn rereads(e: &LogicalExpr) -> bool {
if matches!(
e,
LogicalExpr::Literal(_)
| LogicalExpr::Param(_)
| LogicalExpr::Table(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
) {
return true;
}
if let LogicalExpr::Access {
base,
..
}
| LogicalExpr::First(base)
| LogicalExpr::Last(base)
| LogicalExpr::Each(base)
| LogicalExpr::Flatten {
base,
..
} = e
{
return rereads(base);
}
if let LogicalExpr::Index {
base,
index,
} = e
{
return rereads(base) && rereads(index);
}
if let LogicalExpr::RecordId(_) = e {
return e.children().into_iter().all(rereads);
}
if let LogicalExpr::Call(call) = e
&& matches!(&call.receiver, crate::expr::Function::Normal(name) if name == LINK)
{
return call.args.iter().all(rereads);
}
false
}
fn cuts(e: &LogicalExpr) -> Option<&LogicalExpr> {
if let LogicalExpr::Index {
base,
..
}
| LogicalExpr::First(base)
| LogicalExpr::Last(base)
| LogicalExpr::Filter {
base,
..
} = e
{
return Some(base);
}
None
}
fn has_lookup(e: &LogicalExpr) -> bool {
if let LogicalExpr::Lookup {
..
} = e
{
return true;
}
if let LogicalExpr::Subquery(_) = e {
return false;
}
e.children().into_iter().any(has_lookup)
}
fn has_subquery(e: &LogicalExpr) -> bool {
matches!(e, LogicalExpr::Subquery(_)) || e.children().into_iter().any(has_subquery)
}
fn unname_link_holders(e: &mut LogicalExpr) {
if let LogicalExpr::Call(call) = e
&& matches!(&call.receiver, crate::expr::Function::Normal(name) if name == LINK)
&& let Some(holder) = call.args.get_mut(1)
{
*holder = LogicalExpr::Literal(LogicalLiteral::None);
}
for child in e.children_mut() {
unname_link_holders(child);
}
}
fn reads_through_links(e: &LogicalExpr) -> bool {
if let LogicalExpr::Access {
base,
..
}
| LogicalExpr::Each(base)
| LogicalExpr::Destructure {
base,
..
} = e && field_read(base).is_some()
{
return true;
}
if let LogicalExpr::Subquery(_) = e {
return false;
}
e.children().into_iter().any(reads_through_links)
}
fn expr(e: &mut LogicalExpr, role: LookupTrace) {
if role == LookupTrace::Traced && cuts(e).is_some_and(has_subquery) {
expr(e, LookupTrace::Partial);
return;
}
if role == LookupTrace::Traced && cuts(e).is_some_and(has_lookup) {
expr(e, LookupTrace::Inner);
unname_link_holders(e);
let step = std::mem::replace(e, LogicalExpr::Literal(LogicalLiteral::None));
*e = LogicalExpr::Call(Box::new(LogicalCall {
receiver: crate::expr::Function::Normal(ANCHOR.to_owned()),
args: vec![step],
}));
return;
}
if role == LookupTrace::Traced && cuts(e).is_some_and(reads_through_links) {
expr(e, LookupTrace::Partial);
let step = std::mem::replace(e, LogicalExpr::Literal(LogicalLiteral::None));
*e = LogicalExpr::Call(Box::new(LogicalCall {
receiver: crate::expr::Function::Normal(ANCHOR.to_owned()),
args: vec![step, LogicalExpr::Literal(LogicalLiteral::Bool(true))],
}));
return;
}
match e {
LogicalExpr::Lookup {
base,
lookup,
} => {
lookup_in(lookup, role);
expr(base, role.below());
link_read(base, role.below());
}
LogicalExpr::Access {
base,
..
}
| LogicalExpr::Each(base) => {
expr(base, role);
link_read(base, role);
}
LogicalExpr::First(base)
| LogicalExpr::Last(base)
| LogicalExpr::Flatten {
base,
..
}
| LogicalExpr::RepeatRecurse(base) => expr(base, role),
LogicalExpr::Index {
base,
index,
} => {
expr(base, role);
expr(index, LookupTrace::None);
}
LogicalExpr::Filter {
base,
predicate,
} => {
expr(base, role);
expr(predicate, LookupTrace::None);
}
LogicalExpr::Optional {
base,
then,
}
| LogicalExpr::Broadcast {
base,
body: then,
..
} => {
expr(base, role);
expr(then, role);
}
LogicalExpr::SetField {
base,
value,
..
} => {
expr(base, role);
expr(value, role);
}
LogicalExpr::Destructure {
base,
fields,
} => {
expr(base, role);
link_read(base, role);
destructure_in(fields, role);
}
LogicalExpr::Recurse(recurse) => {
expr(&mut recurse.base, role);
if let Some(path) = &mut recurse.path {
expr(path.body_mut(), role);
}
if let Some(LogicalRecurseInstruction::Shortest {
expects,
..
}) = &mut recurse.instruction
{
expr(expects, LookupTrace::None);
}
}
LogicalExpr::Array(items) | LogicalExpr::Set(items) => {
for item in items {
expr(item, role);
}
}
LogicalExpr::Object(entries) => {
for (_, value) in entries {
expr(value, role);
}
}
LogicalExpr::If(branching) => {
for (cond, value) in &mut branching.branches {
expr(cond, LookupTrace::None);
expr(value, role);
}
if let Some(otherwise) = &mut branching.otherwise {
expr(otherwise, role);
}
}
LogicalExpr::Subquery(op) => mark_op(op, role),
LogicalExpr::RecordId(_) => {
for key in e.children_mut() {
expr(key, LookupTrace::None);
}
}
LogicalExpr::Method {
..
}
| LogicalExpr::Prefix {
..
}
| LogicalExpr::Postfix {
..
}
| LogicalExpr::Invoke {
..
}
| LogicalExpr::Binary {
..
}
| LogicalExpr::Call(_)
| LogicalExpr::Closure(_)
| LogicalExpr::Throw(_) => {
let role = role.changed();
for child in e.children_mut() {
expr(child, role);
}
}
LogicalExpr::Literal(_)
| LogicalExpr::Param(_)
| LogicalExpr::Table(_)
| LogicalExpr::Mock(_)
| LogicalExpr::Constant(_)
| LogicalExpr::Field(_)
| LogicalExpr::Doc
| LogicalExpr::Current
| LogicalExpr::Break
| LogicalExpr::Continue => {}
}
}