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

> Explore the Cypher query engine in DeusData/codebase-memory-mcp. Understand its four-stage pipeline lexing parsing planning and execution turning Cypher queries into SQL operations.

- Repository: [Martin Vogel/codebase-memory-mcp](https://github.com/DeusData/codebase-memory-mcp)
- Tags: internals
- Published: 2026-07-28

---

**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`](https://github.com/DeusData/codebase-memory-mcp/blob/main/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`](https://github.com/DeusData/codebase-memory-mcp/blob/main/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

```c
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

```c
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

```c
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`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/cypher/cypher.c) with public API definitions in [`src/cypher/cypher.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/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.