graph

package
v0.4.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 26, 2026 License: AGPL-3.0 Imports: 8 Imported by: 0

Documentation

Overview

Package graph provides code relationship graph types and operations.

The graph package contains types for representing code as a directed graph where nodes are symbols (functions, types, variables) and edges represent relationships (calls, imports, implements, etc.).

Ownership Model

The graph stores pointers to symbols but does NOT own them:

  • Symbols MUST NOT be mutated after being added via AddNode()
  • The graph does NOT copy symbols (for memory efficiency)
  • Same ownership contract as the index package

Thread Safety

Graph is NOT safe for concurrent use during building. It is designed for:

  • Single-writer access during build phase (AddNode, AddEdge calls)
  • Read-only access after Freeze() is called

After Freeze(), the graph can be safely read from multiple goroutines.

Lifecycle

A typical graph lifecycle:

  1. Create with NewGraph(projectRoot)
  2. Build with AddNode() and AddEdge() calls
  3. Call Freeze() to finalize
  4. Query with GetNode(), traversal methods, etc.

Index

Constants

View Source 
const (
	// DefaultMaxMemoryMB is the default memory limit for building (512MB).
	DefaultMaxMemoryMB = 512

	// DefaultWorkerCount is the default number of parallel workers.
	// Set to 0 to use runtime.NumCPU().
	DefaultWorkerCount = 0
)

Default builder configuration values.

View Source 
const (
	// DefaultQueryLimit is the default maximum number of results.
	DefaultQueryLimit = 1000

	// MaxQueryLimit is the maximum allowed limit.
	MaxQueryLimit = 10000

	// DefaultMaxDepth is the default maximum traversal depth.
	DefaultMaxDepth = 10

	// MaxTraversalDepth is the maximum allowed traversal depth.
	MaxTraversalDepth = 100
)

Query configuration limits.

View Source 
const (
	// DefaultMaxNodes is the default maximum number of nodes a graph can hold.
	DefaultMaxNodes = 1_000_000

	// DefaultMaxEdges is the default maximum number of edges a graph can hold.
	DefaultMaxEdges = 10_000_000
)

Default configuration values.

Variables

View Source 
var (
	// ErrGraphFrozen is returned when attempting to modify a frozen graph.
	// Once Freeze() is called, the graph becomes read-only and no further
	// nodes or edges can be added.
	ErrGraphFrozen = errors.New("graph is frozen and cannot be modified")

	// ErrNodeNotFound is returned when an edge references a non-existent node.
	// Both source and target nodes must exist before an edge can be created.
	ErrNodeNotFound = errors.New("node not found")

	// ErrDuplicateNode is returned when adding a node with an ID that
	// already exists in the graph.
	ErrDuplicateNode = errors.New("duplicate node ID")

	// ErrMaxNodesExceeded is returned when the graph has reached its
	// configured maximum node capacity.
	ErrMaxNodesExceeded = errors.New("maximum node count exceeded")

	// ErrMaxEdgesExceeded is returned when the graph has reached its
	// configured maximum edge capacity.
	ErrMaxEdgesExceeded = errors.New("maximum edge count exceeded")

	// ErrInvalidNode is returned when attempting to add a nil symbol
	// or a symbol that fails validation.
	ErrInvalidNode = errors.New("invalid node")

	// ErrBuildCancelled is returned when a build operation is cancelled via context.
	ErrBuildCancelled = errors.New("build cancelled")

	// ErrMemoryLimitExceeded is returned when the builder exceeds its configured
	// memory limit during graph construction.
	ErrMemoryLimitExceeded = errors.New("memory limit exceeded")

	// ErrInvalidEdgeType is returned when an edge type is not valid for the
	// given source and target node kinds.
	ErrInvalidEdgeType = errors.New("invalid edge type for node kinds")
)

Sentinel errors for graph operations.

Functions

This section is empty.

Types

type BuildProgress 

type BuildProgress struct {
	// Phase is the current build phase.
	Phase ProgressPhase

	// FilesTotal is the total number of files to process.
	FilesTotal int

	// FilesProcessed is the number of files processed so far.
	FilesProcessed int

	// NodesCreated is the number of nodes created so far.
	NodesCreated int

	// EdgesCreated is the number of edges created so far.
	EdgesCreated int
}

