graph

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Mar 11, 2026 License: AGPL-3.0 Imports: 47 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 (2048MB).
	// GR-77: Raised from 512 to 2048 so edge extraction completes for
	// projects up to ~2M LOC. Will be removed when GR-77 (bbolt disk-backed
	// graph) eliminates the in-memory architecture.
	DefaultMaxMemoryMB = 2048

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

Default builder configuration values.

View Source 
const (
	// DefaultMaxLeidenIterations is the maximum outer loop iterations.
	DefaultMaxLeidenIterations = 100

	// DefaultConvergenceThreshold stops early if modularity gain < this.
	DefaultConvergenceThreshold = 1e-6

	// DefaultMinCommunitySize filters out tiny communities from results.
	DefaultMinCommunitySize = 1

	// DefaultResolution affects community granularity.
	// Higher values = smaller communities, lower = larger communities.
	DefaultResolution = 1.0
)

Leiden configuration constants.

View Source 
const (
	// LevelProject represents the project (root) level.
	LevelProject = 0

	// LevelPackage represents the package level.
	LevelPackage = 1

	// LevelFile represents the file level.
	LevelFile = 2

	// LevelSymbol represents the symbol (function/type/etc) level.
	LevelSymbol = 3
)

HierarchyLevel represents a level in the code hierarchy.

View Source 
const (
	// DefaultDampingFactor is the probability of following a link (vs random jump).
	// Standard value from the original PageRank paper.
	DefaultDampingFactor = 0.85

	// DefaultMaxIterations is the maximum iterations before stopping.
	DefaultMaxIterations = 100

	// DefaultConvergence is the threshold for convergence detection.
	// Power iteration stops when max score change < this value.
	DefaultConvergence = 1e-6

	// SmallGraphThreshold is the node count below which we skip convergence checks.
	SmallGraphThreshold = 10
)

PageRank configuration constants.

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.

View Source 
const BboltSchemaVersion = "1.0"

BboltSchemaVersion is the version of the bbolt serialization schema. Increment when the bbolt format changes in a breaking way. GR-77a: Decode failure triggers delete + rebuild.

View Source 
const (
	// DefaultMaxDominatorIterations caps convergence iterations.
	DefaultMaxDominatorIterations = 100
)

Default configuration for dominator algorithm.

View Source 
const (
	// DefaultQueryCacheSize is the default LRU cache size for query results.
	DefaultQueryCacheSize = 1000
)

Query cache configuration.

View Source 
const GraphSchemaVersion = "1.0"

GraphSchemaVersion is the version of the serialization schema. Increment when the serialization format changes in a breaking way.

View Source 
const (
	// HLDSchemaVersion is the current HLD schema version (A-M1).
	// Increment when making breaking changes to serialization format.
	HLDSchemaVersion = 1
)
View Source 
const IncrementalRefreshThreshold = 0.30

IncrementalRefreshThreshold is the maximum ratio of changed files to total files before falling back to a full rebuild. If changedFiles/totalFiles > 0.30, incremental overhead exceeds full build cost.

View Source 
const StalenessCheckCacheTTL = 60 * time.Second

StalenessCheckCacheTTL is how long a staleness result is cached before rechecking.

View Source 
const StalenessCheckSampleSize = 50

StalenessCheckSampleSize is the number of files to spot-check per staleness check. Checking 50 files keeps the check under 50ms on typical systems.

View Source 
const StalenessErrorThreshold = 0.20

StalenessErrorThreshold is the percentage of changed files that triggers an error log suggesting a graph rebuild. Below this, a warning is logged.

View Source 
const VirtualExitNodeID = "__virtual_exit__"

VirtualExitNodeID is the sentinel ID for the virtual exit node used when handling graphs with multiple exits. It is filtered from results.

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")

	// ErrNilGraph is returned when attempting to wrap a nil graph.
	ErrNilGraph = errors.New("graph must not be nil")

	// ErrGraphNotFrozen is returned when attempting to wrap a graph that
	// has not been frozen yet. The graph must be frozen (read-only) before
	// wrapping with HierarchicalGraph.
	ErrGraphNotFrozen = errors.New("graph must be frozen before wrapping")
)

Sentinel errors for graph operations.

View Source 
var (
	ErrInvalidTree      = errors.New("graph is not a valid tree")
	ErrValidationFailed = errors.New("HLD validation failed")
)

Sentinel errors for HLD operations.

View Source 
var (
	ErrNodesInDifferentTrees  = errors.New("cannot compute LCA: nodes are in different tree components")
	ErrIterationLimitExceeded = errors.New("LCA iteration limit exceeded")
	ErrHLDNotInitialized      = errors.New("HLD not properly initialized") // I-C1
)

Sentinel errors for LCA operations.

View Source 
var (
	ErrEmptyArray        = errors.New("array must not be empty")
	ErrArrayTooLarge     = errors.New("array size exceeds maximum")
	ErrInvalidAggFunc    = errors.New("invalid aggregation function")
	ErrInvalidRange      = errors.New("invalid query range")
	ErrRangeUpdateNotSUM = errors.New("range update only supported for SUM aggregation")
)

Sentinel errors for segment tree operations.

Functions

func GetCorrelationID 

func GetCorrelationID(ctx context.Context) string

GetCorrelationID extracts correlation ID from OpenTelemetry trace context.

Description: 

Returns the OTel trace ID as a correlation ID for linking logs and traces.
This provides automatic correlation without custom context keys.

Inputs:

  • ctx: Context with optional OTel span. Can be nil (returns empty string).

Outputs:

  • string: Trace ID in hex format, or empty string if no valid span context.

Thread Safety: Safe for concurrent use.

Example: 

correlationID := GetCorrelationID(ctx)
logger.Info("query complete", slog.String("correlation_id", correlationID))

func LevelName 

func LevelName(level int) string

LevelName returns the human-readable name for a hierarchy level.

func NullLogger 

func NullLogger() *slog.Logger

NullLogger returns a logger that discards all output.

func ProjectHash 

func ProjectHash(projectRoot string) string

ProjectHash returns SHA256(projectRoot)[:16] for use as a key prefix.

Description: 

Computes a deterministic, URL-safe hash of the project root path for
use as a BadgerDB key prefix. Exported so handlers can convert a
project_root query param to the hash used in storage.

Inputs: 

projectRoot - The project root path.

Outputs: 

string - 16-character hex hash.

func RecordFileMtimes 

func RecordFileMtimes(g *Graph, projectRoot string)

RecordFileMtimes populates a graph's FileMtimes field by stat'ing all files referenced in the graph's nodes.

Description: 

Iterates all nodes in the graph, collects unique file paths, stats each
file, and records its modification time. Should be called after Freeze().

Inputs:

  • g: The graph to populate. Must not be nil.
  • projectRoot: Absolute path to the project root.

Thread Safety: Must be called during build (before concurrent reads).

func ShouldDoIncrementalUpdate 

func ShouldDoIncrementalUpdate(changedCount, totalCount int) bool

ShouldDoIncrementalUpdate determines whether an incremental update is appropriate.

Description: 

Returns true if the ratio of changed files to total files is at or below
the IncrementalRefreshThreshold (30%). Returns false if totalFiles is 0
to avoid division by zero.

Inputs:

  • changedCount: Number of files that changed since last snapshot.
  • totalCount: Total number of files in the project.

Outputs:

  • bool: true if incremental update should be used.

Thread Safety: Safe for concurrent use (stateless).

Types

type AggregateFunc 

type AggregateFunc int

AggregateFunc defines the type of aggregation operation. 

const (
	AggregateSUM AggregateFunc = iota // Sum of values
	AggregateMIN                      // Minimum value
	AggregateMAX                      // Maximum value
	AggregateGCD                      // Greatest common divisor
)

func (AggregateFunc) Combine 

func (f AggregateFunc) Combine(a, b int64) int64

Combine applies the aggregation function to two values.

Description: 

Combines two values using the aggregation function. Handles integer
overflow for SUM by saturating at MaxInt64/MinInt64.

Thread Safety: Safe for concurrent use (pure function).

func (AggregateFunc) Identity 

func (f AggregateFunc) Identity() int64

Identity returns the identity element for the aggregation function.

func (AggregateFunc) String 

func (f AggregateFunc) String() string

String returns the string representation of the aggregation function.

type ArticulationResult 

type ArticulationResult struct {
	// Points contains node IDs that are articulation points.
	// An articulation point is a node whose removal increases the number
	// of connected components in the graph.
	Points []string

	// Bridges contains edges whose removal disconnects the graph.
	// Each bridge is represented as [fromID, toID].
	Bridges [][2]string

	// Components is the number of connected components in the graph.
	// For a fully connected graph, this equals 1. For disconnected graphs,
	// this equals the number of separate subgraphs.
	Components int

	// NodeCount is the total nodes analyzed.
	NodeCount int

	// EdgeCount is the total edges analyzed.
	EdgeCount int
}

ArticulationResult contains the articulation point analysis.

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, including truncated.

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), including truncated.

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

	// GoInterfaceEdges is the number of EdgeTypeImplements edges created
	// via Go interface implementation detection (method-set matching).
	// See GR-40 for details.
	GoInterfaceEdges int

	// CallEdgesResolved is the number of EdgeTypeCalls edges where the
	// target was successfully resolved to an existing symbol.
	// See GR-41 for details.
	CallEdgesResolved int

	// CallEdgesUnresolved is the number of EdgeTypeCalls edges where the
	// target could not be resolved and a placeholder was created.
	// See GR-41 for details.
	CallEdgesUnresolved int

	// NamedImportEdgesResolved is the number of EdgeTypeReferences edges
	// created by the named import resolution pass (GR-62). Each represents
	// a "from X import Y" statement where Y was resolved to an in-project
	// symbol node.
	NamedImportEdgesResolved int

	// CommonJSImportEdgesResolved is the number of EdgeTypeReferences edges
	// created by the CommonJS import alias resolution pass (IT-06d Bug D).
	// Each represents a "var X = require('./module')" statement where the
	// imported module's exported class was found and linked.
	CommonJSImportEdgesResolved int

	// DynamicImportEdgesResolved is the number of EdgeTypeReferences edges
	// created by the dynamic import() resolution pass (IT-06e Bug 4).
	// Each represents an import('./module') call where the dynamically loaded
	// module's exported class was found and linked to the importing file.
	DynamicImportEdgesResolved int

	// DecoratorArgEdgesResolved is the number of EdgeTypeReferences edges
	// created by the decorator argument resolution pass (IT-06e Bug 5).
	// Each represents a class name in a @Module({providers: [X]}) or
	// @NgModule({imports: [X]}) decorator array that resolved to an in-project symbol.
	DecoratorArgEdgesResolved int

	// DurationMilli is the total build time in milliseconds.
	// NOTE: For fast builds (< 1ms), this rounds to 0. Use DurationMicro for precision.
	DurationMilli int64

	// DurationMicro is the total build time in microseconds (for sub-millisecond precision).
	DurationMicro int64

	// FileErrorsTruncated is the number of file errors dropped after the cap was reached.
	// See maxErrorSliceLen.
	FileErrorsTruncated int

	// EdgeErrorsTruncated is the number of edge errors dropped after the cap was reached.
	// See maxErrorSliceLen.
	EdgeErrorsTruncated int

	// ValidationBypassed is the number of edge validation checks that were bypassed
	// because one or both symbols were not in the symbolsByID map (e.g., placeholder nodes).
	// GR-71: Tracked for observability — a high count may indicate placeholder ID issues.
	ValidationBypassed int

	// ValidationRejected is the number of edges rejected by validateEdgeType because
	// the edge type was invalid for the source/target node kinds.
	// GR-71: Tracked for observability — helps diagnose false-positive edge creation.
	ValidationRejected int

	// LSPEnrichment contains statistics from the LSP enrichment phase (GR-74).
	// Zero-valued if LSP enrichment was not configured or not run.
	LSPEnrichment EnrichmentStats
}

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.
  Always non-nil, even when error is returned (partial result for debugging).
error - Non-nil when context is cancelled/expired or memory limit exceeded.
  Wraps the underlying error (ctx.Err() or ErrMemoryLimitExceeded).

Build Phases:

  1. COLLECT: Validate and add all symbols as nodes
  2. EXTRACT EDGES: Create edges for imports, calls, implements, etc.
  3. LSP ENRICHMENT (optional): Resolve placeholder targets via LSP definition lookup (GR-74)
  4. 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 WithLSPEnrichment 

func WithLSPEnrichment(config *LSPEnrichmentConfig) BuilderOption

WithLSPEnrichment configures LSP-based placeholder resolution.

Description: 

GR-74: When set, the builder runs an LSP enrichment phase between edge
extraction and finalization. This phase queries language servers for
unresolved placeholder targets, converting them into real edges.

Inputs: 

config - LSP enrichment configuration. If nil or Querier is nil, enrichment is skipped.

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. GR-73: Must be goroutine-safe — with WorkerCount > 1,
	// this callback may be invoked from multiple goroutines concurrently.
	// Progress reports may arrive out-of-order.
	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

	// LSPEnrichment configures optional LSP-based placeholder resolution.
	// GR-74: When non-nil with a valid Querier, an enrichment phase runs
	// between edge extraction and finalization.
	LSPEnrichment *LSPEnrichmentConfig
}

BuilderOptions configures Builder behavior.

func DefaultBuilderOptions 

func DefaultBuilderOptions() BuilderOptions

DefaultBuilderOptions returns sensible defaults.

type CRSGraphAdapter 

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

CRSGraphAdapter provides read-only access to the code graph from CRS activities.

Description: 

CRSGraphAdapter wraps the HierarchicalGraph, GraphAnalytics, and SymbolIndex
to provide a clean interface for CRS activities to query the code graph.
It handles:
  - Lifecycle management (closed state detection)
  - Generation tracking for staleness detection
  - Analytics caching with TTL and singleflight deduplication
  - O(1) symbol lookups via SymbolIndex
  - OTel tracing for all queries

Thread Safety: All methods are safe for concurrent use.

func NewCRSGraphAdapter 

func NewCRSGraphAdapter(g *HierarchicalGraph, idx *index.SymbolIndex, generation int64, refreshTime int64, config *crs.GraphQueryConfig) (*CRSGraphAdapter, error)

NewCRSGraphAdapter creates a new adapter for querying the graph from CRS.

Description: 

Creates an adapter that wraps the graph, analytics, and optional symbol index
for CRS use. The adapter tracks the graph generation for staleness detection.

Inputs:

  • g: The hierarchical graph to wrap. Must not be nil.
  • idx: Optional symbol index for O(1) lookups. May be nil.
  • generation: The graph generation number.
  • refreshTime: When the graph was last refreshed (Unix milliseconds UTC).
  • config: Optional configuration. Uses defaults if nil.

Outputs:

  • *CRSGraphAdapter: The adapter. Never nil if g is not nil.
  • error: Non-nil if g is nil.

Example: 

adapter, err := NewCRSGraphAdapter(graph, symbolIndex, gen, refreshTime, nil)
if err != nil {
    return fmt.Errorf("creating graph adapter: %w", err)
}
defer adapter.Close()

Limitations:

  • Adapter does not own the graph or index lifecycle
  • Graph mutations after adapter creation may cause stale results

Thread Safety: The returned adapter is safe for concurrent use.

func (*CRSGraphAdapter) Analytics 

func (a *CRSGraphAdapter) Analytics() crs.GraphAnalyticsQuery

Analytics returns the analytics query interface.

Outputs:

  • crs.GraphAnalyticsQuery: The analytics interface. Never nil.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) CallEdgeCount 

func (a *CRSGraphAdapter) CallEdgeCount(ctx context.Context) (int, error)

CallEdgeCount returns the number of CALLS edges in the graph.

Description: 

Counts edges of type EdgeTypeCalls. This is used by the dependency
index Size() method. Results are cached and invalidated when
InvalidateCache() is called.

Inputs:

  • ctx: Context for cancellation.

Outputs:

  • int: Number of call edges.
  • error: Non-nil on context cancellation or if adapter is closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) Close 

func (a *CRSGraphAdapter) Close() error

Close releases resources held by the adapter.

Description: 

Must be called when the adapter is no longer needed to prevent
resource leaks. After Close, all methods return ErrGraphQueryClosed.

Thread Safety: Safe for concurrent use. Idempotent.

func (*CRSGraphAdapter) EdgeCount 

func (a *CRSGraphAdapter) EdgeCount() int

EdgeCount returns the number of edges in the graph.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) FindCallees 

func (a *CRSGraphAdapter) FindCallees(ctx context.Context, symbolID string) ([]*ast.Symbol, error)

FindCallees returns symbols that the given symbol calls.

Description: 

Finds all symbols that are called by the source symbol via outgoing call edges.
GR-10: Uses LRU cache to avoid recomputation for repeated queries.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • symbolID: The symbol to find callees for.

Outputs:

  • []*ast.Symbol: Callee symbols. Empty slice if none found.
  • error: Non-nil on graph query failure or adapter closed.

Limitations:

  • GR-10 Review (I-1): Results may be cached. Callers MUST NOT mutate the returned slice or its elements, as this would corrupt the cache.
  • Truncated results (when limit is reached) are not cached.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) FindCallers 

func (a *CRSGraphAdapter) FindCallers(ctx context.Context, symbolID string) ([]*ast.Symbol, error)

FindCallers returns symbols that call the given symbol.

Description: 

Finds all symbols that have outgoing call edges to the target symbol.
GR-10: Uses LRU cache to avoid recomputation for repeated queries.
If SymbolIndex is available, uses O(1) lookup; otherwise falls back to
graph traversal.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • symbolID: The symbol to find callers for.

Outputs:

  • []*ast.Symbol: Caller symbols. Empty slice if none found.
  • error: Non-nil on graph query failure or adapter closed.

Limitations:

  • GR-10 Review (I-1): Results may be cached. Callers MUST NOT mutate the returned slice or its elements, as this would corrupt the cache.
  • Truncated results (when limit is reached) are not cached.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) FindImplementations 

func (a *CRSGraphAdapter) FindImplementations(ctx context.Context, interfaceName string) ([]*ast.Symbol, error)

FindImplementations returns types that implement the given interface.

Description: 

Finds all types that implement the specified interface by name.
Searches across all matching interface definitions.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • interfaceName: The interface name to find implementations for.

Outputs:

  • []*ast.Symbol: Implementing types. Empty slice if none found.
  • error: Non-nil on graph query failure or adapter closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) FindReferences 

func (a *CRSGraphAdapter) FindReferences(ctx context.Context, symbolID string) ([]*ast.Symbol, error)

FindReferences returns symbols that reference the given symbol.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • symbolID: The symbol to find references for.

Outputs:

  • []*ast.Symbol: Referencing symbols. Empty slice if none found.
  • error: Non-nil on graph query failure or adapter closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) FindSymbolByID 

func (a *CRSGraphAdapter) FindSymbolByID(ctx context.Context, id string) (*ast.Symbol, bool, error)

FindSymbolByID returns a symbol by its unique ID.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • id: The unique symbol ID.

Outputs:

  • *ast.Symbol: The symbol, or nil if not found.
  • bool: True if symbol was found.
  • error: Non-nil on context cancellation or adapter closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) FindSymbolsByKind 

func (a *CRSGraphAdapter) FindSymbolsByKind(ctx context.Context, kind ast.SymbolKind) ([]*ast.Symbol, error)

FindSymbolsByKind returns all symbols of the given kind.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • kind: The symbol kind to filter by.

Outputs:

  • []*ast.Symbol: Matching symbols. Empty slice if none found.
  • error: Non-nil on context cancellation or adapter closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) FindSymbolsByName 

func (a *CRSGraphAdapter) FindSymbolsByName(ctx context.Context, name string) ([]*ast.Symbol, error)

FindSymbolsByName returns all symbols with the given name.

Description: 

GR-06: Uses nodesByName secondary index for O(1) lookup instead of
O(V) scan. Multiple symbols can share a name (e.g., "Setup" in
different packages).

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • name: The symbol name to search for.

Outputs:

  • []*ast.Symbol: Matching symbols. Empty slice if none found.
  • error: Non-nil on context cancellation or adapter closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) FindSymbolsInFile 

func (a *CRSGraphAdapter) FindSymbolsInFile(ctx context.Context, filePath string) ([]*ast.Symbol, error)

FindSymbolsInFile returns all symbols in the given file.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • filePath: The file path to search in.

Outputs:

  • []*ast.Symbol: Symbols in the file. Empty slice if none found.
  • error: Non-nil on context cancellation or adapter closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) Generation 

func (a *CRSGraphAdapter) Generation() int64

Generation returns the graph generation this adapter was created with.

Description: 

Use for staleness detection. If the current graph generation is higher
than this value, the adapter may return stale data.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) GetCallChain 

func (a *CRSGraphAdapter) GetCallChain(ctx context.Context, fromID, toID string, maxDepth int) ([]string, error)

GetCallChain returns the call chain from source to target.

Description: 

Finds the path from source to target following call edges. Uses BFS
for path finding to ensure shortest path.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • fromID: The source symbol ID.
  • toID: The target symbol ID.
  • maxDepth: Maximum traversal depth. Clamped to [1, 100].

Outputs:

  • []string: Symbol IDs in the call chain. Empty if no path found.
  • error: Non-nil on graph query failure or adapter closed.

Example: 

path, err := adapter.GetCallChain(ctx, "main.go:10:main", "util.go:20:helper", 10)
if err != nil {
    return fmt.Errorf("getting call chain: %w", err)
}

Limitations:

  • Only follows call edges, not other edge types
  • maxDepth is clamped to prevent runaway traversal

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) GetEdgeCountByFile 

func (a *CRSGraphAdapter) GetEdgeCountByFile(ctx context.Context, filePath string) (int, error)

GetEdgeCountByFile returns the count of edges with Location in the given file.

Description: 

GR-09: Uses secondary index for O(1) count without copying edges.
More efficient than len(GetEdgesByFile()) for just getting counts.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • filePath: The file path to count edges for.

Outputs:

  • int: Number of edges with Location in the file.
  • error: Non-nil on context cancellation or adapter closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) GetEdgesByFile 

func (a *CRSGraphAdapter) GetEdgesByFile(ctx context.Context, filePath string) ([]*Edge, error)

GetEdgesByFile returns all edges with Location in the given file.

Description: 

GR-09: Uses edgesByFile secondary index for O(1) lookup instead of
O(E) scan. Useful for file-scoped dependency analysis.
Note: Returns edges by their Location.FilePath (where the edge is
expressed in code), not by source or target node file.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • filePath: The file path to find edges for.

Outputs:

  • []*Edge: Edges with Location in the file. Empty slice if none found.
  • error: Non-nil on context cancellation or adapter closed.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) HasCycleFrom 

func (a *CRSGraphAdapter) HasCycleFrom(ctx context.Context, symbolID string) (bool, error)

HasCycleFrom checks if there's a cycle in the call graph starting from the given symbol.

Description: 

Uses depth-first search with a recursion stack to detect cycles in the
call graph. Only follows EdgeTypeCalls edges.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • symbolID: The starting symbol ID to check for cycles from.

Outputs:

  • bool: True if a cycle is detected, false otherwise.
  • error: Non-nil on context cancellation or if adapter is closed.

Example: 

hasCycle, err := adapter.HasCycleFrom(ctx, "pkg.Function")
if err != nil {
    return fmt.Errorf("cycle check: %w", err)
}
if hasCycle {
    log.Warn("recursive call detected")
}

Limitations:

  • Only detects cycles through direct CALLS edges
  • May miss cycles through function pointers or interfaces
  • Performance: O(V + E) where V=nodes reachable, E=edges traversed

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) InvalidateCache 

func (a *CRSGraphAdapter) InvalidateCache()

InvalidateCache clears all cached analytics and query results.

Description: 

Call this when the underlying graph has been refreshed to ensure
subsequent queries return fresh data. This is typically called by
the graph refresh event handler.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) LastRefreshTime 

func (a *CRSGraphAdapter) LastRefreshTime() int64

LastRefreshTime returns when the graph was last refreshed (Unix milliseconds UTC).

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) NodeCount 

func (a *CRSGraphAdapter) NodeCount() int

NodeCount returns the number of nodes in the graph.

Thread Safety: Safe for concurrent use.

func (*CRSGraphAdapter) QueryCacheStats 

func (a *CRSGraphAdapter) QueryCacheStats() QueryCacheStats

QueryCacheStats returns statistics for the query caches.

Description: 

Returns hit/miss counts and sizes for all query caches (callers,
callees, paths). Useful for monitoring cache effectiveness and
sizing decisions.

Outputs:

  • QueryCacheStats: Cache statistics snapshot.

Example: 

stats := adapter.QueryCacheStats()
if stats.HitRate < 0.5 {
    log.Warn("low cache hit rate", "rate", stats.HitRate)
}

Limitations:

  • Stats are a point-in-time snapshot; may be slightly stale
  • Hit rate calculation uses integer counts, may lose precision

Thread Safety: Safe for concurrent use. Returns atomic snapshot.

func (*CRSGraphAdapter) ShortestPath 

func (a *CRSGraphAdapter) ShortestPath(ctx context.Context, fromID, toID string) ([]string, error)

ShortestPath returns the shortest path between two symbols.

Description: 

Finds the shortest path between two symbols considering all edge types.
Uses BFS for unweighted shortest path.
GR-10: Uses LRU cache to avoid recomputation for repeated queries.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • fromID: The source symbol ID.
  • toID: The target symbol ID.

Outputs:

  • []string: Symbol IDs in the path. Empty if no path found.
  • error: Non-nil on graph query failure or adapter closed.

Limitations:

  • GR-10 Review (I-1): Results may be cached. Callers MUST NOT mutate the returned slice, as this would corrupt the cache.
  • Returns error if source or target node does not exist.

Thread Safety: Safe for concurrent use.

type CacheStats 

type CacheStats struct {
	Hits      int64 // Total cache hits
	Misses    int64 // Total cache misses
	Evictions int64 // Total evictions
	Size      int   // Current number of cached entries
	MemoryKB  int   // Approximate memory usage in KB
}

CacheStats contains cache performance metrics.

type CircuitBreaker 

type CircuitBreaker interface {
	// Execute runs the function if circuit is closed, returns error if open.
	Execute(fn func() error) error

	// State returns current circuit state.
	State() CircuitState

	// Stats returns circuit breaker statistics.
	Stats() CircuitBreakerStats
}

CircuitBreaker prevents cascading failures.

Description: 

Implements circuit breaker pattern with three states:
- Closed: Normal operation, all requests pass through
- Open: Failing fast, no requests allowed
- Half-Open: Testing if service recovered

Thread Safety: All methods must be safe for concurrent use.

type CircuitBreakerStats 

type CircuitBreakerStats struct {
	State               CircuitState
	TotalRequests       int64
	SuccessfulRequests  int64
	FailedRequests      int64
	RejectedRequests    int64 // Rejected due to open circuit
	ConsecutiveFailures int64
	LastStateChange     int64 // Unix milliseconds UTC
}

CircuitBreakerStats contains circuit breaker metrics.

type CircuitState 

type CircuitState int

CircuitState represents circuit breaker state. 

const (
	CircuitClosed   CircuitState = 0 // Normal operation
	CircuitOpen     CircuitState = 1 // Failing fast
	CircuitHalfOpen CircuitState = 2 // Testing recovery
)

func (CircuitState) String 

func (s CircuitState) String() string

type Community 

type Community struct {
	// ID is the unique identifier for this community.
	ID int `json:"id"`

	// Nodes contains the node IDs in this community.
	Nodes []string `json:"nodes"`

	// DominantPackage is the most common package in this community.
	DominantPackage string `json:"dominant_package"`

	// InternalEdges is the count of edges within this community.
	InternalEdges int `json:"internal_edges"`

	// ExternalEdges is the count of edges to other communities.
	ExternalEdges int `json:"external_edges"`

	// Connectivity is the internal density measure (internal / (internal + external)).
	Connectivity float64 `json:"connectivity"`
}

Community represents a detected code module.

type CommunityResult 

type CommunityResult struct {
	// Communities contains all detected communities.
	Communities []Community `json:"communities"`

	// Modularity is the final modularity score Q.
	// Range [0, 1] where higher is better.
	Modularity float64 `json:"modularity"`

	// Iterations is the number of outer loop passes completed.
	Iterations int `json:"iterations"`

	// Converged indicates whether the algorithm converged before MaxIterations.
	Converged bool `json:"converged"`

	// NodeCount is the total nodes analyzed.
	NodeCount int `json:"node_count"`

	// EdgeCount is the total edges analyzed.
	EdgeCount int `json:"edge_count"`
}

CommunityResult contains the full Leiden output.

func (*CommunityResult) GetCommunityForNode 

func (r *CommunityResult) GetCommunityForNode(nodeID string) (int, bool)

GetCommunityForNode returns the community ID for a node.

Inputs: 

nodeID - The node ID to look up.

Outputs: 

int - The community ID.
bool - True if the node was found in a community.

func (*CommunityResult) GetCommunityMembers 

func (r *CommunityResult) GetCommunityMembers(communityID int) []string

GetCommunityMembers returns all nodes in a community.

Inputs: 

communityID - The community ID to look up.

Outputs: 

[]string - Node IDs in the community. Empty if not found.

type ControlDependence 

type ControlDependence struct {
	// Dependencies maps node → nodes it is control-dependent on.
	// "What controls whether this node executes?"
	Dependencies map[string][]string

	// Dependents maps node → nodes that are control-dependent on it.
	// "What does this node control the execution of?"
	Dependents map[string][]string

	// EdgeCount is the total control dependence edges.
	EdgeCount int

	// NodeCount is the total nodes analyzed.
	NodeCount int

	// NodesWithDependencies is the count of nodes with non-empty Dependencies.
	NodesWithDependencies int

	// NodesWithDependents is the count of nodes with non-empty Dependents.
	NodesWithDependents int

	// MaxDependencies is the most dependencies any single node has.
	MaxDependencies int

	// MaxDependents is the most dependents any single controller has.
	MaxDependents int

	// PostDomTree is the underlying post-dominator tree used.
	PostDomTree *DominatorTree
}

ControlDependence represents the control dependence graph.

A node B is control-dependent on A if:

  1. There exists a path from A to B where A is not post-dominated by B
  2. B post-dominates all nodes on the path after A

This tells us "which conditionals control whether B executes."

Thread Safety: Safe for concurrent use after construction.

func (*ControlDependence) ControlDependencyChain 

func (cd *ControlDependence) ControlDependencyChain(nodeID string, maxDepth int) []string

ControlDependencyChain returns the transitive chain of control dependencies.

Description: 

Starting from nodeID, walks up the control dependency chain collecting
all controllers. Uses BFS to find all controllers at each level.
Stops at maxDepth or when no more dependencies exist.

Inputs:

  • nodeID: The starting node to find dependencies for.
  • maxDepth: Maximum depth to traverse. Must be > 0.

