.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/analysis/passes/ctrlflow/ctrlflow.go

   1 // Copyright 2018 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Package ctrlflow is an analysis that provides a syntactic
   6 // control-flow graph (CFG) for the body of a function.
   7 // It records whether a function cannot return.
   8 // By itself, it does not report any diagnostics.
   9 package ctrlflow
  10
  11 import (
  12         "go/ast"
  13         "go/types"
  14         "log"
  15         "reflect"
  16
  17         "golang.org/x/tools/go/analysis"
  18         "golang.org/x/tools/go/analysis/passes/inspect"
  19         "golang.org/x/tools/go/ast/inspector"
  20         "golang.org/x/tools/go/cfg"
  21         "golang.org/x/tools/go/types/typeutil"
  22 )
  23
  24 var Analyzer = &analysis.Analyzer{
  25         Name:       "ctrlflow",
  26         Doc:        "build a control-flow graph",
  27         Run:        run,
  28         ResultType: reflect.TypeOf(new(CFGs)),
  29         FactTypes:  []analysis.Fact{new(noReturn)},
  30         Requires:   []*analysis.Analyzer{inspect.Analyzer},
  31 }
  32
  33 // noReturn is a fact indicating that a function does not return.
  34 type noReturn struct{}
  35
  36 func (*noReturn) AFact() {}
  37
  38 func (*noReturn) String() string { return "noReturn" }
  39
  40 // A CFGs holds the control-flow graphs
  41 // for all the functions of the current package.
  42 type CFGs struct {
  43         defs      map[*ast.Ident]types.Object // from Pass.TypesInfo.Defs
  44         funcDecls map[*types.Func]*declInfo
  45         funcLits  map[*ast.FuncLit]*litInfo
  46         pass      *analysis.Pass // transient; nil after construction
  47 }
  48
  49 // CFGs has two maps: funcDecls for named functions and funcLits for
  50 // unnamed ones. Unlike funcLits, the funcDecls map is not keyed by its
  51 // syntax node, *ast.FuncDecl, because callMayReturn needs to do a
  52 // look-up by *types.Func, and you can get from an *ast.FuncDecl to a
  53 // *types.Func but not the other way.
  54
  55 type declInfo struct {
  56         decl     *ast.FuncDecl
  57         cfg      *cfg.CFG // iff decl.Body != nil
  58         started  bool     // to break cycles
  59         noReturn bool
  60 }
  61
  62 type litInfo struct {
  63         cfg      *cfg.CFG
  64         noReturn bool
  65 }
  66
  67 // FuncDecl returns the control-flow graph for a named function.
  68 // It returns nil if decl.Body==nil.
  69 func (c *CFGs) FuncDecl(decl *ast.FuncDecl) *cfg.CFG {
  70         if decl.Body == nil {
  71                 return nil
  72         }
  73         fn := c.defs[decl.Name].(*types.Func)
  74         return c.funcDecls[fn].cfg
  75 }
  76
  77 // FuncLit returns the control-flow graph for a literal function.
  78 func (c *CFGs) FuncLit(lit *ast.FuncLit) *cfg.CFG {
  79         return c.funcLits[lit].cfg
  80 }
  81
  82 func run(pass *analysis.Pass) (interface{}, error) {
  83         inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
  84
  85         // Because CFG construction consumes and produces noReturn
  86         // facts, CFGs for exported FuncDecls must be built before 'run'
  87         // returns; we cannot construct them lazily.
  88         // (We could build CFGs for FuncLits lazily,
  89         // but the benefit is marginal.)
  90
  91         // Pass 1. Map types.Funcs to ast.FuncDecls in this package.
  92         funcDecls := make(map[*types.Func]*declInfo) // functions and methods
  93         funcLits := make(map[*ast.FuncLit]*litInfo)
  94
  95         var decls []*types.Func // keys(funcDecls), in order
  96         var lits []*ast.FuncLit // keys(funcLits), in order
  97
  98         nodeFilter := []ast.Node{
  99                 (*ast.FuncDecl)(nil),
 100                 (*ast.FuncLit)(nil),
 101         }
 102         inspect.Preorder(nodeFilter, func(n ast.Node) {
 103                 switch n := n.(type) {
 104                 case *ast.FuncDecl:
 105                         // Type information may be incomplete.
 106                         if fn, ok := pass.TypesInfo.Defs[n.Name].(*types.Func); ok {
 107                                 funcDecls[fn] = &declInfo{decl: n}
 108                                 decls = append(decls, fn)
 109                         }
 110                 case *ast.FuncLit:
 111                         funcLits[n] = new(litInfo)
 112                         lits = append(lits, n)
 113                 }
 114         })
 115
 116         c := &CFGs{
 117                 defs:      pass.TypesInfo.Defs,
 118                 funcDecls: funcDecls,
 119                 funcLits:  funcLits,
 120                 pass:      pass,
 121         }
 122
 123         // Pass 2. Build CFGs.
 124
 125         // Build CFGs for named functions.
 126         // Cycles in the static call graph are broken
 127         // arbitrarily but deterministically.
 128         // We create noReturn facts as discovered.
 129         for _, fn := range decls {
 130                 c.buildDecl(fn, funcDecls[fn])
 131         }
 132
 133         // Build CFGs for literal functions.
 134         // These aren't relevant to facts (since they aren't named)
 135         // but are required for the CFGs.FuncLit API.
 136         for _, lit := range lits {
 137                 li := funcLits[lit]
 138                 if li.cfg == nil {
 139                         li.cfg = cfg.New(lit.Body, c.callMayReturn)
 140                         if !hasReachableReturn(li.cfg) {
 141                                 li.noReturn = true
 142                         }
 143                 }
 144         }
 145
 146         // All CFGs are now built.
 147         c.pass = nil
 148
 149         return c, nil
 150 }
 151
 152 // di.cfg may be nil on return.
 153 func (c *CFGs) buildDecl(fn *types.Func, di *declInfo) {
 154         // buildDecl may call itself recursively for the same function,
 155         // because cfg.New is passed the callMayReturn method, which
 156         // builds the CFG of the callee, leading to recursion.
 157         // The buildDecl call tree thus resembles the static call graph.
 158         // We mark each node when we start working on it to break cycles.
 159
 160         if !di.started { // break cycle
 161                 di.started = true
 162
 163                 if isIntrinsicNoReturn(fn) {
 164                         di.noReturn = true
 165                 }
 166                 if di.decl.Body != nil {
 167                         di.cfg = cfg.New(di.decl.Body, c.callMayReturn)
 168                         if !hasReachableReturn(di.cfg) {
 169                                 di.noReturn = true
 170                         }
 171                 }
 172                 if di.noReturn {
 173                         c.pass.ExportObjectFact(fn, new(noReturn))
 174                 }
 175
 176                 // debugging
 177                 if false {
 178                         log.Printf("CFG for %s:\n%s (noreturn=%t)\n", fn, di.cfg.Format(c.pass.Fset), di.noReturn)
 179                 }
 180         }
 181 }
 182
 183 // callMayReturn reports whether the called function may return.
 184 // It is passed to the CFG builder.
 185 func (c *CFGs) callMayReturn(call *ast.CallExpr) (r bool) {
 186         if id, ok := call.Fun.(*ast.Ident); ok && c.pass.TypesInfo.Uses[id] == panicBuiltin {
 187                 return false // panic never returns
 188         }
 189
 190         // Is this a static call?
 191         fn := typeutil.StaticCallee(c.pass.TypesInfo, call)
 192         if fn == nil {
 193                 return true // callee not statically known; be conservative
 194         }
 195
 196         // Function or method declared in this package?
 197         if di, ok := c.funcDecls[fn]; ok {
 198                 c.buildDecl(fn, di)
 199                 return !di.noReturn
 200         }
 201
 202         // Not declared in this package.
 203         // Is there a fact from another package?
 204         return !c.pass.ImportObjectFact(fn, new(noReturn))
 205 }
 206
 207 var panicBuiltin = types.Universe.Lookup("panic").(*types.Builtin)
 208
 209 func hasReachableReturn(g *cfg.CFG) bool {
 210         for _, b := range g.Blocks {
 211                 if b.Live && b.Return() != nil {
 212                         return true
 213                 }
 214         }
 215         return false
 216 }
 217
 218 // isIntrinsicNoReturn reports whether a function intrinsically never
 219 // returns because it stops execution of the calling thread.
 220 // It is the base case in the recursion.
 221 func isIntrinsicNoReturn(fn *types.Func) bool {
 222         // Add functions here as the need arises, but don't allocate memory.
 223         path, name := fn.Pkg().Path(), fn.Name()
 224         return path == "syscall" && (name == "Exit" || name == "ExitProcess" || name == "ExitThread") ||
 225                 path == "runtime" && name == "Goexit"
 226 }