1package cache
2
3import (
4 "math"
5 "sort"
6 "strings"
7 "sync"
8 "time"
9)
10
11// FuzzySearcher provides high-performance fuzzy search capabilities.
12type FuzzySearcher struct {
13 config *CacheConfig
14 resultPool sync.Pool
15}
16
17// NewFuzzySearcher creates a new fuzzy searcher with the given config.
18func NewFuzzySearcher(config *CacheConfig) *FuzzySearcher {
19 fs := &FuzzySearcher{
20 config: config,
21 }
22
23 // Initialize result pool for zero-allocation queries
24 fs.resultPool = sync.Pool{
25 New: func() interface{} {
26 return &FuzzyResult{
27 Matches: make([]FuzzyMatch, 0, config.MaxResults),
28 }
29 },
30 }
31
32 return fs
33}
34
35// Search performs a fuzzy search on the cache and returns ranked results.
36func (c *DmenuFuzzyCache) Search(query string, config *CacheConfig) *FuzzyResult {
37 if len(query) == 0 {
38 return c.getTopEntries(config)
39 }
40
41 startTime := time.Now()
42
43 // Get result object from pool
44 searcher := NewFuzzySearcher(config)
45 result := searcher.resultPool.Get().(*FuzzyResult)
46 result.Reset()
47
48 c.mu.RLock()
49 defer c.mu.RUnlock()
50
51 // Phase 1: Fast candidate selection using indices
52 candidates := c.getAllCandidates(query)
53
54 // Phase 2: Score candidates using fuzzy algorithms
55 matches := make([]FuzzyMatch, 0, len(candidates))
56
57 if len(candidates) == 0 {
58 // Fallback: search all entries (should be rare)
59 candidates = make([]uint32, len(c.entries))
60 for i := range c.entries {
61 candidates[i] = uint32(i)
62 }
63 }
64
65 // Limit candidates to avoid excessive computation
66 if len(candidates) > 1000 {
67 candidates = candidates[:1000]
68 }
69
70 for _, entryID := range candidates {
71 if int(entryID) >= len(c.entries) {
72 continue
73 }
74
75 match := searcher.scoreEntry(query, &c.entries[entryID])
76 if match.Score >= config.ScoreThreshold {
77 matches = append(matches, match)
78 }
79 }
80
81 // Phase 3: Sort by score and apply limits
82 sort.Slice(matches, func(i, j int) bool {
83 return matches[i].Score > matches[j].Score
84 })
85
86 if len(matches) > config.MaxResults {
87 matches = matches[:config.MaxResults]
88 }
89
90 result.Matches = matches
91 result.QueryTime = time.Since(startTime)
92
93 return result
94}
95
96// getTopEntries returns the top entries when no query is provided.
97func (c *DmenuFuzzyCache) getTopEntries(config *CacheConfig) *FuzzyResult {
98 c.mu.RLock()
99 defer c.mu.RUnlock()
100
101 startTime := time.Now()
102
103 // Use pre-sorted index for O(1) access to top entries
104 maxResults := config.MaxResults
105 if maxResults > len(c.sortedIndex) {
106 maxResults = len(c.sortedIndex)
107 }
108
109 matches := make([]FuzzyMatch, maxResults)
110 for i := 0; i < maxResults; i++ {
111 entryID := c.sortedIndex[i]
112 matches[i] = FuzzyMatch{
113 Entry: &c.entries[entryID],
114 Score: float64(c.entries[entryID].Score) / 65535.0, // Normalize to 0-1
115 RecencyScore: 1.0, // No query, so full recency weight
116 VisitScore: 1.0, // No query, so full visit weight
117 MatchType: MatchTypeExact,
118 }
119 }
120
121 return &FuzzyResult{
122 Matches: matches,
123 QueryTime: time.Since(startTime),
124 }
125}
126
127// scoreEntry calculates the fuzzy match score for a single entry.
128func (fs *FuzzySearcher) scoreEntry(query string, entry *CompactEntry) FuzzyMatch {
129 match := FuzzyMatch{
130 Entry: entry,
131 }
132
133 queryNorm := normalizeText(query)
134 urlNorm := normalizeText(entry.URL)
135 titleNorm := normalizeText(entry.Title)
136
137 // Calculate different types of similarity
138 match.URLScore = fs.calculateTextSimilarity(queryNorm, urlNorm)
139 match.TitleScore = fs.calculateTextSimilarity(queryNorm, titleNorm)
140
141 // Boost exact matches
142 if strings.Contains(urlNorm, queryNorm) {
143 match.URLScore = math.Max(match.URLScore, 0.95)
144 match.MatchType = MatchTypeExact
145 }
146 if strings.Contains(titleNorm, queryNorm) {
147 match.TitleScore = math.Max(match.TitleScore, 0.95)
148 match.MatchType = MatchTypeExact
149 }
150
151 // Boost prefix matches
152 if strings.HasPrefix(urlNorm, queryNorm) {
153 match.URLScore = math.Max(match.URLScore, 0.9)
154 if match.MatchType != MatchTypeExact {
155 match.MatchType = MatchTypePrefix
156 }
157 }
158 if strings.HasPrefix(titleNorm, queryNorm) {
159 match.TitleScore = math.Max(match.TitleScore, 0.9)
160 if match.MatchType != MatchTypeExact {
161 match.MatchType = MatchTypePrefix
162 }
163 }
164
165 // Calculate recency and visit scores
166 match.RecencyScore = fs.calculateRecencyScore(entry.LastVisit)
167 match.VisitScore = fs.calculateVisitScore(entry.VisitCount)
168
169 // Determine final match type if not already set
170 if match.MatchType == 0 {
171 if match.URLScore > 0.7 || match.TitleScore > 0.7 {
172 match.MatchType = MatchTypeFuzzy
173 } else {
174 match.MatchType = MatchTypeTrigram
175 }
176 }
177
178 // Calculate weighted final score
179 match.Score = fs.config.URLWeight*match.URLScore +
180 fs.config.TitleWeight*match.TitleScore +
181 fs.config.RecencyWeight*match.RecencyScore +
182 fs.config.VisitWeight*match.VisitScore
183
184 return match
185}
186
187// calculateTextSimilarity computes similarity between query and text using multiple algorithms.
188func (fs *FuzzySearcher) calculateTextSimilarity(query, text string) float64 {
189 if query == text {
190 return 1.0
191 }
192
193 if len(query) == 0 || len(text) == 0 {
194 return 0.0
195 }
196
197 // Use different algorithms based on text length for optimal performance
198 if len(query) <= 3 {
199 // For short queries, use substring matching
200 return fs.substringSimilarity(query, text)
201 } else if len(query) <= 10 {
202 // For medium queries, use Jaro-Winkler
203 return fs.jaroWinklerSimilarity(query, text)
204 } else {
205 // For long queries, use tokenized matching
206 return fs.tokenizedSimilarity(query, text)
207 }
208}
209
210// substringSimilarity calculates similarity based on substring matches with position weighting.
211func (fs *FuzzySearcher) substringSimilarity(query, text string) float64 {
212 index := strings.Index(text, query)
213 if index == -1 {
214 return 0.0
215 }
216
217 // Base score
218 baseScore := float64(len(query)) / float64(len(text))
219
220 // Position bonus (earlier matches are better)
221 positionBonus := 1.0
222 if index == 0 {
223 positionBonus = 1.5 // Start of string
224 } else if index < len(text)/3 {
225 positionBonus = 1.2 // First third
226 }
227
228 score := baseScore * positionBonus
229 if score > 1.0 {
230 score = 1.0
231 }
232
233 return score
234}
235
236// jaroWinklerSimilarity calculates Jaro-Winkler similarity (optimized version).
237func (fs *FuzzySearcher) jaroWinklerSimilarity(s1, s2 string) float64 {
238 if s1 == s2 {
239 return 1.0
240 }
241
242 len1, len2 := len(s1), len(s2)
243 if len1 == 0 || len2 == 0 {
244 return 0.0
245 }
246
247 // Calculate match window
248 matchWindow := (max(len1, len2) / 2) - 1
249 if matchWindow < 0 {
250 matchWindow = 0
251 }
252
253 matches1 := make([]bool, len1)
254 matches2 := make([]bool, len2)
255 matches := 0
256
257 // Find matches
258 for i := 0; i < len1; i++ {
259 start := max(0, i-matchWindow)
260 end := min(i+matchWindow+1, len2)
261
262 for j := start; j < end; j++ {
263 if matches2[j] || s1[i] != s2[j] {
264 continue
265 }
266 matches1[i] = true
267 matches2[j] = true
268 matches++
269 break
270 }
271 }
272
273 if matches == 0 {
274 return 0.0
275 }
276
277 // Count transpositions
278 transpositions := 0
279 k := 0
280 for i := 0; i < len1; i++ {
281 if !matches1[i] {
282 continue
283 }
284 for !matches2[k] {
285 k++
286 }
287 if s1[i] != s2[k] {
288 transpositions++
289 }
290 k++
291 }
292
293 // Calculate Jaro similarity
294 jaro := (float64(matches)/float64(len1) +
295 float64(matches)/float64(len2) +
296 float64(matches-transpositions/2)/float64(matches)) / 3.0
297
298 // Jaro-Winkler modification
299 if jaro < 0.7 {
300 return jaro
301 }
302
303 // Common prefix (up to 4 characters)
304 prefix := 0
305 for i := 0; i < min(min(len1, len2), 4); i++ {
306 if s1[i] == s2[i] {
307 prefix++
308 } else {
309 break
310 }
311 }
312
313 return jaro + (0.1 * float64(prefix) * (1 - jaro))
314}
315
316// tokenizedSimilarity performs token-based matching for longer texts.
317func (fs *FuzzySearcher) tokenizedSimilarity(query, text string) float64 {
318 queryTokens := strings.Fields(query)
319 textTokens := strings.Fields(text)
320
321 if len(queryTokens) == 0 || len(textTokens) == 0 {
322 return 0.0
323 }
324
325 totalScore := 0.0
326 matchedTokens := 0
327
328 for _, queryToken := range queryTokens {
329 bestScore := 0.0
330 for _, textToken := range textTokens {
331 score := fs.jaroWinklerSimilarity(queryToken, textToken)
332 if score > bestScore {
333 bestScore = score
334 }
335 }
336 if bestScore >= 0.6 { // Token match threshold
337 totalScore += bestScore
338 matchedTokens++
339 }
340 }
341
342 if matchedTokens == 0 {
343 return 0.0
344 }
345
346 // Average score weighted by matched token ratio
347 avgScore := totalScore / float64(matchedTokens)
348 tokenRatio := float64(matchedTokens) / float64(len(queryTokens))
349
350 return avgScore * tokenRatio
351}
352
353// calculateRecencyScore calculates score based on how recently the entry was visited.
354func (fs *FuzzySearcher) calculateRecencyScore(lastVisitDays uint32) float64 {
355 now := time.Now()
356 lastVisit := TimeFromDays(lastVisitDays)
357 daysSince := now.Sub(lastVisit).Hours() / 24
358
359 // Exponential decay over 30 days
360 return math.Exp(-daysSince / 30.0)
361}
362
363// calculateVisitScore calculates score based on visit count with logarithmic scaling.
364func (fs *FuzzySearcher) calculateVisitScore(visitCount uint16) float64 {
365 if visitCount == 0 {
366 return 0.0
367 }
368
369 // Logarithmic scaling to prevent highly visited sites from dominating
370 score := math.Log1p(float64(visitCount)) / math.Log1p(1000.0)
371 if score > 1.0 {
372 score = 1.0
373 }
374
375 return score
376}
377
378// Helper functions
379func max(a, b int) int {
380 if a > b {
381 return a
382 }
383 return b
384}
385
386func min(a, b int) int {
387 if a < b {
388 return a
389 }
390 return b
391}