Outputs:

  • []string: Chain of controllers in BFS order (closest first). Returns nil if receiver is nil, maxDepth <= 0, or no dependencies exist.

Limitations:

  • Does not include nodeID itself in the output.
  • Cycles are handled by tracking visited nodes.
  • BFS order means all depth-1 controllers appear before depth-2, etc.

Thread Safety: Safe for concurrent use.

Complexity: O(edges traversed) bounded by maxDepth.

func (*ControlDependence) GetDependencies 

func (cd *ControlDependence) GetDependencies(nodeID string) []string

GetDependencies returns what controls this node.

Description: 

Returns the list of nodes that control whether this node executes.
A control dependency from A to B means "A's branch decision determines
whether B runs".

Inputs:

  • nodeID: The node to query dependencies for. Must be a valid node ID.

Outputs:

  • []string: List of controlling nodes, or nil if the node has no dependencies or the receiver is nil.

Limitations:

  • Returns nil for nodes not in the post-dominator tree.
  • The returned slice should not be modified by the caller.

Thread Safety: Safe for concurrent use.

Complexity: O(1) map lookup.

func (*ControlDependence) GetDependents 

func (cd *ControlDependence) GetDependents(nodeID string) []string

GetDependents returns what this node controls.

Description: 

Returns the list of nodes whose execution is controlled by this node.
If this node is a branch point, its dependents are the nodes that
only execute on certain branches.

Inputs:

  • nodeID: The node to query dependents for. Must be a valid node ID.

Outputs:

  • []string: List of controlled nodes, or nil if the node has no dependents or the receiver is nil.

Limitations:

  • Returns nil for nodes that are not controllers.
  • The returned slice should not be modified by the caller.

Thread Safety: Safe for concurrent use.

Complexity: O(1) map lookup.

func (*ControlDependence) IsController 

func (cd *ControlDependence) IsController(nodeID string) bool

IsController returns true if this node controls other nodes.

Description: 

Checks whether this node is a control point (branch/decision point)
that determines whether other nodes execute.

Inputs:

  • nodeID: The node to check. Must be a valid node ID.

Outputs:

  • bool: True if this node controls at least one other node, false otherwise.

Limitations:

  • Returns false if receiver is nil.

Thread Safety: Safe for concurrent use.

Complexity: O(1) map lookup and length check.

type ControlDependenceError 

type ControlDependenceError struct {
	Message string
}

ControlDependenceError represents an error in control dependence computation.

func (*ControlDependenceError) Error 

func (e *ControlDependenceError) Error() string

type CouplingMetrics 

type CouplingMetrics struct {
	// Package is the package being measured.
	Package string

	// Afferent is the number of packages that depend on this package (Ca).
	// Higher = more packages would be affected by changes here.
	Afferent int

	// Efferent is the number of packages this package depends on (Ce).
	// Higher = more dependencies to track.
	Efferent int

	// Instability is Ce / (Ca + Ce), range [0, 1].
	// 0 = maximally stable (many dependents, few dependencies)
	// 1 = maximally unstable (few dependents, many dependencies)
	Instability float64

	// AbstractTypes is the count of interfaces and abstract types.
	AbstractTypes int

	// ConcreteTypes is the count of concrete types.
	ConcreteTypes int

	// Abstractness is AbstractTypes / (AbstractTypes + ConcreteTypes), range [0, 1].
	Abstractness float64
}

CouplingMetrics contains package coupling analysis results.

type CyclicDependency 

type CyclicDependency struct {
	// Nodes contains the node IDs in the cycle (in cycle order).
	Nodes []string

	// Packages contains the unique packages involved in the cycle.
	Packages []string

	// Length is the number of nodes in the cycle.
	Length int
}

CyclicDependency represents a cycle in the dependency graph.

type DeadCodeNode 

type DeadCodeNode struct {
	// Node is the graph node.
	Node *Node

	// Reason explains why this was flagged as dead code.
	Reason string
}

DeadCodeNode represents a potentially unused symbol.

type DiffSummary 

type DiffSummary struct {
	// TotalChanges is the total number of changes (added + removed + modified nodes + edge changes).
	TotalChanges int `json:"total_changes"`

	// FilesAffected is the number of distinct files with changed symbols.
	FilesAffected int `json:"files_affected"`

	// ChangeRatio is the fraction of nodes that changed (0.0 to 1.0).
	ChangeRatio float64 `json:"change_ratio"`
}

DiffSummary contains aggregate statistics about a diff.

type DirtyEntry 

type DirtyEntry struct {
	// Path is the file path (absolute or project-relative).
	Path string

	// MarkedAt is when the file was marked dirty.
	MarkedAt time.Time

	// Source indicates how the file became dirty ("agent", "watcher", "manual").
	Source string
}

DirtyEntry contains metadata about a dirty file.

type DirtyTracker 

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

DirtyTracker tracks files modified during agent execution.

Description: 

Tracks which files have been modified and need graph refresh.
Used by the execute phase to trigger incremental graph updates
before tool queries return stale data.

Thread Safety: 

All methods are safe for concurrent use.

func NewDirtyTracker 

func NewDirtyTracker() *DirtyTracker

NewDirtyTracker creates a new tracker.

Description: 

Creates a tracker for monitoring file modifications during
agent execution. Tracks which files need re-parsing.

Inputs: 

None.

Outputs: 

*DirtyTracker - Ready to track file changes.

Thread Safety: 

The returned tracker is safe for concurrent use.

func (*DirtyTracker) Clear 

func (d *DirtyTracker) Clear(paths []string) int

Clear removes specified paths from the dirty set.

Description: 

Called after successful refresh to clear the dirty files
that were refreshed. Only clears the specified paths.

Inputs: 

paths - Paths to clear from dirty set.

Outputs: 

int - Number of paths actually cleared.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) ClearAll 

func (d *DirtyTracker) ClearAll() int

ClearAll removes all paths from the dirty set.

Description: 

Clears the entire dirty set. Use after a full refresh
or when resetting the tracker.

Outputs: 

int - Number of paths cleared.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) Count 

func (d *DirtyTracker) Count() int

Count returns the number of dirty files.

Outputs: 

int - Number of dirty files.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) Disable 

func (d *DirtyTracker) Disable()

Disable turns off dirty tracking.

Description: 

When disabled, MarkDirty calls are no-ops. Useful for
read-only sessions where no file modifications are expected.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) Enable 

func (d *DirtyTracker) Enable()

Enable enables dirty tracking.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) GetDirtyEntries 

func (d *DirtyTracker) GetDirtyEntries() []DirtyEntry

GetDirtyEntries returns all dirty entries with metadata.

Description: 

Returns full metadata about dirty files including timestamps
and sources. Does NOT clear the dirty set.

Inputs: 

None.

Outputs: 

[]DirtyEntry - Dirty file entries. Empty slice if none.

Thread Safety: 

Safe for concurrent use. Returns copies.

func (*DirtyTracker) GetDirtyFiles 

func (d *DirtyTracker) GetDirtyFiles() []string

GetDirtyFiles returns all dirty file paths without clearing.

Description: 

Returns a copy of the dirty file paths. Does NOT clear the
dirty set. Use Clear() after successful refresh.

Inputs: 

None.

Outputs: 

[]string - Paths of dirty files. Empty slice if none.

Thread Safety: 

Safe for concurrent use. Returns a copy.

func (*DirtyTracker) HasDirty 

func (d *DirtyTracker) HasDirty() bool

HasDirty returns true if any files are marked dirty.

Description: 

Quick check before tool execution to determine if
incremental refresh is needed.

Inputs: 

None.

Outputs: 

bool - True if dirty files exist.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) IsEnabled 

func (d *DirtyTracker) IsEnabled() bool

IsEnabled returns true if tracking is enabled.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) MarkDirty 

func (d *DirtyTracker) MarkDirty(path string)

MarkDirty marks a file as modified and needing refresh.

Description: 

Called by tools after writing to a file. Records the file
path and timestamp for later incremental refresh.

Inputs: 

path - Absolute or project-relative file path.

Outputs: 

None.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) MarkDirtyFromWatcher 

func (d *DirtyTracker) MarkDirtyFromWatcher(change FileChange)

MarkDirtyFromWatcher handles a file change from the FileWatcher.

Description: 

Integrates with the existing FileWatcher to mark files dirty
when external changes are detected. Skips removed files.

Inputs: 

change - The file change event from FileWatcher.

Outputs: 

None.

Thread Safety: 

Safe for concurrent use.

func (*DirtyTracker) MarkDirtyWithSource 

func (d *DirtyTracker) MarkDirtyWithSource(path, source string)

MarkDirtyWithSource marks a file dirty with a specific source.

Description: 

Same as MarkDirty but allows specifying the source of the change.
Useful for distinguishing between agent modifications and external
file watcher events.

Inputs: 

path - Absolute or project-relative file path.
source - The source of the modification ("agent", "watcher", "manual").

Outputs: 

None.

Thread Safety: 

Safe for concurrent use.

type DiskGraph 

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

DiskGraph provides read access to a graph persisted in a bbolt file.

Description: 

DiskGraph opens a bbolt file created by MaterializeToDisk and provides
metadata accessors and individual node lookups. For full query support,
use LoadAsGraph to reconstruct an in-memory Graph.

Thread Safety: 

Safe for concurrent reads. bbolt supports concurrent read transactions.
Close must not be called concurrently with reads.

func OpenDiskGraph 

func OpenDiskGraph(path string) (*DiskGraph, error)

OpenDiskGraph opens a bbolt graph file and validates its schema version.

Description: 

Opens the bbolt file in read-only mode, reads metadata from the meta
bucket, and validates the schema version matches BboltSchemaVersion.
The caller must call Close when done.

Inputs: 

path - Absolute path to the bbolt file. Must exist.

Outputs: 

*DiskGraph - The opened disk graph. Caller must Close.
error - Non-nil if the file doesn't exist, is corrupt, or schema mismatch.

Thread Safety: Safe for concurrent use after construction.

func (*DiskGraph) BuiltAtMilli 

func (dg *DiskGraph) BuiltAtMilli() int64

BuiltAtMilli returns the build timestamp recorded in metadata.

Thread Safety: Safe for concurrent use.

func (*DiskGraph) Close 

func (dg *DiskGraph) Close() error

Close closes the underlying bbolt database.

Description: 

Releases the file lock on the bbolt file. Must be called when done.

Thread Safety: Must not be called concurrently with other methods.

func (*DiskGraph) EdgeCount 

func (dg *DiskGraph) EdgeCount() int

EdgeCount returns the number of edges recorded in metadata.

Thread Safety: Safe for concurrent use.

func (*DiskGraph) FileMtimes 

func (dg *DiskGraph) FileMtimes() map[string]int64

FileMtimes returns the file modification times recorded at build time.

Description: 

Returns a copy of the file mtimes map to prevent mutation.

Thread Safety: Safe for concurrent use.

func (*DiskGraph) GetNode 

func (dg *DiskGraph) GetNode(id string) (*Node, bool)

GetNode reads a single node from the bbolt file by ID.

Description: 

Reads the node from the nodes bucket and its edges from edges_out and
edges_in buckets in a single read transaction. Returns a Node with
populated Outgoing and Incoming slices, identical to in-memory Graph.

Inputs: 

id - The node ID to look up.

Outputs: 

*Node - The node with Symbol, Outgoing, and Incoming populated.
bool - True if the node was found.

Thread Safety: Safe for concurrent use.

func (*DiskGraph) GraphHash 

func (dg *DiskGraph) GraphHash() string

GraphHash returns the graph hash recorded in metadata.

Thread Safety: Safe for concurrent use.

func (*DiskGraph) LoadAsGraph 

func (dg *DiskGraph) LoadAsGraph(ctx context.Context) (*Graph, error)

LoadAsGraph reconstructs a full in-memory Graph from the bbolt file.

Description: 

Iterates all nodes in the nodes bucket and all outgoing edges in the
edges_out bucket, calling AddNode and AddEdge to reconstruct the graph
with all secondary indexes. Faster than BadgerDB path because:
  1. No JSON parsing — binary gob decode
  2. No gzip — snappy is faster
  3. Sequential B+ tree reads are cache-friendly

Inputs: 

ctx - Context for cancellation and tracing. Must not be nil.

Outputs: 

*Graph - The reconstructed graph in frozen, read-only state.
error - Non-nil if reconstruction fails.

Limitations: 

Loads the entire graph into memory. For large graphs, this may require
significant RAM. Phase 1b will add direct-from-disk query support.

Thread Safety: Safe for concurrent use on the DiskGraph.

func (*DiskGraph) NodeCount 

func (dg *DiskGraph) NodeCount() int

NodeCount returns the number of nodes recorded in metadata.

Thread Safety: Safe for concurrent use.

func (*DiskGraph) ProjectRoot 

func (dg *DiskGraph) ProjectRoot() string

ProjectRoot returns the project root recorded in metadata.

Thread Safety: Safe for concurrent use.

type DominanceFrontier 

type DominanceFrontier struct {
	// Frontier maps each node to its dominance frontier.
	// DF(n) contains nodes where n's dominance ends.
	Frontier map[string][]string

	// MergePoints contains nodes that appear in multiple frontiers.
	// These are control flow convergence points.
	MergePoints []string

	// MergePointCount maps merge point nodeID to count of frontiers it appears in.
	// Useful for ranking merge points by convergence degree.
	MergePointCount map[string]int

	// DomTree is the underlying dominator tree used.
	DomTree *DominatorTree

	// NodeCount is the number of nodes analyzed.
	NodeCount int

	// NodesWithFrontiers is the count of nodes with non-empty frontiers.
	NodesWithFrontiers int

	// TotalFrontierEntries is the sum of all frontier sizes.
	TotalFrontierEntries int

	// MaxFrontierSize is the largest individual frontier.
	MaxFrontierSize int
}

DominanceFrontier contains the computed dominance frontiers.

The dominance frontier DF(n) for a node n contains all nodes y such that:

  • n dominates a predecessor of y, but
  • n does NOT strictly dominate y

In plain terms: DF(n) = "where n's control ends"

Key concepts:

  • Frontier: Maps each node to its dominance frontier nodes
  • MergePoints: Nodes appearing in 2+ frontiers (control flow convergence)
  • MergePointDegree: How many paths converge at a merge point

Usage: 

domTree, _ := analytics.Dominators(ctx, "main")
df, _ := analytics.ComputeDominanceFrontier(ctx, domTree)

// Find where node's control ends
frontier := df.GetFrontier("nodeID")

// Check if a node is a merge point
if df.IsMergePoint("nodeID") {
    degree := df.MergePointDegree("nodeID")
}

Thread Safety: Safe for concurrent use after construction.

func (*DominanceFrontier) GetFrontier 

func (df *DominanceFrontier) GetFrontier(nodeID string) []string

GetFrontier returns the dominance frontier for a node.

Description: 

Returns the set of nodes where the specified node's dominance ends.
A node Y is in DF(X) if X dominates a predecessor of Y but does not
strictly dominate Y.

Inputs:

  • nodeID: The node to query the frontier for. Must be a valid node ID.

Outputs:

  • []string: The dominance frontier of the node, or nil if the node has no frontier or the receiver is nil.

Limitations:

  • Returns nil for nodes not in the dominator tree.
  • The returned slice should not be modified by the caller.

Thread Safety: Safe for concurrent use.

Complexity: O(1) map lookup.

func (*DominanceFrontier) IsMergePoint 

func (df *DominanceFrontier) IsMergePoint(nodeID string) bool

IsMergePoint returns true if the node is a merge point.

Description: 

A merge point is a node that appears in the dominance frontier of
two or more nodes, indicating it is a control flow convergence point
where execution from different paths meets.

Inputs:

  • nodeID: The node to check. Must be a valid node ID.

Outputs:

  • bool: True if the node is in 2+ frontiers, false otherwise.

Limitations:

  • Returns false if receiver is nil or nodeID is not in any frontier.

Thread Safety: Safe for concurrent use.

Complexity: O(1) map lookup.

func (*DominanceFrontier) MergePointDegree 

func (df *DominanceFrontier) MergePointDegree(nodeID string) int

MergePointDegree returns how many frontiers contain this node.

Description: 

Returns the number of distinct dominance frontiers that include
this node. A higher degree indicates more control flow paths
converge at this point.

Inputs:

  • nodeID: The node to query. Must be a valid node ID.

Outputs:

  • int: The number of frontiers containing this node. Returns 0 if the node is not in any frontier or the receiver is nil.

Limitations:

  • Returns 0 for nodes not appearing in any frontier.

Thread Safety: Safe for concurrent use.

Complexity: O(1) map lookup.

type DominanceFrontierError 

type DominanceFrontierError struct {
	Message string
}

DominanceFrontierError represents an error in dominance frontier computation.

func (*DominanceFrontierError) Error 

func (e *DominanceFrontierError) Error() string

type DominatorError 

type DominatorError struct {
	Message string
}

DominatorError represents an error in dominator computation.

func (*DominatorError) Error 

func (e *DominatorError) Error() string

type DominatorTree 

type DominatorTree struct {
	// Entry is the entry node ID (root of dominator tree).
	Entry string

	// ImmediateDom maps nodeID → immediate dominator nodeID.
	// The immediate dominator of a node N is the unique node D that:
	// 1. Strictly dominates N (D != N)
	// 2. Does not strictly dominate any other dominator of N
	// Entry node maps to itself.
	ImmediateDom map[string]string

	// Children maps nodeID → nodes it immediately dominates.
	// This is the inverse of ImmediateDom for efficient subtree queries.
	// Lazily computed on first access via ensureChildrenBuilt.
	Children map[string][]string

	// Depth maps nodeID → depth in dominator tree.
	// Entry node has depth 0.
	Depth map[string]int

	// PostOrder contains nodes in reverse postorder for iteration.
	// Used internally during computation.
	PostOrder []string

	// Iterations is the number of convergence iterations.
	Iterations int

	// Converged indicates whether the algorithm converged before max iterations.
	Converged bool

	// NodeCount is the total nodes in the graph.
	NodeCount int

	// EdgeCount is the total edges in the graph.
	EdgeCount int

	// ReachableCount is the number of nodes reachable from entry.
	ReachableCount int

	// ExitCount is the number of exit nodes detected (for post-dominators).
	// 0 for dominator trees, 1+ for post-dominator trees.
	ExitCount int

	// UsedVirtualExit indicates whether a virtual exit node was used
	// to handle multiple exits (for post-dominators only).
	UsedVirtualExit bool
	// contains filtered or unexported fields
}

DominatorTree represents the computed dominator relationships.

A dominator tree captures the dominance relationship where node D dominates node N if every path from the entry node to N must go through D.

Thread Safety: Safe for concurrent use after construction.

func (*DominatorTree) DominatedBy 

func (dt *DominatorTree) DominatedBy(node string) []string

DominatedBy returns all nodes dominated by a node (subtree rooted at node).

Builds the children map lazily on first call. Returns empty slice if node is not in the dominator tree.

Thread Safety: Safe for concurrent use. Children map is built atomically.

Complexity: O(subtree size) for traversal.

func (*DominatorTree) Dominates 

func (dt *DominatorTree) Dominates(a, b string) bool

Dominates returns true if a dominates b.

A node dominates itself (reflexive). Returns false if either node is not in the dominator tree.

Thread Safety: Safe for concurrent use.

Complexity: O(depth) where depth is the depth of b in the dominator tree.

func (*DominatorTree) DominatorsOf 

func (dt *DominatorTree) DominatorsOf(node string) []string

DominatorsOf returns all dominators of a node (path from node to entry).

Returns empty slice if node is not in the dominator tree. The result includes the node itself and ends with the entry node.

Thread Safety: Safe for concurrent use.

Complexity: O(depth) where depth is the depth of node.

func (*DominatorTree) LowestCommonDominator 

func (dt *DominatorTree) LowestCommonDominator(a, b string) string

LowestCommonDominator finds the LCD of two nodes.

Description: 

Finds the deepest node in the dominator tree that dominates both
input nodes. Uses an O(depth) algorithm that equalizes depths and
walks up until the nodes meet.

Inputs:

  • a, b: Node IDs to find common dominator for. Can be the same node.

Outputs:

  • string: The LCD node ID. Returns:
  • The node itself if a == b
  • The entry node if either node is not in the tree
  • Empty string if receiver is nil

Example: 

lcd := domTree.LowestCommonDominator("saveDB", "sendEmail")
// Returns "validate" (their common mandatory dependency)

Limitations:

  • O(depth) per query; use PrepareLCAQueries for many queries
  • Nodes not in tree are treated as having entry as LCD

Thread Safety: Safe for concurrent use.

Complexity: O(depth) per query.

func (*DominatorTree) LowestCommonDominatorMultiple 

func (dt *DominatorTree) LowestCommonDominatorMultiple(nodes []string) string

LowestCommonDominatorMultiple finds LCD of multiple nodes.

Description: 

Iteratively computes LCD for a list of nodes using the property
that LCD is associative: LCD(a, b, c) = LCD(LCD(a, b), c).

Inputs:

  • nodes: Slice of node IDs. Can be empty or have duplicates.

Outputs:

  • string: The LCD of all nodes. Returns:
  • Entry node if slice is empty
  • The single node if slice has one element
  • Empty string if receiver is nil

Example: 

lcd := domTree.LowestCommonDominatorMultiple([]string{"saveDB", "sendEmail", "logAction"})
// Returns their common mandatory dependency

Thread Safety: Safe for concurrent use.

Complexity: O(k × depth) where k = len(nodes).

func (*DominatorTree) MaxDepth 

func (dt *DominatorTree) MaxDepth() int

MaxDepth returns the maximum depth in the dominator tree.

Thread Safety: Safe for concurrent use.

func (*DominatorTree) PrepareLCAQueries 

func (dt *DominatorTree) PrepareLCAQueries() *LCAQueryEngine

PrepareLCAQueries preprocesses for O(1) LCD queries.

Description: 

Uses binary lifting to enable O(log depth) LCD queries. The preprocessing
builds a sparse table where parent[v][k] = 2^k-th ancestor of v.

Outputs:

  • *LCAQueryEngine: Engine for fast LCD queries. Returns nil if receiver is nil.

Example: 

lca := domTree.PrepareLCAQueries()
lcd := lca.Query("saveDB", "sendEmail")  // O(log depth) instead of O(depth)

Thread Safety: Safe for concurrent use.

Complexity: O(V log V) time and space for preprocessing.

type DominatorTreeCache 

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

DominatorTreeCache provides session-level caching for dominator trees.

Description: 

Caches a single dominator tree to avoid recomputation when the same
entry point is requested multiple times. The cache is automatically
invalidated when:
- A different entry point is requested
- The underlying graph changes (detected via BuiltAtMilli)

Thread Safety: 

DominatorTreeCache is safe for concurrent use via RWMutex.

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

	// NumEdgeTypes is the total number of edge types (for array sizing).
	// GR-08: Used for edgesByType index.
	NumEdgeTypes
)

func (EdgeType) String 

func (t EdgeType) String() string

String returns the string representation of the EdgeType.

type EnrichmentStats 

type EnrichmentStats struct {
	// PlaceholdersQueried is the number of placeholder nodes sent to LSP for resolution.
	PlaceholdersQueried int

	// PlaceholdersResolved is the number of placeholders successfully resolved to real nodes.
	PlaceholdersResolved int

	// PlaceholdersFailed is the number of placeholders where LSP returned an error.
	PlaceholdersFailed int

	// PlaceholdersSkipped is the number of placeholders skipped (wrong language, no location, etc.).
	PlaceholdersSkipped int

	// FilesQueried is the number of unique source files opened in the LSP server.
	FilesQueried int

	// OrphanedRemoved is the number of placeholder nodes removed because all their edges were resolved.
	OrphanedRemoved int

	// LSPErrors is the total number of LSP operation errors (open, definition, etc.).
	LSPErrors int

	// DurationMicro is the total enrichment phase time in microseconds.
	DurationMicro int64
}

EnrichmentStats contains statistics about the LSP enrichment phase.

Description: 

GR-74: Tracks how many placeholder nodes were queried against LSP servers,
how many were successfully resolved to real symbol nodes, and related metrics.

Thread Safety: 

Immutable after the enrichment phase completes.

func (*EnrichmentStats) Merge 

func (e *EnrichmentStats) Merge(delta EnrichmentStats)

Merge adds the counters from another EnrichmentStats into this one. DurationMicro and FilesQueried reflect the latest run only (not cumulative).

Description: 

GR-76: Used to merge incremental enrichment results into the cumulative
stats stored on CachedGraph. Additive for resolution counters so the CRS
sees the total enrichment state of the graph, not just the latest delta.

Inputs: 

delta - The incremental enrichment stats to merge in.

Thread Safety: NOT safe for concurrent use.

type ExternalDependency 

type ExternalDependency struct {
	// NodeID is the graph node ID of the external symbol.
	// Format: "external:<package>:<name>" or "external::<name>".
	NodeID string

	// Name is the symbol name (e.g., "run_simple", "read_csv").
	Name string

	// Package is the inferred external package/module (e.g., "werkzeug.serving", "pandas").
	// Empty string if the package could not be determined.
	Package string

	// CalledFrom is the ID of the internal node that calls this external symbol.
	// Empty string if the caller could not be determined from the traversal edges.
	CalledFrom string

	// Depth is the traversal depth at which this boundary was encountered.
	Depth int
}

ExternalDependency represents an external library boundary detected during graph traversal.

Description: 

IT-05a: When a traversal tool (get_call_chain, find_callees, find_callers, etc.)
encounters a node with Kind == SymbolKindExternal, this struct captures the
boundary information so tools can annotate their output.

Thread Safety: This type is safe for concurrent use (immutable after creation).

func ClassifyExternalNodes 

func ClassifyExternalNodes(g *Graph, result *TraversalResult) []ExternalDependency

ClassifyExternalNodes identifies external dependency boundaries in a traversal result.

Description: 

IT-05a: Iterates over the visited nodes in a TraversalResult, identifies those with
Kind == SymbolKindExternal, and returns structured ExternalDependency entries with
package information and caller linkage.

This function is designed to be called by any traversal tool's buildOutput method.
It operates on the already-completed TraversalResult — it does not modify the
traversal itself.

Inputs:

  • g: The graph containing the nodes. Must not be nil.
  • result: The traversal result to classify. Must not be nil.

Outputs:

  • []ExternalDependency: External boundaries found, ordered by traversal order. Returns nil if no external nodes are found.

Thread Safety: Safe for concurrent use (reads only).

type FileChange 

type FileChange struct {
	// Path is the absolute path to the changed file.
	Path string

	// Op is the type of change.
	Op FileOp

	// Time is when the change was detected.
	Time time.Time
}

FileChange represents a file system change event.

type FileChangeHandler 

type FileChangeHandler func(changes []FileChange)

FileChangeHandler is called when debounced changes are ready.

type FileClassification 

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

FileClassification holds the classification of all files in the graph.

Description: 

Stores a binary production/non-production classification for each file
based on graph topology (consumption ratio). Non-production files are
those that primarily consume production code (test, example, benchmark,
documentation code) without being consumed back.

Thread Safety: 

FileClassification is safe for concurrent reads after construction.
The internal map is never mutated after ClassifyFiles returns.

func ClassifyFiles 

func ClassifyFiles(hg *HierarchicalGraph, opts FileClassificationOptions) (*FileClassification, error)

ClassifyFiles classifies all files in the graph as production or non-production using a layered approach: graph topology, language-specific file patterns, test symbol density, and iterative ratio refinement.

Description: 

The core insight: test code calls production code, but production code
never calls test code. This is measurable as the "consumption ratio":

  edges_in  = cross-file edges pointing INTO this file
  edges_out = cross-file edges pointing OUT OF this file
  ratio     = edges_in / (edges_in + edges_out)

A file that only consumes (test/example) has ratio ≈ 0 (many edges out, few in).
A file that only produces (core library) has ratio ≈ 1 (many edges in, few out).

However, the raw ratio alone misclassifies test infrastructure files —
files like integrationtest_builder.go that are called by many test files.
These have high edges_in (from tests calling them) and look like production.

The algorithm uses 7 phases to handle this:
  Phase 1: Load config overrides
  Phase 2: Group nodes by file
  Phase 3: Initial consumption ratio (classifies obvious cases)
  Phase 4: Definitive test file patterns (Go _test.go, Python test_*.py, etc.)
  Phase 5: Entry point reinforcement + test symbol keyword density
  Phase 6: Iterative ratio refinement (re-compute using only production edges)
  Phase 7: Config overrides (user always wins)

Inputs: 

hg - The hierarchical graph to classify. Must not be nil and must be frozen.
opts - Classification options (project root for config file).

Outputs: 

*FileClassification - The classification result. Never nil on success.
error - Non-nil if the graph is nil or not frozen.

Thread Safety: Safe for concurrent use (read-only on the graph).

Limitations:

  • File-level classification (not directory-level).
  • Binary production/non-production (no test vs example vs docs distinction).
  • Computed at graph freeze time; does not update dynamically.

Assumptions:

  • Graph is frozen and fully indexed before calling.
  • Edge topology accurately reflects code dependencies.

func (*FileClassification) IsProduction 

func (fc *FileClassification) IsProduction(filePath string) bool

IsProduction returns true if the file is classified as production code.

Description: 

O(1) map lookup. Files not present in the classification map are treated
as production (conservative default — unknown files are not filtered).

Inputs: 

filePath - The file path to check.

Outputs: 

bool - True if the file is production code or unknown.

Thread Safety: Safe for concurrent use.

func (*FileClassification) Stats 

func (fc *FileClassification) Stats() FileClassificationStats

Stats returns summary statistics about the classification.

Outputs: 

FileClassificationStats - Copy of the statistics.

Thread Safety: Safe for concurrent use.

type FileClassificationOptions 

type FileClassificationOptions struct {
	// ProjectRoot is the absolute path to the project root.
	// Used to locate trace.config.yaml for user overrides.
	ProjectRoot string
}

FileClassificationOptions configures the file classification algorithm.

type FileClassificationStats 

type FileClassificationStats struct {
	// TotalFiles is the total number of files classified.
	// Invariant: TotalFiles == ProductionFiles + NonProductionFiles.
	TotalFiles int

	// ProductionFiles is the count of files classified as production.
	// Includes IsolatedFiles (isolated files are treated as production).
	ProductionFiles int

	// NonProductionFiles is the count of files classified as non-production.
	NonProductionFiles int

	// IsolatedFiles is the count of files with zero cross-file edges.
	// These are classified as production (benefit of the doubt).
	// IsolatedFiles is a subset of ProductionFiles.
	IsolatedFiles int

	// LikelyConsumerFiles is a diagnostic counter: files with consumption ratio
	// in [0.05, 0.15) that required entry point reinforcement (Phase 4).
	// Each is resolved into ProductionFiles or NonProductionFiles.
	// This is NOT a separate partition — it overlaps with Prod/NonProd counts.
	LikelyConsumerFiles int
}

