// Encode analyzes the Go syntax trees of a package, constructs a // reference graph, and uses it to compute, for each exported // declaration, the set of exported symbols of directly imported // packages that it references, perhaps indirectly. // // It returns a serializable index of this information. // Use Decode to expand the result. func Encode(files []*parsego.File, imports map[metadata.ImportPath]*metadata.Package) []byte { … } // Decode decodes a serializable index of symbol // reachability produced by Encode. // // Because many declarations reference the exact same set of symbols, // the results are grouped into equivalence classes. // Classes are sorted by Decls[0], ascending. // The class with empty reachability is omitted. // // See the package documentation for more details as to what a // reference does (and does not) represent. func Decode(pkgIndex *PackageIndex, data []byte) []Class { … } type Class … type Symbol … type IndexID … type symbolSet … type symbol … type declNode … type state … // getClassIndex returns the small integer (an index into // state.class) that identifies the given set. func (st *state) getClassIndex(set symbolSet) int { … } // appendSorted appends the symbols to syms, sorts by ascending // (PackageID, name), and returns the result. // The argument must be an empty slice, ideally with capacity len(set). func (set symbolSet) appendSorted(syms []symbol) []symbol { … } // classKey returns a key such that equal keys imply equal sets. // (e.g. a sorted string representation, or a cryptographic hash of same). func classKey(set symbolSet) string { … } // index builds the reference graph and encodes the index. func index(pgfs []*parsego.File, imports map[metadata.ImportPath]*metadata.Package) []byte { … } // visitFile inspects the file syntax for referring identifiers, and // populates the internal and external references of decls. func visitFile(file *ast.File, imports map[metadata.ImportPath]*metadata.Package, decls map[string]*declNode) { … } // tparamsMap returns a set recording each name declared by the provided field // list. It so happens that we only care about names declared by type parameter // lists. func tparamsMap(tparams *ast.FieldList) map[string]bool { … } type refVisitor … // visitDeclOrSpec visits referring idents or dotted idents that may affect // the type of the declaration at the given node, which must be an ast.Decl or // ast.Spec. func visitDeclOrSpec(node ast.Node, f refVisitor) { … } // visitExpr visits referring idents and dotted idents that may affect the // type of expr. // // visitExpr can't reliably distinguish a dotted ident pkg.X from a // selection expr.f or T.method. func visitExpr(expr ast.Expr, f refVisitor) { … } func visitExprList(list []ast.Expr, f refVisitor) { … } func visitFieldList(n *ast.FieldList, f refVisitor) { … } // visit implements the depth-first search of Tarjan's SCC algorithm // (see https://doi.org/10.1137/0201010). // Precondition: x is canonical. func (st *state) visit(x *declNode) { … } // coalesce combines two nodes in the strong component graph. // Precondition: x and y are canonical. func coalesce(x, y *declNode) { … } // find returns the canonical node decl. // (The nodes form a disjoint set forest.) func (decl *declNode) find() *declNode { … } const debugSCC … func checkCanonical(x *declNode) { … } func assert(cond bool, msg string) { … } var classesCodec … type gobClasses … type gobClass … // encode encodes the equivalence classes, // (classNames[i], classes[i]), for i in range classes. // // With the current encoding, across kubernetes, // the encoded size distribution has // p50 = 511B, p95 = 4.4KB, max = 108K. func encode(classNames map[int][]string, classes []symbolSet) []byte { … } func decode(pkgIndex *PackageIndex, data []byte) []Class { … }
Codebase Browser
gotools