.gitignore added

[dotfiles/.git] / .config / coc / extensions / coc-go-data / tools / pkg / mod / honnef.co / go / tools@v0.1.1 / go / callgraph / rta / rta.go

// Copyright 2013 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.

// This package provides Rapid Type Analysis (RTA) for Go, a fast
// algorithm for call graph construction and discovery of reachable code
// (and hence dead code) and runtime types.  The algorithm was first
// described in:
//
// David F. Bacon and Peter F. Sweeney. 1996.
// Fast static analysis of C++ virtual function calls. (OOPSLA '96)
// http://doi.acm.org/10.1145/236337.236371
//
// The algorithm uses dynamic programming to tabulate the cross-product
// of the set of known "address taken" functions with the set of known
// dynamic calls of the same type.  As each new address-taken function
// is discovered, call graph edges are added from each known callsite,
// and as each new call site is discovered, call graph edges are added
// from it to each known address-taken function.
//
// A similar approach is used for dynamic calls via interfaces: it
// tabulates the cross-product of the set of known "runtime types",
// i.e. types that may appear in an interface value, or be derived from
// one via reflection, with the set of known "invoke"-mode dynamic
// calls.  As each new "runtime type" is discovered, call edges are
// added from the known call sites, and as each new call site is
// discovered, call graph edges are added to each compatible
// method.
//
// In addition, we must consider all exported methods of any runtime type
// as reachable, since they may be called via reflection.
//
// Each time a newly added call edge causes a new function to become
// reachable, the code of that function is analyzed for more call sites,
// address-taken functions, and runtime types.  The process continues
// until a fixed point is achieved.
//
// The resulting call graph is less precise than one produced by pointer
// analysis, but the algorithm is much faster.  For example, running the
// cmd/callgraph tool on its own source takes ~2.1s for RTA and ~5.4s
// for points-to analysis.
//
package rta

// TODO(adonovan): test it by connecting it to the interpreter and
// replacing all "unreachable" functions by a special intrinsic, and
// ensure that that intrinsic is never called.

import (
        "fmt"
        "go/types"

        "honnef.co/go/tools/go/callgraph"
        "honnef.co/go/tools/go/ir"

        "golang.org/x/tools/go/types/typeutil"
)

// A Result holds the results of Rapid Type Analysis, which includes the
// set of reachable functions/methods, runtime types, and the call graph.
//
type Result struct {
        // CallGraph is the discovered callgraph.
        // It does not include edges for calls made via reflection.
        CallGraph *callgraph.Graph

        // Reachable contains the set of reachable functions and methods.
        // This includes exported methods of runtime types, since
        // they may be accessed via reflection.
        // The value indicates whether the function is address-taken.
        //
        // (We wrap the bool in a struct to avoid inadvertent use of
        // "if Reachable[f] {" to test for set membership.)
        Reachable map[*ir.Function]struct{ AddrTaken bool }

        // RuntimeTypes contains the set of types that are needed at
        // runtime, for interfaces or reflection.
        //
        // The value indicates whether the type is inaccessible to reflection.
        // Consider:
        //      type A struct{B}
        //      fmt.Println(new(A))
        // Types *A, A and B are accessible to reflection, but the unnamed
        // type struct{B} is not.
        RuntimeTypes typeutil.Map
}

// Working state of the RTA algorithm.
type rta struct {
        result *Result

        prog *ir.Program

        worklist []*ir.Function // list of functions to visit

        // addrTakenFuncsBySig contains all address-taken *Functions, grouped by signature.
        // Keys are *types.Signature, values are map[*ir.Function]bool sets.
        addrTakenFuncsBySig typeutil.Map

        // dynCallSites contains all dynamic "call"-mode call sites, grouped by signature.
        // Keys are *types.Signature, values are unordered []ir.CallInstruction.
        dynCallSites typeutil.Map

        // invokeSites contains all "invoke"-mode call sites, grouped by interface.
        // Keys are *types.Interface (never *types.Named),
        // Values are unordered []ir.CallInstruction sets.
        invokeSites typeutil.Map

        // The following two maps together define the subset of the
        // m:n "implements" relation needed by the algorithm.

        // concreteTypes maps each concrete type to the set of interfaces that it implements.
        // Keys are types.Type, values are unordered []*types.Interface.
        // Only concrete types used as MakeInterface operands are included.
        concreteTypes typeutil.Map

        // interfaceTypes maps each interface type to
        // the set of concrete types that implement it.
        // Keys are *types.Interface, values are unordered []types.Type.
        // Only interfaces used in "invoke"-mode CallInstructions are included.
        interfaceTypes typeutil.Map
}

