--- /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 importgraph computes the forward and reverse import
+// dependency graphs for all packages in a Go workspace.
+package importgraph // import "golang.org/x/tools/refactor/importgraph"
+
+import (
+ "go/build"
+ "sync"
+
+ "golang.org/x/tools/go/buildutil"
+)
+
+// A Graph is an import dependency graph, either forward or reverse.
+//
+// The graph maps each node (a package import path) to the set of its
+// successors in the graph. For a forward graph, this is the set of
+// imported packages (prerequisites); for a reverse graph, it is the set
+// of importing packages (clients).
+//
+// Graph construction inspects all imports in each package's directory,
+// including those in _test.go files, so the resulting graph may be cyclic.
+type Graph map[string]map[string]bool
+
+func (g Graph) addEdge(from, to string) {
+ edges := g[from]
+ if edges == nil {
+ edges = make(map[string]bool)
+ g[from] = edges
+ }
+ edges[to] = true
+}
+
+// Search returns all the nodes of the graph reachable from
+// any of the specified roots, by following edges forwards.
+// Relationally, this is the reflexive transitive closure.
+func (g Graph) Search(roots ...string) map[string]bool {
+ seen := make(map[string]bool)
+ var visit func(x string)
+ visit = func(x string) {
+ if !seen[x] {
+ seen[x] = true
+ for y := range g[x] {
+ visit(y)
+ }
+ }
+ }
+ for _, root := range roots {
+ visit(root)
+ }
+ return seen
+}
+
+// Build scans the specified Go workspace and builds the forward and
+// reverse import dependency graphs for all its packages.
+// It also returns a mapping from canonical import paths to errors for packages
+// whose loading was not entirely successful.
+// A package may appear in the graph and in the errors mapping.
+// All package paths are canonical and may contain "/vendor/".
+func Build(ctxt *build.Context) (forward, reverse Graph, errors map[string]error) {
+ type importEdge struct {
+ from, to string
+ }
+ type pathError struct {
+ path string
+ err error
+ }
+
+ ch := make(chan interface{})
+
+ go func() {
+ sema := make(chan int, 20) // I/O concurrency limiting semaphore
+ var wg sync.WaitGroup
+ buildutil.ForEachPackage(ctxt, func(path string, err error) {
+ if err != nil {
+ ch <- pathError{path, err}
+ return
+ }
+
+ wg.Add(1)
+ go func() {
+ defer wg.Done()
+
+ sema <- 1
+ bp, err := ctxt.Import(path, "", 0)
+ <-sema
+
+ if err != nil {
+ if _, ok := err.(*build.NoGoError); ok {
+ // empty directory is not an error
+ } else {
+ ch <- pathError{path, err}
+ }
+ // Even in error cases, Import usually returns a package.
+ }
+
+ // absolutize resolves an import path relative
+ // to the current package bp.
+ // The absolute form may contain "vendor".
+ //
+ // The vendoring feature slows down Build by 3×.
+ // Here are timings from a 1400 package workspace:
+ // 1100ms: current code (with vendor check)
+ // 880ms: with a nonblocking cache around ctxt.IsDir
+ // 840ms: nonblocking cache with duplicate suppression
+ // 340ms: original code (no vendor check)
+ // TODO(adonovan): optimize, somehow.
+ memo := make(map[string]string)
+ absolutize := func(path string) string {
+ canon, ok := memo[path]
+ if !ok {
+ sema <- 1
+ bp2, _ := ctxt.Import(path, bp.Dir, build.FindOnly)
+ <-sema
+
+ if bp2 != nil {
+ canon = bp2.ImportPath
+ } else {
+ canon = path
+ }
+ memo[path] = canon
+ }
+ return canon
+ }
+
+ if bp != nil {
+ for _, imp := range bp.Imports {
+ ch <- importEdge{path, absolutize(imp)}
+ }
+ for _, imp := range bp.TestImports {
+ ch <- importEdge{path, absolutize(imp)}
+ }
+ for _, imp := range bp.XTestImports {
+ ch <- importEdge{path, absolutize(imp)}
+ }
+ }
+
+ }()
+ })
+ wg.Wait()
+ close(ch)
+ }()
+
+ forward = make(Graph)
+ reverse = make(Graph)
+
+ for e := range ch {
+ switch e := e.(type) {
+ case pathError:
+ if errors == nil {
+ errors = make(map[string]error)
+ }
+ errors[e.path] = e.err
+
+ case importEdge:
+ if e.to == "C" {
+ continue // "C" is fake
+ }
+ forward.addEdge(e.from, e.to)
+ reverse.addEdge(e.to, e.from)
+ }
+ }
+
+ return forward, reverse, errors
+}
projects / dotfiles / .git / blobdiff