lang

package
v0.4.2-alpha Latest Latest
Warning

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

 Go to latest Published: Jan 30, 2025 License: Apache-2.0 Imports: 17 Imported by: 0

Documentation

Overview

Package lang contains functions to help manipulate different objects representing elements of the Go language and the ssa.

Package lang provides functions to operate on the SSA representation of a program. It provides an interface to implement visitors for SSA instructions.

Index

Constants

This section is empty.

Variables

View Source 
var DummyPos = token.Position{
	Filename: "unknown",
	Offset:   -1,
	Line:     -1,
	Column:   -1,
}

DummyPos is a dummy position returned to indicate that no position could be found. Can also be used when generating code, and the generated code has no position.

Functions

func CallGraphReachable 

func CallGraphReachable(cg *callgraph.Graph, excludeMain bool, excludeInit bool) map[*ssa.Function]bool

CallGraphReachable returns a map where each entry is a reachable function

func CanType 

func CanType(v ssa.Value) (res bool)

CanType checks some properties to ensure calling the Type() method on the value won't cause a segfault. This seems to be a problem in the SSA.

func FindImplementationMethod 

func FindImplementationMethod(prog *ssa.Program, tp types.Type, iface types.Type, methodName string) (method *ssa.Function, pointerRequired bool)

FindImplementationMethod looks up the ssa.Function for a reciever value of type tp when called for the given interface type and method name. This could require adding a pointer indirection if the given tp is e.g. a struct type, so the function also returns a boolean indicating if this is necessary.

func FindTypeByName 

func FindTypeByName(prog *ssa.Program, pkg string, tpName string) types.Type

FindTypeByName finds the given type from the given package, if it exists. Otherwise, returns nil

func FnReadsFrom 

func FnReadsFrom(fn *ssa.Function, val ssa.Value) bool

FnReadsFrom returns true if an instruction in fn reads from val.

func FnWritesTo 

func FnWritesTo(fn *ssa.Function, val ssa.Value) bool

FnWritesTo returns true if an instruction in fn writes to val.

func GetArgs 

func GetArgs(instr ssa.CallInstruction) []ssa.Value

GetArgs returns the arguments of a function call including the receiver when the function called is a method. More precisely, it returns instr.Common().Args, but prepends instr.Common().Value if the call is "invoke" mode.

func GetPackageOfType 

func GetPackageOfType(tp types.Type) *types.Package

GetPackageOfType finds the type.Package for a type. Does not require any ssa.* objects

func HasPathTo 

func HasPathTo(b1 *ssa.BasicBlock, b2 *ssa.BasicBlock, mem map[*ssa.BasicBlock]map[*ssa.BasicBlock]bool) bool

HasPathTo returns true if there is a control-flow path from b1 to b2. Use mem to amortize cost. If mem is nil, then the algorithm runs without memoization, and no map is allocated.

func InstrMethodKey 

func InstrMethodKey(instr ssa.CallInstruction) fn.Optional[string]

InstrMethodKey return a method key (as used in the analyzer state for indexing interface methods) if the instruction calls a method from an interface Returns an optional value TODO: this may not be idiomatic but I'm testing this "Optional" implementation

func InstrSwitch 

func InstrSwitch(visitor InstrOp, instr ssa.Instruction)

InstrSwitch is mainly a map from the different instructions to the methods of the visitor.

func IsAnyType 

func IsAnyType(tp types.Type) bool

IsAnyType tests whether the type is equivalent to the `any` type

func IsChannelEnclosingType 

func IsChannelEnclosingType(t types.Type) bool

IsChannelEnclosingType return true if the type is a pointer to channel, a channel, or a data structure containing a channel

func IsErrorType 

func IsErrorType(t types.Type) bool

IsErrorType returns true if t is the error type

func IsExternal 

func IsExternal(function *ssa.Function) bool

IsExternal returns true if function is external (in ssa, when Blocks is nil)

func IsNillableType 

func IsNillableType(t types.Type) bool

IsNillableType returns true if t is a type that can have the nil value.

func IsPredicateFunctionType 

