| 1 |
// Copyright 2024 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_test |
| 15 |
|
| 16 |
import ( |
| 17 |
"context" |
| 18 |
"fmt" |
| 19 |
"math/rand" |
| 20 |
"path" |
| 21 |
"strings" |
| 22 |
"testing" |
| 23 |
|
| 24 |
qt "github.com/frankban/quicktest" |
| 25 |
radix "github.com/gohugoio/go-radix" |
| 26 |
"github.com/gohugoio/hugo/common/para" |
| 27 |
"github.com/gohugoio/hugo/hugolib/doctree" |
| 28 |
"github.com/gohugoio/hugo/hugolib/sitesmatrix" |
| 29 |
"github.com/google/go-cmp/cmp" |
| 30 |
) |
| 31 |
|
| 32 |
var eq = qt.CmpEquals( |
| 33 |
cmp.Comparer(func(n1, n2 *testValue) bool { |
| 34 |
if n1 == n2 { |
| 35 |
return true |
| 36 |
} |
| 37 |
|
| 38 |
return n1.ID == n2.ID && n1.Lang == n2.Lang |
| 39 |
}), |
| 40 |
) |
| 41 |
|
| 42 |
func TestTree(t *testing.T) { |
| 43 |
c := qt.New(t) |
| 44 |
|
| 45 |
zeroZero := doctree.New( |
| 46 |
doctree.Config[*testValue]{ |
| 47 |
Shifter: &testShifter{}, |
| 48 |
}, |
| 49 |
) |
| 50 |
|
| 51 |
a := &testValue{ID: "/a"} |
| 52 |
zeroZero.Insert("/a", a) |
| 53 |
ab := &testValue{ID: "/a/b"} |
| 54 |
zeroZero.Insert("/a/b", ab) |
| 55 |
|
| 56 |
c.Assert(zeroZero.Get("/a"), eq, &testValue{ID: "/a", Lang: 0}) |
| 57 |
s, v := zeroZero.LongestPrefix("/a/b/c", false, nil) |
| 58 |
c.Assert(v, eq, ab) |
| 59 |
c.Assert(s, eq, "/a/b") |
| 60 |
|
| 61 |
// Change language. |
| 62 |
oneZero := zeroZero.Shape(sitesmatrix.Vector{1, 0, 0}) |
| 63 |
c.Assert(zeroZero.Get("/a"), eq, &testValue{ID: "/a", Lang: 0}) |
| 64 |
c.Assert(oneZero.Get("/a"), eq, &testValue{ID: "/a", Lang: 1}) |
| 65 |
} |
| 66 |
|
| 67 |
func TestTreeData(t *testing.T) { |
| 68 |
c := qt.New(t) |
| 69 |
|
| 70 |
tree := doctree.New( |
| 71 |
doctree.Config[*testValue]{ |
| 72 |
Shifter: &testShifter{}, |
| 73 |
}, |
| 74 |
) |
| 75 |
|
| 76 |
tree.Insert("", &testValue{ID: "HOME"}) |
| 77 |
tree.Insert("/a", &testValue{ID: "/a"}) |
| 78 |
tree.Insert("/a/b", &testValue{ID: "/a/b"}) |
| 79 |
tree.Insert("/b", &testValue{ID: "/b"}) |
| 80 |
tree.Insert("/b/c", &testValue{ID: "/b/c"}) |
| 81 |
tree.Insert("/b/c/d", &testValue{ID: "/b/c/d"}) |
| 82 |
|
| 83 |
var values []string |
| 84 |
|
| 85 |
ctx := &doctree.WalkContext[*testValue]{} |
| 86 |
|
| 87 |
w := &doctree.NodeShiftTreeWalker[*testValue]{ |
| 88 |
Tree: tree, |
| 89 |
WalkContext: ctx, |
| 90 |
Handle: func(s string, t *testValue) (radix.WalkFlag, error) { |
| 91 |
ctx.Data().Insert(s, map[string]any{ |
| 92 |
"id": t.ID, |
| 93 |
}) |
| 94 |
|
| 95 |
if s != "" { |
| 96 |
p, v := ctx.Data().LongestPrefix(path.Dir(s)) |
| 97 |
values = append(values, fmt.Sprintf("%s:%s:%v", s, p, v)) |
| 98 |
} |
| 99 |
return radix.WalkContinue, nil |
| 100 |
}, |
| 101 |
} |
| 102 |
|
| 103 |
w.Walk(context.Background()) |
| 104 |
|
| 105 |
c.Assert(strings.Join(values, "|"), qt.Equals, "/a::map[id:HOME]|/a/b:/a:map[id:/a]|/b::map[id:HOME]|/b/c:/b:map[id:/b]|/b/c/d:/b/c:map[id:/b/c]") |
| 106 |
} |
| 107 |
|
| 108 |
func TestTreeEvents(t *testing.T) { |
| 109 |
c := qt.New(t) |
| 110 |
|
| 111 |
tree := doctree.New( |
| 112 |
doctree.Config[*testValue]{ |
| 113 |
Shifter: &testShifter{echo: true}, |
| 114 |
}, |
| 115 |
) |
| 116 |
|
| 117 |
tree.Insert("/a", &testValue{ID: "/a", Weight: 2, IsBranch: true}) |
| 118 |
tree.Insert("/a/p1", &testValue{ID: "/a/p1", Weight: 5}) |
| 119 |
tree.Insert("/a/p", &testValue{ID: "/a/p2", Weight: 6}) |
| 120 |
tree.Insert("/a/s1", &testValue{ID: "/a/s1", Weight: 5, IsBranch: true}) |
| 121 |
tree.Insert("/a/s1/p1", &testValue{ID: "/a/s1/p1", Weight: 8}) |
| 122 |
tree.Insert("/a/s1/p1", &testValue{ID: "/a/s1/p2", Weight: 9}) |
| 123 |
tree.Insert("/a/s1/s2", &testValue{ID: "/a/s1/s2", Weight: 6, IsBranch: true}) |
| 124 |
tree.Insert("/a/s1/s2/p1", &testValue{ID: "/a/s1/s2/p1", Weight: 8}) |
| 125 |
tree.Insert("/a/s1/s2/p2", &testValue{ID: "/a/s1/s2/p2", Weight: 7}) |
| 126 |
|
| 127 |
w := &doctree.NodeShiftTreeWalker[*testValue]{ |
| 128 |
Tree: tree, |
| 129 |
WalkContext: &doctree.WalkContext[*testValue]{}, |
| 130 |
} |
| 131 |
|
| 132 |
w.Handle = func(s string, t *testValue) (radix.WalkFlag, error) { |
| 133 |
if t.IsBranch { |
| 134 |
w.WalkContext.AddEventListener("weight", s, func(e *doctree.Event[*testValue]) { |
| 135 |
if e.Source.Weight > t.Weight { |
| 136 |
t.Weight = e.Source.Weight |
| 137 |
w.WalkContext.SendEvent(&doctree.Event[*testValue]{Source: t, Path: s, Name: "weight"}) |
| 138 |
} |
| 139 |
// Reduces the amount of events bubbling up the tree. If the weight for this branch has |
| 140 |
// increased, that will be announced in its own event. |
| 141 |
e.StopPropagation() |
| 142 |
}) |
| 143 |
} else { |
| 144 |
w.WalkContext.SendEvent(&doctree.Event[*testValue]{Source: t, Path: s, Name: "weight"}) |
| 145 |
} |
| 146 |
|
| 147 |
return radix.WalkContinue, nil |
| 148 |
} |
| 149 |
|
| 150 |
c.Assert(w.Walk(context.Background()), qt.IsNil) |
| 151 |
c.Assert(w.WalkContext.HandleEventsAndHooks(), qt.IsNil) |
| 152 |
|
| 153 |
c.Assert(tree.Get("/a").Weight, eq, 9) |
| 154 |
c.Assert(tree.Get("/a/s1").Weight, eq, 9) |
| 155 |
c.Assert(tree.Get("/a/p").Weight, eq, 6) |
| 156 |
c.Assert(tree.Get("/a/s1/s2").Weight, eq, 8) |
| 157 |
c.Assert(tree.Get("/a/s1/s2/p2").Weight, eq, 7) |
| 158 |
} |
| 159 |
|
| 160 |
func TestTreeInsert(t *testing.T) { |
| 161 |
c := qt.New(t) |
| 162 |
|
| 163 |
tree := doctree.New( |
| 164 |
doctree.Config[*testValue]{ |
| 165 |
Shifter: &testShifter{}, |
| 166 |
}, |
| 167 |
) |
| 168 |
|
| 169 |
a := &testValue{ID: "/a"} |
| 170 |
tree.Insert("/a", a) |
| 171 |
ab := &testValue{ID: "/a/b"} |
| 172 |
tree.Insert("/a/b", ab) |
| 173 |
|
| 174 |
c.Assert(tree.Get("/a"), eq, &testValue{ID: "/a", Lang: 0}) |
| 175 |
c.Assert(tree.Get("/notfound"), qt.IsNil) |
| 176 |
|
| 177 |
ab2 := &testValue{ID: "/a/b", Lang: 0} |
| 178 |
v, _, ok := tree.Insert("/a/b", ab2) |
| 179 |
c.Assert(ok, qt.IsTrue) |
| 180 |
c.Assert(v, qt.DeepEquals, ab2) |
| 181 |
|
| 182 |
tree1 := tree.Shape(sitesmatrix.Vector{1, 0, 0}) |
| 183 |
c.Assert(tree1.Get("/a/b"), qt.DeepEquals, &testValue{ID: "/a/b", Lang: 1}) |
| 184 |
} |
| 185 |
|
| 186 |
func TestTreePara(t *testing.T) { |
| 187 |
c := qt.New(t) |
| 188 |
|
| 189 |
p := para.New(4) |
| 190 |
r, _ := p.Start(context.Background()) |
| 191 |
|
| 192 |
tree := doctree.New( |
| 193 |
doctree.Config[*testValue]{ |
| 194 |
Shifter: &testShifter{}, |
| 195 |
}, |
| 196 |
) |
| 197 |
|
| 198 |
for i := range 8 { |
| 199 |
r.Run(func() error { |
| 200 |
a := &testValue{ID: "/a"} |
| 201 |
tree.Lock(true) |
| 202 |
defer tree.Unlock(true) |
| 203 |
tree.Insert("/a", a) |
| 204 |
ab := &testValue{ID: "/a/b"} |
| 205 |
tree.Insert("/a/b", ab) |
| 206 |
|
| 207 |
key := fmt.Sprintf("/a/b/c/%d", i) |
| 208 |
val := &testValue{ID: key} |
| 209 |
tree.Insert(key, val) |
| 210 |
c.Assert(tree.Get(key), eq, val) |
| 211 |
// s, _ := tree.LongestPrefix(key, nil) |
| 212 |
// c.Assert(s, eq, "/a/b") |
| 213 |
|
| 214 |
return nil |
| 215 |
}) |
| 216 |
} |
| 217 |
|
| 218 |
c.Assert(r.Wait(), qt.IsNil) |
| 219 |
} |
| 220 |
|
| 221 |
func TestValidateKey(t *testing.T) { |
| 222 |
c := qt.New(t) |
| 223 |
|
| 224 |
c.Assert(doctree.ValidateKey(""), qt.IsNil) |
| 225 |
c.Assert(doctree.ValidateKey("/a/b/c"), qt.IsNil) |
| 226 |
c.Assert(doctree.ValidateKey("/"), qt.IsNotNil) |
| 227 |
c.Assert(doctree.ValidateKey("a"), qt.IsNotNil) |
| 228 |
c.Assert(doctree.ValidateKey("abc"), qt.IsNotNil) |
| 229 |
c.Assert(doctree.ValidateKey("/abc/"), qt.IsNotNil) |
| 230 |
} |
| 231 |
|
| 232 |
type testShifter struct { |
| 233 |
echo bool |
| 234 |
} |
| 235 |
|
| 236 |
func (s *testShifter) ForEeachInDimension(n *testValue, v sitesmatrix.Vector, d int, f func(n *testValue) bool) { |
| 237 |
if d != sitesmatrix.Language { |
| 238 |
panic("not implemented") |
| 239 |
} |
| 240 |
f(n) |
| 241 |
} |
| 242 |
|
| 243 |
func (s *testShifter) ForEeachInAllDimensions(n *testValue, f func(*testValue) bool) { |
| 244 |
if n == nil { |
| 245 |
return |
| 246 |
} |
| 247 |
if !f(n) { |
| 248 |
return |
| 249 |
} |
| 250 |
for _, v := range s.All(n) { |
| 251 |
if v != n && !f(v) { |
| 252 |
return |
| 253 |
} |
| 254 |
} |
| 255 |
} |
| 256 |
|
| 257 |
func (s *testShifter) Insert(old, new *testValue) (*testValue, *testValue, bool) { |
| 258 |
return new, old, true |
| 259 |
} |
| 260 |
|
| 261 |
func (s *testShifter) Delete(n *testValue, dimension sitesmatrix.Vector) (*testValue, bool, bool) { |
| 262 |
return nil, true, true |
| 263 |
} |
| 264 |
|
| 265 |
func (s *testShifter) DeleteFunc(v *testValue, f func(*testValue) bool) bool { |
| 266 |
return f(v) |
| 267 |
} |
| 268 |
|
| 269 |
func (s *testShifter) Shift(n *testValue, dimension sitesmatrix.Vector, fallback bool) (v *testValue, ok bool) { |
| 270 |
ok = true |
| 271 |
v = n |
| 272 |
if s.echo { |
| 273 |
return |
| 274 |
} |
| 275 |
if n.NoCopy { |
| 276 |
if n.Lang == dimension[0] { |
| 277 |
return |
| 278 |
} |
| 279 |
v = nil |
| 280 |
ok = false |
| 281 |
return |
| 282 |
} |
| 283 |
c := *n |
| 284 |
c.Lang = dimension[0] |
| 285 |
v = &c |
| 286 |
return |
| 287 |
} |
| 288 |
|
| 289 |
func (s *testShifter) All(n *testValue) []*testValue { |
| 290 |
return []*testValue{n} |
| 291 |
} |
| 292 |
|
| 293 |
type testValue struct { |
| 294 |
ID string |
| 295 |
Lang int |
| 296 |
|
| 297 |
Weight int |
| 298 |
IsBranch bool |
| 299 |
|
| 300 |
NoCopy bool |
| 301 |
} |
| 302 |
|
| 303 |
func BenchmarkTreeInsert(b *testing.B) { |
| 304 |
runBench := func(b *testing.B, numElements int) { |
| 305 |
for b.Loop() { |
| 306 |
tree := doctree.New( |
| 307 |
doctree.Config[*testValue]{ |
| 308 |
Shifter: &testShifter{}, |
| 309 |
}, |
| 310 |
) |
| 311 |
|
| 312 |
for i := range numElements { |
| 313 |
lang := rand.Intn(2) |
| 314 |
tree.Insert(fmt.Sprintf("/%d", i), &testValue{ID: fmt.Sprintf("/%d", i), Lang: lang, Weight: i, NoCopy: true}) |
| 315 |
} |
| 316 |
} |
| 317 |
} |
| 318 |
|
| 319 |
b.Run("1000", func(b *testing.B) { |
| 320 |
runBench(b, 1000) |
| 321 |
}) |
| 322 |
|
| 323 |
b.Run("10000", func(b *testing.B) { |
| 324 |
runBench(b, 10000) |
| 325 |
}) |
| 326 |
|
| 327 |
b.Run("100000", func(b *testing.B) { |
| 328 |
runBench(b, 100000) |
| 329 |
}) |
| 330 |
|
| 331 |
b.Run("300000", func(b *testing.B) { |
| 332 |
runBench(b, 300000) |
| 333 |
}) |
| 334 |
} |
| 335 |
|
| 336 |
func BenchmarkWalk(b *testing.B) { |
| 337 |
const numElements = 1000 |
| 338 |
|
| 339 |
createTree := func() *doctree.NodeShiftTree[*testValue] { |
| 340 |
tree := doctree.New( |
| 341 |
doctree.Config[*testValue]{ |
| 342 |
Shifter: &testShifter{}, |
| 343 |
}, |
| 344 |
) |
| 345 |
|
| 346 |
for i := range numElements { |
| 347 |
lang := rand.Intn(2) |
| 348 |
tree.Insert(fmt.Sprintf("/%d", i), &testValue{ID: fmt.Sprintf("/%d", i), Lang: lang, Weight: i, NoCopy: true}) |
| 349 |
} |
| 350 |
|
| 351 |
return tree |
| 352 |
} |
| 353 |
|
| 354 |
handle := func(s string, t *testValue) (radix.WalkFlag, error) { |
| 355 |
return radix.WalkContinue, nil |
| 356 |
} |
| 357 |
|
| 358 |
for _, numElements := range []int{1000, 10000, 100000} { |
| 359 |
|
| 360 |
b.Run(fmt.Sprintf("Walk one dimension %d", numElements), func(b *testing.B) { |
| 361 |
tree := createTree() |
| 362 |
b.ResetTimer() |
| 363 |
for b.Loop() { |
| 364 |
w := &doctree.NodeShiftTreeWalker[*testValue]{ |
| 365 |
Tree: tree, |
| 366 |
Handle: handle, |
| 367 |
} |
| 368 |
if err := w.Walk(context.Background()); err != nil { |
| 369 |
b.Fatal(err) |
| 370 |
} |
| 371 |
} |
| 372 |
}) |
| 373 |
|
| 374 |
b.Run(fmt.Sprintf("Walk all dimensions %d", numElements), func(b *testing.B) { |
| 375 |
base := createTree() |
| 376 |
b.ResetTimer() |
| 377 |
for b.Loop() { |
| 378 |
for d1 := range 1 { |
| 379 |
for d2 := range 2 { |
| 380 |
tree := base.Shape(sitesmatrix.Vector{d1, d2, 0}) |
| 381 |
w := &doctree.NodeShiftTreeWalker[*testValue]{ |
| 382 |
Tree: tree, |
| 383 |
Handle: handle, |
| 384 |
} |
| 385 |
if err := w.Walk(context.Background()); err != nil { |
| 386 |
b.Fatal(err) |
| 387 |
} |
| 388 |
} |
| 389 |
} |
| 390 |
} |
| 391 |
}) |
| 392 |
|
| 393 |
} |
| 394 |
} |