Delete 'inspect visualize-nodes'

4 files changed, 24 insertions, 377 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go
index fc71558..8ee53d2 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go
@@ -10,9 +10,11 @@ import (
 	"io"
 	"strings"
 
+	"github.com/datawire/dlib/derror"
 	"github.com/datawire/dlib/dlog"
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
@@ -152,3 +154,25 @@ func loopRender(out io.Writer, scanData scanResult, stack ...btrfsvol.LogicalAdd
 		fmt.Fprintln(out, "    "+line)
 	}
 }
+
+func checkNodeExpectations(kp kpData, toNode nodeData) error {
+	var errs derror.MultiError
+	if toNode.Level != kp.ToLevel {
+		errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v",
+			kp.ToLevel, toNode.Level))
+	}
+	if toNode.Generation != kp.ToGeneration {
+		errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v",
+			kp.ToGeneration, toNode.Generation))
+	}
+	if toNode.NumItems == 0 {
+		errs = append(errs, fmt.Errorf("node.num_items=0"))
+	} else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey {
+		errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v",
+			kp.ToKey, toNode.MinItem))
+	}
+	if len(errs) > 0 {
+		return errs
+	}
+	return nil
+}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go
index 7e0eab1..f1033e6 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go
@@ -10,10 +10,6 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
 )
 
