commit 785a31b5b84643f4769f9bd363599cbcce86f098
parent bc1e05286a96d08ad02ad200d6a4076bb01c486e
Author: satotake <doublequotation@gmail.com>
Date: Sun, 23 May 2021 17:42:01 +0900
navigation: Cache and copy Menu for sorting
.Site.Menus is mutated when it is sorted for now and this causes concurrency problem (#7594)
In this patch, each related sort function copies Menu before sorting to prevent
race condition.
Pages already have such a sort and cache logic and this patch is identical to it.
Closes #7594
Diffstat:
4 files changed, 303 insertions(+), 7 deletions(-)
diff --git a/hugolib/menu_test.go b/hugolib/menu_test.go
@@ -105,6 +105,94 @@ Menu Main: {{ partial "menu.html" (dict "page" . "menu" "main") }}`,
"/sect3/|Sect3s|Sect3s|0|-|-|")
}
+// related issue #7594
+func TestMenuSort(t *testing.T) {
+ b := newTestSitesBuilder(t).WithSimpleConfigFile()
+
+ b.WithTemplatesAdded("index.html", `
+{{ range $k, $v := .Site.Menus.main }}
+Default1|{{ $k }}|{{ $v.Weight }}|{{ $v.Name }}|{{ .URL }}|{{ $v.Page }}{{ end }}
+{{ range $k, $v := .Site.Menus.main.ByWeight }}
+ByWeight|{{ $k }}|{{ $v.Weight }}|{{ $v.Name }}|{{ .URL }}|{{ $v.Page }}{{ end }}
+{{ range $k, $v := (.Site.Menus.main.ByWeight).Reverse }}
+Reverse|{{ $k }}|{{ $v.Weight }}|{{ $v.Name }}|{{ .URL }}|{{ $v.Page }}{{ end }}
+{{ range $k, $v := .Site.Menus.main }}
+Default2|{{ $k }}|{{ $v.Weight }}|{{ $v.Name }}|{{ .URL }}|{{ $v.Page }}{{ end }}
+{{ range $k, $v := .Site.Menus.main.ByWeight }}
+ByWeight|{{ $k }}|{{ $v.Weight }}|{{ $v.Name }}|{{ .URL }}|{{ $v.Page }}{{ end }}
+{{ range $k, $v := .Site.Menus.main }}
+Default3|{{ $k }}|{{ $v.Weight }}|{{ $v.Name }}|{{ .URL }}|{{ $v.Page }}{{ end }}
+`)
+
+ b.WithContent("_index.md", `
+---
+title: Home
+menu:
+ main:
+ weight: 100
+---`)
+
+ b.WithContent("blog/A.md", `
+---
+title: "A"
+menu:
+ main:
+ weight: 10
+---
+`)
+
+ b.WithContent("blog/B.md", `
+---
+title: "B"
+menu:
+ main:
+ weight: 20
+---
+`)
+ b.WithContent("blog/C.md", `
+---
+title: "C"
+menu:
+ main:
+ weight: 30
+---
+`)
+
+ b.Build(BuildCfg{})
+
+ b.AssertFileContent("public/index.html",
+ `Default1|0|10|A|/blog/a/|Page(/blog/A.md)
+ Default1|1|20|B|/blog/b/|Page(/blog/B.md)
+ Default1|2|30|C|/blog/c/|Page(/blog/C.md)
+ Default1|3|100|Home|/|Page(/_index.md)
+
+ ByWeight|0|10|A|/blog/a/|Page(/blog/A.md)
+ ByWeight|1|20|B|/blog/b/|Page(/blog/B.md)
+ ByWeight|2|30|C|/blog/c/|Page(/blog/C.md)
+ ByWeight|3|100|Home|/|Page(/_index.md)
+
+ Reverse|0|100|Home|/|Page(/_index.md)
+ Reverse|1|30|C|/blog/c/|Page(/blog/C.md)
+ Reverse|2|20|B|/blog/b/|Page(/blog/B.md)
+ Reverse|3|10|A|/blog/a/|Page(/blog/A.md)
+
+ Default2|0|10|A|/blog/a/|Page(/blog/A.md)
+ Default2|1|20|B|/blog/b/|Page(/blog/B.md)
+ Default2|2|30|C|/blog/c/|Page(/blog/C.md)
+ Default2|3|100|Home|/|Page(/_index.md)
+
+ ByWeight|0|10|A|/blog/a/|Page(/blog/A.md)
+ ByWeight|1|20|B|/blog/b/|Page(/blog/B.md)
+ ByWeight|2|30|C|/blog/c/|Page(/blog/C.md)
+ ByWeight|3|100|Home|/|Page(/_index.md)
+
+ Default3|0|10|A|/blog/a/|Page(/blog/A.md)
+ Default3|1|20|B|/blog/b/|Page(/blog/B.md)
+ Default3|2|30|C|/blog/c/|Page(/blog/C.md)
+ Default3|3|100|Home|/|Page(/_index.md)`,
+ )
+}
+
func TestMenuFrontMatter(t *testing.T) {
b := newTestSitesBuilder(t).WithSimpleConfigFile()
diff --git a/navigation/menu.go b/navigation/menu.go
@@ -25,6 +25,8 @@ import (
"github.com/spf13/cast"
)
+var smc = newMenuCache()
+
// MenuEntry represents a menu item defined in either Page front matter
// or in the site config.
type MenuEntry struct {
@@ -204,27 +206,39 @@ func (m Menu) Limit(n int) Menu {
// ByWeight sorts the menu by the weight defined in the menu configuration.
func (m Menu) ByWeight() Menu {
- menuEntryBy(defaultMenuEntrySort).Sort(m)
- return m
+ const key = "menuSort.ByWeight"
+ menus, _ := smc.get(key, menuEntryBy(defaultMenuEntrySort).Sort, m)
+
+ return menus
}
// ByName sorts the menu by the name defined in the menu configuration.
func (m Menu) ByName() Menu {
+ const key = "menuSort.ByName"
title := func(m1, m2 *MenuEntry) bool {
return compare.LessStrings(m1.Name, m2.Name)
}
- menuEntryBy(title).Sort(m)
- return m
+ menus, _ := smc.get(key, menuEntryBy(title).Sort, m)
+
+ return menus
}
// Reverse reverses the order of the menu entries.
func (m Menu) Reverse() Menu {
- for i, j := 0, len(m)-1; i < j; i, j = i+1, j-1 {
- m[i], m[j] = m[j], m[i]
+ const key = "menuSort.Reverse"
+ reverseFunc := func(menu Menu) {
+ for i, j := 0, len(menu)-1; i < j; i, j = i+1, j-1 {
+ menu[i], menu[j] = menu[j], menu[i]
+ }
}
+ menus, _ := smc.get(key, reverseFunc, m)
- return m
+ return menus
+}
+
+func (m Menu) Clone() Menu {
+ return append(Menu(nil), m...)
}
func (m *MenuEntry) Title() string {
diff --git a/navigation/menu_cache.go b/navigation/menu_cache.go
@@ -0,0 +1,113 @@
+// Copyright 2021 The Hugo Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+package navigation
+
+import (
+ "sync"
+)
+
+type menuCacheEntry struct {
+ in []Menu
+ out Menu
+}
+
+func (entry menuCacheEntry) matches(menuList []Menu) bool {
+ if len(entry.in) != len(menuList) {
+ return false
+ }
+ for i, m := range menuList {
+ if !menuEqual(m, entry.in[i]) {
+ return false
+ }
+ }
+
+ return true
+}
+
+func newMenuCache() *menuCache {
+ return &menuCache{m: make(map[string][]menuCacheEntry)}
+}
+
+func (c *menuCache) clear() {
+ c.Lock()
+ defer c.Unlock()
+ c.m = make(map[string][]menuCacheEntry)
+}
+
+type menuCache struct {
+ sync.RWMutex
+ m map[string][]menuCacheEntry
+}
+
+func menuEqual(m1, m2 Menu) bool {
+ if m1 == nil && m2 == nil {
+ return true
+ }
+
+ if m1 == nil || m2 == nil {
+ return false
+ }
+
+ if len(m1) != len(m2) {
+ return false
+ }
+
+ if len(m1) == 0 {
+ return true
+ }
+
+ for i := 0; i < len(m1); i++ {
+ if m1[i] != m2[i] {
+ return false
+ }
+ }
+ return true
+}
+
+func (c *menuCache) get(key string, apply func(m Menu), menuLists ...Menu) (Menu, bool) {
+ return c.getP(key, func(m *Menu) {
+ if apply != nil {
+ apply(*m)
+ }
+ }, menuLists...)
+}
+
+func (c *menuCache) getP(key string, apply func(m *Menu), menuLists ...Menu) (Menu, bool) {
+ c.Lock()
+ defer c.Unlock()
+
+ if cached, ok := c.m[key]; ok {
+ for _, entry := range cached {
+ if entry.matches(menuLists) {
+ return entry.out, true
+ }
+ }
+ }
+
+ m := menuLists[0]
+ menuCopy := append(Menu(nil), m...)
+
+ if apply != nil {
+ apply(&menuCopy)
+ }
+
+ entry := menuCacheEntry{in: menuLists, out: menuCopy}
+ if v, ok := c.m[key]; ok {
+ c.m[key] = append(v, entry)
+ } else {
+ c.m[key] = []menuCacheEntry{entry}
+ }
+
+ return menuCopy, false
+}
diff --git a/navigation/menu_cache_test.go b/navigation/menu_cache_test.go
@@ -0,0 +1,81 @@
+// Copyright 2021 The Hugo Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package navigation
+
+import (
+ "sync"
+ "sync/atomic"
+ "testing"
+
+ qt "github.com/frankban/quicktest"
+)
+
+func createSortTestMenu(num int) Menu {
+ menu := make(Menu, num)
+ for i := 0; i < num; i++ {
+ m := &MenuEntry{}
+ menu[i] = m
+ }
+ return menu
+}
+
+func TestMenuCache(t *testing.T) {
+ t.Parallel()
+ c := qt.New(t)
+ c1 := newMenuCache()
+
+ changeFirst := func(m Menu) {
+ m[0].title = "changed"
+ }
+
+ var o1 uint64
+ var o2 uint64
+
+ var wg sync.WaitGroup
+
+ var l1 sync.Mutex
+ var l2 sync.Mutex
+
+ var testMenuSets []Menu
+
+ for i := 0; i < 50; i++ {
+ testMenuSets = append(testMenuSets, createSortTestMenu(i+1))
+ }
+
+ for j := 0; j < 100; j++ {
+ wg.Add(1)
+ go func() {
+ defer wg.Done()
+ for k, menu := range testMenuSets {
+ l1.Lock()
+ m, ca := c1.get("k1", nil, menu)
+ c.Assert(ca, qt.Equals, !atomic.CompareAndSwapUint64(&o1, uint64(k), uint64(k+1)))
+ l1.Unlock()
+ m2, c2 := c1.get("k1", nil, m)
+ c.Assert(c2, qt.Equals, true)
+ c.Assert(menuEqual(m, m2), qt.Equals, true)
+ c.Assert(menuEqual(m, menu), qt.Equals, true)
+ c.Assert(m, qt.Not(qt.IsNil))
+
+ l2.Lock()
+ m3, c3 := c1.get("k2", changeFirst, menu)
+ c.Assert(c3, qt.Equals, !atomic.CompareAndSwapUint64(&o2, uint64(k), uint64(k+1)))
+ l2.Unlock()
+ c.Assert(m3, qt.Not(qt.IsNil))
+ c.Assert("changed", qt.Equals, m3[0].title)
+ }
+ }()
+ }
+ wg.Wait()
+}