Debian Codegraph @

hugolib/doctree/nodeshifttree.go

raw
1 // Copyright 2025 The Hugo Authors. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 package doctree
15
16 import (
17 "context"
18 "fmt"
19 "path"
20 "sync"
21
22 radix "github.com/gohugoio/go-radix"
23 "github.com/gohugoio/hugo/common/hstrings"
24 "github.com/gohugoio/hugo/hugolib/sitesmatrix"
25 "github.com/gohugoio/hugo/resources/resource"
26 )
27
28 type (
29 Config[T any] struct {
30 // Shifter handles tree transformations.
31 Shifter Shifter[T]
32 TransformerRaw Transformer[T]
33 }
34
35 // Shifter handles tree transformations.
36 Shifter[T any] interface {
37 // ForEeachInDimension will call the given function for each value in the given dimension d.
38 // This is typicall used to e.g. walk all language translations of a given node.
39 // If the function returns false, the walk will stop.
40 ForEeachInDimension(n T, vec sitesmatrix.Vector, d int, f func(T) bool)
41
42 // ForEeachInAllDimensions will call the given function for each value in all dimensions.
43 // If the function returns false, the walk will stop.
44 ForEeachInAllDimensions(n T, f func(T) bool)
45
46 // Insert inserts new into the tree into the dimension it provides.
47 // It may replace old.
48 // It returns the updated and existing T
49 // and a bool indicating if an existing record is updated.
50 Insert(old, new T) (T, T, bool)
51
52 // Delete deletes T from the given dimension and returns the deleted T and whether the dimension was deleted and if it's empty after the delete.
53 Delete(v T, dimension sitesmatrix.Vector) (T, bool, bool)
54
55 // DeleteFunc deletes nodes in v from the tree where the given function returns true.
56 // It returns true if it's empty after the delete.
57 DeleteFunc(v T, f func(n T) bool) bool
58
59 // Shift shifts v into the given dimension,
60 // if fallback is true, it will fall back a fallback match if found.
61 // It returns the shifted T and a bool indicating if the shift was successful.
62 Shift(v T, dimension sitesmatrix.Vector, fallback bool) (T, bool)
63 }
64
65 Transformer[T any] interface {
66 // Append appends vs to t and returns the updated or replaced T and a bool indicating if T was replaced.
67 // Note that t may be the zero value and should be ignored.
68 Append(t T, ts ...T) (T, bool)
69 }
70 )
71
72 // NodeShiftTree is the root of a tree that can be shaped using the Shape method.
73 // Note that multiplied shapes of the same tree is meant to be used concurrently,
74 // so use the applicable locking when needed.
75 type NodeShiftTree[T any] struct {
76 tree *radix.Tree[T]
77
78 // [language, version, role].
79 siteVector sitesmatrix.Vector
80 shifter Shifter[T]
81 transformerRaw Transformer[T]
82
83 mu *sync.RWMutex
84 }
85
86 func New[T any](cfg Config[T]) *NodeShiftTree[T] {
87 if cfg.Shifter == nil {
88 panic("Shifter is required")
89 }
90
91 return &NodeShiftTree[T]{
92 mu: &sync.RWMutex{},
93
94 shifter: cfg.Shifter,
95 transformerRaw: cfg.TransformerRaw,
96 tree: radix.New[T](),
97 }
98 }
99
100 // SiteVector returns the site vector of the current dimension.
101 func (r *NodeShiftTree[T]) SiteVector() sitesmatrix.Vector {
102 return r.siteVector
103 }
104
105 // Delete deletes the node at the given key in the current dimension.
106 func (r *NodeShiftTree[T]) Delete(key string) (T, bool) {
107 return r.delete(key)
108 }
109
110 // DeleteFuncRaw deletes nodes in the tree at the given key where the given function returns true.
111 // It will delete nodes in all dimensions.
112 func (r *NodeShiftTree[T]) DeleteFuncRaw(key string, f func(T) bool) (T, int) {
113 var count int
114 var lastDeleted T
115
116 v, ok := r.tree.Get(key)
117 if !ok {
118 return lastDeleted, count
119 }
120
121 isEmpty := r.shifter.DeleteFunc(v, func(n T) bool {
122 if f(n) {
123 count++
124 lastDeleted = n
125 return true
126 }
127 return false
128 })
129
130 if isEmpty {
131 r.tree.Delete(key)
132 }
133
134 return lastDeleted, count
135 }
136
137 // DeleteRaw deletes the node at the given key without any shifting or transformation.
138 func (r *NodeShiftTree[T]) DeleteRaw(key string) {
139 r.tree.Delete(key)
140 }
141
142 // DeletePrefix deletes all nodes with the given prefix in the current dimension.
143 func (r *NodeShiftTree[T]) DeletePrefix(prefix string) int {
144 count := 0
145 var keys []string
146 var zero T
147 var walkFn radix.WalkFn[T] = func(key string, value T) (radix.WalkFlag, T, error) {
148 keys = append(keys, key)
149 return radix.WalkContinue, zero, nil
150 }
151 r.tree.WalkPrefix(prefix, walkFn)
152 for _, key := range keys {
153 if _, ok := r.delete(key); ok {
154 count++
155 }
156 }
157 return count
158 }
159
160 func (r *NodeShiftTree[T]) delete(key string) (T, bool) {
161 var wasDeleted bool
162 var deleted T
163 if v, ok := r.tree.Get(key); ok {
164 var isEmpty bool
165 deleted, wasDeleted, isEmpty = r.shifter.Delete(v, r.siteVector)
166 if isEmpty {
167 r.tree.Delete(key)
168 }
169 }
170 return deleted, wasDeleted
171 }
172
173 func (t *NodeShiftTree[T]) DeletePrefixRaw(prefix string) int {
174 count := 0
175 var zero T
176 var walkFn radix.WalkFn[T] = func(key string, value T) (radix.WalkFlag, T, error) {
177 if v, ok := t.tree.Delete(key); ok {
178 resource.MarkStale(v)
179 count++
180 }
181 return radix.WalkContinue, zero, nil
182 }
183 t.tree.WalkPrefix(prefix, walkFn)
184
185 return count
186 }
187
188 // Insert inserts v into the tree at the given key and the
189 // dimension defined by the value.
190 // It returns the updated and existing T and a bool indicating if an existing record is updated.
191 func (r *NodeShiftTree[T]) Insert(s string, v T) (T, T, bool) {
192 s = mustValidateKey(cleanKey(s))
193 var (
194 updated bool
195 existing T
196 )
197 if vv, ok := r.tree.Get(s); ok {
198 v, existing, updated = r.shifter.Insert(vv, v)
199 }
200 r.insert(s, v)
201 return v, existing, updated
202 }
203
204 func (r *NodeShiftTree[T]) insert(s string, v T) (T, bool) {
205 n, updated := r.tree.Insert(s, v)
206 return n, updated
207 }
208
209 // InsertRaw inserts v into the tree at the given key without any shifting or transformation.
210 func (r *NodeShiftTree[T]) InsertRaw(s string, v T) (T, bool) {
211 return r.insert(s, v)
212 }
213
214 func (r *NodeShiftTree[T]) InsertRawWithLock(s string, v T) (T, bool) {
215 r.mu.Lock()
216 defer r.mu.Unlock()
217 return r.insert(s, v)
218 }
219
220 // It returns the updated and existing T and a bool indicating if an existing record is updated.
221 func (r *NodeShiftTree[T]) InsertWithLock(s string, v T) (T, T, bool) {
222 r.mu.Lock()
223 defer r.mu.Unlock()
224 return r.Insert(s, v)
225 }
226
227 func (t *NodeShiftTree[T]) Len() int {
228 return t.tree.Len()
229 }
230
231 func (t *NodeShiftTree[T]) CanLock() bool {
232 ok := t.mu.TryLock()
233 if ok {
234 t.mu.Unlock()
235 }
236 return ok
237 }
238
239 // Lock locks the data store for read or read/write access.
240 // Note that NodeShiftTree is not thread-safe outside of this transaction construct.
241 func (t *NodeShiftTree[T]) Lock(writable bool) {
242 if writable {
243 t.mu.Lock()
244 } else {
245 t.mu.RLock()
246 }
247 }
248
249 // Unlock unlocks the data store.
250 func (t *NodeShiftTree[T]) Unlock(writable bool) {
251 if writable {
252 t.mu.Unlock()
253 } else {
254 t.mu.RUnlock()
255 }
256 }
257
258 // LongestPrefix finds the longest prefix of s that exists in the tree that also matches the predicate (if set).
259 // Set exact to true to only match exact in the current dimension (e.g. language).
260 func (r *NodeShiftTree[T]) LongestPrefix(s string, fallback bool, predicate func(v T) bool) (string, T) {
261 for {
262 longestPrefix, v, found := r.tree.LongestPrefix(s)
263
264 if found {
265 if v, ok := r.shift(v, fallback); ok && (predicate == nil || predicate(v)) {
266 return longestPrefix, v
267 }
268 }
269
270 if s == "" || s == "/" {
271 var t T
272 return "", t
273 }
274
275 // Walk up to find a node in the correct dimension.
276 s = path.Dir(s)
277
278 }
279 }
280
281 // LongestPrefiValueRaw returns the longest prefix and value considering all dimensions
282 func (r *NodeShiftTree[T]) LongestPrefiValueRaw(s string) (string, T) {
283 s, v, found := r.tree.LongestPrefix(s)
284 if !found {
285 var t T
286 return s, t
287 }
288 return s, v
289 }
290
291 // LongestPrefixRaw returns the longest prefix considering all dimensions.
292 func (r *NodeShiftTree[T]) LongestPrefixRaw(s string) (string, bool) {
293 s, _, found := r.tree.LongestPrefix(s)
294 return s, found
295 }
296
297 // GetRaw returns the raw value at the given key without any shifting or transformation.
298 func (r *NodeShiftTree[T]) GetRaw(s string) (T, bool) {
299 v, ok := r.tree.Get(s)
300 if !ok {
301 var t T
302 return t, false
303 }
304 return v, true
305 }
306
307 // AppendRaw appends ts to the node at the given key without any shifting or transformation.
308 func (r *NodeShiftTree[T]) AppendRaw(s string, ts ...T) (T, bool) {
309 if r.transformerRaw == nil {
310 panic("transformerRaw is required")
311 }
312 n, found := r.GetRaw(s)
313 n2, replaced := r.transformerRaw.Append(n, ts...)
314 if replaced || !found {
315 r.insert(s, n2)
316 }
317 return n2, replaced || !found
318 }
319
320 // WalkPrefixRaw walks all nodes with the given prefix in the tree without any shifting or transformation.
321 func (r *NodeShiftTree[T]) WalkPrefixRaw(prefix string, fn radix.WalkFn[T]) error {
322 return r.tree.WalkPrefix(prefix, fn)
323 }
324
325 // Shape returns a new NodeShiftTree shaped to the given dimension.
326 func (t *NodeShiftTree[T]) Shape(v sitesmatrix.Vector) *NodeShiftTree[T] {
327 x := t.clone()
328 x.siteVector = v
329 return x
330 }
331
332 func (t *NodeShiftTree[T]) String() string {
333 return fmt.Sprintf("Root{%v}", t.siteVector)
334 }
335
336 func (r *NodeShiftTree[T]) Get(s string) T {
337 t, _ := r.get(s)
338 return t
339 }
340
341 // GetWithFallback is like Get but uses the fallback/complement mechanism
342 // when finding a node for the current site vector.
343 func (r *NodeShiftTree[T]) GetWithFallback(s string) T {
344 s = cleanKey(s)
345 v, ok := r.tree.Get(s)
346 if !ok {
347 var t T
348 return t
349 }
350 if v, ok := r.shift(v, true); ok {
351 return v
352 }
353 var t T
354 return t
355 }
356
357 func (r *NodeShiftTree[T]) ForEeachInDimension(s string, dims sitesmatrix.Vector, d int, f func(T) bool) {
358 s = cleanKey(s)
359 v, ok := r.tree.Get(s)
360 if !ok {
361 return
362 }
363 r.shifter.ForEeachInDimension(v, dims, d, f)
364 }
365
366 func (r *NodeShiftTree[T]) ForEeachInAllDimensions(s string, f func(T) bool) {
367 s = cleanKey(s)
368 v, ok := r.tree.Get(s)
369 if !ok {
370 return
371 }
372 r.shifter.ForEeachInAllDimensions(v, f)
373 }
374
375 type WalkFunc[T any] func(string, T) (bool, error)
376
377 //go:generate stringer -type=NodeTransformState
378 type NodeTransformState int
379
380 const (
381 NodeTransformStateNone NodeTransformState = iota
382 NodeTransformStateUpdated // Node is updated in place.
383 NodeTransformStateReplaced // Node is replaced and needs to be re-inserted into the tree.
384 NodeTransformStateDeleted // Node is deleted and should be removed from the tree.
385 NodeTransformStateSkip // Skip this node, but continue the walk.
386 NodeTransformStateTerminate // Terminate the walk.
387 )
388
389 type NodeShiftTreeWalker[T any] struct {
390 // The tree to walk.
391 Tree *NodeShiftTree[T]
392
393 // Transform will be called for each node in the main tree.
394 // v2 will replace v1 in the tree if state returned is NodeTransformStateReplaced.
395 Transform func(s string, v1 T) (v2 T, state NodeTransformState, err error)
396
397 // Handle will be called for each node in the main tree.
398 Handle func(s string, v T) (f radix.WalkFlag, err error)
399
400 // Optional prefix filter.
401 Prefix string
402
403 // IncludeFilter is an optional filter that can be used to filter nodes.
404 // If it returns false, the node will be skipped.
405 // Note that v is the shifted value from the tree.
406 IncludeFilter func(s string, v T) bool
407
408 // IncludeRawFilter is an optional filter that can be used to filter nodes.
409 // If it returns false, the node will be skipped.
410 // Note that v is the raw value from the tree.
411 IncludeRawFilter func(s string, v T) bool
412
413 // Enable read or write locking if needed.
414 LockType LockType
415
416 // When set, no dimension shifting will be performed.
417 NoShift bool
418
419 // When set, will try to fall back to alternative match,
420 // typically a shared resource common for all languages.
421 Fallback bool
422
423 // Used in development only.
424 Debug bool
425
426 // Optional context.
427 // Note that this is copied to the nested walkers using Extend.
428 // This means that walkers can pass data (down) and events (up) to
429 // the related walkers.
430 WalkContext *WalkContext[T]
431
432 // Local state.
433 // This is scoped to the current walker and not copied to the nested walkers.
434 skipPrefixes []string
435 }
436
437 // Extend returns a new NodeShiftTreeWalker with the same configuration
438 // and the same WalkContext as the original.
439 // Any local state is reset.
440 func (r *NodeShiftTreeWalker[T]) Extend() *NodeShiftTreeWalker[T] {
441 return &NodeShiftTreeWalker[T]{
442 Tree: r.Tree,
443 Transform: r.Transform,
444 Handle: r.Handle,
445 Prefix: r.Prefix,
446 IncludeFilter: r.IncludeFilter,
447 IncludeRawFilter: r.IncludeRawFilter,
448 LockType: r.LockType,
449 NoShift: r.NoShift,
450 Fallback: r.Fallback,
451 Debug: r.Debug,
452 WalkContext: r.WalkContext,
453 }
454 }
455
456 // WithPrefix returns a new NodeShiftTreeWalker with the given prefix.
457 func (r *NodeShiftTreeWalker[T]) WithPrefix(prefix string) *NodeShiftTreeWalker[T] {
458 r2 := r.Extend()
459 r2.Prefix = prefix
460 return r2
461 }
462
463 // SkipPrefix adds a prefix to be skipped in the walk.
464 func (r *NodeShiftTreeWalker[T]) SkipPrefix(prefix ...string) {
465 r.skipPrefixes = append(r.skipPrefixes, prefix...)
466 }
467
468 func (r *NodeShiftTreeWalker[T]) ShouldSkipKey(s string) bool {
469 return hstrings.HasAnyPrefix(s, r.skipPrefixes...)
470 }
471
472 // ShouldSkip returns whether the given value should be skipped in the walk.
473 func (r *NodeShiftTreeWalker[T]) ShouldSkipValue(s string, v T) bool {
474 if r.IncludeRawFilter != nil {
475 if !r.IncludeRawFilter(s, v) {
476 return true
477 }
478 }
479 return false
480 }
481
482 type walkHandler[T any] struct {
483 r *NodeShiftTreeWalker[T]
484 handle func(s string, v T) (radix.WalkFlag, T, error)
485 }
486
487 func (h *walkHandler[T]) Check(s string) (radix.WalkFlag, error) {
488 if h.r == nil {
489 return radix.WalkContinue, nil
490 }
491 if h.r.ShouldSkipKey(s) {
492 return radix.WalkSkip, nil
493 }
494 return radix.WalkContinue, nil
495 }
496
497 func (h *walkHandler[T]) Handle(s string, v T) (radix.WalkFlag, T, error) {
498 if h.handle == nil {
499 return radix.WalkContinue, v, nil
500 }
501 return h.handle(s, v)
502 }
503
504 func (r *NodeShiftTreeWalker[T]) lock() {
505 switch r.LockType {
506 case LockTypeRead:
507 r.Tree.mu.RLock()
508 case LockTypeWrite:
509 r.Tree.mu.Lock()
510 default:
511 // No lock
512 }
513 }
514
515 func (r *NodeShiftTreeWalker[T]) unlock() {
516 switch r.LockType {
517 case LockTypeRead:
518 r.Tree.mu.RUnlock()
519 case LockTypeWrite:
520 r.Tree.mu.Unlock()
521 default:
522 // No lock
523 }
524 }
525
526 func (r *NodeShiftTreeWalker[T]) Walk(ctx context.Context) error {
527 var deletes []string
528
529 return func() error {
530 r.lock()
531 defer r.unlock()
532
533 r.resetLocalState()
534
535 main := r.Tree
536
537 var handleV radix.WalkFn[T] = func(s string, v T) (radix.WalkFlag, T, error) {
538 var zero T
539 // Context cancellation check.
540 if ctx != nil && ctx.Err() != nil {
541 return radix.WalkStop, zero, ctx.Err()
542 }
543 if r.ShouldSkipValue(s, v) {
544 return radix.WalkContinue, zero, nil
545 }
546 var t T
547 if r.NoShift {
548 t = v
549 } else {
550 var ok bool
551 t, ok = r.toT(r.Tree, v)
552 if !ok {
553 return radix.WalkContinue, zero, nil
554 }
555 }
556 var (
557 ns NodeTransformState
558 t2 T
559 )
560 if r.IncludeFilter != nil && !r.IncludeFilter(s, t) {
561 return radix.WalkContinue, zero, nil
562 }
563 if r.Transform != nil {
564 if !r.NoShift {
565 panic("Transform must be performed with NoShift=true")
566 }
567 var err error
568 ns, err = func() (ns NodeTransformState, err error) {
569 t2, ns, err = r.Transform(s, t)
570 if ns >= NodeTransformStateSkip || err != nil {
571 return
572 }
573 switch ns {
574 case NodeTransformStateReplaced:
575 case NodeTransformStateDeleted:
576 // Delay delete until after the walk.
577 deletes = append(deletes, s)
578 ns = NodeTransformStateSkip
579 }
580 return
581 }()
582
583 if ns == NodeTransformStateTerminate || err != nil {
584 return radix.WalkStop, zero, err
585 }
586
587 if ns == NodeTransformStateSkip {
588 return radix.WalkContinue, zero, nil
589 }
590
591 }
592
593 if r.Handle != nil {
594 f, err := r.Handle(s, t)
595 if f.ShouldSet() {
596 panic("Handle cannot replace nodes in the tree, use Transform for that")
597 }
598 if f.ShouldStop() || err != nil {
599 return f, zero, err
600 }
601 }
602 if ns == NodeTransformStateTerminate {
603 return radix.WalkStop, zero, nil
604 }
605 if ns == NodeTransformStateReplaced {
606 return radix.WalkSet | radix.WalkContinue, t2, nil
607 }
608 return radix.WalkContinue, zero, nil
609 }
610
611 handle := &walkHandler[T]{
612 r: r,
613 handle: handleV,
614 }
615
616 if r.Prefix != "" {
617 if err := main.tree.WalkPrefix(r.Prefix, handle); err != nil {
618 return err
619 }
620 } else {
621 if err := main.tree.Walk(handle); err != nil {
622 return err
623 }
624 }
625
626 // This is currently only performed with no shift.
627 for _, s := range deletes {
628 main.tree.Delete(s)
629 }
630
631 return nil
632 }()
633 }
634
635 func (r *NodeShiftTreeWalker[T]) resetLocalState() {
636 r.skipPrefixes = nil
637 }
638
639 func (r *NodeShiftTreeWalker[T]) toT(tree *NodeShiftTree[T], v T) (T, bool) {
640 return tree.shift(v, r.Fallback)
641 }
642
643 func (r *NodeShiftTree[T]) Has(s string) bool {
644 _, ok := r.GetRaw(s)
645 return ok
646 }
647
648 func (t NodeShiftTree[T]) clone() *NodeShiftTree[T] {
649 return &t
650 }
651
652 func (r *NodeShiftTree[T]) shift(t T, fallback bool) (T, bool) {
653 return r.shifter.Shift(t, r.siteVector, fallback)
654 }
655
656 func (r *NodeShiftTree[T]) get(s string) (T, bool) {
657 s = cleanKey(s)
658 v, ok := r.tree.Get(s)
659
660 if !ok {
661 var t T
662 return t, false
663 }
664 if v, ok := r.shift(v, false); ok {
665 return v, true
666 }
667
668 var t T
669 return t, false
670 }