18802266297

Committed 25 Oct 2025 11:09AM UTC coverage: 70.951%. Remained the same

Build # 18802266297

Build Type

push

github

Committed by

ghettovoice

Commit Message

Update generate command usages

Run Details

1612 of 2272 relevant lines covered (70.95%)

54.71 hits per line

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

63.56

/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 is the identifier of the operator that created the node.
        Key string
        // Pos is the position of the node value in the input.
        Pos uint
        // Value is the value matched by the operator.
        Value []byte
        // Children is a collection of child nodes.
        Children Nodes
}

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

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

// IsEmpty reports whether the node has an empty value.
func (n *Node) IsEmpty() bool { return n == nil || len(n.Value) == 0 }

// Contains reports 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.AllByKey(key)...)
        return ns
}

// Compare compares node values via [bytes.Compare].
// The result is 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]]
        cacheHit,
        cacheMiss atomic.Uint64
)

// 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()
                cacheHit.Store(0)
                cacheMiss.Store(0)
        }
}

// NodeCacheStats reports cache hit and miss counts along with the number of cached nodes.
func NodeCacheStats() struct{ hit, miss, size uint64 } {
        var size uint64
        if cache := nodeCache.Load(); cache != nil {
                size = uint64(cache.Len())
        }
        return struct{ hit, miss, size uint64 }{cacheHit.Load(), cacheMiss.Load(), size}
}

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, length uint, input []byte) {
        ck.Write(unsafeStringToBytes(key))

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

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

        if len(input) == 0 || length == 0 {
                return
        }

        start := int(pos)
        if start >= len(input) {
                return
        }
        end := min(start+int(length), len(input))
        ck.Write(input[start:end])
}

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 {
                cacheMiss.Add(1)
                return nil, false
        }
        cacheHit.Add(1)
        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

// Len returns the number of nodes in the list.
func (ns *Nodes) Len() int {
        if ns == nil {
                return 0
        }
        return len(*ns)
}

// Contains reports whether the subtree contains the given key.
func (ns *Nodes) Contains(key string) bool {
        if ns == nil {
                return false
        }

        for _, n := range *ns {
                if n.Key == key || n.Children.Contains(key) {
                        return true
                }
        }
        return false
}

// Get recursively searches for the first node with the given key.
func (ns *Nodes) Get(key string) (*Node, bool) {
        if ns == nil {
                return nil, false
        }

        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
}

// All returns all nodes in the list.
func (ns *Nodes) All() Nodes {
        if ns == nil {
                return nil
        }
        return *ns
}

// AllByKey recursively searches all nodes with the given key.
func (ns *Nodes) AllByKey(key string) Nodes {
        if ns == nil {
                return nil
        }

        var nodes Nodes
        for _, n := range *ns {
                if n.Key == key {
                        nodes = append(nodes, n)
                }
                nodes = append(nodes, n.Children.AllByKey(key)...)
        }
        return nodes
}

// Best returns a node with the longest value or nil if the list is empty.
func (ns *Nodes) Best() *Node {
        if ns == nil || 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 is 0 if a == b, -1 if a < b, and +1 if a > b where a is the receiver best node and b is the other best node.
func (ns *Nodes) Compare(other *Nodes) int {
        if ns == nil || other == nil {
                return 0
        }
        return ns.Best().Compare(other.Best())
}

// Append adds nodes to the list.
func (ns *Nodes) Append(n ...*Node) {
        *ns = append(*ns, n...)
}

// NodesCap is an initial capacity for a new nodes list.
var NodesCap = 10

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 {
        return nodesPool.Get().(*Nodes)
}

// 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)
}

type nodesSorter Nodes

func (ns *nodesSorter) Len() int { return len(*ns) }

func (ns *nodesSorter) Less(i, j int) bool {
        return len((*ns)[i].Value) > len((*ns)[j].Value) ||
                len((*ns)[i].Children) > len((*ns)[j].Children) ||
                (*ns)[i].Pos < (*ns)[j].Pos ||
                (*ns)[i].Key < (*ns)[j].Key
}

func (ns *nodesSorter) Swap(i, j int) { (*ns)[i], (*ns)[j] = (*ns)[j], (*ns)[i] }

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 is the identifier of the operator that created the node.
18	Key string
19	// Pos is the position of the node value in the input.
20	Pos uint
21	// Value is the value matched by the operator.
22	Value []byte
23	// Children is a collection of child nodes.
24	Children Nodes
25	}
26
27	// String returns the node value as a string.
28	func (n *Node) String() string {	3✔
29	if n == nil {	3✔
30	return ""	×
31	}	×
32	return string(n.Value)	3✔
33	}
34
35	// Len returns the length of the node value.
36	func (n *Node) Len() int {	48✔
37	if n == nil {	48✔
38	return 0	×
39	}	×
40	return len(n.Value)	48✔
41	}
42
43	// IsEmpty reports whether the node has an empty value.
44	func (n *Node) IsEmpty() bool { return n == nil \|\| len(n.Value) == 0 }	×
45
46	// Contains reports whether the subtree contains the given key.
47	func (n *Node) Contains(key string) bool {	×
48	if n == nil {	×
49	return false	×
50	}	×
51	_, ok := n.GetNode(key)	×
52	return ok	×
53	}
54
55	// GetNode recursively searches a node with the given key starting from itself.
56	// Returns found node or nil if not found.
57	func (n Node) GetNode(key string) (Node, bool) {	3✔
58	if n == nil {	3✔
59	return nil, false	×
60	}	×
61	if n.Key == key {	4✔
62	return n, true	1✔
63	}	1✔
64	return n.Children.Get(key)	2✔
65	}
66
67	// GetNodes recursively searches all nodes with the given key starting from itself.
68	func (n *Node) GetNodes(key string) Nodes {	×
69	if n == nil {	×
70	return nil	×
71	}	×
72
73	var ns Nodes	×
74	if n.Key == key {	×
75	ns = append(ns, n)	×
76	}	×
77	ns = append(ns, n.Children.AllByKey(key)...)	×
78	return ns	×
79	}
80
81	// Compare compares node values via [bytes.Compare].
82	// The result is 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
83	func (n Node) Compare(other Node) int {	35✔
84	if n == other {	35✔
85	return 0	×
86	} else if n == nil {	35✔
87	return -1	×
88	} else if other == nil {	35✔
89	return 1	×
90	}	×
91	return bytes.Compare(n.Value, other.Value)	35✔
92	}
93
94	var (
95	nodeCache atomic.Pointer[lru.Cache[uint64, *Node]]
96	cacheHit,
97	cacheMiss atomic.Uint64
98	)
99
100	// EnableNodeCache initializes the node cache.
101	// If size is 0, it will be set to 1024.
102	// By default, the cache is disabled.
103	// It does nothing if the cache is already enabled.
104	// Call this function before using any [Operator], usually in the [init].
105	func EnableNodeCache(size uint) {	1✔
106	if nodeCache.Load() != nil {	1✔
107	return	×
108	}	×
109
110	if size == 0 {	2✔
111	size = 1024	1✔
112	}	1✔
113
114	cache, _ := lru.New[uint64, *Node](int(size))	1✔
115	nodeCache.Store(cache)	1✔
116	}
117
118	// ResizeNodeCache resizes the node cache.
119	// If size is 0, it will be set to 1024.
120	// It does nothing if the cache is disabled.
121	// It is safe to call this function from multiple goroutines.
122	func ResizeNodeCache(size uint) {	×
123	if size == 0 {	×
124	size = 1024	×
125	}	×
126
127	if cache := nodeCache.Load(); cache != nil {	×
128	cache.Resize(int(size))	×
129	}	×
130	}
131
132	// DisableNodeCache disables the node cache and purges all cached nodes.
133	// It does nothing if the cache is already disabled.
134	// It is safe to call this function from multiple goroutines.
135	func DisableNodeCache() {	1✔
136	if cache := nodeCache.Swap(nil); cache != nil {	2✔
137	cache.Purge()	1✔
138	cacheHit.Store(0)	1✔
139	cacheMiss.Store(0)	1✔
140	}	1✔
141	}
142
143	// NodeCacheStats reports cache hit and miss counts along with the number of cached nodes.
144	func NodeCacheStats() struct{ hit, miss, size uint64 } {	×
145	var size uint64	×
146	if cache := nodeCache.Load(); cache != nil {	×
147	size = uint64(cache.Len())	×
148	}	×
149	return struct{ hit, miss, size uint64 }{cacheHit.Load(), cacheMiss.Load(), size}	×
150	}
151
152	type nodeCacheKey struct {
153	hash.Hash64
154	buf [8]byte
155	}
156
157	var nodeCacheKeyPool = sync.Pool{
158	New: func() any { return &nodeCacheKey{fnv.New64a(), [8]byte{}} },	65✔
159	}
160
161	func newNodeCacheKey(key string, pos uint, len uint, input []byte, ns ...Node) nodeCacheKey {	285✔
162	ck := nodeCacheKeyPool.Get().(*nodeCacheKey)	285✔
163	ck.writeBase(key, pos, len, input)	285✔
164	ck.writeChildKeys(0, ns...)	285✔
165	return ck	285✔
166	}	285✔
167
168	func (ck *nodeCacheKey) free() {	285✔
169	if ck == nil {	285✔
170	return	×
171	}	×
172
173	ck.Reset()	285✔
174	nodeCacheKeyPool.Put(ck)	285✔
175	}
176
177	func (ck *nodeCacheKey) writeBase(key string, pos, length uint, input []byte) {	285✔
178	ck.Write(unsafeStringToBytes(key))	285✔
179		285✔
180	binary.BigEndian.PutUint64(ck.buf[:], uint64(pos))	285✔
181	ck.Write(ck.buf[:])	285✔
182		285✔
183	binary.BigEndian.PutUint64(ck.buf[:], uint64(length))	285✔
184	ck.Write(ck.buf[:])	285✔
185		285✔
186	if len(input) == 0 \|\| length == 0 {	359✔
187	return	74✔
188	}	74✔
189
190	start := int(pos)	211✔
191	if start >= len(input) {	211✔
192	return	×
193	}	×
194	end := min(start+int(length), len(input))	211✔
195	ck.Write(input[start:end])	211✔
196	}
197
198	func (ck nodeCacheKey) writeChildKeys(depth uint, ns ...Node) {	727✔
199	for _, n := range ns {	1,046✔
200	binary.BigEndian.PutUint64(ck.buf[:], uint64(depth))	319✔
201	ck.Write(ck.buf[:])	319✔
202	ck.Write(unsafeStringToBytes(n.Key))	319✔
203	ck.writeChildKeys(depth+1, n.Children...)	319✔
204	}	319✔
205	}
206
207	func (ck *nodeCacheKey) hash() uint64 { return ck.Sum64() }	43✔
208
209	// unsafeStringToBytes converts string to []byte without allocation
210	// WARNING: The returned byte slice must not be modified
211	func unsafeStringToBytes(s string) []byte {	604✔
212	return ([]byte)(unsafe.Pointer(&struct {	604✔
213	string	604✔
214	int	604✔
215	}{s, len(s)}))	604✔
216	}	604✔
217
218	func loadNode(k nodeCacheKey) (Node, bool) {	30✔
219	cache := nodeCache.Load()	30✔
220	if cache == nil {	30✔
221	return nil, false	×
222	}	×
223
224	n, ok := cache.Get(k.hash())	30✔
225	if !ok {	43✔
226	cacheMiss.Add(1)	13✔
227	return nil, false	13✔
228	}	13✔
229	cacheHit.Add(1)	17✔
230	return n, true	17✔
231	}
232
233	func storeNode(k nodeCacheKey, n Node) {	13✔
234	cache := nodeCache.Load()	13✔
235	if cache == nil {	13✔
236	return	×
237	}	×
238
239	cache.Add(k.hash(), n)	13✔
240	}
241
242	func loadOrStoreNode(k nodeCacheKey, newNode func() Node) *Node {	285✔
243	defer k.free()	285✔
244		285✔
245	cache := nodeCache.Load()	285✔
246	if cache == nil {	540✔
247	return newNode()	255✔
248	}	255✔
249
250	if n, ok := loadNode(k); ok {	47✔
251	return n	17✔
252	}	17✔
253
254	n := newNode()	13✔
255	storeNode(k, n)	13✔
256	return n	13✔
257	}
258
259	// Nodes represents a list of nodes.
260	type Nodes []*Node
261
262	// Len returns the number of nodes in the list.
263	func (ns *Nodes) Len() int {	225✔
264	if ns == nil {	225✔
265	return 0	×
266	}	×
267	return len(*ns)	225✔
268	}
269
270	// Contains reports whether the subtree contains the given key.
271	func (ns *Nodes) Contains(key string) bool {	×
272	if ns == nil {	×
273	return false	×
274	}	×
275
276	for _, n := range *ns {	×
277	if n.Key == key \|\| n.Children.Contains(key) {	×
278	return true	×
279	}	×
280	}
281	return false	×
282	}
283
284	// Get recursively searches for the first node with the given key.
285	func (ns Nodes) Get(key string) (Node, bool) {	6✔
286	if ns == nil {	6✔
287	return nil, false	×
288	}	×
289
290	for _, n := range *ns {	11✔
291	if n.Key == key {	6✔
292	return n, true	1✔
293	}	1✔
294	if n, ok := n.Children.Get(key); ok {	4✔
295	return n, true	×
296	}	×
297	}
298	return nil, false	5✔
299	}
300
301	// All returns all nodes in the list.
302	func (ns *Nodes) All() Nodes {	357✔
303	if ns == nil {	357✔
304	return nil	×
305	}	×
306	return *ns	357✔
307	}
308
309	// AllByKey recursively searches all nodes with the given key.
310	func (ns *Nodes) AllByKey(key string) Nodes {	×
311	if ns == nil {	×
312	return nil	×
313	}	×
314
315	var nodes Nodes	×
316	for _, n := range *ns {	×
317	if n.Key == key {	×
318	nodes = append(nodes, n)	×
319	}	×
320	nodes = append(nodes, n.Children.AllByKey(key)...)	×
321	}
322	return nodes	×
323	}
324
325	// Best returns a node with the longest value or nil if the list is empty.
326	func (ns Nodes) Best() Node {	81✔
327	if ns == nil \|\| len(*ns) == 0 {	81✔
328	return nil	×
329	}	×
330
331	best := (*ns)[0]	81✔
332	for _, n := range (*ns)[1:] {	105✔
333	if n.Len() > best.Len() {	25✔
334	best = n	1✔
335	}	1✔
336	}
337	return best	81✔
338	}
339
340	// Compare compares two best nodes.
341	// The result is 0 if a == b, -1 if a < b, and +1 if a > b where a is the receiver best node and b is the other best node.
342	func (ns Nodes) Compare(other Nodes) int {	35✔
343	if ns == nil \|\| other == nil {	35✔
344	return 0	×
345	}	×
346	return ns.Best().Compare(other.Best())	35✔
347	}
348
349	// Append adds nodes to the list.
350	func (ns Nodes) Append(n ...Node) {	423✔
351	ns = append(ns, n...)	423✔
352	}	423✔
353
354	// NodesCap is an initial capacity for a new nodes list.
355	var NodesCap = 10
356
357	var nodesPool = &sync.Pool{
358	New: func() any {	71✔
359	ns := make(Nodes, 0, NodesCap)	71✔
360	return &ns	71✔
361	},	71✔
362	}
363
364	// NewNodes returns a new nodes list from the pool.
365	func NewNodes() *Nodes {	262✔
366	return nodesPool.Get().(*Nodes)	262✔
367	}	262✔
368
369	// Clear clears the nodes list.
370	func (ns *Nodes) Clear() {	593✔
371	if ns == nil {	593✔
372	return	×
373	}	×
374
375	clear(*ns)	593✔
376	ns = (ns)[:0]	593✔
377	}
378
379	// Free returns the nodes list to the pool.
380	func (ns *Nodes) Free() {	262✔
381	ns.Clear()	262✔
382		262✔
383	if ns == nil \|\| cap(ns) == 0 \|\| cap(ns) > 10*NodesCap {	262✔
384	return	×
385	}	×
386
387	nodesPool.Put(ns)	262✔
388	}
389
390	type nodesSorter Nodes
391
392	func (ns nodesSorter) Len() int { return len(ns) }	27✔
393
394	func (ns *nodesSorter) Less(i, j int) bool {	65✔
395	return len((ns)[i].Value) > len((ns)[j].Value) \|\|	65✔
396	len((ns)[i].Children) > len((ns)[j].Children) \|\|	65✔
397	(ns)[i].Pos < (ns)[j].Pos \|\|	65✔
398	(ns)[i].Key < (ns)[j].Key	65✔
399	}	65✔
400
401	func (ns nodesSorter) Swap(i, j int) { (ns)[i], (ns)[j] = (ns)[j], (*ns)[i] }	56✔

ghettovoice / abnf / 18802266297

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