FileClassificationStats contains summary statistics for logging.

Partition invariant: TotalFiles == ProductionFiles + NonProductionFiles. IsolatedFiles is a subset of ProductionFiles (isolated → production). LikelyConsumerFiles is a diagnostic counter that overlaps with ProductionFiles or NonProductionFiles after Phase 4 resolves them.

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 FileOp 

type FileOp int

FileOp represents the type of file operation. 

const (
	// FileOpCreate indicates a file was created.
	FileOpCreate FileOp = iota

	// FileOpWrite indicates a file was modified.
	FileOpWrite

	// FileOpRemove indicates a file was deleted.
	FileOpRemove

	// FileOpRename indicates a file was renamed.
	FileOpRename
)

func (FileOp) String 

func (op FileOp) String() string

String returns the string representation of the operation.

type FileParseError 

type FileParseError struct {
	FilePath string
	Err      error
}

FileParseError represents a parse error for a single file.

type FileWatcher 

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

FileWatcher watches for file changes with debouncing.

Description

Watches a directory for file changes and batches them using a debounce window. This prevents triggering updates for every keystroke during active editing.

Debouncing

Changes are collected into a buffer. When the debounce period expires without new changes, all collected changes are sent to the handler. This is implemented using channels for efficient, non-blocking operation.

Thread Safety

Safe for concurrent use. The handler is called from a single goroutine.

func NewFileWatcher 

func NewFileWatcher(root string, handler FileChangeHandler, opts *FileWatcherOptions) (*FileWatcher, error)

NewFileWatcher creates a new file watcher for the given root directory.

Inputs

  • root: Absolute path to the directory to watch.
  • handler: Function called with batched changes after debounce.
  • opts: Optional configuration (nil uses defaults).

Outputs

  • *FileWatcher: Ready-to-use watcher (call Start to begin watching).
  • error: Non-nil if the watcher could not be created.

Example 

watcher, err := NewFileWatcher("/path/to/project", func(changes []FileChange) {
    log.Printf("Changes detected: %d files", len(changes))
    // Trigger incremental graph update
}, nil)
if err != nil {
    return err
}
defer watcher.Stop()
if err := watcher.Start(ctx); err != nil {
    return err
}

func (*FileWatcher) AddPattern 

func (w *FileWatcher) AddPattern(pattern string)

AddPattern adds an ignore pattern.

func (*FileWatcher) IsWatching 

func (w *FileWatcher) IsWatching() bool

IsWatching returns true if the watcher is currently active.

func (*FileWatcher) SetHandler 

func (w *FileWatcher) SetHandler(handler FileChangeHandler)

SetHandler changes the change handler.

func (*FileWatcher) Start 

func (w *FileWatcher) Start(ctx context.Context) error

Start begins watching for file changes.

Description

Recursively watches the root directory and all subdirectories. Changes are debounced and sent to the handler in batches.

Inputs

  • ctx: Context for cancellation. When canceled, watching stops.

Outputs

  • error: Non-nil if watching could not be started.

Behavior

Spawns two goroutines:

  • Event processor: Converts fsnotify events to FileChange
  • Debouncer: Batches changes and calls handler

Both goroutines exit when Stop() is called or context is canceled.

func (*FileWatcher) Stop 

func (w *FileWatcher) Stop()

Stop stops the file watcher.

type FileWatcherOptions 

type FileWatcherOptions struct {
	// DebounceWindow is how long to wait for more changes before triggering.
	// Default: 100ms
	DebounceWindow time.Duration

	// IgnorePatterns are glob patterns for files/directories to ignore.
	// Default: [".git", "node_modules", ".idea", "*.swp", "*.tmp"]
	IgnorePatterns []string

	// BufferSize is the size of the change buffer channel.
	// Default: 1000
	BufferSize int
}

FileWatcherOptions configures the FileWatcher.

func DefaultFileWatcherOptions 

func DefaultFileWatcherOptions() FileWatcherOptions

DefaultFileWatcherOptions returns sensible defaults.

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

	// FileMtimes records file modification times (Unix seconds) at build time.
	// CRS-19: Used for staleness detection across sessions. Populated by
	// RecordFileMtimes() after Freeze(). Key is relative file path.
	FileMtimes map[string]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 FromSerializable 

func FromSerializable(sg *SerializableGraph, opts ...GraphOption) (*Graph, error)

FromSerializable reconstructs a Graph from its serializable representation.

Description: 

Creates a new Graph in building state, calls AddNode() and AddEdge() for
each entry to correctly build all secondary indexes (nodesByName, nodesByKind,
edgesByType, edgesByFile), then calls Freeze(). This reuses the existing
construction code path to guarantee index consistency.

Inputs: 

sg - The serializable graph to reconstruct. Must not be nil.
opts - Optional GraphOption values (e.g., WithMaxNodes).

Outputs: 

*Graph - The reconstructed graph in read-only state.
error - Non-nil if sg is nil, contains invalid data, or capacity exceeded.

Errors: 

Returns error if sg is nil, schema version is unsupported, a node has nil
symbol, or AddNode/AddEdge fails.

Complexity: 

O(V + E) where V is node count and E is edge count.

Thread Safety: 

The returned graph is independent and safe for concurrent reads after construction.

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) FindCallersWithInheritance 

func (g *Graph) FindCallersWithInheritance(ctx context.Context, symbolID string, parentMethodIDs []string, opts ...QueryOption) (*InheritanceQueryResult, error)

FindCallersWithInheritance returns callers of a method AND callers of the same method on parent classes in the inheritance chain.

Description: 

When a child class overrides a parent method, calls through the parent class
(e.g., this.renderImmediately() inside Component) create edges to the parent's
method, not the child's. This function collects callers from the entire
inheritance chain so that callers of both Plot.renderImmediately AND
Component.renderImmediately are returned.

Inputs: 

ctx - Context for cancellation.
symbolID - ID of the target method (e.g., Plot.renderImmediately).
parentMethodIDs - IDs of the same-named method on parent classes.
opts - Query options (Limit, Timeout).

Outputs: 

*QueryResult - Combined callers from all inheritance levels, deduplicated by ID.
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 or extend the given type.

Description: 

Finds all types that have an IMPLEMENTS or EMBEDS edge to the target.
IMPLEMENTS edges come from Go interface satisfaction and TS implements clauses.
EMBEDS edges come from Python/JS/TS class extends and Go struct embedding.
Uses target ID for unambiguous lookup. Deduplicates results when a type
has both edge types to the same target.

Inputs: 

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

Outputs: 

*QueryResult - Types implementing/extending the target (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 types matching the given name.

Description: 

When multiple types (interfaces, classes, structs) share the same name,
this returns implementers/subclasses for each, keyed by type ID.
Non-type symbols (functions, variables, etc.) are filtered out.

Inputs: 

ctx - Context for cancellation
name - Interface/class/struct name to search for
opts - Query options (Limit per target type, Timeout)

Outputs: 

map[string]*QueryResult - Type ID → implementers/subclasses of that type
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. Validates secondary index integrity before freezing.

Thread Safety: 

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

Limitations: 

Index validation adds O(V + E) overhead on freeze. For graphs with
millions of nodes, consider using FreezeWithoutValidation().

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) GetCallGraphParallel 

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

GetCallGraphParallel returns the call tree using parallel BFS for wide graphs.

Description: 

Performs level-synchronous parallel BFS traversal. Automatically chooses
parallel or sequential mode based on level width (threshold: 32 nodes).
For narrow graphs, falls back to sequential for better cache locality.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • symbolID: Root function ID. Must exist in graph.
  • opts: Query options (MaxDepth, Limit).

Outputs:

  • *TraversalResult: Visited nodes (order may vary in parallel mode) and edges.
  • error: Non-nil if root not found.

Performance: 

| Graph Type    | Complexity                    |
|---------------|-------------------------------|
| Sequential    | O(V + E)                      |
| Parallel wide | O((V + E) / P + D * barrier)  |

where P = min(level_size, NumCPU, 8), D = depth

Limitations:

  • VisitedNodes order is non-deterministic when parallel mode is used
  • Parallel mode only engaged for levels with >32 nodes
  • Memory overhead: ~O(level_size) per level for work distribution

Thread Safety: Safe for concurrent use.

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) GetEdgeCountByFile 

func (g *Graph) GetEdgeCountByFile(filePath string) int

GetEdgeCountByFile returns the count of edges with Location in the given file.

Description: 

GR-09: Uses secondary index for O(1) count without copying.
More efficient than len(GetEdgesByFile()) for just getting counts.

Inputs: 

filePath - The file path to count edges for.

Outputs: 

int - Number of edges with Location in that file. Zero if none found.

Complexity: 

O(1) - Direct map access and len().

Thread Safety: 

Safe for concurrent use on frozen graphs.

func (*Graph) GetEdgeCountByType 

func (g *Graph) GetEdgeCountByType(edgeType EdgeType) int

GetEdgeCountByType returns the count of edges of the given type.

Description: 

GR-08: Uses secondary index for O(1) count without copying.
More efficient than len(GetEdgesByType()) for just getting counts.

Inputs: 

edgeType - The edge type to count (e.g., EdgeTypeCalls).

Outputs: 

int - Number of edges of that type. Zero if invalid type or none found.

Complexity: 

O(1) - Direct array access and len().

Thread Safety: 

Safe for concurrent use on frozen graphs.

Example: 

callCount := g.GetEdgeCountByType(EdgeTypeCalls)

func (*Graph) GetEdgesByFile 

func (g *Graph) GetEdgesByFile(filePath string) []*Edge

GetEdgesByFile returns all edges with Location in the given file.

Description: 

GR-09: Uses secondary index for O(1) lookup.
Returns a defensive copy to prevent external mutation.
Note: Indexes by edge.Location.FilePath (where the edge is expressed),
which may differ from the source node's file path.

Inputs: 

filePath - The file path to filter by.

Outputs: 

[]*Edge - Edges with Location in that file. Empty slice if none found.

Complexity: 

O(1) lookup + O(k) copy where k = edges in that file.

Thread Safety: 

Safe for concurrent use on frozen graphs.

Example: 

edges := g.GetEdgesByFile("pkg/handler.go")
fmt.Printf("Found %d edges in handler.go\n", len(edges))

func (*Graph) GetEdgesByType 

func (g *Graph) GetEdgesByType(edgeType EdgeType) []*Edge

GetEdgesByType returns all edges of the given type.

Description: 

GR-08: Uses secondary index for O(1) lookup.
Returns a defensive copy to prevent external mutation.

Inputs: 

edgeType - The edge type to filter by (e.g., EdgeTypeCalls).

Outputs: 

[]*Edge - Edges of that type. Empty slice if none found or invalid type.

Complexity: 

O(1) lookup + O(k) copy where k = edges of that type.

Thread Safety: 

Safe for concurrent use on frozen graphs.

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) GetNodeCountByKind 

func (g *Graph) GetNodeCountByKind(kind ast.SymbolKind) int

GetNodeCountByKind returns the count of nodes of the given kind.

Description: 

GR-07: Uses secondary index for O(1) count without copying.
More efficient than len(GetNodesByKind()) for just getting counts.

Inputs: 

kind - The symbol kind to count.

Outputs: 

int - Number of nodes of that kind. Zero if none found.

Complexity: 

O(1) - Direct map access and len().

Thread Safety: 

Safe for concurrent use on frozen graphs.

func (*Graph) GetNodeCountByName 

func (g *Graph) GetNodeCountByName(name string) int

GetNodeCountByName returns the count of nodes with the given name.

Description: 

GR-06: Uses secondary index for O(1) count without copying.
More efficient than len(GetNodesByName()) for just getting counts.

Inputs: 

name - The symbol name to count.

Outputs: 

int - Number of nodes with that name. Zero if none found.

Complexity: 

O(1) - Direct map access and len().

Thread Safety: 

Safe for concurrent use on frozen graphs.

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) GetNodesByKind 

func (g *Graph) GetNodesByKind(kind ast.SymbolKind) []*Node

GetNodesByKind returns all nodes of the given symbol kind.

Description: 

GR-07: Uses secondary index for O(1) lookup.
Returns a defensive copy to prevent external mutation.

Inputs: 

kind - The symbol kind to filter by (e.g., SymbolKindFunction).

Outputs: 

[]*Node - Nodes of that kind. Empty slice if none found.

Complexity: 

O(1) lookup + O(k) copy where k = nodes of that kind.

Thread Safety: 

Safe for concurrent use on frozen graphs.

func (*Graph) GetNodesByName 

func (g *Graph) GetNodesByName(name string) []*Node

GetNodesByName returns all nodes with the given symbol name.

Description: 

GR-06: Uses secondary index for O(1) lookup.
Multiple symbols can share a name (e.g., "Setup" in different packages).
Returns a defensive copy to prevent external mutation.

Inputs: 

name - The symbol name to search for.

Outputs: 

[]*Node - Nodes with that name. Empty slice if none found.

Complexity: 

O(1) lookup + O(k) copy where k = nodes with that name.

Thread Safety: 

Safe for concurrent use on frozen graphs.

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) GetReverseCallGraphParallel 

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

GetReverseCallGraphParallel returns the callers tree using parallel BFS.

Description: 

Performs level-synchronous parallel BFS traversal following CALLS edges
backwards (finding callers). Automatically chooses parallel or sequential
mode based on level width.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • symbolID: Root function ID. Must exist in graph.
  • opts: Query options (MaxDepth, Limit).

Outputs:

  • *TraversalResult: Caller nodes (order may vary in parallel mode) and edges.
  • error: Non-nil if root not found.

Limitations:

  • VisitedNodes order is non-deterministic when parallel mode is used
  • Parallel mode only engaged for levels with >32 nodes

Thread Safety: Safe for concurrent use.

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) Hash 

func (g *Graph) Hash() string

Hash returns a deterministic hash of the graph structure.

Description: 

Computes a hash over all nodes and edges in the graph. The hash is
deterministic (same graph structure always produces same hash) and
can be used to detect graph changes for cache invalidation.

The hash includes:
  - All node IDs (sorted)
  - All edge tuples (from, to, type) sorted

Uses FNV-1a hash for speed and good distribution.

Outputs:

  • string: Hex-encoded hash (16 characters). Empty string if graph is nil.

Example: 

hash1 := graph.Hash()
// ... modify graph ...
hash2 := graph.Hash()
if hash1 != hash2 {
    log.Info("graph changed, invalidating caches")
}

Complexity: 

O(V log V + E log E) - Sorting nodes and edges
O(V + E) if already sorted (frozen graphs)

Thread Safety: 

Safe for concurrent use on frozen graphs.

func (*Graph) IsFrozen 

func (g *Graph) IsFrozen() bool

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

func (*Graph) IsTree 

func (g *Graph) IsTree(ctx context.Context, root string) error

IsTree validates that the graph forms a valid tree structure.

Description: 

Checks that graph is acyclic, connected, and has exactly V-1 edges.
Uses DFS to detect cycles and verify connectivity from root.

Complexity: O(V + E)

Thread Safety: Safe for concurrent use (read-only on frozen graph).

func (*Graph) MaterializeToDisk 

func (g *Graph) MaterializeToDisk(ctx context.Context, path string) error

MaterializeToDisk persists a frozen graph to a bbolt file.

Description: 

Writes all nodes, edges, secondary indexes, and metadata to a bbolt file
in a single atomic transaction. The graph must be frozen (read-only).
If a file already exists at path, it is replaced atomically via
write-to-temp + rename.

Inputs: 

ctx - Context for cancellation and tracing. Must not be nil.
path - Absolute path to the bbolt file to create. Parent dir must exist.

Outputs: 

error - Non-nil if the graph is not frozen, encoding fails, or I/O fails.

Limitations: 

Requires the graph to be frozen. Does not compress the bbolt file itself
(individual values are snappy-compressed).

Thread Safety: 

Safe for concurrent use on frozen graphs (read-only access to graph data).

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) RemoveNode 

func (g *Graph) RemoveNode(id string) error

RemoveNode removes a node and all its edges from the graph.

Description: 

GR-74: Used by LSP enrichment to clean up orphaned placeholder nodes
after all their edges have been resolved to real targets. Removes the node
from all indexes (nodes, nodesByName, nodesByKind) and removes all edges
connected to the node from the graph's edges slice and secondary indexes.

Inputs: 

id - The ID of the node to remove. Must exist in the graph.

Outputs: 

error - Non-nil if graph is frozen or node not found.

Errors: 

ErrGraphFrozen - Graph has been frozen
ErrNodeNotFound - Node does not exist

Thread Safety: 

NOT safe for concurrent use. Must be called during build phase only.

func (*Graph) ReplaceEdgeTarget 

func (g *Graph) ReplaceEdgeTarget(edge *Edge, newToID string) error

ReplaceEdgeTarget re-points an existing edge from its current target to a new target node.

Description: 

GR-74: Used by LSP enrichment to replace placeholder edge targets with
real symbol nodes after LSP definition lookup resolves the placeholder.
Removes the edge from the old target's Incoming slice, updates edge.ToID,
and appends to the new target's Incoming slice.

Inputs: 

edge - The edge to retarget. Must not be nil.
newToID - ID of the new target node. Must exist in the graph.

Outputs: 

error - Non-nil if graph is frozen, edge is nil, or newToID not found.

Errors: 

ErrGraphFrozen - Graph has been frozen
ErrNodeNotFound - newToID does not exist in the graph

Thread Safety: 

NOT safe for concurrent use. Must be called during build phase only.

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.

Description: 

Returns statistics including node/edge counts, breakdowns by edge type
and symbol kind, and capacity information. Uses secondary indexes for
O(1) lookups instead of O(V+E) iteration.

Outputs: 

GraphStats - Statistics about the graph.

Complexity: 

O(K + T) where K is number of symbol kinds and T is number of edge types.
GR-06/07/08: Improved from O(V + E) via secondary indexes.

Thread Safety: 

Safe for concurrent use on frozen graphs. Not safe during building.

func (*Graph) ToSerializable 

func (g *Graph) ToSerializable() *SerializableGraph

ToSerializable converts a Graph to its JSON-serializable representation.

Description: 

Iterates all nodes (sorted by ID for deterministic output) and all edges
to produce a SerializableGraph suitable for JSON encoding. The resulting
structure contains all data needed to reconstruct the graph.

Outputs: 

*SerializableGraph - The serializable representation. Never nil.

Complexity: 

O(V log V + E) where V is node count and E is edge count.
Sorting nodes by ID dominates.

Thread Safety: 

Safe for concurrent use on frozen graphs.

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 GraphAnalytics 

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

GraphAnalytics provides analytical queries over the code graph.

Description: 

GraphAnalytics operates on a HierarchicalGraph to provide insights about
code structure, including:
- Hotspot detection (most-connected nodes)
- Dead code detection (unreachable symbols)
- Cyclic dependency detection (using Tarjan's SCC)
- Package coupling metrics
- HLD query wrappers with CRS integration

Thread Safety: 

GraphAnalytics is safe for concurrent use (read-only queries).
Session management is protected by RWMutex.

Performance: 

| Operation | Complexity |
|-----------|------------|
| HotSpots | O(V log k) for top-k |
| DeadCode | O(V) |
| CyclicDependencies | O(V + E) |
| PackageCoupling | O(P) where P = packages |
| HLD Queries | O(log V) |

func NewGraphAnalytics 

func NewGraphAnalytics(graph *HierarchicalGraph) *GraphAnalytics

NewGraphAnalytics creates a new analytics instance for the given graph.

Inputs: 

graph - The hierarchical graph to analyze. Must not be nil.

Outputs: 

*GraphAnalytics - The analytics instance. Never nil if graph is valid.

func NewGraphAnalyticsWithCRS 

func NewGraphAnalyticsWithCRS(graph *HierarchicalGraph, hld *HLDecomposition, crsInstance crs.CRS, opts *GraphAnalyticsOptions) *GraphAnalytics

NewGraphAnalyticsWithCRS creates an analytics instance with CRS integration.

Description: 

Creates a GraphAnalytics instance that records HLD query operations to CRS.
Use this when you want query tracing and replay capabilities.

Inputs:

  • graph: The hierarchical graph to analyze. Must not be nil.
  • hld: The HLD instance for LCA queries. Must not be nil.
  • crsInstance: The CRS instance for recording. Must not be nil.
  • opts: Configuration options. If nil, uses defaults (no auto-session).

Outputs:

  • *GraphAnalytics: The analytics instance with CRS enabled. Never nil if inputs valid.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) ArticulationPoints 

func (a *GraphAnalytics) ArticulationPoints(ctx context.Context) (*ArticulationResult, error)

ArticulationPoints finds cut vertices using Tarjan's algorithm.

Description: 

Uses iterative DFS (to avoid stack overflow on deep graphs) to find
nodes whose removal would disconnect the graph when treated as undirected.
Also identifies bridges (critical edges).

The algorithm treats the directed call graph as undirected, which means
both incoming and outgoing edges are considered for connectivity analysis.

Inputs:

  • ctx: Context for cancellation. Must not be nil. Checked every 1000 nodes.

Outputs:

  • *ArticulationResult: Analysis results. Never nil on success. Contains Points (cut vertices), Bridges (critical edges), and component count.
  • error: Non-nil only on context cancellation. Partial results still returned.

Example: 

result, err := analytics.ArticulationPoints(ctx)
if err != nil {
    // Context was cancelled - result may be partial
    log.Printf("cancelled after processing %d nodes", result.NodeCount)
}
for _, point := range result.Points {
    log.Printf("Single point of failure: %s", point)
}

Limitations:

  • Treats directed graph as undirected for connectivity
  • Does not identify direction-sensitive articulation points
  • Memory usage scales with O(V) for auxiliary data structures

Assumptions:

  • Graph is frozen (guaranteed by HierarchicalGraph construction)
  • Node IDs are valid and non-empty strings
  • Self-loops are skipped (do not affect connectivity)

Thread Safety: Safe for concurrent use (read-only on graph).

Complexity: O(V + E) time, O(V) space.

func (*GraphAnalytics) ArticulationPointsWithCRS 

func (a *GraphAnalytics) ArticulationPointsWithCRS(ctx context.Context) (*ArticulationResult, crs.TraceStep)

ArticulationPointsWithCRS wraps ArticulationPoints with CRS tracing.

Description: 

Provides the same functionality as ArticulationPoints but also returns
a TraceStep for recording in the Code Reasoning State (CRS).

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) BatchLCAWithCRS 

func (ga *GraphAnalytics) BatchLCAWithCRS(ctx context.Context, pairs [][2]string) ([]string, []error, error)

BatchLCAWithCRS computes batch LCA and records a StepRecord to CRS.

Description: 

Wraps HLD.BatchLCA() to provide CRS integration. Records a single StepRecord
for the entire batch operation with aggregate statistics.

Inputs:

  • ctx: Context for cancellation and tracing. Must not be nil.
  • pairs: Array of node ID pairs. Must not be empty.

Outputs:

  • []string: LCA results (one per pair).
  • []error: Errors (one per pair, nil on success).
  • error: Non-nil on total failure.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) CheckReducibility 

func (a *GraphAnalytics) CheckReducibility(ctx context.Context, domTree *DominatorTree) (*ReducibilityResult, error)

CheckReducibility analyzes graph reducibility using dominator tree.

Description: 

Determines if the graph is reducible by classifying edges relative
to the dominator tree. A graph is reducible if and only if all
back edges go to dominators (natural loops only).

Identifies and enumerates irreducible regions - subgraphs with
multiple entry points that indicate complex control flow.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • domTree: Pre-computed dominator tree. Must not be nil.

Outputs:

  • *ReducibilityResult: Analysis results. Never nil on success.
  • error: Non-nil on failure with context-wrapped message.

Algorithm:

  1. For each edge (u, v) in the graph: - If domTree.Dominates(v, u): back edge (OK) - If domTree.Dominates(u, v): forward edge (OK) - Otherwise: cross edge (potentially irreducible)
  2. For each cross edge, find the irreducible region it creates
  3. Deduplicate overlapping regions
  4. Compute reducibility score

Complexity:

  • Time: O(E × depth) for edge classification via dominator queries
  • Time: O(V + E) for region enumeration per irreducible region
  • Space: O(V) for tracking node membership

Limitations:

  • Maximum 100 irreducible regions enumerated
  • Disconnected nodes (unreachable from entry) are not analyzed

Assumptions:

  • domTree was computed from the same graph
  • Graph is frozen before analysis

Thread Safety: Safe for concurrent use (read-only on graph/domTree).

func (*GraphAnalytics) CheckReducibilityWithCRS 

func (a *GraphAnalytics) CheckReducibilityWithCRS(
	ctx context.Context,
	domTree *DominatorTree,
) (*ReducibilityResult, crs.TraceStep)

CheckReducibilityWithCRS wraps CheckReducibility with CRS tracing.

Description: 

Provides the same functionality as CheckReducibility but also returns
a TraceStep for recording in the Code Reasoning State (CRS).

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) ComputeControlDependence 

func (a *GraphAnalytics) ComputeControlDependence(
	ctx context.Context,
	postDomTree *DominatorTree,
) (*ControlDependence, error)

ComputeControlDependence builds the control dependence graph.

Description: 

Uses the post-dominance frontier to compute which nodes control
the execution of other nodes. A decision point controls nodes
that appear in its post-dominance frontier.

For each node n in PostDF(m), n is control-dependent on m.

Inputs:

  • ctx: Context for cancellation. Checked during dominance frontier computation.
  • postDomTree: Pre-computed post-dominator tree. Must not be nil.

Outputs:

  • *ControlDependence: The control dependence relationships. Never nil.
  • error: Non-nil if postDomTree is nil or context cancelled.

Example: 

postDomTree, _ := analytics.PostDominators(ctx, "")
cd, err := analytics.ComputeControlDependence(ctx, postDomTree)
if err != nil {
    log.Fatal(err)
}
// What controls the execution of handler?
controllers := cd.GetDependencies("handler")
// What does the condition control?
controlled := cd.GetDependents("condition")

Limitations:

  • Only computes dependencies for nodes in the post-dominator tree
  • Unreachable nodes have no dependencies
  • Memory: O(E) where E is control dependence edges

Assumptions:

  • postDomTree is valid and consistent
  • Graph is frozen

Thread Safety: Safe for concurrent use (read-only on graph and postDomTree).

Complexity: O(E × depth), same as dominance frontier.

func (*GraphAnalytics) ComputeControlDependenceWithCRS 

func (a *GraphAnalytics) ComputeControlDependenceWithCRS(
	ctx context.Context,
	postDomTree *DominatorTree,
) (*ControlDependence, crs.TraceStep)

ComputeControlDependenceWithCRS wraps ComputeControlDependence with CRS tracing.

Description: 

Provides the same functionality as ComputeControlDependence but also returns
a TraceStep for recording in the Code Reasoning State (CRS).

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) ComputeDominanceFrontier 

func (a *GraphAnalytics) ComputeDominanceFrontier(
	ctx context.Context,
	domTree *DominatorTree,
) (*DominanceFrontier, error)

ComputeDominanceFrontier computes dominance frontiers for all nodes.

Description: 

For each node n, DF(n) contains nodes where n's dominance ends.
Uses the standard algorithm from Cytron et al. (1991).
A node m is in DF(n) iff:
  1. n dominates a predecessor of m
  2. n does NOT strictly dominate m

Inputs:

  • ctx: Context for cancellation. Checked every 500 nodes.
  • domTree: Pre-computed dominator tree. Must not be nil.

Outputs:

  • *DominanceFrontier: Frontiers for all nodes. Never nil.
  • error: Non-nil if domTree is nil or context cancelled.

Example: 

domTree, _ := analytics.Dominators(ctx, "main")
df, err := analytics.ComputeDominanceFrontier(ctx, domTree)
if err != nil {
    log.Fatal(err)
}
mergePoints := df.MergePoints

Limitations:

  • Only computes frontiers for nodes in the dominator tree
  • Unreachable nodes have no frontier
  • Memory: O(V) typical, O(V²) worst case

Assumptions:

  • domTree is valid and consistent
  • Graph is frozen

Thread Safety: Safe for concurrent use (read-only on graph and domTree).

Complexity: O(E × depth), typically O(E) for shallow trees.

func (*GraphAnalytics) ComputeDominanceFrontierWithCRS 

func (a *GraphAnalytics) ComputeDominanceFrontierWithCRS(
	ctx context.Context,
	domTree *DominatorTree,
) (*DominanceFrontier, crs.TraceStep)

ComputeDominanceFrontierWithCRS wraps ComputeDominanceFrontier with CRS tracing.

Description: 

Provides the same functionality as ComputeDominanceFrontier but also returns
a TraceStep for recording in the Code Reasoning State (CRS).

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) CyclicDependencies 

func (a *GraphAnalytics) CyclicDependencies() []CyclicDependency

CyclicDependencies finds all cycles in the graph using Tarjan's SCC algorithm.

Description: 

Uses Tarjan's strongly connected components algorithm to find cycles.
Only returns components with more than one node (actual cycles).

Time complexity: O(V + E)
Space complexity: O(V)

Implementation uses an explicit call stack to avoid stack overflow on
deep graphs (CR-2 fix).

Outputs: 

[]CyclicDependency - All cycles found, sorted by length descending.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) CyclicDependenciesWithCRS 

func (a *GraphAnalytics) CyclicDependenciesWithCRS(ctx context.Context) ([]CyclicDependency, crs.TraceStep)

CyclicDependenciesWithCRS returns cycles with a TraceStep.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DeadCode 

func (a *GraphAnalytics) DeadCode() []DeadCodeNode

DeadCode finds symbols with no incoming edges (potential unused code).

Description: 

Returns nodes that have no callers/references, excluding:
- Entry points (main, init, Test*, Benchmark*)
- Exported symbols in main package
- External/placeholder nodes
- Interface methods (implementations satisfy interfaces)

Outputs: 

[]DeadCodeNode - Potentially unused symbols with reasons.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DeadCodeWithCRS 

func (a *GraphAnalytics) DeadCodeWithCRS(ctx context.Context) ([]DeadCodeNode, crs.TraceStep)

DeadCodeWithCRS returns dead code analysis with a TraceStep.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DecomposePathWithCRS 

func (ga *GraphAnalytics) DecomposePathWithCRS(ctx context.Context, u, v string) ([]PathSegment, error)

DecomposePathWithCRS decomposes path and records a StepRecord to CRS.

Description: 

Wraps HLD.DecomposePath() to provide CRS integration. Records the operation
as a StepRecord with timing, outcome, and result summary.

Inputs:

  • ctx: Context for cancellation and tracing. Must not be nil.
  • u, v: Node IDs. Must not be empty.

Outputs:

  • []PathSegment: Path segments (O(log V) segments).
  • error: Non-nil on failure.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DetectCommunities 

