graph

Documentation

Overview

Package graph builds the whole-program call graph and extracts per-entrypoint flows into the mutable Flow IR shared by the filter pipeline and output layers.

Index

• Variables
• type Builder
• type DTOField
• type DTOInfo
• type DecisionInfo
• type EffectUse
• type ExitInfo
• type Flow
  • func Extract(p *loader.Program, cg *callgraph.Graph, fallback *callgraph.Graph, ...) (*Flow, error)
  • func (f *Flow) AddEdge(from, to *Node, kind, label string, seq int)
  • func (f *Flow) AddNode(key string, n *Node)
  • func (f *Flow) EdgeAsync(from, to *Node) bool
  • func (f *Flow) EdgeKind(from, to *Node) string
  • func (f *Flow) EdgeLabel(from, to *Node) string
  • func (f *Flow) EdgeSeq(from, to *Node) int
  • func (f *Flow) EdgeSiteBlock(from, to *Node) *ssa.BasicBlock
  • func (f *Flow) MarkEdgeAsync(from, to *Node)
  • func (f *Flow) RewireEdge(from, to, newFrom *Node, kind string)
  • func (f *Flow) SetEdgeKind(from, to *Node, kind, label string)
  • func (f *Flow) SetEdgeSeq(from, to *Node, seq int)
• type Limits
• type Node
  • func (n *Node) MergeEffectsFrom(c *Node)
• type Options
• type Result
  • func Build(p *loader.Program, roots []*ssa.Function, opts Options) (*Result, error)

Variables

var DefaultLimits = Limits{MaxDepth: 40, MaxNodes: 5000}

Types

type Builder

type Builder interface {
	Name() string
	// Build constructs a call graph for the functions in cone; initial is a
	// sound over-approximation some algorithms refine (may be nil).
	Build(prog *ssa.Program, cone map[*ssa.Function]bool, initial *callgraph.Graph) *callgraph.Graph
}

Algorithm trade-off: CHA is fast but over-approximates interface calls (every implementation of the method's signature becomes an edge). VTA propagates concrete types through a whole-program flow graph, giving far more precise interface resolution, at a cost that grows steeply with the size of the function set. Strategy: build CHA once (cheap, also serves as VTA's initial graph), restrict VTA to the CHA-reachable cone from the requested entrypoints, and fall back to plain CHA when the cone is huge or VTA exceeds its wall-clock budget. The Builder interface keeps algorithms swappable.

type DTOField

type DTOField struct {
	Name  string // Go field name
	Tag   string // wire name from the json/xml/form tag
	Type  string
	Rules string // validation rules (ozzo calls + validate/binding tags)
}

type DTOInfo

type DTOInfo struct {
	Type      string // "api.CreateOrderRequest"
	Format    string // "json" | "xml"
	Fields    []DTOField
	Truncated bool
}

DTOInfo is a data contract (request or response body) of an entrypoint.

type DecisionInfo

type DecisionInfo struct {
	Condition string
	Uses      []string
	FailWhen  bool // which boolean value of the condition takes the exit
	// Gate: no branch exits - the condition decides whether a block of
	// work runs at all ("if !whiteListClient { check debts }"). FailWhen
	// holds the value that SKIPS the work.
	Gate bool
	// Branch: both sides of the gate hold work - an exclusive either/or
	// ("email lookup or phone lookup"). Child edges carry yes/no labels.
	Branch bool
	// Checks: what a validation guard enforces, human-rendered
	// ("phone - required, length(11, 11), digit").
	Checks string
}

DecisionInfo describes a semantic guard rendered as a decision node.

type EffectUse

type EffectUse struct {
	*effects.Effect
	Pos   string // call-site position in module code
	Async bool   // the call happens inside a goroutine
	// Alt: this effect's site is in a branch mutually exclusive with
	// another effect on the same node - they never both run.
	Alt bool
}

EffectUse is one boundary call absorbed by a module-code node: the effect identity plus where in the module it happens.

type ExitInfo

type ExitInfo struct {
	Kind    string // "sentinel" | "message" | "unknown"
	Name    string
	Message string
	Pos     string
}

ExitInfo describes the error outcome of a decision's fail branch.

type Flow

type Flow struct {
	Root      *Node
	Nodes     map[string]*Node // by Node.Name
	Order     []*Node          // deterministic BFS insertion order (excludes Root)
	Truncated bool
	Warnings  []string
	// contains filtered or unexported fields
}

Flow is the mutable intermediate representation between the raw call graph and JSON output: a DAG (with back-edges for recursion) of meaningful-call candidates. The filter pipeline marks and prunes it in place.

func Extract

func Extract(p *loader.Program, cg *callgraph.Graph, fallback *callgraph.Graph, root *ssa.Function, limits Limits) (*Flow, error)

Extract walks the call graph breadth-first from root, producing the raw flow: every reachable module function, effect leaves at library boundaries, terminal nodes for unresolvable dynamic calls, async tags for goroutine spawns.

fallback (may be nil, typically the CHA graph) is consulted per call site when cg resolves an interface call to nothing - the signature pattern of reflection-based dependency injection, where VTA never observes the allocation that flows into an interface field. A unique implementation is then taken as resolved; up to maxFallbackImpls become static-multi edges; more stays an honest dynamic terminal.

