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