Source file src/pkg/cmd/compile/internal/syntax/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	// 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