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 := asNamed(typ); 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 mset = mset.add(named.methods, e.index, e.indirect, e.multiples) 129 130 // continue with underlying type, but only if it's not a type parameter 131 // TODO(rFindley): should this use named.under()? Can there be a difference? 132 typ = named.underlying 133 if _, ok := typ.(*_TypeParam); ok { 134 continue 135 } 136 } 137 138 switch t := typ.(type) { 139 case *Struct: 140 for i, f := range t.fields { 141 if fset == nil { 142 fset = make(map[string]bool) 143 } 144 fset[f.Id()] = true 145 146 // Embedded fields are always of the form T or *T where 147 // T is a type name. If typ appeared multiple times at 148 // this depth, f.Type appears multiple times at the next 149 // depth. 150 if f.embedded { 151 typ, isPtr := deref(f.typ) 152 // TODO(gri) optimization: ignore types that can't 153 // have fields or methods (only Named, Struct, and 154 // Interface types need to be considered). 155 next = append(next, embeddedType{typ, concat(e.index, i), e.indirect || isPtr, e.multiples}) 156 } 157 } 158 159 case *Interface: 160 mset = mset.add(t.allMethods, e.index, true, e.multiples) 161 162 case *_TypeParam: 163 mset = mset.add(t.Bound().allMethods, e.index, true, e.multiples) 164 } 165 } 166 167 // Add methods and collisions at this depth to base if no entries with matching 168 // names exist already. 169 for k, m := range mset { 170 if _, found := base[k]; !found { 171 // Fields collide with methods of the same name at this depth. 172 if fset[k] { 173 m = nil // collision 174 } 175 if base == nil { 176 base = make(methodSet) 177 } 178 base[k] = m 179 } 180 } 181 182 // Add all (remaining) fields at this depth as collisions (since they will 183 // hide any method further down) if no entries with matching names exist already. 184 for k := range fset { 185 if _, found := base[k]; !found { 186 if base == nil { 187 base = make(methodSet) 188 } 189 base[k] = nil // collision 190 } 191 } 192 193 // It's ok to call consolidateMultiples with a nil *Checker because 194 // MethodSets are not used internally (outside debug mode). When used 195 // externally, interfaces are expected to be completed and then we do 196 // not need a *Checker to complete them when (indirectly) calling 197 // Checker.identical via consolidateMultiples. 198 current = (*Checker)(nil).consolidateMultiples(next) 199 } 200 201 if len(base) == 0 { 202 return &emptyMethodSet 203 } 204 205 // collect methods 206 var list []*Selection 207 for _, m := range base { 208 if m != nil { 209 m.recv = T 210 list = append(list, m) 211 } 212 } 213 // sort by unique name 214 sort.Slice(list, func(i, j int) bool { 215 return list[i].obj.Id() < list[j].obj.Id() 216 }) 217 return &MethodSet{list} 218 } 219 220 // A methodSet is a set of methods and name collisions. 221 // A collision indicates that multiple methods with the 222 // same unique id, or a field with that id appeared. 223 type methodSet map[string]*Selection // a nil entry indicates a name collision 224 225 // Add adds all functions in list to the method set s. 226 // If multiples is set, every function in list appears multiple times 227 // and is treated as a collision. 228 func (s methodSet) add(list []*Func, index []int, indirect bool, multiples bool) methodSet { 229 if len(list) == 0 { 230 return s 231 } 232 if s == nil { 233 s = make(methodSet) 234 } 235 for i, f := range list { 236 key := f.Id() 237 // if f is not in the set, add it 238 if !multiples { 239 // TODO(gri) A found method may not be added because it's not in the method set 240 // (!indirect && ptrRecv(f)). A 2nd method on the same level may be in the method 241 // set and may not collide with the first one, thus leading to a false positive. 242 // Is that possible? Investigate. 243 if _, found := s[key]; !found && (indirect || !ptrRecv(f)) { 244 s[key] = &Selection{MethodVal, nil, f, concat(index, i), indirect} 245 continue 246 } 247 } 248 s[key] = nil // collision 249 } 250 return s 251 } 252 253 // ptrRecv reports whether the receiver is of the form *T. 254 func ptrRecv(f *Func) bool { 255 // If a method's receiver type is set, use that as the source of truth for the receiver. 256 // Caution: Checker.funcDecl (decl.go) marks a function by setting its type to an empty 257 // signature. We may reach here before the signature is fully set up: we must explicitly 258 // check if the receiver is set (we cannot just look for non-nil f.typ). 259 if sig, _ := f.typ.(*Signature); sig != nil && sig.recv != nil { 260 _, isPtr := deref(sig.recv.typ) 261 return isPtr 262 } 263 264 // If a method's type is not set it may be a method/function that is: 265 // 1) client-supplied (via NewFunc with no signature), or 266 // 2) internally created but not yet type-checked. 267 // For case 1) we can't do anything; the client must know what they are doing. 268 // For case 2) we can use the information gathered by the resolver. 269 return f.hasPtrRecv 270 } 271