func IsPredicateFunctionType(f *types.Signature) bool

IsPredicateFunctionType returns true if f is a function that can be interpreted as a predicate A function is a predicate if its last argument is either a boolean or an error.

func IsReturningFunctionType 

func IsReturningFunctionType(typ types.Type) bool

IsReturningFunctionType returns true if typ is the type of a function that returns values

func IsStaticallyDefinedLocal 

func IsStaticallyDefinedLocal(v ssa.Value) bool

IsStaticallyDefinedLocal returns true if the value is statically defined, i.e. its value is entirely defined at compile time. This is the case for: - constants - slices of constants This does not analyze whether the value v is mutated; this function is useful in conjunction with the dataflow analyzes for example, which would track all dataflows to the values being analyzed. For values of nodes that do not have any other incoming edges, this function is sound: the dataflow analysis indirectly guarantees no data is flowing from a parameter of the function, or from being written to by another function being called in the function body.

TODO: make this function usable outside of dataflow analysis

func IsValueReturningCall 

func IsValueReturningCall(value ssa.Value) bool

IsValueReturningCall returns true if value is a call that returns some value

func IterateInstructions 

func IterateInstructions(function *ssa.Function, f func(index int, instruction ssa.Instruction))

IterateInstructions iterates through all the instructions in the function, in no specific order. It ignores the order in which blocks should be executed, but always starts with the first block.

func IterateValues 

func IterateValues(function *ssa.Function, f func(index int, value ssa.Value))

IterateValues applies f to every value in the function. It might apply f several times to the same value if the value is from an instruction, the index of the instruction in the block will be provided, otherwise a value of -1 indicating the value is not in an instruction is given to the function.

func LastInstr 

func LastInstr(block *ssa.BasicBlock) ssa.Instruction

LastInstr returns the last instruction in a block. There is always a last instruction for a reachable block. Returns nil for an empty block (a block can be empty if it is non-reachable)

func LastInstrIsReturn 

func LastInstrIsReturn(block *ssa.BasicBlock) bool

LastInstrIsReturn returns true when the last instruction of the block is a return instruction

func MatchExtract 

func MatchExtract(x ssa.Value) ssa.Value

MatchExtract is a proxy for matching a *ssa.Extract. It returns a non-nil value if x is some tuple-extraction value i.e. if x is extract y #0 for some y, then y is returned, otherwise nil

func MatchLoadField 

func MatchLoadField(x ssa.Value) ssa.Value

MatchLoadField matches instruction sequence: y = &z.Field x = *y and returns (z,true) if x is given as argument

func MatchNegation 

func MatchNegation(x ssa.Value) ssa.Value

MatchNegation returns a non-nil ssa. value if x is the negation of some value y, in which case y is returned.

func MatchNilCheck 

func MatchNilCheck(v ssa.Value) (ssa.Value, bool)

MatchNilCheck returns a non-nil ssa value if x is a nil check, i.e. an instruction of the form 'y == nil' or 'y != nil' for some y

The returned ssa value is the value being checked against. The boolean is true if the check is a check of the form 'y == nil' and false if 'y != nil'

func NewBinOp 

func NewBinOp(op token.Token, x, y dst.Expr) *dst.BinaryExpr

NewBinOp constructs a new binary expression

func NewFalse 

func NewFalse() *dst.BasicLit

NewFalse returns a new AST structure that represents the boolean false

func NewFloat32 

func NewFloat32(value float32) *dst.BasicLit

NewFloat32 returns a new AST structure that represents the float32 value

func NewFloat64 

func NewFloat64(value float64) *dst.BasicLit

NewFloat64 returns a new AST structure that represents the float64 value

func NewInt 

func NewInt(value int) *dst.BasicLit

NewInt returns a new AST structure that represents the integer value

func NewNil 

func NewNil() dst.Expr

NewNil returns a dst expression that represents nil

func NewPanic 

func NewPanic(args ...dst.Expr) *dst.CallExpr

NewPanic returns a new call expression that calls panic over the arguments args ...

func NewString 

func NewString(value string) *dst.BasicLit

