Skip to content

dependency-graph.md

Latest commit

 

History

History
149 lines (103 loc) · 7.21 KB

dependency-graph.md

File metadata and controls

149 lines (103 loc) · 7.21 KB
Raw

Dependency Graph

The dependency graph is where DGAT earns its name. After the file tree is built, the engine parses every file's imports, resolves them to actual files in the project, and constructs a directed graph of relationships. This isn't just "file A imports file B" — each node and edge carries a natural-language description generated by the LLM.

Core structures

DepNode

struct DepNode {
  string name;
  string rel_path;
  string abs_path;
  string description;
  bool is_file;
  bool is_gitignored;
  string hash;
  vector<string> depends_on;
  vector<string> depended_by;
};

A DepNode represents a file in the dependency graph. It's similar to TreeNode but flatter — no children array, just the adjacency lists.

name — the filename, extracted from the path. Display label in the graph UI.

rel_path — the unique identifier for this node. Same convention as TreeNode::rel_path. This is what edges reference as from and to.

abs_path — absolute path on disk, populated by looking up the corresponding TreeNode if it exists.

description — the LLM-generated description. For internal files, this comes from the file description pass. For external dependencies (things imported but not in the project tree), a separate LLM call generates a description like "A lightweight HTTP server library for C++."

is_file — always true for dep nodes. Directories don't appear in the dependency graph.

is_gitignored — whether this file is excluded by .gitignore. Gitignored dependencies still appear in the graph but are flagged so you know they're outside the tracked source.

hash — the XXH3-128 fingerprint, copied from the TreeNode if available. Hex-encoded string.

depends_on — list of rel_path values for files this node imports. Populated by iterating all edges after graph construction.

depended_by — list of rel_path values for files that import this node. The inverse of depends_on.

DepEdge

struct DepEdge {
  string from_path;
  string to_path;
  string import_stmt;
  string description;
};

A DepEdge is a directed relationship: from_path imports something from to_path.

from_path — the importing file's rel_path.

to_path — the imported file's rel_path.

import_stmt — the actual import statement as it appears in the source code. import { foo } from './utils', #include "helpers.h", from .models import User. This is what lets the UI show you exactly how one file depends on another.

description — a one-sentence explanation of the relationship, generated by the LLM. The prompt gives it both files' descriptions and the import statement, and asks: "what does file A use from file B and why?" Example: "page.tsx uses the formatDate utility from utils.ts to display human-readable timestamps in the activity feed."

DepGraph

struct DepGraph {
  vector<DepNode> nodes;
  vector<DepEdge> edges;
  unordered_map<string, int> path_to_node;
};

The container that holds everything together. path_to_node is a quick lookup from rel_path to the index in the nodes array — avoids O(n) scans when adding edges.

How the graph is built

The build_dep_graph() function runs in parallel across 8 worker threads:

  1. Collect source files — walk the tree, gather all files with recognized language extensions, read their contents
  2. Extract imports per file — each worker parses one file's imports using tree-sitter (or regex fallback)
  3. Filter out stdlib/external — skip standard library imports (os, sys, stdio.h, etc.) and system includes (<vector>, <iostream>)
  4. Resolve import paths — normalize relative paths, expand TypeScript path aliases (@/components/Foo → frontend/src/components/Foo.tsx), try common extensions, check for barrel files (index.ts) and Python __init__.py
  5. Create edges — for each resolved internal import, create a DepEdge with the import statement
  6. Create nodes — ensure every file that appears in an edge has a corresponding DepNode
  7. Populate adjacency lists — iterate all edges to fill depends_on and depended_by on each node

Import resolution strategy

The resolver tries multiple approaches in order:

  1. Exact path match — ./utils → check if utils exists as a file
  2. Extension trial — try appending .py, .tsx, .ts, .jsx, .js, .css, .scss, .h, .hpp
  3. Barrel files — try norm/index.tsx, norm/index.ts, etc.
  4. Python init — try norm/__init__.py
  5. Filename-only match — last resort, match just the basename (catches C/C++ header-only scenarios)

This covers the common patterns: relative imports, path aliases, barrel re-exports, and Python package imports.

LLM annotation passes

After the raw graph is built, two more passes add descriptions:

Node descriptions (populate_dependency_descriptions)

For nodes marked as "External dependency" or "Gitignored dependency" — files that are imported but don't exist in the project tree — the engine asks the LLM to describe what that dependency is. The prompt includes the dependency name and a list of files that import it (up to 5, with a count for the rest).

Internal files already have descriptions from the file description pass, so they're skipped here.

Edge descriptions (populate_edge_descriptions)

For each edge where both the source and target files have meaningful descriptions (not just placeholders like "Source file" or "External dependency"), the LLM generates a one-sentence explanation of the relationship.

Edges where either side is boring are skipped — the LLM won't produce anything useful if it doesn't know what one of the files does.

Graph serialization

The graph gets serialized to JSON via build_dep_graph_json() and written to dep_graph.json. The frontend consumes this directly for the Sigma.js WebGL graph visualization.

{
  "nodes": [
    {
      "id": "src/utils.ts",
      "name": "utils.ts",
      "rel_path": "src/utils.ts",
      "description": "**Utility functions** — shared helpers for date formatting...",
      "depends_on": [],
      "depended_by": ["src/pages/index.tsx", "src/components/Header.tsx"]
    }
  ],
  "edges": [
    {
      "from": "src/pages/index.tsx",
      "to": "src/utils.ts",
      "import_stmt": "import { formatDate } from '../utils'",
      "description": "index.tsx uses formatDate from utils.ts to render..."
    }
  ]
}

Why a separate graph structure instead of enriching the tree?

The tree and the graph serve different purposes. The tree is a hierarchical representation of the filesystem — it's what you see in the explorer panel. The graph is a flat, edge-list representation of import relationships — it's what you see in the graph tab.

They overlap (every file that appears in the graph also exists in the tree), but the graph includes nodes for external dependencies that don't exist in the tree at all. Keeping them separate avoids polluting the tree structure with nodes that don't correspond to actual files on disk.

After the graph is built, dependency info (depends_on, depended_by) is synced back into the tree nodes so the inspector panel can show it regardless of which view you're using.