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