DEV Community

Cover image for Finding cycles and hidden dependencies in go mod graph
Hamed Yousefi
Hamed Yousefi

Posted on Originally published at hmdsefi.hashnode.dev AI-assisted

Finding cycles and hidden dependencies in go mod graph

#go #opensource #devops #tutorial

go mod graph prints every requirement in your module graph, one per line. For Prometheus that's 2,510 lines covering 893 module versions. All the information is there, but not in a form you can read. Questions like "do any of these modules require each other?", "what depends on this module?" or "what did this pull request change in my dependencies?" turn into a lot of grep.

The output is a graph, so I loaded it into gograph, the graph library I maintain, and wrote a small program, gomodgraph, that answers those questions. Each command turns out to be a few lines on top of a standard graph algorithm. This post walks through them, with real output from Prometheus. The same algorithms are on gograph.dev, on graphs small enough to step through.

You can run it on your own module with:

go mod graph | go run github.com/hmdsefi/gograph/examples/gomodgraph@latest cycles
Enter fullscreen mode Exit fullscreen mode

Loading the graph

Each line of go mod graph is from to, meaning from requires to:

github.com/prometheus/prometheus cloud.google.com/go/auth@v0.23.3
golang.org/x/crypto@v0.57.0 golang.org/x/net@v0.58.0
Enter fullscreen mode Exit fullscreen mode

The main module has no version, and every other module is written as path@version. Each line becomes one edge:

g := gograph.New[string](gograph.Directed())

scanner := bufio.NewScanner(r)
for scanner.Scan() {
    fields := strings.Fields(scanner.Text())
    if len(fields) != 2 {
        continue
    }
    from, to := fields[0], fields[1]
    _, _ = g.AddEdge(vertex(g, from), vertex(g, to))
}
Enter fullscreen mode Exit fullscreen mode

vertex returns the vertex with that label, or adds it if it's new. The real program also skips the go@ and toolchain@ lines, which aren't modules.

The direction matters for everything that follows. With an edge from -> to, the dependencies of a module are the vertices it can reach, and the modules that depend on it are the vertices that can reach it.

Cycles

Requirement cycles are allowed in Go, and they're common between modules that are released together. They're usually harmless, but they mean that upgrading any module in the cycle raises the others too. That's good to know when an upgrade pulls in more than you expected.

In a directed graph, a cycle is a strongly connected component with more than one vertex. gograph has three algorithms for these. The example uses Tarjan's:

for _, component := range connectivity.Tarjan(g) {
    if len(component) < 2 {
        continue
    }
    labels := make([]string, len(component))
    for i, v := range component {
        labels[i] = v.Label()
    }
    sort.Strings(labels)
    fmt.Println(strings.Join(labels, " "))
}
Enter fullscreen mode Exit fullscreen mode

On Prometheus it finds one cycle:

$ gomodgraph -f graph.txt cycles
go.opentelemetry.io/otel/metric@v1.46.0 go.opentelemetry.io/otel/trace@v1.46.0 go.opentelemetry.io/otel@v1.46.0
Enter fullscreen mode Exit fullscreen mode

otel requires otel/metric and otel/trace, and both of them require otel back. They're released from the same repository with the same version, so that's expected. Loading the graph and finding the cycle takes about 10 ms on my laptop. On a small call graph, the same finder is Tarjan on gograph.dev. The number on that page is measured on the server, separate from this laptop run.

Dependents

"What depends on this module?" means "which vertices can reach it?" The example builds a reversed copy of the graph and walks it breadth-first from each version of the module:

reversed := gograph.New[string](gograph.Directed())
for _, e := range g.AllEdges() {
    _, _ = reversed.AddEdge(
        vertex(reversed, e.Destination().Label()),
        vertex(reversed, e.Source().Label()),
    )
}

it, err := traverse.NewBreadthFirstIterator(reversed, "github.com/golang/protobuf@v1.3.2")
if err != nil {
    return err
}
for it.HasNext() {
    fmt.Println(it.Next().Label())
}
Enter fullscreen mode Exit fullscreen mode

gograph 0.8 also has a dag package, and dag.Ancestors(g, label) does the same walk without building a second graph. Its names follow the build graph convention, where A -> B means "B depends on A". For a requirement graph like this one the meanings swap, so Ancestors returns the dependents.

In Prometheus, 39 modules require some version of github.com/golang/protobuf, directly or indirectly:

$ gomodgraph -f graph.txt dependents github.com/golang/protobuf
github.com/armon/go-metrics@v0.4.1
github.com/envoyproxy/go-control-plane/envoy@v1.39.0
github.com/google/s2a-go@v0.1.10
github.com/hashicorp/consul/api@v1.34.5
...
Enter fullscreen mode Exit fullscreen mode

A shorter walk of the same kind is breadth-first search on gograph.dev.

Why is this module here?

go mod why -m answers a related question, but it looks at the package import graph. It shows which chain of imports needs a module. For a module that no package imports, it prints (main module does not need module ...), even though the module is still in the graph and in go.sum. The requirement graph answers the other half: which chain of go.mod files brought it in.

In a graph where every edge has the same cost, the shortest path comes from a breadth-first search. The iterator returns vertices in order of distance, so the first vertex that has an edge to a new vertex is on a shortest path to it. matches accepts either a module path, which matches every version, or path@version:

