18745049026

Committed 23 Oct 2025 10:12AM UTC coverage: 68.825% (-1.1%) from 69.927%

Build # 18745049026

Build Type

push

github

Committed by

ghettovoice

Commit Message

Use cache only in benchmarks, disable it in tests

Run Details

1499 of 2178 relevant lines covered (68.82%)

54.97 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

50.79

/node.go

package abnf

import (
        "bytes"
        "encoding/binary"
        "hash"
        "hash/fnv"
        "sync"
        "sync/atomic"
        "unsafe"

        lru "github.com/hashicorp/golang-lru/v2"
)

// Node represents a single node in a tree generated by [Operator].
type Node struct {
        Key      string
        Pos      uint
        Value    []byte
        Children Nodes
}

// String returns the node's value as string.
func (n *Node) String() string {
        if n == nil {
                return ""
        }
        return string(n.Value)
}

// Len returns length of the node's value.
func (n *Node) Len() int {
        if n == nil {
                return 0
        }
        return len(n.Value)
}

// IsEmpty returns true if the node's value length = 0.
func (n *Node) IsEmpty() bool { return n == nil || len(n.Value) == 0 }

// Contains returns whether the subtree contains the given key.
func (n *Node) Contains(key string) bool {
        if n == nil {
                return false
        }
        _, ok := n.GetNode(key)
        return ok
}

// GetNode recursively searches a node with the given key starting from itself.
// Returns found node or nil if not found.
func (n *Node) GetNode(key string) (*Node, bool) {
        if n == nil {
                return nil, false
        }
        if n.Key == key {
                return n, true
        }
        return n.Children.Get(key)
}

// GetNodes recursively searches all nodes with the given key starting from itself.
func (n *Node) GetNodes(key string) Nodes {
        if n == nil {
                return nil
        }

        var ns Nodes
        if n.Key == key {
                ns = append(ns, n)
        }
        ns = append(ns, n.Children.GetAll(key)...)
        return ns
}

// Compare compares node values via [bytes.Compare].
// The result will be 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
func (n *Node) Compare(other *Node) int {
        if n == other {
                return 0
        } else if n == nil {
                return -1
        } else if other == nil {
                return 1
        }
        return bytes.Compare(n.Value, other.Value)
}

var nodeCache atomic.Pointer[lru.Cache[uint64, *Node]]

// EnableNodeCache initializes the node cache.
// If size is 0, it will be set to 1024.
// By default, the cache is disabled.
// It does nothing if the cache is already enabled.
// Call this function before using any [Operator], usually in the [init].
func EnableNodeCache(size uint) {
        if nodeCache.Load() != nil {
                return
        }

        if size == 0 {
                size = 1024
        }

        cache, _ := lru.New[uint64, *Node](int(size))
        nodeCache.Store(cache)
}

// ResizeNodeCache resizes the node cache.
// If size is 0, it will be set to 1024.
// It does nothing if the cache is disabled.
// It is safe to call this function from multiple goroutines.
func ResizeNodeCache(size uint) {
        if size == 0 {
                size = 1024
        }

        if cache := nodeCache.Load(); cache != nil {
                cache.Resize(int(size))
        }
}

// DisableNodeCache disables the node cache and purges all cached nodes.
// It does nothing if the cache is already disabled.
// It is safe to call this function from multiple goroutines.
func DisableNodeCache() {
        if cache := nodeCache.Swap(nil); cache != nil {
                cache.Purge()
        }
}

type nodeCacheKey struct {
        hash.Hash64
        buf [8]byte
}

var nodeCacheKeyPool = sync.Pool{
        New: func() any { return &nodeCacheKey{fnv.New64a(), [8]byte{}} },
}

func newNodeCacheKey(key string, pos uint, len uint, input []byte, ns ...*Node) *nodeCacheKey {
        ck := nodeCacheKeyPool.Get().(*nodeCacheKey)
        ck.writeBase(key, pos, len, input)
        ck.writeChildKeys(0, ns...)
        return ck
}

func (ck *nodeCacheKey) free() {
        if ck == nil {
                return
        }

        ck.Reset()
        nodeCacheKeyPool.Put(ck)
}

func (ck *nodeCacheKey) writeBase(key string, pos uint, len uint, input []byte) {
        ck.Write(unsafeStringToBytes(key))

        binary.BigEndian.PutUint64(ck.buf[:], uint64(pos))
        ck.Write(ck.buf[:])

        binary.BigEndian.PutUint64(ck.buf[:], uint64(len))
        ck.Write(ck.buf[:])

        ck.Write(input)
}

func (ck *nodeCacheKey) writeChildKeys(depth uint, ns ...*Node) {
        for _, n := range ns {
                binary.BigEndian.PutUint64(ck.buf[:], uint64(depth))
                ck.Write(ck.buf[:])
                ck.Write(unsafeStringToBytes(n.Key))
                ck.writeChildKeys(depth+1, n.Children...)
        }
}