BuildProgress contains progress information during a build.

type BuildResult 

type BuildResult struct {
	// Graph is the constructed graph. May be partial if errors occurred
	// or the build was cancelled.
	Graph *Graph

	// FileErrors contains errors for files that failed processing.
	// Files in this list are not represented in the graph.
	FileErrors []FileError

	// EdgeErrors contains errors for edges that couldn't be created.
	// The graph may still contain valid edges despite these errors.
	EdgeErrors []EdgeError

	// Stats contains build statistics.
	Stats BuildStats

	// Incomplete is true if the build was cancelled (via context) or
	// stopped due to memory limits. When true, the graph contains
	// partial results.
	Incomplete bool
}

BuildResult contains the result of a graph build operation.

Build operations are designed to be resilient: individual file failures do not fail the entire build. Instead, partial results are returned along with error information.

func (*BuildResult) HasErrors 

func (r *BuildResult) HasErrors() bool

HasErrors returns true if any file or edge errors occurred.

func (*BuildResult) Success 

func (r *BuildResult) Success() bool

Success returns true if the build completed without errors and is complete.

func (*BuildResult) TotalErrors 

func (r *BuildResult) TotalErrors() int

TotalErrors returns the total number of errors (file + edge).

type BuildStats 

type BuildStats struct {
	// FilesProcessed is the number of files successfully processed.
	FilesProcessed int

	// FilesFailed is the number of files that failed processing.
	FilesFailed int

	// NodesCreated is the number of nodes added to the graph.
	NodesCreated int

	// EdgesCreated is the number of edges added to the graph.
	EdgesCreated int

	// PlaceholderNodes is the number of placeholder nodes created for
	// external/unresolved symbols.
	PlaceholderNodes int

	// AmbiguousResolves is the number of call resolutions that matched
	// multiple symbols (over-approximated by creating edges to all).
	AmbiguousResolves int

	// DurationMilli is the total build time in milliseconds.
	DurationMilli int64
}

BuildStats contains statistics about a build operation.

type Builder 

type Builder struct {
	// contains filtered or unexported fields
}

Builder constructs code graphs from parsed AST results.

The builder is stateless and can be reused across multiple builds. Each Build() call creates a new graph.

Thread Safety: 

Builder is safe for concurrent use. Each Build() call operates
independently with its own internal state.

func NewBuilder 

func NewBuilder(opts ...BuilderOption) *Builder

NewBuilder creates a new Builder with the given options.

Example: 

builder := NewBuilder(
    WithProjectRoot("/path/to/project"),
    WithMaxMemoryMB(1024),
)

func (*Builder) Build 

func (b *Builder) Build(ctx context.Context, results []*ast.ParseResult) (*BuildResult, error)

Build constructs a graph from the given parse results.

Description: 

Processes all parse results, creating nodes for symbols and edges
for their relationships. The build is resilient to individual file
failures - partial results are returned even on errors.

Inputs: 

ctx - Context for cancellation. Build checks context periodically.
results - Parse results from AST parsing. Nil entries are skipped with error.

Outputs: 

*BuildResult - Contains the graph, any errors, and build statistics.
error - Non-nil only for fatal errors (context cancelled returns partial result).

Build Phases:

  1. COLLECT: Validate and add all symbols as nodes
  2. EXTRACT EDGES: Create edges for imports, calls, implements, etc.
  3. FINALIZE: Freeze graph and compute statistics

type BuilderOption 

type BuilderOption func(*BuilderOptions)

BuilderOption is a functional option for configuring Builder.

func WithBuilderMaxEdges 

func WithBuilderMaxEdges(n int) BuilderOption

WithBuilderMaxEdges sets the maximum number of edges.

func WithBuilderMaxNodes 

func WithBuilderMaxNodes(n int) BuilderOption

WithBuilderMaxNodes sets the maximum number of nodes.

func WithMaxMemoryMB 

func WithMaxMemoryMB(mb int) BuilderOption

WithMaxMemoryMB sets the maximum memory usage in megabytes.

func WithProgressCallback 

func WithProgressCallback(fn ProgressFunc) BuilderOption

WithProgressCallback sets the progress callback function.

func WithProjectRoot 

func WithProjectRoot(root string) BuilderOption

WithProjectRoot sets the project root path.

