cmd/sockdrawer: a tool for package reorganization.

cmd/sockdrawer/main.go

+/*
+The sockdrawer command is an analysis and visualization tool to help
+you reorganize a complex Go package into several simpler ones.
+
+OVERVIEW

[rsc, 2014/12/12 19:53:23]

Godoc will recognize plain 'Overview' as a headline. You don't need to ASCII
SHOUT.

[adonovan, 2014/12/12 20:13:00]

Oh yeah, I discovered that recently.  Fixed.

+
+sockdrawer operates on three kinds of graphs at different levels of
+abstraction.  The lowest level is the NODE GRAPH.  A node is a
+package-level declaration of a named entity (func, var, const or type).
+
+An entire constant declaration is treated as a single node, even if it
+contains multiple "specs" each defining multiple names, since constants
+so grouped are typically closely related; an important special case is
+an enumerated set data type.  Also, we treat each "spec" or a var or
+type declaration as a single node.
+
+        func f()                                // a func node
+        const ( a, b = 0, 1; c = 0 )            // a single const node
+        var (
+                a, b = 0, 1                     // a single var node
+                c = 0                           // another var node
+        )
+        type ( x int; y int )                   // a single type node
+
+Each reference to a package-level entity E forms an edge in the node
+graph, from the node in which it appears to the node E.  For example:
+
+        var x int
+        var y = x                       // edge y -> x
+        func f() int { return y }       // edge f -> y
+
+Each method declaration depends on its receiver named type; in addition
+we add an edge from each receiver type to its methods:
+
+        type T int                      // edge T -> T.f
+        func (T) f()                    // edge T.f -> T
+
+to ensure that a type and its methods stay together.
+
+The node graph is highly cyclic, and obviously all nodes in a cycle must
+belong to the same package for the package import graph to remain
+acyclic.
+
+So, we compute the second graph, the SCNODE GRAPH.  In essence, the
+scnode graph is the graph of strongly connected components (SCCs) of the
+(ordinary) node graph.  By construction, the scnode graph is acyclic.
+
+We optionally perform an optimization at this point, which is to fuse
+single-predecessor scnodes with their sole predecessor, as this tends to
+reduce clutter in big graphs.  This means that the scnodes are no longer
+true SCCs; however, the scnode graph remains acyclic.
+
+We define a valid PARTITION P of the scnode graph as a mapping from
+scnodes to CLUSTERS such that the projection of the scnode graph using
+mapping P is an acyclic graph.  This third graph is the CLUSTER GRAPH.
+
+Every partition represents a valid refactoring of the original package
+into hypothetical subpackages, each cluster being a subpackage.  Two
+partitions define the extreme ends of a spectrum: the MINIMAL partition
+maps every scnode to a single cluster; it represents the status quo, a
+monolithic package.  The MAXIMAL partition maps each scnode to a unique
+cluster; this breaks the package up into an impractically large number
+of small fragments.  The ideal partition lies somewhere in between.
+
+
+CLUSTER FILE
+
+The --clusters=<file> argument specifies a "clusters file" that
+constrains the partition algorithm.  The file consists of a number of
+stanzas, each naming a cluster ("foo") and assigning a set of initial
+nodes ({x, y, z}) to it:
+
+        = foo
+        x
+        y  # this is a comment
+        z
+
+Order of stanzas is important: clusters must be be declared bottom to
+top.  After each stanza, all nodes transitively reachable (via the node
+graph) from that cluster are assigned to that cluster, if they have not
+yet been assigned to some other cluster.  Thus we need only mention the
+root nodes of the cluster, not all its internal nodes.  A warning is
+reported if a node mentioned in a stanza already belongs to a previously
+defined cluster.
+
+There is an implicit cluster, "residue", that holds all remaining nodes
+after the cluster defined by the file have been processed.  Initially,
+when the cluster file is empty, the residue cluster contains the entire
+package.  (It is logically at the top.)  The task for the user is to
+iteratively define new clusters until the residue becomes empty.
+
+
+VISUALIZATION
+
+When sockdrawer is run, it analyzes the source package, builds the node
+graph and the scgraph, loads the cluster file, computes the clusters for
+every node, and then emits SVG renderings of the three levels of graphs,
+with nodes color codes as follows:
+
+        green = cluster  (candidate subpackage)
+        pink  = scnode   (strong component of size > 1)
+        blue  = node     (func/type/var/const)
+
+The graphs of all clusters, a DAG, has green nodes; clicking one takes
+you to the graph over scnodes for a that cluster, also a DAG.  Each pink
+node in this graph represents a cyclical bunch of the node graph,
+collapsed together for ease of viewing.  Each blue node represents a
+singleton SCC, a single named entity; singular SCCs are replaced by
+their sole element for simplicity.
+
+Clicking a pink (plural) scnode shows the cyclical portion of the node
+graph that it represents.  (If the fusion optimization was enabled, it
+may not be fully cyclic.)  All of its nodes are blue.
+
+Clicking a blue node shows the definition of that node in godoc.
+(The godoc server's base URL is specified by the --godoc flag.)
+
+
+WORKFLOW
+
+Initially, all nodes belong to the "residue" cluster.  (GraphViz graph
+rendering can be slow for the first several iterations.)  The sockdrawer
+
+The user's task when decomposing a package into clusters is to identify
+the lowest-hanging fruit (so to speak) in the residue cluster---a
+coherent group of related scnodes at the bottom of the graph---and to
+"snip off" a bunch at the "stem" by appending a new stanza to the
+cluster file, listing the roots of that bunch in the stanza, and
+re-running the tool.  Nodes may be added to an existing stanza if
+appropriate, but if they are added to a cluster that is "too low", this
+may create conflicts; keep an eye out for warnings.
+
+This process continues iteratively until the residue has become empty
+and the sets of clusters are satisfactory.
+
+The tool prints the assignments of nodes to clusters: the "shopping
+list" for the refactoring work.  Clusters should split off into
+subpackages in dependency order, lowest first.
+
+
+CAVEATS
+
+The analysis chooses a single configuration, such as linux/amd64.
+Declarations for other configurations (e.g. windows/arm) will be absent
+from the node graph.
+
+There may be some excessively large SCCs in the node graph that reflect
+a circularity in the design.  For the purposes of analysis, you can
+break them arbitrarily by commenting out some code, though more thought
+will be required for a principled fix (e.g. dependency injection).
+
+
+TODO
+
+- Make pretty and stable names for anonymous nodes such as:
+        func init() {...}
+        var _ int = ...
+  Currently their names are very sensitive to lexical perturbations.
+- Infer more constraints from co-located declarations.  Most of the stuff
+  in the runtime's residue could be disposed of this way.
+- Analyze the package's *_test.go files too.  If they define an external
+  test package, we'll have to deal with two packages at once.
+- Write tests.
+
+*/
+package main
+
+import (
+        "bufio"
+        "bytes"
+        "flag"
+        "fmt"
+        "go/ast"
+        "go/token"
+        "os"
+        "reflect"
+        "sort"
+        "strings"
+        "unicode"
+        "unicode/utf8"
+
+        "golang.org/x/tools/go/loader"
+        "golang.org/x/tools/go/types"
+)
+
+var (
+        outdir = flag.String("outdir", "out", "output directory")
+
+        collapseMethods = flag.Bool("collapse_methods", true,
+                "treat all references to methods as references to the receiver type")
+
+        fuse = flag.Bool("fuse", false,
+                "fuse each single-predecessor SCC with its sole predecessor")
+
+        godoc = flag.String("godoc", "http://localhost:4999",
+                "base URL for godoc server")
+
+        clusterFile = flag.String("clusters", "", "File containing cluster annotations")
+)
+
+const Usage = "Usage: sockdrawer [-clusters=file] [-fuse] [-godoc URL] package"
+
+func main() {
+        flag.Parse()
+        args := flag.Args()
+        if err := doMain(args); err != nil {
+                fmt.Fprintf(os.Stderr, "sockdrawer: %s\n", err)
+                os.Exit(1)
+        }
+}
+
+func doMain(args []string) error {
+        conf := loader.Config{
+                SourceImports: true,
+        }
+
+        if len(args) == 0 {
+                fmt.Fprintln(os.Stderr, Usage)
+                return nil
+        }
+
+        // Use the initial packages from the command line.
+        // TODO(adonovan): support *_test.go files too.
+        _, err := conf.FromArgs(args, false /*FIXME*/)
+        if err != nil {
+                return err
+        }
+
+        // Typecheck only the necessary function bodies.
+        // TODO(adonovan): opt: type-check only the bodies of functions
+        // with the initial packages.
+        conf.TypeCheckFuncBodies = func(p string) bool { return true }
+
+        // Load, parse and type-check the whole program.
+        iprog, err := conf.Load()
+        if err != nil {
+                return err
+        }
+
+        clusters := make(map[string]*cluster)
+
+        o := organizer{
+                fset: conf.Fset,
+        }
+        for _, info := range iprog.InitialPackages() {
+                o.doPackage(info)
+        }
+
+        // Load groups from the cluster file, if any.
+        if *clusterFile != "" {
+                byName := make(map[string]*node)
+                for _, n := range o.nodes {
+                        byName[n.name()] = n
+                }
+
+                f, err := os.Open(*clusterFile)
+                if err != nil {
+                        return err
+                }
+                in := bufio.NewScanner(f)
+                var linenum int
+                var c *cluster
+                for in.Scan() {
+                        linenum++
+                        line := strings.TrimSpace(in.Text())
+                        if i := strings.IndexByte(line, '#'); i >= 0 {
+                                line = strings.TrimSpace(line[:i]) // strip comments
+                        }
+                        if line == "" {
+                                continue // skip blanks
+                        }
+                        if strings.HasPrefix(line, "= ") {
+                                if c != nil {
+                                        c.finish()
+                                }
+
+                                c = &cluster{
+                                        id:    len(clusters),
+                                        name:  line[2:],
+                                        nodes: make(map[*node]bool),
+                                }
+                                if prev := clusters[c.name]; prev != nil {
+                                        fmt.Fprintf(os.Stderr, "%s:%d: duplicate cluster name: %s\n",
+                                                *clusterFile, linenum, c.name)
+                                        continue
+                                }
+                                clusters[c.name] = c
+                                fmt.Printf("\n# cluster %s\n", c.name)
+                                continue
+                        }
+                        if c == nil {
+                                fmt.Fprintf(os.Stderr, "%s:%d: node before '= cluster' marker\n",
+                                        *clusterFile, linenum)
+                                continue
+                        }
+
+                        n := byName[line]
+                        if n == nil {
+                                fmt.Fprintf(os.Stderr, "%s:%d: can't find node %q\n",
+                                        *clusterFile, linenum, line)
+                        } else if n.cluster != nil {
+                                fmt.Fprintf(os.Stderr, "%s:%d: node %q appears in clusters %q and %q\n",
+                                        *clusterFile, linenum, line, n.cluster.name, c.name)
+                        } else {
+                                n.cluster = c
+                                fmt.Printf("\t%s\n", n)
+                                c.nodes[n] = true
+                        }
+                }
+                if c != nil {
+                        c.finish()
+                }
+
+                // The final cluster, residue, includes all other nodes.
+                c = &cluster{
+                        id:    len(clusters),
+                        name:  "residue",
+                        nodes: make(map[*node]bool),
+                }
+                fmt.Printf("\n# cluster %s\n", c.name)
+                for _, n := range o.nodes {
+                        if n.cluster == nil {
+                                n.cluster = c
+                                fmt.Printf("\t%-50s\n", n)
+                                c.nodes[n] = true
+                        }
+                }
+                c.finish()
+                if len(c.nodes) > 0 {
+                        clusters[c.name] = c
+                }
+
+                f.Close()
+                if err := in.Err(); err != nil {
+                        return err
+                }
+        }
+
+        scgraph := o.makeSCGraph()
+
+        // dump the partition to stdout
+        for _, n := range o.nodes {
+                fmt.Printf("n%d\t%-20s s%d c%d (%s)\t\n",
+                        n.id, n.String(), n.scc.id, n.cluster.id, n.cluster.name)
+        }
+
+        return renderGraphs(clusters, scgraph)
+}
+
+type organizer struct {
+        fset     *token.FileSet
+        nodes    []*node
+        clusters map[string]*cluster
+}
+
+// A node represents a package-level declaration.
+// An entire const declaration is a single node.
+// An entire var or type "spec" is a single node.
+//
+// Examples:
+//      func f()                        // FuncDecl node
+//      func init() {...}               // FuncDecl node (no types.Object)
+//      type (
+//              T int                   // TypeSpec node
+//              U int                   // TypeSpec node
+//      )
+//      type T int                      // TypeSpec node
+//      const ( a, b = 0, 1; c = 0 )    // GenDecl(CONST) node (multiple objects)
+//      var x = f()                     // ValueSpec(var) node
+//      var x, y = f()                  // ValueSpec(var) node (multiple objects)
+//      var _ T = C(0)                  // ValueSpec(var) node (no object)
+//
+type node struct {
+        o            *organizer
+        info         *loader.PackageInfo
+        id           int
+        syntax       ast.Node       // *ast.{FuncDecl,ValueSpec(VAR),TypeSpec,GenDecl(CONST)}
+        objects      []types.Object // declared objects in lexical order; blanks omitted
+        succs, preds map[*node]bool // node graph adjacency sets
+        scc          *scnode        // SCC to which this node belongs
+        cluster      *cluster       // cluster to which this node belongs
+}
+
+func (n *node) name() string {
+        // Only the first object of a group (e.g. const decl, or
+        // type+methods) is used for the node label.
+        // This is deterministic.
+        if len(n.objects) > 0 {
+                return n.objects[0].Name()
+        } else {
+                var kind string
+                switch n.syntax.(type) {
+                case *ast.FuncDecl:
+                        // e.g. func init()
+                        kind = "func"
+                case *ast.ValueSpec:
+                        // e.g. var _ int
+                        kind = "var"
+                default:
+                        // can't happen?
+                        kind = reflect.TypeOf(n.syntax).String()
+                }
+                // We give it a stable(-ish) name so we can mention it
+                // in annotations files.  (The name will change if the
+                // source is edited though.)  Make the numbering tighter.
+                return fmt.Sprintf("%s$%d", kind, n.id)
+        }
+}
+
+func (n *node) String() string {
+        var buf bytes.Buffer
+        buf.WriteString(n.name())
+        if nobj := len(n.objects); nobj > 1 {
+                fmt.Fprintf(&buf, " + %d", nobj-1)
+        }
+        return buf.String()
+}
+
+func (n *node) godocURL() string {
+        posn := n.o.fset.Position(n.syntax.Pos())
+        i := strings.Index(posn.Filename, "/src/") // hack!
+
+        selLen := 1
+        switch syntax := n.syntax.(type) {
+        case *ast.FuncDecl:
+                selLen = len("func")
+        case *ast.TypeSpec:
+                selLen = len("type")
+        case *ast.GenDecl:
+                selLen = len("const")
+        case *ast.ValueSpec:
+                // For "var (...; x, y = ...)", select "x, y".
+                selLen = int(syntax.Names[len(syntax.Names)-1].End() - syntax.Names[0].Pos())
+        }
+        return fmt.Sprintf("%s/%s?s=%d:%d#L%d", *godoc,
+                posn.Filename[i+1:], posn.Offset, posn.Offset+selLen, posn.Line)
+}
+
+func (n *node) exportedness() int {
+        for _, obj := range n.objects {
+                if obj.Exported() {
+                        return 1
+                }
+        }
+        return 0
+}
+
+func addEdge(from, to *node) {
+        if from == to {
+                return // skip self-edges
+        }
+        from.succs[to] = true
+        to.preds[from] = true
+}
+
+type cluster struct {
+        id    int
+        name  string
+        nodes map[*node]bool
+}
+
+func (c *cluster) finish() {
+        // annotateReachable applies n's annotation to all unannotated
+        // nodes reachable from it.
+        var annotateReachable func(n *node)
+        annotateReachable = func(n *node) {
+                for s := range n.succs {
+                        if s.cluster == nil {
+                                s.cluster = n.cluster
+                                n.cluster.nodes[s] = true
+                                fmt.Printf("\t%-50s (indirect)\n", s)
+                                annotateReachable(s)
+                        }
+                }
+        }
+
+        // Add synthetic edges around the ring of nodes in the cluster.
+        // The cycle will ensure all appear in the same cluster.
+        //
+        // We must do this step on the node graph to avoid making the
+        // scgraph cyclic (but this does mean that we can't blindly
+        // choose cluster by picking one name from an SCC node, due to
+        // the sole-predecessor-fusion step).
+        var first, prev *node
+        for n := range c.nodes {
+                if first == nil {
+                        first = n
+                }
+                if prev != nil {
+                        annotateReachable(n)
+                }
+                prev = n
+        }
+        if prev != nil {
+                annotateReachable(first)
+        }
+}
+
+func (o *organizer) newNode(info *loader.PackageInfo, syntax ast.Node) *node {
+        n := &node{
+                o:      o,
+                info:   info,
+                id:     len(o.nodes),
+                syntax: syntax,
+                succs:  make(map[*node]bool),
+                preds:  make(map[*node]bool),
+        }
+        o.nodes = append(o.nodes, n)
+        return n
+}
+
+func (o *organizer) doPackage(info *loader.PackageInfo) {
+        fmt.Fprintf(os.Stderr, "\n\n\n==== %s ====\n\n\n", info.Pkg.Path())
+
+        nodesByObj := make(map[types.Object]*node) // keys are package-level objects
+
+        // -- Pass 1: Defs ----------------------------------------------------
+
+        // Node creation (and hence ids) are deterministic.
+
+        // findDefs visits the AST, associating every object defined at
+        // package-level (and every struct field or interface method
+        // defined at any level) with node for its enclosing top-level
+        // syntax tree.
+        findDefs := func(n *node) {
+                ast.Inspect(n.syntax, func(syntax ast.Node) bool {
+                        if id, ok := syntax.(*ast.Ident); ok {
+                                // Definition of package-level object,
+                                // or struct field or interface method?
+                                if obj := info.Info.Defs[id]; obj != nil {
+                                        if obj.Pkg().Scope().Lookup(obj.Name()) == obj {
+                                                // ok: package-level object
+                                                n.objects = append(n.objects, obj)
+                                        } else if v, ok := obj.(*types.Var); ok && v.IsField() {
+                                                // ok: struct field
+                                        } else if _, ok := obj.(*types.Func); ok {
+                                                // ok: concrete method or interface method
+                                        } else {
+                                                return true // ignore
+                                        }
+                                        nodesByObj[obj] = n
+                                }
+                        }
+                        return true
+                })
+        }
+
+        var methods []*ast.FuncDecl
+        for _, f := range info.Files {
+                for _, decl := range f.Decls {
+                        switch decl := decl.(type) {
+                        case *ast.GenDecl:
+                                switch decl.Tok {
+                                case token.CONST:
+                                        // treat decl as one node
+                                        findDefs(o.newNode(info, decl))
+
+                                case token.VAR, token.TYPE:
+                                        // each spec gets its own node
+                                        for _, spec := range decl.Specs {
+                                                findDefs(o.newNode(info, spec))
+                                        }
+                                }
+
+                        case *ast.FuncDecl:
+                                if decl.Recv != nil && *collapseMethods {
+                                        methods = append(methods, decl)
+                                        continue // collapsed method get no node
+                                }
+                                findDefs(o.newNode(info, decl))
+                        }
+                }
+        }
+
+        // -- Pass 2: Refs ----------------------------------------------------
+
+        findRefs := func(n *node, syntax ast.Node) {
+                ast.Inspect(syntax, func(syntax ast.Node) bool {
+                        switch syntax := syntax.(type) {
+                        case *ast.SelectorExpr:
+                                // Selection of struct field or interface method of
+                                // package-level named type?
+                                if sel, ok := info.Info.Selections[syntax]; ok && sel.Obj().Pkg() == info.Pkg {
+                                        //recv := sel.Recv()
+                                        //fmt.Printf("%s: %v\n", o.fset.Position(syntax.Pos()), recv)
+                                        // obj = recvTypeName(recv)
+                                        // TODO(adonovan): don't we need to do something here?
+                                        // Test.
+                                }
+
+                        case *ast.Ident:
+                                // Reference to package-level object?
+                                if obj, ok := info.Info.Uses[syntax]; ok {
+                                        // If --collapse_methods, treat references to methods
+                                        // as references to their receiver type name.
+                                        if recv := methodRecv(obj); recv != nil && *collapseMethods && !isInterface(recv) {
+                                                obj = recvTypeName(recv)
+                                        }
+
+                                        // Need to do the same for struct fields too!
+
+                                        // Only same-package references matter for now.
+                                        // TODO(adonovan): handle external test packages.
+                                        if n2, ok := nodesByObj[obj]; ok {
+                                                // reference to package-level object (or method)
+                                                addEdge(n, n2)
+                                        }
+                                }
+
+                        }
+                        return true
+                })
+        }
+
+        // Concrete method declarations (collapsed with the receiver).
+        for _, decl := range methods {
+                method := info.Info.Defs[decl.Name]
+                recv := recvTypeName(methodRecv(method))
+                // Collapsed method: treat references from this method as
+                // references from its named receiver type.
+                findRefs(nodesByObj[recv], decl)
+        }
+
+        // All other declarations.
+        for _, n := range o.nodes {
+                findRefs(n, n.syntax)
+
+                if decl, ok := n.syntax.(*ast.FuncDecl); ok && decl.Recv != nil {
+                        recv := recvTypeName(methodRecv(info.Info.Defs[decl.Name]))
+
+                        // Add edges from each named receiver type to its methods,
+                        // so they are coupled together.
+                        addEdge(nodesByObj[recv], n)
+                }
+        }
+
+        fmt.Fprintf(os.Stderr, "\t%d nodes\n", len(o.nodes))
+}
+
+// -- SCCs -------------------------------------------------------------

