LEFT | RIGHT |
(no file at all) | |
1 // Copyright 2013 The Go Authors. All rights reserved. | 1 // Copyright 2013 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 package oracle | 5 package oracle |
6 | 6 |
7 import ( | 7 import ( |
| 8 "go/token" |
| 9 |
| 10 "code.google.com/p/go.tools/oracle/json" |
8 "code.google.com/p/go.tools/pointer" | 11 "code.google.com/p/go.tools/pointer" |
9 "code.google.com/p/go.tools/ssa" | 12 "code.google.com/p/go.tools/ssa" |
10 ) | 13 ) |
11 | 14 |
12 // Callstack displays an arbitrary path from a root of the callgraph | 15 // Callstack displays an arbitrary path from a root of the callgraph |
13 // to the function at the current position. | 16 // to the function at the current position. |
14 // | 17 // |
15 // The information may be misleading in a context-insensitive | 18 // The information may be misleading in a context-insensitive |
16 // analysis. e.g. the call path X->Y->Z might be infeasible if Y never | 19 // analysis. e.g. the call path X->Y->Z might be infeasible if Y never |
17 // calls Z when it is called from X. TODO(adonovan): think about UI. | 20 // calls Z when it is called from X. TODO(adonovan): think about UI. |
(...skipping 17 matching lines...) Expand all Loading... |
35 if target == nil { | 38 if target == nil { |
36 return nil, o.errorf(o.queryPath[0], | 39 return nil, o.errorf(o.queryPath[0], |
37 "no SSA function built for this location (dead code?)") | 40 "no SSA function built for this location (dead code?)") |
38 } | 41 } |
39 | 42 |
40 // Run the pointer analysis and build the complete call graph. | 43 // Run the pointer analysis and build the complete call graph. |
41 callgraph := make(pointer.CallGraph) | 44 callgraph := make(pointer.CallGraph) |
42 o.config.Call = callgraph.AddEdge | 45 o.config.Call = callgraph.AddEdge |
43 root := ptrAnalysis(o) | 46 root := ptrAnalysis(o) |
44 | 47 |
| 48 seen := make(map[pointer.CallGraphNode]bool) |
| 49 var callstack []pointer.CallSite |
| 50 |
| 51 // Use depth-first search to find an arbitrary path from a |
| 52 // root to the target function. |
| 53 var search func(cgn pointer.CallGraphNode) bool |
| 54 search = func(cgn pointer.CallGraphNode) bool { |
| 55 if !seen[cgn] { |
| 56 seen[cgn] = true |
| 57 if cgn.Func() == target { |
| 58 return true |
| 59 } |
| 60 for callee, site := range callgraph[cgn] { |
| 61 if search(callee) { |
| 62 callstack = append(callstack, site) |
| 63 return true |
| 64 } |
| 65 } |
| 66 } |
| 67 return false |
| 68 } |
| 69 |
| 70 for toplevel := range callgraph[root] { |
| 71 if search(toplevel) { |
| 72 break |
| 73 } |
| 74 } |
| 75 |
45 return &callstackResult{ | 76 return &callstackResult{ |
46 target: target, | 77 target: target, |
47 » » root: root, | 78 » » callstack: callstack, |
48 » » callgraph: callgraph, | |
49 }, nil | 79 }, nil |
50 } | 80 } |
51 | 81 |
52 type callstackResult struct { | 82 type callstackResult struct { |
53 target *ssa.Function | 83 target *ssa.Function |
54 » root pointer.CallGraphNode | 84 » callstack []pointer.CallSite |
55 » callgraph pointer.CallGraph | |
56 | |
57 » seen map[pointer.CallGraphNode]bool // used by display | |
58 } | 85 } |
59 | 86 |
60 func (r *callstackResult) search(o *oracle, cgn pointer.CallGraphNode) bool { | 87 func (r *callstackResult) display(printf printfFunc) { |
61 » if !r.seen[cgn] { | 88 » if r.callstack != nil { |
62 » » r.seen[cgn] = true | 89 » » printf(false, "Found a call path from root to %s", r.target) |
63 » » if cgn.Func() == r.target { | 90 » » printf(r.target, "%s", r.target) |
64 » » » o.printf(o, "Found a call path from root to %s", r.targe
t) | 91 » » for _, site := range r.callstack { |
65 » » » o.printf(r.target, "%s", r.target) | 92 » » » printf(site, "%s from %s", site.Description(), site.Call
er().Func()) |
66 » » » return true | |
67 } | 93 } |
68 » » for callee, site := range r.callgraph[cgn] { | 94 » } else { |
69 » » » if r.search(o, callee) { | 95 » » printf(r.target, "%s is unreachable in this analysis scope", r.t
arget) |
70 » » » » o.printf(site, "%s from %s", site.Description(),
cgn.Func()) | |
71 » » » » return true | |
72 » » » } | |
73 » » } | |
74 } | 96 } |
75 return false | |
76 } | 97 } |
77 | 98 |
78 func (r *callstackResult) display(o *oracle) { | 99 func (r *callstackResult) toJSON(res *json.Result, fset *token.FileSet) { |
79 » // Show only an arbitrary path from a root to the current function. | 100 » var callers []json.Caller |
80 » // We use depth-first search. | 101 » for _, site := range r.callstack { |
81 | 102 » » callers = append(callers, json.Caller{ |
82 » r.seen = make(map[pointer.CallGraphNode]bool) | 103 » » » Pos: site.Caller().Func().Prog.Fset.Position(site.Pos
()).String(), |
83 | 104 » » » Caller: site.Caller().Func().String(), |
84 » for toplevel := range r.callgraph[r.root] { | 105 » » » Desc: site.Description(), |
85 » » if r.search(o, toplevel) { | 106 » » }) |
86 » » » return | |
87 » » } | |
88 } | 107 } |
89 » o.printf(r.target, "%s is unreachable in this analysis scope", r.target) | 108 » res.Callstack = &json.CallStack{ |
| 109 » » Pos: r.target.Prog.Fset.Position(r.target.Pos()).String(), |
| 110 » » Target: r.target.String(), |
| 111 » » Callers: callers, |
| 112 » } |
90 } | 113 } |
LEFT | RIGHT |