func WithWorkerCount 

func WithWorkerCount(n int) BuilderOption

WithWorkerCount sets the number of parallel workers.

type BuilderOptions 

type BuilderOptions struct {
	// ProjectRoot is the absolute path to the project root directory.
	ProjectRoot string

	// MaxMemoryMB is the maximum memory usage in megabytes.
	// Build will stop with partial results if exceeded.
	// Default: 512
	MaxMemoryMB int

	// WorkerCount is the number of parallel workers for edge extraction.
	// Default: runtime.NumCPU()
	WorkerCount int

	// ProgressCallback is called periodically with build progress.
	// May be nil.
	ProgressCallback ProgressFunc

	// MaxNodes is the maximum number of nodes (passed to Graph).
	MaxNodes int

	// MaxEdges is the maximum number of edges (passed to Graph).
	MaxEdges int
}

BuilderOptions configures Builder behavior.

func DefaultBuilderOptions 

func DefaultBuilderOptions() BuilderOptions

DefaultBuilderOptions returns sensible defaults.

type Edge 

type Edge struct {
	// FromID is the ID of the source node.
	FromID string

	// ToID is the ID of the target node.
	ToID string

	// Type is the relationship type (calls, imports, etc.).
	Type EdgeType

	// Location is where the relationship is expressed in code.
	Location ast.Location
}

Edge represents a directed relationship between two symbols.

Multiple edges of the same type between the same nodes are allowed, representing different call sites or references in the code. For example, if function A calls function B at lines 10 and 20, there will be two EdgeTypeCalls edges with different Locations.

type EdgeError 

type EdgeError struct {
	// FromID is the source node ID.
	FromID string

	// ToID is the target node ID.
	ToID string

	// EdgeType is the type of edge that failed to create.
	EdgeType EdgeType

	// Err is the underlying error.
	Err error
}

EdgeError represents a failure to create a single edge during graph building.

func (EdgeError) Error 

func (e EdgeError) Error() string

Error implements the error interface.

func (EdgeError) Unwrap 

func (e EdgeError) Unwrap() error

Unwrap returns the underlying error for errors.Is/As support.

type EdgeType 

type EdgeType int

EdgeType defines the type of relationship between symbols. 

const (
	// EdgeTypeUnknown indicates an unrecognized relationship type.
	EdgeTypeUnknown EdgeType = iota

	// EdgeTypeCalls indicates a function/method calls another function/method.
	EdgeTypeCalls

	// EdgeTypeImports indicates a file imports a package.
	EdgeTypeImports

	// EdgeTypeDefines indicates a file defines a symbol.
	EdgeTypeDefines

	// EdgeTypeImplements indicates a type implements an interface.
	EdgeTypeImplements

	// EdgeTypeEmbeds indicates a type embeds another type.
	EdgeTypeEmbeds

	// EdgeTypeReferences indicates a symbol references another symbol (general).
	EdgeTypeReferences

	// EdgeTypeReturns indicates a function returns a type.
	EdgeTypeReturns

	// EdgeTypeReceives indicates a method has a receiver of a type.
	EdgeTypeReceives

	// EdgeTypeParameters indicates a function takes a type as parameter.
	EdgeTypeParameters
)

func (EdgeType) String 

func (t EdgeType) String() string

String returns the string representation of the EdgeType.

type FileError 

type FileError struct {
	// FilePath is the path to the file that failed.
	FilePath string

	// Err is the underlying error.
	Err error
}

FileError represents a failure to process a single file during graph building.

func (FileError) Error 

func (e FileError) Error() string

Error implements the error interface.

func (FileError) Unwrap 

func (e FileError) Unwrap() error

Unwrap returns the underlying error for errors.Is/As support.

type Graph 

type Graph struct {
	// ProjectRoot is the absolute path to the project root directory.
	ProjectRoot string

	// BuiltAtMilli is the Unix timestamp in milliseconds when Freeze() was called.
	// Zero if the graph has not been frozen.
	BuiltAtMilli int64
	// contains filtered or unexported fields
}

Graph represents the code relationship graph for a project.

Thread Safety: 

Graph is NOT safe for concurrent use during building. It is designed
for single-writer access during build, then read-only after Freeze().
After Freeze() is called, the graph can be safely read from multiple
goroutines, but no further modifications are allowed.

