feat: implement LRU cache for expensive operations

## Summary
Implement a Least Recently Used (LRU) cache to store results of expensive operations (file search, edit correction, token counting, MCP API calls) and prevent redundant computation.

## Background
Currently, the token optimizer performs expensive operations repeatedly:
- **File search**: Scanning repository for patterns (takes 100-500ms per search)
- **Edit correction**: Running MCP `correct_edits` API (takes 500-2000ms per file)
- **Token counting**: Calling Google AI API or processing large text (takes 100-300ms per call)
- **Smart read**: Calling MCP `smart_read` API (takes 200-1000ms per file)

Gemini CLI uses an LRU cache to store results with automatic eviction of least-used entries when the cache reaches capacity.

## Gemini CLI Pattern Reference

**File**: `packages/core/src/utils/LruCache.ts`

**Pattern**: Generic LRU cache with max size and TTL
```typescript
export class LruCache<K, V> {
  private cache: Map<K, CacheEntry<V>>;
  private maxSize: number;
  private ttlMs: number;

  constructor(maxSize: number, ttlMs: number = 0) {
    this.cache = new Map();
    this.maxSize = maxSize;
    this.ttlMs = ttlMs;
  }

  get(key: K): V | undefined {
    const entry = this.cache.get(key);
    if (!entry) return undefined;

    // Check TTL expiration
    if (this.ttlMs > 0 && Date.now() - entry.timestamp > this.ttlMs) {
      this.cache.delete(key);
      return undefined;
    }

    // Move to end (most recently used)
    this.cache.delete(key);
    this.cache.set(key, entry);
    return entry.value;
  }

  set(key: K, value: V): void {
    // Remove if already exists (to re-insert at end)
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }

    // Evict least recently used if at capacity
    if (this.cache.size >= this.maxSize) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }

    // Insert at end (most recently used)
    this.cache.set(key, {
      value,
      timestamp: Date.now()
    });
  }

  clear(): void {
    this.cache.clear();
  }

  get size(): number {
    return this.cache.size;
  }
}

interface CacheEntry<V> {
  value: V;
  timestamp: number;
}
```

**File**: `packages/core/src/utils/filesearch/crawlCache.ts`

**Pattern**: File search caching with TTL
```typescript
const crawlCache = new LruCache<string, CrawlResult>(
  100,  // Max 100 cached search results
  1000 * 60 * 5  // TTL: 5 minutes
);

async function searchFiles(pattern: string): Promise<CrawlResult> {
  // Check cache first
  const cached = crawlCache.get(pattern);
  if (cached) {
    return cached;
  }

  // Perform expensive search
  const result = await performFileSearch(pattern);

  // Cache result
  crawlCache.set(pattern, result);
  return result;
}
```

## Implementation Strategy

### 1. Create LruCache PowerShell Class

**Location**: `C:\Users\cheat\.claude-global\hooks\handlers\token-optimizer-orchestrator.ps1`

