branches.go

     1  // Copyright 2017 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 syntax
     6  
     7  import "fmt"
     8  
     9  // checkBranches checks correct use of labels and branch
    10  // statements (break, continue, fallthrough, goto) in a function body.
    11  // It catches:
    12  //   - misplaced breaks, continues, and fallthroughs
    13  //   - bad labeled breaks and continues
    14  //   - invalid, unused, duplicate, and missing labels
    15  //   - gotos jumping over variable declarations and into blocks
    16  func checkBranches(body *BlockStmt, errh ErrorHandler) {
    17  	if body == nil {
    18  		return
    19  	}
    20  
    21  	// scope of all labels in this body
    22  	ls := &labelScope{errh: errh}
    23  	fwdGotos := ls.blockBranches(nil, targets{}, nil, body.Pos(), body.List)
    24  
    25  	// If there are any forward gotos left, no matching label was
    26  	// found for them. Either those labels were never defined, or
    27  	// they are inside blocks and not reachable from the gotos.
    28  	for _, fwd := range fwdGotos {
    29  		name := fwd.Label.Value
    30  		if l := ls.labels[name]; l != nil {
    31  			l.used = true // avoid "defined and not used" error
    32  			ls.errf(fwd.Label.Pos(), "goto %s jumps into block starting at %s", name, l.parent.start)
    33  		} else {
    34  			ls.errf(fwd.Label.Pos(), "label %s not defined", name)
    35  		}
    36  	}
    37  
    38  	// spec: "It is illegal to define a label that is never used."
    39  	for _, l := range ls.labels {
    40  		if !l.used {
    41  			l := l.lstmt.Label
    42  			ls.errf(l.Pos(), "label %s defined and not used", l.Value)
    43  		}
    44  	}
    45  }
    46  
    47  type labelScope struct {
    48  	errh   ErrorHandler
    49  	labels map[string]*label // all label declarations inside the function; allocated lazily
    50  }
    51  
    52  type label struct {
    53  	parent *block       // block containing this label declaration
    54  	lstmt  *LabeledStmt // statement declaring the label
    55  	used   bool         // whether the label is used or not
    56  }
    57  
    58  type block struct {
    59  	parent *block       // immediately enclosing block, or nil
    60  	start  Pos          // start of block
    61  	lstmt  *LabeledStmt // labeled statement associated with this block, or nil
    62  }
    63  
    64  func (ls *labelScope) errf(pos Pos, format string, args ...interface{}) {
    65  	ls.errh(Error{pos, fmt.Sprintf(format, args...)})
    66  }
    67  
    68  // declare declares the label introduced by s in block b and returns
    69  // the new label. If the label was already declared, declare reports
    70  // and error and the existing label is returned instead.
    71  func (ls *labelScope) declare(b *block, s *LabeledStmt) *label {
    72  	name := s.Label.Value
    73  	labels := ls.labels
    74  	if labels == nil {
    75  		labels = make(map[string]*label)
    76  		ls.labels = labels
    77  	} else if alt := labels[name]; alt != nil {
    78  		ls.errf(s.Label.Pos(), "label %s already defined at %s", name, alt.lstmt.Label.Pos().String())
    79  		return alt
    80  	}
    81  	l := &label{b, s, false}
    82  	labels[name] = l
    83  	return l
    84  }
    85  
    86  // gotoTarget returns the labeled statement matching the given name and
    87  // declared in block b or any of its enclosing blocks. The result is nil
    88  // if the label is not defined, or doesn't match a valid labeled statement.
    89  func (ls *labelScope) gotoTarget(b *block, name string) *LabeledStmt {
    90  	if l := ls.labels[name]; l != nil {
    91  		l.used = true // even if it's not a valid target
    92  		for ; b != nil; b = b.parent {
    93  			if l.parent == b {
    94  				return l.lstmt
    95  			}
    96  		}
    97  	}
    98  	return nil
    99  }
   100  
   101  var invalid = new(LabeledStmt) // singleton to signal invalid enclosing target
   102  
   103  // enclosingTarget returns the innermost enclosing labeled statement matching
   104  // the given name. The result is nil if the label is not defined, and invalid
   105  // if the label is defined but doesn't label a valid labeled statement.
   106  func (ls *labelScope) enclosingTarget(b *block, name string) *LabeledStmt {
   107  	if l := ls.labels[name]; l != nil {
   108  		l.used = true // even if it's not a valid target (see e.g., test/fixedbugs/bug136.go)
   109  		for ; b != nil; b = b.parent {
   110  			if l.lstmt == b.lstmt {
   111  				return l.lstmt
   112  			}
   113  		}
   114  		return invalid
   115  	}
   116  	return nil
   117  }
   118  
   119  // targets describes the target statements within which break
   120  // or continue statements are valid.
   121  type targets struct {
   122  	breaks    Stmt     // *ForStmt, *SwitchStmt, *SelectStmt, or nil
   123  	continues *ForStmt // or nil
   124  	caseIndex int      // case index of immediately enclosing switch statement, or < 0
   125  }
   126  
   127  // blockBranches processes a block's body starting at start and returns the
   128  // list of unresolved (forward) gotos. parent is the immediately enclosing
   129  // block (or nil), ctxt provides information about the enclosing statements,
   130  // and lstmt is the labeled statement associated with this block, or nil.
   131  func (ls *labelScope) blockBranches(parent *block, ctxt targets, lstmt *LabeledStmt, start Pos, body []Stmt) []*BranchStmt {
   132  	b := &block{parent: parent, start: start, lstmt: lstmt}
   133  
   134  	var varPos Pos
   135  	var varName Expr
   136  	var fwdGotos, badGotos []*BranchStmt
   137  
   138  	recordVarDecl := func(pos Pos, name Expr) {
   139  		varPos = pos
   140  		varName = name
   141  		// Any existing forward goto jumping over the variable
   142  		// declaration is invalid. The goto may still jump out
   143  		// of the block and be ok, but we don't know that yet.
   144  		// Remember all forward gotos as potential bad gotos.
   145  		badGotos = append(badGotos[:0], fwdGotos...)
   146  	}
   147  
   148  	jumpsOverVarDecl := func(fwd *BranchStmt) bool {
   149  		if varPos.IsKnown() {
   150  			for _, bad := range badGotos {
   151  				if fwd == bad {
   152  					return true
   153  				}
   154  			}
   155  		}
   156  		return false
   157  	}
   158  
   159  	innerBlock := func(ctxt targets, start Pos, body []Stmt) {
   160  		// Unresolved forward gotos from the inner block
   161  		// become forward gotos for the current block.
   162  		fwdGotos = append(fwdGotos, ls.blockBranches(b, ctxt, lstmt, start, body)...)
   163  	}
   164  
   165  	// A fallthrough statement counts as last statement in a statement
   166  	// list even if there are trailing empty statements; remove them.
   167  	stmtList := trimTrailingEmptyStmts(body)
   168  	for stmtIndex, stmt := range stmtList {
   169  		lstmt = nil
   170  	L:
   171  		switch s := stmt.(type) {
   172  		case *DeclStmt:
   173  			for _, d := range s.DeclList {
   174  				if v, ok := d.(*VarDecl); ok {
   175  					recordVarDecl(v.Pos(), v.NameList[0])
   176  					break // the first VarDecl will do
   177  				}
   178  			}
   179  
   180  		case *LabeledStmt:
   181  			// declare non-blank label
   182  			if name := s.Label.Value; name != "_" {
   183  				l := ls.declare(b, s)
   184  				// resolve matching forward gotos
   185  				i := 0
   186  				for _, fwd := range fwdGotos {
   187  					if fwd.Label.Value == name {
   188  						fwd.Target = s
   189  						l.used = true
   190  						if jumpsOverVarDecl(fwd) {
   191  							ls.errf(
   192  								fwd.Label.Pos(),
   193  								"goto %s jumps over declaration of %s at %s",
   194  								name, String(varName), varPos,
   195  							)
   196  						}
   197  					} else {
   198  						// no match - keep forward goto
   199  						fwdGotos[i] = fwd
   200  						i++
   201  					}
   202  				}
   203  				fwdGotos = fwdGotos[:i]
   204  				lstmt = s
   205  			}
   206  			// process labeled statement
   207  			stmt = s.Stmt
   208  			goto L
   209  
   210  		case *BranchStmt:
   211  			// unlabeled branch statement
   212  			if s.Label == nil {
   213  				switch s.Tok {
   214  				case _Break:
   215  					if t := ctxt.breaks; t != nil {
   216  						s.Target = t
   217  					} else {
   218  						ls.errf(s.Pos(), "break is not in a loop, switch, or select")
   219  					}
   220  				case _Continue:
   221  					if t := ctxt.continues; t != nil {
   222  						s.Target = t
   223  					} else {
   224  						ls.errf(s.Pos(), "continue is not in a loop")
   225  					}
   226  				case _Fallthrough:
   227  					msg := "fallthrough statement out of place"
   228  					if t, _ := ctxt.breaks.(*SwitchStmt); t != nil {
   229  						if _, ok := t.Tag.(*TypeSwitchGuard); ok {
   230  							msg = "cannot fallthrough in type switch"
   231  						} else if ctxt.caseIndex < 0 || stmtIndex+1 < len(stmtList) {
   232  							// fallthrough nested in a block or not the last statement
   233  							// use msg as is
   234  						} else if ctxt.caseIndex+1 == len(t.Body) {
   235  							msg = "cannot fallthrough final case in switch"
   236  						} else {
   237  							break // fallthrough ok
   238  						}
   239  					}
   240  					ls.errf(s.Pos(), "%s", msg)
   241  				case _Goto:
   242  					fallthrough // should always have a label
   243  				default:
   244  					panic("invalid BranchStmt")
   245  				}
   246  				break
   247  			}
   248  
   249  			// labeled branch statement
   250  			name := s.Label.Value
   251  			switch s.Tok {
   252  			case _Break:
   253  				// spec: "If there is a label, it must be that of an enclosing
   254  				// "for", "switch", or "select" statement, and that is the one
   255  				// whose execution terminates."
   256  				if t := ls.enclosingTarget(b, name); t != nil {
   257  					switch t := t.Stmt.(type) {
   258  					case *SwitchStmt, *SelectStmt, *ForStmt:
   259  						s.Target = t
   260  					default:
   261  						ls.errf(s.Label.Pos(), "invalid break label %s", name)
   262  					}
   263  				} else {
   264  					ls.errf(s.Label.Pos(), "break label not defined: %s", name)
   265  				}
   266  
   267  			case _Continue:
   268  				// spec: "If there is a label, it must be that of an enclosing
   269  				// "for" statement, and that is the one whose execution advances."
   270  				if t := ls.enclosingTarget(b, name); t != nil {
   271  					if t, ok := t.Stmt.(*ForStmt); ok {
   272  						s.Target = t
   273  					} else {
   274  						ls.errf(s.Label.Pos(), "invalid continue label %s", name)
   275  					}
   276  				} else {
   277  					ls.errf(s.Label.Pos(), "continue label not defined: %s", name)
   278  				}
   279  
   280  			case _Goto:
   281  				if t := ls.gotoTarget(b, name); t != nil {
   282  					s.Target = t
   283  				} else {
   284  					// label may be declared later - add goto to forward gotos
   285  					fwdGotos = append(fwdGotos, s)
   286  				}
   287  
   288  			case _Fallthrough:
   289  				fallthrough // should never have a label
   290  			default:
   291  				panic("invalid BranchStmt")
   292  			}
   293  
   294  		case *AssignStmt:
   295  			if s.Op == Def {
   296  				recordVarDecl(s.Pos(), s.Lhs)
   297  			}
   298  
   299  		case *BlockStmt:
   300  			inner := targets{ctxt.breaks, ctxt.continues, -1}
   301  			innerBlock(inner, s.Pos(), s.List)
   302  
   303  		case *IfStmt:
   304  			inner := targets{ctxt.breaks, ctxt.continues, -1}
   305  			innerBlock(inner, s.Then.Pos(), s.Then.List)
   306  			if s.Else != nil {
   307  				innerBlock(inner, s.Else.Pos(), []Stmt{s.Else})
   308  			}
   309  
   310  		case *ForStmt:
   311  			inner := targets{s, s, -1}
   312  			innerBlock(inner, s.Body.Pos(), s.Body.List)
   313  
   314  		case *SwitchStmt:
   315  			inner := targets{s, ctxt.continues, -1}
   316  			for i, cc := range s.Body {
   317  				inner.caseIndex = i
   318  				innerBlock(inner, cc.Pos(), cc.Body)
   319  			}
   320  
   321  		case *SelectStmt:
   322  			inner := targets{s, ctxt.continues, -1}
   323  			for _, cc := range s.Body {
   324  				innerBlock(inner, cc.Pos(), cc.Body)
   325  			}
   326  		}
   327  	}
   328  
   329  	return fwdGotos
   330  }
   331  
   332  func trimTrailingEmptyStmts(list []Stmt) []Stmt {
   333  	for i := len(list); i > 0; i-- {
   334  		if _, ok := list[i-1].(*EmptyStmt); !ok {
   335  			return list[:i]
   336  		}
   337  	}
   338  	return nil
   339  }
   340
View as plain text