From 156eeb40a6d918bcac82871af1b8e428a5414159 Mon Sep 17 00:00:00 2001 From: Dan Scales Date: Sun, 1 Aug 2021 20:29:07 -0700 Subject: [dev.typeparams] cmd/compile: make HasShape() more efficient by implementing with a type flag Implement HasShape() similar to how HasTParam() is implemented. Fixes #47456 Change-Id: Icbd538574237faad2c4cd8c8e187725a1df47637 Reviewed-on: https://go-review.googlesource.com/c/go/+/339029 Reviewed-by: Keith Randall Trust: Dan Scales --- src/cmd/compile/internal/typecheck/subr.go | 1 + src/cmd/compile/internal/types/type.go | 106 ++++++++++++++--------------- 2 files changed, 54 insertions(+), 53 deletions(-) diff --git a/src/cmd/compile/internal/typecheck/subr.go b/src/cmd/compile/internal/typecheck/subr.go index 5ee4152e1c..968d7a0d6d 100644 --- a/src/cmd/compile/internal/typecheck/subr.go +++ b/src/cmd/compile/internal/typecheck/subr.go @@ -1367,6 +1367,7 @@ func Shapify(t *types.Type) *types.Type { s := types.NewNamed(name) s.SetUnderlying(u) s.SetIsShape(true) + s.SetHasShape(true) name.SetType(s) name.SetTypecheck(1) // TODO: add methods to s that the bound has? diff --git a/src/cmd/compile/internal/types/type.go b/src/cmd/compile/internal/types/type.go index 58ac4db95a..1f01498ca1 100644 --- a/src/cmd/compile/internal/types/type.go +++ b/src/cmd/compile/internal/types/type.go @@ -211,6 +211,7 @@ const ( typeRecur typeHasTParam // there is a typeparam somewhere in the type (generic function or type) typeIsShape // represents a set of closely related types, for generics + typeHasShape // there is a shape somewhere in the type ) func (t *Type) NotInHeap() bool { return t.flags&typeNotInHeap != 0 } @@ -220,17 +221,21 @@ func (t *Type) Deferwidth() bool { return t.flags&typeDeferwidth != 0 } func (t *Type) Recur() bool { return t.flags&typeRecur != 0 } func (t *Type) HasTParam() bool { return t.flags&typeHasTParam != 0 } func (t *Type) IsShape() bool { return t.flags&typeIsShape != 0 } +func (t *Type) HasShape() bool { return t.flags&typeHasShape != 0 } func (t *Type) SetNotInHeap(b bool) { t.flags.set(typeNotInHeap, b) } func (t *Type) SetBroke(b bool) { t.flags.set(typeBroke, b) } func (t *Type) SetNoalg(b bool) { t.flags.set(typeNoalg, b) } func (t *Type) SetDeferwidth(b bool) { t.flags.set(typeDeferwidth, b) } func (t *Type) SetRecur(b bool) { t.flags.set(typeRecur, b) } -func (t *Type) SetIsShape(b bool) { t.flags.set(typeIsShape, b) } // Generic types should never have alg functions. func (t *Type) SetHasTParam(b bool) { t.flags.set(typeHasTParam, b); t.flags.set(typeNoalg, b) } +// Should always do SetHasShape(true) when doing SeIsShape(true). +func (t *Type) SetIsShape(b bool) { t.flags.set(typeIsShape, b) } +func (t *Type) SetHasShape(b bool) { t.flags.set(typeHasShape, b) } + // Kind returns the kind of type t. func (t *Type) Kind() Kind { return t.kind } @@ -271,9 +276,6 @@ func (t *Type) SetRParams(rparams []*Type) { base.Fatalf("Setting nil or zero-length rparams") } t.rparams = &rparams - if t.HasTParam() { - return - } // HasTParam should be set if any rparam is or has a type param. This is // to handle the case of a generic type which doesn't reference any of its // type params (e.g. most commonly, an empty struct). @@ -282,6 +284,10 @@ func (t *Type) SetRParams(rparams []*Type) { t.SetHasTParam(true) break } + if rparam.HasShape() { + t.SetHasShape(true) + break + } } } @@ -624,6 +630,9 @@ func NewArray(elem *Type, bound int64) *Type { if elem.HasTParam() { t.SetHasTParam(true) } + if elem.HasShape() { + t.SetHasShape(true) + } return t } @@ -642,6 +651,9 @@ func NewSlice(elem *Type) *Type { if elem.HasTParam() { t.SetHasTParam(true) } + if elem.HasShape() { + t.SetHasShape(true) + } return t } @@ -654,6 +666,9 @@ func NewChan(elem *Type, dir ChanDir) *Type { if elem.HasTParam() { t.SetHasTParam(true) } + if elem.HasShape() { + t.SetHasShape(true) + } return t } @@ -664,6 +679,9 @@ func NewTuple(t1, t2 *Type) *Type { if t1.HasTParam() || t2.HasTParam() { t.SetHasTParam(true) } + if t1.HasShape() || t2.HasShape() { + t.SetHasShape(true) + } return t } @@ -695,6 +713,9 @@ func NewMap(k, v *Type) *Type { if k.HasTParam() || v.HasTParam() { t.SetHasTParam(true) } + if k.HasShape() || v.HasShape() { + t.SetHasShape(true) + } return t } @@ -719,6 +740,9 @@ func NewPtr(elem *Type) *Type { // when this entry was cached. t.SetHasTParam(true) } + if elem.HasShape() { + t.SetHasShape(true) + } return t } @@ -732,6 +756,9 @@ func NewPtr(elem *Type) *Type { if elem.HasTParam() { t.SetHasTParam(true) } + if elem.HasShape() { + t.SetHasShape(true) + } return t } @@ -1768,6 +1795,9 @@ func (t *Type) SetUnderlying(underlying *Type) { if underlying.HasTParam() { t.SetHasTParam(true) } + if underlying.HasShape() { + t.SetHasShape(true) + } // spec: "The declared type does not inherit any methods bound // to the existing type, but the method set of an interface @@ -1799,6 +1829,15 @@ func fieldsHasTParam(fields []*Field) bool { return false } +func fieldsHasShape(fields []*Field) bool { + for _, f := range fields { + if f.Type != nil && f.Type.HasShape() { + return true + } + } + return false +} + // NewBasic returns a new basic type of the given kind. func NewBasic(kind Kind, obj Object) *Type { t := New(kind) @@ -1818,6 +1857,10 @@ func NewInterface(pkg *Pkg, methods []*Field) *Type { t.SetHasTParam(true) break } + if f.Type != nil && f.Type.HasShape() { + t.SetHasShape(true) + break + } } if anyBroke(methods) { t.SetBroke(true) @@ -1923,6 +1966,9 @@ func NewSignature(pkg *Pkg, recv *Field, tparams, params, results []*Field) *Typ fieldsHasTParam(results) { t.SetHasTParam(true) } + if fieldsHasShape(recvs) || fieldsHasShape(params) || fieldsHasShape(results) { + t.SetHasShape(true) + } return t } @@ -1938,6 +1984,9 @@ func NewStruct(pkg *Pkg, fields []*Field) *Type { if fieldsHasTParam(fields) { t.SetHasTParam(true) } + if fieldsHasShape(fields) { + t.SetHasShape(true) + } return t } @@ -2150,52 +2199,3 @@ var ( ) var SimType [NTYPE]Kind - -// Reports whether t has a shape type anywere. -func (t *Type) HasShape() bool { - return t.HasShape1(map[*Type]bool{}) -} -func (t *Type) HasShape1(visited map[*Type]bool) bool { - if t.IsShape() { - return true - } - if visited[t] { - return false - } - visited[t] = true - if t.Sym() != nil { - for _, u := range t.RParams() { - if u.HasShape1(visited) { - return true - } - } - } - switch t.Kind() { - case TPTR, TARRAY, TSLICE, TCHAN: - return t.Elem().HasShape1(visited) - case TMAP: - return t.Elem().HasShape1(visited) || t.Key().HasShape1(visited) - case TSTRUCT: - for _, f := range t.FieldSlice() { - if f.Type.HasShape1(visited) { - return true - } - } - case TFUNC: - for _, a := range RecvsParamsResults { - for _, f := range a(t).FieldSlice() { - if f.Type.HasShape1(visited) { - return true - } - } - } - case TINTER: - for _, f := range t.Methods().Slice() { - if f.Type.HasShape1(visited) { - return true - } - } - return false - } - return false -} -- cgit v1.2.3-54-g00ecf