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 // Note: NewMethodSet is intended for external use only as it
  66 //       requires interfaces to be complete. It may be used
  67 //       internally if LookupFieldOrMethod completed the same
  68 //       interfaces beforehand.
  69
  70 // NewMethodSet returns the method set for the given type T.
  71 // It always returns a non-nil method set, even if it is empty.
  72 func NewMethodSet(T Type) *MethodSet {
  73         // WARNING: The code in this function is extremely subtle - do not modify casually!
  74         //          This function and lookupFieldOrMethod should be kept in sync.
  75
  76         // TODO(rfindley) confirm that this code is in sync with lookupFieldOrMethod
  77         //                with respect to type params.
  78
  79         // method set up to the current depth, allocated lazily
  80         var base methodSet
  81
  82         typ, isPtr := deref(T)
  83
  84         // *typ where typ is an interface has no methods.
  85         if isPtr && IsInterface(typ) {
  86                 return &emptyMethodSet
  87         }
  88
  89         // Start with typ as single entry at shallowest depth.
  90         current := []embeddedType{{typ, nil, isPtr, false}}
  91
  92         // Named types that we have seen already, allocated lazily.
  93         // Used to avoid endless searches in case of recursive types.
  94         // Since only Named types can be used for recursive types, we
  95         // only need to track those.
  96         // (If we ever allow type aliases to construct recursive types,
  97         // we must use type identity rather than pointer equality for
  98         // the map key comparison, as we do in consolidateMultiples.)
  99         var seen map[*Named]bool
 100
 101         // collect methods at current depth
 102         for len(current) > 0 {
 103                 var next []embeddedType // embedded types found at current depth
 104
 105                 // field and method sets at current depth, indexed by names (Id's), and allocated lazily
 106                 var fset map[string]bool // we only care about the field names
 107                 var mset methodSet
 108
 109                 for _, e := range current {
 110                         typ := e.typ
 111
 112                         // If we have a named type, we may have associated methods.
 113                         // Look for those first.
 114                         if named, _ := typ.(*Named); named != nil {
 115                                 if seen[named] {
 116                                         // We have seen this type before, at a more shallow depth
 117                                         // (note that multiples of this type at the current depth
 118                                         // were consolidated before). The type at that depth shadows
 119                                         // this same type at the current depth, so we can ignore
 120                                         // this one.
 121                                         continue
 122                                 }
 123                                 if seen == nil {
 124                                         seen = make(map[*Named]bool)
 125                                 }
 126                                 seen[named] = true
 127
 128                                 for i := 0; i < named.NumMethods(); i++ {
 129                                         mset = mset.addOne(named.Method(i), concat(e.index, i), e.indirect, e.multiples)
 130                                 }
 131                         }
 132
 133                         switch t := under(typ).(type) {
 134                         case *Struct:
 135                                 for i, f := range t.fields {
 136                                         if fset == nil {
 137                                                 fset = make(map[string]bool)
 138                                         }
 139                                         fset[f.Id()] = true
 140
 141                                         // Embedded fields are always of the form T or *T where
 142                                         // T is a type name. If typ appeared multiple times at
 143                                         // this depth, f.Type appears multiple times at the next
 144                                         // depth.
 145                                         if f.embedded {
 146                                                 typ, isPtr := deref(f.typ)
 147                                                 // TODO(gri) optimization: ignore types that can't
 148                                                 // have fields or methods (only Named, Struct, and
 149                                                 // Interface types need to be considered).
 150                                                 next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples})
 151                                         }
 152                                 }
 153
 154                         case *Interface:
 155                                 mset = mset.add(t.typeSet().methods, e.index, true, e.multiples)
 156                         }
 157                 }
 158
 159                 // Add methods and collisions at this depth to base if no entries with matching
 160                 // names exist already.
 161                 for k, m := range mset {
 162                         if _, found := base[k]; !found {
 163                                 // Fields collide with methods of the same name at this depth.
 164                                 if fset[k] {
 165                                         m = nil // collision
 166                                 }
 167                                 if base == nil {
 168                                         base = make(methodSet)
 169                                 }
 170                                 base[k] = m
 171                         }
 172                 }
 173
 174                 // Add all (remaining) fields at this depth as collisions (since they will
 175                 // hide any method further down) if no entries with matching names exist already.
 176                 for k := range fset {
 177                         if _, found := base[k]; !found {
 178                                 if base == nil {
 179                                         base = make(methodSet)
 180                                 }
 181                                 base[k] = nil // collision
 182                         }
 183                 }
 184
 185                 current = consolidateMultiples(next)
 186         }
 187
 188         if len(base) == 0 {
 189                 return &emptyMethodSet
 190         }
 191
 192         // collect methods
 193         var list []*Selection
 194         for _, m := range base {
 195                 if m != nil {
 196                         m.recv = T
 197                         list = append(list, m)
 198                 }
 199         }
 200         // sort by unique name
 201         sort.Slice(list, func(i, j int) bool {
 202                 return list[i].obj.Id() < list[j].obj.Id()
 203         })
 204         return &MethodSet{list}
 205 }
 206
 207 // A methodSet is a set of methods and name collisions.
 208 // A collision indicates that multiple methods with the
 209 // same unique id, or a field with that id appeared.
 210 type methodSet map[string]*Selection // a nil entry indicates a name collision
 211
 212 // Add adds all functions in list to the method set s.
 213 // If multiples is set, every function in list appears multiple times
 214 // and is treated as a collision.
 215 func (s methodSet) add(list []*Func, index []int, indirect bool, multiples bool) methodSet {
 216         if len(list) == 0 {
 217                 return s
 218         }
 219         for i, f := range list {
 220                 s = s.addOne(f, concat(index, i), indirect, multiples)
 221         }
 222         return s
 223 }
 224
 225 func (s methodSet) addOne(f *Func, index []int, indirect bool, multiples bool) methodSet {
 226         if s == nil {
 227                 s = make(methodSet)
 228         }
 229         key := f.Id()
 230         // if f is not in the set, add it
 231         if !multiples {
 232                 // TODO(gri) A found method may not be added because it's not in the method set
 233                 // (!indirect && f.hasPtrRecv()). A 2nd method on the same level may be in the method
 234                 // set and may not collide with the first one, thus leading to a false positive.
 235                 // Is that possible? Investigate.
 236                 if _, found := s[key]; !found && (indirect || !f.hasPtrRecv()) {
 237                         s[key] = &Selection{MethodVal, nil, f, index, indirect}
 238                         return s
 239                 }
 240         }
 241         s[key] = nil // collision
 242         return s
 243 }