Compositionality of Libraries

implements.go

package main

import (
	"go/types"
	"log"

	"golang.org/x/tools/go/packages"
)

func loadNamedTypes(packages map[string]*packages.Package) []*types.Named {
	var allNamed []*types.Named
	for _, info := range packages {
		if info.TypesInfo == nil {
			log.Printf("%v has no types info\n%#v", info, info)
			continue
		}
		for _, obj := range info.TypesInfo.Defs {
			if obj, ok := obj.(*types.TypeName); ok && !isAlias(obj) {
				if named, ok := obj.Type().(*types.Named); ok {
					allNamed = append(allNamed, named)
				}
			}
		}
	}
	return allNamed
}

func loadFuncs(packages map[string]*packages.Package) []*types.Func {
	var funcs []*types.Func

	for _, info := range packages {
		if info.TypesInfo == nil {
			log.Printf("%v has no types info\n%#v", info, info)
			continue
		}
		for _, obj := range info.TypesInfo.Defs {
			if obj, ok := obj.(*types.Func); ok {
				funcs = append(funcs, obj)
			}
		}
	}
	return funcs
}

func filterInterfaces(a []*types.Named) (retVal []*types.Interface) {
	for _, t := range a {
		if isInterface(t) {
			retVal = append(retVal, t.Underlying().(*types.Interface))
		}
	}
	return retVal
}

func implements(t *types.Interface, list []*types.Named) (retVal []*types.Named) {
	for _, u := range list {
		if types.Implements(u, t) {
			retVal = append(retVal, u)
		}
	}
	return
}

func filter(a []*types.Named, fn func(types.Type) bool) (retVal []*types.Named) {
	for _, t := range a {
		if fn(t) {
			retVal = append(retVal, t)
		}
	}
	return retVal
}

func isInterface(T types.Type) bool {
	if !types.IsInterface(T) {
		return false
	}
	return !(T.Underlying().(*types.Interface).Empty())
}
func isAlias(obj *types.TypeName) bool { return obj.IsAlias() }
func isFunc(T types.Type) bool         { _, ok := T.Underlying().(*types.Signature); return ok }

func namedToInterfaces(a []*types.Named) []*types.Interface {
	retVal := make([]*types.Interface, len(a))
	for i := range a {
		retVal[i] = a[i].Underlying().(*types.Interface)
	}
	return retVal
}

main.go

package main

import (
	"go/types"
	"io/ioutil"
	"log"
	"os"
	"path"
	"path/filepath"
	"strings"
	"sync"

	"golang.org/x/tools/go/packages"
	"gonum.org/v1/gonum/graph/encoding/dot"
	"gonum.org/v1/gonum/graph/simple"
)

