Local code intelligence for developers and AI agents. Connect code, docs and infrastructure in a persistent graph, with CBM Lens, MCP tools, agent integrations and change-aware test selection.
C aiderastclaude-codecode-analysiscode-intelligencecodexcursorcypherdeveloper-toolsgemini-cligraph-visualizationkilocodeknowledge-graphmcpmcp-servermodel-context-protocolopencodesqlitetree-sitterwindsurf
/*
* cypher.c — Cypher query engine: lexer, parser, planner, executor.
*
* Translates a subset of Cypher into SQL queries against cbm_store.
* Supports MATCH patterns with relationships, WHERE filters,
* RETURN with COUNT/ORDER BY/LIMIT/DISTINCT.
*/
#include "cypher/cypher.h"
#include "foundation/compat.h"
#include "foundation/constants.h"
#include "store/store.h"
#include "foundation/platform.h"
#include "foundation/limits.h"
#include "foundation/log.h"
#include "foundation/hash_table.h"
#include "foundation/mem_core.h"
enum {
CYP_BUF_16 = 16,
CYP_BUF_48 = 48, /* ASCII '0' */
CYP_BUF_8 = 8,
CYP_BUF_4 = 4,
CYP_MAX_TOKEN = 10, /* max token lookahead */
CYP_PAIR = 2,
CYP_TRIPLE = 3,
CYP_INIT_CAP4 = 4, /* initial small array capacity */
CYP_INIT_CAP8 = 8, /* initial medium array capacity */
CYP_MAX_VARS = 16, /* max Cypher variables in a query */
CYP_MAX_EDGE_VARS = 8, /* max edge variables */
CYP_GROWTH_10 = 10, /* binding growth factor */
CYP_GROWTH_2 = 2, /* geometric buffer growth (#1196) */
CYP_CHAR_IDX1 = 1, /* second character index (e.g. op[1]) */
CYP_EBUF_MASK = 7,
CYP_NODE_COLS = 4, /* columns per node var: name, qn, label, file */
CYP_EDGE_COLS = 3, /* columns per edge var: name, qn, label */
CYP_COL_BUF = 48, /* max column buffer (16 vars * 3 cols) */
CYP_FOUND_NONE = -1,
/* search miss sentinel */ /* mask for ebuf ring buffer (8 entries) */
};
#define CYP_DBL_MAX 1e308
/* execute_single binds the first pattern's leading node even when the query
* leaves it unnamed, so the engine needs a name for it. The binding slot is
* real, which is why check_pattern_var_capacity counts it. */
#define CYP_ANON_HEAD_VAR "_n0"
#include <ctype.h>
#include <limits.h> // INT_MAX
#include "foundation/compat_regex.h"
#include <stddef.h>
#include <stdint.h> // int64_t
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* ── Helpers ────────────────────────────────────────────────────── */
static char *heap_strdup(const char *s) {
if (!s) {
return NULL;
}
size_t len = strlen(s);
char *d = malloc(len + SKIP_ONE);
if (d) {
memcpy(d, s, len + 1);
}
return d;
}
static char *heap_strndup(const char *s, size_t n) {
char *d = malloc(n + SKIP_ONE);
if (d) {
memcpy(d, s, n);
d[n] = '\0';
}
return d;
}
/* ══════════════════════════════════════════════════════════════════
* LEXER
* ══════════════════════════════════════════════════════════════════ */
static void lex_push(cbm_lex_result_t *r, cbm_token_type_t type, const char *text, int pos) {
if (r->count >= r->capacity) {
r->capacity = r->capacity ? r->capacity * PAIR_LEN : CBM_SZ_32;
r->tokens = safe_realloc(r->tokens, r->capacity * sizeof(cbm_token_t));
}
r->tokens[r->count++] = (cbm_token_t){.type = type, .text = heap_strdup(text), .pos = pos};
}
static void lex_push_n(cbm_lex_result_t *r, cbm_token_type_t type, const char *start, size_t len,
int pos) {
if (r->count >= r->capacity) {
r->capacity = r->capacity ? r->capacity * PAIR_LEN : CBM_SZ_32;
r->tokens = safe_realloc(r->tokens, r->capacity * sizeof(cbm_token_t));
}
r->tokens[r->count++] =
(cbm_token_t){.type = type, .text = heap_strndup(start, len), .pos = pos};
}
/* Parse a string literal (with escape handling) into the token list.
* *pos points at the character after the opening quote; updated past closing quote. */
static void lex_string_literal(const char *input, int len, int *pos, char quote,
cbm_lex_result_t *out) {
int start = *pos;
char buf[CBM_SZ_4K];
int blen = 0;
const int max_blen = CBM_SZ_4K - 1;
while (*pos < len && input[*pos] != quote) {
if (input[*pos] == '\\' && *pos + SKIP_ONE < len) {
(*pos)++;
if (blen < max_blen) {
switch (input[*pos]) {
case 'n':
buf[blen++] = '\n';
break;
case 't':
buf[blen++] = '\t';
break;
case '\\':
buf[blen++] = '\\';
break;
default:
buf[blen++] = input[*pos];
break;
}
}
} else {
if (blen < max_blen) {
buf[blen++] = input[*pos];
}
}
(*pos)++;
}
buf[blen] = '\0';
if (*pos < len) {
(*pos)++; /* skip closing quote */
}
lex_push(out, TOK_STRING, buf, start - SKIP_ONE);
}
/* Keyword table (case-insensitive lookup) */
typedef struct {
const char *name;
cbm_token_type_t type;
} kw_entry_t;
static const kw_entry_t keywords[] = {
/* Core query */
{"MATCH", TOK_MATCH},
{"WHERE", TOK_WHERE},
{"RETURN", TOK_RETURN},
{"ORDER", TOK_ORDER},
{"BY", TOK_BY},
{"LIMIT", TOK_LIMIT},
{"AND", TOK_AND},
{"OR", TOK_OR},
{"AS", TOK_AS},
{"DISTINCT", TOK_DISTINCT},
{"COUNT", TOK_COUNT},
{"CONTAINS", TOK_CONTAINS},
{"STARTS", TOK_STARTS},
{"WITH", TOK_WITH},
{"NOT", TOK_NOT},
{"ASC", TOK_ASC},
{"DESC", TOK_DESC},
/* Phase 1-2: operators + expression */
{"ENDS", TOK_ENDS},
{"IN", TOK_IN},
{"IS", TOK_IS},
{"NULL", TOK_NULL_KW},
{"XOR", TOK_XOR},
/* Phase 3-4: SKIP, UNION, UNWIND, aggregates */
{"SKIP", TOK_SKIP},
{"UNION", TOK_UNION},
{"UNWIND", TOK_UNWIND},
{"SUM", TOK_SUM},
{"AVG", TOK_AVG},
{"MIN", TOK_MIN_KW},
{"MAX", TOK_MAX_KW},
{"COLLECT", TOK_COLLECT},
/* Phase 5: string functions + CASE */
{"toLower", TOK_TOLOWER},
{"toUpper", TOK_TOUPPER},
{"toString", TOK_TOSTRING},
{"tolower", TOK_TOLOWER},
{"toupper", TOK_TOUPPER},
{"tostring", TOK_TOSTRING},
{"CASE", TOK_CASE},
{"WHEN", TOK_WHEN},
{"THEN", TOK_THEN},
{"ELSE", TOK_ELSE},
{"END", TOK_END},
/* Phase 7: OPTIONAL */
{"OPTIONAL", TOK_OPTIONAL},
/* Recognized-but-unsupported write/admin keywords */
{"CREATE", TOK_CREATE},
{"DELETE", TOK_DELETE},
{"DETACH", TOK_DETACH},
{"SET", TOK_SET},
{"REMOVE", TOK_REMOVE},
{"MERGE", TOK_MERGE},
{"YIELD", TOK_YIELD},
{"CALL", TOK_CALL},
{"ALL", TOK_ALL},
{"TRUE", TOK_TRUE},
{"FALSE", TOK_FALSE},
{"EXISTS", TOK_EXISTS},
{"MANDATORY", TOK_MANDATORY},
{"FOREACH", TOK_FOREACH},
{"ON", TOK_ON},
{"ADD", TOK_ADD},
{"CONSTRAINT", TOK_CONSTRAINT},
{"DO", TOK_DO},
{"DROP", TOK_DROP},
{"FOR", TOK_FOR},
{"FROM", TOK_FROM},
{"GRAPH", TOK_GRAPH},
{"OF", TOK_OF},
{"REQUIRE", TOK_REQUIRE},
{"SCALAR", TOK_SCALAR},
{"UNIQUE", TOK_UNIQUE},
{NULL, 0}};
static cbm_token_type_t keyword_lookup(const char *word) {
/* Case-insensitive compare */
for (const kw_entry_t *kw = keywords; kw->name; kw++) {
if (strcasecmp(word, kw->name) == 0) {
return kw->type;
}
}
return TOK_IDENT;
}
/* Try to match a two-character token at position i. Returns true and advances i if matched. */
static bool lex_try_two_char(const char *input, int len, int *i, cbm_lex_result_t *out) {
static const struct {
char c1, c2;
cbm_token_type_t type;
const char *text;
} pairs[] = {
{'!', '=', TOK_NEQ, "!="}, {'<', '>', TOK_NEQ, "<>"}, {'=', '~', TOK_EQTILDE, "=~"},
{'>', '=', TOK_GTE, ">="}, {'<', '=', TOK_LTE, "<="}, {'.', '.', TOK_DOTDOT, ".."},
};
char c = input[*i];
if (*i + SKIP_ONE >= len) {
return false;
}
char c2 = input[*i + SKIP_ONE];
for (int p = 0; p < (int)(sizeof(pairs) / sizeof(pairs[0])); p++) {
if (c == pairs[p].c1 && c2 == pairs[p].c2) {
lex_push(out, pairs[p].type, pairs[p].text, *i);
*i += PAIR_LEN;
return true;
}
}
return false;
}
/* Try to match a single-character token. Returns TOK_EOF if not matched. */
static cbm_token_type_t lex_single_char(char c) {
switch (c) {
case '(':
return TOK_LPAREN;
case ')':
return TOK_RPAREN;
case '[':
return TOK_LBRACKET;
case ']':
return TOK_RBRACKET;
case '-':
return TOK_DASH;
case '>':
return TOK_GT;
case '<':
return TOK_LT;
case ':':
return TOK_COLON;
case '.':
return TOK_DOT;
case '{':
return TOK_LBRACE;
case '}':
return TOK_RBRACE;
case '*':
return TOK_STAR;
case ',':
return TOK_COMMA;
case '=':
return TOK_EQ;
case '|':
return TOK_PIPE;
default:
return TOK_EOF;
}
}
/* Try to lex an identifier or keyword starting at position i. Returns true if matched. */
static bool lex_try_ident(const char *input, int len, int *i, cbm_lex_result_t *out) {
char c = input[*i];
if (!isalpha((unsigned char)c) && c != '_') {
return false;
}
int start = *i;
while (*i < len && (isalnum((unsigned char)input[*i]) || input[*i] == '_')) {
(*i)++;
}
char word[CBM_SZ_256];
int wlen = *i - start;
if (wlen >= (int)sizeof(word)) {
wlen = (int)sizeof(word) - SKIP_ONE;
}
memcpy(word, input + start, wlen);
word[wlen] = '\0';
cbm_token_type_t type = keyword_lookup(word);
lex_push_n(out, type, input + start, *i - start, start);
return true;
}
/* Try to lex a number starting at position i. Returns true if matched. */
static bool lex_try_number(const char *input, int len, int *i, cbm_lex_result_t *out) {
char c = input[*i];
if (!isdigit((unsigned char)c) &&
!(c == '.' && *i + SKIP_ONE < len && isdigit((unsigned char)input[*i + SKIP_ONE]))) {
return false;
}
int start = *i;
while (*i < len && (isdigit((unsigned char)input[*i]) ||
(input[*i] == '.' && *i + SKIP_ONE < len && input[*i + SKIP_ONE] != '.'))) {
(*i)++;
}
lex_push_n(out, TOK_NUMBER, input + start, *i - start, start);
return true;
}
/* Skip whitespace and comments. Returns true if something was skipped. */
static bool lex_skip_whitespace_comments(const char *input, int len, int *i) {
if (isspace((unsigned char)input[*i])) {
(*i)++;
return true;
}
if (*i + SKIP_ONE < len && input[*i] == '/' && input[*i + SKIP_ONE] == '/') {
while (*i < len && input[*i] != '\n') {
(*i)++;
}
return true;
}
/* SQL-style -- single-line comment */
if (*i + SKIP_ONE < len && input[*i] == '-' && input[*i + SKIP_ONE] == '-') {
while (*i < len && input[*i] != '\n') {
(*i)++;
}
return true;
}
if (*i + SKIP_ONE < len && input[*i] == '/' && input[*i + SKIP_ONE] == '*') {
*i += PAIR_LEN;
while (*i + SKIP_ONE < len && !(input[*i] == '*' && input[*i + SKIP_ONE] == '/')) {
(*i)++;
}
if (*i + SKIP_ONE < len) {
*i += PAIR_LEN;
}
return true;
}
return false;
}
int cbm_lex(const char *input, cbm_lex_result_t *out) {
memset(out, 0, sizeof(*out));
if (!input) {
return CBM_NOT_FOUND;
}
int len = (int)strlen(input);
int i = 0;
while (i < len) {
if (lex_skip_whitespace_comments(input, len, &i)) {
continue;
}
char c = input[i];
/* String literals */
if (c == '"' || c == '\'') {
char quote = c;
i++;
lex_string_literal(input, len, &i, quote, out);
continue;
}
/* Numbers — stop before ".." (DOTDOT operator) */
if (lex_try_number(input, len, &i, out)) {
continue;
}
/* Identifiers / keywords */
if (lex_try_ident(input, len, &i, out)) {
continue;
}
/* Two-character tokens */
{
bool found_two = lex_try_two_char(input, len, &i, out);
if (found_two) {
continue;
}
}
/* Single-character tokens */
cbm_token_type_t stype = lex_single_char(c);
if (stype != TOK_EOF) {
char buf[PAIR_LEN] = {c, '\0'};
lex_push(out, stype, buf, i);
i++;
continue;
}
/* Unknown character — skip */
i++;
}
/* Add EOF */
lex_push(out, TOK_EOF, "", i);
return 0;
}
void cbm_lex_free(cbm_lex_result_t *r) {
if (!r) {
return;
}
for (int i = 0; i < r->count; i++) {
safe_str_free(&r->tokens[i].text);
}
free(r->tokens);
free(r->error);
memset(r, 0, sizeof(*r));
}
/* ══════════════════════════════════════════════════════════════════
* PARSER
* ══════════════════════════════════════════════════════════════════ */
/* The WHERE grammar descends once per nested '(' and once per NOT, so parse
* depth follows the query text rather than anything bounded. A few tens of KB of
* either exhausts the stack before any semantic limit applies. 256 is far past
* any hand-written or generated query while leaving the stack untouched. */
enum { CYPHER_MAX_PARSE_DEPTH = 256 };
typedef struct {
const cbm_token_t *tokens;
int count;
int pos;
int depth; /* current recursive-descent depth; see CYPHER_MAX_PARSE_DEPTH */
char error[CBM_SZ_512];
} parser_t;
/* Enter one level of recursive descent. Returns false when the cap is hit, in
* which case the caller must return NULL without recursing. */
static bool parse_depth_enter(parser_t *p) {
if (p->depth >= CYPHER_MAX_PARSE_DEPTH) {
snprintf(p->error, sizeof(p->error), "expression nested deeper than %d levels",
CYPHER_MAX_PARSE_DEPTH);
return false;
}
p->depth++;
return true;
}
static void parse_depth_leave(parser_t *p) {
p->depth--;
}
static const cbm_token_t *peek(parser_t *p) {
if (p->pos >= p->count) {
return &p->tokens[p->count - SKIP_ONE]; /* EOF */
}
return &p->tokens[p->pos];
}
static const cbm_token_t *advance(parser_t *p) {
if (p->pos >= p->count) {
return &p->tokens[p->count - SKIP_ONE];
}
return &p->tokens[p->pos++];
}
static bool check(parser_t *p, cbm_token_type_t type) {
return peek(p)->type == type;
}
static bool match(parser_t *p, cbm_token_type_t type) {
if (check(p, type)) {
advance(p);
return true;
}
return false;
}
static const cbm_token_t *expect(parser_t *p, cbm_token_type_t type) {
if (check(p, type)) {
return advance(p);
}
snprintf(p->error, sizeof(p->error), "expected token type %d, got %d at pos %d", type,
peek(p)->type, peek(p)->pos);
return NULL;
}
/* Free the first n entries of a property array and the array itself. */
static void free_prop_entries(cbm_prop_filter_t *arr, int n) {
for (int i = 0; i < n; i++) {
safe_str_free(&arr[i].key);
safe_str_free(&arr[i].value);
}
free(arr);
}
/* Parse inline properties: {key: "value", ...} */
static int parse_props(parser_t *p, cbm_prop_filter_t **out, int *count) {
*out = NULL;
*count = 0;
if (!match(p, TOK_LBRACE)) {
return 0;
}
int cap = CYP_INIT_CAP4;
int n = 0;
cbm_prop_filter_t *arr = malloc(cap * sizeof(cbm_prop_filter_t));
if (!arr) {
return CBM_NOT_FOUND;
}
while (!check(p, TOK_RBRACE) && !check(p, TOK_EOF)) {
/* Every failure frees the entries already parsed, not only the array. */
const cbm_token_t *key = expect(p, TOK_IDENT);
if (!key) {
free_prop_entries(arr, n);
return CBM_NOT_FOUND;
}
if (!expect(p, TOK_COLON)) {
free_prop_entries(arr, n);
return CBM_NOT_FOUND;
}
const cbm_token_t *val = expect(p, TOK_STRING);
if (!val) {
free_prop_entries(arr, n);
return CBM_NOT_FOUND;
}
if (n >= cap) {
int new_cap = cap * PAIR_LEN;
void *tmp = realloc(arr, new_cap * sizeof(cbm_prop_filter_t));
if (!tmp) {
free_prop_entries(arr, n);
return CBM_NOT_FOUND;
}
arr = tmp;
cap = new_cap;
}
const char *new_key = heap_strdup(key->text);
const char *new_val = heap_strdup(val->text);
if (!new_key || !new_val) {
safe_str_free(&new_key);
safe_str_free(&new_val);
free_prop_entries(arr, n);
return CBM_NOT_FOUND;
}
arr[n].key = new_key;
arr[n].value = new_val;
n++;
match(p, TOK_COMMA); /* optional comma */
}
expect(p, TOK_RBRACE);
*out = arr;
*count = n;
return 0;
}
/* Parse node: (variable:Label {props}) */
static int parse_node(parser_t *p, cbm_node_pattern_t *out) {
memset(out, 0, sizeof(*out));
if (!expect(p, TOK_LPAREN)) {
return CBM_NOT_FOUND;
}
/* Optional variable */
if (check(p, TOK_IDENT)) {
/* Lookahead: if next is COLON, this is a variable */
/* Or if next is RPAREN/LBRACE, this is a variable without label */
out->variable = heap_strdup(advance(p)->text);
}
/* Optional :Label, with openCypher label alternation :A|B|C (#242).
* Stored as a single "A|B|C" string; the matcher splits on '|'. */
if (match(p, TOK_COLON)) {
const cbm_token_t *label = expect(p, TOK_IDENT);
if (!label) {
return CBM_NOT_FOUND;
}
char lbuf[CBM_SZ_256];
int ll = snprintf(lbuf, sizeof(lbuf), "%s", label->text);
while (match(p, TOK_PIPE)) {
const cbm_token_t *alt = expect(p, TOK_IDENT);
if (!alt) {
return CBM_NOT_FOUND;
}
int w = snprintf(lbuf + ll, (ll < (int)sizeof(lbuf)) ? sizeof(lbuf) - (size_t)ll : 0,
"|%s", alt->text);
if (w > 0) {
ll += w;
}
if (ll >= (int)sizeof(lbuf)) {
break; /* buffer full */
}
}
out->label = heap_strdup(lbuf);
}
/* Optional {props} */
if (check(p, TOK_LBRACE)) {
if (parse_props(p, &out->props, &out->prop_count) < 0) {
return CBM_NOT_FOUND;
}
}
if (!expect(p, TOK_RPAREN)) {
return CBM_NOT_FOUND;
}
return 0;
}
/* Parse *min..max hop range after the star token has been consumed */
static void parse_hop_range(parser_t *p, int *min_hops, int *max_hops) {
if (check(p, TOK_NUMBER)) {
int val = (int)strtol(peek(p)->text, NULL, CBM_DECIMAL_BASE);
advance(p);
if (match(p, TOK_DOTDOT)) {
*min_hops = val;
*max_hops =
check(p, TOK_NUMBER) ? (int)strtol(advance(p)->text, NULL, CBM_DECIMAL_BASE) : 0;
} else {
/* *N means 1..N */
*min_hops = SKIP_ONE;
*max_hops = val;
}
} else if (match(p, TOK_DOTDOT)) {
*min_hops = SKIP_ONE;
*max_hops =
check(p, TOK_NUMBER) ? (int)strtol(advance(p)->text, NULL, CBM_DECIMAL_BASE) : 0;
} else {
/* * alone = unbounded */
*min_hops = SKIP_ONE;
*max_hops = 0;
}
}
/* Parse relationship type list after ':' inside brackets. Returns -1 on error. */
static int parse_rel_types(parser_t *p, cbm_rel_pattern_t *out) {
int cap = CYP_INIT_CAP4;
int n = 0;
const char **types = malloc(cap * sizeof(const char *));
if (!types) {
return CBM_NOT_FOUND;
}
const cbm_token_t *t = expect(p, TOK_IDENT);
if (!t) {
free(types);
return CBM_NOT_FOUND;
}
const char *first_type = heap_strdup(t->text);
if (!first_type) {
free(types);
return CBM_NOT_FOUND;
}
types[n++] = first_type;
while (match(p, TOK_PIPE)) {
t = expect(p, TOK_IDENT);
if (!t) {
for (int i = 0; i < n; i++) {
safe_str_free(&types[i]);
}
free(types);
return CBM_NOT_FOUND;
}
if (n >= cap) {
int new_cap = cap * PAIR_LEN;
void *tmp = realloc(types, new_cap * sizeof(const char *));
if (!tmp) {
for (int i = 0; i < n; i++) {
safe_str_free(&types[i]);
}
free(types);
return CBM_NOT_FOUND;
}
types = (const char **)tmp;
cap = new_cap;
}
const char *next_type = heap_strdup(t->text);
if (!next_type) {
for (int i = 0; i < n; i++) {
safe_str_free(&types[i]);
}
free(types);
return CBM_NOT_FOUND;
}
types[n++] = next_type;
}
out->types = types;
out->type_count = n;
return 0;
}
/* Parse bracket content of a relationship: [var:TYPE*hops] */
static int parse_rel_bracket(parser_t *p, cbm_rel_pattern_t *out) {
/* Optional variable */
if (check(p, TOK_IDENT) && !check(p, TOK_COLON)) {
out->variable = heap_strdup(advance(p)->text);
}
/* Optional :Types */
if (match(p, TOK_COLON)) {
if (parse_rel_types(p, out) < 0) {
return CBM_NOT_FOUND;
}
}
/* Optional *hop_range */
if (match(p, TOK_STAR)) {
parse_hop_range(p, &out->min_hops, &out->max_hops);
}
if (!expect(p, TOK_RBRACKET)) {
return CBM_NOT_FOUND;
}
return 0;
}
/* Parse relationship: -[:TYPE|TYPE2*min..max]-> or <-[...]- */
static int parse_rel(parser_t *p, cbm_rel_pattern_t *out) {
memset(out, 0, sizeof(*out));
out->min_hops = SKIP_ONE;
out->max_hops = SKIP_ONE;
/* Check for leading < (inbound) */
bool leading_lt = match(p, TOK_LT);
if (!expect(p, TOK_DASH)) {
return CBM_NOT_FOUND;
}
/* Optional bracket content */
if (match(p, TOK_LBRACKET)) {
if (parse_rel_bracket(p, out) < 0) {
return CBM_NOT_FOUND;
}
}
if (!expect(p, TOK_DASH)) {
return CBM_NOT_FOUND;
}
/* Check for trailing > (outbound) */
bool trailing_gt = match(p, TOK_GT);
/* Determine direction */
if (leading_lt && !trailing_gt) {
out->direction = heap_strdup("inbound");
} else if (!leading_lt && trailing_gt) {
out->direction = heap_strdup("outbound");
} else {
out->direction = heap_strdup("any");
}
return 0;
}
/* ── Expression tree helpers ────────────────────────────────────── */
static void expr_free(cbm_expr_t *e) {
enum { EXPR_FREE_STACK = 128 };
cbm_expr_t *stack[EXPR_FREE_STACK];
int top = 0;
if (e) {
stack[top++] = e;
}
while (top > 0) {
cbm_expr_t *cur = stack[--top];
if (cur->type == EXPR_CONDITION) {
safe_str_free(&cur->cond.variable);
safe_str_free(&cur->cond.property);
safe_str_free(&cur->cond.op);
safe_str_free(&cur->cond.value);
safe_str_free(&cur->cond.coalesce_default);
safe_str_free(&cur->cond.rhs_variable);
safe_str_free(&cur->cond.rhs_property);
for (int i = 0; i < cur->cond.in_value_count; i++) {
safe_str_free(&cur->cond.in_values[i]);
}
free(cur->cond.in_values);
safe_str_free(&cur->cond.func);
for (int i = 0; i < cur->cond.arg_count; i++) {
safe_str_free(&cur->cond.args[i].variable);
safe_str_free(&cur->cond.args[i].property);
safe_str_free(&cur->cond.args[i].literal);
}
free(cur->cond.args);
}
if (cur->right) {
if (top < EXPR_FREE_STACK) {
stack[top++] = cur->right;
} else {
expr_free(cur->right); /* recurse when stack overflows */
}
}
if (cur->left) {
if (top < EXPR_FREE_STACK) {
stack[top++] = cur->left;
} else {
expr_free(cur->left); /* recurse when stack overflows */
}
}
free(cur);
}
}
static cbm_expr_t *expr_leaf(cbm_condition_t c) {
cbm_expr_t *e = calloc(CBM_ALLOC_ONE, sizeof(cbm_expr_t));
e->type = EXPR_CONDITION;
e->cond = c;
return e;
}
static cbm_expr_t *expr_binary(cbm_expr_type_t type, cbm_expr_t *left, cbm_expr_t *right) {
cbm_expr_t *e = calloc(CBM_ALLOC_ONE, sizeof(cbm_expr_t));
e->type = type;
e->left = left;
e->right = right;
return e;
}
static cbm_expr_t *expr_not(cbm_expr_t *child) {
cbm_expr_t *e = calloc(CBM_ALLOC_ONE, sizeof(cbm_expr_t));
e->type = EXPR_NOT;
e->left = child;
return e;
}
/* ── Unsupported keyword detection ─────────────────────────────── */
static const char *unsupported_clause_error(cbm_token_type_t type) {
switch (type) {
case TOK_CREATE:
return "unsupported Cypher feature: CREATE clause (write operations not supported)";
case TOK_DELETE:
return "unsupported Cypher feature: DELETE clause (write operations not supported)";
case TOK_DETACH:
return "unsupported Cypher feature: DETACH DELETE (write operations not supported)";
case TOK_SET:
return "unsupported Cypher feature: SET clause (write operations not supported)";
case TOK_REMOVE:
return "unsupported Cypher feature: REMOVE clause (write operations not supported)";
case TOK_MERGE:
return "unsupported Cypher feature: MERGE clause (write operations not supported)";
case TOK_YIELD:
return "unsupported Cypher feature: YIELD clause";
case TOK_CALL:
return "unsupported Cypher feature: CALL clause (stored procedures not supported)";
case TOK_FOREACH:
return "unsupported Cypher feature: FOREACH clause";
case TOK_MANDATORY:
return "unsupported Cypher feature: MANDATORY MATCH";
case TOK_DROP:
return "unsupported Cypher feature: DROP (schema operations not supported)";
case TOK_CONSTRAINT:
return "unsupported Cypher feature: CONSTRAINT (schema operations not supported)";
default:
return NULL;
}
}
/* ── Recursive descent WHERE parser (Phase 2) ──────────────────── */
/* Forward declarations for recursive descent */
static cbm_expr_t *parse_or_expr(parser_t *p);
/* Multi-arg scalar function support, shared with the RETURN-item parser (#874) */
static bool is_multiarg_func_call(parser_t *p);
static int parse_multiarg_func_item(parser_t *p, cbm_return_item_t *item);
/* Free a multi-arg function argument array. */
static void func_args_free(cbm_func_arg_t *args, int count) {
for (int i = 0; i < count; i++) {
safe_str_free(&args[i].variable);
safe_str_free(&args[i].property);
safe_str_free(&args[i].literal);
}
free(args);
}
/* Free the fields of a partially-parsed multi-arg function item. */
static void func_item_fields_free(cbm_return_item_t *item) {
safe_str_free(&item->variable);
safe_str_free(&item->property);
safe_str_free(&item->func);
func_args_free(item->args, item->arg_count);
item->args = NULL;
item->arg_count = 0;
}
/* Free the function-call fields of a WHERE condition (#874). */
static void cond_func_fields_free(cbm_condition_t *c) {
safe_str_free(&c->func);
func_args_free(c->args, c->arg_count);
c->args = NULL;
c->arg_count = 0;
}
/* Parse IN [val, val, ...] list. Returns expr_leaf or NULL on error. */
static cbm_expr_t *parse_in_list(parser_t *p, cbm_condition_t *c) {
advance(p);
c->op = heap_strdup("IN");
if (!c->op) {
safe_str_free(&c->variable);
safe_str_free(&c->property);
return NULL;
}
if (!expect(p, TOK_LBRACKET)) {
safe_str_free(&c->variable);
safe_str_free(&c->property);
safe_str_free(&c->op);
return NULL;
}
int vcap = CYP_INIT_CAP8;
int vn = 0;
const char **vals = malloc(vcap * sizeof(const char *));
if (!vals) {
safe_str_free(&c->variable);
safe_str_free(&c->property);
safe_str_free(&c->op);
return NULL;
}
while (!check(p, TOK_RBRACKET) && !check(p, TOK_EOF)) {
if (vn > 0) {
match(p, TOK_COMMA);
}
if (check(p, TOK_STRING) || check(p, TOK_NUMBER)) {
if (vn >= vcap) {
int new_vcap = vcap * PAIR_LEN;
void *tmp = realloc((void *)vals, new_vcap * sizeof(const char *));
if (!tmp) {
for (int i = 0; i < vn; i++) {
safe_str_free(&vals[i]);
}
safe_free(vals);
safe_str_free(&c->variable);
safe_str_free(&c->property);
safe_str_free(&c->op);
return NULL;
}
vals = (const char **)tmp;
vcap = new_vcap;
}
const char *new_val = heap_strdup(advance(p)->text);
if (!new_val) {
for (int i = 0; i < vn; i++) {
safe_str_free(&vals[i]);
}
safe_free(vals);
safe_str_free(&c->variable);
safe_str_free(&c->property);
safe_str_free(&c->op);
return NULL;
}
vals[vn++] = new_val;
} else {
break;
}
}
expect(p, TOK_RBRACKET);
c->in_values = vals;
c->in_value_count = vn;
return expr_leaf(*c);
}
/* Try to parse a comparison operator. Returns heap-allocated op string or NULL. */
static char *parse_comparison_op(parser_t *p) {
if (match(p, TOK_EQ)) {
return heap_strdup("=");
}
if (match(p, TOK_NEQ)) {
return heap_strdup("<>");
}
if (match(p, TOK_EQTILDE)) {
return heap_strdup("=~");
}
if (match(p, TOK_GTE)) {
return heap_strdup(">=");
}
if (match(p, TOK_LTE)) {
return heap_strdup("<=");
}
if (match(p, TOK_GT)) {
return heap_strdup(">");
}
if (match(p, TOK_LT)) {
return heap_strdup("<");
}
if (check(p, TOK_CONTAINS)) {
advance(p);
return heap_strdup("CONTAINS");
}
if (check(p, TOK_STARTS)) {
advance(p);
expect(p, TOK_WITH);
return heap_strdup("STARTS WITH");
}
if (check(p, TOK_ENDS)) {
advance(p);
expect(p, TOK_WITH);
return heap_strdup("ENDS WITH");
}
return NULL;
}
/* Parse a single condition: var.prop OP value | var.prop IS [NOT] NULL | var.prop IN [...] */
/* Free the heap fields of a standalone node pattern (not owned by a pattern). */
static void free_one_node_pattern(cbm_node_pattern_t *n) {
safe_str_free(&n->variable);
safe_str_free(&n->label);
for (int j = 0; j < n->prop_count; j++) {
safe_str_free(&n->props[j].key);
safe_str_free(&n->props[j].value);
}
free(n->props);
memset(n, 0, sizeof(*n));
}
/* Free the heap fields of a standalone relationship pattern. */
static void free_one_rel_pattern(cbm_rel_pattern_t *r) {
safe_str_free(&r->variable);
for (int j = 0; j < r->type_count; j++) {
safe_str_free(&r->types[j]);
}
free(r->types);
safe_str_free(&r->direction);
memset(r, 0, sizeof(*r));
}
/* Parse a bounded EXISTS predicate: EXISTS { (anchor)-[:TYPE]->() } — a
* single-hop, edge-type-specific existence check anchored on a bound variable
* (e.g. WHERE NOT EXISTS { (f)<-[:CALLS]-() } finds functions with no callers).
* Multi-hop / nested-WHERE EXISTS is intentionally unsupported. */
static cbm_expr_t *parse_exists_predicate(parser_t *p, bool negated) {
advance(p); /* EXISTS */
if (!match(p, TOK_LBRACE)) {
snprintf(p->error, sizeof(p->error), "expected '{' after EXISTS at pos %d", peek(p)->pos);
return NULL;
}
cbm_node_pattern_t anchor = {0};
cbm_rel_pattern_t rel = {0};
cbm_node_pattern_t far_node = {0};
if (parse_node(p, &anchor) < 0 || parse_rel(p, &rel) < 0 || parse_node(p, &far_node) < 0) {
free_one_node_pattern(&anchor);
free_one_rel_pattern(&rel);
free_one_node_pattern(&far_node);
snprintf(p->error, sizeof(p->error),
"unsupported EXISTS pattern — only the single-hop form "
"'(var)-[:TYPE]->()' is supported");
return NULL;
}
expect(p, TOK_RBRACE);
cbm_condition_t c = {0};
c.negated = negated;
c.op = heap_strdup("EXISTS");
c.variable = heap_strdup(anchor.variable ? anchor.variable : "");
c.value = (rel.type_count > 0 && rel.types[0]) ? heap_strdup(rel.types[0]) : NULL;
c.exists_dir = (rel.direction && strcmp(rel.direction, "inbound") == 0) ? 1
: (rel.direction && strcmp(rel.direction, "any") == 0) ? 2
: 0;
free_one_node_pattern(&anchor);
free_one_rel_pattern(&rel);
free_one_node_pattern(&far_node);
return expr_leaf(c);
}
/* Free what a condition parser owns when it gives up mid-condition. */
static void cond_parse_fail_free(cbm_condition_t *c) {
cond_func_fields_free(c);
safe_str_free(&c->variable);
safe_str_free(&c->property);
safe_str_free(&c->op);
safe_str_free(&c->coalesce_default);
safe_str_free(&c->rhs_variable);
safe_str_free(&c->rhs_property);
}
enum { COND_RHS_REF = 1 };
/* RHS operand that names a row value instead of a literal: var.prop, or a bare
* alias such as a WITH projection (#2591). Returns COND_RHS_REF when one was
* parsed, 0 when the next token is not one, CBM_NOT_FOUND with p->error set
* when it is malformed or a function call. */
static int parse_condition_rhs_ref(parser_t *p, cbm_condition_t *c) {
if (p->pos + SKIP_ONE < p->count && p->tokens[p->pos + SKIP_ONE].type == TOK_LPAREN) {
snprintf(p->error, sizeof(p->error),
"unsupported function '%s' on the right side of a WHERE comparison "
"(only literals and var.prop are supported)",
peek(p)->text);
return CBM_NOT_FOUND;
}
if (!check(p, TOK_IDENT)) {
return 0;
}
c->rhs_variable = heap_strdup(advance(p)->text);
if (match(p, TOK_DOT)) {
const cbm_token_t *prop = expect(p, TOK_IDENT);
if (!prop) {
return CBM_NOT_FOUND;
}
c->rhs_property = heap_strdup(prop->text);
}
return COND_RHS_REF;
}
/* Parse the operator + value tail shared by every condition subject
* (var[.prop] and multi-arg functions like coalesce(...)): IS [NOT] NULL,
* IN [...], or a comparison operator with a literal value or a property
* reference (a.x = b.y). */
static cbm_expr_t *parse_condition_op(parser_t *p, cbm_condition_t *c) {
/* IS NULL / IS NOT NULL */
if (check(p, TOK_IS)) {
advance(p);
if (match(p, TOK_NOT)) {
c->op = heap_strdup("IS NOT NULL");
expect(p, TOK_NULL_KW);
} else {
expect(p, TOK_NULL_KW);
c->op = heap_strdup("IS NULL");
}
return expr_leaf(*c);
}
/* IN [...] */
if (check(p, TOK_IN)) {
cbm_expr_t *e = parse_in_list(p, c);
if (!e) {
cond_func_fields_free(c);
}
return e;
}
/* Standard operators */
c->op = parse_comparison_op(p);
if (!c->op) {
snprintf(p->error, sizeof(p->error), "unexpected operator at pos %d", peek(p)->pos);
cond_parse_fail_free(c);
return NULL;
}
/* Value */
if (check(p, TOK_STRING) || check(p, TOK_NUMBER)) {
c->value = heap_strdup(advance(p)->text);
} else if (check(p, TOK_TRUE)) {
advance(p);
c->value = heap_strdup("true");
} else if (check(p, TOK_FALSE)) {
advance(p);
c->value = heap_strdup("false");
} else if (parse_condition_rhs_ref(p, c) <= 0) {
if (!p->error[0]) {
snprintf(p->error, sizeof(p->error), "expected value at pos %d", peek(p)->pos);
}
cond_parse_fail_free(c);
return NULL;
}
return expr_leaf(*c);
}
/* parse_condition_lhs result: the label-test form is a complete condition. */
enum { COND_LHS_COMPLETE = 1 };
/* Parse the left-hand side of a WHERE condition into c.
* Returns CBM_NOT_FOUND on error, 0 when an operator/value should follow, and
* COND_LHS_COMPLETE when the condition is already complete (label test). */
static int parse_condition_lhs(parser_t *p, cbm_condition_t *c) {
if (is_multiarg_func_call(p)) {
/* Multi-arg scalar function LHS: coalesce(f.depth, 0) >= 2 (#874).
* Reuse the RETURN-item parser, then move ownership into the condition. */
cbm_return_item_t fitem;
memset(&fitem, 0, sizeof(fitem));
if (parse_multiarg_func_item(p, &fitem) < 0) {
func_item_fields_free(&fitem);
return CBM_NOT_FOUND;
}
c->variable = fitem.variable;
c->property = fitem.property;
c->func = fitem.func;
c->args = fitem.args;
c->arg_count = fitem.arg_count;
return 0;
}
if (check(p, TOK_IDENT) && p->pos + SKIP_ONE < p->count &&
p->tokens[p->pos + SKIP_ONE].type == TOK_LPAREN) {
/* Unrecognised function call in WHERE — fail loudly with the supported
* set instead of the misleading "unexpected operator" (#874). */
snprintf(p->error, sizeof(p->error),
"unsupported function '%s' in WHERE (supported: coalesce, substring, replace, "
"left, right)",
peek(p)->text);
return CBM_NOT_FOUND;
}
const cbm_token_t *var = expect(p, TOK_IDENT);
if (!var) {
return CBM_NOT_FOUND;
}
/* Label test: WHERE n:Label (openCypher, #241). Modelled as a leaf with
* op="HAS_LABEL" and value=Label, evaluated against the bound node's label. */
if (check(p, TOK_COLON)) {
advance(p);
const cbm_token_t *lbl = expect(p, TOK_IDENT);
if (!lbl) {
return CBM_NOT_FOUND;
}
c->variable = heap_strdup(var->text);
c->op = heap_strdup("HAS_LABEL");
c->value = heap_strdup(lbl->text);
return COND_LHS_COMPLETE;
}
if (match(p, TOK_DOT)) {
const cbm_token_t *prop = expect(p, TOK_IDENT);
if (!prop) {
return CBM_NOT_FOUND;
}
c->variable = heap_strdup(var->text);
c->property = heap_strdup(prop->text);
} else {
/* No dot: bare alias (e.g. post-WITH variable like "cnt") */
c->variable = heap_strdup(var->text);
c->property = NULL;
}
return 0;
}
static cbm_expr_t *parse_condition_expr(parser_t *p) {
/* Check for NOT prefix at condition level (e.g. NOT n.name CONTAINS "x") */
bool negated = match(p, TOK_NOT);
/* EXISTS { pattern } predicate (anchored single-hop existence). */
if (check(p, TOK_EXISTS)) {
return parse_exists_predicate(p, negated);
}
cbm_condition_t c = {0};
c.negated = negated;
int lhs_rc = parse_condition_lhs(p, &c);
if (lhs_rc < 0) {
return NULL;
}
if (lhs_rc > 0) {
/* HAS_LABEL leaf — complete condition, no operator follows */
return expr_leaf(c);
}
return parse_condition_op(p, &c);
}
/* Atom: ( expr ) | condition */
static cbm_expr_t *parse_atom_expr(parser_t *p) { // NOLINT(misc-no-recursion)
if (match(p, TOK_LPAREN)) {
if (!parse_depth_enter(p)) {
return NULL;
}
cbm_expr_t *e = parse_or_expr(p);
parse_depth_leave(p);
expect(p, TOK_RPAREN);
return e;
}
return parse_condition_expr(p);
}
/* NOT: NOT atom | atom */
static cbm_expr_t *parse_not_expr(parser_t *p) { // NOLINT(misc-no-recursion)
if (match(p, TOK_NOT)) {
if (!parse_depth_enter(p)) {
return NULL;
}
cbm_expr_t *child = parse_not_expr(p);
parse_depth_leave(p);
return child ? expr_not(child) : NULL;
}
return parse_atom_expr(p);
}
/* A chain `a OP b OP c ...` of one associative operator is linked along the
* RIGHT child: OP(a, OP(b, OP(c, ...))). The chain's length is bounded only by
* the message size, so a left-deep fold would hand every walker (evaluate,
* seed-selectivity, free) a tree as deep as the chain is long; linked this
* way each walker follows the chain in a loop and only recurses into the
* operands, whose nesting the parse-depth cap bounds. Operand order and the
* left-to-right short-circuit are the same as in the nested form. `next` is
* the operand just parsed; `more` says whether another OP follows it. */
static void expr_chain_link(cbm_expr_t **tail, cbm_expr_type_t type, cbm_expr_t *next, bool more) {
if (more) {
cbm_expr_t *node = expr_binary(type, next, NULL);
(*tail)->right = node;
*tail = node;
} else {
(*tail)->right = next;
}
}
/* AND: not (AND not)* */
static cbm_expr_t *parse_and_expr(parser_t *p) { // NOLINT(misc-no-recursion)
cbm_expr_t *first = parse_not_expr(p);
if (!first || !check(p, TOK_AND)) {
return first;
}
cbm_expr_t *head = expr_binary(EXPR_AND, first, NULL);
cbm_expr_t *tail = head;
while (match(p, TOK_AND)) {
cbm_expr_t *next = parse_not_expr(p);
if (!next) {
expr_free(head);
return NULL;
}
expr_chain_link(&tail, EXPR_AND, next, check(p, TOK_AND));
}
return head;
}
/* XOR: and (XOR and)* */
static cbm_expr_t *parse_xor_expr(parser_t *p) { // NOLINT(misc-no-recursion)
cbm_expr_t *first = parse_and_expr(p);
if (!first || !check(p, TOK_XOR)) {
return first;
}
cbm_expr_t *head = expr_binary(EXPR_XOR, first, NULL);
cbm_expr_t *tail = head;
while (match(p, TOK_XOR)) {
cbm_expr_t *next = parse_and_expr(p);
if (!next) {
expr_free(head);
return NULL;
}
expr_chain_link(&tail, EXPR_XOR, next, check(p, TOK_XOR));
}
return head;
}
/* OR: xor (OR xor)* */
static cbm_expr_t *parse_or_expr(parser_t *p) { // NOLINT(misc-no-recursion)
cbm_expr_t *first = parse_xor_expr(p);
if (!first || !check(p, TOK_OR)) {
return first;
}
cbm_expr_t *head = expr_binary(EXPR_OR, first, NULL);
cbm_expr_t *tail = head;
while (match(p, TOK_OR)) {
cbm_expr_t *next = parse_xor_expr(p);
if (!next) {
expr_free(head);
return NULL;
}
expr_chain_link(&tail, EXPR_OR, next, check(p, TOK_OR));
}
return head;
}
/* Parse WHERE clause — builds expression tree */
static int parse_where(parser_t *p, cbm_where_clause_t **out) {
if (!match(p, TOK_WHERE)) {
*out = NULL;
return 0;
}
cbm_where_clause_t *w = calloc(CBM_ALLOC_ONE, sizeof(cbm_where_clause_t));
w->root = parse_or_expr(p);
if (!w->root && p->error[0]) {
free(w);
return CBM_NOT_FOUND;
}
*out = w;
return 0;
}
/* Helper: is token an aggregate function? */
static bool is_aggregate_tok(cbm_token_type_t t) {
return (t == TOK_COUNT || t == TOK_SUM || t == TOK_AVG || t == TOK_MIN_KW || t == TOK_MAX_KW ||
t == TOK_COLLECT) != 0;
}
/* Helper: is token a string function? */
static bool is_string_func_tok(cbm_token_type_t t) {
return (t == TOK_TOLOWER || t == TOK_TOUPPER || t == TOK_TOSTRING) != 0;
}
/* Token type to function name */
static const char *agg_func_name(cbm_token_type_t t) {
switch (t) {
case TOK_COUNT:
return "COUNT";
case TOK_SUM:
return "SUM";
case TOK_AVG:
return "AVG";
case TOK_MIN_KW:
return "MIN";
case TOK_MAX_KW:
return "MAX";
case TOK_COLLECT:
return "COLLECT";
default:
return "COUNT";
}
}
static const char *str_func_name(cbm_token_type_t t) {
switch (t) {
case TOK_TOLOWER:
return "toLower";
case TOK_TOUPPER:
return "toUpper";
case TOK_TOSTRING:
return "toString";
default:
return "";
}
}
/* Parse a value literal: string, number, ident[.prop], true, false. Returns heap-allocated. */
static const char *parse_value_literal(parser_t *p) {
if (check(p, TOK_STRING) || check(p, TOK_NUMBER)) {
return heap_strdup(advance(p)->text);
}
if (check(p, TOK_IDENT)) {
char buf[CBM_SZ_256];
const cbm_token_t *v = advance(p);
if (match(p, TOK_DOT)) {
const cbm_token_t *pr = expect(p, TOK_IDENT);
snprintf(buf, sizeof(buf), "%s.%s", v->text, pr ? pr->text : "");
} else {
snprintf(buf, sizeof(buf), "%s", v->text);
}
return heap_strdup(buf);
}
if (check(p, TOK_TRUE)) {
advance(p);
return heap_strdup("true");
}
if (check(p, TOK_FALSE)) {
advance(p);
return heap_strdup("false");
}
return NULL;
}
/* Parse CASE WHEN ... THEN ... [ELSE ...] END */
static cbm_case_expr_t *parse_case_expr(parser_t *p) {
/* CASE already consumed */
cbm_case_expr_t *kase = calloc(CBM_ALLOC_ONE, sizeof(cbm_case_expr_t));
if (!kase) {
return NULL;
}
int bcap = CYP_INIT_CAP4;
kase->branches = malloc(bcap * sizeof(cbm_case_branch_t));
if (!kase->branches) {
free(kase);
return NULL;
}
while (check(p, TOK_WHEN)) {
advance(p);
cbm_expr_t *when = parse_or_expr(p);
if (!expect(p, TOK_THEN)) {
expr_free(when);
break;
}
const char *then_val = parse_value_literal(p);
if (kase->branch_count >= bcap) {
int new_bcap = bcap * PAIR_LEN;
void *tmp = realloc(kase->branches, new_bcap * sizeof(cbm_case_branch_t));
if (!tmp) {
expr_free(when);
safe_str_free(&then_val);
for (int i = 0; i < kase->branch_count; i++) {
expr_free(kase->branches[i].when_expr);
safe_str_free(&kase->branches[i].then_val);
}
free(kase->branches);
free(kase);
return NULL;
}
kase->branches = tmp;
bcap = new_bcap;
}
kase->branches[kase->branch_count++] =
(cbm_case_branch_t){.when_expr = when, .then_val = then_val};
}
if (match(p, TOK_ELSE)) {
kase->else_val = parse_value_literal(p);
}
expect(p, TOK_END);
return kase;
}
/* Parse a single RETURN/WITH item (aggregate, string func, CASE, or plain var.prop).
* Returns 0 on success, -1 on error. */
/* Parse var[.prop] into item->variable and item->property. Returns -1 on error. */
/* ASCII case-insensitive string equality. */
static bool cyp_ci_eq(const char *a, const char *b) {
if (!a || !b) {
return false;
}
for (; *a && *b; a++, b++) {
if (tolower((unsigned char)*a) != tolower((unsigned char)*b)) {
return false;
}
}
return *a == '\0' && *b == '\0';
}
/* Canonical name for a single-argument scalar / entity-introspection function
* invoked by identifier — labels/type/id/keys/properties and the numeric/bool
* casts toInteger/toFloat/toBoolean — or NULL if unrecognised (case-insensitive).
* toLower/toUpper/toString are separate keyword tokens handled elsewhere. */
static const char *scalar_func_canonical(const char *s) {
static const char *const names[] = {
"labels", "type", "id", "keys", "properties", "toInteger", "toFloat", "toBoolean",
"size", "length", "trim", "ltrim", "rtrim", "reverse", NULL};
for (int i = 0; names[i]; i++) {
if (cyp_ci_eq(s, names[i])) {
return names[i];
}
}
return NULL;
}
/* True for single-argument functions that transform a scalar string value
* (vs. entity-introspection funcs that act on the bound node/edge). */
static bool is_scalar_value_func(const char *f) {
return f && (strcmp(f, "toLower") == 0 || strcmp(f, "toUpper") == 0 ||
strcmp(f, "toString") == 0 || strcmp(f, "toInteger") == 0 ||
strcmp(f, "toFloat") == 0 || strcmp(f, "toBoolean") == 0 ||
strcmp(f, "size") == 0 || strcmp(f, "length") == 0 || strcmp(f, "trim") == 0 ||
strcmp(f, "ltrim") == 0 || strcmp(f, "rtrim") == 0 || strcmp(f, "reverse") == 0);
}
static int parse_var_dot_prop(parser_t *p, cbm_return_item_t *item) {
const cbm_token_t *var = expect(p, TOK_IDENT);
if (!var) {
return CBM_NOT_FOUND;
}
item->variable = heap_strdup(var->text);
if (match(p, TOK_DOT)) {
const cbm_token_t *prop = expect(p, TOK_IDENT);
if (prop) {
item->property = heap_strdup(prop->text);
}
}
return 0;
}
/* True if the cursor is at `IDENT(` where IDENT is a supported scalar function. */
static bool is_named_func_call(parser_t *p) {
if (!check(p, TOK_IDENT) || p->pos + SKIP_ONE >= p->count) {
return false;
}
if (p->tokens[p->pos + SKIP_ONE].type != TOK_LPAREN) {
return false;
}
return scalar_func_canonical(peek(p)->text) != NULL;
}
/* Parse a single-argument scalar / introspection call: labels(n), type(r),
* id(n), keys(n), properties(n), toInteger(n.start_line), ... */
static int parse_named_func_item(parser_t *p, cbm_return_item_t *item) {
const char *canon = scalar_func_canonical(peek(p)->text);
advance(p); /* consume the function name */
expect(p, TOK_LPAREN);
if (parse_var_dot_prop(p, item) < 0) {
return CBM_NOT_FOUND;
}
expect(p, TOK_RPAREN);
item->func = heap_strdup(canon);
return 0;
}
/* Canonical name for a multi-argument scalar function, or NULL. */
static const char *multiarg_func_canonical(const char *s) {
static const char *const names[] = {"coalesce", "substring", "replace", "left", "right", NULL};
for (int i = 0; names[i]; i++) {
if (cyp_ci_eq(s, names[i])) {
return names[i];
}
}
return NULL;
}
static bool is_multiarg_func_call(parser_t *p) {
if (!check(p, TOK_IDENT) || p->pos + SKIP_ONE >= p->count) {
return false;
}
if (p->tokens[p->pos + SKIP_ONE].type != TOK_LPAREN) {
return false;
}
return multiarg_func_canonical(peek(p)->text) != NULL;
}
/* Parse one function argument: a string/number literal or a var[.prop]. */
static int parse_func_arg(parser_t *p, cbm_func_arg_t *arg) {
memset(arg, 0, sizeof(*arg));
if (check(p, TOK_STRING) || check(p, TOK_NUMBER)) {
arg->literal = heap_strdup(peek(p)->text);
advance(p);
return 0;
}
const cbm_token_t *var = expect(p, TOK_IDENT);
if (!var) {
return CBM_NOT_FOUND;
}
arg->variable = heap_strdup(var->text);
if (match(p, TOK_DOT)) {
const cbm_token_t *prop = expect(p, TOK_IDENT);
if (prop) {
arg->property = heap_strdup(prop->text);
}
}
return 0;
}
/* Parse a multi-argument scalar call: coalesce(a, b, ...), substring(s, i[, n]),
* replace(s, from, to), left(s, n), right(s, n). */
static int parse_multiarg_func_item(parser_t *p, cbm_return_item_t *item) {
const char *canon = multiarg_func_canonical(peek(p)->text);
advance(p); /* function name */
expect(p, TOK_LPAREN);
int cap = CYP_INIT_CAP4;
item->args = malloc((size_t)cap * sizeof(cbm_func_arg_t));
item->arg_count = 0;
while (!check(p, TOK_RPAREN) && !check(p, TOK_EOF)) {
if (item->arg_count > 0 && !match(p, TOK_COMMA)) {
break;
}
if (item->arg_count >= cap) {
cap *= PAIR_LEN;
item->args = safe_realloc(item->args, (size_t)cap * sizeof(cbm_func_arg_t));
}
if (parse_func_arg(p, &item->args[item->arg_count]) < 0) {
return CBM_NOT_FOUND;
}
item->arg_count++;
}
expect(p, TOK_RPAREN);
item->func = heap_strdup(canon);
/* Surface the first variable arg as variable/property for column naming. */
if (item->arg_count > 0 && item->args[0].variable) {
item->variable = heap_strdup(item->args[0].variable);
if (item->args[0].property) {
item->property = heap_strdup(item->args[0].property);
}
}
return 0;
}
/* Parse aggregate function call: COUNT(var.prop) */
static int parse_aggregate_item(parser_t *p, cbm_return_item_t *item) {
cbm_token_type_t ft = peek(p)->type;
advance(p);
expect(p, TOK_LPAREN);
/* Optional DISTINCT inside the call: COUNT(DISTINCT x) (#239). */
item->distinct = match(p, TOK_DISTINCT);
if (match(p, TOK_STAR)) {
item->variable = heap_strdup("*");
} else {
if (parse_var_dot_prop(p, item) < 0) {
return CBM_NOT_FOUND;
}
}
expect(p, TOK_RPAREN);
item->func = heap_strdup(agg_func_name(ft));
return 0;
}
/* Parse string function call: toLower(var.prop) */
static int parse_string_func_item(parser_t *p, cbm_return_item_t *item) {
cbm_token_type_t ft = peek(p)->type;
advance(p);
expect(p, TOK_LPAREN);
if (parse_var_dot_prop(p, item) < 0) {
return CBM_NOT_FOUND;
}
expect(p, TOK_RPAREN);
item->func = heap_strdup(str_func_name(ft));
return 0;
}
static int parse_return_item(parser_t *p, cbm_return_item_t *item) {
memset(item, 0, sizeof(*item));
int rc = 0;
if (check(p, TOK_CASE)) {
advance(p);
item->kase = parse_case_expr(p);
item->variable = heap_strdup("CASE");
} else if (is_aggregate_tok(peek(p)->type)) {
rc = parse_aggregate_item(p, item);
} else if (is_string_func_tok(peek(p)->type)) {
rc = parse_string_func_item(p, item);
} else if (is_multiarg_func_call(p)) {
rc = parse_multiarg_func_item(p, item);
} else if (is_named_func_call(p)) {
rc = parse_named_func_item(p, item);
} else {
rc = parse_var_dot_prop(p, item);
}
if (rc < 0) {
return CBM_NOT_FOUND;
}
/* A bare identifier followed by '(' is a function we don't recognise
* (recognised aggregates / string funcs / scalar funcs are handled above),
* and '[' begins list indexing/slicing we don't support. Rather than
* silently projecting an empty column — which looks like a valid but blank
* result and hides the real problem — fail loudly with a clear message so
* the caller knows the query used an unsupported feature (#373). */
if (!item->func && !item->kase && (check(p, TOK_LPAREN) || check(p, TOK_LBRACKET))) {
if (check(p, TOK_LPAREN)) {
snprintf(p->error, sizeof(p->error),
"unsupported function '%s' (supported: count, sum, avg, min, max, collect, "
"toLower, toUpper, toString, toInteger, toFloat, toBoolean, size, length, "
"trim, ltrim, rtrim, reverse, labels, type, id, keys, properties)",
item->variable ? item->variable : "?");
} else {
snprintf(p->error, sizeof(p->error),
"unsupported expression: list indexing/slicing '[...]' is not supported");
}
safe_str_free(&item->variable);
safe_str_free(&item->property);
return CBM_NOT_FOUND;
}
/* Optional AS alias */
if (match(p, TOK_AS)) {
const cbm_token_t *alias = expect(p, TOK_IDENT);
if (alias) {
item->alias = heap_strdup(alias->text);
}
}
return 0;
}
/* Parse aggregate function call for ORDER BY */
static void parse_order_by_agg(parser_t *p, char *buf, size_t buf_sz) {
const char *fn = agg_func_name(peek(p)->type);
advance(p);
expect(p, TOK_LPAREN);
if (match(p, TOK_STAR)) {
snprintf(buf, buf_sz, "%s(*)", fn);
} else {
const cbm_token_t *var = expect(p, TOK_IDENT);
snprintf(buf, buf_sz, "%s(%s)", fn, var ? var->text : "");
}
expect(p, TOK_RPAREN);
}
/* Parse var[.prop] for ORDER BY */
static void parse_order_by_var(parser_t *p, char *buf, size_t buf_sz) {
const cbm_token_t *var = expect(p, TOK_IDENT);
if (!var) {
return;
}
snprintf(buf, buf_sz, "%s", var->text);
if (match(p, TOK_DOT)) {
const cbm_token_t *prop = expect(p, TOK_IDENT);
if (prop) {
snprintf(buf, buf_sz, "%s.%s", var->text, prop->text);
}
}
}
/* Parse ORDER BY expression into buf. Returns buf. */
static char *parse_order_by_expr(parser_t *p, char *buf, size_t buf_sz) {
buf[0] = '\0';
if (is_aggregate_tok(peek(p)->type)) {
parse_order_by_agg(p, buf, buf_sz);
} else {
parse_order_by_var(p, buf, buf_sz);
}
return buf;
}
/* Parse the full comma-separated ORDER BY key list (#1334). Consuming only the
* first key left ", key2 ... LIMIT n" unparsed, which silently dropped the
* LIMIT and flooded the caller with the whole result set. Returns 0 on
* success, CBM_NOT_FOUND when the key list exceeds the modeled maximum. */
static int parse_order_by_clause(parser_t *p, cbm_return_clause_t *r) {
expect(p, TOK_BY);
do {
if (r->order_key_count >= CBM_CYPHER_ORDER_KEYS_MAX) {
return CBM_NOT_FOUND;
}
char order_buf[CBM_SZ_256];
parse_order_by_expr(p, order_buf, sizeof(order_buf));
bool desc = false;
if (match(p, TOK_ASC)) {
desc = false;
} else if (match(p, TOK_DESC)) {
desc = true;
}
r->order_keys[r->order_key_count] = heap_strdup(order_buf);
r->order_descs[r->order_key_count] = desc;
r->order_key_count++;
} while (match(p, TOK_COMMA));
return 0;
}
static void free_return_clause(cbm_return_clause_t *r);
/* Parse RETURN/WITH clause (shared logic) */
static int parse_return_or_with(parser_t *p, cbm_return_clause_t **out, bool is_with) {
cbm_token_type_t tok = (int)is_with ? TOK_WITH : TOK_RETURN;
/* For WITH, we need to check it's standalone (not preceded by STARTS) */
if (!match(p, tok)) {
*out = NULL;
return 0;
}
cbm_return_clause_t *r = calloc(CBM_ALLOC_ONE, sizeof(cbm_return_clause_t));
/* -1 = no LIMIT clause (return all). An explicit `LIMIT 0` parses to 0 below
* and must return 0 rows — distinguishing the two requires a sentinel, since
* calloc zeroes limit and `limit > 0` would treat LIMIT 0 as "no limit". */
r->limit = -1;
int cap = CYP_INIT_CAP8;
r->items = malloc(cap * sizeof(cbm_return_item_t));
r->distinct = match(p, TOK_DISTINCT);
/* Check for RETURN * */
if (!is_with && match(p, TOK_STAR)) {
r->star = true;
/* Skip to ORDER BY / SKIP / LIMIT */
goto tail;
}
do {
if (r->count > 0 && !match(p, TOK_COMMA)) {
break;
}
cbm_return_item_t item = {0};
if (parse_return_item(p, &item) < 0) {
free_return_clause(r);
return CBM_NOT_FOUND;
}
if (r->count >= cap) {
cap *= PAIR_LEN;
r->items = safe_realloc(r->items, cap * sizeof(cbm_return_item_t));
}
r->items[r->count++] = item;
} while (check(p, TOK_COMMA));
/* Projection is materialized per row into fixed-width stack arrays sized at
* CBM_SZ_32 columns (ret_sink_feed_rows and its siblings). Bound the
* parsed item count to that width so an over-wide RETURN is rejected here
* instead of writing past those arrays downstream.
*
* WITH is bounded tighter, by CYP_MAX_VARS. Every item a WITH projects
* becomes one variable of the binding that carries the rest of the query,
* and binding_t holds exactly CYP_MAX_VARS variables. A wider WITH used to
* parse, then lose every alias past the 16th in with_add_vbinding_var and
* answer with silently blank columns. Refuse it here, the same way an
* over-wide RETURN is refused, so the caller sees an error instead of a
* short or empty result. */
if (r->count > (is_with ? CYP_MAX_VARS : CBM_SZ_32)) {
free_return_clause(r);
return CBM_NOT_FOUND;
}
tail:
/* Optional ORDER BY */
if (match(p, TOK_ORDER)) {
if (parse_order_by_clause(p, r) < 0) {
free_return_clause(r);
return CBM_NOT_FOUND;
}
}
/* Optional SKIP. A non-numeric operand is a loud parse error: expect() has
* already filled p->error, and dropping the clause instead would leave
* r->skip at its "none" default while the query still reports success. */
if (match(p, TOK_SKIP)) {
const cbm_token_t *num = expect(p, TOK_NUMBER);
if (!num) {
free_return_clause(r);
return CBM_NOT_FOUND;
}
r->skip = (int)strtol(num->text, NULL, CBM_DECIMAL_BASE);
}
/* Optional LIMIT. Same rule: a dropped LIMIT is the failure mode #1334
* banned - the caller would silently receive the whole result set. */
if (match(p, TOK_LIMIT)) {
const cbm_token_t *num = expect(p, TOK_NUMBER);
if (!num) {
free_return_clause(r);
return CBM_NOT_FOUND;
}
r->limit = (int)strtol(num->text, NULL, CBM_DECIMAL_BASE);
}
*out = r;
return 0;
}
/* Parse RETURN clause */
static int parse_return(parser_t *p, cbm_return_clause_t **out) {
return parse_return_or_with(p, out, false);
}
static void free_pattern(cbm_pattern_t *pat);
/* Parse a single MATCH pattern into pat. On failure pat is freed and zeroed:
* the caller counts a pattern only after it parsed, so a partial one would
* otherwise leak (a named path "p = (...)" failed this way on every query). */
static int parse_match_pattern(parser_t *p, cbm_pattern_t *pat) {
memset(pat, 0, sizeof(*pat));
int node_cap = CYP_INIT_CAP4;
int rel_cap = CYP_INIT_CAP4;
pat->nodes = malloc(node_cap * sizeof(cbm_node_pattern_t));
pat->rels = calloc(rel_cap, sizeof(cbm_rel_pattern_t));
/* A failed parse_node / parse_rel leaves its element zeroed except for
* what it allocated, so counting that element frees its partial state. */
if (parse_node(p, &pat->nodes[0]) < 0) {
pat->node_count = SKIP_ONE;
goto fail;
}
pat->node_count = SKIP_ONE;
while (check(p, TOK_DASH) || check(p, TOK_LT)) {
if (pat->rel_count >= rel_cap) {
rel_cap *= PAIR_LEN;
pat->rels = safe_realloc(pat->rels, rel_cap * sizeof(cbm_rel_pattern_t));
}
if (parse_rel(p, &pat->rels[pat->rel_count]) < 0) {
pat->rel_count++;
goto fail;
}
pat->rel_count++;
if (pat->node_count >= node_cap) {
node_cap *= PAIR_LEN;
pat->nodes = safe_realloc(pat->nodes, node_cap * sizeof(cbm_node_pattern_t));
}
if (parse_node(p, &pat->nodes[pat->node_count]) < 0) {
pat->node_count++;
goto fail;
}
pat->node_count++;
}
return 0;
fail:
free_pattern(pat);
memset(pat, 0, sizeof(*pat));
return CBM_NOT_FOUND;
}
/* Parse UNWIND [...] AS var clause into query */
static void parse_unwind_clause(parser_t *p, cbm_query_t *q) {
advance(p);
if (check(p, TOK_LBRACKET)) {
/* Literal list: [1, 2, 3] — collect as JSON array string */
advance(p);
char buf[CBM_SZ_2K] = "[";
int blen = SKIP_ONE;
/* snprintf returns the length it WOULD have written, so a single
* oversized token (string literals lex up to CBM_SZ_4K-1) can push
* blen past sizeof(buf). Clamp after every write and guard the raw
* buf[blen++] stores, mirroring format_collect_list(). */
const int cap = (int)sizeof(buf);
while (!check(p, TOK_RBRACKET) && !check(p, TOK_EOF)) {
if (blen > SKIP_ONE && blen < cap - SKIP_ONE) {
buf[blen++] = ',';
}
if (check(p, TOK_STRING)) {
blen += snprintf(buf + blen, (size_t)(cap - blen), "\"%s\"", peek(p)->text);
advance(p);
} else if (check(p, TOK_NUMBER)) {
blen += snprintf(buf + blen, (size_t)(cap - blen), "%s", peek(p)->text);
advance(p);
} else {
advance(p);
}
if (blen >= cap) {
blen = cap - SKIP_ONE;
}
match(p, TOK_COMMA);
}
expect(p, TOK_RBRACKET);
if (blen < cap - SKIP_ONE) {
buf[blen++] = ']';
}
buf[blen] = '\0';
q->unwind_expr = heap_strdup(buf);
} else if (check(p, TOK_IDENT)) {
q->unwind_expr = heap_strdup(advance(p)->text);
}
expect(p, TOK_AS);
const cbm_token_t *alias = expect(p, TOK_IDENT);
if (alias) {
q->unwind_alias = heap_strdup(alias->text);
}
}
/* Parse a chain of MATCH / OPTIONAL MATCH patterns into query.
* Returns -1 on error (fills p->error). */
static int parse_match_chain(parser_t *p, cbm_query_t *q, int *pat_cap) {
while (check(p, TOK_MATCH) || check(p, TOK_OPTIONAL)) {
bool opt = false;
if (check(p, TOK_OPTIONAL)) {
advance(p);
opt = true;
}
if (!expect(p, TOK_MATCH)) {
break;
}
if (q->pattern_count >= *pat_cap) {
*pat_cap *= PAIR_LEN;
q->patterns = safe_realloc(q->patterns, *pat_cap * sizeof(cbm_pattern_t));
q->pattern_optional = safe_realloc(q->pattern_optional, *pat_cap * sizeof(bool));
}
if (parse_match_pattern(p, &q->patterns[q->pattern_count]) < 0) {
return CBM_NOT_FOUND;
}
q->pattern_optional[q->pattern_count] = opt;
q->pattern_count++;
}
return 0;
}
/* Parse post-WHERE clauses: additional MATCH, WITH, RETURN. A UNION keyword
* is left for cbm_parse, which reads the branches in a loop. */
static int parse_post_where(parser_t *p, cbm_query_t *q, int *pat_cap) {
/* More MATCH / OPTIONAL MATCH after WHERE */
if (parse_match_chain(p, q, pat_cap) < 0) {
return CBM_NOT_FOUND;
}
/* Check for unsupported keywords */
const char *unsup = unsupported_clause_error(peek(p)->type);
if (unsup) {
snprintf(p->error, sizeof(p->error), "%s", unsup);
return CBM_NOT_FOUND;
}
/* Optional WITH clause (standalone, not STARTS WITH) */
if (check(p, TOK_WITH) &&
(p->pos < PAIR_LEN || p->tokens[p->pos - SKIP_ONE].type != TOK_STARTS)) {
if (parse_return_or_with(p, &q->with_clause, true) < 0) {
return CBM_NOT_FOUND;
}
if (parse_where(p, &q->post_with_where) < 0) {
return CBM_NOT_FOUND;
}
}
/* Optional RETURN */
if (parse_return(p, &q->ret) < 0) {
return CBM_NOT_FOUND;
}
return 0;
}
/* A stage that failed without writing a message gets the stage's own. */
static void parse_error_default(parser_t *p, const char *msg) {
if (!p->error[0]) {
snprintf(p->error, sizeof(p->error), "%s", msg);
}
}
/* One MATCH ... RETURN block: the whole query, or one branch of a UNION. On
* failure p->error holds the message and *out stays NULL. */
static int parse_query_block(parser_t *p, cbm_query_t **out) {
*out = NULL;
/* Each block starts with a clean message, as it did when every UNION
* branch had a parser of its own. */
p->error[0] = '\0';
/* Check for unsupported leading keywords */
const char *unsup = unsupported_clause_error(peek(p)->type);
if (unsup) {
snprintf(p->error, sizeof(p->error), "%s", unsup);
return CBM_NOT_FOUND;
}
cbm_query_t *q = calloc(CBM_ALLOC_ONE, sizeof(cbm_query_t));
if (check(p, TOK_UNWIND)) {
parse_unwind_clause(p, q);
}
bool first_optional = false;
if (check(p, TOK_OPTIONAL)) {
advance(p);
first_optional = true;
}
if (!expect(p, TOK_MATCH)) {
parse_error_default(p, "expected MATCH");
cbm_query_free(q);
return CBM_NOT_FOUND;
}
int pat_cap = CYP_INIT_CAP4;
q->patterns = malloc(pat_cap * sizeof(cbm_pattern_t));
q->pattern_optional = malloc(pat_cap * sizeof(bool));
if (parse_match_pattern(p, &q->patterns[0]) < 0) {
parse_error_default(p, "failed to parse pattern");
cbm_query_free(q);
return CBM_NOT_FOUND;
}
q->pattern_optional[0] = first_optional;
q->pattern_count = SKIP_ONE;
if (parse_match_chain(p, q, &pat_cap) < 0) {
parse_error_default(p, "failed to parse additional pattern");
cbm_query_free(q);
return CBM_NOT_FOUND;
}
if (parse_where(p, &q->where) < 0) {
parse_error_default(p, "failed to parse WHERE");
cbm_query_free(q);
return CBM_NOT_FOUND;
}
if (parse_post_where(p, q, &pat_cap) < 0) {
parse_error_default(p, "failed to parse query");
cbm_query_free(q);
return CBM_NOT_FOUND;
}
*out = q;
return 0;
}
int cbm_parse(const cbm_token_t *tokens, int token_count, cbm_parse_result_t *out) {
memset(out, 0, sizeof(*out));
parser_t p = {.tokens = tokens, .count = token_count, .pos = 0};
/* The branches of a UNION are read one after another by this one parser
* and linked as they come, so the number of branches is a loop count, not
* a recursion depth, and one depth counter covers the whole query. */
cbm_query_t *q = NULL;
cbm_query_t *tail = NULL;
for (;;) {
cbm_query_t *block = NULL;
if (parse_query_block(&p, &block) < 0) {
out->error = heap_strdup(p.error);
cbm_query_free(q);
return CBM_NOT_FOUND;
}
if (tail) {
tail->union_next = block;
} else {
q = block;
}
tail = block;
/* UNION [ALL]: the ALL flag sits on the branch before the keyword. */
if (!check(&p, TOK_UNION)) {
break;
}
advance(&p);
tail->union_all = match(&p, TOK_ALL);
}
/* Every token must be consumed. The grammar accepts at most one WITH and
* treats RETURN as optional, so a query with a second WITH stage — or any
* typo after RETURN — used to stop parsing there and succeed anyway. The
* dropped tail took the filter and the RETURN with it, and the engine
* answered from the fragment it had parsed, using its default projection.
* That reported success and returned wrong rows, which is worse than a
* refusal because nothing tells the caller to look. Refuse instead. */
if (peek(&p)->type != TOK_EOF) {
/* Only mention the one-WITH limit when a standalone WITH really is
* sitting in the part we could not read. Saying it every time points
* a reader at WITH when the problem is a typo. A WITH straight after
* STARTS is the STARTS WITH operator rather than a clause, the same
* guard parse_post_where uses. */
const char *hint = "";
for (int i = p.pos; i < p.count; i++) {
if (p.tokens[i].type == TOK_WITH &&
(i == 0 || p.tokens[i - SKIP_ONE].type != TOK_STARTS)) {
hint = " Note that only one WITH clause is supported.";
break;
}
}
snprintf(p.error, sizeof(p.error),
"unexpected input at pos %d ('%s') — the query was not fully "
"parsed.%s",
peek(&p)->pos, peek(&p)->text ? peek(&p)->text : "", hint);
out->error = heap_strdup(p.error);
cbm_query_free(q);
return CBM_NOT_FOUND;
}
out->query = q;
return 0;
}
void cbm_parse_free(cbm_parse_result_t *r) {
if (!r) {
return;
}
cbm_query_free(r->query);
free(r->error);
memset(r, 0, sizeof(*r));
}
/* ── Query free ─────────────────────────────────────────────────── */
static void free_pattern(cbm_pattern_t *pat) {
for (int i = 0; i < pat->node_count; i++) {
cbm_node_pattern_t *n = &pat->nodes[i];
safe_str_free(&n->variable);
safe_str_free(&n->label);
for (int j = 0; j < n->prop_count; j++) {
safe_str_free(&n->props[j].key);
safe_str_free(&n->props[j].value);
}
free(n->props);
}
free(pat->nodes);
for (int i = 0; i < pat->rel_count; i++) {
cbm_rel_pattern_t *r = &pat->rels[i];
safe_str_free(&r->variable);
for (int j = 0; j < r->type_count; j++) {
safe_str_free(&r->types[j]);
}
free(r->types);
safe_str_free(&r->direction);
}
free(pat->rels);
}
static void free_where(cbm_where_clause_t *w) {
if (!w) {
return;
}
expr_free(w->root);
for (int i = 0; i < w->count; i++) {
safe_str_free(&w->conditions[i].variable);
safe_str_free(&w->conditions[i].property);
safe_str_free(&w->conditions[i].op);
safe_str_free(&w->conditions[i].value);
for (int j = 0; j < w->conditions[i].in_value_count; j++) {
safe_str_free(&w->conditions[i].in_values[j]);
}
free(w->conditions[i].in_values);
safe_str_free(&w->conditions[i].func);
func_args_free(w->conditions[i].args, w->conditions[i].arg_count);
safe_str_free(&w->conditions[i].rhs_variable);
safe_str_free(&w->conditions[i].rhs_property);
}
free(w->conditions);
safe_str_free(&w->op);
free(w);
}
static void free_case_expr(cbm_case_expr_t *k) {
if (!k) {
return;
}
for (int i = 0; i < k->branch_count; i++) {
expr_free(k->branches[i].when_expr);
safe_str_free(&k->branches[i].then_val);
}
free(k->branches);
safe_str_free(&k->else_val);
free(k);
}
static void free_return_clause(cbm_return_clause_t *r) {
if (!r) {
return;
}
for (int i = 0; i < r->count; i++) {
safe_str_free(&r->items[i].variable);
safe_str_free(&r->items[i].property);
safe_str_free(&r->items[i].alias);
safe_str_free(&r->items[i].func);
free_case_expr(r->items[i].kase);
for (int j = 0; j < r->items[i].arg_count; j++) {
safe_str_free(&r->items[i].args[j].variable);
safe_str_free(&r->items[i].args[j].property);
safe_str_free(&r->items[i].args[j].literal);
}
free(r->items[i].args);
}
free(r->items);
for (int k = 0; k < r->order_key_count; k++) {
safe_str_free(&r->order_keys[k]);
}
free(r);
}
void cbm_query_free(cbm_query_t *q) {
while (q) {
cbm_query_t *next = q->union_next;
for (int i = 0; i < q->pattern_count; i++) {
free_pattern(&q->patterns[i]);
}
free(q->patterns);
free(q->pattern_optional);
free_where(q->where);
free_where(q->post_with_where);
free_return_clause(q->with_clause);
free_return_clause(q->ret);
safe_str_free(&q->unwind_expr);
safe_str_free(&q->unwind_alias);
free(q);
q = next;
}
}
/* ── Convenience: lex + parse ───────────────────────────────────── */
int cbm_cypher_parse(const char *query, cbm_query_t **out, char **error) {
*out = NULL;
*error = NULL;
cbm_lex_result_t lr = {0};
if (cbm_lex(query, &lr) < 0 || lr.error) {
*error = heap_strdup(lr.error ? lr.error : "lex error");
cbm_lex_free(&lr);
return CBM_NOT_FOUND;
}
cbm_parse_result_t pr = {0};
if (cbm_parse(lr.tokens, lr.count, &pr) < 0) {
*error = heap_strdup(pr.error ? pr.error : "parse error");
cbm_parse_free(&pr);
cbm_lex_free(&lr);
return CBM_NOT_FOUND;
}
*out = pr.query;
pr.query = NULL;
cbm_parse_free(&pr);
cbm_lex_free(&lr);
return 0;
}
/* ══════════════════════════════════════════════════════════════════
* EXECUTOR
* ══════════════════════════════════════════════════════════════════ */
/* A binding: maps variable names to nodes and/or edges */
typedef struct {
const char *var_names[CYP_MAX_VARS]; /* variable names (nodes) */
cbm_node_t var_nodes[CYP_MAX_VARS]; /* node data */
int var_count;
const char *edge_var_names[CYP_MAX_EDGE_VARS]; /* variable names (edges) */
cbm_edge_t edge_vars[CYP_MAX_EDGE_VARS]; /* edge data */
int edge_var_count;
cbm_store_t *store; /* for computing in_degree/out_degree on demand */
} binding_t;
/* Return a string field from a node by property name. NULL-safe. */
static const char *node_string_field(const cbm_node_t *n, const char *prop) {
static const struct {
const char *key;
size_t offset;
} fields[] = {
{"name", offsetof(cbm_node_t, name)},
{"qualified_name", offsetof(cbm_node_t, qualified_name)},
/* Aliases: field-eval agents reach for the short names, and a miss
* used to return a silent empty column costing a round-trip. */
{"qn", offsetof(cbm_node_t, qualified_name)},
{"label", offsetof(cbm_node_t, label)},
{"file_path", offsetof(cbm_node_t, file_path)},
{"file", offsetof(cbm_node_t, file_path)},
{"path", offsetof(cbm_node_t, file_path)},
};
for (size_t i = 0; i < sizeof(fields) / sizeof(fields[0]); i++) {
if (strcmp(prop, fields[i].key) == 0) {
const char *val = *(const char **)((const char *)n + fields[i].offset);
return val ? val : "";
}
}
return NULL;
}
/* Get node property by name.
* store may be NULL; only needed for virtual degree properties. */
static const char *json_extract_prop(const char *json, const char *key, char *buf, size_t buf_sz);
static const char *node_prop(const cbm_node_t *n, const char *prop, cbm_store_t *store) {
if (!n || !prop) {
return "";
}
const char *str = node_string_field(n, prop);
if (str && str[0]) {
return str;
}
/* Computed and JSON-derived values live in rotating thread-local buffers:
* a single row (or an ORDER-BY comparison) reads several of these before any
* of them is copied out, so returning one shared static buffer would alias
* every column to the last value read. Mirrors edge_prop's rotation. */
static _Thread_local char bufs[CYP_BUF_8][CBM_SZ_512];
static _Thread_local int buf_idx = 0;
char *out = bufs[buf_idx];
buf_idx = (buf_idx + SKIP_ONE) % CYP_BUF_8;
if (strcmp(prop, "start_line") == 0) {
snprintf(out, CBM_SZ_512, "%d", n->start_line);
return out;
}
if (strcmp(prop, "end_line") == 0) {
snprintf(out, CBM_SZ_512, "%d", n->end_line);
return out;
}
/* Virtual computed properties: in_degree/out_degree via CALLS edges.
* Enables Cypher dead-code detection: WHERE n.in_degree = '0'. */
if (store && (strcmp(prop, "in_degree") == 0 || strcmp(prop, "out_degree") == 0)) {
int in_deg = 0;
int out_deg = 0;
cbm_store_node_degree(store, n->id, &in_deg, &out_deg);
int val = (strcmp(prop, "in_degree") == 0) ? in_deg : out_deg;
snprintf(out, CBM_SZ_512, "%d", val);
return out;
}
/* Fall back to any value stored in the node's properties JSON — exposes the
* extraction metrics (complexity, cognitive, loop_count, loop_depth,
* transitive_loop_depth, recursive) and any other persisted property to
* WHERE/RETURN, e.g. WHERE n.loop_depth >= 2. */
if (n->properties_json && n->properties_json[0] == '{') {
const char *v = json_extract_prop(n->properties_json, prop, out, CBM_SZ_512);
if (v && v[0]) {
return v;
}
}
return "";
}
/* Extract a string value from JSON properties_json by key.
* Writes result to buf (up to buf_sz). Returns buf if found, "" otherwise.
* Handles both string values ("key":"value") and numeric values ("key":1.5). */
static const char *json_extract_prop(const char *json, const char *key, char *buf, size_t buf_sz) {
if (!json || !key) {
buf[0] = '\0';
return buf;
}
/* Build search pattern: "key": */
char pattern[CBM_SZ_256];
snprintf(pattern, sizeof(pattern), "\"%s\":", key);
const char *p = strstr(json, pattern);
if (!p) {
buf[0] = '\0';
return buf;
}
p += strlen(pattern);
/* Skip whitespace */
while (*p == ' ' || *p == '\t') {
p++;
}
if (*p == '"') {
/* String value — honor backslash escapes: without this, an embedded \"
* cuts the value short at the first escaped quote. */
p++;
size_t i = 0;
while (*p && *p != '"' && i < buf_sz - SKIP_ONE) {
if (*p == '\\' && p[SKIP_ONE] && i + SKIP_ONE < buf_sz - SKIP_ONE) {
buf[i++] = *p++; /* keep the escape pair intact */
}
buf[i++] = *p++;
}
buf[i] = '\0';
} else if (*p == '[' || *p == '{') {
/* Array/object value — copy the whole balanced construct. A scan-to-comma
* truncates at the first comma INSIDE the value: e.g. a decorators array
* ["@Roles('OWNER', 'ADMIN')","@Get()"] came back as ["@Roles('OWNER'. */
char open = *p;
char close = (open == '[') ? ']' : '}';
int depth = 0;
int in_str = 0;
size_t i = 0;
while (*p && i < buf_sz - SKIP_ONE) {
char c = *p;
if (in_str) {
if (c == '\\' && p[SKIP_ONE] && i + SKIP_ONE < buf_sz - SKIP_ONE) {
buf[i++] = *p++; /* escape pair stays intact */
} else if (c == '"') {
in_str = 0;
}
} else if (c == '"') {
in_str = 1;
} else if (c == open) {
depth++;
} else if (c == close) {
depth--;
}
buf[i++] = *p++;
if (!in_str && depth == 0) {
break; /* outer bracket closed */
}
}
buf[i] = '\0';
} else {
/* Numeric or other scalar value */
size_t i = 0;
while (*p && *p != ',' && *p != '}' && *p != ' ' && i < buf_sz - SKIP_ONE) {
buf[i++] = *p++;
}
buf[i] = '\0';
}
return buf;
}
/* Get edge property by name. Uses rotating thread-local buffers to allow
* multiple concurrent calls (e.g. projecting r.url_path, r.confidence
* in the same row). */
static const char *edge_prop(const cbm_edge_t *e, const char *prop) {
if (!e || !prop) {
return "";
}
if (strcmp(prop, "type") == 0) {
return e->type ? e->type : "";
}
/* Rotate through 8 thread-local buffers so multiple props can be accessed per row. */
static CBM_TLS char ebufs[CYP_BUF_8][CBM_SZ_512];
static CBM_TLS int ebuf_idx = 0;
char *buf = ebufs[ebuf_idx++ & CYP_EBUF_MASK];
json_extract_prop(e->properties_json, prop, buf, CBM_SZ_512);
return buf;
}
/* Find an edge variable in a binding */
static cbm_edge_t *binding_get_edge(binding_t *b, const char *var) {
for (int i = 0; i < b->edge_var_count; i++) {
if (strcmp(b->edge_var_names[i], var) == 0) {
return &b->edge_vars[i];
}
}
return NULL;
}
/* Find a variable's node in a binding */
static cbm_node_t *binding_get(binding_t *b, const char *var) {
for (int i = 0; i < b->var_count; i++) {
if (strcmp(b->var_names[i], var) == 0) {
return &b->var_nodes[i];
}
}
return NULL;
}
/* Deep copy a node: heap-dup all string fields so the binding owns them */
static void node_deep_copy(cbm_node_t *dst, const cbm_node_t *src) {
*dst = *src;
dst->project = heap_strdup(src->project);
dst->label = heap_strdup(src->label);
dst->name = heap_strdup(src->name);
dst->qualified_name = heap_strdup(src->qualified_name);
dst->file_path = heap_strdup(src->file_path);
dst->properties_json = heap_strdup(src->properties_json);
}
static void node_fields_free(cbm_node_t *n) {
if (!n) {
return;
}
safe_str_free(&n->project);
safe_str_free(&n->label);
safe_str_free(&n->name);
safe_str_free(&n->qualified_name);
safe_str_free(&n->file_path);
safe_str_free(&n->properties_json);
}
/* Deep copy an edge (binding owns the strings) */
static void edge_deep_copy(cbm_edge_t *dst, const cbm_edge_t *src) {
*dst = *src;
dst->project = heap_strdup(src->project);
dst->type = heap_strdup(src->type);
dst->properties_json = heap_strdup(src->properties_json);
}
static void edge_fields_free(cbm_edge_t *e) {
safe_str_free(&e->project);
safe_str_free(&e->type);
safe_str_free(&e->properties_json);
}
/* Set an edge variable in a binding */
static void binding_set_edge(binding_t *b, const char *var, const cbm_edge_t *edge) {
/* Check existing — free old fields first */
for (int i = 0; i < b->edge_var_count; i++) {
if (strcmp(b->edge_var_names[i], var) == 0) {
edge_fields_free(&b->edge_vars[i]);
edge_deep_copy(&b->edge_vars[i], edge);
return;
}
}
if (b->edge_var_count >= CYP_MAX_EDGE_VARS) {
return;
}
b->edge_var_names[b->edge_var_count] = var; /* not owned — points to AST string */
edge_deep_copy(&b->edge_vars[b->edge_var_count], edge);
b->edge_var_count++;
}
/* Free all deep-copied nodes and edges in a binding */
static void binding_free(binding_t *b) {
for (int i = 0; i < b->var_count; i++) {
node_fields_free(&b->var_nodes[i]);
}
for (int i = 0; i < b->edge_var_count; i++) {
edge_fields_free(&b->edge_vars[i]);
}
}
/* Deep-copy a binding (so source and dest own separate string copies) */
static void binding_copy(binding_t *dst, const binding_t *src) {
dst->var_count = src->var_count;
for (int i = 0; i < src->var_count; i++) {
dst->var_names[i] = src->var_names[i]; /* AST-owned, not freed */
node_deep_copy(&dst->var_nodes[i], &src->var_nodes[i]);
}
dst->edge_var_count = src->edge_var_count;
for (int i = 0; i < src->edge_var_count; i++) {
dst->edge_var_names[i] = src->edge_var_names[i]; /* AST-owned */
edge_deep_copy(&dst->edge_vars[i], &src->edge_vars[i]);
}
dst->store = src->store;
}
/* Deep-copy a node into a binding (binding owns the strings) */
static void binding_set(binding_t *b, const char *var, const cbm_node_t *node) {
/* Check existing — free old fields first */
for (int i = 0; i < b->var_count; i++) {
if (strcmp(b->var_names[i], var) == 0) {
node_fields_free(&b->var_nodes[i]);
node_deep_copy(&b->var_nodes[i], node);
return;
}
}
if (b->var_count >= CYP_MAX_VARS) {
return;
}
b->var_names[b->var_count] = var; /* not owned — points to AST string */
node_deep_copy(&b->var_nodes[b->var_count], node);
b->var_count++;
}
/* binding_set for a node the caller owns and is done with: the binding takes
* its strings instead of copying them, and *node is left empty, so the
* caller's node_fields_free of it is a no-op. A binding with no free slot
* takes nothing, as binding_set stores nothing. */
static void binding_take_node(binding_t *b, const char *var, cbm_node_t *node) {
for (int i = 0; i < b->var_count; i++) {
if (strcmp(b->var_names[i], var) == 0) {
node_fields_free(&b->var_nodes[i]);
b->var_nodes[i] = *node;
memset(node, 0, sizeof(*node));
return;
}
}
if (b->var_count >= CYP_MAX_VARS) {
return;
}
b->var_names[b->var_count] = var; /* not owned — points to AST string */
b->var_nodes[b->var_count] = *node;
memset(node, 0, sizeof(*node));
b->var_count++;
}
static const char *eval_multiarg_func(binding_t *b, const cbm_return_item_t *item, char *buf,
size_t bufsz);
/* Resolve the actual property value for a condition from a binding */
static const char *resolve_condition_value(const cbm_condition_t *c, binding_t *b) {
/* Multi-arg scalar function LHS: coalesce(f.depth, 0) >= 2 (#874).
* Evaluated through the same code path as RETURN projections. The value is
* consumed by eval_condition before any other condition is resolved, so a
* single thread-local buffer per call is safe. */
if (c->func) {
static _Thread_local char func_buf[CBM_SZ_512];
cbm_return_item_t item = {0};
item.variable = c->variable;
item.property = c->property;
item.func = c->func;
item.args = c->args;
item.arg_count = c->arg_count;
return eval_multiarg_func(b, &item, func_buf, sizeof(func_buf));
}
cbm_edge_t *e = binding_get_edge(b, c->variable);
if (e) {
return edge_prop(e, c->property);
}
cbm_node_t *n = binding_get(b, c->variable);
if (!n) {
return NULL; /* unbound variable */
}
if (c->property) {
return node_prop(n, c->property, b->store);
}
/* Bare alias (e.g. post-WITH virtual var) — use node name directly */
return n->name ? n->name : "";
}
/* Set when an `=~` or inline-property pattern was refused by the regex
* wrapper's compile-size guard during the CURRENT execution; cbm_cypher_execute
* turns it into result->warning so an empty result can be told from "no such
* name". Reset at the start of every execution. */
static _Thread_local bool g_cypher_regex_refused = false;
/* Evaluate a comparison operator between actual and expected strings. */
static bool eval_comparison_op(const char *op, const char *actual, const char *expected) {
if (strcmp(op, "=") == 0) {
return strcmp(actual, expected) == 0;
}
if (strcmp(op, "<>") == 0) {
return strcmp(actual, expected) != 0;
}
if (strcmp(op, "=~") == 0) {
cbm_regex_t re;
int comp_rc = cbm_regcomp(&re, expected, CBM_REG_EXTENDED | CBM_REG_NOSUB);
if (comp_rc != 0) {
if (comp_rc == CBM_REG_ETOOBIG) {
g_cypher_regex_refused = true;
}
return false;
}
int rc = cbm_regexec(&re, actual, 0, NULL, 0);
cbm_regfree(&re);
return rc == 0;
}
if (strcmp(op, "CONTAINS") == 0) {
return strstr(actual, expected) != NULL;
}
if (strcmp(op, "STARTS WITH") == 0) {
return strncmp(actual, expected, strlen(expected)) == 0;
}
if (strcmp(op, "ENDS WITH") == 0) {
size_t alen = strlen(actual);
size_t elen = strlen(expected);
return alen >= elen && strcmp(actual + alen - elen, expected) == 0;
}
if (strcmp(op, ">") == 0 || strcmp(op, "<") == 0 || strcmp(op, ">=") == 0 ||
strcmp(op, "<=") == 0) {
double a = strtod(actual, NULL);
double exp_val = strtod(expected, NULL);
if (op[0] == '>' && op[CYP_CHAR_IDX1] == '=') {
return a >= exp_val;
}
if (op[0] == '<' && op[CYP_CHAR_IDX1] == '=') {
return a <= exp_val;
}
if (op[0] == '>') {
return a > exp_val;
}
return a < exp_val;
}
return false;
}
enum { EXISTS_DIR_OUT = 0, EXISTS_DIR_IN = 1 };
/* EXISTS { (var)-[:TYPE]->() }: does the bound node have any edge of the
* given type in the requested direction? (dir 0=out, 1=in, 2=any) */
static bool eval_exists_condition(const cbm_condition_t *c, binding_t *b) {
cbm_node_t *n = binding_get(b, c->variable);
bool result = false;
if (n && b->store) {
cbm_edge_t *edges = NULL;
int cnt = 0;
if (c->exists_dir != EXISTS_DIR_IN) { /* outbound or any */
if (c->value) {
cbm_store_find_edges_by_source_type(b->store, n->id, c->value, &edges, &cnt);
} else {
cbm_store_find_edges_by_source(b->store, n->id, &edges, &cnt);
}
result = cnt > 0;
cbm_store_free_edges(edges, cnt);
}
if (!result && c->exists_dir != EXISTS_DIR_OUT) { /* inbound or any */
edges = NULL;
cnt = 0;
if (c->value) {
cbm_store_find_edges_by_target_type(b->store, n->id, c->value, &edges, &cnt);
} else {
cbm_store_find_edges_by_target(b->store, n->id, &edges, &cnt);
}
result = cnt > 0;
cbm_store_free_edges(edges, cnt);
}
}
return c->negated ? !result : result;
}
/* a.x <op> b.y (#2591): the RHS operand is read from the same row. An unbound
* RHS alias does not filter, like an unbound LHS. A missing (empty) property
* on either side is NULL and the comparison is false, so two nodes that both
* lack a property do not compare equal. */
static bool eval_property_comparison(const cbm_condition_t *c, const char *actual, binding_t *b) {
cbm_condition_t rhs = {0};
rhs.variable = c->rhs_variable;
rhs.property = c->rhs_property;
const char *expected = resolve_condition_value(&rhs, b);
if (!expected) {
return true;
}
if (actual[0] == '\0' || expected[0] == '\0') {
return false;
}
bool result = eval_comparison_op(c->op, actual, expected);
return c->negated ? !result : result;
}
/* Evaluate a WHERE condition against a binding */
static bool eval_condition(const cbm_condition_t *c, binding_t *b) {
/* Label test: WHERE n:Label (#241) — compare the bound node's label
* directly rather than a property value. */
if (strcmp(c->op, "HAS_LABEL") == 0) {
cbm_node_t *n = binding_get(b, c->variable);
bool result = n && n->label && c->value && strcmp(n->label, c->value) == 0;
return c->negated ? !result : result;
}
if (strcmp(c->op, "EXISTS") == 0) {
return eval_exists_condition(c, b);
}
const char *actual = resolve_condition_value(c, b);
/* coalesce(var.prop, literal) (#874): a missing/empty property value
* falls back to the literal default before the operator runs. */
if (c->coalesce_default && (!actual || actual[0] == '\0')) {
actual = c->coalesce_default;
}
if (!actual) {
return true;
}
bool result;
/* IS NULL / IS NOT NULL */
if (strcmp(c->op, "IS NULL") == 0) {
result = (actual[0] == '\0');
return c->negated ? !result : result;
}
if (strcmp(c->op, "IS NOT NULL") == 0) {
result = (actual[0] != '\0');
return c->negated ? !result : result;
}
/* IN [...] */
if (strcmp(c->op, "IN") == 0) {
result = false;
for (int i = 0; i < c->in_value_count; i++) {
if (strcmp(actual, c->in_values[i]) == 0) {
result = true;
break;
}
}
return c->negated ? !result : result;
}
if (c->rhs_variable) {
return eval_property_comparison(c, actual, b);
}
result = eval_comparison_op(c->op, actual, c->value);
return c->negated ? !result : result;
}
/* Expression tree evaluator. Recurses into NOT and into the left operand of a
* binary node; a chain of one operator is linked along the right child (see
* expr_chain_link) and is walked here in a loop. */
static bool eval_expr(const cbm_expr_t *e, binding_t *b) { // NOLINT(misc-no-recursion)
if (!e) {
return true;
}
if (e->type == EXPR_CONDITION) {
return eval_condition(&e->cond, b);
}
if (e->type == EXPR_NOT) {
return (!eval_expr(e->left, b)) != 0;
}
/* AND / OR / XOR. The nested form `a OP (b OP (c ...))` evaluates a, then
* b, then c, and AND/OR stop at the first operand that decides the result;
* the loop does exactly that, one link per iteration. A right child that
* is not a link of the same operator is the chain's last operand. */
const cbm_expr_type_t type = e->type;
bool acc = eval_expr(e->left, b);
const cbm_expr_t *rest = e->right;
for (;;) {
if ((type == EXPR_AND && !acc) || (type == EXPR_OR && acc)) {
return acc;
}
bool linked = rest && rest->type == type;
bool v = eval_expr(linked ? rest->left : rest, b);
/* AND reaches here only with acc true, OR only with acc false, so the
* combined value is v itself; XOR keeps the running parity. */
acc = (type == EXPR_XOR) ? (acc != v) : v;
if (!linked) {
return acc;
}
rest = rest->right;
}
}
/* Evaluate WHERE clause — uses expression tree if available, falls back to legacy */
static bool eval_where(const cbm_where_clause_t *w, binding_t *b) {
if (!w) {
return true;
}
if (w->root) {
return eval_expr(w->root, b);
}
/* Legacy flat evaluation */
if (w->count == 0) {
return true;
}
bool is_and = (w->op && strcmp(w->op, "AND") == 0) != 0;
for (int i = 0; i < w->count; i++) {
bool r = eval_condition(&w->conditions[i], b);
if (is_and && !r) {
return false;
}
if (!is_and && r) {
return true;
}
}
return is_and;
}
/* Three-valued WHERE evaluation for the early (seed-row) pass in
* execute_single: only the first MATCH alias is bound there, so a leaf on
* any other alias is UNKNOWN rather than true. The two-valued evaluator
* returns true for an unbound alias, which NOT / XOR then invert -- pruning
* every seed before relationship expansion (distilled from PR #1245). The
* full evaluation reruns after expansion (Step 3), so the early pass only has
* to prune on a definite false. Allocation-free, O(expression nodes). */
typedef enum { CYP_PARTIAL_FALSE = 0, CYP_PARTIAL_TRUE, CYP_PARTIAL_UNKNOWN } cyp_partial_t;
static cyp_partial_t partial_and(cyp_partial_t l, cyp_partial_t r) {
if (l == CYP_PARTIAL_FALSE || r == CYP_PARTIAL_FALSE) {
return CYP_PARTIAL_FALSE;
}
return (l == CYP_PARTIAL_TRUE && r == CYP_PARTIAL_TRUE) ? CYP_PARTIAL_TRUE
: CYP_PARTIAL_UNKNOWN;
}
static cyp_partial_t partial_or(cyp_partial_t l, cyp_partial_t r) {
if (l == CYP_PARTIAL_TRUE || r == CYP_PARTIAL_TRUE) {
return CYP_PARTIAL_TRUE;
}
return (l == CYP_PARTIAL_FALSE && r == CYP_PARTIAL_FALSE) ? CYP_PARTIAL_FALSE
: CYP_PARTIAL_UNKNOWN;
}
static bool partial_alias_unbound(binding_t *b, const char *alias) {
return alias && !binding_get(b, alias) && !binding_get_edge(b, alias);
}
/* A condition is UNKNOWN while any alias it reads is not bound yet: its own
* variable, the RHS of a property comparison (the b in a.x = b.y), and every
* function argument's -- a func condition is filed under its first argument's
* alias, so the b in coalesce(a.x, b.name) is only seen here. A literal-only
* LHS has nothing to wait for. */
static cyp_partial_t eval_condition_partial(const cbm_condition_t *c, binding_t *b) {
if (partial_alias_unbound(b, c->variable) || partial_alias_unbound(b, c->rhs_variable)) {
return CYP_PARTIAL_UNKNOWN;
}
for (int i = 0; i < c->arg_count; i++) {
if (partial_alias_unbound(b, c->args[i].variable)) {
return CYP_PARTIAL_UNKNOWN;
}
}
return eval_condition(c, b) ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
}
static cyp_partial_t partial_xor(cyp_partial_t l, cyp_partial_t r) {
if (l == CYP_PARTIAL_UNKNOWN || r == CYP_PARTIAL_UNKNOWN) {
return CYP_PARTIAL_UNKNOWN;
}
return l != r ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
}
/* Combine the running value of an AND / OR / XOR chain with its next operand. */
static cyp_partial_t partial_combine(cbm_expr_type_t type, cyp_partial_t acc, cyp_partial_t v) {
if (type == EXPR_AND) {
return partial_and(acc, v);
}
if (type == EXPR_OR) {
return partial_or(acc, v);
}
return partial_xor(acc, v);
}
/* Same walk as eval_expr: recurses into NOT and into each operand, and follows
* a chain of one operator (linked along the right child, see expr_chain_link)
* in a loop, so a chain's length never becomes stack depth. This runs on every
* seed row of execute_single, so it sees every WHERE chain the parser accepts.
* The operands are read in the order of the nested form `a OP (b OP (c ...))`,
* with its short-circuits: AND stops at the first definite false, OR at the
* first definite true, and XOR reads every operand. */
static cyp_partial_t eval_expr_partial(const cbm_expr_t *e, // NOLINT(misc-no-recursion)
binding_t *b) {
if (!e) {
return CYP_PARTIAL_TRUE;
}
if (e->type == EXPR_CONDITION) {
return eval_condition_partial(&e->cond, b);
}
if (e->type == EXPR_NOT) {
cyp_partial_t child = eval_expr_partial(e->left, b);
if (child == CYP_PARTIAL_UNKNOWN) {
return CYP_PARTIAL_UNKNOWN;
}
return child == CYP_PARTIAL_TRUE ? CYP_PARTIAL_FALSE : CYP_PARTIAL_TRUE;
}
/* AND / OR / XOR. A right child that is not a link of the same operator is
* the chain's last operand; one that is a parenthesised group of the same
* operator is read as more links, which the operator's associativity
* (three-valued as well) makes the same value. */
const cbm_expr_type_t type = e->type;
cyp_partial_t acc = eval_expr_partial(e->left, b);
const cbm_expr_t *rest = e->right;
for (;;) {
if ((type == EXPR_AND && acc == CYP_PARTIAL_FALSE) ||
(type == EXPR_OR && acc == CYP_PARTIAL_TRUE)) {
return acc;
}
bool linked = rest && rest->type == type;
cyp_partial_t v = eval_expr_partial(linked ? rest->left : rest, b);
acc = partial_combine(type, acc, v);
if (!linked) {
return acc;
}
rest = rest->right;
}
}
static cyp_partial_t eval_where_partial(const cbm_where_clause_t *w, binding_t *b) {
if (!w) {
return CYP_PARTIAL_TRUE;
}
if (w->root) {
return eval_expr_partial(w->root, b);
}
/* Legacy flat evaluation */
if (w->count == 0) {
return CYP_PARTIAL_TRUE;
}
bool is_and = (w->op && strcmp(w->op, "AND") == 0) != 0;
cyp_partial_t result = is_and ? CYP_PARTIAL_TRUE : CYP_PARTIAL_FALSE;
for (int i = 0; i < w->count; i++) {
cyp_partial_t r = eval_condition_partial(&w->conditions[i], b);
result = is_and ? partial_and(result, r) : partial_or(result, r);
}
return result;
}
/* Check if a string value looks like a regex pattern. */
static bool looks_like_regex(const char *s) {
if (!s) {
return false;
}
return strstr(s, ".*") || strstr(s, ".+") || strchr(s, '[') || strchr(s, '(') ||
strchr(s, '|') || strchr(s, '^') || strchr(s, '$');
}
/* Check inline property filters.
* Values that look like regex patterns are matched with POSIX ERE;
* plain values use exact strcmp. */
static bool check_inline_props(const cbm_node_t *n, const cbm_prop_filter_t *props, int count,
cbm_store_t *store) {
for (int i = 0; i < count; i++) {
const char *actual = node_prop(n, props[i].key, store);
if (looks_like_regex(props[i].value)) {
cbm_regex_t re;
int comp_rc = cbm_regcomp(&re, props[i].value, CBM_REG_EXTENDED | CBM_REG_NOSUB);
if (comp_rc == 0) {
bool matched = cbm_regexec(&re, actual, 0, NULL, 0) == 0;
cbm_regfree(&re);
if (!matched) {
return false;
}
} else if (strcmp(actual, props[i].value) != 0) {
if (comp_rc == CBM_REG_ETOOBIG) {
g_cypher_regex_refused = true;
}
return false;
}
} else if (strcmp(actual, props[i].value) != 0) {
return false;
}
}
return true;
}
/* ── Result building helpers ────────────────────────────────────── */
typedef struct {
const char ***rows;
int row_count;
int row_cap;
const char **columns;
int col_count;
} result_builder_t;
static void rb_init(result_builder_t *rb) {
memset(rb, 0, sizeof(*rb));
rb->row_cap = CBM_SZ_32;
rb->rows = malloc(rb->row_cap * sizeof(const char **));
}
static void rb_set_columns(result_builder_t *rb, const char **cols, int count) {
rb->columns = malloc((count > 0 ? (size_t)count : SKIP_ONE) * sizeof(const char *));
for (int i = 0; i < count; i++) {
rb->columns[i] = heap_strdup(cols[i]);
}
rb->col_count = count;
}
static void rb_add_row(result_builder_t *rb, const char **values) {
if (rb->row_count >= rb->row_cap) {
rb->row_cap *= PAIR_LEN;
rb->rows = safe_realloc(rb->rows, rb->row_cap * sizeof(const char **));
}
const char **row =
malloc((rb->col_count > 0 ? (size_t)rb->col_count : SKIP_ONE) * sizeof(const char *));
for (int i = 0; i < rb->col_count; i++) {
row[i] = values[i] ? heap_strdup(values[i]) : heap_strdup("");
}
rb->rows[rb->row_count++] = row;
}
/* ── DISTINCT while projecting (#1364) ─────────────────────────────
*
* RETURN DISTINCT used to project up to the engine row cap and only then drop
* duplicates, so a value first seen past the cap never reached the result: on
* a 150k-edge index `RETURN DISTINCT type(r)` lost its one HAS_BRANCH edge.
* The projection loops now de-duplicate as they go, so the cap counts DISTINCT
* rows. Memory stays bounded by the cap: only admitted rows are remembered;
* rows past the cap are probed (no insert) solely to decide `truncated`. */
typedef struct {
CBMHashTable *seen; /* row key -> the same heap key; NULL = not DISTINCT */
} rb_distinct_t;
static void rb_distinct_init(rb_distinct_t *d, bool distinct) {
d->seen = distinct ? cbm_ht_create(CBM_SZ_64) : NULL;
}
static void rb_distinct_free_key(const char *key, void *value, void *userdata) {
(void)key;
(void)userdata;
cbm_free(CBM_MEM_CLASS_OTHER, value);
}
static void rb_distinct_free(rb_distinct_t *d) {
if (d->seen) {
cbm_ht_foreach(d->seen, rb_distinct_free_key, NULL);
cbm_ht_free(d->seen);
d->seen = NULL;
}
}
/* Length-prefixed row key ("<len>:<value>" per column), so no value content
* can make two different rows collide. NULL projects as "" (as rb_add_row). */
static char *rb_distinct_row_key(const char **vals, int n) {
size_t total = SKIP_ONE;
for (int i = 0; i < n; i++) {
total += (vals[i] ? strlen(vals[i]) : 0) + CBM_SZ_32;
}
char *key = cbm_alloc(CBM_MEM_CLASS_OTHER, total);
if (!key) {
return NULL;
}
size_t pos = 0;
key[0] = '\0';
for (int i = 0; i < n; i++) {
const char *v = vals[i] ? vals[i] : "";
int w = snprintf(key + pos, total - pos, "%zu:%s", strlen(v), v);
if (w > 0) {
pos += (size_t)w;
}
}
return key;
}
/* Admission for one projected row. Returns false for a row DISTINCT already
* holds. On true, *key_out is the key to hand to rb_distinct_keep (NULL when
* not DISTINCT, or when the key allocation failed — the row is then admitted
* without de-duplication rather than dropped). */
static bool rb_distinct_is_new(const rb_distinct_t *d, const char **vals, int n, char **key_out) {
*key_out = NULL;
if (!d->seen) {
return true;
}
char *key = rb_distinct_row_key(vals, n);
if (!key) {
return true;
}
if (cbm_ht_has(d->seen, key)) {
cbm_free(CBM_MEM_CLASS_OTHER, key);
return false;
}
*key_out = key;
return true;
}
static void rb_distinct_keep(rb_distinct_t *d, char *key) {
if (key) {
cbm_ht_set(d->seen, key, key);
}
}
/* Add one projected row under a row cap, de-duplicating when DISTINCT.
* Returns false once a NEW row arrives with the cap already full: the caller
* stops there, and flags truncation when the cap is the engine budget. A
* duplicate past the cap is neither kept nor evidence of truncation. */
static bool rb_add_row_capped(result_builder_t *rb, rb_distinct_t *d, const char **vals, int cap) {
char *key = NULL;
if (!rb_distinct_is_new(d, vals, rb->col_count, &key)) {
return true;
}
if (rb->row_count >= cap) {
cbm_free(CBM_MEM_CLASS_OTHER, key);
return false;
}
rb_distinct_keep(d, key);
rb_add_row(rb, vals);
return true;
}
/* ── Main execution ─────────────────────────────────────────────── */
/* Hard ceiling: queries returning more than this trigger an error instead of data.
* Prevents accidental multi-GB JSON payloads from unbounded MATCH (n) RETURN n. */
#define CYPHER_RESULT_CEILING 100000
/* Wall-clock execution deadline (#601). The row ceiling above only fires once
* rows exist, but an unbounded `OPTIONAL MATCH` over the full node set (or a
* GROUP BY with ~one group per node) does O(bindings x groups) work and can run
* for minutes — exhausting RAM/CPU — before a single row is produced, so the
* ceiling never trips and the caller just hangs. A monotonic deadline aborts
* such runaway queries with a clear, actionable error. Checked (throttled) in
* the scan, expansion and aggregation hot loops. */
#define CYPHER_DEADLINE_BUDGET_MS 30000 /* 30s: generous for legit heavy queries */
#define CYPHER_DEADLINE_CHECK_MASK 0x3FF /* sample the clock every 1024 iterations */
static _Thread_local uint64_t g_cypher_deadline_ms = 0; /* absolute; 0 = disarmed */
static _Thread_local bool g_cypher_timed_out = false;
/* Sticky for one cbm_cypher_execute call. Unlike row_count, this survives caps
* that happen before DISTINCT, aggregation, ORDER BY, or the final projection. */
static _Thread_local bool g_cypher_truncated = false;
/* Set when the streamed start-node scan failed in this execution: the query
* fails with this store error rather than answer from the rows read so far. */
static _Thread_local char g_cypher_scan_error[CBM_SZ_512];
static _Thread_local int64_t g_cypher_deadline_override_ms = -1; /* test hook; <0 = default */
#ifdef CBM_ENABLE_TEST_SEAMS
static _Thread_local cbm_cypher_test_clock_fn g_cypher_deadline_clock = NULL;
void cbm_cypher_test_set_deadline_clock(cbm_cypher_test_clock_fn clock_fn) {
g_cypher_deadline_clock = clock_fn;
}
#endif
static uint64_t cypher_deadline_now(void) {
#ifdef CBM_ENABLE_TEST_SEAMS
if (g_cypher_deadline_clock) {
return g_cypher_deadline_clock();
}
#endif
return cbm_now_ms();
}
static void cypher_deadline_arm(void) {
g_cypher_timed_out = false;
int64_t budget = g_cypher_deadline_override_ms >= 0 ? g_cypher_deadline_override_ms
: CYPHER_DEADLINE_BUDGET_MS;
g_cypher_deadline_ms = cypher_deadline_now() + (uint64_t)budget;
}
/* True once the query has run past its wall-clock budget. Sticky: after the
* first trip every subsequent call returns true, so later loops short-circuit. */
static bool cypher_deadline_exceeded(void) {
if (g_cypher_timed_out) {
return true;
}
if (g_cypher_deadline_ms == 0) {
return false;
}
if (cypher_deadline_now() >= g_cypher_deadline_ms) {
g_cypher_timed_out = true;
return true;
}
return false;
}
/* Test-only: force the execution budget (ms) for subsequent queries on this
* thread. 0 = trip on the first hot-loop check; <0 restores the default. */
void cbm_cypher_test_set_deadline_ms(int64_t budget_ms) {
g_cypher_deadline_override_ms = budget_ms;
}
/* ── Binding virtual variables (for WITH clause) ──────────────── */
static const char *binding_get_virtual(binding_t *b, const char *var, const char *prop) {
if (!var) {
return "";
}
/* Check virtual vars first (from WITH projection) */
char full[CBM_SZ_256];
if (prop) {
snprintf(full, sizeof(full), "%s.%s", var, prop);
} else {
snprintf(full, sizeof(full), "%s", var);
}
for (int i = 0; i < b->var_count; i++) {
if (strcmp(b->var_names[i], full) == 0) {
return b->var_nodes[i].name ? b->var_nodes[i].name : "";
}
}
/* Fall through to normal lookup */
cbm_edge_t *e = binding_get_edge(b, var);
if (e) {
/* Bare `RETURN r` on an edge: surface the full properties JSON
* (or "{}" if none) so callers can inspect timestamps, weights,
* etc. without naming each property. */
return prop ? edge_prop(e, prop) : (e->properties_json ? e->properties_json : "{}");
}
cbm_node_t *n = binding_get(b, var);
if (n) {
if (prop) {
return node_prop(n, prop, b->store);
}
return n->name ? n->name : "";
}
return "";
}
/* ── String function application ──────────────────────────────── */
static const char *apply_string_func(const char *func, const char *val, char *buf, size_t buf_sz) {
if (!func || !val) {
return val ? val : "";
}
if (strcmp(func, "toLower") == 0) {
size_t i = 0;
for (; i < buf_sz - SKIP_ONE && val[i]; i++) {
buf[i] = (char)tolower((unsigned char)val[i]);
}
buf[i] = '\0';
return buf;
}
if (strcmp(func, "toUpper") == 0) {
size_t i = 0;
for (; i < buf_sz - SKIP_ONE && val[i]; i++) {
buf[i] = (char)toupper((unsigned char)val[i]);
}
buf[i] = '\0';
return buf;
}
if (strcmp(func, "toString") == 0) {
return val; /* already strings */
}
if (strcmp(func, "toInteger") == 0) {
char *end = NULL;
long long v = strtoll(val, &end, CBM_DECIMAL_BASE);
if (end == val) {
/* Not an integer literal — accept a float string and truncate. */
char *fend = NULL;
double d = strtod(val, &fend);
if (fend == val) {
return ""; /* non-numeric → null */
}
v = (long long)d;
}
snprintf(buf, buf_sz, "%lld", v);
return buf;
}
if (strcmp(func, "toFloat") == 0) {
char *end = NULL;
double d = strtod(val, &end);
if (end == val) {
return ""; /* non-numeric → null */
}
snprintf(buf, buf_sz, "%g", d);
return buf;
}
if (strcmp(func, "toBoolean") == 0) {
if (cyp_ci_eq(val, "true")) {
return "true";
}
if (cyp_ci_eq(val, "false")) {
return "false";
}
return ""; /* not a boolean → null */
}
if (strcmp(func, "size") == 0 || strcmp(func, "length") == 0) {
snprintf(buf, buf_sz, "%zu", strlen(val));
return buf;
}
if (strcmp(func, "trim") == 0 || strcmp(func, "ltrim") == 0 || strcmp(func, "rtrim") == 0) {
bool do_left = (strcmp(func, "trim") == 0 || strcmp(func, "ltrim") == 0);
bool do_right = (strcmp(func, "trim") == 0 || strcmp(func, "rtrim") == 0);
const char *start = val;
const char *end = val + strlen(val);
while (do_left && (*start == ' ' || *start == '\t' || *start == '\n' || *start == '\r')) {
start++;
}
while (do_right && end > start &&
(end[-1] == ' ' || end[-1] == '\t' || end[-1] == '\n' || end[-1] == '\r')) {
end--;
}
size_t n = (size_t)(end - start);
if (n >= buf_sz) {
n = buf_sz - SKIP_ONE;
}
memcpy(buf, start, n);
buf[n] = '\0';
return buf;
}
if (strcmp(func, "reverse") == 0) {
size_t len = strlen(val);
if (len >= buf_sz) {
len = buf_sz - SKIP_ONE;
}
for (size_t i = 0; i < len; i++) {
buf[i] = val[len - SKIP_ONE - i];
}
buf[len] = '\0';
return buf;
}
return val;
}
/* ── CASE expression evaluation ───────────────────────────────── */
static const char *eval_case_expr(const cbm_case_expr_t *k, binding_t *b) {
if (!k) {
return "";
}
for (int i = 0; i < k->branch_count; i++) {
if (eval_expr(k->branches[i].when_expr, b)) {
return k->branches[i].then_val ? k->branches[i].then_val : "";
}
}
return k->else_val ? k->else_val : "";
}
/* ── Scan nodes for a pattern ─────────────────────────────────── */
/* True if `actual` matches `pat`, where `pat` may be a '|'-alternation of
* labels ("A|B|C") — openCypher label alternation (#242). */
static bool label_alt_matches(const char *actual, const char *pat) {
if (!pat) {
return true;
}
if (!actual) {
return false;
}
if (!strchr(pat, '|')) {
return strcmp(actual, pat) == 0;
}
size_t al = strlen(actual);
const char *seg = pat;
while (*seg) {
const char *bar = strchr(seg, '|');
size_t seglen = bar ? (size_t)(bar - seg) : strlen(seg);
if (seglen == al && strncmp(seg, actual, seglen) == 0) {
return true;
}
if (!bar) {
break;
}
seg = bar + SKIP_ONE;
}
return false;
}
/* Seed nodes for a label alternation "A|B|C": union the per-label results.
* Node-struct fields are moved (shallow) into out_nodes; each per-label array
* container is freed. */
static void scan_alternation_labels(cbm_store_t *store, const char *project, const char *labels,
cbm_node_t **out_nodes, int *out_count) {
*out_nodes = NULL;
*out_count = 0;
int cap = 0;
char *copy = heap_strdup(labels);
if (!copy) {
return;
}
char *save = NULL;
for (char *tok = strtok_r(copy, "|", &save); tok; tok = strtok_r(NULL, "|", &save)) {
cbm_node_t *part = NULL;
int pc = 0;
cbm_store_find_nodes_by_label(store, project, tok, &part, &pc);
if (pc > 0 && part) {
if (*out_count + pc > cap) {
cap = (*out_count + pc) * PAIR_LEN;
*out_nodes = safe_realloc(*out_nodes, (size_t)cap * sizeof(cbm_node_t));
}
memcpy(*out_nodes + *out_count, part, (size_t)pc * sizeof(cbm_node_t));
*out_count += pc;
}
free(part); /* container only — node fields moved to out_nodes */
}
free(copy);
}
static void scan_pattern_nodes(cbm_store_t *store, const char *project, cbm_node_pattern_t *first,
cbm_node_t **out_nodes, int *out_count) {
if (first->label && strchr(first->label, '|')) {
scan_alternation_labels(store, project, first->label, out_nodes, out_count);
} else if (first->label) {
cbm_store_find_nodes_by_label(store, project, first->label, out_nodes, out_count);
} else {
cbm_store_find_nodes(store, project, out_nodes, out_count);
}
/* Apply inline property filters — free rejected nodes' strings */
if (first->prop_count > 0) {
int kept = 0;
for (int i = 0; i < *out_count; i++) {
if (check_inline_props(&(*out_nodes)[i], first->props, first->prop_count, store)) {
if (kept != i) {
(*out_nodes)[kept] = (*out_nodes)[i];
}
kept++;
} else {
node_fields_free(&(*out_nodes)[i]);
}
}
*out_count = kept;
}
}
/* ── Expand one pattern's relationships on a set of bindings ──── */
/* Process edges: look up target node, filter by label/props, add binding.
* `inbound` controls which end of the edge is the target id. */
/* #1196 (second mechanism): a hop's output buffer must hold EVERY matched
* row. max_rows is an OUTPUT-row limit — projection already enforces it — and
* WHERE/aggregation run after expansion, so any cap here silently falsifies
* results: field-measured, count() reported 9,360 of 13,691 DEFINES because
* the old bind_cap*10 ceiling dropped edges before aggregation ever saw them,
* and a labeled source did not save you. The buffer now grows geometrically;
* only allocation failure stops materialisation (the #601 deadline still
* bounds time), and match_count stays truthful either way (#627 contract). */
static bool binding_out_append(binding_t **rows, int *count, int *cap, binding_t *nb) {
if (*count == *cap) {
int next = *cap > 0 ? *cap * CYP_GROWTH_2 : CYP_GROWTH_10;
binding_t *grown = realloc(*rows, (size_t)next * sizeof(binding_t));
if (!grown) {
binding_free(nb);
return false;
}
*rows = grown;
*cap = next;
}
(*rows)[(*count)++] = *nb;
return true;
}
static void process_edges(cbm_store_t *store, cbm_edge_t *edges, int edge_count, bool inbound,
const cbm_node_pattern_t *target_node, binding_t *b, const char *to_var,
const char *rel_var, binding_t **new_bindings, int *new_count,
int *new_cap, int *match_count) {
/* When the terminal node variable is ALREADY bound (e.g. the second pattern
* `(c)-[:CALLS]->(f)` where `f` came from an earlier MATCH), we must FILTER
* to edges that actually reach the bound node — not overwrite the caller's
* `f` binding with whatever node the edge leads to. Overwriting corrupted
* the result of dead-code queries and produced wrong rows (#627). */
cbm_node_t *bound_to = binding_get(b, to_var);
int64_t bound_to_id = bound_to ? bound_to->id : 0;
/* The budget caps MATERIALISATION, not detection: `match_count` must stay
* truthful even after `new_count` hits `max_new`. Gating the loop itself
* (`ei < edge_count && *new_count < max_new`) stopped fetching entirely, so
* a saturated source reported `match_count == 0` despite having neighbours —
* and the OPTIONAL fallback in expand_pattern_rels then emitted an unbound
* "no match" row for it. `WHERE x IS NULL` reads those rows as "nothing
* points here", i.e. it reported live code as dead. Losing rows is
* recoverable; asserting a match does not exist when it does is not. */
for (int ei = 0; ei < edge_count; ei++) {
int64_t tid = inbound ? edges[ei].source_id : edges[ei].target_id;
if (bound_to && tid != bound_to_id) {
continue; /* edge does not reach the already-bound terminal node */
}
cbm_node_t found = {0};
if (cbm_store_find_node_by_id(store, tid, &found) != CBM_STORE_OK) {
continue;
}
if (target_node->label && !label_alt_matches(found.label, target_node->label)) {
node_fields_free(&found);
continue;
}
if (!check_inline_props(&found, target_node->props, target_node->prop_count, store)) {
node_fields_free(&found);
continue;
}
(*match_count)++; /* a real neighbour exists, OOM or not */
binding_t nb = {0};
binding_copy(&nb, b);
binding_take_node(&nb, to_var, &found);
if (rel_var) {
binding_set_edge(&nb, rel_var, &edges[ei]);
}
(void)binding_out_append(new_bindings, new_count, new_cap, &nb);
node_fields_free(&found);
}
}
/* Expand variable-length relationship via BFS */
/* Set when a variable-length hop range is clamped to the engine ceiling
* during the CURRENT execution; cbm_cypher_execute turns it into
* result->warning so callers can tell "clamped" from "no such path" (#797). */
/* C11 _Thread_local directly: cypher.c stays windows.h-free (compat.h pulls
* in windows.h, whose legacy `far` macro breaks this file's identifiers). */
static _Thread_local int g_cypher_depth_clamped = 0;
static _Thread_local int g_cypher_trail_truncated = 0;
static void expand_var_length(cbm_store_t *store, cbm_rel_pattern_t *rel,
cbm_node_pattern_t *target_node, binding_t *b, cbm_node_t *src,
const char *to_var, binding_t **new_bindings, int *new_count,
int *new_cap, int *match_count) {
/* Clamp BOTH the explicit (`*1..N`) and unbounded (`*`, `*..m`) forms to the
* engine ceiling: an explicit N above the cap was previously honoured
* verbatim, driving cbm_store_bfs to an unbounded hop count (#887). WARN on
* clamp — never a silent truncation. */
int depth_cap = cbm_cypher_max_depth();
int max_depth = rel->max_hops > 0 ? rel->max_hops : depth_cap;
/* A range clamped to the engine ceiling (or an unbounded one) is probed one
* hop beyond it: a candidate out there means the clamp hid real rows, so the
* result is reported truncated; a clamp on a shallow graph stays a warning. */
bool probe_beyond_depth_cap = rel->max_hops <= 0 || max_depth > depth_cap;
if (max_depth > depth_cap) {
char req_buf[16];
char cap_buf[16];
snprintf(req_buf, sizeof(req_buf), "%d", max_depth);
snprintf(cap_buf, sizeof(cap_buf), "%d", depth_cap);
cbm_log_warn("cypher.depth_capped", "requested", req_buf, "cap", cap_buf);
g_cypher_depth_clamped = depth_cap; /* surfaced as result->warning (#797) */
max_depth = depth_cap;
}
cbm_traverse_result_t tr = {0};
const char *dir = rel->direction ? rel->direction : "outbound";
int traversal_depth = probe_beyond_depth_cap ? depth_cap + SKIP_ONE : max_depth;
cbm_store_bfs_trail(store, src->id, dir, rel->types, rel->type_count, traversal_depth,
CBM_PERCENT, &tr);
if (tr.truncated) {
g_cypher_trail_truncated = 1;
}
cbm_node_t *bound_to = binding_get(b, to_var);
int64_t bound_to_id = bound_to ? bound_to->id : 0;
/* Same contract as process_edges: the budget caps materialisation, never
* detection, so a saturated source cannot report match_count == 0 and get a
* fabricated OPTIONAL "no match" row. */
for (int v = 0; v < tr.visited_count; v++) {
cbm_node_hop_t *hop = &tr.visited[v];
if (hop->hop > max_depth) {
g_cypher_truncated = true; /* the probe hop found a candidate past the cap */
continue;
}
if (hop->hop < rel->min_hops) {
continue;
}
if (bound_to && hop->node.id != bound_to_id) {
continue;
}
if (target_node->label && !label_alt_matches(hop->node.label, target_node->label)) {
continue;
}
if (!check_inline_props(&hop->node, target_node->props, target_node->prop_count, store)) {
continue;
}
(*match_count)++;
binding_t nb = {0};
binding_copy(&nb, b);
binding_set(&nb, to_var, &hop->node);
(void)binding_out_append(new_bindings, new_count, new_cap, &nb);
}
cbm_store_traverse_free(&tr);
}
/* Expand fixed-length (1-hop) relationship edges */
static void expand_fixed_length(cbm_store_t *store, cbm_rel_pattern_t *rel,
cbm_node_pattern_t *target_node, binding_t *b, cbm_node_t *src,
const char *to_var, binding_t **new_bindings, int *new_count,
int *new_cap, int *match_count) {
bool is_inbound = rel->direction && strcmp(rel->direction, "inbound") == 0;
bool is_any = rel->direction && strcmp(rel->direction, "any") == 0;
const char *rel_var = rel->variable;
if (rel->type_count > 0) {
for (int ti = 0; ti < rel->type_count; ti++) {
cbm_edge_t *edges = NULL;
int edge_count = 0;
if (is_inbound) {
cbm_store_find_edges_by_target_type(store, src->id, rel->types[ti], &edges,
&edge_count);
} else {
cbm_store_find_edges_by_source_type(store, src->id, rel->types[ti], &edges,
&edge_count);
}
process_edges(store, edges, edge_count, is_inbound, target_node, b, to_var, rel_var,
new_bindings, new_count, new_cap, match_count);
cbm_store_free_edges(edges, edge_count);
}
if (is_any) {
for (int ti = 0; ti < rel->type_count; ti++) {
cbm_edge_t *edges = NULL;
int edge_count = 0;
cbm_store_find_edges_by_target_type(store, src->id, rel->types[ti], &edges,
&edge_count);
process_edges(store, edges, edge_count, true, target_node, b, to_var, rel_var,
new_bindings, new_count, new_cap, match_count);
cbm_store_free_edges(edges, edge_count);
}
}
} else {
cbm_edge_t *edges = NULL;
int edge_count = 0;
if (is_inbound) {
cbm_store_find_edges_by_target(store, src->id, &edges, &edge_count);
} else {
cbm_store_find_edges_by_source(store, src->id, &edges, &edge_count);
}
process_edges(store, edges, edge_count, is_inbound, target_node, b, to_var, rel_var,
new_bindings, new_count, new_cap, match_count);
cbm_store_free_edges(edges, edge_count);
if (is_any) {
edges = NULL;
edge_count = 0;
cbm_store_find_edges_by_target(store, src->id, &edges, &edge_count);
process_edges(store, edges, edge_count, true, target_node, b, to_var, rel_var,
new_bindings, new_count, new_cap, match_count);
cbm_store_free_edges(edges, edge_count);
}
}
}
static void expand_pattern_rels(cbm_store_t *store, cbm_pattern_t *pat, binding_t **bindings,
int *bind_count, int *bind_cap, const char **var_name,
bool is_optional) {
for (int ri = 0; ri < pat->rel_count; ri++) {
/* #601: stop expanding further hops once the wall-clock budget is spent
* (an unbounded expansion is exactly what blows up here). */
if (cypher_deadline_exceeded()) {
return;
}
cbm_rel_pattern_t *rel = &pat->rels[ri];
cbm_node_pattern_t *target_node = &pat->nodes[ri + SKIP_ONE];
const char *to_var = target_node->variable ? target_node->variable : "_n_t";
bool is_variable_length = (rel->min_hops != SKIP_ONE || rel->max_hops != SKIP_ONE);
/* #1196: the hop's output buffer GROWS to hold every matched row —
* the old bind_cap*10 ceiling silently dropped edges before WHERE and
* aggregation, falsifying counts. binding_out_append handles growth
* and the OPTIONAL fallback shares it, so no writer can run off the
* end and no row class is dropped (the old fixed sizing had exactly
* those two failure modes, CWE-787 and the OPTIONAL data loss). */
int new_cap = *bind_count > 0 ? *bind_count : CYP_GROWTH_10;
binding_t *new_bindings = malloc((size_t)new_cap * sizeof(binding_t));
if (!new_bindings) {
return; /* OOM: leave existing bindings untouched rather than corrupt */
}
int new_count = 0;
for (int bi = 0; bi < *bind_count; bi++) {
if ((bi & CYPHER_DEADLINE_CHECK_MASK) == 0 && cypher_deadline_exceeded()) {
break;
}
binding_t *b = &(*bindings)[bi];
cbm_node_t *src = binding_get(b, *var_name);
if (!src) {
continue;
}
int match_count = 0;
if (is_variable_length) {
expand_var_length(store, rel, target_node, b, src, to_var, &new_bindings,
&new_count, &new_cap, &match_count);
} else {
expand_fixed_length(store, rel, target_node, b, src, to_var, &new_bindings,
&new_count, &new_cap, &match_count);
}
/* OPTIONAL MATCH: no expansion for this source, so keep the binding
* with the target unbound (projection renders it ""). The shared
* growable append gives every fallback row a slot. */
if (is_optional && match_count == 0) {
binding_t nb = {0};
binding_copy(&nb, b);
/* Don't set to_var — it remains unbound; projection returns "" */
(void)binding_out_append(&new_bindings, &new_count, &new_cap, &nb);
}
}
for (int bi = 0; bi < *bind_count; bi++) {
binding_free(&(*bindings)[bi]);
}
free(*bindings);
*bindings = new_bindings;
*bind_count = new_count;
*bind_cap = new_cap;
*var_name = to_var;
}
}
/* ── Sorting and key lookup ────────────────────────────────────────
* ORDER BY, GROUP BY and DISTINCT used to compare every row with every other
* row (bubble sorts, linear group and duplicate scans). These helpers keep the
* exact same comparisons and keys, in O(n log n) and O(n). */
/* Compare items a and b; positive means a sorts after b. */
typedef int (*cypher_index_cmp_fn)(const void *ctx, int a, int b);
/* Stable sort of idx[0..n). Both this and the bubble sorts it replaces are
* stable, so for any consistent ordering they give the same permutation. An
* item moves before an earlier one only when cmp(earlier, item) > 0, which is
* the bubble sorts' swap test. Without scratch memory it degrades to an
* insertion sort with the same test and result. */
static void cypher_stable_sort(int *idx, int n, cypher_index_cmp_fn cmp, const void *ctx) {
if (n < PAIR_LEN) {
return;
}
int *tmp = cbm_alloc(CBM_MEM_CLASS_OTHER, (size_t)n * sizeof(int));
if (!tmp) {
for (int i = SKIP_ONE; i < n; i++) {
for (int j = i; j > 0 && cmp(ctx, idx[j - SKIP_ONE], idx[j]) > 0; j--) {
int swap = idx[j];
idx[j] = idx[j - SKIP_ONE];
idx[j - SKIP_ONE] = swap;
}
}
return;
}
for (int64_t width = SKIP_ONE; width < n; width *= PAIR_LEN) {
for (int64_t lo = 0; lo < n; lo += PAIR_LEN * width) {
int64_t mid = lo + width < n ? lo + width : n;
int64_t hi = mid + width < n ? mid + width : n;
int64_t i = lo;
int64_t j = mid;
int64_t k = lo;
while (i < mid && j < hi) {
tmp[k++] = cmp(ctx, idx[i], idx[j]) > 0 ? idx[j++] : idx[i++];
}
while (i < mid) {
tmp[k++] = idx[i++];
}
while (j < hi) {
tmp[k++] = idx[j++];
}
}
memcpy(idx, tmp, (size_t)n * sizeof(int));
}
cbm_free(CBM_MEM_CLASS_OTHER, tmp);
}
/* String key → the index it was first recorded with. Keys are copied: the
* arrays they mirror are reallocated as they grow. */
typedef struct {
CBMHashTable *table;
char **keys;
int count;
int cap;
bool failed; /* an allocation failed: callers fall back to their scans */
} cypher_key_index_t;
/* The recorded index, CYP_FOUND_NONE, or KEY_INDEX_UNKNOWN after a failed
* allocation (the caller then scans, so a result never depends on memory). */
enum { KEY_INDEX_UNKNOWN = -2 };
static int key_index_find(const cypher_key_index_t *ix, const char *key) {
if (ix->failed) {
return KEY_INDEX_UNKNOWN;
}
void *value = ix->table ? cbm_ht_get(ix->table, key) : NULL;
return value ? (int)((intptr_t)value - SKIP_ONE) : CYP_FOUND_NONE;
}
static void key_index_add(cypher_key_index_t *ix, const char *key, int index) {
if (ix->failed) {
return;
}
if (!ix->table) {
ix->table = cbm_ht_create(CBM_SZ_256);
}
if (ix->table && ix->count >= ix->cap) {
int cap = ix->cap ? ix->cap * PAIR_LEN : CBM_SZ_256;
char **keys = cbm_realloc(CBM_MEM_CLASS_OTHER, ix->keys, (size_t)cap * sizeof(char *));
if (keys) {
ix->keys = keys;
ix->cap = cap;
}
}
char *copy = ix->table && ix->count < ix->cap ? cbm_mem_strdup(CBM_MEM_CLASS_OTHER, key) : NULL;
if (!copy) {
ix->failed = true;
return;
}
ix->keys[ix->count++] = copy;
(void)cbm_ht_set(ix->table, copy, (void *)(intptr_t)(index + SKIP_ONE));
}
static void key_index_free(cypher_key_index_t *ix) {
if (ix->table) {
cbm_ht_free(ix->table);
}
for (int i = 0; i < ix->count; i++) {
cbm_free(CBM_MEM_CLASS_OTHER, ix->keys[i]);
}
cbm_free(CBM_MEM_CLASS_OTHER, ix->keys);
memset(ix, 0, sizeof(*ix));
}
/* ── Result postprocessing helpers ─────────────────────────────── */
/* Find the column index for one ORDER BY key, checking both column names and
* aliases. Returns -1 if not found. */
static int rb_find_order_column(const result_builder_t *rb, const cbm_return_clause_t *ret,
const char *key) {
for (int ci = 0; ci < rb->col_count; ci++) {
if (strcmp(rb->columns[ci], key) == 0) {
return ci;
}
}
for (int ci = 0; ci < ret->count; ci++) {
if (ret->items[ci].alias && strcmp(ret->items[ci].alias, key) == 0) {
return ci;
}
}
return CBM_NOT_FOUND;
}
/* Check whether a column contains numeric data by examining the first non-empty value */
static bool rb_is_numeric_column(const result_builder_t *rb, int col) {
for (int i = 0; i < rb->row_count; i++) {
const char *v = rb->rows[i][col];
if (v && *v) {
const char *p2 = (*v == '-') ? v + SKIP_ONE : v;
if (*p2 == '\0') {
return false;
}
for (; *p2; p2++) {
if (*p2 < '0' || *p2 > '9') {
return false;
}
}
return true;
}
}
return false;
}
typedef struct {
const int *cols;
const bool *numeric;
const bool *descs;
int keys;
const char ***rows; /* the rows in their pre-sort order */
const int *values; /* numeric keys parsed once: values[row * keys + k], or NULL */
} rb_order_ctx_t;
/* One ORDER BY comparison: numeric columns by their (int)strtol value,
* others by strcmp, a later key breaking ties; positive = a after b.
* va/vb are the rows' parsed numeric keys, or NULL to parse here. */
static int rb_order_compare_rows(const rb_order_ctx_t *ctx, const char **ra, const char **rb_row,
const int *va, const int *vb) {
int cmp = 0;
for (int k = 0; k < ctx->keys && cmp == 0; k++) {
if (ctx->numeric[k]) {
int a = va ? va[k] : (int)strtol(ra[ctx->cols[k]], NULL, CBM_DECIMAL_BASE);
int b = vb ? vb[k] : (int)strtol(rb_row[ctx->cols[k]], NULL, CBM_DECIMAL_BASE);
cmp = (a > b) - (a < b);
} else {
cmp = strcmp(ra[ctx->cols[k]], rb_row[ctx->cols[k]]);
}
if (ctx->descs[k]) {
cmp = -cmp;
}
}
return cmp;
}
static int rb_order_compare(const void *context, int a, int b) {
const rb_order_ctx_t *ctx = context;
const int *va = ctx->values ? ctx->values + (size_t)a * (size_t)ctx->keys : NULL;
const int *vb = ctx->values ? ctx->values + (size_t)b * (size_t)ctx->keys : NULL;
return rb_order_compare_rows(ctx, ctx->rows[a], ctx->rows[b], va, vb);
}
static void rb_apply_order_by(result_builder_t *rb, const cbm_return_clause_t *ret) {
if (ret->order_key_count == 0) {
return;
}
/* Resolve every key up front; an unresolvable key is skipped, matching the
* single-key forgiveness (sorting on what can be resolved beats dropping
* the whole ORDER BY). */
int cols[CBM_CYPHER_ORDER_KEYS_MAX];
bool numeric[CBM_CYPHER_ORDER_KEYS_MAX];
bool descs[CBM_CYPHER_ORDER_KEYS_MAX];
int keys = 0;
for (int k = 0; k < ret->order_key_count; k++) {
int order_col = rb_find_order_column(rb, ret, ret->order_keys[k]);
if (order_col < 0) {
continue;
}
cols[keys] = order_col;
numeric[keys] = rb_is_numeric_column(rb, order_col);
descs[keys] = ret->order_descs[k];
keys++;
}
if (keys == 0 || rb->row_count < PAIR_LEN) {
return;
}
int n = rb->row_count;
rb_order_ctx_t ctx = {.cols = cols, .numeric = numeric, .descs = descs, .keys = keys};
int *idx = cbm_alloc(CBM_MEM_CLASS_OTHER, (size_t)n * sizeof(int));
const char ***rows = cbm_alloc(CBM_MEM_CLASS_OTHER, (size_t)n * sizeof(const char **));
if (!idx || !rows) {
/* No scratch memory: insertion sort in place, same comparisons. */
cbm_free(CBM_MEM_CLASS_OTHER, idx);
cbm_free(CBM_MEM_CLASS_OTHER, rows);
for (int i = SKIP_ONE; i < n; i++) {
for (int j = i; j > 0 && rb_order_compare_rows(&ctx, rb->rows[j - SKIP_ONE],
rb->rows[j], NULL, NULL) > 0;
j--) {
const char **tmp = rb->rows[j];
rb->rows[j] = rb->rows[j - SKIP_ONE];
rb->rows[j - SKIP_ONE] = tmp;
}
}
return;
}
int *values = cbm_alloc(CBM_MEM_CLASS_OTHER, (size_t)n * (size_t)keys * sizeof(int));
for (int r = 0; r < n; r++) {
idx[r] = r;
rows[r] = rb->rows[r];
for (int k = 0; values && k < keys; k++) {
values[(size_t)r * (size_t)keys + (size_t)k] =
numeric[k] ? (int)strtol(rb->rows[r][cols[k]], NULL, CBM_DECIMAL_BASE) : 0;
}
}
ctx.rows = rows;
ctx.values = values;
cypher_stable_sort(idx, n, rb_order_compare, &ctx);
for (int r = 0; r < n; r++) {
rb->rows[r] = rows[idx[r]];
}
cbm_free(CBM_MEM_CLASS_OTHER, values);
cbm_free(CBM_MEM_CLASS_OTHER, rows);
cbm_free(CBM_MEM_CLASS_OTHER, idx);
}
static void rb_apply_skip_limit(result_builder_t *rb, int skip_n, int limit,
bool limit_is_engine_budget) {
/* Skip */
if (skip_n > 0 && skip_n < rb->row_count) {
for (int i = 0; i < skip_n; i++) {
for (int c = 0; c < rb->col_count; c++) {
safe_str_free(&rb->rows[i][c]);
}
free(rb->rows[i]);
}
memmove(rb->rows, rb->rows + skip_n, (rb->row_count - skip_n) * sizeof(const char **));
rb->row_count -= skip_n;
} else if (skip_n >= rb->row_count) {
for (int i = 0; i < rb->row_count; i++) {
for (int c = 0; c < rb->col_count; c++) {
safe_str_free(&rb->rows[i][c]);
}
free(rb->rows[i]);
}
rb->row_count = 0;
}
/* Limit */
if (limit >= 0 && rb->row_count > limit) {
if (limit_is_engine_budget) {
g_cypher_truncated = true;
}
for (int i = limit; i < rb->row_count; i++) {
for (int c = 0; c < rb->col_count; c++) {
safe_str_free(&rb->rows[i][c]);
}
free(rb->rows[i]);
}
rb->row_count = limit;
}
}
/* A row's DISTINCT identity: every column, length-prefixed so no value can
* run into the next — equal keys exactly when every column is equal. Built in
* *buf (grown as needed); NULL when out of memory. */
static const char *rb_row_key(const result_builder_t *rb, const char **row, char **buf,
size_t *cap) {
size_t need = SKIP_ONE;
for (int c = 0; c < rb->col_count; c++) {
need += strlen(row[c]) + CBM_SZ_32;
}
if (need > *cap) {
char *grown = cbm_realloc(CBM_MEM_CLASS_OTHER, *buf, need);
if (!grown) {
return NULL;
}
*buf = grown;
*cap = need;
}
size_t used = 0;
for (int c = 0; c < rb->col_count; c++) {
size_t len = strlen(row[c]);
char prefix[CBM_SZ_32];
int prefix_len = snprintf(prefix, sizeof(prefix), "%zu:", len);
if (prefix_len <= 0 || (size_t)prefix_len >= sizeof(prefix) ||
(size_t)prefix_len + len >= *cap - used) {
return NULL; /* cannot happen: `need` reserved this */
}
memcpy(*buf + used, prefix, (size_t)prefix_len);
used += (size_t)prefix_len;
memcpy(*buf + used, row[c], len);
used += len;
}
(*buf)[used] = '\0';
return *buf;
}
/* Whether row i equals one of the first `kept` rows, column by column. */
static bool rb_row_seen_before(const result_builder_t *rb, int i, int kept) {
for (int j = 0; j < kept; j++) {
bool same = true;
for (int c = 0; c < rb->col_count && same; c++) {
same = strcmp(rb->rows[i][c], rb->rows[j][c]) == 0;
}
if (same) {
return true;
}
}
return false;
}
static void rb_apply_distinct(result_builder_t *rb) {
if (rb->row_count <= SKIP_ONE) {
return;
}
cypher_key_index_t seen = {0};
char *key_buf = NULL;
size_t key_cap = 0;
int kept = 0;
for (int i = 0; i < rb->row_count; i++) {
const char *key = rb_row_key(rb, rb->rows[i], &key_buf, &key_cap);
seen.failed = seen.failed || !key;
int found = key_index_find(&seen, key);
bool dup = found == KEY_INDEX_UNKNOWN ? rb_row_seen_before(rb, i, kept) : found >= 0;
if (!dup) {
key_index_add(&seen, key, kept);
if (kept != i) {
rb->rows[kept] = rb->rows[i];
}
kept++;
} else {
for (int c = 0; c < rb->col_count; c++) {
safe_str_free(&rb->rows[i][c]);
}
free(rb->rows[i]);
}
}
rb->row_count = kept;
key_index_free(&seen);
cbm_free(CBM_MEM_CLASS_OTHER, key_buf);
}
static void rb_free(result_builder_t *rb) {
for (int i = 0; i < rb->row_count; i++) {
for (int c = 0; c < rb->col_count; c++) {
safe_str_free(&rb->rows[i][c]);
}
free(rb->rows[i]);
}
free(rb->rows);
for (int i = 0; i < rb->col_count; i++) {
safe_str_free(&rb->columns[i]);
}
free(rb->columns);
}
/* ── Get projection value for a binding + return item ─────────── */
/* Build a JSON list of a node's non-null property keys: keys(n). */
static const char *node_keys_list(const cbm_node_t *n, char *buf, size_t buf_sz) {
const struct {
const char *k;
bool present;
} ks[] = {
{"name", n->name && n->name[0]},
{"qualified_name", n->qualified_name && n->qualified_name[0]},
{"label", n->label && n->label[0]},
{"file_path", n->file_path && n->file_path[0]},
{"start_line", n->start_line > 0},
{"end_line", n->end_line > 0},
};
size_t pos = 0;
bool first = true;
if (pos < buf_sz - SKIP_ONE) {
buf[pos++] = '[';
}
for (size_t i = 0; i < sizeof(ks) / sizeof(ks[0]) && pos < buf_sz - SKIP_ONE; i++) {
if (!ks[i].present) {
continue;
}
int w = snprintf(buf + pos, buf_sz - pos, "%s\"%s\"", first ? "" : ",", ks[i].k);
if (w < 0 || (size_t)w >= buf_sz - pos) {
break;
}
pos += (size_t)w;
first = false;
}
if (pos < buf_sz - SKIP_ONE) {
buf[pos++] = ']';
}
buf[pos] = '\0';
return buf;
}
/* Resolve a function argument to its string value (literal or var.prop). */
static const char *eval_func_arg(binding_t *b, const cbm_func_arg_t *a) {
if (a->literal) {
return a->literal;
}
return binding_get_virtual(b, a->variable, a->property);
}
/* Evaluate a multi-argument scalar function into func_buf (or a direct value). */
static const char *eval_multiarg_func(binding_t *b, const cbm_return_item_t *item, char *buf,
size_t bufsz) {
const char *f = item->func;
int n = item->arg_count;
if (strcmp(f, "coalesce") == 0) {
for (int i = 0; i < n; i++) {
const char *v = eval_func_arg(b, &item->args[i]);
if (v && v[0]) {
return v;
}
}
return "";
}
if (strcmp(f, "substring") == 0 && n >= 2) {
const char *s = eval_func_arg(b, &item->args[0]);
long start = strtol(eval_func_arg(b, &item->args[1]), NULL, CBM_DECIMAL_BASE);
size_t slen = strlen(s);
if (start < 0 || (size_t)start >= slen) {
return "";
}
size_t take = slen - (size_t)start;
if (n >= 3) {
long len = strtol(eval_func_arg(b, &item->args[2]), NULL, CBM_DECIMAL_BASE);
if (len < 0) {
len = 0;
}
if ((size_t)len < take) {
take = (size_t)len;
}
}
if (take >= bufsz) {
take = bufsz - SKIP_ONE;
}
memcpy(buf, s + start, take);
buf[take] = '\0';
return buf;
}
if ((strcmp(f, "left") == 0 || strcmp(f, "right") == 0) && n >= 2) {
const char *s = eval_func_arg(b, &item->args[0]);
long k = strtol(eval_func_arg(b, &item->args[1]), NULL, CBM_DECIMAL_BASE);
if (k < 0) {
k = 0;
}
size_t slen = strlen(s);
size_t take = (size_t)k < slen ? (size_t)k : slen;
if (take >= bufsz) {
take = bufsz - SKIP_ONE;
}
memcpy(buf, (strcmp(f, "left") == 0) ? s : s + (slen - take), take);
buf[take] = '\0';
return buf;
}
if (strcmp(f, "replace") == 0 && n >= 3) {
const char *s = eval_func_arg(b, &item->args[0]);
const char *from = eval_func_arg(b, &item->args[1]);
const char *to = eval_func_arg(b, &item->args[2]);
size_t fromlen = strlen(from);
size_t tolen = strlen(to);
size_t pos = 0;
const char *pp = s;
if (fromlen == 0) {
snprintf(buf, bufsz, "%s", s);
return buf;
}
while (*pp && pos < bufsz - SKIP_ONE) {
if (strncmp(pp, from, fromlen) == 0) {
size_t cpy = tolen;
if (pos + cpy >= bufsz) {
cpy = bufsz - SKIP_ONE - pos;
}
memcpy(buf + pos, to, cpy);
pos += cpy;
pp += fromlen;
} else {
buf[pos++] = *pp++;
}
}
buf[pos] = '\0';
return buf;
}
return ""; /* wrong arity → null */
}
static const char *project_item(binding_t *b, cbm_return_item_t *item, char *func_buf,
size_t buf_sz) {
if (item->kase) {
return eval_case_expr(item->kase, b);
}
if (item->args) {
return eval_multiarg_func(b, item, func_buf, buf_sz);
}
/* Entity-introspection functions operate on the bound node/edge itself,
* not on a scalar property value. */
if (item->func) {
if (strcmp(item->func, "labels") == 0) {
cbm_node_t *n = binding_get(b, item->variable);
if (n && n->label) {
snprintf(func_buf, buf_sz, "[\"%s\"]", n->label);
return func_buf;
}
return "[]";
}
if (strcmp(item->func, "type") == 0) {
cbm_edge_t *e = binding_get_edge(b, item->variable);
return (e && e->type) ? e->type : "";
}
if (strcmp(item->func, "id") == 0) {
cbm_node_t *n = binding_get(b, item->variable);
if (n) {
snprintf(func_buf, buf_sz, "%lld", (long long)n->id);
return func_buf;
}
cbm_edge_t *e = binding_get_edge(b, item->variable);
if (e) {
snprintf(func_buf, buf_sz, "%lld", (long long)e->id);
return func_buf;
}
return "";
}
if (strcmp(item->func, "keys") == 0) {
cbm_node_t *n = binding_get(b, item->variable);
return n ? node_keys_list(n, func_buf, buf_sz) : "[]";
}
if (strcmp(item->func, "properties") == 0) {
cbm_node_t *n = binding_get(b, item->variable);
if (n) {
return n->properties_json ? n->properties_json : "{}";
}
cbm_edge_t *e = binding_get_edge(b, item->variable);
if (e) {
return e->properties_json ? e->properties_json : "{}";
}
return "{}";
}
}
const char *raw = binding_get_virtual(b, item->variable, item->property);
if (is_scalar_value_func(item->func)) {
return apply_string_func(item->func, raw, func_buf, buf_sz);
}
/* Direct node/edge fields live in the binding until this row has been
* copied by rb_add_row. Keep those allocation-backed values intact: the
* fixed per-column scratch buffer exists only to stabilize computed and
* JSON-derived rotating-buffer values. Copying every value through it
* silently clipped long qualified names and paths to 511 bytes before the
* MCP response budget or prefix directory ever saw them. */
for (int i = 0; raw && raw[0] && i < b->var_count; i++) {
const cbm_node_t *node = &b->var_nodes[i];
if (raw == node->project || raw == node->label || raw == node->name ||
raw == node->qualified_name || raw == node->file_path || raw == node->properties_json) {
return raw;
}
}
for (int i = 0; raw && raw[0] && i < b->edge_var_count; i++) {
const cbm_edge_t *edge = &b->edge_vars[i];
if (raw == edge->project || raw == edge->type || raw == edge->properties_json) {
return raw;
}
}
/* Copy into the caller's per-column buffer. `raw` may point to node_prop's
* rotating scratch buffer, which the next column's projection would overwrite
* before rb_add_row copies the assembled row — aliasing every such column to
* the last value read. The per-column func_buf gives each column stable storage. */
if (raw && raw != func_buf && raw[0]) {
size_t len = strlen(raw);
if (len >= buf_sz) {
len = buf_sz - SKIP_ONE;
}
memcpy(func_buf, raw, len);
func_buf[len] = '\0';
return func_buf;
}
return raw ? raw : "";
}
/* Check if a function name is an aggregate */
static bool is_aggregate_func(const char *func) {
return func &&
(strcmp(func, "COUNT") == 0 || strcmp(func, "SUM") == 0 || strcmp(func, "AVG") == 0 ||
strcmp(func, "MIN") == 0 || strcmp(func, "MAX") == 0 || strcmp(func, "COLLECT") == 0);
}
/* Grow a string list for one more entry at `idx`: the capacity doubles at
* every power of two, so n appends cost O(n) copying, not O(n^2). */
static char **string_list_reserve(char **list, int idx) {
if (idx > 0 && (idx & (idx - SKIP_ONE)) != 0) {
return list; /* capacity is the next power of two above idx */
}
return safe_realloc(list, (size_t)(idx ? idx * PAIR_LEN : SKIP_ONE) * sizeof(char *));
}
enum { DISTINCT_SET_MIN = 16 }; /* below this a set is scanned, not hashed */
/* Append `val` to a string list only if not already present — i.e. maintain a
* set of distinct values. Used by COUNT(DISTINCT x) (#239). Past
* DISTINCT_SET_MIN values the membership test goes through *set, whose keys
* are the list's own strings; a set that cannot be built stays a scan. */
static void distinct_list_add(char ***list, int *count, CBMHashTable **set, const char *val) {
if (*set) {
if (cbm_ht_has(*set, val)) {
return;
}
} else {
for (int i = 0; i < *count; i++) {
if (strcmp((*list)[i], val) == 0) {
return;
}
}
}
int idx = *count;
*list = string_list_reserve(*list, idx);
char *copy = *list ? heap_strdup(val) : NULL;
if (!copy) {
/* Out of memory: keep a consistent (possibly emptied) set. */
if (!*list) {
*count = 0;
if (*set) {
cbm_ht_free(*set);
*set = NULL;
}
}
return;
}
(*list)[idx] = copy;
(*count)++;
if (*set) {
(void)cbm_ht_set(*set, (*list)[idx], (void *)SKIP_ONE);
} else if (*count >= DISTINCT_SET_MIN) {
*set = cbm_ht_create(CBM_SZ_64);
for (int i = 0; *set && i < *count; i++) {
(void)cbm_ht_set(*set, (*list)[i], (void *)SKIP_ONE);
}
}
}
/* Resolve one WITH ORDER BY key on a projected binding. The key is either a
* projected name (`c`, or an unaliased `f.name`) or a property of a carried
* node (`g.start_line` after `WITH f AS g`, #2208): an exact projected name
* wins, otherwise `var.prop` is split and resolved on the carried node. */
static const char *order_key_value(binding_t *b, const char *key) {
const char *dot = strchr(key, '.');
if (!dot) {
return binding_get_virtual(b, key, NULL);
}
for (int i = 0; i < b->var_count; i++) {
if (strcmp(b->var_names[i], key) == 0) {
return binding_get_virtual(b, key, NULL);
}
}
char var[CBM_SZ_256];
size_t vlen = (size_t)(dot - key);
if (vlen >= sizeof(var)) {
return "";
}
memcpy(var, key, vlen);
var[vlen] = '\0';
return binding_get_virtual(b, var, dot + SKIP_ONE);
}
/* One WITH ORDER BY key comparison: numerically when both values start with a
* number, else by strcmp; positive = a after b. */
static int with_order_compare_value(const char *va, const char *vb) {
char *ea = NULL;
char *eb = NULL;
double da = strtod(va, &ea);
double db = strtod(vb, &eb);
return (ea != va && eb != vb) ? ((da > db) - (da < db)) : strcmp(va, vb);
}
/* The full comparison over the ORDER BY key list: later keys break ties,
* direction is per key (#1334). */
static int with_order_compare_bindings(const cbm_return_clause_t *wc, binding_t *a, binding_t *b) {
int cmp = 0;
for (int k = 0; k < wc->order_key_count && cmp == 0; k++) {
cmp = with_order_compare_value(order_key_value(a, wc->order_keys[k]),
order_key_value(b, wc->order_keys[k]));
if (wc->order_descs[k]) {
cmp = -cmp;
}
}
return cmp;
}
typedef struct {
const cbm_return_clause_t *wc;
char **values; /* values[i * keys + k]: owned copy of binding i's key k */
bool *numbered; /* whether strtod consumed a number from that value */
double *numbers;
} with_order_ctx_t;
/* The same comparison on values resolved once per binding. order_key_value
* may return a rotating thread-local buffer, so the values are copies. */
static int with_order_compare(const void *context, int a, int b) {
const with_order_ctx_t *ctx = context;
size_t keys = (size_t)ctx->wc->order_key_count;
int cmp = 0;
for (size_t k = 0; k < keys && cmp == 0; k++) {
size_t ia = (size_t)a * keys + k;
size_t ib = (size_t)b * keys + k;
if (ctx->numbered[ia] && ctx->numbered[ib]) {
cmp = (ctx->numbers[ia] > ctx->numbers[ib]) - (ctx->numbers[ia] < ctx->numbers[ib]);
} else {
cmp = strcmp(ctx->values[ia], ctx->values[ib]);
}
if (ctx->wc->order_descs[k]) {
cmp = -cmp;
}
}
return cmp;
}
/* Sort bindings by the ORDER BY key list (virtual variables), stably. */
static void sort_bindings(binding_t *vbindings, int count, const cbm_return_clause_t *wc) {
if (count < PAIR_LEN || wc->order_key_count <= 0) {
return;
}
size_t keys = (size_t)wc->order_key_count;
size_t cells = (size_t)count * keys;
with_order_ctx_t ctx = {.wc = wc,
.values = cbm_calloc(CBM_MEM_CLASS_OTHER, cells * sizeof(char *)),
.numbered = cbm_calloc(CBM_MEM_CLASS_OTHER, cells * sizeof(bool)),
.numbers = cbm_calloc(CBM_MEM_CLASS_OTHER, cells * sizeof(double))};
int *idx = cbm_alloc(CBM_MEM_CLASS_OTHER, (size_t)count * sizeof(int));
binding_t *sorted = cbm_alloc(CBM_MEM_CLASS_OTHER, (size_t)count * sizeof(binding_t));
bool ready = ctx.values && ctx.numbered && ctx.numbers && idx && sorted;
for (int i = 0; ready && i < count; i++) {
idx[i] = i;
for (size_t k = 0; ready && k < keys; k++) {
size_t cell = (size_t)i * keys + k;
ctx.values[cell] = cbm_mem_strdup(CBM_MEM_CLASS_OTHER,
order_key_value(&vbindings[i], wc->order_keys[k]));
ready = ctx.values[cell] != NULL;
char *end = NULL;
ctx.numbers[cell] = ready ? strtod(ctx.values[cell], &end) : 0;
ctx.numbered[cell] = ready && end != ctx.values[cell];
}
}
if (ready) {
cypher_stable_sort(idx, count, with_order_compare, &ctx);
for (int i = 0; i < count; i++) {
sorted[i] = vbindings[idx[i]];
}
memcpy(vbindings, sorted, (size_t)count * sizeof(binding_t));
} else {
/* No scratch memory: insertion sort in place, same comparisons. */
for (int i = SKIP_ONE; i < count; i++) {
for (int j = i; j > 0 && with_order_compare_bindings(wc, &vbindings[j - SKIP_ONE],
&vbindings[j]) > 0;
j--) {
binding_t tmp = vbindings[j];
vbindings[j] = vbindings[j - SKIP_ONE];
vbindings[j - SKIP_ONE] = tmp;
}
}
}
for (size_t c = 0; ctx.values && c < cells; c++) {
cbm_free(CBM_MEM_CLASS_OTHER, ctx.values[c]);
}
cbm_free(CBM_MEM_CLASS_OTHER, ctx.values);
cbm_free(CBM_MEM_CLASS_OTHER, ctx.numbered);
cbm_free(CBM_MEM_CLASS_OTHER, ctx.numbers);
cbm_free(CBM_MEM_CLASS_OTHER, idx);
cbm_free(CBM_MEM_CLASS_OTHER, sorted);
}
/* Apply skip and limit to a binding array, freeing discarded entries */
static void bindings_skip_limit(binding_t *vbindings, int *count, int skip, int limit) {
if (skip > 0 && skip < *count) {
for (int i = 0; i < skip; i++) {
binding_free(&vbindings[i]);
}
memmove(vbindings, vbindings + skip, (*count - skip) * sizeof(binding_t));
*count -= skip;
} else if (skip >= *count) {
for (int i = 0; i < *count; i++) {
binding_free(&vbindings[i]);
}
*count = 0;
}
if (limit >= 0 && *count > limit) {
for (int i = limit; i < *count; i++) {
binding_free(&vbindings[i]);
}
*count = limit;
}
}
/* Sort, skip, and limit binding array in-place */
static void with_sort_skip_limit(const cbm_return_clause_t *wc, binding_t *vbindings, int *vcount) {
if (wc->order_key_count > 0) {
sort_bindings(vbindings, *vcount, wc);
}
bindings_skip_limit(vbindings, vcount, wc->skip, wc->limit);
}
/* Resolve the alias or compute a default name for a WITH/RETURN item */
static const char *resolve_item_alias(const cbm_return_item_t *item, char *name_buf,
size_t buf_sz) {
if (item->alias) {
return item->alias;
}
if (item->property) {
snprintf(name_buf, buf_sz, "%s.%s", item->variable, item->property);
} else {
snprintf(name_buf, buf_sz, "%s", item->variable);
}
return name_buf;
}
/* ── WITH clause: project bindings through aggregation or rename ── */
/* WITH aggregation group entry */
typedef struct {
char group_key[CBM_SZ_1K];
const char **group_vals;
double *sums;
int *counts;
double *mins, *maxs;
char ***distinct_lists; /* per-item set of seen values for COUNT(DISTINCT) */
int *distinct_n; /* per-item distinct count (#239) */
CBMHashTable **distinct_sets; /* per-item hash over distinct_lists (lazy) */
cbm_node_t *group_nodes; /* per-item carried node (deep copy; id 0 = not a node) */
} with_agg_t;
/* A WITH item that is a bare, bound node variable (`WITH f`, `WITH f AS g`)
* carries the node itself, not a scalar: return that node, else NULL. Property
* items, functions (labels/id/keys/...) and unbound OPTIONAL vars (id 0) stay
* scalar. The carried node keeps every field, so a later g.<prop> resolves
* exactly as it would without the WITH (#2208). */
static const cbm_node_t *with_item_carried_node(const cbm_return_item_t *item, binding_t *b) {
if (item->func || item->property || !item->variable) {
return NULL;
}
const cbm_node_t *n = binding_get(b, item->variable);
return (n && n->id > 0) ? n : NULL;
}
/* Name a carried node is bound under: the AST-owned alias or variable, which
* outlives every binding of the query (binding_set does not copy the name). */
static const char *with_item_node_alias(const cbm_return_item_t *item) {
return item->alias ? item->alias : item->variable;
}
/* Build a group key from non-aggregate WITH items */
static int with_agg_build_key(cbm_return_clause_t *wc, binding_t *b, char *key, size_t key_sz) {
int kl = 0;
for (int ci = 0; ci < wc->count; ci++) {
if (is_aggregate_func(wc->items[ci].func)) {
continue;
}
char vbuf[CBM_SZ_512];
const cbm_node_t *gn = with_item_carried_node(&wc->items[ci], b);
if (gn) {
/* Group a node by identity, never by its (non-unique) name. */
snprintf(vbuf, sizeof(vbuf), "#%lld", (long long)gn->id);
}
const char *v = gn ? vbuf : project_item(b, &wc->items[ci], vbuf, sizeof(vbuf));
kl += snprintf(key + kl, key_sz - (size_t)kl, "%s|", v);
if (kl >= (int)key_sz) {
kl = (int)key_sz - SKIP_ONE;
}
}
return kl;
}
/* Find or create an aggregation group. Returns index. */
static int with_agg_find_or_create(with_agg_t **aggs, int *agg_cnt, int *agg_cap,
cypher_key_index_t *groups, cbm_return_clause_t *wc,
binding_t *b, const char *key) {
int existing = key_index_find(groups, key);
for (int a = 0; existing == KEY_INDEX_UNKNOWN && a < *agg_cnt; a++) {
if (strcmp((*aggs)[a].group_key, key) == 0) {
existing = a;
}
}
if (existing >= 0) {
return existing;
}
if (*agg_cnt >= *agg_cap) {
*agg_cap *= PAIR_LEN;
*aggs = safe_realloc(*aggs, *agg_cap * sizeof(with_agg_t));
}
int found = (*agg_cnt)++;
snprintf((*aggs)[found].group_key, sizeof((*aggs)[found].group_key), "%s", key);
key_index_add(groups, (*aggs)[found].group_key, found);
(*aggs)[found].group_vals = calloc(wc->count, sizeof(const char *));
(*aggs)[found].sums = calloc(wc->count, sizeof(double));
(*aggs)[found].counts = calloc(wc->count, sizeof(int));
(*aggs)[found].mins = calloc(wc->count, sizeof(double));
(*aggs)[found].maxs = calloc(wc->count, sizeof(double));
(*aggs)[found].distinct_lists = calloc(wc->count, sizeof(char **));
(*aggs)[found].distinct_n = calloc(wc->count, sizeof(int));
(*aggs)[found].distinct_sets =
cbm_calloc(CBM_MEM_CLASS_OTHER, (size_t)wc->count * sizeof(CBMHashTable *));
(*aggs)[found].group_nodes = calloc(wc->count, sizeof(cbm_node_t));
for (int ci = 0; ci < wc->count; ci++) {
(*aggs)[found].mins[ci] = CYP_DBL_MAX;
(*aggs)[found].maxs[ci] = -CYP_DBL_MAX;
}
for (int ci = 0; ci < wc->count; ci++) {
if (is_aggregate_func(wc->items[ci].func)) {
(*aggs)[found].group_vals[ci] = heap_strdup("0");
continue;
}
char vbuf[CBM_SZ_512];
const char *v = project_item(b, &wc->items[ci], vbuf, sizeof(vbuf));
(*aggs)[found].group_vals[ci] = heap_strdup(v);
const cbm_node_t *gn = with_item_carried_node(&wc->items[ci], b);
if (gn) {
node_deep_copy(&(*aggs)[found].group_nodes[ci], gn);
}
}
return found;
}
/* Accumulate aggregation values for a binding */
static void with_agg_accumulate(with_agg_t *agg, cbm_return_clause_t *wc, binding_t *b) {
for (int ci = 0; ci < wc->count; ci++) {
if (!is_aggregate_func(wc->items[ci].func)) {
continue;
}
agg->counts[ci]++;
const char *raw = binding_get_virtual(b, wc->items[ci].variable, wc->items[ci].property);
if (wc->items[ci].distinct && strcmp(wc->items[ci].func, "COUNT") == 0) {
distinct_list_add(&agg->distinct_lists[ci], &agg->distinct_n[ci],
&agg->distinct_sets[ci], raw);
}
double dv = strtod(raw, NULL);
agg->sums[ci] += dv;
if (dv < agg->mins[ci]) {
agg->mins[ci] = dv;
}
if (dv > agg->maxs[ci]) {
agg->maxs[ci] = dv;
}
}
}
/* Format a WITH aggregation value into buf */
static void with_agg_format(const char *func, with_agg_t *agg, int ci, char *buf, size_t buf_sz) {
if (strcmp(func, "SUM") == 0) {
snprintf(buf, buf_sz, "%.10g", agg->sums[ci]);
} else if (strcmp(func, "AVG") == 0) {
snprintf(buf, buf_sz, "%.10g", agg->counts[ci] > 0 ? agg->sums[ci] / agg->counts[ci] : 0.0);
} else if (strcmp(func, "MIN") == 0) {
snprintf(buf, buf_sz, "%.10g", agg->mins[ci]);
} else if (strcmp(func, "MAX") == 0) {
snprintf(buf, buf_sz, "%.10g", agg->maxs[ci]);
} else {
snprintf(buf, buf_sz, "%d", agg->counts[ci]);
}
}
/* Add a scalar virtual variable binding for one WITH item. The value lives in
* .name; the owned alias string (var_names points at it) lives in .project,
* which no property accessor exposes. It used to live in .qualified_name, so
* alias.qualified_name / keys(alias) returned the variable name as data (#2208). */
static void with_add_vbinding_var(binding_t *vb, const char *alias, const char *val) {
cbm_node_t vn = {.name = heap_strdup(val), .project = heap_strdup(alias)};
if (vb->var_count < CYP_BUF_16) {
vb->var_names[vb->var_count] = vn.project;
vb->var_nodes[vb->var_count] = vn;
vb->var_count++;
}
}
/* Free with_agg_t array */
static void with_agg_free(with_agg_t *aggs, int agg_cnt, int item_count) {
for (int a = 0; a < agg_cnt; a++) {
for (int ci = 0; ci < item_count; ci++) {
safe_str_free(&aggs[a].group_vals[ci]);
if (aggs[a].distinct_sets && aggs[a].distinct_sets[ci]) {
cbm_ht_free(aggs[a].distinct_sets[ci]);
}
if (aggs[a].distinct_lists && aggs[a].distinct_lists[ci]) {
for (int j = 0; j < aggs[a].distinct_n[ci]; j++) {
free(aggs[a].distinct_lists[ci][j]);
}
free(aggs[a].distinct_lists[ci]);
}
}
free(aggs[a].group_vals);
free(aggs[a].sums);
free(aggs[a].counts);
free(aggs[a].mins);
free(aggs[a].maxs);
free(aggs[a].distinct_lists);
free(aggs[a].distinct_n);
cbm_free(CBM_MEM_CLASS_OTHER, aggs[a].distinct_sets);
if (aggs[a].group_nodes) {
for (int ci = 0; ci < item_count; ci++) {
node_fields_free(&aggs[a].group_nodes[ci]);
}
}
free(aggs[a].group_nodes);
}
free(aggs);
}
/* WITH as a consumer of the binding stream (execute_chunk): aggregation groups
* and projected rows accumulate across feeds in input order, so a chunked run
* keeps the first-seen group order and row order of a single pass. */
typedef struct {
cbm_return_clause_t *wc; /* NULL: the query has no WITH */
bool has_agg;
bool fed_any;
cbm_store_t *store; /* the first fed binding's store */
with_agg_t *aggs;
int agg_cnt;
int agg_cap;
cypher_key_index_t groups;
binding_t *vbindings; /* simple projection: one row per binding (mem core, class OTHER) */
int vcount;
int vcap;
bool oom; /* a row buffer could not grow: the query fails */
} with_sink_t;
static void with_sink_init(with_sink_t *s, cbm_return_clause_t *wc) {
memset(s, 0, sizeof(*s));
s->wc = wc;
if (!wc) {
return;
}
for (int i = 0; i < wc->count; i++) {
if (is_aggregate_func(wc->items[i].func)) {
s->has_agg = true;
break;
}
}
if (s->has_agg) {
s->agg_cap = CBM_SZ_256;
s->aggs = calloc(s->agg_cap, sizeof(with_agg_t));
}
}
/* One projected row per aggregation group, in first-seen group order. */
static binding_t *with_agg_rows(with_sink_t *s, int *vcount) {
cbm_return_clause_t *wc = s->wc;
with_agg_t *aggs = s->aggs;
int agg_cnt = s->agg_cnt;
binding_t *vbindings =
cbm_alloc(CBM_MEM_CLASS_OTHER, ((size_t)agg_cnt + SKIP_ONE) * sizeof(binding_t));
if (!vbindings) {
return NULL;
}
for (int a = 0; a < agg_cnt; a++) {
binding_t vb = {0};
/* Carry the store so node_prop can re-fetch a carried node's properties
* (and compute in_degree/out_degree) on the projected virtual binding. */
vb.store = s->store;
for (int ci = 0; ci < wc->count; ci++) {
char name_buf[CBM_SZ_256];
const char *alias = resolve_item_alias(&wc->items[ci], name_buf, sizeof(name_buf));
if (is_aggregate_func(wc->items[ci].func)) {
char vbuf[CBM_SZ_64];
if (wc->items[ci].distinct && strcmp(wc->items[ci].func, "COUNT") == 0) {
snprintf(vbuf, sizeof(vbuf), "%d", aggs[a].distinct_n[ci]); /* #239 */
} else {
with_agg_format(wc->items[ci].func, &aggs[a], ci, vbuf, sizeof(vbuf));
}
with_add_vbinding_var(&vb, alias, vbuf);
} else if (aggs[a].group_nodes[ci].id > 0) {
binding_set(&vb, with_item_node_alias(&wc->items[ci]), &aggs[a].group_nodes[ci]);
} else {
with_add_vbinding_var(&vb, alias, aggs[a].group_vals[ci]);
}
}
vbindings[(*vcount)++] = vb;
}
return vbindings;
}
/* Execute WITH simple (non-aggregate) projection */
static void execute_with_simple(cbm_return_clause_t *wc, binding_t *bindings, int bind_count,
binding_t *vbindings, int *vcount) {
for (int bi = 0; bi < bind_count; bi++) {
binding_t vb = {0};
vb.store = bindings[bi].store; /* so node_prop can re-fetch / compute on the projection */
for (int ci = 0; ci < wc->count; ci++) {
char name_buf[CBM_SZ_256];
const char *alias = resolve_item_alias(&wc->items[ci], name_buf, sizeof(name_buf));
const cbm_node_t *carried = with_item_carried_node(&wc->items[ci], &bindings[bi]);
if (carried) {
binding_set(&vb, with_item_node_alias(&wc->items[ci]), carried);
continue;
}
char func_buf[CBM_SZ_512];
const char *val =
project_item(&bindings[bi], &wc->items[ci], func_buf, sizeof(func_buf));
with_add_vbinding_var(&vb, alias, val);
}
vbindings[(*vcount)++] = vb;
}
}
static void with_sink_feed(with_sink_t *s, binding_t *bindings, int bind_count) {
if (bind_count > 0 && !s->fed_any) {
s->fed_any = true;
s->store = bindings[0].store;
}
if (!s->has_agg) {
if (s->vcount + bind_count + SKIP_ONE > s->vcap) {
int need = s->vcount + bind_count + SKIP_ONE;
int cap = s->vcap * CYP_GROWTH_2 > need ? s->vcap * CYP_GROWTH_2 : need;
binding_t *grown =
cbm_realloc(CBM_MEM_CLASS_OTHER, s->vbindings, (size_t)cap * sizeof(binding_t));
if (!grown) {
s->oom = true; /* the query fails rather than lose rows */
return;
}
s->vbindings = grown;
s->vcap = cap;
}
execute_with_simple(s->wc, bindings, bind_count, s->vbindings, &s->vcount);
return;
}
for (int bi = 0; bi < bind_count; bi++) {
char key[CBM_SZ_1K] = "";
with_agg_build_key(s->wc, &bindings[bi], key, sizeof(key));
int found = with_agg_find_or_create(&s->aggs, &s->agg_cnt, &s->agg_cap, &s->groups, s->wc,
&bindings[bi], key);
with_agg_accumulate(&s->aggs[found], s->wc, &bindings[bi]);
}
}
/* Release a WITH sink that will not be finished (a failed query). */
static void with_sink_free(with_sink_t *s) {
if (s->has_agg) {
key_index_free(&s->groups);
with_agg_free(s->aggs, s->agg_cnt, s->wc->count);
}
for (int i = 0; i < s->vcount; i++) {
binding_free(&s->vbindings[i]);
}
cbm_free(CBM_MEM_CLASS_OTHER, s->vbindings);
memset(s, 0, sizeof(*s));
}
/* Apply post-WITH WHERE filter */
static void filter_bindings_where(const cbm_where_clause_t *where, binding_t *vbindings,
int *vcount) {
int kept = 0;
for (int i = 0; i < *vcount; i++) {
if (eval_where(where, &vbindings[i])) {
if (kept != i) {
vbindings[kept] = vbindings[i];
}
kept++;
} else {
binding_free(&vbindings[i]);
}
}
*vcount = kept;
}
/* Build a key from a projected vbinding's value tuple (all WITH output items),
* used to detect duplicate rows for WITH DISTINCT (#238). */
static void with_proj_key(cbm_return_clause_t *wc, binding_t *b, char *key, size_t key_sz) {
int kl = 0;
key[0] = '\0';
char name_buf[CBM_SZ_256];
for (int ci = 0; ci < wc->count; ci++) {
const char *alias = resolve_item_alias(&wc->items[ci], name_buf, sizeof(name_buf));
const char *v = binding_get_virtual(b, alias, NULL);
int w = snprintf(key + kl, (kl < (int)key_sz) ? key_sz - (size_t)kl : 0, "%s|", v ? v : "");
if (w > 0) {
kl += w;
}
if (kl >= (int)key_sz) {
break; /* buffer full */
}
}
}
/* Apply WITH DISTINCT: drop projected rows whose value tuple duplicates an
* earlier one, keeping first occurrence (#238 — previously silently ignored). */
static void with_apply_distinct(cbm_return_clause_t *wc, binding_t *vbindings, int *vcount) {
cypher_key_index_t seen = {0};
int kept = 0;
for (int i = 0; i < *vcount; i++) {
char key[CBM_SZ_1K];
with_proj_key(wc, &vbindings[i], key, sizeof(key));
int found = key_index_find(&seen, key);
for (int j = 0; found == KEY_INDEX_UNKNOWN && j < kept; j++) {
char pkey[CBM_SZ_1K];
with_proj_key(wc, &vbindings[j], pkey, sizeof(pkey));
if (strcmp(key, pkey) == 0) {
found = j;
}
}
if (found >= 0) {
binding_free(&vbindings[i]);
} else {
key_index_add(&seen, key, kept);
if (kept != i) {
vbindings[kept] = vbindings[i];
}
kept++;
}
}
*vcount = kept;
key_index_free(&seen);
}
/* The WITH output once every binding has been fed: projected rows (one per
* group or per binding), de-duplicated, sorted, skipped/limited and filtered
* by the post-WITH WHERE. The caller owns the returned rows. */
static binding_t *with_sink_finish(with_sink_t *s, cbm_query_t *q, int *out_count) {
cbm_return_clause_t *wc = s->wc;
binding_t *vbindings = s->vbindings;
int vcount = s->vcount;
if (s->has_agg) {
key_index_free(&s->groups);
vcount = 0;
vbindings = with_agg_rows(s, &vcount);
with_agg_free(s->aggs, s->agg_cnt, wc->count);
}
memset(s, 0, sizeof(*s));
/* WITH DISTINCT: dedup projected rows (no-op for aggregation, which already
* collapses to one row per group). */
if (wc->distinct) {
with_apply_distinct(wc, vbindings, &vcount);
}
with_sort_skip_limit(wc, vbindings, &vcount);
if (q->post_with_where) {
filter_bindings_where(q->post_with_where, vbindings, &vcount);
}
*out_count = vcount;
return vbindings;
}
/* ── Execute a single query (no UNION recursion) ──────────────── */
/* Project RETURN * — all bound variable properties */
/* Collect all variable names from query patterns */
/* Has this variable already been collected? A query may name the same variable
* in more than one pattern, and RETURN * must give it one set of columns. */
static bool star_var_seen(const char **vars, int vc, const char *name) {
for (int i = 0; i < vc; i++) {
if (strcmp(vars[i], name) == 0) {
return true;
}
}
return false;
}
/* Collect the variables a RETURN * projects, in the order the query names them
* and with no repeats. Without the repeat check, `MATCH (f) OPTIONAL MATCH
* (f)-[:CALLS]->(g)` names f in two patterns and f gets its four columns
* twice. */
static int collect_pattern_vars(cbm_query_t *q, const char **vars, int max_vars) {
int vc = 0;
for (int pi = 0; pi < q->pattern_count; pi++) {
for (int ni = 0; ni < q->patterns[pi].node_count && vc < max_vars; ni++) {
const char *var = q->patterns[pi].nodes[ni].variable;
if (var && !star_var_seen(vars, vc, var)) {
vars[vc++] = var;
}
}
for (int ri = 0; ri < q->patterns[pi].rel_count && vc < max_vars; ri++) {
const char *var = q->patterns[pi].rels[ri].variable;
if (var && !star_var_seen(vars, vc, var)) {
vars[vc++] = var;
}
}
}
return vc;
}
/* Build star-projection columns: var.name, var.qualified_name, var.label, var.file_path */
static void build_star_columns(result_builder_t *rb, const char **vars, int vc) {
int col_n = vc * CYP_NODE_COLS;
const char *col_names[CBM_SZ_128];
for (int v = 0; v < vc; v++) {
char buf[CBM_SZ_128];
snprintf(buf, sizeof(buf), "%s.name", vars[v]);
col_names[(size_t)v * CYP_NODE_COLS] = heap_strdup(buf);
snprintf(buf, sizeof(buf), "%s.qualified_name", vars[v]);
col_names[((size_t)v * CYP_NODE_COLS) + SKIP_ONE] = heap_strdup(buf);
snprintf(buf, sizeof(buf), "%s.label", vars[v]);
col_names[((size_t)v * CYP_NODE_COLS) + PAIR_LEN] = heap_strdup(buf);
snprintf(buf, sizeof(buf), "%s.file_path", vars[v]);
col_names[((size_t)v * CYP_NODE_COLS) + CYP_TRIPLE] = heap_strdup(buf);
}
rb_set_columns(rb, col_names, col_n);
for (int i = 0; i < col_n; i++) {
safe_str_free(&col_names[i]);
}
}
/* Project one variable's 4 columns for RETURN * */
static void project_star_var(binding_t *b, const char *var, const char **vals) {
cbm_edge_t *edge = binding_get_edge(b, var);
if (edge) {
vals[0] = edge_prop(edge, "type");
vals[SKIP_ONE] = "";
vals[PAIR_LEN] = "";
vals[CYP_TRIPLE] = "";
return;
}
cbm_node_t *n = binding_get(b, var);
vals[0] = n && n->name ? n->name : "";
vals[SKIP_ONE] = n && n->qualified_name ? n->qualified_name : "";
vals[PAIR_LEN] = n && n->label ? n->label : "";
vals[CYP_TRIPLE] = n && n->file_path ? n->file_path : "";
}
/* Project one binding row for RETURN * */
static void project_star_row(binding_t *b, const char **vars, int vc, const char **vals) {
for (int v = 0; v < vc; v++) {
project_star_var(b, vars[v], vals + ((size_t)v * CYP_NODE_COLS));
}
}
/* ── RETURN as a consumer of the binding stream ───────────────────
* execute_chunk feeds the projection chunk by chunk. Each projection walks its
* input in order and keeps its state between feeds (row cap, DISTINCT set,
* aggregation groups, bindings seen), so a chunked run yields exactly the
* rows, row order, first-seen group order and truncation of a single pass
* over all bindings. A query with a WITH feeds the WITH rows once. */
typedef enum {
RET_SINK_DEFAULT, /* no RETURN: name, qualified_name, label per pattern-0 var */
RET_SINK_SIMPLE,
RET_SINK_AGG,
RET_SINK_STAR,
RET_SINK_STAR_AFTER_WITH,
} ret_sink_kind_t;
typedef struct ret_agg_entry ret_agg_entry_t;
typedef struct {
cbm_return_clause_t *ret; /* NULL for the default projection */
result_builder_t *rb;
int max_rows;
ret_sink_kind_t kind;
bool has_agg;
bool done; /* the row cap is full, or the deadline tripped: later rows add nothing */
int64_t fed; /* bindings fed so far */
int cap; /* projection row cap */
bool cap_is_engine_budget;
rb_distinct_t seen;
const char *vars[CBM_SZ_32]; /* projected variables, or the WITH names of RETURN * */
int vc;
char names[CYP_MAX_VARS][CBM_SZ_128]; /* RETURN * after WITH: computed names */
ret_agg_entry_t *aggs;
int agg_count;
int agg_cap;
cypher_key_index_t groups;
} ret_sink_t;
/* RETURN * after a WITH.
*
* The pattern's variables are out of scope by this point — the WITH replaced
* them with the names it made. Each of those names holds one value, not a
* node, so each is ONE column rather than the four a node variable gets.
*
* Reading the pattern here instead is the fault this projection exists to
* avoid: it named variables the bindings no longer hold, found nothing for
* every one of them, and answered a full result of empty strings with no
* error. */
static void ret_sink_init_star_after_with(ret_sink_t *s, const cbm_query_t *q) {
cbm_return_clause_t *wc = q->with_clause;
s->kind = RET_SINK_STAR_AFTER_WITH;
/* parse_return_or_with refuses a WITH wider than CYP_MAX_VARS, so this
* clamp cannot fire. It stays as the bound this projection relies on. */
s->vc = wc->count < CYP_MAX_VARS ? wc->count : CYP_MAX_VARS;
for (int i = 0; i < s->vc; i++) {
s->vars[i] = resolve_item_alias(&wc->items[i], s->names[i], sizeof(s->names[i]));
}
rb_set_columns(s->rb, s->vars, s->vc);
s->cap = s->max_rows;
s->cap_is_engine_budget = true;
rb_distinct_init(&s->seen, s->ret->distinct);
}
static void ret_sink_init_star(ret_sink_t *s, cbm_query_t *q) {
s->kind = RET_SINK_STAR;
s->vc = collect_pattern_vars(q, s->vars, CBM_SZ_32);
build_star_columns(s->rb, s->vars, s->vc);
cbm_return_clause_t *ret = s->ret;
s->cap = s->max_rows;
s->cap_is_engine_budget = true;
if (ret->limit >= 0 && ret->limit <= s->max_rows && ret->order_key_count == 0 &&
ret->skip <= 0) {
s->cap = ret->limit; /* DISTINCT: the cap counts distinct rows (#1364) */
s->cap_is_engine_budget = false;
}
rb_distinct_init(&s->seen, ret->distinct);
}
/* Format an aggregate value into buf based on function name */
/* Format a COLLECT list as JSON array string */
static void format_collect_list(char **items, int item_count, char *buf, size_t buf_sz) {
char cbuf[CBM_SZ_2K] = "[";
int bl = SKIP_ONE;
for (int i = 0; i < item_count; i++) {
if (i > 0) {
cbuf[bl++] = ',';
}
bl += snprintf(cbuf + bl, sizeof(cbuf) - (size_t)bl, "\"%s\"", items[i]);
if (bl >= (int)sizeof(cbuf)) {
bl = (int)sizeof(cbuf) - SKIP_ONE;
}
}
if (bl < (int)sizeof(cbuf) - SKIP_ONE) {
cbuf[bl++] = ']';
}
cbuf[bl] = '\0';
snprintf(buf, buf_sz, "%s", cbuf);
}
static void format_agg_value(const char *func, int count, double sum, double min_val,
double max_val, char ***collect_lists, int *collect_counts, int ci,
char *buf, size_t buf_sz) {
if (strcmp(func, "SUM") == 0) {
snprintf(buf, buf_sz, "%.10g", sum);
} else if (strcmp(func, "AVG") == 0) {
snprintf(buf, buf_sz, "%.10g", count > 0 ? sum / count : 0.0);
} else if (strcmp(func, "MIN") == 0) {
snprintf(buf, buf_sz, "%.10g", min_val);
} else if (strcmp(func, "MAX") == 0) {
snprintf(buf, buf_sz, "%.10g", max_val);
} else if (strcmp(func, "COLLECT") == 0) {
format_collect_list(collect_lists[ci], collect_counts[ci], buf, buf_sz);
} else {
snprintf(buf, buf_sz, "%d", count);
}
}
/* RETURN aggregation entry (ret_agg_entry_t, declared with ret_sink_t) */
struct ret_agg_entry {
char group_key[CBM_SZ_1K];
const char **group_vals;
double *sums;
int *counts;
double *mins, *maxs;
char ***collect_lists;
int *collect_counts;
CBMHashTable **distinct_sets; /* per-item hash over a COUNT(DISTINCT) list (lazy) */
};
/* Initialize a new RETURN aggregation group */
static void ret_agg_init_group(ret_agg_entry_t *entry, const char *key, int item_count,
const char **vals) {
snprintf(entry->group_key, sizeof(entry->group_key), "%s", key);
entry->group_vals = calloc(item_count, sizeof(const char *));
entry->sums = calloc(item_count, sizeof(double));
entry->counts = calloc(item_count, sizeof(int));
/* calloc: the sentinel loop below overwrites every slot, but the bound
* equality with the accumulate loop is invisible to path-sensitive
* analysis; zeroed backing keeps any modeled mismatch defined. */
entry->mins = calloc(item_count, sizeof(double));
entry->maxs = calloc(item_count, sizeof(double));
entry->collect_lists = calloc(item_count, sizeof(char **));
entry->collect_counts = calloc(item_count, sizeof(int));
entry->distinct_sets =
cbm_calloc(CBM_MEM_CLASS_OTHER, (size_t)item_count * sizeof(CBMHashTable *));
for (int ci = 0; ci < item_count; ci++) {
entry->mins[ci] = CYP_DBL_MAX;
entry->maxs[ci] = -CYP_DBL_MAX;
entry->group_vals[ci] = heap_strdup(vals[ci]);
}
}
/* Accumulate a binding into RETURN aggregation */
static bool binding_has_value(binding_t *b, const char *var, const char *prop) {
if (!var || strcmp(var, "*") == 0) {
return true;
}
char full[CBM_SZ_256];
if (prop) {
snprintf(full, sizeof(full), "%s.%s", var, prop);
} else {
snprintf(full, sizeof(full), "%s", var);
}
for (int i = 0; i < b->var_count; i++) {
if (strcmp(b->var_names[i], full) == 0) {
return true;
}
}
return binding_get_edge(b, var) != NULL || binding_get(b, var) != NULL;
}
static void ret_agg_accumulate(ret_agg_entry_t *entry, cbm_return_clause_t *ret, binding_t *b) {
for (int ci = 0; ci < ret->count; ci++) {
if (!is_aggregate_func(ret->items[ci].func)) {
continue;
}
if (strcmp(ret->items[ci].func, "COUNT") == 0 &&
!binding_has_value(b, ret->items[ci].variable, ret->items[ci].property)) {
continue;
}
entry->counts[ci]++;
const char *raw = binding_get_virtual(b, ret->items[ci].variable, ret->items[ci].property);
double dv = strtod(raw, NULL);
entry->sums[ci] += dv;
if (dv < entry->mins[ci]) {
entry->mins[ci] = dv;
}
if (dv > entry->maxs[ci]) {
entry->maxs[ci] = dv;
}
if (strcmp(ret->items[ci].func, "COLLECT") == 0) {
int idx = entry->collect_counts[ci];
entry->collect_lists[ci] = string_list_reserve(entry->collect_lists[ci], idx);
if (!entry->collect_lists[ci]) {
entry->collect_counts[ci] = 0;
continue;
}
entry->collect_lists[ci][idx] = heap_strdup(raw);
entry->collect_counts[ci]++;
} else if (ret->items[ci].distinct && strcmp(ret->items[ci].func, "COUNT") == 0) {
/* COUNT(DISTINCT x): track unique values; emit the set size (#239). */
distinct_list_add(&entry->collect_lists[ci], &entry->collect_counts[ci],
&entry->distinct_sets[ci], raw);
}
}
}
/* Free RETURN aggregation entries */
static void ret_agg_free(ret_agg_entry_t *aggs, int agg_count, int item_count) {
for (int a = 0; a < agg_count; a++) {
for (int ci = 0; ci < item_count; ci++) {
safe_str_free(&aggs[a].group_vals[ci]);
if (aggs[a].distinct_sets && aggs[a].distinct_sets[ci]) {
cbm_ht_free(aggs[a].distinct_sets[ci]);
}
for (int j = 0; j < aggs[a].collect_counts[ci]; j++) {
free(aggs[a].collect_lists[ci][j]);
}
free(aggs[a].collect_lists[ci]);
}
free(aggs[a].group_vals);
free(aggs[a].sums);
free(aggs[a].counts);
free(aggs[a].mins);
free(aggs[a].maxs);
free(aggs[a].collect_lists);
free(aggs[a].collect_counts);
cbm_free(CBM_MEM_CLASS_OTHER, aggs[a].distinct_sets);
}
free(aggs);
}
/* Execute RETURN with aggregation */
/* Build group key and projected values for one binding */
static void ret_agg_build_key(cbm_return_clause_t *ret, binding_t *b, char *key, size_t key_sz,
const char **vals, char valbufs[][CBM_SZ_512]) {
int klen = 0;
for (int ci = 0; ci < ret->count; ci++) {
if (is_aggregate_func(ret->items[ci].func)) {
vals[ci] = "0";
continue;
}
/* project_item may return its own scratch (stable static or a per-column
* buffer it copied into); persist the value in the caller-owned valbufs
* so vals[] survives until ret_agg_init_group strdup's it. */
const char *v = project_item(b, &ret->items[ci], valbufs[ci], CBM_SZ_512);
if (v != valbufs[ci]) {
snprintf(valbufs[ci], CBM_SZ_512, "%s", v ? v : "");
}
vals[ci] = valbufs[ci];
klen += snprintf(key + klen, key_sz - (size_t)klen, "%s|", vals[ci]);
if (klen >= (int)key_sz) {
klen = (int)key_sz - SKIP_ONE;
}
}
}
/* Emit one aggregated row into the result builder */
static void ret_agg_emit_row(cbm_return_clause_t *ret, ret_agg_entry_t *agg, result_builder_t *rb) {
const char *row[CBM_SZ_32];
char bufs[CBM_SZ_32][CBM_SZ_64];
for (int ci = 0; ci < ret->count; ci++) {
if (!is_aggregate_func(ret->items[ci].func)) {
row[ci] = agg->group_vals[ci];
continue;
}
if (ret->items[ci].distinct && strcmp(ret->items[ci].func, "COUNT") == 0) {
/* COUNT(DISTINCT x) — number of unique values accumulated (#239). */
snprintf(bufs[ci], sizeof(bufs[ci]), "%d", agg->collect_counts[ci]);
row[ci] = bufs[ci];
continue;
}
format_agg_value(ret->items[ci].func, agg->counts[ci], agg->sums[ci], agg->mins[ci],
agg->maxs[ci], agg->collect_lists, agg->collect_counts, ci, bufs[ci],
sizeof(bufs[ci]));
row[ci] = bufs[ci];
}
rb_add_row(rb, row);
}
/* True when every RETURN item is an aggregate, so the whole input is one group. */
static bool ret_agg_is_ungrouped(const cbm_return_clause_t *ret) {
for (int ci = 0; ci < ret->count; ci++) {
if (!is_aggregate_func(ret->items[ci].func)) {
return false;
}
}
return true;
}
/* The one row an ungrouped aggregation answers when no binding reached it
* (#2742): count and sum are 0, collect is an empty list, and avg/min/max have
* no value, rendered as "" like any other null. */
static void ret_agg_emit_empty_row(cbm_return_clause_t *ret, result_builder_t *rb) {
const char *row[CBM_SZ_32];
for (int ci = 0; ci < ret->count && ci < CBM_SZ_32; ci++) {
const char *func = ret->items[ci].func;
if (strcmp(func, "COUNT") == 0 || strcmp(func, "SUM") == 0) {
row[ci] = "0";
} else if (strcmp(func, "COLLECT") == 0) {
row[ci] = "[]";
} else {
row[ci] = "";
}
}
rb_add_row(rb, row);
}
static void ret_sink_feed_agg(ret_sink_t *s, binding_t *bindings, int bind_count) {
cbm_return_clause_t *ret = s->ret;
for (int bi = 0; bi < bind_count && !s->done; bi++) {
/* #601: a whole-graph GROUP BY visits every binding. Abort if we blow
* the wall-clock budget. */
if (((s->fed + bi) & CYPHER_DEADLINE_CHECK_MASK) == 0 && cypher_deadline_exceeded()) {
s->done = true;
break;
}
char key[CBM_SZ_1K] = "";
const char *vals[CBM_SZ_32];
char valbufs[CBM_SZ_32][CBM_SZ_512];
ret_agg_build_key(ret, &bindings[bi], key, sizeof(key), vals, valbufs);
int found = key_index_find(&s->groups, key);
for (int a = 0; found == KEY_INDEX_UNKNOWN && a < s->agg_count; a++) {
if (strcmp(s->aggs[a].group_key, key) == 0) {
found = a;
}
}
if (found < 0) {
if (s->agg_count >= s->agg_cap) {
s->agg_cap *= PAIR_LEN;
s->aggs = safe_realloc(s->aggs, s->agg_cap * sizeof(ret_agg_entry_t));
}
found = s->agg_count++;
ret_agg_init_group(&s->aggs[found], key, ret->count, vals);
key_index_add(&s->groups, s->aggs[found].group_key, found);
}
ret_agg_accumulate(&s->aggs[found], ret, &bindings[bi]);
}
}
/* Build RETURN column names from items */
static void build_return_columns(result_builder_t *rb, cbm_return_clause_t *ret) {
const char *col_names[CBM_SZ_32];
for (int i = 0; i < ret->count && i < CBM_SZ_32; i++) {
cbm_return_item_t *item = &ret->items[i];
if (item->alias) {
col_names[i] = item->alias;
} else if (item->func) {
char buf[CBM_SZ_128];
snprintf(buf, sizeof(buf), "%s(%s)", item->func, item->variable);
col_names[i] = heap_strdup(buf);
} else if (item->kase) {
col_names[i] = "CASE";
} else if (item->property) {
char buf[CBM_SZ_128];
snprintf(buf, sizeof(buf), "%s.%s", item->variable, item->property);
col_names[i] = heap_strdup(buf);
} else {
col_names[i] = item->variable;
}
}
rb_set_columns(rb, col_names, ret->count);
for (int i = 0; i < ret->count && i < CBM_SZ_32; i++) {
cbm_return_item_t *item = &ret->items[i];
if (!item->alias && (item->func || (!item->kase && item->property))) {
safe_str_free(&col_names[i]);
}
}
}
/* Row projections (simple RETURN, RETURN *, RETURN * after WITH): one row per
* binding until the row cap is full. */
static void ret_sink_feed_rows(ret_sink_t *s, binding_t *bindings, int bind_count) {
for (int bi = 0; bi < bind_count && !s->done; bi++) {
const char *vals[CBM_SZ_128];
char func_bufs[CBM_SZ_32][CBM_SZ_512];
if (s->kind == RET_SINK_SIMPLE) {
for (int ci = 0; ci < s->ret->count; ci++) {
vals[ci] = project_item(&bindings[bi], &s->ret->items[ci], func_bufs[ci],
sizeof(func_bufs[ci]));
}
} else if (s->kind == RET_SINK_STAR) {
project_star_row(&bindings[bi], s->vars, s->vc, vals);
} else {
for (int i = 0; i < s->vc; i++) {
cbm_node_t *vn = binding_get(&bindings[bi], s->vars[i]);
vals[i] = vn && vn->name ? vn->name : "";
}
}
if (!rb_add_row_capped(s->rb, &s->seen, vals, s->cap)) {
g_cypher_truncated = g_cypher_truncated || s->cap_is_engine_budget;
s->done = true;
}
}
}
/* Build default 3-column headers (name, qualified_name, label) per variable */
static void build_default_columns(result_builder_t *rb, const char **vars, int vc) {
int col_n = vc * CYP_EDGE_COLS;
const char *col_names[CYP_COL_BUF];
for (int v = 0; v < vc; v++) {
char buf[CBM_SZ_128];
snprintf(buf, sizeof(buf), "%s.name", vars[v]);
col_names[(size_t)v * CYP_EDGE_COLS] = heap_strdup(buf);
snprintf(buf, sizeof(buf), "%s.qualified_name", vars[v]);
col_names[((size_t)v * CYP_EDGE_COLS) + SKIP_ONE] = heap_strdup(buf);
snprintf(buf, sizeof(buf), "%s.label", vars[v]);
col_names[((size_t)v * CYP_EDGE_COLS) + PAIR_LEN] = heap_strdup(buf);
}
rb_set_columns(rb, col_names, col_n);
for (int i = 0; i < col_n; i++) {
safe_str_free(&col_names[i]);
}
}
/* Default projection when no RETURN clause */
static void ret_sink_init_default(ret_sink_t *s, const cbm_pattern_t *pat0) {
s->kind = RET_SINK_DEFAULT;
for (int ni = 0; ni < pat0->node_count; ni++) {
if (pat0->nodes[ni].variable) {
if (s->vc < CYP_MAX_VARS) {
s->vars[s->vc++] = pat0->nodes[ni].variable;
} else {
g_cypher_truncated = true;
}
}
}
build_default_columns(s->rb, s->vars, s->vc);
}
static void ret_sink_feed_default(ret_sink_t *s, binding_t *bindings, int bind_count) {
result_builder_t *rb = s->rb;
for (int bi = 0; bi < bind_count && rb->row_count < s->max_rows; bi++) {
const char *vals[CYP_COL_BUF];
for (int v = 0; v < s->vc; v++) {
cbm_node_t *n = binding_get(&bindings[bi], s->vars[v]);
vals[(size_t)v * CYP_EDGE_COLS] = n && n->name ? n->name : "";
vals[((size_t)v * CYP_EDGE_COLS) + SKIP_ONE] =
n && n->qualified_name ? n->qualified_name : "";
vals[((size_t)v * CYP_EDGE_COLS) + PAIR_LEN] = n && n->label ? n->label : "";
}
rb_add_row(rb, vals);
}
}
static void ret_sink_init(ret_sink_t *s, cbm_query_t *q, int max_rows, result_builder_t *rb) {
memset(s, 0, sizeof(*s));
s->ret = q->ret;
s->rb = rb;
s->max_rows = max_rows;
rb_init(rb);
cbm_return_clause_t *ret = q->ret;
if (!ret) {
ret_sink_init_default(s, &q->patterns[0]);
return;
}
for (int i = 0; i < ret->count; i++) {
if (is_aggregate_func(ret->items[i].func)) {
s->has_agg = true;
break;
}
}
if (ret->star) {
if (q->with_clause) {
ret_sink_init_star_after_with(s, q);
} else {
ret_sink_init_star(s, q);
}
return;
}
build_return_columns(rb, ret);
if (s->has_agg) {
s->kind = RET_SINK_AGG;
s->agg_cap = CBM_SZ_256;
s->aggs = calloc(s->agg_cap, sizeof(ret_agg_entry_t));
return;
}
s->kind = RET_SINK_SIMPLE;
s->cap = max_rows;
s->cap_is_engine_budget = true;
if (ret->limit >= 0 && ret->order_key_count == 0 && ret->skip <= 0) {
s->cap = ret->limit; /* DISTINCT: the cap counts distinct rows (#1364) */
s->cap_is_engine_budget = false;
}
rb_distinct_init(&s->seen, ret->distinct);
}
static void ret_sink_feed(ret_sink_t *s, binding_t *bindings, int bind_count) {
if (s->kind == RET_SINK_DEFAULT) {
ret_sink_feed_default(s, bindings, bind_count);
} else if (s->kind == RET_SINK_AGG) {
ret_sink_feed_agg(s, bindings, bind_count);
} else {
ret_sink_feed_rows(s, bindings, bind_count);
}
s->fed += bind_count;
}
/* Release the sink's own state; the projected rows stay in the builder. */
static void ret_sink_free(ret_sink_t *s) {
if (s->kind == RET_SINK_AGG) {
key_index_free(&s->groups);
ret_agg_free(s->aggs, s->agg_count, s->ret->count);
s->aggs = NULL;
s->agg_count = 0;
}
rb_distinct_free(&s->seen);
}
/* Emit the aggregation groups, then DISTINCT / ORDER BY / SKIP / LIMIT. */
static void ret_sink_finish(ret_sink_t *s) {
result_builder_t *rb = s->rb;
cbm_return_clause_t *ret = s->ret;
if (s->kind == RET_SINK_DEFAULT) {
if (s->fed > s->max_rows) {
g_cypher_truncated = true;
}
return;
}
if (s->kind == RET_SINK_AGG) {
for (int a = 0; a < s->agg_count; a++) {
ret_agg_emit_row(ret, &s->aggs[a], rb);
}
/* Without grouping keys the input is a single group even when it is
* empty; a grouped aggregation over no rows has no group to report. */
if (s->agg_count == 0 && ret_agg_is_ungrouped(ret)) {
ret_agg_emit_empty_row(ret, rb);
}
}
ret_sink_free(s);
/* The simple and star projections de-duplicate while projecting (#1364);
* only aggregate rows still need the post-pass. */
if (ret->distinct && s->has_agg && !ret->star) {
rb_apply_distinct(rb);
}
rb_apply_order_by(rb, ret);
bool limit_is_engine_budget = ret->limit < 0;
rb_apply_skip_limit(rb, ret->skip, limit_is_engine_budget ? s->max_rows : ret->limit,
limit_is_engine_budget);
}
/* Worst-case binding_t slot count for a node cross-join: one row per
* (existing binding × extra node), plus — for an OPTIONAL join with no extra
* nodes — one fallback row per existing binding, plus a trailing sentinel slot.
*
* The plain-int product bind_count * extra_count overflows to a negative/garbage
* malloc size on large graphs (the failure mode fixed for cross_join_with_rels),
* so the count is computed in size_t and rejected if it would not fit the int
* binding counter or would overflow the size_t byte size. Returns 0 and writes
* *out_n on success, CBM_NOT_FOUND on overflow. Non-static so the arithmetic
* boundary can be unit-tested directly. */
int cbm_cypher_cross_join_alloc(int bind_count, int extra_count, bool opt, size_t *out_n) {
size_t per_binding = extra_count > 0 ? (size_t)extra_count : (opt ? (size_t)SKIP_ONE : 0U);
size_t rows = (size_t)bind_count * per_binding;
if (rows > (size_t)INT_MAX) {
return CBM_NOT_FOUND; /* new_count would not fit the int binding counter */
}
size_t n = rows + SKIP_ONE;
if (n > SIZE_MAX / sizeof(binding_t)) {
return CBM_NOT_FOUND; /* alloc_n * sizeof(binding_t) would overflow size_t */
}
*out_n = n;
return 0;
}
/* Cross-join node-only pattern into existing bindings. Returns 0 on success,
* CBM_NOT_FOUND when the allocation is refused (overflow) or fails (OOM); the
* caller propagates that as a query error rather than silently skipping the
* MATCH, which would return a wrong (short) result. */
static int cross_join_nodes(binding_t **bindings, int *bind_count, cbm_node_t *extra_nodes,
int extra_count, const char *nvar, bool opt) {
size_t alloc_n = 0;
if (cbm_cypher_cross_join_alloc(*bind_count, extra_count, opt, &alloc_n) != 0) {
return CBM_NOT_FOUND; /* product overflows int/size_t: fail the query */
}
binding_t *new_bindings = malloc(alloc_n * sizeof(binding_t));
if (!new_bindings) {
return CBM_NOT_FOUND; /* OOM: propagate, don't silently skip the MATCH */
}
size_t new_count = 0;
for (int bi = 0; bi < *bind_count; bi++) {
for (int ni = 0; ni < extra_count && new_count < alloc_n; ni++) {
binding_t nb = {0};
binding_copy(&nb, &(*bindings)[bi]);
binding_set(&nb, nvar, &extra_nodes[ni]);
new_bindings[new_count++] = nb;
}
if (opt && extra_count == 0 && new_count < alloc_n) {
binding_t nb = {0};
binding_copy(&nb, &(*bindings)[bi]);
new_bindings[new_count++] = nb;
}
}
for (int bi = 0; bi < *bind_count; bi++) {
binding_free(&(*bindings)[bi]);
}
free(*bindings);
*bindings = new_bindings;
*bind_count = (int)new_count; /* new_count <= INT_MAX, guaranteed above */
return 0;
}
/* Cross-join pattern-with-rels into existing bindings */
static void cross_join_with_rels(cbm_store_t *store, cbm_pattern_t *patn, binding_t **bindings,
int *bind_count, cbm_node_t *extra_nodes, int extra_count,
const char *nvar, bool opt) {
/* size_t arithmetic: bind_count * extra_count can exceed INT_MAX on large
* graphs (e.g. an unbound `c` scanned against ~29 K `f` bindings), wrapping
* the int product negative and yielding a tiny/garbage malloc → heap OOB
* write → SIGSEGV/SIGABRT (#627). */
int new_cap = *bind_count > 0 && extra_count > 0 ? *bind_count : SKIP_ONE;
binding_t *new_bindings = malloc((size_t)new_cap * sizeof(binding_t));
if (!new_bindings) {
return; /* OOM: leave existing bindings untouched rather than corrupt */
}
int new_count = 0;
for (int bi = 0; bi < *bind_count; bi++) {
for (int ni = 0; ni < extra_count; ni++) {
binding_t nb = {0};
binding_copy(&nb, &(*bindings)[bi]);
binding_set(&nb, nvar, &extra_nodes[ni]);
binding_t *tmp = malloc(PAIR_LEN * sizeof(binding_t));
tmp[0] = nb;
int tc = SKIP_ONE;
int tcap = SKIP_ONE;
const char *tv = nvar;
expand_pattern_rels(store, patn, &tmp, &tc, &tcap, &tv, opt);
for (int ti = 0; ti < tc; ti++) {
(void)binding_out_append(&new_bindings, &new_count, &new_cap, &tmp[ti]);
}
free(tmp);
}
if (opt && extra_count == 0) {
/* OPTIONAL with no start node: keep the row, pattern vars unbound.
* The buffer was sized for a single row when extra_count == 0, so
* this write must grow it like every other writer here. */
binding_t nb = {0};
binding_copy(&nb, &(*bindings)[bi]);
(void)binding_out_append(&new_bindings, &new_count, &new_cap, &nb);
}
}
for (int bi = 0; bi < *bind_count; bi++) {
binding_free(&(*bindings)[bi]);
}
free(*bindings);
*bindings = new_bindings;
*bind_count = new_count;
}
/* Drive a single-relationship additional pattern from its ALREADY-BOUND
* terminal node, binding the unbound START var to the edge's other endpoint.
*
* Handles `OPTIONAL MATCH (c)-[:CALLS]->(f)` where `f` is bound from an earlier
* MATCH and `c` is new: scanning every node for `c` and cross-joining (a) risks
* an int-overflow OOB write on large graphs and (b) leaves `c` bound to an
* arbitrary node so a later `WHERE c IS NULL` wrongly drops every row (#627).
* Instead we scan only the bound terminal's edges and bind `c` to real
* neighbours; with OPTIONAL we keep the row with `c` unbound when there are
* none — the correct dead-code semantics. */
static void expand_from_bound_terminal(cbm_store_t *store, cbm_pattern_t *patn,
binding_t **bindings, int *bind_count, const char *start_var,
bool opt) {
cbm_rel_pattern_t *rel = &patn->rels[0];
const cbm_node_pattern_t *start_node = &patn->nodes[0];
/* The relationship is written start-[r]->terminal. To enumerate the start
* nodes reachable from the bound terminal we invert the stored direction. */
bool rel_inbound = rel->direction && strcmp(rel->direction, "inbound") == 0;
bool scan_targets =
!rel_inbound; /* (start)->(term): start = edge source = scan term's inbound */
/* Size this hop's output for BOTH writers without dropping any row: the
* materialised expansion is capped at max_new = *bind_count * 10 rows (only
* the WRITE is gated on max_new; match DETECTION below is not, so a full
* buffer never hides a real neighbour), and the OPTIONAL fallback
* emits at most one row per source (<= *bind_count). A source either matches
* (feeds the expansion) or takes the fallback, never both, so the two counts
* are additive and bounded by max_new + *bind_count. Computed in size_t so
* the product cannot overflow.
* The previous "+ SKIP_ONE" sizing tied max_new to the whole buffer, so once
* the expansion saturated it the fallback guard silently dropped every later
* OPTIONAL no-match row (a data-loss bug, not an OOB — the fallback stayed
* in-bounds behind that guard) — exactly the rows
* `OPTIONAL MATCH ... WHERE <start> IS NULL` is meant to surface. */
int new_cap = *bind_count > 0 ? *bind_count : CYP_GROWTH_10;
binding_t *new_bindings = malloc((size_t)new_cap * sizeof(binding_t));
if (!new_bindings) {
return;
}
int new_count = 0;
for (int bi = 0; bi < *bind_count; bi++) {
binding_t *b = &(*bindings)[bi];
cbm_node_t *term = binding_get(b, patn->nodes[1].variable ? patn->nodes[1].variable : "");
int match_count = 0;
if (term) {
/* Detection is decoupled from the write budget: scan every edge and
* type unconditionally so match_count reflects the true neighbour
* count, and gate only the WRITE on the ceiling (below). If detection
* stopped at max_new too, a saturated buffer would leave match_count at
* 0 for a terminal that actually has callers, and the fallback below
* would fabricate an UNBOUND "dead code" row for live code — worse than
* dropping a row. */
for (int ti = 0; ti < (rel->type_count > 0 ? rel->type_count : 1); ti++) {
cbm_edge_t *edges = NULL;
int edge_count = 0;
if (rel->type_count > 0) {
if (scan_targets) {
cbm_store_find_edges_by_target_type(store, term->id, rel->types[ti], &edges,
&edge_count);
} else {
cbm_store_find_edges_by_source_type(store, term->id, rel->types[ti], &edges,
&edge_count);
}
} else if (scan_targets) {
cbm_store_find_edges_by_target(store, term->id, &edges, &edge_count);
} else {
cbm_store_find_edges_by_source(store, term->id, &edges, &edge_count);
}
for (int ei = 0; ei < edge_count; ei++) {
int64_t sid = scan_targets ? edges[ei].source_id : edges[ei].target_id;
cbm_node_t found = {0};
if (cbm_store_find_node_by_id(store, sid, &found) != CBM_STORE_OK) {
continue;
}
if (start_node->label && !label_alt_matches(found.label, start_node->label)) {
node_fields_free(&found);
continue;
}
match_count++;
binding_t nb = {0};
binding_copy(&nb, b);
binding_take_node(&nb, start_var, &found);
if (rel->variable) {
binding_set_edge(&nb, rel->variable, &edges[ei]);
}
(void)binding_out_append(&new_bindings, &new_count, &new_cap, &nb);
node_fields_free(&found);
}
cbm_store_free_edges(edges, edge_count);
}
}
if (opt && match_count == 0) {
/* GENUINELY no matching neighbour: the scan above runs unconditionally,
* so match_count is the true neighbour count and match_count == 0 here
* means the terminal really has none. Keep the row with start_var left
* UNBOUND so `WHERE <start> IS NULL` correctly identifies the no-edge
* case; the shared growable append gives every fallback row a slot. */
binding_t nb = {0};
binding_copy(&nb, b);
(void)binding_out_append(&new_bindings, &new_count, &new_cap, &nb);
}
}
for (int bi = 0; bi < *bind_count; bi++) {
binding_free(&(*bindings)[bi]);
}
free(*bindings);
*bindings = new_bindings;
*bind_count = new_count;
}
/* Expand additional MATCH patterns (pi >= 1) */
static int expand_additional_patterns(cbm_store_t *store, cbm_query_t *q, const char *project,
int max_rows, binding_t **bindings, int *bind_count,
int *bind_cap) {
for (int pi = SKIP_ONE; pi < q->pattern_count; pi++) {
cbm_pattern_t *patn = &q->patterns[pi];
bool opt = q->pattern_optional[pi];
const char *nvar = patn->nodes[0].variable ? patn->nodes[0].variable : "_n_extra";
bool start_bound = *bind_count > 0 && binding_get(&(*bindings)[0], nvar) != NULL;
if (start_bound && patn->rel_count > 0) {
const char *tv = nvar;
expand_pattern_rels(store, patn, bindings, bind_count, bind_cap, &tv, opt);
continue;
}
/* Single-rel pattern whose START is unbound but whose TERMINAL is already
* bound: drive from the bound terminal instead of scanning all nodes for
* the start var (avoids the int-overflow OOB write and the c-IS-NULL
* corruption of #627). */
if (!start_bound && patn->rel_count == 1 && *bind_count > 0) {
const char *term_var = patn->nodes[1].variable;
bool term_bound = term_var && binding_get(&(*bindings)[0], term_var) != NULL;
if (term_bound) {
expand_from_bound_terminal(store, patn, bindings, bind_count, nvar, opt);
continue;
}
}
cbm_node_t *extra_nodes = NULL;
int extra_count = 0;
scan_pattern_nodes(store, project, &patn->nodes[0], &extra_nodes, &extra_count);
int rc = 0;
if (patn->rel_count == 0) {
rc = cross_join_nodes(bindings, bind_count, extra_nodes, extra_count, nvar, opt);
} else {
cross_join_with_rels(store, patn, bindings, bind_count, extra_nodes, extra_count, nvar,
opt);
}
cbm_store_free_nodes(extra_nodes, extra_count);
if (rc != 0) {
return rc; /* allocation refused/failed: propagate as a query error */
}
}
return 0;
}
/* ── Planner: seed a single-hop pattern from its selective end ──────────────
*
* The executor scans pattern node 0 and expands from there. Written as
* `MATCH (a)-[:CALLS]->(b) WHERE b.name = '_printk'`, that scans every node
* in the store before the filter on `b` can discard any — on an 8.5 M node
* kernel graph the query hit the execution-time limit while the anchored
* spelling `MATCH (b:Function {name:'_printk'})<-[:CALLS]-(a)` answered in
* seconds (2026-09-16 probe). A reader should not have to know which end to
* write first: when the far node carries an equality on name/qualified_name,
* an inline property, or a label and the near node carries less, the pattern
* is walked from the far end with the relationship direction inverted. The
* result set is identical; only the enumeration order changes. Restricted to
* one single-relationship pattern with an explicit RETURN, and never to an
* OPTIONAL MATCH, whose anchor is part of its meaning. */
static int cypher_cond_selectivity(const cbm_condition_t *c, const char *var) {
if (!c || !c->variable || !var || strcmp(c->variable, var) != 0 || c->negated) {
return 0;
}
/* a.x = b.y pins no value on either alias, so it seeds nothing. */
if (!c->op || strcmp(c->op, "=") != 0 || !c->property || c->rhs_variable) {
return 0;
}
return (strcmp(c->property, "name") == 0 || strcmp(c->property, "qualified_name") == 0) ? 3 : 2;
}
/* Best equality on `var` reachable through AND alone. An AND chain is linked
* along the right child (expr_chain_link), so the links are walked in a loop
* and only each link's left operand recurses. */
static int cypher_expr_selectivity(const cbm_expr_t *e, // NOLINT(misc-no-recursion)
const char *var) {
int best = 0;
while (e) {
if (e->type == EXPR_CONDITION) {
int s = cypher_cond_selectivity(&e->cond, var);
return s > best ? s : best;
}
if (e->type != EXPR_AND) {
return best; /* OR / NOT / XOR: no single equality to seed from */
}
int l = cypher_expr_selectivity(e->left, var);
if (l > best) {
best = l;
}
e = e->right;
}
return best;
}
static int cypher_node_selectivity(const cbm_node_pattern_t *n, const cbm_where_clause_t *w) {
int s = 0;
for (int i = 0; i < n->prop_count; i++) {
const char *k = n->props[i].key;
int v = (k && (strcmp(k, "name") == 0 || strcmp(k, "qualified_name") == 0)) ? 3 : 2;
if (v > s) {
s = v;
}
}
if (w && n->variable) {
int v = 0;
if (w->root) {
v = cypher_expr_selectivity(w->root, n->variable);
} else if (!w->op || strcmp(w->op, "AND") == 0) {
for (int i = 0; i < w->count; i++) {
int c = cypher_cond_selectivity(&w->conditions[i], n->variable);
if (c > v) {
v = c;
}
}
}
if (v > s) {
s = v;
}
}
if (s == 0 && n->label) {
s = 1;
}
return s;
}
static void cypher_plan_seed_from_selective_end(cbm_query_t *q) {
if (!q || q->pattern_count != 1 || !q->ret || (q->pattern_optional && q->pattern_optional[0])) {
return;
}
cbm_pattern_t *p = &q->patterns[0];
if (p->rel_count != 1 || p->node_count != 2) {
return;
}
if (cypher_node_selectivity(&p->nodes[1], q->where) <=
cypher_node_selectivity(&p->nodes[0], q->where)) {
return;
}
cbm_node_pattern_t tmp = p->nodes[0];
p->nodes[0] = p->nodes[1];
p->nodes[1] = tmp;
cbm_rel_pattern_t *r = &p->rels[0];
const char *inverted = NULL;
if (r->direction && strcmp(r->direction, "outbound") == 0) {
inverted = "inbound";
} else if (r->direction && strcmp(r->direction, "inbound") == 0) {
inverted = "outbound";
}
if (inverted) {
safe_str_free(&r->direction);
r->direction = heap_strdup(inverted);
}
}
/* ── Streamed execution ──────────────────────────────────────────────
*
* The start nodes run through the pipeline (pattern-0 hops, late WHERE, WITH,
* RETURN) in chunks of CYPHER_STREAM_CHUNK instead of materialising every
* binding of the whole set first. On the kernel graph (7.5 M nodes, 1.9 M
* CALLS edges) `MATCH (a)-[:CALLS]->(b) RETURN count(*)` held a deep-copied
* binding per start node and per expanded row at once: 23 GB RSS, killed in a
* 12 GB container. Each hop emits a binding's expansions in the order of its
* input bindings, and every consumer keeps its state between chunks, so the
* concatenated chunk outputs are the single-pass output, order included.
*
* Additional MATCH patterns keep one pass: they pick their join strategy from
* the first binding of the whole set and refuse a cross join by its size. */
#define CYPHER_STREAM_CHUNK 1024
#ifdef CBM_ENABLE_TEST_SEAMS
static _Thread_local int g_cypher_stream_chunk = 0; /* test override; 0 = default */
void cbm_cypher_test_set_stream_chunk(int start_nodes) {
g_cypher_stream_chunk = start_nodes;
}
#endif
static int cypher_stream_chunk(void) {
#ifdef CBM_ENABLE_TEST_SEAMS
if (g_cypher_stream_chunk > 0) {
return g_cypher_stream_chunk;
}
#endif
return CYPHER_STREAM_CHUNK;
}
typedef struct {
with_sink_t with;
ret_sink_t ret;
} cypher_sink_t;
static void sink_feed(cypher_sink_t *s, binding_t *bindings, int bind_count) {
if (s->with.wc) {
with_sink_feed(&s->with, bindings, bind_count);
} else {
ret_sink_feed(&s->ret, bindings, bind_count);
}
}
static void sink_finish(cypher_sink_t *s, cbm_query_t *q) {
if (s->with.wc) {
int vcount = 0;
binding_t *vbindings = with_sink_finish(&s->with, q, &vcount);
ret_sink_feed(&s->ret, vbindings, vcount);
for (int bi = 0; bi < vcount; bi++) {
binding_free(&vbindings[bi]);
}
cbm_free(CBM_MEM_CLASS_OTHER, vbindings);
}
ret_sink_finish(&s->ret);
}
static void sink_free(cypher_sink_t *s) {
if (s->with.wc) {
with_sink_free(&s->with);
}
ret_sink_free(&s->ret);
}
/* Pattern 0's start nodes in scan_pattern_nodes' order, pulled a chunk at a
* time from the store's streamed scan instead of materialised up front: a
* label alternation reads each label's scan in turn, and the inline property
* filter drops nodes as they arrive. */
typedef struct {
cbm_store_t *store;
const char *project;
const cbm_node_pattern_t *node;
char *labels; /* label alternation "A|B": strtok_r copy, else NULL */
char *labels_save;
bool labels_started;
cbm_store_node_scan_t *scan;
bool done;
bool failed; /* the scan could not be read to its end: the query fails */
} start_source_t;
/* A start-node scan failed part-way. The rows read so far must not answer the
* query as if they were all of them: record the store's error for
* cbm_cypher_execute, which fails the query with it. */
static void start_source_fail(start_source_t *src, const char *why) {
src->failed = true;
src->done = true;
snprintf(g_cypher_scan_error, sizeof(g_cypher_scan_error), "%s",
why && why[0] ? why : "unknown store error");
cbm_log_error("cypher.scan_failed", "error", g_cypher_scan_error);
}
static void start_source_open(start_source_t *src, cbm_store_t *store, const char *project,
const cbm_node_pattern_t *node) {
memset(src, 0, sizeof(*src));
src->store = store;
src->project = project;
src->node = node;
if (node->label && strchr(node->label, '|')) {
src->labels = cbm_mem_strdup(CBM_MEM_CLASS_OTHER, node->label);
if (!src->labels) {
start_source_fail(src, "out of memory");
}
return; /* one scan per label, opened as the previous one ends */
}
src->scan = cbm_store_node_scan_open(store, project, node->label);
if (!src->scan) {
start_source_fail(src, cbm_store_error(store));
}
}
/* Open the next label's scan of an alternation; false when none is left. */
static bool start_source_next_label(start_source_t *src) {
char *tok = strtok_r(src->labels_started ? NULL : src->labels, "|", &src->labels_save);
src->labels_started = true;
if (!tok) {
return false;
}
src->scan = cbm_store_node_scan_open(src->store, src->project, tok);
if (!src->scan) {
start_source_fail(src, cbm_store_error(src->store));
}
return true;
}
/* Fill out[0..max) with the next start nodes. Fewer than max only once the
* scan is exhausted or has failed. */
static int start_source_next(start_source_t *src, cbm_node_t *out, int max) {
const cbm_node_pattern_t *node = src->node;
int got = 0;
while (got < max && !src->done) {
if (!src->scan) {
if (!src->labels || !start_source_next_label(src)) {
src->done = true;
}
continue;
}
int n = 0;
if (cbm_store_node_scan_next(src->scan, out + got, max - got, &n) != CBM_STORE_OK) {
start_source_fail(src, cbm_store_error(src->store));
break;
}
if (n == 0) {
cbm_store_node_scan_close(src->scan);
src->scan = NULL;
src->done = !src->labels;
continue;
}
/* Apply inline property filters — free rejected nodes' strings */
int kept = got;
for (int i = got; i < got + n; i++) {
if (node->prop_count == 0 ||
check_inline_props(&out[i], node->props, node->prop_count, src->store)) {
if (kept != i) {
out[kept] = out[i];
}
kept++;
} else {
node_fields_free(&out[i]);
}
}
got = kept;
}
return got;
}
static void start_source_close(start_source_t *src) {
cbm_store_node_scan_close(src->scan);
cbm_free(CBM_MEM_CLASS_OTHER, src->labels);
memset(src, 0, sizeof(*src));
}
/* Release a start-node batch: the strings the store gave each node (left
* empty once moved into a binding) and the array itself. */
static void start_nodes_free(cbm_node_t *nodes, int count) {
for (int i = 0; nodes && i < count; i++) {
node_fields_free(&nodes[i]);
}
cbm_free(CBM_MEM_CLASS_OTHER, nodes);
}
/* Pull up to `chunk` start nodes (INT_MAX: all of them) into *out. */
static int pull_start_nodes(start_source_t *src, int chunk, cbm_node_t **out, int *count) {
int cap = chunk < CYPHER_STREAM_CHUNK ? chunk : CYPHER_STREAM_CHUNK;
cbm_node_t *nodes = cbm_alloc(CBM_MEM_CLASS_OTHER, (size_t)cap * sizeof(cbm_node_t));
int n = 0;
while (nodes) {
n += start_source_next(src, nodes + n, cap - n);
if (n < cap || cap == chunk) {
break; /* scan exhausted, or the chunk is full */
}
int grown_cap = cap > chunk / PAIR_LEN ? chunk : cap * PAIR_LEN;
cbm_node_t *grown =
cbm_realloc(CBM_MEM_CLASS_OTHER, nodes, (size_t)grown_cap * sizeof(cbm_node_t));
if (!grown) {
start_nodes_free(nodes, n);
nodes = NULL;
break;
}
nodes = grown;
cap = grown_cap;
}
*out = nodes;
*count = nodes ? n : 0;
return nodes ? 0 : CBM_NOT_FOUND;
}
/* Run the next chunk of start nodes through the pipeline into the sink. The
* start nodes' strings move into their bindings and are released with them.
* *start_index is the chunk's position in the whole start set. */
static int execute_chunk(cbm_store_t *store, cbm_query_t *q, const char *project, int max_rows,
start_source_t *src, int chunk, int *start_index, cypher_sink_t *sink) {
cbm_pattern_t *pat0 = &q->patterns[0];
cbm_node_t *nodes = NULL;
int node_count = 0;
if (pull_start_nodes(src, chunk, &nodes, &node_count) != 0) {
return CBM_NOT_FOUND; /* start node array refused */
}
if (src->failed) {
start_nodes_free(nodes, node_count);
return CBM_NOT_FOUND; /* the scan failed: no answer from part of it */
}
/* Build initial bindings with early WHERE */
int bind_cap = node_count;
binding_t *bindings = malloc(((size_t)bind_cap + SKIP_ONE) * sizeof(binding_t));
if (!bindings) {
start_nodes_free(nodes, node_count);
return CBM_NOT_FOUND; /* initial binding array refused */
}
int bind_count = 0;
const char *var_name = pat0->nodes[0].variable ? pat0->nodes[0].variable : CYP_ANON_HEAD_VAR;
int first = *start_index;
for (int i = 0; i < node_count; i++) {
if (((first + i) & CYPHER_DEADLINE_CHECK_MASK) == 0 && cypher_deadline_exceeded()) {
break;
}
binding_t b = {0};
b.store = store;
binding_take_node(&b, var_name, &nodes[i]);
bool pass = eval_where_partial(q->where, &b) != CYP_PARTIAL_FALSE;
if (pass) {
bindings[bind_count++] = b;
} else {
binding_free(&b);
}
}
*start_index = first + node_count;
start_nodes_free(nodes, node_count); /* + strings of nodes a deadline left untaken */
/* Expand first pattern's relationships */
expand_pattern_rels(store, pat0, &bindings, &bind_count, &bind_cap, &var_name,
q->pattern_optional[0]);
/* Additional patterns */
int rc =
expand_additional_patterns(store, q, project, max_rows, &bindings, &bind_count, &bind_cap);
if (rc == 0) {
/* Late WHERE */
if (q->where && (pat0->rel_count > 0 || q->pattern_count > SKIP_ONE)) {
filter_bindings_where(q->where, bindings, &bind_count);
}
sink_feed(sink, bindings, bind_count);
if (sink->with.oom) {
rc = CBM_NOT_FOUND; /* a WITH row buffer could not grow */
}
}
for (int bi = 0; bi < bind_count; bi++) {
binding_free(&bindings[bi]);
}
free(bindings);
return rc != 0 ? CBM_NOT_FOUND : 0; /* an allocation was refused or failed */
}
static int execute_single(cbm_store_t *store, cbm_query_t *q, const char *project, int max_rows,
result_builder_t *rb) {
cypher_plan_seed_from_selective_end(q);
cbm_pattern_t *pat0 = &q->patterns[0];
/* Step 1: Scan initial nodes, streamed */
start_source_t src;
start_source_open(&src, store, project, &pat0->nodes[0]);
cypher_sink_t sink;
with_sink_init(&sink.with, q->with_clause);
ret_sink_init(&sink.ret, q, max_rows, rb);
/* Steps 2-4 per chunk: expand, late WHERE, WITH / RETURN. The pipeline
* runs at least once, so an empty scan still reaches the additional
* patterns and the projection exactly as a single pass does. */
int chunk = q->pattern_count > SKIP_ONE ? INT_MAX : cypher_stream_chunk();
int rc = 0;
int start_index = 0;
do {
rc = execute_chunk(store, q, project, max_rows, &src, chunk, &start_index, &sink);
} while (rc == 0 && !src.done && !g_cypher_timed_out);
start_source_close(&src);
if (rc == 0) {
sink_finish(&sink, q);
} else {
sink_free(&sink);
}
return rc;
}
/* ── Main entry point ─────────────────────────────────────────── */
/* ── Is every name a RETURN or WITH item uses actually in scope? ──
*
* An unbound variable resolves to NULL and renders as "" on purpose: an
* OPTIONAL MATCH target that found no row has to project a blank rather than
* drop the row. The cost of that convention is that a name the query NEVER
* carried through looks exactly the same on screen. A typo, or a variable a
* WITH dropped, then reads as "the graph holds no such data" instead of "your
* query named something that is not there" (#1919). Same failure shape as
* #373, and the same answer: say so out loud.
*
* The check runs on the parsed query, not on the run-time bindings, and that
* is the whole trick. It asks whether the query DECLARED the name — a
* different question from whether a row happened to bind it. So the OPTIONAL
* MATCH convention above is untouched: a target that did not match is still
* declared, still legal, and still projects "".
*/
/* Cap for one query's declared names. CYP_MAX_VARS is the binding cap for
* nodes alone; a pattern also names edges, so this is the roomier of the two.
* A query that overruns it skips the check rather than guessing — a wrong
* refusal costs the caller a working query, which is worse than the silence
* this guard removes. */
enum { CYP_SCOPE_MAX_NAMES = 32 };
static bool scope_holds(const char *const *names, int count, const char *want) {
for (int i = 0; i < count; i++) {
if (names[i] && strcmp(names[i], want) == 0) {
return true;
}
}
return false;
}
/* Every name the query's patterns declare, plus an UNWIND alias.
* Answers -1 when there are more names than the cap holds. */
static int collect_declared_names(const cbm_query_t *q, const char **out, int cap) {
int n = 0;
for (int pi = 0; pi < q->pattern_count; pi++) {
const cbm_pattern_t *pat = &q->patterns[pi];
for (int ni = 0; ni < pat->node_count; ni++) {
const char *var = pat->nodes[ni].variable;
if (var && !scope_holds(out, n, var)) {
if (n >= cap) {
return -1;
}
out[n++] = var;
}
}
for (int ri = 0; ri < pat->rel_count; ri++) {
const char *var = pat->rels[ri].variable;
if (var && !scope_holds(out, n, var)) {
if (n >= cap) {
return -1;
}
out[n++] = var;
}
}
}
if (q->unwind_alias && !scope_holds(out, n, q->unwind_alias)) {
if (n >= cap) {
return -1;
}
out[n++] = q->unwind_alias;
}
return n;
}
/* What a WITH leaves behind: its alias where it made one, and the plain
* variable where it carried one through whole. `WITH f.name AS caller` leaves
* `caller` and nothing else — `f` is gone, which is the case #1919 is about. */
static int collect_with_names(const cbm_return_clause_t *wc, const char **out, int cap) {
int n = 0;
for (int i = 0; i < wc->count; i++) {
const cbm_return_item_t *item = &wc->items[i];
const char *name = NULL;
if (item->alias) {
name = item->alias;
} else if (item->variable && !item->property && !item->func) {
name = item->variable;
}
if (name && !scope_holds(out, n, name)) {
if (n >= cap) {
return -1;
}
out[n++] = name;
}
}
return n;
}
/* Build the message. It names the variable and the clause, because an error
* that does not say WHICH name is wrong sends the reader back to guessing. */
static char *scope_error(const char *var, const char *clause, const char *why) {
char buf[CBM_SZ_256];
snprintf(buf, sizeof(buf), "variable '%s' is not in scope for %s — %s", var, clause, why);
return heap_strdup(buf);
}
/* The variable this item really references, or NULL when it references none.
* Two items carry a placeholder in that field rather than a name the query
* declared: `count(*)` stores "*", and a CASE expression stores "CASE". Both
* would read as an unknown variable, so neither is checkable here. */
static const char *scope_checkable_var(const cbm_return_item_t *item) {
if (item->kase || !item->variable) {
return NULL;
}
if (strcmp(item->variable, "*") == 0) {
return NULL;
}
return item->variable;
}
/* Says which limit the query passed and how to get under it. An unnamed node
* takes no slot — except the head of the first pattern, which the engine binds
* either way — so dropping a name the query never uses is the cheap way out.
* Splitting the MATCH is NOT — every pattern of one query shares one binding,
* which is why the caller counts across all of them. Separate queries do work,
* because each gets a binding of its own. */
static char *var_capacity_error(const char *kind, int limit) {
char buf[CBM_SZ_256];
snprintf(buf, sizeof(buf),
"too many %s variables: a query can name at most %d — "
"leave the name off the ones you do not use, or run separate queries",
kind, limit);
return heap_strdup(buf);
}
/* A binding holds a fixed number of variables: CYP_MAX_VARS node variables and
* CYP_MAX_EDGE_VARS edge variables, both in plain arrays (see binding_t).
* binding_set and binding_set_edge drop anything past those without a word, so
* a query naming more variables than a binding holds cannot be answered — the
* extra names bind to nothing and project as empty strings, which reads as
* "the graph holds no such data" rather than "this query is too wide".
*
* Refuse such a query instead, before any row is touched. Bounding the input
* here is also what stops collect_declared_names below overflowing its array:
* the patterns contribute at most CYP_MAX_VARS + CYP_MAX_EDGE_VARS names, plus
* one UNWIND alias, which is well inside CYP_SCOPE_MAX_NAMES.
*
* Counts DISTINCT variables across every pattern, because they all land in the
* same binding: a multi-MATCH query shares one, and an OPTIONAL MATCH pattern
* sits in this same array (q->pattern_optional marks which). A node variable
* and an edge variable may share a name and each take a slot, because the
* binding keeps the two in separate arrays. */
static char *check_pattern_var_capacity(const cbm_query_t *q) {
/* Initialized because cppcheck cannot see that scope_holds reads only the
* node_n / edge_n entries already written, and reports the first call as a
* read of an uninitialized array. */
const char *node_vars[CYP_MAX_VARS] = {NULL};
const char *edge_vars[CYP_MAX_EDGE_VARS] = {NULL};
int node_n = 0;
int edge_n = 0;
/* The head of the first pattern always takes a node slot, named or not:
* execute_single binds it under CYP_ANON_HEAD_VAR when the query leaves it
* unnamed. Count it first, or a query with an unnamed head and CYP_MAX_VARS
* named nodes passes this check and still loses its last name in
* binding_set — the exact silence this guard exists to remove. */
if (q->pattern_count > 0 && q->patterns[0].node_count > 0 &&
!q->patterns[0].nodes[0].variable) {
node_vars[node_n++] = CYP_ANON_HEAD_VAR;
}
for (int pi = 0; pi < q->pattern_count; pi++) {
const cbm_pattern_t *pat = &q->patterns[pi];
for (int ni = 0; ni < pat->node_count; ni++) {
const char *var = pat->nodes[ni].variable;
if (!var || scope_holds(node_vars, node_n, var)) {
continue;
}
if (node_n >= CYP_MAX_VARS) {
return var_capacity_error("node", CYP_MAX_VARS);
}
node_vars[node_n++] = var;
}
for (int ri = 0; ri < pat->rel_count; ri++) {
const char *var = pat->rels[ri].variable;
if (!var || scope_holds(edge_vars, edge_n, var)) {
continue;
}
if (edge_n >= CYP_MAX_EDGE_VARS) {
return var_capacity_error("edge", CYP_MAX_EDGE_VARS);
}
edge_vars[edge_n++] = var;
}
}
return NULL;
}
/* Answers NULL when the query is fine, or a heap message naming the first
* variable that is not in scope. Checks one query; the caller walks a UNION. */
static char *check_projection_scope(const cbm_query_t *q) {
/* Runs first, so the rest of this function can trust that the query names
* no more variables than the arrays below can model. */
char *capacity_err = check_pattern_var_capacity(q);
if (capacity_err) {
return capacity_err;
}
const char *declared[CYP_SCOPE_MAX_NAMES];
int declared_n = collect_declared_names(q, declared, CYP_SCOPE_MAX_NAMES);
if (declared_n < 0) {
/* Unreachable while the capacity check above holds. Kept so the guard
* still stands if either bound ever moves. Skipping the check was the
* old behaviour, and it let an out-of-scope name through in silence. */
return NULL;
}
/* A WITH still reads the pattern variables. */
if (q->with_clause && !q->with_clause->star) {
for (int i = 0; i < q->with_clause->count; i++) {
const char *var = scope_checkable_var(&q->with_clause->items[i]);
if (var && !scope_holds(declared, declared_n, var)) {
return scope_error(var, "WITH", "no pattern in this query names it");
}
}
}
if (!q->ret || q->ret->star) {
return NULL;
}
/* A RETURN after a WITH reads only what the WITH left behind. */
const char *after_with[CYP_SCOPE_MAX_NAMES];
const char *const *scope = declared;
int scope_n = declared_n;
if (q->with_clause) {
scope_n = collect_with_names(q->with_clause, after_with, CYP_SCOPE_MAX_NAMES);
if (scope_n < 0) {
return NULL; /* unreachable: a WITH holds at most CYP_SCOPE_MAX_NAMES items */
}
scope = after_with;
}
for (int i = 0; i < q->ret->count; i++) {
const char *var = scope_checkable_var(&q->ret->items[i]);
if (var && !scope_holds(scope, scope_n, var)) {
return scope_error(var, "RETURN",
q->with_clause ? "the WITH clause did not carry it through"
: "no pattern in this query names it");
}
}
return NULL;
}
/* The error of an execution execute_single aborted: a failed start-node scan
* names the store's error, anything else was an allocation. */
static char *cypher_abort_error(void) {
if (g_cypher_scan_error[0]) {
char buf[CBM_SZ_1K];
snprintf(buf, sizeof(buf), "query aborted: reading the graph failed (%s)",
g_cypher_scan_error);
return heap_strdup(buf);
}
return heap_strdup("query aborted: out of memory or an allocation limit was reached");
}
int cbm_cypher_execute(cbm_store_t *store, const char *query, const char *project, int max_rows,
cbm_cypher_result_t *out) {
memset(out, 0, sizeof(*out));
g_cypher_depth_clamped = 0;
g_cypher_trail_truncated = 0;
g_cypher_truncated = false;
g_cypher_regex_refused = false;
g_cypher_scan_error[0] = '\0';
cypher_deadline_arm(); /* #601: start the wall-clock budget for this query */
/* max_rows sizes the initial binding array: non-positive means the
* ceiling, and nothing above the ceiling is ever materialized anyway. */
if (max_rows <= 0 || max_rows > CYPHER_RESULT_CEILING) {
max_rows = CYPHER_RESULT_CEILING;
}
cbm_query_t *q = NULL;
char *err = NULL;
if (cbm_cypher_parse(query, &q, &err) < 0) {
out->error = err;
return CBM_NOT_FOUND;
}
for (const cbm_query_t *sq = q; sq; sq = sq->union_next) {
char *scope_err = check_projection_scope(sq);
if (scope_err) {
cbm_query_free(q);
out->error = scope_err;
return CBM_NOT_FOUND;
}
}
result_builder_t rb = {0};
if (execute_single(store, q, project, max_rows, &rb) < 0) {
rb_free(&rb);
cbm_query_free(q);
out->truncated = g_cypher_truncated;
out->error = cypher_abort_error();
return CBM_NOT_FOUND;
}
/* UNION chain */
cbm_query_t *uq = q->union_next;
while (uq) {
result_builder_t rb2 = {0};
if (execute_single(store, uq, project, max_rows, &rb2) < 0) {
rb_free(&rb);
rb_free(&rb2);
cbm_query_free(q);
out->truncated = g_cypher_truncated;
out->error = cypher_abort_error();
return CBM_NOT_FOUND;
}
/* Concatenate rows from rb2 into rb */
for (int i = 0; i < rb2.row_count; i++) {
rb_add_row(&rb, rb2.rows[i]);
}
rb_free(&rb2);
uq = uq->union_next;
}
/* UNION (not ALL) deduplication */
if (q->union_next && !q->union_all) {
rb_apply_distinct(&rb);
}
/* #601: abort a runaway query that blew the wall-clock budget before it can
* return a misleading partial result. Checked before the row ceiling. */
if (g_cypher_timed_out) {
rb_free(&rb);
cbm_query_free(q);
out->truncated = g_cypher_truncated;
out->error =
heap_strdup("query exceeded the execution time limit — narrow the pattern with a WHERE "
"filter, use a directed MATCH instead of an unbounded OPTIONAL MATCH, or "
"add LIMIT");
return CBM_NOT_FOUND;
}
/* Check ceiling */
if (rb.row_count >= CYPHER_RESULT_CEILING) {
g_cypher_truncated = true;
rb_free(&rb);
cbm_query_free(q);
out->truncated = true;
out->error = heap_strdup("result exceeded 100k rows — use narrower filters or add LIMIT");
return CBM_NOT_FOUND;
}
out->columns = rb.columns;
out->col_count = rb.col_count;
out->rows = rb.rows;
out->row_count = rb.row_count;
/* Any internal ceiling that prevented exhaustive evaluation: a candidate or
* traversal budget, or a variable-length range clamped to the engine cap. */
out->truncated = g_cypher_truncated || g_cypher_trail_truncated != 0;
char wbuf[CBM_SZ_512] = "";
if (g_cypher_depth_clamped > 0 || g_cypher_trail_truncated) {
if (g_cypher_depth_clamped > 0 && g_cypher_trail_truncated) {
snprintf(wbuf, sizeof(wbuf),
"variable-length hop range clamped to the engine ceiling (%d) and "
"traversal budget was exhausted — results may be partial",
g_cypher_depth_clamped);
} else if (g_cypher_depth_clamped > 0) {
snprintf(wbuf, sizeof(wbuf),
"variable-length hop range clamped to the engine ceiling (%d) — an empty "
"result may mean \"clamped\", not \"no such path\"",
g_cypher_depth_clamped);
} else {
snprintf(wbuf, sizeof(wbuf),
"variable-length traversal budget was exhausted — results may be partial");
}
}
/* A refused `=~` or property pattern matched nothing: say so, once per
* query, next to any traversal warning. */
if (g_cypher_regex_refused) {
size_t used = strlen(wbuf);
snprintf(wbuf + used, sizeof(wbuf) - used,
"%sa =~ or property " CBM_REG_ETOOBIG_REASON " — the comparison matched nothing",
used ? "; " : "");
}
if (wbuf[0]) {
out->warning = heap_strdup(wbuf);
}
cbm_query_free(q);
return 0;
}
void cbm_cypher_result_free(cbm_cypher_result_t *r) {
if (!r) {
return;
}
free(r->warning);
r->warning = NULL;
for (int i = 0; i < r->col_count; i++) {
safe_str_free(&r->columns[i]);
}
free(r->columns);
for (int i = 0; i < r->row_count; i++) {
for (int j = 0; j < r->col_count; j++) {
safe_str_free(&r->rows[i][j]);
}
free(r->rows[i]);
}
free(r->rows);
free(r->error);
memset(r, 0, sizeof(*r));
}