[tools] internal/{graph,flow}: monotone flow analysis framework
Austin Clements (Gerrit)
Austin Clements has uploaded the change for review![]( "Open in Gerrit")
Austin Clements would like Alan Donovan to review this change.
Commit message
internal/{graph,flow}: monotone flow analysis framework
This implements a generic monotone flow analysis framework, itself
built on a simple directed graph package.Change diff
diff --git a/internal/flow/flow.go b/internal/flow/flow.go
new file mode 100644
index 0000000..57602b0
--- /dev/null
+++ b/internal/flow/flow.go
@@ -0,0 +1,53 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package flow implements a monotone flow analysis framework.
+package flow
+
+import (
+ "cmp"
+ "slices"
+
+ "golang.org/x/tools/internal/graph"
+)
+
+const debug = false
+
+// Analysis is the result of a monotone analysis. It records the analysis fact
+// on entry to each block and for each successor.
+type Analysis[Fact any, NodeID comparable] struct {
+ nodeMap *graph.NodeMap[NodeID]
+ ins []Fact // By NodeID
+ edges []edgeFact[Fact] // Sorted by (from, to)
+}
+
+// In returns the analysis fact on entry to nid. This is the merge of the facts
+// on all incoming edges.
+func (f *Analysis[Fact, NodeID]) In(nid NodeID) Fact {
+ return f.ins[f.nodeMap.Compact(nid)]
+}
+
+// Edge returns the analysis fact propagated on edge from ==> to.
+func (f *Analysis[Fact, NodeID]) Edge(from, to NodeID) Fact {
+ fromNum, toNum := f.nodeMap.Compact(from), f.nodeMap.Compact(to)
+ i, found := slices.BinarySearchFunc(f.edges, graph.Edge[nodeNum]{Pred: fromNum, Succ: toNum}, func(e edgeFact[Fact], k graph.Edge[nodeNum]) int {
+ return compareEdge(e.Edge, k)
+ })
+ if !found {
+ panic("no such edge")
+ }
+ return f.edges[i].fact
+}
+
+func compareEdge(e, f graph.Edge[nodeNum]) int {
+ if e.Pred != f.Pred {
+ return cmp.Compare(e.Pred, f.Pred)
+ }
+ return cmp.Compare(e.Succ, f.Succ)
+}
+
+type edgeFact[Fact any] struct {
+ graph.Edge[nodeNum]
+ fact Fact
+}
diff --git a/internal/flow/forward.go b/internal/flow/forward.go
new file mode 100644
index 0000000..8461bd5
--- /dev/null
+++ b/internal/flow/forward.go
@@ -0,0 +1,253 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package flow
+
+import (
+ "container/heap"
+ "fmt"
+ "slices"
+
+ "golang.org/x/tools/internal/graph"
+)
+
+// Forward performs a forward monotone analysis over a control flow graph.
+//
+// The entry map provides initial state for entry blocks (blocks with zero
+// predecessors). For each edge, it calls transfer(fact, edge), where fact is
+// the analysis state on entry to edge.Pred. The transfer function must return
+// the outgoing analysis state of the edge (which may be fact, if the edge has
+// no effect on the analysis state).
+func Forward[L Semilattice[Fact], Fact any, NodeID comparable](g graph.Graph[NodeID], entry map[NodeID]Fact, transfer func(Fact, graph.Edge[NodeID]) Fact) *Analysis[Fact, NodeID] {
+ cg, nodeMap := graph.Compact(g)
+
+ nNodes := cg.NumNodes()
+ fb := &fwdBuilder[L, Fact, NodeID]{
+ cfg: cg,
+ nodeMap: nodeMap,
+ transfer: transfer,
+ blocks: make([]blockInfo[Fact], nNodes),
+ }
+ fb.queue.init(cg)
+
+ // Initialize each node.
+ totalEdges := 0
+ for ni := range nNodes {
+ b := &fb.blocks[ni]
+
+ // Construct back-edges.
+ //
+ // I experimented with making Graph support iterating over in-edges, but
+ // in practice that just meant each Graph implementation had a copy of
+ // this logic. So instead we keep Graph as simple as possible and
+ // compute the auxiliary data in the algorithm. One drawback of this is
+ // that, for the [Transpose] graph, this information is redundant with
+ // the underlying graph. We could potentially special-case that.
+ outs := 0
+ for _, succID := range cg.Out(ni) {
+ succ := &fb.blocks[succID]
+ succ.preds = append(succ.preds, blockEdge{ni, outs})
+ outs++
+ totalEdges++
+ }
+
+ // Initialize in & out states.
+ if fact, ok := entry[nodeMap.NodeID(ni)]; ok {
+ b.in = fact
+ } else {
+ b.in = fb.l.Ident()
+ }
+ b.out = make([]Fact, outs)
+ for i := range b.out {
+ b.out[i] = fb.l.Ident()
+ }
+
+ // Enqueue block.
+ //
+ // It's tempting to enqueue only the entry blocks, but this is wrong.
+ // The entry map may be empty if there are no interesting entry states,
+ // but the transfer function may still introduce interesting states
+ // anywhere.
+ b.dirty = true
+ fb.queue.enqueue(ni)
+ }
+
+ // Propagate over blocks.
+ fb.propagate()
+
+ // Collect the final analysis results.
+ a := Analysis[Fact, NodeID]{
+ nodeMap: nodeMap,
+ ins: make([]Fact, nNodes),
+ edges: make([]edgeFact[Fact], totalEdges),
+ }
+ for pred := range nNodes {
+ a.ins[pred] = fb.blocks[pred].in
+ for i, succ := range cg.Out(pred) {
+ a.edges = append(a.edges, edgeFact[Fact]{graph.Edge[nodeNum]{Pred: pred, Succ: succ}, fb.blocks[pred].out[i]})
+ }
+ }
+ slices.SortFunc(a.edges, func(a, b edgeFact[Fact]) int { return compareEdge(a.Edge, b.Edge) })
+ return &a
+}
+
+// nodeNum is a compactly numbered node. It's an alias for int purely for
+// documentation purposes.
+type nodeNum = int
+
+// fwdBuilder is the state used during [Forward] analysis.
+type fwdBuilder[L Semilattice[Fact], Fact any, NodeID comparable] struct {
+ l L // Lattice
+
+ cfg graph.CompactGraph // Control flow graph
+ nodeMap *graph.NodeMap[NodeID] // Map from cfg to original NodeIDs
+
+ // transfer is the edge transfer function.
+ transfer func(Fact, graph.Edge[NodeID]) Fact
+
+ blocks []blockInfo[Fact]
+
+ queue nodeHeap
+}
+
+type blockInfo[Fact any] struct {
+ dirty bool // The in fact has never been propagated.
+
+ preds []blockEdge
+
+ in Fact
+ out []Fact // Corresponds to i'th out edge
+}
+
+type blockEdge struct {
+ node nodeNum
+ i int // Out edge index
+}
+
+// nodeHeap implements a heap of NodeIDs, ordered topologically.
+//
+// We use this ordering so forward analysis converges more quickly.
+type nodeHeap struct {
+ heap []nodeNum
+ inQueue []int64 // Bitmap over node IDs
+ prio []int // NodeID -> priority
+}
+
+func (h *nodeHeap) init(g graph.CompactGraph) {
+ nNodes := g.NumNodes()
+ *h = nodeHeap{
+ inQueue: make([]int64, (nNodes+63)/64),
+ prio: make([]int, nNodes),
+ }
+ for p, nid := range graph.ReversePostorder(g) {
+ h.prio[nid] = p
+ }
+}
+
+func (h *nodeHeap) enqueue(nid nodeNum) {
+ if h.inQueue[nid/64]&(1<<(nid%64)) != 0 {
+ return
+ }
+ h.inQueue[nid/64] |= 1 << (nid % 64)
+ heap.Push(h, nid)
+}
+
+func (h *nodeHeap) dequeue() nodeNum {
+ nid := h.heap[0]
+ heap.Pop(h)
+ h.inQueue[nid/64] &^= 1 << (nid % 64)
+ return nid
+}
+
+func (h nodeHeap) Len() int { return len(h.heap) }
+func (h nodeHeap) Less(i, j int) bool { return h.prio[h.heap[i]] < h.prio[h.heap[j]] }
+func (h nodeHeap) Swap(i, j int) { h.heap[i], h.heap[j] = h.heap[j], h.heap[i] }
+func (h *nodeHeap) Push(x any) { h.heap = append(h.heap, x.(nodeNum)) }
+func (h *nodeHeap) Pop() any {
+ n := len(h.heap)
+ x := h.heap[n-1]
+ h.heap = h.heap[:n-1]
+ return x
+}
+
+func (fb *fwdBuilder[L, Fact, NodeID]) merge(a, b Fact) Fact {
+ if fb.l.Equals(a, b) {
+ return a
+ }
+ return fb.l.Merge(a, b)
+}
+
+func (fb *fwdBuilder[L, Fact, NodeID]) propagate() {
+ for fb.queue.Len() > 0 {
+ bi := fb.queue.dequeue()
+ block := &fb.blocks[bi]
+
+ // Merge predecessor facts to compute updated "in" fact.
+ var in Fact
+ first := true
+ for _, edge := range block.preds {
+ pred := &fb.blocks[edge.node]
+ var edgeFact Fact
+ if pred.dirty {
+ // We haven't visited this predecessor yet, so it doesn't have
+ // meaningful out facts.
+ edgeFact = fb.l.Ident()
+ } else {
+ edgeFact = pred.out[edge.i]
+ }
+ if first {
+ if debug {
+ fmt.Printf("propagate to node %d\n", bi)
+ }
+ in = edgeFact
+ first = false
+ } else {
+ in = fb.merge(in, edgeFact)
+ }
+ if debug {
+ fmt.Printf(" from node %d: %v\n", edge.node, edgeFact)
+ }
+ }
+ if first {
+ // No predecessors.
+ if debug {
+ fmt.Printf("node %d gets initial state\n", bi)
+ }
+ in = block.in
+ }
+
+ if !block.dirty && fb.l.Equals(in, block.in) {
+ // No change to block input, which means the transfer function
+ // results also won't change from the last time we ran it.
+ if debug {
+ fmt.Printf(" initial state unchanged: %v\n", in)
+ }
+ continue
+ }
+ if debug {
+ fmt.Printf(" new initial state: %v\n", in)
+ }
+ block.in = in
+
+ // Apply transfer function.
+ predID := fb.nodeMap.NodeID(bi)
+ for i, succNum := range fb.cfg.Out(bi) {
+ edgeFact := fb.transfer(in, graph.Edge[NodeID]{Pred: predID, Succ: fb.nodeMap.NodeID(succNum)})
+ if block.dirty || !fb.l.Equals(block.out[i], edgeFact) {
+ // Out fact changed, so recompute the target block.
+ if debug {
+ fmt.Printf(" to node %d: %v\n", succNum, edgeFact)
+ }
+ block.out[i] = edgeFact
+ fb.queue.enqueue(succNum)
+ } else {
+ if debug {
+ fmt.Printf(" to node %d: no change\n", succNum)
+ }
+ }
+ }
+
+ block.dirty = false
+ }
+}
diff --git a/internal/flow/forward_test.go b/internal/flow/forward_test.go
new file mode 100644
index 0000000..c105775
--- /dev/null
+++ b/internal/flow/forward_test.go
@@ -0,0 +1,246 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package flow
+
+import (
+ "iter"
+ "math/rand"
+ "testing"
+ "time"
+
+ "golang.org/x/tools/internal/graph"
+)
+
+type simpleGraph struct {
+ numNodes int
+ edges [][]nodeNum
+}
+
+func (g *simpleGraph) NumNodes() int {
+ return g.numNodes
+}
+
+func (g *simpleGraph) All() iter.Seq[nodeNum] {
+ return func(yield func(nodeNum) bool) {
+ for i := range g.numNodes {
+ if !yield(i) {
+ break
+ }
+ }
+ }
+}
+
+func (g *simpleGraph) Out(nid nodeNum) iter.Seq2[int, nodeNum] {
+ return func(yield func(int, nodeNum) bool) {
+ for i, succ := range g.edges[nid] {
+ if !yield(i, succ) {
+ return
+ }
+ }
+ }
+}
+
+func checkAnalysis[Fact comparable](t *testing.T, analysis *Analysis[Fact, nodeNum], wantIns map[int]Fact, wantEdges map[[2]int]Fact) {
+ t.Helper()
+ for nid, want := range wantIns {
+ if got := analysis.In(nid); got != want {
+ t.Errorf("In(%d): got %v, want %v", nid, got, want)
+ }
+ }
+
+ for edge, want := range wantEdges {
+ from, to := edge[0], edge[1]
+ if got := analysis.Edge(from, to); got != want {
+ t.Errorf("Edge(%d, %d): got %v, want %v", from, to, got, want)
+ }
+ }
+}
+
+func TestBasic(t *testing.T) {
+ // Define a trivial graph of 4 nodes in sequence: 0 -> 1 -> 2 -> 3
+ g := &simpleGraph{
+ numNodes: 4,
+ edges: [][]nodeNum{
+ 0: {1},
+ 1: {2},
+ 2: {3},
+ 3: {},
+ },
+ }
+
+ // Transfer function: OR source node's ID into the bitset.
+ transfer := func(fact nodeSet, edge graph.Edge[nodeNum]) nodeSet {
+ return fact | (1 << uint(edge.Pred))
+ }
+
+ analysis := Forward[nodeSetUnion](g, nil, transfer)
+
+ checkAnalysis(t, analysis,
+ map[int]nodeSet{
+ 0: 0,
+ 1: set(0),
+ 2: set(0, 1),
+ 3: set(0, 1, 2),
+ },
+ map[[2]int]nodeSet{
+ {0, 1}: set(0),
+ {1, 2}: set(0, 1),
+ {2, 3}: set(0, 1, 2),
+ },
+ )
+}
+
+func TestDiamond(t *testing.T) {
+ // Diamond graph:
+ // 0
+ // / \
+ // 1 2
+ // \ /
+ // 3
+ g := &simpleGraph{
+ numNodes: 4,
+ edges: [][]nodeNum{
+ 0: {1, 2},
+ 1: {3},
+ 2: {3},
+ 3: {},
+ },
+ }
+
+ transfer := func(fact nodeSet, edge graph.Edge[nodeNum]) nodeSet {
+ return fact | (1 << edge.Pred)
+ }
+
+ analysis := Forward[nodeSetUnion](g, nil, transfer)
+
+ checkAnalysis(t, analysis,
+ map[int]nodeSet{
+ 0: 0,
+ 1: set(0), // Edge (0, 1) carries NodeID 0
+ 2: set(0), // Edge (0, 2) carries NodeID 0
+ 3: set(0, 1, 2),
+ },
+ map[[2]int]nodeSet{
+ {0, 1}: set(0),
+ {0, 2}: set(0),
+ {1, 3}: set(0, 1),
+ {2, 3}: set(0, 2),
+ },
+ )
+}
+
+func TestCycle(t *testing.T) {
+ // Graph with a cycle:
+ // 0 -> 1 -> 2
+ // ^ |
+ // +----+
+ g := &simpleGraph{
+ numNodes: 3,
+ edges: [][]nodeNum{
+ 0: {1},
+ 1: {2},
+ 2: {1},
+ },
+ }
+
+ transfer := func(fact nodeSet, edge graph.Edge[nodeNum]) nodeSet {
+ return fact | (1 << edge.Pred)
+ }
+
+ analysis := Forward[nodeSetUnion](g, nil, transfer)
+
+ checkAnalysis(t, analysis,
+ map[int]nodeSet{
+ 0: 0,
+ 1: set(0, 1, 2),
+ 2: set(0, 1, 2),
+ },
+ map[[2]int]nodeSet{
+ {0, 1}: set(0),
+ {1, 2}: set(0, 1, 2),
+ {2, 1}: set(0, 1, 2),
+ },
+ )
+}
+
+func TestFlowOrder(t *testing.T) {
+ // This test constructs a "Spine with Bottleneck" graph in which a naive
+ // visit order would result in quadratic time.
+ //
+ // Structure:
+ // - Spine: Chain 0 -> 1 -> ... -> T-1.
+ // - Bottleneck: All spine nodes (0..T-1) also point to T.
+ // - Tail: T begins a chain T -> T+1 -> ... -> N-1.
+ //
+ // However, we randomly permute the node IDs to prevent a "lucky" order
+ // derived from the node IDs.
+ //
+ // With a naive order, updates to T from the spine would arrive one by one
+ // (or in small batches), triggering re-evaluation of the entire tail
+ // multiple times, and O(T*N) transfer calls.
+ //
+ // With RPO, T is evaluated once after all spine nodes are processed.
+
+ T := 64 // Max ID allowed by nodeSet
+ N := 2 * T
+
+ // Permute IDs to prevent "lucky" ordering.
+ perm := rand.New(rand.NewSource(42)).Perm(N)
+ invPerm := make([]int, N)
+ for i, p := range perm {
+ invPerm[p] = i
+ }
+ // node maps a logical node ID to a permuted NodeID.
+ node := func(logical int) nodeNum {
+ return nodeNum(perm[logical])
+ }
+
+ // Build the edges.
+ edges := make([][]nodeNum, N)
+ nEdges := 0
+ addEdge := func(u, v int) {
+ uID := node(u)
+ edges[uID] = append(edges[uID], node(v))
+ nEdges++
+ }
+ // Spine: 0 -> 1 -> ... -> T-1
+ for i := range T {
+ if i+1 != T {
+ addEdge(i, i+1)
+ }
+ addEdge(i, T)
+ }
+ // Tail: T -> T+1 -> ... -> N-1
+ for i := T; i < N-2; i++ {
+ addEdge(i, i+1)
+ }
+
+ g := &simpleGraph{
+ numNodes: N,
+ edges: edges,
+ }
+
+ transfers := 0
+ // Transfer: if pred is on the spine (< T), set its bit.
+ transfer := func(in nodeSet, edge graph.Edge[nodeNum]) nodeSet {
+ transfers++
+ logicalPred := invPerm[edge.Pred]
+ if logicalPred < T {
+ return in | (1 << uint64(logicalPred))
+ }
+ return in
+ }
+
+ // Measure flow.Forward (RPO)
+ start := time.Now()
+ _ = Forward[nodeSetUnion](g, nil, transfer)
+ durRPO := time.Since(start)
+ t.Logf("RPO time: %v", durRPO)
+
+ // RPO should result in optimal evaluation, visiting each edge exactly once.
+ if transfers != nEdges {
+ t.Errorf("got %d transfer calls, expected %d for optimal evaluation strategy", transfers, nEdges)
+ }
+}
diff --git a/internal/flow/lattice.go b/internal/flow/lattice.go
new file mode 100644
index 0000000..d6c0c0e
--- /dev/null
+++ b/internal/flow/lattice.go
@@ -0,0 +1,105 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package flow
+
+import "fmt"
+
+// A Semilattice describes a bounded meet- or join-semilattice over Elem. That
+// is, a partial order over values of type Elem, with a binary operator
+// meet/join operator, and an identity element.
+//
+// Because meet and join are duals, this interface simply calls the operator
+// "merge".
+//
+// This is typically implemented by a stateless type, and acts as a factory for
+// lattice elements.
+type Semilattice[Elem any] interface {
+ // Ident returns the identity element of this lattice. In a join
+ // semilattice, this is the least element, aka ⊥ or 𝟎. In a meet
+ // semilattice, this is the greatest element, aka ⊤ or 𝟏.
+ Ident() Elem
+
+ // Equals returns whether a and b are the same element.
+ Equals(a, b Elem) bool
+
+ // Merge is either join (aka least upper bound or supremum) or meet (aka
+ // greatest lower bound or infimum), depending on the direction of this
+ // lattice.
+ //
+ // Merge must satisfy the following identities, where we use ∧ for Merge, =
+ // for Equals, and 𝟏 for Ident:
+ //
+ // - Associativity: x ∧ (y ∧ z) = (x ∧ y) ∧ z
+ //
+ // - Commutativity: x ∧ y = y ∧ x
+ //
+ // - Idempotency: x ∧ x = x
+ //
+ // - Identity: x ∧ 𝟏 = x
+ Merge(a, b Elem) Elem
+}
+
+// A MapLattice implements [Semilattice][map[Key]Elem]. The values in the map
+// are themselves defined by [Semilattice] L.
+//
+// Any elements missing from the map are implicitly L's identity element, and
+// L's identity element never appears as a value in the map.
+type MapLattice[Key comparable, Elem any, L Semilattice[Elem]] struct {
+ l L
+}
+
+func (m MapLattice[Key, Elem, L]) Ident() map[Key]Elem {
+ return nil
+}
+
+func (m MapLattice[Key, Elem, L]) Equals(a, b map[Key]Elem) bool {
+ if len(a) != len(b) {
+ return false
+ }
+ for k, v1 := range a {
+ v2, ok := b[k]
+ if !ok || !m.l.Equals(v1, v2) {
+ return false
+ }
+ }
+ return true
+}
+
+func (m MapLattice[Key, Elem, L]) Merge(a, b map[Key]Elem) map[Key]Elem {
+ if len(a) == 0 {
+ return b
+ } else if len(b) == 0 {
+ return a
+ }
+
+ // We need to consider the union of keys in a and b.
+ out := make(map[Key]Elem)
+ id := m.l.Ident()
+ for k, v1 := range a {
+ v2, ok := b[k]
+ if !ok {
+ // Because Merge(x, Ident()) == x, we can skip calling L.Merge.
+ out[k] = v1
+ continue
+ }
+
+ w := m.l.Merge(v1, v2)
+ if m.l.Equals(w, id) {
+ // In a semilattice, Merge(x, y) = Ident is only possible when x ==
+ // Ident and y == Ident.
+ panic(fmt.Sprintf("%T is not a semilattice: Merge returned Ident for non-Ident arguments", m.l))
+ }
+ out[k] = w
+ }
+ // We considered keys that are only in a, and in both a and b. Now we just
+ // need to handle keys that are only in b.
+ for k, v2 := range b {
+ if _, ok := a[k]; !ok {
+ out[k] = v2
+ }
+ }
+
+ return out
+}
diff --git a/internal/flow/lattice_test.go b/internal/flow/lattice_test.go
new file mode 100644
index 0000000..d943b9f
--- /dev/null
+++ b/internal/flow/lattice_test.go
@@ -0,0 +1,71 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package flow
+
+import "testing"
+
+type nodeSet uint64
+
+type nodeSetUnion struct{}
+
+func (nodeSetUnion) Ident() nodeSet { return 0 }
+func (nodeSetUnion) Equals(a, b nodeSet) bool { return a == b }
+func (nodeSetUnion) Merge(a, b nodeSet) nodeSet { return a | b }
+
+var _ Semilattice[nodeSet] = nodeSetUnion{}
+
+func set(nodes ...int) nodeSet {
+ var out nodeSet
+ for _, node := range nodes {
+ if node < 0 || node >= 64 {
+ panic("NodeID out of range")
+ }
+ out |= 1 << node
+ }
+ return out
+}
+
+func TestMapLattice_Trivial(t *testing.T) {
+ l := MapLattice[int, nodeSet, nodeSetUnion]{}
+
+ // Case 1: a is empty, b is not
+ a := map[int]nodeSet{}
+ b := map[int]nodeSet{1: set(1)}
+
+ got := l.Merge(a, b)
+ if !l.Equals(got, b) {
+ t.Errorf("Merge(empty, b) = %v, want %v", got, b)
+ }
+
+ // Case 2: b is empty, a is not
+ got = l.Merge(b, a)
+ if !l.Equals(got, b) {
+ t.Errorf("Merge(b, empty) = %v, want %v", got, b)
+ }
+}
+
+func TestMapLattice_Merge(t *testing.T) {
+ l := MapLattice[int, nodeSet, nodeSetUnion]{}
+
+ a := map[int]nodeSet{
+ 1: set(1), // Only in a
+ 2: set(2), // In both
+ }
+ b := map[int]nodeSet{
+ 2: set(3), // In both
+ 3: set(4), // Only in b
+ }
+
+ want := map[int]nodeSet{
+ 1: set(1),
+ 2: set(2, 3),
+ 3: set(4),
+ }
+
+ got := l.Merge(a, b)
+ if !l.Equals(got, want) {
+ t.Errorf("Merge(a, b) = %v, want %v", got, want)
+ }
+}
diff --git a/internal/graph/compact.go b/internal/graph/compact.go
new file mode 100644
index 0000000..339b50c
--- /dev/null
+++ b/internal/graph/compact.go
@@ -0,0 +1,95 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+import "iter"
+
+// A CompactGraph is a [Graph] where nodes are compactly numbered from [0, N).
+//
+// Compactly numbered graphs are useful for many graph algorithms.
+type CompactGraph interface {
+ Graph[int]
+
+ // NumNodes returns the number of nodes in this graph.
+ NumNodes() int
+}
+
+// A NodeMap maps between some arbitrary NodeID type and a compact node
+// numbering.
+type NodeMap[NodeID comparable] struct {
+ ids []NodeID
+ idMap map[NodeID]int
+}
+
+var identNodeMap = &NodeMap[int]{}
+
+// Compact takes a Graph with arbitrary NodeIDs and constructs a compactly
+// numbered graph. If g implements CompactGraph, it simply returns g and an
+// identity mapping.
+func Compact[NodeID comparable](g Graph[NodeID]) (CompactGraph, *NodeMap[NodeID]) {
+ if g, ok := g.(CompactGraph); ok {
+ // The above assertion ensures NodeID is int, so we know this type
+ // assertion will always succeed.
+ return g, any(identNodeMap).(*NodeMap[NodeID])
+ }
+
+ // Build the NodeMap
+ cg := compactGraph[NodeID]{g: g}
+ cg.m.idMap = make(map[NodeID]int)
+ for nid := range g.All() {
+ cg.m.idMap[nid] = len(cg.m.ids)
+ cg.m.ids = append(cg.m.ids, nid)
+ }
+
+ return &cg, &cg.m
+}
+
+// NodeID maps a compact node number to a NodeID.
+func (m *NodeMap[NodeID]) NodeID(c int) NodeID {
+ if any(m) == identNodeMap {
+ // Identity map. This will only happen if NodeID is int, but we have no
+ // way to prove that to the compiler.
+ return any(c).(NodeID)
+ }
+ return m.ids[c]
+}
+
+// Compact maps a NodeID to a compact node number.
+func (m *NodeMap[NodeID]) Compact(n NodeID) int {
+ if any(m) == identNodeMap {
+ return any(n).(int)
+ }
+ return m.idMap[n]
+}
+
+type compactGraph[NodeID comparable] struct {
+ g Graph[NodeID]
+ m NodeMap[NodeID]
+}
+
+func (g *compactGraph[NodeID]) NumNodes() int {
+ return len(g.m.ids)
+}
+
+func (g *compactGraph[NodeID]) All() iter.Seq[int] {
+ return func(yield func(int) bool) {
+ for i := range g.m.ids {
+ if !yield(i) {
+ break
+ }
+ }
+ }
+}
+
+func (g *compactGraph[NodeID]) Out(node int) iter.Seq2[int, int] {
+ id := g.m.ids[node]
+ return func(yield func(int, int) bool) {
+ for i, nid := range g.g.Out(id) {
+ if !yield(i, g.m.idMap[nid]) {
+ break
+ }
+ }
+ }
+}
diff --git a/internal/graph/compact_test.go b/internal/graph/compact_test.go
new file mode 100644
index 0000000..8945fef
--- /dev/null
+++ b/internal/graph/compact_test.go
@@ -0,0 +1,72 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+import (
+ "slices"
+ "testing"
+)
+
+func TestCompact(t *testing.T) {
+ g := stringGraph{
+ "A": {"B"},
+ "B": {"C"},
+ "C": {"A"},
+ }
+
+ cg, m := Compact[string](g)
+
+ if n := cg.NumNodes(); n != 3 {
+ t.Errorf("NumNodes() = %d, want 3", n)
+ }
+
+ // Check mapping
+ for i := range cg.NumNodes() {
+ j := m.Compact(m.NodeID(i))
+ if j != i {
+ t.Errorf("Compact(NodeID(%d)) = %d, want %d", i, j, i)
+ }
+ }
+ for n := range g {
+ m := m.NodeID(m.Compact(n))
+ if m != n {
+ t.Errorf("NodeID(Compact(%s)) = %s, want %s", n, m, n)
+ }
+ }
+
+ // Check edges in compacted graph
+ for u := range cg.All() {
+ var got []string
+ for _, v := range cg.Out(u) {
+ got = append(got, m.NodeID(v))
+ }
+
+ want := slices.Sorted(slices.Values(g[m.NodeID(u)]))
+ if !slices.Equal(got, want) {
+ t.Errorf("Out(%d) = %v, want %v", u, got, want)
+ }
+ }
+}
+
+func TestCompact_AlreadyCompact(t *testing.T) {
+ g := newTestGraph(3, map[int][]int{
+ 0: {1},
+ 1: {2},
+ 2: {0},
+ })
+
+ cg, m := Compact[int](g)
+
+ if cg != g {
+ t.Errorf("Compact(g) returned new graph, want original graph")
+ }
+
+ if m.Compact(0) != 0 {
+ t.Errorf("Identity map Compact(0) = %d, want 0", m.Compact(0))
+ }
+ if m.NodeID(0) != 0 {
+ t.Errorf("Identity map NodeID(0) = %d, want 0", m.NodeID(0))
+ }
+}
diff --git a/internal/graph/graph.go b/internal/graph/graph.go
new file mode 100644
index 0000000..61d62fd
--- /dev/null
+++ b/internal/graph/graph.go
@@ -0,0 +1,30 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+import "iter"
+
+// A Graph implements a directed graph where nodes in the graph are identified
+// by the NodeID type.
+//
+// If a concrete graph type stores additional information about nodes and/or
+// edges, it will conventionally provide methods of the form:
+//
+// Node(node NodeID) nodeInfo
+// Edge(from, to NodeID) edgeInfo
+type Graph[NodeID comparable] interface {
+ // All yields all nodes in this graph.
+ All() iter.Seq[NodeID]
+
+ // Out yields the out-edges of node. Out must be deterministic, though
+ // otherwise there is no constraint on the order of the returned sequence.
+ Out(node NodeID) iter.Seq2[int, NodeID]
+}
+
+// An Edge is a directed graph edge between two nodes.
+type Edge[Node comparable] struct {
+ Pred Node // Predecessor node
+ Succ Node // Successor node
+}
diff --git a/internal/graph/graph_test.go b/internal/graph/graph_test.go
new file mode 100644
index 0000000..ae0738f
--- /dev/null
+++ b/internal/graph/graph_test.go
@@ -0,0 +1,68 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+import "iter"
+
+// testGraph is a simple adjacency list implementation of [CompactGraph] for testing.
+type testGraph struct {
+ nodes int
+ edges map[int][]int
+}
+
+func (g *testGraph) NumNodes() int {
+ return g.nodes
+}
+
+func (g *testGraph) All() iter.Seq[int] {
+ return func(yield func(int) bool) {
+ for i := range g.nodes {
+ if !yield(i) {
+ break
+ }
+ }
+ }
+}
+
+func (g *testGraph) Out(u int) iter.Seq2[int, int] {
+ return func(yield func(int, int) bool) {
+ for i, succ := range g.edges[u] {
+ if !yield(i, succ) {
+ return
+ }
+ }
+ }
+}
+
+// newTestGraph builds a testGraph from an adjacency list represented as a map.
+func newTestGraph(n int, adj map[int][]int) *testGraph {
+ return &testGraph{
+ nodes: int(n),
+ edges: adj,
+ }
+}
+
+// stringGraph implements Graph[string].
+type stringGraph map[string][]string
+
+func (g stringGraph) All() iter.Seq[string] {
+ return func(yield func(string) bool) {
+ for node := range g {
+ if !yield(node) {
+ return
+ }
+ }
+ }
+}
+
+func (g stringGraph) Out(node string) iter.Seq2[int, string] {
+ return func(yield func(int, string) bool) {
+ for i, succ := range g[node] {
+ if !yield(i, succ) {
+ return
+ }
+ }
+ }
+}
diff --git a/internal/graph/graphfmt/dot.go b/internal/graph/graphfmt/dot.go
new file mode 100644
index 0000000..d3459a6
--- /dev/null
+++ b/internal/graph/graphfmt/dot.go
@@ -0,0 +1,294 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package graphfmt serializes graphs to external representations.
+package graphfmt
+
+import (
+ "fmt"
+ "io"
+ "os"
+ "os/exec"
+ "strings"
+
+ "golang.org/x/tools/internal/graph"
+)
+
+// Dot contains options for generating a Graphviz Dot graph from a
+// [graph.Graph].
+type Dot[NodeID comparable] struct {
+ // Name is the name given to the graph. Usually this can be
+ // left blank.
+ Name string
+
+ // Label returns the string to use as a label for the given
+ // node. If nil, nodes are labeled with their node numbers.
+ Label func(node NodeID) string
+
+ // NodeAttrs, if non-nil, returns a set of attributes for a
+ // node. If this includes a "label" attribute, it overrides
+ // the label returned by Label.
+ NodeAttrs func(node NodeID) []DotAttr
+
+ // EdgeAttrs, if non-nil, returns a set of attributes for an
+ // edge.
+ EdgeAttrs func(from, to NodeID) []DotAttr
+
+ // ClusterOf, if non-nil, returns the cluster of a node, or nil if the node
+ // should not be in a cluster. Multiple nodes with the same cluster will be
+ // arranged together and enclosed in a box.
+ ClusterOf func(node NodeID) *DotCluster
+}
+
+// DotAttr is an attribute for a Dot node or edge.
+type DotAttr struct {
+ Name string
+
+ // Val is the value of this attribute. It may be a string
+ // (which will be escaped), bool, int, uint, float64 or
+ // DotLiteral.
+ Val interface{}
+}
+
+// DotLiteral is a string literal that should be passed to dot
+// unescaped.
+type DotLiteral string
+
+// DotCluster represents a cluster of nodes arranged together.
+type DotCluster struct {
+ Label string
+ Attrs []DotAttr
+}
+
+func defaultLabel[NodeID comparable](node NodeID) string {
+ return fmt.Sprint(node)
+}
+
+// Print writes the Dot form of g to os.Stdout.
+func (d Dot[NodeID]) Print(g graph.Graph[NodeID]) error {
+ return d.Fprint(os.Stdout, g)
+}
+
+// Sprint returns the Dot form of g as a string.
+func (d Dot[NodeID]) Sprint(g graph.Graph[NodeID]) string {
+ var buf strings.Builder
+ d.Fprint(&buf, g)
+ return buf.String()
+}
+
+// Fprint writes the Dot form of g to w.
+func (d Dot[NodeID]) Fprint(w io.Writer, g graph.Graph[NodeID]) error {
+ label := d.Label
+ if label == nil {
+ label = defaultLabel
+ }
+
+ _, err := fmt.Fprintf(w, "digraph %s {\n", DotString(d.Name))
+ if err != nil {
+ return err
+ }
+
+ // Collect nodes by cluster.
+ nodeNums := make(map[NodeID]int)
+ clusterIDs := make(map[*DotCluster]int)
+ type cluster struct {
+ c *DotCluster
+ nodes []NodeID
+ }
+ clusters := []cluster{{}}
+ clusterIDs[nil] = 0
+ if d.ClusterOf == nil {
+ for nid := range g.All() {
+ clusters[0].nodes = append(clusters[0].nodes, nid)
+ nodeNums[nid] = len(nodeNums)
+ }
+ } else {
+ for nid := range g.All() {
+ c := d.ClusterOf(nid)
+ id, ok := clusterIDs[c]
+ if !ok {
+ id = len(clusters)
+ clusterIDs[c] = id
+ clusters = append(clusters, cluster{c: c})
+ }
+ clusters[id].nodes = append(clusters[id].nodes, nid)
+ nodeNums[nid] = len(nodeNums)
+ }
+ }
+
+ // Emit each cluster.
+ for cid, c := range clusters {
+ if c.c != nil {
+ _, err = fmt.Fprintf(w, "subgraph cluster_%d {\n", cid)
+ if err != nil {
+ return err
+ }
+ haveLabel := false
+ for _, attr := range c.c.Attrs {
+ if attr.Name == "label" {
+ haveLabel = true
+ }
+ _, err = fmt.Fprintf(w, "%s;\n", formatAttr(attr))
+ if err != nil {
+ return err
+ }
+ }
+ if !haveLabel && c.c.Label != "" {
+ _, err = fmt.Fprintf(w, "label=%s;\n", DotString(c.c.Label))
+ if err != nil {
+ return err
+ }
+ }
+ }
+
+ // Emit nodes. We don't emit edges yet because an edge may have a
+ // forward-reference, which could define the target node in the wrong
+ // cluster.
+ for _, nid := range c.nodes {
+ // Define node.
+ var attrList []DotAttr
+ var haveLabel bool
+ if d.NodeAttrs != nil {
+ attrList = d.NodeAttrs(nid)
+ for _, attr := range attrList {
+ if attr.Name == "label" {
+ haveLabel = true
+ break
+ }
+ }
+ }
+ if !haveLabel {
+ attrList = attrList[:len(attrList):len(attrList)]
+ attrList = append(attrList, DotAttr{"label", label(nid)})
+ }
+ _, err = fmt.Fprintf(w, "n%d%s;\n", nodeNums[nid], formatAttrs(attrList))
+ if err != nil {
+ return err
+ }
+ }
+
+ if c.c != nil {
+ _, err = fmt.Fprintf(w, "}\n")
+ if err != nil {
+ return err
+ }
+ }
+ }
+
+ // Emit edges.
+ for nid := range g.All() {
+ for _, succ := range g.Out(nid) {
+ var attrs string
+ if d.EdgeAttrs != nil {
+ attrs = formatAttrs(d.EdgeAttrs(nid, succ))
+ }
+ _, err = fmt.Fprintf(w, "n%d -> n%d%s;\n", nodeNums[nid], nodeNums[succ], attrs)
+ if err != nil {
+ return err
+ }
+ }
+ }
+
+ _, err = fmt.Fprintf(w, "}\n")
+ return err
+}
+
+// SVG attempts to render g to an SVG.
+func (d Dot[NodeID]) SVG(w io.Writer, g graph.Graph[NodeID]) error {
+ // Check that we can run Dot at all.
+ dot := exec.Command("dot", "-V")
+ if err := dot.Run(); err != nil {
+ return fmt.Errorf("cannot run dot: %s", err)
+ }
+
+ // Convert to SVG.
+ //
+ // TODO: Consider lifting nice graph viewer from go.dev/cl/192706
+ dot = exec.Command("dot", "-Tsvg", "-")
+ in, err := dot.StdinPipe()
+ if err != nil {
+ return fmt.Errorf("running dot: %s", err)
+ }
+ dot.Stdout = w
+ if err := dot.Start(); err != nil {
+ return fmt.Errorf("running dot: %s", err)
+ }
+ err = d.Fprint(in, g)
+ in.Close()
+ if err != nil {
+ // Let Dot exit, but ignore any errors from it.
+ dot.Wait()
+ return err
+ }
+ switch err := dot.Wait().(type) {
+ case nil:
+ case *exec.ExitError:
+ if len(err.Stderr) > 0 {
+ return fmt.Errorf("running dot: %s\n%s", err, err.Stderr)
+ }
+ return fmt.Errorf("running dot: %s", err)
+ default:
+ return fmt.Errorf("running dot: %s", err)
+ }
+ return nil
+}
+
+// DotString returns s as a quoted dot string.
+//
+// Users of the Dot type don't need to call this, since it will
+// automatically quote strings. However, this is useful for building
+// custom dot output.
+func DotString(s string) string {
+ var buf strings.Builder
+ buf.WriteByte('"')
+ for i := 0; i < len(s); i++ {
+ switch s[i] {
+ case '\n':
+ buf.WriteString("\\n")
+ case '\\', '"', '{', '}', '<', '>', '|':
+ buf.WriteByte('\\')
+ buf.WriteByte(s[i])
+ default:
+ buf.WriteByte(s[i])
+ }
+ }
+ buf.WriteByte('"')
+ return buf.String()
+}
+
+// formatAttrs formats attrs as a dot attribute set, including the
+// surrounding brackets. If attrs is empty, it returns an empty
+// string.
+func formatAttrs(attrs []DotAttr) string {
+ if len(attrs) == 0 {
+ return ""
+ }
+ var buf strings.Builder
+ buf.WriteString(" [")
+ for i, attr := range attrs {
+ if i > 0 {
+ buf.WriteString(",")
+ }
+ buf.WriteString(formatAttr(attr))
+ }
+ buf.WriteString("]")
+ return buf.String()
+}
+
+func formatAttr(attr DotAttr) string {
+ var buf strings.Builder
+ buf.WriteString(attr.Name)
+ buf.WriteString("=")
+ switch val := attr.Val.(type) {
+ case string:
+ buf.WriteString(DotString(val))
+ case bool, int, uint, float64:
+ fmt.Fprintf(&buf, "%v", val)
+ case DotLiteral:
+ buf.WriteString(string(val))
+ default:
+ panic(fmt.Sprintf("dot attribute %s had unknown type %T", attr.Name, attr.Val))
+ }
+ return buf.String()
+}
diff --git a/internal/graph/order.go b/internal/graph/order.go
new file mode 100644
index 0000000..c95e2d1
--- /dev/null
+++ b/internal/graph/order.go
@@ -0,0 +1,98 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+import "slices"
+
+// Postorder returns the nodes of the graph in post-order.
+//
+// To handle cycles, the algorithm identifies back-edges during DFS. When a
+// cycle is encountered, the algorithm effectively "breaks" it by treating the
+// back-edge as non-existent for the purpose of the ordering, ensuring a
+// complete result for any graph. For rootless subgraphs, it breaks cycles by
+// starting at the lowest numbered node.
+//
+// This algorithm runs in O(V + E) time and O(V + E) space.
+func Postorder[NodeID comparable](g Graph[NodeID]) []NodeID {
+ cg, nodeMap := Compact(g)
+
+ numNodes := cg.NumNodes()
+ if numNodes == 0 {
+ return nil
+ }
+
+ result := make([]NodeID, 0, numNodes)
+ visited := newBitset(numNodes)
+ onStack := newBitset(numNodes)
+
+ // visit performs a Depth-First Search.
+ var visit func(u int)
+ visit = func(u int) {
+ if visited.test(u) {
+ return
+ }
+
+ visited.set(u)
+ onStack.set(u)
+
+ for _, v := range cg.Out(u) {
+ if onStack.test(v) {
+ // Cycle detected (back-edge).
+ // To resolve, we simply skip processing this edge further in the
+ // current recursion, effectively "breaking" the cycle at this point.
+ continue
+ }
+ if !visited.test(v) {
+ visit(v)
+ }
+ }
+
+ onStack.clear(u)
+ // Post-order: add to result after all descendants are processed.
+ result = append(result, nodeMap.NodeID(u))
+ }
+
+ // Visit every node in ascending order to ensure stability.
+ for u := range numNodes {
+ if !visited.test(u) {
+ visit(u)
+ }
+ }
+
+ return result
+}
+
+// ReversePostorder returns the nodes of the graph in reverse post-order.
+//
+// If g is a directed acyclic graph (DAG), the result is a topological sort of
+// g.
+//
+// See [Postorder] for how this handles back-edges and cycles.
+//
+// This algorithm runs in O(V + E) time and O(V + E) space.
+func ReversePostorder[NodeID comparable](g Graph[NodeID]) []NodeID {
+ result := Postorder(g)
+ slices.Reverse(result)
+ return result
+}
+
+// bitset is a simple fixed-size bitset used to reduce memory overhead.
+type bitset []uint64
+
+func newBitset(n int) bitset {
+ return make(bitset, (n+63)/64)
+}
+
+func (b bitset) set(u int) {
+ b[u/64] |= 1 << (u % 64)
+}
+
+func (b bitset) clear(u int) {
+ b[u/64] &= ^(1 << (u % 64))
+}
+
+func (b bitset) test(u int) bool {
+ return b[u/64]&(1<<(u%64)) != 0
+}
diff --git a/internal/graph/order_test.go b/internal/graph/order_test.go
new file mode 100644
index 0000000..16edf96
--- /dev/null
+++ b/internal/graph/order_test.go
@@ -0,0 +1,126 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+import (
+ "reflect"
+ "testing"
+)
+
+func TestPostorder(t *testing.T) {
+ tests := []struct {
+ name string
+ numNodes int
+ adj map[int][]int
+ want []int
+ }{
+ {
+ name: "Simple DAG",
+ numNodes: 3,
+ adj: map[int][]int{
+ 0: {1, 2},
+ 1: {2},
+ },
+ want: []int{2, 1, 0},
+ },
+ {
+ name: "Stability Check (Post-order)",
+ numNodes: 4,
+ adj: map[int][]int{
+ 0: {2},
+ 1: {2},
+ 2: {3},
+ },
+ // DFS Walk:
+ // 1. Start at 0 -> visit 2 -> visit 3. Post-order: [3, 2, 0]
+ // 2. Start at 1 -> visit 2 (visited). Post-order: [3, 2, 0, 1]
+ want: []int{3, 2, 0, 1},
+ },
+ {
+ name: "Disconnected Components",
+ numNodes: 4,
+ adj: map[int][]int{
+ 0: {1},
+ 2: {3},
+ },
+ // DFS Walk:
+ // 1. Start at 0 -> visit 1. Post: [1, 0]
+ // 2. Start at 2 -> visit 3. Post: [1, 0, 3, 2]
+ want: []int{1, 0, 3, 2},
+ },
+ {
+ name: "Simple Cycle Resolution",
+ numNodes: 3,
+ adj: map[int][]int{
+ 0: {1},
+ 1: {2},
+ 2: {0},
+ },
+ // Start 0 -> 1 -> 2 -> 0 (on stack, skip).
+ // Post: [2, 1, 0].
+ want: []int{2, 1, 0},
+ },
+ {
+ name: "Empty Graph",
+ numNodes: 0,
+ adj: map[int][]int{},
+ want: nil,
+ },
+ {
+ name: "Single Node",
+ numNodes: 1,
+ adj: map[int][]int{},
+ want: []int{0},
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ g := newTestGraph(tt.numNodes, tt.adj)
+ got := Postorder(g)
+ if !reflect.DeepEqual(got, tt.want) {
+ t.Errorf("%s: got %v, want %v", tt.name, got, tt.want)
+ }
+ })
+ }
+}
+
+func TestPostorder_LargeChain(t *testing.T) {
+ // Create a large enough graph that super-linear behavior would become a problem.
+ n := 10000
+ adj := make(map[int][]int)
+ var want []int
+ for i := range n {
+ if i < n-1 {
+ adj[int(i)] = []int{i + 1}
+ }
+ // Postorder of 0->1->2... is [n-1, n-2, ..., 0]
+ // Because we visit children fully before adding parent.
+ }
+ // Construct expected want:
+ for i := range n {
+ want = append(want, n-1-i)
+ }
+
+ g := newTestGraph(n, adj)
+ got := Postorder(g)
+ if !reflect.DeepEqual(got, want) {
+ t.Errorf("Large chain failed: got %d elements, first is %v", len(got), got[0])
+ }
+}
+
+func TestReversePostorder(t *testing.T) {
+ g := newTestGraph(3, map[int][]int{
+ 0: {1, 2},
+ 1: {2},
+ })
+ // Postorder: [2, 1, 0]
+ // ReversePostorder: [0, 1, 2]
+ want := []int{0, 1, 2}
+ got := ReversePostorder(g)
+ if !reflect.DeepEqual(got, want) {
+ t.Errorf("ReversePostorder: got %v, want %v", got, want)
+ }
+}
diff --git a/internal/graph/transpose.go b/internal/graph/transpose.go
new file mode 100644
index 0000000..48d7077
--- /dev/null
+++ b/internal/graph/transpose.go
@@ -0,0 +1,42 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package graph
+
+import "iter"
+
+// Transpose implements [Graph], but with all edges reversed. Node IDs are
+// identical to the underlying graph.
+type Transpose[G Graph[NodeID], NodeID comparable] struct {
+ Graph G
+ preds map[NodeID][]NodeID
+}
+
+func NewTranspose[G Graph[NodeID], NodeID comparable](g G) *Transpose[G, NodeID] {
+ preds := make(map[NodeID][]NodeID)
+ for nid := range g.All() {
+ for _, succ := range g.Out(nid) {
+ preds[succ] = append(preds[succ], nid)
+ }
+ }
+ return &Transpose[G, NodeID]{g, preds}
+}
+
+func (t Transpose[G, NodeID]) NumNodes() int {
+ return len(t.preds)
+}
+
+func (t Transpose[G, NodeID]) All() iter.Seq[NodeID] {
+ return t.Graph.All()
+}
+
+func (t Transpose[G, NodeID]) Out(n NodeID) iter.Seq2[int, NodeID] {
+ return func(yield func(int, NodeID) bool) {
+ for i, to := range t.preds[n] {
+ if !yield(i, to) {
+ break
+ }
+ }
+ }
+}
Change information
- A internal/flow/flow.go
- A internal/flow/forward.go
- A internal/flow/forward_test.go
- A internal/flow/lattice.go
- A internal/flow/lattice_test.go
- A internal/graph/compact.go
- A internal/graph/compact_test.go
- A internal/graph/graph.go
- A internal/graph/graph_test.go
- A internal/graph/graphfmt/dot.go
- A internal/graph/order.go
- A internal/graph/order_test.go
- A internal/graph/transpose.go
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 1 comment![]( "Open in Gerrit")
This and the following excfg CL are building blocks for the simd analyzer, but also generally useful. I'm still working on getting the simd analyzer ready for review.
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 1 comment![]( "Open in Gerrit")
Out(node NodeID) iter.Seq2[int, NodeID]I somewhat regret the "int" index in the Seq2. It makes a couple things nicer, but is mostly annoying.
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 18 comments![]( "Open in Gerrit")
// NumNodes returns the number of nodes in this graph.
NumNodes() intPerhaps this belongs in Graph since it is clearly derivable from All(), assuming finitude?
return func(yield func(int) bool) {
for i := range g.m.ids {
if !yield(i) {
break
}
}
}slices.Values(g.m.ids)
// Out yields the out-edges of node. Out must be deterministic, thoughPresumably this makes it big-theta of n even when you break the iteration after the first element, due to the extra slice allocation.
// Print writes the Dot form of g to os.Stdout.
func (d Dot[NodeID]) Print(g graph.Graph[NodeID]) error {
return d.Fprint(os.Stdout, g)
}
// Sprint returns the Dot form of g as a string.
func (d Dot[NodeID]) Sprint(g graph.Graph[NodeID]) string {
var buf strings.Builder
d.Fprint(&buf, g)
return buf.String()
}
Dot graphs are rarely large (since they're incomprehensible above about 50 nodes), so I suggest you just return a string here and leave Writers and errors out of the API. Internally you can use a strings.Builder with infallible writes.
for nid := range g.All() {
clusters[0].nodes = append(clusters[0].nodes, nid)
nodeNums[nid] = len(nodeNums)
}
} else {
for nid := range g.All() {
c := d.ClusterOf(nid)
id, ok := clusterIDs[c]
if !ok {
id = len(clusters)
clusterIDs[c] = id
clusters = append(clusters, cluster{c: c})
}
clusters[id].nodes = append(clusters[id].nodes, nid)
nodeNums[nid] = len(nodeNums)
}Factor the two loops? I can't imagine the cost of re-testing ClusterOf==nil matters.
switch err := dot.Wait().(type) {Clearer:
```
if err := dot.Wait(); err != nil {
if err, ok := err.(*exec.ExitError); ok && len(err.Stderr) > 0 {
return fmt.Errorf("running dot: %s\n%s", err, err.Stderr)
}
return fmt.Errorf("running dot: %s", err)
}
```
var buf strings.Builder
buf.WriteByte('"')
for i := 0; i < len(s); i++ {
switch s[i] {
case '\n':
buf.WriteString("\\n")
case '\\', '"', '{', '}', '<', '>', '|':
buf.WriteByte('\\')
buf.WriteByte(s[i])
default:
buf.WriteByte(s[i])
}
}
buf.WriteByte('"')
return buf.String()This is a one-liner with strings.Replacer.
var buf strings.BuilderMake this a parameter.
// To handle cycles, the algorithm identifies back-edges during DFS. When a
// cycle is encountered, the algorithm effectively "breaks" it by treating the
// back-edge as non-existent for the purpose of the ordering, ensuring a
// complete result for any graph. For rootless subgraphs, it breaks cycles byMore concisely:
Postorder returns the sequence of nodes in the spanning DAG of g, in postorder.
if visited.test(u) {
return
}
visited.set(u)It is both more convenient and more efficient to make `set` report whether it had any effect, then:
```
if visited.set(u) {
...body...
}
```
func (b bitset) set(u int) {add (since it abstracts a set)
func NewTranspose[G Graph[NodeID], NodeID comparable](g G) *Transpose[G, NodeID] {Is it worth making NewTranspose(NewTranspose(g)) return g? I guess the need doesn't often arise.
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 3 comments![]( "Open in Gerrit")
// Compact maps a NodeID to a compact node number."Index maps a NodeID to its index in the compact sequence."?
// Out yields the out-edges of node. Out must be deterministic, thoughPresumably this makes it big-theta of n even when you break the iteration after the first element, due to the extra slice allocation.
Why is predictable ordering important?
Out(node NodeID) iter.Seq2[int, NodeID]I somewhat regret the "int" index in the Seq2. It makes a couple things nicer, but is mostly annoying.
Yeah, it mostly seems to require extra plumbing just avoid maintaining a counter somewhere (that I haven't yet seen).
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 1 comment![]( "Open in Gerrit")
func NewTranspose[G Graph[NodeID], NodeID comparable](g G) *Transpose[G, NodeID] {Call this just Transpose, and hide the representation type?
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 15 comments![]( "Open in Gerrit")
// Analysis is the result of a monotone analysis. It records the analysis factIt's not clear what exactly "the fact" means here; the Fact parameter could use some elaboration.
func (f *Analysis[Fact, NodeID]) In(nid NodeID) Fact {a?
fromNum, toNum := f.nodeMap.Compact(from), f.nodeMap.Compact(to)Add a helper method `(*Analysis).edge(from, to int) edge`?
```
slices.BinarySearchFunc(f.edges, f.edge(from, to), ...)
```
```
type edge struct { from, to int }
s/graph.Edge[nodeNum]/edge/g
```
That said, it's not clear to me that you need an `edge` type distinct from edgeFact; the binary search could make do with an edgeFact if the comparator ignores the fact field.
if e.Pred != f.Pred {```
if v := cmp.Compare(...); v != 0 {
return v
}
```
is self-evidently consistent.
for _, succID := range cg.Out(ni) {After plumbing the index all this way, we discard it. ;-)
Let's make Out return a plain Seq.
if fact, ok := entry[nodeMap.NodeID(ni)]; ok {Factor common tail:
```
fact, ok := entry[nodeMap.NodeID(ni)]
if !ok {
fact = fb.l.Ident()
}
b.in = fact
``` b.out = make([]Fact, outs)
for i := range b.out {
b.out[i] = fb.l.Ident()
}```
b.out = slices.Repeat(fb.l.Ident(), len(outs))
```
a.edges = append(a.edges, edgeFact[Fact]{graph.Edge[nodeNum]{Pred: pred, Succ: succ}, fb.blocks[pred].out[i]})
}
}
slices.SortFunc(a.edges, func(a, b edgeFact[Fact]) int { return compareEdge(a.Edge, b.Edge) })This might be simpler if you identify type `edge` (formerly `graph.Edge[int]`) and edgeFact. There's no need ever to materialize plain edges.
// nodeNum is a compactly numbered node. It's an alias for int purely for
// documentation purposes.I found it confusing: I thought "shouldn't this be an int?" when I was reading the binary search code.
type fwdBuilder[L Semilattice[Fact], Fact any, NodeID comparable] struct {Gotta go shovel before dark. This is as far as I got today.
// A Semilattice describes a bounded meet- or join-semilattice over Elem. That
// is, a partial order over values of type Elem, with a binary operator
// meet/join operator, and an identity element.
//
// Because meet and join are duals, this interface simply calls the operator
// "merge".Let's abolish the meet/join terminology since it has historically been such as source of confusion.
```
// A Semilattice describes a bounded semilattice over Elem.
// That is, a partial order over values of type Elem, with a binary
// Merge operator and an identity element.
```
if len(a) != len(b) {
return false
}
for k, v1 := range a {
v2, ok := b[k]
if !ok || !m.l.Equals(v1, v2) {
return false
}
}
return truereturn maps.EqualFunc(a, b, m.l.Equals)
type Edge[Node comparable] struct {I don't think this type belongs here, as the graph abstraction doesn't materialize edges. Each client can declare a private `type edge struct{ from, to whatever }` as needed.
Pred Node // Predecessor node
Succ Node // Successor nodeFrom, To
Pred and succ are node-to-node relations, not edge-to-node.
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 9 comments![]( "Open in Gerrit")
func Forward[L Semilattice[Fact], Fact any, NodeID comparable](g graph.Graph[NodeID], entry map[NodeID]Fact, transfer func(Fact, graph.Edge[NodeID]) Fact) *Analysis[Fact, NodeID] {from, to NodeID, fact Fact
edges: make([]edgeFact[Fact], totalEdges),make(..., 0, totalEdges)?
Otherwise the first node will have a lot of factless self-edges.
type fwdBuilder[L Semilattice[Fact], Fact any, NodeID comparable] struct {Gotta go shovel before dark. This is as far as I got today.
Done
fmt.Printf(" to node %d: %v\n", succNum, edgeFact)log
Avoid logging to stdout even temporarily as log statements can easily make it into production, and stray bytes on stdout = a broken command-line tool or LSP server.
// NumNodes returns the number of nodes in this graph.
NumNodes() intPerhaps this belongs in Graph since it is clearly derivable from All(), assuming finitude?
Alternatively you could remove this method entirely, and identify Graph[int] and CompactGraph, since in all places that call NumNodes(), the same information is easily derived another way such as `len(g.Postorder())` or `len(nodeMap)`.
Either way it would be nice to dispense with the additional interface.
// A NodeMap maps between some arbitrary NodeID type and a compact node
// numbering.
type NodeMap[NodeID comparable] struct {
ids []NodeID
idMap map[NodeID]int
}
This data type reminds me of one I have used several times in the past, Index[T], which provides a immutable bijection between a list of T values and small integers. It could be a commonly useful thing in its own right in the graph package, constructed by NewIndex(Seq[T]), and not coupled to CompactGraph. The Compact function could then just call NewIndex(g.All()).
The edge case optimization for integers is novel. How important is it? I suspect it may have caused a couple of latent bugs (see below) due to the loss of knowledge of NumNodes.
If it is important, it would be nice if we could represent it as a simple boolean field Index.isIdentity, that reports whether all elements are integers (of any size) equal to their index in the slice (which would have to be sorted). Then the map could be dispensed with. Something like this:
```
// A Index is an immutable bijection between each value in a list
// and its index in that list.
type Index[T comparable] struct {
index map[T]int // nil => identity mapping (T is integral)
value []T
}
// NewIndex returns an index for the specified list of values.
func NewIndex[T comparable](values ...T) *Index[T] {
// fast path: a sorted integer list needs no index.
if T is an integer {
for i, v := range values {
if i is not equal to v {
goto identity
}
}
return &Index[T]{nil, values}
}
nonidentity:
index := make(map[T]int, len(values))
for i, v := range values {
index[v] = i
}
return &Index[T]{index, values}
}
func (ix *Index[T]) Value(index int) T
func (ix *Index[T]) Index(value T) int
```
for i := range g.m.ids {This looks wrong for the edge case of identNodeMap. You could use `range g.NumNodes()`, but I think NumNodes has the same problem. Changing NumNodes return `g.g.NumNodes()` should fix both methods, but this requires that NumNodes be promoted to the Graph interface (which I think is the right move).
return func(yield func(int, int) bool) {
for i, succ := range g.edges[u] {
if !yield(i, succ) {
return
}
}
}slices.Values(g.edges[u])
return func(yield func(int, string) bool) {
for i, succ := range g[node] {
if !yield(i, succ) {
return
}
}
}slices.Values(g[node])
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 43 comments![]( "Open in Gerrit")
Thanks for the detailed review!
package flowI haven't looked at flow yet.
Acknowledged
// Analysis is the result of a monotone analysis. It records the analysis factIt's not clear what exactly "the fact" means here; the Fact parameter could use some elaboration.
I tried to expand. This is one of those things go doc's "trees over forests" approach handles poorly.
func (f *Analysis[Fact, NodeID]) In(nid NodeID) Fact {Austin Clementsa?
Done
fromNum, toNum := f.nodeMap.Compact(from), f.nodeMap.Compact(to)Add a helper method `(*Analysis).edge(from, to int) edge`?
```
slices.BinarySearchFunc(f.edges, f.edge(from, to), ...)
```
Done
```
type edge struct { from, to int }s/graph.Edge[nodeNum]/edge/g
```That said, it's not clear to me that you need an `edge` type distinct from edgeFact; the binary search could make do with an edgeFact if the comparator ignores the fact field.
I'd prefer to keep the graph.Edge type, so it doesn't make sense to introduce another type here.
While it would be fine for compareEdge to use edgeFact, now that I've introduced (*Analysis).edge, it would be really weird for that to return edgeFact.
if e.Pred != f.Pred {```
if v := cmp.Compare(...); v != 0 {
return v
}
```
is self-evidently consistent.
Done
func Forward[L Semilattice[Fact], Fact any, NodeID comparable](g graph.Graph[NodeID], entry map[NodeID]Fact, transfer func(Fact, graph.Edge[NodeID]) Fact) *Analysis[Fact, NodeID] {from, to NodeID, fact Fact
Done
for _, succID := range cg.Out(ni) {After plumbing the index all this way, we discard it. ;-)
Let's make Out return a plain Seq.
Done
if fact, ok := entry[nodeMap.NodeID(ni)]; ok {Factor common tail:
```
fact, ok := entry[nodeMap.NodeID(ni)]
if !ok {
fact = fb.l.Ident()
}
b.in = fact
```
Done
b.out = make([]Fact, outs)
for i := range b.out {
b.out[i] = fb.l.Ident()
}Austin Clements```
b.out = slices.Repeat(fb.l.Ident(), len(outs))
```
It's slightly uglier:
b.out = slices.Repeat([]Fact{fb.l.Ident()}, outs)But sure.
edges: make([]edgeFact[Fact], totalEdges),make(..., 0, totalEdges)?
Otherwise the first node will have a lot of factless self-edges.
Oops!
a.edges = append(a.edges, edgeFact[Fact]{graph.Edge[nodeNum]{Pred: pred, Succ: succ}, fb.blocks[pred].out[i]})
}
}
slices.SortFunc(a.edges, func(a, b edgeFact[Fact]) int { return compareEdge(a.Edge, b.Edge) })This might be simpler if you identify type `edge` (formerly `graph.Edge[int]`) and edgeFact. There's no need ever to materialize plain edges.
If we would just infer type parameters to types from their literals this wouldn't be so messy. 😄
I made this a little easier to read, but I'm keeping graph.Edge
// nodeNum is a compactly numbered node. It's an alias for int purely for
// documentation purposes.I found it confusing: I thought "shouldn't this be an int?" when I was reading the binary search code.
Fair enough. Gone. (Yay //go:fix inline)
fmt.Printf(" to node %d: %v\n", succNum, edgeFact)log
Avoid logging to stdout even temporarily as log statements can easily make it into production, and stray bytes on stdout = a broken command-line tool or LSP server.
Done
// A Semilattice describes a bounded meet- or join-semilattice over Elem. That
// is, a partial order over values of type Elem, with a binary operator
// meet/join operator, and an identity element.
//
// Because meet and join are duals, this interface simply calls the operator
// "merge".Let's abolish the meet/join terminology since it has historically been such as source of confusion.
```
// A Semilattice describes a bounded semilattice over Elem.
// That is, a partial order over values of type Elem, with a binary
// Merge operator and an identity element.
```
It is the official position of the Go project that the historical meet/join terminology is BAD and it should feel bad.
Done.
if len(a) != len(b) {
return false
}
for k, v1 := range a {
v2, ok := b[k]
if !ok || !m.l.Equals(v1, v2) {
return false
}
}
return trueAustin Clementsreturn maps.EqualFunc(a, b, m.l.Equals)
Nice. Modernizer? 😄
// NumNodes returns the number of nodes in this graph.
NumNodes() intAlan DonovanPerhaps this belongs in Graph since it is clearly derivable from All(), assuming finitude?
Alternatively you could remove this method entirely, and identify Graph[int] and CompactGraph, since in all places that call NumNodes(), the same information is easily derived another way such as `len(g.Postorder())` or `len(nodeMap)`.
Either way it would be nice to dispense with the additional interface.
I worry that a type could "accidentally" implement Graph[int] without actually guaranteeing its nodes are compactly numbered. I suppose you could accidentally implement a NumNodes method as well on such a type, but it at least adds some additional barrier. I'm happy to do this some other way, but I do think we need some way to signal "no, really, these are compactly numbered"
Originally I had an entirely different type for compactly numbered node IDs (same underlying type as int). The drawback of that was that you *had* to import internal/graph to implement that interface. That resulted in somewhat tighter coupling than I liked, for example in the excfg package. But that is an option.
Interesting!
1. If it is just Index, it really has nothing to do with graphs, so maybe it should go in its own internal/index package? It would be a pretty trivial package, but like you said, it keeps coming up.
2. The identity optimization I use here has the added property that you can construct the identity NodeMap in O(1) time because it doesn't even need the slice. It would be fine to add a field that says it's an identity on [0, N), and then leave both index and value nil. That may be less confusing.
3. For a general abstraction, we could additionally do an "integer" optimization that populates just the slice in sorted order, like you said. That doesn't come up in any of the graphs I've built (which are either already compactly numbered, or aren't int's at all), but I could certainly see it coming up in other situations.
// Compact maps a NodeID to a compact node number."Index maps a NodeID to its index in the compact sequence."?
Done
for i := range g.m.ids {This looks wrong for the edge case of identNodeMap. You could use `range g.NumNodes()`, but I think NumNodes has the same problem. Changing NumNodes return `g.g.NumNodes()` should fix both methods, but this requires that NumNodes be promoted to the Graph interface (which I think is the right move).
Compact never returns a *compactGraph along with identNodeMap, so g.m will never be identNodeMap.
Reaching into the NodeMap here is arguably an abstraction violation, and leads to this source of confusion. Maybe I shouldn't use NodeMap in compactGraph?
return func(yield func(int) bool) {
for i := range g.m.ids {
if !yield(i) {
break
}
}
}Austin Clementsslices.Values(g.m.ids)
This is yielding the indexes, not the values.
package graphAustin ClementsDoc comment?
Done
// Out yields the out-edges of node. Out must be deterministic, thoughAlan DonovanPresumably this makes it big-theta of n even when you break the iteration after the first element, due to the extra slice allocation.
Why is predictable ordering important?
Predictable ordering lets callers easily annotate the edges with just a slice indexed in the same order that Out yields successors. This is especially nice in compact graphs because annotations can all be kept in slices, without the need for any more expensive map lookups.
In my implementations of this interface, I always had the edges in some order anyway, so there was no added cost to this. That seems to be true of many other graphs in x/tools as well. It's not true of cmd/digraph's representation, though it would be easy to fix that.
We could drop this requirement, it would just mean callers have to use slightly more expensive data structures.
Out(node NodeID) iter.Seq2[int, NodeID]Alan DonovanI somewhat regret the "int" index in the Seq2. It makes a couple things nicer, but is mostly annoying.
Yeah, it mostly seems to require extra plumbing just avoid maintaining a counter somewhere (that I haven't yet seen).
Done
type Edge[Node comparable] struct {I don't think this type belongs here, as the graph abstraction doesn't materialize edges. Each client can declare a private `type edge struct{ from, to whatever }` as needed.
I see what you're saying, but I'd like to keep this for two reasons: 1. Almost every client does wind up needing an edge type, so it's convenient! 2. There are certainly graph algorithms that need to talk about edges, so they need an edge type in this package anyway.
Pred Node // Predecessor node
Succ Node // Successor nodeFrom, To
Pred and succ are node-to-node relations, not edge-to-node.
Done
return func(yield func(int, int) bool) {
for i, succ := range g.edges[u] {
if !yield(i, succ) {
return
}
}
}Austin Clementsslices.Values(g.edges[u])
Done
return func(yield func(int, string) bool) {
for i, succ := range g[node] {
if !yield(i, succ) {
return
}
}
}Austin Clementsslices.Values(g[node])
Done
Val interface{}Austin Clementsany
Heh, you caught me in the act of copying a Dot writer I wrote a long time ago. :) Why didn't gopls suggest modernizing this, though?
// Print writes the Dot form of g to os.Stdout.
func (d Dot[NodeID]) Print(g graph.Graph[NodeID]) error {
return d.Fprint(os.Stdout, g)
}
// Sprint returns the Dot form of g as a string.
func (d Dot[NodeID]) Sprint(g graph.Graph[NodeID]) string {
var buf strings.Builder
d.Fprint(&buf, g)
return buf.String()
}
Dot graphs are rarely large (since they're incomprehensible above about 50 nodes), so I suggest you just return a string here and leave Writers and errors out of the API. Internally you can use a strings.Builder with infallible writes.
Done
for nid := range g.All() {
clusters[0].nodes = append(clusters[0].nodes, nid)
nodeNums[nid] = len(nodeNums)
}
} else {
for nid := range g.All() {
c := d.ClusterOf(nid)
id, ok := clusterIDs[c]
if !ok {
id = len(clusters)
clusterIDs[c] = id
clusters = append(clusters, cluster{c: c})
}
clusters[id].nodes = append(clusters[id].nodes, nid)
nodeNums[nid] = len(nodeNums)
}Factor the two loops? I can't imagine the cost of re-testing ClusterOf==nil matters.
Done
switch err := dot.Wait().(type) {Clearer:
```
if err := dot.Wait(); err != nil {
if err, ok := err.(*exec.ExitError); ok && len(err.Stderr) > 0 {
return fmt.Errorf("running dot: %s\n%s", err, err.Stderr)
}
return fmt.Errorf("running dot: %s", err)
}
```
Done
var buf strings.Builder
buf.WriteByte('"')
for i := 0; i < len(s); i++ {
switch s[i] {
case '\n':
buf.WriteString("\\n")
case '\\', '"', '{', '}', '<', '>', '|':
buf.WriteByte('\\')
buf.WriteByte(s[i])
default:
buf.WriteByte(s[i])
}
}
buf.WriteByte('"')
return buf.String()This is a one-liner with strings.Replacer.
Done
var buf strings.BuilderAustin ClementsMake this a parameter.
Done. I restructured the attr list formatting generally to make it simpler.
// To handle cycles, the algorithm identifies back-edges during DFS. When a
// cycle is encountered, the algorithm effectively "breaks" it by treating the
// back-edge as non-existent for the purpose of the ordering, ensuring a
// complete result for any graph. For rootless subgraphs, it breaks cycles byMore concisely:
Postorder returns the sequence of nodes in the spanning DAG of g, in postorder.
Done
if visited.test(u) {
return
}
visited.set(u)It is both more convenient and more efficient to make `set` report whether it had any effect, then:
```
if visited.set(u) {
...body...
}
```
Done
if !visited.test(u) {Austin Clementsdelete (redundant)
Done. Also above.
func (b bitset) set(u int) {add (since it abstracts a set)
Done
func (b bitset) clear(u int) {Austin Clementsremove
Done
func (b bitset) test(u int) bool {Austin Clementscontains
Done
func NewTranspose[G Graph[NodeID], NodeID comparable](g G) *Transpose[G, NodeID] {Austin ClementsIs it worth making NewTranspose(NewTranspose(g)) return g? I guess the need doesn't often arise.
I don't think I can. Because Transpose is parameterized by G, I can't construct the type to test g against: `g.(*Transpose[???, NodeID])`.
func NewTranspose[G Graph[NodeID], NodeID comparable](g G) *Transpose[G, NodeID] {Call this just Transpose, and hide the representation type?
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 1 comment![]( "Open in Gerrit")
return func(yield func(int) bool) {
for i := range g.m.ids {
if !yield(i) {
break
}
}
}Austin Clementsslices.Values(g.m.ids)
This is yielding the indexes, not the values.
slices.Iota? 😄
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 1 comment![]( "Open in Gerrit")
return func(yield func(int) bool) {
for i := range g.m.ids {
if !yield(i) {
break
}
}
}Austin Clementsslices.Values(g.m.ids)
Austin ClementsThis is yielding the indexes, not the values.
slices.Iota? 😄
I do think an iter.Integers(n) function is not a crazy idea.
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 1 comment![]( "Open in Gerrit")
// NumNodes returns the number of nodes in this graph.
NumNodes() intAlan DonovanPerhaps this belongs in Graph since it is clearly derivable from All(), assuming finitude?
Austin ClementsAlternatively you could remove this method entirely, and identify Graph[int] and CompactGraph, since in all places that call NumNodes(), the same information is easily derived another way such as `len(g.Postorder())` or `len(nodeMap)`.
Either way it would be nice to dispense with the additional interface.
I worry that a type could "accidentally" implement Graph[int] without actually guaranteeing its nodes are compactly numbered. I suppose you could accidentally implement a NumNodes method as well on such a type, but it at least adds some additional barrier. I'm happy to do this some other way, but I do think we need some way to signal "no, really, these are compactly numbered"
Originally I had an entirely different type for compactly numbered node IDs (same underlying type as int). The drawback of that was that you *had* to import internal/graph to implement that interface. That resulted in somewhat tighter coupling than I liked, for example in the excfg package. But that is an option.
One downside of a node type that indicates compactness is that would make algorithms that return a subgraph trickier. I was thinking about this in the context of digraph's allpaths. The natural type of AllPaths as a subgraph algorithm is
func AllPaths[NodeID comparable](g Graph[NodeID], src, dst NodeID) Graph[NodeID]
But the result isn't going to be a compact graph, so if NodeID alone indicates a compact graph, this will go sideways.
I suppose another alternative is to be way more explicit by adding an "IsCompact() bool" method.
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 9 comments![]( "Open in Gerrit")
// Analysis is the result of a monotone analysis. It records the analysis factAustin ClementsIt's not clear what exactly "the fact" means here; the Fact parameter could use some elaboration.
I tried to expand. This is one of those things go doc's "trees over forests" approach handles poorly.
Done
Austin Clements```
type edge struct { from, to int }s/graph.Edge[nodeNum]/edge/g
```That said, it's not clear to me that you need an `edge` type distinct from edgeFact; the binary search could make do with an edgeFact if the comparator ignores the fact field.
I'd prefer to keep the graph.Edge type, so it doesn't make sense to introduce another type here.
While it would be fine for compareEdge to use edgeFact, now that I've introduced (*Analysis).edge, it would be really weird for that to return edgeFact.
I really don't think the graph package wants an Edge type because it's not a concept in that package, it's merely a type that some clients might find useful and could easily declare themselves.
(FWIW I suggested to add the Analysis.edge method before I realized that edgeFact and edge could be profitably merged. I wouldn't let it stand in the way of eliminating the edge pair type.)
a.edges = append(a.edges, edgeFact[Fact]{graph.Edge[nodeNum]{Pred: pred, Succ: succ}, fb.blocks[pred].out[i]})
}
}
slices.SortFunc(a.edges, func(a, b edgeFact[Fact]) int { return compareEdge(a.Edge, b.Edge) })Austin ClementsThis might be simpler if you identify type `edge` (formerly `graph.Edge[int]`) and edgeFact. There's no need ever to materialize plain edges.
If we would just infer type parameters to types from their literals this wouldn't be so messy. 😄
I made this a little easier to read, but I'm keeping graph.Edge
Again, I do think it would better to have only a single type, locally, for the triple. It even simplifies the sort call:
```
edges = append(a.edges, edgeFact[Fact]{pred, succ, fb.blocks[pred].out[i]})
...
slices.SortFunc(a.edges, compareEdge)
```
// NumNodes returns the number of nodes in this graph.
NumNodes() intAlan DonovanPerhaps this belongs in Graph since it is clearly derivable from All(), assuming finitude?
Austin ClementsAlternatively you could remove this method entirely, and identify Graph[int] and CompactGraph, since in all places that call NumNodes(), the same information is easily derived another way such as `len(g.Postorder())` or `len(nodeMap)`.
Either way it would be nice to dispense with the additional interface.
Austin ClementsI worry that a type could "accidentally" implement Graph[int] without actually guaranteeing its nodes are compactly numbered. I suppose you could accidentally implement a NumNodes method as well on such a type, but it at least adds some additional barrier. I'm happy to do this some other way, but I do think we need some way to signal "no, really, these are compactly numbered"
Originally I had an entirely different type for compactly numbered node IDs (same underlying type as int). The drawback of that was that you *had* to import internal/graph to implement that interface. That resulted in somewhat tighter coupling than I liked, for example in the excfg package. But that is an option.
One downside of a node type that indicates compactness is that would make algorithms that return a subgraph trickier. I was thinking about this in the context of digraph's allpaths. The natural type of AllPaths as a subgraph algorithm is
func AllPaths[NodeID comparable](g Graph[NodeID], src, dst NodeID) Graph[NodeID]But the result isn't going to be a compact graph, so if NodeID alone indicates a compact graph, this will go sideways.
I suppose another alternative is to be way more explicit by adding an "IsCompact() bool" method.
Fair enough. I think it would still be useful to promote NumNodes to the parent interface, but I agree there is some value in a marker interface indicating compactness.
// A NodeMap maps between some arbitrary NodeID type and a compact node
// numbering.
type NodeMap[NodeID comparable] struct {
ids []NodeID
idMap map[NodeID]int
}
This data type reminds me of one I have used several times in the past, Index[T], which provides a immutable bijection between a list of T values and small integers. It could be a commonly useful thing in its own right in the graph package, constructed by NewIndex(Seq[T]), and not coupled to CompactGraph. The Compact function could then just call NewIndex(g.All()).
1. True, it could be external, though mostly I have tended to want it in connection to graphs.
2. True, it saves a (small) O(n) term, but Compact is generally expected to be O(n) so I don't think it matters that much, and presumably one calls it only sparingly.
A more general question: what is the goal of compaction? Clearly it allows you to denote sets of nodes compactly using a bitvector, but the actual iteration of edges must still map back to the non-compact NodeID domain, look in the NodeID map representation, then project back to ints (another map lookup). Might it not be more efficient to convert the entire graph connectivity relation to a bit matrix?
for i := range g.m.ids {Austin ClementsThis looks wrong for the edge case of identNodeMap. You could use `range g.NumNodes()`, but I think NumNodes has the same problem. Changing NumNodes return `g.g.NumNodes()` should fix both methods, but this requires that NumNodes be promoted to the Graph interface (which I think is the right move).
Compact never returns a *compactGraph along with identNodeMap, so g.m will never be identNodeMap.
Reaching into the NodeMap here is arguably an abstraction violation, and leads to this source of confusion. Maybe I shouldn't use NodeMap in compactGraph?
If you promote NumNodes to Graph. then you can just range over it instead (since you know that graph is compact).
// Out yields the out-edges of node. Out must be deterministic, thoughAlan DonovanPresumably this makes it big-theta of n even when you break the iteration after the first element, due to the extra slice allocation.
Austin ClementsWhy is predictable ordering important?
Predictable ordering lets callers easily annotate the edges with just a slice indexed in the same order that Out yields successors. This is especially nice in compact graphs because annotations can all be kept in slices, without the need for any more expensive map lookups.
In my implementations of this interface, I always had the edges in some order anyway, so there was no added cost to this. That seems to be true of many other graphs in x/tools as well. It's not true of cmd/digraph's representation, though it would be easy to fix that.
We could drop this requirement, it would just mean callers have to use slightly more expensive data structures.
Ok, fair enough.
type Edge[Node comparable] struct {Austin ClementsI don't think this type belongs here, as the graph abstraction doesn't materialize edges. Each client can declare a private `type edge struct{ from, to whatever }` as needed.
I see what you're saying, but I'd like to keep this for two reasons: 1. Almost every client does wind up needing an edge type, so it's convenient! 2. There are certainly graph algorithms that need to talk about edges, so they need an edge type in this package anyway.
Which algorithms in the package need an edge type?
func NewTranspose[G Graph[NodeID], NodeID comparable](g G) *Transpose[G, NodeID] {Austin ClementsIs it worth making NewTranspose(NewTranspose(g)) return g? I guess the need doesn't often arise.
I don't think I can. Because Transpose is parameterized by G, I can't construct the type to test g against: `g.(*Transpose[???, NodeID])`.
Why not parameterize only by NodeID? You don't actually need G. In particular, it's not as if you return a graph of the same G type as the argument.
Related details
- Austin Clements
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements added 7 comments![]( "Open in Gerrit")
Austin Clements```
type edge struct { from, to int }s/graph.Edge[nodeNum]/edge/g
```That said, it's not clear to me that you need an `edge` type distinct from edgeFact; the binary search could make do with an edgeFact if the comparator ignores the fact field.
Alan DonovanI'd prefer to keep the graph.Edge type, so it doesn't make sense to introduce another type here.
While it would be fine for compareEdge to use edgeFact, now that I've introduced (*Analysis).edge, it would be really weird for that to return edgeFact.
I really don't think the graph package wants an Edge type because it's not a concept in that package, it's merely a type that some clients might find useful and could easily declare themselves.
(FWIW I suggested to add the Analysis.edge method before I realized that edgeFact and edge could be profitably merged. I wouldn't let it stand in the way of eliminating the edge pair type.)
Analysis.edge is nice because it can also wrap up the NodeID to index mapping. While I agree that edge and edgeFact don't need to be separate, I don't think it adds any complexity, and it seems conceptually simpler to me.
a.edges = append(a.edges, edgeFact[Fact]{graph.Edge[nodeNum]{Pred: pred, Succ: succ}, fb.blocks[pred].out[i]})
}
}
slices.SortFunc(a.edges, func(a, b edgeFact[Fact]) int { return compareEdge(a.Edge, b.Edge) })Austin ClementsThis might be simpler if you identify type `edge` (formerly `graph.Edge[int]`) and edgeFact. There's no need ever to materialize plain edges.
Alan DonovanIf we would just infer type parameters to types from their literals this wouldn't be so messy. 😄
I made this a little easier to read, but I'm keeping graph.Edge
Again, I do think it would better to have only a single type, locally, for the triple. It even simplifies the sort call:
```
edges = append(a.edges, edgeFact[Fact]{pred, succ, fb.blocks[pred].out[i]})
...
slices.SortFunc(a.edges, compareEdge)
```
See above.
// NumNodes returns the number of nodes in this graph.
NumNodes() intAlan DonovanPerhaps this belongs in Graph since it is clearly derivable from All(), assuming finitude?
Austin ClementsAlternatively you could remove this method entirely, and identify Graph[int] and CompactGraph, since in all places that call NumNodes(), the same information is easily derived another way such as `len(g.Postorder())` or `len(nodeMap)`.
Either way it would be nice to dispense with the additional interface.
Austin ClementsI worry that a type could "accidentally" implement Graph[int] without actually guaranteeing its nodes are compactly numbered. I suppose you could accidentally implement a NumNodes method as well on such a type, but it at least adds some additional barrier. I'm happy to do this some other way, but I do think we need some way to signal "no, really, these are compactly numbered"
Originally I had an entirely different type for compactly numbered node IDs (same underlying type as int). The drawback of that was that you *had* to import internal/graph to implement that interface. That resulted in somewhat tighter coupling than I liked, for example in the excfg package. But that is an option.
Alan DonovanOne downside of a node type that indicates compactness is that would make algorithms that return a subgraph trickier. I was thinking about this in the context of digraph's allpaths. The natural type of AllPaths as a subgraph algorithm is
func AllPaths[NodeID comparable](g Graph[NodeID], src, dst NodeID) Graph[NodeID]But the result isn't going to be a compact graph, so if NodeID alone indicates a compact graph, this will go sideways.
I suppose another alternative is to be way more explicit by adding an "IsCompact() bool" method.
Fair enough. I think it would still be useful to promote NumNodes to the parent interface, but I agree there is some value in a marker interface indicating compactness.
Requirements:
1. Algorithms must be able to compact any graph.
2. User-defined graph types that are already compact should take O(1) time and space to compact.
3. Algorithms must be able to take a compact graph and return a non-compact graph with the same NodeID type.
Nice-to-have:
4. Algorithms that maintain compactness, such as Transpose, can return a compact graph if the input is compact. This is a nice-to-have because there's no significant harm to compacting a graph that's already compact; it's just unnecessary work.
5. User-defined graph types are loosely coupled: they do not have to import `graph` or use `graph` package types in exported methods.
Some options:
1. `type CompactGraph { Graph[int]; IsCompact() }`. Satisfies all of the requirements and nice-to-haves except for \#4. Makes compactness a static property of a type. It is technically possible to achieve \#4, but it is awkward. Maybe that's fine since there aren't many algorithms that maintain the nodes and only change the edges.
2. Eliminate `CompactGraph`. Document on `Compact` that if g has an `IsCompact() bool` method that returns true, it will assume it's already compact. Satisfies all of the requirements. It makes compactness a fully dynamic property. That's not so bad because if you're not sure, you can call `Compact` and it's free if it's already compact.
3. An optional `Compact() (Graph[int], Index[NodeID])` method. For already compact graphs, this would just return itself. For dynamically compact graphs like transpose, this can choose whether to return itself or call `graph.Compact`. This satisfies everything except nice-to-have \#5. It has the added benefiting of giving an implementation the option of caching the compacted graph. But it's kind of complicated.
I'll try out option 2.
First some history for posterity: Until shortly before I posted this CL stack, I *only* had the interface that is now called `Compact`. I wrote this all for the SIMD analyzer. It was pretty natural for the graphs it used to be compact, and it was quite useful for the implementation of flow.Forward. I showed it to a colleague before posting the CL and she was like "What? None of our graphs fit that interface!" Thus was borne NodeID and the concept of compacting a general graph. That certainly makes it more useful for the many other graphs in x/tools, but perhaps the history of how I got here is causing me to cling too hard to the idea of user-defined compact graphs.
1. Okay, I'm happy to put it in this package.
2. With user-defined compact graphs, I intend Compact to be O(1).
To your more general question, even in algorithms, I see the mapping as only happening as pre- and post- processing, while the heart of the algorithm, which may be Ω(V), can operate on the much tighter (and often more convenient!) representation.
for i := range g.m.ids {Austin ClementsThis looks wrong for the edge case of identNodeMap. You could use `range g.NumNodes()`, but I think NumNodes has the same problem. Changing NumNodes return `g.g.NumNodes()` should fix both methods, but this requires that NumNodes be promoted to the Graph interface (which I think is the right move).
Alan DonovanCompact never returns a *compactGraph along with identNodeMap, so g.m will never be identNodeMap.
Reaching into the NodeMap here is arguably an abstraction violation, and leads to this source of confusion. Maybe I shouldn't use NodeMap in compactGraph?
If you promote NumNodes to Graph. then you can just range over it instead (since you know that graph is compact).
Done
type Edge[Node comparable] struct {Austin ClementsI don't think this type belongs here, as the graph abstraction doesn't materialize edges. Each client can declare a private `type edge struct{ from, to whatever }` as needed.
Alan DonovanI see what you're saying, but I'd like to keep this for two reasons: 1. Almost every client does wind up needing an edge type, so it's convenient! 2. There are certainly graph algorithms that need to talk about edges, so they need an edge type in this package anyway.
Which algorithms in the package need an edge type?
Alright, alright, I'll delete it. We can always add it back if an algorithm needs it.
func NewTranspose[G Graph[NodeID], NodeID comparable](g G) *Transpose[G, NodeID] {Austin ClementsIs it worth making NewTranspose(NewTranspose(g)) return g? I guess the need doesn't often arise.
Alan DonovanI don't think I can. Because Transpose is parameterized by G, I can't construct the type to test g against: `g.(*Transpose[???, NodeID])`.
Why not parameterize only by NodeID? You don't actually need G. In particular, it's not as if you return a graph of the same G type as the argument.
Oh! Indeed. Dropped the G type parameter and added this optimization.
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Austin Clements uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |