18697592777

Committed 21 Oct 2025 09:03PM UTC coverage: 70.422% (+0.9%) from 69.501%

Build # 18697592777

Build Type

Pull #52

github

Committed by

ghettovoice

Commit Message

Improve readability of basic operators

Pull Request Pull Request #52: Optimize

Run Details

397 of 482 new or added lines in 9 files covered. (82.37%)

28 existing lines in 5 files now uncovered.

1519 of 2157 relevant lines covered (70.42%)

55.04 hits per line

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

66.67

/node.go

package abnf

import (
        "bytes"
        "encoding/binary"
        "hash"
        "hash/fnv"
        "sync"
        "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 *lru.Cache[uint64, *Node]

// InitNodeCache initializes the node cache.
// If size is 0, it will be set to 512.
// Call this function before using any [Operator], usually in the [init].
func InitNodeCache(size uint) {
        if size == 0 {
                size = 512
        }
        nodeCache, _ = lru.New[uint64, *Node](int(size))
}

func init() {
        InitNodeCache(512)
}

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) {
        n, ok := nodeCache.Get(k.hash())
        if !ok {
                return nil, false
        }
        return n, true
}

func storeNode(k *nodeCacheKey, n *Node) {
        nodeCache.Add(k.hash(), n)
}

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

        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 nsPool = &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 := nsPool.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
        }

        nsPool.Put(ns)
}

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

ghettovoice / abnf / 18697592777

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