Debian Codegraph @

hugolib/doctree/nodeshiftree_test.go

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