func (ck *nodeCacheKey) hash() uint64 { return ck.Sum64() }

// unsafeStringToBytes converts string to []byte without allocation
// WARNING: The returned byte slice must not be modified
func unsafeStringToBytes(s string) []byte {
        return *(*[]byte)(unsafe.Pointer(&struct {
                string
                int
        }{s, len(s)}))
}

func loadNode(k *nodeCacheKey) (*Node, bool) {
        cache := nodeCache.Load()
        if cache == nil {
                return nil, false
        }

        n, ok := cache.Get(k.hash())
        if !ok {
                return nil, false
        }
        return n, true
}

func storeNode(k *nodeCacheKey, n *Node) {
        cache := nodeCache.Load()
        if cache == nil {
                return
        }

        cache.Add(k.hash(), n)
}

func loadOrStoreNode(k *nodeCacheKey, newNode func() *Node) *Node {
        defer k.free()

        cache := nodeCache.Load()
        if cache == nil {
                return newNode()
        }

        if n, ok := loadNode(k); ok {
                return n
        }

        n := newNode()
        storeNode(k, n)
        return n
}

// Nodes represents a list of nodes.
type Nodes []*Node

// Contains returns whether the subtree contains the given key.
func (ns Nodes) Contains(key string) bool {
        for _, n := range ns {
                if n.Key == key || n.Children.Contains(key) {
                        return true
                }
        }
        return false
}

// Get recursively searches a node with the given key.
func (ns Nodes) Get(key string) (*Node, bool) {
        for _, n := range ns {
                if n.Key == key {
                        return n, true
                }
                if n, ok := n.Children.Get(key); ok {
                        return n, true
                }
        }
        return nil, false
}

// GetAll recursively searches all nodes with the given key.
func (ns Nodes) GetAll(key string) Nodes {
        var nodes Nodes
        for _, n := range ns {
                if n.Key == key {
                        nodes = append(nodes, n)
                }
                nodes = append(nodes, n.Children.GetAll(key)...)
        }
        return nodes
}

// Best returns a node with the longest value or nil if the list is empty.
func (ns Nodes) Best() *Node {
        if len(ns) == 0 {
                return nil
        }

        best := ns[0]
        for _, n := range ns[1:] {
                if n.Len() > best.Len() {
                        best = n
                }
        }
        return best
}

// Compare compares two best nodes.
// The result will be 0 if a == b, -1 if a < b, and +1 if a > b where a - self best node, b - other best node.
func (ns Nodes) Compare(other Nodes) int {
        return ns.Best().Compare(other.Best())
}

func (ns *Nodes) Append(n ...*Node) {
        *ns = append(*ns, n...)
}

// NodesCap is a initial capacity of a new nodes list.
var NodesCap = 100

var nodesPool = &sync.Pool{
        New: func() any {
                ns := make(Nodes, 0, NodesCap)
                return &ns
        },
}

// NewNodes returns a new nodes list from the pool.
func NewNodes() Nodes {
        ns := nodesPool.Get().(*Nodes)
        return *ns
}

// Clear clears the nodes list.
func (ns *Nodes) Clear() {
        if ns == nil {
                return
        }

        clear(*ns)
        *ns = (*ns)[:0]
}

// Free returns the nodes list to the pool.
func (ns *Nodes) Free() {
        ns.Clear()

        if ns == nil || cap(*ns) == 0 || cap(*ns) > 10*NodesCap {
                return
        }

        nodesPool.Put(ns)
}

