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 func ptrRecv(f *Func) bool { 259 // If a method's receiver type is set, use that as the source of truth for the receiver. 260 // Caution: Checker.funcDecl (decl.go) marks a function by setting its type to an empty 261 // signature. We may reach here before the signature is fully set up: we must explicitly 262 // check if the receiver is set (we cannot just look for non-nil f.typ). 263 if sig, _ := f.typ.(*Signature); sig != nil && sig.recv != nil { 264 _, isPtr := deref(sig.recv.typ) 265 return isPtr 266 } 267 268 // If a method's type is not set it may be a method/function that is: 269 // 1) client-supplied (via NewFunc with no signature), or 270 // 2) internally created but not yet type-checked. 271 // For case 1) we can't do anything; the client must know what they are doing. 272 // For case 2) we can use the information gathered by the resolver. 273 return f.hasPtrRecv 274 } 275