godoc/dirtrees.go - tools - Git at Google

 // Copyright 2010 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.

 // This file contains the code dealing with package directory trees.

 package godoc

 import (
 	"go/doc"
 	"go/parser"
 	"go/token"
 	"log"
 	"os"
 	pathpkg "path"
 	"runtime"
 	"sort"
 	"strings"

 	"golang.org/x/tools/godoc/vfs"
 )

 // Conventional name for directories containing test data.
 // Excluded from directory trees.
 //
 const testdataDirName = "testdata"

 type Directory struct {
 	Depth    int
 	Path     string       // directory path; includes Name
 	Name     string       // directory name
 	HasPkg   bool         // true if the directory contains at least one package
 	Synopsis string       // package documentation, if any
 	RootType vfs.RootType // root type of the filesystem containing the directory
 	Dirs     []*Directory // subdirectories
 }

 func isGoFile(fi os.FileInfo) bool {
 	name := fi.Name()
 	return !fi.IsDir() &&
 		len(name) > 0 && name[0] != '.' && // ignore .files
 		pathpkg.Ext(name) == ".go"
 }

 func isPkgFile(fi os.FileInfo) bool {
 	return isGoFile(fi) &&
 		!strings.HasSuffix(fi.Name(), "_test.go") // ignore test files
 }

 func isPkgDir(fi os.FileInfo) bool {
 	name := fi.Name()
 	return fi.IsDir() && len(name) > 0 &&
 		name[0] != '_' && name[0] != '.' // ignore _files and .files
 }

 type treeBuilder struct {
 	c        *Corpus
 	maxDepth int
 }

 // ioGate is a semaphore controlling VFS activity (ReadDir, parseFile, etc).
 // Send before an operation and receive after.
 var ioGate = make(chan struct{}, 20)

 // workGate controls the number of concurrent workers. Too many concurrent
 // workers and performance degrades and the race detector gets overwhelmed. If
 // we cannot check out a concurrent worker, work is performed by the main thread
 // instead of spinning up another goroutine.
 var workGate = make(chan struct{}, runtime.NumCPU()*4)

 func (b *treeBuilder) newDirTree(fset *token.FileSet, path, name string, depth int) *Directory {
 	if name == testdataDirName {
 		return nil
 	}

 	if depth >= b.maxDepth {
 		// return a dummy directory so that the parent directory
 		// doesn't get discarded just because we reached the max
 		// directory depth
 		return &Directory{
 			Depth: depth,
 			Path:  path,
 			Name:  name,
 		}
 	}

 	var synopses [3]string // prioritized package documentation (0 == highest priority)

 	show := true // show in package listing
 	hasPkgFiles := false
 	haveSummary := false

 	if hook := b.c.SummarizePackage; hook != nil {
 		if summary, show0, ok := hook(strings.TrimPrefix(path, "/src/")); ok {
 			hasPkgFiles = true
 			show = show0
 			synopses[0] = summary
 			haveSummary = true
 		}
 	}

 	ioGate <- struct{}{}
 	list, err := b.c.fs.ReadDir(path)
 	<-ioGate
 	if err != nil {
 		// TODO: propagate more. See golang.org/issue/14252.
 		// For now:
 		if b.c.Verbose {
 			log.Printf("newDirTree reading %s: %v", path, err)
 		}
 	}

 	// determine number of subdirectories and if there are package files
 	var dirchs []chan *Directory
 	var dirs []*Directory

 	for _, d := range list {
 		filename := pathpkg.Join(path, d.Name())
 		switch {
 		case isPkgDir(d):
 			name := d.Name()
 			select {
 			case workGate <- struct{}{}:
 				ch := make(chan *Directory, 1)
 				dirchs = append(dirchs, ch)
 				go func() {
 					ch <- b.newDirTree(fset, filename, name, depth+1)
 					<-workGate
 				}()
 			default:
 				// no free workers, do work synchronously
 				dir := b.newDirTree(fset, filename, name, depth+1)
 				if dir != nil {
 					dirs = append(dirs, dir)
 				}
 			}
 		case !haveSummary && isPkgFile(d):
 			// looks like a package file, but may just be a file ending in ".go";
 			// don't just count it yet (otherwise we may end up with hasPkgFiles even
 			// though the directory doesn't contain any real package files - was bug)
 			// no "optimal" package synopsis yet; continue to collect synopses
 			ioGate <- struct{}{}
 			const flags = parser.ParseComments | parser.PackageClauseOnly
 			file, err := b.c.parseFile(fset, filename, flags)
 			<-ioGate
 			if err != nil {
 				if b.c.Verbose {
 					log.Printf("Error parsing %v: %v", filename, err)
 				}
 				break
 			}

 			hasPkgFiles = true
 			if file.Doc != nil {
 				// prioritize documentation
 				i := -1
 				switch file.Name.Name {
 				case name:
 					i = 0 // normal case: directory name matches package name
 				case "main":
 					i = 1 // directory contains a main package
 				default:
 					i = 2 // none of the above
 				}
 				if 0 <= i && i < len(synopses) && synopses[i] == "" {
 					synopses[i] = doc.Synopsis(file.Doc.Text())
 				}
 			}
 			haveSummary = synopses[0] != ""
 		}
 	}

 	// create subdirectory tree
 	for _, ch := range dirchs {
 		if d := <-ch; d != nil {
 			dirs = append(dirs, d)
 		}
 	}

 	// We need to sort the dirs slice because
 	// it is appended again after reading from dirchs.
 	sort.Slice(dirs, func(i, j int) bool {
 		return dirs[i].Name < dirs[j].Name
 	})

 	// if there are no package files and no subdirectories
 	// containing package files, ignore the directory
 	if !hasPkgFiles && len(dirs) == 0 {
 		return nil
 	}

 	// select the highest-priority synopsis for the directory entry, if any
 	synopsis := ""
 	for _, synopsis = range synopses {
 		if synopsis != "" {
 			break
 		}
 	}

 	return &Directory{
 		Depth:    depth,
 		Path:     path,
 		Name:     name,
 		HasPkg:   hasPkgFiles && show, // TODO(bradfitz): add proper Hide field?
 		Synopsis: synopsis,
 		RootType: b.c.fs.RootType(path),
 		Dirs:     dirs,
 	}
 }

 // newDirectory creates a new package directory tree with at most maxDepth
 // levels, anchored at root. The result tree is pruned such that it only
 // contains directories that contain package files or that contain
 // subdirectories containing package files (transitively). If a non-nil
 // pathFilter is provided, directory paths additionally must be accepted
 // by the filter (i.e., pathFilter(path) must be true). If a value >= 0 is
 // provided for maxDepth, nodes at larger depths are pruned as well; they
 // are assumed to contain package files even if their contents are not known
 // (i.e., in this case the tree may contain directories w/o any package files).
 //
 func (c *Corpus) newDirectory(root string, maxDepth int) *Directory {
 	// The root could be a symbolic link so use Stat not Lstat.
 	d, err := c.fs.Stat(root)
 	// If we fail here, report detailed error messages; otherwise
 	// is is hard to see why a directory tree was not built.
 	switch {
 	case err != nil:
 		log.Printf("newDirectory(%s): %s", root, err)
 		return nil
 	case root != "/" && !isPkgDir(d):
 		log.Printf("newDirectory(%s): not a package directory", root)
 		return nil
 	case root == "/" && !d.IsDir():
 		log.Printf("newDirectory(%s): not a directory", root)
 		return nil
 	}
 	if maxDepth < 0 {
 		maxDepth = 1e6 // "infinity"
 	}
 	b := treeBuilder{c, maxDepth}
 	// the file set provided is only for local parsing, no position
 	// information escapes and thus we don't need to save the set
 	return b.newDirTree(token.NewFileSet(), root, d.Name(), 0)
 }

 func (dir *Directory) walk(c chan<- *Directory, skipRoot bool) {
 	if dir != nil {
 		if !skipRoot {
 			c <- dir
 		}
 		for _, d := range dir.Dirs {
 			d.walk(c, false)
 		}
 	}
 }

 func (dir *Directory) iter(skipRoot bool) <-chan *Directory {
 	c := make(chan *Directory)
 	go func() {
 		dir.walk(c, skipRoot)
 		close(c)
 	}()
 	return c
 }

 func (dir *Directory) lookupLocal(name string) *Directory {
 	for _, d := range dir.Dirs {
 		if d.Name == name {
 			return d
 		}
 	}
 	return nil
 }

 func splitPath(p string) []string {
 	p = strings.TrimPrefix(p, "/")
 	if p == "" {
 		return nil
 	}
 	return strings.Split(p, "/")
 }

 // lookup looks for the *Directory for a given path, relative to dir.
 func (dir *Directory) lookup(path string) *Directory {
 	d := splitPath(dir.Path)
 	p := splitPath(path)
 	i := 0
 	for i < len(d) {
 		if i >= len(p) || d[i] != p[i] {
 			return nil
 		}
 		i++
 	}
 	for dir != nil && i < len(p) {
 		dir = dir.lookupLocal(p[i])
 		i++
 	}
 	return dir
 }

 // DirEntry describes a directory entry. The Depth and Height values
 // are useful for presenting an entry in an indented fashion.
 //
 type DirEntry struct {
 	Depth    int          // >= 0
 	Height   int          // = DirList.MaxHeight - Depth, > 0
 	Path     string       // directory path; includes Name, relative to DirList root
 	Name     string       // directory name
 	HasPkg   bool         // true if the directory contains at least one package
 	Synopsis string       // package documentation, if any
 	RootType vfs.RootType // root type of the filesystem containing the direntry
 }

 type DirList struct {
 	MaxHeight int // directory tree height, > 0
 	List      []DirEntry
 }

 // hasThirdParty checks whether a list of directory entries has packages outside
 // the standard library or not.
 func hasThirdParty(list []DirEntry) bool {
 	for _, entry := range list {
 		if entry.RootType == vfs.RootTypeGoPath {
 			return true
 		}
 	}
 	return false
 }

 // listing creates a (linear) directory listing from a directory tree.
 // If skipRoot is set, the root directory itself is excluded from the list.
 // If filter is set, only the directory entries whose paths match the filter
 // are included.
 //
 func (dir *Directory) listing(skipRoot bool, filter func(string) bool) *DirList {
 	if dir == nil {
 		return nil
 	}

 	// determine number of entries n and maximum height
 	n := 0
 	minDepth := 1 << 30 // infinity
 	maxDepth := 0
 	for d := range dir.iter(skipRoot) {
 		n++
 		if minDepth > d.Depth {
 			minDepth = d.Depth
 		}
 		if maxDepth < d.Depth {
 			maxDepth = d.Depth
 		}
 	}
 	maxHeight := maxDepth - minDepth + 1

 	if n == 0 {
 		return nil
 	}

 	// create list
 	list := make([]DirEntry, 0, n)
 	for d := range dir.iter(skipRoot) {
 		if filter != nil && !filter(d.Path) {
 			continue
 		}
 		var p DirEntry
 		p.Depth = d.Depth - minDepth
 		p.Height = maxHeight - p.Depth
 		// the path is relative to root.Path - remove the root.Path
 		// prefix (the prefix should always be present but avoid
 		// crashes and check)
 		path := strings.TrimPrefix(d.Path, dir.Path)
 		// remove leading separator if any - path must be relative
 		path = strings.TrimPrefix(path, "/")
 		p.Path = path
 		p.Name = d.Name
 		p.HasPkg = d.HasPkg
 		p.Synopsis = d.Synopsis
 		p.RootType = d.RootType
 		list = append(list, p)
 	}

 	return &DirList{maxHeight, list}
 }
	// Copyright 2010 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.

	// This file contains the code dealing with package directory trees.

	package godoc

	import (
	"go/doc"
	"go/parser"
	"go/token"
	"log"
	"os"
	pathpkg "path"
	"runtime"
	"sort"
	"strings"

	"golang.org/x/tools/godoc/vfs"
	)

	// Conventional name for directories containing test data.
	// Excluded from directory trees.
	//
	const testdataDirName = "testdata"

	type Directory struct {
	Depth int
	Path string // directory path; includes Name
	Name string // directory name
	HasPkg bool // true if the directory contains at least one package
	Synopsis string // package documentation, if any
	RootType vfs.RootType // root type of the filesystem containing the directory
	Dirs []*Directory // subdirectories
	}

	func isGoFile(fi os.FileInfo) bool {
	name := fi.Name()
	return !fi.IsDir() &&
	len(name) > 0 && name[0] != '.' && // ignore .files
	pathpkg.Ext(name) == ".go"
	}

	func isPkgFile(fi os.FileInfo) bool {
	return isGoFile(fi) &&
	!strings.HasSuffix(fi.Name(), "_test.go") // ignore test files
	}

	func isPkgDir(fi os.FileInfo) bool {
	name := fi.Name()
	return fi.IsDir() && len(name) > 0 &&
	name[0] != '_' && name[0] != '.' // ignore _files and .files
	}

	type treeBuilder struct {
	c *Corpus
	maxDepth int
	}

	// ioGate is a semaphore controlling VFS activity (ReadDir, parseFile, etc).
	// Send before an operation and receive after.
	var ioGate = make(chan struct{}, 20)

	// workGate controls the number of concurrent workers. Too many concurrent
	// workers and performance degrades and the race detector gets overwhelmed. If
	// we cannot check out a concurrent worker, work is performed by the main thread
	// instead of spinning up another goroutine.
	var workGate = make(chan struct{}, runtime.NumCPU()*4)

	func (b treeBuilder) newDirTree(fset token.FileSet, path, name string, depth int) *Directory {
	if name == testdataDirName {
	return nil
	}

	if depth >= b.maxDepth {
	// return a dummy directory so that the parent directory
	// doesn't get discarded just because we reached the max
	// directory depth
	return &Directory{
	Depth: depth,
	Path: path,
	Name: name,
	}
	}

	var synopses [3]string // prioritized package documentation (0 == highest priority)

	show := true // show in package listing
	hasPkgFiles := false
	haveSummary := false

	if hook := b.c.SummarizePackage; hook != nil {
	if summary, show0, ok := hook(strings.TrimPrefix(path, "/src/")); ok {
	hasPkgFiles = true
	show = show0
	synopses[0] = summary
	haveSummary = true
	}
	}

	ioGate <- struct{}{}
	list, err := b.c.fs.ReadDir(path)
	<-ioGate
	if err != nil {
	// TODO: propagate more. See golang.org/issue/14252.
	// For now:
	if b.c.Verbose {
	log.Printf("newDirTree reading %s: %v", path, err)
	}
	}

	// determine number of subdirectories and if there are package files
	var dirchs []chan *Directory
	var dirs []*Directory

	for _, d := range list {
	filename := pathpkg.Join(path, d.Name())
	switch {
	case isPkgDir(d):
	name := d.Name()
	select {
	case workGate <- struct{}{}:
	ch := make(chan *Directory, 1)
	dirchs = append(dirchs, ch)
	go func() {
	ch <- b.newDirTree(fset, filename, name, depth+1)
	<-workGate
	}()
	default:
	// no free workers, do work synchronously
	dir := b.newDirTree(fset, filename, name, depth+1)
	if dir != nil {
	dirs = append(dirs, dir)
	}
	}
	case !haveSummary && isPkgFile(d):
	// looks like a package file, but may just be a file ending in ".go";
	// don't just count it yet (otherwise we may end up with hasPkgFiles even
	// though the directory doesn't contain any real package files - was bug)
	// no "optimal" package synopsis yet; continue to collect synopses
	ioGate <- struct{}{}
	const flags = parser.ParseComments \| parser.PackageClauseOnly
	file, err := b.c.parseFile(fset, filename, flags)
	<-ioGate
	if err != nil {
	if b.c.Verbose {
	log.Printf("Error parsing %v: %v", filename, err)
	}
	break
	}

	hasPkgFiles = true
	if file.Doc != nil {
	// prioritize documentation
	i := -1
	switch file.Name.Name {
	case name:
	i = 0 // normal case: directory name matches package name
	case "main":
	i = 1 // directory contains a main package
	default:
	i = 2 // none of the above
	}
	if 0 <= i && i < len(synopses) && synopses[i] == "" {
	synopses[i] = doc.Synopsis(file.Doc.Text())
	}
	}
	haveSummary = synopses[0] != ""
	}
	}

	// create subdirectory tree
	for _, ch := range dirchs {
	if d := <-ch; d != nil {
	dirs = append(dirs, d)
	}
	}

	// We need to sort the dirs slice because
	// it is appended again after reading from dirchs.
	sort.Slice(dirs, func(i, j int) bool {
	return dirs[i].Name < dirs[j].Name
	})

	// if there are no package files and no subdirectories
	// containing package files, ignore the directory
	if !hasPkgFiles && len(dirs) == 0 {
	return nil
	}

	// select the highest-priority synopsis for the directory entry, if any
	synopsis := ""
	for _, synopsis = range synopses {
	if synopsis != "" {
	break
	}
	}

	return &Directory{
	Depth: depth,
	Path: path,
	Name: name,
	HasPkg: hasPkgFiles && show, // TODO(bradfitz): add proper Hide field?
	Synopsis: synopsis,
	RootType: b.c.fs.RootType(path),
	Dirs: dirs,
	}
	}

	// newDirectory creates a new package directory tree with at most maxDepth
	// levels, anchored at root. The result tree is pruned such that it only
	// contains directories that contain package files or that contain
	// subdirectories containing package files (transitively). If a non-nil
	// pathFilter is provided, directory paths additionally must be accepted
	// by the filter (i.e., pathFilter(path) must be true). If a value >= 0 is
	// provided for maxDepth, nodes at larger depths are pruned as well; they
	// are assumed to contain package files even if their contents are not known
	// (i.e., in this case the tree may contain directories w/o any package files).
	//
	func (c Corpus) newDirectory(root string, maxDepth int) Directory {
	// The root could be a symbolic link so use Stat not Lstat.
	d, err := c.fs.Stat(root)
	// If we fail here, report detailed error messages; otherwise
	// is is hard to see why a directory tree was not built.
	switch {
	case err != nil:
	log.Printf("newDirectory(%s): %s", root, err)
	return nil
	case root != "/" && !isPkgDir(d):
	log.Printf("newDirectory(%s): not a package directory", root)
	return nil
	case root == "/" && !d.IsDir():
	log.Printf("newDirectory(%s): not a directory", root)
	return nil
	}
	if maxDepth < 0 {
	maxDepth = 1e6 // "infinity"
	}
	b := treeBuilder{c, maxDepth}
	// the file set provided is only for local parsing, no position
	// information escapes and thus we don't need to save the set
	return b.newDirTree(token.NewFileSet(), root, d.Name(), 0)
	}

	func (dir Directory) walk(c chan<- Directory, skipRoot bool) {
	if dir != nil {
	if !skipRoot {
	c <- dir
	}
	for _, d := range dir.Dirs {
	d.walk(c, false)
	}
	}
	}

	func (dir Directory) iter(skipRoot bool) <-chan Directory {
	c := make(chan *Directory)
	go func() {
	dir.walk(c, skipRoot)
	close(c)
	}()
	return c
	}

	func (dir Directory) lookupLocal(name string) Directory {
	for _, d := range dir.Dirs {
	if d.Name == name {
	return d
	}
	}
	return nil
	}

	func splitPath(p string) []string {
	p = strings.TrimPrefix(p, "/")
	if p == "" {
	return nil
	}
	return strings.Split(p, "/")
	}

	// lookup looks for the *Directory for a given path, relative to dir.
	func (dir Directory) lookup(path string) Directory {
	d := splitPath(dir.Path)
	p := splitPath(path)
	i := 0
	for i < len(d) {
	if i >= len(p) \|\| d[i] != p[i] {
	return nil
	}
	i++
	}
	for dir != nil && i < len(p) {
	dir = dir.lookupLocal(p[i])
	i++
	}
	return dir
	}

	// DirEntry describes a directory entry. The Depth and Height values
	// are useful for presenting an entry in an indented fashion.
	//
	type DirEntry struct {
	Depth int // >= 0
	Height int // = DirList.MaxHeight - Depth, > 0
	Path string // directory path; includes Name, relative to DirList root
	Name string // directory name
	HasPkg bool // true if the directory contains at least one package
	Synopsis string // package documentation, if any
	RootType vfs.RootType // root type of the filesystem containing the direntry
	}

	type DirList struct {
	MaxHeight int // directory tree height, > 0
	List []DirEntry
	}

	// hasThirdParty checks whether a list of directory entries has packages outside
	// the standard library or not.
	func hasThirdParty(list []DirEntry) bool {
	for _, entry := range list {
	if entry.RootType == vfs.RootTypeGoPath {
	return true
	}
	}
	return false
	}

	// listing creates a (linear) directory listing from a directory tree.
	// If skipRoot is set, the root directory itself is excluded from the list.
	// If filter is set, only the directory entries whose paths match the filter
	// are included.
	//
	func (dir Directory) listing(skipRoot bool, filter func(string) bool) DirList {
	if dir == nil {
	return nil
	}

	// determine number of entries n and maximum height
	n := 0
	minDepth := 1 << 30 // infinity
	maxDepth := 0
	for d := range dir.iter(skipRoot) {
	n++
	if minDepth > d.Depth {
	minDepth = d.Depth
	}
	if maxDepth < d.Depth {
	maxDepth = d.Depth
	}
	}
	maxHeight := maxDepth - minDepth + 1

	if n == 0 {
	return nil
	}

	// create list
	list := make([]DirEntry, 0, n)
	for d := range dir.iter(skipRoot) {
	if filter != nil && !filter(d.Path) {
	continue
	}
	var p DirEntry
	p.Depth = d.Depth - minDepth
	p.Height = maxHeight - p.Depth
	// the path is relative to root.Path - remove the root.Path
	// prefix (the prefix should always be present but avoid
	// crashes and check)
	path := strings.TrimPrefix(d.Path, dir.Path)
	// remove leading separator if any - path must be relative
	path = strings.TrimPrefix(path, "/")
	p.Path = path
	p.Name = d.Name
	p.HasPkg = d.HasPkg
	p.Synopsis = d.Synopsis
	p.RootType = d.RootType
	list = append(list, p)
	}

	return &DirList{maxHeight, list}
	}