func (a *GraphAnalytics) DetectCommunities(ctx context.Context, opts *LeidenOptions) (*CommunityResult, error)

DetectCommunities uses the Leiden algorithm to find natural code communities.

Description: 

Implements the Leiden algorithm for community detection, which is an
improvement over Louvain. The key difference is the refinement phase
that guarantees all communities are well-connected.

Algorithm phases:
  1. Local moves: Try moving each node to neighbor's community if it improves modularity
  2. Refinement: Ensure each community is well-connected (Leiden's key improvement)
  3. Aggregation: Collapse communities into super-nodes (optional, for hierarchical)

For code graphs, we implement phases 1 and 2 which are sufficient for
typical codebase sizes (<100K nodes).

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • opts: Configuration options. If nil, defaults are used.

Outputs:

  • *CommunityResult: Detected communities with modularity score.
  • error: Non-nil if cancelled or other error.

Example: 

opts := graph.DefaultLeidenOptions()
result, err := analytics.DetectCommunities(ctx, opts)
if err != nil {
    return err
}
fmt.Printf("Found %d communities with modularity %.3f\n",
    len(result.Communities), result.Modularity)

Thread Safety: Safe for concurrent use (read-only on graph).

Complexity: O(V + E) per iteration, typically few iterations.

Limitations:

  • Single-threaded implementation
  • Memory usage: O(V) for community assignments

func (*GraphAnalytics) DetectCommunitiesParallel 

func (a *GraphAnalytics) DetectCommunitiesParallel(ctx context.Context, opts *LeidenOptions) (*CommunityResult, error)

DetectCommunitiesParallel uses parallel processing for large graphs.

Description: 

Parallelized version of DetectCommunities that uses multiple goroutines
for pre-computation, refinement, and modularity calculation. Automatically
falls back to sequential for graphs smaller than 1000 nodes.

Parallelization strategy:

  • Pre-computation of degrees/neighbors: embarrassingly parallel
  • Refinement phase: each community processed independently
  • Modularity calculation: parallel sum reduction
  • Local moves: sequential (correctness requires synchronization)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • opts: Configuration options. If nil, defaults are used.

Outputs:

  • *CommunityResult: Detected communities with modularity score.
  • error: Non-nil if cancelled or other error.

Performance: 

Speedup depends on graph structure and CPU count. Typical speedups:
  - 10K nodes: 2-3x faster
  - 100K nodes: 3-5x faster

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DetectCommunitiesWithCRS 

func (a *GraphAnalytics) DetectCommunitiesWithCRS(ctx context.Context, opts *LeidenOptions) (*CommunityResult, crs.TraceStep)

DetectCommunitiesWithCRS detects communities and returns a TraceStep for CRS recording.

Description: 

Wraps DetectCommunities with CRS integration for recording the operation
in the reasoning trace.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DetectEntryNodes 

func (a *GraphAnalytics) DetectEntryNodes(ctx context.Context) []string

DetectEntryNodes finds nodes with no incoming edges.

Description: 

Identifies natural entry points in the call graph - functions that are not
called by any other function. These are typically main, init, test functions,
or other top-level entry points.

Outputs: 

[]string - Node IDs of entry points, prioritizing main/init names.

Thread Safety: Safe for concurrent use (read-only on graph).

func (*GraphAnalytics) DetectLoops 

func (a *GraphAnalytics) DetectLoops(
	ctx context.Context,
	domTree *DominatorTree,
) (*LoopNest, error)

DetectLoops identifies natural loops in the call graph.

Description: 

Uses the dominator tree to find back edges (edges A→B where B dominates A),
then constructs natural loops and their nesting hierarchy. Each back edge
defines a natural loop with the target as the header.

The algorithm:
1. Find all back edges using the dominator tree
2. For each header, compute the loop body via reverse BFS
3. Build the loop nesting hierarchy
4. Assign depths and parent/child relationships

Inputs:

  • ctx: Context for cancellation. Checked between loop body computations.
  • domTree: Pre-computed dominator tree. Must not be nil.

Outputs:

  • *LoopNest: Complete loop nesting structure. Never nil.
  • error: Non-nil if domTree is nil or context cancelled.

Example: 

domTree, _ := analytics.Dominators(ctx, "main")
loops, err := analytics.DetectLoops(ctx, domTree)
if err != nil {
    log.Fatal(err)
}
for _, loop := range loops.Loops {
    log.Printf("Loop with header %s has %d nodes", loop.Header, loop.Size)
}

Limitations:

  • Only detects natural loops (single entry point)
  • Irreducible loops are not fully characterized (logged as warning)
  • Requires dominator tree to be precomputed

Assumptions:

  • domTree is valid and consistent
  • Graph is frozen

Thread Safety: Safe for concurrent use (read-only on graph and domTree).

Complexity: O(V + E) after dominator tree.

func (*GraphAnalytics) DetectLoopsWithCRS 

func (a *GraphAnalytics) DetectLoopsWithCRS(
	ctx context.Context,
	domTree *DominatorTree,
) (*LoopNest, crs.TraceStep)

DetectLoopsWithCRS wraps DetectLoops with CRS tracing.

Description: 

Provides the same functionality as DetectLoops but also returns
a TraceStep for recording in the Code Reasoning State (CRS).

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DetectSESERegions 

func (a *GraphAnalytics) DetectSESERegions(
	ctx context.Context,
	domTree, postDomTree *DominatorTree,
) (*SESEResult, error)

DetectSESERegions finds all SESE regions in the graph.

Description: 

Uses dominator and post-dominator trees to identify regions with
single entry and single exit points. A node N forms a SESE entry
with its immediate post-dominator P if N dominates P.

The algorithm iterates through all nodes and checks if each node
can serve as a SESE entry with its immediate post-dominator as exit.

Inputs:

  • ctx: Context for cancellation. Checked every 100 nodes.
  • domTree: Pre-computed dominator tree. Must not be nil.
  • postDomTree: Pre-computed post-dominator tree. Must not be nil.

Outputs:

  • *SESEResult: All detected SESE regions with hierarchy. Never nil.
  • error: Non-nil if inputs are nil or context cancelled.

Example: 

domTree, _ := analytics.Dominators(ctx, "main")
postDomTree, _ := analytics.PostDominators(ctx, "")
result, err := analytics.DetectSESERegions(ctx, domTree, postDomTree)
if err != nil {
    log.Fatalf("failed to detect SESE regions: %v", err)
}
for _, region := range result.Extractable {
    log.Printf("extractable: %s -> %s (size: %d)", region.Entry, region.Exit, region.Size)
}

Limitations:

  • Requires both dominator and post-dominator trees
  • Only detects SESE regions for nodes in both trees
  • Large graphs may produce many regions; use FilterExtractable()

Assumptions:

  • domTree and postDomTree are computed from the same graph
  • Graph is frozen
  • Trees are consistent and valid

Thread Safety: Safe for concurrent use (read-only on trees).

Complexity: O(E) after dom trees are computed.

func (*GraphAnalytics) DetectSESERegionsWithCRS 

func (a *GraphAnalytics) DetectSESERegionsWithCRS(
	ctx context.Context,
	domTree, postDomTree *DominatorTree,
) (*SESEResult, crs.TraceStep)

DetectSESERegionsWithCRS wraps DetectSESERegions with CRS tracing.

Description: 

Provides the same functionality as DetectSESERegions but also returns
a TraceStep for recording in the Code Reasoning State (CRS).

Inputs:

  • ctx: Context for cancellation.
  • domTree: Pre-computed dominator tree.
  • postDomTree: Pre-computed post-dominator tree.

Outputs:

  • *SESEResult: All detected SESE regions.
  • crs.TraceStep: Trace step for CRS recording.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DistanceWithCRS 

func (ga *GraphAnalytics) DistanceWithCRS(ctx context.Context, u, v string) (int, error)

DistanceWithCRS computes distance and records a StepRecord to CRS.

Description: 

Wraps HLD.Distance() to provide CRS integration. Records the operation
as a StepRecord with timing, outcome, and result summary.

Inputs:

  • ctx: Context for cancellation and tracing. Must not be nil.
  • u, v: Node IDs. Must not be empty.

Outputs:

  • int: Distance between nodes.
  • error: Non-nil on failure.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) Dominators 

func (a *GraphAnalytics) Dominators(ctx context.Context, entry string) (*DominatorTree, error)

Dominators computes the dominator tree using Cooper-Harvey-Kennedy algorithm.

Description: 

Uses the iterative data-flow approach from "A Simple, Fast Dominance Algorithm"
by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy (2001).
This algorithm converges in O(E) time for typical reducible graphs
and O(V²) worst case for non-reducible graphs.

Inputs:

  • ctx: Context for cancellation. Must not be nil. Checked every iteration.
  • entry: The entry node ID. Must exist in graph and not be empty.

Outputs:

  • *DominatorTree: The computed dominator tree. Never nil.
  • error: Non-nil if entry not found or context cancelled.

Example: 

dt, err := analytics.Dominators(ctx, "main.go:10:main")
if err != nil {
    log.Fatalf("failed to compute dominators: %v", err)
}
for node, idom := range dt.ImmediateDom {
    log.Printf("%s is immediately dominated by %s", node, idom)
}

Limitations:

  • Only computes dominators for nodes reachable from entry
  • Unreachable nodes have no entry in ImmediateDom
  • Memory usage: O(V) for all data structures

Assumptions:

  • Graph is frozen (guaranteed by HierarchicalGraph construction)
  • Entry node exists in the graph
  • Directed edges represent call relationships

Thread Safety: Safe for concurrent use (read-only on graph).

Complexity: O(E) typical, O(V²) worst case.

func (*GraphAnalytics) DominatorsWithCRS 

func (a *GraphAnalytics) DominatorsWithCRS(ctx context.Context, entry string) (*DominatorTree, crs.TraceStep)

DominatorsWithCRS wraps Dominators with CRS tracing.

Description: 

Provides the same functionality as Dominators but also returns
a TraceStep for recording in the Code Reasoning State (CRS).

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) DominatorsWithCache 

func (a *GraphAnalytics) DominatorsWithCache(ctx context.Context, entry string) (*DominatorTree, crs.TraceStep, error)

DominatorsWithCache returns a cached dominator tree if available, computing a fresh tree only when needed.

Description: 

Provides the same functionality as Dominators but caches the result to avoid
recomputation when multiple tools request the dominator tree for the same
entry point. The cache is automatically invalidated when:
- A different entry point is requested
- The underlying graph changes (detected via BuiltAtMilli)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • entry: The entry node ID (must exist in graph).

Outputs:

  • *DominatorTree: The computed or cached dominator tree. Never nil.
  • crs.TraceStep: TraceStep for CRS recording (includes cache_hit metadata).
  • error: Non-nil if entry not found or context cancelled.

Thread Safety: Safe for concurrent use via internal RWMutex.

func (*GraphAnalytics) EndSession 

func (ga *GraphAnalytics) EndSession(ctx context.Context) error

EndSession finalizes the current CRS session and clears history.

Description: 

Clears the step history for the current session and resets session state.
Call this when the session is complete to free memory.

Inputs:

  • ctx: Context for cancellation. Must not be nil.

Outputs:

  • error: Non-nil if CRS is not configured or no active session.

Thread Safety: Safe for concurrent use (protected by mutex).

func (*GraphAnalytics) GetCouplingForPackage 

func (a *GraphAnalytics) GetCouplingForPackage(pkg string) *CouplingMetrics

GetCouplingForPackage returns coupling metrics for a specific package.

Inputs: 

pkg - The package path to analyze.

Outputs: 

*CouplingMetrics - Metrics for the package, or nil if not found.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) GetNode 

func (a *GraphAnalytics) GetNode(id string) (*Node, bool)

GetNode retrieves a node from the underlying graph by its ID.

Description: 

Delegates to the underlying Graph.GetNode method to look up a node
by its symbol ID. This is useful for checking node properties such as
outgoing/incoming edge counts without exposing the internal graph.

Inputs: 

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

Outputs: 

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

Thread Safety: Safe for concurrent use (graph is read-only after freeze).

func (*GraphAnalytics) HotSpots 

func (a *GraphAnalytics) HotSpots(top int) []HotspotNode

HotSpots returns the top N most-connected nodes in the graph.

Description: 

Finds nodes with the highest connectivity score, where:
score = inDegree * 2 + outDegree * 1

Incoming edges are weighted higher because being called frequently
indicates higher impact on the codebase.

Inputs: 

top - Maximum number of hotspots to return. Must be > 0.

Outputs: 

[]HotspotNode - Top N nodes sorted by score descending.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) HotSpotsWithCRS 

func (a *GraphAnalytics) HotSpotsWithCRS(ctx context.Context, top int) ([]HotspotNode, crs.TraceStep)

HotSpotsWithCRS returns hotspots with a TraceStep for CRS recording.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) IsGraphReady 

func (a *GraphAnalytics) IsGraphReady() bool

IsGraphReady returns true if the graph has been fully indexed and is ready for queries.

Description: 

Checks if the underlying graph has been populated with nodes and edges.
This prevents race conditions where dominator-based tools execute before
graph indexing completes, returning incorrect empty results.

Outputs:

  • bool: true if graph is ready for queries, false if still indexing.

Thread Safety: Safe for concurrent use (read-only check).

Example: 

if !analytics.IsGraphReady() {
    return &Result{Success: false, Error: "graph not ready - indexing in progress"}, nil
}

Limitations: 

This only checks if nodes/edges exist and graph is frozen. It doesn't
validate that all files have been processed or that the graph is complete.

func (*GraphAnalytics) IsProductionFile 

func (a *GraphAnalytics) IsProductionFile(filePath string) bool

IsProductionFile returns true if the file is classified as production code.

Description: 

Delegates to the underlying HierarchicalGraph.IsProductionFile().
This is the primary method that analytics tools should use to filter
test/example/documentation files from results.

Inputs: 

filePath - The file path to check.

Outputs: 

bool - True if the file is production code. Returns true if analytics
       or graph is nil (conservative default).

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) IsReducible 

func (a *GraphAnalytics) IsReducible(ctx context.Context, domTree *DominatorTree) (bool, error)

IsReducible provides a fast check for reducibility without region enumeration.

Description: 

Returns true if the graph is reducible, false otherwise.
This is faster than CheckReducibility when you only need the boolean result
and don't need the detailed region information.

Complexity:

  • Time: O(E × depth) worst case, but returns early on first cross edge
  • Space: O(1)

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) LCAWithCRS 

func (ga *GraphAnalytics) LCAWithCRS(ctx context.Context, u, v string) (string, error)

LCAWithCRS computes LCA and records a StepRecord to CRS.

Description: 

Wraps HLD.LCA() to provide CRS integration. Records the operation
as a StepRecord with timing, outcome, and result summary.

If CRS is not configured or no active session, falls through to raw HLD call.

Inputs:

  • ctx: Context for cancellation and tracing. Must not be nil.
  • u, v: Node IDs. Must not be empty.

Outputs:

  • string: LCA node ID.
  • error: Non-nil on failure.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) LCDWithCRS 

func (a *GraphAnalytics) LCDWithCRS(
	ctx context.Context,
	domTree *DominatorTree,
	nodes []string,
) (string, crs.TraceStep)

LCDWithCRS wraps LCD query with CRS tracing.

Description: 

Provides the same functionality as LowestCommonDominatorMultiple but also
returns a TraceStep for recording in the Code Reasoning State (CRS).

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • domTree: Pre-computed dominator tree. Must not be nil.
  • nodes: Slice of node IDs to find common dominator for.

Outputs:

  • string: The LCD of all nodes.
  • TraceStep: Trace step for CRS recording.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PackageCoupling 

func (a *GraphAnalytics) PackageCoupling() map[string]CouplingMetrics

PackageCoupling computes coupling metrics for all packages.

Description: 

Computes Robert C. Martin's coupling metrics for each package:

- Afferent Coupling (Ca): packages that depend ON this package
- Efferent Coupling (Ce): packages this package depends ON
- Instability (I): Ce / (Ca + Ce), range [0, 1]
  - I=0: maximally stable (many dependents, no dependencies)
  - I=1: maximally unstable (no dependents, all dependencies)
- Abstractness (A): abstract types / total types

Outputs: 

map[string]CouplingMetrics - Metrics keyed by package path.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PackageCouplingWithCRS 

func (a *GraphAnalytics) PackageCouplingWithCRS(ctx context.Context) (map[string]CouplingMetrics, crs.TraceStep)

PackageCouplingWithCRS returns coupling metrics with a TraceStep.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PageRank 

func (a *GraphAnalytics) PageRank(ctx context.Context, opts *PageRankOptions) *PageRankResult

PageRank computes PageRank scores for all nodes in the graph.

Description: 

Uses power iteration to compute the PageRank score of each node,
which represents its importance based on the importance of nodes
linking to it (transitive importance).

The algorithm handles sink nodes (nodes with no outgoing edges) by
redistributing their PageRank evenly across all nodes, preventing
rank "leakage" from the graph.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • opts: Configuration options. If nil, defaults are used.

Outputs:

  • *PageRankResult: Scores for all nodes, iteration count, convergence status. Returns empty result if graph is nil or empty.

Example: 

opts := graph.DefaultPageRankOptions()
result := analytics.PageRank(ctx, opts)
if result.Converged {
    fmt.Printf("Converged in %d iterations\n", result.Iterations)
}

Thread Safety: Safe for concurrent use.

Complexity: O(k × E) where k = iterations to converge (~20 typical).

Limitations:

  • Single-threaded implementation
  • Memory usage: 2 × V for score maps

func (*GraphAnalytics) PageRankTop 

func (a *GraphAnalytics) PageRankTop(ctx context.Context, k int, opts *PageRankOptions) []PageRankNode

PageRankTop returns the top-k nodes by PageRank score.

Description: 

Computes PageRank for all nodes and returns the top-k ranked nodes.
Each result includes the PageRank score and a comparison degree-based
score for context.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • k: Number of top nodes to return. Must be > 0.
  • opts: Configuration options. If nil, defaults are used.

Outputs: 

[]PageRankNode: Top-k nodes sorted by PageRank score descending.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PageRankTopWithCRS 

func (a *GraphAnalytics) PageRankTopWithCRS(ctx context.Context, k int, opts *PageRankOptions) ([]PageRankNode, crs.TraceStep)

PageRankTopWithCRS returns top-k nodes with a TraceStep for CRS recording.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PageRankWithCRS 

func (a *GraphAnalytics) PageRankWithCRS(ctx context.Context, opts *PageRankOptions) (*PageRankResult, crs.TraceStep)

PageRankWithCRS computes PageRank and returns a TraceStep for CRS recording.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PathGCDWithCRS 

func (ga *GraphAnalytics) PathGCDWithCRS(ctx context.Context, u, v string, valueFunc func(string) int64) (int64, error)

PathGCDWithCRS computes GCD of values on path from u to v with CRS recording.

Description: 

Computes the GCD of node values along the path from u to v using HLD and segment tree.
If BadgerDB caching is enabled, checks cache before computing.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PathMaxWithCRS 

func (ga *GraphAnalytics) PathMaxWithCRS(ctx context.Context, u, v string, valueFunc func(string) int64) (int64, error)

PathMaxWithCRS computes maximum value on path from u to v with CRS recording.

Description: 

Computes the maximum of node values along the path from u to v using HLD and segment tree.
If BadgerDB caching is enabled, checks cache before computing.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PathMinWithCRS 

func (ga *GraphAnalytics) PathMinWithCRS(ctx context.Context, u, v string, valueFunc func(string) int64) (int64, error)

PathMinWithCRS computes minimum value on path from u to v with CRS recording.

Description: 

Computes the minimum of node values along the path from u to v using HLD and segment tree.
If BadgerDB caching is enabled, checks cache before computing.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PathSumWithCRS 

func (ga *GraphAnalytics) PathSumWithCRS(ctx context.Context, u, v string, valueFunc func(string) int64) (int64, error)

PathSumWithCRS computes sum of values on path from u to v with CRS recording.

Description: 

Computes the sum of node values along the path from u to v using HLD and segment tree.
Records operation to CRS for traceability and replay.
If BadgerDB caching is enabled, checks cache before computing.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.
  • valueFunc: Function that returns value for each node. Must not be nil.

Outputs:

  • int64: Sum of values on path u → v.
  • error: Non-nil if nodes don't exist or query fails.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PopSession 

func (ga *GraphAnalytics) PopSession(ctx context.Context) error

PopSession ends the current nested session and restores the previous session from the stack.

Description: 

Ends the current session, clears its history, and restores the previous session
state from the stack. This is the counterpart to PushSession().

Inputs:

  • ctx: Context for cancellation. Must not be nil.

Outputs:

  • error: Non-nil if CRS is not configured, no active session, or stack is empty.

Thread Safety: Safe for concurrent use (protected by mutex).

func (*GraphAnalytics) PostDominators 

func (a *GraphAnalytics) PostDominators(ctx context.Context, exit string) (*DominatorTree, error)

PostDominators computes the post-dominator tree using Cooper-Harvey-Kennedy algorithm.

Description: 

Computes post-dominators by running the dominator algorithm on the reversed
graph. A node A post-dominates B if every path from B to exit must go through A.
This is the dual of dominators: dominators answer "what must happen before X"
while post-dominators answer "what must happen after X".

If exit is empty, auto-detects exit nodes (nodes with no outgoing edges).
If multiple exits are detected, creates a virtual exit node internally.

Inputs:

  • ctx: Context for cancellation. Must not be nil. Checked every iteration.
  • exit: The exit node ID. If empty, auto-detects exits.

Outputs:

  • *DominatorTree: The computed post-dominator tree. Never nil. The Entry field contains the exit node (or virtual exit ID).
  • error: Non-nil if exit not found or context cancelled.

Example: 

dt, err := analytics.PostDominators(ctx, "cleanup")
if err != nil {
    log.Fatalf("failed to compute post-dominators: %v", err)
}
// dt.ImmediateDom maps each node to its immediate post-dominator
for node, ipostdom := range dt.ImmediateDom {
    log.Printf("%s is immediately post-dominated by %s", node, ipostdom)
}

Limitations:

  • Only computes post-dominators for nodes that can reach exit
  • Nodes that cannot reach exit have no entry in ImmediateDom
  • Memory usage: O(V) for all data structures

Assumptions:

  • Graph is frozen (guaranteed by HierarchicalGraph construction)
  • Exit node exists in the graph (if specified)
  • Directed edges represent call relationships

Thread Safety: Safe for concurrent use (read-only on graph).

Complexity: O(E) typical, O(V²) worst case.

func (*GraphAnalytics) PostDominatorsWithCRS 

func (a *GraphAnalytics) PostDominatorsWithCRS(ctx context.Context, exit string) (*DominatorTree, crs.TraceStep)

PostDominatorsWithCRS wraps PostDominators with CRS tracing.

Description: 

Provides the same functionality as PostDominators but also returns
a TraceStep for recording in the Code Reasoning State (CRS).

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) PostDominatorsWithCache 

func (a *GraphAnalytics) PostDominatorsWithCache(ctx context.Context, exit string) (*DominatorTree, crs.TraceStep, error)

PostDominatorsWithCache returns a cached post-dominator tree if available, computing a fresh tree only when needed.

Description: 

Provides the same functionality as PostDominators but caches the result to
avoid recomputation when multiple tools request the post-dominator tree for
the same exit point. The cache is automatically invalidated when:
- A different exit point is requested
- The underlying graph changes (detected via BuiltAtMilli)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • exit: The exit node ID. If empty, auto-detects exits.

Outputs:

  • *DominatorTree: The computed or cached post-dominator tree. Never nil.
  • crs.TraceStep: TraceStep for CRS recording (includes cache_hit metadata).
  • error: Non-nil if exit not found or context cancelled.

Thread Safety: Safe for concurrent use via internal RWMutex.

func (*GraphAnalytics) PushSession 

func (ga *GraphAnalytics) PushSession(ctx context.Context, sessionID string) error

PushSession suspends the current session and starts a new nested session.

Description: 

Saves the current session state onto a stack and starts a new session with
the given sessionID. This allows nested/hierarchical session tracking.
Use PopSession() to end the nested session and restore the previous one.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • sessionID: Unique session identifier for the nested session. Must not be empty.

Outputs:

  • error: Non-nil if CRS is not configured, session ID is empty, or no active session to push.

Thread Safety: Safe for concurrent use (protected by mutex).

Example: 

// Outer operation
analytics.StartSession(ctx, "outer-session")
_, _ = analytics.LCAWithCRS(ctx, "node1", "node2")

// Start nested operation
analytics.PushSession(ctx, "inner-session")
_, _ = analytics.LCAWithCRS(ctx, "node3", "node4")
analytics.PopSession(ctx)

// Back to outer operation
_, _ = analytics.LCAWithCRS(ctx, "node5", "node6")
analytics.EndSession(ctx)

func (*GraphAnalytics) ShortestPath 

func (a *GraphAnalytics) ShortestPath(ctx context.Context, fromID, toID string) (*PathResult, error)

ShortestPath finds the shortest path between two symbols in the graph.

Description: 

D3c: Accessor that delegates to the underlying Graph's ShortestPath method.
Used by filterByReachability to check if a candidate is reachable from the
from-side symbol.

Inputs:

  • ctx: Context for cancellation.
  • fromID: Source symbol ID.
  • toID: Destination symbol ID.

Outputs:

  • *PathResult: Path details or nil if no path exists.
  • error: Non-nil if graph is unavailable or nodes not found.

Thread Safety: Safe for concurrent use.

func (*GraphAnalytics) StartSession 

func (ga *GraphAnalytics) StartSession(ctx context.Context, sessionID string) error

StartSession initializes a new CRS session for query recording.

Description: 

Sets the session ID in CRS and resets the step counter. All subsequent
CRS-aware queries (LCAWithCRS, etc.) will record StepRecords to this session.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • sessionID: Unique session identifier. Must not be empty.

Outputs:

  • error: Non-nil if CRS is not configured or session ID is empty.

Thread Safety: Safe for concurrent use (protected by mutex).

type GraphAnalyticsOptions 

type GraphAnalyticsOptions struct {
	// AutoSession enables automatic session management.
	// When true, CRS-aware queries automatically start a session on first use.
	// User must still call EndSession() to finalize and free resources.
	// Default: false (manual session management required)
	AutoSession bool

	// SessionTimeout defines the maximum inactivity duration before a session expires.
	// When set, if a CRS-aware query is called and the session has been inactive
	// for longer than SessionTimeout, the old session is automatically ended and
	// a new session is started.
	// A value of 0 disables timeout (sessions never expire from inactivity).
	// Default: 0 (no timeout)
	SessionTimeout time.Duration

	// EnableBadgerQueryCache enables cross-session path query caching via BadgerDB.
	// When true, path query results are persisted to BadgerDB and reused across sessions
	// if the graph hash matches (graph unchanged).
	// Cache invalidation: automatic on graph hash change.
	// Default: false (no persistent caching)
	EnableBadgerQueryCache bool

	// BadgerDB is the BadgerDB instance for persistent caching.
	// Required if EnableBadgerQueryCache is true, otherwise ignored.
	// Must be opened and managed by caller.
	BadgerDB *badger.DB
}

GraphAnalyticsOptions configures GraphAnalytics behavior.

type GraphHolder 

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

GraphHolder provides thread-safe access to a mutable graph reference.

Description: 

Wraps a graph pointer with a mutex for thread-safe swapping.
Used by Refresher to atomically update the graph.

Thread Safety: 

All methods are safe for concurrent use.

func NewGraphHolder 

func NewGraphHolder(g *Graph) *GraphHolder

NewGraphHolder creates a new GraphHolder.

func (*GraphHolder) Get 

func (h *GraphHolder) Get() *Graph

Get returns the current graph.

func (*GraphHolder) GetPtr 

func (h *GraphHolder) GetPtr() **Graph

GetPtr returns a pointer to the graph pointer.

Description: 

Returns a pointer suitable for use with NewRefresher.
The returned pointer should only be used with the Refresher.

func (*GraphHolder) Set 

func (h *GraphHolder) Set(g *Graph)

Set replaces the current graph.

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

	// NodesByKind maps each SymbolKind to the count of nodes of that kind.
	// Added for GR-43 debug endpoint.
	NodesByKind map[ast.SymbolKind]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.

Thread Safety: GraphStats is a value type with no internal state. Safe for concurrent use as long as the source Graph is frozen.

type HLDCache 

type HLDCache interface {
	// GetLCA returns cached LCA result, or (empty, false) if not found.
	GetLCA(u, v string) (lca string, found bool)

	// SetLCA stores LCA result with optional TTL.
	SetLCA(u, v, lca string, ttl time.Duration)

	// GetDistance returns cached distance, or (0, false) if not found.
	GetDistance(u, v string) (distance int, found bool)

	// SetDistance stores distance result with optional TTL.
	SetDistance(u, v string, distance int, ttl time.Duration)

	// GetPath returns cached path segments, or (nil, false) if not found.
	GetPath(u, v string) (segments []PathSegment, found bool)

	// SetPath stores path segments with optional TTL.
	SetPath(u, v string, segments []PathSegment, ttl time.Duration)

	// Invalidate removes all cached entries (called when graph changes).
	Invalidate()

	// Stats returns cache statistics.
	Stats() CacheStats
}

HLDCache provides caching for HLD query results.

Description: 

Optional interface for caching expensive query results across invocations.
Implementations can use in-memory caches (LRU, TTL) or persistent stores
(BadgerDB, Redis) depending on requirements.

Thread Safety: All methods must be safe for concurrent use.

type HLDForest 

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

HLDForest represents multiple HLD decompositions for a forest (disconnected graph).

Description: 

A forest is a collection of disconnected trees. This structure maintains
separate HLD decompositions for each tree in the forest.

Thread Safety: 

Read-only after construction. Safe for concurrent queries.

func BuildHLDForest 

func BuildHLDForest(ctx context.Context, g *Graph, useIterative bool) (*HLDForest, error)

BuildHLDForest constructs HLD for each tree in a forest.

Description: 

Detects all connected components in the graph and builds separate
HLD decompositions for each tree. Useful for graphs that may have
multiple disconnected subgraphs.

Algorithm: 

Time:  O(V + E) where V = nodes, E = edges
Space: O(V) for each tree

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • g: Graph (may be forest). Must be frozen, acyclic.
  • useIterative: If true, uses iterative DFS (recommended for deep trees).

Outputs:

  • *HLDForest: Forest structure with HLD for each tree. Never nil on success.
  • error: Non-nil if graph contains cycles or operation is cancelled.

Example: 

forest, err := BuildHLDForest(ctx, graph, true)
if err != nil {
    return fmt.Errorf("build forest: %w", err)
}
fmt.Printf("Forest has %d trees\n", forest.TreeCount())

Thread Safety: Safe for concurrent use with different graphs.

func (*HLDForest) GetHLD 

func (f *HLDForest) GetHLD(nodeID string) *HLDecomposition