```powershell
class LruCacheEntry {
    [object]$Value
    [datetime]$Timestamp

    LruCacheEntry([object]$value) {
        $this.Value = $value
        $this.Timestamp = Get-Date
    }
}

class LruCache {
    [System.Collections.Specialized.OrderedDictionary]$Cache
    [int]$MaxSize
    [int]$TtlSeconds
    [int]$HitCount = 0
    [int]$MissCount = 0
    [int]$EvictionCount = 0

    LruCache([int]$maxSize, [int]$ttlSeconds) {
        $this.Cache = [System.Collections.Specialized.OrderedDictionary]::new()
        $this.MaxSize = $maxSize
        $this.TtlSeconds = $ttlSeconds
    }

    # Get value from cache (returns $null if not found or expired)
    [object] Get([string]$key) {
        if (-not $this.Cache.Contains($key)) {
            $this.MissCount++
            return $null
        }

        $entry = $this.Cache[$key]

        # Check TTL expiration
        if ($this.TtlSeconds -gt 0) {
            $age = ((Get-Date) - $entry.Timestamp).TotalSeconds
            if ($age -gt $this.TtlSeconds) {
                $this.Cache.Remove($key)
                $this.MissCount++
                $this.EvictionCount++
                return $null
            }
        }

        # Move to end (most recently used) by removing and re-adding
        $value = $entry.Value
        $this.Cache.Remove($key)
        $this.Cache[$key] = [LruCacheEntry]::new($value)

        $this.HitCount++
        return $value
    }

    # Set value in cache
    [void] Set([string]$key, [object]$value) {
        # Remove if already exists (to re-insert at end)
        if ($this.Cache.Contains($key)) {
            $this.Cache.Remove($key)
        }

        # Evict least recently used if at capacity
        if ($this.Cache.Count -ge $this.MaxSize) {
            # First key is least recently used (OrderedDictionary maintains insertion order)
            $firstKey = @($this.Cache.Keys)[0]
            $this.Cache.Remove($firstKey)
            $this.EvictionCount++
        }

        # Insert at end (most recently used)
        $this.Cache[$key] = [LruCacheEntry]::new($value)
    }

    # Check if key exists and is not expired
    [bool] ContainsKey([string]$key) {
        return $null -ne $this.Get($key)
    }

    # Clear all entries
    [void] Clear() {
        $this.Cache.Clear()
        $this.HitCount = 0
        $this.MissCount = 0
        $this.EvictionCount = 0
    }

    # Get cache statistics
    [hashtable] GetStats() {
        $totalRequests = $this.HitCount + $this.MissCount
        return @{
            Size = $this.Cache.Count
            MaxSize = $this.MaxSize
            HitCount = $this.HitCount
            MissCount = $this.MissCount
            EvictionCount = $this.EvictionCount
            HitRate = if ($totalRequests -gt 0) {
                [Math]::Round(($this.HitCount / $totalRequests) * 100, 2)
            } else { 0 }
        }
    }

    # Cleanup expired entries (call periodically)
    [int] CleanupExpired() {
        if ($this.TtlSeconds -le 0) { return 0 }

        $removed = 0
        $keysToRemove = @()

        foreach ($key in $this.Cache.Keys) {
            $entry = $this.Cache[$key]
            $age = ((Get-Date) - $entry.Timestamp).TotalSeconds
            if ($age -gt $this.TtlSeconds) {
                $keysToRemove += $key
            }
        }

        foreach ($key in $keysToRemove) {
            $this.Cache.Remove($key)
            $removed++
        }

        $this.EvictionCount += $removed
        return $removed
    }
}
```

### 2. Initialize Caches for Different Operations

**Location**: Script initialization section (top of orchestrator)

```powershell
# Initialize LRU caches for different operation types
if (-not $script:FileSearchCache) {
    # File search results (pattern -> file list)
    # Max 100 patterns, TTL 5 minutes (file system may change)
    $script:FileSearchCache = [LruCache]::new(100, 300)
}

if (-not $script:EditCorrectionCache) {
    # Edit correction results (file hash -> corrected content)
    # Max 50 files, TTL 10 minutes (files change frequently during editing)
    $script:EditCorrectionCache = [LruCache]::new(50, 600)
}

if (-not $script:TokenCountCache) {
    # Token counting results (content hash -> token count)
    # Max 200 entries, TTL 30 minutes (content is stable once counted)
    $script:TokenCountCache = [LruCache]::new(200, 1800)
}

if (-not $script:SmartReadCache) {
    # Smart read results (file path + timestamp -> content)
    # Max 100 files, TTL 2 minutes (very short - files change often)
    $script:SmartReadCache = [LruCache]::new(100, 120)
}
```

### 3. Integration with File Search (Example)

**Current code** (hypothetical file search in orchestrator):
```powershell
function Search-RepositoryFiles {
    param([string]$Pattern)

    # Expensive operation: scan repository
    $files = Get-ChildItem -Path $REPO_ROOT -Recurse -Filter $Pattern
    return $files
}
```

**New code with LRU caching**:
```powershell
function Search-RepositoryFiles {
    param([string]$Pattern)

    # Check cache first
    $cached = $script:FileSearchCache.Get($Pattern)
    if ($null -ne $cached) {
        Write-Log "File search cache HIT for pattern: $Pattern" "DEBUG"
        return $cached
    }

    Write-Log "File search cache MISS for pattern: $Pattern" "DEBUG"

    # Expensive operation: scan repository
    $files = Get-ChildItem -Path $REPO_ROOT -Recurse -Filter $Pattern

    # Cache result
    $script:FileSearchCache.Set($Pattern, $files)

    return $files
}
```

