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 nilness inspects the control-flow graph of an SSA function 6// and reports errors such as nil pointer dereferences and degenerate 7// nil pointer comparisons. 8package nilness 9 10import ( 11 "fmt" 12 "go/token" 13 "go/types" 14 15 "golang.org/x/tools/go/analysis" 16 "golang.org/x/tools/go/analysis/passes/buildssa" 17 "golang.org/x/tools/go/ssa" 18) 19 20const Doc = `check for redundant or impossible nil comparisons 21 22The nilness checker inspects the control-flow graph of each function in 23a package and reports nil pointer dereferences, degenerate nil 24pointers, and panics with nil values. A degenerate comparison is of the form 25x==nil or x!=nil where x is statically known to be nil or non-nil. These are 26often a mistake, especially in control flow related to errors. Panics with nil 27values are checked because they are not detectable by 28 29 if r := recover(); r != nil { 30 31This check reports conditions such as: 32 33 if f == nil { // impossible condition (f is a function) 34 } 35 36and: 37 38 p := &v 39 ... 40 if p != nil { // tautological condition 41 } 42 43and: 44 45 if p == nil { 46 print(*p) // nil dereference 47 } 48 49and: 50 51 if p == nil { 52 panic(p) 53 } 54` 55 56var Analyzer = &analysis.Analyzer{ 57 Name: "nilness", 58 Doc: Doc, 59 Run: run, 60 Requires: []*analysis.Analyzer{buildssa.Analyzer}, 61} 62 63func run(pass *analysis.Pass) (interface{}, error) { 64 ssainput := pass.ResultOf[buildssa.Analyzer].(*buildssa.SSA) 65 for _, fn := range ssainput.SrcFuncs { 66 runFunc(pass, fn) 67 } 68 return nil, nil 69} 70 71func runFunc(pass *analysis.Pass, fn *ssa.Function) { 72 reportf := func(category string, pos token.Pos, format string, args ...interface{}) { 73 pass.Report(analysis.Diagnostic{ 74 Pos: pos, 75 Category: category, 76 Message: fmt.Sprintf(format, args...), 77 }) 78 } 79 80 // notNil reports an error if v is provably nil. 81 notNil := func(stack []fact, instr ssa.Instruction, v ssa.Value, descr string) { 82 if nilnessOf(stack, v) == isnil { 83 reportf("nilderef", instr.Pos(), "nil dereference in "+descr) 84 } 85 } 86 87 // visit visits reachable blocks of the CFG in dominance order, 88 // maintaining a stack of dominating nilness facts. 89 // 90 // By traversing the dom tree, we can pop facts off the stack as 91 // soon as we've visited a subtree. Had we traversed the CFG, 92 // we would need to retain the set of facts for each block. 93 seen := make([]bool, len(fn.Blocks)) // seen[i] means visit should ignore block i 94 var visit func(b *ssa.BasicBlock, stack []fact) 95 visit = func(b *ssa.BasicBlock, stack []fact) { 96 if seen[b.Index] { 97 return 98 } 99 seen[b.Index] = true 100 101 // Report nil dereferences. 102 for _, instr := range b.Instrs { 103 switch instr := instr.(type) { 104 case ssa.CallInstruction: 105 notNil(stack, instr, instr.Common().Value, 106 instr.Common().Description()) 107 case *ssa.FieldAddr: 108 notNil(stack, instr, instr.X, "field selection") 109 case *ssa.IndexAddr: 110 notNil(stack, instr, instr.X, "index operation") 111 case *ssa.MapUpdate: 112 notNil(stack, instr, instr.Map, "map update") 113 case *ssa.Slice: 114 // A nilcheck occurs in ptr[:] iff ptr is a pointer to an array. 115 if _, ok := instr.X.Type().Underlying().(*types.Pointer); ok { 116 notNil(stack, instr, instr.X, "slice operation") 117 } 118 case *ssa.Store: 119 notNil(stack, instr, instr.Addr, "store") 120 case *ssa.TypeAssert: 121 if !instr.CommaOk { 122 notNil(stack, instr, instr.X, "type assertion") 123 } 124 case *ssa.UnOp: 125 if instr.Op == token.MUL { // *X 126 notNil(stack, instr, instr.X, "load") 127 } 128 } 129 } 130 131 // Look for panics with nil value 132 for _, instr := range b.Instrs { 133 switch instr := instr.(type) { 134 case *ssa.Panic: 135 if nilnessOf(stack, instr.X) == isnil { 136 reportf("nilpanic", instr.Pos(), "panic with nil value") 137 } 138 } 139 } 140 141 // For nil comparison blocks, report an error if the condition 142 // is degenerate, and push a nilness fact on the stack when 143 // visiting its true and false successor blocks. 144 if binop, tsucc, fsucc := eq(b); binop != nil { 145 xnil := nilnessOf(stack, binop.X) 146 ynil := nilnessOf(stack, binop.Y) 147 148 if ynil != unknown && xnil != unknown && (xnil == isnil || ynil == isnil) { 149 // Degenerate condition: 150 // the nilness of both operands is known, 151 // and at least one of them is nil. 152 var adj string 153 if (xnil == ynil) == (binop.Op == token.EQL) { 154 adj = "tautological" 155 } else { 156 adj = "impossible" 157 } 158 reportf("cond", binop.Pos(), "%s condition: %s %s %s", adj, xnil, binop.Op, ynil) 159 160 // If tsucc's or fsucc's sole incoming edge is impossible, 161 // it is unreachable. Prune traversal of it and 162 // all the blocks it dominates. 163 // (We could be more precise with full dataflow 164 // analysis of control-flow joins.) 165 var skip *ssa.BasicBlock 166 if xnil == ynil { 167 skip = fsucc 168 } else { 169 skip = tsucc 170 } 171 for _, d := range b.Dominees() { 172 if d == skip && len(d.Preds) == 1 { 173 continue 174 } 175 visit(d, stack) 176 } 177 return 178 } 179 180 // "if x == nil" or "if nil == y" condition; x, y are unknown. 181 if xnil == isnil || ynil == isnil { 182 var newFacts facts 183 if xnil == isnil { 184 // x is nil, y is unknown: 185 // t successor learns y is nil. 186 newFacts = expandFacts(fact{binop.Y, isnil}) 187 } else { 188 // x is nil, y is unknown: 189 // t successor learns x is nil. 190 newFacts = expandFacts(fact{binop.X, isnil}) 191 } 192 193 for _, d := range b.Dominees() { 194 // Successor blocks learn a fact 195 // only at non-critical edges. 196 // (We could do be more precise with full dataflow 197 // analysis of control-flow joins.) 198 s := stack 199 if len(d.Preds) == 1 { 200 if d == tsucc { 201 s = append(s, newFacts...) 202 } else if d == fsucc { 203 s = append(s, newFacts.negate()...) 204 } 205 } 206 visit(d, s) 207 } 208 return 209 } 210 } 211 212 for _, d := range b.Dominees() { 213 visit(d, stack) 214 } 215 } 216 217 // Visit the entry block. No need to visit fn.Recover. 218 if fn.Blocks != nil { 219 visit(fn.Blocks[0], make([]fact, 0, 20)) // 20 is plenty 220 } 221} 222 223// A fact records that a block is dominated 224// by the condition v == nil or v != nil. 225type fact struct { 226 value ssa.Value 227 nilness nilness 228} 229 230func (f fact) negate() fact { return fact{f.value, -f.nilness} } 231 232type nilness int 233 234const ( 235 isnonnil = -1 236 unknown nilness = 0 237 isnil = 1 238) 239 240var nilnessStrings = []string{"non-nil", "unknown", "nil"} 241 242func (n nilness) String() string { return nilnessStrings[n+1] } 243 244// nilnessOf reports whether v is definitely nil, definitely not nil, 245// or unknown given the dominating stack of facts. 246func nilnessOf(stack []fact, v ssa.Value) nilness { 247 switch v := v.(type) { 248 // unwrap ChangeInterface values recursively, to detect if underlying 249 // values have any facts recorded or are otherwise known with regard to nilness. 250 // 251 // This work must be in addition to expanding facts about 252 // ChangeInterfaces during inference/fact gathering because this covers 253 // cases where the nilness of a value is intrinsic, rather than based 254 // on inferred facts, such as a zero value interface variable. That 255 // said, this work alone would only inform us when facts are about 256 // underlying values, rather than outer values, when the analysis is 257 // transitive in both directions. 258 case *ssa.ChangeInterface: 259 if underlying := nilnessOf(stack, v.X); underlying != unknown { 260 return underlying 261 } 262 } 263 264 // Is value intrinsically nil or non-nil? 265 switch v := v.(type) { 266 case *ssa.Alloc, 267 *ssa.FieldAddr, 268 *ssa.FreeVar, 269 *ssa.Function, 270 *ssa.Global, 271 *ssa.IndexAddr, 272 *ssa.MakeChan, 273 *ssa.MakeClosure, 274 *ssa.MakeInterface, 275 *ssa.MakeMap, 276 *ssa.MakeSlice: 277 return isnonnil 278 case *ssa.Const: 279 if v.IsNil() { 280 return isnil 281 } else { 282 return isnonnil 283 } 284 } 285 286 // Search dominating control-flow facts. 287 for _, f := range stack { 288 if f.value == v { 289 return f.nilness 290 } 291 } 292 return unknown 293} 294 295// If b ends with an equality comparison, eq returns the operation and 296// its true (equal) and false (not equal) successors. 297func eq(b *ssa.BasicBlock) (op *ssa.BinOp, tsucc, fsucc *ssa.BasicBlock) { 298 if If, ok := b.Instrs[len(b.Instrs)-1].(*ssa.If); ok { 299 if binop, ok := If.Cond.(*ssa.BinOp); ok { 300 switch binop.Op { 301 case token.EQL: 302 return binop, b.Succs[0], b.Succs[1] 303 case token.NEQ: 304 return binop, b.Succs[1], b.Succs[0] 305 } 306 } 307 } 308 return nil, nil, nil 309} 310 311// expandFacts takes a single fact and returns the set of facts that can be 312// known about it or any of its related values. Some operations, like 313// ChangeInterface, have transitive nilness, such that if you know the 314// underlying value is nil, you also know the value itself is nil, and vice 315// versa. This operation allows callers to match on any of the related values 316// in analyses, rather than just the one form of the value that happend to 317// appear in a comparison. 318// 319// This work must be in addition to unwrapping values within nilnessOf because 320// while this work helps give facts about transitively known values based on 321// inferred facts, the recursive check within nilnessOf covers cases where 322// nilness facts are intrinsic to the underlying value, such as a zero value 323// interface variables. 324// 325// ChangeInterface is the only expansion currently supported, but others, like 326// Slice, could be added. At this time, this tool does not check slice 327// operations in a way this expansion could help. See 328// https://play.golang.org/p/mGqXEp7w4fR for an example. 329func expandFacts(f fact) []fact { 330 ff := []fact{f} 331 332Loop: 333 for { 334 switch v := f.value.(type) { 335 case *ssa.ChangeInterface: 336 f = fact{v.X, f.nilness} 337 ff = append(ff, f) 338 default: 339 break Loop 340 } 341 } 342 343 return ff 344} 345 346type facts []fact 347 348func (ff facts) negate() facts { 349 nn := make([]fact, len(ff)) 350 for i, f := range ff { 351 nn[i] = f.negate() 352 } 353 return nn 354} 355