Lifecycle:

  1. Create with NewGraph(projectRoot)
  2. Build with AddNode() and AddEdge() calls
  3. Call Freeze() to finalize
  4. Query with GetNode(), traversal methods, etc.

func NewGraph 

func NewGraph(projectRoot string, opts ...GraphOption) *Graph

NewGraph creates a new empty graph for the given project root.

Description: 

Creates a graph in the Building state, ready to accept AddNode and
AddEdge calls. The graph must be frozen with Freeze() before querying.

Inputs: 

projectRoot - Absolute path to the project root directory.
opts - Optional configuration options.

Example: 

// Default options
g := NewGraph("/path/to/project")

// Custom limits
g := NewGraph("/path/to/project",
    WithMaxNodes(100_000),
    WithMaxEdges(1_000_000),
)

func (*Graph) AddEdge 

func (g *Graph) AddEdge(fromID, toID string, edgeType EdgeType, loc ast.Location) error

AddEdge creates a directed edge between two nodes.

Description: 

Creates an edge from the source node to the target node with the
given type and location. Both nodes must already exist in the graph.
Multiple edges of the same type between the same nodes are allowed
(representing different call sites or references).

Inputs: 

fromID - ID of the source node.
toID - ID of the target node.
edgeType - The type of relationship.
loc - Where the relationship is expressed in code.

Outputs: 

error - Non-nil if the graph is frozen, at capacity, or nodes don't exist.

Errors: 

ErrGraphFrozen - Graph has been frozen
ErrNodeNotFound - Source or target node doesn't exist
ErrMaxEdgesExceeded - Graph is at edge capacity

func (*Graph) AddNode 

func (g *Graph) AddNode(symbol *ast.Symbol) (*Node, error)

AddNode adds a symbol as a node in the graph.

Description: 

Creates a new node from the given symbol and adds it to the graph.
The symbol's ID becomes the node's ID.

Inputs: 

symbol - The symbol to add. Must not be nil.

Outputs: 

*Node - The created node. Can be used to inspect Outgoing/Incoming edges.
error - Non-nil if the graph is frozen, at capacity, or symbol is invalid.

Errors: 

ErrGraphFrozen - Graph has been frozen
ErrInvalidNode - Symbol is nil
ErrDuplicateNode - Node with same ID already exists
ErrMaxNodesExceeded - Graph is at node capacity

Ownership: 

The graph stores a pointer to the symbol but does NOT own it.
The symbol MUST NOT be mutated after this call.

func (*Graph) Clone 

func (g *Graph) Clone() *Graph

Clone creates a deep copy of the graph.

Description: 

Creates an independent copy of the graph that can be modified without
affecting the original. Used for copy-on-write incremental updates.

Outputs: 

*Graph - A deep copy of the graph. Always in GraphStateBuilding state
         to allow modifications.

Behavior:

  • Nodes are deep copied (new Node structs, same Symbol pointers)
  • Edges are deep copied (new Edge structs)
  • Edge/node references are updated to point to cloned nodes
  • BuiltAtMilli is preserved from original
  • State is reset to GraphStateBuilding

Thread Safety: 

The returned graph is independent and can be modified without synchronization.

func (*Graph) EdgeCount 

func (g *Graph) EdgeCount() int

EdgeCount returns the number of edges in the graph.

func (*Graph) Edges 

func (g *Graph) Edges() []*Edge

Edges returns a slice of all edges in the graph.

Description: 

Returns the internal edge slice. Callers should NOT modify
the returned slice.

func (*Graph) FindCalleesByID 

func (g *Graph) FindCalleesByID(ctx context.Context, symbolID string, opts ...QueryOption) (*QueryResult, error)

FindCalleesByID returns all symbols called by the given function/method.

Description: 

Finds all functions/methods that the source has CALLS edges to.
Uses symbol ID for unambiguous lookup.

Inputs: 

ctx - Context for cancellation
symbolID - ID of the function/method to find callees for
opts - Query options (Limit, Timeout)

Outputs: 

*QueryResult - Symbols called by the source (empty if none), with metadata
error - Non-nil if context error occurs

func (*Graph) FindCalleesByName 

func (g *Graph) FindCalleesByName(ctx context.Context, name string, opts ...QueryOption) (map[string]*QueryResult, error)

