Cypher Query Engine Internal Architecture in Codebase-Memory-MCP: A Deep Dive

The Cypher query engine in codebase-memory-mcp implements a four-stage compiler pipeline—lexer, parser, planner, and executor—that translates a restricted OpenCypher dialect into SQL queries against the internal graph store.

The Cypher query engine powers graph traversals inside the codebase-memory-mcp repository, enabling read-only analysis of code structure stored in the cbm_store database. Understanding its internal architecture helps developers write efficient queries and extend the supported OpenCypher subset. This article examines the compiler pipeline, AST structures, and precisely which language features are supported based on the actual source implementation.

Four-Stage Compiler Architecture

The engine follows a classic front-end compiler design with distinct phases that transform query text into executable database operations.

Lexer (Tokenization)

The lexical analyzer scans input strings and produces a stream of tokens defined in [src/cypher/cypher.h](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/cypher/cypher.h#L21-L127) (lines 21–127). The implementation in [src/cypher/cypher.c](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/cypher/cypher.c#L68-L140) (starting at line 68) handles string literals, numbers, identifiers, and operators.

Key token categories include:

• Two-character operators: !=, <>, =~, >=, <=, ..
• Single-character symbols: parentheses, brackets, colons, and arithmetic operators
• Keywords: MATCH, WHERE, RETURN, LIMIT, and logical operators

Parser and AST Construction

The recursive-descent parser consumes the token stream and builds an abstract syntax tree using structures defined in cypher.h (lines 57–85). The parser implementation in cypher.c (starting at line 33) constructs:

• Node patterns: cbm_node_pattern_t with labels and property maps
• Relationship patterns: cbm_rel_pattern_t supporting directionality and variable-length hops
• Expression trees: cbm_expr_t for WHERE clauses and CASE logic
• Return descriptors: handling projections, aliases, and ordering

The grammar covers seven distinct phases, validating pattern syntax, property filters, and clause ordering before AST construction completes.

Planner and SQL Translation

The planner walks the completed AST and emits a single SQL SELECT statement targeting the cbm_store tables (specifically node and edge tables). Implemented after line 1600 in cypher.c, this stage:

• Maps MATCH patterns to SQL JOIN operations between node and edge tables
• Translates WHERE expression trees into SQL predicates with proper parameter binding
• Converts RETURN items (including aggregates and scalar functions) into SELECT columns
• Handles ORDER BY, LIMIT, and SKIP as SQL clauses

The generated SQL string is passed to cbm_store_query for execution against the underlying storage layer.

Execution Layer

The execution entry point cbm_cypher_execute (defined in cypher.c) orchestrates the pipeline. It initializes the planner, processes the query, and populates a cbm_cypher_result_t structure containing column metadata, row data, and error states. Results are collected from the store and returned to the caller, who must invoke cbm_cypher_result_free to release memory.

Supported OpenCypher Subset

The engine deliberately implements a read-only subset of OpenCypher optimized for code analysis workflows. Write operations are rejected at parse time via unsupported_clause_error (lines 606–634 in cypher.c).

Pattern Matching and Traversal

MATCH clauses support complex graph patterns including:

• Node patterns: (var:Label {prop:"value"}) with optional labels and property filters
• Relationship patterns: -[:TYPE]-> with directional arrows (<-, ->, - for any direction)
• Variable-length hops: *, *1..3, *..5 for recursive relationship traversal

Example:

const char *qry = "MATCH (f:Function)-[:CALLS*1..3]->(g:Function) RETURN f.name, g.name";

Filtering and Predicates

WHERE clauses support extensive filtering via comparison operators (=, <>, !=, >, <, >=, <=), logical operators (AND, OR, XOR, NOT), and string operators (CONTAINS, STARTS WITH, ENDS WITH). Additional capabilities include:

• Regex matching: =~ operator
• List membership: IN
• Null checks: IS NULL / IS NOT NULL
• Label tests: var:Label
• Single-hop EXISTS sub-queries

Projections and Aggregations

RETURN and WITH clauses support:

• Scalar functions: toLower, toUpper, toString, size, length, trim, reverse
• Entity functions: labels(), type(), id(), keys(), properties()
• Multi-argument functions: coalesce, substring, replace, left, right
• Aggregates: COUNT, SUM, AVG, MIN, MAX, COLLECT
• Modifiers: DISTINCT, aliasing with AS, ORDER BY [ASC|DESC], LIMIT, SKIP
• CASE expressions: CASE WHEN condition THEN value [ELSE value] END

Example aggregation:

const char *qry = 
    "MATCH (f)-[:CALLS]->(g) "
    "RETURN f.name, COUNT(g) AS cnt ORDER BY cnt DESC LIMIT 10";

Explicitly Rejected Features

The parser rejects write-oriented and administrative clauses with clear error messages:

• Data modification: CREATE, DELETE, MERGE, SET, REMOVE
• Schema operations: DROP, CONSTRAINT, INDEX
• Advanced constructs: CALL, FOREACH, YIELD, list indexing/slicing, and user-defined procedures

Working with the Cypher API

Execute queries using the public C API defined in src/cypher/cypher.h:

#include "cypher.h"

/* Simple property lookup */
const char *query1 = "MATCH (f:Function) RETURN f.name, f.qualified_name";

/* Variable-length traversal with filtering */
const char *query2 = 
    "MATCH (f:Function)-[:CALLS*1..3]->(g:Function) "
    "WHERE f.name CONTAINS \"Order\" RETURN f.name, COUNT(g) AS cnt";

/* Execution and result handling */
cbm_cypher_result_t result = {0};
int rc = cbm_cypher_execute(store, query2, "analysis_context", 0, &result);

if (rc == 0) {
    /* Process rows in result.rows */
    for (int i = 0; i < result.row_count; i++) {
        /* Access result.rows[i].values[j] */
    }
}

cbm_cypher_result_free(&result);

Reference implementations in [tests/test_cypher.c](https://github.com/DeusData/codebase-memory-mcp/blob/main/tests/test_cypher.c) demonstrate supported syntax and error handling for edge cases.

Summary

• The Cypher query engine implements a four-stage pipeline: lexer (line 68+ in cypher.c), parser (line 33+), planner (post-line 1600), and executor (cbm_cypher_execute).
• It translates OpenCypher read-only queries into SQL for the cbm_store SQLite-backed graph database.
• Supported features include MATCH with variable-length relationships, comprehensive WHERE predicates, scalar and aggregate functions, and CASE expressions.
• Write operations are explicitly rejected via unsupported_clause_error (lines 606–634) to maintain read-only safety guarantees.
• Key files: src/cypher/cypher.h (AST definitions), src/cypher/cypher.c (implementation), and tests/test_cypher.c (validation suite).

Frequently Asked Questions

What Cypher clauses are unsupported by the engine?

The engine rejects all write-oriented clauses including CREATE, DELETE, MERGE, SET, and REMOVE, as well as administrative statements like DROP, CONSTRAINT, CALL, and FOREACH. These trigger unsupported_clause_error at parse time (lines 606–634 in cypher.c) to enforce the read-only design constraint.

How does the engine handle variable-length relationships?

Variable-length hops are parsed in relationship patterns using the * syntax (e.g., *1..3 or *..5) and stored in cbm_rel_pattern_t AST nodes. The planner translates these into recursive SQL CTEs or repeated JOINs against the edge table, depending on the specific SQLite capabilities available in cbm_store.

What is the underlying storage mechanism for the graph data?

The engine targets the internal cbm_store subsystem (defined in src/store/store.h and src/store/store.c), which uses SQLite as the backing store. Graph entities reside in node and edge tables, and the planner generates standard SQL SELECT statements to query these tables via cbm_store_query.

Where is the entry point for executing Cypher queries?

The public API entry point is cbm_cypher_execute in src/cypher/cypher.c. This function initializes the compiler pipeline, manages the conversion from Cypher text to SQL, executes the query against the store, and populates a cbm_cypher_result_t structure with the results.

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