### 4. Integration with Token Counting

**Location**: TokenCounter class from Issue #4

```powershell
class TokenCounter {
    [LruCache]$Cache

    TokenCounter([string]$apiKey) {
        $this.ApiKey = $apiKey
        # Use LRU cache instead of simple hashtable
        $this.Cache = [LruCache]::new(200, 1800)  # Max 200, TTL 30 min
    }

    [int] CountTokens([string]$text, [string]$contentType) {
        # Cache key includes both content hash and type
        $textHash = [System.BitConverter]::ToString(
            [System.Security.Cryptography.SHA256]::Create().ComputeHash(
                [System.Text.Encoding]::UTF8.GetBytes($text)
            )
        ).Replace("-", "")
        $cacheKey = "$contentType`:$textHash"

        # Check LRU cache
        $cached = $this.Cache.Get($cacheKey)
        if ($null -ne $cached) {
            return $cached
        }

        # Expensive operation: API call or estimation
        try {
            $tokenCount = $this.CountTokensViaAPI($text)
        } catch {
            $tokenCount = $this.EstimateTokens($text, $contentType)
        }

        # Cache result
        $this.Cache.Set($cacheKey, $tokenCount)

        return $tokenCount
    }
}
```

### 5. Periodic Cache Cleanup and Statistics

**Location**: End of PostToolUse phase or SessionStart

```powershell
# Cleanup expired entries every 10 operations
if ($script:CurrentSession.totalOperations % 10 -eq 0) {
    $removedSearch = $script:FileSearchCache.CleanupExpired()
    $removedEdit = $script:EditCorrectionCache.CleanupExpired()
    $removedToken = $script:TokenCountCache.CleanupExpired()
    $removedRead = $script:SmartReadCache.CleanupExpired()

    $totalRemoved = $removedSearch + $removedEdit + $removedToken + $removedRead
    if ($totalRemoved -gt 0) {
        Write-Log "Cache cleanup: removed $totalRemoved expired entries" "DEBUG"
    }
}

# Log cache statistics every 20 operations
if ($script:CurrentSession.totalOperations % 20 -eq 0) {
    $searchStats = $script:FileSearchCache.GetStats()
    $editStats = $script:EditCorrectionCache.GetStats()
    $tokenStats = $script:TokenCountCache.GetStats()
    $readStats = $script:SmartReadCache.GetStats()

    Write-Log "Cache stats - FileSearch: $($searchStats.Size)/$($searchStats.MaxSize) entries, $($searchStats.HitRate)% hit rate" "INFO"
    Write-Log "Cache stats - EditCorrection: $($editStats.Size)/$($editStats.MaxSize) entries, $($editStats.HitRate)% hit rate" "INFO"
    Write-Log "Cache stats - TokenCount: $($tokenStats.Size)/$($tokenStats.MaxSize) entries, $($tokenStats.HitRate)% hit rate" "INFO"
    Write-Log "Cache stats - SmartRead: $($readStats.Size)/$($readStats.MaxSize) entries, $($readStats.HitRate)% hit rate" "INFO"
}
```

## Acceptance Criteria

- [ ] LruCache class implemented with generic key/value support
- [ ] Automatic eviction of least recently used entries at capacity
- [ ] TTL (time-to-live) support with automatic expiration
- [ ] Cache statistics tracking (hits, misses, evictions, hit rate)
- [ ] Cleanup method to remove expired entries
- [ ] Integration with file search operations
- [ ] Integration with edit correction operations
- [ ] Integration with token counting operations
- [ ] Integration with smart read operations
- [ ] Periodic cleanup of expired entries
- [ ] Periodic logging of cache statistics

## Testing Strategy

### Unit Tests
```powershell
# Test basic LRU behavior
$cache = [LruCache]::new(3, 0)  # Max 3 entries, no TTL
$cache.Set("a", 1)
$cache.Set("b", 2)
$cache.Set("c", 3)
$cache.Get("a") | Should -Be 1  # Hit
$cache.Set("d", 4)  # Should evict "b" (least recently used)
$cache.Get("b") | Should -Be $null  # Miss (evicted)
$cache.Get("a") | Should -Be 1  # Still there (was accessed)

