1 // Copyright 2014 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 // Package analysis performs type and pointer analysis
6 // and generates mark-up for the Go source view.
8 // The Run method populates a Result object by running type and
9 // (optionally) pointer analysis. The Result object is thread-safe
10 // and at all times may be accessed by a serving thread, even as it is
11 // progressively populated as analysis facts are derived.
13 // The Result is a mapping from each godoc file URL
14 // (e.g. /src/fmt/print.go) to information about that file. The
15 // information is a list of HTML markup links and a JSON array of
16 // structured data values. Some of the links call client-side
17 // JavaScript functions that index this array.
19 // The analysis computes mark-up for the following relations:
21 // IMPORTS: for each ast.ImportSpec, the package that it denotes.
23 // RESOLUTION: for each ast.Ident, its kind and type, and the location
26 // METHOD SETS, IMPLEMENTS: for each ast.Ident defining a named type,
27 // its method-set, the set of interfaces it implements or is
28 // implemented by, and its size/align values.
30 // CALLERS, CALLEES: for each function declaration ('func' token), its
31 // callers, and for each call-site ('(' token), its callees.
33 // CALLGRAPH: the package docs include an interactive viewer for the
34 // intra-package call graph of "fmt".
36 // CHANNEL PEERS: for each channel operation make/<-/close, the set of
37 // other channel ops that alias the same channel(s).
39 // ERRORS: for each locus of a frontend (scanner/parser/type) error, the
40 // location is highlighted in red and hover text provides the compiler
43 package analysis // import "golang.org/x/tools/godoc/analysis"
60 "golang.org/x/tools/go/loader"
61 "golang.org/x/tools/go/pointer"
62 "golang.org/x/tools/go/ssa"
63 "golang.org/x/tools/go/ssa/ssautil"
66 // -- links ------------------------------------------------------------
68 // A Link is an HTML decoration of the bytes [Start, End) of a file.
69 // Write is called before/after those bytes to emit the mark-up.
73 Write(w io.Writer, _ int, start bool) // the godoc.LinkWriter signature
78 start, end int // =godoc.Segment
79 title string // hover text
80 onclick string // JS code (NB: trusted)
81 href string // URL (NB: trusted)
84 func (a aLink) Start() int { return a.start }
85 func (a aLink) End() int { return a.end }
86 func (a aLink) Write(w io.Writer, _ int, start bool) {
88 fmt.Fprintf(w, `<a title='%s'`, html.EscapeString(a.title))
90 fmt.Fprintf(w, ` onclick='%s'`, html.EscapeString(a.onclick))
93 // TODO(adonovan): I think that in principle, a.href must first be
94 // url.QueryEscape'd, but if I do that, a leading slash becomes "%2F",
95 // which causes the browser to treat the path as relative, not absolute.
97 fmt.Fprintf(w, ` href='%s'`, html.EscapeString(a.href))
101 fmt.Fprintf(w, "</a>")
105 // An <a class='error'> element.
106 type errorLink struct {
111 func (e errorLink) Start() int { return e.start }
112 func (e errorLink) End() int { return e.start + 1 }
114 func (e errorLink) Write(w io.Writer, _ int, start bool) {
115 // <span> causes havoc, not sure why, so use <a>.
117 fmt.Fprintf(w, `<a class='error' title='%s'>`, html.EscapeString(e.msg))
119 fmt.Fprintf(w, "</a>")
123 // -- fileInfo ---------------------------------------------------------
125 // FileInfo holds analysis information for the source file view.
126 // Clients must not mutate it.
127 type FileInfo struct {
128 Data []interface{} // JSON serializable values
129 Links []Link // HTML link markup
132 // A fileInfo is the server's store of hyperlinks and JSON data for a
134 type fileInfo struct {
136 data []interface{} // JSON objects
139 hasErrors bool // TODO(adonovan): surface this in the UI
142 // addLink adds a link to the Go source file fi.
143 func (fi *fileInfo) addLink(link Link) {
145 fi.links = append(fi.links, link)
147 if _, ok := link.(errorLink); ok {
153 // addData adds the structured value x to the JSON data for the Go
154 // source file fi. Its index is returned.
155 func (fi *fileInfo) addData(x interface{}) int {
157 index := len(fi.data)
158 fi.data = append(fi.data, x)
163 // get returns the file info in external form.
164 // Callers must not mutate its fields.
165 func (fi *fileInfo) get() FileInfo {
167 // Copy slices, to avoid races.
169 r.Data = append(r.Data, fi.data...)
171 sort.Sort(linksByStart(fi.links))
174 r.Links = append(r.Links, fi.links...)
179 // PackageInfo holds analysis information for the package view.
180 // Clients must not mutate it.
181 type PackageInfo struct {
182 CallGraph []*PCGNodeJSON
183 CallGraphIndex map[string]int
184 Types []*TypeInfoJSON
187 type pkgInfo struct {
189 callGraph []*PCGNodeJSON
190 callGraphIndex map[string]int // keys are (*ssa.Function).RelString()
191 types []*TypeInfoJSON // type info for exported types
194 func (pi *pkgInfo) setCallGraph(callGraph []*PCGNodeJSON, callGraphIndex map[string]int) {
196 pi.callGraph = callGraph
197 pi.callGraphIndex = callGraphIndex
201 func (pi *pkgInfo) addType(t *TypeInfoJSON) {
203 pi.types = append(pi.types, t)
207 // get returns the package info in external form.
208 // Callers must not mutate its fields.
209 func (pi *pkgInfo) get() PackageInfo {
211 // Copy slices, to avoid races.
213 r.CallGraph = append(r.CallGraph, pi.callGraph...)
214 r.CallGraphIndex = pi.callGraphIndex
215 r.Types = append(r.Types, pi.types...)
220 // -- Result -----------------------------------------------------------
222 // Result contains the results of analysis.
223 // The result contains a mapping from filenames to a set of HTML links
224 // and JavaScript data referenced by the links.
226 mu sync.Mutex // guards maps (but not their contents)
227 status string // global analysis status
228 fileInfos map[string]*fileInfo // keys are godoc file URLs
229 pkgInfos map[string]*pkgInfo // keys are import paths
232 // fileInfo returns the fileInfo for the specified godoc file URL,
233 // constructing it as needed. Thread-safe.
234 func (res *Result) fileInfo(url string) *fileInfo {
236 fi, ok := res.fileInfos[url]
238 if res.fileInfos == nil {
239 res.fileInfos = make(map[string]*fileInfo)
242 res.fileInfos[url] = fi
248 // Status returns a human-readable description of the current analysis status.
249 func (res *Result) Status() string {
251 defer res.mu.Unlock()
255 func (res *Result) setStatusf(format string, args ...interface{}) {
257 res.status = fmt.Sprintf(format, args...)
258 log.Printf(format, args...)
262 // FileInfo returns new slices containing opaque JSON values and the
263 // HTML link markup for the specified godoc file URL. Thread-safe.
264 // Callers must not mutate the elements.
265 // It returns "zero" if no data is available.
267 func (res *Result) FileInfo(url string) (fi FileInfo) {
268 return res.fileInfo(url).get()
271 // pkgInfo returns the pkgInfo for the specified import path,
272 // constructing it as needed. Thread-safe.
273 func (res *Result) pkgInfo(importPath string) *pkgInfo {
275 pi, ok := res.pkgInfos[importPath]
277 if res.pkgInfos == nil {
278 res.pkgInfos = make(map[string]*pkgInfo)
281 res.pkgInfos[importPath] = pi
287 // PackageInfo returns new slices of JSON values for the callgraph and
288 // type info for the specified package. Thread-safe.
289 // Callers must not mutate its fields.
290 // PackageInfo returns "zero" if no data is available.
292 func (res *Result) PackageInfo(importPath string) PackageInfo {
293 return res.pkgInfo(importPath).get()
296 // -- analysis ---------------------------------------------------------
298 type analysis struct {
301 ops []chanOp // all channel ops in program
302 allNamed []*types.Named // all "defined" (formerly "named") types in the program
303 ptaConfig pointer.Config
304 path2url map[string]string // maps openable path to godoc file URL (/src/fmt/print.go)
305 pcgs map[*ssa.Package]*packageCallGraph
308 // fileAndOffset returns the file and offset for a given pos.
309 func (a *analysis) fileAndOffset(pos token.Pos) (fi *fileInfo, offset int) {
310 return a.fileAndOffsetPosn(a.prog.Fset.Position(pos))
313 // fileAndOffsetPosn returns the file and offset for a given position.
314 func (a *analysis) fileAndOffsetPosn(posn token.Position) (fi *fileInfo, offset int) {
315 url := a.path2url[posn.Filename]
316 return a.result.fileInfo(url), posn.Offset
319 // posURL returns the URL of the source extent [pos, pos+len).
320 func (a *analysis) posURL(pos token.Pos, len int) string {
321 if pos == token.NoPos {
324 posn := a.prog.Fset.Position(pos)
325 url := a.path2url[posn.Filename]
326 return fmt.Sprintf("%s?s=%d:%d#L%d",
327 url, posn.Offset, posn.Offset+len, posn.Line)
330 // ----------------------------------------------------------------------
332 // Run runs program analysis and computes the resulting markup,
333 // populating *result in a thread-safe manner, first with type
334 // information then later with pointer analysis information if
335 // enabled by the pta flag.
337 func Run(pta bool, result *Result) {
338 conf := loader.Config{
342 // Silence the default error handler.
343 // Don't print all errors; we'll report just
344 // one per errant package later.
345 conf.TypeChecker.Error = func(e error) {}
347 var roots, args []string // roots[i] ends with os.PathSeparator
349 // Enumerate packages in $GOROOT.
350 root := filepath.Join(build.Default.GOROOT, "src") + string(os.PathSeparator)
351 roots = append(roots, root)
352 args = allPackages(root)
353 log.Printf("GOROOT=%s: %s\n", root, args)
355 // Enumerate packages in $GOPATH.
356 for i, dir := range filepath.SplitList(build.Default.GOPATH) {
357 root := filepath.Join(dir, "src") + string(os.PathSeparator)
358 roots = append(roots, root)
359 pkgs := allPackages(root)
360 log.Printf("GOPATH[%d]=%s: %s\n", i, root, pkgs)
361 args = append(args, pkgs...)
364 // Uncomment to make startup quicker during debugging.
365 //args = []string{"golang.org/x/tools/cmd/godoc"}
366 //args = []string{"fmt"}
368 if _, err := conf.FromArgs(args, true); err != nil {
369 // TODO(adonovan): degrade gracefully, not fail totally.
370 // (The crippling case is a parse error in an external test file.)
371 result.setStatusf("Analysis failed: %s.", err) // import error
375 result.setStatusf("Loading and type-checking packages...")
376 iprog, err := conf.Load()
378 // Report only the first error of each package.
379 for _, info := range iprog.AllPackages {
380 for _, err := range info.Errors {
381 fmt.Fprintln(os.Stderr, err)
385 log.Printf("Loaded %d packages.", len(iprog.AllPackages))
388 result.setStatusf("Loading failed: %s.\n", err)
392 // Create SSA-form program representation.
393 // Only the transitively error-free packages are used.
394 prog := ssautil.CreateProgram(iprog, ssa.GlobalDebug)
396 // Create a "testmain" package for each package with tests.
397 for _, pkg := range prog.AllPackages() {
398 if testmain := prog.CreateTestMainPackage(pkg); testmain != nil {
399 log.Printf("Adding tests for %s", pkg.Pkg.Path())
403 // Build SSA code for bodies of all functions in the whole program.
404 result.setStatusf("Constructing SSA form...")
406 log.Print("SSA construction complete")
411 pcgs: make(map[*ssa.Package]*packageCallGraph),
414 // Build a mapping from openable filenames to godoc file URLs,
415 // i.e. "/src/" plus path relative to GOROOT/src or GOPATH[i]/src.
416 a.path2url = make(map[string]string)
417 for _, info := range iprog.AllPackages {
419 for _, f := range info.Files {
421 continue // e.g. files generated by cgo
423 abs := iprog.Fset.File(f.Pos()).Name()
424 // Find the root to which this file belongs.
425 for _, root := range roots {
426 rel := strings.TrimPrefix(abs, root)
427 if len(rel) < len(abs) {
428 a.path2url[abs] = "/src/" + filepath.ToSlash(rel)
433 log.Printf("Can't locate file %s (package %q) beneath any root",
434 abs, info.Pkg.Path())
438 // Add links for scanner, parser, type-checker errors.
439 // TODO(adonovan): fix: these links can overlap with
440 // identifier markup, causing the renderer to emit some
442 errors := make(map[token.Position][]string)
443 for _, info := range iprog.AllPackages {
444 for _, err := range info.Errors {
445 switch err := err.(type) {
447 posn := a.prog.Fset.Position(err.Pos)
448 errors[posn] = append(errors[posn], err.Msg)
449 case scanner.ErrorList:
450 for _, e := range err {
451 errors[e.Pos] = append(errors[e.Pos], e.Msg)
454 log.Printf("Package %q has error (%T) without position: %v\n",
455 info.Pkg.Path(), err, err)
459 for posn, errs := range errors {
460 fi, offset := a.fileAndOffsetPosn(posn)
461 fi.addLink(errorLink{
463 msg: strings.Join(errs, "\n"),
467 // ---------- type-based analyses ----------
469 // Compute the all-pairs IMPLEMENTS relation.
470 // Collect all named types, even local types
471 // (which can have methods via promotion)
472 // and the built-in "error".
473 errorType := types.Universe.Lookup("error").Type().(*types.Named)
474 a.allNamed = append(a.allNamed, errorType)
475 for _, info := range iprog.AllPackages {
476 for _, obj := range info.Defs {
477 if obj, ok := obj.(*types.TypeName); ok {
478 if named, ok := obj.Type().(*types.Named); ok {
479 a.allNamed = append(a.allNamed, named)
484 log.Print("Computing implements relation...")
485 facts := computeImplements(&a.prog.MethodSets, a.allNamed)
487 // Add the type-based analysis results.
488 log.Print("Extracting type info...")
489 for _, info := range iprog.AllPackages {
490 a.doTypeInfo(info, facts)
495 result.setStatusf("Type analysis complete.")
498 mainPkgs := ssautil.MainPackages(prog.AllPackages())
499 log.Print("Transitively error-free main packages: ", mainPkgs)
504 // visitInstrs visits all SSA instructions in the program.
505 func (a *analysis) visitInstrs(pta bool) {
506 log.Print("Visit instructions...")
507 for fn := range ssautil.AllFunctions(a.prog) {
508 for _, b := range fn.Blocks {
509 for _, instr := range b.Instrs {
511 // (Dynamic calls require pointer analysis.)
513 // We use the SSA representation to find the static callee,
514 // since in many cases it does better than the
515 // types.Info.{Refs,Selection} information. For example:
517 // defer func(){}() // static call to anon function
518 // f := func(){}; f() // static call to anon function
519 // f := fmt.Println; f() // static call to named function
521 // The downside is that we get no static callee information
522 // for packages that (transitively) contain errors.
523 if site, ok := instr.(ssa.CallInstruction); ok {
524 if callee := site.Common().StaticCallee(); callee != nil {
525 // TODO(adonovan): callgraph: elide wrappers.
526 // (Do static calls ever go to wrappers?)
527 if site.Common().Pos() != token.NoPos {
528 a.addCallees(site, []*ssa.Function{callee})
538 // Collect send/receive/close instructions in the whole ssa.Program.
539 for _, op := range chanOps(instr) {
540 a.ops = append(a.ops, op)
541 a.ptaConfig.AddQuery(op.ch) // add channel ssa.Value to PTA query
546 log.Print("Visit instructions complete")
549 // pointer runs the pointer analysis.
550 func (a *analysis) pointer(mainPkgs []*ssa.Package) {
551 // Run the pointer analysis and build the complete callgraph.
552 a.ptaConfig.Mains = mainPkgs
553 a.ptaConfig.BuildCallGraph = true
554 a.ptaConfig.Reflection = false // (for now)
556 a.result.setStatusf("Pointer analysis running...")
558 ptares, err := pointer.Analyze(&a.ptaConfig)
560 // If this happens, it indicates a bug.
561 a.result.setStatusf("Pointer analysis failed: %s.", err)
564 log.Print("Pointer analysis complete.")
566 // Add the results of pointer analysis.
568 a.result.setStatusf("Computing channel peers...")
569 a.doChannelPeers(ptares.Queries)
570 a.result.setStatusf("Computing dynamic call graph edges...")
571 a.doCallgraph(ptares.CallGraph)
573 a.result.setStatusf("Analysis complete.")
576 type linksByStart []Link
578 func (a linksByStart) Less(i, j int) bool { return a[i].Start() < a[j].Start() }
579 func (a linksByStart) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
580 func (a linksByStart) Len() int { return len(a) }
582 // allPackages returns a new sorted slice of all packages beneath the
583 // specified package root directory, e.g. $GOROOT/src or $GOPATH/src.
584 // Derived from from go/ssa/stdlib_test.go
585 // root must end with os.PathSeparator.
587 // TODO(adonovan): use buildutil.AllPackages when the tree thaws.
588 func allPackages(root string) []string {
590 filepath.Walk(root, func(path string, info os.FileInfo, err error) error {
592 return nil // non-existent root directory?
595 return nil // not a directory
597 // Prune the search if we encounter any of these names:
598 base := filepath.Base(path)
599 if base == "testdata" || strings.HasPrefix(base, ".") {
600 return filepath.SkipDir
602 pkg := filepath.ToSlash(strings.TrimPrefix(path, root))
605 return filepath.SkipDir
607 return nil // ignore root of tree
609 pkgs = append(pkgs, pkg)