[rsc, 2014/12/12 19:53:23]

Banners like this are discouraged.
http://golang.org/doc/effective_go.html#commentary

[adonovan, 2014/12/12 20:13:00]

Reduced to 4 dashes either side. :)

+
+// An scnode is a node in the scnode graph.
+// It is (approximately; see -fuse) an SCC of the node graph.
+type scnode struct {
+        id           int              // unique id
+        nodes        map[*node]bool   // elements of this SCC
+        succs, preds map[*scnode]bool // scnode graph adjacency sets
+        cluster      *cluster         // the (sole) cluster to which this SCC belongs
+}
+
+const maxLines = 8 // maximum number of lines in a label
+
+func (s *scnode) String() string {
+        var buf bytes.Buffer
+        // Order nodes by exportedness and in-degree.
+        order := make([]*node, 0, len(s.nodes))
+        for n := range s.nodes {
+                order = append(order, n)
+        }
+        sort.Sort(byExportednessAndInDegree(order))
+        for i, n := range order {
+                if i > 0 {
+                        buf.WriteByte('\n')
+                }
+                if i == maxLines-1 && len(order) > maxLines {
+                        fmt.Fprintf(&buf, "+ %d more", len(order)-i)
+                        break
+                }
+                buf.WriteString(n.String())
+        }
+        return buf.String()
+}
+
+type byExportednessAndInDegree []*node
+
+func (b byExportednessAndInDegree) Len() int { return len(b) }
+func (b byExportednessAndInDegree) Less(i, j int) bool {
+        if r := b[i].exportedness() - b[j].exportedness(); r != 0 {
+                return r > 0
+        }
+        if r := len(b[i].preds) - len(b[j].preds); r != 0 {
+                return r > 0
+        }
+        return false
+}
+func (b byExportednessAndInDegree) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
+
+func (o *organizer) makeSCGraph() map[*scnode]bool {
+        // Kosaraju's algorithm---Tarjan is overkill here.
+
+        // Forward pass.
+        S := make([]*node, 0, len(o.nodes)) // postorder stack
+        seen := make(map[*node]bool)
+        var visit func(n *node)
+        visit = func(n *node) {
+                if !seen[n] {
+                        seen[n] = true
+                        for s := range n.succs {
+                                visit(s)
+                        }
+                        S = append(S, n)
+                }
+        }
+
+        for _, n := range o.nodes {
+                visit(n)
+        }
+
+        // Reverse pass.
+        var current *scnode
+        seen = make(map[*node]bool)
+        var rvisit func(d *node)
+        rvisit = func(d *node) {
+                if !seen[d] {
+                        seen[d] = true
+                        current.nodes[d] = true
+                        d.scc = current
+                        for p := range d.preds {
+                                rvisit(p)
+                        }
+                }
+        }
+        scnodes := make(map[*scnode]bool)
+        for len(S) > 0 {
+                top := S[len(S)-1]
+                S = S[:len(S)-1] // pop
+                if !seen[top] {
+                        current = &scnode{
+                                id:      len(scnodes),
+                                cluster: top.cluster,
+                                nodes:   make(map[*node]bool),
+                                succs:   make(map[*scnode]bool),
+                                preds:   make(map[*scnode]bool),
+                        }
+                        rvisit(top)
+                        scnodes[current] = true
+                }
+        }
+
+        // Build the strong-component DAG by
+        // projecting the edges of the node graph,
+        // discarding self-edges.
+        for s := range scnodes {
+                for n := range s.nodes {
+                        for pred := range n.preds {
+                                if s != pred.scc {
+                                        s.preds[pred.scc] = true
+                                }
+                        }
+                        for succ := range n.succs {
+                                if s != succ.scc {
+                                        s.succs[succ.scc] = true
+                                }
+                        }
+                }
+        }
+
+        fmt.Fprintf(os.Stderr, "\t%d SCCs\n", len(scnodes))
+
+        if *fuse {
+                // Now fold each single-predecessor scnode into that predecessor.
+                // Iterate until a fixed point is reached.
+                //
+                // Example:  a -> b -> c
+                //                b -> d
+                // Becomes:  ab -> c
+                //           ab -> d
+                // Then:     abcd
+                //
+                // Since the loop conserves predecessor count for all
+                // non-deleted scnodes, the algorithm is order-invariant.
+                for {
+                        var changed bool
+                        for b := range scnodes {
+                                if b == nil || len(b.preds) != 1 {
+                                        continue
+                                }
+                                var a *scnode
+                                for a = range b.preds {
+                                }
+                                // a is sole predecessor of b
+                                if a.cluster != b.cluster {
+                                        // don't fuse SCCs belonging to different clusters!
+                                        continue
+                                }
+
+                                changed = true
+
+                                b.preds = nil
+                                delete(a.succs, b)
+
+                                // a gets all b's nodes
+                                for n := range b.nodes {
+                                        a.nodes[n] = true
+                                        n.scc = a
+                                }
+                                b.nodes = nil
+
+                                // a gets all b's succs
+                                for c := range b.succs {
+                                        a.succs[c] = true
+                                        c.preds[a] = true
+                                        delete(c.preds, b)
+                                }
+                                b.succs = nil
+
+                                delete(scnodes, b)
+                        }
+                        if !changed {
+                                break
+                        }
+                }
+
+                fmt.Fprintf(os.Stderr, "\t%d SCCs (excluding single-predecessor ones)\n",
+                        len(scnodes))
+        }
+
+        return scnodes
+}
+
+// -- util -------------------------------------------------------------
+
+func recvTypeName(T types.Type) *types.TypeName {

[rsc, 2014/12/12 19:53:23]

It is very unusual in Go to see capitalized local variable names. Please
reconsider.

[adonovan, 2014/12/12 20:13:00]

Agreed, but T seems to have become the default name for vars of type types.Type,
at least between Robert and I.  I have grown quite fond of it.

[rsc, 2014/12/12 21:00:04]

I'm happy for you both but it's not idiomatic Go and it would be great not to
propagate it further. The convention is that T is an exported package-level
name. 't' seems like it would do just fine for a variable of type types.Type.
The whole point of having conventions is to follow them, not to break them
because you grow fond of something else.

+        if ptr, ok := T.(*types.Pointer); ok {
+                T = ptr.Elem()
+        }
+        return T.(*types.Named).Obj()
+}
+
+// methodRecv returns the receiver type of obj,
+// if it's a method, or nil otherwise.
+// TODO(adonovan): move this to go/types.  It gets re-invented a lot.
+func methodRecv(obj types.Object) types.Type {
+        if obj, ok := obj.(*types.Func); ok {
+                recv := obj.Type().(*types.Signature).Recv()
+                if recv != nil {
+                        return recv.Type()
+                }
+        }
+        return nil
+}
+
+// isInterface reports whether T's underlying type is an interface.
+func isInterface(T types.Type) bool {
+        _, ok := T.Underlying().(*types.Interface)
+        return ok
+}
+
+// from go/ast
+func IsExported(name string) bool {
+        ch, _ := utf8.DecodeRuneInString(name)
+        return unicode.IsUpper(ch)
+}