1package cache
2
3import (
4 "context"
5 "database/sql"
6 "os"
7 "path/filepath"
8 "testing"
9 "time"
10
11 mock_cache "github.com/bnema/dumber/internal/cache/mocks"
12 "github.com/bnema/dumber/internal/db"
13 "github.com/golang/mock/gomock"
14)
15
16func createTestHistory() []db.History {
17 now := time.Now()
18 return []db.History{
19 {
20 ID: 1,
21 Url: "https://github.com",
22 Title: sql.NullString{String: "GitHub", Valid: true},
23 VisitCount: sql.NullInt64{Int64: 25, Valid: true},
24 LastVisited: sql.NullTime{Time: now.Add(-1 * time.Hour), Valid: true},
25 },
26 {
27 ID: 2,
28 Url: "https://stackoverflow.com",
29 Title: sql.NullString{String: "Stack Overflow", Valid: true},
30 VisitCount: sql.NullInt64{Int64: 15, Valid: true},
31 LastVisited: sql.NullTime{Time: now.Add(-2 * time.Hour), Valid: true},
32 },
33 {
34 ID: 3,
35 Url: "https://golang.org",
36 Title: sql.NullString{String: "The Go Programming Language", Valid: true},
37 VisitCount: sql.NullInt64{Int64: 8, Valid: true},
38 LastVisited: sql.NullTime{Time: now.Add(-5 * time.Hour), Valid: true},
39 },
40 {
41 ID: 4,
42 Url: "https://news.ycombinator.com",
43 Title: sql.NullString{String: "Hacker News", Valid: true},
44 VisitCount: sql.NullInt64{Int64: 30, Valid: true},
45 LastVisited: sql.NullTime{Time: now.Add(-30 * time.Minute), Valid: true},
46 },
47 {
48 ID: 5,
49 Url: "https://youtube.com",
50 Title: sql.NullString{String: "YouTube", Valid: true},
51 VisitCount: sql.NullInt64{Int64: 50, Valid: true},
52 LastVisited: sql.NullTime{Time: now.Add(-10 * time.Minute), Valid: true},
53 },
54 }
55}
56
57func TestCacheManager_BuildCache(t *testing.T) {
58 ctrl := gomock.NewController(t)
59 defer ctrl.Finish()
60
61 mockQuerier := mock_cache.NewMockHistoryQuerier(ctrl)
62 history := createTestHistory()
63
64 // Mock both calls - one for building cache, one for calculating hash
65 mockQuerier.EXPECT().GetHistory(gomock.Any(), int64(10000)).Return(history, nil)
66 mockQuerier.EXPECT().GetHistory(gomock.Any(), int64(20)).Return(history, nil)
67
68 tempDir, err := os.MkdirTemp("", "dumber_cache_test")
69 if err != nil {
70 t.Fatalf("Failed to create temp dir: %v", err)
71 }
72 defer func() {
73 if err := os.RemoveAll(tempDir); err != nil {
74 t.Logf("Warning: failed to remove temp dir %s: %v", tempDir, err)
75 }
76 }()
77
78 config := DefaultCacheConfig()
79 config.CacheFile = filepath.Join(tempDir, "test_cache.bin")
80 config.MaxResults = 10
81
82 manager := NewCacheManager(mockQuerier, config)
83 ctx := context.Background()
84
85 // Test cache building
86 cache, err := manager.GetCache(ctx)
87 if err != nil {
88 t.Fatalf("Failed to get cache: %v", err)
89 }
90
91 if cache.entryCount != 5 {
92 t.Errorf("Expected 5 entries, got %d", cache.entryCount)
93 }
94
95 // Test that indices are built
96 if len(cache.trigramIndex) == 0 {
97 t.Error("Trigram index should not be empty")
98 }
99
100 if cache.prefixTrie == nil || cache.prefixTrie.Root == nil {
101 t.Error("Prefix trie should be initialized")
102 }
103}
104
105// validateSimilarityScore is a helper function to validate similarity scores
106func validateSimilarityScore(t *testing.T, result, expected, delta float64, testName string) {
107 if result < 0.0 || result > 1.0 {
108 t.Errorf("Score %f should be between 0.0 and 1.0", result)
109 }
110
111 diff := result - expected
112 if diff < 0 {
113 diff = -diff
114 }
115 if diff > delta {
116 t.Errorf("%s: Expected %f ±%f, got %f", testName, expected, delta, result)
117 }
118}
119
120func TestFuzzySearcher_JaroWinklerSimilarity(t *testing.T) {
121 config := DefaultCacheConfig()
122 searcher := NewFuzzySearcher(config)
123
124 tests := []struct {
125 name string
126 s1 string
127 s2 string
128 expected float64
129 delta float64
130 }{
131 {"identical strings", "test", "test", 1.0, 0.0},
132 {"empty strings", "", "", 1.0, 0.0},
133 {"one empty", "", "test", 0.0, 0.0},
134 {"similar strings", "github", "gihub", 0.88, 0.1},
135 {"different strings", "github", "stackoverflow", 0.41, 0.05},
136 {"prefix match", "programming", "program", 0.9, 0.1},
137 }
138
139 for _, tt := range tests {
140 t.Run(tt.name, func(t *testing.T) {
141 result := searcher.jaroWinklerSimilarity(tt.s1, tt.s2)
142 validateSimilarityScore(t, result, tt.expected, tt.delta, tt.name)
143 })
144 }
145}
146
147func TestFuzzySearcher_SubstringSimilarity(t *testing.T) {
148 config := DefaultCacheConfig()
149 searcher := NewFuzzySearcher(config)
150
151 tests := []struct {
152 name string
153 query string
154 text string
155 expected float64
156 delta float64
157 }{
158 {"exact match", "github", "github", 1.0, 0.0},
159 {"substring at start", "git", "github.com", 0.45, 0.2},
160 {"substring at end", "com", "github.com", 0.3, 0.1},
161 {"no match", "xyz", "github.com", 0.0, 0.0},
162 {"empty query", "", "github.com", 0.0, 0.0},
163 {"empty text", "git", "", 0.0, 0.0},
164 }
165
166 for _, tt := range tests {
167 t.Run(tt.name, func(t *testing.T) {
168 result := searcher.substringSimilarity(tt.query, tt.text)
169 validateSimilarityScore(t, result, tt.expected, tt.delta, tt.name)
170 })
171 }
172}
173
174func TestFuzzySearcher_TokenizedSimilarity(t *testing.T) {
175 config := DefaultCacheConfig()
176 searcher := NewFuzzySearcher(config)
177
178 tests := []struct {
179 name string
180 query string
181 text string
182 expected float64
183 delta float64
184 }{
185 {"exact token match", "go programming", "The Go Programming Language", 0.8, 0.2},
186 {"partial token match", "stack overflow", "Stack Overflow Questions", 0.8, 0.2},
187 {"no token match", "python django", "JavaScript React Framework", 0.0, 0.1},
188 {"single token", "github", "GitHub Repository", 0.78, 0.05},
189 }
190
191 for _, tt := range tests {
192 t.Run(tt.name, func(t *testing.T) {
193 result := searcher.tokenizedSimilarity(tt.query, tt.text)
194
195 if result < 0.0 || result > 1.0 {
196 t.Errorf("Score %f should be between 0.0 and 1.0", result)
197 }
198
199 diff := result - tt.expected
200 if diff < 0 {
201 diff = -diff
202 }
203 if diff > tt.delta {
204 t.Errorf("Expected %f ±%f, got %f", tt.expected, tt.delta, result)
205 }
206 })
207 }
208}
209
210func TestFuzzySearcher_RecencyScore(t *testing.T) {
211 config := DefaultCacheConfig()
212 searcher := NewFuzzySearcher(config)
213
214 now := time.Now()
215 tests := []struct {
216 name string
217 lastVisitDays uint32
218 expected float64
219 delta float64
220 }{
221 {"recent visit", DaysFromTime(now.Add(-1 * time.Hour)), 0.95, 0.1},
222 {"one day ago", DaysFromTime(now.Add(-24 * time.Hour)), 0.88, 0.1},
223 {"one week ago", DaysFromTime(now.Add(-7 * 24 * time.Hour)), 0.7, 0.1},
224 {"one month ago", DaysFromTime(now.Add(-30 * 24 * time.Hour)), 0.37, 0.1},
225 {"very old", DaysFromTime(now.Add(-365 * 24 * time.Hour)), 0.01, 0.01},
226 }
227
228 for _, tt := range tests {
229 t.Run(tt.name, func(t *testing.T) {
230 result := searcher.calculateRecencyScore(tt.lastVisitDays)
231
232 if result < 0.0 || result > 1.0 {
233 t.Errorf("Score %f should be between 0.0 and 1.0", result)
234 }
235
236 diff := result - tt.expected
237 if diff < 0 {
238 diff = -diff
239 }
240 if diff > tt.delta {
241 t.Errorf("Expected %f ±%f, got %f", tt.expected, tt.delta, result)
242 }
243 })
244 }
245}
246
247func TestFuzzySearcher_VisitScore(t *testing.T) {
248 config := DefaultCacheConfig()
249 searcher := NewFuzzySearcher(config)
250
251 tests := []struct {
252 name string
253 visitCount uint16
254 expected float64
255 delta float64
256 }{
257 {"zero visits", 0, 0.0, 0.0},
258 {"single visit", 1, 0.1, 0.05},
259 {"moderate visits", 10, 0.35, 0.1},
260 {"many visits", 100, 0.67, 0.1},
261 {"max visits", 1000, 1.0, 0.01},
262 }
263
264 for _, tt := range tests {
265 t.Run(tt.name, func(t *testing.T) {
266 result := searcher.calculateVisitScore(tt.visitCount)
267
268 if result < 0.0 || result > 1.0 {
269 t.Errorf("Score %f should be between 0.0 and 1.0", result)
270 }
271
272 diff := result - tt.expected
273 if diff < 0 {
274 diff = -diff
275 }
276 if diff > tt.delta {
277 t.Errorf("Expected %f ±%f, got %f", tt.expected, tt.delta, result)
278 }
279 })
280 }
281}
282
283func TestTextNormalization(t *testing.T) {
284 tests := []struct {
285 name string
286 input string
287 expected string
288 }{
289 {"basic url", "https://github.com", "github com"},
290 {"with www", "https://www.google.com", "google com"},
291 {"with path", "https://stackoverflow.com/questions/123", "stackoverflow com questions 123"},
292 {"mixed case", "GitHub.COM/User", "github com user"},
293 {"with special chars", "test-site_name.com", "test site name com"},
294 {"unicode chars", "café-münü.com", "café münü com"},
295 }
296
297 for _, tt := range tests {
298 t.Run(tt.name, func(t *testing.T) {
299 result := normalizeText(tt.input)
300 if result != tt.expected {
301 t.Errorf("Expected %q, got %q", tt.expected, result)
302 }
303 })
304 }
305}
306
307func TestTrigramExtraction(t *testing.T) {
308 tests := []struct {
309 name string
310 input string
311 expected []string
312 }{
313 {"short string", "ab", nil},
314 {"exact length", "abc", []string{"abc"}},
315 {"longer string", "github", []string{"git", "ith", "thu", "hub"}},
316 {"with spaces", "go lang", []string{"go ", "o l", " la", "lan", "ang"}},
317 }
318
319 for _, tt := range tests {
320 t.Run(tt.name, func(t *testing.T) {
321 result := extractTrigrams(tt.input)
322 if len(result) != len(tt.expected) {
323 t.Errorf("Expected %d trigrams, got %d", len(tt.expected), len(result))
324 return
325 }
326 for i, expected := range tt.expected {
327 if result[i] != expected {
328 t.Errorf("Expected trigram %q at index %d, got %q", expected, i, result[i])
329 }
330 }
331 })
332 }
333}
334
335func TestCompactEntry_BaseScore(t *testing.T) {
336 now := time.Now()
337
338 tests := []struct {
339 name string
340 visitCount uint16
341 lastVisit time.Time
342 expectRange [2]uint16 // min, max expected score
343 }{
344 {"high visits, recent", 100, now.Add(-1 * time.Hour), [2]uint16{44000, 65535}},
345 {"low visits, recent", 5, now.Add(-1 * time.Hour), [2]uint16{35000, 50000}},
346 {"high visits, old", 100, now.Add(-90 * 24 * time.Hour), [2]uint16{5000, 25000}},
347 {"low visits, old", 5, now.Add(-90 * 24 * time.Hour), [2]uint16{1000, 15000}},
348 }
349
350 for _, tt := range tests {
351 t.Run(tt.name, func(t *testing.T) {
352 entry := CompactEntry{
353 VisitCount: tt.visitCount,
354 LastVisit: DaysFromTime(tt.lastVisit),
355 }
356
357 score := entry.calculateBaseScore()
358
359 if score < tt.expectRange[0] || score > tt.expectRange[1] {
360 t.Errorf("Expected score between %d and %d, got %d",
361 tt.expectRange[0], tt.expectRange[1], score)
362 }
363 })
364 }
365}
366
367func TestFuzzySearch_Integration(t *testing.T) {
368 ctrl := gomock.NewController(t)
369 defer ctrl.Finish()
370
371 mockQuerier := mock_cache.NewMockHistoryQuerier(ctrl)
372 history := createTestHistory()
373
374 mockQuerier.EXPECT().GetHistory(gomock.Any(), gomock.Any()).Return(history, nil).AnyTimes()
375
376 tempDir, err := os.MkdirTemp("", "dumber_search_test")
377 if err != nil {
378 t.Fatalf("Failed to create temp dir: %v", err)
379 }
380 defer func() {
381 if err := os.RemoveAll(tempDir); err != nil {
382 t.Logf("Warning: failed to remove temp dir %s: %v", tempDir, err)
383 }
384 }()
385
386 config := DefaultCacheConfig()
387 config.CacheFile = filepath.Join(tempDir, "search_cache.bin")
388 config.ScoreThreshold = 0.1
389
390 manager := NewCacheManager(mockQuerier, config)
391 ctx := context.Background()
392
393 // Critical fuzzy search tests
394 searchTests := []struct {
395 name string
396 query string
397 expectCount int
398 expectFirst string
399 expectMatchType MatchType
400 }{
401 {
402 name: "exact domain match",
403 query: "github",
404 expectCount: 1,
405 expectFirst: "https://github.com",
406 expectMatchType: MatchTypeExact,
407 },
408 {
409 name: "partial title match",
410 query: "programming",
411 expectCount: 1,
412 expectFirst: "https://golang.org",
413 expectMatchType: MatchTypeExact,
414 },
415 {
416 name: "fuzzy typo match",
417 query: "githb", // typo in github
418 expectCount: 1,
419 expectFirst: "https://github.com",
420 expectMatchType: MatchTypeFuzzy,
421 },
422 {
423 name: "prefix match",
424 query: "you",
425 expectCount: 1,
426 expectFirst: "https://youtube.com",
427 expectMatchType: MatchTypePrefix,
428 },
429 {
430 name: "no matches",
431 query: "nonexistentsite12345",
432 expectCount: 0,
433 },
434 }
435
436 for _, tt := range searchTests {
437 t.Run(tt.name, func(t *testing.T) {
438 result, err := manager.Search(ctx, tt.query)
439 if err != nil {
440 t.Fatalf("Search failed: %v", err)
441 }
442
443 if len(result.Matches) < tt.expectCount {
444 t.Errorf("Expected at least %d matches, got %d", tt.expectCount, len(result.Matches))
445 return
446 }
447
448 if tt.expectCount == 0 {
449 return // No further checks needed
450 }
451
452 // Check first result
453 if result.Matches[0].Entry.URL != tt.expectFirst {
454 t.Errorf("Expected first result %q, got %q",
455 tt.expectFirst, result.Matches[0].Entry.URL)
456 }
457
458 // Verify results are sorted by score
459 for i := 1; i < len(result.Matches); i++ {
460 if result.Matches[i].Score > result.Matches[i-1].Score {
461 t.Errorf("Results not sorted by score: %f > %f at position %d",
462 result.Matches[i].Score, result.Matches[i-1].Score, i)
463 }
464 }
465
466 // Verify all scores meet threshold
467 for i, match := range result.Matches {
468 if match.Score < config.ScoreThreshold {
469 t.Errorf("Match %d score %f below threshold %f",
470 i, match.Score, config.ScoreThreshold)
471 }
472 }
473
474 // Verify query time is recorded
475 if result.QueryTime <= 0 {
476 t.Error("Query time should be positive")
477 }
478 })
479 }
480}
481
482func TestCacheInvalidation(t *testing.T) {
483 ctrl := gomock.NewController(t)
484 defer ctrl.Finish()
485
486 mockQuerier := mock_cache.NewMockHistoryQuerier(ctrl)
487
488 // First call returns initial history
489 firstHistory := createTestHistory()[:3] // Only 3 entries
490 secondHistory := createTestHistory() // All 5 entries
491
492 // Set up multiple expectations for the different calls
493 gomock.InOrder(
494 mockQuerier.EXPECT().GetHistory(gomock.Any(), gomock.Any()).Return(firstHistory, nil).Times(2), // Build + hash
495 mockQuerier.EXPECT().GetHistory(gomock.Any(), gomock.Any()).Return(secondHistory, nil).AnyTimes(), // Subsequent calls
496 )
497
498 tempDir, err := os.MkdirTemp("", "dumber_invalidation_test")
499 if err != nil {
500 t.Fatalf("Failed to create temp dir: %v", err)
501 }
502 defer func() {
503 if err := os.RemoveAll(tempDir); err != nil {
504 t.Logf("Warning: failed to remove temp dir %s: %v", tempDir, err)
505 }
506 }()
507
508 config := DefaultCacheConfig()
509 config.CacheFile = filepath.Join(tempDir, "invalidation_cache.bin")
510
511 manager := NewCacheManager(mockQuerier, config)
512 ctx := context.Background()
513
514 // Initial cache build
515 cache1, err := manager.GetCache(ctx)
516 if err != nil {
517 t.Fatalf("Failed to get initial cache: %v", err)
518 }
519
520 if cache1.entryCount != 3 {
521 t.Errorf("Expected 3 entries in initial cache, got %d", cache1.entryCount)
522 }
523
524 // Invalidate and refresh
525 manager.InvalidateAndRefresh(ctx)
526
527 // Wait for background refresh
528 time.Sleep(100 * time.Millisecond)
529
530 // Get updated cache
531 cache2, err := manager.GetCache(ctx)
532 if err != nil {
533 t.Fatalf("Failed to get updated cache: %v", err)
534 }
535
536 if cache2.entryCount != 5 {
537 t.Errorf("Expected 5 entries in updated cache, got %d", cache2.entryCount)
538 }
539}
540
541// create40TestEntries creates a realistic dataset with 40 entries for benchmarking
542func create40TestEntries() []db.History {
543 now := time.Now()
544 entries := make([]db.History, 40)
545
546 urls := []string{
547 "https://github.com", "https://stackoverflow.com", "https://golang.org", "https://news.ycombinator.com",
548 "https://youtube.com", "https://google.com", "https://reddit.com", "https://twitter.com",
549 "https://linkedin.com", "https://medium.com", "https://dev.to", "https://docs.python.org",
550 "https://reactjs.org", "https://nodejs.org", "https://kubernetes.io", "https://docker.com",
551 "https://aws.amazon.com", "https://cloud.google.com", "https://azure.microsoft.com", "https://heroku.com",
552 "https://netlify.com", "https://vercel.com", "https://stripe.com", "https://shopify.com",
553 "https://gitlab.com", "https://bitbucket.org", "https://atlassian.com", "https://slack.com",
554 "https://discord.com", "https://telegram.org", "https://whatsapp.com", "https://facebook.com",
555 "https://instagram.com", "https://tiktok.com", "https://netflix.com", "https://spotify.com",
556 "https://apple.com", "https://microsoft.com", "https://amazon.com", "https://wikipedia.org",
557 }
558
559 titles := []string{
560 "GitHub", "Stack Overflow", "Go Programming Language", "Hacker News",
561 "YouTube", "Google", "Reddit", "Twitter",
562 "LinkedIn", "Medium", "Dev.to", "Python Documentation",
563 "React", "Node.js", "Kubernetes", "Docker",
564 "AWS", "Google Cloud", "Microsoft Azure", "Heroku",
565 "Netlify", "Vercel", "Stripe", "Shopify",
566 "GitLab", "Bitbucket", "Atlassian", "Slack",
567 "Discord", "Telegram", "WhatsApp", "Facebook",
568 "Instagram", "TikTok", "Netflix", "Spotify",
569 "Apple", "Microsoft", "Amazon", "Wikipedia",
570 }
571
572 for i := 0; i < 40; i++ {
573 entries[i] = db.History{
574 ID: int64(i + 1),
575 Url: urls[i],
576 Title: sql.NullString{String: titles[i], Valid: true},
577 VisitCount: sql.NullInt64{Int64: int64(40 - i), Valid: true}, // Decreasing visit counts
578 LastVisited: sql.NullTime{Time: now.Add(-time.Duration(i) * time.Hour), Valid: true},
579 }
580 }
581
582 return entries
583}
584
585// BenchmarkGetTopEntries benchmarks the critical path for dmenu performance
586func BenchmarkGetTopEntries(b *testing.B) {
587 ctrl := gomock.NewController(b)
588 defer ctrl.Finish()
589
590 mockQuerier := mock_cache.NewMockHistoryQuerier(ctrl)
591
592 // Setup 40 test entries
593 testHistory := create40TestEntries()
594 mockQuerier.EXPECT().GetHistory(gomock.Any(), gomock.Any()).Return(testHistory, nil).AnyTimes()
595
596 // Create temporary directory for cache file
597 tempDir, err := os.MkdirTemp("", "cache_benchmark")
598 if err != nil {
599 b.Fatalf("Failed to create temp dir: %v", err)
600 }
601 defer func() {
602 if err := os.RemoveAll(tempDir); err != nil {
603 b.Logf("Warning: failed to remove temp dir %s: %v", tempDir, err)
604 }
605 }()
606
607 config := DefaultCacheConfig()
608 config.CacheFile = filepath.Join(tempDir, "benchmark_cache.bin")
609 config.MaxResults = 50
610
611 manager := NewCacheManager(mockQuerier, config)
612 ctx := context.Background()
613
614 // Pre-build cache once (this isn't part of the benchmark)
615 _, err = manager.GetCache(ctx)
616 if err != nil {
617 b.Fatalf("Failed to pre-build cache: %v", err)
618 }
619
620 b.ResetTimer() // Start timing from here
621 b.ReportAllocs()
622
623 // This is the critical path that needs to be under 2ms
624 for i := 0; i < b.N; i++ {
625 result, err := manager.GetTopEntries(ctx)
626 if err != nil {
627 b.Fatalf("GetTopEntries failed: %v", err)
628 }
629 if len(result.Matches) == 0 {
630 b.Fatalf("Expected matches, got none")
631 }
632 }
633}
634
635// BenchmarkGetTopEntriesParallel benchmarks concurrent access performance
636func BenchmarkGetTopEntriesParallel(b *testing.B) {
637 ctrl := gomock.NewController(b)
638 defer ctrl.Finish()
639
640 mockQuerier := mock_cache.NewMockHistoryQuerier(ctrl)
641
642 // Setup 40 test entries
643 testHistory := create40TestEntries()
644 mockQuerier.EXPECT().GetHistory(gomock.Any(), gomock.Any()).Return(testHistory, nil).AnyTimes()
645
646 // Create temporary directory for cache file
647 tempDir, err := os.MkdirTemp("", "cache_benchmark_parallel")
648 if err != nil {
649 b.Fatalf("Failed to create temp dir: %v", err)
650 }
651 defer func() {
652 if err := os.RemoveAll(tempDir); err != nil {
653 b.Logf("Warning: failed to remove temp dir %s: %v", tempDir, err)
654 }
655 }()
656
657 config := DefaultCacheConfig()
658 config.CacheFile = filepath.Join(tempDir, "benchmark_parallel_cache.bin")
659 config.MaxResults = 50
660
661 manager := NewCacheManager(mockQuerier, config)
662 ctx := context.Background()
663
664 // Pre-build cache once (this isn't part of the benchmark)
665 _, err = manager.GetCache(ctx)
666 if err != nil {
667 b.Fatalf("Failed to pre-build cache: %v", err)
668 }
669
670 b.ResetTimer()
671 b.ReportAllocs()
672
673 b.RunParallel(func(pb *testing.PB) {
674 for pb.Next() {
675 result, err := manager.GetTopEntries(ctx)
676 if err != nil {
677 b.Fatalf("GetTopEntries failed: %v", err)
678 }
679 if len(result.Matches) == 0 {
680 b.Fatalf("Expected matches, got none")
681 }
682 }
683 })
684}