.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/godoc/analysis/analysis.go

   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.
   4
   5 // Package analysis performs type and pointer analysis
   6 // and generates mark-up for the Go source view.
   7 //
   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.
  12 //
  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.
  18 //
  19 // The analysis computes mark-up for the following relations:
  20 //
  21 // IMPORTS: for each ast.ImportSpec, the package that it denotes.
  22 //
  23 // RESOLUTION: for each ast.Ident, its kind and type, and the location
  24 // of its definition.
  25 //
  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.
  29 //
  30 // CALLERS, CALLEES: for each function declaration ('func' token), its
  31 // callers, and for each call-site ('(' token), its callees.
  32 //
  33 // CALLGRAPH: the package docs include an interactive viewer for the
  34 // intra-package call graph of "fmt".
  35 //
  36 // CHANNEL PEERS: for each channel operation make/<-/close, the set of
  37 // other channel ops that alias the same channel(s).
  38 //
  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
  41 // error message.
  42 //
  43 package analysis // import "golang.org/x/tools/godoc/analysis"
  44
  45 import (
  46         "fmt"
  47         "go/build"
  48         "go/scanner"
  49         "go/token"
  50         "go/types"
  51         "html"
  52         "io"
  53         "log"
  54         "os"
  55         "path/filepath"
  56         "sort"
  57         "strings"
  58         "sync"
  59
  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"
  64 )
  65
  66 // -- links ------------------------------------------------------------
  67
  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.
  70 type Link interface {
  71         Start() int
  72         End() int
  73         Write(w io.Writer, _ int, start bool) // the godoc.LinkWriter signature
  74 }
  75
  76 // An <a> element.
  77 type aLink struct {
  78         start, end int    // =godoc.Segment
  79         title      string // hover text
  80         onclick    string // JS code (NB: trusted)
  81         href       string // URL     (NB: trusted)
  82 }
  83
  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) {
  87         if start {
  88                 fmt.Fprintf(w, `<a title='%s'`, html.EscapeString(a.title))
  89                 if a.onclick != "" {
  90                         fmt.Fprintf(w, ` onclick='%s'`, html.EscapeString(a.onclick))
  91                 }
  92                 if a.href != "" {
  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.
  96                         // WTF?
  97                         fmt.Fprintf(w, ` href='%s'`, html.EscapeString(a.href))
  98                 }
  99                 fmt.Fprintf(w, ">")
 100         } else {
 101                 fmt.Fprintf(w, "</a>")
 102         }
 103 }
 104
 105 // An <a class='error'> element.
 106 type errorLink struct {
 107         start int
 108         msg   string
 109 }
 110
 111 func (e errorLink) Start() int { return e.start }
 112 func (e errorLink) End() int   { return e.start + 1 }
 113
 114 func (e errorLink) Write(w io.Writer, _ int, start bool) {
 115         // <span> causes havoc, not sure why, so use <a>.
 116         if start {
 117                 fmt.Fprintf(w, `<a class='error' title='%s'>`, html.EscapeString(e.msg))
 118         } else {
 119                 fmt.Fprintf(w, "</a>")
 120         }
 121 }
 122
 123 // -- fileInfo ---------------------------------------------------------
 124
 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
 130 }
 131
 132 // A fileInfo is the server's store of hyperlinks and JSON data for a
 133 // particular file.
 134 type fileInfo struct {
 135         mu        sync.Mutex
 136         data      []interface{} // JSON objects
 137         links     []Link
 138         sorted    bool
 139         hasErrors bool // TODO(adonovan): surface this in the UI
 140 }
 141
 142 // addLink adds a link to the Go source file fi.
 143 func (fi *fileInfo) addLink(link Link) {
 144         fi.mu.Lock()
 145         fi.links = append(fi.links, link)
 146         fi.sorted = false
 147         if _, ok := link.(errorLink); ok {
 148                 fi.hasErrors = true
 149         }
 150         fi.mu.Unlock()
 151 }
 152
 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 {
 156         fi.mu.Lock()
 157         index := len(fi.data)
 158         fi.data = append(fi.data, x)
 159         fi.mu.Unlock()
 160         return index
 161 }
 162
 163 // get returns the file info in external form.
 164 // Callers must not mutate its fields.
 165 func (fi *fileInfo) get() FileInfo {
 166         var r FileInfo
 167         // Copy slices, to avoid races.
 168         fi.mu.Lock()
 169         r.Data = append(r.Data, fi.data...)
 170         if !fi.sorted {
 171                 sort.Sort(linksByStart(fi.links))
 172                 fi.sorted = true
 173         }
 174         r.Links = append(r.Links, fi.links...)
 175         fi.mu.Unlock()
 176         return r
 177 }
 178
 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
 185 }
 186
 187 type pkgInfo struct {
 188         mu             sync.Mutex
 189         callGraph      []*PCGNodeJSON
 190         callGraphIndex map[string]int  // keys are (*ssa.Function).RelString()
 191         types          []*TypeInfoJSON // type info for exported types
 192 }
 193
 194 func (pi *pkgInfo) setCallGraph(callGraph []*PCGNodeJSON, callGraphIndex map[string]int) {
 195         pi.mu.Lock()
 196         pi.callGraph = callGraph
 197         pi.callGraphIndex = callGraphIndex
 198         pi.mu.Unlock()
 199 }
 200
 201 func (pi *pkgInfo) addType(t *TypeInfoJSON) {
 202         pi.mu.Lock()
 203         pi.types = append(pi.types, t)
 204         pi.mu.Unlock()
 205 }
 206
 207 // get returns the package info in external form.
 208 // Callers must not mutate its fields.
 209 func (pi *pkgInfo) get() PackageInfo {
 210         var r PackageInfo
 211         // Copy slices, to avoid races.
 212         pi.mu.Lock()
 213         r.CallGraph = append(r.CallGraph, pi.callGraph...)
 214         r.CallGraphIndex = pi.callGraphIndex
 215         r.Types = append(r.Types, pi.types...)
 216         pi.mu.Unlock()
 217         return r
 218 }
 219
 220 // -- Result -----------------------------------------------------------
 221
 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.
 225 type Result struct {
 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
 230 }
 231
 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 {
 235         res.mu.Lock()
 236         fi, ok := res.fileInfos[url]
 237         if !ok {
 238                 if res.fileInfos == nil {
 239                         res.fileInfos = make(map[string]*fileInfo)
 240                 }
 241                 fi = new(fileInfo)
 242                 res.fileInfos[url] = fi
 243         }
 244         res.mu.Unlock()
 245         return fi
 246 }
 247
 248 // Status returns a human-readable description of the current analysis status.
 249 func (res *Result) Status() string {
 250         res.mu.Lock()
 251         defer res.mu.Unlock()
 252         return res.status
 253 }
 254
 255 func (res *Result) setStatusf(format string, args ...interface{}) {
 256         res.mu.Lock()
 257         res.status = fmt.Sprintf(format, args...)
 258         log.Printf(format, args...)
 259         res.mu.Unlock()
 260 }
 261
 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.
 266 //
 267 func (res *Result) FileInfo(url string) (fi FileInfo) {
 268         return res.fileInfo(url).get()
 269 }
 270
 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 {
 274         res.mu.Lock()
 275         pi, ok := res.pkgInfos[importPath]
 276         if !ok {
 277                 if res.pkgInfos == nil {
 278                         res.pkgInfos = make(map[string]*pkgInfo)
 279                 }
 280                 pi = new(pkgInfo)
 281                 res.pkgInfos[importPath] = pi
 282         }
 283         res.mu.Unlock()
 284         return pi
 285 }
 286
 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.
 291 //
 292 func (res *Result) PackageInfo(importPath string) PackageInfo {
 293         return res.pkgInfo(importPath).get()
 294 }
 295
 296 // -- analysis ---------------------------------------------------------
 297
 298 type analysis struct {
 299         result    *Result
 300         prog      *ssa.Program
 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
 306 }
 307
 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))
 311 }
 312
 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
 317 }
 318
 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 {
 322                 return ""
 323         }
 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)
 328 }
 329
 330 // ----------------------------------------------------------------------
 331
 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.
 336 //
 337 func Run(pta bool, result *Result) {
 338         conf := loader.Config{
 339                 AllowErrors: true,
 340         }
 341
 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) {}
 346
 347         var roots, args []string // roots[i] ends with os.PathSeparator
 348
 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)
 354
 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...)
 362         }
 363
 364         // Uncomment to make startup quicker during debugging.
 365         //args = []string{"golang.org/x/tools/cmd/godoc"}
 366         //args = []string{"fmt"}
 367
 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
 372                 return
 373         }
 374
 375         result.setStatusf("Loading and type-checking packages...")
 376         iprog, err := conf.Load()
 377         if iprog != nil {
 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)
 382                                 break
 383                         }
 384                 }
 385                 log.Printf("Loaded %d packages.", len(iprog.AllPackages))
 386         }
 387         if err != nil {
 388                 result.setStatusf("Loading failed: %s.\n", err)
 389                 return
 390         }
 391
 392         // Create SSA-form program representation.
 393         // Only the transitively error-free packages are used.
 394         prog := ssautil.CreateProgram(iprog, ssa.GlobalDebug)
 395
 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())
 400                 }
 401         }
 402
 403         // Build SSA code for bodies of all functions in the whole program.
 404         result.setStatusf("Constructing SSA form...")
 405         prog.Build()
 406         log.Print("SSA construction complete")
 407
 408         a := analysis{
 409                 result: result,
 410                 prog:   prog,
 411                 pcgs:   make(map[*ssa.Package]*packageCallGraph),
 412         }
 413
 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 {
 418         nextfile:
 419                 for _, f := range info.Files {
 420                         if f.Pos() == 0 {
 421                                 continue // e.g. files generated by cgo
 422                         }
 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)
 429                                         continue nextfile
 430                                 }
 431                         }
 432
 433                         log.Printf("Can't locate file %s (package %q) beneath any root",
 434                                 abs, info.Pkg.Path())
 435                 }
 436         }
 437
 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
 441         // characters twice.
 442         errors := make(map[token.Position][]string)
 443         for _, info := range iprog.AllPackages {
 444                 for _, err := range info.Errors {
 445                         switch err := err.(type) {
 446                         case types.Error:
 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)
 452                                 }
 453                         default:
 454                                 log.Printf("Package %q has error (%T) without position: %v\n",
 455                                         info.Pkg.Path(), err, err)
 456                         }
 457                 }
 458         }
 459         for posn, errs := range errors {
 460                 fi, offset := a.fileAndOffsetPosn(posn)
 461                 fi.addLink(errorLink{
 462                         start: offset,
 463                         msg:   strings.Join(errs, "\n"),
 464                 })
 465         }
 466
 467         // ---------- type-based analyses ----------
 468
 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)
 480                                 }
 481                         }
 482                 }
 483         }
 484         log.Print("Computing implements relation...")
 485         facts := computeImplements(&a.prog.MethodSets, a.allNamed)
 486
 487         // Add the type-based analysis results.
 488         log.Print("Extracting type info...")
 489         for _, info := range iprog.AllPackages {
 490                 a.doTypeInfo(info, facts)
 491         }
 492
 493         a.visitInstrs(pta)
 494
 495         result.setStatusf("Type analysis complete.")
 496
 497         if pta {
 498                 mainPkgs := ssautil.MainPackages(prog.AllPackages())
 499                 log.Print("Transitively error-free main packages: ", mainPkgs)
 500                 a.pointer(mainPkgs)
 501         }
 502 }
 503
 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 {
 510                                 // CALLEES (static)
 511                                 // (Dynamic calls require pointer analysis.)
 512                                 //
 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:
 516                                 //
 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
 520                                 //
 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})
 529                                                 }
 530                                         }
 531                                 }
 532
 533                                 if !pta {
 534                                         continue
 535                                 }
 536
 537                                 // CHANNEL PEERS
 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
 542                                 }
 543                         }
 544                 }
 545         }
 546         log.Print("Visit instructions complete")
 547 }
 548
 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)
 555
 556         a.result.setStatusf("Pointer analysis running...")
 557
 558         ptares, err := pointer.Analyze(&a.ptaConfig)
 559         if err != nil {
 560                 // If this happens, it indicates a bug.
 561                 a.result.setStatusf("Pointer analysis failed: %s.", err)
 562                 return
 563         }
 564         log.Print("Pointer analysis complete.")
 565
 566         // Add the results of pointer analysis.
 567
 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)
 572
 573         a.result.setStatusf("Analysis complete.")
 574 }
 575
 576 type linksByStart []Link
 577
 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) }
 581
 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.
 586 //
 587 // TODO(adonovan): use buildutil.AllPackages when the tree thaws.
 588 func allPackages(root string) []string {
 589         var pkgs []string
 590         filepath.Walk(root, func(path string, info os.FileInfo, err error) error {
 591                 if info == nil {
 592                         return nil // non-existent root directory?
 593                 }
 594                 if !info.IsDir() {
 595                         return nil // not a directory
 596                 }
 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
 601                 }
 602                 pkg := filepath.ToSlash(strings.TrimPrefix(path, root))
 603                 switch pkg {
 604                 case "builtin":
 605                         return filepath.SkipDir
 606                 case "":
 607                         return nil // ignore root of tree
 608                 }
 609                 pkgs = append(pkgs, pkg)
 610                 return nil
 611         })
 612         return pkgs
 613 }