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/loader"
16	"golang.org/x/tools/go/ssa"
17	"golang.org/x/tools/go/ssa/ssautil"
18)
19
20// peers enumerates, for a given channel send (or receive) operation,
21// the set of possible receives (or sends) that correspond to it.
22//
23// TODO(adonovan): support reflect.{Select,Recv,Send,Close}.
24// TODO(adonovan): permit the user to query based on a MakeChan (not send/recv),
25// or the implicit receive in "for v := range ch".
26func peers(q *Query) error {
27	lconf := loader.Config{Build: q.Build}
28
29	if err := setPTAScope(&lconf, q.Scope); err != nil {
30		return err
31	}
32
33	// Load/parse/type-check the program.
34	lprog, err := loadWithSoftErrors(&lconf)
35	if err != nil {
36		return err
37	}
38
39	qpos, err := parseQueryPos(lprog, q.Pos, false)
40	if err != nil {
41		return err
42	}
43
44	prog := ssautil.CreateProgram(lprog, ssa.GlobalDebug)
45
46	ptaConfig, err := setupPTA(prog, lprog, q.PTALog, q.Reflection)
47	if err != nil {
48		return err
49	}
50
51	opPos := findOp(qpos)
52	if opPos == token.NoPos {
53		return fmt.Errorf("there is no channel operation here")
54	}
55
56	// Defer SSA construction till after errors are reported.
57	prog.Build()
58
59	var queryOp chanOp // the originating send or receive operation
60	var ops []chanOp   // all sends/receives of opposite direction
61
62	// Look at all channel operations in the whole ssa.Program.
63	// Build a list of those of same type as the query.
64	allFuncs := ssautil.AllFunctions(prog)
65	for fn := range allFuncs {
66		for _, b := range fn.Blocks {
67			for _, instr := range b.Instrs {
68				for _, op := range chanOps(instr) {
69					ops = append(ops, op)
70					if op.pos == opPos {
71						queryOp = op // we found the query op
72					}
73				}
74			}
75		}
76	}
77	if queryOp.ch == nil {
78		return fmt.Errorf("ssa.Instruction for send/receive not found")
79	}
80
81	// Discard operations of wrong channel element type.
82	// Build set of channel ssa.Values as query to pointer analysis.
83	// We compare channels by element types, not channel types, to
84	// ignore both directionality and type names.
85	queryType := queryOp.ch.Type()
86	queryElemType := queryType.Underlying().(*types.Chan).Elem()
87	ptaConfig.AddQuery(queryOp.ch)
88	i := 0
89	for _, op := range ops {
90		if types.Identical(op.ch.Type().Underlying().(*types.Chan).Elem(), queryElemType) {
91			ptaConfig.AddQuery(op.ch)
92			ops[i] = op
93			i++
94		}
95	}
96	ops = ops[:i]
97
98	// Run the pointer analysis.
99	ptares := ptrAnalysis(ptaConfig)
100
101	// Find the points-to set.
102	queryChanPtr := ptares.Queries[queryOp.ch]
103
104	// Ascertain which make(chan) labels the query's channel can alias.
105	var makes []token.Pos
106	for _, label := range queryChanPtr.PointsTo().Labels() {
107		makes = append(makes, label.Pos())
108	}
109	sort.Sort(byPos(makes))
110
111	// Ascertain which channel operations can alias the same make(chan) labels.
112	var sends, receives, closes []token.Pos
113	for _, op := range ops {
114		if ptr, ok := ptares.Queries[op.ch]; ok && ptr.MayAlias(queryChanPtr) {
115			switch op.dir {
116			case types.SendOnly:
117				sends = append(sends, op.pos)
118			case types.RecvOnly:
119				receives = append(receives, op.pos)
120			case types.SendRecv:
121				closes = append(closes, op.pos)
122			}
123		}
124	}
125	sort.Sort(byPos(sends))
126	sort.Sort(byPos(receives))
127	sort.Sort(byPos(closes))
128
129	q.Output(lprog.Fset, &peersResult{
130		queryPos:  opPos,
131		queryType: queryType,
132		makes:     makes,
133		sends:     sends,
134		receives:  receives,
135		closes:    closes,
136	})
137	return nil
138}
139
140// findOp returns the position of the enclosing send/receive/close op.
141// For send and receive operations, this is the position of the <- token;
142// for close operations, it's the Lparen of the function call.
143//
144// TODO(adonovan): handle implicit receive operations from 'for...range chan' statements.
145func findOp(qpos *queryPos) token.Pos {
146	for _, n := range qpos.path {
147		switch n := n.(type) {
148		case *ast.UnaryExpr:
149			if n.Op == token.ARROW {
150				return n.OpPos
151			}
152		case *ast.SendStmt:
153			return n.Arrow
154		case *ast.CallExpr:
155			// close function call can only exist as a direct identifier
156			if close, ok := unparen(n.Fun).(*ast.Ident); ok {
157				if b, ok := qpos.info.Info.Uses[close].(*types.Builtin); ok && b.Name() == "close" {
158					return n.Lparen
159				}
160			}
161		}
162	}
163	return token.NoPos
164}
165
166// chanOp abstracts an ssa.Send, ssa.Unop(ARROW), or a SelectState.
167type chanOp struct {
168	ch  ssa.Value
169	dir types.ChanDir // SendOnly=send, RecvOnly=recv, SendRecv=close
170	pos token.Pos
171}
172
173// chanOps returns a slice of all the channel operations in the instruction.
174func chanOps(instr ssa.Instruction) []chanOp {
175	// TODO(adonovan): handle calls to reflect.{Select,Recv,Send,Close} too.
176	var ops []chanOp
177	switch instr := instr.(type) {
178	case *ssa.UnOp:
179		if instr.Op == token.ARROW {
180			ops = append(ops, chanOp{instr.X, types.RecvOnly, instr.Pos()})
181		}
182	case *ssa.Send:
183		ops = append(ops, chanOp{instr.Chan, types.SendOnly, instr.Pos()})
184	case *ssa.Select:
185		for _, st := range instr.States {
186			ops = append(ops, chanOp{st.Chan, st.Dir, st.Pos})
187		}
188	case ssa.CallInstruction:
189		cc := instr.Common()
190		if b, ok := cc.Value.(*ssa.Builtin); ok && b.Name() == "close" {
191			ops = append(ops, chanOp{cc.Args[0], types.SendRecv, cc.Pos()})
192		}
193	}
194	return ops
195}
196
197// TODO(adonovan): show the line of text for each pos, like "referrers" does.
198type peersResult struct {
199	queryPos                       token.Pos   // of queried channel op
200	queryType                      types.Type  // type of queried channel
201	makes, sends, receives, closes []token.Pos // positions of aliased makechan/send/receive/close instrs
202}
203
204func (r *peersResult) PrintPlain(printf printfFunc) {
205	if len(r.makes) == 0 {
206		printf(r.queryPos, "This channel can't point to anything.")
207		return
208	}
209	printf(r.queryPos, "This channel of type %s may be:", r.queryType)
210	for _, alloc := range r.makes {
211		printf(alloc, "\tallocated here")
212	}
213	for _, send := range r.sends {
214		printf(send, "\tsent to, here")
215	}
216	for _, receive := range r.receives {
217		printf(receive, "\treceived from, here")
218	}
219	for _, clos := range r.closes {
220		printf(clos, "\tclosed, here")
221	}
222}
223
224func (r *peersResult) JSON(fset *token.FileSet) []byte {
225	peers := &serial.Peers{
226		Pos:  fset.Position(r.queryPos).String(),
227		Type: r.queryType.String(),
228	}
229	for _, alloc := range r.makes {
230		peers.Allocs = append(peers.Allocs, fset.Position(alloc).String())
231	}
232	for _, send := range r.sends {
233		peers.Sends = append(peers.Sends, fset.Position(send).String())
234	}
235	for _, receive := range r.receives {
236		peers.Receives = append(peers.Receives, fset.Position(receive).String())
237	}
238	for _, clos := range r.closes {
239		peers.Closes = append(peers.Closes, fset.Position(clos).String())
240	}
241	return toJSON(peers)
242}
243
244// -------- utils --------
245
246// NB: byPos is not deterministic across packages since it depends on load order.
247// Use lessPos if the tests need it.
248type byPos []token.Pos
249
250func (p byPos) Len() int           { return len(p) }
251func (p byPos) Less(i, j int) bool { return p[i] < p[j] }
252func (p byPos) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
253