all: Rework page store, add a dynacache, improve partial rebuilds, and some general spring cleaningdevelop2024

There are some breaking changes in this commit, see #11455.

Closes #11455
Closes #11549

This fixes a set of bugs (see issue list) and it is also paying some technical debt accumulated over the years. We now build with Staticcheck enabled in the CI build.

The performance should be about the same as before for regular sized Hugo sites, but it should perform and scale much better to larger data sets, as objects that uses lots of memory (e.g. rendered Markdown, big JSON files read into maps with transform.Unmarshal etc.) will now get automatically garbage collected if needed. Performance on partial rebuilds when running the server in fast render mode should be the same, but the change detection should be much more accurate.

A list of the notable new features:

* A new dependency tracker that covers (almost) all of Hugo's API and is used to do fine grained partial rebuilds when running the server.
* A new and simpler tree document store which allows fast lookups and prefix-walking in all dimensions (e.g. language) concurrently.
* You can now configure an upper memory limit allowing for much larger data sets and/or running on lower specced PCs.
We have lifted the "no resources in sub folders" restriction for branch bundles (e.g. sections).
Memory Limit
* Hugos will, by default, set aside a quarter of the total system memory, but you can set this via the OS environment variable HUGO_MEMORYLIMIT (in gigabytes). This is backed by a partitioned LRU cache used throughout Hugo. A cache that gets dynamically resized in low memory situations, allowing Go's Garbage Collector to free the memory.

New Dependency Tracker: Hugo has had a rule based coarse grained approach to server rebuilds that has worked mostly pretty well, but there have been some surprises (e.g. stale content). This is now revamped with a new dependency tracker that can quickly calculate the delta given a changed resource (e.g. a content file, template, JS file etc.). This handles transitive relations, e.g. $page -> js.Build -> JS import, or $page1.Content -> render hook -> site.GetPage -> $page2.Title, or $page1.Content -> shortcode -> partial -> site.RegularPages -> $page2.Content -> shortcode ..., and should also handle changes to aggregated values (e.g. site.Lastmod) effectively.

This covers all of Hugo's API with 2 known exceptions (a list that may not be fully exhaustive):

Changes to files loaded with template func os.ReadFile may not be handled correctly. We recommend loading resources with resources.Get
Changes to Hugo objects (e.g. Page) passed in the template context to lang.Translate may not be detected correctly. We recommend having simple i18n templates without too much data context passed in other than simple types such as strings and numbers.
Note that the cachebuster configuration (when A changes then rebuild B) works well with the above, but we recommend that you revise that configuration, as it in most situations should not be needed. One example where it is still needed is with TailwindCSS and using changes to hugo_stats.json to trigger new CSS rebuilds.

Document Store: Previously, a little simplified, we split the document store (where we store pages and resources) in a tree per language. This worked pretty well, but the structure made some operations harder than they needed to be. We have now restructured it into one Radix tree for all languages. Internally the language is considered to be a dimension of that tree, and the tree can be viewed in all dimensions concurrently. This makes some operations re. language simpler (e.g. finding translations is just a slice range), but the idea is that it should also be relatively inexpensive to add more dimensions if needed (e.g. role).

Fixes #10169
Fixes #10364
Fixes #10482
Fixes #10630
Fixes #10656
Fixes #10694
Fixes #10918
Fixes #11262
Fixes #11439
Fixes #11453
Fixes #11457
Fixes #11466
Fixes #11540
Fixes #11551
Fixes #11556
Fixes #11654
Fixes #11661
Fixes #11663
Fixes #11664
Fixes #11669
Fixes #11671
Fixes #11807
Fixes #11808
Fixes #11809
Fixes #11815
Fixes #11840
Fixes #11853
Fixes #11860
Fixes #11883
Fixes #11904
Fixes #7388
Fixes #7425
Fixes #7436
Fixes #7544
Fixes #7882
Fixes #7960
Fixes #8255
Fixes #8307
Fixes #8863
Fixes #8927
Fixes #9192
Fixes #9324

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.