mirror of
https://github.com/lotabout/skim.git
synced 2026-09-10 07:16:23 -04:00
c65274441a
* 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 commit9c8571ebe8. * Revert "refactor: replace unsafe transmute in Cell::dir() and compute_cell with safe match" This reverts commit8805fa14ce. * Revert "perf: Atom::is_sep() trait method avoids u8→char→u32 in separator check" This reverts commit175f26af81. * Revert "perf: early exit in count_tail_present_ordered when match is impossible" This reverts commit29721558f0. * Revert "perf: 128-bit ASCII bitset for cheap_typo_prefilter tail scan" This reverts commitd79947fcb5. * Revert "refactor: extract match_slices_range; simplify run_range" This reverts commit0fb7f05513. * Revert "perf(skim_v3): replace RefCell with UnsafeCell (TLCell) in thread-locals" This reverts commit0806683251. * Revert "perf(skim_v3): add ASCII fast path to char::eq_ignore_case" This reverts commit069710ad7c. * Revert "revert(skim_v3): restore m upper bound in typo_vband_row" This reverts commit90ffc46633. * Revert "perf(skim_v3): tighten typo-mode upper band bound in typo_vband_row" This reverts commitf38ca3a10d. * Revert "perf(skim_v3): avoid clone in traceback by using mem::take on thread-local buffer" This reverts commitffa9a21167. * Revert "perf(skim_v3): add early termination when DP rows are all-zero" This reverts commit073195be58. * Revert "perf(skim_v3): use 2-row rolling buffer for score-only DP path" This reverts commit3acacaad74. * 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>
180 lines
8.2 KiB
Plaintext
180 lines
8.2 KiB
Plaintext
module completions {
|
|
|
|
def "nu-complete sk tiebreak" [] {
|
|
[ "score" "-score" "begin" "-begin" "end" "-end" "length" "-length" "index" "-index" ]
|
|
}
|
|
|
|
def "nu-complete sk algorithm" [] {
|
|
[ "skim_v1" "skim_v2" "clangd" "fzy" "frizbee" "arinae" ]
|
|
}
|
|
|
|
def "nu-complete sk case" [] {
|
|
[ "respect" "ignore" "smart" ]
|
|
}
|
|
|
|
def "nu-complete sk layout" [] {
|
|
[ "default" "reverse" "reverse-list" ]
|
|
}
|
|
|
|
def "nu-complete sk info" [] {
|
|
[ "default" "inline" "hidden" ]
|
|
}
|
|
|
|
def "nu-complete sk border" [] {
|
|
[ "plain" "rounded" "double" "thick" "light-double-dashed" "heavy-double-dashed" "light-triple-dashed" "heavy-triple-dashed" "light-quadruple-dashed" "heavy-quadruple-dashed" "quadrant-inside" "quadrant-outside" ]
|
|
}
|
|
|
|
def "nu-complete sk shell" [] {
|
|
[ "bash" "elvish" "fish" "nushell" "power-shell" "zsh" ]
|
|
}
|
|
|
|
def "nu-complete sk flags" [] {
|
|
[ "no-preview-pty" "show-score" ]
|
|
}
|
|
|
|
# Fuzzy Finder in rust!
|
|
export extern sk [
|
|
--tac # Show results in reverse order
|
|
--min-query-length: string # Minimum query length to start showing results
|
|
--no-sort # Do not sort the results
|
|
--tiebreak(-t): string@"nu-complete sk tiebreak" # Comma-separated list of sort criteria to apply when the scores are tied.
|
|
--nth(-n): string # Fields to be matched
|
|
--with-nth: string # Fields to be transformed
|
|
--delimiter(-d): string # Delimiter between fields
|
|
--exact(-e) # Run in exact mode
|
|
--regex # Start in regex mode instead of fuzzy-match
|
|
--algo: string@"nu-complete sk algorithm" # Fuzzy matching algorithm
|
|
--case: string@"nu-complete sk case" # Case sensitivity
|
|
--typos: string # Enable typo-tolerant matching
|
|
--no-typos # Disable typo-resistant matching
|
|
--normalize # Normalize unicode characters
|
|
--split-match: string # Enable split matching and set delimiter
|
|
--bind(-b): string # Comma separated list of bindings
|
|
--multi(-m) # Enable multiple selection
|
|
--no-multi # Disable multiple selection
|
|
--no-mouse # Disable mouse
|
|
--cmd(-c): string # Command to invoke dynamically in interactive mode
|
|
--interactive(-i) # Start skim in interactive mode
|
|
-I: string # Replace replstr with the selected item in commands
|
|
--color: string # Set color theme
|
|
--no-hscroll # Disable horizontal scroll
|
|
--keep-right # Keep the right end of the line visible on overflow
|
|
--skip-to-pattern: string # Show the matched pattern at the line start
|
|
--no-clear-if-empty # Do not clear previous line if the command returns an empty result
|
|
--no-clear-start # Do not clear items on start
|
|
--no-clear # Do not clear screen on exit
|
|
--show-cmd-error # Show error message if command fails
|
|
--cycle # Cycle the results by wrapping around when scrolling
|
|
--disabled # Disable matching entirely
|
|
--layout: string@"nu-complete sk layout" # Set layout
|
|
--reverse # Shorthand for reverse layout
|
|
--height: string # Height of skim's window
|
|
--no-height # Disable height (force full screen)
|
|
--min-height: string # Minimum height of skim's window
|
|
--margin: string # Screen margin
|
|
--prompt(-p): string # Set prompt
|
|
--cmd-prompt: string # Set prompt in command mode
|
|
--selector: string # Set selected item icon
|
|
--multi-selector: string # Set selected item icon
|
|
--ansi # Parse ANSI color codes in input strings
|
|
--tabstop: string # Number of spaces that make up a tab
|
|
--ellipsis: string # The characters used to display truncated lines
|
|
--info: string@"nu-complete sk info" # Set matching result count display position
|
|
--no-info # Alias for --info=hidden
|
|
--inline-info # Alias for --info=inline
|
|
--header: string # Set header, displayed next to the info
|
|
--header-lines: string # Number of lines of the input treated as header
|
|
--border: string@"nu-complete sk border" # Draw borders around the UI components
|
|
--wrap # Wrap items in the item list
|
|
--history: string # History file
|
|
--history-size: string # Maximum number of query history entries to keep
|
|
--cmd-history: string # Command history file
|
|
--cmd-history-size: string # Maximum number of query history entries to keep
|
|
--preview: string # Preview command
|
|
--preview-window: string # Preview window layout
|
|
--query(-q): string # Initial query
|
|
--cmd-query: string # Initial query in interactive mode
|
|
--read0 # Read input delimited by ASCII NUL(\0) characters
|
|
--print0 # Print output delimited by ASCII NUL(\0) characters
|
|
--print-query # Print the query as the first line
|
|
--print-cmd # Print the command as the first line (after print-query)
|
|
--print-score # Print the score after each item
|
|
--print-header # Print the header as the first line (after print-score)
|
|
--print-current # Print the current (highlighted) item as the first line (after print-header)
|
|
--output-format: string # Set the output format If set, overrides all print_ options Will be expanded the same way as preview or commands
|
|
--no-strip-ansi # Print the ANSI codes, making the output exactly match the input even when --ansi is on
|
|
--select-1(-1) # Do not enter the TUI if the query passed in -q matches only one item and return it
|
|
--exit-0(-0) # Do not enter the TUI if the query passed in -q does not match any item
|
|
--sync # Synchronous search for multi-staged filtering
|
|
--pre-select-n: string # Pre-select the first n items in multi-selection mode
|
|
--pre-select-pat: string # Pre-select the matched items in multi-selection mode
|
|
--pre-select-items: string # Pre-select the items separated by newline character
|
|
--pre-select-file: string # Pre-select the items read from this file
|
|
--filter(-f): string # Query for filter mode
|
|
--shell: string@"nu-complete sk shell" # Generate shell completion script
|
|
--shell-bindings # Generate shell key bindings - only for bash, zsh and fish
|
|
--man # Generate man page and output it to stdout
|
|
--listen: string # Run an IPC socket with optional name (defaults to sk)
|
|
--remote: string # Send commands to an IPC socket with optional name (defaults to sk)
|
|
--tmux: string # Run in a tmux popup
|
|
--log-file: string # Pipe log output to a file
|
|
--flags: string@"nu-complete sk flags" # Feature flags
|
|
--extended(-x)
|
|
--literal
|
|
--hscroll-off: string
|
|
--filepath-word
|
|
--jump-labels: string
|
|
--no-bold
|
|
--phony
|
|
--scheme: string
|
|
--tail: string
|
|
--style: string
|
|
--no-color
|
|
--padding: string
|
|
--border-label: string
|
|
--border-label-pos: string
|
|
--highlight-line
|
|
--wrap-sign: string
|
|
--no-multi-line
|
|
--raw
|
|
--track
|
|
--gap: string
|
|
--gap-line: string
|
|
--freeze-left: string
|
|
--freeze-right: string
|
|
--scroll-off: string
|
|
--gutter: string
|
|
--gutter-raw: string
|
|
--marker-multi-line: string
|
|
--scrollbar: string
|
|
--no-scrollbar
|
|
--list-border: string
|
|
--list-label: string
|
|
--list-label-pos: string
|
|
--no-input
|
|
--info-command: string
|
|
--separator: string
|
|
--no-separator
|
|
--ghost: string
|
|
--input-border: string
|
|
--input-label: string
|
|
--input-label-pos: string
|
|
--preview-label: string
|
|
--preview-label-pos: string
|
|
--header-first
|
|
--header-border: string
|
|
--header-lines-border: string
|
|
--footer: string
|
|
--footer-border: string
|
|
--footer-label: string
|
|
--footer-label-pos: string
|
|
--with-shell: string
|
|
--expect: string # Deprecated, kept for compatibility purposes. See accept() bind instead
|
|
--help(-h) # Print help (see more with '--help')
|
|
--version(-V) # Print version
|
|
]
|
|
|
|
}
|
|
|
|
export use completions *
|