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