1// Copyright 2014 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
5package analysis
6
7// This file computes the "implements" relation over all pairs of
8// named types in the program.  (The mark-up is done by typeinfo.go.)
9
10// TODO(adonovan): do we want to report implements(C, I) where C and I
11// belong to different packages and at least one is not exported?
12
13import (
14	"go/types"
15	"sort"
16
17	"golang.org/x/tools/go/types/typeutil"
18)
19
20// computeImplements computes the "implements" relation over all pairs
21// of named types in allNamed.
22func computeImplements(cache *typeutil.MethodSetCache, allNamed []*types.Named) map[*types.Named]implementsFacts {
23	// Information about a single type's method set.
24	type msetInfo struct {
25		typ          types.Type
26		mset         *types.MethodSet
27		mask1, mask2 uint64
28	}
29
30	initMsetInfo := func(info *msetInfo, typ types.Type) {
31		info.typ = typ
32		info.mset = cache.MethodSet(typ)
33		for i := 0; i < info.mset.Len(); i++ {
34			name := info.mset.At(i).Obj().Name()
35			info.mask1 |= 1 << methodBit(name[0])
36			info.mask2 |= 1 << methodBit(name[len(name)-1])
37		}
38	}
39
40	// satisfies(T, U) reports whether type T satisfies type U.
41	// U must be an interface.
42	//
43	// Since there are thousands of types (and thus millions of
44	// pairs of types) and types.Assignable(T, U) is relatively
45	// expensive, we compute assignability directly from the
46	// method sets.  (At least one of T and U must be an
47	// interface.)
48	//
49	// We use a trick (thanks gri!) related to a Bloom filter to
50	// quickly reject most tests, which are false.  For each
51	// method set, we precompute a mask, a set of bits, one per
52	// distinct initial byte of each method name.  Thus the mask
53	// for io.ReadWriter would be {'R','W'}.  AssignableTo(T, U)
54	// cannot be true unless mask(T)&mask(U)==mask(U).
55	//
56	// As with a Bloom filter, we can improve precision by testing
57	// additional hashes, e.g. using the last letter of each
58	// method name, so long as the subset mask property holds.
59	//
60	// When analyzing the standard library, there are about 1e6
61	// calls to satisfies(), of which 0.6% return true.  With a
62	// 1-hash filter, 95% of calls avoid the expensive check; with
63	// a 2-hash filter, this grows to 98.2%.
64	satisfies := func(T, U *msetInfo) bool {
65		return T.mask1&U.mask1 == U.mask1 &&
66			T.mask2&U.mask2 == U.mask2 &&
67			containsAllIdsOf(T.mset, U.mset)
68	}
69
70	// Information about a named type N, and perhaps also *N.
71	type namedInfo struct {
72		isInterface bool
73		base        msetInfo // N
74		ptr         msetInfo // *N, iff N !isInterface
75	}
76
77	var infos []namedInfo
78
79	// Precompute the method sets and their masks.
80	for _, N := range allNamed {
81		var info namedInfo
82		initMsetInfo(&info.base, N)
83		_, info.isInterface = N.Underlying().(*types.Interface)
84		if !info.isInterface {
85			initMsetInfo(&info.ptr, types.NewPointer(N))
86		}
87
88		if info.base.mask1|info.ptr.mask1 == 0 {
89			continue // neither N nor *N has methods
90		}
91
92		infos = append(infos, info)
93	}
94
95	facts := make(map[*types.Named]implementsFacts)
96
97	// Test all pairs of distinct named types (T, U).
98	// TODO(adonovan): opt: compute (U, T) at the same time.
99	for t := range infos {
100		T := &infos[t]
101		var to, from, fromPtr []types.Type
102		for u := range infos {
103			if t == u {
104				continue
105			}
106			U := &infos[u]
107			switch {
108			case T.isInterface && U.isInterface:
109				if satisfies(&U.base, &T.base) {
110					to = append(to, U.base.typ)
111				}
112				if satisfies(&T.base, &U.base) {
113					from = append(from, U.base.typ)
114				}
115			case T.isInterface: // U concrete
116				if satisfies(&U.base, &T.base) {
117					to = append(to, U.base.typ)
118				} else if satisfies(&U.ptr, &T.base) {
119					to = append(to, U.ptr.typ)
120				}
121			case U.isInterface: // T concrete
122				if satisfies(&T.base, &U.base) {
123					from = append(from, U.base.typ)
124				} else if satisfies(&T.ptr, &U.base) {
125					fromPtr = append(fromPtr, U.base.typ)
126				}
127			}
128		}
129
130		// Sort types (arbitrarily) to avoid nondeterminism.
131		sort.Sort(typesByString(to))
132		sort.Sort(typesByString(from))
133		sort.Sort(typesByString(fromPtr))
134
135		facts[T.base.typ.(*types.Named)] = implementsFacts{to, from, fromPtr}
136	}
137
138	return facts
139}
140
141type implementsFacts struct {
142	to      []types.Type // named or ptr-to-named types assignable to interface T
143	from    []types.Type // named interfaces assignable from T
144	fromPtr []types.Type // named interfaces assignable only from *T
145}
146
147type typesByString []types.Type
148
149func (p typesByString) Len() int           { return len(p) }
150func (p typesByString) Less(i, j int) bool { return p[i].String() < p[j].String() }
151func (p typesByString) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
152
153// methodBit returns the index of x in [a-zA-Z], or 52 if not found.
154func methodBit(x byte) uint64 {
155	switch {
156	case 'a' <= x && x <= 'z':
157		return uint64(x - 'a')
158	case 'A' <= x && x <= 'Z':
159		return uint64(26 + x - 'A')
160	}
161	return 52 // all other bytes
162}
163
164// containsAllIdsOf reports whether the method identifiers of T are a
165// superset of those in U.  If U belongs to an interface type, the
166// result is equal to types.Assignable(T, U), but is cheaper to compute.
167//
168// TODO(gri): make this a method of *types.MethodSet.
169//
170func containsAllIdsOf(T, U *types.MethodSet) bool {
171	t, tlen := 0, T.Len()
172	u, ulen := 0, U.Len()
173	for t < tlen && u < ulen {
174		tMeth := T.At(t).Obj()
175		uMeth := U.At(u).Obj()
176		tId := tMeth.Id()
177		uId := uMeth.Id()
178		if tId > uId {
179			// U has a method T lacks: fail.
180			return false
181		}
182		if tId < uId {
183			// T has a method U lacks: ignore it.
184			t++
185			continue
186		}
187		// U and T both have a method of this Id.  Check types.
188		if !types.Identical(tMeth.Type(), uMeth.Type()) {
189			return false // type mismatch
190		}
191		u++
192		t++
193	}
194	return u == ulen
195}
196