FindCalleesByName returns callees for all symbols matching the given name.

Description: 

When multiple symbols have the same name, this returns callees
for each, keyed by symbol ID.

Inputs: 

ctx - Context for cancellation
name - Symbol name to search for
opts - Query options (Limit per symbol, Timeout)

Outputs: 

map[string]*QueryResult - Symbol ID → callees of that symbol
error - Non-nil if context error occurs

func (*Graph) FindCallersByID 

func (g *Graph) FindCallersByID(ctx context.Context, symbolID string, opts ...QueryOption) (*QueryResult, error)

FindCallersByID returns all symbols that call the given function/method.

Description: 

Finds all functions/methods that have a CALLS edge to the target.
Uses symbol ID for unambiguous lookup.

Inputs: 

ctx - Context for cancellation
symbolID - ID of the function/method to find callers for
opts - Query options (Limit, Timeout)

Outputs: 

*QueryResult - Symbols that call the target (empty if none), with metadata
error - Non-nil if context error occurs

Limitations: 

Only finds direct callers (not transitive)
May miss callers through function pointers/interfaces

func (*Graph) FindCallersByName 

func (g *Graph) FindCallersByName(ctx context.Context, name string, opts ...QueryOption) (map[string]*QueryResult, error)

FindCallersByName returns callers for all symbols matching the given name.

Description: 

When multiple symbols have the same name (e.g., Setup in different packages),
this returns callers for each, keyed by symbol ID.

Inputs: 

ctx - Context for cancellation
name - Symbol name to search for
opts - Query options (Limit per symbol, Timeout)

Outputs: 

map[string]*QueryResult - Symbol ID → callers of that symbol
error - Non-nil if context error occurs

func (*Graph) FindImplementationsByID 

func (g *Graph) FindImplementationsByID(ctx context.Context, interfaceID string, opts ...QueryOption) (*QueryResult, error)

FindImplementationsByID returns all types that implement the given interface.

Description: 

Finds all types that have an IMPLEMENTS edge to the interface.
Uses interface ID for unambiguous lookup.

Inputs: 

ctx - Context for cancellation
interfaceID - ID of the interface to find implementers for
opts - Query options (Limit, Timeout)

Outputs: 

*QueryResult - Types implementing the interface (empty if none)
error - Non-nil if context error occurs

func (*Graph) FindImplementationsByName 

func (g *Graph) FindImplementationsByName(ctx context.Context, name string, opts ...QueryOption) (map[string]*QueryResult, error)

FindImplementationsByName returns implementations for all interfaces matching the given name.

Description: 

When multiple interfaces have the same name, this returns implementers
for each, keyed by interface ID.

Inputs: 

ctx - Context for cancellation
name - Interface name to search for
opts - Query options (Limit per interface, Timeout)

Outputs: 

map[string]*QueryResult - Interface ID → implementers of that interface
error - Non-nil if context error occurs

func (*Graph) FindImporters 

func (g *Graph) FindImporters(ctx context.Context, packagePath string, opts ...QueryOption) ([]string, error)

FindImporters returns all file paths that import the given package.

Description: 

Finds all files that have an IMPORTS edge to nodes in the given package.

Inputs: 

ctx - Context for cancellation
packagePath - Package path to find importers for
opts - Query options (Limit, Timeout)

Outputs: 

[]string - File paths that import the package
error - Non-nil if context error occurs

func (*Graph) FindReferencesByID 

func (g *Graph) FindReferencesByID(ctx context.Context, symbolID string, opts ...QueryOption) ([]ast.Location, error)

FindReferencesByID returns all locations where the given symbol is referenced.

Description: 

Finds all incoming edges to the symbol and returns their locations.
This includes calls, type references, etc.

Inputs: 

ctx - Context for cancellation
symbolID - ID of the symbol to find references for
opts - Query options (Limit, Timeout)

Outputs: 

[]ast.Location - Locations where the symbol is referenced
error - Non-nil if context error occurs

func (*Graph) Freeze 

func (g *Graph) Freeze()

Freeze transitions the graph to read-only mode.

Description: 

After calling Freeze(), AddNode and AddEdge will return ErrGraphFrozen.
This operation is irreversible. The BuiltAtMilli timestamp is set to
the current time.