# Test TTL expiration
$cache = [LruCache]::new(10, 2)  # TTL: 2 seconds
$cache.Set("key", "value")
$cache.Get("key") | Should -Be "value"  # Hit
Start-Sleep -Seconds 3
$cache.Get("key") | Should -Be $null  # Expired

# Test statistics
$cache = [LruCache]::new(10, 0)
$cache.Set("k1", "v1")
$cache.Get("k1")  # Hit
$cache.Get("k2")  # Miss
$stats = $cache.GetStats()
$stats.HitCount | Should -Be 1
$stats.MissCount | Should -Be 1
$stats.HitRate | Should -Be 50.0
```

### Integration Tests
```powershell
# Test file search caching
$pattern = "*.ps1"
$result1 = Search-RepositoryFiles -Pattern $pattern
$result2 = Search-RepositoryFiles -Pattern $pattern
# Second call should be cached (much faster)
$stats = $script:FileSearchCache.GetStats()
$stats.HitCount | Should -BeGreaterThan 0

# Test token counting caching
$counter = [TokenCounter]::new($env:GOOGLE_AI_API_KEY)
$text = "Some test content"
$count1 = $counter.CountTokens($text, "text")
$count2 = $counter.CountTokens($text, "text")
# Second call should be cached
$stats = $counter.Cache.GetStats()
$stats.HitCount | Should -BeGreaterThan 0
```

### Performance Tests
```powershell
# Measure cache speedup
$pattern = "*.cs"
$time1 = Measure-Command { Search-RepositoryFiles -Pattern $pattern }
$time2 = Measure-Command { Search-RepositoryFiles -Pattern $pattern }
# Cached call should be at least 10x faster
$time2.TotalMilliseconds | Should -BeLessThan ($time1.TotalMilliseconds / 10)

# Measure memory usage
$cache = [LruCache]::new(1000, 0)
1..1000 | ForEach-Object { $cache.Set("key$_", "value$_") }
# Memory should be reasonable (OrderedDictionary overhead)
[GC]::Collect()
$memoryMB = [GC]::GetTotalMemory($false) / 1MB
$memoryMB | Should -BeLessThan 100  # Less than 100MB for 1000 entries
```

## Priority
**MEDIUM-HIGH** - LRU caching provides significant performance improvements but requires other optimizations (token counting, compression) to be in place first to maximize benefit.

## Expected Impact
- **File search**: 100-500ms → <10ms (10-50x speedup)
- **Edit correction**: 500-2000ms → <10ms (50-200x speedup)
- **Token counting**: 100-300ms → <5ms (20-60x speedup)
- **Smart read**: 200-1000ms → <10ms (20-100x speedup)

For a typical session with 383 operations (current session), assuming 30% cache hit rate:
- ~115 operations skip expensive API calls
- Total savings: ~15-30 seconds per session

## References
- Gemini CLI LRU cache: `packages/core/src/utils/LruCache.ts`
- Gemini CLI file search cache: `packages/core/src/utils/filesearch/crawlCache.ts`
- Related: Issue #4 (Token counting - benefits from LRU cache)
- Related: Issue #3 (Context delta - benefits from LRU cache for content hashing)


Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: implement LRU cache for expensive operations #125

Summary

Background

Gemini CLI Pattern Reference

Implementation Strategy

1. Create LruCache PowerShell Class

2. Initialize Caches for Different Operations

3. Integration with File Search (Example)

4. Integration with Token Counting

5. Periodic Cache Cleanup and Statistics

Acceptance Criteria

Testing Strategy

Unit Tests

Integration Tests

Performance Tests

Priority

Expected Impact

References

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

feat: implement LRU cache for expensive operations #125

Description

Summary

Background

Gemini CLI Pattern Reference

Implementation Strategy

1. Create LruCache PowerShell Class

2. Initialize Caches for Different Operations

3. Integration with File Search (Example)

4. Integration with Token Counting

5. Periodic Cache Cleanup and Statistics

Acceptance Criteria

Testing Strategy

Unit Tests

Integration Tests

Performance Tests

Priority

Expected Impact

References

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions