libgo/go/go/types/methodset.go

   1 // Copyright 2013 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 // This file implements method sets.
   6
   7 package types
   8
   9 import (
  10         "fmt"
  11         "sort"
  12         "strings"
  13 )
  14
  15 // A MethodSet is an ordered set of concrete or abstract (interface) methods;
  16 // a method is a MethodVal selection, and they are ordered by ascending m.Obj().Id().
  17 // The zero value for a MethodSet is a ready-to-use empty method set.
  18 type MethodSet struct {
  19         list []*Selection
  20 }
  21
  22 func (s *MethodSet) String() string {
  23         if s.Len() == 0 {
  24                 return "MethodSet {}"
  25         }
  26
  27         var buf strings.Builder
  28         fmt.Fprintln(&buf, "MethodSet {")
  29         for _, f := range s.list {
  30                 fmt.Fprintf(&buf, "\t%s\n", f)
  31         }
  32         fmt.Fprintln(&buf, "}")
  33         return buf.String()
  34 }
  35
  36 // Len returns the number of methods in s.
  37 func (s *MethodSet) Len() int { return len(s.list) }
  38
  39 // At returns the i'th method in s for 0 <= i < s.Len().
  40 func (s *MethodSet) At(i int) *Selection { return s.list[i] }
  41
  42 // Lookup returns the method with matching package and name, or nil if not found.
  43 func (s *MethodSet) Lookup(pkg *Package, name string) *Selection {
  44         if s.Len() == 0 {
  45                 return nil
  46         }
  47
  48         key := Id(pkg, name)
  49         i := sort.Search(len(s.list), func(i int) bool {
  50                 m := s.list[i]
  51                 return m.obj.Id() >= key
  52         })
  53         if i < len(s.list) {
  54                 m := s.list[i]
  55                 if m.obj.Id() == key {
  56                         return m
  57                 }
  58         }
  59         return nil
  60 }
  61
  62 // Shared empty method set.
  63 var emptyMethodSet MethodSet
  64
  65 // NewMethodSet returns the method set for the given type T.
  66 // It always returns a non-nil method set, even if it is empty.
  67 func NewMethodSet(T Type) *MethodSet {
  68         // WARNING: The code in this function is extremely subtle - do not modify casually!
  69         //          This function and lookupFieldOrMethod should be kept in sync.
  70
  71         // method set up to the current depth, allocated lazily
  72         var base methodSet
  73
  74         typ, isPtr := deref(T)
  75
  76         // *typ where typ is an interface has no methods.
  77         if isPtr && IsInterface(typ) {
  78                 return &emptyMethodSet
  79         }
  80
  81         // Start with typ as single entry at shallowest depth.
  82         current := []embeddedType{{typ, nil, isPtr, false}}
  83
  84         // Named types that we have seen already, allocated lazily.
  85         // Used to avoid endless searches in case of recursive types.
  86         // Since only Named types can be used for recursive types, we
  87         // only need to track those.
  88         // (If we ever allow type aliases to construct recursive types,
  89         // we must use type identity rather than pointer equality for
  90         // the map key comparison, as we do in consolidateMultiples.)
  91         var seen map[*Named]bool
  92
  93         // collect methods at current depth
  94         for len(current) > 0 {
  95                 var next []embeddedType // embedded types found at current depth
  96
  97                 // field and method sets at current depth, allocated lazily
  98                 var fset fieldSet
  99                 var mset methodSet
 100
 101                 for _, e := range current {
 102                         typ := e.typ
 103
 104                         // If we have a named type, we may have associated methods.
 105                         // Look for those first.
 106                         if named, _ := typ.(*Named); named != nil {
 107                                 if seen[named] {
 108                                         // We have seen this type before, at a more shallow depth
 109                                         // (note that multiples of this type at the current depth
 110                                         // were consolidated before). The type at that depth shadows
 111                                         // this same type at the current depth, so we can ignore
 112                                         // this one.
 113                                         continue
 114                                 }
 115                                 if seen == nil {
 116                                         seen = make(map[*Named]bool)
 117                                 }
 118                                 seen[named] = true
 119
 120                                 mset = mset.add(named.methods, e.index, e.indirect, e.multiples)
 121
 122                                 // continue with underlying type
 123                                 typ = named.underlying
 124                         }
 125
 126                         switch t := typ.(type) {
 127                         case *Struct:
 128                                 for i, f := range t.fields {
 129                                         fset = fset.add(f, e.multiples)
 130
 131                                         // Embedded fields are always of the form T or *T where
 132                                         // T is a type name. If typ appeared multiple times at
 133                                         // this depth, f.Type appears multiple times at the next
 134                                         // depth.
 135                                         if f.embedded {
 136                                                 typ, isPtr := deref(f.typ)
 137                                                 // TODO(gri) optimization: ignore types that can't
 138                                                 // have fields or methods (only Named, Struct, and
 139                                                 // Interface types need to be considered).
 140                                                 next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples})
 141                                         }
 142                                 }
 143
 144                         case *Interface:
 145                                 mset = mset.add(t.allMethods, e.index, true, e.multiples)
 146                         }
 147                 }
 148
 149                 // Add methods and collisions at this depth to base if no entries with matching
 150                 // names exist already.
 151                 for k, m := range mset {
 152                         if _, found := base[k]; !found {
 153                                 // Fields collide with methods of the same name at this depth.
 154                                 if _, found := fset[k]; found {
 155                                         m = nil // collision
 156                                 }
 157                                 if base == nil {
 158                                         base = make(methodSet)
 159                                 }
 160                                 base[k] = m
 161                         }
 162                 }
 163
 164                 // Multiple fields with matching names collide at this depth and shadow all
 165                 // entries further down; add them as collisions to base if no entries with
 166                 // matching names exist already.
 167                 for k, f := range fset {
 168                         if f == nil {
 169                                 if _, found := base[k]; !found {
 170                                         if base == nil {
 171                                                 base = make(methodSet)
 172                                         }
 173                                         base[k] = nil // collision
 174                                 }
 175                         }
 176                 }
 177
 178                 current = consolidateMultiples(next)
 179         }
 180
 181         if len(base) == 0 {
 182                 return &emptyMethodSet
 183         }
 184
 185         // collect methods
 186         var list []*Selection
 187         for _, m := range base {
 188                 if m != nil {
 189                         m.recv = T
 190                         list = append(list, m)
 191                 }
 192         }
 193         // sort by unique name
 194         sort.Slice(list, func(i, j int) bool {
 195                 return list[i].obj.Id() < list[j].obj.Id()
 196         })
 197         return &MethodSet{list}
 198 }
 199
 200 // A fieldSet is a set of fields and name collisions.
 201 // A collision indicates that multiple fields with the
 202 // same unique id appeared.
 203 type fieldSet map[string]*Var // a nil entry indicates a name collision
 204
 205 // Add adds field f to the field set s.
 206 // If multiples is set, f appears multiple times
 207 // and is treated as a collision.
 208 func (s fieldSet) add(f *Var, multiples bool) fieldSet {
 209         if s == nil {
 210                 s = make(fieldSet)
 211         }
 212         key := f.Id()
 213         // if f is not in the set, add it
 214         if !multiples {
 215                 if _, found := s[key]; !found {
 216                         s[key] = f
 217                         return s
 218                 }
 219         }
 220         s[key] = nil // collision
 221         return s
 222 }
 223
 224 // A methodSet is a set of methods and name collisions.
 225 // A collision indicates that multiple methods with the
 226 // same unique id appeared.
 227 type methodSet map[string]*Selection // a nil entry indicates a name collision
 228
 229 // Add adds all functions in list to the method set s.
 230 // If multiples is set, every function in list appears multiple times
 231 // and is treated as a collision.
 232 func (s methodSet) add(list []*Func, index []int, indirect bool, multiples bool) methodSet {
 233         if len(list) == 0 {
 234                 return s
 235         }
 236         if s == nil {
 237                 s = make(methodSet)
 238         }
 239         for i, f := range list {
 240                 key := f.Id()
 241                 // if f is not in the set, add it
 242                 if !multiples {
 243                         // TODO(gri) A found method may not be added because it's not in the method set
 244                         // (!indirect && ptrRecv(f)). A 2nd method on the same level may be in the method
 245                         // set and may not collide with the first one, thus leading to a false positive.
 246                         // Is that possible? Investigate.
 247                         if _, found := s[key]; !found && (indirect || !ptrRecv(f)) {
 248                                 s[key] = &Selection{MethodVal, nil, f, concat(index, i), indirect}
 249                                 continue
 250                         }
 251                 }
 252                 s[key] = nil // collision
 253         }
 254         return s
 255 }
 256
 257 // ptrRecv reports whether the receiver is of the form *T.
 258 // The receiver must exist.
 259 func ptrRecv(f *Func) bool {
 260         _, isPtr := deref(f.typ.(*Signature).recv.typ)
 261         return isPtr
 262 }