diff options
author | Junegunn Choi <junegunn.c@gmail.com> | 2024-06-04 15:48:38 +0900 |
---|---|---|
committer | Junegunn Choi <junegunn.c@gmail.com> | 2024-06-04 17:50:46 +0900 |
commit | 93bbb3032d1e7550dbabb2d450999cd434c60509 (patch) | |
tree | f6b4331975184172b256c71335f5964bcddc77df | |
parent | 4c83d8596d48acc106ffe62d50a55b3f9608c830 (diff) |
Add --tail=NUM to limit the number of items to keep in memory
-rw-r--r-- | CHANGELOG.md | 9 | ||||
-rw-r--r-- | man/man1/fzf.1 | 10 | ||||
-rw-r--r-- | src/chunklist.go | 48 | ||||
-rw-r--r-- | src/chunklist_test.go | 42 | ||||
-rw-r--r-- | src/core.go | 44 | ||||
-rw-r--r-- | src/matcher.go | 35 | ||||
-rw-r--r-- | src/merger.go | 32 | ||||
-rw-r--r-- | src/merger_test.go | 15 | ||||
-rw-r--r-- | src/options.go | 18 | ||||
-rw-r--r-- | src/terminal.go | 29 |
10 files changed, 226 insertions, 56 deletions
diff --git a/CHANGELOG.md b/CHANGELOG.md index 7fce1944..6db23ac2 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -42,7 +42,14 @@ CHANGELOG ```vim let g:fzf_layout = { 'tmux': '100%,70%' } ``` -- (Windows) fzf now works on Git bash (mintty) out of the box via winpty integration +- Better Windows Support + - fzf now works on Git bash (mintty) out of the box via winpty integration + - Many fixes and improvements for Windows +- Added `--tail=NUM` option to limit the number of items to keep in memory. This is useful when you want to browse an endless stream of data (e.g. log stream) with fzf while limiting memory usage. + ```sh + # Interactive filtering of a log stream + tail -f *.log | fzf --tail 100000 --tac --no-sort --exact + ``` - man page is now embedded in the binary; `fzf --man` to see it - Changed the default `--scroll-off` to 3, as we think it's a better default - Process started by `execute` action now directly writes to and reads from `/dev/tty`. Manual `/dev/tty` redirection for interactive programs is no longer required. diff --git a/man/man1/fzf.1 b/man/man1/fzf.1 index f1bf04af..d636db22 100644 --- a/man/man1/fzf.1 +++ b/man/man1/fzf.1 @@ -99,6 +99,16 @@ interface rather than a "fuzzy finder". You can later enable the search using .B "+s, --no-sort" Do not sort the result .TP +.B "--tail=NUM" +Maximum number of items to keep in memory. This is useful when you want to +browse an endless stream of data (e.g. log stream) with fzf while limiting +memory usage. +.RS +e.g. + \fB# Interactive filtering of a log stream + tail -f *.log | fzf --tail 100000 --tac --no-sort --exact\fR +.RE +.TP .B "--track" Make fzf track the current selection when the result list is updated. This can be useful when browsing logs using fzf with sorting disabled. It is diff --git a/src/chunklist.go b/src/chunklist.go index cd635c25..91177b17 100644 --- a/src/chunklist.go +++ b/src/chunklist.go @@ -48,7 +48,12 @@ func CountItems(cs []*Chunk) int { if len(cs) == 0 { return 0 } - return chunkSize*(len(cs)-1) + cs[len(cs)-1].count + if len(cs) == 1 { + return cs[0].count + } + + // First chunk might not be full due to --tail=N + return cs[0].count + chunkSize*(len(cs)-2) + cs[len(cs)-1].count } // Push adds the item to the list @@ -72,18 +77,53 @@ func (cl *ChunkList) Clear() { } // Snapshot returns immutable snapshot of the ChunkList -func (cl *ChunkList) Snapshot() ([]*Chunk, int) { +func (cl *ChunkList) Snapshot(tail int) ([]*Chunk, int, bool) { cl.mutex.Lock() + changed := false + if tail > 0 && CountItems(cl.chunks) > tail { + changed = true + // Find the number of chunks to keep + numChunks := 0 + for left, i := tail, len(cl.chunks)-1; left > 0 && i >= 0; i-- { + numChunks++ + left -= cl.chunks[i].count + } + + // Copy the chunks to keep + ret := make([]*Chunk, numChunks) + copy(ret, cl.chunks[len(cl.chunks)-numChunks:]) + + for left, i := tail, len(ret)-1; i >= 0; i-- { + chunk := ret[i] + if chunk.count > left { + newChunk := *chunk + newChunk.count = left + oldCount := chunk.count + for i := 0; i < left; i++ { + newChunk.items[i] = chunk.items[oldCount-left+i] + } + ret[i] = &newChunk + break + } + left -= chunk.count + } + cl.chunks = ret + } + ret := make([]*Chunk, len(cl.chunks)) copy(ret, cl.chunks) - // Duplicate the last chunk + // Duplicate the first and the last chunk if cnt := len(ret); cnt > 0 { + if tail > 0 && cnt > 1 { + newChunk := *ret[0] + ret[0] = &newChunk + } newChunk := *ret[cnt-1] ret[cnt-1] = &newChunk } cl.mutex.Unlock() - return ret, CountItems(ret) + return ret, CountItems(ret), changed } diff --git a/src/chunklist_test.go b/src/chunklist_test.go index 6c1d09eb..c07e4adf 100644 --- a/src/chunklist_test.go +++ b/src/chunklist_test.go @@ -17,7 +17,7 @@ func TestChunkList(t *testing.T) { }) // Snapshot - snapshot, count := cl.Snapshot() + snapshot, count, _ := cl.Snapshot(0) if len(snapshot) > 0 || count > 0 { t.Error("Snapshot should be empty now") } @@ -32,7 +32,7 @@ func TestChunkList(t *testing.T) { } // But the new snapshot should contain the added items - snapshot, count = cl.Snapshot() + snapshot, count, _ = cl.Snapshot(0) if len(snapshot) != 1 && count != 2 { t.Error("Snapshot should not be empty now") } @@ -61,7 +61,7 @@ func TestChunkList(t *testing.T) { } // New snapshot - snapshot, count = cl.Snapshot() + snapshot, count, _ = cl.Snapshot(0) if len(snapshot) != 3 || !snapshot[0].IsFull() || !snapshot[1].IsFull() || snapshot[2].IsFull() || count != chunkSize*2+2 { t.Error("Expected two full chunks and one more chunk") @@ -78,3 +78,39 @@ func TestChunkList(t *testing.T) { t.Error("Unexpected number of items:", lastChunkCount) } } + +func TestChunkListTail(t *testing.T) { + cl := NewChunkList(func(item *Item, s []byte) bool { + item.text = util.ToChars(s) + return true + }) + total := chunkSize*2 + chunkSize/2 + for i := 0; i < total; i++ { + cl.Push([]byte(fmt.Sprintf("item %d", i))) + } + + snapshot, count, changed := cl.Snapshot(0) + assertCount := func(expected int, shouldChange bool) { + if count != expected || CountItems(snapshot) != expected { + t.Errorf("Unexpected count: %d (expected: %d)", count, expected) + } + if changed != shouldChange { + t.Error("Unexpected change status") + } + } + assertCount(total, false) + + tail := chunkSize + chunkSize/2 + snapshot, count, changed = cl.Snapshot(tail) + assertCount(tail, true) + + snapshot, count, changed = cl.Snapshot(tail) + assertCount(tail, false) + + snapshot, count, changed = cl.Snapshot(0) + assertCount(tail, false) + + tail = chunkSize / 2 + snapshot, count, changed = cl.Snapshot(tail) + assertCount(tail, true) +} diff --git a/src/core.go b/src/core.go index 0c7abff1..f2563a08 100644 --- a/src/core.go +++ b/src/core.go @@ -18,6 +18,28 @@ Matcher -> EvtSearchFin -> Terminal (update list) Matcher -> EvtHeader -> Terminal (update header) */ +type revision struct { + major int + minor int +} + +func (r *revision) bumpMajor() { + r.major++ + r.minor = 0 +} + +func (r *revision) bumpMinor() { + r.minor++ +} + +func (r revision) equals(other revision) bool { + return r.major == other.major && r.minor == other.minor +} + +func (r revision) compatible(other revision) bool { + return r.major == other.major +} + // Run starts fzf func Run(opts *Options) (int, error) { if opts.Tmux != nil && len(os.Getenv("TMUX")) > 0 && opts.Tmux.index >= opts.Height.index { @@ -155,8 +177,8 @@ func Run(opts *Options) (int, error) { opts.Fuzzy, opts.FuzzyAlgo, opts.Extended, opts.Case, opts.Normalize, forward, withPos, opts.Filter == nil, opts.Nth, opts.Delimiter, runes) } - inputRevision := 0 - snapshotRevision := 0 + inputRevision := revision{} + snapshotRevision := revision{} matcher := NewMatcher(cache, patternBuilder, sort, opts.Tac, eventBox, inputRevision) // Filtering mode @@ -190,7 +212,8 @@ func Run(opts *Options) (int, error) { eventBox.Unwatch(EvtReadNew) eventBox.WaitFor(EvtReadFin) - snapshot, _ := chunkList.Snapshot() + // NOTE: Streaming filter is inherently not compatible with --tail + snapshot, _, _ := chunkList.Snapshot(opts.Tail) merger, _ := matcher.scan(MatchRequest{ chunks: snapshot, pattern: pattern}) @@ -261,7 +284,7 @@ func Run(opts *Options) (int, error) { reading = true chunkList.Clear() itemIndex = 0 - inputRevision++ + inputRevision.bumpMajor() header = make([]string, 0, opts.HeaderLines) go reader.restart(command, environ) } @@ -306,10 +329,14 @@ func Run(opts *Options) (int, error) { useSnapshot = false } if !useSnapshot { - if snapshotRevision != inputRevision { + if !snapshotRevision.compatible(inputRevision) { query = []rune{} } - snapshot, count = chunkList.Snapshot() + var changed bool + snapshot, count, changed = chunkList.Snapshot(opts.Tail) + if changed { + inputRevision.bumpMinor() + } snapshotRevision = inputRevision } total = count @@ -349,7 +376,10 @@ func Run(opts *Options) (int, error) { break } if !useSnapshot { - newSnapshot, newCount := chunkList.Snapshot() + newSnapshot, newCount, changed := chunkList.Snapshot(opts.Tail) + if changed { + inputRevision.bumpMinor() + } // We want to avoid showing empty list when reload is triggered // and the query string is changed at the same time i.e. command != nil && changed if command == nil || newCount > 0 { diff --git a/src/matcher.go b/src/matcher.go index 26426e4f..869663fa 100644 --- a/src/matcher.go +++ b/src/matcher.go @@ -16,7 +16,7 @@ type MatchRequest struct { pattern *Pattern final bool sort bool - revision int + revision revision } // Matcher is responsible for performing search @@ -30,7 +30,7 @@ type Matcher struct { partitions int slab []*util.Slab mergerCache map[string]*Merger - revision int + revision revision } const ( @@ -40,7 +40,7 @@ const ( // NewMatcher returns a new Matcher func NewMatcher(cache *ChunkCache, patternBuilder func([]rune) *Pattern, - sort bool, tac bool, eventBox *util.EventBox, revision int) *Matcher { + sort bool, tac bool, eventBox *util.EventBox, revision revision) *Matcher { partitions := util.Min(numPartitionsMultiplier*runtime.NumCPU(), maxPartitions) return &Matcher{ cache: cache, @@ -82,11 +82,13 @@ func (m *Matcher) Loop() { break } + cacheCleared := false if request.sort != m.sort || request.revision != m.revision { m.sort = request.sort m.revision = request.revision m.mergerCache = make(map[string]*Merger) m.cache.Clear() + cacheCleared = true } // Restart search @@ -95,20 +97,20 @@ func (m *Matcher) Loop() { cancelled := false count := CountItems(request.chunks) - foundCache := false - if count == prevCount { - // Look up mergerCache - if cached, found := m.mergerCache[patternString]; found { - foundCache = true - merger = cached + if !cacheCleared { + if count == prevCount { + // Look up mergerCache + if cached, found := m.mergerCache[patternString]; found { + merger = cached + } + } else { + // Invalidate mergerCache + prevCount = count + m.mergerCache = make(map[string]*Merger) } - } else { - // Invalidate mergerCache - prevCount = count - m.mergerCache = make(map[string]*Merger) } - if !foundCache { + if merger == nil { merger, cancelled = m.scan(request) } @@ -160,6 +162,7 @@ func (m *Matcher) scan(request MatchRequest) (*Merger, bool) { return PassMerger(&request.chunks, m.tac, request.revision), false } + minIndex := request.chunks[0].items[0].Index() cancelled := util.NewAtomicBool(false) slices := m.sliceChunks(request.chunks) @@ -231,11 +234,11 @@ func (m *Matcher) scan(request MatchRequest) (*Merger, bool) { partialResult := <-resultChan partialResults[partialResult.index] = partialResult.matches } - return NewMerger(pattern, partialResults, m.sort, m.tac, request.revision), false + return NewMerger(pattern, partialResults, m.sort, m.tac, request.revision, minIndex), false } // Reset is called to interrupt/signal the ongoing search -func (m *Matcher) Reset(chunks []*Chunk, patternRunes []rune, cancel bool, final bool, sort bool, revision int) { +func (m *Matcher) Reset(chunks []*Chunk, patternRunes []rune, cancel bool, final bool, sort bool, revision revision) { pattern := m.patternBuilder(patternRunes) var event util.EventType diff --git a/src/merger.go b/src/merger.go index 6a235043..fee8a59a 100644 --- a/src/merger.go +++ b/src/merger.go @@ -3,8 +3,8 @@ package fzf import "fmt" // EmptyMerger is a Merger with no data -func EmptyMerger(revision int) *Merger { - return NewMerger(nil, [][]Result{}, false, false, revision) +func EmptyMerger(revision revision) *Merger { + return NewMerger(nil, [][]Result{}, false, false, revision, 0) } // Merger holds a set of locally sorted lists of items and provides the view of @@ -20,19 +20,25 @@ type Merger struct { final bool count int pass bool - revision int + revision revision + minIndex int32 } // PassMerger returns a new Merger that simply returns the items in the // original order -func PassMerger(chunks *[]*Chunk, tac bool, revision int) *Merger { +func PassMerger(chunks *[]*Chunk, tac bool, revision revision) *Merger { + var minIndex int32 + if len(*chunks) > 0 { + minIndex = (*chunks)[0].items[0].Index() + } mg := Merger{ pattern: nil, chunks: chunks, tac: tac, count: 0, pass: true, - revision: revision} + revision: revision, + minIndex: minIndex} for _, chunk := range *mg.chunks { mg.count += chunk.count @@ -41,7 +47,7 @@ func PassMerger(chunks *[]*Chunk, tac bool, revision int) *Merger { } // NewMerger returns a new Merger -func NewMerger(pattern *Pattern, lists [][]Result, sorted bool, tac bool, revision int) *Merger { +func NewMerger(pattern *Pattern, lists [][]Result, sorted bool, tac bool, revision revision, minIndex int32) *Merger { mg := Merger{ pattern: pattern, lists: lists, @@ -52,7 +58,8 @@ func NewMerger(pattern *Pattern, lists [][]Result, sorted bool, tac bool, revisi tac: tac, final: false, count: 0, - revision: revision} + revision: revision, + minIndex: minIndex} for _, list := range mg.lists { mg.count += len(list) @@ -61,7 +68,7 @@ func NewMerger(pattern *Pattern, lists [][]Result, sorted bool, tac bool, revisi } // Revision returns revision number -func (mg *Merger) Revision() int { +func (mg *Merger) Revision() revision { return mg.revision } @@ -81,7 +88,7 @@ func (mg *Merger) First() Result { func (mg *Merger) FindIndex(itemIndex int32) int { index := -1 if mg.pass { - index = int(itemIndex) + index = int(itemIndex - mg.minIndex) if mg.tac { index = mg.count - index - 1 } @@ -102,6 +109,13 @@ func (mg *Merger) Get(idx int) Result { if mg.tac { idx = mg.count - idx - 1 } + firstChunk := (*mg.chunks)[0] + if firstChunk.count < chunkSize && idx >= firstChunk.count { + idx -= firstChunk.count + + chunk := (*mg.chunks)[idx/chunkSize+1] + return Result{item: &chunk.items[idx%chunkSize]} + } chunk := (*mg.chunks)[idx/chunkSize] return Result{item: &chunk.items[idx%chunkSize]} } diff --git a/src/merger_test.go b/src/merger_test.go index 5fd1576f..a6b28f6e 100644 --- a/src/merger_test.go +++ b/src/merger_test.go @@ -23,10 +23,11 @@ func randResult() Result { } func TestEmptyMerger(t *testing.T) { - assert(t, EmptyMerger(0).Length() == 0, "Not empty") - assert(t, EmptyMerger(0).count == 0, "Invalid count") - assert(t, len(EmptyMerger(0).lists) == 0, "Invalid lists") - assert(t, len(EmptyMerger(0).merged) == 0, "Invalid merged list") + r := revision{} + assert(t, EmptyMerger(r).Length() == 0, "Not empty") + assert(t, EmptyMerger(r).count == 0, "Invalid count") + assert(t, len(EmptyMerger(r).lists) == 0, "Invalid lists") + assert(t, len(EmptyMerger(r).merged) == 0, "Invalid merged list") } func buildLists(partiallySorted bool) ([][]Result, []Result) { @@ -57,7 +58,7 @@ func TestMergerUnsorted(t *testing.T) { cnt := len(items) // Not sorted: same order - mg := NewMerger(nil, lists, false, false, 0) + mg := NewMerger(nil, lists, false, false, revision{}, 0) assert(t, cnt == mg.Length(), "Invalid Length") for i := 0; i < cnt; i++ { assert(t, items[i] == mg.Get(i), "Invalid Get") @@ -69,7 +70,7 @@ func TestMergerSorted(t *testing.T) { cnt := len(items) // Sorted sorted order - mg := NewMerger(nil, lists, true, false, 0) + mg := NewMerger(nil, lists, true, false, revision{}, 0) assert(t, cnt == mg.Length(), "Invalid Length") sort.Sort(ByRelevance(items)) for i := 0; i < cnt; i++ { @@ -79,7 +80,7 @@ func TestMergerSorted(t *testing.T) { } // Inverse order - mg2 := NewMerger(nil, lists, true, false, 0) + mg2 := NewMerger(nil, lists, true, false, revision{}, 0) for i := cnt - 1; i >= 0; i-- { if items[i] != mg2.Get(i) { t.Error("Not sorted", items[i], mg2.Get(i)) diff --git a/src/options.go b/src/options.go index 25bfd317..35784e5c 100644 --- a/src/options.go +++ b/src/options.go @@ -41,6 +41,7 @@ Usage: fzf [options] field index expressions -d, --delimiter=STR Field delimiter regex (default: AWK-style) +s, --no-sort Do not sort the result + --tail=NUM Maximum number of items to keep in memory --track Track the current selection when the result is updated --tac Reverse the order of the input --disabled Do not perform search @@ -421,6 +422,7 @@ type Options struct { Sort int Track trackOption Tac bool + Tail int Criteria []criterion Multi int Ansi bool @@ -2096,6 +2098,15 @@ func parseOptions(index *int, opts *Options, allArgs []string) error { opts.Tac = true case "--no-tac": opts.Tac = false + case "--tail": + if opts.Tail, err = nextInt(allArgs, &i, "number of items to keep required"); err != nil { + return err + } + if opts.Tail <= 0 { + return errors.New("number of items to keep must be a positive integer") + } + case "--no-tail": + opts.Tail = 0 case "-i", "--ignore-case": opts.Case = CaseIgnore case "+i", "--no-ignore-case": @@ -2631,6 +2642,13 @@ func parseOptions(index *int, opts *Options, allArgs []string) error { } else if match, value := optString(arg, "--jump-labels="); match { opts.JumpLabels = value validateJumpLabels = true + } else if match, value := optString(arg, "--tail="); match { + if opts.Tail, err = atoi(value); err != nil { + return err + } + if opts.Tail <= 0 { + return errors.New("number of items to keep must be a positive integer") + } } else { return errors.New("unknown option: " + arg) } diff --git a/src/terminal.go b/src/terminal.go index ff6295f1..caa2446e 100644 --- a/src/terminal.go +++ b/src/terminal.go @@ -160,6 +160,7 @@ type itemLine struct { result Result empty bool other bool + minIndex int32 } func (t *Terminal) markEmptyLine(line int) { @@ -301,7 +302,7 @@ type Terminal struct { merger *Merger selected map[int32]selectedItem version int64 - revision int + revision revision reqBox *util.EventBox initialPreviewOpts previewOpts previewOpts previewOpts @@ -822,7 +823,7 @@ func NewTerminal(opts *Options, eventBox *util.EventBox, executor *util.Executor printer: opts.Printer, printsep: opts.PrintSep, proxyScript: opts.ProxyScript, - merger: EmptyMerger(0), + merger: EmptyMerger(revision{}), selected: make(map[int32]selectedItem), reqBox: util.NewEventBox(), initialPreviewOpts: opts.Preview, @@ -1164,8 +1165,8 @@ func (t *Terminal) UpdateProgress(progress float32) { func (t *Terminal) UpdateList(merger *Merger, triggerResultEvent bool) { t.mutex.Lock() prevIndex := minItem.Index() - reset := t.revision != merger.Revision() - if !reset && t.track != trackDisabled { + newRevision := merger.Revision() + if t.revision.compatible(newRevision) && t.track != trackDisabled { if t.merger.Length() > 0 { prevIndex = t.currentIndex() } else if merger.Length() > 0 { @@ -1174,9 +1175,19 @@ func (t *Terminal) UpdateList(merger *Merger, triggerResultEvent bool) { } t.progress = 100 t.merger = merger - if reset { - t.selected = make(map[int32]selectedItem) - t.revision = merger.Revision() + if !t.revision.equals(newRevision) { + if !t.revision.compatible(newRevision) { // Reloaded: clear selection + t.selected = make(map[int32]selectedItem) + } else { // Trimmed by --tail: filter selection by index + filtered := make(map[int32]selectedItem) + for k, v := range t.selected { + if k >= merger.minIndex { + filtered[k] = v + } + } + t.selected = filtered + } + t.revision = newRevision t.version++ } if t.triggerLoad { @@ -1959,9 +1970,9 @@ func (t *Terminal) printItem(result Result, line int, maxLine int, index int, cu // Avoid unnecessary redraw newLine := itemLine{firstLine: line, cy: index + t.offset, current: current, selected: selected, label: label, - result: result, queryLen: len(t.input), width: 0, hasBar: line >= barRange[0] && line < barRange[1]} + result: result, queryLen: len(t.input), width: 0, hasBar: line >= barRange[0] && line < barRange[1], minIndex: t.merger.minIndex} prevLine := t.prevLines[line] - forceRedraw := prevLine.other || prevLine.firstLine != newLine.firstLine + forceRedraw := prevLine.other || prevLine.firstLine != newLine.firstLine || prevLine.minIndex != t.merger.minIndex printBar := func(lineNum int, forceRedraw bool) bool { return t.printBar(lineNum, forceRedraw, barRange) } |