Add ToKey to TreePaths; MinItem and MaxItem to NodeExpectations

4 files changed, 41 insertions, 9 deletions

diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go
index acbdd23..d7db225 100644
--- a/lib/btrfs/btrfstree/ops.go
+++ b/lib/btrfs/btrfstree/ops.go
@@ -176,6 +176,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
 				ToNodeAddr:       item.BlockPtr,
 				ToNodeGeneration: item.Generation,
 				ToNodeLevel:      node.Data.Head.Level - 1,
+				ToKey:            item.Key,
 			})
 			if cbs.PreKeyPointer != nil {
 				if err := cbs.PreKeyPointer(itemPath, item); err != nil {
@@ -199,6 +200,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
 			itemPath := append(path, TreePathElem{
 				FromTree:    node.Data.Head.Owner,
 				FromItemIdx: i,
+				ToKey:       item.Key,
 			})
 			if errBody, isErr := item.Body.(btrfsitem.Error); isErr {
 				if cbs.BadItem == nil {
@@ -273,6 +275,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
 				ToNodeAddr:       node.Data.BodyInternal[lastGood].BlockPtr,
 				ToNodeGeneration: node.Data.BodyInternal[lastGood].Generation,
 				ToNodeLevel:      node.Data.Head.Level - 1,
+				ToKey:            node.Data.BodyInternal[lastGood].Key,
 			})
 		} else {
 			// leaf node
@@ -296,6 +299,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
 			path = append(path, TreePathElem{
 				FromTree:    node.Data.Head.Owner,
 				FromItemIdx: idx,
+				ToKey:       node.Data.BodyLeaf[idx].Key,
 			})
 			return path, node, nil
 		}
@@ -339,11 +343,13 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical
 				ToNodeAddr:       node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
 				ToNodeGeneration: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Generation,
 				ToNodeLevel:      node.Data.Head.Level - 1,
+				ToKey:            node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Key,
 			})
 		} else {
 			path = append(path, TreePathElem{
 				FromTree:    node.Data.Head.Owner,
 				FromItemIdx: len(node.Data.BodyLeaf) - 1,
+				ToKey:       node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key,
 			})
 		}
 	}
@@ -409,11 +415,13 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical
 				ToNodeAddr:       node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
 				ToNodeGeneration: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Generation,
 				ToNodeLevel:      node.Data.Head.Level - 1,
+				ToKey:            node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Key,
 			})
 		} else {
 			path = append(path, TreePathElem{
 				FromTree:    node.Data.Head.Owner,
 				FromItemIdx: 0,
+				ToKey:       node.Data.BodyInternal[0].Key,
 			})
 		}
 	}
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index 212b5df..b40c7ed 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -85,6 +85,10 @@ type TreePathElem struct {
 	// ToNodeAddr, or 0 if this is a leaf item and nothing is
 	// being pointed at.
 	ToNodeLevel uint8
+	// ToKey is btrfprim.Key{} this is the root node being pointed
+	// to, the KeyPointer.Key if this is a non-root node being
+	// pointed to, or the key of the leaf item being bointed to.
+	ToKey btrfsprim.Key
 }
 
 func (elem TreePathElem) writeNodeTo(w io.Writer) {
diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go
index a84e7ee..1c5dd21 100644
--- a/lib/btrfs/btrfstree/readnode.go
+++ b/lib/btrfs/btrfstree/readnode.go
@@ -67,5 +67,6 @@ func FSReadNode(
 		Level:      containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
 		Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).ToNodeGeneration},
 		Owner:      checkOwner,
+		MinItem:    containers.Optional[btrfsprim.Key]{OK: true, Val: path.Node(-1).ToKey},
 	})
 }
diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go
index 59411a0..299c433 100644
--- a/lib/btrfs/btrfstree/types_node.go
+++ b/lib/btrfs/btrfstree/types_node.go
@@ -9,6 +9,8 @@ import (
 	"errors"
 	"fmt"
 
+	"github.com/datawire/dlib/derror"
+
 	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
@@ -386,6 +388,9 @@ type NodeExpectations struct {
 	Level      containers.Optional[uint8]
 	Generation containers.Optional[btrfsprim.Generation]
 	Owner      func(btrfsprim.ObjID) error
+	MinItem    containers.Optional[btrfsprim.Key]
+	// Things knowable from the structure of the tree.
+	MaxItem containers.Optional[btrfsprim.Key]
 }
 
 type NodeError[Addr ~int64] struct {
@@ -472,24 +477,38 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N
 
 	// sanity checking (that doesn't prevent parsing)
 
+	var errs derror.MultiError
 	if exp.LAddr.OK && nodeRef.Data.Head.Addr != exp.LAddr.Val {
-		return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr,
-			Err: fmt.Errorf("read from laddr=%v but claims to be at laddr=%v",
-				exp.LAddr.Val, nodeRef.Data.Head.Addr)}
+		errs = append(errs, fmt.Errorf("read from laddr=%v but claims to be at laddr=%v",
+			exp.LAddr.Val, nodeRef.Data.Head.Addr))
 	}
 	if exp.Level.OK && nodeRef.Data.Head.Level != exp.Level.Val {
-		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected level=%v but claims to be level=%v",
-			addr, exp.Level.Val, nodeRef.Data.Head.Level)
+		errs = append(errs, fmt.Errorf("expected level=%v but claims to be level=%v",
+			exp.Level.Val, nodeRef.Data.Head.Level))
 	}
 	if exp.Generation.OK && nodeRef.Data.Head.Generation != exp.Generation.Val {
-		return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr,
-			Err: fmt.Errorf("expected generation=%v but claims to be generation=%v",
-				exp.Generation.Val, nodeRef.Data.Head.Generation)}
+		errs = append(errs, fmt.Errorf("expected generation=%v but claims to be generation=%v",
+			exp.Generation.Val, nodeRef.Data.Head.Generation))
 	}
 	if exp.Owner != nil {
 		if err := exp.Owner(nodeRef.Data.Head.Owner); err != nil {
-			return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: err}
+			errs = append(errs, err)
+		}
+	}
+	if nodeRef.Data.Head.NumItems == 0 {
+		errs = append(errs, fmt.Errorf("has no items"))
+	} else {
+		if minItem, _ := nodeRef.Data.MinItem(); exp.MinItem.OK && exp.MinItem.Val.Cmp(minItem) > 0 {
+			errs = append(errs, fmt.Errorf("expected minItem>=%v but node has minItem=%v",
+				exp.MinItem, minItem))
 		}
+		if maxItem, _ := nodeRef.Data.MaxItem(); exp.MaxItem.OK && exp.MaxItem.Val.Cmp(maxItem) < 0 {
+			errs = append(errs, fmt.Errorf("expected maxItem<=%v but node has maxItem=%v",
+				exp.MaxItem, maxItem))
+		}
+	}
+	if len(errs) > 0 {
+		return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: errs}
 	}
 
 	// return