facts.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 defines a serializable set of analysis.Fact.
     6  //
     7  // It provides a partial implementation of the Fact-related parts of the
     8  // analysis.Pass interface for use in analysis drivers such as "go vet"
     9  // and other build systems.
    10  //
    11  // The serial format is unspecified and may change, so the same version
    12  // of this package must be used for reading and writing serialized facts.
    13  //
    14  // The handling of facts in the analysis system parallels the handling
    15  // of type information in the compiler: during compilation of package P,
    16  // the compiler emits an export data file that describes the type of
    17  // every object (named thing) defined in package P, plus every object
    18  // indirectly reachable from one of those objects. Thus the downstream
    19  // compiler of package Q need only load one export data file per direct
    20  // import of Q, and it will learn everything about the API of package P
    21  // and everything it needs to know about the API of P's dependencies.
    22  //
    23  // Similarly, analysis of package P emits a fact set containing facts
    24  // about all objects exported from P, plus additional facts about only
    25  // those objects of P's dependencies that are reachable from the API of
    26  // package P; the downstream analysis of Q need only load one fact set
    27  // per direct import of Q.
    28  //
    29  // The notion of "exportedness" that matters here is that of the
    30  // compiler. According to the language spec, a method pkg.T.f is
    31  // unexported simply because its name starts with lowercase. But the
    32  // compiler must nonetheless export f so that downstream compilations can
    33  // accurately ascertain whether pkg.T implements an interface pkg.I
    34  // defined as interface{f()}. Exported thus means "described in export
    35  // data".
    36  package facts
    37  
    38  import (
    39  	"bytes"
    40  	"encoding/gob"
    41  	"fmt"
    42  	"go/types"
    43  	"io"
    44  	"log"
    45  	"reflect"
    46  	"sort"
    47  	"sync"
    48  
    49  	"golang.org/x/tools/go/analysis"
    50  	"golang.org/x/tools/go/types/objectpath"
    51  )
    52  
    53  const debug = false
    54  
    55  // A Set is a set of analysis.Facts.
    56  //
    57  // Decode creates a Set of facts by reading from the imports of a given
    58  // package, and Encode writes out the set. Between these operation,
    59  // the Import and Export methods will query and update the set.
    60  //
    61  // All of Set's methods except String are safe to call concurrently.
    62  type Set struct {
    63  	pkg *types.Package
    64  	mu  sync.Mutex
    65  	m   map[key]analysis.Fact
    66  }
    67  
    68  type key struct {
    69  	pkg *types.Package
    70  	obj types.Object // (object facts only)
    71  	t   reflect.Type
    72  }
    73  
    74  // ImportObjectFact implements analysis.Pass.ImportObjectFact.
    75  func (s *Set) ImportObjectFact(obj types.Object, ptr analysis.Fact) bool {
    76  	if obj == nil {
    77  		panic("nil object")
    78  	}
    79  	key := key{pkg: obj.Pkg(), obj: obj, t: reflect.TypeOf(ptr)}
    80  	s.mu.Lock()
    81  	defer s.mu.Unlock()
    82  	if v, ok := s.m[key]; ok {
    83  		reflect.ValueOf(ptr).Elem().Set(reflect.ValueOf(v).Elem())
    84  		return true
    85  	}
    86  	return false
    87  }
    88  
    89  // ExportObjectFact implements analysis.Pass.ExportObjectFact.
    90  func (s *Set) ExportObjectFact(obj types.Object, fact analysis.Fact) {
    91  	if obj.Pkg() != s.pkg {
    92  		log.Panicf("in package %s: ExportObjectFact(%s, %T): can't set fact on object belonging another package",
    93  			s.pkg, obj, fact)
    94  	}
    95  	key := key{pkg: obj.Pkg(), obj: obj, t: reflect.TypeOf(fact)}
    96  	s.mu.Lock()
    97  	s.m[key] = fact // clobber any existing entry
    98  	s.mu.Unlock()
    99  }
   100  
   101  func (s *Set) AllObjectFacts(filter map[reflect.Type]bool) []analysis.ObjectFact {
   102  	var facts []analysis.ObjectFact
   103  	s.mu.Lock()
   104  	for k, v := range s.m {
   105  		if k.obj != nil && filter[k.t] {
   106  			facts = append(facts, analysis.ObjectFact{Object: k.obj, Fact: v})
   107  		}
   108  	}
   109  	s.mu.Unlock()
   110  	return facts
   111  }
   112  
   113  // ImportPackageFact implements analysis.Pass.ImportPackageFact.
   114  func (s *Set) ImportPackageFact(pkg *types.Package, ptr analysis.Fact) bool {
   115  	if pkg == nil {
   116  		panic("nil package")
   117  	}
   118  	key := key{pkg: pkg, t: reflect.TypeOf(ptr)}
   119  	s.mu.Lock()
   120  	defer s.mu.Unlock()
   121  	if v, ok := s.m[key]; ok {
   122  		reflect.ValueOf(ptr).Elem().Set(reflect.ValueOf(v).Elem())
   123  		return true
   124  	}
   125  	return false
   126  }
   127  
   128  // ExportPackageFact implements analysis.Pass.ExportPackageFact.
   129  func (s *Set) ExportPackageFact(fact analysis.Fact) {
   130  	key := key{pkg: s.pkg, t: reflect.TypeOf(fact)}
   131  	s.mu.Lock()
   132  	s.m[key] = fact // clobber any existing entry
   133  	s.mu.Unlock()
   134  }
   135  
   136  func (s *Set) AllPackageFacts(filter map[reflect.Type]bool) []analysis.PackageFact {
   137  	var facts []analysis.PackageFact
   138  	s.mu.Lock()
   139  	for k, v := range s.m {
   140  		if k.obj == nil && filter[k.t] {
   141  			facts = append(facts, analysis.PackageFact{Package: k.pkg, Fact: v})
   142  		}
   143  	}
   144  	s.mu.Unlock()
   145  	return facts
   146  }
   147  
   148  // gobFact is the Gob declaration of a serialized fact.
   149  type gobFact struct {
   150  	PkgPath string          // path of package
   151  	Object  objectpath.Path // optional path of object relative to package itself
   152  	Fact    analysis.Fact   // type and value of user-defined Fact
   153  }
   154  
   155  // A Decoder decodes the facts from the direct imports of the package
   156  // provided to NewEncoder. A single decoder may be used to decode
   157  // multiple fact sets (e.g. each for a different set of fact types)
   158  // for the same package. Each call to Decode returns an independent
   159  // fact set.
   160  type Decoder struct {
   161  	pkg        *types.Package
   162  	getPackage GetPackageFunc
   163  }
   164  
   165  // NewDecoder returns a fact decoder for the specified package.
   166  //
   167  // It uses a brute-force recursive approach to enumerate all objects
   168  // defined by dependencies of pkg, so that it can learn the set of
   169  // package paths that may be mentioned in the fact encoding. This does
   170  // not scale well; use [NewDecoderFunc] where possible.
   171  func NewDecoder(pkg *types.Package) *Decoder {
   172  	// Compute the import map for this package.
   173  	// See the package doc comment.
   174  	m := importMap(pkg.Imports())
   175  	getPackageFunc := func(path string) *types.Package { return m[path] }
   176  	return NewDecoderFunc(pkg, getPackageFunc)
   177  }
   178  
   179  // NewDecoderFunc returns a fact decoder for the specified package.
   180  //
   181  // It calls the getPackage function for the package path string of
   182  // each dependency (perhaps indirect) that it encounters in the
   183  // encoding. If the function returns nil, the fact is discarded.
   184  //
   185  // This function is preferred over [NewDecoder] when the client is
   186  // capable of efficient look-up of packages by package path.
   187  func NewDecoderFunc(pkg *types.Package, getPackage GetPackageFunc) *Decoder {
   188  	return &Decoder{
   189  		pkg:        pkg,
   190  		getPackage: getPackage,
   191  	}
   192  }
   193  
   194  // A GetPackageFunc function returns the package denoted by a package path.
   195  type GetPackageFunc = func(pkgPath string) *types.Package
   196  
   197  // Decode decodes all the facts relevant to the analysis of package
   198  // pkgPath. The read function reads serialized fact data from an external
   199  // source for one of pkg's direct imports, identified by package path.
   200  // The empty file is a valid encoding of an empty fact set.
   201  //
   202  // It is the caller's responsibility to call gob.Register on all
   203  // necessary fact types.
   204  //
   205  // Concurrent calls to Decode are safe, so long as the
   206  // [GetPackageFunc] (if any) is also concurrency-safe.
   207  func (d *Decoder) Decode(read func(pkgPath string) ([]byte, error)) (*Set, error) {
   208  	// Read facts from imported packages.
   209  	// Facts may describe indirectly imported packages, or their objects.
   210  	m := make(map[key]analysis.Fact) // one big bucket
   211  	for _, imp := range d.pkg.Imports() {
   212  		logf := func(format string, args ...interface{}) {
   213  			if debug {
   214  				prefix := fmt.Sprintf("in %s, importing %s: ",
   215  					d.pkg.Path(), imp.Path())
   216  				log.Print(prefix, fmt.Sprintf(format, args...))
   217  			}
   218  		}
   219  
   220  		// Read the gob-encoded facts.
   221  		data, err := read(imp.Path())
   222  		if err != nil {
   223  			return nil, fmt.Errorf("in %s, can't import facts for package %q: %v",
   224  				d.pkg.Path(), imp.Path(), err)
   225  		}
   226  		if len(data) == 0 {
   227  			continue // no facts
   228  		}
   229  		var gobFacts []gobFact
   230  		if err := gob.NewDecoder(bytes.NewReader(data)).Decode(&gobFacts); err != nil {
   231  			return nil, fmt.Errorf("decoding facts for %q: %v", imp.Path(), err)
   232  		}
   233  		logf("decoded %d facts: %v", len(gobFacts), gobFacts)
   234  
   235  		// Parse each one into a key and a Fact.
   236  		for _, f := range gobFacts {
   237  			factPkg := d.getPackage(f.PkgPath) // possibly an indirect dependency
   238  			if factPkg == nil {
   239  				// Fact relates to a dependency that was
   240  				// unused in this translation unit. Skip.
   241  				logf("no package %q; discarding %v", f.PkgPath, f.Fact)
   242  				continue
   243  			}
   244  			key := key{pkg: factPkg, t: reflect.TypeOf(f.Fact)}
   245  			if f.Object != "" {
   246  				// object fact
   247  				obj, err := objectpath.Object(factPkg, f.Object)
   248  				if err != nil {
   249  					// (most likely due to unexported object)
   250  					// TODO(adonovan): audit for other possibilities.
   251  					logf("no object for path: %v; discarding %s", err, f.Fact)
   252  					continue
   253  				}
   254  				key.obj = obj
   255  				logf("read %T fact %s for %v", f.Fact, f.Fact, key.obj)
   256  			} else {
   257  				// package fact
   258  				logf("read %T fact %s for %v", f.Fact, f.Fact, factPkg)
   259  			}
   260  			m[key] = f.Fact
   261  		}
   262  	}
   263  
   264  	return &Set{pkg: d.pkg, m: m}, nil
   265  }
   266  
   267  // Encode encodes a set of facts to a memory buffer.
   268  //
   269  // It may fail if one of the Facts could not be gob-encoded, but this is
   270  // a sign of a bug in an Analyzer.
   271  func (s *Set) Encode() []byte {
   272  	encoder := new(objectpath.Encoder)
   273  
   274  	// TODO(adonovan): opt: use a more efficient encoding
   275  	// that avoids repeating PkgPath for each fact.
   276  
   277  	// Gather all facts, including those from imported packages.
   278  	var gobFacts []gobFact
   279  
   280  	s.mu.Lock()
   281  	for k, fact := range s.m {
   282  		if debug {
   283  			log.Printf("%v => %s\n", k, fact)
   284  		}
   285  
   286  		// Don't export facts that we imported from another
   287  		// package, unless they represent fields or methods,
   288  		// or package-level types.
   289  		// (Facts about packages, and other package-level
   290  		// objects, are only obtained from direct imports so
   291  		// they needn't be reexported.)
   292  		//
   293  		// This is analogous to the pruning done by "deep"
   294  		// export data for types, but not as precise because
   295  		// we aren't careful about which structs or methods
   296  		// we rexport: it should be only those referenced
   297  		// from the API of s.pkg.
   298  		// TODO(adonovan): opt: be more precise. e.g.
   299  		// intersect with the set of objects computed by
   300  		// importMap(s.pkg.Imports()).
   301  		// TODO(adonovan): opt: implement "shallow" facts.
   302  		if k.pkg != s.pkg {
   303  			if k.obj == nil {
   304  				continue // imported package fact
   305  			}
   306  			if _, isType := k.obj.(*types.TypeName); !isType &&
   307  				k.obj.Parent() == k.obj.Pkg().Scope() {
   308  				continue // imported fact about package-level non-type object
   309  			}
   310  		}
   311  
   312  		var object objectpath.Path
   313  		if k.obj != nil {
   314  			path, err := encoder.For(k.obj)
   315  			if err != nil {
   316  				if debug {
   317  					log.Printf("discarding fact %s about %s\n", fact, k.obj)
   318  				}
   319  				continue // object not accessible from package API; discard fact
   320  			}
   321  			object = path
   322  		}
   323  		gobFacts = append(gobFacts, gobFact{
   324  			PkgPath: k.pkg.Path(),
   325  			Object:  object,
   326  			Fact:    fact,
   327  		})
   328  	}
   329  	s.mu.Unlock()
   330  
   331  	// Sort facts by (package, object, type) for determinism.
   332  	sort.Slice(gobFacts, func(i, j int) bool {
   333  		x, y := gobFacts[i], gobFacts[j]
   334  		if x.PkgPath != y.PkgPath {
   335  			return x.PkgPath < y.PkgPath
   336  		}
   337  		if x.Object != y.Object {
   338  			return x.Object < y.Object
   339  		}
   340  		tx := reflect.TypeOf(x.Fact)
   341  		ty := reflect.TypeOf(y.Fact)
   342  		if tx != ty {
   343  			return tx.String() < ty.String()
   344  		}
   345  		return false // equal
   346  	})
   347  
   348  	var buf bytes.Buffer
   349  	if len(gobFacts) > 0 {
   350  		if err := gob.NewEncoder(&buf).Encode(gobFacts); err != nil {
   351  			// Fact encoding should never fail. Identify the culprit.
   352  			for _, gf := range gobFacts {
   353  				if err := gob.NewEncoder(io.Discard).Encode(gf); err != nil {
   354  					fact := gf.Fact
   355  					pkgpath := reflect.TypeOf(fact).Elem().PkgPath()
   356  					log.Panicf("internal error: gob encoding of analysis fact %s failed: %v; please report a bug against fact %T in package %q",
   357  						fact, err, fact, pkgpath)
   358  				}
   359  			}
   360  		}
   361  	}
   362  
   363  	if debug {
   364  		log.Printf("package %q: encode %d facts, %d bytes\n",
   365  			s.pkg.Path(), len(gobFacts), buf.Len())
   366  	}
   367  
   368  	return buf.Bytes()
   369  }
   370  
   371  // String is provided only for debugging, and must not be called
   372  // concurrent with any Import/Export method.
   373  func (s *Set) String() string {
   374  	var buf bytes.Buffer
   375  	buf.WriteString("{")
   376  	for k, f := range s.m {
   377  		if buf.Len() > 1 {
   378  			buf.WriteString(", ")
   379  		}
   380  		if k.obj != nil {
   381  			buf.WriteString(k.obj.String())
   382  		} else {
   383  			buf.WriteString(k.pkg.Path())
   384  		}
   385  		fmt.Fprintf(&buf, ": %v", f)
   386  	}
   387  	buf.WriteString("}")
   388  	return buf.String()
   389  }
   390
View as plain text