1 files changed, 409 insertions, 95 deletions

diff --git a/identity/identity.go b/identity/identity.go
index e73951caf..ccb2f6e79 100644
--- a/identity/identity.go
+++ b/identity/identity.go
@@ -1,4 +1,4 @@
-// Copyright 2023 The Hugo Authors. All rights reserved.
+// Copyright 2024 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.
@@ -11,167 +11,481 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
+// Package provides ways to identify values in Hugo. Used for dependency tracking etc.
 package identity
 
 import (
+	"fmt"
+	"path"
 	"path/filepath"
+	"sort"
 	"strings"
 	"sync"
 	"sync/atomic"
+
+	"github.com/gohugoio/hugo/common/types"
+	"github.com/gohugoio/hugo/compare"
 )
 
-// NewManager creates a new Manager starting at id.
-func NewManager(id Provider) Manager {
-	return &identityManager{
-		Provider: id,
-		ids:      Identities{id.GetIdentity(): id},
+const (
+	// Anonymous is an Identity that can be used when identity doesn't matter.
+	Anonymous = StringIdentity("__anonymous")
+
+	// GenghisKhan is an Identity everyone relates to.
+	GenghisKhan = StringIdentity("__genghiskhan")
+)
+
+var NopManager = new(nopManager)
+
+// NewIdentityManager creates a new Manager.
+func NewManager(name string, opts ...ManagerOption) Manager {
+	idm := &identityManager{
+		Identity: Anonymous,
+		name:     name,
+		ids:      Identities{},
 	}
+
+	for _, o := range opts {
+		o(idm)
+	}
+
+	return idm
 }
 
-// NewPathIdentity creates a new Identity with the two identifiers
-// type and path.
-func NewPathIdentity(typ, pat string) PathIdentity {
-	pat = strings.ToLower(strings.TrimPrefix(filepath.ToSlash(pat), "/"))
-	return PathIdentity{Type: typ, Path: pat}
+// CleanString cleans s to be suitable as an identifier.
+func CleanString(s string) string {
+	s = strings.ToLower(s)
+	s = strings.TrimPrefix(filepath.ToSlash(s), "/")
+	return path.Clean(s)
 }
 
-// Identities stores identity providers.
-type Identities map[Identity]Provider
+// CleanStringIdentity cleans s to be suitable as an identifier and wraps it in a StringIdentity.
+func CleanStringIdentity(s string) StringIdentity {
+	return StringIdentity(CleanString(s))
+}
 
-func (ids Identities) search(depth int, id Identity) Provider {
-	if v, found := ids[id.GetIdentity()]; found {
-		return v
+// GetDependencyManager returns the DependencyManager from v or nil if none found.
+func GetDependencyManager(v any) Manager {
+	switch vv := v.(type) {
+	case Manager:
+		return vv
+	case types.Unwrapper:
+		return GetDependencyManager(vv.Unwrapv())
+	case DependencyManagerProvider:
+		return vv.GetDependencyManager()
 	}
+	return nil
+}
 
-	depth++
+// GetDependencyManagerForScope returns the DependencyManager for the given scope from v or nil if none found.
+// Note that it will fall back to an unscoped manager if none found for the given scope.
+func GetDependencyManagerForScope(v any, scope int) Manager {
+	switch vv := v.(type) {
+	case DependencyManagerScopedProvider:
+		return vv.GetDependencyManagerForScope(scope)
+	case types.Unwrapper:
+		return GetDependencyManagerForScope(vv.Unwrapv(), scope)
+	case Manager:
+		return vv
+	case DependencyManagerProvider:
+		return vv.GetDependencyManager()
 
-	// There may be infinite recursion in templates.
-	if depth > 100 {
-		// Bail out.
-		return nil
 	}
+	return nil
+}
 
-	for _, v := range ids {
-		switch t := v.(type) {
-		case IdentitiesProvider:
-			if nested := t.GetIdentities().search(depth, id); nested != nil {
-				return nested
-			}
+// FirstIdentity returns the first Identity in v, Anonymous if none found
+func FirstIdentity(v any) Identity {
+	var result Identity = Anonymous
+	WalkIdentitiesShallow(v, func(level int, id Identity) bool {
+		result = id
+		return true
+	})
+
+	return result
+}
+
+// PrintIdentityInfo is used for debugging/tests only.
+func PrintIdentityInfo(v any) {
+	WalkIdentitiesDeep(v, func(level int, id Identity) bool {
+		var s string
+		if idm, ok := id.(*identityManager); ok {
+			s = " " + idm.name
 		}
+		fmt.Printf("%s%s (%T)%s\n", strings.Repeat("  ", level), id.IdentifierBase(), id, s)
+		return false
+	})
+}
+
+func Unwrap(id Identity) Identity {
+	switch t := id.(type) {
+	case IdentityProvider:
+		return t.GetIdentity()
+	default:
+		return id
 	}
-	return nil
 }
 
-// IdentitiesProvider provides all Identities.
-type IdentitiesProvider interface {
-	GetIdentities() Identities
+// WalkIdentitiesDeep walks identities in v and applies cb to every identity found.
+// Return true from cb to terminate.
+// If deep is true, it will also walk nested Identities in any Manager found.
+func WalkIdentitiesDeep(v any, cb func(level int, id Identity) bool) {
+	seen := make(map[Identity]bool)
+	walkIdentities(v, 0, true, seen, cb)
 }
 
-// Identity represents an thing that can provide an identify. This can be
-// any Go type, but the Identity returned by GetIdentify must be hashable.
-type Identity interface {
-	Provider
-	Name() string
+// WalkIdentitiesShallow will not walk into a Manager's Identities.
+// See WalkIdentitiesDeep.
+// cb is called for every Identity found and returns whether to terminate the walk.
+func WalkIdentitiesShallow(v any, cb func(level int, id Identity) bool) {
+	walkIdentitiesShallow(v, 0, cb)
 }
 
-// Manager manages identities, and is itself a Provider of Identity.
-type Manager interface {
-	SearchProvider
-	Add(ids ...Provider)
-	Reset()
+// WithOnAddIdentity sets a callback that will be invoked when an identity is added to the manager.
+func WithOnAddIdentity(f func(id Identity)) ManagerOption {
+	return func(m *identityManager) {
+		m.onAddIdentity = f
+	}
+}
+
+// DependencyManagerProvider provides a manager for dependencies.
+type DependencyManagerProvider interface {
+	GetDependencyManager() Manager
+}
+
+// DependencyManagerProviderFunc is a function that implements the DependencyManagerProvider interface.
+type DependencyManagerProviderFunc func() Manager
+
+func (d DependencyManagerProviderFunc) GetDependencyManager() Manager {
+	return d()
+}
+
+// DependencyManagerScopedProvider provides a manager for dependencies with a given scope.
+type DependencyManagerScopedProvider interface {
+	GetDependencyManagerForScope(scope int) Manager
+}
+
+// ForEeachIdentityProvider provides a way iterate over identities.
+type ForEeachIdentityProvider interface {
+	// ForEeachIdentityProvider calls cb for each Identity.
+	// If cb returns true, the iteration is terminated.
+	ForEeachIdentity(cb func(id Identity) bool)
+}
+
+// ForEeachIdentityByNameProvider provides a way to look up identities by name.
+type ForEeachIdentityByNameProvider interface {
+	// ForEeachIdentityByName calls cb for each Identity that relates to name.
+	// If cb returns true, the iteration is terminated.
+	ForEeachIdentityByName(name string, cb func(id Identity) bool)
+}
+
+type FindFirstManagerIdentityProvider interface {
+	Identity
+	FindFirstManagerIdentity() ManagerIdentity
 }
 
-// SearchProvider provides access to the chained set of identities.
-type SearchProvider interface {
-	Provider
-	IdentitiesProvider
-	Search(id Identity) Provider
+func NewFindFirstManagerIdentityProvider(m Manager, id Identity) FindFirstManagerIdentityProvider {
+	return findFirstManagerIdentity{
+		Identity: Anonymous,
+		ManagerIdentity: ManagerIdentity{
+			Manager: m, Identity: id,
+		},
+	}
+}
+
+type findFirstManagerIdentity struct {
+	Identity
+	ManagerIdentity
+}
+
+func (f findFirstManagerIdentity) FindFirstManagerIdentity() ManagerIdentity {
+	return f.ManagerIdentity
+}
+
+// Identities stores identity providers.
+type Identities map[Identity]bool
+
+func (ids Identities) AsSlice() []Identity {
+	s := make([]Identity, len(ids))
+	i := 0
+	for v := range ids {
+		s[i] = v
+		i++
+	}
+	sort.Slice(s, func(i, j int) bool {
+		return s[i].IdentifierBase() < s[j].IdentifierBase()
+	})
+
+	return s
+}
+
+func (ids Identities) String() string {
+	var sb strings.Builder
+	i := 0
+	for id := range ids {
+		sb.WriteString(fmt.Sprintf("[%s]", id.IdentifierBase()))
+		if i < len(ids)-1 {
+			sb.WriteString(", ")
+		}
+		i++
+	}
+	return sb.String()
+}
+
+// Identity represents a thing in Hugo (a Page, a template etc.)
+// Any implementation must be comparable/hashable.
+type Identity interface {
+	IdentifierBase() string
+}
+
+// IdentityGroupProvider can be implemented by tightly connected types.
+// Current use case is Resource transformation via Hugo Pipes.
+type IdentityGroupProvider interface {
+	GetIdentityGroup() Identity
 }
 
-// A PathIdentity is a common identity identified by a type and a path, e.g. "layouts" and "_default/single.html".
-type PathIdentity struct {
-	Type string
-	Path string
+// IdentityProvider can be implemented by types that isn't itself and Identity,
+// usually because they're not comparable/hashable.
+type IdentityProvider interface {
+	GetIdentity() Identity
 }
 
-// GetIdentity returns itself.
-func (id PathIdentity) GetIdentity() Identity {
-	return id
+// IncrementByOne implements Incrementer adding 1 every time Incr is called.
+type IncrementByOne struct {
+	counter uint64
 }
 
-// Name returns the Path.
-func (id PathIdentity) Name() string {
-	return id.Path
+func (c *IncrementByOne) Incr() int {
+	return int(atomic.AddUint64(&c.counter, uint64(1)))
 }
 
-// A KeyValueIdentity a general purpose identity.
-type KeyValueIdentity struct {
-	Key   string
-	Value string
+// Incrementer increments and returns the value.
+// Typically used for IDs.
+type Incrementer interface {
+	Incr() int
 }
 
-// GetIdentity returns itself.
-func (id KeyValueIdentity) GetIdentity() Identity {
-	return id
+// IsProbablyDependentProvider is an optional interface for Identity.
+type IsProbablyDependentProvider interface {
+	IsProbablyDependent(other Identity) bool
 }
 
-// Name returns the Key.
-func (id KeyValueIdentity) Name() string {
-	return id.Key
+// IsProbablyDependencyProvider is an optional interface for Identity.
+type IsProbablyDependencyProvider interface {
+	IsProbablyDependency(other Identity) bool
 }
 
-// Provider provides the comparable Identity.
-type Provider interface {
-	// GetIdentity is for internal use.
+// Manager  is an Identity that also manages identities, typically dependencies.
+type Manager interface {
+	Identity
+	AddIdentity(ids ...Identity)
 	GetIdentity() Identity
+	Reset()
+	getIdentities() Identities
+}
+
+type ManagerOption func(m *identityManager)
+
+// StringIdentity is an Identity that wraps a string.
+type StringIdentity string
+
+func (s StringIdentity) IdentifierBase() string {
+	return string(s)
 }
 
 type identityManager struct {
-	sync.Mutex
-	Provider
+	Identity
+
+	// Only used for debugging.
+	name string
+
+	// mu protects _changes_ to this manager,
+	// reads currently assumes no concurrent writes.
+	mu  sync.RWMutex
 	ids Identities
+
+	// Hooks used in debugging.
+	onAddIdentity func(id Identity)
 }
 
-func (im *identityManager) Add(ids ...Provider) {
-	im.Lock()
+func (im *identityManager) AddIdentity(ids ...Identity) {
+	im.mu.Lock()
+
 	for _, id := range ids {
-		im.ids[id.GetIdentity()] = id
+		if id == Anonymous {
+			continue
+		}
+		if _, found := im.ids[id]; !found {
+			if im.onAddIdentity != nil {
+				im.onAddIdentity(id)
+			}
+			im.ids[id] = true
+		}
 	}
-	im.Unlock()
+	im.mu.Unlock()
+}
+
+func (im *identityManager) ContainsIdentity(id Identity) FinderResult {
+	if im.Identity != Anonymous && id == im.Identity {
+		return FinderFound
+	}
+
+	f := NewFinder(FinderConfig{Exact: true})
+	r := f.Contains(id, im, -1)
+
+	return r
+}
+
+// Managers are always anonymous.
+func (im *identityManager) GetIdentity() Identity {
+	return im.Identity
 }
 
 func (im *identityManager) Reset() {
-	im.Lock()
-	id := im.GetIdentity()
-	im.ids = Identities{id.GetIdentity(): id}
-	im.Unlock()
+	im.mu.Lock()
+	im.ids = Identities{}
+	im.mu.Unlock()
+}
+
+func (im *identityManager) GetDependencyManagerForScope(int) Manager {
+	return im
+}
+
+func (im *identityManager) String() string {
+	return fmt.Sprintf("IdentityManager(%s)", im.name)
 }
 
 // TODO(bep) these identities are currently only read on server reloads
 // so there should be no concurrency issues, but that may change.
-func (im *identityManager) GetIdentities() Identities {
-	im.Lock()
-	defer im.Unlock()
+func (im *identityManager) getIdentities() Identities {
 	return im.ids
 }
 
-func (im *identityManager) Search(id Identity) Provider {
-	im.Lock()
-	defer im.Unlock()
-	return im.ids.search(0, id.GetIdentity())
+type nopManager int
+
+func (m *nopManager) AddIdentity(ids ...Identity) {
 }
 
-// Incrementer increments and returns the value.
-// Typically used for IDs.
-type Incrementer interface {
-	Incr() int
+func (m *nopManager) IdentifierBase() string {
+	return ""
 }
 
-// IncrementByOne implements Incrementer adding 1 every time Incr is called.
-type IncrementByOne struct {
-	counter uint64
+func (m *nopManager) GetIdentity() Identity {
+	return Anonymous
 }
 
-func (c *IncrementByOne) Incr() int {
-	return int(atomic.AddUint64(&c.counter, uint64(1)))
+func (m *nopManager) Reset() {
+}
+
+func (m *nopManager) getIdentities() Identities {
+	return nil
+}
+
+// returns whether further walking should be terminated.
+func walkIdentities(v any, level int, deep bool, seen map[Identity]bool, cb func(level int, id Identity) bool) {
+	if level > 20 {
+		panic("too deep")
+	}
+	var cbRecursive func(level int, id Identity) bool
+	cbRecursive = func(level int, id Identity) bool {
+		if id == nil {
+			return false
+		}
+		if deep && seen[id] {
+			return false
+		}
+		seen[id] = true
+		if cb(level, id) {
+			return true
+		}
+
+		if deep {
+			if m := GetDependencyManager(id); m != nil {
+				for id2 := range m.getIdentities() {
+					if walkIdentitiesShallow(id2, level+1, cbRecursive) {
+						return true
+					}
+				}
+			}
+		}
+		return false
+	}
+	walkIdentitiesShallow(v, level, cbRecursive)
+}
+
+// returns whether further walking should be terminated.
+// Anonymous identities are skipped.
+func walkIdentitiesShallow(v any, level int, cb func(level int, id Identity) bool) bool {
+	cb2 := func(level int, id Identity) bool {
+		if id == Anonymous {
+			return false
+		}
+		return cb(level, id)
+	}
+
+	if id, ok := v.(Identity); ok {
+		if cb2(level, id) {
+			return true
+		}
+	}
+
+	if ipd, ok := v.(IdentityProvider); ok {
+		if cb2(level, ipd.GetIdentity()) {
+			return true
+		}
+	}
+
+	if ipdgp, ok := v.(IdentityGroupProvider); ok {
+		if cb2(level, ipdgp.GetIdentityGroup()) {
+			return true
+		}
+	}
+
+	return false
+}
+
+var (
+	_ Identity             = (*orIdentity)(nil)
+	_ compare.ProbablyEqer = (*orIdentity)(nil)
+)
+
+func Or(a, b Identity) Identity {
+	return orIdentity{a: a, b: b}
+}
+
+type orIdentity struct {
+	a, b Identity
+}
+
+func (o orIdentity) IdentifierBase() string {
+	return o.a.IdentifierBase()
+}
+
+func (o orIdentity) ProbablyEq(other any) bool {
+	otherID, ok := other.(Identity)
+	if !ok {
+		return false
+	}
+
+	return probablyEq(o.a, otherID) || probablyEq(o.b, otherID)
+}
+
+func probablyEq(a, b Identity) bool {
+	if a == b {
+		return true
+	}
+
+	if a == Anonymous || b == Anonymous {
+		return false
+	}
+
+	if a.IdentifierBase() == b.IdentifierBase() {
+		return true
+	}
+
+	if a2, ok := a.(IsProbablyDependentProvider); ok {
+		return a2.IsProbablyDependent(b)
+	}
+
+	return false
 }