finder.go - hugo - [fork] hugo port for 9front
HTML git clone https://git.drkhsh.at/hugo.git
DIR Log
DIR Files
DIR Refs
DIR Submodules
DIR README
DIR LICENSE
---
finder.go (6928B)
---
1 // Copyright 2024 The Hugo Authors. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 package identity
15
16 import (
17 "fmt"
18 "sync"
19
20 "github.com/gohugoio/hugo/compare"
21 )
22
23 // NewFinder creates a new Finder.
24 // This is a thread safe implementation with a cache.
25 func NewFinder(cfg FinderConfig) *Finder {
26 return &Finder{cfg: cfg, answers: make(map[ManagerIdentity]FinderResult), seenFindOnce: make(map[Identity]bool)}
27 }
28
29 var searchIDPool = sync.Pool{
30 New: func() any {
31 return &searchID{seen: make(map[Manager]bool)}
32 },
33 }
34
35 func getSearchID() *searchID {
36 return searchIDPool.Get().(*searchID)
37 }
38
39 func putSearchID(sid *searchID) {
40 sid.id = nil
41 sid.isDp = false
42 sid.isPeq = false
43 sid.hasEqer = false
44 sid.maxDepth = 0
45 sid.dp = nil
46 sid.peq = nil
47 sid.eqer = nil
48 clear(sid.seen)
49 searchIDPool.Put(sid)
50 }
51
52 // GetSearchID returns a searchID from the pool.
53
54 // Finder finds identities inside another.
55 type Finder struct {
56 cfg FinderConfig
57
58 answers map[ManagerIdentity]FinderResult
59 muAnswers sync.RWMutex
60
61 seenFindOnce map[Identity]bool
62 muSeenFindOnce sync.RWMutex
63 }
64
65 type FinderResult int
66
67 const (
68 FinderNotFound FinderResult = iota
69 FinderFoundOneOfManyRepetition
70 FinderFoundOneOfMany
71 FinderFound
72 )
73
74 // Contains returns whether in contains id.
75 func (f *Finder) Contains(id, in Identity, maxDepth int) FinderResult {
76 if id == Anonymous || in == Anonymous {
77 return FinderNotFound
78 }
79
80 if id == GenghisKhan && in == GenghisKhan {
81 return FinderNotFound
82 }
83
84 if id == GenghisKhan {
85 return FinderFound
86 }
87
88 if id == in {
89 return FinderFound
90 }
91
92 if id == nil || in == nil {
93 return FinderNotFound
94 }
95
96 var (
97 isDp bool
98 isPeq bool
99
100 dp IsProbablyDependentProvider
101 peq compare.ProbablyEqer
102 )
103
104 if !f.cfg.Exact {
105 dp, isDp = id.(IsProbablyDependentProvider)
106 peq, isPeq = id.(compare.ProbablyEqer)
107 }
108
109 eqer, hasEqer := id.(compare.Eqer)
110
111 sid := getSearchID()
112 sid.id = id
113 sid.isDp = isDp
114 sid.isPeq = isPeq
115 sid.hasEqer = hasEqer
116 sid.dp = dp
117 sid.peq = peq
118 sid.eqer = eqer
119 sid.maxDepth = maxDepth
120
121 defer putSearchID(sid)
122
123 r := FinderNotFound
124 if i := f.checkOne(sid, in, 0); i > r {
125 r = i
126 }
127 if r == FinderFound {
128 return r
129 }
130
131 m := GetDependencyManager(in)
132 if m != nil {
133 if i := f.checkManager(sid, m, 0); i > r {
134 r = i
135 }
136 }
137 return r
138 }
139
140 func (f *Finder) checkMaxDepth(sid *searchID, level int) FinderResult {
141 if sid.maxDepth >= 0 && level > sid.maxDepth {
142 return FinderNotFound
143 }
144 if level > 100 {
145 // This should never happen, but some false positives are probably better than a panic.
146 if !f.cfg.Exact {
147 return FinderFound
148 }
149 panic("too many levels")
150 }
151 return -1
152 }
153
154 func (f *Finder) checkManager(sid *searchID, m Manager, level int) FinderResult {
155 if r := f.checkMaxDepth(sid, level); r >= 0 {
156 return r
157 }
158
159 if m == nil {
160 return FinderNotFound
161 }
162 if sid.seen[m] {
163 return FinderNotFound
164 }
165 sid.seen[m] = true
166
167 f.muAnswers.RLock()
168 r, ok := f.answers[ManagerIdentity{Manager: m, Identity: sid.id}]
169 f.muAnswers.RUnlock()
170 if ok {
171 return r
172 }
173
174 r = f.search(sid, m, level)
175
176 if r == FinderFoundOneOfMany {
177 // Don't cache this one.
178 return r
179 }
180
181 f.muAnswers.Lock()
182 f.answers[ManagerIdentity{Manager: m, Identity: sid.id}] = r
183 f.muAnswers.Unlock()
184
185 return r
186 }
187
188 func (f *Finder) checkOne(sid *searchID, v Identity, depth int) (r FinderResult) {
189 if ff, ok := v.(FindFirstManagerIdentityProvider); ok {
190 f.muSeenFindOnce.RLock()
191 mi := ff.FindFirstManagerIdentity()
192 seen := f.seenFindOnce[mi.Identity]
193 f.muSeenFindOnce.RUnlock()
194 if seen {
195 return FinderFoundOneOfManyRepetition
196 }
197
198 r = f.doCheckOne(sid, mi.Identity, depth)
199 if r == 0 {
200 r = f.checkManager(sid, mi.Manager, depth)
201 }
202
203 if r > FinderFoundOneOfManyRepetition {
204 f.muSeenFindOnce.Lock()
205 // Double check.
206 if f.seenFindOnce[mi.Identity] {
207 f.muSeenFindOnce.Unlock()
208 return FinderFoundOneOfManyRepetition
209 }
210 f.seenFindOnce[mi.Identity] = true
211 f.muSeenFindOnce.Unlock()
212 r = FinderFoundOneOfMany
213 }
214 return r
215 } else {
216 return f.doCheckOne(sid, v, depth)
217 }
218 }
219
220 func (f *Finder) doCheckOne(sid *searchID, v Identity, depth int) FinderResult {
221 id2 := Unwrap(v)
222 if id2 == Anonymous {
223 return FinderNotFound
224 }
225 id := sid.id
226 if sid.hasEqer {
227 if sid.eqer.Eq(id2) {
228 return FinderFound
229 }
230 } else if id == id2 {
231 return FinderFound
232 }
233
234 if f.cfg.Exact {
235 return FinderNotFound
236 }
237
238 if id2 == nil {
239 return FinderNotFound
240 }
241
242 if id2 == GenghisKhan {
243 return FinderFound
244 }
245
246 if id.IdentifierBase() == id2.IdentifierBase() {
247 return FinderFound
248 }
249
250 if sid.isDp && sid.dp.IsProbablyDependent(id2) {
251 return FinderFound
252 }
253
254 if sid.isPeq && sid.peq.ProbablyEq(id2) {
255 return FinderFound
256 }
257
258 if pdep, ok := id2.(IsProbablyDependencyProvider); ok && pdep.IsProbablyDependency(id) {
259 return FinderFound
260 }
261
262 if peq, ok := id2.(compare.ProbablyEqer); ok && peq.ProbablyEq(id) {
263 return FinderFound
264 }
265
266 return FinderNotFound
267 }
268
269 // search searches for id in ids.
270 func (f *Finder) search(sid *searchID, m Manager, depth int) FinderResult {
271 id := sid.id
272
273 if id == Anonymous {
274 return FinderNotFound
275 }
276
277 if !f.cfg.Exact && id == GenghisKhan {
278 return FinderNotFound
279 }
280
281 var r FinderResult
282 m.forEeachIdentity(
283 func(v Identity) bool {
284 i := f.checkOne(sid, v, depth)
285 if i > r {
286 r = i
287 }
288 if r == FinderFound {
289 return true
290 }
291 m := GetDependencyManager(v)
292 if i := f.checkManager(sid, m, depth+1); i > r {
293 r = i
294 }
295 if r == FinderFound {
296 return true
297 }
298 return false
299 },
300 )
301 return r
302 }
303
304 // FinderConfig provides configuration for the Finder.
305 // Note that we by default will use a strategy where probable matches are
306 // good enough. The primary use case for this is to identity the change set
307 // for a given changed identity (e.g. a template), and we don't want to
308 // have any false negatives there, but some false positives are OK. Also, speed is important.
309 type FinderConfig struct {
310 // Match exact matches only.
311 Exact bool
312 }
313
314 // ManagerIdentity wraps a pair of Identity and Manager.
315 type ManagerIdentity struct {
316 Identity
317 Manager
318 }
319
320 func (p ManagerIdentity) String() string {
321 return fmt.Sprintf("%s:%s", p.Identity.IdentifierBase(), p.Manager.IdentifierBase())
322 }
323
324 type searchID struct {
325 id Identity
326 isDp bool
327 isPeq bool
328 hasEqer bool
329
330 maxDepth int
331
332 seen map[Manager]bool
333
334 dp IsProbablyDependentProvider
335 peq compare.ProbablyEqer
336 eqer compare.Eqer
337 }