How Code-Graph-RAG Performs Data Flow Analysis: A Three-Verdict Reachability Algorithm

Code-Graph-RAG performs data flow analysis by executing a client-side breadth-first search over a locally built adjacency map, returning one of three verdicts—FOUND, NO_FLOW, or UNKNOWN—based on whether a path exists from source to sink or coverage gaps are detected.

Data flow analysis in the vitali87/code-graph-rag repository answers the critical security question "can data flow from source to sink?" using a lightweight, client-side algorithm that avoids expensive server-side traversals. The implementation in codebase_rag/flow_verdict.py runs entirely in Python, querying a Memgraph instance for FLOWS_TO edges before executing a local breadth-first search to determine reachability.

The Three-Verdict Data Flow Analysis Algorithm

The flow_reachability_verdict function implements a deterministic, four-step process to analyze data flow between any two qualified names (QNs) in a codebase.

Step 1: Collecting FLOWS_TO Edges via Cypher

The algorithm begins by retrieving the graph topology from Memgraph. It executes the CYPHER_FLOW_EDGES query defined in codebase_rag/cypher_queries.py, selecting every FLOWS_TO relationship whose endpoints belong to the target project.

The function accepts a generic fetch_all callable—typically a thin wrapper around the Memgraph client provided by GraphQueryClient in codebase_rag/graph_loader.py. Results are transformed into a Python adjacency map (edges) where each source qualified name maps to a list of its target QNs. This initialization occurs in lines 65-82 of codebase_rag/flow_verdict.py.

Step 2: Breadth-First Search for Concrete Paths

With the adjacency map loaded, the algorithm invokes the _bfs_path helper to perform a breadth-first search from the source QN to the sink QN. This pure-Python traversal operates entirely client-side, eliminating network round-trips during the pathfinding phase.

If _bfs_path discovers a route, the function immediately returns a FlowVerdict named-tuple with the verdict FOUND and an ordered list of QNs representing the complete data-flow path.

Step 3: Detecting Coverage Gaps

When the BFS finds no path, the algorithm distinguishes between "no flow possible" and "insufficient coverage." It executes CYPHER_FLOW_COVERAGE_GAPS to fetch every module not marked as flow-covered.

If uncovered files exist, the verdict becomes UNKNOWN accompanied by the list of gap paths. Otherwise, the verdict is NO_FLOW, indicating the analysis definitively proved no data-flow path exists within the covered graph. This logic resides in lines 86-94 of flow_verdict.py.

Step 4: Returning Structured FlowVerdict Results

Regardless of outcome, the function returns a structured FlowVerdict containing three fields:

• verdict: One of FOUND, NO_FLOW, or UNKNOWN
• path: An ordered list of QNs (populated only for FOUND)
• gaps: A list of uncovered file paths (populated only for UNKNOWN)

Callers inspect the verdict field to determine whether the flow is proven, inconclusive due to missing coverage, or definitively absent.

Client-Side BFS Architecture

The data-flow analysis achieves millisecond-level performance by keeping traversal logic out of the database. The adjacency map construction happens in a single Cypher round-trip, after which the Python BFS runs locally over the in-memory structure. This design scales to large codebases without degrading responsiveness.

The implementation relies on constants defined in codebase_rag/constants.py, specifically RelationshipType.FLOWS_TO and property identifiers used in the Cypher queries. A similar reachability pattern appears in codebase_rag/dead_code.py, demonstrating the reusability of this BFS-based strategy across the codebase.

Practical Example: Tracing Data from Source to Sink

The following example demonstrates how to invoke the data-flow analysis using the concrete GraphQueryClient implementation:

from codebase_rag.flow_verdict import flow_reachability_verdict, FlowVerdict
from codebase_rag.graph_loader import GraphQueryClient

# Initialize a client that can run Cypher queries against the Memgraph instance

client = GraphQueryClient(uri="bolt://localhost:7687", auth=("user", "pass"))

# Define the project and the qualified names of the source and sink

project = "my_project"
source_qn = "my_project.module_a.ClassA.method_x"
sink_qn = "my_project.module_b.ClassB.method_y"

# Run the data-flow analysis

verdict: FlowVerdict = flow_reachability_verdict(
    fetch_all=client.fetch_all,   # Callable that executes a Cypher query

    project_name=project,
    source_qn=source_qn,
    sink_qn=sink_qn,
)

print(f"Verdict: {verdict.verdict}")
if verdict.verdict == "FOUND":
    print("Path:", " → ".join(verdict.path))
elif verdict.verdict == "UNKNOWN":
    print("Uncovered files:", ", ".join(verdict.gaps))

Running this snippet produces one of three outcomes:

• FOUND — A concrete data-flow path exists, such as module_a.ClassA.method_x → … → module_b.ClassB.method_y
• NO_FLOW — The analysis proved no path can exist within the covered graph
• UNKNOWN — The graph lacks complete coverage; the listed gaps indicate files requiring additional instrumentation

Summary

• Three-verdict logic: Code-Graph-RAG returns FOUND, NO_FLOW, or UNKNOWN to distinguish proven flows, proven absences, and inconclusive results due to coverage gaps.
• Client-side performance: The algorithm builds a local adjacency map via CYPHER_FLOW_EDGES, then executes Python BFS without server-side traversal overhead.
• Coverage awareness: When paths are missing, CYPHER_FLOW_COVERAGE_GAPS identifies uncovered modules, preventing false negatives.
• Structured output: The FlowVerdict named-tuple provides programmatic access to paths, gaps, and verdicts for downstream security analysis.

Frequently Asked Questions

What are the three possible verdicts in Code-Graph-RAG's data flow analysis?

The algorithm returns FOUND when a concrete path exists from source to sink, NO_FLOW when the covered graph definitively contains no such path, and UNKNOWN when the analysis cannot determine reachability due to incomplete coverage of the project files. This three-verdict system prevents false negatives by explicitly flagging coverage gaps rather than assuming safety.

Why does Code-Graph-RAG use client-side BFS instead of server-side graph traversal?

Code-Graph-RAG uses client-side breadth-first search to minimize latency and database load. By fetching all FLOWS_TO edges in a single Cypher query via fetch_all and building a local adjacency map, the system avoids repeated network round-trips during traversal. According to the source code in codebase_rag/flow_verdict.py, this approach completes in milliseconds even for large codebases because the BFS runs in pure Python over an in-memory data structure.

How does the algorithm handle incomplete code coverage?

When the BFS finds no path, the algorithm executes CYPHER_FLOW_COVERAGE_GAPS to identify modules not marked as flow-covered. If any gaps exist, it returns an UNKNOWN verdict along with the list of uncovered file paths. This mechanism, implemented in lines 86-94 of flow_verdict.py, ensures users understand whether a "no path" result is conclusive or merely reflects missing instrumentation.

Where are the Cypher queries for data flow analysis defined?

The Cypher query strings reside in codebase_rag/cypher_queries.py, specifically CYPHER_FLOW_EDGES (which selects all FLOWS_TO relationships for a project) and CYPHER_FLOW_COVERAGE_GAPS (which identifies uncovered modules). These constants are imported by codebase_rag/flow_verdict.py and executed through the generic fetch_all protocol provided by GraphQueryClient in codebase_rag/graph_loader.py.

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