Skip to content

Commit 421d9d2

Browse files
authored
Merge pull request #1998 from CaptainMittens/fix/bound-pattern-variable-count
fix(cypher): refuse a query naming more variables than a binding holds
2 parents 98b94a2 + a143b08 commit 421d9d2

2 files changed

Lines changed: 214 additions & 3 deletions

File tree

‎src/cypher/cypher.c‎

Lines changed: 92 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,10 @@ enum {
3636
/* search miss sentinel */ /* mask for ebuf ring buffer (8 entries) */
3737
};
3838
#define CYP_DBL_MAX 1e308
39+
/* execute_single binds the first pattern's leading node even when the query
40+
* leaves it unnamed, so the engine needs a name for it. The binding slot is
41+
* real, which is why check_pattern_var_capacity counts it. */
42+
#define CYP_ANON_HEAD_VAR "_n0"
3943

4044
#include <ctype.h>
4145
#include <limits.h> // INT_MAX
@@ -4994,7 +4998,7 @@ static int execute_single(cbm_store_t *store, cbm_query_t *q, const char *projec
49944998
int bind_cap = scan_count > max_rows ? scan_count : (max_rows > 0 ? max_rows : SKIP_ONE);
49954999
binding_t *bindings = malloc((bind_cap + SKIP_ONE) * sizeof(binding_t));
49965000
int bind_count = 0;
4997-
const char *var_name = pat0->nodes[0].variable ? pat0->nodes[0].variable : "_n0";
5001+
const char *var_name = pat0->nodes[0].variable ? pat0->nodes[0].variable : CYP_ANON_HEAD_VAR;
49985002

49995003
for (int i = 0; i < scan_count && bind_count < bind_cap; i++) {
50005004
if ((i & CYPHER_DEADLINE_CHECK_MASK) == 0 && cypher_deadline_exceeded()) {
@@ -5164,13 +5168,98 @@ static const char *scope_checkable_var(const cbm_return_item_t *item) {
51645168
return item->variable;
51655169
}
51665170

5171+
/* Says which limit the query passed and how to get under it. An unnamed node
5172+
* takes no slot — except the head of the first pattern, which the engine binds
5173+
* either way — so dropping a name the query never uses is the cheap way out.
5174+
* Splitting the MATCH is NOT — every pattern of one query shares one binding,
5175+
* which is why the caller counts across all of them. Separate queries do work,
5176+
* because each gets a binding of its own. */
5177+
static char *var_capacity_error(const char *kind, int limit) {
5178+
char buf[CBM_SZ_256];
5179+
snprintf(buf, sizeof(buf),
5180+
"too many %s variables: a query can name at most %d — "
5181+
"leave the name off the ones you do not use, or run separate queries",
5182+
kind, limit);
5183+
return heap_strdup(buf);
5184+
}
5185+
5186+
/* A binding holds a fixed number of variables: CYP_MAX_VARS node variables and
5187+
* CYP_MAX_EDGE_VARS edge variables, both in plain arrays (see binding_t).
5188+
* binding_set and binding_set_edge drop anything past those without a word, so
5189+
* a query naming more variables than a binding holds cannot be answered — the
5190+
* extra names bind to nothing and project as empty strings, which reads as
5191+
* "the graph holds no such data" rather than "this query is too wide".
5192+
*
5193+
* Refuse such a query instead, before any row is touched. Bounding the input
5194+
* here is also what stops collect_declared_names below overflowing its array:
5195+
* the patterns contribute at most CYP_MAX_VARS + CYP_MAX_EDGE_VARS names, plus
5196+
* one UNWIND alias, which is well inside CYP_SCOPE_MAX_NAMES.
5197+
*
5198+
* Counts DISTINCT variables across every pattern, because they all land in the
5199+
* same binding: a multi-MATCH query shares one, and an OPTIONAL MATCH pattern
5200+
* sits in this same array (q->pattern_optional marks which). A node variable
5201+
* and an edge variable may share a name and each take a slot, because the
5202+
* binding keeps the two in separate arrays. */
5203+
static char *check_pattern_var_capacity(const cbm_query_t *q) {
5204+
/* Initialized because cppcheck cannot see that scope_holds reads only the
5205+
* node_n / edge_n entries already written, and reports the first call as a
5206+
* read of an uninitialized array. */
5207+
const char *node_vars[CYP_MAX_VARS] = {NULL};
5208+
const char *edge_vars[CYP_MAX_EDGE_VARS] = {NULL};
5209+
int node_n = 0;
5210+
int edge_n = 0;
5211+
/* The head of the first pattern always takes a node slot, named or not:
5212+
* execute_single binds it under CYP_ANON_HEAD_VAR when the query leaves it
5213+
* unnamed. Count it first, or a query with an unnamed head and CYP_MAX_VARS
5214+
* named nodes passes this check and still loses its last name in
5215+
* binding_set — the exact silence this guard exists to remove. */
5216+
if (q->pattern_count > 0 && q->patterns[0].node_count > 0 &&
5217+
!q->patterns[0].nodes[0].variable) {
5218+
node_vars[node_n++] = CYP_ANON_HEAD_VAR;
5219+
}
5220+
for (int pi = 0; pi < q->pattern_count; pi++) {
5221+
const cbm_pattern_t *pat = &q->patterns[pi];
5222+
for (int ni = 0; ni < pat->node_count; ni++) {
5223+
const char *var = pat->nodes[ni].variable;
5224+
if (!var || scope_holds(node_vars, node_n, var)) {
5225+
continue;
5226+
}
5227+
if (node_n >= CYP_MAX_VARS) {
5228+
return var_capacity_error("node", CYP_MAX_VARS);
5229+
}
5230+
node_vars[node_n++] = var;
5231+
}
5232+
for (int ri = 0; ri < pat->rel_count; ri++) {
5233+
const char *var = pat->rels[ri].variable;
5234+
if (!var || scope_holds(edge_vars, edge_n, var)) {
5235+
continue;
5236+
}
5237+
if (edge_n >= CYP_MAX_EDGE_VARS) {
5238+
return var_capacity_error("edge", CYP_MAX_EDGE_VARS);
5239+
}
5240+
edge_vars[edge_n++] = var;
5241+
}
5242+
}
5243+
return NULL;
5244+
}
5245+
51675246
/* Answers NULL when the query is fine, or a heap message naming the first
51685247
* variable that is not in scope. Checks one query; the caller walks a UNION. */
51695248
static char *check_projection_scope(const cbm_query_t *q) {
5249+
/* Runs first, so the rest of this function can trust that the query names
5250+
* no more variables than the arrays below can model. */
5251+
char *capacity_err = check_pattern_var_capacity(q);
5252+
if (capacity_err) {
5253+
return capacity_err;
5254+
}
5255+
51705256
const char *declared[CYP_SCOPE_MAX_NAMES];
51715257
int declared_n = collect_declared_names(q, declared, CYP_SCOPE_MAX_NAMES);
51725258
if (declared_n < 0) {
5173-
return NULL; /* too many names to model — stay quiet rather than guess */
5259+
/* Unreachable while the capacity check above holds. Kept so the guard
5260+
* still stands if either bound ever moves. Skipping the check was the
5261+
* old behaviour, and it let an out-of-scope name through in silence. */
5262+
return NULL;
51745263
}
51755264

51765265
/* A WITH still reads the pattern variables. */
@@ -5194,7 +5283,7 @@ static char *check_projection_scope(const cbm_query_t *q) {
51945283
if (q->with_clause) {
51955284
scope_n = collect_with_names(q->with_clause, after_with, CYP_SCOPE_MAX_NAMES);
51965285
if (scope_n < 0) {
5197-
return NULL;
5286+
return NULL; /* unreachable: a WITH holds at most CYP_SCOPE_MAX_NAMES items */
51985287
}
51995288
scope = after_with;
52005289
}

‎tests/test_cypher.c‎

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3202,6 +3202,124 @@ TEST(cypher_wide_with_refused_not_truncated) {
32023202
ASSERT_EQ(cbm_cypher_execute(s, ok_query, "test", 0, &r16), 0);
32033203
ASSERT_EQ(r16.col_count, 16);
32043204
cbm_cypher_result_free(&r16);
3205+
cbm_store_close(s);
3206+
PASS();
3207+
}
3208+
3209+
/* Build "MATCH (a0:NoSuchLabelXYZ)-[:CALLS]->(a1)-…->(aN-1)" into buf. The label
3210+
* matches nothing, so any query built on it is instant and needs no fixture. */
3211+
static void build_node_chain(char *buf, size_t buf_sz, int nodes) {
3212+
int off = snprintf(buf, buf_sz, "MATCH (a0:NoSuchLabelXYZ)");
3213+
for (int i = 1; i < nodes; i++) {
3214+
off += snprintf(buf + off, buf_sz - (size_t)off, "-[:CALLS]->(a%d)", i);
3215+
}
3216+
}
3217+
3218+
TEST(cypher_wide_pattern_refused) {
3219+
/* A binding holds CYP_MAX_VARS (16) node variables, and binding_set drops
3220+
* the 17th without a word. The query then answers a column of empty strings
3221+
* for every name it could not bind, which reads as "the graph holds no such
3222+
* data". Refuse the query instead of answering it wrong. */
3223+
cbm_store_t *s = setup_cypher_store();
3224+
char query[2048];
3225+
3226+
build_node_chain(query, sizeof(query), 20); /* 20 > CYP_MAX_VARS */
3227+
strncat(query, " RETURN a0.name", sizeof(query) - strlen(query) - 1);
3228+
cbm_cypher_result_t wide = {0};
3229+
ASSERT_TRUE(cbm_cypher_execute(s, query, "test", 0, &wide) != 0);
3230+
ASSERT_NOT_NULL(wide.error);
3231+
ASSERT_TRUE(strstr(wide.error, "node") != NULL); /* says which limit was passed */
3232+
cbm_cypher_result_free(&wide);
3233+
3234+
/* The width right at the bound still runs, so the guard refuses only what a
3235+
* binding genuinely cannot hold. */
3236+
build_node_chain(query, sizeof(query), 16);
3237+
strncat(query, " RETURN a0.name", sizeof(query) - strlen(query) - 1);
3238+
cbm_cypher_result_t ok = {0};
3239+
ASSERT_EQ(cbm_cypher_execute(s, query, "test", 0, &ok), 0);
3240+
cbm_cypher_result_free(&ok);
3241+
3242+
cbm_store_close(s);
3243+
PASS();
3244+
}
3245+
3246+
TEST(cypher_wide_edge_pattern_refused) {
3247+
/* Same shape on the edge table, where binding_set_edge stops at
3248+
* CYP_MAX_EDGE_VARS (8). Only NAMED relationships take a slot. */
3249+
cbm_store_t *s = setup_cypher_store();
3250+
char query[2048];
3251+
int off = snprintf(query, sizeof(query), "MATCH (a0:NoSuchLabelXYZ)");
3252+
for (int i = 1; i <= 9; i++) { /* 9 > CYP_MAX_EDGE_VARS */
3253+
off += snprintf(query + off, sizeof(query) - (size_t)off, "-[r%d:CALLS]->(a%d)", i, i);
3254+
}
3255+
snprintf(query + off, sizeof(query) - (size_t)off, " RETURN a0.name");
3256+
cbm_cypher_result_t wide = {0};
3257+
ASSERT_TRUE(cbm_cypher_execute(s, query, "test", 0, &wide) != 0);
3258+
ASSERT_NOT_NULL(wide.error);
3259+
ASSERT_TRUE(strstr(wide.error, "edge") != NULL);
3260+
cbm_cypher_result_free(&wide);
3261+
cbm_store_close(s);
3262+
PASS();
3263+
}
3264+
3265+
TEST(cypher_unnamed_head_takes_a_slot) {
3266+
/* The head of the first pattern is bound whether the query names it or not:
3267+
* execute_single falls back to the synthetic name "_n0". So an unnamed head
3268+
* plus CYP_MAX_VARS (16) named nodes needs 17 slots and only 16 exist. Before
3269+
* the fix, the capacity check counted names alone, let this query through,
3270+
* and binding_set dropped the 16th name without a word — a0..a14 answered and
3271+
* a15 came back empty. Refuse it instead. */
3272+
cbm_store_t *s = setup_cypher_store();
3273+
char query[2048];
3274+
int off = snprintf(query, sizeof(query), "MATCH (:NoSuchLabelXYZ)");
3275+
for (int i = 0; i < 16; i++) { /* 16 named + the unnamed head = 17 */
3276+
off += snprintf(query + off, sizeof(query) - (size_t)off, "-[:CALLS]->(a%d)", i);
3277+
}
3278+
snprintf(query + off, sizeof(query) - (size_t)off, " RETURN a0.name");
3279+
cbm_cypher_result_t wide = {0};
3280+
ASSERT_TRUE(cbm_cypher_execute(s, query, "test", 0, &wide) != 0);
3281+
ASSERT_NOT_NULL(wide.error);
3282+
ASSERT_TRUE(strstr(wide.error, "node") != NULL);
3283+
cbm_cypher_result_free(&wide);
3284+
3285+
/* One name fewer fits exactly, so the guard still refuses only what a
3286+
* binding genuinely cannot hold. */
3287+
off = snprintf(query, sizeof(query), "MATCH (:NoSuchLabelXYZ)");
3288+
for (int i = 0; i < 15; i++) {
3289+
off += snprintf(query + off, sizeof(query) - (size_t)off, "-[:CALLS]->(a%d)", i);
3290+
}
3291+
snprintf(query + off, sizeof(query) - (size_t)off, " RETURN a0.name");
3292+
cbm_cypher_result_t ok = {0};
3293+
ASSERT_EQ(cbm_cypher_execute(s, query, "test", 0, &ok), 0);
3294+
cbm_cypher_result_free(&ok);
3295+
3296+
cbm_store_close(s);
3297+
PASS();
3298+
}
3299+
3300+
TEST(cypher_scope_check_survives_wide_pattern) {
3301+
/* Regression test for #1995. check_projection_scope models declared names in
3302+
* a fixed array and used to skip the check entirely when a query declared
3303+
* more than it held. So the same out-of-scope name was refused on a narrow
3304+
* query and quietly accepted on a wide one. Both must now be refused. */
3305+
cbm_store_t *s = setup_cypher_store();
3306+
char query[4096];
3307+
3308+
build_node_chain(query, sizeof(query), 10);
3309+
strncat(query, " RETURN zzz.name", sizeof(query) - strlen(query) - 1);
3310+
cbm_cypher_result_t narrow = {0};
3311+
ASSERT_TRUE(cbm_cypher_execute(s, query, "test", 0, &narrow) != 0);
3312+
ASSERT_NOT_NULL(narrow.error);
3313+
ASSERT_TRUE(strstr(narrow.error, "zzz") != NULL);
3314+
cbm_cypher_result_free(&narrow);
3315+
3316+
/* 35 declared names — this one used to answer a zzz.name column of nothing. */
3317+
build_node_chain(query, sizeof(query), 35);
3318+
strncat(query, " RETURN zzz.name", sizeof(query) - strlen(query) - 1);
3319+
cbm_cypher_result_t wide = {0};
3320+
ASSERT_TRUE(cbm_cypher_execute(s, query, "test", 0, &wide) != 0);
3321+
ASSERT_NOT_NULL(wide.error);
3322+
cbm_cypher_result_free(&wide);
32053323

32063324
cbm_store_close(s);
32073325
PASS();
@@ -4521,6 +4639,10 @@ SUITE(cypher) {
45214639
RUN_TEST(cypher_return_star_dedups_repeated_pattern_var);
45224640
RUN_TEST(cypher_return_star_after_with_names_aliases);
45234641
RUN_TEST(cypher_wide_with_refused_not_truncated);
4642+
RUN_TEST(cypher_wide_pattern_refused);
4643+
RUN_TEST(cypher_wide_edge_pattern_refused);
4644+
RUN_TEST(cypher_unnamed_head_takes_a_slot);
4645+
RUN_TEST(cypher_scope_check_survives_wide_pattern);
45244646
RUN_TEST(cypher_parse_neq);
45254647
RUN_TEST(cypher_parse_in);
45264648
RUN_TEST(cypher_parse_is_null);

0 commit comments

Comments
 (0)