go/callgraph: gofmt
Gofmt to update doc comments to the new formatting.
(There are so many files in x/tools I am breaking up the
gofmt'ing into multiple CLs.)
For golang/go#51082.
Change-Id: I229b90365998244cfa858ae678382f6089b1cdb9
Reviewed-on: https://go-review.googlesource.com/c/tools/+/399360
Run-TryBot: Russ Cox <rsc@golang.org>
Auto-Submit: Russ Cox <rsc@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
diff --git a/go/callgraph/callgraph.go b/go/callgraph/callgraph.go
index 2bcc3dc..352ce0c 100644
--- a/go/callgraph/callgraph.go
+++ b/go/callgraph/callgraph.go
@@ -3,7 +3,6 @@
// license that can be found in the LICENSE file.
/*
-
Package callgraph defines the call graph and various algorithms
and utilities to operate on it.
@@ -30,7 +29,6 @@
Calls to built-in functions (e.g. panic, println) are not represented
in the call graph; they are treated like built-in operators of the
language.
-
*/
package callgraph // import "golang.org/x/tools/go/callgraph"
@@ -51,7 +49,6 @@
// A graph may contain nodes that are not reachable from the root.
// If the call graph is sound, such nodes indicate unreachable
// functions.
-//
type Graph struct {
Root *Node // the distinguished root node
Nodes map[*ssa.Function]*Node // all nodes by function
diff --git a/go/callgraph/cha/cha.go b/go/callgraph/cha/cha.go
index 215ff17..1700404 100644
--- a/go/callgraph/cha/cha.go
+++ b/go/callgraph/cha/cha.go
@@ -20,7 +20,6 @@
// 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"
import (
@@ -34,7 +33,6 @@
// 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
diff --git a/go/callgraph/cha/cha_test.go b/go/callgraph/cha/cha_test.go
index 3dc0314..8777ce4 100644
--- a/go/callgraph/cha/cha_test.go
+++ b/go/callgraph/cha/cha_test.go
@@ -47,7 +47,6 @@
// TestCHA runs CHA on each file in inputs, prints the dynamic edges of
// the call graph, and compares it with the golden results embedded in
// the WANT comment at the end of the file.
-//
func TestCHA(t *testing.T) {
for _, filename := range inputs {
content, err := ioutil.ReadFile(filename)
diff --git a/go/callgraph/rta/rta.go b/go/callgraph/rta/rta.go
index e6b4460..5dfb441 100644
--- a/go/callgraph/rta/rta.go
+++ b/go/callgraph/rta/rta.go
@@ -39,7 +39,6 @@
// 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 // import "golang.org/x/tools/go/callgraph/rta"
// TODO(adonovan): test it by connecting it to the interpreter and
@@ -57,7 +56,6 @@
// 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.
@@ -262,7 +260,6 @@
// If buildCallGraph is true, Result.CallGraph will contain a call
// graph; otherwise, only the other fields (reachable functions) are
// populated.
-//
func Analyze(roots []*ssa.Function, buildCallGraph bool) *Result {
if len(roots) == 0 {
return nil
@@ -341,7 +338,6 @@
// addRuntimeType is called for each concrete type that can be the
// dynamic type of some interface or reflect.Value.
// Adapted from needMethods in go/ssa/builder.go
-//
func (r *rta) addRuntimeType(T types.Type, skip bool) {
if prev, ok := r.result.RuntimeTypes.At(T).(bool); ok {
if skip && !prev {
diff --git a/go/callgraph/rta/rta_test.go b/go/callgraph/rta/rta_test.go
index 9ae1bdf..89ade37 100644
--- a/go/callgraph/rta/rta_test.go
+++ b/go/callgraph/rta/rta_test.go
@@ -51,7 +51,6 @@
// The results string consists of two parts: the set of dynamic call
// edges, "f --> g", one per line, and the set of reachable functions,
// one per line. Each set is sorted.
-//
func TestRTA(t *testing.T) {
for _, filename := range inputs {
content, err := ioutil.ReadFile(filename)
diff --git a/go/callgraph/static/static.go b/go/callgraph/static/static.go
index 7c41c12..c7fae75 100644
--- a/go/callgraph/static/static.go
+++ b/go/callgraph/static/static.go
@@ -14,7 +14,6 @@
// CallGraph computes the call graph of the specified program
// considering only static calls.
-//
func CallGraph(prog *ssa.Program) *callgraph.Graph {
cg := callgraph.New(nil) // TODO(adonovan) eliminate concept of rooted callgraph
diff --git a/go/callgraph/util.go b/go/callgraph/util.go
index a8f8903..1ab0390 100644
--- a/go/callgraph/util.go
+++ b/go/callgraph/util.go
@@ -11,7 +11,6 @@
// CalleesOf returns a new set containing all direct callees of the
// caller node.
-//
func CalleesOf(caller *Node) map[*Node]bool {
callees := make(map[*Node]bool)
for _, e := range caller.Out {
@@ -24,7 +23,6 @@
// The edge function is called for each edge in postorder. If it
// returns non-nil, visitation stops and GraphVisitEdges returns that
// value.
-//
func GraphVisitEdges(g *Graph, edge func(*Edge) error) error {
seen := make(map[*Node]bool)
var visit func(n *Node) error
@@ -54,7 +52,6 @@
// ending at some node for which isEnd() returns true. On success,
// PathSearch returns the path as an ordered list of edges; on
// failure, it returns nil.
-//
func PathSearch(start *Node, isEnd func(*Node) bool) []*Edge {
stack := make([]*Edge, 0, 32)
seen := make(map[*Node]bool)
@@ -82,7 +79,6 @@
// synthetic functions (except g.Root and package initializers),
// preserving the topology. In effect, calls to synthetic wrappers
// are "inlined".
-//
func (g *Graph) DeleteSyntheticNodes() {
// Measurements on the standard library and go.tools show that
// resulting graph has ~15% fewer nodes and 4-8% fewer edges
diff --git a/go/callgraph/vta/graph.go b/go/callgraph/vta/graph.go
index ad7ef0e..37308f8 100644
--- a/go/callgraph/vta/graph.go
+++ b/go/callgraph/vta/graph.go
@@ -175,9 +175,10 @@
// We merge such constructs into a single node for simplicity and without
// much precision sacrifice as such variables are rare in practice. Both
// a and b would be represented as the same PtrInterface(I) node in:
-// type I interface
-// var a ***I
-// var b **I
+//
+// type I interface
+// var a ***I
+// var b **I
type nestedPtrInterface struct {
typ types.Type
}
@@ -195,8 +196,9 @@
// constructs into a single node for simplicity and without much precision
// sacrifice as such variables are rare in practice. Both a and b would be
// represented as the same PtrFunction(func()) node in:
-// var a *func()
-// var b **func()
+//
+// var a *func()
+// var b **func()
type nestedPtrFunction struct {
typ types.Type
}
@@ -441,7 +443,9 @@
}
// selekt generates flows for select statement
-// a = select blocking/nonblocking [c_1 <- t_1, c_2 <- t_2, ..., <- o_1, <- o_2, ...]
+//
+// a = select blocking/nonblocking [c_1 <- t_1, c_2 <- t_2, ..., <- o_1, <- o_2, ...]
+//
// between receiving channel registers c_i and corresponding input register t_i. Further,
// flows are generated between o_i and a[2 + i]. Note that a is a tuple register of type
// <int, bool, r_1, r_2, ...> where the type of r_i is the element type of channel o_i.
@@ -544,8 +548,9 @@
// panic creates a flow from arguments to panic instructions to return
// registers of all recover statements in the program. Introduces a
// global panic node Panic and
-// 1) for every panic statement p: add p -> Panic
-// 2) for every recover statement r: add Panic -> r (handled in call)
+// 1. for every panic statement p: add p -> Panic
+// 2. for every recover statement r: add Panic -> r (handled in call)
+//
// TODO(zpavlinovic): improve precision by explicitly modeling how panic
// values flow from callees to callers and into deferred recover instructions.
func (b *builder) panic(p *ssa.Panic) {
diff --git a/go/callgraph/vta/helpers_test.go b/go/callgraph/vta/helpers_test.go
index 0e00aeb..c46dd7e 100644
--- a/go/callgraph/vta/helpers_test.go
+++ b/go/callgraph/vta/helpers_test.go
@@ -87,7 +87,9 @@
// callGraphStr stringifes `g` into a list of strings where
// each entry is of the form
-// f: cs1 -> f1, f2, ...; ...; csw -> fx, fy, ...
+//
+// f: cs1 -> f1, f2, ...; ...; csw -> fx, fy, ...
+//
// f is a function, cs1, ..., csw are call sites in f, and
// f1, f2, ..., fx, fy, ... are the resolved callees.
func callGraphStr(g *callgraph.Graph) []string {
diff --git a/go/callgraph/vta/internal/trie/bits.go b/go/callgraph/vta/internal/trie/bits.go
index f2fd0ba..c3aa159 100644
--- a/go/callgraph/vta/internal/trie/bits.go
+++ b/go/callgraph/vta/internal/trie/bits.go
@@ -19,11 +19,11 @@
// bitpos is the position of a bit. A position is represented by having a 1
// bit in that position.
// Examples:
-// * 0b0010 is the position of the `1` bit in 2.
-// It is the 3rd most specific bit position in big endian encoding
-// (0b0 and 0b1 are more specific).
-// * 0b0100 is the position of the bit that 1 and 5 disagree on.
-// * 0b0 is a special value indicating that all bit agree.
+// - 0b0010 is the position of the `1` bit in 2.
+// It is the 3rd most specific bit position in big endian encoding
+// (0b0 and 0b1 are more specific).
+// - 0b0100 is the position of the bit that 1 and 5 disagree on.
+// - 0b0 is a special value indicating that all bit agree.
type bitpos uint64
// prefixes represent a set of keys that all agree with the
@@ -35,7 +35,8 @@
// A prefix always mask(p, m) == p.
//
// A key is its own prefix for the bit position 64,
-// e.g. seeing a `prefix(key)` is not a problem.
+// e.g. seeing a `prefix(key)` is not a problem.
+//
// Prefixes should never be turned into keys.
type prefix uint64
@@ -64,8 +65,9 @@
// In big endian encoding, this value is the [64-(m-1)] most significant bits of k
// followed by a `0` bit at bitpos m, followed m-1 `1` bits.
// Examples:
-// prefix(0b1011) for a bitpos 0b0100 represents the keys:
-// 0b1000, 0b1001, 0b1010, 0b1011, 0b1100, 0b1101, 0b1110, 0b1111
+//
+// prefix(0b1011) for a bitpos 0b0100 represents the keys:
+// 0b1000, 0b1001, 0b1010, 0b1011, 0b1100, 0b1101, 0b1110, 0b1111
//
// This mask function has the property that if matchPrefix(k, p, b), then
// k <= p if and only if zeroBit(k, m). This induces binary search tree tries.
@@ -85,9 +87,10 @@
// can hold that can also be held by a prefix `q` for some bitpos `n`.
//
// This is equivalent to:
-// m ==n && p == q,
-// higher(m, n) && matchPrefix(q, p, m), or
-// higher(n, m) && matchPrefix(p, q, n)
+//
+// m ==n && p == q,
+// higher(m, n) && matchPrefix(q, p, m), or
+// higher(n, m) && matchPrefix(p, q, n)
func prefixesOverlap(p prefix, m bitpos, q prefix, n bitpos) bool {
fbb := n
if ord(m, n) {
diff --git a/go/callgraph/vta/internal/trie/builder.go b/go/callgraph/vta/internal/trie/builder.go
index 25d3805..11ff59b 100644
--- a/go/callgraph/vta/internal/trie/builder.go
+++ b/go/callgraph/vta/internal/trie/builder.go
@@ -9,7 +9,9 @@
// will be stored for the key.
//
// Collision functions must be idempotent:
-// collision(x, x) == x for all x.
+//
+// collision(x, x) == x for all x.
+//
// Collisions functions may be applied whenever a value is inserted
// or two maps are merged, or intersected.
type Collision func(lhs interface{}, rhs interface{}) interface{}
@@ -72,7 +74,8 @@
// in the current scope and handle collisions using the collision function c.
//
// This is roughly corresponds to updating a map[uint64]interface{} by:
-// if _, ok := m[k]; ok { m[k] = c(m[k], v} else { m[k] = v}
+//
+// if _, ok := m[k]; ok { m[k] = c(m[k], v} else { m[k] = v}
//
// An insertion or update happened whenever Insert(m, ...) != m .
func (b *Builder) InsertWith(c Collision, m Map, k uint64, v interface{}) Map {
@@ -85,7 +88,8 @@
//
// If there was a previous value mapped by key, keep the previously mapped value.
// This is roughly corresponds to updating a map[uint64]interface{} by:
-// if _, ok := m[k]; ok { m[k] = val }
+//
+// if _, ok := m[k]; ok { m[k] = val }
//
// This is equivalent to b.Merge(m, b.Create({k: v})).
func (b *Builder) Insert(m Map, k uint64, v interface{}) Map {
@@ -94,7 +98,8 @@
// Updates a (key, value) in the map. This is roughly corresponds to
// updating a map[uint64]interface{} by:
-// m[key] = val
+//
+// m[key] = val
func (b *Builder) Update(m Map, key uint64, val interface{}) Map {
return b.InsertWith(TakeRhs, m, key, val)
}
@@ -148,14 +153,17 @@
// Intersect Maps lhs and rhs and returns a map with all of the keys in
// both lhs and rhs and the value comes from lhs, i.e.
-// {(k, lhs[k]) | k in lhs, k in rhs}.
+//
+// {(k, lhs[k]) | k in lhs, k in rhs}.
func (b *Builder) Intersect(lhs, rhs Map) Map {
return b.IntersectWith(TakeLhs, lhs, rhs)
}
// IntersectWith take lhs and rhs and returns the intersection
// with the value coming from the collision function, i.e.
-// {(k, c(lhs[k], rhs[k]) ) | k in lhs, k in rhs}.
+//
+// {(k, c(lhs[k], rhs[k]) ) | k in lhs, k in rhs}.
+//
// The elements of the resulting map are always { <k, c(lhs[k], rhs[k]) > }
// for each key k that a key in both lhs and rhs.
func (b *Builder) IntersectWith(c Collision, lhs, rhs Map) Map {
@@ -261,7 +269,9 @@
}
// mkBranch returns the hash-consed representative of the tuple
-// (prefix, branch, left, right)
+//
+// (prefix, branch, left, right)
+//
// in the current scope.
func (b *Builder) mkBranch(p prefix, bp bitpos, left node, right node) *branch {
br := &branch{
diff --git a/go/callgraph/vta/internal/trie/trie.go b/go/callgraph/vta/internal/trie/trie.go
index 160eb21..511fde5 100644
--- a/go/callgraph/vta/internal/trie/trie.go
+++ b/go/callgraph/vta/internal/trie/trie.go
@@ -10,8 +10,10 @@
// environment abstract domains in program analysis).
//
// This implementation closely follows the paper:
-// C. Okasaki and A. Gill, “Fast mergeable integer maps,” in ACM SIGPLAN
-// Workshop on ML, September 1998, pp. 77–86.
+//
+// C. Okasaki and A. Gill, “Fast mergeable integer maps,” in ACM SIGPLAN
+// Workshop on ML, September 1998, pp. 77–86.
+//
// Each Map is immutable and can be read from concurrently. The map does not
// guarantee that the value pointed to by the interface{} value is not updated
// concurrently.
@@ -36,9 +38,9 @@
// Maps are immutable and can be read from concurrently.
//
// Notes on concurrency:
-// - A Map value itself is an interface and assignments to a Map value can race.
-// - Map does not guarantee that the value pointed to by the interface{} value
-// is not updated concurrently.
+// - A Map value itself is an interface and assignments to a Map value can race.
+// - Map does not guarantee that the value pointed to by the interface{} value
+// is not updated concurrently.
type Map struct {
s Scope
n node
diff --git a/go/callgraph/vta/propagation_test.go b/go/callgraph/vta/propagation_test.go
index 9670741..00b2127 100644
--- a/go/callgraph/vta/propagation_test.go
+++ b/go/callgraph/vta/propagation_test.go
@@ -123,7 +123,8 @@
// isRevTopSorted checks if sccs of `g` are sorted in reverse
// topological order:
-// for every edge x -> y in g, nodeToScc[x] > nodeToScc[y]
+//
+// for every edge x -> y in g, nodeToScc[x] > nodeToScc[y]
func isRevTopSorted(g vtaGraph, nodeToScc map[node]int) bool {
for n, succs := range g {
for s := range succs {
@@ -148,39 +149,39 @@
// parentheses contain node types and F nodes stand for function
// nodes whose content is function named F:
//
-// no-cycles:
-// t0 (A) -> t1 (B) -> t2 (C)
+// no-cycles:
+// t0 (A) -> t1 (B) -> t2 (C)
//
-// trivial-cycle:
-// <-------- <--------
-// | | | |
-// t0 (A) -> t1 (B) ->
+// trivial-cycle:
+// <-------- <--------
+// | | | |
+// t0 (A) -> t1 (B) ->
//
-// circle-cycle:
-// t0 (A) -> t1 (A) -> t2 (B)
-// | |
-// <--------------------
+// circle-cycle:
+// t0 (A) -> t1 (A) -> t2 (B)
+// | |
+// <--------------------
//
-// fully-connected:
-// t0 (A) <-> t1 (B)
-// \ /
-// t2(C)
+// fully-connected:
+// t0 (A) <-> t1 (B)
+// \ /
+// t2(C)
//
-// subsumed-scc:
-// t0 (A) -> t1 (B) -> t2(B) -> t3 (A)
-// | | | |
-// | <--------- |
-// <-----------------------------
+// subsumed-scc:
+// t0 (A) -> t1 (B) -> t2(B) -> t3 (A)
+// | | | |
+// | <--------- |
+// <-----------------------------
//
-// more-realistic:
-// <--------
-// | |
-// t0 (A) -->
-// ---------->
-// | |
-// t1 (A) -> t2 (B) -> F1 -> F2 -> F3 -> F4
-// | | | |
-// <------- <------------
+// more-realistic:
+// <--------
+// | |
+// t0 (A) -->
+// ---------->
+// | |
+// t1 (A) -> t2 (B) -> F1 -> F2 -> F3 -> F4
+// | | | |
+// <------- <------------
func testSuite() map[string]vtaGraph {
a := newNamedType("A")
b := newNamedType("B")
diff --git a/go/callgraph/vta/utils.go b/go/callgraph/vta/utils.go
index 0049955..0531a22 100644
--- a/go/callgraph/vta/utils.go
+++ b/go/callgraph/vta/utils.go
@@ -32,13 +32,13 @@
// hasInFlow checks if a concrete type can flow to node `n`.
// Returns yes iff the type of `n` satisfies one the following:
-// 1) is an interface
-// 2) is a (nested) pointer to interface (needed for, say,
+// 1. is an interface
+// 2. is a (nested) pointer to interface (needed for, say,
// slice elements of nested pointers to interface type)
-// 3) is a function type (needed for higher-order type flow)
-// 4) is a (nested) pointer to function (needed for, say,
+// 3. is a function type (needed for higher-order type flow)
+// 4. is a (nested) pointer to function (needed for, say,
// slice elements of nested pointers to function type)
-// 5) is a global Recover or Panic node
+// 5. is a global Recover or Panic node
func hasInFlow(n node) bool {
if _, ok := n.(panicArg); ok {
return true
diff --git a/go/callgraph/vta/vta.go b/go/callgraph/vta/vta.go
index 98fabe5..9839bd3 100644
--- a/go/callgraph/vta/vta.go
+++ b/go/callgraph/vta/vta.go
@@ -3,7 +3,7 @@
// license that can be found in the LICENSE file.
// Package vta computes the call graph of a Go program using the Variable
-// Type Analysis (VTA) algorithm originally described in ``Practical Virtual
+// Type Analysis (VTA) algorithm originally described in “Practical Virtual
// Method Call Resolution for Java," Vijay Sundaresan, Laurie Hendren,
// Chrislain Razafimahefa, Raja Vallée-Rai, Patrick Lam, Etienne Gagnon, and
// Charles Godin.
@@ -18,22 +18,23 @@
//
// A type propagation is a directed, labeled graph. A node can represent
// one of the following:
-// - A field of a struct type.
-// - A local (SSA) variable of a method/function.
-// - All pointers to a non-interface type.
-// - The return value of a method.
-// - All elements in an array.
-// - All elements in a slice.
-// - All elements in a map.
-// - All elements in a channel.
-// - A global variable.
+// - A field of a struct type.
+// - A local (SSA) variable of a method/function.
+// - All pointers to a non-interface type.
+// - The return value of a method.
+// - All elements in an array.
+// - All elements in a slice.
+// - All elements in a map.
+// - All elements in a channel.
+// - A global variable.
+//
// In addition, the implementation used in this package introduces
// a few Go specific kinds of nodes:
-// - (De)references of nested pointers to interfaces are modeled
-// as a unique nestedPtrInterface node in the type propagation graph.
-// - Each function literal is represented as a function node whose
-// internal value is the (SSA) representation of the function. This
-// is done to precisely infer flow of higher-order functions.
+// - (De)references of nested pointers to interfaces are modeled
+// as a unique nestedPtrInterface node in the type propagation graph.
+// - Each function literal is represented as a function node whose
+// internal value is the (SSA) representation of the function. This
+// is done to precisely infer flow of higher-order functions.
//
// Edges in the graph represent flow of types (and function literals) through
// the program. That is, the model 1) typing constraints that are induced by
