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