Only invoke a given cached partial once

Note that this is backed by a LRU cache (which we soon shall see more usage of), so if you're a heavy user of cached partials it may be evicted and
refreshed if needed. But in most cases every partial is only invoked once.

This commit also adds a timeout (the global `timeout` config option) to make infinite recursion in partials
easier to reason about.

```
name              old time/op    new time/op    delta
IncludeCached-10    8.92ms ± 0%    8.48ms ± 1%   -4.87%  (p=0.016 n=4+5)

name              old alloc/op   new alloc/op   delta
IncludeCached-10    6.65MB ± 0%    5.17MB ± 0%  -22.32%  (p=0.002 n=6+6)

name              old allocs/op  new allocs/op  delta
IncludeCached-10      117k ± 0%       71k ± 0%  -39.44%  (p=0.002 n=6+6)
```

Closes #4086
Updates #9588

3 files changed, 135 insertions, 146 deletions

diff --git a/tpl/partials/integration_test.go b/tpl/partials/integration_test.go
index bda5ddbd5..fcebe6c05 100644
--- a/tpl/partials/integration_test.go
+++ b/tpl/partials/integration_test.go
@@ -21,6 +21,8 @@ import (
 	"strings"
 	"testing"
 
+	qt "github.com/frankban/quicktest"
+
 	"github.com/gohugoio/hugo/htesting/hqt"
 	"github.com/gohugoio/hugo/hugolib"
 )
@@ -225,7 +227,7 @@ D1
 	b.Assert(got, hqt.IsSameString, expect)
 }
 
