Skip to content

Commit b835b5e

Browse files
committed
fix(cypher): defer unbound relationship predicates
execute_single previously evaluated the complete WHERE tree while only the first MATCH alias was bound. A target-alias predicate such as NOT callee.file_path CONTAINS "tests/" therefore rejected every seed before CALLS expansion and returned zero rows. Add allocation-free three-valued partial evaluation in src/cypher/cypher.c: bound leaves prune early, unbound node or edge aliases remain unknown, and AND/OR/NOT/XOR preserve boolean semantics and safe short-circuiting. Register eval_expr_partial in src/foundation/recursion_whitelist.h. Add four relationship-target and mixed-alias regressions in tests/test_cypher.c. Verified 159/159 Cypher tests under ASan/UBSan, source-safety and whitelist checks, an -O2 production build, and the formerly empty hotspot query returning 20 bounded rows. Signed-off-by: Andrew Hundt <[email protected]>
1 parent a4b3a71 commit b835b5e

3 files changed

Lines changed: 154 additions & 6 deletions

File tree

‎src/cypher/cypher.c‎

Lines changed: 82 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2619,6 +2619,87 @@ static bool eval_where(const cbm_where_clause_t *w, binding_t *b) {
26192619
return is_and;
26202620
}
26212621

2622+
typedef enum { CYP_PARTIAL_FALSE = 0, CYP_PARTIAL_TRUE, CYP_PARTIAL_UNKNOWN } cypher_partial_bool_t;
2623+
2624+
static cypher_partial_bool_t partial_and(cypher_partial_bool_t left, cypher_partial_bool_t right) {
2625+
if (left == CYP_PARTIAL_FALSE || right == CYP_PARTIAL_FALSE) {
2626+
return CYP_PARTIAL_FALSE;
2627+
}
2628+
return left == CYP_PARTIAL_TRUE && right == CYP_PARTIAL_TRUE ? CYP_PARTIAL_TRUE
2629+
: CYP_PARTIAL_UNKNOWN;
2630+
}
2631+
2632+
static cypher_partial_bool_t partial_or(cypher_partial_bool_t left, cypher_partial_bool_t right) {
2633+
if (left == CYP_PARTIAL_TRUE || right == CYP_PARTIAL_TRUE) {
2634+
return CYP_PARTIAL_TRUE;
2635+
}
2636+
return left == CYP_PARTIAL_FALSE && right == CYP_PARTIAL_FALSE ? CYP_PARTIAL_FALSE
2637+
: CYP_PARTIAL_UNKNOWN;
2638+
}
2639+
2640+
/* Evaluate the portion of a WHERE expression whose aliases are already
2641+
* bound. Unknown leaves keep the seed; definitively false source predicates
2642+
* still prune before relationship expansion. Per seed this is O(expression
2643+
* nodes) time, O(expression depth) stack, and allocation-free; AND/OR retain
2644+
* the full evaluator's safe short-circuit behavior. */
2645+
static cypher_partial_bool_t eval_expr_partial(const cbm_expr_t *e, // NOLINT(misc-no-recursion)
2646+
binding_t *b) {
2647+
if (!e) {
2648+
return CYP_PARTIAL_TRUE;
2649+
}
2650+
if (e->type == EXPR_CONDITION) {
2651+
if (!binding_get(b, e->cond.variable) && !binding_get_edge(b, e->cond.variable)) {
2652+
return CYP_PARTIAL_UNKNOWN;
2653+
}
2654+
return eval_condition(&e->cond, b) ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
2655+
}
2656+
2657+
cypher_partial_bool_t left = eval_expr_partial(e->left, b);
2658+
if (e->type == EXPR_NOT) {
2659+
return left == CYP_PARTIAL_UNKNOWN
2660+
? CYP_PARTIAL_UNKNOWN
2661+
: (left == CYP_PARTIAL_TRUE ? CYP_PARTIAL_FALSE : CYP_PARTIAL_TRUE);
2662+
}
2663+
if (e->type == EXPR_AND && left == CYP_PARTIAL_FALSE) {
2664+
return CYP_PARTIAL_FALSE;
2665+
}
2666+
if (e->type == EXPR_OR && left == CYP_PARTIAL_TRUE) {
2667+
return CYP_PARTIAL_TRUE;
2668+
}
2669+
cypher_partial_bool_t right = eval_expr_partial(e->right, b);
2670+
if (e->type == EXPR_AND) {
2671+
return partial_and(left, right);
2672+
}
2673+
if (e->type == EXPR_OR) {
2674+
return partial_or(left, right);
2675+
}
2676+
if (left == CYP_PARTIAL_UNKNOWN || right == CYP_PARTIAL_UNKNOWN) {
2677+
return CYP_PARTIAL_UNKNOWN;
2678+
}
2679+
return left != right ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
2680+
}
2681+
2682+
static cypher_partial_bool_t eval_where_partial(const cbm_where_clause_t *where, binding_t *b) {
2683+
if (!where) {
2684+
return CYP_PARTIAL_TRUE;
2685+
}
2686+
if (where->root) {
2687+
return eval_expr_partial(where->root, b);
2688+
}
2689+
cypher_partial_bool_t result =
2690+
where->op && strcmp(where->op, "AND") == 0 ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
2691+
for (int i = 0; i < where->count; i++) {
2692+
cypher_partial_bool_t item =
2693+
(!binding_get(b, where->conditions[i].variable) &&
2694+
!binding_get_edge(b, where->conditions[i].variable))
2695+
? CYP_PARTIAL_UNKNOWN
2696+
: (eval_condition(&where->conditions[i], b) ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE);
2697+
result = where->op && strcmp(where->op, "AND") == 0 ? partial_and(result, item)
2698+
: partial_or(result, item);
2699+
}
2700+
return result;
2701+
}
2702+
26222703
/* Check if a string value looks like a regex pattern. */
26232704
static bool looks_like_regex(const char *s) {
26242705
if (!s) {
@@ -4668,7 +4749,7 @@ static int execute_single(cbm_store_t *store, cbm_query_t *q, const char *projec
46684749
b.project = project;
46694750
b.use_active_overlay_edges = scan_mode == CYP_NODE_SCAN_ACTIVE_OVERLAY;
46704751
binding_set(&b, var_name, &scanned[i]);
4671-
bool pass = !q->where || eval_where(q->where, &b);
4752+
bool pass = eval_where_partial(q->where, &b) != CYP_PARTIAL_FALSE;
46724753
if (pass) {
46734754
bindings[bind_count++] = b;
46744755
} else {

‎src/foundation/recursion_whitelist.h‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -8,8 +8,8 @@
88
* - parse_or_expr, parse_xor_expr, parse_and_expr, parse_not_expr
99
* - parse_atom_expr, parse_post_where, cbm_parse
1010
*
11-
* Cypher expression evaluator (bounded by WHERE clause depth ~5):
12-
* - eval_expr
11+
* Cypher expression traversal (bounded by WHERE clause depth ~5):
12+
* - eval_expr, eval_expr_partial
1313
*
1414
* Glob pattern matcher (bounded by pattern nesting ~3):
1515
* - glob_match, glob_match_star, glob_match_doublestar
@@ -27,7 +27,7 @@
2727
*/
2828
#define CBM_RECURSION_WHITELIST \
2929
"parse_or_expr", "parse_xor_expr", "parse_and_expr", "parse_not_expr", "parse_atom_expr", \
30-
"parse_post_where", "cbm_parse", "eval_expr", "glob_match", "glob_match_star", \
31-
"glob_match_doublestar", "glob_match_doublestar_slash", "glob_match_doublestar_any", \
32-
"parse_bool_expr", "parse_bool_atom", "r_collect_imports", \
30+
"parse_post_where", "cbm_parse", "eval_expr", "eval_expr_partial", "glob_match", \
31+
"glob_match_star", "glob_match_doublestar", "glob_match_doublestar_slash", \
32+
"glob_match_doublestar_any", "parse_bool_expr", "parse_bool_atom", "r_collect_imports", \
3333
"find_first_descendant_by_kind", "find_first_descendant_of"

‎tests/test_cypher.c‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1929,6 +1929,69 @@ TEST(cypher_exec_where_not) {
19291929
PASS();
19301930
}
19311931

1932+
TEST(cypher_exec_where_not_on_relationship_target) {
1933+
cbm_store_t *s = setup_cypher_store();
1934+
cbm_cypher_result_t r = {0};
1935+
int rc = cbm_cypher_execute(s,
1936+
"MATCH (a:Function)-[:CALLS]->(b:Function) "
1937+
"WHERE NOT b.name CONTAINS \"Order\" RETURN b.name",
1938+
"test", 0, &r);
1939+
ASSERT_EQ(rc, 0);
1940+
ASSERT_EQ(r.row_count, 1);
1941+
ASSERT_STR_EQ(r.rows[0][0], "LogError");
1942+
cbm_cypher_result_free(&r);
1943+
cbm_store_close(s);
1944+
PASS();
1945+
}
1946+
1947+
TEST(cypher_exec_where_mixed_alias_and) {
1948+
cbm_store_t *s = setup_cypher_store();
1949+
cbm_cypher_result_t r = {0};
1950+
int rc = cbm_cypher_execute(
1951+
s,
1952+
"MATCH (a:Function)-[:CALLS]->(b:Function) "
1953+
"WHERE a.name = \"HandleOrder\" AND NOT b.name CONTAINS \"Order\" RETURN b.name",
1954+
"test", 0, &r);
1955+
ASSERT_EQ(rc, 0);
1956+
ASSERT_EQ(r.row_count, 1);
1957+
ASSERT_STR_EQ(r.rows[0][0], "LogError");
1958+
cbm_cypher_result_free(&r);
1959+
cbm_store_close(s);
1960+
PASS();
1961+
}
1962+
1963+
TEST(cypher_exec_where_mixed_alias_or) {
1964+
cbm_store_t *s = setup_cypher_store();
1965+
cbm_cypher_result_t r = {0};
1966+
int rc = cbm_cypher_execute(
1967+
s,
1968+
"MATCH (a:Function)-[:CALLS]->(b:Function) "
1969+
"WHERE a.name = \"NoSuchFunction\" OR NOT b.name CONTAINS \"Order\" RETURN b.name",
1970+
"test", 0, &r);
1971+
ASSERT_EQ(rc, 0);
1972+
ASSERT_EQ(r.row_count, 1);
1973+
ASSERT_STR_EQ(r.rows[0][0], "LogError");
1974+
cbm_cypher_result_free(&r);
1975+
cbm_store_close(s);
1976+
PASS();
1977+
}
1978+
1979+
TEST(cypher_exec_where_mixed_alias_xor) {
1980+
cbm_store_t *s = setup_cypher_store();
1981+
cbm_cypher_result_t r = {0};
1982+
int rc =
1983+
cbm_cypher_execute(s,
1984+
"MATCH (a:Function)-[:CALLS]->(b:Function) "
1985+
"WHERE a.name = \"HandleOrder\" XOR b.name = \"LogError\" RETURN b.name",
1986+
"test", 0, &r);
1987+
ASSERT_EQ(rc, 0);
1988+
ASSERT_EQ(r.row_count, 1);
1989+
ASSERT_STR_EQ(r.rows[0][0], "ValidateOrder");
1990+
cbm_cypher_result_free(&r);
1991+
cbm_store_close(s);
1992+
PASS();
1993+
}
1994+
19321995
TEST(cypher_exec_where_in) {
19331996
cbm_store_t *s = setup_cypher_store();
19341997
cbm_cypher_result_t r = {0};
@@ -3073,6 +3136,10 @@ SUITE(cypher) {
30733136
RUN_TEST(cypher_exec_where_neq_bang);
30743137
RUN_TEST(cypher_exec_where_ends_with);
30753138
RUN_TEST(cypher_exec_where_not);
3139+
RUN_TEST(cypher_exec_where_not_on_relationship_target);
3140+
RUN_TEST(cypher_exec_where_mixed_alias_and);
3141+
RUN_TEST(cypher_exec_where_mixed_alias_or);
3142+
RUN_TEST(cypher_exec_where_mixed_alias_xor);
30763143
RUN_TEST(cypher_exec_where_in);
30773144
RUN_TEST(cypher_exec_where_not_in);
30783145
RUN_TEST(cypher_exec_where_is_null);

0 commit comments

Comments
 (0)