Thread Safety: 

After Freeze() returns, the graph can be safely read from multiple
goroutines concurrently.

func (*Graph) GetCallGraph 

func (g *Graph) GetCallGraph(ctx context.Context, symbolID string, opts ...QueryOption) (*TraversalResult, error)

GetCallGraph returns the call tree rooted at a function.

Description: 

Performs iterative BFS traversal following CALLS edges up to maxDepth.
Uses iterative approach (not recursive) to handle deep graphs without
stack overflow.

Inputs: 

ctx - Context for cancellation (checked every 100 nodes)
symbolID - Root function ID (must be unambiguous)
opts - Query options including MaxDepth (default: 10, max: 100)

Outputs: 

*TraversalResult - Visited nodes and edges, with Truncated flag
error - Non-nil if root not found

func (*Graph) GetDependencyTree 

func (g *Graph) GetDependencyTree(ctx context.Context, filePath string, opts ...QueryOption) (*TraversalResult, error)

GetDependencyTree returns the dependency tree for a file.

Description: 

Performs iterative BFS traversal following IMPORTS edges up to maxDepth.
Returns all transitive dependencies.

Inputs: 

ctx - Context for cancellation (checked every 100 nodes)
filePath - File path to find dependencies for
opts - Query options including MaxDepth (default: 10, max: 100)

Outputs: 

*TraversalResult - Visited nodes and edges, with Truncated flag
error - Non-nil if file not found in graph

func (*Graph) GetNode 

func (g *Graph) GetNode(id string) (*Node, bool)

GetNode retrieves a node by its ID.

Description: 

Performs O(1) lookup in the node map.

Inputs: 

id - The node ID (same as Symbol.ID).

Outputs: 

*Node - The node if found, nil otherwise.
bool - True if the node was found.

func (*Graph) GetNodesByFile 

func (g *Graph) GetNodesByFile(filePath string) []*Node

GetNodesByFile returns all nodes from a specific file.

Description: 

Returns all nodes where the Symbol's FilePath matches the given path.
Useful for identifying what symbols are defined in a file.

Inputs: 

filePath - The relative file path to search for.

Outputs: 

[]*Node - Nodes from that file. Empty slice if none found.

func (*Graph) GetReverseCallGraph 

func (g *Graph) GetReverseCallGraph(ctx context.Context, symbolID string, opts ...QueryOption) (*TraversalResult, error)

GetReverseCallGraph returns the callers tree rooted at a function.

Description: 

Performs iterative BFS traversal following CALLS edges backwards
(finding callers) up to maxDepth.

Inputs: 

ctx - Context for cancellation (checked every 100 nodes)
symbolID - Root function ID (must be unambiguous)
opts - Query options including MaxDepth (default: 10, max: 100)

Outputs: 

*TraversalResult - Visited nodes and edges, with Truncated flag
error - Non-nil if root not found

func (*Graph) GetTypeHierarchy 

func (g *Graph) GetTypeHierarchy(ctx context.Context, typeID string, opts ...QueryOption) (*TraversalResult, error)

GetTypeHierarchy returns the type hierarchy for a type.

Description: 

Performs iterative BFS traversal following IMPLEMENTS and EMBEDS edges.
Returns all interfaces implemented and types embedded.

Inputs: 

ctx - Context for cancellation (checked every 100 nodes)
typeID - Type ID to find hierarchy for
opts - Query options including MaxDepth (default: 10, max: 100)

Outputs: 

*TraversalResult - Visited nodes and edges, with Truncated flag
error - Non-nil if type not found

func (*Graph) IsFrozen 

func (g *Graph) IsFrozen() bool

IsFrozen returns true if the graph is in read-only mode.

func (*Graph) MergeParseResult 

func (g *Graph) MergeParseResult(result *ast.ParseResult) (int, error)

MergeParseResult adds nodes and edges from a ParseResult.

Description: 

Adds all symbols from the ParseResult as nodes and creates edges
based on import relationships. Used for incremental updates when
adding newly parsed files.

Inputs: 

result - The ParseResult containing symbols to add.

Outputs: 

int - Number of nodes added.
error - Non-nil if the graph is frozen or capacity exceeded.

Errors: 