-//  gobench --package ./tpl/partials
+// gobench --package ./tpl/partials
 func BenchmarkIncludeCached(b *testing.B) {
 	files := `
 -- config.toml --
@@ -262,7 +264,7 @@ ABCDE
 	}
 	builders := make([]*hugolib.IntegrationTestBuilder, b.N)
 
-	for i, _ := range builders {
+	for i := range builders {
 		builders[i] = hugolib.NewIntegrationTestBuilder(cfg)
 	}
 
@@ -272,3 +274,53 @@ ABCDE
 		builders[i].Build()
 	}
 }
+
+func TestIncludeTimeout(t *testing.T) {
+	t.Parallel()
+
+	files := `
+-- config.toml --
+baseURL = 'http://example.com/'
+timeout = '200ms'
+-- layouts/index.html --
+{{ partials.Include "foo.html" . }}
+-- layouts/partials/foo.html --
+{{ partial "foo.html" . }}
+  `
+
+	b, err := hugolib.NewIntegrationTestBuilder(
+		hugolib.IntegrationTestConfig{
+			T:           t,
+			TxtarString: files,
+		},
+	).BuildE()
+
+	b.Assert(err, qt.Not(qt.IsNil))
+	b.Assert(err.Error(), qt.Contains, "timed out")
+
+}
+
+func TestIncludeCachedTimeout(t *testing.T) {
+	t.Parallel()
+
+	files := `
+-- config.toml --
+baseURL = 'http://example.com/'
+timeout = '200ms'
+-- layouts/index.html --
+{{ partials.IncludeCached "foo.html" . }}
+-- layouts/partials/foo.html --
+{{ partialCached "foo.html" . }}
+  `
+
+	b, err := hugolib.NewIntegrationTestBuilder(
+		hugolib.IntegrationTestConfig{
+			T:           t,
+			TxtarString: files,
+		},
+	).BuildE()
+
+	b.Assert(err, qt.Not(qt.IsNil))
+	b.Assert(err.Error(), qt.Contains, "timed out")
+
+}
diff --git a/tpl/partials/partials.go b/tpl/partials/partials.go
index eb4ebfe32..3b08604b7 100644
--- a/tpl/partials/partials.go
+++ b/tpl/partials/partials.go
@@ -17,19 +17,17 @@ package partials
 
 import (
 	"context"
-	"errors"
 	"fmt"
 	"html/template"
 	"io"
 	"io/ioutil"
-	"reflect"
 	"strings"
-	"sync"
 	"time"
 
-	texttemplate "github.com/gohugoio/hugo/tpl/internal/go_templates/texttemplate"
+	"github.com/bep/lazycache"
 
-	"github.com/gohugoio/hugo/helpers"
+	"github.com/gohugoio/hugo/identity"
+	texttemplate "github.com/gohugoio/hugo/tpl/internal/go_templates/texttemplate"
 
 	"github.com/gohugoio/hugo/tpl"
 
@@ -42,32 +40,48 @@ import (
 var TestTemplateProvider deps.ResourceProvider
 
 type partialCacheKey struct {
-	name    string
-	variant any
+	Name     string
+	Variants []any
+}
+type includeResult struct {
+	name   string
+	result any
+	err    error
+}
+
+func (k partialCacheKey) Key() string {
+	if k.Variants == nil {
+		return k.Name
+	}
+	return identity.HashString(append([]any{k.Name}, k.Variants...)...)
 }
 
 func (k partialCacheKey) templateName() string {
-	if !strings.HasPrefix(k.name, "partials/") {
-		return "partials/" + k.name
+	if !strings.HasPrefix(k.Name, "partials/") {
+		return "partials/" + k.Name
 	}
-	return k.name
+	return k.Name
 }
 
-// partialCache represents a cache of partials protected by a mutex.
+// partialCache represents a LRU cache of partials.
 type partialCache struct {
-	sync.RWMutex
-	p map[partialCacheKey]any
+	cache *lazycache.Cache[string, includeResult]
 }
 
 func (p *partialCache) clear() {
-	p.Lock()
-	defer p.Unlock()
-	p.p = make(map[partialCacheKey]any)
+	p.cache.DeleteFunc(func(string, includeResult) bool {
+		return true
+	})
 }
 
 // New returns a new instance of the templates-namespaced template functions.
 func New(deps *deps.Deps) *Namespace {
-	cache := &partialCache{p: make(map[partialCacheKey]any)}
+	// This lazycache was introduced in Hugo 0.111.0.
+	// We're going to expand and consolidate all memory caches in Hugo using this,
+	// so just set a high limit for now.
+	lru := lazycache.New[string, includeResult](lazycache.Options{MaxEntries: 1000})
+
+	cache := &partialCache{cache: lru}
 	deps.BuildStartListeners.Add(
 		func() {
 			cache.clear()
@@ -103,21 +117,44 @@ func (c *contextWrapper) Set(in any) string {
 // A string if the partial is a text/template, or template.HTML when html/template.
 // Note that ctx is provided by Hugo, not the end user.
 func (ns *Namespace) Include(ctx context.Context, name string, contextList ...any) (any, error) {
-	name, result, err := ns.include(ctx, name, contextList...)
-	if err != nil {
-		return result, err
+	res := ns.includWithTimeout(ctx, name, contextList...)
+	if res.err != nil {
+		return nil, res.err
 	}
 
 	if ns.deps.Metrics != nil {
-		ns.deps.Metrics.TrackValue(name, result, false)
+		ns.deps.Metrics.TrackValue(res.name, res.result, false)
+	}
+
+	return res.result, nil
+}
+
+func (ns *Namespace) includWithTimeout(ctx context.Context, name string, dataList ...any) includeResult {
+	ctx, cancel := context.WithTimeout(ctx, ns.deps.Timeout)
+	defer cancel()
+
+	res := make(chan includeResult, 1)
+
+	go func() {
+		res <- ns.include(ctx, name, dataList...)
+	}()
+
+	select {
+	case r := <-res:
+		return r
+	case <-ctx.Done():
+		err := ctx.Err()
+		if err == context.DeadlineExceeded {
+			err = fmt.Errorf("partial %q timed out after %s. This is most likely due to infinite recursion. If this is just a slow template, you can try to increase the 'timeout' config setting.", name, ns.deps.Timeout)
+		}
+		return includeResult{err: err}
 	}
 
-	return result, nil
 }
 
 // include is a helper function that lookups and executes the named partial.
 // Returns the final template name and the rendered output.
-func (ns *Namespace) include(ctx context.Context, name string, dataList ...any) (string, any, error) {
+func (ns *Namespace) include(ctx context.Context, name string, dataList ...any) includeResult {
 	var data any
 	if len(dataList) > 0 {
 		data = dataList[0]
@@ -137,7 +174,7 @@ func (ns *Namespace) include(ctx context.Context, name string, dataList ...any)
 	}
 
 	if !found {
-		return "", "", fmt.Errorf("partial %q not found", name)
+		return includeResult{err: fmt.Errorf("partial %q not found", name)}
 	}
 
 	var info tpl.ParseInfo
@@ -164,7 +201,7 @@ func (ns *Namespace) include(ctx context.Context, name string, dataList ...any)
 	}
 
 	if err := ns.deps.Tmpl().ExecuteWithContext(ctx, templ, w, data); err != nil {
-		return "", nil, err
+		return includeResult{err: err}
 	}
 
 	var result any
@@ -177,101 +214,41 @@ func (ns *Namespace) include(ctx context.Context, name string, dataList ...any)
 		result = template.HTML(w.(fmt.Stringer).String())
 	}
 
-	return templ.Name(), result, nil
+	return includeResult{
+		name:   templ.Name(),
+		result: result,
+	}
+
 }
 
 // IncludeCached executes and caches partial templates.  The cache is created with name+variants as the key.
 // Note that ctx is provided by Hugo, not the end user.
 func (ns *Namespace) IncludeCached(ctx context.Context, name string, context any, variants ...any) (any, error) {
-	key, err := createKey(name, variants...)
-	if err != nil {
-		return nil, err
-	}
-
-	result, err := ns.getOrCreate(ctx, key, context)
-	if err == errUnHashable {
-		// Try one more
-		key.variant = helpers.HashString(key.variant)
-		result, err = ns.getOrCreate(ctx, key, context)
+	start := time.Now()
+	key := partialCacheKey{
+		Name:     name,
+		Variants: variants,
 	}
 
-	return result, err
-}
+	r, found, err := ns.cachedPartials.cache.GetOrCreate(key.Key(), func(string) (includeResult, error) {
+		r := ns.includWithTimeout(ctx, key.Name, context)
+		return r, r.err
+	})
 
-func createKey(name string, variants ...any) (partialCacheKey, error) {
-	var variant any
-
-	if len(variants) > 1 {
-		variant = helpers.HashString(variants...)
-	} else if len(variants) == 1 {
-		variant = variants[0]
-		t := reflect.TypeOf(variant)
-		switch t.Kind() {
-		// This isn't an exhaustive list of unhashable types.
-		// There may be structs with slices,
-		// but that should be very rare. We do recover from that situation
-		// below.
-		case reflect.Slice, reflect.Array, reflect.Map:
-			variant = helpers.HashString(variant)
-		}
+	if err != nil {
+		return nil, err
 	}
 
-	return partialCacheKey{name: name, variant: variant}, nil
-}
-
-var errUnHashable = errors.New("unhashable")
-
-func (ns *Namespace) getOrCreate(ctx context.Context, key partialCacheKey, context any) (result any, err error) {
-	start := time.Now()
-	defer func() {
-		if r := recover(); r != nil {
-			err = r.(error)
-			if strings.Contains(err.Error(), "unhashable type") {
-				ns.cachedPartials.RUnlock()
-				err = errUnHashable
-			}
-		}
-	}()
-
-	ns.cachedPartials.RLock()
-	p, ok := ns.cachedPartials.p[key]
-	ns.cachedPartials.RUnlock()
-
-	if ok {
-		if ns.deps.Metrics != nil {
-			ns.deps.Metrics.TrackValue(key.templateName(), p, true)
+	if ns.deps.Metrics != nil {
+		if found {
 			// The templates that gets executed is measured in Execute.
 			// We need to track the time spent in the cache to
 			// get the totals correct.
 			ns.deps.Metrics.MeasureSince(key.templateName(), start)
 
 		}
-		return p, nil
+		ns.deps.Metrics.TrackValue(key.templateName(), r.result, found)
 	}
 
-	// This needs to be done outside the lock.
-	// See #9588
-	_, p, err = ns.include(ctx, key.name, context)
-	if err != nil {
-		return nil, err
-	}
-
-	ns.cachedPartials.Lock()
-	defer ns.cachedPartials.Unlock()
-	// Double-check.
-	if p2, ok := ns.cachedPartials.p[key]; ok {
-		if ns.deps.Metrics != nil {
-			ns.deps.Metrics.TrackValue(key.templateName(), p, true)
-			ns.deps.Metrics.MeasureSince(key.templateName(), start)
-		}
-		return p2, nil
-
-	}
-	if ns.deps.Metrics != nil {
-		ns.deps.Metrics.TrackValue(key.templateName(), p, false)
-	}
-
-	ns.cachedPartials.p[key] = p
-
-	return p, nil
+	return r.result, nil
 }
diff --git a/tpl/partials/partials_test.go b/tpl/partials/partials_test.go
deleted file mode 100644
index 490354499..000000000
--- a/tpl/partials/partials_test.go
+++ /dev/null
@@ -1,40 +0,0 @@
-// Copyright 2019 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 partials
-
-import (
-	"testing"
-
-	qt "github.com/frankban/quicktest"
-)
-
-func TestCreateKey(t *testing.T) {
-	c := qt.New(t)
-	m := make(map[any]bool)
-
-	create := func(name string, variants ...any) partialCacheKey {
-		k, err := createKey(name, variants...)
-		c.Assert(err, qt.IsNil)
-		m[k] = true
-		return k
-	}
-
-	for i := 0; i < 123; i++ {
-		c.Assert(create("a", "b"), qt.Equals, partialCacheKey{name: "a", variant: "b"})
-		c.Assert(create("a", "b", "c"), qt.Equals, partialCacheKey{name: "a", variant: "9629524865311698396"})
-		c.Assert(create("a", 1), qt.Equals, partialCacheKey{name: "a", variant: 1})
-		c.Assert(create("a", map[string]string{"a": "av"}), qt.Equals, partialCacheKey{name: "a", variant: "4809626101226749924"})
-		c.Assert(create("a", []string{"a", "b"}), qt.Equals, partialCacheKey{name: "a", variant: "2712570657419664240"})
-	}
-}