Source file src/pkg/cmd/vendor/golang.org/x/tools/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; 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	}
   511	

View as plain text