From bd2838be77caf367cd6aede50c48279ee6b3a6c4 Mon Sep 17 00:00:00 2001 From: Josh Bleecher Snyder Date: Wed, 1 Jun 2016 11:34:28 -0700 Subject: [PATCH] cmd/compile: use a map to detect duplicate type switch cases MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This is a bit simpler than playing sorting games, and it is clearer that it generates errors in the correct (source) order. It also allows us to simplify sorting. It also prevents quadratic error messages for (pathological) inputs with many duplicate type cases. While we’re here, refactoring deduping into separate functions. Negligible compilebench impact. Fixes #15912. Change-Id: I6cc19edd38875389a70ccbdbdf0d9b7d5ac5946f Reviewed-on: https://go-review.googlesource.com/26762 Run-TryBot: Josh Bleecher Snyder Reviewed-by: Matthew Dempsky --- src/cmd/compile/internal/gc/swt.go | 81 ++++++++++++++++-------------- test/switch5.go | 2 +- 2 files changed, 45 insertions(+), 38 deletions(-) diff --git a/src/cmd/compile/internal/gc/swt.go b/src/cmd/compile/internal/gc/swt.go index 848eca8915..3662758bd4 100644 --- a/src/cmd/compile/internal/gc/swt.go +++ b/src/cmd/compile/internal/gc/swt.go @@ -453,8 +453,8 @@ func genCaseClauses(sw *Node, kind int) caseClauses { c.typ = caseKindTypeVar default: c.typ = caseKindTypeConst - c.hash = typehash(n.Left.Type) } + c.hash = typehash(n.Left.Type) } else { // expression switch switch consttype(n.Left) { @@ -477,37 +477,53 @@ func genCaseClauses(sw *Node, kind int) caseClauses { // sort by value and diagnose duplicate cases if kind == switchKindType { - // type switch - sort.Sort(caseClauseByType(cc.list)) - for i, c1 := range cc.list { - for _, c2 := range cc.list[i+1:] { - if c1.hash != c2.hash { - break - } - if Eqtype(c1.node.Left.Type, c2.node.Left.Type) { - yyerrorl(c2.node.Lineno, "duplicate case %v in type switch\n\tprevious case at %v", c2.node.Left.Type, c1.node.Line()) - } - } - } + checkDupTypeCases(cc.list) } else { - // expression switch - sort.Sort(caseClauseByExpr(cc.list)) - for i, c1 := range cc.list { - if i+1 == len(cc.list) { - break - } - c2 := cc.list[i+1] - if exprcmp(c1, c2) != 0 { - continue + checkDupExprCases(cc.list) + } + + return cc +} + +func checkDupTypeCases(cc []caseClause) { + // We store seen types in a map keyed by type hash. + // It is possible, but very unlikely, for multiple distinct types to have the same hash. + seen := make(map[uint32][]*Node) + // To avoid many small allocations of length 1 slices, + // also set up a single large slice to slice into. + nn := make([]*Node, 0, len(cc)) +Outer: + for _, c := range cc { + prev, ok := seen[c.hash] + if !ok { + // First entry for this hash. + nn = append(nn, c.node) + seen[c.hash] = nn[len(nn)-1 : len(nn):len(nn)] + continue + } + for _, n := range prev { + if Eqtype(n.Left.Type, c.node.Left.Type) { + yyerrorl(c.node.Lineno, "duplicate case %v in type switch\n\tprevious case at %v", c.node.Left.Type, n.Line()) + // avoid double-reporting errors + continue Outer } - setlineno(c2.node) - Yyerror("duplicate case %v in switch\n\tprevious case at %v", c1.node.Left, c1.node.Line()) } + seen[c.hash] = append(seen[c.hash], c.node) } +} +func checkDupExprCases(cc []caseClause) { + sort.Sort(caseClauseByExpr(cc)) + for i, c1 := range cc[:len(cc)-1] { + c2 := cc[i+1] + if exprcmp(c1, c2) != 0 { + continue + } + setlineno(c2.node) + Yyerror("duplicate case %v in switch\n\tprevious case at %v", c1.node.Left, c1.node.Line()) + } // put list back in processing order - sort.Sort(caseClauseByOrd(cc.list)) - return cc + sort.Sort(caseClauseByOrd(cc)) } // walk generates an AST that implements sw, @@ -801,18 +817,9 @@ func (x caseClauseByType) Len() int { return len(x) } func (x caseClauseByType) Swap(i, j int) { x[i], x[j] = x[j], x[i] } func (x caseClauseByType) Less(i, j int) bool { c1, c2 := x[i], x[j] - switch { - // sort non-constants last - case c1.typ != caseKindTypeConst: - return false - case c2.typ != caseKindTypeConst: - return true - - // sort by hash code - case c1.hash != c2.hash: + // sort by hash code, then ordinal (for the rare case of hash collisions) + if c1.hash != c2.hash { return c1.hash < c2.hash } - - // sort by ordinal return c1.ordinal < c2.ordinal } diff --git a/test/switch5.go b/test/switch5.go index 7da2c6641f..bb0f5e33ad 100644 --- a/test/switch5.go +++ b/test/switch5.go @@ -57,8 +57,8 @@ func f4(e interface{}) { case int: case int: // ERROR "duplicate case int in type switch" case int64: - case error: // ERROR "duplicate case error in type switch" case error: + case error: // ERROR "duplicate case error in type switch" case fmt.Stringer: case fmt.Stringer: // ERROR "duplicate case fmt.Stringer in type switch" case struct { -- 2.48.1