func main() {

	gopath := os.Getenv("GOPATH")
	if gopath == "" {
		gopath = path.Join(os.Getenv("HOME"), "go")
	}

	gopathPkgs := make(map[string]*packages.Package)

	var mut sync.Mutex
	var dirs []string
	walk := func(p string, info os.FileInfo, err error) error {
		if err != nil {
			return err
		}
		b := path.Base(p)
		switch b {
		// ATTENTION
		case  "llvm.org", "shiny":
			return filepath.SkipDir

		default:
			if strings.HasPrefix(b, ".") || strings.Contains(p, "golang.org/x/mobile") || strings.Contains(p, "llvm") {
				return filepath.SkipDir
			}
		}

		if info.IsDir() {
			fileList, _ := filepath.Glob("*.go")
			hasgo := len(fileList) > 0
			mut.Lock()
			if hasgo {
				dirs = append(dirs, strings.TrimPrefix(p, path.Join(gopath, "src/")+"/..."))
			}

			mut.Unlock()
		}
		return nil
	}

	src := path.Join(gopath, "src")
	die(filepath.Walk(src, walk))
	//	dirs = append(dirs, "gonum.org/v1/gonum/...", "github.com/chewxy/lingo", "github.com/chewxy/gogogadget", "github.com/chewxy/InkHuffer", "github.com/chewxy/math32", "github.com/chewxy/hm", "github.com/chewxy/sexp", "github.com/chewxy/skiprope", "go-hep.org/x/hep/...", "github.com/boyter/scc/...")

	cfg := &packages.Config{Mode: packages.NeedFiles | packages.NeedSyntax | packages.NeedTypesInfo | packages.NeedTypes | packages.NeedImports | packages.NeedDeps, Tests: false, Dir: gopath}
	ps, err := packages.Load(cfg, dirs...)
	die(err)

	for _, pkg := range ps {
		gopathPkgs[pkg.ID] = pkg
	}
	log.Printf("dirs %v", dirs)
	log.Printf("Packages %d %d %d", len(ps), len(gopathPkgs), len(dirs))

	allNamed := loadNamedTypes(gopathPkgs)
	allFuncs := loadFuncs(gopathPkgs)
	ifaces := filter(allNamed, isInterface)
	log.Printf("allNamed Types %d. Interface Types: %d, Function Types %d", len(allNamed), len(ifaces), len(allFuncs))

	var allPackages []packageID
	lookup := make(map[string]int)
	pkgIn := make(map[packageID]map[packageID]struct{})  // pkg -> list of packages that requires pkg (unique)
	pkgOut := make(map[packageID]map[packageID]struct{}) // pkg -> list of packages that pkg provides an interface to (unique)

	addPackage := func(pkg *types.Package) int {
		allPackages = append(allPackages, packageID{pkg.Path(), 0})
		pid := len(allPackages) - 1
		allPackages[pid].id = pid
		lookup[pkg.Path()] = pid
		return pid
	}
	addInDeg := func(from, to *types.Package) {
		fromID, ok := lookup[from.Path()]
		if !ok {
			fromID = addPackage(from)
		}
		fromPkg := allPackages[fromID]

		toID, ok := lookup[to.Path()]
		if !ok {
			toID = addPackage(to)
		}
		toPkg := allPackages[toID]

		m, ok := pkgIn[toPkg]
		if !ok {
			pkgIn[toPkg] = make(map[packageID]struct{})
			m = pkgIn[toPkg]
		}
		m[fromPkg] = struct{}{}
	}

	addOutDeg := func(from, to *types.Package) {
		fromID, ok := lookup[from.Path()]
		if !ok {
			fromID = addPackage(from)
		}
		fromPkg := allPackages[fromID]

		toID, ok := lookup[to.Path()]
		if !ok {
			toID = addPackage(to)
		}
		toPkg := allPackages[toID]

		m, ok := pkgOut[fromPkg]
		if !ok {
			pkgIn[fromPkg] = make(map[packageID]struct{})
			m = pkgIn[fromPkg]
		}
		m[toPkg] = struct{}{}
	}
	/*
		for _, pkg := range ps {
			allPackages = append(allPackages, packageID{pkg.ID, 0})
			pid := len(allPackages) - 1
			allPackages[pid].id = pid
		}
	*/
	// first, all types
	for _, nt := range ifaces {
		pkg := nt.Obj().Pkg()
		T := nt.Underlying().(*types.Interface)
		list := implements(T, allNamed)

		log.Printf("interface type %v in %v. %d implementors", nt.Obj().Name(), pkg, len(list))
		if strings.Contains(pkg.Name(), "gorgonia") {
			log.Printf("%v", list)
		}

		for _, t := range list {
			tpkg := t.Obj().Pkg()
			addInDeg(tpkg, pkg)
			addOutDeg(tpkg, pkg)
		}
	}

	// then functions
	for _, fn := range allFuncs {
		fnPkg := fn.Pkg()
		sig := fn.Type().(*types.Signature)
		params := sig.Params()
		for i := 0; i < params.Len(); i++ {
			if isInterface(params.At(i).Type()) {
				Tpkg := params.At(i).Pkg()
				if Tpkg == fnPkg {
					continue
				}

				addOutDeg(fnPkg, Tpkg)
			}
		}
	}

	g := newGraph(allPackages, pkgIn, pkgOut)
	data, err := dot.Marshal(g, "", "", "")
	die(err)
	ioutil.WriteFile("foo.dot", data, 0666)

}

type packageID struct {
	name string
	id   int
}

func (p packageID) ID() int64 { return int64(p.id) }

func (p packageID) DOTID() string { return p.name }
func newGraph(all []packageID, in, out map[packageID]map[packageID]struct{}) *simple.DirectedGraph {
	g := simple.NewDirectedGraph()
	for i := range all {
		g.AddNode(all[i])
	}
	for to, froms := range in {
		for from := range froms {
			if from.id == to.id {
				continue
			}
			g.SetEdge(g.NewEdge(from, to))
		}
	}
	for from, tos := range out {
		for to := range tos {
			if from.id == to.id {
				continue
			}
			g.SetEdge(g.NewEdge(from, to))
		}
	}
	return g
}

func die(err error) {
	if err != nil {
		panic(err)
	}
}