1	package abnf
2
3	import (
4	"bytes"
5	"encoding/binary"
6	"hash"
7	"hash/fnv"
8	"sync"
9	"sync/atomic"
10	"unsafe"
11
12	lru "github.com/hashicorp/golang-lru/v2"
13	)
14
15	// Node represents a single node in a tree generated by [Operator].
16	type Node struct {
17	Key string
18	Pos uint
19	Value []byte
20	Children Nodes
21	}
22
23	// String returns the node's value as string.
24	func (n *Node) String() string {	3✔
25	if n == nil {	3✔
26	return ""	×
27	}	×
28	return string(n.Value)	3✔
29	}
30
31	// Len returns length of the node's value.
32	func (n *Node) Len() int {	48✔
33	if n == nil {	48✔
34	return 0	×
35	}	×
36	return len(n.Value)	48✔
37	}
38
39	// IsEmpty returns true if the node's value length = 0.
40	func (n *Node) IsEmpty() bool { return n == nil \|\| len(n.Value) == 0 }	×
41
42	// Contains returns whether the subtree contains the given key.
43	func (n *Node) Contains(key string) bool {	×
44	if n == nil {	×
45	return false	×
46	}	×
47	_, ok := n.GetNode(key)	×
48	return ok	×
49	}
50
51	// GetNode recursively searches a node with the given key starting from itself.
52	// Returns found node or nil if not found.
53	func (n Node) GetNode(key string) (Node, bool) {	3✔
54	if n == nil {	3✔
55	return nil, false	×
56	}	×
57	if n.Key == key {	4✔
58	return n, true	1✔
59	}	1✔
60	return n.Children.Get(key)	2✔
61	}
62
63	// GetNodes recursively searches all nodes with the given key starting from itself.
64	func (n *Node) GetNodes(key string) Nodes {	×
65	if n == nil {	×
66	return nil	×
67	}	×
68
69	var ns Nodes	×
70	if n.Key == key {	×
71	ns = append(ns, n)	×
72	}	×
73	ns = append(ns, n.Children.GetAll(key)...)	×
74	return ns	×
75	}
76
77	// Compare compares node values via [bytes.Compare].
78	// The result will be 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
79	func (n Node) Compare(other Node) int {	35✔
80	if n == other {	35✔
81	return 0	×
82	} else if n == nil {	35✔
83	return -1	×
84	} else if other == nil {	35✔
85	return 1	×
86	}	×
87	return bytes.Compare(n.Value, other.Value)	35✔
88	}
89
90	var nodeCache atomic.Pointer[lru.Cache[uint64, *Node]]
91
92	// EnableNodeCache initializes the node cache.
93	// If size is 0, it will be set to 1024.
94	// By default, the cache is disabled.
95	// It does nothing if the cache is already enabled.
96	// Call this function before using any [Operator], usually in the [init].
97	func EnableNodeCache(size uint) {	×
98	if nodeCache.Load() != nil {	×
99	return	×
100	}	×
101
102	if size == 0 {	×
103	size = 1024	×
104	}	×
105
106	cache, _ := lru.New[uint64, *Node](int(size))	×
107	nodeCache.Store(cache)	×
108	}
109
110	// ResizeNodeCache resizes the node cache.
111	// If size is 0, it will be set to 1024.
112	// It does nothing if the cache is disabled.
113	// It is safe to call this function from multiple goroutines.
114	func ResizeNodeCache(size uint) {	×
115	if size == 0 {	×
116	size = 1024	×
117	}	×
118
119	if cache := nodeCache.Load(); cache != nil {	×
120	cache.Resize(int(size))	×
121	}	×
122	}
123
124	// DisableNodeCache disables the node cache and purges all cached nodes.
125	// It does nothing if the cache is already disabled.
126	// It is safe to call this function from multiple goroutines.
127	func DisableNodeCache() {	×
128	if cache := nodeCache.Swap(nil); cache != nil {	×
129	cache.Purge()	×
130	}	×
131	}
132
133	type nodeCacheKey struct {
134	hash.Hash64
135	buf [8]byte
136	}
137
138	var nodeCacheKeyPool = sync.Pool{
139	New: func() any { return &nodeCacheKey{fnv.New64a(), [8]byte{}} },	76✔
140	}
141
142	func newNodeCacheKey(key string, pos uint, len uint, input []byte, ns ...Node) nodeCacheKey {	276✔
143	ck := nodeCacheKeyPool.Get().(*nodeCacheKey)	276✔
144	ck.writeBase(key, pos, len, input)	276✔
145	ck.writeChildKeys(0, ns...)	276✔
146	return ck	276✔
147	}	276✔
148
149	func (ck *nodeCacheKey) free() {	276✔
150	if ck == nil {	276✔
151	return	×
152	}	×
153
154	ck.Reset()	276✔
155	nodeCacheKeyPool.Put(ck)	276✔
156	}
157
158	func (ck *nodeCacheKey) writeBase(key string, pos uint, len uint, input []byte) {	276✔
159	ck.Write(unsafeStringToBytes(key))	276✔
160		276✔
161	binary.BigEndian.PutUint64(ck.buf[:], uint64(pos))	276✔
162	ck.Write(ck.buf[:])	276✔
163		276✔
164	binary.BigEndian.PutUint64(ck.buf[:], uint64(len))	276✔
165	ck.Write(ck.buf[:])	276✔
166		276✔
167	ck.Write(input)	276✔
168	}	276✔
169
170	func (ck nodeCacheKey) writeChildKeys(depth uint, ns ...Node) {	705✔
171	for _, n := range ns {	1,014✔
172	binary.BigEndian.PutUint64(ck.buf[:], uint64(depth))	309✔
173	ck.Write(ck.buf[:])	309✔
174	ck.Write(unsafeStringToBytes(n.Key))	309✔
175	ck.writeChildKeys(depth+1, n.Children...)	309✔
176	}	309✔
177	}
178
179	func (ck *nodeCacheKey) hash() uint64 { return ck.Sum64() }	×
180
181	// unsafeStringToBytes converts string to []byte without allocation
182	// WARNING: The returned byte slice must not be modified
183	func unsafeStringToBytes(s string) []byte {	585✔
184	return ([]byte)(unsafe.Pointer(&struct {	585✔
185	string	585✔
186	int	585✔
187	}{s, len(s)}))	585✔
188	}	585✔
189
190	func loadNode(k nodeCacheKey) (Node, bool) {	×
191	cache := nodeCache.Load()	×
192	if cache == nil {	×
193	return nil, false	×
194	}	×
195
196	n, ok := cache.Get(k.hash())	×
197	if !ok {	×
198	return nil, false	×
199	}	×
200	return n, true	×
201	}
202
203	func storeNode(k nodeCacheKey, n Node) {	×
204	cache := nodeCache.Load()	×
205	if cache == nil {	×
206	return	×
207	}	×
208
209	cache.Add(k.hash(), n)	×
210	}
211
212	func loadOrStoreNode(k nodeCacheKey, newNode func() Node) *Node {	276✔
213	defer k.free()	276✔
214		276✔
215	cache := nodeCache.Load()	276✔
216	if cache == nil {	552✔
217	return newNode()	276✔
218	}	276✔
219
220	if n, ok := loadNode(k); ok {	×
221	return n	×
222	}	×
223
224	n := newNode()	×
225	storeNode(k, n)	×
226	return n	×
227	}
228
229	// Nodes represents a list of nodes.
230	type Nodes []*Node
231
232	// Contains returns whether the subtree contains the given key.
233	func (ns Nodes) Contains(key string) bool {	×
234	for _, n := range ns {	×
235	if n.Key == key \|\| n.Children.Contains(key) {	×
236	return true	×
237	}	×
238	}
239	return false	×
240	}
241
242	// Get recursively searches a node with the given key.
243	func (ns Nodes) Get(key string) (*Node, bool) {	6✔
244	for _, n := range ns {	11✔
245	if n.Key == key {	6✔
246	return n, true	1✔
247	}	1✔
248	if n, ok := n.Children.Get(key); ok {	4✔
249	return n, true	×
250	}	×
251	}
252	return nil, false	5✔
253	}
254
255	// GetAll recursively searches all nodes with the given key.
256	func (ns Nodes) GetAll(key string) Nodes {	×
257	var nodes Nodes	×
258	for _, n := range ns {	×
259	if n.Key == key {	×
260	nodes = append(nodes, n)	×
261	}	×
262	nodes = append(nodes, n.Children.GetAll(key)...)	×
263	}
264	return nodes	×
265	}
266
267	// Best returns a node with the longest value or nil if the list is empty.
268	func (ns Nodes) Best() *Node {	81✔
269	if len(ns) == 0 {	81✔
270	return nil	×
271	}	×
272
273	best := ns[0]	81✔
274	for _, n := range ns[1:] {	105✔
275	if n.Len() > best.Len() {	25✔
276	best = n	1✔
277	}	1✔
278	}
279	return best	81✔
280	}
281
282	// Compare compares two best nodes.
283	// The result will be 0 if a == b, -1 if a < b, and +1 if a > b where a - self best node, b - other best node.
284	func (ns Nodes) Compare(other Nodes) int {	35✔
285	return ns.Best().Compare(other.Best())	35✔
286	}	35✔
287
288	func (ns Nodes) Append(n ...Node) {	411✔
289	ns = append(ns, n...)	411✔
290	}	411✔
291
292	// NodesCap is a initial capacity of a new nodes list.
293	var NodesCap = 100
294
295	var nodesPool = &sync.Pool{
296	New: func() any {	207✔
297	ns := make(Nodes, 0, NodesCap)	207✔
298	return &ns	207✔
299	},	207✔
300	}
301
302	// NewNodes returns a new nodes list from the pool.
303	func NewNodes() Nodes {	385✔
304	ns := nodesPool.Get().(*Nodes)	385✔
305	return *ns	385✔
306	}	385✔
307
308	// Clear clears the nodes list.
309	func (ns *Nodes) Clear() {	562✔
310	if ns == nil {	562✔
311	return	×
312	}	×
313
314	clear(*ns)	562✔
315	ns = (ns)[:0]	562✔
316	}
317
318	// Free returns the nodes list to the pool.
319	func (ns *Nodes) Free() {	247✔
320	ns.Clear()	247✔
321		247✔
322	if ns == nil \|\| cap(ns) == 0 \|\| cap(ns) > 10*NodesCap {	247✔
323	return	×
324	}	×
325
326	nodesPool.Put(ns)	247✔
327	}

ghettovoice / abnf / 18745049026

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous