From 548090e67f66acf84385c4152ca464e52d3e3319 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Fri, 13 Sep 2024 13:01:48 +0200 Subject: Migrate away from templ and towards html/template --- vendor/golang.org/x/tools/go/callgraph/cha/cha.go | 164 ++++++++++++++++++++++ 1 file changed, 164 insertions(+) create mode 100644 vendor/golang.org/x/tools/go/callgraph/cha/cha.go (limited to 'vendor/golang.org/x/tools/go/callgraph/cha') diff --git a/vendor/golang.org/x/tools/go/callgraph/cha/cha.go b/vendor/golang.org/x/tools/go/callgraph/cha/cha.go new file mode 100644 index 0000000..3040f3d --- /dev/null +++ b/vendor/golang.org/x/tools/go/callgraph/cha/cha.go @@ -0,0 +1,164 @@ +// Copyright 2014 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 cha computes the call graph of a Go program using the Class +// Hierarchy Analysis (CHA) algorithm. +// +// CHA was first described in "Optimization of Object-Oriented Programs +// Using Static Class Hierarchy Analysis", Jeffrey Dean, David Grove, +// and Craig Chambers, ECOOP'95. +// +// CHA is related to RTA (see go/callgraph/rta); the difference is that +// CHA conservatively computes the entire "implements" relation between +// interfaces and concrete types ahead of time, whereas RTA uses dynamic +// programming to construct it on the fly as it encounters new functions +// reachable from main. CHA may thus include spurious call edges for +// types that haven't been instantiated yet, or types that are never +// instantiated. +// +// Since CHA conservatively assumes that all functions are address-taken +// and all concrete types are put into interfaces, it is sound to run on +// partial programs, such as libraries without a main or test function. +package cha // import "golang.org/x/tools/go/callgraph/cha" + +// TODO(zpavlinovic): update CHA for how it handles generic function bodies. + +import ( + "go/types" + + "golang.org/x/tools/go/callgraph" + "golang.org/x/tools/go/ssa" + "golang.org/x/tools/go/ssa/ssautil" + "golang.org/x/tools/go/types/typeutil" +) + +// CallGraph computes the call graph of the specified program using the +// Class Hierarchy Analysis algorithm. +func CallGraph(prog *ssa.Program) *callgraph.Graph { + cg := callgraph.New(nil) // TODO(adonovan) eliminate concept of rooted callgraph + + allFuncs := ssautil.AllFunctions(prog) + + calleesOf := lazyCallees(allFuncs) + + addEdge := func(fnode *callgraph.Node, site ssa.CallInstruction, g *ssa.Function) { + gnode := cg.CreateNode(g) + callgraph.AddEdge(fnode, site, gnode) + } + + addEdges := func(fnode *callgraph.Node, site ssa.CallInstruction, callees []*ssa.Function) { + // Because every call to a highly polymorphic and + // frequently used abstract method such as + // (io.Writer).Write is assumed to call every concrete + // Write method in the program, the call graph can + // contain a lot of duplication. + // + // TODO(taking): opt: consider making lazyCallees public. + // Using the same benchmarks as callgraph_test.go, removing just + // the explicit callgraph.Graph construction is 4x less memory + // and is 37% faster. + // CHA 86 ms/op 16 MB/op + // lazyCallees 63 ms/op 4 MB/op + for _, g := range callees { + addEdge(fnode, site, g) + } + } + + for f := range allFuncs { + fnode := cg.CreateNode(f) + for _, b := range f.Blocks { + for _, instr := range b.Instrs { + if site, ok := instr.(ssa.CallInstruction); ok { + if g := site.Common().StaticCallee(); g != nil { + addEdge(fnode, site, g) + } else { + addEdges(fnode, site, calleesOf(site)) + } + } + } + } + } + + return cg +} + +// lazyCallees returns a function that maps a call site (in a function in fns) +// to its callees within fns. +// +// The resulting function is not concurrency safe. +func lazyCallees(fns map[*ssa.Function]bool) func(site ssa.CallInstruction) []*ssa.Function { + // funcsBySig contains all functions, keyed by signature. It is + // the effective set of address-taken functions used to resolve + // a dynamic call of a particular signature. + var funcsBySig typeutil.Map // value is []*ssa.Function + + // methodsByID contains all methods, grouped by ID for efficient + // lookup. + // + // We must key by ID, not name, for correct resolution of interface + // calls to a type with two (unexported) methods spelled the same but + // from different packages. The fact that the concrete type implements + // the interface does not mean the call dispatches to both methods. + methodsByID := make(map[string][]*ssa.Function) + + // An imethod represents an interface method I.m. + // (There's no go/types object for it; + // a *types.Func may be shared by many interfaces due to interface embedding.) + type imethod struct { + I *types.Interface + id string + } + // methodsMemo records, for every abstract method call I.m on + // interface type I, the set of concrete methods C.m of all + // types C that satisfy interface I. + // + // Abstract methods may be shared by several interfaces, + // hence we must pass I explicitly, not guess from m. + // + // methodsMemo is just a cache, so it needn't be a typeutil.Map. + methodsMemo := make(map[imethod][]*ssa.Function) + lookupMethods := func(I *types.Interface, m *types.Func) []*ssa.Function { + id := m.Id() + methods, ok := methodsMemo[imethod{I, id}] + if !ok { + for _, f := range methodsByID[id] { + C := f.Signature.Recv().Type() // named or *named + if types.Implements(C, I) { + methods = append(methods, f) + } + } + methodsMemo[imethod{I, id}] = methods + } + return methods + } + + for f := range fns { + if f.Signature.Recv() == nil { + // Package initializers can never be address-taken. + if f.Name() == "init" && f.Synthetic == "package initializer" { + continue + } + funcs, _ := funcsBySig.At(f.Signature).([]*ssa.Function) + funcs = append(funcs, f) + funcsBySig.Set(f.Signature, funcs) + } else if obj := f.Object(); obj != nil { + id := obj.(*types.Func).Id() + methodsByID[id] = append(methodsByID[id], f) + } + } + + return func(site ssa.CallInstruction) []*ssa.Function { + call := site.Common() + if call.IsInvoke() { + tiface := call.Value.Type().Underlying().(*types.Interface) + return lookupMethods(tiface, call.Method) + } else if g := call.StaticCallee(); g != nil { + return []*ssa.Function{g} + } else if _, ok := call.Value.(*ssa.Builtin); !ok { + fns, _ := funcsBySig.At(call.Signature()).([]*ssa.Function) + return fns + } + return nil + } +} -- cgit v1.2.3