* Shrink binary: trim image decoders and swap color-eyre for eyre
Two dependency changes that cut the default `sk` binary from 13.6 MiB to
8.55 MiB (-5.06 MiB, -37%) with no loss of core functionality:
- image: build the `image` crate with only the common decoders (png,
jpeg, gif, webp) instead of its full default format set, and drop
ratatui-image's `image-defaults`. This removes AVIF encoding (ravif,
avif-serialize), OpenEXR (exr), TIFF, QOI and other decoders that are
irrelevant to terminal image previews. Previewing those formats now
falls back to the normal command preview.
- error handling: replace color-eyre with plain eyre. color-eyre only
provided colored panic/error backtraces; skim used none of its
Section/Help extension APIs. This drops the backtrace/gimli/addr2line/
color-spantrace stack. `color_eyre::install()` is no longer needed.
Tests, benches and examples are migrated from color_eyre to eyre so the
crate is fully removed from the dependency graph.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01BQtxeCS4gM7dumghqmNgST
* chore: fmt
* docs: ARCHITECTURE.md
* chore(flake): add cargo-bloat
---------
Co-authored-by: Claude <noreply@anthropic.com>
* test(engine,fuzzy_matcher): add unit tests for branch coverage; fix use_cache(false) double-borrow
Add targeted unit tests to exercise every reachable branch in the `engine`
and `fuzzy_matcher` modules, measured with cargo-llvm-cov's branch coverage
on nightly. Tests use realistic inputs and assert concrete behaviour:
- engine: empty/offset/byte-range matching ranges in the fuzzy engine, the
Frizbee and typo Arinae build paths, AND/OR empty-term filtering, and
split-engine byte-range char exclusion.
- arinae: typo substitutions and deletions, non-ASCII dispatch, prefilter
rejection paths, and direct kernel tests for the DP guards / band-skip /
dead-row pruning that compute_banding makes unreachable through the API.
- clangd/fzy/skim/util: typo-DP substitution, deletion, gap and length-guard
paths; ASCII/non-ASCII dispatch; single-char and score-only paths; and the
assert_order failure diagnostics.
Fix a latent double-borrow bug: `use_cache(false)` in the clangd, skim and
fzy matchers called `RefCell::replace` on cache cells whose `RefMut` guards
were still alive, panicking on every match. Drop the guards before clearing
the caches so the option works (and is now covered by tests).
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Q93ttrw4JoXCjBezV2Skmm
* test(fuzzy_matcher): thread guard paths by isolating callees
Cover branches that are reachable only when the inner helper is invoked
directly with inputs the public matchers can never produce:
- clangd `match_bonus` with `Action::Miss` (callers always pass `Match`) —
asserts the 30-point in-segment-after-miss penalty.
- fzy `internal_to_skim_score(SCORE_MIN)` sentinel mapping; the empty-pattern
slow-path `n == 0` guard; and `fzy_score` driven with a non-subsequence
needle so the position backtrace hits the column-0 fallback.
The branches that remain uncovered are now confirmed structurally
unreachable even via direct callee calls: const-generic monomorphization
artifacts, M-cell `!= SCORE_MIN` checks (an M-cell is never exactly the
sentinel after gap accumulation), a match cell at (i>0, j==0) that is always
SCORE_MIN, and short-circuit operands excluded by upstream invariants.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Q93ttrw4JoXCjBezV2Skmm
* test(fuzzy_matcher/skim): thread arg-reachable guards in skim helpers
build_in_place_bonus's `b.len() > 1` and calculate_score_with_pos's
`op.is_none()` are unreachable through the public matcher (the real caller
never passes an empty choice or an over-wide column range), but they ARE
reachable by calling the private helpers directly with such arguments.
Cover both, leaving only genuinely argument-independent dead branches.
Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Q93ttrw4JoXCjBezV2Skmm
* chore: misc checks & fixes
* fix: default bench arg
* Potential fix for pull request finding
Co-authored-by: Copilot Autofix powered by AI <175728472+Copilot@users.noreply.github.com>
* chore: remove magic number
---------
Co-authored-by: Claude <noreply@anthropic.com>
Co-authored-by: Copilot Autofix powered by AI <175728472+Copilot@users.noreply.github.com>
* chore: deps: Only use frizbee on x86_64 and aarch64
* chore: update docs for frizbee support
* chore: docs [skip ci]
---------
Co-authored-by: LoricAndre <57358788+LoricAndre@users.noreply.github.com>
* feat: initial work on skim v3
wip
* wip: SW
* chore: refactor SkimV3 to make it more maintainable
* chore: remove SIMD batch scores
* fix: fix Skim V3 tests
* feat: small optimizations
* feat: bigger optimizations
* chore: generate completions & manpage
* chore: remove unused wide dependency
* chore: update deps
* chore: generate completions & manpage
* fix: make sure all subsequences pass in non-typos mode
* chore: trade some performance against more precision with typos
* feat: gain the performance back using unchecked accesses
* chore: remove failing tests
* feat: use banding across whole upper triangle
* chore: remove useless DEAD_COL checks
* feat: make sure we match everything `frizbee` does while enforcing first char
* feat: minor optimizations
* feat: more minor optimizations
* chore: tweak parameters to find a good balance between performance and accuracy
* chore: accept snap
* chore: penalize consecutive typos
* chore: revert consecutive typos penalization as it seems useless in practice
* wip: optimizations
* feat: multiple optimizations
* perf(skim_v3): use 2-row rolling buffer for score-only DP path
When compute_indices=false (fuzzy_match), the full (n+1)×mcols matrix
was allocated and populated even though traceback was never performed.
Introduce score_only_dp() which maintains only two rows at a time,
reducing memory from O(n×m) to O(m) and improving cache utilization
for long choice strings.
* perf(skim_v3): add early termination when DP rows are all-zero
Track consecutive rows where no cell has a positive score. After 2
consecutive dead rows, return None immediately: gap penalties can only
decrease existing scores, so no downstream row can produce a positive
result. Applied to both score_only_dp and full_dp.
* perf(skim_v3): add range_dp for fuzzy_match_range, avoiding full index vec
fuzzy_match_range previously called fuzzy_indices (full traceback collecting
every matched index) just to extract the first and last. Introduce range_dp
which performs the same full-matrix DP but during traceback only records the
begin and end positions, avoiding the Vec allocation and index collection.
Add range_consistent_with_indices test to verify correctness.
* perf(skim_v3): remove redundant is_subsequence scan in exact mode
In non-typo mode, is_subsequence was called before compute_banding, but
compute_banding -> compute_first_match_cols already validates the same
subsequence property (returning None if any pattern char is absent).
Remove the redundant O(m) scan and delete the now-unused is_subsequence
function. Typo mode retains cheap_typo_prefilter as its guard.
* perf(skim_v3): avoid clone in traceback by using mem::take on thread-local buffer
Previously full_dp returned indices via indices_ref.to_vec() which copies
all n index values into a new allocation. Replace with std::mem::take which
moves ownership of the populated Vec out of the thread-local without copying,
trading the reuse-across-calls benefit for zero-copy return per call.
* perf(skim_v3): tighten typo-mode upper band bound in typo_vband_row
Previously the upper column bound in typo mode was always m (the full
choice length), even for early rows where the diagonal sits far from the
right edge. Compute hi = (j + bandwidth).min(m) symmetrically with the
existing lower bound, skipping cells that cannot contribute to a valid
alignment and reducing work for short patterns on long strings.
* perf(skim_v3): use memchr SIMD for first-char search in prefilter and banding
Add memchr as a direct dependency and implement Atom::find_first_in with
a u8-specialization that calls memchr() for case-sensitive search and a
two-call min-of-two approach for case-insensitive. Use this in:
- cheap_typo_prefilter: first-character existence check
- find_first_char: typo-mode banding anchor computation
This replaces scalar byte-by-byte loops with SIMD-vectorized searches for
ASCII inputs, the common case.
* revert(skim_v3): restore m upper bound in typo_vband_row
The tightened hi = (j + bandwidth).min(m) bound incorrectly rejected valid
typo-mode alignments where the optimal path takes many LEFT (gap) steps
past the bandwidth boundary. The snapshot test confirms 5 fewer matches vs
the expected 37. Revert to hi = m; the affine gap penalty alone prevents
poor alignments from winning.
* perf(skim_v3): add ASCII fast path to char::eq_ignore_case
Replace the to_lowercase() iterator comparison with eq_ignore_ascii_case()
for the common case where both chars are ASCII. This avoids creating two
ToLowercase iterators per comparison in the non-ASCII DP path, using a
single bitwise comparison instead.
* perf(skim_v3): replace RefCell with UnsafeCell (TLCell) in thread-locals
ThreadLocal<RefCell<T>> incurs a runtime borrow-check on every access.
Since ThreadLocal already guarantees per-thread isolation and we never
re-enter the same thread-local within a single call stack, the RefCell
check is redundant.
Replace with TLCell<T>, a Send newtype over UnsafeCell<T>, and a tl_get_mut
helper that returns &mut T directly. Document the safety invariant at each
call site. Also remove the now-unused SWMatrix::zero constructor.
* fix(skim_v3): fix precompute_bonuses reserve logic
The previous reserve(cho.len().saturating_sub(buf.len())) computed the
needed additional capacity relative to the current length, which could
be wrong if buf.len() was stale (e.g. after a set_len call on a longer
buffer). Replace with clear() + reserve(cho.len()) for a correct and
clear-intent O(1) reset followed by a single exact reservation.
* guard: return None for pat.len() > MAX_PAT_LEN in exact mode
Patterns longer than MAX_PAT_LEN (16) used the stack-allocated
[usize; MAX_PAT_LEN] banding arrays with out-of-bounds indices,
causing undefined behaviour in the exact (non-typo) DP path.
Add an early return of None in compute_first_match_cols and
compute_last_match_cols so callers gracefully skip overlong patterns
rather than reading past the end of a fixed-size array. Typo mode
is unaffected: its dummy arrays are never indexed by the pattern
length.
* perf: re-encode Dir::None=0 so CELL_ZERO is all-zero bytes
Previously Dir::None=3 made Cell::new(0,Dir::None) encode as
0x00030000, preventing bulk-zeroing with write_bytes(0).
Re-assign discriminants to None=0, Diag=1, Up=2, Left=3 so that
CELL_ZERO is now all-zero. Update:
- Dir discriminants in the enum
- Cell::is_diag() (checks tag==1 instead of 0)
- compute_cell branchless arithmetic (base is Left=3, subtract 2 for
Diag wins, 1 for Up wins; None=0 so no OR needed)
- score_only_dp: replace init loop with write_bytes(0)
- full_dp / range_dp: replace row-0 init loop with write_bytes(0)
* perf: 128-bit ASCII bitset for cheap_typo_prefilter tail scan
Add Atom::count_tail_present with a u8 specialisation that builds a
two-u64 presence bitset from the choice in a single O(m) pass, making
each subsequent pattern-char lookup O(1) instead of O(m).
The char (non-ASCII) path delegates to count_tail_present_ordered, the
same ordered linear scan that was previously inlined in the function.
The change is observationally equivalent: the prefilter remains a
lenient superset of the old check (unordered vs. ordered presence),
and the snapshot test count is unchanged.
* perf: early exit in count_tail_present_ordered when match is impossible
Add a hopeless-state check at the top of each iteration: if matched
plus remaining pattern chars cannot reach min_needed, bail out
immediately rather than completing the full scan.
This prunes the non-ASCII (char) ordered-scan fallback inside
cheap_typo_prefilter when the pattern is long and many chars are
missing from the choice.
* cleanup: remove unused constants SEPARATOR_MASK_LO/HI and FIRST_CHAR_BONUS_MULTIPLIER
All three were suppressed with #[allow(dead_code)] and are not
referenced by any live code. SEPARATOR_TABLE is the active lookup;
the mask constants were documentation remnants.
* refactor: replace unsafe transmute in Cell::dir() and compute_cell with safe match
Both usages converted a u8 (guaranteed 0..=3) to Dir via transmute.
Replace with an exhaustive match on the 2-bit tag value — no unsafe
required, and the compiler generates the same conditional-move
sequence.
* perf: Atom::is_sep() trait method avoids u8→char→u32 in separator check
Add is_sep() to the Atom trait with a u8 specialisation that indexes
SEPARATOR_TABLE directly with self as usize, skipping the into::<char>
conversion required by the generic default.
Remove the now-unnecessary is_separator free function; callers use
prev.is_sep() instead.
* refactor: precompute_bonuses rewritten as safe iterator chain
Replace the unsafe raw-pointer write loop with a safe iterator that
starts with START_OF_STRING_BONUS and maps windows-of-2 to the
separator/camelCase bonus formula. buf.extend() dispatches through
ExactSizeIterator, so no extra allocation occurs.
The safe form exposes the element-independent structure to the
compiler, enabling auto-vectorisation on release builds.
* refactor: extract match_slices_range; simplify run_range
Add match_slices_range<C: Atom> that mirrors match_slices but calls
range_dp instead of dispatch_dp. run_range now delegates the ASCII
path to match_slices_range and keeps only the non-ASCII char-buf
setup inline, eliminating the duplicated prefilter + bonus +
range_dp block.
* mem: SWMatrix::resize shrinks when buffer is 4× over-allocated
After a one-off large input, the full-DP matrix buffer could hold
significantly more memory than typical inputs require. Add a
shrink-or-cap heuristic: if the current capacity exceeds 4× the
needed size, truncate and shrink_to(2×needed) to release excess
memory without thrashing on stable-sized inputs.
* Revert "mem: SWMatrix::resize shrinks when buffer is 4× over-allocated"
This reverts commit 9c8571ebe8.
* Revert "refactor: replace unsafe transmute in Cell::dir() and compute_cell with safe match"
This reverts commit 8805fa14ce.
* Revert "perf: Atom::is_sep() trait method avoids u8→char→u32 in separator check"
This reverts commit 175f26af81.
* Revert "perf: early exit in count_tail_present_ordered when match is impossible"
This reverts commit 29721558f0.
* Revert "perf: 128-bit ASCII bitset for cheap_typo_prefilter tail scan"
This reverts commit d79947fcb5.
* Revert "refactor: extract match_slices_range; simplify run_range"
This reverts commit 0fb7f05513.
* Revert "perf(skim_v3): replace RefCell with UnsafeCell (TLCell) in thread-locals"
This reverts commit 0806683251.
* Revert "perf(skim_v3): add ASCII fast path to char::eq_ignore_case"
This reverts commit 069710ad7c.
* Revert "revert(skim_v3): restore m upper bound in typo_vband_row"
This reverts commit 90ffc46633.
* Revert "perf(skim_v3): tighten typo-mode upper band bound in typo_vband_row"
This reverts commit f38ca3a10d.
* Revert "perf(skim_v3): avoid clone in traceback by using mem::take on thread-local buffer"
This reverts commit ffa9a21167.
* Revert "perf(skim_v3): add early termination when DP rows are all-zero"
This reverts commit 073195be58.
* Revert "perf(skim_v3): use 2-row rolling buffer for score-only DP path"
This reverts commit 3acacaad74.
* fix: reverse only order of frizbee indices
* chore: rename & refactor into multiple files
* chore: optimizations to the main flow
* fix: correct banding in non-typo path
* chore: generate completions & manpage
* docs: add algorithms section to the README [skip ci]
* fix(ari): correctly bound vband low
* chore(ari): specific pre-separator bonuses
* fix(ari): boost consec a bit more to beat start/sep
* chore: generate completions & manpage
* feat: run matcher over chunks
* chore: adjust penalties to keep typos under subsequences
* chore: accept snapshot
* fix: replace greedy ordered prefilter with looser unordered
* chore: finish up rename
* chore: review
---------
Co-authored-by: Skim bot <skim-bot@skim-rs.github.io>
