diff options
Diffstat (limited to 'src')
| -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 |
8 files changed, 208 insertions, 55 deletions
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) } |