Skip to content

GRAPH_SCHEMA.md

Latest commit

 

History

History
207 lines (160 loc) · 4.76 KB

GRAPH_SCHEMA.md

File metadata and controls

207 lines (160 loc) · 4.76 KB
Raw

Graph Schema

This document describes the data model used by Arbor to represent code structure.

Nodes

Every code entity is represented as a node in the graph.

Node Structure

{
  "id": "unique_node_identifier",
  "name": "FunctionName",
  "qualifiedName": "ModuleName.ClassName.FunctionName",
  "kind": "function",
  "file": "src/services/user.ts",
  "lineStart": 45,
  "lineEnd": 78,
  "column": 2,
  "signature": "async validateUser(id: string): Promise<User>",
  "visibility": "public",
  "attributes": {
    "async": true,
    "static": false,
    "exported": true
  },
  "docstring": "Validates a user by their ID.",
  "centrality": 0.75
}

Node Kinds

Kind Description Languages
function Standalone function All
method Class method All
class Class definition All
interface Interface/protocol/trait TS, Rust
struct Struct definition Rust
enum Enum definition All
variable Module-level variable All
constant Constant definition All
type_alias Type alias TS, Rust
module File/module boundary All
import Import statement All
export Export declaration TS

Node IDs

Node IDs are generated deterministically from:

  • File path (relative to project root)
  • Node qualified name
  • Node kind

This ensures the same node always gets the same ID, enabling incremental updates.

id = hash(file_path + ":" + qualified_name + ":" + kind)

Edges

Edges represent relationships between nodes.

Edge Structure

{
  "from": "source_node_id",
  "to": "target_node_id",
  "kind": "calls",
  "location": {
    "file": "src/services/user.ts",
    "line": 52,
    "column": 8
  }
}

Edge Kinds

Kind Description From → To
calls Function invocation function → function
imports Import statement module → module
exports Re-export module → symbol
extends Class inheritance class → class
implements Interface implementation class → interface
uses_type Type reference any → type/interface
references General symbol reference any → any
contains Nesting relationship class → method
returns Return type function → type
parameter Parameter type function → type

Graph Structure

The graph is stored using an adjacency list representation:

nodes: HashMap<NodeId, Node>
edges_out: HashMap<NodeId, Vec<Edge>>
edges_in: HashMap<NodeId, Vec<Edge>>

Both incoming and outgoing edges are indexed for fast traversal in either direction.

Indexes

For fast lookups, we maintain several indexes:

Name Index

name_index: HashMap<String, Vec<NodeId>>

Maps symbol names to node IDs. Used for text search.

File Index

file_index: HashMap<PathBuf, Vec<NodeId>>

Maps file paths to all nodes defined in that file. Used for incremental updates.

Kind Index

kind_index: HashMap<NodeKind, Vec<NodeId>>

Maps node kinds to IDs. Used for filtering by type.

Serialization

The graph can be serialized to JSON for export or persistence:

{
  "version": "1.0",
  "projectRoot": "/path/to/project",
  "timestamp": "2024-01-15T10:30:00Z",
  "stats": {
    "nodeCount": 1542,
    "edgeCount": 4820
  },
  "nodes": [
    { "id": "...", "name": "...", ... }
  ],
  "edges": [
    { "from": "...", "to": "...", "kind": "..." }
  ]
}

Language-Specific Mappings

TypeScript

AST Node Arbor Kind
function_declaration function
method_definition method
class_declaration class
interface_declaration interface
type_alias_declaration type_alias
variable_declaration variable
import_statement import
export_statement export

Rust

AST Node Arbor Kind
function_item function
impl_item → function_item method
struct_item struct
enum_item enum
trait_item interface
use_declaration import
mod_item module

Python

AST Node Arbor Kind
function_definition function
class_definition.function_definition method
class_definition class
import_statement import
import_from_statement import

Centrality Algorithm

Arbor uses a simplified PageRank variant to compute node importance:

  1. Initialize all nodes with score 1/N
  2. For each iteration:
    • Each node distributes its score to nodes it calls
    • Damping factor of 0.85 prevents score concentration
  3. Converge after ~10-20 iterations

Nodes with high centrality scores are architecturally significant (many dependents) and prioritized in context windows.