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 5// No testdata on Android. 6 7// +build !android 8 9package pointer_test 10 11// This test uses 'expectation' comments embedded within testdata/*.go 12// files to specify the expected pointer analysis behaviour. 13// See below for grammar. 14 15import ( 16 "bytes" 17 "errors" 18 "fmt" 19 "go/token" 20 "go/types" 21 "io/ioutil" 22 "os" 23 "regexp" 24 "strconv" 25 "strings" 26 "testing" 27 28 "golang.org/x/tools/go/callgraph" 29 "golang.org/x/tools/go/loader" 30 "golang.org/x/tools/go/pointer" 31 "golang.org/x/tools/go/ssa" 32 "golang.org/x/tools/go/ssa/ssautil" 33 "golang.org/x/tools/go/types/typeutil" 34) 35 36var inputs = []string{ 37 "testdata/a_test.go", 38 "testdata/another.go", 39 "testdata/arrayreflect.go", 40 "testdata/arrays.go", 41 "testdata/channels.go", 42 "testdata/chanreflect.go", 43 "testdata/context.go", 44 "testdata/conv.go", 45 "testdata/extended.go", 46 "testdata/finalizer.go", 47 "testdata/flow.go", 48 "testdata/fmtexcerpt.go", 49 "testdata/func.go", 50 "testdata/funcreflect.go", 51 "testdata/hello.go", // NB: causes spurious failure of HVN cross-check 52 "testdata/interfaces.go", 53 "testdata/issue9002.go", 54 "testdata/mapreflect.go", 55 "testdata/maps.go", 56 "testdata/panic.go", 57 "testdata/recur.go", 58 "testdata/reflect.go", 59 "testdata/rtti.go", 60 "testdata/structreflect.go", 61 "testdata/structs.go", 62 // "testdata/timer.go", // TODO(adonovan): fix broken assumptions about runtime timers 63} 64 65// Expectation grammar: 66// 67// @calls f -> g 68// 69// A 'calls' expectation asserts that edge (f, g) appears in the 70// callgraph. f and g are notated as per Function.String(), which 71// may contain spaces (e.g. promoted method in anon struct). 72// 73// @pointsto a | b | c 74// 75// A 'pointsto' expectation asserts that the points-to set of its 76// operand contains exactly the set of labels {a,b,c} notated as per 77// labelString. 78// 79// A 'pointsto' expectation must appear on the same line as a 80// print(x) statement; the expectation's operand is x. 81// 82// If one of the strings is "...", the expectation asserts that the 83// points-to set at least the other labels. 84// 85// We use '|' because label names may contain spaces, e.g. methods 86// of anonymous structs. 87// 88// From a theoretical perspective, concrete types in interfaces are 89// labels too, but they are represented differently and so have a 90// different expectation, @types, below. 91// 92// @types t | u | v 93// 94// A 'types' expectation asserts that the set of possible dynamic 95// types of its interface operand is exactly {t,u,v}, notated per 96// go/types.Type.String(). In other words, it asserts that the type 97// component of the interface may point to that set of concrete type 98// literals. It also works for reflect.Value, though the types 99// needn't be concrete in that case. 100// 101// A 'types' expectation must appear on the same line as a 102// print(x) statement; the expectation's operand is x. 103// 104// If one of the strings is "...", the expectation asserts that the 105// interface's type may point to at least the other types. 106// 107// We use '|' because type names may contain spaces. 108// 109// @warning "regexp" 110// 111// A 'warning' expectation asserts that the analysis issues a 112// warning that matches the regular expression within the string 113// literal. 114// 115// @line id 116// 117// A line directive associates the name "id" with the current 118// file:line. The string form of labels will use this id instead of 119// a file:line, making @pointsto expectations more robust against 120// perturbations in the source file. 121// (NB, anon functions still include line numbers.) 122// 123type expectation struct { 124 kind string // "pointsto" | "pointstoquery" | "types" | "calls" | "warning" 125 filename string 126 linenum int // source line number, 1-based 127 args []string 128 query string // extended query 129 extended *pointer.Pointer // extended query pointer 130 types []types.Type // for types 131} 132 133func (e *expectation) String() string { 134 return fmt.Sprintf("@%s[%s]", e.kind, strings.Join(e.args, " | ")) 135} 136 137func (e *expectation) errorf(format string, args ...interface{}) { 138 fmt.Printf("%s:%d: ", e.filename, e.linenum) 139 fmt.Printf(format, args...) 140 fmt.Println() 141} 142 143func (e *expectation) needsProbe() bool { 144 return e.kind == "pointsto" || e.kind == "pointstoquery" || e.kind == "types" 145} 146 147// Find probe (call to print(x)) of same source file/line as expectation. 148func findProbe(prog *ssa.Program, probes map[*ssa.CallCommon]bool, queries map[ssa.Value]pointer.Pointer, e *expectation) (site *ssa.CallCommon, pts pointer.PointsToSet) { 149 for call := range probes { 150 pos := prog.Fset.Position(call.Pos()) 151 if pos.Line == e.linenum && pos.Filename == e.filename { 152 // TODO(adonovan): send this to test log (display only on failure). 153 // fmt.Printf("%s:%d: info: found probe for %s: %s\n", 154 // e.filename, e.linenum, e, p.arg0) // debugging 155 return call, queries[call.Args[0]].PointsTo() 156 } 157 } 158 return // e.g. analysis didn't reach this call 159} 160 161func doOneInput(input, filename string) bool { 162 var conf loader.Config 163 164 // Parsing. 165 f, err := conf.ParseFile(filename, input) 166 if err != nil { 167 fmt.Println(err) 168 return false 169 } 170 171 // Create single-file main package and import its dependencies. 172 conf.CreateFromFiles("main", f) 173 iprog, err := conf.Load() 174 if err != nil { 175 fmt.Println(err) 176 return false 177 } 178 mainPkgInfo := iprog.Created[0].Pkg 179 180 // SSA creation + building. 181 prog := ssautil.CreateProgram(iprog, ssa.SanityCheckFunctions) 182 prog.Build() 183 184 mainpkg := prog.Package(mainPkgInfo) 185 ptrmain := mainpkg // main package for the pointer analysis 186 if mainpkg.Func("main") == nil { 187 // No main function; assume it's a test. 188 ptrmain = prog.CreateTestMainPackage(mainpkg) 189 } 190 191 // Find all calls to the built-in print(x). Analytically, 192 // print is a no-op, but it's a convenient hook for testing 193 // the PTS of an expression, so our tests use it. 194 probes := make(map[*ssa.CallCommon]bool) 195 for fn := range ssautil.AllFunctions(prog) { 196 if fn.Pkg == mainpkg { 197 for _, b := range fn.Blocks { 198 for _, instr := range b.Instrs { 199 if instr, ok := instr.(ssa.CallInstruction); ok { 200 call := instr.Common() 201 if b, ok := call.Value.(*ssa.Builtin); ok && b.Name() == "print" && len(call.Args) == 1 { 202 probes[instr.Common()] = true 203 } 204 } 205 } 206 } 207 } 208 } 209 210 ok := true 211 212 lineMapping := make(map[string]string) // maps "file:line" to @line tag 213 214 // Parse expectations in this input. 215 var exps []*expectation 216 re := regexp.MustCompile("// *@([a-z]*) *(.*)$") 217 lines := strings.Split(input, "\n") 218 for linenum, line := range lines { 219 linenum++ // make it 1-based 220 if matches := re.FindAllStringSubmatch(line, -1); matches != nil { 221 match := matches[0] 222 kind, rest := match[1], match[2] 223 e := &expectation{kind: kind, filename: filename, linenum: linenum} 224 225 if kind == "line" { 226 if rest == "" { 227 ok = false 228 e.errorf("@%s expectation requires identifier", kind) 229 } else { 230 lineMapping[fmt.Sprintf("%s:%d", filename, linenum)] = rest 231 } 232 continue 233 } 234 235 if e.needsProbe() && !strings.Contains(line, "print(") { 236 ok = false 237 e.errorf("@%s expectation must follow call to print(x)", kind) 238 continue 239 } 240 241 switch kind { 242 case "pointsto": 243 e.args = split(rest, "|") 244 245 case "pointstoquery": 246 args := strings.SplitN(rest, " ", 2) 247 e.query = args[0] 248 e.args = split(args[1], "|") 249 case "types": 250 for _, typstr := range split(rest, "|") { 251 var t types.Type = types.Typ[types.Invalid] // means "..." 252 if typstr != "..." { 253 tv, err := types.Eval(prog.Fset, mainpkg.Pkg, f.Pos(), typstr) 254 if err != nil { 255 ok = false 256 // Don't print err since its location is bad. 257 e.errorf("'%s' is not a valid type: %s", typstr, err) 258 continue 259 } 260 t = tv.Type 261 } 262 e.types = append(e.types, t) 263 } 264 265 case "calls": 266 e.args = split(rest, "->") 267 // TODO(adonovan): eagerly reject the 268 // expectation if fn doesn't denote 269 // existing function, rather than fail 270 // the expectation after analysis. 271 if len(e.args) != 2 { 272 ok = false 273 e.errorf("@calls expectation wants 'caller -> callee' arguments") 274 continue 275 } 276 277 case "warning": 278 lit, err := strconv.Unquote(strings.TrimSpace(rest)) 279 if err != nil { 280 ok = false 281 e.errorf("couldn't parse @warning operand: %s", err.Error()) 282 continue 283 } 284 e.args = append(e.args, lit) 285 286 default: 287 ok = false 288 e.errorf("unknown expectation kind: %s", e) 289 continue 290 } 291 exps = append(exps, e) 292 } 293 } 294 295 var log bytes.Buffer 296 fmt.Fprintf(&log, "Input: %s\n", filename) 297 298 // Run the analysis. 299 config := &pointer.Config{ 300 Reflection: true, 301 BuildCallGraph: true, 302 Mains: []*ssa.Package{ptrmain}, 303 Log: &log, 304 } 305probeLoop: 306 for probe := range probes { 307 v := probe.Args[0] 308 pos := prog.Fset.Position(probe.Pos()) 309 for _, e := range exps { 310 if e.linenum == pos.Line && e.filename == pos.Filename && e.kind == "pointstoquery" { 311 var err error 312 e.extended, err = config.AddExtendedQuery(v, e.query) 313 if err != nil { 314 panic(err) 315 } 316 continue probeLoop 317 } 318 } 319 if pointer.CanPoint(v.Type()) { 320 config.AddQuery(v) 321 } 322 } 323 324 // Print the log is there was an error or a panic. 325 complete := false 326 defer func() { 327 if !complete || !ok { 328 log.WriteTo(os.Stderr) 329 } 330 }() 331 332 result, err := pointer.Analyze(config) 333 if err != nil { 334 panic(err) // internal error in pointer analysis 335 } 336 337 // Check the expectations. 338 for _, e := range exps { 339 var call *ssa.CallCommon 340 var pts pointer.PointsToSet 341 var tProbe types.Type 342 if e.needsProbe() { 343 if call, pts = findProbe(prog, probes, result.Queries, e); call == nil { 344 ok = false 345 e.errorf("unreachable print() statement has expectation %s", e) 346 continue 347 } 348 if e.extended != nil { 349 pts = e.extended.PointsTo() 350 } 351 tProbe = call.Args[0].Type() 352 if !pointer.CanPoint(tProbe) { 353 ok = false 354 e.errorf("expectation on non-pointerlike operand: %s", tProbe) 355 continue 356 } 357 } 358 359 switch e.kind { 360 case "pointsto", "pointstoquery": 361 if !checkPointsToExpectation(e, pts, lineMapping, prog) { 362 ok = false 363 } 364 365 case "types": 366 if !checkTypesExpectation(e, pts, tProbe) { 367 ok = false 368 } 369 370 case "calls": 371 if !checkCallsExpectation(prog, e, result.CallGraph) { 372 ok = false 373 } 374 375 case "warning": 376 if !checkWarningExpectation(prog, e, result.Warnings) { 377 ok = false 378 } 379 } 380 } 381 382 complete = true 383 384 // ok = false // debugging: uncomment to always see log 385 386 return ok 387} 388 389func labelString(l *pointer.Label, lineMapping map[string]string, prog *ssa.Program) string { 390 // Functions and Globals need no pos suffix, 391 // nor do allocations in intrinsic operations 392 // (for which we'll print the function name). 393 switch l.Value().(type) { 394 case nil, *ssa.Function, *ssa.Global: 395 return l.String() 396 } 397 398 str := l.String() 399 if pos := l.Pos(); pos != token.NoPos { 400 // Append the position, using a @line tag instead of a line number, if defined. 401 posn := prog.Fset.Position(pos) 402 s := fmt.Sprintf("%s:%d", posn.Filename, posn.Line) 403 if tag, ok := lineMapping[s]; ok { 404 return fmt.Sprintf("%s@%s:%d", str, tag, posn.Column) 405 } 406 str = fmt.Sprintf("%s@%s", str, posn) 407 } 408 return str 409} 410 411func checkPointsToExpectation(e *expectation, pts pointer.PointsToSet, lineMapping map[string]string, prog *ssa.Program) bool { 412 expected := make(map[string]int) 413 surplus := make(map[string]int) 414 exact := true 415 for _, g := range e.args { 416 if g == "..." { 417 exact = false 418 continue 419 } 420 expected[g]++ 421 } 422 // Find the set of labels that the probe's 423 // argument (x in print(x)) may point to. 424 for _, label := range pts.Labels() { 425 name := labelString(label, lineMapping, prog) 426 if expected[name] > 0 { 427 expected[name]-- 428 } else if exact { 429 surplus[name]++ 430 } 431 } 432 // Report multiset difference: 433 ok := true 434 for _, count := range expected { 435 if count > 0 { 436 ok = false 437 e.errorf("value does not alias these expected labels: %s", join(expected)) 438 break 439 } 440 } 441 for _, count := range surplus { 442 if count > 0 { 443 ok = false 444 e.errorf("value may additionally alias these labels: %s", join(surplus)) 445 break 446 } 447 } 448 return ok 449} 450 451func checkTypesExpectation(e *expectation, pts pointer.PointsToSet, typ types.Type) bool { 452 var expected typeutil.Map 453 var surplus typeutil.Map 454 exact := true 455 for _, g := range e.types { 456 if g == types.Typ[types.Invalid] { 457 exact = false 458 continue 459 } 460 expected.Set(g, struct{}{}) 461 } 462 463 if !pointer.CanHaveDynamicTypes(typ) { 464 e.errorf("@types expectation requires an interface- or reflect.Value-typed operand, got %s", typ) 465 return false 466 } 467 468 // Find the set of types that the probe's 469 // argument (x in print(x)) may contain. 470 for _, T := range pts.DynamicTypes().Keys() { 471 if expected.At(T) != nil { 472 expected.Delete(T) 473 } else if exact { 474 surplus.Set(T, struct{}{}) 475 } 476 } 477 // Report set difference: 478 ok := true 479 if expected.Len() > 0 { 480 ok = false 481 e.errorf("interface cannot contain these types: %s", expected.KeysString()) 482 } 483 if surplus.Len() > 0 { 484 ok = false 485 e.errorf("interface may additionally contain these types: %s", surplus.KeysString()) 486 } 487 return ok 488} 489 490var errOK = errors.New("OK") 491 492func checkCallsExpectation(prog *ssa.Program, e *expectation, cg *callgraph.Graph) bool { 493 found := make(map[string]int) 494 err := callgraph.GraphVisitEdges(cg, func(edge *callgraph.Edge) error { 495 // Name-based matching is inefficient but it allows us to 496 // match functions whose names that would not appear in an 497 // index ("<root>") or which are not unique ("func@1.2"). 498 if edge.Caller.Func.String() == e.args[0] { 499 calleeStr := edge.Callee.Func.String() 500 if calleeStr == e.args[1] { 501 return errOK // expectation satisfied; stop the search 502 } 503 found[calleeStr]++ 504 } 505 return nil 506 }) 507 if err == errOK { 508 return true 509 } 510 if len(found) == 0 { 511 e.errorf("didn't find any calls from %s", e.args[0]) 512 } 513 e.errorf("found no call from %s to %s, but only to %s", 514 e.args[0], e.args[1], join(found)) 515 return false 516} 517 518func checkWarningExpectation(prog *ssa.Program, e *expectation, warnings []pointer.Warning) bool { 519 // TODO(adonovan): check the position part of the warning too? 520 re, err := regexp.Compile(e.args[0]) 521 if err != nil { 522 e.errorf("invalid regular expression in @warning expectation: %s", err.Error()) 523 return false 524 } 525 526 if len(warnings) == 0 { 527 e.errorf("@warning %q expectation, but no warnings", e.args[0]) 528 return false 529 } 530 531 for _, w := range warnings { 532 if re.MatchString(w.Message) { 533 return true 534 } 535 } 536 537 e.errorf("@warning %q expectation not satisfied; found these warnings though:", e.args[0]) 538 for _, w := range warnings { 539 fmt.Printf("%s: warning: %s\n", prog.Fset.Position(w.Pos), w.Message) 540 } 541 return false 542} 543 544func TestInput(t *testing.T) { 545 if testing.Short() { 546 t.Skip("skipping in short mode; this test requires tons of memory; https://golang.org/issue/14113") 547 } 548 ok := true 549 550 wd, err := os.Getwd() 551 if err != nil { 552 t.Errorf("os.Getwd: %s", err) 553 return 554 } 555 556 // 'go test' does a chdir so that relative paths in 557 // diagnostics no longer make sense relative to the invoking 558 // shell's cwd. We print a special marker so that Emacs can 559 // make sense of them. 560 fmt.Fprintf(os.Stderr, "Entering directory `%s'\n", wd) 561 562 for _, filename := range inputs { 563 content, err := ioutil.ReadFile(filename) 564 if err != nil { 565 t.Errorf("couldn't read file '%s': %s", filename, err) 566 continue 567 } 568 569 if !doOneInput(string(content), filename) { 570 ok = false 571 } 572 } 573 if !ok { 574 t.Fail() 575 } 576} 577 578// join joins the elements of multiset with " | "s. 579func join(set map[string]int) string { 580 var buf bytes.Buffer 581 sep := "" 582 for name, count := range set { 583 for i := 0; i < count; i++ { 584 buf.WriteString(sep) 585 sep = " | " 586 buf.WriteString(name) 587 } 588 } 589 return buf.String() 590} 591 592// split returns the list of sep-delimited non-empty strings in s. 593func split(s, sep string) (r []string) { 594 for _, elem := range strings.Split(s, sep) { 595 elem = strings.TrimSpace(elem) 596 if elem != "" { 597 r = append(r, elem) 598 } 599 } 600 return 601} 602