go/pointer: 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: I5e11f2946001b9b36b7bd3af4d42da9dcea7494f
Reviewed-on: https://go-review.googlesource.com/c/tools/+/399361
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Auto-Submit: Russ Cox <rsc@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
diff --git a/go/pointer/analysis.go b/go/pointer/analysis.go
index 0ee0b05..35ad8ab 100644
--- a/go/pointer/analysis.go
+++ b/go/pointer/analysis.go
@@ -46,7 +46,6 @@
//
// (Note: most variables called 'obj' are not *objects but nodeids
// such that a.nodes[obj].obj != nil.)
-//
type object struct {
// flags is a bitset of the node type (ot*) flags defined above.
flags uint32
@@ -82,7 +81,6 @@
//
// Nodes that are pointed-to locations ("labels") have an enclosing
// object (see analysis.enclosingObject).
-//
type node struct {
// If non-nil, this node is the start of an object
// (addressable memory location).
@@ -215,7 +213,6 @@
//
// Pointer analysis of a transitively closed well-typed program should
// always succeed. An error can occur only due to an internal bug.
-//
func Analyze(config *Config) (result *Result, err error) {
if config.Mains == nil {
return nil, fmt.Errorf("no main/test packages to analyze (check $GOROOT/$GOPATH)")
@@ -361,7 +358,6 @@
// callEdge is called for each edge in the callgraph.
// calleeid is the callee's object node (has otFunction flag).
-//
func (a *analysis) callEdge(caller *cgnode, site *callsite, calleeid nodeid) {
obj := a.nodes[calleeid].obj
if obj.flags&otFunction == 0 {
@@ -394,7 +390,6 @@
// It only dumps the nodes that existed before solving. The order in
// which solver-created nodes are created depends on pre-solver
// optimization, so we can't include them in the cross-check.
-//
func (a *analysis) dumpSolution(filename string, N int) {
f, err := os.Create(filename)
if err != nil {
@@ -422,7 +417,6 @@
// showCounts logs the size of the constraint system. A typical
// optimized distribution is 65% copy, 13% load, 11% addr, 5%
// offsetAddr, 4% store, 2% others.
-//
func (a *analysis) showCounts() {
if a.log != nil {
counts := make(map[reflect.Type]int)
diff --git a/go/pointer/api.go b/go/pointer/api.go
index 2a13a67..9a4cc0a 100644
--- a/go/pointer/api.go
+++ b/go/pointer/api.go
@@ -128,9 +128,10 @@
// before analysis has finished has undefined behavior.
//
// Example:
-// // given v, which represents a function call to 'fn() (int, []*T)', and
-// // 'type T struct { F *int }', the following query will access the field F.
-// c.AddExtendedQuery(v, "x[1][0].F")
+//
+// // given v, which represents a function call to 'fn() (int, []*T)', and
+// // 'type T struct { F *int }', the following query will access the field F.
+// c.AddExtendedQuery(v, "x[1][0].F")
func (c *Config) AddExtendedQuery(v ssa.Value, query string) (*Pointer, error) {
ops, _, err := parseExtendedQuery(v.Type(), query)
if err != nil {
@@ -160,7 +161,6 @@
// A Result contains the results of a pointer analysis.
//
// See Config for how to request the various Result components.
-//
type Result struct {
CallGraph *callgraph.Graph // discovered call graph
Queries map[ssa.Value]Pointer // pts(v) for each v in Config.Queries.
@@ -172,7 +172,6 @@
//
// A Pointer doesn't have a unique type because pointers of distinct
// types may alias the same object.
-//
type Pointer struct {
a *analysis
n nodeid
@@ -223,7 +222,6 @@
// map value is the PointsToSet for pointers of that type.
//
// The result is empty unless CanHaveDynamicTypes(T).
-//
func (s PointsToSet) DynamicTypes() *typeutil.Map {
var tmap typeutil.Map
tmap.SetHasher(s.a.hasher)
diff --git a/go/pointer/callgraph.go b/go/pointer/callgraph.go
index 48e152e..0b7aba5 100644
--- a/go/pointer/callgraph.go
+++ b/go/pointer/callgraph.go
@@ -39,7 +39,6 @@
// it is implicitly context-sensitive.
// callsites never represent calls to built-ins;
// they are handled as intrinsics.
-//
type callsite struct {
targets nodeid // pts(·) contains objects for dynamically called functions
instr ssa.CallInstruction // the call instruction; nil for synthetic/intrinsic
diff --git a/go/pointer/doc.go b/go/pointer/doc.go
index e317cf5..d41346e 100644
--- a/go/pointer/doc.go
+++ b/go/pointer/doc.go
@@ -3,7 +3,6 @@
// license that can be found in the LICENSE file.
/*
-
Package pointer implements Andersen's analysis, an inclusion-based
pointer analysis algorithm first described in (Andersen, 1994).
@@ -22,8 +21,7 @@
information than they need since it may increase the cost of the
analysis significantly.
-
-CLASSIFICATION
+# CLASSIFICATION
Our algorithm is INCLUSION-BASED: the points-to sets for x and y will
be related by pts(y) ⊇ pts(x) if the program contains the statement
@@ -44,7 +42,9 @@
It has a CONTEXT-SENSITIVE HEAP: objects are named by both allocation
site and context, so the objects returned by two distinct calls to f:
- func f() *T { return new(T) }
+
+ func f() *T { return new(T) }
+
are distinguished up to the limits of the calling context.
It is a WHOLE PROGRAM analysis: it requires SSA-form IR for the
@@ -52,16 +52,14 @@
See the (Hind, PASTE'01) survey paper for an explanation of these terms.
-
-SOUNDNESS
+# SOUNDNESS
The analysis is fully sound when invoked on pure Go programs that do not
use reflection or unsafe.Pointer conversions. In other words, if there
is any possible execution of the program in which pointer P may point to
object O, the analysis will report that fact.
-
-REFLECTION
+# REFLECTION
By default, the "reflect" library is ignored by the analysis, as if all
its functions were no-ops, but if the client enables the Reflection flag,
@@ -77,17 +75,18 @@
In particular, addressable reflect.Values are not yet implemented, so
operations such as (reflect.Value).Set have no analytic effect.
-
-UNSAFE POINTER CONVERSIONS
+# UNSAFE POINTER CONVERSIONS
The pointer analysis makes no attempt to understand aliasing between the
operand x and result y of an unsafe.Pointer conversion:
- y = (*T)(unsafe.Pointer(x))
+
+ y = (*T)(unsafe.Pointer(x))
+
It is as if the conversion allocated an entirely new object:
- y = new(T)
+ y = new(T)
-NATIVE CODE
+# NATIVE CODE
The analysis cannot model the aliasing effects of functions written in
languages other than Go, such as runtime intrinsics in C or assembly, or
@@ -100,7 +99,7 @@
------------------------------------------------------------------------
-IMPLEMENTATION
+# IMPLEMENTATION
The remaining documentation is intended for package maintainers and
pointer analysis specialists. Maintainers should have a solid
@@ -118,8 +117,7 @@
but imposes certain restrictions, e.g. potential context sensitivity
is limited since all variants must be created a priori.
-
-TERMINOLOGY
+# TERMINOLOGY
A type is said to be "pointer-like" if it is a reference to an object.
Pointer-like types include pointers and also interfaces, maps, channels,
@@ -134,8 +132,7 @@
in pts(dst). Similarly *dst+offset=src is used for store constraints
and dst=src+offset for offset-address constraints.
-
-NODES
+# NODES
Nodes are the key datastructure of the analysis, and have a dual role:
they represent both constraint variables (equivalence classes of
@@ -166,8 +163,7 @@
edges (load, store, etc) trigger the creation of new simple edges
during the solving phase.
-
-OBJECTS
+# OBJECTS
Conceptually, an "object" is a contiguous sequence of nodes denoting
an addressable location: something that a pointer can point to. The
@@ -175,12 +171,12 @@
about the allocation: its size, context, and ssa.Value.
Objects include:
- - functions and globals;
- - variable allocations in the stack frame or heap;
- - maps, channels and slices created by calls to make();
- - allocations to construct an interface;
- - allocations caused by conversions, e.g. []byte(str).
- - arrays allocated by calls to append();
+ - functions and globals;
+ - variable allocations in the stack frame or heap;
+ - maps, channels and slices created by calls to make();
+ - allocations to construct an interface;
+ - allocations caused by conversions, e.g. []byte(str).
+ - arrays allocated by calls to append();
Many objects have no Go types. For example, the func, map and chan type
kinds in Go are all varieties of pointers, but their respective objects
@@ -198,14 +194,13 @@
so there are no empty arrays. The empty tuple is never address-taken,
so is never an object.)
-
-TAGGED OBJECTS
+# TAGGED OBJECTS
An tagged object has the following layout:
- T -- obj.flags ⊇ {otTagged}
- v
- ...
+ T -- obj.flags ⊇ {otTagged}
+ v
+ ...
The T node's typ field is the dynamic type of the "payload": the value
v which follows, flattened out. The T node's obj has the otTagged
@@ -219,331 +214,345 @@
the value v is not of type T but *T; this is used only for
reflect.Values that represent lvalues. (These are not implemented yet.)
-
-ANALYSIS ABSTRACTION OF EACH TYPE
+# ANALYSIS ABSTRACTION OF EACH TYPE
Variables of the following "scalar" types may be represented by a
single node: basic types, pointers, channels, maps, slices, 'func'
pointers, interfaces.
-Pointers
- Nothing to say here, oddly.
+Pointers:
-Basic types (bool, string, numbers, unsafe.Pointer)
- Currently all fields in the flattening of a type, including
- non-pointer basic types such as int, are represented in objects and
- values. Though non-pointer nodes within values are uninteresting,
- non-pointer nodes in objects may be useful (if address-taken)
- because they permit the analysis to deduce, in this example,
+Nothing to say here, oddly.
- var s struct{ ...; x int; ... }
- p := &s.x
+Basic types (bool, string, numbers, unsafe.Pointer):
- that p points to s.x. If we ignored such object fields, we could only
- say that p points somewhere within s.
+Currently all fields in the flattening of a type, including
+non-pointer basic types such as int, are represented in objects and
+values. Though non-pointer nodes within values are uninteresting,
+non-pointer nodes in objects may be useful (if address-taken)
+because they permit the analysis to deduce, in this example,
- All other basic types are ignored. Expressions of these types have
- zero nodeid, and fields of these types within aggregate other types
- are omitted.
+ var s struct{ ...; x int; ... }
+ p := &s.x
- unsafe.Pointers are not modelled as pointers, so a conversion of an
- unsafe.Pointer to *T is (unsoundly) treated equivalent to new(T).
+that p points to s.x. If we ignored such object fields, we could only
+say that p points somewhere within s.
-Channels
- An expression of type 'chan T' is a kind of pointer that points
- exclusively to channel objects, i.e. objects created by MakeChan (or
- reflection).
+All other basic types are ignored. Expressions of these types have
+zero nodeid, and fields of these types within aggregate other types
+are omitted.
- 'chan T' is treated like *T.
- *ssa.MakeChan is treated as equivalent to new(T).
- *ssa.Send and receive (*ssa.UnOp(ARROW)) and are equivalent to store
- and load.
+unsafe.Pointers are not modelled as pointers, so a conversion of an
+unsafe.Pointer to *T is (unsoundly) treated equivalent to new(T).
-Maps
- An expression of type 'map[K]V' is a kind of pointer that points
- exclusively to map objects, i.e. objects created by MakeMap (or
- reflection).
+Channels:
- map K[V] is treated like *M where M = struct{k K; v V}.
- *ssa.MakeMap is equivalent to new(M).
- *ssa.MapUpdate is equivalent to *y=x where *y and x have type M.
- *ssa.Lookup is equivalent to y=x.v where x has type *M.
+An expression of type 'chan T' is a kind of pointer that points
+exclusively to channel objects, i.e. objects created by MakeChan (or
+reflection).
-Slices
- A slice []T, which dynamically resembles a struct{array *T, len, cap int},
- is treated as if it were just a *T pointer; the len and cap fields are
- ignored.
+'chan T' is treated like *T.
+*ssa.MakeChan is treated as equivalent to new(T).
+*ssa.Send and receive (*ssa.UnOp(ARROW)) and are equivalent to store
- *ssa.MakeSlice is treated like new([1]T): an allocation of a
- singleton array.
- *ssa.Index on a slice is equivalent to a load.
- *ssa.IndexAddr on a slice returns the address of the sole element of the
- slice, i.e. the same address.
- *ssa.Slice is treated as a simple copy.
+ and load.
-Functions
- An expression of type 'func...' is a kind of pointer that points
- exclusively to function objects.
+Maps:
- A function object has the following layout:
+An expression of type 'map[K]V' is a kind of pointer that points
+exclusively to map objects, i.e. objects created by MakeMap (or
+reflection).
- identity -- typ:*types.Signature; obj.flags ⊇ {otFunction}
- params_0 -- (the receiver, if a method)
- ...
- params_n-1
- results_0
- ...
- results_m-1
+map K[V] is treated like *M where M = struct{k K; v V}.
+*ssa.MakeMap is equivalent to new(M).
+*ssa.MapUpdate is equivalent to *y=x where *y and x have type M.
+*ssa.Lookup is equivalent to y=x.v where x has type *M.
- There may be multiple function objects for the same *ssa.Function
- due to context-sensitive treatment of some functions.
+Slices:
- The first node is the function's identity node.
- Associated with every callsite is a special "targets" variable,
- whose pts() contains the identity node of each function to which
- the call may dispatch. Identity words are not otherwise used during
- the analysis, but we construct the call graph from the pts()
- solution for such nodes.
+A slice []T, which dynamically resembles a struct{array *T, len, cap int},
+is treated as if it were just a *T pointer; the len and cap fields are
+ignored.
- The following block of contiguous nodes represents the flattened-out
- types of the parameters ("P-block") and results ("R-block") of the
- function object.
+*ssa.MakeSlice is treated like new([1]T): an allocation of a
- The treatment of free variables of closures (*ssa.FreeVar) is like
- that of global variables; it is not context-sensitive.
- *ssa.MakeClosure instructions create copy edges to Captures.
+ singleton array.
- A Go value of type 'func' (i.e. a pointer to one or more functions)
- is a pointer whose pts() contains function objects. The valueNode()
- for an *ssa.Function returns a singleton for that function.
+*ssa.Index on a slice is equivalent to a load.
+*ssa.IndexAddr on a slice returns the address of the sole element of the
+slice, i.e. the same address.
+*ssa.Slice is treated as a simple copy.
-Interfaces
- An expression of type 'interface{...}' is a kind of pointer that
- points exclusively to tagged objects. All tagged objects pointed to
- by an interface are direct (the otIndirect flag is clear) and
- concrete (the tag type T is not itself an interface type). The
- associated ssa.Value for an interface's tagged objects may be an
- *ssa.MakeInterface instruction, or nil if the tagged object was
- created by an instrinsic (e.g. reflection).
+Functions:
- Constructing an interface value causes generation of constraints for
- all of the concrete type's methods; we can't tell a priori which
- ones may be called.
+An expression of type 'func...' is a kind of pointer that points
+exclusively to function objects.
- TypeAssert y = x.(T) is implemented by a dynamic constraint
- triggered by each tagged object O added to pts(x): a typeFilter
- constraint if T is an interface type, or an untag constraint if T is
- a concrete type. A typeFilter tests whether O.typ implements T; if
- so, O is added to pts(y). An untagFilter tests whether O.typ is
- assignable to T,and if so, a copy edge O.v -> y is added.
+A function object has the following layout:
- ChangeInterface is a simple copy because the representation of
- tagged objects is independent of the interface type (in contrast
- to the "method tables" approach used by the gc runtime).
+ identity -- typ:*types.Signature; obj.flags ⊇ {otFunction}
+ params_0 -- (the receiver, if a method)
+ ...
+ params_n-1
+ results_0
+ ...
+ results_m-1
- y := Invoke x.m(...) is implemented by allocating contiguous P/R
- blocks for the callsite and adding a dynamic rule triggered by each
- tagged object added to pts(x). The rule adds param/results copy
- edges to/from each discovered concrete method.
+There may be multiple function objects for the same *ssa.Function
+due to context-sensitive treatment of some functions.
- (Q. Why do we model an interface as a pointer to a pair of type and
- value, rather than as a pair of a pointer to type and a pointer to
- value?
- A. Control-flow joins would merge interfaces ({T1}, {V1}) and ({T2},
- {V2}) to make ({T1,T2}, {V1,V2}), leading to the infeasible and
- type-unsafe combination (T1,V2). Treating the value and its concrete
- type as inseparable makes the analysis type-safe.)
+The first node is the function's identity node.
+Associated with every callsite is a special "targets" variable,
+whose pts() contains the identity node of each function to which
+the call may dispatch. Identity words are not otherwise used during
+the analysis, but we construct the call graph from the pts()
+solution for such nodes.
-reflect.Value
- A reflect.Value is modelled very similar to an interface{}, i.e. as
- a pointer exclusively to tagged objects, but with two generalizations.
+The following block of contiguous nodes represents the flattened-out
+types of the parameters ("P-block") and results ("R-block") of the
+function object.
- 1) a reflect.Value that represents an lvalue points to an indirect
- (obj.flags ⊇ {otIndirect}) tagged object, which has a similar
- layout to an tagged object except that the value is a pointer to
- the dynamic type. Indirect tagged objects preserve the correct
- aliasing so that mutations made by (reflect.Value).Set can be
- observed.
+The treatment of free variables of closures (*ssa.FreeVar) is like
+that of global variables; it is not context-sensitive.
+*ssa.MakeClosure instructions create copy edges to Captures.
- Indirect objects only arise when an lvalue is derived from an
- rvalue by indirection, e.g. the following code:
+A Go value of type 'func' (i.e. a pointer to one or more functions)
+is a pointer whose pts() contains function objects. The valueNode()
+for an *ssa.Function returns a singleton for that function.
- type S struct { X T }
- var s S
- var i interface{} = &s // i points to a *S-tagged object (from MakeInterface)
- v1 := reflect.ValueOf(i) // v1 points to same *S-tagged object as i
- v2 := v1.Elem() // v2 points to an indirect S-tagged object, pointing to s
- v3 := v2.FieldByName("X") // v3 points to an indirect int-tagged object, pointing to s.X
- v3.Set(y) // pts(s.X) ⊇ pts(y)
+Interfaces:
- Whether indirect or not, the concrete type of the tagged object
- corresponds to the user-visible dynamic type, and the existence
- of a pointer is an implementation detail.
+An expression of type 'interface{...}' is a kind of pointer that
+points exclusively to tagged objects. All tagged objects pointed to
+by an interface are direct (the otIndirect flag is clear) and
+concrete (the tag type T is not itself an interface type). The
+associated ssa.Value for an interface's tagged objects may be an
+*ssa.MakeInterface instruction, or nil if the tagged object was
+created by an instrinsic (e.g. reflection).
- (NB: indirect tagged objects are not yet implemented)
+Constructing an interface value causes generation of constraints for
+all of the concrete type's methods; we can't tell a priori which
+ones may be called.
- 2) The dynamic type tag of a tagged object pointed to by a
- reflect.Value may be an interface type; it need not be concrete.
+TypeAssert y = x.(T) is implemented by a dynamic constraint
+triggered by each tagged object O added to pts(x): a typeFilter
+constraint if T is an interface type, or an untag constraint if T is
+a concrete type. A typeFilter tests whether O.typ implements T; if
+so, O is added to pts(y). An untagFilter tests whether O.typ is
+assignable to T,and if so, a copy edge O.v -> y is added.
- This arises in code such as this:
- tEface := reflect.TypeOf(new(interface{}).Elem() // interface{}
- eface := reflect.Zero(tEface)
- pts(eface) is a singleton containing an interface{}-tagged
- object. That tagged object's payload is an interface{} value,
- i.e. the pts of the payload contains only concrete-tagged
- objects, although in this example it's the zero interface{} value,
- so its pts is empty.
+ChangeInterface is a simple copy because the representation of
+tagged objects is independent of the interface type (in contrast
+to the "method tables" approach used by the gc runtime).
-reflect.Type
- Just as in the real "reflect" library, we represent a reflect.Type
- as an interface whose sole implementation is the concrete type,
- *reflect.rtype. (This choice is forced on us by go/types: clients
- cannot fabricate types with arbitrary method sets.)
+y := Invoke x.m(...) is implemented by allocating contiguous P/R
+blocks for the callsite and adding a dynamic rule triggered by each
+tagged object added to pts(x). The rule adds param/results copy
+edges to/from each discovered concrete method.
- rtype instances are canonical: there is at most one per dynamic
- type. (rtypes are in fact large structs but since identity is all
- that matters, we represent them by a single node.)
+(Q. Why do we model an interface as a pointer to a pair of type and
+value, rather than as a pair of a pointer to type and a pointer to
+value?
+A. Control-flow joins would merge interfaces ({T1}, {V1}) and ({T2},
+{V2}) to make ({T1,T2}, {V1,V2}), leading to the infeasible and
+type-unsafe combination (T1,V2). Treating the value and its concrete
+type as inseparable makes the analysis type-safe.)
- The payload of each *rtype-tagged object is an *rtype pointer that
- points to exactly one such canonical rtype object. We exploit this
- by setting the node.typ of the payload to the dynamic type, not
- '*rtype'. This saves us an indirection in each resolution rule. As
- an optimisation, *rtype-tagged objects are canonicalized too.
+reflect.Value:
+A reflect.Value is modelled very similar to an interface{}, i.e. as
+a pointer exclusively to tagged objects, but with two generalizations.
+
+1. a reflect.Value that represents an lvalue points to an indirect
+(obj.flags ⊇ {otIndirect}) tagged object, which has a similar
+layout to an tagged object except that the value is a pointer to
+the dynamic type. Indirect tagged objects preserve the correct
+aliasing so that mutations made by (reflect.Value).Set can be
+observed.
+
+Indirect objects only arise when an lvalue is derived from an
+rvalue by indirection, e.g. the following code:
+
+ type S struct { X T }
+ var s S
+ var i interface{} = &s // i points to a *S-tagged object (from MakeInterface)
+ v1 := reflect.ValueOf(i) // v1 points to same *S-tagged object as i
+ v2 := v1.Elem() // v2 points to an indirect S-tagged object, pointing to s
+ v3 := v2.FieldByName("X") // v3 points to an indirect int-tagged object, pointing to s.X
+ v3.Set(y) // pts(s.X) ⊇ pts(y)
+
+Whether indirect or not, the concrete type of the tagged object
+corresponds to the user-visible dynamic type, and the existence
+of a pointer is an implementation detail.
+
+(NB: indirect tagged objects are not yet implemented)
+
+2. The dynamic type tag of a tagged object pointed to by a
+reflect.Value may be an interface type; it need not be concrete.
+
+This arises in code such as this:
+
+ tEface := reflect.TypeOf(new(interface{}).Elem() // interface{}
+ eface := reflect.Zero(tEface)
+
+pts(eface) is a singleton containing an interface{}-tagged
+object. That tagged object's payload is an interface{} value,
+i.e. the pts of the payload contains only concrete-tagged
+objects, although in this example it's the zero interface{} value,
+so its pts is empty.
+
+reflect.Type:
+
+Just as in the real "reflect" library, we represent a reflect.Type
+as an interface whose sole implementation is the concrete type,
+*reflect.rtype. (This choice is forced on us by go/types: clients
+cannot fabricate types with arbitrary method sets.)
+
+rtype instances are canonical: there is at most one per dynamic
+type. (rtypes are in fact large structs but since identity is all
+that matters, we represent them by a single node.)
+
+The payload of each *rtype-tagged object is an *rtype pointer that
+points to exactly one such canonical rtype object. We exploit this
+by setting the node.typ of the payload to the dynamic type, not
+'*rtype'. This saves us an indirection in each resolution rule. As
+an optimisation, *rtype-tagged objects are canonicalized too.
Aggregate types:
Aggregate types are treated as if all directly contained
aggregates are recursively flattened out.
-Structs
- *ssa.Field y = x.f creates a simple edge to y from x's node at f's offset.
+Structs:
- *ssa.FieldAddr y = &x->f requires a dynamic closure rule to create
- simple edges for each struct discovered in pts(x).
+*ssa.Field y = x.f creates a simple edge to y from x's node at f's offset.
- The nodes of a struct consist of a special 'identity' node (whose
- type is that of the struct itself), followed by the nodes for all
- the struct's fields, recursively flattened out. A pointer to the
- struct is a pointer to its identity node. That node allows us to
- distinguish a pointer to a struct from a pointer to its first field.
+*ssa.FieldAddr y = &x->f requires a dynamic closure rule to create
- Field offsets are logical field offsets (plus one for the identity
- node), so the sizes of the fields can be ignored by the analysis.
+ simple edges for each struct discovered in pts(x).
- (The identity node is non-traditional but enables the distinction
- described above, which is valuable for code comprehension tools.
- Typical pointer analyses for C, whose purpose is compiler
- optimization, must soundly model unsafe.Pointer (void*) conversions,
- and this requires fidelity to the actual memory layout using physical
- field offsets.)
+The nodes of a struct consist of a special 'identity' node (whose
+type is that of the struct itself), followed by the nodes for all
+the struct's fields, recursively flattened out. A pointer to the
+struct is a pointer to its identity node. That node allows us to
+distinguish a pointer to a struct from a pointer to its first field.
- *ssa.Field y = x.f creates a simple edge to y from x's node at f's offset.
+Field offsets are logical field offsets (plus one for the identity
+node), so the sizes of the fields can be ignored by the analysis.
- *ssa.FieldAddr y = &x->f requires a dynamic closure rule to create
- simple edges for each struct discovered in pts(x).
+(The identity node is non-traditional but enables the distinction
+described above, which is valuable for code comprehension tools.
+Typical pointer analyses for C, whose purpose is compiler
+optimization, must soundly model unsafe.Pointer (void*) conversions,
+and this requires fidelity to the actual memory layout using physical
+field offsets.)
-Arrays
- We model an array by an identity node (whose type is that of the
- array itself) followed by a node representing all the elements of
- the array; the analysis does not distinguish elements with different
- indices. Effectively, an array is treated like struct{elem T}, a
- load y=x[i] like y=x.elem, and a store x[i]=y like x.elem=y; the
- index i is ignored.
+*ssa.Field y = x.f creates a simple edge to y from x's node at f's offset.
- A pointer to an array is pointer to its identity node. (A slice is
- also a pointer to an array's identity node.) The identity node
- allows us to distinguish a pointer to an array from a pointer to one
- of its elements, but it is rather costly because it introduces more
- offset constraints into the system. Furthermore, sound treatment of
- unsafe.Pointer would require us to dispense with this node.
+*ssa.FieldAddr y = &x->f requires a dynamic closure rule to create
- Arrays may be allocated by Alloc, by make([]T), by calls to append,
- and via reflection.
+ simple edges for each struct discovered in pts(x).
-Tuples (T, ...)
- Tuples are treated like structs with naturally numbered fields.
- *ssa.Extract is analogous to *ssa.Field.
+Arrays:
- However, tuples have no identity field since by construction, they
- cannot be address-taken.
+We model an array by an identity node (whose type is that of the
+array itself) followed by a node representing all the elements of
+the array; the analysis does not distinguish elements with different
+indices. Effectively, an array is treated like struct{elem T}, a
+load y=x[i] like y=x.elem, and a store x[i]=y like x.elem=y; the
+index i is ignored.
+A pointer to an array is pointer to its identity node. (A slice is
+also a pointer to an array's identity node.) The identity node
+allows us to distinguish a pointer to an array from a pointer to one
+of its elements, but it is rather costly because it introduces more
+offset constraints into the system. Furthermore, sound treatment of
+unsafe.Pointer would require us to dispense with this node.
-FUNCTION CALLS
+Arrays may be allocated by Alloc, by make([]T), by calls to append,
+and via reflection.
- There are three kinds of function call:
- (1) static "call"-mode calls of functions.
- (2) dynamic "call"-mode calls of functions.
- (3) dynamic "invoke"-mode calls of interface methods.
- Cases 1 and 2 apply equally to methods and standalone functions.
+Tuples (T, ...):
- Static calls.
- A static call consists three steps:
- - finding the function object of the callee;
- - creating copy edges from the actual parameter value nodes to the
- P-block in the function object (this includes the receiver if
- the callee is a method);
- - creating copy edges from the R-block in the function object to
- the value nodes for the result of the call.
+Tuples are treated like structs with naturally numbered fields.
+*ssa.Extract is analogous to *ssa.Field.
- A static function call is little more than two struct value copies
- between the P/R blocks of caller and callee:
+However, tuples have no identity field since by construction, they
+cannot be address-taken.
- callee.P = caller.P
- caller.R = callee.R
+# FUNCTION CALLS
- Context sensitivity
+There are three kinds of function call:
+ 1. static "call"-mode calls of functions.
+ 2. dynamic "call"-mode calls of functions.
+ 3. dynamic "invoke"-mode calls of interface methods.
- Static calls (alone) may be treated context sensitively,
- i.e. each callsite may cause a distinct re-analysis of the
- callee, improving precision. Our current context-sensitivity
- policy treats all intrinsics and getter/setter methods in this
- manner since such functions are small and seem like an obvious
- source of spurious confluences, though this has not yet been
- evaluated.
+Cases 1 and 2 apply equally to methods and standalone functions.
- Dynamic function calls
+Static calls:
- Dynamic calls work in a similar manner except that the creation of
- copy edges occurs dynamically, in a similar fashion to a pair of
- struct copies in which the callee is indirect:
+A static call consists three steps:
+ - finding the function object of the callee;
+ - creating copy edges from the actual parameter value nodes to the
+ P-block in the function object (this includes the receiver if
+ the callee is a method);
+ - creating copy edges from the R-block in the function object to
+ the value nodes for the result of the call.
- callee->P = caller.P
- caller.R = callee->R
+A static function call is little more than two struct value copies
+between the P/R blocks of caller and callee:
- (Recall that the function object's P- and R-blocks are contiguous.)
+ callee.P = caller.P
+ caller.R = callee.R
- Interface method invocation
+Context sensitivity: Static calls (alone) may be treated context sensitively,
+i.e. each callsite may cause a distinct re-analysis of the
+callee, improving precision. Our current context-sensitivity
+policy treats all intrinsics and getter/setter methods in this
+manner since such functions are small and seem like an obvious
+source of spurious confluences, though this has not yet been
+evaluated.
- For invoke-mode calls, we create a params/results block for the
- callsite and attach a dynamic closure rule to the interface. For
- each new tagged object that flows to the interface, we look up
- the concrete method, find its function object, and connect its P/R
- blocks to the callsite's P/R blocks, adding copy edges to the graph
- during solving.
+Dynamic function calls:
- Recording call targets
+Dynamic calls work in a similar manner except that the creation of
+copy edges occurs dynamically, in a similar fashion to a pair of
+struct copies in which the callee is indirect:
- The analysis notifies its clients of each callsite it encounters,
- passing a CallSite interface. Among other things, the CallSite
- contains a synthetic constraint variable ("targets") whose
- points-to solution includes the set of all function objects to
- which the call may dispatch.
+ callee->P = caller.P
+ caller.R = callee->R
- It is via this mechanism that the callgraph is made available.
- Clients may also elect to be notified of callgraph edges directly;
- internally this just iterates all "targets" variables' pts(·)s.
+(Recall that the function object's P- and R-blocks are contiguous.)
+Interface method invocation:
-PRESOLVER
+For invoke-mode calls, we create a params/results block for the
+callsite and attach a dynamic closure rule to the interface. For
+each new tagged object that flows to the interface, we look up
+the concrete method, find its function object, and connect its P/R
+blocks to the callsite's P/R blocks, adding copy edges to the graph
+during solving.
+
+Recording call targets:
+
+The analysis notifies its clients of each callsite it encounters,
+passing a CallSite interface. Among other things, the CallSite
+contains a synthetic constraint variable ("targets") whose
+points-to solution includes the set of all function objects to
+which the call may dispatch.
+
+It is via this mechanism that the callgraph is made available.
+Clients may also elect to be notified of callgraph edges directly;
+internally this just iterates all "targets" variables' pts(·)s.
+
+# PRESOLVER
We implement Hash-Value Numbering (HVN), a pre-solver constraint
optimization described in Hardekopf & Lin, SAS'07. This is documented
in more detail in hvn.go. We intend to add its cousins HR and HU in
future.
-
-SOLVER
+# SOLVER
The solver is currently a naive Andersen-style implementation; it does
not perform online cycle detection, though we plan to add solver
@@ -565,8 +574,7 @@
Partly thanks to avoiding map iteration, the execution of the solver is
100% deterministic, a great help during debugging.
-
-FURTHER READING
+# FURTHER READING
Andersen, L. O. 1994. Program analysis and specialization for the C
programming language. Ph.D. dissertation. DIKU, University of
@@ -605,6 +613,5 @@
conference on Programming language design and implementation (PLDI '00).
ACM, New York, NY, USA, 47-56. DOI=10.1145/349299.349310
http://doi.acm.org/10.1145/349299.349310
-
*/
package pointer // import "golang.org/x/tools/go/pointer"
diff --git a/go/pointer/example_test.go b/go/pointer/example_test.go
index 673de7a..6e02092 100644
--- a/go/pointer/example_test.go
+++ b/go/pointer/example_test.go
@@ -19,7 +19,6 @@
// obtain a conservative call-graph of a Go program.
// It also shows how to compute the points-to set of a variable,
// in this case, (C).f's ch parameter.
-//
func Example() {
const myprog = `
package main
diff --git a/go/pointer/gen.go b/go/pointer/gen.go
index ef5108a..0970594 100644
--- a/go/pointer/gen.go
+++ b/go/pointer/gen.go
@@ -37,7 +37,6 @@
// analytically uninteresting.
//
// comment explains the origin of the nodes, as a debugging aid.
-//
func (a *analysis) addNodes(typ types.Type, comment string) nodeid {
id := a.nextNode()
for _, fi := range a.flatten(typ) {
@@ -56,7 +55,6 @@
//
// comment explains the origin of the nodes, as a debugging aid.
// subelement indicates the subelement, e.g. ".a.b[*].c".
-//
func (a *analysis) addOneNode(typ types.Type, comment string, subelement *fieldInfo) nodeid {
id := a.nextNode()
a.nodes = append(a.nodes, &node{typ: typ, subelement: subelement, solve: new(solverState)})
@@ -69,7 +67,6 @@
// setValueNode associates node id with the value v.
// cgn identifies the context iff v is a local variable.
-//
func (a *analysis) setValueNode(v ssa.Value, id nodeid, cgn *cgnode) {
if cgn != nil {
a.localval[v] = id
@@ -125,7 +122,6 @@
//
// obj is the start node of the object, from a prior call to nextNode.
// Its size, flags and optional data will be updated.
-//
func (a *analysis) endObject(obj nodeid, cgn *cgnode, data interface{}) *object {
// Ensure object is non-empty by padding;
// the pad will be the object node.
@@ -150,7 +146,6 @@
//
// For a context-sensitive contour, callersite identifies the sole
// callsite; for shared contours, caller is nil.
-//
func (a *analysis) makeFunctionObject(fn *ssa.Function, callersite *callsite) nodeid {
if a.log != nil {
fmt.Fprintf(a.log, "\t---- makeFunctionObject %s\n", fn)
@@ -190,7 +185,6 @@
// payload points to the sole rtype object for T.
//
// TODO(adonovan): move to reflect.go; it's part of the solver really.
-//
func (a *analysis) makeRtype(T types.Type) nodeid {
if v := a.rtypes.At(T); v != nil {
return v.(nodeid)
@@ -222,7 +216,6 @@
// valueNode returns the id of the value node for v, creating it (and
// the association) as needed. It may return zero for uninteresting
// values containing no pointers.
-//
func (a *analysis) valueNode(v ssa.Value) nodeid {
// Value nodes for locals are created en masse by genFunc.
if id, ok := a.localval[v]; ok {
@@ -247,7 +240,6 @@
// valueOffsetNode ascertains the node for tuple/struct value v,
// then returns the node for its subfield #index.
-//
func (a *analysis) valueOffsetNode(v ssa.Value, index int) nodeid {
id := a.valueNode(v)
if id == 0 {
@@ -264,7 +256,6 @@
// taggedValue returns the dynamic type tag, the (first node of the)
// payload, and the indirect flag of the tagged object starting at id.
// Panic ensues if !isTaggedObject(id).
-//
func (a *analysis) taggedValue(obj nodeid) (tDyn types.Type, v nodeid, indirect bool) {
n := a.nodes[obj]
flags := n.obj.flags
@@ -276,7 +267,6 @@
// funcParams returns the first node of the params (P) block of the
// function whose object node (obj.flags&otFunction) is id.
-//
func (a *analysis) funcParams(id nodeid) nodeid {
n := a.nodes[id]
if n.obj == nil || n.obj.flags&otFunction == 0 {
@@ -287,7 +277,6 @@
// funcResults returns the first node of the results (R) block of the
// function whose object node (obj.flags&otFunction) is id.
-//
func (a *analysis) funcResults(id nodeid) nodeid {
n := a.nodes[id]
if n.obj == nil || n.obj.flags&otFunction == 0 {
@@ -305,7 +294,6 @@
// copy creates a constraint of the form dst = src.
// sizeof is the width (in logical fields) of the copied type.
-//
func (a *analysis) copy(dst, src nodeid, sizeof uint32) {
if src == dst || sizeof == 0 {
return // trivial
@@ -337,7 +325,6 @@
// load creates a load constraint of the form dst = src[offset].
// offset is the pointer offset in logical fields.
// sizeof is the width (in logical fields) of the loaded type.
-//
func (a *analysis) load(dst, src nodeid, offset, sizeof uint32) {
if dst == 0 {
return // load of non-pointerlike value
@@ -358,7 +345,6 @@
// store creates a store constraint of the form dst[offset] = src.
// offset is the pointer offset in logical fields.
// sizeof is the width (in logical fields) of the stored type.
-//
func (a *analysis) store(dst, src nodeid, offset uint32, sizeof uint32) {
if src == 0 {
return // store of non-pointerlike value
@@ -379,7 +365,6 @@
// offsetAddr creates an offsetAddr constraint of the form dst = &src.#offset.
// offset is the field offset in logical fields.
// T is the type of the address.
-//
func (a *analysis) offsetAddr(T types.Type, dst, src nodeid, offset uint32) {
if !a.shouldTrack(T) {
return
@@ -398,7 +383,6 @@
// typeAssert creates a typeFilter or untag constraint of the form dst = src.(T):
// typeFilter for an interface, untag for a concrete type.
// The exact flag is specified as for untagConstraint.
-//
func (a *analysis) typeAssert(T types.Type, dst, src nodeid, exact bool) {
if isInterface(T) {
a.addConstraint(&typeFilterConstraint{T, dst, src})
@@ -417,7 +401,6 @@
// copyElems generates load/store constraints for *dst = *src,
// where src and dst are slices or *arrays.
-//
func (a *analysis) copyElems(cgn *cgnode, typ types.Type, dst, src ssa.Value) {
tmp := a.addNodes(typ, "copy")
sz := a.sizeof(typ)
@@ -553,7 +536,6 @@
// choose a policy. The current policy, rather arbitrarily, is true
// for intrinsics and accessor methods (actually: short, single-block,
// call-free functions). This is just a starting point.
-//
func (a *analysis) shouldUseContext(fn *ssa.Function) bool {
if a.findIntrinsic(fn) != nil {
return true // treat intrinsics context-sensitively
@@ -705,11 +687,13 @@
// practice it occurs rarely, so we special case for reflect.Type.)
//
// In effect we treat this:
-// var rt reflect.Type = ...
-// rt.F()
-// as this:
-// rt.(*reflect.rtype).F()
//
+// var rt reflect.Type = ...
+// rt.F()
+//
+// as this:
+//
+// rt.(*reflect.rtype).F()
func (a *analysis) genInvokeReflectType(caller *cgnode, site *callsite, call *ssa.CallCommon, result nodeid) {
// Unpack receiver into rtype
rtype := a.addOneNode(a.reflectRtypePtr, "rtype.recv", nil)
@@ -789,13 +773,15 @@
// a simple copy constraint when the sole destination is known a priori.
//
// Some SSA instructions always have singletons points-to sets:
-// Alloc, Function, Global, MakeChan, MakeClosure, MakeInterface, MakeMap, MakeSlice.
+//
+// Alloc, Function, Global, MakeChan, MakeClosure, MakeInterface, MakeMap, MakeSlice.
+//
// Others may be singletons depending on their operands:
-// FreeVar, Const, Convert, FieldAddr, IndexAddr, Slice, SliceToArrayPointer.
+//
+// FreeVar, Const, Convert, FieldAddr, IndexAddr, Slice, SliceToArrayPointer.
//
// Idempotent. Objects are created as needed, possibly via recursion
// down the SSA value graph, e.g IndexAddr(FieldAddr(Alloc))).
-//
func (a *analysis) objectNode(cgn *cgnode, v ssa.Value) nodeid {
switch v.(type) {
case *ssa.Global, *ssa.Function, *ssa.Const, *ssa.FreeVar:
@@ -1156,7 +1142,6 @@
// genRootCalls generates the synthetic root of the callgraph and the
// initial calls from it to the analysis scope, such as main, a test
// or a library.
-//
func (a *analysis) genRootCalls() *cgnode {
r := a.prog.NewFunction("<root>", new(types.Signature), "root of callgraph")
root := a.makeCGNode(r, 0, nil)
diff --git a/go/pointer/hvn.go b/go/pointer/hvn.go
index 52fd479..ad25cdf 100644
--- a/go/pointer/hvn.go
+++ b/go/pointer/hvn.go
@@ -174,14 +174,14 @@
// peLabel have identical points-to solutions.
//
// The numbers are allocated consecutively like so:
-// 0 not a pointer
+//
+// 0 not a pointer
// 1..N-1 addrConstraints (equals the constraint's .src field, hence sparse)
// ... offsetAddr constraints
// ... SCCs (with indirect nodes or multiple inputs)
//
// Each PE label denotes a set of pointers containing a single addr, a
// single offsetAddr, or some set of other PE labels.
-//
type peLabel int
type hvn struct {
@@ -212,7 +212,6 @@
// the source, i.e. against the flow of values: they are dependencies.
// Implicit edges are used for SCC computation, but not for gathering
// incoming labels.
-//
type onode struct {
rep onodeid // index of representative of SCC in offline constraint graph
@@ -244,7 +243,6 @@
// hvn computes pointer-equivalence labels (peLabels) using the Hash-based
// Value Numbering (HVN) algorithm described in Hardekopf & Lin, SAS'07.
-//
func (a *analysis) hvn() {
start("HVN")
@@ -455,28 +453,27 @@
// markIndirectNodes marks as indirect nodes whose points-to relations
// are not entirely captured by the offline graph, including:
//
-// (a) All address-taken nodes (including the following nodes within
-// the same object). This is described in the paper.
+// (a) All address-taken nodes (including the following nodes within
+// the same object). This is described in the paper.
//
// The most subtle cause of indirect nodes is the generation of
// store-with-offset constraints since the offline graph doesn't
// represent them. A global audit of constraint generation reveals the
// following uses of store-with-offset:
//
-// (b) genDynamicCall, for P-blocks of dynamically called functions,
-// to which dynamic copy edges will be added to them during
-// solving: from storeConstraint for standalone functions,
-// and from invokeConstraint for methods.
-// All such P-blocks must be marked indirect.
-// (c) MakeUpdate, to update the value part of a map object.
-// All MakeMap objects's value parts must be marked indirect.
-// (d) copyElems, to update the destination array.
-// All array elements must be marked indirect.
+// (b) genDynamicCall, for P-blocks of dynamically called functions,
+// to which dynamic copy edges will be added to them during
+// solving: from storeConstraint for standalone functions,
+// and from invokeConstraint for methods.
+// All such P-blocks must be marked indirect.
+// (c) MakeUpdate, to update the value part of a map object.
+// All MakeMap objects's value parts must be marked indirect.
+// (d) copyElems, to update the destination array.
+// All array elements must be marked indirect.
//
// Not all indirect marking happens here. ref() nodes are marked
// indirect at construction, and each constraint's presolve() method may
// mark additional nodes.
-//
func (h *hvn) markIndirectNodes() {
// (a) all address-taken nodes, plus all nodes following them
// within the same object, since these may be indirectly
@@ -761,7 +758,6 @@
// labels assigned by the hvn, and uses it to simplify the main
// constraint graph, eliminating non-pointer nodes and duplicate
// constraints.
-//
func (h *hvn) simplify() {
// canon maps each peLabel to its canonical main node.
canon := make([]nodeid, h.label)
diff --git a/go/pointer/intrinsics.go b/go/pointer/intrinsics.go
index b7e2b14..43bb8e8 100644
--- a/go/pointer/intrinsics.go
+++ b/go/pointer/intrinsics.go
@@ -159,7 +159,6 @@
// findIntrinsic returns the constraint generation function for an
// intrinsic function fn, or nil if the function should be handled normally.
-//
func (a *analysis) findIntrinsic(fn *ssa.Function) intrinsic {
// Consult the *Function-keyed cache.
// A cached nil indicates a normal non-intrinsic function.
@@ -220,7 +219,6 @@
//
// We sometimes violate condition #3 if the function creates only
// non-function labels, as the control-flow graph is still sound.
-//
func ext۰NoEffect(a *analysis, cgn *cgnode) {}
func ext۰NotYetImplemented(a *analysis, cgn *cgnode) {
diff --git a/go/pointer/labels.go b/go/pointer/labels.go
index 7d64ef6..5a1e199 100644
--- a/go/pointer/labels.go
+++ b/go/pointer/labels.go
@@ -17,15 +17,15 @@
// channel, 'func', slice or interface.
//
// Labels include:
-// - functions
-// - globals
-// - tagged objects, representing interfaces and reflect.Values
-// - arrays created by conversions (e.g. []byte("foo"), []byte(s))
-// - stack- and heap-allocated variables (including composite literals)
-// - channels, maps and arrays created by make()
-// - intrinsic or reflective operations that allocate (e.g. append, reflect.New)
-// - intrinsic objects, e.g. the initial array behind os.Args.
-// - and their subelements, e.g. "alloc.y[*].z"
+// - functions
+// - globals
+// - tagged objects, representing interfaces and reflect.Values
+// - arrays created by conversions (e.g. []byte("foo"), []byte(s))
+// - stack- and heap-allocated variables (including composite literals)
+// - channels, maps and arrays created by make()
+// - intrinsic or reflective operations that allocate (e.g. append, reflect.New)
+// - intrinsic objects, e.g. the initial array behind os.Args.
+// - and their subelements, e.g. "alloc.y[*].z"
//
// Labels are so varied that they defy good generalizations;
// some have no value, no callgraph node, or no position.
@@ -33,7 +33,6 @@
// maps, channels, functions, tagged objects.
//
// At most one of Value() or ReflectType() may return non-nil.
-//
type Label struct {
obj *object // the addressable memory location containing this label
subelement *fieldInfo // subelement path within obj, e.g. ".a.b[*].c"
@@ -47,7 +46,6 @@
// ReflectType returns the type represented by this label if it is an
// reflect.rtype instance object or *reflect.rtype-tagged object.
-//
func (l Label) ReflectType() types.Type {
rtype, _ := l.obj.data.(types.Type)
return rtype
@@ -55,7 +53,6 @@
// Path returns the path to the subelement of the object containing
// this label. For example, ".x[*].y".
-//
func (l Label) Path() string {
return l.subelement.path()
}
@@ -79,23 +76,24 @@
// String returns the printed form of this label.
//
// Examples: Object type:
-// x (a variable)
-// (sync.Mutex).Lock (a function)
-// convert (array created by conversion)
-// makemap (map allocated via make)
-// makechan (channel allocated via make)
-// makeinterface (tagged object allocated by makeinterface)
-// <alloc in reflect.Zero> (allocation in instrinsic)
-// sync.Mutex (a reflect.rtype instance)
-// <command-line arguments> (an intrinsic object)
+//
+// x (a variable)
+// (sync.Mutex).Lock (a function)
+// convert (array created by conversion)
+// makemap (map allocated via make)
+// makechan (channel allocated via make)
+// makeinterface (tagged object allocated by makeinterface)
+// <alloc in reflect.Zero> (allocation in instrinsic)
+// sync.Mutex (a reflect.rtype instance)
+// <command-line arguments> (an intrinsic object)
//
// Labels within compound objects have subelement paths:
-// x.y[*].z (a struct variable, x)
-// append.y[*].z (array allocated by append)
-// makeslice.y[*].z (array allocated via make)
+//
+// x.y[*].z (a struct variable, x)
+// append.y[*].z (array allocated by append)
+// makeslice.y[*].z (array allocated via make)
//
// TODO(adonovan): expose func LabelString(*types.Package, Label).
-//
func (l Label) String() string {
var s string
switch v := l.obj.data.(type) {
diff --git a/go/pointer/opt.go b/go/pointer/opt.go
index 6defea1..bbd411c 100644
--- a/go/pointer/opt.go
+++ b/go/pointer/opt.go
@@ -27,7 +27,6 @@
//
// Renumbering makes the PTA log inscrutable. To aid debugging, later
// phases (e.g. HVN) must not rely on it having occurred.
-//
func (a *analysis) renumber() {
if a.log != nil {
fmt.Fprintf(a.log, "\n\n==== Renumbering\n\n")
diff --git a/go/pointer/pointer_test.go b/go/pointer/pointer_test.go
index 1ac5b6c..49065c4 100644
--- a/go/pointer/pointer_test.go
+++ b/go/pointer/pointer_test.go
@@ -69,60 +69,59 @@
//
// @calls f -> g
//
-// A 'calls' expectation asserts that edge (f, g) appears in the
-// callgraph. f and g are notated as per Function.String(), which
-// may contain spaces (e.g. promoted method in anon struct).
+// A 'calls' expectation asserts that edge (f, g) appears in the
+// callgraph. f and g are notated as per Function.String(), which
+// may contain spaces (e.g. promoted method in anon struct).
//
// @pointsto a | b | c
//
-// A 'pointsto' expectation asserts that the points-to set of its
-// operand contains exactly the set of labels {a,b,c} notated as per
-// labelString.
+// A 'pointsto' expectation asserts that the points-to set of its
+// operand contains exactly the set of labels {a,b,c} notated as per
+// labelString.
//
-// A 'pointsto' expectation must appear on the same line as a
-// print(x) statement; the expectation's operand is x.
+// A 'pointsto' expectation must appear on the same line as a
+// print(x) statement; the expectation's operand is x.
//
-// If one of the strings is "...", the expectation asserts that the
-// points-to set at least the other labels.
+// If one of the strings is "...", the expectation asserts that the
+// points-to set at least the other labels.
//
-// We use '|' because label names may contain spaces, e.g. methods
-// of anonymous structs.
+// We use '|' because label names may contain spaces, e.g. methods
+// of anonymous structs.
//
-// From a theoretical perspective, concrete types in interfaces are
-// labels too, but they are represented differently and so have a
-// different expectation, @types, below.
+// From a theoretical perspective, concrete types in interfaces are
+// labels too, but they are represented differently and so have a
+// different expectation, @types, below.
//
// @types t | u | v
//
-// A 'types' expectation asserts that the set of possible dynamic
-// types of its interface operand is exactly {t,u,v}, notated per
-// go/types.Type.String(). In other words, it asserts that the type
-// component of the interface may point to that set of concrete type
-// literals. It also works for reflect.Value, though the types
-// needn't be concrete in that case.
+// A 'types' expectation asserts that the set of possible dynamic
+// types of its interface operand is exactly {t,u,v}, notated per
+// go/types.Type.String(). In other words, it asserts that the type
+// component of the interface may point to that set of concrete type
+// literals. It also works for reflect.Value, though the types
+// needn't be concrete in that case.
//
-// A 'types' expectation must appear on the same line as a
-// print(x) statement; the expectation's operand is x.
+// A 'types' expectation must appear on the same line as a
+// print(x) statement; the expectation's operand is x.
//
-// If one of the strings is "...", the expectation asserts that the
-// interface's type may point to at least the other types.
+// If one of the strings is "...", the expectation asserts that the
+// interface's type may point to at least the other types.
//
-// We use '|' because type names may contain spaces.
+// We use '|' because type names may contain spaces.
//
// @warning "regexp"
//
-// A 'warning' expectation asserts that the analysis issues a
-// warning that matches the regular expression within the string
-// literal.
+// A 'warning' expectation asserts that the analysis issues a
+// warning that matches the regular expression within the string
+// literal.
//
// @line id
//
-// A line directive associates the name "id" with the current
-// file:line. The string form of labels will use this id instead of
-// a file:line, making @pointsto expectations more robust against
-// perturbations in the source file.
-// (NB, anon functions still include line numbers.)
-//
+// A line directive associates the name "id" with the current
+// file:line. The string form of labels will use this id instead of
+// a file:line, making @pointsto expectations more robust against
+// perturbations in the source file.
+// (NB, anon functions still include line numbers.)
type expectation struct {
kind string // "pointsto" | "pointstoquery" | "types" | "calls" | "warning"
filepath string
diff --git a/go/pointer/reflect.go b/go/pointer/reflect.go
index 7aa1a9c..efb11b0 100644
--- a/go/pointer/reflect.go
+++ b/go/pointer/reflect.go
@@ -1943,14 +1943,13 @@
// types they create to ensure termination of the algorithm in cases
// where the output of a type constructor flows to its input, e.g.
//
-// func f(t reflect.Type) {
-// f(reflect.PtrTo(t))
-// }
+// func f(t reflect.Type) {
+// f(reflect.PtrTo(t))
+// }
//
// It does this by limiting the type height to k, but this still leaves
// a potentially exponential (4^k) number of of types that may be
// enumerated in pathological cases.
-//
func typeHeight(T types.Type) int {
switch T := T.(type) {
case *types.Chan:
diff --git a/go/pointer/solve.go b/go/pointer/solve.go
index 0fdd098..7a41b78 100644
--- a/go/pointer/solve.go
+++ b/go/pointer/solve.go
@@ -91,7 +91,6 @@
// and adds them to the graph, ensuring
// that new constraints are applied to pre-existing labels and
// that pre-existing constraints are applied to new labels.
-//
func (a *analysis) processNewConstraints() {
// Take the slice of new constraints.
// (May grow during call to solveConstraints.)
@@ -151,7 +150,6 @@
// solveConstraints applies each resolution rule attached to node n to
// the set of labels delta. It may generate new constraints in
// a.constraints.
-//
func (a *analysis) solveConstraints(n *node, delta *nodeset) {
if delta.IsEmpty() {
return
@@ -199,7 +197,6 @@
//
// The size of the copy is implicitly 1.
// It returns true if pts(dst) changed.
-//
func (a *analysis) onlineCopy(dst, src nodeid) bool {
if dst != src {
if nsrc := a.nodes[src]; nsrc.solve.copyTo.add(dst) {
@@ -221,7 +218,6 @@
//
// TODO(adonovan): now that we support a.copy() during solving, we
// could eliminate onlineCopyN, but it's much slower. Investigate.
-//
func (a *analysis) onlineCopyN(dst, src nodeid, sizeof uint32) uint32 {
for i := uint32(0); i < sizeof; i++ {
if a.onlineCopy(dst, src) {
diff --git a/go/pointer/util.go b/go/pointer/util.go
index 5bdd623..5fec1fc 100644
--- a/go/pointer/util.go
+++ b/go/pointer/util.go
@@ -35,7 +35,6 @@
// CanHaveDynamicTypes reports whether the type T can "hold" dynamic types,
// i.e. is an interface (incl. reflect.Type) or a reflect.Value.
-//
func CanHaveDynamicTypes(T types.Type) bool {
switch T := T.(type) {
case *types.Named:
@@ -69,17 +68,21 @@
// of a type T: the subelement's type and its path from the root of T.
//
// For example, for this type:
-// type line struct{ points []struct{x, y int} }
-// flatten() of the inner struct yields the following []fieldInfo:
-// struct{ x, y int } ""
-// int ".x"
-// int ".y"
-// and flatten(line) yields:
-// struct{ points []struct{x, y int} } ""
-// struct{ x, y int } ".points[*]"
-// int ".points[*].x
-// int ".points[*].y"
//
+// type line struct{ points []struct{x, y int} }
+//
+// flatten() of the inner struct yields the following []fieldInfo:
+//
+// struct{ x, y int } ""
+// int ".x"
+// int ".y"
+//
+// and flatten(line) yields:
+//
+// struct{ points []struct{x, y int} } ""
+// struct{ x, y int } ".points[*]"
+// int ".points[*].x
+// int ".points[*].y"
type fieldInfo struct {
typ types.Type
@@ -89,7 +92,6 @@
}
// path returns a user-friendly string describing the subelement path.
-//
func (fi *fieldInfo) path() string {
var buf bytes.Buffer
for p := fi; p != nil; p = p.tail {
@@ -113,7 +115,6 @@
// reflect.Value is considered pointerlike, similar to interface{}.
//
// Callers must not mutate the result.
-//
func (a *analysis) flatten(t types.Type) []*fieldInfo {
fl, ok := a.flattenMemo[t]
if !ok {
