How the Cypher Query Engine in src/cypher/cypher.c Functions: From Lexing to Execution

The Cypher query engine in codebase-memory-mcp implements a four-stage pipeline—lexing, parsing, planning/validation, and execution—that transforms Neo4j-style Cypher queries into SQL-style operations against the internal cbm_store.

The Cypher query engine is a self-contained interpreter residing in src/cypher/cypher.c that enables the codebase-memory-mcp repository to process graph pattern matching without external Neo4j dependencies. This compact implementation handles a strategic subset of the Cypher language, converting raw query strings into executable operations through a rigorous multi-phase pipeline.

Lexical Analysis: Tokenizing the Query Stream

The pipeline begins with cbm_lex(const char *input, cbm_lex_result_t *out), defined in src/cypher/cypher.c. This function transforms the raw query string into a flat array of cbm_token_t structures, each capturing the token type, original text, and source position.

The lexer operates through several specialized helper functions:

• lex_skip_whitespace_comments – Skips irrelevant whitespace and comment blocks before processing meaningful tokens.
• lex_string_literal – Handles quoted strings while respecting escape sequences.
• lex_try_number and lex_try_ident – Distinguish between numeric literals and identifiers/keywords.
• lex_try_two_char – Recognizes multi-character operators such as !=, >=, and the range operator ...
• lex_single_char – Processes single-character tokens like parentheses, commas, and brackets.

Tokens are appended to the result buffer using lex_push and lex_push_n, producing a stream that includes types such as TOK_MATCH, TOK_WHERE, and TOK_RETURN.

Parsing: Constructing the Abstract Syntax Tree

Once tokenized, the stream enters cbm_parse(const cbm_token_t *tokens, int token_count, cbm_parse_result_t *out). This recursive-descent parser builds a cbm_query_t structure representing the complete query AST.

The parser utilizes a parser_t struct to maintain the token array and a positional cursor (pos). Key parsing components include:

Pattern Matching: The parse_match_pattern and parse_match_chain functions construct cbm_pattern_t objects containing cbm_node_pattern_t and cbm_rel_pattern_t descriptors. These structures encode graph topology, variable bindings, and label constraints.

Expression Trees: WHERE clauses are parsed into executable expression trees through a hierarchy of functions: parse_or_expr, parse_and_expr, and parse_not_expr. This recursive approach handles nested boolean logic and comparison operators.

Return Projections: The parse_return_item function processes RETURN and WITH clauses, dispatching to specialized handlers like parse_case_expr for CASE statements and parse_aggregate_item for aggregate functions (COUNT, SUM, etc.).

Unsupported Construct Detection: Functions like unsupported_clause_error immediately reject queries containing CREATE, DELETE, or MERGE clauses, ensuring the engine only attempts operations it can safely execute.

Planning and Validation

During the parsing phase, the engine performs lightweight planning to prepare for execution:

• Direction Detection: The parser analyzes relationship patterns for directional indicators (< and >), populating rel->direction with values "inbound", "outbound", or "any" based on the presence of leading_lt or trailing_gt markers.
• Hop Range Interpretation: Variable-length path patterns like *1..3 are processed by parse_hop_range, converting syntax into min/max bounds for traversal.
• Label Predicates: Constraints such as WHERE n:Label are encoded as leaf conditions with the operator "HAS_LABEL", allowing efficient filtering during execution.

This validation layer ensures that only semantically valid queries proceed to the execution phase, preventing runtime errors on malformed graph patterns.

Execution: Query Evaluation and Result Generation

The public execution API is cbm_cypher_execute(cbm_store_t *store, const char *query, const char *project, int max_rows, cbm_result_set_t *out). This function orchestrates the complete execution flow:

1. Lex and Parse: Invokes cbm_lex and cbm_parse to validate syntax and build the AST.
2. Budget Enforcement: Establishes a wall-clock deadline via execute_deadline to prevent runaway queries from consuming excessive resources.
3. Pattern Matching: execute_with_clause iterates over MATCH patterns, utilizing the store's index functions (e.g., cbm_store_find_node) to bind variables to actual graph entities.
4. Predicate Evaluation: The expression tree built during parsing is evaluated for each binding via expr_eval, discarding rows that fail the WHERE clause constraints.
5. Projection Dispatch: execute_return_clause routes to specialized handlers based on return type:
   • execute_return_star: Returns all columns for * projections.
   • execute_return_agg: Accumulates aggregate values (COUNT, SUM, AVG) across the result set.
   • execute_return_simple: Handles scalar expressions with optional DISTINCT, ORDER BY, and LIMIT clauses.
