.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/godoc/dirtrees.go

   1 // Copyright 2010 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 // This file contains the code dealing with package directory trees.
   6
   7 package godoc
   8
   9 import (
  10         "go/doc"
  11         "go/parser"
  12         "go/token"
  13         "log"
  14         "os"
  15         pathpkg "path"
  16         "runtime"
  17         "sort"
  18         "strings"
  19
  20         "golang.org/x/tools/godoc/vfs"
  21 )
  22
  23 // Conventional name for directories containing test data.
  24 // Excluded from directory trees.
  25 //
  26 const testdataDirName = "testdata"
  27
  28 type Directory struct {
  29         Depth    int
  30         Path     string       // directory path; includes Name
  31         Name     string       // directory name
  32         HasPkg   bool         // true if the directory contains at least one package
  33         Synopsis string       // package documentation, if any
  34         RootType vfs.RootType // root type of the filesystem containing the directory
  35         Dirs     []*Directory // subdirectories
  36 }
  37
  38 func isGoFile(fi os.FileInfo) bool {
  39         name := fi.Name()
  40         return !fi.IsDir() &&
  41                 len(name) > 0 && name[0] != '.' && // ignore .files
  42                 pathpkg.Ext(name) == ".go"
  43 }
  44
  45 func isPkgFile(fi os.FileInfo) bool {
  46         return isGoFile(fi) &&
  47                 !strings.HasSuffix(fi.Name(), "_test.go") // ignore test files
  48 }
  49
  50 func isPkgDir(fi os.FileInfo) bool {
  51         name := fi.Name()
  52         return fi.IsDir() && len(name) > 0 &&
  53                 name[0] != '_' && name[0] != '.' // ignore _files and .files
  54 }
  55
  56 type treeBuilder struct {
  57         c        *Corpus
  58         maxDepth int
  59 }
  60
  61 // ioGate is a semaphore controlling VFS activity (ReadDir, parseFile, etc).
  62 // Send before an operation and receive after.
  63 var ioGate = make(chan struct{}, 20)
  64
  65 // workGate controls the number of concurrent workers. Too many concurrent
  66 // workers and performance degrades and the race detector gets overwhelmed. If
  67 // we cannot check out a concurrent worker, work is performed by the main thread
  68 // instead of spinning up another goroutine.
  69 var workGate = make(chan struct{}, runtime.NumCPU()*4)
  70
  71 func (b *treeBuilder) newDirTree(fset *token.FileSet, path, name string, depth int) *Directory {
  72         if name == testdataDirName {
  73                 return nil
  74         }
  75
  76         if depth >= b.maxDepth {
  77                 // return a dummy directory so that the parent directory
  78                 // doesn't get discarded just because we reached the max
  79                 // directory depth
  80                 return &Directory{
  81                         Depth: depth,
  82                         Path:  path,
  83                         Name:  name,
  84                 }
  85         }
  86
  87         var synopses [3]string // prioritized package documentation (0 == highest priority)
  88
  89         show := true // show in package listing
  90         hasPkgFiles := false
  91         haveSummary := false
  92
  93         if hook := b.c.SummarizePackage; hook != nil {
  94                 if summary, show0, ok := hook(strings.TrimPrefix(path, "/src/")); ok {
  95                         hasPkgFiles = true
  96                         show = show0
  97                         synopses[0] = summary
  98                         haveSummary = true
  99                 }
 100         }
 101
 102         ioGate <- struct{}{}
 103         list, err := b.c.fs.ReadDir(path)
 104         <-ioGate
 105         if err != nil {
 106                 // TODO: propagate more. See golang.org/issue/14252.
 107                 // For now:
 108                 if b.c.Verbose {
 109                         log.Printf("newDirTree reading %s: %v", path, err)
 110                 }
 111         }
 112
 113         // determine number of subdirectories and if there are package files
 114         var dirchs []chan *Directory
 115         var dirs []*Directory
 116
 117         for _, d := range list {
 118                 filename := pathpkg.Join(path, d.Name())
 119                 switch {
 120                 case isPkgDir(d):
 121                         name := d.Name()
 122                         select {
 123                         case workGate <- struct{}{}:
 124                                 ch := make(chan *Directory, 1)
 125                                 dirchs = append(dirchs, ch)
 126                                 go func() {
 127                                         ch <- b.newDirTree(fset, filename, name, depth+1)
 128                                         <-workGate
 129                                 }()
 130                         default:
 131                                 // no free workers, do work synchronously
 132                                 dir := b.newDirTree(fset, filename, name, depth+1)
 133                                 if dir != nil {
 134                                         dirs = append(dirs, dir)
 135                                 }
 136                         }
 137                 case !haveSummary && isPkgFile(d):
 138                         // looks like a package file, but may just be a file ending in ".go";
 139                         // don't just count it yet (otherwise we may end up with hasPkgFiles even
 140                         // though the directory doesn't contain any real package files - was bug)
 141                         // no "optimal" package synopsis yet; continue to collect synopses
 142                         ioGate <- struct{}{}
 143                         const flags = parser.ParseComments | parser.PackageClauseOnly
 144                         file, err := b.c.parseFile(fset, filename, flags)
 145                         <-ioGate
 146                         if err != nil {
 147                                 if b.c.Verbose {
 148                                         log.Printf("Error parsing %v: %v", filename, err)
 149                                 }
 150                                 break
 151                         }
 152
 153                         hasPkgFiles = true
 154                         if file.Doc != nil {
 155                                 // prioritize documentation
 156                                 i := -1
 157                                 switch file.Name.Name {
 158                                 case name:
 159                                         i = 0 // normal case: directory name matches package name
 160                                 case "main":
 161                                         i = 1 // directory contains a main package
 162                                 default:
 163                                         i = 2 // none of the above
 164                                 }
 165                                 if 0 <= i && i < len(synopses) && synopses[i] == "" {
 166                                         synopses[i] = doc.Synopsis(file.Doc.Text())
 167                                 }
 168                         }
 169                         haveSummary = synopses[0] != ""
 170                 }
 171         }
 172
 173         // create subdirectory tree
 174         for _, ch := range dirchs {
 175                 if d := <-ch; d != nil {
 176                         dirs = append(dirs, d)
 177                 }
 178         }
 179
 180         // We need to sort the dirs slice because
 181         // it is appended again after reading from dirchs.
 182         sort.Slice(dirs, func(i, j int) bool {
 183                 return dirs[i].Name < dirs[j].Name
 184         })
 185
 186         // if there are no package files and no subdirectories
 187         // containing package files, ignore the directory
 188         if !hasPkgFiles && len(dirs) == 0 {
 189                 return nil
 190         }
 191
 192         // select the highest-priority synopsis for the directory entry, if any
 193         synopsis := ""
 194         for _, synopsis = range synopses {
 195                 if synopsis != "" {
 196                         break
 197                 }
 198         }
 199
 200         return &Directory{
 201                 Depth:    depth,
 202                 Path:     path,
 203                 Name:     name,
 204                 HasPkg:   hasPkgFiles && show, // TODO(bradfitz): add proper Hide field?
 205                 Synopsis: synopsis,
 206                 RootType: b.c.fs.RootType(path),
 207                 Dirs:     dirs,
 208         }
 209 }
 210
 211 // newDirectory creates a new package directory tree with at most maxDepth
 212 // levels, anchored at root. The result tree is pruned such that it only
 213 // contains directories that contain package files or that contain
 214 // subdirectories containing package files (transitively). If a non-nil
 215 // pathFilter is provided, directory paths additionally must be accepted
 216 // by the filter (i.e., pathFilter(path) must be true). If a value >= 0 is
 217 // provided for maxDepth, nodes at larger depths are pruned as well; they
 218 // are assumed to contain package files even if their contents are not known
 219 // (i.e., in this case the tree may contain directories w/o any package files).
 220 //
 221 func (c *Corpus) newDirectory(root string, maxDepth int) *Directory {
 222         // The root could be a symbolic link so use Stat not Lstat.
 223         d, err := c.fs.Stat(root)
 224         // If we fail here, report detailed error messages; otherwise
 225         // is is hard to see why a directory tree was not built.
 226         switch {
 227         case err != nil:
 228                 log.Printf("newDirectory(%s): %s", root, err)
 229                 return nil
 230         case root != "/" && !isPkgDir(d):
 231                 log.Printf("newDirectory(%s): not a package directory", root)
 232                 return nil
 233         case root == "/" && !d.IsDir():
 234                 log.Printf("newDirectory(%s): not a directory", root)
 235                 return nil
 236         }
 237         if maxDepth < 0 {
 238                 maxDepth = 1e6 // "infinity"
 239         }
 240         b := treeBuilder{c, maxDepth}
 241         // the file set provided is only for local parsing, no position
 242         // information escapes and thus we don't need to save the set
 243         return b.newDirTree(token.NewFileSet(), root, d.Name(), 0)
 244 }
 245
 246 func (dir *Directory) walk(c chan<- *Directory, skipRoot bool) {
 247         if dir != nil {
 248                 if !skipRoot {
 249                         c <- dir
 250                 }
 251                 for _, d := range dir.Dirs {
 252                         d.walk(c, false)
 253                 }
 254         }
 255 }
 256
 257 func (dir *Directory) iter(skipRoot bool) <-chan *Directory {
 258         c := make(chan *Directory)
 259         go func() {
 260                 dir.walk(c, skipRoot)
 261                 close(c)
 262         }()
 263         return c
 264 }
 265
 266 func (dir *Directory) lookupLocal(name string) *Directory {
 267         for _, d := range dir.Dirs {
 268                 if d.Name == name {
 269                         return d
 270                 }
 271         }
 272         return nil
 273 }
 274
 275 func splitPath(p string) []string {
 276         p = strings.TrimPrefix(p, "/")
 277         if p == "" {
 278                 return nil
 279         }
 280         return strings.Split(p, "/")
 281 }
 282
 283 // lookup looks for the *Directory for a given path, relative to dir.
 284 func (dir *Directory) lookup(path string) *Directory {
 285         d := splitPath(dir.Path)
 286         p := splitPath(path)
 287         i := 0
 288         for i < len(d) {
 289                 if i >= len(p) || d[i] != p[i] {
 290                         return nil
 291                 }
 292                 i++
 293         }
 294         for dir != nil && i < len(p) {
 295                 dir = dir.lookupLocal(p[i])
 296                 i++
 297         }
 298         return dir
 299 }
 300
 301 // DirEntry describes a directory entry. The Depth and Height values
 302 // are useful for presenting an entry in an indented fashion.
 303 //
 304 type DirEntry struct {
 305         Depth    int          // >= 0
 306         Height   int          // = DirList.MaxHeight - Depth, > 0
 307         Path     string       // directory path; includes Name, relative to DirList root
 308         Name     string       // directory name
 309         HasPkg   bool         // true if the directory contains at least one package
 310         Synopsis string       // package documentation, if any
 311         RootType vfs.RootType // root type of the filesystem containing the direntry
 312 }
 313
 314 type DirList struct {
 315         MaxHeight int // directory tree height, > 0
 316         List      []DirEntry
 317 }
 318
 319 // hasThirdParty checks whether a list of directory entries has packages outside
 320 // the standard library or not.
 321 func hasThirdParty(list []DirEntry) bool {
 322         for _, entry := range list {
 323                 if entry.RootType == vfs.RootTypeGoPath {
 324                         return true
 325                 }
 326         }
 327         return false
 328 }
 329
 330 // listing creates a (linear) directory listing from a directory tree.
 331 // If skipRoot is set, the root directory itself is excluded from the list.
 332 // If filter is set, only the directory entries whose paths match the filter
 333 // are included.
 334 //
 335 func (dir *Directory) listing(skipRoot bool, filter func(string) bool) *DirList {
 336         if dir == nil {
 337                 return nil
 338         }
 339
 340         // determine number of entries n and maximum height
 341         n := 0
 342         minDepth := 1 << 30 // infinity
 343         maxDepth := 0
 344         for d := range dir.iter(skipRoot) {
 345                 n++
 346                 if minDepth > d.Depth {
 347                         minDepth = d.Depth
 348                 }
 349                 if maxDepth < d.Depth {
 350                         maxDepth = d.Depth
 351                 }
 352         }
 353         maxHeight := maxDepth - minDepth + 1
 354
 355         if n == 0 {
 356                 return nil
 357         }
 358
 359         // create list
 360         list := make([]DirEntry, 0, n)
 361         for d := range dir.iter(skipRoot) {
 362                 if filter != nil && !filter(d.Path) {
 363                         continue
 364                 }
 365                 var p DirEntry
 366                 p.Depth = d.Depth - minDepth
 367                 p.Height = maxHeight - p.Depth
 368                 // the path is relative to root.Path - remove the root.Path
 369                 // prefix (the prefix should always be present but avoid
 370                 // crashes and check)
 371                 path := strings.TrimPrefix(d.Path, dir.Path)
 372                 // remove leading separator if any - path must be relative
 373                 path = strings.TrimPrefix(path, "/")
 374                 p.Path = path
 375                 p.Name = d.Name
 376                 p.HasPkg = d.HasPkg
 377                 p.Synopsis = d.Synopsis
 378                 p.RootType = d.RootType
 379                 list = append(list, p)
 380         }
 381
 382         return &DirList{maxHeight, list}
 383 }