.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/cfg/builder.go

   1 // Copyright 2016 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 cfg
   6
   7 // This file implements the CFG construction pass.
   8
   9 import (
  10         "fmt"
  11         "go/ast"
  12         "go/token"
  13 )
  14
  15 type builder struct {
  16         cfg       *CFG
  17         mayReturn func(*ast.CallExpr) bool
  18         current   *Block
  19         lblocks   map[*ast.Object]*lblock // labeled blocks
  20         targets   *targets                // linked stack of branch targets
  21 }
  22
  23 func (b *builder) stmt(_s ast.Stmt) {
  24         // The label of the current statement.  If non-nil, its _goto
  25         // target is always set; its _break and _continue are set only
  26         // within the body of switch/typeswitch/select/for/range.
  27         // It is effectively an additional default-nil parameter of stmt().
  28         var label *lblock
  29 start:
  30         switch s := _s.(type) {
  31         case *ast.BadStmt,
  32                 *ast.SendStmt,
  33                 *ast.IncDecStmt,
  34                 *ast.GoStmt,
  35                 *ast.DeferStmt,
  36                 *ast.EmptyStmt,
  37                 *ast.AssignStmt:
  38                 // No effect on control flow.
  39                 b.add(s)
  40
  41         case *ast.ExprStmt:
  42                 b.add(s)
  43                 if call, ok := s.X.(*ast.CallExpr); ok && !b.mayReturn(call) {
  44                         // Calls to panic, os.Exit, etc, never return.
  45                         b.current = b.newBlock("unreachable.call")
  46                 }
  47
  48         case *ast.DeclStmt:
  49                 // Treat each var ValueSpec as a separate statement.
  50                 d := s.Decl.(*ast.GenDecl)
  51                 if d.Tok == token.VAR {
  52                         for _, spec := range d.Specs {
  53                                 if spec, ok := spec.(*ast.ValueSpec); ok {
  54                                         b.add(spec)
  55                                 }
  56                         }
  57                 }
  58
  59         case *ast.LabeledStmt:
  60                 label = b.labeledBlock(s.Label)
  61                 b.jump(label._goto)
  62                 b.current = label._goto
  63                 _s = s.Stmt
  64                 goto start // effectively: tailcall stmt(g, s.Stmt, label)
  65
  66         case *ast.ReturnStmt:
  67                 b.add(s)
  68                 b.current = b.newBlock("unreachable.return")
  69
  70         case *ast.BranchStmt:
  71                 b.branchStmt(s)
  72
  73         case *ast.BlockStmt:
  74                 b.stmtList(s.List)
  75
  76         case *ast.IfStmt:
  77                 if s.Init != nil {
  78                         b.stmt(s.Init)
  79                 }
  80                 then := b.newBlock("if.then")
  81                 done := b.newBlock("if.done")
  82                 _else := done
  83                 if s.Else != nil {
  84                         _else = b.newBlock("if.else")
  85                 }
  86                 b.add(s.Cond)
  87                 b.ifelse(then, _else)
  88                 b.current = then
  89                 b.stmt(s.Body)
  90                 b.jump(done)
  91
  92                 if s.Else != nil {
  93                         b.current = _else
  94                         b.stmt(s.Else)
  95                         b.jump(done)
  96                 }
  97
  98                 b.current = done
  99
 100         case *ast.SwitchStmt:
 101                 b.switchStmt(s, label)
 102
 103         case *ast.TypeSwitchStmt:
 104                 b.typeSwitchStmt(s, label)
 105
 106         case *ast.SelectStmt:
 107                 b.selectStmt(s, label)
 108
 109         case *ast.ForStmt:
 110                 b.forStmt(s, label)
 111
 112         case *ast.RangeStmt:
 113                 b.rangeStmt(s, label)
 114
 115         default:
 116                 panic(fmt.Sprintf("unexpected statement kind: %T", s))
 117         }
 118 }
 119
 120 func (b *builder) stmtList(list []ast.Stmt) {
 121         for _, s := range list {
 122                 b.stmt(s)
 123         }
 124 }
 125
 126 func (b *builder) branchStmt(s *ast.BranchStmt) {
 127         var block *Block
 128         switch s.Tok {
 129         case token.BREAK:
 130                 if s.Label != nil {
 131                         if lb := b.labeledBlock(s.Label); lb != nil {
 132                                 block = lb._break
 133                         }
 134                 } else {
 135                         for t := b.targets; t != nil && block == nil; t = t.tail {
 136                                 block = t._break
 137                         }
 138                 }
 139
 140         case token.CONTINUE:
 141                 if s.Label != nil {
 142                         if lb := b.labeledBlock(s.Label); lb != nil {
 143                                 block = lb._continue
 144                         }
 145                 } else {
 146                         for t := b.targets; t != nil && block == nil; t = t.tail {
 147                                 block = t._continue
 148                         }
 149                 }
 150
 151         case token.FALLTHROUGH:
 152                 for t := b.targets; t != nil && block == nil; t = t.tail {
 153                         block = t._fallthrough
 154                 }
 155
 156         case token.GOTO:
 157                 if s.Label != nil {
 158                         block = b.labeledBlock(s.Label)._goto
 159                 }
 160         }
 161         if block == nil {
 162                 block = b.newBlock("undefined.branch")
 163         }
 164         b.jump(block)
 165         b.current = b.newBlock("unreachable.branch")
 166 }
 167
 168 func (b *builder) switchStmt(s *ast.SwitchStmt, label *lblock) {
 169         if s.Init != nil {
 170                 b.stmt(s.Init)
 171         }
 172         if s.Tag != nil {
 173                 b.add(s.Tag)
 174         }
 175         done := b.newBlock("switch.done")
 176         if label != nil {
 177                 label._break = done
 178         }
 179         // We pull the default case (if present) down to the end.
 180         // But each fallthrough label must point to the next
 181         // body block in source order, so we preallocate a
 182         // body block (fallthru) for the next case.
 183         // Unfortunately this makes for a confusing block order.
 184         var defaultBody *[]ast.Stmt
 185         var defaultFallthrough *Block
 186         var fallthru, defaultBlock *Block
 187         ncases := len(s.Body.List)
 188         for i, clause := range s.Body.List {
 189                 body := fallthru
 190                 if body == nil {
 191                         body = b.newBlock("switch.body") // first case only
 192                 }
 193
 194                 // Preallocate body block for the next case.
 195                 fallthru = done
 196                 if i+1 < ncases {
 197                         fallthru = b.newBlock("switch.body")
 198                 }
 199
 200                 cc := clause.(*ast.CaseClause)
 201                 if cc.List == nil {
 202                         // Default case.
 203                         defaultBody = &cc.Body
 204                         defaultFallthrough = fallthru
 205                         defaultBlock = body
 206                         continue
 207                 }
 208
 209                 var nextCond *Block
 210                 for _, cond := range cc.List {
 211                         nextCond = b.newBlock("switch.next")
 212                         b.add(cond) // one half of the tag==cond condition
 213                         b.ifelse(body, nextCond)
 214                         b.current = nextCond
 215                 }
 216                 b.current = body
 217                 b.targets = &targets{
 218                         tail:         b.targets,
 219                         _break:       done,
 220                         _fallthrough: fallthru,
 221                 }
 222                 b.stmtList(cc.Body)
 223                 b.targets = b.targets.tail
 224                 b.jump(done)
 225                 b.current = nextCond
 226         }
 227         if defaultBlock != nil {
 228                 b.jump(defaultBlock)
 229                 b.current = defaultBlock
 230                 b.targets = &targets{
 231                         tail:         b.targets,
 232                         _break:       done,
 233                         _fallthrough: defaultFallthrough,
 234                 }
 235                 b.stmtList(*defaultBody)
 236                 b.targets = b.targets.tail
 237         }
 238         b.jump(done)
 239         b.current = done
 240 }
 241
 242 func (b *builder) typeSwitchStmt(s *ast.TypeSwitchStmt, label *lblock) {
 243         if s.Init != nil {
 244                 b.stmt(s.Init)
 245         }
 246         if s.Assign != nil {
 247                 b.add(s.Assign)
 248         }
 249
 250         done := b.newBlock("typeswitch.done")
 251         if label != nil {
 252                 label._break = done
 253         }
 254         var default_ *ast.CaseClause
 255         for _, clause := range s.Body.List {
 256                 cc := clause.(*ast.CaseClause)
 257                 if cc.List == nil {
 258                         default_ = cc
 259                         continue
 260                 }
 261                 body := b.newBlock("typeswitch.body")
 262                 var next *Block
 263                 for _, casetype := range cc.List {
 264                         next = b.newBlock("typeswitch.next")
 265                         // casetype is a type, so don't call b.add(casetype).
 266                         // This block logically contains a type assertion,
 267                         // x.(casetype), but it's unclear how to represent x.
 268                         _ = casetype
 269                         b.ifelse(body, next)
 270                         b.current = next
 271                 }
 272                 b.current = body
 273                 b.typeCaseBody(cc, done)
 274                 b.current = next
 275         }
 276         if default_ != nil {
 277                 b.typeCaseBody(default_, done)
 278         } else {
 279                 b.jump(done)
 280         }
 281         b.current = done
 282 }
 283
 284 func (b *builder) typeCaseBody(cc *ast.CaseClause, done *Block) {
 285         b.targets = &targets{
 286                 tail:   b.targets,
 287                 _break: done,
 288         }
 289         b.stmtList(cc.Body)
 290         b.targets = b.targets.tail
 291         b.jump(done)
 292 }
 293
 294 func (b *builder) selectStmt(s *ast.SelectStmt, label *lblock) {
 295         // First evaluate channel expressions.
 296         // TODO(adonovan): fix: evaluate only channel exprs here.
 297         for _, clause := range s.Body.List {
 298                 if comm := clause.(*ast.CommClause).Comm; comm != nil {
 299                         b.stmt(comm)
 300                 }
 301         }
 302
 303         done := b.newBlock("select.done")
 304         if label != nil {
 305                 label._break = done
 306         }
 307
 308         var defaultBody *[]ast.Stmt
 309         for _, cc := range s.Body.List {
 310                 clause := cc.(*ast.CommClause)
 311                 if clause.Comm == nil {
 312                         defaultBody = &clause.Body
 313                         continue
 314                 }
 315                 body := b.newBlock("select.body")
 316                 next := b.newBlock("select.next")
 317                 b.ifelse(body, next)
 318                 b.current = body
 319                 b.targets = &targets{
 320                         tail:   b.targets,
 321                         _break: done,
 322                 }
 323                 switch comm := clause.Comm.(type) {
 324                 case *ast.ExprStmt: // <-ch
 325                         // nop
 326                 case *ast.AssignStmt: // x := <-states[state].Chan
 327                         b.add(comm.Lhs[0])
 328                 }
 329                 b.stmtList(clause.Body)
 330                 b.targets = b.targets.tail
 331                 b.jump(done)
 332                 b.current = next
 333         }
 334         if defaultBody != nil {
 335                 b.targets = &targets{
 336                         tail:   b.targets,
 337                         _break: done,
 338                 }
 339                 b.stmtList(*defaultBody)
 340                 b.targets = b.targets.tail
 341                 b.jump(done)
 342         }
 343         b.current = done
 344 }
 345
 346 func (b *builder) forStmt(s *ast.ForStmt, label *lblock) {
 347         //      ...init...
 348         //      jump loop
 349         // loop:
 350         //      if cond goto body else done
 351         // body:
 352         //      ...body...
 353         //      jump post
 354         // post:                                 (target of continue)
 355         //      ...post...
 356         //      jump loop
 357         // done:                                 (target of break)
 358         if s.Init != nil {
 359                 b.stmt(s.Init)
 360         }
 361         body := b.newBlock("for.body")
 362         done := b.newBlock("for.done") // target of 'break'
 363         loop := body                   // target of back-edge
 364         if s.Cond != nil {
 365                 loop = b.newBlock("for.loop")
 366         }
 367         cont := loop // target of 'continue'
 368         if s.Post != nil {
 369                 cont = b.newBlock("for.post")
 370         }
 371         if label != nil {
 372                 label._break = done
 373                 label._continue = cont
 374         }
 375         b.jump(loop)
 376         b.current = loop
 377         if loop != body {
 378                 b.add(s.Cond)
 379                 b.ifelse(body, done)
 380                 b.current = body
 381         }
 382         b.targets = &targets{
 383                 tail:      b.targets,
 384                 _break:    done,
 385                 _continue: cont,
 386         }
 387         b.stmt(s.Body)
 388         b.targets = b.targets.tail
 389         b.jump(cont)
 390
 391         if s.Post != nil {
 392                 b.current = cont
 393                 b.stmt(s.Post)
 394                 b.jump(loop) // back-edge
 395         }
 396         b.current = done
 397 }
 398
 399 func (b *builder) rangeStmt(s *ast.RangeStmt, label *lblock) {
 400         b.add(s.X)
 401
 402         if s.Key != nil {
 403                 b.add(s.Key)
 404         }
 405         if s.Value != nil {
 406                 b.add(s.Value)
 407         }
 408
 409         //      ...
 410         // loop:                                   (target of continue)
 411         //      if ... goto body else done
 412         // body:
 413         //      ...
 414         //      jump loop
 415         // done:                                   (target of break)
 416
 417         loop := b.newBlock("range.loop")
 418         b.jump(loop)
 419         b.current = loop
 420
 421         body := b.newBlock("range.body")
 422         done := b.newBlock("range.done")
 423         b.ifelse(body, done)
 424         b.current = body
 425
 426         if label != nil {
 427                 label._break = done
 428                 label._continue = loop
 429         }
 430         b.targets = &targets{
 431                 tail:      b.targets,
 432                 _break:    done,
 433                 _continue: loop,
 434         }
 435         b.stmt(s.Body)
 436         b.targets = b.targets.tail
 437         b.jump(loop) // back-edge
 438         b.current = done
 439 }
 440
 441 // -------- helpers --------
 442
 443 // Destinations associated with unlabeled for/switch/select stmts.
 444 // We push/pop one of these as we enter/leave each construct and for
 445 // each BranchStmt we scan for the innermost target of the right type.
 446 //
 447 type targets struct {
 448         tail         *targets // rest of stack
 449         _break       *Block
 450         _continue    *Block
 451         _fallthrough *Block
 452 }
 453
 454 // Destinations associated with a labeled block.
 455 // We populate these as labels are encountered in forward gotos or
 456 // labeled statements.
 457 //
 458 type lblock struct {
 459         _goto     *Block
 460         _break    *Block
 461         _continue *Block
 462 }
 463
 464 // labeledBlock returns the branch target associated with the
 465 // specified label, creating it if needed.
 466 //
 467 func (b *builder) labeledBlock(label *ast.Ident) *lblock {
 468         lb := b.lblocks[label.Obj]
 469         if lb == nil {
 470                 lb = &lblock{_goto: b.newBlock(label.Name)}
 471                 if b.lblocks == nil {
 472                         b.lblocks = make(map[*ast.Object]*lblock)
 473                 }
 474                 b.lblocks[label.Obj] = lb
 475         }
 476         return lb
 477 }
 478
 479 // newBlock appends a new unconnected basic block to b.cfg's block
 480 // slice and returns it.
 481 // It does not automatically become the current block.
 482 // comment is an optional string for more readable debugging output.
 483 func (b *builder) newBlock(comment string) *Block {
 484         g := b.cfg
 485         block := &Block{
 486                 Index:   int32(len(g.Blocks)),
 487                 comment: comment,
 488         }
 489         block.Succs = block.succs2[:0]
 490         g.Blocks = append(g.Blocks, block)
 491         return block
 492 }
 493
 494 func (b *builder) add(n ast.Node) {
 495         b.current.Nodes = append(b.current.Nodes, n)
 496 }
 497
 498 // jump adds an edge from the current block to the target block,
 499 // and sets b.current to nil.
 500 func (b *builder) jump(target *Block) {
 501         b.current.Succs = append(b.current.Succs, target)
 502         b.current = nil
 503 }
 504
 505 // ifelse emits edges from the current block to the t and f blocks,
 506 // and sets b.current to nil.
 507 func (b *builder) ifelse(t, f *Block) {
 508         b.current.Succs = append(b.current.Succs, t, f)
 509         b.current = nil
 510 }