#![deny(clippy::wildcard_enum_match_arm)]
use std::collections::{HashMap, HashSet, VecDeque};
use crate::expr::function::{Function, FunctionCall};
use crate::expr::lookup::{Lookup, LookupSubject};
use crate::expr::statements::SelectStatement;
use crate::expr::visit::{Visit, Visitor};
use crate::expr::{Expr, Idiom, Literal, Part};
const TARGET: &str = "surrealdb::core::perms";
#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)]
pub struct ComputedDeps {
pub fields: Vec<String>,
pub is_complete: bool,
}
pub fn extract_computed_deps(expr: &Expr) -> ComputedDeps {
extract_computed_deps_binding(expr, &[])
}
pub fn extract_computed_deps_binding(expr: &Expr, bound: &[&str]) -> ComputedDeps {
let mut extractor = FieldDependencyExtractor {
deps: HashSet::new(),
is_complete: true,
bound,
nested: 0,
};
let _ = extractor.visit_expr(expr);
ComputedDeps {
fields: {
let mut fields: Vec<String> = extractor.deps.into_iter().collect();
fields.sort();
fields
},
is_complete: extractor.is_complete,
}
}
fn field_name_from_part(part: &Part) -> Option<String> {
if let Part::Field(name) | Part::Value(Expr::Literal(Literal::String(name))) = part {
Some(name.as_str().to_owned())
} else {
None
}
}
fn is_session_param(param: &crate::expr::Param) -> bool {
surrealdb_cnf::PROTECTED_PARAM_NAMES.contains(¶m.as_str())
}
fn is_plain_lookup(lookup: &Lookup) -> bool {
let Lookup {
kind: _,
expr,
only: _,
what,
cond,
split,
group,
order,
limit,
start,
alias,
} = lookup;
expr.is_none()
&& cond.is_none()
&& split.is_none()
&& group.is_none()
&& order.is_none()
&& limit.is_none()
&& start.is_none()
&& alias.is_none()
&& what.iter().all(|subject| matches!(subject, LookupSubject::Table { .. }))
}
struct FieldDependencyExtractor<'b> {
deps: HashSet<String>,
is_complete: bool,
bound: &'b [&'b str],
nested: u32,
}
impl FieldDependencyExtractor<'_> {
fn reads_no_field(&self, param: &crate::expr::Param) -> bool {
is_session_param(param) || self.bound.contains(¶m.as_str())
}
}
impl Visitor for FieldDependencyExtractor<'_> {
type Error = std::convert::Infallible;
fn visit_idiom(&mut self, idiom: &Idiom) -> Result<(), Self::Error> {
let consumed = match idiom.0.as_slice() {
[Part::Field(name), ..] => {
if self.nested == 0 {
self.deps.insert(name.as_str().to_owned());
}
1
}
[Part::Lookup(lookup), ..] if self.nested == 0 && is_plain_lookup(lookup) => {
self.deps.insert("id".to_owned());
1
}
[Part::Start(Expr::Param(p)), second, ..] if matches!(p.as_str(), "this" | "self") => {
match field_name_from_part(second) {
Some(name) => {
if self.nested == 0 {
self.deps.insert(name);
}
2
}
None => 0,
}
}
[Part::Start(Expr::Param(p)), second, ..] if p.as_str() == "parent" => {
self.is_complete = false;
match field_name_from_part(second) {
Some(name) => {
if self.nested == 1 {
self.deps.insert(name);
}
2
}
None => 0,
}
}
_ => 0,
};
for p in idiom.0.iter().skip(consumed) {
self.visit_part(p)?;
}
Ok(())
}
fn visit_expr(&mut self, expr: &Expr) -> Result<(), Self::Error> {
match expr {
Expr::Literal(_)
| Expr::Idiom(_)
| Expr::Table(_)
| Expr::Mock(_)
| Expr::Constant(_)
| Expr::Break
| Expr::Continue
| Expr::Prefix { .. }
| Expr::Postfix { .. }
| Expr::Binary { .. }
| Expr::Block(_)
| Expr::IfElse(_)
| Expr::Foreach(_)
| Expr::Let(_)
| Expr::Return(_)
| Expr::Throw(_)
| Expr::Explain { .. }
| Expr::Sleep(_)
| Expr::Info(_) => {
expr.visit(self)?;
}
Expr::Select(select) => {
self.is_complete = false;
self.visit_select(select)?;
}
Expr::Create(_)
| Expr::Update(_)
| Expr::Upsert(_)
| Expr::Delete(_)
| Expr::Relate(_)
| Expr::Insert(_)
| Expr::Closure(_)
| Expr::Define(_)
| Expr::Remove(_)
| Expr::Rebuild(_)
| Expr::Alter(_) => {
self.is_complete = false;
expr.visit(self)?;
}
Expr::Param(param) if self.reads_no_field(param) => {}
Expr::Param(_) => {
self.is_complete = false;
}
Expr::FunctionCall(call) => {
self.visit_function_call(call)?;
}
}
Ok(())
}
fn visit_select(&mut self, select: &SelectStatement) -> Result<(), Self::Error> {
let SelectStatement {
fields,
omit,
only: _,
what,
with: _,
cond,
split,
group,
order,
limit,
start,
fetch,
version,
timeout,
explain: _,
tempfiles: _,
for_update: _,
} = select;
let selects_outer_doc =
!what.is_empty() && what.iter().all(|target| self.is_outer_doc_target(target));
for v in what {
self.visit_expr(v)?;
}
if let Some(limit) = limit {
self.visit_expr(&limit.0)?;
}
if let Some(start) = start {
self.visit_expr(&start.0)?;
}
self.visit_expr(version)?;
self.visit_expr(timeout)?;
let prev_nested = self.nested;
self.nested = if selects_outer_doc {
0
} else {
self.nested + 1
};
self.visit_fields(fields)?;
for v in omit {
self.visit_expr(v)?;
}
if let Some(cond) = cond {
self.visit_expr(&cond.0)?;
}
if let Some(split) = split {
for v in &split.0 {
self.visit_idiom(&v.0)?;
}
}
if let Some(group) = group {
for v in &group.0 {
self.visit_idiom(&v.0)?;
}
}
if let Some(order) = order {
self.visit_ordering(order)?;
}
if let Some(fetch) = fetch {
for v in fetch.iter() {
self.visit_expr(&v.0)?;
}
}
self.nested = prev_nested;
Ok(())
}
fn visit_part(&mut self, part: &Part) -> Result<(), Self::Error> {
match part {
Part::All
| Part::Flatten
| Part::Last
| Part::First
| Part::Field(_)
| Part::Optional
| Part::RepeatRecurse => {}
Part::Doc => {
self.is_complete = false;
}
Part::Where(_) => {
self.nested += 1;
part.visit(self)?;
self.nested -= 1;
}
Part::Value(_) | Part::Destructure(_) | Part::Recurse(_, _, _) => {
part.visit(self)?;
}
Part::Start(Expr::Param(param)) if self.reads_no_field(param) => {}
Part::Lookup(_) | Part::Start(_) | Part::Method(_, _) => {
self.is_complete = false;
part.visit(self)?;
}
}
Ok(())
}
}
impl FieldDependencyExtractor<'_> {
fn is_outer_doc_target(&self, expr: &Expr) -> bool {
if let Expr::Param(p) = expr {
match p.as_str() {
"this" | "self" => self.nested == 0,
"parent" => self.nested <= 1,
_ => false,
}
} else {
false
}
}
fn visit_function_call(&mut self, call: &FunctionCall) -> Result<(), std::convert::Infallible> {
match &call.receiver {
Function::Normal(name) => match name.as_str() {
"type::field" => self.analyse_type_field(&call.arguments),
"type::fields" => self.analyse_type_fields(&call.arguments),
_ => {}
},
Function::Model(_) => {}
Function::Custom(_)
| Function::Script(_)
| Function::Module(..)
| Function::Silo {
..
} => {
self.is_complete = false;
}
}
call.visit(self)?;
Ok(())
}
fn analyse_type_field(&mut self, args: &[Expr]) {
match args {
[Expr::Literal(Literal::String(s))] => match parse_idiom_root(s.as_str()) {
Some(root) => {
if self.nested == 0 {
self.deps.insert(root);
}
}
None => {
self.is_complete = false;
}
},
_ => {
self.is_complete = false;
}
}
}
fn analyse_type_fields(&mut self, args: &[Expr]) {
let [Expr::Literal(Literal::Array(items))] = args else {
self.is_complete = false;
return;
};
let mut pending = Vec::with_capacity(items.len());
for item in items {
let Expr::Literal(Literal::String(s)) = item else {
self.is_complete = false;
return;
};
let Some(root) = parse_idiom_root(s.as_str()) else {
self.is_complete = false;
return;
};
pending.push(root);
}
if self.nested == 0 {
self.deps.extend(pending);
}
}
}
fn parse_idiom_root(s: &str) -> Option<String> {
let idi: Idiom = crate::parser::idiom(s).ok()?;
if let Part::Field(name) = idi.0.first()? {
Some(name.as_str().to_owned())
} else {
None
}
}
pub fn warn_incomplete_perm_deps(table: &str, field: &str) {
tracing::warn!(
target: TARGET,
table = %table,
field = %field,
"Field-permission expression has opaque dependencies; \
all computed fields on the named table will be evaluated for every \
row. Inspect with `INFO FOR TABLE`."
);
}
pub fn topological_sort_computed_fields(fields: &[(String, Vec<String>)]) -> Vec<usize> {
if fields.is_empty() {
return Vec::new();
}
let name_to_idx: HashMap<&str, usize> =
fields.iter().enumerate().map(|(i, (name, _))| (name.as_str(), i)).collect();
let mut in_degree = vec![0usize; fields.len()];
let mut dependents: Vec<Vec<usize>> = vec![Vec::new(); fields.len()];
for (idx, (_, deps)) in fields.iter().enumerate() {
for dep in deps {
if let Some(&dep_idx) = name_to_idx.get(dep.as_str()) {
in_degree[idx] += 1;
dependents[dep_idx].push(idx);
}
}
}
let mut queue: VecDeque<usize> = VecDeque::new();
for (idx, °) in in_degree.iter().enumerate() {
if deg == 0 {
queue.push_back(idx);
}
}
let mut result = Vec::with_capacity(fields.len());
while let Some(idx) = queue.pop_front() {
result.push(idx);
for &dependent in &dependents[idx] {
in_degree[dependent] -= 1;
if in_degree[dependent] == 0 {
queue.push_back(dependent);
}
}
}
if result.len() < fields.len() {
for idx in 0..fields.len() {
if !result.contains(&idx) {
result.push(idx);
}
}
}
result
}
pub fn resolve_required_computed_fields(
needed: &HashSet<String>,
computed_deps: &HashMap<String, ComputedDeps>,
) -> Option<HashSet<String>> {
let mut required: HashSet<String> = HashSet::new();
let mut worklist: Vec<String> = needed.iter().cloned().collect();
while let Some(field) = worklist.pop() {
if !required.insert(field.clone()) {
continue; }
if let Some(deps) = computed_deps.get(&field) {
if !deps.is_complete {
return None;
}
for dep in &deps.fields {
if !required.contains(dep) {
worklist.push(dep.clone());
}
}
}
}
Some(required)
}
#[cfg(test)]
mod tests {
use surrealdb_strand::Strand;
use super::*;
use crate::expr::operator::BinaryOperator;
use crate::expr::{Literal, Part};
fn extract(expr: &Expr) -> ComputedDeps {
extract_computed_deps(expr)
}
fn field_expr(name: &str) -> Expr {
Expr::Idiom(Idiom(vec![Part::Field(name.into())]))
}
fn int_expr(n: i64) -> Expr {
Expr::Literal(Literal::Integer(n))
}
fn str_lit(s: &str) -> Expr {
Expr::Literal(Literal::String(Strand::new(s)))
}
fn fn_call(name: &str, args: Vec<Expr>) -> Expr {
Expr::FunctionCall(Box::new(crate::expr::function::FunctionCall {
receiver: crate::expr::function::Function::Normal(name.to_owned()),
arguments: args,
}))
}
#[test]
fn simple_field_reference() {
let expr = field_expr("b");
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["b"]);
assert!(deps.is_complete);
}
#[test]
fn binary_expression_two_fields() {
let expr = Expr::Binary {
left: Box::new(field_expr("b")),
op: BinaryOperator::Add,
right: Box::new(field_expr("c")),
};
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["b", "c"]);
assert!(deps.is_complete);
}
#[test]
fn field_plus_literal() {
let expr = Expr::Binary {
left: Box::new(field_expr("d")),
op: BinaryOperator::Add,
right: Box::new(int_expr(1)),
};
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["d"]);
assert!(deps.is_complete);
}
#[test]
fn nested_field_access() {
let expr = Expr::Idiom(Idiom(vec![
Part::Field(Strand::new_static("user")),
Part::Field(Strand::new_static("name")),
Part::Field(Strand::new_static("first")),
]));
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["user"]);
assert!(deps.is_complete);
}
#[test]
fn param_marks_incomplete() {
let expr = Expr::Param(crate::expr::Param::from("param".to_string()));
let deps = extract(&expr);
assert!(deps.fields.is_empty());
assert!(!deps.is_complete);
}
#[test]
fn no_deps_literal_only() {
let expr = Expr::Binary {
left: Box::new(int_expr(55)),
op: BinaryOperator::Multiply,
right: Box::new(int_expr(1000)),
};
let deps = extract(&expr);
assert!(deps.fields.is_empty());
assert!(deps.is_complete);
}
#[test]
fn deduplicates_deps() {
let expr = Expr::Binary {
left: Box::new(field_expr("a")),
op: BinaryOperator::Add,
right: Box::new(field_expr("a")),
};
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a"]);
assert!(deps.is_complete);
}
#[test]
fn self_reference() {
let expr = Expr::Binary {
left: Box::new(field_expr("a")),
op: BinaryOperator::Multiply,
right: Box::new(int_expr(2)),
};
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a"]);
assert!(deps.is_complete);
}
fn this_field_expr(name: &str) -> Expr {
Expr::Idiom(Idiom(vec![
Part::Start(Expr::Param(crate::expr::Param::from("this".to_string()))),
Part::Field(name.into()),
]))
}
fn self_field_expr(name: &str) -> Expr {
Expr::Idiom(Idiom(vec![
Part::Start(Expr::Param(crate::expr::Param::from("self".to_string()))),
Part::Field(name.into()),
]))
}
#[test]
fn this_dot_field() {
let deps = extract(&this_field_expr("a"));
assert_eq!(deps.fields, vec!["a"]);
assert!(deps.is_complete);
}
#[test]
fn self_dot_field() {
let deps = extract(&self_field_expr("a"));
assert_eq!(deps.fields, vec!["a"]);
assert!(deps.is_complete);
}
#[test]
fn this_dot_nested() {
let expr = Expr::Idiom(Idiom(vec![
Part::Start(Expr::Param(crate::expr::Param::from("this".to_string()))),
Part::Field(Strand::new_static("a")),
Part::Field(Strand::new_static("b")),
Part::Field(Strand::new_static("c")),
]));
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a"]);
assert!(deps.is_complete);
}
#[test]
fn this_dot_field_in_binary() {
let expr = Expr::Binary {
left: Box::new(this_field_expr("a")),
op: BinaryOperator::Add,
right: Box::new(this_field_expr("b")),
};
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a", "b"]);
assert!(deps.is_complete);
}
#[test]
fn mixed_bare_and_this() {
let expr = Expr::Binary {
left: Box::new(Expr::Binary {
left: Box::new(field_expr("a")),
op: BinaryOperator::Add,
right: Box::new(this_field_expr("b")),
}),
op: BinaryOperator::Add,
right: Box::new(self_field_expr("c")),
};
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a", "b", "c"]);
assert!(deps.is_complete);
}
#[test]
fn this_in_function_args() {
use crate::expr::function::{Function, FunctionCall};
let expr = Expr::FunctionCall(Box::new(FunctionCall {
receiver: Function::Normal("math::sum".to_string()),
arguments: vec![Expr::Literal(Literal::Array(vec![
this_field_expr("a"),
field_expr("b"),
self_field_expr("c"),
]))],
}));
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a", "b", "c"]);
assert!(deps.is_complete);
}
#[test]
fn this_in_nested_parens() {
let expr = Expr::Binary {
left: Box::new(field_expr("a")),
op: BinaryOperator::Add,
right: Box::new(Expr::Binary {
left: Box::new(this_field_expr("b")),
op: BinaryOperator::Add,
right: Box::new(self_field_expr("c")),
}),
};
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a", "b", "c"]);
assert!(deps.is_complete);
}
#[test]
fn doc_part_marks_incomplete() {
let at_c = Expr::Idiom(Idiom(vec![Part::Doc, Part::Field("c".into())]));
let deps = extract(&at_c);
assert!(deps.fields.is_empty());
assert!(!deps.is_complete);
let sum = Expr::Binary {
left: Box::new(at_c),
op: BinaryOperator::Add,
right: Box::new(int_expr(1)),
};
assert!(!extract(&sum).is_complete);
}
#[test]
fn this_alone_marks_incomplete() {
let expr = Expr::Param(crate::expr::Param::from("this".to_string()));
let deps = extract(&expr);
assert!(deps.fields.is_empty());
assert!(!deps.is_complete);
}
#[test]
fn this_dot_wildcard_marks_incomplete() {
let expr = Expr::Idiom(Idiom(vec![
Part::Start(Expr::Param(crate::expr::Param::from("this".to_string()))),
Part::All,
]));
let deps = extract(&expr);
assert!(deps.fields.is_empty());
assert!(!deps.is_complete);
}
#[test]
fn this_bracket_string_field() {
let expr = Expr::Idiom(Idiom(vec![
Part::Start(Expr::Param(crate::expr::Param::from("this".to_string()))),
Part::Value(Expr::Literal(Literal::String(Strand::new_static("a")))),
]));
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a"]);
assert!(deps.is_complete);
}
#[test]
fn self_bracket_string_field() {
let expr = Expr::Idiom(Idiom(vec![
Part::Start(Expr::Param(crate::expr::Param::from("self".to_string()))),
Part::Value(Expr::Literal(Literal::String(Strand::new_static("c")))),
]));
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["c"]);
assert!(deps.is_complete);
}
#[test]
fn mixed_dot_and_bracket() {
let expr = Expr::Binary {
left: Box::new(field_expr("a")),
op: BinaryOperator::Add,
right: Box::new(Expr::Binary {
left: Box::new(this_field_expr("b")),
op: BinaryOperator::Add,
right: Box::new(Expr::Idiom(Idiom(vec![
Part::Start(Expr::Param(crate::expr::Param::from("self".to_string()))),
Part::Value(Expr::Literal(Literal::String(Strand::new_static("c")))),
]))),
}),
};
let deps = extract(&expr);
assert_eq!(deps.fields, vec!["a", "b", "c"]);
assert!(deps.is_complete);
}
#[test]
fn subquery_names_no_field_of_the_document() {
let deps =
extract(&parse("(SELECT VALUE loc FROM child WHERE ref = $parent.id LIMIT 1)[0]"));
assert_eq!(deps.fields, vec!["id"]);
assert!(!deps.is_complete);
let deps = extract(&parse("(SELECT VALUE name FROM $this.members WHERE kind = 1)"));
assert_eq!(deps.fields, vec!["members"]);
assert!(!deps.is_complete);
let deps = extract(&parse(
"(SELECT VALUE type::field('sub_a') FROM child WHERE type::fields(['sub_b', 'sub_c']) != NONE)",
));
assert!(deps.fields.is_empty(), "{deps:?}");
assert!(!deps.is_complete);
let deps = extract(&parse(
"(SELECT VALUE child_field FROM child LIMIT lim START st VERSION ver TIMEOUT dur)",
));
assert_eq!(deps.fields, vec!["dur", "lim", "st", "ver"]);
assert!(!deps.is_complete);
let deps = extract(&parse("(SELECT VALUE city FROM $this WHERE active = true)"));
assert_eq!(deps.fields, vec!["active", "city"]);
assert!(!deps.is_complete);
let deps = extract(&parse("(SELECT VALUE type::field('city') FROM $self)"));
assert_eq!(deps.fields, vec!["city"]);
assert!(!deps.is_complete);
let deps = extract(&parse("(SELECT VALUE (SELECT VALUE city FROM $parent) FROM child)"));
assert_eq!(deps.fields, vec!["city"]);
assert!(!deps.is_complete);
let deps = extract(&parse(
"(SELECT $parent.other_field, $parent['bracket_field'] FROM other WHERE col = 1)",
));
assert_eq!(deps.fields, vec!["bracket_field", "other_field"]);
assert!(!deps.is_complete);
let deps =
extract(&parse("(SELECT (SELECT VALUE $parent.inner_only FROM other2) FROM other1)"));
assert!(deps.fields.is_empty(), "{deps:?}");
assert!(!deps.is_complete);
}
#[test]
fn session_params_read_no_field_of_the_row() {
for src in ["$auth", "$auth.id", "$access", "$token.sub", "$session.ns", "$auth.roles[0]"] {
let deps = extract(&parse(src));
assert!(deps.fields.is_empty(), "`{src}` reads no field: {deps:?}");
assert!(deps.is_complete, "`{src}` is not opaque");
}
let deps = extract(&parse("owner = $auth.id AND $session.ns = 'test'"));
assert_eq!(deps.fields, vec!["owner"]);
assert!(deps.is_complete);
assert!(!extract(&parse("$auth->likes->post")).is_complete);
assert!(!extract(&parse("$auth.id = $this")).is_complete);
}
#[test]
fn bound_params_read_no_field_of_the_row() {
let bound = |src: &str| extract_computed_deps_binding(&parse(src), &["value"]);
for src in ["$value", "$value.owner", "$value[0]", "$value != NONE"] {
let deps = bound(src);
assert!(deps.fields.is_empty(), "`{src}` reads no field: {deps:?}");
assert!(deps.is_complete, "`{src}` is not opaque");
}
let deps = bound("$value = $auth.id OR hidden != true");
assert_eq!(deps.fields, vec!["hidden"]);
assert!(deps.is_complete);
let deps = bound("$value = $this.owner");
assert_eq!(deps.fields, vec!["owner"]);
assert!(deps.is_complete);
assert!(!bound("$value = $other").is_complete);
assert!(!extract(&parse("$value != NONE")).is_complete);
}
#[test]
fn other_param_dot_field_marks_incomplete() {
let expr = Expr::Idiom(Idiom(vec![
Part::Start(Expr::Param(crate::expr::Param::from("foo".to_string()))),
Part::Field(Strand::new_static("a")),
]));
let deps = extract(&expr);
assert!(!deps.is_complete);
}
fn parse(s: &str) -> Expr {
crate::syn::expr(s).expect("test expression must parse")
}
#[test]
fn select_subquery_marks_incomplete() {
let expr = parse("(SELECT * FROM t) + b");
let deps = extract(&expr);
assert!(!deps.is_complete);
assert!(deps.fields.contains(&"b".to_string()));
}
#[test]
fn create_subquery_marks_incomplete() {
let expr = parse("(CREATE t SET x = 1).y");
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn update_subquery_marks_incomplete() {
let expr = parse("(UPDATE t SET x = 1).y");
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn upsert_subquery_marks_incomplete() {
let expr = parse("(UPSERT t SET x = 1).y");
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn delete_subquery_marks_incomplete() {
let expr = parse("(DELETE t).y");
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn relate_subquery_marks_incomplete() {
let expr = parse("(RELATE a:1 -> rel -> b:1).y");
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn insert_subquery_marks_incomplete() {
let expr = parse("(INSERT INTO t { x: 1 }).y");
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn closure_marks_incomplete() {
let expr = parse("|$x: any| $x + a");
let deps = extract(&expr);
assert!(!deps.is_complete);
assert_eq!(deps.fields, vec!["a"]);
let deps = extract(&parse("[1].map(|$x| $x + b)"));
assert!(!deps.is_complete);
assert_eq!(deps.fields, vec!["b"]);
let deps = extract(&parse("[1].map(|$x| $x + $this.b)"));
assert!(!deps.is_complete);
assert_eq!(deps.fields, vec!["b"]);
}
#[test]
fn where_part_scopes_element_fields_and_extracts_parent_deps() {
let deps = extract(&parse("items[WHERE x > 0]"));
assert_eq!(deps.fields, vec!["items"]);
assert!(deps.is_complete);
let deps = extract(&parse("items[WHERE $this.x > 0]"));
assert_eq!(deps.fields, vec!["items"]);
assert!(deps.is_complete);
let deps = extract(&parse("items[WHERE x = $parent.b]"));
assert_eq!(deps.fields, vec!["b", "items"]);
assert!(!deps.is_complete);
}
#[test]
fn a_leading_bare_lookup_reads_only_the_id() {
for text in ["<~doc", "->friends", "<-friends"] {
let deps = extract(&parse(text));
assert!(deps.is_complete, "`{text}` is not opaque");
assert_eq!(deps.fields, vec!["id".to_owned()]);
}
}
#[test]
fn graph_lookup_beyond_the_bare_leading_one_marks_incomplete() {
for text in [
"->friends->person",
"->(friends WHERE x > 1)",
"->(friends LIMIT 1)",
"->friends.name->person",
"a->friends",
] {
assert!(!extract(&parse(text)).is_complete, "`{text}` must stay opaque");
}
}
#[test]
fn start_with_arbitrary_expr_marks_incomplete() {
let expr = parse("(a + b).field");
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn subquery_inside_function_args() {
let expr = parse("array::len([a, (SELECT * FROM t)])");
let deps = extract(&expr);
assert!(!deps.is_complete);
assert!(deps.fields.contains(&"a".to_string()));
}
#[test]
fn subquery_inside_ifelse() {
let expr = parse("IF a > 0 { (SELECT * FROM t) } ELSE { b }");
let deps = extract(&expr);
assert!(!deps.is_complete);
assert!(deps.fields.contains(&"a".to_string()));
assert!(deps.fields.contains(&"b".to_string()));
}
#[test]
fn ifelse_extracts_branch_deps() {
let expr = parse("IF a { b } ELSE { c }");
let deps = extract(&expr);
assert!(deps.is_complete);
assert!(deps.fields.contains(&"a".to_string()));
assert!(deps.fields.contains(&"b".to_string()));
assert!(deps.fields.contains(&"c".to_string()));
}
#[test]
fn type_field_literal_extracts_root() {
let expr = fn_call("type::field", vec![str_lit("admin_only")]);
let deps = extract(&expr);
assert!(deps.is_complete);
assert_eq!(deps.fields, vec!["admin_only"]);
}
#[test]
fn type_field_dotted_extracts_root() {
let expr = fn_call("type::field", vec![str_lit("user.name")]);
let deps = extract(&expr);
assert!(deps.is_complete);
assert_eq!(deps.fields, vec!["user"]);
}
#[test]
fn type_field_dollar_this_marks_incomplete() {
let expr = fn_call("type::field", vec![str_lit("$this.x")]);
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn type_field_param_arg_marks_incomplete() {
let expr =
fn_call("type::field", vec![Expr::Param(crate::expr::Param::from("name".to_string()))]);
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn type_field_concat_arg_marks_incomplete() {
let expr = fn_call(
"type::field",
vec![Expr::Binary {
left: Box::new(str_lit("a")),
op: BinaryOperator::Add,
right: Box::new(field_expr("b")),
}],
);
let deps = extract(&expr);
assert!(!deps.is_complete);
assert!(deps.fields.contains(&"b".to_string()));
}
#[test]
fn type_fields_array_of_literals_extracts_roots() {
let expr = fn_call(
"type::fields",
vec![Expr::Literal(Literal::Array(vec![str_lit("a"), str_lit("b.c")]))],
);
let deps = extract(&expr);
assert!(deps.is_complete);
assert_eq!(deps.fields, vec!["a", "b"]);
}
#[test]
fn type_fields_with_dynamic_element_marks_incomplete() {
let expr =
fn_call("type::fields", vec![Expr::Literal(Literal::Array(vec![field_expr("a")]))]);
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn type_fields_non_array_marks_incomplete() {
let expr = fn_call(
"type::fields",
vec![Expr::Param(crate::expr::Param::from("names".to_string()))],
);
let deps = extract(&expr);
assert!(!deps.is_complete);
}
#[test]
fn type_field_combined_with_other_field() {
let expr = Expr::Binary {
left: Box::new(fn_call("type::field", vec![str_lit("a")])),
op: BinaryOperator::Add,
right: Box::new(field_expr("b")),
};
let deps = extract(&expr);
assert!(deps.is_complete);
assert_eq!(deps.fields, vec!["a", "b"]);
}
#[test]
fn a_call_running_its_own_body_marks_incomplete() {
for src in [
"fn::hidden() != true",
"fn::check(a) = true",
"function() { return this.hidden; }",
"mod::perms::hidden()",
"silo::acme::perms::<1.0.0>::hidden()",
] {
assert!(!extract(&parse(src)).is_complete, "`{src}` is opaque");
}
assert_eq!(extract(&parse("fn::check(a) = true")).fields, vec!["a"]);
let deps = extract(&parse("string::lowercase(owner) = 'bob'"));
assert!(deps.is_complete);
assert_eq!(deps.fields, vec!["owner"]);
}
#[test]
fn topo_sort_empty() {
let result = topological_sort_computed_fields(&[]);
assert!(result.is_empty());
}
#[test]
fn topo_sort_no_deps() {
let fields = vec![("b".to_string(), vec![]), ("a".to_string(), vec![])];
let order = topological_sort_computed_fields(&fields);
assert_eq!(order.len(), 2);
assert!(order.contains(&0));
assert!(order.contains(&1));
}
#[test]
fn topo_sort_linear_chain() {
let fields = vec![
("a".to_string(), vec!["b".to_string()]),
("b".to_string(), vec!["c".to_string()]),
("c".to_string(), vec![]),
];
let order = topological_sort_computed_fields(&fields);
assert_eq!(order.len(), 3);
let pos_a = order.iter().position(|&x| x == 0).unwrap();
let pos_b = order.iter().position(|&x| x == 1).unwrap();
let pos_c = order.iter().position(|&x| x == 2).unwrap();
assert!(pos_c < pos_b);
assert!(pos_b < pos_a);
}
#[test]
fn topo_sort_diamond() {
let fields = vec![
("a".to_string(), vec!["b".to_string(), "c".to_string()]),
("b".to_string(), vec!["d".to_string()]),
("c".to_string(), vec!["d".to_string()]),
("d".to_string(), vec![]),
];
let order = topological_sort_computed_fields(&fields);
assert_eq!(order.len(), 4);
let pos_a = order.iter().position(|&x| x == 0).unwrap();
let pos_b = order.iter().position(|&x| x == 1).unwrap();
let pos_c = order.iter().position(|&x| x == 2).unwrap();
let pos_d = order.iter().position(|&x| x == 3).unwrap();
assert!(pos_d < pos_b);
assert!(pos_d < pos_c);
assert!(pos_b < pos_a);
assert!(pos_c < pos_a);
}
#[test]
fn topo_sort_dep_on_stored_field() {
let fields = vec![("a".to_string(), vec!["stored".to_string()])];
let order = topological_sort_computed_fields(&fields);
assert_eq!(order, vec![0]);
}
#[test]
fn closure_simple() {
let mut computed = HashMap::new();
computed.insert(
"a".to_string(),
ComputedDeps {
fields: vec!["b".to_string(), "c".to_string()],
is_complete: true,
},
);
computed.insert(
"b".to_string(),
ComputedDeps {
fields: vec![],
is_complete: true,
},
);
computed.insert(
"c".to_string(),
ComputedDeps {
fields: vec!["d".to_string()],
is_complete: true,
},
);
let needed: HashSet<String> = ["a".to_string()].into_iter().collect();
let required = resolve_required_computed_fields(&needed, &computed).unwrap();
assert!(required.contains("a"));
assert!(required.contains("b"));
assert!(required.contains("c"));
assert!(required.contains("d")); }
#[test]
fn closure_incomplete_forces_all() {
let mut computed = HashMap::new();
computed.insert(
"a".to_string(),
ComputedDeps {
fields: vec!["b".to_string()],
is_complete: false,
},
);
computed.insert(
"b".to_string(),
ComputedDeps {
fields: vec![],
is_complete: true,
},
);
let needed: HashSet<String> = ["a".to_string()].into_iter().collect();
let result = resolve_required_computed_fields(&needed, &computed);
assert!(result.is_none());
}
#[test]
fn closure_only_needed() {
let mut computed = HashMap::new();
computed.insert(
"a".to_string(),
ComputedDeps {
fields: vec!["b".to_string(), "c".to_string()],
is_complete: true,
},
);
computed.insert(
"b".to_string(),
ComputedDeps {
fields: vec![],
is_complete: true,
},
);
computed.insert(
"c".to_string(),
ComputedDeps {
fields: vec![],
is_complete: true,
},
);
computed.insert(
"x".to_string(),
ComputedDeps {
fields: vec!["y".to_string()],
is_complete: true,
},
);
let needed: HashSet<String> = ["b".to_string()].into_iter().collect();
let required = resolve_required_computed_fields(&needed, &computed).unwrap();
assert!(required.contains("b"));
assert!(!required.contains("a"));
assert!(!required.contains("x"));
}
}