rotree.gno

  1// Package rotree provides a read-only wrapper for avl.Tree with safe value transformation.
  2//
  3// It is useful when you want to expose a read-only view of a tree while ensuring that
  4// the sensitive data cannot be modified.
  5//
  6// Example:
  7//
  8//	// Define a user structure with sensitive data
  9//	type User struct {
 10//		Name     string
 11//		Balance  int
 12//		Internal string // sensitive field
 13//	}
 14//
 15//	// Create and populate the original tree
 16//	privateTree := avl.NewTree()
 17//	privateTree.Set("alice", &User{
 18//		Name:     "Alice",
 19//		Balance:  100,
 20//		Internal: "sensitive",
 21//	})
 22//
 23//	// Create a safe transformation function that copies the struct
 24//	// while excluding sensitive data
 25//	makeEntrySafeFn := func(v any) any {
 26//		u := v.(*User)
 27//		return &User{
 28//			Name:     u.Name,
 29//			Balance:  u.Balance,
 30//			Internal: "", // omit sensitive data
 31//		}
 32//	}
 33//
 34//	// Create a read-only view of the tree
 35//	PublicTree := rotree.Wrap(tree, makeEntrySafeFn)
 36//
 37//	// Safely access the data
 38//	value := roTree.Get("alice")
 39//	user := value.(*User)
 40//	// user.Name == "Alice"
 41//	// user.Balance == 100
 42//	// user.Internal == "" (sensitive data is filtered)
 43package rotree
 44
 45import (
 46	"gno.land/p/nt/avl/v0"
 47)
 48
 49// Wrap creates a new ReadOnlyTree from an existing avl.Tree and a safety transformation function.
 50// If makeEntrySafeFn is nil, values will be returned as-is without transformation.
 51//
 52// makeEntrySafeFn is a function that transforms a tree entry into a safe version that can be exposed to external users.
 53// This function should be implemented based on the specific safety requirements of your use case:
 54//
 55//  1. No-op transformation: For primitive types (int, string, etc.) or already safe objects,
 56//     simply pass nil as the makeEntrySafeFn to return values as-is.
 57//
 58//  2. Defensive copying: For mutable types like slices or maps, you should create a deep copy
 59//     to prevent modification of the original data.
 60//     Example: func(v any) any { return append([]int{}, v.([]int)...) }
 61//
 62//  3. Read-only wrapper: Return a read-only version of the object that implements
 63//     a limited interface.
 64//     Example: func(v any) any { return NewReadOnlyObject(v) }
 65//
 66//  4. DAO transformation: Transform the object into a data access object that
 67//     controls how the underlying data can be accessed.
 68//     Example: func(v any) any { return NewDAO(v) }
 69//
 70// The function ensures that the returned object is safe to expose to untrusted code,
 71// preventing unauthorized modifications to the original data structure.
 72func Wrap(tree *avl.Tree, makeEntrySafeFn func(any) any) *ReadOnlyTree {
 73	return &ReadOnlyTree{
 74		tree:            tree,
 75		makeEntrySafeFn: makeEntrySafeFn,
 76	}
 77}
 78
 79// ReadOnlyTree wraps an avl.Tree and provides read-only access.
 80type ReadOnlyTree struct {
 81	tree            *avl.Tree
 82	makeEntrySafeFn func(any) any
 83}
 84
 85// IReadOnlyTree defines the read-only operations available on a tree.
 86type IReadOnlyTree interface {
 87	Size() int
 88	Has(key string) bool
 89	Get(key string) any
 90	GetByIndex(index int) (string, any)
 91	Iterate(start, end string, cb avl.IterCbFn) bool
 92	ReverseIterate(start, end string, cb avl.IterCbFn) bool
 93	IterateByOffset(offset int, count int, cb avl.IterCbFn) bool
 94	ReverseIterateByOffset(offset int, count int, cb avl.IterCbFn) bool
 95}
 96
 97// Verify that ReadOnlyTree implements both ITree and IReadOnlyTree
 98var (
 99	_ avl.ITree     = (*ReadOnlyTree)(nil)
100	_ IReadOnlyTree = (*ReadOnlyTree)(nil)
101)
102
103// getSafeValue applies the makeEntrySafeFn if it exists, otherwise returns the original value
104func (roTree *ReadOnlyTree) getSafeValue(value any) any {
105	if roTree.makeEntrySafeFn == nil {
106		return value
107	}
108	return roTree.makeEntrySafeFn(value)
109}
110
111// Size returns the number of key-value pairs in the tree.
112func (roTree *ReadOnlyTree) Size() int {
113	return roTree.tree.Size()
114}
115
116// Has checks whether a key exists in the tree.
117func (roTree *ReadOnlyTree) Has(key string) bool {
118	return roTree.tree.Has(key)
119}
120
121// Get retrieves the value associated with the given key, converted to a safe format.
122// It returns the value if the key exists, or nil if it doesn't.
123// Note that a key stored with a nil value is indistinguishable
124// from an absent key; use Has to check for existence.
125func (roTree *ReadOnlyTree) Get(key string) any {
126	value := roTree.tree.Get(key)
127	if value == nil {
128		return nil
129	}
130	return roTree.getSafeValue(value)
131}
132
133// GetByIndex retrieves the key-value pair at the specified index in the tree, with the value converted to a safe format.
134func (roTree *ReadOnlyTree) GetByIndex(index int) (string, any) {
135	key, value := roTree.tree.GetByIndex(index)
136	return key, roTree.getSafeValue(value)
137}
138
139// Iterate performs an in-order traversal of the tree within the specified key range.
140func (roTree *ReadOnlyTree) Iterate(start, end string, cb avl.IterCbFn) bool {
141	return roTree.tree.Iterate(start, end, func(key string, value any) bool {
142		return cb(key, roTree.getSafeValue(value))
143	})
144}
145
146// ReverseIterate performs a reverse in-order traversal of the tree within the specified key range.
147func (roTree *ReadOnlyTree) ReverseIterate(start, end string, cb avl.IterCbFn) bool {
148	return roTree.tree.ReverseIterate(start, end, func(key string, value any) bool {
149		return cb(key, roTree.getSafeValue(value))
150	})
151}
152
153// IterateByOffset performs an in-order traversal of the tree starting from the specified offset.
154func (roTree *ReadOnlyTree) IterateByOffset(offset int, count int, cb avl.IterCbFn) bool {
155	return roTree.tree.IterateByOffset(offset, count, func(key string, value any) bool {
156		return cb(key, roTree.getSafeValue(value))
157	})
158}
159
160// ReverseIterateByOffset performs a reverse in-order traversal of the tree starting from the specified offset.
161func (roTree *ReadOnlyTree) ReverseIterateByOffset(offset int, count int, cb avl.IterCbFn) bool {
162	return roTree.tree.ReverseIterateByOffset(offset, count, func(key string, value any) bool {
163		return cb(key, roTree.getSafeValue(value))
164	})
165}
166
167// Set is not supported on ReadOnlyTree and will panic.
168func (roTree *ReadOnlyTree) Set(key string, value any) bool {
169	panic("Set operation not supported on ReadOnlyTree")
170}
171
172// Remove is not supported on ReadOnlyTree and will panic.
173func (roTree *ReadOnlyTree) Remove(key string) (value any, removed bool) {
174	panic("Remove operation not supported on ReadOnlyTree")
175}
176
177// RemoveByIndex is not supported on ReadOnlyTree and will panic.
178func (roTree *ReadOnlyTree) RemoveByIndex(index int) (key string, value any) {
179	panic("RemoveByIndex operation not supported on ReadOnlyTree")
180}