GetHLD returns the HLD decomposition for the tree containing the given node.

Returns nil if node is not found in any tree.

func (*HLDForest) GetHLDByIndex 

func (f *HLDForest) GetHLDByIndex(index int) *HLDecomposition

GetHLDByIndex returns the HLD decomposition for the tree at the given index.

Returns nil if index is out of bounds.

func (*HLDForest) GetRoot 

func (f *HLDForest) GetRoot(index int) string

GetRoot returns the root node ID for the tree at the given index.

Returns empty string if index is out of bounds.

func (*HLDForest) GetTreeID 

func (f *HLDForest) GetTreeID(nodeID string) (int, error)

GetTreeID returns the tree index for a given node.

Description: 

Returns the index of the tree containing the specified node.
Used for validating that two nodes are in the same tree component.

Inputs:

  • nodeID: Node to look up. Must exist in forest.

Outputs:

  • int: Tree index (0-based).
  • error: Non-nil if node not found.

Thread Safety: Safe for concurrent use (read-only).

func (*HLDForest) GetTreeOffset 

func (f *HLDForest) GetTreeOffset(nodeID string) (int, error)

GetTreeOffset returns the segment tree position offset for a node's tree.

Description: 

Calculates the cumulative position offset for the tree containing nodeID.
In a forest, segment tree positions are laid out sequentially:
  - Tree 0: positions [0, tree0.NodeCount())
  - Tree 1: positions [tree0.NodeCount(), tree0.NodeCount() + tree1.NodeCount())
  - etc.

To get global segment tree position from tree-local HLD position:
  globalPos = GetTreeOffset(nodeID) + treeHLD.Pos(nodeIdx)

Algorithm: 

Time:  O(T) where T = number of trees (typically small)
Space: O(1)

Inputs:

  • nodeID: Node to get tree offset for. Must exist in forest.

Outputs:

  • int: Position offset for this node's tree (0 for tree 0).
  • error: Non-nil if node not found in forest.

Example: 

// Forest with 2 trees: tree0 has 3 nodes, tree1 has 4 nodes
// Segment tree positions: [0,1,2 | 3,4,5,6]
offset, _ := forest.GetTreeOffset("nodeInTree1") // Returns 3
treeHLD := forest.GetHLD("nodeInTree1")
nodeIdx, _ := treeHLD.NodeToIdx("nodeInTree1")
treePos := treeHLD.Pos(nodeIdx)  // e.g., 0 (local position)
globalPos := offset + treePos     // 3 + 0 = 3 (global position)

Thread Safety: Safe for concurrent use (read-only).

func (*HLDForest) GraphHash 

func (f *HLDForest) GraphHash() string

GraphHash returns combined hash of all trees in the forest.

Description: 

Combines graph hashes from all HLD decompositions to create
a unique identifier for the forest structure.
Used for cache invalidation when graph changes.

Thread Safety: Safe for concurrent use (read-only).

func (*HLDForest) TotalNodes 

func (f *HLDForest) TotalNodes() int

TotalNodes returns the total number of nodes across all trees in the forest.

Description: 

Sums NodeCount() across all HLD decompositions.
Used for validating segment tree size compatibility.

Thread Safety: Safe for concurrent use (read-only).

func (*HLDForest) TreeCount 

func (f *HLDForest) TreeCount() int

TreeCount returns the number of trees in the forest.

func (*HLDForest) Validate 

func (f *HLDForest) Validate() error

Validate checks validity of all HLD decompositions in the forest.

Description: 

Validates each HLD decomposition and checks forest invariants.

Thread Safety: Safe for concurrent use (read-only).

type HLDStats 

type HLDStats struct {
	NodeCount        int
	HeavyPathCount   int
	AvgPathLength    float64
	MaxPathLength    int
	LightEdgeCount   int
	ConstructionTime time.Duration
}

HLDStats contains statistics about the HLD structure.

type HLDecomposition 

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

HLDecomposition represents a Heavy-Light Decomposition of a tree.

Description: 

Decomposes a tree into heavy and light paths, enabling O(log V) path
queries and O(log² V) aggregate queries when combined with segment trees.
The decomposition is computed via DFS and remains static until rebuilt.

Invariants:

  • All arrays have length V (number of nodes)
  • parent[root] == -1
  • heavy[v] == -1 iff v is leaf or all children have subtree size 1
  • head[v] == v iff v starts a new heavy path
  • Positions form valid DFS ordering: parent before children
  • Subtree v occupies positions [pos[v], pos[v]+subSize[v])

Thread Safety: 

Read-only after construction. Safe for concurrent queries.

func BuildHLD 

func BuildHLD(ctx context.Context, g *Graph, root string) (*HLDecomposition, error)

BuildHLD constructs a Heavy-Light Decomposition from a tree graph.

Description: 

Performs three-pass DFS to compute HLD structure:
1. First DFS: Compute subtree sizes, depths, parents
2. Heavy child selection: Identify heavy child for each node
3. Second DFS: Assign heads and positions in DFS order

Algorithm: 

Time:  O(V) where V = number of nodes
Space: O(V) for arrays, O(log V) for recursion stack

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • g: Tree graph. Must be frozen, acyclic, connected.
  • root: Root node ID. Must exist in graph.

Outputs:

  • *HLDecomposition: Constructed HLD structure. Never nil on success.
  • error: Non-nil if graph is invalid (cyclic, disconnected, not frozen).

Optimizations:

  • Single allocation for all arrays (reduces GC pressure)
  • Iterative DFS where possible (reduces stack depth)
  • Pre-computed node count (avoids multiple traversals)
  • Inline heavy child selection (avoids separate pass)

CRS Integration:

  • Records construction as TraceStep with timing and metadata
  • Includes node count, root, light edge count
  • Enables caching of HLD structure across sessions

Example: 

hld, err := BuildHLD(ctx, callGraph, "main")
if err != nil {
    return fmt.Errorf("build HLD: %w", err)
}
// hld is ready for queries

Thread Safety: Safe for concurrent use with different graphs.

func BuildHLDIterative 

func BuildHLDIterative(ctx context.Context, g *Graph, root string) (*HLDecomposition, error)

BuildHLDIterative constructs HLD using iterative DFS (no recursion).

Description: 

Identical to BuildHLD but uses iterative DFS to avoid stack overflow
for deep trees (>10K depth). Recommended for production use with
large or unknown graph structures.

Algorithm: 

Time:  O(V) where V = number of nodes
Space: O(V) for arrays + O(V) for explicit DFS stack

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • g: Tree graph. Must be frozen, acyclic, connected.
  • root: Root node ID. Must exist in graph.

Outputs:

  • *HLDecomposition: Constructed HLD structure. Never nil on success.
  • error: Non-nil if graph is invalid or operation is cancelled.

Differences from BuildHLD:

  • Uses iterative DFS (explicit stack) instead of recursive DFS
  • No stack overflow risk for deep trees
  • Slightly more memory overhead (explicit stack)

Example: 

// For large or deep graphs
hld, err := BuildHLDIterative(ctx, callGraph, "main")
if err != nil {
    return fmt.Errorf("build HLD: %w", err)
}

Thread Safety: Safe for concurrent use with different graphs.

func (*HLDecomposition) BatchDecomposePath 

func (hld *HLDecomposition) BatchDecomposePath(ctx context.Context, pairs [][2]string) ([][]PathSegment, []error, error)

BatchDecomposePath decomposes multiple paths in parallel.

Description: 

Similar to BatchLCA but returns path segments.

Thread Safety: Safe for concurrent use.

func (*HLDecomposition) BatchDistance 

func (hld *HLDecomposition) BatchDistance(ctx context.Context, pairs [][2]string) ([]int, []error, error)

BatchDistance computes distance for multiple node pairs in parallel.

Description: 

Similar to BatchLCA but returns distances instead of LCA nodes.

Thread Safety: Safe for concurrent use.

func (*HLDecomposition) BatchLCA 

func (hld *HLDecomposition) BatchLCA(ctx context.Context, pairs [][2]string) ([]string, []error, error)

BatchLCA computes LCA for multiple node pairs in parallel.

Description: 

Executes multiple LCA queries concurrently, bounded by available CPUs.
Useful for bulk analysis and report generation.
Each query is independent and uses the same HLD structure.

Algorithm: 

Time:  O(N * log V) where N = number of pairs
Space: O(N) for results
Parallelism: Limited to runtime.NumCPU() concurrent queries

Inputs:

  • ctx: Context for cancellation. Cancels all pending queries.
  • pairs: Slice of [2]string, each containing (u, v) node IDs.

Outputs:

  • results: Slice of LCA results, same length as pairs. Empty string on error.
  • errors: Slice of errors, same length as pairs. Nil on success.
  • error: Non-nil only if validation fails. Individual query errors in errors slice.

Performance:

  • 5-10x faster than sequential queries for N > 100
  • Limited by CPU count, not I/O
  • Memory usage: O(N) for results

Example: 

pairs := [][2]string{{"A", "B"}, {"C", "D"}, {"E", "F"}}
results, errs, err := hld.BatchLCA(ctx, pairs)
if err != nil {
    return fmt.Errorf("batch LCA: %w", err)
}
for i, result := range results {
    if errs[i] != nil {
        log.Warn("Query failed", "pair", pairs[i], "error", errs[i])
        continue
    }
    fmt.Printf("LCA(%s, %s) = %s\n", pairs[i][0], pairs[i][1], result)
}

Thread Safety: Safe for concurrent use.

func (*HLDecomposition) CacheKey 

func (hld *HLDecomposition) CacheKey() string

CacheKey generates a cache key for this HLD structure.

Description: 

Returns a deterministic cache key based on root node ID.
For full graph hashing, use with external graph hash.

Thread Safety: Safe for concurrent use (read-only).

func (*HLDecomposition) CacheKeyWithGraphHash 

func (hld *HLDecomposition) CacheKeyWithGraphHash(graphHash string) string

CacheKeyWithGraphHash generates a cache key using pre-computed graph hash.

Description: 

More efficient than CacheKey() when graph hash is already available.
Use this when graph provides its own hash.

Thread Safety: Safe for concurrent use (read-only).

func (*HLDecomposition) DecomposePath 

func (hld *HLDecomposition) DecomposePath(ctx context.Context, u, v string) (segments []PathSegment, err error)

DecomposePath decomposes a path into O(log V) heavy path segments.

Description: 

Breaks the path from u to v into contiguous segments, each lying
entirely on a single heavy path. Returns segments as [Start, End]
position ranges suitable for segment tree queries.

Algorithm:

  1. Compute lca = LCA(u, v)

  2. Decompose upward path u → lca into segments

  3. Decompose upward path v → lca into segments

  4. Return combined list of segments

    Time: O(log V) - at most O(log V) segments Space: O(log V) - segment slice

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.

Outputs:

  • []PathSegment: List of segments covering path u → v. Nil on error.
  • error: Non-nil if nodes don't exist or are in different trees.

Ordering: 

Segments are ordered from leaf to root for each branch:
- First: segments from u upward to lca
- Then: segments from v upward to lca
This ensures correct aggregation order for non-commutative operations.

Memory Management (P-C1 fix): 

P-C1: Removed sync.Pool as it added overhead without benefit.
Now uses simple allocation - caller owns the returned slice.
For batch workloads, see BatchDecomposePath (future enhancement).

Example: 

segments, err := hld.DecomposePath(ctx, "funcA", "funcB")
if err != nil {
    return fmt.Errorf("decompose path: %w", err)
}
for _, seg := range segments {
    value := segmentTree.Query(seg.Start, seg.End)
    // Aggregate values...
}

Limitations:

  • Only works on trees
  • Nodes must be in same tree component
  • Allocates O(log V) memory for segments

Assumptions:

  • HLD structure is valid
  • Segment positions are within bounds

Thread Safety: Safe for concurrent use (allocates new slice per call).

func (*HLDecomposition) Depth 

func (hld *HLDecomposition) Depth(v int) int

Depth returns the depth of node v from root.

func (*HLDecomposition) Distance 

func (hld *HLDecomposition) Distance(ctx context.Context, u, v string) (int, error)

Distance computes the number of edges on the path between u and v.

Description: 

Uses LCA to compute distance: dist(u, v) = depth[u] + depth[v] - 2*depth[lca]
Formula is derived from tree property: any path goes through LCA.

Algorithm: 

Time:  O(log V) - dominated by LCA query
Space: O(1) - no allocations

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.

Outputs:

  • int: Number of edges on path from u to v.
  • error: Non-nil if nodes don't exist or are in different trees.

Special Cases:

  • Distance(u, u) = 0
  • Distance(u, parent[u]) = 1

Performance Note (P-M3): 

If you need both LCA and distance, call LCA() first and compute
distance directly from depths to avoid redundant LCA computation:
  lca, _ := hld.LCA(ctx, u, v)
  uIdx, vIdx := hld.nodeToIdx[u], hld.nodeToIdx[v]
  lcaIdx := hld.nodeToIdx[lca]
  dist := hld.depth[uIdx] + hld.depth[vIdx] - 2*hld.depth[lcaIdx]

Example: 

dist, err := hld.Distance(ctx, "main", "helper")
if err != nil {
    return fmt.Errorf("compute distance: %w", err)
}
fmt.Printf("Distance: %d edges\n", dist)

Limitations:

  • Only works on trees
  • Nodes must be in same tree component

Assumptions:

  • HLD structure is valid
  • Depth array is correct

Thread Safety: Safe for concurrent use (read-only).

func (*HLDecomposition) EstimateDistanceCost 

func (hld *HLDecomposition) EstimateDistanceCost(u, v string) (int, error)

EstimateDistanceCost estimates the cost of a distance query. Same as LCA cost since distance computation is dominated by LCA.

func (*HLDecomposition) EstimateLCACost 

func (hld *HLDecomposition) EstimateLCACost(u, v string) (int, error)

EstimateLCACost estimates the computational cost of an LCA query.

Description: 

Provides conservative estimate of query cost based on node depths.
Cost represents approximate number of iterations needed.
Can be used for query prioritization or rejection.

Algorithm: 

cost = max(depth[u], depth[v])
Worst case: O(depth) iterations when nodes are on different branches.

Inputs:

  • u: First node ID. Must exist in graph.
  • v: Second node ID. Must exist in graph.

Outputs:

  • int: Estimated cost (higher = more expensive query)
  • error: Non-nil if nodes don't exist

Use Cases:

  • Reject queries exceeding cost budget
  • Prioritize cheap queries in batch processing
  • Monitor query patterns for optimization

Example: 

cost, err := hld.EstimateLCACost("deepNode", "anotherDeepNode")
if err != nil {
    return fmt.Errorf("estimate cost: %w", err)
}
if cost > maxAllowedCost {
    return errors.New("query too expensive")
}

Thread Safety: Safe for concurrent use (read-only).

func (*HLDecomposition) EstimatePathCost 

func (hld *HLDecomposition) EstimatePathCost(u, v string) (int, error)

EstimatePathCost estimates the cost of a path decomposition query. Returns 2x LCA cost (decompose both u→lca and v→lca).

func (*HLDecomposition) GetLCAStats 

func (hld *HLDecomposition) GetLCAStats() LCAStats

GetLCAStats returns statistics about LCA queries.

Description: 

Returns aggregated statistics tracked atomically during LCA queries.
Provides insights into query performance and iteration counts.

Note on Consistency (A-H2): 

Stats are eventually consistent. The four atomic fields are loaded
separately, so in high-concurrency scenarios they may represent
slightly different points in time. For most monitoring use cases,
this eventual consistency is acceptable.

Outputs:

  • LCAStats: Statistics about LCA queries

Example (CM-C1): 

stats := hld.GetLCAStats()
fmt.Printf("Queries: %d, Avg iterations: %.1f, Max: %d\n",
    stats.QueryCount, stats.AvgIterations, stats.MaxIterations)
fmt.Printf("Total time: %d ms\n", stats.TotalDurationMs)

Thread Safety: Safe for concurrent use (atomic loads).

func (*HLDecomposition) GraphHash 

func (hld *HLDecomposition) GraphHash() string

GraphHash returns the hash of the graph when HLD was built.

func (*HLDecomposition) Head 

func (hld *HLDecomposition) Head(v int) int

Head returns the head of the heavy path containing node v.

func (*HLDecomposition) HeavyChild 

func (hld *HLDecomposition) HeavyChild(v int) int

HeavyChild returns the heavy child of node v (-1 if none).

func (*HLDecomposition) IdxToNode 

func (hld *HLDecomposition) IdxToNode(idx int) (string, error)

IdxToNode returns the node ID for an internal index.

func (*HLDecomposition) InitStats 

func (hld *HLDecomposition) InitStats()

InitStats initializes LCA query statistics to zero.

Description: 

Called automatically during HLD construction to ensure clean state.
Can also be called to reset stats without rebuilding HLD.

Thread Safety: NOT safe for concurrent use with query operations. 

Call only during construction or when queries are paused.

func (*HLDecomposition) IsAncestor 

func (hld *HLDecomposition) IsAncestor(ctx context.Context, u, v string) (bool, error)

IsAncestor checks if u is an ancestor of v.

Description: 

Node u is an ancestor of v iff LCA(u, v) == u.
Uses LCA query internally, so has same O(log V) complexity.

Algorithm: 

Time:  O(log V) - requires LCA query
Space: O(1)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Potential ancestor node ID. Must exist in graph.
  • v: Potential descendant node ID. Must exist in graph.

Outputs:

  • bool: True if u is ancestor of v (or u == v).
  • error: Non-nil if nodes don't exist or are in different trees.

Example (CM-C1): 

isAncestor, err := hld.IsAncestor(ctx, "main", "helper")
if err != nil {
    return fmt.Errorf("check ancestry: %w", err)
}
if isAncestor {
    fmt.Println("main calls helper (directly or indirectly)")
}

Assumptions (CM-H1):

  • HLD has been built successfully
  • Graph structure hasn't changed since construction

Thread Safety: Safe for concurrent use (read-only).

func (*HLDecomposition) LCA 

func (hld *HLDecomposition) LCA(ctx context.Context, u, v string) (lca string, err error)

LCA computes the Lowest Common Ancestor of two nodes.

Description: 

Finds the deepest node that is an ancestor of both u and v using
Heavy-Light Decomposition. Repeatedly jumps up light edges until
both nodes are on the same heavy path, then returns the shallower one.

Algorithm: 

Time:  O(log V) - at most O(log V) light edge jumps
Space: O(1) - no allocations

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: First node ID. Must exist in graph.
  • v: Second node ID. Must exist in graph.

Outputs:

  • lca: Node ID of LCA. Empty string on error.
  • err: Non-nil if nodes don't exist, are in different trees, or HLD invalid.

Special Cases:

  • LCA(u, u) = u
  • LCA(u, parent[u]) = parent[u]
  • LCA(u, v) where u is ancestor of v = u

Example: 

lca, err := hld.LCA(ctx, "funcA", "funcB")
if err != nil {
    return fmt.Errorf("compute LCA: %w", err)
}
fmt.Printf("LCA of funcA and funcB: %s\n", lca)

Limitations:

  • SINGLE-TREE ONLY: This implementation does not support forest mode. For graphs with multiple disconnected tree components, nodes must be in the same component. Cross-tree queries will return incorrect results. Use HLDForest for multi-tree support when implemented.
  • Graph must not change after HLD construction

Assumptions:

  • HLD has been built successfully via BuildHLD or BuildHLDIterative
  • Graph structure hasn't changed since HLD construction
  • For forest graphs, caller has validated nodes are in same tree

Thread Safety: 

Safe for concurrent use. All methods use pointer receivers because:
1. HLD struct is large (~10+ arrays)
2. Methods update atomic stats fields
3. Read-only operations are safe for concurrent use

func (*HLDecomposition) NodeAtPos 

func (hld *HLDecomposition) NodeAtPos(i int) int

NodeAtPos returns the node at DFS position i.

func (*HLDecomposition) NodeCount 

func (hld *HLDecomposition) NodeCount() int

NodeCount returns the number of nodes in the HLD.

func (*HLDecomposition) NodeToIdx 

func (hld *HLDecomposition) NodeToIdx(nodeID string) (int, bool)

NodeToIdx returns the internal index for a node ID.

func (*HLDecomposition) Parent 

func (hld *HLDecomposition) Parent(v int) int

Parent returns the parent index of node v (-1 for root).

func (*HLDecomposition) PathNodes 

func (hld *HLDecomposition) PathNodes(ctx context.Context, u, v string) ([]string, error)

PathNodes returns all node IDs on the path from u to v.

Description: 

Materializes the actual path as a list of node IDs from u to v.
Useful for debugging and visualization, but slower than decomposition.

Algorithm:

  1. Compute lca = LCA(u, v)

  2. Collect nodes from u upward to lca

  3. Collect nodes from v upward to lca (in reverse order)

  4. Concatenate both paths with lca in middle

    Time: O(distance(u,v)) - proportional to path length Space: O(distance(u,v)) - stores all node IDs on path

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.

Outputs:

  • []string: Node IDs from u to v (inclusive). Nil on error.
  • error: Non-nil if nodes don't exist or are in different trees.

Example: 

path, err := hld.PathNodes(ctx, "funcA", "funcB")
if err != nil {
    return fmt.Errorf("get path: %w", err)
}
fmt.Printf("Call path: %v\n", path)

Limitations:

  • Allocates O(distance) memory
  • Slower than DecomposePath for queries on large paths
  • Not suitable for aggregate queries (use DecomposePath instead)

Thread Safety: Safe for concurrent use (allocates new slice).

func (*HLDecomposition) Pos 

func (hld *HLDecomposition) Pos(v int) int

Pos returns the DFS position of node v.

func (*HLDecomposition) SerializeMetadata 

func (hld *HLDecomposition) SerializeMetadata() map[string]string

SerializeMetadata returns HLD metadata for CRS TraceStep.

func (*HLDecomposition) Stats 

func (hld *HLDecomposition) Stats() HLDStats

Stats returns statistics about the HLD structure.

Description: 

Computes:
- Number of heavy paths
- Average heavy path length
- Maximum heavy path length
- Light edge count
Useful for debugging and performance analysis.

Thread Safety: Safe for concurrent use (read-only).

func (*HLDecomposition) SubtreeSize 

func (hld *HLDecomposition) SubtreeSize(v int) int

SubtreeSize returns the subtree size rooted at node v.

func (*HLDecomposition) Validate 

func (hld *HLDecomposition) Validate() error

Validate checks HLD invariants after construction.

Description: 

Verifies:
- All arrays have correct length
- Root has parent -1
- Depths are valid (parent depth < child depth)
- Subtree sizes are consistent
- Heavy paths are well-formed
- Position mapping is bijective

Complexity: O(V) time

Thread Safety: Safe for concurrent use (read-only).

func (*HLDecomposition) ValidateGraphHash 

func (hld *HLDecomposition) ValidateGraphHash(g *Graph) error

ValidateGraphHash checks if graph has changed since HLD construction.

Description: 

Compares stored graph hash with current graph hash.
Returns error if graph has changed, preventing stale results.

Inputs:

  • g: Graph to validate against

Outputs:

  • error: Non-nil if graph has changed or hash unavailable

Limitations:

  • Requires HLD to have been built with graph hash
  • Graph must provide Hash() method

Example: 

if err := hld.ValidateGraphHash(graph); err != nil {
    log.Warn("Graph changed, rebuilding HLD")
    hld = BuildHLD(ctx, graph, root)
}

Thread Safety: Safe for concurrent use (read-only).

func (*HLDecomposition) Version 

func (hld *HLDecomposition) Version() int

Version returns the HLD schema version.

type HierarchicalGraph 

type HierarchicalGraph struct {
	// Embedded graph provides all base functionality.
	*Graph
	// contains filtered or unexported fields
}

HierarchicalGraph wraps a Graph with hierarchical indexes for efficient package-level and file-level queries.

Description: 

HierarchicalGraph embeds the base Graph and adds:
- O(1) package lookup via packageIndex
- O(1) file lookup via fileIndex
- O(1) kind lookup via kindIndex
- Cached cross-package edges
- Package metadata with counts

Thread Safety: 

After construction, HierarchicalGraph is safe for concurrent reads.
Indexes are built during construction and never mutated.

Performance: 

| Operation | Complexity |
|-----------|------------|
| GetNodesInPackage | O(1) lookup + O(k) copy |
| GetNodesInFile | O(1) lookup + O(k) copy |
| GetCrossPackageEdges | O(1) cached |
| GetPackages | O(1) cached |

func WrapGraph 

func WrapGraph(g *Graph) (*HierarchicalGraph, error)

WrapGraph creates a HierarchicalGraph from an existing frozen Graph.

Description: 

Wraps the given Graph and builds hierarchical indexes. The graph
must be frozen (read-only) before wrapping.

Inputs: 

g - The graph to wrap. Must be frozen (IsFrozen() == true).

Outputs: 

*HierarchicalGraph - The wrapped graph with indexes. Never nil.
error - Non-nil if the graph is not frozen.

Thread Safety: 

The returned HierarchicalGraph is safe for concurrent reads.

func (*HierarchicalGraph) DrillDown 

func (hg *HierarchicalGraph) DrillDown(level int, id string) []*Node

DrillDown returns children at the next hierarchy level.

Description: 

Starting from an entity at the given level, returns the entities
one level deeper in the hierarchy.

Level 0 (Project) → Level 1 (Packages): Returns all packages
Level 1 (Package) → Level 2 (Files): Returns files in the package
Level 2 (File) → Level 3 (Symbols): Returns symbols in the file
Level 3 (Symbol): No children, returns empty

Inputs: 

level - The current hierarchy level (0-3).
id - The entity ID (empty for project, pkg path, file path, or node ID).

Outputs: 

[]*Node - Child nodes at the next level. For levels 0-1, returns
          representative nodes. For level 2, returns actual symbol nodes.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) DrillDownWithCRS 

func (hg *HierarchicalGraph) DrillDownWithCRS(ctx context.Context, level int, id string) ([]*Node, crs.TraceStep)

DrillDownWithCRS returns children and a TraceStep.

Inputs: 

ctx - Context for cancellation.
level - The current hierarchy level.
id - The entity ID.

Outputs: 

[]*Node - Child nodes at the next level.
crs.TraceStep - TraceStep with navigation metadata.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetCrossPackageEdges 

func (hg *HierarchicalGraph) GetCrossPackageEdges() []*Edge

GetCrossPackageEdges returns all edges that cross package boundaries.

Description: 

O(1) cached access, returns defensive copy of edge slice.

Outputs: 

[]*Edge - Edges where source and target are in different packages.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetFilesInPackage 

func (hg *HierarchicalGraph) GetFilesInPackage(pkg string) []string

GetFilesInPackage returns all file paths in a package.

Inputs: 

pkg - The package path to look up.

Outputs: 

[]string - File paths in the package, empty slice if not found.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetInternalEdges 

func (hg *HierarchicalGraph) GetInternalEdges() []*Edge

GetInternalEdges returns all edges within the same package.

Description: 

O(1) cached access, returns defensive copy of edge slice.

Outputs: 

[]*Edge - Edges where source and target are in the same package.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetNodesByKind 

func (hg *HierarchicalGraph) GetNodesByKind(kind ast.SymbolKind) []*Node

GetNodesByKind returns all nodes of a specific kind.

Description: 

O(1) lookup via kindIndex, returns defensive copy of node slice.

Inputs: 

kind - The symbol kind to filter by.

Outputs: 

[]*Node - Nodes of that kind, empty slice if none found.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetNodesInFile 

func (hg *HierarchicalGraph) GetNodesInFile(filePath string) []*Node

GetNodesInFile returns all nodes defined in a file.

Description: 

O(1) lookup via fileIndex, returns defensive copy of node slice.

Inputs: 

filePath - The file path to look up.

Outputs: 

[]*Node - Nodes in the file, empty slice if not found.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetNodesInPackage 

func (hg *HierarchicalGraph) GetNodesInPackage(pkg string) []*Node

GetNodesInPackage returns all nodes in a package.

Description: 

O(1) lookup via packageIndex, returns defensive copy of node slice.

Inputs: 

pkg - The package path to look up.

Outputs: 

[]*Node - Nodes in the package, empty slice if not found.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetNodesInPackageWithCRS 

func (hg *HierarchicalGraph) GetNodesInPackageWithCRS(ctx context.Context, pkg string) ([]*Node, crs.TraceStep)

GetNodesInPackageWithCRS returns nodes in a package and a TraceStep.

Description: 

Same as GetNodesInPackage but also returns a TraceStep for CRS recording.

Inputs: 

ctx - Context for cancellation (checked but not currently used).
pkg - The package path to look up.

Outputs: 

[]*Node - Nodes in the package.
crs.TraceStep - TraceStep with query metadata.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetPackageDependencies 

func (hg *HierarchicalGraph) GetPackageDependencies(pkg string) []string

GetPackageDependencies returns packages that the given package imports.

Description: 

Finds all packages that have IMPORTS edges from the given package,
or CALLS/REFERENCES edges to symbols in other packages.

Inputs: 

pkg - The package path to analyze.

Outputs: 

[]string - Package paths that this package depends on.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetPackageDependents 

func (hg *HierarchicalGraph) GetPackageDependents(pkg string) []string

GetPackageDependents returns packages that import the given package.

Description: 

Finds all packages that have incoming edges from the given package
(reverse of GetPackageDependencies).

Inputs: 

pkg - The package path to analyze.

Outputs: 

[]string - Package paths that depend on this package.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetPackageInfo 

func (hg *HierarchicalGraph) GetPackageInfo(pkg string) *PackageInfo

GetPackageInfo returns metadata for a specific package.

Inputs: 

pkg - The package path to look up.

Outputs: 

*PackageInfo - Package metadata, or nil if not found.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetPackageNames 

func (hg *HierarchicalGraph) GetPackageNames() []string

GetPackageNames returns a sorted list of all package names.

Outputs: 

[]string - Sorted package names.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetPackageSiblings 

func (hg *HierarchicalGraph) GetPackageSiblings(nodeID string) []string

GetPackageSiblings returns other files in the same package as the node.

Inputs: 

nodeID - The node ID to find package siblings for.

Outputs: 

[]string - File paths of sibling files (not including the node's file).

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetPackages 

func (hg *HierarchicalGraph) GetPackages() []PackageInfo

GetPackages returns metadata for all packages in the graph.

Description: 

Returns a sorted list of PackageInfo for all packages, including
node counts, file counts, and coupling metrics.

Outputs: 

[]PackageInfo - Package metadata, sorted by package name.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetPackagesWithCRS 

func (hg *HierarchicalGraph) GetPackagesWithCRS(ctx context.Context) ([]PackageInfo, crs.TraceStep)

GetPackagesWithCRS returns package info and a TraceStep.

Inputs: 

ctx - Context for cancellation.

Outputs: 

[]PackageInfo - Package metadata.
crs.TraceStep - TraceStep with query metadata.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) GetSiblings 

