Go program to generate a dot file from the packages. Run from src/pkg.

goimports.go

package main

import (
	"container/vector"
	"fmt"
	"go/ast"
	"go/parser"
	"go/token"
	"io/ioutil"
	"os"
	"strings"
)

func isGoFile(fileInfo *os.FileInfo) bool {
	return strings.HasSuffix(fileInfo.Name, ".go") && fileInfo.Name[0] != '_' && !strings.HasSuffix(fileInfo.Name, "_test.go")
}

func getImportsForAllPackages(m map[string][]string, dir string) os.Error {
	dents, err := ioutil.ReadDir(dir)
	if err != nil {
		return err
	}
	for _, file := range dents {
		if file.IsDirectory() && file.Name[0] != '_' {
			err = getImportsForAllPackages(m, dir + "/" + file.Name)
			if err != nil {
				return err
			}
		}
	}

	if len(dir) == 1 {
		return nil
	}

	packageName := dir[2:]

	packages, err := parser.ParseDir(dir, isGoFile, parser.ImportsOnly)
	if err != nil {
		return err
	}
	if len(packages) == 0 {
		return nil
	}
	imports := make(map[string]bool)
	for foundPkgName, pkg := range packages {
		if foundPkgName == "main" {
			continue
		}
		for _, file := range pkg.Files {
			for _, decl := range file.Decls {
				if gendecl, ok := decl.(*ast.GenDecl); ok {
					if gendecl.Tok == token.IMPORT {
						for _, spec := range gendecl.Specs {
							imprt := string(spec.(*ast.ImportSpec).Path.Value)
							imprt = imprt[1:len(imprt)-1]
							if imprt != packageName {
								imports[imprt] = true
							}
						}
					}
				}
			}
		}
	}

	m[packageName] = make([]string, len(imports))
	i := 0
	for k, _ := range imports {
		m[packageName][i] = k
		i++
	}

	return nil
}

func importsToDot(m map[string][]string, ranks [][]string) {
	fmt.Printf("digraph {\n")
	for pkg, _ := range m {
		fmt.Printf("  \"%s\";\n", pkg)
	}

	for rank, pkgs := range ranks {
		fmt.Printf("\n  subgraph rank%d {\n    rank = same;\n", rank)
		for _, pkg := range pkgs {
			fmt.Printf("    \"%s\";\n", pkg)
		}
		fmt.Printf("  }\n")
	}

	for pkg, imports := range m {
		for _, imprt := range imports {
			fmt.Printf("  \"%s\" -> \"%s\";\n", pkg, imprt)
		}
	}
	fmt.Printf("}\n")
}

func printInboundArcs(m map[string][]string) {
	for pkg, imports := range m {
		if strings.HasPrefix(pkg, "crypto/") {
			continue
		}
		for _, imprt := range imports {
			if strings.HasPrefix(imprt, "crypto/") {
				fmt.Printf("%s %s\n", pkg, imprt)
			}
		}
	}
}

func findCycles(m map[string][]string) {
	for pkg, _ := range m {
		trail := new(vector.StringVector)
		findCycle(trail, pkg, m)
	}
}

func findCycle(trail *vector.StringVector, pkg string, m map[string][]string) {
	for _, p := range []string(*trail) {
		if p == pkg {
			fmt.Printf("%s: %v\n", pkg, trail)
		}
	}

	trail.Push(pkg)

	for _, imprt := range m[pkg] {
		trailCopy := trail.Copy()
		findCycle(&trailCopy, imprt, m)
	}
}

func buildRanks(ranks map[string]uint, m map[string][]string) {
	for pkg, _ := range m {
		ranks[pkg] = 0
	}

	changed := true
	for changed {
		changed = false

		for pkg, imports := range m {
			r := ranks[pkg]
			oldR := r
			for _, imprt := range imports {
				if ranks[imprt] + 1 > r {
					r = ranks[imprt] + 1
				}
			}
			if r != oldR {
				changed = true
				ranks[pkg] = r
			}
		}
	}
}

func invertRanks(pkgranks map[string]uint) [][]string {
	var maxRank uint
	for _, rank := range pkgranks {
		if rank > maxRank {
			maxRank = rank
		}
	}
	
	ranks := make([][]string, maxRank+1)
	for pkg, rank := range pkgranks {
		old := ranks[rank]
		n := make([]string, len(old) + 1)
		copy(n, old)
		n[len(old)] = pkg
		ranks[rank] = n
	}

	return ranks
}

func main() {
	m := make(map[string][]string)
	err := getImportsForAllPackages(m, ".")
	if err != nil {
		fmt.Printf("%s\n", err)
		return
	}
	findCycles(m)
	pkgranks := make(map[string]uint)
	buildRanks(pkgranks, m)
	ranks := invertRanks(pkgranks)
	importsToDot(m, ranks)
	// printInboundArcs(m)
}