FF170986765387…200D2E11E67A

Arguments · 15

1. #1ulist
2. #2README.md
3. #3# `gno.land/p/moul/ulist/v1` Append-only list backed by a binary tree, with index-preserving compaction. An index is the element's position in the tree, so `Delete` is a *soft* delete: it clears the data and leaves the node, because moving a live element would silently invalidate an index another realm is holding. That leaves reclaimable storage behind, and on gno.land storage is money: every byte of realm state locks GNOT, refunded to whoever signs the transaction that frees it. `v1` adds the pair that turns those dead nodes back into a refund: | | | |---|---| | `Compactable() int` | how many nodes a compaction would free, **right now, for free**. Reads nothing, mutates nothing, so a caller can poll it before paying gas | | `Compact() int` | frees every node whose subtree holds no live element, and returns how many. Nothing live moves, so every index stays valid and `TotalSize` is unchanged | ### Which deletions can be compacted, which cannot Index 0 is the root and index `i` sits at depth `bitlen(i+1)-1`, so **the oldest indices are the ancestors of the newest.** A node is only freeable when its whole subtree is dead, which gives a result worth knowing before you design around this: | You delete | `Compactable` | Why | |---|---|---| | the oldest entries | **0**, always | every newer entry keeps their ancestors alive | | the newest entries | immediately non-zero | they are the leaves | Measured on chain with 32 entries of 512 bytes: deleting the oldest 16 refunded 8,896 bytes and left nothing to compact. Deleting the newest 16 refunded the same 8,896 bytes and then `Compact` returned **a further 27,679**, because a node costs far more than the payload it holds. The structure is roughly two thirds of the total cost, so being unable to compact leaves most of the money on the table. **So an expiry queue that reaps oldest-first can never compact**, which is the opposite of the intuition. Delete from the top down, or wait for a run of deletions to reach the leaves. `Compactable` is free, so a caller never has to guess which case it is in. **`v1`, not an addition to `v0`, because one behaviour changes:** a soft-deleted element can be restored with `Set`, but not once `Compact` has freed its node and the deposit has been refunded. `Set` on such an index returns `ErrOutOfBounds`. That is the trade the refund pays for. [`v0`](https://github.com/moul/gno-contracts/tree/f6d0693f5161db423c042a4fe7c78057593cff80/p/moul/ulist) is unchanged and still deployed: it is part of the gnoland1 genesis set. Whether compacting is worth its gas depends on the gas price of the day, which a contract cannot know. [`p/moul/x/storagecost`](https://github.com/moul/gno-contracts/tree/main/p/moul/x/storagecost) turns a `Compactable` count into a verdict in GNOT, and [`r/moul/x/reaper`](https://github.com/moul/gno-contracts/tree/main/r/moul/x/reaper) is a realm that does it in public. <!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) --> --- Part of **[moul/gno-contracts](https://github.com/moul/gno-contracts)** — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage. > ⚠️ **Disclaimer:** provided as-is, without warranty; not security-audited. Full disclaimer: [DISCLAIMER](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md). <!-- END GNOCONTRACTS FOOTER -->
4. #4compact.gno
5. #5package ulist // Compaction: turning soft deletes back into refunded storage. // // Delete is a soft delete. It clears the element's data but leaves the tree // node in place, because the node's position IS the index: indices are the // public addressing scheme, and moving a live element would silently // invalidate an index some other realm is holding. // // That leaves reclaimable storage behind. On gno.land every byte of realm // state locks GNOT, refunded to whoever signs the transaction that frees it, // so those dead nodes are money sitting in the structure. // // Compact reclaims them without moving anything live, by dropping whole // subtrees that contain no live element. Nothing live moves, so every index // stays valid. // // # Which deletions can actually be compacted // // This is the counterintuitive part, and it decides whether compaction is // worth anything at all. Index 0 is the root and index i sits at depth // bitlen(i+1)-1, so the OLDEST indices are the ANCESTORS of the newest. A node // is only freeable when its whole subtree is dead. Therefore: // // - Deleting the oldest entries frees no nodes at all, however many you // delete, because every newer entry keeps their ancestors alive. An expiry // queue reaping oldest-first is exactly this case. // - Deleting the newest entries frees nodes immediately, because they are // the leaves. // // Measured on chain, 32 entries of 512 bytes each: deleting the oldest 16 // refunded 8,896 bytes and left Compactable at zero. Deleting the newest 16 // instead refunded the same 8,896 bytes and then Compact returned a further // 27,679, because a ulist node costs far more than the payload it holds. The // structure is roughly two thirds of the total cost, so being unable to // compact leaves most of the money on the table. // // The practical rule: compaction pays in proportion to how much of the // deepest layer is dead. Delete from the top down, or wait until a run of // deletions reaches the leaves. // // Whether it is worth doing is not a question this package can answer, since // it depends on the gas price of the day. Compactable reports the size of the // prize as a free read so a caller can decide; gno.land/p/moul/x/storagecost/v0 // turns that count into a verdict in GNOT. // Compactable reports how many tree nodes Compact would free right now. // // It reads and mutates nothing, so a caller can poll it to decide whether // compaction is worth its gas before paying for it. Zero means every dead node // still shares a subtree with a live element, and compacting would cost gas to // free nothing. func (l *List) Compactable() int { if l == nil || l.root == nil { return 0 } // The root is never freed, so only its subtrees are counted. n, _ := prunableNodes(l.root) return n } // Compact frees every tree node whose subtree holds no live element, and // returns the number of nodes freed. // // Indices are preserved exactly: TotalSize is unchanged, Size is unchanged, // and every live element keeps the index it had. Appends continue from the // same number. // // Deleted elements swept up by a Compact become permanently unrestorable: // Set on such an index returns ErrOutOfBounds where before it would have // restored the value. That is the trade the refund pays for, and it is the // reason this behaviour is v1 rather than an addition to v0. func (l *List) Compact() int { if l == nil || l.root == nil { return 0 } // The root is deliberately never freed. findNode treats a nil root as an // empty list and returns the root for every index, so a tree that still // has a totalSize but no root would write index 0 on the next append. // Keeping one node costs a few dozen bytes and keeps that unreachable. freed, _ := pruneDead(l.root) return freed } // pruneDead drops n's fully dead subtrees, returning how many nodes were freed // and whether n's own subtree is now dead. A dead subtree is one in which no // node holds data. func pruneDead(n *treeNode) (freed int, dead bool) { if n == nil { return 0, true } leftFreed, leftDead := pruneDead(n.left) rightFreed, rightDead := pruneDead(n.right) freed = leftFreed + rightFreed // A dead child's own descendants have already been counted and unlinked by // the recursive call, so the child itself is the one node left to free. if leftDead && n.left != nil { n.left = nil freed++ } if rightDead && n.right != nil { n.right = nil freed++ } return freed, n.data == nil && n.left == nil && n.right == nil } // prunableNodes is pruneDead without the mutation, so Compactable and Compact // can never disagree about the count. func prunableNodes(n *treeNode) (prunable int, dead bool) { if n == nil { return 0, true } leftPrunable, leftDead := prunableNodes(n.left) rightPrunable, rightDead := prunableNodes(n.right) prunable = leftPrunable + rightPrunable if leftDead && n.left != nil { prunable++ } if rightDead && n.right != nil { prunable++ } return prunable, n.data == nil && (n.left == nil || leftDead) && (n.right == nil || rightDead) }
6. #6compact_test.gno
7. #7package ulist import ( "testing" "gno.land/p/nt/uassert/v0" ) // countNodes walks the tree directly, so the tests assert against the real // structure rather than against Compact's own bookkeeping. func countNodes(n *treeNode) int { if n == nil { return 0 } return 1 + countNodes(n.left) + countNodes(n.right) } func TestCompactEmptyAndNil(t *testing.T) { var nilList *List uassert.Equal(t, 0, nilList.Compactable()) uassert.Equal(t, 0, nilList.Compact()) l := New() uassert.Equal(t, 0, l.Compactable()) uassert.Equal(t, 0, l.Compact()) } func TestCompactNothingDeleted(t *testing.T) { l := New() l.Append(generateSequence(20)...) before := countNodes(l.root) uassert.Equal(t, 0, l.Compactable()) uassert.Equal(t, 0, l.Compact()) uassert.Equal(t, before, countNodes(l.root)) uassert.Equal(t, 20, l.Size()) uassert.Equal(t, 20, l.TotalSize()) } func TestCompactFreesOnlyFullyDeadSubtrees(t *testing.T) { tests := []struct { name string size int deleted []int }{ {"nothing deleted", 16, nil}, {"one deleted", 16, []int{9}}, {"leading run", 32, []int{0, 1, 2, 3, 4, 5, 6, 7}}, {"trailing run", 32, []int{24, 25, 26, 27, 28, 29, 30, 31}}, {"every other", 32, []int{1, 3, 5, 7, 9, 11, 13, 15}}, {"all but one", 16, []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}}, {"all of them", 16, []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14}}, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { l := New() l.Append(generateSequence(tt.size)...) for _, i := range tt.deleted { uassert.NoError(t, l.Delete(i)) } // Every surviving element, recorded before the compaction. survivors := map[int]any{} for i := 0; i < tt.size; i++ { if v := l.Get(i); v != nil { survivors[i] = v } } predicted := l.Compactable() nodesBefore := countNodes(l.root) freed := l.Compact() // Compactable and Compact must agree, and both must match the tree. uassert.Equal(t, predicted, freed) uassert.Equal(t, nodesBefore-freed, countNodes(l.root)) // A second pass has nothing left to do: Compact is idempotent. uassert.Equal(t, 0, l.Compactable()) uassert.Equal(t, 0, l.Compact()) // Indices are preserved: every survivor is still at its own index, // and the sizes are untouched. uassert.Equal(t, tt.size, l.TotalSize()) uassert.Equal(t, len(survivors), l.Size()) for i, want := range survivors { uassert.Equal(t, want, l.Get(i)) } // Appends continue from the same number. l.Append("after") uassert.Equal(t, "after", l.Get(tt.size)) uassert.Equal(t, tt.size+1, l.TotalSize()) }) } } func TestCompactNeverFreesTheRoot(t *testing.T) { // Index 0 is the root. Deleting everything must still leave it, or // findNode would treat the list as empty and write the next append to // index 0. l := New() l.Append("a", "b", "c") uassert.NoError(t, l.Delete(0, 1, 2)) l.Compact() uassert.True(t, l.root != nil) uassert.Equal(t, 1, countNodes(l.root)) uassert.Equal(t, 0, l.Size()) uassert.Equal(t, 3, l.TotalSize()) l.Append("d") uassert.Equal(t, "d", l.Get(3)) uassert.Equal(t, nil, l.Get(0)) } func TestCompactMakesDeletedElementsUnrestorable(t *testing.T) { // The documented behaviour change against v0: a soft-deleted element can // be restored with Set, but not once its node has been freed and the // storage deposit refunded. l := New() l.Append(generateSequence(8)...) uassert.NoError(t, l.Delete(4, 5, 6, 7)) // Before compaction: restoring works. uassert.NoError(t, l.Set(5, "restored")) uassert.Equal(t, "restored", l.Get(5)) uassert.NoError(t, l.Delete(5)) uassert.True(t, l.Compact() > 0) // After compaction: the node is gone, so there is nothing to restore. uassert.Error(t, l.Set(5, "restored again")) uassert.Equal(t, nil, l.Get(5)) // And a live element is still perfectly settable. uassert.NoError(t, l.Set(1, "still here")) uassert.Equal(t, "still here", l.Get(1)) } func TestCompactLeavesIterationUnchanged(t *testing.T) { collect := func(l *List) []Entry { var got []Entry l.Iterator(0, l.TotalSize()-1, func(i int, v any) bool { got = append(got, Entry{Index: i, Value: v}) return false }) return got } l := New() l.Append(generateSequence(24)...) uassert.NoError(t, l.Delete(16, 17, 18, 19, 20, 21, 22, 23)) before := collect(l) l.Compact() after := collect(l) uassert.Equal(t, len(before), len(after)) for i := range before { uassert.Equal(t, before[i].Index, after[i].Index) uassert.Equal(t, before[i].Value, after[i].Value) } }
8. #8gnomod.toml
9. #9module = "gno.land/p/moul/ulist/v1" gno = "0.9" [addpkg] creator = "g1manfred47kzduec920z88wfr64ylksmdcedlf5"
10. #10ulist.gno
11. #11// Package ulist provides an append-only list implementation using a binary tree structure, // optimized for scenarios requiring sequential inserts with auto-incrementing indices. // // The implementation uses a binary tree where new elements are added by following a path // determined by the binary representation of the index. This provides automatic balancing // for append operations without requiring any balancing logic. // // Unlike the AVL tree-based list implementation (p/demo/avl/list), ulist is specifically // designed for append-only operations and does not require rebalancing. This makes it more // efficient for sequential inserts but less flexible for general-purpose list operations. // // Key differences from AVL list: // * Append-only design (no arbitrary inserts) // * No tree rebalancing needed // * Simpler implementation // * More memory efficient for sequential operations // * Less flexible than AVL (no arbitrary inserts/reordering) // // Key characteristics: // * O(log n) append and access operations // * Perfect balance for power-of-2 sizes // * No balancing needed // * Memory efficient // * Natural support for range queries // * Support for soft deletion of elements, and index-preserving compaction of // what those deletions leave behind (see compact.gno) // * Forward and reverse iteration capabilities // * Offset-based iteration with count control package ulist // TODO: Make avl/pager compatible in some way. Explain the limitations (not always 10 items because of nil ones). // TODO: Use this ulist in moul/collection for the primary index. // TODO: Benchmarks. import ( "errors" ) // List represents an append-only binary tree list type List struct { root *treeNode totalSize int activeSize int } // Entry represents a key-value pair in the list, where Index is the position // and Value is the stored data type Entry struct { Index int Value any } // treeNode represents a node in the binary tree type treeNode struct { data any left *treeNode right *treeNode } // Error variables var ( ErrOutOfBounds = errors.New("index out of bounds") ErrDeleted = errors.New("element already deleted") ) // New creates a new empty List instance func New() *List { return &List{} } // Append adds one or more values to the end of the list. // Values are added sequentially, and the list grows automatically. func (l *List) Append(values ...any) { for _, value := range values { index := l.totalSize node := l.findNode(index, true) node.data = value l.totalSize++ l.activeSize++ } } // Get retrieves the value at the specified index. // Returns nil if the index is out of bounds or if the element was deleted. func (l *List) Get(index int) any { node := l.findNode(index, false) if node == nil { return nil } return node.data } // Delete marks the elements at the specified indices as deleted. // Returns ErrOutOfBounds if any index is invalid or ErrDeleted if // the element was already deleted. func (l *List) Delete(indices ...int) error { if len(indices) == 0 { return nil } if l == nil || l.totalSize == 0 { return ErrOutOfBounds } for _, index := range indices { if index < 0 || index >= l.totalSize { return ErrOutOfBounds } node := l.findNode(index, false) if node == nil || node.data == nil { return ErrDeleted } node.data = nil l.activeSize-- } return nil } // Set updates or restores a value at the specified index if within bounds // Returns ErrOutOfBounds if the index is invalid func (l *List) Set(index int, value any) error { if l == nil || index < 0 || index >= l.totalSize { return ErrOutOfBounds } node := l.findNode(index, false) if node == nil { return ErrOutOfBounds } // If this is restoring a deleted element if value != nil && node.data == nil { l.activeSize++ } // If this is deleting an element if value == nil && node.data != nil { l.activeSize-- } node.data = value return nil } // Size returns the number of active (non-deleted) elements in the list func (l *List) Size() int { if l == nil { return 0 } return l.activeSize } // TotalSize returns the total number of elements ever added to the list, // including deleted elements func (l *List) TotalSize() int { if l == nil { return 0 } return l.totalSize } // IterCbFn is a callback function type used in iteration methods. // Return true to stop iteration, false to continue. type IterCbFn func(index int, value any) bool // Iterator performs iteration between start and end indices, calling cb for each entry. // If start > end, iteration is performed in reverse order. // Returns true if iteration was stopped early by the callback returning true. // Skips deleted elements. func (l *List) Iterator(start, end int, cb IterCbFn) bool { // For empty list or invalid range if l == nil || l.totalSize == 0 { return false } if start < 0 && end < 0 { return false } if start >= l.totalSize && end >= l.totalSize { return false } // Normalize indices if start < 0 { start = 0 } if end < 0 { end = 0 } if end >= l.totalSize { end = l.totalSize - 1 } if start >= l.totalSize { start = l.totalSize - 1 } // Handle reverse iteration if start > end { for i := start; i >= end; i-- { val := l.Get(i) if val != nil { if cb(i, val) { return true } } } return false } // Handle forward iteration for i := start; i <= end; i++ { val := l.Get(i) if val != nil { if cb(i, val) { return true } } } return false } // IteratorByOffset performs iteration starting from offset for count elements. // If count is positive, iterates forward; if negative, iterates backward. // The iteration stops after abs(count) elements or when reaching list bounds. // Skips deleted elements. func (l *List) IteratorByOffset(offset int, count int, cb IterCbFn) bool { if count == 0 || l == nil || l.totalSize == 0 { return false } // Normalize offset if offset < 0 { offset = 0 } if offset >= l.totalSize { offset = l.totalSize - 1 } // Determine end based on count direction var end int if count > 0 { end = l.totalSize - 1 } else { end = 0 } wrapperReturned := false // Wrap the callback to limit iterations remaining := abs(count) wrapper := func(index int, value any) bool { if remaining <= 0 { wrapperReturned = true return true } remaining-- return cb(index, value) } ret := l.Iterator(offset, end, wrapper) if wrapperReturned { return false } return ret } // abs returns the absolute value of x func abs(x int) int { if x < 0 { return -x } return x } // findNode locates or creates a node at the given index in the binary tree. // The tree is structured such that the path to a node is determined by the binary // representation of the index. For example, a tree with 15 elements would look like: // // 0 // / \ // 1 2 // / \ / \ // 3 4 5 6 // / \ / \ / \ / \ // 7 8 9 10 11 12 13 14 // // To find index 13 (binary 1101): // 1. Start at root (0) // 2. Calculate bits needed (4 bits for index 13) // 3. Skip the highest bit position and start from bits-2 // 4. Read bits from left to right: // - 1 -> go right to 2 // - 1 -> go right to 6 // - 0 -> go left to 13 // // Special cases: // - Index 0 always returns the root node // - For create=true, missing nodes are created along the path // - For create=false, returns nil if any node is missing func (l *List) findNode(index int, create bool) *treeNode { // For read operations, check bounds strictly if !create && (l == nil || index < 0 || index >= l.totalSize) { return nil } // For create operations, allow index == totalSize for append if create && (l == nil || index < 0 || index > l.totalSize) { return nil } // Initialize root if needed if l.root == nil { if !create { return nil } l.root = &treeNode{} return l.root } node := l.root // Special case for root node if index == 0 { return node } // Calculate the number of bits needed (inline highestBit logic) bits := 0 n := index + 1 for n > 0 { n >>= 1 bits++ } // Start from the second highest bit for level := bits - 2; level >= 0; level-- { bit := (index & (1 << uint(level))) != 0 if bit { if node.right == nil { if !create { return nil } node.right = &treeNode{} } node = node.right } else { if node.left == nil { if !create { return nil } node.left = &treeNode{} } node = node.left } } return node } // MustDelete deletes elements at the specified indices. // Panics if any index is invalid or if any element was already deleted. func (l *List) MustDelete(indices ...int) { if err := l.Delete(indices...); err != nil { panic(err) } } // MustGet retrieves the value at the specified index. // Panics if the index is out of bounds or if the element was deleted. func (l *List) MustGet(index int) any { if l == nil || index < 0 || index >= l.totalSize { panic(ErrOutOfBounds) } value := l.Get(index) if value == nil { panic(ErrDeleted) } return value } // MustSet updates or restores a value at the specified index. // Panics if the index is out of bounds. func (l *List) MustSet(index int, value any) { if err := l.Set(index, value); err != nil { panic(err) } } // GetRange returns a slice of Entry containing elements between start and end indices. // If start > end, elements are returned in reverse order. // Deleted elements are skipped. func (l *List) GetRange(start, end int) []Entry { var entries []Entry l.Iterator(start, end, func(index int, value any) bool { entries = append(entries, Entry{Index: index, Value: value}) return false }) return entries } // GetByOffset returns a slice of Entry starting from offset for count elements. // If count is positive, returns elements forward; if negative, returns elements backward. // The operation stops after abs(count) elements or when reaching list bounds. // Deleted elements are skipped. func (l *List) GetByOffset(offset int, count int) []Entry { var entries []Entry l.IteratorByOffset(offset, count, func(index int, value any) bool { entries = append(entries, Entry{Index: index, Value: value}) return false }) return entries } // IList defines the interface for an ulist.List compatible structure. type IList interface { // Basic operations Append(values ...any) Get(index int) any Delete(indices ...int) error Size() int TotalSize() int Set(index int, value any) error // Must variants that panic instead of returning errors MustDelete(indices ...int) MustGet(index int) any MustSet(index int, value any) // Range operations GetRange(start, end int) []Entry GetByOffset(offset int, count int) []Entry // Iterator operations Iterator(start, end int, cb IterCbFn) bool IteratorByOffset(offset int, count int, cb IterCbFn) bool } // Verify that List implements IList var _ IList = (*List)(nil)
12. #12ulist_test.gno
13. #13package ulist import ( "testing" "gno.land/p/moul/typeutil/v0" "gno.land/p/nt/uassert/v0" "gno.land/p/nt/ufmt/v0" ) func TestNew(t *testing.T) { l := New() uassert.Equal(t, 0, l.Size()) uassert.Equal(t, 0, l.TotalSize()) } func TestListAppendAndGet(t *testing.T) { tests := []struct { name string setup func() *List index int expected any }{ { name: "empty list", setup: func() *List { return New() }, index: 0, expected: nil, }, { name: "single append and get", setup: func() *List { l := New() l.Append(42) return l }, index: 0, expected: 42, }, { name: "multiple appends and get first", setup: func() *List { l := New() l.Append(1) l.Append(2) l.Append(3) return l }, index: 0, expected: 1, }, { name: "multiple appends and get last", setup: func() *List { l := New() l.Append(1) l.Append(2) l.Append(3) return l }, index: 2, expected: 3, }, { name: "get with invalid index", setup: func() *List { l := New() l.Append(1) return l }, index: 1, expected: nil, }, { name: "31 items get first", setup: func() *List { l := New() for i := 0; i < 31; i++ { l.Append(i) } return l }, index: 0, expected: 0, }, { name: "31 items get last", setup: func() *List { l := New() for i := 0; i < 31; i++ { l.Append(i) } return l }, index: 30, expected: 30, }, { name: "31 items get middle", setup: func() *List { l := New() for i := 0; i < 31; i++ { l.Append(i) } return l }, index: 15, expected: 15, }, { name: "values around power of 2 boundary", setup: func() *List { l := New() for i := 0; i < 18; i++ { l.Append(i) } return l }, index: 15, expected: 15, }, { name: "values at power of 2", setup: func() *List { l := New() for i := 0; i < 18; i++ { l.Append(i) } return l }, index: 16, expected: 16, }, { name: "values after power of 2", setup: func() *List { l := New() for i := 0; i < 18; i++ { l.Append(i) } return l }, index: 17, expected: 17, }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { l := tt.setup() got := l.Get(tt.index) if got != tt.expected { t.Errorf("List.Get() = %v, want %v", got, tt.expected) } }) } } // generateSequence creates a slice of integers from 0 to n-1 func generateSequence(n int) []any { result := make([]any, n) for i := 0; i < n; i++ { result[i] = i } return result } func TestListDelete(t *testing.T) { tests := []struct { name string setup func() *List deleteIndices []int expectedErr error expectedSize int }{ { name: "delete single element", setup: func() *List { l := New() l.Append(1, 2, 3) return l }, deleteIndices: []int{1}, expectedErr: nil, expectedSize: 2, }, { name: "delete multiple elements", setup: func() *List { l := New() l.Append(1, 2, 3, 4, 5) return l }, deleteIndices: []int{0, 2, 4}, expectedErr: nil, expectedSize: 2, }, { name: "delete with negative index", setup: func() *List { l := New() l.Append(1) return l }, deleteIndices: []int{-1}, expectedErr: ErrOutOfBounds, expectedSize: 1, }, { name: "delete beyond size", setup: func() *List { l := New() l.Append(1) return l }, deleteIndices: []int{1}, expectedErr: ErrOutOfBounds, expectedSize: 1, }, { name: "delete already deleted element", setup: func() *List { l := New() l.Append(1) l.Delete(0) return l }, deleteIndices: []int{0}, expectedErr: ErrDeleted, expectedSize: 0, }, { name: "delete multiple elements in reverse", setup: func() *List { l := New() l.Append(1, 2, 3, 4, 5) return l }, deleteIndices: []int{4, 2, 0}, expectedErr: nil, expectedSize: 2, }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { l := tt.setup() initialSize := l.Size() err := l.Delete(tt.deleteIndices...) if err != nil && tt.expectedErr != nil { uassert.ErrorIs(t, err, tt.expectedErr) } else { uassert.Equal(t, tt.expectedErr, err) } uassert.Equal(t, tt.expectedSize, l.Size(), ufmt.Sprintf("Expected size %d after deleting %d elements from size %d, got %d", tt.expectedSize, len(tt.deleteIndices), initialSize, l.Size())) }) } } func TestListSizeAndTotalSize(t *testing.T) { t.Run("empty list", func(t *testing.T) { list := New() uassert.Equal(t, 0, list.Size()) uassert.Equal(t, 0, list.TotalSize()) }) t.Run("list with elements", func(t *testing.T) { list := New() list.Append(1) list.Append(2) list.Append(3) uassert.Equal(t, 3, list.Size()) uassert.Equal(t, 3, list.TotalSize()) }) t.Run("list with deleted elements", func(t *testing.T) { list := New() list.Append(1) list.Append(2) list.Append(3) list.Delete(1) uassert.Equal(t, 2, list.Size()) uassert.Equal(t, 3, list.TotalSize()) }) } func TestIterator(t *testing.T) { tests := []struct { name string values []any start int end int expected []Entry wantStop bool stopAfter int // stop after N elements, -1 for no stop }{ { name: "empty list", values: []any{}, start: 0, end: 10, expected: []Entry{}, stopAfter: -1, }, { name: "nil list", values: nil, start: 0, end: 0, expected: []Entry{}, stopAfter: -1, }, { name: "single element forward", values: []any{42}, start: 0, end: 0, expected: []Entry{ {Index: 0, Value: 42}, }, stopAfter: -1, }, { name: "multiple elements forward", values: []any{1, 2, 3, 4, 5}, start: 0, end: 4, expected: []Entry{ {Index: 0, Value: 1}, {Index: 1, Value: 2}, {Index: 2, Value: 3}, {Index: 3, Value: 4}, {Index: 4, Value: 5}, }, stopAfter: -1, }, { name: "multiple elements reverse", values: []any{1, 2, 3, 4, 5}, start: 4, end: 0, expected: []Entry{ {Index: 4, Value: 5}, {Index: 3, Value: 4}, {Index: 2, Value: 3}, {Index: 1, Value: 2}, {Index: 0, Value: 1}, }, stopAfter: -1, }, { name: "partial range forward", values: []any{1, 2, 3, 4, 5}, start: 1, end: 3, expected: []Entry{ {Index: 1, Value: 2}, {Index: 2, Value: 3}, {Index: 3, Value: 4}, }, stopAfter: -1, }, { name: "partial range reverse", values: []any{1, 2, 3, 4, 5}, start: 3, end: 1, expected: []Entry{ {Index: 3, Value: 4}, {Index: 2, Value: 3}, {Index: 1, Value: 2}, }, stopAfter: -1, }, { name: "stop iteration early", values: []any{1, 2, 3, 4, 5}, start: 0, end: 4, wantStop: true, stopAfter: 2, expected: []Entry{ {Index: 0, Value: 1}, {Index: 1, Value: 2}, }, }, { name: "negative start", values: []any{1, 2, 3}, start: -1, end: 2, expected: []Entry{ {Index: 0, Value: 1}, {Index: 1, Value: 2}, {Index: 2, Value: 3}, }, stopAfter: -1, }, { name: "negative end", values: []any{1, 2, 3}, start: 0, end: -2, expected: []Entry{ {Index: 0, Value: 1}, }, stopAfter: -1, }, { name: "start beyond size", values: []any{1, 2, 3}, start: 5, end: 6, expected: []Entry{}, stopAfter: -1, }, { name: "end beyond size", values: []any{1, 2, 3}, start: 0, end: 5, expected: []Entry{ {Index: 0, Value: 1}, {Index: 1, Value: 2}, {Index: 2, Value: 3}, }, stopAfter: -1, }, { name: "with deleted elements", values: []any{1, 2, nil, 4, 5}, start: 0, end: 4, expected: []Entry{ {Index: 0, Value: 1}, {Index: 1, Value: 2}, {Index: 3, Value: 4}, {Index: 4, Value: 5}, }, stopAfter: -1, }, { name: "with deleted elements reverse", values: []any{1, nil, 3, nil, 5}, start: 4, end: 0, expected: []Entry{ {Index: 4, Value: 5}, {Index: 2, Value: 3}, {Index: 0, Value: 1}, }, stopAfter: -1, }, { name: "start equals end", values: []any{1, 2, 3}, start: 1, end: 1, expected: []Entry{{Index: 1, Value: 2}}, stopAfter: -1, }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { list := New() list.Append(tt.values...) var result []Entry stopped := list.Iterator(tt.start, tt.end, func(index int, value any) bool { result = append(result, Entry{Index: index, Value: value}) return tt.stopAfter >= 0 && len(result) >= tt.stopAfter }) uassert.Equal(t, len(result), len(tt.expected), "comparing length") for i := range result { uassert.Equal(t, result[i].Index, tt.expected[i].Index, "comparing index") uassert.Equal(t, typeutil.ToString(result[i].Value), typeutil.ToString(tt.expected[i].Value), "comparing value") } uassert.Equal(t, stopped, tt.wantStop, "comparing stopped") }) } } func TestLargeListAppendGetAndDelete(t *testing.T) { l := New() size := 100 // Append values from 0 to 99 for i := 0; i < size; i++ { l.Append(i) val := l.Get(i) uassert.Equal(t, i, val) } // Verify size uassert.Equal(t, size, l.Size()) uassert.Equal(t, size, l.TotalSize()) // Get and verify each value for i := 0; i < size; i++ { val := l.Get(i) uassert.Equal(t, i, val) } // Get and verify each value for i := 0; i < size; i++ { err := l.Delete(i) uassert.Equal(t, nil, err) } // Verify size uassert.Equal(t, 0, l.Size()) uassert.Equal(t, size, l.TotalSize()) // Get and verify each value for i := 0; i < size; i++ { val := l.Get(i) uassert.Equal(t, nil, val) } } func TestEdgeCases(t *testing.T) { tests := []struct { name string test func(t *testing.T) }{ { name: "nil list operations", test: func(t *testing.T) { var l *List uassert.Equal(t, 0, l.Size()) uassert.Equal(t, 0, l.TotalSize()) uassert.Equal(t, nil, l.Get(0)) err := l.Delete(0) uassert.ErrorIs(t, err, ErrOutOfBounds) }, }, { name: "delete empty indices slice", test: func(t *testing.T) { l := New() l.Append(1) err := l.Delete() uassert.Equal(t, nil, err) uassert.Equal(t, 1, l.Size()) }, }, { name: "append nil values", test: func(t *testing.T) { l := New() l.Append(nil, nil) uassert.Equal(t, 2, l.Size()) uassert.Equal(t, nil, l.Get(0)) uassert.Equal(t, nil, l.Get(1)) }, }, { name: "delete same index multiple times", test: func(t *testing.T) { l := New() l.Append(1, 2, 3) err := l.Delete(1) uassert.Equal(t, nil, err) err = l.Delete(1) uassert.ErrorIs(t, err, ErrDeleted) }, }, { name: "iterator with all deleted elements", test: func(t *testing.T) { l := New() l.Append(1, 2, 3) l.Delete(0, 1, 2) var count int l.Iterator(0, 2, func(index int, value any) bool { count++ return false }) uassert.Equal(t, 0, count) }, }, { name: "append after delete", test: func(t *testing.T) { l := New() l.Append(1, 2) l.Delete(1) l.Append(3) uassert.Equal(t, 2, l.Size()) uassert.Equal(t, 3, l.TotalSize()) uassert.Equal(t, 1, l.Get(0)) uassert.Equal(t, nil, l.Get(1)) uassert.Equal(t, 3, l.Get(2)) }, }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { tt.test(t) }) } } func TestIteratorByOffset(t *testing.T) { tests := []struct { name string values []any offset int count int expected []Entry wantStop bool }{ { name: "empty list", values: []any{}, offset: 0, count: 5, expected: []Entry{}, wantStop: false, }, { name: "positive count forward iteration", values: []any{1, 2, 3, 4, 5}, offset: 1, count: 2, expected: []Entry{ {Index: 1, Value: 2}, {Index: 2, Value: 3}, }, wantStop: false, }, { name: "negative count backward iteration", values: []any{1, 2, 3, 4, 5}, offset: 3, count: -2, expected: []Entry{ {Index: 3, Value: 4}, {Index: 2, Value: 3}, }, wantStop: false, }, { name: "count exceeds available elements forward", values: []any{1, 2, 3}, offset: 1, count: 5, expected: []Entry{ {Index: 1, Value: 2}, {Index: 2, Value: 3}, }, wantStop: false, }, { name: "count exceeds available elements backward", values: []any{1, 2, 3}, offset: 1, count: -5, expected: []Entry{ {Index: 1, Value: 2}, {Index: 0, Value: 1}, }, wantStop: false, }, { name: "zero count", values: []any{1, 2, 3}, offset: 0, count: 0, expected: []Entry{}, wantStop: false, }, { name: "negative offset", values: []any{1, 2, 3}, offset: -1, count: 2, expected: []Entry{ {Index: 0, Value: 1}, {Index: 1, Value: 2}, }, wantStop: false, }, { name: "offset beyond size", values: []any{1, 2, 3}, offset: 5, count: -2, expected: []Entry{ {Index: 2, Value: 3}, {Index: 1, Value: 2}, }, wantStop: false, }, { name: "with deleted elements", values: []any{1, nil, 3, nil, 5}, offset: 0, count: 3, expected: []Entry{ {Index: 0, Value: 1}, {Index: 2, Value: 3}, {Index: 4, Value: 5}, }, wantStop: false, }, { name: "early stop in forward iteration", values: []any{1, 2, 3, 4, 5}, offset: 0, count: 5, expected: []Entry{ {Index: 0, Value: 1}, {Index: 1, Value: 2}, }, wantStop: true, // The callback will return true after 2 elements }, { name: "early stop in backward iteration", values: []any{1, 2, 3, 4, 5}, offset: 4, count: -5, expected: []Entry{ {Index: 4, Value: 5}, {Index: 3, Value: 4}, }, wantStop: true, // The callback will return true after 2 elements }, { name: "nil list", values: nil, offset: 0, count: 5, expected: []Entry{}, wantStop: false, }, { name: "single element forward", values: []any{1}, offset: 0, count: 5, expected: []Entry{ {Index: 0, Value: 1}, }, wantStop: false, }, { name: "single element backward", values: []any{1}, offset: 0, count: -5, expected: []Entry{ {Index: 0, Value: 1}, }, wantStop: false, }, { name: "all deleted elements", values: []any{nil, nil, nil}, offset: 0, count: 3, expected: []Entry{}, wantStop: false, }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { list := New() list.Append(tt.values...) var result []Entry var cb IterCbFn if tt.wantStop { cb = func(index int, value any) bool { result = append(result, Entry{Index: index, Value: value}) return len(result) >= 2 // Stop after 2 elements for early stop tests } } else { cb = func(index int, value any) bool { result = append(result, Entry{Index: index, Value: value}) return false } } stopped := list.IteratorByOffset(tt.offset, tt.count, cb) uassert.Equal(t, len(tt.expected), len(result), "comparing length") for i := range result { uassert.Equal(t, tt.expected[i].Index, result[i].Index, "comparing index") uassert.Equal(t, typeutil.ToString(tt.expected[i].Value), typeutil.ToString(result[i].Value), "comparing value") } uassert.Equal(t, tt.wantStop, stopped, "comparing stopped") }) } } func TestMustDelete(t *testing.T) { tests := []struct { name string setup func() *List indices []int shouldPanic bool panicMsg string }{ { name: "successful delete", setup: func() *List { l := New() l.Append(1, 2, 3) return l }, indices: []int{1}, shouldPanic: false, }, { name: "out of bounds", setup: func() *List { l := New() l.Append(1) return l }, indices: []int{1}, shouldPanic: true, panicMsg: ErrOutOfBounds.Error(), }, { name: "already deleted", setup: func() *List { l := New() l.Append(1) l.Delete(0) return l }, indices: []int{0}, shouldPanic: true, panicMsg: ErrDeleted.Error(), }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { l := tt.setup() if tt.shouldPanic { defer func() { r := recover() if r == nil { t.Error("Expected panic but got none") } err, ok := r.(error) if !ok { t.Errorf("Expected error but got %v", r) } uassert.Equal(t, tt.panicMsg, err.Error()) }() } l.MustDelete(tt.indices...) if tt.shouldPanic { t.Error("Expected panic") } }) } } func TestMustGet(t *testing.T) { tests := []struct { name string setup func() *List index int expected any shouldPanic bool panicMsg string }{ { name: "successful get", setup: func() *List { l := New() l.Append(42) return l }, index: 0, expected: 42, shouldPanic: false, }, { name: "out of bounds negative", setup: func() *List { l := New() l.Append(1) return l }, index: -1, shouldPanic: true, panicMsg: ErrOutOfBounds.Error(), }, { name: "out of bounds positive", setup: func() *List { l := New() l.Append(1) return l }, index: 1, shouldPanic: true, panicMsg: ErrOutOfBounds.Error(), }, { name: "deleted element", setup: func() *List { l := New() l.Append(1) l.Delete(0) return l }, index: 0, shouldPanic: true, panicMsg: ErrDeleted.Error(), }, { name: "nil list", setup: func() *List { return nil }, index: 0, shouldPanic: true, panicMsg: ErrOutOfBounds.Error(), }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { l := tt.setup() if tt.shouldPanic { defer func() { r := recover() if r == nil { t.Error("Expected panic but got none") } err, ok := r.(error) if !ok { t.Errorf("Expected error but got %v", r) } uassert.Equal(t, tt.panicMsg, err.Error()) }() } result := l.MustGet(tt.index) if tt.shouldPanic { t.Error("Expected panic") } uassert.Equal(t, typeutil.ToString(tt.expected), typeutil.ToString(result)) }) } } func TestGetRange(t *testing.T) { tests := []struct { name string values []any start int end int expected []Entry }{ { name: "empty list", values: []any{}, start: 0, end: 10, expected: []Entry{}, }, { name: "single element", values: []any{42}, start: 0, end: 0, expected: []Entry{ {Index: 0, Value: 42}, }, }, { name: "multiple elements forward", values: []any{1, 2, 3, 4, 5}, start: 1, end: 3, expected: []Entry{ {Index: 1, Value: 2}, {Index: 2, Value: 3}, {Index: 3, Value: 4}, }, }, { name: "multiple elements reverse", values: []any{1, 2, 3, 4, 5}, start: 3, end: 1, expected: []Entry{ {Index: 3, Value: 4}, {Index: 2, Value: 3}, {Index: 1, Value: 2}, }, }, { name: "with deleted elements", values: []any{1, nil, 3, nil, 5}, start: 0, end: 4, expected: []Entry{ {Index: 0, Value: 1}, {Index: 2, Value: 3}, {Index: 4, Value: 5}, }, }, { name: "nil list", values: nil, start: 0, end: 5, expected: []Entry{}, }, { name: "negative indices", values: []any{1, 2, 3}, start: -1, end: -2, expected: []Entry{}, }, { name: "indices beyond size", values: []any{1, 2, 3}, start: 1, end: 5, expected: []Entry{ {Index: 1, Value: 2}, {Index: 2, Value: 3}, }, }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { list := New() list.Append(tt.values...) result := list.GetRange(tt.start, tt.end) uassert.Equal(t, len(tt.expected), len(result), "comparing length") for i := range result { uassert.Equal(t, tt.expected[i].Index, result[i].Index, "comparing index") uassert.Equal(t, typeutil.ToString(tt.expected[i].Value), typeutil.ToString(result[i].Value), "comparing value") } }) } } func TestGetByOffset(t *testing.T) { tests := []struct { name string values []any offset int count int expected []Entry }{ { name: "empty list", values: []any{}, offset: 0, count: 5, expected: []Entry{}, }, { name: "positive count forward", values: []any{1, 2, 3, 4, 5}, offset: 1, count: 2, expected: []Entry{ {Index: 1, Value: 2}, {Index: 2, Value: 3}, }, }, { name: "negative count backward", values: []any{1, 2, 3, 4, 5}, offset: 3, count: -2, expected: []Entry{ {Index: 3, Value: 4}, {Index: 2, Value: 3}, }, }, { name: "count exceeds available elements", values: []any{1, 2, 3}, offset: 1, count: 5, expected: []Entry{ {Index: 1, Value: 2}, {Index: 2, Value: 3}, }, }, { name: "zero count", values: []any{1, 2, 3}, offset: 0, count: 0, expected: []Entry{}, }, { name: "with deleted elements", values: []any{1, nil, 3, nil, 5}, offset: 0, count: 3, expected: []Entry{ {Index: 0, Value: 1}, {Index: 2, Value: 3}, {Index: 4, Value: 5}, }, }, { name: "negative offset", values: []any{1, 2, 3}, offset: -1, count: 2, expected: []Entry{ {Index: 0, Value: 1}, {Index: 1, Value: 2}, }, }, { name: "offset beyond size", values: []any{1, 2, 3}, offset: 5, count: -2, expected: []Entry{ {Index: 2, Value: 3}, {Index: 1, Value: 2}, }, }, { name: "nil list", values: nil, offset: 0, count: 5, expected: []Entry{}, }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { list := New() list.Append(tt.values...) result := list.GetByOffset(tt.offset, tt.count) uassert.Equal(t, len(tt.expected), len(result), "comparing length") for i := range result { uassert.Equal(t, tt.expected[i].Index, result[i].Index, "comparing index") uassert.Equal(t, typeutil.ToString(tt.expected[i].Value), typeutil.ToString(result[i].Value), "comparing value") } }) } } func TestMustSet(t *testing.T) { tests := []struct { name string setup func() *List index int value any shouldPanic bool panicMsg string }{ { name: "successful set", setup: func() *List { l := New() l.Append(42) return l }, index: 0, value: 99, shouldPanic: false, }, { name: "restore deleted element", setup: func() *List { l := New() l.Append(42) l.Delete(0) return l }, index: 0, value: 99, shouldPanic: false, }, { name: "out of bounds negative", setup: func() *List { l := New() l.Append(1) return l }, index: -1, value: 99, shouldPanic: true, panicMsg: ErrOutOfBounds.Error(), }, { name: "out of bounds positive", setup: func() *List { l := New() l.Append(1) return l }, index: 1, value: 99, shouldPanic: true, panicMsg: ErrOutOfBounds.Error(), }, { name: "nil list", setup: func() *List { return nil }, index: 0, value: 99, shouldPanic: true, panicMsg: ErrOutOfBounds.Error(), }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { l := tt.setup() if tt.shouldPanic { defer func() { r := recover() if r == nil { t.Error("Expected panic but got none") } err, ok := r.(error) if !ok { t.Errorf("Expected error but got %v", r) } uassert.Equal(t, tt.panicMsg, err.Error()) }() } l.MustSet(tt.index, tt.value) if tt.shouldPanic { t.Error("Expected panic") } // Verify the value was set correctly for non-panic cases if !tt.shouldPanic { result := l.Get(tt.index) uassert.Equal(t, typeutil.ToString(tt.value), typeutil.ToString(result)) } }) } } func TestSet(t *testing.T) { tests := []struct { name string setup func() *List index int value any expectedErr error verify func(t *testing.T, l *List) }{ { name: "set value in empty list", setup: func() *List { return New() }, index: 0, value: 42, expectedErr: ErrOutOfBounds, verify: func(t *testing.T, l *List) { uassert.Equal(t, 0, l.Size()) }, }, { name: "set value at valid index", setup: func() *List { l := New() l.Append(1) return l }, index: 0, value: 42, verify: func(t *testing.T, l *List) { uassert.Equal(t, 42, l.Get(0)) uassert.Equal(t, 1, l.Size()) uassert.Equal(t, 1, l.TotalSize()) }, }, { name: "set value at negative index", setup: func() *List { l := New() l.Append(1) return l }, index: -1, value: 42, expectedErr: ErrOutOfBounds, verify: func(t *testing.T, l *List) { uassert.Equal(t, 1, l.Get(0)) }, }, { name: "set value beyond size", setup: func() *List { l := New() l.Append(1) return l }, index: 1, value: 42, expectedErr: ErrOutOfBounds, verify: func(t *testing.T, l *List) { uassert.Equal(t, 1, l.Get(0)) uassert.Equal(t, 1, l.Size()) }, }, { name: "set nil value", setup: func() *List { l := New() l.Append(1) return l }, index: 0, value: nil, verify: func(t *testing.T, l *List) { uassert.Equal(t, nil, l.Get(0)) uassert.Equal(t, 0, l.Size()) }, }, { name: "set value at deleted index", setup: func() *List { l := New() l.Append(1, 2, 3) l.Delete(1) return l }, index: 1, value: 42, verify: func(t *testing.T, l *List) { uassert.Equal(t, 42, l.Get(1)) uassert.Equal(t, 3, l.Size()) uassert.Equal(t, 3, l.TotalSize()) }, }, { name: "set value in nil list", setup: func() *List { return nil }, index: 0, value: 42, expectedErr: ErrOutOfBounds, verify: func(t *testing.T, l *List) { uassert.Equal(t, 0, l.Size()) }, }, { name: "set multiple values at same index", setup: func() *List { l := New() l.Append(1) return l }, index: 0, value: 42, verify: func(t *testing.T, l *List) { uassert.Equal(t, 42, l.Get(0)) err := l.Set(0, 99) uassert.Equal(t, nil, err) uassert.Equal(t, 99, l.Get(0)) uassert.Equal(t, 1, l.Size()) }, }, { name: "set value at last index", setup: func() *List { l := New() l.Append(1, 2, 3) return l }, index: 2, value: 42, verify: func(t *testing.T, l *List) { uassert.Equal(t, 42, l.Get(2)) uassert.Equal(t, 3, l.Size()) }, }, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { l := tt.setup() err := l.Set(tt.index, tt.value) if tt.expectedErr != nil { uassert.ErrorIs(t, err, tt.expectedErr) } else { uassert.Equal(t, nil, err) } tt.verify(t, l) }) } }
14. #14/gno.MemPackageType
15. #15 MPUserAll