func (hg *HierarchicalGraph) GetSiblings(nodeID string) []*Node

GetSiblings returns nodes at the same hierarchy level as the given node.

Description: 

Returns other nodes that share the same parent. For a symbol, returns
other symbols in the same file. For a file (identified by any symbol
in it), returns other files in the same package.

Inputs: 

nodeID - The node ID to find siblings for.

Outputs: 

[]*Node - Sibling nodes (not including the input node itself).

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) IsProductionFile 

func (hg *HierarchicalGraph) IsProductionFile(filePath string) bool

IsProductionFile returns true if the file is classified as production code.

Description: 

If a FileClassification has been set (via SetFileClassification), delegates
to fc.IsProduction(filePath). If no classification is set, falls back to
heuristic checks: !isTestFilePath(filePath) && !isDocFilePath(filePath).
This preserves existing behavior when the classification feature is not used.

Inputs: 

filePath - The file path to check.

Outputs: 

bool - True if the file is production code.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) RollUp 

func (hg *HierarchicalGraph) RollUp(nodeID string) (string, int)

RollUp returns the parent entity ID at the previous hierarchy level.

Description: 

Given a node ID, returns the parent entity:
Symbol → File path
File → Package path
Package → "" (project root)
Project → "" (no parent)

Inputs: 

nodeID - The node ID to get the parent for.

Outputs: 

string - The parent entity ID, or empty string if at root.
int - The parent's hierarchy level.

Thread Safety: Safe for concurrent use.

func (*HierarchicalGraph) SetFileClassification 

func (hg *HierarchicalGraph) SetFileClassification(fc *FileClassification)

SetFileClassification stores a computed file classification on the graph.

Description: 

Called after ClassifyFiles() to attach the classification to the graph.
Subsequent calls to IsProductionFile() will use this classification
instead of the heuristic fallback.

Inputs: 

fc - The file classification to store. May be nil (clears classification).

Thread Safety: NOT safe for concurrent use with IsProductionFile reads. Must be called during initialization (RegisterExploreTools) before any tool execution begins. After this call, IsProductionFile is safe for concurrent reads.

type HotspotNode 

type HotspotNode struct {
	// Node is the graph node.
	Node *Node

	// Score is the connectivity score (higher = more connected).
	// Computed as: inDegree*2 + outDegree*1
	Score int

	// InDegree is the number of incoming edges.
	InDegree int

	// OutDegree is the number of outgoing edges.
	OutDegree int
}

HotspotNode represents a node with its connectivity score.

type IncrementalResult 

type IncrementalResult struct {
	// Graph is the updated graph (frozen, read-only).
	Graph *Graph

	// Strategy is "incremental" or "full_rebuild".
	Strategy string

	// ChangedFiles is the list of files that were refreshed.
	ChangedFiles []string

	// NodesRemoved is the count of nodes removed from changed files.
	NodesRemoved int

	// NodesAdded is the count of nodes added from re-parsed files.
	NodesAdded int

	// EdgesCreated is the count of edges created during re-extraction.
	EdgesCreated int

	// DurationMilli is the total time for the incremental refresh.
	DurationMilli int64

	// FallbackReason is non-empty if a full rebuild was used instead.
	FallbackReason string

	// EnrichmentStats contains LSP enrichment results for the changed files.
	// Zero-valued if LSP enrichment was not configured or not run.
	// GR-76: Populated by Phase 6 when lspConfig is provided.
	EnrichmentStats EnrichmentStats
}

IncrementalResult contains the outcome of an incremental graph refresh.

Thread Safety: Immutable after construction.

func IncrementalRefresh 

func IncrementalRefresh(
	ctx context.Context,
	baseGraph *Graph,
	changedFiles []string,
	changedResults []*ast.ParseResult,
	lspConfig *LSPEnrichmentConfig,
) (*IncrementalResult, error)

IncrementalRefresh applies changes to a previously-saved graph by removing nodes/edges for changed files and re-adding them from fresh parse results.

Description: 

Given a base graph (from a prior snapshot) and parse results for changed
files, this function:
  1. Clones the base graph to get a writable copy
  2. Removes all nodes and edges for each changed file
  3. Adds new nodes from the parse results
  4. Re-extracts per-file edges for the changed files
  5. Freezes the updated graph

Cross-file resolution (interface matching, Python import resolution) is
NOT re-run. Existing edges from unchanged files are preserved via Clone.
For changed files, per-file edges (imports, calls, returns) are re-extracted
against the full symbol set. If structural changes affect cross-file edges
(e.g., interface method additions, renamed exports), CRS-19 graph staleness
detection catches the discrepancy.

Inputs:

  • ctx: Context for cancellation and tracing. Must not be nil.
  • baseGraph: The previous session's graph (frozen). Must not be nil.
  • changedFiles: File paths (relative to project root) that changed.
  • changedResults: Parse results for ONLY the changed files.

Outputs:

  • *IncrementalResult: The result of the refresh operation.
  • error: Non-nil if the operation fails.

Limitations:

  • Cross-file edges FROM unchanged files TO renamed symbols are not updated.
  • Interface implementation edges are not recomputed (use full rebuild for interface signature changes).

Thread Safety: Safe for concurrent use (creates a new graph via Clone).

type InheritanceQueryResult 

