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
7package types
8
9import (
10	"bytes"
11	"fmt"
12	"sort"
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.
18type MethodSet struct {
19	list []*Selection
20}
21
22func (s *MethodSet) String() string {
23	if s.Len() == 0 {
24		return "MethodSet {}"
25	}
26
27	var buf bytes.Buffer
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.
37func (s *MethodSet) Len() int { return len(s.list) }
38
39// At returns the i'th method in s for 0 <= i < s.Len().
40func (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.
43func (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.
63var 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.
67func 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	named, _ := typ.(*Named)
76
77	// *typ where typ is an interface has no methods.
78	if isPtr {
79		utyp := typ
80		if named != nil {
81			utyp = named.underlying
82		}
83		if _, ok := utyp.(*Interface); ok {
84			return &emptyMethodSet
85		}
86	}
87
88	// Start with typ as single entry at shallowest depth.
89	// If typ is not a named type, insert a nil type instead.
90	current := []embeddedType{{named, nil, isPtr, false}}
91
92	// named types that we have seen already, allocated lazily
93	var seen map[*Named]bool
94
95	// collect methods at current depth
96	for len(current) > 0 {
97		var next []embeddedType // embedded types found at current depth
98
99		// field and method sets at current depth, allocated lazily
100		var fset fieldSet
101		var mset methodSet
102
103		for _, e := range current {
104			// The very first time only, e.typ may be nil.
105			// In this case, we don't have a named type and
106			// we simply continue with the underlying type.
107			if e.typ != nil {
108				if seen[e.typ] {
109					// We have seen this type before, at a more shallow depth
110					// (note that multiples of this type at the current depth
111					// were consolidated before). The type at that depth shadows
112					// this same type at the current depth, so we can ignore
113					// this one.
114					continue
115				}
116				if seen == nil {
117					seen = make(map[*Named]bool)
118				}
119				seen[e.typ] = true
120
121				mset = mset.add(e.typ.methods, e.index, e.indirect, e.multiples)
122
123				// continue with underlying type
124				typ = e.typ.underlying
125			}
126
127			switch t := typ.(type) {
128			case *Struct:
129				for i, f := range t.fields {
130					fset = fset.add(f, e.multiples)
131
132					// Embedded fields are always of the form T or *T where
133					// T is a named type. If typ appeared multiple times at
134					// this depth, f.Type appears multiple times at the next
135					// depth.
136					if f.anonymous {
137						// Ignore embedded basic types - only user-defined
138						// named types can have methods or struct fields.
139						typ, isPtr := deref(f.typ)
140						if t, _ := typ.(*Named); t != nil {
141							next = append(next, embeddedType{t, concat(e.index, i), e.indirect || isPtr, e.multiples})
142						}
143					}
144				}
145
146			case *Interface:
147				mset = mset.add(t.allMethods, e.index, true, e.multiples)
148			}
149		}
150
151		// Add methods and collisions at this depth to base if no entries with matching
152		// names exist already.
153		for k, m := range mset {
154			if _, found := base[k]; !found {
155				// Fields collide with methods of the same name at this depth.
156				if _, found := fset[k]; found {
157					m = nil // collision
158				}
159				if base == nil {
160					base = make(methodSet)
161				}
162				base[k] = m
163			}
164		}
165
166		// Multiple fields with matching names collide at this depth and shadow all
167		// entries further down; add them as collisions to base if no entries with
168		// matching names exist already.
169		for k, f := range fset {
170			if f == nil {
171				if _, found := base[k]; !found {
172					if base == nil {
173						base = make(methodSet)
174					}
175					base[k] = nil // collision
176				}
177			}
178		}
179
180		current = consolidateMultiples(next)
181	}
182
183	if len(base) == 0 {
184		return &emptyMethodSet
185	}
186
187	// collect methods
188	var list []*Selection
189	for _, m := range base {
190		if m != nil {
191			m.recv = T
192			list = append(list, m)
193		}
194	}
195	sort.Sort(byUniqueName(list))
196	return &MethodSet{list}
197}
198
199// A fieldSet is a set of fields and name collisions.
200// A collision indicates that multiple fields with the
201// same unique id appeared.
202type fieldSet map[string]*Var // a nil entry indicates a name collision
203
204// Add adds field f to the field set s.
205// If multiples is set, f appears multiple times
206// and is treated as a collision.
207func (s fieldSet) add(f *Var, multiples bool) fieldSet {
208	if s == nil {
209		s = make(fieldSet)
210	}
211	key := f.Id()
212	// if f is not in the set, add it
213	if !multiples {
214		if _, found := s[key]; !found {
215			s[key] = f
216			return s
217		}
218	}
219	s[key] = nil // collision
220	return s
221}
222
223// A methodSet is a set of methods and name collisions.
224// A collision indicates that multiple methods with the
225// same unique id appeared.
226type methodSet map[string]*Selection // a nil entry indicates a name collision
227
228// Add adds all functions in list to the method set s.
229// If multiples is set, every function in list appears multiple times
230// and is treated as a collision.
231func (s methodSet) add(list []*Func, index []int, indirect bool, multiples bool) methodSet {
232	if len(list) == 0 {
233		return s
234	}
235	if s == nil {
236		s = make(methodSet)
237	}
238	for i, f := range list {
239		key := f.Id()
240		// if f is not in the set, add it
241		if !multiples {
242			// TODO(gri) A found method may not be added because it's not in the method set
243			// (!indirect && ptrRecv(f)). A 2nd method on the same level may be in the method
244			// set and may not collide with the first one, thus leading to a false positive.
245			// Is that possible? Investigate.
246			if _, found := s[key]; !found && (indirect || !ptrRecv(f)) {
247				s[key] = &Selection{MethodVal, nil, f, concat(index, i), indirect}
248				continue
249			}
250		}
251		s[key] = nil // collision
252	}
253	return s
254}
255
256// ptrRecv reports whether the receiver is of the form *T.
257// The receiver must exist.
258func ptrRecv(f *Func) bool {
259	_, isPtr := deref(f.typ.(*Signature).recv.typ)
260	return isPtr
261}
262
263// byUniqueName function lists can be sorted by their unique names.
264type byUniqueName []*Selection
265
266func (a byUniqueName) Len() int           { return len(a) }
267func (a byUniqueName) Less(i, j int) bool { return a[i].obj.Id() < a[j].obj.Id() }
268func (a byUniqueName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
269