From cd847affb79ea6438c9721635724efc6f58e2215 Mon Sep 17 00:00:00 2001 From: Junegunn Choi Date: Mon, 12 Jan 2015 12:56:17 +0900 Subject: Reorganize source code --- src/Makefile | 2 +- src/algo.go | 155 -------------------------------------------- src/algo/algo.go | 155 ++++++++++++++++++++++++++++++++++++++++++++ src/algo/algo_test.go | 44 +++++++++++++ src/algo_test.go | 44 ------------- src/atomicbool.go | 32 --------- src/atomicbool_test.go | 17 ----- src/chunklist.go | 10 +-- src/constants.go | 9 +-- src/core.go | 10 +-- src/eventbox.go | 77 ---------------------- src/eventbox_test.go | 51 --------------- src/matcher.go | 18 ++--- src/options.go | 3 +- src/pattern.go | 12 ++-- src/pattern_test.go | 8 ++- src/reader.go | 9 ++- src/reader_test.go | 10 ++- src/terminal.go | 39 ++++++----- src/tokenizer.go | 4 +- src/util.go | 45 ------------- src/util/atomicbool.go | 32 +++++++++ src/util/atomicbool_test.go | 17 +++++ src/util/eventbox.go | 80 +++++++++++++++++++++++ src/util/eventbox_test.go | 61 +++++++++++++++++ src/util/util.go | 56 ++++++++++++++++ src/util/util_test.go | 22 +++++++ src/util_test.go | 18 ----- 28 files changed, 544 insertions(+), 496 deletions(-) delete mode 100644 src/algo.go create mode 100644 src/algo/algo.go create mode 100644 src/algo/algo_test.go delete mode 100644 src/algo_test.go delete mode 100644 src/atomicbool.go delete mode 100644 src/atomicbool_test.go delete mode 100644 src/eventbox.go delete mode 100644 src/eventbox_test.go delete mode 100644 src/util.go create mode 100644 src/util/atomicbool.go create mode 100644 src/util/atomicbool_test.go create mode 100644 src/util/eventbox.go create mode 100644 src/util/eventbox_test.go create mode 100644 src/util/util.go create mode 100644 src/util/util_test.go delete mode 100644 src/util_test.go (limited to 'src') diff --git a/src/Makefile b/src/Makefile index 7108f0d9..43a7bc05 100644 --- a/src/Makefile +++ b/src/Makefile @@ -33,7 +33,7 @@ build: fzf/$(BINARY32) fzf/$(BINARY64) test: go get - go test -v + go test -v ./... install: $(BINDIR)/fzf diff --git a/src/algo.go b/src/algo.go deleted file mode 100644 index 5f15ab3b..00000000 --- a/src/algo.go +++ /dev/null @@ -1,155 +0,0 @@ -package fzf - -import "strings" - -/* - * String matching algorithms here do not use strings.ToLower to avoid - * performance penalty. And they assume pattern runes are given in lowercase - * letters when caseSensitive is false. - * - * In short: They try to do as little work as possible. - */ - -// FuzzyMatch performs fuzzy-match -func FuzzyMatch(caseSensitive bool, input *string, pattern []rune) (int, int) { - runes := []rune(*input) - - // 0. (FIXME) How to find the shortest match? - // a_____b__c__abc - // ^^^^^^^^^^ ^^^ - // 1. forward scan (abc) - // *-----*-----*> - // a_____b___abc__ - // 2. reverse scan (cba) - // a_____b___abc__ - // <*** - pidx := 0 - sidx := -1 - eidx := -1 - - for index, char := range runes { - // This is considerably faster than blindly applying strings.ToLower to the - // whole string - if !caseSensitive && char >= 65 && char <= 90 { - char += 32 - } - if char == pattern[pidx] { - if sidx < 0 { - sidx = index - } - if pidx++; pidx == len(pattern) { - eidx = index + 1 - break - } - } - } - - if sidx >= 0 && eidx >= 0 { - pidx-- - for index := eidx - 1; index >= sidx; index-- { - char := runes[index] - if !caseSensitive && char >= 65 && char <= 90 { - char += 32 - } - if char == pattern[pidx] { - if pidx--; pidx < 0 { - sidx = index - break - } - } - } - return sidx, eidx - } - return -1, -1 -} - -// ExactMatchStrings performs exact-match using strings package. -// Currently not used. -func ExactMatchStrings(caseSensitive bool, input *string, pattern []rune) (int, int) { - var str string - if caseSensitive { - str = *input - } else { - str = strings.ToLower(*input) - } - - if idx := strings.Index(str, string(pattern)); idx >= 0 { - prefixRuneLen := len([]rune((*input)[:idx])) - return prefixRuneLen, prefixRuneLen + len(pattern) - } - return -1, -1 -} - -// ExactMatchNaive is a basic string searching algorithm that handles case -// sensitivity. Although naive, it still performs better than the combination -// of strings.ToLower + strings.Index for typical fzf use cases where input -// strings and patterns are not very long. -// -// We might try to implement better algorithms in the future: -// http://en.wikipedia.org/wiki/String_searching_algorithm -func ExactMatchNaive(caseSensitive bool, input *string, pattern []rune) (int, int) { - runes := []rune(*input) - numRunes := len(runes) - plen := len(pattern) - if numRunes < plen { - return -1, -1 - } - - pidx := 0 - for index := 0; index < numRunes; index++ { - char := runes[index] - if !caseSensitive && char >= 65 && char <= 90 { - char += 32 - } - if pattern[pidx] == char { - pidx++ - if pidx == plen { - return index - plen + 1, index + 1 - } - } else { - index -= pidx - pidx = 0 - } - } - return -1, -1 -} - -// PrefixMatch performs prefix-match -func PrefixMatch(caseSensitive bool, input *string, pattern []rune) (int, int) { - runes := []rune(*input) - if len(runes) < len(pattern) { - return -1, -1 - } - - for index, r := range pattern { - char := runes[index] - if !caseSensitive && char >= 65 && char <= 90 { - char += 32 - } - if char != r { - return -1, -1 - } - } - return 0, len(pattern) -} - -// SuffixMatch performs suffix-match -func SuffixMatch(caseSensitive bool, input *string, pattern []rune) (int, int) { - runes := []rune(strings.TrimRight(*input, " ")) - trimmedLen := len(runes) - diff := trimmedLen - len(pattern) - if diff < 0 { - return -1, -1 - } - - for index, r := range pattern { - char := runes[index+diff] - if !caseSensitive && char >= 65 && char <= 90 { - char += 32 - } - if char != r { - return -1, -1 - } - } - return trimmedLen - len(pattern), trimmedLen -} diff --git a/src/algo/algo.go b/src/algo/algo.go new file mode 100644 index 00000000..bc4e5382 --- /dev/null +++ b/src/algo/algo.go @@ -0,0 +1,155 @@ +package algo + +import "strings" + +/* + * String matching algorithms here do not use strings.ToLower to avoid + * performance penalty. And they assume pattern runes are given in lowercase + * letters when caseSensitive is false. + * + * In short: They try to do as little work as possible. + */ + +// FuzzyMatch performs fuzzy-match +func FuzzyMatch(caseSensitive bool, input *string, pattern []rune) (int, int) { + runes := []rune(*input) + + // 0. (FIXME) How to find the shortest match? + // a_____b__c__abc + // ^^^^^^^^^^ ^^^ + // 1. forward scan (abc) + // *-----*-----*> + // a_____b___abc__ + // 2. reverse scan (cba) + // a_____b___abc__ + // <*** + pidx := 0 + sidx := -1 + eidx := -1 + + for index, char := range runes { + // This is considerably faster than blindly applying strings.ToLower to the + // whole string + if !caseSensitive && char >= 65 && char <= 90 { + char += 32 + } + if char == pattern[pidx] { + if sidx < 0 { + sidx = index + } + if pidx++; pidx == len(pattern) { + eidx = index + 1 + break + } + } + } + + if sidx >= 0 && eidx >= 0 { + pidx-- + for index := eidx - 1; index >= sidx; index-- { + char := runes[index] + if !caseSensitive && char >= 65 && char <= 90 { + char += 32 + } + if char == pattern[pidx] { + if pidx--; pidx < 0 { + sidx = index + break + } + } + } + return sidx, eidx + } + return -1, -1 +} + +// ExactMatchStrings performs exact-match using strings package. +// Currently not used. +func ExactMatchStrings(caseSensitive bool, input *string, pattern []rune) (int, int) { + var str string + if caseSensitive { + str = *input + } else { + str = strings.ToLower(*input) + } + + if idx := strings.Index(str, string(pattern)); idx >= 0 { + prefixRuneLen := len([]rune((*input)[:idx])) + return prefixRuneLen, prefixRuneLen + len(pattern) + } + return -1, -1 +} + +// ExactMatchNaive is a basic string searching algorithm that handles case +// sensitivity. Although naive, it still performs better than the combination +// of strings.ToLower + strings.Index for typical fzf use cases where input +// strings and patterns are not very long. +// +// We might try to implement better algorithms in the future: +// http://en.wikipedia.org/wiki/String_searching_algorithm +func ExactMatchNaive(caseSensitive bool, input *string, pattern []rune) (int, int) { + runes := []rune(*input) + numRunes := len(runes) + plen := len(pattern) + if numRunes < plen { + return -1, -1 + } + + pidx := 0 + for index := 0; index < numRunes; index++ { + char := runes[index] + if !caseSensitive && char >= 65 && char <= 90 { + char += 32 + } + if pattern[pidx] == char { + pidx++ + if pidx == plen { + return index - plen + 1, index + 1 + } + } else { + index -= pidx + pidx = 0 + } + } + return -1, -1 +} + +// PrefixMatch performs prefix-match +func PrefixMatch(caseSensitive bool, input *string, pattern []rune) (int, int) { + runes := []rune(*input) + if len(runes) < len(pattern) { + return -1, -1 + } + + for index, r := range pattern { + char := runes[index] + if !caseSensitive && char >= 65 && char <= 90 { + char += 32 + } + if char != r { + return -1, -1 + } + } + return 0, len(pattern) +} + +// SuffixMatch performs suffix-match +func SuffixMatch(caseSensitive bool, input *string, pattern []rune) (int, int) { + runes := []rune(strings.TrimRight(*input, " ")) + trimmedLen := len(runes) + diff := trimmedLen - len(pattern) + if diff < 0 { + return -1, -1 + } + + for index, r := range pattern { + char := runes[index+diff] + if !caseSensitive && char >= 65 && char <= 90 { + char += 32 + } + if char != r { + return -1, -1 + } + } + return trimmedLen - len(pattern), trimmedLen +} diff --git a/src/algo/algo_test.go b/src/algo/algo_test.go new file mode 100644 index 00000000..363b6eee --- /dev/null +++ b/src/algo/algo_test.go @@ -0,0 +1,44 @@ +package algo + +import ( + "strings" + "testing" +) + +func assertMatch(t *testing.T, fun func(bool, *string, []rune) (int, int), caseSensitive bool, input string, pattern string, sidx int, eidx int) { + if !caseSensitive { + pattern = strings.ToLower(pattern) + } + s, e := fun(caseSensitive, &input, []rune(pattern)) + if s != sidx { + t.Errorf("Invalid start index: %d (expected: %d, %s / %s)", s, sidx, input, pattern) + } + if e != eidx { + t.Errorf("Invalid end index: %d (expected: %d, %s / %s)", e, eidx, input, pattern) + } +} + +func TestFuzzyMatch(t *testing.T) { + assertMatch(t, FuzzyMatch, false, "fooBarbaz", "oBZ", 2, 9) + assertMatch(t, FuzzyMatch, true, "fooBarbaz", "oBZ", -1, -1) + assertMatch(t, FuzzyMatch, true, "fooBarbaz", "oBz", 2, 9) + assertMatch(t, FuzzyMatch, true, "fooBarbaz", "fooBarbazz", -1, -1) +} + +func TestExactMatchNaive(t *testing.T) { + assertMatch(t, ExactMatchNaive, false, "fooBarbaz", "oBA", 2, 5) + assertMatch(t, ExactMatchNaive, true, "fooBarbaz", "oBA", -1, -1) + assertMatch(t, ExactMatchNaive, true, "fooBarbaz", "fooBarbazz", -1, -1) +} + +func TestPrefixMatch(t *testing.T) { + assertMatch(t, PrefixMatch, false, "fooBarbaz", "Foo", 0, 3) + assertMatch(t, PrefixMatch, true, "fooBarbaz", "Foo", -1, -1) + assertMatch(t, PrefixMatch, false, "fooBarbaz", "baz", -1, -1) +} + +func TestSuffixMatch(t *testing.T) { + assertMatch(t, SuffixMatch, false, "fooBarbaz", "Foo", -1, -1) + assertMatch(t, SuffixMatch, false, "fooBarbaz", "baz", 6, 9) + assertMatch(t, SuffixMatch, true, "fooBarbaz", "Baz", -1, -1) +} diff --git a/src/algo_test.go b/src/algo_test.go deleted file mode 100644 index 5da01a6d..00000000 --- a/src/algo_test.go +++ /dev/null @@ -1,44 +0,0 @@ -package fzf - -import ( - "strings" - "testing" -) - -func assertMatch(t *testing.T, fun func(bool, *string, []rune) (int, int), caseSensitive bool, input string, pattern string, sidx int, eidx int) { - if !caseSensitive { - pattern = strings.ToLower(pattern) - } - s, e := fun(caseSensitive, &input, []rune(pattern)) - if s != sidx { - t.Errorf("Invalid start index: %d (expected: %d, %s / %s)", s, sidx, input, pattern) - } - if e != eidx { - t.Errorf("Invalid end index: %d (expected: %d, %s / %s)", e, eidx, input, pattern) - } -} - -func TestFuzzyMatch(t *testing.T) { - assertMatch(t, FuzzyMatch, false, "fooBarbaz", "oBZ", 2, 9) - assertMatch(t, FuzzyMatch, true, "fooBarbaz", "oBZ", -1, -1) - assertMatch(t, FuzzyMatch, true, "fooBarbaz", "oBz", 2, 9) - assertMatch(t, FuzzyMatch, true, "fooBarbaz", "fooBarbazz", -1, -1) -} - -func TestExactMatchNaive(t *testing.T) { - assertMatch(t, ExactMatchNaive, false, "fooBarbaz", "oBA", 2, 5) - assertMatch(t, ExactMatchNaive, true, "fooBarbaz", "oBA", -1, -1) - assertMatch(t, ExactMatchNaive, true, "fooBarbaz", "fooBarbazz", -1, -1) -} - -func TestPrefixMatch(t *testing.T) { - assertMatch(t, PrefixMatch, false, "fooBarbaz", "Foo", 0, 3) - assertMatch(t, PrefixMatch, true, "fooBarbaz", "Foo", -1, -1) - assertMatch(t, PrefixMatch, false, "fooBarbaz", "baz", -1, -1) -} - -func TestSuffixMatch(t *testing.T) { - assertMatch(t, SuffixMatch, false, "fooBarbaz", "Foo", -1, -1) - assertMatch(t, SuffixMatch, false, "fooBarbaz", "baz", 6, 9) - assertMatch(t, SuffixMatch, true, "fooBarbaz", "Baz", -1, -1) -} diff --git a/src/atomicbool.go b/src/atomicbool.go deleted file mode 100644 index b264724c..00000000 --- a/src/atomicbool.go +++ /dev/null @@ -1,32 +0,0 @@ -package fzf - -import "sync" - -// AtomicBool is a boxed-class that provides synchronized access to the -// underlying boolean value -type AtomicBool struct { - mutex sync.Mutex - state bool -} - -// NewAtomicBool returns a new AtomicBool -func NewAtomicBool(initialState bool) *AtomicBool { - return &AtomicBool{ - mutex: sync.Mutex{}, - state: initialState} -} - -// Get returns the current boolean value synchronously -func (a *AtomicBool) Get() bool { - a.mutex.Lock() - defer a.mutex.Unlock() - return a.state -} - -// Set updates the boolean value synchronously -func (a *AtomicBool) Set(newState bool) bool { - a.mutex.Lock() - defer a.mutex.Unlock() - a.state = newState - return a.state -} diff --git a/src/atomicbool_test.go b/src/atomicbool_test.go deleted file mode 100644 index 0af45701..00000000 --- a/src/atomicbool_test.go +++ /dev/null @@ -1,17 +0,0 @@ -package fzf - -import "testing" - -func TestAtomicBool(t *testing.T) { - if !NewAtomicBool(true).Get() || NewAtomicBool(false).Get() { - t.Error("Invalid initial value") - } - - ab := NewAtomicBool(true) - if ab.Set(false) { - t.Error("Invalid return value") - } - if ab.Get() { - t.Error("Invalid state") - } -} diff --git a/src/chunklist.go b/src/chunklist.go index 73983b1d..571a59af 100644 --- a/src/chunklist.go +++ b/src/chunklist.go @@ -8,20 +8,20 @@ const ChunkSize int = 100 // Chunk is a list of Item pointers whose size has the upper limit of ChunkSize type Chunk []*Item // >>> []Item -// Transformer is a closure type that builds Item object from a pointer to a +// ItemBuilder is a closure type that builds Item object from a pointer to a // string and an integer -type Transformer func(*string, int) *Item +type ItemBuilder func(*string, int) *Item // ChunkList is a list of Chunks type ChunkList struct { chunks []*Chunk count int mutex sync.Mutex - trans Transformer + trans ItemBuilder } // NewChunkList returns a new ChunkList -func NewChunkList(trans Transformer) *ChunkList { +func NewChunkList(trans ItemBuilder) *ChunkList { return &ChunkList{ chunks: []*Chunk{}, count: 0, @@ -29,7 +29,7 @@ func NewChunkList(trans Transformer) *ChunkList { trans: trans} } -func (c *Chunk) push(trans Transformer, data *string, index int) { +func (c *Chunk) push(trans ItemBuilder, data *string, index int) { *c = append(*c, trans(data, index)) } diff --git a/src/constants.go b/src/constants.go index 80eb6345..a8715700 100644 --- a/src/constants.go +++ b/src/constants.go @@ -1,14 +1,15 @@ package fzf +import ( + "github.com/junegunn/fzf/src/util" +) + // Current version const Version = "0.9.0" -// EventType is the type for fzf events -type EventType int - // fzf events const ( - EvtReadNew EventType = iota + EvtReadNew util.EventType = iota EvtReadFin EvtSearchNew EvtSearchProgress diff --git a/src/core.go b/src/core.go index 65e641c2..ee904135 100644 --- a/src/core.go +++ b/src/core.go @@ -30,6 +30,8 @@ import ( "os" "runtime" "time" + + "github.com/junegunn/fzf/src/util" ) const coordinatorDelayMax time.Duration = 100 * time.Millisecond @@ -59,7 +61,7 @@ func Run(options *Options) { } // Event channel - eventBox := NewEventBox() + eventBox := util.NewEventBox() // Chunk list var chunkList *ChunkList @@ -111,7 +113,7 @@ func Run(options *Options) { looping := true eventBox.Unwatch(EvtReadNew) for looping { - eventBox.Wait(func(events *Events) { + eventBox.Wait(func(events *util.Events) { for evt := range *events { switch evt { case EvtReadFin: @@ -154,7 +156,7 @@ func Run(options *Options) { for { delay := true ticks++ - eventBox.Wait(func(events *Events) { + eventBox.Wait(func(events *util.Events) { defer events.Clear() for evt, value := range *events { switch evt { @@ -185,7 +187,7 @@ func Run(options *Options) { } }) if delay && reading { - dur := DurWithin( + dur := util.DurWithin( time.Duration(ticks)*coordinatorDelayStep, 0, coordinatorDelayMax) time.Sleep(dur) diff --git a/src/eventbox.go b/src/eventbox.go deleted file mode 100644 index 0c8f922a..00000000 --- a/src/eventbox.go +++ /dev/null @@ -1,77 +0,0 @@ -package fzf - -import "sync" - -// Events is a type that associates EventType to any data -type Events map[EventType]interface{} - -// EventBox is used for coordinating events -type EventBox struct { - events Events - cond *sync.Cond - ignore map[EventType]bool -} - -// NewEventBox returns a new EventBox -func NewEventBox() *EventBox { - return &EventBox{ - events: make(Events), - cond: sync.NewCond(&sync.Mutex{}), - ignore: make(map[EventType]bool)} -} - -// Wait blocks the goroutine until signaled -func (b *EventBox) Wait(callback func(*Events)) { - b.cond.L.Lock() - defer b.cond.L.Unlock() - - if len(b.events) == 0 { - b.cond.Wait() - } - - callback(&b.events) -} - -// Set turns on the event type on the box -func (b *EventBox) Set(event EventType, value interface{}) { - b.cond.L.Lock() - defer b.cond.L.Unlock() - b.events[event] = value - if _, found := b.ignore[event]; !found { - b.cond.Broadcast() - } -} - -// Clear clears the events -// Unsynchronized; should be called within Wait routine -func (events *Events) Clear() { - for event := range *events { - delete(*events, event) - } -} - -// Peak peaks at the event box if the given event is set -func (b *EventBox) Peak(event EventType) bool { - b.cond.L.Lock() - defer b.cond.L.Unlock() - _, ok := b.events[event] - return ok -} - -// Watch deletes the events from the ignore list -func (b *EventBox) Watch(events ...EventType) { - b.cond.L.Lock() - defer b.cond.L.Unlock() - for _, event := range events { - delete(b.ignore, event) - } -} - -// Unwatch adds the events to the ignore list -func (b *EventBox) Unwatch(events ...EventType) { - b.cond.L.Lock() - defer b.cond.L.Unlock() - for _, event := range events { - b.ignore[event] = true - } -} diff --git a/src/eventbox_test.go b/src/eventbox_test.go deleted file mode 100644 index 1cd7f220..00000000 --- a/src/eventbox_test.go +++ /dev/null @@ -1,51 +0,0 @@ -package fzf - -import "testing" - -func TestEventBox(t *testing.T) { - eb := NewEventBox() - - // Wait should return immediately - ch := make(chan bool) - - go func() { - eb.Set(EvtReadNew, 10) - ch <- true - <-ch - eb.Set(EvtSearchNew, 10) - eb.Set(EvtSearchNew, 15) - eb.Set(EvtSearchNew, 20) - eb.Set(EvtSearchProgress, 30) - ch <- true - <-ch - eb.Set(EvtSearchFin, 40) - ch <- true - <-ch - }() - - count := 0 - sum := 0 - looping := true - for looping { - <-ch - eb.Wait(func(events *Events) { - for _, value := range *events { - switch val := value.(type) { - case int: - sum += val - looping = sum < 100 - } - } - events.Clear() - }) - ch <- true - count++ - } - - if count != 3 { - t.Error("Invalid number of events", count) - } - if sum != 100 { - t.Error("Invalid sum", sum) - } -} diff --git a/src/matcher.go b/src/matcher.go index b8be2870..1ea9541b 100644 --- a/src/matcher.go +++ b/src/matcher.go @@ -6,6 +6,8 @@ import ( "sort" "sync" "time" + + "github.com/junegunn/fzf/src/util" ) // MatchRequest represents a search request @@ -18,14 +20,14 @@ type MatchRequest struct { type Matcher struct { patternBuilder func([]rune) *Pattern sort bool - eventBox *EventBox - reqBox *EventBox + eventBox *util.EventBox + reqBox *util.EventBox partitions int mergerCache map[string]*Merger } const ( - reqRetry EventType = iota + reqRetry util.EventType = iota reqReset ) @@ -35,12 +37,12 @@ const ( // NewMatcher returns a new Matcher func NewMatcher(patternBuilder func([]rune) *Pattern, - sort bool, eventBox *EventBox) *Matcher { + sort bool, eventBox *util.EventBox) *Matcher { return &Matcher{ patternBuilder: patternBuilder, sort: sort, eventBox: eventBox, - reqBox: NewEventBox(), + reqBox: util.NewEventBox(), partitions: runtime.NumCPU(), mergerCache: make(map[string]*Merger)} } @@ -52,7 +54,7 @@ func (m *Matcher) Loop() { for { var request MatchRequest - m.reqBox.Wait(func(events *Events) { + m.reqBox.Wait(func(events *util.Events) { for _, val := range *events { switch val := val.(type) { case MatchRequest: @@ -128,7 +130,7 @@ func (m *Matcher) scan(request MatchRequest, limit int) (*Merger, bool) { } pattern := request.pattern empty := pattern.IsEmpty() - cancelled := NewAtomicBool(false) + cancelled := util.NewAtomicBool(false) slices := m.sliceChunks(request.chunks) numSlices := len(slices) @@ -202,7 +204,7 @@ func (m *Matcher) scan(request MatchRequest, limit int) (*Merger, bool) { func (m *Matcher) Reset(chunks []*Chunk, patternRunes []rune, cancel bool) { pattern := m.patternBuilder(patternRunes) - var event EventType + var event util.EventType if cancel { event = reqReset } else { diff --git a/src/options.go b/src/options.go index cf0608bd..e1dba299 100644 --- a/src/options.go +++ b/src/options.go @@ -2,10 +2,11 @@ package fzf import ( "fmt" - "github.com/junegunn/go-shellwords" "os" "regexp" "strings" + + "github.com/junegunn/go-shellwords" ) const usage = `usage: fzf [options] diff --git a/src/pattern.go b/src/pattern.go index 9f32de60..17e3b6b8 100644 --- a/src/pattern.go +++ b/src/pattern.go @@ -4,6 +4,8 @@ import ( "regexp" "sort" "strings" + + "github.com/junegunn/fzf/src/algo" ) const uppercaseLetters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" @@ -112,10 +114,10 @@ func BuildPattern(mode Mode, caseMode Case, delimiter: delimiter, procFun: make(map[termType]func(bool, *string, []rune) (int, int))} - ptr.procFun[termFuzzy] = FuzzyMatch - ptr.procFun[termExact] = ExactMatchNaive - ptr.procFun[termPrefix] = PrefixMatch - ptr.procFun[termSuffix] = SuffixMatch + ptr.procFun[termFuzzy] = algo.FuzzyMatch + ptr.procFun[termExact] = algo.ExactMatchNaive + ptr.procFun[termPrefix] = algo.PrefixMatch + ptr.procFun[termSuffix] = algo.SuffixMatch _patternCache[asString] = ptr return ptr @@ -245,7 +247,7 @@ func (p *Pattern) fuzzyMatch(chunk *Chunk) []*Item { matches := []*Item{} for _, item := range *chunk { input := p.prepareInput(item) - if sidx, eidx := p.iter(FuzzyMatch, input, p.text); sidx >= 0 { + if sidx, eidx := p.iter(algo.FuzzyMatch, input, p.text); sidx >= 0 { matches = append(matches, dupItem(item, []Offset{Offset{int32(sidx), int32(eidx)}})) } diff --git a/src/pattern_test.go b/src/pattern_test.go index c006c451..4d36eda5 100644 --- a/src/pattern_test.go +++ b/src/pattern_test.go @@ -1,6 +1,10 @@ package fzf -import "testing" +import ( + "testing" + + "github.com/junegunn/fzf/src/algo" +) func TestParseTermsExtended(t *testing.T) { terms := parseTerms(ModeExtended, @@ -55,7 +59,7 @@ func TestExact(t *testing.T) { pattern := BuildPattern(ModeExtended, CaseSmart, []Range{}, nil, []rune("'abc")) str := "aabbcc abc" - sidx, eidx := ExactMatchNaive(pattern.caseSensitive, &str, pattern.terms[0].text) + sidx, eidx := algo.ExactMatchNaive(pattern.caseSensitive, &str, pattern.terms[0].text) if sidx != 7 || eidx != 10 { t.Errorf("%s / %d / %d", pattern.terms, sidx, eidx) } diff --git a/src/reader.go b/src/reader.go index 269a2fdc..2c10b8aa 100644 --- a/src/reader.go +++ b/src/reader.go @@ -1,13 +1,12 @@ package fzf -// #include -import "C" - import ( "bufio" "io" "os" "os/exec" + + "github.com/junegunn/fzf/src/util" ) const defaultCommand = `find * -path '*/\.*' -prune -o -type f -print -o -type l -print 2> /dev/null` @@ -15,12 +14,12 @@ const defaultCommand = `find * -path '*/\.*' -prune -o -type f -print -o -type l // Reader reads from command or standard input type Reader struct { pusher func(string) - eventBox *EventBox + eventBox *util.EventBox } // ReadSource reads data from the default command or from standard input func (r *Reader) ReadSource() { - if int(C.isatty(C.int(os.Stdin.Fd()))) != 0 { + if util.IsTty() { cmd := os.Getenv("FZF_DEFAULT_COMMAND") if len(cmd) == 0 { cmd = defaultCommand diff --git a/src/reader_test.go b/src/reader_test.go index 630f6faa..5800b3f2 100644 --- a/src/reader_test.go +++ b/src/reader_test.go @@ -1,10 +1,14 @@ package fzf -import "testing" +import ( + "testing" + + "github.com/junegunn/fzf/src/util" +) func TestReadFromCommand(t *testing.T) { strs := []string{} - eb := NewEventBox() + eb := util.NewEventBox() reader := Reader{ pusher: func(s string) { strs = append(strs, s) }, eventBox: eb} @@ -26,7 +30,7 @@ func TestReadFromCommand(t *testing.T) { } // Wait should return immediately - eb.Wait(func(events *Events) { + eb.Wait(func(events *util.Events) { if _, found := (*events)[EvtReadNew]; !found { t.Errorf("%s", events) } diff --git a/src/terminal.go b/src/terminal.go index daf63c5c..4204a1da 100644 --- a/src/terminal.go +++ b/src/terminal.go @@ -2,13 +2,16 @@ package fzf import ( "fmt" - C "github.com/junegunn/fzf/src/curses" - "github.com/junegunn/go-runewidth" "os" "regexp" "sort" "sync" "time" + + C "github.com/junegunn/fzf/src/curses" + "github.com/junegunn/fzf/src/util" + + "github.com/junegunn/go-runewidth" ) // Terminal represents terminal input/output @@ -28,8 +31,8 @@ type Terminal struct { reading bool merger *Merger selected map[*string]*string - reqBox *EventBox - eventBox *EventBox + reqBox *util.EventBox + eventBox *util.EventBox mutex sync.Mutex initFunc func() suppress bool @@ -38,7 +41,7 @@ type Terminal struct { var _spinner = []string{`-`, `\`, `|`, `/`, `-`, `\`, `|`, `/`} const ( - reqPrompt EventType = iota + reqPrompt util.EventType = iota reqInfo reqList reqRefresh @@ -53,7 +56,7 @@ const ( ) // NewTerminal returns new Terminal object -func NewTerminal(opts *Options, eventBox *EventBox) *Terminal { +func NewTerminal(opts *Options, eventBox *util.EventBox) *Terminal { input := []rune(opts.Query) return &Terminal{ prompt: opts.Prompt, @@ -68,7 +71,7 @@ func NewTerminal(opts *Options, eventBox *EventBox) *Terminal { printQuery: opts.PrintQuery, merger: EmptyMerger, selected: make(map[*string]*string), - reqBox: NewEventBox(), + reqBox: util.NewEventBox(), eventBox: eventBox, mutex: sync.Mutex{}, suppress: true, @@ -288,7 +291,7 @@ func (*Terminal) printHighlighted(item *Item, bold bool, col1 int, col2 int) { b, e := offset[0], offset[1] b += 2 - diff e += 2 - diff - b = Max32(b, 2) + b = util.Max32(b, 2) if b < e { offsets[idx] = Offset{b, e} } @@ -300,8 +303,8 @@ func (*Terminal) printHighlighted(item *Item, bold bool, col1 int, col2 int) { sort.Sort(ByOrder(offsets)) var index int32 for _, offset := range offsets { - b := Max32(index, offset[0]) - e := Max32(index, offset[1]) + b := util.Max32(index, offset[0]) + e := util.Max32(index, offset[1]) C.CPrint(col1, bold, string(text[index:b])) C.CPrint(col2, bold, string(text[b:e])) index = e @@ -388,7 +391,7 @@ func (t *Terminal) Loop() { go func() { for { - t.reqBox.Wait(func(events *Events) { + t.reqBox.Wait(func(events *util.Events) { defer events.Clear() t.mutex.Lock() for req := range *events { @@ -426,8 +429,8 @@ func (t *Terminal) Loop() { t.mutex.Lock() previousInput := t.input - events := []EventType{reqPrompt} - req := func(evts ...EventType) { + events := []util.EventType{reqPrompt} + req := func(evts ...util.EventType) { for _, event := range evts { events = append(events, event) if event == reqClose || event == reqQuit { @@ -538,7 +541,7 @@ func (t *Terminal) Loop() { t.cx++ case C.Mouse: me := event.MouseEvent - mx, my := Min(len(t.input), Max(0, me.X-len(t.prompt))), me.Y + mx, my := util.Constrain(me.X-len(t.prompt), 0, len(t.input)), me.Y if !t.reverse { my = C.MaxY() - my - 1 } @@ -588,7 +591,7 @@ func (t *Terminal) constrain() { height := C.MaxY() - 2 diffpos := t.cy - t.offset - t.cy = Max(0, Min(t.cy, count-1)) + t.cy = util.Constrain(t.cy, 0, count-1) if t.cy > t.offset+(height-1) { // Ceil @@ -600,8 +603,8 @@ func (t *Terminal) constrain() { // Adjustment if count-t.offset < height { - t.offset = Max(0, count-height) - t.cy = Max(0, Min(t.offset+diffpos, count-1)) + t.offset = util.Max(0, count-height) + t.cy = util.Constrain(t.offset+diffpos, 0, count-1) } } @@ -614,7 +617,7 @@ func (t *Terminal) vmove(o int) { } func (t *Terminal) vset(o int) bool { - t.cy = Max(0, Min(o, t.merger.Length()-1)) + t.cy = util.Constrain(o, 0, t.merger.Length()-1) return t.cy == o } diff --git a/src/tokenizer.go b/src/tokenizer.go index 294329b0..26aebd94 100644 --- a/src/tokenizer.go +++ b/src/tokenizer.go @@ -4,6 +4,8 @@ import ( "regexp" "strconv" "strings" + + "github.com/junegunn/fzf/src/util" ) const rangeEllipsis = 0 @@ -180,7 +182,7 @@ func Transform(tokens []Token, withNth []Range) *Transformed { end += numTokens + 1 } } - minIdx = Max(0, begin-1) + minIdx = util.Max(0, begin-1) for idx := begin; idx <= end; idx++ { if idx >= 1 && idx <= numTokens { part += *tokens[idx-1].text diff --git a/src/util.go b/src/util.go deleted file mode 100644 index 5461705f..00000000 --- a/src/util.go +++ /dev/null @@ -1,45 +0,0 @@ -package fzf - -import "time" - -// Max returns the largest integer -func Max(first int, items ...int) int { - max := first - for _, item := range items { - if item > max { - max = item - } - } - return max -} - -// Max32 returns the largest 32-bit integer -func Max32(first int32, second int32) int32 { - if first > second { - return first - } - return second -} - -// Min returns the smallest integer -func Min(first int, items ...int) int { - min := first - for _, item := range items { - if item < min { - min = item - } - } - return min -} - -// DurWithin limits the given time.Duration with the upper and lower bounds -func DurWithin( - val time.Duration, min time.Duration, max time.Duration) time.Duration { - if val < min { - return min - } - if val > max { - return max - } - return val -} diff --git a/src/util/atomicbool.go b/src/util/atomicbool.go new file mode 100644 index 00000000..9e1bdc8f --- /dev/null +++ b/src/util/atomicbool.go @@ -0,0 +1,32 @@ +package util + +import "sync" + +// AtomicBool is a boxed-class that provides synchronized access to the +// underlying boolean value +type AtomicBool struct { + mutex sync.Mutex + state bool +} + +// NewAtomicBool returns a new AtomicBool +func NewAtomicBool(initialState bool) *AtomicBool { + return &AtomicBool{ + mutex: sync.Mutex{}, + state: initialState} +} + +// Get returns the current boolean value synchronously +func (a *AtomicBool) Get() bool { + a.mutex.Lock() + defer a.mutex.Unlock() + return a.state +} + +// Set updates the boolean value synchronously +func (a *AtomicBool) Set(newState bool) bool { + a.mutex.Lock() + defer a.mutex.Unlock() + a.state = newState + return a.state +} diff --git a/src/util/atomicbool_test.go b/src/util/atomicbool_test.go new file mode 100644 index 00000000..1feff79c --- /dev/null +++ b/src/util/atomicbool_test.go @@ -0,0 +1,17 @@ +package util + +import "testing" + +func TestAtomicBool(t *testing.T) { + if !NewAtomicBool(true).Get() || NewAtomicBool(false).Get() { + t.Error("Invalid initial value") + } + + ab := NewAtomicBool(true) + if ab.Set(false) { + t.Error("Invalid return value") + } + if ab.Get() { + t.Error("Invalid state") + } +} diff --git a/src/util/eventbox.go b/src/util/eventbox.go new file mode 100644 index 00000000..568ad9f7 --- /dev/null +++ b/src/util/eventbox.go @@ -0,0 +1,80 @@ +package util + +import "sync" + +// EventType is the type for fzf events +type EventType int + +// Events is a type that associates EventType to any data +type Events map[EventType]interface{} + +// EventBox is used for coordinating events +type EventBox struct { + events Events + cond *sync.Cond + ignore map[EventType]bool +} + +// NewEventBox returns a new EventBox +func NewEventBox() *EventBox { + return &EventBox{ + events: make(Events), + cond: sync.NewCond(&sync.Mutex{}), + ignore: make(map[EventType]bool)} +} + +// Wait blocks the goroutine until signaled +func (b *EventBox) Wait(callback func(*Events)) { + b.cond.L.Lock() + defer b.cond.L.Unlock() + + if len(b.events) == 0 { + b.cond.Wait() + } + + callback(&b.events) +} + +// Set turns on the event type on the box +func (b *EventBox) Set(event EventType, value interface{}) { + b.cond.L.Lock() + defer b.cond.L.Unlock() + b.events[event] = value + if _, found := b.ignore[event]; !found { + b.cond.Broadcast() + } +} + +// Clear clears the events +// Unsynchronized; should be called within Wait routine +func (events *Events) Clear() { + for event := range *events { + delete(*events, event) + } +} + +// Peak peaks at the event box if the given event is set +func (b *EventBox) Peak(event EventType) bool { + b.cond.L.Lock() + defer b.cond.L.Unlock() + _, ok := b.events[event] + return ok +} + +// Watch deletes the events from the ignore list +func (b *EventBox) Watch(events ...EventType) { + b.cond.L.Lock() + defer b.cond.L.Unlock() + for _, event := range events { + delete(b.ignore, event) + } +} + +// Unwatch adds the events to the ignore list +func (b *EventBox) Unwatch(events ...EventType) { + b.cond.L.Lock() + defer b.cond.L.Unlock() + for _, event := range events { + b.ignore[event] = true + } +} diff --git a/src/util/eventbox_test.go b/src/util/eventbox_test.go new file mode 100644 index 00000000..5a9dc302 --- /dev/null +++ b/src/util/eventbox_test.go @@ -0,0 +1,61 @@ +package util + +import "testing" + +// fzf events +const ( + EvtReadNew EventType = iota + EvtReadFin + EvtSearchNew + EvtSearchProgress + EvtSearchFin + EvtClose +) + +func TestEventBox(t *testing.T) { + eb := NewEventBox() + + // Wait should return immediately + ch := make(chan bool) + + go func() { + eb.Set(EvtReadNew, 10) + ch <- true + <-ch + eb.Set(EvtSearchNew, 10) + eb.Set(EvtSearchNew, 15) + eb.Set(EvtSearchNew, 20) + eb.Set(EvtSearchProgress, 30) + ch <- true + <-ch + eb.Set(EvtSearchFin, 40) + ch <- true + <-ch + }() + + count := 0 + sum := 0 + looping := true + for looping { + <-ch + eb.Wait(func(events *Events) { + for _, value := range *events { + switch val := value.(type) { + case int: + sum += val + looping = sum < 100 + } + } + events.Clear() + }) + ch <- true + count++ + } + + if count != 3 { + t.Error("Invalid number of events", count) + } + if sum != 100 { + t.Error("Invalid sum", sum) + } +} diff --git a/src/util/util.go b/src/util/util.go new file mode 100644 index 00000000..14833c04 --- /dev/null +++ b/src/util/util.go @@ -0,0 +1,56 @@ +package util + +// #include +import "C" + +import ( + "os" + "time" +) + +// Max returns the largest integer +func Max(first int, items ...int) int { + max := first + for _, item := range items { + if item > max { + max = item + } + } + return max +} + +// Max32 returns the largest 32-bit integer +func Max32(first int32, second int32) int32 { + if first > second { + return first + } + return second +} + +// Constrain limits the given integer with the upper and lower bounds +func Constrain(val int, min int, max int) int { + if val < min { + return min + } + if val > max { + return max + } + return val +} + +// DurWithin limits the given time.Duration with the upper and lower bounds +func DurWithin( + val time.Duration, min time.Duration, max time.Duration) time.Duration { + if val < min { + return min + } + if val > max { + return max + } + return val +} + +// IsTty returns true is stdin is a terminal +func IsTty() bool { + return int(C.isatty(C.int(os.Stdin.Fd()))) != 0 +} diff --git a/src/util/util_test.go b/src/util/util_test.go new file mode 100644 index 00000000..06cfd4f2 --- /dev/null +++ b/src/util/util_test.go @@ -0,0 +1,22 @@ +package util + +import "testing" + +func TestMax(t *testing.T) { + if Max(-2, 5, 1, 4, 3) != 5 { + t.Error("Invalid result") + } +} + +func TestContrain(t *testing.T) { + if Constrain(-3, -1, 3) != -1 { + t.Error("Expected", -1) + } + if Constrain(2, -1, 3) != 2 { + t.Error("Expected", 2) + } + + if Constrain(5, -1, 3) != 3 { + t.Error("Expected", 3) + } +} diff --git a/src/util_test.go b/src/util_test.go deleted file mode 100644 index 814b42ce..00000000 --- a/src/util_test.go +++ /dev/null @@ -1,18 +0,0 @@ -package fzf - -import "testing" - -func TestMax(t *testing.T) { - if Max(-2, 5, 1, 4, 3) != 5 { - t.Error("Invalid result") - } -} - -func TestMin(t *testing.T) { - if Min(2, -3) != -3 { - t.Error("Invalid result") - } - if Min(-2, 5, 1, 4, 3) != -2 { - t.Error("Invalid result") - } -} -- cgit v1.2.3