// addReachable marks a function as potentially callable at run-time,
// and ensures that it gets processed.
func (r *rta) addReachable(f *ir.Function, addrTaken bool) {
        reachable := r.result.Reachable
        n := len(reachable)
        v := reachable[f]
        if addrTaken {
                v.AddrTaken = true
        }
        reachable[f] = v
        if len(reachable) > n {
                // First time seeing f.  Add it to the worklist.
                r.worklist = append(r.worklist, f)
        }
}

// addEdge adds the specified call graph edge, and marks it reachable.
// addrTaken indicates whether to mark the callee as "address-taken".
func (r *rta) addEdge(site ir.CallInstruction, callee *ir.Function, addrTaken bool) {
        r.addReachable(callee, addrTaken)

        if g := r.result.CallGraph; g != nil {
                if site.Parent() == nil {
                        panic(site)
                }
                from := g.CreateNode(site.Parent())
                to := g.CreateNode(callee)
                callgraph.AddEdge(from, site, to)
        }
}

// ---------- addrTakenFuncs × dynCallSites ----------

// visitAddrTakenFunc is called each time we encounter an address-taken function f.
func (r *rta) visitAddrTakenFunc(f *ir.Function) {
        // Create two-level map (Signature -> Function -> bool).
        S := f.Signature
        funcs, _ := r.addrTakenFuncsBySig.At(S).(map[*ir.Function]bool)
        if funcs == nil {
                funcs = make(map[*ir.Function]bool)
                r.addrTakenFuncsBySig.Set(S, funcs)
        }
        if !funcs[f] {
                // First time seeing f.
                funcs[f] = true

                // If we've seen any dyncalls of this type, mark it reachable,
                // and add call graph edges.
                sites, _ := r.dynCallSites.At(S).([]ir.CallInstruction)
                for _, site := range sites {
                        r.addEdge(site, f, true)
                }
        }
}

// visitDynCall is called each time we encounter a dynamic "call"-mode call.
func (r *rta) visitDynCall(site ir.CallInstruction) {
        S := site.Common().Signature()

        // Record the call site.
        sites, _ := r.dynCallSites.At(S).([]ir.CallInstruction)
        r.dynCallSites.Set(S, append(sites, site))

        // For each function of signature S that we know is address-taken,
        // mark it reachable.  We'll add the callgraph edges later.
        funcs, _ := r.addrTakenFuncsBySig.At(S).(map[*ir.Function]bool)
        for g := range funcs {
                r.addEdge(site, g, true)
        }
}

// ---------- concrete types × invoke sites ----------

// addInvokeEdge is called for each new pair (site, C) in the matrix.
func (r *rta) addInvokeEdge(site ir.CallInstruction, C types.Type) {
        // Ascertain the concrete method of C to be called.
        imethod := site.Common().Method
        cmethod := r.prog.MethodValue(r.prog.MethodSets.MethodSet(C).Lookup(imethod.Pkg(), imethod.Name()))
        r.addEdge(site, cmethod, true)
}

// visitInvoke is called each time the algorithm encounters an "invoke"-mode call.
func (r *rta) visitInvoke(site ir.CallInstruction) {
        I := site.Common().Value.Type().Underlying().(*types.Interface)

        // Record the invoke site.
        sites, _ := r.invokeSites.At(I).([]ir.CallInstruction)
        r.invokeSites.Set(I, append(sites, site))

        // Add callgraph edge for each existing
        // address-taken concrete type implementing I.
        for _, C := range r.implementations(I) {
                r.addInvokeEdge(site, C)
        }
}

