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.
5 // No testdata on Android.
12 // This test uses 'expectation' comments embedded within testdata/*.go
13 // files to specify the expected pointer analysis behaviour.
14 // See below for grammar.
29 "golang.org/x/tools/go/callgraph"
30 "golang.org/x/tools/go/loader"
31 "golang.org/x/tools/go/pointer"
32 "golang.org/x/tools/go/ssa"
33 "golang.org/x/tools/go/ssa/ssautil"
34 "golang.org/x/tools/go/types/typeutil"
37 var inputs = []string{
39 "testdata/another.go",
40 "testdata/arrayreflect.go",
42 "testdata/channels.go",
43 "testdata/chanreflect.go",
44 "testdata/context.go",
46 "testdata/extended.go",
47 "testdata/finalizer.go",
49 "testdata/fmtexcerpt.go",
51 "testdata/funcreflect.go",
52 "testdata/hello.go", // NB: causes spurious failure of HVN cross-check
53 "testdata/interfaces.go",
54 "testdata/issue9002.go",
55 "testdata/mapreflect.go",
59 "testdata/reflect.go",
61 "testdata/structreflect.go",
62 "testdata/structs.go",
63 // "testdata/timer.go", // TODO(adonovan): fix broken assumptions about runtime timers
66 // Expectation grammar:
70 // A 'calls' expectation asserts that edge (f, g) appears in the
71 // callgraph. f and g are notated as per Function.String(), which
72 // may contain spaces (e.g. promoted method in anon struct).
74 // @pointsto a | b | c
76 // A 'pointsto' expectation asserts that the points-to set of its
77 // operand contains exactly the set of labels {a,b,c} notated as per
80 // A 'pointsto' expectation must appear on the same line as a
81 // print(x) statement; the expectation's operand is x.
83 // If one of the strings is "...", the expectation asserts that the
84 // points-to set at least the other labels.
86 // We use '|' because label names may contain spaces, e.g. methods
87 // of anonymous structs.
89 // From a theoretical perspective, concrete types in interfaces are
90 // labels too, but they are represented differently and so have a
91 // different expectation, @types, below.
95 // A 'types' expectation asserts that the set of possible dynamic
96 // types of its interface operand is exactly {t,u,v}, notated per
97 // go/types.Type.String(). In other words, it asserts that the type
98 // component of the interface may point to that set of concrete type
99 // literals. It also works for reflect.Value, though the types
100 // needn't be concrete in that case.
102 // A 'types' expectation must appear on the same line as a
103 // print(x) statement; the expectation's operand is x.
105 // If one of the strings is "...", the expectation asserts that the
106 // interface's type may point to at least the other types.
108 // We use '|' because type names may contain spaces.
112 // A 'warning' expectation asserts that the analysis issues a
113 // warning that matches the regular expression within the string
118 // A line directive associates the name "id" with the current
119 // file:line. The string form of labels will use this id instead of
120 // a file:line, making @pointsto expectations more robust against
121 // perturbations in the source file.
122 // (NB, anon functions still include line numbers.)
124 type expectation struct {
125 kind string // "pointsto" | "pointstoquery" | "types" | "calls" | "warning"
127 linenum int // source line number, 1-based
129 query string // extended query
130 extended *pointer.Pointer // extended query pointer
131 types []types.Type // for types
134 func (e *expectation) String() string {
135 return fmt.Sprintf("@%s[%s]", e.kind, strings.Join(e.args, " | "))
138 func (e *expectation) errorf(format string, args ...interface{}) {
139 fmt.Printf("%s:%d: ", e.filename, e.linenum)
140 fmt.Printf(format, args...)
144 func (e *expectation) needsProbe() bool {
145 return e.kind == "pointsto" || e.kind == "pointstoquery" || e.kind == "types"
148 // Find probe (call to print(x)) of same source file/line as expectation.
149 func findProbe(prog *ssa.Program, probes map[*ssa.CallCommon]bool, queries map[ssa.Value]pointer.Pointer, e *expectation) (site *ssa.CallCommon, pts pointer.PointsToSet) {
150 for call := range probes {
151 pos := prog.Fset.Position(call.Pos())
152 if pos.Line == e.linenum && pos.Filename == e.filename {
153 // TODO(adonovan): send this to test log (display only on failure).
154 // fmt.Printf("%s:%d: info: found probe for %s: %s\n",
155 // e.filename, e.linenum, e, p.arg0) // debugging
156 return call, queries[call.Args[0]].PointsTo()
159 return // e.g. analysis didn't reach this call
162 func doOneInput(input, filename string) bool {
163 var conf loader.Config
166 f, err := conf.ParseFile(filename, input)
172 // Create single-file main package and import its dependencies.
173 conf.CreateFromFiles("main", f)
174 iprog, err := conf.Load()
179 mainPkgInfo := iprog.Created[0].Pkg
181 // SSA creation + building.
182 prog := ssautil.CreateProgram(iprog, ssa.SanityCheckFunctions)
185 mainpkg := prog.Package(mainPkgInfo)
186 ptrmain := mainpkg // main package for the pointer analysis
187 if mainpkg.Func("main") == nil {
188 // No main function; assume it's a test.
189 ptrmain = prog.CreateTestMainPackage(mainpkg)
192 // Find all calls to the built-in print(x). Analytically,
193 // print is a no-op, but it's a convenient hook for testing
194 // the PTS of an expression, so our tests use it.
195 probes := make(map[*ssa.CallCommon]bool)
196 for fn := range ssautil.AllFunctions(prog) {
197 if fn.Pkg == mainpkg {
198 for _, b := range fn.Blocks {
199 for _, instr := range b.Instrs {
200 if instr, ok := instr.(ssa.CallInstruction); ok {
201 call := instr.Common()
202 if b, ok := call.Value.(*ssa.Builtin); ok && b.Name() == "print" && len(call.Args) == 1 {
203 probes[instr.Common()] = true
213 lineMapping := make(map[string]string) // maps "file:line" to @line tag
215 // Parse expectations in this input.
216 var exps []*expectation
217 re := regexp.MustCompile("// *@([a-z]*) *(.*)$")
218 lines := strings.Split(input, "\n")
219 for linenum, line := range lines {
220 linenum++ // make it 1-based
221 if matches := re.FindAllStringSubmatch(line, -1); matches != nil {
223 kind, rest := match[1], match[2]
224 e := &expectation{kind: kind, filename: filename, linenum: linenum}
229 e.errorf("@%s expectation requires identifier", kind)
231 lineMapping[fmt.Sprintf("%s:%d", filename, linenum)] = rest
236 if e.needsProbe() && !strings.Contains(line, "print(") {
238 e.errorf("@%s expectation must follow call to print(x)", kind)
244 e.args = split(rest, "|")
246 case "pointstoquery":
247 args := strings.SplitN(rest, " ", 2)
249 e.args = split(args[1], "|")
251 for _, typstr := range split(rest, "|") {
252 var t types.Type = types.Typ[types.Invalid] // means "..."
254 tv, err := types.Eval(prog.Fset, mainpkg.Pkg, f.Pos(), typstr)
257 // Don't print err since its location is bad.
258 e.errorf("'%s' is not a valid type: %s", typstr, err)
263 e.types = append(e.types, t)
267 e.args = split(rest, "->")
268 // TODO(adonovan): eagerly reject the
269 // expectation if fn doesn't denote
270 // existing function, rather than fail
271 // the expectation after analysis.
272 if len(e.args) != 2 {
274 e.errorf("@calls expectation wants 'caller -> callee' arguments")
279 lit, err := strconv.Unquote(strings.TrimSpace(rest))
282 e.errorf("couldn't parse @warning operand: %s", err.Error())
285 e.args = append(e.args, lit)
289 e.errorf("unknown expectation kind: %s", e)
292 exps = append(exps, e)
297 fmt.Fprintf(&log, "Input: %s\n", filename)
300 config := &pointer.Config{
302 BuildCallGraph: true,
303 Mains: []*ssa.Package{ptrmain},
307 for probe := range probes {
309 pos := prog.Fset.Position(probe.Pos())
310 for _, e := range exps {
311 if e.linenum == pos.Line && e.filename == pos.Filename && e.kind == "pointstoquery" {
313 e.extended, err = config.AddExtendedQuery(v, e.query)
320 if pointer.CanPoint(v.Type()) {
325 // Print the log is there was an error or a panic.
328 if !complete || !ok {
329 log.WriteTo(os.Stderr)
333 result, err := pointer.Analyze(config)
335 panic(err) // internal error in pointer analysis
338 // Check the expectations.
339 for _, e := range exps {
340 var call *ssa.CallCommon
341 var pts pointer.PointsToSet
342 var tProbe types.Type
344 if call, pts = findProbe(prog, probes, result.Queries, e); call == nil {
346 e.errorf("unreachable print() statement has expectation %s", e)
349 if e.extended != nil {
350 pts = e.extended.PointsTo()
352 tProbe = call.Args[0].Type()
353 if !pointer.CanPoint(tProbe) {
355 e.errorf("expectation on non-pointerlike operand: %s", tProbe)
361 case "pointsto", "pointstoquery":
362 if !checkPointsToExpectation(e, pts, lineMapping, prog) {
367 if !checkTypesExpectation(e, pts, tProbe) {
372 if !checkCallsExpectation(prog, e, result.CallGraph) {
377 if !checkWarningExpectation(prog, e, result.Warnings) {
385 // ok = false // debugging: uncomment to always see log
390 func labelString(l *pointer.Label, lineMapping map[string]string, prog *ssa.Program) string {
391 // Functions and Globals need no pos suffix,
392 // nor do allocations in intrinsic operations
393 // (for which we'll print the function name).
394 switch l.Value().(type) {
395 case nil, *ssa.Function, *ssa.Global:
400 if pos := l.Pos(); pos != token.NoPos {
401 // Append the position, using a @line tag instead of a line number, if defined.
402 posn := prog.Fset.Position(pos)
403 s := fmt.Sprintf("%s:%d", posn.Filename, posn.Line)
404 if tag, ok := lineMapping[s]; ok {
405 return fmt.Sprintf("%s@%s:%d", str, tag, posn.Column)
407 str = fmt.Sprintf("%s@%s", str, posn)
412 func checkPointsToExpectation(e *expectation, pts pointer.PointsToSet, lineMapping map[string]string, prog *ssa.Program) bool {
413 expected := make(map[string]int)
414 surplus := make(map[string]int)
416 for _, g := range e.args {
423 // Find the set of labels that the probe's
424 // argument (x in print(x)) may point to.
425 for _, label := range pts.Labels() {
426 name := labelString(label, lineMapping, prog)
427 if expected[name] > 0 {
433 // Report multiset difference:
435 for _, count := range expected {
438 e.errorf("value does not alias these expected labels: %s", join(expected))
442 for _, count := range surplus {
445 e.errorf("value may additionally alias these labels: %s", join(surplus))
452 func checkTypesExpectation(e *expectation, pts pointer.PointsToSet, typ types.Type) bool {
453 var expected typeutil.Map
454 var surplus typeutil.Map
456 for _, g := range e.types {
457 if g == types.Typ[types.Invalid] {
461 expected.Set(g, struct{}{})
464 if !pointer.CanHaveDynamicTypes(typ) {
465 e.errorf("@types expectation requires an interface- or reflect.Value-typed operand, got %s", typ)
469 // Find the set of types that the probe's
470 // argument (x in print(x)) may contain.
471 for _, T := range pts.DynamicTypes().Keys() {
472 if expected.At(T) != nil {
475 surplus.Set(T, struct{}{})
478 // Report set difference:
480 if expected.Len() > 0 {
482 e.errorf("interface cannot contain these types: %s", expected.KeysString())
484 if surplus.Len() > 0 {
486 e.errorf("interface may additionally contain these types: %s", surplus.KeysString())
491 var errOK = errors.New("OK")
493 func checkCallsExpectation(prog *ssa.Program, e *expectation, cg *callgraph.Graph) bool {
494 found := make(map[string]int)
495 err := callgraph.GraphVisitEdges(cg, func(edge *callgraph.Edge) error {
496 // Name-based matching is inefficient but it allows us to
497 // match functions whose names that would not appear in an
498 // index ("<root>") or which are not unique ("func@1.2").
499 if edge.Caller.Func.String() == e.args[0] {
500 calleeStr := edge.Callee.Func.String()
501 if calleeStr == e.args[1] {
502 return errOK // expectation satisfied; stop the search
512 e.errorf("didn't find any calls from %s", e.args[0])
514 e.errorf("found no call from %s to %s, but only to %s",
515 e.args[0], e.args[1], join(found))
519 func checkWarningExpectation(prog *ssa.Program, e *expectation, warnings []pointer.Warning) bool {
520 // TODO(adonovan): check the position part of the warning too?
521 re, err := regexp.Compile(e.args[0])
523 e.errorf("invalid regular expression in @warning expectation: %s", err.Error())
527 if len(warnings) == 0 {
528 e.errorf("@warning %q expectation, but no warnings", e.args[0])
532 for _, w := range warnings {
533 if re.MatchString(w.Message) {
538 e.errorf("@warning %q expectation not satisfied; found these warnings though:", e.args[0])
539 for _, w := range warnings {
540 fmt.Printf("%s: warning: %s\n", prog.Fset.Position(w.Pos), w.Message)
545 func TestInput(t *testing.T) {
547 t.Skip("skipping in short mode; this test requires tons of memory; https://golang.org/issue/14113")
551 wd, err := os.Getwd()
553 t.Errorf("os.Getwd: %s", err)
557 // 'go test' does a chdir so that relative paths in
558 // diagnostics no longer make sense relative to the invoking
559 // shell's cwd. We print a special marker so that Emacs can
560 // make sense of them.
561 fmt.Fprintf(os.Stderr, "Entering directory `%s'\n", wd)
563 for _, filename := range inputs {
564 content, err := ioutil.ReadFile(filename)
566 t.Errorf("couldn't read file '%s': %s", filename, err)
570 if !doOneInput(string(content), filename) {
579 // join joins the elements of multiset with " | "s.
580 func join(set map[string]int) string {
583 for name, count := range set {
584 for i := 0; i < count; i++ {
587 buf.WriteString(name)
593 // split returns the list of sep-delimited non-empty strings in s.
594 func split(s, sep string) (r []string) {
595 for _, elem := range strings.Split(s, sep) {
596 elem = strings.TrimSpace(elem)