Knowledge Graph Core Indexer (#17517) · Epics · GitLab.org

Knowledge Graph Core Indexer

This document outlines the design for the **Knowledge Graph Core Rust Project**. This project is a core component of the broader [Knowledge Graph First Iteration](https://gitlab.com/groups/gitlab-org/-/epics/17514) initiative, which aims to create a structured, queryable representation of code repositories to power advanced AI features and enhance developer productivity within GitLab. The Core Indexer is responsible for discovering, parsing, analyzing, and storing code information to build this knowledge graph. ## Table of Contents * [High-Level Architecture Overview](#high-level-architecture-overview) * [1. Client-Side Integration Entry Points](#1-client-side-integration-entry-points) * [1.1. Command Line Interface (CLI)](#11-command-line-interface-cli) * [1.2. Language Server Protocol (LSP) Integration](#12-language-server-protocol-lsp-integration) * [2. Server Integration](#2-server-integration) * [3. File Discovery and Parsing Phase](#3-file-discovery-and-parsing-phase) * [3.1. File Discovery](#31-file-discovery) * [3.1.1. Workspace Scanning (Client-Side)](#311-workspace-scanning-client-side) * [3.1.2. Repository Access (Client-Side)](#312-repository-access-client-side) * [3.1.3. Server-Side File Discovery](#313-server-side-file-discovery) * [3.2. Code Parsing and Language Data Extraction](#32-code-parsing-and-language-data-extraction) * [4. Resolution/Analysis Phase](#4-resolutionanalysis-phase) * [4.1. Analysis Service](#41-analysis-service) * [4.2. Phase 1: Initial Linking - Definitions, References, and Local Context](#42-phase-1-initial-linking---definitions-references-and-local-context) * [4.2.1. Core Goal & Approach](#421-core-goal--approach) * [4.2.2 Kùzu Schema Definition: Phase 1 Entities and Relationships](#422-k%C3%B9zu-schema-definition-phase-1-entities-and-relationships) * [4.2.3 Dependency Analysis (Phase 1)](#423-dependency-analysis-phase-1) * [4.2.4. Intermediate State Management (Using an Embedded Key-Value Store)](#424-intermediate-state-management-using-an-embedded-key-value-store) * [4.3. Phase 2: Advanced Cross-File Resolution](#43-phase-2-advanced-cross-file-resolution) * [4.3.1. Core Goal & Approach](#431-core-goal--approach) * [4.3.2. Enhancing `gitlab-code-parser` with Scope and Export Data](#432-enhancing-gitlab-code-parser-with-scope-and-export-data) * [4.3.3. Kùzu Schema Definition: Phase 2 Additions and Refinements](#433-k%C3%B9zu-schema-definition-phase-2-additions-and-refinements) * [4.3.4. Resolution Engine: Using Stack Graphs Internally](#434-resolution-engine-using-stack-graphs-internally) * [4.4. Language-Specific Considerations](#44-language-specific-considerations) * [4.5. Incremental Analysis & State Management](#45-incremental-analysis--state-management) * [5. Writing Phase](#5-writing-phase) * [5.1. Database Technology (Kuzu)](#51-database-technology-kuzu) * [5.2. Database Connection Service](#52-database-connection-service) * [5.3. Database Schema Service](#53-database-schema-service) * [5.4. Writer Service - General](#54-writer-service---general) * [5.4.1. Parallel Data Processing and Writing Architecture](#541-parallel-data-processing-and-writing-architecture) * [5.4.2. Bulk Writer (Initial Indexing)](#542-bulk-writer-initial-indexing) * [5.4.3. Incremental Writer (Updates)](#543-incremental-writer-updates) * [6. Query Library](#6-query-library) * [7. Observability](#7-observability) ## High-Level Architecture Overview The Knowledge Graph Core Indexer follows a pipeline architecture with three main phases: 1. **File Discovery and Parsing Phase**: Discovers source files and extracts AST-based code elements 2. **Resolution/Analysis Phase**: Links definitions to references and builds relationships 3. **Writing Phase**: Persists the analyzed graph data to Kuzu database The system supports both client-side (CLI, LSP) and server-side integration points. ```mermaid graph TD subgraph "Client-Side Entry Points" CLI["CLI Application"] LSP["LSP Integration (NAPI-RS)"] end subgraph "Server Integration" SERVER["Server Worker (Future)"] end subgraph "Phase 1: File Discovery & Parsing" GITALISK["Gitalisk (Repository Discovery)"] PARSER["gitlab-code-parser (AST & Language Analysis)"] CLI --> GITALISK LSP --> GITALISK SERVER --> PARSER GITALISK --> PARSER end subgraph "Phase 2: Resolution & Analysis" ANALYSIS["Analysis Service"] PHASE1["Phase 1: Initial Linking (Local Context & FQNs)"] PHASE2["Phase 2: Advanced Resolution (Cross-file & Stack Graphs)"] KV["Key-Value Store (Fjall - Optional)"] PARSER --> ANALYSIS ANALYSIS --> PHASE1 PHASE1 --> PHASE2 ANALYSIS <--> KV end subgraph "Phase 3: Writing" WRITER["Writer Service"] BULK["Bulk Writer (Parquet + COPY FROM)"] INCR["Incremental Writer (Targeted Cypher)"] PHASE2 --> WRITER WRITER --> BULK WRITER --> INCR end subgraph "Storage" KUZU[("Kuzu Database (Embedded Graph DB)")] SCHEMA["Database Schema Service"] CONN["Database Connection Service"] BULK --> KUZU INCR --> KUZU SCHEMA --> KUZU CONN --> KUZU end subgraph "Query & Access" QUERY["Query Library (Future)"] KUZU --> QUERY end ``` ## 1. Client-Side Integration Entry Points The Knowledge Graph Core Indexer will be designed to be accessible and usable directly on any developer's machine. ### 1.1. Command Line Interface (CLI) The indexer will provide a standalone Command Line Interface (CLI) application, packaged within the `cli` crate. This CLI serves as the primary entry point for client-side operations. **End goals:** * **Full Indexing Process:** will be able to run the entire indexing process in a standalone CLI application. * **Local Query Server:** The CLI will spin up a local server for running cypher queries against the generated graph database. * **Data Exploration UI (future):** will serve a UI for exploring the data (similar to kuzu explorer) * **Server-Side Invocation (Initial):** For initial server-side implementation simplicity, "The server-side Go worker... would execute the Rust CLI binary, passing the path to the code." [("Knowledge Graph Indexer Sync 2025-04-30" comment)](https://gitlab.com/groups/gitlab-org/-/epics/17517#note_2480940813). **Implementation Example (`main.rs` from context):** We will use `clap::Parser` for argument parsing and orchestrating the indexing pipeline. Here's an example of the CLI (simplified): ```rust use clap::{Parser, Subcommand}; // ... other imports ... #[derive(Parser, Debug)] #[command(author, version, about, long_about = None)] struct Cli { #[command(subcommand)] command: Commands, } #[derive(Subcommand, Debug)] enum Commands { /// Run full indexing of the workspace Index { /// Directory to scan #[arg(default_value = ".")] workspace_path: PathBuf, /// Optional number of threads to use #[arg(short, long, default_value_t = 0)] threads: usize, /// Optional path to the graph database #[arg(short, long, default_value = "graph.db")] database_path: PathBuf, }, /// Watch mode for incremental updates Watch { /// Directory to watch #[arg(default_value = ".")] workspace_path: PathBuf, /// Optional number of threads to use #[arg(short, long, default_value_t = 0)] threads: usize, /// Optional path to the graph database #[arg(short, long, default_value = "graph.db")] database_path: PathBuf, }, /// Start query service for running Cypher queries Query { /// Optional path to the graph database #[arg(short, long, default_value = "graph.db")] database_path: PathBuf, /// Port to run the query server on #[arg(short, long, default_value_t = 8080)] port: u16, }, } fn main() -> anyhow::Result<()> { env_logger::init(); let start_time = Instant::now(); let cli = Cli::parse(); // ... rest of the main logic orchestrating file collection, processing, writing ... Ok(()) } ``` ### 1.2. Language Server Protocol (LSP) Integration The indexer's core logic will be consumable by Language Servers to provide real-time code intelligence within IDEs. This will be facilitated by the Language Server Bindings crate `lsp`, which uses `napi-rs` to expose Rust functionality directly to Node.js environments. **NAPI-RS Integration Architecture:** Following the pattern established in our `gitalisk` project, the Knowledge Graph indexer will expose its core functionality to the Language Server through native Node.js addons built with `napi-rs`. This approach is necessary because: * The Language Server runs in a Node.js environment and requires real-time access to indexing functionality * Separate processes would introduce communication overhead and complexity for frequent LSP operations * The indexer's core logic is implemented in Rust and needs to be accessible from TypeScript * Incremental indexing operations must run asynchronously to avoid blocking the Language Server's event loop **Implementation Structure:** The Language Server Bindings crate (`lsp`) will be structured similarly to `gitalisk-node`: ```rust use knowledge_graph_core::CoreKnowledgeGraphIndexer; use napi_derive::napi; use std::sync::Arc; #[napi(object)] pub struct IndexerOptions { pub workspace_path: String, pub database_path: String, } #[napi] pub struct KnowledgeGraphLSP { core_indexer: Arc<CoreKnowledgeGraphIndexer>, } #[napi] impl KnowledgeGraphLSP { #[napi(constructor)] pub fn new(options: IndexerOptions) -> napi::Result<Self> { let core_indexer = CoreKnowledgeGraphIndexer::new( &options.workspace_path, &options.database_path, )?; Ok(Self { core_indexer: Arc::new(core_indexer) }) } /// Perform incremental indexing (async, non-blocking) #[napi] pub fn index_files_async(&self, file_paths: Vec<String>) -> AsyncTask<IncrementalIndexTask> { // Returns AsyncTask for non-blocking operation } /// Find references to a symbol at position #[napi] pub fn find_references(&self, file_path: String, line: u32, column: u32) -> napi::Result<Vec<Reference>> { let references = self.core_indexer.find_references_at_position(&file_path, line, column)?; Ok(references.into_iter().map(Reference::from).collect()) } } ``` **Language Server Usage:** In the GitLab Language Server (Node.js), the bindings would be consumed as follows: ```typescript import { KnowledgeGraphLSP } from '@gitlab-org/knowledge-graph-lsp'; class GitLabKnowledgeGraphProvider { private indexer: KnowledgeGraphLSP; constructor(workspacePath: string) { this.indexer = new KnowledgeGraphLSP({ workspace_path: workspacePath, database_path: path.join(workspacePath, '.gitlab', 'knowledge-graph.db'), }); } // Handle file change events with non-blocking updates async onFileChanged(fileUri: string): Promise<void> { const filePath = URI.parse(fileUri).fsPath; await this.indexer.indexFilesAsync([filePath]); } // Provide references for LSP requests async provideReferences(document: TextDocument, position: Position): Promise<Reference[]> { const filePath = URI.parse(document.uri).fsPath; return this.indexer.findReferences(filePath, position.line, position.character); } } ``` **Build Configuration:** The Language Server Bindings will use the same cross-platform build approach as `gitalisk`, generating platform-specific `.node` files that are automatically loaded at runtime. The `package.json` configuration will include: ```json { "name": "@gitlab-org/knowledge-graph-lsp", "napi": { "name": "knowledge-graph-lsp", "triples": { "defaults": true, "additional": [ "x86_64-apple-darwin", "aarch64-apple-darwin", "aarch64-unknown-linux-gnu", "x86_64-unknown-linux-musl" ] } } } ``` This integration approach ensures that the Language Server can leverage the full power of the Knowledge Graph indexer with minimal performance overhead and maximum type safety. > **Important Note:** Both the CLI and Language Server will share a majority of the client side logic under the "file discovery and parsing phase". ## 2. Server Integration TBD, can be filled out by @jprovaznik. > Note: The server, for testing purposes, will rely on the CLI version. ## 3. File Discovery and Parsing Phase This phase is responsible for locating relevant source code files within a project and transforming their content into structured Abstract Syntax Trees (ASTs). ### 3.1. File Discovery The indexer needs to efficiently find all relevant source files in a given workspace or repository. #### 3.1.1. Workspace Scanning (Client-Side) For client-side operations, the indexer will use `gitalisk` to scan local workspaces and discover repositories. * **Repository Discovery:** `gitalisk` handles traversing the file system to discover all repositories within a workspace URI, including nested repositories * **Workspace Management:** The service can associate local projects with their GitLab/GitHub remotes and provide workspace-level statistics * **Cross-Platform Support:** Leverages `libgit2` through Rust for consistent behavior across macOS, Linux, and Windows #### 3.1.2. Repository Access (Client-Side) All repository-level operations will be handled through `gitalisk` for consistency and performance. * **Git Operations:** Branch information, file status, and repository metadata access through safe Rust bindings to `libgit2` * **File Enumeration:** Efficient discovery of tracked files while respecting `.gitignore` rules * **Integration:** Available as Node.js bindings via `napi-rs` for Language Server integration, and as native Rust crate for CLI usage #### 3.1.3. Server-Side File Discovery In the future, for server-side indexing operations, the process will be much simpler: * The server-side worker will receive a repository path from the GitLab Monolith application * Files will be provided directly through Gitaly or similar repository access mechanisms * No workspace scanning or repository discovery logic is needed server-side * The indexer core will focus purely on parsing the provided file content ### 3.2. Code Parsing and Language Data Extraction Once files are discovered, their content will be parsed into Abstract Syntax Trees (ASTs) and relevant code intelligence data will be extracted. The Knowledge Graph Core Indexer will directly utilize the `parser-core` crate (from the `gitlab-code-parser` project) for these tasks. The `indexer` crate will orchestrate the parsing and data extraction process. For each file, we will: 1. **Determine the Language:** The language will be inferred from the file extension (e.g., `.rb` for Ruby, `.py` for Python). 2. **Invoke the Language-Specific Analyzer:** Based on the determined language, we will instantiate and use the appropriate analyzer from `parser-core`. For example, for Ruby files, we will use `parser_core::ruby::analyzer::RubyAnalyzer`. 3. **Rule-Based Data Extraction:** The analyzer will then apply a set of predefined `ast-grep` rules (embedded within `parser-core`, such as `RUBY_RULES` and `RULES_CONFIG` for Ruby) to the AST. These rules are designed to identify key code constructs. 4. **Extraction of Definitions, References, and Imports:** The core indexer, through the language-specific analyzer, will extract structured information, including: * **Definitions:** Such as classes, modules, functions, methods, and constants. Each definition will include: * A **Fully Qualified Name (FQN)** (e.g., `MyModule::MyClass#my_method`). The generation of FQNs is a critical responsibility of the analyzer. * The **type** of the definition (e.g., "class", "method", "module"). * The **byte range** (start and end bytes) covering the entire entity. * Other language-specific metadata (e.g., visibility for methods, superclasses for classes). * **References:** Such as method calls, class instantiations, or constant usages. Each reference will include: * The **text matched** for the reference. * A **target FQN hint** (the name/FQN of the entity being referenced, as best as can be determined statically). For Ruby, the `RubyAnalyzer` attempts assignment tracing to improve the accuracy of the resolved FQN. * The **byte range** of the reference. * The **context FQN** (the FQN of the scope containing the reference). * **Imports/Requires:** Statements that bring external code into the current file's scope. This information is crucial for resolving references across files. * The **source path** of the imported symbol/module. * Any **alias** used. * The **byte range** of the import statement. The output will be a structured representation of these elements for each file. To ensure that subsequent phases of the indexing process can work with rich, type-specific information for each language, this output (e.g., a `FileAnalysisResult` structure) can be conceptualized as being generic or containing language-specific data types for its core fields. An illustrative example: ```rust struct FileAnalysisResult { file_path: String, definitions: Vec<(/* FQN */ String, /* entity_type */ String, /* rule_id */ String /*, ...other_lang_specific_metadata */)>, references: Vec<(/* matched_text */ String, /* target_fqn_hint */ String, /* rule_id */ String /*, ...other_lang_specific_metadata */)>, imports: Vec<(/* source_path */ String, /* alias */ Option<String> /*, ...other_lang_specific_metadata */)>, } // Actual fields for definitions, references, and imports will hold language-specific types // or enums to capture detailed metadata (e.g., visibility, inheritance, specific call types). ``` This language-specific approach ensures that we can capture the unique semantics and metadata relevant to each programming language. For instance, Ruby's module system and dynamic nature require different handling compared to Python's import mechanism or JavaScript's module formats. The above demonstrates how specific logic can be encapsulated to handle such language-specifics effectively. This extracted information (definitions, references, imports) will then be passed to the "Resolution/Analysis Phase" for node matching and relationship building. The goal is to produce a consistent set of data structures that can be consumed by the graph-building process, while allowing for the necessary language-specific details to be captured accurately. ## 4. Resolution/Analysis Phase After parsing, the extracted ASTs and raw code elements are analyzed to understand their meaning, resolve names, and identify relationships. This phase transforms the parser's output into a connected graph of code entities. It is a two-stage process: an initial linking phase focusing on local context and basic relationships, followed by an advanced resolution phase for more complex cross-file and contextual linking. This logic will reside primarily in the `indexer` crate of the indexer. ```mermaid graph TD subgraph "Input from Parsing Phase" PARSER_OUT["Parser Output (Definitions, References, Imports)"] end subgraph "Analysis Service Orchestration" ANALYSIS_SVC["Analysis Service (indexer crate)"] STATE_MGMT["Intermediate State Management"] PARSER_OUT --> ANALYSIS_SVC ANALYSIS_SVC <--> STATE_MGMT end subgraph "Phase 1: Initial Linking" P1_PROCESS["Local Context Resolution"] P1_FQN["FQN-based Linking"] P1_IMPORT["Basic Import Resolution"] P1_OUTPUT["Phase 1 Results (Local Links)"] ANALYSIS_SVC --> P1_PROCESS P1_PROCESS --> P1_FQN P1_FQN --> P1_IMPORT P1_IMPORT --> P1_OUTPUT end subgraph "Phase 2: Advanced Resolution" P2_SCOPE["Scope Analysis (Future Enhancement)"] P2_STACK["Stack Graph Resolution"] P2_CROSS["Cross-file Linking"] P2_OUTPUT["Phase 2 Results (Complete Graph)"] P1_OUTPUT --> P2_SCOPE P2_SCOPE --> P2_STACK P2_STACK --> P2_CROSS P2_CROSS --> P2_OUTPUT end subgraph "State Storage (Optional)" FJALL[("Fjall Key-Value Store (Symbol Tables & Unresolved Refs)")] STATE_MGMT <--> FJALL end subgraph "Kuzu Schema Preparation" KUZU_PREP["Transform to Kuzu Format (Nodes & Relationships)"] P2_OUTPUT --> KUZU_PREP end subgraph "Output to Writing Phase" WRITER_INPUT["Structured Graph Data (Ready for Kuzu)"] KUZU_PREP --> WRITER_INPUT end ``` The diagram above shows how the Analysis Service orchestrates the two-phase resolution process, utilizing an optional key-value store for managing intermediate state. ### 4.1. Analysis Service The Analysis Service, a core component of the `indexer`, orchestrates the resolution and analysis process. Its primary responsibilities include: * **Consuming Parser Output:** Ingesting the structured data (definitions, references, imports, and potentially initial scope information) produced by the `gitlab-code-parser` for each processed file. * **Managing Intermediate State (optional depending on performance):** Coordinating with any embedded key-value store (e.g., Fjall) to manage symbol tables, unresolved references, and other necessary state during the indexing process, especially for large projects, to avoid excessive memory consumption. * **Executing Phase 1 Linking:** Driving the initial linking of definitions and references based on readily available information like Fully Qualified Names (FQNs) and local lexical context. * **Executing Phase 2 Resolution:** Initiating advanced resolution algorithms that leverage richer semantic information, including detailed scope data and import/export relationships, to link references across files and complex code structures. * **Preparing Data for Kùzu:** Transforming the analyzed and linked data into a format suitable for writing to the Kùzu graph database via the Writer Service. This service acts as the brain of the analysis phase so that data flows correctly from parsing to graph construction. ### 4.2. Phase 1: Initial Linking - Definitions, References, and Local Context This initial phase focuses on establishing straightforward relationships within the codebase, primarily leveraging the direct output of `gitlab-code-parser` and simple heuristics. #### 4.2.1. Core Goal & Approach The main goal is to quickly link obvious definitions to their references, especially those within the same file or easily resolvable via FQNs. This phase builds the foundational layer of the code graph. * **Intra-file Resolution:** Link references to definitions within the same file using FQNs and lexical proximity. * **Basic Import Resolution:** Link import statements to the files they point to, if directly identifiable. * **Directory Structure:** Establish relationships between directories and the files/subdirectories they contain. #### 4.2.2 Kùzu Schema Definition: Phase 1 Entities and Relationships > **Note:** these relationships are subject to change depending on implementation findings. This subsection, along with 4.3.3, defines the Kùzu graph schema that the Database Schema Service (Section 5.3) will be responsible for creating. The data from Phase 1 analysis populates an initial set of nodes and relationships in Kùzu. * **Node Types (Phase 1):** * `DirectoryNode`: Represents a directory in the repository. * Properties: `path` (PRIMARY KEY, STRING), `name` (STRING). * `FileNode`: Represents a source code file. * Properties: `path` (PRIMARY KEY, STRING), `name` (STRING), `language` (STRING), `checksum` (STRING, for change detection). * `DefinitionNode`: Represents a defined code construct. Initially, `scope_id` might be null or point to a file-level default scope if detailed scope parsing is deferred to Phase 2. * Properties: `fqn` (PRIMARY KEY, STRING), `name` (STRING), `type` (STRING: "class", "function", "method", etc.), `file_path` (STRING, FK to `FileNode.path`), `scope_id` (STRING, FK to `ScopeNode.id` - may be refined in Phase 2), `start_byte` (INT64), `end_byte` (INT64). * `ReferenceNode`: Represents a usage or call to a definition. Initially, `scope_id` might be null or point to a file-level default scope. * Properties: `id` (SERIAL PRIMARY KEY, or a composite unique ID STRING, e.g., `file_path#Ref(name)@start_byte`), `name_referenced` (STRING, the textual name being referenced), `file_path` (STRING, FK to `FileNode.path`), `scope_id` (STRING, FK to `ScopeNode.id` - may be refined in Phase 2), `start_byte` (INT64), `end_byte` (INT64), `context_fqn` (STRING, FQN of containing scope, useful before full `ScopeNode` linking). * `ImportStatementNode`: Represents an import statement. * Properties: `id` (SERIAL PRIMARY KEY, or a composite unique ID STRING), `file_path` (STRING, FK to `FileNode.path`), `scope_id` (STRING, FK to `ScopeNode.id` - typically file/module scope), `source_text` (STRING), `imported_symbol_name` (STRING, optional), `alias` (STRING, optional), `start_byte` (INT64), `end_byte` (INT64). * **Relationship Types (Phase 1):** * `CONTAINS_DIR (FROM DirectoryNode TO DirectoryNode)` * `CONTAINS_FILE (FROM DirectoryNode TO FileNode)` * `DEFINED_IN_FILE (FROM DefinitionNode TO FileNode)` (or `FILE_HAS_DEFINITION`) * `HAS_REFERENCE_IN_FILE (FROM ReferenceNode TO FileNode)` (or `FILE_CONTAINS_REFERENCE`) * `DECLARES_IMPORT (FROM ImportStatementNode TO FileNode)` (or `FILE_HAS_IMPORT`) * `REFERENCE_RESOLVES_TO_DEFINITION (FROM ReferenceNode TO DefinitionNode)`: Populated for direct, unambiguous local resolutions established in Phase 1. #### 4.2.3 Dependency Analysis (Phase 1) In addition to code entities, understanding the dependencies a codebase relies on is crucial for a comprehensive knowledge graph. Phase 1 will include basic modeling of these dependencies. ##### DependencyNode Schema * **`DependencyNode`** (NEW for Phase 1) * `name`: STRING (PRIMARY KEY, e.g., "rails", "lodash", "./utils/helpers") - This represents the identifier of the dependency. * `type`: STRING (e.g., "external_library", "internal_module", "system_library") - Categorizes the dependency. * `version`: STRING (Optional, e.g., "7.0.0", null for internal dependencies or when version is not specified/resolved). * `source_type`: STRING (e.g., "gem", "npm", "pip", "maven", "go_module", "rust_crate", "internal_relative_path", "internal_absolute_path", "stdlib") - Indicates how the dependency is managed or its origin. * _Comment:_ Represents a dependency that the codebase relies on. This can be an external third-party library, an internal module within the same monorepo but a different logical unit, or a standard library component. ##### New Relationships for Dependencies (Phase 1) * **`FILE_DEPENDS_ON (FROM FileNode TO DependencyNode)`** * Links a `FileNode` directly to a `DependencyNode` it utilizes. This relationship is typically derived from successfully resolved import statements within the file. * _Properties (optional):_ `import_type`: STRING (e.g., "require", "import", "include", "use") - The keyword or mechanism used for the import. * **`IMPORT_STATEMENT_RESOLVES_TO_DEPENDENCY (FROM ImportStatementNode TO DependencyNode)`** * Connects an `ImportStatementNode` to the specific `DependencyNode` it successfully resolves to. This provides a more granular link showing which import declaration brought in which dependency. The `gitlab-code-parser` will be responsible for identifying import statements and attempting an initial classification of the dependency's name and source (e.g., distinguishing a gem from a relative file path in Ruby). The Analysis Service will then create the `DependencyNode` and the relevant relationships. ##### Future Iterations: Advanced Dependency Resolution While Phase 1 focuses on capturing declared dependencies, subsequent iterations will aim for more sophisticated dependency resolution and analysis, including: * **Version Resolution:** For external libraries, accurately determining the specific version being used, potentially by parsing lock files (`Gemfile.lock`, `package-lock.json`, `go.mod`, `Cargo.lock`) or build system configurations. * **Transitive Dependencies:** Mapping the full dependency tree, including dependencies of dependencies. * **Internal Module Resolution:** For monorepos or complex projects, accurately resolving internal dependencies across different modules or packages within the same repository by analyzing project configuration files (e.g., `setup.py`, `package.json` workspaces, `pom.xml`). * **Dependency Vulnerability Linking:** Integrating with vulnerability databases to link `DependencyNode`s to known security advisories. * **License Information:** Storing license information associated with each `DependencyNode`. #### 4.2.4. Intermediate State Management (Using an Embedded Key-Value Store) > Note: This is aspect can be lower priority for the initial release. We will need to measure the memory usage and performance of the indexer and determine if this is a bottleneck. For large repositories, loading all symbols and unresolved references into main memory can be inefficient or infeasible. To manage this, the Analysis Service can utilize a fast embedded key-value store, such as [Fjall](https://github.com/fjall-rs/fjall). * **Symbol Table:** As definitions are processed from each file by `gitlab-code-parser`, their FQNs and essential metadata (e.g., file path, type, Kùzu node ID if already written) can be stored in Fjall. * `Key`: `definition_fqn` (e.g., "MyModule::MyClass#my_method") * `Value`: Serialized data (e.g., JSON, Bincode) like `{ "file_path": "src/my_class.rb", "type": "method", "kuzu_id": "some_uuid" }` * **Unresolved References:** When a reference is encountered, the Analysis Service first attempts to resolve it using the key-value store. * If the `target_fqn_hint` from the parser exists as a key in Fjall, a preliminary link can be established. * If not immediately resolvable (e.g., requires import resolution or deeper analysis), the reference can be stored in a "pending resolution" list within Fjall or a separate Kùzu table. * **Incremental Updates:** For incremental indexing, the key-value store can help track the state of symbols from the previous run, aiding in diffing and determining what needs re-analysis. **Practical Example with Fjall (Conceptual):** ```rust use fjall::{Config, Keyspace, PartitionCreateOptions}; // Assuming fjall is a dependency let keyspace = Config::new("./temp_symbol_db").open().unwrap(); let definitions_partition = keyspace.open_partition("definitions", PartitionCreateOptions::default()).unwrap(); let unresolved_refs_partition = keyspace.open_partition("unresolved_refs", PartitionCreateOptions::default()).unwrap(); let def_fqn = "MyModule::MyClass#my_method"; let def_metadata = r#"{ "file_path": "src/my_class.rb", "type": "method" }"#; definitions_partition.insert(def_fqn, def_metadata).unwrap(); // When processing a reference from parser_core_result.references: let target_fqn_hint = "MyModule::MyClass#my_method"; if let Ok(Some(def_metadata_bytes)) = definitions_partition.get(target_fqn_hint) { // Found a candidate definition, proceed to link or verify } else { // Store for Phase 2: unresolved_refs_partition.insert(reference_id, reference_details_json).unwrap(); } keyspace.persist(fjall::PersistMode::SyncAll).unwrap(); // Periodically persist ``` This can allow the indexer to scale better by offloading large symbol tables to disk while still providing fast lookups. ### 4.3. Phase 2: Advanced Cross-File Resolution While Phase 1 handles many common cases, robustly resolving references across files, through imports, and in the presence of complex scope interactions (like those in dynamically-typed languages or complex class hierarchies) requires a more sophisticated approach. This phase can draw inspiration from stack graph and call-graph principles. #### 4.3.1. Core Goal & Approach The primary goal of Phase 2 is to accurately resolve remaining unresolved references by: * Modeling code scopes explicitly. * Tracking how symbols are imported and exported between scopes (files/modules). * Using this information to trace a path from a reference to its correct definition, even across multiple files. This phase enriches the graph with more precise relationships and lays the foundation for features like call graph construction. #### 4.3.2. Enhancing `gitlab-code-parser` with Scope and Export Data > Note: This is a future enhancement. With the stack graph approach, the parser requirements are simplified. To power this advanced resolution, `gitlab-code-parser` would need to be updated to extract more detailed semantic information beyond basic definitions and references. This includes: * **Detailed Scope Information:** * For each logical block of code (module, class, function, method, even anonymous blocks if relevant for the language), the parser should identify: * `scope_id`: A unique identifier for the scope (e.g., derived from file path and scope structure, or a UUID). * `parent_scope_id`: Identifier of the lexically enclosing scope. * `scope_type`: (e.g., "module", "class_definition", "function_definition", "lexical_block"). * `start_byte`, `end_byte`: The exact boundaries of the scope. * Definitions and references should be associated with their immediate `scope_id`. * **Export Information:** * For scopes that can export symbols (e.g., modules, files in some languages), the parser must identify what symbols are made available to other scopes. * This would result in `ExportEntry` data, including: * `exporting_scope_id`: The scope performing the export. * `definition_fqn`: The FQN of the `DefinitionNode` being exported. * `exported_name`: The name under which the symbol is exported (could be an alias). **Practical Example of Parser Output (Simplified):** ```rust struct ScopeInfo { scope_id: String, // e.g., "src/utils.py#MyClass" parent_scope_id: Option<String>, // e.g., "src/utils.py#<file_scope>" scope_type: String, // "class_definition" start_byte: usize, end_byte: usize, // Definitions, References, and Imports would now also carry their direct scope_id } struct ExportInfo { exporting_scope_id: String, // e.g., "src/utils.py#<file_scope>" definition_fqn: String, // FQN of the definition being exported exported_name: String, // e.g., "utility_function_renamed" } ``` `gitlab-code-parser` would need language-specific logic to identify these scopes and exports accurately (e.g., Python's `__all__` or implicit module exports, JavaScript's `export` keyword). #### 4.3.3. Kùzu Schema Definition: Phase 2 Additions and Refinements Phase 2 can leverage concepts from stack-graphs/call-graphs as an internal resolution engine to accurately link references to definitions across files and complex scopes, without persisting the intermediate graph structures to Kuzu. * **Enhanced Relationship (Phase 2):** * **`REFERENCE_RESOLVES_TO_DEFINITION (FROM ReferenceNode TO DefinitionNode)`**: This would be the primary output of Phase 2 resolution. * Properties: * `resolution_type` (STRING): Indicates how the reference was resolved (e.g., "direct_local", "imported", "inherited", "stack_graph_path") * `confidence` (FLOAT): A score indicating resolution confidence (0.0-1.0) * `resolution_path` (STRING, optional): For debugging, can store the stack graph path used for resolution > Note: it may make sense to store the intermediary information relationships (like MODULE_IN_SCOPE) in the graph database so that that clients can consume them. #### 4.3.4. Resolution Engine: Using Stack Graphs Internally The Resolution Engine can leverage stack graphs to perform name resolution: 1. **Stack Graph Construction:** For each file being analyzed, the Resolution Engine: * Builds a stack graph representation including: * Push/pop nodes for scopes * Import/export nodes for module boundaries * Definition and reference nodes with their binding information * This graph exists only in memory during analysis 2. **Path-Finding Resolution:** For each unresolved reference: * The engine performs stack graph path-finding from the reference to potential definitions * It considers: * Lexical scoping rules * Import/export relationships * Symbol visibility and shadowing * Multiple candidate paths may be found and ranked 3. **Resolution Output:** Once a reference is resolved: * Only the `REFERENCE_RESOLVES_TO_DEFINITION` relationship is created in Kuzu * Resolution metadata (type, confidence) is attached to the relationship > **Implementation Note:** We can consider directly using [stack-graphs](https://github.com/github/stack-graphs) as a dependency in the Analysis Service, similar to how `tree-sitter` is used for parsing. ### 4.4. Language-Specific Considerations While the overall framework aims for language agnosticism, the specifics of parsing (scope rules, export mechanisms, FQN generation) and certain resolution heuristics will inevitably be language-specific. * **`gitlab-code-parser`:** Encapsulates most language-specific parsing logic. For example, Python's dynamic features mean FQN resolution for references is often a "best effort" approximation, as noted in the "First iteration of the Python parser" epic. The `RubyAnalyzer`'s "assignment tracing" is another example of language-specific analysis. * **Resolution Engine:** May employ language-specific strategies for tie-breaking ambiguous resolutions or understanding idiomatic patterns (e.g., how different module systems interact). The goal remains "good-enough" accuracy for AI features, not full compiler precision, as stated in the [main epic](https://gitlab.com/groups/gitlab-org/-/epics/17514). ### 4.5. Incremental Analysis & State Management Efficient incremental updates are crucial, especially for client-side scenarios. The state management approach discussed in Phase 1 (using an embedded key-value store like Fjall) is vital here: * **Tracking Changes:** The indexer needs to identify which files have changed since the last run (e.g., by comparing checksums or using file system notifications). We can use `gitalisk` for this purpose (running "git status") * **Updating Key-Value Store:** For changed files, definitions and other relevant symbols are updated in the key-value store. * **Targeted Re-resolution:** * References _within_ changed files are re-resolved. * References _to_ symbols in changed files (from other, unchanged files) may need re-validation. The key-value store can help identify these affected "external" references. * If a definition's FQN changes or it's deleted, all `ReferenceNode`s previously pointing to it (queried from Kùzu or tracked in the KV store) must be re-processed. * **Kùzu Updates:** The Writer Service then applies the delta (new nodes/rels, updated nodes/rels, deleted nodes/rels) to the Kùzu database using targeted Cypher queries (MERGE, SET, DELETE). ## 5. Writing Phase This phase involves persisting the analyzed and resolved code graph data into the Kuzu database. It takes the output from the Resolution/Analysis Phase (Section 4) and uses the KuzuDatabaseManager and schema definitions to write nodes and relationships. ### 5.1. Database Technology (Kuzu) The project will utilize Kuzu, an embeddable graph database, to persist the graph structure. Kuzu is well-suited for this task due to its performance characteristics for graph operations and its ability to be embedded within the indexer application. For client-side deployments, such as the CLI or LSP integration, the indexer will statically link Kuzu's C++ library, enabling a self-contained distribution. We will create a separate Kuzu database file for each indexed project (e.g., `project_name.kuzu.db`). When the indexer processes a project that references entities in another project (e.g., cross-project imports or dependencies), it may create placeholder nodes (like a `ProjectNode`) in the current project's database to represent the external project. Future client-side tooling could potentially offer capabilities to merge these individual project databases or perform queries that span across multiple database files. To maintain flexibility across different environments (client-side vs. server-side), database interactions will be managed through an abstracted database client layer, ensuring that the core indexing logic remains decoupled from specific database connection or management details of the host environment. ### 5.2. Database Connection Service A dedicated Database Connection Service, likely residing within the `indexer` crate (or a specialized `indexer-db` sub-crate), will be responsible for managing all interactions with Kuzu database instances. Given the strategy of maintaining one Kuzu database file per project, this service will primarily handle the opening, closing, and lifecycle management of connections to these individual database files. It will provide a central component, tentatively named `KuzuDatabaseManager`, which encapsulates a Kuzu `Database` object and an active `Connection`. The `KuzuDatabaseManager` will expose a comprehensive API for database operations, including: * Executing arbitrary Cypher queries for data retrieval or modification. * Performing efficient bulk data ingestion, primarily using Kuzu's `COPY FROM` command with Parquet files (as detailed in Section 5.4.2), for initial indexing and large-scale updates. * Applying incremental updates to the graph using targeted Cypher queries (e.g., `MERGE`, `SET`, `DELETE` statements) for smaller, more frequent changes. * Initiating schema definition and migration processes, ensuring the database structure is correctly established and maintained. * Facilitating read access to the graph, which might be required by the Analysis Service (Section 4.1) during incremental updates to understand the existing graph state. This service acts as the primary interface for the indexer to interact with the Kuzu persistence layer. ### 5.3. Database Schema Service The Database Schema Service, also a component of the `indexer` (or a dedicated database crate), will define, apply, and manage the Kuzu graph schema. While the conceptual schema (node tables, relationship tables, properties) is detailed in Section 4 (Resolution/Analysis Phase), this service is responsible for its concrete implementation and evolution within Kuzu. A core feature of this service will be a **Rust-based, type-safe API for constructing schema definition (DDL) statements**. This API will allow developers to define Kuzu tables (nodes and relationships), their properties, data types (e.g., `STRING`, `INT64`, `BOOL`), and primary keys using idiomatic Rust structures and enums. The service will then translate these Rust definitions into the appropriate Kuzu Cypher DDL queries (e.g., `CREATE NODE TABLE ...`, `CREATE REL TABLE ...`). The Database Schema Service will utilize the `KuzuDatabaseManager` (from the Database Connection Service) to execute these generated DDL statements, ensuring that Kuzu database instances are correctly initialized with the required schema before any data is written. It will also be responsible for managing schema migrations should the graph structure evolve in future versions of the indexer. Furthermore, this service (or a closely related query service, see Section 6.1) will aim to provide a **type-safe mechanism for building Cypher queries in Rust**. This could involve: * A builder pattern for constructing Cypher queries programmatically. * Compile-time or strong runtime checks for query parameters. * Utilities for parsing query results into strongly-typed Rust structs or enums. ### 5.4. Writer Service - General This service in the `Core Indexer crate` uses the output from the Analysis Service (Section 4) and the schema definitions (Section 5.3) to write data to Kuzu. It determines the writing strategy. * **Purpose (from CSV data, adapted):** "This layer determines the strategy for the incoming write operations (e.g., initial bulk load vs. incremental update), and passes the data and operation type to the Bulk Writer or Incremental Writer sub-services. It receives fully resolved and structured node/relationship data from the Analysis Service." #### 5.4.1. Parallel Data Processing and Writing Architecture To efficiently handle the processing of numerous source files and the subsequent writing of extracted graph data, the indexer will employ a parallel processing architecture based on worker threads and communication channels. This design is inspired by concurrent processing patterns (similar to the [PoC in `main.rs` that used this for CSV generation](https://gitlab.com/gitlab-org/rust/knowledge-graph/-/merge_requests)) and is crucial for achieving high throughput, especially during bulk indexing operations where data is written to Parquet files. ```mermaid graph TD subgraph "File Discovery" FEEDER["File Feeder Thread (Producer)"] FILES[("Source Files (*.rb, *.py, etc.)")] FILES --> FEEDER end subgraph "Work Distribution" WORK_QUEUE[("Work Channel (Bounded MPMC)")] FEEDER --> WORK_QUEUE end subgraph "Parallel Processing" W1["Worker Thread 1 (Consumer)"] W2["Worker Thread 2 (Consumer)"] W3["Worker Thread N (Consumer)"] WORK_QUEUE --> W1 WORK_QUEUE --> W2 WORK_QUEUE --> W3 subgraph "Per-Worker Processing" PARSE["Parse File (AST Extraction)"] ANALYZE["Analysis Service (Resolution)"] STRUCT["Structure Data (Nodes & Relationships)"] W1 --> PARSE PARSE --> ANALYZE ANALYZE --> STRUCT end end subgraph "Result Collection" RESULT_QUEUE[("Result Channel (Bounded MPMC)")] W1 --> RESULT_QUEUE W2 --> RESULT_QUEUE W3 --> RESULT_QUEUE end subgraph "Parquet Writing" WRITER["Parquet Writer Thread (Consumer)"] RESULT_QUEUE --> WRITER subgraph "Output Files" DEF_PARQUET["definitionnodes.parquet"] REF_PARQUET["referencenodes.parquet"] FILE_PARQUET["filenodes.parquet"] REL_PARQUET["relationships.parquet"] WRITER --> DEF_PARQUET WRITER --> REF_PARQUET WRITER --> FILE_PARQUET WRITER --> REL_PARQUET end end subgraph "Kuzu Database" COPY_CMD["COPY FROM commands (Bulk Loading)"] KUZU_DB[("Kuzu Database (project.kuzu.db)")] DEF_PARQUET --> COPY_CMD REF_PARQUET --> COPY_CMD FILE_PARQUET --> COPY_CMD REL_PARQUET --> COPY_CMD COPY_CMD --> KUZU_DB end ``` The architecture comprises the following key components: * **File Feeder Thread:** * Responsible for discovering all relevant source code files within the target workspace or repository. * Once files are collected, this thread acts as a producer, sending file paths to a bounded work channel (e.g., `work_sender`). * This decouples file discovery from the actual processing. * **Worker Threads:** * A pool of worker threads (configurable, typically based on the number of CPU cores) act as consumers from the work channel (e.g., `work_receiver`). * Each worker thread retrieves a file path, reads the file content, and invokes the Analysis Service (as detailed in Section 4) to parse the file and resolve entities. * The results from the Analysis Service (structured data representing nodes and relationships) are then sent to a bounded result channel (e.g., `result_sender`). * This allows multiple files to be parsed and analyzed concurrently, maximizing CPU utilization. * **Parquet Writer Thread:** * A dedicated writer thread acts as a consumer from the result channel (e.g., `result_receiver`). * It receives structured data from the worker threads and is responsible for serializing this data into the Parquet format. * Multiple Parquet files will be generated, typically one for each node type (e.g., `DefinitionNode`, `ReferenceNode`, `FileNode`) and one for each relationship type (e.g., `REFERENCE_RESOLVES_TO_DEFINITION`). * This thread handles all I/O operations for writing Parquet files, preventing I/O from blocking the processing worker threads. It will manage Parquet file writers, schema definitions for each file, and batching writes for efficiency. * **Communication Channels:** * **Work Channel:** A multi-producer, multi-consumer (MPMC) bounded channel for distributing file paths from the feeder to the workers. * **Result Channel:** An MPMC bounded channel for sending processed graph data from workers to the Parquet writer thread. * Bounded channels help manage backpressure. This should help prevent excessive memory consumption if one stage is significantly faster than another. #### 5.4.2. Bulk Writer (Initial Indexing) For the first-time indexing of a repository or large-scale updates, the Bulk Writer Service leverages Kuzu's efficient bulk loading capabilities. This occurs after the Resolution/Analysis phase has processed and linked all relevant code data, potentially using in-memory techniques or an embedded Key-Value store (e.g., Fjall) for managing intermediate state during analysis. The parallel processing architecture described in Section 5.4.1 prepares data for this stage. * **Strategy:** Utilize Kuzu's `COPY FROM` command with Parquet files for the initial, full graph population. The Parquet format, being columnar and typed, is highly suitable for bulk data ingestion into Kuzu. The Resolution/Analysis Service, via the parallel processing pipeline, will prepare comprehensive sets of node and relationship data. The Bulk Writer, through the Parquet Writer Thread, then serializes this data into multiple Parquet files (e.g., `filenodes.parquet`, `definitionnodes.parquet`, `referencenodes.parquet`, and various relationship Parquet files like `ref_def_rels.parquet`, `scope_child_rels.parquet`, etc.) from the structured data provided by the Analysis Service's output. Each Parquet file will adhere to the schema of the corresponding Kuzu table. * **Service Role:** This sub-layer of the Writer Service orchestrates the initial import of the complete, resolved graph into Kuzu. It is responsible for generating multiple Parquet files (e.g., `filenodes.parquet`, `definitionnodes.parquet`, `referencenodes.parquet`, and various relationship Parquet files like `ref_def_rels.parquet`, `scope_child_rels.parquet`, etc.) from the structured data provided by the Analysis Service's output. Each Parquet file will adhere to the schema of the corresponding Kuzu table. * **Parquet File Generation and Kuzu `COPY` Statements:** The Parquet Writer Thread (Section 5.4.1) will receive analyzed data and write it to appropriately structured Parquet files. For instance: * `definitionnodes.parquet`: Would contain columns like `fqn` (STRING), `name` (STRING), `type` (STRING), `file_path` (STRING), `scope_id` (STRING), `start_byte` (INT64), `end_byte` (INT64). * `reference_definition_rels.parquet`: Would contain columns like `_from` (referring to `ReferenceNode.id`), `_to` (referring to `DefinitionNode.fqn`), and relationship properties like `resolution_type` (STRING). Once the Parquet files are generated, Kuzu `COPY FROM` statements will be executed to load the data. Example Kuzu Cypher statements for loading from Parquet files: ```cypher -- Load DefinitionNode data from a Parquet file COPY DefinitionNode FROM 'definitionnodes.parquet' (FORMAT PARQUET); -- Load FileNode data from a Parquet file COPY FileNode FROM 'filenodes.parquet' (FORMAT PARQUET); -- Load REFERENCE_RESOLVES_TO_DEFINITION relationship data -- Assuming _from column in Parquet maps to ReferenceNode's ID and _to maps to DefinitionNode's FQN COPY REFERENCE_RESOLVES_TO_DEFINITION FROM 'reference_definition_rels.parquet' (FORMAT PARQUET); ``` These commands direct Kuzu to efficiently load data from the specified Parquet files into the corresponding tables. The `FORMAT PARQUET` option explicitly tells Kuzu the file format. If column names in the Parquet file match the table property names, Kuzu handles the mapping automatically. #### 5.4.3. Incremental Writer (Updates) For incremental updates, the indexer will use the existing Bulk Writer service to apply the delta (new nodes/rels, updated nodes/rels, deleted nodes/rels) to the Kuzu database using targeted Cypher queries (MERGE, SET, DELETE). ## 6. Query Library ## 7. Observability

epic