func containsAllIdsOf(T, U *types.MethodSet) bool {
	t, tlen := 0, T.Len()
	u, ulen := 0, U.Len()
	for t < tlen && u < ulen {
		tMeth := T.At(t).Obj()
		uMeth := U.At(u).Obj()
		tId := tMeth.Id()
		uId := uMeth.Id()
		if tId > uId {
			return false
		}
		if tId < uId {
			t++
			continue
		}
		if !types.Identical(tMeth.Type(), uMeth.Type()) {
			return false  
		}
		u++
		t++
	}
	return u == ulen
}
containsAllIdsOf reports whether the method identifiers of T are a
superset of those in U.  If U belongs to an interface type, the
result is equal to types.Assignable(T, U), but is cheaper to compute.

TODO(gri): make this a method of *types.MethodSet.
package analysis
import (
	"go/types"
	"sort"
	"golang.org/x/tools/go/types/typeutil"
)
func computeImplements(cache *typeutil.MethodSetCache, allNamed []*types.Named) map[*types.Named]implementsFacts {
	type msetInfo struct {
		typ          types.Type
		mset         *types.MethodSet
		mask1, mask2 uint64
	}
	initMsetInfo := func(info *msetInfo, typ types.Type) {
		info.typ = typ
		info.mset = cache.MethodSet(typ)
		for i := 0; i < info.mset.Len(); i++ {
			name := info.mset.At(i).Obj().Name()
			info.mask1 |= 1 << methodBit(name[0])
			info.mask2 |= 1 << methodBit(name[len(name)-1])
		}
	}
	satisfies := func(T, U *msetInfo) bool {
		return T.mask1&U.mask1 == U.mask1 &&
			T.mask2&U.mask2 == U.mask2 &&
			containsAllIdsOf(T.mset, U.mset)
	}
	type namedInfo struct {
		isInterface bool
		base        msetInfo  
		ptr         msetInfo  
	}
	var infos []namedInfo
	for _, N := range allNamed {
		var info namedInfo
		initMsetInfo(&info.base, N)
		_, info.isInterface = N.Underlying().(*types.Interface)
		if !info.isInterface {
			initMsetInfo(&info.ptr, types.NewPointer(N))
		}
		if info.base.mask1|info.ptr.mask1 == 0 {
			continue  
		}
		infos = append(infos, info)
	}
	facts := make(map[*types.Named]implementsFacts)
	for t := range infos {
		T := &infos[t]
		var to, from, fromPtr []types.Type
		for u := range infos {
			if t == u {
				continue
			}
			U := &infos[u]
			switch {
			case T.isInterface && U.isInterface:
				if satisfies(&U.base, &T.base) {
					to = append(to, U.base.typ)
				}
				if satisfies(&T.base, &U.base) {
					from = append(from, U.base.typ)
				}
			case T.isInterface:  
				if satisfies(&U.base, &T.base) {
					to = append(to, U.base.typ)
				} else if satisfies(&U.ptr, &T.base) {
					to = append(to, U.ptr.typ)
				}
			case U.isInterface:  
				if satisfies(&T.base, &U.base) {
					from = append(from, U.base.typ)
				} else if satisfies(&T.ptr, &U.base) {
					fromPtr = append(fromPtr, U.base.typ)
				}
			}
		}
		sort.Sort(typesByString(to))
		sort.Sort(typesByString(from))
		sort.Sort(typesByString(fromPtr))
		facts[T.base.typ.(*types.Named)] = implementsFacts{to, from, fromPtr}
	}
	return facts
}
type implementsFacts struct {
	to      []types.Type  
	from    []types.Type  
	fromPtr []types.Type  
}
type typesByString []types.Type
func (p typesByString) Len() int           { return len(p) }
func (p typesByString) Less(i, j int) bool { return p[i].String() < p[j].String() }
func (p typesByString) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func methodBit(x byte) uint64 {
	switch {
	case 'a' <= x && x <= 'z':
		return uint64(x - 'a')
	case 'A' <= x && x <= 'Z':
		return uint64(26 + x - 'A')
	}
	return 52  
}