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

3 files changed, 215 insertions, 7 deletions

diff --git a/navigation/menu.go b/navigation/menu.go
index 1fb970c7c..159c49710 100644
--- 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
new file mode 100644
index 000000000..6a3266431
--- /dev/null
+++ 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
new file mode 100644
index 000000000..4bb8921bf
--- /dev/null
+++ 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()
+}