// ---------- main algorithm ----------

// visitFunc processes function f.
func (r *rta) visitFunc(f *ir.Function) {
        var space [32]*ir.Value // preallocate space for common case

        for _, b := range f.Blocks {
                for _, instr := range b.Instrs {
                        rands := instr.Operands(space[:0])

                        switch instr := instr.(type) {
                        case ir.CallInstruction:
                                call := instr.Common()
                                if call.IsInvoke() {
                                        r.visitInvoke(instr)
                                } else if g := call.StaticCallee(); g != nil {
                                        r.addEdge(instr, g, false)
                                } else if _, ok := call.Value.(*ir.Builtin); !ok {
                                        r.visitDynCall(instr)
                                }

                                // Ignore the call-position operand when
                                // looking for address-taken Functions.
                                // Hack: assume this is rands[0].
                                rands = rands[1:]

                        case *ir.MakeInterface:
                                r.addRuntimeType(instr.X.Type(), false)
                        }

                        // Process all address-taken functions.
                        for _, op := range rands {
                                if g, ok := (*op).(*ir.Function); ok {
                                        r.visitAddrTakenFunc(g)
                                }
                        }
                }
        }
}

// Analyze performs Rapid Type Analysis, starting at the specified root
// functions.  It returns nil if no roots were specified.
//
// If buildCallGraph is true, Result.CallGraph will contain a call
// graph; otherwise, only the other fields (reachable functions) are
// populated.
//
func Analyze(roots []*ir.Function, buildCallGraph bool) *Result {
        if len(roots) == 0 {
                return nil
        }

        r := &rta{
                result: &Result{Reachable: make(map[*ir.Function]struct{ AddrTaken bool })},
                prog:   roots[0].Prog,
        }

        if buildCallGraph {
                // TODO(adonovan): change callgraph API to eliminate the
                // notion of a distinguished root node.  Some callgraphs
                // have many roots, or none.
                r.result.CallGraph = callgraph.New(roots[0])
        }

        hasher := typeutil.MakeHasher()
        r.result.RuntimeTypes.SetHasher(hasher)
        r.addrTakenFuncsBySig.SetHasher(hasher)
        r.dynCallSites.SetHasher(hasher)
        r.invokeSites.SetHasher(hasher)
        r.concreteTypes.SetHasher(hasher)
        r.interfaceTypes.SetHasher(hasher)

        // Visit functions, processing their instructions, and adding
        // new functions to the worklist, until a fixed point is
        // reached.
        var shadow []*ir.Function // for efficiency, we double-buffer the worklist
        r.worklist = append(r.worklist, roots...)
        for len(r.worklist) > 0 {
                shadow, r.worklist = r.worklist, shadow[:0]
                for _, f := range shadow {
                        r.visitFunc(f)
                }
        }
        return r.result
}

// interfaces(C) returns all currently known interfaces implemented by C.
func (r *rta) interfaces(C types.Type) []*types.Interface {
        // Ascertain set of interfaces C implements
        // and update 'implements' relation.
        var ifaces []*types.Interface
        r.interfaceTypes.Iterate(func(I types.Type, concs interface{}) {
                if I := I.(*types.Interface); types.Implements(C, I) {
                        concs, _ := concs.([]types.Type)
                        r.interfaceTypes.Set(I, append(concs, C))
                        ifaces = append(ifaces, I)
                }
        })
        r.concreteTypes.Set(C, ifaces)
        return ifaces
}

// implementations(I) returns all currently known concrete types that implement I.
func (r *rta) implementations(I *types.Interface) []types.Type {
        var concs []types.Type
        if v := r.interfaceTypes.At(I); v != nil {
                concs = v.([]types.Type)
        } else {
                // First time seeing this interface.
                // Update the 'implements' relation.
                r.concreteTypes.Iterate(func(C types.Type, ifaces interface{}) {
                        if types.Implements(C, I) {
                                ifaces, _ := ifaces.([]*types.Interface)
                                r.concreteTypes.Set(C, append(ifaces, I))
                                concs = append(concs, C)
                        }
                })
                r.interfaceTypes.Set(I, concs)
        }
        return concs
}

// addRuntimeType is called for each concrete type that can be the
// dynamic type of some interface or reflect.Value.
// Adapted from needMethods in go/ir/builder.go
//
func (r *rta) addRuntimeType(T types.Type, skip bool) {
        if prev, ok := r.result.RuntimeTypes.At(T).(bool); ok {
                if skip && !prev {
                        r.result.RuntimeTypes.Set(T, skip)
                }
                return
        }
        r.result.RuntimeTypes.Set(T, skip)

        mset := r.prog.MethodSets.MethodSet(T)

        if _, ok := T.Underlying().(*types.Interface); !ok {
                // T is a new concrete type.
                for i, n := 0, mset.Len(); i < n; i++ {
                        sel := mset.At(i)
                        m := sel.Obj()

                        if m.Exported() {
                                // Exported methods are always potentially callable via reflection.
                                r.addReachable(r.prog.MethodValue(sel), true)
                        }
                }

                // Add callgraph edge for each existing dynamic
                // "invoke"-mode call via that interface.
                for _, I := range r.interfaces(T) {
                        sites, _ := r.invokeSites.At(I).([]ir.CallInstruction)
                        for _, site := range sites {
                                r.addInvokeEdge(site, T)
                        }
                }
        }

        // Precondition: T is not a method signature (*Signature with Recv()!=nil).
        // Recursive case: skip => don't call makeMethods(T).
        // Each package maintains its own set of types it has visited.

        var n *types.Named
        switch T := T.(type) {
        case *types.Named:
                n = T
        case *types.Pointer:
                n, _ = T.Elem().(*types.Named)
        }
        if n != nil {
                owner := n.Obj().Pkg()
                if owner == nil {
                        return // built-in error type
                }
        }

        // Recursion over signatures of each exported method.
        for i := 0; i < mset.Len(); i++ {
                if mset.At(i).Obj().Exported() {
                        sig := mset.At(i).Type().(*types.Signature)
                        r.addRuntimeType(sig.Params(), true)  // skip the Tuple itself
                        r.addRuntimeType(sig.Results(), true) // skip the Tuple itself
                }
        }

        switch t := T.(type) {
        case *types.Basic:
                // nop

        case *types.Interface:
                // nop---handled by recursion over method set.

        case *types.Pointer:
                r.addRuntimeType(t.Elem(), false)

        case *types.Slice:
                r.addRuntimeType(t.Elem(), false)

        case *types.Chan:
                r.addRuntimeType(t.Elem(), false)

        case *types.Map:
                r.addRuntimeType(t.Key(), false)
                r.addRuntimeType(t.Elem(), false)

        case *types.Signature:
                if t.Recv() != nil {
                        panic(fmt.Sprintf("Signature %s has Recv %s", t, t.Recv()))
                }
                r.addRuntimeType(t.Params(), true)  // skip the Tuple itself
                r.addRuntimeType(t.Results(), true) // skip the Tuple itself

        case *types.Named:
                // A pointer-to-named type can be derived from a named
                // type via reflection.  It may have methods too.
                r.addRuntimeType(types.NewPointer(T), false)

                // Consider 'type T struct{S}' where S has methods.
                // Reflection provides no way to get from T to struct{S},
                // only to S, so the method set of struct{S} is unwanted,
                // so set 'skip' flag during recursion.
                r.addRuntimeType(t.Underlying(), true)

        case *types.Array:
                r.addRuntimeType(t.Elem(), false)

        case *types.Struct:
                for i, n := 0, t.NumFields(); i < n; i++ {
                        r.addRuntimeType(t.Field(i).Type(), false)
                }

        case *types.Tuple:
                for i, n := 0, t.Len(); i < n; i++ {
                        r.addRuntimeType(t.At(i).Type(), false)
                }

        default:
                panic(T)
        }
}