README
¶
This repo is an attempt to create a workable go-library from the amazing fzf package from Junegunn Choi.
For more information on the why and how, see this blogpost.
Performance
The goal of this library is to match the performance of the original fzf. Where possible, performance enhancing cache has been maintained (and moved into non-global locations, so that multiple fzf objects can live simultaneously). One of the places where a performance-changing change has been made is in returning the exacts characters that match the hit. In the original fzf, only the matching lines are returned, and only when displaying these in the console the exact characters are retrieved. This is obviously faster if one has a complex match that returns thousands of results where we only display a couple in the terminal. For now fzf-lib always returns machting character positions for all matches. Benchmarks shows that returning the positions has a 5-10% speed cost; considering the extreme speed of the fzf code, I hardly think anyone will miss these 5-10 percents. If this turns out to be a bottleneck, in the future we may consider alternative options.
The testing suite contains a benchmark, that fuzzy searches a string in a (repeating) list of quotes of different lengths. On my Macbook Pro M1, I got the following timings (this is from the moment a Search("hello world") command is given, until the full result is returned):
| Number of lines to search in | time until result (ms) |
|---|---|
| 1,024 | 0.709 |
| 2,048 | 1.140 |
| 4,096 | 2.483 |
| 8,192 | 4.787 |
| 16,384 | 6.814 |
| 32,768 | 12.86 |
| 65,536 | 24.92 |
| 131,072 | 48.95 |
| 262,144 | 95.65 |
| 524,288 | 190.9 |
| 1,048,576 | 380.1 |
| 2,097,152 | 767.5 (0.7s) |
| 4,194,304 | 1,577 (1.5s) |
| 8,388,608 | 3,173 (3s) |
| 16,777,216 | 6,588 (6.5s) |
| 33,554,432 | 33,098 (33s) |
It is hard to properly compare this to fzf --filter, since it's not clear how much is overhead / parsing the data, etc.
However the results are in the same order; you can see more info on my blog.
Obviously the results depend a lot on system and exact use, however I do think it's fair to say that up until 100k strings to search in, you should have a performance that will work for updating-the-results-while-typing, especially since that will have caching that was not taken into account here.
Note: There is also a RunBasicBenchmark function in the exported library. This is there so that some benchmarks can be run when the library is imported into another package. Since there are many transpilers for Go, this function may be used to compare pre and post transpile performance.
Installation
TODO
Usage
package main
import (
"fmt"
"github.com/reinhrst/fzf-lib"
"time"
"sync"
)
func main() {
var options = fzf.DefaultOptions()
// update any options here
var hayStack = []string{`hello world`, `hyo world`}
var myFzf = fzf.New(hayStack, options)
var result fzf.SearchResult
myFzf.Search(`^hel owo`)
result = <- myFzf.GetResultChannel()
fmt.Printf("%#v", result)
time.Sleep(200 * time.Millisecond)
myFzf.Search(`^hy owo`)
result = <- myFzf.GetResultChannel()
fmt.Printf("%#v", result)
myFzf.End() // Note: not strictly necessary since end of program
}
Note: If the channel is not being read, the search go routine will block
The following options can be set (most are 1-on-1 matches to fzf commandline optioens with the same name
// If true, each word (separated by non-escaped spaces) is an independent
// searchterm. If false, all spaces are literal
Extended bool
// if true, default is Fuzzy search (' escapes to make exact search)
// if false, default is exact search (' escapes to make fuzzy search)
Fuzzy bool
// CaseRespect, CaseIgnore or CaseSmart
// CaseSmart matches case insensitive if the needle is all lowercase, else case sensitive
CaseMode Case
// set to False to get fzf --literal behaviour:
// "Do not normalize latin script letters for matching."
Normalize bool
// Array with options from {ByScore, ByLength, ByBegin, ByEnd}.
// Metches will first be sorted by the first element, ties will be sorted by
// second element, etc.
// ByScore: Each match is scored (see algo file for more info), higher score
// comes first
// ByLength: Shorter match wins
// ByBegin: Match closer to begin of string wins
// ByEnd: Match closer to end of string wins
//
// If all methods give equal score (including when the Sort slice is empty),
// the result is sorted by HayIndex, the order in which they appeared in
// the input.
Sort []Criterion
The DefaultOptions are as follows:
func DefaultOptions() Options {
return Options{
Extended: true,
Fuzzy: true,
CaseMode: CaseSmart,
Normalize: true,
Sort: []Criterion{ByScore, ByLength},
}
}
FAQ
Where are all other useful options
The idea is that most other useful options in fzf cli are easy to build in your client program. Please see this blog post for more information.
Why does this look nothing like a proper golang module/library
Quite honestly, because this is my first Go project that I'm working on. I appreciate any feedback on how to make it better.
What version of fzf is this code based on
The code was cloned from the fzf master branch on 8 June 2021, latest commit being 7191ebb615f5d6ebbf51d598d8ec853a65e2274d.
This means that it's basically version 0.27.2, with some bug fixes.
Fzf follows its own version numbering scheme, where we creep up on v1.0 for a production ready release.
The old git tags (with fzf releases) have been removed from the github repository.
What is still missing
The wishlist for v1.0 is (in addition to extra (stress)tests):
- Send SearchProgess messages on the result channel if the search takes more than 200ms, so that a progress bar can be shown
- See if we can automatically call
myFzf.End()when the item goes out of scope. - Allow selection of algorithm v1, in case someone would want that.
- Probably some work to make this act nicely in the Go ecosystem.
Appreciation / Thank You's / Coffee / Beer
If you like the project, I always appeciate feedback (on my blog), in the issues or by starring this repository. I still have a dream that one day I'll be able to have fans pay for my coffees and beers; when that time comes, you'll find a button here!
Documentation
¶
Index ¶
- Constants
- Variables
- func CountItems(cs []*Chunk) int
- func RunBasicBenchmark()
- type ByOrder
- type ByRelevance
- type ByRelevanceTac
- type Case
- type Chunk
- type ChunkCache
- type ChunkList
- type Criterion
- type Fzf
- type History
- type Item
- type ItemBuilder
- type MatchRequest
- type MatchResult
- type Matcher
- type Merger
- type Offset
- type Options
- type Pattern
- type Result
- type SearchResult
Constants ¶
const ( EvtSearchProgress util.EventType = iota EvtSearchFin EvtQuit )
fzf events
Variables ¶
EmptyMerger is a Merger with no data
Functions ¶
func RunBasicBenchmark ¶ added in v0.8.6
func RunBasicBenchmark()
A function that creates a fully internal benchmark, that can be compared in different environments. Note that the benchmark is super basic; use the benchmarks in the test suite if you can
Types ¶
type ByRelevance ¶
type ByRelevance []Result
ByRelevance is for sorting Items
func (ByRelevance) Len ¶
func (a ByRelevance) Len() int
func (ByRelevance) Less ¶
func (a ByRelevance) Less(i, j int) bool
func (ByRelevance) Swap ¶
func (a ByRelevance) Swap(i, j int)
type ByRelevanceTac ¶
type ByRelevanceTac []Result
ByRelevanceTac is for sorting Items
func (ByRelevanceTac) Len ¶
func (a ByRelevanceTac) Len() int
func (ByRelevanceTac) Less ¶
func (a ByRelevanceTac) Less(i, j int) bool
func (ByRelevanceTac) Swap ¶
func (a ByRelevanceTac) Swap(i, j int)
type Chunk ¶
type Chunk struct {
// contains filtered or unexported fields
}
Chunk is a list of Items whose size has the upper limit of chunkSize
type ChunkCache ¶
type ChunkCache struct {
// contains filtered or unexported fields
}
ChunkCache associates Chunk and query string to lists of items
func (*ChunkCache) Add ¶
func (cc *ChunkCache) Add(chunk *Chunk, key string, list []Result)
Add adds the list to the cache
type ChunkList ¶
type ChunkList struct {
// contains filtered or unexported fields
}
ChunkList is a list of Chunks
func NewChunkList ¶
func NewChunkList(trans ItemBuilder) *ChunkList
NewChunkList returns a new ChunkList
type Fzf ¶
type Fzf struct {
// contains filtered or unexported fields
}
func (*Fzf) GetResultChannel ¶ added in v0.9.0
func (fzf *Fzf) GetResultChannel() <-chan SearchResult
type History ¶
type History struct {
// contains filtered or unexported fields
}
History struct represents input history
type Item ¶
type Item struct {
// contains filtered or unexported fields
}
Item represents each input line. 56 bytes.
func (*Item) TrimLength ¶
type ItemBuilder ¶
ItemBuilder is a closure type that builds Item object from byte array
type MatchRequest ¶
type MatchRequest struct {
// contains filtered or unexported fields
}
MatchRequest represents a search request
type Matcher ¶
type Matcher struct {
// contains filtered or unexported fields
}
Matcher is responsible for performing search
type Merger ¶
type Merger struct {
// contains filtered or unexported fields
}
Merger holds a set of locally sorted lists of items and provides the view of a single, globally-sorted list
func PassMerger ¶
PassMerger returns a new Merger that simply returns the items in the original order
type Offset ¶
type Offset [2]int32
Offset holds two 32-bit integers denoting the offsets of a matched substring
type Options ¶
type Options struct {
// If true, each word (separated by non-escaped spaces) is an independent
// searchterm. If false, all spaces are literal
Extended bool
// if true, default is Fuzzy search (' escapes to make exact search)
// if false, default is exact search (' escapes to make fuzzy search)
Fuzzy bool
// CaseRespect, CaseIgnore or CaseSmart
// CaseSmart matches case insensitive if the needle is all lowercase, else case sensitive
CaseMode Case
// set to False to get fzf --literal behaviour:
// "Do not normalize latin script letters for matching."
Normalize bool
// Array with options from {ByScore, ByLength, ByBegin, ByEnd}.
// Metches will first be sorted by the first element, ties will be sorted by
// second element, etc.
// ByScore: Each match is scored (see algo file for more info), higher score
// comes first
// ByLength: Shorter match wins
// ByBegin: Match closer to begin of string wins
// ByEnd: Match closer to end of string wins
//
// If all methods give equal score (including when the Sort slice is empty),
// the result is sorted by HayIndex, the order in which they appeared in
// the input.
Sort []Criterion
}
func DefaultOptions ¶
func DefaultOptions() Options
type Pattern ¶
type Pattern struct {
// contains filtered or unexported fields
}
Pattern represents search pattern
func BuildPattern ¶
func BuildPattern(fuzzy bool, fuzzyAlgo algo.Algo, extended bool, caseMode Case, normalize bool, forward bool, needle string, sortCriteria []Criterion, patternCache *map[string]*Pattern) *Pattern
buildPattern builds Pattern object from the given arguments
type SearchResult ¶
type SearchResult struct {
Needle string
SearchOptions Options
Matches []MatchResult
}
Source Files
Directories