1// Copyright 2013 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package main
6
7import (
8	"fmt"
9	"go/ast"
10	"go/token"
11	"go/types"
12	"sort"
13
14	"golang.org/x/tools/cmd/guru/serial"
15	"golang.org/x/tools/go/ast/astutil"
16	"golang.org/x/tools/go/loader"
17	"golang.org/x/tools/go/pointer"
18	"golang.org/x/tools/go/ssa"
19	"golang.org/x/tools/go/ssa/ssautil"
20)
21
22// pointsto runs the pointer analysis on the selected expression,
23// and reports its points-to set (for a pointer-like expression)
24// or its dynamic types (for an interface, reflect.Value, or
25// reflect.Type expression) and their points-to sets.
26//
27// All printed sets are sorted to ensure determinism.
28//
29func pointsto(q *Query) error {
30	lconf := loader.Config{Build: q.Build}
31
32	if err := setPTAScope(&lconf, q.Scope); err != nil {
33		return err
34	}
35
36	// Load/parse/type-check the program.
37	lprog, err := loadWithSoftErrors(&lconf)
38	if err != nil {
39		return err
40	}
41
42	qpos, err := parseQueryPos(lprog, q.Pos, true) // needs exact pos
43	if err != nil {
44		return err
45	}
46
47	prog := ssautil.CreateProgram(lprog, ssa.GlobalDebug)
48
49	ptaConfig, err := setupPTA(prog, lprog, q.PTALog, q.Reflection)
50	if err != nil {
51		return err
52	}
53
54	path, action := findInterestingNode(qpos.info, qpos.path)
55	if action != actionExpr {
56		return fmt.Errorf("pointer analysis wants an expression; got %s",
57			astutil.NodeDescription(qpos.path[0]))
58	}
59
60	var expr ast.Expr
61	var obj types.Object
62	switch n := path[0].(type) {
63	case *ast.ValueSpec:
64		// ambiguous ValueSpec containing multiple names
65		return fmt.Errorf("multiple value specification")
66	case *ast.Ident:
67		obj = qpos.info.ObjectOf(n)
68		expr = n
69	case ast.Expr:
70		expr = n
71	default:
72		// TODO(adonovan): is this reachable?
73		return fmt.Errorf("unexpected AST for expr: %T", n)
74	}
75
76	// Reject non-pointerlike types (includes all constants---except nil).
77	// TODO(adonovan): reject nil too.
78	typ := qpos.info.TypeOf(expr)
79	if !pointer.CanPoint(typ) {
80		return fmt.Errorf("pointer analysis wants an expression of reference type; got %s", typ)
81	}
82
83	// Determine the ssa.Value for the expression.
84	var value ssa.Value
85	var isAddr bool
86	if obj != nil {
87		// def/ref of func/var object
88		value, isAddr, err = ssaValueForIdent(prog, qpos.info, obj, path)
89	} else {
90		value, isAddr, err = ssaValueForExpr(prog, qpos.info, path)
91	}
92	if err != nil {
93		return err // e.g. trivially dead code
94	}
95
96	// Defer SSA construction till after errors are reported.
97	prog.Build()
98
99	// Run the pointer analysis.
100	ptrs, err := runPTA(ptaConfig, value, isAddr)
101	if err != nil {
102		return err // e.g. analytically unreachable
103	}
104
105	q.Output(lprog.Fset, &pointstoResult{
106		qpos: qpos,
107		typ:  typ,
108		ptrs: ptrs,
109	})
110	return nil
111}
112
113// ssaValueForIdent returns the ssa.Value for the ast.Ident whose path
114// to the root of the AST is path.  isAddr reports whether the
115// ssa.Value is the address denoted by the ast.Ident, not its value.
116//
117func ssaValueForIdent(prog *ssa.Program, qinfo *loader.PackageInfo, obj types.Object, path []ast.Node) (value ssa.Value, isAddr bool, err error) {
118	switch obj := obj.(type) {
119	case *types.Var:
120		pkg := prog.Package(qinfo.Pkg)
121		pkg.Build()
122		if v, addr := prog.VarValue(obj, pkg, path); v != nil {
123			return v, addr, nil
124		}
125		return nil, false, fmt.Errorf("can't locate SSA Value for var %s", obj.Name())
126
127	case *types.Func:
128		fn := prog.FuncValue(obj)
129		if fn == nil {
130			return nil, false, fmt.Errorf("%s is an interface method", obj)
131		}
132		// TODO(adonovan): there's no point running PTA on a *Func ident.
133		// Eliminate this feature.
134		return fn, false, nil
135	}
136	panic(obj)
137}
138
139// ssaValueForExpr returns the ssa.Value of the non-ast.Ident
140// expression whose path to the root of the AST is path.
141//
142func ssaValueForExpr(prog *ssa.Program, qinfo *loader.PackageInfo, path []ast.Node) (value ssa.Value, isAddr bool, err error) {
143	pkg := prog.Package(qinfo.Pkg)
144	pkg.SetDebugMode(true)
145	pkg.Build()
146
147	fn := ssa.EnclosingFunction(pkg, path)
148	if fn == nil {
149		return nil, false, fmt.Errorf("no SSA function built for this location (dead code?)")
150	}
151
152	if v, addr := fn.ValueForExpr(path[0].(ast.Expr)); v != nil {
153		return v, addr, nil
154	}
155
156	return nil, false, fmt.Errorf("can't locate SSA Value for expression in %s", fn)
157}
158
159// runPTA runs the pointer analysis of the selected SSA value or address.
160func runPTA(conf *pointer.Config, v ssa.Value, isAddr bool) (ptrs []pointerResult, err error) {
161	T := v.Type()
162	if isAddr {
163		conf.AddIndirectQuery(v)
164		T = deref(T)
165	} else {
166		conf.AddQuery(v)
167	}
168	ptares := ptrAnalysis(conf)
169
170	var ptr pointer.Pointer
171	if isAddr {
172		ptr = ptares.IndirectQueries[v]
173	} else {
174		ptr = ptares.Queries[v]
175	}
176	if ptr == (pointer.Pointer{}) {
177		return nil, fmt.Errorf("pointer analysis did not find expression (dead code?)")
178	}
179	pts := ptr.PointsTo()
180
181	if pointer.CanHaveDynamicTypes(T) {
182		// Show concrete types for interface/reflect.Value expression.
183		if concs := pts.DynamicTypes(); concs.Len() > 0 {
184			concs.Iterate(func(conc types.Type, pta interface{}) {
185				labels := pta.(pointer.PointsToSet).Labels()
186				sort.Sort(byPosAndString(labels)) // to ensure determinism
187				ptrs = append(ptrs, pointerResult{conc, labels})
188			})
189		}
190	} else {
191		// Show labels for other expressions.
192		labels := pts.Labels()
193		sort.Sort(byPosAndString(labels)) // to ensure determinism
194		ptrs = append(ptrs, pointerResult{T, labels})
195	}
196	sort.Sort(byTypeString(ptrs)) // to ensure determinism
197	return ptrs, nil
198}
199
200type pointerResult struct {
201	typ    types.Type       // type of the pointer (always concrete)
202	labels []*pointer.Label // set of labels
203}
204
205type pointstoResult struct {
206	qpos *queryPos
207	typ  types.Type      // type of expression
208	ptrs []pointerResult // pointer info (typ is concrete => len==1)
209}
210
211func (r *pointstoResult) PrintPlain(printf printfFunc) {
212	if pointer.CanHaveDynamicTypes(r.typ) {
213		// Show concrete types for interface, reflect.Type or
214		// reflect.Value expression.
215
216		if len(r.ptrs) > 0 {
217			printf(r.qpos, "this %s may contain these dynamic types:", r.qpos.typeString(r.typ))
218			for _, ptr := range r.ptrs {
219				var obj types.Object
220				if nt, ok := deref(ptr.typ).(*types.Named); ok {
221					obj = nt.Obj()
222				}
223				if len(ptr.labels) > 0 {
224					printf(obj, "\t%s, may point to:", r.qpos.typeString(ptr.typ))
225					printLabels(printf, ptr.labels, "\t\t")
226				} else {
227					printf(obj, "\t%s", r.qpos.typeString(ptr.typ))
228				}
229			}
230		} else {
231			printf(r.qpos, "this %s cannot contain any dynamic types.", r.typ)
232		}
233	} else {
234		// Show labels for other expressions.
235		if ptr := r.ptrs[0]; len(ptr.labels) > 0 {
236			printf(r.qpos, "this %s may point to these objects:",
237				r.qpos.typeString(r.typ))
238			printLabels(printf, ptr.labels, "\t")
239		} else {
240			printf(r.qpos, "this %s may not point to anything.",
241				r.qpos.typeString(r.typ))
242		}
243	}
244}
245
246func (r *pointstoResult) JSON(fset *token.FileSet) []byte {
247	var pts []serial.PointsTo
248	for _, ptr := range r.ptrs {
249		var namePos string
250		if nt, ok := deref(ptr.typ).(*types.Named); ok {
251			namePos = fset.Position(nt.Obj().Pos()).String()
252		}
253		var labels []serial.PointsToLabel
254		for _, l := range ptr.labels {
255			labels = append(labels, serial.PointsToLabel{
256				Pos:  fset.Position(l.Pos()).String(),
257				Desc: l.String(),
258			})
259		}
260		pts = append(pts, serial.PointsTo{
261			Type:    r.qpos.typeString(ptr.typ),
262			NamePos: namePos,
263			Labels:  labels,
264		})
265	}
266	return toJSON(pts)
267}
268
269type byTypeString []pointerResult
270
271func (a byTypeString) Len() int           { return len(a) }
272func (a byTypeString) Less(i, j int) bool { return a[i].typ.String() < a[j].typ.String() }
273func (a byTypeString) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
274
275type byPosAndString []*pointer.Label
276
277func (a byPosAndString) Len() int { return len(a) }
278func (a byPosAndString) Less(i, j int) bool {
279	cmp := a[i].Pos() - a[j].Pos()
280	return cmp < 0 || (cmp == 0 && a[i].String() < a[j].String())
281}
282func (a byPosAndString) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
283
284func printLabels(printf printfFunc, labels []*pointer.Label, prefix string) {
285	// TODO(adonovan): due to context-sensitivity, many of these
286	// labels may differ only by context, which isn't apparent.
287	for _, label := range labels {
288		printf(label, "%s%s", prefix, label)
289	}
290}
291