1// Copyright 2018 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 facts
6
7import (
8	"go/types"
9
10	"golang.org/x/tools/internal/aliases"
11)
12
13// importMap computes the import map for a package by traversing the
14// entire exported API each of its imports.
15//
16// This is a workaround for the fact that we cannot access the map used
17// internally by the types.Importer returned by go/importer. The entries
18// in this map are the packages and objects that may be relevant to the
19// current analysis unit.
20//
21// Packages in the map that are only indirectly imported may be
22// incomplete (!pkg.Complete()).
23//
24// This function scales very poorly with packages' transitive object
25// references, which can be more than a million for each package near
26// the top of a large project. (This was a significant contributor to
27// #60621.)
28// TODO(adonovan): opt: compute this information more efficiently
29// by obtaining it from the internals of the gcexportdata decoder.
30func importMap(imports []*types.Package) map[string]*types.Package {
31	objects := make(map[types.Object]bool)
32	typs := make(map[types.Type]bool) // Named and TypeParam
33	packages := make(map[string]*types.Package)
34
35	var addObj func(obj types.Object)
36	var addType func(T types.Type)
37
38	addObj = func(obj types.Object) {
39		if !objects[obj] {
40			objects[obj] = true
41			addType(obj.Type())
42			if pkg := obj.Pkg(); pkg != nil {
43				packages[pkg.Path()] = pkg
44			}
45		}
46	}
47
48	addType = func(T types.Type) {
49		switch T := T.(type) {
50		case *aliases.Alias:
51			addType(aliases.Unalias(T))
52		case *types.Basic:
53			// nop
54		case *types.Named:
55			// Remove infinite expansions of *types.Named by always looking at the origin.
56			// Some named types with type parameters [that will not type check] have
57			// infinite expansions:
58			//     type N[T any] struct { F *N[N[T]] }
59			// importMap() is called on such types when Analyzer.RunDespiteErrors is true.
60			T = T.Origin()
61			if !typs[T] {
62				typs[T] = true
63				addObj(T.Obj())
64				addType(T.Underlying())
65				for i := 0; i < T.NumMethods(); i++ {
66					addObj(T.Method(i))
67				}
68				if tparams := T.TypeParams(); tparams != nil {
69					for i := 0; i < tparams.Len(); i++ {
70						addType(tparams.At(i))
71					}
72				}
73				if targs := T.TypeArgs(); targs != nil {
74					for i := 0; i < targs.Len(); i++ {
75						addType(targs.At(i))
76					}
77				}
78			}
79		case *types.Pointer:
80			addType(T.Elem())
81		case *types.Slice:
82			addType(T.Elem())
83		case *types.Array:
84			addType(T.Elem())
85		case *types.Chan:
86			addType(T.Elem())
87		case *types.Map:
88			addType(T.Key())
89			addType(T.Elem())
90		case *types.Signature:
91			addType(T.Params())
92			addType(T.Results())
93			if tparams := T.TypeParams(); tparams != nil {
94				for i := 0; i < tparams.Len(); i++ {
95					addType(tparams.At(i))
96				}
97			}
98		case *types.Struct:
99			for i := 0; i < T.NumFields(); i++ {
100				addObj(T.Field(i))
101			}
102		case *types.Tuple:
103			for i := 0; i < T.Len(); i++ {
104				addObj(T.At(i))
105			}
106		case *types.Interface:
107			for i := 0; i < T.NumMethods(); i++ {
108				addObj(T.Method(i))
109			}
110			for i := 0; i < T.NumEmbeddeds(); i++ {
111				addType(T.EmbeddedType(i)) // walk Embedded for implicits
112			}
113		case *types.Union:
114			for i := 0; i < T.Len(); i++ {
115				addType(T.Term(i).Type())
116			}
117		case *types.TypeParam:
118			if !typs[T] {
119				typs[T] = true
120				addObj(T.Obj())
121				addType(T.Constraint())
122			}
123		}
124	}
125
126	for _, imp := range imports {
127		packages[imp.Path()] = imp
128
129		scope := imp.Scope()
130		for _, name := range scope.Names() {
131			addObj(scope.Lookup(name))
132		}
133	}
134
135	return packages
136}
137