src/go/types/interface.go

   1 // Copyright 2021 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 types
   6
   7 import (
   8         "fmt"
   9         "go/ast"
  10         "go/internal/typeparams"
  11         "go/token"
  12         "sort"
  13 )
  14
  15 func (check *Checker) interfaceType(ityp *Interface, iface *ast.InterfaceType, def *Named) {
  16         var tlist *ast.Ident // "type" name of first entry in a type list declaration
  17         var types []ast.Expr
  18         for _, f := range iface.Methods.List {
  19                 if len(f.Names) > 0 {
  20                         // We have a method with name f.Names[0], or a type
  21                         // of a type list (name.Name == "type").
  22                         // (The parser ensures that there's only one method
  23                         // and we don't care if a constructed AST has more.)
  24                         name := f.Names[0]
  25                         if name.Name == "_" {
  26                                 check.errorf(name, _BlankIfaceMethod, "invalid method name _")
  27                                 continue // ignore
  28                         }
  29
  30                         if name.Name == "type" {
  31                                 // Always collect all type list entries, even from
  32                                 // different type lists, under the assumption that
  33                                 // the author intended to include all types.
  34                                 types = append(types, f.Type)
  35                                 if tlist != nil && tlist != name {
  36                                         check.errorf(name, _Todo, "cannot have multiple type lists in an interface")
  37                                 }
  38                                 tlist = name
  39                                 continue
  40                         }
  41
  42                         typ := check.typ(f.Type)
  43                         sig, _ := typ.(*Signature)
  44                         if sig == nil {
  45                                 if typ != Typ[Invalid] {
  46                                         check.invalidAST(f.Type, "%s is not a method signature", typ)
  47                                 }
  48                                 continue // ignore
  49                         }
  50
  51                         // Always type-check method type parameters but complain if they are not enabled.
  52                         // (This extra check is needed here because interface method signatures don't have
  53                         // a receiver specification.)
  54                         if sig.tparams != nil {
  55                                 var at positioner = f.Type
  56                                 if tparams := typeparams.Get(f.Type); tparams != nil {
  57                                         at = tparams
  58                                 }
  59                                 check.errorf(at, _Todo, "methods cannot have type parameters")
  60                         }
  61
  62                         // use named receiver type if available (for better error messages)
  63                         var recvTyp Type = ityp
  64                         if def != nil {
  65                                 recvTyp = def
  66                         }
  67                         sig.recv = NewVar(name.Pos(), check.pkg, "", recvTyp)
  68
  69                         m := NewFunc(name.Pos(), check.pkg, name.Name, sig)
  70                         check.recordDef(name, m)
  71                         ityp.methods = append(ityp.methods, m)
  72                 } else {
  73                         // We have an embedded type. completeInterface will
  74                         // eventually verify that we have an interface.
  75                         ityp.embeddeds = append(ityp.embeddeds, check.typ(f.Type))
  76                         check.posMap[ityp] = append(check.posMap[ityp], f.Type.Pos())
  77                 }
  78         }
  79
  80         // type constraints
  81         ityp.types = _NewSum(check.collectTypeConstraints(iface.Pos(), types))
  82
  83         if len(ityp.methods) == 0 && ityp.types == nil && len(ityp.embeddeds) == 0 {
  84                 // empty interface
  85                 ityp.allMethods = markComplete
  86                 return
  87         }
  88
  89         // sort for API stability
  90         sortMethods(ityp.methods)
  91         sortTypes(ityp.embeddeds)
  92
  93         check.later(func() { check.completeInterface(iface.Pos(), ityp) })
  94 }
  95
  96 func (check *Checker) collectTypeConstraints(pos token.Pos, types []ast.Expr) []Type {
  97         list := make([]Type, 0, len(types)) // assume all types are correct
  98         for _, texpr := range types {
  99                 if texpr == nil {
 100                         check.invalidAST(atPos(pos), "missing type constraint")
 101                         continue
 102                 }
 103                 list = append(list, check.varType(texpr))
 104         }
 105
 106         // Ensure that each type is only present once in the type list.  Types may be
 107         // interfaces, which may not be complete yet. It's ok to do this check at the
 108         // end because it's not a requirement for correctness of the code.
 109         // Note: This is a quadratic algorithm, but type lists tend to be short.
 110         check.later(func() {
 111                 for i, t := range list {
 112                         if t := asInterface(t); t != nil {
 113                                 check.completeInterface(types[i].Pos(), t)
 114                         }
 115                         if includes(list[:i], t) {
 116                                 check.softErrorf(types[i], _Todo, "duplicate type %s in type list", t)
 117                         }
 118                 }
 119         })
 120
 121         return list
 122 }
 123
 124 // includes reports whether typ is in list.
 125 func includes(list []Type, typ Type) bool {
 126         for _, e := range list {
 127                 if Identical(typ, e) {
 128                         return true
 129                 }
 130         }
 131         return false
 132 }
 133
 134 func (check *Checker) completeInterface(pos token.Pos, ityp *Interface) {
 135         if ityp.allMethods != nil {
 136                 return
 137         }
 138
 139         // completeInterface may be called via the LookupFieldOrMethod,
 140         // MissingMethod, Identical, or IdenticalIgnoreTags external API
 141         // in which case check will be nil. In this case, type-checking
 142         // must be finished and all interfaces should have been completed.
 143         if check == nil {
 144                 panic("internal error: incomplete interface")
 145         }
 146         completeInterface(check, pos, ityp)
 147 }
 148
 149 func completeInterface(check *Checker, pos token.Pos, ityp *Interface) {
 150         assert(ityp.allMethods == nil)
 151
 152         if check != nil && trace {
 153                 // Types don't generally have position information.
 154                 // If we don't have a valid pos provided, try to use
 155                 // one close enough.
 156                 if !pos.IsValid() && len(ityp.methods) > 0 {
 157                         pos = ityp.methods[0].pos
 158                 }
 159
 160                 check.trace(pos, "complete %s", ityp)
 161                 check.indent++
 162                 defer func() {
 163                         check.indent--
 164                         check.trace(pos, "=> %s (methods = %v, types = %v)", ityp, ityp.allMethods, ityp.allTypes)
 165                 }()
 166         }
 167
 168         // An infinitely expanding interface (due to a cycle) is detected
 169         // elsewhere (Checker.validType), so here we simply assume we only
 170         // have valid interfaces. Mark the interface as complete to avoid
 171         // infinite recursion if the validType check occurs later for some
 172         // reason.
 173         ityp.allMethods = markComplete
 174
 175         // Methods of embedded interfaces are collected unchanged; i.e., the identity
 176         // of a method I.m's Func Object of an interface I is the same as that of
 177         // the method m in an interface that embeds interface I. On the other hand,
 178         // if a method is embedded via multiple overlapping embedded interfaces, we
 179         // don't provide a guarantee which "original m" got chosen for the embedding
 180         // interface. See also issue #34421.
 181         //
 182         // If we don't care to provide this identity guarantee anymore, instead of
 183         // reusing the original method in embeddings, we can clone the method's Func
 184         // Object and give it the position of a corresponding embedded interface. Then
 185         // we can get rid of the mpos map below and simply use the cloned method's
 186         // position.
 187
 188         var todo []*Func
 189         var seen objset
 190         var methods []*Func
 191         mpos := make(map[*Func]token.Pos) // method specification or method embedding position, for good error messages
 192         addMethod := func(pos token.Pos, m *Func, explicit bool) {
 193                 switch other := seen.insert(m); {
 194                 case other == nil:
 195                         methods = append(methods, m)
 196                         mpos[m] = pos
 197                 case explicit:
 198                         if check == nil {
 199                                 panic(fmt.Sprintf("%v: duplicate method %s", m.pos, m.name))
 200                         }
 201                         check.errorf(atPos(pos), _DuplicateDecl, "duplicate method %s", m.name)
 202                         check.errorf(atPos(mpos[other.(*Func)]), _DuplicateDecl, "\tother declaration of %s", m.name) // secondary error, \t indented
 203                 default:
 204                         // We have a duplicate method name in an embedded (not explicitly declared) method.
 205                         // Check method signatures after all types are computed (issue #33656).
 206                         // If we're pre-go1.14 (overlapping embeddings are not permitted), report that
 207                         // error here as well (even though we could do it eagerly) because it's the same
 208                         // error message.
 209                         if check == nil {
 210                                 // check method signatures after all locally embedded interfaces are computed
 211                                 todo = append(todo, m, other.(*Func))
 212                                 break
 213                         }
 214                         check.later(func() {
 215                                 if !check.allowVersion(m.pkg, 1, 14) || !check.identical(m.typ, other.Type()) {
 216                                         check.errorf(atPos(pos), _DuplicateDecl, "duplicate method %s", m.name)
 217                                         check.errorf(atPos(mpos[other.(*Func)]), _DuplicateDecl, "\tother declaration of %s", m.name) // secondary error, \t indented
 218                                 }
 219                         })
 220                 }
 221         }
 222
 223         for _, m := range ityp.methods {
 224                 addMethod(m.pos, m, true)
 225         }
 226
 227         // collect types
 228         allTypes := ityp.types
 229
 230         var posList []token.Pos
 231         if check != nil {
 232                 posList = check.posMap[ityp]
 233         }
 234         for i, typ := range ityp.embeddeds {
 235                 var pos token.Pos // embedding position
 236                 if posList != nil {
 237                         pos = posList[i]
 238                 }
 239                 utyp := under(typ)
 240                 etyp := asInterface(utyp)
 241                 if etyp == nil {
 242                         if utyp != Typ[Invalid] {
 243                                 var format string
 244                                 if _, ok := utyp.(*_TypeParam); ok {
 245                                         format = "%s is a type parameter, not an interface"
 246                                 } else {
 247                                         format = "%s is not an interface"
 248                                 }
 249                                 if check != nil {
 250                                         // TODO: correct error code.
 251                                         check.errorf(atPos(pos), _InvalidIfaceEmbed, format, typ)
 252                                 } else {
 253                                         panic(fmt.Sprintf(format, typ))
 254                                 }
 255                         }
 256                         continue
 257                 }
 258                 if etyp.allMethods == nil {
 259                         completeInterface(check, pos, etyp)
 260                 }
 261                 for _, m := range etyp.allMethods {
 262                         addMethod(pos, m, false) // use embedding position pos rather than m.pos
 263                 }
 264                 allTypes = intersect(allTypes, etyp.allTypes)
 265         }
 266
 267         // process todo's (this only happens if check == nil)
 268         for i := 0; i < len(todo); i += 2 {
 269                 m := todo[i]
 270                 other := todo[i+1]
 271                 if !Identical(m.typ, other.typ) {
 272                         panic(fmt.Sprintf("%v: duplicate method %s", m.pos, m.name))
 273                 }
 274         }
 275
 276         if methods != nil {
 277                 sort.Sort(byUniqueMethodName(methods))
 278                 ityp.allMethods = methods
 279         }
 280         ityp.allTypes = allTypes
 281 }
 282
 283 // intersect computes the intersection of the types x and y.
 284 // Note: A incomming nil type stands for the top type. A top
 285 // type result is returned as nil.
 286 func intersect(x, y Type) (r Type) {
 287         defer func() {
 288                 if r == theTop {
 289                         r = nil
 290                 }
 291         }()
 292
 293         switch {
 294         case x == theBottom || y == theBottom:
 295                 return theBottom
 296         case x == nil || x == theTop:
 297                 return y
 298         case y == nil || x == theTop:
 299                 return x
 300         }
 301
 302         xtypes := unpackType(x)
 303         ytypes := unpackType(y)
 304         // Compute the list rtypes which includes only
 305         // types that are in both xtypes and ytypes.
 306         // Quadratic algorithm, but good enough for now.
 307         // TODO(gri) fix this
 308         var rtypes []Type
 309         for _, x := range xtypes {
 310                 if includes(ytypes, x) {
 311                         rtypes = append(rtypes, x)
 312                 }
 313         }
 314
 315         if rtypes == nil {
 316                 return theBottom
 317         }
 318         return _NewSum(rtypes)
 319 }
 320
 321 func sortTypes(list []Type) {
 322         sort.Stable(byUniqueTypeName(list))
 323 }
 324
 325 // byUniqueTypeName named type lists can be sorted by their unique type names.
 326 type byUniqueTypeName []Type
 327
 328 func (a byUniqueTypeName) Len() int           { return len(a) }
 329 func (a byUniqueTypeName) Less(i, j int) bool { return sortName(a[i]) < sortName(a[j]) }
 330 func (a byUniqueTypeName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
 331
 332 func sortName(t Type) string {
 333         if named := asNamed(t); named != nil {
 334                 return named.obj.Id()
 335         }
 336         return ""
 337 }
 338
 339 func sortMethods(list []*Func) {
 340         sort.Sort(byUniqueMethodName(list))
 341 }
 342
 343 func assertSortedMethods(list []*Func) {
 344         if !debug {
 345                 panic("internal error: assertSortedMethods called outside debug mode")
 346         }
 347         if !sort.IsSorted(byUniqueMethodName(list)) {
 348                 panic("internal error: methods not sorted")
 349         }
 350 }
 351
 352 // byUniqueMethodName method lists can be sorted by their unique method names.
 353 type byUniqueMethodName []*Func
 354
 355 func (a byUniqueMethodName) Len() int           { return len(a) }
 356 func (a byUniqueMethodName) Less(i, j int) bool { return a[i].Id() < a[j].Id() }
 357 func (a byUniqueMethodName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }