imports.go

     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  
     5  package facts
     6  
     7  import (
     8  	"go/types"
     9  
    10  	"golang.org/x/tools/internal/typesinternal"
    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.
    30  func 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 *types.Basic:
    51  			// nop
    52  		case typesinternal.NamedOrAlias: // *types.{Named,Alias}
    53  			// Add the type arguments if this is an instance.
    54  			if targs := T.TypeArgs(); targs.Len() > 0 {
    55  				for t := range targs.Types() {
    56  					addType(t)
    57  				}
    58  			}
    59  
    60  			// Remove infinite expansions of *types.Named by always looking at the origin.
    61  			// Some named types with type parameters [that will not type check] have
    62  			// infinite expansions:
    63  			//     type N[T any] struct { F *N[N[T]] }
    64  			// importMap() is called on such types when Analyzer.RunDespiteErrors is true.
    65  			T = typesinternal.Origin(T)
    66  			if !typs[T] {
    67  				typs[T] = true
    68  
    69  				// common aspects
    70  				addObj(T.Obj())
    71  				if tparams := T.TypeParams(); tparams.Len() > 0 {
    72  					for tparam := range tparams.TypeParams() {
    73  						addType(tparam)
    74  					}
    75  				}
    76  
    77  				// variant aspects
    78  				switch T := T.(type) {
    79  				case *types.Alias:
    80  					addType(T.Rhs())
    81  				case *types.Named:
    82  					addType(T.Underlying())
    83  					for method := range T.Methods() {
    84  						addObj(method)
    85  					}
    86  				}
    87  			}
    88  		case *types.Pointer:
    89  			addType(T.Elem())
    90  		case *types.Slice:
    91  			addType(T.Elem())
    92  		case *types.Array:
    93  			addType(T.Elem())
    94  		case *types.Chan:
    95  			addType(T.Elem())
    96  		case *types.Map:
    97  			addType(T.Key())
    98  			addType(T.Elem())
    99  		case *types.Signature:
   100  			addType(T.Params())
   101  			addType(T.Results())
   102  			if tparams := T.TypeParams(); tparams != nil {
   103  				for tparam := range tparams.TypeParams() {
   104  					addType(tparam)
   105  				}
   106  			}
   107  		case *types.Struct:
   108  			for field := range T.Fields() {
   109  				addObj(field)
   110  			}
   111  		case *types.Tuple:
   112  			for v := range T.Variables() {
   113  				addObj(v)
   114  			}
   115  		case *types.Interface:
   116  			for method := range T.Methods() {
   117  				addObj(method)
   118  			}
   119  			for etyp := range T.EmbeddedTypes() {
   120  				addType(etyp) // walk Embedded for implicits
   121  			}
   122  		case *types.Union:
   123  			for term := range T.Terms() {
   124  				addType(term.Type())
   125  			}
   126  		case *types.TypeParam:
   127  			if !typs[T] {
   128  				typs[T] = true
   129  				addObj(T.Obj())
   130  				addType(T.Constraint())
   131  			}
   132  		}
   133  	}
   134  
   135  	for _, imp := range imports {
   136  		packages[imp.Path()] = imp
   137  
   138  		scope := imp.Scope()
   139  		for _, name := range scope.Names() {
   140  			addObj(scope.Lookup(name))
   141  		}
   142  	}
   143  
   144  	return packages
   145  }
   146
View as plain text