// computeImplements computes the "implements" relation over all pairs
// of named types in allNamed.
func computeImplements(cache *typeutil.MethodSetCache, allNamed []*types.Named) map[*types.Named]implementsFacts {
	// Information about a single type's method set.
	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(T, U) reports whether type T satisfies type U.
	// U must be an interface.
	//
	// Since there are thousands of types (and thus millions of
	// pairs of types) and types.Assignable(T, U) is relatively
	// expensive, we compute assignability directly from the
	// method sets.  (At least one of T and U must be an
	// interface.)
	//
	// We use a trick (thanks gri!) related to a Bloom filter to
	// quickly reject most tests, which are false.  For each
	// method set, we precompute a mask, a set of bits, one per
	// distinct initial byte of each method name.  Thus the mask
	// for io.ReadWriter would be {'R','W'}.  AssignableTo(T, U)
	// cannot be true unless mask(T)&mask(U)==mask(U).
	//
	// As with a Bloom filter, we can improve precision by testing
	// additional hashes, e.g. using the last letter of each
	// method name, so long as the subset mask property holds.
	//
	// When analyzing the standard library, there are about 1e6
	// calls to satisfies(), of which 0.6% return true.  With a
	// 1-hash filter, 95% of calls avoid the expensive check; with
	// a 2-hash filter, this grows to 98.2%.
	satisfies := func(T, U *msetInfo) bool {
		return T.mask1&U.mask1 == U.mask1 &&
			T.mask2&U.mask2 == U.mask2 &&
			containsAllIdsOf(T.mset, U.mset)
	}

	// Information about a named type N, and perhaps also *N.
	type namedInfo struct {
		isInterface bool
		base        msetInfo // N
		ptr         msetInfo // *N, iff N !isInterface
	}

	var infos []namedInfo

	// Precompute the method sets and their masks.
	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 // neither N nor *N has methods
		}

		infos = append(infos, info)
	}

	facts := make(map[*types.Named]implementsFacts)

	// Test all pairs of distinct named types (T, U).
	// TODO(adonovan): opt: compute (U, T) at the same time.
	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: // U concrete
				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)
//.........这里部分代码省略.........

// Implements displays the "implements" relation as it pertains to the
// selected type.
// If the selection is a method, 'implements' displays
// the corresponding methods of the types that would have been reported
// by an implements query on the receiver type.
//
func implements(q *Query) error {
	lconf := loader.Config{Build: q.Build}
	allowErrors(&lconf)

	qpkg, err := importQueryPackage(q.Pos, &lconf)
	if err != nil {
		return err
	}

	// Set the packages to search.
	if len(q.Scope) > 0 {
		// Inspect all packages in the analysis scope, if specified.
		if err := setPTAScope(&lconf, q.Scope); err != nil {
			return err
		}
	} else {
		// Otherwise inspect the forward and reverse
		// transitive closure of the selected package.
		// (In theory even this is incomplete.)
		_, rev, _ := importgraph.Build(q.Build)
		for path := range rev.Search(qpkg) {
			lconf.ImportWithTests(path)
		}

		// TODO(adonovan): for completeness, we should also
		// type-check and inspect function bodies in all
		// imported packages.  This would be expensive, but we
		// could optimize by skipping functions that do not
		// contain type declarations.  This would require
		// changing the loader's TypeCheckFuncBodies hook to
		// provide the []*ast.File.
	}

	// Load/parse/type-check the program.
	lprog, err := lconf.Load()
	if err != nil {
		return err
	}
	q.Fset = lprog.Fset

	qpos, err := parseQueryPos(lprog, q.Pos, false)
	if err != nil {
		return err
	}

	// Find the selected type.
	path, action := findInterestingNode(qpos.info, qpos.path)

	var method *types.Func
	var T types.Type // selected type (receiver if method != nil)

	switch action {
	case actionExpr:
		// method?
		if id, ok := path[0].(*ast.Ident); ok {
			if obj, ok := qpos.info.ObjectOf(id).(*types.Func); ok {
				recv := obj.Type().(*types.Signature).Recv()
				if recv == nil {
					return fmt.Errorf("this function is not a method")
				}
				method = obj
				T = recv.Type()
			}
		}
	case actionType:
		T = qpos.info.TypeOf(path[0].(ast.Expr))
	}
	if T == nil {
		return fmt.Errorf("no type or method here")
	}

	// Find all named types, even local types (which can have
	// methods via promotion) and the built-in "error".
	var allNamed []types.Type
	for _, info := range lprog.AllPackages {
		for _, obj := range info.Defs {
			if obj, ok := obj.(*types.TypeName); ok {
				allNamed = append(allNamed, obj.Type())
			}
		}
	}
	allNamed = append(allNamed, types.Universe.Lookup("error").Type())

	var msets typeutil.MethodSetCache

	// Test each named type.
	var to, from, fromPtr []types.Type
	for _, U := range allNamed {
		if isInterface(T) {
			if msets.MethodSet(T).Len() == 0 {
				continue // empty interface
			}
			if isInterface(U) {
				if msets.MethodSet(U).Len() == 0 {
//.........这里部分代码省略.........

// Implements displays the "implements" relation as it pertains to the
// selected type within a single package.
// If the selection is a method, 'implements' displays
// the corresponding methods of the types that would have been reported
// by an implements query on the receiver type.
//
func implements(q *Query) error {
	lconf := loader.Config{Build: q.Build}
	allowErrors(&lconf)

	if err := importQueryPackage(q.Pos, &lconf); err != nil {
		return err
	}

	// Load/parse/type-check the program.
	lprog, err := lconf.Load()
	if err != nil {
		return err
	}
	q.Fset = lprog.Fset

	qpos, err := parseQueryPos(lprog, q.Pos, false)
	if err != nil {
		return err
	}

	// Find the selected type.
	path, action := findInterestingNode(qpos.info, qpos.path)

	var method *types.Func
	var T types.Type // selected type (receiver if method != nil)

	switch action {
	case actionExpr:
		// method?
		if id, ok := path[0].(*ast.Ident); ok {
			if obj, ok := qpos.info.ObjectOf(id).(*types.Func); ok {
				recv := obj.Type().(*types.Signature).Recv()
				if recv == nil {
					return fmt.Errorf("this function is not a method")
				}
				method = obj
				T = recv.Type()
			}
		}
	case actionType:
		T = qpos.info.TypeOf(path[0].(ast.Expr))
	}
	if T == nil {
		return fmt.Errorf("no type or method here")
	}

	// Find all named types, even local types (which can have
	// methods via promotion) and the built-in "error".
	//
	// TODO(adonovan): include all packages in PTA scope too?
	// i.e. don't reduceScope?
	//
	var allNamed []types.Type
	for _, info := range lprog.AllPackages {
		for _, obj := range info.Defs {
			if obj, ok := obj.(*types.TypeName); ok {
				allNamed = append(allNamed, obj.Type())
			}
		}
	}
	allNamed = append(allNamed, types.Universe.Lookup("error").Type())

	var msets typeutil.MethodSetCache

	// Test each named type.
	var to, from, fromPtr []types.Type
	for _, U := range allNamed {
		if isInterface(T) {
			if msets.MethodSet(T).Len() == 0 {
				continue // empty interface
			}
			if isInterface(U) {
				if msets.MethodSet(U).Len() == 0 {
					continue // empty interface
				}

				// T interface, U interface
				if !types.Identical(T, U) {
					if types.AssignableTo(U, T) {
						to = append(to, U)
					}
					if types.AssignableTo(T, U) {
						from = append(from, U)
					}
				}
			} else {
				// T interface, U concrete
				if types.AssignableTo(U, T) {
					to = append(to, U)
				} else if pU := types.NewPointer(U); types.AssignableTo(pU, T) {
					to = append(to, pU)
				}
			}
		} else if isInterface(U) {
//.........这里部分代码省略.........