Source file src/pkg/cmd/compile/internal/gc/swt.go

     1	// Copyright 2009 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 gc
     6	
     7	import (
     8		"cmd/compile/internal/types"
     9		"fmt"
    10		"sort"
    11	)
    12	
    13	const (
    14		// expression switch
    15		switchKindExpr  = iota // switch a {...} or switch 5 {...}
    16		switchKindTrue         // switch true {...} or switch {...}
    17		switchKindFalse        // switch false {...}
    18	)
    19	
    20	const (
    21		binarySearchMin = 4 // minimum number of cases for binary search
    22		integerRangeMin = 2 // minimum size of integer ranges
    23	)
    24	
    25	// An exprSwitch walks an expression switch.
    26	type exprSwitch struct {
    27		exprname *Node // node for the expression being switched on
    28		kind     int   // kind of switch statement (switchKind*)
    29	}
    30	
    31	// A typeSwitch walks a type switch.
    32	type typeSwitch struct {
    33		hashname *Node // node for the hash of the type of the variable being switched on
    34		facename *Node // node for the concrete type of the variable being switched on
    35		okname   *Node // boolean node used for comma-ok type assertions
    36	}
    37	
    38	// A caseClause is a single case clause in a switch statement.
    39	type caseClause struct {
    40		node    *Node  // points at case statement
    41		ordinal int    // position in switch
    42		hash    uint32 // hash of a type switch
    43		// isconst indicates whether this case clause is a constant,
    44		// for the purposes of the switch code generation.
    45		// For expression switches, that's generally literals (case 5:, not case x:).
    46		// For type switches, that's concrete types (case time.Time:), not interfaces (case io.Reader:).
    47		isconst bool
    48	}
    49	
    50	// caseClauses are all the case clauses in a switch statement.
    51	type caseClauses struct {
    52		list   []caseClause // general cases
    53		defjmp *Node        // OGOTO for default case or OBREAK if no default case present
    54		niljmp *Node        // OGOTO for nil type case in a type switch
    55	}
    56	
    57	// typecheckswitch typechecks a switch statement.
    58	func typecheckswitch(n *Node) {
    59		typecheckslice(n.Ninit.Slice(), ctxStmt)
    60	
    61		var nilonly string
    62		var top int
    63		var t *types.Type
    64	
    65		if n.Left != nil && n.Left.Op == OTYPESW {
    66			// type switch
    67			top = Etype
    68			n.Left.Right = typecheck(n.Left.Right, ctxExpr)
    69			t = n.Left.Right.Type
    70			if t != nil && !t.IsInterface() {
    71				yyerrorl(n.Pos, "cannot type switch on non-interface value %L", n.Left.Right)
    72			}
    73			if v := n.Left.Left; v != nil && !v.isBlank() && n.List.Len() == 0 {
    74				// We don't actually declare the type switch's guarded
    75				// declaration itself. So if there are no cases, we
    76				// won't notice that it went unused.
    77				yyerrorl(v.Pos, "%v declared and not used", v.Sym)
    78			}
    79		} else {
    80			// expression switch
    81			top = ctxExpr
    82			if n.Left != nil {
    83				n.Left = typecheck(n.Left, ctxExpr)
    84				n.Left = defaultlit(n.Left, nil)
    85				t = n.Left.Type
    86			} else {
    87				t = types.Types[TBOOL]
    88			}
    89			if t != nil {
    90				switch {
    91				case !okforeq[t.Etype]:
    92					yyerrorl(n.Pos, "cannot switch on %L", n.Left)
    93				case t.IsSlice():
    94					nilonly = "slice"
    95				case t.IsArray() && !IsComparable(t):
    96					yyerrorl(n.Pos, "cannot switch on %L", n.Left)
    97				case t.IsStruct():
    98					if f := IncomparableField(t); f != nil {
    99						yyerrorl(n.Pos, "cannot switch on %L (struct containing %v cannot be compared)", n.Left, f.Type)
   100					}
   101				case t.Etype == TFUNC:
   102					nilonly = "func"
   103				case t.IsMap():
   104					nilonly = "map"
   105				}
   106			}
   107		}
   108	
   109		n.Type = t
   110	
   111		var def, niltype *Node
   112		for _, ncase := range n.List.Slice() {
   113			if ncase.List.Len() == 0 {
   114				// default
   115				if def != nil {
   116					setlineno(ncase)
   117					yyerrorl(ncase.Pos, "multiple defaults in switch (first at %v)", def.Line())
   118				} else {
   119					def = ncase
   120				}
   121			} else {
   122				ls := ncase.List.Slice()
   123				for i1, n1 := range ls {
   124					setlineno(n1)
   125					ls[i1] = typecheck(ls[i1], ctxExpr|Etype)
   126					n1 = ls[i1]
   127					if n1.Type == nil || t == nil {
   128						continue
   129					}
   130	
   131					setlineno(ncase)
   132					switch top {
   133					// expression switch
   134					case ctxExpr:
   135						ls[i1] = defaultlit(ls[i1], t)
   136						n1 = ls[i1]
   137						switch {
   138						case n1.Op == OTYPE:
   139							yyerrorl(ncase.Pos, "type %v is not an expression", n1.Type)
   140						case n1.Type != nil && assignop(n1.Type, t, nil) == 0 && assignop(t, n1.Type, nil) == 0:
   141							if n.Left != nil {
   142								yyerrorl(ncase.Pos, "invalid case %v in switch on %v (mismatched types %v and %v)", n1, n.Left, n1.Type, t)
   143							} else {
   144								yyerrorl(ncase.Pos, "invalid case %v in switch (mismatched types %v and bool)", n1, n1.Type)
   145							}
   146						case nilonly != "" && !n1.isNil():
   147							yyerrorl(ncase.Pos, "invalid case %v in switch (can only compare %s %v to nil)", n1, nilonly, n.Left)
   148						case t.IsInterface() && !n1.Type.IsInterface() && !IsComparable(n1.Type):
   149							yyerrorl(ncase.Pos, "invalid case %L in switch (incomparable type)", n1)
   150						}
   151	
   152					// type switch
   153					case Etype:
   154						var missing, have *types.Field
   155						var ptr int
   156						switch {
   157						case n1.Op == OLITERAL && n1.Type.IsKind(TNIL):
   158							// case nil:
   159							if niltype != nil {
   160								yyerrorl(ncase.Pos, "multiple nil cases in type switch (first at %v)", niltype.Line())
   161							} else {
   162								niltype = ncase
   163							}
   164						case n1.Op != OTYPE && n1.Type != nil: // should this be ||?
   165							yyerrorl(ncase.Pos, "%L is not a type", n1)
   166							// reset to original type
   167							n1 = n.Left.Right
   168							ls[i1] = n1
   169						case !n1.Type.IsInterface() && t.IsInterface() && !implements(n1.Type, t, &missing, &have, &ptr):
   170							if have != nil && !missing.Broke() && !have.Broke() {
   171								yyerrorl(ncase.Pos, "impossible type switch case: %L cannot have dynamic type %v"+
   172									" (wrong type for %v method)\n\thave %v%S\n\twant %v%S", n.Left.Right, n1.Type, missing.Sym, have.Sym, have.Type, missing.Sym, missing.Type)
   173							} else if !missing.Broke() {
   174								if ptr != 0 {
   175									yyerrorl(ncase.Pos, "impossible type switch case: %L cannot have dynamic type %v"+
   176										" (%v method has pointer receiver)", n.Left.Right, n1.Type, missing.Sym)
   177								} else {
   178									yyerrorl(ncase.Pos, "impossible type switch case: %L cannot have dynamic type %v"+
   179										" (missing %v method)", n.Left.Right, n1.Type, missing.Sym)
   180								}
   181							}
   182						}
   183					}
   184				}
   185			}
   186	
   187			if top == Etype {
   188				ll := ncase.List
   189				if ncase.Rlist.Len() != 0 {
   190					nvar := ncase.Rlist.First()
   191					if ll.Len() == 1 && (ll.First().Type == nil || !ll.First().Type.IsKind(TNIL)) {
   192						// single entry type switch
   193						nvar.Type = ll.First().Type
   194					} else {
   195						// multiple entry type switch or default
   196						nvar.Type = n.Type
   197					}
   198	
   199					if nvar.Type == nil || nvar.Type.IsUntyped() {
   200						// if the value we're switching on has no type or is untyped,
   201						// we've already printed an error and don't need to continue
   202						// typechecking the body
   203						continue
   204					}
   205	
   206					nvar = typecheck(nvar, ctxExpr|ctxAssign)
   207					ncase.Rlist.SetFirst(nvar)
   208				}
   209			}
   210	
   211			typecheckslice(ncase.Nbody.Slice(), ctxStmt)
   212		}
   213		switch top {
   214		// expression switch
   215		case ctxExpr:
   216			checkDupExprCases(n.Left, n.List.Slice())
   217		}
   218	}
   219	
   220	// walkswitch walks a switch statement.
   221	func walkswitch(sw *Node) {
   222		// convert switch {...} to switch true {...}
   223		if sw.Left == nil {
   224			sw.Left = nodbool(true)
   225			sw.Left = typecheck(sw.Left, ctxExpr)
   226			sw.Left = defaultlit(sw.Left, nil)
   227		}
   228	
   229		if sw.Left.Op == OTYPESW {
   230			var s typeSwitch
   231			s.walk(sw)
   232		} else {
   233			var s exprSwitch
   234			s.walk(sw)
   235		}
   236	}
   237	
   238	// walk generates an AST implementing sw.
   239	// sw is an expression switch.
   240	// The AST is generally of the form of a linear
   241	// search using if..goto, although binary search
   242	// is used with long runs of constants.
   243	func (s *exprSwitch) walk(sw *Node) {
   244		// Guard against double walk, see #25776.
   245		if sw.List.Len() == 0 && sw.Nbody.Len() > 0 {
   246			return // Was fatal, but eliminating every possible source of double-walking is hard
   247		}
   248	
   249		casebody(sw, nil)
   250	
   251		cond := sw.Left
   252		sw.Left = nil
   253	
   254		s.kind = switchKindExpr
   255		if Isconst(cond, CTBOOL) {
   256			s.kind = switchKindTrue
   257			if !cond.Val().U.(bool) {
   258				s.kind = switchKindFalse
   259			}
   260		}
   261	
   262		// Given "switch string(byteslice)",
   263		// with all cases being constants (or the default case),
   264		// use a zero-cost alias of the byte slice.
   265		// In theory, we could be more aggressive,
   266		// allowing any side-effect-free expressions in cases,
   267		// but it's a bit tricky because some of that information
   268		// is unavailable due to the introduction of temporaries during order.
   269		// Restricting to constants is simple and probably powerful enough.
   270		// Do this before calling walkexpr on cond,
   271		// because walkexpr will lower the string
   272		// conversion into a runtime call.
   273		// See issue 24937 for more discussion.
   274		if cond.Op == OBYTES2STR {
   275			ok := true
   276			for _, cas := range sw.List.Slice() {
   277				if cas.Op != OCASE {
   278					Fatalf("switch string(byteslice) bad op: %v", cas.Op)
   279				}
   280				if cas.Left != nil && !Isconst(cas.Left, CTSTR) {
   281					ok = false
   282					break
   283				}
   284			}
   285			if ok {
   286				cond.Op = OBYTES2STRTMP
   287			}
   288		}
   289	
   290		cond = walkexpr(cond, &sw.Ninit)
   291		t := sw.Type
   292		if t == nil {
   293			return
   294		}
   295	
   296		// convert the switch into OIF statements
   297		var cas []*Node
   298		if s.kind == switchKindTrue || s.kind == switchKindFalse {
   299			s.exprname = nodbool(s.kind == switchKindTrue)
   300		} else if consttype(cond) > 0 {
   301			// leave constants to enable dead code elimination (issue 9608)
   302			s.exprname = cond
   303		} else {
   304			s.exprname = temp(cond.Type)
   305			cas = []*Node{nod(OAS, s.exprname, cond)} // This gets walk()ed again in walkstmtlist just before end of this function.  See #29562.
   306			typecheckslice(cas, ctxStmt)
   307		}
   308	
   309		// Enumerate the cases and prepare the default case.
   310		clauses := s.genCaseClauses(sw.List.Slice())
   311		sw.List.Set(nil)
   312		cc := clauses.list
   313	
   314		// handle the cases in order
   315		for len(cc) > 0 {
   316			run := 1
   317			if okforcmp[t.Etype] && cc[0].isconst {
   318				// do binary search on runs of constants
   319				for ; run < len(cc) && cc[run].isconst; run++ {
   320				}
   321				// sort and compile constants
   322				sort.Sort(caseClauseByConstVal(cc[:run]))
   323			}
   324	
   325			a := s.walkCases(cc[:run])
   326			cas = append(cas, a)
   327			cc = cc[run:]
   328		}
   329	
   330		// handle default case
   331		if nerrors == 0 {
   332			cas = append(cas, clauses.defjmp)
   333			sw.Nbody.Prepend(cas...)
   334			walkstmtlist(sw.Nbody.Slice())
   335		}
   336	}
   337	
   338	// walkCases generates an AST implementing the cases in cc.
   339	func (s *exprSwitch) walkCases(cc []caseClause) *Node {
   340		if len(cc) < binarySearchMin {
   341			// linear search
   342			var cas []*Node
   343			for _, c := range cc {
   344				n := c.node
   345				lno := setlineno(n)
   346	
   347				a := nod(OIF, nil, nil)
   348				if rng := n.List.Slice(); rng != nil {
   349					// Integer range.
   350					// exprname is a temp or a constant,
   351					// so it is safe to evaluate twice.
   352					// In most cases, this conjunction will be
   353					// rewritten by walkinrange into a single comparison.
   354					low := nod(OGE, s.exprname, rng[0])
   355					high := nod(OLE, s.exprname, rng[1])
   356					a.Left = nod(OANDAND, low, high)
   357				} else if (s.kind != switchKindTrue && s.kind != switchKindFalse) || assignop(n.Left.Type, s.exprname.Type, nil) == OCONVIFACE || assignop(s.exprname.Type, n.Left.Type, nil) == OCONVIFACE {
   358					a.Left = nod(OEQ, s.exprname, n.Left) // if name == val
   359				} else if s.kind == switchKindTrue {
   360					a.Left = n.Left // if val
   361				} else {
   362					// s.kind == switchKindFalse
   363					a.Left = nod(ONOT, n.Left, nil) // if !val
   364				}
   365				a.Left = typecheck(a.Left, ctxExpr)
   366				a.Left = defaultlit(a.Left, nil)
   367				a.Nbody.Set1(n.Right) // goto l
   368	
   369				cas = append(cas, a)
   370				lineno = lno
   371			}
   372			return liststmt(cas)
   373		}
   374	
   375		// find the middle and recur
   376		half := len(cc) / 2
   377		a := nod(OIF, nil, nil)
   378		n := cc[half-1].node
   379		var mid *Node
   380		if rng := n.List.Slice(); rng != nil {
   381			mid = rng[1] // high end of range
   382		} else {
   383			mid = n.Left
   384		}
   385		le := nod(OLE, s.exprname, mid)
   386		if Isconst(mid, CTSTR) {
   387			// Search by length and then by value; see caseClauseByConstVal.
   388			lenlt := nod(OLT, nod(OLEN, s.exprname, nil), nod(OLEN, mid, nil))
   389			leneq := nod(OEQ, nod(OLEN, s.exprname, nil), nod(OLEN, mid, nil))
   390			a.Left = nod(OOROR, lenlt, nod(OANDAND, leneq, le))
   391		} else {
   392			a.Left = le
   393		}
   394		a.Left = typecheck(a.Left, ctxExpr)
   395		a.Left = defaultlit(a.Left, nil)
   396		a.Nbody.Set1(s.walkCases(cc[:half]))
   397		a.Rlist.Set1(s.walkCases(cc[half:]))
   398		return a
   399	}
   400	
   401	// casebody builds separate lists of statements and cases.
   402	// It makes labels between cases and statements
   403	// and deals with fallthrough, break, and unreachable statements.
   404	func casebody(sw *Node, typeswvar *Node) {
   405		if sw.List.Len() == 0 {
   406			return
   407		}
   408	
   409		lno := setlineno(sw)
   410	
   411		var cas []*Node  // cases
   412		var stat []*Node // statements
   413		var def *Node    // defaults
   414		br := nod(OBREAK, nil, nil)
   415	
   416		for _, n := range sw.List.Slice() {
   417			setlineno(n)
   418			if n.Op != OXCASE {
   419				Fatalf("casebody %v", n.Op)
   420			}
   421			n.Op = OCASE
   422			needvar := n.List.Len() != 1 || n.List.First().Op == OLITERAL
   423	
   424			lbl := autolabel(".s")
   425			jmp := nodSym(OGOTO, nil, lbl)
   426			switch n.List.Len() {
   427			case 0:
   428				// default
   429				if def != nil {
   430					yyerrorl(n.Pos, "more than one default case")
   431				}
   432				// reuse original default case
   433				n.Right = jmp
   434				def = n
   435			case 1:
   436				// one case -- reuse OCASE node
   437				n.Left = n.List.First()
   438				n.Right = jmp
   439				n.List.Set(nil)
   440				cas = append(cas, n)
   441			default:
   442				// Expand multi-valued cases and detect ranges of integer cases.
   443				if typeswvar != nil || sw.Left.Type.IsInterface() || !n.List.First().Type.IsInteger() || n.List.Len() < integerRangeMin {
   444					// Can't use integer ranges. Expand each case into a separate node.
   445					for _, n1 := range n.List.Slice() {
   446						cas = append(cas, nod(OCASE, n1, jmp))
   447					}
   448					break
   449				}
   450				// Find integer ranges within runs of constants.
   451				s := n.List.Slice()
   452				j := 0
   453				for j < len(s) {
   454					// Find a run of constants.
   455					var run int
   456					for run = j; run < len(s) && Isconst(s[run], CTINT); run++ {
   457					}
   458					if run-j >= integerRangeMin {
   459						// Search for integer ranges in s[j:run].
   460						// Typechecking is done, so all values are already in an appropriate range.
   461						search := s[j:run]
   462						sort.Sort(constIntNodesByVal(search))
   463						for beg, end := 0, 1; end <= len(search); end++ {
   464							if end < len(search) && search[end].Int64() == search[end-1].Int64()+1 {
   465								continue
   466							}
   467							if end-beg >= integerRangeMin {
   468								// Record range in List.
   469								c := nod(OCASE, nil, jmp)
   470								c.List.Set2(search[beg], search[end-1])
   471								cas = append(cas, c)
   472							} else {
   473								// Not large enough for range; record separately.
   474								for _, n := range search[beg:end] {
   475									cas = append(cas, nod(OCASE, n, jmp))
   476								}
   477							}
   478							beg = end
   479						}
   480						j = run
   481					}
   482					// Advance to next constant, adding individual non-constant
   483					// or as-yet-unhandled constant cases as we go.
   484					for ; j < len(s) && (j < run || !Isconst(s[j], CTINT)); j++ {
   485						cas = append(cas, nod(OCASE, s[j], jmp))
   486					}
   487				}
   488			}
   489	
   490			stat = append(stat, nodSym(OLABEL, nil, lbl))
   491			if typeswvar != nil && needvar && n.Rlist.Len() != 0 {
   492				l := []*Node{
   493					nod(ODCL, n.Rlist.First(), nil),
   494					nod(OAS, n.Rlist.First(), typeswvar),
   495				}
   496				typecheckslice(l, ctxStmt)
   497				stat = append(stat, l...)
   498			}
   499			stat = append(stat, n.Nbody.Slice()...)
   500	
   501			// Search backwards for the index of the fallthrough
   502			// statement. Do not assume it'll be in the last
   503			// position, since in some cases (e.g. when the statement
   504			// list contains autotmp_ variables), one or more OVARKILL
   505			// nodes will be at the end of the list.
   506			fallIndex := len(stat) - 1
   507			for stat[fallIndex].Op == OVARKILL {
   508				fallIndex--
   509			}
   510			last := stat[fallIndex]
   511			if last.Op != OFALL {
   512				stat = append(stat, br)
   513			}
   514		}
   515	
   516		stat = append(stat, br)
   517		if def != nil {
   518			cas = append(cas, def)
   519		}
   520	
   521		sw.List.Set(cas)
   522		sw.Nbody.Set(stat)
   523		lineno = lno
   524	}
   525	
   526	// genCaseClauses generates the caseClauses value for clauses.
   527	func (s *exprSwitch) genCaseClauses(clauses []*Node) caseClauses {
   528		var cc caseClauses
   529		for _, n := range clauses {
   530			if n.Left == nil && n.List.Len() == 0 {
   531				// default case
   532				if cc.defjmp != nil {
   533					Fatalf("duplicate default case not detected during typechecking")
   534				}
   535				cc.defjmp = n.Right
   536				continue
   537			}
   538			c := caseClause{node: n, ordinal: len(cc.list)}
   539			if n.List.Len() > 0 {
   540				c.isconst = true
   541			}
   542			switch consttype(n.Left) {
   543			case CTFLT, CTINT, CTRUNE, CTSTR:
   544				c.isconst = true
   545			}
   546			cc.list = append(cc.list, c)
   547		}
   548	
   549		if cc.defjmp == nil {
   550			cc.defjmp = nod(OBREAK, nil, nil)
   551		}
   552		return cc
   553	}
   554	
   555	// genCaseClauses generates the caseClauses value for clauses.
   556	func (s *typeSwitch) genCaseClauses(clauses []*Node) caseClauses {
   557		var cc caseClauses
   558		for _, n := range clauses {
   559			switch {
   560			case n.Left == nil:
   561				// default case
   562				if cc.defjmp != nil {
   563					Fatalf("duplicate default case not detected during typechecking")
   564				}
   565				cc.defjmp = n.Right
   566				continue
   567			case n.Left.Op == OLITERAL:
   568				// nil case in type switch
   569				if cc.niljmp != nil {
   570					Fatalf("duplicate nil case not detected during typechecking")
   571				}
   572				cc.niljmp = n.Right
   573				continue
   574			}
   575	
   576			// general case
   577			c := caseClause{
   578				node:    n,
   579				ordinal: len(cc.list),
   580				isconst: !n.Left.Type.IsInterface(),
   581				hash:    typehash(n.Left.Type),
   582			}
   583			cc.list = append(cc.list, c)
   584		}
   585	
   586		if cc.defjmp == nil {
   587			cc.defjmp = nod(OBREAK, nil, nil)
   588		}
   589	
   590		// diagnose duplicate cases
   591		s.checkDupCases(cc.list)
   592		return cc
   593	}
   594	
   595	func (s *typeSwitch) checkDupCases(cc []caseClause) {
   596		if len(cc) < 2 {
   597			return
   598		}
   599		// We store seen types in a map keyed by type hash.
   600		// It is possible, but very unlikely, for multiple distinct types to have the same hash.
   601		seen := make(map[uint32][]*Node)
   602		// To avoid many small allocations of length 1 slices,
   603		// also set up a single large slice to slice into.
   604		nn := make([]*Node, 0, len(cc))
   605	Outer:
   606		for _, c := range cc {
   607			prev, ok := seen[c.hash]
   608			if !ok {
   609				// First entry for this hash.
   610				nn = append(nn, c.node)
   611				seen[c.hash] = nn[len(nn)-1 : len(nn) : len(nn)]
   612				continue
   613			}
   614			for _, n := range prev {
   615				if types.Identical(n.Left.Type, c.node.Left.Type) {
   616					yyerrorl(c.node.Pos, "duplicate case %v in type switch\n\tprevious case at %v", c.node.Left.Type, n.Line())
   617					// avoid double-reporting errors
   618					continue Outer
   619				}
   620			}
   621			seen[c.hash] = append(seen[c.hash], c.node)
   622		}
   623	}
   624	
   625	func checkDupExprCases(exprname *Node, clauses []*Node) {
   626		// boolean (naked) switch, nothing to do.
   627		if exprname == nil {
   628			return
   629		}
   630	
   631		var cs constSet
   632		for _, ncase := range clauses {
   633			for _, n := range ncase.List.Slice() {
   634				// Don't check for duplicate bools. Although the spec allows it,
   635				// (1) the compiler hasn't checked it in the past, so compatibility mandates it, and
   636				// (2) it would disallow useful things like
   637				//       case GOARCH == "arm" && GOARM == "5":
   638				//       case GOARCH == "arm":
   639				//     which would both evaluate to false for non-ARM compiles.
   640				if n.Type.IsBoolean() {
   641					continue
   642				}
   643	
   644				if prev := cs.add(n); prev != nil {
   645					yyerrorl(ncase.Pos, "duplicate case %s in switch\n\tprevious case at %v",
   646						nodeAndVal(n), prev.Line())
   647				}
   648			}
   649		}
   650	}
   651	
   652	func nodeAndVal(n *Node) string {
   653		show := n.String()
   654		val := n.Val().Interface()
   655		if s := fmt.Sprintf("%#v", val); show != s {
   656			show += " (value " + s + ")"
   657		}
   658		return show
   659	}
   660	
   661	// walk generates an AST that implements sw,
   662	// where sw is a type switch.
   663	// The AST is generally of the form of a linear
   664	// search using if..goto, although binary search
   665	// is used with long runs of concrete types.
   666	func (s *typeSwitch) walk(sw *Node) {
   667		cond := sw.Left
   668		sw.Left = nil
   669	
   670		if cond == nil {
   671			sw.List.Set(nil)
   672			return
   673		}
   674		if cond.Right == nil {
   675			yyerrorl(sw.Pos, "type switch must have an assignment")
   676			return
   677		}
   678	
   679		cond.Right = walkexpr(cond.Right, &sw.Ninit)
   680		if !cond.Right.Type.IsInterface() {
   681			yyerrorl(sw.Pos, "type switch must be on an interface")
   682			return
   683		}
   684	
   685		var cas []*Node
   686	
   687		// predeclare temporary variables and the boolean var
   688		s.facename = temp(cond.Right.Type)
   689	
   690		a := nod(OAS, s.facename, cond.Right)
   691		a = typecheck(a, ctxStmt)
   692		cas = append(cas, a)
   693	
   694		s.okname = temp(types.Types[TBOOL])
   695		s.okname = typecheck(s.okname, ctxExpr)
   696	
   697		s.hashname = temp(types.Types[TUINT32])
   698		s.hashname = typecheck(s.hashname, ctxExpr)
   699	
   700		// set up labels and jumps
   701		casebody(sw, s.facename)
   702	
   703		clauses := s.genCaseClauses(sw.List.Slice())
   704		sw.List.Set(nil)
   705		def := clauses.defjmp
   706	
   707		// For empty interfaces, do:
   708		//     if e._type == nil {
   709		//         do nil case if it exists, otherwise default
   710		//     }
   711		//     h := e._type.hash
   712		// Use a similar strategy for non-empty interfaces.
   713	
   714		// Get interface descriptor word.
   715		// For empty interfaces this will be the type.
   716		// For non-empty interfaces this will be the itab.
   717		itab := nod(OITAB, s.facename, nil)
   718	
   719		// Check for nil first.
   720		i := nod(OIF, nil, nil)
   721		i.Left = nod(OEQ, itab, nodnil())
   722		if clauses.niljmp != nil {
   723			// Do explicit nil case right here.
   724			i.Nbody.Set1(clauses.niljmp)
   725		} else {
   726			// Jump to default case.
   727			lbl := autolabel(".s")
   728			i.Nbody.Set1(nodSym(OGOTO, nil, lbl))
   729			// Wrap default case with label.
   730			blk := nod(OBLOCK, nil, nil)
   731			blk.List.Set2(nodSym(OLABEL, nil, lbl), def)
   732			def = blk
   733		}
   734		i.Left = typecheck(i.Left, ctxExpr)
   735		i.Left = defaultlit(i.Left, nil)
   736		cas = append(cas, i)
   737	
   738		// Load hash from type or itab.
   739		h := nodSym(ODOTPTR, itab, nil)
   740		h.Type = types.Types[TUINT32]
   741		h.SetTypecheck(1)
   742		if cond.Right.Type.IsEmptyInterface() {
   743			h.Xoffset = int64(2 * Widthptr) // offset of hash in runtime._type
   744		} else {
   745			h.Xoffset = int64(2 * Widthptr) // offset of hash in runtime.itab
   746		}
   747		h.SetBounded(true) // guaranteed not to fault
   748		a = nod(OAS, s.hashname, h)
   749		a = typecheck(a, ctxStmt)
   750		cas = append(cas, a)
   751	
   752		cc := clauses.list
   753	
   754		// insert type equality check into each case block
   755		for _, c := range cc {
   756			c.node.Right = s.typeone(c.node)
   757		}
   758	
   759		// generate list of if statements, binary search for constant sequences
   760		for len(cc) > 0 {
   761			if !cc[0].isconst {
   762				n := cc[0].node
   763				cas = append(cas, n.Right)
   764				cc = cc[1:]
   765				continue
   766			}
   767	
   768			// identify run of constants
   769			var run int
   770			for run = 1; run < len(cc) && cc[run].isconst; run++ {
   771			}
   772	
   773			// sort by hash
   774			sort.Sort(caseClauseByType(cc[:run]))
   775	
   776			// for debugging: linear search
   777			if false {
   778				for i := 0; i < run; i++ {
   779					n := cc[i].node
   780					cas = append(cas, n.Right)
   781				}
   782				continue
   783			}
   784	
   785			// combine adjacent cases with the same hash
   786			var batch []caseClause
   787			for i, j := 0, 0; i < run; i = j {
   788				hash := []*Node{cc[i].node.Right}
   789				for j = i + 1; j < run && cc[i].hash == cc[j].hash; j++ {
   790					hash = append(hash, cc[j].node.Right)
   791				}
   792				cc[i].node.Right = liststmt(hash)
   793				batch = append(batch, cc[i])
   794			}
   795	
   796			// binary search among cases to narrow by hash
   797			cas = append(cas, s.walkCases(batch))
   798			cc = cc[run:]
   799		}
   800	
   801		// handle default case
   802		if nerrors == 0 {
   803			cas = append(cas, def)
   804			sw.Nbody.Prepend(cas...)
   805			sw.List.Set(nil)
   806			walkstmtlist(sw.Nbody.Slice())
   807		}
   808	}
   809	
   810	// typeone generates an AST that jumps to the
   811	// case body if the variable is of type t.
   812	func (s *typeSwitch) typeone(t *Node) *Node {
   813		var name *Node
   814		var init Nodes
   815		if t.Rlist.Len() == 0 {
   816			name = nblank
   817			nblank = typecheck(nblank, ctxExpr|ctxAssign)
   818		} else {
   819			name = t.Rlist.First()
   820			init.Append(nod(ODCL, name, nil))
   821			a := nod(OAS, name, nil)
   822			a = typecheck(a, ctxStmt)
   823			init.Append(a)
   824		}
   825	
   826		a := nod(OAS2, nil, nil)
   827		a.List.Set2(name, s.okname) // name, ok =
   828		b := nod(ODOTTYPE, s.facename, nil)
   829		b.Type = t.Left.Type // interface.(type)
   830		a.Rlist.Set1(b)
   831		a = typecheck(a, ctxStmt)
   832		a = walkexpr(a, &init)
   833		init.Append(a)
   834	
   835		c := nod(OIF, nil, nil)
   836		c.Left = s.okname
   837		c.Nbody.Set1(t.Right) // if ok { goto l }
   838	
   839		init.Append(c)
   840		return init.asblock()
   841	}
   842	
   843	// walkCases generates an AST implementing the cases in cc.
   844	func (s *typeSwitch) walkCases(cc []caseClause) *Node {
   845		if len(cc) < binarySearchMin {
   846			var cas []*Node
   847			for _, c := range cc {
   848				n := c.node
   849				if !c.isconst {
   850					Fatalf("typeSwitch walkCases")
   851				}
   852				a := nod(OIF, nil, nil)
   853				a.Left = nod(OEQ, s.hashname, nodintconst(int64(c.hash)))
   854				a.Left = typecheck(a.Left, ctxExpr)
   855				a.Left = defaultlit(a.Left, nil)
   856				a.Nbody.Set1(n.Right)
   857				cas = append(cas, a)
   858			}
   859			return liststmt(cas)
   860		}
   861	
   862		// find the middle and recur
   863		half := len(cc) / 2
   864		a := nod(OIF, nil, nil)
   865		a.Left = nod(OLE, s.hashname, nodintconst(int64(cc[half-1].hash)))
   866		a.Left = typecheck(a.Left, ctxExpr)
   867		a.Left = defaultlit(a.Left, nil)
   868		a.Nbody.Set1(s.walkCases(cc[:half]))
   869		a.Rlist.Set1(s.walkCases(cc[half:]))
   870		return a
   871	}
   872	
   873	// caseClauseByConstVal sorts clauses by constant value to enable binary search.
   874	type caseClauseByConstVal []caseClause
   875	
   876	func (x caseClauseByConstVal) Len() int      { return len(x) }
   877	func (x caseClauseByConstVal) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
   878	func (x caseClauseByConstVal) Less(i, j int) bool {
   879		// n1 and n2 might be individual constants or integer ranges.
   880		// We have checked for duplicates already,
   881		// so ranges can be safely represented by any value in the range.
   882		n1 := x[i].node
   883		var v1 interface{}
   884		if s := n1.List.Slice(); s != nil {
   885			v1 = s[0].Val().U
   886		} else {
   887			v1 = n1.Left.Val().U
   888		}
   889	
   890		n2 := x[j].node
   891		var v2 interface{}
   892		if s := n2.List.Slice(); s != nil {
   893			v2 = s[0].Val().U
   894		} else {
   895			v2 = n2.Left.Val().U
   896		}
   897	
   898		switch v1 := v1.(type) {
   899		case *Mpflt:
   900			return v1.Cmp(v2.(*Mpflt)) < 0
   901		case *Mpint:
   902			return v1.Cmp(v2.(*Mpint)) < 0
   903		case string:
   904			// Sort strings by length and then by value.
   905			// It is much cheaper to compare lengths than values,
   906			// and all we need here is consistency.
   907			// We respect this sorting in exprSwitch.walkCases.
   908			a := v1
   909			b := v2.(string)
   910			if len(a) != len(b) {
   911				return len(a) < len(b)
   912			}
   913			return a < b
   914		}
   915	
   916		Fatalf("caseClauseByConstVal passed bad clauses %v < %v", x[i].node.Left, x[j].node.Left)
   917		return false
   918	}
   919	
   920	type caseClauseByType []caseClause
   921	
   922	func (x caseClauseByType) Len() int      { return len(x) }
   923	func (x caseClauseByType) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
   924	func (x caseClauseByType) Less(i, j int) bool {
   925		c1, c2 := x[i], x[j]
   926		// sort by hash code, then ordinal (for the rare case of hash collisions)
   927		if c1.hash != c2.hash {
   928			return c1.hash < c2.hash
   929		}
   930		return c1.ordinal < c2.ordinal
   931	}
   932	
   933	type constIntNodesByVal []*Node
   934	
   935	func (x constIntNodesByVal) Len() int      { return len(x) }
   936	func (x constIntNodesByVal) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
   937	func (x constIntNodesByVal) Less(i, j int) bool {
   938		return x[i].Val().U.(*Mpint).Cmp(x[j].Val().U.(*Mpint)) < 0
   939	}
   940	

View as plain text