type InheritanceQueryResult struct {
	// DirectCallers are callers of the primary (queried) method.
	DirectCallers *QueryResult

	// InheritedCallers maps parent method ID to callers of that parent method.
	// Only includes callers NOT already in DirectCallers (deduplicated).
	InheritedCallers map[string]*QueryResult

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

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

InheritanceQueryResult separates direct callers from inherited callers.

Description: 

Returned by FindCallersWithInheritance to allow the caller to distinguish
between direct callers of the queried method and callers that reach it
through parent class methods in the inheritance chain.

Example: 

result, err := g.FindCallersWithInheritance(ctx, plotRenderID, parentIDs)
// result.DirectCallers has callers of Plot.render
// result.InheritedCallers["Component.render ID"] has callers of Component.render

func (*InheritanceQueryResult) AllCallers 

func (r *InheritanceQueryResult) AllCallers() *QueryResult

AllCallers returns a flat deduplicated list of all callers (direct + inherited).

Description: 

Convenience method that merges DirectCallers and InheritedCallers into a
single QueryResult. Useful when the caller doesn't need to distinguish
between direct and inherited callers.

func (*InheritanceQueryResult) TotalCallerCount 

func (r *InheritanceQueryResult) TotalCallerCount() int

TotalCallerCount returns the total number of callers across all levels.

type IrreducibleRegion 

type IrreducibleRegion struct {
	// ID is a unique 0-indexed identifier for this region.
	ID int

	// EntryNodes are the multiple entry points to this region.
	// An irreducible region has >= 2 entry points.
	EntryNodes []string

	// Nodes contains all nodes in this irreducible region.
	Nodes []string

	// Size is the number of nodes in the region.
	Size int

	// CrossEdges are the edges that form this irreducible pattern.
	CrossEdges [][2]string

	// Reason explains why this region is irreducible.
	Reason string
}

IrreducibleRegion represents a detected irreducible subgraph.

An irreducible region has multiple entry points - nodes that can be reached from outside the region via different paths.

Thread Safety: Safe for concurrent use after construction.

type LCAQueryEngine 

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

LCAQueryEngine provides O(1) LCD queries after O(V log V) preprocessing.

Description: 

Uses binary lifting to precompute 2^k-th ancestors for each node.
This enables O(log depth) queries instead of O(depth), which is
effectively O(1) for practical tree depths.

Thread Safety: Safe for concurrent use after construction.

func (*LCAQueryEngine) Query 

func (lca *LCAQueryEngine) Query(a, b string) string

Query returns LCD in O(log depth) time after preprocessing.

Description: 

Uses the precomputed binary lifting table to find the LCD
efficiently. First lifts the deeper node to the same depth,
then binary searches for the LCD.

Inputs:

  • a, b: Node IDs to query.

Outputs:

  • string: The LCD node ID.

Thread Safety: Safe for concurrent use.

Complexity: O(log depth) per query.

type LCAStats 

type LCAStats struct {
	QueryCount      int64   // Total LCA queries (Unix milliseconds UTC)
	AvgIterations   float64 // Average iterations per query
	MaxIterations   int32   // Maximum iterations seen (int32 for atomic.CompareAndSwapInt32)
	TotalDurationMs int64   // Total duration in milliseconds (Unix milliseconds per CLAUDE.md §4.6)
}

LCAStats tracks LCA query statistics.

Description: 

Statistics are tracked atomically for thread-safe access.
All durations stored as Unix milliseconds for consistency with CLAUDE.md §4.6.

Note on Consistency (A-H2): 

Stats are eventually consistent. In high-concurrency scenarios,
the four fields may be from slightly different snapshots.
For precise snapshots, use external synchronization.

Thread Safety: Safe for concurrent access (atomic operations).

type LRUCache 

type LRUCache[K comparable, V any] struct {
	// contains filtered or unexported fields
}

LRUCache is a thread-safe LRU cache with generics support.

Description: 

Implements a fixed-size cache that evicts the least recently used
entries when capacity is reached. Uses container/list for O(1)
access and eviction.

Thread Safety: All methods are safe for concurrent use.

Performance: 

| Operation | Complexity |
|-----------|------------|
| Get       | O(1)       |
| Set       | O(1)       |
| Delete    | O(1)       |
| Purge     | O(n)       |

func NewLRUCache 

func NewLRUCache[K comparable, V any](capacity int) *LRUCache[K, V]

NewLRUCache creates a new LRU cache with the given capacity.

Description: 

Creates a fixed-size LRU cache. When the cache is full, the least
recently accessed entry is evicted to make room for new entries.

Inputs:

  • capacity: Maximum number of entries. Must be > 0.

Outputs:

  • *LRUCache[K, V]: The cache. Never nil.

Example: 

cache := NewLRUCache[string, *QueryResult](1000)
cache.Set("key", result)
if val, ok := cache.Get("key"); ok {
    // use val
}

Thread Safety: The returned cache is safe for concurrent use.

func (*LRUCache[K, V]) Delete 

func (c *LRUCache[K, V]) Delete(key K) bool

Delete removes a key from the cache.

Inputs:

  • key: The key to remove.

Outputs:

  • bool: True if the key was found and removed.

Thread Safety: Safe for concurrent use.

func (*LRUCache[K, V]) Evictions 

func (c *LRUCache[K, V]) Evictions() int64

Evictions returns the number of cache evictions since creation or last purge.

Description: 

GR-10 Review (O-1): Tracks evictions for monitoring cache effectiveness.
High eviction count relative to cache size indicates capacity may be too small.

Outputs:

  • evictions: Number of entries evicted due to capacity limits.

Thread Safety: Safe for concurrent use (lock-free).

func (*LRUCache[K, V]) Get 

func (c *LRUCache[K, V]) Get(key K) (V, bool)

Get retrieves a value from the cache.

Description: 

Returns the value associated with the key and moves it to the
front of the LRU list (most recently used).

Inputs:

  • key: The key to look up.

Outputs:

  • V: The value (zero value if not found).
  • bool: True if the key was found.

Thread Safety: Safe for concurrent use.

func (*LRUCache[K, V]) Len 

func (c *LRUCache[K, V]) Len() int

Len returns the number of entries in the cache.

Thread Safety: Safe for concurrent use.

func (*LRUCache[K, V]) Purge 

func (c *LRUCache[K, V]) Purge()

Purge clears all entries from the cache.

Description: 

Removes all entries and resets hit/miss/eviction counters.

Thread Safety: Safe for concurrent use.

func (*LRUCache[K, V]) Set 

func (c *LRUCache[K, V]) Set(key K, value V)

Set adds or updates a value in the cache.

Description: 

Adds the key-value pair to the cache. If the key exists, updates
the value and moves it to the front. If the cache is full, evicts
the least recently used entry.

Inputs:

  • key: The key to store.
  • value: The value to associate with the key.

Thread Safety: Safe for concurrent use.

func (*LRUCache[K, V]) Stats 

func (c *LRUCache[K, V]) Stats() (hits, misses int64)

Stats returns cache hit/miss/eviction statistics.

Outputs:

  • hits: Number of cache hits since creation or last purge.
  • misses: Number of cache misses since creation or last purge.

Thread Safety: Safe for concurrent use (lock-free).

type LSPEnrichmentConfig 

type LSPEnrichmentConfig struct {
	// Querier provides LSP operations. Required — enrichment is skipped if nil.
	Querier LSPQuerier

	// Manager provides IsAvailable checks. Optional — if nil, all languages are attempted.
	Manager *lsp.Manager

	// MaxConcurrentFiles is the maximum number of files processed in parallel.
	// Default: 4
	MaxConcurrentFiles int

	// PerFileTimeout is the maximum time to process a single file's enrichment queries.
	// Default: 30s
	PerFileTimeout time.Duration

	// TotalTimeout is the maximum time for the entire enrichment phase.
	// Default: 120s
	TotalTimeout time.Duration

	// Languages is the list of languages to enrich. Placeholders from other languages
	// are skipped. Default: ["python", "typescript", "javascript"]
	// Note: JavaScript uses the same typescript-language-server binary as TypeScript.
	Languages []string

	// FileReader overrides the default os.ReadFile for reading source files.
	// If nil, os.ReadFile is used. Provided for testability.
	FileReader func(path string) ([]byte, error)
}

LSPEnrichmentConfig configures the LSP enrichment phase.

Description: 

GR-74: Controls which LSP server to query, timeouts, parallelism, and
which languages to enrich. When added to BuilderOptions via
WithLSPEnrichment, the builder runs an enrichment phase after edge extraction.

Thread Safety: 

Immutable after construction.

type LSPQuerier 

type LSPQuerier interface {
	// OpenDocument notifies the LSP server that a document was opened.
	//
	// Inputs:
	//
	//	ctx - Context for cancellation and timeout
	//	filePath - Absolute path to the file
	//	content - The file content
	//
	// Outputs:
	//
	//	error - Non-nil on failure
	OpenDocument(ctx context.Context, filePath, content string) error

	// CloseDocument notifies the LSP server that a document was closed.
	//
	// Inputs:
	//
	//	ctx - Context for cancellation and timeout
	//	filePath - Absolute path to the file
	//
	// Outputs:
	//
	//	error - Non-nil on failure
	CloseDocument(ctx context.Context, filePath string) error

	// Definition returns the definition location(s) for a symbol.
	//
	// Inputs:
	//
	//	ctx - Context for cancellation and timeout
	//	filePath - Absolute path to the file
	//	line - 1-indexed line number
	//	col - 0-indexed column number
	//
	// Outputs:
	//
	//	[]lsp.Location - Definition location(s)
	//	error - Non-nil on failure
	Definition(ctx context.Context, filePath string, line, col int) ([]lsp.Location, error)
}

LSPQuerier abstracts LSP operations for testability.

Description: 

GR-74: The graph builder uses this interface instead of calling lsp.Operations
directly. This allows tests to provide mock implementations that return
deterministic results without requiring actual LSP servers.

Thread Safety: 

Implementations must be safe for concurrent use from multiple goroutines.

type LeidenOptions 

type LeidenOptions struct {
	// MaxIterations limits total outer loop passes. Default: 100
	MaxIterations int

	// ConvergenceThreshold stops early if modularity gain < this. Default: 1e-6
	ConvergenceThreshold float64

	// MinCommunitySize filters out tiny communities from results. Default: 1
	MinCommunitySize int

	// Resolution affects community granularity. Default: 1.0
	// Higher values produce smaller, more granular communities.
	// Lower values produce larger, coarser communities.
	Resolution float64
}

LeidenOptions configures the Leiden algorithm.

func DefaultLeidenOptions 

func DefaultLeidenOptions() *LeidenOptions

DefaultLeidenOptions returns sensible defaults.

func (*LeidenOptions) Validate 

func (o *LeidenOptions) Validate()

Validate checks options and applies defaults for invalid values.

type Loop 

type Loop struct {
	// Header is the loop header node ID (the dominator).
	// The header is the single entry point to the loop.
	Header string

	// BackEdges contains edges that form this loop.
	// Each entry is [fromID, toID] where toID is the header.
	BackEdges [][2]string

	// Body contains all node IDs in the loop body (including header).
	// Computed via reverse BFS from back edge sources.
	Body []string

	// Size is the number of nodes in the loop body.
	Size int

	// Depth is the nesting depth (0 = top-level loop).
	Depth int

	// Parent is the enclosing loop (nil if top-level).
	Parent *Loop

	// Children are nested loops within this loop.
	Children []*Loop
}

Loop represents a natural loop in the graph.

A natural loop is defined by a back edge A→B where B dominates A. The header B is the single entry point to the loop.

Thread Safety: Safe for concurrent use after construction.

type LoopDetectionError 

type LoopDetectionError struct {
	Message string
}

LoopDetectionError represents an error in loop detection.

func (*LoopDetectionError) Error 

func (e *LoopDetectionError) Error() string

type LoopNest 

type LoopNest struct {
	// Loops contains all detected loops.
	Loops []*Loop

	// TopLevel contains loops with no parent.
	TopLevel []*Loop

	// LoopOf maps node ID → innermost containing loop.
	LoopOf map[string]*Loop

	// MaxDepth is the maximum nesting depth.
	MaxDepth int

	// BackEdgeCount is the total number of back edges found.
	BackEdgeCount int

	// DomTree is the dominator tree used for detection.
	DomTree *DominatorTree
}

LoopNest represents the complete loop nesting structure.

Thread Safety: Safe for concurrent use after construction.

func (*LoopNest) GetInnermostLoop 

func (ln *LoopNest) GetInnermostLoop(nodeID string) *Loop

GetInnermostLoop returns the innermost loop containing a node.

Description: 

Returns the most deeply nested loop that contains the specified node.
For nested loops, this returns the inner loop, not the outer one.

Inputs:

  • nodeID: The node to query. Must be a valid node ID.

Outputs:

  • *Loop: The innermost containing loop, or nil if not in any loop.

Limitations:

  • Returns nil if receiver is nil or nodeID is not in any loop.

Thread Safety: Safe for concurrent use.

Complexity: O(1) map lookup.

func (*LoopNest) GetLoopByHeader 

func (ln *LoopNest) GetLoopByHeader(headerID string) *Loop

GetLoopByHeader returns the loop with the specified header.

Description: 

Finds the loop whose header matches the specified node ID.
Each loop has exactly one header.

Inputs:

  • headerID: The header node ID to search for.

Outputs:

  • *Loop: The loop with this header, or nil if no such loop exists.

Limitations:

  • Returns nil if receiver is nil or no loop has this header.
  • Linear search through loops.

Thread Safety: Safe for concurrent use.

Complexity: O(loops) linear search.

func (*LoopNest) IsInLoop 

func (ln *LoopNest) IsInLoop(nodeID string) bool

IsInLoop checks if a node is inside any loop.

Description: 

Returns true if the specified node is part of any detected loop body.
This includes loop headers and all nodes within loop bodies.

Inputs:

  • nodeID: The node to check. Must be a valid node ID.

Outputs:

  • bool: True if the node is in any loop, false otherwise.

Limitations:

  • Returns false if receiver is nil or nodeID is not in any loop.

Thread Safety: Safe for concurrent use.

Complexity: O(1) map lookup.

func (*LoopNest) IsLoopHeader 

func (ln *LoopNest) IsLoopHeader(nodeID string) bool

IsLoopHeader returns true if the node is a loop header.

Description: 

Checks if the specified node is the header (entry point) of any loop.

Inputs:

  • nodeID: The node to check. Must be a valid node ID.

Outputs:

  • bool: True if the node is a loop header, false otherwise.

Limitations:

  • Returns false if receiver is nil.

Thread Safety: Safe for concurrent use.

Complexity: O(loops) linear search.

type NoOpCache 

type NoOpCache struct{}

NoOpCache is a cache that does nothing (always misses). Used as default when no cache is configured.

func (NoOpCache) GetDistance 

func (NoOpCache) GetDistance(u, v string) (int, bool)

func (NoOpCache) GetLCA 

func (NoOpCache) GetLCA(u, v string) (string, bool)

func (NoOpCache) GetPath 

func (NoOpCache) GetPath(u, v string) ([]PathSegment, bool)

func (NoOpCache) Invalidate 

func (NoOpCache) Invalidate()

func (NoOpCache) SetDistance 

func (NoOpCache) SetDistance(u, v string, distance int, ttl time.Duration)

func (NoOpCache) SetLCA 

func (NoOpCache) SetLCA(u, v, lca string, ttl time.Duration)

func (NoOpCache) SetPath 

func (NoOpCache) SetPath(u, v string, segments []PathSegment, ttl time.Duration)

func (NoOpCache) Stats 

func (NoOpCache) Stats() CacheStats

type NoOpCircuitBreaker 

type NoOpCircuitBreaker struct{}

NoOpCircuitBreaker never opens the circuit. Used as default when no circuit breaker is configured.

func (NoOpCircuitBreaker) Execute 

func (NoOpCircuitBreaker) Execute(fn func() error) error

func (NoOpCircuitBreaker) State 

func (NoOpCircuitBreaker) State() CircuitState

func (NoOpCircuitBreaker) Stats 

func (NoOpCircuitBreaker) Stats() CircuitBreakerStats

type NoOpRateLimiter 

type NoOpRateLimiter struct{}

NoOpRateLimiter always allows all queries. Used as default when no rate limiting is configured.

func (NoOpRateLimiter) Allow 

func (NoOpRateLimiter) Allow() bool

func (NoOpRateLimiter) Stats 

func (NoOpRateLimiter) Stats() RateLimiterStats

func (NoOpRateLimiter) Wait 

func (NoOpRateLimiter) Wait(ctx context.Context) error

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 NodeDiff 

type NodeDiff struct {
	// NodeID is the unique node identifier.
	NodeID string `json:"node_id"`

	// SymbolName is the human-readable name of the symbol.
	SymbolName string `json:"symbol_name"`

	// ChangeType describes what changed: "signature_changed", "moved", "edges_changed".
	ChangeType string `json:"change_type"`
}

NodeDiff describes how a single node changed between snapshots.

type PackageInfo 

type PackageInfo struct {
	// Name is the package path (e.g., "services/trace/graph").
	Name string

	// Files lists file paths in this package.
	Files []string

	// NodeCount is the total number of symbols in this package.
	NodeCount int

	// ExportedCount is the number of exported (public) symbols.
	ExportedCount int

	// ImportCount is the number of packages this package imports.
	ImportCount int

	// ImportedByCount is the number of packages that import this package.
	ImportedByCount int

	// Types counts types (struct, interface, etc.) in the package.
	Types int

	// Functions counts functions and methods in the package.
	Functions int
}

PackageInfo contains metadata about a package in the graph.

type PageRankNode 

type PageRankNode struct {
	// Node is the graph node.
	Node *Node

	// Score is the PageRank score.
	Score float64

	// Rank is the position in the ranking (1-indexed).
	Rank int

	// DegreeScore is the simple degree-based score for comparison.
	// Computed as: inDegree*2 + outDegree
	DegreeScore int
}

PageRankNode represents a node with its PageRank score and rank.

type PageRankOptions 

type PageRankOptions struct {
	// DampingFactor is the probability of following a link (vs random jump).
	// Must be in [0, 1]. Default: 0.85
	DampingFactor float64

	// MaxIterations is the maximum iterations before stopping.
	// Must be > 0. Default: 100
	MaxIterations int

	// Convergence is the threshold for convergence detection.
	// Must be > 0. Default: 1e-6
	Convergence float64
}

PageRankOptions configures the PageRank algorithm.

func DefaultPageRankOptions 

func DefaultPageRankOptions() *PageRankOptions

DefaultPageRankOptions returns sensible defaults.

func (*PageRankOptions) Validate 

func (o *PageRankOptions) Validate()

Validate checks options and applies defaults for invalid values.

type PageRankResult 

type PageRankResult struct {
	// Scores maps nodeID to PageRank score.
	// Scores sum to approximately 1.0.
	Scores map[string]float64

	// Iterations is the actual number of iterations performed.
	Iterations int

	// Converged indicates whether the algorithm converged before MaxIterations.
	Converged bool

	// MaxDiff is the final maximum score difference (useful for debugging).
	MaxDiff float64
}

PageRankResult contains the output of PageRank computation.

type PathQueryEngine 

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

PathQueryEngine combines HLD and Segment Tree for efficient path aggregate queries.

Description: 

Provides O(log² V) path aggregate queries by decomposing paths into
O(log V) heavy path segments and querying each segment with a segment tree.
Supports SUM, MIN, MAX, GCD aggregations over node values.

Invariants:

  • Exactly one of hld or forest must be non-nil
  • HLD and SegmentTree must be built from same graph
  • Node indices must align between HLD positions and segment tree array
  • SegmentTree aggregation function must match query type
  • In forest mode, path queries only valid within single tree component

Thread Safety: 

Safe for concurrent queries (read-only operations).
Stats are tracked with atomic operations.

func NewPathQueryEngine 

func NewPathQueryEngine(hld *HLDecomposition, segTree *SegmentTree, aggFunc AggregateFunc, opts *PathQueryEngineOptions) (*PathQueryEngine, error)

NewPathQueryEngine creates a path query engine for single-tree graphs.

Description: 

Combines HLD and segment tree to enable efficient path queries.
The segment tree must be built over node values in HLD position order.

Algorithm: 

Time:  O(1) - just validates and stores references
Space: O(C) where C is total cache capacity

Inputs:

  • hld: Heavy-Light Decomposition. Must not be nil.
  • segTree: Segment tree over node values. Must not be nil.
  • aggFunc: Aggregation function. Must match segTree's aggregation.
  • opts: Configuration options. If nil, uses defaults.

Outputs:

  • *PathQueryEngine: Ready for queries. Never nil on success.
  • error: Non-nil if inputs are invalid.

Example: 

// Build value array in HLD position order
values := make([]int64, hld.NodeCount())
for i := 0; i < hld.NodeCount(); i++ {
    nodeID := hld.NodeAtPosition(i)
    values[i] = getNodeValue(nodeID)
}

// Build segment tree
segTree, _ := NewSegmentTree(ctx, values, AggregateSUM)

// Create query engine
opts := DefaultPathQueryEngineOptions()
engine, _ := NewPathQueryEngine(hld, segTree, AggregateSUM, &opts)

Limitations:

  • Only works with single-tree graphs (no forests)
  • Cannot change aggregation function after creation
  • Cache sizes fixed at creation time

Assumptions:

  • Values array used for segment tree corresponds to HLD position array
  • Graph structure unchanged since HLD construction (validated by graph hash)
  • All node values fit in int64

Thread Safety: The returned engine is safe for concurrent use.

func NewPathQueryEngineForForest 

func NewPathQueryEngineForForest(forest *HLDForest, segTree *SegmentTree, aggFunc AggregateFunc, opts *PathQueryEngineOptions) (*PathQueryEngine, error)

NewPathQueryEngineForForest creates a path query engine for multi-tree graphs (forests).

Description: 

Like NewPathQueryEngine but supports forests with multiple disconnected trees.
Path queries are only valid within a single tree component.

Inputs:

  • forest: HLD forest structure. Must not be nil.
  • segTree: Segment tree over all node values. Must not be nil.
  • aggFunc: Aggregation function. Must match segTree's aggregation.
  • opts: Configuration options. If nil, uses defaults.

Outputs:

  • *PathQueryEngine: Ready for queries. Never nil on success.
  • error: Non-nil if inputs are invalid.

Example: 

forest, _ := BuildHLDForest(ctx, graph)
values := buildValueArrayForForest(forest)
segTree, _ := NewSegmentTree(ctx, values, AggregateSUM)
engine, _ := NewPathQueryEngineForForest(forest, segTree, AggregateSUM, nil)

Limitations:

  • Path queries between nodes in different trees will return an error
  • Cannot query across tree boundaries even if graph has edges between components

Assumptions:

  • Forest and segment tree built from same graph
  • Values array corresponds to forest's unified position array

Thread Safety: The returned engine is safe for concurrent use.

func NewPathQueryEngineWithCRS 

func NewPathQueryEngineWithCRS(hld *HLDecomposition, segTree *SegmentTree, aggFunc AggregateFunc, opts *PathQueryEngineOptions, crsInstance crs.CRS, sessionID string) (*PathQueryEngine, error)

NewPathQueryEngineWithCRS creates a path query engine with optional CRS integration.

Description: 

Like NewPathQueryEngine but accepts optional CRS instance and session ID
for recording sub-steps (LCA computation, path decomposition).
If crsInstance is nil, CRS recording is disabled.

Inputs:

  • hld: HLD structure. Must not be nil.
  • segTree: Segment tree for range queries. Must not be nil.
  • aggFunc: Aggregation function (SUM/MIN/MAX/GCD). Must be valid constant.
  • opts: Configuration options. If nil, uses defaults.
  • crsInstance: Optional CRS for sub-step recording. Can be nil.
  • sessionID: CRS session ID. Ignored if crsInstance is nil.

Outputs:

  • *PathQueryEngine: Configured engine ready for queries.
  • error: Non-nil if validation fails.

Limitations:

  • Single-tree graphs only (use NewPathQueryEngineForForest for forests)
  • CRS recording adds ~0.1-0.5ms overhead per query

Assumptions:

  • hld and segTree are compatible (same node count, same agg func)
  • Caller validates crsInstance is not nil if sessionID is provided

Thread Safety: The returned engine is safe for concurrent use.

func (*PathQueryEngine) PathGCD 

func (pqe *PathQueryEngine) PathGCD(ctx context.Context, u, v string, logger *slog.Logger) (int64, error)

PathGCD computes GCD of values on path from u to v.

Description: 

Convenience wrapper for PathQuery with GCD aggregation.
Requires engine to be configured with AggregateGCD.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.
  • logger: Logger for structured logging. Must not be nil.

Outputs:

  • int64: GCD of values along path u → v.
  • error: Non-nil if engine not configured for GCD or PathQuery fails.

Example: 

gcdVersion, err := engine.PathGCD(ctx, "main", "leaf", logger)

Limitations:

  • Engine must be created with AggregateGCD
  • Nodes must be in same tree (forest mode)
  • GCD undefined for paths with zero values

Assumptions:

  • Caller has validated engine configuration
  • Node IDs are valid and exist in graph
  • All values on path are non-negative

Thread Safety: Safe for concurrent use.

func (*PathQueryEngine) PathMax 

func (pqe *PathQueryEngine) PathMax(ctx context.Context, u, v string, logger *slog.Logger) (int64, error)

PathMax computes maximum value on path from u to v.

Description: 

Convenience wrapper for PathQuery with MAX aggregation.
Requires engine to be configured with AggregateMAX.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.
  • logger: Logger for structured logging. Must not be nil.

Outputs:

  • int64: Maximum value along path u → v.
  • error: Non-nil if engine not configured for MAX or PathQuery fails.

Example: 

maxLatency, err := engine.PathMax(ctx, "main", "leaf", logger)

Limitations:

  • Engine must be created with AggregateMAX
  • Nodes must be in same tree (forest mode)

Assumptions:

  • Caller has validated engine configuration
  • Node IDs are valid and exist in graph

Thread Safety: Safe for concurrent use.

func (*PathQueryEngine) PathMin 

func (pqe *PathQueryEngine) PathMin(ctx context.Context, u, v string, logger *slog.Logger) (int64, error)

PathMin computes minimum value on path from u to v.

Description: 

Convenience wrapper for PathQuery with MIN aggregation.
Requires engine to be configured with AggregateMIN.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.
  • logger: Logger for structured logging. Must not be nil.

Outputs:

  • int64: Minimum value along path u → v.
  • error: Non-nil if engine not configured for MIN or PathQuery fails.

Example: 

minMemory, err := engine.PathMin(ctx, "main", "leaf", logger)

Limitations:

  • Engine must be created with AggregateMIN
  • Nodes must be in same tree (forest mode)

Assumptions:

  • Caller has validated engine configuration
  • Node IDs are valid and exist in graph

Thread Safety: Safe for concurrent use.

func (*PathQueryEngine) PathQuery 

func (pqe *PathQueryEngine) PathQuery(ctx context.Context, u, v string, logger *slog.Logger) (int64, error)

PathQuery computes aggregate over path from u to v.

Description: 

Decomposes path into heavy path segments, queries each segment with
segment tree, and combines results using aggregation function.
Handles LCA double-counting for SUM (but not MIN/MAX - idempotent).

Algorithm: 

Time:  O(log² V) = O(log V) segments × O(log V) per query
Space: O(log V) - store segment query results

Inputs:

  • ctx: Context for cancellation and timeout. Must not be nil.
  • u: Start node ID. Must exist in graph and not be empty.
  • v: End node ID. Must exist in graph and not be empty.
  • logger: Structured logger for events. Must not be nil.

Outputs:

  • int64: Aggregate value over path u → v.
  • error: Non-nil if nodes don't exist, cross-tree in forest, or query fails.

Special Cases:

  • PathQuery(u, u) = value[u]
  • PathQuery(u, parent[u]) = aggFunc(value[u], value[parent[u]])

Example: 

sum, err := engine.PathQuery(ctx, "main", "helper", logger)
if err != nil {
    return fmt.Errorf("path query: %w", err)
}
fmt.Printf("Total complexity on path: %d\n", sum)

Limitations:

  • Only works within single tree component (error for cross-tree in forest)
  • Requires graph unchanged since HLD construction (checked via graph hash)
  • Maximum depth limited by opts.MaxTreeDepth

Assumptions:

  • Segment tree values correspond to HLD position array
  • Node values fit in int64
  • Caller has validated graph hasn't changed

Thread Safety: Safe for concurrent use.

func (*PathQueryEngine) PathQueryCacheKey 

func (pqe *PathQueryEngine) PathQueryCacheKey(u, v string) string

PathQueryCacheKey generates deterministic cache key for path query.

Description: 

H2: Includes graph hash to ensure cache invalidation on graph changes.
Canonical ordering for symmetric aggregations (MIN/MAX).
Uses strings.Builder for efficient string concatenation.

Inputs:

  • u: Start node ID. Must not be empty.
  • v: End node ID. Must not be empty.

Outputs:

  • string: Cache key in format "pathquery:{graphHash}:{u}:{v}:{aggFunc}"

Limitations:

  • Keys are unique per (graph, u, v, aggFunc) tuple
  • MIN/MAX queries use canonical ordering (smaller node first)

Assumptions:

  • Graph hash is stable for same graph structure
  • Node IDs don't contain ':' character

Thread Safety: Safe for concurrent use (read-only).

func (*PathQueryEngine) PathSum 

func (pqe *PathQueryEngine) PathSum(ctx context.Context, u, v string, logger *slog.Logger) (int64, error)

PathSum computes sum of values on path from u to v.

Description: 

Convenience wrapper for PathQuery with SUM aggregation.
Requires engine to be configured with AggregateSUM.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.
  • logger: Logger for structured logging. Must not be nil.

Outputs:

  • int64: Sum of values along path u → v.
  • error: Non-nil if engine not configured for SUM or PathQuery fails.

Example: 

totalComplexity, err := engine.PathSum(ctx, "main", "leaf", logger)

Limitations:

  • Engine must be created with AggregateSUM
  • Nodes must be in same tree (forest mode)

Assumptions:

  • Caller has validated engine configuration
  • Node IDs are valid and exist in graph

Thread Safety: Safe for concurrent use.

func (*PathQueryEngine) Stats 

func (pqe *PathQueryEngine) Stats() PathQueryStats

Stats returns query statistics.

Description: 

C2: Thread-safe stats retrieval using atomic operations.
Returns snapshot of current statistics.
M-IMPL-2: Includes SegmentsPerQuery average.

Inputs:

  • None

Outputs:

  • PathQueryStats: Snapshot of statistics including query count, latency, cache hit ratio, segments per query

Limitations:

  • Snapshot may be stale immediately after return
  • SegmentsPerQuery excludes cache hits (counted as 0 segments)
  • CacheHitRatio includes both LCA cache and query cache

Assumptions:

  • Atomic loads provide consistent point-in-time snapshot
  • QueryCount > 0 when calculating averages

Thread Safety: Safe for concurrent use (atomic reads).

func (*PathQueryEngine) Validate 

func (pqe *PathQueryEngine) Validate() error

Validate checks that HLD and SegmentTree are compatible and valid.

Description: 

Verifies:
- HLD or Forest is valid
- SegmentTree is valid
- Size compatibility
- Aggregation function consistency
L-IMPL-2: Creates OpenTelemetry span to track validation.

Inputs:

  • None (validates internal state)

Outputs:

  • error: Non-nil if validation fails with detailed error message

Limitations:

  • Only checks structural validity, not semantic correctness
  • Does not validate node values or tree structure

Assumptions:

  • Engine fields are immutable after construction
  • HLD and SegmentTree built from same graph

Thread Safety: Safe for concurrent use (read-only).

type PathQueryEngineOptions 

type PathQueryEngineOptions struct {
	// EnableLCACache enables caching of LCA results.
	// Default: true
	EnableLCACache bool

	// LCACacheSize sets maximum number of LCA results to cache.
	// Default: 10000
	LCACacheSize int

	// EnableQueryCache enables caching of full path query results.
	// Default: false (disabled by default as results may be large)
	EnableQueryCache bool

	// QueryCacheSize sets maximum number of query results to cache.
	// Default: 1000
	QueryCacheSize int

	// QueryTimeout sets maximum time allowed for a single path query.
	// Default: 30 seconds
	QueryTimeout time.Duration

	// MaxTreeDepth sets maximum allowed tree depth to prevent OOM.
	// Default: 10000
	MaxTreeDepth int

	// SlowQueryThreshold defines the duration threshold for slow query warnings.
	// Queries exceeding this threshold will emit a warning log.
	// Default: 5 seconds
	SlowQueryThreshold time.Duration
}

PathQueryEngineOptions configures path query engine behavior.

Description: 

Controls caching, timeouts, and resource limits for path query operations.
All fields are optional with sensible defaults.

Thread Safety: Immutable after creation, safe to share across goroutines.

func DefaultPathQueryEngineOptions 

func DefaultPathQueryEngineOptions() PathQueryEngineOptions

DefaultPathQueryEngineOptions returns default options.

type PathQueryStats 

type PathQueryStats struct {
	QueryCount       int64         // Total queries
	TotalLatency     time.Duration // Sum of all query durations
	AvgLatency       time.Duration // Average query duration
	LastQueryTime    int64         // Unix milliseconds UTC of last query
	SegmentsPerQuery float64       // Average segments per query (requires tracking)
	CacheHitRatio    float64       // Ratio of cache hits to total lookups
}

PathQueryStats contains query statistics.

Description: 

Statistics collected across all queries on this engine.
All timestamps in Unix milliseconds UTC per CLAUDE.md Section 4.6.

Thread Safety: Snapshot at time of Stats() call, may be stale.

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 PathSegment 

type PathSegment struct {
	Start    int  // Start position (inclusive)
	End      int  // End position (inclusive)
	IsUpward bool // True if this segment goes upward (child to parent)
}

PathSegment represents a contiguous segment of a path in HLD position space.

Description: 

A path segment covers positions [Start, End] (inclusive) in the HLD
position array. The segment corresponds to a portion of a heavy path.
All positions in the segment are guaranteed to be on the same heavy path.

Invariants:

  • Start >= 0 and End >= 0
  • Start, End in [0, nodeCount)
  • All positions in [Start, End] are on same heavy path
  • IsUpward indicates direction: true = child→parent, false = parent→child

Usage: 

Used as input to segment tree range queries. For path query(u, v),
decompose into O(log V) PathSegments, query each with segment tree.

Thread Safety: Immutable after creation, safe for concurrent use.

type PathUpdateEngine 

type PathUpdateEngine struct {
	*PathQueryEngine // Embed for CRS fields (H-CRS-1)
	// contains filtered or unexported fields
}

PathUpdateEngine provides path update operations using HLD and segment tree.

Description: 

Extends PathQueryEngine with update operations. Updates values along
paths by decomposing into O(log V) segments and applying range updates
with lazy propagation for O(log² V) total time.
Supports forest mode - updates only within single tree component.

Invariants:

  • Segment tree must support range updates (RangeUpdate method)
  • Only works with SUM aggregation (GR-19b restriction)
  • Updates invalidate query cache for correctness
  • In forest mode, path updates only valid within single tree component
  • Segment tree version increments on each update

Thread Safety: 

NOT safe for concurrent updates (PathUpdate, PathSet, etc.).
NOT safe for concurrent update+query (segment tree Query takes write lock for lazy push).
Safe for concurrent queries only (no updates in progress).
Caller MUST use external synchronization (e.g., sync.RWMutex):
  - Lock.RLock() for queries
  - Lock.Lock() for updates

func NewPathUpdateEngine 

func NewPathUpdateEngine(pqe *PathQueryEngine) (*PathUpdateEngine, error)

NewPathUpdateEngine creates a path update engine.

Description: 

Wraps PathQueryEngine to add update capabilities.
Requires segment tree to support RangeUpdate (SUM aggregation only).
Validates aggregation function at construction time.

Algorithm: 

Time:  O(1) - wraps existing engine
Space: O(1) - no allocations

Inputs:

  • pqe: Path query engine. Must not be nil.

Outputs:

  • *PathUpdateEngine: Ready for updates. Never nil on success.
  • error: Non-nil if query engine is nil, invalid, or not configured for SUM.

Example: 

// Build value array in HLD position order
values := make([]int64, hld.NodeCount())
for i := 0; i < hld.NodeCount(); i++ {
    nodeID := hld.NodeAtPosition(i)
    values[i] = getNodeValue(nodeID)
}

// Build segment tree with SUM aggregation
segTree, _ := NewSegmentTree(ctx, values, AggregateSUM)

// Create query engine
queryEngine, _ := NewPathQueryEngine(hld, segTree, AggregateSUM, nil)

// Create update engine
updateEngine, _ := NewPathUpdateEngine(queryEngine)

Limitations:

  • Only works with SUM aggregation (GR-19b RangeUpdate restriction)
  • MIN/MAX/GCD engines cannot be used for updates
  • Constructor validates aggregation function and returns error if not SUM

Assumptions:

  • Query engine's segment tree was built with SUM aggregation
  • Caller has validated compatibility between HLD and segment tree

Thread Safety: Safe for concurrent use (wraps read-only engine).

func (*PathUpdateEngine) PathDecrement 

func (pue *PathUpdateEngine) PathDecrement(ctx context.Context, u, v string, logger *slog.Logger) error

PathDecrement decrements all values on path (delta=-1).

Description: 

Convenience wrapper for PathUpdate with delta=-1.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.
  • logger: Structured logger for events. Must not be nil.

Outputs:

  • error: Non-nil if update fails.

Thread Safety: NOT safe for concurrent use.

func (*PathUpdateEngine) PathIncrement 

func (pue *PathUpdateEngine) PathIncrement(ctx context.Context, u, v string, logger *slog.Logger) error

PathIncrement increments all values on path (delta=+1).

Description: 

Convenience wrapper for PathUpdate with delta=+1.

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.
  • logger: Structured logger for events. Must not be nil.

Outputs:

  • error: Non-nil if update fails.

Thread Safety: NOT safe for concurrent use.

func (*PathUpdateEngine) PathSet 

func (pue *PathUpdateEngine) PathSet(ctx context.Context, u, v string, value int64, logger *slog.Logger) error

PathSet sets all node values on path from u to v to a specific value.

Description: 

Sets each node on path to value. Implemented by computing current
aggregate and calculating delta needed to achieve target value.
Less efficient than PathUpdate (requires querying current values).

Algorithm: 

Time:  O(log² V) query + O(log² V) update = O(log² V)
Space: O(log V)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph.
  • v: End node ID. Must exist in graph.
  • value: New value for all nodes on path.
  • logger: Structured logger for events. Must not be nil.

Outputs:

  • error: Non-nil if operation fails.

Example: 

// Set all complexity values on path to 10
err := engine.PathSet(ctx, "main", "leaf", 10, logger)

Limitations:

  • Requires two passes: query current aggregate, then update
  • Only works with SUM aggregation
  • NOT safe for concurrent updates

Assumptions:

  • Path exists and nodes are in same tree component
  • Current values fit in int64

Thread Safety: NOT safe for concurrent use.

func (*PathUpdateEngine) PathUpdate 

func (pue *PathUpdateEngine) PathUpdate(ctx context.Context, u, v string, delta int64, logger *slog.Logger) error

PathUpdate adds delta to all node values on path from u to v.

Description: 

Decomposes path into heavy path segments and applies range update
to each segment. Handles LCA correctly (DecomposePath already excludes
from second path). Uses lazy propagation for efficiency.
Invalidates query cache after update for correctness.

Algorithm: 

Time:  O(log² V) = O(log V) segments × O(log V) per range update
Space: O(log V) - segment decomposition

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • u: Start node ID. Must exist in graph and not be empty.
  • v: End node ID. Must exist in graph and not be empty.
  • delta: Value to add to each node on path.
  • logger: Structured logger for events. Must not be nil.

Outputs:

  • error: Non-nil if nodes don't exist, cross-tree in forest, or update fails.

Special Cases:

  • PathUpdate(u, u, delta): Updates single node
  • PathUpdate(u, parent[u], delta): Updates two nodes
  • delta == 0: No-op fast path, still recorded in CRS

Example: 

// Add 5 to complexity along call path
err := engine.PathUpdate(ctx, "main", "leaf", 5, logger)
if err != nil {
    return fmt.Errorf("path update: %w", err)
}

CRS Integration: 

Records update as StepRecord with node IDs, delta, segments updated.
Sub-steps recorded for each segment update.

Limitations:

  • Only works within single tree component (error for cross-tree in forest mode)
  • Requires SUM aggregation (MIN/MAX/GCD not supported for updates - GR-19b restriction)
  • Query cache invalidated on EVERY update via Purge() - entire cache discarded (O(cache_size) cost) This impacts mixed read-heavy workloads: after ANY update, all cached queries must be recomputed For update-heavy workloads, consider disabling query cache to avoid purge overhead
  • NOT safe for concurrent updates (caller must synchronize with external lock)
  • Segment tree version incremented (may invalidate external references)

Assumptions:

  • Segment tree values correspond to HLD position array
  • Node values fit in int64
  • Caller has validated graph hasn't changed since construction

Thread Safety: NOT safe for concurrent use. Caller must synchronize.

func (*PathUpdateEngine) Stats 

func (pue *PathUpdateEngine) Stats() PathUpdateStats

Stats returns update statistics.

Description: 

Thread-safe stats retrieval using atomic operations.
Returns snapshot of current statistics.
Includes average segments per update.

Inputs:

  • None

Outputs:

  • PathUpdateStats: Snapshot of statistics including update count, latency, segments per update

Limitations:

  • Snapshot may be stale immediately after return
  • AvgSegmentsPerUpdate excludes no-op updates (counted as 0 segments)

Assumptions:

  • Atomic loads provide consistent point-in-time snapshot
  • UpdateCount > 0 when calculating averages

Thread Safety: Safe for concurrent use (atomic reads).

type PathUpdateStats 

type PathUpdateStats struct {
	UpdateCount          int64         // Total updates
	TotalUpdateLatency   time.Duration // Sum of all update durations
	AvgUpdateLatency     time.Duration // Average update duration
	SegmentsUpdated      int64         // Total segments updated across all operations
	AvgSegmentsPerUpdate float64       // Average segments per update
}

PathUpdateStats contains update statistics.

Description: 

Statistics collected across all updates on this engine.

Thread Safety: Snapshot at time of Stats() call, may be stale.

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

	// ProgressPhaseLSPEnrichment indicates LSP enrichment is resolving placeholders.
	// GR-74: Inserted between edge extraction and finalization.
	ProgressPhaseLSPEnrichment

	// 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 QueryCacheStats 

type QueryCacheStats struct {
	// CallersHits is the number of callers cache hits.
	CallersHits int64 `json:"callers_hits"`
	// CallersMisses is the number of callers cache misses.
	CallersMisses int64 `json:"callers_misses"`
	// CallersEvictions is the number of callers cache evictions.
	CallersEvictions int64 `json:"callers_evictions"`
	// CallersSize is the current number of entries in the callers cache.
	CallersSize int `json:"callers_size"`

	// CalleesHits is the number of callees cache hits.
	CalleesHits int64 `json:"callees_hits"`
	// CalleesMisses is the number of callees cache misses.
	CalleesMisses int64 `json:"callees_misses"`
	// CalleesEvictions is the number of callees cache evictions.
	CalleesEvictions int64 `json:"callees_evictions"`
	// CalleesSize is the current number of entries in the callees cache.
	CalleesSize int `json:"callees_size"`

	// PathsHits is the number of paths cache hits.
	PathsHits int64 `json:"paths_hits"`
	// PathsMisses is the number of paths cache misses.
	PathsMisses int64 `json:"paths_misses"`
	// PathsEvictions is the number of paths cache evictions.
	PathsEvictions int64 `json:"paths_evictions"`
	// PathsSize is the current number of entries in the paths cache.
	PathsSize int `json:"paths_size"`

	// TotalHits is the sum of all cache hits.
	TotalHits int64 `json:"total_hits"`
	// TotalMisses is the sum of all cache misses.
	TotalMisses int64 `json:"total_misses"`
	// TotalEvictions is the sum of all cache evictions.
	TotalEvictions int64 `json:"total_evictions"`
	// HitRate is the cache hit rate (0.0 to 1.0). Zero if no queries.
	HitRate float64 `json:"hit_rate"`
}

QueryCacheStats contains statistics for query caches.

Description: 

Provides visibility into query cache performance for monitoring and
debugging. All counts are since cache creation or last Purge.

Thread Safety: Fields are atomic snapshots, safe for concurrent use.

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 RateLimiter 

type RateLimiter interface {
	// Allow returns true if the query is allowed, false if rate limited.
	Allow() bool

	// Wait blocks until a query is allowed or context is canceled.
	Wait(ctx context.Context) error

	// Stats returns rate limiter statistics.
	Stats() RateLimiterStats
}

RateLimiter controls query rate to prevent DoS.

Description: 

Implements rate limiting using token bucket, leaky bucket, or
similar algorithms. Protects against query flooding.

Thread Safety: All methods must be safe for concurrent use.

type RateLimiterStats 

type RateLimiterStats struct {
	Allowed  int64   // Total requests allowed
	Rejected int64   // Total requests rejected
	QPS      float64 // Current queries per second
}

RateLimiterStats contains rate limiting metrics.

type ReducibilityResult 

type ReducibilityResult struct {
	// IsReducible is true if the entire graph is reducible.
	IsReducible bool

	// Score is the percentage of nodes NOT in irreducible regions.
	// Range: 0.0 to 1.0, where 1.0 means fully reducible.
	// Rounded to 4 decimal places for consistency.
	Score float64

	// IrreducibleRegions contains detected irreducible subgraphs.
	IrreducibleRegions []*IrreducibleRegion

	// Summary contains aggregate statistics.
	Summary ReducibilitySummary

	// Recommendation provides actionable guidance.
	Recommendation string

	// DomTree is the dominator tree used for analysis.
	DomTree *DominatorTree

	// NodeCount is total nodes analyzed.
	NodeCount int

	// EdgeCount is total edges analyzed.
	EdgeCount int

	// CrossEdgeCount is the number of cross edges found.
	CrossEdgeCount int
}

ReducibilityResult contains the reducibility analysis output.

A graph is reducible if all back edges go to dominators (natural loops only). Irreducible graphs have cross edges that create multi-entry regions.

Thread Safety: Safe for concurrent use after construction.

type ReducibilitySummary 

type ReducibilitySummary struct {
	TotalNodes             int
	IrreducibleNodeCount   int
	IrreducibleRegionCount int
	WellStructuredPercent  float64
}

ReducibilitySummary contains aggregate statistics.

type RefreshConfig 

type RefreshConfig struct {
	// MaxFilesToRefresh limits incremental refresh size.
	// If exceeded, returns error suggesting full rebuild.
	// Default: 50
	MaxFilesToRefresh int

	// ParallelParsing enables concurrent file parsing.
	// Default: true
	ParallelParsing bool

	// ParallelWorkers is the number of parallel parse workers.
	// Default: 4
	ParallelWorkers int

	// Timeout is the maximum time for a refresh operation.
	// Default: 30s
	Timeout time.Duration
}

RefreshConfig configures refresh behavior.

func DefaultRefreshConfig 

func DefaultRefreshConfig() RefreshConfig

DefaultRefreshConfig returns sensible defaults.

type RefreshResult 

type RefreshResult struct {
	// FilesRefreshed is the number of files processed.
	FilesRefreshed int

	// NodesRemoved is the count of nodes removed from old files.
	NodesRemoved int

	// NodesAdded is the count of nodes added from new parses.
	NodesAdded int

	// Duration is how long the refresh took.
	Duration time.Duration

	// ParseErrors contains errors for files that failed to parse.
	ParseErrors []FileParseError
}

RefreshResult contains statistics about an incremental refresh.

type Refresher 

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

Refresher handles incremental graph updates.

Description: 

Provides incremental refresh capability for the code graph.
When files are modified by agent tools, the Refresher can
update only the affected portions of the graph without
requiring a full rebuild.

Thread Safety: 

The Refresher is safe for concurrent use. During refresh,
a clone of the graph is modified, then atomically swapped.

func NewRefresher 

func NewRefresher(graph **Graph, parsers *ast.ParserRegistry, opts ...RefresherOption) *Refresher

NewRefresher creates a new Refresher.

Description: 

Creates a refresher bound to a graph pointer. The graph pointer
can be swapped atomically during refresh operations.

Inputs: 

graph - Pointer to the graph pointer (allows atomic swap).
parsers - Parser registry for re-parsing files.
opts - Optional configuration.

Outputs: 

*Refresher - The configured refresher.

func (*Refresher) GetGraph 

func (r *Refresher) GetGraph() *Graph

GetGraph returns the current graph.

Thread Safety: 

Safe for concurrent use.

func (*Refresher) RefreshFiles 

func (r *Refresher) RefreshFiles(ctx context.Context, paths []string) (*RefreshResult, error)

RefreshFiles incrementally updates the graph for modified files.

Description: 

Re-parses only the specified files and updates graph nodes.
Uses a copy-on-write pattern: clones the graph, modifies the
clone, then atomically swaps if successful.

Inputs: 

ctx - Context for cancellation and timeout.
paths - Files to refresh (absolute paths).

Outputs: 

*RefreshResult - Statistics about the refresh.
error - Non-nil if refresh failed completely.

Errors: 

Returns error if:
  - Too many files (exceeds MaxFilesToRefresh)
  - Context cancelled or timed out
  - Graph is nil

Thread Safety: 

Safe for concurrent use. Uses copy-on-write to avoid
blocking readers during refresh.

func (*Refresher) SetGraph 

func (r *Refresher) SetGraph(g *Graph)

SetGraph replaces the current graph.

Description: 

Used to set a new graph, for example after a full rebuild.

Thread Safety: 

Safe for concurrent use.

type RefresherOption 

type RefresherOption func(*Refresher)

RefresherOption configures a Refresher.

func WithRefresherConfig 

func WithRefresherConfig(config RefreshConfig) RefresherOption

WithRefresherConfig sets the refresh configuration.

func WithRefresherLogger 

func WithRefresherLogger(logger *slog.Logger) RefresherOption

WithRefresherLogger sets the logger.

type SESEError 

type SESEError struct {
	Message string
}

SESEError represents an error in SESE region detection.

func (*SESEError) Error 

func (e *SESEError) Error() string

type SESERegion 

type SESERegion struct {
	// Entry is the single entry node ID.
	Entry string

	// Exit is the single exit node ID.
	Exit string

	// Nodes contains all node IDs in the region (including entry/exit).
	Nodes []string

	// Size is the node count (len(Nodes)).
	Size int

	// Parent is the enclosing region (nil if top-level).
	Parent *SESERegion

	// Children are nested regions within this region.
	Children []*SESERegion

	// Depth is the nesting depth (0 = top-level).
	Depth int
}

SESERegion represents a single-entry single-exit region.

A SESE region has exactly one entry and one exit node where:

  • All paths into the region go through entry
  • All paths out of the region go through exit
  • Entry dominates all nodes in the region
  • Exit post-dominates all nodes in the region

Thread Safety: Safe for concurrent use after construction.

type SESEResult 

type SESEResult struct {
	// Regions contains all SESE regions found.
	Regions []*SESERegion

	// TopLevel contains regions with no parent (depth 0).
	TopLevel []*SESERegion

	// RegionOf maps node ID → innermost containing region.
	RegionOf map[string]*SESERegion

	// MaxDepth is the maximum nesting depth found.
	MaxDepth int

	// Extractable contains regions suitable for extraction.
	// Populated by FilterExtractable().
	Extractable []*SESERegion

	// NodeCount is the total nodes analyzed.
	NodeCount int

	// RegionCount is the total regions found.
	RegionCount int
}

SESEResult contains all detected SESE regions.

Thread Safety: Safe for concurrent use after construction.

func (*SESEResult) FilterExtractable 

func (r *SESEResult) FilterExtractable(minSize, maxSize int) []*SESERegion

FilterExtractable returns regions suitable for extraction based on size.

Description: 

Filters regions by node count. Regions that are too small may not be
worth extracting, while regions that are too large should be split further.

Inputs:

  • minSize: Minimum nodes in region (inclusive). Use 1 to include all.
  • maxSize: Maximum nodes in region (inclusive). Use a large value for no limit.

Outputs:

  • []*SESERegion: Regions within the size range. Never nil.

Example: 

// Find regions with 3-50 nodes (good candidates for extraction)
extractable := result.FilterExtractable(3, 50)

Thread Safety: Safe for concurrent use.

type SegmentTree 

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

SegmentTree provides efficient range queries and updates over an array.

Description: 

A segment tree supporting O(log N) range queries and updates for
associative aggregation functions (sum, min, max, gcd). Supports
lazy propagation for efficient range updates (SUM only).

Invariants:

  • Tree array has size 2*paddedSize where paddedSize is next power of 2
  • tree[i] represents aggregate over range [L, R]
  • Parent(i) = i/2, LeftChild(i) = 2*i, RightChild(i) = 2*i+1
  • lazy[i] stores pending updates for node i's children (SUM only)
  • After build, tree[1] = aggregate over entire array
  • version increments on each Update/RangeUpdate

Thread Safety:

  • All operations are protected by RWMutex
  • Query operations acquire read lock (thread-safe for concurrent reads)
  • Update operations acquire write lock (not safe for concurrent updates)
  • Lazy propagation during Query requires write lock on affected nodes

func NewSegmentTree 

func NewSegmentTree(ctx context.Context, arr []int64, aggFunc AggregateFunc) (*SegmentTree, error)

NewSegmentTree creates a segment tree from an array of values.

Description: 

Constructs a segment tree supporting range queries/updates over arr.
Uses bottom-up construction for O(N) build time. Pads array to next
power of 2 for proper tree structure.

Algorithm: 

Time:  O(N) where N = len(arr)
Space: O(N) - tree array size 2*paddedSize

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • arr: Initial array values. Must not be empty.
  • aggFunc: Aggregation function (SUM, MIN, MAX, GCD).

Outputs:

  • *SegmentTree: Constructed segment tree. Never nil on success.
  • error: Non-nil if arr is empty, too large, or aggFunc is invalid.

Optimizations:

  • Single allocation for tree and lazy arrays
  • Bottom-up construction (iterative, not recursive)
  • Pre-computed power-of-2 padding
  • Context cancellation checked periodically

CRS Integration:

  • Records construction timing and metadata
  • Deterministic output for caching

Example: 

arr := []int64{3, 1, 4, 2, 5, 7, 6, 8}
tree, err := NewSegmentTree(ctx, arr, AggregateSUM)
if err != nil {
    return fmt.Errorf("build segment tree: %w", err)
}
sum, _ := tree.Query(ctx, 2, 5)  // Range [2,5] sum = 18

Thread Safety: Safe for concurrent use with different arrays.

func (*SegmentTree) CacheKey 

func (st *SegmentTree) CacheKey() string

CacheKey generates a cache key for this segment tree.

Description: 

Returns a deterministic cache key based on tree structure and version.
Includes version to handle updates properly.

Thread Safety: Safe for concurrent use (read-only, protected by RWMutex).

func (*SegmentTree) GetValue 

func (st *SegmentTree) GetValue(ctx context.Context, index int) (int64, error)

GetValue retrieves the current value at arr[index].

Description: 

Returns the current value at index, accounting for lazy updates.
Equivalent to Query(ctx, index, index) but more explicit.

Algorithm: 

Time:  O(log N) - must push down lazy updates
Space: O(1)

Thread Safety: Safe for concurrent reads (protected by RWMutex).

func (*SegmentTree) MemoryUsage 

func (st *SegmentTree) MemoryUsage() int

MemoryUsage estimates memory usage in bytes.

func (*SegmentTree) Query 

func (st *SegmentTree) Query(ctx context.Context, left, right int) (int64, error)

Query computes the aggregate over range [left, right] (inclusive).

Description: 

Queries the segment tree for the aggregate value over [left, right].
Automatically pushes down lazy updates before reading nodes.

Algorithm: 

Time:  O(log N) where N = size of array
Space: O(1) - iterative implementation

Inputs:

  • ctx: Context for tracing.
  • left: Left boundary (0-indexed, inclusive). Must be in [0, size).
  • right: Right boundary (0-indexed, inclusive). Must be in [left, size).

Outputs:

  • int64: Aggregate value over [left, right].
  • error: Non-nil if range is invalid.

Example: 

sum, err := tree.Query(ctx, 2, 5)  // Sum of arr[2..5]

Thread Safety: Safe for concurrent reads (protected by RWMutex).

func (*SegmentTree) RangeUpdate 

func (st *SegmentTree) RangeUpdate(ctx context.Context, left, right int, delta int64) error

RangeUpdate adds delta to all elements in [left, right].

Description: 

Efficiently updates a range using lazy propagation. Actual updates
are deferred until the nodes are queried or updated again.
CRITICAL: Only supports SUM aggregation (additive operation).

Algorithm: 

Time:  O(log N)
Space: O(1)

Inputs:

  • ctx: Context for tracing.
  • left: Left boundary (0-indexed, inclusive). Must be in [0, size).
  • right: Right boundary (0-indexed, inclusive). Must be in [left, size).
  • delta: Value to add to each element in range.

Outputs:

  • error: Non-nil if range is invalid or aggFunc is not SUM.

Example: 

err := tree.RangeUpdate(ctx, 0, 3, 5)  // Add 5 to arr[0..3]

Limitations:

  • Only supports additive updates (delta added to existing values)
  • Does not support set operations (use Update for single elements)
  • Only works with AggregateSUM (MIN/MAX are not additive)

Thread Safety: NOT safe for concurrent use. Caller must synchronize.

func (*SegmentTree) Stats 

func (st *SegmentTree) Stats() SegmentTreeStats

Stats returns statistics about the segment tree.

Thread Safety: Safe for concurrent use (read-only, protected by RWMutex).

func (*SegmentTree) Update 

func (st *SegmentTree) Update(ctx context.Context, index int, value int64) error

Update sets arr[index] = value and updates tree.

Description: 

Updates a single element and propagates change up to root.
Pushes down lazy updates on path from leaf to root.

Algorithm: 

Time:  O(log N)
Space: O(1)

Inputs:

  • ctx: Context for tracing.
  • index: Array index to update (0-indexed). Must be in [0, size).
  • value: New value for arr[index].

Outputs:

  • error: Non-nil if index is out of bounds.

Example: 

err := tree.Update(ctx, 3, 10)  // Set arr[3] = 10

Thread Safety: NOT safe for concurrent use. Caller must synchronize.

func (*SegmentTree) Validate 

func (st *SegmentTree) Validate() error

Validate checks segment tree invariants.

Description: 

Verifies:
- Tree and lazy arrays have correct size
- Root aggregate matches expected value
- Parent-child relationships are correct
- Lazy array consistency

Complexity: O(N) time

Thread Safety: Safe for concurrent use (read-only, protected by RWMutex).

type SegmentTreeStats 

type SegmentTreeStats struct {
	Size        int           // Number of leaves (original array size)
	PaddedSize  int           // Padded size (next power of 2)
	TreeSize    int           // Total tree array size
	Height      int           // Tree height (log2 of padded size)
	AggFunc     AggregateFunc // Aggregation function
	BuildTime   time.Duration // Construction time
	QueryCount  int64         // Queries performed
	UpdateCount int64         // Updates performed
	Version     int64         // Current version
	MemoryBytes int           // Approximate memory usage
}

SegmentTreeStats contains statistics about the segment tree.

type SerializableEdge 

type SerializableEdge struct {
	// FromID is the ID of the source node.
	FromID string `json:"from_id"`

	// ToID is the ID of the target node.
	ToID string `json:"to_id"`

	// Type is the human-readable edge type string (e.g., "calls", "imports").
	Type string `json:"type"`

	// TypeCode is the integer edge type for exact reconstruction.
	TypeCode EdgeType `json:"type_code"`

	// Location is where the relationship is expressed in code.
	Location ast.Location `json:"location"`
}

SerializableEdge is the JSON-serializable representation of an Edge.

type SerializableGraph 

type SerializableGraph struct {
	// SchemaVersion identifies the serialization format version.
	SchemaVersion string `json:"schema_version"`

	// ProjectRoot is the absolute path to the project root directory.
	ProjectRoot string `json:"project_root"`

	// BuiltAtMilli is the Unix timestamp in milliseconds when the graph was frozen.
	BuiltAtMilli int64 `json:"built_at_milli"`

	// GraphHash is the deterministic hash of the graph structure.
	GraphHash string `json:"graph_hash"`

	// Nodes contains all nodes in the graph, sorted by ID.
	Nodes []SerializableNode `json:"nodes"`

	// Edges contains all edges in the graph.
	Edges []SerializableEdge `json:"edges"`

	// FileMtimes records file modification times (Unix seconds) at build time.
	// CRS-19: Used for staleness detection across sessions.
	FileMtimes map[string]int64 `json:"file_mtimes,omitempty"`
}

SerializableGraph is the JSON-serializable representation of a Graph.

Description: 

Contains all data needed to reconstruct a Graph from JSON. Nodes are
sorted by ID for deterministic output, enabling reliable diffing and
content hashing.

Thread Safety: SerializableGraph is a value type with no internal state.

type SerializableNode 

type SerializableNode struct {
	// ID is the unique node identifier (same as Symbol.ID).
	ID string `json:"id"`

	// Symbol is the underlying AST symbol. ast.Symbol already has JSON tags.
	Symbol *ast.Symbol `json:"symbol"`
}

SerializableNode is the JSON-serializable representation of a Node.

type SnapshotDiff 

type SnapshotDiff struct {
	// BaseSnapshotID is the ID of the base snapshot.
	BaseSnapshotID string `json:"base_snapshot_id"`

	// TargetSnapshotID is the ID of the target snapshot.
	TargetSnapshotID string `json:"target_snapshot_id"`

	// NodesAdded are node IDs present in target but not in base.
	NodesAdded []string `json:"nodes_added"`

	// NodesRemoved are node IDs present in base but not in target.
	NodesRemoved []string `json:"nodes_removed"`

	// NodesModified are nodes that changed between snapshots.
	NodesModified []NodeDiff `json:"nodes_modified"`

	// EdgesAdded is the count of edges in target but not in base.
	EdgesAdded int `json:"edges_added"`

	// EdgesRemoved is the count of edges in base but not in target.
	EdgesRemoved int `json:"edges_removed"`

	// Summary contains aggregate statistics about the diff.
	Summary DiffSummary `json:"summary"`
}

SnapshotDiff contains the differences between two graph snapshots.

func DiffSnapshots 

func DiffSnapshots(base, target *Graph, baseSnapshotID, targetSnapshotID string) (*SnapshotDiff, error)

DiffSnapshots computes the differences between two graphs.

Description: 

Compares two graphs (typically loaded from snapshots) and produces a
SnapshotDiff describing what changed. Comparison is by node ID —
symbols with the same ID in both graphs are compared for modifications.
Moved symbols (same name, different file) show as remove + add.

Inputs: 

base - The base graph for comparison. Must not be nil.
target - The target graph for comparison. Must not be nil.
baseSnapshotID - ID of the base snapshot (for labeling).
targetSnapshotID - ID of the target snapshot (for labeling).

Outputs: 

*SnapshotDiff - The computed differences.
error - Non-nil if either graph is nil.

Complexity: 

O(V + E) where V is max(baseNodes, targetNodes) and E is max(baseEdges, targetEdges).

Thread Safety: 

Safe for concurrent use on frozen graphs.

type SnapshotManager 

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

SnapshotManager manages saving and loading graph snapshots in BadgerDB.

Description: 

Provides CRUD operations for graph snapshots stored as gzip-compressed
JSON in BadgerDB. Each snapshot stores the full SerializableGraph plus
metadata for listing and filtering.

Thread Safety: 

Safe for concurrent use. BadgerDB handles its own concurrency control.

func NewSnapshotManager 

func NewSnapshotManager(db *badger.DB, logger *slog.Logger) (*SnapshotManager, error)

NewSnapshotManager creates a new SnapshotManager.

Description: 

Creates a manager that uses the given BadgerDB instance for persistence.
The DB should be opened by the caller and closed when no longer needed.

Inputs: 

db - An opened BadgerDB instance. Must not be nil.
logger - Logger for diagnostic output. Must not be nil.

Outputs: 

*SnapshotManager - The configured manager.
error - Non-nil if db or logger is nil.

func (*SnapshotManager) Delete 

func (m *SnapshotManager) Delete(ctx context.Context, snapshotID string) error

Delete removes a snapshot from BadgerDB.

Description: 

Removes all keys associated with the given snapshot ID: data, metadata,
and the reverse index entry. If the deleted snapshot was the "latest",
the latest pointer is also removed.

Inputs: 

ctx - Context for cancellation. Must not be nil.
snapshotID - The snapshot ID to delete. Must not be empty.

Outputs: 

error - Non-nil if the snapshot is not found or deletion fails.

func (*SnapshotManager) List 

func (m *SnapshotManager) List(ctx context.Context, projectHash string, limit int) ([]*SnapshotMetadata, error)

List returns metadata for snapshots matching the optional project hash filter.

Description: 

Iterates BadgerDB keys with the snapshot prefix to find metadata entries.
If projectHash is non-empty, only snapshots for that project are returned.
Results are ordered by CreatedAtMilli descending (newest first).

Inputs: 

ctx - Context for cancellation. Must not be nil.
projectHash - Optional filter. If empty, returns all snapshots.
limit - Maximum number of results. If <= 0, defaults to 100.

Outputs: 

[]*SnapshotMetadata - The matching snapshots.
error - Non-nil if the read fails.

func (*SnapshotManager) Load 

func (m *SnapshotManager) Load(ctx context.Context, snapshotID string) (*Graph, *SnapshotMetadata, error)

Load retrieves a graph snapshot by its ID.

Description: 

Loads the compressed data from BadgerDB, decompresses it, and
reconstructs the graph using FromSerializable.

Inputs: 

ctx - Context for cancellation. Must not be nil.
snapshotID - The snapshot ID to load. Must not be empty.

Outputs: 

*Graph - The reconstructed graph in read-only state.
*SnapshotMetadata - The snapshot metadata.
error - Non-nil if the snapshot is not found or reconstruction fails.

func (*SnapshotManager) LoadLatest 

func (m *SnapshotManager) LoadLatest(ctx context.Context, projectHash string) (*Graph, *SnapshotMetadata, error)

LoadLatest loads the most recent snapshot for a project.

Description: 

Uses the "latest" pointer to find and load the most recent snapshot
for the given project hash.

Inputs: 

ctx - Context for cancellation. Must not be nil.
projectHash - The SHA256(ProjectRoot)[:16] hash. Must not be empty.

Outputs: 

*Graph - The reconstructed graph in read-only state.
*SnapshotMetadata - The snapshot metadata.
error - Non-nil if no snapshot exists or reconstruction fails.

func (*SnapshotManager) Save 

func (m *SnapshotManager) Save(ctx context.Context, g *Graph, label string) (*SnapshotMetadata, error)

Save persists a graph snapshot to BadgerDB.

Description: 

Serializes the graph to JSON, gzip-compresses it, and stores it in
BadgerDB along with metadata. Updates the "latest" pointer for the
project.

Inputs: 

ctx - Context for cancellation. Must not be nil.
g - The graph to snapshot. Must not be nil and should be frozen.
label - Optional human-readable label for the snapshot.

Outputs: 

*SnapshotMetadata - Metadata about the saved snapshot.
error - Non-nil if serialization or storage fails.

Key Schema: 

graph:snap:{projectHash}:{snapshotID}:data → gzip(JSON(SerializableGraph))
graph:snap:{projectHash}:{snapshotID}:meta → JSON(SnapshotMetadata)
graph:snap:{projectHash}:latest            → snapshotID
graph:snap:index:{snapshotID}              → projectHash

type SnapshotMetadata 

type SnapshotMetadata struct {
	// SnapshotID is the unique identifier for this snapshot.
	// Derived from SHA256(ProjectRoot + BuiltAtMilli)[:16].
	SnapshotID string `json:"snapshot_id"`

	// ProjectRoot is the absolute path to the project root.
	ProjectRoot string `json:"project_root"`

	// ProjectHash is SHA256(ProjectRoot)[:16] for key grouping.
	ProjectHash string `json:"project_hash"`

	// GraphHash is the deterministic hash of the graph structure.
	GraphHash string `json:"graph_hash"`

	// Label is an optional human-readable label.
	Label string `json:"label,omitempty"`

	// CreatedAtMilli is when the snapshot was saved (Unix milliseconds UTC).
	CreatedAtMilli int64 `json:"created_at_milli"`

	// NodeCount is the number of nodes in the graph.
	NodeCount int `json:"node_count"`

	// EdgeCount is the number of edges in the graph.
	EdgeCount int `json:"edge_count"`

	// SchemaVersion is the serialization schema version.
	SchemaVersion string `json:"schema_version"`

	// CompressedSize is the size of the gzip-compressed JSON payload in bytes.
	CompressedSize int64 `json:"compressed_size"`

	// ContentHash is the SHA256 hash of the compressed payload.
	ContentHash string `json:"content_hash"`
}

SnapshotMetadata contains metadata about a saved graph snapshot.

type StalenessChecker 

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

StalenessChecker detects whether the code graph is stale relative to the current working tree.

Description: 

Records file modification times at build time and spot-checks a sample
of files at query time. Results are cached for StalenessCheckCacheTTL
(60s) to avoid repeated stat syscalls.

Thread Safety: Safe for concurrent use. Uses sync.RWMutex for cache.

func NewStalenessChecker 

func NewStalenessChecker(projectRoot string, fileMtimes map[string]int64) *StalenessChecker

NewStalenessChecker creates a staleness checker from a graph's recorded file mtimes.

Inputs:

  • projectRoot: Absolute path to the project root.
  • fileMtimes: Map of relative file path → mtime (Unix seconds) recorded at build time.

Outputs:

  • *StalenessChecker: The checker, or nil if fileMtimes is nil/empty.

Thread Safety: Safe for concurrent use after construction.

func (*StalenessChecker) Check 

func (sc *StalenessChecker) Check() StalenessResult

Check performs a staleness check, returning a cached result if available.

Description: 

If a cached result exists and is younger than StalenessCheckCacheTTL,
returns it immediately. Otherwise, spot-checks up to StalenessCheckSampleSize
files from the build-time mtime map against their current mtimes.

Outputs:

  • StalenessResult: The check outcome.

Thread Safety: Safe for concurrent use.

func (*StalenessChecker) InvalidateCache 

func (sc *StalenessChecker) InvalidateCache()

InvalidateCache forces the next Check() to recompute staleness.

Thread Safety: Safe for concurrent use.

type StalenessResult 

type StalenessResult struct {
	// IsStale is true if any files have changed since graph build.
	IsStale bool

	// ChangedFileCount is the number of files detected as changed.
	ChangedFileCount int

	// TotalFileCount is the total number of files checked.
	TotalFileCount int

	// PercentChanged is the ratio of changed files to total files (0.0-1.0).
	PercentChanged float64

	// CheckedAt is when this result was computed.
	CheckedAt time.Time

	// SampleBased is true if only a subset of files was checked.
	SampleBased bool
}

StalenessResult contains the outcome of a staleness check.

Thread Safety: Immutable after construction.

type SubtreeQueryEngine 

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

SubtreeQueryEngine provides efficient subtree queries using HLD position ranges.

Description: 

Leverages HLD's DFS ordering property: subtree(v) occupies contiguous
range [pos[v], pos[v]+size[v]) in position array. Enables O(log V)
subtree queries with a single segment tree range query.

Invariants:

  • pos[v] + size[v] <= nodeCount for all v
  • All descendants of v have positions in [pos[v], pos[v]+size[v])
  • Subtree ranges are non-overlapping (except for ancestors)
  • Exactly one of hld or forest is non-nil
  • In forest mode, subtrees are always within single tree (by definition)

Thread Safety: 

Safe for concurrent queries (read-only operations with internal locking for stats).

func NewSubtreeQueryEngine 

func NewSubtreeQueryEngine(hld *HLDecomposition, segTree *SegmentTree, aggFunc AggregateFunc, crsRecorder crs.CRS, sessionID string) (*SubtreeQueryEngine, error)

NewSubtreeQueryEngine creates a subtree query engine for single-tree mode.

Description: 

Combines HLD and segment tree for efficient subtree aggregation queries.
Uses HLD's subtree size information to compute position ranges.

Algorithm: 

Time:  O(1) - store references and validate
Space: O(1) - no allocations

Inputs:

  • hld: Heavy-Light Decomposition. Must not be nil.
  • segTree: Segment tree over node values. Must not be nil.
  • aggFunc: Aggregation function. Must match segTree's aggregation.
  • crsRecorder: CRS recorder for tracing (can be nil).
  • sessionID: Session ID for CRS context (ignored if crsRecorder is nil).

Outputs:

  • *SubtreeQueryEngine: Ready for queries. Never nil on success.
  • error: Non-nil if inputs are invalid.

Example: 

// Build HLD and segment tree
hld, _ := BuildHLD(ctx, graph, "main")
values := buildValueArray(hld)
segTree, _ := NewSegmentTree(ctx, values, AggregateSUM)

// Create subtree query engine
engine, _ := NewSubtreeQueryEngine(hld, segTree, AggregateSUM, nil, "")

Limitations:

  • Single tree only. For forests, use NewSubtreeQueryEngineForest.
  • Aggregation function cannot be changed after construction.

Assumptions:

  • HLD and segment tree are already built and valid.
  • Segment tree values correspond to HLD positions.

Thread Safety: Safe for concurrent use.

func NewSubtreeQueryEngineForest 

func NewSubtreeQueryEngineForest(forest *HLDForest, segTree *SegmentTree, aggFunc AggregateFunc, crsRecorder crs.CRS, sessionID string) (*SubtreeQueryEngine, error)

NewSubtreeQueryEngineForest creates a subtree query engine for forest mode.

Description: 

Like NewSubtreeQueryEngine but supports multiple disconnected trees.
Automatically routes queries to the correct tree component.

Algorithm: 

Time:  O(1) - store references and validate
Space: O(1) - no allocations

Inputs:

  • forest: HLD forest. Must not be nil.
  • segTree: Segment tree over ALL forest nodes. Must not be nil.
  • aggFunc: Aggregation function. Must match segTree's aggregation.
  • crsRecorder: CRS recorder for tracing (can be nil).
  • sessionID: Session ID for CRS context (ignored if crsRecorder is nil).

Outputs:

  • *SubtreeQueryEngine: Ready for queries. Never nil on success.
  • error: Non-nil if inputs are invalid.

Example: 

forest, _ := BuildHLDForest(ctx, graph, true)
values := buildForestValueArray(forest)
segTree, _ := NewSegmentTree(ctx, values, AggregateSUM)
engine, _ := NewSubtreeQueryEngineForest(forest, segTree, AggregateSUM, nil, "")

Limitations:

  • Segment tree must span entire forest (size = forest.TotalNodes()).

Assumptions:

  • Forest and segment tree are already built and valid.
  • Segment tree values correspond to forest global positions.

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) ClearCache 