-func ptrTo[T any](x T) *T {
-	return &x
-}
-
 func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error {
 	if other, conflict := m[k]; conflict && other != v {
 		return fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v)
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go
index 7be903a..4d93916 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go
@@ -5,12 +5,8 @@
 package rebuildnodes
 
 import (
-	"fmt"
-	"strings"
-
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
 type uuidMap struct {
@@ -57,72 +53,3 @@ func (m uuidMap) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) {
 	}
 	return parentObjID, true
 }
-
-type fullAncestorLister struct {
-	uuidMap       uuidMap
-	treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]
-
-	memos map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]
-}
-
-func newFullAncestorLister(uuidMap uuidMap, treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) fullAncestorLister {
-	return fullAncestorLister{
-		uuidMap:       uuidMap,
-		treeAncestors: treeAncestors,
-		memos:         make(map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]),
-	}
-}
-
-type loopError []btrfsprim.ObjID
-
-func (le loopError) Error() string {
-	var buf strings.Builder
-	buf.WriteString("loop: ")
-	for i, treeID := range le {
-		if i > 0 {
-			buf.WriteString("->")
-		}
-		fmt.Fprintf(&buf, "%d", treeID)
-	}
-	return buf.String()
-}
-
-func (fa fullAncestorLister) GetFullAncestors(child btrfsprim.ObjID) containers.Set[btrfsprim.ObjID] {
-	if memoized, ok := fa.memos[child]; ok {
-		if memoized == nil {
-			panic(loopError{child})
-		}
-		return memoized
-	}
-	fa.memos[child] = nil
-	defer func() {
-		if r := recover(); r != nil {
-			if le, ok := r.(loopError); ok {
-				r = append(loopError{child}, le...)
-			}
-			panic(r)
-		}
-	}()
-
-	ret := make(containers.Set[btrfsprim.ObjID])
-	defer func() {
-		fa.memos[child] = ret
-	}()
-
-	// Try to use '.uuidMap' instead of '.treeAncestors' if possible.
-	knownAncestors := make(containers.Set[btrfsprim.ObjID])
-	if parent, ok := fa.uuidMap.ParentTree(child); ok {
-		if parent == 0 {
-			return ret
-		}
-		knownAncestors.Insert(parent)
-	} else {
-		knownAncestors.InsertFrom(fa.treeAncestors[child])
-	}
-
-	for _, ancestor := range maps.SortedKeys(knownAncestors) {
-		ret.Insert(ancestor)
-		ret.InsertFrom(fa.GetFullAncestors(ancestor))
-	}
-	return ret
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go
deleted file mode 100644
index fc9d19b..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go
+++ /dev/null
@@ -1,300 +0,0 @@
-// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildnodes
-
-import (
-	"archive/zip"
-	"context"
-	"fmt"
-	"html"
-	"io"
-	"strings"
-
-	"github.com/datawire/dlib/derror"
-	"github.com/datawire/dlib/dlog"
-
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
-	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
-)
-
-func getCliques(scanData scanResult) map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID] {
-	cliques := make(map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID])
-
-	// UUID map
-	lister := newFullAncestorLister(scanData.uuidMap, map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]{})
-	for _, treeID := range maps.SortedKeys(scanData.uuidMap.SeenTrees) {
-		clique := ptrTo(make(containers.Set[btrfsprim.ObjID]))
-		clique.Insert(treeID)
-		clique.InsertFrom(lister.GetFullAncestors(treeID))
-		for _, id := range maps.SortedKeys(*clique) {
-			if existingClique, ok := cliques[id]; ok {
-				clique.InsertFrom(*existingClique)
-			}
-			cliques[id] = clique
-		}
-	}
-
-	// node graph
-	for _, laddr := range maps.SortedKeys(scanData.nodeGraph.Nodes) {
-		clique := ptrTo(make(containers.Set[btrfsprim.ObjID]))
-		clique.Insert(scanData.nodeGraph.Nodes[laddr].Owner)
-		for _, edge := range scanData.nodeGraph.EdgesTo[laddr] {
-			clique.Insert(edge.FromTree)
-		}
-		for _, id := range maps.SortedKeys(*clique) {
-			if existingClique, ok := cliques[id]; ok {
-				clique.InsertFrom(*existingClique)
-			}
-			cliques[id] = clique
-		}
-	}
-	return cliques
-}
-
-func getCliqueID(cliques map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID], treeID btrfsprim.ObjID) btrfsprim.ObjID {
-	clique, ok := cliques[treeID]
-	if !ok {
-		panic(fmt.Errorf("tree ID %v was not in .SeenTrees", treeID))
-	}
-	return maps.SortedKeys(*clique)[0]
-}
-
-func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) error {
-	scanData, err := ScanDevices(ctx, fs, nodeScanResults)
-	if err != nil {
-		return err
-	}
-
-	////////////////////////////////////////////////////////////////////////////////////////////
-
-	dlog.Info(ctx, "Building cliques...")
-	cliques := getCliques(*scanData)
-	cliqueIDs := make(containers.Set[btrfsprim.ObjID])
-	for treeID := range cliques {
-		cliqueIDs.Insert(getCliqueID(cliques, treeID))
-	}
-	dlog.Infof(ctx, "... built %d cliques of %d trees", len(cliqueIDs), len(cliques))
-
-	////////////////////////////////////////////////////////////////////////////////////////////
-
-	dlog.Info(ctx, "Building graphviz graphs...")
-
-	type graph struct {
-		nodes    map[btrfsprim.ObjID]containers.Set[string] // keyed by treeID
-		badNodes containers.Set[string]
-		edges    containers.Set[string]
-	}
-	graphs := make(map[btrfsprim.ObjID]graph, len(cliques)) // keyed by cliqueID
-	for cliqueID := range cliqueIDs {
-		graphs[cliqueID] = graph{
-			nodes:    make(map[btrfsprim.ObjID]containers.Set[string]),
-			badNodes: make(containers.Set[string]),
-			edges:    make(containers.Set[string]),
-		}
-	}
-
-	dlog.Infof(ctx, "... processing %d nodes...", len(scanData.Nodes))
-
-	for _, laddr := range maps.SortedKeys(scanData.Nodes) {
-		nodeData := scanData.Nodes[laddr]
-		cliqueID := getCliqueID(cliques, nodeData.Owner)
-		graph, ok := graphs[cliqueID]
-		if !ok {
-			panic(cliqueID)
-		}
-		if graph.nodes[nodeData.Owner] == nil {
-			graph.nodes[nodeData.Owner] = make(containers.Set[string])
-		}
-
-		var buf strings.Builder
-		fmt.Fprintf(&buf, `n%d [shape=record label="{laddr=%v\lgen=%v\llvl=%v\litems=%v\l|{`,
-			laddr,
-			laddr,
-			nodeData.Generation,
-			nodeData.Level,
-			nodeData.NumItems)
-		if nodeData.Level == 0 {
-			buf.WriteString("leaf")
-		} else {
-			for i := uint32(0); i < nodeData.NumItems; i++ {
-				if i == 0 {
-					fmt.Fprintf(&buf, "<p%[1]d>%[1]d", i)
-				} else {
-					fmt.Fprintf(&buf, "|<p%[1]d>%[1]d", i)
-				}
-			}
-		}
-		buf.WriteString(`}}"]`)
-		graph.nodes[nodeData.Owner].Insert(buf.String())
-
-		if len(scanData.EdgesTo[laddr]) == 0 {
-			graph.edges.Insert(fmt.Sprintf("orphanRoot -> n%d", laddr))
-		}
-
-		graphs[cliqueID] = graph
-	}
-
-	dlog.Infof(ctx, "... processing %d bad nodes...", len(scanData.BadNodes))
-
-	for _, laddr := range maps.SortedKeys(scanData.BadNodes) {
-		cliqueIDs := make(containers.Set[btrfsprim.ObjID])
-		for _, edge := range scanData.EdgesTo[laddr] {
-			cliqueIDs.Insert(getCliqueID(cliques, edge.FromTree))
-		}
-		if len(cliqueIDs) != 1 {
-			dlog.Errorf(ctx, "couldn't assign bad node@%v to a clique: %v", laddr, maps.SortedKeys(cliqueIDs))
-			continue
-		}
-
-		cliqueID := cliqueIDs.TakeOne()
-		graph, ok := graphs[cliqueID]
-		if !ok {
-			panic(cliqueID)
-		}
-		graph.badNodes.Insert(fmt.Sprintf(`n%d [shape=star color=red label="%v\l\lerr=%s"]`,
-			laddr, laddr, gvEscape(scanData.BadNodes[laddr].Error()+"\n")))
-		graphs[cliqueID] = graph
-	}
-
-	numEdges := 0
-	for _, kps := range scanData.EdgesFrom {
-		numEdges += (len(kps))
-	}
-	dlog.Infof(ctx, "... processing %d keypointers...", numEdges)
-
-	for _, laddr := range maps.SortedKeys(scanData.EdgesFrom) {
-		for _, kp := range scanData.EdgesFrom[laddr] {
-			cliqueID := getCliqueID(cliques, kp.FromTree)
-			graph, ok := graphs[cliqueID]
-			if !ok {
-				panic(cliqueID)
-			}
-
-			var buf strings.Builder
-			if kp.FromNode == 0 {
-				if graph.nodes[kp.FromTree] == nil {
-					graph.nodes[kp.FromTree] = make(containers.Set[string])
-				}
-				graph.nodes[kp.FromTree].Insert(fmt.Sprintf(`t%d [label="root of %s"]`, kp.FromTree, gvEscape(kp.FromTree.String())))
-				fmt.Fprintf(&buf, "t%d", kp.FromTree)
-			} else {
-				fmt.Fprintf(&buf, "n%d:p%d", kp.FromNode, kp.FromItem)
-			}
-			fmt.Fprintf(&buf, ` -> n%d`, kp.ToNode)
-
-			var err error
-			toNode, ok := scanData.Nodes[kp.ToNode]
-			if !ok {
-				err = scanData.BadNodes[kp.ToNode]
-			} else {
-				err = checkNodeExpectations(*kp, toNode)
-			}
-			if err != nil {
-				fmt.Fprintf(&buf, ` [label="key=(%d,%v,%d) gen=%v\l\lerr=%s" color=red]`,
-					kp.ToKey.ObjectID,
-					kp.ToKey.ItemType,
-					kp.ToKey.Offset,
-					kp.ToGeneration,
-					gvEscape(err.Error()+"\n"))
-			}
-
-			graph.edges.Insert(buf.String())
-			graphs[cliqueID] = graph
-		}
-	}
-
-	////////////////////////////////////////////////////////////////////////////////////////////
-
-	dlog.Info(ctx, "Writing graphviz output...")
-
-	zw := zip.NewWriter(out)
-	for _, cliqueID := range maps.SortedKeys(graphs) {
-		if err := func() (err error) {
-			graph := graphs[cliqueID]
-
-			buf, err := zw.Create(fmt.Sprintf("%d.dot", cliqueID))
-			if err != nil {
-				return err
-			}
-			if _, err := fmt.Fprintf(buf, "strict digraph clique%d {\n", cliqueID); err != nil {
-				return err
-			}
-			if _, err := fmt.Fprintf(buf, "rankdir=LR;\n  nodesep=0.1;\n  ranksep=25;\n  splines=line;\n"); err != nil {
-				return err
-			}
-			for _, treeID := range maps.SortedKeys(graph.nodes) {
-				nodes := graph.nodes[treeID]
-
-				if _, err := fmt.Fprintf(buf, "  subgraph cluster_tree%d {\n", treeID); err != nil {
-					return err
-				}
-				for _, node := range maps.SortedKeys(nodes) {
-					if _, err := fmt.Fprintf(buf, "    %s;\n", node); err != nil {
-						return err
-					}
-				}
-				if _, err := fmt.Fprintln(buf, "  }"); err != nil {
-					return err
-				}
-			}
-			for _, node := range maps.SortedKeys(graph.badNodes) {
-				if _, err := fmt.Fprintf(buf, "  %s;\n", node); err != nil {
-					return err
-				}
-			}
-			for _, edge := range maps.SortedKeys(graph.edges) {
-				if _, err := fmt.Fprintf(buf, "  %s;\n", edge); err != nil {
-					return err
-				}
-			}
-
-			if _, err := fmt.Fprintln(buf, "}"); err != nil {
-				return err
-			}
-			return nil
-		}(); err != nil {
-			return err
-		}
-	}
-	if err := zw.Close(); err != nil {
-		return err
-	}
-
-	dlog.Info(ctx, "... done writing")
-
-	return nil
-}
-
-func gvEscape(str string) string {
-	str = html.EscapeString(str)
-	str = strings.ReplaceAll(str, "\n", `\l`)
-	str = strings.ReplaceAll(str, `\n`, `\l`)
-	return str
-}
-
-func checkNodeExpectations(kp kpData, toNode nodeData) error {
-	var errs derror.MultiError
-	if toNode.Level != kp.ToLevel {
-		errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v",
-			kp.ToLevel, toNode.Level))
-	}
-	if toNode.Generation != kp.ToGeneration {
-		errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v",
-			kp.ToGeneration, toNode.Generation))
-	}
-	if toNode.NumItems == 0 {
-		errs = append(errs, fmt.Errorf("node.num_items=0"))
-	} else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey {
-		errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v",
-			kp.ToKey, toNode.MinItem))
-	}
-	if len(errs) > 0 {
-		return errs
-	}
-	return nil
-}