NewString returns a new AST structure that represents the string value

func NewTypeExpr 

func NewTypeExpr(t types.Type) (dst.Expr, error)

NewTypeExpr returns an AST expression that represents the type t.

For example, the expression that represents a types.Struct will be of the form struct{...}.

For an integer, the expression is an identifier 'int'

func NewUnOp 

func NewUnOp(op token.Token, x dst.Expr) *dst.UnaryExpr

NewUnOp construct a new unary expression

func PackageNameFromFunction 

func PackageNameFromFunction(f *ssa.Function) string

PackageNameFromFunction returns the best possible package name for a ssa.Function If the Function has a package, use that. If the function doesn't have a package, check if it's a method and use the package associated with its object If none of those are true, it must be an error, so try to extract the package name from the various error formats.

func PackageTypeFromFunction 

func PackageTypeFromFunction(f *ssa.Function) *types.Package

PackageTypeFromFunction returns the package associated with a function If the function has a package, return that. If the function is a method, return the package of its object

func RunAllPaths 

func RunAllPaths(op PathSensitiveInstrOp, function *ssa.Function)

RunAllPaths tries every possible simple path in the function and runs the instruction operation calling NewPath every time a new path from the initial Block is taken, and NewBlock every time a new Block in a path is entered. The operation op should implement the functionality to keep track of path information, either at the Block level or at the operation level.

func RunDFS 

func RunDFS(op InstrOp, function *ssa.Function)

RunDFS visits the blocks in the function in a depth-first search, running the instruction operation on every instruction in each Block.

func RunForwardIterative 

func RunForwardIterative(op IterativeAnalysis, function *ssa.Function)

RunForwardIterative visits the blocks in the function. At each Block visited, it queues the successors of the Block if the information for the Block has changed after visiting each of its instructions. All reachable blocks of the function will be visited if the call to ChangedOnBlock is true after each first visit to a given Block (the IterativeAnalysis structure must keep track of previously visited blocks, and ensure termination)

func SafeFunctionPos 

func SafeFunctionPos(function *ssa.Function) fn.Optional[token.Position]

SafeFunctionPos returns the position of the function without panicking

func TryTupleIndexType 

func TryTupleIndexType(v types.Type, i int) types.Type

TryTupleIndexType extract the type of element i in tuple type, or returns the type if it's not a tuple type

func ValuesWithSameData 

func ValuesWithSameData(v1 ssa.Value, v2 ssa.Value) bool

ValuesWithSameData defines when values v1 and v2 refer to the same data. WARNING: This function is incomplete, and encodes only the necessary information for validators. You should modify as much as you need.

func ZeroValueExpr 

func ZeroValueExpr(typ types.Type) (dst.Expr, error)

ZeroValueExpr returns the zero-value of a type typ, or an error when it could not find a zero value

Types

type BlockPath 

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

A BlockPath is a simple list of blocks

func (*BlockPath) ToBlocks 

func (b *BlockPath) ToBlocks() []*ssa.BasicBlock

ToBlocks turns a pointer-based list into a slice

type BlockTree 

type BlockTree struct {
	Block    *ssa.BasicBlock
	Parent   *BlockTree
	Children []*BlockTree
}

BlockTree is a tree of ssa.BasicBlock

func (*BlockTree) AddChild 

func (t *BlockTree) AddChild(block *ssa.BasicBlock) *BlockTree

AddChild adds a child to t and returns pointer to that child

func (*BlockTree) CountPathOccurrences 

func (t *BlockTree) CountPathOccurrences(block *ssa.BasicBlock) int

CountPathOccurrences count how many times Block is encountered on the path to the root

func (*BlockTree) PathToLeaf 

func (t *BlockTree) PathToLeaf() *BlockPath

PathToLeaf returns the path from the root to the receiver

type CalleeInfo 

type CalleeInfo struct {
	Callee *ssa.Function
	Type   CalleeType
}

CalleeInfo decorates a function with some CalleeType that records how the dataflow information of the function can be resolved or how the callee's identity was determined

type CalleeType 

type CalleeType int

A CalleeType gives information about how the callee was resolved 

const (
	// Static indicates the callee is a statically defined function
	Static CalleeType = 1 << iota
	// CallGraph indicates the callee is a function obtained from the call graph
	CallGraph
	// InterfaceContract indicates the callee is obtained from an interface contract (one particular instance
	// of an interface method to stand for all methods)
	InterfaceContract
	// InterfaceMethod indicates the calle is an interface method
	InterfaceMethod
)

func (CalleeType) Code 

func (t CalleeType) Code() string

Code returns a short string representation of the type of callee

type CallgraphAnalysisMode 

type CallgraphAnalysisMode uint64

CallgraphAnalysisMode is either PointerAnalysis, StaticAnalysis, ClassHierarchyAnalysis, RapidTypeAnalysis or VariableTypeAnalysis for calling ComputeCallGraph 

const (
	// PointerAnalysis is over-approximating (slow)
	PointerAnalysis CallgraphAnalysisMode = iota
	// StaticAnalysis is under-approximating (fast)
	StaticAnalysis
	// ClassHierarchyAnalysis is a coarse over-approximation (fast)
	ClassHierarchyAnalysis
	// RapidTypeAnalysis TODO: review
	RapidTypeAnalysis
	// VariableTypeAnalysis TODO: review
	VariableTypeAnalysis
)

func (CallgraphAnalysisMode) ComputeCallgraph 

func (mode CallgraphAnalysisMode) ComputeCallgraph(prog *ssa.Program) (*callgraph.Graph, error)

ComputeCallgraph computes the call graph of prog using the provided mode.

type Expression 

type Expression interface {
	String() string
	Type() ssa.Type
}

An Expression can be used to manipulate expression for symbolic execution. TODO: implementations

type FuncInfo 

type FuncInfo struct {
	// Package is the package where the function is declared
	Package *decorator.Package

	// Decorator is the decorator object that contains also the maps from dst to ast objects
	Decorator *decorator.Decorator

	// File if the file where the function is declared
	File *dst.File

	// NodeMap stores parent information for the ast
	NodeMap map[dst.Node]*NodeTree

	// Decl is the function declaration in the ast
	Decl *dst.FuncDecl
}

FuncInfo contains information about a function declaration in the ast.

func (*FuncInfo) ClosestEnclosingScope 

func (f *FuncInfo) ClosestEnclosingScope(n dst.Node) *types.Scope

ClosestEnclosingScope returns the closest scope to the node n.

For example, in : 

func f(..) {
  if(b) {
     node1
  } else {
    node2
  }
  node 3
}

the closest scope for node1 is the then-branch scope, for node2 the else-branch scope and for node3 the function scope

func (*FuncInfo) FreshNameAt 

func (f *FuncInfo) FreshNameAt(n dst.Node, prefix string, i int) string

FreshNameAt returns a fresh identifier at node n. The identifier will be of the form `prefix(NUM)` where NUM is empty or some integer. For example, FreshNameAt(n,"s", 0) may return "s", "s0" or "s1".

func (*FuncInfo) FunctionScope 

func (f *FuncInfo) FunctionScope() *types.Scope

FunctionScope returns the scope of the function

func (*FuncInfo) NameExistsAt 

func (f *FuncInfo) NameExistsAt(n dst.Node, name string) bool

NameExistsAt checks whether name is a declared identifier at node n

func (*FuncInfo) NewName 

func (f *FuncInfo) NewName(n dst.Node, prefix string) (*types.Scope, string)

NewName returns a new identifier that is a fresh name at node n. If successful, the scope should be non-nil and addition of the identifier in the program should be done by adding the identifier to the scope returned (if the intention is to declare the identifier next to n).

type InstrOp 

