From c8e73489c32d5a45beca3f4810b6be64a2553ddb Mon Sep 17 00:00:00 2001 From: Rob Findley Date: Tue, 8 Dec 2020 14:28:21 -0500 Subject: [PATCH] go/types: import instance.expand and subst.go from dev.go2go Changes from dev.go2go: + A potentially latent bug is fixed when nilling out tparams in an instantiated signature (the resulting type could be Typ[Invalid]) + Support for pointer designation is removed + instantiatedHash is updated to use '[]' rather than '()' + Several TODOs were added for me to follow-up on, rather than address in this CL + Error callsites are updated. Deciding on error codes and better error messages is punted to a later CL These changes can be reviewed by comparing with Patchset #1 of this CL. Change-Id: Ib5869586b8395419013010e2085cab877727d2ef Reviewed-on: https://go-review.googlesource.com/c/go/+/276253 Run-TryBot: Robert Findley TryBot-Result: Go Bot Trust: Robert Findley Reviewed-by: Robert Griesemer --- src/go/types/check.go | 2 + src/go/types/subst.go | 542 +++++++++++++++++++++++++++++++++++++ src/go/types/type.go | 29 +- src/go/types/typestring.go | 3 - 4 files changed, 567 insertions(+), 9 deletions(-) create mode 100644 src/go/types/subst.go diff --git a/src/go/types/check.go b/src/go/types/check.go index f82c7fdf7b..73330db6e4 100644 --- a/src/go/types/check.go +++ b/src/go/types/check.go @@ -82,6 +82,7 @@ type Checker struct { objMap map[Object]*declInfo // maps package-level objects and (non-interface) methods to declaration info impMap map[importKey]*Package // maps (import path, source directory) to (complete or fake) package posMap map[*Interface][]token.Pos // maps interface types to lists of embedded interface positions + typMap map[string]*Named // maps an instantiated named type hash to a *Named type pkgCnt map[string]int // counts number of imported packages with a given name (for better error messages) // information collected during type-checking of a set of package files @@ -194,6 +195,7 @@ func NewChecker(conf *Config, fset *token.FileSet, pkg *Package, info *Info) *Ch objMap: make(map[Object]*declInfo), impMap: make(map[importKey]*Package), posMap: make(map[*Interface][]token.Pos), + typMap: make(map[string]*Named), pkgCnt: make(map[string]int), } } diff --git a/src/go/types/subst.go b/src/go/types/subst.go new file mode 100644 index 0000000000..ca9462dfda --- /dev/null +++ b/src/go/types/subst.go @@ -0,0 +1,542 @@ +// Copyright 2018 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. + +// This file implements instantiation of generic types +// through substitution of type parameters by actual +// types. + +package types + +import ( + "bytes" + "fmt" + "go/token" +) + +// TODO(rFindley) decide error codes for the errors in this file, and check +// if error spans can be improved + +type substMap struct { + // The targs field is currently needed for *Named type substitution. + // TODO(gri) rewrite that code, get rid of this field, and make this + // struct just the map (proj) + targs []Type + proj map[*TypeParam]Type +} + +// makeSubstMap creates a new substitution map mapping tpars[i] to targs[i]. +// If targs[i] is nil, tpars[i] is not substituted. +func makeSubstMap(tpars []*TypeName, targs []Type) *substMap { + assert(len(tpars) == len(targs)) + proj := make(map[*TypeParam]Type, len(tpars)) + for i, tpar := range tpars { + // We must expand type arguments otherwise *instance + // types end up as components in composite types. + // TODO(gri) explain why this causes problems, if it does + targ := expand(targs[i]) // possibly nil + targs[i] = targ + proj[tpar.typ.(*TypeParam)] = targ + } + return &substMap{targs, proj} +} + +func (m *substMap) String() string { + return fmt.Sprintf("%s", m.proj) +} + +func (m *substMap) empty() bool { + return len(m.proj) == 0 +} + +func (m *substMap) lookup(tpar *TypeParam) Type { + if t := m.proj[tpar]; t != nil { + return t + } + return tpar +} + +func (check *Checker) instantiate(pos token.Pos, typ Type, targs []Type, poslist []token.Pos) (res Type) { + if trace { + check.trace(pos, "-- instantiating %s with %s", typ, typeListString(targs)) + check.indent++ + defer func() { + check.indent-- + var under Type + if res != nil { + // Calling under() here may lead to endless instantiations. + // Test case: type T[P any] T[P] + // TODO(gri) investigate if that's a bug or to be expected. + under = res.Underlying() + } + check.trace(pos, "=> %s (under = %s)", res, under) + }() + } + + assert(len(poslist) <= len(targs)) + + // TODO(gri) What is better here: work with TypeParams, or work with TypeNames? + var tparams []*TypeName + switch t := typ.(type) { + case *Named: + tparams = t.tparams + case *Signature: + tparams = t.tparams + defer func() { + // If we had an unexpected failure somewhere don't panic below when + // asserting res.(*Signature). Check for *Signature in case Typ[Invalid] + // is returned. + if _, ok := res.(*Signature); !ok { + return + } + // If the signature doesn't use its type parameters, subst + // will not make a copy. In that case, make a copy now (so + // we can set tparams to nil w/o causing side-effects). + if t == res { + copy := *t + res = © + } + // After instantiating a generic signature, it is not generic + // anymore; we need to set tparams to nil. + res.(*Signature).tparams = nil + }() + + default: + check.dump("%v: cannot instantiate %v", pos, typ) + unreachable() // only defined types and (defined) functions can be generic + } + + // the number of supplied types must match the number of type parameters + if len(targs) != len(tparams) { + // TODO(gri) provide better error message + check.errorf(atPos(pos), 0, "got %d arguments but %d type parameters", len(targs), len(tparams)) + return Typ[Invalid] + } + + if len(tparams) == 0 { + return typ // nothing to do (minor optimization) + } + + smap := makeSubstMap(tparams, targs) + + // check bounds + for i, tname := range tparams { + tpar := tname.typ.(*TypeParam) + iface := tpar.Bound() + if iface.Empty() { + continue // no type bound + } + + targ := targs[i] + + // best position for error reporting + pos := pos + if i < len(poslist) { + pos = poslist[i] + } + + // The type parameter bound is parameterized with the same type parameters + // as the instantiated type; before we can use it for bounds checking we + // need to instantiate it with the type arguments with which we instantiate + // the parameterized type. + iface = check.subst(pos, iface, smap).(*Interface) + + // targ must implement iface (methods) + // - check only if we have methods + check.completeInterface(token.NoPos, iface) + if len(iface.allMethods) > 0 { + // If the type argument is a pointer to a type parameter, the type argument's + // method set is empty. + // TODO(gri) is this what we want? (spec question) + if base, isPtr := deref(targ); isPtr && asTypeParam(base) != nil { + check.errorf(atPos(pos), 0, "%s has no methods", targ) + break + } + if m, wrong := check.missingMethod(targ, iface, true); m != nil { + // TODO(gri) needs to print updated name to avoid major confusion in error message! + // (print warning for now) + // Old warning: + // check.softErrorf(pos, "%s does not satisfy %s (warning: name not updated) = %s (missing method %s)", targ, tpar.bound, iface, m) + if m.name == "==" { + // We don't want to report "missing method ==". + check.softErrorf(atPos(pos), 0, "%s does not satisfy comparable", targ) + } else if wrong != nil { + // TODO(gri) This can still report uninstantiated types which makes the error message + // more difficult to read then necessary. + check.softErrorf(atPos(pos), 0, + "%s does not satisfy %s: wrong method signature\n\tgot %s\n\twant %s", + targ, tpar.bound, wrong, m, + ) + } else { + check.softErrorf(atPos(pos), 0, "%s does not satisfy %s (missing method %s)", targ, tpar.bound, m.name) + } + break + } + } + + // targ's underlying type must also be one of the interface types listed, if any + if iface.allTypes == nil { + continue // nothing to do + } + + // If targ is itself a type parameter, each of its possible types, but at least one, must be in the + // list of iface types (i.e., the targ type list must be a non-empty subset of the iface types). + if targ := asTypeParam(targ); targ != nil { + targBound := targ.Bound() + if targBound.allTypes == nil { + check.softErrorf(atPos(pos), 0, "%s does not satisfy %s (%s has no type constraints)", targ, tpar.bound, targ) + break + } + for _, t := range unpackType(targBound.allTypes) { + if !iface.isSatisfiedBy(t) { + // TODO(gri) match this error message with the one below (or vice versa) + check.softErrorf(atPos(pos), 0, "%s does not satisfy %s (%s type constraint %s not found in %s)", targ, tpar.bound, targ, t, iface.allTypes) + break + } + } + break + } + + // Otherwise, targ's type or underlying type must also be one of the interface types listed, if any. + if !iface.isSatisfiedBy(targ) { + check.softErrorf(atPos(pos), 0, "%s does not satisfy %s (%s or %s not found in %s)", targ, tpar.bound, targ, under(targ), iface.allTypes) + break + } + } + + return check.subst(pos, typ, smap) +} + +// subst returns the type typ with its type parameters tpars replaced by +// the corresponding type arguments targs, recursively. +// subst is functional in the sense that it doesn't modify the incoming +// type. If a substitution took place, the result type is different from +// from the incoming type. +func (check *Checker) subst(pos token.Pos, typ Type, smap *substMap) Type { + if smap.empty() { + return typ + } + + // common cases + switch t := typ.(type) { + case *Basic: + return typ // nothing to do + case *TypeParam: + return smap.lookup(t) + } + + // general case + subst := subster{check, pos, make(map[Type]Type), smap} + return subst.typ(typ) +} + +type subster struct { + check *Checker + pos token.Pos + cache map[Type]Type + smap *substMap +} + +func (subst *subster) typ(typ Type) Type { + switch t := typ.(type) { + case nil: + // Call typOrNil if it's possible that typ is nil. + panic("nil typ") + + case *Basic, *bottom, *top: + // nothing to do + + case *Array: + elem := subst.typOrNil(t.elem) + if elem != t.elem { + return &Array{len: t.len, elem: elem} + } + + case *Slice: + elem := subst.typOrNil(t.elem) + if elem != t.elem { + return &Slice{elem: elem} + } + + case *Struct: + if fields, copied := subst.varList(t.fields); copied { + return &Struct{fields: fields, tags: t.tags} + } + + case *Pointer: + base := subst.typ(t.base) + if base != t.base { + return &Pointer{base: base} + } + + case *Tuple: + return subst.tuple(t) + + case *Signature: + // TODO(gri) rethink the recv situation with respect to methods on parameterized types + // recv := subst.var_(t.recv) // TODO(gri) this causes a stack overflow - explain + recv := t.recv + params := subst.tuple(t.params) + results := subst.tuple(t.results) + if recv != t.recv || params != t.params || results != t.results { + return &Signature{ + rparams: t.rparams, + // TODO(rFindley) why can't we nil out tparams here, rather than in + // instantiate above? + tparams: t.tparams, + scope: t.scope, + recv: recv, + params: params, + results: results, + variadic: t.variadic, + } + } + + case *Sum: + types, copied := subst.typeList(t.types) + if copied { + // Don't do it manually, with a Sum literal: the new + // types list may not be unique and NewSum may remove + // duplicates. + return NewSum(types) + } + + case *Interface: + methods, mcopied := subst.funcList(t.methods) + types := t.types + if t.types != nil { + types = subst.typ(t.types) + } + embeddeds, ecopied := subst.typeList(t.embeddeds) + if mcopied || types != t.types || ecopied { + iface := &Interface{methods: methods, types: types, embeddeds: embeddeds} + subst.check.posMap[iface] = subst.check.posMap[t] // satisfy completeInterface requirement + subst.check.completeInterface(token.NoPos, iface) + return iface + } + + case *Map: + key := subst.typ(t.key) + elem := subst.typ(t.elem) + if key != t.key || elem != t.elem { + return &Map{key: key, elem: elem} + } + + case *Chan: + elem := subst.typ(t.elem) + if elem != t.elem { + return &Chan{dir: t.dir, elem: elem} + } + + case *Named: + subst.check.indent++ + defer func() { + subst.check.indent-- + }() + dump := func(format string, args ...interface{}) { + if trace { + subst.check.trace(subst.pos, format, args...) + } + } + + if t.tparams == nil { + dump(">>> %s is not parameterized", t) + return t // type is not parameterized + } + + var newTargs []Type + + if len(t.targs) > 0 { + // already instantiated + dump(">>> %s already instantiated", t) + assert(len(t.targs) == len(t.tparams)) + // For each (existing) type argument targ, determine if it needs + // to be substituted; i.e., if it is or contains a type parameter + // that has a type argument for it. + for i, targ := range t.targs { + dump(">>> %d targ = %s", i, targ) + newTarg := subst.typ(targ) + if newTarg != targ { + dump(">>> substituted %d targ %s => %s", i, targ, newTarg) + if newTargs == nil { + newTargs = make([]Type, len(t.tparams)) + copy(newTargs, t.targs) + } + newTargs[i] = newTarg + } + } + + if newTargs == nil { + dump(">>> nothing to substitute in %s", t) + return t // nothing to substitute + } + } else { + // not yet instantiated + dump(">>> first instantiation of %s", t) + // TODO(rFindley) can we instead subst the tparam types here? + newTargs = subst.smap.targs + } + + // before creating a new named type, check if we have this one already + h := instantiatedHash(t, newTargs) + dump(">>> new type hash: %s", h) + if named, found := subst.check.typMap[h]; found { + dump(">>> found %s", named) + subst.cache[t] = named + return named + } + + // create a new named type and populate caches to avoid endless recursion + tname := NewTypeName(subst.pos, t.obj.pkg, t.obj.name, nil) + named := subst.check.NewNamed(tname, t.underlying, t.methods) // method signatures are updated lazily + named.tparams = t.tparams // new type is still parameterized + named.targs = newTargs + subst.check.typMap[h] = named + subst.cache[t] = named + + // do the substitution + dump(">>> subst %s with %s (new: %s)", t.underlying, subst.smap, newTargs) + named.underlying = subst.typOrNil(t.underlying) + named.orig = named.underlying // for cycle detection (Checker.validType) + + return named + + case *TypeParam: + return subst.smap.lookup(t) + + case *instance: + // TODO(gri) can we avoid the expansion here and just substitute the type parameters? + return subst.typ(t.expand()) + + default: + panic("unimplemented") + } + + return typ +} + +// TODO(gri) Eventually, this should be more sophisticated. +// It won't work correctly for locally declared types. +func instantiatedHash(typ *Named, targs []Type) string { + var buf bytes.Buffer + writeTypeName(&buf, typ.obj, nil) + buf.WriteByte('[') + writeTypeList(&buf, targs, nil, nil) + buf.WriteByte(']') + + // With respect to the represented type, whether a + // type is fully expanded or stored as instance + // does not matter - they are the same types. + // Remove the instanceMarkers printed for instances. + res := buf.Bytes() + i := 0 + for _, b := range res { + if b != instanceMarker { + res[i] = b + i++ + } + } + + return string(res[:i]) +} + +func typeListString(list []Type) string { + var buf bytes.Buffer + writeTypeList(&buf, list, nil, nil) + return buf.String() +} + +// typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid]. +// A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_)) +// where an array/slice element is accessed before it is set up. +func (subst *subster) typOrNil(typ Type) Type { + if typ == nil { + return Typ[Invalid] + } + return subst.typ(typ) +} + +func (subst *subster) var_(v *Var) *Var { + if v != nil { + if typ := subst.typ(v.typ); typ != v.typ { + copy := *v + copy.typ = typ + return © + } + } + return v +} + +func (subst *subster) tuple(t *Tuple) *Tuple { + if t != nil { + if vars, copied := subst.varList(t.vars); copied { + return &Tuple{vars: vars} + } + } + return t +} + +func (subst *subster) varList(in []*Var) (out []*Var, copied bool) { + out = in + for i, v := range in { + if w := subst.var_(v); w != v { + if !copied { + // first variable that got substituted => allocate new out slice + // and copy all variables + new := make([]*Var, len(in)) + copy(new, out) + out = new + copied = true + } + out[i] = w + } + } + return +} + +func (subst *subster) func_(f *Func) *Func { + if f != nil { + if typ := subst.typ(f.typ); typ != f.typ { + copy := *f + copy.typ = typ + return © + } + } + return f +} + +func (subst *subster) funcList(in []*Func) (out []*Func, copied bool) { + out = in + for i, f := range in { + if g := subst.func_(f); g != f { + if !copied { + // first function that got substituted => allocate new out slice + // and copy all functions + new := make([]*Func, len(in)) + copy(new, out) + out = new + copied = true + } + out[i] = g + } + } + return +} + +func (subst *subster) typeList(in []Type) (out []Type, copied bool) { + out = in + for i, t := range in { + if u := subst.typ(t); u != t { + if !copied { + // first function that got substituted => allocate new out slice + // and copy all functions + new := make([]Type, len(in)) + copy(new, out) + out = new + copied = true + } + out[i] = u + } + } + return +} diff --git a/src/go/types/type.go b/src/go/types/type.go index e0cff1b976..0fcefefb73 100644 --- a/src/go/types/type.go +++ b/src/go/types/type.go @@ -313,7 +313,6 @@ type Interface struct { allTypes Type // intersection of all embedded and locally declared types (TODO(gri) need better field name) obj Object // type declaration defining this interface; or nil (for better error messages) - } // unpack unpacks a type into a list of types. @@ -669,6 +668,14 @@ func NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named { return typ } +func (check *Checker) NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named { + typ := &Named{check: check, obj: obj, orig: underlying, underlying: underlying, methods: methods} + if obj.typ == nil { + obj.typ = typ + } + return typ +} + // Obj returns the type name for the named type t. func (t *Named) Obj() *TypeName { return t.obj } @@ -713,16 +720,15 @@ func (t *Named) AddMethod(m *Func) { type TypeParam struct { check *Checker // for lazy type bound completion id uint64 // unique id - ptr bool // pointer designation obj *TypeName // corresponding type name index int // parameter index bound Type // *Named or *Interface; underlying type is always *Interface } // NewTypeParam returns a new TypeParam. -func (check *Checker) NewTypeParam(ptr bool, obj *TypeName, index int, bound Type) *TypeParam { +func (check *Checker) NewTypeParam(obj *TypeName, index int, bound Type) *TypeParam { assert(bound != nil) - typ := &TypeParam{check: check, id: check.nextId, ptr: ptr, obj: obj, index: index, bound: bound} + typ := &TypeParam{check: check, id: check.nextId, obj: obj, index: index, bound: bound} check.nextId++ if obj.typ == nil { obj.typ = typ @@ -783,8 +789,19 @@ type instance struct { // The result is either an instantiated *Named type, or // Typ[Invalid] if there was an error. func (t *instance) expand() Type { - // TODO(rFindley) add this in a follow-up CL. - panic("not implemented") + v := t.value + if v == nil { + v = t.check.instantiate(t.pos, t.base, t.targs, t.poslist) + if v == nil { + v = Typ[Invalid] + } + t.value = v + } + // After instantiation we must have an invalid or a *Named type. + if debug && v != Typ[Invalid] { + _ = v.(*Named) + } + return v } // expand expands a type instance into its instantiated diff --git a/src/go/types/typestring.go b/src/go/types/typestring.go index b9c227d460..64bbb33505 100644 --- a/src/go/types/typestring.go +++ b/src/go/types/typestring.go @@ -333,9 +333,6 @@ func writeTParamList(buf *bytes.Buffer, list []*TypeName, qf Qualifier, visited prev = b if t, _ := p.typ.(*TypeParam); t != nil { - if t.ptr { - buf.WriteByte('*') - } writeType(buf, t, qf, visited) } else { buf.WriteString(p.name) -- 2.48.1