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  	"golang.org/x/tools/internal/typesinternal"
    23  )
    24  
    25  var Analyzer = &analysis.Analyzer{
    26  	Name:       "ctrlflow",
    27  	Doc:        "build a control-flow graph",
    28  	URL:        "https://pkg.go.dev/golang.org/x/tools/go/analysis/passes/ctrlflow",
    29  	Run:        run,
    30  	ResultType: reflect.TypeFor[*CFGs](),
    31  	FactTypes:  []analysis.Fact{new(noReturn)},
    32  	Requires:   []*analysis.Analyzer{inspect.Analyzer},
    33  }
    34  
    35  // noReturn is a fact indicating that a function does not return.
    36  type noReturn struct{}
    37  
    38  func (*noReturn) AFact() {}
    39  
    40  func (*noReturn) String() string { return "noReturn" }
    41  
    42  // A CFGs holds the control-flow graphs
    43  // for all the functions of the current package.
    44  type CFGs struct {
    45  	defs      map[*ast.Ident]types.Object // from Pass.TypesInfo.Defs
    46  	funcDecls map[*types.Func]*declInfo
    47  	funcLits  map[*ast.FuncLit]*litInfo
    48  	noReturn  map[*types.Func]bool // functions lacking a reachable return statement
    49  	pass      *analysis.Pass       // transient; nil after construction
    50  }
    51  
    52  // NoReturn reports whether the specified control-flow graph cannot return normally.
    53  //
    54  // It is defined for at least all function symbols that appear as the static callee of a
    55  // CallExpr in the current package, even if the callee was imported from a dependency.
    56  //
    57  // The result may incorporate interprocedural information based on induction of
    58  // the "no return" property over the static call graph within the package.
    59  // For example, if f simply calls g and g always calls os.Exit, then both f and g may
    60  // be deemed never to return.
    61  func (c *CFGs) NoReturn(fn *types.Func) bool {
    62  	return c.noReturn[fn]
    63  }
    64  
    65  // CFGs has two maps: funcDecls for named functions and funcLits for
    66  // unnamed ones. Unlike funcLits, the funcDecls map is not keyed by its
    67  // syntax node, *ast.FuncDecl, because callMayReturn needs to do a
    68  // look-up by *types.Func, and you can get from an *ast.FuncDecl to a
    69  // *types.Func but not the other way.
    70  
    71  type declInfo struct {
    72  	decl    *ast.FuncDecl
    73  	cfg     *cfg.CFG // iff decl.Body != nil
    74  	started bool     // to break cycles
    75  }
    76  
    77  type litInfo struct {
    78  	cfg      *cfg.CFG
    79  	noReturn bool // (currently unused)
    80  }
    81  
    82  // FuncDecl returns the control-flow graph for a named function.
    83  // It returns nil if decl.Body==nil.
    84  func (c *CFGs) FuncDecl(decl *ast.FuncDecl) *cfg.CFG {
    85  	if decl.Body == nil {
    86  		return nil
    87  	}
    88  	fn := c.defs[decl.Name].(*types.Func)
    89  	return c.funcDecls[fn].cfg
    90  }
    91  
    92  // FuncLit returns the control-flow graph for a literal function.
    93  func (c *CFGs) FuncLit(lit *ast.FuncLit) *cfg.CFG {
    94  	return c.funcLits[lit].cfg
    95  }
    96  
    97  func run(pass *analysis.Pass) (any, error) {
    98  	inspect := pass.ResultOf[inspect.Analyzer].(*inspector.Inspector)
    99  
   100  	// Because CFG construction consumes and produces noReturn
   101  	// facts, CFGs for exported FuncDecls must be built before 'run'
   102  	// returns; we cannot construct them lazily.
   103  	// (We could build CFGs for FuncLits lazily,
   104  	// but the benefit is marginal.)
   105  
   106  	// Pass 1. Map types.Funcs to ast.FuncDecls in this package.
   107  	funcDecls := make(map[*types.Func]*declInfo) // functions and methods
   108  	funcLits := make(map[*ast.FuncLit]*litInfo)
   109  
   110  	var decls []*types.Func // keys(funcDecls), in order
   111  	var lits []*ast.FuncLit // keys(funcLits), in order
   112  
   113  	nodeFilter := []ast.Node{
   114  		(*ast.FuncDecl)(nil),
   115  		(*ast.FuncLit)(nil),
   116  	}
   117  	inspect.Preorder(nodeFilter, func(n ast.Node) {
   118  		switch n := n.(type) {
   119  		case *ast.FuncDecl:
   120  			// Type information may be incomplete.
   121  			if fn, ok := pass.TypesInfo.Defs[n.Name].(*types.Func); ok {
   122  				funcDecls[fn] = &declInfo{decl: n}
   123  				decls = append(decls, fn)
   124  			}
   125  		case *ast.FuncLit:
   126  			funcLits[n] = new(litInfo)
   127  			lits = append(lits, n)
   128  		}
   129  	})
   130  
   131  	c := &CFGs{
   132  		defs:      pass.TypesInfo.Defs,
   133  		funcDecls: funcDecls,
   134  		funcLits:  funcLits,
   135  		noReturn:  make(map[*types.Func]bool),
   136  		pass:      pass,
   137  	}
   138  
   139  	// Pass 2. Build CFGs.
   140  
   141  	// Build CFGs for named functions.
   142  	// Cycles in the static call graph are broken
   143  	// arbitrarily but deterministically.
   144  	// We create noReturn facts as discovered.
   145  	for _, fn := range decls {
   146  		c.buildDecl(fn, funcDecls[fn])
   147  	}
   148  
   149  	// Build CFGs for literal functions.
   150  	// These aren't relevant to facts (since they aren't named)
   151  	// but are required for the CFGs.FuncLit API.
   152  	for _, lit := range lits {
   153  		li := funcLits[lit]
   154  		if li.cfg == nil {
   155  			li.cfg = cfg.New(lit.Body, c.callMayReturn)
   156  			if li.cfg.NoReturn() {
   157  				li.noReturn = true
   158  			}
   159  		}
   160  	}
   161  
   162  	// All CFGs are now built.
   163  	c.pass = nil
   164  
   165  	return c, nil
   166  }
   167  
   168  // di.cfg may be nil on return.
   169  func (c *CFGs) buildDecl(fn *types.Func, di *declInfo) {
   170  	// buildDecl may call itself recursively for the same function,
   171  	// because cfg.New is passed the callMayReturn method, which
   172  	// builds the CFG of the callee, leading to recursion.
   173  	// The buildDecl call tree thus resembles the static call graph.
   174  	// We mark each node when we start working on it to break cycles.
   175  
   176  	if di.started {
   177  		return // break cycle
   178  	}
   179  	di.started = true
   180  
   181  	noreturn, known := knownIntrinsic(fn)
   182  	if !known {
   183  		if di.decl.Body != nil {
   184  			di.cfg = cfg.New(di.decl.Body, c.callMayReturn)
   185  			if di.cfg.NoReturn() {
   186  				noreturn = true
   187  			}
   188  		}
   189  	}
   190  	if noreturn {
   191  		c.pass.ExportObjectFact(fn, new(noReturn))
   192  		c.noReturn[fn] = true
   193  	}
   194  
   195  	// debugging
   196  	if false {
   197  		log.Printf("CFG for %s:\n%s (noreturn=%t)\n", fn, di.cfg.Format(c.pass.Fset), noreturn)
   198  	}
   199  }
   200  
   201  // callMayReturn reports whether the called function may return.
   202  // It is passed to the CFG builder.
   203  func (c *CFGs) callMayReturn(call *ast.CallExpr) (r bool) {
   204  	if id, ok := call.Fun.(*ast.Ident); ok && c.pass.TypesInfo.Uses[id] == panicBuiltin {
   205  		return false // panic never returns
   206  	}
   207  
   208  	// Is this a static call? Also includes static functions
   209  	// parameterized by a type. Such functions may or may not
   210  	// return depending on the parameter type, but in some
   211  	// cases the answer is definite. We let ctrlflow figure
   212  	// that out.
   213  	fn := typeutil.StaticCallee(c.pass.TypesInfo, call)
   214  	if fn == nil {
   215  		return true // callee not statically known; be conservative
   216  	}
   217  
   218  	// Function or method declared in this package?
   219  	if di, ok := c.funcDecls[fn]; ok {
   220  		c.buildDecl(fn, di)
   221  		return !c.noReturn[fn]
   222  	}
   223  
   224  	// Not declared in this package.
   225  	// Is there a fact from another package?
   226  	if c.pass.ImportObjectFact(fn, new(noReturn)) {
   227  		c.noReturn[fn] = true
   228  		return false
   229  	}
   230  
   231  	return true
   232  }
   233  
   234  var panicBuiltin = types.Universe.Lookup("panic").(*types.Builtin)
   235  
   236  // knownIntrinsic reports whether a function intrinsically never
   237  // returns because it stops execution of the calling thread, or does
   238  // in fact return, contrary to its apparent body, because it is
   239  // handled specially by the compiler.
   240  //
   241  // It is the base case in the recursion.
   242  func knownIntrinsic(fn *types.Func) (noreturn, known bool) {
   243  	// Add functions here as the need arises, but don't allocate memory.
   244  
   245  	// Functions known intrinsically never to return.
   246  	if typesinternal.IsFunctionNamed(fn, "syscall", "Exit", "ExitProcess", "ExitThread") ||
   247  		typesinternal.IsFunctionNamed(fn, "runtime", "Goexit", "fatalthrow", "fatalpanic", "exit") ||
   248  		// Following staticcheck (see go/ir/exits.go) we include functions
   249  		// in several popular logging packages whose no-return status is
   250  		// beyond the analysis to infer.
   251  		// TODO(adonovan): make this list extensible.
   252  		typesinternal.IsMethodNamed(fn, "go.uber.org/zap", "Logger", "Fatal", "Panic") ||
   253  		typesinternal.IsMethodNamed(fn, "go.uber.org/zap", "SugaredLogger", "Fatal", "Fatalw", "Fatalf", "Panic", "Panicw", "Panicf") ||
   254  		typesinternal.IsMethodNamed(fn, "github.com/sirupsen/logrus", "Logger", "Exit", "Panic", "Panicf", "Panicln") ||
   255  		typesinternal.IsMethodNamed(fn, "github.com/sirupsen/logrus", "Entry", "Panicf", "Panicln") ||
   256  		typesinternal.IsFunctionNamed(fn, "k8s.io/klog", "Exit", "ExitDepth", "Exitf", "Exitln", "Fatal", "FatalDepth", "Fatalf", "Fatalln") ||
   257  		typesinternal.IsFunctionNamed(fn, "k8s.io/klog/v2", "Exit", "ExitDepth", "Exitf", "Exitln", "Fatal", "FatalDepth", "Fatalf", "Fatalln") {
   258  		return true, true
   259  	}
   260  
   261  	// Compiler intrinsics known to return, contrary to
   262  	// what analysis of the function body would conclude.
   263  	//
   264  	// Not all such intrinsics must be listed here: ctrlflow
   265  	// considers any function called for its value--such as
   266  	// crypto/internal/constanttime.bool2Uint8--to potentially
   267  	// return; only functions called as a statement, for effects,
   268  	// are no-return candidates.
   269  	//
   270  	// Unfortunately this does sometimes mean peering into internals.
   271  	// Where possible, use the nearest enclosing public API function.
   272  	if typesinternal.IsFunctionNamed(fn, "internal/abi", "EscapeNonString") ||
   273  		typesinternal.IsFunctionNamed(fn, "hash/maphash", "Comparable") {
   274  		return false, true
   275  	}
   276  
   277  	return // unknown
   278  }
   279
View as plain text