// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package typerefs extracts symbol-level reachability information
// from the syntax of a Go package.
//
// # Background
//
// The goal of this analysis is to determine, for each package P, a nearly
// minimal set of packages that could affect the type checking of P. This set
// may contain false positives, but the smaller this set the better we can
// invalidate and prune packages in gopls.
//
// More precisely, for each package P we define the set of "reachable" packages
// from P as the set of packages that may affect the (deep) export data of the
// direct dependencies of P. By this definition, the complement of this set
// cannot affect any information derived from type checking P, such as
// diagnostics, cross references, or method sets. Therefore we need not
// invalidate any results for P when a package in the complement of this set
// changes.
//
// # Computing references
//
// For a given declaration D, references are computed based on identifiers or
// dotted identifiers referenced in the declaration of D, that may affect
// the type of D. However, these references reflect only local knowledge of the
// package and its dependency metadata, and do not depend on any analysis of
// the dependencies themselves. This allows the reference information for
// a package to be cached independent of all others.
//
// Specifically, if a referring identifier I appears in the declaration, we
// record an edge from D to each object possibly referenced by I. We search for
// references within type syntax, but do not actually type-check, so we can't
// reliably determine whether an expression is a type or a term, or whether a
// function is a builtin or generic. For example, the type of x in var x =
// p.F(W) only depends on W if p.F is a builtin or generic function, which we
// cannot know without type-checking package p. So we may over-approximate in
// this way.
//
//   - If I is declared in the current package, record a reference to its
//     declaration.
//   - Otherwise, if there are any dot imports in the current
//     file and I is exported, record a (possibly dangling) edge to
//     the corresponding declaration in each dot-imported package.
//
// If a dotted identifier q.I appears in the declaration, we
// perform a similar operation:
//
//   - If q is declared in the current package, we record a reference to that
//     object. It may be a var or const that has a field or method I.
//   - Otherwise, if q is a valid import name based on imports in the current file
//     and the provided metadata for dependency package names, record a
//     reference to the object I in that package.
//   - Additionally, handle the case where Q is exported, and Q.I may refer to
//     a field or method in a dot-imported package.
//
// That is essentially the entire algorithm, though there is some subtlety to
// visiting the set of identifiers or dotted identifiers that may affect the
// declaration type. See the visitDeclOrSpec function for the details of this
// analysis. Notably, we also skip identifiers that refer to type parameters in
// generic declarations.
//
// # Graph optimizations
//
// The references extracted from the syntax are used to construct
// edges between nodes representing declarations. Edges are of two
// kinds: internal references, from one package-level declaration to
// another; and external references, from a symbol in this package to
// a symbol imported from a direct dependency.
//
// Once the symbol reference graph is constructed, we find its
// strongly connected components (SCCs) using Tarjan's algorithm.
// As we coalesce the nodes of each SCC we compute the union of
// external references reached by each package-level declaration.
// The final result is the mapping from each exported package-level
// declaration to the set of external (imported) declarations that it
// reaches.
//
// Because it is common for many package members to have the same
// reachability, the result takes the form of a set of equivalence
// classes, each mapping a set of package-level declarations to a set
// of external symbols. We use a hash table to canonicalize sets so that
// repeated occurrences of the same set (which are common) are only
// represented once in memory or in the file system.
// For example, all declarations that ultimately reference only
// {fmt.Println,strings.Join} would be classed as equivalent.
//
// This approach was inspired by the Hash-Value Numbering (HVN)
// optimization described by Hardekopf and Lin. See
// golang.org/x/tools/go/pointer/hvn.go for an implementation. (Like
// pointer analysis, this problem is fundamentally one of graph
// reachability.) The HVN algorithm takes the compression a step
// further by preserving the topology of the SCC DAG, in which edges
// represent "is a superset of" constraints. Redundant edges that
// don't increase the solution can be deleted. We could apply the same
// technique here to further reduce the worst-case size of the result,
// but the current implementation seems adequate.
//
// # API
//
// The main entry point for this analysis is the [Encode] function,
// which implements the analysis described above for one package, and
// encodes the result as a binary message.
//
// The [Decode] function decodes the message into a usable form: a set
// of equivalence classes. The decoder uses a shared [PackageIndex] to
// enable more compact representations of sets of packages
// ([PackageSet]) during the global reacahability computation.
//
// The [BuildPackageGraph] constructor implements a whole-graph analysis similar
// to that which will be implemented by gopls, but for various reasons the
// logic for this analysis will eventually live in the
// [golang.org/x/tools/gopls/internal/lsp/cache] package. Nevertheless,
// BuildPackageGraph and its test serve to verify the syntactic analysis, and
// may serve as a proving ground for new optimizations of the whole-graph analysis.
//
// # Export data is insufficient
//
// At first it may seem that the simplest way to implement this analysis would
// be to consider the types.Packages of the dependencies of P, for example
// during export. After all, it makes sense that the type checked packages
// themselves could describe their dependencies. However, this does not work as
// type information does not describe certain syntactic relationships.
//
// For example, the following scenarios cause type information to miss
// syntactic relationships:
//
// Named type forwarding:
//
//	package a; type A b.B
//	package b; type B int
//
// Aliases:
//
//	package a; func A(f b.B)
//	package b; type B = func()
//
// Initializers:
//
//	package a; var A = b.B()
//	package b; func B() string { return "hi" }
//
// Use of the unsafe package:
//
//	package a; type A [unsafe.Sizeof(B{})]int
//	package b; type B struct { f1, f2, f3 int }
//
// In all of these examples, types do not contain information about the edge
// between the a.A and b.B declarations.
package typerefs