--- /dev/null
+// Copyright 2014 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package analysis performs type and pointer analysis
+// and generates mark-up for the Go source view.
+//
+// The Run method populates a Result object by running type and
+// (optionally) pointer analysis. The Result object is thread-safe
+// and at all times may be accessed by a serving thread, even as it is
+// progressively populated as analysis facts are derived.
+//
+// The Result is a mapping from each godoc file URL
+// (e.g. /src/fmt/print.go) to information about that file. The
+// information is a list of HTML markup links and a JSON array of
+// structured data values. Some of the links call client-side
+// JavaScript functions that index this array.
+//
+// The analysis computes mark-up for the following relations:
+//
+// IMPORTS: for each ast.ImportSpec, the package that it denotes.
+//
+// RESOLUTION: for each ast.Ident, its kind and type, and the location
+// of its definition.
+//
+// METHOD SETS, IMPLEMENTS: for each ast.Ident defining a named type,
+// its method-set, the set of interfaces it implements or is
+// implemented by, and its size/align values.
+//
+// CALLERS, CALLEES: for each function declaration ('func' token), its
+// callers, and for each call-site ('(' token), its callees.
+//
+// CALLGRAPH: the package docs include an interactive viewer for the
+// intra-package call graph of "fmt".
+//
+// CHANNEL PEERS: for each channel operation make/<-/close, the set of
+// other channel ops that alias the same channel(s).
+//
+// ERRORS: for each locus of a frontend (scanner/parser/type) error, the
+// location is highlighted in red and hover text provides the compiler
+// error message.
+//
+package analysis // import "golang.org/x/tools/godoc/analysis"
+
+import (
+ "fmt"
+ "go/build"
+ "go/scanner"
+ "go/token"
+ "go/types"
+ "html"
+ "io"
+ "log"
+ "os"
+ "path/filepath"
+ "sort"
+ "strings"
+ "sync"
+
+ "golang.org/x/tools/go/loader"
+ "golang.org/x/tools/go/pointer"
+ "golang.org/x/tools/go/ssa"
+ "golang.org/x/tools/go/ssa/ssautil"
+)
+
+// -- links ------------------------------------------------------------
+
+// A Link is an HTML decoration of the bytes [Start, End) of a file.
+// Write is called before/after those bytes to emit the mark-up.
+type Link interface {
+ Start() int
+ End() int
+ Write(w io.Writer, _ int, start bool) // the godoc.LinkWriter signature
+}
+
+// An <a> element.
+type aLink struct {
+ start, end int // =godoc.Segment
+ title string // hover text
+ onclick string // JS code (NB: trusted)
+ href string // URL (NB: trusted)
+}
+
+func (a aLink) Start() int { return a.start }
+func (a aLink) End() int { return a.end }
+func (a aLink) Write(w io.Writer, _ int, start bool) {
+ if start {
+ fmt.Fprintf(w, `<a title='%s'`, html.EscapeString(a.title))
+ if a.onclick != "" {
+ fmt.Fprintf(w, ` onclick='%s'`, html.EscapeString(a.onclick))
+ }
+ if a.href != "" {
+ // TODO(adonovan): I think that in principle, a.href must first be
+ // url.QueryEscape'd, but if I do that, a leading slash becomes "%2F",
+ // which causes the browser to treat the path as relative, not absolute.
+ // WTF?
+ fmt.Fprintf(w, ` href='%s'`, html.EscapeString(a.href))
+ }
+ fmt.Fprintf(w, ">")
+ } else {
+ fmt.Fprintf(w, "</a>")
+ }
+}
+
+// An <a class='error'> element.
+type errorLink struct {
+ start int
+ msg string
+}
+
+func (e errorLink) Start() int { return e.start }
+func (e errorLink) End() int { return e.start + 1 }
+
+func (e errorLink) Write(w io.Writer, _ int, start bool) {
+ // <span> causes havoc, not sure why, so use <a>.
+ if start {
+ fmt.Fprintf(w, `<a class='error' title='%s'>`, html.EscapeString(e.msg))
+ } else {
+ fmt.Fprintf(w, "</a>")
+ }
+}
+
+// -- fileInfo ---------------------------------------------------------
+
+// FileInfo holds analysis information for the source file view.
+// Clients must not mutate it.
+type FileInfo struct {
+ Data []interface{} // JSON serializable values
+ Links []Link // HTML link markup
+}
+
+// A fileInfo is the server's store of hyperlinks and JSON data for a
+// particular file.
+type fileInfo struct {
+ mu sync.Mutex
+ data []interface{} // JSON objects
+ links []Link
+ sorted bool
+ hasErrors bool // TODO(adonovan): surface this in the UI
+}
+
+// addLink adds a link to the Go source file fi.
+func (fi *fileInfo) addLink(link Link) {
+ fi.mu.Lock()
+ fi.links = append(fi.links, link)
+ fi.sorted = false
+ if _, ok := link.(errorLink); ok {
+ fi.hasErrors = true
+ }
+ fi.mu.Unlock()
+}
+
+// addData adds the structured value x to the JSON data for the Go
+// source file fi. Its index is returned.
+func (fi *fileInfo) addData(x interface{}) int {
+ fi.mu.Lock()
+ index := len(fi.data)
+ fi.data = append(fi.data, x)
+ fi.mu.Unlock()
+ return index
+}
+
+// get returns the file info in external form.
+// Callers must not mutate its fields.
+func (fi *fileInfo) get() FileInfo {
+ var r FileInfo
+ // Copy slices, to avoid races.
+ fi.mu.Lock()
+ r.Data = append(r.Data, fi.data...)
+ if !fi.sorted {
+ sort.Sort(linksByStart(fi.links))
+ fi.sorted = true
+ }
+ r.Links = append(r.Links, fi.links...)
+ fi.mu.Unlock()
+ return r
+}
+
+// PackageInfo holds analysis information for the package view.
+// Clients must not mutate it.
+type PackageInfo struct {
+ CallGraph []*PCGNodeJSON
+ CallGraphIndex map[string]int
+ Types []*TypeInfoJSON
+}
+
+type pkgInfo struct {
+ mu sync.Mutex
+ callGraph []*PCGNodeJSON
+ callGraphIndex map[string]int // keys are (*ssa.Function).RelString()
+ types []*TypeInfoJSON // type info for exported types
+}
+
+func (pi *pkgInfo) setCallGraph(callGraph []*PCGNodeJSON, callGraphIndex map[string]int) {
+ pi.mu.Lock()
+ pi.callGraph = callGraph
+ pi.callGraphIndex = callGraphIndex
+ pi.mu.Unlock()
+}
+
+func (pi *pkgInfo) addType(t *TypeInfoJSON) {
+ pi.mu.Lock()
+ pi.types = append(pi.types, t)
+ pi.mu.Unlock()
+}
+
+// get returns the package info in external form.
+// Callers must not mutate its fields.
+func (pi *pkgInfo) get() PackageInfo {
+ var r PackageInfo
+ // Copy slices, to avoid races.
+ pi.mu.Lock()
+ r.CallGraph = append(r.CallGraph, pi.callGraph...)
+ r.CallGraphIndex = pi.callGraphIndex
+ r.Types = append(r.Types, pi.types...)
+ pi.mu.Unlock()
+ return r
+}
+
+// -- Result -----------------------------------------------------------
+
+// Result contains the results of analysis.
+// The result contains a mapping from filenames to a set of HTML links
+// and JavaScript data referenced by the links.
+type Result struct {
+ mu sync.Mutex // guards maps (but not their contents)
+ status string // global analysis status
+ fileInfos map[string]*fileInfo // keys are godoc file URLs
+ pkgInfos map[string]*pkgInfo // keys are import paths
+}
+
+// fileInfo returns the fileInfo for the specified godoc file URL,
+// constructing it as needed. Thread-safe.
+func (res *Result) fileInfo(url string) *fileInfo {
+ res.mu.Lock()
+ fi, ok := res.fileInfos[url]
+ if !ok {
+ if res.fileInfos == nil {
+ res.fileInfos = make(map[string]*fileInfo)
+ }
+ fi = new(fileInfo)
+ res.fileInfos[url] = fi
+ }
+ res.mu.Unlock()
+ return fi
+}
+
+// Status returns a human-readable description of the current analysis status.
+func (res *Result) Status() string {
+ res.mu.Lock()
+ defer res.mu.Unlock()
+ return res.status
+}
+
+func (res *Result) setStatusf(format string, args ...interface{}) {
+ res.mu.Lock()
+ res.status = fmt.Sprintf(format, args...)
+ log.Printf(format, args...)
+ res.mu.Unlock()
+}
+
+// FileInfo returns new slices containing opaque JSON values and the
+// HTML link markup for the specified godoc file URL. Thread-safe.
+// Callers must not mutate the elements.
+// It returns "zero" if no data is available.
+//
+func (res *Result) FileInfo(url string) (fi FileInfo) {
+ return res.fileInfo(url).get()
+}
+
+// pkgInfo returns the pkgInfo for the specified import path,
+// constructing it as needed. Thread-safe.
+func (res *Result) pkgInfo(importPath string) *pkgInfo {
+ res.mu.Lock()
+ pi, ok := res.pkgInfos[importPath]
+ if !ok {
+ if res.pkgInfos == nil {
+ res.pkgInfos = make(map[string]*pkgInfo)
+ }
+ pi = new(pkgInfo)
+ res.pkgInfos[importPath] = pi
+ }
+ res.mu.Unlock()
+ return pi
+}
+
+// PackageInfo returns new slices of JSON values for the callgraph and
+// type info for the specified package. Thread-safe.
+// Callers must not mutate its fields.
+// PackageInfo returns "zero" if no data is available.
+//
+func (res *Result) PackageInfo(importPath string) PackageInfo {
+ return res.pkgInfo(importPath).get()
+}
+
+// -- analysis ---------------------------------------------------------
+
+type analysis struct {
+ result *Result
+ prog *ssa.Program
+ ops []chanOp // all channel ops in program
+ allNamed []*types.Named // all "defined" (formerly "named") types in the program
+ ptaConfig pointer.Config
+ path2url map[string]string // maps openable path to godoc file URL (/src/fmt/print.go)
+ pcgs map[*ssa.Package]*packageCallGraph
+}
+
+// fileAndOffset returns the file and offset for a given pos.
+func (a *analysis) fileAndOffset(pos token.Pos) (fi *fileInfo, offset int) {
+ return a.fileAndOffsetPosn(a.prog.Fset.Position(pos))
+}
+
+// fileAndOffsetPosn returns the file and offset for a given position.
+func (a *analysis) fileAndOffsetPosn(posn token.Position) (fi *fileInfo, offset int) {
+ url := a.path2url[posn.Filename]
+ return a.result.fileInfo(url), posn.Offset
+}
+
+// posURL returns the URL of the source extent [pos, pos+len).
+func (a *analysis) posURL(pos token.Pos, len int) string {
+ if pos == token.NoPos {
+ return ""
+ }
+ posn := a.prog.Fset.Position(pos)
+ url := a.path2url[posn.Filename]
+ return fmt.Sprintf("%s?s=%d:%d#L%d",
+ url, posn.Offset, posn.Offset+len, posn.Line)
+}
+
+// ----------------------------------------------------------------------
+
+// Run runs program analysis and computes the resulting markup,
+// populating *result in a thread-safe manner, first with type
+// information then later with pointer analysis information if
+// enabled by the pta flag.
+//
+func Run(pta bool, result *Result) {
+ conf := loader.Config{
+ AllowErrors: true,
+ }
+
+ // Silence the default error handler.
+ // Don't print all errors; we'll report just
+ // one per errant package later.
+ conf.TypeChecker.Error = func(e error) {}
+
+ var roots, args []string // roots[i] ends with os.PathSeparator
+
+ // Enumerate packages in $GOROOT.
+ root := filepath.Join(build.Default.GOROOT, "src") + string(os.PathSeparator)
+ roots = append(roots, root)
+ args = allPackages(root)
+ log.Printf("GOROOT=%s: %s\n", root, args)
+
+ // Enumerate packages in $GOPATH.
+ for i, dir := range filepath.SplitList(build.Default.GOPATH) {
+ root := filepath.Join(dir, "src") + string(os.PathSeparator)
+ roots = append(roots, root)
+ pkgs := allPackages(root)
+ log.Printf("GOPATH[%d]=%s: %s\n", i, root, pkgs)
+ args = append(args, pkgs...)
+ }
+
+ // Uncomment to make startup quicker during debugging.
+ //args = []string{"golang.org/x/tools/cmd/godoc"}
+ //args = []string{"fmt"}
+
+ if _, err := conf.FromArgs(args, true); err != nil {
+ // TODO(adonovan): degrade gracefully, not fail totally.
+ // (The crippling case is a parse error in an external test file.)
+ result.setStatusf("Analysis failed: %s.", err) // import error
+ return
+ }
+
+ result.setStatusf("Loading and type-checking packages...")
+ iprog, err := conf.Load()
+ if iprog != nil {
+ // Report only the first error of each package.
+ for _, info := range iprog.AllPackages {
+ for _, err := range info.Errors {
+ fmt.Fprintln(os.Stderr, err)
+ break
+ }
+ }
+ log.Printf("Loaded %d packages.", len(iprog.AllPackages))
+ }
+ if err != nil {
+ result.setStatusf("Loading failed: %s.\n", err)
+ return
+ }
+
+ // Create SSA-form program representation.
+ // Only the transitively error-free packages are used.
+ prog := ssautil.CreateProgram(iprog, ssa.GlobalDebug)
+
+ // Create a "testmain" package for each package with tests.
+ for _, pkg := range prog.AllPackages() {
+ if testmain := prog.CreateTestMainPackage(pkg); testmain != nil {
+ log.Printf("Adding tests for %s", pkg.Pkg.Path())
+ }
+ }
+
+ // Build SSA code for bodies of all functions in the whole program.
+ result.setStatusf("Constructing SSA form...")
+ prog.Build()
+ log.Print("SSA construction complete")
+
+ a := analysis{
+ result: result,
+ prog: prog,
+ pcgs: make(map[*ssa.Package]*packageCallGraph),
+ }
+
+ // Build a mapping from openable filenames to godoc file URLs,
+ // i.e. "/src/" plus path relative to GOROOT/src or GOPATH[i]/src.
+ a.path2url = make(map[string]string)
+ for _, info := range iprog.AllPackages {
+ nextfile:
+ for _, f := range info.Files {
+ if f.Pos() == 0 {
+ continue // e.g. files generated by cgo
+ }
+ abs := iprog.Fset.File(f.Pos()).Name()
+ // Find the root to which this file belongs.
+ for _, root := range roots {
+ rel := strings.TrimPrefix(abs, root)
+ if len(rel) < len(abs) {
+ a.path2url[abs] = "/src/" + filepath.ToSlash(rel)
+ continue nextfile
+ }
+ }
+
+ log.Printf("Can't locate file %s (package %q) beneath any root",
+ abs, info.Pkg.Path())
+ }
+ }
+
+ // Add links for scanner, parser, type-checker errors.
+ // TODO(adonovan): fix: these links can overlap with
+ // identifier markup, causing the renderer to emit some
+ // characters twice.
+ errors := make(map[token.Position][]string)
+ for _, info := range iprog.AllPackages {
+ for _, err := range info.Errors {
+ switch err := err.(type) {
+ case types.Error:
+ posn := a.prog.Fset.Position(err.Pos)
+ errors[posn] = append(errors[posn], err.Msg)
+ case scanner.ErrorList:
+ for _, e := range err {
+ errors[e.Pos] = append(errors[e.Pos], e.Msg)
+ }
+ default:
+ log.Printf("Package %q has error (%T) without position: %v\n",
+ info.Pkg.Path(), err, err)
+ }
+ }
+ }
+ for posn, errs := range errors {
+ fi, offset := a.fileAndOffsetPosn(posn)
+ fi.addLink(errorLink{
+ start: offset,
+ msg: strings.Join(errs, "\n"),
+ })
+ }
+
+ // ---------- type-based analyses ----------
+
+ // Compute the all-pairs IMPLEMENTS relation.
+ // Collect all named types, even local types
+ // (which can have methods via promotion)
+ // and the built-in "error".
+ errorType := types.Universe.Lookup("error").Type().(*types.Named)
+ a.allNamed = append(a.allNamed, errorType)
+ for _, info := range iprog.AllPackages {
+ for _, obj := range info.Defs {
+ if obj, ok := obj.(*types.TypeName); ok {
+ if named, ok := obj.Type().(*types.Named); ok {
+ a.allNamed = append(a.allNamed, named)
+ }
+ }
+ }
+ }
+ log.Print("Computing implements relation...")
+ facts := computeImplements(&a.prog.MethodSets, a.allNamed)
+
+ // Add the type-based analysis results.
+ log.Print("Extracting type info...")
+ for _, info := range iprog.AllPackages {
+ a.doTypeInfo(info, facts)
+ }
+
+ a.visitInstrs(pta)
+
+ result.setStatusf("Type analysis complete.")
+
+ if pta {
+ mainPkgs := ssautil.MainPackages(prog.AllPackages())
+ log.Print("Transitively error-free main packages: ", mainPkgs)
+ a.pointer(mainPkgs)
+ }
+}
+
+// visitInstrs visits all SSA instructions in the program.
+func (a *analysis) visitInstrs(pta bool) {
+ log.Print("Visit instructions...")
+ for fn := range ssautil.AllFunctions(a.prog) {
+ for _, b := range fn.Blocks {
+ for _, instr := range b.Instrs {
+ // CALLEES (static)
+ // (Dynamic calls require pointer analysis.)
+ //
+ // We use the SSA representation to find the static callee,
+ // since in many cases it does better than the
+ // types.Info.{Refs,Selection} information. For example:
+ //
+ // defer func(){}() // static call to anon function
+ // f := func(){}; f() // static call to anon function
+ // f := fmt.Println; f() // static call to named function
+ //
+ // The downside is that we get no static callee information
+ // for packages that (transitively) contain errors.
+ if site, ok := instr.(ssa.CallInstruction); ok {
+ if callee := site.Common().StaticCallee(); callee != nil {
+ // TODO(adonovan): callgraph: elide wrappers.
+ // (Do static calls ever go to wrappers?)
+ if site.Common().Pos() != token.NoPos {
+ a.addCallees(site, []*ssa.Function{callee})
+ }
+ }
+ }
+
+ if !pta {
+ continue
+ }
+
+ // CHANNEL PEERS
+ // Collect send/receive/close instructions in the whole ssa.Program.
+ for _, op := range chanOps(instr) {
+ a.ops = append(a.ops, op)
+ a.ptaConfig.AddQuery(op.ch) // add channel ssa.Value to PTA query
+ }
+ }
+ }
+ }
+ log.Print("Visit instructions complete")
+}
+
+// pointer runs the pointer analysis.
+func (a *analysis) pointer(mainPkgs []*ssa.Package) {
+ // Run the pointer analysis and build the complete callgraph.
+ a.ptaConfig.Mains = mainPkgs
+ a.ptaConfig.BuildCallGraph = true
+ a.ptaConfig.Reflection = false // (for now)
+
+ a.result.setStatusf("Pointer analysis running...")
+
+ ptares, err := pointer.Analyze(&a.ptaConfig)
+ if err != nil {
+ // If this happens, it indicates a bug.
+ a.result.setStatusf("Pointer analysis failed: %s.", err)
+ return
+ }
+ log.Print("Pointer analysis complete.")
+
+ // Add the results of pointer analysis.
+
+ a.result.setStatusf("Computing channel peers...")
+ a.doChannelPeers(ptares.Queries)
+ a.result.setStatusf("Computing dynamic call graph edges...")
+ a.doCallgraph(ptares.CallGraph)
+
+ a.result.setStatusf("Analysis complete.")
+}
+
+type linksByStart []Link
+
+func (a linksByStart) Less(i, j int) bool { return a[i].Start() < a[j].Start() }
+func (a linksByStart) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a linksByStart) Len() int { return len(a) }
+
+// allPackages returns a new sorted slice of all packages beneath the
+// specified package root directory, e.g. $GOROOT/src or $GOPATH/src.
+// Derived from from go/ssa/stdlib_test.go
+// root must end with os.PathSeparator.
+//
+// TODO(adonovan): use buildutil.AllPackages when the tree thaws.
+func allPackages(root string) []string {
+ var pkgs []string
+ filepath.Walk(root, func(path string, info os.FileInfo, err error) error {
+ if info == nil {
+ return nil // non-existent root directory?
+ }
+ if !info.IsDir() {
+ return nil // not a directory
+ }
+ // Prune the search if we encounter any of these names:
+ base := filepath.Base(path)
+ if base == "testdata" || strings.HasPrefix(base, ".") {
+ return filepath.SkipDir
+ }
+ pkg := filepath.ToSlash(strings.TrimPrefix(path, root))
+ switch pkg {
+ case "builtin":
+ return filepath.SkipDir
+ case "":
+ return nil // ignore root of tree
+ }
+ pkgs = append(pkgs, pkg)
+ return nil
+ })
+ return pkgs
+}
projects / dotfiles / .git / blobdiff