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