ErrGraphFrozen - Graph has been frozen
ErrMaxNodesExceeded - Graph is at node capacity
ErrMaxEdgesExceeded - Graph is at edge capacity

Behavior:

  • Adds all top-level symbols as nodes
  • Creates EdgeTypeDefines edges from file node to symbols
  • Skips duplicate nodes (by ID)
  • Does NOT add children (caller should flatten if needed)

Thread Safety: 

NOT safe for concurrent use during modification.

func (*Graph) NodeCount 

func (g *Graph) NodeCount() int

NodeCount returns the number of nodes in the graph.

func (*Graph) Nodes 

func (g *Graph) Nodes() func(yield func(string, *Node) bool)

Nodes returns an iterator function over all nodes in the graph.

Description: 

Returns a function that can be used to iterate over all nodes.
This allows iteration without exposing the internal map.

Example: 

for id, node := range g.Nodes() {
    fmt.Printf("Node: %s\n", id)
}

func (*Graph) RemoveFile 

func (g *Graph) RemoveFile(filePath string) (int, error)

RemoveFile removes all nodes and edges associated with a file.

Description: 

Removes all symbols (nodes) that were defined in the specified file,
along with all edges that reference those nodes. Used for incremental
updates when a file is deleted or modified.

Inputs: 

filePath - The relative file path to remove (must match Symbol.FilePath).

Outputs: 

int - Number of nodes removed.
error - Non-nil if the graph is frozen.

Errors: 

ErrGraphFrozen - Graph has been frozen

Behavior:

  • Removes all nodes where Symbol.FilePath matches
  • Removes all edges where FromID or ToID references removed nodes
  • Updates Incoming/Outgoing slices of remaining nodes

Thread Safety: 

NOT safe for concurrent use during modification.

func (*Graph) ShortestPath 

func (g *Graph) ShortestPath(ctx context.Context, fromID, toID string) (*PathResult, error)

ShortestPath finds the shortest path between two symbols.

Description: 

Uses BFS to find minimum-edge path. Considers all edge types.
Returns immediately if fromID == toID (path of length 0).

Inputs: 

ctx - Context for cancellation
fromID - Starting node ID
toID - Target node ID

Outputs: 

*PathResult - Path details or empty if no path exists
error - Non-nil if nodes not found

func (*Graph) State 

func (g *Graph) State() GraphState

State returns the current lifecycle state of the graph.

func (*Graph) Stats 

func (g *Graph) Stats() GraphStats

Stats returns statistics about the graph.

func (*Graph) Validate 

func (g *Graph) Validate() error

Validate checks that the graph is in a consistent state for querying.

Description: 

Verifies all edges reference existing nodes. Should be called once
after build, before queries. Queries will return error if validation
fails.

Outputs: 

error - Non-nil if graph is corrupt (dangling edges)

Example: 

if err := graph.Validate(); err != nil {
    return fmt.Errorf("graph corrupt: %w", err)
}

type GraphOption 

type GraphOption func(*GraphOptions)

GraphOption is a functional option for configuring Graph.

func WithMaxEdges 

func WithMaxEdges(n int) GraphOption

WithMaxEdges sets the maximum number of edges the graph can hold.

func WithMaxNodes 

func WithMaxNodes(n int) GraphOption

WithMaxNodes sets the maximum number of nodes the graph can hold.

type GraphOptions 

type GraphOptions struct {
	// MaxNodes is the maximum number of nodes the graph can hold.
	// Default: 1,000,000
	MaxNodes int

	// MaxEdges is the maximum number of edges the graph can hold.
	// Default: 10,000,000
	MaxEdges int
}

GraphOptions configures Graph behavior and limits.

func DefaultGraphOptions 

func DefaultGraphOptions() GraphOptions

DefaultGraphOptions returns sensible defaults for graph configuration.

type GraphState 

type GraphState int

GraphState represents the lifecycle state of the graph. 

const (
	// GraphStateBuilding indicates the graph is accepting AddNode/AddEdge calls.
	GraphStateBuilding GraphState = iota

	// GraphStateReadOnly indicates the graph is frozen and read-only.
	GraphStateReadOnly
)

func (GraphState) String 

func (s GraphState) String() string

String returns the string representation of the GraphState.

type GraphStats 

