graph.go

Documentation: golang.org/x/tools/refactor/importgraph

     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  }
   168
View as plain text