From 49dad0f5716484ec2f3b2e1480801c134933f1ab Mon Sep 17 00:00:00 2001 From: Matthew Dempsky Date: Thu, 25 Feb 2016 20:29:09 -0800 Subject: [PATCH] cmd/compile: support arbitrarily deep embedded fields Fixes #13337. Change-Id: Ie74d00390111796619150287d3f7a147750ab456 Reviewed-on: https://go-review.googlesource.com/19932 Reviewed-by: Ian Lance Taylor --- src/cmd/compile/internal/gc/go.go | 6 - src/cmd/compile/internal/gc/subr.go | 186 +++++++++++++++------------- test/fixedbugs/issue13337.go | 30 +++++ 3 files changed, 131 insertions(+), 91 deletions(-) create mode 100644 test/fixedbugs/issue13337.go diff --git a/src/cmd/compile/internal/gc/go.go b/src/cmd/compile/internal/gc/go.go index b5d3f3ec63..6dc31c3f48 100644 --- a/src/cmd/compile/internal/gc/go.go +++ b/src/cmd/compile/internal/gc/go.go @@ -192,10 +192,6 @@ type Sig struct { offset int32 } -type Dlist struct { - field *Type -} - // argument passing to/from // smagic and umagic type Magic struct { @@ -240,8 +236,6 @@ var sizeof_Array int // runtime sizeof(Array) // } String; var sizeof_String int // runtime sizeof(String) -var dotlist [10]Dlist // size is max depth of embeddeds - // lexlineno is the line number _after_ the most recently read rune. // In particular, it's advanced (or rewound) as newlines are read (or unread). var lexlineno int32 diff --git a/src/cmd/compile/internal/gc/subr.go b/src/cmd/compile/internal/gc/subr.go index ec98c356f3..48baacd9c5 100644 --- a/src/cmd/compile/internal/gc/subr.go +++ b/src/cmd/compile/internal/gc/subr.go @@ -1564,14 +1564,22 @@ func Setmaxarg(t *Type, extra int32) { } } -// unicode-aware case-insensitive strcmp +// Code to resolve elided DOTs in embedded types. -// code to resolve elided DOTs -// in embedded types +// A Dlist stores a pointer to a TFIELD Type embedded within +// a TSTRUCT or TINTER Type. +type Dlist struct { + field *Type +} + +// dotlist is used by adddot1 to record the path of embedded fields +// used to access a target field or method. +// Must be non-nil so that dotpath returns a non-nil slice even if d is zero. +var dotlist = make([]Dlist, 10) -// search depth 0 -- -// return count of fields+methods -// found with a given name +// lookdot0 returns the number of fields or methods named s associated +// with Type t. If exactly one exists, it will be returned in *save +// (if save is not nil). func lookdot0(s *Sym, t *Type, save **Type, ignorecase int) int { u := t if Isptr[u.Etype] { @@ -1605,26 +1613,30 @@ func lookdot0(s *Sym, t *Type, save **Type, ignorecase int) int { return c } -// search depth d for field/method s -- -// return count of fields+methods -// found at search depth. -// answer is in dotlist array and -// count of number of ways is returned. -func adddot1(s *Sym, t *Type, d int, save **Type, ignorecase int) int { +// adddot1 returns the number of fields or methods named s at depth d in Type t. +// If exactly one exists, it will be returned in *save (if save is not nil), +// and dotlist will contain the path of embedded fields traversed to find it, +// in reverse order. If none exist, more will indicate whether t contains any +// embedded fields at depth d, so callers can decide whether to retry at +// a greater depth. +func adddot1(s *Sym, t *Type, d int, save **Type, ignorecase int) (c int, more bool) { if t.Trecur != 0 { - return 0 + return } t.Trecur = 1 - var c int var u *Type - var a int - if d == 0 { + d-- + if d < 0 { + // We've reached our target depth. If t has any fields/methods + // named s, then we're done. Otherwise, we still need to check + // below for embedded fields. c = lookdot0(s, t, save, ignorecase) - goto out + if c != 0 { + goto out + } } - c = 0 u = t if Isptr[u.Etype] { u = u.Type @@ -1633,24 +1645,53 @@ func adddot1(s *Sym, t *Type, d int, save **Type, ignorecase int) int { goto out } - d-- for f := u.Type; f != nil; f = f.Down { - if f.Embedded == 0 { + if f.Embedded == 0 || f.Sym == nil { continue } - if f.Sym == nil { - continue + if d < 0 { + // Found an embedded field at target depth. + more = true + goto out } - a = adddot1(s, f.Type, d, save, ignorecase) + a, more1 := adddot1(s, f.Type, d, save, ignorecase) if a != 0 && c == 0 { dotlist[d].field = f } c += a + if more1 { + more = true + } } out: t.Trecur = 0 - return c + return c, more +} + +// dotpath computes the unique shortest explicit selector path to fully qualify +// a selection expression x.f, where x is of type t and f is the symbol s. +// If no such path exists, dotpath returns nil. +// If there are multiple shortest paths to the same depth, ambig is true. +func dotpath(s *Sym, t *Type, save **Type, ignorecase int) (path []Dlist, ambig bool) { + // The embedding of types within structs imposes a tree structure onto + // types: structs parent the types they embed, and types parent their + // fields or methods. Our goal here is to find the shortest path to + // a field or method named s in the subtree rooted at t. To accomplish + // that, we iteratively perform depth-first searches of increasing depth + // until we either find the named field/method or exhaust the tree. + for d := 0; ; d++ { + if d > len(dotlist) { + dotlist = append(dotlist, Dlist{}) + } + if c, more := adddot1(s, t, d, save, ignorecase); c == 1 { + return dotlist[:d], false + } else if c > 1 { + return nil, true + } else if !more { + return nil, false + } + } } // in T.field @@ -1677,24 +1718,16 @@ func adddot(n *Node) *Node { return n } - var c int - for d := 0; d < len(dotlist); d++ { - c = adddot1(s, t, d, nil, 0) - if c > 0 { - if c > 1 { - Yyerror("ambiguous selector %v", n) - n.Left = nil - return n - } - - // rebuild elided dots - for c := d - 1; c >= 0; c-- { - n.Left = Nod(ODOT, n.Left, newname(dotlist[c].field.Sym)) - n.Left.Implicit = true - } - - return n + switch path, ambig := dotpath(s, t, nil, 0); { + case path != nil: + // rebuild elided dots + for c := len(path) - 1; c >= 0; c-- { + n.Left = Nod(ODOT, n.Left, newname(path[c].field.Sym)) + n.Left.Implicit = true } + case ambig: + Yyerror("ambiguous selector %v", n) + n.Left = nil } return n @@ -1758,16 +1791,13 @@ func expand0(t *Type, followptr bool) { } } -func expand1(t *Type, d int, followptr bool) { +func expand1(t *Type, top, followptr bool) { if t.Trecur != 0 { return } - if d == 0 { - return - } t.Trecur = 1 - if d != len(dotlist)-1 { + if !top { expand0(t, followptr) } @@ -1788,7 +1818,7 @@ func expand1(t *Type, d int, followptr bool) { if f.Sym == nil { continue } - expand1(f.Type, d-1, followptr) + expand1(f.Type, false, followptr) } out: @@ -1810,27 +1840,18 @@ func expandmeth(t *Type) { // generate all reachable methods slist = nil - expand1(t, len(dotlist)-1, false) + expand1(t, true, false) // check each method to be uniquely reachable - var c int - var d int for sl := slist; sl != nil; sl = sl.link { sl.field.Sym.Flags &^= SymUniq - for d = 0; d < len(dotlist); d++ { - c = adddot1(sl.field.Sym, t, d, &f, 0) - if c == 0 { - continue - } - if c == 1 { - // addot1 may have dug out arbitrary fields, we only want methods. - if f.Type.Etype == TFUNC && f.Type.Thistuple > 0 { - sl.good = true - sl.field = f - } - } - - break + if path, _ := dotpath(sl.field.Sym, t, &f, 0); path == nil { + continue + } + // dotpath may have dug out arbitrary fields, we only want methods. + if f.Type.Etype == TFUNC && f.Type.Thistuple > 0 { + sl.good = true + sl.field = f } } @@ -1991,6 +2012,7 @@ func genwrapper(rcvr *Type, method *Type, newnam *Sym, iface int) { if !instrumenting && Isptr[rcvr.Etype] && Isptr[methodrcvr.Etype] && method.Embedded != 0 && !isifacemethod(method.Type) { // generate tail call: adjust pointer receiver and jump to embedded method. dot = dot.Left // skip final .M + // TODO(mdempsky): Remove dependency on dotlist. if !Isptr[dotlist[0].field.Type.Etype] { dot = Nod(OADDR, dot, nil) } @@ -2058,33 +2080,27 @@ func ifacelookdot(s *Sym, t *Type, followptr *bool, ignorecase int) *Type { } var m *Type - var i int - var c int - for d := 0; d < len(dotlist); d++ { - c = adddot1(s, t, d, &m, ignorecase) - if c > 1 { + path, ambig := dotpath(s, t, &m, ignorecase) + if path == nil { + if ambig { Yyerror("%v.%v is ambiguous", t, s) - return nil } + return nil + } - if c == 1 { - for i = 0; i < d; i++ { - if Isptr[dotlist[i].field.Type.Etype] { - *followptr = true - break - } - } - - if m.Type.Etype != TFUNC || m.Type.Thistuple == 0 { - Yyerror("%v.%v is a field, not a method", t, s) - return nil - } - - return m + for _, d := range path { + if Isptr[d.field.Type.Etype] { + *followptr = true + break } } - return nil + if m.Type.Etype != TFUNC || m.Type.Thistuple == 0 { + Yyerror("%v.%v is a field, not a method", t, s) + return nil + } + + return m } func implements(t *Type, iface *Type, m **Type, samename **Type, ptr *int) bool { diff --git a/test/fixedbugs/issue13337.go b/test/fixedbugs/issue13337.go new file mode 100644 index 0000000000..63f4efca8a --- /dev/null +++ b/test/fixedbugs/issue13337.go @@ -0,0 +1,30 @@ +// compile + +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Issue 13337: The Go compiler limited how deeply embedded types +// were searched for promoted fields and methods. + +package s + +type S0 struct{ f int } +func (S0) m() {} + +type S1 struct{ S0 } +type S2 struct{ S1 } +type S3 struct{ S2 } +type S4 struct{ S3 } +type S5 struct{ S4 } +type S6 struct{ S5 } +type S7 struct{ S6 } +type S8 struct{ S7 } +type S9 struct{ S8 } +type S10 struct{ S9 } +type S11 struct{ S10 } +type S12 struct{ S11 } +type S13 struct{ S12 } + +var _ = S13{}.f +var _ = S13.m -- 2.48.1