.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/analysis/passes/nilness/nilness.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 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.
   8 package nilness
   9
  10 import (
  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
  20 const Doc = `check for redundant or impossible nil comparisons
  21
  22 The nilness checker inspects the control-flow graph of each function in
  23 a package and reports nil pointer dereferences, degenerate nil
  24 pointers, and panics with nil values. A degenerate comparison is of the form
  25 x==nil or x!=nil where x is statically known to be nil or non-nil. These are
  26 often a mistake, especially in control flow related to errors. Panics with nil
  27 values are checked because they are not detectable by
  28
  29         if r := recover(); r != nil {
  30
  31 This check reports conditions such as:
  32
  33         if f == nil { // impossible condition (f is a function)
  34         }
  35
  36 and:
  37
  38         p := &v
  39         ...
  40         if p != nil { // tautological condition
  41         }
  42
  43 and:
  44
  45         if p == nil {
  46                 print(*p) // nil dereference
  47         }
  48
  49 and:
  50
  51         if p == nil {
  52                 panic(p)
  53         }
  54 `
  55
  56 var Analyzer = &analysis.Analyzer{
  57         Name:     "nilness",
  58         Doc:      Doc,
  59         Run:      run,
  60         Requires: []*analysis.Analyzer{buildssa.Analyzer},
  61 }
  62
  63 func 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
  71 func 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.
 225 type fact struct {
 226         value   ssa.Value
 227         nilness nilness
 228 }
 229
 230 func (f fact) negate() fact { return fact{f.value, -f.nilness} }
 231
 232 type nilness int
 233
 234 const (
 235         isnonnil         = -1
 236         unknown  nilness = 0
 237         isnil            = 1
 238 )
 239
 240 var nilnessStrings = []string{"non-nil", "unknown", "nil"}
 241
 242 func (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.
 246 func 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.
 297 func 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.
 329 func expandFacts(f fact) []fact {
 330         ff := []fact{f}
 331
 332 Loop:
 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
 346 type facts []fact
 347
 348 func (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 }