parent := map[string]string{start: ""}
for it.HasNext() {
    v := it.Next()
    if v.Label() != start && matches(v.Label(), module) {
        var path []string
        for label := v.Label(); label != ""; label = parent[label] {
            path = append([]string{label}, path...)
        }
        return path
    }
    for _, n := range v.Neighbors() {
        if _, ok := parent[n.Label()]; !ok {
            parent[n.Label()] = v.Label()
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

The output uses the format of go mod why -m:

$ gomodgraph -f graph.txt why github.com/golang/protobuf
# github.com/golang/protobuf
github.com/prometheus/prometheus
github.com/armon/go-metrics@v0.4.1
github.com/golang/protobuf@v1.3.2
Enter fullscreen mode Exit fullscreen mode

Ancestors on gograph.dev answers the same question on a module graph small enough to draw.

What changed between two versions?

Module versions are vertices and requirements are edges, so comparing two graphs takes two set differences. A module version is removed if the new graph doesn't contain its vertex, and a requirement is removed if the new graph doesn't contain its edge:

for _, v := range oldGraph.GetAllVertices() {
    if !newGraph.ContainsVertex(v) {
        fmt.Println("- module", v.Label())
    }
}
for _, e := range oldGraph.AllEdges() {
    if !newGraph.ContainsEdge(e.Source(), e.Destination()) {
        fmt.Println("- require", e.Source().Label(), e.Destination().Label())
    }
}
Enter fullscreen mode Exit fullscreen mode

The same loops with the graphs swapped print what was added. Between Prometheus v3.14.0 and v3.15.0, 277 module versions left the graph and 235 came in, and 1,472 requirements were removed while 1,504 were added. Most of that is version bumps deep in the graph. The lines for the main module show the direct changes. Here are the golang.org/x ones:

$ gomodgraph diff v3.14.0.txt v3.15.0.txt | grep 'require github.com/prometheus/prometheus golang.org/x/'
- require github.com/prometheus/prometheus golang.org/x/crypto@v0.54.0
- require github.com/prometheus/prometheus golang.org/x/mod@v0.38.0
- require github.com/prometheus/prometheus golang.org/x/net@v0.57.0
- require github.com/prometheus/prometheus golang.org/x/text@v0.40.0
- require github.com/prometheus/prometheus golang.org/x/tools@v0.48.0
+ require github.com/prometheus/prometheus golang.org/x/crypto@v0.56.0
+ require github.com/prometheus/prometheus golang.org/x/net@v0.58.0
+ require github.com/prometheus/prometheus golang.org/x/text@v0.41.0
Enter fullscreen mode Exit fullscreen mode

Three of them are upgrades. golang.org/x/mod and golang.org/x/tools have a - line and no + line, so v3.15.0 doesn't list them in its go.mod any more. That's easy to miss in a go.mod diff with dozens of changed lines.

Running it on pull requests

The example's README has a GitHub Actions workflow that runs go mod graph on the base and head commits of a pull request and posts the diff as a comment. That way, reviewers see what a dependency bump pulls in before they approve it.

Watching it run

The Prometheus graph is too big to draw step by step. gograph.dev runs the same algorithms on small graphs, and the timing on each page is measured on the server when the site starts, on the released library.

Wrapping up

The whole program is about 340 lines, and most of that is argument parsing and output. The graph work is a Tarjan call, two breadth-first searches and a few set checks.

gograph is a generic graph library with no dependencies outside the standard library. It covers dependency graphs (Acyclic() graphs that reject cycles, TopologySort, and the dag package), traversal, shortest paths, strongly connected components and partitioning, and encoding/mermaid writes any graph as a Mermaid flowchart. Version 0.8 made the order of vertices and edges predictable, so results are the same on every run. I wrote about how that works in an earlier post.

If you run it on your own module and find something surprising, I'd like to hear about it.

Top comments (2)

Collapse
 
kashif_manzer profile image
Kashif Manzer •

Nice writeup. One command I would add: flag modules that appear at multiple versions, since go mod graph lists every requirement while MVS silently picks the highest, so the graph alone never tells you which version actually builds. A versions command that groups vertices by module path would show exactly where a bump never took effect, which is the kind of surprise you want the PR diff to catch.

Collapse
 
hamed_yousefi profile image
Hamed Yousefi •

Good idea, and I tried it on the same Prometheus graph from the post. In v3.15.0, 151 of the 414 module paths show up at more than one version, and golang.org/x/sys alone shows up at 41.

The graph does carry the answer: MVS picks the highest version of each path in it, and for all 414 paths that matched go list -m all. The hard part is reading it, and grouping by module path is exactly what makes it readable.

It would help the PR diff a lot too. Between v3.14.0 and v3.15.0, the diff command prints 3,488 lines of module and requirement changes. Comparing the selected version of each path gives 171: 144 version changes, 12 new modules and 15 removed. That's the list a reviewer wants to see.

I opened an issue for it: github.com/hmdsefi/gograph/issues/246. gomodgraph gets a versions command that groups the vertices by module path, marks the version that builds and lists who requires each version, plus a diff of those selected versions for the pull request comment. It ships in gograph 0.9 on Oct 19.