diff options
| -rw-r--r-- | src/core.go | 11 | ||||
| -rw-r--r-- | src/item.go | 38 | ||||
| -rw-r--r-- | src/item_test.go | 10 | ||||
| -rw-r--r-- | src/matcher.go | 39 | ||||
| -rw-r--r-- | src/merger.go | 79 | ||||
| -rw-r--r-- | src/merger_test.go | 80 | ||||
| -rw-r--r-- | src/terminal.go | 28 |
7 files changed, 193 insertions, 92 deletions
diff --git a/src/core.go b/src/core.go index e5bdb129..98973f8b 100644 --- a/src/core.go +++ b/src/core.go @@ -93,17 +93,18 @@ func Run(options *Options) { } snapshot, _ := chunkList.Snapshot() - matches, cancelled := matcher.scan(MatchRequest{ + merger, cancelled := matcher.scan(MatchRequest{ chunks: snapshot, pattern: pattern}, limit) if !cancelled && (filtering || - opts.Exit0 && len(matches) == 0 || opts.Select1 && len(matches) == 1) { + opts.Exit0 && merger.Length() == 0 || + opts.Select1 && merger.Length() == 1) { if opts.PrintQuery { fmt.Println(patternString) } - for _, item := range matches { - item.Print() + for i := 0; i < merger.Length(); i++ { + merger.Get(i).Print() } os.Exit(0) } @@ -147,7 +148,7 @@ func Run(options *Options) { case EVT_SEARCH_FIN: switch val := value.(type) { - case []*Item: + case *Merger: terminal.UpdateList(val) } } diff --git a/src/item.go b/src/item.go index 4c8f13d4..60355b4c 100644 --- a/src/item.go +++ b/src/item.go @@ -104,41 +104,3 @@ func compareRanks(irank Rank, jrank Rank) bool { } return false } - -func SortMerge(partialResults [][]*Item) []*Item { - if len(partialResults) == 1 { - return partialResults[0] - } - - merged := []*Item{} - - for len(partialResults) > 0 { - minRank := Rank{0, 0, 0} - minIdx := -1 - - for idx, partialResult := range partialResults { - if len(partialResult) > 0 { - rank := partialResult[0].Rank() - if minIdx < 0 || compareRanks(rank, minRank) { - minRank = rank - minIdx = idx - } - } - } - - if minIdx >= 0 { - merged = append(merged, partialResults[minIdx][0]) - partialResults[minIdx] = partialResults[minIdx][1:] - } - - nonEmptyPartialResults := make([][]*Item, 0, len(partialResults)) - for _, partialResult := range partialResults { - if len(partialResult) > 0 { - nonEmptyPartialResults = append(nonEmptyPartialResults, partialResult) - } - } - partialResults = nonEmptyPartialResults - } - - return merged -} diff --git a/src/item_test.go b/src/item_test.go index 23b8718c..87d8be46 100644 --- a/src/item_test.go +++ b/src/item_test.go @@ -64,14 +64,4 @@ func TestItemRank(t *testing.T) { items[4] != &item5 || items[5] != &item3 { t.Error(items) } - - // Sort merged lists - lists := [][]*Item{ - []*Item{&item2, &item4, &item5}, []*Item{&item1, &item6}, []*Item{&item3}} - items = SortMerge(lists) - if items[0] != &item2 || items[1] != &item1 || - items[2] != &item6 || items[3] != &item4 || - items[4] != &item5 || items[5] != &item3 { - t.Error(items) - } } diff --git a/src/matcher.go b/src/matcher.go index ad782bdf..234e7033 100644 --- a/src/matcher.go +++ b/src/matcher.go @@ -18,7 +18,7 @@ type Matcher struct { eventBox *EventBox reqBox *EventBox partitions int - queryCache QueryCache + mergerCache map[string]*Merger } const ( @@ -44,7 +44,7 @@ func NewMatcher(patternBuilder func([]rune) *Pattern, eventBox: eventBox, reqBox: NewEventBox(), partitions: runtime.NumCPU(), - queryCache: make(QueryCache)} + mergerCache: make(map[string]*Merger)} } func (m *Matcher) Loop() { @@ -67,30 +67,30 @@ func (m *Matcher) Loop() { // Restart search patternString := request.pattern.AsString() - allMatches := []*Item{} + var merger *Merger cancelled := false count := CountItems(request.chunks) foundCache := false if count == prevCount { - // Look up queryCache - if cached, found := m.queryCache[patternString]; found { + // Look up mergerCache + if cached, found := m.mergerCache[patternString]; found { foundCache = true - allMatches = cached + merger = cached } } else { - // Invalidate queryCache + // Invalidate mergerCache prevCount = count - m.queryCache = make(QueryCache) + m.mergerCache = make(map[string]*Merger) } if !foundCache { - allMatches, cancelled = m.scan(request, 0) + merger, cancelled = m.scan(request, 0) } if !cancelled { - m.queryCache[patternString] = allMatches - m.eventBox.Set(EVT_SEARCH_FIN, allMatches) + m.mergerCache[patternString] = merger + m.eventBox.Set(EVT_SEARCH_FIN, merger) } } } @@ -120,12 +120,12 @@ type partialResult struct { matches []*Item } -func (m *Matcher) scan(request MatchRequest, limit int) ([]*Item, bool) { +func (m *Matcher) scan(request MatchRequest, limit int) (*Merger, bool) { startedAt := time.Now() numChunks := len(request.chunks) if numChunks == 0 { - return []*Item{}, false + return EmptyMerger, false } pattern := request.pattern empty := pattern.IsEmpty() @@ -188,18 +188,7 @@ func (m *Matcher) scan(request MatchRequest, limit int) ([]*Item, bool) { partialResult := <-resultChan partialResults[partialResult.index] = partialResult.matches } - - var allMatches []*Item - if empty || !m.sort { - allMatches = []*Item{} - for _, matches := range partialResults { - allMatches = append(allMatches, matches...) - } - } else { - allMatches = SortMerge(partialResults) - } - - return allMatches, false + return NewMerger(partialResults, !empty && m.sort), false } func (m *Matcher) Reset(chunks []*Chunk, patternRunes []rune, cancel bool) { diff --git a/src/merger.go b/src/merger.go new file mode 100644 index 00000000..7ff32434 --- /dev/null +++ b/src/merger.go @@ -0,0 +1,79 @@ +package fzf + +var EmptyMerger *Merger = NewMerger([][]*Item{}, false) + +type Merger struct { + lists [][]*Item + merged []*Item + cursors []int + done bool +} + +func NewMerger(lists [][]*Item, sorted bool) *Merger { + mg := Merger{ + lists: lists, + merged: []*Item{}, + cursors: make([]int, len(lists)), + done: false} + if !sorted { + for _, list := range lists { + mg.merged = append(mg.merged, list...) + } + mg.done = true + } + return &mg +} + +func (mg *Merger) Length() int { + cnt := 0 + for _, list := range mg.lists { + cnt += len(list) + } + return cnt +} + +func (mg *Merger) Get(idx int) *Item { + if mg.done { + return mg.merged[idx] + } else if len(mg.lists) == 1 { + return mg.lists[0][idx] + } + mg.buildUpto(idx) + return mg.merged[idx] +} + +func (mg *Merger) buildUpto(upto int) { + numBuilt := len(mg.merged) + if numBuilt > upto { + return + } + + for i := numBuilt; i <= upto; i++ { + minRank := Rank{0, 0, 0} + minIdx := -1 + for listIdx, list := range mg.lists { + cursor := mg.cursors[listIdx] + if cursor < 0 || cursor == len(list) { + mg.cursors[listIdx] = -1 + continue + } + if cursor >= 0 { + rank := list[cursor].Rank() + if minIdx < 0 || compareRanks(rank, minRank) { + minRank = rank + minIdx = listIdx + } + } + mg.cursors[listIdx] = cursor + } + + if minIdx >= 0 { + chosen := mg.lists[minIdx] + mg.merged = append(mg.merged, chosen[mg.cursors[minIdx]]) + mg.cursors[minIdx] += 1 + } else { + mg.done = true + return + } + } +} diff --git a/src/merger_test.go b/src/merger_test.go new file mode 100644 index 00000000..19941b17 --- /dev/null +++ b/src/merger_test.go @@ -0,0 +1,80 @@ +package fzf + +import ( + "math/rand" + "sort" + "testing" +) + +func assert(t *testing.T, cond bool, msg ...string) { + if !cond { + t.Error(msg) + } +} + +func randItem() *Item { + return &Item{ + rank: Rank{uint16(rand.Uint32()), uint16(rand.Uint32()), rand.Uint32()}} +} + +func TestEmptyMerger(t *testing.T) { + assert(t, EmptyMerger.Length() == 0, "Not empty") +} + +func buildLists(partiallySorted bool) ([][]*Item, []*Item) { + numLists := 4 + lists := make([][]*Item, numLists) + cnt := 0 + for i := 0; i < numLists; i++ { + numItems := rand.Int() % 20 + cnt += numItems + lists[i] = make([]*Item, numItems) + for j := 0; j < numItems; j++ { + item := randItem() + lists[i][j] = item + } + if partiallySorted { + sort.Sort(ByRelevance(lists[i])) + } + } + items := []*Item{} + for _, list := range lists { + items = append(items, list...) + } + return lists, items +} + +func TestMergerUnsorted(t *testing.T) { + lists, items := buildLists(false) + cnt := len(items) + + // Not sorted: same order + mg := NewMerger(lists, false) + assert(t, cnt == mg.Length(), "Invalid Length") + for i := 0; i < cnt; i++ { + assert(t, items[i] == mg.Get(i), "Invalid Get") + } +} + +func TestMergerSorted(t *testing.T) { + lists, items := buildLists(true) + cnt := len(items) + + // Sorted sorted order + mg := NewMerger(lists, true) + assert(t, cnt == mg.Length(), "Invalid Length") + sort.Sort(ByRelevance(items)) + for i := 0; i < cnt; i++ { + if items[i] != mg.Get(i) { + t.Error("Not sorted", items[i], mg.Get(i)) + } + } + + // Inverse order + mg2 := NewMerger(lists, true) + for i := cnt - 1; i >= cnt; i-- { + if items[i] != mg2.Get(i) { + t.Error("Not sorted", items[i], mg2.Get(i)) + } + } +} diff --git a/src/terminal.go b/src/terminal.go index 77a70f78..7b83a475 100644 --- a/src/terminal.go +++ b/src/terminal.go @@ -25,7 +25,7 @@ type Terminal struct { count int progress int reading bool - list []*Item + merger *Merger selected map[*string]*string reqBox *EventBox eventBox *EventBox @@ -64,7 +64,7 @@ func NewTerminal(opts *Options, eventBox *EventBox) *Terminal { input: input, multi: opts.Multi, printQuery: opts.PrintQuery, - list: []*Item{}, + merger: EmptyMerger, selected: make(map[*string]*string), reqBox: NewEventBox(), eventBox: eventBox, @@ -99,10 +99,10 @@ func (t *Terminal) UpdateProgress(progress float32) { t.reqBox.Set(REQ_INFO, nil) } -func (t *Terminal) UpdateList(list []*Item) { +func (t *Terminal) UpdateList(merger *Merger) { t.mutex.Lock() t.progress = 100 - t.list = list + t.merger = merger t.mutex.Unlock() t.reqBox.Set(REQ_INFO, nil) t.reqBox.Set(REQ_LIST, nil) @@ -110,7 +110,7 @@ func (t *Terminal) UpdateList(list []*Item) { func (t *Terminal) listIndex(y int) int { if t.tac { - return len(t.list) - y - 1 + return t.merger.Length() - y - 1 } else { return y } @@ -121,8 +121,8 @@ func (t *Terminal) output() { fmt.Println(string(t.input)) } if len(t.selected) == 0 { - if len(t.list) > t.cy { - t.list[t.listIndex(t.cy)].Print() + if t.merger.Length() > t.cy { + t.merger.Get(t.listIndex(t.cy)).Print() } } else { for ptr, orig := range t.selected { @@ -175,7 +175,7 @@ func (t *Terminal) printInfo() { } t.move(1, 2, false) - output := fmt.Sprintf("%d/%d", len(t.list), t.count) + output := fmt.Sprintf("%d/%d", t.merger.Length(), t.count) if t.multi && len(t.selected) > 0 { output += fmt.Sprintf(" (%d)", len(t.selected)) } @@ -189,11 +189,11 @@ func (t *Terminal) printList() { t.constrain() maxy := maxItems() - count := len(t.list) - t.offset + count := t.merger.Length() - t.offset for i := 0; i < maxy; i++ { t.move(i+2, 0, true) if i < count { - t.printItem(t.list[t.listIndex(i+t.offset)], i == t.cy-t.offset) + t.printItem(t.merger.Get(t.listIndex(i+t.offset)), i == t.cy-t.offset) } } } @@ -417,7 +417,7 @@ func (t *Terminal) Loop() { previousInput := t.input events := []EventType{REQ_PROMPT} toggle := func() { - item := t.list[t.listIndex(t.cy)] + item := t.merger.Get(t.listIndex(t.cy)) if _, found := t.selected[item.text]; !found { t.selected[item.text] = item.origText } else { @@ -460,13 +460,13 @@ func (t *Terminal) Loop() { t.cx -= 1 } case C.TAB: - if t.multi && len(t.list) > 0 { + if t.multi && t.merger.Length() > 0 { toggle() t.vmove(-1) req(REQ_LIST, REQ_INFO) } case C.BTAB: - if t.multi && len(t.list) > 0 { + if t.multi && t.merger.Length() > 0 { toggle() t.vmove(1) req(REQ_LIST, REQ_INFO) @@ -567,7 +567,7 @@ func (t *Terminal) Loop() { } func (t *Terminal) constrain() { - count := len(t.list) + count := t.merger.Length() height := C.MaxY() - 2 diffpos := t.cy - t.offset |