Source file src/pkg/cmd/vendor/golang.org/x/tools/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				fn := pass.TypesInfo.Defs[n.Name].(*types.Func)
   106				funcDecls[fn] = &declInfo{decl: n}
   107				decls = append(decls, fn)
   108	
   109			case *ast.FuncLit:
   110				funcLits[n] = new(litInfo)
   111				lits = append(lits, n)
   112			}
   113		})
   114	
   115		c := &CFGs{
   116			defs:      pass.TypesInfo.Defs,
   117			funcDecls: funcDecls,
   118			funcLits:  funcLits,
   119			pass:      pass,
   120		}
   121	
   122		// Pass 2. Build CFGs.
   123	
   124		// Build CFGs for named functions.
   125		// Cycles in the static call graph are broken
   126		// arbitrarily but deterministically.
   127		// We create noReturn facts as discovered.
   128		for _, fn := range decls {
   129			c.buildDecl(fn, funcDecls[fn])
   130		}
   131	
   132		// Build CFGs for literal functions.
   133		// These aren't relevant to facts (since they aren't named)
   134		// but are required for the CFGs.FuncLit API.
   135		for _, lit := range lits {
   136			li := funcLits[lit]
   137			if li.cfg == nil {
   138				li.cfg = cfg.New(lit.Body, c.callMayReturn)
   139				if !hasReachableReturn(li.cfg) {
   140					li.noReturn = true
   141				}
   142			}
   143		}
   144	
   145		// All CFGs are now built.
   146		c.pass = nil
   147	
   148		return c, nil
   149	}
   150	
   151	// di.cfg may be nil on return.
   152	func (c *CFGs) buildDecl(fn *types.Func, di *declInfo) {
   153		// buildDecl may call itself recursively for the same function,
   154		// because cfg.New is passed the callMayReturn method, which
   155		// builds the CFG of the callee, leading to recursion.
   156		// The buildDecl call tree thus resembles the static call graph.
   157		// We mark each node when we start working on it to break cycles.
   158	
   159		if !di.started { // break cycle
   160			di.started = true
   161	
   162			if isIntrinsicNoReturn(fn) {
   163				di.noReturn = true
   164			}
   165			if di.decl.Body != nil {
   166				di.cfg = cfg.New(di.decl.Body, c.callMayReturn)
   167				if !hasReachableReturn(di.cfg) {
   168					di.noReturn = true
   169				}
   170			}
   171			if di.noReturn {
   172				c.pass.ExportObjectFact(fn, new(noReturn))
   173			}
   174	
   175			// debugging
   176			if false {
   177				log.Printf("CFG for %s:\n%s (noreturn=%t)\n", fn, di.cfg.Format(c.pass.Fset), di.noReturn)
   178			}
   179		}
   180	}
   181	
   182	// callMayReturn reports whether the called function may return.
   183	// It is passed to the CFG builder.
   184	func (c *CFGs) callMayReturn(call *ast.CallExpr) (r bool) {
   185		if id, ok := call.Fun.(*ast.Ident); ok && c.pass.TypesInfo.Uses[id] == panicBuiltin {
   186			return false // panic never returns
   187		}
   188	
   189		// Is this a static call?
   190		fn := typeutil.StaticCallee(c.pass.TypesInfo, call)
   191		if fn == nil {
   192			return true // callee not statically known; be conservative
   193		}
   194	
   195		// Function or method declared in this package?
   196		if di, ok := c.funcDecls[fn]; ok {
   197			c.buildDecl(fn, di)
   198			return !di.noReturn
   199		}
   200	
   201		// Not declared in this package.
   202		// Is there a fact from another package?
   203		return !c.pass.ImportObjectFact(fn, new(noReturn))
   204	}
   205	
   206	var panicBuiltin = types.Universe.Lookup("panic").(*types.Builtin)
   207	
   208	func hasReachableReturn(g *cfg.CFG) bool {
   209		for _, b := range g.Blocks {
   210			if b.Live && b.Return() != nil {
   211				return true
   212			}
   213		}
   214		return false
   215	}
   216	
   217	// isIntrinsicNoReturn reports whether a function intrinsically never
   218	// returns because it stops execution of the calling thread.
   219	// It is the base case in the recursion.
   220	func isIntrinsicNoReturn(fn *types.Func) bool {
   221		// Add functions here as the need arises, but don't allocate memory.
   222		path, name := fn.Pkg().Path(), fn.Name()
   223		return path == "syscall" && (name == "Exit" || name == "ExitProcess" || name == "ExitThread") ||
   224			path == "runtime" && name == "Goexit"
   225	}
   226	

View as plain text