+++ /dev/null
-// Copyright 2018 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Package ctrlflow is an analysis that provides a syntactic
-// control-flow graph (CFG) for the body of a function.
-// It records whether a function cannot return.
-// By itself, it does not report any diagnostics.
-package ctrlflow
-
-import (
- "go/ast"
- "go/types"
- "log"
- "reflect"
-
- "golang.org/x/tools/go/analysis"
- "golang.org/x/tools/go/analysis/passes/inspect"
- "golang.org/x/tools/go/ast/inspector"
- "golang.org/x/tools/go/cfg"
- "golang.org/x/tools/go/types/typeutil"
-)
-
-var Analyzer = &analysis.Analyzer{
- Name: "ctrlflow",
- Doc: "build a control-flow graph",
- Run: run,
- ResultType: reflect.TypeOf(new(CFGs)),
- FactTypes: []analysis.Fact{new(noReturn)},
- Requires: []*analysis.Analyzer{inspect.Analyzer},
-}
-
-// noReturn is a fact indicating that a function does not return.
-type noReturn struct{}
-
-func (*noReturn) AFact() {}
-
-func (*noReturn) String() string { return "noReturn" }
-
-// A CFGs holds the control-flow graphs
-// for all the functions of the current package.
-type CFGs struct {
- defs map[*ast.Ident]types.Object // from Pass.TypesInfo.Defs
- funcDecls map[*types.Func]*declInfo
- funcLits map[*ast.FuncLit]*litInfo
- pass *analysis.Pass // transient; nil after construction
-}
-
-// CFGs has two maps: funcDecls for named functions and funcLits for
-// unnamed ones. Unlike funcLits, the funcDecls map is not keyed by its
-// syntax node, *ast.FuncDecl, because callMayReturn needs to do a
-// look-up by *types.Func, and you can get from an *ast.FuncDecl to a
-// *types.Func but not the other way.
-
-type declInfo struct {
- decl *ast.FuncDecl
- cfg *cfg.CFG // iff decl.Body != nil
- started bool // to break cycles
- noReturn bool
-}
-
-type litInfo struct {
- cfg *cfg.CFG
- noReturn bool
-}
-
-// FuncDecl returns the control-flow graph for a named function.
-// It returns nil if decl.Body==nil.
-func (c *CFGs) FuncDecl(decl *ast.FuncDecl) *cfg.CFG {
- if decl.Body == nil {
- return nil
- }
- fn := c.defs[decl.Name].(*types.Func)
- return c.funcDecls[fn].cfg
-}
-
-// FuncLit returns the control-flow graph for a literal function.
-func (c *CFGs) FuncLit(lit *ast.FuncLit) *cfg.CFG {
- return c.funcLits[lit].cfg
-}
-
-func run(pass *analysis.Pass) (interface{}, error) {
- inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
-
- // Because CFG construction consumes and produces noReturn
- // facts, CFGs for exported FuncDecls must be built before 'run'
- // returns; we cannot construct them lazily.
- // (We could build CFGs for FuncLits lazily,
- // but the benefit is marginal.)
-
- // Pass 1. Map types.Funcs to ast.FuncDecls in this package.
- funcDecls := make(map[*types.Func]*declInfo) // functions and methods
- funcLits := make(map[*ast.FuncLit]*litInfo)
-
- var decls []*types.Func // keys(funcDecls), in order
- var lits []*ast.FuncLit // keys(funcLits), in order
-
- nodeFilter := []ast.Node{
- (*ast.FuncDecl)(nil),
- (*ast.FuncLit)(nil),
- }
- inspect.Preorder(nodeFilter, func(n ast.Node) {
- switch n := n.(type) {
- case *ast.FuncDecl:
- // Type information may be incomplete.
- if fn, ok := pass.TypesInfo.Defs[n.Name].(*types.Func); ok {
- funcDecls[fn] = &declInfo{decl: n}
- decls = append(decls, fn)
- }
- case *ast.FuncLit:
- funcLits[n] = new(litInfo)
- lits = append(lits, n)
- }
- })
-
- c := &CFGs{
- defs: pass.TypesInfo.Defs,
- funcDecls: funcDecls,
- funcLits: funcLits,
- pass: pass,
- }
-
- // Pass 2. Build CFGs.
-
- // Build CFGs for named functions.
- // Cycles in the static call graph are broken
- // arbitrarily but deterministically.
- // We create noReturn facts as discovered.
- for _, fn := range decls {
- c.buildDecl(fn, funcDecls[fn])
- }
-
- // Build CFGs for literal functions.
- // These aren't relevant to facts (since they aren't named)
- // but are required for the CFGs.FuncLit API.
- for _, lit := range lits {
- li := funcLits[lit]
- if li.cfg == nil {
- li.cfg = cfg.New(lit.Body, c.callMayReturn)
- if !hasReachableReturn(li.cfg) {
- li.noReturn = true
- }
- }
- }
-
- // All CFGs are now built.
- c.pass = nil
-
- return c, nil
-}
-
-// di.cfg may be nil on return.
-func (c *CFGs) buildDecl(fn *types.Func, di *declInfo) {
- // buildDecl may call itself recursively for the same function,
- // because cfg.New is passed the callMayReturn method, which
- // builds the CFG of the callee, leading to recursion.
- // The buildDecl call tree thus resembles the static call graph.
- // We mark each node when we start working on it to break cycles.
-
- if !di.started { // break cycle
- di.started = true
-
- if isIntrinsicNoReturn(fn) {
- di.noReturn = true
- }
- if di.decl.Body != nil {
- di.cfg = cfg.New(di.decl.Body, c.callMayReturn)
- if !hasReachableReturn(di.cfg) {
- di.noReturn = true
- }
- }
- if di.noReturn {
- c.pass.ExportObjectFact(fn, new(noReturn))
- }
-
- // debugging
- if false {
- log.Printf("CFG for %s:\n%s (noreturn=%t)\n", fn, di.cfg.Format(c.pass.Fset), di.noReturn)
- }
- }
-}
-
-// callMayReturn reports whether the called function may return.
-// It is passed to the CFG builder.
-func (c *CFGs) callMayReturn(call *ast.CallExpr) (r bool) {
- if id, ok := call.Fun.(*ast.Ident); ok && c.pass.TypesInfo.Uses[id] == panicBuiltin {
- return false // panic never returns
- }
-
- // Is this a static call?
- fn := typeutil.StaticCallee(c.pass.TypesInfo, call)
- if fn == nil {
- return true // callee not statically known; be conservative
- }
-
- // Function or method declared in this package?
- if di, ok := c.funcDecls[fn]; ok {
- c.buildDecl(fn, di)
- return !di.noReturn
- }
-
- // Not declared in this package.
- // Is there a fact from another package?
- return !c.pass.ImportObjectFact(fn, new(noReturn))
-}
-
-var panicBuiltin = types.Universe.Lookup("panic").(*types.Builtin)
-
-func hasReachableReturn(g *cfg.CFG) bool {
- for _, b := range g.Blocks {
- if b.Live && b.Return() != nil {
- return true
- }
- }
- return false
-}
-
-// isIntrinsicNoReturn reports whether a function intrinsically never
-// returns because it stops execution of the calling thread.
-// It is the base case in the recursion.
-func isIntrinsicNoReturn(fn *types.Func) bool {
- // Add functions here as the need arises, but don't allocate memory.
- path, name := fn.Pkg().Path(), fn.Name()
- return path == "syscall" && (name == "Exit" || name == "ExitProcess" || name == "ExitThread") ||
- path == "runtime" && name == "Goexit"
-}
projects / dotfiles / .git / blobdiff