branches.go

Documentation: cmd/compile/internal/syntax

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