Skip to content

Commit 8ab555e

Browse files
authored
Merge pull request #2253 from DeusData/distill/1245-cypher-partial-where
fix(cypher): stop the early WHERE pruning rows it cannot judge yet
2 parents 100ea8f + dc5293d commit 8ab555e

3 files changed

Lines changed: 170 additions & 8 deletions

File tree

‎src/cypher/cypher.c‎

Lines changed: 91 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2778,6 +2778,96 @@ static bool eval_where(const cbm_where_clause_t *w, binding_t *b) {
27782778
return is_and;
27792779
}
27802780

2781+
/* Three-valued WHERE evaluation for the early (seed-row) pass in
2782+
* execute_single: only the first MATCH alias is bound there, so a leaf on
2783+
* any other alias is UNKNOWN rather than true. The two-valued evaluator
2784+
* returns true for an unbound alias, which NOT / XOR then invert -- pruning
2785+
* every seed before relationship expansion (distilled from PR #1245). The
2786+
* full evaluation reruns after expansion (Step 3), so the early pass only has
2787+
* to prune on a definite false. Allocation-free, O(expression nodes). */
2788+
typedef enum { CYP_PARTIAL_FALSE = 0, CYP_PARTIAL_TRUE, CYP_PARTIAL_UNKNOWN } cyp_partial_t;
2789+
2790+
static cyp_partial_t partial_and(cyp_partial_t l, cyp_partial_t r) {
2791+
if (l == CYP_PARTIAL_FALSE || r == CYP_PARTIAL_FALSE) {
2792+
return CYP_PARTIAL_FALSE;
2793+
}
2794+
return (l == CYP_PARTIAL_TRUE && r == CYP_PARTIAL_TRUE) ? CYP_PARTIAL_TRUE
2795+
: CYP_PARTIAL_UNKNOWN;
2796+
}
2797+
2798+
static cyp_partial_t partial_or(cyp_partial_t l, cyp_partial_t r) {
2799+
if (l == CYP_PARTIAL_TRUE || r == CYP_PARTIAL_TRUE) {
2800+
return CYP_PARTIAL_TRUE;
2801+
}
2802+
return (l == CYP_PARTIAL_FALSE && r == CYP_PARTIAL_FALSE) ? CYP_PARTIAL_FALSE
2803+
: CYP_PARTIAL_UNKNOWN;
2804+
}
2805+
2806+
/* A condition whose alias is not bound yet is UNKNOWN; a literal-only LHS
2807+
* (func condition with no variable arg) has nothing to wait for. */
2808+
static cyp_partial_t eval_condition_partial(const cbm_condition_t *c, binding_t *b) {
2809+
if (c->variable && !binding_get(b, c->variable) && !binding_get_edge(b, c->variable)) {
2810+
return CYP_PARTIAL_UNKNOWN;
2811+
}
2812+
return eval_condition(c, b) ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
2813+
}
2814+
2815+
static cyp_partial_t eval_expr_partial(const cbm_expr_t *e, // NOLINT(misc-no-recursion)
2816+
binding_t *b) {
2817+
if (!e) {
2818+
return CYP_PARTIAL_TRUE;
2819+
}
2820+
if (e->type == EXPR_CONDITION) {
2821+
return eval_condition_partial(&e->cond, b);
2822+
}
2823+
cyp_partial_t left = eval_expr_partial(e->left, b);
2824+
if (e->type == EXPR_NOT) {
2825+
if (left == CYP_PARTIAL_UNKNOWN) {
2826+
return CYP_PARTIAL_UNKNOWN;
2827+
}
2828+
return left == CYP_PARTIAL_TRUE ? CYP_PARTIAL_FALSE : CYP_PARTIAL_TRUE;
2829+
}
2830+
/* Same short-circuits as eval_expr: a definite left decides AND / OR. */
2831+
if (e->type == EXPR_AND && left == CYP_PARTIAL_FALSE) {
2832+
return CYP_PARTIAL_FALSE;
2833+
}
2834+
if (e->type == EXPR_OR && left == CYP_PARTIAL_TRUE) {
2835+
return CYP_PARTIAL_TRUE;
2836+
}
2837+
cyp_partial_t right = eval_expr_partial(e->right, b);
2838+
if (e->type == EXPR_AND) {
2839+
return partial_and(left, right);
2840+
}
2841+
if (e->type == EXPR_OR) {
2842+
return partial_or(left, right);
2843+
}
2844+
/* EXPR_XOR */
2845+
if (left == CYP_PARTIAL_UNKNOWN || right == CYP_PARTIAL_UNKNOWN) {
2846+
return CYP_PARTIAL_UNKNOWN;
2847+
}
2848+
return left != right ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
2849+
}
2850+
2851+
static cyp_partial_t eval_where_partial(const cbm_where_clause_t *w, binding_t *b) {
2852+
if (!w) {
2853+
return CYP_PARTIAL_TRUE;
2854+
}
2855+
if (w->root) {
2856+
return eval_expr_partial(w->root, b);
2857+
}
2858+
/* Legacy flat evaluation */
2859+
if (w->count == 0) {
2860+
return CYP_PARTIAL_TRUE;
2861+
}
2862+
bool is_and = (w->op && strcmp(w->op, "AND") == 0) != 0;
2863+
cyp_partial_t result = is_and ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
2864+
for (int i = 0; i < w->count; i++) {
2865+
cyp_partial_t r = eval_condition_partial(&w->conditions[i], b);
2866+
result = is_and ? partial_and(result, r) : partial_or(result, r);
2867+
}
2868+
return result;
2869+
}
2870+
27812871
/* Check if a string value looks like a regex pattern. */
27822872
static bool looks_like_regex(const char *s) {
27832873
if (!s) {
@@ -5281,7 +5371,7 @@ static int execute_single(cbm_store_t *store, cbm_query_t *q, const char *projec
52815371
binding_t b = {0};
52825372
b.store = store;
52835373
binding_set(&b, var_name, &scanned[i]);
5284-
bool pass = !q->where || eval_where(q->where, &b);
5374+
bool pass = eval_where_partial(q->where, &b) != CYP_PARTIAL_FALSE;
52855375
if (pass) {
52865376
bindings[bind_count++] = b;
52875377
} else {

‎src/foundation/recursion_whitelist.h‎

Lines changed: 7 additions & 7 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 evaluators (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
@@ -25,9 +25,9 @@
2525
* To add a function: add it below AND add NOLINT(misc-no-recursion) on
2626
* the function definition line. The lint gate verifies both match.
2727
*/
28-
#define CBM_RECURSION_WHITELIST \
29-
"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", \
28+
#define CBM_RECURSION_WHITELIST \
29+
"parse_or_expr", "parse_xor_expr", "parse_and_expr", "parse_not_expr", "parse_atom_expr", \
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: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3281,6 +3281,74 @@ TEST(cypher_exec_where_not) {
32813281
PASS();
32823282
}
32833283

3284+
/* Regression (distilled from PR #1245, Andrew Hundt): the early WHERE pass in
3285+
* execute_single runs on seed rows with only the first alias bound. A
3286+
* comparison on an unbound alias used to evaluate to true, which NOT / XOR
3287+
* then inverted -- so every seed was pruned before CALLS expansion and the
3288+
* query returned zero rows. Unbound leaves must stay UNKNOWN there. */
3289+
TEST(cypher_exec_where_not_on_relationship_target) {
3290+
cbm_store_t *s = setup_cypher_store();
3291+
cbm_cypher_result_t r = {0};
3292+
int rc = cbm_cypher_execute(s,
3293+
"MATCH (a:Function)-[:CALLS]->(b:Function) "
3294+
"WHERE NOT b.name CONTAINS \"Order\" RETURN b.name",
3295+
"test", 0, &r);
3296+
ASSERT_EQ(rc, 0);
3297+
ASSERT_EQ(r.row_count, 1);
3298+
ASSERT_STR_EQ(r.rows[0][0], "LogError");
3299+
cbm_cypher_result_free(&r);
3300+
cbm_store_close(s);
3301+
PASS();
3302+
}
3303+
3304+
TEST(cypher_exec_where_mixed_alias_and) {
3305+
cbm_store_t *s = setup_cypher_store();
3306+
cbm_cypher_result_t r = {0};
3307+
int rc = cbm_cypher_execute(
3308+
s,
3309+
"MATCH (a:Function)-[:CALLS]->(b:Function) "
3310+
"WHERE a.name = \"HandleOrder\" AND NOT b.name CONTAINS \"Order\" RETURN b.name",
3311+
"test", 0, &r);
3312+
ASSERT_EQ(rc, 0);
3313+
ASSERT_EQ(r.row_count, 1);
3314+
ASSERT_STR_EQ(r.rows[0][0], "LogError");
3315+
cbm_cypher_result_free(&r);
3316+
cbm_store_close(s);
3317+
PASS();
3318+
}
3319+
3320+
TEST(cypher_exec_where_mixed_alias_or) {
3321+
cbm_store_t *s = setup_cypher_store();
3322+
cbm_cypher_result_t r = {0};
3323+
int rc = cbm_cypher_execute(
3324+
s,
3325+
"MATCH (a:Function)-[:CALLS]->(b:Function) "
3326+
"WHERE a.name = \"NoSuchFunction\" OR NOT b.name CONTAINS \"Order\" RETURN b.name",
3327+
"test", 0, &r);
3328+
ASSERT_EQ(rc, 0);
3329+
ASSERT_EQ(r.row_count, 1);
3330+
ASSERT_STR_EQ(r.rows[0][0], "LogError");
3331+
cbm_cypher_result_free(&r);
3332+
cbm_store_close(s);
3333+
PASS();
3334+
}
3335+
3336+
TEST(cypher_exec_where_mixed_alias_xor) {
3337+
cbm_store_t *s = setup_cypher_store();
3338+
cbm_cypher_result_t r = {0};
3339+
int rc =
3340+
cbm_cypher_execute(s,
3341+
"MATCH (a:Function)-[:CALLS]->(b:Function) "
3342+
"WHERE a.name = \"HandleOrder\" XOR b.name = \"LogError\" RETURN b.name",
3343+
"test", 0, &r);
3344+
ASSERT_EQ(rc, 0);
3345+
ASSERT_EQ(r.row_count, 1);
3346+
ASSERT_STR_EQ(r.rows[0][0], "ValidateOrder");
3347+
cbm_cypher_result_free(&r);
3348+
cbm_store_close(s);
3349+
PASS();
3350+
}
3351+
32843352
TEST(cypher_exec_where_in) {
32853353
cbm_store_t *s = setup_cypher_store();
32863354
cbm_cypher_result_t r = {0};
@@ -5160,6 +5228,10 @@ SUITE(cypher) {
51605228
RUN_TEST(cypher_exec_where_neq_bang);
51615229
RUN_TEST(cypher_exec_where_ends_with);
51625230
RUN_TEST(cypher_exec_where_not);
5231+
RUN_TEST(cypher_exec_where_not_on_relationship_target);
5232+
RUN_TEST(cypher_exec_where_mixed_alias_and);
5233+
RUN_TEST(cypher_exec_where_mixed_alias_or);
5234+
RUN_TEST(cypher_exec_where_mixed_alias_xor);
51635235
RUN_TEST(cypher_exec_where_in);
51645236
RUN_TEST(cypher_exec_where_not_in);
51655237
RUN_TEST(cypher_exec_where_is_null);

0 commit comments

Comments
 (0)