6. UNION Handling: For UNION clauses, the engine recursively parses and executes the right-hand side query, merging result sets according to UNION ALL semantics.
7. Result Packaging: Populates cbm_result_set_t while respecting the max_rows limit and execution deadline.

Key internal execution entry points include execute_with_clause (driving the pattern-matching loop) and execute_return_clause (managing result projection), both implementing the core traversal logic that interfaces with the underlying storage layer.

Practical Code Examples

Simple MATCH with Filtering

const char *query = "MATCH (n:Person) WHERE n.age > 30 RETURN n.name, n.age ORDER BY n.age DESC LIMIT 10";
cbm_result_set_t rs;
int rc = cbm_cypher_execute(store, query, "myproject", 1000, &rs);

This example demonstrates the full pipeline: the lexer identifies TOK_MATCH and comparison operators, the parser builds patterns for (n:Person) with a WHERE condition n.age > 30, and execution filters nodes before returning the top 10 results sorted by age.

UNION with OPTIONAL MATCH

const char *query =
    "MATCH (a:Author) OPTIONAL MATCH (a)-[:WROTE]->(b:Book) "
    "RETURN a.name, collect(b.title) UNION ALL "
    "MATCH (c:Category) RETURN c.name";
cbm_result_set_t rs;
cbm_cypher_execute(store, query, "library", 0, &rs);

Here, parse_rel detects the optional relationship pattern, setting rel->direction = "any" for the WROTE edge. The UNION clause triggers recursive cbm_parse calls to process both sub-queries, with results concatenated according to UNION ALL semantics.

Aggregate Functions

const char *query = "MATCH (p:Product) RETURN SUM(p.price) AS total_price";
cbm_result_set_t rs;
cbm_cypher_execute(store, query, "sales", 1, &rs);

parse_aggregate_item identifies TOK_SUM and constructs a cbm_return_item_t with func = "SUM". During execution, execute_return_agg accumulates values across all bindings, emitting a single row containing the aliased total_price.

Summary

• Four-Stage Pipeline: The engine processes queries through lexical analysis (cbm_lex), AST construction (cbm_parse), validation planning, and execution (cbm_cypher_execute).
• File Location: All core logic resides in src/cypher/cypher.c with public API definitions in src/cypher/cypher.h.
• Memory Safety: Allocation wrappers from src/foundation/* (such as heap_strdup and safe_str_free) ensure leak-free operation even during parse failures.
• Query Support: The implementation handles MATCH, OPTIONAL MATCH, WHERE, RETURN, WITH, and UNION ALL, with explicit rejection of mutating operations (CREATE, DELETE, MERGE).

Frequently Asked Questions

What subset of Cypher does the engine support?

According to the codebase-memory-mcp source code, the engine supports read-only operations including MATCH, OPTIONAL MATCH, WHERE filtering, RETURN projections (including aggregates), WITH clauses, and UNION ALL. It explicitly rejects data-modifying commands such as CREATE, DELETE, MERGE, and SET through the unsupported_clause_error mechanism during parsing.

How does the engine prevent infinite or long-running queries?

The execution phase enforces a wall-clock deadline via execute_deadline, which tracks elapsed time during pattern matching and result generation. If a query exceeds this budget, execution terminates early, returning partial results or an error depending on the implementation context.

How are complex WHERE clauses with nested logic handled?

The parser implements recursive-descent expression parsing through functions like parse_or_expr, parse_and_expr, and parse_not_expr, building a tree structure that expr_eval traverses during execution. This design supports arbitrarily nested boolean logic, comparisons, and label checks (e.g., n:Label syntax).

How does OPTIONAL MATCH affect execution?

When the parser encounters OPTIONAL MATCH, parse_rel sets relationship direction to "any" and the executor (execute_with_clause) treats missing patterns as valid bindings with NULL values rather than filtering failures, ensuring rows are preserved even when optional relationships do not exist.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}