aboutsummaryrefslogtreecommitdiffhomepage
path: root/identity
diff options
context:
space:
mode:
Diffstat (limited to 'identity')
-rw-r--r--identity/finder.go336
-rw-r--r--identity/finder_test.go58
-rw-r--r--identity/identity.go504
-rw-r--r--identity/identity_test.go192
-rw-r--r--identity/identityhash.go6
-rw-r--r--identity/identityhash_test.go3
-rw-r--r--identity/identitytesting/identitytesting.go5
-rw-r--r--identity/predicate_identity.go78
-rw-r--r--identity/predicate_identity_test.go58
-rw-r--r--identity/question.go57
-rw-r--r--identity/question_test.go38
11 files changed, 1200 insertions, 135 deletions
diff --git a/identity/finder.go b/identity/finder.go
new file mode 100644
index 000000000..bd23d698e
--- /dev/null
+++ b/identity/finder.go
@@ -0,0 +1,336 @@
+// 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.
+// 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 identity
+
+import (
+ "fmt"
+ "sync"
+
+ "github.com/gohugoio/hugo/compare"
+)
+
+// NewFinder creates a new Finder.
+// This is a thread safe implementation with a cache.
+func NewFinder(cfg FinderConfig) *Finder {
+ return &Finder{cfg: cfg, answers: make(map[ManagerIdentity]FinderResult), seenFindOnce: make(map[Identity]bool)}
+}
+
+var searchIDPool = sync.Pool{
+ New: func() interface{} {
+ return &searchID{seen: make(map[Manager]bool)}
+ },
+}
+
+func getSearchID() *searchID {
+ return searchIDPool.Get().(*searchID)
+}
+
+func putSearchID(sid *searchID) {
+ sid.id = nil
+ sid.isDp = false
+ sid.isPeq = false
+ sid.hasEqer = false
+ sid.maxDepth = 0
+ sid.dp = nil
+ sid.peq = nil
+ sid.eqer = nil
+ for k := range sid.seen {
+ delete(sid.seen, k)
+ }
+ searchIDPool.Put(sid)
+}
+
+// GetSearchID returns a searchID from the pool.
+
+// Finder finds identities inside another.
+type Finder struct {
+ cfg FinderConfig
+
+ answers map[ManagerIdentity]FinderResult
+ muAnswers sync.RWMutex
+
+ seenFindOnce map[Identity]bool
+ muSeenFindOnce sync.RWMutex
+}
+
+type FinderResult int
+
+const (
+ FinderNotFound FinderResult = iota
+ FinderFoundOneOfManyRepetition
+ FinderFoundOneOfMany
+ FinderFound
+)
+
+// Contains returns whether in contains id.
+func (f *Finder) Contains(id, in Identity, maxDepth int) FinderResult {
+ if id == Anonymous || in == Anonymous {
+ return FinderNotFound
+ }
+
+ if id == GenghisKhan && in == GenghisKhan {
+ return FinderNotFound
+ }
+
+ if id == GenghisKhan {
+ return FinderFound
+ }
+
+ if id == in {
+ return FinderFound
+ }
+
+ if id == nil || in == nil {
+ return FinderNotFound
+ }
+
+ var (
+ isDp bool
+ isPeq bool
+
+ dp IsProbablyDependentProvider
+ peq compare.ProbablyEqer
+ )
+
+ if !f.cfg.Exact {
+ dp, isDp = id.(IsProbablyDependentProvider)
+ peq, isPeq = id.(compare.ProbablyEqer)
+ }
+
+ eqer, hasEqer := id.(compare.Eqer)
+
+ sid := getSearchID()
+ sid.id = id
+ sid.isDp = isDp
+ sid.isPeq = isPeq
+ sid.hasEqer = hasEqer
+ sid.dp = dp
+ sid.peq = peq
+ sid.eqer = eqer
+ sid.maxDepth = maxDepth
+
+ defer putSearchID(sid)
+
+ if r := f.checkOne(sid, in, 0); r > 0 {
+ return r
+ }
+
+ m := GetDependencyManager(in)
+ if m != nil {
+ if r := f.checkManager(sid, m, 0); r > 0 {
+ return r
+ }
+ }
+ return FinderNotFound
+}
+
+func (f *Finder) checkMaxDepth(sid *searchID, level int) FinderResult {
+ if sid.maxDepth >= 0 && level > sid.maxDepth {
+ return FinderNotFound
+ }
+ if level > 100 {
+ // This should never happen, but some false positives are probably better than a panic.
+ if !f.cfg.Exact {
+ return FinderFound
+ }
+ panic("too many levels")
+ }
+ return -1
+}
+
+func (f *Finder) checkManager(sid *searchID, m Manager, level int) FinderResult {
+ if r := f.checkMaxDepth(sid, level); r >= 0 {
+ return r
+ }
+
+ if m == nil {
+ return FinderNotFound
+ }
+ if sid.seen[m] {
+ return FinderNotFound
+ }
+ sid.seen[m] = true
+
+ f.muAnswers.RLock()
+ r, ok := f.answers[ManagerIdentity{Manager: m, Identity: sid.id}]
+ f.muAnswers.RUnlock()
+ if ok {
+ return r
+ }
+
+ ids := m.getIdentities()
+ if len(ids) == 0 {
+ r = FinderNotFound
+ } else {
+ r = f.search(sid, ids, level)
+ }
+
+ if r == FinderFoundOneOfMany {
+ // Don't cache this one.
+ return r
+ }
+
+ f.muAnswers.Lock()
+ f.answers[ManagerIdentity{Manager: m, Identity: sid.id}] = r
+ f.muAnswers.Unlock()
+
+ return r
+}
+
+func (f *Finder) checkOne(sid *searchID, v Identity, depth int) (r FinderResult) {
+ if ff, ok := v.(FindFirstManagerIdentityProvider); ok {
+ f.muSeenFindOnce.RLock()
+ mi := ff.FindFirstManagerIdentity()
+ seen := f.seenFindOnce[mi.Identity]
+ f.muSeenFindOnce.RUnlock()
+ if seen {
+ return FinderFoundOneOfManyRepetition
+ }
+
+ r = f.doCheckOne(sid, mi.Identity, depth)
+ if r == 0 {
+ r = f.checkManager(sid, mi.Manager, depth)
+ }
+
+ if r > FinderFoundOneOfManyRepetition {
+ f.muSeenFindOnce.Lock()
+ // Double check.
+ if f.seenFindOnce[mi.Identity] {
+ f.muSeenFindOnce.Unlock()
+ return FinderFoundOneOfManyRepetition
+ }
+ f.seenFindOnce[mi.Identity] = true
+ f.muSeenFindOnce.Unlock()
+ r = FinderFoundOneOfMany
+ }
+ return r
+ } else {
+ return f.doCheckOne(sid, v, depth)
+ }
+}
+
+func (f *Finder) doCheckOne(sid *searchID, v Identity, depth int) FinderResult {
+ id2 := Unwrap(v)
+ if id2 == Anonymous {
+ return FinderNotFound
+ }
+ id := sid.id
+ if sid.hasEqer {
+ if sid.eqer.Eq(id2) {
+ return FinderFound
+ }
+ } else if id == id2 {
+ return FinderFound
+ }
+
+ if f.cfg.Exact {
+ return FinderNotFound
+ }
+
+ if id2 == nil {
+ return FinderNotFound
+ }
+
+ if id2 == GenghisKhan {
+ return FinderFound
+ }
+
+ if id.IdentifierBase() == id2.IdentifierBase() {
+ return FinderFound
+ }
+
+ if sid.isDp && sid.dp.IsProbablyDependent(id2) {
+ return FinderFound
+ }
+
+ if sid.isPeq && sid.peq.ProbablyEq(id2) {
+ return FinderFound
+ }
+
+ if pdep, ok := id2.(IsProbablyDependencyProvider); ok && pdep.IsProbablyDependency(id) {
+ return FinderFound
+ }
+
+ if peq, ok := id2.(compare.ProbablyEqer); ok && peq.ProbablyEq(id) {
+ return FinderFound
+ }
+
+ return FinderNotFound
+}
+
+// search searches for id in ids.
+func (f *Finder) search(sid *searchID, ids Identities, depth int) FinderResult {
+ if len(ids) == 0 {
+ return FinderNotFound
+ }
+
+ id := sid.id
+
+ if id == Anonymous {
+ return FinderNotFound
+ }
+
+ if !f.cfg.Exact && id == GenghisKhan {
+ return FinderNotFound
+ }
+
+ for v := range ids {
+ r := f.checkOne(sid, v, depth)
+ if r > 0 {
+ return r
+ }
+
+ m := GetDependencyManager(v)
+ if r := f.checkManager(sid, m, depth+1); r > 0 {
+ return r
+ }
+ }
+
+ return FinderNotFound
+}
+
+// FinderConfig provides configuration for the Finder.
+// Note that we by default will use a strategy where probable matches are
+// good enough. The primary use case for this is to identity the change set
+// for a given changed identity (e.g. a template), and we don't want to
+// have any false negatives there, but some false positives are OK. Also, speed is important.
+type FinderConfig struct {
+ // Match exact matches only.
+ Exact bool
+}
+
+// ManagerIdentity wraps a pair of Identity and Manager.
+type ManagerIdentity struct {
+ Identity
+ Manager
+}
+
+func (p ManagerIdentity) String() string {
+ return fmt.Sprintf("%s:%s", p.Identity.IdentifierBase(), p.Manager.IdentifierBase())
+}
+
+type searchID struct {
+ id Identity
+ isDp bool
+ isPeq bool
+ hasEqer bool
+
+ maxDepth int
+
+ seen map[Manager]bool
+
+ dp IsProbablyDependentProvider
+ peq compare.ProbablyEqer
+ eqer compare.Eqer
+}
diff --git a/identity/finder_test.go b/identity/finder_test.go
new file mode 100644
index 000000000..abfab9d75
--- /dev/null
+++ b/identity/finder_test.go
@@ -0,0 +1,58 @@
+// 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.
+// 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 provides ways to identify values in Hugo. Used for dependency tracking etc.
+package identity_test
+
+import (
+ "testing"
+
+ "github.com/gohugoio/hugo/identity"
+)
+
+func BenchmarkFinder(b *testing.B) {
+ m1 := identity.NewManager("")
+ m2 := identity.NewManager("")
+ m3 := identity.NewManager("")
+ m1.AddIdentity(
+ testIdentity{"base", "id1", "", "pe1"},
+ testIdentity{"base2", "id2", "eq1", ""},
+ m2,
+ m3,
+ )
+
+ b4 := testIdentity{"base4", "id4", "", ""}
+ b5 := testIdentity{"base5", "id5", "", ""}
+
+ m2.AddIdentity(b4)
+
+ f := identity.NewFinder(identity.FinderConfig{})
+
+ b.Run("Find one", func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ r := f.Contains(b4, m1, -1)
+ if r == 0 {
+ b.Fatal("not found")
+ }
+ }
+ })
+
+ b.Run("Find none", func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ r := f.Contains(b5, m1, -1)
+ if r > 0 {
+ b.Fatal("found")
+ }
+ }
+ })
+}
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
}
diff --git a/identity/identity_test.go b/identity/identity_test.go
index baf2628bb..d003caaf0 100644
--- a/identity/identity_test.go
+++ b/identity/identity_test.go
@@ -1,4 +1,4 @@
-// Copyright 2019 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,79 +11,201 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-package identity
+package identity_test
import (
"fmt"
- "math/rand"
- "strconv"
"testing"
qt "github.com/frankban/quicktest"
+ "github.com/gohugoio/hugo/identity"
+ "github.com/gohugoio/hugo/identity/identitytesting"
)
-func TestIdentityManager(t *testing.T) {
- c := qt.New(t)
-
- id1 := testIdentity{name: "id1"}
- im := NewManager(id1)
-
- c.Assert(im.Search(id1).GetIdentity(), qt.Equals, id1)
- c.Assert(im.Search(testIdentity{name: "notfound"}), qt.Equals, nil)
-}
-
func BenchmarkIdentityManager(b *testing.B) {
- createIds := func(num int) []Identity {
- ids := make([]Identity, num)
+ createIds := func(num int) []identity.Identity {
+ ids := make([]identity.Identity, num)
for i := 0; i < num; i++ {
- ids[i] = testIdentity{name: fmt.Sprintf("id%d", i)}
+ name := fmt.Sprintf("id%d", i)
+ ids[i] = &testIdentity{base: name, name: name}
}
return ids
}
- b.Run("Add", func(b *testing.B) {
- c := qt.New(b)
- b.StopTimer()
+ b.Run("identity.NewManager", func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ m := identity.NewManager("")
+ if m == nil {
+ b.Fatal("manager is nil")
+ }
+ }
+ })
+
+ b.Run("Add unique", func(b *testing.B) {
ids := createIds(b.N)
- im := NewManager(testIdentity{"first"})
- b.StartTimer()
+ im := identity.NewManager("")
+ b.ResetTimer()
for i := 0; i < b.N; i++ {
- im.Add(ids[i])
+ im.AddIdentity(ids[i])
}
b.StopTimer()
- c.Assert(im.GetIdentities(), qt.HasLen, b.N+1)
})
- b.Run("Search", func(b *testing.B) {
- c := qt.New(b)
+ b.Run("Add duplicates", func(b *testing.B) {
+ id := &testIdentity{base: "a", name: "b"}
+ im := identity.NewManager("")
+
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ im.AddIdentity(id)
+ }
+
b.StopTimer()
- ids := createIds(b.N)
- im := NewManager(testIdentity{"first"})
+ })
+
+ b.Run("Nop StringIdentity const", func(b *testing.B) {
+ const id = identity.StringIdentity("test")
+ for i := 0; i < b.N; i++ {
+ identity.NopManager.AddIdentity(id)
+ }
+ })
+
+ b.Run("Nop StringIdentity const other package", func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ identity.NopManager.AddIdentity(identitytesting.TestIdentity)
+ }
+ })
+
+ b.Run("Nop StringIdentity var", func(b *testing.B) {
+ id := identity.StringIdentity("test")
+ for i := 0; i < b.N; i++ {
+ identity.NopManager.AddIdentity(id)
+ }
+ })
+ b.Run("Nop pointer identity", func(b *testing.B) {
+ id := &testIdentity{base: "a", name: "b"}
for i := 0; i < b.N; i++ {
- im.Add(ids[i])
+ identity.NopManager.AddIdentity(id)
}
+ })
- b.StartTimer()
+ b.Run("Nop Anonymous", func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ identity.NopManager.AddIdentity(identity.Anonymous)
+ }
+ })
+}
+func BenchmarkIsNotDependent(b *testing.B) {
+ runBench := func(b *testing.B, id1, id2 identity.Identity) {
for i := 0; i < b.N; i++ {
- name := "id" + strconv.Itoa(rand.Intn(b.N))
- id := im.Search(testIdentity{name: name})
- c.Assert(id.GetIdentity().Name(), qt.Equals, name)
+ isNotDependent(id1, id2)
+ }
+ }
+
+ newNestedManager := func(depth, count int) identity.Manager {
+ m1 := identity.NewManager("")
+ for i := 0; i < depth; i++ {
+ m2 := identity.NewManager("")
+ m1.AddIdentity(m2)
+ for j := 0; j < count; j++ {
+ id := fmt.Sprintf("id%d", j)
+ m2.AddIdentity(&testIdentity{id, id, "", ""})
+ }
+ m1 = m2
}
+ return m1
+ }
+
+ type depthCount struct {
+ depth int
+ count int
+ }
+
+ for _, dc := range []depthCount{{10, 5}} {
+ b.Run(fmt.Sprintf("Nested not found %d %d", dc.depth, dc.count), func(b *testing.B) {
+ im := newNestedManager(dc.depth, dc.count)
+ id1 := identity.StringIdentity("idnotfound")
+ b.ResetTimer()
+ runBench(b, im, id1)
+ })
+ }
+}
+
+func TestIdentityManager(t *testing.T) {
+ c := qt.New(t)
+
+ newNestedManager := func() identity.Manager {
+ m1 := identity.NewManager("")
+ m2 := identity.NewManager("")
+ m3 := identity.NewManager("")
+ m1.AddIdentity(
+ testIdentity{"base", "id1", "", "pe1"},
+ testIdentity{"base2", "id2", "eq1", ""},
+ m2,
+ m3,
+ )
+
+ m2.AddIdentity(testIdentity{"base4", "id4", "", ""})
+
+ return m1
+ }
+
+ c.Run("Anonymous", func(c *qt.C) {
+ im := newNestedManager()
+ c.Assert(im.GetIdentity(), qt.Equals, identity.Anonymous)
+ im.AddIdentity(identity.Anonymous)
+ c.Assert(isNotDependent(identity.Anonymous, identity.Anonymous), qt.IsTrue)
+ })
+
+ c.Run("GenghisKhan", func(c *qt.C) {
+ c.Assert(isNotDependent(identity.GenghisKhan, identity.GenghisKhan), qt.IsTrue)
})
}
type testIdentity struct {
+ base string
name string
+
+ idEq string
+ idProbablyEq string
+}
+
+func (id testIdentity) Eq(other any) bool {
+ ot, ok := other.(testIdentity)
+ if !ok {
+ return false
+ }
+ if ot.idEq == "" || id.idEq == "" {
+ return false
+ }
+ return ot.idEq == id.idEq
}
-func (id testIdentity) GetIdentity() Identity {
- return id
+func (id testIdentity) IdentifierBase() string {
+ return id.base
}
func (id testIdentity) Name() string {
return id.name
}
+
+func (id testIdentity) ProbablyEq(other any) bool {
+ ot, ok := other.(testIdentity)
+ if !ok {
+ return false
+ }
+ if ot.idProbablyEq == "" || id.idProbablyEq == "" {
+ return false
+ }
+ return ot.idProbablyEq == id.idProbablyEq
+}
+
+func isNotDependent(a, b identity.Identity) bool {
+ f := identity.NewFinder(identity.FinderConfig{})
+ r := f.Contains(b, a, -1)
+ return r == 0
+}
diff --git a/identity/identityhash.go b/identity/identityhash.go
index ef7b5afa7..8760ff64d 100644
--- a/identity/identityhash.go
+++ b/identity/identityhash.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.
@@ -59,10 +59,10 @@ type keyer interface {
// so rewrite the input slice for known identity types.
func toHashable(v any) any {
switch t := v.(type) {
- case Provider:
- return t.GetIdentity()
case keyer:
return t.Key()
+ case IdentityProvider:
+ return t.GetIdentity()
default:
return v
}
diff --git a/identity/identityhash_test.go b/identity/identityhash_test.go
index 378c0160d..1ecaf7612 100644
--- a/identity/identityhash_test.go
+++ b/identity/identityhash_test.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.
@@ -29,7 +29,6 @@ func TestHashString(t *testing.T) {
c.Assert(HashString(vals...), qt.Equals, "12599484872364427450")
c.Assert(vals[2], qt.Equals, tstKeyer{"c"})
-
}
type tstKeyer struct {
diff --git a/identity/identitytesting/identitytesting.go b/identity/identitytesting/identitytesting.go
new file mode 100644
index 000000000..74f3ec540
--- /dev/null
+++ b/identity/identitytesting/identitytesting.go
@@ -0,0 +1,5 @@
+package identitytesting
+
+import "github.com/gohugoio/hugo/identity"
+
+const TestIdentity = identity.StringIdentity("__testIdentity")
diff --git a/identity/predicate_identity.go b/identity/predicate_identity.go
new file mode 100644
index 000000000..bad247867
--- /dev/null
+++ b/identity/predicate_identity.go
@@ -0,0 +1,78 @@
+// 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.
+// 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 provides ways to identify values in Hugo. Used for dependency tracking etc.
+package identity
+
+import (
+ "fmt"
+ "sync/atomic"
+
+ hglob "github.com/gohugoio/hugo/hugofs/glob"
+)
+
+// NewGlobIdentity creates a new Identity that
+// is probably dependent on any other Identity
+// that matches the given pattern.
+func NewGlobIdentity(pattern string) Identity {
+ glob, err := hglob.GetGlob(pattern)
+ if err != nil {
+ panic(err)
+ }
+
+ predicate := func(other Identity) bool {
+ return glob.Match(other.IdentifierBase())
+ }
+
+ return NewPredicateIdentity(predicate, nil)
+}
+
+var predicateIdentityCounter = &atomic.Uint32{}
+
+type predicateIdentity struct {
+ id string
+ probablyDependent func(Identity) bool
+ probablyDependency func(Identity) bool
+}
+
+var (
+ _ IsProbablyDependencyProvider = &predicateIdentity{}
+ _ IsProbablyDependentProvider = &predicateIdentity{}
+)
+
+// NewPredicateIdentity creates a new Identity that implements both IsProbablyDependencyProvider and IsProbablyDependentProvider
+// using the provided functions, both of which are optional.
+func NewPredicateIdentity(
+ probablyDependent func(Identity) bool,
+ probablyDependency func(Identity) bool,
+) *predicateIdentity {
+ if probablyDependent == nil {
+ probablyDependent = func(Identity) bool { return false }
+ }
+ if probablyDependency == nil {
+ probablyDependency = func(Identity) bool { return false }
+ }
+ return &predicateIdentity{probablyDependent: probablyDependent, probablyDependency: probablyDependency, id: fmt.Sprintf("predicate%d", predicateIdentityCounter.Add(1))}
+}
+
+func (id *predicateIdentity) IdentifierBase() string {
+ return id.id
+}
+
+func (id *predicateIdentity) IsProbablyDependent(other Identity) bool {
+ return id.probablyDependent(other)
+}
+
+func (id *predicateIdentity) IsProbablyDependency(other Identity) bool {
+ return id.probablyDependency(other)
+}
diff --git a/identity/predicate_identity_test.go b/identity/predicate_identity_test.go
new file mode 100644
index 000000000..3a54dee75
--- /dev/null
+++ b/identity/predicate_identity_test.go
@@ -0,0 +1,58 @@
+// 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.
+// 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 provides ways to identify values in Hugo. Used for dependency tracking etc.
+package identity
+
+import (
+ "testing"
+
+ qt "github.com/frankban/quicktest"
+)
+
+func TestGlobIdentity(t *testing.T) {
+ c := qt.New(t)
+
+ gid := NewGlobIdentity("/a/b/*")
+
+ c.Assert(isNotDependent(gid, StringIdentity("/a/b/c")), qt.IsFalse)
+ c.Assert(isNotDependent(gid, StringIdentity("/a/c/d")), qt.IsTrue)
+ c.Assert(isNotDependent(StringIdentity("/a/b/c"), gid), qt.IsTrue)
+ c.Assert(isNotDependent(StringIdentity("/a/c/d"), gid), qt.IsTrue)
+}
+
+func isNotDependent(a, b Identity) bool {
+ f := NewFinder(FinderConfig{})
+ r := f.Contains(a, b, -1)
+ return r == 0
+}
+
+func TestPredicateIdentity(t *testing.T) {
+ c := qt.New(t)
+
+ isDependent := func(id Identity) bool {
+ return id.IdentifierBase() == "foo"
+ }
+ isDependency := func(id Identity) bool {
+ return id.IdentifierBase() == "baz"
+ }
+
+ id := NewPredicateIdentity(isDependent, isDependency)
+
+ c.Assert(id.IsProbablyDependent(StringIdentity("foo")), qt.IsTrue)
+ c.Assert(id.IsProbablyDependent(StringIdentity("bar")), qt.IsFalse)
+ c.Assert(id.IsProbablyDependent(id), qt.IsFalse)
+ c.Assert(id.IsProbablyDependent(NewPredicateIdentity(isDependent, nil)), qt.IsFalse)
+ c.Assert(id.IsProbablyDependency(StringIdentity("baz")), qt.IsTrue)
+ c.Assert(id.IsProbablyDependency(StringIdentity("foo")), qt.IsFalse)
+}
diff --git a/identity/question.go b/identity/question.go
new file mode 100644
index 000000000..78fcb8234
--- /dev/null
+++ b/identity/question.go
@@ -0,0 +1,57 @@
+// 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.
+// 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 identity
+
+import "sync"
+
+// NewQuestion creates a new question with the given identity.
+func NewQuestion[T any](id Identity) *Question[T] {
+ return &Question[T]{
+ Identity: id,
+ }
+}
+
+// Answer takes a func that knows the answer.
+// Note that this is a one-time operation,
+// fn will not be invoked again it the question is already answered.
+// Use Result to check if the question is answered.
+func (q *Question[T]) Answer(fn func() T) {
+ q.mu.Lock()
+ defer q.mu.Unlock()
+
+ if q.answered {
+ return
+ }
+
+ q.fasit = fn()
+ q.answered = true
+}
+
+// Result returns the fasit of the question (if answered),
+// and a bool indicating if the question has been answered.
+func (q *Question[T]) Result() (any, bool) {
+ q.mu.RLock()
+ defer q.mu.RUnlock()
+
+ return q.fasit, q.answered
+}
+
+// A Question is defined by its Identity and can be answered once.
+type Question[T any] struct {
+ Identity
+ fasit T
+
+ mu sync.RWMutex
+ answered bool
+}
diff --git a/identity/question_test.go b/identity/question_test.go
new file mode 100644
index 000000000..bf1e1d06d
--- /dev/null
+++ b/identity/question_test.go
@@ -0,0 +1,38 @@
+// 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.
+// 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 identity
+
+import (
+ "testing"
+
+ qt "github.com/frankban/quicktest"
+)
+
+func TestQuestion(t *testing.T) {
+ c := qt.New(t)
+
+ q := NewQuestion[int](StringIdentity("2+2?"))
+
+ v, ok := q.Result()
+ c.Assert(ok, qt.Equals, false)
+ c.Assert(v, qt.Equals, 0)
+
+ q.Answer(func() int {
+ return 4
+ })
+
+ v, ok = q.Result()
+ c.Assert(ok, qt.Equals, true)
+ c.Assert(v, qt.Equals, 4)
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-26 12:32:23 +0000