type InstrOp interface {
	DoDebugRef(*ssa.DebugRef)
	DoUnOp(*ssa.UnOp)
	DoBinOp(*ssa.BinOp)
	DoCall(*ssa.Call)
	DoChangeInterface(*ssa.ChangeInterface)
	DoChangeType(*ssa.ChangeType)
	DoConvert(*ssa.Convert)
	DoSliceArrayToPointer(*ssa.SliceToArrayPointer)
	DoMakeInterface(*ssa.MakeInterface)
	DoExtract(*ssa.Extract)
	DoSlice(*ssa.Slice)
	DoReturn(*ssa.Return)
	DoRunDefers(*ssa.RunDefers)
	DoPanic(*ssa.Panic)
	DoSend(*ssa.Send)
	DoStore(*ssa.Store)
	DoIf(*ssa.If)
	DoJump(*ssa.Jump)
	DoDefer(*ssa.Defer)
	DoGo(*ssa.Go)
	DoMakeChan(*ssa.MakeChan)
	DoAlloc(*ssa.Alloc)
	DoMakeSlice(*ssa.MakeSlice)
	DoMakeMap(*ssa.MakeMap)
	DoRange(*ssa.Range)
	DoNext(*ssa.Next)
	DoFieldAddr(*ssa.FieldAddr)
	DoField(*ssa.Field)
	DoIndexAddr(*ssa.IndexAddr)
	DoIndex(*ssa.Index)
	DoLookup(*ssa.Lookup)
	DoMapUpdate(*ssa.MapUpdate)
	DoTypeAssert(*ssa.TypeAssert)
	DoMakeClosure(*ssa.MakeClosure)
	DoPhi(*ssa.Phi)
	DoSelect(*ssa.Select)
}

An InstrOp must implement methods for ALL possible SSA instructions

type IterativeAnalysis 

type IterativeAnalysis interface {
	InstrOp
	Pre(instruction ssa.Instruction)
	Post(instruction ssa.Instruction)
	NewBlock(block *ssa.BasicBlock)
	ChangedOnEndBlock() bool // ChangedOnEndBlock returns a boolean signaling the information has changed.
}

IterativeAnalysis is an iterative analysis that extends an InstrOp with a function executed each time a new Block is visited, and a function that queries the analysis once the Block has been visited to check whether the analysis information has changed.

type NodeTree 

type NodeTree struct {
	Parent *NodeTree
	Label  dst.Node
}

NodeTree is a tree of dst.Nodes

type PathSensitiveInstrOp 

type PathSensitiveInstrOp interface {
	InstrOp
	NewPath()                 // Called when a new path is inspected.
	EndPath()                 // Called when a path ended.
	NewBlock(*ssa.BasicBlock) // Called when a new Block is entered on a path.
}

PathSensitiveInstrOp is an InstrOp with additional functionality to indicate that the operation is running on a different path

type ValueOp 

type ValueOp interface {
	DoFunction(*ssa.Function)
	DoFreeVar(*ssa.FreeVar)
	DoParameter(*ssa.Parameter)
	DoConst(*ssa.Const)
	DoGlobal(*ssa.Global)
	DoBuiltin(*ssa.Builtin)
	DoAlloc(*ssa.Alloc)
	DoPhi(*ssa.Phi)
	DoCall(*ssa.Call)
	DoBinOp(*ssa.BinOp)
	DoUnOp(*ssa.UnOp)
	DoChangeType(*ssa.ChangeType)
	DoSliceToArrayPointer(*ssa.SliceToArrayPointer)
	DoMakeInterface(*ssa.MakeInterface)
	DoMakeClosure(*ssa.MakeClosure)
	DoMakeMap(*ssa.MakeMap)
	DoMakeChan(*ssa.MakeChan)
	DoMakeSlice(*ssa.MakeSlice)
	DoSlice(*ssa.Slice)
	DoFieldAddr(*ssa.FieldAddr)
	DoField(*ssa.Field)
	DoIndexAddr(*ssa.IndexAddr)
	DoIndex(*ssa.Index)
	DoLookup(*ssa.Lookup)
	DoSelect(*ssa.Select)
	DoRange(*ssa.Range)
	DoNext(*ssa.Next)
	DoTypeAssert(*ssa.TypeAssert)
	DoExtract(*ssa.Extract)
}

A ValueOp contains the methods necessary to implement an exhaustive switch on ssa.Value

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.