.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/refactor/importgraph/graph.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 importgraph computes the forward and reverse import
   6 // dependency graphs for all packages in a Go workspace.
   7 package importgraph // import "golang.org/x/tools/refactor/importgraph"
   8
   9 import (
  10         "go/build"
  11         "sync"
  12
  13         "golang.org/x/tools/go/buildutil"
  14 )
  15
  16 // A Graph is an import dependency graph, either forward or reverse.
  17 //
  18 // The graph maps each node (a package import path) to the set of its
  19 // successors in the graph.  For a forward graph, this is the set of
  20 // imported packages (prerequisites); for a reverse graph, it is the set
  21 // of importing packages (clients).
  22 //
  23 // Graph construction inspects all imports in each package's directory,
  24 // including those in _test.go files, so the resulting graph may be cyclic.
  25 type Graph map[string]map[string]bool
  26
  27 func (g Graph) addEdge(from, to string) {
  28         edges := g[from]
  29         if edges == nil {
  30                 edges = make(map[string]bool)
  31                 g[from] = edges
  32         }
  33         edges[to] = true
  34 }
  35
  36 // Search returns all the nodes of the graph reachable from
  37 // any of the specified roots, by following edges forwards.
  38 // Relationally, this is the reflexive transitive closure.
  39 func (g Graph) Search(roots ...string) map[string]bool {
  40         seen := make(map[string]bool)
  41         var visit func(x string)
  42         visit = func(x string) {
  43                 if !seen[x] {
  44                         seen[x] = true
  45                         for y := range g[x] {
  46                                 visit(y)
  47                         }
  48                 }
  49         }
  50         for _, root := range roots {
  51                 visit(root)
  52         }
  53         return seen
  54 }
  55
  56 // Build scans the specified Go workspace and builds the forward and
  57 // reverse import dependency graphs for all its packages.
  58 // It also returns a mapping from canonical import paths to errors for packages
  59 // whose loading was not entirely successful.
  60 // A package may appear in the graph and in the errors mapping.
  61 // All package paths are canonical and may contain "/vendor/".
  62 func Build(ctxt *build.Context) (forward, reverse Graph, errors map[string]error) {
  63         type importEdge struct {
  64                 from, to string
  65         }
  66         type pathError struct {
  67                 path string
  68                 err  error
  69         }
  70
  71         ch := make(chan interface{})
  72
  73         go func() {
  74                 sema := make(chan int, 20) // I/O concurrency limiting semaphore
  75                 var wg sync.WaitGroup
  76                 buildutil.ForEachPackage(ctxt, func(path string, err error) {
  77                         if err != nil {
  78                                 ch <- pathError{path, err}
  79                                 return
  80                         }
  81
  82                         wg.Add(1)
  83                         go func() {
  84                                 defer wg.Done()
  85
  86                                 sema <- 1
  87                                 bp, err := ctxt.Import(path, "", 0)
  88                                 <-sema
  89
  90                                 if err != nil {
  91                                         if _, ok := err.(*build.NoGoError); ok {
  92                                                 // empty directory is not an error
  93                                         } else {
  94                                                 ch <- pathError{path, err}
  95                                         }
  96                                         // Even in error cases, Import usually returns a package.
  97                                 }
  98
  99                                 // absolutize resolves an import path relative
 100                                 // to the current package bp.
 101                                 // The absolute form may contain "vendor".
 102                                 //
 103                                 // The vendoring feature slows down Build by 3×.
 104                                 // Here are timings from a 1400 package workspace:
 105                                 //    1100ms: current code (with vendor check)
 106                                 //     880ms: with a nonblocking cache around ctxt.IsDir
 107                                 //     840ms: nonblocking cache with duplicate suppression
 108                                 //     340ms: original code (no vendor check)
 109                                 // TODO(adonovan): optimize, somehow.
 110                                 memo := make(map[string]string)
 111                                 absolutize := func(path string) string {
 112                                         canon, ok := memo[path]
 113                                         if !ok {
 114                                                 sema <- 1
 115                                                 bp2, _ := ctxt.Import(path, bp.Dir, build.FindOnly)
 116                                                 <-sema
 117
 118                                                 if bp2 != nil {
 119                                                         canon = bp2.ImportPath
 120                                                 } else {
 121                                                         canon = path
 122                                                 }
 123                                                 memo[path] = canon
 124                                         }
 125                                         return canon
 126                                 }
 127
 128                                 if bp != nil {
 129                                         for _, imp := range bp.Imports {
 130                                                 ch <- importEdge{path, absolutize(imp)}
 131                                         }
 132                                         for _, imp := range bp.TestImports {
 133                                                 ch <- importEdge{path, absolutize(imp)}
 134                                         }
 135                                         for _, imp := range bp.XTestImports {
 136                                                 ch <- importEdge{path, absolutize(imp)}
 137                                         }
 138                                 }
 139
 140                         }()
 141                 })
 142                 wg.Wait()
 143                 close(ch)
 144         }()
 145
 146         forward = make(Graph)
 147         reverse = make(Graph)
 148
 149         for e := range ch {
 150                 switch e := e.(type) {
 151                 case pathError:
 152                         if errors == nil {
 153                                 errors = make(map[string]error)
 154                         }
 155                         errors[e.path] = e.err
 156
 157                 case importEdge:
 158                         if e.to == "C" {
 159                                 continue // "C" is fake
 160                         }
 161                         forward.addEdge(e.from, e.to)
 162                         reverse.addEdge(e.to, e.from)
 163                 }
 164         }
 165
 166         return forward, reverse, errors
 167 }