func (*Flow) AddEdge

func (f *Flow) AddEdge(from, to *Node, kind, label string, seq int)

AddEdge adds an edge with flowchart semantics at a source position.

func (*Flow) AddNode

func (f *Flow) AddNode(key string, n *Node)

AddNode registers an externally built node (decisions, exits) under a unique key and appends it to the deterministic order.

func (*Flow) EdgeAsync

func (f *Flow) EdgeAsync(from, to *Node) bool

EdgeAsync reports whether the from->to hop happens via a goroutine.

func (*Flow) EdgeKind

func (f *Flow) EdgeKind(from, to *Node) string

EdgeKind returns "pass"/"fail" for flowchart edges, "" for plain calls.

func (*Flow) EdgeLabel

func (f *Flow) EdgeLabel(from, to *Node) string

EdgeLabel returns the short display label of an edge, if any.

func (*Flow) EdgeSeq

func (f *Flow) EdgeSeq(from, to *Node) int

EdgeSeq is the source-order key of an edge (0 = unknown, sorts last).

func (*Flow) EdgeSiteBlock

func (f *Flow) EdgeSiteBlock(from, to *Node) *ssa.BasicBlock

EdgeSiteBlock returns the basic block of the call site behind the edge.

func (*Flow) MarkEdgeAsync

func (f *Flow) MarkEdgeAsync(from, to *Node)

MarkEdgeAsync records an async hop (also used when the filter splices collapse chains).

func (*Flow) RewireEdge

func (f *Flow) RewireEdge(from, to, newFrom *Node, kind string)

RewireEdge moves the from->to edge to newFrom->to, preserving async and site metadata and applying the given kind.

func (*Flow) SetEdgeKind

func (f *Flow) SetEdgeKind(from, to *Node, kind, label string)

SetEdgeKind records flowchart semantics on an existing edge.

func (*Flow) SetEdgeSeq

func (f *Flow) SetEdgeSeq(from, to *Node, seq int)

SetEdgeSeq records the source-order key, keeping the earliest.

type Limits

type Limits struct {
	MaxDepth int
	MaxNodes int
}

Limits guards raw extraction; hitting one marks the flow truncated rather than failing.

type Node

type Node struct {
	Name string // qualified display name; the node's identity
	Fn   *ssa.Function
	Pkg  string
	Pos  string
	Kind string // "step" | "terminal" | "decision" | "exit"
	// Effects are the boundary calls this node performs, in call-site
	// order. Driver calls (database/sql, go-redis, kafka writers, ...) are
	// not nodes: the module method that makes them carries them.
	Effects    []EffectUse
	Async      bool   // reached via a `go` statement on some edge
	Resolution string // "static" | "static-multi" | "dynamic" | "truncated"
	Depth      int

	Out []*Node
	In  []*Node

	// Returns renders the function's result types compactly
	// ("*model.Order, error") - what the reader gets out of this step.
	Returns string

	// ErrorExits are the named error outcomes this function can return -
	// business branch points (guards, permission checks) a reader cares
	// about alongside effects.
	ErrorExits []string

	// SuccessResponse: how the entrypoint completes successfully over HTTP
	// ("HTTP 200"), when statically known.
	SuccessResponse string
	// RequestDTO/ResponseDTO: the entrypoint's data contracts.
	RequestDTO  *DTOInfo
	ResponseDTO *DTOInfo

	// Guards layer (set by internal/guards after filtering).
	Fallible       bool          // some caller propagates this call's error
	ChecksOverflow int           // semantic guards beyond the render budget
	Decision       *DecisionInfo // kind == "decision"
	ExitErr        *ExitInfo     // kind == "exit"

	// Filter bookkeeping.
	Collapsed []string // names of wrappers inlined into this node
	DroppedBy string   // rule id that dropped/collapsed this node, "" = kept
	Collapse  bool     // marked for collapse rather than drop
	Kept      bool     // protected: effects and ancestors of effects
}

func (*Node) MergeEffectsFrom

func (n *Node) MergeEffectsFrom(c *Node)

MergeEffectsFrom bubbles a collapsing node's effects into its survivor, deduplicating: what the subtree ultimately does stays visible.

type Options

type Options struct {
	Algo       string // "auto" | "vta" | "cha"
	VTATimeout time.Duration
	// MaxVTAFuncs is the reachable-cone size beyond which auto mode falls
	// back to CHA.
	MaxVTAFuncs int
}

Options controls call-graph construction.

type Result

type Result struct {
	Graph *callgraph.Graph
	// CHA is the sound over-approximation, kept alongside a VTA Graph so
	// extraction can fall back per call site when VTA resolves an interface
	// call to nothing (typical with reflection-based dependency injection,
	// where VTA never sees the allocation flow into an interface field).
	CHA   *callgraph.Graph
	Algo  string // algorithm actually used
	Funcs int    // size of the function set given to the algorithm
	Warn  string // non-empty when a fallback happened
}

Result carries the built graph plus honesty metadata for the CLI.

func Build

func Build(p *loader.Program, roots []*ssa.Function, opts Options) (*Result, error)

Build constructs the call graph once for the whole program. roots are the entrypoints whose cones matter; with an empty roots slice the whole module is the cone.