func (sqe *SubtreeQueryEngine) ClearCache()

ClearCache clears the subtree range cache.

Description: 

Clears all cached subtree ranges. Useful for long-lived engines
that have queried many unique nodes and want to free memory.

Algorithm: 

Time:  O(n) where n is number of cached entries
Space: O(1)

Limitations: 

Cache entries are only 16 bytes each, so this is rarely needed.
Clearing the cache will cause next queries to recompute ranges.

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) Stats 

func (sqe *SubtreeQueryEngine) Stats() SubtreeQueryStats

Stats returns query statistics.

Description: 

Provides query count, latency metrics, and average subtree size.
Thread-safe via mutex locking.

Algorithm: 

Time:  O(1)
Space: O(1)

Outputs: 

SubtreeQueryStats with current statistics

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) SubtreeGCD 

func (sqe *SubtreeQueryEngine) SubtreeGCD(ctx context.Context, v string) (int64, error)

SubtreeGCD computes GCD of all values in subtree.

Description: 

Convenience wrapper for SubtreeQuery with GCD aggregation.
Requires engine to be configured with AggregateGCD.

Algorithm: 

Time:  O(log V) - delegates to SubtreeQuery
Space: O(1)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.

Outputs:

  • int64: GCD of all values in subtree(v).
  • error: Non-nil if node doesn't exist or query fails.

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) SubtreeMax 

func (sqe *SubtreeQueryEngine) SubtreeMax(ctx context.Context, v string) (int64, error)

SubtreeMax computes maximum value in subtree.

Description: 

Convenience wrapper for SubtreeQuery with MAX aggregation.
Requires engine to be configured with AggregateMAX.

Algorithm: 

Time:  O(log V) - delegates to SubtreeQuery
Space: O(1)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.

Outputs:

  • int64: Maximum value in subtree(v).
  • error: Non-nil if node doesn't exist or query fails.

Example: 

maxLatency, err := engine.SubtreeMax(ctx, "handler")

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) SubtreeMin 

func (sqe *SubtreeQueryEngine) SubtreeMin(ctx context.Context, v string) (int64, error)

SubtreeMin computes minimum value in subtree.

Description: 

Convenience wrapper for SubtreeQuery with MIN aggregation.
Requires engine to be configured with AggregateMIN.

Algorithm: 

Time:  O(log V) - delegates to SubtreeQuery
Space: O(1)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.

Outputs:

  • int64: Minimum value in subtree(v).
  • error: Non-nil if node doesn't exist or query fails.

Example: 

minMemory, err := engine.SubtreeMin(ctx, "allocator")

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) SubtreeNodes 

func (sqe *SubtreeQueryEngine) SubtreeNodes(ctx context.Context, v string) ([]string, error)

SubtreeNodes returns all node IDs in subtree(v).

Description: 

Materializes the subtree as a list of node IDs.
Useful for debugging but slower than aggregation queries.

Algorithm: 

Time:  O(size[v]) - collect all nodes in subtree
Space: O(size[v]) - store node IDs

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.

Outputs:

  • []string: Node IDs in DFS order (same as position order)
  • error: Non-nil if node doesn't exist

Example: 

nodes, err := engine.SubtreeNodes(ctx, "package")
fmt.Printf("Package contains %d functions\n", len(nodes))

Limitations: 

Slower than SubtreeQuery - use only when you need the actual node list.

Thread Safety: Safe for concurrent use (allocates new slice).

func (*SubtreeQueryEngine) SubtreeQuery 

func (sqe *SubtreeQueryEngine) SubtreeQuery(ctx context.Context, v string) (int64, error)

SubtreeQuery computes aggregate over all nodes in subtree of v.

Description: 

Uses HLD's contiguous subtree property to answer query with a single
segment tree range query. Subtree(v) = [pos[v], pos[v]+size[v]).

Algorithm: 

Time:  O(log V) - single segment tree query
Space: O(1) - no allocations

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.

Outputs:

  • int64: Aggregate value over all nodes in subtree(v).
  • error: Non-nil if node doesn't exist or query fails.

Special Cases:

  • SubtreeQuery(leaf) = value[leaf] (single node, uses fast path)
  • SubtreeQuery(root) = aggregate over entire tree

Example: 

// Total complexity in package and all subpackages
totalComplexity, err := engine.SubtreeQuery(ctx, "pkg/parser")
if err != nil {
	return fmt.Errorf("subtree query: %w", err)
}
fmt.Printf("Total complexity: %d\n", totalComplexity)

CRS Integration: 

Records query as TraceStep with node ID, subtree size, result.
Only records if CRS recorder is non-nil (H-PRE-6).

Limitations:

  • Requires valid HLD and segment tree.
  • Forest mode requires GetTreeOffset method.

Assumptions:

  • Node v exists in the graph.
  • HLD positions are valid and consistent.

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) SubtreeRange 

func (sqe *SubtreeQueryEngine) SubtreeRange(ctx context.Context, v string) (start, end int, err error)

SubtreeRange returns the position range occupied by subtree(v).

Description: 

Returns [start, end] (inclusive) position range for subtree.
Useful for debugging and visualization.

Algorithm: 

Time:  O(1) - cached array lookups
Space: O(1)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.

Outputs:

  • start: First position in subtree (pos[v])
  • end: Last position in subtree (pos[v] + size[v] - 1)
  • error: Non-nil if node doesn't exist

Example: 

start, end, _ := engine.SubtreeRange(ctx, "parser")
fmt.Printf("Subtree occupies positions [%d, %d]\n", start, end)

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) SubtreeSum 

func (sqe *SubtreeQueryEngine) SubtreeSum(ctx context.Context, v string) (int64, error)

SubtreeSum computes sum of all values in subtree.

Description: 

Convenience wrapper for SubtreeQuery with SUM aggregation.
Requires engine to be configured with AggregateSUM.

Algorithm: 

Time:  O(log V) - delegates to SubtreeQuery
Space: O(1)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.

Outputs:

  • int64: Sum of all values in subtree(v).
  • error: Non-nil if node doesn't exist or query fails.

Example: 

totalLOC, err := engine.SubtreeSum(ctx, "main")

Thread Safety: Safe for concurrent use.

func (*SubtreeQueryEngine) Validate 

func (sqe *SubtreeQueryEngine) Validate() error

Validate checks that HLD and SegmentTree are compatible.

Description: 

Verifies:
- Exactly one of hld/forest is non-nil (L-PRE-2)
- HLD/Forest and SegmentTree have same node count
- All subtree ranges are valid (pos[v] + size[v] <= nodeCount)

Algorithm: 

Time:  O(V) - must check all nodes
Space: O(1)

Outputs:

  • error: Non-nil if validation fails

Thread Safety: Safe for concurrent use (read-only).

type SubtreeQueryStats 

type SubtreeQueryStats struct {
	QueryCount     int64
	TotalLatency   time.Duration
	AvgLatency     time.Duration
	AvgSubtreeSize float64
}

SubtreeQueryStats provides query statistics.

type SubtreeUpdateEngine 

type SubtreeUpdateEngine struct {
	*SubtreeQueryEngine // Embed query engine
	// contains filtered or unexported fields
}

SubtreeUpdateEngine extends SubtreeQueryEngine with update operations.

Description: 

Provides O(log V) subtree updates using single range update.
All nodes in subtree(v) updated with one segment tree RangeUpdate.

Thread Safety: 

NOT safe for concurrent updates. Caller must synchronize writes.
Safe for concurrent reads (queries).

func NewSubtreeUpdateEngine 

func NewSubtreeUpdateEngine(sqe *SubtreeQueryEngine) (*SubtreeUpdateEngine, error)

NewSubtreeUpdateEngine creates a subtree update engine.

Description: 

Wraps a SubtreeQueryEngine to add update operations.
The query engine must already be constructed and valid.

Algorithm: 

Time:  O(1) - wrap reference
Space: O(1)

Inputs:

  • sqe: Subtree query engine. Must not be nil.

Outputs:

  • *SubtreeUpdateEngine: Ready for updates. Never nil on success.
  • error: Non-nil if query engine is nil.

Example: 

queryEngine, _ := NewSubtreeQueryEngine(hld, segTree, AggregateSUM, nil, "")
updateEngine, _ := NewSubtreeUpdateEngine(queryEngine)

Thread Safety: Safe for concurrent use (wraps read-only engine).

func (*SubtreeUpdateEngine) SubtreeDecrement 

func (sue *SubtreeUpdateEngine) SubtreeDecrement(ctx context.Context, v string) error

SubtreeDecrement decrements all values in subtree (delta=-1).

Description: 

Convenience wrapper for SubtreeUpdate with delta=-1.

Thread Safety: NOT safe for concurrent updates.

func (*SubtreeUpdateEngine) SubtreeIncrement 

func (sue *SubtreeUpdateEngine) SubtreeIncrement(ctx context.Context, v string) error

SubtreeIncrement increments all values in subtree (delta=+1).

Description: 

Convenience wrapper for SubtreeUpdate with delta=1.

Thread Safety: NOT safe for concurrent updates.

func (*SubtreeUpdateEngine) SubtreeSet 

func (sue *SubtreeUpdateEngine) SubtreeSet(ctx context.Context, v string, value int64) error

SubtreeSet sets all node values in subtree(v) to a specific value.

Description: 

Sets each node in subtree to value.
Implementation iterates through positions since different nodes
have different current values (cannot use single RangeUpdate).

Algorithm: 

Time:  O(size[v]) - must update each node individually
Space: O(1)

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.
  • value: Value to set for all nodes in subtree.

Outputs:

  • error: Non-nil if node doesn't exist or update fails.

Note: 

This is slower than SubtreeUpdate because nodes have different
current values, so we cannot compute a single delta for all.

Thread Safety: NOT safe for concurrent updates.

func (*SubtreeUpdateEngine) SubtreeUpdate 

func (sue *SubtreeUpdateEngine) SubtreeUpdate(ctx context.Context, v string, delta int64) error

SubtreeUpdate adds delta to all node values in subtree(v).

Description: 

Uses contiguous subtree range to perform single range update.
Much more efficient than updating each node individually.

Algorithm: 

Time:  O(log V) - single range update with lazy propagation
Space: O(1) - no allocations

Inputs:

  • ctx: Context for cancellation. Must not be nil.
  • v: Root node of subtree. Must exist in graph.
  • delta: Value to add to each node in subtree.

Outputs:

  • error: Non-nil if node doesn't exist or update fails.

Example: 

// Increment complexity for entire package by 10
err := engine.SubtreeUpdate(ctx, "pkg/parser", 10)
if err != nil {
	return fmt.Errorf("subtree update: %w", err)
}

CRS Integration: 

Records update as TraceStep with node ID, delta, subtree size.

Thread Safety: NOT safe for concurrent updates.

func (*SubtreeUpdateEngine) UpdateStats 

func (sue *SubtreeUpdateEngine) UpdateStats() SubtreeUpdateStats

UpdateStats returns update statistics.

Description: 

Provides update count, latency metrics, and total nodes updated.

Algorithm: 

Time:  O(1)
Space: O(1)

Outputs: 

SubtreeUpdateStats with current statistics

Thread Safety: Safe for concurrent use.

type SubtreeUpdateStats 

type SubtreeUpdateStats struct {
	UpdateCount        int64
	TotalUpdateLatency time.Duration
	AvgUpdateLatency   time.Duration
	NodesUpdated       int64
}

SubtreeUpdateStats provides update statistics.

type TraceConfig 

type TraceConfig struct {
	// ExcludeFromAnalysis lists file path prefixes to force-classify as non-production.
	// Example: ["vendor/", "third_party/", "generated/"]
	ExcludeFromAnalysis []string `yaml:"exclude_from_analysis"`

	// IncludeOverride lists file path prefixes to force-classify as production,
	// overriding the graph topology result.
	// Example: ["integration/core/"]
	IncludeOverride []string `yaml:"include_override"`
}

TraceConfig holds user-provided overrides for file classification.

Description: 

Loaded from <projectRoot>/trace.config.yaml. All fields are optional.
A missing config file is not an error (zero-config works out of the box).

Thread Safety: Safe for concurrent reads after construction.

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.