.config/coc/extensions/coc-go-data/tools/pkg/mod/honnef.co/go/tools@v0.0.1-2020.1.5/ir/sanity.go

   1 // Copyright 2013 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 ir
   6
   7 // An optional pass for sanity-checking invariants of the IR representation.
   8 // Currently it checks CFG invariants but little at the instruction level.
   9
  10 import (
  11         "fmt"
  12         "go/types"
  13         "io"
  14         "os"
  15         "strings"
  16 )
  17
  18 type sanity struct {
  19         reporter io.Writer
  20         fn       *Function
  21         block    *BasicBlock
  22         instrs   map[Instruction]struct{}
  23         insane   bool
  24 }
  25
  26 // sanityCheck performs integrity checking of the IR representation
  27 // of the function fn and returns true if it was valid.  Diagnostics
  28 // are written to reporter if non-nil, os.Stderr otherwise.  Some
  29 // diagnostics are only warnings and do not imply a negative result.
  30 //
  31 // Sanity-checking is intended to facilitate the debugging of code
  32 // transformation passes.
  33 //
  34 func sanityCheck(fn *Function, reporter io.Writer) bool {
  35         if reporter == nil {
  36                 reporter = os.Stderr
  37         }
  38         return (&sanity{reporter: reporter}).checkFunction(fn)
  39 }
  40
  41 // mustSanityCheck is like sanityCheck but panics instead of returning
  42 // a negative result.
  43 //
  44 func mustSanityCheck(fn *Function, reporter io.Writer) {
  45         if !sanityCheck(fn, reporter) {
  46                 fn.WriteTo(os.Stderr)
  47                 panic("SanityCheck failed")
  48         }
  49 }
  50
  51 func (s *sanity) diagnostic(prefix, format string, args ...interface{}) {
  52         fmt.Fprintf(s.reporter, "%s: function %s", prefix, s.fn)
  53         if s.block != nil {
  54                 fmt.Fprintf(s.reporter, ", block %s", s.block)
  55         }
  56         io.WriteString(s.reporter, ": ")
  57         fmt.Fprintf(s.reporter, format, args...)
  58         io.WriteString(s.reporter, "\n")
  59 }
  60
  61 func (s *sanity) errorf(format string, args ...interface{}) {
  62         s.insane = true
  63         s.diagnostic("Error", format, args...)
  64 }
  65
  66 func (s *sanity) warnf(format string, args ...interface{}) {
  67         s.diagnostic("Warning", format, args...)
  68 }
  69
  70 // findDuplicate returns an arbitrary basic block that appeared more
  71 // than once in blocks, or nil if all were unique.
  72 func findDuplicate(blocks []*BasicBlock) *BasicBlock {
  73         if len(blocks) < 2 {
  74                 return nil
  75         }
  76         if blocks[0] == blocks[1] {
  77                 return blocks[0]
  78         }
  79         // Slow path:
  80         m := make(map[*BasicBlock]bool)
  81         for _, b := range blocks {
  82                 if m[b] {
  83                         return b
  84                 }
  85                 m[b] = true
  86         }
  87         return nil
  88 }
  89
  90 func (s *sanity) checkInstr(idx int, instr Instruction) {
  91         switch instr := instr.(type) {
  92         case *If, *Jump, *Return, *Panic, *Unreachable, *ConstantSwitch:
  93                 s.errorf("control flow instruction not at end of block")
  94         case *Sigma:
  95                 if idx > 0 {
  96                         prev := s.block.Instrs[idx-1]
  97                         if _, ok := prev.(*Sigma); !ok {
  98                                 s.errorf("Sigma instruction follows a non-Sigma: %T", prev)
  99                         }
 100                 }
 101         case *Phi:
 102                 if idx == 0 {
 103                         // It suffices to apply this check to just the first phi node.
 104                         if dup := findDuplicate(s.block.Preds); dup != nil {
 105                                 s.errorf("phi node in block with duplicate predecessor %s", dup)
 106                         }
 107                 } else {
 108                         prev := s.block.Instrs[idx-1]
 109                         switch prev.(type) {
 110                         case *Phi, *Sigma:
 111                         default:
 112                                 s.errorf("Phi instruction follows a non-Phi, non-Sigma: %T", prev)
 113                         }
 114                 }
 115                 if ne, np := len(instr.Edges), len(s.block.Preds); ne != np {
 116                         s.errorf("phi node has %d edges but %d predecessors", ne, np)
 117
 118                 } else {
 119                         for i, e := range instr.Edges {
 120                                 if e == nil {
 121                                         s.errorf("phi node '%v' has no value for edge #%d from %s", instr, i, s.block.Preds[i])
 122                                 }
 123                         }
 124                 }
 125
 126         case *Alloc:
 127                 if !instr.Heap {
 128                         found := false
 129                         for _, l := range s.fn.Locals {
 130                                 if l == instr {
 131                                         found = true
 132                                         break
 133                                 }
 134                         }
 135                         if !found {
 136                                 s.errorf("local alloc %s = %s does not appear in Function.Locals", instr.Name(), instr)
 137                         }
 138                 }
 139
 140         case *BinOp:
 141         case *Call:
 142         case *ChangeInterface:
 143         case *ChangeType:
 144         case *Convert:
 145                 if _, ok := instr.X.Type().Underlying().(*types.Basic); !ok {
 146                         if _, ok := instr.Type().Underlying().(*types.Basic); !ok {
 147                                 s.errorf("convert %s -> %s: at least one type must be basic", instr.X.Type(), instr.Type())
 148                         }
 149                 }
 150
 151         case *Defer:
 152         case *Extract:
 153         case *Field:
 154         case *FieldAddr:
 155         case *Go:
 156         case *Index:
 157         case *IndexAddr:
 158         case *MapLookup:
 159         case *StringLookup:
 160         case *MakeChan:
 161         case *MakeClosure:
 162                 numFree := len(instr.Fn.(*Function).FreeVars)
 163                 numBind := len(instr.Bindings)
 164                 if numFree != numBind {
 165                         s.errorf("MakeClosure has %d Bindings for function %s with %d free vars",
 166                                 numBind, instr.Fn, numFree)
 167
 168                 }
 169                 if recv := instr.Type().(*types.Signature).Recv(); recv != nil {
 170                         s.errorf("MakeClosure's type includes receiver %s", recv.Type())
 171                 }
 172
 173         case *MakeInterface:
 174         case *MakeMap:
 175         case *MakeSlice:
 176         case *MapUpdate:
 177         case *Next:
 178         case *Range:
 179         case *RunDefers:
 180         case *Select:
 181         case *Send:
 182         case *Slice:
 183         case *Store:
 184         case *TypeAssert:
 185         case *UnOp:
 186         case *DebugRef:
 187         case *BlankStore:
 188         case *Load:
 189         case *Parameter:
 190         case *Const:
 191         case *Recv:
 192         case *TypeSwitch:
 193         default:
 194                 panic(fmt.Sprintf("Unknown instruction type: %T", instr))
 195         }
 196
 197         if call, ok := instr.(CallInstruction); ok {
 198                 if call.Common().Signature() == nil {
 199                         s.errorf("nil signature: %s", call)
 200                 }
 201         }
 202
 203         // Check that value-defining instructions have valid types
 204         // and a valid referrer list.
 205         if v, ok := instr.(Value); ok {
 206                 t := v.Type()
 207                 if t == nil {
 208                         s.errorf("no type: %s = %s", v.Name(), v)
 209                 } else if t == tRangeIter {
 210                         // not a proper type; ignore.
 211                 } else if b, ok := t.Underlying().(*types.Basic); ok && b.Info()&types.IsUntyped != 0 {
 212                         if _, ok := v.(*Const); !ok {
 213                                 s.errorf("instruction has 'untyped' result: %s = %s : %s", v.Name(), v, t)
 214                         }
 215                 }
 216                 s.checkReferrerList(v)
 217         }
 218
 219         // Untyped constants are legal as instruction Operands(),
 220         // for example:
 221         //   _ = "foo"[0]
 222         // or:
 223         //   if wordsize==64 {...}
 224
 225         // All other non-Instruction Values can be found via their
 226         // enclosing Function or Package.
 227 }
 228
 229 func (s *sanity) checkFinalInstr(instr Instruction) {
 230         switch instr := instr.(type) {
 231         case *If:
 232                 if nsuccs := len(s.block.Succs); nsuccs != 2 {
 233                         s.errorf("If-terminated block has %d successors; expected 2", nsuccs)
 234                         return
 235                 }
 236                 if s.block.Succs[0] == s.block.Succs[1] {
 237                         s.errorf("If-instruction has same True, False target blocks: %s", s.block.Succs[0])
 238                         return
 239                 }
 240
 241         case *Jump:
 242                 if nsuccs := len(s.block.Succs); nsuccs != 1 {
 243                         s.errorf("Jump-terminated block has %d successors; expected 1", nsuccs)
 244                         return
 245                 }
 246
 247         case *Return:
 248                 if nsuccs := len(s.block.Succs); nsuccs != 0 {
 249                         s.errorf("Return-terminated block has %d successors; expected none", nsuccs)
 250                         return
 251                 }
 252                 if na, nf := len(instr.Results), s.fn.Signature.Results().Len(); nf != na {
 253                         s.errorf("%d-ary return in %d-ary function", na, nf)
 254                 }
 255
 256         case *Panic:
 257                 if nsuccs := len(s.block.Succs); nsuccs != 1 {
 258                         s.errorf("Panic-terminated block has %d successors; expected one", nsuccs)
 259                         return
 260                 }
 261
 262         case *Unreachable:
 263                 if nsuccs := len(s.block.Succs); nsuccs != 1 {
 264                         s.errorf("Unreachable-terminated block has %d successors; expected one", nsuccs)
 265                         return
 266                 }
 267
 268         case *ConstantSwitch:
 269
 270         default:
 271                 s.errorf("non-control flow instruction at end of block")
 272         }
 273 }
 274
 275 func (s *sanity) checkBlock(b *BasicBlock, index int) {
 276         s.block = b
 277
 278         if b.Index != index {
 279                 s.errorf("block has incorrect Index %d", b.Index)
 280         }
 281         if b.parent != s.fn {
 282                 s.errorf("block has incorrect parent %s", b.parent)
 283         }
 284
 285         // Check all blocks are reachable.
 286         // (The entry block is always implicitly reachable, the exit block may be unreachable.)
 287         if index > 1 && len(b.Preds) == 0 {
 288                 s.warnf("unreachable block")
 289                 if b.Instrs == nil {
 290                         // Since this block is about to be pruned,
 291                         // tolerating transient problems in it
 292                         // simplifies other optimizations.
 293                         return
 294                 }
 295         }
 296
 297         // Check predecessor and successor relations are dual,
 298         // and that all blocks in CFG belong to same function.
 299         for _, a := range b.Preds {
 300                 found := false
 301                 for _, bb := range a.Succs {
 302                         if bb == b {
 303                                 found = true
 304                                 break
 305                         }
 306                 }
 307                 if !found {
 308                         s.errorf("expected successor edge in predecessor %s; found only: %s", a, a.Succs)
 309                 }
 310                 if a.parent != s.fn {
 311                         s.errorf("predecessor %s belongs to different function %s", a, a.parent)
 312                 }
 313         }
 314         for _, c := range b.Succs {
 315                 found := false
 316                 for _, bb := range c.Preds {
 317                         if bb == b {
 318                                 found = true
 319                                 break
 320                         }
 321                 }
 322                 if !found {
 323                         s.errorf("expected predecessor edge in successor %s; found only: %s", c, c.Preds)
 324                 }
 325                 if c.parent != s.fn {
 326                         s.errorf("successor %s belongs to different function %s", c, c.parent)
 327                 }
 328         }
 329
 330         // Check each instruction is sane.
 331         n := len(b.Instrs)
 332         if n == 0 {
 333                 s.errorf("basic block contains no instructions")
 334         }
 335         var rands [10]*Value // reuse storage
 336         for j, instr := range b.Instrs {
 337                 if instr == nil {
 338                         s.errorf("nil instruction at index %d", j)
 339                         continue
 340                 }
 341                 if b2 := instr.Block(); b2 == nil {
 342                         s.errorf("nil Block() for instruction at index %d", j)
 343                         continue
 344                 } else if b2 != b {
 345                         s.errorf("wrong Block() (%s) for instruction at index %d ", b2, j)
 346                         continue
 347                 }
 348                 if j < n-1 {
 349                         s.checkInstr(j, instr)
 350                 } else {
 351                         s.checkFinalInstr(instr)
 352                 }
 353
 354                 // Check Instruction.Operands.
 355         operands:
 356                 for i, op := range instr.Operands(rands[:0]) {
 357                         if op == nil {
 358                                 s.errorf("nil operand pointer %d of %s", i, instr)
 359                                 continue
 360                         }
 361                         val := *op
 362                         if val == nil {
 363                                 continue // a nil operand is ok
 364                         }
 365
 366                         // Check that "untyped" types only appear on constant operands.
 367                         if _, ok := (*op).(*Const); !ok {
 368                                 if basic, ok := (*op).Type().(*types.Basic); ok {
 369                                         if basic.Info()&types.IsUntyped != 0 {
 370                                                 s.errorf("operand #%d of %s is untyped: %s", i, instr, basic)
 371                                         }
 372                                 }
 373                         }
 374
 375                         // Check that Operands that are also Instructions belong to same function.
 376                         // TODO(adonovan): also check their block dominates block b.
 377                         if val, ok := val.(Instruction); ok {
 378                                 if val.Block() == nil {
 379                                         s.errorf("operand %d of %s is an instruction (%s) that belongs to no block", i, instr, val)
 380                                 } else if val.Parent() != s.fn {
 381                                         s.errorf("operand %d of %s is an instruction (%s) from function %s", i, instr, val, val.Parent())
 382                                 }
 383                         }
 384
 385                         // Check that each function-local operand of
 386                         // instr refers back to instr.  (NB: quadratic)
 387                         switch val := val.(type) {
 388                         case *Const, *Global, *Builtin:
 389                                 continue // not local
 390                         case *Function:
 391                                 if val.parent == nil {
 392                                         continue // only anon functions are local
 393                                 }
 394                         }
 395
 396                         // TODO(adonovan): check val.Parent() != nil <=> val.Referrers() is defined.
 397
 398                         if refs := val.Referrers(); refs != nil {
 399                                 for _, ref := range *refs {
 400                                         if ref == instr {
 401                                                 continue operands
 402                                         }
 403                                 }
 404                                 s.errorf("operand %d of %s (%s) does not refer to us", i, instr, val)
 405                         } else {
 406                                 s.errorf("operand %d of %s (%s) has no referrers", i, instr, val)
 407                         }
 408                 }
 409         }
 410 }
 411
 412 func (s *sanity) checkReferrerList(v Value) {
 413         refs := v.Referrers()
 414         if refs == nil {
 415                 s.errorf("%s has missing referrer list", v.Name())
 416                 return
 417         }
 418         for i, ref := range *refs {
 419                 if _, ok := s.instrs[ref]; !ok {
 420                         if val, ok := ref.(Value); ok {
 421                                 s.errorf("%s.Referrers()[%d] = %s = %s is not an instruction belonging to this function", v.Name(), i, val.Name(), val)
 422                         } else {
 423                                 s.errorf("%s.Referrers()[%d] = %s is not an instruction belonging to this function", v.Name(), i, ref)
 424                         }
 425                 }
 426         }
 427 }
 428
 429 func (s *sanity) checkFunction(fn *Function) bool {
 430         // TODO(adonovan): check Function invariants:
 431         // - check params match signature
 432         // - check transient fields are nil
 433         // - warn if any fn.Locals do not appear among block instructions.
 434         s.fn = fn
 435         if fn.Prog == nil {
 436                 s.errorf("nil Prog")
 437         }
 438
 439         _ = fn.String()            // must not crash
 440         _ = fn.RelString(fn.pkg()) // must not crash
 441
 442         // All functions have a package, except delegates (which are
 443         // shared across packages, or duplicated as weak symbols in a
 444         // separate-compilation model), and error.Error.
 445         if fn.Pkg == nil {
 446                 if strings.HasPrefix(fn.Synthetic, "wrapper ") ||
 447                         strings.HasPrefix(fn.Synthetic, "bound ") ||
 448                         strings.HasPrefix(fn.Synthetic, "thunk ") ||
 449                         strings.HasSuffix(fn.name, "Error") {
 450                         // ok
 451                 } else {
 452                         s.errorf("nil Pkg")
 453                 }
 454         }
 455         if src, syn := fn.Synthetic == "", fn.source != nil; src != syn {
 456                 s.errorf("got fromSource=%t, hasSyntax=%t; want same values", src, syn)
 457         }
 458         for i, l := range fn.Locals {
 459                 if l.Parent() != fn {
 460                         s.errorf("Local %s at index %d has wrong parent", l.Name(), i)
 461                 }
 462                 if l.Heap {
 463                         s.errorf("Local %s at index %d has Heap flag set", l.Name(), i)
 464                 }
 465         }
 466         // Build the set of valid referrers.
 467         s.instrs = make(map[Instruction]struct{})
 468         for _, b := range fn.Blocks {
 469                 for _, instr := range b.Instrs {
 470                         s.instrs[instr] = struct{}{}
 471                 }
 472         }
 473         for i, p := range fn.Params {
 474                 if p.Parent() != fn {
 475                         s.errorf("Param %s at index %d has wrong parent", p.Name(), i)
 476                 }
 477                 // Check common suffix of Signature and Params match type.
 478                 if sig := fn.Signature; sig != nil {
 479                         j := i - len(fn.Params) + sig.Params().Len() // index within sig.Params
 480                         if j < 0 {
 481                                 continue
 482                         }
 483                         if !types.Identical(p.Type(), sig.Params().At(j).Type()) {
 484                                 s.errorf("Param %s at index %d has wrong type (%s, versus %s in Signature)", p.Name(), i, p.Type(), sig.Params().At(j).Type())
 485
 486                         }
 487                 }
 488
 489                 s.checkReferrerList(p)
 490         }
 491         for i, fv := range fn.FreeVars {
 492                 if fv.Parent() != fn {
 493                         s.errorf("FreeVar %s at index %d has wrong parent", fv.Name(), i)
 494                 }
 495                 s.checkReferrerList(fv)
 496         }
 497
 498         if fn.Blocks != nil && len(fn.Blocks) == 0 {
 499                 // Function _had_ blocks (so it's not external) but
 500                 // they were "optimized" away, even the entry block.
 501                 s.errorf("Blocks slice is non-nil but empty")
 502         }
 503         for i, b := range fn.Blocks {
 504                 if b == nil {
 505                         s.warnf("nil *BasicBlock at f.Blocks[%d]", i)
 506                         continue
 507                 }
 508                 s.checkBlock(b, i)
 509         }
 510
 511         s.block = nil
 512         for i, anon := range fn.AnonFuncs {
 513                 if anon.Parent() != fn {
 514                         s.errorf("AnonFuncs[%d]=%s but %s.Parent()=%s", i, anon, anon, anon.Parent())
 515                 }
 516         }
 517         s.fn = nil
 518         return !s.insane
 519 }
 520
 521 // sanityCheckPackage checks invariants of packages upon creation.
 522 // It does not require that the package is built.
 523 // Unlike sanityCheck (for functions), it just panics at the first error.
 524 func sanityCheckPackage(pkg *Package) {
 525         if pkg.Pkg == nil {
 526                 panic(fmt.Sprintf("Package %s has no Object", pkg))
 527         }
 528         _ = pkg.String() // must not crash
 529
 530         for name, mem := range pkg.Members {
 531                 if name != mem.Name() {
 532                         panic(fmt.Sprintf("%s: %T.Name() = %s, want %s",
 533                                 pkg.Pkg.Path(), mem, mem.Name(), name))
 534                 }
 535                 obj := mem.Object()
 536                 if obj == nil {
 537                         // This check is sound because fields
 538                         // {Global,Function}.object have type
 539                         // types.Object.  (If they were declared as
 540                         // *types.{Var,Func}, we'd have a non-empty
 541                         // interface containing a nil pointer.)
 542
 543                         continue // not all members have typechecker objects
 544                 }
 545                 if obj.Name() != name {
 546                         if obj.Name() == "init" && strings.HasPrefix(mem.Name(), "init#") {
 547                                 // Ok.  The name of a declared init function varies between
 548                                 // its types.Func ("init") and its ir.Function ("init#%d").
 549                         } else {
 550                                 panic(fmt.Sprintf("%s: %T.Object().Name() = %s, want %s",
 551                                         pkg.Pkg.Path(), mem, obj.Name(), name))
 552                         }
 553                 }
 554         }
 555 }