crawler.go

     1  // Copyright 2021 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 typecheck
     6  
     7  import (
     8  	"cmd/compile/internal/base"
     9  	"cmd/compile/internal/ir"
    10  	"cmd/compile/internal/types"
    11  	"cmd/internal/src"
    12  )
    13  
    14  // crawlExports crawls the type/object graph rooted at the given list of exported
    15  // objects (which are variables, functions, and types). It descends through all parts
    16  // of types and follows methods on defined types. Any functions that are found to be
    17  // potentially callable by importers directly or after inlining are marked with
    18  // ExportInline, so that iexport.go knows to export their inline body.
    19  //
    20  // The overall purpose of crawlExports is to AVOID exporting inlineable methods
    21  // that cannot actually be referenced, thereby reducing the size of the exports
    22  // significantly.
    23  //
    24  // For non-generic defined types reachable from global variables, we only set
    25  // ExportInline for exported methods. For defined types that are directly named or are
    26  // embedded recursively in such a type, we set ExportInline for all methods, since
    27  // these types can be embedded in another local type. For instantiated types that are
    28  // used anywhere in a inlineable function, we set ExportInline on all methods of the
    29  // base generic type, since all methods will be needed for creating any instantiated
    30  // type.
    31  func crawlExports(exports []*ir.Name) {
    32  	p := crawler{
    33  		marked:         make(map[*types.Type]bool),
    34  		embedded:       make(map[*types.Type]bool),
    35  		generic:        make(map[*types.Type]bool),
    36  		checkFullyInst: make(map[*types.Type]bool),
    37  	}
    38  	for _, n := range exports {
    39  		p.markObject(n)
    40  	}
    41  }
    42  
    43  type crawler struct {
    44  	marked         map[*types.Type]bool // types already seen by markType
    45  	embedded       map[*types.Type]bool // types already seen by markEmbed
    46  	generic        map[*types.Type]bool // types already seen by markGeneric
    47  	checkFullyInst map[*types.Type]bool // types already seen by checkForFullyInst
    48  }
    49  
    50  // markObject visits a reachable object (function, method, global type, or global variable)
    51  func (p *crawler) markObject(n *ir.Name) {
    52  	if n.Op() == ir.ONAME && n.Class == ir.PFUNC {
    53  		p.markInlBody(n)
    54  	}
    55  
    56  	// If a declared type name is reachable, users can embed it in their
    57  	// own types, which makes even its unexported methods reachable.
    58  	if n.Op() == ir.OTYPE {
    59  		p.markEmbed(n.Type())
    60  	}
    61  
    62  	p.markType(n.Type())
    63  }
    64  
    65  // markType recursively visits types reachable from t to identify functions whose
    66  // inline bodies may be needed. For instantiated generic types, it visits the base
    67  // generic type, which has the relevant methods.
    68  func (p *crawler) markType(t *types.Type) {
    69  	if orig := t.OrigType(); orig != nil {
    70  		// Convert to the base generic type.
    71  		t = orig
    72  	}
    73  	if p.marked[t] {
    74  		return
    75  	}
    76  	p.marked[t] = true
    77  
    78  	// If this is a defined type, mark all of its associated
    79  	// methods. Skip interface types because t.Methods contains
    80  	// only their unexpanded method set (i.e., exclusive of
    81  	// interface embeddings), and the switch statement below
    82  	// handles their full method set.
    83  	if t.Sym() != nil && t.Kind() != types.TINTER {
    84  		for _, m := range t.Methods().Slice() {
    85  			if types.IsExported(m.Sym.Name) {
    86  				p.markObject(m.Nname.(*ir.Name))
    87  			}
    88  		}
    89  	}
    90  
    91  	// Recursively mark any types that can be produced given a
    92  	// value of type t: dereferencing a pointer; indexing or
    93  	// iterating over an array, slice, or map; receiving from a
    94  	// channel; accessing a struct field or interface method; or
    95  	// calling a function.
    96  	//
    97  	// Notably, we don't mark function parameter types, because
    98  	// the user already needs some way to construct values of
    99  	// those types.
   100  	switch t.Kind() {
   101  	case types.TPTR, types.TARRAY, types.TSLICE:
   102  		p.markType(t.Elem())
   103  
   104  	case types.TCHAN:
   105  		if t.ChanDir().CanRecv() {
   106  			p.markType(t.Elem())
   107  		}
   108  
   109  	case types.TMAP:
   110  		p.markType(t.Key())
   111  		p.markType(t.Elem())
   112  
   113  	case types.TSTRUCT:
   114  		if t.IsFuncArgStruct() {
   115  			break
   116  		}
   117  		for _, f := range t.FieldSlice() {
   118  			// Mark the type of a unexported field if it is a
   119  			// fully-instantiated type, since we create and instantiate
   120  			// the methods of any fully-instantiated type that we see
   121  			// during import (see end of typecheck.substInstType).
   122  			if types.IsExported(f.Sym.Name) || f.Embedded != 0 ||
   123  				isPtrFullyInstantiated(f.Type) {
   124  				p.markType(f.Type)
   125  			}
   126  		}
   127  
   128  	case types.TFUNC:
   129  		for _, f := range t.Results().FieldSlice() {
   130  			p.markType(f.Type)
   131  		}
   132  
   133  	case types.TINTER:
   134  		for _, f := range t.AllMethods().Slice() {
   135  			if types.IsExported(f.Sym.Name) {
   136  				p.markType(f.Type)
   137  			}
   138  		}
   139  
   140  	case types.TTYPEPARAM:
   141  		// No other type that needs to be followed.
   142  	}
   143  }
   144  
   145  // markEmbed is similar to markType, but handles finding methods that
   146  // need to be re-exported because t can be embedded in user code
   147  // (possibly transitively).
   148  func (p *crawler) markEmbed(t *types.Type) {
   149  	if t.IsPtr() {
   150  		// Defined pointer type; not allowed to embed anyway.
   151  		if t.Sym() != nil {
   152  			return
   153  		}
   154  		t = t.Elem()
   155  	}
   156  
   157  	if orig := t.OrigType(); orig != nil {
   158  		// Convert to the base generic type.
   159  		t = orig
   160  	}
   161  
   162  	if p.embedded[t] {
   163  		return
   164  	}
   165  	p.embedded[t] = true
   166  
   167  	// If t is a defined type, then re-export all of its methods. Unlike
   168  	// in markType, we include even unexported methods here, because we
   169  	// still need to generate wrappers for them, even if the user can't
   170  	// refer to them directly.
   171  	if t.Sym() != nil && t.Kind() != types.TINTER {
   172  		for _, m := range t.Methods().Slice() {
   173  			p.markObject(m.Nname.(*ir.Name))
   174  		}
   175  	}
   176  
   177  	// If t is a struct, recursively visit its embedded fields.
   178  	if t.IsStruct() {
   179  		for _, f := range t.FieldSlice() {
   180  			if f.Embedded != 0 {
   181  				p.markEmbed(f.Type)
   182  			}
   183  		}
   184  	}
   185  }
   186  
   187  // markGeneric takes an instantiated type or a base generic type t, and marks all the
   188  // methods of the base generic type of t. If a base generic type is written out for
   189  // export, even if not explicitly marked for export, then all of its methods need to
   190  // be available for instantiation, since we always create all methods of a specified
   191  // instantiated type. Non-exported methods must generally be instantiated, since they may
   192  // be called by the exported methods or other generic function in the same package.
   193  func (p *crawler) markGeneric(t *types.Type) {
   194  	if t.IsPtr() {
   195  		t = t.Elem()
   196  	}
   197  	if orig := t.OrigType(); orig != nil {
   198  		// Convert to the base generic type.
   199  		t = orig
   200  	}
   201  	if p.generic[t] {
   202  		return
   203  	}
   204  	p.generic[t] = true
   205  
   206  	if t.Sym() != nil && t.Kind() != types.TINTER {
   207  		for _, m := range t.Methods().Slice() {
   208  			p.markObject(m.Nname.(*ir.Name))
   209  		}
   210  	}
   211  }
   212  
   213  // checkForFullyInst looks for fully-instantiated types in a type (at any nesting
   214  // level). If it finds a fully-instantiated type, it ensures that the necessary
   215  // dictionary and shape methods are exported. It updates p.checkFullyInst, so it
   216  // traverses each particular type only once.
   217  func (p *crawler) checkForFullyInst(t *types.Type) {
   218  	if p.checkFullyInst[t] {
   219  		return
   220  	}
   221  	p.checkFullyInst[t] = true
   222  
   223  	if t.IsFullyInstantiated() && !t.HasShape() && !t.IsInterface() && t.Methods().Len() > 0 {
   224  		// For any fully-instantiated type, the relevant
   225  		// dictionaries and shape instantiations will have
   226  		// already been created or are in the import data.
   227  		// Make sure that they are exported, so that any
   228  		// other package that inlines this function will have
   229  		// them available for import, and so will not need
   230  		// another round of method and dictionary
   231  		// instantiation after inlining.
   232  		baseType := t.OrigType()
   233  		shapes := make([]*types.Type, len(t.RParams()))
   234  		for i, t1 := range t.RParams() {
   235  			shapes[i] = Shapify(t1, i, baseType.RParams()[i])
   236  		}
   237  		for j, tmethod := range t.Methods().Slice() {
   238  			baseNname := baseType.Methods().Slice()[j].Nname.(*ir.Name)
   239  			dictsym := MakeDictSym(baseNname.Sym(), t.RParams(), true)
   240  			if dictsym.Def == nil {
   241  				in := Resolve(ir.NewIdent(src.NoXPos, dictsym))
   242  				dictsym = in.Sym()
   243  			}
   244  			Export(dictsym.Def.(*ir.Name))
   245  			methsym := MakeFuncInstSym(baseNname.Sym(), shapes, false, true)
   246  			if methsym.Def == nil {
   247  				in := Resolve(ir.NewIdent(src.NoXPos, methsym))
   248  				methsym = in.Sym()
   249  			}
   250  			methNode := methsym.Def.(*ir.Name)
   251  			Export(methNode)
   252  			if HaveInlineBody(methNode.Func) {
   253  				// Export the body as well if
   254  				// instantiation is inlineable.
   255  				ImportedBody(methNode.Func)
   256  				methNode.Func.SetExportInline(true)
   257  			}
   258  			// Make sure that any associated types are also exported. (See #52279)
   259  			p.checkForFullyInst(tmethod.Type)
   260  		}
   261  	}
   262  
   263  	// Descend into the type. We descend even if it is a fully-instantiated type,
   264  	// since the instantiated type may have other instantiated types inside of
   265  	// it (in fields, methods, etc.).
   266  	switch t.Kind() {
   267  	case types.TPTR, types.TARRAY, types.TSLICE:
   268  		p.checkForFullyInst(t.Elem())
   269  
   270  	case types.TCHAN:
   271  		p.checkForFullyInst(t.Elem())
   272  
   273  	case types.TMAP:
   274  		p.checkForFullyInst(t.Key())
   275  		p.checkForFullyInst(t.Elem())
   276  
   277  	case types.TSTRUCT:
   278  		if t.IsFuncArgStruct() {
   279  			break
   280  		}
   281  		for _, f := range t.FieldSlice() {
   282  			p.checkForFullyInst(f.Type)
   283  		}
   284  
   285  	case types.TFUNC:
   286  		if recv := t.Recv(); recv != nil {
   287  			p.checkForFullyInst(t.Recv().Type)
   288  		}
   289  		for _, f := range t.Params().FieldSlice() {
   290  			p.checkForFullyInst(f.Type)
   291  		}
   292  		for _, f := range t.Results().FieldSlice() {
   293  			p.checkForFullyInst(f.Type)
   294  		}
   295  
   296  	case types.TINTER:
   297  		for _, f := range t.AllMethods().Slice() {
   298  			p.checkForFullyInst(f.Type)
   299  		}
   300  	}
   301  }
   302  
   303  // markInlBody marks n's inline body for export and recursively
   304  // ensures all called functions are marked too.
   305  func (p *crawler) markInlBody(n *ir.Name) {
   306  	if n == nil {
   307  		return
   308  	}
   309  	if n.Op() != ir.ONAME || n.Class != ir.PFUNC {
   310  		base.Fatalf("markInlBody: unexpected %v, %v, %v", n, n.Op(), n.Class)
   311  	}
   312  	fn := n.Func
   313  	if fn == nil {
   314  		base.Fatalf("markInlBody: missing Func on %v", n)
   315  	}
   316  	if !HaveInlineBody(fn) {
   317  		return
   318  	}
   319  
   320  	if fn.ExportInline() {
   321  		return
   322  	}
   323  	fn.SetExportInline(true)
   324  
   325  	ImportedBody(fn)
   326  
   327  	var doFlood func(n ir.Node)
   328  	doFlood = func(n ir.Node) {
   329  		t := n.Type()
   330  		if t != nil {
   331  			if t.HasTParam() {
   332  				// If any generic types are used, then make sure that
   333  				// the methods of the generic type are exported and
   334  				// scanned for other possible exports.
   335  				p.markGeneric(t)
   336  			} else {
   337  				p.checkForFullyInst(t)
   338  			}
   339  			if base.Debug.Unified == 0 {
   340  				// If a method of un-exported type is promoted and accessible by
   341  				// embedding in an exported type, it makes that type reachable.
   342  				//
   343  				// Example:
   344  				//
   345  				//     type t struct {}
   346  				//     func (t) M() {}
   347  				//
   348  				//     func F() interface{} { return struct{ t }{} }
   349  				//
   350  				// We generate the wrapper for "struct{ t }".M, and inline call
   351  				// to "struct{ t }".M, which makes "t.M" reachable.
   352  				if t.IsStruct() {
   353  					for _, f := range t.FieldSlice() {
   354  						if f.Embedded != 0 {
   355  							p.markEmbed(f.Type)
   356  						}
   357  					}
   358  				}
   359  			}
   360  		}
   361  
   362  		switch n.Op() {
   363  		case ir.OMETHEXPR, ir.ODOTMETH:
   364  			p.markInlBody(ir.MethodExprName(n))
   365  		case ir.ONAME:
   366  			n := n.(*ir.Name)
   367  			switch n.Class {
   368  			case ir.PFUNC:
   369  				p.markInlBody(n)
   370  				// Note: this Export() and the one below seem unneeded,
   371  				// since any function/extern name encountered in an
   372  				// exported function body will be exported
   373  				// automatically via qualifiedIdent() in iexport.go.
   374  				Export(n)
   375  			case ir.PEXTERN:
   376  				Export(n)
   377  			}
   378  		case ir.OMETHVALUE:
   379  			// Okay, because we don't yet inline indirect
   380  			// calls to method values.
   381  		case ir.OCLOSURE:
   382  			// VisitList doesn't visit closure bodies, so force a
   383  			// recursive call to VisitList on the body of the closure.
   384  			ir.VisitList(n.(*ir.ClosureExpr).Func.Body, doFlood)
   385  		}
   386  	}
   387  
   388  	// Recursively identify all referenced functions for
   389  	// reexport. We want to include even non-called functions,
   390  	// because after inlining they might be callable.
   391  	ir.VisitList(fn.Inl.Body, doFlood)
   392  }
   393  
   394  // isPtrFullyInstantiated returns true if t is a fully-instantiated type, or it is a
   395  // pointer to a fully-instantiated type.
   396  func isPtrFullyInstantiated(t *types.Type) bool {
   397  	return t.IsPtr() && t.Elem().IsFullyInstantiated() ||
   398  		t.IsFullyInstantiated()
   399  }
   400
View as plain text