type GraphStats struct {
	// NodeCount is the total number of nodes.
	NodeCount int

	// EdgeCount is the total number of edges.
	EdgeCount int

	// EdgesByType maps each EdgeType to the count of edges of that type.
	EdgesByType map[EdgeType]int

	// MaxNodes is the configured maximum node capacity.
	MaxNodes int

	// MaxEdges is the configured maximum edge capacity.
	MaxEdges int

	// State is the current graph state.
	State GraphState

	// BuiltAtMilli is when Freeze() was called (0 if not frozen).
	BuiltAtMilli int64
}

GraphStats contains statistics about the graph.

type Node 

type Node struct {
	// ID is the unique identifier, same as Symbol.ID.
	ID string

	// Symbol is the underlying symbol from AST parsing.
	// This pointer is NOT owned by the Node.
	Symbol *ast.Symbol

	// Outgoing contains edges where this node is the source.
	// For example, if this node is a function, Outgoing contains
	// all the functions it calls.
	Outgoing []*Edge

	// Incoming contains edges where this node is the target.
	// For example, if this node is a function, Incoming contains
	// all the functions that call it.
	Incoming []*Edge
}

Node represents a symbol in the code graph with its relationships.

The Symbol pointer is NOT owned by the Node. The referenced Symbol MUST NOT be mutated after the Node is added to a Graph.

type PathResult 

type PathResult struct {
	// From is the starting node ID.
	From string

	// To is the target node ID.
	To string

	// Path contains node IDs in path order, including From and To.
	// Empty if no path exists.
	Path []string

	// Length is the number of edges in the path.
	// -1 if no path exists.
	Length int
}

PathResult contains the result of a shortest path query.

type ProgressFunc 

type ProgressFunc func(progress BuildProgress)

ProgressFunc is a callback function for build progress updates.

type ProgressPhase 

type ProgressPhase int

ProgressPhase indicates which phase of building is in progress. 

const (
	// ProgressPhaseCollecting indicates symbols are being collected as nodes.
	ProgressPhaseCollecting ProgressPhase = iota

	// ProgressPhaseExtractingEdges indicates edges are being extracted.
	ProgressPhaseExtractingEdges

	// ProgressPhaseFinalizing indicates the graph is being finalized.
	ProgressPhaseFinalizing
)

func (ProgressPhase) String 

func (p ProgressPhase) String() string

String returns the string representation of the ProgressPhase.

type QueryOption 

type QueryOption func(*QueryOptions)

QueryOption is a functional option for configuring queries.

func WithLimit 

func WithLimit(n int) QueryOption

WithLimit sets the maximum number of results.

If n <= 0, uses default (1000). If n > 10000, clamps to 10000.

func WithMaxDepth 

func WithMaxDepth(d int) QueryOption

WithMaxDepth sets the maximum traversal depth.

If d < 0, uses default (10). If d > 100, clamps to 100.

func WithTimeout 

func WithTimeout(d time.Duration) QueryOption

WithTimeout sets the per-query timeout.

type QueryOptions 

type QueryOptions struct {
	// Limit is the maximum number of results (default: 1000, max: 10000).
	Limit int

	// MaxDepth is the maximum traversal depth (default: 10, max: 100).
	MaxDepth int

	// Timeout is the per-query timeout (0 = use context deadline).
	Timeout time.Duration
}

QueryOptions configures query behavior.

func DefaultQueryOptions 

func DefaultQueryOptions() QueryOptions

DefaultQueryOptions returns sensible defaults for queries.

type QueryResult 

type QueryResult struct {
	// Symbols contains the matching symbols.
	Symbols []*ast.Symbol

	// Truncated is true if limit was reached or context was cancelled.
	Truncated bool

	// Duration is the query execution time.
	Duration time.Duration
}

QueryResult wraps query results with metadata.

type TraversalResult 

type TraversalResult struct {
	// StartNode is the ID of the node where traversal began.
	StartNode string

	// VisitedNodes contains IDs of all visited nodes in traversal order.
	VisitedNodes []string

	// Edges contains all edges that were traversed.
	Edges []*Edge

	// Depth is the maximum depth reached during traversal.
	Depth int

	// Truncated indicates the traversal was stopped early due to
	// limit, depth, or context cancellation.
	Truncated bool
}

TraversalResult contains the results of a graph traversal query.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.